Codes based on a trellis cut-set transformation. I. Rotationallyinvariant codes

Let a trellis section 𝒯 generate a trellis code 𝒞. We study two trellis sections based on 𝒯, a “cut-set” trellis section 𝒯_cs and a “differential encoder” trellis section 𝒯_de. We show that 𝒯 can be transformed to a cut-set trellis section 𝒯_cs, which is equivalent to 𝒯 in the sense that both 𝒯 and 𝒯 _cs generate 𝒞 and both 𝒯 and 𝒯_cs have the same decoding complexity. A differential encoder trellis section is equivalent to the trellis section obtained by following 𝒯 with a differential encoder. It is shown that both 𝒯_cs and 𝒯_de have inverse transform trellis sections. A differential encoder trellis section generates a rotationally invariant (RI) code in a particularly simple and straightforward way. But an RI code need not have a differential encoder trellis section. However, for all of the RI codes examined here, we show that the cut-set trellis section can be arranged into a differential encoder trellis section. This means that these codes can be decomposed into an encoder followed by a differential encoder. Further we show that when 𝒯 is formed using a linear binary convolutional encoder and a mapping by set partitioning, then 𝒯 followed by a differential encoder gives an RI code which in some cases is as good as the best previously known codes, after applying the inverse transform to 𝒯_de     

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     

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.     

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     

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     

Design of ring convolutional trellis codes for MAP decoding of MPEG-4 images

We propose a trellis-coded modulation system using continuous-phase frequency-shift keying (CPFSK) and ring convolutional codes for transmitting the bits generated by an embedded zerotree wavelet encoder. Improved performance is achieved by using maximum a posteriori decoding of the zerotree symbols, and ring convolutional trellis codes are determined for this decoding method. The CPFSK transmitter is decomposed into a memoryless modulator and a continuous phase encoder over the ring of integers modulo 4; the latter is combined with a polynomial convolutional encoder over the same ring. In the code design process, a search is made of the combined trellis, where the branch metrics are modified to include the source transition matrix. Simulation results of image transmission are provided using the optimized system, including mismatched channel cases.     

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     

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.     

Space-time convolutional codes over GF(p) for two transmit antennas

We present new space-time trellis codes for two transmit antennas and p-PSK modulations, where p=3. 5. 7.11. 13.17, satisfying the rank and the determinant or the trace criteria. The system utilizes a rate 1/2 convolutional encoder over GF(p), p a prime. Some encoder properties are presented that simplify the code search.     

The length of a typical Huffman codeword

If p_i(i=1,···, N) is the probability of the ith letter of a memoryless source, the length l_i of the corresponding binary Huffman codeword can be very different from the value -log p_i. For a typical letter, however, l_i≈-logp_i. More precisely, P_m ^-=Σ/sub j∈{i|l<-logpj-m}/p_j<2^-m and P_m ⁺=Σ/sub j∈{i|li>-logpi+m/}p_j<2^-c(m-2)+2, where c≈2.27     

Superimposed codes based on punctured convolutional codes

Punctured convolutional codes of rates k₁/n and k₂ /n are applied to |u|u+v construction, and then a superimposed code of rate (k₁+k₂)/(2n) is constructed. A suboptimal decoding procedure is presented for the superimposed codes, and it reduces the decoding complexity as compared with maximum likelihood decoding for the known convolutional codes     

A note on type II convolutional codes

The result of a search for the world's second type II (doubly-even and self-dual) convolutional code is reported. A rate R=4/8, 16-state, time-invariant, convolutional code with free distance d_free=8 was found to be type II. The initial part of its weight spectrum is better than that of the Golay convolutional code (GCC). Generator matrices and path weight enumerators for some other type II convolutional codes are given. By the “wrap-around” technique tail-biting versions of (32, 18, 8) Type II block codes are constructed     

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     

An Upper Bound on the Minimum Distance of Serially Concatenated Convolutional Codes

This correspondence presents an upper bound on the minimum distance of serially concatenated codes with interleaver where the inner code is a systematic recursive convolutional encoder and the outer code is any convolutional encoder. The resulting expression shows that the minimum distance of the concatenated code cannot grow more than O(K¹-1/d_f ^(O)), where K is the information word length, and d_f ^(O) is the free distance of the outer code. The obtained upper bound is shown to agree with and, in some cases, improve over previously known results     

Assembled space-time turbo trellis codes

A novel full rate space-time turbo trellis code, referred to as an assembled space-time turbo trellis code (ASTTTC), is presented in this paper. For this scheme, input information binary sequences are first encoded using two parallel concatenated convolutional encoders. The encoder outputs are split into four parallel streams and each of them is modulated by a QPSK modulator. The modulated symbols are assembled by a predefined linear function rather than punctured as in the standard schemes. This results in a lower code rate and a higher coding gain over time-varying fading channels. An extended two-dimensional (2-D) log-MAP (maximum a posteriori probability) decoding algorithm, which simultaneously calculates two a posteriori probabilities (APP), is developed to decode the proposed scheme. Simulation results show that, under the same conditions, the proposed code considerably outperforms the conventional space-time turbo codes over time-varying fading channels.     

Reduced-state representations for trellis codes using constellation symmetry

This paper presents a symmetry-based technique for trellis-code state-diagram reduction that has more general applicability than the quasi-regularity technique of Rouanne et al. and Zehavi et al. for trellis codes using standard constellations and labelings. For a 2/sup /spl nu/x/-state trellis code, the new technique reduces the 2/sup 2/spl nu/x/ state diagram to 2/sup /spl nu/x+/spl nu/q/-state diagram where 0/spl les//spl nu//sub q//spl les//spl nu//sub x/. The particular value of /spl nu//sub q/ depends on the constellation labeling and the convolutional encoder. For standard rate-k/(k+1) set-partitioned trellis codes, /spl nu//sub q/=0, and the overall number of states is the same with the new technique as with quasi-regularity. For codes that are not quasi-regular (and thus not amenable to the quasi-regularity technique), the new technique often provides some improvement (when /spl nu//sub q/相似文献   

衰落信道下的格形码设计

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

一种实现高性能TCM的卷积编码器结构

本文提出了一种用于网格编码调制(TCM)技术的卷积编码器结构,并在三种不同的信号分配约束条件下对具有最大自由欧几里德距离的TCM码进行了搜索,结果表明:当状态数目较少时,Ungerboeck建议的规则是获得好码的前提条件,当状态增多时,可能存在有其它的信号分配形式达到最好的性能。