Entropy and the law of small numbers

Two new information-theoretic methods are introduced for establishing Poisson approximation inequalities. First, using only elementary information-theoretic techniques it is shown that, when S/sub n/=/spl Sigma//sub i=1//sup n/X/sub i/ is the sum of the (possibly dependent) binary random variables X/sub 1/,X/sub 2/,...,X/sub n/, with E(X/sub i/)=p/sub i/ and E(S/sub n/)=/spl lambda/, then D(P(S/sub n/)/spl par/Po(/spl lambda/)) /spl les//spl Sigma//sub i=1//sup n/p/sub i//sup 2/+[/spl Sigma//sub i=1//sup n/H(X/sub i/)-H(X/sub 1/,X/sub 2/,...,X/sub n/)] where D(P(S/sub n/)/spl par/Po(/spl lambda/)) is the relative entropy between the distribution of S/sub n/ and the Poisson (/spl lambda/) distribution. The first term in this bound measures the individual smallness of the X/sub i/ and the second term measures their dependence. A general method is outlined for obtaining corresponding bounds when approximating the distribution of a sum of general discrete random variables by an infinitely divisible distribution. Second, in the particular case when the X/sub i/ are independent, the following sharper bound is established: D(P(S/sub n/)/spl par/Po(/spl lambda/))/spl les/1//spl lambda/ /spl Sigma//sub i=1//sup n/ ((p/sub i//sup 3/)/(1-p/sub i/)) and it is also generalized to the case when the X/sub i/ are general integer-valued random variables. Its proof is based on the derivation of a subadditivity property for a new discrete version of the Fisher information, and uses a recent logarithmic Sobolev inequality for the Poisson distribution.     

Lattices which are good for (almost) everything

We define an ensemble of lattices, and show that for asymptotically high dimension most of its members are simultaneously good as sphere packings, sphere coverings, additive white Gaussian noise (AWGN) channel codes and mean-squared error (MSE) quantization codes. These lattices are generated by applying Construction A to a random linear code over a prime field of growing size, i.e., by "lifting" the code to /spl Ropf//sup n/.     

Capacity and lattice strategies for canceling known interference

We consider the generalized dirty-paper channel Y=X+S+N,E{X/sup 2/}/spl les/P/sub X/, where N is not necessarily Gaussian, and the interference S is known causally or noncausally to the transmitter. We derive worst case capacity formulas and strategies for "strong" or arbitrarily varying interference. In the causal side information (SI) case, we develop a capacity formula based on minimum noise entropy strategies. We then show that strategies associated with entropy-constrained quantizers provide lower and upper bounds on the capacity. At high signal-to-noise ratio (SNR) conditions, i.e., if N is weak relative to the power constraint P/sub X/, these bounds coincide, the optimum strategies take the form of scalar lattice quantizers, and the capacity loss due to not having S at the receiver is shown to be exactly the "shaping gain" 1/2log(2/spl pi/e/12)/spl ap/ 0.254 bit. We extend the schemes to obtain achievable rates at any SNR and to noncausal SI, by incorporating minimum mean-squared error (MMSE) scaling, and by using k-dimensional lattices. For Gaussian N, the capacity loss of this scheme is upper-bounded by 1/2log2/spl pi/eG(/spl Lambda/), where G(/spl Lambda/) is the normalized second moment of the lattice. With a proper choice of lattice, the loss goes to zero as the dimension k goes to infinity, in agreement with the results of Costa. These results provide an information-theoretic framework for the study of common communication problems such as precoding for intersymbol interference (ISI) channels and broadcast channels.     

The inequalities of quantum information theory

