Rotational invariance of trellis codes. II. Group codes anddecoders

For pt.I see ibid., vol.42, no.3, p.751-65 (1996). In Part I, general results on rotationally invariant codes and encoders were derived assuming no algebraic structure. In Part II, trellis codes based on group systems are considered as a special case for which code and encoder constructions are particularly simple. Rotational invariance is expressed as an algebraic constraint on a group code, and algebraic constructions are found for both “absorbed precoder” encoders and for encoders with separate differential precoders. Finally, the various encoder forms used to achieve rotational invariance are compared based on their performance on an AWGN channel     

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     

Design and decoding of optimal high-rate convolutional codes

This correspondence deals with the design and decoding of high-rate convolutional codes. After proving that every (n,n-1) convolutional code can be reduced to a structure that concatenates a block encoder associated to the parallel edges with a convolutional encoder defining the trellis section, the results of an exhaustive search for the optimal (n,n-1) convolutional codes is presented through various tables of best high-rate codes. The search is also extended to find the "best" recursive systematic convolutional encoders to be used as component encoders of parallel concatenated "turbo" codes. A decoding algorithm working on the dual code is introduced (in both multiplicative and additive form), by showing that changing in a proper way the representation of the soft information passed between constituent decoders in the iterative decoding process, the soft-input soft-output (SISO) modules of the decoder based on the dual code become equal to those used for the original code. A new technique to terminate the code trellis that significantly reduces the rate loss induced by the addition of terminating bits is described. Finally, an inverse puncturing technique applied to the highest rate "mother" code to yield a sequence of almost optimal codes with decreasing rates is proposed. Simulation results applied to the case of parallel concatenated codes show the significant advantages of the newly found codes in terms of performance and decoding complexity.     

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     

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     

Rotational invariance of trellis codes. I. Encoders and precoders

We present a theoretical framework for rotational invariance of trellis codes. The distinction between codes and encoders plays a pivotal role. Necessary and sufficient conditions for rotational invariance are derived under general assumptions, and a construction is presented that obtains a rotationally invariant encoder for almost any rotationally invariant code, independent of the code's algebraic structure. Encoders that use a differential precoder are considered as a separate case, where a system-theoretic characterization of precoding is used to find two alternative and slightly less general encoder constructions     

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     

Bounded minimum distance decoding of unit memory codes

We propose an algorithm for bounded minimum distance decoding of (partial) unit memory codes up to half the “designed” extended row distance. It makes use of a reduced trellis with the nodes found by bounded minimum distance decoding of the block codes used in the unit memory code. The results can be extended to general multimemory codes. The complexity of this algorithm is upper bounded by 2(d¯ ₁^r-2d_α) times the complexity of the bounded minimum distance decoder of the block codes in the unit memory code. Here d_α is the linear increase of the designed extended row distance d¯_i^r     

On Minimality of Convolutional Ring Encoders

Convolutional codes are considered with code sequences modeled as semi-infinite Laurent series. It is well known that a convolutional code C over a finite group G has a minimal trellis representation that can be derived from code sequences. It is also well known that, for the case that G is a finite field, any polynomial encoder of C can be algebraically manipulated to yield a minimal polynomial encoder whose controller canonical realization is a minimal trellis. In this paper we seek to extend this result to the finite ring case G = BBZpr by introducing a so-called ldquo p-encoderrdquo. We show how to manipulate a polynomial encoding scheme of a noncatastrophic convolutional code over BBZpr to produce a particular type of p-encoder (ldquominimal p -encoderrdquo) whose controller canonical realization is a minimal trellis with nonlinear features. The minimum number of trellis states is then expressed as p ^gamma, where gamma is the sum of the row degrees of the minimal p -encoder. In particular, we show that any convolutional code over BBZpr admits a delay-free p -encoder which implies the novel result that delay-freeness is not a property of the code but of the encoder, just as in the field case. We conjecture that a similar result holds with respect to catastrophicity, i.e., any catastrophic convolutional code over BBZpr admits a noncatastrophic p-encoder.     

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     

Minimal tail-biting trellises: the Golay code and more

Tail-biting trellis representations of block codes are investigated. We develop some elementary theory, and present several intriguing examples, which we hope will stimulate further developments in this field. In particular, we construct a 16-state 12-section structurally invariant tail-biting trellis for the (24, 12, 8) binary Golay code. This tail-biting trellis representation is minimal: it simultaneously minimizes all conceivable measures of state complexity. Moreover, it compares favorably with the minimal conventional 12-section trellis for the Golay code, which has 256 states at its midpoint, or with the best quasi-cyclic representation of this code, which leads to a 64-state tail-biting trellis. Unwrapping this tail-biting trellis produces a periodically time-varying 16-state rate-1/2 “convolutional Golay code” with d=8, which has attractive performance/complexity properties. We furthermore show that the (6, 3, 4) quaternary hexacode has a minimal 8-state group tail-biting trellis, even though it has no such linear trellis over F₄. Minimal tail-biting trellises are also constructed for the (8, 4, 4) binary Hamming code, the (4, 2, 3) ternary tetracode, the (4, 2, 3) code over F₄, and the Z₄-linear (8. 4, 4) octacode     

