We show two discrete memoryless source (DMS) rate-distortion (R-D) problems with continuous alphabets where the optimal reconstruction distributions are discrete. The first problem is a Gaussian distributed source with square error distortion but a peak-limited reconstruction alphabet. The second is a source distribution related to the generalized inverse Gaussian (GIG) distribution with a certain distortion measure.

The classic problem for a channel with inputs X, outputs Y, and conditional probability pY |X(y|x) is to find the distribution pX(x) that maximizes Shannon's I(X; Y) subject perhaps to constraints imposed on pX(x). Here, we seek instead, for a specified pX(x), the channel pY|X(y|x) that maximizes I(X; Y) subject to constraints on pY |X(y|x). That is, we investigate the part of joint source-channel coding that matches channels to sources. We assume that pX(x) and pY |X(y|x) are pdfs, eventually relaxing this assumption somewhat. We consider only time-discrete memoryless channels. Our motivation for studying this problem stems from neuroscience. Energy costs therefore must be analyzed and addressed in detail if one hopes to understand how Nature has built neuron “channels” that are so astoundingly energy efficient. However, our general theory is not limited to neuroscience nor limited solely to constraints on energy expenditure.

Neuronal information processing is energetically costly. Energy supply restrictions on information processing have resulted in the evolution of brains to compute and communicate information with remarkable energy efficiency. Indeed, energy minimization subject to functional constraints is a unifying principle. Toward better comprehension of neuronal information processing and communication from an information-energy standpoint, we consider a continuous time, continuous state-space neuron model with a generalized inverse Gaussian (GIG) conditional density. This GIG model arises from a Lévy diffusion that contains both homogeneous Poisson processes and Wiener processes with drift as special cases. We show that, when the energy constraints consist of a tripartite family apropos of the GIG model, the distribution of input excitation, A, that maximizes bits per Joule (bpJ) generates an output interspike interval duration T that possesses a related GIG marginal distribution. Most importantly, we obtain the exact expression for the bpJ-maximizing distribution of A in terms of Bessel functions that are readily evaluated numerically. This permits display of the strictly concave curves of bpJ-maximized mutual information I(A; T). Because bpJ equals bits per second/watt, these curves serve as the Shannon-theory capacity v. power curves for GIG neuron models. We show that the noise in GIG channels is essentially multiplicative, so our results may have significance for broader classes of fading channels.

Neuronal information processing is energetically costly. Energy supply restrictions on information processing have caused brains to evolve to compute and communicate information with remarkable efficiency. Indeed, energy minimization subject to functional constraints is a unifying principle. Toward better comprehension of neuronal information processing and communication from an information-energy standpoint, we consider a neuron model with a generalized inverse Gaussian (GIG) conditional density. This GIG model arises from a Lévy diffusion process that is more general than that of a Wiener process with drift. We show that, when the GIG neuron operates so as to maximize bits per Joule (bpJ), the output interspike interval (ISI) distribution is a related GIG marginal distribution. Also, we specify how to obtain the associated input distribution fΛ(λ) numerically. By generalizing from the Gamma and inverse Gaussian (IG) families to the GIG family, the derived results contain both the homogeneous Poisson and Wiener processes as special cases. The results allow us to readily compute the tradeoff between information rate (bits/second) and average power (Joules/second) in the GIG class, reminiscent of Shannon's celebrated formula for such curves for the additive Gaussian family.

Multipacket reception (MPR) refers to physical layers where receivers can decode multiple simultaneously transmitted packets. In this paper we investigate the resulting performance of conjoining carrier sense multiple access (CSMA) communications with MPR. We report on its maximum achievable stable throughput with decentralized control and show there can be throughput gain over slotted ALOHA (S-ALOHA), the non-channel-sensing protocol of choice. However, this gain diminishes as the physical layer's MPR strength increases, thereby diminishing the need for channel sensing. Nonetheless, for systems evolving from a single-user (SU) to a multiple-user (MU) channel, CSMA can furnish significantly more efficient utilization of MPR capacity than S-ALOHA. This is meaningful in practice because the emerging generation of the widely deployed IEEE 802.11 wireless local area networks (WLAN) - 802.11ac - is adapting MPR and will operate in said region. In that regard, we also discuss the effective usage of a channel's resources for MPR and highlight the advantages multiuser-MIMO (MU-MIMO), an MPR technique, can offer to WLANs. Using early design specifications of 802.11ac, we show that the existing SU-oriented 802.11 MAC parameters can under-utilize the MPR capacity offered by a MU-oriented physical layer.

While there has been much research on the capacity of the collision channel for multiple access protocols, there has been little investigation on their fundamental performance with multipacket reception (MPR)-capable channels, which allow more than one simultaneous transmissions to be successfully received. In this paper we investigate the properties of these MPR channels and provide an upper bound for their multiaccess capacities with a genie-aided argument. Our results not only give insights into the limiting efficiency with which multiaccessing can be performed in the MPR environment, but also generalize familiar results from classical multiaccess theory.

Given enough physical constraints, the format of optimal computation may resolve into a rather small set of options, which we call design specifications. Our interest centers on computational problems that are so intensive, relative to the time and energy available, that they can be solved only in a probabilistic fashion. Here we consider just information and energy in one particular computational format, called neural-like (NL), and characterized as massively parallel, analog computation. Within this format, we consider only the design of a single NL element and the nature of its inputs. Importantly, we provide a specific mathematical format of a simple NL element. We consider this format to be minimal and generic and, therefore, extendable to structures composed of several NL compartments. Secondly, the information and energy constraints are linked, via Shannon's entropy, to classical results from mathematical statistics yielding design specifications that go beyond our initial description of a NL element and its inputs. Critically, for a NL element to preserve all of its relevant input-information at minimal energetic cost, it must transform its inputs so as to create and communicate a minimal sufficient statistic. Then, the assumptions associated with producing such a statistic become new design specifications for NL computing.

How neurons in the cerebral cortex process and transmit information is a long-standing question in systems neuroscience. To analyze neuronal activity from an information-energy efficiency standpoint, Berger and Levy calculated the maximum Shannon mutual information transfer per unit of energy expenditure of an idealized integrate-and-fire (IIF) neuron whose excitatory synapses all have the same weight. Here, we extend their IIF model to a biophysically more realistic one in which synaptic weights are unequal. Using information theory, random Poisson measures, and the maximum entropy principle, we show that the probability density function (pdf) of interspike interval (ISI) duration induced by the bits per joule (bpj) maximizing pdf fΛ(λ) of the excitatory postsynaptic potential (EPSP) intensity remains equal to the delayed gamma distribution of the IIF model. We then show that, in the case of unequal weights, fΛ(·) satisfies an inhomogeneous Cauchy-Euler equation with variable coefficients for which we provide the general solution form.

A neuroscience-based mathematical model of how a neuron stochastically processes data and communicates information is introduced and analyzed. Call the neuron in question 'neuron j", or just "j". The information j transmits approximately describes the time-varying intensity of the excitation j is continuously experiencing from neural spike trains delivered to its synapses by thousands of other neurons. Neuron j "encodes" this excitation history into a sequence of time instants at which it generates neural spikes of its own. By propagating these spikes along its axon, j acts as a multiaccess, partially degraded broadcast channel with thousands of input and output terminals that employs a time-continuous version of pulse position modulation. The mathematical model features three parameters, m, ¿, and b, which largely characterize j as an engine of computation and communication. Each set of values of these parameters corresponds to a long term maximization of the bits j conveys to its targets per joule it expends doing so, which is achieved by distributing the random duration between successive spikes j generates according to a gamma pdf with parameters ¿ and b and distributing b/A according to a beta probability density with parameters ¿ and m-¿, whereAis the random intensity of the effectively Poisson process of spikes that arrive to the union of all ofj's synapses at a randomly chosen time instant.

