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.     

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     

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     

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.     

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     

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     

Bit-error probability for maximum-likelihood decoding of linearblock codes and related soft-decision decoding methods

In this correspondence, the bit-error probability P_b for maximum-likelihood decoding of binary linear block codes is investigated. The contribution P_b(j) of each information bit j to P_b is considered and an upper bound on P_b(j) is derived. For randomly generated codes, it is shown that the conventional approximation at high SNR P_b≈(d_H/N).P_s, where P_s represents the block error probability, holds for systematic encoding only. Also systematic encoding provides the minimum P_b when the inverse mapping corresponding to the generator matrix of the code is used to retrieve the information sequence. The bit-error performances corresponding to other generator matrix forms are also evaluated. Although derived for codes with a generator matrix randomly generated, these results are shown to provide good approximations for codes used in practice. Finally, for soft-decision decoding methods which require a generator matrix with a particular structure such as trellis decoding, multistage decoding, or algebraic-based soft-decision decoding, equivalent schemes that reduce the bit-error probability are discussed. Although the gains achieved at practical bit-error rates are only a fraction of a decibel, they remain meaningful as they are of the same orders as the error performance differences between optimum and suboptimum decodings. Most importantly, these gains are free as they are achieved with no or little additional circuitry which is transparent to the conventional implementation     

Selective trellis pruning for block codes: theory and application to iterative decoding

In this paper we present a new method to simplify trellis‐based decoding of linear block codes. Our method is based on removing (pruning) some edges and states from the trellis representation of the code; the trellis is pruned through some hard‐decisions that are made on received bits whose likelihood exceeds a predefined threshold. We show in this paper how this simplification can be accounted for by a new generator matrix (and sometimes a coset leader) that totally parametrize the new trellis, or, equivalently, the set of allowed codewords after simplification. Extensive simulations show that significant computational savings can be achieved, at a very small loss in coding performance, as long as the operating point and threshold are carefully chosen. Moreover, the application of this technique to iterative decoding of product codes is outlined, and our results show that the simplifications do not hinder the convergence, again, as long as proper parameters are chosen. Copyright © 2007 John Wiley & Sons, Ltd.     

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     

Nonhomogeneous Trellis codes for the Quasi-Synchronous Multiple-Access Binary adder channel with Two Users

A trellis code is {em homogeneous} if the number of branches emanating from each node (or state) in the trellis diagram is constant. For example, convolutional codes are linear homogeneous trellis codes. A trellis code is {em nonhomogeneous} if the number of branches emanating from each node in the trellis diagram is not the same. The two-user binary adder channel is a multiple-access channel with two binary inputs,x_{1}andx_{2}, and one ternary output,y = x_{1} + x_{2}, where the addition is done in the real number field. The adder channel is synchronous if both encoders and the decoder maintain block (frame) synchronism. It is quasi-synchronous if the encoders do not start their blocks at the same time, but the decoder knows the position of each block. The difference between the starting times of the blocks is called the slippage. The channel is asynchronous if no block synchronism exists among the encoders and the decoder. Some uniquely decodable code pairs(C_{1}, C_{2})are presented that can be used to transmit information reliably over the quasi-synchronous binary adder channel with two users. One of the codes is a nonhomogeneous trellis code, the other is a common block code. Our code rates are better than Deaett-Wolf codes and are close to or equal to the asymptotic rates of Kasami {em et al}. A method for calculating the rates of nonhomogeneous trellis codes is described. An algorithm for finding more uniquely decodable code pairs for the quasi-synchronous binary adder channel is formulated.     

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.     

Syndrome trellis codes based on minimal span generator matrix

To improve the embedding efficiency of steganography, syndrome coding based on the coding theory has attracted many researchers’ attentions. In this paper, we make use of the relationship between syndrome coding for minimizing additive distortion and maximum likelihood decoding for linear codes to analyze the main parameters of convolutional codes which influence the embedding efficiency. And, the new syndrome trellis codes based on minimal span generator matrix is proposed. It can be considered an alternative construction of the state-of-the-art syndrome trellis codes (STCs) proposed by Filler and Fridrich recently. Experimental results show that the proposed scheme owns the same embedding performance to STCs and achieve the reduced time complexity and storage requirement meanwhile.     

基于删余等效的高码率卷积码的低复杂度译码方法

