Chapter 3 Linear Block Codes

Outlines
Introduction to linear block codes Syndrome and error detection The minimum distance of a block code Error-detecting and error-correcting capabilities of a block code Standard array and syndrome decoding Probability of an undetected error for linear codes over a binary symmetric channel (BSC). Single-Parity-Check Codes, Repetition Codes, and Self-Dual Codes
2

Introduction to Linear Block Codes

Introduction to Linear Block Codes

We assume that the output of an information source is a sequence of binary digits 0 or 1 This binary information sequence is segmented into message block of fixed length, denoted by u.
Each message block consists of k information digits. There are a total of 2k distinct message.

The encoder transforms each input message u into a binary n-tuple v with n > k
This n-tuple v is referred to as the code word ( or code vector ) of the message u. There are distinct 2k code words.
4

Introduction to Linear Block Codes

This set of 2k code words is called a block code. For a block code to be useful, there should be a one-to-one correspondence between a message u and its code word v. A desirable structure for a block code to possess is the linearity. With this structure, the encoding complexity will be greatly reduced. u
Message block (k info. digits) (2k distinct message) Encoder

v
Code word (n-tuple , n > k ) (2k distinct code word)

Introduction to Linear Block Codes

Definition 3.1. A block code of length n and 2k code word is called a linear (n, k) code iff its 2k code words form a k-dimensional subspace of the vector space of all the n-tuple over the field GF(2). In fact, a binary block code is linear iff the module-2 sum of two code word is also a code word
0 must be code word. The block code given in Table 3.1 is a (7, 4) linear code.

Introduction to Linear Block Codes

For large k, it is virtually impossible to build up the loop up table.

7

Introduction to Linear Block Codes

Since an (n, k) linear code C is a k-dimensional subspace of the vector space Vn of all the binary ntuple, it is possible to find k linearly independent code word, g0 , g1 ,, gk-1 in C

v = u 0 g 0 + u1g 1 + + u k 1g k 1
where ui = 0 or 1 for 0 i < k

(3.1)

Introduction to Linear Block Codes

Let us arrange these k linearly independent code words as the rows of a k n matrix as follows:
g 0 g 00 g g 1 10 . . G= . = . . . . . g k 1 g k 1,0 g 01 g11 . . . . g k 1,1 g 02 g12 . . . . g k 1,2 . . . . . . . . g 0,n 1 . g1,n 1 . . . . . . . . . g k 1,n 1

(3.2)

where gi = (gi0, gi1,,gi,n-1) for 0 i < k

9

Introduction to Linear Block Codes

If u = (u0,u1,,uk-1) is the message to be encoded, the corresponding code word can be given as follows:
v = u G g0 g 1 . = (u0 , u1 ,..., uk 1 ) . . g k 1 = u0 g 0 + u1g1 + + uk 1g k 1
10

(3.3)

Introduction to Linear Block Codes

Because the rows of G generate the (n, k) linear code C, the matrix G is called a generator matrix for C Note that any k linearly independent code words of an (n, k) linear code can be used to form a generator matrix for the code It follows from (3.3) that an (n, k) linear code is completely specified by the k rows of a generator matrix G

11

Introduction to Linear Block Codes

Example 3.1
the (7, 4) linear code given in Table 3.1 has the following matrix as a generator matrix :
g 0 1 g 0 G = 1 = g 2 1 g 3 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1

If u = (1 1 0 1) is the message to be encoded, its corresponding code word, according to (3.3), would be
v = 1 g 0 + 1 g1 + 0 g 2 + 1 g 3 = (11 0 1 0 0 0) + (0 11 0 1 0 0) + (1 0 1 0 0 0 1) = (0 0 0 11 0 1)
12

Introduction to Linear Block Codes

A desirable property for a linear block code is the systematic structure of the code words as shown in Fig. 3.1
where a code word is divided into two parts
The message part consists of k information digits The redundant checking part consists of n k parity-check digits

A linear block code with this structure is referred to as a linear systematic block code
Redundant checking part
n - k digits

Message part
k digits

Fig. 3.1

Systematic format of a code word

13

Introduction to Linear Block Codes

A linear systematic (n, k) code is completely specified by a k n matrix G of the following form :
P matrix
k k identity matrix

g 0 p00 g p 1 10 g 2 p20 G= . = . . g p k 1 k 1, 0
where pij = 0 or 1

p 01 p11 p21

. . .

. . .

. . .

p0,n k 1 p1,n k 1 p2,n k 1

pk 1,1

pk 1, n k 1
14

0 0 | 0 0 1 . . . 0 | | | | 0 0 0 0 0 0 1 | 1 0 0 | 0 1 0 . . . . . .

(3.4)

Introduction to Linear Block Codes

Let u = (u0, u1, , uk-1) be the message to be encoded The corresponding code word is

v = (v0 , v1 , v2 ,..., vn 1 ) = (u0 , u1 ,..., uk -1 ) G (3.5)

It follows from (3.4) & (3.5) that the components of v are vn-k+i = ui for 0 i < k (3.6a) and vj = u0 p0j + u1 p1j + + uk-1 pk-1, j for 0 j < n-k (3.6b)
15

Introduction to Linear Block Codes

Equation (3.6a) shows that the rightmost k digits of a code word v are identical to the information digits u0, u1,uk-1 to be encoded Equation (3.6b) shown that the leftmost n k redundent digits are linear sums of the information digits The n k equations given by (3.6b) are called parity-check equations of the code

16

Introduction to Linear Block Codes

Example 3.2
The matrix G given in example 3.1 Let u = (u0, u1, u2, u3) be the message to be encoded Let v = (v0, v1, v2, v3, v4, v5,v6) be the corresponding code word Solution :

1 0 v = u G = (u0 , u1 , u2 , u3 ) 1 1