Let /spl rho/ denote the density matrix of a quantum state having n parts 1, ..., n. For I/spl sube/N={1, ..., n}, let /spl rho//sub I/=Tr/sub N/spl bsol/I/(/spl rho/) denote the density matrix of the state comprising those parts i such that i/spl isin/I, and let S(/spl rho//sub I/) denote the von Neumann (1927) entropy of the state /spl rho//sub I/. The collection of /spl nu/=2/sup n/ numbers {S(/spl rho//sub I/)}/sub I/spl sube/N/ may be regarded as a point, called the allocation of entropy for /spl rho/, in the vector space R/sup /spl nu//. Let A/sub n/ denote the set of points in R/sup /spl nu// that are allocations of entropy for n-part quantum states. We show that A~/sub n/~ (the topological closure of A/sub n/) is a closed convex cone in R/sup /spl nu//. This implies that the approximate achievability of a point as an allocation of entropy is determined by the linear inequalities that it satisfies. Lieb and Ruskai (1973) have established a number of inequalities for multipartite quantum states (strong subadditivity and weak monotonicity). We give a finite set of instances of these inequalities that is complete (in the sense that any valid linear inequality for allocations of entropy can be deduced from them by taking positive linear combinations) and independent (in the sense that none of them can be deduced from the others by taking positive linear combinations). Let B/sub n/ denote the polyhedral cone in R/sup /spl nu// determined by these inequalities. We show that A~/sub n/~=B/sub n/ for n/spl les/3. The status of this equality is open for n/spl ges/4. We also consider a symmetric version of this situation, in which S(/spl rho//sub I/) depends on I only through the number i=/spl ne/I of indexes in I and can thus be denoted S(/spl rho//sub i/). In this case, we give for each n a finite complete and independent set of inequalities governing the symmetric allocations of entropy {S(/spl rho//sub i/)}/sub 0/spl les/i/spl les/n/ in R/sup n+1/.     

Decoding by linear programming

This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y? We prove that under suitable conditions on the coding matrix A, the input f is the unique solution to the /spl lscr//sub 1/-minimization problem (/spl par/x/spl par//sub /spl lscr/1/:=/spl Sigma//sub i/|x/sub i/|) min(g/spl isin/R/sup n/) /spl par/y - Ag/spl par//sub /spl lscr/1/ provided that the support of the vector of errors is not too large, /spl par/e/spl par//sub /spl lscr/0/:=|{i:e/sub i/ /spl ne/ 0}|/spl les//spl rho//spl middot/m for some /spl rho/>0. In short, f can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted. This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements. In fact, the results introduced in this paper improve on our earlier work. Finally, underlying the success of /spl lscr//sub 1/ is a crucial property we call the uniform uncertainty principle that we shall describe in detail.     

Lossless and near-lossless source coding for multiple access networks

A multiple access source code (MASC) is a source code designed for the following network configuration: a pair of correlated information sequences {X/sub i/}/sub i=1//sup /spl infin// and {Y/sub i/}/sub i=1//sup /spl infin// is drawn independent and identically distributed (i.i.d.) according to joint probability mass function (p.m.f.) p(x,y); the encoder for each source operates without knowledge of the other source; the decoder jointly decodes the encoded bit streams from both sources. The work of Slepian and Wolf describes all rates achievable by MASCs of infinite coding dimension (n/spl rarr//spl infin/) and asymptotically negligible error probabilities (P/sub e//sup (n)//spl rarr/0). In this paper, we consider the properties of optimal instantaneous MASCs with finite coding dimension (n相似文献   

Near-optimal depth-constrained codes

