An entropy theorem for computing the capacity of weakly(d,k)-constrained sequences

We find an analytic expression for the maximum of the normalized entropy -Σ_iϵTp_iln p_i/Σ_iϵTip_i where the set T is the disjoint union of sets S_n of positive integers that are assigned probabilities P_n, Σ_nP_n =1. This result is applied to the computation of the capacity of weakly (d,k)-constrained sequences that are allowed to violate the (d,k)-constraint with small probability     

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     

Source Coding for Quasiarithmetic Penalties

Whereas Huffman coding finds a prefix code minimizing mean codeword length for a given finite-item probability distribution, quasiarithmetic or quasilinear coding problems have the goal of minimizing a generalized mean of the form rho^-1(Sigma_ip_irho(l_i )), where l_i denotes the length of the ith codeword, p _i denotes the corresponding probability, and rho is a monotonically increasing cost function. Such problems, proposed by Campbell, have a number of diverse applications. Several cost functions are shown here to yield quasiarithmetic problems with simple redundancy bounds in terms of a generalized entropy. A related property, also shown here, involves the existence of optimal codes: For "well-behaved" cost functions, optimal codes always exist for (possibly infinite-alphabet) sources having finite generalized entropy. An algorithm is introduced for finding binary codes optimal for convex cost functions. This algorithm, which can be extended to other minimization utilities, can be performed using quadratic time and linear space. This reduces the computational complexity of a problem involving minimum delay in a queue, allows combinations of previously considered problems to be optimized, and greatly expands the set of problems solvable in quadratic time and linear space     

Bounds on the information rate of intertransition-time-restrictedbinary signaling over an AWGN channel

Upper and lower bounds on the capacity of a continuous-time additive white Gaussian noise (AWGN) channel with bilevel (±√P) input signals subjected to a minimum inter-transition time (T_min) constraint are derived. The channel model and input constraints reflect basic features of certain magnetic recording systems. The upper bounds are based on Duncan's relation between the average mutual information in an AWGN regime and the mean-square error (MSE) of an optimal causal estimator. Evaluation or upper-bounding the MSE of suboptimal causal estimators yields the desired upper bounds. The lower bound is found by invoking the extended “Mrs. Gerber's” lemma and asymptotic properties of the entropy of max-entropic bipolar (d, k) codes. Asymptotic results indicate that at low SNR=PT_min/N₀, with N₀ designating the noise one-sided power spectral density, the capacity tends to P/N ₀ nats per second (nats/s), i.e., it equals the capacity in the simplest average power limited case. At high SNR, the capacity in the simplest average power limited case. At high SNR, the capacity behaves asymptotically as T_min^-1ln(SNR/ln(SNR)) (nats/s), demonstrating the degradation relatively to T_avg ^-1 lnSNR, which is the asymptotic known behavior of the capacity with a bilevel average intertransition-time (T_avg) restricted channel input. Additional lower bounds are obtained by considering specific signaling formats such as pulsewidth modulation. The effect of mild channel filtering on the lower bounds on capacity is also addressed, and novel techniques to lower-bound the capacity in this case are introduced     

The effect of bandwidth allocation policies on delay inunidirectional bus networks

We consider the problem of allocating bandwidth fairly to each node in a shared, unidirectional bus network. We focus on the p_i persistent protocol, since these are open loop policies designed to operate well in high speed networks, which have a very large bandwidth-delay product and feedback in the upstream direction is not available in a timely manner. First, we introduce an improvement to the basic p_i persistent protocol, in which we replace random coin tosses with a deterministic counting algorithm, and thereby reduce the delays for all nodes for any given choice of {p_i}. We then describe an exact method for calculating average packet delays and queue lengths in both the p_i persistent and our new deterministic n out of m protocols, based on the regenerative approach of Georgiades et al. (1987). These delay results, together with simulation measurements, show that both of these protocols still waste some bandwidth. After presenting a lower bounding argument to show that some wasted bandwidth is inevitable in all such distributed access control schemes, assuming a passive bus without feedback in the upstream direction, we show that changing the bus to unidirectional point-to-point links between (very simple) active interfaces at each node allows us to construct distributed access schemes that require no upstream feedback and are both work conserving and fair. To illustrate how this can be done, we introduce the p_i preemptive protocol, in which each node randomly inserts its own packets into the traffic arriving from upstream. We derive a simple and effective heuristic for calculating the preemption probability for each node, and use simulation to show how well it equalizes the delays at each node     

Optimal quaternary linear codes of dimension five

