For any finite discrete source, the competitive advantage of prefix code$C_{1}$over prefix code$C_{2}$is the probability$C_{1}$produces a shorter codeword than$C_{2}$, minus the probability$C_{2}$produces a shorter codeword than$C_{1}$. For any source, a prefix code is competitively optimal if it has a nonnegative competitive advantage over all other prefix codes. In 1991, Cover proved that Huffman codes are competitively optimal for all dyadic sources, namely sources whose symbol probabilities are negative integer powers of 2. We prove the following asymptotic converse: As the source size grows, the probability a Huffman code for a randomly chosen non-dyadic source is competitively optimal converges to zero. We also prove: (i) For any non-dyadic source, a Huffman code has a positive competitive advantage over a Shannon-Fano code; (ii) For any source, the competitive advantage of any prefix code over a Huffman code is strictly less than$\frac {1}{3}$; (iii) For each integer$n\gt 3$, there exists a source of size n and some prefix code whose competitive advantage over a Huffman code is arbitrarily close to$\frac {1}{3}$; and (iv) For each positive integer n, there exists a source of size n and some prefix code whose competitive advantage over a Shannon-Fano code becomes arbitrarily close to 1 as$n\to \infty $.

The 3/4 conjecture was posed 25 years ago by Ahlswede, Balkenhol, and Khachatrian, and states that if a multiset of positive integers has Kraft sum at most 3/4, then there exists a code that is both a prefix code and a suffix code with these integers as codeword lengths. We prove that the 3/4 conjecture is true whenever the given multiset of positive integers contains at most three distinct values.

The zero capacity region for hexagonal$(d,k)$run-length constraints is known for many, but not all,$d$and$k$. The pairs$(d,k)$for which it has been unproven whether the capacity is zero or positive consist of: (i)$k=d+2$when$d\ge 2$; (ii)$k=d+3$when$d \ge 1$; (iii)$k=d+4$when either$d=4$or$d$is odd and$d \ge 3$; and (iv)$k=d+5$when$d=4$. Here, we prove that the capacity is zero for all of case (i), and for case (ii) whenever$d \ge 7$. The method used in this paper is to reduce an infinite search space of valid labelings to a finite set of configurations that we exhaustively examine using backtracking. In Part II of this two-part series, we use automated procedures to prove that the capacity is zero in case (i) when$2 \le d \le 9$, in case (ii) when$3 \le d \le 11$, and in case (iii) when$d \in \{ 4,5,7,9 \}$, and that the capacity is positive in case (ii) when$d \in \{1,2\}$, in case (iii) when$d = 3$, and in case (iv). Thus, the only remaining unknown cases are now when$k=d+4$, for any odd$d \ge 11$.

The zero capacity region for hexagonal$(d,k)$run-length constraints is known for many, but not all,$d$and$k$. The pairs$(d,k)$for which it has been unproven whether the capacity is zero or positive consist of: (i)$k=d+2$when$d\ge 2$; (ii)$k=d+3$when$d \ge 1$; (iii)$k=d+4$when either$d=4$or$d$is odd and$d \ge 3$; and (iv)$k=d+5$when$d=4$. Here, we prove the capacity is zero in case (i) when$2 \le d \le 9$, in case (ii) when$3 \le d \le 11$, and in case (iii) when$d \in \{ 4,5,7,9 \}$. We also prove the capacity is positive in case (ii) when$d \in \{1,2\}$, in case (iii) when$d = 3$, and in case (iv). The zero capacities for$k=d+4$are the first and only known cases equal to zero when$k-d > 3$. All of our results are obtained by developing three algorithms that automatically and rigorously assist in proving either the zero or positive capacity results by efficiently searching large numbers of configurations. The proofs involve either upper bounding the number of paths through certain large directed graphs, finding forbidden strings, or building distinct tileable square labelings. Some of the proofs examine over 20 billion cases using a supercomputer. In Part I of this two-part series, it is proven that the capacity is zero for all of case (i), and for case (ii) whenever$d \ge 7$. Thus, the only remaining unknown cases are now when$k=d+4$, for any odd$d \ge 11$.

The rate of a network code is the ratio of the block size of the network's messages to that of its edge codewords. We compare the linear capacities and achievable rate regions of networks using finite field alphabets to the more general cases of arbitrary ring and module alphabets. For non-commutative rings, two-sided linearity is allowed. Specifically, we prove the following for directed acyclic networks. First, the linear rate region and the linear capacity of any network over a finite field depend only on the characteristic of the field. Furthermore, any two fields with different characteristics yield different linear capacities for at least one network. Second, whenever the characteristic of a given finite field divides the size of a given finite ring, each network's linear rate region over the ring is contained in its linear rate region over the field. Thus, any network's linear capacity over a field is at least its linear capacity over any other ring of the same size. An analogous result also holds for linear network codes over module alphabets. Third, whenever the characteristic of a given finite field does not divide the size of a given finite ring, there is some network whose linear capacity over the ring is strictly greater than its linear capacity over the field. Thus, for any finite field, there always exist rings over which some networks have higher linear capacities than over the field.

Linear network coding over finite fields is a wellstudied problem. We consider the more general setting of linear coding for directed acyclic networks with finite commutative ring alphabets. Our results imply that for scalar linear network coding over commutative rings, fields can always be used when the alphabet size is flexible, but other rings may be needed when the alphabet size is fixed. We prove that if a network has a scalar linear solution over some finite commutative ring, then the (unique) smallest such commutative ring is a field. We also show that fixed-size commutative rings are quasi-ordered, such that all the scalar linearly solvable networks over any given ring are also scalar linearly solvable over any higher-ordered ring. We study commutative rings that are maximal with respect to this quasiorder, as they may be considered the best commutative rings of a given size. We prove that a commutative ring is maximal if and only if some network is scalar linearly solvable over the ring, but not over any other commutative ring of the same size. Furthermore, we show that maximal commutative rings are direct products of certain fields specified by the integer partitions of the prime factor multiplicities of the ring's size. Finally, we prove that there is a unique maximal commutative ring of size m if and only if each prime factor of m has multiplicity in {1, 2, 3, 4, 6}. As consequences, 1) every finite field is such a maximal ring and 2) for each prime p, some network is scalar linearly solvable over a commutative ring of size pk but not over the field of the same size if and only if k ∉ {1, 2, 3, 4, 6}.

In Part I, we studied linear network coding over finite commutative rings and made comparisons to the well-studied case of linear network coding over finite fields. Here, we consider the more general setting of linear network coding over finite (possibly non-commutative) rings and modules. We prove the following results regarding the linear solvability of directed acyclic networks over various finite alphabets. For any network, the following are equivalent: (i) vector linear solvability over some field, (ii) scalar linear solvability over some ring, and (iii) linear solvability over some module. Analogously, the following are equivalent: (a) scalar linear solvability over some field, (b) scalar linear solvability over some commutative ring, and (c) linear solvability over some module whose ring is commutative. Whenever any network is linearly solvable over a module, a smallest such module arises in a vector linear solution for that network over a field. If a network is scalar linearly solvable over some non-commutative ring but not over any commutative ring, then such a non-commutative ring must have size at least 16, and for some networks, this bound is achieved. An infinite family of networks is demonstrated, each of which is scalar linearly solvable over some non-commutative ring but not over any commutative ring. Whenever p is prime and 1 ≤ k ≤ 6, if a network is scalar linearly solvable over some ring of size pk, then it is also k-dimensional vector linearly solvable over the field GF(p), but the converse does not necessarily hold. This result is extended to all k ≥ 1 when the ring is commutative.

For each positive composite integer m, a network is constructed, which is solvable over an alphabet of size m but is not solvable over any smaller alphabet. These networks have no linear solutions over any module alphabets and are not asymptotically linearly solvable over any finite-field alphabets. The networks' capacities are all shown to equal one, and their linear capacities are all shown to be bounded away from one for all finite-field alphabets. In addition, if m is a non-power-of-prime composite number, then such a network is not solvable over any prime-power-size alphabet.

