Networking Explained, 2nd Edition

Appendix B

Using Parity for Single-Bit Error

Correction

Let’s define a codeword to have the following structure (each X

i

is a bit in the data set):

X

1

X

2

X

3

X

4

X

5

X

6

X

7

X

8

X

9

X

10

X

11

X

12

. . .

Also, let every bit with a subscript that is a power of 2 be a check bit, denoted by r

j

, which

will contain redundant information for error correction. Thus, X

1

, X

2

, X

4

, and X

8

are check

bits and we replace them with r

1

, r

2

, r

4

, and r

8

, respectively.

r

1

r

2

X

3

r

4

X

5

X

6

X

7

r

8

X

9

X

10

X

11

X

12

. . .

Since the X

i

bits are predetermined (they represent user data), we need a rule for forming

check bits. This rule is based on parity and is defined as follows:

Each check bit, r

j

, is formed by collecting all corresponding X

i

bits. These are determined

by expressing the subscript of each X

i

as ...