0 0 . . . 0 1 1

r 1 1

2:8

where HSEC is an H matrix of a single-error correcting (SEC) code, and r n k. De nition 2.25 An n; k single-bit error correcting and double-bit error detecting (SEC-DED) code is de ned and expressed by an r n H matrix shown in Eq.(2.8). & Unlike the SEC code this code requires an extra overall parity check of its encoding and decoding. In the encoding the following overall parity bit cr is generated and appended to the remaining r 1 generated check bits: cr 1 d0 d1 dk 1 c0 c1 cr 2 : The syndrome calculation is performed in the same way by making a parity calculation:

0 0 0 Sr 1 d0 d1 dk 1 c00 c01 c0r 1 :

The decoding of the SEC-DED codes is performed by the calculated syndrome S S0 ; S1 ; . . . ; Sr 1 as follows: Step 1. If S 0, then the received word is error-free. Step 2. If S 6 0 and Sr 1 1, then an odd number of errors, likely single-bit errors, have occurred. If the syndrome pattern is identical to a column vector in H, the corresponding bit is in error and then inverted, that is, corrected. If the syndrome pattern is not identical

. . .

to any column vector in H, then three or the larger odd number of errors is detected. That is, uncorrectable errors are detected. Step 3. If S 6 0 and Sr 1 0, then the even number of errors, likely double-bit errors, are detected. As a result uncorrectable errors are detected. A modi ed Hamming SEC-DED code will be discussed in 4. It is constructed by using all odd-weight-column vectors in the H matrix. That is, there is no overall parity check. This code is called an odd-weight-column SEC-DED code, or a modi ed Hamming SEC-DED code, which brings smaller decoder hardware and higher decoding speed than the Hamming SEC-DED code [HSIA70]. It can be easily proved that the n; k binary SEC-DED codes have the maximum code length in bits n 2n k 1 . 2.3.4 Cyclic Codes

Cyclic codes are a class of typical linear polynomial codes. Encoding and decoding are performed mainly by linear feedback shift register (LFSR) circuits and therefore operated serially bit by bit. There are ef cient cyclic codes for detecting and / or correcting random errors, burst errors, and byte errors. They have inherent algebraic structure, and hence there exist various serial decoding methods. Usually the codes are expressed by generator polynomials. Algebraic Structure of Cyclic Codes First, we consider the codeword of a linear cyclic code C over GF q as v vn 1 vn 2 . . . v2 v1 v0 , called a code vector, where vj 2 GF q ; j 0; 1; . . . ; n 1. In a cyclic code this n-tuple vector is expressed by polynomial over GF q . That is, v x vn 1 xn 1 v1 x v0 : This is called a code polynomial of v. There exists a one-to-one correspondence between the code vector v and the code polynomial v x . Here we have another vector v i that is cyclically shifted i places to the left in the previous n-tuple vector v, called a cyclic i-shift of v: v i vn i 1 vn i 2 . . . v2 v1 v0 vn 1 vn 2 . . . vn i 1 vn i : The code polynomial that corresponds to the code vector v i is v i x vn i 1 xn 1 vn i 2 xn 2 v2 xi 2 v1 xi 1 v0 xi vn 1 xi 1 vn 2 xi 2 vn i 1 x vn i : 2:9

De nition 2.26 An n; k linear code C is called a cyclic code if every cyclic shift of a code vector in C is also a code vector in C. & The code polynomial corresponding to v i is expressed as xi v x mod xn 1: