# Patent

## Title
Circuit arrangement and method for realizing check bit compacting for cross parity codes

## Abstract

A circuit arrangement for determining m check bits c1, . . . , cm for k data bits u1, . . . , uk is provided, wherein the circuit arrangement includes a first subcircuit and a second subcircuit. The first subcircuit has k binary inputs for inputting the k data bits u=u1, . . . , uk and M binary outputs for outputting M binary intermediate values z1, . . . , zM determined from the data bits. The second subcircuit is configured to transform the intermediate values z1, . . . , zM into the check bits c1, . . . , cm.

## Background
REFERENCE TO RELATED APPLICATION
This application claims priority to German application number 10 2013 219 088.3 filed on Sep. 23, 2013.
FIELD
The application relates to error detection, particularly error detection in semiconductor memories, and, specifically, to a circuit arrangement and a method for realizing check bit compacting for cross parity codes.
BACKGROUND
The prior art discloses the practice of correcting arbitrary 1-bit errors in binary sequences of a particular length n, for example by means of Hamming codes. This is described in Lin, S. and Costello, D. “Error Control Logic”, Prentice Hall, 1983, pp. 79-81, for example.
If, besides the correction of 1-bit errors, 2-bit errors are also recognized, it is possible to use what are known as Hsiao codes, see Lin, S. and Costello, D. “Error Control Coding”, Prentice Hall, 1983, pp. 499-502, for example.
For Hamming codes, the number m of check bits is approximately equal to m≈log2(k), when k is the number of data bits, so that n=k+m. The error correction is known to take place such that first of all a m-component error syndrome is determined from the possibly disrupted data bits and check bits. The m-dimensional error syndrome is then assigned the bit to be corrected that corresponds to the error syndrome by a decoder.
In the case of Hsiao codes, the error correction is likewise effected by the determination of an error syndrome and by a decoder. The number of check bits is one bit greater than for Hamming codes. If the syndrome has an uneven number of ones, a 1-bit error is corrected; if the syndrome has an even number of ones, a 2-bit error is recognized.
The error correction by means of Hamming codes and Hsiao codes is too slow for special applications.
Faster correction, for example of 1-bit errors, is permitted by cross parity codes (for example see: Pflanz, M., Walther, K., Galke, C. and Vierhaus, H., “On-line Error Detection and Correction in Storage Elements with Cross-Parity Check”, Proc. 8-th IOLTW, 2002, pp. 69-73 and Rubinoff, M., “N-dimensional Codes for Detecting and Correcting Multiple Errors”, Comm of the ACM, 1961, pp. 545-551). In the case of these codes, the k data bits are arranged in a rectangular or square array, sometimes also a multidimensional array. On account of the relatively simple description, we assume here that the data are notionally arranged in a rectangular or square two-dimensional array comprising rows and columns. Each data bit is then located precisely in one row and precisely in one column. By way of example, the check bits used can then be the row and column parities. If k is a square number, such as 64=82, then √{square root over (k)}=m′ row parities and √{square root over (k)}=m′ column parities can be used, so that in this case m=2·m′=2·√{square root over (k)} check bits are required.
If the total parity is furthermore used as an additional check bit, m=2·√{square root over (k)}+1 check bits are obtained. For 64 data bits, 17 check bits are then required.
In comparison with the number of 7 checks bits that is required for a Hamming code with 64 data bits, this number is large. To some extent, the error correction is much faster for cross parity codes than for Hamming codes, however.
1-Bit errors in memories or on buses are thus corrected by 1-bit-error-correcting codes. According to the prior art, this is thus usually effected by a Hamming code, if only the correction of 1-bit errors is required, or by a Hsiao code, if, besides the 1-bit error correction, 2-bit error detection is also necessary. If k is the number of data bits, approximately log(k) check bits are required for these codes. For Hamming and Hsiao codes, the number of check bits is an optimum.
The decoding that is effected by means of syndrome determination and decoder takes too long a time in various applications, on account of the circuit depth prescribed by the code.
Alternatively, the correction of 1-bit errors and the detection of 2-bit errors can, as already discussed, be performed by cross parity codes. In this case, the data bits are notionally arranged as a (usually) square array, and the check bits are the row parities and the column parities (and possibly also diagonal parities) of the array.
In this case, the number of check bits is approximately 2 √{square root over (k)}, which is much greater than log(k), particularly when k is relatively large. Thus, 17 check bits are required for a cross parity code with 64 data bits (with total parity included), while a Hsiao code requires only 8 check bits.
However, error correction by means of cross parity codes is much faster than by means of Hamming codes or Hsiao codes.
The error correction is particularly time-critical, since the data can be processed further only after they have been corrected.
In order to be able to observe the requisite clock times, some circuits have involved the use of cross parity codes at particular time-critical points, for example, which replace the initially provided Hsiao codes.
If the requisite time for correcting an error by means of a Hamming code is even just slightly too long to be able to be executed in the current clock cycle, it is possible for a cross parity code to be used instead of a Hamming code, said cross parity code being able to execute the requisite error correction in the current clock cycle.
However, a drawback in this case is that the number of check bits increases abruptly, even though there may be a need for just slight shortening of the time for the error correction. Thus, in the case of 64 data bits, for example, it is necessary to use 17 check bits for a cross parity code instead of the 7 check bits for a Hamming code, even though there may be a need for just a little shortening of the time for the error correction.
To date, there is only the option of choosing between Hamming or Hsiao codes and cross parity codes.
Thus, if the requisite clock time means that it is necessary to decide on a cross parity code, the number of check bits and hence the hardware complexity rise abruptly. This is the case even if an Hsiao code requires a time involvement for decoding that is only just above the necessary clock time.
It would be desirable to determine codes that can be adjusted to suit the requisite clock time for the decoding and at the same time have as small a number of check bits as possible.
SUMMARY
In one embodiment of the present disclosure it is a goal to provide improved concepts for error detection.
A circuit arrangement according to claim 1, a decoder according to claim 16, and a method according to claim 20 are provided.
A circuit arrangement for determining m check bits c1, . . . , cm for k data bits u1, . . . , uk is provided. The circuit arrangement comprises a first subcircuit having k binary inputs for inputting the k data bits u=u1, . . . , uk and M binary outputs for outputting M binary intermediate values z1, . . . , zM determined from the data bits, and a second subcircuit for transforming the intermediate values z1, . . . , zM into the check bits c1, . . . , cm, where m<M. The first subcircuit is designed to determine the intermediate values from the data bits such that there is an association between a determined pair of intermediate values z1,lj,z2,mj for each data bit uj that is to be corrected, so that a change in the pair z1,lj,z2,mj to z1,lj,z2,mj when only one data bit from the data bits {u1, . . . , uk} has changed to its negated value indicates that the j-th data bit uj has changed to ūj, wherein the second subcircuit is designed such that it transforms the intermediate values into check bits such that the check bits associated with the intermediate values determined from the data bits u1, . . . , ui, . . . , uk and the check bits associated with the intermediate values determined from the data bits inverted in a respective bit from the data bits that are to be corrected differ in pairs, where m<M and M<k.
By way of example, in one specific embodiment, the intermediate values and/or the check bits determined from the intermediate values by the second subcircuit may each be check bits from an at least 1-bit-error-correcting code.
Furthermore, a decoder for determining a subset of data bits that are to be corrected on the basis of m check bits c1, . . . , cm is provided, wherein the m check bits c1, . . . , cm are determined by a circuit arrangement for determining the check bits c1, . . . , cm for k data bits u1, . . . , uk. The decoder comprises a third subcircuit, a fourth subcircuit and a fifth subcircuit. The third subcircuit Ssyndrome is designed to form a subset of differences Δc1=c1⊕c1′, . . . , Δcm=cm⊕cm′ for the correct check bits c1, . . . , cm and the possibly erroneous check bits c1′, . . . , cm′, wherein these differences are determined from possibly erroneous data bits u1, . . . , uk and possibly erroneous check bits c1′, . . . , cm′. The fourth subcircuit Decomp is designed to form a subset of differences Δz1=z1⊕z1′, . . . , ΔzM=zM⊕zM′ from error-free intermediate values z1, . . . , zM and possibly erroneous intermediate values z1′, . . . , zM′, the differences Δz1, . . . ΔzM being determined from the differences in the intermediate values Δc1, . . . , Δcm. The fifth subcircuit Corr is designed to determine a corrected data bit ujcor. In this case, the fifth subcircuit Corr contains at least three binary inputs for inputting a possibly erroneous data bit u′j and for inputting two differences Δz1,lj,Δz2,rj for intermediate values and a binary output for outputting the corrected data bit ujcor, wherein z1,lj belongs to a first group of intermediate values and z2,rj belongs to a second group of intermediate values, so that when uj changes to uj and also no error occurs, z1,lj changes to z1,lj and z2,rj changes to z2,rj and the fifth subcircuit Corr is designed such that it outputs ujcor=uj⊕1 when Δz1,lj=Δz2,rj=1.
In addition, a system is provided. The system comprises the circuit arrangement described above for determining m check bits c1, . . . , cm for k data bits, and the decoder described above for determining a subset of data bits that are to be corrected.
Furthermore, a method for determining m check bits c1, . . . , cm for k data bits u1, . . . , uk is provided. The method comprises:
determination of M intermediate values from the k data bits, so that there is an association between a determined pair of intermediate values z1,lj,z2,mj for each data bit uj that is to be corrected, and:
transformation of the intermediate values z1, . . . , zM into the check bits c1, . . . , cm.
A change in the pair z1,lj,z2,mj to z1,lj,z2,mj when only one data bit from the data bits {u1, . . . , uk} has changed to its negated value indicates that the j-th data bit uj has changed to ūj, wherein the intermediate values are transformed into check bits such that the check bits associated with the intermediate values determined from the data bits u1, . . . , ui, . . . , uk and the check bits associated with the intermediate values determined from the data bits inverted in a respective bit from the data bits that are to be corrected differ in pairs, where m<M and M<k.
In addition, a method for determining a subset of data bits that are to be corrected on the basis of m check bits c1, . . . , cm is provided, wherein the method for determining the subset of the data bits that are to be corrected comprises:
formation of a subset of differences Δc1=c1⊕c1′, . . . , Δcm=cm⊕cm′ for the correct check bits c1, . . . , cm and the possibly erroneous check bits c1′, . . . , cm′, these differences being determined from possibly erroneous data bits u1′, . . . , uk′ and possibly erroneous check bits c1′, . . . , cm′,
formation of a subset of differences Δz1=z1⊕z1′, . . . , ΔzM=zM⊕zM′ from error-free intermediate values z1, . . . , zM and possibly erroneous intermediate values z1′, . . . , zM′, the differences Δz1, . . . ΔzM being determined from the differences in the intermediate values Δc1, . . . , Δcm, and
determination of a corrected data bit ujcor on the basis of a possibly erroneous data bit u′j and two differences Δz1,lj,Δz2,rj in intermediate values, wherein z1,lj belongs to a first group of intermediate values and z2,rj belongs to a second group of intermediate values, so that when uj changes to uj and no further error occurs, z1,lj changes to z1,lj and z2,rj changes to z2,rj and wherein ujcor=uj⊕1, when Δz1,lj=Δz2,rj=1.
In addition, a computer program having a program code for performing one of the methods described above is provided.
Embodiments overcome or reduce the disadvantages of known solutions and allow the number of check bits from a code to be matched in the best possible way to the required speed of decoding.
In one embodiment, this involves transformation or compacting of, by way of example, M check bits for a first code C1 with k data bits u1, . . . , uk into m check bits c1, . . . , cm of a code C2 with the same data bits that is derived from the first code. In order to clarify that check bits from the second code are derived from the check bits of the first code, the M check bits of the first code are referred to as intermediate values z1, . . . , zM.
If both C1 and the code C2 derived therefrom are an at least 1-bit-error-correcting code, then a change in the intermediate values z1, . . . , zM and a change in the check bits c1, . . . , cm correspond on a one-to-one basis to a 1-bit error in a data bit, for example. As stated, the intermediate values z1, . . . , zM are transformed into check bits c1, . . . , cm, the transformation being effected according to one embodiment such that a change in the check bits c1, . . . , cm corresponds to a change in the intermediate values z1, . . . , zM that is caused by a 1-bit error. This property is particularly advantageous for the decoding and error correction.
For the decoding, it is then first of all possible to determine the relevant change in the intermediate values from a present change in the check bits c1, . . . , cm and then to realize a simple correction circuit in line with the first code C1 from the change in the intermediate values. M>m. Depending on the degree of compacting of the intermediate values into check bits, i.e. depending on the realized difference between M and m, the number of requisite check bits is decreased from M to m to a greater or lesser extent. In this case, heavier compacting requires a longer time that is necessary for compacting and decoding and particularly for error correction. It is thus possible to match the required involvement of check bits and the required speed for error correction to one another, which is advantageous.
In this case, the first code C1 may be a cross parity code, with row and column parities being used as intermediate values z1, . . . , zM, for example. Particularly for 1-bit errors in the data bits, it is possible for simple and fast decoders and error correctors to be specified for cross parity codes.
The intermediate values, which are row and column parities of the data bits arranged as an array in the case of a cross parity code, are transformed or compacted into check bits of the code used according to one embodiment.
A 1-bit error in the data bits is then reflected in a change in the check bits c1, . . . , cm, from which change a change in the intermediate values, i.e. a change in the row and column parities, e.g. the change in a bit of the row parities and in a bit of the column parities, is determined. From the changes in the bits of the intermediate values, the correction value for the corrupted data bit is then determined in a simple manner, in this case by ANDing the relevant row and column parities, as in the case of a cross parity code.
It is not necessary for the first code to be a cross parity code. In other embodiments, the first code is not a cross parity code but rather a different code, such as a Latin Square Code (see [6]), e.g. an orthogonal Latin Square Code (see [6]).
According to some embodiments, the first code has a first group of intermediate values and a second group of intermediate values, the intermediate values being determined from the data bits such that a 1-bit error in a data bit has an association between a determined pair of intermediate values, wherein the first intermediate value belongs to the first group and the second intermediate value belongs to the second group of intermediate values. If the relevant data bit changes, e.g. erroneously, then the values of the intermediate values associated with this data bit change.
In some embodiments, the check bits of the cross parity code are compacted during the coding and decompacted during the decoding and error correction, so that—in comparison with the cross parity code—fewer check bits need to be stored.
The degree of compacting firstly determines how many check bits are required and secondly determines how much time the decoding requires. Heavier compacting corresponds to a longer correction time.
It is particularly advantageous that some embodiments allow (step-by-step) scaling between the Hsiao code and the cross parity code, and the determination of codes that meet the necessary time criteria for the error correction with as small a number of check bits as possible. This means that the requisite hardware complexity can be matched to the demanded time limit.
In principle, it is also possible for 2-bit correcting codes to be matched to requisite time limits of the clock.
Some embodiments are based on a principle that is described here for 1-bit errors in the data bits. A description of the correction of 2-bit errors and the detection of 2-bit and 3-bit errors is presented further below.
In general, the check bits of the cross parity code are considered to be intermediate values from which the check bits of the sought code are formed by compacting. This allows the number of check bits that need to be stored to be reduced.
In this case, simple, relatively low compacting allows simple decompacting that can be performed quickly. More complex, heavier compacting generally requires more time for decompacting. Depending on the time available for decoding, it is possible, within certain limits, for the degree of compacting and hence the involvement for storing check bits to be matched to the time conditions.
For compacting, the check bits of a relevant cross parity code are divided into groups such that each 1-bit error in the data bits changes precisely one bit into two groups of check bits of the cross parity code. By way of example, the check bits in such groups are the row parities and the column parities of the intended data array. (For the purpose of simpler description, only groups of the row and column parities are considered to be groups of check bits from the cross parity code in this case, although other groups of check bits are also possible). The row parities and the column parities are the intermediate values that are compacted into check bits of the sought code. This decreases the number of check bits required in comparison with the cross parity code.
The compacting is effected such that changes in the row parities that correspond to a 1-bit error in the data bits reflect changes in the associated check bits, so that the changes in the row parities are again determined from the changes in the check bits. The column parities are handled in the same way. In this case, the compacting is performed in linear or else nonlinear fashion. After the check bits have been decompacted into the intermediate values, which are the check bits of a cross parity code, the correction is very simple, as in the case of a cross parity code.
The procedure is described for the correction of 1-bit errors, the correction of 1-bit errors and the detection of 2-bit errors, the correction of 2-bit errors and the correction of 2-bit errors and the detection of 3-bit errors.
In order to make the description as simple and clear as possible, it is assumed here that the 1-bit errors arise only in the region of the useful data bits.
For a simple example embodiment, the check bits of a cross parity code are compacted for 16 useful data bits. Notionally, these 16 useful data bits are distributed over an array containing 4 rows and 4 columns.




