Stopping Set Analysis of Iterative Row-Column Decoding of Product Codes

In this paper, we introduce stopping sets for iterative row-column decoding of product codes using optimal constituent decoders. When transmitting over the binary erasure channel (BEC), iterative row-column decoding of product codes using optimal constituent decoders will either be successful, or stop in the unique maximum-size stopping set that is contained in the (initial) set of erased positions. Let C_p denote the product code of two binary linear codes C_c and C_r of minimum distances dc and d_r and second generalized Hamming weights d₂(C_c) and d₂(C_r), respectively. We show that the size s_min of the smallest noncode- word stopping set is at least mm(d_rd₂(C_c),d_cd₂(C_r)) > d_rd_c, where the inequality follows from the Griesmer bound. If there are no codewords in C_p with support set S, where S is a stopping set, then S is said to be a noncodeword stopping set. An immediate consequence is that the erasure probability after iterative row-column decoding using optimal constituent decoders of (finite-length) product codes on the BEC, approaches the erasure probability after maximum-likelihood decoding as the channel erasure probability decreases. We also give an explicit formula for the number of noncodeword stopping sets of size s_min, which depends only on the first nonzero coefficient of the constituent (row and column) first and second support weight enumerators, for the case when d₂(C_r) < 2d_r and d₂(C_c) < 2d_c. Finally, as an example, we apply the derived results to the product of two (extended) Hamming codes and two Golay codes.     

Weight hierarchies of extremal non-chain binary codes of dimension4

The weight hierarchy of a linear [n,k;q] code C over GF(q) is the sequence (d₁,d₂,···,d_k ) where d_r is the smallest support of an r-dimensional subcode of C. An [n,k;q] code is extremal nonchain if, for any r and s, where 1⩽rS(D)=d_r, and w_S (E)=d_s. The possible weight hierarchies of such binary codes of dimension 4 are determined     

On the weight hierarchy of Preparata codes over Z4

Hammons et al. (see ibid., vol.40, p.301-19, 1994) showed that, when properly defined, the binary nonlinear Preparata code can be considered as the Gray map of a linear code over Z₄, the so called Preparata code over Z₄. We consider the rth generalized Hamming weight d_r(m) of the Preparata code of length 2^m over Z₄. For any m⩾3, d_r(m) is exactly determined for r=0.5, 1, 1.5, 2, 2.5 and 3.0. For a composite m, we give an upper bound on d_r(m) using the lifting technique. For m=3, 4, 5, 6 and 8, the weight hierarchy is completely determined. In the case of m=7, the weight hierarchy is completely determined except for d₄(7)     

Further results on generalized Hamming weights for Goethals andPreparata codes over Z4

This article contains results on the generalized Hamming weights (GHW) for the Goethals and Preparata codes over Z₄. We give an upper bound on the rth generalized Hamming weights d_r(m,j) for the Goethals code G_m(j) of length 2^m over Z ₄, when m is odd. We also determine d_3.5(m,j) exactly. The upper bound is shown to be tight up to r=3.5. Furthermore, we determine the rth generalized Hamming weight d_r(m) for the Preparata code of length 2^m over Z₄ when r=3.5 and r=4     

VI-2 class of Hamming weight of -aryq linear codes with dimension 5

The Hamming weight hierarchy of a linear [n,k;q] code c over GF(q)is the sequence(d₁,d₂,…,d_k),where d_r is the smallest support weight of an r-dimensional subcode of c.According to some new necessary conditions,the VI class Hamming weight hierarchies of q -ary linear codes of dimension 5 can be divided into six subclasses. By using the finite projective geometry method, VI-2 subclass and determine were researched almost all weight hierarchies of the VI-2 subclass of weight hierarchies of q -ary linear codes with dimension 5.     

On the second generalized Hamming weight of the dual code of adouble-error-correcting binary BCH code

