Tight bounds on the redundancy of Huffman codes

A method for deriving optimal upper bounds on the redundancy of binary Huffman codes in terms of the probability p₁ of the most likely source letter is presented. This method will be used to compute bounds for all p₁⩾1/127, which were previously known only for a few special cases. Furthermore, the known optimal lower bound for binary Huffman codes is generalized to arbitrary code alphabets and some upper bounds for D-ary Huffman codes, 2⩽D<∞, are given, which are the tightest possible for all p₁⩾1/2     

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     

Optimal probability-of-error thresholds and performance for twoversions of the sign detector

Expressions are obtained for specifying the optimal error probability (minimum P_e) thresholds λ₀₁ and λ₀₂ for the traditional and modified sign detectors, respectively. These thresholds are shown to depend on the parameters p, P₁, and M where: M is the number of observations z_i used in the test statistic; P₁=P(H₁ ) is the prior probability for hypothesis H₁ that signal s₁ is present and 1-P₁ =P(H₀) corresponds to the hypothesis H₀ that signal s₀ is present; and p=Pr{z_i⩾0|H₁} with s₀=0 for the traditional sign detector and p=Pr{z_i⩾λ|H₁ }=Pr{z_i<λ|H₀} with λ =(s₀+s₁)/2 for the modified sign detector. The expressions for λ₀₁ and λ₀₂, are given explicitly, and shown to be independent of P₁ for sufficiently large M. Optimal P_e versus M performance curves, corresponding to both versions of the sign detector, are obtained for a representative range of values for p and P₁     

Determination of the merit factor of Legendre sequences

M.J.E. Golay (ibid., vol.IT-23, no.1, p.43-51, 1977) has used the ergodicity postulate to calculate that the merit factor F of a Legendre sequence offset by a fraction f of its length has an asymptotic value given by 1/F=(2/3)-4|f|+8f ², |f|⩽1/2, which gives F=6 for |f |=1/4. Here this is proved without using the ergodicity postulate     

Lower bounds for binary covering codes

G.D. Chen et al. (ibid., vol.IT-32, p.680-94, 1986) presented two new lower bounds for K(n,R), where K(n,R) denotes the minimum cardinality of a binary code of length n and covering radius R. The author shows that a slight modification gives further improvements and some examples are given to confirm the argument. Codes that have a certain partitioning property are considered     

Reply to comments on Wait's `In defense of J.A. Stratton'

The author points out that M.G.M. Hussain (ibid., vol.31, no.3, p.202, May 1989), in his comments on the author's paper (ibid., vol.30, no.4, p.590, Nov. 1988) says that equation (4) is not valid at y=0. He notes that he stated that y>0. Even if the source were a current sheet in the plane y=0, it would still be possible to alloy y to approach zero from positive values     

A note on D-ary Huffman codes

An upper bound on the redundancy of D-ary Huffman codes in terms of the probability p₁ of the most likely source letter is provided. For large values of p₁, the bound improves the one given by R.G. Gallager (1978). Additionally, some results known for the binary case (D=2) are extended to arbitrary D-ary Huffman codes. As a consequence, a tight lower bound that corrects a bound recently proposed by J.D. Golic and M.M. Obradovic (1987) is derived     

Simple proof of the concavity of the entropy power with respect toadded Gaussian noise

A very simple proof of M.H. Costa's result (see ibid., vol.IT-31, p.751-60, 1985) that the entropy power of X_t=X +N(O,tI) is concave in t, is derived as an immediate consequence of an inequality concerning Fisher information. This relationship between Fisher information and entropy is found to be useful for proving the central limit theorem. Thus, one who seeks new entropy inequalities should try first to find new equalities about Fisher information, or at least to exploit the existing ones in new ways     

Limiting efficiencies of burst-correcting array codes

The author evaluates the limiting efficiencies e(-S ) of burst-correcting array codes A(n₁,n₂, -s) for all negative readouts -s as n₂ tends to infinity and n₁ is properly chosen to maximize the efficiency. Specializing the result to the products of the first i primes donated by s_i (1⩽i<∞), which are optimal choices for readouts, gives the expression e(-s_i)=(2p_i+1 -2)/(2p_i+1-1) where p_i+1 is the next prime. Previously, it was known only that e(-2)⩾4/5 and e(-1)⩾2/3. This result reveals the existence of burst-correcting array codes with efficiencies arbitrarily close to 1 and with rates also arbitrarily close to 1     

Optimization of signal sets for partial-response channels. II.Asymptotic coding gain

For Pt. I see ibid., vol.37, no.5, p.1327-141 (1991). For a linear, time-invariant, discrete-time channel with a given transfer function H(f), and information rate R bits/ T, where T is the symbol interval, an optimal signal set of length K is defined to be a set of 2^RK inputs of length K that maximizes the minimum l₂ distance between pairs of outputs. The author studies the minimum distance between outputs, or equivalently, the coding gain of optimal signal sets as K→∞. He shows how to estimate the coding gain, relative to single-step detection, of an optimal signal set length K when K is large     

An explicit solution for the number of minimalp-cutsequences in a consecutive-k-out of-n:Fsystem

R.C. Bollinger and A.A. Salvia (see ibid., vol. R-34, p. 43-5, Apr. 1985) proposed an approach to study the failure-time distribution of a consecutive-k-out-of-n:F system by studying the number of minimal p-cutsequences. They gave recursive equations to compute this number for independent identically distributed components. It is shown that the recursive equations have an explicit solution     

Frequency-locking of a 1.3 μm DFB laser using a miniature argonglow lamp

The frequency of an InGaAsP distributed-feedback (DFB) laser was locked to the 2p₁₀-3d₅ transition of argon atoms at 1.2960 μm using the optogalvanic signal obtained from a commercial miniature glow lamp. At a discharge current of 500 μA, the signal-to-noise ratio of the optogalvanic signal corresponding to the Ar transition was about 18 dB. The peak-to-peak width of the first derivative signal was 650 MHz. The slope of the signal was 0.32 μV/MHz near the center of the transition. By using the linear portion of the first-derivative signal, the laser frequency was locked to the Ar 2p₁₀-3d₅ transition. The peak-to-peak frequency fluctuations in the free-running condition were estimated to be 650 MHz, which is mainly due to laser temperature fluctuations. When the servo-loop was closed, the frequency stability was improved to better than 13 MHz     

Repeated convolutional codes for high-error-rate channels

An error-correction scheme for an M-ary symmetric channel (MSC) characterized by a large error probability p_e is considered. The value of p_e can be near, but smaller than, 1-1/M, for which the channel capacity is zero, such as may occur in a jamming environment. The coding scheme consists of an outer convolutional code and an inner repetition code of length m that is used for each convolutional code symbol. At the receiving end, the m inner code symbols are used to form a soft-decision metric, which is passed to a soft-decision decoder for the convolutional code. The effect of finite quantization and methods to generate binary metrics for M>2 are investigated. Monte Carlo simulation results are presented. For the binary symmetric channel (BSC), it is shown that the overall code rate is larger than 0.6R₀, where R₀ is the cutoff rate of the channel. New union bounds on the bit error probability for systems with a binary convolutional code on 4-ary and 8-ary orthogonal channels are presented. For a BSC and a large m, a method is presented for BER approximation based on the central limit theorem     

A generalized two-threshold detection procedure

A modified sequential procedure for testing binary hypotheses with different means, proposed by C.C. Lee and J.B. Thomas (ibid., vol.IT-30, no.1, p.16-23, Jan. 1984), is generalized for application to the case of multiple hypotheses with different means/variances of the Gaussian distribution. The method constitutes a two-threshold test for fixed-size packages of samples with a sequential procedure of discarding the package for which no decision is reached and subsequently testing a new package. The objective is to find an optimum package size N₀ which leads to the minimum overall average sample number (ASN) for a given overall error probability. An optimization algorithm is developed to extend the application of the Lee-Thomas procedure to the M-ary case. Performance characteristics of the generalized two-threshold (GTT) test procedure are compared with those of conventional sequential as well as fixed-sample-size (FSS) methods. It is shown for the M-ary different means/variances cases that for low error rates the number of samples required by the GTT test is, on the average, approximately half that needed by a FSS test. However, it is somewhat more than the ASN obtained with a conventional sequential test. With decreasing error probabilities the GTT test performance approaches that of conventional sequential methods     

Optical orthogonal codes-new bounds and an optimal construction

A technique for constructing optimal OOCs (optical orthogonal codes) is presented. It provides the only known family of optimal (with respect to family size) OOCs having λ=2. The parameters (n ,ω,λ) are respectively (p^2m-1, p^m+1,2), where p is any prime and the family size is p^m-2. Three distinct upper bounds on the size of an OOC are presented that, for many values of the parameter set (n,ω,λ), improve upon the tightest previously known bound     

On the design of maximally sparse beamforming arrays

The problem of designing nonuniformly spaced arrays is formulated as one of constrained optimization in which the cost function is chosen to select the array with the minimum number of elements. The response of the array is controlled by a set of inequality point response constraints. It is shown that a suitable cost function for this problem is the l_p quasi-norm for 0<p<1 and that there exists a number p₁ such that for all 0<p<p₁ the resulting array is maximally sparse. Furthermore it is shown that a solution to the problem lies at an extreme point of the simplex formed by the point constraints. A simplex search algorithm is described which will converge to a local minimum of the cost function on this simplex. The algorithm is applied to the design of sparse linear and planar arrays     

Upper bounds on capacity for a constrained Gaussian channel

A low-pass and a bandpass additive white Gaussian noise channel with a peak-power constraint imposed on otherwise arbitrary input signals are considered. Upper bounds on the capacity of such channels are derived. They are strictly less than the capacity of the channel when the peak-power constrain is removed and replaced by the average-power constraint, for which the Gaussian inputs are optimum. This provides the answer to an often-posed question: peak-power limiting in the case of bandlimited channels does reduce capacity, whereas in infinite bandwidth channels it does not, as is well known. For an ideal low-pass filter of bandwidth B, the upper bound is Blog 0.934P/(N₀B) for P/( N₀B)≫1, where P is the peak power of the input signal and N₀/2 is the double-sided power spectral density of the additive white Gaussian noise     

Limited search trellis decoding of convolutional codes

The least storage and node computation required by a breadth-first tree or trellis decoder that corrects t errors over the binary symmetric channels is calculated. Breadth-first decoders work with code paths of the same length, without backtracking. The Viterbi algorithm is an exhaustive trellis decoder of this type; other schemes look at a subset of the tree or trellis paths. For random tree codes, theorems about the asymptotic number of paths required and their depth are proved. For concrete convolutional codes, the worst case storage for t error sequences is measured. In both cases the optimal decoder storage has the same simple dependence on t. The M algorithm and algorithms proposed by G.J. Foschini (ibid., vol.IT-23, p.605-9, Sept. 1977) and by S.J. Simmons (PhD. diss., Queens Univ., Kingston, Ont., Canada) are optimal, or nearly so; they are all far more efficient than the Viterbi algorithm     

Focused codes for channels with skewed errors

Consider a channel with inputs and outputs in the field F _q(q>2). It is said that the channel is skewed on a set B⊂F_q* if the additive noise generated by the channel is likely to lie in B, i.e. B is a set of common errors. The concern is the construction of focused codes that are appropriate for such channels. It is said that a code is (t₁,t₂)-focused on B if it can correct up to t₁+t₂ errors provided at most t₁ of those errors lie outside of B; the strategy is to offer different levels of protection against common and uncommon errors and so provide novel tradeoffs between performance and rate. Techniques for constructing focused codes and bounds on their rates are described     

The entropy theorem via coding bounds

The entropy theorem (also known as the Shannon-McMillan-Breiman theory or the asymptotic equipartition theorem) asserts that, for a stationary ergodic finite alphabet process, the sequence-(1/n)log p(x₁ⁿ) converges almost surely to the entropy-rate H of the process. The entropy theorem has been used to establish asymptotic bounds on the performance of noiseless codes. Here, the coding theorems are established without using the entropy theorem, and the coding theorems are then used to prove the entropy theorem. The principle feature is the direct use of coding ideas to obtain the entropy theorem