{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Headi ng 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Ti mes" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 0 1 } {PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 33 "Reed Solomon codes as eva luations" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 12 "Introduction" }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 789 "This example follows the presenta tion of Reed-Solomon codes in Chapter 5 of J\370rn Justesen and Tom H \370holdt: A Course in Error-Correcting Codes. The k information symbo ls from the field F(q) are interpreted as coefficients of a polynomial f(x) of degree less than k, and the codeword is the value of the pol ynomial for the q-1 nonzero values of x (or all q values if we include x=0). Since the polynomial can have at most k-1 zeros, it follows tha t the minimum weight is d=n-k+1. This was the original approach to RS \+ codes. The evaluation of the information polynomial may be described a s a finite field version of the Fourier Transform. This leads to encod ing methods related to the FFT of signal processing. The decoding in t his example uses the interpolation algorithm in Section 5.2. " }}}} {SECT 0 {PARA 3 "" 0 "" {TEXT -1 22 "Linear algebra package" }}{PARA 0 "" 0 "" {TEXT -1 45 "For simplicity we include the entire package." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{MPLTEXT 1 0 13 "with(linalg): " }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 13 "Finite fields" }}{PARA 0 " " 0 "" {TEXT -1 325 "If F(p) is a field with p elements, we can extend it to q=p^m symbols by adding a root of a polynomial of degree m.In t his version of the example we shall do the computations in a prime fie ld, q=p ( a prime). Some of the notation is prepared for a version in an extension field. A primitive element, alpha, must be supplied." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "p:=17;" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 5 "m:=1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "q:=p^m;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "powers:=vec tor(q-1); " }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "alpha:=3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "for i to q-1 \+ do powers[i]:=evala(alpha^(i-1)) mod p od:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 14 "print(powers);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "inverse:=vector(q-1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "for i to q-1 do inverse[i]:=evala(1/powers[i])mod p o d:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "print(inverse);" }}}{PARA 12 "" 1 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 8 "Encoding " }}{PARA 0 "" 0 "" {TEXT -1 364 "In this example we encode a Reed-Sol omon code by evaluating the information symbols as coefficients of a p olynomial of degree < k. Another interpretation is to extend the input vector to length n by adding n-k zeros and multiplying it by a matrix with elements alpha^rs, 0<= r,s " 0 "" {MPLTEXT 1 0 5 "k:=8;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 83 "fin:=vector(q-1,[1, 1, 1, al pha, 1+alpha, 1, alpha^2, 0, 0, 0, 0 , 0, 0, 0, 0, 0]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "fx:= x-> simplify(add(fin[i]*x^(i-1 ), i=1..k)) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "w:=ma p(fx, powers);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "FT:=matri x(q-1,q-1,[]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 107 "for r to q-1 do\n for s to q-1 do\n FT[r,s]:=simplify(alpha^((r-1)*(s- 1))) mod p\n od:od: print(FT);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "w:=evalm(FT&*fin);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "w:=map(`mod`,w,p);" }}}}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 12 "Transmission" }}}{PARA 0 "" 0 "" {TEXT -1 53 " We may add erro rs by specifying an error vector." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "ee:=vector(q-1,[0, 1, 0, 1+a lpha, 0, 0, 0, 0, 1, 0, 0, 0, 0, alpha,0,0]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "rr:=evalm(ee+w):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "rr:=map(`mod`,rr,p);" }}}{PARA 11 "" 1 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 13 "Interpolation" }}{PARA 0 "" 0 "" {TEXT -1 121 "The idea in this decoding method is to find a polyn omial Q(x,y) such that for any location, x, and any y=rr(x), Q(x,y)=0. " }}}{PARA 0 "" 0 "" {TEXT -1 129 "Such a polynomial exists if we allo w q coefficients, and we may find the coefficients by solving a system of linear equations. " }}{PARA 0 "" 0 "" {TEXT -1 307 "We are looki ng for a Q that can be factored as (y+f(x))e(x), where f(x) is the inf ormation polynomial and e(x) has zeros in the error positions. Thus wi th t errors, we allow terms up to y*x^t and x^(k+t-1), and the number \+ of such terms is k+2t+1. In this way we can correct up to (q-k-1)/2 = \+ (d-1)/2 errors." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 20 "t:=trunc((q-k-1)/2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "l0:=q-2-t;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "l1:=q-2-t-(k-1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "A:=matrix(q-1,l0+l1+2,[]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 187 "for i to q-1 do\n for j to l0+1 do\n A[ i,j]:=simplify(powers[i]^(j-1)) mod p\n od;\n for j to l1+1 do\n A[i,j+l0+1]:=simplify(powers[i]^(j-1)*rr[i]) mod p;\n od;\n od;" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "prin t(A);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "Pc:=Nullspace(A) m od p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "Qv:=Pc[1];" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 75 "V:=[1,x,x^2,x^3,x^4,x^5,x^6, x^7,x^8,x^9,x^10,x^11,y,y*x,y*x^2,y*x^3,y*x^4];" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 31 "QQ:=dotprod(Qv,V,'orthogonal');" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Q1:=coeff(QQ,y);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "Q0:=coeff(QQ,y,0);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 184 "If the polynomial can be factored, we get Q(x,y) = e(x)(y-f(x)) = y e(x) + e(x)f(x). Thus we can find the error location s by finding the roots of e(x), and we may then recover f(x). " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Divide(Q0,Q1,'Fr') mod p;" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "-Fr mod p;" }}}{PARA 12 " " 1 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Facto r(Q1) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Factor(QQ) \+ mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 139 "The factorization give s us the location values of the errors, and by dividing the two polyno mials we have recovered the information vector." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 8 "Problems" }}{PARA 0 "" 0 "" {TEXT -1 43 "1. Modify the program to do Example 5.2.1" }} {PARA 0 "" 0 "" {TEXT -1 54 "2. Give a generator matrix as part of t he matrix FT." }}{PARA 0 "" 0 "" {TEXT -1 57 "3. Give a parity check matrix as part of the matrix FT." }}{PARA 0 "" 0 "" {TEXT -1 71 "4. \+ Find the error locator polynomial Q1 by the method in Section 5.4." } }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{MARK "38 4 0" 71 }{VIEWOPTS 0 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }