Books in black and white
 Books Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

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

Moreloz R.H. The art of error correcting coding - Wiley publishing , 2002. - 232 p.
ISBN 0471-49581-6
Previous << 1 .. 47 48 49 50 51 52 < 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)
Compare
Select
Figure 69 Soft-decision Viterbi decoder operation at * = 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
+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
+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.
Previous << 1 .. 47 48 49 50 51 52 < 53 > 54 55 56 57 58 59 .. 86 >> Next