Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-03-27
2004-08-03
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S755000
Reexamination Certificate
active
06772391
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to processes that create time diversity in systems with high processing gain. More specifically, the invention relates to a system and method of turbo code interleaving mapping where the number of tail bits required to flush the storage registers of each constituent encoder to an all-zero state are reduced.
2. Description of the Prior Art
In many types of data communication systems, whether voice or non-voice, signal diversity or redundancy when transmitting information is shown to improve performance without compromising other aspects of the data transmission system. Two techniques that add time diversity are known as interleaving and forward error-correcting (FEC) coding.
The process of interleaving is where the input data sequence is permuted or reordered into another sequence. For example:
where the mathematical operator I
N
[J] transposes the original position of each bit or symbol of a finite input sequence to a new position J by operation of the interleaver I
N
. This reordering process that achieves time diversity is called interleaving and can be performed in a number of ways. Two methods of typical interleaving are known as block and random interleaving.
At the transmission destination, the signal is again reordered, putting the data sequence back in the original order. The inverse process is called deinterleaving.
The most recent advance in coding techniques which exhibit the best performance are turbo codes. A variety of turbo code interleaver designs exist and require less complexity when decoding. The three most popular are: 1) block interleavers; 2) pseudo-random interleavers; and 3) S-random interleavers.
The best performing interleavers are the S-random interleavers. The S-random interleavers exploit the property of not mapping neighbor positions within a certain sequence length, to neighbor positions exhibiting the same length. This makes the sequence length as large as possible. All interleaver designs require a specific set of rules setting forth input sequence size and permutation.
In conjunction with interleaving, FEC coding improves performance for signals that are coherently demodulated. FEC coding adds additional redundancy in the original data sequence. In communication systems that communicate over a spread spectrum air interface, redundancy is already present in the shared spectral transmission channel. A FEC encoder is a finite-state machine that relies upon nodes or states and delay registers. The predetermined transitions between the registers define a path from which a given data input may produce an output. A common way to illustrate the encoding and decoding technique for the convolutionally encoded data is the use of a trellis diagram which is known to those familiar with this art. A trellis diagram is an infinite replication of a state machine diagram and is shown in FIG.
1
.
The decoding is typically performed using a maximum likelihood algorithm which relies upon the trellis structure and the path state or metric for each level and each selected node or state. Any code word of a convolutional code corresponds to the symbols along a path in the trellis diagram. At each state and at each level of the trellis an add-compare-select operation is performed to select the best path and state. The trellis is assembled over many received symbols. After a predefined number of symbols have been accumulated, the determination finds the trellis path with the smallest error. The final decision on all bits in the trellis is made via the encoders by forcing the encoder to return to an initial all-zero state. This is achieved by inserting zero tail bits at the end of the finite bit stream after encoding. This process is referred to as “tailing off.”
A process known as “chaining back” is performed starting at the last node, tracing the decision path back from the last decision to the first. This method of decoding determines which symbol was originally sent. The trellis structure introduces redundancy and accumulates past history.
A prior art turbo encoder is shown in FIG.
2
. The encoder comprises first and second systematic recursive convolutional code (RCS) encoders coupled in parallel with a turbo code interleaver coupled prior to the second recursive convolutional encoder. The two recursive convolutional codes used in each encoder are known as the constituent codes. The first encoder reorders the input information bits {right arrow over (x)}
N
in their original order while the second encoder reorders the input bits as permuted by the turbo code interleaver {right arrow over (X)}
1
N
. The input information sequence {right arrow over (x)}
N
is always transmitted through a channel. In dependence upon the data transmission rate, the outputs from both encoders may be “punctured” before transmission {right arrow over (y)}
N
. Puncturing is a process where alternate outputs of the lower taps (first and second encoders {right arrow over (p)}
1
N
,{right arrow over (p)}
2
N
) are deleted from the output. This process establishes a code rate.
The turbo code interleaver is a scrambler defined by a permutation of the sequence length with no repetitions. A complete sequence is input into the interleaver and output in a predefined order.
A prior art tailing off process is shown and described in
FIGS. 3 and 4
. The tail bits for each encoder are obtained from register feedback from each respective encoder as shown in FIG.
3
. Since the register contents of each constituent encoder are different at the beginning of the tailing off operation, each encoder must be flushed separately. As described in
FIG. 4
, each encoder (in
FIG. 3
) is flushed independently and exclusive of each other after the information bits have been encoded. Each encoder derives and receives its own tail bits. Therefore, if m equals the number of states or register memory of an encoder, m tail bits are required for one encoder and 2 m are required for both encoders.
A prior art turbo code decoder is shown in FIG.
5
. On receiving the demodulated soft value signal {right arrow over (y)}
N
, the soft-decision information for the systematic (information) and parity bits {right arrow over (p)}
1
N
from the first constituent encoder are input to a first constituent decoder. The first constituent decoder generates updated, soft-decision likelihood values {right arrow over (L)}
e1
({right arrow over (x)}
N
) for the information bits that are input along with the information bits to a decoder interleaver. The input to a second constituent decoder includes the interleaved soft-valued sequences {right arrow over (x)}
N
and {right arrow over (L)}
e1
({right arrow over (x)}
N
) and the parity bits {right arrow over (p)}
2
N
from the second constituent encoder. The output of the second decoder improves on the soft-decision likelihood values derived from the output from the first constituent decoder and is fed back to the first constituent decoder after reordering in accordance with the turbo decoder interleaver as an iterative process. The output {right arrow over (X)}
e
from the second constituent decoder is obtained after the decoding operation is completed.
As discussed above, the use of a turbo code interleaver requires that coding be performed on a finite sequence length. To encode such a finite information sequence, it is necessary for both constituent RSC encoders in the turbo encoder to start and end in an all zero-state with the same trellis bits. Most prior art turbo encoders have their information sequences terminated with a plurality of tail bits. Tail bits are considered a nuisance and as overhead of the turbo encoded sequence.
The difficulties with flushing turbo code encoders and bringing their trellises back to their initial state have long been recognized by the prior art. For example, the article entitled Turbo Code Termination And Interleaver Conditions by Blackert et al., the article entitled Turbo Codes For PSC Applications by Divsalar et al., and the article entitled Te
LandOfFree
Hybrid interleaver for turbo codes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hybrid interleaver for turbo codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid interleaver for turbo codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3275459