Device and method for error correction and protection against data corruption

A device for protecting a data word against data corruption includes first and second determiners. The first determiner is configured to determine an error correction code cvA associated with a data word a so that cvA=aAT, with A being a generator matrix of a linear systematic base correction code, the columns of which enable performance of an x-bit error correction on replica of the data word a and the associated error correction code cvA. The second determiner is configured to determine an extended error correction code cvE so that (cvA|cvE)=aFT, with F being an extended generator matrixof an extended linear systematic correction code, the columns of which enable, using the extension error correction code cvE, performance of an y-bit error correction, with y>x, on a replica of the data word a and the associated error correction code cvA.

TECHNICAL FIELD

Embodiments described herein relate to error correction and protection against data corruption.

BACKGROUND

Error correction is one measure for obtaining correct data from a source such as memory or a transmitter. Error correction may reduce the costs involved with implementing the data source as a higher data rate is acceptable due to the data correction capability. Such error correction is used, for example, for memory data stored in a RAM (random access memory), ROM (read only memory), cache memory, EEPROM (electrically erasable programmable read-only memory), and even hard drives, CDs (compact discs), DVDs (digital versatile discs), magnetic tapes and the like. In forward error correction, the data to be protected against data corruption is, in units of data words, for example, mapped onto codewords. In accordance with systematic codes, codewords include the data word to be protected plus some error correction code. Many such systematic codes are available, such as Reed Solomon codes, for example.

However, an error correction capability not only increases the demands imposed on the data source, but also increases the amount of data due to the addition of redundancy and the data latency due to the granularity at which the data is protected.

SUMMARY

According to an embodiment of a device for error correction, the device includes a receiver and a checker. The receiver is configured to receive a data word a and an error correction code cvAassociated with the data word a. The checker is configured to declare the data word a as being correct if cvAequals aAT, with A being a generator matrix of a linear systematic base correction code. The checker is further configured to perform, if cvAis unequal to aAT, are x-bit error correction on the data word a and the associated error correction code cvAusing columns of A in order to obtain a corrected version of the data word a and the associated error correction code cvAin the case of the x-bit error correction being successful, and assume a number of corrupted bits of the data word a and the associated error correction code cvAto be greater than x. The checker is also configured to perform, if the x-bit error correction fails, obtaining an extension error correction code cvEand performing a y-bit error correction with y>x, on the data word a and the error correction code cvAusing the extension error correction code cvEand columns of an extended matrix

F=(AE)
of an extended linear systematic correction code according to which (cvA|cvE)=aFTif the data word a, the error correction code cvAand the extension error correction code cvEwere correct.

According to an embodiment of a device for protecting a data word against data corruption, the device includes first and second determiners. The first determiner is configured to determine an error correction code cvAassociated with a data word a so that cvA=aAT, with A being a generator matrix of a linear systematic base correction code, the columns of which enable performance of an x-bit error correction on replica of the data word a and the associated error correction code cvA. The second determiner is configured to determine an extended error correction code cvEso that (cvA|cvE)=aFT, with F being an extended generator matrix

F=(AE)
of an extended linear systematic correction code, the columns of which enable, using the extension error correction code cvE, performance of an y-bit error correction, with y>x, on a replica of the data word a and the associated error correction code cvA.

According to an embodiment of a device for error correction, the device includes a receiver and a checker. The receiver is configured to receive an encrypted data word a and an error correction code cvAassociated with the encrypted data word a. The checker is configured to declare the encrypted data word a as being correct if cvA=aAT, with A being a generator matrix of a linear systematic base correction code and perform, if cvAis unequal to aAT, using columns of A, a single-bit error correction on the encrypted data word a and the associated error correction code cvAin order to obtain a corrected version of the encrypted data word a and the associated error correction code cvAin case of the single-bit error correction being successful, and, in case of the single-bit error correction failing, a double-bit error detection on the encrypted data word a and the associated error correction code cvAso as to regard an error of the encrypted data word a to be a double-bit error or a more-than-two-bit error. If the error of the encoded data word a is regarded as a double-bit error, the checker is further configured to request a number of further encrypted data words forming, along with the encrypted data word a, a set of w+1 encrypted data words, along with further error correction codes associated with the further encrypted data words, respectively, check all of the further encrypted data words and the further error correction codes as to whether the same are correct, request a decryption of a correct version of the further encrypted data words in order to obtain a decrypted correct version of the further encrypted data words, and form a mod-2 sum of the decrypted correct version of the further encrypted data words to obtain a decrypted correct version of the encrypted data word.

According to an embodiment of a device for protecting an encrypted data word, the device includes a determiner and an updater. The determiner is configured to determine an error correction code cvAassociated with an encrypted data word a so that cvA=aAT, with A being a generator matrix of a linear systematic base correction code, the columns of which enable performance of a single-bit error correction and a double-bit error detection on replica of the encrypted data word a and the associated error correction code cvA. The updater is configured to update a predetermined one of w further encrypted data words forming, along with the encrypted data word a, a set of w+1 encrypted data words, so as to correspond to a mod-2 sum of the predetermined encrypted data word, the encrypted data word a and a previous version of the encrypted data word a, and update the error correction code associated with the predetermined encrypted data word so as to be equal to the predetermined encrypted data word times AT.

According to an embodiment of a method of error correction, the method includes receiving a data word a and an error correction code cvAassociated with the data word a, and declaring the data word a as being correct if cvAequals aAT, with A being a generator matrix of a linear systematic base correction code. The method further includes performing, if cvAis unequal to aAT, an x-bit error correction on the data word a and the associated error correction code cvAusing columns of A in order to obtain a corrected version of the data word a and the associated error correction code cvAin the case of the x-bit error correction being successful, and assuming a number of corrupted bits of the data word a and the associated error correction code cvAto be greater than x and perform. The method also includes, if the x-bit error correction fails, obtaining an extension error correction code cvEand performing an y-bit error correction with y>x, on the data word a and the error correction code cvAusing the extension error correction code cvEand columns of an extended matrix

F=(AE)
of an extended linear systematic correction code according to which (cvA|cvE)=aFTif the data word a, the error correction code cvAand the extension error correction code cvEwere correct.

According to an embodiment of a method of protecting a data word against data corruption, the method includes determining an error correction code cvAassociated with a data word a so that cvA=aAT, with A being a generator matrix of a linear systematic base correction code, the columns of which enable performance of an x-bit error correction on replica of the data word a and the associated error correction code cvA. The method further includes determining an extended error correction code cvEso that (cvA|cvE)=aFT, with F being an extended generator matrix

F=(AE)
of an extended linear systematic correction code, the columns of which enable, using the extension error correction code cvE, performance of an y-bit error correction, with y=x, on a replica of the data word a and the associated error correction code cvA.

According to an embodiment of a method of error correction, the method includes receiving an encrypted data word a and an error correction code cvAassociated with the encrypted data word a and declaring the encrypted data word a as being correct if cvA=aAT, with A being a generator matrix of a linear systematic base correction code. The method further includes performing, if cvAis unequal to aAT, using columns of A, a single-bit error correction on the encrypted data word a and the associated error correction code cvAin order to obtain a corrected version of the encrypted data word a and the associated error correction code cvAin case of the single-bit error correction being successful, and, in case of the single-bit error correction failing, a double-bit error detection on the encrypted data word a and the associated error correction code cvAso as to regard an error of the encrypted data word a to be a double-bit error or a more-than-two-bit error. The method also includes if the error of the encrypted data word a is regarded as a double-bit error, requesting a number w of further encrypted data words forming, along with the encrypted data word a, a set of w+1 encrypted data words, along with further error correction codes associated with the further encrypted data words, respectively, checking all of the further encrypted data words and the further error correction codes as to whether the same are correct, requesting a decryption of a correct version of the further encrypted data words in order to obtain a decrypted correct version of the further encrypted data words, requesting an encryption of a mod-2 sum of the decrypted correct version of the further encrypted data words to obtain a correct version of the encrypted data word, and comparing the encrypted data word and the correct version of the encrypted data word to prove that the error of the encrypted data word a is a double-bit error.

According to an embodiment of a method of protecting an encrypted data word, the method includes determining an error correction code cvAassociated with an encrypted data word a so that cvA=aAT, with A being a generator matrix of a linear systematic base correction code, the columns of which enable performance of a single-bit error correction and a double-bit error detection on replica of the encrypted data word a and the associated error correction code cvA. The method further includes updating a predetermined one of w further encrypted data words forming, along with the encrypted data word a, a set of w+1 encrypted data words, so as to correspond to a mod-2 sum of the predetermined encrypted data word, the encrypted data word a and a previous version of the encrypted data word a, and update the error correction code associated with the predetermined encrypted data word so as to be equal to the predetermined encrypted data word times AT.

According to an embodiment of a computer readable medium storing a computer program configured to perform error correction, the computer program includes program instruction to determine an error correction code cvAassociated with a data word a so that cvA=aATwith A being a generator matrix of a linear systematic base correction code, the columns of which enable performance of an x-bit error correction on replica of the data word a and the associated error correction code cvA. The computer program further includes program instructions to determine an extended error correction code cvEso that (cvA|cvE)=aFT, with F being an extended generator matrix

F=(AE)
of an extended linear systematic correction code, the columns of which enable, using the extension error correction code cvE, performance of an y-bit error correction, with y=x, on a replica of the data word a and the associated error correction code cvA.

According to an embodiment of a computer readable medium storing a computer program configured to perform error correction, the computer program includes program instructions to receive an encrypted data word a and an error correction code cvAassociated with the encrypted data word a and program instructions to declare the encrypted data word a as being correct if cvA=aAT, with A being a generator matrix of a linear systematic base correction code. The computer program further includes program instructions to perform, if cvAis unequal to aAT, using columns of A, a single-bit error correction on the encrypted data word a and the associated error correction code cvAin order to obtain a corrected version of the encrypted data word a and the associated error correction code cvAin case of the single-bit error correction being successful, and, in case of the single-bit error correction failing, a double-bit error detection on the encrypted data word a and the associated error correction code so as to regard an error of the encrypted data word a to be a double-bit error or a more-than-two-bit error. The computer program also includes program instructions to, if the error of the encrypted data word a is regarded as a double-bit error, request a number w of further encrypted data words forming, along with the encrypted data word a, a set of w+1 encrypted data words, along with further error correction codes associated with the further encrypted data words, respectively, check all of the further encrypted data words and the further error correction codes as to whether the same are correct, request a decryption of a correct version of the further encrypted data words in order to obtain a decrypted correct version of the further encrypted data words, request an encryption of a mod-2 sum of the decrypted correct version of the further encrypted data words to obtain a correct version of the encrypted data word, and compare the encrypted data word and the correct version of the encrypted data word to prove that the error of the encrypted data word a is a double-bit error.

DETAILED DESCRIPTION

Before several embodiments for data correction and protection are outlined in more detail below, an illustrative explanation shall be given in order to motivate, and make clear, advantages of the embodiments described further below. As already mentioned above, redundancy has to be added to data which is to be protected against data corruption. The amount of redundancy to be added depends on the number of bits within a single data word, which is to be still correctable. The higher this number of bits, the more redundancy has to be added. Put differently, the mean number of bits corrupted in a data word depend on the size of the data word; the greater the data word, the higher the mean number of data bits corrupted therein. That is, the greater the size of the data words, the worse the code rate of the correction code gets, i.e. the higher the number of bits necessary in order to render the data word correctable at a certain predefined probability. However, data words of greater size result in disadvantages in terms of data latency. If, for example, merely a minor portion of the data word protected is of interest for the recipient, despite this the whole data word along with its redundancy has to be subject to the data error correction and detection capability. The below outlined embodiments yield a possibility for a better tradeoff between data protection and data latency and/or coding rate. Bit errors involving less than or equal to x bits, such as single-bit errors, can be detected and corrected data word-wisely based on the data word and its associated error correction code itself. However, bit errors involving more than these x bits, such as double-bit errors, may be corrected as well.

In accordance with one aspect of the embodiments outlined below, this is achieved by accompanying the error correction code associated with a data word via a linear systematic base correction code, with an extension error code of an extended linear systematic correction code according to which the data word a and the error correction code cvAis correct, if cvA=aAt, with A being a generator matrix of a linear systematic base correction code. An extended matrix of the extended linear systematic correction code is

F=(AE).
According to the extended linear systematic code (cvA|cvE)=aFTif the data word a, the error correction code cvAand the extension error correction code cvEwere correct. That is, the extension error correction code is not added to the data word a and the error correction code cvAcompletely anew. Rather, a hierarchy among the linear systematic base correction code in the extended linear systematic correction code is exploited, thereby decreasing the redundancy to be additionally spent for the ability of correcting further bits. By this measure, even the amount of correction overhead scales with the error statistic of the data words. In most application cases, the number of bit errors within a data word monotonically get less probable. Accordingly, at a higher probability, the error correction code cvAsuffices in order to perform the error detection or error correction if necessary. Merely in the remaining cases, the additional extension error correction code is necessary in order to attempt in correcting a higher number of bit errors.

In accordance with a further embodiment, the data words are grouped into sets of data words with merely using one extension error correction code to check some of the extension error correction codes of the data words of the respective set. This further reduces the amount of data necessary for the redundancy.

In accordance with further embodiments also described below, the tradeoff between protection capability and data latency and/or code rate increase is achieved by associating a set of encrypted data words with an error correction code cvAallowing for a single-bit error correction and a double-bit error detection, with additionally providing this set of data words with an additional data word and an additional error correction code representing a mod-2 sum of the encrypted data words and their error correction codes of that set. By this measure, single-bit errors are easily detectable and correctable without extra measures. On the other hand, a double-bit error within one of the encrypted data words is still correctable via a detour crossing the boundary between encrypted domain and decrypted domain. Thus, the latter embodiments are particularly advantageous in cases where the data words to be protected are available in an encrypted form, and where a decryption module is involved in decrypting the data words. Again, even in these latter embodiments, the amount of overhead necessary in order to gain access to the data word content is adapted to the probability distribution of the number of bit errors occurring in the data words. In many application cases, merely a few bits are corrupted. In these cases it is very likely that an encrypted data word may be corrected individually in the encrypted domain in case merely a single-bit error is present. In case of a seldom occurring double-bit error, it is at least worthwhile to try to correct the double-bit error by the detour via the encryption/decryption domain boundary using the other encrypted data words and their associated error correction codes.

FIG. 1shows a device10for error correction. The device10includes a receiver12and a checker14. Both are connected in series to each other in the order mentioned between an input16and an output18of the device10. For ease of understanding of the following description of the mode of operation of the device10, the device10is shown to be connected to memory20having stored therein data words protected by use of redundancy as outlined below and as exploited by the device10for error correction also as described below.

In particular, the mode of operation of the device10described in the foil wing with respect toFIG. 2. For ease of understanding, the description of the mode of operation of the device10ofFIG. 1focuses on the functionality of the device10with respect to the performance of error correction with respect to a specific data word stored in the memory20. Primarily, it is assumed that the data word a (22) has redundancy associated therewith and stored in memory the20as shown inFIG. 3a, although there are other possibilities as well, among which one is specifically outlined with respect toFIG. 3b.

In particular, the receiver12is configured to receive the data word a and an error correction cvA(24) associated with the data word a in step S1, thereby starting a respective process of performing an error correction on the data word a. Although in accordance withFIG. 1, the receiver12is shown and described as receiving the data word a from the memory20, alternative embodiments are possible as well, such as reception from a respective transmitter such as a wireless transmitter, or from a data bus. The data word a received in step S1may have been passed on from the memory20to the receiver12on demand, such as a demand issued by a recipient connected to the output18, which is not shown inFIG. 1, but could be a CPU (central processor unit), for instance. Alternatively, the data word a may be part of a unidirectional transmission such as a broadcast or multicast signal comprising, for instance a stream of data words a. The sort of data content represented by the data word a is also not restricted to any particular kind of information. The information transferred via the data word a may, for example, comprise program instructions or a program code, secret data such as an encryption/decryption key, personal user data, video or audio data, or other multimedia data, or any other sort of data.

The checker14is configured to check as to whether cvA=aAT, with A being a generator matrix of a linear systematic base correction code. A specific example for generator matrix A is presented in embodiments described in more detail below. Generally speaking, the linear systematic base correction code may, for example, be a linear block code allowing for an x-bit correction. In the following specific examples x=1.

In other words, the checker12assumes that the error correction code cvAassociated with the data word a as received from the memory20has been computed such that cvA=aAT. Accordingly, if neither the data word a nor the error correction cvAis corrupted, the check in step S2results in equality. In response, the checker14declares the data word a as being correct in step S3. Otherwise, the checker14is configured to perform, if cvAis unequal to aAT, an x-bit error correction on the data word a and the associated error correction code cvAusing columns of A in step S4in order to obtain a corrected version of the data word a in case of the x-bit error correction being successful, and assumes a number of corrupted bits of the data word a and the associated error correction code cvAto be greater than x if the x-bit error correction fails. As will be outlined in more detail below, the process of x-bit error correction in step S4as performed by the checker14may involve an evaluation of a syndrome or check vector corresponding to a mod-2 sum of the error correction code cvAand aATin accordance with certain rules of the x-bit error correction. Applying the rules onto this syndrome or check vector may lead to abort situations where the x-bit error correction has to be interrupted unsuccessfully, thereby making clear that more than x-bits are corrupted within the data word a. If no such abort situation occurs, the x-bit error correction may be finished successfully, thereby revealing or obtaining a corrected version of the data word a in which case the checker14may output this corrected version as the output18.

In case of the failure situation, the checker14may, as indicated above, assume that the number of corrupted bits of the data word a and the associated error correction code cvAexceeds x. In accordance with embodiments outlined in more detail below, the checker14and the base correction code may be configured such that the checker14can check whether the number of corrupted bits is ≦y, or not, and to cease processing in case of the number of corrupted bits exceeding y. However, this check is optional.

The checker14then obtains an extension error correction code cvE(26) in step S5. Similar to the above discussion with respect to the various options which exist for implementing the reception in step S1, the obtaining step S5may involve the checker14requesting, by demand, respective further information from the memory20or some other data source, or the extension error correction code26may be passed onto the receiver12automatically or unavoidably with the checker14ignoring this extension error correction code26in case the x-bit error correction failure situation does not occur.

AlthoughFIG. 3asuggests that the storage positions of data items22,24and26may be such that all these data items physically or virtually abut each other, this is not necessarily the case. The association between these data items may be guaranteed in alternative ways such as by use of same indices in separated lists, by use of pointers or the like. In other words, the association may be determined by syntax or by some other means. As will become clearer from the following description, the data word a (22) forms, along with its associated error correction code cvA(24), a systematic codeword of the afore-mentioned linear systematic base correction code, whereas the data word22along with both the error correction code cvAand the extension error correction code cvE, form a systematic codeword of another extended linear systematic correction code according to which (cvA|cvE)=aFTif the data word a, the error correction code cvAand the extension error correction code cvEwere correct. Accordingly, after step S5, the checker14performs an y-bit error correction with y>x on the data word a and the error correction code cvAusing the extension error correction code cvEand columns of an extended matrix

F=(AE)
of the extended linear systematic correction code in step S6. The result of step S6is a corrected data word a. In particular, the latter corrected data word a is correct provided the number of corrupted bits has not accidentally exceeded y.

Thus, depending on the specific type of data source, such as the memory20, it may be most likely that the process for performing error correction and detection on the data word a finishes at step S3, with the next probable finishing situation being the x-bit error correction in step S4being successful, and with the last probable situation at which the process ends, being the failure situation involving steps S5and S6. Advantageously, the amount necessary for the second-stage protection exploited in step S5and S6, merely involves a minor amount of data, namely data26, since the respective matrix F of this second-stage systematic correction code merely represents an extension of the generator matrix of the base correction code.

As will become clear from the following embodiments, the linear system base correction code may be a single-bit error-correction and double-bit error detection code with x=1 and y=2. Further, the matrix E may extend the columns of H=(A|I) such that the columns of

(AIEO)
are pair-wise different, and no sum of any pair of columns of

(AIEO)
equals another sum of another pair of columns of

(AIEO),
where the symbol I represents the unity matrix of appropriate size and 0 represents the zero matrix of appropriate size.

If the data word or the encrypted data word a is of a length of n bit and the error correction code cvAis of a length of k bit, then k and n may be selected such that k=┌ log2(n+1)┐ and the checker14may be configured such that A is a matrix with k rows and n columns.

Until now, the above discussion suggested that step S5inFIG. 2involves obtaining the extension error code26directly, i.e. in the same way as the data word a and the error correction code cvAare received. However, in the following, an alternative embodiment is described with respect toFIG. 3b, according to which the checker14is specifically configured to perform the obtaining of the extension error correction code in step S5, in a way taking into account other data words forming, along with the data word of interest, a predetermined set of data words.

As shown inFIG. 3b, the data word a of interest, i.e. the one for which the data error correction/detection is currently to be performed, forms one of a set of w data words a1to awwith, for the sake of illustration only, data word a2, for example, representing the data word a of interest, i.e. data word22as mentioned before with respect to the embodiment ofFIG. 3b. Each of these data words ai, with i=1 . . . w, has a respective error correction code cvAassociated therewith just as described with respect to the data word22with respect toFIG. 3a. All this data is accessible by the checker14when entering step S5. The checker14is configured to, in obtaining the extension error correction code cvEin step S5, request the number w−1 of remaining data words aiexcept the data word of interest already having been received in step S1, and the associated error correction codes cvAi. However, as shown inFIG. 3b, in accordance with the embodiment ofFIG. 3b, it is not necessary to render an extension error correction code cvEaccessible for, or available to, the checker14. Thus, in case of storing the data words, it is not necessary to store all these extension error correction codes cvEfor all these data words of the data set28. Rather, merely an extension error correction code check sum msc (30), with msc being the mod-2 sum of all cvE, is associated with the set28of data words aiand requested by the checker14at step S5. As already described above, these requests may be output by the checker14in the form of a demand to the memory20. Alternatively, the extension error correction code check sum msc may be forwarded to the checker14by the receiver12and the input16automatically with the checker14disregarding this information in case the x-bit error correction failure situation does not take place.

The checker14then checks all of the further data words aiand the associated error correction codes cvAias to whether same are correct or correctable by the x-bit error correction in the same manner as described above with respect to the data word of interest, such as data word a2, i.e. analogously to the description of steps S2to S4. If all of the further data words aiand the associated error correction codes cvAiare correct or correctable, i.e. cvAi=aiATholds true or merely x bit or less are corrupted, the checker14derives the extension error correction code cvEifor the correct (such as corrected by x-bit error correction) version of each of the further data words aiso as to obey (cvAi|cvEi)=aiFT. Thus, if the data word of interest was data word a2, then the checker14would perform steps S2to S4onto all pairs of data words a and associated error correction code cvAiwith i≠2. If no x-bit error correction failure situation results for any of these further data words aiwith i≠2, then all these pairs of data words aiand associated error correction codes cvAiwith i≠2 would be correct (maybe corrected) and enable a derivation of the correct version of the extension error correction code cvEiin accordance with the just mentioned formula. The checker14can then obtain the extension error correction code cvEfor the data word of interest, i.e. a2. The checker14uses a mod-2 sum of the extension error correction code cvEiof the further data words aiwith i≠2 and the extension error correction code check sum msc as the extension error correction code cvE2of the data word a2of interest. Thus, although merely a minor amount of data is to be reserved for the msc (instead of a data item26for each of the data words in set28), a correction of an y-bit error n one of the data words in set28is still possible.

However, if any of the further data words aiwith i≠2 and the associated error correction code cvAiare not correctable by the x-bit error correction, then the checker14may declare the data word a and the associated error correction code cvAas not being correctable using the y-bit error correction and the process stops at step S5. As has been described above, the checker14may be configured to, in requesting the number w−1 of further data words ai, the associated error correction code cvAiand the extension error correction code check sum msc, send read commands to the memory20to read the further data words ai, the further error correction code cvAiand the extension error correction code check sum msc from the memory20, or alternatively, some data source other than the memory20.

The checker14may be configured to support sets of data words with different w's. For example, different sets of data words may be used for different physical storage portions of the memory20. For example, the memory20may be a non-volatile memory, such as a flash memory or a EEPROM. However, the memory20may also include a combination of different types of memories, such as a selection of one or more of an RAM, ROM, flash-memory, EEPROM, hard drive, CD drive, DVD drive, magnetic tape drive or the like. For different memory types, different may be used. However, the boundary between different w's may also be placed differently, such as within the virtual domain of memory addresses or between data words concerning differing content, such as more important and less important content. In case of a transmitter as data source, the different portions associated with different w's may correspond to different portions defined by syntax, such as different layers of a scalable data stream of the like.

After having described various embodiments with respect toFIGS. 1 to 3b, a further embodiment complying with a variant according toFIG. 3band being adaptable to the variant ofFIG. 3a, is described in the following with explicit examples for the above mentioned matrices A and E, respectively. The embodiment explained below provides, just as the above-outlined embodiments do, a hierarchical and scalable error correction for memory data stored in a RAM, ROM, flash-memory, EEPROM or other types of memory such as hard drives, CD drives, DVD drives or magnetic tape drives. Single-bit errors can be detected and corrected directly after every read of a data word of interest, whereas all double-bit errors and higher-order errors are corrected after additional read operations. In this approach, fault-free data and data with single-bit errors can be read from a memory without additional read operations. The required overhead for the correction of double-bit errors can be scaled/traded with the amount of additional read operations necessary to perform the correction. The scaling is performed by use of w between the embodiment ofFIGS. 3aand3b, as will also be described below. Just as it is true for the above-outlined embodiments, the embodiment outlined below combines small read granularity and single-bit error correction with an efficient additional implementation of double-bit or higher-bit error correction. Again, the memory application merely serves for illustration purposes, and all these explicit embodiments described in the present application are also transferable to other applications where the data to be protected stems from other data sources.

In accordance with the embodiments outlined below, a specific extended double-bit error correction code is constructed that contains a stand-alone single-bit error correcting and 2-bit error detecting sub-code. Separate use of this embedded sub-code is hierarchically made to correct single-bit errors on one data granularity and to only use the extended code to correct double-bit errors on another granularity which may be larger as explained with regard toFIG. 3b. Thus, independent scaling of single-bit error correction capabilities and double-bit error correction capabilities is possible.

In the specific embodiment described below, a systematic linear code capable of single-bit error correction and simultaneously capable of double-bit error detection is used. For an n-bit input data vector a, a k-bit check vector cvAis computed by multiplying the vector a with the transpose ATof some matrix A that defines the error correction code (all in modulus-2 arithmetic): cvA=aAT.

The matrix A with k rows is now extended in a special way described further below with a matrix E with l rows to get a new matrix

The matrix F with k+l rows describes a code that can be utilized to compute a check vector cvF=aFT, which can be utilized to correct double-bit errors in a code word (a|cvA), where cvF=(cvA|cvE). The code word for the extended code is (a|cvF)=(a|cvA|cvE).

The so called control matrices used for error detection and correction are for the standard sub-code: H=(A|I) and for the extended code: R=(F|I), where the symbol I represents the unity matrix of appropriate size.

