reed_solomon.ps

rs encoder in matlab 7,3

13F0A6007013E0A2383801C0A2381C038038070E00EA01F814147F9317>I<EA1C7CEAFD
87381E018014C0381C00E014F014701478A6147014F014E0381E01C0EB0380381D8700EA
1C7C90C7FCA8B47E151D7E9319>I<3801F04038070CC0EA0E02EA1C03EA380112781270
12F0A6127012781238EA1C03EA0C05EA0709EA01F1EA0001A8EB0FF8151D7F9318>I<EA
1CF0EAFD18EA1E3CA21318EA1C00AEEAFFC00E147E9312>I<EA0FC8EA3038EA6018EAC0
08A3EAE000127CEA3FE0EA1FF0EA07F8EA003CEA800E130612C0A21304EAE00CEAD818EA
87E00F147F9312>I<1202A31206A2120EA2123EEAFFF8EA0E00AB1304A5EA07081203EA
01F00E1C7F9B12>I<381C0380EAFC1FEA1C03AE1307120CEA061B3803E3F014147E9319>
I<38FF83F8383E00E0001C13C06C1380A338070100A21383EA0382A2EA01C4A213E4EA00
E8A21370A3132015147F9318>I<39FF9FE1FC393C078070391C030060EC8020000E1440
A214C0D80704138014E0A239038861001471A23801D032143A143E3800E01CA2EB6018EB
40081E147F9321>I<38FF87F8381E03C0380E0180EB0300EA0702EA0384EA01C813D8EA
00F01370137813F8139CEA010E1202EA060738040380000C13C0003C13E038FE07FC1614
7F9318>I<38FF83F8383E00E0001C13C06C1380A338070100A21383EA0382A2EA01C4A2
13E4EA00E8A21370A31320A25BA3EAF080A200F1C7FC1262123C151D7F9318>I<EA7FFF
EA700E1260EA401C133813781370EA00E0120113C0EA038012071301120E121EEA1C03EA
3802EA7006130EEAFFFE10147F9314>I<B512FC1601808C17>I<B812F02C01808C2D>I
E /Ft 24 118 df<49B4FC011F13C090387F81E0EBFC013901F807F01203EA07F0A4EC01
C091C8FCA3EC3FF8B6FCA33807F003B3A33A7FFF3FFF80A3212A7FA925>12
D<130E131E137EEA07FE12FFA212F81200B3ABB512FEA317277BA622>49
D<EBFF80000713F04813FC381E03FE393800FF80007C133F00FE14C06C131F15E0140FA2
127E003C131FC7FC15C0A2EC3F801500147E5C5C495A495AEB078049C7FC131E4913E013
705B3901C001C0EA0380EA0600000FB5FC5A5A5AB61280A31B277DA622>I<EB7F803803
FFF04813FC380F81FE381F007FEA3F80EC3F80A3121F1300C7EA7F00A2147E5C495AEB07
F0EBFFC0A2EB01F8EB007E801580EC1FC0A215E0A2123C127EB4FCA215C0143F48148000
7CEB7F00383F01FE6CB45A000713F0C613801B277DA622>I<140FA25C5C5C5C5BA2EB03
BFEB073F130E131C133C1338137013E0EA01C0EA038012071300120E5A5A5A12F0B612F8
A3C7EA7F00A890381FFFF8A31D277EA622>I<EC0780A24A7EA34A7EA24A7EA3EC77F8A2
ECF7FC14E3A2903801C1FEA201037F1480A249486C7EA24980010E133FA2496D7EA2013F
B57EA39039700007F8A201F080491303000181491301A2000381D8FFFE013F13FCA32E29
7EA833>65 D<91387FE003903907FFFC07011FEBFF0F90397FF00F9F9039FF0001FFD801
FC7F4848147F4848143F4848141F485A160F485A1607127FA290C9FC5AA97E7F1607123F
A26C7E160E6C7E6C6C141C6C6C143C6C6C14786CB4EB01F090397FF007C0011FB5128001
07EBFE009038007FF028297CA831>67 D<B512F0A33803FC00B3B1B512F0A314297EA819
>73 D<ECFFC0010F13FC90383F807F9039FE001FC0D801F8EB07E048486D7E48486D7E00
0F8148486D7EA24848147FA2007F168090C8123FA34816C0AA6C16806D147FA2003F1600
A26C6C14FEA26C6C495A6C6C495A6C6C495A6C6C495A6C6C495A90263FC0FFC7FC90380F
FFFC010013C02A297CA833>79 D<B612E015FE6F7E3A03FC003FE0ED0FF06F7E6F7E1501
82A65E4B5A1507ED0FE0ED3FC090B500FEC7FCA29039FC00FF80ED3FC06F7E6F7E6F7EA9
170EA21503923801FC1CB538F000FEEE7FF8EE0FE02F297EA832>82
D<EB3FF03801FFFC3803F03E380FC07FEA1F80EA3F00A248133E007E90C7FCA212FEA712
7EA2127F6CEB03801380001FEB0700380FE00E3803F83C3801FFF838003FC0191B7E9A1E
>99 D<EC7FF0A31407ACEB3F873801FFF73807F03F380FC00F381F8007EA3F00A2127EA3
12FEA8127EA27EA2381F800F380FC01F3907E07FFF3801FFE738007F87202A7EA925>I<
EB3FC03801FFF03803E07C380F803E001F7F130048EB0F80127E15C0A200FE1307A2B6FC
A248C8FCA3127EA2127F6CEB01C07E390F8003803907C007003803F01E3800FFFCEB3FE0
1A1B7E9A1F>I<EB07F8EB3FFCEB7E3E3801FC7FEA03F813F01207143E1400A7B512C0A3
3807F000B3A3387FFF80A3182A7EA915>I<9038FF80F00003EBE3F8390FC1FE1C391F00
7C7C48137E003EEB3E10007EEB3F00A6003E133E003F137E6C137C380FC1F8380BFFE000
18138090C8FC1238A2123C383FFFF814FF6C14C06C14E06C14F0121F383C0007007CEB01
F8481300A4007CEB01F0A2003FEB07E0390FC01F806CB5120038007FF01E287E9A22>I<
EAFFE0A3120FAC147E9038E1FF809038E30FC001E413E0EBE80701F813F013F0A213E0B0
39FFFE3FFFA3202A7DA925>I<1207EA0F80EA1FC0EA3FE0A3EA1FC0EA0F80EA0700C7FC
A7EAFFE0A3120FB3A3EAFFFEA30F2B7EAA12>I<EAFFE0A3120FB3B2EAFFFEA30F2A7EA9
12>108 D<38FFC07E9038C1FF809038C30FC0D80FC413E0EBC80701D813F013D0A213E0
B039FFFE3FFFA3201B7D9A25>110 D<EB3FE03801FFFC3803F07E390FC01F80391F800F
C0393F0007E0A2007EEB03F0A300FE14F8A8007E14F0A26CEB07E0A2391F800FC0390FC0
1F803907F07F003801FFFC38003FE01D1B7E9A22>I<38FFC1F0EBC7FCEBC63E380FCC7F
13D813D0A2EBF03EEBE000B0B5FCA3181B7F9A1B>114 D<3803FE30380FFFF0EA3E03EA
7800127000F01370A27E00FE1300EAFFE06CB4FC14C06C13E06C13F0000713F8C6FCEB07
FC130000E0137C143C7E14387E6C137038FF01E038E7FFC000C11300161B7E9A1B>I<13
E0A41201A31203A21207120F381FFFE0B5FCA2380FE000AD1470A73807F0E0000313C038
01FF8038007F0014267FA51A>I<39FFE07FF0A3000F1307B2140FA2000713173903F067
FF3801FFC738007F87201B7D9A25>I E /Fu 11 116 df<B61280A4190480971F>45
D<DB0FFC142092B500C01360020314F091271FFC00F813E0DA3FE0131E02FFC7EA0701D9
01FCEC0381D907F8EC01C3D90FE0EC0067494815774948153F49C9121F01FE160F5B0001
1707485A491603120748481601A2121F491600A2123F5B1960127FA390CCFC5AAD7E7F19
60A2123FA27F121F19C07F120FA26C6CEE018012036DEE03006C7E000017067F017F5E6D
6C5D6D6C15386D6C5DD907F85DD901FC4A5A6DB4EC0780DA3FE0011EC7FCDA1FFC13FC02
03B512F0020014C0DB0FFEC8FC3B497CC745>67 D<B712C016FCEEFF80000190C7EA7FE0
6C48EC0FF0EE03FCEE00FE177F717E717E84170F84A2170784A760170F60A24D5A604DC8
FC177E5FEE03F8EE0FE0EEFF8090B600FCC9FC16F049C712FE163FEE0FC0707E707E707E
83160083A2177E177FA784A7F1018018C0173FA2051FEB0300EF0FE0486C1706B500FE91
3807F00E943801FC1C9438007FF8CBEA0FE041487CC646>82 D<49B45B010FEBE003013F
13F89039FE00FC07D801F0131F4848EB078FD80780EB03CF48C7EA01DF486EB4FC001E81
488182127C007881A212F882A46C81A3127E007F92C7FCA26C7E13E06C7EEA0FFEEBFFE0
6C13FC6CEBFFC06C14FC6C6C13FF6D14C0010780010080020F7F02007FED0FFEED03FF15
00EE7F80163FEE1FC0160FA2EE07E012C0A21603A47EA217C07E16077E17806C150F6C16
006C151ED8FB80143ED8F1C05CD8F0F05CD8E07EEB03F090393FC00FE0D8C00FB5128001
0149C7FC3980003FF02B497CC735>I<16FC153FA315011500167CB3A414FF010713E090
381F80F090387E001C01F81306484813034848EB01FC485A000F140049147C121F48C8FC
A35A127EA212FEAA127EA2127FA27EA26C7E16FC120F6C6C13016C6CEB037C6C6C13066C
6CEB0C7E017CEB387F90263F80F013F890380FFFC0903801FE002D487DC735>100
D<49B4FC010F13E090381F03F090387C00FC49133ED801E07F000315804848130F484814
C0001F140716E048C7FCA21503007E15F0A312FEB7FCA248C9FCA7127EA2127F7EA26C6C
1430A2000F15607F6C6C14C0000314016C6C1480D800FCEB0700013F130E90381FC07890
3807FFE001001380242C7EAB2A>I<EA03F012FFA3120712031201B3B3B3A8487EB512E0
A313487EC719>108 D<2703F003FEEC7FC000FF903B0FFF8001FFF0913B380FE00701FC
913B6001F00C003E000790278000F8107FD803F1C7D878207FD801F2DA7C408001F615C0
01F46E486D7E01FC143F4992C7FCA349143EB3A9486C027F4A7EB528E01FFFFC03B51280
A3492C7DAB51>I<3903F003FC00FFEB1FFF9138380FC091386003E0000790388001F0D8
03F1C77EEA01F213F601F4147C13F8A35BB3AA486C14FEB539E03FFFF8A32D2C7DAB35>
I<ECFF80010713F090381F80FC90387E003F01F8EB0F8048486D7E48486D7E48486D7E48
486D7EA248C8127CA248157EA2007E81A300FE1680AA007E1600A2007F5D6C157EA36C6C
5C000F5D6D130100075D6C6C495A6C6C495A6C6C495A017E013FC7FC90381F80FC903807
FFF001001380292C7EAB2F>I<90383FE0083901FFFC183907C01F38390F0003F8001C13
0148130000781478127000F01438A21518A27EA2127C007F1400EA3FC013FC381FFFE000
0713FC6C13FFC614C0010F13E09038007FF0EC07F8140100C0EB00FC157C153E7E151EA2
7EA36C141C153C6C14386C147800F714F039E38001E039E0F00FC039C07FFF0038800FF8
1F2C7EAB25>115 D E end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 535 312 a Fu(Reed-Solomon)31 b(Co)s(des)224 516
y Ft(1)67 b(In)n(tro)r(duction)224 617 y Fs(A)18 b(Reed-Solomon)g
(\(RS\))g(co)q(de)g(is)g(an)f(error-correcting)g(co)q(de)h(\014rst)f
(describ)q(ed)j(in)e(a)224 674 y(pap)q(er)c(b)o(y)g(Reed)h(and)f
(Solomon)g(in)g(1960)f([8)o(].)19 b(Enco)q(ding)c(data)e(using)i(an)e
(RS)i(co)q(de)f(is)224 730 y(relativ)o(ely)k(straigh)o(tforw)o(ard,)d
(but)i(deco)q(ding)i(is)e(time-consuming.)27 b(Despite)17
b(ma)s(jor)224 787 y(e\016ciency)j(impro)o(v)o(emen)o(ts)e(made)h(b)o
(y)f(Berlek)m(amp)i(and)e(others)g(during)i(the)e(1960's)224
843 y([1,)11 b(4,)g(5,)h(7],)f(only)i(in)g(the)f(past)g(few)f(y)o(ears)
h(has)g(it)g(b)q(ecome)h(computationally)g(p)q(ossible)224
899 y(to)19 b(send)i(high-bandwidth)h(data)d(using)i(RS)f(co)q(des.)34
b(Recen)o(t)21 b(applications)g(of)f(RS)224 956 y(co)q(des)d(include)i
(CD-R)o(OMs,)e(wireless)g(comm)o(unications,)g(space)g(comm)o
(unications,)224 1012 y(DSL,)e(D)o(VD,)f(and)i(digital)g(TV.)295
1069 y(An)h(RS)h(co)q(de)g(di\013ers)g(from)f(a)g(Hamming)g(co)q(de)h
(in)g(that)f(it)h(enco)q(des)g(groups)f(of)224 1125 y(bits)k(instead)h
(of)e(one)h(bit)h(at)e(a)g(time.)37 b(W)l(e)21 b(will)i(call)f(these)f
(groups)f(\\digits")h(\(or)224 1182 y(\\sym)o(b)q(ols")14
b(or)g(\\co)q(e\016cien)o(ts"\).)19 b(A)14 b(digit)h(is)g(error-free)f
(if)g(and)h(only)f(if)h(all)g(of)f(its)g(bits)224 1238
y(are)g(error-free.)19 b(F)l(or)14 b(instance,)g(if)h(a)f(digit)h(is)g
(an)f(8-bit)g(c)o(haracter,)g(and)g(three)g(bits)h(of)224
1295 y(the)i(same)f(single)i(c)o(haracter)d(are)h(in)i(error,)d(w)o(e)i
(will)h(coun)o(t)e(that)g(as)g(one)g(corrupted)224 1351
y(digit.)21 b(There)14 b(are)g(t)o(w)o(o)f(corrupted)h(digits)h(\(but)f
(more)f(than)h(t)o(w)o(o)f(corrupted)h(bits\))h(in)224
1408 y(the)g(follo)o(wing)h(example.)370 1506 y(Original)e(:)81
b(10110001)39 b(11011111)g(01001011)h(01011100)370 1562
y(Receiv)o(ed)15 b(:)67 b(10110101)39 b(11011111)g(01110001)h(01011100)
370 1619 y(Corrupted?)102 b(y)o(es)169 b(no)g(y)o(es)g(no)295
1717 y(If)15 b(w)o(e)g(w)o(an)o(t)f(to)h(send)h(a)f Fr(k)q
Fs(-digit)h(plain)o(text)g(message,)f(RS)h(will)h(send)f
Fr(n)d Fs(=)g Fr(k)e Fs(+)g(2)p Fr(s)224 1773 y Fs(digits,)17
b(and)f(guaran)o(tee)g(that)f(the)h(correct)g(message)g(can)g(b)q(e)h
(reconstructed)f(at)f(the)224 1830 y(other)g(end)h(if)f(there)h(are)f
(few)o(er)f(than)i Fr(s)f Fs(corrupted)g(digits.)295
1886 y(An)10 b(example)i(of)e(commonly)g(used)h(parameters:)17
b Fr(k)d Fs(=)f(223,)d Fr(s)j Fs(=)g(16,)d Fr(n)j Fs(=)g
Fr(k)r Fs(+)q(2)p Fr(s)f Fs(=)224 1943 y(255,)k(giving)h(the)g(abilit)o
(y)h(to)e(correct)g(16)g(corrupted)h(digits)g(out)g(of)f(ev)o(ery)g
(255-digit)224 1999 y(transmission.)24 b(In)18 b(general,)e(the)h(n)o
(um)o(b)q(er)g(of)f(bits)h(in)g(a)g(digit)g(and)g(the)f(parameters)224
2056 y Fr(n)e Fs(and)g Fr(s)g Fs(are)f(tuned)h(to)f(optimize)i(for)e(y)
o(our)g(application.)21 b(A)14 b(CD-R)o(OM)f(can)h(correct)224
2112 y(a)h(burst)g(of)g(up)h(to)e(4000)g(consecutiv)o(e)i(errors.)224
2255 y Ft(2)67 b(Outline)24 b(of)d(enco)r(ding)224 2357
y Fs(No)o(w)12 b(w)o(e'll)i(describ)q(e)h(the)e(RS)g(enco)q(ding.)21
b(The)13 b(k)o(ey)g(to)f(it)h(all)h(is)f(to)g(view)g(the)g(digits)h(of)
224 2413 y(the)g(message)g(that)f(is)h(to)g(b)q(e)g(enco)q(ded)i(as)d
(if)i(they)f(are)f(the)i(co)q(e\016cien)o(ts)f(of)g(a)g(p)q(olyno-)224
2470 y(mial.)20 b(If)13 b(there)g(are)f Fr(j)j Fs(distinct)f(digit)f(v)
m(alues)h(\(e.g.,)e(256)g(distinct)h(8-bit)h(digit)f(v)m(alues\),)960
2613 y(1)p eop
%%Page: 2 2
2 1 bop 224 286 a Fs(w)o(e'll)18 b(create)f(a)g(mapping)h(b)q(et)o(w)o
(een)g(these)f(v)m(alues)i(and)e(the)h(elemen)o(ts)g(of)e(a)h(\014eld)i
Fr(F)224 343 y Fs(with)f Fr(j)h Fs(elemen)o(ts.)26 b(Our)17
b(c)o(hoice)h(of)f Fr(F)23 b Fs(will)c(b)q(e)f(describ)q(ed)h(later,)e
(but)g(for)f(no)o(w)h(just)224 399 y(understand)i(that)e(this)h
(de\014nes)h(ho)o(w)e(the)h(basic)h(arithmetic)f(op)q(erations)g(w)o
(ork)f(for)224 456 y(digits.)24 b(F)l(or)16 b(a)g Fr(k)q
Fs(-digit)h(message)f(whose)g(digits)h(are)f Fr(m)1191
463 y Fq(0)1211 456 y Fr(;)8 b(m)1272 463 y Fq(1)1290
456 y Fr(;)g(:)g(:)g(:)13 b(;)8 b(m)1440 463 y Fp(k)q
Fo(\000)p Fq(1)1505 456 y Fs(,)16 b(w)o(e)g(de\014ne)224
512 y(the)i(corresp)q(onding)g(message)f(p)q(olynomial)i(to)e(b)q(e)h
Fr(m)p Fs(\()p Fr(x)p Fs(\))d(=)i Fr(m)1344 519 y Fq(0)1375
512 y Fs(+)12 b Fr(m)1462 519 y Fq(1)1482 512 y Fr(x)f
Fs(+)h Fr(m)1606 519 y Fq(2)1626 512 y Fr(x)1652 496
y Fq(2)1683 512 y Fs(+)224 569 y Fn(\001)c(\001)g(\001)g
Fs(+)j Fr(m)373 576 y Fp(k)q Fo(\000)p Fq(1)439 569 y
Fr(x)465 552 y Fp(k)q Fo(\000)p Fq(1)532 569 y Fs(,)j(where)i(the)f(co)
q(e\016cien)o(ts)h Fr(m)1039 576 y Fq(0)1059 569 y Fr(;)8
b(m)1120 576 y Fq(1)1139 569 y Fr(;)g(:)g(:)g(:)k(;)c(m)1288
576 y Fp(k)q Fo(\000)p Fq(1)1369 569 y Fs(of)15 b(the)g(p)q(olynomial)
224 625 y Fr(m)p Fs(\()p Fr(x)p Fs(\))f(are)g(elemen)o(ts)i(of)e
Fr(F)6 b Fs(.)20 b(W)l(e)15 b(use)g Fr(F)6 b Fs([)p Fr(x)p
Fs(])14 b(to)g(denote)h(the)g(set)g(of)f(p)q(olynomials)i(with)224
682 y(co)q(e\016cien)o(ts)g(in)g Fr(F)6 b Fs(;)16 b(so)e
Fr(m)p Fs(\()p Fr(x)p Fs(\))e Fn(2)h Fr(F)6 b Fs([)p
Fr(x)p Fs(].)295 738 y(Recall)18 b(that)e(there)h(is)g(exactly)h(one)e
(p)q(olynomial)j(of)d(degree)h Fr(k)c Fn(\000)e Fs(1)17
b(that)f(passes)224 795 y(through)f Fr(k)h Fs(p)q(oin)o(ts)g(\()p
Fr(x)617 802 y Fq(0)636 795 y Fr(;)8 b(y)679 802 y Fq(0)699
795 y Fs(\))p Fr(;)g(:)g(:)g(:)k(;)c Fs(\()p Fr(x)870
802 y Fp(k)q Fo(\000)p Fq(1)935 795 y Fr(;)g(y)978 802