Error decoding method and apparatus for Reed-Solomon codes

A method and an apparatus for performing error decoding on digital data using a Reed-Solomon code. The method decodes the value and location of errors and erasures on digital data defined as RS.sub.m (n,n-4) of the Reed-Solomon code by a series of arithmetic operations using multiplication-addition, inversion, shift-logarithm operations, and location determinations, but without power operation. Thus, the decoder requires less hardware. By these calculations the values and locations of errors and erasures on digital data are determined correctly and rapidly, avoiding Chien's search.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The invention relates generally to a method and an apparatus for performing 
error decoding of digital data using Reed-Solomon codes. More 
particularly, the invention relates to a method and an apparatus for 
decoding the value and location of error words in digital data using 
Reed-Solomon codes by a series of product sum arithmetic operations, 
without a calculation of power. 
2. Technical Background 
Reed-Solomon (hereinbelow, abbreviated as RS) codes are very important in 
communication for the preservation of data, operating to continuously 
correct errors in bytes of digital data. 
There are generally two different circuit types in the design of RS code 
decoders. One is the pipe-line type and the other is the processor-based 
program control type. Pipe-line type RS code decoders are typically used 
in systems that must work at high-speed and in real-time. Correspondingly, 
the circuitry for the pipe-line type RS code decoder is complex and 
expensive which is wasteful of resources and money in a system demanding 
only moderate speed. The RS code decoder of the processor-based program 
control type performs repeated calculations using an arithmetic logic unit 
(ALU), under the program control, which reduces the complexity and cost of 
the circuit of the RS code decoder. There are apparent differences between 
the pipe-line type and the processor-based program control type RS code 
decoders. 
For RS codes, the calculations for decoding, when there are more than two 
errors among the transmitted words, are too complex to appropriately use 
the processor-based program control type of RS code decoder. However, the 
conventional system of this type for decoding two error words is used and 
is illustrated hereinafter: 
An RS code can be defined as RS.sub.m (n, k). The input terminal of the RS 
code decoder receives n symbols, with each symbol consisting of m bits. 
After error correction, k data symbols are transmitted from the decoder. 
RS.sub.m (n,k) can be defined as: 
##EQU1## 
Therefore, in an RS code decoder which can detect two error words, t=2, 
d=2t+1=5, k=n+1-5=n-4, and RS.sub.m (n,k) can be modified as RS.sub.m 
(n,n-4). For RS.sub.m (n,n-4) codes, the generating polynomial can be 
represented as: 
EQU g(x)=(x-1)(X-.alpha.)(X-.alpha..sup.2) (X-.alpha..sup.3) 
It may be assumed that in the n symbols there are v error words which are 
located at l.sub.1, l.sub.2, l.sub.3, l.sub.4, . . . , l.sub.v and whose 
values are respectively Y.sub.1, Y.sub.2, Y.sub.3, Y.sub.4, . . . , 
Y.sub.v. In order to explain the principle of decoding the RS codes 
hereinafter, if the location l.sub.i is known before the n symbols are 
decoded, the error word is defined as an `erasure`, and if the location 
l.sub.i is unknown before the n symbols are decoded, the error word is 
defined as an `error`. 
With RS codes having a Hamming distance (d=5), p error words and q erasure 
words can be detected if p and q satisfy the following formula: 
EQU 2p+q .ltoreq.d-1=5-1=4 (1) 
And if X.sub.i =.alpha..sup.li 1.ltoreq.i.ltoreq.v, 
then the syndromes are: 
##EQU2## 
that is, the syndromes S.sub.0, S.sub.1, S.sub.2, S.sub.3 can be obtained 
with the respective combinations of X.sub.j and Y.sub.j where: 
v: the number of erasure words and error words, v=p+q, 
p: the number of error words, 
q: the number of erasure words, 
X.sub.j,: X.sub.j =.alpha..sup.lj and l.sub.j is the location of the jth 
error 
S.sub.k : syndrome, 
Y.sub.j : jth error value, and 
d: Hamming distance of the code. 
According to several U.S. Pat. Nos., for example, Ozaki (4,852,099) and 
Okamoto et al. (4,677,622), we know the following: 
If p=0 and q=4, then: 
##EQU3## 
When the number of erasure words q is from one to three, the number of 
error words p that can be accommodated becomes zero or one in accordance 
with Equation (1). To determine whether the actual value of p is zero, or 
one, or larger than one (in the situation that p is larger than one, the 
decoder cannot detect any error word from n symbols), reference must be 
made to a set of Forney Syndromes. If q is equal to one, then the Forney 
Syndromes are defined as: 
EQU T.sub.1 =S.sub.1 +S.sub.0 X.sub.1 
EQU T.sub.2 =S.sub.2 +S.sub.1 X.sub.2 ( 7) 
EQU T.sub.3 =S.sub.3 +S.sub.2 X.sub.3 
If q is equal to two, then the Forney Syndromes are defined as: 
EQU T.sub.1 =S.sub.2 +(X.sub.1 +X.sub.2) S.sub.1 +X.sub.1 X.sub.2 S.sub.0( 8) 
EQU T.sub.2 =S.sub.3 +(X.sub.1 +X.sub.2) S.sub.2 +X.sub.1 X.sub.2 S.sub.1 
If q is equal to three, then the Forney Syndromes are defined as: 
EQU T.sub.1 =S.sub.3 +(X.sub.1 +X.sub.2 +X.sub.3) S.sub.2 +(X.sub.1 X.sub.2 
+X.sub.2 X.sub.3 +X.sub.3 X.sub.1) S.sub.1 +X.sub.1 X.sub.2 X.sub.3 
S.sub.0( 9) 
In the condition that q is equal to one or two, the value of p can be 
determined according to the rules below: 
(1) If the Forney Syndromes are all equal to zero, the value of p is zero. 
(2) If the Forney Syndromes are all not equal to zero, the value of p is 
one. 
(3) If at least one of the Forney Syndromes is equal to zero and at least 
one of the Forney Syndromes is not equal to zero, the decoder cannot 
correct any error word from n symbols. 
Further, when q is equal to three, if the Forney Syndrome is equal to zero, 
then the decoder can correct error words from n symbols. When q is equal 
to three, and if the Forney Syndrome is not equal to zero, then the 
decoder cannot correct errors from n symbols. 
When p is equal to one, the locations of unknown error words can be 
determined with the equations below: 
##EQU4## 
From the above Equations (3) to (11), the value of p can be determined only 
when the value of q is not equal to zero. In the situation that q is equal 
to zero, the value of p is determined by evaluating the following 
quantities: 
EQU S.sub.A =S.sub.1 S.sub.1 +S.sub.0 S.sub.2 
EQU S.sub.B =S.sub.2 S.sub.2 +S.sub.1 S.sub.3 ( 12) 
EQU S.sub.C =S.sub.0 S.sub.3 +S.sub.1 S.sub.2 
(1) If the three quantities are all equal to zero, then p is equal to one. 
(2) If three quantities are all not equal to zero, then p is equal to two. 
(3) If one or more of the quantities are equal to zero, and one or more of 
the quantities are not equal to zero, the decoder cannot correct the 
errors in n symbols. In situation (1), that is q=0 and p=1: 
##EQU5## 
In situation (2), that is q=0 and p=2: 
##EQU6## 
From Equation (3) to Equation (13), X.sub.i and Y.sub.i can be determined 
by three types of calculations, such as adding, multiplying and inverting, 
except in the case of (p,q)=(2,0). (When q is not equal to zero, under the 
condition that i .ltoreq.q, X.sub.i can be obtained while the n symbols 
are being imported, and the values of Y.sub.i and l.sub.i can be obtained 
with the additional calculation of a logarithm.) 
Under the condition that p=2 and q=0, there are several ways to solve for 
the values of X.sub.1 and X.sub.2 with Equation (14) and Equation (15). 
For example, the conventional method is to perform a "Chien's Search". In 
the method using a Chien's Search, at first, X.sub.1 is set to a 
predetermined value, and the value of X.sub.1 +X.sub.2 is set as SUM. 
Thus, X.sub.2 =SUM-X.sub.1 is obtained from Equation (14). Thereafter, 
X.sub.1 and X.sub.2 are substituted in Equation (15). If the value of the 
left side of the equation is not equal to the value of the right side, 
X.sub.1 is set to another predetermined value, referring to the former 
value. By repeatedly setting the value of X.sub.1, the value of X.sub.2 
can be obtained. But the speed of decoding is very slow for several 
repetitions of the calculation in which different values of X.sub.1 and 
X.sub.2 are substituted in the processor-based program control decoder. 
The method therefore has a negative influence on the whole system, and is 
not practicable for calculating the actual values of X.sub.1 and X.sub.2. 
SUMMARY OF THE INVENTION 
It is therefore an object of the invention to provide a method for 
performing error decoding of digital data using a Reed-Solomon code, that 
is useful to correctly and rapidly decode the values and locations of two 
errors in digital data defined as RS.sub.m (n,n-4) of the Reed-Solomon 
code, by a series of product sum arithmetic operations, using addition, 
multiplication, division, shift-logarithm, and location. 
It is another object of the invention to provide an apparatus for 
performing such a method of decoding. 
This is accomplished in accordance with the invention by providing an error 
decoding method for decoding syndrome signals using Reed-Solomon codes, 
the Reed-Solomon codes being defined as RS.sub.m (n,k), wherein m is a 
number of bits of each syndrome, n is a length of Reed-Solomon codes, and 
k is a length of information words in the Reed-Solomon codes, wherein the 
Reed-Solomon codes comprise p error words and q erasure words, 
n.ltoreq.(2.sup.m -1) and 2p+q.ltoreq.d-1, and wherein d is the Hamming 
distance. The error decoding method includes decoding the error words and 
the erasure words existing in every syndrome signal and determining the 
numbers p and q. 
Two equations X.sub.1.sup.2 =.alpha..sup.2l.sbsp.1 and X.sub.2.sup.2 
=.alpha..sup.2l.sbsp.2 are evaluated for a calculation of location when 
there are two error words and no erasure words in every syndrome signal, 
wherein the syndrome signals having two errors are defined as: 
##EQU7## 
wherein X.sub.1 =.alpha..sup.1.sbsp.1, X.sub.2 =.alpha..sup.1.sbsp.2, 
l.sub.1 and l.sub.2 define the locations of two error words, and Y.sub.1 
and Y.sub.2 are values of the two error words: 
l.sub.1 and l.sub.2 are evaluated by a calculation of the logarithm of 
.alpha..sup.2l.sbsp.1 and .alpha..sup.2l.sbsp.2 and a calculation of 
shifting; and 
Y.sub.1 and Y.sub.2 are obtained by a series of product/sum arithmetic 
calculations according to X.sub.1.sup.2 =.alpha..sup.2l.sbsp.1, X.sub.2 
=.alpha..sup.2l.sbsp.2. 
In the above-mentioned error decoding method, when there are no erasure 
words in syndrome signals, the number p of error words can be determined 
by the three quantities S.sub.1 S.sub.1 +S.sub.0 S.sub.2, S.sub.2 S.sub.2 
+S.sub.1 S.sub.3 and S.sub.0 S.sub.3 +S.sub.1 S.sub.2. When none of the 
three quantities are equal to 0, then p is equal to 1. When all three 
quantities are equal to 0, then p is equal to 1. When at least one of the 
three quantities is equal to 0 and at least one of the three quantities 
are not equal to 0, then p is not determinable. 
Furthermore, in the above-mentioned error decoding method, the calculation 
of location is performed by evaluating the following equation: 
EQU .alpha..sup.i +.alpha..sup.-i .fwdarw..alpha..sup.i 
EQU 1.ltoreq.i.ltoreq.2.sup.m -1 
When there are two error words and no erasure words in every syndrome 
signal, then: 
##EQU8## 
Therefore, locations l.sub.1 and l.sub.2 of the error words can be 
determined by calculation of location according to the following equations 
: 
EQU X.sub.1.sup.2 =.alpha..sup.2l.sbsp.1 
EQU X.sub.2.sup.2 =.alpha..sup.2l.sbsp.2 
and l.sub.1 and l.sub.2 determined as follows: 
##EQU9## 
Furthermore, the error decoding method according to the invention can be 
executed by providing an apparatus for decoding error words and erasure 
words existing in transmitted word signals, using Reed-Solomon codes 
provided from an external system. Such an apparatus would include a 
syndrome generator, to be coupled to the external system, for receiving 
the transmitted word signals therefrom and generating syndrome signals. 
An erasure counter is to be coupled to the external system, for receiving 
the erasure words. An erasure counting value stored in the erasure counter 
is incremented by one each time that an erasure word is detected. 
Registers are coupled to the syndrome generator, and to be coupled to the 
external system, for receiving the syndrome signals and the erasure words, 
and for storing the syndrome signals and the erasure words at 
predetermined locations. An arithmetic logic circuit (ALU) is coupled to 
the registers for reading the syndrome signals and the erasure words 
stored in the registers, and performing a predetermined operation in order 
to provide a feedback signal to the registers, and generate a deductive 
signal. 
A comparator is coupled to the arithmetic logic circuit for receiving the 
deductive signal, performing a comparing operation, and then outputting a 
comparison signal. A program controller is coupled to the comparator and 
the erasure counter, for receiving the comparison signal from the 
comparator, reading the erasure counting value stored in the erasure 
counter, and outputting a program control signal. A program counter is 
coupled to the program controller for receiving the program control 
signal, in response to which it generates a program counting signal, and 
also outputs a feedback signal to the program controller. In response to 
receipt of the feedback signal, the program controller changes the program 
control signal. 
An interpreter is coupled to the program counter to receive the program 
counting signal, and in response outputs a register address signal and an 
ALU enable signal. The arithmetic logic circuit (ALU) reads the syndrome 
signals and also reads the erasure words stored in the registers, 
according to the register address signal, in order to decode the error 
words in the transmitted word signals. 
Moreover, the arithmetic logic circuit includes an inverter, a 
multiplier-adder circuit, a shift-logarithm circuit for performing shift 
and logarithm calculations and a locator for performing a location 
calculation. The inverter performs an inverting calculation on the 
syndrome signals and the multiplier-adder circuit performs an add 
calculation and a multiplication calculation on the syndrome signals. The 
shift-logarithm circuit performs a logarithmic calculation of the syndrome 
signals, and a shift calculation on the result of the logarithmic 
calculation, according to the ALU enable signal. The locator performs a 
calculation of location. 
The method is executed selectively in the arithmetic logic circuit by 
operating the inverter the multiplier-adder circuit, the shift-logarithm 
circuit, and the locator, in order to generate the feedback signal and the 
deductive signal.