The generalized Hamming weight of a linear code is a new notion of higher dimensional Hamming weights. Let C be an [n,k] linear code and D be a subcode. The support of D is the cardinality of the set of not-always-zero bit positions of D. The rth generalized Hamming weight of C, denoted by d_r(C), is defined as the minimum support of an r-dimensional subcode of C. It was shown by Wei (1991) that the generalized Hamming weight hierarchy of a linear code completely characterizes the performance of the code on the type II wire-tap channel defined by Ozarow and Wyner (1984). In the present paper the second generalized Hamming weight of the dual code of a double-error-correcting BCH code is derived and the authors prove that except for m=4, the second generalized Hamming weight of [2^m-1, 2m]-dual BCH codes achieves the Griesmer bound     

Improved coding techniques for preceded partial-response channels

A coset of a convolutional code may be used to generate a zero-run length limited trellis code for a 1-D partial-response channel. The free squared Euclidean distance, d_free², at the channel output is lower bounded by the free Hamming distance of the convolutional code. The lower bound suggests the use of a convolutional code with maximal free Hamming distance, d_max(R,N), for given rate R and number of decoder states N. In this paper we present cosets of convolutional codes that generate trellis codes with d_free ²>d_max(R,N) for rates 1/5⩽R⩽7/9 and (d _free²=d_max(R,N) for R=13/16,29/32,61/64, The tabulated convolutional codes with R⩽7/9 were not optimized for Hamming distance. Instead, a computer search was used to determine cosets of convolutional codes that exploit the memory of the 1-D channel to increase d_free² at the channel output. The search was limited by only considering cosets with certain structural properties. The R⩾13/16 codes were obtained using a new construction technique for convolutional codes with free Hamming distance 4. Newly developed bounds on the maximum zero-run lengths of cosets were used to ensure a short maximum run length at the 1-D channel output     

New converses in the theory of identification via channels

New converses for identification via arbitrary single-user and multiple-access channels, with finite first- and second-type probabilities of error, are developed. For the arbitrary single-user channel, it is shown that (λ₁, λ₂)-identification capacity is upper-bounded by λ-capacity, and optimistic (λ₁,λ₂ )-identification capacity is upper-bounded by optimistic λ-capacity, for any λ>λ₁+λ₂. The bounds become tight at the limit of the vanishing probabilities of error, thus generalizing previous results by Han and Verdu (1992), who showed that the identification capacity is equal to transmission capacity for channels satisfying the strong converse of the channel coding theorem. A by-product of the new identification converses is a general formula for optimistic λ-capacity. An outer bound on the (λ₁, λ₂)-identification capacity region of an arbitrary multiple-access channel is developed. A consequence of this bound is that the identification capacity region is equal to the transmission capacity region for any stationary, finite-memory multiple-access channel. The key tool in proving these bounds is the partial resolvability of a channel, a new notion in resolvability theory, which deals with approximation of the output statistics on a suitably chosen part of the output alphabet. This notion of approximation enables us to get sharp bounds on identification for arbitrary channels, and to extend these bounds to the multiple-access channel     

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     

Bounds for codes over the unit circle

LetCbe a code of lengthnand rateRover the alphabetA(Q)={ exp (2pi ir/Q): r=O,1, cdots ,Q-1}, and letd(C)be the minimum Euclidean distance ofC. For largen, the lower and upper bounds are obtained in parametric form on the achievable pairs(R, delta), wheredelta = d^{2}(C)/nholds. To obtain these bounds, the arguments leading to the Gilbert bound and the Elias bound, respectively, are applied to the alphabetA(Q). ForQ rightarrow infty, they are shown to be expressible in terms of the modified Bessel function of the first kind. The Elias type bound is compared with the Kabatyanskii-Levenshtein (K-L) bound that holds for less restrictive alphabets. It turns out that our upper bound improves the K-L bound fordelta leq 0.93.     

Information rates for a discrete-time Gaussian channel withintersymbol interference and stationary inputs

Bounds are presented on I_i.i.d.-the achievable information rate for a discrete Gaussian Channel with intersymbol interference (ISI) present and i.i.d. channel input symbols governed by an arbitrary predetermined distribution p_x(x). The lower and upper bounds on I _i.i.d. and I are formulated. The bounds on I_i.i.d. are calculated for independent equiprobably binary channel symbols and for causal channels with ISI memory of degree one and two. The bounds on I_i.i.d. are compared to the approximated (by Monte Carlo methods) known value of I_i.i.d. and their tightness is considered. An application of the new lower bound on I_i.i.d. yields an improvement on previously reported lower bounds for the capacity of the continuous-time strictly bandlimited (or bandpass) Gaussian channel with either peak or simultaneously peak power and bandlimiting constraints imposed on the channel's input waveform     

Further results on the covering radius of codes

A number of upper and lower bounds are obtained forK(n, R), the minimal number of codewords in any binary code of lengthnand covering radiusR. Several new constructions are used to derive the upper bounds, including an amalgamated direct sum construction for nonlinear codes. This construction works best when applied to normal codes, and we give some new and stronger conditions which imply that a linear code is normal. An upper bound is given for the density of a covering code over any alphabet, and it is shown thatK(n + 2, R + 1) leq K(n, R)holds for sufficiently largen.     

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     

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 Nehari shuffle: FIR(q) filter design with guaranteederror bounds

An approach to the problem of designing a finite impulse response filter of specified length q which approximates in uniform frequency (L_∞) norm a given desired (possibly infinite impulse response) causal, stable filter transfer function is presented. An algorithm-independent lower bound on the achievable approximation error is derived, and an approximation method that involves the solution of a fixed number of all-pass (Nehari) extension problems (and is therefore called the Nehari shuffle) is presented. Upper and lower bounds on the approximation error are derived for the algorithm. Examples indicate that the method closely approaches the derived global lower bound. The method is compared with the Preuss (complex Remez exchange) algorithm in some examples     

Tight upper bounds on the redundancy of Huffman codes

Bounds on the redundancy of Huffman codes in terms of the probability p₁ of the most likely source letter are provided. In particular, upper bounds are presented that are sharper than the bounds given recently by R.G. Gallager (ibid., vol.IT-24, no.6, p.668-74, Nov.1978) and by R.M. Capocelli et al. (ibid., vol. IT-32, no.6, p.854-857, Nov. 1986) for an interval 2/(2^l+1+1)<p₁<1/(2^l-1), l⩾2. It is shown that the new bounds are the tightest possible for these intervals     

The Cost of Uncorrelation and Noncooperation in MIMO Channels

We investigate the capacity loss for using uncorrelated Gaussian input over a multiple-input multiple-output (MIMO) linear additive-noise channel. We upper-bound the capacity loss by a universal constant C* which is independent of the channel matrix and the noise distribution. For a single-user MIMO channel with n_t inputs and n_r outputs C* = min [ 1/2, n_r/n_t log₂ (1+n_t/n_r) ] bit per input dimension (or 2C* bit per transmit antenna per second per hertz), under both total and per-input power constraints. If we restrict attention to (colored) Gaussian noise, then the capacity loss is upper-bounded by a smaller constant C_G = n_r/2n_r log₂ (n_t/n_r) for n_r ges n_t/e, and C_G = 0.265 otherwise, and this bound is tight for certain cases of channel matrix and noise covariance. We also derive similar bounds for the sum-capacity loss in multiuser MIMO channels. This includes in particular uncorrelated Gaussian transmission in a MIMO multiple-access channel (MAC), and "flat" Gaussian dirty-paper coding (DPC) in a MIMO broadcast channel. In the context of wireless communication, our results imply that the benefit of beamforming and spatial water-filling over simple isotropic transmission is limited. Moreover, the excess capacity of a point-to-point MIMO channel over the same MIMO channel in a multiuser configuration is bounded by a universal constant.