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.     

New class of nonlinear systematic error detecting codes

A code C detects error e with probability 1-Q(e),ifQ(e) is a fraction of codewords y such that y, y+e/spl isin/C. We present a class of optimal nonlinear q-ary systematic (n, q/sup k/)-codes (robust codes) minimizing over all (n, q/sup k/)-codes the maximum of Q(e) for nonzero e. We also show that any linear (n, q/sup k/)-code V with n /spl les/2k can be modified into a nonlinear (n, q/sup k/)-code C/sub v/ with simple encoding and decoding procedures, such that the set E={e|Q(e)=1} of undetected errors for C/sub v/ is a (k-r)-dimensional subspace of V (|E|=q/sup k-r/ instead of q/sup k/ for V). For the remaining q/sup n/-q/sup k-r/ nonzero errors, Q(e)/spl les/q/sup -r/for q/spl ges/3 and Q(e)/spl les/ 2/sup -r+1/ for q=2.     

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.     

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.     

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相似文献   

Improving the Gilbert-Varshamov bound for q-ary codes

Given positive integers q,n, and d, denote by A/sub q/(n,d) the maximum size of a q-ary code of length n and minimum distance d. The famous Gilbert-Varshamov bound asserts that A/sub q/(n,d+1)/spl ges/q/sup n//V/sub q/(n,d) where V/sub q/(n,d)=/spl Sigma//sub i=0//sup d/ (/sub i//sup n/)(q-1)/sup i/ is the volume of a q-ary sphere of radius d. Extending a recent work of Jiang and Vardy on binary codes, we show that for any positive constant /spl alpha/ less than (q-1)/q there is a positive constant c such that for d/spl les//spl alpha/n A/sub q/(n,d+1)/spl ges/cq/sup n//V/sub q/(n,d)n. This confirms a conjecture by Jiang and Vardy.     

On robust and dynamic identifying codes

A subset C of vertices in an undirected graph G=(V,E) is called a 1-identifying code if the sets I(v)={u/spl isin/C:d(u,v)/spl les/1}, v/spl isin/V, are nonempty and no two of them are the same set. It is natural to consider classes of codes that retain the identification property under various conditions, e.g., when the sets I(v) are possibly slightly corrupted. We consider two such classes of robust codes. We also consider dynamic identifying codes, i.e., walks in G whose vertices form an identifying code in G.     

Random properties of the highest level sequences of primitive sequences over Z(2/sup e/)

Using the estimates of the exponential sums over Galois rings, we discuss the random properties of the highest level sequences /spl alpha//sub e-1/ of primitive sequences generated by a primitive polynomial of degree n over Z(2/sup e/). First we obtain an estimate of 0, 1 distribution in one period of /spl alpha//sub e-1/. On the other hand, we give an estimate of the absolute value of the autocorrelation function |C/sub N/(h)| of /spl alpha//sub e-1/, which is less than 2/sup e-1/(2/sup e-1/-1)/spl radic/3(2/sup 2e/-1)2/sup n/2/+2/sup e-1/ for h/spl ne/0. Both results show that the larger n is, the more random /spl alpha//sub e-1/ will be.     

Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.     

Cyclic codes over GR(4/sup m/) which are also cyclic over /spl Zopf//sub 4/