Each of these rows and columns is protected by a parity, which is the intermediate values in the text below. The parities of the rows are denoted by pi and those of the columns are denoted by qj, where 1≦i,j≦4. The equations for calculating the parities are

p1=u01+u02+u03+u04 

p2=u05+u06+u07+u08 

p3=u09+u10+u11+u12 

p4=u13+u14+u15+u16 

q1=u01+u05+u09+u13 

q2=u02+u06+u10+u14 

q3=u03+u08+u11+u15 

q4=u04+u08+u12+u16 

It should be noted that the addition is addition in binary, i.e. is addition modulo 2.

From the equations it is possible to read that each useful data bit is used in the calculation of precisely one row parity and one column parity. Therefore, by way of example, if an error occurs in one bit from the useful data bits, for example u5, then only the results of the equations for p2 and q1 change. The error can thus be located when decoding using the row and column parities and can easily be corrected by an AND gate.
For compacting, a total of two groups G1 and G2 are formed and the parities, referred to as intermediate values in the text below, are distributed over these groups. The row intermediate values pi are associated with group G1 and the column intermediate values qj are associated with the group G2, where 1≦i,j≦4

G1={p1,p2,p3,p4}

G2={q1,q2,q3,q4}

As a final step, the intermediate values p1, p2, p3, p4, q1, q2, q3 and q4 from the groups G1 and G2 are transformed into the check bits c1,1, c2,1, c3,1, c1,2, c2,2 and c3,2 of the codes used. In both groups, the 4 intermediate values are compacted onto 3 check bits in each case. This compacting is performed such that the check bits c1,j, c2,j, c3,j associated with the intermediate values z1,j, z2,j, z3,j, z4,j, where zi,jεGj, 1≦i≦4, jε{1,2}, from the intermediate values inverted in a respective bit differ from one another in pairs.
The equations used for calculating these six check bits may be the following equations

c1,1=p1+p4 

c2,1=p2+p4 

c3,1=p3+p4 

For c1,1, the intermediate values p1 and p4 are added. In addition, for c2,1, the intermediate values p2 and p4 are added and for c3,1, the intermediate values p3 and p4 are added. Similarly, the intermediate values from the second group G2, are compacted

c1,2=q1+q4 

c2,2=q2+q4 

c3,2=q3+q4 

The individual equations for compacting the intermediate values can also be regarded as a compaction matrix in the form of a check matrix H from a Hisao code.




  H
  =
  
    (
    
      
        
          1
        
        
          0
        
        
          0
        
        
          1
        
      
      
        
          0
        
        
          1
        
        
          0
        
        
          1
        
      
      
        
          0
        
        
          0
        
        
          1
        
        
          1
        
      
    
    )
  




In general, in this example, z4,j is added to each of z1j, z2,j and z3,j, where zi,jεGj, 1≦i≦4, jε{1,2}. The following list shows the association of the intermediate values with the individual check bits. In this case, the following is always true

zi,jz2,jz3,jz4,j→c1,jc2,jc3,j 

The mappings are



















0000 → 000
0100 → 010
1000 → 100
1100 → 110



0001 → 111
0101 → 101
1001 → 011
1101 → 001



0010 → 001
0110 → 011
1010 → 101
1110 → 111



0011 → 110
0111 → 100
1011 → 010
1111 → 000










It can be seen from the mappings that the check bits associated with the intermediate values and the check bits associated with the intermediate values inverted in one bit differ from one another in pairs. By way of example, the intermediate value 0000 is transformed into 000, while 0001 is transformed into 111, 0010 is transformed into 001, 0100 is transformed into 010 and 1000 is transformed into 100.
A further advantage of this variant is the decoder. For 1-bit error correction, it is not necessary, as in the case of normal Hsiao code, for the complete syndrome to be taken into account for the correction of a single data bit. Instead, it is possible to use just parts of this syndrome, as is usual in the case of cross parity code.
The procedure for decoding may now be that first of all the changes in the bits c1,1, c2,1, c3,1, c1,2, c2,2, c3,2 are decompacted to produce the changes in the parities Δp1, . . . , Δp4, Δq1, . . . , Δq4. For decompacting the syndrome, it is possible to use the following equations

Δp1=Δc1,1Λ(Δc2,1ΛΔc3,1)

Δp2=Δc2,1Λ(Δc1,1ΛΔc3,1)

Δp3=Δc3,1Λ(Δc1,1ΛΔc2,1)

Δp4=Δc1,1ΛΔc2,1ΛΔc3,1 

Δq1=Δc1,2Λ(Δc2,2ΛΔc3,2)

Δq2=Δc2,2Λ(Δc1,2ΛΔc3,2)

Δq3=Δc3,2Λ(Δc1,2ΛΔc2,2)

Δp4=Δc1,2ΛΔc2,2ΛΔc3,2 

For correcting a single data bit, the syndrome component of the row and the column in which the data bit is logically located can be logically combined by an AND gate, and the result can be linked to the read data bit using an XOR gate. This is shown in FIG. 8 for the correction of the bit u2.
The equations for correction of the data bits are therefore as follows



  
    
      u
      1
    
    =
    
      
        u
        1
        ′
      
      +
      
        (
        
          Δ
          ⁢
          
            
          
          ⁢
          
            p
            1
          
          ⁢
          ΛΔ
          ⁢
          
            
          
          ⁢
          
            q
            1
          
        
        )
      
    
  




  
    
      u
      2
    
    =
    
      
        u
        2
        ′
      
      +
      
        (
        
          Δ
          ⁢
          
            
          
          ⁢
          
            p
            1
          
          ⁢
          ΛΔ
          ⁢
          
            
          
          ⁢
          
            q
            2
          
        
        )
      
    
  




  
    
      u
      3
    
    =
    
      
        u
        3
        ′
      
      +
      
        (
        
          Δ
          ⁢
          
            
          
          ⁢
          
            p
            1
          
          ⁢
          ΛΔ
          ⁢
          
            
          
          ⁢
          
            q
            3
          
        
        )
      
    
  




  ⋮




  
    
      u
      16
    
    =
    
      
        u
        16
        ′
      
      +
      
        (
        
          Δ
          ⁢
          
            
          
          ⁢
          
            p
            4
          
          ⁢
          ΛΔ
          ⁢
          
            
          
          ⁢
          
            q
            4
          
        
        )
      
    
  



This kind of reduction of the check bits can be performed for cross parity codes for 1-bit error correction and 2-bit error detection and also for cross parity codes for 2-bit error correction and 3-bit error detection.
Further embodiments can be found in the dependent claims.



BRIEF DESCRIPTION OF THE DRAWINGS
Embodiments are now described with reference to the drawings.
The illustrations of the drawings are as follows:
FIG. 1 shows a circuit arrangement according to an embodiment,
FIG. 2 shows a circuit arrangement for forming intermediate values and check bits according to an embodiment,
FIG. 3A shows a circuit arrangement with overlapping groups of intermediate values according to an embodiment,
FIG. 3B shows a circuit arrangement with disjoint groups of intermediate values according to an embodiment,
FIG. 4 shows a circuit arrangement with 16 useful data bits and 7 check bits according to an embodiment,
FIG. 5 shows an implementation of the first subcircuit SZw for forming intermediate values with 16 useful data bits, according to an embodiment,
FIG. 6 shows a decoder for correcting data bits according to an embodiment,
FIG. 7 shows a system according to an embodiment, comprising a circuit arrangement and a decoder for determining a subset of data bits that are to be corrected, and
FIG. 8 shows an AND gate and an XOR gate, with the correction of a single data bit involving the syndrome component of the row and column in which the data bit is logically located being logically combined by the AND gate and the result being linked to the read data bit by means of the XOR gate.



DETAILED DESCRIPTION
FIG. 1 shows a circuit arrangement 1 for determining m check bits c1, . . . , cm for k data bits u1, . . . , uk according to an embodiment.
The circuit arrangement 1 comprises a first subcircuit 19 having k binary inputs for inputting the k data bits u=u1, . . . , uk and M binary outputs for outputting M binary intermediate values z1, . . . , zM determined from the data bits.
In addition, the circuit arrangement 1 comprises a second subcircuit 110 for transforming the intermediate values z1, . . . , zM into the check bits c1, . . . , cm, where m<M.
The first subcircuit 19 is designed to determine the intermediate values from the data bits such that there is an association between a determined pair of intermediate values z1,lj,z2,mj for each data bit uj that is to be corrected, so that a change in the pair z1,lj,z2,mj into z1,lj,z2,mj when only one data bit from the data bits {u1, . . . , uk} has changed to its negated value indicates that the j-th data bit uj has changed to ūj.
The second subcircuit 110 is designed such that it transforms the intermediate values into check bits such that the check bits associated with the intermediate values z1(u1, . . . , ui, . . . , uk), . . . , zM(u1, . . . , ui, . . . , uk) determined from the data bits u1, . . . , ui, . . . , uk and the check bits associated with the intermediate values determined from the data bits inverted in a respective bit from the data bits that are to be corrected differ in pairs, where m<M and M<k.
A few principles that are relevant to at least some of the embodiments will first of all be provided below.
Errors, that is to say erroneous bits in a binary sequence, for example, can be recognized and corrected using error recognizing and error correcting codes. By way of example, the use of Hamming codes and Hsiao codes is known.
A code C can be used to code data bits u=u1, . . . , uk into a code word v=v1, . . . , vn. In this case, the binary sequence u of the data bits can also be regarded as a k-component data vector and the code word v can also be regarded as an n-component code vector. For a linear code, it is possible for a data vector u=u1, . . . , uk to be coded into a corresponding code vector v=v1, . . . , vn using a generator matrix G with k rows and n columns, i.e. with a (k,n) matrix G such that

v=u·G  (1)

is determined. In this case, u and v are row vectors here. Vectors are known to be able to be presented both as row vectors and as column vectors. If a matrix is multiplied by a vector from the left, the vector is a row vector and the result of the multiplication is likewise a row vector. If a matrix is multiplied by a vector from the right, the vector is a column vector and the result of the modification is likewise a column vector. It is then clear from the context whether a vector can be regarded as a row vector or a column vector.

If the aim is particularly to point out that a vector w is presented as a column vector, then it needs to be denoted by wT.
Error correction and error detection can take place using a H matrix H, which is an (in, n) matrix where m=n−k.
If a code vector v=v1, . . . , vn is determined from a data vector u=u1, . . . , uk in accordance with equation (1) and if the bits of this vector are disrupted, for example by alpha radiation, to produce an erroneous vector v′=v1′, . . . , vn′, then an error syndrome s=s1, . . . , sm may be determined as

s=H·v′  (2).

In this case, the H matrix H is determined such that, for a code word v,

0=H·v.  (3).

If v′ and v differ by an error vector e=e1, . . . , en, so that

e=e1, . . . , en=v1+v1′, . . . , vn+vn′  (4),

then

s=H·e.  (5).

If C is a 1-bit-error-correcting code, a different error syndrome s1, s2, . . . , sn is associated with each 1-bit error, i.e. each of the n error vectors [1, 0, . . . , 0], [0, 1, 0, . . . , 0], . . . , [0, . . . , 0, 1].
A decoder can then associate the relevant bit that needs to be corrected or to be inverted with each of the error syndromes s1, s2, . . . , sn.
If C is a 2-bit error correcting code, each 1-bit error and each 2-bit error has a different associated error syndrome.
If the code C is a Hamming code, all the columns of the H matrix differ in pairs. If n=7, for example, then the H matrix may be in the form




  
    
      
        H
        =
        
          
            (
            
              
                
                  1
                
                
                  0
                
                
                  0
                
                
                  1
                
                
                  1
                
                
                  0
                
                
                  1
                
              
              
                
                  0
                
                
                  1
                
                
                  0
                
                
                  1
                
                
                  0
                
                
                  1
                
                
                  1
                
              
              
                
                  0
                
                
                  0
                
                
                  1
                
                
                  0
                
                
                  1
                
                
                  1
                
                
                  1
                
              
            
            )
          
          =
          
            
              (
              
                
                  I
                  3
                
                ,
                
                  P
                  
                    3
                    ,
                    4
                  
                  T
                
              
              )
            
            .
          
        
      
    
    
      
        (
        6
        )
      
    
  




The H matrix has 7 columns that all differ in pairs. The first three columns form a 3-dimensional unit matrix I3. The next four columns form a (3,4) matrix P3,4T.
An associated G matrix G is




  
    
      
        
          G
          =
          
            
              (
              
                
                  
                    1
                  
                  
                    1
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    1
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                
                
                  
                    1
                  
                  
                    1
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                
              
              )
            
            =
            
              (
              
                
                  P
                  
                    4
                    ,
                    3
                  
                
                ,
                
                  I
                  4
                
              
              )
            
          
        
        ,
      
    
    
      
        (
        7
        )
      
    
  




