The length of a typical Huffman codeword

If p_i(i=1,···, N) is the probability of the ith letter of a memoryless source, the length l_i of the corresponding binary Huffman codeword can be very different from the value -log p_i. For a typical letter, however, l_i≈-logp_i. More precisely, P_m ^-=Σ/sub j∈{i|l<-logpj-m}/p_j<2^-m and P_m ⁺=Σ/sub j∈{i|li>-logpi+m/}p_j<2^-c(m-2)+2, where c≈2.27     

Upper bounds on trellis complexity of lattices

Unlike block codes, n-dimensional lattices can have minimal trellis diagrams with an arbitrarily large number of states, branches, and paths. In particular, we show by a counterexample that there is no f(n), a function of n, such that all rational lattices of dimension n have a trellis with less than f(n) states. Nevertheless, using a theorem due to Hermite, we prove that every integral lattice Λ of dimension n has a trellis T, such that the total number of paths in T is upper-bounded by P(T)⩽n!(2/√3)^n2(n-1/2)V(Λ) ^n-1 where V(n) is the volume of Λ. Furthermore, the number of states at time i in T is upper-bounded by |S_i|⩽(2/√3)^i2(n-1)V(Λ)²ⁱ² n/. Although these bounds are seldom tight, these are the first known general upper bounds on trellis complexity of lattices     

The dynamics of group codes: state spaces, trellis diagrams, andcanonical encoders

A group code C over a group G is a set of sequences of group elements that itself forms a group under a component-wise group operation. A group code has a well-defined state space Σ_k at each time k. Each code sequence passes through a well-defined state sequence. The set of all state sequences is also a group code, the state code of C. The state code defines an essentially unique minimal realization of C. The trellis diagram of C is defined by the state code of C and by labels associated with each state transition. The set of all label sequences forms a group code, the label code of C, which is isomorphic to the state code of C. If C is complete and strongly controllable, then a minimal encoder in controller canonical (feedbackfree) form may be constructed from certain sets of shortest possible code sequences, called granules. The size of the state space Σ_k is equal to the size of the state space of this canonical encoder, which is given by a decomposition of the input groups of C at each time k. If C is time-invariant and ν-controllable, then |Σ_k|=Π_1⩽j⩽v|F_j/F _j-1|^j, where F₀ ⊆···⊆ Fν is a normal series, the input chain of C. A group code C has a well-defined trellis section corresponding to any finite interval, regardless of whether it is complete. For a linear time-invariant convolutional code over a field G, these results reduce to known results; however, they depend only on elementary group properties, not on the multiplicative structure of G. Moreover, time-invariance is not required. These results hold for arbitrary groups, and apply to block codes, lattices, time-varying convolutional codes, trellis codes, geometrically uniform codes and discrete-time linear systems     

On ternary complementary sequences

A pair of real-valued sequences A=(a₁,a₂,...,a_N) and B=(b₁,b ₂,...,b_N) is called complementary if the sum R(·) of their autocorrelation functions R_A(·) and R_B(·) satisfies R(τ)=R_A(τ)+R _B(τ)=Σ_i=1^N$ -^τa_ia_i+τ+Σ_j=1 ^N-τb_jb_j+τ=0, ∀τ≠0. In this paper we introduce a new family of complementary pairs of sequences over the alphabet α₃=+{1,-1,0}. The inclusion of zero in the alphabet, which may correspond to a pause in transmission, leads both to a better understanding of the conventional binary case, where the alphabet is α₂={+1,-1}, and to new nontrivial constructions over the ternary alphabet α₃. For every length N, we derive restrictions on the location of the zero elements and on the form of the member sequences of the pair. We also derive a bound on the minimum number of zeros necessary for the existence of a complementary pair of length N over α₃. The bound is tight, as it is met by some of the proposed constructions, for infinitely many lengths     

Erasure, list, and detection zero-error capacities for low noiseand a relation to identification

