Rate k/(k+1) punctured convolutional encoders

G.D. Forney (1970, 1975) defined a minimal encoder as a polynomial matrix G such that G generates the code and G has the least constraint length among all generators for the code. Any convolutional code can be generated by a minimal encoder. High-rate k(k+1) punctured convolutional codes were introduced to simplify Viterbi decoding. An ordinary convolutional encoder G can be obtained from any punctured encoder. A punctured encoder is minimal if the corresponding ordinary encoder G is minimal and the punctured and ordinary encoders have the same constraint length. It is shown that any rate k/(k+1), noncatastrophic, antipodal punctured encoder is a minimal encoder.<>     

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     

Quaternary Convolutional Codes From Linear Block Codes Over Galois Rings

From a linear block code B over the Galois ring GR(4, m) with a k times n generator matrix and minimum Hamming distance d, a rate-k/n convolutional code over the ring Z₄ with squared Euclidean free distance at least 2d and a nonrecursive encoder with memory at most m - 1 is constructed. When the generator matrix of B is systematic, the convolutional encoder is systematic, basic, noncatastrophic and minimal. Long codes constructed in this manner are shown to satisfy a Gilbert-Varshnmov bound.     

On the structure of convolutional and cyclic convolutional codes

Algebraic convolutional coding theory is considered. It is shown that any convolutional code has a canonical direct decomposition into subcodes and that this decomposition leads in a natural way to a minimal encoder. Considering cyclic convolutional codes, as defined by Piret, an easy application of the general theory yields a canonical direct decomposition into cyclic subcodes, and at the same time a canonical minimal encoder for such codes. A list of pairs(n,k)admitting completely proper cyclic(n, k)-convolutional codes is included.     

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.     

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     

Improved Frey Chaotic Digital Encoder for Trellis-Coded Modulation

In this brief, nonlinear digital filters with finite precision are analyzed as recursive systematic convolutional (RSC) encoders. An infinite-impulse-response (IIR) digital filter with finite precision (wordlength of N bits) is a rate-1 RSC encoder over a Galois field GF(2N). The Frey chaotic filter is analyzed for different wordlengths N, and it is demonstrated that the trellis performances can be enhanced by proper filter design. Therefore, a modified definition for the encoding rate is provided, and a trellis design method is proposed for the Frey filter, which consists of reducing the encoding rate from 1 to 1/2. This trellis optimization partially follows Ungerboeck's rules, i.e., increasing the performances of the encoded chaotic transmission in the presence of noise. In fact, it is demonstrated that for the same spectral efficiency, the modified Frey encoder outperforms the original Frey encoder only for N = 2. To show the potential of these nonlinear encoders, it is demonstrated that a particular nonlinear digital filter over GF(4) is equivalent to a GF(2) conventional optimum RSC encoder. The symbol error rate (SER) is estimated for all the proposed schemes, and the results show the expected coding gains as compared to their equivalent nonencoded and linear versions.     

Convolutional codes I: Algebraic structure

A convolutional encoder is defined as any constant linear sequential circuit. The associated code is the set of all output sequences resulting from any set of input sequences beginning at any time. Encoders are called equivalent if they generate the same code. The invariant factor theorem is used to determine when a convolutional encoder has a feedback-free inverse, and the minimum delay of any inverse. All encoders are shown to be equivalent to minimal encoders, which are feedback-free encoders with feedback-free delay-free inverses, and which can be realized in the conventional manner with as few memory elements as any equivalent encoder, Minimal encoders are shown to be immune to catastrophic error propagation and, in fact, to lead in a certain sense to the shortest decoded error sequences possible per error event. In two appendices, we introduce dual codes and syndromes, and show that a minimal encoder for a dual code has exactly the complexity of the original encoder; we show that systematic encoders with feedback form a canonical class, and compare this class to the minimal class.     

Error-trellises for convolutional codes .I. Construction

An error-trellis is a directed graph that represents all the sequences belonging to the coset which contains the symbol-by-symbol detected version of a given received sequence. A modular construction of error-trellises for an (n,k) convolutional code over GF(q) is presented. The trellis is designed on the basis of partitioning the scalar check matrix of the code into submatrices of l rows, accompanied with a corresponding segmentation of the syndrome. The value of the design parameter l is an essentially unconstrained multiple of n-k. For all the cosets of the code, the sections of the error-trellis are drawn from a collection of only q^l modules; the module for each section is determined by the value of the associated syndrome segment. In case the construction is based on a basic polynomial check matrix, either canonical or noncanonical, then the error-trellis is minimal in the sense that σ⩽μ, where σ is the dimension of the state space of the trellis and μ is the constraint length of a canonical generator matrix for the code. For basic check matrices with delay-free columns, the inequality reduces to σ=μ     

