PROCESSING OF DATA

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method, comprising:
 identifying data to be processed; and
processing the data using an error code,wherein the error code comprises an Hmatrix with n columns and m rows,wherein the columns of the Hmatrix are different,wherein componentbycomponent XOR sums of adjacent columns of the Hmatrix are different from one another and from all columns of the Hmatrix, andwherein componentbycomponent XOR sums of nonadjacent columns of the Hmatrix are different from all columns of the Hmatrix and from all componentbycomponent XOR sums of adjacent columns of the Hmatrix.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and associated apparatus is disclosed for processing data by means of an error code, wherein the error code has an Hmatrix with n columns and m rows, wherein the columns of the Hmatrix are different, wherein componentbycomponent XOR sums of adjacent columns of the Hmatrix are different from one another and from all columns of the Hmatrix and wherein componentbycomponent XOR sums of nonadjacent columns of the Hmatrix are different from all columns of the Hmatrix and from all componentbycomponent XOR sums of adjacent columns of the Hmatrix.
0 Citations
No References
No References
20 Claims
 1. A method, comprising:
identifying data to be processed; and processing the data using an error code, wherein the error code comprises an Hmatrix with n columns and m rows, wherein the columns of the Hmatrix are different, wherein componentbycomponent XOR sums of adjacent columns of the Hmatrix are different from one another and from all columns of the Hmatrix, and wherein componentbycomponent XOR sums of nonadjacent columns of the Hmatrix are different from all columns of the Hmatrix and from all componentbycomponent XOR sums of adjacent columns of the Hmatrix.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
 16. An apparatus for processing data by means of an error code, wherein the error code has an Hmatrix with n columns and m rows, wherein the apparatus comprises:
a memory circuit comprising instructions; and a processing circuit that is configured to retrieve and execute the instructions, and upon execution of the instructions is configured to; determine the error code in accordance with the Hmatrix, wherein the columns of the Hmatrix are different, wherein componentbycomponent XOR sums of adjacent columns of the Hmatrix are different from one another and from all columns of the Hmatrix, and wherein componentbycomponent XOR sums of nonadjacent columns of the Hmatrix are different from all columns of the Hmatrix and from all componentbycomponent XOR sums of adjacent columns of the Hmatrix.  View Dependent Claims (17, 18, 19, 20)
1 Specification
This Application claims priority to German Application No. 10 2018 126 685.5, filed on Oct. 25, 2018, the contents of which are hereby incorporated by reference in their entirety.
The processing of data that is mentioned here relates in particular to the error detection and error correction of data stored in a memory.
This disclosure improves existing approaches to error correction and/or error detection of data stored in a memory.
In one embodiment, a method is proposed for processing data by means of an error code, wherein the error code has an Hmatrix with n columns and m rows,
 wherein the columns of the Hmatrix are different,
 wherein componentbycomponent XOR sums of adjacent columns of the Hmatrix are different from one another and from all columns of the Hmatrix, and
 wherein componentbycomponent XOR sums of nonadjacent columns of the Hmatrix are different from all columns of the Hmatrix and from all componentbycomponent XOR sums of adjacent columns of the Hmatrix.
In one embodiment, it is in particular advantageous that a processing speed for correcting and detecting errors can be significantly increased in comparison with known solutions.
One embodiment is that a number of all components of a column is less than the smallest whole number that is greater than 2.log 2 n.
One embodiment is that the error code is an errordetecting or an errorcorrecting and errordetecting code.
One embodiment is that at least two componentbycomponent XOR sums of nonadjacent columns of the Hmatrix are not different.
One embodiment is that the error code has a length of n bits with m check bits and nm payload bits.
One embodiment is that the error code is used
 to correct 1bit errors,
 to correct adjacent 2bit errors, and
 to detect nonadjacent 2bit errors.
