Three dependent users are physically separated but communicate with each other via a satellite. Each user generates data which it stores locally. In addition, each user sends a message to the satellite. The satellite processes the messages received from the users and broadcasts one common message to all three users. Each user must be capable of reconstructing the data of the other two users based upon the broadcast message and its own stored data. Our problem is to determine the minimum amount of information which must be transmitted to and from the satellite. The solution to this problem is obtained for the case where subsequent data triples that are produced by the users are independent and identically distributed. The three symbols within each triple are assumed to be dependent. Crucial for the solution is an achievability proof that involves cascaded Slepian-Wolf (1973) source coding.

In this paper, the role of pattern matching in information theory is motivated and discussed. We describe the relationship between a pattern's recurrence time and its probability under the data-generating stochastic source. We show how this relationship has led to great advances in universal data compression. We then describe nonasymptotic uniform bounds on the performance of data-compression algorithms in cases where the size of the training data that is available to the encoder is not large enough so as to yield the asymptotic compression: the Shannon entropy. We then discuss applications of pattern matching and universal compression to universal prediction, classification, and entropy estimation.

A simple idealized linear (and planar) uplink cellular multiple-access communication model, where only adjacent cell interference is present and all signals may experience fading, is considered. Shannon theoretic arguments are invoked to gain insight into the implications on performance of the main system parameters and multiple-access techniques. We specialize to the linear model and address the case of practical importance where the cell-site receiver processes only the signals received at this cell site, and where the actively interfering users assigned to other cells (but not those within the cell) are interpreted as Gaussian noise (worst case assumption). We assume that the cell-site receiver is aware of the instantaneous signal-to-noise ratios for all users assigned to that cell while the users' transmitters do not have access to this side information. We first investigate several different scenarios and focus on the effect of fading and intercell interference and then provide a general formulation for an achievable rate region (inner-bound) of which all the different scenarios are special cases. The features of TDMA and wideband (WB) intracell multiple-access techniques are examined as well as the role of (optimized) fractional intercell time-sharing (ICTS) protocol. The cases of: no fading, fading where intercell interference is not dominant, and fading where intercell interference is present, are discussed.

For pt.I see ibid., vol.43, no.6, p.1877-94 (1997). A simple idealized linear (and planar) uplink, cellular, multiple-access communication model, where only adjacent cell interference is present and all signals may experience fading is considered. Shannon theoretic arguments are invoked to gain insight into the implications on performance of the main system parameters and multiple-access techniques. The model treated in Part I (Shamai, 1997) is extended here to account for cell-site receivers that may process also the received signal at an adjacent cell site, compromising thus between the advantage of incorporating additional information from other cell sites on one hand and the associated excess processing complexity on the other. Various settings which include fading, time-division multiple access (TDMA), wideband (WB), and (optimized) fractional inter-cell time sharing (ICTS) protocols are investigated and compared. In this case and for the WB approach and a large number of users per cell it is found, surprisingly, that fading may enhance performance in terms of Shannon theoretic achievable rates. The linear model is extended to account for general linear and planar configurations. The effect of a random number of users per cell is investigated and it is demonstrated that randomization is beneficial. Certain aspects of diversity as well as some features of TDMA and orthogonal code-division multiple access (CDMA) techniques in the presence of fading are studied in an isolated cell scenario.

Consider the following situation. A device called a classifier observes a probability law P on l-vectors from an alphabet of size A. Its task is to observe a second probability law Q and decide whether P/spl equiv/Q or P and Q are sufficiently different according to some appropriate criterion. If the classifier has available an unlimited memory (so that it can remember P(z) exactly for all z), this is a simple matter. In fact for most differentness criteria, a finite memory of 2/sup (log/ /sup A)l+o(l)/ bits will suffice (for large l), i.e., store a finite approximation of P(z) for all A/sup l/z's. In a sense made precise in this paper, it is shown that a memory of only about 2/sup Rl/ bits is required, where the quantity R

The Lempel-Ziv data compression algorithm has the property that for finite-memory sources the redundancy /spl rho//sub n/ (defined as the difference between the average code rate and the entropy when the memory size is n) is O (log log n/log n). We suggest a new version of the algorithm with redundancy /spl rho//sub n/=O (1/log n).>

