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

ISBN 0471-49581-6

**Download**(direct link)

**:**

**19**> 20 21 22 23 24 25 .. 86 >> Next

v\ + V2 + v3 + v5 = 0 V2 + v3 + Vi + ve = 0 V3 + V4 + v5 + v7 = 0 V\ + t>4 + V5 + ve = 0 V2 + v5 + ve + v7 = 0 V\ + V3 + Ve +v7 = 0

Vi + V2 + V4 + v7 — 0 (2.13)

5 See Chapter 3.

32

THE ART OF ERROR CORRECTING CODING

open at . n=7

Figure 15 A majority-logic decoder for a cyclic RM*(1,3) code.

In a manner similar to the previous example, the syndromes Si and S2 below are orthogonal on V4 and vr,, and S2 and S3 are orthogonal on v5 and v(;:

51 = e3 + &4 + es + ej

52 = ei + 64 + 65 + e6

53 = e2 + 65 + + 67 (2.14)

Based on the estimates e\ + e'~ and e'5 + e'6 two additional orthogonal equations on e5 can be formed to give the final estimate,

SJ = e'4 + e'5

S^ = e'+e; (2.15)

where e'j;, j = 4. 5,6, represents the ML estimate from the previous step. This results in the circuit shown in the Figure 15. The circuit operates as follows. Initially the contents of the seven-bit register are set to zero. Suppose that a single error is contained in the received word in position i, for 1 < i < 7. At each clock cycle, the contents of the register are cyclically shifted to the right by one position. Time, in clock cycles, is denoted by the subindex n in the following.

Consider first the case i = 1. That is, there is an error in the first codeword position. After three cycles, the error is contained in register 5 (115). The output of the majority-logic circuit is set to en = 1. Four cycles later (a total of seven cycles), the first received bit is output and the error corrected. Consider now the case i — 7. After nine cycles, the error is detected and en = 1. Again, four cycles later (total 13 cycles), the bit in the last position is output and the

error corrected. This decoder has a latency of 13 cycles. Every 13 cycles, the contents of the

shift register are cleared and a new codeword can be processed.

In the next chapter, binary cyclic codes and the powerful family of BCH codes are introduced.

The Art of Error Correcting Coding Robert H. Morelos-Zaragoza Copyright © 2002 John Wiley & Sons Ltd ISBNs: 0-471-49581-6 (Hardback); 0-470-84782-4 (Electronic)

3

Binary cyclic codes and BCH codes

The aim of this chapter is to introduce a minimum set of concepts necessary for the understanding of binary cyclic codes and for the efficient implementation of their encoding and decoding procedures. Also in this chapter, the important family of binary BCH codes is introduced. BCH codes are a family of cyclic codes, which gives them an algebraic structure that is useful in simplifying their encoding and decoding procedures. Binary BCH codes with minimum distance 3, better known as Hamming codes, have been a very popular choice in computer networks and in memories, due to their simple and fast encoding and decoding. Also, a shortened (48,36,5) BCH code is used in the U.S. cellular TDMA system specification, standard IS-54.

3.1 Binary cyclic codes

Cyclic codes are a class of error correcting codes that can be efficiently encoded and decoded using simple shift-registers and combinatorial logic elements, based on their representation using polynomials. In this section, the fundamental concepts of cyclic codes are discussed.

3.1.1 Generator and parity-check polynomials

Let C denote a linear (n, k) block code. Let u and v denote a message and the corresponding codeword in C, respectively. Cyclic codes are linear codes with properties that make them suitable for hardware implementation. To every codeword v a polynomial v(x) is associated,

V = (v0, Vi, ? ? ? , Vn-i) l-> v(x) = V0 + ViX + ? ? ? vn-iXn_1.

The indeterminant x serves to indicate the relative position of an element t'i of v as a term

ViX1 of u(x), 0 < i < n.

A linear block code C is cyclic if and only if every cyclic shift of a codeword is another codeword,

V = {v0,vi, ? ? ? ,vn-i) ? C •?=>• u(1) = («„_!, u0, ? ? ? ,U„_2) e C.

In the language of polynomials, a cyclic shift by one position, denoted «^(x), is

accomplished by a multiplication by x modulo (xn — 1),

v(x) ? C <s=4* v^(x) = xv(x) mod (xn — 1) ? C.

Shift-registers can be used for this purpose, as illustrated in Figure 16.

34

THE ART OF ERROR CORRECTING CODING

Figure 16 A cyclic shift register

Example 19 Consider the case of n = 7. Then, a cyclic shift by one position of the vector v = (0101011) equals v^ = (1010101). In terms of polynomials, v(x) — x + x3 + x5 + x6 and

(x) = xv{x) = x2 + x4 + x6 + x7 mod (x7 + 1)

= x2 + x4 + x6 + x7 + (x7 + 1) + 1

= 1 + x2 + x4 + xe

3.1.2 The generator polynomial

An important property of cyclic codes is that all code polynomials v(x) are multiples of a unique polynomial, g(x), called the generator polynomial of the code. This polynomial is specified by its roots, which are called the zeros of the code. It can be shown that the

generator polynomial g(x) divides (xn — 1). (As with integers, “a(x) divides b{x)" whenever

b(x) = q{x)a{x).) Therefore, to find a generator polynomial, the polynomial (xn — 1) must be factored into its irreducible factors, cj)j(x), j = 1.2. ? ? •, I,

**19**> 20 21 22 23 24 25 .. 86 >> Next