ERROR PROCESSING AND CORRECTION OF ADJACENT 2-BIT ERRORS

Abstract

What is proposed is a solution for processing errors in a sequence of bits, wherein the sequence of bits, in the error-free case, forms a codeword of an error code, wherein the error code is based on an H-matrix or is able to be determined thereby, wherein an error syndrome is determined for the sequence of bits, wherein a link is determined between components of the error syndrome and parts of the H-matrix, and wherein two adjacent bits in the sequence of bits are corrected if the link adopts a predefined value.

Claims

1. A method, comprising: processing errors in a sequence of bits, wherein the sequence of bits, in an error-free case, forms a codeword of an error code, wherein the error code is based on an H-matrix or is able to be determined by the H-matrix; determining an error syndrome for the sequence of bits; determining a link between components of the error syndrome and parts of the H-matrix; and correcting two adjacent bits in the sequence of bits when the link adopts a predefined value.

2. The method of claim 1, in which the two adjacent bits in the sequence of bits are corrected and the components of the error syndrome are inverted when the corresponding linked components of columns of the H-matrix have an odd number of ones, and are not inverted when the corresponding linked components of the columns of the H-matrix have an even number of ones.

3. The method of claim 2, in which the two adjacent bits in the sequence of bits are corrected by way of a correction signal, wherein the correction signal is determined based on a Boolean link between the inverted components of the error syndrome and the non-inverted components of the error syndrome.

4. The method of claim 3, in which the two adjacent bits in the sequence of bits are corrected when the link adopts a predefined value in a predefined number of components.

5. The method of claim 4, in which the predefined number of components corresponds to a number that is fewer than all of the predefined number of components.

6. The method of claim 3, in which the two adjacent bits in the sequence of bits are not corrected when the link does not adopt the predefined value and/or adopts a value different from the predefined value.

7. The method of claim 1, in which the components of the error syndrome are sub-error syndromes of the error syndrome.

8. The method of claim 1, in which the parts of the H-matrix are components of the H-matrix, columns of the H-matrix, and/or sub-matrices of the H-matrix.

9. The method of claim 1, in which the two adjacent bits of the sequence of bits are corrected, wherein each of the bits has a bit position that corresponds to a column of the H-matrix.

10. The method of claim 1, in which components of the error syndrome are linked with parts of the H-matrix by linking the components of the error syndrome with at least two columns of the H-matrix or with components of two columns of the H-matrix.

11. The method of claim 10, in which the at least two columns of the H-matrix are adjacent to one another.

12. The method of claim 10, in which components of adjacent columns of the H-matrix are linked with components of the error syndrome.

13. The method of claim 1, in which the predefined value is equal to a vector r) or equal to a vector I.

14. The method of claim 1, in which the error code is able to correct at least 2-bit errors.

15. The method of claim 1, in which the error code is a BCH code, the error syndrome comprises a first sub-error syndrome and a second sub-error syndrome, and components of the first sub-error syndrome are linked with corresponding components of columns of the H-matrix.

16. The method of claim 3, in which the two adjacent bits of the sequence of bits are corrected simultaneously or at least partially simultaneously.

17. A computer program product that is able to be loaded directly into a memory of a digital computer and comprises program code portions that are configured to perform acts of the method of claim 1.

18. A device for processing errors in a sequence of bits, wherein the device has a processing unit that is configured to carry out the acts of the method of claim 1.

19. The device as claimed in claim 18, wherein the device comprises a memory containing the sequence of bits.

20. The device as claimed in claim 18, in which the device is a memory or a memory system.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0052] The above-described properties, features and advantages of this invention and the way in which these are achieved will be described below in connection with a schematic description of exemplary embodiments that are explained in more detail in connection with the drawings. In this case, for the sake of clarity, identical or functionally identical elements may be provided with the same reference signs.

[0053] FIG. 1 shows a flowchart for illustrating one exemplary variant of the solution for processing errors as proposed here, and in particular for correcting adjacent 2-bit errors.

[0054] FIG. 2 shows one exemplary embodiment of a correction circuit for 1-bit errors and adjacent 2-bit errors.

[0055] FIG. 3 shows a schematic arrangement for determining signals E.sub.01 to E.sub.52 based on sub-error syndromes S.sub.j, S.sub.j of the error syndrome S by way of inverters.

DETAILED DESCRIPTION

[0056] What is proposed for example is fast parallel correction of adjacent 2-bit errors.

[0057] This approach may be used in particular for linear error codes (also referred to below as codes) that are suitable for correcting adjacent 2-bit errors. Hamming codes are one type of linear error code. For the purposes of Hamming codes, two Hamming matrices can be defined: a code generator matrix G and a parity-check matrix H:

