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     

Coset codes viewed as terminated convolutional codes

Coset codes are considered as terminated convolutional codes. Based on this approach, three new general results are presented. First, it is shown that the iterative squaring construction can equivalently be defined from a convolutional code whose trellis terminates. This convolutional code determines a simple encoder for the coset code considered, and the state and branch labelings of the associated trellis diagram become straightforward. Also, from the generator matrix of the code in its convolutional code form, much information about the trade-off between the state connectivity and complexity at each section, and the parallel structure of the trellis, is directly available. Based on this generator matrix, it is shown that the parallel branches in the trellis diagram of the convolutional code represent the same coset code C₁ of smaller dimension and shorter length. Utilizing this fact, a two-stage optimum trellis decoding method is devised. The first stage decodes C₁ while the second stage decodes the associated convolutional code, using the branch metrics delivered by stage 1. Finally, a bidirectional decoding of each received block starting at both ends is presented. If about the same number of computations is required, this approach remains very attractive from a practical point of view as it roughly doubles the decoding speed. This fact is particularly interesting whenever the second half of the trellis is the mirror image of the first half, since the same decoder can be implemented for both parts     

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     

Random double-bit error-correcting decomposable codes

For odd m, a family of decomposable [3·(2^m-1), 3·(2^m-1)-3m, 5] codes, based on |a+x|b+x|a+b+x| construction, are proposed. A simple high-speed decoding algorithm for these codes suitable for implementation in combinational circuits is described     

Linear unequal error protection codes from shorter codes (Corresp.)

The methods for combining codes, such as the direct sum, direct product, and|u|u + v|constructions, concatenation, etc., are extended to linear unequal error protection codes.     

Weight distribution for closest coset decoding of |u|u+v|constructed codes

In this correspondence, the exact weight distribution for closest coset decoding of |u|u+v| constructed codes is derived. The results allow more accurate evaluations of the decoding error probabilities     

Repeated-root cyclic codes

In the theory of cyclic codes, it is common practice to require that (n,q)=1, where n is the word length and F_q is the alphabet. It is shown that the even weight subcodes of the shortened binary Hamming codes form a sequence of repeated-root cyclic codes that are optimal. In nearly all other cases, one does not find good cyclic codes by dropping the usual restriction that n and q must be relatively prime. This statement is based on an analysis for lengths up to 100. A theorem shows why this was to be expected, but it also leads to low-complexity decoding methods. This is an advantage, especially for the codes that are not much worse than corresponding codes of odd length. It is demonstrated that a binary cyclic code of length 2n (n odd) can be obtained from two cyclic codes of length n by the well-known | u|u+v| construction. This leads to an infinite sequence of optimal cyclic codes with distance 4. Furthermore, it is shown that low-complexity decoding methods can be used for these codes. The structure theorem generalizes to other characteristics and to other lengths. Some comparisons of the methods using earlier examples are given     

Two-dimensional weight-constrained codes through enumeration bounds

For a rational α∈(0,1), let 𝒜_n×m,α be the set of binary n×m arrays in which each row has Hamming weight αm and each column has Hamming weight αn, where αm and αn are integers. (The special case of two-dimensional balanced arrays corresponds to α=1/2 and even values for n and m.) The redundancy of 𝒜_n×m,α is defined by ρ_n×m,α=nmH(α)-log₂|𝒜 _n×m,α| where H(x)=-xlog₂x-(1-x)log₂(1-x). Bounds on ρ_n×m,α are obtained in terms of the redundancies of the sets 𝒜_ℒ,α of all binary ℒ-vectors with Hamming weight αℒ, ℒ∈{n,m}. Specifically, it is shown that ρ_n×m,α⩽nρ_m,α+mρ _n,α where ρ_ℒ,α=ℒH(α)-log₂|𝒜 _ℒ,α| and that this bound is tight up to an additive term O(n+log m). A polynomial-time coding algorithm is presented that maps unconstrained input sequences into 𝒜_n×m,α at a rate H(α)-(ρ_m,α/m)     

Fast generalized minimum-distance decoding of algebraic-geometryand Reed-Solomon codes