1 1 1 0

0 1 1 1

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

17

Introduction to Linear Block Codes

By matrix multiplication, we obtain the following digits of the code word v
v6 = u3 v5 = u 2 v4 = u1 v3 = u0 v2 = u1 + u2 + u3 v1 = u0 + u1 + u 2 v0 = u0 + u2 + u3

The code word corresponding to the message (1 0 1 1) is (1 0 0 1 0 1 1)

18

Introduction to Linear Block Codes

For any k n matrix G with k linearly independent rows, there exists an (n-k) n matrix H with n-k linearly independent rows such that any vector in the row space of G is orthogonal to the rows of H and any vector that is orthogonal to the rows of H is in the row space of G. An n-tuple v is a code word in the code generated by G if and only if v HT = 0 This matrix H is called a parity-check matrix of the code The 2n-k linear combinations of the rows of matrix H form an (n, n k) linear code Cd This code is the null space of the (n, k) linear code C generated by matrix G Cd is called the dual code of C
19

Introduction to Linear Block Codes

If the generator matrix of an (n,k) linear code is in the systematic form of (3.4), the parity-check matrix may take the following form :
H = I nk 1 0 0 = . . . 0

PT 0 0 1 0 0 1

]
. . . . . . . 0 . 0 . 0 p00 p01 p02 p10 p11 p12 . . . . . . . . . pk-1,0 pk-1,1 pk-1,2 pk-1,n-k-1

(3.7)

0 0

. 1

p0 ,n-k-1
20

p1,n-k-1

Introduction to Linear Block Codes

Let hj be the jth row of H

g i h j = pij + pij = 0
for 0 i < k and 0 j < n k This implies that G HT = 0

21

Introduction to Linear Block Codes

Let u = (u0, u1, , uk-1) be the message to be encoded In systematic form the corresponding code word would be v = (v0, v1, , vn-k-1, u0,u1, , uk-1) Using the fact that v HT = 0, we obtain vj + u0 p0j + u1 p1j + + uk-1 pk-1,j = 0 (3.8) Rearranging the equation of (3.8), we obtain the same parity-check equations of (3.6b) An (n, k) linear code is completely specified by its paritycheck matrix
22

Introduction to Linear Block Codes

Example 3.3
Consider the generator matrix of a (7,4) linear code given in example 3.1 The corresponding parity-check matrix is

1 0 0 1 0 1 1 H = 0 1 0 1 1 1 0 0 0 1 0 1 1 1

23

Introduction to Linear Block Codes

For any (n, k) linear block code C, there exists a k n matrix G whose row space given C There exist an (n k) n matrix H such that an n-tuple v is a code word in C if and only if v HT = 0 If G is of the form given by (3.4), then H may take form given by (3.7), and vice versa

24

Introduction to Linear Block Codes

Based on the equation of (3.6a) and (3.6b), the encoding circuit for an (n, k) linear systematic code can be implemented easily The encoding circuit is shown in Fig. 3.2
where
denotes a shift-register stage (flip-flop) Pij denotes a connection if pij = 1 and no connection if pij = 0 denotes a modulo-2 adder As soon as the entire message has entered the message register, the n-k parity-check digits are formed at the outputs of the n-k module-2 adders

The complexity of the encoding circuit is linear proportional to the block length The encoding circuit for the (7,4) code given in Table 3.1 is shown in Fig 3.3
25

Introduction to Linear Block Codes

26

Introduction to Linear Block Codes

27

Syndrome and Error Detection

Syndrome and Error Detection

Let v = (v0, v1, , vn-1) be a code word that was transmitted over a noisy channel Let r = (r0, r1, , rn-1) be the received vector at the output of the channel r=v+e v e e = r + v = (e0, e1, , en-1) is an n-tuple

ei = 1 for ri vi ei = 0 for ri = vi The n-tuple e is called the error vector (or error pattern)
29

Syndrome and Error Detection

Upon receiving r, the decoder must first determine whether r contains transmission errors If the presence of errors is detected, the decoder will take actions to locate the errors
Correct errors (FEC) Request for a retransmission of v (ARQ)

When r is received, the decoder computes the following (n k)-tuple : s = r HT = (s0, s1, , sn-k-1) (3.10)
which is called the syndrome of r
30

Syndrome and Error Detection

s = 0 if and only if r is a code word and receiver accepts r as the transmitted code word s0 if and only if r is not a code word and the presence of errors has been detected When the error pattern e is identical to a nonzero code word (i.e., r contain errors but s = r HT = 0), error patterns of this kind are called undetectable error patterns
Since there are 2k 1 nonzero code words, there are 2k 1 undetectable error patterns

31

Syndrome and Error Detection

Based on (3.7) and (3.10), the syndrome digits are as follows : s0 = r0 + rn-k p00 + rn-k+1 p10 + + rn-1 pk-1,0 s1 = r1 + rn-k p01 + rn-k+1 p11 + + rn-1 pk-1,1 . (3.11) . sn-k-1 = rn-k-1 + rn-k p0,n-k-1 + rn-k+1 p1,n-k-1 + + rn-1 pk-1,n-k-1 The syndrome s is the vector sum of the received parity digits (r0,r1,,rn-k-1) and the parity-check digits recomputed from the received information digits (rn-k,rn-k+1,,rn-1). A general syndrome circuit is shown in Fig. 3.4
32

Syndrome and Error Detection

33

Syndrome and Error Detection

Example 3.4
The parity-check matrix is given in example 3.3 Let r = (r0, r1, r2, r3, r4, r5, r6, r7) be the received vector The syndrome is given by
1 0 0 s = ( s0 , s1 , s2 ) = (r0 , r1 , r2 , r3 , r4 , r5 , r6 ) 1 0 1 1
34

