Tail-biting turbo-code encoder and associated decoder

Details Tail-biting turbo-code encoder and associated decoder Tail-biting turbo-code encoder and associated decoder

1999-06-01

2003-03-04

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06530059

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to the field of digital communications, and is particularly concerned with improving error rate performance and increasing the transmission rate of convolutionally encoded data transmissions.
BACKGROUND OF THE INVENTION
Turbo-codes have received considerable attention in recent years due to their powerful error correcting capability, reasonable complexity, and flexibility in terms of providing different block sizes and code rates. The original paper on “Turbo-codes” was published by C. Berrou, A. Glavieux, and P. Thitamajshima and was entitled “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes”, Proceedings of ICC'93, Geneva, Switzerland, pp. 1064-1070, May, 1993. (Also, see C. Berrou, and A. Glavieux, “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes”, IEEE Trans. On Comm., Vol. 44, No. 10, October 1996 and B. Talibart and C. Berrou, “Notice Preliminaire du Circuit Turbo-Codeur/Decodeur TURBO4”, Version 0.0, June 1995, and also U.S. Pat. No. 5,446,747.) A rate ½ binary code was represented that provides performance within 0.5 dB of the antipodal signaling capacity limit at a BER of 10
−5
. The canonical Turbo encoder consisted of two rate ½ recursive systematic convolutional (RSC) encoders operating in parallel with the data bits interleaved between the two encoders. Soft-in soft-out iterative processing based on a posteriori probability (APP) decoding principles was used. This is also referred to as maximum a posteriori (MAP) decoding in the literature. The interleaver block size used was 65,536. It is practical to look at much shorter block sizes, on the order of a few hundred bits, where the overhead associated with flush bits becomes important.
A problem that was recognized early in the design of Turbo-codes is the termination of the trellises as noted by P. Robertson in “Illuminating the Structure of Code and Decoder of Parallel Concatenated Recursive systematic (Turbo) Codes”, IEEE Globecom, pp. 1298-1303, November-December, 1994. As with conventional block-oriented non-recursive convolutional codes, it is desirable to have the encoder start and stop in a known state. This is achieved for non-recursive convolutional codes by starting the encoder in a known state (usually the zero state) and then using known flush bits to terminate the encoder. The flush bits are usually zeros to force the encoder back into the zero state (zero-flush). The result is a simple decoder, with all bits well protected, but the flush bits take energy away from the data bits and also lower the code rate or bandwidth efficiency of the code. One solution to this problem is to perform tail-biting as noted by G. Solomon and H. Tilborg in “A Connection Between Block and Convolutional Codes”, SIAM J. Appl. Math, Vol. 37, No. 2, pp. 358-369, October, 1979; and by H. Ma and J. Wolf in “On Tail Biting Convolutional Codes”, IEEE Trans. on Comm., Vol. COM-34, No. 2, pp. 104-111, February, 1986. Tail biting is a technique where the constraint length k (memory k-1) encoder is initialized with the first k-1 data bits and then flushed at the end of the block with the same k-1 data bits. This eliminates the overhead associated with the flush bits. In this case the starting and ending states are the same, but unknown. Decoding requires more computations, but the increase in complexity is not significant for typical block sizes of several Viterbi decoder history depths. The usual close-to-optimal decoding approach is to decode in a circle, processing at least two extra history depths of signal as noted by Solomon and Tilborg in their previously noted work.
The termination problem is more complicated for Turbo-codes. This is because there are (at least) two trellises to be terminated and the input to the second RSC encoder is an interleaved or permuted version of the input to the first RSC encoder. The most common termination approach is to add termination bits to the end of the first uninterleaved block, resulting in termination of the first trellis, but leave the second trellis unterminated. The first encoder cannot be simply flushed with zero bits because the encoder is recursive. It is straightforward, however, to determine the termination bits required to force the encoder into a given state, such as the zero state. The required termination bits are simply the feedback bits from the RSC encoder at the time of termination.
Termination of both trellises has been achieved by P. Guinand and J. Lodge as documented in “Trellis Termination for Turbo Encoders”, Proc. 17th Biennial Symp. On Communications, Queen's University, Kingston, Canada, pp. 389-392, May 30-Jun. 1 1994. This was accomplished by determining a set of termination positions in the input that allow control of both final states and then defining the appropriate mapping to determine the bits to be inserted into these positions. Conceptually this involves running the encoder twice (at most) and does add further overhead in the form of yet more termination bits.
An alternate solution to the problem of terminating the second trellis is the so-called frame-oriented Turbo-code of C. Berrou and M. Jezequel as described in “Frame-Oriented Convolutional Turbo Codes”, Elec. Letters, Vol.32, No.15, pp. 1362-1364, July 1996. In this approach, a single trellis is used. A block of input bits, twice as long as the number of data bits, is produced by placing the data bits, in their original order, in the first half of the block and a specially interleaved or permuted copy of the data bits in the second half of the block. This block is then run through a single RSC encoder to generate the parity bits. There are some similarities between this approach and a tail-biting approach in that the flush bits are eliminated without leaving an unterminated end, but full tail biting is not performed. Also, the block size is restricted to be a multiple of the repetition period of the RSC feedback polynomial. For example, the Turbo4 encoder defined in B. Talibart and C. Berrou has a repetition period of 15. This is an undesirable restriction, and represents a significant overhead for some desired block lengths. Full tail biting in this situation would result in an increase in the code rate.
Other tail-biting methods have been mentioned in various papers such as J. Anderson and S. Hladik's “MAP Tail biting Decoders”, ISIT, Ulm, Germany, p. 224, Jun. 29-Jul. 4 1997, J. Anderson and S. Hladik's , “Tail biting MAP Decoders”, IEEE Journal on Selected Areas in Communications, Vol. 16, No. 2, pp. 297-302, February 1998, Y-P Wang, R. Ramesh, A. Hassan, and H. Koorapaty's, “On MAP Decoding for Tail-Biting Convolutional Codes”, ISIT, Ulm, Germany, p. 225, Jun. 29-Jul. 4 1997, H-A Loeliger's, “New Turbo-Like Codes”, ISIT, Ulm, Germany, p. 109, Jun. 29-Jul. 4, 1997. None of these schemes is particularly general and/or flexible. The Anderson and Hladik papers make no mention of how to implement tail-biting RSC codes or tail-biting Turbo-codes. Tail-citing Turbo-codes are mentioned in Wang, Ramesh, Hassan and Koorapaty, as well as in H-A Loeliger but these papers place restrictions on the feedback polynomial and block length of the tail-biting RSC component codes. These restrictions, though undesirable, are necessary because these codes are designed to be strictly systematic, that is, all the data bits are encoded and represented directly in the systematic output of the code.
In the following discussion, various known method of either terminating or tail biting the output of a Turbo encoder will be discussed. In the discussion, the term “symbol” will be used to refer to either a bit or an arbitrary non-binary symbol. The associated RSC and Turbo decoders are also described. One can consider the number of data or information bits per block to be K and the total number of code bits is N. Thus, the exact code rate for a block Turbo-code is always r=K/N. The memory of each RSC encoder is typically the same and given by m=k−1, where k is the RSC encoder

Affiliated with

Also associated with

Rating

Tail-biting turbo-code encoder and associated decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Tail-biting turbo-code encoder and associated decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tail-biting turbo-code encoder and associated decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3002519