wherein the first three columns form the matrix P4,3 and the next four columns form the four-dimensional unit matrix I4. In this case, P3,4T is the transposed matrix for the matrix P4,3.

For the Hamming code under consideration, each of the seven 1-bit errors, i.e. including each of the seven error vectors [1,0,0,0,0,0,0], [0,1,0,0,0,0,0], [0,0,1,0,0,0,0], [0,0,0,1,0,0,0], [0,0,0,0,1,0,0], [0,0,0,0,0,1,0], [0,0,0.0,0,0,1], has an associated dedicated error syndrome [1,0,0]T, [0,1,0]T, [0,0,1]T, [1,1,0]T, [1,0,1]T, [0,1,1]T, [1,1,1]T. A decoder then determines the bit that is to be corrected from the syndrome.
If the error syndrome is equal to [1,0,0]T, for example, then v′1 is to be corrected to v1′=v1′+1. If the error syndrome is equal to [1,1,1]T, then v′7 is to be corrected to v7=v7′+1.
If the code C is a Hsiao code, then all the columns of the H matrix differ in pairs, and each column of the H matrix has an uneven number of ones. If n=8, the H matrix for a Hsiao code may be in the form




  
    
      
        
          H
          =
          
            
              (
              
                
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    1
                  
                  
                    1
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    1
                  
                  
                    0
                  
                  
                    1
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    1
                  
                  
                    1
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    1
                  
                  
                    1
                  
                  
                    1
                  
                
              
              )
            
            =
            
              (
              
                
                  I
                  4
                
                ,
                
                  P
                  
                    4
                    ,
                    4
                  
                  T
                
              
              )
            
          
        
        ,
        .
      
    
    
      
        (
        8
        )
      
    
  




The first four columns form the 4-dimensional unit matrix I4 and the next columns form the matrix P4,4T.
If a 2-bit error now occurs, it has a corresponding error vector with two ones. The associated error syndrome is obtained as a component-by-component (XOR) sum of two columns of the H matrix. Since each column has an uneven number of ones, the sum of two columns has an even number of ones, and the error syndrome for a 2-bit error can therefore be distinguished from all the error syndromes for a 1-bit error, since these have an uneven number of ones.
If C is a cross parity code, the data bits can notionally be arranged as a rectangular array. If the number k of data bits is a square number, e.g. k=16=42, then a 4×4 array comprising four rows and four columns can be formed, as illustrated in (9),




  
    
      
        
          
            
              
                u
                1
              
            
            
              
                u
                2
              
            
            
              
                u
                3
              
            
            
              
                u
                4
              
            
          
          
            
              
                u
                5
              
            
            
              
                u
                6
              
            
            
              
                u
                7
              
            
            
              
                u
                8
              
            
          
          
            
              
                u
                9
              
            
            
              
                u
                10
              
            
            
              
                u
                11
              
            
            
              
                u
                12
              
            
          
          
            
              
                u
                13
              
            
            
              
                u
                14
              
            
            
              
                u
                15
              
            
            
              
                u
                16
              
            
          
        
        =
        
          
            
              
                
                  u
                  11
                
              
              
                
                  u
                  12
                
              
              
                
                  u
                  13
                
              
              
                
                  u
                  14
                
              
            
            
              
                
                  u
                  21
                
              
              
                
                  u
                  22
                
              
              
                
                  u
                  23
                
              
              
                
                  u
                  24
                
              
            
            
              
                
                  u
                  31
                
              
              
                
                  u
                  32
                
              
              
                
                  u
                  33
                
              
              
                
                  u
                  34
                
              
            
            
              
                
                  u
                  41
                
              
              
                
                  u
                  42
                
              
              
                
                  u
                  43
                
              
              
                
                  u
                  44
                
              
            
          
          .
        
      
    
    
      
        (
        9
        )
      
    
  




In this case, however, it is not necessary for the data bits, in this case the bits u1, . . . , u16, to be arranged in the specific manner illustrated in (9).
A further possible arrangement of the data bits as a 4×4 array, which is produced from the arrangement (9) by interchanging data bits, is illustrated in (10).




  
    
      
        
          
            
              
                u
                1
              
            
            
              
                u
                11
              
            
            
              
                u
                10
              
            
            
              
                u
                6
              
            
          
          
            
              
                u
                16
              
            
            
              
                u
                3
              
            
            
              
                u
                2
              
            
            
              
                u
                12
              
            
          
          
            
              
                u
                13
              
            
            
              
                u
                4
              
            
            
              
                u
                9
              
            
            
              
                u
                5
              
            
          
          
            
              
                u
                7
              
            
            
              
                u
                15
              
            
            
              
                u
                8
              
            
            
              
                u
                14
              
            
          
        
        =
        
          
            
              
                
                  u
                  11
                
              
              
                
                  u
                  12
                
              
              
                
                  u
                  13
                
              
              
                
                  u
                  14
                
              
            
            
              
                
                  u
                  21
                
              
              
                
                  u
                  22
                
              
              
                
                  u
                  23
                
              
              
                
                  u
                  24
                
              
            
            
              
                
                  u
                  31
                
              
              
                
                  u
                  32
                
              
              
                
                  u
                  33
                
              
              
                
                  u
                  34
                
              
            
            
              
                
                  u
                  41
                
              
              
                
                  u
                  42
                
              
              
                
                  u
                  43
                
              
              
                
                  u
                  44
                
              
            
          
          .
        
      
    
    
      
        (
        10
        )
      
    
  




The arrangement (10) is obtained from the arrangement (9) by interchanging or permutating the indices of the data bits in accordance with the permutation π, where




  
    
      
        π
        =
        
          
            (
            
              
                
                  1
                
                
                  2
                
                
                  3
                
                
                  4
                
                
                  5
                
                
                  6
                
                
                  7
                
                
                  8
                
                
                  9
                
                
                  10
                
                
                  11
                
                
                  12
                
                
                  13
                
                
                  14
                
                
                  15
                
                
                  16
                
              
              
                
                  1
                
                
                  11
                
                
                  10
                
                
                  6
                
                
                  16
                
                
                  3
                
                
                  2
                
                
                  12
                
                
                  13
                
                
                  4
                
                
                  9
                
                
                  5
                
                
                  7
                
                
                  15
                
                
                  8
                
                
                  14
                
              
            
            )
          
          .
        
      
    
    
      
        (
        11
        )
      
    
  




If 8 data bits u1, . . . , u8 are existent, it is possible to form a 3×3 array, as shown in (12).




  
    
      
        
          
            
              
                u
                1
              
            
            
              
                u
                2
              
            
            
              
                u
                3
              
            
          
          
            
              
                u
                4
              
            
            
              
                u
                5
              
            
            
              
                u
                6
              
            
          
          
            
              
                u
                7
              
            
            
              
                u
                8
              
            
            
              0
            
          
        
        =
        
          
            
              
                
                  u
                  1
                
              
              
                
                  u
                  2
                
              
              
                
                  u
                  3
                
              
            
            
              
                
                  u
                  4
                
              
              
                
                  u
                  5
                
              
              
                
                  u
                  6
                
              
            
            
              
                
                  u
                  7
                
              
              
                
                  u
                  8
                
              
              
                
                  
                
              
            
          
          =
          
            
              
                
                  
                    u
                    11
                  
                
                
                  
                    u
                    12
                  
                
                
                  
                    u
                    13
                  
                
              
              
                
                  
                    u
                    21
                  
                
                
                  
                    u
                    22
                  
                
                
                  
                    u
                    23
                  
                
              
              
                
                  
                    u
                    31
                  
                
                
                  
                    u
                    32
                  
                
                
                  
                    
                  
                
              
            
            .
          
        
      
    
    
      
        (
        12
        )
      
    
  




In this case, a constant value 0 can be added as element u9, or it is also possible for a further element not to be added, in which case the relevant space in the array is simply not used.
In (12), the data bits u1,u2,u3 form the first row, the data bits u4,u5,u6 form the second row and the data bits u7,u8,0 or u7,u8 form the third row of the array.
A further option for arranging the data bits u1, . . . , u8 as a 3×3 array is shown in (13):




  
    
      
        
          
            
              
                u
                1
              
            
            
              
                u
                2
              
            
            
              
                u
                3
              
            
          
          
            
              
                
              
            
            
              
                u
                7
              
            
            
              
                u
                8
              
            
          
          
            
              
                u
                6
              
            
            
              
                u
                5
              
            
            
              
                u
                4
              
            
          
        
        .
      
    
    
      
        (
        13
        )
      
    
  




In (13), the data bits u1,u2,u3 form the first row, the data bits u7,u8 form the second row and the data bits u6,u5,u4 form the third row. Accordingly, the first column comprises u1,u6, the second column comprises u2,u7,u5 and the third column comprises u3,u8,u4.
For 12 data bits u1, . . . , u12, (14) shows a possible arrangement as a rectangular 4×3 array,




  
    
      
        
          
            
              
                u
                1
              
            
            
              
                u
                2
              
            
            
              
                u
                3
              
            
          
          
            
              
                u
                4
              
            
            
              
                u
                5
              
            
            
              
                u
                6
              
            
          
          
            
              
                u
                7
              
            
            
              
                u
                8
              
            
            
              
                u
                9
              
            
          
          
            
              
                u
                10
              
            
            
              
                u
                11
              
            
            
              
                u
                12
              
            
          
        
        =
        
          
            
              
                
                  u
                  11
                
              
              
                
                  u
                  12
                
              
              
                
                  u
                  13
                
              
            
            
              
                
                  u
                  21
                
              
              
                
                  u
                  22
                
              
              
                
                  u
                  23
                
              
            
            
              
                
                  u
                  31
                
              
              
                
                  u
                  32
                
              
              
                
                  u
                  33
                
              
            
            
              
                
                  u
                  41
                
              
              
                
                  u
                  42
                
              
              
                
                  u
                  43
                
              
            
          
          .
        
      
    
    
      
        (
        14
        )
      
    
  




When a cross parity code is applied, the check bits formed can be row parities and column parities.
For the array shown in (9), the row parities p1,p2,p2,p4 where

p1=u1+u2+u3+u4 

p2=u5+u6+u7+u8 

p3=u9+u10+u11+u12 

p4=u13+u14+u15+u16 

and the column parities q1,q2,q3,q4 where

q1=u1+u5+u9+u13 

q2=u2+u6+u10+u14 

q3=u3+u7+u11+u15 

q4=u4+u8+u12+u16 

may be formed.

In addition, the total parity

P=u1+u2+ . . . +u16 

may be formed.

For the array shown in (10), the row parities p1, p2, p3, p4 are equal to

p1=u1+u11+u10+u6 

p2=u16+u3+u2+u12 

p3=u13+u4+u9+u5 

p4=u7+u15+u8+u14 

and the column parities q1,q2,q3,q4 are equal to

q1=u1+u16+u13+u7 

q2=u11+u3+u4+u15 

q3=u10+u2+u9+u8 

q4=u6+u12+u5+u14.

The row parities and the column parities for the arrangement (10) are obtained from the row parities and column parities according to (9) by simply applying the permutation π.
The row parities p1,p2,p3,p4 can be regarded as a first group G1={p1,p2,p3,p4} of check bits and the column parities q1,q2,q3,q4 can be regarded as a second group G2={q1,q2,q3,q4} of check bits.
It is also possible to form further check bits or groups of check bits for cross parity codes, for example by forming what are known as diagonal parities, as described in the example embodiments and, by way of example, also in Rubinoff, M, “N-dimensional Codes for Detecting and Correcting Multiple Errors”, Com. of the ACM, 1961, pp. 545-551.
The effect of the change in a data bit on the change in the check bits in the first group of check bits, i.e. in this case on the change in the row parities and on the change in a second group of check bits, i.e. in this case on the change in the column parities, will now be described. The aim in this case is to consider that a data bit ui has been disrupted into an erroneous data bit ūi. As an example, the change in the data bit u6 to ū6 will be considered when the data bits are notionally arranged according to (9).
Since p2=u5+u6+u7+u8≠u5+ū6+u7+u8=p2, p2 changes to p2 when u6 changes to ū6. Since the row parities p1,p3,p4 are not dependent on u6, they also do not change when u6 changes to an erroneous data bit ū6.
Since q2=u2+u6+u10+u14≠u2+ū6+u10+u14=q2, q2 changes to q2 when u6 changes to ū6. Since the column parities q1,q3,q4 are not dependent on u6, they also do not change when u6 changes to an erroneous data bit ū6.
If the data bit u6 changes to ū6, precisely one bit, in this case the bit p2, in the first group G1={p1,p2,p3,p4} and precisely one bit, in this case the bit q2, in the second group G2={q1,q2,q3,q4} change. Totally analogously, it is possible to check for each data bit u1, . . . , u16 that, when the data bit ui under consideration changes to ūi, precisely one bit pji in the group G1 and precisely one bit qki in the group G2 change and that the pair pjj,qki is associated with the changing data bit ui for i=1, . . . , 16.
As a further example, the change in the data bit u6 to ū6 will be considered when the data bits are notionally arranged according to (10).
Since in this case p1=u1+u11+u10+u6≠u1+u11+u10+ū6=p1, p1 changes to p1 when u6 changes to ū6. Since q4=u6+u12+u5+u14≠ū6+u12+u5+u14=q4, q4 changes to q4 when u6 changes to ū6. Further row or column parities do not change.
If the data bit u6 changes to ū6, precisely one bit, in this case the bit p1, in the first group G1={p1,p2,p3,p4} and precisely one bit, in this case the bit q4, in the second group G2={q1,q2,q3,q4} change. Totally analogously, it is possible to check for each data bit u1, . . . ,u16 that, when the data bit ui under consideration changes to ūi, precisely one bit pji in the group G1 and precisely one bit qki in the group G2 change and that the pair pji,qki is associated with the changing data bit ui for i=1, . . . , 16.
For the two described arrangements according to (9) and (10), it is the case that, as for any cross parity code, there are two groups G1 and G2 of bits, which means that when precisely one data bit changes, precisely one bit from G1 and precisely one bit from G2 also change. The pair of changing bits from G1 and G2 also determines the changing data bit.
Hence, simple correction of an erroneously changed data bit is possible. The ANDing of the changes in each pair of bits, with the first bit from G1 and with the second bit from G2, is equal to the correction value for the associated data bit.
If Δui denotes the correction signal for ui, Δpj denotes the change in pj and Δqk denotes the change in qk, the arrangement (9) has the changes Δu1=Δp1Δq1, Δu2=Δp1Δq2, . . . , Δu16=Δp4Δq4.
For the arrangement (10), accordingly Δu1=Δp1Δq1, Δu2=Δp2Δq3, . . . , Δu16=Δp2Δq1.
FIG. 2 shows a circuit arrangement 2 according to an embodiment. The circuit arrangement 2 determines m check bits c1, . . . , cm=c from k data bits u1, . . . ,uk=u. The circuit arrangement 2 consists of a first subcircuit SZw 19 for forming M binary intermediate values z1, . . . , zM having k binary inputs to which the data bits u1, . . . , uk are applied. The circuit SZw 19 has M binary outputs at which the intermediate values z1, . . . , zM are output and are connected to corresponding inputs on a second subcircuit Tr 110. The second subcircuit Tr 110 is called the transformation circuit. It transforms the intermediate values z1, . . . , zM into m check bits c1, . . . , cm and outputs them at their m outputs. In this case, m<M.
The intermediate values z1, . . . , zM that are output by the first subcircuit SZw 19 form a first group G1 of M1 intermediate values z1,1, z1,2, . . . , zi,j1, . . . , z1,s, . . . , z1,M1, which are output at the outputs 11, 12, 13, 14, 15, and a second group G2 of M2 intermediate values z2,1 . . . , z2,i, . . . , z2,rj, . . . , z2,M2, which are output at the outputs 14, 15, 16, 17. In this example embodiment, provision is made for the intermediate value that is output at the output 14 to belong both to group G1 and to group G2. As an element of group G1, it is referred to as z1,s and as an element of group G2, it is referred to as z2,1, so that z1,s=z2,1.
Provision is also made in this example embodiment for the intermediate value that is output at the output 15 to belong both to group G1 and to group G2. As an element of group G1, it is referred to as z1,M1, and as an element of group G2, it is referred to as z2,i, so that z1,M1=z2,i.
The groups G1 and G2 of intermediate values have different intermediate values. Thus, the intermediate values z1,1,z1,2,z1,lj that are output at the outputs 11, 12, 13 belong only to group G1, while the intermediate values z2,rj,z2,M2 that are output at the outputs 16 and 17 belong only to group G2. In other example embodiments, the groups G1 and G2 do not have any common elements. In the example embodiment in FIG. 2, the case in which there is at least one intermediate value that belongs neither to group G1 nor to group G2 is shown. Thus, the intermediate value zM that is output at the output 18 belongs neither to group G1 nor to group G2.
In other example embodiments, it is possible for each intermediate value to belong to a group of intermediate values.
The first subcircuit SZw 19 is configured such that each data bit uj, j=1, . . . , k, that is input to the first subcircuit SZw 19 has an associated pair of intermediate values z1,lj, z2,rj, with a first intermediate value z1,lj belonging to group G1 and the second intermediate values z2,rj belonging to group G2, with the following properties:
if z1,lj(u1, . . . , uj−1, uj, uj+1, . . . , uk) is the intermediate value z1,lj determined from the data bits (u1, . . . , uj−1, uj, uj+1, . . . , uk), which belongs to the first group G1, and if z2,rj(u1, . . . , uj−1, uj, uj+1, . . . , uk) is the intermediate value z2,rj, determined from the data bits (u1, . . . , uj−1, uj, uj+1 . . . , uk), which belongs to the second group G2, then both z1,lj changes to the negated value zj,lj and z2,rj changes to the negated value z2,rj when the data bit uj changes to the negated data bit ūj and when no further data bit changes, so that

