Bit-flip coding
View Patent ↗Bit-flip coding uses a bit-flip encoder to flip bits in a redundancy-intersecting vector of a binary array having n rows and n columns until Hamming weights of the binary array are within a predetermined range Δ of n divided by two. Information bits of an input data word to the bit-flip coding apparatus are stored in locations within the binary array that are not occupied by n redundancy bits of a redundancy vector.
1. A memory coding apparatus comprising: a bit-flip encoder to receive an input data and encode the input data to produce encoded data by flipping bits in a redundancy-intersecting vector of a binary array having n rows and n columns until Hamming weights of each of the rows and columns of the binary array are within a predetermined range A of n divided by two, the bit-flip encoder to write the encoded data to a memory, wherein information bits of the input data to the bit-flip encoder are stored in locations within the binary array that are not occupied by n redundancy bits of a redundancy vector; and a decoder to decode the encoded data retrieved from the memory to recover the information bits of the input data; the memory including a resistive crossbar memory array to store the binary array after the bit-flip encoder flips the bits, wherein unselected row lines and column lines of the resistive crossbar memory array are floating during a write to a resistive memory element within the resistive crossbar memory array.
2. The memory coding apparatus of claim 1 , wherein the redundancy-intersecting vector comprises both a row and a corresponding column of the binary array, the redundancy vector comprising a diagonal of the binary array and is intersected by the redundancy-intersecting vector.
3. The memory coding apparatus of claim 1 , wherein the redundancy-intersecting vector comprises a generalized diagonal of the binary array, the redundancy vector comprising either a row or a column of the binary array and is intersected by the redundancy-intersecting vector.
4. The memory coding apparatus of claim 1 , wherein the bit-flip encoder is a randomized bit-flip encoder, the randomized bit-flip encoder to randomly select the redundancy-intersecting vector, flip the bits of the randomly selected redundancy-intersecting vector, and compute Hamming weights of each of the rows and columns of the binary array to determine if the Hamming weights are within the predetermined range Δ of n divided by two.
5. The memory coding apparatus of claim 4 , wherein the randomized bit-flip encoder further is to select a random, binary n-bit word having a uniform distribution, the redundancy-intersecting vector to be randomly selected corresponding to indices of bits of the selected binary n-bit word having a value of one.
6. The memory coding apparatus of claim 1 , wherein the bit-flip encoder is a deterministic bit-flip encoder, the deterministic bit-flip encoder to compute a difference parameter Q k (A) for each k from 1 to n, and if the difference parameter Q k (A) is less than zero, then to flip the bits in A that belong to a k-th redundancy-intersecting vector, wherein the difference parameter Q k (A) is given by:
Q
k
(
A
)
=
∑
i
=
1
n
[
(
-
1
)
a
i
,
k
(
(
n
-
k
t
i
,
k
)
-
(
n
-
k
s
i
,
k
)
)
+
(
-
1
)
a
k
,
i
(
(
n
-
k
t
i
,
k
*
)
-
(
n
-
k
s
i
,
k
*
)
)
]
where
s
i
.
k
=
n
2
-
Δ
-
1
-
∑
j
=
1
k
-
1
a
i
,
j
t
i
.
k
=
n
2
+
Δ
-
∑
j
=
1
k
-
1
a
i
,
j
s
i
,
k
*
=
n
2
-
Δ
-
1
-
∑
j
=
1
k
-
1
a
j
,
i
t
i
,
k
*
=
n
2
+
Δ
-
∑
j
=
1
k
-
1
a
j
,
i
and where A is the binary array, a i,j is a binary element of the binary array A at location (i,j), and each of s i,k , t i,k , s* i,k , and t* i,k are variables indexed on i and k.
7. The memory coding apparatus of claim 6 , wherein the k-th redundancy-intersecting vector includes a k-th row and a k-th column of the binary array A, and wherein the redundancy vector is a diagonal of the binary array A.
8. The memory coding apparatus of claim 1 , wherein the decoder is to decode a selected bit of the encoded data retrieved from the memory, the decoder to determine both an exclusive OR (XOR) of the selected bit and a pair of redundancy bits corresponding to the selected bit, wherein a predetermined value of each of the n redundancy bits of the redundancy vector is each equal to zero prior to the bit-flip encoder flipping the bits.
9. The memory coding apparatus of claim 1 , wherein the flipping of the bits in the redundancy-intersecting vector is to reduce introduction of errors when writing data to the memory.
10. The memory coding apparatus of claim 9 , wherein the memory includes resistive memory elements, and wherein the flipping of the bits in the redundancy-intersecting vector is to reduce introduction of errors caused by unselected resistive memory elements connected to floating unselected row and column lines when writing a data bit to a selected resistive memory element of the memory.
11. The memory coding apparatus of claim 10 , wherein the flipping of the bits in the redundancy-intersecting vector is to reduce the introduction of errors caused by interference from a resistor network formed by the unselected resistive memory elements when writing the data bit to the selected resistive memory element of the memory.
12. The memory coding apparatus of claim 9 , wherein the memory includes resistive memory elements, and wherein the flipping of the bits in the redundancy-intersecting vector is to reduce introduction of errors caused by unselected resistive memory elements turning on when writing a data bit to a selected resistive memory element of the memory.
13. A memory system employing bit flip coding comprising:
a bit-flip encoder to receive an input data and to place information bits of the input data into a binary array, the bit-flip encoder to encode the binary array having n rows and n columns by flipping bits in a redundancy-intersecting vector of the binary array until Hamming weights of the rows and columns of the binary array are within a predetermined range Δ of n divided by two, the binary array comprising an n-bit redundancy vector and n squared minus n information bits, the information bits being stored in array locations of the binary array outside of the n-bit redundancy vector;
a resistive crossbar memory to receive and store the binary array encoded by the bit-flip encoder; and
a decoder to retrieve a selected encoded bit of the stored, encoded binary array from the resistive crossbar memory, and to decode the selected encoded bit using a corresponding encoded bit of the n-bit redundancy vector.
14. The memory system of claim 13 , wherein the n-bit redundancy vector is a diagonal of the binary array, the redundancy-intersecting vector being a row and a corresponding column of the binary array, the redundancy-intersecting vector intersecting the n-bit redundancy vector, and wherein the bit-flip encoder is a randomized bit-flip encoder, the randomized bit-flip encoder to randomly select the redundancy-intersecting vector, flip the bits of the randomly selected redundancy-intersecting vector, and test whether or not the Hamming weights of the binary array are within the predetermined range Δ of n divided by two.
15. The memory system of claim 13 , wherein the n-bit redundancy vector is a diagonal of the binary array, the redundancy-intersecting vector being a row and a corresponding column of the binary array, the redundancy-intersecting vector intersecting the n-bit redundancy vector, and wherein the bit-flip encoder is a deterministic bit-flip encoder, the deterministic bit-flip encoder to compute a difference parameter Q k (A) for each k from 1 to n and if the difference parameter Q k (A) is less than zero, then to flip the bits in A that belong to a k-th redundancy-intersecting vector, wherein the difference parameter Q k (A) is given by:
Q
k
(
A
)
=
∑
i
=
1
n
[
(
-
1
)
a
i
,
k
(
(
n
-
k
t
i
,
k
)
-
(
n
-
k
s
i
,
k
)
)
+
(
-
1
)
a
k
,
i
(
(
n
-
k
t
i
,
k
*
)
-
(
n
-
k
s
i
,
k
*
)
)
]
where
s
i
.
k
=
n
2
-
Δ
-
1
-
∑
j
=
1
k
-
1
a
i
,
j
t
i
.
k
=
n
2
+
Δ
-
∑
j
=
1
k
-
1
a
i
,
j
s
i
,
k
*
=
n
2
-
Δ
-
1
-
∑
j
=
1
k
-
1
a
j
,
i
t
i
,
k
*
=
n
2
+
Δ
-
∑
j
=
1
k
-
1
a
j
,
i
and where A is the binary array, a i,j is a binary element of the binary array A at location (i,j), and each of s i,k , t i,k , s* i,k , and t* i,k are variables indexed on i and k.
16. The memory system of claim 13 , wherein the flipping of the bits in the redundancy-intersecting vector is to reduce introduction of errors when writing data to the resistive crossbar memory.
17. A method comprising: receiving an input data to write to a memory; mapping the input data into a binary array stored in non-transitory computer memory, the binary array having n rows and n columns, the input data having n squared minus n information bits; bit-flip encoding the binary array comprising flipping bits in a redundancy-intersecting vector of the binary array using a processor until Hamming weights of the rows and the columns of the binary array are within a predetermined range Δ of n divided by two, wherein the mapping of the input data places the information bits in locations in the binary array that are not occupied by n redundancy bits of a redundancy vector stored in the binary array, writing the bit-flip encoded binary array to the memory; storing the encoded binary array in an n×n crossbar array of resistive memory elements, wherein storing comprises writing to a selected resistive memory element of the n×n crossbar array, the writing comprising selecting and driving a row line and a column line of the n×n crossbar array connected to the selected resistive memory element, wherein all unselected row lines and column lines of the n×n crossbar array are floating during the writing; and retrieving a selected encoded bit of the bit-flip encoded binary array from the memory, and decoding, using a decoder, the selected encoded bit.
18. The method of claim 17 , wherein the redundancy vector is stored in a major diagonal of the binary array, the redundancy-intersecting vector comprising a row and a corresponding column of the binary array, and either
wherein the bit-flip encoding is a randomized bit-flip encoding comprising:
randomly selecting a row and a corresponding column of the binary array; flipping bits of the selected row and column; and
computing the Hamming weights of all of the rows and columns of the binary array, wherein if the computed Hamming weights are within the predetermined range Δ of n divided by two, the randomized bit-flip encoding is terminated,
or wherein the bit-flip encoding is a deterministic bit-flip encoding comprising:
computing a difference parameter Q k (A) for each k from 1 to n and if the difference parameter Q k (A) is less than zero, flipping the bits in A that belong to a k-th row and column, wherein A is the binary array.