ERROR DETECTION OR CORRECTION USING SIGNED PARITY CODES

1 . A data storage system comprising:

a data storage assembly; and

a signed parity code error correction system configured to:

receive data from the data storage assembly, the data including a data block, a parity block, and a signature;

calculate a signature for the data block and determine whether the calculated signature matches the signature included in the received data;

calculate a parity for the data block and determine whether the calculated parity matches a parity of the received parity block;

responsive to determining that the signature and the parity matches, return the received data block;

responsive to determining that the parity does not match, generate a correction by:

reconstructing sub-blocks of the received data block using the parity block;

calculating updated signatures based on the reconstructed sub-blocks; and

responsive to determining that exactly one of the updated signatures matches the received signature, returning a corrected data block that incorporates the reconstructed sub-block corresponding to the matching updated signature.

2 . The data storage system of claim 1 , wherein the sub-blocks of the received data correspond to bounded error domains of the data storage assembly.

3 . The data storage system of claim 2 , wherein the bounded error domains are memory chips.

4 . The data storage system of claim 2 , wherein the bounded error domains are memory chip subchannels.

5 . The data storage system of any one of claims 1-4 , wherein each bit of the parity block is calculated based on one bit from each sub-block.

6 . The data storage system of any one of claims 1-5 , wherein the signature is calculated using a separable operation.

7 . The data storage system of any one of claims 1-6 , wherein the data block includes metadata.

8 . The data storage system of any one of claims 1-7 , wherein the signed parity code error correction system is further configured to:

receive a second data block for storage in the data storage assembly;

calculate a second signature for the second data block;

calculate a second parity for the second data block; and

store the second data block, second signature and second parity in the data storage assembly.

9 . A computing device comprising:

at least one processing device; and

the data storage system of any one of claims 1 - 8 .

10 . A computing device configured to:

receive data to store in a memory;

calculate a signature and parity block for the data;

cause the data, signature, and parity block to be stored in the memory; and

responsive to receiving a request for the data:

retrieve the data, signature, and parity block from the memory;

recalculate the signature and parity block from the retrieved data;

compare the retrieved signature and parity block with the recalculated signature and parity block; and

responsive to detecting a discrepancy between the retrieved signature and parity block with the recalculated signature and parity block:

use the parity block to reconstruct each sub-block of the data retrieved from the memory as a candidate correction and a candidate signature for each reconstructed sub-block;

responsive to determining that exactly one candidate correction results in a candidate signature that matches the retrieved signature, return corrected data based on the exactly one candidate correction; and

responsive to determining that there is not exactly one candidate correction that results in a candidate signature that matches the retrieved signature, return an error.

11 . The computing device of claim 10 , wherein the signature is constructed by a separable arithmetic that assigns a unique bit pattern to each bit position in the data.

12 . The computing device of claim 11 , wherein the signature is a pseudo-random permutation which is a repeatable but high entropy value which distills the overall data and metadata pattern.

13 . The computing device of any one of claims 10-12 , wherein the parity blocks are constructed by a blockwise XOR of the data, metadata, and signature bits.

14 . The computing device of claim 13 , wherein the blockwise XOR is applied in a redundant manner that allows any one missing block to be reconstructed by a XOR of remaining blocks including the parity block.

15 . The computing device of any one of claims 10-14 , wherein the data is retrieved incrementally from the memory and the signature and parity calculations are performed on portions of the data as it is retrieved reducing a complexity and latency of calculations to be performed after the data is fully retrieved.

16 . The computing device of any one of claims 10-15 , wherein signature values are calculated in parallel for each reconstructed sub-block by combining the signature of the reconstructed sub-block with previously calculated signatures for other sub-blocks.

17 . The computing device of any one of claims 10-16 , wherein candidate corrections are evaluated in parallel to determine whether any one or more than one of those candidate corrections results in a matching signature.

18 . The computing device of any one of claims 10-17 , wherein the signature is constructed based on assigning unique values to represent each different data bit position, wherein the unique values are identified by an exhaustive search of most likely fault patterns and of fault patterns with few bits, wherein the exhaustive search is used to discover faults where unique and distinctive values representing each data bit happen to combine in ways which cause two or more matches to be possible, causing one or several of those bit positions'values to be replaced with new unique and distinctive values and repeating the exhaustive search until it successfully evaluates all of the most likely fault patterns and all of the fault patterns with few bits.

19 . The computing device of any one of claims 10-18 , wherein the data stored in memory includes raw data and metadata.

20 . A method of generating a signature code, the method comprising:

assigning bit patterns to each bit position of a data block, wherein each bit pattern is unique with respect to all of the other bit patterns;

selecting a set of expected fault patterns;

conducting an exhaustive search of the selected set of expected fault patterns to identify fault patterns in which the bit patterns representing each bit position of the data block combine in ways which cause two or more matches to be possible;

replacing at least one of the bit patterns associated with a bit in fault in the identified fault patterns to be replaced with a new bit pattern; and

repeating the steps of conducting the exhaustive search and replacing at least one of the bit patterns until the exhaustive search is completed without finding a combination that causes two or more matches.

21 . The method of claim 20 , wherein the selecting a set of fault patterns includes selecting a set of fault patterns that includes most likely to occur fault patterns and fault patterns with few bits.

22 . The method of claim 21 , wherein the conducting an exhaustive search comprises applying each of the fault patterns to the data block, attempting to correct the data block using signed parity correction, and determining whether multiple candidate corrections are found.

23 . The method of any one of claims 20-22 , wherein a set of available permutations of bit patterns is significantly more numerous than the set of faults which merit the exhaustive search.

24 . The method of any one of claims 20-23 , wherein resulting bit patterns are guaranteed to correct the faults which were selected in the set of expected fault patterns.

25 . A method comprising:

receiving data;

calculating a signature for the data;

calculating a parity block, wherein the parity block is calculated for the data and the signature; and

storing the data, signature, and parity block in a memory.

26 . The method of claim 25 , wherein the parity block is calculated for the data.

27 . The method of claim 25 , wherein the parity block is calculated for the data and the signature.

28 . The method of any one of claims 25-27 , further comprising:

receiving a request for the data;

responsive to receiving the request for the data:

retrieving the data, signature, and parity block from the memory;

recalculating the signature and parity block from the retrieved data;

comparing the retrieved signature and parity block with the recalculated signature and parity block; and

responsive to detecting a discrepancy between the retrieved signature and parity block with the recalculated signature and parity block:

using the parity block to reconstruct each sub-block of the data retrieved from the memory as a candidate correction and a candidate signature for each reconstructed sub-block;

responsive to determining that exactly one candidate correction results in a candidate signature that matches the retrieved signature, returning corrected data based on the exactly one candidate correction; and

responsive to determining that there is not exactly one candidate correction that results in a candidate signature that matches the retrieved signature, returning an error.