z1,lj(u1, . . . ,uj−1,ūj,uj+1, . . . ,uk)=z1,lj(u1, . . . ,uj−1,uj,uj+1, . . . ,uk)

z2,rj(u1, . . . ,uj−1,ūj,uj+1, . . . ,uk)=z2,rj(u1, . . . ,uj−1,uj,uj+1, . . . ,uk).

Furthermore, also: if both z1,lj changes to the negated value zj,lj and z2,rj changes to the negated value z2,rj and if only one data bit is changed, then the data bit uj is changed.
In FIG. 2, the data bit uj is input at the input 118. The figure shows that the associated pair of intermediate values z1,lj and z2,rj is output at the outputs 13 and 16 of the first subcircuit SZw 19. If uj now changes to ūj, then both z1,lj changes to z1,lj and z2,rj changes to z2,rj. In FIG. 2, the changed values are each written in parentheses after the original values. The association between the data bit uj and the pair of intermediate values z1,lj and z2,rj and the association between the pair of intermediate values z1,lj,z2,rj and the data bit uj are illustrated by two arrows.
As already described, each of the data bits u1, . . . , uk has an associated pair of corresponding intermediate values, as illustrated in FIG. 2 just for the input value uj.
The second subcircuit Tr 110 transforms the intermediate values z1, . . . , zM into the check bits c1, . . . , cm, which are output at the m binary outputs of the second subcircuit Tr.
In the example embodiment shown in FIG. 2, the intermediate values z1,1, . . . , z1,M1, which belong to group G1, are transformed by the second subcircuit Tr 110 into the check bits c1,1, . . . , c1,h1 (z1,1, . . . , z1,k, . . . , z1,M1), where h1<M1 and where the check bits c1,1, c1,2, . . . , c1,h1 are not dependent on further intermediate values.
The transformation circuit Tr 110 is configured such that the intermediate values z1,1(u1, . . . , ui, . . . , uk), . . . , z1,i(u1, . . . , ui, . . . , uk), . . . , z1,M1(u1, . . . , ui, . . . uk) determined by the data bits u1, . . . , ui, . . . , uk and the intermediate values



  
    
      
        z
        
          1
          ,
          1
        
      
      ⁡
      
        (
        
          
            
              u
              _
            
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        z
        
          1
          ,
          i
        
      
      ⁡
      
        (
        
          
            
              
                u
                _
              
              
                1
                ,
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            
              u
              i
            
            ⁢
            
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          1
          ,
          
            M
            1
          
        
      
      ⁡
      
        (
        
          
            
              u
              _
            
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            
              u
              k
            
          
        
        )
      
    
  




  ⋮




  
    
      
        z
        
          1
          ,
          1
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          1
          ,
          i
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              
                u
                _
              
              i
            
            ⁢
            
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        z
        
          1
          ,
          
            M
            1
          
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            i
          
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            
              u
              k
            
          
        
        )
      
    
  




  ⋮




  
    
      
        z
        
          1
          ,
          1
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        z
        
          1
          ,
          i
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              i
            
            ⁢
            
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          1
          ,
          
            M
            1
          
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            
              
                u
                _
              
              k
            
          
        
        )
      
    
  



determined by the data bits inverted in a respective bit are transformed into sequences of m check bits that differ in pairs.

In particular embodiments, it is possible for the check bits ch1+1, . . . , cm to be equal to the intermediate values zM-(m-h1−1), . . . , zM.
FIG. 3a shows a further example embodiment of the circuit arrangement 3 according to an embodiment. The circuit arrangement 3 comprises a first subcircuit SZw 29 for forming M binary intermediate values z1, . . . , zM having k binary inputs to which the data bits u1, . . . , uk are applied. The circuit SZw 29 has M binary outputs at which the intermediate values z1, . . . , zM are output and that are connected to the corresponding inputs of a transformation circuit Tr 210. It transforms the intermediate values z1, . . . , zM into m check bits c1, . . . , cm and outputs them at its m outputs. In this case, m<M.
The intermediate values z1, . . . , zM that are output by the first subcircuit SZw 29 form a first group G1 of M1 intermediate values z1,1, z1,2, . . . , z1,j1, . . . , z1,s, . . . , z1,M1, which are output at the outputs 21, 22, 23, 24, 25, and a second group G2 of M2 intermediate values z2,1 . . . , z2,t, . . . , z2,rj, . . . , z2,M2, which are output at the outputs 24, 25, 26, 27. In this example embodiment, provision is made for the intermediate value that is output at the output 24 to belong both to the group G1 and to the group G2. As an element of group G1, it is referred to as z1,s, and as an element of group G2, it is referred to as z2,1, so that z1,s=z2,1.
This example embodiment also has provision for the intermediate value that is output at the output 25 to belong both to group G1 and to group G2. As an element of group G1, it is referred to as z1,M1, and as an element of group G2, it is referred to as z2,t, so that z1,M1=z2,t.
The groups G1 and G2 of intermediate values have different intermediate values. Thus, the intermediate values z1,1,z1,2,z1,lj that are output at the outputs 21, 22, 23 belong only to group G1, while the intermediate values z2,rj,z2,M2 that are output at the outputs 26 and 27 belong only to group G2.
In the example embodiment in FIG. 3a, the case in which there is at least one intermediate value that belongs neither to group G1 nor to group G2 is shown. Thus, the intermediate value zM that is output at the output 28 belongs neither to group G1 nor to group G2.
In other example embodiments, it is possible for each intermediate value to belong to a group of intermediate values.
The first subcircuit SZw 29 is configured such that each data bit uj, j=1, . . . , k, that is input into the first subcircuit SZw 29 has an associated pair of intermediate values z1,lj, z2,rj, with a first intermediate value z1,lj belonging to the group G1 and with the second intermediate value z2,rj belonging to the group G2, with the properties already described in the example embodiment from FIG. 2.
In FIG. 3a, the data bit uj is input at the input 218. The figure shows that the associated pair of intermediate values z1,lj and z2,rj is output at the outputs 23 and 26 of the first subcircuit SZw 29. If uj now changes to ūj, then z1,lj changes to z1,lj and z2,rj changes to z2,rj. In FIG. 3a, as in FIG. 2, the changed values are each written in parentheses after the original values. The association between the data bit uj and the pair of intermediate values z1,lj and z2,rj and the association between the pair of intermediate values z1,lj,z2,rj and the data bit uj are illustrated by two arrows.
As already described, each of the data bits u1, . . . , uk has an associated pair of corresponding intermediate values, as illustrated in FIG. 3a just for the input value uj.
The second subcircuit Tr 210 transforms the intermediate values z1, . . . , zM into the check bits c1, . . . , cm, which are output at the m binary outputs of the second subcircuit Tr.
In the example embodiment shown in FIG. 3a, the intermediate values z1,1, . . . , z1,M1, that belong to group G1 are transformed by the second subcircuit Tr 210 into the check bits c1,1, . . . , c1,h1 (z1,1, . . . , z1,k, . . . , z1,M1), where h1<M1 and where the check bits c1,1, c1,2, . . . , c1,h1 are not dependent on further intermediate values. The intermediate values z2,1, . . . , z2,M2 that belong to group G2 are transformed by the second subcircuit Tr 210 into the check bits c2,1, . . . , c2,h2 (z2,1, . . . z2,k, . . . , z2,M2), where h2<M2 and where the check bits c2,1, c2,2, . . . , c2,h2 are not dependent on further intermediate values.
The transformation circuit Tr 210 is configured such that for q=1,2 the intermediate values

zq,1(u1, . . . ,ui, . . . ,uk), . . . ,zq,i(u1, . . . ,ui, . . . ,uk), . . . ,zq,M1(u1, . . . ,ui, . . . uk)

determined by the data bits u1, . . . , ui, . . . , uk and the intermediate values




  
    
      
        z
        
          q
          ,
          1
        
      
      ⁡
      
        (
        
          
            
              u
              _
            
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        z
        
          q
          ,
          i
        
      
      ⁡
      
        (
        
          
            
              u
              _
            
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              i
            
            ⁢
            
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          q
          ,
          
            M
            q
          
        
      
      ⁡
      
        (
        
          
            
              u
              _
            
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            
              u
              k
            
          
        
        )
      
    
  




  ⋮




  
    
      
        z
        
          q
          ,
          1
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        z
        
          q
          ,
          i
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              
                u
                _
              
              i
            
            ⁢
            
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          q
          ,
          
            M
            q
          
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            i
          
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            
              u
              k
            
          
        
        )
      
    
  




  ⋮




  
    
      
        z
        
          q
          ,
          1
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        z
        
          q
          ,
          i
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          q
          ,
          
            M
            q
          
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            
              
                u
                _
              
              k
            
          
        
        )
      
    
  



determined by the data bits inverted in a respective bit are transformed into sequences of m check bits that differ in pairs.

FIG. 3b shows a further example embodiment of a circuit arrangement 4 according to an embodiment. The circuit arrangement 4 comprises a first subcircuit SZw 39 for forming M binary intermediate values z1, . . . , zM having k binary inputs 316 to 319 to which the data bits u1, . . . , uk are applied. The circuit SZw 39 has M binary outputs 31 to 37 at which the intermediate values z1, . . . , zM are output and that are connected to corresponding inputs of a transformation circuit Tr 310. The transformation circuit Tr 310 transforms the intermediate values z1, . . . , zM into m check bits c1, . . . , cm and outputs them at its m outputs. In this case, m<M.
The intermediate values z1, . . . , zM that are output by the first subcircuit SZw 39 form a first group G1 of M1 intermediate values z1,1, . . . , z1,lj . . . , z1,M1=z1, z2, . . . , z1,lj, . . . zM1, which are output at the outputs 31, 32, 33, 34, and a second group G2 of M2 intermediate values z2,1, . . . , z2,rj, . . . , z2,M2=zM1+1, . . . , z2,rj, . . . zM, which are output at the outputs 35, 36, 37. In this example embodiment, provision is made for each intermediate value to belong either to group G1 or to group G2.
In the example embodiment under consideration, the groups G1 and G2 of intermediate values do not have any common intermediate values, and each intermediate value belongs either to group G1 or to group G2.
The first subcircuit SZw 39 is configured such that each data bit uj, j=1, . . . , k, that is input into the first subcircuit SZw 39 has an associated pair of intermediate values z1,lj, z2,rj with a first intermediate value z1,lj belonging to group G1 and with the second intermediate value z2,rj belonging to group G2, with the properties already described in the example embodiment from FIG. 2.
In FIG. 3b, the data bit uj is input at the input 318. The figure shows that the associated pair of intermediate values z1,lj and z2,rj is output at the outputs 33 and 36 of the first subcircuit SZw 39. If uj now changes to ūj, then both z1,lj changes to z1,lj and z2,rj changes to z2,rj. In FIG. 3b, as in FIG. 2 and FIG. 3a, the changed values are each written in parentheses after the original values. The association between the data bit uj and the pair of intermediate values z1,lj and z2,rj and the association between the pair of intermediate values z1,lj,z2,rj and the data bit uj are illustrated by two arrows.
As already described, each of the data bits u1, . . . , uk has an associated pair of corresponding intermediate values, as illustrated in FIG. 3b just for the input value uj.
The second subcircuit Tr 310 transforms the intermediate values z1, . . . , zM into the check bits c1, . . . , cm, which are output at the in binary outputs 311 to 315 of the second subcircuit Tr 310.
In the example embodiment shown in FIG. 3b, the intermediate values z1,1, . . . , z1,M1=z1, . . . , zM1 that belong to group G1 are transformed by the second subcircuit 310 into the check bits c1,1, . . . , c1,h1=c1, . . . , ch1(z1, . . . . , zM1), which are output at the outputs 311 to 313, where h1<M1.
The intermediate values z2,1, . . . , z2,M2=zM1+1, . . . , zM that belong to group G2 are transformed by the second subcircuit Tr 310 into the check bits ch1+1, . . . , cm, which are output at the outputs 314 to 315, where h2<M2.
An example embodiment with 16 data bits u1, u1, . . . , u16 is explained below.
FIG. 4 shows a circuit arrangement 5 according to an embodiment with 16 data bits u1, . . . , u16.
The first subcircuit SZw 41 has 16 binary inputs, at which the data bits u1, . . . , u16 are input, and 8 binary outputs 431-438, at which the binary intermediate values z1, . . . , z8 are output, and a further binary output 439, at which a total parity bit P is output.
The 8 intermediate values z1=p1, z2=p2, z3=p3, z4=p4, z5=q1, z6=q2, z6=q3, z8=q4 are determined by the first subcircuit SZw from the data bits according to the relationships

