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

ISBN 0471-49581-6

**Download**(direct link)

**:**

**10**> 11 12 13 14 15 16 .. 86 >> Next

HsVs = (PT\In-k). (1.16)

Example 3 Consider a binary linear (4,2,2) code with generator matrix

G =

1110 0 0 11

To bring G into systematic form, permute (exchange) the second and fourth columns and obtain

10 1

Gsys —

1

0 110

Thus the parity-check sub-matrix is given by

P =

It is interesting to note that in this case, the relation P = PT holds3. From (1.16) it follows

1 1 1 0

3 In this case, the code in question is referred to as a self-dual code. See also Section 2.2.3.

8

THE ART OF ERROR CORRECTING CODING

that the systematic form of the parity-check matrix is

1110 10 0 1

HSys —

In the following let u = («0; ui, ? ? ?. Uk-i) denote an information message to be encoded and v — (vo,vi, - ? ? ,vn-i) the corresponding codeword in C.

If the parameters of C are such that k < (n — k), or equivalently the code rate k/n < 1/2, then encoding with the generator matrix is the most economical. The cost considered here is in terms of binary operations. In such case

V = uGsys = (u.Vp), (1.17)

where vp — uP — (Vk, Vk+i , • • •, vn-1) represents the parity-check part of the codeword.

However, if k > (n — k), or k/n > 1/2, then alternative encoding with the parity-check matrix H requires less number of computations. In this case, we have encoding based on Equation (1.12), (u,vp)HT = 0, such that the (n — k) parity-check positions Vk, Vk+1, • • ?, w,i-1 are obtained as follows:

Vj = u0po,j + UiPij H \~Uk-iPk-ij-, k < j < n. (1-18)

Stated in other terms, the systematic form of a parity-check matrix of a linear code has as entries of its rows the coefficients of the parity-check equations, from which the values of the redundant positions are obtained. This fact will be used when low-density parity-check codes are presented, in Section 8.3.

Example 4 Consider the binary linear (4,2,2) code from Example 3. Let messages and codewords be denoted by u = (n0. m) and v = (v0,vi,V2-,v3), respectively. From Equation (1.18), we have that

V2 = «0 + U1

V3 = U0

The correspondence between the 22 = 4 two-bit messages and codewords is as follows:

(00) M- (0000)

(01) i-t (0110)

(10) i-» (1011)

(11) h-t (1101)

1.3.2 Standard array decoding

In this section, a decoding procedure is presented that finds the closest codeword v to a received noisy word f = v + e. The error vector e ? {0, l}n is produced by a BSC, as depicted in Figure 5. It is assumed that the crossover probability (or BSC parameter) p is such thatp < 1/2.

A standard array [Sle] for a binary linear (n,k,dmin) code C is a table of all possible received vectors f arranged in such a way that the closest codeword v to f can be read out.

INTRODUCTION

Figure 5 A binary symmetric channel model. Table 1 The standard array of a binary linear block code.

s M0 = 0 M2 ' • Uk-1

0 S' II 01 Vi ? ? «2*-l

Si ei &1+V1 ? • ei + M2fc-1

S2 S2 e2 + Vl ? • e2 + V2k-1

— 1 e2n-k_1 e2n-k_1 + Ml . • (Z<2,n — fc_l ^2fc — 1

The standard array contains 2n~k rows and 2k + 1 columns. The entries of the rightmost 2k columns of the array contain all the vectors in V-z = {0, l}n.

In order to describe the decoding procedure, the concept of syndrome is needed. The syndrome of a word in V2 is defined from Equation (1.12) as

s = rH

~ EjrT

(1.20)

where H is the parity-check matrix of C. That s is indeed a set of symptoms that indicate errors is shown as follows. Suppose that a codeword v 6 C is transmitted over a BSC and received as f = v + e. The syndrome of f is

s = fH =(v + e)H 1 = eH 1

(1-21)

where to obtain the last equality Equation (1.12) has been used. Therefore, the computation of the syndrome can be thought of as a linear transformation of an error vector.

Standard array construction procedure

1. As the first row, in the positions corresponding to the 2fc rightmost columns, enter all the codewords of C, beginning with the all-zero codeword in the leftmost position. In the position corresponding to the first column, enter the all-zero syndrome. Let 3=0.

2. Let j = j + 1. Find the smallest Hamming weight word ej in V2, not in C, and not included in previous rows. The corresponding syndrome Sj = SjHT is the first (rightmost) entry of the row. The 2k remaining entries in that row are obtained by adding ej to all the entries in the first row (the codewords of C).

3. Repeat the previous step until all vectors in V2 are included in the array. Equivalently, let j = j + 1. If j < 2n~k, then repeat previous step, otherwise stop.

10

THE ART OF ERROR CORRECTING CODING

Example 5 The standard array of the binary linear (4,2,2) code is the following:

s 00 01 10 11

00 0000 0110 1011 1101

11 1000 1110 0011 0101

10 0100 0010 1111 1001

01 0001 0111 1010 1100

Decoding with the standard array proceeds as follows. Let f = v + e be the received word. Find the word in the array and output as decoded message u the header of the column in which r lies. Conceptually, this process requires storing the entire array and matching the received word to an entry in the array.

However, a simplified decoding procedure can be found by noticing that every row in the array has the same syndrome. Each row of the array, denoted Row;, for 0 < i < 2n~k, is a coset of C, such that Row* = {e* 4- v\v e C} . The vector et is known as the coset leader. The syndrome of the elements in the i-th row is given by

**10**> 11 12 13 14 15 16 .. 86 >> Next