0 0 1 0 0 1 1 0 1 1 1 1 0 1

Syndrome and Error Detection

Example 3.4
The syndrome digits are s0 = r0 + r3 + r5 + r6 s1 = r1 + r3 + r4 + r5 s2 = r2 + r4 + r5 + r6 The syndrome circuit for this code is shown below

35

Syndrome and Error Detection

Since r is the vector sum of v and e, it follows from (3.10) that s = r HT = (v + e) HT = v HT + e HT however, v HT = 0 consequently, we obtain the following relation between the syndrome and the error pattern : (3.12) s = e HT
36

Syndrome and Error Detection

If the parity-check matrix H is expressed in the systematic form as given by (3.7), multiplying out e HT yield the following linear relationship between the syndrome digits and the error digits : s0 = e0 + en-k p00 + en-k+1 p10 + + en-1 pk-1,0 s1 = e1 + en-k p01 + en-k+1 p11 + + en-1 pk-1,1 . . sn-k-1 = en-k-1 + en-k p0,n-k-1 + + en-1 pk-1,n-k-1
37

(3.13)

Syndrome and Error Detection

The syndrome digits are linear combinations of the error digits The syndrome digits can be used for error correction Because the n k linear equations of (3.13) do not have a unique solution but have 2k solutions There are 2k error pattern that result in the same syndrome, and the true error pattern e is one of them The decoder has to determine the true error vector from a set of 2k candidates To minimize the probability of a decoding error, the most probable error pattern that satisfies the equations of (3.13) is chosen as the true error vector
38

Syndrome and Error Detection

Example 3.5
We consider the (7,4) code whose parity-check matrix is given in example 3.3 Let v = (1 0 0 1 0 1 1) be the transmitted code word Let r = (1 0 0 1 0 0 1) be the received vector The receiver computes the syndrome s = r HT = (1 1 1) The receiver attempts to determine the true error vector e = (e0, e1, e2, e3, e4, e5, e6), which yields the syndrome above 1 = e0 + e3 + e5 + e6 1 = e1 + e3 + e4 + e5 1 = e2 + e4 + e5 + e6 There are 24 = 16 error patterns that satisfy the equations above
39

Syndrome and Error Detection

Example 3.5
The error vector e = (0 0 0 0 0 1 0) has the smallest number of nonzero components If the channel is a BSC, e = (0 0 0 0 0 1 0) is the most probable error vector that satisfies the equation above Taking e = (0 0 0 0 0 1 0) as the true error vector, the receiver decodes the received vector r = (1 0 0 1 0 0 1) into the following code word v* = r + e = (1 0 0 1 0 0 1) + (0 0 0 0 0 1 0) = (1 0 0 1 0 1 1) where v* is the actual transmitted code word
40

The Minimum Distance of a Block Code

The Minimum Distance of a Block Code Let v = (v0, v1, , vn-1) be a binary n-tuple, the Hamming weight (or simply weight) of v, denote by w(v), is defined as the number of nonzero components of v
For example, the Hamming weight of v = (1 0 0 0 1 1 0) is 4

Let v and w be two n-tuple, the Hamming distance between v and w, denoted d(v,w), is defined as the number of places where they differ
For example, the Hamming distance between v = (1 0 0 1 0 1 1) and w = (0 1 0 0 0 1 1) is 3

42

The Minimum Distance of a Block Code The Hamming distance is a metric function that satisfied the triangle inequality d(v, w) + d(w, x) d(v, x) (3.14)
the proof of this inequality is left as a problem

From the definition of Hamming distance and the definition of module-2 addition that the Hamming distance between two n-tuple, v and w, is equal to the Hamming weight of the sum of v and w, that is d(v, w) = w(v + w) (3.15)
For example, the Hamming distance between v = (1 0 0 1 0 1 1) and w = (1 1 1 0 0 1 0) is 4 and the weight of v + w = (0 1 1 1 0 0 1) is also 4
43

The Minimum Distance of a Block Code

Given, a block code C, the minimum distance of C, denoted dmin, is defined as (3.16) dmin = min{d(v, w) : v, w C, v w} If C is a linear block, the sum of two vectors is also a code vector From (3.15) that the Hamming distance between two code vectors in C is equal to the Hamming weight of a third code vector in C dmin = min{w(v + w): v, w C, v w} (3.17) = min{w(x): x C, x 0} wmin

44

The Minimum Distance of a Block Code

The parameter wmin {w(x): x C, x 0} is called the minimum weight of the linear code C Theorem 3.1 The minimum distance of a linear block code is equal to the minimum weight of its nonzero code words Theorem 3.2 Let C be an (n, k) linear code with parity-check matrix H.
For each code vector of Hamming weight l, there exist l columns of H such that the vector sum of these l columns is equal to the zero vector Conversely, if there exist l columns of H whose vector sum is the zeros vector, there exists a code vector of Hamming weight l in C.

45

The Minimum Distance of a Block Code Proof

Let the parity-check matrix be H = [ho, h1, , hn-1] where hi represents the ith column of H Let v = (v0, v1, , vn-1) be a code vector of weight l and v has l nonzero components Let vi1, vi2, , vil be the l nonzero components of v, where 0 i1 < i2 < < il n-1, then vi1 = vi2 = = vil = 1 since v is code vector, we must have 0 = v HT = voh0 + v1h1 + + vn-1hn-1 = vi1hi1 + vi2hi2 + + vilhil = hi1 + hi2 + + hil
46

The Minimum Distance of a Block Code Proof

Suppose that hi1, hi2, , hil are l columns of H such that (3.18) hi1 + hi2 + + hil = 0 Let x = (x1, x2, , xn-1) whose nonzero components are xi1, xi2, xil x HT = x0h0 + x1h1 + + xn-1hn-1 = xi1hi1 + xi2hi2 + + xilhil = hi1 + hi2 + + hil It following from (3.18) that x HT = 0, x is code vector of weight l in C

47

The Minimum Distance of a Block Code Let C be a linear block code with parity-check matrix H Corollary 3.2.1 If no d-1 or fewer columns of H add to 0, the code has minimum weight at least d Corollary 3.2.2 The minimum weight of C is equal to the smallest number of columns of H that sum to 0

48

Error-Detecting and Error-Correcting Capabilities of a Block Code

Error-Detecting and Error-Correcting Capabilities of a Block Code If the minimum distance of a block code C is dmin, any two distinct code vector of C differ in at least dmin places A block code with minimum distance dmin is capable of detecting all the error pattern of dmin 1 or fewer errors However, it cannot detect all the error pattern of dmin errors because there exists at least one pair of code vectors that differ in dmin places and there is an error pattern of dmin errors that will carry one into the other The random-error-detecting capability of a block code with minimum distance dmin is dmin 1
50

Error-Detecting and Error-Correcting Capabilities of a Block Code An (n, k) linear code is capable of detecting 2n 2k error patterns of length n Among the 2n 1 possible nonzero error patterns, there are 2k 1 error patterns that are identical to the 2k 1 nonzero code words If any of these 2k 1 error patterns occurs, it alters the transmitted code word v into another code word w, thus w will be received and its syndrome is zero There are 2k 1 undetectable error patterns If an error pattern is not identical to a nonzero code word, the received vector r will not be a code word and the syndrome will not be zero
51

Error-Detecting and Error-Correcting Capabilities of a Block Code These 2n 2k error patterns are detectable error patterns Let Al be the number of code vectors of weight i in C, the numbers A0, A1,..., An are called the weight distribution of C Let Pu(E) denote the probability of an undetected error Since an undetected error occurs only when the error pattern is identical to a nonzero code vector of C

Pu ( E ) = Ai p i (1 p ) n i
where p is the transition probability of the BSC If the minimum distance of C is dmin, then A1 to Admin 1 are zero
52
i =1

Error-Detecting and Error-Correcting Capabilities of a Block Code

Assume that a block code C with minimum distance dmin is used for random-error correction. The minimum dmin distance is either odd or even. Let t be a positive integer such that: 2t+1 dmin 2t+2 Fact 1: The code C is capable of correcting all the error patterns of t or fewer errors. Proof: Let v and r be the transmitted code vector and the received vector, respectively. Let w be any other code vector in C. d(v,r) + d(w,r) d(v,w) Suppose that an error pattern of t errors occurs during the transmission of v. We have d(v,r)=t.
53

Error-Detecting and Error-Correcting Capabilities of a Block Code

Since v and w are code vectors in C, we have d(v,w) dmin 2t+1. d(w,r)d(v,w)-d(v,r) dmin-t 2t+1-t t+1>t (if t t) The inequality above says that if an error pattern of t or fewer errors occurs, the received vector r is closer (in Hamming distance) to the transmitted code vector v than to any other code vector w in C. For a BSC, this means that the conditional probability P(r|v) is greater than the conditional probability P(r|w) for wv. Q.E.D.
54

Error-Detecting and Error-Correcting Capabilities of a Block Code

Fact 2: The code is not capable of correcting all the error patterns of l errors with l > t, for there is at least one case where an error pattern of l errors results in a received vector which is closer to an incorrect code vector than to the actual transmitted code vector. Proof: Let v and w be two code vectors in C such that d(v,w)=dmin. Let e1 and e2 be two error patterns that satisfy the following conditions: e1+ e2=v+w e1 and e2 do not have nonzero components in common places. We have w(e1) + w(e2) = w(v+w) = d(v,w) = dmin. (3.23)
55

Error-Detecting and Error-Correcting Capabilities of a Block Code

Suppose that v is transmitted and is corrupted by the error pattern e1, then the received vector is r = v + e1 The Hamming distance between v and r is d(v, r) = w(v + r) = w(e1). (3.24) The Hamming distance between w and r is d(w, r) = w(w + r) = w(w + v + e1) = w(e2) (3.25) Now, suppose that the error pattern e1 contains more than t errors [i.e. w(e1) t+1]. Since 2t + 1 dmin 2t +2, it follows from (3.23) that w(e2) = dmin- w(e1) (2t +2) - (t+1) = t + 1
56

Error-Detecting and Error-Correcting Capabilities of a Block Code

Combining (3.24) and (3.25) and using the fact that w(e1) t+1 and w(e2) t + 1, we have d(v, r) d(w, r) This inequality say that there exists an error pattern of l (l > t) errors which results in a received vector that is closer to an incorrect code vector than to the transmitted code vector. Based on the maximum likelihood decoding scheme, an incorrect decoding would be committed. Q.E.D.

57

Error-Detecting and Error-Correcting Capabilities of a Block Code A block code with minimum distance dmin guarantees correcting all the error patterns of t = (d min 1) / 2 or fewer errors, where (d min 1) / 2 denotes the largest integer no greater than (dmin 1)/2 The parameter t = (d min 1) / 2 is called the random-error correcting capability of the code The code is referred to as a t-error-correcting code A block code with random-error-correcting capability t is usually capable of correcting many error patterns of t + 1 or more errors For a t-error-correcting (n, k) linear code, it is capable of correcting a total 2n-k error patterns (shown in next section).
58

Error-Detecting and Error-Correcting Capabilities of a Block Code

If a t-error-correcting block code is used strictly for error correction on a BSC with transition probability p, the probability that the decoder commits an erroneous decoding is upper bounded by: n n i n i P ( E ) p (1 p ) i =t +1 i In practice, a code is often used for correctingor fewer errors and simultaneously detecting l (l >) or fewer errors. That is, whenor fewer errors occur, the code is capable of correcting them; when more than but fewer than l+1 errors occur, the code is capable of detecting their presence without making a decoding error. The minimum distance dmin of the code is at least + l+1.
59

Standard Array and Syndrome Decoding

Standard Array and Syndrome Decoding Let v1, v2, , v2k be the code vector of C Any decoding scheme used at the receiver is a rule to partition the 2n possible received vectors into 2k disjoint subsets D1, D2, , D2k such that the code vector vi is contained in the subset Di for 1 i 2k Each subset Di is one-to-one correspondence to a code vector vi If the received vector r is found in the subset Di, r is decoded into vi Correct decoding is made if and only if the received vector r is in the subset Di that corresponds to the actual code vector transmitted
61

Standard Array and Syndrome Decoding A method to partition the 2n possible received vectors into 2k disjoint subsets such that each subset contains one and only one code vector is described here
First, the 2k code vectors of C are placed in a row with the all-zero code vector v1 = (0, 0, , 0) as the first (leftmost) element From the remaining 2n 2k n-tuple, an n-tuple e2 is chosen and is placed under the zero vector v1 Now, we form a second row by adding e2 to each code vector vi in the first row and placing the sum e2 + vi under vi An unused n-tuple e3 is chosen from the remaining n-tuples and is placed under e2. Then a third row is formed by adding e3 to each code vector vi in the first row and placing e3 + vi under vi . we continue this process until all the n-tuples are used.
62

Standard Array and Syndrome Decoding

63

Standard Array and Syndrome Decoding Then we have an array of rows and columns as shown in Fig 3.6 This array is called a standard array of the given linear code C Theorem 3.3 No two n-tuples in the same row of a standard array are identical. Every n-tuple appears in one and only one row Proof
The first part of the theorem follows from the fact that all the code vectors of C are distinct Suppose that two n-tuples in the lth rows are identical, say el + vi = el + vj with i j This means that vi = vj, which is impossible, therefore no two n-tuples in the same row are identical
64

Standard Array and Syndrome Decoding Proof

It follows from the construction rule of the standard array that every n-tuple appears at least once Suppose that an n-tuple appears in both lth row and the mth row with l < m Then this n-tuple must be equal to el + vi for some i and equal to em + vj for some j As a result, el + vi = em + vj From this equality we obtain em = el + (vi + vj) Since vi and vj are code vectors in C, vi + vj is also a code vector in C, say vs This implies that the n-tuple em is in the lth row of the array, which contradicts the construction rule of the array that em, the first element of the mth row, should be unused in any previous row No n-tuple can appear in more than one row of the array
65

Standard Array and Syndrome Decoding From Theorem 3.3 we see that there are 2n/2k = 2n-k disjoint rows in the standard array, and each row consists of 2k distinct elements The 2n-k rows are called the cosets of the code C The first n-tuple ej of each coset is called a coset leader Any element in a coset can be used as its coset leader

66

Standard Array and Syndrome Decoding Example 3.6 consider the (6, 3) linear code generated by the following matrix :

0 1 1 1 0 0 G= 1 0 1 0 1 0 1 1 0 0 0 1
The standard array of this code is shown in Fig. 3.7

67

Standard Array and Syndrome Decoding

68

Standard Array and Syndrome Decoding A standard array of an (n, k) linear code C consists of 2k disjoint columns Let Dj denote the jth column of the standard array, then (3.27) Dj = {vj, e2+vj, e3+vj, , e2n-k + vj}
vj is a code vector of C and e2, e3, , e2n-k are the coset leaders

The 2k disjoint columns D1, D2, , D2k can be used for decoding the code C. Suppose that the code vector vj is transmitted over a noisy channel, from (3.27) we see that the received vector r is in Dj if the error pattern caused by the channel is a coset leader If the error pattern caused by the channel is not a coset leader, an erroneous decoding will result
69

Standard Array and Syndrome Decoding The decoding is correct if and only if the error pattern caused by the channel is a coset leader The 2n-k coset leaders (including the zero vector 0) are called the correctable error patterns Theorem 3.4 Every (n, k) linear block code is capable of correcting 2n-k error pattern To minimize the probability of a decoding error, the error patterns that are most likely to occur for a given channel should be chosen as the coset leaders When a standard array is formed, each coset leader should be chosen to be a vector of least weight from the remaining available vectors
70

Standard Array and Syndrome Decoding Each coset leader has minimum weight in its coset The decoding based on the standard array is the minimum distance decoding (i.e. the maximum likelihood decoding) Let i denote the number of coset leaders of weight i, the numbers 0 , 1 ,,n are called the weight distribution of the coset leaders Since a decoding error occurs if and only if the error pattern is not a coset leader, the error probability for a BSC with transition probability p is

P(E) =1 i p i (1 p ) n i
i =0

71

Standard Array and Syndrome Decoding Example 3.7

The standard array for this code is shown in Fig. 3.7 The weight distribution of the coset leader is 0 =1, 1 = 6, 2=1 and 3 =4 =5 =6 = 0 Thus, P(E) = 1 (1 p)6 6p(1 p)5 p2(1 p)4 For p = 10-2, we have P(E) 1.37 10-3

72

Standard Array and Syndrome Decoding An (n, k) linear code is capable of detecting 2n 2k error patterns, it is capable of correcting only 2 nk error patterns The probability of a decoding error is much higher than the probability of an undetected error Theorem 3.5
(1) For an (n, k) linear code C with minimum distance dmin, all the n-tuples of weight of t = (d min 1) / 2 or less can be used as coset leaders of a standard array of C. (2) If all the n-tuple of weight t or less are used as coset leader, there is at least one n-tuple of weight t + 1 that cannot be used as a coset leader
73