This note considers an n-letter alphabet in which the ith letter is accessed with probability p/sub i/. The problem is to design efficient algorithms for constructing near-optimal, depth-constrained Huffman and alphabetic codes. We recast the problem as one of determining a probability vector q/sup */=(q/sup *//sub 1/,...,q/sup *//sub n/) in an appropriate convex set, S, so as to minimize the relative entropy D(p/spl par/q) over all q/spl isin/S. Methods from convex optimization give an explicit solution for q/sup */ in terms of p. We show that the Huffman and alphabetic codes so constructed are within 1 and 2 bits of the corresponding optimal depth-constrained codes.     

Coded modulation in the block-fading channel: coding theorems and code construction

We consider coded modulation schemes for the block-fading channel. In the setting where a codeword spans a finite number N of fading degrees of freedom, we show that coded modulations of rate R bit per complex dimension, over a finite signal set /spl chi//spl sube//spl Copf/ of size 2/sup M/, achieve the optimal rate-diversity tradeoff given by the Singleton bound /spl delta/(N,M,R)=1+/spl lfloor/N(1-R/M)/spl rfloor/, for R/spl isin/(0,M/spl rfloor/. Furthermore, we show also that the popular bit-interleaved coded modulation achieves the same optimal rate-diversity tradeoff. We present a novel coded modulation construction based on blockwise concatenation that systematically yields Singleton-bound achieving turbo-like codes defined over an arbitrary signal set /spl chi//spl sub//spl Copf/. The proposed blockwise concatenation significantly outperforms conventional serial and parallel turbo codes in the block-fading channel. We analyze the ensemble average performance under maximum-likelihood (ML) decoding of the proposed codes by means of upper bounds and tight approximations. We show that, differently from the additive white Gaussian noise (AWGN) and fully interleaved fading cases, belief-propagation iterative decoding performs very close to ML on the block-fading channel for any signal-to-noise ratio (SNR) and even for relatively short block lengths. We also show that, at constant decoding complexity per information bit, the proposed codes perform close to the information outage probability for any block length, while standard block codes (e.g., obtained by trellis termination of convolutional codes) have a gap from outage that increases with the block length: this is a different and more subtle manifestation of the so-called "interleaving gain" of turbo codes.     

The convex-concave characteristics of Gaussian channel capacity functions

In this correspondence, we give several inherent properties of the capacity function of a Gaussian channel with and without feedback by using some operator inequalities and matrix analysis. We give a new proof method which is different from the method appearing in: K. Yanagi and H. W. Chen, "Operator inequality and its application to information theory," Taiwanese J. Math., vol. 4, no. 3, pp. 407-416, Sep. 2000. We obtain the following results: C/sub n,Z/(P) and C/sub n,FB,Z/(P) are both concave functions of P, C/sub n,Z/(P) is a convex function of the noise covariance matrix and C/sub n,FB,Z/(P) is a convex-like function of the noise covariance matrix. This new proof method is very elementary and the results shall help study the capacity of Gaussian channel. Finally, we state a conjecture concerning the convexity of C/sub n,FB,/spl middot//(P).     

On /spl Zopf//sub 4/-linear Preparata-like and Kerdock-like codes

We say that a binary code of length n is additive if it is isomorphic to a subgroup of /spl Zopf//sub 2//sup /spl alpha// /spl times/ /spl Zopf//sub 4//sup /spl beta//, where the quaternary coordinates are transformed to binary by means of the usual Gray map and hence /spl alpha/ + 2/spl beta/ = n. In this paper, we prove that any additive extended Preparata (1968) -like code always verifies /spl alpha/ = 0, i.e., it is always a /spl Zopf//sub 4/-linear code. Moreover, we compute the rank and the dimension of the kernel of such Preparata-like codes and also the rank and the kernel of the /spl Zopf//sub 4/-dual of these codes, i.e., the /spl Zopf//sub 4/-linear Kerdock-like codes.     

Asymptotic capacity of two-dimensional channels with checkerboard constraints

A checkerboard constraint is a bounded measurable set S/spl sub/R/sup 2/, containing the origin. A binary labeling of the Z/sup 2/ lattice satisfies the checkerboard constraint S if whenever t/spl isin/Z/sup 2/ is labeled 1, all of the other Z/sup 2/-lattice points in the translate t+S are labeled 0. Two-dimensional channels that only allow labelings of Z/sup 2/ satisfying checkerboard constraints are studied. Let A(S) be the area of S, and let A(S)/spl rarr//spl infin/ mean that S retains its shape but is inflated in size in the form /spl alpha/S, as /spl alpha//spl rarr//spl infin/. It is shown that for any open checkerboard constraint S, there exist positive reals K/sub 1/ and K/sub 2/ such that as A(S)/spl rarr//spl infin/, the channel capacity C/sub S/ decays to zero at least as fast as (K/sub 1/log/sub 2/A(S))/A(S) and at most as fast as (K/sub 2/log/sub 2/A(S))/A(S). It is also shown that if S is an open convex and symmetric checkerboard constraint, then as A(S)/spl rarr//spl infin/, the capacity decays exactly at the rate 4/spl delta/(S)(log/sub 2/A(S))/A(S), where /spl delta/(S) is the packing density of the set S. An implication is that the capacity of such checkerboard constrained channels is asymptotically determined only by the areas of the constraint and the smallest (possibly degenerate) hexagon that can be circumscribed about the constraint. In particular, this establishes that channels with square, diamond, or hexagonal checkerboard constraints all asymptotically have the same capacity, since /spl delta/(S)=1 for such constraints.     

On the filtering problem for stationary random /spl Zopf//sup 2/-fields

It is shown that whenever a stationary random field (Z/sub n,m/)/sub n,m/spl isin/z/ is given by a Borel function f:/spl Ropf//sup z/ /spl times/ /spl Ropf//sup z/ /spl rarr/ /spl Ropf/ of two stationary processes (X/sub n/)/sub n/spl isin/z/ and (Y/sub m/)/sub m/spl isin/z/ i.e., then (Z/sub n, m/) = (f((X/sub n+k/)/sub k/spl epsi/z/, (Y/sub m + /spl lscr// )/sub /spl lscr/ /spl epsi/z/)) under a mild first coordinate univalence assumption on f, the process (X/sub n/)/sub n/spl isin/z/ is measurable with respect to (Z/sub n,m/)/sub n,m/spl epsi/z/ whenever the process (Y/sub m/)/sub m/spl isin/z/ is ergodic. The notion of universal filtering property of an ergodic stationary process is introduced, and then using ergodic theory methods it is shown that an ergodic stationary process has this property if and only if the centralizer of the dynamical system canonically associated with the process does not contain a nontrivial compact subgroup.     

Asymptotic properties on codeword lengths of an optimal FV code for general sources

This correspondence is concerned with asymptotic properties on the codeword length of a fixed-to-variable length code (FV code) for a general source {X/sup n/}/sub n=1//sup /spl infin// with a finite or countably infinite alphabet. Suppose that for each n /spl ges/ 1 X/sup n/ is encoded to a binary codeword /spl phi//sub n/(X/sup n/) of length l(/spl phi//sub n/(X/sup n/)). Letting /spl epsiv//sub n/ denote the decoding error probability, we consider the following two criteria on FV codes: i) /spl epsiv//sub n/ = 0 for all n /spl ges/ 1 and ii) lim sup/sub n/spl rarr//spl infin///spl epsiv//sub n/ /spl les/ /spl epsiv/ for an arbitrarily given /spl epsiv/ /spl isin/ [0,1). Under criterion i), we show that, if X/sup n/ is encoded by an arbitrary prefix-free FV code asymptotically achieving the entropy, 1/nl(/spl phi//sub n/(X/sup n/)) - 1/nlog/sub 2/ 1/PX/sup n/(X/sup n/) /spl rarr/ 0 in probability as n /spl rarr/ /spl infin/ under a certain condition, where P/sub X//sup n/ denotes the probability distribution of X/sup n/. Under criterion ii), we first determine the minimum rate achieved by FV codes. Next, we show that 1/nl(/spl phi//sub n/(X/sup n/)) of an arbitrary FV code achieving the minimum rate in a certain sense has a property similar to the lossless case.     

Network information flow with correlated sources

Consider the following network communication setup, originating in a sensor networking application we refer to as the "sensor reachback" problem. We have a directed graph G=(V,E), where V={v/sub 0/v/sub 1/...v/sub n/} and E/spl sube/V/spl times/V. If (v/sub i/,v/sub j/)/spl isin/E, then node i can send messages to node j over a discrete memoryless channel (DMC) (X/sub ij/,p/sub ij/(y|x),Y/sub ij/), of capacity C/sub ij/. The channels are independent. Each node v/sub i/ gets to observe a source of information U/sub i/(i=0...M), with joint distribution p(U/sub 0/U/sub 1/...U/sub M/). Our goal is to solve an incast problem in G: nodes exchange messages with their neighbors, and after a finite number of communication rounds, one of the M+1 nodes (v/sub 0/ by convention) must have received enough information to reproduce the entire field of observations (U/sub 0/U/sub 1/...U/sub M/), with arbitrarily small probability of error. In this paper, we prove that such perfect reconstruction is possible if and only if H(U/sub s/ | U/sub S(c)/) < /spl Sigma//sub i/spl isin/S,j/spl isin/S(c)/ for all S/spl sube/{0...M},S/spl ne/O,0/spl isin/S(c). Our main finding is that in this setup, a general source/channel separation theorem holds, and that Shannon information behaves as a classical network flow, identical in nature to the flow of water in pipes. At first glance, it might seem surprising that separation holds in a fairly general network situation like the one we study. A closer look, however, reveals that the reason for this is that our model allows only for independent point-to-point channels between pairs of nodes, and not multiple-access and/or broadcast channels, for which separation is well known not to hold. This "information as flow" view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of implementing codes using a layered protocol stack.     

Five-contact silicon structure based integrated 3D Hall sensor

A new silicon integrated 3D Hall sensor for high-accuracy magnetic field measurements is suggested and tested. Its unique device design in having only five n/sup +/ contacts allows simultaneous and independent obtaining of the full information about the three components of the magnetic field vector. The device is manufactured through a simple planar process and requires the use of four masks. The lateral dimensions of the sensor are 270/spl times/270 /spl mu/m; the channel magnetosensitivities are S/sub x/=S/sub y/=85 V/AT and S/sub z/=29 V/AT; the nonlinearity and channel cross-sensitivities at B/spl les/1 reach no more than 0.6% and 3-4%, respectively; and the frequency response to AC magnetic field is greater than 30 kHz     

Curves on a sphere, shift-map dynamics, and error control for continuous alphabet sources

We consider two codes based on dynamical systems, for transmitting information from a continuous alphabet, discrete-time source over a Gaussian channel. The first code, a homogeneous spherical code, is generated by the linear dynamical system s/spl dot/=As, with A a square skew-symmetric matrix. The second code is generated by the shift map s/sub n/=b/sub n/s/sub n-1/(mod 1). The performance of each of these codes is determined by the geometry of its locus or signal set, specifically, its arc length and minimum distance, suitably defined. We show that the performance analyses for these systems are closely related, and derive exact expressions and bounds for relevant geometric parameters. We also observe that the lattice /spl Zopf//sup N/ underlies both modulation systems and we develop a fast decoding algorithm that relies on this observation. Analytic results show that for fixed bandwidth expansion, good scaling behavior of the mean squared error is obtained relative to the channel signal-to-noise ratio (SNR). Particularly interesting is the resulting observation that sampled, exponentially chirped modulation codes are good bandwidth expansion codes.     

A unified construction of space-time codes with optimal rate-diversity tradeoff

The problem of constructing space-time (ST) block codes over a fixed, desired signal constellation is considered. In this situation, there is a tradeoff between the transmission rate as measured in constellation symbols per channel use and the transmit diversity gain achieved by the code. The transmit diversity is a measure of the rate of polynomial decay of pairwise error probability of the code with increase in the signal-to-noise ratio (SNR). In the setting of a quasi-static channel model, let n/sub t/ denote the number of transmit antennas and T the block interval. For any n/sub t/ /spl les/ T, a unified construction of (n/sub t/ /spl times/ T) ST codes is provided here, for a class of signal constellations that includes the familiar pulse-amplitude (PAM), quadrature-amplitude (QAM), and 2/sup K/-ary phase-shift-keying (PSK) modulations as special cases. The construction is optimal as measured by the rate-diversity tradeoff and can achieve any given integer point on the rate-diversity tradeoff curve. An estimate of the coding gain realized is given. Other results presented here include i) an extension of the optimal unified construction to the multiple fading block case, ii) a version of the optimal unified construction in which the underlying binary block codes are replaced by trellis codes, iii) the providing of a linear dispersion form for the underlying binary block codes, iv) a Gray-mapped version of the unified construction, and v) a generalization of construction of the -ary case corresponding to constellations of size /sup K/. Items ii) and iii) are aimed at simplifying the decoding of this class of ST codes.     

