Syndrome computing apparatus

Details Syndrome computing apparatus Syndrome computing apparatus

1998-05-22

2002-03-19

Le, Dieu-Minh (Department: 2184)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S781000

Reexamination Certificate

active

06360349

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates to a syndrome computing apparatus used for error correcting apparatuses using cyclic codes.
At present, error correcting apparatuses with cyclic codes are utilized for communication devices, data memories, and so on. These error correcting apparatuses makes computation of syndromes on data (codewords) previously encoded by utilizing a generator polynominal. The error correcting apparatuses are adapted to detect data error positions by utilizing that all but “0” of the syndrome results from an error caused through a transmission line, which corresponds to an error position in a one-to-one manner.
The data as codewords used for computation is obtainable, through double error-correctable BCH (Bose-Chaudhuri-Hocquenghem) encoding, by expressing for example a generator polynominal G(x) using the following two polynomials g
1
(x) and g
2
(x).
g
1
(
x
)=
x
5
+x
2
+1
g
2
(
x
)=
x
5
+x
4
+x
3
+x
2
+1
where g
1
(x) is a primitive polynominal and g
2
(x) is a minimal polynominal having a solution &agr;
3
thereto provided that &agr; is a solution to g
1
(x). These polynominals are given based on the elements of a Galois field GF(2
5
−1).
The below computation is a modulo-2 arithmetic that uses, as a factor, an element of Galois field GF(
2
).
Here, the generator polynominal G(x) is expressed as:
G
(
x
)=
g
1
(
x
)
g
2
(
x
)=
x
10
+x
9
+x
8
+x
6
+x
5
+x
3
+1.
As for the data, information bits (i
20
, i
19
, i
18
, . . . , i
0
) representative of 21-bit actual information is given by:
I
(
X
)=
i
20
x
30
+i
19
x
29
+i
18
x
28
+ . . . +i
0
x
10
.
This equation is divided by the generator polynominal G(x) to obtain a residue (p
9
, p
8
, p
7
, . . . , p
0
). This residue is added as check bits to the information bits.
That is, if encoded data is given by W=(w
30
, w
29
, w
28
, . . . , w
0
), the following relationship is obtained:
(
w
30
, w
29
, w
28
, . . . , w
0
)=(
i
20
, i
19
, i
18
, . . . , i
0
, p
9
, p
8
, p
7
, . . . , p
0
)
This gives a residue
0
when it is divided by G(x).
This data can be expressed by a polynominal as:
W
(
X
)=
w
30
x
30
+w
29
x
29
+w
28
x
28
+ . . . +w
0
x
0
where W(X) has roots of &agr; and &agr;
3
. That is, those fallen onto W(&agr;)=W(&agr;
3
)=0 are included in a set for this code.
From the above, those having W(&agr;) and W(&agr;
3
) not fallen onto 0 will not constitute the above code, resulting in involving an error. This value is referred to as a syndrome (S). Data errors are specified of position and corrected by examining this value.
If the syndrome is vector-represented as S=(s
1
, s
2
) (s
1
and s
2
are respectively correspond to &agr; and &agr;
3
and the solution &agr;
3
of g
2
(x) is written by &bgr;, the syndrome can be determined by matrix operation as follows:
S=W·H
T
where H is a check matrix expressed by
H
=
[
α
30
,
α
29
,
α
28
,
…
⁢
 
,
α
2
,
α
1
,
α
0

β
30
,
β
29
,
β
28
,
…
⁢
 
,
β
2
,
β
1
,
β
0
]
As stated above, it has been a conventional practice to compute a syndrome directly from the data inputted. However, where the data is unclear of position at which data begins, it is impossible to correctly compute a syndrome.
To this end, where collating for a frame synchronous pattern, etc. that is unclear of position data (codewords) begins, the data has to be collated over the entire portions thereof such that it is determined whether or not it resides within an error correctable range where the number of the error bits can be warranted by the code.
SUMMARY OF THE INVENTION
It is therefore the object of the invention to provide a syndrome computing means which is capable of computing a syndrome at every 1-bit input even where a codeword is unclear of position at which it begins, by computing a first syndrome on input data and simultaneously a second syndrome on the data with a delay by a number of bits due to previous fetch into a delay means, and vector-adding modulo 2 the first syndrome without delay to the second syndrome at every 1-bit input.
According to the present invention, a syndrome computing apparatus, comprises: a first syndrome computing means for receiving a predetermined number of bits of data (codewords) encoded based on a predetermined generator polynominal, and performing a syndrome computation on the data inputted based on the generator polynominal; a delay means for outputting the data with a delay by the predetermined number of bits; a second syndrome computing means for receiving the data delayed by the predetermined number of bits, and performing a syndrome computation on the data inputted based on the generator polynominal; and an operating means for vector-adding modulo 2 a first syndrome outputted by the first syndrome computing means to a second syndrome outputted by the second syndrome computing means, whereby an output of the operating means is offered as a syndrome based on the generator polynominal.
Preferably, the first and second syndrome computing means are formed by a combination of an exclusive-OR circuit and registers, the delay means being configured by a shift register with the predetermined number of the bits of the codewords, and the operating means is configured by an exclusive-OR circuit.
According to one form of the present invention, a syndrome computing apparatus, comprises: a plurality of first syndrome computing means for receiving a predetermined number of bits of data encoded based on a generator polynominal, and performing a syndrome computation on the inputted data by using an individually assigned polynominal among a plurality of polynominals constituting the generator polynominal; a delay means for outputting the data with a delay by the predetermined number of bits; a plurality of second syndrome computing means for receiving the data delayed by the predetermined number of bits from the delay means, and performing a syndrome computation on the inputted data by using an individually assigned polynominal among a plurality of polynominals constituting the generator polynominal; a plurality of operating means for vector-adding modulo 2, using the individually assigned polynominal among the plurality of polynominals constituting the generator polynominal, a first syndrome to a second syndrome which are respectively outputted by the first syndrome computing means, the second syndrome computing means corresponding to the individually assigned polynominal; whereby an output of the operating means is offered as a syndrome based on the generator polynominal.


REFERENCES:
patent: 4354269 (1982-10-01), Vries et al.
patent: 4849975 (1989-07-01), Patel
patent: 5644695 (1997-07-01), Blaum et al.
patent: 5872799 (1999-02-01), Lee et al.
patent: 6-252874 (1994-09-01), None
patent: 7-074655 (1995-03-01), None

Affiliated with

Also associated with

Rating

Syndrome computing apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2825251