One embodiment is that a syndrome generator for forming an mcomponent error syndrome is determined in accordance with the Hmatrix.
One embodiment is that the syndrome generator is implemented as a combinatorial circuit having n inputs and m outputs.
One embodiment is that there is provision for a correction value formation circuit or unit that uses the mcomponent error syndrome provided by the syndrome generator to form correction values for erroneous bit positions.
One embodiment is that n≥2m/2.
One embodiment is that the Hmatrix is part of an extended Hmatrix.
One embodiment is that the extended Hmatrix is determined as follows:
 the Hmatrix is duplicated into an original Hmatrix and a duplicate Hmatrix, wherein an intermediate column having m zeroes is inserted between the original Hmatrix and the duplicate Hmatrix,
 the original Hmatrix has two rows having n zeroes added to it,
 the duplicate Hmatrix has one row having n ones and a further row added to it, wherein the further row is determined by
 a bit combination comprising n bits according to 1010 . . . 10, if n is evennumbered, or
 a bit combination comprising n bits according to 1010 . . . 1, if n is oddnumbered, and
 the intermediate column comprising m zeroes has one column [0,1]T added to it.
One embodiment is that the Hmatrix is adapted by deleting at least one first and/or at least one last column.
One embodiment is that the Hmatrix is modified by a linear combination of its rows.
One embodiment is that the processing of the data comprises writing to a memory or reading from a memory.
Furthermore, an apparatus is proposed for processing data by means of an error code, wherein the error code has an Hmatrix with n columns and m rows, wherein the apparatus comprises a processing circuit or unit that is configured to determine the error code by way of the Hmatrix,
 wherein the columns of the Hmatrix are different,
 wherein componentbycomponent XOR sums of adjacent columns of the Hmatrix are different from one another and from all columns of the Hmatrix, and
 wherein componentbycomponent XOR sums of nonadjacent columns of the Hmatrix are different from all columns of the Hmatrix and from all componentbycomponent XOR sums of adjacent columns of the Hmatrix.
The processing circuit or unit mentioned here may be embodied in particular as a processor unit and/or an at least partially hardwired or logic circuit arrangement that is configured for example such that the method as described herein is performable. The processing circuit or unit can be or comprise any type of processor or calculator or computer having accordingly necessary peripherals (memory, input/output interfaces, input/output devices, etc.).
One embodiment is that the processing circuit or unit comprises a syndrome generator that outputs syndromes on the basis of the Hmatrix.
One embodiment is that the apparatus comprises a memory or is couplable to a memory, wherein the processing of the data comprises writing to the memory or reading from the memory.
One embodiment is that a number of all components of a column is less than the smallest whole number that is greater than 2.log 2 n.
One embodiment is that at least two componentbycomponent XOR sums of nonadjacent columns of the Hmatrix are not different.
The above explanations relating to the method apply to the apparatus accordingly. The apparatus may be embodied in one circuit or component or in a manner distributed in multiple circuits or components.
The aforementioned functionality is also achieved by means of a system comprising at least one of the apparatuses described here.
Furthermore, a nontransitory computer program product is proposed that is loadable directly into a memory of a digital computer, comprising program code parts suitable for performing steps of the method described here.
A nontransitory computerreadable storage medium is also specified comprising computerexecutable instructions suitable for the computer to perform steps of the method described here.
The properties, features and advantages of this disclosure that are described above and the way in which they are achieved are described below in connection with a schematic description of exemplary embodiments that are explained more specifically in connection with the drawing, in which:
When storing data in memory cells of a memory and when reading from the memory, errors can occur. The data stored in the memory can also become distorted. By way of example, the memory may be exposed to radiation (e.g. from space or terrestrial radiation) that distorts the content of memory cells, in particular the content of adjacent memory cells.
As such, the error occurring may be a 1bit error that distorts 1 bit in a memory cell. Accordingly, a 2bit error distorts two memory cells.
Memory cell errors in two adjacent memory cells can occur more frequently in this case than memory cell errors in two memory cells that are not adjacent.
To achieve the most reliable storage of data possible in a memory while at the same time making little effort, it is for example an aim
 to correct memory cell errors in one memory cell,
 to correct memory cell errors in two adjacent memory cells, and
 to reliably detect memory cell errors in two nonadjacent memory cells, and to need as few memory cells having check bits as possible for this.