Generalized smoothing splines and the optimal discretization of the Wiener filter

We introduce an extended class of cardinal L/sup */L-splines, where L is a pseudo-differential operator satisfying some admissibility conditions. We show that the L/sup */L-spline signal interpolation problem is well posed and that its solution is the unique minimizer of the spline energy functional /spl par/Ls/spl par//sub L2//sup 2/, subject to the interpolation constraint. Next, we consider the corresponding regularized least squares estimation problem, which is more appropriate for dealing with noisy data. The criterion to be minimized is the sum of a quadratic data term, which forces the solution to be close to the input samples, and a "smoothness" term that privileges solutions with small spline energies. Here, too, we find that the optimal solution, among all possible functions, is a cardinal L/sup */L-spline. We show that this smoothing spline estimator has a stable representation in a B-spline-like basis and that its coefficients can be computed by digital filtering of the input signal. We describe an efficient recursive filtering algorithm that is applicable whenever the transfer function of L is rational (which corresponds to the case of exponential splines). We justify these algorithms statistically by establishing an equivalence between L/sup */L smoothing splines and the minimum mean square error (MMSE) estimation of a stationary signal corrupted by white Gaussian noise. In this model-based formulation, the optimum operator L is the whitening filter of the process, and the regularization parameter is proportional to the noise variance. Thus, the proposed formalism yields the optimal discretization of the classical Wiener filter, together with a fast recursive algorithm. It extends the standard Wiener solution by providing the optimal interpolation space. We also present a Bayesian interpretation of the algorithm.     