[00001]$G^T:=\left(\begin{array}{cccc}1& 1& 0& 1\\ 1& 0& 1& 1\\ 1& 0& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right),H:=\left(\begin{array}{ccccccc}1& 0& 1& 0& 1& 0& 1\\ 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 1& 1& 1& 1\end{array}\right).$

[0058] The starting point is for example a linear error code (also referred to as code) having a parity-check matrix (H-matrix) characterizing this code

H=(h.sup.0,h.sup.1,h.sup.2,h.sup.3, . . . ,h.sup.n1),

wherein

h.sup.0,h.sup.1,h.sup.2,h.sup.3, . . . ,h.sup.n1

are column vectors of the H-matrix. A bit vector v with n bits is also given:

=(.sub.0,.sub.1, . . . ,.sub.n1).

[0059] The bit vector v may potentially contain defective bits. An error syndrome S

S=H.Math.

is determined for the bit vector v.

[0060] The bit vector v may result from bit errors from a code vector

v=(v.sub.0,v.sub.1, . . . ,v.sub.N1)

of the code. The code vector v is also referred to as codeword of the code.

If

[0061]
v=

then the bit vector v is the same as the codeword v, and thus no (detectable) error has occurred.

[0062] For the codeword v, it holds for the error syndrome S that:

S=H.Math.v=0

[0063] For a 2-bit error at the bit positions i and j, the error syndrome S results as

S=h.sup.i+h.sup.j,

[0064] and for an adjacent 2-bit error at the bit positions i and i+1, the error syndrome S results as

S=h.sup.i+h.sup.i+1.

[0065] The approach proposed here may be applied in particular when adjacent 2-bit errors to be corrected have a different error syndrome.

[0066] If all adjacent 2-bit errors of the code have a separate error syndrome that differs from all other error syndromes of adjacent 2-bit errors, the solution proposed here may be used to correct all of these adjacent 2-bit errors.

[0067] If the error syndromes of 1-bit errors are different from all error syndromes of adjacent 2-bit errors, then 1-bit errors may also be corrected.

[0068] If the error syndromes of all non-adjacent 2-bit errors are different from all error syndromes of the adjacent 2-bit errors to be corrected, then the non-adjacent 2-bit errors may differ from adjacent 2-bit errors based on their error syndrome.

[0069] The following expressions may be used for the error correction of adjacent 2-bit errors:

[00002]$S+h^0+h^1$$S+h^1+h^2$$S+h^2+h^3$$S+h^3+h^4$$.Math.$$S+h^{n-2}+h^{n-1}$

[0070] Components of the bit vector v may accordingly be corrected as follows: [0071] The components v.sub.0; and v.sub.1 are corrected to components

v.sub.0.sup.cor=v.sub.0+1 and

v.sub.1.sup.cor=v.sub.1+1

when

S+h.sup.0+h.sup.1={right arrow over (0)}. [0072] The components v.sub.1 and v.sub.2 are corrected to components

v.sub.1.sup.cor=v.sub.1+1 and

v.sub.2.sup.cor=v.sub.2+1

when

S+h.sup.1+h.sup.2={right arrow over (0)} [0073] The components v.sub.2 and v.sub.3 are corrected to components

v.sub.2.sup.cor=v.sub.2+1 and

v.sub.3.sup.cor=v.sub.3+1

when

S+h.sub.2+h.sub.3={right arrow over (0)} [0074] The components v.sub.3 and v.sub.4 are corrected to components

v.sub.3.sup.cor=v.sub.3+1 and

v.sub.4.sup.cor=v.sub.4+1

when

S+h.sup.3+h.sup.4={right arrow over (0)} [0075] The components v.sub.n2 and v.sub.n1 are corrected to components

v.sub.n2.sup.cor=c.sub.n2+1 and

v.sub.n1.sup.cor=v.sub.n1+1

when

S+h.sup.n2+h.sup.n1={right arrow over (0)}

[0076] In this case, + denotes the component wise XOR linking of the corresponding binary vectors.

[0077] One option is to correct the corresponding bits at the bit positions i and i+1 when for example

[00003]$S+h^i+h^{i-1}={\left(\underset{M}{\underset{}{1,1,.Math.,1}}\right)}^T$

wherein M is the number of components of the column vector h. The vector

[00004]${\left(\underset{M}{\underset{}{1,1,.Math.,1}}\right)}^T$

is an exemplary population. Other populations of the vector are also possible. It is in particular not necessary for all of the bits of the vector to have the same value.

[0078] The superscript T after the vector indicates that it is the transposed vector. By way of example, the bit positions i and i+1 should be corrected when

S+h.sup.i+h.sup.i+1=(b.sub.1,b.sub.2, . . . ,b.sub.M).sup.T

and a subset

{b.sub.i.sub.1,b.sub.i.sub.2, . . . ,b.sub.i.sub.N}

of the bits

b.sub.1,b.sub.2, . . . ,b.sub.M

where N<M, adopt a particular value, for example the value 0.

[0079] This is described further below by way of example for a 2-bit error correcting BCH code in a Galois field GF(2.sup.m). There, the error syndrome S=[s.sub.1,s.sub.3], where M=2m, has the two m-component sub-syndromes s.sub.1 and s.sub.3 and an adjacent 2-bit error is able to be corrected when the m-dimensional sub-syndrome s.sub.1 has a predetermined value, for example the value

[00005]${\left(\underset{m}{\underset{}{0,.Math.,0}}\right)}^T$

Since the column vectors

h.sup.0,h.sup.1, . . . ,h.sup.n1

are constant binary column vectors of the H-matrix, the expressions

[00006]$\begin{array}{c}S+h^0+h^1\\ .Math.\\ S+h^{n-2}+h^{n-1}\end{array}$

may be achieved by converting (or not converting) the components of the error syndrome S, which simplifies implementation in comparison with more complex XOR gates.

[0080] If for example the error syndrome

S=(S.sub.1,S.sub.2, . . . ,S.sub.M).sup.T

[0081] where M>1, is an M-component binary vector and the column vector

h.sup.i=(h.sub.1.sup.i,h.sub.2.sup.i, . . . ,h.sub.M.sup.i).sup.T

is an M-component binary column vector of the H-matrix of the error code, then

S+h.sup.i+h.sup.i+1

is determined by inverting those components of the error syndrome S for which exactly one of the corresponding components of the column vector h.sup.i or of the column vector h.sup.i+1 is equal to 1 and not inverting those components of the error syndrome S for which the corresponding components of the column vector vector h.sup.i and of the column vector h.sup.i+1 are the same (that is to say either both equal to 1 or both equal to 0).

[0082] It then holds for example for i=0, n1 and j=1, M

