Encoding and decoding of hamming distance-based binary representations of numbers
View Patent ↗Systems and methods for dynamically encoding and decoding binary numbers using linear-time algorithms that encode and decode Hamming Distance-Based representations for the binary numbers are described. The binary numbers may correspond with integer values, such as 64-bit, 128-bit, or 256-bit integer values. In some cases, in response to detecting that a binary number is to be stored using a particular type of memory (e.g., a phase change memory), the binary number may first be encoded using a Hamming Distance-Based representation and then the encoded data may be written to the particular type of memory. The binary number may be encoded by generating a binary string or a binary array representing the binary number such that if one bit flips within the binary string or the binary array, the maximum distortion in the number is less than a threshold amount (e.g., less than 256).
1. An apparatus, comprising:
a semiconductor memory; and
one or more control circuits configured to acquire a first set of data associated with a binary number and detect that the semiconductor memory comprises a particular type of memory, the first set of data comprises a total number of bits, the one or more control circuits configured to store the first set of data associated with the binary number in a memory buffer and generate a Hamming distance-based encoding for the first set of data associated with the binary number in response to detection that the first set of data is to be stored using the particular type of memory, the one or more control circuits configured to encode the first set of data associated with the binary number using the Hamming distance-based encoding, the one or more control circuits configured to detect that the binary number minus the total number of bits choose one is greater than or equal to zero and reduce the binary number by the total number of bits choose one in response to detection that the binary number minus the total number of bits choose one is greater than or equal to zero, the one or more control circuits configured to initialize a loop variable and an output array, the one or more control circuits configured to determine a Hamming weight for the first set of data, the one or more control circuits configured to detect that the reduced binary number is greater than or equal to the total number of bits minus one choose the Hamming weight for the first set of data and set a bit position within the output array corresponding with the loop variable to one in response to detection that the reduced binary number is greater than or equal to the total number of bits minus one choose the Hamming weight for the first set of data, the one or more control circuits configured to output the output array as the Hamming distance-based encoding for the first set of data and write the Hamming distance-based encoding for the first set of data to the semiconductor memory.
2. The apparatus of claim 1 , wherein:
the one or more control circuits configured to detect that the semiconductor memory comprises a phase change memory and generate the Hamming distance-based encoding for the first set of data in response to detection that the semiconductor memory comprises the phase change memory.
3. The apparatus of claim 1 , wherein:
the one or more control circuits configured to detect that the particular type of memory has experienced more than a threshold number of bit errors and generate the Hamming distance-based encoding for the first set of data in response to detection that the particular type of memory has experienced more than the threshold number of bit errors.
4. The apparatus of claim 1 , wherein:
the one or more control circuits configured to detect that the semiconductor memory has a threshold number of defects and generate the Hamming distance-based encoding for the first set of data in response to detection that the semiconductor memory has the threshold number of defects.
5. The apparatus of claim 1 , wherein:
the one or more control circuits configured to detect that the semiconductor memory has at least a threshold number of word line defects and generate the Hamming distance-based encoding for the first set of data in response to detection that the semiconductor memory has at least the threshold number of word line defects.
6. The apparatus of claim 1 , wherein:
the one or more control circuits configured to detect that data previously written to the semiconductor memory has experienced at least a threshold number of bit errors and generate the Hamming distance-based encoding for the first set of data in response to detection that the data previously written to the semiconductor memory has experienced at least the threshold number of bit errors.
7. The apparatus of claim 1 , wherein:
the one or more control circuits configured to precompute all values of a choose b for a ranging from 1 to the total number of bits for the first set of data and b ranging from 0 to a and store the precomputed values using the semiconductor memory.
8. The apparatus of claim 1 , wherein:
the total number of bits for the first set of data comprises 128 bits.
9. The apparatus of claim 1 , wherein:
the semiconductor memory comprises a non-volatile memory that is monolithically formed in one or more physical levels of memory cells having active areas disposed above a silicon substrate.
10. An apparatus, comprising:
a phase change memory;
a memory buffer;
a control circuit configured to acquire a first set of data associated with a binary number and store the first set of data associated with the binary number using the memory buffer, the first set of data comprises a total number of bits; and
means for generating a Hamming distance-based encoding for the first set of data associated with the binary number, the means for generating the Hamming distance-based encoding encodes the first set of data associated with the binary number using the Hamming distance-based encoding, the means for generating the Hamming distance-based encoding determines a Hamming weight for the first set of data, detects that the binary number minus the total number of bits choose one is greater than or equal to zero, reduces the binary number by the total number of bits choose one in response to detection that the binary number minus the total number of bits choose one is greater than or equal to zero, initializes a loop variable and an output array, detects that the reduced binary number is greater than or equal to the total number of bits minus one choose the Hamming weight for the first set of data, and sets a bit position within the output array corresponding with the loop variable to one in response to detection that the reduced binary number is greater than or equal to the total number of bits minus one choose the Hamming weight for the first set of data, the control circuit configured to output the output array as the Hamming distance-based encoding for the first set of data and write the Hamming distance-based encoding for the first set of data to the phase change memory.
11. The apparatus of claim 10 , wherein:
the control circuit configured to detect that the phase change memory has experienced more than a threshold number of bit errors and cause the Hamming distance-based encoding for the first set of data to be generated in response to detection that the phase change memory has experienced more than the threshold number of bit errors.
12. The apparatus of claim 10 , wherein:
the control circuit configured to detect that the phase change memory has a threshold number of defects and cause the Hamming distance-based encoding for the first set of data to be generated in response to detection that the phase change memory has the threshold number of defects.
13. The apparatus of claim 10 , wherein:
the control circuit configured to detect that the phase change memory has at least a threshold number of word line defects and cause the Hamming distance-based encoding for the first set of data to be generated in response to detection that the phase change memory has at least the threshold number of word line defects.
14. The apparatus of claim 10 , wherein:
the control circuit configured to detect that data previously written to the phase change memory has experienced at least a threshold number of bit errors and cause the Hamming distance-based encoding for the first set of data to be generated in response to detection that the data previously written to the semiconductor memory has experienced at least the threshold number of bit errors.
15. The apparatus of claim 10 , wherein:
the total number of bits for the first set of data comprises 256 bits.
16. The apparatus of claim 10 , wherein:
the phase change memory comprises a non-volatile memory that is monolithically formed in one or more physical levels of memory cells having active areas disposed above a silicon substrate.
17. A method, comprising:
acquiring a first set of data to be written to a semiconductor memory, the first set of data is associated with a binary number;
storing the first set of data associated with the binary number in a memory buffer;
determining a total number of bits for the first set of data;
determining a Hamming weight for the first set of data;
detecting that the semiconductor memory comprises a phase change memory;
generating a Hamming distance-based encoding for the first set of data associated with the binary number in response to detecting that the first set of data is to be written to the phase change memory, the generating the Hamming distance-based encoding includes encoding the first set of data associated with the binary number using the Hamming distance-based encoding, the generating the Hamming distance-based encoding for the first set of data includes detecting that the binary number minus the total number of bits choose one is greater than or equal to zero and reducing the binary number by the total number of bits choose one in response to detecting that the binary number minus the total number of bits choose one is greater than or equal to zero, the generating the Hamming distance-based encoding for the first set of data includes detecting that the reduced binary number is greater than or equal to the total number of bits minus one choose the Hamming weight for the first set of data and setting a bit position within an output array to one in response to detecting that the reduced binary number is greater than or equal to the total number of bits minus one choose the Hamming weight for the first set of data, the generating the Hamming distance-based encoding for the first set of data includes outputting the output array as the Hamming distance-based encoding for the first set of data; and
writing the Hamming distance-based encoding for the first set of data to the phase change memory.
18. The method of claim 17 , further comprising:
detecting that the phase change memory has experienced more than a threshold number of bit errors and generating the Hamming distance-based encoding for the first set of data in response to detecting that the phase change memory has experienced more than the threshold number of bit errors.
19. The method of claim 17 , further comprising:
detecting that data previously written to the phase change memory has experienced at least a threshold number of bit errors and generating the Hamming distance-based encoding for the first set of data in response to detecting that the data previously written to the phase change memory has experienced at least the threshold number of bit errors.
20. The method of claim 17 , further comprising:
acquiring a second set of data to be written to a second semiconductor memory, the second set of data is associated with a second binary number different from the binary number;
detecting that the second semiconductor memory has experienced less than a threshold number of bit errors; and
writing the second set of data to the second semiconductor memory in response to detecting that the second semiconductor memory has experienced less than the threshold number of bit errors.