On dualizing trellis-based APP decoding algorithms

The trellis of a finite Abelian group code is locally (i.e., trellis section by trellis section) related to the trellis of the corresponding dual group code which allows one to express the basic operations of the a posteriori probability (APP) decoding algorithm (defined on a single trellis section of the primal trellis) in terms of the corresponding dual trellis section. Using this local approach, any algorithm employing the same type of operations as the APP algorithm can, thus, be dualized, even if the global dual code does not exist (e.g., nongroup codes represented by a group trellis). Given this, the complexity advantage of the dual approach for high-rate codes can be generalized to a broader class of APP decoding algorithms, including suboptimum algorithms approximating the true APP, which may be more attractive in practical applications due to their reduced complexity. Moreover, the local approach opens the way for mixed approaches where the operations of the APP algorithm are not exclusively performed on the primal or dual trellis. This is inevitable if the code does not possess a trellis consisting solely of group trellis sections as, e.g., for certain terminated group or ring codes. The complexity reduction offered by applying dualization is evaluated. As examples, we give a dual implementation of a suboptimum APP decoding algorithm for tailbiting convolutional codes, as well as dual implementations of APP algorithms of the sliding-window type. Moreover, we evaluate their performance for decoding usual tailbiting codes or convolutional codes, respectively, as well as their performance as component decoders in iteratively decoded parallel concatenated schemes.     

衰落信道下的格形码设计

衰落信道下ＴＣＭ好码的设计准则是使有效码长度最长，同时使其对应路径的欧几里德距离乘积最大。本文首先从理论上得到有效码长度与卷积编码器的状态数，并行输入数之间的关系。提出了一种能达到最大自由长的状态转移图－标准拓扑篱笆图的概念，在此基础上，对衰落信道下采用速率为（２／３）８ＰＳＫ信号集合时的ＴＣＭ好码进行搜索，与文献中已有码相比，利用准则判别和进行蒙特－卡洛模拟都说明了新码在抗衰落方面的良好性能。     

Bandwidth-efficient noncoherent Trellis-coded MPSK

In this letter, we propose a novel bandwidth-efficient noncoherent trellis-coded MPSK scheme, in which a particularly designed differential encoder is added in front of the trellis encoder. With this differential encoder, trellis-coded MPSK proposed by Ungerboeck is no longer noncoherently catastrophic and thus achieves better error performance. Moreover, new trellis codes which, for the proposed scheme, have better bit error rates than Ungerboeck's codes are found by computer searches.     

Minimal transmitter complexity design of analytically describedtrellis codes

G. Ungerboeck's (1982) design rules for a class of bandlimited codes called trellis codes are reviewed. His design of the trellis is based on a set partitioning of the signal constellation, and he realized these trellis codes by a convolutional encoder followed by a mapping rule from the coder output to modulation symbols. R. Calderbank and J.E. Mazo (1984) showed how to realize trellis codes for one-dimensional signal sets in a single-step, easily derived, nonlinear transformation with memory on a sliding block of source symbols. The design rules that give a signal (state) specification in a trellis that yields the Calderbank-Mazo transformation with the smallest number of terms are presented. This gives a minimal transmitter complexity design. It is shown how to realize the Ungerboeck from the Calderbank-Mazo form, and as a result a step-by-step, search-free design procedure for trellis codes is presented. Two additional design rules are presented and applied to two examples by analytically designing two trellis codes. A simple procedure for converting an analytic code expression to a convolutional encoder realization is discussed. The analytic designs of a 4-D code and a 2-D code are presented     

Two trellis coding schemes for large free distances

A trellis code encoded by using the encoder of a convolutional code C with a short constraint length followed by an additional processing unit is equivalent to a trellis code with a large constraint-length. In 1993, Hellstern proposed a trellis coding scheme for which the processing unit consists of a delay processor and a signal mapper. With Hellstern's scheme, trellis codes with large free distances can be constructed. In this paper, we propose two trellis coding schemes. For the first scheme, the processing unit is composed of multiple pairs of delay processors and signal mappers. For the second scheme, the processing unit is composed of a convolutional processor and a signal mapper, where a convolutional processor is a rate 1 convolutional code. The trellis code constructed from each of the proposed schemes can be suboptimally decoded by using the trellis of the convolutional code C with some feedback information. Either of the proposed schemes can produce a trellis code that has a larger bound on free distance and better error performance as compared to the trellis code constructed from Hellstern's scheme based on the same convolutional code C     

On the automorphism group of various Goppa codes

We determine the automorphism group of various Goppa codes 𝒞 _L(D,G) associated with certain function fields F/F _q of genus g>0. It is well known that, for deg D=n>2g+2, the automorphism group {Aut_D,G(F/F_q) can be embedded into Aut(𝒞_L(D,G)) as a subgroup. We show that, under certain conditions on the divisors D and G Aut_D,G(F/F_q ) is actually isomorphic to Aut(𝒞_L(D,G))     

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     

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     

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