Let GR(4/sup m/) be the Galois ring of characteristic 4 and cardinality 4/sup m/, and /spl alpha/_={/spl alpha//sub 0/,/spl alpha//sub 1/,...,/spl alpha//sub m-1/} be a basis of GR(4/sup m/) over /spl Zopf//sub 4/ when we regard GR(4/sup m/) as a free /spl Zopf//sub 4/-module of rank m. Define the map d/sub /spl alpha/_/ from GR(4/sup m/)[z]/(z/sup n/-1) into /spl Zopf//sub 4/[z]/(z/sup mn/-1) by d/spl alpha/_(a(z))=/spl Sigma//sub i=0//sup m-1//spl Sigma//sub j=0//sup n-1/a/sub ij/z/sup mj+i/ where a(z)=/spl Sigma//sub j=0//sup n-1/a/sub j/z/sup j/ and a/sub j/=/spl Sigma//sub i=0//sup m-1/a/sub ij//spl alpha//sub i/, a/sub ij//spl isin//spl Zopf//sub 4/. Then, for any linear code C of length n over GR(4/sup m/), its image d/sub /spl alpha/_/(C) is a /spl Zopf//sub 4/-linear code of length mn. In this article, for n and m being odd integers, it is determined all pairs (/spl alpha/_,C) such that d/sub /spl alpha/_/(C) is /spl Zopf//sub 4/-cyclic, where /spl alpha/_ is a basis of GR(4/sup m/) over /spl Zopf//sub 4/, and C is a cyclic code of length n over GR(4/sup m/).     

A new binary sequence family with low correlation and large size

For odd n=2l+1 and an integer /spl rho/ with 1/spl les//spl rho//spl les/l, a new family S/sub o/(/spl rho/) of binary sequences of period 2/sup n/-1 is constructed. For a given /spl rho/, S/sub o/(/spl rho/) has maximum correlation 1+2/sup n+2/spl rho/-1/2/, family size 2/sup n/spl rho//, and maximum linear span n(n+1)/2. Similarly, a new family of S/sub e/(/spl rho/) of binary sequences of period 2/sup n/-1 is also presented for even n=2l and an integer /spl rho/ with 1/spl les//spl rho/相似文献   

A note on density model size testing

Let (F/sub k/)/sub k/spl ges/1/ be a nested family of parametric classes of densities with finite Vapnik-Chervonenkis dimension. Let f be a probability density belonging to F/sub k//sup */, where k/sup */ is the unknown smallest integer such that f/spl isin/F/sub k/. Given a random sample X/sub 1/,...,X/sub n/ drawn from f, an integer k/sub 0//spl ges/1 and a real number /spl alpha//spl isin/(0,1), we introduce a new, simple, explicit /spl alpha/-level consistent testing procedure of the hypothesis {H/sub 0/:k/sup */=k/sub 0/} versus the alternative {H/sub 1/:k/sup *//spl ne/k/sub 0/}. Our method is inspired by the combinatorial tools developed in Devroye and Lugosi and it includes a wide range of density models, such as mixture models, neural networks, or exponential families.     

Identifying and locating-dominating codes: NP-completeness results for directed graphs

Let G=(V, A) be a directed, asymmetric graph and C a subset of vertices, and let B/sub r//sup -/(v) denote the set of all vertices x such that there exists a directed path from x to v with at most r arcs. If the sets B/sub r//sup -/(v) /spl cap/ C, v /spl isin/ V (respectively, v /spl isin/ V/spl bsol/C), are all nonempty and different, we call C an r-identifying code (respectively, an r-locating-dominating code) of G. In other words, if C is an r-identifying code, then one can uniquely identify a vertex v /spl isin/ V only by knowing which codewords belong to B/sub r//sup -/(v), and if C is r-locating-dominating, the same is true for the vertices v in V/spl bsol/C. We prove that, given a directed, asymmetric graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r/spl ges/1 and remains so even when restricted to strongly connected, directed, asymmetric, bipartite graphs or to directed, asymmetric, bipartite graphs without directed cycles.     

Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes

Given positive integers n and d, let A/sub 2/(n,d) denote the maximum size of a binary code of length n and minimum distance d. The well-known Gilbert-Varshamov bound asserts that A/sub 2/(n,d)/spl ges/2/sup n//V(n,d-l), where V(n,d) = /spl sigma//sub i=0//sup d/(/sub i//sup n/) is the volume of a Hamming sphere of radius d. We show that, in fact, there exists a positive constant c such that A/sub 2/(n, d)/spl ges/c2/sup n//V(n,d-1)log/sub 2/V(n, d-1) whenever d/n/spl les/0.499. The result follows by recasting the Gilbert-Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. Generalizations and extensions of this result are briefly discussed.     

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.     

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.     

Locally testable cyclic codes

Cyclic linear codes of block length n over a finite field F/sub q/ are linear subspaces of F/sub q//sup n/ that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in the family have constant rate and constant normalized distance (distance divided by block length). It is a long-standing open problem whether there exists a good family of cyclic linear codes. A code C is r-testable if there exists a randomized algorithm which, given a word x/spl isin//sub q//sup n/, adaptively selects r positions, checks the entries of x in the selected positions, and makes a decision (accept or reject x) based on the positions selected and the numbers found, such that 1) if x/spl isin/C then x is surely accepted; ii) if dist(x,C) /spl ges/ /spl epsi/n then x is probably rejected. ("dist" refers to Hamming distance.) A family of codes is locally testable if all members of the family are r-testable for some constant r. This concept arose from holographic proofs/PCP's. Recently it was asked whether there exist good, locally testable families of codes. In this paper the intersection of the two questions stated is addressed. Theorem. There are no good, locally testable families of cyclic codes over any (fixed) finite field. In fact the result is stronger in that it replaces condition ii) of local testability by the condition ii') if dist (x,C) /spl ges/ /spl epsi/n then x has a positive chance of being rejected. The proof involves methods from Galois theory, cyclotomy, and diophantine approximation.     

Quantum cyclic and constacyclic codes

Based on classical quaternary constacyclic linear codes, we construct a set of quantum codes with parameters [[(4/sup m/ -1)/3, (4/sup m/ -1)/3 -2(3l + b)m, 4l + b + 2]] where m/spl ges/4, 1/spl les/b/spl les/3, and 12l + 3b < 2 /spl times/ 4/sup /spl lfloor/(m+2)/3/spl rfloor//-1, which are better than the codes in Bierbrauer and Edel (2000).     

Near-ellipsoidal Voronoi coding

We consider a special case of Voronoi coding, where a lattice /spl Lambda/ in /spl Ropf//sup n/ is shaped (or truncated) using a lattice /spl Lambda/'={(m/sub 1/x/sub 1/,...,m/sub n/x/sub n/)|(x/sub 1/,...,x/sub n/)/spl isin//spl Lambda/} for a fixed m_=(m/sub 1/,...,m/sub n/)/spl isin/(/spl Nopf//spl bsol/{0,1})/sup n/. Using this technique, the shaping boundary is near-ellipsoidal. It is shown that the resulting codes can be indexed by standard Voronoi indexing algorithms plus a conditional modification step, as far as /spl Lambda/' is a sublattice of /spl Lambda/. We derive the underlying conditions on m_ and present generic near-ellipsoidal Voronoi indexing algorithms. Examples of constraints on m_ and conditional modification are provided for the lattices A/sub 2/, D/sub n/ (n/spl ges/2) and 2D/sub n//sup +/ (n even /spl ges/4).