For the discrete memoryless channel (χ, y, W) we give characterizations of the zero-error erasure capacity C_er and the zero-error average list size capacity C_al in terms of limits of suitable information (respectively, divergence) quantities (Theorem 1). However, they do not “single-letterize.” Next we assume that χ⊂y and W(x|x)>0 for all x∈χ, and we associate with W the low-noise channel W_ϵ, where for y ⁺(x)={y:W(y|x)>0} W_ϵ(y|x)={1, if y=x and |y⁺(x)|=1 1-ϵ, if y=x and |y⁺(x)|>1 e/|y ⁺(x)|-1, if y≠x. Our Theorem-2 says that as ε tends to zero the capacities C_er(W_ε) and C_al (W_ε) relate to the zero-error detection capacity C _de(W). Our third result is a seemingly basic contribution to the theory of identification via channels. We introduce the (second-order) identification capacity C_oid for identification codes with zero misrejection probability and misacceptance probability tending to zero. Our Theorem 3 says that C_oid equals the zero-error erasure capacity for transmission C_er     

An inequality on guessing and its application to sequentialdecoding

Let (X,Y) be a pair of discrete random variables with X taking one of M possible values, Suppose the value of X is to be determined, given the value of Y, by asking questions of the form “Is X equal to x?” until the answer is “Yes”. Let G(x|y) denote the number of guesses in any such guessing scheme when X=x, Y=y. We prove that E[G(X|Y)^ρ]⩾(1+lnM)^-ρΣ_y [Σ_xP_X,Y(x,y)^1/1+ρ] ^1+ρ for any ρ⩾0. This provides an operational characterization of Renyi's entropy. Next we apply this inequality to the estimation of the computational complexity of sequential decoding. For this, we regard X as the input, Y as the output of a communication channel. Given Y, the sequential decoding algorithm works essentially by guessing X, one value at a time, until the guess is correct. Thus the computational complexity of sequential decoding, which is a random variable, is given by a guessing function G(X|Y) that is defined by the order in which nodes in the tree code are hypothesized by the decoder. This observation, combined with the above lower bound on moments of G(X|Y), yields lower bounds on moments of computation in sequential decoding. The present approach enables the determination of the (previously known) cutoff rate of sequential decoding in a simple manner; it also yields the (previously unknown) cutoff rate region of sequential decoding for multiaccess channels. These results hold for memoryless channels with finite input alphabets     

Wide-sense and strict-sense nonblocking operation of multicastmulti-log2 n switching networks

Multicast connections are used in broad-band switching networks as well as in parallel processing. We consider wide-sense and strict-sense nonblocking conditions for multi-log₂ N switching networks with multicast connections. We prove that such networks are wide-sense nonblocking if they are designed by vertically stacking at least t · 2^n-t-1 + 2 ^n-2t-1 planes of a log₂ N networks together, where 1 ⩽ t ⩽ [n/2] and t defines the size of a blocking window K = 2^t. For t = [n/2] and n even, and for [n/2] ⩽ t ⩽ n the number of planes must be at least t · 2^n-t-1 + 1 and 2^t + (n - t - 1) · 2^n-t-1 - 2^2t-n-1 + 1, respectively. In the case of strict-sense nonblocking switching networks, the number of planes is at least N/2. The results obtained in this paper show that in many cases number of planes in wide-sense nonblocking switching networks is less than those for t = [n/2] considered by Tscha and Lee (see ibid., vol.47, p.1425-31, Sept. 1999). The number of planes given in the paper is the minimum number of planes needed for wide-sense nonblocking operation provided that Algorithm 1 is used for setting up connections. The minimum number of planes for such operation in general is still open issue     

Combinatorial bounds for list decoding

Informally, an error-correcting code has "nice" list-decodability properties if every Hamming ball of "large" radius has a "small" number of codewords in it. We report linear codes with nontrivial list-decodability: i.e., codes of large rate that are nicely list-decodable, and codes of large distance that are not nicely list-decodable. Specifically, on the positive side, we show that there exist codes of rate R and block length n that have at most c codewords in every Hamming ball of radius H^-1(1-R-1/c)·n. This answers the main open question from the work of Elias (1957). This result also has consequences for the construction of concatenated codes of good rate that are list decodable from a large fraction of errors, improving previous results of Guruswami and Sudan (see IEEE Trans. Inform. Theory, vol.45, p.1757-67, Sept. 1999, and Proc. 32nd ACM Symp. Theory of Computing (STOC), Portland, OR, p. 181-190, May 2000) in this vein. Specifically, for every ε > 0, we present a polynomial time constructible asymptotically good family of binary codes of rate Ω(ε⁴) that can be list-decoded in polynomial time from up to a fraction (1/2-ε) of errors, using lists of size O(ε^-2). On the negative side, we show that for every δ and c, there exists τ < δ, c₁ > 0, and an infinite family of linear codes {C_i}_i such that if n_i denotes the block length of C_i, then C _i has minimum distance at least δ · n_i and contains more than c₁ · n_i^c codewords in some Hamming ball of radius τ · n_i. While this result is still far from known bounds on the list-decodability of linear codes, it is the first to bound the "radius for list-decodability by a polynomial-sized list" away from the minimum distance of the code     

The Kolmogorov complexity, universal distribution, and codingtheorem for generalized length functions

A function h(w) is said to be useful for the coding theorem if the coding theorem remains to be true when the lengths |w| of codewords w in it are replaced with h(w). For a codeword w=a₀a₁...a_m-1 of length m and an infinite sequence Q=(q₀, q₁, q₂, ...) of real numbers such that 0n⩽½, let |w|_Q denote the value Σ_n=0^m-1 (if a_n =0 then -log₂q_n, else -log₂(1-q _n)), that is, -log₂, (the probability that flippings of coins generate x) assuming that the (i+1)th coin generates a tail (or 0) with probability q_i. It is known that if 0n→∞ q_n then |w|_Q is useful for the coding theorem and if lim_n→∞ q _n/(1/(2ⁿ))=0 then |w|_Q is not useful. We introduce several variations of the coding theorem and show sufficient conditions for h(w) not to be useful for these variations. The usefulness is also defined for the expressions that define the Kolmogorov complexity and the universal distribution. We consider the relation among the usefulness for the coding theorem, that for the Kolmogorov complexity, and that for the universal distribution     

Coding theorems for Shannon's cipher system with correlated sourceoutputs, and common information

Source coding problems are treated for Shannon's (1949) cipher system with correlated source outputs (X,Y). Several cases are considered based on whether both X and Y, only X, or only Y must be transmitted to the receiver, whether both X and Y, only X, or only Y must be kept secret, or whether the security level is measured by (¹/_KH(X^K|W), (¹/_KH(Y^K|W)) or ¹/_K H(X^KY^K|W) where W is a cryptogram. The admissible region of cryptogram rate and key rate for a given security level is derived for each case. Furthermore, two new kinds of common information of X and Y, say C₁(X;Y) and C₂(X;Y), are considered. C₁(X;Y) is defined as the rate of the attainable minimum core of (X^K,Y^K) by removing each private information from (X^K,Y^K) as much as possible, while C₂(X;Y) is defined as the rate of the attainable maximum core V_C such that if one loses V_C , then each uncertainty of X^K and Y^K becomes H(V_C). It is proved that C₁(X;Y)=I(X;Y) and C₂(X;Y)=min {H(X), H(Y)}. C₁(X;Y) justifies the author's intuitive feeling that the mutual information represents a common information of X and Y     

Universal schemes for learning the best nonlinear predictor giventhe infinite past and side information

Let {X_t} be a real-valued time series. The best nonlinear predictor of X₀ given the infinite past X_-∞^-1 in the least squares sense, is equal to the conditional mean E{X₀|X_-∞^-1}. Previously, it has been shown that certain predictors based on growing segments of past observations converge to the best predictor given the infinite past whenever {X_t} is a stationary process with values in a bounded interval. The present paper deals with universal prediction schemes for stationary processes with finite mean. We also discuss universal schemes for learning the conditional mean E{X₀|X _-∞^-1Y_-∞^-1Y₀ } from past observations of a stationary pair process {(X_t , Y_t)}, and schemes for learning the repression function m(y)=E{X|Y=y} from independent samples of (X, Y)     

Fast evaluation of an integral occurring in digital filteringapplications

A fast evaluation procedure for the integral I_m,n,p=1/2πj∯_|z|=1H_m,n(z)H _m,n(z^-1)z^p-1dz for arbitrary nonnegative integer-valued m, n, and p, is presented, where H_m,n (z)=Σ_k=0^mb_m,kz^-k /Σ_l=0ⁿa_n,lz^-1,a _n,0≠0 is the transfer function of an arbitrary digital filter. Evaluation of this integral frequently appears in control, communication, and digital filtering. A notable result is the one-term recursion on p, for arbitrary but fixed nonnegative integers m and n. The computational complexity is analyzed, and two illustrative examples demonstrate some of the advantages of this approach     

Low resistance ohmic contacts to p-Ge1-xCx onSi

We report on ohmic contact measurements of Al, Au, and W metallizations to p-type epitaxial Ge_0.9983C_0.0017 grown on a (100) Si substrate by molecular beam epitaxy (MBE). Contacts were annealed at various temperatures, and values of specific contact resistance have been achieved which range from 10^-5Ω·cm² to as low as 5.6×10 ^-6Ω·cm². Theoretical calculations of the contact resistance of metals on Ge_1-xC_x with small percentages of carbon, based on the thermionic field emission mechanism of conduction, result in good agreement with the experimental data. We conclude that Al and Au are suitable ohmic contacts to p-Ge_0.9983C_0.0017 alloys     

A general combinatorial sphere decoder and its application

The conventional problem of searching the shortest vector z of a N-dimensional lattice L(H) with generating matrix HisinR^NtimesM is considered in a more general setting. There are P generating matrices H_iisinR^NtimesM(i=1,2,...,P) of the P lattices L(H_i). For a (bounded) integer vector bisinZ^M , we obtain P lattice points H_ib. Let d_i be the Euclidean norm of H_ib. The problem of interest is how to search for a vector b so that the maximum of d_i is minimized. We propose a new sphere decoder called combinatorial sphere decoder (CSD) to solve this problem. One of the applications of the new CSD is presented in detail to show its effectiveness     

A universal predictor based on pattern matching

We consider a universal predictor based on pattern matching. Given a sequence X₁, ..., X_n drawn from a stationary mixing source, it predicts the next symbol X_n+1 based on selecting a context of X_n+1. The predictor, called the sampled pattern matching (SPM), is a modification of the Ehrenfeucht-Mycielski (1992) pseudorandom generator algorithm. It predicts the value of the most frequent symbol appearing at the so-called sampled positions. These positions follow the occurrences of a fraction of the longest suffix of the original sequence that has another copy inside X₁X₂···X_n ; that is, in SPM, the context selection consists of taking certain fraction of the longest match. The study of the longest match for lossless data compression was initiated by Wyner and Ziv in their 1989 seminal paper. Here, we estimate the redundancy of the SPM universal predictor, that is, we prove that the probability the SPM predictor makes worse decisions than the optimal predictor is O(n^-ν) for some 0<ν<½ as n→∞. As a matter of fact, we show that we can predict K=O(1) symbols with the same probability of error     

On the number of memories that can be perfectly stored in a neuralnet with Hebb weights

Let {w_ij} be the weights of the connections of a neural network with n nodes, calculated from m data vectors v¹, ···, v^m in {1,-1}ⁿ, according to the Hebb rule. The author proves that if m is not too large relative to n and the v^k are random, then the w_ij constitute, with high probability, a perfect representation of the v^k in the sense that the v ^k are completely determined by the w_ij up to their sign. The conditions under which this is established turn out to be less restrictive than those under which it has been shown that the v^k can actually be recovered by letting the network evolve until equilibrium is attained. In the specific case where the entries of the v^k are independent and equal to 1 or -1 with probability 1/2, the condition on m is that m should not exceed n/0.7 log n     

The Zak transform and some counterexamples in time-frequencyanalysis

It is shown how the Zak transform can be used to find nontrivial examples of functions f, g∈L²(R) with f×g≡0≡F×G, where F, G are the Fourier transforms of f, g, respectively. This is then used to exhibit a nontrivial pair of functions h, k∈L²(R), h≠k, such that |h|=|k|, |H |=|K|. A similar construction is used to find an abundance of nontrivial pairs of functions h, k∈L² (R), h≠k, with |A_h |=|A_k| or with |W_h|=|W _k| where A_h, A_k and W_h, W_k are the ambiguity functions and Wigner distributions of h, k, respectively. One of the examples of a pair of h, k∈L²(R), h≠k , with |A_h|=|A_k| is F.A. Grunbaum's (1981) example. In addition, nontrivial examples of functions g and signals f₁≠f₂ such that f₁ and f₂ have the same spectrogram when using g as window have been found     

On the number of points on shells for shiftedZ4n lattices

A conjecture is proven on the number of points on shells for the shifted Z⁴ and the shifted Z⁸ lattices. Furthermore, the results are extended to any shifted Z⁴ⁿ lattice (n=0, 1, . . .). These results provide an easy way to compute the number of points on shells for the type of lattices used in the design of multidimensional signal sets or in vector coding     

Strongly consistent online forecasting of centered Gaussianprocesses

An estimator Eˆ(d_n,n) of the conditional expectation E[X_n+1|X_n,...,X(n-d_n+1)] in a centered, stationary, and ergodic Gaussian process {X_i}_i with absolutely summable Wold coefficients is constructed on the basis of having observed X₁,...,X_n . For a suitable choice of the length dn→∞ (n→∞) of the past covered by the conditional expectation, it is established that |Eˆ(d_n,n)-E[X_n+1|X_n ,...,X(n-d_n+1)]|→0 with probability 1. In addition, sufficient conditions for |E[X_n+1|X_n,X _n-1,...]-E[X_n+1|X_n,...,X(n-d_n +1)]| →0 to hold with probability 1 are given, that is, conditions under which Eˆ(d_n,n) can be used as a strongly consistent forecaster for |E[X_n+1|X_n,X _n-1,...]