z1=p1=u1⊕u2⊕u3⊕u4  (15)

z2=p2=u5⊕u6⊕u7⊕u8  (16)

z3=p3=u9⊕u10⊕u11⊕u12  (17)

z4=p4=u13⊕u14⊕u15⊕u16  (18)

and

z5=q1=u1⊕u5⊕u9⊕u13  (19)

z6=q2=u2⊕u6⊕u10⊕u14  (20)

z7=q3=u3⊕u7⊕u11⊕u15  (21)

z8=q4=u4⊕u8⊕u12⊕u16  (22).

The intermediate values p1, . . . , p4 correspond to the row parities and the intermediate values q1, . . . ,q4 correspond to the column parities of a cross parity code with 16 data bits.
The group G1 comprises the intermediate values p1, p2, p3, p4 and the group G2 comprises the intermediate values q1, q2, q3, q4.
If the value of a data bit ui changes to the negated value ūi while all the remaining data bits remain unchanged, precisely one pair pj1,i, qj2,i of intermediate values changes, one intermediate value, in this case the intermediate value pj1,i, being from G1 and one intermediate value, in this case the intermediate value qj2,i, being from G2. By way of example, the intermediate value p1εG1 changes to p1 and the intermediate value q2εG2 changes to q2 when u2 changes to ū2 and when no further data bit changes.
The second input is marked u2 and (u2). This input is connected both to the output 431 and to the output 436 of the first subcircuit SZw 41 by means of a double-headed arrow, these outputs being marked (p1) and (q2) in order to illustrate that a change from u2 to u2 results in a change from p1 to p1 and from q2 to q2.
A change in the value u16 to u16 results in a change in the intermediate value p4 to p4 and in the intermediate value q4 to q4. The sixteenth input, which is marked u16 and [ū16], is connected to the output 434, which is marked p4 and [p4], and to the output 438, which is marked q4 and [q4], by means of a respective double-headed arrow. It is illustrated that a change from u16 to u16 results in a change from p4 to p4 and from q4 to q4.
Furthermore, the double-headed arrows illustrate that the result of a change from p1 to p1 and q2 to q2 is that u2 has changed to u2 when only a single data bit changes.
Similarly, the double-headed arrows illustrate that the result of a change from p4 to p4 and q4 to q4 is that u16 has changed to u16 when no further data bit has changed.
The first subcircuit SZw 41 has a further output 439 that carries the parity P=u1⊕u2⊕ . . . ⊕u16. An output that carries the parity of the input signals may be expedient in instances of application.
In the example embodiment described, the intermediate values p1, p2, p3, p4 in group G1 are transformed by the second subcircuit Tr 42 into the check bits c1, c2, c3 according to the relationship

(c1,c2,c3)=A1·(p1,p2,p3,p4)  (23)

and the intermediate values q1, q2, q3, q4 in group G2 are transformed by the second subcircuit Tr 42 into the check bits c4, c5, c6 according to the relationship

(c4,c5,c6)=A2·(q1,q2,q3,q4)  (24),

where





  
    
      
        
          A
          1
        
        =
        
          
            A
            2
          
          =
          
            
              (
              
                
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    1
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    1
                  
                
              
              )
            
            .
          
        
      
    
    
      
        (
        25
        )
      
    
  




If the data bit u2, for example, erroneously changes to ū2, while all the other data bits do not change, then according to equation (15) the intermediate value p1 changes to p1 and according to equation (20) the intermediate value q2 changes to q2. In this case, p1 belongs to group G1, while q2 belongs to group G2.
According to equations (23), (24) and (25), the check bits c1, c2, c3 then change to (c1,c2,c3) and the check bits c4, c5, c6 change to (c4,c5,c6).
If the data bit u16, for example, erroneously changes to ū16, then according to equation (18) the intermediate value p4 changes to p4 and according to equation (22) the intermediate value q4 changes to q4. The intermediate value p4 belongs to group G1 and the intermediate value q4 belongs to group G2.
According to equations (23), (24) and (25), the check bits c1, c2, c3 then change to (c1,c2,c3) and the check bits c4, c5, c6 change to (c4,c5,c6).
If all possible changes of data bits ui to ūi are considered in the same way for iε{1, . . . , 16}, the changes in the check bits c1, . . . , c6 that are associated with these changes in the intermediate values all differ in pairs.
It can be seen that the 8 check bits p1, p2, p3, p4, q1, q2, q3 and q4 from a cross parity code with 16 data bits u1, . . . ,u16 as intermediate values are, according to an embodiment, transformed into 6 check bits c1, . . . , c6, which means that the number of check bits decreases.
According to the relationships specified in (23) and (24), the following equations are obtained for the check bits

c1=p1⊕p4,  (26)

c2=p2⊕p4,  (27)

c3=p3⊕p4,  (28)

c4=q1⊕q4,  (29)

c5=q2⊕q4,  (30)

c6=q3⊕q4.  (31).

The relationships 26 to 31 are provided by the second subcircuit Tr 42 from FIG. 4.
The 9 inputs of the second subcircuit Tr 42 are connected to the corresponding outputs 431 to 439 of the first subcircuit SZw 41. The inputs of the first subcircuit Tr 42 are denoted by the same numbers as the outputs of the first subcircuit SZw 41.
In order to form the parity bits at its outputs 441-446, the second subcircuit Tr 42 logically combines appropriate inputs using XOR gates.
According to equation (26), the input 431 that carries the intermediate value z1=p1 and the input 434 that carries the intermediate value z4=p4 are routed to a first input and to a second input of an XOR gate 421, the output 441 of which outputs the value of the check bit according to equation (26).
According to equation (30), the input 436 that carries the intermediate values z6=q2 is connected to a first input of an XOR gate 425, the second input of which is connected to the input 438 that carries the value z8=q4, and the output 445 of which outputs the value c5. If the word contains P which is output to the output 439 of the first subcircuit SZw 41, then P is output to the output 447 by the second subcircuit Tr 42 without alteration.
The data bits u=u1, . . . , u16 and the check bits c=c1, . . . , c6 can be stored in a memory at the address a. If the data bits u′=u1′, . . . , u16′ and the check bits c′=c1′, . . . , c6′ are read from the memory at the address a after some time, u and u′ and c and c′ may differ on account of errors that arise as a result of radiation, for example.
For the purpose of error correction, in this case for the purpose of error correction for 1-bit errors, changes Δci, i=1, . . . , 6 in the check bits may be determined as follows.
The effect of a 1-bit error in the data bits is that precisely one of the intermediate values piε{p1,p2,p3,p4}=G1 and one of the intermediate values qjε{q1,q2,q3,q4}=G2 change.
According to relationships (26) to (28), a change Δp1=1 in the intermediate value p1 to p1 corresponds to a change Δc1=1, Δc2=0, Δc3=0 in the check bits c1, c2, c3 to c1′, c2′, c3′, where c1′=c1, c2′=c2 and c3′=c3, so that only c1 changes to c1. To illustrate this change, the value (p1) is shown at the input 431 after z1=p1. Accordingly, the values (c1), (c2), (c3) are shown next to the values c1, c2, c3 at the outputs 441, 442, 443.
According to relationships (26) to (28), a change Δp4=1 in the intermediate value p4 to p4 corresponds, by contrast, to a change Δc1=1, Δc2=1, Δc3=1 in the check bits c1, c2, c3 to c1′, c2′, c3′, where c1′=c1, c2′=c2 and c3′=c3.
A change Δp2=1 in the intermediate value p2 to p2 corresponds to a change Δc1=0, Δc2=1, Δc3=0 in the check bits c1, c2, c3 to c1′, c2′, c3′, where c1′=c1, c2′=c2 and c3′=c3.
A change Δp3=1 in the intermediate value p3 to p3 corresponds to a change Δc1=0, Δc2=0, Δc3=1 in the check bits c1, c2, c3 to c1′, c2′, c3′, where c1′=c1, c2′=c2 and c3′=c3.
Correspondingly, according to relationships (29) to (31): a change Δq1=1 in the intermediate value q1 to q1, corresponds to a change Δc4=1, Δc5=0, Δc6=0 in the check bits c4, c5, c6 to c4′, c5′, c6′, where c4′=c4, c5′=c5 and c6′=c6. A change Δq2=1 in the intermediate value q2 to q2 corresponds to a change Δc4=0, Δc5=1, Δc6=0 in the check bits c4, c5, c6 to c4′, c5′, c6′, where c4′=c4, c5′=c5 and c6′=c6. A change Δq3=1 in the intermediate value q3 to q3 corresponds to a change Δc4=0, Δc5=0, Δc6=1 in the check bits c4, c5, c6 to c4′, c5′, c6′, where c4′=c4, and c6′=c6. A change Δq4=1 in the intermediate value q4 to q4 corresponds to a change Δc4=1, Δc5=1, Δc6=1 in the check bits c4, c5, c6 to c4′, c5′, c6′, where c4′=c4, c5′=c5 and c6′=c6.
Table 1 summarizes these statements for Δc1, Δc2, Δc3 and Δp1, Δp2, Δp3, Δp4.













TABLE 1





Δc1
Δc2
Δc3
Δp1
Δp2
Δp3
Δp4







0
0
0
0
0
0
0


1
0
0
1
0
0
0


0
1
0
0
1
0
0


0
0
1
0
0
1
0


1
1
1
0
0
0
1









A change in one of the intermediate values p1, p2, p3, p4 has an associated change in the check bits c1, c2, c3, as shown in table 1.
The appropriate correlations for Δc4, Δc5, Δc6 and Δq1, Δq2, Δq3, Δq4 are shown in table 2.













TABLE 2





Δc4
Δc5
Δc6
Δq1
Δq2
Δq3
Δq4







0
0
0
0
0
0
0


1
0
0
1
0
0
0


0
1
0
0
1
0
0


0
0
1
0
0
1
0


1
1
1
0
0
0
1









A change in the intermediate values q1, q2, q3, q4 has an associated change in the check bits c4, c5, c6 as shown in table 2.
The changes in the check bits can be used to determine the changes in the intermediate values by means of the relationships

Δp1=Δc1(Δc2Δc3),  (32)

Δp2=Δc2(Δc1Δc3),  (33)

Δp3=Δc3(Δc1Δc2),  (34)

Δp4=Δc1Δc2Δc3,  (35)

and

Δq1=Δc4(Δc5Δc6),  (36)

Δq2=Δc5(Δc4Δc6),  (37)

Δq3=Δc6(Δc4Δc5),  (38)

Δq4=Δc4Δc5Δc6  (39).

The changes in the intermediate values can now be used to locate and correct any 1-bit errors in the data bits. If Δp2 and Δq4 are equal to one, for example, then there is an error in the 2nd row and 4th column, and hence in u8.
The correction equation for the read data bit u8′ comprises ANDing of Δp2 and Δq4 

u8=u8′⊕(Δp2Δq4).

In a similar manner to u8, the correction equations for the remaining data bits are determined.
A data bit is corrected when an intermediate value from the first group G1={p1,p2,p3,p4} and an intermediate value from the second group G2={q1,q2,q3,q4} has changed.
ANDing of all the pairs of intermediate value changes, wherein a first intermediate value is from G1 and a second intermediate value is from G2 and the subsequent XORing of the output of the AND function with the appropriate data bit do not cause any difficulties for a person skilled in the art.
FIG. 5 shows a possible implementation of the first subcircuit SZw 41 from FIG. 4. In order to form the intermediate values z1=p1, . . . , z8=q4, appropriate data bits are XORed.
For i=1, 3, 5, 7, 9, 11, 13, 15, the input of the circuit SZw 41 that carries the signal ui is connected to a first input of an XOR gate 51i, the second input of which is connected to the circuit input that carries the signal ui+1.
The output of the XOR gate 51j is connected to a first input of an XOR gate 51(j+1), the second input of which is connected to the output of the XOR gate 51j+2, where jε{1,5,9,13}.
The output of the XOR gate 512 carries the intermediate value z1=p1.
The output of the XOR gate 516 carries the intermediate value z2=p2.
The output of the XOR gate 5110 carries the intermediate value z3=p3.
The output of the XOR gate 5114 carries the intermediate value z4=p4.
For kε{1,2,3,4,9,10,11,12}, the first input of an XOR gate 52k is connected to the circuit input of the first subcircuit SZw 41 that carries the input signal uk, and the second input of said XOR gate is connected to the circuit input of SZw 41 that carries the input signal uk+4.
For lε{1,2,3,4}, the output of the XOR gate 52l is connected to a first input of an XOR gate 52(l+4), the second input of which is connected to the output of the XOR gate 52(l+8).
The output of the XOR gate 525 carries the intermediate value z5=q1.
The output of the XOR gate 526 carries the intermediate value z6=q2.
The output of the XOR gate 527 carries the intermediate value z7=q3.
The output of the XOR gate 528 carries the intermediate value z8=q4.
In order to distinguish 1-bit errors from 2-bit errors in the check bits, a parity P is usually also formed over all the data bits in the case of uncompacted cross parity codes. If any data bit ui changes, then the total parity P also changes. No change occurs if a check bit is affected by an error. Using this total parity, it is therefore possible to distinguish 1-bit errors in the data bits from 2-bit errors in the data and check bits.
For the equations for correcting the row and column parities, the changes in the transformed check bits are used directly. If only the value of c2 changes, for example, then also just the change Δc2 is equal to one. Since ΔP is one only when a data bit is affected by a change, the following equation can be used for correcting c2 

c2=c2′⊕(Δc2ΔP).

For correcting the total parity P, it is possible to use a fact that, in the event of an exclusive change in P, there is also just a resultant change therein to one. For the correction, it is therefore possible to use the following equation

P=P′⊕((Δc1Δc2Δc3Δc4Δc5Δc6)ΔP).

Hence, the correction circuit for P has the longest path. One way of shortening this path is to calculate it twice, once using the read row check bits and once using the read column check bits

