Patent ID: 6421807
Filing Date: 2002-07-16
Classification: H03M

Abstract:
A decoding apparatus comprising:erasure locator data calculating means for calculating erasure locator data &agr;i indicating the locator of erasure occurring in data encoded in a linear cyclic code R(x), syndrome polynomial calculating means for calculating a syndrome polynomial S(x) based on said calculated erasure locator data &agr;i and said linear cyclic code R(x), updated syndrome polynomial calculating means for calculating an updated syndrome polynomial M(x) based on said erasure locator data &agr;i and said calculated syndrome polynomial S(x), polynomial calculating means for calculating an error position polynomial &sgr;(x), an erasure locator polynomial &lgr;(x) and an error evaluator polynomial &ohgr;(x), based on said erasure locator data &agr;i and said calculated updated syndrome polynomial M(x), decoding means for calculating an error/erasure value ei/Ei to correct the error/erasure in said linear cyclic code R(x) for decoding based on said calculated error position polynomial &sgr;(x) said calculated erasure locator polynomial &lgr;(x), said calculated error evaluator polynomial &ohgr;(x), said error position data &agr;i, and said linear cyclic code R(x), said polynomial calculating means performing according to recursive formulas: &sgr;i(x)=&sgr;iâˆ’2(x)+Qi(x)Â·&sgr;iâˆ’1(x) &ohgr;i(x)=&ohgr;iâˆ’2(x)+Qi(x)Â·&ohgr;iâˆ’1(x) where Qi(x) is a quotient of &ohgr;iâˆ’2(x)/(&ohgr;iâˆ’1(x), &sgr;âˆ’1(x)=1, &ohgr;âˆ’i(x)=x2t, &sgr;0(x)=1, &ohgr;0(x)=M(x),until the degree of the polynomial &ohgr;i becomes equal to or less than (where [ ] is a Gauss symbol, d is a minimum Hamming distance and h is the number of erasures) to calculate the error position polynomial &sgr;(x) and the error evaluator polynomial &ohgr;(x) for deriving the erasure locator polynomial &lgr;(x) from said erasure locator data &agr;i, two first registers (registers U, X) having a data width equal to or greater than kÂ·(dâˆ’1)/2 bits (where k is a data length of a symbol included in said linear cyclic code), two second registers (registers Y, Z) having a data width equal to or greater than kÂ·(dâˆ’1)/2 bits: (where k is the data length of a symbol included in said linear cyclic code), multiplier/divider means for multiplying/dividing two multiplication/division data items, a data selector for selecting two of polynomials held by said registers, said erasure locator data &agr;i and the result of said multiplication/division to generate said two multiplication/division data items, a first adder means for adding said result of multiplication/division to data held in one of said first registers, a second adder means for adding said result of multiplication/division to the data held in one of said first registers, a shifter for shifting said result of multiplication/division, and arithmetic control means for causing these means to execute arithmetic processing to solve said recursive formulas.