If data are read from the memory and a read datum from one memory cell is erroneous, then this is a 1bit error. If there are two errors in two adjacent memory cells, then this is an adjacent 2bit error. If there are two errors in two nonadjacent memory cells, this is consistent with a nonadjacent 2bit error.
By using an error code, a solution is provided that is used to correct 1bit errors and adjacent 2bit errors, and to detect nonadjacent 2bit errors. It is in particular an option for corrigible errors to be detected (before correction).
It may be advantageous that rarely occurring nonadjacent 2bit errors are detected (and not corrected), but more often occurring adjacent 2bit errors are detected and corrected, since fewer check bits are needed in such a scenario than for correcting all (including nonadjacent) 2bit errors.
The error code referred to can be an errorcorrecting and/or errordetecting code.
The data to be stored can be stored in the memory in a manner coded as codewords of the error code. By way of example, the data to be stored can comprise data bits that have check bits added to them, so that the data bits and the check bits form a codeword of the error code or are part of such a codeword.
Linear codes are considered in exemplary fashion below as error codes. An error code can be described as a linear code by an Hmatrix, for example, an (m,n) matrix being able to be used as an Hmatrix for an error code of length n having m check bits.
The Hmatrix determines for example a syndrome generator that determines error syndromes for errors that occur.
On the basis of the error syndromes, the applicable errors can be corrected and/or detected by using a combinatorial circuit, for example. By way of example, bit positions to be corrected may be associated with the error syndromes on the basis of a combinatorial circuit.
The Hmatrix can be used to determine a method for correcting 1bit errors and adjacent 2bit errors and for detecting nonadjacent 2bit errors.
If the Hmatrix has m rows and n columns, this determines an error code having m check bits. The length of the error code is equal to the number n of columns of the Hmatrix.
The Hmatrix of the error code is an (m, n) matrix and can be described as
where h1, h2, hn denote the n columns of the Hmatrix, which each have m binary components.
If v=v1, . . . , vn is a code vector (also referred to as a codeword) of the error code under consideration, then
H·v=0. (2)
If v′ is a vector where
v′=v+e=v_{1}+e_{1},v_{2}+e_{2}, . . . ,v_{n}+e_{n},
then
H·v′=H·(v+e)=H·e=s. (3)
In this case, the vector e =e1, . . . , en denotes an error vector describing a possible deviation of the erroneous vector v′ from the correct vector v. The vector v′ is therefore the disturbed or erroneous (code) vector.
The vector v′ differs from the vector v in the components in which the applicable components of the error vector e are equal to 1, and the vector v′ does not differ from the vector v in the components in which the components of the error vector e are equal to 0.
If, for example for i∈{1, . . . , n}, the ith component ei of the error vector e is equal to 1, the ith bit vi of the vector v has been disturbed by an error in the ith bit
v′_{i}=v_{i}+1
of the vector v′. If for example the jth component ej of the error vector e is equal to 0, then the jth bit of the vector v has not been disturbed by an error of the vector v′, and: v′j=vj.
If precisely one component of the error vector e is equal to 1, then there is a 1bit error. If precisely two components of the error vector e are equal to 1, then there is a 2bit error. If precisely two components of the error vector that are equal to 1 are adjacent, then there is an adjacent 2bit error. If precisely two components of the error vector are equal to 1 that are not adjacent, then there is a nonadjacent 2bit error.
The operation “+” denotes modulo 2 addition or the logic XOR operation (XOR stands for ExclusiveOr).
If a vector is arranged to the right of a matrix, then it must be interpreted as a column vector. If the aim is to highlight that the vector v is represented as a column vector, then this can be expressed by vT.
Equation (3) defines an error syndrome s. The error syndrome s is represented in equation (3) as a column vector sT=[s1, . . . , sm]T having m components s1, . . . , sm.
In accordance with the elements of the Hmatrix, the components s1, . . . , sn of the error syndrome s are determined by
An implementation of equations (4) to (6) to determine the components s1 to sm of the error syndrome s can also be referred to as the syndrome generator. An implementation of these equations can be achieved by means of a standard synthesis tool, for example.
If all 1bit errors are corrected by using an error syndrome of an error code, all 1bit errors are distinguishable on the basis of the error syndrome and the error syndromes of the different 1bit errors are different in pairs. The different error syndromes of the n possible 1bit errors are then equal to the n columns h1 to hn of the Hmatrix according to equation (1). In this case, the Hmatrix is determined such that all n columns are different in pairs.
If all 1bit errors and all, including nonadjacent, 2bit errors are corrected by using an error syndrome of an error code, then all error syndromes of the n different 1bit bit errors and all error syndromes of the
different 2bit errors are different in pairs. The different error syndromes of the n possible 1bit errors are then equal to the n columns h1 to hn of the Hmatrix according to equation (1), and the error syndromes of the
different 2bit errors are then equal to the componentbycomponent XOR sums of the
different combinations of two columns of this Hmatrix.
A known 2biterrorcorrecting code is a 2biterrorcorrecting BCH code that allows all 1bit errors and all 2bit errors to be corrected. A 2biterrorcorrecting BCH code for correcting any 1bit errors and any 2bit errors is described in [Rao, T.; Fujiwara, E.: “Error Control codes for Computer Systems”, Prentice Hall 1989, pages 97 to 99], for example, which is hereby incorporated by reference in its entirety.
For a 2biterrorcorrecting BCH code, all columns of the applicable Hmatrix and all componentbycomponent XOR sums of all pairs of columns of the Hmatrix need to be different in pairs. The number m of the components of the error syndrome, which is equal to the number of check bits of the error code, then needs to be at least of such a magnitude that
This is necessary so that all errors to be corrected correspond to different error syndromes and can be distinguished on the basis of their error syndromes. The number m of components of the error syndrome is equal to the number of check bits of the error code in this case.
For a known 2biterrorcorrecting BCH code of length n, the number m of the at least necessary check bits is equal to the smallest positive whole number that is greater than 2.log 2 n, that is to say that in this case
m>2·log_{2 }n.
If the aim is to correct only the 1bit errors and the adjacent 2bit errors by using an error code, then it may be disadvantageous if all
error syndromes for 1bit errors and for any 2bit errors are different in pairs, as is the case for the 2biterrorcorrecting BCH code, because this could require more check bits than for correcting the 1bit errors, for correcting adjacent 2bit errors and for detecting nonadjacent 2bit errors.
The limitation that nonadjacent 2bit errors are merely supposed to be detected but do not need to be corrected means that the number of check bits needed can be reduced.
This is advantageous in particular because memory cells are also needed for the check bits.
In particular, it is proposed that the n+n−1 error syndromes for the n possible 1bit errors and for n−1 adjacent 2bit errors are different in pairs and that the error syndromes of all nonadjacent 2bit errors are only different from the error syndromes of the 1bit errors and from the error syndromes of the adjacent 2bit errors.
There is thus a first group of error syndromes for 1bit errors and a second group of error syndromes for adjacent 2bit errors. The error syndromes of the first group need to differ from one another and the error syndromes of the second group need to differ from one another and from the error syndromes of the first group. Furthermore, there is a third group of error syndromes for nonadjacent 2bit errors; the error syndromes that the third group contains need only be different from the error syndromes of the first group and the second group, but the error syndromes of the third group do not need to be different from one another.
Error syndromes of pairs of different nonadjacent 2bit errors may be equal to one another in this example. If error syndromes of different pairs of nonadjacent 2bit errors are equal to one another, then this allows the number of error syndromes needing to be distinguished to be reduced such that fewer check bits are necessary than for a 2biterrorcorrecting BCH code.
Therefore, it is in particular an advantage of the approach described here to allow correction of 1bit errors and of adjacent 2bit errors and to detect errors in nonadjacent 2bit errors, the intention being for as few check bits as possible to be used for this.
The number of check bits for an Hmatrix is then smaller than the number of check bits for an Hmatrix of a 2biterrorcorrecting BCH code having the same number of columns. Accordingly, a syndrome generator resulting therefrom has fewer outputs than a corresponding syndrome generator for the 2biterrorcorrecting BCH code.
In particular, a method for correcting 1bit errors and adjacent 2bit errors and for detecting nonadjacent 2bit errors in particular when reading bits stored in memory cells is proposed. The method uses an error code determined by an Hmatrix. This Hmatrix is described in exemplary fashion below.
In this case, it should be mentioned that the Hmatrix is used as an exemplary notation to describe any linear error code. The Hmatrix is then used to illustrate the properties that the error code needs to have in order to be able to be used for the aforementioned correction and detection. Theoretically, other forms of description are possible instead of the Hmatrix. In other words: it is possible for any linear error code that has the properties demanded here, namely being able to correct 1bit errors and adjacent 2bit errors and detect nonadjacent 2bit errors, to be mapped onto an Hmatrix having the properties described here. Therefore, the Hmatrix is a unique reference for the error codes proposed herein.
The Hmatrix can have multiple Hmatrices. By way of example, an Hmatrix may be determined such that special Hmatrices are provided for specific numbers of rows and columns and that further Hmatrices are derived from the provided Hmatrices for further numbers of rows and columns. Further Hmatrices can also be derived by deleting columns, for example last or first columns, from already existent Hmatrices.
Hmatrices are specified in exemplary fashion below for
 m=6 and n=11,
 m=7 and n=14 and
 m=8 and n=26,