Standard Array and Syndrome Decoding Proof of the (1)

Since the minimum distance of C is dmin , the minimum weight of C is also dmin Let x and y be two n-tuples of weight t or less The weight of x + y is w(x + y) w(x) + w(y) 2t < dmin (2t+1 dmin 2t+2) Suppose that x and y are in the same coset, then x + y must be a nonzero code vector in C This is impossible because the weight of x+y is less than the minimum weight of C. No two n-tuple of weight t or less can be in the same coset of C All the n-tuples of weight t or less can be used as coset leaders
74

Standard Array and Syndrome Decoding Proof of the (2)

Let v be a minimum weight code vector of C ( i.e., w(v) = dmin ) Let x and y be two n-tuples which satisfy the following two conditions:
x+y=v x and y do not have nonzero components in common places

It follows from the definition that x and y must be in the same coset and w(x) + w(y) = w(v) = dmin Suppose we choose y such that w(y) = t + 1 Since 2t + 1 dmin 2t + 2, we have w(x)=t or t+1. If x is used as a coset leader, then y cannot be a coset leader.
75

Standard Array and Syndrome Decoding Theorem 3.5 reconfirms the fact that an (n, k) linear code with minimum distance dmin is capable of correcting all the error pattern of (d min 1) / 2 or fewer errors But it is not capable of correcting all the error patterns of weight t + 1 Theorem 3.6 All the 2k n-tuples of a coset have the same syndrome. The syndrome for different cosets are different Proof
Consider the coset whose coset leader is el A vector in this coset is the sum of el and some code vector vi in C The syndrome of this vector is (el + vi)HT = elHT + viHT = elHT
76

Standard Array and Syndrome Decoding Proof

Let ej and el be the coset leaders of the jth and lth cosets respectively, where j < l Suppose that the syndromes of these two cosets are equal Then, ejHT = elHT (ej + el)HT = 0 This implies that ej + el is a code vector in C, say vj Thus, ej + el = vi and el = ej + vi This implies that el is in the jth coset, which contradicts the construction rule of a standard array that a coset leader should be previously unused
77

Standard Array and Syndrome Decoding The syndrome of an n-tuple is an (nk)-tuple and there are 2n-k distinct (nk)-tuples From theorem 3.6 that there is a one-to-one correspondence between a coset and an (nk)-tuple syndrome Using this one-to-one correspondence relationship, we can form a decoding table, which is much simpler to use than a standard array The table consists of 2n-k coset leaders (the correctable error pattern) and their corresponding syndromes This table is either stored or wired in the receiver
78

Standard Array and Syndrome Decoding The decoding of a received vector consists of three steps:
Step 1. Compute the syndrome of r, r HT Step 2. Locate the coset leader el whose syndrome is equal to r HT, then el is assumed to be the error pattern caused by the channel Step 3. Decode the received vector r into the code vector v i.e., v = r + el

The decoding scheme described above is called the syndrome decoding or table-lookup decoding

79

Standard Array and Syndrome Decoding Example 3.8 Consider the (7, 4) linear code given in Table 3.1, the parity-check matrix is given in example 3.3
The code has 23 = 8 cosets There are eight correctable error patterns (including the all-zero vector) Since the minimum distance of the code is 3, it is capable of correcting all the error patterns of weight 1 or 0 All the 7-tuples of weight 1 or 0 can be used as coset leaders The number of correctable error pattern guaranteed by the minimum distance is equal to the total number of correctable error patterns
80

Standard Array and Syndrome Decoding

The correctable error patterns and their corresponding syndromes are given in Table 3.2

81

Standard Array and Syndrome Decoding Suppose that the code vector v = (1 0 0 1 0 1 1) is transmitted and r = (1 0 0 1 1 1 1) is received For decoding r, we compute the syndrome of r 1 0 0 0 1 0 0 0 1 s = (1 0 0 1 1 1 1) 1 1 0 = ( 0 1 1) 0 1 1 1 1 1 1 0 1
82

Standard Array and Syndrome Decoding From Table 3.2 we find that (0 1 1) is the syndrome of the coset leader e = (0 0 0 0 1 0 0), then r is decoded into v* = r + e = (1 0 0 1 1 1 1) + (0 0 0 0 1 0 0) = (1 0 0 1 0 1 1)
which is the actual code vector transmitted The decoding is correct since the error pattern caused by the channel is a coset leader

83

Standard Array and Syndrome Decoding Suppose that v = (0 0 0 0 0 0 0) is transmitted and r = (1 0 0 0 1 0 0) is received We see that two errors have occurred during the transmission of v The error pattern is not correctable and will cause a decoding error When r is received, the receiver computes the syndrome s = r HT = (1 1 1) From the decoding table we find that the coset leader e = (0 0 0 0 0 1 0) corresponds to the syndrome s = (1 1 1)
84

Standard Array and Syndrome Decoding r is decoded into the code vector v* = r + e = (1 0 0 0 1 0 0) + (0 0 0 0 0 1 0) = (1 0 0 0 1 1 0) Since v* is not the actual code vector transmitted, a decoding error is committed Using Table 3.2, the code is capable of correcting any single error over a block of seven digits When two or more errors occur, a decoding error will be committed
85

Standard Array and Syndrome Decoding The table-lookup decoding of an (n, k) linear code may be implemented as follows The decoding table is regarded as the truth table of n switch functions : e0 = f 0 ( s0 , s1 ,..., sn k 1 )

e1 = f1 ( s0 , s1 ,..., sn k 1 ) . . en 1 = f n 1 ( s0 , s1 ,..., sn k 1 )
where s0, s1, , sn-k-1 are the syndrome digits where e0, e1, , en-1 are the estimated error digits
86

