Method and apparatus for decoding error correcting code
First Claim
1. An error correcting code decoding apparatus comprising:
- means for receiving a digital signal train V(X) added with an error correcting code on the basis of a generator polynominal G(X) formed by a first primitive polynominal G1 (X) and a second primitive polynominal G2 (X);
first syndrome calculating means for dividing said received signal train V(X) by said first primitive polynominal G1 (X) to obtain a syndrome S1 (X), being the remainder term, said first primitive polynominal G1 (X) being a polynominal of degree m (m;
positive integer), said syndrome S1 (X) being obtained by dividing said signal train V(X), including a single-bit error, by said first primitive polynominal G1 (X) being in a cycle of 2m -1;
second syndrome calculating means for dividing said received signal train V(X) by said second primitive polynominal G2 (X) to obtain an actual syndrome S2 (X), being the remainder term, said second primitive polynominal G2 (X) being a polynominal of said degree m, said actual syndrome S2 (X) being obtained by dividing said signal train V(X), including said single-bit error, by said second primitive polynominal G2 (X) being in a cycle of (2m -1)/n (n;
positive integer);
error position calculating means for obtaining a single-bit error position l of said received signal train on the basis of said syndrome S1 (X) obtained by said first syndrome calculating means;
means for obtaining an assumed syndrome S2 '"'"'(X) corresponding to said single-bit error position l calculated by said error position calculating means among values of said actual syndrome S2 (X) corresponding to single-bit errors;
means for comparing said actual syndrome S2 (X) outputted from said second syndrome calculating means with said assumed syndrome S2 '"'"'(X); and
means for judging that said received signal train V(X) includes said single-bit error upon coincidence of said actual syndrome S2 (X) with said assumed syndrome S2 '"'"'(X) while judging that said received signal train V(X) includes a double-bit error or a multiple-bit error upon non-coincidence as the result of comparison by said comparing means.
1 Assignment
0 Petitions
Accused Products
Abstract
A received signal train V(X), to which a BCH error correcting code is added on the basis of a generator polynominal G(X)=X12 +X10 +X8 +X5 +X4 +X3 +1, is divided by primative polynominals G1 (X)=X6 +X+1 and G2 (X)=X6 +X4 +X2 +X+1 resulting from factorization of G(X), to obtain syndromes S1 (X) and S2 (X) respectively. A single-bit error position λ of the signal train V(X) is obtained from a first ROM table with the address of the syndrome S1 (X). Among values of the syndrome S2 (X) corresponding to single-bit errors, a syndrome S2 '"'"'(X) corresponding to the single-bit error position λ is calculated from a second ROM table, to be compared with the syndrome S2 (X) obtained by dividing the received signal train V(X) by the primitive polynominal G2 (X). Upon coincidence of the synchromes S2 '"'"'(X) and S2 (X), a judgement is made on a primitive error, to perform correction. Upon non-coincidence, a judgement is made on a secondary error or an error of higher degree.
31 Citations
15 Claims
-
1. An error correcting code decoding apparatus comprising:
-
means for receiving a digital signal train V(X) added with an error correcting code on the basis of a generator polynominal G(X) formed by a first primitive polynominal G1 (X) and a second primitive polynominal G2 (X); first syndrome calculating means for dividing said received signal train V(X) by said first primitive polynominal G1 (X) to obtain a syndrome S1 (X), being the remainder term, said first primitive polynominal G1 (X) being a polynominal of degree m (m;
positive integer), said syndrome S1 (X) being obtained by dividing said signal train V(X), including a single-bit error, by said first primitive polynominal G1 (X) being in a cycle of 2m -1;second syndrome calculating means for dividing said received signal train V(X) by said second primitive polynominal G2 (X) to obtain an actual syndrome S2 (X), being the remainder term, said second primitive polynominal G2 (X) being a polynominal of said degree m, said actual syndrome S2 (X) being obtained by dividing said signal train V(X), including said single-bit error, by said second primitive polynominal G2 (X) being in a cycle of (2m -1)/n (n;
positive integer);error position calculating means for obtaining a single-bit error position l of said received signal train on the basis of said syndrome S1 (X) obtained by said first syndrome calculating means; means for obtaining an assumed syndrome S2 '"'"'(X) corresponding to said single-bit error position l calculated by said error position calculating means among values of said actual syndrome S2 (X) corresponding to single-bit errors; means for comparing said actual syndrome S2 (X) outputted from said second syndrome calculating means with said assumed syndrome S2 '"'"'(X); and means for judging that said received signal train V(X) includes said single-bit error upon coincidence of said actual syndrome S2 (X) with said assumed syndrome S2 '"'"'(X) while judging that said received signal train V(X) includes a double-bit error or a multiple-bit error upon non-coincidence as the result of comparison by said comparing means. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. An error correcting code decoding method comprising the steps of:
-
a first step of receiving a digital signal train V(X) added with an error correcting code on the basis of a generator polynominal G(X) formed by a first primitive polynominal G1 (X) and a second primitive polynominal G2 (X); a second step of dividing said received signal train V(X) by said first primitive polynominal G1 (X) to obtain a syndrome S1 (X), being the remainder term, said first primitive polynominal G1 (X) being a polynominal of degree m (m;
positive integer), said syndrome S1 (X) being obtained by dividing said signal train V(X), including a single-bit error, by said first primitive polynominal G1 (X) being in a cycle of 2m -1;a third step of dividing said received signal train V(X) by said second primitive polynominal G2 (X) to obtain an actual syndrome S2 (X), being the remainder term, said second primitive polynominal G2 (X) being a polynominal of degree m, said actual syndrome S2 (X) being obtained by dividing said signal train V(X), including said single-bit error, by said primitive polynominal G2 (X) being in a cycle of (2m -1)/n (n;
positive integer;a fourth step of obtaining a single-bit error position l of said received signal train on the basis of said syndrome S1 (X) obtained by said second step; a fifth step of obtaining an assumed syndrome S2 '"'"'(X) corresponding to said single bit error position l calculated in said fourth step among values of said actual syndrome S2 (X) corresponding to single-bit errors; a sixth step of comparing said actual syndrome S2 (X) obtained in said third step with said assumed syndrome S2 '"'"'(X); and a seventh step of judging that said received signal train V(X) includes said single-bit error l upon coincidence of said actual syndrome S2 (X) with said assumed syndrome S2 '"'"'(X) while judging that the same includes a double-bit error or a multiple-bit error upon non-coincidence as the result of comparison in said sixth step. - View Dependent Claims (11, 12, 13, 14, 15)
-
Specification