The sliding-window version of the Lempel-Ziv data-compression algorithm (sometimes called LZ '77) has been thrust into prominence recently. A version of this algorithm is used in the highly successful "Stacker" program for personal computers. If is also incorporated into Microsoft's new MS-DOS-6. Although other versions of the Lempel-Ziv algorithm are known to he optimal in the sense that they compress a data source to its entropy, optimality in this sense has never been demonstrated for this version. In this self-contained paper, we will describe the algorithm, and show that as the "window size," a quantity which is related to the memory and complexity of the procedure, goes to infinity, the compression rate approaches the source entropy. The proof is surprisingly general, applying to all finite-alphabet stationary ergodic sources.>

We obtain Shannon-theoretic limits for a very simple cellular multiple-access system. In our model the received signal at a given cell site is the sum of the signals transmitted from within that cell plus a factor /spl alpha/ (0/spl les//spl alpha//spl les/1) times the sum of the signals transmitted from the adjacent cells plus ambient Gaussian noise. Although this simple model is scarcely realistic, it nevertheless has enough meat so that the results yield considerable insight into the workings of real systems. We consider both a one dimensional linear cellular array and the familiar two-dimensional hexagonal cellular pattern. The discrete-time channel is memoryless. We assume that N contiguous cells have active transmitters in the one-dimensional case, and that N/sup 2/ contiguous cells have active transmitters in the two-dimensional case. There are K transmitters per cell. Most of our results are obtained for the limiting case as N/spl rarr//spl infin/. The results include the following. (1) We define C/sub N/,C/spl circ//sub N/ as the largest achievable rate per transmitter in the usual Shannon-theoretic sense in the one- and two-dimensional cases, respectively (assuming that all signals are jointly decoded). We find expressions for limN/spl rarr//spl infin/C/sub N/ and limN/spl rarr//spl infin/C/spl circ//sub N/. (2) As the interference parameter /spl alpha/ increases from 0, C/sub N/ and C/spl circ//sub N/ increase or decrease according to whether the signal-to-noise ratio is less than or greater than unity. (3) Optimal performance is attainable using TDMA within the cell, but using TDMA for adjacent cells is distinctly suboptimal. (4) We suggest a scheme which does not require joint decoding of all the users, and is, in many cases, close to optimal.>

In an earlier work, Wyner and Ziv (see ibid., vol.35, no.6, p.1250-8, 1989) proved theorems on recurrence times for strings in a random sequence, and applied these theorems to data compression and the Lempel-Ziv algorithm. It is shown that one of these theorems holds under an essentially weaker hypothesis. The new proof is considerably simpler than the original.>

It is demonstrated that a variant of the algorithm, where the data base is held fixed and is reused to encode successive strings of incoming input symbols, is optimal provided that the source is stationary and satisfies certain conditions (e.g. a finite-order Markov source).>

Bounds are presented on I/sub i.i.d./-the achievable information rate for a discrete Gaussian Channel with intersymbol interference (ISI) present and i.i.d. channel input symbols governed by an arbitrary predetermined distribution p/sub x/(x). The lower and upper bounds on I/sub i.i.d./ and I are formulated. The bounds on I/sub i.i.d./ are calculated for independent equiprobably binary channel symbols and for causal channels with ISI memory of degree one and two. The bounds on I/sub i.i.d./ are compared to the approximated (by Monte Carlo methods) known value of I/sub i.i.d./ and their tightness is considered. An application of the new lower bound on I/sub i.i.d./ yields an improvement on previously reported lower bounds for the capacity of the continuous-time strictly bandlimited (or bandpass) Gaussian channel with either peak or simultaneously peak power and bandlimiting constraints imposed on the channel's input waveform.>

It is demonstrated that a variant of the Lempel-Ziv data compression algorithm where the database is held fixed and is reused to encode successive strings of incoming input symbols is optimal, provided that the source is stationary and satisfies certain conditions (e.g., a finite-order Markov source). A finite memory version of the Lempel-Ziv algorithm compresses (on the average) to about the entropy rate. The necessary memory size depends on the nature of the source.>

An analytic confirmation of an observation made by G. Ungerboeck (1965) that approximately optimal performance on a Gaussian channel with capacity C can be obtained with about 2/sup C+1/ levels is given. In particular, the results imply that by using about 2/sup C-1/ levels, a rate of nearly C-1 bit can be achieved, and that by using 2/sup C+1/ levels a rate of about C-0.4 bits can be achieved.>

Let (X/sub n/), (Y/sub n/) be independent stationary binary random sequences with entropy H(X), H(Y), respectively. Let h( zeta )=- zeta log zeta -(1- zeta )log(1- zeta ), 0or= sigma (X)* sigma (Y), where sigma (Z)=h/sup -1/ (H(Z)), and alpha * beta = alpha (1- beta )+ beta (1- alpha ). When (Y/sub n/) are independent identically distributed, this reduces to Mrs. Gerber's Lemma from A.D. Wyner and J. Ziv (1973).>

Theorems concerning the entropy of a stationary ergodic information source are derived and used to obtain insight into the workings of certain data-compression coding schemes, in particular the Lempel-Siv data compression algorithm.>

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.>

The contributions of S.O. Rice to Shannon's formulations in communication theory are discussed. In 'Communication in the presence of noise-Probability of error for two encoding schemes' (see Bell Syst. Tech. J., vol.29, p.60-93, Jan. 1950) Rice considered two explicit construction schemes for choosing the transmitted signals of duration T and exhibited an exact formula for the probability of error in the decoded messages. Rice evaluated these unwieldy expressions and presented tables and curves showing the trade-off between rate, delay, and error probability. He obtained asymptotic expressions for the error probability for large delay, and showed that with his scheme for choosing the signals, Shannon's results could be obtained. He recognized from his numerical calculations that the error probability seemed to approach zero much more rapidly than this and that, in his asymptotics, he had evidently made approximations that might one day be improved.>

The capacity and the lower bound on the error exponent of a direct detection optical channel are derived. The channel input in a T-second interval is a waveform satisfying certain peak and average power constraints for the optical signal. The channel output is a Poisson process with a given intensity parameter; the intensity parameter takes account of the dark-current signal component. An explicit construction for an exponentially optimum family of codes is also presented.>

For pt.I see ibid., vol.34, no.6, p.1449-61 (1980). The discussion of the capacity and error exponent of the direct detection optical channel is continued. The channel input in a T-second interval is a waveform satisfying certain peak and average power constraints for the optical signals. The channel output is a Poisson process with an intensity parameter that accounts for the dark-current component. An upper bound is obtained on the error exponent which coincides with the lower bound. Thus, this channel is one for which the error exponent can be known exactly.>

It is desirable to choose the waveforms making up a signaling alphabet so that they are maximally separated one from another. This problem is considered, in the space of square-integrable functions, for signals which have finite duration, and are constrained in the ranges of their values as well as in energy. Corresponding to each of the following cases, we establish sharp bounds for the minimum distance and for the average distance between elements of a fixed size signal set, and construct sets of signals that attain both bounds simultaneously. \begin{list} \item {\em Case A (Energy Constraint Only):} The average energy of the waveforms in the signal set is at most\sigma, where0 \leq \sigma < \infty. \item {\em Case B (Energy and Peak Amplitude Constraints):} The average energy of the waveforms in the signal set is\leq \sigma (0 \leq \sigma < 1), and the absolute value of each waveform is at most1. \item {\em Case C (Energy and Value Constraints):} The average energy of the waveforms in the signal set is at mostb^{2}\sigma + a^{2}(1 - \sigma), and each waveform takes values in the set[a, b], where0 \leq a < b < \infty, and0 \leq \sigma \leq 1. \end{list} Cases A and B are applicable to signal design for communication in channels with additive noise (say Gaussian), and Case C is applicable to signal design for optical channels, where the signal represents the intensity of a photon stream. The general character of the results is that the minimum distance behaves like\gamma \sigmain Cases A and B, and like\gamma \sigma (1 - \sigma)in Case C, with\gammaa suitable constant.

The problem of scrambling a discrete-time analog sequence for the purpose of privacy encoding is studied. A large family of linear orthogonal invertible scrambling transformations is described that result in a negligible expansion of bandwidth and can therefore serve as building blocks in a secure communication system.

The techniques developed in Part I[1] for discrete-time analog scrambling are applied to the problem of scrambling band-limited continuous-time signals or waveforms. The idea behind the waveform scrambler is to sample the waveform (which is assumed to be band-limited) at a rate exceeding the Nyquist rate. The resulting sequence of samples is band-limited in the sense of Part I. The discrete-time scrambler described in Part I is applied to this sequence to produce a nearly band-limited scrambled sequence. A scrambled waveform is formed by modulating the amplitudes of a chain of pulses. This scrambled waveform can be transmitted over a band-limited channel, and the original unscrambled waveform can be recovered at the receiver.

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 set\cal 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} \}, where\hat{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 (with\varepsilon > 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 set\cal 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 any\varepsilon >0, knowledge of the side information at the encoder does not allow a reduction of the transmission rate.

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(Y\mid W), the conditional entropy ofYgivenW, with respect to all discrete random variablesWsuch that a)H(X\mid 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.

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.

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].

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.

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.

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.

A known bound on the maximum size of a subset of the binary n-cube with distance k is applied to yield an asymptotically good bound on the length of a circuit or chain in the n-cube of spread k.

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 by\hat{m}an estimate ofmbased on observingy(t)from 0 to\tau, where\tauis a random variable determined by a certain stopping rule of the decoder depending on a realization ofy. Letd(m,\hat{m})be the distortion of\hat{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).

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), where\Deltais a measure of the memory of the source. A number of interesting applications of these bounds are given.