Let d_q(n,k) be the maximum possible minimum Hamming distance of a q-ary [n,k,d]-code for given values of n and k. It is proved that d₄ (33,5)=22, d₄(49,5)=34, d₄ (131,5)=96, d₄(142,5)=104, d₄(147,5)=108, d ₄(152,5)=112, d₄(158,5)=116, d₄(176,5)⩾129, d₄(180,5)⩾132, d₄(190,5)⩾140, d₄(195,5)=144, d₄(200,5)=148, d₄(205,5)=152, d₄(216,5)=160, d₄(227,5)=168, d₄(232,5)=172, d₄(237,5)=176, d₄(240,5)=178, d₄(242,5)=180, and d₄(247,5)=184. A survey of the results of recent work on bounds for quaternary linear codes in dimensions four and five is made and a table with lower and upper bounds for d₄(n,5) is presented     

New bounds on the expected length of one-to-one codes

We provide new bounds on the expected length L of a binary one-to-one code for a discrete random variable X with entropy H. We prove that L⩾H-log(H+1)-Hlog(1+1/H). This bound improves on previous results. Furthermore, we provide upper bounds on the expected length of the best code as function of H and the most likely source letter probability     

The first-order asymptotic of waiting times with distortion betweenstationary processes

Let X and Y be two independent stationary processes on general metric spaces, with distributions P and Q, respectively. The first-order asymptotic of the waiting time W_n(D) between X and Y, allowing distortion, is established in the presence of one-sided ψ-mixing conditions for Y. With probability one, n^-1log W _n(D) has the same limit as -n^-1logQ(B(X₁ⁿ, D)), where Q(B(X₁ ⁿ, D)) is the Q-measure of the D-ball around (X₁ ,...,X_n), with respect to a given distortion measure. Large deviations techniques are used to get the convergence of -n^-1 log Q(B(X₁ⁿ, D)). First, a sequence of functions R_n in terms of the marginal distributions of X₁ⁿ and Y₁ⁿ as well as D are constructed and demonstrated to converge to a function R(P, Q, D). The functions R_n and R(P, Q, D) are different from rate distortion functions. Then -n^-1logQ(B(X₁ⁿ , D)) is shown to converge to R(P, Q, D) with probability one     

Capacity of the Class of MIMO Channels With Incomplete CDI—Properties of Mutual Information for a Class of Channels

This paper is concerned with multiple-input multiple-output (MIMO) wireless channel capacity, when the probability distribution of the channel matrix p(H) is not completely known to the transmitter and the receiver. The partial knowledge of a true probability distribution of the channel matrix p(H) is modelled by a relative entropy D(middot||middot) such that D(p||p_nom) les d, d ges 0, where d is the distance from the so-called nominal channel matrix distribution p_nom(H). The capacity of this compound channel is equal to the maximin of the mutual information, where the minimum is with respect to the channel matrix distribution, and the maximum is with respect to the covariance matrix of a transmitted signal. The existence of a minimizing probability distribution is proved, and the explicit formula for the minimizing distribution is derived in terms of the nominal distribution p_nom(H) and parameter d. A number of properties of the mutual information, minimized over the set of channel distributions, are derived. Specifically, upper and lower bounds are derived for the minimized mutual information, while its convexity with respect to d is shown. In the case of the Rayleigh fading, an explicit formula for the capacity and the optimal transmit covariance matrix are derived.     

On coding without restrictions for the AWGN channel

Many coded modulation constructions, such as lattice codes, are visualized as restricted subsets of an infinite constellation (IC) of points in the n-dimensional Euclidean space. The author regards an IC as a code without restrictions employed for the AWGN channel. For an IC the concept of coding rate is meaningless and the author uses, instead of coding rate, the normalized logarithmic density (NLD). The maximum value C_∞ such that, for any NLD less than C_∞, it is possible to construct an PC with arbitrarily small decoding error probability, is called the generalized capacity of the AWGN channel without restrictions. The author derives exponential upper and lower bounds for the decoding error probability of an IC, expressed in terms of the NLD. The upper bound is obtained by means of a random coding method and it is very similar to the usual random coding bound for the AWGN channel. The exponents of these upper and lower bounds coincide for high values of the NLD, thereby enabling derivation of the generalized capacity of the AWGN channel without restrictions. It is also shown that the exponent of the random coding bound can be attained by linear ICs (lattices), implying that lattices play the same role with respect to the AWGN channel as linear-codes do with respect to a discrete symmetric channel     

A binary analog to the entropy-power inequality

Let {X_n}, {Y_n} be independent stationary binary random sequences with entropy H( X), H(Y), respectively. Let h(ζ)=-ζlogζ-(1-ζ)log(1-ζ), 0⩽ζ⩽1/2, be the binary entropy function and let σ(X)=h^-1 (H(X)), σ(Y)=h^-1 (H(Y)). Let z_n=X_n⊕Y_n , where ⊕ denotes modulo-2 addition. The following analog of the entropy-power inequality provides a lower bound on H(Z ), the entropy of {Z_n}: σ(Z)⩾σ(X)*σ(Y), where σ(Z)=h^-1 (H(Z)), and α*β=α(1-β)+β(1-α). When {Y _n} are independent identically distributed, this reduces to Mrs. Gerber's Lemma from A.D. Wyner and J. Ziv (1973)     

