General treatment of the problem of coding Shannon, C. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Feb 1953 On page(s): 102- 104 Volume: 1, Issue: 1 ISSN: 0018-9448 Abstract: A typical communication system consists of the following five elements: (1) An information source. This can be considered to be represented mathematically by a suitable stochastic process which chooses one message from a set of possible messages. The rate R of producing information is measured by the entropy per symbol of the process. (2) An encoding or transmitting element. Mathematically this amounts to a transformation applied to the message to produce the signal, i.e., the encoded message. (3) A channel on which the signal is transmitted from transmitter to receiver. During transmission the signal may be perturbed by noise. (4) A receiving and decoding (or demodulating) device which recovers the original message from the received signal. (5) The destination of the information, e.g., the human ear (for telephony) or the eye (for television). The characteristics of the destination may determine the significant elements of the information to be transmitted. For example, with sound transmission, precise recovery of the phases of components is not required because of the insensitivity of the ear to this type of distortion. ----- Significance of information theory to neurophysiology Bates, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Feb 1953 On page(s): 137- 142 Volume: 1, Issue: 1 ISSN: 0018-9448 Abstract: Not Available Index Terms: Not Available ----- Communication theory--Exposition of fundamentals Shannon, C. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Feb 1953 On page(s): 44- 47 Volume: 1, Issue: 1 ISSN: 0018-9448 Abstract: In any branch of applied mathematics, the vague and ambiguous concepts of a physical problem are given a more refined and idealized meaning. In information theory, one of the basic notions is that of the amount of information associated with a given situation. "Information" here, although related to the everyday meaning of the word, should not be confused with it. In everyday usage, information usually implies something about the semantic content of a message. For the purposes of communication theory, the "meaning" of a message is generally irrelevant; what is significant is the difficulty in transmitting the message from one point to another. Index Terms: Not Available ----- The lattice theory of information Shannon, C. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Feb 1953 On page(s): 105- 107 Volume: 1, Issue: 1 ISSN: 0018-9448 Abstract: The word "information" has been given many different meanings by various writers in the general field of information theory. It is likely that at least a number of these will prove sufficiently useful in certain applications to deserve further study and permanent recognition. It is hardly to be expected that a single concept of information would satisfactorily account for the numerous possible applications of this general field. The present note outlines a new approach to information theory which is aimed specifically at the analysis of certain communication problems in which there exist a number of information sources simultaneously in operation. A typical example is that of a simple communication channel with a feedback path from the receiving point to the transmitting point. The problem is to make use of the feedback information for improving forward transmission, and to determine the forward channel capacity when the best possible use is made of this feedback information. Another more general problem is that of a communication system consisting of a large number of transmitting and receiving points with some type of interconnection network between the various points. The problem here is to formulate the best systems design whereby, in some sense, the best overall use of the available facilities is made. While the analysis sketched here has not yet proceeded to the point or a complete solution of these problems, partial answers have been found and it is believed that a complete solution may be possible. Index Terms: Not Available ----- Discussion on Dr. J.A.V. Bate's paper 'Significance of Information Theory in Neurophysiology' Bates, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Feb 1953 On page(s): 192- 192 Volume: 1, Issue: 1 ISSN: 0018-9448 Abstract: Not Available Index Terms: Not Available ----- Glossary of physiological terms Bates, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Feb 1953 On page(s): 5- 8 Volume: 1, Issue: 1 ISSN: 0018-9448 Abstract: Not Available Index Terms: Not Available ----- Discussion on Dr. Shannon's papers Shannon, C. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Feb 1953 On page(s): 169- 174 Volume: 1, Issue: 1 ISSN: 0018-9448 Abstract: Not Available Index Terms: Not Available ----- The problem of the information which the brain receives from the eye (Abstr.) Rushton, W. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Feb 1953 On page(s): 128- 129 Volume: 1, Issue: 1 ISSN: 0018-9448 Abstract: Not Available Index Terms: Not Available ----- A non-linear prediction theory Drenick, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1954 On page(s): 146- 162 Volume: 4, Issue: 4 ISSN: 0018-9448 Abstract: Not Available Index Terms: Not Available ----- A study of ergodicity and redundancy based on intersymbol correlation of finite range Watanabe, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1954 On page(s): 85- 92 Volume: 4, Issue: 4 ISSN: 0018-9448 Abstract: Some of the basic concepts of information theory are critically reviewed in the light of a generalized formulation of the theory of Markoff's chains, in which the initial and final states are sequences of symbols of different lengths, and occurrence of symbols is governed by inter-symbol correlation probability of finite range. In particular, the conditions of ergodicity and the structure of "ergodic subsets" of sequences of arbitrary length are carefully discussed. A mathematical method is developed to determine the "range" and "strength" of inter-symbol correlation. A brief summary of the content is given at the end of Section 1. Index Terms: Not Available ----- On the response of a certain class of systems to random inputs Heilfron, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1955 On page(s): 59- 61 Volume: 1, Issue: 1 ISSN: 0018-9448 Abstract: This paper deals with the connection between vector Markoff processes and the response of a lumped constant parameter linear system composed of a finite number of elements. It was known that if a Gaussian process which is one component of a vector Markoff process passes through such a system, the result is also Gaussian and may be considered as one component of a higher dimensional vector Markoff process. We show that the term Gaussian may be excluded in the above statement. The practical importance of this result is that if one can determine the initial and transition probabilities of this vector Markoff process, one can also determine the complete statistical properties of the output of the system. This further implies that the determination of the properties of the output for the class of not necessarily Gaussian inputs mentioned above is not as difficult as might be expected from the results available for just the first probability distribution for non-Gaussian inputs. Index Terms: Not Available ----- An expansion for some second-order probability distributions and its application to noise problems Barrett, J. Lampard, D. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1955 On page(s): 10- 15 Volume: 1, Issue: 1 ISSN: 0018-9448 Abstract: In this paper it is shown that, in general, second-order probability distributions may be expanded in a certain double series involving orthogonal polynomials associated with the corresponding first-order probability distributions. Attention is restricted to those second-order probability distributions which lead to a "diagonal" form for this expansion. When such distributions are joint probability distributions for samples taken from a pair of time series, some interesting results can be demonstrated. For example, it is shown that if one of the time series undergoes an amplitude distortion in a time-varying "instantaneous" nonlinear device, the covariance function after distortion is simply proportional to that before distortion. Some simple results concerning conditional expectations are given and an extension of a theorem, due to Doob, on stationary Markov processes is presented. The relation between the "diagonal" expansion used in this paper and the Mercer expansion of the kernel of a certain linear homogeneous integral equation, is pointed out and in conclusion explicit expansions are given for three specific examples. Index Terms: Not Available ----- Error bounds in noisy channels without memory Feinstein, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1955 On page(s): 13- 14 Volume: 1, Issue: 2 ISSN: 0018-9448 Abstract: It is shown that for any noisy channel without memory having only a finite number of received signals, the error in transmitting information at a rateH < Cand using uniformly good codes of lengthnis bounded by an expressionFe^{-Bn(C-H)^2}whereFandBare constants depending upon the channel parameters but not uponHorn. ----- On binary channels and their cascades Silverman, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Dec 1955 On page(s): 19- 27 Volume: 1, Issue: 3 ISSN: 0018-9448 Abstract: A detailed analysis of the general binary channel is given, with special reference to capacity (both separately and in cascade), input and output symbol distributions, and probability of error. The infinite number of binary channels with the same capacity lie on double-branched equicapacity lines. Of the channels on the lower branch of a given equicapacity line, the symmetric channel has the smallest probability of error and the largest capacity in cascade, unless the capacity is small, in which case the asymmetric channel (with one noiseless symbol) has the smallest probability of error and the largest capacity in cascade. By simply reversing the designation of the output (or input) symbols, we can decrease the probability of error of any channel on the upper branch of the equi-capacity line and increase the capacity in cascade of any asymmetric channel on the upper branch. In a binary channel neither symbol should be transmitted with a probability lying outside the interval[1/e, 1 - (1/e)]if capacity is to be achieved. The maximally asymmetric input symbol distributions are approached by certain low-capacity channels. For these channels, redundancy coding permits an appreciable fraction of capacity in cascade if sufficient delay can be tolerated. Index Terms: Information theory ----- Some optimal signals for time measurement Sherman, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1956 On page(s): 24- 28 Volume: 2, Issue: 1 ISSN: 0018-9448 Abstract: Some optimal transmitted signals are given for communications systems in which the time of occurrence of a signal is desired in the presence of additive Gaussian noise. These signals are of two classes; those in which bipolar signal excursions are permitted and those in which only unipolar signal excursions are permissible. Some bipolar codes used by R. H. Barker are supplemented when conditions permit unlimited negative excursions of the optimally correlated signal output. Other constraints, such as limiting the positive and negative excursions of the optimally correlated signal output, except at the proper phase, will lead to different codes. When only unipolar codes are permitted, optimum repetitive and nonrepetitive codes (embedded in zeros) are given for various code lengths. The minimum length of such codes is given. A mathematical resemblance is indicated to a frequency allocation problem in which third-order intermodulation products must be avoided. The closely related concepts of error-detecting and correcting codes and optimally correlated signals are illustrated in the derivation of these codes. The problem of generating such codes by other than trial and error is not solved and remains as a provocative problem. Index Terms: Error-correcting codes Signal design Time measurement ----- The bandwagon (Edtl.) Shannon, C. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1956 On page(s): 3- 3 Volume: 2, Issue: 1 ISSN: 0018-9448 Abstract: Not Available Index Terms: Information theory ----- What is information theory? (Edtl.) Wiener, N. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jun 1956 On page(s): 48- 48 Volume: 2, Issue: 2 ISSN: 0018-9448 Abstract: Not Available Index Terms: Information theory ----- On optimum non-linear extraction and coding filters Balakrishnan, A. Drenick, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1956 On page(s): 166- 172 Volume: 2, Issue: 3 ISSN: 0018-9448 Abstract: The problem of determining optimal non-linear least-square filters is solved for a class of stationary time series. This theory is then used as the basis for developing a band-width reduction scheme using non-linear encoding and decoding filters, for the same class of signals. A simple illustrative example is included. Index Terms: Nonlinear filtering Source coding Time series ----- A new interpretation of information rate Kelly, J., Jr. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1956 On page(s): 185- 189 Volume: 2, Issue: 3 ISSN: 0018-9448 Abstract: If the input symbols to a communication channel represent the outcomes of a chance event on which bets are available at odds consistent with their probabilities (i.e., "fair" odds), a gambler can use the knowledge given him by the received symbols to cause his money to grow exponentially. The maximum exponential rate of growth of the gambler's capital is equal to the rate of transmission of information over the channel. This result is generalized to include the case of arbitrary odds. Thus we find a situation in which the transmission rate has significance even though no coding is contemplated. Previously this quantity was given significance only by a theorem of Shannon's which asserted that, with suitable encoding, binary digits could be transmitted over the channel at this rate with an arbitrarily small probability of error. Index Terms: Game theory Information rates ----- Theory of information feedback systems Chang, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1956 On page(s): 29- 40 Volume: 2, Issue: 3 ISSN: 0018-9448 Abstract: A general information feedback system is defined and formulated in a way broad enough to allow coded or uncoded channels with total dr partial information feedback. Basic theorems governing change in information rate and reliability are derived with full consideration of the transition probabilities of both direct and feedback channels, including message words as well as the confirmation- denial signal. Index Terms: Feedback communication ----- Three models for the description of language Chomsky, N. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1956 On page(s): 113- 124 Volume: 2, Issue: 3 ISSN: 0018-9448 Abstract: We investigate several conceptions of linguistic structure to determine whether or not they can provide simple and "revealing" grammars that generate all of the sentences of English and only these. We find that no finite-state Markov process that produces symbols with transition from state to state can serve as an English grammar. Furthermore, the particular subclass of such processes that producen-order statistical approximations to English do not come closer, with increasingn, to matching the output of an English grammar. We formalize-the notions of "phrase structure" and show that this gives us a method for describing language which is essentially more powerful, though still representable as a rather elementary type of finite-state process. Nevertheless, it is successful only when limited to a small subset of simple sentences. We study the formal properties of a set of grammatical transformations that carry sentences with phrase structure into new sentences with derived phrase structure, showing that transformational grammars are processes of the same elementary type as phrase-structure grammars; that the grammar of English is materially simplified if phrase structure description is limited to a kernel of simple sentences from which all other sentences are constructed by repeated transformations; and that this view of linguistic structure gives a certain insight into the use and understanding of language. Index Terms: Languages Markov processes ----- Some general aspects of the sampling theorem Jagerman, D. Fogel, L. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Dec 1956 On page(s): 139- 146 Volume: 2, Issue: 4 ISSN: 0018-9448 Abstract: The sampling theorem is recognized as an interpolation formula. Starting from the Lagrange Polynomial, this theorem is developed under conditions which are of broader applicability than those usually stated. Such a view point indicates the essential unity of temporal and frequency domain application. It will also be shown that the theorem is applicable as an exact interpolation formula throughout the complex plane. The basic theorem is extended to include sampling of the first derivative of the function. The concept of band-limited functions is introduced through use of Fourier-Stieltjes representations. This is then shown to be subsumed under the general class of functions which is considered in connection with the interpolation theorems developed. This approach, as presented, readily leads to the establishment of many sampling theorems. It is hoped that this paper will aid the formulation of particularly applicable sampling theorems for specific problems. Index Terms: Signal sampling/reconstruction Smoothing methods ----- On the Shannon theory of information transmission in the case of continuous signals Kolmogorov, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Dec 1956 On page(s): 102- 108 Volume: 2, Issue: 4 ISSN: 0018-9448 Abstract: Not Available Index Terms: Information theory ----- Locally stationary random processes Silverman, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1957 On page(s): 182- 187 Volume: 3, Issue: 3 ISSN: 0018-9448 Abstract: A new kind of random process, the locally stationary random process, is defined, which includes the stationary random process as a special case. Numerous examples of locally stationary random processes are exhibited. By the generalized spectral densityPsi(omega, omega prime)of a random process is meant the two-dimensional Fourier transform of the covariance of the process; as is well known, in the case of stationary processes,Psi(omega, omega prime)reduces to a positive mass distribution on the lineomega = omega primein theomega, omega primeplane, a fact which is the gist of the familiar Wiener-Khintchine relations. In the case of locally stationary random processes, a relation is found between the covariance and the spectral density which constitutes a natural generalization of the Wiener-Khintchine relations. Index Terms: Stochastic processes ----- A generalization of a method for the solution of the integral equation arising in optimization of time-varying linear systems with nonstationary inputs Shinbrot, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Dec 1957 On page(s): 220- 224 Volume: 3, Issue: 4 ISSN: 0018-9448 Abstract: A new method is presented for the solution of the integral equation which arises in the optimization of a system in the presence of noise when the inputs are not stationary. The method depends on the correlation functions satisfying a certain condition which, fortunately, is frequently satisfied in practical situations. A simple example is presented to illustrate the method. Index Terms: Integral equations Linear systems Optimization methods ----- A useful theorem for nonlinear devices having Gaussian inputs Price, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jun 1958 On page(s): 69- 72 Volume: 4, Issue: 2 ISSN: 0018-9448 Abstract: If and only if the inputs to a set of nonlinear, zero-memory devices are variates drawn from a Gaussian random process, a useful general relationship may be found between certain input and output statistics of the set. This relationship equates partial derivatives of the (high-order) output correlation coefficient taken with respect to the input correlation coefficients, to the output correlation coefficient of a new set of nonlinear devices bearing a simple derivative relation to the original set. Application is made to the interesting special cases of conventional cross-correlation and autocorrelation functions, and Bussgang's theorem is easily proved. As examples, the output autocorrelation functions are simply obtained for a hard limiter, linear detector, clipper, and smooth limiter. Index Terms: Correlation functions Gaussian processes Nonlinearities ----- Non-mean-square error criteria Sherman, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1958 On page(s): 125- 126 Volume: 4, Issue: 3 ISSN: 0018-9448 Abstract: While in the engineering literature non-mean-square error criteria for predictors are often presented as physically significant and then shunted aside because of mathematical unmanageability, it is shown here that ia the case of Gaussian processes all such criteria given ia three recent textbooks yield the same predictor as the linear minimum mean-square predictor of Wiener. Index Terms: Gaussian processes Prediction methods Wiener filtering ----- Some quantum effects in information channels Stern, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1960 On page(s): 435- 440 Volume: 6, Issue: 4 ISSN: 0018-9448 Abstract: In this paper the quantum nature of electromagnetic radiation is used as a basis for a mathematical model of a continuous channel. It is shown that this "photon channel" model leads to more realistic conclusions regarding information transmission. Among the results obtained are: 1) the maximum entropy for a narrow-band source under an average power limitation, 2) the frequency distribution (Bose-Einstein) for a wide-band power-limited source, 3) the transmission rate through a Poisson channel with additive Poisson noise. Index Terms: Information theory Quantum theory ----- On a characterization of processes for which optimal mean-square systems are of specified form Balakrishnan, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1960 On page(s): 490- 500 Volume: 6, Issue: 4 ISSN: 0018-9448 Abstract: This paper presents the first results in an unconventional approach to the problem of mean-square optimization. Instead of obtaining a representation for the optimal operator for a process, we seek to characterize the class of processes for which the optimal operator is of specified form. If the processes are given, so that the multivariate characteristic functions are known, then our results can be used to tell whether it is possible for the optimal operator to have a specified form. The bulk of the paper pertains to the signal extraction problem where the signal and noise are independent and additive, and it is desired to estimate some function of the signal. Here, with a slight shift in viewpoint, we phrase the characterization problem in the following way: Given, for example, a noise process, determine the class of signal processes for which the optimal extraction system is of specified form. The case where the noise process is Gaussian comes in for special attention. Index Terms: Estimation Optimization methods ----- A new derivation of the entropy expressions Golomb, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1961 On page(s): 166- 167 Volume: 7, Issue: 3 ISSN: 0018-9448 Abstract: In the discrete case, the Shannon expression for entropy is obtained as a line integral in probability space. The integrand is the "information density vector" (log p_1, log p_2, cdots, log p_n). In the continuous case, the continuous analog of information density is integrated to obtain the entropy expression for continuous probability distributions. Index Terms: Entropy functions ----- On the factorization of rational matrices Youla, D. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1961 On page(s): 172- 189 Volume: 7, Issue: 3 ISSN: 0018-9448 Abstract: Many problems in electrical engineering, such as the synthesis of linear n ports and the detection and filtration of multivariable systems corrupted by stationary additive noise, depend for their successful solution upon the factorization of a matrix-valued function of a complex variablep. This paper presents several algorithms for affecting such decompositions for the class of rational matricesG(p), i.e., matrices whose entries are ratios of polynomials inp. The methods employed are elementary in nature and center around the Smith canonic form of a polynomial matrix. Several nontrivial examples are worked out in detail to illustrate the theory. Index Terms: Matrix factorization Polynomial matrices Rational matrices ----- Correction to 'On the Factorization of Rational Matrices' Youla, D. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Oct 1961 On page(s): 277- 277 Volume: 7, Issue: 4 ISSN: 0018-9448 Abstract: Not Available Index Terms: Not Available ----- Low-density parity-check codes Gallager, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1962 On page(s): 21- 28 Volume: 8, Issue: 1 ISSN: 0018-9448 Abstract: A low-density parity-check code is a code specified by a parity-check matrix with the following properties: each column contains a small fixed numberj geq 3of l's and each row contains a small fixed numberk > jof l's. The typical minimum distance of these codes increases linearly with block length for a fixed rate and fixedj. When used with maximum likelihood decoding on a sufficiently quiet binary-input symmetric channel, the typical probability of decoding error decreases exponentially with block length for a fixed rate and fixedj. A simple but nonoptimum decoding scheme operating directly from the channel a posteriori probabilities is described. Both the equipment complexity and the data-handling capacity in bits per second of this decoder increase approximately linearly with block length. Forj > 3and a sufficiently low rate, the probability of error using this decoder on a binary symmetric channel is shown to decrease at least exponentially with a root of the block length. Some experimental results show that the actual probability of decoding error is much smaller than this theoretical bound. Index Terms: Error-correcting codes Parity checks ----- Temporal coding of neural responses to acoustic stimuli Kiang, N. Goldstein, M. Peake, W. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Feb 1962 On page(s): 113- 119 Volume: 8, Issue: 2 ISSN: 0018-9448 Abstract: Electric responses to acoustic stimuli have been recorded from the auditory nervous system of cats. Responses of single nerve cells in the cochlear nucleus recorded with microelectrodes, and auditory nerve responses recorded with gross electrodes (which record activity of many cells) are presented as examples of the kinds of data which can be obtained. The behavior of these responses for various changes in stimulus parameters is illustrated together with several methods of data analysis. The data presented are from studies in auditory physiology in which one aim is a description of the neural coding of the temporal pattern of acoustic stimuli. Index Terms: Auditory system Nervous system ----- Analog models of neural mechanism Harmon, L. Levinson, J. Bergeijk, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Feb 1962 On page(s): 107- 112 Volume: 8, Issue: 2 ISSN: 0018-9448 Abstract: This paper outlines in condensed form the use that can be made of accurate neural analogs in analyzing the complexities of nervous systems. After a short review of the most pertinent information available in neurophysiology, various ways of modeling neural behavior are discussed. A brief description is given of the "neuromime" we have used. We then describe two applications of this analog. The first is a model of the flicker-fusion mechanism of the eye, and the second is a model of the spiral innervation of the ear. Index Terms: Nervous system ----- Information capacity of a single retinal channel Kelly, D. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Apr 1962 On page(s): 221- 226 Volume: 8, Issue: 3 ISSN: 0018-9448 Abstract: Recent psychophysical experiments with sinusoidally flickering waveforms provide suitable data for calculating the maximum rate at which information can enter the human visual system, according to the single-channel model which explains these data; i.e., if the signal-to-noise ratio in the retinal pathways governs the minimum detectable modulation amplitude, then the latter is an appropriate measure of the maximum number of distinguishable signals within a given narrow frequency band. Applying the Hartley-Shannon Law, these measured (gain-vs-frequency) response curves are integrated to obtain the (retinal average) channel capacity. This procedure yields a monotonic function of the adapting luminance, increasing at high photopic levels to almost 800 bits per sec per channel or about10^9bits per sec for the entire retina. Most of this large input capacity is obviously not directly available for the transmission of (random) signals by the human observer; the results are discussed from this viewpoint and compared with other estimates of sensory information rates. Index Terms: Information rates Visual system ----- On instantaneous entropy Foy, W., Jr. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1962 On page(s): 267- 274 Volume: 8, Issue: 5 ISSN: 0018-9448 Abstract: Not Available Index Terms: Entropy functions ----- Sur la limitation spectrale et la frequence instantanee des signaux (in French) Oswald, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1962 On page(s): 275- 282 Volume: 8, Issue: 5 ISSN: 0018-9448 Abstract: L'article qui suit présente une interpretation nouvelle de la limitation du spectre des signaux, conduisant à des modes de representation différents de celui, classique, qui consiste à associer une fonction continue du temps à un signal. La méthode proposée lève les difficultés fondamentales de localisation simultanée dans le temps et dans l'intervalle spectral, et aboutit à une définition cohérente de la fréquence instantanée. Index Terms: Not Available ----- System performance in the presence of stochastic delays Brown, W. Palermo, C. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1962 On page(s): 206- 214 Volume: 8, Issue: 5 ISSN: 0018-9448 Abstract: System performance in the presence of additive noise has been given considerable attention in the past. With the advent of sophisticated data-processing systems using high time-bandwidth products, it becomes necessary to consider the effects of stochastic delays. Depending on the particular application, the mathematical process to be considered is either a stochastic process of a stochastic process or a function of a stochastic process. Ifx(t), a stochastic process, represents the stochastic delay, andf(t)is either a stochastic process or a fixed functionf(t)represents the ideal signal) then the process to be studied isg(t) = f[t + x(t)]. This paper derives various properties ofg(t)and applies them to system performance. In the first section the correlation function and power spectrum ofg(t)are derived in terms of the characteristic function ofx(t)and the power density spectrum off(t)wheref(t)is a random process. It is shown that the effect of stochastic delays is to increase the bandwidth of the received data. In the second section, these results are applied to optimum least squares filtering, and optimum linear filters and expressions for the mean square error are derived. Important special cases are considered. In particular it is shown that with equal first-order statistics, high frequency delays cause less degradation than low frequency delays. Along somewhat similar lines, some results on random jitter in sampling are derived. The degradation due to high and low frequency jitter are compared. At high sampling rates, low frequency jitter causes more error; but when the sampling rate is matched to the bandwidth off(t), high frequency jitter causes greater degradation. In the final section the effect of stochastic delays on the ambiguity function are considered. Expressions are derived that show that the presence of stochastic delays degrades both time and doppler resolution. Index Terms: Delay Least-squares estimation Stochastic processes ----- Optimum message transmission in a finite time Chang, S. Harris, B. Metzner, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1962 On page(s): 215- 224 Volume: 8, Issue: 5 ISSN: 0018-9448 Abstract: The basic problem of transmitting information through a noisy channel in a finite time with the least error is considered. The transmitted signals are either peak or average power limited, and the interference is presumed to be additive white gaussian noise. It is shown that the optimum signals are sequences of binary waveforms resembling a(2^m -l,m)Slepian group code, the generators of which can be obtained from a modified Reed Code. An analysis is also made of near-optimum codes which allow some inequality in the distance between code words in signal space. The advantage of these near-optimum codes is that for a small sacrifice in error probability, either the information rate can be substantially increased, or the bandwidth of the system greatly reduced. The details of these sytems are given and the results show that a many-fold improvement is obtained. An instrumentation of the detector is also presented to show how the code groups at the receiver can be effectively stored as an arrangement of resistors. Index Terms: Coding Information rates Signal design ----- Mathematical analysis of formal structure of music Fucks, W. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1962 On page(s): 225- 228 Volume: 8, Issue: 5 ISSN: 0018-9448 Abstract: Statistical properties of music and their development since about 1500 have been studied; e.g. the properties of frequency distributions of pitch and duration of tones, of intervals of consecutive tones, correlograms of various parameters up to distances of 30 of these parameters, matrices of transition probabilities of various parameters. In the period considered here the variance of the frequency distributions of pitch grows from 3 to 13 and the mean value of the kurtosis of the intervals of consecutive tones grows from 5 to 15 and splits up in recent times into two distinct values (15 and 6, 5). Index Terms: Music ----- Learning process and inverse H-theorem Watanabe, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1962 On page(s): 246- 251 Volume: 8, Issue: 5 ISSN: 0018-9448 Abstract: It is proposed to use the time rate of decrease of the entropy defined by the response probabilities as a measure of the speed of learning. An empirical formula, see Index Terms: Entropy functions Learning procedures ----- Time-frequency duality Bello, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1964 On page(s): 18- 33 Volume: 10, Issue: 1 ISSN: 0018-9448 Abstract: This paper develops a concept of duality, called time-frequency duality, which is applicable to a class of networks called communication-signal-processing networks. Such networks consist of an interconnection of basic elements such as filters, mixers, delay lines, etc. The usefulness of time-frequency duality stems from the fact that two situations which may be quite distinct physically can have identical behavior patterns except for an interchange of the roles played by time and frequency. As a result, the solution to a detection or estimation problem may be found directly from the solution of the dual problem, if known, merely by replacing variables and quantities by their duals. This application of time-frequency duality is illustrated in the paper by the problem of measuring the transfer function of a scatter medium by means of an optimal gating operation prior to spectrum analysis. Another benefit to be obtained from time-frequency duality is the generation of new ideas for communication signal processing techniques. We illustrate this type of benefit by constructing the dual of the Kineplex communication system. A third benefit is the additional insight gained into a communication problem by the ability to look at it in another way. This benefit is illustrated by the characterization of time-variant linear channels. It is demonstrated that such channels may be characterized in an interesting symmetrical manner in time and frequency variables by defining dual system functions. Index Terms: Duality Signal detection Signal estimation Signal processing Time-varying channels ----- Rook domains, Latin squares, affine planes, and error-distributing codes Golomb, S. Posner, E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1964 On page(s): 196- 208 Volume: 10, Issue: 3 ISSN: 0018-9448 Abstract: A problem originally suggested in the context of genetic coding leads naturally to the concept of {em rook packing} and {em error-distributing codes}. It is shown how various concepts in the theory of Latin squares, and also in coding theory, are best expressed in the form of questions about the placing of rooks onk-dimensional hyperchessboards of siden. A new species of combinatorial design suggested by this is the concept of {em optimal coloring}. It is shown that the optimal colorings in certain cases correspond to duals of desarguian projective planes. Light is thereby shed on the problems of the existence of both finite projective planes and close-packed single-error-correcting codes. In particular, the existence of a certain close-packed nonbinary single-error-correcting code, listed by Golay as the first unknown case, has been ruled out by a well-known result concerning Latin squares. Index Terms: Coding Error-control coding Error-correcting codes ----- Entropy as a measure Campbell, L. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1965 On page(s): 112- 114 Volume: 11, Issue: 1 ISSN: 0018-9448 Abstract: A probability space of a special type is put into correspondence with a measure space. Under this correspondence, sets in the measure space correspond to partitions of the probability space and the measure of a set equals the entropy of the corresponding partition. Index Terms: Entropy functions Information theory ----- A simple derivation of the coding theorem and some applications Gallager, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1965 On page(s): 3- 18 Volume: 11, Issue: 1 ISSN: 0018-9448 Abstract: Upper bounds are derived on the probability of error that can be achieved by using block codes on general time-discrete memoryless channels. Both amplitude-discrete and amplitude-continuous channels are treated, both with and without input constraints. The major advantages of the present approach are the simplicity of the derivations and the relative simplicity of the results; on the other hand, the exponential behavior of the bounds with block length is the best known for all transmission rates between0and capacity. The results are applied to a number of special channels, including the binary symmetric channel and the additive Gaussian noise channel. Index Terms: Block codes Memoryless channels ----- Determination of optimum nonlinear systems for generalized error criteria based on the use of gate functions Schetzen, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1965 On page(s): 117- 125 Volume: 11, Issue: 1 ISSN: 0018-9448 Abstract: A generalization of the error criteria in the analysis of optimum nonlinear systems is presented. The experimental and analytical techniques presented are based upon the expansion of the nonlinear system in the orthogonal set of gate functions that were introduced into the study of nonlinear systems by Bose in 1955. It is shown that, for various error criteria, the coefficients in the expansion can be determined independently of each other. By making use of this result, methods are developed for the determination of nonlinear systems with and without memory, for which an arbitrary weighted function of the error or the probability of an arbitrary function of the error is a minimum. Index Terms: Nonlinear systems ----- Probability of decoding error for random phase and Rayleigh fading channels Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1965 On page(s): 53- 61 Volume: 11, Issue: 1 ISSN: 0018-9448 Abstract: In this paper, the probability of error of two time-varying channels with memory, 1) the random phase channel and 2) the Rayleigh fading channel, is discussed. The input is assumed to be one of M equiprobable waveforms. An upper bound to the probability of error is derived by convetting the channel into a memoryless one by means of scrambling. A lower bound to the probability of error is derived by assuming that except for an additive noise, all the channel parameters are completely known at the receiver and, therefore, are not considered to be random variables any more. Following this assumption, it is shown that the channel is converted into a memoryless channel. For each one of the two channels, there is a region of SNR where the upper and lower bounds are close together and therefore yield a good estimate to the actual probability of error. Furthermore, using random coding and scrambling, this probability of error may actually be achieved (for a certain region of rates). Index Terms: Decoding Fading channels Time-varying channels ----- The convolution inequality for entropy powers Blachman, N. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Apr 1965 On page(s): 267- 271 Volume: 11, Issue: 2 ISSN: 0018-9448 Abstract: The entropy power of a band-limited random process is the power of white Gaussian noise having the same entropy rate. Shannon's convolution inequality for entropy power states that the entropy power of the sum of two independent random processes is at least the sum of their entropy powers. This paper presents an improved version of Stam's proof of this inequality, which is obtained by mathematical induction from the one-dimensional case. Index Terms: Convolution Entropy functions ----- A simple example of a channel for which the strong converse fails (Corresp.) Ash, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1965 On page(s): 456- 457 Volume: 11, Issue: 3 ISSN: 0018-9448 Abstract: Not Available Index Terms: Error-correcting codes ----- On decoding binary Bose-Chadhuri- Hocquenghem codes Berlekamp, E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Oct 1965 On page(s): 577- 579 Volume: 11, Issue: 4 ISSN: 0018-9448 Abstract: The solution of Newton's identities over a field of characteristic two is the key step in decoding Bose-Chaudhuri-Hocquenghem codes. This paper introduces a simple transformation of variables which halves the size of the resulting matrix. This transformation can increase the decoder's speed by almost a factor of eight and decrease the decoder's storage requirements by almost a factor of four. Index Terms: BCH codes Decoding ----- Theoretical limitations on the transmission of data from analog sources Goblick, T., Jr. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Oct 1965 On page(s): 558- 567 Volume: 11, Issue: 4 ISSN: 0018-9448 Abstract: Fundamental limitations on the performance of any type of communication system transmitting data from an analog source may be obtained by application of a theorem in Shannon's original paper on information theory. In order to transmit the output of an analog source to a sink with mean-squared error e or less, it is necessary to transmit information from source to sink at rates greater than some minimal rateR(epsilon)bits per second. If a channel of capacityCbits per second is used, then in order for any communication system to be able to achieveepsilonmean-squared error or less with this channel it is necessary thatR(epsilon) leq C. This inequality can be used to determine the minimum mean-squared error obtainable for a given source-channel pair without discussing any particular communication system. As an example, the minimum mean-squared error is calculated for cases in which the analog source and additive channel noise are stationary, Gaussian processes. The performance of amplitude and angle modulation systems is compared to the theoretically ideal performance obtainable in some of these cases. Index Terms: Information theory Modulation/demodulation Rate-distortion theory ----- On decoding BCH codes Forney, G., Jr. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Oct 1965 On page(s): 549- 557 Volume: 11, Issue: 4 ISSN: 0018-9448 Abstract: The Gorenstein-Zierler decoding algorithm for BCH codes is extended, modified, and analyzed; in particular, we show how to correct erasures as well as errors, exhibit improved procedures for finding error and erasure values, and consider in some detail the implementation of these procedures in a special-purpose computer. Index Terms: BCH codes Decoding ----- Generalized Barker sequences Golomb, S. Scholtz, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Oct 1965 On page(s): 533- 537 Volume: 11, Issue: 4 ISSN: 0018-9448 Abstract: A generalized Barker sequence is a finite sequence{a_{r}}of complex numbers having absolute value1, and possessing a correlation functionC(tau)satisfying the constraint|C(tau)| leq 1, tau neq 0. Classes of transformations leaving|C(tau)|invariant are exhibited. Constructions for generalized Barker sequences of various lengths and alphabet sizes are given. Sextic Barker sequences are investigated and examples are given for all lengths through thirteen. No theoretical limit to the length of sextic sequences has been found. Index Terms: Correlation functions Sequences ----- Step-by-step decoding of the Bose-Chaudhuri- Hocquenghem codes Massey, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Oct 1965 On page(s): 580- 585 Volume: 11, Issue: 4 ISSN: 0018-9448 Abstract: A new and conceptually simple decoding procedure is developed for all of the cyclic Bose-Chaudhuri-Hocquenghem codes. Iftis the number of errors guaranteed correctable by the Bose-Chaudhuri bound, then any pattern oftor fewer errors can be corrected in a step-by-step manner using this procedure. In the binary case, the method requires only the determination of whether at times tmatrix is singular. In the general case, the method requires only the determination of whether at times tmatrix and a(t+1) times (t+1)matrix are simultaneously singular. Circuits to implement the algorithm are developed and two detailed examples are given. Finally, the step-by-step procedure is compared to other known methods for decoding the Bose-Chaudhuri-Hocquenghem codes. Index Terms: BCH codes Decoding ----- Codes with synchronization capability Scholtz, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Apr 1966 On page(s): 135- 142 Volume: 12, Issue: 2 ISSN: 0018-9448 Abstract: A synchronizable(SC_{s})code has the property that the punctuation (comma or no comma, comma indicating that the next symbol is the beginning of a new code word) at a given position in a code symbol stream can always be determined by observing at mostscode symbols in the neighborhood of the position in question. The construction ofSC_{s}dictionaries and the mechanization of synchronizers using nonlinear shift registers are explained in detail. Necessary and sufficient conditions for the existence ofSC_{s}codes with specified word lengths are derived. By allowing unequal word lengths in the code, it is demonstrated that a substantial saving in average word length and information rate can be accomplished over other recently proposed codes having synchronization capability. Index Terms: Coding Comma-free codes Synchronization ----- Self-synchronizing codes derived from binary cyclic codes Levy, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1966 On page(s): 286- 290 Volume: 12, Issue: 3 ISSN: 0018-9448 Abstract: The sensitivity of a binary block code to loss of synchronism (misplacement of the "commas" separating codewords) can be characterized by a pair of numbers[s, delta]such that any synchronization slip of s bits or less produces an overlap sequence differing from a legitimate codeword in at leastdeltaplaces. This definition is broader than that of comma freedom of indexdelta, which is included as the special case of s equal to the integer part of half the code block length. For codes having the slip-detecting characteristic[s, delta]there exists the possibility of implementation to restore synchronism during an interval relatively free from bit errors. It is shown that certain error-correcting binary cyclic block codes can be altered to obtain the characteristic[s, delta]by the addition of a fixed binary vector to each codeword prior to transmission. These altered cyclic codes retain the full error-correcting power of the original cyclic codes. An error-detecting/correcting data format providing protection against the acceptance of misframed data is thus obtained without the insertion of special synchronizing sequences into the bit stream. Index Terms: Cyclic codes Synchronization ----- A per letter converse to the channel coding theorem Reiffen, B. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Oct 1966 On page(s): 475- 480 Volume: 12, Issue: 4 ISSN: 0018-9448 Abstract: By relating the average probability of error to the distortion measure of a source-sink pair, we prove a converse to the channel coding theorem. This converse lower-bounds the probability of error per source letter. It differs from the more familiar "weak" and "strong" converses which bound the probability of error of an entire message. The result is applicable to all stationary sources, all channels, and all block lengths. Lower-bounding the rate distortion function of the source-sink pair with which the channel is to be used reduces the new result to a lower bound on the achievable probability of error per source letter expressed in terms of the source entropy, alphabet size, and maximum achievable average mutual information on the channel. This latter result had been proved previously only for a memoryless channel operating with an independent letter source. Index Terms: Block codes ----- On the capabilities of codes to correct synchronization errors Ullman, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1967 On page(s): 95- 105 Volume: 13, Issue: 1 ISSN: 0018-9448 Abstract: A synchronization error is said to occur when either a bit which does not belong appears, or is detected in a channel between bits which were transmitted; or a bit which was transmitted is lost or not detected. A model for such a channel will be proposed, and a lower and upper bound on the redundancy necessary to correct a given error rate will be derived. We will consider the case of single synchronization error correction in detail, and stronger bounds will be derived for that case. We will consider multiple adjacent synchronization errors as a special case, and show that the bounds can be tightened in this case as well. Index Terms: Error-correcting codes ----- Some noises withI/fspectrum, a bridge between direct current and white noise Mandelbrot, B. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Apr 1967 On page(s): 289- 298 Volume: 13, Issue: 2 ISSN: 0018-9448 Abstract: Noises in thin metallic fills, semiconductors, nerve tissues, and many other media, have measured spectral densities proportional tof^theta - 2}withfthe frequency andthetaa constant0 leq theta < 2. The energy of these "f^{theta-2}noises" behaves more "erratically" in time, than expected from functions subject to the Wiener-Khinchin spectral theory. Moreover, blind extrapolation of the "f^{theta -2}law" tof=0incorrectly suggests, when0 leq 1, that the total energy is infinite ("infrared catastrophe"). The problems thus raised are of the greatest theoretical interest, and of the greatest practical importance in the design of electronic devices. The present paper reinterprets these spectral measurements without paradox, by introducing a concept to be called "conditional spectrum." Examples are given of functions ruled by chance, that have the observed "erratic" behavior and conditional spectral density. A conditional spectrum is obtained when a procedure, meant to measure a sample Wiener-Khinchin spectrum, is applied to a sample conditioned to be nonconstant. The conditional spectrum is defined, not only for nonconstant samples from all random functions of the Wiener-Khinchin theory, but also for nonconstant samples from certain nonstationary random functions, and for nonconstant samples from a new generalization of random functions, called "sporadic functions." The simplest sporadic functions, having af^{-2}conditional spectral density, is a "direct current" with a single discontinuity uniformly distributed over- infty < t < infty. The otherf^{theta -2}noises to be described partake both of direct current and of white noise (thetheta =2limit off^{theta - 2}noise), and continuously span the gap between these limits. In many cases, their noise energy can be said to be proportional to the square of their "dc" component. Empirical studies will be suggested, and the descriptive value of the concepts of dc component and of spectrum will be discussed. Index Terms: Noise ----- On the reducibility of Toeplitz eigenvalue equations (Corresp.) Mullen, J. Raytheon Company, Waltham, MA, USA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1968 On page(s): 162- 163 Volume: 14, Issue: 1 ISSN: 0018-9448 Abstract: Not Available Index Terms: Eigenvalues Toeplitz matrices ----- Information transmission in evolution Spetner, L. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1968 On page(s): 3- 6 Volume: 14, Issue: 1 ISSN: 0018-9448 Abstract: On the basis of a model previously established for the random-mutation portion of the synthetic theory of evolution, an investigation is made of the information that can be transmitted from the environment to the evolving species. The probability that a given adaptive character is produced decreases with increasing information measure of the adaptive character. The average information transmitted in any one evolutionary step is defined as the product of the information and its probability of transmission. The average information turns out to be very small for a reasonable number of trials and reasonable gene size. This is consistent with the conjecture that evolution proceeds in small steps, and the size of a step can be discussed quantitatively in terms of the amount of adaptive information that is being transmitted into the species. Index Terms: Biological systems Information theory ----- The amount of information that y gives about X Blachman, N. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1968 On page(s): 27- 31 Volume: 14, Issue: 1 ISSN: 0018-9448 Abstract: No single measureM(X;y)of the amount of information that a specific valueyof a random variableYgives about another random variableXhas all of the desirable properties possessed by Shannon's measureI(X;Y) = E{M(X;y)}of the average mutual information ofXandY. It is shown that one of these properties (additivity) determines one particular form forM(X;y), while others (non-negativity or coordinate independance) determine a different form. The latter, which is the more useful and accepted information measure, is thus seen to be unique. Index Terms: Information theory Random variables ----- An extension of rate-distortion theory to confusion matrices Ebert, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1968 On page(s): 6- 11 Volume: 14, Issue: 1 ISSN: 0018-9448 Abstract: A discrete confusion matrix is completely specified by a set of transition probabilities,P_{D}(y/x), wherexandyare the input and output symbols, respectively. In this paper we examine the possibility of simulating such a matrix by an available channel with processors at the input and output, when the source is specified beforehand. The central result is to show that such a simulation is always possible when the capacity of the available channel is larger than the mutual information between the source and the desired output. Conversely, such a simulation is not possible if the capacity is less than the mutual information. These results indicate the conditions under which it is physically possible to build transmitter-receiver pairs to approximate a desired discrete confusion matrix. Index Terms: Rate-distortion theory ----- Center-of-gravity information feedback Schalkwijk, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1968 On page(s): 324- 331 Volume: 14, Issue: 2 ISSN: 0018-9448 Abstract: We considerMsignals in aD-dimensional signal space. TheseMsignals are used to communicate over an additive Gaussian white noise channel. It is shown that if a noiseless feedback channel is available one could use this feedback channel to inform the transmitter of the location of the center of gravity of the signal structure and thus obtain a very efficient signaling scheme. Each signal point is assigned a mass proportional to its posterior probability at the particular instant. The center of gravity is used by the transmitter as a new origin for the signal space. It is shown that some previously considered coding schemes for channels with feedback are particular cases of center-of-gravity feedback. The probability of error decreases as a double exponential function of the coding delay as opposed to an exponential decrease for one-way systems. The effect of noise in the feedback path is briefly considered. Index Terms: Feedback communication ----- The uncorrelated output components of a nonlinearity Blachman, N. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1968 On page(s): 250- 255 Volume: 14, Issue: 2 ISSN: 0018-9448 Abstract: Using his characteristic-function approach, Rice (1945) obtained a double series for the autocorrelation function of a sinusoidal signal and Gaussian noise after passage through a memoryless nonlinearity. It is shown here that the output of the nonlinearity can be expressed as the sum of uncorrelated terms whose auto-correlation functions are the terms of Rice's double series. Such a decomposition of the output is shown to be generally possible if and only if the bivariate probability density functions of the input signal and the input noise can both be expressed in the diagonal form studied by Barrett and Lampard (1955), though not necessarily involving polynomials, as they can in the sinusoidal and Gaussian cases. In addition, a more direct and meaningful equation is found for the coefficients in Rice's double series. Index Terms: Correlation functions Nonlinearities ----- A remark on per letter converses for a discrete channel (Corresp.) Wagner, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1968 On page(s): 606- 607 Volume: 14, Issue: 4 ISSN: 0018-9448 Abstract: Not Available Index Terms: Mutual information ----- The Fisher information and convexity (Corresp.) Cohen, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1968 On page(s): 591- 592 Volume: 14, Issue: 4 ISSN: 0018-9448 Abstract: Not Available Index Terms: Information theory Parameter estimation ----- Poisson transform signal analysis (Corresp.) Bolgiano, L. Piovoso, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1968 On page(s): 600- 601 Volume: 14, Issue: 4 ISSN: 0018-9448 Abstract: It is shown that the Poisson transform used in the statistical theory of photodetection corresponds to a simple sign measurement and has mathematical properties which suggest its use in other areas of signal theory. Index Terms: Poisson transforms Signal analysis ----- Logical basis for information theory and probability theory Kolmogorov, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1968 On page(s): 662- 664 Volume: 14, Issue: 5 ISSN: 0018-9448 Abstract: A new logical basis for information theory as well as probability theory is proposed, based on computing complexity. Index Terms: Information theory Probability ----- A coding theorem for time-discrete analog data sources Goblick, T., Jr. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1969 On page(s): 401- 407 Volume: 15, Issue: 3 ISSN: 0018-9448 Abstract: The main result of the paper is a coding theorem for time-discrete sources with a fidelity criterion on average distortion. This result applies to a subclass of the ergodic sources (stationary sources having a strong mixing property) and to the cases in which source samples are continuously distributed (analog) quantities or discrete symbols. An intuitive definition of the information content of data samples for this class of sources is then formally established and is shown to be exactly the same as Shannon's definition. Index Terms: Source coding ----- On the difficulty of computations Chaitin, G. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1970 On page(s): 5- 9 Volume: 16, Issue: 1 ISSN: 0018-9448 Abstract: Two practical considerations concerning the use of computing machines are the amount of information that must be given to the machine for it to perform a given task and the time it takes the machine to perform it. The size of programs and their running time are studied for mathematical models of computing machines. The study of the amount of information (i.e., number of bits) in a computer program needed for it to put out a given finite binary sequence leads to a definition of a random sequence; the random sequences of a given length are those that require the longest programs. The study of the running time of programs for computing infinite sets of natural numbers leads to an arithmetic of computers, which is a distributive lattice. Index Terms: Computation theory ----- Coding theorems for the nonsynchronized channel Chase, D. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1970 On page(s): 55- 73 Volume: 16, Issue: 1 ISSN: 0018-9448 Abstract: Capacity and error bounds are derived for a memoryless binary symmetric channel with the receiver having no a priori information as to the starting time of the code words. The channel capacity is the same as the capacity of the synchronized channel. For all rates below capacity, the minimum probability of error for the nonsynchronized channel decreases exponentially with the code-block length. For rates near channel capacity, the exponent in the upper bound on the probability of error for the nonsynchronized channel is the same as the corresponding exponent for the synchronized channel. For low rates, the largest exponent obtained for the nonsynchronized channel with conventional block coding is inferior to the exponent obtained for the synchronized channel. Stronger results are obtained for a new form of coding that allows for a Markov dependency between successive code words. Bounds on the minimum probability of error are obtained for unconstrained binary codes and for several classes of parity-check codes and are used to obtain asymptotic distance properties for various classes of binary codes. At certain rates there exist codes whose minimum distance, in the comma-free sense, is not only greater than one, but is proportional to the block length. Index Terms: Coding ----- Fitting continuous probability density functions over [0,infty) using information theory ideas (Corresp.) Wragg, A. Dowson, D. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1970 On page(s): 226- 230 Volume: 16, Issue: 2 ISSN: 0018-9448 Abstract: The problem of estimating a probability density functionp(x)over[0, infty)when several low-order moments are known is considered. A computational procedure, based on information theory, is used to obtain the maximum entropy estimates ofp(x)in a number of cases. The situation when the first two moments only are known is considered in some detail. A table is included for estimatingp(x)when givenmu_1 ^{prime} , mu_2 ^{prime}withmu_2 ^{prime} leq 2(mu_1 ^{prime}) ^ 2. Index Terms: Entropy functions Estimation Probability functions ----- Calculation of Fourier transforms on finite Abelian groups (Corresp.) Apple, G. Wintz, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1970 On page(s): 233- 234 Volume: 16, Issue: 2 ISSN: 0018-9448 Abstract: A recent paper by Crimmins et al. deals with minimization of mean-square error for group codes by the use of Fourier transforms on groups. In this correspondence a method for representing the groups in a form suitable for machine calculation is shown. An efficient method for calculating the Fourier transform of a group is also proposed and its relationship to the fast Fourier transform is shown. For groups of characteristic two, the calculation requires onlyN log_2 Nadditive operations whereNis the order of the group. Index Terms: Fourier transforms Group theory ----- Information rates of Wiener processes Berger, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1970 On page(s): 134- 139 Volume: 16, Issue: 2 ISSN: 0018-9448 Abstract: 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), wheresigma^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. Index Terms: Rate-distortion theory Wiener processes ----- The two-armed-bandit problem with time-invariant finite memory Cover, T. Hellman, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1970 On page(s): 185- 195 Volume: 16, Issue: 2 ISSN: 0018-9448 Abstract: This paper solves the classical two-armed-bandit problem under the finite-memory constraint described below. Given are probability densitiesp_0andp_1, and two experimentsAandB. It is not known which density is associated with which experiment. Thus the experimental outcomeYof experimentAis as likely to be distributed according top_0as it is to be distributed according top_1. It is desired to sequentially choose an experiment to be performed on the basis of past observations according to the algorithmT_n = f(T_{n-1}, e_n, Y_n), e_n = e(T_{n-1}), whereT_n in {1, 2, cdots, m}is the state of memory at timen, e_n in {A, B}is the choice of experiment, andY_n, is the random variable observation. The goal is to maximize the asymptotic proportionrof uses of the experiment associated with densityp_0. Letl(y) = p_0 (y) / p_1 (y), and letbar{l}andbar{bar{l}}denote the almost everywhere greatest lower bound and least upper bound onl(y). Let1 = max {bar{bar{l}}, 1/bar{l}}. Then the optimal value ofr, over allm-state algorithms(f, e), will be shown to bel^{m-1} / (l^{m-1} + 1). Ane-optimal family ofm-state algorithms will be demonstrated. In general, optimal algorithms do not exist, ande-optimal algorithms require artificial randomization. Index Terms: Finite-memory methods Learning systems Sequential decision procedures Stochastic automata ----- Reliability of quantum-mechanical communication systems Liu, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1970 On page(s): 319- 329 Volume: 16, Issue: 3 ISSN: 0018-9448 Abstract: We are concerned with the detection of a set ofMmessages that are transmitted over a channel disturbed by chaotic thermal noise when quantum effects in the communication systems are taken into account. Our attention is restricted to the special case in which the density operators specifying the state of the received field are commutative. In particular, the performance of two special communication systems is evaluated. For a system in which orthogonal signals with known amplitudes and random phases are transmitted over an additive white Gaussian channel, the structure of an optimum receiver is found. Expressions for the system reliability function and channel capacity are derived. For a system in which orthogonal signals are transmitted over a Rayleigh fading channel, the optimum performance is obtained. The optimum degree of diversity for an equal-strength diversity system is found numerically as a function of the average thermal-noise energy and information rate. Index Terms: Quantum detection ----- Entropy analysis of estimating systems Weidemann, H. Stear, E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1970 On page(s): 264- 270 Volume: 16, Issue: 3 ISSN: 0018-9448 Abstract: A study of the use of entropy as a criterion function for analyzing the performance of sampled-data estimating systems is presented, and performance bounds are obtained for a broad class of such systems. The general result is that the difference between the entropy of the signal to be estimated and the entropy of its estimate based on the output of a noisy sensor can never be larger than the mutual information between the sensor input and output. An interesting, but not totally satisfactory, sufficient condition for attainment of the bound is developed. Index Terms: Entropy functions Estimation ----- Transmission of noisy information to a noisy receiver with minimum distortion Wolf, J. Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1970 On page(s): 406- 411 Volume: 16, Issue: 4 ISSN: 0018-9448 Abstract: This paper is concerned with the transmission of information with a fidelity criterion where the source output may be distorted prior to encoding and, furthermore, where the output of the decoder may be distorted prior to its delivery to the final destination. The criterion for optimality is that the normalized average of the squared norm of the difference between theT- second undistorted source sample and the correspondingT-second sample delivered to the final destination be minimum. The optimal structure of the encoder and decoder is derived for anyT. Index Terms: Coding Decoding Source coding ----- On the detection of a sudden change in system parameters Prabhu, K. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1970 On page(s): 497- 500 Volume: 16, Issue: 4 ISSN: 0018-9448 Abstract: This correspondence deals with the problem of detecting a sudden change in system parameters by means of noisy observations made on the system. The solution given here is dependent on the classical Bayes criterion. However, by forming an auxiliary sequence of O's and l's as the observations are taken, it is shown, at most, three log-likelihood numbers need to be updated recursively at any stage. An example is given to illustrate the principle. Index Terms: Bayes procedures Sequential decision procedures Testing ----- The behavior of analog communication systems Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1970 On page(s): 587- 594 Volume: 16, Issue: 5 ISSN: 0018-9448 Abstract: We consider the problem of transmission of analog data over a noisy channel. It is assumed that the channel input is of the formsurd S f(t, X), whereXis ann-dimensional source vector, andSis the allowable transmitted power. The performance of any given modulation schemef(t, cdot )as a function of the transmitted powerSis studied. Lower bounds on the average distortion produced by noise for a class of distortion functions are derived. These bounds relate the "smoothness" of modulation techniques to the minimum error that can be achieved with them. It is shown that when the analog source emits a sequence of mutually independent real random variables at a rate ofRper second, the mean-square error that is associated with any practical modulation schemef(t, cdot)decays no faster thanS^{-2}as the signal powerS rightarrow infty. It follows that in the case of a band-limited additive white Gaussian channel no single modulation schemef(t, cdot )can achieve the ideal rate-distortion bound on the mean-square error for all values ofS, if the channel bandwidth is larger than the source rateR. Index Terms: Modulation/demodulation Rate-distortion theory ----- Convergence to the rate-distortion function for Gaussian sources Bunin, B. Wolf, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1971 On page(s): 65- 70 Volume: 17, Issue: 1 ISSN: 0018-9448 Abstract: In this paper we derive an expression for the minimum-mean-square error achievable in encodingtsamples of a stationary correlated Gaussian source. It is assumed that the source output is not known exactly but is corrupted by correlated Gaussian noise. The expression is obtained in terms of the covariance matrices of the source and noise sequences. It is shown that ast rightarrow infty, the result agrees with a known asymptotic result, which is expressed in terms of the power spectra of the source and noise. The rate of convergence to the asymptotic results as a function of coding delay is investigated for the case where the source is first-order Markov and the noise is uncorrelated. WithDthe asymptotic minimum-mean-square error andD_tthe minimum-mean-square error achievable in transmittingtsamples, we findmid D_t - D mid leq O((t^{-1} log t) ^ {1/2})when we transmit the noisy source vectors over a noiseless channel andmid D_t - D mid leq O((t^{-1} log t)^ {1/3})when the channel is noisy. Index Terms: Gaussian processes Rate-distortion theory Source coding ----- The source coding game Berger, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1971 On page(s): 71- 76 Volume: 17, Issue: 1 ISSN: 0018-9448 Abstract: 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. Index Terms: Game theory Multiplexing Rate-distortion theory Source coding ----- How does a porcupine separate its quills? Landau, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1971 On page(s): 157- 161 Volume: 17, Issue: 2 ISSN: 0018-9448 Abstract: Sets of unit vectors inN-dimensional Euclidean vector space whose constituent vectors are separated one from another by at least a fixed distanced, prescribed once for all and independent ofN, are of interest in theory and practice; they have fondly been called "porcupine codes." Although an elegant constructive proof of Gilbert shows that the number of vectors in a porcupine code (of givend) can increase exponentially withN, no systematic method is yet known for generating porcupine codes of this cardinality. Corresponding to a collection ofMvectors, we can partition the space into maximum-likelihood regions, thejth of which consists of those vectors that lie closer to thejth than to any other element of the collection. Each maximum-likelihood region is bounded by at most(M - 1)hyperplanes, and we denote byKthe total number of these bounding hyperplanes. Collections for whichKis small may be expected to have greater symmetry than those for whichKis large. In this paper we show that, for porcupine codes,K geq (M/2)^{1/s}, withsdepending only ond, the minimum separation of the code vectors. Hence, for the number of vectors of a porcupine code to increase exponentially with dimension, the number of separating hyperplanes must do so as well. We conclude with, an application to the permutation codes introduced by Slepian, showing that the number of vectors of a porcupine code which is of permutation-modulation type can not increase exponentially withN. Index Terms: Coding maximum-likelihood (ML) decoding ----- Bibliography on rate distortion theory (Corresp.) Andrews, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1971 On page(s): 198- 199 Volume: 17, Issue: 2 ISSN: 0018-9448 Abstract: This bibliography contains articles and books on the subject of rate distortion theory. Growing interest in the subject is evident by the large number of recent publications. Index Terms: Bibliographies Rate-distortion theory ----- Generalized inverse approach to clustering, feature selecting, and classification Wee, W. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1971 On page(s): 262- 269 Volume: 17, Issue: 3 ISSN: 0018-9448 Abstract: This paper gives a unified approach to designing a data analyzer that performs cluster-seeking, feature selection, and categorizer design under a weighted least-square performance criterion. The cost of misrecognitions is preserved throughout the process, It can be used as a fast procedure to evaluate the discriminatory capability of sensors and/or preprocessors. Index Terms: Feature extraction Pattern classification Pattern clustering methods ----- Repetitive signaling using a noisy feedback channel Lavenberg, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1971 On page(s): 269- 278 Volume: 17, Issue: 3 ISSN: 0018-9448 Abstract: Several feedback coding schemes considered recently are repetitive signaling schemes. The sender retransmits the message, if necessary, on the basis of information received over the feedback channel. This paper considers a repetitive signaling scheme in which the user's estimate of the transmitted message is sent over the feedback channel to the sender with high energy if the user is uncertain of the estimate and with lower energy if otherwise. The sender retransmits the message with high energy if it decides the user's estimate is incorrect. This scheme is applied to a wide-band, additive-white-Gaussian-noise, average-power-constrained feedback communication system. Orthogonal signals are used for transmission over both forward and feedback channels. A lower bound is obtained for the probability of error when arbitrary decision rules are used. This lower bound is achieved asymptotically for long block duration by using decision rules implemented with correlation receivers. The resulting asymptotic error performance is superior to that of any feedback coding scheme previously considered for use in a wide-band additive-white-Gaussian-noise system for any values of the forward and feedback channel capacities. Index Terms: Feedback communication ----- Codes based on inaccurate source probabilities Gilbert, E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1971 On page(s): 304- 314 Volume: 17, Issue: 3 ISSN: 0018-9448 Abstract: Information theory obtains efficient codes by encoding messages in large blocks. The code design requires block probabilities that are often hard to measure accurately. This paper studies the effect of inaccuracies in the block probabilities and gives coding procedures that anticipate some of the worst errors. For an efficient code, the mean numberdof digits per letter must be kept small. In some cases the expected value ofdcan be related to the size of the sample on which probability estimates are based. To underestimate badly the probability of a common letter or block is usually a serious error. To ensure against this possibility, some coding procedures are given that avoid extremely long codewords. These codes provide a worthwhile insurance but are still very efficient if the probability estimates happen to be correct. Index Terms: Block codes Source coding ----- An alternative approach to the linear causal least-square filtering theory Kung Yao This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1971 On page(s): 232- 240 Volume: 17, Issue: 3 ISSN: 0018-9448 Abstract: We present in this paper an alternative approach to the discrete-and-continuous-time, linear, causal, least-square filtering of wide-sense stationary random processes. Various new and simplified solutions for the optimum filter and the minimum-mean-square error (MMSE) are given in a unified manner by using Hilbert-space techniques. Particular emphasis is placed on the closed-form solution obtained without explicit spectral factorization. In contrast to the Wiener theory, we impose the causality requirement on the linear minimum-phase filter-transfer function by using the conjugate Poisson-integral transformation before we perform the optimization operation. After optimization, we obtain a set of integral equations from which various symmetrical properties of the optimum transfer function and the MMSE appear in simple forms. When one of the spectral densities is arbitrary, while the other is rational and fixed, the filtering problem is reduced to the solution of a set of transcendental equations. In particular, the closed-form solutions for the optimum filter and the MMSE of an arbitrary signal disturbed by a fixed, additive, wise-sense Markov noise are given explicitly for discrete-and-continuous-time cases. Index Terms: Filtering Hilbert spaces Least-squares estimation ----- Note on approximating discrete probability distributions (Corresp.) Freeman, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1971 On page(s): 491- 493 Volume: 17, Issue: 4 ISSN: 0018-9448 Abstract: Not Available Index Terms: Approximation methods Probability functions ----- Mutual information of the white Gaussian channel with and without feedback Kadota, T. Zakai, M. Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1971 On page(s): 368- 371 Volume: 17, Issue: 4 ISSN: 0018-9448 Abstract: The following model for the white Gaussian channel with or without feedback is considered: begin{equation} Y(t) = int_o ^{t} phi (s, Y_o ^{s} ,m) ds + W(t) end{equation} wheremdenotes the message,Y(t)denotes the channel output at timet,Y_o ^ {t}denotes the sample pathY(theta), 0 leq theta leq t. W(t)is the Brownian motion representing noise, andphi(s, y_o ^ {s} ,m)is the channel input (modulator output). It is shown that, under some general assumptions, the amount of mutual informationI(Y_o ^{T} ,m)between the messagemand the output pathY_o ^ {T}is directly related to the mean-square causal filtering error of estimatingphi (t, Y_o ^{t} ,m)from the received dataY_o ^{T} , 0 leq t leq T. It follows, as a corollary to the result forI(Y_o ^ {T} ,m), that feedback can not increase the capacity of the nonband-limited additive white Gaussian noise channel. Index Terms: Feedback communication Gaussian processes Mutual information ----- Capacity of a continuous memoryless channel with feedback Kadota, T. Zakai, M. Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1971 On page(s): 372- 378 Volume: 17, Issue: 4 ISSN: 0018-9448 Abstract: Shannon showed that the capacity of a discrete memoryless channel can not be increased by noiseless feedback. It has been conjectured that this should be true for a continuous memoryless channel, provided such a channel is appropriately defined. We precisely define such a channel from two mathematically different points of view and rigorously prove that its capacity can not be increased by feedback. Index Terms: Feedback communication Information rates Memoryless channels ----- RKHS approach to detection and estimation problems--I: Deterministic signals in Gaussian noise Kailath, T. Stanford University, Stanford, CA, USA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1971 On page(s): 530- 549 Volume: 17, Issue: 5 ISSN: 0018-9448 Abstract: First it is shown how the Karhunen-Loève approach to the detection of a deterministic signal can be given a coordinate-free and geometric interpretation in a particular Hilbert space of functions that is uniquely determined by the covariance function of the additive Gaussian noise. This Hilbert space, which is called a reproducing-kernel Hilbert space (RKHS), has many special properties that appear to make it a natural space of functions to associate with a second-order random process. A mapping between the RKHS and the linear Hilbert space of random variables generated by the random process is studied in some detail. This mapping enables one to give a geometric treatment of the detection problem. The relations to the usual integral-equation approach to this problem are also discussed. Some of the special properties of the RKHS are developed and then used to study the singularity and stability of the detection problem and also to suggest simple means of approximating the detectability of the signal. The RKHS for several multidimensional and multivariable processes is presented; by going to the RKHS of functionals rather than functions it is also shown how generalized random processes, including white noise and stationary processes whose spectra grow at infinity, are treated. Index Terms: Bibliographies Estimation Gaussian processes Hilbert spaces Signal detection Signal estimation Stochastic processes ----- Quantizing for maximum output entropy (Corresp.) Messerschmitt, D. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1971 On page(s): 612- 612 Volume: 17, Issue: 5 ISSN: 0018-9448 Abstract: The entropy at the output of a quantizer is equal to the average mutual information between unquantized and quantized random variables. Thus, for a fixed number of quantization levels, output entropy is a reasonable information-theoretic criterion of quantizer fidelity. It is shown that, for a class of signal distributions, which includes the Gaussian, the quantizers with maximum output entropy (MOE) and minimum average error (MAE) are approximately the same within a multiplicative constant. Index Terms: Entropy functions Quantization (signal) Signal quantization ----- Information rates of stationary ergodic finite-alphabet sources Gray, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1971 On page(s): 516- 523 Volume: 17, Issue: 5 ISSN: 0018-9448 Abstract: The generalized Shannon lower bound to the rate-distortion functionR(D)for stationary sources with memory is extended to a wide class of distortion measures involving no symmetry conditions. The lower boundR_{L} (D)is a reasonably simple function of the entropy and marginal probabilities of the source and the per-letter distortion measure. Sufficient conditions only slightly less general than necessary conditions are given for the existence of a strictly positive cutoff distortionD_csuch thatR(D) = R_{L} (D)forD leq D_c. The sufficient conditions are the most general to date and include all previously known examples. This provides a nearly complete resolution of the question of when the Shannon-type lower bound to the rate-distortion function of a source with memory is tight. The results are applied to generalize earlier results for balanced distortion measures and Markov sources to nonbalanced distortion measures and wide-sense Markov sources. As a special case, it is shown thatD_c > 0for all finite-alphabet autoregressive sources. As an example,R_{L} (D)is evaluated for the first-order ternary autoregressive source for a balanced (Hamming) and a nonbalanced (modular distance) distortion measure. A simple lower bound toD_cis derived for this example. Index Terms: Information rates Rate-distortion theory ----- Bound on the average transmission time for sequential estimation systems containing an additive Gaussian noise channel Kadota, T. Wyner, A. Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1971 On page(s): 514- 515 Volume: 17, Issue: 5 ISSN: 0018-9448 Abstract: We consider the class of sequential estimation systems containing additive Gaussian noise channels. Letmbe a random variable representing the source andx(t),y(t)be stochastic processes representing the signal and the channel output, respectively. Denote byhat{m}an estimate ofmbased on observingy(t)from 0 totau, wheretauis a random variable determined by a certain stopping rule of the decoder depending on a realization ofy. Letd(m,hat{m})be the distortion ofhat{m}relative tomandR(cdot)be the rate distortion function ofmwith respect to the distortion measured. Denote byP_oandN_othe available average signal power and the noise power level, respectively. We show thatE_{tau} geq (2 N_o / P_o)R. (Ed(m,hat{m}))and henceEd(m,hat{m}) geq R ^ {-1} (P_o E_ tau /2N_o ).. That is, given the average distortionEd(m,hat{m}), the average transmission time required can be no smaller than(2N_o/P_o)R(Ed(m,hat{m})). Conversely, given the average transmission timeE_{tau}, the average distortion can be no smaller thanR ^ {-1} (P_o E _ {tau} /2N_o). Index Terms: Gaussian processes Sequential estimation ----- Bounds on the rate-distortion function for stationary sources with memory Wyner, A. Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1971 On page(s): 508- 513 Volume: 17, Issue: 5 ISSN: 0018-9448 Abstract: In this paper, we study discrete-time stationary sourcesSwith memory. The rateR(beta)of the source relative to a distortion measure is compared withR^ ast (beta), the rate of the memoryless sourceS^ /astwith the same marginal statistics asS. We show thatR^ ast (beta) - Delta leq R(beta) leq R^ ast (beta), whereDeltais a measure of the memory of the source. A number of interesting applications of these bounds are given. Index Terms: Rate-distortion theory ----- Broadcast channels Cover, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1972 On page(s): 2- 14 Volume: 18, Issue: 1 ISSN: 0018-9448 Abstract: We introduce the problem of a single source attempting to communicate information simultaneously to several receivers. The intent is to model the situation of a broadcaster with multiple receivers or a lecturer with many listeners. Thus several different channels with a common input alphabet are specified. We shall determine the families of simultaneously achievable transmission rates for many extreme classes of channels. Upper and lower bounds on the capacity region will be found, and it will be shown that the family of theoretically achievable rates dominates the family of rates achievable by previously known time-sharing and maximin procedures. This improvement is gained by superimposing high-rate information on low-rate information. All of these results lead to a new approach to the compound channels problem. Index Terms: Broadcast channels Information rates ----- Rate-distortion theory for context-dependent fidelity criteria Berger, T. Weng Yu This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1972 On page(s): 378- 384 Volume: 18, Issue: 3 ISSN: 0018-9448 Abstract: 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. Index Terms: Rate-distortion theory ----- Some relations among RKHS norms, Fredholm equations, and innovations representations Kailath, T. Geesey, R. Weinert, H. Stanford University, Stanford, CA, USA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1972 On page(s): 341- 348 Volume: 18, Issue: 3 ISSN: 0018-9448 Abstract: We first show how reproducing kernel Hilbert space (RKHS) norms can be determined for a large class of covariance functions by methods based on the solution of a Riccati differential equation or a Wiener-Hopf integral equation. Efficient numerical algorithms for such equations have been extensively studied, especially in the control literature. The innovations representations enter in that it is they that suggest the form of the RKHS norms. From the RKHS norms, we show how recursive solutions can be obtained for certain Fredholm equations of the first kind that are widely used in certain approaches to detection theory. Our approach specifies a unique solution: moreover, the algorithms used are well suited to the treatment of increasing observation intervals. Index Terms: Covariance functions Hilbert spaces Innovations methods (stochastic processes) Integral equations Numerical methods Riccati equations Wiener-Hopf theory ----- Coding of sources with unknown statistics--I: Probability of encoding error Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1972 On page(s): 384- 389 Volume: 18, Issue: 3 ISSN: 0018-9448 Abstract: It is well known that it is often possible to obtain considerable data compression by encoding messages in long blocks. Usually the coding scheme for a specific source depends parametrically on the statistics of the source. Universal codes which are independent of the source statistics are introduced. These codes are shown to be asymptotically optimal in the sense that the probability of encoding error can be made vanishingly small for output rates no larger than those of optimal codes that do in fact depend on the statistics of the source. A particular universal coding scheme is introduced for which the encoding complexity increases no faster than the second power of the block lengthnand for which the encoding error vanishes exponentially withn. The discussion is limited to discrete-time finite-alphabet sources. Index Terms: Block codes Source coding ----- Coding of sources with unknown statistics--II: Distortion relative to a fidelity criterion Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1972 On page(s): 389- 394 Volume: 18, Issue: 3 ISSN: 0018-9448 Abstract: The encoding of sources with unknown statistics is considered. The average distortion that is obtained with universal coding schemes that are independent of the source statistics is shown to be asymptotically identical to the smallest average distortion that can be achieved with the best individual coding scheme (i.e., a code that is based on the specific statistics of the source). This result is shown to hold for any stationary source, as well as for a class of nonstationary sources. The discussion is limited to a certain important class of metric spaces. Index Terms: Rate-distortion theory Source coding ----- Algorithms for tree source coding with a fidelity criterion (Ph.D. Thesis abstr.) Anderson, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1972 On page(s): 543- 543 Volume: 18, Issue: 4 ISSN: 0018-9448 Abstract: Not Available Index Terms: Rate-distortion theory Tree codes ----- Computation of channel capacity and rate-distortion functions Blahut, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1972 On page(s): 460- 473 Volume: 18, Issue: 4 ISSN: 0018-9448 Abstract: By defining mutual information as a maximum over an appropriate space, channel capacities can be defined as double maxima and rate-distortion functions as double minima. This approach yields valuable new insights regarding the computation of channel capacities and rate-distortion functions. In particular, it suggests a simple algorithm for computing channel capacity that consists of a mapping from the set of channel input probability vectors into itself such that the sequence of probability vectors generated by successive applications of the mapping converges to the vector that achieves the capacity of the given channel. Analogous algorithms then are provided for computing rate-distortion functions and constrained channel capacities. The algorithms apply both to discrete and to continuous alphabet channels or sources. In addition, a formalization of the theory of channel capacity in the presence of constraints is included. Among the examples is the calculation of close upper and lower bounds to the rate-distortion function of a binary symmetric Markov source. Index Terms: Mutual information Rate-distortion theory ----- k_n-nearest neighbor classification Goldstein, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1972 On page(s): 627- 630 Volume: 18, Issue: 5 ISSN: 0018-9448 Abstract: Thek_nnearest neighbor classification rule is a nonparametric classification procedure that assigns a random vectorZto one of two populationspi_1, pi_2. Samples of equal sizenare taken frompi_1andpi_2and are ordered separately with respect to their distance fromZ = z. The rule assignsZtopi_1if the distance of thek_nth sample observation frompi_1tozis less than the distance of thek_nth sample observation frompi_2toz; otherwiseZis assigned topi_2. This rule is equivalent to the Fix and Hodges, "majority rule" [4] or the nearest neighbor rule of Cover and Hart [3]. This paper studies some asymptotic properties of this rule including an expression for a consistent upper bound on the probability of misclassification. Index Terms: Pattern classification ----- On the asymptotic eigenvalue distribution of Toeplitz matrices Gray, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1972 On page(s): 725- 730 Volume: 18, Issue: 6 ISSN: 0018-9448 Abstract: Since covariance matrices of weakly stationary random processes are Toeplitz, much of the theory involving asymptotic results for such processes is simply the theory of the asymptotic behavior of Toeplitz forms. The fundamental theorem of this type is the Szegö theorem on the asymptotic eigenvalue distribution of Toeplitz matrices. This theorem is often quoted but relatively little understood in the engineering literature. In this tutorial paper we prove the Szegiö theorem for the special case of finite-order Toeplitz matrices. In this setting the mathematical sophistication of the classical proofs is not required and the proof is both simple and intuitive--yet it contains the important concepts involved in the most general case. Index Terms: Toeplitz matrices ----- An RKHS approach to detection and estimation problems-- III: Generalized innovations representations and a likelihood-ratio formula Kailath, T. Duttweiler, D. Stanford University, Stanford, CA, USA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1972 On page(s): 730- 745 Volume: 18, Issue: 6 ISSN: 0018-9448 Abstract: The concept of a white Gaussian noise (WGN) innovations process has been used in a number of detection and estimation problems. However, there is fundamentally no special reason why WGN should be preferred over any other process, say, for example, an nth-order stationary autoregressive process. In this paper, we show that by working with the proper metric, any Gaussian process can be used as the innovations process. The proper metric is that of the associated reproducing kernel Hilbert space. This is not unexpected, but what is unexpected is that in this metric some basic concepts, like that of a causal operator and the distinction between a causal and a Volterra operator, have to be carefully reexamined and defined more precisely and more generally. It is shown that if the problem of deciding between two Gaussian processes is nonsingular, then there exists a causal (properly defined) and causally invertible transformation between them. Thus either process can be regarded as a generalized innovations process. As an application, it is shown that the likelihood ratio (LR) for two arbitrary Gaussian processes can, when it exists, be written in the same form as the LR for a known signal in colored Gaussian noise. This generalizes a similar result obtained earlier for white noise. The methods of Gohberg and Krein, as specialized to reproducing kernel spaces, are heavily used. Index Terms: Estimation Gaussian processes Hilbert spaces Innovations methods (stochastic processes) Signal detection Signal estimation ----- RKHS approach to detection and estimation problems--IV: Non-Gaussian detection Duttweiler, D. Kailath, T. AT&T Bell Labs., Holmdel, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1973 On page(s): 19- 28 Volume: 19, Issue: 1 ISSN: 0018-9448 Abstract: We introduce the reproducing-kernel Hilbert space (RKHS) associated with the characteristic functional of a random process and use it to develop a general RKHS theory for non-Gaussian detection. Previously known results for choosing between processes with Gaussian and Poisson statistics are obtained as specializations of this theory. Index Terms: Hilbert spaces Signal detection Stochastic processes ----- Editorial Forney, G., Jr. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1973 On page(s): 2- 2 Volume: 19, Issue: 1 ISSN: 0018-9448 Abstract: Not Available Index Terms: Information theory ----- RKHS approach to detection and estimation problems--V: Parameter estimation Duttweiler, D. Kailath, T. AT&T Bell Labs., Holmdel, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1973 On page(s): 29- 37 Volume: 19, Issue: 1 ISSN: 0018-9448 Abstract: Using reproducing-kernel Hilbert space (RKHS) techniques, we obtain new results for three different parameter estimation problems. The new results are 1) an explicit formula for the minimum-variance unbiased estimate of the arrival time of a step function in white Gaussian noise, 2) a new interpretation of the Bhattacharyya bounds on the variance of an unbiased estimate of a function of regression coefficients, and 3) a concise formula for the Cramér-Rao bound on the variance of an unbiased estimate of a parameter determining the covariance of a zero-mean Gaussian process. Index Terms: Hilbert spaces Parameter estimation Stochastic processes ----- The random coding bound is tight for the average code (Corresp.) Gallager, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1973 On page(s): 244- 246 Volume: 19, Issue: 2 ISSN: 0018-9448 Abstract: The random coding bound of information theory provides a well-known upper bound to the probability of decoding error for the best code of a given rate and block length. The bound is constructed by upper-bounding the average error probability over an ensemble of codes. The bound is known to give the correct exponential dependence of error probability on block length for transmission rates above the critical rate, but it gives an incorrect exponential dependence at rates below a second lower critical rate. Here we derive an asymptotic expression for the average error probability over the ensemble of codes used in the random coding bound. The result shows that the weakness of the random coding bound at rates below the second critical rate is due not to upperbounding the ensemble average, but rather to the fact that the best codes are much better than the average at low rates. Index Terms: Coding Decoding ----- Random coding theorem for broadcast channels with degraded components Bergmans, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1973 On page(s): 197- 207 Volume: 19, Issue: 2 ISSN: 0018-9448 Abstract: This paper generalizes Cover's results on broadcast channels with two binary symmetric channels (BSC) to the class of degraded channels withNcomponents. A random code, and its associated decoding scheme, is shown to have expected probability of error going to zero for all components simultaneously as the codeword length goes to infinity, if the point representing the rates to the various receivers falls in the set of achievable rates described by this paper. A procedure to expurgate a good random broadcast code is given, leading to a bound on the maximum probability of error. Binary symmetric broadcast channels always fall in the class of degraded broadcast channels. The results of the paper are applied to this class of channels of potential practical importance. Index Terms: Broadcast channels Coding Memoryless channels ----- An algorithm for optimal prefix parsing of a noiseless and memoryless channel Lempel, A. Even, S. Cohn, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1973 On page(s): 208- 214 Volume: 19, Issue: 2 ISSN: 0018-9448 Abstract: We discuss the prefix encoding of aQ-ary source(Q geq 2)into anL-symbol channel alphabet withL geq Q. We present an optimal encoding scheme that minimizes the expected cost per symbol in the case of equally probable source symbols and arbitrary channel symbol costs. Index Terms: Coding Memoryless channels Source coding ----- Time, frequency, sequency, and their uncertainty relations (Corresp.) Pearl, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1973 On page(s): 225- 229 Volume: 19, Issue: 2 ISSN: 0018-9448 Abstract: We study the form assumed by the classical time-frequency uncertainty relations in discrete as well as nontrigonometric spectral analysis. In particular we find that if anN-sample time signal is to contain a fractiongammaof its energy inTconsecutive samples, then the minimum number of frequency components containing that same energy fraction must be greater thanN/T(2gamma - 1)^2. It is also found that the discrete Walsh transform permits greater energy concentration (less uncertainty) than the discrete Fourier transform. Index Terms: DFT Discrete Fourier transforms (DFT's) Spectral analysis Walsh transforms ----- Information rates for Poisson sequences Rubin, I. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1973 On page(s): 283- 294 Volume: 19, Issue: 3 ISSN: 0018-9448 Abstract: The rate-distortion function of a Poisson sequence, under a single-letter magnitude-error distortion measure is derived and studied. Simple approximations to the rate-distortion curve for low and high distortions are obtained. A useful lower bound to this curve is derived and an upper bound is generated by a simple instrumentable coding scheme. The rate-distortion relationship for the latter is seen to be nearly ideal over a large distortion region. Index Terms: Poisson processes Rate-distortion theory ----- On the converse to the coding theorem for discrete memoryless channels (Corresp.) Arimoto, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1973 On page(s): 357- 359 Volume: 19, Issue: 3 ISSN: 0018-9448 Abstract: A new lower bound on the probability of decoding error for the case of rates above capacity is presented. It forms a natural companion to Gallager's random coding bound for rates below capacity. The strong converse to the coding theorem follows immediately from the proposed lower bound. Index Terms: Decoding Memoryless channels ----- On functionals satisfying a data-processing theorem Ziv, J. Zakai, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1973 On page(s): 275- 283 Volume: 19, Issue: 3 ISSN: 0018-9448 Abstract: It is shown that the rate-distortion bound(R(d) leq C)remains true when-log xin the definition of mutual information is replaced by an arbitrary concave(cup)nonincreasing function satisfying some technical conditions. Examples are given showing that for certain choices of the concave functions, the bounds obtained are better than the classical rate-distortion bounds. Index Terms: Mutual information Rate-distortion theory ----- The Barankin bound: A geometric interpretation (Corresp.) Albuquerque, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1973 On page(s): 559- 561 Volume: 19, Issue: 4 ISSN: 0018-9448 Abstract: It is well known that the Barankin bound is locally the tightest lower bound on the variance of any unbiased estimator. If the minimum-variance unbiased-parameter estimation problem is viewed as a minimum-norm problem in an appropriate Hilbert space, the Barankin bound has a very simple geometric interpretation. This interpretation also gives some insight into the influence of bias on the estimation error. Index Terms: Parameter estimation ----- A coding theorem for discrete-time sources Omura, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1973 On page(s): 490- 498 Volume: 19, Issue: 4 ISSN: 0018-9448 Abstract: We present a new derivation of the source coding theorem for discrete-time sources. This proof parallels Gallager's [1] derivation of the random coding bound for channel coding theory and shows that the classical random coding exponent also emerges as a critical quantity for source coding. The major advantage of this approach is the simplicity of the derivation and its close relationship to the more familiar channel coding theory. The source coding theorem we derive here also yields a natural bound on the rate of convergence to the rate-distortion limit. Index Terms: Source coding ----- A new class of lower bounds to information rates of stationary sources via conditional rate-distortion functions Gray, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1973 On page(s): 480- 489 Volume: 19, Issue: 4 ISSN: 0018-9448 Abstract: A new class of lower bounds to rate-distortion functions of stationary processes with memory and single-letter vector-valued distortion measures is derived. This class is shown to include or imply all other well-known lower bounds to rates of such sources and distortion measures. The derivation is based on the definition and properties of the conditional rate-distortion function. In addition to providing a unified and intuitive approach to lower bounds, this approach yields several interesting relations among conditional, joint, and marginal rates that are similar to and sometimes identical with the analogous relations among the corresponding entropies. Index Terms: Rate-distortion theory ----- Noiseless coding of correlated information sources Slepian, D. Wolf, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1973 On page(s): 471- 480 Volume: 19, Issue: 4 ISSN: 0018-9448 Abstract: Correlated information sequencescdots ,X_{-1},X_0,X_1, cdotsandcdots,Y_{-1},Y_0,Y_1, cdotsare generated by repeated independent drawings of a pair of discrete random variablesX, Yfrom a given bivariate distributionP_{XY} (x,y). We determine the minimum number of bits per characterR_XandR_Yneeded to encode these sequences so that they can be faithfully reproduced under a variety of assumptions regarding the encoders and decoders. The results, some of which are not at all obvious, are presented as an admissible rate regionmathcal{R}in theR_X - R_Yplane. They generalize a similar and well-known result for a single information sequence, namelyR_X geq H (X)for faithful reproduction. Index Terms: Source coding ----- Bounds on rate-distortion functions for stationary sources and context-dependent fidelity criteria (Corresp.) Leiner, B. Gray, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1973 On page(s): 706- 708 Volume: 19, Issue: 5 ISSN: 0018-9448 Abstract: A class of lower bounds to rate-distortion functions of stationary sources with context-dependent fidelity criteria is derived by mapping the source and distortion measure into an equivalent restricted-transition stationary source with a single-letter fidelity criterion, and then applying the composite bound. This approach is seen to yield bounds which, although sometimes quite loose, apply to general stationary sources and context-dependent fidelity criteria. Two examples are presented. Index Terms: Rate-distortion theory ----- A theorem on the entropy of certain binary sequences and applications--I Wyner, A. Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1973 On page(s): 769- 772 Volume: 19, Issue: 6 ISSN: 0018-9448 Abstract: In this, the first part of a two-part paper, we establish a theorem concerning the entropy of a certain sequence of binary random variables. In the sequel we will apply this result to the solution of three problems in multi-user communication, two of which have been open for some time. Specifically we show the following. LetXandYbe binary randomn-vectors, which are the input and output, respectively, of a binary symmetric channel with "crossover" probabilityp_0. LetH{X}andH{ Y}be the entropies ofXandY, respectively. Then begin{equation} begin{split} frac{1}{n} H{X} geq h(alpha_0), qquad 0 leq alpha_0 &leq 1, Rightarrow \ qquad qquad &qquad frac{1}{n}H{Y} geq h(alpha_0(1 - p_0) + (1 - alpha_0)p_0) end{split} end{equation} whereh(lambda) = -lambda log lambda - (1 - lambda) log(l - lambda), 0 leq lambda leq 1. Index Terms: Entropy functions Random variables Sequences ----- A theorem on the entropy of certain binary sequences and applications--II Wyner, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1973 On page(s): 772- 777 Volume: 19, Issue: 6 ISSN: 0018-9448 Abstract: In this, the second part of a two-part paper, we apply the result of Part I [9] to three problems in multi-user communication. 1) For the special case of the broadcast channel where both channels are binary symmetric, we establish a converse result that shows the ad hoc scheme suggested by Cover and Bergmans [2], [3l is in fact optimal. 2) For a modified version of a source coding problem with side information of Slepian and Wolf [3], we establish a converse result. 3) We show that the "common information" of a certain pair of dependent random variables is zero. Index Terms: Broadcast channels Entropy functions Information rates Multiuser channels Random variables Sequences Source coding ----- Two-step encoding for finite sources Korner, J. Longo, G. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1973 On page(s): 778- 782 Volume: 19, Issue: 6 ISSN: 0018-9448 Abstract: Any finite information source is given a graph structure, in which two vertices are adjacent whenever the two corresponding source letters are distinguishable by the coder-decoder pair. Usual sources correspond, therefore, to complete graphs. If the associated graph is not complete, however, anvarepsilon-code for the source can be constructed in two steps: in the first, distinct codewords are given to distinguishable letters only; in the second step, a similar encoding is carried out for the complementary graph, in which distinguishable letters become indistinguishable and the converse. A particularly simple case shows up when nonadjacency is an equivalence relation among the vertices of the graph: each class of nondistinguishable letters can then be considered as a letter in a coarser source alphabet. The two-step procedure is then particularly intuitive. A problem arises when this procedure does not destroy optimality of the resultingvarepsilon-code; some partial results are given in this direction. The results obtained are largely based on some graph-theoretical ideas and tools. Index Terms: Graph theory Source coding ----- On the computation of rate-distortion functions (Corresp.) Csiszar, I. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1974 On page(s): 122- 124 Volume: 20, Issue: 1 ISSN: 0018-9448 Abstract: In a recent paper [1], Blahut suggested an efficient algorithm for computing rate-distortion functions. In this correspondence we show that the sequence of distributions used in that algorithm has a limit yielding a point on theR(d)curve if the reproducing alphabet is finite, and we obtain a similar but weaker result for countable reproducing alphabets. Index Terms: Rate-distortion theory ----- Tree encoding for symmetric sources with a distortion measure Gallager, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1974 On page(s): 65- 76 Volume: 20, Issue: 1 ISSN: 0018-9448 Abstract: A simple algorithm is developed for mapping the outputs of a source into the set of code sequences generated by a tree code. The algorithm is analyzed for a special case in which the source produces discrete independent equiprobable letters, and the distortion measure satisfies a symmetry condition. LettingRbe the code rate andD^{ast}be the minimum average distortion for that rate as given by Shannon's rate-distortion theorem, we show that the algorithm is capable of achieving average distortion as close toD^{ast}as desired. Furthermore an upper bound is developed on the average amount of computation for the algorithm. Asymptotically as the average distortionapproaches the theoretical limitD^{ast}, the bound on average computation has the formexp [a/ sqrt{ - D^{ast} }]for some constanta. Index Terms: Rate-distortion theory Tree codes ----- Recent results in the Shannon theory Wyner, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1974 On page(s): 2- 10 Volume: 20, Issue: 1 ISSN: 0018-9448 Abstract: The first part of this paper consists of short summaries of recent work in five rather traditional areas of the Shannon theory, namely: 1) source and channel coding theorems for new situations; 2) calculation of source rate and channel capacity; 3) channel coding with feedback; 4) source coding; 5) universal coding. The second part of thc paper consists of a relatively detailed discussion of some aspects of the area that the author considers to be the most dynamic and exciting in the Shannon theory: multiple-user communication. The discussion here includes "multiple-access channels," "broadcast channels," and various source coding problems with multiple-user constraints. Index Terms: Bibliographies Coding Information theory Source coding ----- Information rates and data-compression schemes for Poisson processes Rubin, I. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1974 On page(s): 200- 210 Volume: 20, Issue: 2 ISSN: 0018-9448 Abstract: In this paper, we derive rate-distortion functions under proper magnitude-error fidelity criteria and study instrumentable data-compression schemes for Poisson processes. In particular, we derive information rates and obtain rate-distortion relationships for practical data-compression schemes, for the reproduction of the unordered sequence of Poisson event occurrences, for the reproduction of the sample functions of the Poisson counting process, and for the reproduction of the sequence of intervals between the event occurrences of a Poisson process. The reproducing processes are taken to be point (or jump) processes themselves. The performances of the various data-compression schemes presented here are compared with those of the ideal schemes (us presented by the rate-distortion functions) and are shown to be close to the latter over wide regions of distortion. Index Terms: Data compression Poisson processes Rate-distortion theory ----- A stack algorithm for source coding with a fidelity criterion Anderson, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1974 On page(s): 211- 226 Volume: 20, Issue: 2 ISSN: 0018-9448 Abstract: A new scheme for encoding source information with respect to a fidelity criterion by tree codes is analyzed. Taking its design from earlier stack sequential decoders for channels, the algorithm keeps a stack of code tree paths of variable lengths ordered by a metric. It repeatedly extends the topmost path and reorders, until the topmost rises above a given metricA. The analysis uses difference equations, both linear and nonlinear; a commonly occurring nonlinear equation is solved asymptotically for the first time. The distribution of the worst metric to appear at the stack top is found to fall off faster than exponentially below a specifiable metric, whenever the encoder performance lies above the rate-distortion limit. Next, development of the top path is found to follow asymptotically a certain trajectory in the length-metric plane; this leads to a tight bound on path length released at termination. Finally, difference equations are written to bound the nodes searched. The work concludes with numerical calculations and simulations for the binary lid source with Hamming distortion measure. Comparison is made to other algorithms. Index Terms: Not Available ----- On theepsilon-entropy of certain Gaussian processes Binia, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1974 On page(s): 190- 196 Volume: 20, Issue: 2 ISSN: 0018-9448 Abstract: A condition on the eigenvalues of two Gaussian processes is given that is sufficient for the boundedness of the difference of theirvarepsilon-entropies. It is also proved that the difference between thevarepsilon-entropies of two strongly equivalent Gaussian processes is bounded. The relation between thevarepsilon-entropies of equivalent (or strongly equivalent) Gaussian processes is used for obtaining the asymptotic behavior (asvarepsilongoes to zero) of thevarepsilon-entropy of certain processes. Index Terms: Entropy functions Gaussian processes ----- Cooperative broadcasting Bergmans, P. Cover, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1974 On page(s): 317- 324 Volume: 20, Issue: 3 ISSN: 0018-9448 Abstract: This paper shows that several transmitters operating in an additive white Gaussian noise environment can send at rates strictly dominating time-multiplex and frequency-multiplex rates by use of a superposition scheme that pools the time, bandwidth, and power allocations of the transmitters. This pooling can be achieved without cooperative action, except for agreement on the actual rate of transmission each transmitter will allow itself. The superposition scheme involves subtraction from the received signal of the estimated signals sent by the other transmitters, followed by decoding of the intended signal. This scheme has been shown to be optimal. We conclude that present methods of allocating different frequency bands to different transmitters are necessarily suboptimal. Index Terms: Broadcast channels Frequency-division multiplexing (FDM) Multiplexing Time-division multiplexing ----- Source coding theorems without the ergodic assumption Gray, R. Davisson, L. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1974 On page(s): 502- 516 Volume: 20, Issue: 4 ISSN: 0018-9448 Abstract: Source coding theorems are proved for discrete-time stationary processes subject to a fidelity criterion. The alphabet of the process is assumed to be a separable metric space, but the process is not assumed to be ergodic. When the process is not ergodic, the minimum average distortion for a fixed-rate code is not given by the distortion-rate function of the source as usually defined. It is given instead by a weighted average of the distortion-rate functions of ergodic subsources comprising the ergodic decomposition of the source. Potential applications to universal source coding with a fidelity criterion are discussed. Index Terms: Source coding ----- On theepsilon-entropy and the rate-distortion function of certain non-Gaussian processes Binia, J. Zakai, M. Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1974 On page(s): 517- 524 Volume: 20, Issue: 4 ISSN: 0018-9448 Abstract: Letxi = {xi(t), 0 leq t leq T}be a process with covariance functionK(s,t)andE int_0^T xi^2(t) dt < infty. It is proved that for everyvarepsilon > 0thevarepsilon-entropyH_{varepsilon}(xi)satisfies begin{equation} H_{varepsilon}(xi_g) - mathcal{H}_{xi_g} (xi) leq H_{varepsilon}(xi) leq H_{varepsilon}(xi_g) end{equation} wherexi_gis a Gaussian process with the covarianeeK(s,t)andmathcal{H}_{xi_g}(xi)is the entropy of the measure induced byxi(in function space) with respect to that induced byxi_g. It is also shown that ifmathcal{H}_{xi_g}(xi) < inftythen, asvarepsilon rightarrow 0begin{equation} H_{varepsilon}(xi) = H_{varepsilon}(xi_g) - mathcal{H}_{xi_g}(xi) + o(1). end{equation} Furthermore, ff there exists a Gaussian processg = { g(t); 0 leq t leq T }such thatmathcal{H}_g(xi) < infty, then the ratio betweenH_{varepsilon}(xi)andH_{varepsilon}(g)goes to one asvarepsilongoes to zero. Similar results are given for the rate-distortion function, and some particular examples are worked out in detail. Some cases for whichmathcal_{xi_g}(xi) = inftyare discussed, and asymptotic bounds onH_{varepsilon}(xi), expressed in terms ofH_{varepsilon}(xi_g), are derived. Index Terms: Entropy functions Rate-distortion theory ----- Hypothesis testing and information theory Blahut, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1974 On page(s): 405- 417 Volume: 20, Issue: 4 ISSN: 0018-9448 Abstract: The testing of binary hypotheses is developed from an information-theoretic point of view, and the asymptotic performance of optimum hypothesis testers is developed in exact analogy to the asymptotic performance of optimum channel codes. The discrimination, introduced by Kullback, is developed in a role analogous to that of mutual information in channel coding theory. Based on the discrimination, an error-exponent functione(r)is defined. This function is found to describe the behavior of optimum hypothesis testers asymptotically with block length. Next, mutual information is introduced as a minimum of a set of discriminations. This approach has later coding significance. The channel reliability-rate functionE(R)is defined in terms of discrimination, and a number of its mathematical properties developed. Sphere-packing-like bounds are developed in a relatively straightforward and intuitive manner by relatinge(r)andE (R). This ties together the aforementioned developments and gives a lower bound in terms of a hypothesis testing model. The result is valid for discrete or continuous probability distributions. The discrimination function is also used to define a source code reliability-rate function. This function allows a simpler proof of the source coding theorem and also bounds the code performance as a function of block length, thereby providing the source coding analog ofE (R). Index Terms: Block codes Decision procedures Decoding Information theory Source coding ----- Rate-distortion functions for nonhomogeneous Poisson processes (Corresp.) Rubin, I. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1974 On page(s): 669- 672 Volume: 20, Issue: 5 ISSN: 0018-9448 Abstract: Information rates for nonhomogeneous Poisson counting processes are derived. A source coding theorem is proved and rate-distortion functions are obtained for the reconstruction of the sample functions of the latter sources. Distortion measures which depend upon the magnitude of the error as well as on a temporal weighting function proportional to the instantaneous intensity of the source are assumed. The analysis utilizes recent results concerning information rates for homogeneous Poisson processes and appropriate time-scale transformations, which map the source sample functions into an isometric induced source. Index Terms: Poisson processes Rate-distortion theory ----- Rate-distortion theory for ergodic sources with side information (Corresp.) Leiner, B. Gray, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1974 On page(s): 672- 675 Volume: 20, Issue: 5 ISSN: 0018-9448 Abstract: The definition of the rate-distortion function is extended to the case of a stationary-ergodic source with side information, and the appropriate coding theorem is proved. Inequalities between the joint, marginal, and conditional rate-distortion functions for ergodic processes are given, and their implications in terms of universal coding are discussed. Index Terms: Rate-distortion theory ----- Entropy inequalities for discrete channels Witsenhausen, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1974 On page(s): 610- 616 Volume: 20, Issue: 5 ISSN: 0018-9448 Abstract: The sharp lower boundf(x)on the per-symbol output entropy for a given per-symbol input entropyxis determined for stationary discrete memoryless channels; it is the lower convex envelope of the boundg(x)for a single channel use. The bounds agree for all noiseless channels and all binary channels. However, for nonbinary channels,gis not generally convex so that the bounds differ. Such is the case for the Hamming channels that generalize the binary symmetric channels. The bounds are of interest in connection with multiple-user communication, as exemplified by Wyner's applications of "Mrs. Gerber's lemma" (the bound for binary symmetric channels first obtained by Wyner and Ziv). These applications extend from the binary symmetric case to the. Hamming case. Doubly stochastic channels are characterized by the property of never decreasing entropy. Index Terms: Entropy functions Memoryless channels ----- Regular jump processes and their information processing Rubin, I. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1974 On page(s): 617- 624 Volume: 20, Issue: 5 ISSN: 0018-9448 Abstract: A class of regular jump processes (RJP's) is introduced. An RJP is described in terms of the intensity function of its associated stochastic point process and the state-transition density of its embedded random-state sequence. Expressions for the joint occurrence statistics of these processes are derived. Assuming that an information stochastic process causally modulates an observed RJP, we obtain the joint occurrence statistics of the resulting compound jump processes. We show the latter to incorporate appropriately the causal MMSE estimate of the conditional intensities and state-transition functions. The results are used to derive a general likelihood-ratio formula for information processing of RJP's. A separation is observed between the likelihood processor of the point process associated with the observed RJP and the processor associated with the embedded stochastic state sequence. Considering the detection of RJP's with uncertain (statistically known) probability measures, we obtain the optimal Bayes receiver as the appropriate compound likelihood processor and thus exhibit separation between the detection and filtering operations. Index Terms: Filtering Jump processes Parameter estimation Signal detection maximum-likelihood (ML) estimation ----- Rate-distortion theory for sources with side information (Ph.D. Thesis abstr.) Leiner, B. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1974 On page(s): 694- 694 Volume: 20, Issue: 5 ISSN: 0018-9448 Abstract: Not Available Index Terms: Rate-distortion theory ----- Statistical inference for space-time point processes (D.Sc. Thesis abstr.) Fishman, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1974 On page(s): 771- 771 Volume: 20, Issue: 6 ISSN: 0018-9448 Abstract: Not Available Index Terms: Multidimensional signal processing Point processes ----- The capacity region of a multiple-access discrete memoryless channel can increase with feedback (Corresp.) Gaarder, N. Wolf, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1975 On page(s): 100- 102 Volume: 21, Issue: 1 ISSN: 0018-9448 Abstract: The capacity of a single-input single-output discrete memoryless channel is not increased by the use of a noiseless feedback link. It is shown, by example, that this is not the case for a multiple-access discrete memoryless channel. That is, it is shown that the capacity region for such a channel is enlarged if a noiseless feedback link is utilized. Index Terms: Feedback communication Memoryless channels Multiple-access communications ----- An RKHS approach to detection and estimation problems--II: Gaussian signal detection Kailath, T. Weinert, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1975 On page(s): 15- 23 Volume: 21, Issue: 1 ISSN: 0018-9448 Abstract: The theory of reproducing kernel Hilbert spaces is used to obtain a simple but formal expression for the likelihood ratio (LR) for discriminating between two Gaussian processes with unequal covariances, and to develop a test by which the formal expression can be checked for validity. This LR formula can be evaluated by working separately with each covariance, thus reducing the calculations for the random signal case to those for the simpler known signal problem. In contrast, all previous LR formulas for the unequal covariance problem seem to require calculations involving both covariances simultaneously. Index Terms: Gaussian processes Hilbert spaces Signal detection Signal estimation ----- Evaluation of rate-distortion functions for a class of independent identically distributed sources under an absolute-magnitude criterion Tan, H. Kung Yao This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1975 On page(s): 59- 64 Volume: 21, Issue: 1 ISSN: 0018-9448 Abstract: The explicit evaluation of the rate-distortion functionR(D)for continnous-amplitude sources when it is strictly greater than its Shannon lower bound has been previously considered a formidable task. This is the case for independent identically distributed (i.i.d.) Gaussian sources under an absolute-magnitude distortion criterion. In this paper, we provide a method that yields the explicit evaluation ofR(D)for this case. This method is then shown to be applicable to the evaluation of the absolute-magnitude-criterionR(D)for a large class of i.i.d, sources having probability densities with constrained tail decay. Other applications are discussed. Index Terms: Rate-distortion theory ----- The common information of two dependent random variables Wyner, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1975 On page(s): 163- 179 Volume: 21, Issue: 2 ISSN: 0018-9448 Abstract: The problem of finding a meaningful measure of the "common information" or "common randomness' of two discrete dependent random variablesX,Yis studied. The quantityC(X; Y)is defined as the minimum possible value ofI(X, Y; W)where the minimum is taken over all distributions defining an auxiliary random variableW in mathcal{W}, a finite set, such thatX, Yare conditionally independent givenW. The main result of the paper is contained in two theorems which show thatC(X; Y)is i) the minimumR_0such that a sequence of independent copies of(X,Y)can be efficiently encoded into three binary streamsW_0, W_1,W_2with ratesR_0,R_1,R_2, respectively,[sum R_i = H(X, Y)]andXrecovered from(W_0, W_1), andYrecovered from(W_0, W_2), i.e.,W_0is the common stream; ii) the minimum binary rateRof the common input to independent processors that generate an approximation toX,Y. Index Terms: Information rates Random variables Source coding ----- Random coding theorems for the general discrete memoryless broadcast channel van der Meulen, E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1975 On page(s): 180- 190 Volume: 21, Issue: 2 ISSN: 0018-9448 Abstract: Three different communication situations are considered for the general nondegraded discrete memoryless broadcast channel with two components. In the most general situation, common and separate information is sent to both receivers. In another situation, only separate information is sent, and in a third, one Common and one separate message is sent. For each communication situation a random coding inner bound on the capacity region is derived. An example is presented which Shows that in the most general situation the inner bound strictly dominates the family of rates obtained by time-sharing. The capacity region for the general situation is characterized by a limiting expression. The relationship with the degraded broadcast channel and the connection with other multiway channels, such as the channel with two senders and two receivers, is shown. Index Terms: Broadcast channels Coding Memoryless channels ----- A proof of the data compression theorem of Slepian and Wolf for ergodic sources (Corresp.) Cover, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1975 On page(s): 226- 228 Volume: 21, Issue: 2 ISSN: 0018-9448 Abstract: If{(X_i, Y_i)}_{i=1}^{infty}is a sequence of independent identically distributed discrete random pairs with(X_i, Y_i) ~ p(x,y), Slepian and Wolf have shown that theXprocess and theYprocess can be separately described to a common receiver at ratesR_XandR_Yhits per symbol ifR_X + R_Y > H(X,Y), R_X > H(XmidY), R_Y > H(YmidX). A simpler proof of this result will be given. As a consequence it is established that the Slepian-Wolf theorem is true without change for arbitrary ergodic processes{(X_i,Y_i)}_{i=1}^{infty}and countably infinite alphabets. The extension to an arbitrary number of processes is immediate. Index Terms: Data compression Source coding ----- On source coding with side information at the decoder Wyner, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1975 On page(s): 294- 300 Volume: 21, Issue: 3 ISSN: 0018-9448 Abstract: Let{(X_k, Y_k, V_k)}_{k=1}^{infty}be a sequence of independent copies of the triple(X,Y,V)of discrete random variables. We consider the following source coding problem with a side information network. This network has three encoders numbered 0, 1, and 2, the inputs of which are the sequences{ V_k}, {X_k}, and{Y_k}, respectively. The output of encoder i is a binary sequence of rateR_i, i = 0,1,2. There are two decoders, numbered 1 and 2, whose task is to deliver essentially perfect reproductions of the sequences{X_k}and{Y_k}, respectively, to two distinct destinations. Decoder 1 observes the output of encoders 0 and 1, and decoder 2 observes the output of encoders 0 and 2. The sequence{V_k}and its binary encoding (by encoder 0) play the role of side information, which is available to the decoders only. We study the characterization of the family of rate triples(R_0,R_1,R_2)for which this system can deliver essentially perfect reproductions (in the usual Shannon sense) of{X_k}and{Y_k}. The principal result is a characterization of this family via an information-theoretic minimization. Two special cases are of interest. In the first,V = (X, Y)so that the encoding of{V_k }contains common information. In the second,Y equiv 0so that our problem becomes a generalization of the source coding problem with side information studied by Slepian and Wo1f [3]. Index Terms: Source coding ----- Worst sources and robust codes for difference distortion measures Sakrison, D. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1975 On page(s): 301- 309 Volume: 21, Issue: 3 ISSN: 0018-9448 Abstract: It has long been known that for a mean-square error distortion measure the Gaussian distribution requires the largest rate of all sources of a given variance. It has also been stated that a code designed for the Gaussian source and yielding distortiondwhen used with a Gaussian source will yield distortionleq dwhen used with any independent-letter source of the same variance. In this paper, we extend these results in two directions: a) instead of assuming that the source has a fixed variance, we fix an arbitrary moment; b) instead of mean-square error distortion measures, we consider nearly arbitrary continuous difference distortion measures. For each moment constraint, we show that there is a given distribution that has the largest rate for (nearly) any difference distortion measure and that a code designed for this source yielding distortiondyields distortionleq dfor any ergodic source satisfying the same moment constraint. Furthermore, digital encoding of the output of this encoder may yield a lower rate when this encoder is used with a source for which it was not designed. We also extend these results to the case of a random process or random field of known correlation function under a difference distortion measure. Index Terms: Rate-distortion theory Source coding ----- An achievable rate region for the broadcast channel Cover, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1975 On page(s): 399- 404 Volume: 21, Issue: 4 ISSN: 0018-9448 Abstract: Letp(y_1, y_2 mid x)denote a discrete memoryless channel with a single sourceXand two independent receiversY_1andY_2. We exhibit an achievable region of rates(R_{11},R_{12},R_{22})at which independent information can be sent, respectively, to receiver 1, to both receivers 1 and 2, and to receiver 2. The achievability of the region is shown by using a version of the asymptotic equipartition property involving many simultaneous "typicality" constraints. These results immediately generalize to yield an achievable rate region for them-sendern-receiver channel in terms of standard mutual information quantities. Index Terms: Broadcast channels Coding ----- A conditional entropy bound for a pair of discrete random variables Witsenhausen, H. Wyner, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1975 On page(s): 493- 501 Volume: 21, Issue: 5 ISSN: 0018-9448 Abstract: LetX, Ybe a pair of discrete random variables with a given joint probability distribution. For0 leq x leq H(X), the entropy ofX, define the functionF(x)as the infimum ofH(Ymid W), the conditional entropy ofYgivenW, with respect to all discrete random variablesWsuch that a)H(Xmid W) = x, and b)WandYare conditionally independent givenX. This paper concerns the functionF, its properties, its calculation, and its applications to several problems in information theory. Index Terms: Entropy functions Random variables ----- Information-singular random processes Berger, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1975 On page(s): 502- 511 Volume: 21, Issue: 5 ISSN: 0018-9448 Abstract: 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. Index Terms: Source coding Stochastic processes ----- Process definitions of distortion-rate functions and source coding theorems Gray, R. Neuhoff, D. Omura, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1975 On page(s): 524- 532 Volume: 21, Issue: 5 ISSN: 0018-9448 Abstract: The standard definition of the distortion-rate function involves a limit of information-tbeoretic minimizations over distributions of random vectors. Several alternative definitions, each involving a single minimization over random processes, are presented here and verified. These definitions parallel Khinchine's process definition of channel capacity, provide a new interpretation of block and nonblock source coding (with a fidelity criterion) theorems in terms of optimal stochastic codes, and provide a comparison between the optimal performance theoretically attainable (OPTA) using block and nonblock source codes. Coupling the process definitions with recently developed bounding techniques provides a new and simple proof of the block source coding theorem for ergodic sources. Index Terms: Rate-distortion theory ----- How to track a swarm of fireflies by observing their flashes (Corresp.) Snyder, D. Fishman, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1975 On page(s): 692- 695 Volume: 21, Issue: 6 ISSN: 0018-9448 Abstract: In this correspondence, we examine the problem of estimating the centroid of a normally shaped intensity function of a time-space point process in terms of an observed realization of the point process. The centroid is assumed to move randomly as a projection of a Gauss-Markov process. We find that the centroid is conditionally normal given the observations. Dynamical equations are given for the conditional mean and covariance of the centroid. The resulting filter is nonlinear, but closely related to the continuous-discrete Kalman-Bucy filter. An application to optical position sensing is given. Index Terms: Estimation Insects Point processes Tracking ----- Source coding with side information and a converse for degraded broadcast channels Ahlswede, R. Korner, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1975 On page(s): 629- 637 Volume: 21, Issue: 6 ISSN: 0018-9448 Abstract: Let{(X_i, Y_i,)}_{i=1}^{infty}be a memoryless correlated source with finite alphabets, and let us imagine that one person, encoder 1, observes onlyX^n = X_1,cdots,X_nand another person, encoder 2, observes onlyY^n = Y_1,cdots,Y_n. The encoders can produce encoding functionsf_n(X^n)andg_n(Y^n)respectively, which are made available to the decoder. We determine the rate region in case the decoder is interested only in knowingY^n = Y_1,cdots,Y_n(with small error probability). In Section H of the paper we give a characterization of the capacity region for degraded broadcast channels (DBC's), which was conjectured by Bergmans [11] and is somewhat sharper than the one obtained by Gallager [12]. Index Terms: Broadcast channels Source coding ----- On the inverse problem of entropy maximizations (Corresp.) Noonan, J. Tzannes, N. Costello, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1976 On page(s): 120- 123 Volume: 22, Issue: 1 ISSN: 0018-9448 Abstract: The inverse isoperimetric problem of the entropy functional is considered in this Correspondence. This problem can be stated as follows: Given a known probability density function (pdf), what prior constraints are needed in order for this pdf to be the one that maximizes the entropy functional? The solution is given in terms of a Theorem, and it is compared to the Rozenberg-Rubichev solution. The Theorem is also used in simple applications, one of which illuminates the relationship of the maximum entropy principle (MEP) to the concept of "relative frequencies." Index Terms: Entropy functions ----- On the Complexity of Finite Sequences Lempel, A. Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1976 On page(s): 75- 81 Volume: 22, Issue: 1 ISSN: 0018-9448 Abstract: A new approach to the problem of evaluating the complexity ("randomness") of finite sequences is presented. The proposed complexity measure is related to the number of steps in a self-delimiting production process by which a given sequence is presumed to be generated. It is further related to the number of distinct substrings and the rate of their occurrence along the sequence. The derived properties of the proposed measure are discussed and motivated in conjunction with other well-established complexity criteria. Index Terms: Sequences ----- The rate-distortion function for source coding with side information at the decoder Wyner, A. Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1976 On page(s): 1- 10 Volume: 22, Issue: 1 ISSN: 0018-9448 Abstract: Let{(X_{k}, Y_{k}) }^{ infty}_{k=1}be a sequence of independent drawings of a pair of dependent random variablesX, Y. Let us say thatXtakes values in the finite setcal X. It is desired to encode the sequence{X_{k}}in blocks of length n into a binary stream of rateR, which can in turn be decoded as a sequence{ hat{X}_{k} }, wherehat{X}_{k} in hat{ cal X}, the reproduction alphabet. The average distortion level is(1/n) sum^{n}_{k=1} E[D(X_{k},hat{X}_{k})], whereD(x,hat{x}) geq 0, x in {cal X}, hat{x} in hat{ cal X}, is a preassigned distortion measure. The special assumption made here is that the decoder has access to the side information{Y_{k}}. In this paper we determine the quantityR ast (d), defined as the infimum ofratesRsuch that (withvarepsilon > 0arbitrarily small and with suitably largen)communication is possible in the above setting at an average distortion level (as defined above) not exceedingd + varepsilon. The main result is thatR ast (d) = inf [I(X;Z) - I(Y;Z)], where the infimum is with respect to all auxiliary random variablesZ(which take values in a finite setcal Z) that satisfy: i)Y,Zconditionally independent givenX; ii) there exists a functionf: {cal Y} times {cal Z} rightarrow hat{ cal X}, such thatE[D(X,f(Y,Z))] leq d. LetR_{X | Y}(d)be the rate-distortion function which results when the encoder as well as the decoder has access to the side information{ Y_{k} }. In nearly all cases it is shown that whend > 0thenR ast(d) > R_{X|Y} (d), so that knowledge of the side information at the encoder permits transmission of the{X_{k}}at a given distortion level using a smaller transmission rate. This is in contrast to the situation treated by Slepian and Wolf [5] where, for arbitrarily accurate reproduction of{X_{k}}, i.e.,d = varepsilonfor anyvarepsilon >0, knowledge of the side information at the- encoder does not allow a reduction of the transmission rate. Index Terms: Rate-distortion theory ----- Variable rate coding for nonergodic sources and classes of ergodic sources subject to a fidelity constraint Pursley, M. Davisson, L. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1976 On page(s): 324- 337 Volume: 22, Issue: 3 ISSN: 0018-9448 Abstract: This paper is concerned with two problems in the theory of source coding subject to a maximum average distortion constraint. The first problem involves the coding of a nonergodic discrete time source and the second involves coding for a class of ergodic discrete time sources. Coding theorems are given for both of these situations for very general source alphabets. The codes that are obtained here will, in general, be variable length codes so that average code rate and average distortion are the measures of performance. Index Terms: Rate-distortion theory Variable-rate coding ----- Huffman codes and self-information Katona, G. Nemetz, O. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1976 On page(s): 337- 340 Volume: 22, Issue: 3 ISSN: 0018-9448 Abstract: In this paper the connection between the self-information of a source letter from a finite alphabet and its code-word length in a Huffman code is investigated. Consider the set of all independent finite alphabet sources which contain a source letter a of probabilityp. The maximum over this set of the length of a Huffman codeword for a is determined. This maximum remains constant aspvaries between the reciprocal values of two consecutive Fibonacci numbers. For the smallpthis maximum is approximately equal toleft[ log_{2} frac{1+ sqrt{5}}{2} right]^{-1} approx 1.44times the self-information. Index Terms: Huffman codes ----- Information bounds of the Fano-Kullback type Blahut, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1976 On page(s): 410- 421 Volume: 22, Issue: 4 ISSN: 0018-9448 Abstract: A large class of lower bounds relating to the performance of hypothesis testers, channel codes, and source compression codes is developed. These are extensions of Fano's inequality on the one hand, and of the discrimination inequality of Kullback on the other. The hypothesis testing and channel coding bounds are interesting primarily for small blocklengths and, in general, are asymptotically inferior to the well-known exponentially decreasing bounds. The source compression results include new proofs of converse coding theorems. A lower bound is given to the probability that a source produces an output block which cannot be encoded within a desired maximum distortion. Index Terms: Block codes Coding Decision procedures Source coding ----- Basic limits on protocol information in data communication networks Gallager, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1976 On page(s): 385- 398 Volume: 22, Issue: 4 ISSN: 0018-9448 Abstract: We consider basic limitations on the amount of protocol information that must be transmitted in a data communication network to keep track of source and receiver addresses and of the starting and stopping of messages. Assuming Poisson message arrivals between each communicating source-receiver pair, we find a lower bound on the required protocol information per message. This lower bound is the sum of two terms, one for the message length information, which depends only on the distribution of message lengths, and the other for the message start information, which depends only on the product of the source-receiver pair arrival rate and the expected delay for transmitting the message. Two strategies are developed which, in the limit of large numbers of sources and receivers, almost meet the lower bound on protocol information. Index Terms: Data communications Message switching Multiplexing Packet switching Queued communications Source coding Store-and-forward networks Time-division multiplexing ----- The zero-error side information problem and chromatic numbers (Corresp.) Witsenhausen, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1976 On page(s): 592- 593 Volume: 22, Issue: 5 ISSN: 0018-9448 Abstract: A discrete random variableXis to be transmitted by means of a discrete signal. The receiver has prior knowledge of a discrete random variableYjointly distributed withX. The probability of error must be exactly zero, and the problem is to minimize the signal's alphabet size. In the case where the transmitter also has access to the value ofY, the problem is trivial and no advantage can be obtained by block coding over independent repetitions. If, however,Yis not known at the transmitter then the problem is equivalent to the chromatic number problem for graphs, and block coding may produce savings. Index Terms: Graph theory Source coding ----- New directions in cryptography Diffie, W. Hellman, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1976 On page(s): 644- 654 Volume: 22, Issue: 6 ISSN: 0018-9448 Abstract: Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing. Index Terms: Cryptography ----- Data compression for communication networks: The delay-distortion function Rubin, I. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1976 On page(s): 655- 665 Volume: 22, Issue: 6 ISSN: 0018-9448 Abstract: The problem of data compression for communication networks is considered. The system performance criterion is the signal distortion resulting both from data compression and from average message delay through the network. The delay-distortion function is defined as the smallest message delay among all data-compression schemes that yield the given distortion value. The distortion-delay region is similarly defined. The capacity region is defined to include all incoming message rates for which there exists a set of data-compression schemes yielding a prescribed network distortion-delay value. The basic characteristics of these functions and regions are derived. In particular, it is shown that their evaluations can be performed by solving separately the source coding problem and the network's queuing problem. The distortion-delay functions and regions are explicitly derived for single channel systems. Index Terms: Delay distortion Multiple-access communications Packet switching Queued communications Source coding Store-and-forward networks ----- A survey of multi-way channels in information theory: 1961-1976 van der Meulen, E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1977 On page(s): 1- 37 Volume: 23, Issue: 1 ISSN: 0018-9448 Abstract: The advances in the area of multi-way channels during the period 1961-1976 are described. Shannon's two-way channel, the multiple-access channel, the interference channel, the broadcast channel, and the relay channel are treated successively. Only channel coding aspects are discussed. Thirty-nine open problems are mentioned. Index Terms: Bibliographies Broadcast channels Coding Interference Multiple-access communications Multiuser channels ----- General broadcast channels with degraded message sets Korner, J. Marton, K. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1977 On page(s): 60- 64 Volume: 23, Issue: 1 ISSN: 0018-9448 Abstract: A broadcast channel with one sender and two receivers is considered. Three independent messages are to be transmitted over this channel: one common message which is meant for both receivers, and one private message for each of them. The coding theorem and strong converse for this communication situation is proved for the case when one of the private messages has rate zero. Index Terms: Broadcast channels Coding ----- Explicit bounds to R(D) for a binary symmetric Markov source Berger, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1977 On page(s): 52- 59 Volume: 23, Issue: 1 ISSN: 0018-9448 Abstract: 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. Index Terms: Markov processes Rate-distortion theory ----- Generalized Gram-Charlier series with application to the sum of log-normal variates (Corresp.) Schleher, D. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1977 On page(s): 275- 280 Volume: 23, Issue: 2 ISSN: 0018-9448 Abstract: A generalized Gram-Charlier series, applicable to non-Gaussian problems, is developed. Expressions are given for the first six error coefficients. The high inherent accuracy of the series is demonstrated by development of the expansion for the sum of independent, identically distributed log-normal variates. Index Terms: Log-normal distributions Probability functions ----- An extension of the Shannon theory approach to cryptography Hellman, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1977 On page(s): 289- 294 Volume: 23, Issue: 3 ISSN: 0018-9448 Abstract: Shannon's information-theoretic approach to cryptography is reviewed and extended. It is shown that Shannon's random cipher model is conservative in that a randomly chosen cipher is essentially the worst possible. This is in contrast with error-correcting codes where a randomly chosen code is essentially the best possible. The concepts of matching a cipher to a language and of the trade-off between local and global uncertainty are also developed. Index Terms: Cryptography ----- A universal algorithm for sequential data compression Ziv, J. Lempel, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1977 On page(s): 337- 343 Volume: 23, Issue: 3 ISSN: 0018-9448 Abstract: A universal algorithm for sequential data compression is presented. Its performance is investigated with respect to a nonprobabilistic model of constrained sources. The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable-to-block codes designed to match a completely specified source. Index Terms: Sequential coding Source coding ----- Distortion-rate functions for vector sources and a maximum fidelity criterion Leiner, B. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1977 On page(s): 354- 359 Volume: 23, Issue: 3 ISSN: 0018-9448 Abstract: The problem of distortion-rate functions for vector sources is considered. Two fidelity criteria are treated. The first considers the maximum of the weighted component distortions and then takes the per-letter average. The second takes the maximum of the weighted component per-letter averages. In either case, a well-defined distortion-rate function results, giving the minimum possible distortion achievable at a given rate of transmission. Upper and lower bounds to these distortion-rate functions are derived in terms of more easily calculated functions. Index Terms: Rate-distortion theory Source coding ----- A note on Wyner's wiretap channel (Corresp.) Carleial, A. Hellman, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1977 On page(s): 387- 390 Volume: 23, Issue: 3 ISSN: 0018-9448 Abstract: Wyner recently introduced the concept of a wiretap channel and showed that by transmitting at a rate less than capacity on the main link it was possible to keep the wiretapper's information about the entire message equal to zero. It is shown that it is possible to send at capacity on the main link and still keep the wiretapper's information equal to zero on many, large, arbitrary portions of the message. Index Terms: Cryptography ----- Information structure: Common and private (Corresp.) Hexner, G. Ho, Y. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1977 On page(s): 390- 393 Volume: 23, Issue: 3 ISSN: 0018-9448 Abstract: Two new definitions for the common and private information structures between two decisionmakers are introduced and are shown to satisfy various reasonable properties. The new definitions are framed in a decisionmaking context and do not require a probability assignment on the space of events. Index Terms: Decision making ----- On common information in decision problems Dick, R. Hexner, G. Ho, Y. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1977 On page(s): 393- 396 Volume: 23, Issue: 3 ISSN: 0018-9448 Abstract: Three classes of decisionmaking problems are distinguished, and notions of common information appropriate thereto are discussed for cases involving two or more decisionmakers. Index Terms: Not Available ----- On the rate distortion functions of spherically invariant vectors and sequences Hoi Leung Cambanis, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1978 On page(s): 367- 373 Volume: 24, Issue: 3 ISSN: 0018-9448 Abstract: The Shannon lower bound on the rate distortion function of spherically invariant random vectors and sequences is found, and a condition for its tightness is given. Under this condition, simple upper bounds which are valid over a certain range of distortions are given. Also included is a coding theorem for certain stationary discrete-time spherically invariant sources. Index Terms: Rate-distortion theory ----- Renyi's entropy and the probability of error Ben-Bassat, M. Raviv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1978 On page(s): 324- 331 Volume: 24, Issue: 3 ISSN: 0018-9448 Abstract: The basic properties of Renyi's entropy are reviewed, and its concavity properties are characterized. New bounds (referred to asI_{alpha}bounds) on the probability of error are derived from Renyi's entropy and are compared with known bounds. It is proved that for the two-class case, theI_{2}bound is sharper than many of the previously known bounds. The difference between theI_{2}bound and the real value of the probability of error is at most 0.09. Index Terms: Entropy functions Pattern classification ----- Broadcast channels with confidential messages Csiszar, I. Korner, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1978 On page(s): 339- 348 Volume: 24, Issue: 3 ISSN: 0018-9448 Abstract: Given two discrete memoryless channels (DMC's) with a common input, it is desired to transmit private messages to receiver1rateR_{1}and common messages to both receivers at rateR_{o}, while keeping receiver2as ignorant of the private messages as possible. Measuring ignorance by equivocation, a single-letter characterization is given of the achievable triples(R_{1},R_{e},R_{o})whereR_{e}is the equivocation rate. Based on this channel coding result, the related source-channel matching problem is also settled. These results generalize those of Wyner on the wiretap channel and of Körner-Marton on the broadcast Channel. ----- The Gaussian wire-tap channel Leung-Yan-Cheong, S. Hellman, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1978 On page(s): 451- 456 Volume: 24, Issue: 4 ISSN: 0018-9448 Abstract: Wyner's results for discrete memoryless wire-tap channels are extended to the Gaussian wire-tap channel. It is shown that the secrecy capacity Cs is the difference between the capacities of the main and wire.tap channels. It is further shown that Rd= Cs is the upper boundary of the achievable rate-equivocation region. Index Terms: Broadcast channels Cryptography Rate-distortion theory ----- Variations on a theme by Huffman Gallager, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1978 On page(s): 668- 674 Volume: 24, Issue: 6 ISSN: 0018-9448 Abstract: In honor of the twenty-fifth anniversary of Huffman coding, four new results about Huffman codes are presented. The first result shows that a binary prefix condition code is a Huffman code iff the intermediate and terminal nodes in the code tree can be listed by nonincreasing probability so that each node in the list is adjacent to its sibling. The second result upper bounds the redundancy (expected length minus entropy) of a binary Huffman code byP_{1}+ log_{2}[2(log_{2}e)/e]=P_{1}+0.086, whereP_{1}is the probability of the most likely source letter. The third result shows that one can always leave a codeword of length two unused and still have a redundancy of at most one. The fourth result is a simple algorithm for adapting a Huffman code to slowly varying esthnates of the source probabilities. In essence, one maintains a running count of uses of each node in the code tree and lists the nodes in order of these counts. Whenever the occurrence of a message increases a node count above the count of the next node in the list, the nodes, with their attached subtrees, are interchanged. Index Terms: Adaptive coding Huffman codes ----- On the Shannon capacity of a graph Lovasz, L. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1979 On page(s): 1- 7 Volume: 25, Issue: 1 ISSN: 0018-9448 Abstract: It is proved that the Shannon zero-error capacity of the pentagon issqrt{5}. The method is then generalized to obtain upper bounds on the capacity of an arbitrary graph. A well-characterized, and in a sense easily computable, function is introduced which bounds the capacity from above and equals the capacity in a large number of cases. Several results are obtained on the capacity of special graphs; for example, the Petersen graph has capacity four and a self-complementary graph with n points and with a vertex-transitive automorphism group has capacitysqrt{5}. Index Terms: Graph theory Information rates ----- Reliability function of a discrete memoryless channel at rates above capacity (Corresp.) Dueck, G. Korner, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1979 On page(s): 82- 85 Volume: 25, Issue: 1 ISSN: 0018-9448 Abstract: Asymptotically coincident upper and lower bounds on the exponent of the largest possible probability of the correct decoding of block codes are given for all rates above capacity. The lower bound sharpens Omura's bound. The upper bound is proved by a new and simple combinatorial argument. Index Terms: Block codes Decoding ----- How to encode the modulo-two sum of binary sources (Corresp.) Korner, J. Marton, K. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1979 On page(s): 219- 221 Volume: 25, Issue: 2 ISSN: 0018-9448 Abstract: How much separate information about two random binary sequences is needed in order to tell with small probability of error in which positions the two sequences differ? If the sequences are the outputs of two correlated memoryless binary sources, then in some cases the rate of this information may be substantially less than the joint entropy of the two sources. This result is implied by the solution of the source coding problem with two separately encoded side information sources for a special class of source distributions. Index Terms: Source coding ----- On Some Problems of Lovász Concerning the Shannon Capacity of a Graph Haemers, W. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1979 On page(s): 231- 232 Volume: 25, Issue: 2 ISSN: 0018-9448 Abstract: The answers to several problems of Lovhat{a}sz concerning the Shannon capacity of a graph are shown to be negative. Index Terms: Not Available ----- The capacity of a class of broadcast channels Gamal, A.E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1979 On page(s): 166- 169 Volume: 25, Issue: 2 ISSN: 0018-9448 Abstract: The capacity region is established for those discrete memoryless broadcast channelsp(y,z mid x)for whichI(X;Y) geq I(X;Z)holds for all Input distributions. The capacity region for this class of channels resembles the capacity region for degraded message sets considered by Körner and Marton. Index Terms: Broadcast channels ----- Source coding with cross observations at the encoders (Corresp.) Te Han This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1979 On page(s): 360- 361 Volume: 25, Issue: 3 ISSN: 0018-9448 Abstract: A source coding problem is considered which generalizes the Slepian-Wolf-Cover theorem on noiseless coding of correlated sources so as to include the case of arbitrary cross observations at the encoders. The achievable rate region is established by using Cover's result. Also a co-polymatroidal property of the relevant polytope is pointed out. Index Terms: Multiple-access communications Source coding ----- A coding theorem for the discrete memoryless broadcast channel Marton, K. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1979 On page(s): 306- 311 Volume: 25, Issue: 3 ISSN: 0018-9448 Abstract: A coding theorem for the discrete memoryless broadcast channel is proved for the case where no common message is to he transmitted. The theorem is a generalization of the results of Cover and van der Meulen on this problem. The result is tight for broadcast channels having one deterministic component Index Terms: Broadcast channels Coding Memoryless channels ----- New fidelity criteria for discrete-time source encoding Rickard, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1979 On page(s): 275- 282 Volume: 25, Issue: 3 ISSN: 0018-9448 Abstract: A probabilistic approach to the source encoding problem requires the specification of a fidelity criterion which measures the degradation of the source output produced by the encoding transformation. Historically, the fidelity criteria generated by difference-type distortion measures have received by far the widest acceptance, due in part to their analytical tractability. Two new fidelity criteria for discrete.time sources are introduced. These are designated as the "mean incoherence" (MIC) and the "mean lng-coherence" (MLC). Both criteria are functionals of the magnitude-squared coherence between the source output and its reproduction, and thus do not admit a recognizable time-domain distortion measure representation. Interesting features of these fidelity criteria are indicated, and comparisons are made with the classical mean-squared error (MSE) fidelity criterion. The rate-distortion functions for a stationary Gaussian source subject to constraints on either the MIC or MLC are derived, and the corresponding optimum encoder behavior is described. Finally, the applications where these new fidelity criteria may he advantageous over the MSE criterion are discussed. Index Terms: Rate-distortion theory Source coding ----- A note on the capacity region of the multiple-access channel (Corresp.) Bierbaum, M. Wallmeier, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1979 On page(s): 484- 484 Volume: 25, Issue: 4 ISSN: 0018-9448 Abstract: In the classification problem for chromosomes there areNchromosomes which must be classified intokpopulationsA_(1}, cdots ,A_{k}having known probability distributions. It is further known that theseNchromosomes haveN_{i}in classA_{i}, i = 1,2, cdots ,k. This is a compound decision problem whose optimal solution gives a classification algorithm which is not currently useful in practice because of its long computation time. Two other classification methods are considered, and the results are compared. One is the method often used for the classification of the 46 human chromosomes, where the knowledge about the exact number of chromosome types is disregarded, and only the a priori probability that a chromosome originates from populationA_{i}is used. The other method permits only classifications with the correct number of objects in each class and selects from all the possible classifications that one which has the maximum likelihood function. This last method has some advantages for a small number of objects, particularly if the numbers of objects in the classes are equal. Index Terms: Multiple-access communications ----- On the algorithmic foundation of information theory Heim, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1979 On page(s): 557- 566 Volume: 25, Issue: 5 ISSN: 0018-9448 Abstract: The information content of binary sequences is defined by minimal program complexity measures and is related to computable martingales. The equivalence of the complexity approach and the martingale approach after restriction to effective random tests is used to establish generalized source coding theorems and converses. Finite state complexity and decomposable martingales are related to classical block codes and the relative frequency behavior of sequences. Index Terms: Computation theory Information theory Martingales Sequences Source coding ----- The source coding theorem revisited: A combinatorial approach Longo, G. Sgarro, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1979 On page(s): 544- 548 Volume: 25, Issue: 5 ISSN: 0018-9448 Abstract: A combinatorial approach is proposed for proving the classical source coding theorems for a finite memoryless stationary source (giving achievable rates and the error probability exponent). This approach provides a sound heuristic justification for the widespread appearence of entropy and divergence (Kullback's discrimination) in source coding. The results are based on the notion of composition class -- a set made up of all the distinct source sequences of a given length which are permutations of one another. The asymptotic growth rate of any composition class is precisely an entropy. For a finite memoryless constant source all members of a composition class have equal probability; the probability of any given class therefore is equal to the number of sequences in the class times the probability of an individual sequence in the class. The number of different composition classes is algebraic in block length, whereas the probability of a composition class is exponential, and the probability exponent is a divergence. Thus if a codeword is assigned to all sequences whose composition classes have rate less than some rateR, the probability of error is asymptotically the probability of the must probable composition class of rate greater thanR. This is expressed in terms of a divergence. No use is made either of the law of large numbers or of Chebyshev's inequality. Index Terms: Combinatorial mathematics Source coding ----- The source coding theorem revisited: A combinatorial approach Longo, G. Sgarro, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1979 On page(s): 544- 548 Volume: 25, Issue: 5 ISSN: 0018-9448 Abstract: A combinatorial approach is proposed for proving the classical source coding theorems for a finite memoryless stationary source (giving achievable rates and the error probability exponent). This approach provides a sound heuristic justification for the widespread appearence of entropy and divergence (Kullback's discrimination) in source coding. The results are based on the notion of composition class -- a set made up of all the distinct source sequences of a given length which are permutations of one another. The asymptotic growth rate of any composition class is precisely an entropy. For a finite memoryless constant source all members of a composition class have equal probability; the probability of any given class therefore is equal to the number of sequences in the class times the probability of an individual sequence in the class. The number of different composition classes is algebraic in block length, whereas the probability of a composition class is exponential, and the probability exponent is a divergence. Thus if a codeword is assigned to all sequences whose composition classes have rate less than some rateR, the probability of error is asymptotically the probability of the must probable composition class of rate greater thanR. This is expressed in terms of a divergence. No use is made either of the law of large numbers or of Chebyshev's inequality. Index Terms: Combinatorial mathematics Source coding ----- Capacity theorems for the relay channel Cover, T. Gamal, A.E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1979 On page(s): 572- 584 Volume: 25, Issue: 5 ISSN: 0018-9448 Abstract: A relay channel consists of an inputx_{l}, a relay outputy_{1}, a channel outputy, and a relay senderx_{2}(whose transmission is allowed to depend on the past symbolsy_{1}. The dependence of the received symbols upon the inputs is given byp(y,y_{1}|x_{1},x_{2}). The channel is assumed to be memoryless. In this paper the following capacity theorems are proved. 1)Ifyis a degraded form ofy_{1}, thenC : = : max !_{p(x_{1},x_{2})} min ,{I(X_{1},X_{2};Y), I(X_{1}; Y_{1}|X_{2})}. 2)Ify_{1}is a degraded form ofy, thenC : = : max !_{p(x_{1})} max_{x_{2}} I(X_{1};Y|x_{2}). 3)Ifp(y,y_{1}|x_{1},x_{2})is an arbitrary relay channel with feedback from(y,y_{1})to bothx_{1} and x_{2}, thenC: = : max_{p(x_{1},x_{2})} min ,{I(X_{1},X_{2};Y),I ,(X_{1};Y,Y_{1}|X_{2})}. 4)For a general relay channel,C : leq : max_{p(x_{1},x_{2})} min ,{I ,(X_{1}, X_{2};Y),I(X_{1};Y,Y_{1}|X_{2}). Superposition block Markov encoding is used to show achievability ofC, and converses are established. The capacities of the Gaussian relay channel and certain discrete relay channels are evaluated. Finally, an achievable lower bound to the capacity of the general relay channel is established. Index Terms: Information rates Repeaters ----- An upper bound on the rate distortion function for source coding with partial side information at the decoder Berger, T. Housewright, K. Omura, J. Suiyin Yung Wolfowitz, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1979 On page(s): 664- 666 Volume: 25, Issue: 6 ISSN: 0018-9448 Abstract: 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 Index Terms: Not Available ----- Reproducing probability density classes on Lie groups with application to discrete-time filtering (Corresp.) Johnson, C. Stear, E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1980 On page(s): 124- 129 Volume: 26, Issue: 1 ISSN: 0018-9448 Abstract: A general approach to discrete-time filtering for dynamical systems evolving in a Lie group is presented. The most general filtering solution is given by the signal probability density function conditioned on the measurements, which for nonlinear systems is usually nonparametric. Index Terms: Discrete-time filters Lie groups Nonlinear filtering ----- Distortion-rate theory for individual sequences Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1980 On page(s): 137- 143 Volume: 26, Issue: 2 ISSN: 0018-9448 Abstract: For every individual infinite sequenceuwe define a distortion-rate functiond(R|u)which is shown to be an asymptotically attainable lower bound on the distortion that can be achieved foruby any finite-state encoder which operates at a fixed output information rateR. This is done by means of a coding theorem and its converse. No probabilistic characterization ofuis assumed. The coding theorem demonstrates the existence of {em universal} encoders which are asymptotically optimal for every infinite sequence over a given finite alphabet. The transmission of individual sequences via a noisy channel with a capacityCis also investigated. It is shown that, for every given sequenceuand any finite-state encoder, the average distortion with respect to the channel statistics is lower bounded byd(C|u). Furthermored(C|u)is asymptotically attainable. Index Terms: Rate-distortion theory Source coding ----- Towards a general theory of source networks Csiszar, I. Korner, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1980 On page(s): 155- 165 Volume: 26, Issue: 2 ISSN: 0018-9448 Abstract: A unified approach to multiterminal source coding problems not involving rate-distortion theory is presented. It is shown that, for determining file achievable rate region, attention may be restricted to source networks of a relatively simple structure. A product space characterizafion of the achievable rate region pinpoints the mathematical problem to be solved for getting a single letter characterization. The complexity of this problem depends on a structural condition, viz., the number of encoders of a certain kind in the source network. This approach yields all the known single-letter characterizations of achievable rate regions and a number of new ones for more complex networks. As a digression, for a class of source networks including that of Slepian and Wolf, exponential error bounds are derived which are attainable by universal codes. These bounds are tight in a neighborhood of the boundary of the achievable rate region. Index Terms: Source coding ----- Some aspects of convexity useful in information theory Witsenhausen, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1980 On page(s): 265- 271 Volume: 26, Issue: 3 ISSN: 0018-9448 Abstract: From its very beginning, information theory has been pervaded by convexity arguments. Much of the necessary background was developed on an ad hoc basis without reference to the knowledge available from the mathematical study of convex sets and functions. Yet explicit use shown by examples. Index Terms: Information theory Set theory ----- An evaluation of the Wyner-Ziv rate region (Corresp.) Mackenthun, K., Jr. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1980 On page(s): 347- 350 Volume: 26, Issue: 3 ISSN: 0018-9448 Abstract: Wyner and Ziv considered the problem of source encoding and decoding when the decoder knows a random variableYcorrelated with the sourceX. The least rateRfor which the system can operate with fidelitydia given ia terms of an information theoretic minimizationRast (d). Explicit upper and lower bounds toRast (d)are given for an important class of correlated sources. The upper and lower bounds have been evaluated for several members of the class and are shown to agree in these cases. Index Terms: Rate-distortion theory ----- Mutual information rate, distortion, and quantization in metric spaces Gray, R. Kieffer, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1980 On page(s): 412- 422 Volume: 26, Issue: 4 ISSN: 0018-9448 Abstract: Several new properties as well as simplified proofs of known properties are developed for the mutual information rate between discrete-time random processes whose alphabets are Borel subsets of complete separable metric spaces. In particular, the asymptotic properties of quantizers for such spaces provide a fink with finite-alphabet processes and yield the ergodic decomposition of mutual information rate. This result is used to prove the equality of stationary and ergodic process distortion-rate functions with the usual distortion-rate function. An unusual definition of mutual information rate for continuous-alphabet processes is used, but it is shown to be operationally appropriate and more useful mathematically; it provides an intuitive link between continuous-alphabet and finite-alphabet processes, and it allows generalizations of some fundamental results of ergodic theory that are useful for information theory. Index Terms: Mutual information Quantization (signal) Rate-distortion theory Signal quantization Stochastic processes ----- Indirect rate distortion problems Witsenhausen, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1980 On page(s): 518- 521 Volume: 26, Issue: 5 ISSN: 0018-9448 Abstract: The output of a source, the first of the two arguments of a distortion function, is seen by an encoder through a noisy channel. A decoder sees the encoder's signal through the usual communication channel. The second argument of the distortion function is obtained from the decoder's output via another noisy channel. The Dobrushin-Tsybakov reduction of this problem to a direct one is shown to follow at once from a "disconnection principle" for conditional expectations. The same principle applies to more general situations such as i) dependence between the noise variables acting in the input and output channels and ii) side information available only at the decoder. Index Terms: Rate-distortion theory ----- Graph decomposition: A new key to coding theorems Csiszar, I. Korner, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1981 On page(s): 5- 12 Volume: 27, Issue: 1 ISSN: 0018-9448 Abstract: A new and simple method is proposed for finding good encoders both for channels and for sources with side information. This method relies on the continuous version of a graph decomposition result of Lovász. The presently known best exponential error bounds for both problems follow in a unified manner with an improvement on the source coding bound. The previous bounds for universal codes of the authors and Marton are also improved. Index Terms: Coding Graph theory ----- A proof of Marton's coding theorem for the discrete memoryless broadcast channel (Corresp.) El Gamal, A. van der Meulen, E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1981 On page(s): 120- 122 Volume: 27, Issue: 1 ISSN: 0018-9448 Abstract: A simple proof using random partitions and typicality is given for Marton's coding theorem for broadcast channels. Index Terms: Broadcast channels Coding Memoryless channels ----- The capacity region for the deterministic broadcast channel with a common message (Corresp.) Te Han This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1981 On page(s): 122- 125 Volume: 27, Issue: 1 ISSN: 0018-9448 Abstract: The deterministic broadcast channel with two output terminals is studied for the case of a common message. The capacity region for this channel is established by means of a random coding argument combining the standard channel coding technique and the standard source coding technique. Index Terms: Broadcast channels Coding Source coding ----- An achievable rate region for the multiple-access channel with feedback Cover, T. Leung, C. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1981 On page(s): 292- 298 Volume: 27, Issue: 3 ISSN: 0018-9448 Abstract: An achievable rate regionR_{1} leq I(X_{1};Y|X_{2},U), R_{2} leq I(X_{2}; Y|X_{1},U), R_{1}+R_{2} leq I(X_{1}, X_{2};Y), wherep(u,x_{l},x_{2},y)= p(u)p(x_{l}|u)p(x_{2}|u)p(y|x_{l},x_{2}), is established for the multiple-access channel with feedback. Time sharing of these achievable rates yields the rate region of this paper. This region generally exceeds the achievable rate region without feedback and exceeds the rate point found by Gaarder and Wolf for the binary erasure multiple-access channel with feedback. The presence of feedback allows the independent transmitters to understand each other's intended transmissions before the receiver has sufficient information to achieve the desired decoding. This allows the transmitters to cooperate in the transmission of information that resolves the residual uncertainty of the receiver. At the same time, independent information from the transmitters is superimposed on the cooperative correction information. The proof involves list codes and block Markov encoding. Index Terms: Not Available ----- A strong outer bound to the capacity region for multiple access channels (Corresp.) Ohkubo, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1981 On page(s): 505- 508 Volume: 27, Issue: 4 ISSN: 0018-9448 Abstract: Arimoto's converse to the coding theorem for discrete memoryless channel is extended to multiple access channels. The strong outer bound to the capacity region for multiple access channels that results is described analytically and graphically. Index Terms: Memoryless channels Multiple-access communications ----- Maximum entropy and conditional probability van Campenhout, J. Cover, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1981 On page(s): 483- 489 Volume: 27, Issue: 4 ISSN: 0018-9448 Abstract: It is well-known that maximum entropy distributions, subject to appropriate moment constraints, arise in physics and mathematics. In an attempt to find a physical reason for the appearance of maximum entropy distributions, the following theorem is offered. The conditional distribution ofX_{l}given the empirical observation(1/n)sum^{n}_{i}=_{l}h(X_{i})=alpha, whereX_{1},X_{2}, cdotsare independent identically distributed random variables with common densitygconverges tof_{lambda}(x)=e^{lambda^{t}h(X)}g(x)(Suitably normalized), wherelambdais chosen to satisfyint f_{lambda}(x)h(x)dx= alpha. Thus the conditional distribution of a given random variableXis the (normalized) product of the maximum entropy distribution and the initial distribution. This distribution is the maximum entropy distribution whengis uniform. The proof of this and related results relies heavily on the work of Zabell and Lanford. Index Terms: Entropy functions ----- The capacity of the physically degraded Gaussian broadcast channel with feedback (Corresp.) Gamal, A.E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1981 On page(s): 508- 511 Volume: 27, Issue: 4 ISSN: 0018-9448 Abstract: Bounds on the output entropy of the additive white Gaussian noise (AWGN) channel with feedback are used to prove that the capacity of the degraded additive white Gaussian noise (DAWGN) broadcast channel is not increased by feedback. Index Terms: Broadcast channels ----- To get a bit of information may be as hard as to get full information Ahlswede, R. Csiszar, I. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1981 On page(s): 398- 408 Volume: 27, Issue: 4 ISSN: 0018-9448 Abstract: The following coding problem for correlated discrete memoryless sources is considered. The two sources can be separately block encoded, and the values of the encoding functions are available to a decoder who wants to answer a certain question concerning the source outputs. Typically, this question has only a few possible answers (even as few as two). The rates of the encoding functions must be found that enable the decoder to answer this question correctly with high probability. It is proven that these rates are often as large as those needed for a full reproduction of the outputs of both sources. Furthermore, if one source is completely known at the decoder, this phenomenon already occurs when what is asked for is the joint type (joint composition) of the two source output blocks, or some function thereof such as the Hamming distance of the two blocks or (for alphabet size at least three) just the parity of this Hamming distance. Index Terms: Information rates Source coding ----- On universal coding for classes of composite and remote sources with memory (Corresp.) Fontana, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1981 On page(s): 784- 786 Volume: 27, Issue: 6 ISSN: 0018-9448 Abstract: Weakly minimax universal codes for composite sources whose channel analog has asymptotically decreasing input memory and anticipation (ADIMA) are examined. In particular, weak universal codes of all rates with respect to an arbitrary distortion measure are shown to exist for ADIMA composite sources when the switch processes belong to abar{d}-compact class. These results are immediately applicable to universal coding for classes of remote sources. Index Terms: Source coding ----- The feedback capacity region of a class of discrete memoryless multiple access channels (Corresp.) Willems, F. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1982 On page(s): 93- 95 Volume: 28, Issue: 1 ISSN: 0018-9448 Abstract: The capacity region of a class of discrete memoryless multiple access channels with feedback is determined, including as a special case the channel considered by Gaarder and Wolf. Index Terms: Memoryless systems Multiple-access communications ----- The rate-distortion function on classes of sources determined by spectral capacities Poor, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1982 On page(s): 19- 26 Volume: 28, Issue: 1 ISSN: 0018-9448 Abstract: The quantitysup_{a in cal R} R{a}(D)is considered, wherecal Ris a class of homogeneousn-parameter sources andR_{a}(D)denotes the single-letter mean-square-error (MSE) rate-distortion function for the individual source a. In particular, the case in which the classcal Ris specified in terms of spectral information is treated for general classes of spectral measures whose upper measures are capacities (in the sense of Choquet) alternating of order two. This type of class includes many common models for spectral uncertainty such as mixture models, spectral band models, and neighborhoods generated by variation and Prohorov metrics. It is shown that each such class contains a worst-case source whose rate-distortion function achieves the supremum over the class for each value of distortion. This source is characterized as having a spectral density that is a derivative (in the sense of Huber and Strassen) of the upper spectral measure with respect to Lebesgue measure on[-pi,pi]^{n}. Moreover it is shown that the spectral measure of the worst-case source is closest, in a sense defined by directed divergence, to Lebesgue measure (which corresponds to a memoryless source). Numerical results are presented for the particular case in which the source spectral measure is a mixture of a Gauss-Markov spectrum and an unknown contaminating component. Index Terms: Rate-distortion theory ----- Feedback does not affect the reliability function of a DMC at rates above capacity (Corresp.) Csiszar, I. Korner, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1982 On page(s): 92- 93 Volume: 28, Issue: 1 ISSN: 0018-9448 Abstract: Asymptotically coincident upper and lower bounds on the exponent of the largest possible probability of correct decoding for block codes of any given rate above capacity have been given by Dueck and Körner. Their method is extended to show that the same bounds also hold in the presence of noiseless feedback. Index Terms: Memoryless systems ----- On the convexity of some divergence measures based on entropy functions Burbea, J. Rao, C. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1982 On page(s): 489- 495 Volume: 28, Issue: 3 ISSN: 0018-9448 Abstract: Three measures of divergence between vectors in a convex set of an-dimensional real vector space are defined in terms of certain types of entropy functions, and their convexity property is studied. Among other results, a classification of the entropies of degreealphais obtained by the convexity of these measures. These results have applications in information theory and biological studies. Index Terms: Not Available ----- The capacity of the semideterministic relay channel (Corresp.) Gamal, A.E. Aref, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1982 On page(s): 536- 536 Volume: 28, Issue: 3 ISSN: 0018-9448 Abstract: The capacity of the class of relay channels with senderx_{1}, a relay senderx_{2}, a relay receivery_{1}=f(x_{1},x_{2}), and ultimate receiveryis proved to beC = maxmin_{p(x_{1},x_{2})} {I(X_{1}, X_{2}; Y), H(Y_{1}|X_{2})+I(X_{1};Y|X_{2},Y_{1}})}. Index Terms: Information rates Repeaters ----- Information-singularity and recoverability of random processes Hajek, B. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1982 On page(s): 422- 429 Volume: 28, Issue: 3 ISSN: 0018-9448 Abstract: Two notions of information-singular and strong information-singular random processes were proposed by Berger as processes which are deterministic or negligible in a physically meaningful, information theoretic sense. This paper serves two purposes. First, it shows that strong information-singularity of a random process is equivalent to information-singularity plus a quite different property called recoverability. Secondly, it shows that these properties can be completely characterized in the case where the processes of interest are (jointly) stationary and satisfy a mild integrability condition. Index Terms: Information theory ----- Information of partitions with applications to random access communications Hajek, B. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1982 On page(s): 691- 701 Volume: 28, Issue: 5 ISSN: 0018-9448 Abstract: The minimum amount of information and the asymptotic minimum amount of entropy of a random partition which separates the points of a Poisson point process are found. Related information theoretic bounds are applied to yield an upper bound to the throughput of a random access broadcast channel. It is shown that more information is needed to separate points by partitions consisting of intervals than by general partitions. This suggests that single-interval conflict resolution algorithms may not achieve maximum efficiency. Index Terms: Multiple-access communications Mutual information Point processes ----- Wyner - Ziv theory for a general function of the correlated sources (Corresp.) Yamamoto, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1982 On page(s): 803- 807 Volume: 28, Issue: 5 ISSN: 0018-9448 Abstract: A source coding problem is considered for the Wyner-Ziv type system where the decoder is required to estimate the value of some function of the encoder input and the side information. The rate-distortion function is established for this system, and for some binary cases parametric expressions are obtained to enable numerical calculations. Index Terms: Source coding ----- On the error exponent of source-channel transmission with a distortion threshold Csiszar, I. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1982 On page(s): 823- 828 Volume: 28, Issue: 6 ISSN: 0018-9448 Abstract: The author's previous results on the exponent of probability of error for joint source-channel codes are improved and extended to distortion threshold fidelity criteria. The maximum error version of the problem is also considered. Index Terms: Rate-distortion theory Source coding ----- Rate-distortion for correlated sources with partially separated encoders Kaspi, A. Berger, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1982 On page(s): 828- 840 Volume: 28, Issue: 6 ISSN: 0018-9448 Abstract: 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. Index Terms: Rate-distortion theory ----- The Gaussian test channel with an intelligent jammer Basar, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1983 On page(s): 152- 157 Volume: 29, Issue: 1 ISSN: 0018-9448 Abstract: The problem of transmitting a sequence of identically distributed independent Gaussian random variables through a Gaussian memoryless channel with a given input power constraint, in the presence of an intelligent jammer, is considered. The jammer taps the channel and feeds back a signal, at a given energy level, for the purpose of jamming the transmitting sequence. Under a square-difference distortion measure which is to be maximized by the jammer and to be minimized by the transmitter and the receiver, this correspondence obtains the complete set of optimal (saddle-point) policies. The solution is essentially unique, and it is structurally different in three different regions in the parameter space, which are determined by the signal-to-noise ratios and relative magnitudes of the noise variances. The best (maximin) policy of the jammer is either to choose a linear function of the measurement he receives through channel-tapping, or to choose, in addition (and additively), an independent Gaussian noise sequence, depending on the region where the parameters lie. The optimal (minimax) policy of the transmitter is to amplify the input sequence to the given power level by a linear transformation, and that of the receiver is to use a Bayes estimator. Index Terms: Gaussian processes Radio communication countermeasures ----- Graph theoretic approaches to the code construction for the two-user multiple- access binary adder channel Kasami, T. Shu Lin Wei, V. Yamamura, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1983 On page(s): 114- 130 Volume: 29, Issue: 1 ISSN: 0018-9448 Abstract: We relate coding for the two-user multiple-access binary adder channel to a problem in graph theory, known as the independent set problem. Graph-theoretic approaches to coding for both synchronized and nonsynchronized two-user adder channels are presented. Using the Tur'an theorem on the independence number of a simple graph, we are able to improve the lower bounds on the achievable rates of uniquely anddelta-decodable codes for the synchronized adder channel derived by Kasami and Lin. We are also able to derive lower bounds on the achievable rates of uniquely decodable codes for the nonsynchronized adder channel. We show that the rates of Deaett-Wolf codes for the nonsynchronized adder channel fall below the bounds. Synchronizing sequences for the nonsynchronized adder channel are constructed. Index Terms: Block coding ----- Correction to 'Wyner- Ziv theory for a general function of the correlated sources' (Sep 82 803-807) Yamamoto, H. Page(s): 320- 320 [Abstract] [PDF Full-Text (80 KB)] ----- Writing on dirty paper (Corresp.) Costa, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1983 On page(s): 439- 441 Volume: 29, Issue: 3 ISSN: 0018-9448 Abstract: A channel with outputY = X + S + Zis examined, The stateS sim N(0, QI)and the noiseZ sim N(0, NI)are multivariate Gaussian random variables (Iis the identity matrix.). The inputX in R^{n}satisfies the power constraint(l/n) sum_{i=1}^{n}X_{i}^{2} leq P. IfSis unknown to both transmitter and receiver then the capacity isfrac{1}{2} ln (1 + P/( N + Q))nats per channel use. However, if the stateSis known to the encoder, the capacity is shown to beC^{ast} =frac{1}{2} ln (1 + P/N), independent ofQ. This is also the capacity of a standard Gaussian channel with signal-to-noise power ratioP/N. Therefore, the stateSdoes not affect the capacity of the channel, even thoughSis unknown to the receiver. It is shown that the optimal transmitter adapts its signal to the stateSrather than attempting to cancel it. Index Terms: Error-correction coding ----- The discrete memoryless multiple access channel with partially cooperating encoders (Corresp.) Willems, F. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1983 On page(s): 441- 445 Volume: 29, Issue: 3 ISSN: 0018-9448 Abstract: We introduce the communication situation in which the encoders of a multiple access channel are partially cooperating. These encoders are connected by communication links with finite capacities, which permit both encoders to communicate with each other. First we give a general definition of such a communication process (conference). Then, by proving a converse and giving an achievability proof, we establish the capacity region of the multiple access channel with partially cooperating encoders. It turns out that the optimal conference is very simple. Index Terms: Not Available ----- Successive encoding of correlated sources Ericson, T. Korner, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1983 On page(s): 390- 395 Volume: 29, Issue: 3 ISSN: 0018-9448 Abstract: The encoding of a discrete memoryless multiple source{( X_{i}, Y_{i})}_{i=1}^{infty}for reconstruction of a sequence{Z_{i}}_{i=1}^{infty}}, withZ_{i} = F( X_{i}, Y_{i}); i = 1,2, cdotsis considered. We require that the encoding should be such that{X_{i}}_{i=1}^{infty}is encoded first without any consideration of{Y_{i}}_{i=1}^{infty}, while in a second part of the encoding, this latter sequence is encoded based on knowledge of the outcome of the first encoding. The resulting scheme is called successive encoding. We find general outer and inner bounds for the corresponding set of achievable rates along with a complete single letter characterization for the special caseH( X_{i}|Z_{i}, Y_{i}) = 0. Comparisons with the Slepian-Wolf problem and the Ahlswede-Korner-Wyner side information problem are carried out. Index Terms: Source coding ----- On source coding with side information via a multiple-access channel and related problems in multi-user information theory Ahlswede, R. Te Han This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1983 On page(s): 396- 412 Volume: 29, Issue: 3 ISSN: 0018-9448 Abstract: A simple proof of the coding theorem for the multiple-access channel (MAC) with arbitrarily correlated sources (DMCS) of Cover-El Carnal-Salehi, which includes the results of Ahlswede for the MAC and of Slepian-Wolf for the DMCS and the MAC as special cases, is first given. A coding theorem is introduced and established for another type of source-channel matching problem, i.e., a system of source coding with side information via a MAC, which can be regarded as an extension of the Ahlswede-Körner-Wyner type noiseless coding system. This result is extended to a more general system with several principal sources and several side information sources subject to cross observation at the encoders in the sense of Han. The regions are shown to be optimal in special situations. Dueck's example shows that this is in general not the case for the result of Cover-El Gamal-Salehi and the present work. In another direction, the achievable rate region for the module-two sum source network found by Körner-Marton is improved. Finally, some ideas about a new approach to the source-channel matching problem in multi-user communication theory are presented. The basic concept is that of a correlated channel code. The approach leads to several new coding problems. Index Terms: Source coding ----- A universal data compression system Rissanen, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1983 On page(s): 656- 664 Volume: 29, Issue: 5 ISSN: 0018-9448 Abstract: A universal data compression algorithm is described which is capable of compressing long strings generated by a "finitely generated" source, with a near optimum per symbol length without prior knowledge of the source. This class of sources may be viewed as a generalization of Markov sources to random fields. Moreover, the algorithm does not require a working storage much larger than that needed to describe the source generating parameters. Index Terms: Source coding ----- A simple proof of the Ahlswede - Csiszár one-bit theorem (Corresp.) Gamal, A.E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1983 On page(s): 931- 933 Volume: 29, Issue: 6 ISSN: 0018-9448 Abstract: It is proved that if(X,Y)are two finite alphabet correlated sources withp(x,y)>0for all(x,y) in ({cal X} times {cal Y}), and if a functionF(X,Y)isalpha-sensitive, then the rateRof transmission fromXtoYnecessary to computeF(X,Y)reliably must be greater thanH(X|Y). The same result holds if the function is highly sensitive and for everyx_{1} neq x_{2} in {cal X}, then the number of elementsy in {cal Y}withp(x_{l},y) cdot p(x_{2}, y)>0is different from one. Index Terms: Information rates Source coding ----- Dominance--A relation between distortion measures Stjernvall, J.-E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1983 On page(s): 798- 807 Volume: 29, Issue: 6 ISSN: 0018-9448 Abstract: A relation between distortion measures for source coding, called dominance, is defined so that ifd_{1}andd_{2}are two distortion measures andd_{1}dominatesd_{2}, then a source coding system which meets the distortion criterion(d_{l}, Delta)simply yields a system meeting the distortion criterion(d_{2}, Delta)by a simple change of decoder. It is shown that a very simple characterization of dominance can be given in terms of the characteristic sets of the distortion measures. The characteristic set of a distortion matrix is defined as the sum of the convex hull of the columns of the matrix and the nonnegative orthant. If two distortion measures have the same characteristic set they are regarded as equivalent. It is shown that the definition of dominance is robust in the sense that some alternative definitions are equivalent to the given one. The definition of dominance is extended to the case where a pair of distortion measures dominates a third distortion measure. Here a simple characterization is given in terms of the characteristic sets of the distortion measures. Index Terms: Rate-distortion theory Source coding ----- A general coding scheme for the two-way channel Te Han This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1984 On page(s): 35- 44 Volume: 30, Issue: 1 ISSN: 0018-9448 Abstract: A general coding scheme for the nonrestricted memoryless discrete two-way channel is presented based on the introduction of auxiliary random variables forming a stationary Markov process. The coding scheme yields an achievable rate region which exceeds the inner bound of Shannon in the general case. A finite cardinality bound for the auxiliary random variables is given, showing that the region is computable. Finally, the capacity region for the memoryless Gaussian two-way channel is established. Index Terms: Multiuser channels ----- Robust Wiener- Kolmogorov theory Vastola, K. Poor, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1984 On page(s): 316- 327 Volume: 30, Issue: 2 ISSN: 0018-9448 Abstract: A minimax formulation is considered for the problem of designing robust linear causal estimators of linear functions of discrete-time wide-sense stationary signals when knowledge of the signal and/or noise spectra is inexact. The solution is given (under mild regularity conditions) in terms of a least favorable pair of spectra, thus reducing the minimax problem to a direct maximization problem which in many cases can be solved easily. It is noted that this design method leads, in particular, to robustn-step predictors, robust causal filters, and robustn-lag smoothers. The method of design is illustrated by a thorough development of the special case of one-step noiseless prediction. Further, solutions are given explicitly for the problem of robust causal filtering of an uncertain signal in white noise, and numerical examples are given for this case which illustrate the effectiveness of this design. Index Terms: Minimax estimation ----- On minimax robustness: A general approach and applications Verdu, S. Poor, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1984 On page(s): 328- 340 Volume: 30, Issue: 2 ISSN: 0018-9448 Abstract: The minimax approach to the design of systems that are robust with respect to modeling uncertainties is studied using a game theoretic formulation in which the performance functional and the sets of modeling uncertainties and admissible design policies are arbitrary. The existence and characterization of minimax robust solutions that form saddle points are discussed through various methods that take into account several common features of the games encountered in applications. In particular, it is shown that if the performance functional and the uncertainty set are convex then a certain type of regularity condition on the functional is sufficient to ensure that the optimal strategy for a least favorable element of the uncertainty set is minimax robust. The efficacy of the methods proposed for a general game is tested in the problems of matched filtering, Wiener filtering, quadratic detection, and output energy filtering, in which uncertainties in their respective signal and noise models are assumed to exist. These problems are analyzed in a common Hilbert space framework and they serve to point out the advantages and limitations of the proposed techniques. Index Terms: Game theory Minimax optimization Robustness ------ Fixed-rate encoding of individual sequences with side information Ziv, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1984 On page(s): 348- 352 Volume: 30, Issue: 2 ISSN: 0018-9448 Abstract: For every infinite sequencexand a given side-information sequencey, we define a qualityH(x|y)called the finite-state conditional complexity ofxgiveny. It is shown thatH(x|y)is the smallest asymptotically attainable fixed-rate at whichxcan be transmitted with negligibly small distortion, giveny. Moreover, it is demonstrated that in order to achieve an arbitrary small distortion for all sequences such thatH(x|y)is less than the allowable transmission rate it is not necessary for the encoder to have access to the side-information sequencey(provided it is available to the decoder). This result is a generalization of the classical Slepian-Wolf result for cases where the probabilistic characterization ofxandyis not known, or does not exist. Index Terms: Source coding ----- An achievable region and outer bound for the Gaussian broadcast channel with feedback (Corresp.) Ozarow, L. Leung-Yan-Cheong, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1984 On page(s): 667- 671 Volume: 30, Issue: 4 ISSN: 0018-9448 Abstract: A deterministic coding scheme is presented for additive white Gaussian broadcast channels with two receivers and feedback from the receivers to the transmitter. The region of data rates at which reliable communication is possible is larger than that of the corresponding channel without feedback. This is the first example showing that the capacity region of degraded broadcast channels can be enlarged with feedback. Index Terms: Broadcast channels Feedback communication ----- Self-synchronizing Huffman codes (Corresp.) Ferguson, T. Rabinowitz, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1984 On page(s): 687- 693 Volume: 30, Issue: 4 ISSN: 0018-9448 Abstract: A problem associated with the use of variable-length source codes is that loss of synchronization may lead to extended errors in the decoded text. In this correspondence it is shown that some binary Huffman codes contain a codeword that resynchronizes the decoder regardless of the synchronization slippage preceding that codeword. Such codes are self-synchronizing in a probabilistic sense, yet require no additional system overhead. Some sufficient conditions are found for the existence or nonexistence of self-synchronizing Huffman codes for many classes of source probabilities. One of our results shows that many common languages can be encoded with self-synchronizing Huffman codes. Index Terms: Huffman coding ----- The capacity of the white Gaussian multiple access channel with feedback Ozarow, L. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1984 On page(s): 623- 629 Volume: 30, Issue: 4 ISSN: 0018-9448 Abstract: Since the appearance of [10] by Gaarder and Wolf, it has been well known that feedback can enlarge the capacity region of the multiple access channel. In this paper a deterministic feedback code is presented for the two-user Gaussian multiple access channel, which is shown to allow reliable communication at all points inside a region larger than any previously obtained. An outer bound is given which is shown to coincide with the achievable region, thus yielding the capacity region of this channel exactly. Index Terms: Feedback communication Multiaccess communication ----- Universal coding, information, prediction, and estimation Rissanen, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1984 On page(s): 629- 636 Volume: 30, Issue: 4 ISSN: 0018-9448 Abstract: A connection between universal codes and the problems of prediction and statistical estimation is established. A known lower bound for the mean length of universal codes is sharpened and generalized, and optimum universal codes constructed. The bound is defined to give the information in strings relative to the considered class of processes. The earlier derived minimum description length criterion for estimation of parameters, including their number, is given a fundamental information, theoretic justification by showing that its estimators achieve the information in the strings. It is also shown that one cannot do prediction in Gaussian autoregressive moving average (ARMA) processes below a bound, which is determined by the information in the data. Index Terms: Information theory Parameter estimation Prediction methods Source coding ------ Relationship between the Karhunen- Loéve transform and the Courant - Fischer theorem (Corresp.) Delsarte, P. Kamp, Y. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1984 On page(s): 662- 664 Volume: 30, Issue: 4 ISSN: 0018-9448 Abstract: It is shown that the Karhunen-Loève transform problem can be formulated as a matrix approximation problem with Hilbert-Schmidt error norm. On the other hand, the Courant-Fischer minimax theorem provides a characterization for the best matrix approximation when the spectral norm is used. It appears that the optimality conditions of the Karhunen-Loève problem lead to the selection of a particular solution among the set of solutions to the Courant-Fischer problem. Index Terms: Karhunen-Loeve transforms Matrices Minimax approximation ----- Coin flipping by telephone (Corresp.) Reyneri, J. Karnin, E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1984 On page(s): 775- 776 Volume: 30, Issue: 5 ISSN: 0018-9448 Abstract: Two parties, who do not trust each other, wish to agree on the result of a coin toss while they are conversing by telephone. A new protocol which solves this problem is proposed and compared with previous protocols. Index Terms: Cryptography ----- On the similarity of the entropy power inequality and the Brunn- Minkowski inequality (Corresp.) Costa, M. Cover, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1984 On page(s): 837- 839 Volume: 30, Issue: 6 ISSN: 0018-9448 Abstract: The entropy power inequality states that the effective variance (entropy power) of the sum of two independent random variables is greater than the sum of their effective variances. The Brunn-Minkowski inequality states that the effective radius of the set sum of two sets is greater than the sum of their effective radii. Both these inequalities are recast in a form that enhances their similarity. In spite of this similarity, there is as yet no common proof of the inequalities. Nevertheless, their intriguing similarity suggests that new results relating to entropies from known results in geometry and vice versa may be found. Two applications of this reasoning are presented. First, an isoperimetric inequality for entropy is proved that shows that the spherical normal distribution minimizes the trace of the Fisher information matrix given an entropy constraint--just as a sphere minimizes the surface area given a volume constraint. Second, a theorem involving the effective radii of growing convex sets is proved. Index Terms: Entropy Geometry Set theory ----- The collision channel without feedback Massey, J. Mathys, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1985 On page(s): 192- 204 Volume: 31, Issue: 2 ISSN: 0018-9448 Abstract: A model is proposed for the situation whereMusers share a common communication resource but, because of unknown time offsets among their clocks, cannot transmit their data packets in a time-sharing mode and, because of the lack of a feedback link, can never determine these time offsets and also can never be sure of the outcomes of their individual packet transmissions. Each user is required to make his packet transmissions at times determined by a protocol signal that is independent of the data to be sent. The capacity and zero-error capacity regions of this channel are determined for both the unsynchronized and slot-synchronized cases; these four regions are shown to coincide. It is further shown that a dense set of rate points on the outer boundary of this region can be achieved in the slot-synchronized case. Specific constructions of protocol sequences for achieving these points are given, and the technique of "decimation decoding" is introduced for identifying the sender of each successfully transmitted packet. Maximum-erasure burst-correcting codes over an alphabet of arbitrary size are constructed and shown to suffice for reconstructing the packets lost in "collisions" when these protocol sequences are used. Index Terms: Packet switching ----- The capacity region of the totally asynchronous multiple-access channel Hui, J. Humblet, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1985 On page(s): 207- 216 Volume: 31, Issue: 2 ISSN: 0018-9448 Abstract: It is shown that the capacity region of the asynchronous multiple-access channel differs from that of the synchronous channel only by the lack of a convex hull operation. Index Terms: Multiaccess communication ----- A perspective on multiaccess channels Gallager, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1985 On page(s): 124- 142 Volume: 31, Issue: 2 ISSN: 0018-9448 Abstract: The information theoretic approach and the collision resolution approach to multiaccess channels are reviewed in terms of the underlying communication problems that both are modeling. Some perspective on the strengths and weakness of these approaches is given, and the need of a more combined approach focused on coding and decoding techniques is argued. Index Terms: Bibliographies CDMA (code-division multiple-access) Code division multiaccess (CDMA) Code-division multiple-access Multiaccess communication Packet switching ----- Born again group testing: Multiaccess communications Wolf, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1985 On page(s): 185- 191 Volume: 31, Issue: 2 ISSN: 0018-9448 Abstract: A brief summary of the basic notions of group testing is presented together with a brief historical account. One of the early papers on group testing is shown to include a description of the tree-search polling algorithm of Hayes. The classical group testing problem is formulated, including a criterion for optimality of test plans. A restricted class of tests, called nested testing, is described, and a complete description for an optimal nested strategy is given for both a finite number and an infinite number of Bernoulli distributed random variables. A generalization of group testing applicable to the random access communications problem is presented. Index Terms: Multiaccess communication Testing ----- The discrete memoryless multiple-access channel with cribbing encoders Willems, F. van der Meulen, E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1985 On page(s): 313- 327 Volume: 31, Issue: 3 ISSN: 0018-9448 Abstract: The capacity regions are determined for various communication situations in which one or both encoders for a multiple access channel crib from the other encoder and learn the channel input(s) (to be) emitted by this encoder. Most of the achievability proofs in this paper hinge upon the new concept of backward decoding. Also, the notion of Shannon strategies seems to be of crucial importance. It is demonstrated that in some situations parts of the total cooperation line are achievable. Moreover, it is proved that if the encoders and the decoder are allowed to be nondeterministic, the capacity regions are not increased. Index Terms: Coding/decoding Multiaccess communication ----- On the Gaussian interference channel Costa, M. Stanford University, Standford, CA, USA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1985 On page(s): 607- 615 Volume: 31, Issue: 5 ISSN: 0018-9448 Abstract: The determination of the capacity region of the Gaussian interference channel remains an open problem. The channel model is described and cases that have been solved by other researchers are summarized. The optimality is established of two extreme points in the achievable region of the general Gaussian interference channel. It is proved that the class of degraded Gaussian interference channels is equivalent to the class ofZ(one-sided) interference channels. Index Terms: Cochannel interference Gaussian processes ----- The rate-distortion region for multiple descriptions without excess rate Ahlswede, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1985 On page(s): 721- 726 Volume: 31, Issue: 6 ISSN: 0018-9448 Abstract: During recent years there has been strong interest in a certain source coding problem, which some authors call the "problem of multiple descriptions." Old and new wringing techniques enable us to establish a single-letter characterization of the rate-distortion region in the case of no excess rate for the joint description. Index Terms: Rate-distortion theory ----- Rate distortion when side information may be absent Heegard, C. Berger, T. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1985 On page(s): 727- 734 Volume: 31, Issue: 6 ISSN: 0018-9448 Abstract: 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. ----- Random coding bound and codes produced by permutations for the multiple-access channel Pokorny, J. Wallmeier, H. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1985 On page(s): 741- 750 Volume: 31, Issue: 6 ISSN: 0018-9448 Abstract: A random coding bound for the multiple-access channel (MAC) is given, and it is shown to be obtainable universally for all MAC's with common input and output alphabets. For channels for which the random coding bound may be achieved by codes consisting of codewords of a single type for each sender, this bound is also achievable by codes produced by permutations. Index Terms: Coding/decoding Multiaccess communication Permutation coding ----- A new entropy power inequality Costa, M. Stanford University, Stanford, CA, USA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1985 On page(s): 751- 760 Volume: 31, Issue: 6 ISSN: 0018-9448 Abstract: A strengthened version of Shannon's entropy power inequality for the case where one of the random vectors involved is Gaussian is proved. In particular it is shown that if independent Gaussian noise is added to an arbitrary, multivariate random variable, the entropy power of the resulting random variable is a concave function of the variance (power) of the added noise. The strengthened inequality is shown to hold for the class of stable distributions. Index Terms: Entropy Gaussian processes ----- Two-way source coding with a fidelity criterion Kaspi, A. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1985 On page(s): 735- 740 Volume: 31, Issue: 6 ISSN: 0018-9448 Abstract: Let(X_{i}, Y_{i}), i= 1,2 cdots, be a sequence of independent, identically distributed bivariate random variables and consider the following communication situation. TheXcomponent of the process is observed at some location, sayA, while theYcomponent is observed at a different location, sayB. TheX(Y)component of the process has to be reproduced at locationB(A). It is desired to find the amount of information that should be exchanged between the two locations, so that the distortions incurred will not exceed some predetermined tolerance. A "single-letter characterization" of a certain region{cal****}^{K} subset {cal R}^{4}of rates and distortions is given. This region contains (all, and only) the achievable rates and distortions for the special case where block coding is used and the information is conveyed through a one-way link that can switch direction onlyKtimes per block. Index Terms: Source coding ----- Minimum probability of error for asynchronous Gaussian multiple-access channels Verdu, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1986 On page(s): 85- 96 Volume: 32, Issue: 1 ISSN: 0018-9448 Abstract: Consider a Gaussian multiple-access channel shared byKusers who transmit asynchronously independent data streams by modulating a set of assigned signal waveforms. The uncoded probability of error achievable by optimum multiuser detectors is investigated. It is shown that theK-user maximum-likelihood sequence detector consists of a bank of single-user matched filters followed by a Viterbi algorithm whose complexity per binary decision isO(2^{K}). The upper bound analysis of this detector follows an approach based on the decomposition of error sequences. The issues of convergence and tightness of the bounds are examined, and it is shown that the minimum multiuser error probability is equivalent in the Iow-noise region to that of a single-user system with reduced power. These results show that the proposed multiuser detectors afford important performance gains over conventional single-user systems, in which the signal constellation carries the entire burden of complexity required to achieve a given performance level. Index Terms: Multiaccess communication Viterbi decoding maximum-likelihood (ML) estimation ----- Efficient balanced codes Knuth, D. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1986 On page(s): 51- 53 Volume: 32, Issue: 1 ISSN: 0018-9448 Abstract: Coding schemes in which each codeword contains equally many zeros and ones are constructed in such a way that they can be efficiently encoded and decoded. Index Terms: Coding/decoding ----- A note on jackknifing kernel regression function estimators (Corresp.) Hardle, W. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1986 On page(s): 298- 300 Volume: 32, Issue: 2 ISSN: 0018-9448 Abstract: Estimation of the value of a regression function at a point of continuity using a kernel-type estimator is considered and improvements by a jackknife technique are discussed. It is seen that a so-called generalized jackknife estimator asymptotically improves upon an ordinary kernel-type estimator. However, for a fixed sample size the generalized jackknife method may inflate the mean-square error. Index Terms: Estimation ----- Reverse-time Markov processes (Corresp.) Elliott, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1986 On page(s): 290- 292 Volume: 32, Issue: 2 ISSN: 0018-9448 Abstract: The problem of representing a Markov process as a reverse-time Markov process is discussed. Diffusions and finite-state Markov processes are two important classes of Markov processes for which this problem has been considered. A gap in a paper of Castanon is pointed out which discusses diffusions; reverse-time finite and discrete-state Markov processes are then considered using martingale methods. Index Terms: Markov processes ----- An algorithm for detecting a change in a stochastic process Bansal, R. Papantoni-Kazakos, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1986 On page(s): 227- 235 Volume: 32, Issue: 2 ISSN: 0018-9448 Abstract: The problem of detecting a change from one given stationary and ergodic stochastic process to another such process is considered. It is assumed that both stochastic processes are processes with memory and that they are mutually independent. A sequential test is proposed and analyzed. It is proved that the proposed test is asymptotically optimal in a mathematically precise sense. Index Terms: Stochastic processes ----- Rate-distortion bounds for quotient-based distortions with application to Itakura- Saito distortion measures Buzo, A. Kuhlmann, F. Rivera, C. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1986 On page(s): 141- 147 Volume: 32, Issue: 2 ISSN: 0018-9448 Abstract: In many linear predictive coding (LPC) speech compression systems the encoding of the LPC parameters is performed using a product code book scheme. One possible approach consists in organizing the set of LPC reproduction models as the Cartesian product of a vector code book describing the shape of each reproduction LPC model and a scalar codebook describing the gain or energy. We first present a formal development of rate-distortion theoretic results for distortion functions based on quotients of input and reproduction symbols. We also obtain theoretical bounds for the rate-distortion function of the gain term of LPC systems (which, depending on the quantization scheme, can use about10-25percent of the transmission rate), as well as asymptotic (small distortions) approximations to the performance of the optimal scalar quantizer for these gain terms, when the overall fidelity criterion is the Itakura-Saito distortion measure, which is a member of the class of quotient distortion measures. The approximations and bounds are compared finally with experimental results. Index Terms: Rate-distortion theory Speech coding ----- A simple proof of the blowing-up lemma (Corresp.) Marton, K. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1986 On page(s): 445- 446 Volume: 32, Issue: 3 ISSN: 0018-9448 Abstract: The blowing-up lemma says that if the probability with respect to a product measure of a setAsubseteq {cal X}^{n} ({cal X}finite,nlarge) is not exponentially small, then itsl_{n}-neighborhood has probability almost one for somel_{n} = O(n). Here an information-theoretic proof of the blowing-up lemma, generalizing it to continuous alphabets, is given. Index Terms: Information theory ----- New outer bounds to capacity regions of two-way channels Zhen Zhang Berger, T. Schalkwijk, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1986 On page(s): 383- 386 Volume: 32, Issue: 3 ISSN: 0018-9448 Abstract: 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. Index Terms: Information theory ----- Hypothesis testing with communication constraints Ahlswede, R. Csiszar, I. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1986 On page(s): 533- 542 Volume: 32, Issue: 4 ISSN: 0018-9448 Abstract: A new class of statistical problems is introduced, involving the presence of communication constraints on remotely collected data. Bivariate hypothesis testing,H_{0}: P_{XY}againstH_{1}: P_{={XY}}, is considered when the statistician has direct access toYdata but can be informed aboutXdata only at a preseribed finite rateR. For any fixed R the smallest achievable probability of an error of type2with the probability of an error of type1being at mostepsilonis shown to go to zero with an exponential rate not depending onepsilonas the sample size goes to infinity. A single-letter formula for the exponent is given whenP_{={XY}} = P_{X} times P_{Y}(test against independence), and partial results are obtained for generalP_{={XY}}. An application to a search problem of Chernoff is also given. Index Terms: Data compression Decision making Source coding ----- On multiple descriptions and team guessing Ahlswede, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1986 On page(s): 543- 549 Volume: 32, Issue: 4 ISSN: 0018-9448 Abstract: Witsenhausen's hyperbola bound for the multiple description problem without excess rate in case of a binary source is not tight for exact joint reproductions. However, this bound is tight for almost-exact joint reproductions (Theorem1, conjectured by Witsenhausen). The proof is based on an {em approximative} form of the team guessing lemma for {em sequences} of random variables. (This result may be of interest also for team guessing). The hyperbola bound is also tight for exact joint reproductions and arbitrarily small, but positive, excess rate (Theorem2). The proof of this result uses our covering lemma. Index Terms: Distributed decision-making Source coding ----- The complexity of information extraction Abu-Mostafa, Y. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1986 On page(s): 513- 525 Volume: 32, Issue: 4 ISSN: 0018-9448 Abstract: How difficult are decision problems based on natural data, such as pattern recognition? To answer this question, decision problems are characterized by introducing four measures defined on a Boolean functionfofNvariables: the implementation costC(f), the randomnessR(f), the deterministic entropyH(f), and the complexityK(f). The highlights and main results are roughly as follows,l) C(f) approx R(f) H(f) approx K(f), all measured in bits.2)Decision problems based on natural data are partially random (in the Kolmogorov sense) and have low entropy with respect to their dimensionality, and the relations between the four measures translate to lower and upper bounds on the cost of solving these problems.3)Allowing small errors in the implementation offsaves a lot in the iow entropy case but saves nothing in the high-entropy case. Iffis partially structured, the implementation cost is reduced substantially. Index Terms: Boolean functions Decision making ----- Rate distortion theory with generalized information measures via convex programming duality Ben-Tal, A. Teboulle, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1986 On page(s): 630- 641 Volume: 32, Issue: 5 ISSN: 0018-9448 Abstract: A new generalized average mutual information measure (GAMIM) is introduced in terms of Csiszarphi-divergence, and the associated rate distortion functionR_{phi}is studied. The main objective is to derive in a unified way a dual representation ofR_{phi}, then to use it to generalize classical results (corresponding tophi(t) = t log t) in rate distortion theory and extend results associated with other concepts of GAMIM. Our development uses the methodology of convex programming duality extensively. Index Terms: Mathematical programming Source coding ----- Estimating a probability using finite memory Leighton, F. Rivest, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1986 On page(s): 733- 742 Volume: 32, Issue: 6 ISSN: 0018-9448 Abstract: Let{X_{i}}_{i=1}^{infty}be a sequence of independent Bernoulli random variables with probabilitypthatX_{i} = 1and probabilityq=1-pthatX_{i} = 0for alli geq 1. Time-invariant finite-memory (i.e., finite-state) estimation procedures for the parameter p are considered which takeX_{1}, cdotsas an input sequence. In particular, an n-state deterministic estimation procedure is described which can estimate p with mean-square errorO(log n/n)and ann-state probabilistic estimation procedure which can estimatepwith mean-square errorO(1/n). It is proved that theO(1/n)bound is optimal to within a constant factor. In addition, it is shown that linear estimation procedures are just as powerful (up to the measure of mean-square error) as arbitrary estimation procedures. The proofs are based on an analog of the well-known matrix tree theorem that is called the Markov chain tree theorem. Index Terms: Estimation Probability ----- The ergodic and entropy theorems revisited Shields, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1987 On page(s): 263- 266 Volume: 33, Issue: 2 ISSN: 0018-9448 Abstract: A new proof of Birkhoff's ergodic theorem is given using a sample path covering idea, an idea created by Ornstein and Weiss in their extension of the information convergence theorem to random fields. A sketch of the Ornstein-Weiss proof for processes is included in the Appendix. Index Terms: Entropy Statistics Stochastic processes ----- Gaussian arbitrarily varying channels Hughes, B. Narayan, P. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1987 On page(s): 267- 284 Volume: 33, Issue: 2 ISSN: 0018-9448 Abstract: The {em arbitrarily varying channel} (AVC) can be interpreted as a model of a channel jammed by an intelligent and unpredictable adversary. We investigate the asymptotic reliability of optimal random block codes on Gaussian arbitrarily varying channels (GAVC's). A GAVC is a discrete-time memoryless Gaussian channel with input power constraintP_{T}and noise powerN_{e}, which is further corrupted by an additive "jamming signal." The statistics of this signal are unknown and may be arbitrary, except that they are subject to a power constraintP_{J}. We distinguish between two types of power constraints: {em peak} and {em average.} For peak constraints on the input power and the jamming power we show that the GAVC has a random coding capacity. For the remaining cases in which either the transmitter or the jammer or both are subject to average power constraints, no capacities exist and onlylambda-capacities are found. The asymptotic error probability suffered by optimal random codes in these cases is determined. Our results suggest that if the jammer is subject only to an average power constraint, reliable communication is impossible at any positive code rate. Index Terms: Block coding Gaussian processes Random coding ----- New results on the real-time transmission problem Engell, S. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1987 On page(s): 210- 218 Volume: 33, Issue: 2 ISSN: 0018-9448 Abstract: A new concept is presented for the treatment of real-time transmission problems. It basically consists of a modification of the flow of information. The resulting quantity, which we call the forward flow of information, is smaller than the flow of information according to the usual definition except for special cases. We derive various negative coding theorems in which the forward flow of information is used. These bounds are sharper than those previously known for transmission with finite delay. Index Terms: Delay effects Information rates Source coding ----- The rate-distortion function of a binary symmetric source when side information may be absent (Corresp.) Kerpez, K. This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1987 On page(s): 448- 452 Volume: 33, Issue: 3 ISSN: 0018-9448 Abstract: A binary symmetric source with binary side information is given. An encoder codes the source for data compression with no knowledge of the side information. It is then decoded, perhaps with and perhaps without the presence of side information. The rate-distortion function of this scheme is a function of two variables:D_{1}is the distortion when side information is present at the decoder, and D2 is the distortion when side information is absent at the decoder. The rate-distortion function is shown to reduce to previously solved problems in much of the(D_{1}, D_{2})-plane. Tight upper and lower bounds are found for the rate-distortion function in the rest of the(D_{1}, D_{2})-plane. Index Terms: Rate-distortion theory ----- The capacity region of the discrete memoryless interference channel with strong interference (Corresp.) Costa, M. Gamal, A.E. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1987 On page(s): 710- 711 Volume: 33, Issue: 5 ISSN: 0018-9448 Abstract: The capacity region of the discrete memoryless interference channel with strong interference is established. Index Terms: Interference Multiuser channels ----- Feedback can at most double Gaussian multiple access channel capacity (Corresp.) Thomas, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1987 On page(s): 711- 716 Volume: 33, Issue: 5 ISSN: 0018-9448 Abstract: The converse for the discrete memoryless multiple access channel is generalized and is used to derive strong bounds on the total capacity (sum of the rates of all the senders) of anm-user Gaussian multiple access channel in terms of the input covariance matrix. These bounds are used to show that the total capacity of the channel with feedback is less than twice the total capacity without feedback. The converse for the general multiple access channel is also used to show that for anym-user multiple access channel, feedback cannot increase the total capacity by more than a factor ofm. Index Terms: Multiaccess communication ----- Broadcast channels with arbitrarily correlated sources Te Han Costa, M. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1987 On page(s): 641- 650 Volume: 33, Issue: 5 ISSN: 0018-9448 Abstract: A new coding theorem for the broadcast channel with arbitrarily correlated sources is presented. The result covers all the previously established coding techniques. In particular, it includes Marton's coding theorem as a properly special case. Index Terms: Broadcast channels Coding/decoding Source coding ----- Ergodicity of Markov channels Gray, R. Dunham, M. Gobbi, R. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1987 On page(s): 656- 664 Volume: 33, Issue: 5 ISSN: 0018-9448 Abstract: A Markov channel is a discrete information channel that includes as special cases the finite state channels and finite state codes of information theory. Kieffer and Rahe proved that one-sided and two-sided Markov channels have the following property: If the input source to a Markov channel is asymptotically mean stationary (AMS), then so is the resulting input-output process and hence the ergodic theorem and the Shannon-McMillan-Breiman theorem hold for the input-output process. Kieffer and Rahe also provided a sufficient condition for any AMS ergodic source to yield an AMS ergodic input-output process. New conditions for a Markov channel to have this ergodicity property are presented and discussed here. Several relations are developed among various classes of channels, including weakly ergodic, indecomposable, and strongly mixing channels. Some connections between Markov channels and the theory of nonhomogeneous Markov chains are also discussed. Index Terms: Coding/decoding Markov processes ----- Capacity of the mismatched Gaussian channel Baker, C. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1987 On page(s): 802- 812 Volume: 33, Issue: 6 ISSN: 0018-9448 Abstract: Information capacity is determined for the additive Gaussian channel when the constraint is given in terms of a covariance different from that of the channel noise. These results, combined with previous results on capacity when the constraint covariance is the same as the noise covariance, provide a complete and general solution for the information capacity of the Gaussian channel without feedback. The results are valid for both continuous-time and discrete-time channels and require only two assumptions: the noise is due to a stochastic process with sample paths having finite energy over the observation period (w.p.1), and the constraint is given in terms of a Hilbert space norm. Such a constraint is implicit in any constraint giving finite capacity. Index Terms: Covariance analysis Gaussian processes Information rates ----- The source coding theorem via Sanov's theorem (Corresp.) Bucklew, J. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1987 On page(s): 907- 909 Volume: 33, Issue: 6 ISSN: 0018-9448 Abstract: A proof of Shannon's source coding theorem is given using results from large deviation theory. In particular Sanov's theorem on convergence rates for empirical distributions is invoked to obtain the key large deviation result. This result is used directly to prove the source coding theorem for discrete memoryless sources. It is then shown how this theorem can be extended to ergodic Polish space valued sources and continuous distortion measures. Index Terms: Probability Source coding ----- Conditional limit theorems under Markov conditioning Csiszar, I. Cover, T. Byoung-Seon Choi This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1987 On page(s): 788- 801 Volume: 33, Issue: 6 ISSN: 0018-9448 Abstract: Let X_{1},X_{2},cdotsbe independent identically distributed random variables taking values in a finite setXand consider the conditional joint distribution of the first m elements of the sampleX_{1},cdots , X_{n}on the condition thatX_{1}=x_{1}and the sliding block sample average of a functionh(cdot , cdot)defined onX^{2}exceeds a thresholdalpha > Eh(X_{1}, X_{2}). Formfixed andn rightarrow infty, this conditional joint distribution is shown to converge m them-step joint distribution of a Markov chain started inx_{1}which is closest toX_{l}, X_{2}, cdotsin Kullback-Leibler information divergence among all Markov chains whose two-dimensional stationary distributionP(cdot , cdot)satisfiessum P(x, y)h(x, y)geq alpha, provided some distributionPonX_{2}having equal marginals does satisfy this constraint with strict inequality. Similar conditional limit theorems are obtained whenX_{1}, X_{2},cdotsis an arbitrary finite-order Markov chain and more general conditioning is allowed. Index Terms: Information theory Markov processes Maximum-entropy methods ----- Totally asynchronous Slepian-Wolf data compression Willems, F.M.J. Dept. of Electr. Eng., Eindhoven Univ. of Technol. ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1988 On page(s): 35-44 Volume: 34, Issue: 1 ISSN: 0018-9448 References Cited: 13 CODEN: IETTAW INSPEC Accession Number: 3171725 Abstract: It is proved that the Slepian-Wolf data compression theorem still holds when both encoders are operating totally asynchronously. In addition it is shown that in this case the Wyner-Ahlswede-Korner source-coding theorem holds Index Terms: data compression encoding Slepian-Wolf data compression theorem Wyner-Ahlswede-Korner source-coding theorem encoders totally asynchronous encoding ----- Finding parity in a simple broadcast network Gallager, R.G. Lab. for Inf. & Decision Syst., MIT, Cambridge, MA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1988 On page(s): 176-180 Volume: 34, Issue: 2 ISSN: 0018-9448 References Cited: 4 CODEN: IETTAW INSPEC Accession Number: 3232590 Abstract: A broadcast network of N+1 nodes is considered in which each binary digit transmitted by each node is received by every other node via a binary symmetric channel of given transition probability. The errors on these channels are independent over transmitters, receivers and time. Each node has a binary state, and the problem is to construct a distributed algorithm to find the parity of the set of states with some given reliability. It is shown that this can be done with O(ln(ln N)) bits of communication from each node. Communicating all the node states to one node can be accomplished with only marginally more communication Index Terms: information theory telecommunication networks binary symmetric channel broadcast network distributed algorithm parity telecommunication network transition probability ----- Estimation via compressed information Zhang, Z. Berger, T. Dept. of Math., Bielefeld Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1988 On page(s): 198-211 Volume: 34, Issue: 2 ISSN: 0018-9448 References Cited: 17 CODEN: IETTAW INSPEC Accession Number: 3232593 Abstract: 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 Index Terms: data compression estimation theory information theory Gaussian sources communication rates compressed information estimation theory unbiased estimator ----- Poisson models and mean-squared error for correlator estimator of time delay Hero, A.O. Schwartz, S.C. Dept. of Electr. Eng., & Comput. Sci., Michigan Univ., Ann Arbor, MI; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1988 On page(s): 287-303 Volume: 34, Issue: 2 ISSN: 0018-9448 References Cited: 21 CODEN: IETTAW INSPEC Accession Number: 3232601 Abstract: A method for modeling large errors in correlation-based time-delay estimation is developed in terms of level-crossing probabilities. The level-crossing interpretation for peak ambiguity leads directly to an exact expression for the probability of large error involving the hazard function associated with the level-crossing process. Two models for the distribution of the error over the level-crossing time yield approximations to the mean-square error (MSE) that involve the low-order (<4) finite-dimensional distributions of the associated level-crossing process. Application of an inhomogeneous Poisson model for the level crossings reduces the form of the approximations to a weighted sum of the Cramer-Rao lower bound and the second moment of a function of the level-crossing intensity over time. Explicit expressions for the large error probability and the MSE approximations are obtained under a Gaussian model for the correlator statistics. Results of computer simulation are presented that indicate the accuracy of the approximations Index Terms: correlators delays error statistics estimation theory information theory probability signal processing Cramer-Rao lower bound Gaussian model MSE approximations Poisson models correlator estimator error probability hazard function level-crossing probabilities mean-squared error signal processing time-delay estimation ----- Random access communication and graph entropy Korner, J. Marton, K. Math. Inst. of Hungarian Acad. of Sci., Budapest ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1988 On page(s): 312-314 Volume: 34, Issue: 2 ISSN: 0018-9448 References Cited: 7 CODEN: IETTAW INSPEC Accession Number: 3232603 Abstract: A probabilistic problem that arises for conflict resolution in random-access communication is treated. An earlier conjecture is disproved and a technique for finding lower bounds on the number of graphs of given structure needed to cover all edges of a given graph is developed Index Terms: entropy graph theory information theory probability conflict resolution graph entropy lower bounds probabilistic problem random-access communication ----- Bounds on the extreme eigenvalues of positive-definite Toeplitz matrices Dembo, A. Dept. of Electr. Eng., Technion, Israel Inst. of Technol., Haifa; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1988 On page(s): 352-355 Volume: 34, Issue: 2 ISSN: 0018-9448 References Cited: 13 CODEN: IETTAW INSPEC Accession Number: 3232615 Abstract: Easily computable bounds on the extreme eigenvalues of positive semidefinite (PSD) Toeplitz matrices are presented. The bounds are especially suitable for matrices of relatively small dimension. The bounds are derived for the wider class of PSD Hermitian matrices and interpreted via the Levinson-Durbin Algorithm for Toeplitz matrices. As a by-product of this derivation an order-recursive algorithm for the eigenvector/eigenvalue decomposition is obtained, and certain properties of the eigenvalues distribution are revealed Index Terms: eigenvalues and eigenfunctions matrix algebra Hermitian matrices Levinson-Durbin Algorithm bounds eigenvector/eigenvalue decomposition extreme eigenvalues order-recursive algorithm positive-definite Toeplitz matrices ----- Achievable rates for a constrained Gaussian channel Ozarow, L.H. Wyner, A.D. Ziv, J. AT&T Bell Lab., Murray Hill, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1988 On page(s): 365-370 Volume: 34, Issue: 3 ISSN: 0018-9448 References Cited: 3 CODEN: IETTAW INSPEC Accession Number: 3291229 Abstract: The authors obtained lower bounds to the capacity of the continuous-time filtered additive Gaussian noise channel with two-valued inputs. Essentially, the problem reduces to the continuous-time peak-limited case, which remains an unsolved problem of primary importance in communication theory Index Terms: channel capacity filtering and prediction theory information theory telecommunication channels achievable rates additive Gaussian noise channel channel capacity communication theory constrained Gaussian channel continuous-time filtered channel lower bounds ----- A rate-distortion problem for a communication system with a secondary decoder to be hindered Yamamoto, H. Dept. of Commun. Syst., Univ. of Electro-Communications, Chofu, Tokyo; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1988 On page(s): 835-842 Volume: 34, Issue: 4 ISSN: 0018-9448 References Cited: 10 CODEN: IETTAW INSPEC Accession Number: 3310129 Abstract: A rate-distortion problem is considered for a communication system (f, ?1) with a secondary decoder ?2 to be hindered which uses a different distortion measure from the primary system. The least achievable distortion of the secondary decoder is evaluated for the most secure primary system. Source coding for sources with additional outputs to be kept secret from the receiver or wiretappers is also discussed. Security is evaluated by distortion measures instead of the equivocation function used by H. Tamamoto (1983) Index Terms: decoding encoding information theory telecommunication systems communication system rate-distortion problem secondary decoder secure primary system security source coding wiretappers ----- Partial converse for a relay channel Zhen Zhang Inf. Syst. Lab., Stanford Univ., CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1988 On page(s): 1106-1110 Volume: 34, Issue: 5 ISSN: 0018-9448 References Cited: 6 CODEN: IETTAW INSPEC Accession Number: 3375788 Abstract: A special case of the general discrete memoryless relay channel is studied. This channel consists of an input x, a relay output z, a channel output y, and a noiseless channel of capacity Cr allowing the relay sender to send additional information to the decoder. The channel is described by a collection of distributions {p(y, z|x)}. The decoder uses the channel output y and a function f(z) of the relay output at a rate no greater than Cr to recover the message. Some results on the capacity of the channel are obtained Index Terms: decoding information theory noise telecommunication channels decoder general discrete memoryless relay channel message noiseless channel partial converse ----- The Renyi redundancy of generalized Huffman codes Blumer, A.C. McEliece, R.J. Dept. of Comput. Sci., Tufts Univ., Medford, MA ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1988 On page(s): 1242-1249 Volume: 34, Issue: 5 ISSN: 0018-9448 References Cited: 12 CODEN: IETTAW INSPEC Accession Number: 3375796 Abstract: Huffman's algorithm gives optimal codes, as measured by average codeword length, and the redundancy can be measured as the difference between the average codeword length and Shannon's entropy. If the objective function is replaced by an exponentially weighted average, then a simple modification of Huffman's algorithm gives optimal codes. The redundancy can now be measured as the difference between this new average and A. Renyi's (1961) generalization of Shannon's entropy. By decreasing some of the codeword lengths in a Shannon code, the upper bound on the redundancy given in the standard proof of the noiseless source coding theorem is improved. The lower bound is improved by randomizing between codeword lengths, allowing linear programming techniques to be used on an integer programming problem. These bounds are shown to be asymptotically equal. The results are generalized to the Renyi case and are related to R.G. Gallager's (1978) bound on the redundancy of Huffman codes Index Terms: boundary-value problems codes encoding Huffman codes Renyi redundancy Shannon code average codeword length entropy exponentially weighted average linear programming noiseless source coding theorem objective function optimal codes upper bound ----- Retrials and balks (queueing) Gilbert, E.N. AT&T Bell Lab., Murray Hill, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1988 On page(s): 1502-1508 Volume: 34, Issue: 6 ISSN: 0018-9448 References Cited: 21 CODEN: IETTAW INSPEC Accession Number: 3393621 Abstract: An overloaded service system may reject customers if it has no queue to store them. In practice, rejected customers return later to make retrials and may not leave permanently (balk) until several retrials fail. A single-server system with Poisson arrivals is examined in which rejected customers balk or make retrials according to a simple probabilistic model. Customer service times are independent random variables, all with the same given distribution function b(t). The stationary probability distribution for the number of customers waiting to make retrials satisfies a complicated functional equation. The solution is elusive in general but can be obtained for special b(t) (exponential distribution) or special values of model parameters. When the solution cannot be found, bounds on the fraction of customers served can be obtained Index Terms: probability queueing theory random processes Poisson arrivals balks functional equation independent random variables overloaded service system queue rejected customers retrials simple probabilistic model single-server system stationary probability distribution ----- Identification via channels Ahlswede, R. Dueck, G. Bielefeld Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1989 On page(s): 15-29 Volume: 35, Issue: 1 ISSN: 0018-9448 References Cited: 6 CODEN: IETTAW INSPEC Accession Number: 3444290 Abstract: The authors' main finding is that any object among doubly exponentially many objects can be identified in blocklength n with arbitrarily small error probability via a discrete memoryless channel (DMC), if randomization can be used for the encoding procedure. A novel doubly exponential coding theorem is presented which determines the optimal R, that is, the identification capacity of the DMC as a function of its transmission probability matrix. This identification capacity is a well-known quantity, namely, Shannon's transmission capacity for the DMC Index Terms: channel capacity encoding identification information theory probability telecommunication channels Shannon's transmission capacity discrete memoryless channel doubly exponential coding theorem encoding error probability identification capacity information theory transmission probability matrix ----- Identification in the presence of feedback-a discovery of new capacity formulas Ahlswede, R. Dueck, G. Bielefeld Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1989 On page(s): 30-36 Volume: 35, Issue: 1 ISSN: 0018-9448 References Cited: 5 CODEN: IETTAW INSPEC Accession Number: 3444291 Abstract: A study is made of the identification problem in the presence of a noiseless feedback channel, and the second-order capacity Cf (resp. CF) for deterministic (resp. randomized) encoding strategies is determined. Several important phenomena are encountered. (1) Although feedback does not increase the transmission capacity of a discrete memoryless channel (DMC), it does increase the (second-order) identification capacity; (2) noise increases Cf; (3) the structure of the new capacity formulas is simpler than C.E. Shannon's (1948) familiar formula. This has the effect that proofs of converses become easier than in the authors' previous work Index Terms: channel capacity encoding feedback identification information theory telecommunication channels deterministic encoding identification capacity identification problem information theory noiseless feedback channel second-order capacity transmission capacity ----- Gaussian feedback capacity Cover, T.M. Pombra, S. Dept. of Electr. Eng. & Stat., Stanford Univ., CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1989 On page(s): 37-43 Volume: 35, Issue: 1 ISSN: 0018-9448 References Cited: 12 CODEN: IETTAW INSPEC Accession Number: 3444292 Abstract: The capacity of time-varying additive Gaussian noise channels with feedback is characterized. Toward this end, an asymptotic equipartition theorem for nonstationary Gaussian processes is proved. Then, with the aid of certain matrix inequalities, it is proved that the feedback capacity CFB in bits per transmission and the nonfeedback capacity C satisfy C⩽CFB ⩽2C and C⩽CFB⩽ C+1/2 Index Terms: channel capacity feedback information theory asymptotic equipartition theorem feedback feedback capacity information theory nonfeedback capacity nonstationary Gaussian processes time-varying additive Gaussian noise channels ----- Statistical inference under multiterminal rate restrictions: a differential geometric approach Amari, S.-I. Han, T.S. Fac. of Eng., Tokyo Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1989 On page(s): 217-227 Volume: 35, Issue: 2 ISSN: 0018-9448 References Cited: 24 CODEN: IETTAW INSPEC Accession Number: 3465966 Abstract: A statistical inference problem for a two-terminal information source emitting mutually correlated signals X and Y is treated. Let sequences Xn and Yn of n independent observations be encoded independently of each other into message sets MX and MY at rates R1 and R 2 per letter, respectively. This compression causes a loss of the statistical information available for testing hypotheses concerning X and Y. The loss of statistical information is evaluated as a function of the amounts R1 and R 2 of the Shannon information. A complete solution is given in the case of asymptotically complete data compression, R1, R2?0 as n??. It is shown that the differential geometry of the manifold of all probability distributions plays a fundamental role in this type of multiterminal problem connecting Shannon information and statistical information. A brief introduction to the dually coupled e-affine and m-affine connections together with e -flatness and m-flatness is given Index Terms: data compression information theory probability statistical analysis Shannon information asymptotically complete data compression differential geometric approach e-affine e-flatness m-affine m-flatness multiterminal rate restrictions mutually correlated signals probability distributions statistical inference two-terminal information source ----- Multiterminal source encoding with one distortion criterion Berger, T. Yeung, R.W. Sch. of Electr. Eng., Cornell Univ., Ithaca, NY ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1989 On page(s): 228-236 Volume: 35, Issue: 2 ISSN: 0018-9448 References Cited: 10 CODEN: IETTAW INSPEC Accession Number: 3456433 Abstract: The authors unify earlier investigations concerning the encoding of two correlated sources {Xk}, {Yk } by means of separate encoders. Decoding is done by a single decoder which receives the outputs from both encoders. The reconstruction of {Xk} 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 {Yk}. The binary Hamming case is investigated explicitly Index Terms: encoding admissible rate region binary Hamming case correlated sources decoder distortion criterion encoders multiterminal source encoding ----- Multiterminal source encoding with encoder breakdown Berger, T. Yeung, R.W. Sch. of Electr. Eng., Cornell Univ., Ithaca, NY ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1989 On page(s): 237-244 Volume: 35, Issue: 2 ISSN: 0018-9448 References Cited: 10 CODEN: IETTAW INSPEC Accession Number: 3456434 Abstract: 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 Index Terms: encoding admissible rate region correlated sources decoder encoder breakdown multiterminal source encoding ----- Simple proof of the concavity of the entropy power with respect to added Gaussian noise Dembo, A. Inf. Systs. Lab., Stanford Univ., CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1989 On page(s): 887-888 Volume: 35, Issue: 4 ISSN: 0018-9448 References Cited: 7 CODEN: IETTAW INSPEC Accession Number: 3488937 Abstract: A very simple proof of M.H. Costa's result (see ibid., vol.IT-31, p.751-60, 1985) that the entropy power of Xt=X +N(O,tI) is concave in t, is derived as an immediate consequence of an inequality concerning Fisher information. This relationship between Fisher information and entropy is found to be useful for proving the central limit theorem. Thus, one who seeks new entropy inequalities should try first to find new equalities about Fisher information, or at least to exploit the existing ones in new ways Index Terms: entropy information theory Fisher information Gaussian noise central limit theorem concavity entropy power inequality ----- On Gaussian feedback capacity Dembo, A. Inf. Syst. Lab., Stanford Univ., CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1989 On page(s): 1072-1076 Volume: 35, Issue: 5 ISSN: 0018-9448 References Cited: 7 CODEN: IETTAW INSPEC Accession Number: 3561608 Abstract: M. Pinsker and P. Ebert (Bell Syst. Tech. J., p.1705-1712, Oct.1970) proved that in channels with additive Gaussian noise, feedback at most doubles the capacity. Recently, T. Cover and S. Pombra (ibid., vol.35, no.1, p.37-43, Jan.1989) proved that feedback at most adds half a bit per transmission. Following their approach, the author proves that in the limit as signal power approaches either zero (very low SNR) or infinity (very high SNR), feedback does not increase the finite block-length capacity (which for nonstationary Gaussian channels replaces the standard notion of capacity that may not exist). Tighter upper bounds on the capacity are obtained in the process. Specializing these results to stationary channels, the author recovers some of the bounds recently obtained by L.H. Ozarow (to appear in IEEE Trans. Inf. Theory) using a different bounding technique Index Terms: channel capacity feedback information theory additive Gaussian noise channel capacity feedback finite block-length capacity nonstationary Gaussian channels stationary channels upper bounds ----- Embedding nonnegative definite Toeplitz matrices in nonnegative definite circulant matrices, with application to covariance estimation Dembo, A. Mallows, C.L. Shepp, L.A. AT&T Bell Lab., Murray Hill, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1989 On page(s): 1206-1212 Volume: 35, Issue: 6 ISSN: 0018-9448 References Cited: 13 CODEN: IETTAW INSPEC Accession Number: 3606126 Abstract: The class of nonnegative definite Toeplitz matrices that can be embedded in nonnegative definite circulant matrices of a larger size is characterized. An equivalent characterization in terms of the spectrum of the underlying process is also presented, together with the corresponding extremal processes. It is shown that a given finite-duration sequence ? can be extended to be the covariance of a periodic stationary processes whenever the Toeplitz matrix R generated by this sequence is strictly positive definite. The sequence ?=1, cos ?, cos 2? with (?/?) irrational, which has a unique nonperiodic extension as a covariance sequence, demonstrates that the strictness is needed. A simple constructive proof supplies a bound on the abovementioned period in terms of the minimal eigenvalue of R. It also yields, under the same conditions, an extension of ? to covariances that eventually decay to zero. For the maximum-likelihood estimate of the covariance of a stationary Gaussian process, the extension length required for using the estimate-maximize iterative algorithm is determined Index Terms: iterative methods matrix algebra parameter estimation random processes covariance estimation estimate-maximize iterative algorithm extremal processes finite-duration sequence maximum-likelihood estimate minimal eigenvalue nonnegative definite Toeplitz matrices nonnegative definite circulant matrices periodic stationary processes random process stationary Gaussian process ----- Random coding for additive Gaussian channels with feedback Ozarow, L.H. AT&T Bell Lab., Murray Hill, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1990 On page(s): 17-22 Volume: 36, Issue: 1 ISSN: 0018-9448 References Cited: 6 CODEN: IETTAW INSPEC Accession Number: 3652932 Abstract: A random coding strategy for discrete-time additive Gaussian noise channels with feedback is analyzed. It has long been known that feedback may increase the capacity of such channels as long as the additive noise process is not white. Here, it is proved that a strictly positive gain is always achieved and that, as the signal power goes to zero, the ratio of feedback capacity to capacity without feedback may be strictly greater than one if the noise spectrum has a null. This is not the case when the noise spectrum is bounded away from zero. It is also demonstrated that random coding, where the codewords are chosen from an ensemble of stationary Gaussian sequences, does not achieve capacity Index Terms: channel capacity encoding feedback random noise additive Gaussian noise channels channel capacity discrete time channels feedback random coding strategy ----- Upper bounds on the capacity of Gaussian channels with feedback Ozarow, L.H. AT&T Bell Lab., Murray Hill, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1990 On page(s): 156-161 Volume: 36, Issue: 1 ISSN: 0018-9448 References Cited: 13 CODEN: IETTAW INSPEC Accession Number: 3652944 Abstract: The capacity of the discrete-time additive Gaussian channel without feedback is known. A class of upper bounds on the capacity with noiseless feedback that are quite good for some exemplary channels is obtained Index Terms: channel capacity feedback information theory channel capacity discrete-time additive Gaussian channel noiseless feedback upper bounds ----- Extremal properties of rate distortion functions Ahlswede, R. Fakultat fuer Math., Bielefeld Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1990 On page(s): 166-171 Volume: 36, Issue: 1 ISSN: 0018-9448 References Cited: 7 CODEN: IETTAW INSPEC Accession Number: 3652946 Abstract: An attempt is made to determine whether it is true that for a fixed distortion level ? the rate-distortion function R( P,?) has in the distribution P no local maxima with values different from the global maximum. It is shown that, in general, the answer is negative. However, the answer is positive for Hamming distortion measures. Moreover their R is Schur-concave Index Terms: information theory Hamming distortion measures Schur-concavity extremal properties information theory rate distortion functions ----- Quantization for decentralized hypothesis testing under communication constraints Longo, M. Lookabaugh, T.D. Gray, R.M. Dept. of Electron. Eng., Naples Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1990 On page(s): 241-255 Volume: 36, Issue: 2 ISSN: 0018-9448 References Cited: 30 CODEN: IETTAW INSPEC Accession Number: 3689374 Abstract: In a decentralized hypothesis testing network, several peripheral nodes observe an environment and communicate their observations to a central node for the final decision. The presence of capacity constraints introduces theoretical and practical problems. The following problem is addressed: given that the peripheral encoders that satisfy these constraints are scalar quantizers, how should they be designed in order that the central test to be performed on their output indices is most powerful? The scheme is called cooperative design-separate encoding since the quantizers process separate observations but have a common goal; they seek to maximize a system-wide performance measure. The Bhattacharyya distance of the joint index space as such a criterion is suggested, and a design algorithm to optimize arbitrarily many quantizers cyclically is proposed. A simplified version of the algorithm, namely an independent design-separate encoding scheme, where the correlation is either absent or neglected for the sake of simplicity, is outlined. Performances are compared through worked examples Index Terms: encoding information theory Bhattacharyya distance capacity constraints communication constraints cooperative design-separate encoding decentralized hypothesis testing independent design-separate encoding joint index space peripheral encoders peripheral nodes quantisation scalar quantizers system-wide performance measure ----- The wavelet transform, time-frequency localization and signal analysis Daubechies, I. Math. Dept., Michigan Univ., Ann Arbor, MI; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1990 On page(s): 961-1005 Volume: 36, Issue: 5 ISSN: 0018-9448 References Cited: 71 CODEN: IETTAW INSPEC Accession Number: 3758193 Abstract: Two different procedures for effecting a frequency analysis of a time-dependent signal locally in time are studied. The first procedure is the short-time or windowed Fourier transform; the second is the wavelet transform, in which high-frequency components are studied with sharper time resolution than low-frequency components. The similarities and the differences between these two methods are discussed. For both schemes a detailed study is made of the reconstruction method and its stability as a function of the chosen time-frequency density. Finally, the notion of time-frequency localization is made precise, within this framework, by two localization theorems Index Terms: Fourier transforms signal processing transforms frequency analysis reconstruction method short time Fourier transform signal analysis stability time-dependent signal time-frequency density time-frequency localization wavelet transform windowed Fourier transform ----- Worst-case interactive communication. I. Two messages are almost optimal Orlitsky, A. AT&T Bell Labs., Murray Hill, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1990 On page(s): 1111-1126 Volume: 36, Issue: 5 ISSN: 0018-9448 References Cited: 15 CODEN: IETTAW INSPEC Accession Number: 3758204 Abstract: The reduction in communication achievable by interaction is investigated. The model assumes two communicators: an informant having a random variable X, and a recipient having a possibly dependent random variable Y. Both communicators want the recipient to learn X with no probability of error, whereas the informant may or may not learn Y. To that end, they alternate in transmitting messages comprising finite sequences of bits. Messages are transmitted over an error-free channel and are determined by an agreed-upon, deterministic protocol for (X,Y) (i.e. a protocol for transmitting X to a person who knows Y). A two-message protocol is described, and its worst case performance is investigated Index Terms: information theory protocols deterministic protocol error-free channel interactive communication two-message protocol worst case performance ----- Robust data fusion for multisensor detection systems Geraniotis, E. Chau, Y.A. Dept. of Electr. Eng., Maryland Univ., College Park, MD; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1990 On page(s): 1265-1279 Volume: 36, Issue: 6 ISSN: 0018-9448 References Cited: 20 CODEN: IETTAW INSPEC Accession Number: 3825307 Abstract: Minimax robust data fusion schemes for multisensor detection systems with discrete-time observations characterized by statistical uncertainty are developed and analyzed. Block, sequential, and serial fusion rules are considered. The performance measures used, and made robust with respect to the uncertainties, include the error probabilities of the hypothesis testing problem in the block fusion case and the error probabilities and expected numbers of samples or sensors in the sequential and serial fusion cases. For different sensor observation statistics, the minimax robust fusion rules are derived for two asymptotic cases of interest: when the number of sensors is large and when the number of times the fusion center collects the local (sensor) decisions is large. Moreover, for the case of identical sensor observation statistics and a large number of sensors, it is shown that there is no loss in optimality, if local tests using likelihood ratios and equal thresholds are used in the sequential fusion rule. In all situations, the robust decision rules at the sensors and the fusion center are shown to make use of likelihood ratios and thresholds that depend on the least-favorable probability distributions of the uncertainty class describing the statistics of sensor observations Index Terms: error statistics minimax techniques signal detection block fusion discrete-time observations error probabilities least-favorable probability distributions likelihood ratios minimax schemes multisensor detection systems robust data fusion robust decision rules sequential fusion rule serial fusion rules thresholds uncertainty class ----- A binary analog to the entropy-power inequality Shamai, S. Wyner, A.D. AT&T Bell Lab., Murray Hill, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1990 On page(s): 1428-1430 Volume: 36, Issue: 6 ISSN: 0018-9448 References Cited: 7 CODEN: IETTAW INSPEC Accession Number: 3825318 Abstract: Let {Xn}, {Yn} be independent stationary binary random sequences with entropy H( X), H(Y), respectively. Let h(?)=-?log?-(1-?)log(1-?), 0⩽?⩽1/2, be the binary entropy function and let ?(X)=h-1 (H(X)), ?(Y)=h-1 (H(Y)). Let zn=Xn?Yn , where ? denotes modulo-2 addition. The following analog of the entropy-power inequality provides a lower bound on H(Z ), the entropy of {Zn}: ?(Z)⩾?(X)*?(Y), where ?(Z)=h-1 (H(Z)), and ?*?=?(1-?)+?(1-?). When {Y n} are independent identically distributed, this reduces to Mrs. Gerber's Lemma from A.D. Wyner and J. Ziv (1973) Index Terms: entropy information theory random processes binary analog entropy-power inequality independent stationary binary random sequences information theory modulo-2 addition ----- Any code of which we cannot think is good Coffey, J.T. Goodman, R.M. Dept. of Electr. Eng., California Inst. of Technol., Pasadena, CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1990 On page(s): 1453-1461 Volume: 36, Issue: 6 ISSN: 0018-9448 References Cited: 30 CODEN: IETTAW INSPEC Accession Number: 3825324 Abstract: A central paradox of coding theory concerns the existence and construction of the best codes. Virtually every linear code is good, in the sense that it meets the Gilbert-Varshamov bound on distance versus redundancy. Despite the sophisticated constructions for codes derived over the years, however, no one has succeeded in demonstrating a constructive procedure that yields such codes over arbitrary symbol fields. Using the theory of Kolmogorov complexity, it is shown that this statement holds true in a rigorous mathematical sense: any linear code that is truly random, in the sense that there is no concise way of specifying the code, is good. Furthermore, random selection of a code that does contain some constructive pattern results, with probability bounded away from zero, in a code that does not meet the Gilbert-Varshamov bound regardless of the block length of the code. In contrast to the situation for linear codes, it is shown that there are effectively random nonlinear codes which have no guarantee on distance. In addition, it is shown that the techniques of Kolmogorov complexity can be used to derive typical properties of classes of codes in a novel way Index Terms: encoding error correction codes Gilbert-Varshamov bound Kolmogorov complexity arbitrary symbol fields coding theory linear code random nonlinear codes ----- Timing estimation for a filtered Poisson process in Gaussian noise Hero, A.O., III Dept. of Electr. Eng. & Comput. Sci., Michigan Univ., Ann Arbor, MI; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1991 On page(s): 92-106 Volume: 37, Issue: 1 ISSN: 0018-9448 References Cited: 28 CODEN: IETTAW INSPEC Accession Number: 3857697 Abstract: The problem of estimation of time shift of an inhomogeneous casually filtered Poisson process in the presence of additive Gaussian noise is discussed. Approximate expressions for the likelihood function, the MAP estimator, and the MMSE estimator that becomes increasingly accurate as the per-unit-time density of superimposed filter responses becomes small are obtained. The optimal MAP estimator takes the form of a cascade of linear and memoryless nonlinear components. For smooth point process intensities, the performance of the MAP estimator is studied via local bias and local variance. A rate distortion type lower bound on the MSE of any estimator of time delay is then derived by identification of a communications channel that accounts for the mapping from time delay to observation process. Results of numerical studies of estimator performance are presented. Based on the examples considered it is concluded: (1) the small-error MSE of the nonlinear MAP estimator can be significantly better than the small-error MSE of the optimal linear estimator: (2) the rate distortion lower bound can be significantly tighter than the Poisson limited bounds determined in previous studies Index Terms: filtering and prediction theory information theory parameter estimation random noise signal processing MAP estimator MMSE estimator additive Gaussian noise communications channel filtered Poisson process inhomogeneous process likelihood function local bias local variance maximum a posteriori estimator rate distortion type lower bound time shift estimation ----- A calculus for network delay. I. Network elements in isolation Cruz, R.L. Dept. of Electr. & Comput. Eng., California Univ., San Diego, CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1991 On page(s): 114-131 Volume: 37, Issue: 1 ISSN: 0018-9448 References Cited: 25 CODEN: IETTAW INSPEC Accession Number: 3847586 Abstract: A calculus is developed for obtaining bounds on delay and buffering requirements in a communication network operating in a packet switched mode under a fixed routing strategy. The theory developed is different from traditional approaches to analyzing delay because the model used to describe the entry of data into the network is nonprobabilistic. It is supposed that the data stream entered into the network by any given user satisfies burstiness constraints. A data stream is said to satisfy a burstiness constraint if the quantity of data from the stream contained in any interval of time is less than a value that depends on the length of the interval. Several network elements are defined that can be used as building blocks to model a wide variety of communication networks. Each type of network element is analyzed by assuming that the traffic entering it satisfies bursting constraints. Under this assumption, bounds are obtained on delay and buffering requirements for the network element; burstiness constraints satisfied by the traffic that exits the element are derived Index Terms: packet switching queueing theory telecommunication networks buffering burstiness constraints calculus communication network data stream fixed routing strategy network delay packet switched mode queueing networks traffic ----- A calculus for network delay. II. Network analysis Cruz, R.L. Dept. of Electr. & Comput. Eng., California Univ., San Diego, CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1991 On page(s): 132-141 Volume: 37, Issue: 1 ISSN: 0018-9448 References Cited: 7 CODEN: IETTAW INSPEC Accession Number: 3847587 Abstract: For pt.I see ibid., vol.37, no.1, p.114-31 (1991). A method to analyze the flow of data in a network consisting of the interconnection of network elements is presented. Assuming the data that enters the network satisfies burstiness constraints, burstiness constraints are derived for traffic flowing between network elements. These derived constraints imply bounds on network delay and buffering requirements. By example, it is shown that the use of regulator elements within the network can reduce maximum network delay. It is also found that such a use of regulator elements can enlarge the throughput region where finite bounds for delay are found. Finally, it is shown how regulator elements connected in series can be used to enforce general burstiness constraints Index Terms: packet switching queueing theory telecommunication networks buffering burstiness constraints communication network fixed routing strategy interconnection of network elements network delay packet switched mode queueing networks regulator elements throughput region traffic ----- Divergence measures based on the Shannon entropy Lin, J. Dept. of Comput. Sci., Brandeis Univ., Waltham, MA ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1991 On page(s): 145-151 Volume: 37, Issue: 1 ISSN: 0018-9448 References Cited: 32 CODEN: IETTAW INSPEC Accession Number: 3857700 Abstract: A novel class of information-theoretic divergence measures based on the Shannon entropy is introduced. Unlike the well-known Kullback divergences, the new measures do not require the condition of absolute continuity to be satisfied by the probability distributions involved. More importantly, their close relationship with the variational distance and the probability of misclassification error are established in terms of bounds. These bounds are crucial in many applications of divergence measures. The measures are also well characterized by the properties of nonnegativity, finiteness, semiboundedness, and boundedness Index Terms: entropy information theory Shannon entropy boundedness divergence measures finiteness information theory nonnegativity probability of misclassification error semiboundedness variational distance ----- Successive refinement of information Equitz, W.H.R. Cover, T.M. IBM Almaden Res. Center, San Jose, CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1991 On page(s): 269-275 Volume: 37, Issue: 2 ISSN: 0018-9448 References Cited: 20 CODEN: IETTAW INSPEC Accession Number: 3911546 Abstract: The successive refinement of information consists of first approximating data using a few bits of information, then iteratively improving the approximation as more and more information is supplied. The goal is to achieve an optimal description at each stage. In general, an ongoing description which is rate-distortion optimal whenever it is interrupted is sought. It is shown that in order to achieve optimal successive refinement the necessary and sufficient conditions are that the solutions of the rate distortion problem can be written as a Markov chain. In particular, all finite alphabet signals with Hamming distortion satisfy these requirements. It is also shown that the same is true for Gaussian signals with squared error distortion and for Laplacian signals with absolute error distortion. A simple counterexample with absolute error distortion and a symmetric source distribution which shows that successive refinement is not always achievable is presented Index Terms: information theory Gaussian signals Hamming distortion Laplacian signals absolute error distortion finite alphabet signals information theory optimal description rate distortion problem squared error distortion successive refinement symmetric source distribution ----- A new outlook of Shannon's information measures Yeung, R.W. AT&T Bell Lab., Holmdel, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 1991 On page(s): 466-474 Volume: 37, Issue: 3 ISSN: 0018-9448 References Cited: 15 CODEN: IETTAW INSPEC Accession Number: 3960406 Abstract: The author presents a new approach to understanding the underlying mathematical structure of Shannon's information measures, which provides answers to the following two questions for any finite number of random variables. (1) For any information-theoretic identity, is there a corresponding set-theoretic identity via the formal substitution of symbols? (2) For any set-theoretic identity, is there a corresponding information-theoretic identity and, if so, in what sense? The author establishes the analogy between information theory and set theory. Therefore, each information-theoretic operation can formally be viewed as a set-theoretic operation and vice versa. This point of view, which the author believes is of fundamental importance has apparently been overlooked in the past by information theorists. As a consequence the I-diagram, which is a geometrical representation of the relationship among the information measures, is introduced. The I -diagram is analogous to the Venn diagram in set theory. The use of the I-diagram is discussed Index Terms: information theory set theory I-diagram Shannon's information measures finite number of random variables geometrical representation information theory information-theoretic identity mathematical structure set theory set-theoretic identity ----- Worst-case interactive communication. II. Two messages are not optimal Orlitsky, A. AT&T Bell Lab., Murray Hill, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1991 On page(s): 995-1005 Volume: 37, Issue: 4 ISSN: 0018-9448 References Cited: 5 CODEN: IETTAW INSPEC Accession Number: 3991274 Abstract: For pt.I see ibid., vol.36, no.5, p.1111-26, (1990). The author defines the chromatic-decomposition number of a hypergraph and shows that, under general conditions, it determines the two message complexity. This result is then used to provide that two messages are not optimal. Protocols, complexities, and the characteristic hypergraph of (X,Y) are defined. The playoffs problem is described. Although similar in appearance to the league problem given in an example, it is shown that its two-message complexity is about twice as high as its three-message complexity. The author proves a high lower bound on the chromatic-decomposition number of the playoffs problem's characteristic hypergraph showing that the problem has a high two-message complexity, and that allowing more than two messages may decrease the number of transmitted bits by a factor of two. A technique that improves the lower bound for the chromatic-decomposition number of the playoffs problem is described. However, this improved lower bound does not suffice to increase the provable gap between two and three message complexities Index Terms: information theory protocols chromatic-decomposition number hypergraph interactive communication lower bound playoffs problem protocols two message complexity worst case performance ----- On the Gaarder-Slepian “tracking system” conjecture [source coding] Gabor, G. Szekeres, G. Gyorfi, Z. Dept. of Math., Stat. & Comput. Sci., Dalhousie Univ., Halifax, NS; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1991 On page(s): 1165-1168 Volume: 37, Issue: 4 ISSN: 0018-9448 References Cited: 8 CODEN: IETTAW INSPEC Accession Number: 4004053 Abstract: The authors examine under what conditions, and with what notion of optimality, the coder of an optimal system can be operated with the information which is also accessible to the decoder. After a discussion of the difficulties involved, a theorem is proved for Markov sources which states that the extra memory of the coder can be substituted with independent randomization. The result is not tied to any specific notion of optimality. The main result is shown to hold for Markov sources of order k under weak assumptions on the structure and with respect to any per-letter fidelity criterion Index Terms: Markov processes encoding Gaarder-Slepian conjecture Markov sources coder optimal system optimality per-letter fidelity criterion source coding ----- Information theoretic inequalities Dembo, A. Cover, T.M. Thomas, J.A. Stanford Univ., CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1991 On page(s): 1501-1518 Volume: 37, Issue: 6 ISSN: 0018-9448 References Cited: 40 CODEN: IETTAW INSPEC Accession Number: 4083981 Abstract: The role of inequalities in information theory is reviewed, and the relationship of these inequalities to inequalities in other branches of mathematics is developed. The simple inequalities for differential entropy are applied to the standard multivariate normal to furnish new and simpler proofs of the major determinant inequalities in classical mathematics. The authors discuss differential entropy inequalities for random subsets of samples. These inequalities when specialized to multivariate normal variables provide the determinant inequalities that are presented. The authors focus on the entropy power inequality (including the related Brunn-Minkowski, Young's, and Fisher information inequalities) and address various uncertainty principles and their interrelations Index Terms: entropy information theory reviews determinant inequalities differential entropy entropy power inequality inequalities information theory multivariate normal variables review uncertainty principles ----- The entropy of a randomly stopped sequence Ekroot, L. Cover, T.M. Dept. of Electr. Eng., Stanford Univ., CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1991 On page(s): 1641-1644 Volume: 37, Issue: 6 ISSN: 0018-9448 References Cited: 8 CODEN: IETTAW INSPEC Accession Number: 4083993 Abstract: A Wald-like equation is proved for the entropy of a randomly stopped sequence of independent identically distributed discrete random variables X1, X2. . ., with a nonanticipating stopping time N. The authors first define a general stopping time and the associated stopped sequence, and then present the two main theorems for the entropy of a stopped sequence. The formal proofs of the lemmas necessary for the proof of the theorems are given. The randomness in the stopped sequence XN is the expected number of calls for X times the entropy per call plus the residual randomness in the stopping time conditioned on the unstopped sequence X? Index Terms: entropy information theory probability Wald-like equation entropy independent identically distributed discrete random variables information theory probability randomly stopped ----- On the rate distortion function of sources with incomplete statistics Vogel, P.H.A. Philips Kommunikations Ind. AG, Nuremberg; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1992 On page(s): 131-135 Volume: 38, Issue: 1 ISSN: 0018-9448 References Cited: 10 CODEN: IETTAW INSPEC Accession Number: 4123154 Abstract: Maximization of the rate distortion function (RDF) of a class of memoryless sources constrained by moments is transformed to a minimax problem. Kuhn-Tucker conditions for determining channel capacity and an RDF are solved simultaneously by a linear program. Special cases include the maximum entropy method, Gaussian densities, and spherical invariance Index Terms: channel capacity information theory minimax techniques Gaussian densities Kuhn-Tucker conditions channel capacity incomplete statistics information theory linear program maximum entropy method memoryless sources minimax problem rate distortion function spherical invariance ----- Simple bounds on the extreme eigenvalues of Toeplitz matrices Hertz, D. Rafael, Haifa; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1992 On page(s): 175-176 Volume: 38, Issue: 1 ISSN: 0018-9448 References Cited: 3 CODEN: IETTAW INSPEC Accession Number: 4123164 Abstract: Simple bounds are presented on the extreme eigenvalues of n ×n-dimensional Hermitian Toeplitz matrices. Such a matrix, say Tn, is determined by its first row. The proposed bounds have low complexity O(n); furthermore, examples are presented for which the proposed bounds are tighter than the Slepian-Landau bounds at their best, i.e. when the extreme eigenvalues of the submatrix obtained by deleting the first row and first column of Tn are known exactly. The bounds are first presented on the extreme eigenvalues of Hermitian Toeplitz matrices: the corresponding bounds for real symmetric Toeplitz matrices follow as a special case. Then, these bounds are extended to Hermitian Toeplitz interval matrices Index Terms: computational complexity eigenvalues and eigenfunctions matrix algebra Hermitian Toeplitz matrices bounds computational complexity extreme eigenvalues interval matrices real symmetric Toeplitz matrices ----- Necessary and sufficient condition for capacity of the discrete time Gaussian channel to be increased by feedback Yanagi, K. Dept. of Math., Yamaguchi Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1992 On page(s): 1788-1791 Volume: 38, Issue: 6 ISSN: 0018-9448 References Cited: 10 CODEN: IETTAW INSPEC Accession Number: 4320679 Abstract: The problem of whether the capacity of a discrete-time Gaussian channel is increased by feedback or not is considered. It is well known that the capacity of a white Gaussian channel under an average power constraint is not changed by feedback. The necessary condition under which the capacity of a nonwhite Gaussian channel with blockwise white noise is increased by feedback is given Index Terms: channel capacity discrete time systems feedback white noise blockwise white noise channel capacity discrete time Gaussian channel feedback necessary condition nonwhite Gaussian channel sufficient condition ----- Decentralized sequential detection with a fusion center performing the sequential test Veeravalli, V.V. Basar, T. Poor, H.V. Dept. of Electr. & Comput. Eng., Illinois Univ., Urbana, IL; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1993 On page(s): 433-442 Volume: 39, Issue: 2 ISSN: 0018-9448 References Cited: 13 CODEN: IETTAW INSPEC Accession Number: 4434431 Abstract: A decentralized sequential detection problem is considered in which each one of a set of sensors receives a sequence of observations about the hypothesis. Each sensor sends a sequence of summary messages to the fusion center where a sequential test is carried out to determine the true hypothesis. A Bayesian framework for this problem is introduced, and for the case when the information structure in the system is quasi-classical, it is shown that the problem is tractable. A detailed analysis of this case is presented, along with some numerical results Index Terms: Bayes methods dynamic programming sensor fusion signal detection Bayesian framework decentralized sequential detection dynamic programming fusion center hypothesis testing numerical results quasi-classical information structure sensor fusion sequential test summary messages tractable problem ----- On the reliability function of the ideal Poisson channel with noiseless feedback Lapidoth, A. Dept. of Electr. Eng., Technion-Israel Inst. of Technol., Haifa; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1993 On page(s): 491-503 Volume: 39, Issue: 2 ISSN: 0018-9448 References Cited: 32 CODEN: IETTAW INSPEC Accession Number: 4434436 Abstract: A coding scheme for the channel under peak power and average power constraints on the input is presented, and its asymptotic error exponent is shown to coincide, at all rates below capacity, with the sphere packing error exponent, which, for the case at hand, is known to be unachievable without feedback for rates below the critical rate. An upper bound on the error exponent achievable with feedback is also derived and shown, under a capacity reducing average power constraint, to coincide with the error exponent achieved by the proposed coding scheme; in such a case the coding scheme is asymptotically optimal. Thus, the ideal Poisson channel, limited by a capacity-reducing average power constraint, provides a nontrivial example of a channel for which the reliability function is known exactly both with and without feedback. It is shown that a slight modification of the coding scheme to one of random transmission time can achieve zero-error probability for any rate lower than the ordinary average-error channel capacity Index Terms: channel capacity encoding feedback optical communication reliability theory telecommunication channels asymptotic error exponent average power constraints channel capacity coding scheme direct detection optical channel ideal Poisson channel noiseless feedback peak power random transmission time reliability function sphere packing error exponent upper bound zero-error probability ----- Common randomness in information theory and cryptography. I. Secret sharing Ahlswede, R. Csiszar, I. Dept. of Math., Bielefeld Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 1993 On page(s): 1121-1132 Volume: 39, Issue: 4 ISSN: 0018-9448 References Cited: 12 CODEN: IETTAW INSPEC Accession Number: 4592665 Abstract: As the first part of a study of problems involving common randomness at distance locations, information-theoretic models of secret sharing (generating a common random key at two terminals, without letting an eavesdropper obtain information about this key) are considered. The concept of key-capacity is defined. Single-letter formulas of key-capacity are obtained for several models, and bounds to key-capacity are derived for other models Index Terms: cryptography information theory common random key common randomness cryptography eavesdropper information theory key-capacity secret sharing secure communication ----- A survey of the theory of source coding with a fidelity criterion Kieffer, J.C. Dept. of Electr. Eng., Minnesota Univ., Minneapolis, MN; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1993 On page(s): 1473-1490 Volume: 39, Issue: 5 ISSN: 0018-9448 References Cited: 137 CODEN: IETTAW INSPEC Accession Number: 4627384 Abstract: The purpose of this paper is threefold: 1) to acquaint the reader with the types of problems that have been considered in the area of source coding with a fidelity criterion; 2) to survey results that have been obtained on these problems; and 3) to outline future research trends in the area Index Terms: data compression encoding reviews abstract source model asymptotic source coding data compression distortion measure fidelity criterion multiparameter source models multiterminal source coding one-shot coding theory quantization problems rate distortion theory sequential source models universal source coding ----- Rate-distortion bound for a class of non-Gaussian sources with memory Ya-Qin Zhang Pickholtz, R.L. Loew, M.H. Dept. of Electr. Eng. & Comput. Sci., George Washington Univ., Washington, DC; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1993 On page(s): 1697-1701 Volume: 39, Issue: 5 ISSN: 0018-9448 References Cited: 10 CODEN: IETTAW INSPEC Accession Number: 4627408 Abstract: The rate-distortion performance of a class of non-Gaussian source with memory is studied. The source model is generated from a correlated Gaussian source through a memoryless transform, which actually constitutes a special class of the frequently-used Gibbs model in speech and image processing applications. Its entropy and a rate-distortion bound are evaluated to obtain further insights into this class of source models. Several examples are also given to illustrate the usefulness and tightness of the rate-distortion bound Index Terms: data compression entropy image processing information theory speech analysis and processing Gibbs model correlated Gaussian source entropy image processing memoryless transform non-Gaussian sources with memory rate-distortion bound source model ----- A generalization of the entropy power inequality with applications Zamir, R. Feder, M. Dept. of Electr. Eng., Tel Aviv Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1993 On page(s): 1723-1728 Volume: 39, Issue: 5 ISSN: 0018-9448 References Cited: 14 CODEN: IETTAW INSPEC Accession Number: 4627413 Abstract: The authors prove the following generalization of the entropy power inequality: h(ax_)⩾h(Ax_) where h(·) denotes (joint-) differential-entropy x_=x1...xn , is a random vector with independent components, x˜_=x˜...x˜n, is a Gaussian vector with independent components such that h(x¯i)=h(xi ), i=1...n, and A is any matrix. This generalization of the entropy-power inequality is applied to show that a non-Gaussian vector with independent components becomes “closer” to Gaussianity after a linear transformation, where the distance to Gaussianity is measured by the information divergence. Another application is a lower bound, greater than zero, for the mutual-information between nonoverlapping spectral components of a non-Gaussian white process. They also describe a dual generalization of the Fisher information inequality Index Terms: information theory matrix algebra spectral analysis Fisher information inequality Gaussian vector differential-entropy entropy power inequality independent components information divergence linear transformation lower bound matrix mutual information nonGaussian vector nonGaussian white process nonoverlapping spectral components random vector ----- Successive refinement of information: characterization of the achievable rates Rimoldi, B. Dept. of Electr. Eng., Missouri Univ., St. Louis, MO; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 1994 On page(s): 253-259 Volume: 40, Issue: 1 ISSN: 0018-9448 References Cited: 16 CODEN: IETTAW INSPEC Accession Number: 4666885 Abstract: Let R(·) be the rate-distortion function. Assume that we want to describe a source with distortion no larger than ?1 . From the rate-distortion theory we know that we need to do so at a rate R1 no smaller than R(?1) [bits/symbol]. If it turns out that a more accurate description at distortion ?2, ?20 and any ?>0, which induce the half-bit and factor-of-two bounds given by Cover and Pombra (1989) in the special case of ?=1 Index Terms: Gaussian channels channel capacity feedback discrete time Gaussian channel factor-of-two bound feedback finite blocklength capacity half-bit bound nonfeedback capacity upper bounds ----- High-resolution source coding for non-difference distortion measures: the rate-distortion function Linder, T. Zamir, R. Dept. of Math. & Stat., Queen's Univ., Kingston, Ont.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1999 On page(s): 533-547 Volume: 45, Issue: 2 ISSN: 0018-9448 References Cited: 30 CODEN: IETTAW INSPEC Accession Number: 6198531 Abstract: The problem of asymptotic (i,e., low-distortion) behavior of the rate-distortion function of a random vector is investigated for a class of non-difference distortion measures. The main result is an asymptotically tight expression which parallels the Shannon lower bound for difference distortion measures. For example, for an input-weighted squared error distortion measure d(x,y)=∥W(x)(y-x)∥2,y,x?Rn, the asymptotic expression for the rate-distortion function of X?Rn at distortion level D equals h(X)-2 /nlog(2?eD/n)+Elog|detW(X)| where h(X) is the differential entropy of X. Extensions to stationary sources and to high-resolution remote (“noisy”) source coding are also given Index Terms: entropy rate distortion theory source coding asymptotic behavior asymptotic expression asymptotically tight expression high-resolution remote source coding high-resolution source coding input-weighted squared error distortion measure nondifference distortion measures random vector rate-distortion function stationary sources ----- High-resolution source coding for non-difference distortion measures: multidimensional companding Linder, T. Zamir, R. Zeger, K. Dept. of Math. & Stat., Queen's Univ., Kingston, Ont.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1999 On page(s): 548-561 Volume: 45, Issue: 2 ISSN: 0018-9448 References Cited: 35 CODEN: IETTAW INSPEC Accession Number: 6198532 Abstract: Entropy-coded vector quantization is studied using high-resolution multidimensional companding over a class of nondifference distortion measures. For distortion measures which are “locally quadratic” a rigorous derivation of the asymptotic distortion and entropy-coded rate of multidimensional companders is given along with conditions for the optimal choice of the compressor function. This optimum compressor, when it exists, depends on the distortion measure but not on the source distribution. The rate-distortion performance of the companding scheme is studied using an asymptotic expression for the rate-distortion function which parallels the Shannon lower bound for difference distortion measures. It is proved that the high-resolution performance of the scheme is arbitrarily close to the rate-distortion limit for large quantizer dimensions if the compressor function and the lattice quantizer used in the companding scheme are optimal, extending an analogous statement for entropy-coded lattice quantization and MSE distortion. The companding approach is applied to obtain a high-resolution quantizing scheme for noisy sources Index Terms: compandors entropy codes lattice theory rate distortion theory source coding vector quantisation asymptotic distortion companding scheme compressor function entropy-coded rate entropy-coded vector quantization high-resolution performance high-resolution source coding lattice quantizer multidimensional companding noisy sources nondifference distortion measure rate-distortion limit ----- Linear multiuser receivers: effective interference, effective bandwidth and user capacity Tse, D.N.C. Hanly, S.V. Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 1999 On page(s): 641-657 Volume: 45, Issue: 2 ISSN: 0018-9448 References Cited: 29 CODEN: IETTAW INSPEC Accession Number: 6198538 Abstract: Multiuser receivers improve the performance of spread-spectrum and antenna-array systems by exploiting the structure of the multiaccess interference when demodulating the signal of a user. Much of the previous work on the performance analysis of multiuser receivers has focused on their ability to reject worst case interference. Their performance in a power-controlled network and the resulting user capacity are less well-understood. We show that in a large system with each user using random spreading sequences, the limiting interference effects under several linear multiuser receivers can be decoupled, such that each interferer can be ascribed a level of effective interference that it provides to the user to be demodulated. Applying these results to the uplink of a single power-controlled cell, we derive an effective bandwidth characterization of the user capacity: the signal-to-interference requirements of all the users can be met if and only if the sum of the effective bandwidths of the users is less than the total number of degrees of freedom in the system. The effective bandwidth of a user depends only on its own SIR requirement, and simple expressions are derived for three linear receivers: the conventional matched filter, the decorrelator, and the MMSE receiver. The effective bandwidths under the three receivers serve as a basis for performance comparison Index Terms: antenna arrays cellular radio channel capacity decorrelation demodulation diversity reception least mean squares methods matched filters multi-access systems multiuser channels power control radio links radio receivers radiofrequency interference random processes sequences spread spectrum communication telecommunication control MMSE receiver SIR requirement antenna diversity antenna-array systems decorrelator effective bandwidth effective interference limiting interference effects linear multiuser receivers matched filter multiaccess interference performance performance analysis power-controlled network random spreading sequences signal demodulation signal-to-interference single power-controlled cell spread-spectrum systems uplink user capacity ----- Improved decoding of Reed-Solomon and algebraic-geometry codes Guruswami, V. Sudan, M. Lab. for Comput. Sci., MIT, Cambridge, MA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1999 On page(s): 1757-1767 Volume: 45, Issue: 6 ISSN: 0018-9448 References Cited: 32 CODEN: IETTAW INSPEC Accession Number: 6341991 Abstract: Given an error-correcting code over strings of length n and an arbitrary input string also of length n, the list decoding problem is that of finding all codewords within a specified Hamming distance from the input string. We present an improved list decoding algorithm for decoding Reed-Solomon codes. The list decoding problem for Reed-Solomon codes reduces to the following “curve-fitting” problem over a field F: given n points ((xi·yi))i=1 n, xi, yi?F, and a degree parameter k and error parameter e, find all univariate polynomials p of degree at most k such that yi=p(xi) for all but at most e values of i?(1,...,n). We give an algorithm that solves this problem for e1/3, where the result yields the first asymptotic improvement in four decades. The algorithm generalizes to solve the list decoding problem for other algebraic codes, specifically alternant codes (a class of codes including BCH codes) and algebraic-geometry codes. In both cases, we obtain a list decoding algorithm that corrects up to n-?(n(n-d')) errors, where n is the block length and d' is the designed distance of the code. The improvement for the case of algebraic-geometry codes extends the methods of Shokrollahi and Wasserman (see in Proc. 29th Annu. ACM Symp. Theory of Computing, p.241-48, 1998) and improves upon their bound for every choice of n and d'. We also present some other consequences of our algorithm including a solution to a weighted curve-fitting problem, which may be of use in soft-decision decoding algorithms for Reed-Solomon codes Index Terms: BCH codes Reed-Solomon codes algebraic geometric codes coding errors curve fitting decoding BCH codes Hamming distance Reed-Solomon codes algebraic-geometry codes alternant codes asymptotic improvement block length bound code distance codewords curve-fitting problem degree parameter error parameter error-correcting code input string list decoding algorithm polynomial time algorithm soft-decision decoding algorithms string length univariate polynomials weighted curve-fitting problem ----- On the rate-distortion function of random vectors and stationary sources with mixed distributions Gyorgy, A. Linder, T. Zeger, K. Fac. of Electr. Eng. & Inf., Tech. Univ. Budapest; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1999 On page(s): 2110-2115 Volume: 45, Issue: 6 ISSN: 0018-9448 References Cited: 14 CODEN: IETTAW INSPEC Accession Number: 6342023 Abstract: The asymptotic (small distortion) behavior of the rate-distortion function of an n-dimensional source vector with mixed distribution is derived. The source distribution is a finite mixture of components such that under each component distribution a certain subset of the coordinates have a discrete distribution while the remaining coordinates have a joint density. The expected number of coordinates with a joint density is shown to equal the rate-distortion dimension of the source vector. Also, the exact small distortion asymptotic behavior of the rate-distortion function of a special but interesting class of stationary information sources is determined Index Terms: functional analysis random processes rate distortion theory statistical analysis vectors asymptotic behavior coordinates joint density mixed distributions random vectors rate-distortion function small distortion behavior source distribution source vector stationary information sources stationary sources ----- Information measures for discrete random fields Hajek, B. This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 1999 On page(s): 2210-2211 Volume: 45, Issue: 6 ISSN: 0018-9448 Abstract: Not Available Index Terms: Not Available ----- Gaussian codes and Shannon bounds for multiple descriptions Zamir, R. Dept. of Electr. Eng.-Syst., Tel Aviv Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 1999 On page(s): 2629-2636 Volume: 45, Issue: 7 ISSN: 0018-9448 References Cited: 17 CODEN: IETTAW INSPEC Accession Number: 6418599 Abstract: A pair of well-known inequalities, due to Shannon, upper/lower bound the rate-distortion function of a real source by the rate-distortion function of the Gaussian source with the same variance/entropy. We extend these bounds to multiple descriptions, a problem for which a general “single-letter” solution is not known. We show that the set DX(R1, R2) of achievable marginal (d1, d2) and central (d0) mean-squared errors in decoding X from two descriptions at rates R1 and R2 satisfies D*(?x2, R1, R2)?D X(R1, R2)?D*(Px, R1, R2) where ?x2 and Px are the variance and the entropy-power of X, respectively, and D*(?2, R1, R2) is the multiple description distortion region for a Gaussian source with variance ?2 found by Ozarow (1980). We further show that like in the single description case, a Gaussian random code achieves the outer bound in the limit as d1, d2?0, thus the outer bound is asymptotically tight at high resolution conditions Index Terms: Gaussian processes decoding random codes rate distortion theory source coding Gaussian codes Gaussian random code Gaussian source Shannon bounds achievable marginal asymptotically tight bound decoding entropy high resolution conditions mean-squared errors multiple description distortion region multiple descriptions outer bound rate-distortion function variance ----- The generalized distributive law Aji, S.M. McEliece, R.J. Dept. of Electr. Eng., California Inst. of Technol., Pasadena, CA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 2000 On page(s): 325-343 Volume: 46, Issue: 2 ISSN: 0018-9448 References Cited: 41 CODEN: IETTAW INSPEC Accession Number: 6548307 Abstract: We discuss a general message passing algorithm, which we call the generalized distributive law (GDL). The GDL is a synthesis of the work of many authors in information theory, digital communications, signal processing, statistics, and artificial intelligence. It includes as special cases the Baum-Welch algorithm, the fast Fourier transform (FFT) on any finite Abelian group, the Gallager-Tanner-Wiberg decoding algorithm, Viterbi's algorithm, the BCJR algorithm, Pearl's “belief propagation” algorithm, the Shafer-Shenoy probability propagation algorithm, and the turbo decoding algorithm. Although this algorithm is guaranteed to give exact answers only in certain cases (the “junction tree” condition), unfortunately not including the cases of GTW with cycles or turbo decoding, there is much experimental evidence, and a few theorems, suggesting that it often works approximately even when it is not supposed to Index Terms: decoding graph theory message passing turbo codes BCJR algorithm Baum-Welch algorithm FFT GDL Gallager-Tanner-Wiberg decoding algorithm Pearl belief propagation algorithm Shafer-Shenoy probability propagation algorithm Viterbi algorithm fast Fourier transform finite Abelian group general message passing algorithm generalized distributive law junction tree condition turbo decoding ----- The common randomness capacity of a network of discrete memoryless channels Venkatesan, S. Anantharam, V. Sch. of Electr. Eng., Cornell Univ., Ithaca, NY ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 2000 On page(s): 367-387 Volume: 46, Issue: 2 ISSN: 0018-9448 References Cited: 25 CODEN: IETTAW INSPEC Accession Number: 6548309 Abstract: We generalize our previous results on generating common randomness at two terminals to a situation where any finite number of agents, interconnected by an arbitrary network of independent, point-to-point, discrete memoryless channels, wish to generate common randomness by interactive communication over the network. Our main result is an exact characterization of the common randomness capacity of such a network, i.e., the maximum number of bits of randomness that all the agents can agree on per step of communication. As a by-product, we also obtain a purely combinatorial result, viz., a characterization of (the incidence vectors of) the spanning arborescences rooted at a specified vertex in a digraph, and having exactly one edge exiting the root, as precisely the extreme points of a certain unbounded convex polyhedron, described by a system of linear inequalities Index Terms: channel capacity graph theory interactive systems memoryless systems random processes telecommunication networks combinatorial result common randomness capacity communicating agents digraph vertex discrete memoryless channels incidence vectors independent memoryless channels interactive communication linear inequalities network topology point-to-point channels spanning arborescences terminals unbounded convex polyhedron ----- Tracing traitors Chor, B. Fiat, A. Naor, M. Pinkas, B. Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa; This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 2000 On page(s): 893-910 Volume: 46, Issue: 3 ISSN: 0018-9448 References Cited: 26 CODEN: IETTAW INSPEC Accession Number: 6593118 Abstract: We give cryptographic schemes that help trace the source of leaks when sensitive or proprietary data is made available to a large set of parties. A very relevant application is in the context of pay television, where only paying customers should be able to view certain programs. In this application, the programs are normally encrypted, and then the sensitive data is the decryption keys that are given to paying customers. If a pirate decoder is found, it is desirable to reveal the source of its decryption keys. We describe fully resilient schemes which can be used against any decoder which decrypts with nonnegligible probability. Since there is typically little demand for decoders which decrypt only a small fraction of the transmissions (even if it is nonnegligible), we further introduce threshold tracing schemes which can only be used against decoders which succeed in decryption with probability greater than some threshold. Threshold schemes are considerably more efficient than fully resilient schemes Index Terms: cryptography decoding telecommunication security television networks video signal processing cryptographic schemes decryption keys fully resilient schemes pay television paying customers pirate decoder sensitive data threshold tracing schemes ----- On the AEP of word-valued sources Nishiara, M. Morita, H. Graduate Sch. of Inf. Syst., Univ. of Electro-Commun., Tokyo; This paper appears in: Information Theory, IEEE Transactions on Publication Date: May 2000 On page(s): 1116-1120 Volume: 46, Issue: 3 ISSN: 0018-9448 References Cited: 8 CODEN: IETTAW INSPEC Accession Number: 6593142 Abstract: We consider a new class of information sources called word-valued sources in order to investigate coding algorithms based upon string parsing. A word-valued source is defined as a pair of an independent and identically distributed (i.i.d.) source with a countable alphabet and a function that maps each symbol into a finite sequence over a finite alphabet. A word-valued source is a nonstationary process and has countable states. If the function of a word-valued source is prefix-free, the entropy rate is characterized with a simple expression and the AEP (asymptotic equipartition property) holds Index Terms: entropy grammars probability sequences source coding AEP asymptotic equipartition property coding algorithms compressed sequence countable alphabet countable states entropy rate finite alphabet finite sequence i.i.d. source independent identically distributed source information sources nonstationary process probability distribution string parsing word-valued source word-valued sources ----- Network information flow Ahlswede, R. Ning Cai Li, S.-Y.R. Yeung, R.W. Fakultat fur Math., Bielefeld Univ.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 2000 On page(s): 1204-1216 Volume: 46, Issue: 4 ISSN: 0018-9448 References Cited: 14 CODEN: IETTAW INSPEC Accession Number: 6660200 Abstract: We introduce a new class of problems called network information flow which is inspired by computer network applications. Consider a point-to-point communication network on which a number of information sources are to be multicast to certain sets of destinations. We assume that the information sources are mutually independent. The problem is to characterize the admissible coding rate region. This model subsumes all previously studied models along the same line. We study the problem with one information source, and we have obtained a simple characterization of the admissible coding rate region. Our result can be regarded as the max-flow min-cut theorem for network information flow. Contrary to one's intuition, our work reveals that it is in general not optimal to regard the information to be multicast as a “fluid” which can simply be routed or replicated. Rather, by employing coding at the nodes, which we refer to as network coding, bandwidth can in general be saved. This finding may have significant impact on future design of switching systems Index Terms: computer networks directed graphs encoding minimax techniques multicast communication telecommunication network routing telecommunication switching admissible coding rate region bandwidth computer network applications directed graph information source information sources max-flow min-cut theorem multicasting networ routing network coding network information flow node coding point-to-point communication network switching systems design ----- Duality theorems for joint source-channel coding Mittal, U. Phamdo, N. Dept. of Electr. & Comput. Eng., State Univ. of New York, Stony Brook, NY; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 2000 On page(s): 1263-1275 Volume: 46, Issue: 4 ISSN: 0018-9448 References Cited: 19 CODEN: IETTAW INSPEC Accession Number: 6660204 Abstract: We consider joint source-channel coding for a memoryless Gaussian source and an additive white Gaussian noise (AWGN) channel. For a given code defined by an encoder-decoder pair (?, ?), its dual code is obtained by interchanging the encoder and decoder: (?, ?). It is shown that if a code (?, ?) is optimal at rate p channel uses per source sample and if it satisfies a certain uniform continuity condition, then its dual code (?, ?) is optimal for rate 1/? channel uses per source sample. Further, it is demonstrated that there is a code which is optimal but its dual code is not optimal. Finally, using random coding, we show that there is an optimal code which has an optimal dual. The duality concept is also presented for the cases of (i) binary memoryless equiprobable source and binary-symmetric channel (BSC), and (ii) colored Gaussian source and additive colored Gaussian noise (ACGN) channel Index Terms: AWGN channels combined source-channel coding decoding dual codes memoryless systems optimisation random codes AWGN channel additive colored Gaussian noise channel additive white Gaussian noise channel binary memoryless equiprobable source binary-symmetric channel code rate colored Gaussian source dual code duality theorems encoder-decoder pair joint source-channel coding memoryless Gaussian source optimal code optimal dual code random coding uniform continuity condition ----- A short proof of the “concavity of entropy power” Villani, C. DMA, Ecole Normale Superieure, Paris; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jul 2000 On page(s): 1695-1696 Volume: 46, Issue: 4 ISSN: 0018-9448 References Cited: 8 CODEN: IETTAW INSPEC Accession Number: 6660255 Abstract: After a brief statement of the“concavity of entropy power” theorem, a proof is given Index Terms: entropy concavity of entropy power proof ----- Signal design for bandwidth-efficient multiple-access communications based on eigenvalue optimization Guess, T. Varanasi, M.K. Dept. of Electr. Eng., Virginia Univ., Charlottesville, VA; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 2000 On page(s): 2045-2058 Volume: 46, Issue: 6 ISSN: 0018-9448 References Cited: 17 CODEN: IETTAW INSPEC Accession Number: 6724759 Abstract: Bandwidth-efficient multiple access (BEMA) is a strategy where transmitter pulses are continually designed at the base station and are dynamically allocated to the transmitters via a feedback channel. Such pulses (or “signature waveforms”) are designed to conserve bandwidth while simultaneously enabling the receiver at the base station to meet a quality-of-service (QoS) specification for each transmitter. The key technical problem in BEMA communication is therefore the design of the transmitter pulses for the base station receiver. In an earlier paper, we presented solutions to this problem that were shown to be superior (in terms of strict bandwidth) to common signaling schemes such as time-, frequency-, and code-division multiple access (TDMA, FDMA, and CDMA). This paper uses the framework developed earlier, but considers strictly time-limited transmitter pulses and the root-mean squared (RMS) bandwidth measure. As in the earlier paper, significant bandwidth savings over the traditional multiple-access strategies are obtained. However, in contrast to the rank-conserving approach, the bandwidth gains of this paper are realized by tailoring the signature waveform design to conserve RMS bandwidth via eigenvalue optimization problems Index Terms: eigenvalues and eigenfunctions multi-access systems multiuser channels optimisation quality of service radio receivers radio transmitters signal synthesis BEMA communication QoS specification RMS bandwidth measure bandwidth conservation bandwidth gains bandwidth-efficient multiple-access communications base station receiver correlated waveform multiple-access channel eigenvalue optimization feedback channel multiple-access strategies quality-of-service root-mean squared bandwidth measure signal design signature waveform design time-limited transmitter pulses transmitter pulses ----- A suboptimal quadratic change detection scheme Nikiforov, I.V. Univ. de Technol. de Troyes; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Sep 2000 On page(s): 2095-2107 Volume: 46, Issue: 6 ISSN: 0018-9448 References Cited: 21 CODEN: IETTAW INSPEC Accession Number: 6724762 Abstract: We address the problem of detecting changes in multivariate Gaussian random signals with an unknown mean after the change. The window-limited generalized-likelihood ratio (GLR) scheme is a well-known approach to solve this problem. However, this algorithm involves at least (log ?)/? likelihood-ratio computations at each stage, where ?(???) is the mean time before a false alarm and ? is the Kullback-Leibler information. We establish a new suboptimal recursive approach which is based on a collection of L parallel recursive ?2 tests instead of the window-limited GLR scheme. This new approach involves only a fixed number L of likelihood-ratio computations at each stage for any combinations of ? and ?. By choosing an acceptable value of nonoptimality, the designer can easily find a tradeoff between the complexity of the quadratic change detection algorithm and its efficiency Index Terms: Gaussian processes computational complexity optimisation random processes signal detection Kullback-Leibler information algorithm complexity algorithm efficiency false alarm likelihood-ratio computations mean time multivariate Gaussian random signals parallel recursive ? 2 tests suboptimal quadratic change detection suboptimal recursive approach window-limited generalized-likelihood ratio ----- Hypothesis testing with the general source Te Sun Han Graduate Sch. of Inf. Syst., Univ. of Electro-Commun., Tokyo; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 2000 On page(s): 2415-2427 Volume: 46, Issue: 7 ISSN: 0018-9448 References Cited: 20 CODEN: IETTAW INSPEC Accession Number: 6800191 Abstract: The asymptotically optimal hypothesis testing problem, with general sources as the null and alternative hypotheses, is studied under exponential-type error constraints on the first kind of error probability. Our fundamental philosophy is to convert all of the hypothesis testing problems to the pertinent computation problems in the large deviation-probability theory. This methodologically new approach enables us to establish compact general formulas of the optimal exponents of the second kind of error and correct testing probabilities for the general sources including all nonstationary and/or nonergodic sources with arbitrary abstract alphabet (countable or uncountable). These general formulas are presented from the information-spectrum point of view Index Terms: error statistics optimisation source coding achievable coding rates alternative hypothesis arbitrary abstract alphabet asymptotically optimal hypothesis testing compact general formulas computation problems countable alphabet error probability exponential-type error constraints fixed-length source coding general formulas general source information spectrum large deviation-probability theory nonstationary sources null hypothesis optimal exponents testing probabilities uncountable alphabet ----- On source coding with side-information-dependent distortion measures Linder, T. Zamir, R. Zeger, K. Dept. of Math. & Stat., Queen's Univ., Kingston, Ont.; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 2000 On page(s): 2697-2704 Volume: 46, Issue: 7 ISSN: 0018-9448 References Cited: 17 CODEN: IETTAW INSPEC Accession Number: 6800221 Abstract: High-resolution bounds in lossy coding of a real memoryless source are considered when side information is present. Let X be a “smooth” source and let Y be the side information. First we treat the case when both the encoder and the decoder have access to Y and we establish an asymptotically tight (high-resolution) formula for the conditional rate-distortion function RX|Y(D) for a class of locally quadratic distortion measures which may be functions of the side information. We then consider the case when only the decoder has access to the side information (i.e., the “Wyner-Ziv problem”). For side-information-dependent distortion measures, we give an explicit formula which tightly approximates the Wyner-Ziv rate-distortion function RWZ(D) for small D under some assumptions on the joint distribution of X and Y. These results demonstrate that for side-information-dependent distortion measures the rate loss RWZ(D)-RX|Y(D) can be bounded away from zero in the limit of small D. This contrasts the case of distortion measures which do not depend on the side information where the rate loss vanishes as D?0 Index Terms: rate distortion theory source coding Wyner-Ziv problem asymptotically tight formula conditional rate-distortion function high-resolution bounds high-resolution formula joint distribution locally quadratic distortion measures lossy coding rate loss real memoryless source side-information-dependent distortion measures smooth source source coding ----- Lower bounds of the minimal eigenvalue of a Hermitian positive-definite matrix Weiwei Sun Dept. of Math., Hong Kong Univ., Kowloon; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Nov 2000 On page(s): 2760-2762 Volume: 46, Issue: 7 ISSN: 0018-9448 References Cited: 4 CODEN: IETTAW INSPEC Accession Number: 6800231 Abstract: In this correspondence, we present several lower bounds of the minimal eigenvalue of a class of Hermitian positive-definite matrices, which improve the previous bounds given by Dembo (1988) and Ma and Zarowski (1995) Index Terms: Hermitian matrices eigenvalues and eigenfunctions information theory Hermitian positive-definite matrix lower bounds minimal eigenvalue ----- Asymptotically optimal water-filling in vector multiple-access channels Viswanath, P. Tse, D.N.C. Anantharam, V. Flarion Technol., Bedminster, NJ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Jan 2001 On page(s): 241-267 Volume: 47, Issue: 1 ISSN: 0018-9448 References Cited: 34 CODEN: IETTAW INSPEC Accession Number: 6862364 Abstract: Dynamic resource allocation is an important means to increase the sum capacity of fading multiple-access channels (MACs). In this paper, we consider vector multi-access channels (channels where each user has multiple degrees of freedom) and study the effect of power allocation as a function of the channel state on the sum capacity (or spectral efficiency) defined as the maximum sum of rates of users per unit degree of freedom at which the users can jointly transmit reliably, in an information-theoretic sense, assuming random directions of received signal. Direct-sequence code-division multiple-access (DS-CDMA) channels and MACs with multiple antennas at the receiver are two systems that fall under the model. Our main result is the identification of a simple dynamic power-allocation scheme that is optimal in a large system, i.e., with a large number of users and a correspondingly large number of degrees of freedom. A key feature of this policy is that, for any user, it depends on the instantaneous amplitude of channel state of that user alone and the structure of the policy is “water-filling.” In the contest of DS-CDMA and in the special case of no fading, the asymptotically optimal power policy of water-filling simplifies to constant power allocation over all realizations of signature sequences; this result verifies the conjecture made in Verdu and Shamai (1999). We study the behavior of the asymptotically optimal water-filling policy in various regimes of number of users per unit degree of freedom and signal-to-noise ratio (SNR). We also generalize this result to multiple classes, i.e., the situation when users in different classes have different average power constraints Index Terms: antenna arrays antenna theory channel capacity code division multiple access fading channels multiuser channels spread spectrum communication DS-CDMA channels asymptotically optimal water-filling channel state degree of freedom direct-sequence code-division multiple-access dynamic resource allocation fading multiple-access channels instantaneous amplitude multiple antennas power allocation power constraints power-allocation received signal signal-to-noise ratio signature sequences spectral efficiency sum capacity vector multiple-access channels ----- All sources are nearly successively refinable Lastras, L. Berger, T. Sch. of Electr. Eng., Cornell Univ., Ithaca, NY ; This paper appears in: Information Theory, IEEE Transactions on Publication Date: Mar 2001 On page(s): 918-926 Volume: 47, Issue: 3 ISSN: 0018-9448 References Cited: 20 CODEN: IETTAW INSPEC Accession Number: 6908004 Abstract: Given an achievable quadruple (R1, R2, D1, D2) for progressive transmission, the rate loss at step i is defined as Li=Ri-R(Di). Let D1 and D 2 be any two desired distortion levels (D2