We consider binary communication over the additive white Gaussian noise channel with no bandwidth constraint on the channel input signals, assuming the availability of a noiseless delayless feedback link. Although the signals at timetcan depend on the noise at times\tau < tand are therefore random functions, we require that the signal energy never exceed a fixed level. We show that the optimal probability of error is attainable without the use of the feedback channel by using antipodal signals.

In a recent series of papers, [2]-[4] Schalkwijk and Kailath have proposed a block coding scheme for transmission over the additive white Gaussian noise channel with one-sided spectral densityN_{0}using a noiseless delayless feedback link. The signals have bandwidthW (W \leq \infty)and average power\bar{P}. They show how to communicate at ratesR < C = W \log (1 + \bar{P}/N_{0}W), the channel capacity, with error probabilityP_{e} = \exp \{-e^{2(C-R)T+o(T)}\}(whereTis the coding delay), a "double exponential" decay. In their scheme the signal energy (in aT-second transmission) is a random variable with only its expectation constrained to be\bar{P}T. In this paper we consider the effect of imposing a peak energy constraint on the transmitter such that whenever the Schalkwijk-Kailath scheme requires energy exceeding a\bar{P}T(wherea > 1is a fixed parameter) transmission stops and an error is declared. We show that the error probability is degraded to a "single exponential" formP_{e} = e^{-E(a)T+o(T)}and find the exponentE(a). In the caseW = \infty , E(a) = (a - 1)^{2}/4a C. For finiteW, E(a)is given by a more complicated expression.

