Decoding apparatus, processing apparatus and methods therefor

Details Decoding apparatus, processing apparatus and methods therefor Decoding apparatus, processing apparatus and methods therefor

1999-06-30

2002-07-16

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06421807

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to a decoding apparatus and method for decoding data encoded in a linear cyclic code.
BACKGROUND OF THE INVENTION
The Peterson method, Berlekamp-Massey method and Euclidean method are known generally as methods of obtaining an error position polynomial indicating a position of a symbol within a received word polynomial where an error occurs and an error evaluator polynomial indicating the value of the error of the symbol in decoding a linear cyclic code,
“A Method for Solving Key Equation for Decoding Goppa Codes, Y. Sugiyama, M. Kasahara, S. Hirasawa and N. Namekawa, Inform. and Contr., Vol. 27, pp 87-99, January 1975” (reference 1) discloses a Euclidean method.
“An erasures-Errors Decoding Algorithm for Goppa Codes (Y. Sugiyama, M. Kasahara and N. Namekawa, IEEE Trans., Inform. Theory, March 1976” (reference 2) discloses that the Euclidean method can be applied to error erasure and correction processing by calculating an updated syndrome, i.e., by multiplying a syndrome polynomial with an erasure locator polynomial and erasing the (d−1) th degree term where “d” is the minimum Hamming distance of the code (“d” is an odd number unless specifically mentioned).
The Euclidean method involves a computation load which is equal to or less than other methods. In addition, the Euclidean method is conveniently implemented in a hardware because computation is easily paralleled.
For example, Japanese PUPA 62-122332 discloses an apparatus in which the Euclidean method is implemented in a hardware. The apparatus disclosed in this reference (3) is so configured as to successively calculate an updated syndrome and a GCD (greatest common divisor) of two polynomials, and processes error erasure by using a systolic array technology.
In the apparatus disclosed in the reference 3, it is necessary for each calculating cell to be provided with a latch for holding information/status and multiplier/adder for calculation.
Japanese PUPA 7-202718 (reference 4), for example, discloses a decoding apparatus which comprises a less amount of hardware than the apparatus disclosed in the reference 2 by using a polynomial arithmetic processing circuit rather than a systolic array.
SUMMARY OF THE INVENTION
This invention provides a decoding apparatus and a method which allows data encoded in a linear cyclic code to be decoded with less hardware than the prior art decoding apparatus.
It is a further object of this invention to provide a decoding apparatus, an arithmetic apparatus and a method therefor which allows a linear cyclic code to be decoded in a speed equal to or higher than the prior art decoding apparatus with less hardware than the prior art decoding apparatus.
In order to achieve the above objectives, the decoding apparatus of this invention comprises erasure locator data calculating means for calculating erasure locator data &agr;
i
indicating the locator of erasure occurring 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), and decoding means for calculating an error/erasure value e
i
/E
i
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 repeating recursive formulas;
&sgr;
i
(
x
)=&sgr;
i−2
(
x
)+
Q
i
(
x
)·&sgr;
i−1
(
x
)
&ohgr;
i
(
x
)=&ohgr;
i−2
(
x
)+
Q
i
(
x
)·&ohgr;
i−1
(
x
)
where Q
i
(x) is a quotient of &ohgr;
i−2
(x)/&ohgr;
i−1
(x), &sgr;
−i
(x)=1, &ohgr;
−i
(x)=x
2t
, &sgr;
o
(x)=1, &ohgr;
o
(x)=M(x),
until the degree of the polynomial &ohgr;
i
becomes equal to or less than [(d+h−1)/2−1] (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
.
The decoding apparatus of this invention solves
S
(
x
)·&sgr;(
x
)·&lgr;(
x
)=&ohgr;(
x
) mod (
x
)  (expression 12)
using the Euclidean method to derive the error evaluator polynomial &ohgr;(x) and the error position polynomial &sgr;(x) for decoding a linear cyclic code such as BHC code. Rewriting the expression 12 by using the updated syndrome polynomial M(x)=S(x)·(x) mod x
d−1
, &phgr;(x)·x
d−1
±M(x)·&sgr;(x)=&ohgr;(x) (expression 14) is obtained. The error position polynomial &sgr;(x) and the error evaluator polynomial &ohgr;(x) can be uniquely obtained from this expression 14 except for the difference of a multiple of constant.
The polynomial calculating means of the decoding apparatus of this invention uses the expression;
&lgr;
i
(
x
)
x
2t
+&sgr;
i
(
x
)·
M
(
x
)=&ohgr;
i
(
x
)
(expression 16) Initial condition
&lgr;
−1
(x)=1, &sgr;
−1
(x)=0, &ohgr;
−1
(x)=X
2t
, &lgr;
0
(x)=1,
&sgr;
0
(x)=0, &ohgr;
0
(x)=M(x))
for solving the expression 14 using the Euclidean method.
The expression 16 can be expressed in the form of a recursive formula given below and the polynomial calculating means derives the error position polynomial &sgr;(x) and the error evaluator polynomial &ohgr;(x) by repeating the following recursive formula until the condition deg &ohgr;(x)≦[(d+h−1)/2]−1 is satisfied:
&sgr;
i
(
x
)=&sgr;
i−2
(
x
)+
Q
i
(
x
)·&sgr;
i−1
(
x
)
 &ohgr;
i
(
x
)=&ohgr;
i−2
(
x
)+
Q
i
(
x
)·&ohgr;
1−1
(
x
)
where Q
i
(x) is quotient of &ohgr;
i−2
(x)/&ohgr;
i−1
(x),
The erasure locator polynomial &lgr;(x) is further calculated from the erasure locator data &agr;
i
as shown in the expression 8.
The decoding means obtains an error value e
i
and an erasure value E
i
to correct a received word by substituting the expressions
e
i
=&ohgr;(&agr;
−ji
)/{&agr;
−ji
·&agr;′(&agr;
−ji
)·&lgr;(&agr;
−ji
)},  (23)
E
i
=&ohgr;(&agr;
−j′i
)/{&agr;
−j′i
·&agr;′(&agr;
−j′i
)·&lgr;(&agr;
−j′i
)}  (24)
with the erasure locator polynomial &lgr;(x), the error position polynomial &sgr;(x) and the error evaluator polynomial &ohgr;(x) so obtained for correcting the received word to decode it.
The arithmetic apparatus of this invention calculates the error position polynomial &sgr;(x) and the error evaluator polynomial &ohgr;(x) from the updated syndrome polynomial M(x) which is calculated from the erasure locator data &agr;
i
indicating the locator of an erasure in the linear cyclic code R(x) and the syndrome polynomial S(x) which is calculated from said erasure locator data &agr;
i
and said linear cyclic code R(x). Said arithmetic apparatus repeats recursive formulas;
&sgr;
i
(
x
)=&sgr;
i−2
(
x
)+
Q
i
(
x
)·&sgr;
i−1
(
x
)
&ohgr;
i
(
x
)=&ohgr;
i−2
(
x
)+
Q
i
(
x
)·&ohgr;
i−1
(
x
)
where Q
i
(x) is a quotient of &ohgr;
1−2
(x)/&ohgr;
i−1
(x), &sgr;
−i
(x)=1, &ohgr;
−i
(x)=x
2t
, &sgr;
0
(x)=1, &ohgr;
0
(x)=M(x),
until the degree of

Affiliated with

Also associated with

Rating

Decoding apparatus, processing apparatus and methods therefor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Decoding apparatus, processing apparatus and methods therefor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding apparatus, processing apparatus and methods therefor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2879673