Understanding how a biological neuron works has been a major goal in neuroscience. Under the Poisson-excitation assumption, results from earlier study by Suksompong and Berger on the timing jitter in the leaky integrate-and-fire (LIF) model of neurons are used to determine families of neural thresholding functions that are appropriate in certain interesting senses. Next, the neuron is treated as a communication channel for which information-theoretic quantities can be calculated. In particular, the optimal distribution of the Poisson excitation intensity is numerically evaluated along with the corresponding capacity using the Blahut-Arimoto algorithm. Simple formulas which approximate the optimal intensity distribution are given. Furthermore, the Jimbo-Kunisawa algorithm is used to explore energy-efficient operations for neuron. Finally, a rate-matching argument leads to a unique operating condition which turns out to agree with experimentally observed rate.

We introduce and analyze a biologically motivated mathematical model of a neuron in primary cortex that we call neuron j, or just j. Our goal is to ascertain how j maximizes the ratio of the information it conveys to the energy it expends.

It is known that the worst case near-far resistance of optimum multiuser detectors for asynchronous Gaussian multiple-access channels can be expressed in terms of a class of block-tridiagonal matrices, and the minimal eigenvalues of such a class of block-tridiagonal matrices serve as a good measure of the worst case near-far resistance. In this paper, we focus on the two-user scenario where each block-tridiagonal matrix under consideration is a tridiagonal matrix. We derive closed-form expressions for the minimal eigenvalues of such a class of tridiagonal matrices in terms of the largest real solution of a trigonometric equation in[0,pi]. We also obtain lower bounds and upper bounds on the minimal eigenvalues which improve on previously known results in the literature.

In this paper, we introduce a distributed source coding scheme called successive Wyner-Ziv coding. We show that every point in the rate region of the quadratic Gaussian CEO problem can be achieved via successive Wyner-Ziv coding. The concept of successive refinement in single source coding is generalized to the distributed source coding scenario, which we refer to as distributed successive refinement. For the quadratic Gaussian CEO problem, we establish a necessary and sufficient condition for distributed successive refinement, where the successive Wyner-Ziv coding scheme plays an important role.

We consider a distributed source coding system in which several observations must be encoded separately and communicated to the decoder by using limited transmission rate. We introduce a robust distributed coding scheme which flexibly trades off between system robustness and compression efficiency. The optimality of this coding scheme is proved for various special cases.

In this correspondence, we show that solutions to the multiple description coding problem and the broadcast channel coding problem share a common encoding procedure: successive source encoding. We use this connection as the basis for establishing connections between the achievable multiple description rate region and Marton's region for broadcast channels. Specifically, we show that Marton's encoding scheme can be viewed as a multiple description coding procedure. We also explore the dual problem, namely, the relationship between successive channel decoding in multiple access communication and distributed source coding. By illuminating these connections to multiple description, we hope to motivate a solution to what remains a mostly unsolved problem

In critical distortion range, the MSE rate-distortion function of time-discrete stationary Gaussian first-order autoregressive source is equal to that of related time-discrete i.i.d. Gaussian source. For 0cit is necessary to provide additional information of non-negligible positive rate in order to obtain a D-admissible code for the original source via the R-D coding of the innovations process and additional post-processing at the decoder. In this scenario, we provide an explicit expression of additional description rate about the original source to find the degree of suboptimality of sending a lossy version of the innovations process in Gauss-Markov rate-distortion. It is shown that additional description rate is monotone increasing on alpha isin [0,1) and is constant on all critical distortion range

We analyze three sources of timing jitter for (differential) time of arrival estimation for successive spikes arriving at a biological synapse. The dominant source of this jitter is believed to occur during spike generation. Other jitters introduced by propagation and estimation for time-of-arrival are on the order of 10 microseconds. We also obtain and compare several forms of the threshold curve when different assumptions about its form or error properties are imposed

The multiple description (MD) problem has received considerable attention as a model of information transmission over unreliable channels. A general framework for designing efficient MD quantization schemes is proposed in this paper. We provide a systematic treatment of the El Gamal-Cover (EGC) achievable MD rate-distortion region, and show it can be decomposed into a simplified-EGC (SEGC) region and a superimposed refinement operation. Furthermore, any point in the SEGC region can be achieved via a successive quantization scheme along with quantization splitting. For the quadratic Gaussian case, the proposed scheme has an intrinsic connection with the Gram-Schmidt orthogonalization, which implies that the whole Gaussian MD rate-distortion region is achievable with a sequential dithered lattice-based quantization scheme as the dimension of the (optimal) lattice quantizers becomes large. Moreover, this scheme is shown to be universal for all independent and identically distributed (i.i.d.) smooth sources with performance no worse than that for an i.i.d. Gaussian source with the same variance and asymptotically optimal at high resolution. A class of MD scalar quantizers in the proposed general framework is also constructed and is illustrated geometrically; the performance is analyzed in the high-resolution regime, which exhibits a noticeable improvement over the existing MD scalar quantization schemes

We show that for every$n ≫ 2$the standard$ n$th-order approximation$R_n(D)$, to the rate-distortion function of the binary-symmetric Markov source (BSMS) is not successively refineable under the Hamming distortion measure in an open interval of the form$D_n !≪ ! D !≪ !1/2 ! = !D_max $.

It is well known that the Kraft inequality gives a necessary and sufficient condition on the codeword lengths of a zero-error instantaneous code for a single source. However, generalization for two correlated sources is nontrivial. We show that in the Slepian-Wolf configuration, even if one source is known at the decoder, designing a zero-error instantaneous code with given codeword lengths for the other source is NP-complete.

This paper addresses the problem of bit allocation among frames in a predictively encoded video sequence. Finding optimal solutions to this problem potentially requires making an exponential number of calls to the encoder. To better understand the structure of the rate-distortion data output by video encoders, a simple model of a sequentially encoded autoregressive Gaussian random field is theoretically investigated. The rate-distortion data for the model exhibits an additive-separability property, i.e. the rate can be decomposed into a sum of independent functions of single distortion variables. This property implies the near-optimal behavior of a non-backtracking steepest-descent (SD) based bit allocation algorithm. The SD algorithm when applied to video coding produces near-optimal solutions by making a linear number of calls to the encoder. Results are presented for MPEG-2 encoding of standard video sequences.

We propose a new class of universal multiple description lattice quantizers based on the method of quantization splitting. For Gaussian sources and squared error distortion measure, our scheme can achieve the whole multiple description rate-distortion region, as the dimension of the (optimal) lattice quantizers becomes large

In the critical range Oc, the MSE rate-distortion function of a time-discrete stationary autoregressive Gaussian source is equal to that of a related time-discrete i.i.d. Gaussian source. This suggests that perhaps an optimum encoder should compute the related memoryless sequence from the given source sequence with memory and then use a code of rate R(D) to convey the memoryless sequence to the decoder with an MSE of D. In this scenario, the question is, "for D les Dccan a D-admissible code for the original source be obtained via the R-D coding of the innovations process and additional post-processing at the decoder without having to provide any additional information of positive rate?" We show that the answer of this question often is "No"

