Method and Device for Correction of Ternary Stored Binary Data

• US 20130305119A1
• Filed: 05/08/2012
• Published: 11/14/2013
• Est. Priority Date: 05/08/2012
• Status: Active Grant

• Current Assignee: Infineon Technologies AG
• Original Assignee: Infineon Technologies AG
• Inventors: Kern, Thomas, Goessei, Michael
• Granted Patent: US 8,732,560 B2
• Time in Patent Office: Days
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G11C 2029/0411 Online error correction
• CPC Class Codes: H03M 13/13 Linear codes

Abstract

The invention relates to a device and a method for storing binary data in a storage device, in which the binary data is transformed to and stored as ternary data. The storage device uses memory cells capable of storing three states. The device and method furthermore are configured to identify and correct falsified ternary data when reading and outputting the data from storage device.

Claims

1. A memory device for storing a block of binary data u of length k, k being an integer, k>

2, comprising;

an encoder configured to receive the binary data, and configured to encode the block of binary data u of length k into encoded binary data x of length n, n≧

k, wherein the encoder uses an error correcting code C with a code distance d≧

3; and

a storage component coupled to the encoder, and configured to receive the encoded binary data x and output binary output data x′

of length n, wherein the storage component is configured to transform binary data x into ternary data, store the ternary data as ternary states in ternary memory cells of a ternary memory, and transform the ternary data into binary data x′

when the ternary data is retrieved from the ternary memory; and

a corrector coupled to the storage component, the corrector configured to receive binary data x′

from the storage component, and correct errors in the received binary data x′

caused by errors in the states of the ternary memory cells of the ternary memory.

2. The memory device of claim 1, wherein the error correcting code C is a linear block code with an (k−

n) generator matrix G and a (q,n) parity check matrix H with q=n−

k.

3. The memory device of claim 1, wherein information is stored in a ternary memory cell as a continuous physical value or state Z of that memory cell which, in dependence on the membership of the state Z of that memory cell to one of non-overlapping intervals W₀, W₁, W₂ of the continuous physical values, represents a ternary value Z₀, Z₁ or Z₂ with Z₀<

Z₁<

Z₂, where Z₂ is maximal and where Z₀ is minimal.

4. The memory device of claim 3, wherein Z represents a threshold voltage of a nonvolatile memory cell.

5. The memory device of claim 1, wherein in the storage component a pair of ternary memory cells is provided for storing one triple of binary data.

6. The memory device of claim 5, wherein the storage component comprises circuitry configured to transform a triple of binary data into a tuple of ternary data, wherein the circuitry exhibits at least three binary inputs and two ternary outputs, and wherein the circuitry for a triple of binary data x₁,x₂,x₃ outputs a tuple ternary values Z¹,Z², and for another, different triple of binary data x₁′

,x₂′

,x₃′

the circuitry outputs another, different pair of ternary values Z^1′

,Z^2′

, wherein Z¹, Z² and Z¹, Z² belong to different pairs of ternary values W_i,W_j and W_k,W_l, with (W_i,W_j)≠

(W_k,W_l), and

wherein if the pairs of ternary values are neighbouring, then x₁,x₂,x₃ and x₁′

,x₂′

,x₃′

differ by one or by three bits, whereby the pairs Z¹,Z² and Z^1′

,Z^2′

are neighboring if a first of their components belongs to the same interval and the second component belong to two contiguous intervals W_K and W_L of physical values where K and L differ by 1.

7. The memory device of claim 6, wherein the circuitry for transforming a triple of binary data to a tuple of ternary data is configured to transform none of the triples 000, 001, 010, 011, 100, 101, 110, 111 of binary values into a tuple of ternary data Z_i, Z_i, wherein Z_i corresponds to a maximal physical value stored in a ternary memory cell.

8. The memory device of claim 6, wherein the circuitry for transforming a triple of binary data to a tuple of ternary data is configured to transform none of the triples 000, 001, 010, 011, 100, 101, 110, 111 of binary values into a tuple of ternary data Z_i, Z_i, wherein Z_i corresponds to a minimal physical value stored in a ternary memory cell.

9. The memory device of claim 2, wherein the corrector comprises a syndrome generator, a decoder, and a combiner circuit, wherein the syndrome generator is configured to generate an error syndrome s=s₁, . . . , s_q of length q with q=n−

k based on the received binary data x=x₁′

, . . . , x_n′

wherein

s^T=H·

(x₁′

, . . . ,x_n′

)^T

and wherein s^T is a column vector of length q of the elements s₁, . . . , s_q and (x₁′

, . . . , x_n′

)^T is the column vector of length n of the elements wherein H=(h₁, h₂, . . . , h_n) is the parity check matrix of code C with the column vectors h₁, . . . , h_n, wherein the column vectors are pairwise different where the columns h₁, h₂, . . . , h_n of the H-matrix H consist of n/3 groups of three columns {h_i1,h_i2,h_i3}, . . . , {h_i[n-2],h_i[n-1],h_in} if n is divisible by 3 without remainder, and

wherein the columns h₁, h₂, . . . , h_n of the H-matrix H consist of (n−

2)/3 groups of three columns each {h_i1,h_i2,h_i3}, . . . , {h_i[n-4],h_i[n-3],h_i[n-2]} and a group of two columns {h_i[n-1],h_in} if n−

2 is divisible by 3 without remainder, and

wherein the columns h₁,h₂, . . . , h_n of the H-matrix H consist of (n−

1)/3 groups of three columns each {h_i1,h_i2,h_i3}, . . . , {h_i[n-3],h_i[n-2],h_i[n-1]} and a group of a single element {h_in} if (n−

1) is divisible by 3 without remainder,

such that the component-wise XOR sum of all columns of each group of columns of the parity check matrix H do not form a column of the parity check matrix H if the corresponding group contains at least two columns.

10. The memory device of claim 9, wherein binary data bits corresponding to the columns of a group of columns of the H-matrix, for which the componentwise XOR-sum of that columns does not form a column of the H-matrix, are stored as ternary values in a pair of memory cells of the memory device.

11. The memory device of claim 7, wherein the columns of the parity check matrix H=(h₁, . . . , h_n) are ordered such that h₁, . . . , h_n=h_i1, . . . , h_in.

12. The memory device of claim 11, wherein the columns h₁, . . . , h_n of the parity check matrix H comprises an odd number of ones.

13. The memory device of claim 12, wherein the device outputs an error signal indicating a 2-bit error if the syndrome s does not equal 0 and if the number of ones of components of the syndrome is even and indicating a 1-bit error or a 3-bit error if the number of ones of the components of the syndrome is odd.

14. A memory device for storing binary data, comprising:

an encoder configured to receive a block of binary data u of length k, k>

2, and encode the received binary data using a linear error correcting code thus producing a block of encoded binary data x of length n, n>

k;

a storage component, coupled to the encoder and comprising binary-to-ternary transformer circuitry configured to transform triples of encoded binary data x into tuples of ternary signals, and further comprising ternary memory configured to store the ternary signals, and comprising ternary-to-binary transformer circuitry configured to transform tuples of ternary signals into triples of binary signals x′

, and wherein the storage component is configured to output binary signals x′

; and

corrector circuitry coupled to the output of the storage component, and configured to determine an error vector e based on the output binary signals x′

of the storage component; and

a circuit coupled to the output of the storage component and to the output of the corrector circuitry, and configured to combine the binary signals x′ and

error vector e to produce a corrected output of the memory device.

15. The memory device of claim 14, wherein the corrector circuitry comprises:

a syndrome generator configured to generate an error syndrome s of length q=n−

k based on a parity check matrix and the output of the storage means x′

; and

a decoder circuit configured to generate the error vector e of length n based on the error syndrome s.

16. The memory device of claim 15, wherein the circuit coupled to the output of the storage component and the output of the corrector circuitry is configured to XOR-combine the error vector e with the binary signals x′

to correct the data as output by the storage component.