Standard Array and Syndrome Decoding The general decoder for an (n, k) linear code based on the table-lookup scheme is shown in Fig. 3.8

87

Standard Array and Syndrome Decoding Example 3.9 Consider the (7, 4) code given in Table 3.1
The syndrome circuit for this code is shown in Fig. 3.5 The decoding table is given by Table 3.2 From this table we form the truth table (Table 3.3) The switching expression for the seven error digits are
' e0 = s0 s1' s2 ' s1' s2 e2 = s0 ' s1 s2 e4 = s0 ' ' s1 s2 e1 = s0 ' e3 = s0 s1 s2

e5 = s0 s1 s2

where denotes the logic-AND operation where s denotes the logic-COMPLENENT of s

88

e6 = s0 s1' s2

Standard Array and Syndrome Decoding

89

Standard Array and Syndrome Decoding The complete circuit of the decoder is shown in Fig. 3.9

90

Probability of An Undetected Error for Linear Codes Over a BSC

Probability of An Undetected Error for Linear Codes Over a BSC Let {A0, A1, , An} be the weight distribution of an (n, k) linear code C Let {B0, B1, , Bn} be the weight distribution of its dual code Cd Now we represent these two weight distribution in polynomial form as follows : A(z) = A0 + A1z + + Anzn B(z) = B0 + B1z + + Bnzn (3.31) Then A(z) and B(z) are related by the following identity : A(z) = 2 -(n-k) (1 + z)n B(1 z / 1 + z) (3.32) This identity is known as the MacWilliams identity
92

Probability of An Undetected Error for Linear Codes Over a BSC The polynomials A(z) and B(z) are called the weight enumerators for the (n, k) linear code C and its dual Cd Using the MacWilliams identity, we can compute the probability of an undetected error for an (n, k) linear code from the weight distribution of its dual. From equation 3.19:

Pu ( E ) = Ai p (1 p )
i i =1 n n

n i

p i = (1 p ) Ai ( ) 1 p i =1
93

(3.33)

Probability of An Undetected Error for Linear Codes Over a BSC Substituting z = p/(1 p) in A(z) of (3.31) and using the fact that A0 = 1, we obtain

p p A 1 = Ai i =1 1 p 1 p
n

(3.34)

Combining (3.33) and (3.34), we have the following expression for the probability of an undetected error

p Pu ( E ) = (1 p ) [ A 1] 1 p
n

(3.35)

94

Probability of An Undetected Error for Linear Codes Over a BSC From (3.35) and the MacWilliams identity of (3.32), we finally obtain the following expression for Pu(E) : (3.36) Pu(E) = 2-(n k) B(1 2p) (1 p)n where n B(1 2 p ) = Bi (1 2 p )i
i =0

Hence, there are two ways for computing the probability of an undetected error for a linear code; often one is easier than the other. If n-k is smaller than k, it is much easier to compute Pu(E) from (3.36); otherwise, it is easier to use (3.35).
95

Probability of An Undetected Error for Linear Codes Over a BSC Example 3.10 consider the (7, 4) linear code given in Table 3.1
The dual of this code is generated by its parity-check matrix

Taking the linear combinations of the row of H, we obtain the following eight vectors in the dual code (0 0 0 0 0 0 0), (1 1 0 0 1 0 1), (1 0 0 1 0 1 1), (1 0 1 1 1 0 0), (0 1 0 1 1 1 0), (0 1 1 1 0 0 1), (0 0 1 0 1 1 1), (1 1 1 0 0 1 0)
96

1 H = 0 0

0 1 0

0 0 1

1 1 0

0 1 1 1 1 0 1 1 1

Probability of An Undetected Error for Linear Codes Over a BSC Example 3.10
Thus, the weight enumerator for the dual code is B(z) = 1 + 7z4 Using (3.36), we obtain the probability of an undetected error for the (7, 4) linear code given in Table 3.1 Pu(E) = 2-3[1 + 7(1 2p)4] (1 p)7 This probability was also computed in Section 3.4 using the weight distribution of the code itself

97

Probability of An Undetected Error for Linear Codes Over a BSC For large n, k, and n k, the computation becomes practically impossible Except for some short linear codes and a few small classes of linear codes, the weight distributions for many known linear code are still unknown Consequently, it is very difficult to compute their probability of an undetected error

98

Probability of An Undetected Error for Linear Codes Over a BSC

It is quite easy to derive an upper bound on the average probability of an undetected error for the ensemble of all (n, k) linear systematic codes

n i n i Pu ( E ) 2 p p (1 ) i =1 i = 2 ( n k ) [1 (1 p ) n ]
(nk ) n

(3.42)

Since [1 (1 p)n] 1, it is clear that Pu(E) 2(n k). There exist (n,k) linear codes with probability of an undetected error, Pu(E), upper bounded by 2-(n-k). Only a few small classes of linear codes have been proved to have Pu(E) satisfying the upper bound 2-(n-k).
99

Hamming Codes

Hamming Codes
These codes and their variations have been widely used for error control in digital communication and data storage systems For any positive integer m 3, there exists a Hamming code with the following parameters :
Code length: n = 2m 1 Number of information symbols: k = 2m m 1 Number of parity-check symbols: nk=m Error-correcting capability : t = 1( dmin = 3) The parity-check matrix H of this code consists of all the nonzero m-tuple as its columns (2m-1).
101

Hamming Codes
In systematic form, the columns of H are arranged in the following form : H = [Im Q]
where Im is an m m identity matrix The submatrix Q consists of 2m m 1 columns which are the m-tuples of weight 2 or more

The columns of Q may be arranged in any order without affecting the distance property and weight distribution of the code
102

Hamming Codes
In systematic form, the generator matrix of the code is G = [QT I2mm1]
where QT is the transpose of Q and I 2mm1 is an (2m m 1) (2m m 1) identity matrix

