Efficient algorithm for decoding layered space-time codes

Layered space-time codes have been designed to exploit the capacity advantage of multiple antenna systems in Rayleigh fading environments. A new efficient decoding algorithm based on QR decomposition is presented, which requires only a fraction of the computational effort compared with the standard decoding algorithm requiring the multiple calculation of the pseudo inverse of the channel matrix     

Efficient Forney functions for decoding AG codes

Using a Forney formula to solve for the error magnitudes in decoding algebraic-geometric (AG) codes requires producing functions σ_P, which are 0 at all but one point P of the variety of the error-locator ideal. The best such function is produced here in a reasonably efficient way from a lex Grobner basis. This lex basis is, in turn, produced efficiently from a weighted grevlex basis by using the FGLM algorithm. These two steps essentially complete the efficient decoding scheme based on a Forney formula started in the author's previous work (see ibid., vol.42, p.1263-8, 1996)     

Efficient decoding algorithms for generalized Reed-Muller codes

Previously, a class of generalized Reed-Muller (RM) codes has been suggested for use in orthogonal frequency-division multiplexing. These codes offer error correcting capability combined with substantially reduced peak-to mean power ratios. A number of approaches to decoding these codes have already been developed. Here, we present low complexity, suboptimal alternatives which are inspired by the classical Reed decoding algorithm for binary RM codes. We simulate these new algorithms along with the existing decoding algorithms using additive white Gaussian noise and two-path fading models for a particular choice of code. The simulations show that one of our new algorithms outperforms all existing suboptimal algorithms and offers performance that is within 0.5 dB of maximum-likelihood decoding, yet has complexity comparable to or lower than existing decoding approaches     

Linear programming decoding: The ultimate decoding technique for low density parity check codes

Linear programming (LP) decoding is an alternative to iterative algorithms for decoding low density parity check (LDPC) codes. Although the practical performance of LP decoding is comparable to message-passing decoding, a significant advantage is its relative amenability to nonasymptotic analysis. Moreover, there turn out to be a number of important theoretical connections between the LP decoding and standard forms of iterative decoding. These connections allow theoretical insight from the LP decoding perspective to be transferred to iterative decoding algorithms. These advantages encouraged many researchers to work in this recent decoding technique for LDPC codes. In this paper, LP decoding for LDPC code is extensively reviewed and is discussed in different segmented areas.     

Efficient multithreshold decoding of nonbinary codes

The main principles of multithreshold decoding (MTD) are generalized to nonbinary codes. The lower bounds of the probability of erroneous decoding are proposed. The nonbinary MTD efficiency is shown to be close to the values attained via optimum search methods that cannot usually be implemented for nonbinary codes. The complexity of the implementation of the proposed decoders is discussed.     

Loosely coupled memory-based decoding architecture for low density parity check codes

Parallel decoding is required for low density parity check (LDPC) codes to achieve high decoding throughput, but it suffers from a large set of registers and complex interconnections due to randomly located 1's in the sparse parity check matrix. This paper proposes a new LDPC decoding architecture to reduce registers and alleviate complex interconnections. To reduce the number of messages to be exchanged among processing units (PUs), two data flows that can be loosely coupled are developed by allowing duplicated operations. In addition, intermediate values are grouped and stored into local storages each of which is accessed by only one PU. In order to save area, local storages are implemented using memories instead of registers. A partially parallel architecture is proposed to promote the memory usage and an efficient algorithm that schedules the processing order of the partially parallel architecture is also proposed to reduce the overall processing time by overlapping operations. To verify the proposed architecture, a 1024 bit rate-1/2 LDPC decoder is implemented using a 0.18-/spl mu/m CMOS process. The decoder runs correctly at the frequency of 200 MHz, which enables almost 1 Gbps decoding throughput. Since the proposed decoder occupies an area of 10.08 mm/sup 2/, it is less than one fifth of area compared to the previous architecture.     

Efficient maximum-likelihood decoding of spherical lattice codes

A new framework for efficient exact Maximum- Likelihood (ML) decoding of spherical lattice codes is developed. It employs a double-tree structure: The first is that which underlies established tree-search decoders; the second plays the crucial role of guiding the primary search by specifying admissible candidates and is our present focus. Lattice codes have long been of interest due to their rich structure, leading to decoding algorithms for unbounded lattices, as well as those with axis-aligned rectangular shaping regions. Recently, spherical Lattice Space-Time (LAST) codes were proposed to realize the optimal diversity-multiplexing tradeoff of MIMO channels. We address the so-called boundary control problem arising from the spherical shaping region defining these codes. This problem is complicated because of the varying number of candidates to consider at each search stage; it is not obvious how to address it effectively within the frameworks of existing decoders. Our proposed strategy is compatible with all sequential tree-search detectors, as well as auxiliary processing such as the MMSEGDFE and lattice reduction. We demonstrate the superior performance and complexity profiles achieved when applying the proposed boundary control in conjunction with two current efficient ML detectors and show an improvement of 1dB over the state-of-the-art at a comparable complexity.     

Efficient maximum-likelihood decoding of Q-ary modulatedReed-Muller codes

We derive an efficient soft-decision maximum-likelihood decoding algorithm for a class of Q-ary phase-shift keyed peak-to-average power ratio limited codes for orthogonal frequency division modulation, by generalizing the fast Hadamard transform decoding of first-order Reed-Muller codes     

Low-density parity check codes and iterative decoding for long-haul optical communication systems

