Cyclic codes In going from arbitrary block codes to linear codes the characteristic of linearity enables the minimum distance and therefore error-control capabilities of codes to be easily determined, and encoding and decoding can be concisely described in terms of matrix algebra. A second characteristic is now considered, namely that codewords are cyclic, and in doing so further gains are made, in particular with regard to the implementation of encoding and decoding. 1 Definition of cyclic codes With cyclic codes it is conventional to think of codewords as starting with the component ¢,_1 and ending with co, and as such codewords are represented as © = (Cnty On-25 C15 €0)+ This representation proves more convenient than that previously used, namely €=(€1,€2y--sCn-1s€n)+and should not cause confusion. The coefficients cand ¢y_1 are now referred to as the least-order and highest-order coefficients respectively, and define the low-order and high-order sides of c. A cyclic shift leftwards ona codeword c is one in which each bit is shifted one place towards the left with the bit ¢,,_ ‘occupying the position vacated by co. The resulting word is ¢ = (Ca-25n—35- ++» C00€n-1) Bits can be shifted towards the right in a similar manner, and shifts may be by more than one bit. So, for example, a cyclic shift on ¢’ of 4 bits towards the right gives ol = (€2,€1, C0, €n-1y +++ C4563): A cyclic code is a linear code that has the property that a cyclic shift on any of its codewords produces another codeword. The cyclic shift may be leftwards or rightwards by any number of places. Hence fe given above isa codeword of an (n, k) cyclic code then e’ and ¢" are also codewords. Example 3.1 Returning to the (7,4) Hamming code we find that all the codewords satisfy the cyclic requirement. For example, let’s consider the codeword ¢5=(0011101) given in Table 1.6. A shift of 2 places to the left produces (1110100), which is the codeword c14. A further shift of 3 places to the left gives (0 100111), which is ¢q and a shift of 1 place to the right gives e¢19=(1010011). a The above example does not prove that the (7, 4) Hamming code is cyclic, it only shows that some of its codewords have the required cyclic property. However, the74 | Cyclic codes code is indeed cyclic, the reader may wish to consider cyclic shifts on other code- words. Not all linear codes are cyclic. A linear code may have some codewords that satisfy the cyclic requirement, but other codewords that fail to do so, such codes are therefore not cyclic Example 3.2 Consider the (5, 2) linear code with nonzero codewords = (01101) e2= (10111) 3 = (11010). A leftwards shift of 1 bit on ¢; produces ¢3, but a further shift of 1 bit leftwards gives (10101) which is not a codeword. The (5,2) linear code is therefore not cyclic. a 3.2 Polynomials Ascyclic codes are linear, encoding and decoding can be achieved in the same way as for linear codes, namely using matrices. However, with cyclic codes, a polynomial representation of codewords is often more suitable and encoding and decoding rules can be formulated in terms of polynomial algebra. Before proceeding to consider cyclic codes in terms of polynomials, it is useful to look at polynomial addition, subtraction, multiplication, and division, for these are required for encoding and decoding cyclic codes. An n-bit word (dy 1, dy +) can be represented by the polynomial +, P(X) = yx"! yx? + +++ + aX? + 4X + ag (3.1) where the n components of the Word dy_1, dy2.++++@2- 41, do form the polynomial coefficients. Note that the highest possible power of x in the polynomial repre~ sentation of an.n-bit word ism — 1. For a binary word, the components a, are binary and hence the polynomial coefficients are 0 or 1. For example, the words (0110 010) and (00101 1) give the polynomials pilx) = + x4 +x and px) =P +x4+1 respectively. The degree of a polynomial is the largest power of x that has a nonzero coefficient. The above polynomials p (x) and p3(x) have degrees Sand 3 respectively. Two polynomials can be added together by adding the polynomial coefficients pairwise, so the sum of the two polynomials PalX) = Oy aX"" + ayaX? 4 --- + ap? + ax + ay and Pol)Generator polynomials | 79 Example 3.6 Given that p)(x) = x°+.x? + 1 and po(x) = 2° + x represent two 7-bit words w and >, Using eqn 3.6 find the resulting words when w, and w2 are shifted leftwards by 1 place. For pi(x) = x* + x7 + 1, the product xp(x) gives x” + x° + x. Dividing x73 +x by x” + | gives the remainder x? + + | which corresponds to the 7-bit word (00.0 101 1), Asa check, note that pi(x) = x° +.x7 + 1 gives the 7-bit word (1000101), which when shifted | place towards the left gives (0001011) as already obtained. Given px(x) =" +x, then xp(x)=x'+ x7 and dividing by x’+1 gives the remainder x*+ x, Hence the required word is (0.0 1 01 0.0). We can again easily check that this is correct, Note that here the degree of xp(x) is less than 7 and so ing xp(x) by x’ +1 gives xp(x) as the remainder (with a zero quotient). We now reconsider polynomial multiplication. We have already considered the product of two arbitrary polynomials p;(x) and p,(x), and we have seen that the degree of p(x) = p;(x)p2(x) is the sum of the degrees of p)(x) and p(x). If pi(x) and a(x) represent n-bit words then the degree of p(x) = p;(x)p2(x) could be greater than n— 1, in which case p(x) could not represent an n-bit word. To address this, we define a second kind of multiplication that ensures that the degree of the product of two polynomials does not exceed n ~ 1. Given the polynomials p,(x) and p2(x) then P(x) = Resi[pi(x)p2(x)] (3.7) has degree less than or equal to n— 1 and can therefore represent an n-bit word Consider, for example, p) = x* + x and py = x° +x +1 representing two 5-bit words (1.0010) and (01011) respectively. The product py(x)po(x) =x’ +.x° +x? +x has degree 7 and therefore cannot represent words with less than 8 bits. However the remainder of p,(x)p2(x) divided by x° +1 gives x + 1 which can be expressed as the S-bit word (0001 1). 3.3 Generator polynomials Consider an (n,k) cyclic code with codeword © = (Cn-15€n-24-+ + 5€25€15€0)- The coefficients of the codeword can be used to construct a codeword polynomial (x) = Cuaax"! + Cn + 02x +.c1x + ¢9 so giving a polynomial representation of e. We now return to the (7,4) Hamming code which, as we have already seen, is a cyclic code. The first nonzero codeword, in the list of codewords given in Table 1.6, is = (0001011)80 | Cyclic codes which can be expressed as x(x) = Ox® + Ox5 + Ox4 + Lx? + Ox? + Le +1 that is a(x) =P 4x41 Table 3.1 shows the codeword polynomials, and corresponding codewords, for all the codewords belonging to the (7, 4) Hamming code. Consider now the codewords ¢, = (000101 1) and e)=(00101 10) with code- word polynomials ¢(x)=x°+x+1 and cy(x)=x‘+x?+x respectively. The codeword e; can be obtained from a single leftwards cyclic shift of ¢), and the cyclic relationship between the 2 codewords can be represented as eo(x) x8 +2 +e =x( txt) = xe\(x) Further cyclic shifts of ¢, produce the codeword polynomials ¢s(x) and en (x) = Pei(x). Table 3.1 The (7,4) codewords and codeword polynomials Codewords ¢ Codeword polynomials ex) 9 =(0000000) e=(0001011) 2=(0010110) es=(0011101) e4=(0100111) ¢5=(0101100) ¢=(0110001) e7=(0111010) ¢s=(1000101) e=(1001110) Pextxtgxt text]Encoding cyclic codes | 81 Other codeword polynomials can be generated from (x) by multiplying c,(x) with polynomials of degree less than or equal to 3. For example (x+ Der. f+ +x + b= s(x) ? = c1a(x). (2 + Pe (x) = x8 4 8 4 xt x’ Furthermore, the product of c\(x)= x’ + x +1 with every polynomial of degree less than or equal to 3 produces the complete set of codeword polynomials of the (7, 4) code. The polynomial x*+.x+1 is therefore able to generate all the codeword polynomials of the (7, 4) code, it is called a generator polynomial and is denoted by a(x). The existence of a generator polynomial is not restricted to the (7,4) cyclic code, but is an important property of all cyclic codes. In an (n, k) cyclic code there exists a unique generator polynomial from which all the codeword polynomials can be generated. The generator polynomial is unique within the code and so none of the other codeword polynomials are able to generate the complete set of codeword polynomials. The generator polynomial can be likened to the generator matrix of a linear code, in that they are capable of generating all the codewords of a code, and in Section 3.9 the relationship between generator polynomials and matrices will be considered. For an (n, k) binary cyclic code the generator polynomial has the form 80%) = Bt + Bake +o + gx? + Bx + go (3.8) where the coefficients gy 1,8n-k-2»- +8281 ate 0 oF I. The coefficients of the first and last terms are always equal to I, and so Bn-k = 1 go= 1. The x"~* term is always present in the generator polynomial and there are no higher order terms, therefore the degree of the generator polynomial g(x) of an (n,k) cyclic code is n—k. Furthermore, the product of g(x) with every polynomial of degree k—1 or less, generates all the codeword polynomials of an (1, k) cyclic code. The generator polynomial g(.x) is the smallest degree codeword polynomial of a cyclic code and no other codeword polynomial has degree less than or equal ton — k. Note that the degree of g(x) is equal to the number of parity-check bits of the code. 3.4 Encoding cyclic codes We have seen that the codeword polynomials of a cyclic code have the code’s generator polynomial g(x) as a factor. Hence to encode an information word we must first express the information word as a polynomial and then construct some suitable polynomial that has g(x) asa factor. As with linear codes, there are two ways in which encoding can be achieved, namely nonsystematic and systematic encoding, we consider nonsystematic encoding first.82 | Cyclic codes Nonsystematic encoding is the easiest way of encoding, but not necessarily the preferred method because the resulting codeword polynomials represent non- systematic codewords. We have seen that the product of a generator polynomial g(x) with any polynomial of degree k — I or less produces a codeword polynomial for an (n, k) cyclic code and itis this that forms the basis for nonsystematic encoding. The information word ito be encoded is first expressed as an information polynomial i(x), soit B= (thts th—2y ++ stay tty ig) then ix) = hh" + hat? te $x? + xt iy We then simply take the product of (x) and g(x) to give the codeword polynomial (x) = i(x)g(x). (3.9) Taking the product of g(x) with all the information polynomials i(x) generates the complete set of codewords. Note that there are * polynomials of degree k — 1 or less (ie. the same number as different patterns in a k-bit word). To illustrate why encoding using eqn 3.9 is nonsystematic we reconsider the (7, 4) code. The generator polynomial of the (7,4) code is g(x) = x41 (3.10) asalready seen in Section 3.3 and taking say i= (01 0 1) gives i(x) =x? + 1. Fromeqn 3.9 the corresponding codeword polynomial is e(x) = i(x)g(x) = (7418 +241) Steere txel axe txt] giving the codeword ¢= (01001 1 1), which is not the codeword for (0 1 0 1) but rather for (0 1 0 0) (see Table 1.6). The encoding rule e(x) = i(x)g(x) therefore pro- duces nonsystematic codewords. Example 3.7 Determine nonsystematic codeword polynomials, for the (7,4) code, given i, = (1100) and =(100 1). The information polynomial corresponding to 4 is i(x)=x?+x°, and taking (x)= +x+41 gives e(x) = i(x)a(x) = (8 +2) +241) axtattxe + Sti +27 By ae as the codeword polynomial. Note that the corresponding codeword is e= (11101 00) and encoding is therefore nonsystematic.Encoding cyclic codes | 83 (1001), then i(x) =x? +1 and this gives o(x) =x°+x* +x +1. Again this gives a nonsystematic codeword for iz o Table 3.2 shows the set of codeword polynomials generated by c(x) = i(x)g(x) The table contains the same set of codeword polynomials shown in Table 3.1, except that the order in which the polynomials occur in the tables is different. The encoding procedure for producing systematic codewords for cyclic codes is slightly more complicated than that for nonsystematic codewords. Given an (n, k) cyclic code with generator polynomial g(x), an information polynomial i(x) is encoded into a systematic codeword using the following three steps 1, Multiply (x) by x"~* to give ix)", 2. Divide i(x)x"* by g(x) to give the remainder 1(x) = Rea lilx)x"™*) 3. Add r(x) to i(x)x""* to give the codeword (x) = i(x)x* + r(x). @.11) ‘Asan example, let's again consider the (7, 4) code with i= (0 1 0 1) and information x?+ 1. In Step 1, i(x) is multiplied by x"~* = x" to give IG) = (x7 + x8 = x5 433, In Step 2, x° + x* is divided by g(x) =x? +.x+1 which gives the quotient x? and remainder x*, and so r(x) = Rygle +x)] = Table 3.2 Codeword polynomials generated by ¢(x) = i(x)g(x) for the (7,4) code a ae ed nee aE ig) cx) xex41 ex) Mex ex etx) Hee eet ex) Hehe s(x) eax) cox) eo) enna) cox) cox) x(x) cra) Metre ete tet] e15(%) 44x crx) Bt 4xrt1 en@)84 | Cyclic codes Finally in Step 3, r(x) is added to i(x)x"~* to give the codeword polynomial ox) = +0407 which corresponds to the codeword c= (010 1 1 00) and is the systematic codeword for i=(0101). Example 3.8 ‘Assuming the (7,4) cyclic code determine the systematic codeword polynomials for i) =(1001) and i:=(1110). The information polynomial for i, is i(x) =x? + | and carrying ou! encoding gives : Step 1: Multiplying (x* + 1) by xk gives x8+2°, Step 2: Dividing x°+.° by g(x) =x° +x + | gives the remainder r(x) =x? +x. it systematic Step 3: Adding r(x) to x +x? gives o(x)=x° + PH 4x. Hence the codeword is ¢=(1001110) which is the systematic codeword for (1001). For iy we get (x) =x° +x? +x and x*i(x)=2°+ x +x4, which when divided by g(x) gives r(x)=x. Hence e(x)= x40 4¢xb+27 and c=(1110100) (again encoding is systematic). a Let’s now consider why the three steps given produce systematic codewords. The first step, multiplying i(x) by x*-*, shifts the information bits n ~ k places towards the left-hand side of the word. This leaves the k information bits in the correct position, required for a systematic codeword, and furthermore leaves space for the nk parity bits. In the second and third steps the remainder r(x) of x)” * divided by g(x) is determined and added to i(x)x""*. Using the Euclidean division algorithm, we can write i(x)x* = q(x)ata) +70) where q(x)is the quotient obtained when i(x)x"* is divided by g(x). Subtracting. r(x) from both sides of the above equation, and remembering that polynomial sub- traction is the same as polynomial addition, gives i(x)x"* + r(x) = a(x)a(x) (3.12) Now the term on the right-hand side of eqn 3.12 has g(x) as a factor, and is therefore a codeword polynomial, and so i(x)x" + r(x) will also be a codeword polynomial. Hence Steps I, 2, and 3 give systematic codeword polynomials. Equation 3.12 shows that the codeword polynomial c(x) can be obtained by multiplying the quotient q(x) by g(x) instead of adding the remainder r(x) to i(x)x""*, and so codewords can be expressed as ex) = a(x)a(x) (3.13) for systematic encoding. In Step 3 eqn 3.11 could be replaced by eqn 3.13, however because polynomial addition is easier than multiplication itis normal to use eqn 3.11Decoding cyclic codes | 85 rather than eqn 3.13. Nevertheless it is sometimes useful to think of systematic encoding in terms of eqn 3.13. Comparing eqns 3.9 and 3:13, we see that for an (7, k) cyclic code with generator polynomial g(x), the codeword polynomial e(x) corre- sponding to the information polynomial i(x) is e(x) = f(a)g(x) (3.14) where f(x)=9(x) and f(x)=ix) for systematic and nonsystematic encoding respectively, and where q(x) is the quotient obtained when dividing i(x)x"* by g(x). ‘Example 3.9 : Determine systematic and nonsystematic codewords for #=(0 1 1 1) given the (7,4) code with g(x)=x°+x+1. The information polynomial corresponding to # is i(x)= x2 4x41, and so the nonsystematic codeword polynomial is e(x) = i(x)g(x) = (2 4x+ IP +x+1) axtxtth For the systematic codeword polynomial we get Step 1: (x)x"* =? +x+)) wax txttx Step 2: 1x) = Roser b+ +] =X. Step 3: (x) =i)" 4 Qa txt tet x ‘The corresponding systematic and nonsystematic codewords are therefore (0 11 010) and (0110001) respectively. Note also that in Step 2 the quotient is hx) =x° + x, and replacing Step 3 with (x)= q(xg(x) gives e(x) = ataete) =(P te +x+1) =xtxte ex as given in Step 3 3.5 Decoding cyclic codes We have already seen how with linear codes a syndrome table can be constructed and used for error correction, Here the same approach is adopted, but viewed in terms of polynomials. The implementation of decoding algorithms for cyclic codes can be achieved with linear-feedback shift registers, this is considered in Chapter 4 ‘Whether systematic or nonsystematic encoding is used, a codeword polynomial of acyclic code always has the generator polynomial g(x) as a factor. To test whether some arbitrary polynomial v(x), of degree less than n, is a codeword polynomial of aan (ak) cyclic code the remainder of (x) divided by g(x) is determined. If the remainder is zero then v(x) is a codeword polynomial, otherwise it is not. A code- ‘word polynomial will only give a nonzero remainder if t incurs errors, and as with86 | Cyclic codes linear codes an error syndrome can be defined as that depends solely on the presence of errors. The syndrome polynomial of v(x) is defined as $(x) = Recs) [r(x)] (3.15) recalling that the notation on the right-hand side denotes the remainder obtained when »(x) is divided by g(x). For a codeword polynomial c(x) Rex [e(x)] = 0 (3.16) TT ens: | i because (x) has g(x) as a factor and therefore the syndrome polynomial of a codeword polynomial is s(x) =0. If (x) represents a codeword polynomial o(x) / containing errors then v(x) = e(x) + e(x) \ where the error polynomial e(x)is the polynomial representation of the error pattern. | Using eqn 3.15 the syndrome polynomial is 8(x) = Ry lr()] 3 = Rale(x) + e(x)] = Reyle(x)] + Reisle()] and using eqn 3.16 gives 3(x) = Resle(x)]. (3.17) j Therefore, the syndrome polynomial depends solely on the error polynomial and not on the codeword polynomial incurring the errors. From eqn 3.17 a syndrome table, giving the syndrome polynomials of all the correctable error polynomials, can easily be constructed. As an example, let's construct the syndrome table for the single-error-correcting (7,4) code. We need to determine the syndrome polynomials for the 7 single-error patterns (0000001), (00000 10),..., (1000000). Starting with (0000001) the corresponding error polynomial is e(x)=1 and using eqn 3.17, with g(x) =x" +x + 1, gives the remainder r(x) = Ry .,[]]=1 and therefore the syn- drome polynomial is s(x)=1. The error pattern (0000010) gives e(x) =x and syndrome polynomial s(x)=.x, and continuing through to (1000000) gives e(x) = x° with s(x) =x* + I. Table 3.3 shows the resulting syndrome table. The table isequivalent to the syndrome table previously given for the (7, 4) Hamming code (see Table 1.7), except that here we have a polynomial representation of error patterns and error syndromes. Either table can be converted into the other simply by chan- ging to or from a polynomial representation, as required. It is instructive, however, to see the construction of Table 3.3 from the perspective of cyclic codes and not just ; by a change of notation. Error detection and correction is carried out in a manner similar to that already described for linear codes. Consider a codeword polynomial e(x) incurring an error polynomial e(.c) such that the input to the decoder is (x). The syndrome polynomial s(x) is determined using s(x) = Rec {v(x)] and the error polynomial, denoted by é(.x), corresponding to s(x) is read from the syndrome table. Adding é(1x) to v(x) gives E(x) = v(x) + ex) (3.18)Factors of x"+1 | 87 Table 3.3, Syndrome table for the (7, 4) cyclic code e ex) s(x) aa ap ree a (0000000) 0 (0000001) 1 (0000010) x (0000100) x (0001000) (0010000) V+x (0100000) Sted] (1000000) r+ EEE as the estimated codeword polynomial for c(x). Ifthe number of errors in e(x) is not greater than the error-correction limit of the code then é(x) = e(x), (x) = e(x) and decoding is correct. As already mentioned for decoding linear codes, the use of a syndrome table is not always practical, especially for codes with large blocklengths and information lengths. Furthermore, with cyclic codes this approach does not uilize the cyclic nature of the codes. In Chapter 4 we consider the implementation of encoding and decoding, using linear-feedback shift registers, and we will see how the cyclic property of the codes is utilized Example 3.10 Consider decoding when the codeword c= (1010011). belonging to the (7,4) code, incurs the error e=(1000000). The codeword (1010011) gives e(x)=x°+.4 44-41 and e=(1000000) gives ¢(x) =x°. Hence the word to be decoded is RAL sO v(x) = e(x) + e(x) = a4 $041. The generator polynomial for the (7, 4) code isg(x) =x" ++ Land the syndrome polynomial is 50) = Repeilyt txt I =e 41 Referring to Table 3.3, we see that (x) = x? + 1 corresponds to the error polynomial ¢(x) = x°. Therefore the estimated codeword polynomial is (x) = v(x) + 6) = (x4 4x41) 4x6 =tattet] which gives ¢=(1010011). The decoder therefore correctly concludes that » was the codeword (1010011). a 3.6 Factors of x”+1 We now ask whether any polynomial can be used to generate a cyclic code, and if not, then what characteristics must a polynomial have such that it can generate a88 | Cyclic codes cyclic code. The answer to this question lies in the factorization of the polynomial p(x) =x" 41. (3.19) A polynomial g(x) with degree r generates an (n, k) cyclic code, where k=n—r, if g(x) divides x" + 1. Note that by ‘divides’ itis implied that the remainder is zero and so g(x) has to bea factor of x" + 1 if itis to generate a cyclic code. Consider the (7, 4) code with g(x) =x? +x + 1. In Section 3.1 it was claimed that the (7, 4) code is cyclic and examples of cyclic shifts were given. This though does not prove that the code is cyclic but only illustrates the cyclic relationship between some of its codewords. To show that g(x) generates a cyclic code we need to divide x’ + 1 by g(x) and check that the remainder is zero. Dividing x’ +1 by g(x) gives +etxtl x +x41)x7 41 xi hot Sapa Sep? DUES S eT a DS FxtT xe+x4l 0 and so the remainder is zero. Hence, the polynomial g(x) = x° +x + I divides x” +1 and therefore generates a (7, 4) cyclic code. Note that the degree of g(x) is r= 3 and so the information length of the code is =4, Furthermore the quotient obtained is x4+.x7 +x + 1,and if we let A(x)=x4 +27 +x+1 then * g(h(x) = x7 $1. (3.20) From eqn 3.20 we see that h(x) also divides x” + 1 and therefore h(x) =x‘ +x? + x+ | likewise generates a cyclic code of blocklength 7 but with information length 3 (because the degree of h(x) is 4). Hence the polynomial x* +27 +x +1 generates a (7,3) cyclic code (note that h(x) is referred to as the parity-check polynomial of the (7,4) code, this is considered further in Section 3.7). We can go astep further in factorizing x’ + 1 because x= | isa root of A(x) (letting x= 1 gives A(1)=1+1+1+1=0) and so (x+ 1) is a factor of h(x). Dividing h(x) by (x+1) gives the quotient x°+x7+1 and a zero remainder. Therefore h(x)=x'+x°+x4+1=(x+1) (x° +x? +1) and substituting this into eqn 3.20, along with g(x) =x? + x+1, gives (e+ IP 4274+ NiO Hx$ ID Hx Le (3.21) There are no other factors of x’ + 1 as neither x°+ x7 +1 or x* + x+1 can be fac- torized. Any of the 3 factors of x” +1 or products of the factors will generate a cyclic code with blocklength 7. Equation 3.21 therefore shows that there are 2 polynomials that generate (7,4) codes, the polynomial x°+x+1 that we have already considered and x? + x? 1 (the codes are however equivalent). Taking theFactors of x"+1 | 89 Table 3.4 Cyclic codes constructed from x” +1 Factors ax) (nk) code fi) xt] (7,8) fla) eel (7,4) Sx) e+x+] (7,4) AOA) +H FH41 (7,3) A fl) A+ +x41 (7,3) PPX) Petxteeer tat 1 71) Note: 37 +1 = file fal) Ale) product of the factors (x + 1) and (x* +x +1) gives (x4 D(P4xt Hat ¢e tert] which generates a (7, 3) cyclic code and is equivalent to the (7, 3) code generated by x4 4x2 + x41. The product of (x? +x +1) and (x? +27 + 1) gives (P4x4 (+24 las teeter ttre This has degree r=6 and so the cyclic code constructed has k= (recall that k=n-—r) and is therefore the (7, 1) repetition code, The code is clearly cyclic, as a cyclic shift on either of its 2 codewords, (0000000) or (1111111), gives the same codeword. The factor (x +1) taken on its own generates a code with k=6 and therefore gives the (7, 6) single-parity-check code. Again this is clearly a cyclic code because a codeword that is subjected to a cyclic shift preserves its parity and is therefore still a codeword. Note that 3 factors give 8 different combinations, of which we have seen 6 (giving the two (7, 4) codes, the two (7, 3) codes, the (7, 1) code and the (7, 6) code). The remaining 2 combinations give 2 trivial codes with g(x) =1 (and n=k=7) and g(x) =x’ +1 (with n=7 and k=0). Table 3.4 shows the 6 nontrivial cyclic codes that can be obtained from x” +1. Example 3.11 Given that x°+1=(x+1) (2 +x+1) (+2? +1) determine the cyclic codes with blocklength 9. Let the individual factors be denoted by Ale)=x+1 fla) =e? tx+l fix) =x $x$. Here f(x) =x-+1 has degree | and therefore generates a (9, 8) single-parity-check code, while f(x) and f(x) generate (9, 7) and (9, 3) cyclic codes respectively. Taking the product of f(x) with f3(x) and then with f(x) gives AG) A(x) = +1 A) Alx) =x +x8tx8 +4 xt] which give (9, 6) and (9,2) cyclic codes respectively.90 | Cyclic codes The product of f(x) and fa(x) gives AMA =P 4x7 484 S444 8424x451 which has degree 8 and therefore gives the (9, 1) repetition code. This accounts for 6 codes, the remaining 2 codes are trivial codes with g(x) =1 (n=k=9) and g(x) =x° +1 (1 =9, k =0), a 3.7 Parity-check polynomials {f(s is the generator polynomial of an (n,k) cyclic code, then the polynomial (x) that satisfies g(x)A(x) =x" $1 (3.22) is known as the parity-check polynomial of the code, and rearranging this gives +1 iO) ae (3.23) The degree of h(x) is n minus the degree of g(x), and as g(x) has degree n —k the Parity-check polynomial A(x) therefore has degree n — (n — k) =k. The parity-check Polynomial can be written as W(x) = hex + nat" +--+ hax? + fix + hg (3.24) where the coefficients y= /y = and the remaining coefficients hy, hy, ... haa ‘y—1 are 0 or 1. The (7,4) code with g(x) =x?+x-+1 has the parity-check poly- nomial h(x) = (x7 + 1)/( + x +1) which gives Ax) = x8 tex $ (3.25) The parity-check polynomial is analogous to the parity-check matrix H used in linear codes, just as the generator polynot is analogous to the generator matrix G. Note however that we have already cor red the decoding of cyclic codes, and as we saw this can be achieved using the generator polynomial (the parity-check polynomial was not required for decoding the (7,4) code). The relevance of the Parity-check polynomial to decoding is considered later. In Section 3.9 we consider how the generator and parity-check matrices can be obtained directly from the generator and parity-check polynomials respectively. Its interesting to compare the relationships between codeword, generator, and Parity-check polynomials with that of codewords, generator, and parity-check matrices (used in cyclic codes and linear codes respectively). First consider the construction of codeword polynomials. We have seen that the codeword polynomial ¢(x) for an information polynomial i(x) is given by (x) = i(x)g(x)