根据删余卷积码具有较低的译码复杂度这一特征,提出了一种适用于普通高码率卷积码的低复杂度译码方法。通过多项式生成矩阵表示法,推导了删余卷积码的等效多项式生成矩阵,给出了等效多项式生成矩阵的计算准则。在分析删余卷积码与相同码率普通卷积码的等效关系和区别的基础上,提出了高码率卷积码的删余等效并给出了计算高码率卷积码删余等效后原始码和删余矩阵的方法。以原始码和删余矩阵构成的删余等效结构为译码基础,实现了高码率卷积码的低复杂度译码,其译码复杂度与原始码相当。仿真结果表明,删余等效译码方法相对于正常译码方法,其性能损失很小。     

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     

Generalized punctured convolutional codes

This letter introduces the class of generalized punctured convolutional codes (GPCCs), which is broader than and encompasses the class of the standard punctured convolutional codes (PCCs). A code in this class can be represented by a trellis module, the GPCC trellis module, whose topology resembles that of the minimal trellis module. he GPCC trellis module for a PCC is isomorphic to the minimal trellis module. A list containing GPCCs with better distance spectrum than the best known PCCs with same code rate and trellis complexity is presented.     

Bandwidth efficient parallel concatenated coding schemes

The authors propose a solution to the parallel concatenation of trellis codes with multilevel amplitude/phase modulations and a suitable iterative decoding structure. Examples are given for throughputs 2bit/s/Hz with 8PSK and 16QAM signal constellations. For parallel concatenated trellis codes in the examples, rate 2/3 and 4/5, 16-state binary convolutional codes with Gray code mapping are used. The performances of these codes are within 1 dB of the Shannon limit at a bit error probability of 10^-6 for a given throughput. This outperforms all codes reported in the past for the same throughput     

A new high rate code scheme with highly parallel and low complexity decoding algorithm

A new high rate code scheme is proposed in this paper. It consists of serial concatenated recursive systematic ordinary (nonpunctured) convolutional codes with only 8 states in the trellis of the corresponding reciprocal dual codes. With a low complexity and highly parallel decoding algorithm, over additive white Gaussian noise channels, the proposed codes can achieve good bit error rate (BER) performance comparable to that of turbo codes and low density parity check (LDPC) codes. At code rate R=16/17, the overall decoding complexity of the proposed code scheme is almost half that of the LDPC codes.     

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.     

Good trellises for IC implementation of Viterbi decoders for linearblock codes

This paper investigates trellis structures of linear block codes for the integrated circuit (IC) implementation of Viterbi decoders capable of achieving high decoding speed while satisfying a constraint on the structural complexity of the trellis in terms of the maximum number of states at any particular depth. Only uniform sectionalizations of the code trellis diagram are considered. An upper-bound on the number of parallel and structurally identical (or isomorphic) subtrellises in a proper trellis for a code without exceeding the maximum state complexity of the minimal trellis of the code is first derived. Parallel structures of trellises with various section lengths for binary BCH and Reed-Muller (RM) codes of lengths 32 and 64 are analyzed. Next, the complexity of the IC implementation of a Viterbi decoder based on an L-section trellis diagram for a code is investigated. A structural property of a Viterbi decoder called add-compare-select (ACS)-connectivity which is related to state connectivity is introduced. This parameter affects the complexity of wire-routing (interconnections within the IC). The effect of five parameters namely: (1) effective computational complexity; (2) complexity of the ACS-circuit; (3) traceback complexity; (4) ACS-connectivity; and (5) branch complexity of a trellis diagram on the very large scale integration (VLSI) complexity of a Viterbi decoder is investigated. It is shown that an IC implementation of a Viterbi decoder based on a nonminimal trellis requires less area and is capable of operation at higher speed than one based on the minimal trellis when the commonly used ACS-array architecture is considered     

Efficient maximum likelihood decoding of linear block codes using a trellis

It is shown that soft decision maximum likelihood decoding of any(n,k)linear block code overGF(q)can be accomplished using the Viterbi algorithm applied to a trellis with no more thanq^{(n-k)}states. For cyclic codes, the trellis is periodic. When this technique is applied to the decoding of product codes, the number of states in the trellis can be much fewer thanq^{n-k}. For a binary(n,n - 1)single parity check code, the Viterbi algorithm is equivalent to the Wagner decoding algorithm.