⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 bbsanc_php.htm

📁 rs纠错算法
💻 HTM
📖 第 1 页 / 共 4 页
字号:
🔍
1234 
      class=content>发信人:&nbsp;goloho&nbsp;(我想你),&nbsp;信区:&nbsp;Commun&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<BR>标&nbsp;&nbsp;题:&nbsp;rs编码的源程序。<BR>发信站:&nbsp;BBS&nbsp;水木清华站&nbsp;(Fri&nbsp;Jul&nbsp;27&nbsp;08:12:19&nbsp;2001)<BR><BR>由于太多人向我索求rs程序，所以考虑再三还是把它贴出来，不过首先申明，此程序只<BR>作研究用！<BR>/*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rs.c&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>/*&nbsp;This&nbsp;program&nbsp;is&nbsp;an&nbsp;encoder/decoder&nbsp;for&nbsp;Reed-Solomon&nbsp;codes.&nbsp;Encoding&nbsp;is&nbsp;in<BR><BR>&nbsp;&nbsp;&nbsp;systematic&nbsp;form,&nbsp;decoding&nbsp;via&nbsp;the&nbsp;Berlekamp&nbsp;iterative&nbsp;algorithm.<BR>&nbsp;&nbsp;&nbsp;In&nbsp;the&nbsp;present&nbsp;form&nbsp;,&nbsp;the&nbsp;constants&nbsp;mm,&nbsp;nn,&nbsp;tt,&nbsp;and&nbsp;kk=nn-2tt&nbsp;must&nbsp;be<BR>&nbsp;&nbsp;&nbsp;specified&nbsp;&nbsp;(the&nbsp;double&nbsp;letters&nbsp;are&nbsp;used&nbsp;simply&nbsp;to&nbsp;avoid&nbsp;clashes&nbsp;with<BR>&nbsp;&nbsp;&nbsp;other&nbsp;n,k,t&nbsp;used&nbsp;in&nbsp;other&nbsp;programs&nbsp;into&nbsp;which&nbsp;this&nbsp;was&nbsp;incorporated!)<BR>&nbsp;&nbsp;&nbsp;Also,&nbsp;the&nbsp;irreducible&nbsp;polynomial&nbsp;used&nbsp;to&nbsp;generate&nbsp;GF(2**mm)&nbsp;must&nbsp;also&nbsp;be<BR>&nbsp;&nbsp;&nbsp;entered&nbsp;--&nbsp;these&nbsp;can&nbsp;be&nbsp;found&nbsp;in&nbsp;Lin&nbsp;and&nbsp;Costello,&nbsp;and&nbsp;also&nbsp;Clark&nbsp;and&nbsp;Cai<BR>n.<BR>&nbsp;&nbsp;&nbsp;The&nbsp;representation&nbsp;of&nbsp;the&nbsp;elements&nbsp;of&nbsp;GF(2**m)&nbsp;is&nbsp;either&nbsp;in&nbsp;index&nbsp;form,<BR>&nbsp;&nbsp;&nbsp;where&nbsp;the&nbsp;number&nbsp;is&nbsp;the&nbsp;power&nbsp;of&nbsp;the&nbsp;primitive&nbsp;element&nbsp;alpha,&nbsp;which&nbsp;is<BR>&nbsp;&nbsp;&nbsp;convenient&nbsp;for&nbsp;multiplication&nbsp;(add&nbsp;the&nbsp;powers&nbsp;modulo&nbsp;2**m-1)&nbsp;or&nbsp;in<BR>&nbsp;&nbsp;&nbsp;polynomial&nbsp;form,&nbsp;where&nbsp;the&nbsp;bits&nbsp;represent&nbsp;the&nbsp;coefficients&nbsp;of&nbsp;the<BR>&nbsp;&nbsp;&nbsp;polynomial&nbsp;representation&nbsp;of&nbsp;the&nbsp;number,&nbsp;which&nbsp;is&nbsp;the&nbsp;most&nbsp;convenient&nbsp;for<BR>m<BR>&nbsp;&nbsp;&nbsp;for&nbsp;addition.&nbsp;&nbsp;The&nbsp;two&nbsp;forms&nbsp;are&nbsp;swapped&nbsp;between&nbsp;via&nbsp;lookup&nbsp;tables.<BR>&nbsp;&nbsp;&nbsp;This&nbsp;leads&nbsp;to&nbsp;fairly&nbsp;messy&nbsp;looking&nbsp;expressions,&nbsp;but&nbsp;unfortunately,&nbsp;there<BR>&nbsp;&nbsp;&nbsp;is&nbsp;no&nbsp;easy&nbsp;alternative&nbsp;when&nbsp;working&nbsp;with&nbsp;Galois&nbsp;arithmetic.<BR>&nbsp;&nbsp;&nbsp;The&nbsp;code&nbsp;is&nbsp;not&nbsp;written&nbsp;in&nbsp;the&nbsp;most&nbsp;elegant&nbsp;way,&nbsp;but&nbsp;to&nbsp;the&nbsp;best<BR>&nbsp;&nbsp;&nbsp;of&nbsp;my&nbsp;knowledge,&nbsp;(no&nbsp;absolute&nbsp;guarantees!),&nbsp;it&nbsp;works.<BR>&nbsp;&nbsp;&nbsp;However,&nbsp;when&nbsp;including&nbsp;it&nbsp;into&nbsp;a&nbsp;simulation&nbsp;program,&nbsp;you&nbsp;may&nbsp;want&nbsp;to&nbsp;do<BR>&nbsp;&nbsp;&nbsp;some&nbsp;conversion&nbsp;of&nbsp;global&nbsp;variables&nbsp;(used&nbsp;here&nbsp;because&nbsp;I&nbsp;am&nbsp;lazy!)&nbsp;to<BR>&nbsp;&nbsp;&nbsp;local&nbsp;variables&nbsp;where&nbsp;appropriate,&nbsp;and&nbsp;passing&nbsp;parameters&nbsp;(eg&nbsp;array<BR>&nbsp;&nbsp;&nbsp;addresses)&nbsp;to&nbsp;the&nbsp;functions&nbsp;&nbsp;may&nbsp;be&nbsp;a&nbsp;sensible&nbsp;move&nbsp;to&nbsp;reduce&nbsp;the&nbsp;number<BR>&nbsp;&nbsp;&nbsp;of&nbsp;global&nbsp;variables&nbsp;and&nbsp;thus&nbsp;decrease&nbsp;the&nbsp;chance&nbsp;of&nbsp;a&nbsp;bug&nbsp;being&nbsp;introduce<BR>d.<BR>&nbsp;&nbsp;&nbsp;This&nbsp;program&nbsp;does&nbsp;not&nbsp;handle&nbsp;erasures&nbsp;at&nbsp;present,&nbsp;but&nbsp;should&nbsp;not&nbsp;be&nbsp;hard<BR>&nbsp;&nbsp;&nbsp;to&nbsp;adapt&nbsp;to&nbsp;do&nbsp;this,&nbsp;as&nbsp;it&nbsp;is&nbsp;just&nbsp;an&nbsp;adjustment&nbsp;to&nbsp;the&nbsp;Berlekamp-Massey<BR>&nbsp;&nbsp;&nbsp;algorithm.&nbsp;It&nbsp;also&nbsp;does&nbsp;not&nbsp;attempt&nbsp;to&nbsp;decode&nbsp;past&nbsp;the&nbsp;BCH&nbsp;bound&nbsp;--&nbsp;see<BR>&nbsp;&nbsp;&nbsp;Blahut&nbsp;"Theory&nbsp;and&nbsp;practice&nbsp;of&nbsp;error&nbsp;control&nbsp;codes"&nbsp;for&nbsp;how&nbsp;to&nbsp;do&nbsp;this.<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Simon&nbsp;Rockliff,&nbsp;University&nbsp;of&nbsp;Adelaide&nbsp;&nbsp;&nbsp;21/9/89<BR>&nbsp;&nbsp;&nbsp;26/6/91&nbsp;Slight&nbsp;modifications&nbsp;to&nbsp;remove&nbsp;a&nbsp;compiler&nbsp;dependent&nbsp;bug&nbsp;which&nbsp;had<BR>n't<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;previously&nbsp;surfaced.&nbsp;A&nbsp;few&nbsp;extra&nbsp;comments&nbsp;added&nbsp;for&nbsp;clarity.<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Appears&nbsp;to&nbsp;all&nbsp;work&nbsp;fine,&nbsp;ready&nbsp;for&nbsp;posting&nbsp;to&nbsp;net!<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Notice<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;--------<BR>&nbsp;&nbsp;&nbsp;This&nbsp;program&nbsp;may&nbsp;be&nbsp;freely&nbsp;modified&nbsp;and/or&nbsp;given&nbsp;to&nbsp;whoever&nbsp;wants&nbsp;it.<BR>&nbsp;&nbsp;&nbsp;A&nbsp;condition&nbsp;of&nbsp;such&nbsp;distribution&nbsp;is&nbsp;that&nbsp;the&nbsp;author's&nbsp;contribution&nbsp;be<BR>&nbsp;&nbsp;&nbsp;acknowledged&nbsp;by&nbsp;his&nbsp;name&nbsp;being&nbsp;left&nbsp;in&nbsp;the&nbsp;comments&nbsp;heading&nbsp;the&nbsp;program,<BR>&nbsp;&nbsp;&nbsp;however&nbsp;no&nbsp;responsibility&nbsp;is&nbsp;accepted&nbsp;for&nbsp;any&nbsp;financial&nbsp;or&nbsp;other&nbsp;loss&nbsp;whi<BR>ch<BR>&nbsp;&nbsp;&nbsp;may&nbsp;result&nbsp;from&nbsp;some&nbsp;unforseen&nbsp;errors&nbsp;or&nbsp;malfunctioning&nbsp;of&nbsp;the&nbsp;program<BR>&nbsp;&nbsp;&nbsp;during&nbsp;use.<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Simon&nbsp;Rockliff,&nbsp;26th&nbsp;June&nbsp;1991<BR>*/<BR>#include&nbsp;&lt;math.h&gt;<BR>#include&nbsp;&lt;stdio.h&gt;<BR>#define&nbsp;mm&nbsp;&nbsp;4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;RS&nbsp;code&nbsp;over&nbsp;GF(2**4)&nbsp;-&nbsp;change&nbsp;to&nbsp;suit&nbsp;*/<BR>#define&nbsp;nn&nbsp;&nbsp;15&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;nn=2**mm&nbsp;-1&nbsp;&nbsp;&nbsp;length&nbsp;of&nbsp;codeword&nbsp;*/<BR>#define&nbsp;tt&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;number&nbsp;of&nbsp;errors&nbsp;that&nbsp;can&nbsp;be&nbsp;corrected&nbsp;*/<BR>#define&nbsp;kk&nbsp;&nbsp;9&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;kk&nbsp;=&nbsp;nn-2*tt&nbsp;&nbsp;*/<BR>int&nbsp;pp&nbsp;[mm+1]&nbsp;=&nbsp;{&nbsp;1,&nbsp;1,&nbsp;0,&nbsp;0,&nbsp;1}&nbsp;;&nbsp;/*&nbsp;specify&nbsp;irreducible&nbsp;polynomial&nbsp;coeffts<BR>&nbsp;*/<BR>int&nbsp;alpha_to&nbsp;[nn+1],&nbsp;index_of&nbsp;[nn+1],&nbsp;gg&nbsp;[nn-kk+1]&nbsp;;<BR>int&nbsp;recd&nbsp;[nn],&nbsp;data&nbsp;[kk],&nbsp;bb&nbsp;[nn-kk]&nbsp;;<BR>void&nbsp;generate_gf()<BR>/*&nbsp;generate&nbsp;GF(2**mm)&nbsp;from&nbsp;the&nbsp;irreducible&nbsp;polynomial&nbsp;p(X)&nbsp;in&nbsp;pp[0]..pp[mm]<BR>&nbsp;&nbsp;&nbsp;lookup&nbsp;tables:&nbsp;&nbsp;index-&gt;polynomial&nbsp;form&nbsp;&nbsp;&nbsp;alpha_to[]&nbsp;contains&nbsp;j=alpha**i;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;polynomial&nbsp;form&nbsp;-&gt;&nbsp;index&nbsp;form&nbsp;&nbsp;index_of[j=alpha**i]&nbsp;=&nbsp;i<BR>&nbsp;&nbsp;&nbsp;alpha=2&nbsp;is&nbsp;the&nbsp;primitive&nbsp;element&nbsp;of&nbsp;GF(2**mm)<BR>*/<BR>&nbsp;{<BR>&nbsp;&nbsp;&nbsp;register&nbsp;int&nbsp;i,&nbsp;mask&nbsp;;<BR>&nbsp;&nbsp;mask&nbsp;=&nbsp;1&nbsp;;<BR>&nbsp;&nbsp;alpha_to[mm]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;mm;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;{&nbsp;alpha_to[i]&nbsp;=&nbsp;mask&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index_of[alpha_to[i]]&nbsp;=&nbsp;i&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(pp[i]!=0)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alpha_to[mm]&nbsp;^=&nbsp;mask&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mask&nbsp;&lt;&lt;=&nbsp;1&nbsp;;<BR>&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;index_of[alpha_to[mm]]&nbsp;=&nbsp;mm&nbsp;;<BR>&nbsp;&nbsp;mask&nbsp;&gt;&gt;=&nbsp;1&nbsp;;<BR>&nbsp;&nbsp;for&nbsp;(i=mm+1;&nbsp;i&lt;nn;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;{&nbsp;if&nbsp;(alpha_to[i-1]&nbsp;&gt;=&nbsp;mask)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;alpha_to[i]&nbsp;=&nbsp;alpha_to[mm]&nbsp;^&nbsp;((alpha_to[i-1]^mask)&lt;&lt;1)&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;alpha_to[i]&nbsp;=&nbsp;alpha_to[i-1]&lt;&lt;1&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index_of[alpha_to[i]]&nbsp;=&nbsp;i&nbsp;;<BR>&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;index_of[0]&nbsp;=&nbsp;-1&nbsp;;<BR>&nbsp;&nbsp;for(i=0;i&lt;5;i++)printf("gf%d&nbsp;is%d\n",i,alpha_to[i]);<BR>&nbsp;}<BR>void&nbsp;gen_poly()<BR>/*&nbsp;Obtain&nbsp;the&nbsp;generator&nbsp;polynomial&nbsp;of&nbsp;the&nbsp;tt-error&nbsp;correcting,&nbsp;length<BR>&nbsp;&nbsp;nn=(2**mm&nbsp;-1)&nbsp;Reed&nbsp;Solomon&nbsp;code&nbsp;&nbsp;from&nbsp;the&nbsp;product&nbsp;of&nbsp;(X+alpha**i),&nbsp;i=1..2*<BR>tt<BR>*/<BR>&nbsp;{<BR>&nbsp;&nbsp;&nbsp;register&nbsp;int&nbsp;i,j&nbsp;;<BR>&nbsp;&nbsp;&nbsp;gg[0]&nbsp;=&nbsp;2&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;primitive&nbsp;element&nbsp;alpha&nbsp;=&nbsp;2&nbsp;&nbsp;for&nbsp;GF(2**mm)&nbsp;&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;gg[1]&nbsp;=&nbsp;1&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;g(x)&nbsp;=&nbsp;(X+alpha)&nbsp;initially&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;for&nbsp;(i=2;&nbsp;i&lt;=nn-kk;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;gg[i]&nbsp;=&nbsp;1&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(j=i-1;&nbsp;j&gt;0;&nbsp;j--)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(gg[j]&nbsp;!=&nbsp;0)&nbsp;&nbsp;gg[j]&nbsp;=&nbsp;gg[j-1]^&nbsp;alpha_to[(index_of[gg[j]]+i)%nn]&nbsp;;<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;gg[j]&nbsp;=&nbsp;gg[j-1]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;gg[0]&nbsp;=&nbsp;alpha_to[(index_of[gg[0]]+i)%nn]&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;gg[0]&nbsp;can&nbsp;never&nbsp;be&nbsp;z<BR>ero&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;/*&nbsp;convert&nbsp;gg[]&nbsp;to&nbsp;index&nbsp;form&nbsp;for&nbsp;quicker&nbsp;encoding&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;=nn-kk;&nbsp;i++)&nbsp;&nbsp;gg[i]&nbsp;=&nbsp;index_of[gg[i]]&nbsp;;<BR>&nbsp;}<BR>void&nbsp;encode_rs()<BR>/*&nbsp;take&nbsp;the&nbsp;string&nbsp;of&nbsp;symbols&nbsp;in&nbsp;data[i],&nbsp;i=0..(k-1)&nbsp;and&nbsp;encode&nbsp;systematical<BR>ly<BR>&nbsp;&nbsp;&nbsp;to&nbsp;produce&nbsp;2*tt&nbsp;parity&nbsp;symbols&nbsp;in&nbsp;bb[0]..bb[2*tt-1]<BR>&nbsp;&nbsp;&nbsp;data[]&nbsp;is&nbsp;input&nbsp;and&nbsp;bb[]&nbsp;is&nbsp;output&nbsp;in&nbsp;polynomial&nbsp;form.<BR>&nbsp;&nbsp;&nbsp;Encoding&nbsp;is&nbsp;done&nbsp;by&nbsp;using&nbsp;a&nbsp;feedback&nbsp;shift&nbsp;register&nbsp;with&nbsp;appropriate<BR>&nbsp;&nbsp;&nbsp;connections&nbsp;specified&nbsp;by&nbsp;the&nbsp;elements&nbsp;of&nbsp;gg[],&nbsp;which&nbsp;was&nbsp;generated&nbsp;above.<BR><BR>&nbsp;&nbsp;&nbsp;Codeword&nbsp;is&nbsp;&nbsp;&nbsp;c(X)&nbsp;=&nbsp;data(X)*X**(nn-kk)+&nbsp;b(X)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/<BR>&nbsp;{<BR>&nbsp;&nbsp;&nbsp;register&nbsp;int&nbsp;i,j&nbsp;;<BR>&nbsp;&nbsp;&nbsp;int&nbsp;feedback&nbsp;;<BR>&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;nn-kk;&nbsp;i++)&nbsp;&nbsp;&nbsp;bb[i]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;for&nbsp;(i=kk-1;&nbsp;i&gt;=0;&nbsp;i--)<BR>&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;feedback&nbsp;=&nbsp;index_of[data[i]^bb[nn-kk-1]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(feedback&nbsp;!=&nbsp;-1)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;for&nbsp;(j=nn-kk-1;&nbsp;j&gt;0;&nbsp;j--)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(gg[j]&nbsp;!=&nbsp;-1)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bb[j]&nbsp;=&nbsp;bb[j-1]^alpha_to[(gg[j]+feedback)%nn]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bb[j]&nbsp;=&nbsp;bb[j-1]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bb[0]&nbsp;=&nbsp;alpha_to[(gg[0]+feedback)%nn]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;for&nbsp;(j=nn-kk-1;&nbsp;j&gt;0;&nbsp;j--)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bb[j]&nbsp;=&nbsp;bb[j-1]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bb[0]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;;<BR>&nbsp;}&nbsp;;<BR>void&nbsp;decode_rs()<BR>/*&nbsp;assume&nbsp;we&nbsp;have&nbsp;received&nbsp;bits&nbsp;grouped&nbsp;into&nbsp;mm-bit&nbsp;symbols&nbsp;in&nbsp;recd[i],<BR>&nbsp;&nbsp;&nbsp;i=0..(nn-1),&nbsp;&nbsp;and&nbsp;recd[i]&nbsp;is&nbsp;index&nbsp;form&nbsp;(ie&nbsp;as&nbsp;powers&nbsp;of&nbsp;alpha).<BR>&nbsp;&nbsp;&nbsp;We&nbsp;first&nbsp;compute&nbsp;the&nbsp;2*tt&nbsp;syndromes&nbsp;by&nbsp;substituting&nbsp;alpha**i&nbsp;into&nbsp;rec(X)&nbsp;<BR>and<BR>&nbsp;&nbsp;&nbsp;evaluating,&nbsp;storing&nbsp;the&nbsp;syndromes&nbsp;in&nbsp;s[i],&nbsp;i=1..2tt&nbsp;(leave&nbsp;s[0]&nbsp;zero)&nbsp;.<BR>&nbsp;&nbsp;&nbsp;Then&nbsp;we&nbsp;use&nbsp;the&nbsp;Berlekamp&nbsp;iteration&nbsp;to&nbsp;find&nbsp;the&nbsp;error&nbsp;location&nbsp;polynomial<BR><BR>&nbsp;&nbsp;&nbsp;elp[i].&nbsp;&nbsp;&nbsp;If&nbsp;the&nbsp;degree&nbsp;of&nbsp;the&nbsp;elp&nbsp;is&nbsp;&gt;tt,&nbsp;we&nbsp;cannot&nbsp;correct&nbsp;all&nbsp;the&nbsp;erro<BR>rs<BR>&nbsp;&nbsp;&nbsp;and&nbsp;hence&nbsp;just&nbsp;put&nbsp;out&nbsp;the&nbsp;information&nbsp;symbols&nbsp;uncorrected.&nbsp;If&nbsp;the&nbsp;degree<BR>&nbsp;of<BR>&nbsp;&nbsp;&nbsp;elp&nbsp;is&nbsp;&lt;=tt,&nbsp;we&nbsp;substitute&nbsp;alpha**i&nbsp;,&nbsp;i=1..n&nbsp;into&nbsp;the&nbsp;elp&nbsp;to&nbsp;get&nbsp;the&nbsp;root<BR>s,<BR>&nbsp;&nbsp;&nbsp;hence&nbsp;the&nbsp;inverse&nbsp;roots,&nbsp;the&nbsp;error&nbsp;location&nbsp;numbers.&nbsp;If&nbsp;the&nbsp;number&nbsp;of&nbsp;err<BR>ors<BR>&nbsp;&nbsp;&nbsp;located&nbsp;does&nbsp;not&nbsp;equal&nbsp;the&nbsp;degree&nbsp;of&nbsp;the&nbsp;elp,&nbsp;we&nbsp;have&nbsp;more&nbsp;than&nbsp;tt&nbsp;errors<BR><BR>&nbsp;&nbsp;&nbsp;and&nbsp;cannot&nbsp;correct&nbsp;them.&nbsp;&nbsp;Otherwise,&nbsp;we&nbsp;then&nbsp;solve&nbsp;for&nbsp;the&nbsp;error&nbsp;value&nbsp;at<BR><BR>&nbsp;&nbsp;&nbsp;the&nbsp;error&nbsp;location&nbsp;and&nbsp;correct&nbsp;the&nbsp;error.&nbsp;&nbsp;The&nbsp;procedure&nbsp;is&nbsp;that&nbsp;found&nbsp;in<BR><BR>&nbsp;&nbsp;&nbsp;Lin&nbsp;and&nbsp;Costello.&nbsp;For&nbsp;the&nbsp;cases&nbsp;where&nbsp;the&nbsp;number&nbsp;of&nbsp;errors&nbsp;is&nbsp;known&nbsp;to&nbsp;be<BR>&nbsp;too<BR>&nbsp;&nbsp;&nbsp;large&nbsp;to&nbsp;correct,&nbsp;the&nbsp;information&nbsp;symbols&nbsp;as&nbsp;received&nbsp;are&nbsp;output&nbsp;(the<BR>&nbsp;&nbsp;&nbsp;advantage&nbsp;of&nbsp;systematic&nbsp;encoding&nbsp;is&nbsp;that&nbsp;hopefully&nbsp;some&nbsp;of&nbsp;the&nbsp;informatio<BR>n<BR>&nbsp;&nbsp;&nbsp;symbols&nbsp;will&nbsp;be&nbsp;okay&nbsp;and&nbsp;that&nbsp;if&nbsp;we&nbsp;are&nbsp;in&nbsp;luck,&nbsp;the&nbsp;errors&nbsp;are&nbsp;in&nbsp;the<BR>&nbsp;&nbsp;&nbsp;parity&nbsp;part&nbsp;of&nbsp;the&nbsp;transmitted&nbsp;codeword).&nbsp;&nbsp;Of&nbsp;course,&nbsp;these&nbsp;insoluble&nbsp;cas<BR>es<BR>&nbsp;&nbsp;&nbsp;can&nbsp;be&nbsp;returned&nbsp;as&nbsp;error&nbsp;flags&nbsp;to&nbsp;the&nbsp;calling&nbsp;routine&nbsp;if&nbsp;desired.&nbsp;&nbsp;&nbsp;*/<BR>&nbsp;{<BR>&nbsp;&nbsp;&nbsp;register&nbsp;int&nbsp;i,j,u,q&nbsp;;<BR>&nbsp;&nbsp;&nbsp;int&nbsp;elp[nn-kk+2][nn-kk],&nbsp;d[nn-kk+2],&nbsp;l[nn-kk+2],&nbsp;u_lu[nn-kk+2],&nbsp;s[nn-kk+1<BR>]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;int&nbsp;count=0,&nbsp;syn_error=0,&nbsp;root[tt],&nbsp;loc[tt],&nbsp;z[tt+1],&nbsp;err[nn],&nbsp;reg[tt+1]&nbsp;<BR>;<BR>/*&nbsp;first&nbsp;form&nbsp;the&nbsp;syndromes&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;for&nbsp;(i=1;&nbsp;i&lt;=nn-kk;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;s[i]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(j=0;&nbsp;j&lt;nn;&nbsp;j++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(recd[j]!=-1)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s[i]&nbsp;^=&nbsp;alpha_to[(recd[j]+i*j)%nn]&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;recd[j]&nbsp;in&nbsp;index&nbsp;form<BR>&nbsp;*/<BR>/*&nbsp;convert&nbsp;syndrome&nbsp;from&nbsp;polynomial&nbsp;form&nbsp;to&nbsp;index&nbsp;form&nbsp;&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(s[i]!=0)&nbsp;&nbsp;syn_error=1&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;set&nbsp;flag&nbsp;if&nbsp;non-zero&nbsp;syndrome&nbsp;=&gt;<BR>&nbsp;error&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s[i]&nbsp;=&nbsp;index_of[s[i]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;;<BR>&nbsp;&nbsp;&nbsp;if&nbsp;(syn_error)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;if&nbsp;errors,&nbsp;try&nbsp;and&nbsp;correct&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>/*&nbsp;compute&nbsp;the&nbsp;error&nbsp;location&nbsp;polynomial&nbsp;via&nbsp;the&nbsp;Berlekamp&nbsp;iterative&nbsp;algorit<BR>hm,<BR>&nbsp;&nbsp;&nbsp;following&nbsp;the&nbsp;terminology&nbsp;of&nbsp;Lin&nbsp;and&nbsp;Costello&nbsp;:&nbsp;&nbsp;&nbsp;d[u]&nbsp;is&nbsp;the&nbsp;'mu'th<BR>&nbsp;&nbsp;&nbsp;discrepancy,&nbsp;where&nbsp;u='mu'+1&nbsp;and&nbsp;'mu'&nbsp;(the&nbsp;Greek&nbsp;letter!)&nbsp;is&nbsp;the&nbsp;step&nbsp;numb<BR>er<BR>&nbsp;&nbsp;&nbsp;ranging&nbsp;from&nbsp;-1&nbsp;to&nbsp;2*tt&nbsp;(see&nbsp;L&amp;C),&nbsp;&nbsp;l[u]&nbsp;is&nbsp;the<BR>&nbsp;&nbsp;&nbsp;degree&nbsp;of&nbsp;the&nbsp;elp&nbsp;at&nbsp;that&nbsp;step,&nbsp;and&nbsp;u_l[u]&nbsp;is&nbsp;the&nbsp;difference&nbsp;between&nbsp;the<BR>&nbsp;&nbsp;&nbsp;step&nbsp;number&nbsp;and&nbsp;the&nbsp;degree&nbsp;of&nbsp;the&nbsp;elp.<BR>*/<BR>/*&nbsp;initialise&nbsp;table&nbsp;entries&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d[0]&nbsp;=&nbsp;0&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;index&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d[1]&nbsp;=&nbsp;s[1]&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;index&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elp[0][0]&nbsp;=&nbsp;0&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;index&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elp[1][0]&nbsp;=&nbsp;1&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;polynomial&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=1;&nbsp;i&lt;nn-kk;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;elp[0][i]&nbsp;=&nbsp;-1&nbsp;;&nbsp;&nbsp;&nbsp;/*&nbsp;index&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elp[1][i]&nbsp;=&nbsp;0&nbsp;;&nbsp;&nbsp;&nbsp;/*&nbsp;polynomial&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;l[0]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;l[1]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u_lu[0]&nbsp;=&nbsp;-1&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u_lu[1]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u++&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(d[u]==-1)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;l[u+1]&nbsp;=&nbsp;l[u]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;=l[u];&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;elp[u+1][i]&nbsp;=&nbsp;elp[u][i]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elp[u][i]&nbsp;=&nbsp;index_of[elp[u][i]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else<BR>/*&nbsp;search&nbsp;for&nbsp;words&nbsp;with&nbsp;greatest&nbsp;u_lu[q]&nbsp;for&nbsp;which&nbsp;d[q]!=0&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;q&nbsp;=&nbsp;u-1&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;((d[q]==-1)&nbsp;&amp;&amp;&nbsp;(q&gt;0))&nbsp;q--&nbsp;;<BR>/*&nbsp;have&nbsp;found&nbsp;first&nbsp;non-zero&nbsp;d[q]&nbsp;&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(q&gt;0)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;j=q&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;j--&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;((d[j]!=-1)&nbsp;&amp;&amp;&nbsp;(u_lu[q]&lt;u_lu[j]))<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q&nbsp;=&nbsp;j&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}while&nbsp;(j&gt;0)&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;;<BR>/*&nbsp;have&nbsp;now&nbsp;found&nbsp;q&nbsp;such&nbsp;that&nbsp;d[u]!=0&nbsp;and&nbsp;u_lu[q]&nbsp;is&nbsp;maximum&nbsp;*/<BR>/*&nbsp;store&nbsp;degree&nbsp;of&nbsp;new&nbsp;elp&nbsp;polynomial&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(l[u]&gt;l[q]+u-q)&nbsp;&nbsp;l[u+1]&nbsp;=&nbsp;l[u]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;&nbsp;l[u+1]&nbsp;=&nbsp;l[q]+u-q&nbsp;;<BR>/*&nbsp;form&nbsp;new&nbsp;elp(x)&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;nn-kk;&nbsp;i++)&nbsp;&nbsp;&nbsp;&nbsp;elp[u+1][i]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;=l[q];&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(elp[q][i]!=-1)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elp[u+1][i+u-q]&nbsp;=&nbsp;alpha_to[(d[u]+nn-d[q]+elp[q][i])%nn]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;=l[u];&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;elp[u+1][i]&nbsp;^=&nbsp;elp[u][i]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elp[u][i]&nbsp;=&nbsp;index_of[elp[u][i]]&nbsp;;&nbsp;&nbsp;/*convert&nbsp;old&nbsp;elp&nbsp;value&nbsp;t<BR>o&nbsp;index*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u_lu[u+1]&nbsp;=&nbsp;u-l[u+1]&nbsp;;<BR>/*&nbsp;form&nbsp;(u+1)th&nbsp;discrepancy&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(u&lt;nn-kk)&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;no&nbsp;discrepancy&nbsp;computed&nbsp;on&nbsp;last&nbsp;iteration&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(s[u+1]!=-1)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d[u+1]&nbsp;=&nbsp;alpha_to[s[u+1]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d[u+1]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=1;&nbsp;i&lt;=l[u+1];&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;((s[u+1-i]!=-1)&nbsp;&amp;&amp;&nbsp;(elp[u+1][i]!=0))<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d[u+1]&nbsp;^=&nbsp;alpha_to[(s[u+1-i]+index_of[elp[u+1][i]])%nn]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;d[u+1]&nbsp;=&nbsp;index_of[d[u+1]]&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;put&nbsp;d[u+1]&nbsp;into&nbsp;index&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;while&nbsp;((u&lt;nn-kk)&nbsp;&amp;&amp;&nbsp;(l[u+1]&lt;=tt))&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u++&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(l[u]&lt;=tt)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;can&nbsp;correct&nbsp;error&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>/*&nbsp;put&nbsp;elp&nbsp;into&nbsp;index&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;=l[u];&nbsp;i++)&nbsp;&nbsp;&nbsp;elp[u][i]&nbsp;=&nbsp;index_of[elp[u][i]]&nbsp;;<BR>/*&nbsp;find&nbsp;roots&nbsp;of&nbsp;the&nbsp;error&nbsp;location&nbsp;polynomial&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=1;&nbsp;i&lt;=l[u];&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;reg[i]&nbsp;=&nbsp;elp[u][i]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=1;&nbsp;i&lt;=nn;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;q&nbsp;=&nbsp;1&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(j=1;&nbsp;j&lt;=l[u];&nbsp;j++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(reg[j]!=-1)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;reg[j]&nbsp;=&nbsp;(reg[j]+j)%nn&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q&nbsp;^=&nbsp;alpha_to[reg[j]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!q)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;store&nbsp;root&nbsp;and&nbsp;error&nbsp;location&nbsp;number&nbsp;indices&nbsp;<BR>*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;root[count]&nbsp;=&nbsp;i;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;loc[count]&nbsp;=&nbsp;nn-i&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count++&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;};<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(count==l[u])&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;no.&nbsp;roots&nbsp;=&nbsp;degree&nbsp;of&nbsp;elp&nbsp;hence&nbsp;&lt;=&nbsp;tt&nbsp;errors<BR>&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>/*&nbsp;form&nbsp;polynomial&nbsp;z(x)&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=1;&nbsp;i&lt;=l[u];&nbsp;i++)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;Z[0]&nbsp;=&nbsp;1&nbsp;always&nbsp;-&nbsp;do&nbsp;not&nbsp;need&nbsp;*<BR>/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;if&nbsp;((s[i]!=-1)&nbsp;&amp;&amp;&nbsp;(elp[u][i]!=-1))<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;z[i]&nbsp;=&nbsp;alpha_to[s[i]]&nbsp;^&nbsp;alpha_to[elp[u][i]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if&nbsp;((s[i]!=-1)&nbsp;&amp;&amp;&nbsp;(elp[u][i]==-1))<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;z[i]&nbsp;=&nbsp;alpha_to[s[i]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if&nbsp;((s[i]==-1)&nbsp;&amp;&amp;&nbsp;(elp[u][i]!=-1))<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;z[i]&nbsp;=&nbsp;alpha_to[elp[u][i]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;z[i]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(j=1;&nbsp;j&lt;i;&nbsp;j++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;((s[j]!=-1)&nbsp;&amp;&amp;&nbsp;(elp[u][i-j]!=-1))<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;z[i]&nbsp;^=&nbsp;alpha_to[(elp[u][i-j]&nbsp;+&nbsp;s[j])%nn]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;z[i]&nbsp;=&nbsp;index_of[z[i]]&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;put&nbsp;into&nbsp;index&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;;<BR>&nbsp;&nbsp;/*&nbsp;evaluate&nbsp;errors&nbsp;at&nbsp;locations&nbsp;given&nbsp;by&nbsp;error&nbsp;location&nbsp;numbers&nbsp;loc[i]&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;nn;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;err[i]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(recd[i]!=-1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;convert&nbsp;recd[]&nbsp;to&nbsp;polynomial&nbsp;form&nbsp;<BR>*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;recd[i]&nbsp;=&nbsp;alpha_to[recd[i]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;&nbsp;recd[i]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;l[u];&nbsp;i++)&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;compute&nbsp;numerator&nbsp;of&nbsp;error&nbsp;term&nbsp;firs<BR>t&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;err[loc[i]]&nbsp;=&nbsp;1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;accounts&nbsp;for&nbsp;z[0]&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(j=1;&nbsp;j&lt;=l[u];&nbsp;j++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(z[j]!=-1)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;err[loc[i]]&nbsp;^=&nbsp;alpha_to[(z[j]+j*root[i])%nn]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(err[loc[i]]!=0)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;err[loc[i]]&nbsp;=&nbsp;index_of[err[loc[i]]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q&nbsp;=&nbsp;0&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;form&nbsp;denominator&nbsp;of&nbsp;error&nbsp;term&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(j=0;&nbsp;j&lt;l[u];&nbsp;j++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(j!=i)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q&nbsp;+=&nbsp;index_of[1^alpha_to[(loc[j]+root[i])%nn]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;q&nbsp;=&nbsp;q&nbsp;%&nbsp;nn&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;err[loc[i]]&nbsp;=&nbsp;alpha_to[(err[loc[i]]-q+nn)%nn]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;recd[loc[i]]&nbsp;^=&nbsp;err[loc[i]]&nbsp;;&nbsp;&nbsp;/*recd[i]&nbsp;must&nbsp;be&nbsp;in&nbsp;polynom<BR>ial&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;no.&nbsp;roots&nbsp;!=&nbsp;degree&nbsp;of&nbsp;elp&nbsp;=&gt;&nbsp;&gt;tt&nbsp;errors&nbsp;and&nbsp;cannot&nbsp;solv<BR>e&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;nn;&nbsp;i++)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;could&nbsp;return&nbsp;error&nbsp;flag&nbsp;if&nbsp;desired<BR>&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(recd[i]!=-1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;convert&nbsp;recd[]&nbsp;to&nbsp;polynomial&nbsp;form&nbsp;<BR>*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;recd[i]&nbsp;=&nbsp;alpha_to[recd[i]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;&nbsp;recd[i]&nbsp;=&nbsp;0&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;just&nbsp;output&nbsp;received&nbsp;codeword&nbsp;as&nbsp;i<BR>s&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;elp&nbsp;has&nbsp;degree&nbsp;has&nbsp;degree&nbsp;&gt;tt&nbsp;hence&nbsp;cannot&nbsp;solve&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;nn;&nbsp;i++)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;could&nbsp;return&nbsp;error&nbsp;flag&nbsp;if&nbsp;desired&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(recd[i]!=-1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;convert&nbsp;recd[]&nbsp;to&nbsp;polynomial&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;recd[i]&nbsp;=&nbsp;alpha_to[recd[i]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;&nbsp;recd[i]&nbsp;=&nbsp;0&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;just&nbsp;output&nbsp;received&nbsp;codeword&nbsp;as&nbsp;is&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;else&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;no&nbsp;non-zero&nbsp;syndromes&nbsp;=&gt;&nbsp;no&nbsp;errors:&nbsp;output&nbsp;received&nbsp;codewor<BR>d&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;nn;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(recd[i]!=-1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;convert&nbsp;recd[]&nbsp;to&nbsp;polynomial&nbsp;form&nbsp;*/<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;recd[i]&nbsp;=&nbsp;alpha_to[recd[i]]&nbsp;;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;&nbsp;recd[i]&nbsp;=&nbsp;0&nbsp;;<BR>&nbsp;}<BR>main()<BR>{<BR>&nbsp;&nbsp;register&nbsp;int&nbsp;i;<BR>/*&nbsp;generate&nbsp;the&nbsp;Galois&nbsp;Field&nbsp;GF(2**mm)&nbsp;*/<BR>&nbsp;&nbsp;generate_gf()&nbsp;;<BR>&nbsp;&nbsp;printf("Look-up&nbsp;tables&nbsp;for&nbsp;GF(2**%2d)\n",mm)&nbsp;;<BR>&nbsp;&nbsp;printf("&nbsp;&nbsp;i&nbsp;&nbsp;&nbsp;alpha_to[i]&nbsp;&nbsp;index_of[i]\n")&nbsp;;<BR>&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;=nn;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;printf("%3d&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;%3d&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;%3d\n",i,alpha_to[i],index_of[i])&nbsp;;<BR>&nbsp;&nbsp;printf("\n\n")&nbsp;;<BR>/*&nbsp;compute&nbsp;the&nbsp;generator&nbsp;polynomial&nbsp;for&nbsp;this&nbsp;RS&nbsp;code&nbsp;*/<BR>&nbsp;&nbsp;gen_poly()&nbsp;;<BR>/*&nbsp;for&nbsp;known&nbsp;data,&nbsp;stick&nbsp;a&nbsp;few&nbsp;numbers&nbsp;into&nbsp;a&nbsp;zero&nbsp;codeword.&nbsp;Data&nbsp;is&nbsp;in<BR>&nbsp;&nbsp;&nbsp;polynomial&nbsp;form.<BR>*/<BR>for&nbsp;&nbsp;(i=0;&nbsp;i&lt;kk;&nbsp;i++)&nbsp;&nbsp;&nbsp;data[i]&nbsp;=&nbsp;0&nbsp;;<BR>/*&nbsp;for&nbsp;example,&nbsp;say&nbsp;we&nbsp;transmit&nbsp;the&nbsp;following&nbsp;message&nbsp;(nothing&nbsp;special!)&nbsp;*/<BR>data[0]&nbsp;=&nbsp;8&nbsp;;<BR>data[1]&nbsp;=&nbsp;6&nbsp;;<BR>data[2]&nbsp;=&nbsp;8&nbsp;;<BR>data[3]&nbsp;=&nbsp;1&nbsp;;<BR>data[4]&nbsp;=&nbsp;2&nbsp;;<BR>data[5]&nbsp;=&nbsp;4&nbsp;;<BR>data[6]&nbsp;=&nbsp;15&nbsp;;<BR>data[7]&nbsp;=&nbsp;9&nbsp;;<BR>data[8]&nbsp;=&nbsp;9&nbsp;;<BR>/*&nbsp;encode&nbsp;data[]&nbsp;to&nbsp;produce&nbsp;parity&nbsp;in&nbsp;bb[].&nbsp;&nbsp;Data&nbsp;input&nbsp;and&nbsp;parity&nbsp;output<BR>&nbsp;&nbsp;&nbsp;is&nbsp;in&nbsp;polynomial&nbsp;form<BR>*/<BR>&nbsp;&nbsp;encode_rs()&nbsp;;<BR>/*&nbsp;put&nbsp;the&nbsp;transmitted&nbsp;codeword,&nbsp;made&nbsp;up&nbsp;of&nbsp;data&nbsp;plus&nbsp;parity,&nbsp;in&nbsp;recd[]&nbsp;*/<BR>&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;nn-kk;&nbsp;i++)&nbsp;&nbsp;recd[i]&nbsp;=&nbsp;bb[i]&nbsp;;<BR>&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;kk;&nbsp;i++)&nbsp;recd[i+nn-kk]&nbsp;=&nbsp;data[i]&nbsp;;<BR>/*&nbsp;if&nbsp;you&nbsp;want&nbsp;to&nbsp;test&nbsp;the&nbsp;program,&nbsp;corrupt&nbsp;some&nbsp;of&nbsp;the&nbsp;elements&nbsp;of&nbsp;recd[]<BR>&nbsp;&nbsp;&nbsp;here.&nbsp;This&nbsp;can&nbsp;also&nbsp;be&nbsp;done&nbsp;easily&nbsp;in&nbsp;a&nbsp;debugger.&nbsp;*/<BR>/*&nbsp;Again,&nbsp;lets&nbsp;say&nbsp;that&nbsp;a&nbsp;middle&nbsp;element&nbsp;is&nbsp;changed&nbsp;*/<BR>&nbsp;&nbsp;data[nn-nn/2]&nbsp;=&nbsp;3&nbsp;;<BR>&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;nn;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;recd[i]&nbsp;=&nbsp;index_of[recd[i]]&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;put&nbsp;recd[i]&nbsp;into&nbsp;index&nbsp;form&nbsp;*<BR>/<BR>/*&nbsp;decode&nbsp;recv[]&nbsp;*/<BR>&nbsp;&nbsp;decode_rs()&nbsp;;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;recd[]&nbsp;is&nbsp;returned&nbsp;in&nbsp;polynomial&nbsp;form&nbsp;*/<BR>/*&nbsp;print&nbsp;out&nbsp;the&nbsp;relevant&nbsp;stuff&nbsp;-&nbsp;initial&nbsp;and&nbsp;decoded&nbsp;{parity&nbsp;and&nbsp;message}&nbsp;*<BR>/<BR>&nbsp;&nbsp;printf("Results&nbsp;for&nbsp;Reed-Solomon&nbsp;code&nbsp;(n=%3d,&nbsp;k=%3d,&nbsp;t=&nbsp;%3d)\n\n",nn,kk,tt<BR>)&nbsp;;<BR>&nbsp;&nbsp;printf("&nbsp;&nbsp;i&nbsp;&nbsp;data[i]&nbsp;&nbsp;&nbsp;recd[i](decoded)&nbsp;&nbsp;&nbsp;(data,&nbsp;recd&nbsp;in&nbsp;polynomial&nbsp;form)\<BR>n");<BR>&nbsp;&nbsp;for&nbsp;(i=0;&nbsp;i&lt;nn-kk;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;printf("%3d&nbsp;&nbsp;&nbsp;&nbsp;%3d&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;%3d\n",i,&nbsp;bb[i],&nbsp;recd[i])&nbsp;;<BR>&nbsp;&nbsp;for&nbsp;(i=nn-kk;&nbsp;i&lt;nn;&nbsp;i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;printf("%3d&nbsp;&nbsp;&nbsp;&nbsp;%3d&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;%3d\n",i,&nbsp;data[i-nn+kk],&nbsp;recd[i])&nbsp;;<BR>}<BR><BR><BR>--<BR><BR>※&nbsp;来源:·BBS&nbsp;水木清华站&nbsp;smth.org·[FROM:&nbsp;202.119.230.80]<BR></FONT></TD></TR></TBODY></TABLE></CENTER>