The matrix R has the form

R=(AI0E0I),
where 0 represents the zero matrix of appropriate size. The columns of the matrix R should be distinct, i.e. pairwise different.

Moreover, the matrix E is constructed in such a way that all the possible sums of any two columns of its sub-matrix

G=(AIEO)
are also pairwise different, E is chosen in such a way that the (modulo 2) sum of any two columns of G is different to the sum of any other two columns of G. Later on this will ensure that any double-bit error in a code word (a|cvA) can be identified and corrected using the code defined by matrix R.

It is noted, that errors in cvEcannot (and as will be described below need not) be identified.

The systematic linear base code according to the current specific embodiment defined by A and H respectively, is shown inFIG. 4. The extended special linear code is defined by

F=(AE)⁢⁢and⁢⁢R=(AI0E0I)=(G⁢0I),
respectively, for which a possible implementation is also shown inFIG. 4.

As described above, the sub-matrix E is chosen in such a way that the sum of any two of the first 39 columns of R is different to the sum of any other two of these columns.

The last 5 columns of R may not be included in this property. This leads to a more efficient implementation as it gets tendentially smaller. In other words, the extension error correction code cvEmay have a length of I bits, and a check matrix

R=(AIOEOI)
of the extended linear systematic correction code may have along its right-hand side outmost I columns at least one column which, added with another column of R yields a sum of a different pair of columns of R.

Advantageously, the base systematic linear code capable of single-bit error correction and double-bit error detection is embedded into the special extended code. This saves bits to be spent for msc or cvE, respectively.

As far as the possible selections of n and I is concerned, same may be selected such that log2((n+I)*(n+I−1)/2)≦n+I. Further, as mentioned before, k and n may be selected such that k=┌ log2(n+1)┐.

Although a specific embodiment is shown inFIG. 4, many alternatives exist for matrices A and E, respectively.

According to the specific embodiment, the device10may make use of the above matrices to protect memory data in the following way. Assume a block of w words with n bits each is to be stored in the memory20. For every word aiwith i=0 . . . w−1 a check vector cvFi=ai FT=(cvAi|cvEi) is computed. The following data is stored in the memory:

w extended words (ai|cvA) with n+k bits each; and

This procedure, and the resulting storing situation, is depicted inFIG. 5. In particular, the blocks inFIG. 5with solid lines indicate values written to the memory20, while the blocks with dashed lines indicate intermediate values not stored in the memory20. When a word ar is to be read from the memory20, the device10does the following:1. Read extended word (ar*|cvAr*) from memory20, where “*” indicates potentially distorted values (c.f. step S1ofFIG. 2);2. Use standard code with control matrix H=(A|I) to detect/correct errors:A) If the syndrom vector s=H (ar*|cvAr*)==0, (c.f. step S2ofFIG. 2)correct data is assumed and no further steps are necessary;the read word ar=ar* is assumed to be correct (c.f. step S3ofFIG. 2);B) If the concrete syndrom vector s=H (ar*|cvAr*)T≠0 indicates a single-bit error,a single-bit error is assumed and the single-bit error is corrected using the standard code andno further steps are necessary; the read word ar is assumed to be correct after the correction. (c.f. step S4ofFIG. 2);C) if the concrete syndrom vector s=H (ar*|cvAr*)T≠0 indicates a double-bit error,a double-bit error is assumed and the following procedure is executed: (a-c: c.f. step S5ofFIG. 2; d: c.f. step S6ofFIG. 2)a) In a loop over all w−1 remaining extended words of the block (j=0 . . . w−1; j≠r)read (aj*cvAj*).If sj=H (aj*cvAi*)T==0 or if s=H (aj*|cvAj*)T≠0 indicates a single-bit error, aj* is corrected.If sj=H (aj*|cvAj*)T≠0 indicates a double-bit error, no correction of (ar*|cvAr*) is possible, since more than two words in the block contain at least double-bit errors.Compute cvEjfrom cvFj=(cvAj|cvEj)=aj FT. (see32inFIG. 6)b) Read msc from the memory.c) Compute modulo-2-sum of msc and all cvEj(j=0 . . . w−1; j≠r) to get cvEr. (see34inFIG. 6)d) Correct error in ar* using the double-bit error correcting code R (ar*cvAr*|cvEr)T, (see36inFIG. 6)

This procedure is also depicted inFIG. 6for the example r=1.

The “If” operations performed in lines A), B), and C) above are the operations known from the evaluation of the base systematic linear code with single-bit error correction and double-bit error detection. Only the steps a) . . . d) involve the extended systematic code.

The correction scheme neither requires to protect and thus read large words, nor imposes an overly large overhead caused by a large percentage of additional check bits.

As long as none of the relatively low probable double-bit errors occurs, small words with direct single-bit error correction are read, which is especially more power efficient than to always read all bits required for double-bit error correction. Only when really a double-bit error is detected during a read operation, extra read operations may be used to perform the correction.

By adapting the number of words w in a block, the probability of being able to correct a double-bit error can be scaled independent of the correction of single-hit errors. The relative overhead (measured in required extra memory bits) for double-bit error correction compared to single-bit error correction is oecc2=//(w*(n+k)) (where “*” here indicates integer multiplication). With large w, oecc2can become very small. (For traditional codes: oecc2≈//(n+k).)

For the example code described above with n=32, k=7, l=5, and w=4: oecc2=3.2%, doubling w to w=8 gives oecc2=1.6%. This shows that the overhead oecc2on one side can be traded against the number of additional read operations in case of a double-bit error (w−1) and against the probability for the correction of a word.

The larger a block, the larger the probability that more than one of its words has a double-bit error, which makes it impossible to correct the double bit error-incriminated words.

The following variants are possible:For example, w may be set to be w=1, i.e. protection of one word only. This corresponds to the aboveFIG. 3a. Here, the advantage lays, for example, in the power saving of not always reading the full set of n+k+l bits, but only reading the l bits when it is necessary, i.e. when an double-bit error is detected in the n+k bits read first;For example, w may be set to be w=2x, i.e. block granularity “power of 2”;Different w, i.e. different block sues, for different data sections in a single memory may be used.

For an exemplary EEPROM: small w for data that is cycled (erased and re-written) very often, so that same are better protected against double-bit errors. Larger w may be used for constant data. This minimizes the overhead oecc2, and:n may be set to be n=2x, i.e. data widths “power of 2”;the data words need not to be stored in a memory, but instead, data in a communication could be protected, such as data on a data bus, on a chip or the like.

Any inversion of a set of bits consistently done during writing and during reading of the data does not harm the scheme. This can be employed to e.g. make a completely erased memory ECC-clean. Further, an even deeper embedding of code may be achieved. That is, more levels of hierarchy than two levels may be provided.

For all the above-outlined embodiments, and also for the following embodiments, these embodiments relay be used in connection with flash or EEPROMs. Further, with respect to the device10and its internal elements, namely the receiver12and the checker14, the same may be implemented by dedicated hardware, by a CPU with suitable software or by any other combination of hardware or software such as, for example, firmware, i.e. programmable hardware such FPGA or the like.