For each integer m ≥ 2, a network is constructed which is solvable over an alphabet of size m but is not solvable over any smaller alphabets. If m is composite, then the network has no vector linear solution over any module alphabet. The network's capacity is shown to equal one, and when m is composite, its linear capacity is bounded away from one for all finite-field alphabets.

Determining the achievable rate region for networks using routing, linear coding, or nonlinear coding is thought to be a difficult task in general, and few are known. We describe the achievable rate regions for four interesting networks (completely for three and partially for the fourth). In addition to the known matrix-computation method for proving outer bounds for linear coding, we present a new method that yields actual characteristic-dependent linear rank inequalities from which the desired bounds follow immediately.

Two characteristic-dependent linear rank inequalities are given for eight variables. In particular, the first inequality holds for all finite fields whose characteristic is not three and does not in general hold over characteristic three. The second inequality holds for all finite fields whose characteristic is three and does not in general hold over characteristics other than three. Applications of these inequalities to the computation of capacity upper bounds in network coding are demonstrated.

Two characteristic-dependent linear rank inequalities are given for eight variables. Specifically, the first inequality holds for all finite fields whose characteristic is not three and does not in general hold over characteristic three. The second inequality holds for all finite fields whose characteristic is three and does not in general hold over characteristics other than three. Applications of these inequalities to the computation of capacity upper bounds in network coding are demonstrated.

We study the use of linear codes for network computing in single-receiver networks with various classes of target functions of the source messages. Such classes include reducible, semi-injective, and linear target functions over finite fields. Computing capacity bounds and achievability are given with respect to these target function classes for network codes that use routing, linear coding, or nonlinear coding.

We study the use of linear codes for network computing in single-receiver networks with various classes of target functions of the source messages. Such classes include reducible, injective, and semi-injective target functions. Computing capacity bounds are given with respect to these target function classes for network codes that use routing, linear coding, or nonlinear coding.

Networks derived from matroids have played a fundamental role in proving theoretical results about the limits of network coding. In this tutorial paper, we review many connections between matroids and network coding theory, with specific emphasis on network solvability, admissible network alphabet sizes, linear coding, and network capacity.

The following network computing problem is considered. Source nodes in a directed acyclic network generate independent messages and a single receiver node computes a target functionfof the messages. The objective is to maximize the average number of timesfcan be computed per network usage, i.e., the “computing capacity”. The network coding problem for a single-receiver network is a special case of the network computing problem in which all of the source messages must be reproduced at the receiver. For network coding with a single receiver, routing is known to achieve the capacity by achieving the network min-cut upper bound. We extend the definition of min-cut to the network computing problem and show that the min-cut is still an upper bound on the maximum achievable rate and is tight for computing (using coding) any target function in multi-edge tree networks. It is also tight for computing linear target functions in any network. We also study the bound's tightness for different classes of target functions. In particular, we give a lower bound on the computing capacity in terms of the Steiner tree packing number and a different bound for symmetric functions. We also show that for certain networks and target functions, the computing capacity can be less than an arbitrarily small fraction of the min-cut bound.

We study the computation of the arithmetic sum of the q-ary source messages in the reverse butterfly network. Specifically, we characterize the maximum rate at which the message sum can be computed at the receiver and demonstrate that linear coding is suboptimal.

An algorithm is given for placing relays at spatial positions to improve the reliability of communicated data in a sensor network. The network consists of many power-limited sensors, a small set of relays, and a receiver. For each sensor, the receiver receives a direct signal as well as an indirect signal from one of the available relays. The relays rebroadcast the transmissions in order to achieve diversity at the receiver. Both amplify-and-forward and decode-and-forward relay networks are considered. Channels are modeled with Rayleigh fading, path loss, and additive white Gaussian noise. Performance analysis and numerical results are given.

If beta and gamma are nonnegative integers and F is a field, then a polynomial collection {p1,..., pbeta}subeZ[alpha1,..., alphagamma] is said to be solvable over F if there exist omega1,..., omegagammaisinF such that for all i=1,..., beta we have pi(omega1,..., omegagamma)=0. We say that a network and a polynomial collection are solvably equivalent if for each field F the network has a scalar-linear solution over F if and only if the polynomial collection is solvable over F. Koetter and Medardpsilas work implies that for any directed acyclic network, there exists a solvably equivalent polynomial collection. We provide the converse result, namely that for any polynomial collection there exists a solvably equivalent directed acyclic network. (Hence, the problems of network scalar-linear solvability and polynomial collection solvability have the same complexity.) The construction of the network is modeled on a matroid construction using finite projective planes, due to MacLane in 1936. A set psi of prime numbers is a set of characteristics of a network if for every qisinpsi, the network has a scalar-linear solution over some finite field with characteristic q and does not have a scalar-linear solution over any finite field whose characteristic lies outside of psi. We show that a collection of primes is a set of characteristics of some network if and only if the collection is finite or co-finite. Two networks N and N' are ls-equivalent if for any finite field F, N is scalar-linearly solvable over F if and only if N' is scalar-linearly solvable over F. We further show that every network is ls-equivalent to a multiple-unicast matroidal network.

We study network coding capacity under a constraint on the total number of network nodes that can perform coding. That is, only a certain number of network nodes can produce coded outputs, whereas the remaining nodes are limited to performing routing. We prove that every nonnegative, monotonically nondecreasing, eventually constant, rational-valued function on the nonnegative integers is equal to the capacity as a function of the number of allowable coding nodes of some directed acyclic network.

If beta and gamma are nonnegative integers and F is a field, then a polynomial collection {p1,hellip,Pbeta} sube Z[alpha1,hellip, alphagamma] is said to be solvable over F if there exist omega1hellip, omegagammaisin F such that for all i = 1,hellip, beta we have pi(omega1hellip, omegagamma) = 0. We say that a network and a polynomial collection are solvably equivalent if for each field F the network has a scalar-linear solution over F if and only if the polynomial collection is solvable over F. Koetter and Medard's work implies that for any directed acyclic network, there exists a solvably equivalent polynomial collection. We provide the converse result, namely, that for any polynomial collection there exists a solvably equivalent directed acyclic network. (Hence, the problems of network scalar-linear solvability and polynomial collection solvability have the same complexity.) The construction of the network is modeled on a matroid construction using finite projective planes, due to MacLane in 1936. A set psi of prime numbers is a set of characteristics of a network if for every q isin psi, the network has a scalar-linear solution over some finite field with characteristic q and does not have a scalar-linear solution over any finite field whose characteristic lies outside of psi. We show that a collection of primes is a set of characteristics of some network if and only if the collection is finite or co-finite. Two networks N and N' are Is-equivalent if for any finite field F, N is scalar-linearly solvable over F if and only if N' is scalar- linearly solvable over F. We further show that every network is ls-equivalent to a multiple-unicast matroidal network.

We define a class of networks, called matroidal networks, which includes as special cases all scalar-linearly solvable networks, and in particular solvable multicast networks. We then present a method for constructing matroidal networks from known matroids. We specifically construct networks that play an important role in proving results in the literature, such as the insufficiency of linear network coding and the unachievability of network coding capacity. We also construct a new network, from the Vamos matroid, which we call the Vamos network, and use it to prove that Shannon-type information inequalities are in general not sufficient for computing network coding capacities. To accomplish this, we obtain a capacity upper bound for the Vamos network using a non-Shannon-type information inequality discovered in 1998 by Zhang and Yeung, and then show that it is smaller than any such bound derived from Shannon-type information inequalities. This is the first application of a non-Shannon-type inequality to network coding. We also compute the exact routing capacity and linear coding capacity of the Vamos network. Finally, using a variation of the Vamos network, we prove that Shannon-type information inequalities are insufficient even for computing network coding capacities of multiple-unicast networks.