<TABLE cellSpacing=0 cellPadding=3 width="100%" border=0>
  <TBODY>
  <TR>
    <TD background=bbsanc_php.files/dashed.gif colSpan=2 height=9></TD></TR>
  <TR>
    <TD class=b1 align=middle colSpan=2>[<A 
      href="http://www.smth.edu.cn/bbsanc.php?path=%2Fgroups%2Fsci.faq%2FCommun%2Fforum%2Fsimmu%2FC%2Frs#listtop">返回顶部</A>] 
      [<A href="javascript:location.reload()">刷新</A>] [<A 
      href="http://www.smth.edu.cn/bbsodoc.php?board=Commun">同主题模式</A>] [<A 
      href="http://www.smth.edu.cn/bbsdoc.php?board=Commun">普通模式</A>] [<A 
      href="http://www.smth.edu.cn/bbsbfind.php?board=Commun">版内查询</A>] 
  </TD></TR></TBODY></TABLE>
<P align=center>[<A 
href="http://www.smth.edu.cn/bbssfav.php?act=choose&amp;title=%BE%AB%BB%AA%C7%F8&amp;url=%2Fbbsanc.php%3Fpath%3D%252Fgroups%252Fsci.faq%252FCommun%252Fforum%252Fsimmu%252FC%252Frs&amp;type=0">我的百宝箱</A>] 
[<A href="http://www.smth.edu.cn/mainpage.php">返回首页</A>] [<A 
href="http://www.smth.edu.cn/bbs0an.php?path=%2Fgroups%2Fsci.faq%2FCommun%2Fforum%2Fsimmu%2FC">上级目录</A>] 
[<A href="http://www.smth.edu.cn/bbs0an.php">根目录</A>] [<A 
href="http://www.smth.edu.cn/bbsxsearch.php">令狐冲精华区搜索</A>] [<A 
href="http://www.smth.edu.cn/bbsanc.php?path=%2Fgroups%2Fsci.faq%2FCommun%2Fforum%2Fsimmu%2FC%2Frs#listtop">返回顶部</A>] 
[<A href="javascript:location.reload()">刷新</A>] [<A 
href="javascript:history.go(-1)">返回</A>] </P></BODY></HTML>
1234

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -