# The art of error correcting coding - Moreloz R.H.

ISBN 0471-49581-6

**Download**(direct link)

**:**

**53**> 54 55 56 57 58 59 .. 86 >> Next

State/Stage i = 0 i — 1 i = 2 i = 3 i = 4 i = 5 i = 6

sT 0 +5 +7 +6 +12 + 14 +26

5<1} 0 +3 +5 +12 +14 +24 +18

S<2) 0 +5 +9 +8 + 18 +14 +22

sf> 0 +3 +7 +14 + 14 +20 +24

The decoded information sequence is ? = ( 1 1 0 1 0 0), and two errors have been

corrected.

All the implementation issues related to Viterbi decoding, discussed in Sections 5.4.3 and 5.5.1, apply in the case of soft-decision. In particular, metric normalization must be carefully taken into account.

124

THE ART OF ERROR CORRECTING CODING

Transmitted -1 -1 +1 -1 +1 -1 +1 +1 -1 +1 -1 -1

Received -4-1 -1-3 +2-3 +3+3 -3+3 -3+1

i = 0:

i = 1:

0 -4-1

"-N 00 -5 / N (0) (0)

°°A pKoo) M(S j) 1 - +5, y ! = (!!)

Ml\ 0 \+5 “ MX /" N (i) (1)

oiXT \ +j/oi) M(S j) ? = +3, y ! = (10)

^ oo\. V/.3W

“ io/^<Vs (2) (2)

lOK; /-sYio) M(S ,) = +5, y ! = (11)

orV w

(3) (3)

WTo X® M(S ,) i = +3, y !=(10)

( 1 = change sign ) /

Branch metric computation:

(0) (I)

BMj =d (00,-4-1 ) = -5 BMj =d (01,-4-1 ) =-3 (2) (3)

BMj = d (10,-4 -1 ) = +3 BMj = d (11,-4 -1 ) =+5

(0) (0) (0) (1) (3)

M(S j) = max{M(S0)+BM j, M(S q)+BM { }

= +5, select branch from state 1

(0) (0) Update metric M(S j) = +5 Update path y j = (11)

Add

Compare

Select

Figure 69 Soft-decision Viterbi decoder operation at * = 1.

Transmitted -1 -1 Received -4-1

+1 -1 -1 -3

+1 -1 +2 -3

+ 1 +1

+3 +3

-1 +1 -3 +3

-1 -1 -3+1

i = 2:

-4-1 +5 -1-3

+1^ (0) —Moo) y 2= (10,11)

(3)

Figure 70 Soft-decision Viterbi decoder operation at i = 2.

SOFT-DECISION DECODING

Transmitted -1-1 +1-1 +1-1 +1+1 -1+1 -1-1

Received -4 -1 -1 -3 +2 -3 +3 +3 -3 +3 -3 +1

i = 3:

-4-1

-1 -3

+2 -3

Figure 71 Soft-decision Viterbi decoder operation at i = 3.

Transmitted -1 -1 +1 -1 +1 -1 +1 +1 -1 +1 -1 -1

Received -4 -1 -1 -3 +2 -3 +3 +3 -3 +3 -3 +1

-1 -3

+2 -3

+3 +3

Figure 72 Soft-decision Viterbi decoder operation at i = 4.

126 THE ART OF ERROR CORRECTING CODING

Transmitted -1-1 Received -4 -1

+1 -1 -1 -3

+1 -1 +2 -3

+1 +1

+3 +3

-1 +1

-3 +3

-1 -1 -3+1

i = 5:

+2 -3

+3 +3

-3 +3

+12^^ (0)

y g = (1 1,11,01,01,11)

(1)

y 5 = (11,01,01,00,10)

. (2)

+14\10J y 5 = (11,11,01,01,00)

+l2"' (3)

y 5= Cl 1,11,01,10,10)

Figure 73 Soft-decision Viterbi decoder operation at i = 5.

SOFT-DECISION DECODING

127

Transmitted -1-1 Received -4 -1

+1 -1

-1 -3

+1 -1 +2 -3

+1 +1 +3 +3

-1 +1 -3 +3

-1 -1 -3+1

i = 6:

-4-1

-1 -3

+2 -3

+3 +3

(0)

i 6= (11,01,01,00,10,1

y ^=(11,11,01,01,00,1'

y6= (11,01,01,00,10,0»

(3)

y 6 = (11,11,01,10,10,11

Figure 74

Soft-decision Viterbi decoder operation at i = 6.

128

THE ART OF ERROR CORRECTING CODING

7.3 Decoding binary linear block codes with a trellis

The Viterbi algorithm can also be applied to linear block codes. A syndrome trellis for a binary linear (TV, K) block code C can be constructed from its parity-check matrix as follows [Wol]. Let (i>i, v2. ? ? ?, vjv) denote a codeword of C. At time i, 1 < i < N, states in the trellis are specified by the partial syndromes:

i

Si = ^2vjhj, (7.3)

1=1

where the sum is over GF(2), hj is the j-th column of H, and sj = (0 0 • ? • 0). The maximum number of states in the syndrome trellis is min {2K, 2N~K}. The syndrome trellis has the property that it has the smallest possible number of states. A trellis satisfying this condition is said to be a minimal trellis.

Example 87 Consider a binary cyclic Hamming (7,4.3) code with g(x) = ,r3 + x + 1. Then h(x) = 1 + x + x2 + x4, and a parity-check matrix for C is

/1 1 1 0 1 0 0\

77= 0111010 .

\0 0 1 1 1 0 1/

To label a state sj = (so «1 s2) an integer ft is assigned, such that

Ij = So T Si x 2 s2 x 22.

The trellis has maximum of 8 states (since 2n~k = 23) at times i = 3 and i — 4, and is shown in Figure 75.

It is interesting to note that with a syndrome trellis there is no need to label the branches with the coded bits. A transition between two states with the same label corresponds to coded bit 0, as seen from Equation (7.3): If the coded bit is 0, then the sum does not change.

SOFT-DECISION DECODING

129

Some observations about the trellis structure of linear block codes are the following: In general, the trellis of a binary cyclic code has an irregular structure. As a result, implementation of the Viterbi algorithm will be more intricate than in the case of convolutional codes.

For some classes of codes, such as extended2 BCH codes and Reed-Muller codes, the trellis can be divided into sections. This results in a more regular and symmetric trellis structure with many parallel subtrellises, which may be used to build very high-speed Viterbi decoders for block codes [LKFF, F1M].

7.4 The Chase algorithm

The Chase algorithm [Cha] is a suboptimal decoding procedure that uses a set or list of most likely error patterns. These error patterns are selected based on the reliability of the received symbols. Each error pattern is added to the hard-decision received word and decoded using a hard-decision decoder. Each decoded codeword is scored by computing its metric with respect to the received (soft-decision) sequence. The codeword with the best metric is selected as the most likely.

**53**> 54 55 56 57 58 59 .. 86 >> Next