You are an expert at summarizing long articles. Proceed to summarize the following text: 
reed - solomon ( rs ) codes are among the most widely used codes . their applications range from consumer electronics such as compact disc ( cd ) and digital versatile disc ( dvd ) players to optical communication and data storage systems . most high - throughput rs codec architectures are based on reformulated versions @xcite of either the berlekamp - massey algorithm @xcite or the extended euclidean algorithm ( eea ) @xcite . a variable number of iterations  at most @xmath0 for correcting up to @xmath1 errors  are used in most eea - based decoders . one exception is the errors - only hypersystolic reed - solomon decoder proposed by berlekamp _ _ @xcite that uses exactly @xmath0 iterations regardless of the number of errors . of course , decoders based on the berlekamp - massey algorithm also use exactly @xmath0 iterations .    in this paper , new modifications of the eea are proposed for both errors - only ( eo ) decoding and errors - and - erasures ( ee ) decoding . first , a new modification of the eea for errors - only decoding is proposed based on the ideas in @xcite and @xcite . the new algorithm also uses _ exactly _ @xmath0 iterations , thus eliminating the degree computation and comparison in most variants of the eea ( see , for example , @xcite ) . one particular hardware implementation ( not described in this paper ) of this modified algorithm turns out to be the _ same _ circuit as that obtained by implementing the ribm algorithm of @xcite , with the difference that in one implementation the polynomials enter and leave the circuit in ascending order of coefficients while in the other implementation the polynomials enter and leave in descending order of coefficients ! the ribm algorithm is based on the berlekamp - massey algorithm , and this result gives yet _ another _ equivalence between the berlekamp - massey algorithm and the eea , different from those that have been described previously in @xcite and @xcite . the modified eea proposed in this paper can be extended to errors - and - erasures decoding , and used to derive an errors - and - erasures decoding algorithm that also iterates _ exactly _ @xmath0 times . this modified algorithm also combines the erasure - locator polynomial computation and the solution of the modified key equation in a seamless way . hardware implementation of this algorithm eliminates not only the degree computation and comparison ( see , e.g. , @xcite ) but also the separate block used for computing the erasure - locator polynomial ( see , for example , @xcite ) , thus leading to considerable savings . the codewords in a @xmath1-error - correcting cyclic reed - solomon code @xcite of block length @xmath2 over @xmath3 are the polynomials @xmath4 , with the property that the @xmath0 successive powers @xmath5 of @xmath6 , a primitive @xmath2-th root of unity in @xmath3 , are roots of @xmath7 . here , @xmath8 can be any integer , but is often chosen to be @xmath9 or @xmath10 for ease of implementation . the code has @xmath11 information symbols . suppose the codeword polynomial @xmath7 is transmitted and the received word , corrupted by errors , is @xmath12 where @xmath13 . the decoder computes the _ syndromes _ of the error polynomial @xmath14 : @xmath15 , @xmath16 the _ syndrome polynomial _ is defined as @xmath17 if @xmath18 errors have occurred , the error polynomial @xmath14 can be written as @xmath19 where @xmath20 , called the _ error values _ , are said to have occurred at the _ error locations _ @xmath21 respectively . the _ error - locator polynomial _ @xmath22 of degree @xmath18 is defined to be @xmath23 while the _ error - evaluator polynomial _ @xmath24 of degree less than @xmath18 is defined as @xmath25    the error - locator and error - evaluator polynomials defined above are related to the syndrome polynomial by the _ key equation : _ @xmath26 note that @xmath27 is known to the decoder , while @xmath22 and @xmath24 are not . as the name suggests , solving the key equation for both @xmath22 and @xmath24 is the most difficult part of the decoding process . in this paper , we focus on the eea algorithm @xcite for solving the key equation .    after the key equation is solved , the errors can be corrected by finding the error locations and computing the error values . the error locations can be found via the _ chien search _ : for each @xmath28 , @xmath29 , the decoder tests whether or not @xmath30 . if @xmath30 , @xmath31 , that is , @xmath32 . the value of the @xmath28-th transmitted symbol is computed via _ forney s formula _ : @xmath33 where @xmath34 is the formal derivative of @xmath22 . it is worth noting that most implementations of rs decoders compute and use @xmath35 and @xmath36 where @xmath37 is a nonzero scalar whose value is immaterial : @xmath35 has the same roots as @xmath22 and so the decoder finds the same error locations , and @xmath37 cancels out in ( [ eq : forney ] ) and so the decoder finds the same error values . henceforth , we ignore such scalar factors in @xmath22 and @xmath24 .      in some cases , the received words enter the decoder with some symbols specially marked as being highly unreliable and hence more likely to be in error than other symbols . these marked symbols are called erasures . for a code with minimum hamming distance @xmath38 , any pattern of @xmath39 erasures and @xmath18 errors can be corrected @xcite as long as @xmath40 let @xmath41 denote the ( unknown ) error locations and @xmath42 denote the known _ erasure locations_. as before , the error - locator polynomial is defined as @xmath43 while the _ erasure - locator polynomial _ is defined to be @xmath44 note that @xmath45 can be computed from the known erasure locations whereas @xmath46 is unknown . similarly , the error - evaluator polynomial is defined as @xmath47 and the _ erasure - evaluator polynomial _ is defined to be @xmath48 where @xmath49 and @xmath50 denote respectively the @xmath51-th error and _ erasure values_. also note that some of the erasure values might be zero .    if we define the _ errata - locator polynomial _ @xmath52 of degree @xmath53 as @xmath54 and the _ errata - evaluator polynomial _ @xmath55 as @xmath56 , then the key equation ( [ eq : keyeq ] ) still holds for the errata - locator and errata - evaluator polynomials . furthermore , the @xmath57 errata locations can be obtained from the errata - locator polynomial by the chien search and the correct values of the codeword symbols can be computed using forney s formula . note that the errors - only decoding is simply the special case of the errors - and - erasures decoding where @xmath58 and @xmath59 . as in errors - only decoders , typical implementations compute the same scalar multiple of all these polynomials , and the value of this scalar does not affect the results of any subsequent computations .      as described above , the decoding of rs codes involve three successive stages  syndrome computation ( sc ) , key equation solving ( kes ) , and errata correction ( ec ) . the implementation of syndrome computation and errata correction , which is described in , for example , @xcite-@xcite is generally straightforward and will not be discussed further in this paper . here , we will focus on the implementation of key equation solving , which is the most difficult part of the decoding process . sugiyama _ et al . _ @xcite first pointed out that the extended euclidean algorithm for computing the polynomial greatest common divisor ( gcd ) can be used to solve the key equation ( [ eq : keyeq ] ) . the eea , tailored to solving the key equation , can be stated as follows :    * eea for errors - only decoding : the eo algorithm *    1 . * initialization : set * @xmath60 , @xmath61 , + @xmath62 , @xmath63 , and @xmath64 . * iteration : while * @xmath65 \geq t$ ] , + @xmath66 by @xmath67 to obtain both + @xmath68 and the + @xmath69 . . + @xmath71 . * output : * @xmath72 , @xmath73 . let @xmath74 denote the value of @xmath28 when the eo algorithm stops . then , the outputs @xmath75 and @xmath76 are scalar multiples of @xmath52 and @xmath55 as defined in ( [ eq : errorlocator ] ) and ( [ eq : errorevaluator ] ) since @xmath77 is not necessarily @xmath10 . also , it can be shown that the polynomials @xmath78 computed by the eo algorithm have degrees @xmath79 that form a strictly decreasing sequence with @xmath80 , @xmath81 and @xmath82 . the drawbacks to efficient implementation of the above algorithm are as follows . * the degree @xmath83 of the quotient polynomial @xmath84 can vary with @xmath28 , and thus step 2 of the eo algorithm requires a variable number of computations . this complicates the control mechanism . furthermore , it is necessary to divide the coefficients of @xmath85 by the leading coefficient of @xmath67 in order to obtain the quotient polynomial @xmath84 . * determining the stopping condition @xmath86 < t$ ] is difficult since data needs to be gathered from many different cells in the circuit . these two drawbacks have motivated many improvements . brent and kung @xcite proposed a systolic array implementation of the polynomial gcd algorithm in which each of the polynomial division operations involved is broken into a sequence of partial divisions , as humans often do in the `` long division '' method . in fact , this idea had been pointed out even earlier ( see , for example , @xcite ) . brent and kung also proposed using cross multiplications to avoid dividing one polynomial coefficient by another . these notions can be explained as follows . let @xmath87 and @xmath88 denote polynomials of degrees @xmath89 and @xmath90 respectively where @xmath91 . then , in the  long division " of @xmath87 by @xmath88 , the first step consists of subtracting @xmath92 from @xmath87 to cancel out the highest degree term in @xmath87 . if the remainder has degree at least @xmath90 , a different multiple of @xmath88 is subtracted to cancel out the highest degree term in the remainder , and so on . but , @xmath93 where ( [ eq : crossmult ] ) follows from ( [ eq : longdiv ] ) because @xmath94 for any nonzero scalar @xmath37 . thus , changing @xmath87 to @xmath95 instead of @xmath96 avoids a division while still zeroing out the highest degree term in @xmath87 and still having the same gcd . since the computation of @xmath97 in the eo algorithm is of exactly the same form as the computation of @xmath98 , a similar calculation can be used to update these polynomials as well . these two basic ideas have been used in different ways by many researchers to design different algorithms for gcd computation and rs decoding ( see , for example , @xcite ) . all these algorithms actually compute scalar multiples @xmath99 and @xmath100 of the error - locator and error - evaluator polynomials defined in ( [ eq : errorlocator ] ) and ( [ eq : errorevaluator ] ) respectively . our architectures also use the ideas of brent and kung , but compute @xmath101 and @xmath102 where @xmath103 . since the nonzero roots of @xmath104 are the same as those of @xmath52 and the factors @xmath105 cancel out in forney s formula ( [ eq : forney ] ) , such factors are inconsequential and can be ignored . as noted before @xcite , a polynomial division can be broken up into a sequence of partial divisions for ease of implementation , and the cross - multiplication technique can be used to avoid divisions of field elements @xcite . the same ideas can be adapted to eliminate the comparison of @xmath106 $ ] with @xmath1 as well . our modification of the eea solves the key equation in _ exactly _ @xmath0 steps ; rather than in _ at most _ @xmath0 steps as in previous work by others . when @xmath107 errors have occurred , our algorithm computes @xmath108 and @xmath109 in @xmath110 steps instead of @xmath22 and @xmath24 . our algorithm is also set up so that each of the additional @xmath111 steps simply multiplies the results by @xmath112 so that after a total of @xmath0 steps , our modification of the eea has computed @xmath113 and @xmath114 . these give the same error locations and error values as do @xmath22 and @xmath55 . the advantages to our approach are that the degree checking is avoided completely , and the key equation solution is produced with a fixed latency , both of which properties simplify the control mechanism in an implementation . we claim that the following modified version of the eea solves the key equation for rs decoding , producing polynomials @xmath115 and @xmath116 . * algorithm i ( modified euclidean algorithm ) *    1 .   * initialization : * @xmath117 , @xmath118 , @xmath119 , @xmath120 , and @xmath121 . * iteration : repeat * @xmath0 times : 1 .   * set * @xmath122 , @xmath123 , @xmath124 . if * @xmath125 and @xmath126 , + @xmath127 3 . * set * @xmath128 3 . * output : * @xmath129 , @xmath130 , and @xmath131 .    if @xmath107 errors have occurred , then after @xmath132 iterations of step  i.2 in algorithm  i , @xmath133 and @xmath134 where scalar factors are ignored . when step  i.2 is iterated @xmath111 more times , @xmath135 and @xmath88 are multiplied by @xmath112 ( step 1.2a ) and the ignorable scalar factor @xmath136 ( step i.2c ) each time . hence , when algorithm  i ends , @xmath137 , @xmath138 , and @xmath139 . if @xmath140 , then algorithm i terminates with @xmath141 . in practice , steps  i.2a - i.2c are not executed in succession but combined into a single calculation that computes a boolean control variable @xmath142 and then _ simultaneously _ sets @xmath143 note also that @xmath131 must be initialized to @xmath144 for this modified computation to work properly . we refer to this variation of algorithm  i as algorithm  i*. the following theorem summarizes the results of algorithms  i and i*. + _ theorem _ 1 : if @xmath107 errors have occurred , then when algorithm i or i * terminates , @xmath145 and @xmath146 where @xmath37 is nonzero . if algorithm i or i * terminates with @xmath147 , then more than @xmath1 errors have occurred and the error pattern @xmath14 is not correctable . in errors - and - erasures decoding ( see , for example , @xcite ) , the key equation ( [ eq : keyeq ] ) relating the errata - locator polynomial @xmath148 and the errata - evaluator polynomial @xmath55 is usually solved via the following three steps executed in succession :    1 .   using the known erasure locations @xmath149 , @xmath150 to compute the erasure - locator polynomial @xmath151 and the modified syndrome polynomial @xmath152 2 .   solving the modified key equation @xmath153 for the _ error_-locator polynomial @xmath154 and the _ errata_-evaluator polynomial @xmath55 3 . multiplying @xmath154 by @xmath151 to obtain the errata - locator polynomial @xmath52 . the computations of @xmath151 and @xmath155 can be implemented as @xmath39-iteration procedures in which initial values @xmath156 and @xmath157 are multiplied successively by @xmath158 , @xmath159 ,  , @xmath160 . alternatively , @xmath151 can be computed as described above and then the polynomial product @xmath161 computed in @xmath162 further iterations ( cf . @xcite ) . of course , if there are no erasures , then these calculations do not need to be carried out . next , the ( modified ) key equation is solved in _ at most _ @xmath163 iterations via a slightly modified version of the extended euclidean algorithm for errors - only decoding . a slightly modified version of the berlekamp - massey errors - only decoding algorithm also can be used for this purpose . finally , the last of the three steps above is not strictly necessary , but is usually implemented ( in fact , embedded into the second step ) because it is more convenient to use @xmath52 in computing errata values via forney s formula . it was pointed out by blahut @xcite that if the registers used to compute @xmath46 are initialized to @xmath151 instead of @xmath10 , then the iterations during the solution of the modified key equation produce @xmath148 directly and thus the third step above is in effect embedded into the key equation solution . blahut @xcite also noted that for the berlekamp - massey algorithm , it is unnecessary to compute the modified syndrome polynomial : if the registers used to compute @xmath46 are initialized to @xmath151 instead of @xmath10 , then the `` discrepancies '' calculated in the berlekamp - massey algorithm are exactly those needed for solving the modified key equation , and the algorithm produces @xmath22 directly instead of @xmath45 . unfortunately , reformulated berlekamp - massey algorithms such as the ribm and ribm algorithms of @xcite as well as _ all _ key equation solvers that are based on the extended euclidean algorithm _ do _ need @xmath155 . however , these algorithms are able to embed the third step above into the key equation solution . finally , it has been noted by several researchers that the operations used for the solution of the key equation can be adapted to the computation of @xmath151 or @xmath155 or both . thus , the same hardware can be used in these calculations , which reduces the number of finite - field multipliers required . as pointed out in @xcite , the modified key equation @xmath164 can be solved by using the extended euclidean algorithm shown below :    * eea for errors - and - erasures decoding *    1 .   * initialization : set * @xmath60 , @xmath165 , @xmath62 , @xmath63 , and @xmath166 . * iteration : while * @xmath86 \geq t+\mu /2 $ ] , + @xmath66 by @xmath67 to obtain both + @xmath68 and the + @xmath69 . + @xmath70 . + @xmath71 . * output : * @xmath167 , @xmath73 . this algorithm is clearly similar to the eo algorithm for errors - only decoding . in fact , the only differences between the two algorithms are the initial values of @xmath168 and the stopping condition . hence , direct implementation based on the above algorithm suffers the same problems we described in section iii.a . using the same reformulation steps as in section iii , the above algorithm can be modified to a @xmath169-iteration algorithm that eliminates the degree checking and produces @xmath170 and @xmath171 instead of @xmath46 and @xmath24 respectively .    as mentioned above , the operations used to compute @xmath172 in the third step can be embedded in the modified euclidean algorithm by initializing @xmath173 and @xmath174 to scaled values @xmath175 and @xmath176 respectively . note that the updates of @xmath177 depend on @xmath84 , which are not at all affected by the change in the initial values . thus , each @xmath177 is scaled by @xmath151 , leading to a final output @xmath178 .    in order to combine the computation of @xmath151 and @xmath155 with the modified euclidean algorithm ( with the computation of @xmath52 embedded ) into a single algorithm with @xmath0 iterations , we use a polynomial @xmath179 that can be formed easily during the syndrome computation stage by saving the marked erasure locations . we allow for the possibility that more than @xmath0 erasures have occurred , even though such an errata pattern is not decodable . our reformulated eea for errors - and - erasures decoding is as follows :    * algorithm ii *    1 . * initialization : * @xmath180 , @xmath118 , @xmath119 , @xmath121 , @xmath120 , and @xmath181 . * iteration : repeat * @xmath0 times : + @xmath182 . + @xmath183 . + @xmath184 + @xmath185 @xmath186 3 . * output : * @xmath187 , @xmath188 , @xmath131 , and @xmath189 . this algorithm uses a boolean control variable first that has value 1 only when the erasure locations are being processed to compute @xmath151 and @xmath155 . during this time , swap is always @xmath9 and @xmath190 is set to the erasure location being processed currently . for each erasure location @xmath190 , algorithm ii sets @xmath88 to @xmath191 $ ] and @xmath135 to @xmath192 $ ] , thus obtaining @xmath155 and @xmath151 after all the @xmath39 erasure locations have been processed one by one . note that the update @xmath193 discards the erasure location that was just processed and replaces it by the next erasure location to be processed , and thus first becomes zero after @xmath39 iterations . from this point onwards , the updates of all the polynomials and of @xmath131 are the same as in algorithm i * , and thus solve the modified key equation in @xmath163 iterations . we remark that the received words with no erasures can be decoded correctly by algorithm ii as well . in fact , algorithm i * corresponds to the special case of algorithm ii where @xmath194 and first is always @xmath9 . similar to theorem 1 , we have + _ theorem _ 2 : suppose that @xmath18 errors and @xmath39 erasures have occurred where @xmath195 . let @xmath53 denote the total number of errata . then when algorithm ii terminates , @xmath126 and + @xmath196 where @xmath37 is nonzero . if algorithm ii terminates with @xmath147 or with @xmath197 , then the errata pattern is not correctable . in this paper , modified euclidean algorithms that use _ fixed _ numbers of iterations are proposed for both errors - only and errors - and - erasures decoding of rs codes . the salient feature of fixed numbers of iterations leads to simpler control mechanisms and hence hardware savings . the new algorithm for errors - and - erasures decoding seamlessly combines the three steps typically used in previously proposed architectures into one procedure , leading to hardware savings . j.  h. baek , j.  y.  kang and m.  h.  sunwoo , `` design of a high - speed reed - solomon decoder , '' _ proceedings of the 2002 ieee international symposium on circuits and systems , iscas 2002 , _ may  2002 , vol .  5 , pp .  793796 . e.  berlekamp , g.  seroussi , and p.  tong , `` a hypersystolic reed - solomon decoder , '' in _ reed - solomon codes and their applications _ , s.  b. wicker and v.  k. bhargava , eds . , chapter  10 . ieee press , piscataway nj , 1994 . a.  e.  heydtmann and j.  m.  jensen , `` on the equivalence of the berlekamp - massey and the euclidean algorithms for decoding , '' _ ieee transactions on information theory _ 46 , pp .  26142624 , november 2000 . huang and c.w . wu , `` vlsi design of a high speed pipelined reed - solomon codec , '' _ proceedings of the international symposium on multi - technology information processing ( ismip ) , _ hsinchu , december  1996 , pp . 517522 . s. kwon and h. shin , `` an area - efficient vlsi architecture of a reed - solomon decoder / encoder for digital vcrs , '' _ ieee transactions on consumer electronics _ , vol . 43 , no .  4 pp . 10191027 , november 1997 . t.  k. truong , w.  l. eastman , i.  s. reed , and i.  s. hsu , `` simplified procedure for correcting both errors and erasures of reed - solomon code using euclidean algorithm , '' in _ proc . iee , part e _ , november 1988 , vol .
the extended euclidean algorithm ( eea ) for polynomial greatest common divisors is commonly used in solving the key equation in the decoding of reed - solomon ( rs ) codes , and more generally in bch decoding . for this particular application , 
 the iterations in the eea are stopped when the degree of the remainder polynomial falls below a threshold . 
 while determining the degree of a polynomial is a simple task for human beings , hardware implementation of this stopping rule is more complicated . 
 this paper describes a modified version of the eea that is specifically adapted to the rs decoding problem . 
 this modified algorithm requires no degree computation or comparison to a threshold , and it uses a fixed number of iterations . 
 another advantage of this modified version is in its application to the errors - and - erasures decoding problem for rs codes where significant hardware savings can be achieved via seamless computation .