where n indicates the number of columns and m indicates the number of rows of the Hmatrix.
Example of an Hmatrix H6,11
If m=6 and n=11, then equation (7) shows an example of a special Hmatrix H6,11
of an error code C6,11 having 6 rows, i.e. m=6 check bits, and n=11 columns (and hence n−m=5 data bits). The length of the error code C6,11 is n=11.
The smallest whole number that is greater than
log_{2 }n=log_{2 }11
is 4, because
2^{3}=8<11<2^{4}=16.
The number of rows m=6 of the Hmatrix H6,11 is less than the number 2·4=8 of rows of a 2biterrorcorrecting BCH code of length 11.
Calculation can be used to check that the Hmatrix H6,11 is determined such that all 11 columns h1 to h11 and all componentbycomponent XOR sums of the n−1=10 pairs of adjacent columns
are different in pairs. They are also different from the componentbycomponent XOR sums of the
pairs of nonadjacent columns
In this case, [110000]^{T }denotes a column vector having the components 1,1,0,0,0,0. This applies accordingly to the other column vectors.
XOR sums of two different pairs of nonadjacent columns may be equal in this case. As such, for example
h_{1}h_{3}=h_{9}+_{11}=[101000]^{T}.
The 11 columns h1 to h11 are equal to the syndromes of applicable 1bit errors, and the 10 XOR sums of the adjacent columns
h_{1}+h_{2},
h_{2}+h_{3},
h_{3}+h_{4},
h_{4}+h_{5},
h_{5}+h_{6},
h_{6}+h_{7},
h_{7}+h_{8},
h_{8}+h_{9},
h_{9}+h_{10},
h_{10}+h_{11},
are equal to the syndromes of the 10 possible adjacent 2bit errors.
The Hmatrix H6,11 is in this case determined such that the 10 error syndromes of the 10 adjacent 2bit errors are different in pairs, that they are different from all 11 error syndromes of the 1bit errors and different from all
nonadjacent 2bit errors.
Any 1bit error and any adjacent 2bit error can then be explicitly identified and corrected on the basis of its error syndrome.
The error syndromes of nonadjacent 2bit errors differ from the error syndromes of adjacent 2bit errors and from the error syndromes of the 1bit errors.
Since error syndromes of different nonadjacent 2bit errors may be equal, nonadjacent 2bit errors cannot be explicitly corrected. This is also not necessary in the present example and advantageously leads to fewer check bits being needed than in the case of a 2biterrorcorrecting BCH code.
The error code C6,11 is therefore a code of length 11 that has 6 check bits and 5 data bits, that can correct 1bit errors and adjacent 2bit errors and that can detect nonadjacent 2bit errors.
By contrast, a known 2biterrorcorrecting BCH code having 6 check bits is a code having the maximum length 7 and has only 1 data bit. Therefore, the length of the BCH code is shorter for the same number of check bits. With a length of 11, the 2biterrorcorrecting BCH code requires a number of 8 check bits. Therefore only 3 data bits remain.
The Hmatrix H6,11 can be used to determine a syndrome generator.
An errorfree codeword (code vector) referred to is
v=[v_{1}, . . . ,v_{11}],
and an erroneous, disturbed codeword (erroneous code vector) referred to is
v′=[v′_{1}, . . . ,v′_{11}]
where
v′=v+e=v_{1}+e_{1}, . . . ,v_{11}+e_{11}.
In this case, e=e1, e11 is the error vector. The modulo 2 addition or the logic XOR operation is denoted by +.
If a component of the error vector e is equal to 1, then the applicable component of the vector v′ is erroneous; if a component of the error vector e is equal to 0, then the applicable component of the vector v′ is not erroneous
The error syndrome s is determined according to
s=[s_{1}, . . . ,s_{11}]=H^{6,11}·v′. (8)
This is obtained by multiplying the Hmatrix H6,11 by the column vector v′. The vector v′ in equation (8) is a column vector.
The components of the error syndrome s can be specified as follows
s_{1}=v′_{1}v′_{7}+v′_{8}+v′_{9}+v′_{10}, (9)
s_{2}=v′_{2}v′_{7}+v′_{8}+v′_{9}+v′_{11}, (10)
s_{3}=v′_{3}v′_{7}+v′_{8}+v′_{10}+v′_{11}, (11)
s_{4}=v′_{4}v′_{7}+v′_{9}+v′_{10}+v′_{11}, (12)
s_{5}=v′_{5}v′_{8}+v′_{9}+v′_{10}+v′_{11}, (13)
s_{6}=v′_{6}+v′_{7}+v′_{9}+v′_{11}. (14)
The error detection and error correction using an error syndrome are known to a person skilled in the art. As such, the error correction can be effected for example by using a syndrome table (also referred to as “syndrome decoding table”). The syndrome table is a table describing a bijective association between the error vectors of the errors to be corrected and their bijectively corresponding error syndromes. The association between error syndromes and error vectors that is described by the syndrome table can be realized by a combinatorial circuit, for example. The components of the error syndrome are then applied to the inputs of the combinatorial circuit, the outputs of which output the components of the applicable error vector. The components el to en of the error vector e that are provided by the combinatorial circuit can be XORed with the applicable components v′1 to v′n of the possibly erroneous code vector v′ that is to be corrected, for example, in order to form the corrected values.
An example of a syndrome table is depicted in [Wickert, S. B.: “Error Control for Digital Communication and Storage”, Prentice Hall 1995, page 89], for example, which is hereby incorporated by reference.
Example of an Hmatrix H7,14
For m=7 and n=14, equation (15) shows a further example of an Hmatrix H7,14
of an error code C7,14 having 7 rows, i.e. m=7 check bits, and n=14 columns (and hence n−m=7 data bits). The length of the error code C7,14 is n=14.
The Hmatrix H7,14 is for example determined such that all 14 columns h1 to h14 and all componentbycomponent XOR sums of the 13 pairs of adjacent columns
are different in pairs. They are determined such that they are also different from the componentbycomponent XOR sums of the
pairs of nonadjacent columns
XOR sums of two different pairs of nonadjacent columns can be equal in this case.
The 14 columns h1 to h14 are equal to the syndromes of applicable 1bit errors, and the 13 XOR sums of the adjacent columns
h_{1}+h_{2},
h_{2}+h_{3},
h_{3}+h_{4},
h_{4}+h_{5},
h_{5}+h_{6},
h_{6}+h_{7},
h_{7}+h_{8},
h_{8}+h_{9},
h_{9}+h_{10},
h_{10}+h_{11},
h_{11}+h_{12},
h_{12}+h_{13},
h_{13}+h_{14},
are equal to the syndromes of the 13 possible adjacent 2bit errors. The Hmatrix H7,14 is determined such that error syndromes are different in pairs. Any 1bit error and any adjacent 2bit error can be explicitly identified and corrected on the basis of its error syndrome.
The error syndromes of nonadjacent 2bit errors differ from the error syndromes of adjacent 2bit errors and from the error syndromes of the 1bit errors.
Since error syndromes of different nonadjacent 2bit errors can be equal, nonadjacent 2bit errors cannot be explicitly corrected.
As such, for example:
h_{8}h_{12}=[1111101]^{T}+[1011111]^{T}[0100010]^{T}=
h_{2}+h_{6}=[0100000]^{T}+[0000010]^{T}.
Therefore, a 2bit error in the 8th and the 12th bit is not distinguishable from a 2bit error in the 2nd and the 6th bit.
The error code C7,14 is therefore a code of length 14 that has 7 check bits and 7 data bits, that can correct 1bit errors and adjacent 2bit errors and that can detect nonadjacent 2bit errors.
By contrast, a known 2biterrorcorrecting BCH code, if it has a length of 14, has 8 check bits and only 6 data bits. A 2biterrorcorrecting BCH code of equal length thus requires more check bits.
The smallest whole number that is greater than
log_{2 }n=log_{2 }14
is again 4 (see explanations above). The number of m=7 rows of the H matrix H7,14 is less than the number of 2·4=8 rows of a 2biterrorcorrecting BCH code of length 14.
Analogously to what has been explained above for the syndrome components s1, . . . , s6 of the Hmatrix H6,11, the syndrome equations for the syndrome components s1, . . . , s7 are determined from the Hmatrix H7,17 according to equation (15).
Example of an Hmatrix H8,26
For m=8 and n=26, equation (16) shows a further example of an Hmatrix H8,26
of an error code C8,26 having 8 rows, i.e. m=8 check bits, and n=26 columns. The length of the error code C8,26 is n=26. The error code C8,26 has (26−8=) 18 data bits.
If only 16 data bits are required, then for example the last two columns h25 and h26 of the Hmatrix H8,26 can be deleted so as to obtain an Hmatrix H8,24
H^{8,24}=(h_{1},h_{2}. . . ,h_{23},h_{24})
having 24 columns.
Calculation can be used to check that the Hmatrix H8,26 is determined such that all 26 columns h1 to h26 and all componentbycomponent XOR sums of the 25 pairs of adjacent columns
are different in pairs.
Furthermore, the
XOR sums of all pairs of nonadjacent columns are not equal to all columns and not equal to all componentbycomponent XOR sums of the adjacent columns.
The componentbycomponent XOR sums of nonadjacent columns may be identical, on the other hand. By way of example:
h_{5}+h_{7}=[00001000]^{T}+[00000010]^{T}=[00001010]^{T}=
h_{9}+h_{11}=[11111101]^{T}+[11110111]^{T}.
Therefore, a 2bit error in the 5th and the 7th bit is not distinguishable from a 2bit error in the 9th and 11th bits.
The smallest whole number that is greater than
log_{2 }n=log_{2 }26
is 5, because
2^{4}=16<26<2^{5}=32.
The number m=8 rows of the Hmatrix H8,26 is less than the number of 2·5=10 rows of a 2biterrorcorrecting BCH code of length 26.
An errorfree codeword of length n=26 is denoted by
v=[v_{1}, . . . ,v_{26}]
and an erroneous, disturbed codeword is denoted by
v′=[v′_{1}, . . . ,v′_{26}]=v+e=v_{1}+e_{1}, . . . ,v_{26}e_{26},
where e=e1, . . . , e26 is the error vector.
The error syndrome s is determined according to
s=[s_{1}, . . . ,s_{26}]=H^{8.26}·v′. (17)
The components of the error syndrome s are obtained from the rows of the Hmatrix H8,26 and the components of the disturbed codeword v′=v′1, . . . , v′26. As such, for example for the first component s1 of the error syndrome in accordance with the first row [10000000111111011011100011] of the Hmatrix H8,26,
s_{1}=v′_{1}v′_{9}+v′_{10}+v′_{11}+v′_{12}+v′_{13}+v′_{14}+v′_{16}+v′_{17}+v′_{19}+v′_{20}+v′_{21}+v′_{25}+v′_{26}. (18)
The components s2 to s8 of the error syndrome result in analogous fashion on the basis of the 2nd to 8th rows of the Hmatrix H8,26 and the components of the disturbed codeword v′.
An implementation of the components s1 to s8 of the error syndrome s allows a syndrome generator of the error code to be determined.
Exemplary embodiment: generation of further Hmatrices
An exemplary embodiment of how a first Hmatrix Hm,n having m rows and n columns can be taken as a basis for determining a second Hmatrix Hm+2,2·n+1 having m+2 rows and 2·n+1 columns will be described below. The applicable error code Cm+2,2·n+1 then has m+2 check bits. The length of the code is 2·n+1, and there are 2·n−m−1 data bits present.
As an example, m=8 and n=26 and the Hmatrix
H^{8.26}=(h_{1},h_{2}, . . . ,h_{25},h_{26}), (19)
according to equation (16) are chosen.
The first Hmatrix H8,26 according to equation (16) can be used to determine a second Hmatrix H10,53 according to
In this case, a column hzw is inserted as a column vector
having 8 components. The column vector hzw can also be referred to as an intermediate column that is inserted between the two Hmatrices H8,26.
In general, the second matrix can be determined as follows:
The original matrix Hm,n is duplicated, wherein the intermediate column hzw having m zeroes is inserted between the original matrix and the duplicate matrix.
The original matrix can have two rows comprising n zeroes each added to it.
The duplicate matrix can have one row comprising n ones and a further row added to it. The further row is determined by
if n is even, or the further row is determined by
if n is odd.
The intermediate column hzw comprising m zeroes has one column [0,1]T added to it.
In the example above, m=8 and n=26 have been chosen.
The Hmatrix Hm,n can therefore be taken as a basis for determining the Hmatrix Hm+2,2·n+1. Accordingly, the Hmatrix Hm+2,2·n+1 can be used to determine an Hmatrix Hm+4,4·n+3. This approach can be continued for further Hmatrices accordingly.
For a number of for example 6, 7 or 8 check bits, Hmatrices for determining a syndrome generator can be ascertained directly. For a larger number of check bits, for example for 10, 12, 14 or more check bits, Hmatrices for determining syndrome generators can be determined from Hmatrices already determined beforehand having a smaller number of check bits. For the purpose of matching to a different length of codewords, first columns and/or last columns of an Hmatrix ascertained in this manner can be deleted.
Modifications of Hmatrices can also be made by virtue of linear combinations of their rows, for example.
Hmatrices can also be modified by interchanging their columns, for example.
One option is that the error code described herein can be combined with other (e.g. including already known) error codes. By way of example, in particular an Hmatrix of a BCH code may be part of the Hmatrix described here.
Error Processing
First of all, a payload 101 is applied to a coding unit 102. The coding unit 102 uses an error code in order to store the payload 101 in a memory 104 in the form of codewords 103. Each codeword 103 comprises data bits and check bits.
In exemplary fashion, read access is now effected to the memory 104. A decoding unit 106 obtains a possibly erroneous codeword 105 as a result. The decoding unit 106 performs correction of a 1bit error or of a 2bit error in adjacent read memory cells (and hence adjacent bit positions) or detects a 2bit error at nonadjacent memory cells.
Therefore, an errorfree, possibly corrected, payload 107 is output that is identical to the payload 101 if no error or a 1bit error or an adjacent 2bit error has been detected. It is also possible for the decoding unit 106 to output an error indicating that a 2bit error has been detected in nonadjacent memory cells.