ΔP′=c1′⊕c2′⊕c3′⊕P′,  (40)

ΔP2=c4′,⊕c5′⊕c6′⊕P.  (41)

This is possible because

P=u1⊕u2⊕ . . . ⊕16=c1⊕c2⊕c3=c4⊕c5⊕c6.  (42).

For the correction equations for the data bits, this has no further effects. If the value of a row or column check bit changes, then the corresponding row or column change is accompanied by a change in the corresponding row total parity change ΔP1 or column total parity change ΔP2. For c2, it is therefore now possible to use the following correction equation

c2=c2⊕(Δc2ΔP1).

For the correction of c4, the column check bit used can be the following equation

c4=c4′⊕(Δc4ΔP2).

For all the other row and column check bits, the equations are determined in a similar manner.
In the event of a 1-bit error in P, the changes ΔP1 and ΔP2 are determined to be one. This combination does not arise for any of the other 1-bit errors. Therefore, the following equation can be used for correcting P

P=P′⊕(ΔP1ΔP2).

The equations for possible detection of 1-bit and 2-bit errors will now be presented. It should first of all be established that at least one of the changes is equal to one when two values in the bits of the read or received word have changed in comparison with the actual code word.
In principle, there are 3 ways for the individual components of a 2-bit error to be distributed over the intended array. Both errors are located in one row, both errors are located in one column or both errors are located in different rows and columns. In this case, it is irrelevant whether data bits or the check bits are affected by an error. The two total parity changes ΔP1 and ΔP2 provide information about whether there is a disruption in the last row or column.
Therefore, if two errors are located in the same row, none of the changes in the rows is equal to one, but two changes in the columns. Similarly, for two errors in one column, only two changes in the rows are equal to one. If both errors are in different rows and columns, two respective changes in the rows and columns are equal to one. Therefore, at least one of the changes is always equal to one.
So as now to separate 1-bit errors and 2-bit errors, the relationship specified in (42) can be used. The relationship reveals that the sum of all the bits in the code word must be even, that is to say

0=P′⊕u1′⊕u2′⊕ . . . ⊕u16′⊕c1′⊕c2′⊕c3′⊕c4′⊕c5′⊕c6′.

It can be seen, when a 1-bit error occurs in one of the bits, that this sum then turns out to be one and turns out to be zero again in the case of a 2-bit error. The equation used for recognizing 1-bit errors can therefore be

f1-bit-error=P′⊕u1′⊕u2′⊕ . . . ⊕u16′⊕c1′⊕c2′⊕c3′⊕c4′⊕c5′⊕c6′   (43).

For 2-bit error detection, it is possible to use

f2-bit-=f1-bit-error(Δc1Δc2Δc3Δc4Δc5Δc6)error  (44).

FIG. 6 shows a decoder for determining a subset of data bits that are to be corrected on the basis of m check bits c1, . . . , cm, the m check bits c1, . . . , cm being formed by a circuit arrangement for determining the check bits c1, . . . , cm for k data bits u1, . . . ,uk in accordance with one of the preceding claims.
The decoder comprises:
a third subcircuit Ssyndrome 61 for forming a subset of differences Δc1=c1⊕c1′, . . . , Δcm=cm⊕cm′ for the correct check bits c1, . . . , cm and the possibly erroneous check bits c1′, . . . , cm′, these differences being determined from possibly erroneous data bits u1′, . . . , uk′ and possibly erroneous check bits c1′, . . . , cm′,
a fourth subcircuit Decomp 62 for forming a subset of differences Δz1=z1⊕z1′, . . . , ΔzM=zM⊕zM′ from error-free intermediate values z1, . . . , zM and possibly erroneous intermediate values z1′, . . . , zM′, the differences Δz1, . . . ΔzM being determined from the differences in the intermediate values Δc1, . . . , Δcm, and
a fifth subcircuit Corr 63 for determining a corrected data bit uicor having at least three binary inputs for inputting the possibly erroneous data bit u1′ and for inputting two differences Δz1,lj,Δz2,rj for intermediate values and a binary output for outputting the corrected data bit uicor, wherein z1,lj belongs to a first group of intermediate values and z2,rj belongs to a second group of intermediate values, so that, when uj changes to uj and also no error occurs, z1,lj changes to z1,lj and z2,rj changes to z2,rj and the fifth subcircuit Corr is designed such that it outputs ujcor=uj⊕1 when Δz1,lj=Δz2,rj=1.
In particular, FIG. 6 shows an example embodiment of a decoder that is constructed from the three subcircuits Syndrome 6.1, Decomp 6.2 and Corr 6.3.
The m+k inputs of the subcircuit Syndrome 6.1 have the values u1′, . . . , uk′ of the possibly erroneous k data bits and of the values c1′, . . . , cm′ of the possibly erroneous m check bits supplied to them, said values having been read from a memory, for example.
The subcircuit Syndrome 6.1 outputs the changes in the check bits Δc1=c1′⊕c1, . . . , Δcm=cm′⊕cm at its m outputs.
The subcircuit Decomp 6.2 forms changes in the intermediate values Δz1=z1′⊕z1, . . . , ΔzM=zM′⊕zM from the changes in the check bits Δc1, . . . , Δcm.
If precisely one data bit, for example uj, is disrupted into uj=uj′, while all the remaining data bits and check bits are error-free, then two changes in the intermediate values Δz1,lj and Δz2,rj are equal to one, while all the remaining changes in intermediate values are equal to zero. z1,lj belongs to a first group of intermediate values and z2,rj belongs to a second group of intermediate values.
The corrector Corr 6.3 forms the corrected bits.
FIG. 6 shows the case in which the data bits are corrected and the check bits are not corrected. It is also possible for just one data bit, a subset of the data bits or data and check bits to be corrected.
In FIG. 6, the subcircuit Corr 6.3 has M+k inputs for inputting the differences in the intermediate values Δz1, . . . , ΔzM and the data bits u1′, . . . , uk′ that are to be corrected. In addition, it has k outputs for outputting the k corrected values of the data bits u1corr, . . . , ukcorr.
In this case, the subcircuit Corr 6.3 is designed such that ujcor=uj⊕1 when Δz1,lj=Δz2,rj=1 and all the other differences in the output intermediate values are equal to zero.
In a further example embodiment, 36 useful data bits u1, . . . , u36 will be considered that are notionally arranged in a 6×6 array and are determined for the 12 intermediate values z1, . . . , z12.
The intermediate values z1=p1, . . . , z6=p6 are formed as the row parities p1, . . . , p6 of a 6×6 array from the 36 useful data bits, and the intermediate values z7=q1, . . . , z12=q6 are formed as the column parities q1, . . . , q6. In this example embodiment, the intermediate values can also be referred to as row and column parities. The following apply:

z1=p1=u1⊕u2⊕u3⊕u4⊕u5⊕u6,  (45)

z2=p2=u7⊕u8⊕u9⊕u10⊕u11⊕u12,  (46)

z3=p3=u13⊕u14⊕u15⊕u16⊕u17⊕u18,  (47)

z4=p4=u19⊕u20⊕u21⊕u22⊕u23⊕u24,  (48)

z5=p5=u25⊕u26⊕u27⊕u28⊕u29⊕u30,  (49)

z6=p6=u31⊕u32⊕u33⊕u34⊕u35⊕u36,  (50)

z7=q1=u1⊕u7⊕u13⊕u19⊕u25⊕u31,  (51)

z8=q2=u2⊕u8⊕u14⊕u20⊕u26⊕u32,  (52)

z9=q3=u3⊕u9⊕u15⊕u21⊕u27⊕u33,  (53)

z10=q4=u4⊕u10⊕u16⊕u22⊕u28⊕u34,  (54)

z11=q5=u5⊕u11⊕u17⊕u23⊕u29⊕u35,  (55)

z12=q6=u6⊕u12⊕u18⊕u24⊕u30⊕u36.  (56).

The intermediate values z1=p1, . . . , z12=q6 form two groups G1 and G2 of intermediate values

G1={z1=p1,z2=p2,z3=p3,z4=p5,z6=p6},

G2={z7=q1,z8=q2,z9=q3,z10=q5,z12=q6}.

In this case, the groups G1 and G2 are formed such that a change in a data bit ui to ui results in the change in precisely one intermediate value from G1 and in the change in an intermediate value from G2 when no further data bit changes. Similarly: if precisely one intermediate value from G1 changes and if precisely one intermediate value from G2 simultaneously changes, then precisely one data bit changes.
If a total parity

P=u1⊕u2⊕ . . . ⊕u36 

is existent, then G3={P} forms a separate group in this example embodiment. According to one embodiment, it is possible to compact the 12 intermediate values z1, . . . , z12 into 8 check bits.

To this end, it is possible to transform the first 6 intermediate values z1, . . . , z6 according to the relationship

(c1,c2,c3,c4)=A·(z1,z2,z3,z4,z5,z6)  (57)

and the second 6 intermediate values z7, . . . , z12 according to the relationship

(c5,c6,c7,c8)=A·(z7,z8,z9,z10,z11,z12)  (58),

where





  
    
      
        
          A
          =
          
            (
            
              
                
                  1
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  1
                
                
                  0
                
              
              
                
                  0
                
                
                  1
                
                
                  0
                
                
                  0
                
                
                  1
                
                
                  1
                
              
              
                
                  0
                
                
                  0
                
                
                  1
                
                
                  0
                
                
                  1
                
                
                  1
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  1
                
                
                  0
                
                
                  1
                
              
            
            )
          
        
        ,
      
    
    
      
        (
        59
        )
      
    
  




into the check bits c1, . . . , c8.

Explicitly,

c1=z1⊕z5=p1⊕p5,  (60)

c2=z2⊕z5⊕z6=p2⊕p5⊕p6,  (61)

c3=z3⊕z5⊕z6=p3⊕p5⊕p6,  (62)

c4=z4⊕z6=p4⊕p6,  (63)

c5=z7⊕z11=q1⊕q5,  (64)

c6=z8⊕z11⊕z12=q2⊕q5⊕q6,  (65)

c7=z9⊕z11⊕z12=q3⊕q5⊕q6,  (66)

c8=z10⊕z12=q4⊕q6.  (67).

When a total parity P has been formed, it is not transformed in this example embodiment.
Implementing relationships (45) to (56) and (60) to (67) using XOR gates is not a problem for a person skilled in the art, which means that it is not discussed in more detail.
The matrix A, which stipulates how the intermediate values are transformed into check bits, has the following properties:
1. All the columns of the matrix A differ in pairs.
2. All the columns of the matrix A have an uneven number of ones.
These are precisely the properties of a matrix for a Hsiao code.
For c2 and c3, 2 XOR gate stages are required for the transformation. If faster coding is demanded and more check bits are permitted, the code can be adapted in accordance with these requirements.
The transformation of the 12 intermediate values z1, . . . , z12 onto 10 check bits c1, . . . , c10 can now be effected using a matrix A′




  
    
      
        
          
            A
            ′
          
          =
          
            (
            
              
                
                  1
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  1
                
              
              
                
                  0
                
                
                  1
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  1
                
              
              
                
                  0
                
                
                  0
                
                
                  1
                
                
                  0
                
                
                  0
                
                
                  1
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  1
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  1
                
                
                  0
                
              
            
            )
          
        
        ,
      
    
    
      
        (
        68
        )
      
    
  




so that

(c1,c2,c3,c4,c5)=A′·(z1,z2,z3,z4,z5,z6)

and

(c6,c7,c8,c9,c10)=A′·(z7,z8,z9,z10,z11,z12).

Then, for c1, . . . , c5,

c1=p1⊕p6,

c2=p2⊕p6,

c3=p3⊕p6,

c4=p4,

c5=p5 

and, for c6, . . . , c10,

c6=q1⊕q6,

c7=q2⊕q6,

c8=q3⊕q6,

c9=q4,

c10=q5.

All the columns of the matrix A′ are pairwise different and each column of A′ has an odd number of ones, so that A′ is again an H matrix for a Hsiao code.
It is possible to infer from the equations that one gate stage can be saved in comparison with a transformation using (59), an additional check bit being needed. An implementation of the second transformation therefore has a shorter delay than an implementation of the first transformation.
In a further application example, 9 data bits u1, . . . , u9 will now be considered. The 9 data bits u1, . . . , u9 are notionally arranged as a 3×3 array.
Initially, a total of 7 intermediate values z1, . . . , z7 

z1=p1=u1⊕u2⊕u3,

z2=p2=u4⊕u5⊕u6,

z3=p3=u7⊕u8⊕u9,

z4=q1=u1⊕u4⊕u7,

z5=q2=u2⊕u5⊕u8,

z6=q3=u3⊕u6⊕u9,

z7=P=u1⊕u2⊕ . . . ⊕u9 

are now formed. The intermediate values z1=p1, z2=p2, z3=p3 are now transformed according to the relationship

(c1,c2)=A′′·(p1,p2,p3)  (69)

and the intermediate values z4=q1, z5=q2, z6=q3 are transformed according to the relationship

(c3,c4)=A′′·(q1,q2,q3)  (70),

where





  
    
      
        
          
            A
            ′′
          
          =
          
            (
            
              
                
                  1
                
                
                  0
                
                
                  1
                
              
              
                
                  0
                
                
                  1
                
                
                  1
                
              
            
            )
          
        
        ,
      
    
    
      
        (
        71
        )
      
    
  




so that

c1=p1⊕p3,

c2=p2⊕p3,

c3=q1⊕q3,

c4=q2⊕q3.

All the columns of the matrix A′′ are pairwise different and A′′ is the H matrix for a Hamming code.
For the purpose of error correction, the changes Δc1, Δc2, Δc3, Δc4, ΔP are first of all determined, with u1′, . . . , u9′, c1′, . . . , c4′, P′ being the possibly erroneous values read from the memory. The following apply:

Δc1=c1′⊕u1′⊕u2′⊕u3′⊕u7′⊕u8′⊕u9′,

Δc2=c2′⊕u4′⊕u5′⊕u6′⊕u7′⊕u8′⊕u9′,

Δc3=c3′⊕u1′⊕u4′⊕u7′⊕u3′⊕u6′⊕u9′,

Δc4=c4′⊕u2′⊕u5′⊕u8′⊕u3′⊕u6′⊕u9′,

ΔP=P′⊕u1′⊕u2′⊕ . . . ⊕u9′.

The changes Δz1=Δp1, Δz2=Δp2, Δz3=Δp3, Δz4=Δq1, Δz5=Δq2, Δz6=Δq3, Δz7=ΔP in the intermediate values are

Δz1=Δp1=Δc1Δc2,

Δz2=Δp2=Δc2Δc1,

Δz3=Δp3=Δc1Δc2,

Δz4=Δq1=Δc3Δc4,

Δz5=Δq2=Δc4Δc3,

Δz6=Δq3=Δc3Δc4,