In this paper, we propose guided broadcast algorithms (GB) - a family of distributed broadcast algorithms for wireless sensor networks (WSNs). GB is based on the recently proposed self-organizing redundancy cellular architecture (SoRCA) for WSNs. It utilizes spatial diversity to cover the sensor nodes in the WSN for a tunable number of times to ensure that at least n portion, a parameter specified by QoS-requirements, of nodes will receive the broadcast message (BM), instead of striving for a 100% delivery ratio which can be costly and unnecessary in some WSN applications. Specifically, the coverage assurance algorithm (CAA) in the GB family ensures that, in the ideal scenario, all nodes in the WSN receive any BM with probability that is at least n; the propagation assurance algorithm (PAA) is invoked to circumvent obstacles and to ensure that BMs propagate through the entire WSN. Additionally, the load balancing and equal exposure scheme (LBEE) is proposed to balance broadcast energy cost. Our performance evaluations show that the proposed schemes possess several nice characteristics that fit well for many applications of WSNs

Due to constraints inherent in RF systems, it is commonly agreed that collision detection is not feasible for CSMA-based wireless networks. However, by applying ideas from the busy-tone solution for hidden terminals and engineering together existing solutions for RF communications, we devise a simple method to reliably detect collisions for the wireless channel. We investigate the throughput gain delivered by CSMA/CD and its cross-layer designed version for multipacket-reception capable physical layers. We show that collision detection can help the system operate closer to its channel capacity. Our novel performance-improving protocols can be applied as beneficial extensions to the IEEE 802.11 wireless LAN standards

We propose self-organizing redundancy-cellular architecture (SoRCA) - a cell-based architecture for wireless sensor networks (WSN). SoRCA conserves energy by significantly reducing redundant data admitted to the network. It is scalable, robust and guarantees coverage. At a cost of extra energy, it can supply adjustable resolution. SoRCA also significantly simplifies the network models and may serve as a framework for mathematical analysis and simulation of WSNs. A formula for network lifetime is derived for location-based SoRCA and is verified by simulations. In addition, a scheme for extending network lifetime is proposed. We also evaluate various partitions from practical perspectives and show that hexagonal partitions are best for the class of cell-based WSNs.

We consider a class of finite-state Markov channels with feedback. We first introduce a simplified equivalent channel model, and then construct the optimal stationary and nonstationary input processes that maximize the long-term directed mutual information. Furthermore, we give a sufficient condition under which the channel's Shannon capacity can be achieved by a stationary input process. The corresponding converse coding theorem and direct coding theorem are proved.

A distributed sensor network in which several observations are communicated to the fusion center using limited transmission rate is considered in this paper. The observations must be separately coded and introduces a class of robust distributed coding schemes, which flexibly trade off between system robustness and compression efficiency.

The finite battery power in wireless portable computing devices is a motivating factor for developing energy efficient wireless network technologies. This paper investigates energy efficiency, relating it to throughput and packet delay for both non-persistent and p-persistent CSMA, two protocols popularly applied in current wireless networks; for example, the widely adopted IEEE 802.11 WLAN standards are based on p-persistent CSMA. For high message generation by the members of a finite population, we find that non-persistent CSMA has a markedly higher energy efficiency than p-persistent CSMA for all network configurations, though the latter attains a moderately lower packet delay. We also show that when non-persistent CSMA is optimized for energy efficiency, throughput and delay are impacted negatively, whereas p-persistent CSMA can effectively optimize all three with the same network settings. Our results help illuminate the suitability of each CSMA scheme for various wireless environments and applications.

We consider a distributed sensor network in which several observations are communicated to the fusion center using limited transmission rate. The observation must be separately encoded so that the target can be estimated with minimum average distortion. We address the problem from an information theoretic perspective and establish the inner and outer bound of the admissible rate-distortion region. We derive an upper bound on the sum-rate distortion function and its corresponding rate allocation schemes by exploiting the contra-polymatroid structure of the achievable rate region. The quadratic Gaussian case is analyzed in detail and the optimal rate allocation schemes in the achievable rate region are characterized. We show that our upper bound on the sum-rate distortion function is tight for the quadratic Gaussian CEO problem in the case of same signal-to-noise ratios at the sensors.