[00007]$\begin{array}{cc}S+h^i+h^{i+1}=\left(\begin{array}{c}{S}_1^{}\\ S_2^{}\\ .Math.\\ S_M^{}\end{array}\right)\mathrm{with}{S}_j^{}=\{\begin{array}{cc}{S}_j& \mathrm{for}{h}_j^i+h_j^{i+1}=0\\ {\stackrel{\_}{S}}_j=S_j+1& \mathrm{for}{h}_j^i+h_j^{i+1}=1\end{array}& \left(1\right)\end{array}$

[0083] One option is that of not inverting those components of the error syndrome S for which exactly one of the corresponding components of h.sup.i and h1 is equal to 1 and inverting (only) those components of the error syndrome S for which the corresponding components of h.sup.i and h.sup.i+1 are either both equal to 1 or both equal to 0.

[0084] S+h.sup.i may also be determined by inverting those components of the error syndrome S for which the corresponding component of h.sup.i is equal to 1.

[0085] It will be explained below that, in addition to adjacent 2-bit errors, 1-bit errors may also be corrected.

[0086] If a 1-bit error is present at the bit position k, the error syndrome is determined as

S=h.sup.k

and it holds that

S+h.sup.k=h.sup.k+h.sup.k={right arrow over (0)}

[0087] For a bit position L, where Lk, it holds that

S+h.sup.L=h.sup.k+h.sup.L{right arrow over (0)}

[0088] The following expressions may be used for the error correction of 1-bit errors:

[00008]$S+h^0$$S+h^1$$S+h^2$$S+h^3$$.Math.$$S+h^{n-2}$$S+h^{n-1}$

[0089] Components of the bit vector v may accordingly be corrected as follows: [0090] The component v.sub.0 is corrected to the component

v.sub.0.sup.cor=v.sub.0+1

when

S+h.sup.0={right arrow over (0)} [0091] The component v.sub.1 is corrected to the component

v.sub.1.sup.cor=v.sub.1+1

when

S+h.sup.1={right arrow over (0)} [0092] The component v.sub.2 is corrected to the component

v.sub.2.sup.cor=v.sub.2+1

when

S+h.sup.2={right arrow over (0)} [0093] The component v.sub.3 is corrected to the component

v.sub.3.sup.cor=v.sub.3+1

when

S+h.sup.3={right arrow over (0)} [0094] The component is corrected to the component

v.sub.n2.sup.cor=v.sub.n2+1

when

S+h.sup.n2=0 [0095] The component v.sub.n1 is corrected to the component

v.sub.n1.sup.cor=v.sub.n1+1

when

S+h.sup.n1=0

[0096] If both 1-bit errors and adjacent 2-bit errors are to be corrected, the following expressions may be used:

[00009]$\begin{array}{ccc}S+h^0,& & S+h^0+h^1\\ S+h^1,& & S+h^1+h^2\\ S+h^2,& & S+h^2+h^3\\ S+h^3,& & S+h^3+h^4\\ & .Math.& \\ S+h^{n-2},& & S+h^{n-2}+h^{n-1}\\ S+h^{n-1}& & \end{array}$

It then accordingly holds that: [0097] The component v.sub.0 is corrected to the component

v.sub.0.sup.cor=v.sub.0+1

if

S+h.sup.0=0 or

S+h.sup.0+h.sup.1=0 [0098] The component v.sub.1 is corrected to the component

v.sub.1.sup.cor=v.sub.1+1

if

S+h.sup.1=0 or

S+h.sup.0+h.sup.1=0 or

S+h.sup.1+h.sup.2=0 [0099] The component v.sub.2 is corrected to the component

v.sub.2.sup.cor=v.sub.2+1

if

S+h.sup.2=0 or

S+h.sup.1+h.sup.2=0 or

S+h.sup.2+h.sup.3=0 [0100] The component v.sub.3 is corrected to the component

v.sub.3.sup.cor=v.sub.3+1

if

S+h.sup.3=0 or

S+h.sup.2+h.sup.3=0 or

S+h.sup.3+h.sup.4=0 [0101] The component v.sub.n2 is corrected to the component

v.sub.n2.sup.cor=v.sub.n2+1

if

S+h.sup.n2=0 or

S+h.sup.n3+h.sup.n2=0 or

S+h.sup.n2+h.sup.n1=0 [0102] The component v.sub.n1 is corrected to the component

v.sub.n1.sup.cor=v.sub.n1+1

if

S+h.sup.n1=0 or

S+h.sup.n2+h.sup.n1=0.

[0103] The approach described here may be applied to error codes that have different error syndromes for adjacent 2-bit errors to be corrected. Examples of such error codes are: [0104] an error code that is able to correct two adjacent bit errors and a 1-bit error (for example an Abramson code, see [3]), [0105] an at least 2-bit error correcting BCH code, [0106] a code that is able to correct at least 2-bit errors, as described for example in [4], [0107] a code in which a (larger) code composed of sub-codes is formed, wherein the code is suitable for correcting adjacent 2-bit errors and for detecting non-adjacent 2-bit errors (such a code is disclosed for example in [5]), [0108] another linear code.

[0109] One option, in the case of a 2-bit error correcting code, is to correct adjacent 2-bit errors in accordance with the described method and then, if there are no adjacent 2-bit errors, but rather a non-adjacent error, to detect the non-adjacent error or likewise to correct same.

[0110] The approach proposed here is particularly advantageous when adjacent 2-bit errors occur commonly, since a particularly fast and thus efficient correction is proposed for these.

[0111] FIG. 1 shows a flowchart for illustrating one exemplary variant of the proposed solution for error processing, and in particular for correcting adjacent 2-bit errors.

[0112] Step 101: A sequence of bits is read from a memory. The memory may be an SRAM or another memory.

[0113] Step 102: An error syndrome is determined. The error code is based on an H-matrix. An error syndrome results based on this H-matrix and comprises multiple components. Components of the error syndrome may be combined to form sub-syndromes.

[0114] Step 103: It is checked whether the error syndrome is equal to 0 or other than If the error syndrome is equal to 0, then the sequence of bits forms a codeword of the error code. No error is recognized and no correction is made. The method may be ended for this sequence. If the error syndrome is other than 0, the method is continued with the next step.

[0115] Step 104: Components of the error syndrome are linked with parts of the H-matrix. Such parts of the H-matrix may be components of two adjacent columns of the H-matrix.

[0116] One option is for the components of the error syndrome to be linked with the components of a multiplicity of adjacent columns in parallel or at least in a temporally overlapping manner, so as to result in different linked values for the different adjacent columns. In this case, the multiplicity of adjacent columns may comprise all columns.

[0117] Step 105: The correction signal is determined. The correction signal is 1 when the linked value of the error syndrome with the components of two adjacent columns adopts the predefined value. The correction signal is 0 when it adopts a value different from the predefined value. There is thus a correction signal 1 for exactly one combination of two adjacent columns, and a correction signal 0 for all other combinations of adjacent columns.

[0118] If no adjacent 2-bit error is present, no combination of the error syndrome with the components of two adjacent columns of the H-matrix is equal to the predefined value, and the correction signal for all combinations is equal to 0.

[0119] Step 106: If the correction signal is 1, the associated adjacent 2-bit error is corrected.

EXAMPLE

[0120] The following H-matrix is used by way of example as an explanation:

[00010]$\begin{array}{cc}H=\left(\begin{array}{cccccc}1& 0& 0& 1& 0& 1\\ 0& 1& 0& 1& 1& 1\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 1& 1& 1& 1\end{array}\right)=\left(h^0,h^1,h^2,h^3,h^4,h^5\right)& \left(2\right)\end{array}$

[0121] The H-matrix according to equation (2) thus comprises the six column vectors:

h.sup.0=(1,0,0,1).sup.T,

h.sup.1=(0,1,0,1).sup.T,

h.sup.2=(0,0,1,1).sup.T,

h.sup.3=(1,1,0,1).sup.T,

h.sup.4=(0,1,1,1).sup.T and

h.sup.5=(1,1,1,1).sup.T.

[0122] In this example, the notation introduced above applies accordingly:

n=6

M=4

S=S.sub.1,S.sub.2,S.sub.3,S.sub.4.

[0123] A check reveals that the following column vectors

h.sup.0+h.sup.1,h.sup.1+h.sup.2,h.sup.2+h.sup.3,h.sup.3+h.sup.4,h.sup.4+h.sup.5

and

h.sup.0,h.sup.1,h.sup.2,h.sup.3,h.sup.4,h.sup.5

are pairwise different.

[0124] The correction takes place when either a 1-bit error or an adjacent 2-bit error has been determined.

[0125] For the H-matrix according to equation (2), FIG. 2 shows one exemplary embodiment of a correction circuit for 1-bit errors and adjacent 2-bit errors.

[0126] The potentially defective binary vector

v=(v.sub.0,v.sub.1,v.sub.2,v.sub.3,v.sub.4,v.sub.5)

is corrected by the circuit shown in FIG. 2 to a corrected vector

v.sup.cor=(v.sub.0.sup.cor,v.sub.1.sup.cor,v.sub.2.sup.cor,v.sub.3.sup.cor,v.sub.4.sup.cor,v.sub.5.sup.cor)

using signals

E.sub.01,E.sub.21,E.sub.31,E.sub.41,E.sub.51

and

E.sub.12,E.sub.22,E.sub.32,E.sub.42,E.sub.52

[0127] The signal E.sub.01 results from a component wise linking of the components S.sub.1 to S.sub.4 of the error syndrome S with the components of the 0th column

h.sup.0=(1,0,0,1).sup.t

of the H-matrix according to equation (2), wherein a downstream NOR gate (NOT OR gate) is used to check whether all components of S+h are equal to 0.
It holds that:

[00011]$\begin{array}{c}{E}_{01}=\mathrm{NOR}\left(S_1+1,S_2,S_3,S_4+1\right)=\\ =\mathrm{NOR}\left({\stackrel{\_}{S}}_1,S_2,S_3,{\stackrel{\_}{S}}_4\right).\end{array}$

E.sub.01 is thus 1 whenever all of the inputs of the NOR gate are equal to 0. This is the case for

S.sub.1=1

S.sub.2=0

S.sub.3=0

S.sub.4=1

[0128] According to the present example, it holds that

S+h.sup.0=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T,

S+h.sup.1=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T,

S+h.sup.2=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T,

S+h.sup.3=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T,

S+h.sup.4=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T,

S+h.sup.5=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T

and

S+h.sup.0+h.sup.1=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T,

S+h.sup.1+h.sup.2=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T,

S+h.sup.2+h.sup.3=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T,

S+h.sup.3+h.sup.4=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T,

S+h.sup.4+h.sup.5=(S.sub.1,S.sub.2,S.sub.3,S.sub.4).sup.T.

[0129] According to the above explanations, it follows directly from this that:

E.sub.01=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

E.sub.11=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

E.sub.21=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

E.sub.31=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

E.sub.41=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

E.sub.51=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

and

E.sub.12=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

E.sub.22=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

E.sub.32=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

E.sub.42=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

E.sub.52=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4),

[0130] FIG. 2 shows the generation of the correction signals v.sub.0.sup.cor or to v.sub.5.sup.cor based on the associated possibly defective bits v,; to v G and the signals E.sub.01 to E.sub.52:

v.sub.0.sup.cor=v.sub.0+E.sub.01+E.sub.12,

v.sub.1.sup.cor=v.sub.1+(E.sub.12vE.sub.11)+E.sub.22,

v.sub.2.sup.cor=v.sub.2+(E.sub.22vE.sub.21)+E.sub.32,

v.sub.3.sup.cor=v.sub.3+(E.sub.32vE.sub.31)+E.sub.42,

v.sub.4.sup.cor=v.sub.4+(E.sub.42vE.sub.41)+E.sub.52,

v.sub.5.sup.cor=v.sub.5+(E.sub.52vE.sub.51).

[0131] In this case, + again denotes the Exclusive Or operation (XOR) and v indicates the logic Or link (implemented in FIG. 2 by an OR gate). The above links are implemented in FIG. 2 by way of OR gates 121 to 125 and XOR gates (Exclusive Or gates) 131 to 136.

[0132] The signals E.sub.01 to E.sub.52 are indicated by way of example in FIG. 2 based on the components S.sub.1 to S.sub.4 of the error syndrome S, linked with the column vectors h.sup.0 to h.sup.5 of the H-matrix by way of NOR gates (NOT OR gates) 101 to 111, as also shown in equations (3) and (4).

[0133] In this case, the correction signals are determined for example by way of a NOR link between corresponding syndrome components or inverted syndrome components. Instead of the NOR link, other equivalent Boolean expressions (or gates) may also be used. By way of example, any of the following Boolean functions may be used: AND, OR, NOR (NOT OR), NAND (NOT AND). Inverters may also be used.

[0134] The Boolean functions AND, NAND, OR and NOR that may be used to determine the correction signals are Boolean functions having a determining value (what is called a controlling value, see also [6]).

[0135] The determining value of the functions AND and NAND is the value 0. If one of the variables on which the AND function depends adopts the value 0, then the value determined by the AND function is always 0. If one of the variables on which the NAND function depends adopts the value 0, then the value determined by the NAND function is always equal to 1.

[0136] The determining value of the functions OR and NOR is the value 1. If one of the variables on which the OR function depends adopts the value 1, then the value determined by the OR function is always equal to 1. If one of the variables on which the NOR function depends adopts the value 1, then the value determined by the NOR function is always equal to 0.

[0137] By way of example, the correction signal

E.sub.42=NOR(S.sub.1,S.sub.2,S.sub.3,S.sub.4)

from equation (4), instead of the NOR function, may also be implemented by way of the AND function in conjunction with inverters:

E.sub.42=AND(S.sub.1,S.sub.2,S.sub.3,S.sub.4)

The NOR link gives the value 1 for the population

[00012]$\left(\begin{array}{c}{\stackrel{\_}{S}}_1\\ S_2\\ {\stackrel{\_}{S}}_3\\ S_4\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right).$

since the result 0 is present only when all inputs of the NOR gate are equal to 0. For the components S.sub.1 and S.sub.3, this is ensured by way of inverters.

[0138] The AND link accordingly gives the value 1 for the population

[00013]$\left(\begin{array}{c}{S}_1\\ {\stackrel{\_}{S}}_2\\ S_3\\ {\stackrel{\_}{S}}_4\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right).$

since, in the case of the AND link, the value 1 is achieved only when all inputs of the AND gate are equal to 1.

[0139] It is pointed out that the circuit shown in FIG. 2 (and also in FIG. 3) should be understood to be exemplary. Other implementations, in particular using different gate logic, are also possible.

[0140] The signals E.sub.01 to E.sub.52 are binary values. In the present example, at most one of the signals E.sub.01 to E.sub.52 is equal to 1.

[0141] If a 1-bit error is present, one of the signals E.sub.01, E.sub.11, E.sub.21, E.sub.31, E.sub.41, E.sub.51 is equal to 1 and the 1-bit error is corrected. The bit v.sub.1 is thus for example corrected to a bit

v.sub.1.sup.cor=v.sub.1+1

when E.sub.11=1.

[0142] If an adjacent 2-bit error is present, one of the signals E.sub.12, E.sub.22, E.sub.32, E.sub.42, E.sub.52 is equal to 1 and the adjacent 2-bit error is corrected. The bit v.sub.2 is thus for example corrected to a bit

v.sub.2.sup.cor=c.sub.2+1

and a bit v.sub.3 is corrected to a bit

v.sub.3.sup.cor=v.sub.3+1

when E.sub.32=1 and an adjacent 2-bit error is present at the bit positions 2 and 3.

[0143] FIG. 3 shows a schematic arrangement for determining the signals E.sub.01 to E.sub.52 based on the sub-error syndromes

S.sub.1,S.sub.1,S.sub.2,S.sub.2,S.sub.3,S.sub.3,S.sub.4,S.sub.4

of the error syndrome S by way of inverters 301 to 304.

[0144] For each of the eleven signals E.sub.01 to E.sub.52 (for the sake of simplicity, only six of these signals are illustrated in FIG. 3), there is a NOR gate 311 to 316 that indicates, according to equations (3) and (4), the combination of sub-error syndromes on which the respective signal is based.

[0145] In FIG. 3, each sub-error syndrome S of the error syndrome S is provided once in non-inverted form as S.sub.j and once in inverted form as For each of the signals E.sub.01 to E.sub.52, a selection is made, according to the links shown in FIG. 3 for each sub-error syndrome, as to whether it contributes to the signal in its non-inverted form or in its inverted form. The selected sub-error syndromes are then linked via the NOR gates 311 to 316 to form one of the signals E.sub.01 to E.sub.52.

[0146] It is additionally pointed out that the correction signals may be determined simultaneously or at least partially simultaneously (in parallel or in a temporally overlapping manner), as also illustrated for example in present FIGS. 1 and 2.

BCH Code

[0147] The application of a 2-bit error correcting BCH code is discussed by way of example below.

[0148] The H-matrix of a 2-bit error correcting BCH code over a Galois field GF(2.sup.m) with the generator element a may be described for example as

[00014]$\begin{array}{cc}H=\left(h^0,h^1,.Math.,h^{n-1}\right)=\left(\begin{array}{c}{H}_1\\ H_2\end{array}\right)=\left(\begin{array}{cccccc}{}^0& {}^1& {}^2& {}^3& .Math.& {}^{n-1}\\ {}^0& {}^3& {}^6& {}^9& .Math.& {}^{3\left(n-1\right)}\end{array}\right)& \left(5\right)\end{array}$

In this case, H.sub.1 and H.sub.3 are sub-matrices of the H-matrix.

[0149] This is explained in [7] by way of example for m=4. Page 148 thereof shows what is called a parity check matrix, in which a is denoted by 1 in accordance with the one element of the Galois field. Page 149 above shows the parity check matrix in its binary form (with binary column vectors).

[0150] The values a in equation (5) may be interpreted as elements of the Galois field GF(2.sup.m) in its vector representation as m-component column vectors. The exponents of a should be interpreted modulo (2.sup.m1). The error syndrome

S=[S.sub.1,S.sub.3]

contains sub-error syndromes s.sub.1 and s.sub.3, which are determined as follows:

s.sub.1=H.sub.1.Math.v,(6)

s.sub.3=H.sub.3.Math.v.(7)

[0151] In this case, v again denotes the potentially defective binary vector. The error syndrome S has M=2 m components.

[0152] For an adjacent 2-bit error at the positions i and i+1, it holds that

s.sub.1=.sup.i+.sup.i+1=a.sup.i(1+)(8)

and

s.sub.3=.sup.3i+.sup.3i+3=a.sup.3i(1+.sup.3)(9)

It results from this that

[00015]$\begin{array}{cc}\frac{s_1^3}{s_3}=\frac{{\left(1+\right)}^3}{1+{}^3}& \left(10\right)\end{array}$

or

s.sub.1.sup.3(1+.sup.3)=s.sub.3(1+).sup.3.(11)

[0153] Equation (11) does not apply to a non-adjacent 2-bit error or to a 1-bit error.

[0154] For any 2-bit error, Si is always other than 0. In cases in which the denominator of the quotient of equation (10) or the denominator of one of the quotients of the following equations adopts the value 0, the respective reciprocal form may be used.

[0155] It is thus possible for a 2-bit correcting BCH code to correct adjacent 2-bit errors using just the sub-error syndrome s.sub.1 and then to check whether equation (11) is satisfied: If the equation is satisfied, then there are no non-adjacent 2-bit errors and also no 1-bit errors.

[0156] For a 2-bit error correcting BCH code, the ith and the i+1th bit are corrected when

s.sub.1+.sup.i+.sup.i+1=0(12)

and equation (11) holds.

[0157] In this case, it is sufficient to functionally link only one true subset of the m components of the error syndrome (from the 2.Math.m components), namely the m components of the sub-error syndrome s.sub.1, with the components of the columns a.sup.0, a.sup.1, . . . , a.sup.n1 of the submatrix H.sub.1 in order to determine correction signals for the different bit positions.

[0158] One exemplary approach for correcting possible defective (adjacent) bits may comprise the following steps:

[0159] 1. It is checked whether the condition according to equation (11)

s.sub.1.sup.3(1+.sup.3)=s.sub.3(1+).sup.3

is satisfied. In this case, the sub-error syndromes s.sub.1 and s.sub.3 are known from equations (6) and (7) and a is determined by the H-matrix according to equation (5). If this condition is not satisfied, no error correction takes place. If on the other hand the condition is satisfied, the following step is carried out.

[0160] 2. It is checked for the individual bit positions i whether the condition according to equation (12)

s.sub.1+.sup.i+.sup.i+1=0

is satisfied:

[0161] a) It is checked for the 0th bit position whether

s.sub.1+.sup.0+.sup.1=0

is satisfied. If it is, a correction at the bit positions 0 and 1 takes place. If it is not, no correction takes place.

[0162] b) It is checked for the 1st bit position whether

s.sub.1+.sup.1+.sup.2=0

is satisfied. If it is, a correction at the bit positions 1 and 2 takes place. If it is not, no correction takes place.

[0163] c) It is checked for the (n2)th bit position whether

s.sub.1+a.sup.n2+a.sup.n1=0

is satisfied. If it is, a correction at the bit positions (n2) and (n1) takes place. If it is not, no correction takes place.

[0164] It will be shown below that a 2-bit error for a 2-bit error correcting BCH code is adjacent when one of the equations (10) or (11) holds, that is to say

[00016]$\frac{s_1^3}{s_3}=\frac{{\left(1+\right)}^3}{1+{}^3}\mathrm{or}{s}_1^3\left(1+{}^3\right)={s_3\left(1+\right)}^3.$

[0165] A 2-bit error at the positions j and j+p is considered and it is shown that p=1 or p=1 is then satisfied and the error is necessarily adjacent.

[0166] For the 2-bit error under consideration, it holds that:

[00017]$s_1={}^j+{}^{j+p}={}^j\left(1+{}^p\right),$$s_3={}^{3j}+{}^{3j+3p}={}^{3j}\left(1+{}^{3p}\right)\mathrm{and}$$\frac{s_1^3}{s_3}=\frac{{\left(1+{}^p\right)}^3}{1+{}^{3p}}.$

[0167] According to the assumption that the errors with the distances 1 and p are not able to be distinguished, it holds that:

[00018]$\begin{array}{cc}\frac{{\left(1+\right)}^3}{1+{}^3}=\frac{{\left(1+{}^p\right)}^3}{1+{}^{3p}}.& \left(13\right)\end{array}$

With

[0168]
1+.sup.3=(1++.sup.2)(1+),(14)

1+.sup.3p=(1+.sup.p+.sup.2p)(1+.sup.p),(15)

(1+).sup.3=(1+.sup.2)(1+) and(16)

(1+.sup.p).sup.3=(1+.sup.2p)(1+.sup.p)(17)

the two sides of equation (13) may be represented as

[00019]$\frac{{\left(1+\right)}^3}{1+{}^3}=\frac{\left(1+{}^2\right)\left(1+\right)}{\left(1++{}^2\right)\left(1+\right)}=\frac{1+{}^2}{1++{}^2}$$\frac{{\left(1+{}^p\right)}^3}{1+{}^{3p}}=\frac{\left(1+{}^{2p}\right)\left(1+{}^p\right)}{\left(1+{}^p+{}^{2p}\right)\left(1+{}^p\right)}=\frac{1+{}^{2p}}{1+{}^p+{}^{2p}}$

and equation (13) thus becomes

[00020]$\begin{array}{cc}\frac{1+{}^2}{1++{}^2}=\frac{1+{}^{2p}}{1+{}^p+{}^{2p}}.& \left(18\right)\end{array}$

Multiplying this out gives

(1+.sup.2)(1+.sup.p+.sup.2p)=(1+.sup.2p)(1++.sup.2)

1+.sup.p+.sup.2p+.sup.2+.sup.p2+.sup.2p+2=1++.sup.2+.sup.2p+.sup.2p+1+.sup.2p+2

.sup.p+.sup.p+2=+.sup.2p+1

+.sup.p+.sup.p+2+.sup.2p+1=0

(+.sup.p)(1+.sup.p+1)=0

with the solutions p=1 and p=1.

[0169] Since p in the Galois field GF(2.sup.m) is considered modulo 2.sup.m1,

p=2.sup.m2

is also a solution to equation (19). In the cyclic code present here, a 2-bit error at the bit positions 0 and 2.sup.m2 is also an adjacent 2-bit error.

CITATIONS

[0170] [1] Okano, Imai: A construction method for high speed decoders using ROMs for Bose-Chadhuri-Hocquenhem and Reed Solomon Code, IEEE Trans. Comp. C36 (10), pages 1165 to 1171, 1987 [0171] [2] S. Lin, D. Costello: Error Control Coding, Prentice Hall, 1983, pages 153 to 169 [0172] [3] J Swoboda: Codierung zur Fehlerkorrektur and Fehlererkennung [Error correction and error detection coding], Oldenbourg-Verlag 1973, pages 85 to 89 [0173] [4] DE 10 2020 110 787 B3 [0174] [5] DE 10 2018 126 685 B3 [0175] [6] M. Abramovici et al.: Digital Systems Testing and Testable Design, Computer Science Press, 1990, page 59 [0176] [7] S. Lin, D. Costello: Error Control Coding, Prentice Hall, 1983, pages 148 and 149, Example 6.2