Δz7=ΔP. 

Furthermore, the correction of the data bits u1′, . . . , u9′ implements the relationships

u1=u1′⊕(Δp1Δq1),

u2=u2′⊕(Δp1Δq2),

u3=u3′⊕(Δp1Δq3),

u4=u4′⊕(Δp2Δq1),

u5=u5′⊕(Δp2Δq2),

u6=u6′⊕(Δp2Δq3),

u7=u7′⊕(Δp3Δq1),

u8=u8′⊕(Δp3Δq2),

u9=u9′⊕(Δp3Δq3),

The error detection can be effected by implementing the equation

Eerror=Δc1Δc2Δc3Δc4ΔP  (72).

The error detection for a 1-bit error in the useful data is output by a circuit that implements

E1-bit-error=(u1′⊕u2′⊕ . . . ⊕u9′⊕P′)  (73).

In a further application example, 14 data bits u1, . . . , u14 will now be considered.
Nine intermediate values z1, . . . , z9 are determined according to the relationships

z1=u1⊕u2⊕u3⊕u4,z2=u1⊕u5⊕u9,

z3=u5⊕u6⊕u7⊕u8,z4=u12⊕u14⊕u7,

z5=u9⊕u10⊕u11⊕u12,z6=u10⊕u13⊕u3,

z7=u13⊕u14,z8=u2⊕u6⊕u11,

z9=u4⊕u8.

For the total parity P,

P=u1⊕u2⊕ . . . ⊕u14.

The intermediate values z1, z2, . . . , z9 are now distributed over 2 groups

G1={z1,z3,z5,z7}.

G2={z2,z4,z6,z8,z9}.

If u1 changes to u1, then z1 from G1 changes to z1 and z2 from G2 changes to z2.
If u2 changes to u2, then z1 from G1 changes to z1 and z8 from G2 changes to z8.
For all the remaining data bits uj, j=3, . . . , 14, it can similarly be shown that, when uj changes to uj, a first intermediate value from G1 and a second intermediate value from G2 change.
The intermediate values in the two groups are now transformed onto 3 and 4 check bits, respectively. In this case, the following relationships apply:

(c1,c2,c3)=A1·(z1,z2,z5,z7),  (74)

(c4,c5,c6,c7)=A2′·(z2,z4,z6,z8,z9).  (75)

The matrices A1 and A2′ used are




  
    
      A
      1
    
    =
    
      (
      
        
          
            1
          
          
            0
          
          
            0
          
          
            1
          
        
        
          
            0
          
          
            1
          
          
            0
          
          
            1
          
        
        
          
            0
          
          
            0
          
          
            1
          
          
            1
          
        
      
      )
    
  
  ,
  
    

  
  ⁢
  
    
      A
      2
      ′
    
    =
    
      
        (
        
          
            
              1
            
            
              0
            
            
              0
            
            
              0
            
            
              1
            
          
          
            
              0
            
            
              1
            
            
              0
            
            
              0
            
            
              1
            
          
          
            
              0
            
            
              0
            
            
              1
            
            
              0
            
            
              1
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              1
            
            
              0
            
          
        
        )
      
      .
    
  




From relationships (74) and (75), the equations

c1=z1⊕z7,c4=z2⊕z9,

c2=z3⊕z7,c5=z4⊕z9,

c3=z5⊕z7,c6=z6⊕z9,

c7=z8 

are determined.

The text below considers an example embodiment with 36 data bits u1, . . . , u36 that are notionally considered to be arranged as a 6×6 array. The 12 intermediate values z1, . . . , z12 and the total parity P can then be formed as follows:

z1=p1=u1⊕u2⊕u3⊕u4⊕u5⊕u6,

z2=p2=u7⊕u8⊕u9⊕u10⊕u11⊕u12,

z3=p3=u13⊕u14⊕u15⊕u16⊕u17⊕u18,

z4=p4=u19⊕u20⊕u21⊕u22⊕u23⊕u24,

z5=p5=u25⊕u26⊕u27⊕u28⊕u29⊕u30,

z6=p6=u31⊕u32⊕u33⊕u34⊕u35⊕u36,

z7=q1=u1⊕u7⊕u13⊕u19⊕u25⊕u31,

z8=q2=u2⊕u8⊕u14⊕u20⊕u26⊕u32,

z9=q3=u3⊕u9⊕u15⊕u21⊕u27⊕u33,

z10=q4=u4⊕u10⊕u16⊕u22⊕u28⊕u34,

z11=q5=u5⊕u11⊕u17⊕u23⊕u29⊕u35,

z12=q6=u6⊕u12⊕u18⊕u24⊕u30⊕u36,

P=u1⊕u2⊕ . . . ⊕u36.

The intermediate values z1=p1, . . . , z6=p6 can also be referred to as row parities.
The intermediate values z7=q1, . . . , z12=q6 can also be referred to as column parities.
It is now possible to form further intermediate values z13=d1, . . . , z19=d7 according to the relationships

z13=d1=u1⊕u8⊕u15⊕u22⊕u29⊕u36⊕P, 

z14=d2=u2⊕u9⊕u16⊕u23⊕u30⊕p6⊕q1,

z15=d3=u3⊕u10⊕u17⊕u24⊕p5⊕u31⊕q2,

z16=d4=u4⊕u11⊕u18⊕p4⊕u25⊕u32⊕q3,

z17=d5=u5⊕u12⊕p3⊕u19⊕u26⊕u33⊕q4,

z18=d6=u6⊕p2⊕u13⊕u20⊕u27⊕u34⊕q5,

z19=d7=p1⊕u7⊕u14⊕u21⊕u28⊕u35⊕q6,

The intermediate values z13=d1, . . . , z19=d7 can be referred to as diagonal parities.
Obviously, the respective row parities p1, . . . , p6 can be appended to the 6 rows of the 6×6 array of the 36 useful data bits. Similarly, the 6 column parities q1, . . . , q6 can be appended to the 6 columns of the 6×6 array. In addition, the total parity P can be added in the bottom right-hand field, so that a 7×7 array is now formed from the data bits u1, . . . , u36 and the row and column parities p1, . . . , p6, q1, . . . , q6 and the total parity P.
The intermediate values z13=d1, . . . , z19=d7 then correspond to the diagonal parities, as are described in the work by E. J. Wieder “N-dimensional Codes for Detecting Four Errors and Correcting Three”, Master Thesis, Moore School of Electrical Engineering, Philadelphia, 1961, chapter V, pp. 2-3.
The additional diagonals can be used to locate 2-bit errors. If both error components of a 2-bit error are located in the same row, for example, then exclusive consideration of the row and column parities allows two changes to be observed in two columns, but not in the rows. Hence, although the two columns that contain the errors must be locatable, the row must not. The use of the diagonal adds a third dimension too, which can be used to locate the two erroneous bits again.
It is possible, for example, for the 7 intermediate values z13=d1, . . . , z19=d7 to be transformed into 4 check bits c1, c2, c3, c4 according to the relationships

c1=d1⊕d5⊕d7,

c2=d2⊕d5⊕d6,

c3=d3⊕d5⊕d6⊕d7,

c4=d4⊕d6⊕d7 

and for the other intermediate values z1, . . . , z12 to be left unchanged.

Similarly, it is possible for just the intermediate values z1, . . . , z6 and z7, . . . , z12 to be transformed and for the intermediate values z13, . . . , z19 and the total parity P not to be transformed.
FIG. 7 shows a system comprising a circuit arrangement 710 according to one of the embodiments described above and a decoder 720 for determining a subset of data bits that are to be corrected according to one of the embodiments described above. The circuit arrangement 710 produces check bits on the basis of received data bits. When a correction is necessary, the decoder 720 produces corrected data bits on the basis of received input data bits and the received check bits.
For the spatial and/or temporal transmission and the channel model, see [7], in particular.
In a specific example embodiment, a cross parity code for 16 useful data bits u1, . . . , u16 will be considered, the data bits of which are notionally arranged in a 4×4 array.
For this specific example embodiment, the circuit arrangement 710 is formed by at least 16 inputs for the 16 useful data bits u1, . . . , u16 and at least 6 outputs for the 6 check bits c1, . . . , c6 calculated from the data bits. The 6 check bits may have been determined in accordance with encoder equations (15) to (22) and (26) to (31).
As inputs, the decoder 720 has at least 16 inputs for the 16 received possibly erroneous useful data bits u1′, . . . , u16′ and 6 inputs for the 6 received possibly erroneous check bits c1′, c2′, . . . , c6′. The changes Δc1, . . . , Δc6 calculated in the decoder 720 may have been determined by the equations

Δc1=c1′⊕u1′⊕u2′⊕u3′⊕u4′⊕u13′⊕u14′⊕u15′⊕u16′,

Δc2=c2′⊕u5′⊕u6′⊕u7′⊕u8′⊕u13′⊕u14′⊕u15′⊕u16′,

Δc3=c3′⊕u9′⊕u10′⊕u11′⊕u12′⊕u13′⊕u14′⊕u15′⊕u16′,

Δc4=c4′⊕u1′⊕u5′⊕u9′⊕u13′⊕u4′⊕u8′⊕u12′⊕u16′,

Δc5=c5′⊕u2′⊕u6′⊕u10′⊕u14′⊕u4′⊕u8′⊕u12′⊕u16′,

Δc6=c6′⊕u1′⊕u7′⊕u11′⊕u15′⊕u4′⊕u8′⊕u12′⊕u16′,

The further correction of a subset of data bits, all the data bits or all the data and check bits may be implemented as set out in other preceding example embodiments.
Although some aspects have been described in connection with an apparatus, it goes without saying that these aspects are also a description of the corresponding method, which means that the block or a component of an apparatus is also intended to be understood to mean a corresponding method step or to mean a feature of a method step. Similarly, aspects that have been described in connection with or as a method step are also a description of a corresponding block or detail or feature of a corresponding apparatus. Some or all of the method steps can be performed by a hardware apparatus (or using a hardware apparatus), such as a microprocessor, a programmable computer or an electronic circuit. In the case of some example embodiments, some or several of the most important method steps can be performed by such an apparatus.
Depending on particular implementation requirements, example embodiments of the disclosure may be implemented in hardware or in software. The implementation can be performed using a digital storage medium, for example a floppy disk, a DVD, a BluRay Disk, a CD, a ROM, a PROM, an EPROM, an EEPROM or a FLASH memory, a hard disk or another magnetic or optical memory that stores electronically readable control signals that can interact or do interact with a programmable computer system such that the respective method is performed. Therefore, the digital storage medium may be computer-readable.
Some example embodiments according to the disclosure thus comprise a data storage medium that has electronically readable control signals that are capable of interacting with a programmable computer system such that one of the methods described herein is performed.
In general, example embodiments of the present disclosure may be implemented as a computer program product with a program code, the program code being effective for performing one of the methods when the computer program product is executed on a computer.
By way of example, the program code may also be stored on a machine-readable storage medium.
Other example embodiments comprise the computer program for performing one of the methods described herein, wherein the computer program is stored on a machine-readable storage medium. In other words, one example embodiment of the method according to the disclosure is therefore a computer program that has a program code for performing one of the methods described herein when the computer program is executed on a computer.
A further example embodiment of the methods according to the disclosure is therefore a data storage medium (or a digital storage medium or a computer-readable medium) on which the computer program for performing one of the methods described herein is recorded.
A further example embodiment of the method according to the disclosure is therefore a data stream or a sequence of signals that is/are the computer program for performing one of the methods described herein. By way of example, the data stream or the sequence of signals may be configured to be transferred via a data communication link, for example via the Internet.
A further example embodiment comprises a processing device, for example a computer or a programmable logic component, that is configured or customized to perform one of the methods described herein.
A further example embodiment comprises a computer on which the computer program for performing one of the methods described herein is installed.
A further example embodiment according to the disclosure comprises an apparatus or a system that is designed to transmit a computer program for performing at least one of the methods described herein to a receiver. By way of example, the transmission can be effected electronically or optically. By way of example, the receiver may be a computer, a mobile appliance, a storage appliance or a similar apparatus. By way of example, the apparatus or the system may comprise a file server for transmitting the computer program to the receiver.
In some example embodiments, a programmable logic component (for example a field-programmable gate array, an FPGA) can be used to perform some or all functionalities of the methods described herein. In some example embodiments, a field-programmable gate array can interact with a microprocessor in order to perform one of the methods described herein. In general, the methods in some example embodiments are performed by any hardware apparatus. This may be a universally usable piece of hardware such as a computer processor (CPU), or hardware that is specific to the method, such as an ASIC.
The example embodiments described above are merely an illustration of the principles of the present disclosure. It goes without saying that modifications and variations for the arrangements and details described herein will be apparent to other persons skilled in the art. The intention is therefore that the disclosure be limited merely by the scope of protection of the patent claims that follow rather than by the specific details that have been presented herein on the basis of the description and the explanation of the example embodiments.
Further examples of embodiments may include

    
    
        diagonal parities which are formed by XOR ing data bits.
        diagonal parity bits which are formed by XOR functions on the basis of data bits, row parity bits and column parity bits.
        a second subcircuit for transforming intermediate values into check bits which is a linear circuit.

Further embodiments may include a circuit arrangement, wherein M′=M1 and the subset {z1′, . . . , zM′} of the intermediate values is equal to the set of the intermediate values {z1,1, . . . , z1,M1} from the group G1 of intermediate values.

Further embodiments may include a decoder, wherein, in the event of a 1-bit error in the data bits u′, the change in the data bit Δui, where 0≦i≦k, can be presented as the product of n changes, where n≧2, in the intermediate values.

Further embodiments may include a circuit arrangement for determining m check bits c1, . . . , cm for k data bits u1, . . . , uk, comprising: a first subcircuit, and a second subcircuit, wherein the first subcircuit has SZw k binary inputs for inputting the k data bits u=u1, . . . , uk and M binary outputs for outputting M binary intermediate values z1, . . . , zM determined from the data bits, where

z1=z1(u)=z1(u1, . . . ,uk), . . . ,zM=zM(u)=zM(u1, . . . ,uk),

    
    


wherein the intermediate values form at least a first group G1={z1,1, z1,2, . . . , z1,M1} of M1 intermediate values and a second group G2={z2,1, z2,2, . . . , z2,M2} of M2 intermediate values, which is different than G1, wherein the first group G1 and the second group G2 have different intermediate values and 2≦M1, M2≦M, and the first subcircuit SZw is designed such that it determines the intermediate values from the data bits such that there is an association between a determined pair of intermediate values z1,lj,z2,mj for each data bit uj that is to be corrected, where z1,lj is an intermediate value from the first group G1 and z2,mj is an intermediate value from the second group G2, which is different than the intermediate value from the first group, so that

z1,lj(u1, . . . ,uj−1,ūj,uj+1, . . . ,uk)=z1,lj(u1, . . . ,uj−1,uj,uj+1, . . . ,uk)