It is known that linear codes are sufficient to solve the multicast network coding problem when each out-edge of a network node carries its own specific function of the in-edges of the node, i.e. operating in "point-to-point-mode." Alternatively, in "broadcast-mode," a network has the property that for each node, every out-edge of the node carries the same function of the in-edges of the node. Only one transmission is required in order to send the same function on all of the out-edges of a node. The edge functions in broadcast-mode can vary from node to node and each edge can carry an arbitrary number of transmissions, with at most one per time unit. We prove that linear codes are sufficient, in terms of total number of transmissions, for multicast networks in broadcast-mode. That is, we show that for any broadcast-mode solution to a multicast network, there exists a linear broadcast-mode solution over some finite field which does not increase the total number of network transmissions

All unconstrained information inequalities in three or fewer random variables are known to be "Shannon-type", in that they are nonnegative linear combinations of instances of the inequality I(A;B|C) ges 0. In 1998, Zhang and Yeung gave the first example of an information inequality in four variables that is not "Shannon-type". Here we give six new unconstrained non-Shannon information inequalities in four variables. The new inequalities are independent of each other and of the Zhang-Yeung inequality

An automated theorem proving technique is developed and is used to show that the capacity of the hexagonal (d, k) constraint is zero whenever k = d + 3 for d = 3,4, 5,7,9,11

We define the routing capacity of a network to be the supremum of all possible fractional message throughputs achievable by routing. We prove that the routing capacity of every network is achievable and rational, we present an algorithm for its computation, and we prove that every rational number in (0, 1] is the routing capacity of some solvable network. We also determine the routing capacity for various example networks. Finally, we discuss the extension of routing capacity to fractional coding solutions and show that the coding capacity of a network is independent of the alphabet used

The coding capacity of a network is the supremum of ratios k/n, for which there exists a fractional (k,n) coding solution, where k is the source message dimension and n is the maximum edge dimension. The coding capacity is referred to as routing capacity in the case when only routing is allowed. A network is said to achieve its capacity if there is some fractional (k,n) solution for which k/n equals the capacity. The routing capacity is known to be achievable for arbitrary networks. We give an example of a network whose coding capacity (which is 1) cannot be achieved by a network code. We do this by constructing two networks, one of which is solvable if and only if the alphabet size is odd, and the other of which is solvable if and only if the alphabet size is a power of 2. No linearity assumptions are made.

We prove that for any finite directed acyclic network, there exists a corresponding multiple-unicast network, such that for every alphabet, each network is solvable if and only if the other is solvable, and, for every finite-field alphabet, each network is linearly solvable if and only if the other is linearly solvable. The proof is constructive and creates an extension of the original network by adding exactly s+5m(r-1) new nodes where, in the original network, m is the number of messages, r is the average number of receiver nodes demanding each source message, and s is the number of messages emitted by more than one source. The construction is then used to create a solvable multiple-unicast network which becomes unsolvable over every alphabet size if all of its edge directions are reversed and if the roles of source-receiver pairs are reversed

Scalar quantizers with uniform decoders and channel-optimized encoders are studied for a uniform source on [0,1] and binary symmetric channels. Two families of affine index assignments are considered: the complemented natural code (CNC), introduced here, and the natural binary code (NBC). It is shown that the NBC never induces empty cells in the quantizer encoder, whereas the CNC can. Nevertheless, we show that the asymptotic distributions of quantizer encoder cells for the NBC and the CNC are equal and are uniform over a proper subset of the source's support region. Empty cells act as a form of implicit channel coding. An effective channel code rate associated with a quantizer designed for a noisy channel is defined and computed for the codes studied. By explicitly showing that the mean-squared error (MSE) of the CNC can be strictly smaller than that of the NBC, we also demonstrate that the NBC is suboptimal for a large range of transmission rates and bit error probabilities. This contrasts with the known optimality of the NBC when either both the encoder and decoder are not channel optimized, or when only the decoder is channel optimized.

Asymptotically optimal real-valued bit allocation among a set of quantizers for a finite collection of sources was derived in 1963 by Huang and Schultheiss, and an algorithm for obtaining an optimal nonnegative integer-valued bit allocation was given by Fox in 1966. We prove that, for a given bit budget, the set of optimal nonnegative integer-valued bit allocations is equal to the set of nonnegative integer-valued bit allocation vectors which minimize the Euclidean distance to the optimal real-valued bit-allocation vector of Huang and Schultheiss. We also give an algorithm for finding optimal nonnegative integer-valued bit allocations. The algorithm has lower computational complexity than Fox's algorithm, as the bit budget grows. Finally, we compare the performance of the Huang-Schultheiss solution to that of an optimal integer-valued bit allocation. Specifically, we derive upper and lower bounds on the deviation of the mean-squared error (MSE) using optimal integer-valued bit allocation from the MSE using optimal real-valued bit allocation. It is shown that, for asymptotically large transmission rates, optimal integer-valued bit allocations do not necessarily achieve the same performance as that predicted by Huang-Schultheiss for optimal real-valued bit allocations

Asymptotically optimal bit allocation among a set of quantizers for a finite collection of sources was determined by Huang and Schultheiss (1963). Their solution, however, gives a real-valued bit allocation, whereas in practice, integer-valued bit allocations are needed. We compare the performance of the Huang-Schultheiss solution to that of an optimal integer-valued bit allocation. Specifically, we derive upper and lower bounds on the deviation of the mean squared error using optimal integer-valued bit allocation from the mean squared error using optimal real-valued bit allocation. One consequence shown is that optimal integer-valued bit allocations do not necessarily achieve the same performance as that predicted by Huang-Schultheiss, for asymptotically large transmission rates. We also prove that integer bit allocation vectors that minimize the Euclidean distance to the optimal real-valued bit allocation vector are optimal integer bit allocations.

We define the routing capacity of a network to be the supremum of all possible fractional message throughputs achievable by routing. We prove that the routing capacity of every network is achievable and rational, we present an algorithm for its computation, and we prove that every non-negative rational number is the routing capacity of some network. We also determine the routing capacity for various example networks. Finally, we discuss the extension of routing capacity to fractional coding solutions and show that the coding capacity of a network is independent of the alphabet used

It is known that every solvable multicast network has a scalar linear solution over a sufficiently large finite field alphabet. It is also known that this result does not generalize to arbitrary networks. There are several examples in the literature of solvable networks with no scalar linear solution over any finite field. However, each example has a linear solution for some vector dimension greater than one. It has been conjectured that every solvable network has a linear solution over some finite field alphabet and some vector dimension. We provide a counterexample to this conjecture. We also show that if a network has no linear solution over any finite field, then it has no linear solution over any finite commutative ring with identity. Our counterexample network has no linear solution even in the more general algebraic context of modules, which includes as special cases all finite rings and Abelian groups. Furthermore, we show that the network coding capacity of this network is strictly greater than the maximum linear coding capacity over any finite field (exactly 10% greater), so the network is not even asymptotically linearly solvable. It follows that, even for more general versions of linearity such as convolutional coding, filter-bank coding, or linear time sharing, the network has no linear solution

It is known that every solvable multicast network has a scalar linear solution over a sufficiently large finite-field alphabet. It is also known that this result does not generalize to arbitrary networks. There are several examples in the literature of solvable networks with no scalar linear solution over any finite field. However, each example has a linear solution for some vector dimension greater than one. It has been conjectured that every solvable network has a linear solution over some finite-field alphabet and some vector dimension. We provide a counterexample to this conjecture. We also show that if a network has no linear solution over any finite field, then it has no linear solution over any finite commutative ring with identity. Our counterexample network has no linear solution even in the more general algebraic context of modules, which includes as special cases all finite rings and Abelian groups. Furthermore, we show that the network coding capacity of this network is strictly greater than the maximum linear coding capacity over any finite field (exactly 10% greater), so the network is not even asymptotically linearly solvable. It follows that, even for more general versions of linearity such as convolutional coding, filter-bank coding, or linear time sharing, the network has no linear solution.

Two sufficient conditions are given for the existence of binary fix-free codes (i.e., both prefix-free and suffix-free). Let L be a finite multiset of positive integers whose Kraft sum is at most 3/4. It is shown that there exists a fix-free code whose codeword lengths are the elements of L if either of the following two conditions holds: i) The smallest integer in L is at least 2, and no integer in L, except possibly the largest one, occurs more than 2/sup min(L)-2/ times. ii) No integer in L, except possibly the largest one, occurs more than twice. The results move closer to the Ahlswede-Balkenhol-Khachatrian conjecture that Kraft sums of at most 3/4 suffice for the existence of fix-free codes.