17. The memory device of claim 16, wherein in the storage component two ternary memory cells are provided for storing triples of binary data and where the storage component comprises circuitry configured to transform a tuple of ternary data into a triple of binary data, the circuitry exhibiting two ternary inputs and three binary outputs, wherein the circuitry for a tuple of ternary data Z¹, Z² outputs a triple of binary data x₁,x₂,x₃, and if for another, different tuple Z^1′

, Z^2′

of ternary data the circuitry outputs a triple x₁′

,x₂′

,x₃′

, of binary data, wherein Z¹, Z² and Z¹′

, Z²′

belong to different pairs of intervals W_i,W_j and W_k,W_l with (W_i,W_j)≠

(W_k,W_l) and wherein the pairs of ternary states are neighboring, then x₁,x₂,x₃ and x₁′

,x₂′

,x₃′

differ by one or three bits, whereby the pairs Z¹, Z² and Z¹′

, Z²′

are neighboring if a first component of the first pair and a first component of the second pair belong to the same interval and the second component of the first pair and the second component of the second pair belong to different intervals W_K and W_L where K and L differ by one.

18. The memory device of claim 17, wherein the decoder is configured to generate an error or correction vector e=e₁, . . . , e_n with binary components e₁, . . . , e_n and with e_i=1 and e_j=0 for j≠

t, if the error syndrome s is s=h_i, where h_i is the t-th column of the parity check matrix H of the code C and,

if n is divisible by 3 without remainder and if iε

{1, 4, . . . , n−

2} and if the error syndrome s is s=h_i⊕

h_i+1⊕

h_i+2 . . . , where h_i, h_i+1 and h_i+2 are the i-th, the (i+1)-th and the (i+2)-th columns of the parity check matrix H of the code C, then the components e_i, e_i+1, e_i+2 of the error vector e are equal to one and all the other components of the error vector e are equal to zero;

if the remainder of the division of n by 3 is equal to 2 and if iε

{1, 4, . . . , n−

4} and if the error syndrome s is s=h_i⊕

h_i+1⊕

h_i+2 then the components e_i, e_i+1, e_i+2 of the error vector e are equal to one and all the other components of the error vector e are equal to zero;

if the remainder of the division of n by 3 is equal to 2 and if the error syndrome s is s=h_n-1⊕

h_n, then the components e_n-1 and e_n of the error vector e are equal to one and all the other components of the error vector e are equal to zero;

if the remainder of the division of n by 3 is equal to 1 and if iε

{1, 4, . . . , n−

3} and if the error syndrome s is s=h_i⊕

h_i+1⊕

h_i+2 then the components e_i, e_i+1, e_i+2 of the error vector e are equal to one and all the other components of the error vector e are equal to zero; and

if the remainder of the division of n by 3 is equal to 1 and if the error syndrome s is s=h_n, then the component e_n of the error vector e is equal to 1 and all the other components of the error vector are equal to zero,

wherein the components e₁, . . . , e_n of the error vector are component-wise XORed with the corresponding components x₁′

, . . . , x_n′

of the binary data x′

=x₁′

, . . . , x_n′

.

19. A method for storing a block of binary data u of length k, k being integer, k>

2, comprising;

receiving the binary data in an encoder, and encoding the block u into e encoded binary data x of length n, n≧

k, using an error correcting code C with a code distance code d≧

3; and

storing the encoded binary data x in a storage component coupled to the encoder, wherein the storing comprises transforming binary data x into ternary data and storing the ternary data as ternary states in ternary memory cells, and reading the ternary data from the ternary memory cells, and transforming the ternary data into binary data x′

; and

correcting errors in the binary data x′

caused by errors in the states of the ternary memory cells.

20. The method of claim 19, wherein the error correcting code C is a linear block code with an (k−

n) generator matrix G and a (q,n) parity check matrix H with q=n−

k.

21. The method of claim 19, wherein information is stored in a memory cell as a continuous physical value or state Z of that memory cell which, in dependence on the membership of the state Z of that memory cell to one of non-overlapping intervals W₀, W₁, W₂ of the continuous physical values, represents a ternary value Z₀, Z₁ or Z₂ with Z₀<

Z₁<

Z₂, where Z₂ is maximal and where Z₀ is minimal.