Variable-complexity trellis decoding of binary convolutional codes

Considers trellis decoding of convolutional codes with selectable effort, as measured by decoder complexity. Decoding is described for single parent codes with a variety of complexities, with performance “near” that of the optimal fixed receiver complexity coding system. Effective free distance is examined. Criteria are proposed for ranking parent codes, and some codes found to be best according to the criteria are tabulated, Several codes with effective free distance better than the best code of comparable complexity were found. Asymptotic (high SNR) performance analysis and error propagation are discussed. Simulation results are also provided     

Coded QAM using a binary convolutional code

As an alternative to trellis coding, a binary convolutional code is considered for use with such nonbinary modulation schemes as quadrature amplitude modulation (QAM). A Gray code is used to map the encoder output to the M-ary QAM constellation. The focus is on the design of 16-ary coded QAM with a rate 3/4 punctured convolutional code of a constraint length 7. A quantized binary metric generation method is proposed and shown to be suboptimum as compared to the direct use of a M-ary unquantized metric. Impressive coding gains and bandwidth efficiency are shown in comparison with uncoded systems     

Some periodic convolutional codes better than any fixed code (Corresp.)

Some(n_{o}=2; k_{o}=1)noncatastrophic periodic convolutional codes with memoryM=4are given that have the same free distance,d_{infty}, as the best fixed code but have both a smaller number of paths of weightd_{infty}per time instant and a smaller average number of information bit errors per such path for periodsT=2, 3, 4, and5. It is also shown that an(n_{0}, k_{0})code of periodTis equivalent to a fixed code with parameters(Tn_{0}, Tk_{0}).     

A comparison of trellis modules for binary convolutional codes

A convolutional code can be represented by the conventional trellis module or the “minimal” trellis module based on the BCJR trellis for block codes. For many convolutional codes, the trellis complexity (TC) of the minimal module is significantly less than the TC of the conventional module. An alternative representation, consisting of an extended BCJR trellis module and a pruned version of the conventional module, was previously introduced. We prove that the overall TC of the two new modules is less than the TC of the conventional module for infinitely many codes. Furthermore, we show that the overall TC of the new modules is smaller than the TC of the minimal module for many codes considered in the literature     

Hamming distance preserving mappings and trellis codes withconstrained binary symbols

The transformation of a linear convolutional code into a run-length-constrained or balanced trellis code with the same or larger free distance is investigated. The transformation involves a Hamming-distance-preserving mapping of the set of unconstrained binary symbols of the convolutional code onto a set of suitably constrained symbols. Simple tests to determine if these mappings can exist and a tree search algorithm for finding such mappings are presented     

Geometrically uniform partitions of L×MPSK constellations andrelated binary trellis codes

The theory of geometrically uniform trellis codes is applied to the case of multidimensional PSK (phase shift keying) constellations. The symmetry group of an L×MPSK (M-ary PSK) constellation is completely characterized. Conditions for rotational invariance of geometrically uniform partitions of a signal constellation are given. Through suitable algorithms, geometrically uniform partitions of L×MPSK (M=4,8,16 and L=1,2,3,4) constellations are found, which present good characteristics in terms of the set of distances at a given partition level, the maximum obtainable rotational invariance, and the isomorphism of the quotient group associated with the partition. These partitions are used as starting points in a search for good geometrically uniform trellis codes based on binary convolutional codes     

Variable-to-fixed length codes are better than fixed-to-variablelength codes for Markov sources

It is demonstrated that for finite-alphabet, kth-order ergodic Markov sources (i.e. memory of k letters), a variable-to-fixed length code is better than the best fixed-to-variable length code (Huffman code). It is shown how to construct a variable-to-fixed length code for a kth order ergodic Markov source, which compresses more effectively than the best fixed-to-variable code     

Variable-to-fixed length codes provide better large deviationsperformance than fixed-to-variable length codes

It is proved that for finite-alphabet, finite-state unifilar sources, variable-to-fixed length codes provide better large deviations performance of the empirical compression ratio, than fixed-to-variable length codes. It is shown how to construct a universal variable-to-fixed length code that achieves the optimal performance     

A Goppa-like bound on the trellis state complexity of algebraic-geometric codes

For a linear code C of length n and dimension k, Wolf (1978) noticed that the trellis state complexity s(C) of C is upper-bounded by w(C):=min(k,n-k). We point out some new lower bounds for s(C). In particular, if C is an algebraic-geometric code, then s(C)/spl ges/w(C)-(g-a), where g is the genus of the underlying curve and a is the abundance of the code.     

Power allocation and code construction for space-time turbo trellis codes with partial CSI feedback

Conventional space-time turbo trellis coding (STTuTC) schemes allocate transmit power equally to the available antennas. This is not optimal if channel state information (CSI) is available at the transmitter. A STTuTC scheme is considered with partial CSI knowledge that optimally allocates power to the transmit antennas. This scheme is referred to as STTuTC with dynamic transmit power allocation (STTuTC/DTPA). The optimum four-state constituent code and power allocation are presented. Simulation results show that the STTuTC/DTPA scheme with the new code outperforms conventional STTuTC schemes.     

Bounds for binary codes of length less than 25