Generalized minimum-distance (GMD) decoding is a standard soft-decoding method for block codes. We derive an efficient general GMD decoding scheme for linear block codes in the framework of error-correcting pairs. Special attention is paid to Reed-Solomon (RS) codes and one-point algebraic-geometry (AG) codes. For RS codes of length n and minimum Hamming distance d the GMD decoding complexity turns out to be in the order O(nd), where the complexity is counted as the number of multiplications in the field of concern. For AG codes the GMD decoding complexity is highly dependent on the curve in consideration. It is shown that we can find all relevant error-erasure-locating functions with complexity O(o₁nd), where o₁ is the size of the first nongap in the function space associated with the code. A full GMD decoding procedure for a one-point AG code can be performed with complexity O(dn²)     

Some optimal type-B1 convolutional codes (Corresp.)

Ratefrac{3}{4}optimal type-B1burst-error-correcting convolutional codes have been discovered. Optimal codes of rate1/n_oandfrac{2}{3}are also given. A method of decoding is described.     

Sequential decoding of systematic and nonsystematic convolutional codes with arbitrary decoder bias

This paper presents several results involving Fano's sequential decoding algorithm for convolutional codes. An upper bound to theath moment of decoder computation is obtained for arbitrary decoder biasBanda leq 1. An upper bound on error probability with sequential decoding is derived for both systematic and nonsystematic convolutional codes. This error bound involves the exact value of the decoder biasB. It is shown that there is a trade-off between sequential decoder computation and error probability as the biasBis varied. It is also shown that for many values ofB, sequential decoding of systematic convolutional codes gives an exponentially larger error probability than sequential decoding of nonsystematic convolutional codes when both codes are designed with exponentially equal optimum decoder error probabilities.     

New rate-compatible punctured convolutional codes for Viterbidecoding

New good rate-P/(P+δ) rate-compatible punctured convolutional (RCPC) codes for 2⩽P⩽7 and 1⩽δ⩽(n-1)P were found and tabulated, These codes have been determined by iterative search based upon a criterion of maximizing the free distance and were generated by periodically puncturing their rate-1/n mother codes of memory 2⩽M⩽6 and n=2. These codes are expected to find their applications in unequal error protection schemes employing Viterbi decoding     

A family of efficient burst-correcting array codes

A family of binary burst correcting array codes that are defined as follows is discussed: consider an n₁×n n₂ array with n₁=4u+ν+2 and n₂=6u+2ν+5, u⩾1, ν⩾0, ν≠1 where each row and column has even parity. The bits are read diagonally starting from the upper-left corner. The columns are viewed cyclically, i.e. the array is a cylinder. If one diagonal has been read out, one proceeds with the second diagonal preceding it. It is proven that the codes of this type can correct any burst of length up to n₁. The burst-correcting efficiency of this family tends to 4/5 as u→∞. As a comparison, the burst-correcting efficiency of other families of array codes tends to 2/3; the same is true for Fire codes. A simple decoding algorithm for the codes is also presented     

A construction technique for random-error-correcting convolutional codes

A simple algorithm is presented for finding rate1/nrandom-error-correcting convolutional codes. Good codes considerably longer than any now known are obtained. A discussion of a new distance measure for convolutional codes, called the free distance, is included. Free distance is particularly useful when considering decoding schemes, such as sequential decoding, which are not restricted to a fixed constraint length. It is shown how the above algorithm can be modified slightly to produce codes with known free distance. A comparison of probability of error with sequential decoding is made among the best known constructive codes of constraint length36.     

MAP decoding of convolutional codes using reciprocal dual codes

A new symbol-by-symbol maximum a posteriori (MAP) decoding algorithm for high-rate convolutional codes using reciprocal dual convolutional codes is presented. The advantage of this approach is a reduction of the computational complexity since the number of codewords to consider is decreased for codes of rate greater than 1/2. The discussed algorithms fulfil all requirements for iterative (“turbo”) decoding schemes. Simulation results are presented for high-rate parallel concatenated convolutional codes (“turbo” codes) using an AWGN channel or a perfectly interleaved Rayleigh fading channel. It is shown that iterative decoding of high-rate codes results in high-gain, moderate-complexity coding     

Low-complexity ML decoding for convolutional tail-biting codes

