US 10,379,945 B2Granted

Asymmetric error correction and flash-memory rewriting using polar codes

AssigneesCalifornia Institute of Technology, The Texas A&M University System

InventorsEyal En Gad, Yue Li, Joerg Kliewer, Michael Langberg, Anxiao Jiang, Jehoshua Bruck

Life of this patent

Estimating the term…

Loading patent…

Abstract

Techniques are disclosed for generating codes for representation of data in memory devices that may avoid the block erasure operation in changing data values. Data values comprising binary digits (bits) can be encoded and decoded using the generated codes, referred to as codewords, such that the codewords may comprise a block erasure-avoiding code, in which the binary digits of a data message m can be encoded such that the encoded data message can be stored into multiple memory cells of a data device and, once a memory cell value is changed from a first logic value to a second logic value, the value of the memory cell may remain at the second logic value, regardless of subsequently received messages, until a block erasure operation on the memory cell. Similarly, a received data message comprising an input codeword, in which source data values of multiple binary digits have been encoded with the disclosed block erasure-avoiding code, can be decoded in the data device to recover an estimated source data message.

Claims27

Dependent claims

A method to operate a data device, the method comprising:

receiving a message m by the data device over a communications channel, the communications channel having a state s, and the data device including a non-volatile memory device;
processing the message m based on the state s such that multiple binary digits of the processed message m represent a codeword of a block erasure-avoiding code in which the binary digits of the processed message m represent multiple memory cells of the non-volatile memory device such that, after a value of a memory cell is changed from a first logic value to a second logic value, the value of the memory cell remains at the second logic value, regardless of subsequently received messages, until a block erasure operation on the memory cell;
and
storing the processed message m in memory cells of the non-volatile memory device by, without performing block erasure operations on the memory cells, changing values of at least some of the memory cells from the first logic value to the second logic value,
wherein the message m is defined by an expression m[|HV|S∩LV|Y|]∈{0,1}HV|S∩LV|Y| and the state s is defined by an expression s[n]∈{0,1}n;
and
wherein processing the message m comprises:
assigning values u to the binary digits of the processed message m according to, for each i from 1 to n:
u
i
=
{
u
∈
{
0
,
1
}
⁢
⁢
with
⁢
⁢
probability
p
U
i
❘
U
[
i
-
1
]
,
S
[
n
]
⁡
(
u
❘
u
[
i
-
1
]
,
s
[
n
]
)
⁢
ifi
∈
ℋ
V
❘
S
c
m
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
)
ifi
∈
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
f
r
⁢
{
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
)
ifi
∈
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
⁢
;
calculating v[n]=u[n]Gn, where
G
n
=
G
⊗
log
2
⁢
n
,
for
⁢
⁢
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power;
and
storing a value xi(vi, si), for each i∈[n].

145 more elements

A method to operate a data device, the method comprising:

receiving a message m by the data device over a communications channel, the communications channel having a state s, and the data device including a non-volatile memory device;
processing the message m based on the state s such that multiple binary digits of the processed message m represent a codeword of a block erasure-avoiding code in which the binary digits of the processed message m represent multiple memory cells of the non-volatile memory device such that, after a value of a memory cell is changed from a first logic value to a second logic value, the value of the memory cell remains at the second logic value, regardless of subsequently received messages, until a block erasure operation on the memory cell;
and
storing the processed message m in memory cells of the non-volatile memory device by, without performing block erasure operations on the memory cells, changing values of at least some of the memory cells from the first logic value to the second logic value,
wherein the message m is defined by an expression m[(|HV|S∩LV|Y|−|HV|Sc∩LV|Yc|],[k])∈{0,1}k(|HV|S∩LV|Y|−|HV|Sc∩LV|Yc|) and the state s is defined by an expression s[n],[k]∈{0,1}kn;
wherein processing the message m comprises processing the message m to assign values u to the binary digits according to:
let u[n],0∈{0,1}n be an arbitrary vector;
for each j from 1 to k, and for each i from 1 to n, assign ui,j to one of:
u
i
,
j
=
{
u
∈
{
0
,
1
}
⁢
⁢
with
⁢
⁢
probability
p
U
i
❘
U
[
i
-
1
]
,
S
[
n
]
⁡
(
u
❘
u
[
i
-
1
]
,
s
[
n
]
)
ifi
∈
ℋ
V
❘
S
c
m
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
)
,
j
ifi
∈
(
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
)
⁢
\
⁢
ℛ
u
r
⁡
(
i
,
ℋ
V
❘
S
c
⋂
ℒ
V
❘
Y
c
)
,
j
-
1
ifi
∈
ℛ
f
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
)
,
j
ifi
∈
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
;
and
wherein processing the message m further comprises:
calculating v, where, for each j from 1 to k, v is defined by an expression v[n],j=u[n],jGn, where
G
n
=
G
⊗
log
2
⁢
n
,
for
⁢
⁢
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power;
and
storing a value xi,j(vi,j, si,j), for each i∈[n].

