Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-05-25
2004-04-27
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S787000
Reexamination Certificate
active
06728927
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to methods of data encoding and decoding for error correction, and more particularly to interleaving for turbo-codes.
BACKGROUND OF THE INVENTION
With the advent of modern information theory and the definition of Shannon's Limit it was determined that any given noisy communications channel has a finite, non-zero threshold above which a message cannot be transmitted with a guarantee of error free transmission. The establishment of Shannon's Limit was what is considered an existence proof, that is, it establishes that a coding method can be derived that reaches the defined limits for communicating over a noisy channel, but does not show how such a code may be derived.
In 1993, in a paper by C. Berrou, A. Glavieux, and P. Thitimajshima entitled “Near Shannon Limit Error Correcting Coding ad Decoding: Turbo Codes”, Proceedings of ICC'93, Geneva, Switzerland, pp. 1064-1070, May 1993, a new communications scheme referred to as turbo coding was disclosed. This communications code offered transmissions near Shannon's Limit, as has in the ensuing years been modified numerous times to eke out any last performance advantage. Turbo codes (TC), like many other codes, used controlled redundant information, and interleaving to allow a decoder to correct for noise induced errors. The attention paid to turbo codes since 1993 is related to their powerful error correcting capability, reasonable complexity, and flexibility in terms of providing different block sizes and code rates.
One common turbo-code encoder consists of two 16-state, rate ½ recursive systematic convolutional (RSC) encoders operating in parallel with be data bits interleaved between the two encoders, as shown in FIG.
1
.
FIG. 1
illustrates a standard turbo code encoder
100
, with a data stream d
i
, which is provided to the modulator (not shown), RSC
1
102
, and the interleaver
104
. The interleaver reorders the bits of data stream d
i
according to a predetermined set of indices, and provides its output to RSC
2
106
. The outputs of RSC
1
102
and RSC
2
106
c
i
1
and c
i
2
respectively are sets of parity bits that are provided to a standard puncturing unit
108
, whose output is provided to a modulator (not shown). The feedback and feedforward polynomials used herein are (23, 35) octal, respectively. Other polynomials and number of states could also be used. Without puncturing, the overall code rate is ⅓. This is because the systematic data bits, d
i
, are only included once. Higher code rates can be achieved by puncturing the code parity bits c
i
1
and c
i
2
. (In some cases it can be beneficial to puncture a small number of systematic data bits, d
i
, to improve flare performance, as will be shown.) Good interleaver spreading properties are desirable for both fast convergence and good distance properties. High (Hamming) distance is desirable for both lowering the so-called “error floor” or are and for making the flare as steep as possible. Hamming distance is the minimum number of symbols in a block that must be changed for a first codeword to become a second codeword. The further apart two blocks are, the more a block can be corrupted while retaining the ability for the decoder to properly decode the message. It is also important to reduce the number of codewords at or near the minimum distance.
RSC codes are often terminated with flush bits. Flush bits are employed because they increase the Hamming distance between codewords. The cost of the introduction of flush bits is a penalty in the code rate. A method of obtaining the benefits of the increased distances found in terminated RSC codes without the code rate penalty is to encode the RSC code in a circle. This technique is referred to as tail-biting. Tail-biting increases the distances of an RSC code without employing flush bits. If both RSC codes in a turbo encoder are either terminated or tail-biting the encoder is described as either dual terminating or dual tail-biting as the case may be. Though the design of dual terminating or dual tail-biting encoders must account for the presence of an interleaver, the design of the interleaves need not be varied.
Interleaving is a practice well known in the art. It is a method of arranging or permuting the elements within a block. In a turbo-code encoder the elements are typically data bits or data symbols. In a turbo-code decoder the data elements are typically soft data samples from the receiver.
Interleaving is a key component of turbo-codes, as shown in FIG.
1
. Two interleavers that have been commonly investigated are the “random” interleaver and the so-called “S-random” or “spread” interleaver. The random interleaver simply performs a random or pseudo-random permutation of the elements without any restrictions.
Golden relative prime, golden, and dithered golden interleavers have previously been applied to the design of turbo-codes. Good error rate performance has been reported for small to medium sized blocks (on the order of 1000 data bits). These interleavers can be generated quickly and have excellent spreading properties. Even though the worst-case low-distance codewords are usually eliminated golden interleavers can still produce a large number of low-distance codewords, related to the regular structure of the interleaver.
Another recent interleaver design method tries to select the interleaver indexes by minimizing the correlation between the extrinsic inputs. Not surprisingly, the designed interleavers tend to have high-spread characteristics. It is also true in general that interleaves with high-spread characteristics tend to produce extrinsic values with low correlation. This is because the new definition of spread is inherently well matched to providing low extrinsic correlation.
FIG. 2
illustrates the components of a conventional interleaver
104
in the context of the encoder
100
. The input of the interleaver is stored in a memory
110
, which is at least as large as the interleaver block size (K symbols). An indexing engine
112
, re-orders the symbols stored in the memory
110
according to the order provided by the indices
114
. The re-ordered symbols are stored in memory
116
and provided as output. In some cases the interleaver can provide the re-ordered symbols directly without the need for memory
116
.
The following is a general review of S-random interleavers. Interleavers can be defined and implemented in a number of different ways.
FIG. 3
shows the definition used herein. The interleaver reads from a vector of input symbols or samples, v
in
, and writes to a vector of interleaved or permuted output samples, v
out
. The output samples are written sequentially using the time index i, i=0 . . . K−1, where K is the size of the interleaver. Vector I defines the order that the samples in the input vector are read. That is, the i-th output, written to location i in the output vector, is read from location I(i) in the input vector. With this model, the interleaved is completely defined by the integer read vector I. This illustration is used for definition purposes only, and does not necessarily represent a preferred method of implementation. As another example, vector I could define the write order.
The “S-random” interleaver is a semi-random interleaver. It is based on the random selection, without replacement, of K integers from 0 to K−1, but with the following constraint: each randomly selected integer is compared to the J−1 most recently selected integers. If the current selection is within J−1 of at least one of the previous J−1 integers, then it is rejected and a new integer is selected until the condition is satisfied.
This process is repeated until all K integers are extracted. The search time increases with J, and there is no guarantee that the process will finish successfully.
Note that J denotes the one-sided span of write indexes considered at each step, including the current index and ignoring edge effect. An appropriate (old) definition of spread
Her Majesty the Queen in Right of Canada, as represented by the
Morrison & Foerster / LLP
Ton David
LandOfFree
Method and system for high-spread high-distance interleaving... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for high-spread high-distance interleaving..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for high-spread high-distance interleaving... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222526