z2,mj(u1, . . . ,uj−1,ūj,uj+1, . . . ,uk)=z2,mj(u1, . . . ,uj−1,uj,uj+1, . . . ,uk)

and a change in the pair z1,lj,z2,mj to z1,lj,z2,mj when only one data bit from the data bits {u1, . . . , uk} has changed to its negated value indicates that the j-th data bit uj has changed to ūj wherein the second subcircuit Tr is configured to transform the intermediate values z1, . . . , zM into the check bits c1, . . . , cm, wherein the second subcircuit Tr is designed such that it transforms the intermediate values zj,1, . . . , zj,Mj from at least one group Gj, of intermediate values into check bits

cj,1, . . . ,cj,hj(zj,1, . . . ,zj,k, . . . ,zj,Mj),

    
    
        so that the check bits associated with the intermediate values

zj,1(u1, . . . ,ui, . . . ,uk), . . . ,zj,i(u1, . . . ,ui . . . ,uk), . . . ,zj,Mj(u1, . . . ,ui, . . . uk)

determined from the data bits u1, . . . , ui, . . . , uk and the check bits associated with the intermediate values

    
    





  
    
      
        z
        
          j
          ,
          1
        
      
      ⁡
      
        (
        
          
            
              u
              _
            
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        z
        
          j
          ,
          i
        
      
      ⁡
      
        (
        
          
            
              u
              _
            
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          j
          ,
          
            M
            j
          
        
      
      ⁡
      
        (
        
          
            
              u
              _
            
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            
              u
              k
            
          
        
        )
      
    
  




  ⋮




  
    
      
        z
        
          j
          ,
          1
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        z
        
          j
          ,
          i
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              
                u
                _
              
              i
            
            ⁢
            
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          j
          ,
          
            M
            j
          
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            k
          
        
        )
      
    
  




  ⋮




  
    
      
        z
        
          j
          ,
          1
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        z
        
          j
          ,
          i
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              i
            
            ⁢
            
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            k
          
        
        )
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          j
          ,
          
            M
            j
          
        
      
      ⁡
      
        (
        
          
            u
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            u
            i
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              u
              _
            
            k
          
        
        )
      
    
  



determined from the data bits inverted in a respective bit differ in pairs, where m<M and hj<Mj 

Further embodiments may include a circuit arrangement which has been realized using a synthesis tool and/or a decoder which has been realized using a synthesis tool.

## Claims

1. A circuit arrangement for determining m check bits c1, . . . , cm for k data bits u1, . . . , uk, wherein the circuit arrangement comprises:
a first subcircuit having k binary inputs for inputting the k data bits (u=u1, . . . , uk) and M binary outputs for outputting M intermediate values determined from the k data bits, and
a second subcircuit for transforming the intermediate values (z1, . . . , zM) into the m check bits c1, . . . , cm, where m<M and M<k,
wherein the first subcircuit is configured to determine the intermediate values from the k data bits such that there is an association between a determined pair of intermediate values for each data bit uj that is to be corrected, such that a change in the pair of intermediate values indicates that the j-th data bit uj has changed to ūj when only one data bit from the k data bits {u1, . . . , uk} has changed to its negated value,
wherein the second subcircuit is configured to transform the intermediate values into the m check bits such that the m check bits associated with the intermediate values determined from the k data bits u1, . . . , uk and the m check bits associated with the intermediate values determined from the k data bits inverted in a respective bit from the k data bits that are to be corrected are pairwise different, where m<M.

2. The circuit arrangement as claimed in claim 1 for determining the m check bits c1, . . . , cm for the k data bits u1, . . . , uk,
wherein, for the intermediate values z1, . . . , zM:


z1=z1(u)=z1(u1, . . . , uk), . . . , zM=zM(u)=zM(u1, . . . , uk),


wherein the intermediate values form at least a first group G1={z1,1, z1,2, . . . , z1,M1} of M1 intermediate values and a second group G2={z2,1, z2,2, . . . , z2,M2} of M2 intermediate values, which is different than G1,
wherein the first group G1 and the second group G2 have different intermediate values, where 2≦M1,M2≦M,
wherein the first subcircuit is configured to determine the intermediate values from the k data bits such that there is an association between a determined pair of intermediate values z1,lj,z2,mj for each data bit uj that is to be corrected,
wherein z1,lj is an intermediate value from the first group G1 and z2,mj is an intermediate value from the second group G2, which is different than the intermediate value from the first group, so that


z1,lj(u1, . . . , uj−1,ūj,uj+1, . . . , uk)=z1,lj(u1, . . . , uj−1,uj,uj+1, . . . , uk)



z2,mj(u1, . . . , uj−1,ūj,uj+1, . . . , uk)=z2,mj(u1, . . . , uj−1,uj,uj+1, . . . , uk)



and a change in the pair z1,lj,z2,mj to z1,lj,z2,mj when only one data bit from the k data bits {u1, . . . , uk} has changed to its negated value indicates that the j-th data bit uj has changed to ūj.

3. The circuit arrangement as claimed in claim 2,
wherein the first subcircuit is configured such that when only one data bit uj changes to a negated data bit ūj a change takes place in precisely the intermediate values z1,lj,z2,mj and no further intermediate value from at least one of the groups G1 and G2 changes.

4. The circuit arrangement as claimed in claim 2,
wherein the second subcircuit is configured to transform the intermediate values z1, . . . , zM into the m check bits c1, . . . , cm such that it transforms the intermediate values zj,1, . . . , zj,Mj from at least the group Gj of intermediate values in which no further intermediate value changes in the event of the change from uj to ūj into the m check bits


cj,1, . . . , cj,hj(zj,1, . . . , zj,k, . . . , zj,Mj),



so that the m check bits associated with the intermediate values


zj,1, . . . , zj,k, . . . , zj,Mj 


and the intermediate values



  
    
      (
      
        
          
            z
            _
          
          
            j
            ,
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          z
          
            j
            ,
            k
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          z
          
            j
            ,
            
              M
              j
            
          
        
      
      )
    
    ,
    
      

    
    ⁢
    
      ...
      ⁢
      
        

      
      (
      
        
          z
          
            j
            ,
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          
            z
            _
          
          
            j
            ,
            k
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          z
          
            j
            ,
            
              M
              j
            
          
        
      
      )
    
  




  ...



and (zj,1, . . . , zj,k, . . . , zj,Mj)
which are inverted in a respective bit, are pairwise different.

5. The circuit arrangement as claimed in claim 4,
wherein the first subcircuit is configured such that when only one data bit uj changes to a negated data bit ūj a change is made in precisely the intermediate values z1,lj,z2,mj and no further intermediate value changes in both groups G1 and G2 and the second subcircuit for transforming the intermediate values z1, . . . , zM into the m check bits c1, . . . , cm is existent, wherein the second subcircuit is configured such that it transforms the intermediate values zj,1, . . . , zj,Mj from the group Gj of intermediate values, for j=1,2, into the m check bits


cj,1, . . . , cj,mj(zj,1, . . . , zj,k, . . . , zj,Mj),



so that the m check bits associated with the intermediate values


zj,1, . . . , zj,k, . . . , zj,Mj 


and the intermediate values



  
    
      (
      
        
          
            z
            _
          
          
            j
            ,
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          z
          
            j
            ,
            k
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          z
          
            j
            ,
            
              M
              j
            
          
        
      
      )
    
    ,
    
      

    
    ⁢
    
      ...
      ⁢
      
        

      
      (
      
        
          z
          
            j
            ,
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          
            z
            _
          
          
            j
            ,
            k
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          z
          
            j
            ,
            
              M
              j
            
          
        
      
      )
    
  




  ...



and (zj,1, . . . , zj,k, . . . , zj,Mj)
which are inverted in a respective bit, are pairwise different.

6. The circuit arrangement as claimed in claim 1, wherein the intermediate values or the m check bits determined from the intermediate values by the second subcircuit are each check bits from an at least 1-bit-error-correcting code.

7. The circuit arrangement as claimed in claim 6, wherein the m check bits determined from the intermediate values by the second subcircuit are the m check bits from an at least 1-bit-error-correcting code for correcting the intermediate values.

8. The circuit arrangement as claimed in claim 1, wherein the intermediate values determined by the first subcircuit and to be transformed by the second subcircuit are the m check bits from a cross parity code.

9. The circuit arrangement as claimed in claim 1, wherein the intermediate values determined by the first subcircuit and to be transformed by the second subcircuit are the m check bits from a code that, apart from a permutation of the k data bits and a permutation of the m check bits, is a cross parity code.

10. The circuit arrangement as claimed in claim 8, wherein the intermediate values are one or a combination of the following: row parities from a cross parity code, column parities from a cross parity code, diagonal parities from a cross parity code.

11. The circuit arrangement as claimed in claim 1, wherein the second subcircuit is configured to form a subset {z1′, . . . , zM′} of the intermediate values {z1, . . . , zM} into a subset c1′, . . . , cm′ of the m check bits in accordance with the relationship


c1′, . . . , cm′=H·(z1′, . . . , zM′),


where {c1′, . . . , cm′} are check bits that are associated with the intermediate values z1′, . . . , zM′ and H=(h1,h2, . . . , hM′) is a binary (m′,M′) matrix, wherein hi is a plurality of m′ columns of the binary matrix and are pairwise different for i=1, . . . , M′.

12. The circuit arrangement as claimed in claim 11, wherein the second subcircuit is configured to form a first subset {z1,1, . . . , z1,M1} of the intermediate values {z1, . . . , zM} into a subset c1,1, . . . , c1,m1 of the m check bits in accordance with the relationship


c1,1, . . . , c1,m1=H·(z1,1, . . . , z1,M1),


where {c1,1, . . . c1,m1} are check bits that are associated with the intermediate values z1,1, . . . , z1,M1 and H1=(h11,h21, . . . , hM11) is a binary (m1,M1) matrix, the m1-component columns hi1 of which are pairwise different for i=1, . . . , M1, and wherein it forms a second subset {z2,1, . . . , z2,M2} of the intermediate values {z1, . . . , zM} into a subset c2,1, . . . ,c2,m2 of the m check bits in accordance with the relationship


c2,1, . . . , c2,m2=H2·(z2,1, . . . , z2,M2),


where {c2,1, . . . , c2,m2} are check bits that are associated with the intermediate values z2,1, . . . , z2,M2 and H2=(h12,h22, . . . , hM12) is a binary (m2,M2) matrix, wherein hi2 is a plurality of m2 columns of the binary matrix and are pairwise different for i=1, . . . , M2.

13. The circuit arrangement as claimed in claim 12, wherein the columns of the matrix H1 or H2 have an odd number of ones.

14. The circuit arrangement as claimed in claim 12, wherein the matrix H1 or the matrix H2 is an H matrix for an error correcting linear code.

15. The circuit arrangement as claimed in claim 1, wherein the first subcircuit and the second subcircuit are located on a same support structure.

16. A decoder for determining a subset of data bits that are to be corrected on the basis of m check bits c1, . . . , cm, wherein the m check bits c1, . . . , cm are formed by a circuit arrangement for determining the m check bits c1, . . . , cm for k data bits u1, . . . , uk, wherein the decoder comprises:
a first subcircuit having k binary inputs for inputting the k data bits (u=u1, . . . uk) and M binary outputs for outputting M intermediate values (z1=z1(u1, . . . , uk), . . . , zM=zM(u1, . . . , uk)) determined from the k data bits, and
a second subcircuit for transforming the intermediate values (z1, . . . , zM) into the m check bits c1, . . . , cm, where m<M and M<k,
a third subcircuit for forming a subset of differences Δc1=c1⊕c1′, . . . , Δcm=cm⊕cm′ for a plurality of correct check bits c1, . . . , cm and the possibly erroneous check bits c1′, . . . , cm′, these differences being determined from a plurality of possibly erroneous data bits u1′, . . . , uk′ and possibly erroneous check bits c1′, . . . , cm′,
a fourth subcircuit for forming a subset of differences Δz1=z1⊕z1′, . . . , ΔzM=zM⊕zM′ from error-free intermediate values z1, . . . , zM and possibly erroneous intermediate values z1′, . . . , zM′, the differences Δz1, . . . ΔzM being determined from the differences in the intermediate values Δc1, . . . , Δcm, and
a fifth subcircuit for determining a corrected data bit ujcor having at least three binary inputs for inputting a possibly erroneous data bit uj′ and for inputting two differences Δz1,lj,Δz2,rj from intermediate values and a binary output for outputting the corrected data bit ujcor, wherein z1,lj belongs to a first group of intermediate values and z2,rj belongs to a second group of intermediate values, so that when uj changes to uj and also no error occurs, z1,lj changes to z1,lj and z2,rj changes to z2,rj, and the fifth subcircuit is designed such that it outputs ujcor=uj⊕1 when Δz1,lj=Δz2,rj=1.

17. The decoder as claimed in claim 16, wherein the third subcircuit has k+m binary inputs for inputting k possibly erroneous data bits and u′=u1′, . . . , uk′ and m possibly erroneous check bits c′=c1′, . . . , cm′ and m binary outputs for outputting changes Δc=Δc1, . . . , Δcm determined from u′ and c′,
the fourth subcircuit has m binary inputs for inputting the changes Δc=Δc1, . . . , Δcm and M binary outputs for outputting the changes determined from Δc for intermediate values Δz=Δz1, . . . , ΔzM,
and the fifth subcircuit has k+M inputs for inputting the k possibly erroneous data bits u′=u1′, . . . , uk′ and M changes in the intermediate values Δz=Δz1, . . . , ΔzM and has k′, where k′≦k, outputs for outputting a subset of k′ from a plurality of k corrected data bits u1cor, . . . , ukcor.

18. The decoder as claimed in claim 16, wherein the change Δui in the data bit ui, where 0≦i≦k, can be presented as a product of at least 2 changes in the intermediate values.

19. The decoder as claimed in claim 16, wherein at least two subcircuits from a set comprising the third subcircuit, the fourth subcircuit and the fifth subcircuit of the decoder are located on a same support structure.

20. A method for determining m check bits c1, . . . , cm for k data bits u1, . . . , uk, wherein the method comprises:
determination of M intermediate values from the k data bits, so that there is an association between a determined pair of intermediate values for each data bit uj that is to be corrected, so that a change in the pair of intermediate values indicates that the j-th data bit uj has changed to ūj when only one data bit from the k data bits {u1, . . . , uk} has changed to its negated value, and
transformation of the intermediate values into the m check bits c1, . . . , cm,
wherein the intermediate values are transformed into the m check bits such that the m check bits associated with the intermediate values determined from the k data bits and the m check bits associated with the intermediate values determined from the k data bits inverted in a respective bit from the k data bits that are to be corrected differ in pairs, where m<M and M<k.