Hamming distance based binary representations of numbers
View Patent ↗Technology is described herein for encoding and decoding numbers. In one aspect, floating point numbers are represented as binary strings. The binary strings may be encoded in a manner such that if one bit flips, the average and maximum distortion in the number that is represented by the binary string is relatively small. In one aspect, 2^n binary strings are ordered across an interval [a, b) in accordance with their Hamming weights. Numbers in the interval may be uniformly quantized into one of 2^n sub-intervals. For example, floating point numbers in the interval [a, b) may be uniformly quantized into 2^n sub-intervals. These 2^n sub-intervals may be mapped to the 2^n binary strings. Thus, the number may be assigned to one of the 2^n binary strings. Doing so may reduce the distortion in the number in the event that there is a bit flip in the assigned binary string.
1. An apparatus for encoding numbers into binary form, comprising:
a number accesser configured to access representations of numbers stored in non-transitory storage, the numbers being in an interval that comprises 2^n non-overlapping sub-intervals that cover the interval;
a quantizer configured to assign the respective numbers to one of the 2^n non-overlapping sub-intervals in accordance with a location of the respective number within the interval; and
a mapper configured to encode each of the respective numbers as a binary string in non-transitory storage based on the assigned sub-interval, the binary string being one of 2^n binary strings of length “n” that are ordered across the interval in accordance with Hamming distance from a base binary string of length “n”.
2. The apparatus of claim 1 , wherein the 2^n binary strings are clustered across the interval in n+1 Hamming groups, wherein each Hamming group comprises only binary strings with the same Hamming distance from the base binary string.
3. The apparatus of claim 2 , wherein the interval comprises n+1 non-overlapping sub-intervals that correspond to the n+1 Hamming groups, wherein the mapper is further configured to encode all numbers assigned to a given sub-interval of the n+1 sub-intervals to the Hamming group that corresponds to the given sub-interval.
4. The apparatus of claim 3 , wherein, within each of the n+1 Hamming groups, the binary strings are ordered according to binary value, wherein the mapper is further configured to encode the numbers assigned to the given sub-interval in accordance with the binary values of the binary strings in the Hamming group that corresponds to the given sub-interval.
5. The apparatus of claim 1 , wherein the mapper is further configured to encode all numbers assigned to a given sub-interval of the 2^n sub-intervals to the same binary string.
6. The apparatus of claim 1 , wherein the representations of the numbers are digital representations of floating point numbers.
7. The apparatus of claim 6 , wherein to assign respective numbers in the interval to one of 2^n non-overlapping sub-intervals the quantizer is further configured to:
uniformly quantize the floating point numbers in the interval into the 2^n sub-intervals.
8. The apparatus of claim 1 , further comprising:
non-volatile storage;
a write circuit configured to store the binary strings that represent the respective numbers in the non-volatile storage; and
a demapper configured to decode the stored binary strings with at least one of the binary strings having a bit flipped, wherein the binary string with the bit flipped decodes to a number in the interval other than the number the binary string represented when encoded.
9. The apparatus of claim 1 , wherein the base binary string comprises all zeros.
10. A method, comprising:
accessing, by a control circuit, digital representations of respective numbers stored in non-transitory storage, the numbers being in an interval that comprises 2^n non-overlapping sub-intervals that cover the interval;
assigning, by the control circuit, the respective numbers to one of the 2^n non-overlapping sub-intervals, wherein the assigning is performed in accordance with a location of the respective numbers within the interval;
encoding, by the control circuit, each of the respective numbers as a selected binary string of 2^n binary strings that are ordered across the interval by Hamming weight, the encoding being based on the assigned sub-interval; and
storing, by the control circuit, the selected binary strings in non-transitory storage.
11. The method of claim 10 , wherein the 2^n binary strings are clustered across the interval in n+1 Hamming groups, wherein each Hamming group comprises only binary strings with the same Hamming weight.
12. The method of claim 11 , wherein the interval comprises n+1 non-overlapping sub-intervals that correspond to the n+1 Hamming groups, further comprising:
encoding all numbers in a given sub-interval of the n+1 sub-intervals to the Hamming group that corresponds to the given sub-interval.
13. The method of claim 12 wherein, within each of the n+1 Hamming groups, the binary strings are ordered according to binary value, and further comprising:
encoding, by the control circuit, the numbers in the given sub-interval in accordance with the binary values of the binary strings in the Hamming group that corresponds to the given sub-interval.
14. The method of claim 10 , further comprising:
encoding, by the control circuit, all numbers assigned to a given sub-interval of the 2^n sub-intervals to the same binary string.
15. The method of claim 10 , wherein assigning the respective numbers to one of the 2^n non-overlapping sub-intervals comprises:
uniformly quantizing, by the control circuit, floating point numbers in the interval into the “2^n” sub-intervals.
16. An apparatus comprising:
non-volatile storage;
means for accessing digital representations of numbers stored in non-transitory storage, the numbers being in an interval that comprises 2^n non-overlapping sub-intervals that cover the interval, wherein the 2^n sub-intervals are ordered from a first end of the interval to a second end of the interval;
means for assigning the respective numbers to one of the 2^n non-overlapping sub-intervals, including means for assigning in accordance with a location of the respective numbers within the interval;
means for encoding each of the respective numbers to a selected binary string of 2^n binary strings that are ordered across the interval by Hamming weight; and
means for storing the selected binary strings in the non-volatile storage.
17. The apparatus of claim 16 , wherein the means for assigning the respective numbers to one of the 2^n non-overlapping sub-intervals comprises:
means for uniformly quantizing floating point numbers into one of the 2^n sub-intervals that correspond to the 2^n binary strings.
18. The apparatus of claim 17 , wherein the 2^n binary strings are clustered across the interval in n+1 Hamming groups, wherein the interval comprises n+1 non-overlapping sub-intervals that correspond to the n+1 Hamming groups, further comprising:
means for encoding all numbers in a given sub-interval of the n+1 sub-intervals to the Hamming group that corresponds to the given sub-interval of the n+1 sub-intervals.
19. The apparatus of claim 16 , wherein the means for encoding comprises:
means for encoding all numbers assigned to a given sub-interval of the 2^n sub-intervals to the same binary string of the 2^n binary strings.
20. The apparatus of claim 16 , further comprising:
means for decoding the selected binary strings that were stored in the non-volatile storage.