TURBO EQUALIZATION - Adaptive Signal Processing: Next Generation Solutions - page 152

Now, a stationary point corresponds to no change in the variables from one iteration to
the next, giving U ( mþ 1)

j ( c j ) ¼ U ( m j ( c j ) for all j . By inspection, this corresponds to the
two decoders producing the same pseudo posterior values. Conversely, if the pseudo
posteriors from the two decoders agree, that is, [Pr( d i ¼ 1 jy )] ( m ) ¼ [Pr( c j ¼ 0 jd )] ( m )

with j ¼ P ( i ), then we must have U ( mþ 1)
j

( c j ) ¼ U ( m )

( c j ), giving a stationary point of

j

the iterative procedure. We summarize as [4]:

Property 1 (Consensus property) A stationary point of the iterative decoding algo-
rithm occurs if and only if the two decoders reach consensus on the pseudo posteriors.

Property 2 The iterative decoding algorithm so described always admits a station-
ary point.

A proof is developed in [31, 32], and sketched here. A classic result of nonlinear
mathematics, known as the Brouwer fixed point theorem [33], asserts that any con-
tinuous function from a closed, bounded and convex set into itself admits a fixed
point. To apply this result in our present context, consider the variables U ( m j ( c j ) for
i ¼ 1, ... , N , at a given iteration m . As these variables are pseudo probabilities,
their values are restricted to the hypercube

0 U ( m )
j

( c j ) 1, j ¼ 1, 2, ... , N:

This hypercube is clearly a closed, bounded, and convex set. As the updated values
U ( mþ 1 j ( c j ) at iteration mþ 1 remain in this hypercube, the iterative decoding pro-
cedure may be viewed as a function that maps a closed, bounded, and convex set
into itself. Upon showing that this function is continuous [31], the conditions of the
Brouwer fixed point theorem are satisfied, to establish the existence of a fixed point.
Convergence to a fixed point, conversely, is more difficult to establish, and is taken
up in Section 3.9. We present first, however, the detailed workings of the forward-
backward algorithm for calculating marginals.

3.5 FORWARD-BACKWARD ALGORITHM

The forward-backward algorithm is an efficient procedure to calculate marginal prob-
abilities when the underlying observables are produced from a Markov chain. Its ori-
gins in the communications literature are usually credited to [14] in the context of
channel equalization, and [17] in the context of error correction decoding, although
the same basic algorithm may be recognized under various guises [15, 16, 34, 35].
For clarity we illustrate the algorithm for a specific encoder and channel, with the
understanding that other choices of encoder and channel are readily accommodated
once the basics are established.
Consider the “(5,7)” recursive systematic encoder sketched in Figure 3.3. (The
label “(5,7)” applies since the connection branches below and above the delay line
are 1 0 1 and 1 1 1, respectively, where 1 denotes a connection branch and 0 its