Lower bounds on the error probability are obtained for communication with average powerPand no bandwidth constraint in the presence of white Gaussian noise with spectral densityN. For ratesRless than the channel capacityC = P/N, these bounds show that the error-exponent (reliability)E(R)satisfiesE(R) \leq \left{ ^{C/2 -R, \mbox{R \leq C/4,}}_{(\sqrt{C}-\sqrt{R})^{2}, \mbox{R \geq C/4}}.Since this exponent can be achieved with orthogonal signals, the reliability is now known exactly. For rates exceeding the capacity, it is shown that the error probability approaches unity as the delay approaches infinity. This is a "strong converse" for this channel.

A definition of a recurrent code is given in a framework which renders it amenable to mathematical analysis. Recurrent codes for both independent and burst errors are considered, and a necessary and sufficient condition for either type of error correction is established. For burst-error-correcting codes, the problem treated is (for a fixed burst length and redundancy) the minimization of the error-free distance ("guard space") required between bursts. A lower bound is obtained on the guard space, and in certain cases, codes which realize this bound are given. A general code which is close to the lower bound in many cases is also given. For independent errors, a code which will correct any error, provided that no consecutive "n" positions have more than "e" digits in error, is discussed. Fore = 1, a necessary and sufficient condition onnis derived; fore > 1, a lower bound onnis obtained, and for the case of redundancy1/2, an upper bound onnis also derived.