Before turning to another embodiment, reference is made toFIGS. 7 and 8to describe embodiments of devices for protecting a data word against data corruption in a way so that the protection is exploitable by any of the above-mentioned embodiments. The mode of operation in protecting a data word has briefly been mentioned in the above discussion ofFIG. 5with respect to the treatment of a whole set of data words, but despite this, specific embodiments for a device for protecting a data word against data corruption are presented inFIGS. 7 and 8.

FIG. 7shows a device40for protecting a data word against data corruption. The device40includes a first determiner42and a second determiner44which are connected in series between an input46and an output48of the device40in the order mentioned. As illustrated inFIG. 7, memory20may be connected to the output48. That is, the device40may, as just mentioned, be configured to store data word a into the memory20along with an error correction code cvAsuch that the device10ofFIG. 1may perform the above-mentioned error correction/detection thereupon. The first determiner42may be configured to determine an error correction code cvAassociated with the data word a so that cvA=aAT, with A being a generator matrix of a linear systematic base correction code, the columns of which enable performance of an x-bit error correction on replica of the data word a and the associated error correction code cvA. The second determiner44, in turn, may be configured to determine the afore-mentioned extended error correction code cvEso that (cvA|cvE)=aFT, with F being an extended generator matrix

F=(AE)
of an extended linear systematic correction code, the columns of which enable, using the extension error correction code cvE, performance of the y-bit error correction, with y>x, on replica of the data word a and the associated error correction code cvA.

As illustrated inFIG. 7, the first and second determiners42,44may be configured to perform the respective determination in response to a write command stemming from, for example, a CPU or the like, wishing to store the data word a into the memory20. In other words, the write command may instruct the data word a to be written into the memory20. The device40may be configured to write the error correction code cvAto the memory20along with data word a.

FIG. 8shows a device40′ differing from the device40ofFIG. 7in that the device40′ includes a check sum updater50connected between the second determiner44and the output48. The check sum updater50may be configured to update an extension error correction code check sum msc (30) so as to correspond to a mod-2 sum of a previous version of the extension error correction code check sum, i.e. the precious value thereof which is to be updated, the extension error correction code cvEand a previous version of the extension error correction code cvEassociated with the data word a. Consider, for example, data word a2ofFIG. 3bis to be overwritten according to a certain write command, a2is the previous version, which is overwritten, and a2′ is the current version to be written. Then, the check sum updater50overwrites the old version of data word a2′ with a new version A2and overwrites the corresponding error correction code using the new version cvA2corresponding to the new data word a2and overwrites and updates msc with the mod-2 sum of the old version of msc′, the extension error correction code cvE2′ corresponding to the previous version of the data word a2′ obtained so that (cvA2′|cvE2′)=a2′FTand the extension error correction code cvE2obtained such that (cvA2|cvE2)=a2FT, i.e. msc is updated so that msc→msc⊕cvE2⊕cvE2′. Thus, the device40′ is able to store the data words of a set28individually without having to recalculate all the extension error correction codes cvEfor all the other data words as well. Rather, merely the extension error correction codes of the old and new versions of the data word of interest of set28are calculated and modulo-2 added to the old version of msc to be updated.

FIG. 9shows an embodiment of a system in which devices in accordance with embodiments as described above and as described below may be employed. The system includes a memory50, such as the memory20mentioned before, a CPU52and an ECC (error correction code) generation/checking/correction unit54which corresponds to, in case of merely read capabilities with respect to the memory50, the device10, and in accordance with merely write capabilities, to the device40or the device40′, and in case of read and write capabilities, to a combination of the aforementioned devices. that the ECC unit54may similarly be implemented in accordance with any of the below-outlined devices in accordance with the embodiments described next. The CPU52is connected to the memory50via an address bus56, the ECC unit54is connected into a data path between the memory50and the CPU52. In particular, an data bus58connects the CPU52and the ECC unit54, while a n+k data bus60may connect the memory50and the ECC unit54with some serial measure being used to update the msc value in case of embodiments ofFIG. 3b, or the data bus60may be n+k +l-bits wide in case ofFIG. 3a, for example.

Turning now toFIG. 10, additional embodiments are described further below. In accordance with these embodiments, encrypted data words are protected. Again, the embodiments outlined below are primarily described with respect to stored encrypted data words although all these embodiments are easily transferable to applications where the data words are supplied by some other source such as by transferal on some data bus within a controller or the like. Generally, all of the statements regarding the generality of certain entities which occur in both the embodiments ofFIGS. 1 to 8on the one hand, andFIGS. 10 to 13on the other hand, shall also apply to the embodiments outlined below, i.e. the embodiments ofFIGS. 10 to 13. This is, for example, true for all the statements regarding w, the memory type, the properties of A and the like.

With this understanding,FIG. 10shows a device80for error correction which includes a receiver82and a checker84connected in series and in the order mentioned between an input86and an output88of the device80. Again, the memory20is shown as being connected to the input86as an example for a data source of the encrypted data words entering the input86.

The encrypted data words could be indicated by the symbol “a”, as this is the actual data, or the data in that domain, which is subject to data correction/detection. However, in order to keep the conformity with the afore-mentioned embodiments from the perspective of a recipient of the content of these encrypted data words, which is necessarily interested in the decrypted information of the data words rather than their appearance in the encrypted domain, the encrypted data words are denoted in accordance with a slightly different notation, namely as “ENC(a(0))”, for example, as far as decrypted data word a(0) is concerned, where the function “ENC” shall represent the encryption function leading from the decryption data word a(0) to the encrypted data word ENC(a(0)), with ENC−1indicating the inverse thereof. The encryption and decryption functions may be highly non-linear functions. Accordingly, a single-bit error in an encoded data word, necessarily results in a multi-bit error in the decrypted domain.

As shown inFIG. 10, the checker84includes a request connection90to the memory20in order to request the provision of further encrypted data words as will be outlined in more detail below. The output88is connected to a decryption device92forming an interface between the encrypted domain94within which the memory20is positioned, and a decrypted domain96within which the recipient of the data word for which the error correction is performed, is positioned, such as, as outlined above, a CPU or the like.

As illustrated by parenthesis inFIG. 10, the decryption device92may also be capable of performing encryption. The checker84is also connected via a request connection94to the decryption device92in order to request decryption of a certain encrypted data word as will be outlined in more detail below. The decryption device92may output the decrypted data words the decryption of which has been requested the checker84, to the checker84via a data connection96. Similarly, the decryption device92can output decrypted versions of encrypted data words to an output98via a data connection100for encrypted data words having been identified as being correct or as having maybe a single-bit error in the encrypted domain94by the device80as will be described in more detail below. The checker84is also connected to the output98via a data line102for forwarding to the output98decrypted versions of data words which have to be subject to a double-bit correction as will be described below in further detail. As is shown by dotted lines inFIG. 10, in case of the decryption device92also having an encryption capability, the device92may receive data words to be encrypted and stored in the memory20via a data line104in order to output the respectively encrypted data words at a data output line106leading to the memory20, but having connected thereinto a device120for protecting the respective encrypted data words output by the device92. This device120includes a determiner122and an updater124connected in series to each other. Dashed line126inFIG. 10illustrates a boundary between the encrypted domain94and the decrypted domain96.