Improved bounds forA(n,d), the maximum number of codewords in a (linear or nonlinear) binary code of word lengthnand minimum distanced, and forA(n,d,w), the maximum number of binary vectors of lengthn, distanced, and constant weightwin the rangen leq 24andd leq 10are presented. Some of the new values areA     

Non‐binary SOVA algorithms for decoding of block codes on a sectionalized trellis

In this paper, we explore computationally efficient implementations of the soft output viterbi algorithm (SOVA) applied to Soft‐Input Soft‐Output (SISO) decoding of linear block codes. In order to simplify the trellis‐based decoding of binary block codes with SOVA, we use the technique of sectionalization of the trellis, which has been successfully applied to the simplification of the MAP and Max‐Log‐MAP algorithms. Due to the branch complexity of the sectionalized trellis, we define a generalization of a non‐binary version of SOVA. However, the computational complexity of directly applying this approach remains too high for efficient implementation; we thus introduce the concept of non‐binary SOVA (NSOVA) with propagation of bit‐level reliabilities (BLR). This new algorithm is analyzed from a computational complexity viewpoint. Both serial and parallel implementations are explored. Finally, optimal sectionalizations are derived for selected codes; since the normal SOVA decoding is a particular case of NSOVA with BLR, we show that our approach is more efficient than a bit‐level trellis by showing that, for all the codes tested, the optimal trellis is a sectionalized one. Copyright © 2007 John Wiley & Sons, Ltd.     

The dynamics of group codes: state spaces, trellis diagrams, andcanonical encoders

A group code C over a group G is a set of sequences of group elements that itself forms a group under a component-wise group operation. A group code has a well-defined state space Σ_k at each time k. Each code sequence passes through a well-defined state sequence. The set of all state sequences is also a group code, the state code of C. The state code defines an essentially unique minimal realization of C. The trellis diagram of C is defined by the state code of C and by labels associated with each state transition. The set of all label sequences forms a group code, the label code of C, which is isomorphic to the state code of C. If C is complete and strongly controllable, then a minimal encoder in controller canonical (feedbackfree) form may be constructed from certain sets of shortest possible code sequences, called granules. The size of the state space Σ_k is equal to the size of the state space of this canonical encoder, which is given by a decomposition of the input groups of C at each time k. If C is time-invariant and ν-controllable, then |Σ_k|=Π_1⩽j⩽v|F_j/F _j-1|^j, where F₀ ⊆···⊆ Fν is a normal series, the input chain of C. A group code C has a well-defined trellis section corresponding to any finite interval, regardless of whether it is complete. For a linear time-invariant convolutional code over a field G, these results reduce to known results; however, they depend only on elementary group properties, not on the multiplicative structure of G. Moreover, time-invariance is not required. These results hold for arbitrary groups, and apply to block codes, lattices, time-varying convolutional codes, trellis codes, geometrically uniform codes and discrete-time linear systems     

Prime-phase sequences with periodic correlation properties better than binary sequences

For the case where p is an odd prime, n>or=2 is an integer, and omega is a complex primitive pth root of unity, a construction is presented for a family of p/sup n/ p-phase sequences (symbols of the form omega /sup i/), where each sequence has length p/sup n/-1, and where the maximum nontrivial correlation value C/sub max/ does not exceed 1+ square root p/sup n/. A complete distribution of correlation values is provided. As a special case of this construction, a previous construction due to Sidelnikov (1971) is obtained. The family of sequences is asymptotically optimum with respect to its correlation properties, and, in comparison with many previous nonbinary designs, the present design has the additional advantage of not requiring an alphabet of size larger than three. The new sequences are suitable for achieving code-division multiple access and are easily implemented using shift registers. They wee discovered through an application of Deligne's bound (1974) on exponential sums of the Weil type in, several variables. The sequences are also shown to have strong identification with certain bent functions.<>     

A [55,16,19] binary Goppa code and related codes having largeminimum distance

A [55,16,19] binary Goppa code is used to construct [57,17,17], [58,17,18], [59,17,19], and [60,17,20] codes. The first two codes have smaller redundancy than previously known codes (linear or nonlinear) of the same length and minimum distance. The last two codes have parameters previously attained only by nonlinear codes     

Block and trellis codes for the binary (1-D) partial responsechannel with simple maximum likelihood decoders

We consider block and convolutional codes for improving the reliability of data transmission over the binary precoded noisy (1-D) partial response channel. We concentrate on a class of codes for which the maximum likelihood decoder, matched to the encoder, precoder, and the channel has the same trellis structure as the encoder. Thus, doubling the number of states due to the channel memory is avoided, We show that the necessary and sufficient condition to belong to this class is that all codewords be of the same parity. The Reed-Muller and Golay codes belong to this class     

On the [24, 12, 10] quaternary code and binary codes with anautomorphism having two cycles

A general decomposition theorem is given for codes over finite fields which have an automorphism of a given type. Such codes can be decomposed as direct sums of subcodes which may be viewed as shorter length codes over extension fields. If such a code is self-dual, sometimes the subcodes are also. This decomposition is applied to prove that the self-dual [24, 12, 10] quaternary code has no automorphism of order 3. This decomposition is also applied to count the number of equivalent [2r, r] and [2r+2r+1] self-dual binary codes with an automorphism of prime order r