reed_solomon.ps

rs encoder in matlab 7,3

y Fp(k)q Fo(\000)p Fq(1)1044 795 y Fs(\))15 b(with)g(all)i(the)e
Fr(x)1348 802 y Fp(i)1377 795 y Fs(distinct)i(and)e(non-)224
851 y(zero.)34 b(If)20 b(w)o(e)g(w)o(eren't)f(w)o(orried)h(ab)q(out)g
(errors,)g(one)g(alternativ)o(e)g(to)g(transmitting)224
907 y(the)15 b(co)q(e\016cien)o(ts)h(of)e Fr(m)p Fs(\()p
Fr(x)p Fs(\))g(w)o(ould)i(b)q(e)f(to)f(ev)m(aluate)i
Fr(m)p Fs(\()p Fr(x)p Fs(\))e(at)g Fr(k)i Fs(kno)o(wn)f(p)q(oin)o(ts,)g
(send)224 964 y(the)h Fr(k)h Fs(ev)m(aluations)g(of)f
Fr(m)p Fs(\()p Fr(x)p Fs(\))f(as)g(our)h(message,)f(and)h(then)h
(reconstruct)e Fr(m)p Fs(\()p Fr(x)p Fs(\))g(from)224
1020 y(those)c(ev)m(aluations.)20 b(This)12 b(approac)o(h)f(do)q(esn't)
h(pro)o(vide)f(an)o(y)h(adv)m(an)o(tages)e(if)i(there)g(are)224
1077 y(guaran)o(teed)f(to)f(b)q(e)h(no)g(errors,)g(but)f(it)i(can)f(b)q
(e)g(extended)h(to)e(pro)o(vide)h(the)g(redundancy)224
1133 y(necessary)23 b(to)f(correct)g(errors.)41 b(The)23
b(w)o(a)o(y)f(w)o(e)g(will)i(get)e(our)h(redundancy)g(is)h(b)o(y)224
1190 y(ev)m(aluating)18 b Fr(m)p Fs(\()p Fr(x)p Fs(\))d(at)h(2)p
Fr(s)g Fs(additional)i(distinct)f(non-zero)g(p)q(oin)o(ts;)g(so)f(that)
f(what)h(w)o(e)224 1246 y(send)j(is)f Fr(n)f Fs(=)g Fr(k)c
Fs(+)f(2)p Fr(s)18 b Fs(ev)m(aluations)h Fn(f)p Fr(m)p
Fs(\()p Fr(x)967 1253 y Fq(0)986 1246 y Fs(\))p Fr(;)8
b(:)g(:)g(:)k(;)c(m)p Fs(\()p Fr(x)1197 1253 y Fp(n)p
Fo(\000)p Fq(1)1264 1246 y Fs(\))p Fn(g)p Fs(,)18 b(where)g
Fr(x)1496 1253 y Fq(0)1515 1246 y Fr(;)8 b(:)g(:)g(:)13
b(;)8 b(x)1651 1253 y Fp(n)p Fo(\000)p Fq(1)224 1303
y Fs(are)15 b(distinct)h Fr(x)p Fs(-v)m(alues)h(agreed)e(up)q(on)h(b)q
(efore)f(sending)i(the)e(message.)295 1359 y(W)l(e)f(will)i
(reconstruct)e Fr(m)p Fs(\()p Fr(x)p Fs(\))f(in)i(the)g(follo)o(wing)g
(w)o(a)o(y:)j(let)d(\()p Fr(y)1344 1366 y Fq(0)1363 1359
y Fr(;)8 b(:)g(:)g(:)13 b(;)8 b(y)1495 1366 y Fp(n)p
Fo(\000)p Fq(1)1563 1359 y Fs(\))14 b(b)q(e)g(the)224
1416 y(ev)m(aluations)20 b(receiv)o(ed,)h(with)f(at)e(most)g(most)h
Fr(s)g Fs(errors.)31 b(T)l(ry)19 b(to)f(\014nd)i(a)f(subset)g(of)224
1472 y Fr(k)11 b Fs(+)e Fr(s)15 b Fs(\(or)f(more\))g(p)q(oin)o(ts)h
(from)f Fn(f)p Fs(\()p Fr(x)853 1479 y Fq(0)872 1472
y Fr(;)8 b(y)915 1479 y Fq(0)935 1472 y Fs(\))p Fr(;)g(:)g(:)g(:)k(;)c
Fs(\()p Fr(x)1106 1479 y Fp(n)p Fo(\000)p Fq(1)1173 1472
y Fr(;)g(y)1216 1479 y Fp(n)p Fo(\000)p Fq(1)1284 1472
y Fs(\))p Fn(g)14 b Fs(suc)o(h)h(that)g(a)f(degree-)224
1528 y(\()p Fr(k)q Fs(-1\))f(p)q(olynomial)j(passes)e(through)g(the)g
(p)q(oin)o(ts.)20 b(Suc)o(h)15 b(a)e(subset)i(m)o(ust)e(exist,)h(since)
224 1585 y(w)o(e)20 b(start)f(with)h Fr(k)15 b Fs(+)e(2)p
Fr(s)20 b Fs(p)q(oin)o(ts)h(and)f(at)f(most)h Fr(s)g
Fs(p)q(oin)o(ts)g(are)g(in)h(error.)34 b(Once)21 b(w)o(e)224
1641 y(ha)o(v)o(e)g(suc)o(h)g(a)g(subset,)h(w)o(e)f(kno)o(w)f(that)h
(it)g(matc)o(hes)g(ev)m(aluations)h(of)f Fr(m)p Fs(\()p
Fr(x)p Fs(\))f(for)g(at)224 1698 y(least)c Fr(k)g Fs(distinct)g
Fr(x)p Fs(-v)m(alues,)h(b)q(ecause)f(at)e(most)h Fr(s)g
Fs(of)g(the)h Fr(k)11 b Fs(+)f Fr(s)16 b Fs(p)q(oin)o(ts)g(are)e(in)j
(error.)224 1754 y(Since)f Fr(k)f Fs(ev)m(aluations)g(uniquely)i
(determine)e(a)f(degree-\()p Fr(k)9 b Fn(\000)f Fs(1\))14
b(p)q(olynomial,)h(w)o(e)f(can)224 1811 y(reconstruct)h(the)g(correct)g
Fr(m)p Fs(\()p Fr(x)p Fs(\).)295 1867 y(The)e(algorithm)h(just)f
(describ)q(ed)i(has)f(the)f(righ)o(t)g(\015a)o(v)o(or,)g(but)g(the)h
(step)f(of)g(\014nding)224 1924 y(a)21 b(subset)h(of)f(consisten)o(t)h
(p)q(oin)o(ts)g(is)g(computationally)g(di\016cult.)40
b(Later)21 b(on)h(w)o(e'll)224 1980 y(impro)o(v)o(e)14
b(this)h(algorithm)f(and)g(talk)g(ab)q(out)g(mo)q(dern)h(RS)g(co)q
(ding)g(implemen)o(tations;)224 2037 y(but)h(\014rst)g(let's)g(\015esh)
g(out)g(the)g(construction)g(of)g(the)g(\014eld)h(o)o(v)o(er)e(whic)o
(h)i(w)o(e)f(tak)o(e)f(our)224 2093 y(p)q(olynomial)i
Fr(m)p Fs(\()p Fr(x)p Fs(\).)224 2236 y Ft(3)67 b(Constructing)23
b(the)g(\014eld)g Fm(F)224 2339 y Fl(3.1)56 b(Refresher)17
b(on)i(\014elds)224 2425 y Fs(W)l(e)d(in)o(tro)q(duce)g(here)g(the)g
(basic)g(algebraic)g(de\014nitions)h(whic)o(h)f(will)i(b)q(e)e(used)g
(in)g(this)224 2482 y(section.)960 2613 y(2)p eop
%%Page: 3 3
3 2 bop 224 286 a Fk(Groups.)45 b Fs(A)14 b(group)g(is)h(a)f(tuple)h
(\()p Fr(G;)8 b Fn(\002)p Fr(;)g(e)p Fs(\),)k(where)j
Fr(G)f Fs(is)h(a)f(set)g(of)g(elemen)o(ts,)g Fn(\002)h
Fs(is)g(a)224 343 y(binary)i(op)q(erator)e(on)h Fr(G)p
Fs(,)g(and)g Fr(e)e Fn(2)g Fr(G)i Fs(is)h(a)e(designated)i(iden)o(tit)o
(y)g(elemen)o(t.)23 b Fr(G)16 b Fs(m)o(ust)224 399 y(ha)o(v)o(e)f(the)g
(follo)o(wing)h(prop)q(erties:)280 486 y(1.)22 b Fn(\002)15
b Fs(is)h(closed.)21 b(F)l(or)14 b(all)i Fr(a;)8 b(b)k
Fn(2)h Fr(G)p Fs(,)h Fr(a)c Fn(\002)h Fr(b)h Fn(2)h Fr(G)p
Fs(.)280 578 y(2.)22 b Fn(\002)15 b Fs(is)h(asso)q(ciativ)o(e.)k(F)l
(or)15 b(all)h Fr(a;)8 b(b;)g(c)i Fn(2)j Fr(G)p Fs(,)i(\()p
Fr(a)9 b Fn(\002)i Fr(b)p Fs(\))e Fn(\002)i Fr(c)h Fs(=)h
Fr(a)d Fn(\002)g Fs(\()p Fr(b)g Fn(\002)g Fr(c)p Fs(\).)280
669 y(3.)22 b(F)l(or)14 b(all)i Fr(a)d Fn(2)g Fr(G)p
Fs(,)i Fr(a)10 b Fn(\002)g Fr(e)j Fs(=)g Fr(e)d Fn(\002)h
Fr(a)h Fs(=)h Fr(a)p Fs(.)280 760 y(4.)22 b(F)l(or)d(eac)o(h)h
Fr(a)h Fn(2)g Fr(G)f Fs(there)g(is)h(an)f(elemen)o(t)h
Fr(a)1120 743 y Fo(\000)p Fq(1)1188 760 y Fn(2)g Fr(G)e
Fs(suc)o(h)i(that)e Fr(a)14 b Fn(\002)f Fr(a)1615 743
y Fo(\000)p Fq(1)1683 760 y Fs(=)338 816 y Fr(a)362 800
y Fo(\000)p Fq(1)419 816 y Fn(\002)e Fr(a)h Fs(=)h Fr(e)i
Fs(\()p Fr(a)627 800 y Fo(\000)p Fq(1)690 816 y Fs(is)g(called)i(an)e
(in)o(v)o(erse)h(of)f Fr(a)p Fs(\).)224 903 y(W)l(e)g(will)h(often)e
(abbreviate)g Fr(a)9 b Fn(\002)g Fr(b)k Fs(as)h Fr(ab)g
Fs(when)h(it's)f(ob)o(vious)h(what)e(the)i(op)q(erator)e(is.)224
1022 y Fk(Fields.)46 b Fs(A)19 b(\014eld)h(is)g(a)f(tuple)h(\()p
Fr(F)q(;)8 b Fs(+)p Fr(;)g Fn(\002)p Fr(;)g Fs(0)p Fr(;)g
Fs(1\),)17 b(where)i Fr(F)26 b Fs(is)19 b(the)h(set)e(of)h(elemen)o
(ts,)224 1079 y(+)f(is)h(the)f(addition)h(op)q(erator,)f
Fn(\002)g Fs(is)h(the)f(m)o(ultiplication)i(op)q(erator,)e(0)f
Fn(2)g Fr(F)25 b Fs(is)18 b(the)224 1135 y(additiv)o(e)f(iden)o(tit)o
(y)l(,)e(and)h(1)d Fn(2)g Fr(F)22 b Fs(is)15 b(the)h(m)o(ultiplicativ)o
(e)i(iden)o(tit)o(y)l(.)j Fr(F)h Fs(m)o(ust)14 b(ha)o(v)o(e)h(the)224
1192 y(follo)o(wing)h(prop)q(erties:)280 1279 y(1.)22
b(\()p Fr(F)q(;)8 b Fs(+)p Fr(;)g Fs(0\))13 b(forms)i(a)g(group.)280
1370 y(2.)22 b Fn(\002)15 b Fs(is)h(asso)q(ciativ)o(e)g(and)f
(distributes)h(o)o(v)o(er)f(+.)280 1461 y(3.)22 b(\()p
Fr(F)16 b Fn(n)10 b(f)p Fs(0)p Fn(g)p Fr(;)e Fn(\002)p
Fr(;)g Fs(1\))k(forms)j(a)g(group.)224 1548 y(Note)i(w)o(e)f(will)i
(often)f(sa)o(y)f(\\the)h(\014eld)h Fr(F)6 b Fs(")17
b(when)g(w)o(e)f(mean)h(\\the)g(\014eld)h(whose)e(set)h(is)224
1604 y Fr(F)6 b Fs(,)15 b(with)h(the)f(standard)g(op)q(erators)f(for)h
(that)f(set".)295 1661 y(Fields)k(that)e(w)o(e)h(commonly)g(w)o(ork)f
(with)i(include)h(the)e(real,)h(complex,)g(and)f(ra-)224
1717 y(tional)h(n)o(um)o(b)q(ers.)27 b(The)18 b(set)f(of)g(in)o(tegers)
g(is)h(not)f(a)g(\014eld.)28 b(It)18 b(satis\014es)f(the)h(\014rst)f(t)
o(w)o(o)224 1774 y(prop)q(erties,)f(but)g(fails)h(the)f(third)g(prop)q
(ert)o(y)f(b)q(ecause)i(not)f(all)g(in)o(tegers)g(ha)o(v)o(e)g(m)o
(ulti-)224 1830 y(plicativ)o(e)k(in)o(v)o(erses.)28 b(A)18
b(set)f(lik)o(e)i(the)f(in)o(tegers)g(whic)o(h)h(satis\014es)f(the)g
(\014rst)g(t)o(w)o(o)e(\014eld)224 1887 y(prop)q(erties)g(is)g(called)h
(a)d(\\ring".)224 2007 y Fl(3.2)56 b(Galois)18 b(\014elds)224
2093 y Fs(W)l(e)i(no)o(w)g(turn)g(to)g(the)g(question)h(of)f
(constructing)g(the)h(\014eld)g Fr(F)27 b Fs(from)19
b(whic)o(h)i(the)224 2149 y(co)q(e\016cien)o(ts)d(of)f
Fr(m)p Fs(\()p Fr(x)p Fs(\))g(are)g(dra)o(wn.)26 b(A)17
b(basic)h(result)g(from)f(n)o(um)o(b)q(er)g(theory)g(is)h(that)224
2206 y(if)g Fr(p)f Fs(is)h(prime,)g(then)f(the)g(set)g(of)g(in)o
(tegers)g(mo)q(dulo)h Fr(p)f Fs(\(denoted)h Fj(Z)1409
2213 y Fp(p)1426 2206 y Fs(\))f(is)h(a)e(\014eld.)28
b(So)224 2262 y(if)16 b(there)g(are)f(a)h(prime)g(n)o(um)o(b)q(er)g
Fr(p)f Fs(of)g(p)q(ossible)j(digits,)e(w)o(e)f(can)h(use)g
Fj(Z)1453 2269 y Fp(p)1485 2262 y Fs(as)f(our)h(\014eld.)224
2319 y(Ho)o(w)o(ev)o(er,)f(that)g(is)i(true)f(if)g(and)h(only)f(if)h
Fr(p)f Fs(is)g(prime.)23 b(Unfortunately)l(,)17 b(in)g(computer)224
2375 y(applications)e(w)o(e)f(are)f(lik)o(ely)i(to)e(w)o(an)o(t)g
(digits)h(that)f(w)o(e)g(can)h(enco)q(de)h(with)f Fr(r)f(>)g
Fs(1)g(bits;)224 2432 y(for)j(instance,)h(8-bit)g(c)o(haracters.)22
b(This)17 b(means)g(w)o(e)f(ha)o(v)o(e)g(a)g(non-prime)h(n)o(um)o(b)q
(er)g(2)1700 2415 y Fp(r)224 2488 y Fs(of)e(p)q(ossible)i(digits.)960
2613 y(3)p eop
%%Page: 4 4
4 3 bop 295 286 a Fs(F)l(ortunately)l(,)24 b(it)f(can)f(b)q(e)i(pro)o
(v)o(en)e(that)g(for)g(an)o(y)g(prime)h Fr(p)f Fs(and)h(an)o(y)f
(natural)224 343 y(n)o(um)o(b)q(er)16 b Fr(r)h Fs(there)f(exists)g(a)g
(\014nite)h(\014eld)g(with)f Fr(p)1053 326 y Fp(r)1088
343 y Fs(n)o(um)o(b)q(ers.)22 b(\(In)16 b(fact)f(the)h(rev)o(erse)g(is)
224 399 y(also)h(true|ev)o(ery)h(\014nite)g(\014eld)g(has)f
Fr(p)890 383 y Fp(r)926 399 y Fs(n)o(um)o(b)q(ers,)g(where)h
Fr(p)e Fs(is)i(prime\).)26 b(There)17 b(is)h(a)224 456
y(w)o(a)o(y)c(to)g(generate)h(suc)o(h)g(a)f(\014eld.)21
b(It)15 b(is)h(called)g(a)e(Galois)i(\014eld,)f(and)g(it)g(can)g(b)q(e)
h(sho)o(wn)224 512 y(that)f(an)o(y)g(\014nite)h(\014eld)g(of)f(size)h
Fr(p)784 496 y Fp(r)818 512 y Fs(is)g(isomorphic)g(to)e(a)h(Galois)h
(\014eld.)295 569 y(Galois)11 b(\014elds)h(are)f(constructed)g(with)g
(the)g(help)h(of)f Fj(Z)1200 576 y Fp(p)1217 569 y Fs([)p
Fr(x)p Fs(],)g(the)g(set)f(of)h(p)q(olynomials)224 625
y(with)16 b(co)q(e\016cien)o(ts)g(in)g Fj(Z)641 632 y
Fp(p)658 625 y Fs(.)295 682 y(W)l(e're)i(used)i(to)e(dealing)j(with)e
(p)q(olynomials)h(with)g(real)f(co)q(e\016cien)o(ts)h(\(p)q(olyno-)224
738 y(mials)c(in)g Fj(R)m Fs([)o Fr(x)p Fs(]\),)11 b(so)k(the)g
(arithmetic)g(of)g(p)q(olynomials)i(in)e Fj(Z)1263 745
y Fp(p)1280 738 y Fs([)p Fr(x)p Fs(])f(ma)o(y)g(seem)i(coun)o(ter-)224
795 y(in)o(tuitiv)o(e.)21 b(T)l(ak)o(e)15 b Fr(F)k Fs(=)13
b Fj(Z)659 802 y Fq(2)676 795 y Fs(,)i(for)f(instance.)295
851 y(A)h(refresher)g(on)g(ho)o(w)g(arithmetic)h(mo)q(dulo)g(2)f(w)o
(orks:)850 953 y(0)10 b(+)h(0)41 b(=)h(0)850 1022 y(0)10
b(+)h(1)41 b(=)h(1)850 1091 y(1)10 b(+)h(0)41 b(=)h(1)850
1160 y(1)10 b(+)h(1)41 b(=)h(0)224 1262 y(No)o(w)15 b(for)f(example,)i
(let)g Fr(a;)8 b(b)j Fn(2)i Fj(Z)804 1269 y Fq(2)821
1262 y Fs([)p Fr(x)p Fs(],)h Fr(a)p Fs(\()p Fr(x)p Fs(\))e(=)h
Fr(x)1072 1245 y Fq(2)1102 1262 y Fs(+)d Fr(x)p Fs(,)15
b Fr(b)p Fs(\()p Fr(x)p Fs(\))c(=)j Fr(x)p Fs(.)19 b(Then)d(w)o(e)f
(can)h(do)224 1318 y(the)f(addition)742 1408 y Fr(a)p
Fs(\()p Fr(x)p Fs(\))41 b(=)h(1)p Fr(x)995 1391 y Fq(2)1024
1408 y Fs(+)11 b(1)p Fr(x)747 1464 y(b)p Fs(\()p Fr(x)p
Fs(\))40 b(=)i(0)p Fr(x)995 1448 y Fq(2)1024 1464 y Fs(+)11
b(1)p Fr(x)606 1521 y(a)p Fs(\()p Fr(x)p Fs(\))e(+)i
Fr(b)p Fs(\()p Fr(x)p Fs(\))40 b(=)i(1)p Fr(x)995 1504
y Fq(2)1024 1521 y Fs(+)11 b(0)p Fr(x)41 b Fs(=)13 b
Fr(x)1234 1504 y Fq(2)224 1621 y Fs(whic)o(h)g(is)g(of)f(course)g(a)g
(di\013eren)o(t)g(result)h(than)f(w)o(e)g(w)o(ould)g(ha)o(v)o(e)g
(gotten)g(if)g Fr(a)p Fs(\()p Fr(x)p Fs(\))p Fr(;)c(b)p
Fs(\()p Fr(x)p Fs(\))i Fn(2)224 1678 y Fj(R)m Fs([)p
Fr(x)p Fs(])o(;)i(in)k(that)f(case)g(w)o(e)g(w)o(ould)g(ha)o(v)o(e)g
(had)h(\()p Fr(x)1018 1661 y Fq(2)1047 1678 y Fs(+)10
b Fr(x)p Fs(\))g(+)h(\()p Fr(x)p Fs(\))h(=)h Fr(x)1340
1661 y Fq(2)1369 1678 y Fs(+)e(2)p Fr(x)p Fs(.)295 1734
y(No)o(w)16 b(to)g(de\014ne)i(mo)q(dulo)f(arithmetic)h(for)e(p)q
(olynomials:)24 b Fr(a)p Fs(\()p Fr(x)p Fs(\))16 b(mo)q(dulo)i
Fr(g)r Fs(\()p Fr(x)p Fs(\))d(is)224 1791 y(another)h(p)q(olynomial)j
Fr(r)q Fs(\()p Fr(x)p Fs(\))d(with)h(degree)g(strictly)g(less)g(than)g
Fr(g)r Fs(\()p Fr(x)p Fs(\),)e(and)i(satisfying)224 1847
y Fr(a)p Fs(\()p Fr(x)p Fs(\))12 b(=)h Fr(g)r Fs(\()p
Fr(x)p Fs(\))p Fr(q)r Fs(\()p Fr(x)p Fs(\))6 b(+)g Fr(r)q
Fs(\()p Fr(x)p Fs(\))11 b(for)h(some)h(p)q(olynomial)i
Fr(q)r Fs(\()p Fr(x)p Fs(\).)j Fk(Exercise:)