Quasi-cyclic codes over Z4 and some new binarycodes

Previously, (linear) codes over Z₄ and quasi-cyclic (QC) codes (over fields) have been shown to yield useful results in coding theory. Combining these two ideas we study Z ₄-QC codes and obtain new binary codes using the usual Gray map. Among the new codes, the lift of the famous Golay code to Z₄ produces a new binary code, a (92, 2²⁴, 28)-code, which is the best among all binary codes (linear or nonlinear). Moreover, we characterize cyclic codes corresponding to free modules in terms of their generator polynomials     

Z4×(F2+uF2)上的一类循环码

定义了Z₄×（F₂+uF₂）上的循环码,明确了一类循环码的生成元结构,给出了该类循环码的极小生成元集.利用Gray映射,构造了一些二元非线性码.     

Results on Punctured Low-Density Parity-Check Codes and Improved Iterative Decoding Techniques

This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R₁ and R₂ satisfying 012<1, there exists an ensemble of LDPC codes with the following property. The ensemble can be punctured from rate R₁ to R₂ resulting in asymptotically good codes for all rates R₁lesRlesR₂. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R₁2<1, the existence of the sequences of punctured LDPC codes that are capacity-achieving for all rates R₁ lesRlesR₂ is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels     

Performance of sphere decoding of block codes

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We focus on analyzing the performance of sphere decoding of linear block codes. We analyze the performance of soft-decision sphere decoding on AWGN channels and a variety of modulation schemes. A hard-decision sphere decoder is a bounded distance decoder with the corresponding decoding radius. We analyze the performance of hard-decision sphere decoding on binary and q-ary symmetric channels. An upper bound on the performance of maximum-likelihood decoding of linear codes defined over F_q (e.g. Reed- Solomon codes) and transmitted over q-ary symmetric channels is derived and used in the analysis.We then discuss sphere decoding of general block codes or lattices with arbitrary modulation schemes. The tradeoff between the performance and complexity of a sphere decoder is then discussed.     

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.     

A 2-adic approach to the analysis of cyclic codes

This paper describes how 2-adic numbers can be used to analyze the structure of binary cyclic codes and of cyclic codes defined over Z _2(a), a⩾2, the ring of integers modulo 2^a. It provides a 2-adic proof of a theorem of McEliece that characterizes the possible Hamming weights that can appear in a binary cyclic code. A generalization of this theorem is derived that applies to cyclic codes over Z_2(a) that are obtained from binary cyclic codes by a sequence of Hensel lifts. This generalization characterizes the number of times a residue modulo 2^a appears as a component of an arbitrary codeword in the cyclic code. The limit of the sequence of Hensel lifts is a universal code defined over the 2-adic integers. This code was first introduced by Calderbank and Sloane (1995), and is the main subject of this paper. Binary cyclic codes and cyclic codes over Z_2(a) are obtained from these universal codes by reduction modulo some power of 2. A special case of particular interest is cyclic codes over Z₄ that are obtained from binary cyclic codes by means of a single Hensel lift. The binary images of such codes under the Gray isometry include the Kerdock, Preparata, and Delsart-Goethals codes. These are nonlinear binary codes that contain more codewords than any linear code presently known. Fundamental understanding of the composition of codewords in cyclic codes over Z₄ is central to the search for more families of optimal codes. This paper also constructs even unimodular lattices from the Hensel lift of extended binary cyclic codes that are self-dual with all Hamming weights divisible by 4. The Leech lattice arises in this way as do extremal lattices in dimensions 32 through 48     

Cyclic codes and self-dual codes over F2+uF2

We introduce linear cyclic codes over the ring F₂+uF ₂={0,1,u,u¯=u+1}, where u²=0 and study them by analogy with the Z₄ case. We give the structure of these codes on this new alphabet. Self-dual codes of odd length exist as in the case of Z₄-codes. Unlike the Z₄ case, here free codes are not interesting. Some nonfree codes give rise to optimal binary linear codes and extremal self-dual codes through a linear Gray map     