We consider a hybrid selection/maximal-ratio combining (HS/MRC) diversity system and assume independent Nakagami fading on the diversity branches with unequal fading parameters and unequal signal-to-noise ratios (SNR's). We use the virtual branch technique and two series expressions for the characteristic function (CF) of the sum of independent gamma random variables to derive closed-form expressions for CF, the probability density function (PDF), the mean, and the variance of the instantaneous combiner output SNR. We also obtain closed-form expressions for the outage probability, the channel capacity under different transmission policies, and the average symbol error probability (SEP) for a general class of M-ary modulation schemes (including MPSK, MQAM, BFSK, and MSK) with coherent detection. Our approach provides a canonical structure for the closed-form expressions, which are the closed-form expressions for a single-branch system in different Nakagami fading environments.

In this paper, we provide a unified analysis of average symbol error probability (SEP) for a diversity system over generalized gamma fading channels, which is a generalization of Rayleigh, Nakagami, and Ricean fading channels. We consider independent generalized gamma fading on the diversity branches and derive different closed-form expressions of the average SEP for a general class of M-ary modulation schemes (including MPSK, MQAM, BFSK, and MSK) with maximal-ratio combining (MRC) and for M-ary orthogonal FSK with postdetection equal-gain combining (EGC). The results apply to the situations where some branches are Nakagami faded and the others are Ricean faded. Furthermore, the results are applied to obtain closed-form expressions of the average SEP for the cases of arbitrarily correlated and not necessarily identically distributed Nakagami and Ricean faded branches with the help of virtual branch technique by Win et al. Our approach provides a canonical structure for the average SEP as a weighted sum of elementary closed-form expressions, which are the closed-form expressions for the average SEP of a diversity system in independent and identically distributed (i.i.d.) Nakagami fading environments.

We present an integrated system with structural Gaussian mixture models (SGMMs) and a neural network for purposes of achieving both computational efficiency and high accuracy in text-independent speaker verification. A structural background model (SBM) is constructed first by hierarchically clustering all Gaussian mixture components in a universal background model (UBM). In this way the acoustic space is partitioned into multiple regions in different levels of resolution. For each target speaker, a SGMM can be generated through multilevel maximum a posteriori (MAP) adaptation from the SBM. During test, only a small subset of Gaussian mixture components are scored for each feature vector in order to reduce the computational cost significantly. Furthermore, the scores obtained in different layers of the tree-structured models are combined via a neural network for final decision. Different configurations are compared in the experiments conducted on the telephony speech data used in the NIST speaker verification evaluation. The experimental results show that computational reduction by a factor of 17 can be achieved with 5% relative reduction in equal error rate (EER) compared with the baseline. The SGMM-SBM also shows some advantages over the recently proposed hash GMM, including higher speed and better verification performance.

We adapt methods originally developed in information and coding theory to solve some testing problems. The efficiency of two-stage pool testing of n items is characterized by the minimum expected number E(n, p) of tests for the Bernoulli p-scheme, where the minimum is taken over a matrix that specifies the tests that constitute the first stage. An information-theoretic bound implies that the natural desire to achieve E(n, p) = o(n) as n /spl rarr/ /spl infin/ can be satisfied only if p(n) /spl rarr/ 0. Using random selection and linear programming, we bound some parameters of binary matrices, thereby determining up to positive constants how the asymptotic behavior of E(n, p) as n /spl rarr/ /spl infin/ depends on the manner in which p(n) /spl rarr/ 0. In particular, it is shown that for p(n) = n/sup -/spl beta/+o(1)/, where 0 < /spl beta/ < 1, the asymptotic efficiency of two-stage procedures cannot be improved upon by generalizing to the class of all multistage adaptive testing algorithms.

We formulate quantum rate-distortion theory in the most general setting where classical side information is included in the tradeoff. Using a natural distortion measure based on entanglement fidelity and specializing to the case of an unrestricted classical side channel, we find the exact quantum rate-distortion function for a source of isotropic qubits. An upper bound we believe to be exact is found in the case of biased sources. We establish that in this scenario optimal rate-distortion codes produce no entropy exchange with the environment of any individual qubit.

A multiple mixture segmental hidden Markov model (MMSHMM) is presented. This model is extended from the linear probabilistic-trajectory segmental HMM. Each segment is characterized by a linear trajectory with slope and mid-point parameters, and also the residual error covariances around the trajectory, so that both extra-segmental and intra-segmental variation are represented. Instead of modeling single distribution for each model parameter as earlier work, we use multiple mixture components for model parameters to represent the variability due to the variation within each speaker and also the differences between speakers. This model is evaluated on two applications. One is a phonetic classification task with TIMIT corpus, which shows that MMSHMM has advantages over conventional HMM. Another one is a speaker-independent keyword spotting task with the Road Rally database. By rescoring putative events hypothesized by a primary HMM keyword spotter, the experiments show that the performance is improved through distinguishing true hits from false alarms.

Given an achievable quadruple (R/sub 1/, R/sub 2/, D/sub 1/, D/sub 2/) for progressive transmission, the rate loss at step i is defined as L/sub i/=R/sub i/-R(D/sub i/). Let D/sub 1/ and D/sub 2/ be any two desired distortion levels (D/sub 2/

We study a generalization of the successive refinement coding problem called the sequential coding of correlated sources. In successive refinement source coding one first describes the given source using a few bits of information, and then subsequently improves the description of the same source when more information is supplied. Sequential coding differs from successive refinement in that the second-stage encoding involves describing a correlated source as opposed to improving the description of the same source. We introduce the notion of a coupled fidelity criterion to quantify perceived distortion in certain applications of sequential coding. We characterize the achievable rate region for this source coding problem and show that the rate region reduces to the successive refinement rate region when the two sources are the same. Then we consider the specific case of a pair of correlated Gaussian sources as an example. We give an explicit characterization that reveals an interesting generalization of a property of successive refinement of a single Gaussian source.

Designing a videocodec involves a four-way tradeoff among computational complexity, data rate, picture quality, and latency. Rapid advancement in very large-scale integration technology has provided CPUs with enough power to accommodate a software-only videocodec. Accordingly, computational complexity has resurfaced as a major element in this tradeoff. With a view toward significantly reducing computational complexity relative to standards-based videocodecs, we introduce a pixelwise conditional differential replenishment scheme to compress video via perception-sensitive decomposition of difference frames into a facsimile map and an intensity vector. Our schemes, which apply techniques from facsimile, are transform free. Some of them also involve no motion compensation and hence are completely free of block-based artifacts and particularly computationally economical. The fusion of our facsimile-based video-coding schemes and spatio-temporal perceptual-coding techniques facilitates powerful software-only video conferencing on today's medium- and highend personal computers. Indeed, assuming that a frame-capture driver has been provided, our motion-compensation-free approach has yielded a software-only, full-duplex, full-color videoconferencing system that conveys high-quality, CIF/Q-NTSC-sized video at 30 frames per second on 200-MHz Pentium PCs sending less than 300 Kbps in each direction. We also present new spatio-temporal compression techniques for perceptual coding of video. These techniques, motivated by the classical psychological experiments that led to formulation of the Weber-Fechner law, allow videocodec systems to capitalize on properties of the human visual system. Some of our spatiotemporal perceptual techniques not only apply to our proprietary pixelwise conditional differential replenishment schemes that we describe for video conferencing but also can readily be incorporated into today's popular video standards.

We present a continuous dual of multiterminal source encoding with one distortion criterion (the "Berger-Yeung (1989) problem"). A continuous source X is encoded with "high resolution" (D/sub x//spl rarr/0), with the aid of a "helper," i.e., a correlated discrete or continuous source Y, that is encoded separately subject to some arbitrary distortion criterion D/sub y/. We find the asymptotic form of the set of achievable coding rates R(D/sub x/, D/sub y/) of the X- and Y-encoders as D/sub x//spl rarr/0. Two extreme cases of our result provide high-resolution interpretations to the classical work of Wyner (1975, 1978), Ahlswede (1975), Korner (1975), and Ziv (1976) on source coding with side information.

We consider separate encoding and joint decoding of correlated continuous information sources, subject to a difference distortion measure. We first derive a multiterminal extension of the Shannon lower bound for the rate region. Then we show that this Shannon outer bound is asymptotically tight for small distortions. These results imply that the loss in the sum of the coding rates due to the separation of the encoders vanishes in the limit of high resolution. Furthermore, lattice quantizers followed by Slepian-Wolf lossless encoding are asymptotically optimal. We also investigate the high-resolution rate region in the remote coding case, where the encoders observe only noisy versions of the sources. For the quadratic Gaussian case, we establish a separation result to the effect that multiterminal coding aimed at reconstructing the noisy sources subject to the rate constraints, followed by estimation of the remote sources from these reconstructions, is optimal under certain regularity conditions on the structure of the coding scheme.

Summary form only given. Huffman coding has been applied in many disciplines including text compression, still image compression, and video compression. In the case of video, several software-only codecs have been developed aiming at real-time performance. However, they fall well short of achieving full screen, high-quality, and full-motion. A key bottleneck in such software implementations occurs during writing and reading of the Huffman-coded bit stream. The reason is that the minimum unit for software operations is a byte rather than a bit. Therefore, the need to read/write data in bits necessitates devising means to bridge the bits-to-bytes and and bytes-to-bits gaps efficiently. We introduce new tables for software-only Huffman coding that enable us to write/read data in M-bit units, thereby virtually eliminating the need for inefficient software simulation of bit-based operations. We present an offset-based Huffman encoding table containing information for each number of bits by which the length of a Huffman word is offset from an integral number of bytes. The number of rows in the offset-based Huffman encoding table is M times that of the general Huffman table. The offset-based Huffman encoding table eliminates most of the bit operations, but it still requires some bit-based operations to update the offset and the condition of the current unit. In order to avoid bit operations entirely, we extend the offset-based table into a byte-based table by associating a unique subtable with each offset and unit condition. A byte-based Huffman decoding table has also been studied.

Lossy coding of speech, high-quality audio, still images, and video is commonplace today. However, in 1948, few lossy compression systems were in service. Shannon introduced and developed the theory of source coding with a fidelity criterion, also called rate-distortion theory. For the first 25 years of its existence, rate-distortion theory had relatively little impact on the methods and systems actually used to compress real sources. Today, however, rate-distortion theoretic concepts are an important component of many lossy compression techniques and standards. We chronicle the development of rate-distortion theory and provide an overview of its influence on the practice of lossy source coding.

The critical distortion d/sub c/ of the Potts models on a number of lattices is shown to be related to the radius of convergence R of Mayer's series by d/sub c/=(q-1)R/(1+R). By using the matrix representation of Mayer's series, a recursive approach is applied to estimate R, and hence d/sub c/ for Ising models for which q=2.

We show that information refinement fails for a continuous alphabet source whose input distribution is the symmetric mixture of normal densities with means -/spl mu/ and /spl mu/ and common variance /spl sigma//sup 2/.

A firm's CEO employs a team of L agents who observe independently corrupted versions of a data sequence {X(t)}/sub t=1//sup /spl infin//. Let R be the total data rate at which the agents may communicate information about their observations to the CEO. The agents are not allowed to convene. Berger, Zhang and Viswanathan (see ibid., vol.42, no.5, p.887-902, 1996) determined the asymptotic behavior of the minimal error frequency in the limit as L and R tend to infinity for the case in which the source and observations are discrete and memoryless. We consider the same multiterminal source coding problem when {X(t)}/sub t=1//sup /spl infin// is independent and identically distributed (i.i.d.) Gaussian random variable corrupted by independent Gaussian noise. We study, under quadratic distortion, the rate-distortion tradeoff in the limit as L and R tend to infinity. As in the discrete case, there is a significant loss between the cases when the agents are allowed to convene and when they are not. As L/spl rarr//spl infin/, if the agents may pool their data before communicating with the CEO, the distortion decays exponentially with the total rate R; this corresponds to the distortion-rate function for an i.i.d. Gaussian source. However, for the case in which they are not permitted to convene, we establish that the distortion decays asymptotically only as R-l.

Corresponding to any lossless codeword length function l, three universal lossy data compression schemes are presented: one is with a fixed rate, another is with a fixed distortion, and a third is with a fixed slope. The former two universal lossy data compression schemes are the generalization of Yang-Kieffer's (see ibid., vol.42, no.1, p.239-45, 1995) results to the general case of any lossless codeword length function l, whereas the third is new. In the case of fixed-slope /spl lambda/>0, our universal lossy data compression scheme works as follows: for any source sequence x/sup n/ of length n, the encoder first searches for a reproduction sequence y/sup n/ of length n which minimizes a cost function n/sup -1/l(y/sup n/)+/spl lambda//spl rho//sub n/(x/sup n/, y/sup n/) over all reproduction sequences of length n, and then encodes x/sup n/ into the binary codeword of length l(y/sup n/) associated with y/sup n/ via the lossless codeword length function l, where /spl rho//sub n/(x/sup n/, y/sup n/) is the distortion per sample between x/sup n/ and y/sup n/. Under some mild assumptions on the lossless codeword length function l, it is shown that when this fixed-slope data compression scheme is applied to encode a stationary, ergodic source, the resulting encoding rate per sample and the distortion per sample converge with probability one to R/sub /spl lambda// and D/sub /spl lambda//, respectively, where (D/sub /spl lambda//, R/sub /spl lambda//) is the point on the rate distortion curve at which the slope of the rate distortion function is -/spl lambda/. This result holds particularly for the arithmetic codeword length function and Lempel-Ziv codeword length function. The main advantage of this fixed-slope universal lossy data compression scheme over the fixed-rate (fixed-distortion) universal lossy data compression scheme lies in the fact that it converts the encoding problem to a search problem through a trellis and then permits one to use some sequential search algorithms to implement it. Simulation results show that this fixed-slope universal lossy data compression scheme, combined with a suitable search algorithm, is promising.

We have implemented approaches to compressing and decompressing a sequence of head-and-shoulders images that trade off the data rate, picture quality, computational complexity and latency. All these approaches are transform-free and pixel-based; some of them also involve no motion compensation and hence are free of block-based artifacts. We compare the magnitude of the intensity of each pixel site in the difference frame to a threshold. If the intensity at a pixel site is above the threshold, that pixel is a survivor; otherwise, that pixel is a casualty. We zero the intensity at each casualty pixel and leave the intensity intact at each surviving pixel. A bi-level frame is formed to represent the location map of the survivors and casualties. We gather the intensities at the surviving pixels into an intensity vector. The zeroed difference frame is therefore decomposed into a bi-level frame and an intensity vector. We modified the Group 3, Group 4 or JBIG facsimile standards to compress the bi-level frame and can achieve further compression by applying scalar quantization to each element of the intensity vector. Forming the difference frames by direct subtraction of the previous decompressed frame from the current input frame permits software-only realization of the compressor and decompressor on today's home and office computers for large (CIF or Q-NTSC) full-color formats at 30 frames per second for head-and-shoulders video at under 1.0 Mbps with PSNR>38 dB, assuming provision has been made for A/D converted camera output to be pipelined into the computer CPU in real time.

Online dynamic signature verification systems were designed and tested. A database of more than 10,000 signatures in (x(t), y(t))-form was acquired using a graphics tablet. We extracted a 42-parameter feature set at first, and advanced to a set of 49 normalized features that tolerate inconsistencies in genuine signatures while retaining the power to discriminate against forgeries. We studied algorithms for selecting and perhaps orthogonalizing features in accordance with the availability of training data and the level of system complexity. For decision making we studied several classifiers types. A modified version of our majority classifier yielded 2.5% equal error rate and, more importantly, an asymptotic performance of 7% false acceptance rate at zero false rejection rate, was robust to the speed of genuine signatures, and used only 15 parameter features.

We consider a new problem in multiterminal source coding motivated by the following decentralized communication/estimation task. A firm's Chief Executive Officer (CEO) is interested in the data sequence {X(t)}/sub t=1//sup /spl infin// which cannot be observed directly, perhaps because it represents tactical decisions by a competing firm. The CEO deploys a team of L agents who observe independently corrupted versions of {X(t)}/sub t=1//sup /spl infin//. Because {X(t)} is only one among many pressing matters to which the CEO must attend, the combined data rate at which the agents may communicate information about their observations to the CEO is limited to, say, R bits per second. If the agents were permitted to confer and pool their data, then in the limit as L/spl rarr//spl infin/ they usually would be able to smooth out their independent observation noises entirely. Then they could use their R bits per second to provide the CEO with a representation of {X(t)} with fidelity D(R), where D(/spl middot/) is the distortion-rate function of {X(t)}. In particular, with such data pooling D can be made arbitrarily small if R exceeds the entropy rate H of {X(t)}. Suppose, however, that the agents are not permitted to convene, Agent i having to send data based solely on his own noisy observations {Y/sub i/(t)}. We show that then there does not exist a finite value of R for which even infinitely many agents can make D arbitrarily small. Furthermore, in this isolated-agents case we determine the asymptotic behavior of the minimal error frequency in the limit as L and then R tend to infinity.

Multiple description source coding concerns situations in which the transmission of the source information is distributed over two data streams at rates R/sub 1/ and R/sub 2/, respectively. When both data streams are received, the decoder uses the combined data at rate R/sub 1/+R/sub 2/ to reconstruct the source information with average distortion d/sub 0/. If a communication breakdown prevents one of the data streams from reaching the receiver, the decoder has to base its reconstruction solely on the available data at rate either R/sub 1/ or R/sub 2/. This results in a higher distortion of either d/sub 1/ or d/sub 2/, respectively. The region /spl Rscr/ of all achievable quintuples (R/sub 1/, R/sub 2/, d/sub 0/, d/sub 1/, d/sub 2/) has been determined in the so-called "no excess rate" sum case defined by imposing the requirement R/sub 1/+R/sub 2/=R(d/sub 0/), where R(/spl middot/) is the rate-distortion function of the source. The case with excess rate sum, characterized by R/sub 1/+R/sub 2/>R(d/sub 0/), is challenging. We study in this paper a special case of it in which the requirements R/sub t/=R(d/sub t/), t=1, 2, are imposed; we refer to this as the "no excess marginal rate" case. The lower and upper bounds on d/sub 0/ we obtain are separated by only a tiny gap when evaluated for a binary equiprobable source and the Hamming distortion measure.>

Online dynamic signature verification systems were designed and tested. Data acquisition consisted of compiling a database of more than ten thousand signatures in (x(t), y(t))-form using a graphics tablet. For feature extraction we started with a 42-parameter feature set and advanced to a set of 49 normalized features. The normalized features tolerate inconsistencies in genuine signatures while retaining the power to discriminate against forgeries. For decision making we studied several classifiers types. Specifically, a modified versions of our so-called majority classifier yielded 2.5% equal error rate and, more importantly, an asymptotic performance of 7% false acceptance rate at zero false rejection rate using only 15 parameter features.

A Manhattan street network (MSN) is a regular, two-connected local area network. It has multiple paths between each pair of nodes that improve the reliability and throughput relative to single-loop networks. The authors evaluate reliability for accurate and approximate MSN models. Via both simulation and theoretical analysis, they show that there is little difference between the exact and approximate models. Because it is not practical to calculate the reliability for either model for large networks, simple upper and lower bounds are developed. They also determine the availability of MSNs for several repair disciplines for servicing failed links. Approximate Markov chain models for two different smart repair discipline models are analyzed. It is shown that the smart repair disciplines provide significant improvements in availability over the simple FCFS discipline, and simulations with confidence intervals are provided.>

It was shown by C.M. Newman and G.A. Baker (1991) that the critical distortion d/sub c/ of the Ising model on z/sup k/ is related to the radius of convergence R of the classical Mayer series by d/sub c/=R/(1+R). An approach from statistical mechanics to estimate R as well as d/sub c/ by using the matrix representation of Mayer series is found.>

Simple binary symmetric one- and two-dimensional channel systems called Ising channels are investigated. The one-dimensional version is a certain binary finite-state channel with input intersymbol interference. Its zero-error capacity is determined together with lower and upper bounds to its Shannon capacity. For the two-dimensional channel system, a lower bound is obtained for the zero-error capacity, and an efficient zero-error coding scheme is developed.>

The link between epsilon -entropy for binary random fields and the Lee-Yang theorem in statistical mechanics makes it possible to prove the existence of positive critical distortion for most binary random fields with pair interactions and some with many body interactions. Lower bounds for critical distortion of random fields on two-dimensional (2-D) lattices have been obtained. In particular, the new lower bounds for some 2-D Ising models improve upon previously known bounds.>

The existence of the entropy rate of shift-invariant random fields on binary trees is proven. Alternative representations of and bounds for the entropy rate and surface entropy rate are obtained in terms of conditional entropy. Particular emphasis is placed on Markov chain fields on trees; explicit results are obtained, some of which extend to a more complicated class of tree models.>

The problem of finding a binary prefix code of minimum average codeword length for a given finite probability distribution subject to the requirement that each codeword must end with a 1 is considered. Lower and upper bounds to the performance of the optimum code are derived; the lower bound is tight for certain probability distributions. An algorithm that generates an optimum code for any given distribution is described.>

The authors unify earlier investigations concerning the encoding of two correlated sources (X/sub k/), (Y/sub k/) by means of separate encoders. Decoding is done by a single decoder which receives the outputs from both encoders. The reconstruction of (X/sub k/) is required to be perfect in the usual Shannon sense. The authors determine the admissible rate region R (D), where D is the distortion of the reconstruction of (Y/sub k/). The binary Hamming case is investigated explicitly.>

When separate encoders are assigned to each of two correlated sources, it is in general true that the rate sum required is less when decoding is done by a single decoder than when separate decoders are used. However, if either encoder breaks down, system performance ordinarily degrades severely in the single-decoder case when one tries to recover the sources based solely on the output of the remaining encoder. The authors determine the admissible rate region for this situation, which is related to the multiple description problem. Some of the implications of the general result are unintuitive.>

Some results from classical estimation theory are extended to the case in which data must be communicated from several places where observations are made to the place where the estimate is generated. Particular emphasis is placed on determining how the variance of an unbiased estimator depends on the communication rates. Explicit result are given for Gaussian sources.>

An encoder whose input is a binary equiprobable memoryless source produces one output of rateR_{1}and another of rateR_{2}. LetD_{1}, D_{2}, and D_{0}, respectively, denote the average error frequencies with which the source data can be reproduced on the basis of the encoder output of rateR_{l}only, the encoder output of rateR_{2}only, and both encoder outputs. The two-descriptions problem is to determine the regionRof all quintuples(R_{1}, R_{2}, D_{1}, D_{2}, D_{0})that are achievable in thc usual Shannon sense. LetR(D)=1+D \log_{2} D+(1-D) \log_{2}(1-D)denote the error frequency rate-distortion function of the source. The "no excess rate case" prevails whenR_{1} + R_{2} = R(D_{0}), and the "excess rate case" whenR_{1} + R_{2} > R(D_{0}). Denote the section ofRat(R_{1}, R_{2}, D_{0})byD(R_{1} R_{2}, D_{0}) =\{(D_{1},D_{2}): (R_{1}, R_{2}, D_{1},D_{2},D_{0}) \in R}. In the no excess rate case we show that a portion of the boundary ofD(R_{1}, R_{2}, D_{0})coincides with the curve(\frac{1}{2} + D_{1}-2D_{0})(\frac_{1}_{2} + D_{2}-2D_{0})= \frac{1}{2}(1-2D_{0})^{2}. This curve is an extension of Witsenhausen's hyperbola bound to the caseD_{0} > 0. It follows that the projection ofRonto the(D_{1}, D_{2})-plane at fixedD_{0}consists of allD_{1} \geq D_{0}andD_{2} \geq D_{0}that lie on or above this hyperbola. In the excess rate case we show by counterexample that the achievable region of El Gamal and Cover is not tight.

Families of zero-error codes for the real binary adder channel with feedback that achieve high rate pairs are introduced. Two families of zero-error block codes are given for the case in which only one of the two senders receives feedback about the channel output. In the first of these families, the uninformed sender transmits at a rate of nearly one bit per symbol and the informed sender transmits slightly less that1/2bit per symbol. The second family is designed for the case in which the informed sender sends at or near one bit per symbol and the uninformed one sends nearly1/2bit per symbol. A family of zero-error codes is introduced, based on the Fibonacci recursion; these codes are readily implemented by means of a simple square-dividing strategy. The Fibonacci codes achieveR_{1}=R_{2}=\log_{2} [(1 + \sqrt{5})/2]in the limit of large block length. Time-sharing between members of these three code families is used to obtain an achievable rate region, or inner bound, to the zero-error capacity region for block coding. For the case in which the feedback is available to both senders, a variant of the Fibonacci difference equation is used to generate zero-error block codes with slightly higher asymptotic rateR_{1}=R_{2}=0.717.

We derive upper and lower bounds to the curve of expected delay versus throughput for the delay-enhanced version of the celebrated 0.487 multiple access contention resolution algorithm. The key to the derivation is a technique for generating upper and lower bounds to monotonic functions of the transmission lag via corresponding bounds on the kernel of the integral equation for the distribution of said lag. The separation between the upper and lower bounds is small, and the results agree well with simulations.

Shannon's two-way channel problem has attracted the attention of information theorists for many years. In a classic paper Shannon gave both an outer and an inner bound to the capacity region of the two-way channel. Schalkwijk recently obtained an improvement to the inner bound for the Blackwell multiplying channel (BMC). We present the first improvements on Shannon's outer bound. Calculation shows that our results are close to optimum when applied to the BMC.

The authors underbound the critical distortion below which the rate-distortion function of a Markov chain equals its Shannon lower bound. The bound is tight in all cases in which the exact answer is currently known.

The problem is considered of encoding a discrete memoryless source when correlated side information may or may not be available to the decoder. It is assumed that the side information is not available to the encoder. The rate-distortion functionR (D_{l}, D_{2})is determined whereD_{1}is the distortion achieved with side information andD_{2}is the distortion achieved without it. A generalization is made to the case ofmdecoders, each of which is privy to its own side information. An appropriately definedD-admissible rate for this general case is shown to equalR(D)when the side information sources satisfy a specified degradedness condition. Explicit results are obtained in the quadratic Gaussian case and in the binary Hamming case.

The intelligent design of a random multiple-access communication system involves analyzing the tradeoffs among throughput rate, transmission delay, and stability subject to additional restrictions imposed by distributed processing requirements. Interval-searching contention resolution algorithms have been found to achieve high throughput, and simulations have shown that they also possess short average delay. A general approach to the delay analysis of interval-searching contention resolution is proposed based on solving an integral equation for the distribution of a quantity called the transmission lag. For a certain multibit feedback algorithm, this analytical technique leads to exact determination of the throughput-delay characteristic. For the celebrated "0.487" algorithm, the method yields upper and lower bounds to the curve of expected delay versus throughput that are in close agreement with simulation results.

We study the application of group testing to the design of efficient algorithms for random multiple-access communication systems. Both direct transmission and reservation systems are considered for various types of channel feedback. We propose and analyze algorithms based on conventional and generalized group testing techniques. The proposed algorithms outperform TDMA and algorithms based on binary tree search and possess certain optimality properties.

Communication over a random multiple-access, collision-type, time-slotted, packet-switched channel with binary feedback is considered for a Poisson infinite-user model. Three different types of binary feedback are introduced and confusion resolution algorithms (CRA) are discussed for each. The CRA proposed for the feedback that tells only whether or not there was a collision in the previous slot achieves a throughput of0.442. The CRA proposed for the feedback that tells whether or not the previous slot was empty achieves a throughput of0.279.

A memoryless binary equiprobable source produces one letter per second. Two people each are provided separately with private information about the source data at a rate of1/2bit per second. Suppose that by pooling their information they can produce a long-mn reconstruction of the source output that has arbitrarily small error frequency. We prove that then the least common asymptotic error frequency d that each can achieve without the other's help is(\sqrt{2}-1)/2=0.207. Since it had been shown previously that0.200 \leq d \leq 0.207, our result closes the so-called "007 gap." New analytical techniques introduced to effect the proof are of broader significance in multiuser information theory.

Amplitude quantization and permutation encoding are two approaches to efficient digitization of analog data. It has been proven that they are equivalent in the sense that their optimum rate versus distortion performances are identical. Reviews of the aforementioned results and of work performed in the interim by several investigators are presented. Equations which must be satisfied by the thresholds of the minimum entropy quantizer that achieves a prescribed meanrth power distortion are derived, and an iterative procedure for solving them is developed. It is shown that these equations often have many families of solutions. In the case of the Laplacian distribution, for which we had previously shown that quantizers with uniformly spaced thresholds satisfy the equations whenr=2, other families of solutions with nonuniform spacing are exhibited. What had appeared to be a discrepancy between the performances of optimum permutation codes and minimum entropy quantizers is resolved by the resulting optimum quantizers, which span all entropy rates from zero to infinity.

We resolve some open problems concerning the encoding of a pair of correlated sources with respect to a fidelity criterion. Two encoders are used. One encoder observes only the output of the first source, while the other is supplied both with the second source output and with partial information about the first source at some predetermined rate. A general coding theorem is proved which established that{\cal S} \ast, a certain region defined in terms of "single-letter" information theoretic quantities, is an inner bound to the region of all attainable vectors of rates and distortions. For certain cases of interest the converse is proved, too, thereby establishing the rate-distortion region for these cases.

An upper bound on the rate distortion function is obtained for source coding with partial side information at the decoder. Previous results were for complete side information, i.e. full knowledge ofY_{n}. below. A diagram given in the paper helps to describe the problem. The bound is given in

A new upper houndR_{u}(D)and lower houndR_{\ell}(D)are developed for the rate-distortion function of a binary symmetric Markov source with respect to the frequency of error criterion. Both hounds are explicit in the sense that they do not depend on a blocklength parameter. In the intervalD_{c} < D < 1/2 = D_{max}, whereD_{c}is Gray's critical value of distortion,R_{u}(D)is convex downward and possesses the correct value and the correct slope at both endpoints. The new lower boundR_{ell}(D)diverges from the Shannon lower bound at the same value of distortion as does the second-order Wyner-Ziv lower bound. However, it remains strictly positive for allD \leq 1/2and therefore eventually rises above all the Wyner-Ziv lower bounds asDapproaches1/2. Some generalizations suggested by the analytical and geometrical techniques employed to deriveR_{u}(D)andR_{ell}(D)are discussed.

Sliding block codes are an intriguing alternative to the block codes used in the development of classical information theory. The fundamental analytical problem associated with the use of a sliding block code (SBC) for source encoding with respect to a fidelity criterion is that of determining the entropy of the coder output. Several methods of calculating and of bounding the output entropy of an SBC are presented. The local and global behaviors of a well-designed SBC also are discussed. The so-called "101-coder," which eliminates all the isolated zeros from a binary input, plays a central role. It not only provides a specific example for application of the techniques developed for calculating and bounding the output entropy, but also serves as a medium for obtaining indirect insight into the problem of characterizing a good SBC. An easily implementable SBC subclass is introduced in which the outputs can be calculated by simple logic circuitry. The study of this subclass is shown to be closely linked with the theory of algebraic group codes.

Tree encoding and sequential decoding are considered for noisy channels that respond a random number of times to each input. Such channels appear in mathematical models of certain speech recognition systems. The decoding error probability and the channel capacity are bounded by extension of the methods of Jelinek and Zigangirov to noisy multilevel channels with input-dependent insertions. Certain analytical difficulties peculiar to the channels in question are indicated.

We derive sequences of upper and lower bounds that converge to the capacity of a binary channel in which a one takes twice as long to send as does a zero and may be received either as a one or as a pair of zeros. Such a fission mechanism can occur, for example, in the use of Morse code over a noisy channel. Next we present a sequential decoding algorithm for the channel which is particularly easy to implement. By means of the Perron-Frobenius theorem and an extension of Zigangirov's analysis of sequential decoding, we overbound error probability and thereby again underbound capacity. The resulting lower bound turns out to be within 0.014 nats of the fourteenth-order upper bound to capacity, uniformly in the fission probability. By extending an analytical method due in part to Jelinek, we overbound expected decoding computation and thereby lowerboundR_{comp}.

An extensive study of binary triple-error-correcting codes of primitive lengthn = 2^{m} - 1is reported that results in a complete decoding algorithm whenever the maximum coset weightW_{max}is five. In this regard it is shown thatW_{max} = 5when four dividesm, and strong support is provided for the validity of the conjecture thatW_{max} = 5for allm. The coset weight distribution is determined exactly in some cases and bounded in others.

Random processes that generate information slower than linearly with time are termed information-singular. The study of information-singularity contributes to a more thorough understanding of the mathematical nature of information generation. Specifically, it elucidates the manner in which generation of information by a time series is critically dependent on the detailed behavior of the sample functions of its spectral representation. The main theorem states that any random sequence whose spectral representation has stationary independent increments with no Brownian motion component is information-singular in the mean-squared sense. The concept of information-singularity can be construed as a means for discriminating between deterministic and nondeterministic processes. It is felt that information-singularity fulfills this discriminating function in a physically more satisfying manner than does the classical Hilbert space theory of linear and nonlinear prediction. The desire for a still more satisfying discriminant motivates investigation of the class of random processes that retain their information-singularity even when corrupted by additive noise. In the case of strictly stationary processes, the discussion focuses on the relationship between information-singularity and zero entropy. Lastly, some alternative definitions of information-singularity are considered and several open problems are identified.

Tree codes are known to be capable of performing arbitrarily close to the rate-distortion function for any memoryless source and single-letter fidelity criterion. Tree coding and tree search strategies are investigated for the discrete-time memoryless Gaussian source encoded for a signal-power-to-mean-squared-error ratio of about 30 dB (about 5 binary digits per source output). Also, a theoretical lower bound on average search effort is derived. Two code search strategies (the Viterbi algorithm and the stack algorithm) were simulated in assembly language on a large digital computer. After suitable modifications, both strategies yielded encoding with a signal-to-distortion ratio about 1 dB below the limit set by the rate-distortion function. Although this performance is better than that of any previously known instrumentable scheme, it unfortunately requires search computation of the order ofl0^5machine cycles per source output encoded.

Coding for fidelity criteria, dependent upon the time delay of coding and transmission, is studied from an information-theoretic viewpoint. The results presented here, unlike the conventional Shannon theory, show that the optimum code frequently has finite block length. By extending some rate-distortion theory results, coding theorems and converses are proven. These suggest a procedure for bounding the block length of the code with minimum distortion.

Expressions are obtained for the capacity and error exponents of a channel modeled as a linear dynamic system with additive Gaussian noise. The derivations are based on a procedure for determining the asymptotic distribution of the eigenvalues of a sequence of almost cyclic matrices of matrices.

Amplitude quantization and permutation encoding are two of the many approaches to efficient digitization of analog data. It is shown in this paper that these seemingly different approaches actually are equivalent in the sense that their optimum rate versus distortion performances are identical. Although this equivalence becomes exact only when the quantizer output is perfectly entropy coded and the permutation code block length is infinite, it nonetheless has practical consequences both for quantization and for permutation encoding. In particular, this equivalence permits us to deduce that permutation codes provide a readily implementable block-coding alternative to buffer-instrumented variable-length codes. Moreover, the abundance of methods in the literature for optimizing quantizers with respect to various criteria can be translated directly into algorithms for generating source permutation codes that are optimum for the same purposes. The optimum performance attainable with quantizers (hence, permutation codes) of a fixed entropy rate is explored too. The investigation reveals that quantizers with uniformly spaced thresholds are quasi-optimum with considerable generality, and are truly optimum in the mean-squared sense for data having either an exponential or a Laplacian distribution. An attempt is made to provide some analytical insight into why simple uniform quantization is so good so generally.

Source encoding techniques based on permutation codes are investigated. For a broad class of distortion measures it is shown that optimum encoding of a source permutation code is easy to instrument even for very long block lengths. Also, the nonparametric nature of permutation encoding is well suited to situations involving unknown source statistics. For the squared-error distortion measure a procedure for generating good permutation codes of a given rate and block length is described. The performance of such codes for a memoryless Gaussian source is compared both with the rate-distortion function bound and with the performance of various quantization schemes. The comparison reveals that permutation codes are asymptotically ideal for small rates and perform as well as the best entropy-coded quantizers presently known for intermediate rates. They can be made to compare favorably at high rates, too, provided the coding delay associated with extremely long block lengths is tolerable.

A lower boundR_L (D)is obtained to the rate-distortion functionR(D)of a finite-alphabet stationary source with respect to a context-dependent fidelity criterion. For equiprobable memoryless sources and modular distortion measures,R(D) = R_L (D)for allD. It is conjectured that, for a broad class of finite-alphabet sources and context-dependent fidelity criteria, there exists a critical distortionD_c > 0such thatR(D) = R_L (D)forD \leq D_{c^\cdot}. The case of a binary source and span-2 distortion measure is treated in detail. Among other results a coding theorem is proved that establishes thatR(0) = \log (2/r_g), wherer_gis the golden ratio,(1 + \sqrt{5})/2.

The encoding of a source whose probability distribution varies arbitrarily from letter to letter is considered. The problem is formulated as a two-person statistical game. The exponential rate of growth with block length of the minimum number of codewords needed to achieve a specified fidelity with respect to a single-letter distortion measure is determined. The rate distortion function of a source whose statistics are entirely unknown is obtained as a special case. The dependence of the results on the rules under which the game is played also is studied. The analysis is based on a refinement of the usual random coding argument for sources which sheds new light on the significance of the term that decays at a doubly exponential rate with block length.

An expression is given for the mean-squared-error (MSE) rate distortion curve of a linear finite-memory Gaussian dynamic system; for a range of small MSE, it coincides with that of the excitation noise vector.R(D)curves of non-Gaussian and nonlinear dynamic systems are analyzed, also. The results are applicable to determining information requirements for communication and control systems.

Rate distortion functions are calculated for time discrete and time continuous Wiener processes with respect to the mean squared error criterion. In the time discrete case, we find the interesting result that, for0 \leq D \leq \sigma^2 /4,R(D)for the Wiener process is identical toR(D)for the sequence of zero mean independent normally distributed increments of variance \sigma^2 whose partial sums form the Wiener process. In the time continuous case, we derive the explicit formulaR(D) = 2 \sigma^2 / ( \pi^2 D), where\sigma^2is the variance of the increment daring a one-second interval. The resuitingR(D)curves are compared with the performance of an optimum integrating delta modulation system. Finally, by incorporating a delta modulation scheme in the random coding argument, we prove a source coding theorem that guarantees ourR(D)curves are physically significant for information transmission purposes even though Wiener processes are nonstationary.

Intersymbol interference and additive noise are two common sources of distortion in data transmission systems. For pulse amplitude modulation (PAM) communication links, the combination of transmitter waveform and linear receiver that minimizes the mean-squared error arising from these sources is determined. An extension to include the effects of timing jitter is performed in a companion paper. Performance characteristics of the optimal PAM systems, showing the mean-squared error versus the signal-to-noise ratio, are determined explicitly for several examples. These characteristics are compared both with those of certain suboptimal systems and with the optimal performance theoretically attainable (OPTA), derived by combining Shannon's concepts of the capacity of a channel and the rate distortion function of a source. The optimal PAM systems are seen to perform very close to the OPTA for low signal-to-noise ratios. For high signal-to-noise ratios, however, the mean-squared error of optimal PAM systems decreases as the reciprocal of the signal-to-noise ratio, but the OPTA decreases more rapidly, except for band-limited channels. The performance of PAM systems can be improved at high signal-to-noise ratios by coding techniques. One such technique, called Shannon-Cantor coding, is discussed briefly.

A method is presented for specifying transmitter waveforms and receiver filters for pulse amplitude modulation (PAM) systems which are subject to distortion from additive noise, intersymbol interference, and timing jitter. A criterion of minimum mean-squared error is used. For the case of band-limited transmission, specific procedures are developed for computing optimum transmitters, optimum receivers, and jointly optimum transmitters and receivers. For two special jitter distributions the joint optimization problem is solved without a bandwidth limitation, and the resulting systems are found to be band-limited. In cases of localized timing jitter and high signal-to-noise ratio, we are led to system pulse responses of the form[\sin x/x]^{2}. A nonparametric method of reducing the effects of timing jitter is briefly discussed. In this approach the noise interference is minimized subject to the constraints that the intersymbol interference be zero and that the system pulse response have zero derivative at each nominal sampling point.