Efficient Error Correction of Multi-Bit Errors
AssigneeInfineon Technologies AG
InventorsThomas Kern, Michael Goessel, Christian Badack
Life of this patent
Estimating the term…
Abstract
A circuitry for error correction includes a plurality of subcircuits for determining intermediate values Zw0, Zw1, Zw2, Zw3 to be used as coefficients in an error correction expression (z1i, z2i, . . . , zmi)=Zw3·α3ji+Zw2·α2ji+Zw1·αji+Zw0. The intermediate values Zw0, Zw1, Zw2, Zw3 are determined depending on subsyndromes s1, s3, s5 so that in case of a 1-bit, 2-bit, or 3-bit error zi=(z1i, z2i, . . . , zmi)=(0, 0, . . . , 0) when an error occurred in the bit position i, and zi=(z1i, z2i, . . . , zmi)≠(0, 0, . . . , 0) when no error occurred in the bit position i. A correction value Δvi= for the bit position i may then be determined on the basis of the error correction expression evaluated for αji.
Claims18
A circuitry SK for an error correction of at least 1-bit, 2-bit, and 3-bit errors of bits in an n-digit binary word v′=v1′, . . . , vn′ which resulted from bit errors from an n-digit codeword v=v1, . . . , vn of a binary BCH code C over the Galois field GF(2m), wherein m≧4, wherein the code C comprises a code distance of at least d≧7, wherein the BCH code C comprises an H matrix H, so that m first rows of the H matrix form a submatrix H1, m second rows of the H matrix form a second submatrix H3 and further m rows of the H matrix form a third submatrix H5 with
- H1=(h11, . . . ,h1n,H3=(h31, . . . ,h3n) and H5=(h51, . . . ,h5n),
- wherein
- h11=αj1, . . . ,h1n=αjn,
- h31=α3(j1), . . . ,h3n=α3(jn),
- h51=α5(j1), . . . ,h5n=α5(jn),
- applies, α is an element of the Galois field GF (2m) in its vector representation as an m-component binary column vector and the respective exponent j of αj is to be interpreted modulo 2m−1 and n≧2m−1 applies, comprising:
- a syndrome generator Synd configured to determine an error syndrome s, wherein m first components of s form an m-component subsyndrome s1, m second components of s form a second m-component subsyndrome s3 and further m components of s form a third subsyndrome s5, wherein
- s1=H1·v′,s3=H3·v′, and s5=H5·v′
- apply,
- a plurality of subcircuits wherein for each bit v1′ subject to possible error correction of the n-digit binary word v′=v1′, . . . , vn′ a subcircuit SKi exists which is configured so that it forms, from intermediate values Zw0, Zw1, Zw2, Zw3 which are equal for all bit positions subject to possible error correction, a correction value Δvi according to the following relation
- Δv1=
- wherein
- (z1i,z2i, . . . ,zmi)=Zw3·α3ji+Zw2·α2ji+Zw1·αji+Zw0
- and the intermediate values Zw0, Zw1, Zw2, Zw3 are determined depending on the subsyndromes s1, s3, s5 so that in case of a 1-bit error or a 2-bit error or a 3-bit error the following applies:
- zi=(z1i, z2i, . . . , zmi)=(0, 0, . . . , 0) when an error occurred in the bit position i and zi=(z1i, z2i, . . . , zmi)≠(0, 0, . . . , 0) when no error occurred in the bit position i;
- wherein for determining the intermediate values Zw0, Zw1, Zw2, and Zw3 one subcircuit SZw0, SZw1, SZw2 and SZw3 each exists which is each configured so that it provides the same intermediate values Zw0, Zw1, Zw2 and Zw3 from the subsyndromes s1, s3, s5 for each bit position subject to possible error correction of the word v′;
- and
- a combinational circuit Vkn configured to combine bits that are subject to possible error correction vi′ in a component-wise manner with corresponding correction values Δvi provided by the subcircuit SKi into possibly corrected bits vicor.
A method for error correction of at least 1-bit, 2-bit, and 3-bit errors of bits in an n-digit binary word which resulted from bit errors from an n-digit codeword v=v1, . . . , vn of a binary BCH code C over the Galois field GF(2m), wherein m≧4, wherein the code C comprises a code distance of at least d≧7, wherein the BCH code C comprises an H matrix H, so that m first rows of the H matrix form a submatrix H1, m second rows of the H matrix form a second submatrix H3 and further m rows of the H matrix form a third submatrix H5 with
- H1=(h11, . . . ,h1n,H3=(h31, . . . ,h3n) and H5=(h51, . . . ,h5n),
- wherein
- h11=αj1, . . . ,h1n=αjn,
- h31=α3(j1), . . . ,h3n=α3(jn),
- h51=α5(j1), . . . ,h5n=α5(jn),
- applies, α is an element of the Galois field GF (2m) in its vector representation as an m-component binary column vector and the respective exponent j of a′ is to be interpreted modulo 2m−1 and n≧2m−1 applies, wherein the method comprises:
- determining an error syndrome s, wherein m first components of s form an m-component subsyndrome s1, m second components of s form a second m-component subsyndrome s3 and further m components of s form a third subsyndrome s5, wherein
- s1=H1·v′,s3=H3·v′, and s5=H5·v′
- apply,
- determining intermediate values Zw0, Zw1, Zw2, and Zw3 from the subsyndromes s1, s3, s5, the intermediate values being the same for each bit position subject to possible error correction of the word v′;
- forming a correction value Δvi for each bit vi′ subject to possible error correction from the intermediate values Zw0, Zw1, Zw2, Zw3 which are equal for all bit positions subject to possible error correction, a according to the following relation
- Δvi=
- wherein
- (z1i,z2i, . . . ,zmi)=Zw3·α3ji+Zw2·α2ji+Zw1·αji+Zw0
- and the intermediate values Zw0, Zw1, Zw2, Zw3 are determined depending on the subsyndromes s1, s3, s5 so that in case of a 1-bit error or a 2-bit error or a 3-bit error the following applies:
- zi=(z1i, z2i, . . . , zmi)=(0, 0, . . . , 0) when an error occurred in the bit position i and zi=(z1i, z2i, . . . , zmi)≠(0, 0, . . . , 0) when no error occurred in the bit position i;
- combining bits that are subject to possible error correction vi′ in a componentwise manner with corresponding correction values Δvi into possibly corrected bits vicor.
A non-transitory storage medium having stored thereon a computer program having a program code for performing, when running on a computer, a method for error correction of at least 1-bit, 2-bit and 3-bit errors of bits in an n-digit binary word v′=v1′, . . . , vn′ which resulted from bit errors from an n-digit codeword v=v1, . . . , vn of a binary BCH code C over the Galois field GF(2m), wherein m≧4, wherein the code C comprises a code distance of at least d≧7, wherein the BCH code C comprises an H matrix H, so that m first rows of the H matrix form a submatrix H1, m second rows of the H matrix form a second submatrix H3 and further m rows of the H matrix form a third submatrix H5 with
- H1=(h11, . . . ,h1n,H3=(h31, . . . ,h3n) and H5=(h51, . . . ,h5n),
- wherein
- h11=αj1, . . . ,h1n=αjn,
- h31=α3(j1), . . . ,h3n=α3(jn),
- h51=α5(j1), . . . ,h5n=α5(jn),
- applies, α is an element of the Galois field GF (2m) in its vector representation as an m-component binary column vector and the respective exponent j of d is to be interpreted modulo 2m−1 and n≧2m−1 applies, wherein the method comprises:
- determining an error syndrome s, wherein m first components of s form an m-component subsyndrome s1, m second components of s form a second m-component subsyndrome s3 and further m components of s form a third subsyndrome s5, wherein
- s1=H1·v′,s3=H3·v′, and s5=H5·v′
- apply,
- determining intermediate values Zw0, Zw1, Zw2, and Zw3 from the subsyndromes s1, s3, s5, the intermediate values being the same for each bit position subject to possible error correction of the word v′;
- forming a correction value Δvi for each bit vi′ subject to possible error correction from the intermediate values Zw0, Zw1, Zw2, Zw3 which are equal for all bit positions subject to possible error correction, a according to the following relation
- Δv1=
- wherein
- (z1i,z2i, . . . ,zmi)=Zw3·α3ji+Zw2·α2ji+Zw1·αji+Zw0
- and the intermediate values Zw0, Zw1, Zw2, Zw3 are determined depending on the subsyndromes s1, s3, s5 so that in case of a 1-bit error or a 2-bit error or a 3-bit error the following applies:
- zi=(z1i, z2i, . . . , zmi)=(0, 0, . . . , 0) when an error occurred in the bit position i and z1=(z1i, z2i, . . . zmi)≠(0, 0, . . . 0) when no error occurred in the bit position i;
- and
- combining bits that are subject to possible error correction vi′ in a componentwise manner with corresponding correction values Δvi into possibly corrected bits vicor.
Dependencies are inferred from the claim text.