Recently, a maximum-likelihood (ML) decoding algorithm with two phases has been proposed for convolutional tailbiting codes [1]. The first phase applies the Viterbi algorithm to obtain the trellis information, and then the second phase employs the algorithm A* to find the ML solution. In this work, we improve the complexity of the algorithm A* by using a new evaluation function. Simulations showed that the improved A* algorithm has over 5 times less average decoding complexity in the second phase when E_b/N₀? 4 dB.     

High-rate punctured convolutional codes for Viterbi and sequentialdecoding

An investigation is conducted of the high-rate punctured convolutional codes suitable for Viterbi and sequential decoding. Results on known short-memory codes M⩽8 discovered by others are extended. Weight spectra and upper bounds on the bit error probability of the best known punctured codes having memory 2⩽M ⩽8, and coding rates 2/3⩽R⩽7/8 are provided. Newly discovered rate-2/3 and -3/4 long-memory punctured convolutional codes with 9⩽M⩽23 are provided together with the leading terms of their weight spectra and their bit error performance bounds. Some results of simulation with sequential decoding are given     

High-rate punctured convolutional self-doubly orthogonal codes for iterative threshold decoding

The puncturing technique allows obtaining high-rate convolutional codes from low-rate convolutional codes used as mother codes. This technique has been successfully applied to generate good high-rate convolutional codes which are suitable for Viterbi and sequential decoding. In this paper, we investigate the puncturing technique for convolutional self-doubly orthogonal codes (CSO/sup 2/C) which are decoded using an iterative threshold-decoding algorithm. Based on an analysis of iterative threshold decoding of the rate-R=b/(b+1) punctured systematic CSO/sup 2/C, the required properties of the rate-R=1/2 systematic convolutional codes (SCCs) used as mother codes are derived. From this analysis, it is shown that there is no need for the punctured mother codes to respect all the required conditions, in order to maintain the double orthogonality at the second iteration step of the iterative threshold-decoding algorithm. The results of the search for the appropriate rate-R=1/2 SCCs used as mother codes to yield a large number of punctured codes of rates 2/3/spl les/R/spl les/6/7 are presented, and some of their error performances evaluated.     

Shadow codes and weight enumerators

The technique of using shadow codes to build larger self-dual codes is extended to codes over arbitrary fields. It is shown how to build the codes and how to determine the new weight enumerator as well. For codes over fields equipped with a square root of -1 and not of characteristic 2, a self-dual code of length n+2 can be built from a self-dual code of length n; for codes over a field without a square root of -1 and not of characteristic 2 a self-dual code of length n+4 is built from a self-dual code of length n; and for codes over fields of characteristic 2 the length of the new self-dual code depends on the presence of the all-one vector in the subcode chosen. In certain cases using the subcode of vectors orthogonal to the all-one vector, the new weight enumerator can be calculated directly from the original weight enumerator. Specific examples of the technique are illustrated for codes over F₃, F₄, and F₅     

Space-time turbo codes with full antenna diversity

In attempting to find a spectrally and power efficient channel code which is able to exploit maximum diversity from a wireless channel whenever available, we investigate the possibility of constructing a full antenna diversity space-time turbo code. As a result, both three-antenna and two-antenna (punctured) constructions are shown to be possible and very easy to find. To check the decodability and performance of the proposed codes, we derive non-binary soft-decoding algorithms. The performance of these codes are then simulated and compared with two existing space-time convolutional codes (one has minimum worst-case symbol-error probability; the other has maximal minimum free distance) having similar decoding complexity. As the simulation results show, the proposed space-time turbo codes give similar or slightly better performance than the convolutional codes under extremely slow fading. When fading is fast, the better distance spectra of the turbo codes help seize the temporal diversity. Thus, the performance advantage of the turbo codes becomes evident. In particular, 10^-5 bit-error rate and 10^-3 frame-error rate can be achieved at less than 6-dB E_b/N₀ with 1 b/s/Hz and binary phase-shift keying modulation. The practical issue of obtaining the critical channel state information (CSI) is also considered by applying an iteratively filtered pilot symbol-assisted modulation technique. The penalty when the CSI is not given a priori is about 2-3 dB