A forward-error correction (FEC) scheme based on low-density parity check (LDPC) codes and iterative decoding using belief propagation in code graphs is presented in this paper. We show that LDPC codes provide a significant system performance improvement with respect to the state-of-the-art FEC schemes employed in optical communications systems. We present a class of structured codes based on mutually orthogonal Latin rectangles. Such codes have high rates and can lend themselves to very low-complexity encoder/decoder implementations. The system performance is further improved by a code design that eliminates short cycles in a graph employed in iterative decoding.     

Sequential message-passing decoding of LDPC codes by partitioning check nodes

In this paper, we analyze the sequential message- passing decoding algorithm of low-density parity-check (LDPC) codes by partitioning check nodes. This decoding algorithm shows better bit error rate (BER) performance than the conventional message-passing decoding algorithm, especially for the small number of iterations. Analytical results indicate that as the number of partitioned subsets of check nodes increases, the BER performance is improved. We also derive the recursive equations for mean values of messages at check and variable nodes by using density evolution with a Gaussian approximation. From these equations, the mean values are obtained at each iteration of the sequential decoding algorithm and the corresponding BER values are calculated. They show that the sequential decoding algorithm converges faster than the conventional one. Finally, the analytical results are confirmed by the simulation results.     

Efficient heuristic search algorithms for soft-decision decoding oflinear block codes

Efficient new algorithms are presented for maximum-likelihood and suboptimal soft-decision decoding algorithms for linear block codes. The first algorithm, MA*, improves the efficiency of the A* decoding algorithm, conducting the heuristic search through a code tree while exploiting code-specific properties. The second algorithm, H*, reduces search space by successively estimating the cost of the minimum-cost codeword with a fixed value at each of the most reliable and linearly independent components of the received message. The third algorithm, directed search, finds the codeword closest to the received vector by exploring a continuous search space. The strengths of these three algorithms are combined in a hybrid algorithm, applied to the (128,64), the (256,131), and the (256,139) binary-extended Bose-Chaudhuri-Hocquenghem (BCH) codes. Simulation results show that this hybrid algorithm can efficiently decode the (128,64) code for any signal-to-noise ratio, with near-optimal performance. Previously, no practical decoder could have decoded this code with such a performance for all ranges of signal-to-noise ratio     

Near optimum universal belief propagation based decoding oflow-density parity check codes

In this paper, we propose a belief-propagation (BP)-based decoding algorithm which utilizes normalization to improve the accuracy of the soft values delivered by a previously proposed simplified BP-based algorithm. The normalization factors can be obtained not only by simulation, but also, importantly, theoretically. This new BP-based algorithm is much simpler to implement than BP decoding as it requires only additions of the normalized received values and is universal, i.e., the decoding is independent of the channel characteristics. Some simulation results are given, which show this new decoding approach can achieve an error performance very close to that of BP on the additive white Gaussian noise channel, especially for low-density parity check (LDPC) codes whose check sums have large weights. The principle of normalization can also be used to improve the performance of the max-log-MAP algorithm in turbo decoding, and some coding gain can be achieved if the code length is long enough     

Iterative decoding of parallel and serial concatenated single parity check product codes

An efficient, iterative soft-in-soft-out decoding scheme is employed for the parallel and serially concatenated single parity check (SPC) product codes, which has very low complexity, requiring only two addition-equivalent-operations per information bit. For a rate 0.8637 of parallel concatenated SPC product code, a performance of BER=10/sup -5/ at E/sub b//N/sub 0/=3.66 dB can be achieved using this decoding scheme, which is within 1 dB from the Shannon limit.     

Efficient optimal decoding of linear block codes (Corresp.)

An optimal soft decision (maximum likelihood) decoding scheme for linear block codes is described which works in the code domain and is relatively simple. It can be simplified further by considering more channel measurement information. Furthermore, optimal decoder complexity can be traded for asymptotically optimum performance.     

Error-correcting codes for list decoding

In the list-of-L decoding of a block code the receiver of a noisy sequence lists L possible transmitted messages, and is in error only if the correct message is not on the list. Consideration is given to (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding. New geometric relations between the number of errors corrected under list-of-1 decoding and the (larger) number corrected under list-of-L decoding of the same code lead to new lower bounds on the maximum rate of (n,e,L) codes. They show that a jammer who can change a fixed fraction p<1/2 of the bits in an n-bit linear block code cannot prevent reliable communication at a positive rate using list-of- L decoding for sufficiently large n and an L⩽n. The new bounds are stronger for small n , but weaker for fixed e/n in the limit of large n and L than known random coding bounds     

Existence and uniqueness of the solution for turbo decoding of parallel concatenated single parity check codes

We consider turbo decoding of parallel concatenated single parity check (SPC) (K+1,K) codes, with row-column interleaving. The existence and uniqueness of the asymptotic probability density evaluated with the turbo algorithm is proved for every length K and every signal-to-noise ratio (SNR).     

性能接近最优的LDPC码LLR-BP简化译码算法

讨论了LDPC码的LLR-BP译码算法,对多项式拟合和偏移量近似两种简化算法进行了研究,通过仿真的方法确定了近似参数;算法仿真结果表明,这两种简化算法不仅易于硬件实现,而且性能接近最优。     

Efficient maximum-likelihood decoding of LDPC codes over the binary erasure channel

We propose an efficient maximum-likelihood (ML) decoding algorithm for decoding low-density parity-check (LDPC) codes over the binary-erasure channel (BEC). We also analyze the computational complexity of the proposed algorithm.     

Efficient computer decoding of pseudorandom radar signal codes (Corresp.)

A method is presented that decreases the number of instructions needed to decode a pseudorandom phase-coded radar signal. The efficiency of this method increases exponentially as a function of the code length.