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     

Near constant envelope trellis shaping for PSK signaling

In this paper, we propose a powerful trellis shaping for peak-to-average power ratio (PAR) reduction of pulse-shaped phase shift keying (PSK) systems. The proposed approach consists of 1) memory extension of trellis shaping encoder for capturing the full effect of pulse shaping filter impulse response, and 2) simple branch metrics that quantify envelope fluctuation of the filter output. Simulation results demonstrate that achieving near constant envelope is possible even if a pulse shaping filter with a roll-off factor as low as 0.1 is employed. Furthermore, due to the circular nature of the resulting signal trajectory, the proposed system also exhibits a robustness against sampling timing jitter at the receiver.     

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     

Coding to reduce both PAR and PICR of an OFDM signal

The two major drawbacks in orthogonal frequency-division multiplexing (OFDM) system are high peak-to-average power ratio (PAR) and intercarrier interference (ICI) due to frequency offset errors. Several techniques proposed in the literature treat these limitations as two separate problems. We introduce the peak interference-to-carrier ratio (PICR) to measure ICI. This paper shows the existence of codes to reduce both the PAR and PICR simultaneously. The coding scheme is based on selecting only those messages with both low PAR and PICR as valid codewords. We identify those codes by computer search. As an example of an explicit construction for such codes, we construct Golay complementary repetition codes that can reduce both PAR and PICR simultaneously.     

Concatenated codes for fading channels based on recursive space-time trellis codes

We propose a class of codes which combine the principles of turbo coding and space-time trellis codes. It is first shown that several classes of space-time codes have an equivalent recursive realization. This fact is then exploited to design serial concatenated coding schemes with an outer code, interleaver, and an inner recursive space-time encoder. Two solutions are proposed in this paper - the use of convolutional outer codes aimed mainly to improve the power efficiency and the use of very high-rate outer codes to obtain significant improvement in power efficiency with a marginal decrease in spectral efficiency. We show that single parity check based turbo product codes are a good candidate for very high-rate outer codes. Finally, we propose an automatic repeat request scheme based on recursive realizations of space-time codes and show that the proposed scheme provides significant reduction in frame error rate.     

Relation between encoder and syndrome former variables and symbol reliability estimation using a syndrome trellis

We derive a linear correspondence between the variables of an encoder and those of a corresponding syndrome former. Using the derived correspondence, we show that the log-likelihood ratio of an information bit conditioned on a received sequence can be equally calculated using the syndrome trellis. It is shown that the proposed method also applies to recursive systematic convolutional codes which are typical constituent codes for turbo codes. Moreover, we show that soft-in syndrome decoding considering a priori probabilities of information bits is possible in the same way as for Viterbi decoding based on the code trellis. Hence, the proposed method can be applied to iterative decoding such as turbo decoding. We also show that the proposed method is effective for high-rate codes by making use of trellis modification.     

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     

The Design of Predictive Trellis Waveform Coders Using the Generalized Lloyd Algorithm

Trellis source codes consist of a finite-state machine decoder and a trellis search algorithm, such as the Viterbi algorithm, as the encoder. The encoder experiments with a local copy of the decoder and determines the best channel path map in the sense that it will yield the smallest average distortion between the source sequence and the reproduction sequence given the codebook. In this paper we present a coding system and a design algorithm for predictive trellis coding. Results obtained via simulation are compared for trellis and predictive trellis codes designed for first-order autoregressive sources with Gaussian and Laplacian innovations and for sampled speech. On a random source which models speech, simulation results of the predictive and nonpredictive trellis codes designed by the generalized Lloyd algorithm and those obtained by other researchers are compared. Issues related to computational complexity, the effects of initial codebook selection, training sequence segmentation, search length, channel errors, and algorithm convergence are addressed.     

New TCM codes for 4PSK-2PSK modulation

The authors present some new multi-dimensional (3-D, 4PSK-2PSK) and 180° rotationally invariant trellis codes that combined with the demodulator (which locks onto the 2PSK signal of the 3-D signal set) allows robust operation at low signal to noise ratios. Examples of the codes are presented for 2, 4, 8, 16 and 32 states. The codes achieve a coding gain of 1.76 dB (for two encoder states) to 5.44 dB (for 42 encoder states) compared to uncoded BPSK. Distance profiles of the codes are shown     

An error bound for reduced-state Viterbi decoding of TCM codes

An upper bound is given on the error event rate of reduced-state Viterbi decoding of trellis-coded modulation (TCM) codes. Such reduced-state decoding could form the heart of an adaptive-complexity approach that saves substantially on required decoding power consumption, an important consideration in handheld portable communications. The bound is based on a difference-state formulation utilizing the uniform error properties of the codes. It fully includes the effect of finite decoding depth L, and is efficiently computed with a single forward pass through the encoder trellis     

On Trellis Shaping for PAR Reduction in OFDM Systems

The application of trellis shaping was proposed to reduce the peak-to-average power ratio (PAR) of orthogonal frequency division multiplexing (OFDM) signals. In this letter, we review the trellis-shaping schemes presented in the literature, and we introduce modifications such as a new decoding metric and the use of sequential decoding. We conduct comprehensive complexity and performance comparisons for the different schemes, and one interesting result of this work is that, in terms of PAR-reduction capability, trellis shaping with time-domain metrics is generally superior to trellis shaping with frequency-domain metrics. Furthermore, the proposed modifications enable trellis shaping for PAR reduction with a flexible performance-complexity tradeoff.     

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.     

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

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

Shift-full-rank matrices and applications in space-time trellis codes for relay networks with asynchronous cooperative diversity

To achieve full cooperative diversity in a relay network, most of the existing space-time coding schemes require the synchronization between terminals. A family of space-time trellis codes that achieve full cooperative diversity order without the assumption of synchronization has been recently proposed. The family is based on the stack construction by Hammons and El Gamal and its generalizations by Lu and Kumar. It has been shown that the construction of such a family is equivalent to the construction of binary matrices that have full row rank no matter how their rows are shifted, where a row corresponds to a terminal (or transmit antenna) and its length corresponds to the memory size of the trellis code on that terminal. We call such matrices as shift-full-rank (SFR) matrices. A family of SFR matrices has been also constructed, but the memory sizes of the corresponding space-time trellis codes (the number of columns of SFR matrices) grow exponentially in terms of the number of terminals (the number of rows of SFR matrices), which may cause a high decoding complexity when the number of terminals is not small. In this paper, we systematically study and construct SFR matrices of any sizes for any number of terminals. Furthermore, we construct shortest (square) SFR (SSFR) matrices that correspond to space-time trellis codes with the smallest memory sizes and asynchronous full cooperative diversity. We also present some simulation results to illustrate the performances of the space-time trellis codes associated with SFR matrices in asynchronous cooperative communications.     

Scarce-state-transition syndrome-former error-trellis decoding of(n,n-1) convolutional codes

A novel scarce-state-transition (SST) type trellis decoding system for (n,n-1) convolutional codes with coherent BPSK signals is proposed. The new system retains the same number of binary comparisons as the syndrome-former trellis decoding technique. Like the original SST-type encoder trellis technique, the proposed system is also suitable for CMOS VLSI implementation. A combination of the two techniques results in a less complex and low power consumption decoding system     

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.     

Trellis-coded direct-sequence spread-spectrum communications

This paper considers the application of trellis coding techniques to direct-sequence spread-spectrum multiple-access (DS/SSMA) communication. The unique feature of the trellis codes considered is that they are constructed over the set of possible signature sequences rather than over some standard 2-D signal constellation. The resulting codes have a small number of signals per dimension. We present several examples of these trellis codes, and suggest possible methods of implementation. We also present a detailed error analysis for this system, which employs techniques developed by Lehnert and Pursley (1987, 1989)) to accurately model the multiple access interference. We generate numerical results for several examples and conclude that the proposed trellis coded systems yield significant performance improvements over binary antipodal DS/SSMA systems. In addition, the new trellis codes perform better than standard error control techniques with the same complexity and code rate. Analytic results are verified with simulations     

Space-Time Coded Systems using Continuous Phase Modulation

We develop space-time trellis coded (STC) schemes using continuous-phase modulation (CPM). We employ the Rimoldi model of CPM to create a decomposed model of STC-CPM. The decomposition separates the coding from the modulation. The space-time encoding and the inherent CPM encoding is combined into a single trellis encoder on the ring of integers modulo-. This is followed by a bank of memoryless modulators. The model allows the search for good space-time codes to take into account the inherent encoding of the modulation.     

Comparison of constructions of irregular Gallager codes

The low-density parity check codes whose performance is closest to the Shannon limit are “Gallager codes” based on irregular graphs. We compare alternative methods for constructing these graphs and present two results. First, we find a “super-Poisson” construction which gives a small improvement in empirical performance over a random construction. Second, whereas Gallager codes normally take N² time to encode, we investigate constructions of regular and irregular Gallager codes that allow more rapid encoding and have smaller memory requirements in the encoder. We find that these “fast encoding” Gallager codes have equally good performance     

Block-LDPC: a practical LDPC coding system design approach

This paper presents a joint low-density parity-check (LDPC) code-encoder-decoder design approach, called Block-LDPC, for practical LDPC coding system implementations. The key idea is to construct LDPC codes subject to certain hardware-oriented constraints that ensure the effective encoder and decoder hardware implementations. We develop a set of hardware-oriented constraints, subject to which a semi-random approach is used to construct Block-LDPC codes with good error-correcting performance. Correspondingly, we develop an efficient encoding strategy and a pipelined partially parallel Block-LDPC encoder architecture, and a partially parallel Block-LDPC decoder architecture. We present the estimation of Block-LDPC coding system implementation key metrics including the throughput and hardware complexity for both encoder and decoder. The good error-correcting performance of Block-LDPC codes has been demonstrated through computer simulations. With the effective encoder/decoder design and good error-correcting performance, Block-LDPC provides a promising vehicle for real-life LDPC coding system implementations.