After having described an exemplary structure of the device80and its embedding into a data decryption or data encryption/decryption system along with the device92, the mode of operation of the device80is explained further below with further regard toFIGS. 11 and 12, which show the data words available to the device80along with respective error correction code, i.e. here accessibly stored in the memory20, and an exemplary process flow, respectively.

When the device80starts to error correct and perform error detection on a certain encrypted data word, a plurality of encrypted data words is available to the device80. The encrypted data words are grouped into sets of encrypted data words, an example of which is shown inFIG. 11with reference sign128. The set128has w encrypted data words ENC(a(0)), ENC(a(1)), . . . , ENC(a(w−1)) and ENC(a(w)). First w encrypted data words correspond to the set28of data words of the embodiment ofFIG. 3b. That is, all these encrypted data words carry decrypted content in form of a(0), a(1), . . . , a(w−1) and each has an error correction code cvA(0), . . . , cvA(w−1), respectively, associated therewith, so that the respective error correction code equals ENC(a(#))AT, with A being a generator matrix of a linear systematic base correction code just as previously described with respect toFIGS. 1-8. Instead of additionally providing an MSC as it was the case inFIG. 3b, an additional word is added to these w encrypted data words, namely the encrypted data word ENC(a(w)) forming an encrypted version of a mod-2 sum over all w encrypted data words ENC(a(0)) . . . ENC(a(w−1)) as it is shown inFIG. 11. This additional encrypted data word ENC(a(w)) also has a respective error correction code cvA(w) associated therewith, so that cvA(w)=ENC(a(w))AT. The effect of this additional encrypted data word will become clear from the following discussion ofFIG. 12.

The process starts at step S10inFIG. 12with the receiver82receiving an encrypted data word of interest along with an associated error correction code. For ease of understanding, it is assumed that this encrypted data word of interest is ENC(a(1)). The process of step S10may have been triggered by the recipient connected to the output98, such as a CPU as shown inFIG. 9, requesting a certain data word in decrypted form by sending a respective address via the address bus56to the memory50and20, respectively.

Subsequently, the checker84checks whether the error correction code cvA(1) equals ENC(a(1))ATin step S11. If so, the checker84declares the encrypted data word as being correct in step S12, whereupon the checker84may forward this encrypted data word ENC(a(1)) via the output88to the decryption device92with notifying the latter via the connection94about its correctness. The device92, in turn, decrypts the encrypted data word and sends the decrypted version thereof, i.e. a(1), to the output92via the connection100with using this outbound direction due to the correctness as indicated by the checker84via the connection94to the recipient.

If, however, the check in step S11results in inequality, the checker84performs, using the columns of A, the single-bit error correction on the encoded data word ENC(a(1)) and its associated error correction code cvA(1) in step S13as described previously with respect to step S4inFIG. 2. In case of the single-bit error correction being successful, a corrected version of the encrypted data word ENC(a(1)) and the associated error correction code cvA(1) is obtained from the single-bit error correction step S13and the checker84may act as outlined above with respect to step S12, i.e. by outputting the corrected version of the encrypted data word via the output88to the decryption device92with concurrently indicating its correctness to the device92via the connection94with the latter, in turn, decrypting the encrypted data word and outputting the decrypted version to the output98.

If, however, the single-bit error correction in step S13fails, the checker84performs a 2-bit error detection on the encoded data word ENC(a(1)) in step S14and the associated error correction code cvA(1), so as to regard an error within the encoded data word ENC(a(1)) and the associated error correction code cvA(1) to be a double-bit error or a more-than-two-bit error. If the error of the encoded data word ENC(a(1)) and the associated error correction code cvA(1) is regarded as a more-than-two-bit error, the checker84may trigger some exceptional measure in step S15to be performed. If, for example, the recipient at the output98is a CPU, the checker84may notify in step S15the CPU about the exceptional situation, namely the more-than-two-bit error in the currently inspected encrypted data word whereupon the CPU may be configured to cease a currently executed program or stop processing at all or the like. If, for example, the CPU is a controller for a security chip card, the exceptional situation of step S15may be interpreted as a fault attack onto the security controller, necessitating a cessation of further processing in order to defend the fault attack.

If, however, the error of the encoded data word ENC(a(1)) is regarded as a double-bit error, the checker84requests in step S16the number w of further encrypted data words along with their associated error correction codes, here via the connection90from the memory20, namely the encrypted data words and associated error correction codes corresponding to the other indices except one, namely 0, and 2 to w. Briefly interrupting the current description, such a double-bit error detection as mentioned in step S14may also be used between steps S4and S5inFIG. 2in order to perform step S5merely in case the more-than-one-bit error turns out to be a double-bit error and ceases the further processing without a further trial of correction in case of a more-than-two-bit error.

Upon the checker84receiving the other encrypted data words and their associated error correction codes via the receiver82upon the request in step S16, the checker84checks all of the further encrypted data words and their associated error correction codes as to whether same are correct in step S17. This check corresponds to applying step S11to all these further encrypted data words and their associated error correction codes. If all of them are correct, the checker84proceeds with requesting via the correction94a decryption of these further encrypted data words by the decryption device92with outputting the latter via the output88to the input of the decryption device92as shown in step S18. The decryption device92decrypts all these encrypted data words to obtain a(0), a(2) to a(w) and outputs the same via the data connection96to the checker84as the checker84requests such back transmission via the connection94. The checker84then forms a mod-2 sum of the decrypted correct version of the further encrypted data words in step S19, thereby obtaining a decrypted correct version, i.e. a(1), of the encrypted data word ENC(a(1)) provided the error situation of all the encrypted data words and their associated error correction codes have correctly been determined in steps S17, S14and S11, respectively.

As shown inFIG. 12, the process may stop here. However, the checker84may alternatively be configured to proceed to determine as to whether any of the just-mentioned assumptions regarding the error situations of the data as shown inFIG. 11are false. Accordingly, the checker84may be configured to request the device92to encrypt the mod-2 sum of the decrypted further encrypted data words in step S20by forwarding the mod-2 sum via the output88to the device92and instructing the device92via the connection94to send the encryption result back via the data path96. The result of step S20is a correct version of the encrypted data word ENC(a(1)) provided all assumptions are correct. Accordingly, the checker84is able to check in step S21as to whether the encrypted data word ENC(a(1)) as obtained via the input86, in fact merely deviates at two bit positions from the encrypted version of the mod-2 sum as obtained from the device92via the data connection96. If this is the case, the checker84may allow for further processing in step S22, whereas the checker84may request exceptional measures to be taken in step S23in case of the deviation exceeding the number of two bit positions. For example, the checker84may be configured to output an alarm signal resulting in disabling of cryptographic functions of the device, for example. The same may apply to step S15.

Of course, the check in step S17may reveal that not only the encrypted data word of interest, i.e. ENC(a(1)) is incorrect, but also one of the other encrypted data words of set128. In this case, the checker84may either take an exceptional measure in step S24directly without any further trial to correct any of these further encrypted data words, alternatively, the checker84may be configured to perform an x-bit error correction in step S25on all those encrypted data words, which turned out to be incorrect in test817, which corresponds to step S11. According to the latter alternative, the process may proceed with step S24, in case the single-bit error correction in step S25failed for any of these further encrypted data words (with indices0,2,3, . . . w), and with step S18in case all single-bit error corrections in step S25were successful.

As indicated above, the system ofFIG. 10may also include a device120for protecting an encrypted data word, encrypted by the device92upon a request for storing plain text data words entering via the input104and having been encrypted by the device92. Before explaining a possible configuration of the device120, in accordance with an alternative embodiment, the system shown inFIG. 10does not include the device18, but merely the device124, protecting the data, the system having, accordingly, merely the data generation capability, rather than the data retrieval capability described above. In the latter case, the unit92may merely be operative for encryption rather than decryption.

The determiner122may be configured to determine the error correction code cvA(1) associated with the encrypted data word ENC(a(1)) so that cvA(1)=ENC(a(1))ATwith, again, assuming that this encrypted data word is the data word of interest, i.e., the content of a(1) shall be stored into the memory20upon a request from some entity connected to the device92via the connection104. The updater124is configured to update a predetermined one of the w further encrypted data words, namely ENC(a(w)), so as to correspond to a mod-2 sum of the predetermined encryption data word ENC(a(1)) as obtained via the connection106, the previous version thereof as stored in the memory20and the previous version of the predetermined encrypted data word ENC(a(w)). Further, the updater124updates the error correction code cvA(w) associated with a predetermined encrypted data word so as to be equal to (result of the mod-2 sum)AT. Thus, altogether, four data items inFIG. 11change upon a request to overwrite any of the encrypted data words ENC(a(0)) to ENC(a(w−1)), merely the respective encoded data word itself is overwritten along with the error correction code thereof, which is adapted to the new content of the respective encrypted data word, and the encrypted data word ENC(a(w)) and its associated error correction code cvA(w), as has been outlined just before.

An enhancement of the embodiments described just before with respect toFIGS. 10-13combines the latter embodiments with the first two matrices defining the base systematic error correction code ofFIG. 4. The result is a special 2-bit error correction code. A first stage is formed by the single-bit error correcting and 2-bit error detecting code on word level offered by the systematic base correction code scheme involving the error correction code cvA. The second stage uses the encryption/decryption capability on block or data word set level to correct 2-bit errors detected on word level in the first stage, if no further 1-bit or 2-bit errors are seen in the other words of the block. Again, similar to the embodiment ofFIG. 3b, this results in the possibility of independent scaling of single-bit error correction capabilities and double-bit error correction capabilities.

In particular, the generator matrix A ofFIG. 4may be used to form the 1-bit error correcting and 2-bit error detecting code according to cvA=aATfor all w+1 word shown inFIG. 11with a block containing, as indicated above, w data word+1 EDC word. Accordingly, w+1 extended words are stored in the memory20, namely (ai|cvAi) with n+k bits each (or an encrypted version thereof, respectively). InFIG. 11, for example, all blocks with solid lines indicate the values written to the memory20, respectively.

In order to retrieve a certain extended word comprising the encrypted data word and its associated error correction code, the following process may be used with respect toFIG. 13with, however, the correspondences toFIG. 12being indicated in parentheses:Read extended word (ar*|cvAr) from memory20(“*” means potential distortion) (c.f. S10) (inFIG. 13ar* is ENC(a(1))**);Use code with control matrix H=(A|I) to detect/correct errors:1.If syndrom vector s=H (ar*|cvAr*)T==0, correct data is assumed and no further steps are necessary; read word ar=ar* is assumed to be correct (c.f. S12);2. If syndrom vector s=H (ar*|cvAr*)T≠0 indicates single-bit error, a single-bit error is assumed and corrected using sub-code and no further steps are necessary; read word ar is assumed to be correct after the correction (success alternative);3. If syndrom vectors s=H (ar*|cvAr*)T≠0 indicates double-bit error (c.f. S14), a double-bit error is assumed and the following procedure is executed:a. In a loop over all w remaining extended words of the block (j=0 . . . w; j≠r)read (aj*|cvAj*) (c.f. S16)If sj=H (aj*|cvAj*)T==0, aj* is correct (c.f. S17);If sj=H (aj*|cvAj*)T≠0, no correction of (ar*|cvAr*) is performed, since too many errors in block→alarm (c.f. S24);b. Compute mod-2-sum of all ENC−1(aj) (j=0 . . . w; j≠r) to get ENC−1(ar_new*) (c.f. S18, S19);c. Check if (ENC(ENC−1(ar_new*))|cvAr—new*) and (ar*|cvAr*) differ in exactly 2 bit positions (c.f. S20, S21), then use ar=ar_new* (c.f. S22), else→alarm (c.f. S23).

In the above embodiments, although the other [ENC(a(x))|cvA(x)] could contain ECC1 errors, the need to be ECC-clean is higher to keep maximum security of the scheme.

Accordingly,FIG. 13shows a station of reading the memory20when [ENC(a(1))**|cvA(x)**] contains a double-bit error: blocks with solid lines indicate values stored in the memory20, blocks with dotted lines indicate intermediate computed values used to correct the double-bit error.

The memory overhead is as follows:

bits per w-word block for 1-bit error correcting code:(32+1)*w+33

bits per w-word block for 2-bit error correcting code:(32+7)*w+39→overhead=(6w+6)/(33w+33)w=8: overhead=18.2%.

Other embodiments include the computer program for performing one of the methods described herein, stored on a machine readable carrier.

A further embodiment is, therefore, a data carrier (or a digital storage medium, or a computer-readable medium) having, recorded thereon, the computer program for performing one of the methods described herein. The data carrier, the digital storage medium or the recorded medium are typically tangible and/or non-transitionary.

A further embodiment is, therefore, a data stream or a sequence of signals representing the computer program for performing one of the methods described herein. The data stream or the sequence of signals may for example be configured to be transferred via a data communication connection, for example via the Internet.

A further embodiment includes a processing means, for example a computer, or a programmable logic device, configured to or adapted to perform one of the methods described herein.

A further embodiment includes a computer having installed thereon the computer program for performing one of the methods described herein.

Terms such as “first”, “second”, and the like, are also used to describe various elements, regions, sections, etc. and are also not intended to be limiting. Like terms refer to like elements throughout the description.