Since the columns of H are nonzero and distinct, no two columns add to zero Since H consists of all the nonzero m-tuples as its columns, the vector sum of any two columns, say hi and hj, must also be a column in H, say hl hi + hj + hl = 0 The minimum distance of a Hamming code is exactly 3
103

Hamming Codes
The code is capable of correcting all the error patterns with a single error or of detecting all the error patterns of two or fewer errors If we form the standard array for the Hamming code of length 2m 1
All the (2m1)-tuple of weight 1 can be used as coset leaders The number of (2m1)-tuples of weight 1 is 2m 1 Since n k = m, the code has 2m cosets The zero vector 0 and the (2m1)-tuples of weight 1 form all the coset leaders of the standard array
104

Hamming Codes
A t-error-correcting code is called a perfect code if its standard array has all the error patterns of t or fewer errors and no others as coset leader Besides the Hamming codes, the only other nontrivial binary perfect code is the (23, 12) Golay code (section 5.3) Decoding of Hamming codes can be accomplished easily with the table-lookup scheme

105

Hamming Codes
We may delete any l columns from the parity-check matrix H of a Hamming code This deletion results in an m (2m l 1) matrix H' Using H' as a parity-check matrix, we obtain a shortened Hamming code with the following parameters :
Code length: n = 2m l 1 Number of information symbols: k = 2m m l 1 Number of parity-check symbols: nk=m Minimum distance : dmin 3 If we delete columns from H properly, we may obtain a shortened Hamming code with minimum distance 4
106

Hamming Codes
For example, if we delete from the submatrix Q all the columns of even weight, we obtain an m x 2m-1 matrix. H=[Im Q] Q consists of 2m-1-m columns of odd weight. Since all columns of H have odd weight, no three columns add to zero. However, for a column hi of weight 3 in Q, there exists three columns hj, hl, and hs in Im such that hi +hj+hl+hs=0. Thus, the shortened Hamming code with H as a parity-check matrix has minimum distance exactly 4. The distance 4 shortened Hamming code can be used for correcting all error patterns of single error and simultaneously detecting all error patterns of double errors
107

Hamming Codes
When a single error occurs during the transmission of a code vector, the resultant syndrome is nonzero and it contains an odd number of 1s (e x HT corresponds to a column in H) When double errors occurs, the syndrome is nonzero, but it contains even number of 1s Decoding can be accomplished in the following manner : If the syndrome s is zero, we assume that no error occurred If s is nonzero and it contains odd number of 1s, we assume that a single error occurred. The error pattern of a single error that corresponds to s is added to the received vector for error correction If s is nonzero and it contains even number of 1s, an uncorrectable error pattern has been detected
108

Hamming Codes
The dual code of a (2m1, 2mm1) Hamming code is a (2m1,m) linear code If a Hamming code is used for error detection over a BSC, its probability of an undetected error, Pu(E), can be computed either from (3.35) and (3.43) or from (3.36) and (3.44) Computing Pu(E) from (3.36) and (3.44) is easier Combining (3.36) and (3.44), we obtain m-1 m1 -m m 2 2 Pu(E) = 2 {1+(2 1)(1 2p) } (1 p) The probability Pu(E) for Hamming codes does satisfy the upper bound 2(nk) = 2-m for p [i.e., Pu(E) 2-m]
109

Single-Parity-Check Codes, Repetition Codes, and Self-Dual Codes

Single-Parity-Check Codes, Repetition Codes, and Self-Dual Codes

A single-parity-check (SPC) code is a linear block code with a single parity-check digit. Let u=(u0,u1,,uk-1) be the message to be encoded. The single parity-check digit is given by p= u0+u1++uk-1 which is simply the modulo-2 sum of all the message digits. Adding this parity-check digit to each k-digit message results in a (k+1,k) linear block code. Each codeword is of the form v=(p,u0,u1,,uk-1) p=1(0) if the weight of message u is odd(even). All the codewords of a SPC code have even weights, and the minimum weight (or minimum distance) of the code is 2.
111

Single-Parity-Check Codes, Repetition Codes, and Self-Dual Codes

The generator of the code in systematic form is given by
1 1 G = 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 = 1 0 0 0 0 1 1 Ik

The parity-check matrix of the code is H = [1 1 1] A SPC code is also called an even-parity-check code. All the error patterns of odd weight are detectable.
112

Single-Parity-Check Codes, Repetition Codes, and Self-Dual Codes

A repetition code of length n is an (n,1) linear block code that consists of only two codewords, the all-zero codeword (000) and the all-one codeword (111). This code is obtained by simply repeating a single message bit n times. The generator matrix of the code is H = [1 1 1] From the generator matrixes, we see that the (n,1) repetition code and the (n,n-1) SPC code are dual codes to each other. A linear block code C that is equal to its dual code Cd is called a self-dual code. For a self-dual code, the code length n must be even, and the dimension k of the code must be equal to n/2. => Rate=1/2.
113

Single-Parity-Check Codes, Repetition Codes, and Self-Dual Codes

Let G be a generator matrix of a self-dual code C. Then, G is also a generator matrix of its dual code Cd and hence is a parity-check matrix of C. Consequently, GGT=0 Suppose G is in systematic form, G=[P In/2]. We can see that PPT=In/2 Conversely, if a rate (n,n/2) linear block code C satisfies the condition of GGT=0 or PPT=In/2, then it is a self-dual code. 1 1 1 1 1 1 1 1 Example: the (8,4) linear block 0 0 0 0 1 1 1 1 code generated by the following G= 0 0 1 1 0 0 1 1 matrix has a rate R= and is a self-dual code since GGT=0. 0 1 0 1 0 1 0 1
114