Antipodal-mapping-based encoders and decoders

1. An electronic-memory-system component comprising:

an array of data-storage elements; and

an encoder that

receives input data,

processes the input data as a two-dimensional array of bits by carrying out two passes, in one pass subjecting a portion of each row of the two-dimensional array of bits having more than a threshold weight to a first weight-reduction operation, and, in another pass, subjecting a portion of each considered column of the two-dimensional array of bits having more than a threshold weight to a second weight-reduction operation, one of the first and second weight-reduction operations employing an antipodal mapping and the other of the first and second weight-reduction operations employing bit inversion,

generates a codeword corresponding to the input data, and

stores the codeword in the array of data-storage elements.

2. The electronic-memory-system component of claim 1

wherein the encoder initially processes the input data as a bit string containing an ordered sequence of bits, each having one of a first value and a second value;

wherein the weight of a column or row is the number of bits in the column or row having the first value;

wherein the two-dimensional array has m rows, each having n bits, and therefore has n columns, each having m bits, the two-dimensional array storing a total of mn bits, each having one of the first value and the second value;

wherein m−2 successive ordered groups of n−1 bits of the bit string, to each of which a row-flag bit is appended, form initial m−2 rows of the two-dimensional array;

wherein a single, final ordered group of n−2 bits of the bit string, to which a first additional bit and then a row-flag bit are appended, form row m−1 of the two-dimensional array;

wherein the first m−1 bits in the final column contain row flags; and

wherein a final row of n−1 column flags and an additional bit forms row m of the two-dimensional array.

3. The electronic-memory-system component of claim 2

wherein bit n−1 in row m−1, bit n in row m, and all of the column flags and row flags are initially set to the second value;

wherein bit n in row m is considered to store binary value LRFlip; and

wherein bits n−1 and n in row m are added together, by modulo-2 arithmetic, to generate binary value LCFlip, which, when having the first value, indicates that the last column has been flipped, and when having the second value, indicates that the last column has not been flipped.

4. The electronic-memory-system component of claim 3

wherein, in a first pass, the encoder inverts each row of the two-dimensional array having

n

2

 or more bits with the first value, the inversion changing the row-flag bit from the second value to the first value; and

wherein, in a second pass, the encoder maps the first m−1 bits of each column of the two-dimensional array having

m

2

 or more bits with the first value, by an antipodal mapping, to m−1 mapped bits that the encoder then uses to replace the first m−1 bits of the column, the encoder setting the column flag of each column of the two-dimensional array having

m

2

 or more bits set to the first value.

5. The electronic-memory-system component of claim 4

wherein, when the final row m of the two-dimensional array has more than

n

2

 bits with the first value, the encoder inverts the final row m of the two-dimensional array, with LRFlip indicating whether or not the final row has been inverted; and

wherein, when the final column n of the two-dimensional array has more than

m

2

 bits with the first value, the encoder inverts the first m−1 bits of the final column n of the two-dimensional array, with LCFlip indicating whether or not the final column has been inverted.

6. An electronic-memory-system component comprising:

an array of data-storage elements; and

a decoder that

retrieves a codeword from the array of data-storage elements,

processes the codeword as a two-dimensional array of bits in two passes, in one pass subjecting a portion of each row of the two-dimensional array having a row-flag indication to an inverse first-weight-reduction operation, and, in another pass, subjecting a portion of each considered column of the two-dimensional array having a column-flag indication to an inverse second-weight-reduction operation, one of inverse first-weight-reduction and inverse second-weight-reduction operations employing an antipodal mapping and the other employing bit inversion, and

extracts bits from the two-dimensional array of bits as a sequence of uncoded bits corresponding to the codeword.

7. The electronic-memory-system component of claim 6

wherein the decoder initially processes the codeword as a bit string containing an ordered sequence of bits, each having one of a first value and a second value;

wherein the weight of a column or row is the number of bits in the column or row having the first value;

wherein the two-dimensional array has m rows, each having n bits, and therefore has n columns, each having m bits, the two-dimensional array storing a total of mn bits, each having one of the first value and the second value;

wherein m successive ordered groups of n bits of the bit string form the m rows of the two-dimensional array;

wherein the initial m−1 bits of the last column contain row flags for the first m−1 rows;

wherein the initial n−1 bits of the final row contain column flags for the first n−1 columns.

8. The electronic-memory-system component of claim 7

wherein bit n in row m is considered to store binary value LRFlip; and

wherein bits n−1 and n in row m are added together, by modulo-2 arithmetic, to generate binary value LCFlip, which, when having the first value, indicates that the last column has been flipped, and when having the second value, indicates that the last column has not been flipped.

9. The electronic-memory-system component of claim 8

wherein, when LRFlip has the first value, a column flag with the second value indicates that the column was subjected to the second weight-reducing operation during encoding, and, when LRFlip has the second value, a column flag with the first value indicates that the column was subjected to the second weight-reducing operation during encoding; and

wherein, when LCFlip has the first value, a row flag with the second value indicates that the row was subjected to the first weight-reducing operation during encoding, and, when LCFlip has the second value, a row flag with the first value indicates that the column was subjected to the first weight-reducing operation during encoding.

10. The electronic-memory-system component of claim 9

wherein, in a first pass, the decoder maps the first m−1 bits of each column of the two-dimensional array that was subjected to the second weight-reduction operation during encoding, by an antipodal mapping, to m−1 mapped bits that the decoder then uses to replace the first m−1 bits of the column; and

in a second pass, the decoder inverts the first n−1 bits of each row that was subjected to the first weight-reduction operation during encoding.

11. A method for carrying out an antipodal mapping φ, the method comprising:

receiving a bit string and storing the bit string in an electronic memory;

determining the minimal bit positions within the bit string; and

inverting the value of the bits at the minimal bit positions within the bit string.

12. The method of claim 11

wherein the antipodal mapping φ maps a first n-bit bit string x to a second n-bit string y, y=φ(x); and

wherein the mapping has characteristics:

length ( x )= n =length ( y )

| x|=k |y|=n−k

y i =1 x i =1 when |x|≧n/ 2

x i =1 y i =1 when | x|<n/ 2

φ(φ( x ))=φ( y )= x

where |x| and |y| represent the number of bits in bit string x and bit string y, respectively, having the value “1.”

13. The method of claim 12 wherein the minimal positions are found for a bit string with a majority of bits having the value “1” by:

reinterpreting bit values “1” and “0” as “1” and “−1,” respectively; and

selecting bit positions as minimal for which all sequences of successive bits within the bit string, with the successive bits wrapping back from the end of the bit string to the beginning of the bit string, when added together, produce a non-negative sum.

14. The method of claim 12 wherein the minimal positions are found for a bit string with less than a majority of bits having the value “1” by:

reversing and complementing, or flipping, the values of each bit in the bit string;

reinterpreting bit values “1” and “0” as “1” and “−1,” respectively;

selecting bit positions as minimal for which all sequences of successive bits within the bit string, with the successive bits wrapping back from the end of the bit string to the beginning of the bit string, when added together, produce a non-negative sum; and

again reversing and complementing, or flipping, the values of each bit in the bit string.

15. The method of claim 12

wherein the minimal positions are found by recursively removing sets of bits with value “1” from consideration as minimal positions, with the bit string considered to be circular, with position 0 following position n−1 and position n−1 preceding position 0 and

wherein, in each recursion, the rightmost bit with value “1” in each group of all-“1”-valued bits is removed from consideration, along with the bordering 0.