This paper describes cell density and effective channel code rates for quantizers with uniform decoders and channel-optimized encoders. In particular, the natural binary code index assignment is investigated which is called as modified natural code. The occurrences of empty encoding cells in such quantizers compute their effective channel code rate. Also the high-resolution distributions of the encoding cells are examined and the mean squared errors the quantizers achieve.

This paper describes the capacity bounds for the hard triangle model and examines such constraints for an equilateral triangular nonlattice tiling of the two-dimensional plane. The capacity is analyzed by deriving an upper bound analytically and obtain a lower bound by exhibiting a bit stuffing algorithm for hard-triangle constrained encoder. The encoder maps a random sequence of independent bits with the probability to calculate the coding rate of the encoder.

It is known that for every solvable multicast network, there exists a large enough finite-field alphabet such that a scalar linear solution exists. We prove: i) every binary solvable multicast network with at most two messages has a binary scalar linear solution; ii) for more than two messages, not every binary solvable multicast network has a binary scalar linear solution; iii) a multicast network that has a solution for a given alphabet might not have a solution for all larger alphabets.

We examine the performance of the Karhunen-Loeve transform (KLT) for transform coding applications. The KLT has long been viewed as the best available block transform for a system that orthogonally transforms a vector source, scalar quantizes the components of the transformed vector using optimal bit allocation, and then inverse transforms the vector. This paper treats fixed-rate and variable-rate transform codes of non-Gaussian sources. The fixed-rate approach uses an optimal fixed-rate scalar quantizer to describe the transform coefficients; the variable-rate approach uses a uniform scalar quantizer followed by an optimal entropy code, and each quantized component is encoded separately. Earlier work shows that for the variable-rate case there exist sources on which the KLT is not unique and the optimal quantization and coding stage matched to a "worst" KLT yields performance as much as 1.5 dB worse than the optimal quantization and coding stage matched to a "best" KLT. In this paper, we strengthen that result to show that in both the fixed-rate and the variable-rate coding frameworks there exist sources for which the performance penalty for using a "worst" KLT can be made arbitrarily large. Further, we demonstrate in both frameworks that there exist sources for which even a best KLT gives suboptimal performance. Finally, we show that even for vector sources where the KLT yields independent coefficients, the KLT can be suboptimal for fixed-rate coding.

Scalar quantizers with uniform encoders and channel optimized decoders are studied for uniform sources and binary symmetric channels. It is shown that the natural binary code (NBC) and folded binary code (FBC) induce point density functions that are uniform on proper subintervals of the source support, whereas the Gray code (GC) does not induce a point density function. The mean-squared errors (MSE) for the NBC, FBC, GC, and for randomly chosen index assignments are calculated and the NBC is shown to be mean-squared optimal among all possible index assignments, for all bit-error rates and all quantizer transmission rates. In contrast, it is shown that almost all index assignments perform poorly and have degenerate codebooks.

A rigorous derivation is given of the coding rate of a variable-to-variable length bit-stuffing coder for a two-dimensional (1,/spl infin/)-constrained channel. The coder studied is "nearly" a fixed-to-fixed length algorithm. Then an analogous variable-to-variable length bit-stuffing algorithm for the three-dimensional (1,/spl infin/)-constrained channel is presented, and its coding rate is analyzed using the two-dimensional method. The three-dimensional coding rate is demonstrated to be at least 0.502, which is proven to be within 4% of the capacity.

The performance of the KLT for transform coding applications was examined. The KLT has long been viewed as the best available block transform for transform coding. The fixed-rate and variable-rate transform codes were also presented. The fixed-rate approach uses an optimal fixed-rate scalar quantizer to describe the transform coefficients; the variable-rate approach uses a uniform scalar quantizer followed by an optimal entropy code. Earlier work shows that for the variable-rate case, there exist sources on which the KLT is not unique and the optimal transform code matched to a "worst" KLT yields performance as much as 1.5 dB worse than the optimal transform code matched to a "best" KLT. The results were strengthened to show that in both the fixed-rate and the variable-rate coding frameworks, there exist sources for which the performance penalty for using a "worst" KLT can be made arbitrarily large. Further demonstrations in both frameworks show that there exist sources for which even a best KLT gives suboptimal performance. Finally, the results show that even for vector sources where the KLT yields independent coefficients, the KLT can be suboptimal for fixed-rate coding.

The probability that a complete binary prefix code has a self-synchronizing string approaches one, as the number of codewords tends to infinity.

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.

Scalar quantizers with uniform encoders and channel optimized decoders are studied for uniform sources and binary symmetric channels. It is shown that the natural binary code and folded binary code induce point density functions that are uniform on proper subintervals of the source support, whereas the Gray code does not induce a point density function. The mean squared errors for the natural binary code, folded binary code, Gray code, and for randomly chosen index assignments are calculated and the natural binary code is shown to be mean squared optimal among all possible index assignments. In contrast, it is shown that almost all index assignments perform poorly and have degenerate codebooks.

An open problem in source coding theory has been whether the Karhunen-Loeve transform (KLT) is optimal for a system that orthogonally transforms a vector source, scalar quantizes the components of the transformed vector using optimal bit allocation, and then inverse transforms the vector. Huang and Schultheiss (1963) proved that for a Gaussian source the KLT is mean squared optimal in the limit of high quantizer resolution. It is often assumed and stated in the literature that the KLT is also optimal in general for nonGaussian sources. We disprove such assertions by demonstrating that the KLT is not optimal for certain nearly bimodal Gaussian and uniform sources. In addition, we show the unusual result that for vector sources with independent identically distributed Laplacian components, the distortion resulting from scalar quantizing the components can be reduced by including an orthogonal transform that adds intercomponent dependency.

The main. focus of research in stereo image coding has been disparity estimation (DE), a technique used to reduce coding rate by taking advantage of the redundancy in a stereo image pair. Significantly less effort has been put into the coding of the residual image. In this paper we propose a new method for the coding of residual images that takes into account the properties of residual images. Particular attention is paid to the effects of occlusion and the correlation properties of residual images that result from block-based disparity estimation. The embedded, progressive nature of our coder allows one to stop decoding at any time. We demonstrate that it is possible to achieve good results with a computationally simple method.

In this semitutorial paper, a comprehensive survey of closest point search methods for lattices without a regular structure is presented. The existing search strategies are described in a unified framework, and differences between them are elucidated. An efficient closest point search algorithm, based on the Schnorr-Euchner (1995) variation of the Pohst (1981) method, is implemented. Given an arbitrary point x /spl isin/ /spl Ropf//sup m/ and a generator matrix for a lattice /spl Lambda/, the algorithm computes the point of /spl Lambda/ that is closest to x. The algorithm is shown to be substantially faster than other known methods, by means of a theoretical comparison with the Kannan (1983, 1987) algorithm and an experimental comparison with the Pohst (1981) algorithm and its variants, such as the Viterbo-Boutros (see ibid. vol.45, p.1639-42, 1999) decoder. Modifications of the algorithm are developed to solve a number of related search problems for lattices, such as finding a shortest vector, determining the kissing number, computing the Voronoi (1908)-relevant vectors, and finding a Korkine-Zolotareff (1873) reduced basis.

A fixed-rate shape-gain quantizer for the memoryless Gaussian source is proposed. The shape quantizer is constructed from wrapped spherical codes that map a sphere packing in /spl Ropf//sup k-1/ onto a sphere in /spl Ropf//sup k/, and the gain codebook is a globally optimal scalar quantizer. A wrapped Leech lattice shape quantizer is used to demonstrate a signal-to-quantization-noise ratio within 1 dB of the distortion-rate function for rates above 1 bit per sample, and an improvement over existing techniques of similar complexity. An asymptotic analysis of the tradeoff between gain quantization and shape quantization is also given.