The Z4-linearity of Kerdock, Preparata, Goethals, andrelated codes

Certain notorious nonlinear binary codes contain more codewords than any known linear code. These include the codes constructed by Nordstrom-Robinson (1967), Kerdock (1972), Preparata (1968), Goethals (1974), and Delsarte-Goethals (1975). It is shown here that all these codes can be very simply constructed as binary images under the Gray map of linear codes over Z₄, the integers mod 4 (although this requires a slight modification of the Preparata and Goethals codes). The construction implies that all these binary codes are distance invariant. Duality in the Z₄ domain implies that the binary images have dual weight distributions. The Kerdock and “Preparata” codes are duals over Z₄-and the Nordstrom-Robinson code is self-dual-which explains why their weight distributions are dual to each other. The Kerdock and “Preparata” codes are Z₄-analogues of first-order Reed-Muller and extended Hamming codes, respectively. All these codes are extended cyclic codes over Z₄, which greatly simplifies encoding and decoding. An algebraic hard-decision decoding algorithm is given for the “Preparata” code and a Hadamard-transform soft-decision decoding algorithm for the I(Kerdock code. Binary first- and second-order Reed-Muller codes are also linear over Z₄ , but extended Hamming codes of length n⩾32 and the Golay code are not. Using Z₄-linearity, a new family of distance regular graphs are constructed on the cosets of the “Preparata” code     

Hybrid Hard-Decision Iterative Decoding of Irregular Low-Density Parity-Check Codes

Time-invariant hybrid (Hscr_TI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on Hscr_TI algorithms with majority-based (MB) binary message-passing constituents, we use density evolution (DE) and finite-length simulation to analyze the performance and the convergence properties of these algorithms over (memoryless) binary symmetric channels. To apply DE, we generalize degree distributions to have the irregularity of both the code and the decoding algorithm embedded in them. A tight upper bound on the threshold of MB Hscr_TI algorithms is derived, and it is proven that the asymptotic error probability for these algorithms tends to zero, at least exponentially, with the number of iterations. We devise optimal MB Hscr_TI algorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB Hscr_TI algorithms are more robust and can better cope with unknown channel conditions, and thus can be practically more attractive     

Two 16-state, rate R=2/4 trellis codes whose free distances meetthe Heller bound

For rate R=1/2 convolutional codes with 16 states there exists a gap between Heller's (1968) upper bound on the free distance and its optimal value. This article reports on the construction of 16-state, binary, rate R=2/4 nonlinear trellis and convolutional codes having d _free=8; a free distance that meets the Heller upper bound. The nonlinear trellis code is constructed from a 16-state, rate R=1/2 convolutional code over Z₄ using the Gray map to obtain a binary code. Both convolutional codes are obtained by computer search. Systematic feedback encoders for both codes are potential candidates for use in combination with iterative decoding. Regarded as modulation codes for 4-PSK, these codes have free squared Euclidean distance d_{E, free}²=16     

Source-channel optimized trellis codes for bitonal imagetransmission over AWGN channels

We consider the design of trellis codes for transmission of binary images over additive white Gaussian noise (AWGN) channels. We first model the image as a binary asymmetric Markov source (BAMS) and then design source-channel optimized (SCO) trellis codes for the BAMS and AWGN channel. The SCO codes are shown to be superior to Ungerboeck's codes by approximately 1.1 dB (64-state code, 10^-5 bit error probability), We also show that a simple “mapping conversion” method can be used to improve the performance of Ungerboeck's codes by approximately 0.4 dB (also 64-state code and 10 ^-5 bit error probability). We compare the proposed SCO system with a traditional tandem system consisting of a Huffman code, a convolutional code, an interleaver, and an Ungerboeck trellis code. The SCO system significantly outperforms the tandem system. Finally, using a facsimile image, we compare the image quality of an SCO code, an Ungerboeck code, and the tandem code, The SCO code yields the best reconstructed image quality at 4-5 dB channel SNR     

Low-density parity-check codes for space-time wireless transmission

Irregular low-density parity-check (LDPC) codes have shown exceptionally good performance for single antenna systems over a wide class of channels. In this paper, we investigate their application to multiple antenna systems in flat Rayleigh fading channels. For small transmit arrays, we focus mainly on space-time coding with 2/sup p/-ary LDPC codes, where p equals the number of encoded bits transmitted by the transmit antenna array during each signaling interval. For large transmit arrays, we study a layered space-time architecture using binary LDPC codes as component codes of each layer: We show through simulation that, when applied to multiple antenna systems with high diversity order, LDPC codes of quasi-regular construction are able to achieve higher coding gain and/or diversity gain than previously proposed space-time trellis codes, space-time turbo codes, and convolutional codes in a number of fading conditions. Extending the work of density evolution with Gaussian approximation, we study 2/sup p/-ary LDPC codes on multiple antenna fading channels, and search for the optimum 2/sup p/-ary quasi-regular codes in quasi-static fading. We also show that on fast fading channels, 2/sup p/-ary irregular LDPC codes, though designed for static channels, have superior performance to nonbinary quasiregular codes and binary irregular codes specifically designed for fast fading channels.     

Constrained Information Combining: Theory and Applications for LDPC Coded Systems

This paper tightens previous information combining bounds on the performance of iterative decoding of binary low-density parity-check (LDPC) codes over binary-input symmetric-output channels by tracking the probability of erroneous bit in conjunction with mutual information. Evaluation of the new bounds as well as of other known bounds on different LDPC ensembles demonstrates sensitivity of the finite dimensional iterative bounds to lambda₂, the fraction of edges connected to degree 2 variable nodes     

Frame error rates for convolutional codes on fading channels andthe concept of effective Eb/N0

Estimation of Viterbi decoder performance over channels with time-varying received signal levels is the subject of this paper. This work is motivated by a desire to obtain good estimates of the frame error rate (FER) for convolutional codes with bit-level interleaving over fading channels subject to practical power control algorithms. The convolutional code performance is quantified through the FER and effective E_b/N₀. where the latter is defined as the E_b/N₀ on an additive white Gaussian noise (AWGN) channel that results in the same FER. Given a received vector of (time-varying) E_b/N₀ values, we compute analytic estimates for the probability of frame error and the effective E_b /N₀ for a Viterbi decoder and interleaver combination. In particular, we validate our analysis using the R=1/3 convolutional code and interleaver used on the IS-95 CDMA reverse channel. Comparisons with simulations show that even for E_b/N₀ vectors with very large variations, our proposed estimates are good to within 0.2 dB for the effective E_b/N₀, giving FER estimates within a factor of two-five of the simulations     

Bandwidth efficient coding for fading channels: code constructionand performance analysis

The authors apply a general method of bounding the event error probability of TCM (trellis-coded modulation) schemes to fading channels and use the effective length and the minimum-squared-product distance to replace the minimum-free-squared-Euclidean distance as code design parameters for Rayleigh and Rician fading channels with a substantial multipath component. They present 8-PSK (phase-shift-keying) trellis codes specifically constructed for fading channels that outperform equivalent codes designed for the AWGN (additive white Gaussian noise) channel when v⩾5. For quasiregular trellis codes there exists an efficient algorithm for evaluating event error probability, and numerical results which demonstrate the importance of the effective length as a code design parameter for fading channels with or without side information have been obtained. This is consistent with the case for binary signaling, where the Hamming distance remains the best code design parameter for fading channels. The authors show that the use of Reed-Solomon block codes with expanded signal sets becomes interesting only for large value of E_s/N₀, where they begin to outperform trellis codes     

Embedded Rank Distance Codes for ISI Channels

Designs for transmit alphabet constrained space–time codes naturally lead to questions about the design of rank distance codes. Recently, diversity embedded multilevel space–time codes for flat-fading channels have been designed from sets of binary matrices with rank distance guarantees over the binary field by mapping them onto quadrature amplitude modulation (QAM) and phase-shift keying (PSK) constellations. In this paper, we demonstrate that diversity embedded space–time codes for fading intersymbol interference (ISI) channels can be designed with provable rank distance guarantees. As a corollary, we obtain an asymptotic characterization of the fixed transmit alphabet rate–diversity tradeoff for multiple antenna fading ISI channels. The key idea is to construct and analyze properties of binary matrices with a particular structure (Toeplitz structure) induced by ISI channels.      

Sort-and-match algorithm for soft-decision decoding

Let a q-ary linear (n, k) code C be used over a memoryless channel. We design a decoding algorithm Ψ_N that splits the received block into two halves in n different ways. First, about √N error patterns are found on either half. Then the left- and right-hand lists are sorted out and matched to form codewords. Finally, the most probable codeword is chosen among at most n√N codewords obtained in all n trials. The algorithm can be applied to any linear code C and has complexity order of n³√N. For any N⩾q^n-k, the decoding error probability P_N exceeds at most 1+q^n-k/N times the probability P_Ψ (C) of maximum-likelihood decoding. For code rates R⩾1/2, the complexity order q^n-k/2 grows as square root of general trellis complexity q^min{n-k,k}. When used on quantized additive white Gaussian noise (AWGN) channels, the algorithm Ψ_N can provide maximum-likelihood decoding for most binary linear codes even when N has an exponential order of q^n-k     

Cyclic codes over Z4, locator polynomials, and Newton'sidentities

Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock (1972) and Preparata (1968) codes that can be very simply constructed as binary images, under the Gray map, of linear codes over Z₄ that are defined by means of parity checks involving Galois rings. This paper describes how Fourier transforms on Galois rings and elementary symmetric functions can be used to derive lower bounds on the minimum distance of such codes. These methods and techniques from algebraic geometry are applied to find the exact minimum distance of a family of Z ₄. Linear codes with length 2^m (m, odd) and size 2(2^m+1-5m-2). The Gray image of the code of length 32 is the best (64, 2³⁷) code that is presently known. This paper also determines the exact minimum Lee distance of the linear codes over Z₄ that are obtained from the extended binary two- and three-error-correcting BCH codes by Hensel lifting. The Gray image of the Hensel lift of the three-error-correcting BCH code of length 32 is the best (64, 2³²) code that is presently known. This code also determines an extremal 32-dimensional even unimodular lattice     

Finite-Dimensional Bounds on Zm and Binary LDPC Codes With Belief Propagation Decoders

This paper focuses on finite-dimensional upper and lower bounds on decodable thresholds of Zopf_m and binary low-density parity-check (LDPC) codes, assuming belief propagation decoding on memoryless channels. A concrete framework is presented, admitting systematic searches for new bounds. Two noise measures are considered: the Bhattacharyya noise parameter and the soft bit value for a maximum a posteriori probability (MAP) decoder on the uncoded channel. For Zopf _m LDPC codes, an iterative m-dimensional bound is derived for m-ary-input/symmetric-output channels, which gives a sufficient stability condition for Zopf_m LDPC codes and is complemented by a matched necessary stability condition introduced herein. Applications to coded modulation and to codes with nonequiprobably distributed codewords are also discussed. For binary codes, two new lower bounds are provided for symmetric channels, including a two-dimensional iterative bound and a one-dimensional noniterative bound, the latter of which is the best known bound that is tight for binary-symmetric channels (BSCs), and is a strict improvement over the existing bound derived by the channel degradation argument. By adopting the reverse channel perspective, upper and lower bounds on the decodable Bhattacharyya noise parameter are derived for nonsymmetric channels, which coincides with the existing bound for symmetric channels