A new characterization of canonical convolutional encoders (Corresp.)

A realization of a linear sequential circuit is called a canonical convolutional encoder if its state space has the smallest dimension among all realizations generating the same code. We give conditions for a realization to be a canonical oncoder and for two canonical encoders to generate the same code. The techniques used provide an enumeration of canonical encoders whose realizations are not isomorphic.     

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     

Catastrophic continuous phase modulation schemes and theirnoncatastrophic equivalents

Continuous phase modulation (CPM) schemes are bandwidth and energy efficient constant-envelope modulation schemes that can be viewed as a continuous-phase encoder (CPE) followed by a memoryless modulator (MM), where the CPE is of convolutional type. It is observed that CPM schemes can be catastrophic in the sense that pairs of input sequences that differ in an infinite number of positions can be mapped into pairs of signals with finite Euclidean distance. This can happen in spite of the fact that the CPE is never catastrophic when considered as a stand alone convolutional encoder. The necessary and sufficient condition for a general CPM scheme to be catastrophic is given. Each member of the two major families of CPM schemes, namely the LREC and the LRC, has been classified as a catastrophic or noncatastrophic scheme. For the catastrophic schemes, the probability that a catastrophic event occurs is determined. A canonical precoder which transforms each scheme of both families into an equivalent noncatastrophic scheme is derived. The equivalent noncatastrophic scheme has the same number of states as the original one. Moreover, it has the property that if two input sequences differ in the ith position, the corresponding output signals have nonzero Euclidean distance in the ith interval     

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     

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.     

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     

Minimal syndrome formers for group codes

Given a controllable group code, it has been shown by Forney (1970, 1973), Trott, and Loeliger (1994) that it is possible to construct a canonical encoder whose state space coincides with the canonical state space of the code, that is the essential element determining the minimal trellis of the code. The construction of such an encoder is based on the concept of controllability granule. In this paper the construction of a syndrome former for an observable group code is proposed. This syndrome former exhibits analogous properties of the above mentioned canonical encoder and, in particular, its state space coincides with the canonical state space of the code. The proposed construction is based on the concept of observability granule, introduced by Forney and Trott (1993), which dualizes the concept of controllability granule. Similarly to what happens for the encoders, each observability granule produces a map and all these maps together provide the syndrome former. The main difference is that here, to achieve the right state-space dimension, the automata associated with these maps do not evolve independently from each other, but are coupled according to a triangular structure     

Sphere-packing bounds for convolutional codes

We introduce general sphere-packing bounds for convolutional codes. These improve upon the Heller (1968) bound for high-rate convolutional codes. For example, based on the Heller bound, McEliece (1998) suggested that for a rate (n - 1)/n convolutional code of free distance 5 with /spl nu/ memory elements in its minimal encoder it holds that n /spl les/ 2/sup (/spl nu/+1)/2/. A simple corollary of our bounds shows that in this case, n < 2/sup /spl nu//2/, an improvement by a factor of /spl radic/2. The bound can be further strengthened. Note that the resulting bounds are also highly useful for codes of limited bit-oriented trellis complexity. Moreover, the results can be used in a constructive way in the sense that they can be used to facilitate efficient computer search for codes.     

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.     

Space-time code design for CPFSK modulation over frequency-nonselective fading channels

We derive a novel space-time code (STC) design criterion for continuous-phase frequency-shift keying (CPFSK) over frequency-nonselective fading channels. Our derivation is based on a specific matrix that is related to the input symbols of the CPFSK modulators. With this code-design criterion, we propose a simple interleaved space-time encoding scheme for CPFSK modulation over frequency-nonselective correlated fading channels to exploit potential temporal and spatial diversity advantages. Such an encoding scheme consists of a ring convolutional encoder and a spatial encoder, between which a convolutional interleaver is placed. A decoding algorithm that generates symbol metrics for the Viterbi decoder of convolutional codes from the spatial modulation trellis is examined. Simulation results confirm that the advantages of the combination of the interleaved convolutional encoding (for temporal diversity) and the spatial encoding (for spatial diversity) are promising for various system parameters.     

Codes on graphs: constraint complexity of cycle-free realizations of linear codes

Cycle-free graphical realizations of linear codes generalize trellis realizations. Given a linear code C and a cycle-free graph topology, there exists a well-defined minimal realization for C on that graph in which each constraint is a linear code with a well-defined length and dimension. The constraint complexity of the realization is defined as maximum dimension of any constraint code. There exists a graph that minimizes constraint complexity in which all internal nodes have degree 3 and all interface nodes have degree 2, and which moreover can be put in the form of a "tree-structured trellis realization." The constraint complexity of a general cycle-free graph realization can be less than that of any conventional trellis realization, but not by very much. Such realizations can yield reductions in decoding complexity even when they do not reduce constraint complexity.