We present a packetization method for robust image transmission over packet erasure channels. The packets are formed in such a way that the image information is spread over different frequency bands and spatial locations to avoid complete disruption of certain image blocks in case of a packet loss. Experimental results are provided to demonstrate the performance of this method.

We consider the progressive transmission of a lossy source across a power constrained Gaussian channel using binary phase-shift keying modulation. Under the theoretical assumptions of infinite bandwidth, arbitrarily complex channel coding, and lossless transmission, we derive the optimal channel code rate and the optimal energy allocation per transmitted bit. Under the practical assumptions of a low complexity class of algebraic channel codes and progressive image coding, we numerically optimize the choice of channel code rate and the energy per bit allocation. This model provides an additional degree of freedom with respect to previously proposed schemes, and can achieve a higher performance for sources such as images. It also allows one to control bandwidth expansion or reduction.

Let A(n, d) denote the maximum possible number of codewords in an (n, d) binary code. We establish four new bounds on A(n, d), namely, A(21, 4)/spl les/43689, A(22, 4)/spl les/87378, A(22, 6)/spl les/6941, and A(23, 4)/spl les/173491. Furthermore, using previous upper bounds on the size of constant-weight binary codes, we reapply known methods to generate a table of bounds on A(n, d) for all n/spl les/28. This table extends the range of parameters compared with previously known tables.

We combine multiple description (MD) quantization, entropy coding, and data partitioning to improve the error resiliency of images over varying packet loss channels. Our proposed scheme degrades gracefully as channel conditions worsen. A multidimensional extension of the two-channel multiple description scalar quantizer (MDSQ) improves robustness. A high performance wavelet image coder is designed for MDSQ, using the set-partitioning-in-hierarchical-trees (SPIHT) algorithm for entropy coding. Experimentally, with 4 descriptions, the new coder outperforms previous reports at any loss rate.

Principal curves have been defined as "self-consistent" smooth curves which pass through the "middle" of a d-dimensional probability distribution or data cloud. They give a summary of the data and also serve as an efficient feature extraction tool. We take a new approach by defining principal curves as continuous curves of a given length which minimize the expected squared distance between the curve and points of the space randomly chosen according to a given distribution. The new definition makes it possible to theoretically analyze principal curve learning from training data and it also leads to a new practical construction. Our theoretical learning scheme chooses a curve from a class of polygonal lines with k segments and with a given total length to minimize the average squared distance over n training points drawn independently. Convergence properties of this learning scheme are analyzed and a practical version of this theoretical algorithm is implemented. In each iteration of the algorithm, a new vertex is added to the polygonal line and the positions of the vertices are updated so that they minimize a penalized squared distance criterion. Simulation results demonstrate that the new algorithm compares favorably with previous methods, both in terms of performance and computational complexity, and is more robust to varying data models.

One method of transmitting wavelet based zerotree encoded images over noisy channels is to add channel coding without altering the source coder. A second method is to reorder the embedded zerotree bitstream into packets containing a small set of wavelet coefficient trees. We consider a hybrid mixture of these two approaches and demonstrate situations in which the hybrid image coder can outperform either of the two building block methods, namely on channels that can suffer packet losses as well as statistically varying bit errors.

Let A(n,d,w) denote the maximum possible number of codewords in an (n,d,w) constant-weight binary code. We improve upon the best known upper bounds on A(n,d,w) in numerous instances for n/spl les/24 and d/spl les/12, which is the parameter range of existing tables. Most improvements occur for d=8, 10, where we reduce the upper bounds in more than half of the unresolved cases. We also extend the existing tables up to n/spl les/28 and d/spl les/14. To obtain these results, we develop new techniques and introduce new classes of codes. We derive a number of general bounds on A(n,d,w) by means of mapping constant-weight codes into Euclidean space. This approach produces, among other results, a bound on A(n,d,w) that is tighter than the Johnson bound. A similar improvement over the best known bounds for doubly-constant-weight codes, studied by Johnson and Levenshtein, is obtained in the same way. Furthermore, we introduce the concept of doubly-bounded-weight codes, which may be thought of as a generalization of the doubly-constant-weight codes. Subsequently, a class of Euclidean-space codes, called zonal codes, is introduced, and a bound on the size of such codes is established. This is used to derive bounds for doubly-bounded-weight codes, which are in turn used to derive bounds on A(n,d,w). We also develop a universal method to establish constraints that augment the Delsarte inequalities for constant-weight codes, used in the linear programming bound. In addition, we present a detailed survey of known upper bounds for constant-weight codes, and sharpen these bounds in several cases. All these bounds, along with all known dependencies among them, are then combined in a coherent framework that is amenable to analysis by computer. This improves the bounds on A(n,d,w) even further for a large number of instances of n, d, and w.

A binary sequence satisfies a one-dimensional (d,k) run length constraint if every run of zeros has length at least d and at most k. A two-dimensional binary pattern is (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/)-constrained if it satisfies the one-dimensional (d/sub 1/,k/sub 1/) run length constraint horizontally and the one-dimensional (d/sub 2/,k/sub 2/) run length constraint vertically. For given d/sub 1/, k/sub 1/, d/sub 2/, and k/sub 2/, the asymmetric two-dimensional capacity is defined as C/sub d1,k1,d2,k2/=lim/sub m,n/spl rarr//spl infin// (1/(mn)) log/sub 2/ N/sub m,n//sup (d1,k1,d2,k2)/ where N/sub m,n//sup (d1,k1,d2,k2)/ denotes the number of (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/)-constrained m/spl times/n binary patterns. We determine whether the capacity is positive or is zero, for many choices of (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/).

High-resolution bounds in lossy coding of a real memoryless source are considered when side information is present. Let X be a "smooth" source and let Y be the side information. First we treat the case when both the encoder and the decoder have access to Y and we establish an asymptotically tight (high-resolution) formula for the conditional rate-distortion function R/sub X|Y/(D) for a class of locally quadratic distortion measures which may be functions of the side information. We then consider the case when only the decoder has access to the side information (i.e., the "Wyner-Ziv problem"). For side-information-dependent distortion measures, we give an explicit formula which tightly approximates the Wyner-Ziv rate-distortion function R/sup WZ/(D) for small D under some assumptions on the joint distribution of X and Y. These results demonstrate that for side-information-dependent distortion measures the rate loss R/sup WZ/(D)-R/sub X|Y/(D) can be bounded away from zero in the limit of small D. This contrasts the case of distortion measures which do not depend on the side information where the rate loss vanishes as D/spl rarr/0.

We derive bounds for optimal rate allocation between source and channel coding for linear channel codes that meet the Gilbert-Varshamov or Tsfasman-Vladut-Zink (1984) bounds. Formulas giving the high resolution vector quantizer distortion of these systems are also derived. In addition, we give bounds on how far below the channel capacity the transmission rate should be for a given delay constraint. The bounds obtained depend on the relationship between channel code rate and relative minimum distance guaranteed by the Gilbert-Varshamov bound, and do not require sophisticated decoding beyond the error correction limit. We demonstrate that the end-to-end mean-squared error decays exponentially fast as a function of the overall transmission rate, which need not be the case for certain well-known structured codes such as Hamming codes.

Achievable distortion bounds are derived for the cascade of structured families of binary linear channel codes and binary lattice vector quantizers. It is known that for the cascade of asymptotically good channel codes and asymptotically good vector quantizers the end-to-end distortion decays to zero exponentially fast as a function of the overall transmission rate, and is achieved by choosing a channel code rate that is independent of the overall transmission rate. We show that for certain families of practical channel codes and binary lattice vector quantizers, the overall distortion can be made to decay to zero exponentially fast as a function of the square root of transmission rate. This is achieved by carefully choosing a channel code rate that decays to zero as the transmission rate grows. Explicit channel code rate schedules are obtained for several well-known families of channel codes.

The capacity C/sub 0,1//sup (8)/ of a three-dimensional (0,1) run length constrained channel is shown to satisfy 0.522501741838/spl les/C/sub 0,1//sup (8)//spl les/0.526880847825.