DETAILED DESCRIPTION OF THE INVENTION 
Referring to FIG. 1, a decoding apparatus 200 according to the preferred 
embodiment of the invention comprises syndrome generator 210, registers 
220, an arithmetic logic circuit 230, an interpreter 240, a comparator 
250, a program counter 260, a program controller 270, and an erasure 
counter 280. The arithmetic logic circuit 230 includes an inverter 232, a 
multiplier-adder circuit 234, a shift-logarithm circuit 236, and a locator 
circuit 238. 
When an external system 100 begins to transmit signals, transmitted word 
signals are transmitted to the syndrome generator 210 through a line 10, 
and erasure word signals are transmitted to the registers 220 and the 
erasure counter 280 through a line 32. The syndrome generator 210 
generates syndrome signals from the transmitted word signals according to 
the format of RS codes. Syndrome signals are output to the registers 220 
through a line 12. The registers 220 temporarily store every syndrome 
signal and erasure word signal in corresponding addresses in predetermined 
registers therein. Each time that the erasure counter 280 receives an 
erasure word signal via the line 32, an erasure counting value stored in 
the erasure counter 280 is incremented by one in order to count the sum of 
all erasure word signals. The erasure counting value is transmitted to the 
program controller 270 through a line 34. 
When the apparatus 200 is enabled, the arithmetic logic circuit 230 
receives syndrome signals and erasure word signals, which are stored in 
the registers 220, through the respective line 13, line 14, and line 15. 
After a series of selective calculations in the arithmetic logic circuit 
230, a feedback signal is output to the registers 220 on line 16 where it 
is stored at a predetermined location. At the same time a deductive signal 
is output to the comparator 250 for a comparison calculation. Thereafter, 
a comparison signal is output to a program controller 270 on line 22. 
Based on the output of the comparator 250, the erasure counting value from 
the erasure counter 280, and the program counting value stored in program 
counter 260, the program controller 270 determines whether the program 
address should jump or not, and if it should, to which address it should 
jump. Based on the determination, a program control signal is output from 
the program controller 270 to the program counter 260 through a line 28. A 
program counting signal is outputted to the interpreter 240 through a line 
24 when the program counter 260 receives the program control signal. At 
the same time, the program counter 260 changes the program counting value, 
and then outputs the modified value as feedback to the program controller 
270 on line 26 in order serve as a reference for the shifting of the 
program controller 270. 
The interpreter 240 outputs register address signals on line 20 and an 
enable signal on line 30 respectively to the registers 220 and the 
arithmetic logic circuit 230 while receiving the program counting signal 
from the program counter 260. The arithmetic logic circuit 230 reads the 
values stored in correspondence with the register address signal, while 
receiving the enable signal. By the deductive function performed in the 
arithmetic logic circuit 230, the value and location of error words 
existing in transmitted word signals can be determined. 
For the purpose of performing the deductive function, the arithmetic logic 
circuit 230 comprises the inverter 232, the multiplier-adder circuit 234, 
the shift-logarithm circuit 236 and the locator 238. The inverter 232 
performs an inverting calculation on the ALU input value. The 
multiplier-adder circuit 234 performs an addition and multiplication 
calculation on the ALU input values. The shift-logarithm circuit 236 
performs a logarithmic calculation on the ALU input values, and performs a 
shift calculation on the ALU input values based on the result of logarithm 
calculation, according to the enable signal. The locator 238, performs a 
calculation of location. 
Referring to FIG. 2, the shift-logarithm circuit 236 includes a logarithm 
calculator 410 and a multiplexer 420. When calculating data, for example, 
ALU input value is transmitted to the logarithm calculator 410 through a 
line 402, and shifted syndrome signals and unshifted syndrome signals are 
respectively output therefrom to the multiplexer 420 as, for example, 
b.sub.0, b.sub.2.spsb.m.sub.-1, b.sub.2.spsb.m.sub.-2, . . . ,b.sub.1 and 
b.sub.2.spsb.m.sub.-1, b.sub.2.spsb.m.sub.-2, . . . ,b.sub.0 through lines 
412 and 414. When the multiplexer 420 receives these signals and is 
enabled by the enable signal (shift) through line 422, the multiplexer 420 
outputs the calculation result through line 424. 
The shift-logarithm performed in the shift-logarithm circuit 236, is 
specified below: 
##EQU10## 
The calculating method of location is: 
EQU .alpha..sup.i +.alpha..sup.-i .fwdarw..alpha..sup.i 
EQU 1.ltoreq.i.ltoreq.2.sup.m-1 (17) 
When word signals are transmitted, the apparatus 200 for decoding error 
words and erasure words performs some initial actions. That means, at 
first, the values stored in two of the registers 220 are respectively set 
as .alpha..sup.n and .alpha..sup.-1, and these two registers are defined 
as r.sub.1 and r.sub.2. Therefore, the value of register r.sub.1 is 
.alpha..sup.n and the value of register r.sub.2 is .alpha..sup.-1. When 
the first transmitted word signal is transmitted to the apparatus 200, the 
value of register r.sub.1 is multiplied by .alpha..sup.-1, and then the 
value of register r.sub.1 is replaced with r.sub.1 .times..alpha..sup.-1. 
That means that if the syndrome signal is the Lth signal in transmitted 
data, the value of register r.sub.1 is set to .alpha..sup.n 
.times..alpha..sup.-L. Whenever the erasure word signal is not logic "0", 
the value of r.sub.1 is saved in some proper register of the registers 
220. Then the definition X.sub.i =.alpha..sup.li. can be executed without 
the calculation of multi-powers, i.e., powers higher than 2. This 
procedure can reduce the complexity of the circuit. 
Previously, an RS decoder was able to correct two errors with a 
processor-based program control structure, as noted above. However, a 
processor-based program control structure is not practical because the 
calculating formulas become very complex when an RS decoder must solve 
more than two errors. Therefore, a decoder which can correct two errors 
existing in RS codes accords with the real demands. 
Errors and erasures can be corrected by the above Equations (3) to (10) 
when (p,q)=(0,1), (0,2), (0,3), (0,4), (1,1), or (1,2), but not for the 
situation p=2 and q=0. The errors also can be determined by Equation (13) 
when (p,q)=(1,0). The value of (X.sub.i,Y.sub.i) can be determined by 
calculations above-mentioned of addition, subtraction and inversion and 
the value of location l.sub.i, of Y.sub.i can also be determined. 
The Equations (14) and (15) can also be solved when p=2 and q=0: 
##EQU11## 
According to conventional calculating methods, for example, a Chien Search 
is conducted, in which the calculating formulas are very complex and time 
consuming. The invention can decode the errors with the new calculating 
methods of location and shift-logarithm. Equation (14) divided by Equation 
(15) provides an Equation (17) as follows: 
##EQU12## 
The calculating method of location is: 
EQU .alpha..sup.i +.alpha..sup.-i .fwdarw..alpha..sup.i 
EQU 1.ltoreq.i.ltoreq.2.sup.m-1 (19) 
The following equation is obtained by the method of location: 
EQU .alpha..sup.l.sbsp.1.sup.-l.sbsp.2 =X.sub.i /X.sub.2 
EQU 1.ltoreq.(1.sub.1 -1.sub.2)mod(2.sup.m -1).ltoreq.2.sup.m- 1(19) 
Multiplying Equation (15) by Equation (19) provides the following equation: 
##EQU13## 
In the same way as by the shift-logarithm calculation of Equation (16), the 
value of 1.sub.2 is obtained. 
With this method the values of X.sub.1.sup.2 and X.sub.2.sup.2 are 
obtained. In order to solve for the value of Y.sub.2 by Equation (5), it 
is necessary to calculate according to the following: 
EQU i.fwdarw..alpha..sup.i 
in order to find out the values of X.sub.1 and X.sub.2. 
Equation (5) is redefined in order to avoid the calculation of 
.alpha..sup.i from i and solve for the value Y.sub.2 : 
##EQU14## 
Referring to the flow chart of FIG. 3, when all transmitted words have been 
input into the decoder if all syndrome signals are zero as determined in 
step 310, this of course means that the transmitted words have no error 
words, and in the following step, step 340, the decoding action is 
terminated. If all syndrome signals are not zero, then in a step 312 the 
erasure counting value stored in the erasure counter 280 is tested. If the 
erasure counting value is 1, 2 or 3, the flow branches to the left where a 
determination is made as to whether there is any error word or not using 
the Forney Syndrome formulas separately according to step 314, step 316, 
or step 318, respectively. 
For example, in step 318, when the erasure counting value is equal to 1, 
the Forney Syndrome formulas of Equation (7) are evaluated. In step 316, 
when the erasure counting value is equal to 2, the Forney Syndrome 
formulas of Equation (8) are evaluated. In step 314, when erasure counting 
value is equal to 3, the Forney Syndrome formula of Equation (9) is 
evaluated. After one of the above-mentioned steps, the values of X.sub.i, 
such as X.sub.3 in step 320 and X.sub.2 in step 322 are obtained. 
When the erasure counting value is equal to 4, then in step 324 the value 
of Y.sub.4 is obtained according to Equation (3) and the values of 
S.sub.2, S.sub.1, and S.sub.0 are updated according to the value of 
Y.sub.4. In step 326 the value of Y.sub.3 is directly obtained according 
to Equation (4), and based on this value of Y.sub.3 the values of S.sub.2 
and S.sub.0 are updated. And then, in step 328, the value of Y.sub.2 is 
obtained by Equation (20), and based on this value of Y.sub.2 the value of 
S.sub.0 is updated. Then in step 330, the value of Y.sub.1 is obtained 
with the Equation (6). 
The method of calculating the value of Y.sub.i is initiated by substitution 
of the maximum value `i`. The calculated value Y.sub.i(max) may be taken 
as a known error word and that error word may be regarded as removed from 
the transmitted words. New values of S.sub.i are obtained by a method 
supplemented by Equation (2). 
For example, if the value of Y.sub.4 is known, then the new values of 
S.sub.i are: 
EQU S.sub.0 .rarw.S.sub.0 +Y.sub.4 
EQU S.sub.i .rarw.S.sub.0 +Y.sub.4 X.sub.4 
EQU S.sub.2 .rarw.S.sub.2 +Y.sub.4 X.sub.4.sup.2 
Every value of Y.sub.i can be obtained corresponding to every X.sub.i. 
In the same way, when the erasure counting value is equal to 3, then when 
in step 314 the Forney Syndrome T.sub.1 according to Equation (9) is 
computed and checked, if the result is not zero, which means that the 
errors cannot be decoded, this causes the termination of decoding in step 
342. If the Syndrome T.sub.1 is zero, then flow branches from decision 
step 314 and the values of Y.sub.1, Y.sub.2, and Y.sub.3 are computed 
separately in step 326, step 328, and step 330 as already described. 
When the erasure counting value is equal to 2, then in decision step 316 
the values of the Forney Syndromes T.sub.1 and T.sub.2 are computed and 
checked according to Equation (8). If T.sub.1 or T.sub.2, but not both, 
are equal to zero, the flow is terminated in step 342. If T.sub.1 and 
T.sub.2 are both equal to zero, then the process flow branches and the 
values of Y.sub.1 and Y.sub.2 are obtained separately in step 328 and step 
330, as previously described. 
When the erasure counting value is equal to 1, decision step 318 is 
performed to compute and check Forney Syndrome Equations (7) for T.sub.1, 
T.sub.2 and T.sub.3. If at least one, but not all of T.sub.1, T.sub.2 and 
T.sub.3 are equal to zero, decoding cannot be performed, causing the 
termination of decoding through step 342. If T.sub.1, T.sub.2 and T.sub.3 
are all equal to zero, then the value of Y.sub.1 is obtained in step 330 
as previously described. 
When the values Y.sub.i according to the series of steps above described 
are determined, the corresponding locations l.sub.i corresponding to 
Y.sub.i (the values of l.sub.i are obtained by the shift-logarithm 
operation on X.sub.i as described above). In the following step 332, a 
judgment is made as to whether l.sub.i is in the correct range or not. 
Because the sum of the inputted syndrome signals is n, the value of 
l.sub.i must be in the range from 0 to n-1. If l.sub.i is outside of the 
correct range decoding is not possible and is stopped at block 342. 
When the erasure counting value is equal to 0, decoding can be completed in 
a manner similar to the steps described hereinbefore. Flow branches from 
decision block 312 to step 334 where the number of error words is computed 
according to Equation (12). When some, i.e., one or more, but not all of 
the quantities computed in equation (12), are equal to zero, the decoding 
is insolvable and the decoding is terminated at block 340. When none of 
the quantities computed with Equation (12) are equal to zero, that is p=2, 
the values of X.sub.1.sup.2 and X.sub.2.sup.2 according to equations 
14-19, and then Y.sub.2 are computed and S.sub.0 is updated, in steps 336 
and 328 respectively. When the quantities computed with equation (12) are 
all equal to zero, that is p=1, the value of X.sub.1 is computed in step 
338, and the value of Y.sub.1 is computed in step 330. The test in step 
332 is then performed to check for the correct range, as previously 
described. 
In conclusion, the invention provides a new method of decoding of RS codes 
whose Hamming distance is equal to 5, by using the program to control 
sharing of information in the processing-based structure, and by using the 
calculation of location to avoid the redundant calculation of a Chien's 
Search. It is important that the arithmetic logic circuit thus becomes 
very simple without the need for the calculation of powers. Only the 
following four kinds of calculations are required: 
Inverting calculation: a.fwdarw.1/a 
Multiplication-addition calculation: a,b,c.fwdarw.a.multidot.b+c 
Shift-logarithm calculation: referring to Equation (16) 
Location calculation: referring to Equation (17) 
With regard to a shortened RS code, n.noteq.2.sup.m, the hardware of the 
shift-logarithm circuit and locator in the arithmetic logic circuit 230 
can be simplified even further. At first the shift-logarithm circuit can 
calculate the value of l.sub.i using X.sub.i and X.sub.i.sup.2. This is 
meaningful only when l.sub.i is in the range from 0 to n-1, and decoding 
cannot be completed when l.sub.i is outside of the range. Therefore, the 
logarithm table (not shown) in the shift-logarithm circuit 236 of FIG. 1 
corresponds only from 0 to 2.sup.n-1. If the inputted value is outside of 
the valid range, the shift-logarithm circuit outputs an error flag. 
Regarding the locator 238, because (l.sub.2 -l.sub.2) is in the range from 
1 to n-1 (when l.sub.1 &gt;l.sub.2), according to Equation (17), the output 
value of the locator 238 must be in the range from 1 to 2.sup.m-1. 
Therefore, the calculation of location can be executed in the range from 1 
to Max (2.sup.m-1, n-1). If the value is outside of this range, an error 
flag is output to show that the decoder cannot correct any error words, 
that is, the code is insolvable. 
Therefore, in the preferred embodiment with the decoder detecting RS codes 
whose Hamming distance is 5, the calculation of powers is not required. 
This permits a simplification of the arithmetic logic circuit. It does not 
have to repeatedly execute complex calculations when there are two error 
words and there is no erasure word. Therefore, the decoding speed is 
increased. Moreover, the invention provides a great improvement in fields 
concerning the decoding of RS codes. 
While the invention has been described by way of example and in terms of a 
preferred embodiment, it is to be understood that the invention is not 
limited to the disclosed embodiment. To the contrary, it is intended to 
cover various modifications and similar arrangements. Therefore, the scope 
of the appended claims should be accorded the broadest interpretation so 
as to encompass all such modifications and similar arrangements.