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.     

On the BCJR trellis for linear block codes

In this semi-tutorial paper, we will investigate the computational complexity of an abstract version of the Viterbi algorithm on a trellis, and show that if the trellis has e edges, the complexity of the Viterbi algorithm is Θ(e). This result suggests that the “best” trellis representation for a given linear block code is the one with the fewest edges. We will then show that, among all trellises that represent a given code, the original trellis introduced by Bahl, Cocke, Jelinek, and Raviv in 1974, and later rediscovered by Wolf (1978), Massey (1978), and Forney (1988), uniquely minimizes the edge count, as well as several other figures of merit. Following Forney and Kschischang and Sorokine (1995), we will also discuss “trellis-oriented” or “minimal-span” generator matrices, which facilitate the calculation of the size of the BCJR trellis, as well as the actual construction of it     

关于几类线性分组码网格图复杂度的研究

本文研究了几类线性分组码C[n,k,d]的网格图复杂度s（C）。给出并证明了码长为奇数的两类线性分组码的网格图复杂度。同时得出了有关可纠t个错的本原BCH码[2^m-1,2^m-1-mt]及其扩展本在BCH码的网格图复杂度的若干结论。从而避免了必须先寻找码的直和结构才可得到码的网格图复杂度的较好上界。     

Reduced-search soft-decision trellis coding of linear block codes (Corresp.)

Algorithms for the soft-decision decoding of linear block codes are presented. These algorithms perform a reduced complexity search through a trellis derived from the parity check matrix of an(n, k)linear block code. The computational complexity of the algorithms is considerably reduced from that of a full maximum-likelihood algorithm. We demonstrate the trade-off between complexity and efficiency of the algorithms through computer simulation.     

MAP algorithms for decoding linear block codes based onsectionalized trellis diagrams

The maximum a posterioriprobability (MAP) algorithm is a trellis-based MAP decoding algorithm. It is the heart of turbo (or iterative) decoding that achieves an error performance near the Shannon limit. Unfortunately, the implementation of this algorithm requires large computation and storage. Furthermore, its forward and backward recursions result in a long decoding delay. For practical applications, this decoding algorithm must be simplifled and its decoding complexity and delay must be reduced. In this paper, the MAP algorithm and its variation's, such as log-MAP and max-log-MAP algorithms, are first applied to sectionalized trellises for linear block codes and carried out as two-stage decodings. Using the structural properties of properly sectionalized trellises, the decoding complexity and delay of the MAP algorithms can be reduced. Computation-wise optimum sectionalizations of a trellis for MAP algorithms are investigated. Also presented in this paper are bidirectional and parallel MAP decodings     

Soft decision decoding of block codes using received signalenvelope in digital mobile radio

The codeword error rate (WER) performance of noncoherent frequency-shift keying with soft decision decoding of block codes using Chase's second algorithm (1972) is investigated in a Rayleigh fading channel. The received signal envelope is sampled and used as channel measurement information. The theoretical upper and lower bounds of the WER are derived, assuming independent Rayleigh envelope samples in a received block. When the Golay (23, 12, 7) code is used, soft decision decoding with 6-bit error correction capability (3-bit error and 3-bit erasure) requires an average signal-to-noise power ratio about 5 dB lower than that for minimum distance decoding with 3-bit error correction to obtain a WER=10^-3. The effects of bit interleaving on the WER performance when fading envelope variation is slow compared to the bit rate are investigated through computer simulations     

Better phase-modulation error performance using trellis phase codes

We construct phase codes for use in phase- and frequency-shift modulation. A trellis structure allows simple decoding using the Viterbi algorithm. Even short codes give a large improvement in error performance.     

Two-stage maximum likelihood estimation for diversity combining indigital mobile radio

For space diversity, it is shown that it is related to maximal-ratio combining (MRC). Unlike MRC, it allows the receiver to collect diversity signals without gain adjustments or cophasing. Some worst-case bit error rate (BER) simulation results that show the influence of time delay spread, Doppler, shadow loss, and diversity for a seven-cell cluster using quadrature modulation are presented     

Iterative maximum-likelihood trellis decoding for block codes

An iterative trellis search technique is described for the maximum-likelihood (ML) soft decision decoding of block codes. The proposed technique derives its motivation from the fact that a given block code may be a subcode for a parent code whose associated trellis has substantially fewer edges. Through the use of list-Viterbi (1967) decoding and an iterative algorithm, the proposed technique allows for the use of a trellis for the parent code in the ML decoding of the desired subcode. Complexity and performance analyses, as well as details of potential implementations, indicate a substantial reduction in decoding complexity for linear block codes of practical length while achieving ML or near-ML soft decision performance     

Performance comparison of space-time block and trellis codes in the MIMO land mobile satellite channels