Achievable distortion bounds are derived for the cascade of structured families of binary linear channel codes and binary lattice vector quantizers. It is known that for the cascade of asymptotically good channel codes and asymptotically good vector quantizers the end-to-end distortion decays to zero exponentially fast as a function of the overall transmission rate, and is achieved by choosing a channel code rate that is independent of the overall transmission rate. We show that for certain families of practical channel codes and binary lattice vector quantizers, the overall distortion can still be made to decay to zero exponentially fast as the transmission rate grows, although the exponent is a sub-linear function of the transmission rate. This is achieved by carefully choosing a channel code rate that decays to zero as the transmission rate grows. Explicit channel code rate schedules are obtained for several well-known families of channel codes.

We investigate the problem of selecting blocklength and code rate for progressive image transmission, motivated by turbo coding methods where the performance improves with blocklength. The problem is to balance the tradeoff among error protection, source coding rate, and delay. We propose a general performance measure for evaluating progressive transmission and use dynamic programming to determine the channel code parameters based on the progressive performance. Performance results are provided for the evaluation of the gains over less complex methods as a function of channel error rate.

The asymptotic (small distortion) behavior of the rate-distortion function of an n-dimensional source vector with mixed distribution is derived. The source distribution is a finite mixture of components such that under each component distribution a certain subset of the coordinates have a discrete distribution while the remaining coordinates have a joint density. The expected number of coordinates with a joint density is shown to equal the rate-distortion dimension of the source vector. Also, the exact small distortion asymptotic behavior of the rate-distortion function of a special but interesting class of stationary information sources is determined.

Two-dimensional binary patterns that satisfy one-dimensional (d, k) run-length constraints both horizontally and vertically are considered. For a given d and k, the capacity C/sub d,k/ is defined as C/sub d,k/=lim/sub m,n/spl rarr//spl infin//log/sub 2/N/sub m,n//sup d,k//mn, where N/sub m,n//sup d,k/ denotes the number of m/spl times/n rectangular patterns that satisfy the two-dimensional (d,k) run-length constraint. Bounds on C/sub d,k/ are given and it is proven for every d/spl ges/1 and every k>d that C/sub d,k/=0 if and only if k=d+1. Encoding algorithms are also discussed.

Entropy-coded vector quantization is studied using high-resolution multidimensional companding over a class of nondifference distortion measures. For distortion measures which are "locally quadratic" a rigorous derivation of the asymptotic distortion and entropy-coded rate of multidimensional companders is given along with conditions for the optimal choice of the compressor function. This optimum compressor, when it exists, depends on the distortion measure but not on the source distribution. The rate-distortion performance of the companding scheme is studied using an asymptotic expression for the rate-distortion function which parallels the Shannon lower bound for difference distortion measures. It is proved that the high-resolution performance of the scheme is arbitrarily close to the rate-distortion limit for large quantizer dimensions if the compressor function and the lattice quantizer used in the companding scheme are optimal, extending an analogous statement for entropy-coded lattice quantization and MSE distortion. The companding approach is applied to obtain a high-resolution quantizing scheme for noisy sources.

It is known that among all redundancy-free codes (or index assignments), the natural binary code minimizes the mean-squared error (MSE) of the uniform source and uniform quantizer on a binary symmetric channel. We derive a code which maximizes the MSE and demonstrate that the code is linear and its distortion is asymptotically equivalent, as the block length grows, to the expected distortion of an index assignment chosen uniformly at random.