Improved tangential sphere bound on the bit-error probability ofconcatenated codes

The tangential sphere bound (TSB) of Poltyrev (1994) is a tight upper bound on the word error probability P_w of linear codes with maximum likelihood decoding and is based on the code's distance spectrum. An extension of the TSB to a bound on the bit-error probability P_b is given by Sason/Shitz (see IEEE Trans. Inform. Theory, vol.46, p.24-47, 2000). We improve the tangential sphere bound on P_b and apply the new method to some examples. Our comparison to other bounds as well as to simulation results shows an improved tightness, particularly for signal-to-noise ratios below the value corresponding to the computational cutoff rate R_o     

Entropy inequalities for discrete channels

The sharp lower boundf(x)on the per-symbol output entropy for a given per-symbol input entropyxis determined for stationary discrete memoryless channels; it is the lower convex envelope of the boundg(x)for a single channel use. The bounds agree for all noiseless channels and all binary channels. However, for nonbinary channels,gis not generally convex so that the bounds differ. Such is the case for the Hamming channels that generalize the binary symmetric channels. The bounds are of interest in connection with multiple-user communication, as exemplified by Wyner's applications of "Mrs. Gerber's lemma" (the bound for binary symmetric channels first obtained by Wyner and Ziv). These applications extend from the binary symmetric case to the. Hamming case. Doubly stochastic channels are characterized by the property of never decreasing entropy.     

Bounds on the entropy series

Upper bounds on the entropy of a countable integer-valued random variable are furnished in terms of the expectation of the logarithm function. In particular, an upper bound is derived that is sharper than that of P. Elias (ibid., vol.IT-21, no.2, p.194-203, 1975), for all values of E_p(log). Bounds that are better only for large values of E_p than the previous known upper bounds are also provided     

Comment. Remarks on the LUC public key system

The authors of [Remarks on the LUC public key system, see ibid., vol. 30, p. 123, 1994] consider the Lucas function on which the public cryptosystem LUC proposed by Smith and Lennon [1993] is based. For a finite field G with m∈G, the Lucas function V_n(m) is defined by the second order linear recurrence relation V_n(m)=mV_n-1(m)-V_n-2(m) where V_o (m)=2, V₁(m)=m. The characteristic polynomial f of the Lucas function is f(x)=x²-mx+1, and V_x(m)=α ^x+α^-x where α is a root of f. We now consider some of the results of and give concise proofs     

On universal hypotheses testing via large deviations

A prototype problem in hypotheses testing is discussed. The problem of deciding whether an i.i.d. sequence of random variables has originated from a known source P₁ or an unknown source P₂ is considered. The exponential rate of decrease in type II probability of error under a constraint on the minimal rate of decrease in type I probability of error is chosen for a criterion of optimality. Using large deviations estimates, a decision rule that is based on the relative entropy of the empirical measure with respect to P₁ is proposed. In the case of discrete random variables, this approach yields weaker results than the combinatorial approach used by Hoeffding (1965). However, it enables the analysis to be extended to the general case of Rⁿ-valued random variables. Finally, the results are extended to the case where P₁ is an unknown parameter-dependent distribution that is known to belong to a set of distributions (P⁰₁, &thetas;∈Θ)     

Near-optimal depth-constrained codes

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

Renyi's divergence and entropy rates for finite alphabet Markovsources

In this work, we examine the existence and the computation of the Renyi divergence rate, lim_n→∞ 1/n D_α (p⁽ⁿ⁾∥q⁽ⁿ⁾), between two time-invariant finite-alphabet Markov sources of arbitrary order and arbitrary initial distributions described by the probability distributions p⁽ⁿ⁾ and q⁽ⁿ⁾, respectively. This yields a generalization of a result of Nemetz (1974) where he assumed that the initial probabilities under p⁽ⁿ⁾ and q⁽ⁿ⁾ are strictly positive. The main tools used to obtain the Renyi divergence rate are the theory of nonnegative matrices and Perron-Frobenius theory. We also provide numerical examples and investigate the limits of the Renyi divergence rate as α→1 and as α↓0. Similarly, we provide a formula for the Renyi entropy rate lim_n→∞ 1/n H _α(p⁽ⁿ⁾) of Markov sources and examine its limits as α→1 and as α↓0. Finally, we briefly provide an application to source coding     

Computation in faulty stars [hypercube networks]

The question of simulating a completely healthy hypercube with a degraded one (one with some faulty processors) has been considered by several authors. We consider the question for the star-graph interconnection network. With suitable assumptions on the fault probability, there is, with high probability, a bounded distance embedding of K_n×S_n-1 in a degraded S_n , of congestion O(n). By a different method, a congestion O(log(n)) embedding of S, can be obtained. For the hypercube O(1) congestion has been obtained, but this is open for the star graph. Other results presented include a guaranteed O(n) slowdown simulation if there are sufficiently few faults, and upper and lower bounds for the minimal size of a system of faults rendering faulty every m-substar