The rank and kernel of extended 1-perfect /spl Zopf//sub 4/-linear and additive non-/spl Zopf//sub 4/-linear codes

A binary extended 1-perfect code of length n + 1 = 2/sup t/ is additive if it is a subgroup of /spl Zopf//sub 2//sup /spl alpha// /spl times/ /spl Zopf//sub 4//sup /spl beta//. The punctured code by deleting a /spl Zopf//sub 2/ coordinate (if there is one) gives a perfect additive code. 1-perfect additive codes were completely characterized and by using that characterization we compute the possible parameters /spl alpha/, /spl beta/, rank, and dimension of the kernel for extended 1-perfect additive codes. A very special case is that of extended 1-perfect /spl Zopf//sub 4/-linear codes.     

The empirical distribution of rate-constrained source codes

Let X = (X/sub 1/,...) be a stationary ergodic finite-alphabet source, X/sup n/ denote its first n symbols, and Y/sup n/ be the codeword assigned to X/sup n/ by a lossy source code. The empirical kth-order joint distribution Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rceil/(x/sup k/,y/sup k/) is defined as the frequency of appearances of pairs of k-strings (x/sup k/,y/sup k/) along the pair (X/sup n/,Y/sup n/). Our main interest is in the sample behavior of this (random) distribution. Letting I(Q/sup k/) denote the mutual information I(X/sup k/;Y/sup k/) when (X/sup k/,Y/sup k/)/spl sim/Q/sup k/ we show that for any (sequence of) lossy source code(s) of rate /spl les/R lim sup/sub n/spl rarr//spl infin//(1/k)I(Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rfloor/) /spl les/R+(1/k)H (X/sub 1//sup k/)-H~(X) a.s. where H~(X) denotes the entropy rate of X. This is shown to imply, for a large class of sources including all independent and identically distributed (i.i.d.). sources and all sources satisfying the Shannon lower bound with equality, that for any sequence of codes which is good in the sense of asymptotically attaining a point on the rate distortion curve Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rfloor//spl rArr//sup d/P(X/sup k/,Y~/sup k/) a.s. whenever P(/sub X//sup k//sub ,Y//sup k/) is the unique distribution attaining the minimum in the definition of the kth-order rate distortion function. Consequences of these results include a new proof of Kieffer's sample converse to lossy source coding, as well as performance bounds for compression-based denoisers.