We present a lower bound on the probability of symbol error for maximum-likelihood decoding of lattices and lattice codes on a Gaussian channel. The bound is tight for error probabilities and signal-to-noise ratios of practical interest, as opposed to most existing bounds that become tight asymptotically for high signal-to-noise ratios. The bound is also universal; it provides a limit on the highest possible coding gain that may be achieved, at specific symbol error probabilities, using any lattice or lattice code in n dimensions. In particular, it is shown that the effective coding gains of the densest known lattices are much lower than their nominal coding gains. The asymptotic (as n/spl rarr//spl infin/) behavior of the new bound is shown to coincide with the Shannon (1948) limit for Gaussian channels.

Consider encoding a memoryless source using two descriptions, the first at rate R/sub 1/ and distortion d/sub 1/, the second at rate R/sub 2/ and distortion d/sub 2/. Combining the two descriptions the source can be reconstructed with distortion d/sub 0/. For a Gaussian source of variance /spl sigma//sup 2/, Ozarow (1980) found an explicit characterization of the region R*(/spl sigma//sup 2/; d/sub 1/,d/sub 2/,d/sub 0/)/spl sub/R/sup 2/ of achievable rate pairs (R/sub 1/, R/sub 2/) with given mean squared distortions d/sub 1/, d/sub 2/, and d/sub 0/. This is the only case for which the multiple description rate-distortion region is completely known. We show that for a general real valued source X and a locally quadratic distortion measure of the form /spl rho/(x,x/spl circ/)=w(x)/sup 2/(x-x/spl circ/)/sup 2/+o((x-x/spl circ/)/sup 2/), the region of admissible rate pairs is arbitrary well approximated in the limit of small distortions by the region R*(P/sub X/2/sup 2E{log m(X)}/; d/sub 1/,d/sub 2/,d/sub 0/) where R*(/spl sigma//sup 2/; d/sub 1/,/sub 2/, d/sub 0/) denotes the multiple description rate region of a Gaussian source with variance /spl sigma//sup 2/, and where P/sub X/ is the entropy-power of the source. Applications to companding quantization are also considered.

We study joint source-channel coding for a power constrained Gaussian channel and its application to progressive image compression. For a given power constrained, we consider the optimum allocation of energy per bit for a BPSK transmitter and the best choice of channel code rate, when the performance is measured by end-to-end average quantizer distortion. Choosing the average energy per transmitted bit in conjunction with both the source rate and the channel code rate provides an additional degree of freedom with respect to previously proposed schemes, and therefore can achieve higher overall PSNRs for images.

A product channel code is proposed to protect progressively compressed and packetized image data that is transmitted across noisy channels. Across packets, the product code is composed of Reed-Solomon codes. Within packets, the product code uses the concatenation of a rate compatible punctured convolutional code and an error detecting parity check code. The benefits include flexibility in terms of delay, the ability to easily adapt the level of protection based on importance (i.e., unequal error protection), and scalable decoding complexity. The system outperforms the best known image coders for memoryless channels and performs well on fading channels.

We present a method for ordering the wavelet coefficient information in a compressed bitstream that allows an image to be sequentially decoded, with lower memory requirements than conventional wavelet decompression schemes. We also introduce a hybrid filtering scheme that uses different horizontal and vertical filters, each with different depths of wavelet decomposition. This reduces decoder memory requirements by reducing the instantaneous number of wavelet coefficients needed for inverse filtering.

Product channel codes are proposed to protect progressively compressed and packetized images for noisy channels. Within packets, the product code uses the concatenation of a rate-compatible punctured convolutional code and an error detecting parity check code. Across packets, Reed-Solomon codes are used. Benefits include flexible choice of delay, adaptability of error protection level (i.e., unequal error protection), and scalable decoding complexity. The system outperforms the best known image coders for memoryless channels and performs well on fading channels.

We determine analytic expressions for the performance of some low-complexity combined source-channel coding systems. The main tool used is the Hadamard transform. In particular, we obtain formulas for the average distortion of binary lattice vector quantization with affine index assignments, linear block channel coding, and a binary-symmetric channel. The distortion formulas are specialized to nonredundant channel codes for a binary-symmetric channel, and then extended to affine index assignments on a binary-asymmetric channel. Various structured index assignments are compared. Our analytic formulas provide a computationally efficient method for determining the performance of various coding schemes. One interesting result shown is that for a uniform source and uniform quantizer, the natural binary code is never optimal for a nonsymmetric channel, even though it is known to be optimal for a symmetric channel.

Numerous sophisticated techniques have been developed over the last several decades to efficiently transmit images across noisy channels. Here, we cascade an existing image coder with carefully chosen error control coding, and thus produce a progressive image compression scheme whose performance on a noisy channel is significantly better than that of previously known image compression techniques. The main idea is to trade off the available transmission rate between source coding and channel coding in an efficient manner. This coding system is easy to implement and has acceptably low complexity. Furthermore, effectively no degradation due to channel noise can be detected; instead, the penalty paid due to channel noise is a reduction in source coding resolution. As an example, for the 512/spl times/512 Lena image, at an overall transmission rate of 1 bit per pixel, and for binary symmetric channels with bit error probabilities 10/sup -3/, 10/sup -2/, and 10/sup -1/, the proposed system typically outperforms other existing systems by at least 2.6 dB, 2.8 dB, and 8.9 dB, respectively.

We present a wavelet-based progressive image coding system that allows the specification of regions of interest to alter the spatial allocation of future transmitted bits. When used in an interactive mode with feedback, the viewer, after seeing a low resolution version of the image, can instruct the encoder to concentrate more effort on coding regions of interest. When operating in an independent mode, the encoder can select regions of interest based on automatic feature recognition algorithms or offline human selection. The algorithm is flexible enough to adapt to changes of interest during encoding.

We cascade an existing image coder with carefully chosen error control coding, and thus produce a progressive image compression scheme whose performance on a noisy channel is significantly better than that of previously known techniques. The main idea is to trade off the available transmission rate between source coding and channel coding in an efficient manner. This coding system is easy to implement and has acceptably low complexity. Furthermore, effectively no degradation due to channel noise can be detected; instead, the penalty paid due to channel noise is a reduction in source coding resolution. Detailed numerical comparisons are given that can serve as benchmarks for comparisons with future encoding schemes. For example, for the 512/spl times/512 Lena image, at a transmission rate of 1 b/pixel, and for binary symmetric channels with bit error probabilities 10/sup -3/, 10/sup -2/, and 10/sup -1/, the proposed system outperforms previously reported results by at least 2.6, 2.8, and 8.9 dB, respectively.

The maximum size of binary radar arrays (matrices) with only eight or fewer rows has previously been determined. We determine the maximum size of radar arrays containing 9-16 rows, and for those containing 17 rows we narrow the maximum size down to two values. We also give improved upper and lower asymptotic bounds on the maximum size of radar arrays, which narrow the gap between the existing upper and lower asymptotic bounds by more than 25%.

A new class of spherical codes called wrapped spherical codes is constructed by "wrapping" any sphere packing /spl Lambda/ in Euclidean space onto a finite subset of the unit sphere in one higher dimension. The mapping preserves much of the structure of /spl Lambda/, and unlike previously proposed maps, the density of the wrapped spherical codes approaches the density of /spl Lambda/ as the minimum distance approaches zero. We show that this implies that the asymptotically maximum spherical coding density is achieved by wrapped spherical codes whenever /spl Lambda/ is the densest possible sphere packing.

For pt. I see ibid., vol.43, no.6, p.1774-85, 1997. New spherical codes called laminated spherical codes are constructed in dimensions 2-49 using a technique similar to the construction of laminated lattices. Each spherical code is recursively constructed from existing spherical codes in one lower dimension. Laminated spherical codes outperform the best known spherical codes in the minimum distance sense for many code sizes. The density of a laminated spherical code approaches the density of the laminated lattice in one lower dimension, as the minimum distance approaches zero. In particular, the three-dimensional laminated spherical code is asymptotically optimal, in the sense that its density approaches the Fejes Toth (1959) upper bound as the minimum distance approaches zero. Laminated spherical codes perform asymptotically as well as wrapped spherical codes in those dimensions where laminated lattices are optimal sphere packings.

A fundamental problem in the transmission of analog information across a noisy discrete channel is the choice of channel code rate that optimally allocates the available transmission rate between lossy source coding and block channel coding. We establish tight bounds on the channel code rate that minimizes the average distortion of a vector quantizer cascaded with a channel coder and a binary-symmetric channel. Analytic expressions are derived in two cases of interest: small bit-error probability and arbitrary source vector dimension; arbitrary bit-error probability and large source vector dimension. We demonstrate that the optimal channel code rate is often substantially smaller than the channel capacity, and obtain a noisy-channel version of the Zador (1982) high-resolution distortion formula.

The problem of vector quantizer empirical design for noisy channels or for noisy sources is studied. It is shown that the average squared distortion of a vector quantizer designed optimally from observing clean independent and identically distributed (i.i.d.) training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the clean source and transmitting across a discrete memoryless noisy channel. Similarly, it is shown that if the source is corrupted by additive noise, then the average squared distortion of a vector quantizer designed optimally from observing i.i.d. noisy training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the noisy source and transmitting across a noiseless channel. Rates of convergence are also provided.

It is proven that for every random variable with a countably infinite set of outcomes and finite entropy there exists an optimal prefix code which can be constructed from Huffman codes for truncated versions of the random variable, and that the average lengths of any sequence of Huffman codes for the truncated versions converge to that of the optimal code. Also, it is shown that every optimal infinite code achieves Kraft's inequality with equality.

The problem of vector quantizer empirical design for noisy channels or for noisy sources is studied. It is shown that the average squared distortion of a vector quantizer designed optimally from observing clean i.i.d. training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the clean source and transmitting across a discrete memoryless noisy channel. Similarly, it is shown that if the source is corrupted by additive noise, then the average squared distortion of a vector quantizer designed optimally from observing i.i.d. noisy training vectors converges in expectation, as the training set size grows, to the minimum possible mean-squared error obtainable for quantizing the noisy source and transmitting across a noiseless channel. Rates of convergence are also provided.

The problem of fixed-rate block quantization of an unbounded real memoryless source is studied. It is proved that if the source has a finite sixth moment, then there exists a sequence of quantizers Q/sub n/ of increasing dimension n and fixed rate R such that the mean squared distortion /spl Delta/(Q/sub n/) is bounded as /spl Delta/(Q/sub n/)/spl les/D(R)+O(/spl radic/(log n/n)), where D(R) is the distortion-rate function of the source. Applications of this result include the evaluation of the distortion redundancy of fixed-rate universal quantizers, and the generalization to the non-Gaussian case of a result of Wyner on the transmission of a quantized Gaussian source over a memoryless channel.

In pattern recognition or, as it has also been called, concept learning, the value of a { 0,1}-valued random variable Y is to be predicted based upon observing an R/sup d/-valued random variable X. We apply the method of complexity regularization to learn concepts from large concept classes. The method is shown to automatically find a good balance between the approximation error and the estimation error. In particular, the error probability of the obtained classifier is shown to decrease as O(/spl radic/(logn/n)) to the achievable optimum, for large nonparametric classes of distributions, as the sample size n grows. We also show that if the Bayes error probability is zero and the Bayes rule is in a known family of decision rules, the error probability is O(logn/n) for many large families, possibly with infinite VC dimension.

A fixed-rate universal lossy coding scheme is introduced for independent and identically distributed (i.i.d.) sources. It is shown for finite alphabet sources and arbitrary single letter distortion measures that as the sample size n grows the expected distortion obtained using this universal scheme converges to Shannon's distortion rate function D(R) at a rate O(log n/n). The scheme can be extended to universal quantization of real i.i.d sources subject to a squared error criterion. It is shown in this case that the per-letter distortion converges to D(R) at a rate O(/spl radic/(log n/n)) both in expectation and almost surely for any real-valued bounded i.i.d. source.>

A general notion of universal consistency of nonparametric estimators is introduced that applies to regression estimation, conditional median estimation, curve fitting, pattern recognition, and learning concepts. General methods for proving consistency of estimators based on minimizing the empirical error are shown. In particular, distribution-free almost sure consistency of neural network estimates and generalized linear estimators is established.>

A universal source coding system with vector quantizer codebook transmissions is studied using high resolution quantization theory. Conditions are derived for the optimal tradeoff between quantizer resolution and the information rate used to transmit codebooks. A formula that tightly bounds the mean squared error of the universal coding system as a function of the time between codebook transmissions is experimentally verified and found to be tight, and a new and simpler derivation is given. Other research in the literature has proposed vector quantizing the transmitted codebooks; one conclusion we prove here is that under some reasonable conditions uniform scalar quantization of the transmitted codebooks performs as well as vector quantizing them. Experimental results are given that support the analytic derivations.>

Rate of convergence results are established for vector quantization. Convergence rates are given for an increasing vector dimension and/or an increasing training set size. In particular, the following results are shown for memoryless real-valued sources with bounded support at transmission rate R. (1) If a vector quantizer with fixed dimension k is designed to minimize the empirical mean-square error (MSE) with respect to m training vectors, then its MSE for the true source converges in expectation and almost surely to the minimum possible MSE as O(/spl radic/(log m/m)). (2) The MSE of an optimal k-dimensional vector quantizer for the true source converges, as the dimension grows, to the distortion-rate function D(R) as O(/spl radic/(log k/k)). (3) There exists a fixed-rate universal lossy source coding scheme whose per-letter MSE on a real-valued source samples converges in expectation and almost surely to the distortion-rate function D(R) as O((/spl radic/(loglog n/log n)). (4) Consider a training set of n real-valued source samples blocked into vectors of dimension k, and a k-dimension vector quantizer designed to minimize the empirical MSE with respect to the m=[n/k] training vectors. Then the per-letter MSE of this quantizer for the true source converges in expectation and almost surely to the distortion-rate function D(R) as O(/spl radic/(log log n/log n))), if one chooses k=[(1/R)(1-/spl epsiv/)log n] for any /spl epsiv//spl isin/(0.1).>

Two results are given. First, using a result of Csiszar (1973) the asymptotic (i.e., high-resolution/low distortion) performance for entropy-constrained tessellating vector quantization, heuristically derived by Gersho (1979), is proven for all sources with finite differential entropy. This implies, using Gersho's conjecture and Zador's formula, that tessellating vector quantizers are asymptotically optimal for this broad class of sources, and generalizes a rigorous result of Gish and Pierce (1968) from the scalar to the vector case. Second, the asymptotic performance is established for Zamir and Feder's (1992) randomized lattice quantization. With the only assumption that the source has finite differential entropy, it is proven that the low-distortion performance of the Zamir-Feder universal vector quantizer is asympotically the same as that of the deterministic lattice quantizer.>

A Euclidean code is a finite set of points in n-dimensional Euclidean space /spl Rscr//sup n/. The total number of nearest neighbors of a given codepoint in the code is called its touching number. We show that the maximum number of codepoints F/sub n/ that can share the same nearest-neighbor codepoint is equal to the maximum kissing number /spl tau//sub n/ in n dimensions, that is, the maximum number of unit spheres that can touch a given unit sphere without overlapping. We then apply a known upper bound on /spl tau//sub n/ to obtain F/sub n//spl les/2/sup n(0.401+o(1))/, which improves upon the best known upper known upper bound of F/sub n//spl les/2/sup n(1+o(1))/. We also show that the average touching number T of all the points in a Euclidean code is upper bounded /spl tau//sub n/.>

Asymptotically optimal zero-delay vector quantization in the presence of channel noise is studied using random coding techniques. First, an upper bound is derived for the average rth-power distortion of channel optimized k-dimensional vector quantization at transmission rate R on a binary symmetric channel with bit error probability /spl epsiv/. The upper bound asymptotically equals 2/sup -rRg(/spl epsiv/,k,r/). where k/(k +r) [1 - log/sub 2/(l +2/spl radic/(/spl epsiv/(1-/spl epsiv/))] /spl les/g(/spl epsiv/,k,r)/spl les/1) for all /spl epsiv//spl ges/0, lim/sub /spl epsiv//spl rarr/0/g(/spl epsiv/,k,r)=1, and lim/sub k/spl rarr//spl infin//g(/spl epsiv/,k,r)=1. Numerical computations of g(/spl epsiv/,k,r) are also given. This result is analogous to Zador's (1982) asymptotic distortion rate of 2/sup -rR/ for quantization on noiseless channels. Next, using a random coding argument on nonredundant index assignments, a useful upper bound is derived in terms of point density functions, on the minimum mean squared error of high resolution, regular, vector quantizers in the presence of channel noise. The formula provides an accurate approximation to the distortion of a noisy channel quantizer whose codebook is arbitrarily ordered. Finally, it is shown that the minimum mean squared distortion of a regular, noisy channel VQ with a randomized nonredundant index assignment, is, in probability, asymptotically bounded away from zero.>

The authors show that without knowing anything about the statistics of a bounded real-valued memoryless source, it is possible to construct a sequence of codes, of rate not exceeding a fixed number R>0, such that the per-letter sample distortion converges to the distortion-rate function D(R) with probability one as the length of the message approaches infinity. It is proven that the distortion converges to D(R) as square root log log n/log n almost surely, where n is the length of the data to be transmitted.>

Upper and lower bounds are derived for the average number of facets per cell in the encoder partition of binary tree-structured vector quantizers. The achievability of the bounds is described as well. It is shown that the average number of facets per cell for unbalanced trees must lie asymptotically between three and four in R/sup 2/, and each of these bounds can be achieved, whereas for higher dimensions it is shown that an arbitrarily large percentage of the cells can each have a linear number (in codebook size) of facets. Analogous results are also indicated for balanced trees.>

A high-resolution analysis is presented for a universal vector quantization scheme based on periodic codebook transmissions. The scheme assumes a slowly changing nonstationary source such as an image and periodically transmits new updated codebooks as side information to the receiver. The side information is transmitted via a large universal codebook which itself acts as a quantizer for the updated codebooks to be transmitted. This scheme generalizes the more simple technique of adapting a codebook by transmitting its vector components one at a time using a fixed uniform scalar quantizer. These schemes are compared both theoretically and experimentally and side information is determined.>

An approach to quantizing discrete-time memoryless sources is presented. An important feature is that its performance is largely insensitive to errors in modeling the input PDF. The method involves changing the amplitude distribution of the source to be approximately Gaussian by all-pass filtering, then applying a Lloyd-Max quantizer designed for a Gaussian source. After quantization, the samples are passed through another all-pass filter, which is an approximate inverse of the first filter. The mean-square error (MSE) for the overall process is roughly equal to the quantization MSE for the intermediate Gaussian signal, independent of the source statistics. For some sources, this is actually an improvement over direct, correct-model Lloyd-Max quantization. The cost of this technique is some delay due to filtering.>

A technique for designing vector quantizers that is well suited for parallel processing environments is presented. The input space is iteratively partitioned into M disjoint connected regions composed of unions of partition regions. Each of M processors then independently commutes an optimal subquantizer for its restricted input space. The partitions can regularly be changed to further improve the overall quantizer performance. This technique can improve on the performance of the generalized Lloyd algorithm by following the traditional design process with the subpartitioning iterations.>

A technique for efficient vector quantization (VQ) design based on conjugate-gradient search methods is introduced. It is demonstrated experimentally that the new design algorithm performs better than the generalized Lloyd algorithm in many cases in terms of computation time and/or quality of the codebook it produces.>

A pseudo-Gray code is an assignment of n-bit binary indexes to 2" points in a Euclidean space so that the Hamming distance between two points corresponds closely to the Euclidean distance. Pseudo-Gray coding provides a redundancy-free error protection scheme for vector quantization (VQ) of analog signals when the binary indexes are used as channel symbols on a discrete memoryless channel and the points are signal codevectors. Binary indexes are assigned to codevectors in a way that reduces the average quantization distortion introduced in the reproduced source vectors when a transmitted index is corrupted by channel noise. A globally optimal solution to this problem is generally intractable due to an inherently large computational complexity. A locally optimal solution, the binary switching algorithm, is introduced, based on the objective of minimizing a useful upper bound on the average system distortion. The algorithm yields a significant reduction in average distortion, and converges in reasonable running times. The sue of pseudo-Gray coding is motivated by the increasing need for low-bit-rate VQ-based encoding systems that operate on noisy channels, such as in mobile radio speech communications.>