182 more elements

A memory controller to control memory of a data device having a non-volatile memory device, the memory controller comprising:

an interface configured to receive a message m over a communications channel, the communications channel having a state s;
and
a processor coupled to the interface and configured to:
process the message m based on the state s such that multiple binary digits of the message m represent a codeword of a block erasure-avoiding code in which the binary digits of the message m represent multiple memory cells of the non-volatile memory device such that, after a value of a memory cell is changed from a first logic value to a second logic value, the value of the memory cell remains at the second logic value, regardless of subsequently received messages, until a block erasure operation on the memory cell, and
store the processed message m in memory cells of the non-volatile memory device by, without performing block erasure operations on the memory cells, changing values of at least some of the memory cells from the first logic value to the second logic value,
wherein the message m is defined by an expression m[|HV|S∩LV|Y|]∈{0,1}HV|S∩LV|Y| and the state s is defined by an expression s[n]∈{0,1}n;
and
wherein processing the message m comprises:
assigning values u to the binary digits of the processed message m according to, for each i from 1 to n:
u
i
=
{
u
∈
{
0
,
1
}
⁢
⁢
with
⁢
⁢
probability
p
U
i
❘
U
[
i
-
1
]
,
S
[
n
]
⁡
(
u
❘
u
[
i
-
1
]
,
s
[
n
]
)
ifi
∈
ℋ
V
❘
S
c
m
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
)
ifi
∈
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
f
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
)
ifi
∈
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
;
calculating v[n]=u[n]Gn, where
G
n
=
G
⊗
log
2
⁢
n
,
for
⁢
⁢
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power;
and
storing a value xi(vi, si), for each i∈[n].

144 more elements

A memory controller to control memory of a data device having a non-volatile memory device, the memory controller comprising:

an interface configured to receive a message m over a communications channel, the communications channel having a state s;
and
a processor coupled to the interface and configured to:
process the message m based on the state s such that multiple binary digits of the message m represent a codeword of a block erasure-avoiding code in which the binary digits of the message m represent multiple memory cells of the non-volatile memory device such that, after a value of a memory cell is changed from a first logic value to a second logic value, the value of the memory cell remains at the second logic value, regardless of subsequently received messages, until a block erasure operation on the memory cell, and
store the processed message m in memory cells of the non-volatile memory device by, without performing block erasure operations on the memory cells, changing values of at least some of the memory cells from the first logic value to the second logic value,
wherein the message m is defined by an expression {circumflex over (m)}[(|HV|S∩LV|Y|−|HV|Sc∩LV|Yc|],[k]∈{0,1}k(|HV|S∩LV|Y|−|HV|Sc∩LV|Yc|) and the state s is defined by an expression s[n],[k]∈{0,1}kn;
wherein the processor is configured to process the message m to assign values u to the binary digits according to:
let u[n],0∈{0,1}n be an arbitrary vector;
for each j from 1 to k, and for each i from 1 to n, assign ui,j to one of:
u
i
,
j
=
{
u
∈
{
0
,
1
}
⁢
⁢
with
⁢
⁢
probability
p
U
i
❘
U
[
i
-
1
]
,
S
[
n
]
⁡
(
u
❘
u
[
i
-
1
]
,
s
[
n
]
)
ifi
∈
ℋ
V
❘
S
c
m
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
)
,
j
ifi
∈
(
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
)
⁢
\
⁢
ℛ
u
r
⁡
(
i
,
ℋ
V
❘
S
c
⋂
ℒ
V
❘
Y
c
)
,
j
-
1
ifi
∈
ℛ
f
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
)
,
j
ifi
∈
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
;
and
wherein to process the message m, the processor is further configured to:
calculate v, where, for each j from 1 to k, v is defined by an expression v[n],j=u[n],j Gn, where
G
n
=
G
⊗
log
2
⁢
n
,
for
⁢
⁢
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power;
and
store a value xi,j(vi,j, si,j), for each i∈[n].

183 more elements

A data device, comprising:

a non-volatile memory device configured to store data values;
and
a memory controller that is coupled to the non-volatile memory device and is configured to:
receive a message m over a communications channel, the communications channel having a state s;
process the message m based on the state s such that multiple binary digits of the processed message m represent a codeword of a block erasure-avoiding code in which the binary digits of the processed message m represent multiple memory cells of the non-volatile memory device such that, after a value of a memory cell is changed from a first logic value to a second logic value, the value of the memory cell remains at the second logic value, regardless of subsequently received messages, until a block erasure operation on the memory cell;
and
store the processed message m in memory cells of the non-volatile memory device by, without performing block erasure operations on the memory cells, changing values of at least some of the memory cells from the first logic value to the second logic value,
wherein the message m is defined by an expression m[|HV|S∩LV|Y|]∈{0,1}HV|S∩LV|Y| and the state s is defined by an expression s[n]∈{0,1}n;
and
wherein processing the message m comprises:
assigning values u to the binary digits of the processed message m according to, for each i from 1 to n:
u
i
=
{
u
∈
{
0
,
1
}
⁢
⁢
with
⁢
⁢
probability
p
U
i
❘
U
[
i
-
1
]
,
S
[
n
]
⁡
(
u
❘
u
[
i
-
1
]
,
s
[
n
]
)
ifi
∈
ℋ
V
❘
S
c
m
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
)
ifi
∈
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
f
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
)
ifi
∈
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
;
calculating v[n]=u[n]Gn, where
G
n
=
G
⊗
log
2
⁢
n
,
for
⁢
⁢
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power;
and
storing a value xi(vi, si), for each i∈[n].

146 more elements

A data device, comprising:

a non-volatile memory device configured to store data values;
and
a memory controller that is coupled to the non-volatile memory device and is configured to:
receive a message m over a communications channel, the communications channel having a state s;
process the message m based on the state s such that multiple binary digits of the processed message m represent a codeword of a block erasure-avoiding code in which the binary digits of the processed message m represent multiple memory cells of the non-volatile memory device such that, after a value of a memory cell is changed from a first logic value to a second logic value, the value of the memory cell remains at the second logic value, regardless of subsequently received messages, until a block erasure operation on the memory cell;
and
store the processed message m in memory cells of the non-volatile memory device by, without performing block erasure operations on the memory cells, changing values of at least some of the memory cells from the first logic value to the second logic value,
wherein the message m is defined by an expression m[(|HV|S∩LV|Y|−|HV|Sc∩LV|Yc|],[k])∈{0,1}k(|HV|S∩LV|Y|−|HV|Sc∩LV|Yc|) and the state s is defined by an expression s[n],[k]∈{0,1}kn;
and
wherein to process the message m, the memory controller is configured to process the message m to assign values u to the binary digits according to:
let u[n],0∈{0,1}n be an arbitrary vector;
for each j from 1 to k, and for each i from 1 to n, assign ui,j to one of:
u
i
,
j
=
{
u
∈
{
0
,
1
}
⁢
⁢
with
⁢
⁢
probability
p
U
i
❘
U
[
i
-
1
]
,
S
[
n
]
⁡
(
u
❘
u
[
i
-
1
]
,
s
[
n
]
)
ifi
∈
ℋ
V
❘
S
c
m
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
)
,
j
ifi
∈
(
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
)
⁢
\
⁢
ℛ
u
r
⁡
(
i
,
ℋ
V
❘
S
c
⋂
ℒ
V
❘
Y
c
)
,
j
-
1
ifi
∈
ℛ
f
r
⁡
(
i
,
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
)
,
j
ifi
∈
ℋ
V
❘
S
⋂
ℒ
V
❘
Y
c
;
calculate v, where, for each j from 1 to k, v is defined by an expression v[n],j=u[n],jGn, where
G
n
=
G
⊗
log
2
⁢
n
,
for
⁢
⁢
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power;
and
store a value xi,j(vi,j, si,j), for each i∈[n].

184 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/112,156Filed 14 Jan 2015 · us provisional application
Priority: 17 Jan 2014
Published: US 2016/0335156 A117 Nov 2016
Granted: 13 Aug 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

G06F 11/1068
In individual solid state devices: in sector programmable memories, e.g. flash disk
G06F 11/1012
In individual solid state devices: using codes or arrangements adapted for a specific type of error
G11C 29/52
Checking stores for correct operation ; Subsequent repair; Testing stores during standby or offline operation: protection of memory contents;…
H03M 13/13
Using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits: linear codes