Turbo decoder extrinsic normalization

Details Turbo decoder extrinsic normalization Turbo decoder extrinsic normalization

2002-07-24

2004-08-10

Lamarre, Guy J. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C708S700000, C375S262000, C375S341000, C714S794000, C714S795000, C714S796000

Reexamination Certificate

active

06775801

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
The technical field of this invention is forward error correction using turbo decoders.
BACKGROUND OF THE INVENTION
Turbo codes are a type of forward error correction code with powerful capabilities. These codes are becoming widely used in many applications such as wireless handsets, wireless base stations, hard disk drives, wireless local area networks (LANs), satellites and digital television.
Turbo encoding is accomplished by means of concatenation of convolutional codes.
FIG. 1A
illustrates an example of a prior art rate ⅓ parallel-concatenated turbo encoder. The notation rate ⅓ refers to the configuration of
FIG. 1A
in which a single input bit stream x
k
is converted by the encoder into a 3-component bit stream. Input data stream
100
passes unmodified to multiplexer input
106
. Two recursive systematic convolutional (RSC) encoders
102
and
103
function in parallel to transform their input bit streams. The resulting bit streams after transformation by RSC encoder
102
forms multiplexer input
107
and after transformation by RSC encoder
103
forms multiplexer input
108
. Block
101
is an interleaver (I) which randomly re-arranges the information bits to decorrelate the noise for the decoder. RSC encoder
102
generates a p
1
k
bit stream and RSC encoder
103
generates a p
2
k
bit stream. Under control of a turbo controller function multiplexer
104
reassembles the separate bit streams x
k
106
, p
1
k
107
and p
2
k
108
into the resulting output bit stream x
k
/p
1
k
/p
2
k
111
.
FIG. 1B
illustrates an example of the RSC encoder function which is a part of the blocks
102
or
103
. Input data stream
120
passes unmodified to become output x
0
131
. After transformation by the RSC encoder the resulting bit streams
131
,
132
and
133
in prescribed combinations form multiplexer inputs
107
and
108
of FIG.
1
A. The precise combinations are determined by the class of turbo encoder being implemented, ½, ⅓, or ¼ for example. The action of the circuit of
FIG. 1B
is depicted by a corresponding trellis diagram which is illustrated in FIG.
4
and will be described in the text below.
This transmitted output bit stream
111
of
FIG. 1A
can be corrupted by transmission through a noisy environment. The function of the decoder at the receiving end is to reconstruct the original bit stream by tracing through multiple passes or iterations through the turbo trellis function.
FIG. 2
illustrates the functional block diagram of a prior art turbo decoder. A single pass through the loop of
FIG. 2
is one iteration through the turbo decoder. This iterative decoder generates soft decisions from two maximum-a-posteriori (MAP) blocks
202
and
203
. In each iteration MAP block
202
generates extrinsic information W
0,k
206
and MAP block
203
generates extrinsic information W
1,k
207
. First MAP block
202
receives the non-interleaved data x
k
200
and data p
1
k
201
as inputs. Second MAP decoder
203
receives data p
2
k
211
and interleaved x
k
data
210
from the interleaver block
208
.
FIG. 3
illustrates the functional block diagram of a prior art MAP block. The MAP block of
FIG. 3
includes circuit functions similar to those illustrated in FIG.
2
. The MAP block calculates three vectors: beta state metrics, alpha state metrics and extrinsics. Both alpha block
302
and beta block
303
calculate state metrics. It is useful to define the function gamma as:
&Ggr;
k
=f
(
X
k
,P
k
,W
k
)  [1]
where: X
k
is the systematic data; P
k
is the parity data; and W
k
is the extrinsics data.
Input
300
to the alpha state metrics block
302
and input
301
to beta state metrics block
302
are referred to as a-priori inputs. The beta state metrics are generated by beta state metrics block
303
. These beta metrics are generated in reverse order and stored in the beta state random access memory (RAM)
304
. Next, alpha state metrics are generated by alpha state metrics block
302
. The alpha state metrics are not stored because the extrinsic block
305
uses this data as soon as it is generated. The beta state metrics are read from beta RAM
304
in a forward order at the same time as the alpha state metrics are generated. Extrinsic block
305
uses both the alpha and beta state metrics in a forward order to generate the extrinsics W
n,j
306
.
The variables for the MAP algorithm are usually represented by the natural logarithm of probabilities. This allows for simplification of very large scale integration (VLSI) implementation. The recursive equations for the alpha and beta state metrics are as follows:
A
k
,
s
=
ln
⁡
[
∑
s
⁢
exp
⁢
{
A
k
-
1
+
Γ
k
}
]
[
2
]
B
k
,
s
=
ln
⁡
[
∑
s
⁢
exp
⁢
{
B
k
-
1
+
Γ
k
}
]
[
3
]
where: s is the set of states in the trellis; and &Ggr;
k
is as stated in equation [1] above.
FIG. 4
shows the trellis diagram for an 8-state state encoder. For a given state on the trellis, for example state
7
indicated by reference numbers
401
and
402
, it is possible to write the probability equation for a given state in the form:
P
(7)=[
P
(3)×&ggr;(001)]+[
P
(7)×&ggr;(110)]  [4]
for Alpha and
P
(7)=[
P
(6)×&ggr;(001)]+[
P
(7)×&ggr;(110)]  [5]
for Beta.
These equations are said to be of the form:
P
=MAX*(
A, B
)  [6]
where: A and B are the alpha and beta state metrics given by equations [2] and [3]. Equation 6 is referred to as the ‘max star’ equation, a simplification of the probability equations. The function P can be further expressed as:
P
=MAX*(
A, B
)=MAX(
A, B
)+
f
(−|
A−B
|)  [7]
and f(−|A−B|) ranges from 0 to ln(2).
Turbo decoder processing is an iterative process requiring multiple cycles until a low bit-error ratio (BER) solution is obtained. Because the state of the trellis at the start of processing is unknown the probability of the occurrence of all the states in the trellis is initialized to a uniform constant. For each pass through the trellis, the probability of occurrence of a given state will increase or decrease as convergence to the original transmitted data proceeds. After processing through the trellis a number of times a set of states corresponding to the original transmitted data becomes dominant and the state metrics become reliable.
FIG. 4
illustrate a trellis diagram for an 8-state state encoder depicting the possible state transitions from each possible state S
k,x
=ABC. For example, for state S
k,4
, ABC=001. These states are represented in
FIG. 1B
by the state of the three registers A
121
, B
122
and C
123
, respectively. In the decoder, the generation of the alpha state metrics requires processing the data in a forward direction through this trellis and the generation of the beta state metrics requires processing the data in a reverse direction through this trellis. Initial states in the trellis for forward traversal are labeled S
k,x
and next states are labeled S
k+1,x
. Conversely, initial states in the trellis for reverse direction traversal are labeled S
k+1,x
and next states are labeled S
k,x
. The nomenclature X/DEF of
403
and
404
of
FIG. 4
refers to the next bit ‘Y’ inserted at the input X
k
,
120
of
FIG. 1B
, followed by the forward slash, followed by the next three bits D, E and F generated respectively at the nodes
131
,
132
,
133
of FIG.
1
B.
FIG. 5
illustrates an example of a prior art VLSI implementation of a four-stage beta state metric architecture. The first stage is an adder tree
501
which sums X, P, W and the beta state metrics depending on the trellis of the encoder. The implementation of the alpha block is the same as the beta block of
FIG. 5
, except the combinations of the operands in the adder tree. The second stage
502
t

Affiliated with

Also associated with

Rating

Turbo decoder extrinsic normalization does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Turbo decoder extrinsic normalization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turbo decoder extrinsic normalization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3334395