Due to the crowded orbits and shortage of frequency resources, the use of MIMO technology to improve spectrum efficiency and an increase of the capacity have become a necessary trend of broadband satellite communication. Firstly, we analyze the main influenced factors and compare the bit error rate (BER) performance of space-time block code (STBC) scheme and space-time trellis code (STTC) scheme. Then we build up the model of land mobile satellite (LMS) channel under different environments by using 3-state Markov chain. This paper emphatically studies the BER performance of STTC and STBC in the MIMO satellite channel. The main emphasis is placed on the effects of different factors, such as terminal environment and elevation angles, on the BER performance of STBC and STTC schemes. Simulation results indicate that performance of STTC in Rayleigh channel is obviously improved with the increasing number of transmitting and receiving antennas, but the encoder state has little impact on the performance. In the Rayleigh channel, the performance of Alamouti code is better than that of STTC. In the LMS channel, performance of these two kinds of space-time coding in open area is optimal, and in the urban area it is the worst. Nevertheless, performance of STTC is slightly superior to the performance of STBC under different circumstances. Under the same environmental conditions, BER of STBC and STTC reduces with the increase of the satellite altitude angle, and therefore, the BER curves of STTC fall faster.     

Multilevel construction of block and trellis group codes

The theory of group codes has been shown to be a useful starting point for the construction of good geometrically uniform codes. In this paper we study the problem of building multilevel group codes, i.e., codes obtained combining separate coding at different levels in such a way that the resulting code is a group code. A construction leading to multilevel group codes for semi-direct and direct products is illustrated. The codes that can be obtained in this way are identified. New geometrically uniform Euclidean-space codes obtained from multilevel codes over abelian and nonabelian groups are presented     

Enhanced trellis extracted synchronisation for block codes usinginterleavers

Previously, trellis extracted synchronisation techniques (TEST) have been presented as a purely digital method of providing bit/symbol and word synchronisation for block codes using auxiliary data obtained through trellis decoding. One of the factors affecting the complexity of the algorithm has been that any cyclic properties within the code must be countered by building confidence in a particular synchronisation point. This problem is further exasperated by a long sequence of the all-zeros (or all-ones) codeword, which presents all cyclic shifts as valid codewords. The novel algorithm presented in this Letter uses an interleaver with an inversion to overcome these two problems and significantly reduce the complexity without reducing performance     

Decoding linear block codes for minimizing word error rate (Corresp.)

Two modifications of the basic correlation decoding approach are presented. One of them yields a nonexhaustive optimum word decoding algorithm whose complexity depends upon the "projecting" structure of the code. This algorithm is then modified to yield a second decoding algorithm which, while not optimum, has simpler complexity. Applications to the AWGN channel are discussed and performance curves are given for (24, 12) and (31, 15) codes.     

On the error performance analysis of space-time trellis codes

We present analytical performance results for space-time trellis codes over spatially correlated Rayleigh fading channels. Bit-error-probability estimates are obtained based on the derivation of an exact pairwise error probability expression using a residue technique combined with a characteristic function approach. We investigate both quasi-static and interleaved channels and demonstrate how the spatial fading correlation affects the performance of space-time codes over these two different channel models. Simulation results are also included to confirm the accuracy of analytical estimates.     

Performance of GMSK frequency detection with soft decision decoding of block codes using Chase's second algorithm in mobile radio channel

Investigates bit error rate (BER) performance of a GMSK frequency detection system. The channel measurement information (CMI) for a bit in the received block is calculated from samples of the received signal envelope (R/sub s/) and the demodulator output (eye level). The CMIs of eye level*R/sub s/ and of R/sub s//sup 2/ are investigated, and the decoding performances for the CMIs are compared using the Hamming (7, 4) code in nonfading (static) and fading channels in laboratory experiments.<>     

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/相似文献   

The ABCs of linear block codes

The basic principles of block codes are presented with illustrations to visualize the concepts of vector spaces and subspaces. Intuitive explanations of goals, capabilities, and limitations of codes are offered. An important subclass of block codes called cyclic codes is examined. Their algebraic structure is described and looked at the very popular BCH and R-S cyclic codes. In addition, the newest techniques, turbo codes and LDPC codes, that use iterative decoding to obtain performance exceedingly close to theoretical limitations.     

An analytical method for approximate performance evaluation of binary linear block codes

An analytical method for approximate performance evaluation of binary linear block codes using an additive white Gaussian noise channel model with binary phase-shift keying modulation is presented. We focus on the probability density function of the bit log-likelihood ratio (LLR), which is expressed in terms of the Gram-Charlier series expansion. This expansion requires knowledge of the statistical moments of the bit LLR. We introduce an analytical method for calculating these moments. This is based on some recursive calculations involving certain weight enumerating functions of the code. It is proved that the approximation can be as accurate as desired, if we use enough terms in the Gram-Charlier series expansion. Numerical results are provided for some examples, which demonstrate close agreement with simulation results.     

A comparison of turbo codes using different trellis terminations

This paper investigates the incidence of trellis termination on the performance of turbo codes and accounts for the performance degradation often experienced in the absence of trellis termination. Analytical upper bounds on the performance for the ensemble of turbo codes using different trellis termination strategies as well as performance results obtained by computer simulation are presented. In the case of uniform interleaving, the performance differences between various termination methods are relatively small, except when using no trellis termination at all.     

Exact performance analysis of linear block codes in frequency-hopspread spectrum communication systems

We present a framework for determining the exact decoder error and failure probabilities for linear block codes in a frequency-hop communication channel with an arbitrary number of conditional symbol error and erasure probabilities. Applications are demonstrated for type-I hybrid ARQ systems by deriving equations for the packet error probability and throughput. Because these quantities are too small to be obtained by simulation, the framework provides exact results which are unobtainable by previous work