The universality of grammar-based codes for sources with countably infinite alphabets

In this paper, we investigate the performance of grammar-based codes for sources with countably infinite alphabets. Let /spl Lambda/ denote an arbitrary class of stationary, ergodic sources with a countably infinite alphabet. It is shown that grammar-based codes can be modified so that they are universal with respect to any /spl Lambda/ if and only if there exists a universal code for /spl Lambda/. Moreover, upper bounds on the worst case redundancies of grammar-based codes among large sets of length-n individual sequences from a countably infinite alphabet are established. Depending upon the conditions satisfied by length-n individual sequences, these bounds range from O(loglogn/logn) to O(1/log/sup 1-/spl alpha//n) for some 0相似文献   

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.     

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.     

Markov types and minimax redundancy for Markov sources

Redundancy of universal codes for a class of sources determines by how much the actual code length exceeds the optimal code length. In the minimax scenario, one designs the best code for the worst source within the class. Such minimax redundancy comes in two flavors: average minimax or worst case minimax. We study the worst case minimax redundancy of universal block codes for Markovian sources of any order. We prove that the maximal minimax redundancy for Markov sources of order r is asymptotically equal to 1/2m/sup r/(m-1)log/sub 2/n+log/sub 2/A/sub m//sup r/-(lnlnm/sup 1/(m-1)/)/lnm+o(1), where n is the length of a source sequence, m is the size of the alphabet, and A/sub m//sup r/ is an explicit constant (e.g., we find that for a binary alphabet m=2 and Markov of order r=1 the constant A/sub 2//sup 1/=16/spl middot/G/spl ap/14.655449504 where G is the Catalan number). Unlike previous attempts, we view the redundancy problem as an asymptotic evaluation of certain sums over a set of matrices representing Markov types. The enumeration of Markov types is accomplished by reducing it to counting Eulerian paths in a multigraph. In particular, we propose exact and asymptotic formulas for the number of strings of a given Markov type. All of these findings are obtained by analytic and combinatorial tools of analysis of algorithms.     

Compression mappings on primitive sequences over Z/(p/sup e/)

Let Z/(p/sup e/) be the integer residue ring with odd prime p/spl ges/5 and integer e/spl ges/2. For a sequence a_ over Z/(p/sup e/), there is a unique p-adic expansion a_=a_/sub 0/+a_/spl middot/p+...+a_/sub e-1//spl middot/p/sup e-1/, where each a_/sub i/ is a sequence over {0,1,...,p-1}, and can be regarded as a sequence over the finite field GF(p) naturally. Let f(x) be a primitive polynomial over Z/(p/sup e/), and G'(f(x),p/sup e/) the set of all primitive sequences generated by f(x) over Z/(p/sup e/). Set /spl phi//sub e-1/ (x/sub 0/,...,x/sub e-1/) = x/sub e-1//sup k/ + /spl eta//sub e-2,1/(x/sub 0/, x/sub 1/,...,x/sub e-2/) /spl psi//sub e-1/(x/sub 0/,...,x/sub e-1/) = x/sub e-1//sup k/ + /spl eta//sub e-2,2/(x/sub 0/,x/sub 1/,...,x/sub e-2/) where /spl eta//sub e-2,1/ and /spl eta//sub e-2,2/ are arbitrary functions of e-1 variables over GF(p) and 2/spl les/k/spl les/p-1. Then the compression mapping /spl phi//sub e-1/:{G'(f(x),p/sup e/) /spl rarr/ GF(p)/sup /spl infin// a_ /spl rarr/ /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) is injective, that is, a_ = b_ if and only if /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) = /spl phi//sub e-1/(b_/sub 0/,...,b_/sub e-1/) for a_,b_ /spl isin/ G'(f(x),p/sup e/). Furthermore, if f(x) is a strongly primitive polynomial over Z/(p/sup e/), then /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) = /spl psi//sub e-1/(b_/sub 0/,...,b_/sub e-1/) if and only if a_ = b_ and /spl phi//sub e-1/(x/sub 0/,...,x/sub e-1/) = /spl psi//sub e-1/(x/sub 0/,...,x/sub e-1/) for a_,b_ /spl isin/ G'(f(x),p/sup e/).     

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.     

Order statistics from a logistic distribution and applications to survival and reliability analysis

Joint moments involving arbitrary powers of order statistics are the main concern. Consider order statistics u/sub 1/ /spl les/ u/sub 2/ /spl les/ /spl middot//spl middot//spl middot/ /spl les/ u/sub k/ coming from a simple random sample of size n from a real continuous population where u/sub 1/ = x/sub r(1):n/ is order-statistic #r/sub 1/, u/sub 2/ = x/sub r(1)+r(2):n/ is order statistic #(r/sub 1/ + r/sub 2/), et al., and u/sub k/ = x/sub r(1)+/spl middot//spl middot//spl middot/+r(k):n/ is order statistic #(r/sub 1/ +/spl middot//spl middot//spl middot/+ r/sub k/). Product moments are examined of the type E[u/sub 1//sup /spl alpha/(1)/ /spl middot/ u/sub 2//sup /spl alpha/(2)//sub /spl middot/ /spl middot//spl middot//spl middot//spl middot//u/sub k//sup /spl alpha/(k)/] where /spl alpha//sub 1/, ..., /spl alpha//sub k/ are arbitrary quantities that might be complex numbers, and E[/spl middot/] denotes the s-expected value. Some explicit evaluations are considered for a logistic population. Detailed evaluations of all integer moments of u/sub 1/ and recurrence relations, recurring only on the order of the moments, are given. Connections to survival functions in survival analysis, hazard functions in reliability situations, real type-1, type-2 /spl beta/ and Dirichlet distributions are also examined. Arbitrary product moments for the survival functions are evaluated. Very general results are obtained which can be used in many problems in various areas.     

Reduced-state representations for trellis codes using constellation symmetry

This paper presents a symmetry-based technique for trellis-code state-diagram reduction that has more general applicability than the quasi-regularity technique of Rouanne et al. and Zehavi et al. for trellis codes using standard constellations and labelings. For a 2/sup /spl nu/x/-state trellis code, the new technique reduces the 2/sup 2/spl nu/x/ state diagram to 2/sup /spl nu/x+/spl nu/q/-state diagram where 0/spl les//spl nu//sub q//spl les//spl nu//sub x/. The particular value of /spl nu//sub q/ depends on the constellation labeling and the convolutional encoder. For standard rate-k/(k+1) set-partitioned trellis codes, /spl nu//sub q/=0, and the overall number of states is the same with the new technique as with quasi-regularity. For codes that are not quasi-regular (and thus not amenable to the quasi-regularity technique), the new technique often provides some improvement (when /spl nu//sub q/相似文献   

Grammar-based codes: a new class of universal lossless source codes

We investigate a type of lossless source code called a grammar-based code, which, in response to any input data string x over a fixed finite alphabet, selects a context-free grammar G_x representing x in the sense that x is the unique string belonging to the language generated by G_x. Lossless compression of x takes place indirectly via compression of the production rules of the grammar G_x. It is shown that, subject to some mild restrictions, a grammar-based code is a universal code with respect to the family of finite-state information sources over the finite alphabet. Redundancy bounds for grammar-based codes are established. Reduction rules for designing grammar-based codes are presented     

Grammar-based lossless universal refinement source coding

A sequence y=(y/sub 1/,...,y/sub n/) is said to be a coarsening of a given finite-alphabet source sequence x=(x/sub 1/,...,x/sub n/) if, for some function /spl phi/, y/sub i/=/spl phi/(x/sub i/) (i=1,...,n). In lossless refinement source coding, it is assumed that the decoder already possesses a coarsening y of a given source sequence x. It is the job of the lossless refinement source encoder to furnish the decoder with a binary codeword B(x|y) which the decoder can employ in combination with y to obtain x. We present a natural grammar-based approach for finding the binary codeword B(x|y) in two steps. In the first step of the grammar-based approach, the encoder furnishes the decoder with O(/spl radic/nlog/sub 2/n) code bits at the beginning of B(x|y) which tell the decoder how to build a context-free grammar G/sub y/ which represents y. The encoder possesses a context-free grammar G/sub x/ which represents x; in the second step of the grammar-based approach, the encoder furnishes the decoder with code bits in the rest of B(x|y) which tell the decoder how to build G/sub x/ from G/sub y/. We prove that our grammar-based lossless refinement source coding scheme is universal in the sense that its maximal redundancy per sample is O(1/log/sub 2/n) for n source samples, with respect to any finite-state lossless refinement source coding scheme. As a by-product, we provide a useful notion of the conditional entropy H(G/sub x/|G/sub y/) of the grammar G/sub x/ given the grammar G/sub y/, which is approximately equal to the length of the codeword B(x|y).     

Prime-length real-valued polynomial residue division algorithms

One class of efficient algorithms for computing a discrete Fourier transform (DFT) is based on a recursive polynomial factorization of the polynomial 1-z/sup -N/. The Bruun algorithm is a typical example of such algorithms. Previously, the Bruun algorithm, which is applicable only when system lengths are powers of two in its original form, is generalized and modified to be applicable to the case when the length is other than a power of two. This generalized algorithm consists of transforms T/sub d,f/ with prime d and real f in the range 0/spl les/f<0.5. T/sub d,0/ computes residues X(z)mod(1-z/sup -2/) and X(z)mod(1-2 cos(/spl pi/k/d)z/sup -1/+z/sup -2/), k=1, 2, ..., d-1, and T/sub d,f/ (f /spl ne/0) computes residues X(z)mod(1-2cos(2/spl pi/(f+k)/d)z/sup -1/+z/sup -2/), k=0, 1, ..., d-1 for a given real signal X(z) of length 2d. The purpose of this paper is to find efficient algorithms for T/sub d,f/. First, polynomial factorization algorithms are derived for T/sub d,0/ and T/sub d,1/4/. When f is neither 0 nor 1/4, it is not feasible to derive a polynomial factorization algorithm. Two different implementations of T/sub d,f/ for such f are derived. One implementation realizes T/sub d,f/ via a d-point DFT, for which a variety of fast algorithms exist. The other implementation realizes T/sub d,f/ via T/sub d, 1/4/, for which the polynomial factorization algorithm exists. Comparisons show that for d/spl ges/5, these implementations achieve better performance than computing each output of T/sub d,f/ separately.     

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.     

Generalization of the /spl Sigma//sub 0/-rank criteria for space-time codes

Recently, Liu et al., developed the /spl Sigma//sub 0/-rank criteria for space-time codes. It provides a sufficient condition on codeword and generator matrices defined over finite rings /spl Zopf//sub 2k/(j) to ensure full spatial diversity with 2/sup 2k/-QAM modulation. Here, we generalize the /spl Sigma//sub 0/-rank criteria and derive a sufficient condition on the generator matrices defined over finite rings /spl Zopf//sub 2l/(j) to ensure full spatial diversity with 2/sup 2k/-QAM modulation for any positive integer l/spl les/k. We also show that generator matrices defined over GF(2) satisfying the BPSK stacking construction constraint of Mammons and El Gamal achieve full spatial diversity when used with 2/sup 2k/-QAM modulation.     

List decoding of q-ary Reed-Muller codes

The q-ary Reed-Muller (RM) codes RM/sub q/(u,m) of length n=q/sup m/ are a generalization of Reed-Solomon (RS) codes, which use polynomials in m variables to encode messages through functional encoding. Using an idea of reducing the multivariate case to the univariate case, randomized list-decoding algorithms for RM codes were given in and . The algorithm in Sudan et al. (1999) is an improvement of the algorithm in , it is applicable to codes RM/sub q/(u,m) with u相似文献   

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.     

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

More results on the weight enumerator of product codes

We consider the product code C/sub p/ of q-ary linear codes with minimum distances d/sub c/ and d/sub r/. The words in C/sub p/ of weight less than d/sub r/d/sub c/+max(d/sub r//spl lceil/(d/sub c//g)/spl rceil/,d/sub c//spl lceil/(d/sub r//q)/spl rceil/) are characterized, and their number is expressed in the number of low-weight words of the constituent codes. For binary product codes, we give an upper bound on the number of words in C/sub p/ of weightless than min(d/sub r/(d/sub c/+/spl lceil/(d/sub c//2)/spl rceil/+1)), d/sub c/(d/sub r/+/spl lceil/(d/sub r//2)/spl rceil/+1) that is met with equality if C/sub c/ and C/sub r/ are (extended) perfect codes.     

Generalized multiplication-free arithmetic codes

Arithmetic coding is a highly efficient lossless source coding technique. Multiplication-free arithmetic coding algorithms provide an excellent tradeoff between operation complexity and coding performance. A whole family of multiplication-free arithmetic codes, which achieve the best coding efficiency and can be used for arbitrary size of alphabets, is derived. The complete tradeoff between the complexity of operations and compression performance of all the algorithms is presented     

Exact thresholds and optimal codes for the binary-symmetric channel and Gallager's decoding algorithm A

We show that for the case of the binary-symmetric channel and Gallager's decoding algorithm A the threshold can, in many cases, be determined analytically. More precisely, we show that the threshold is always upper-bounded by the minimum of (1-/spl lambda//sub 2//spl rho/'(1))/(/spl lambda/'(1)/spl rho/'(1)-/spl lambda//sub 2//spl rho/'(1)) and the smallest positive real root /spl tau/ of a specific polynomial p(x) and we observe that for most cases this bound is tight, i.e., it determines the threshold exactly. We also present optimal degree distributions for a large range of rates. In the case of rate one-half codes, for example, the threshold x/sub 0//sup */ of the optimal degree distribution is given by x/sup *//sub 0//spl sim/0.0513663. Finally, we outline how thresholds of more complicated decoders might be determined analytically.