Asymmetric error correction and flash-memory rewriting using polar codes
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.
1. 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 [|H V|S ∩L V|Y |] ∈{0,1} H V|S ∩L V|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] G n , where
G
n
=
G
⊗
log
2
n
,
for
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power; and
storing a value x i (v i , s i ), for each i∈[n].
2. The method as in claim 1 , wherein storing the processed message m comprises:
storing a vector u in the data device, where u LcV|Y∩HcV , separately from x, using a linear, non-capacity-achieving polar code with a uniform input distribution.
3. The method of claim 1 , further comprising:
receiving a message y over the communications channel of the data device from the non-volatile memory device, the message y comprising binary digits corresponding to an encoded data value and comprising a vector y[n]∈{0,1} n that represents the encoded data value with a noise term that represents error in the communications channel;
estimating a vector û that represents the message y decoded, wherein the vector û comprises a codeword of a block erasure-avoiding code in which binary digits of the message y are represented by a codeword configured for representation by multiple memory cells of the data device such that, after a value of a memory cell is changed from logic “0” to logic “1”, the value of that memory cell remains at logic “1”, even if a corresponding stored data value is later changed; and
returning the estimated vector û as an estimated original data value that corresponds to an estimated decoded value of the encoded data value of the received message y.
4. The method as in claim 3 , wherein estimating the vector û comprises processing the message y to assign values û to the binary digits according to:
for each i from 1 to n, assign
u
^
i
=
{
argmax
u
∈
{
0
,
1
}
p
U
i
❘
U
[
i
-
1
]
,
Y
[
n
]
(
u
❘
u
[
i
-
1
]
,
y
[
n
]
)
ifi
∈
ℒ
V
❘
Y
u
^
r
(
i
,
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
c
)
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
c
f
r
(
i
,
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
)
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
.
5. The method as in claim 3 , wherein returning the estimated vector û comprises returning an estimated message {circumflex over (m)} [|H V|S ∩L V|Y |] =û H V|S ∩L V|Y .
6. 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 [(|H V|S ∩L V|Y |−|H V|S c ∩L V|Y c |],[k]) ∈{0,1} k(|H V|S ∩L V|Y |−|H V|S c ∩L V|Y c |) 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 u i,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],j G n , where
G
n
=
G
⊗
log
2
n
,
for
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power; and
storing a value x i,j (v i,j , s i,j ), for each i∈[n].
7. The method as in claim 6 , wherein storing the processed message m in the data device comprises:
storing a vector u H V c ∩L V|Y c ,k separately using a non-capacity-achieving polar code with a uniform input distribution.
8. The method as in claim 6 , further comprising:
receiving a message y over the communications channel from the non-volatile memory device, the message y comprising binary digits corresponding to an encoded data value and comprising a vector y[n]∈{0,1} n that represents the encoded data value with a noise term that represents error in the communications channel;
estimating a vector û that represents the message y decoded, wherein the vector û comprises a codeword of a block erasure-avoiding code in which binary digits of the message y are represented by a codeword configured for representation by multiple memory cells of the data device such that, after a value of a memory cell is changed from logic “0” to logic “1”, the value of that memory cell remains at logic “1”, even if a corresponding stored data value is later changed; and
returning the estimated vector û as an estimated original data value that corresponds to an estimated decoded value of the encoded data value of the received message y,
wherein estimating the vector û comprises:
letting û R,K+1 =û L V|Y c ∩H V|S c ,k ; and
estimating û [n],[k] (y [n],[k] , f [|L V|Y c ∩H V|S |],[k] ) as follows: for each j down from k to 1, and for each i from 1 to n, assign:
u
^
i
j
=
{
argmax
u
∈
{
0
,
1
}
p
U
i
❘
U
[
i
-
1
]
,
Y
[
n
]
(
u
❘
u
[
i
-
1
]
,
j
,
y
[
n
]
,
j
)
ifi
∈
ℒ
V
❘
Y
u
^
r
(
i
,
ℛ
)
,
j
+
1
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
c
f
r
(
i
,
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
)
,
j
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
.
9. The method as in claim 8 , further comprising returning an estimated message {circumflex over (m)} [|H V|S ∩L V|Y |−|H V|S c ∩L V|Y c |],[k] =û (H V|S ∩L V|Y )\R,[k] .
10. 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 [|H V|S ∩L V|Y |] ∈{0,1} H V|S ∩L V|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] G n , where
G
n
=
G
⊗
log
2
n
,
for
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power; and
storing a value x i (v i , s i ), for each i∈[n].
11. The memory controller as in claim 10 , wherein the processor is further configured to store a vector u in the data device, where u LcV|Y∩HcV , separately from x, by use of a linear, non-capacity-achieving polar code with a uniform input distribution.
12. The memory controller of claim 10 , wherein:
the interface is further configured to receive a message y over the communications channel from the non-volatile memory device, the message y comprising binary digits corresponding to an encoded data value and comprising a vector y[n]∈{0, 1} n that represents the encoded data value with a noise term that represents error in the communications channel;
the processor is further configured to:
estimate a vector û that represents the message y decoded, wherein the vector û comprises a codeword of a block erasure-avoiding code in which binary digits of the message y are represented by a codeword configured for representation by multiple memory cells of the data device such that, after a value of a memory cell is changed from logic “0” to logic “1”, the value of that memory cell remains at logic “1”, even if a corresponding stored data value is later changed; and
return the estimated vector û as an estimated original data value that corresponds to an estimated decoded value of the encoded data value of the received message y.
13. The memory controller as in claim 12 , wherein to estimate the vector û, the processor is configured to process the message y to assign values û to the binary digits according to:
for each i from 1 to n, assign
u
^
i
=
{
argmax
u
∈
{
0
,
1
}
p
U
i
❘
U
[
i
-
1
]
,
Y
[
n
]
(
u
❘
u
[
i
-
1
]
,
y
[
n
]
)
ifi
∈
ℒ
V
❘
Y
u
^
r
(
i
,
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
c
)
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
c
f
r
(
i
,
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
)
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
.
14. The memory controller as in claim 12 , wherein to return the estimated vector û, the processor is configured to return an estimated message {circumflex over (m)} [|H V|S ∩L V|Y |] =û H V|S ∩L V|Y .
15. 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)} [(|H V|S ∩L V|Y |−|H V|S c ∩L V|Y c |],[k] ∈{0,1} k(|H V|S ∩L V|Y |−|H V|S c ∩L V|Y c |) 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 u i,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 G n , where
G
n
=
G
⊗
log
2
n
,
for
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power; and
store a value x i,j (v i,j , s i,j ), for each i∈[n].
16. The memory controller as in claim 15 , wherein the processor is further configured to store a vector u H V c ∩L V|Y c ,k separately by use of a non-capacity-achieving polar code with a uniform input distribution.
17. The memory controller as in claim 15 , wherein:
the interface is further configured to receive a message y over the communications channel of the data device from the non-volatile memory device, the message y comprising binary digits corresponding to an encoded data value and comprising a vector y[n]∈{0,1} n that represents the encoded data value with a noise term that represents error in the communications channel; and
the processor is further configured to:
estimate a vector û that represents the message y decoded, wherein the vector û comprises a codeword of a block erasure-avoiding code in which binary digits of the message y are represented by a codeword configured for representation by multiple memory cells of the data device such that, after a value of a memory cell is changed from logic “0” to logic “1”, the value of that memory cell remains at logic “1”, even if a corresponding stored data value is later changed; and
return the estimated vector û as an estimated original data value that corresponds to an estimated decoded value of the encoded data value of the received message y;
wherein to estimate the vector û, the processor is configured to:
let û R,K+1 =û L V|Y c ∩H V|S c ,k ; and
estimate û [n],[k] (y [n],[k] , f [|L V|Y c ∩H V|S |],[k] ) as follows: for each j down from k to 1, and for each i from 1 to n, assign:
u
^
i
j
=
{
argmax
u
∈
{
0
,
1
}
p
U
i
❘
U
[
i
-
1
]
,
Y
[
n
]
(
u
❘
u
[
i
-
1
]
,
j
,
y
[
n
]
,
j
)
ifi
∈
ℒ
V
❘
Y
u
^
r
(
i
,
ℛ
)
,
j
+
1
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
c
f
r
(
i
,
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
)
,
j
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
.
18. The memory controller as in claim 17 , wherein the processor is configured to return an estimated message {circumflex over (m)} [|H V|S ∩L V|Y |−|H V|S c ∩L V|Y c |],[k] =û (H V|S ∩L V|Y )\R,[k] .
19. 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 [|H V|S ∩L V|Y |] ∈{0,1} H V|S ∩L V|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] G n , where
G
n
=
G
⊗
log
2
n
,
for
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power; and
storing a value x i (v i , s i ), for each i∈[n].
20. The data device as in claim 19 , wherein to store the processed message m, the memory controller is configured to:
store a vector u in the data device, where u LcV|Y∩HcV , separately from x, by use of a linear, non-capacity-achieving polar code with a uniform input distribution.
21. The data device of claim 19 , wherein:
the memory controller is configured to receive a message y over the communications channel from the non-volatile memory device, the message y comprising binary digits corresponding to an encoded data value and comprising a vector y[n]∈{0, 1} n that represents the encoded data value with a noise term that represents error in the communications channel; and
the data device further comprises a processor coupled to the non-volatile memory device and configured to:
estimate a vector û that represents the message y decoded, wherein the vector û comprises a codeword of a block erasure-avoiding code in which binary digits of the message y are represented by a codeword configured for representation by multiple memory cells of the data device such that, after a value of a memory cell is changed from logic “0” to logic “1”, the value of that memory cell remains at logic “1”, even if a corresponding stored data value is later changed; and
return the estimated vector û as an estimated original data value that corresponds to an estimated decoded value of the encoded data value of the received message y.
22. The data device as in claim 21 , wherein to estimate the vector û, the processor is configured to process the message y to assign values û to the binary digits according to:
for each i from 1 to n, assign:
u
^
i
=
{
argmax
u
∈
{
0
,
1
}
p
U
i
❘
U
[
i
-
1
]
,
Y
[
n
]
(
u
❘
u
[
i
-
1
]
,
y
[
n
]
)
ifi
∈
ℒ
V
❘
Y
u
^
r
(
i
,
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
c
)
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
c
f
r
(
i
,
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
)
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
.
23. The data device as in claim 21 , wherein to return the estimated vector û, the processor is configured to return an estimated message {circumflex over (m)} [|H V|S ∩L V|Y |] =û H V|S ∩L V|Y .
24. 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 [(|H V|S ∩L V|Y |−|H V|S c ∩L V|Y c |],[k]) ∈{0,1} k(|H V|S ∩L V|Y |−|H V|S c ∩L V|Y c |) 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 u i,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],j G n , where
G
n
=
G
⊗
log
2
n
,
for
G
=
(
1
0
1
1
)
,
and ⊗ denotes a Kronecker power; and
store a value x i,j (v i,j , s i,j ), for each i∈[n].
25. The data device as in claim 24 , wherein to store the processed message m in the data device, the memory controller is configured to:
store a vector u H V c ∩L V|Y c ,k separately by use of a non-capacity-achieving polar code with a uniform input distribution.
26. The data device as in claim 24 , wherein:
the memory controller is configured to receive a message y over the communications channel from the non-volatile memory device, the message y comprising binary digits corresponding to an encoded data value and comprising a vector y[n]∈{0, 1} n that represents the encoded data value with a noise term that represents error in the communications channel; and
the data device further comprises a processor coupled to the non-volatile memory device and configured to:
estimate a vector û that represents the message y decoded, wherein the vector û comprises a codeword of a block erasure-avoiding code in which binary digits of the message y are represented by a codeword configured for representation by multiple memory cells of the data device such that, after a value of a memory cell is changed from logic “0” to logic “1”, the value of that memory cell remains at logic “1”, even if a corresponding stored data value is later changed; and
return the estimated vector û as an estimated original data value that corresponds to an estimated decoded value of the encoded data value of the received message y; and
the processor is configured to:
let û R,K+1 =û L V|Y c ∩H V|S c ,k ; and
estimate û [n],[k] (y [n],[k] , f [|L V|Y c ∩H V|S |],[k] ) as follows: for each j down from k to 1, and for each i from 1 to n, assign:
u
^
i
j
=
{
argmax
u
∈
{
0
,
1
}
p
U
i
❘
U
[
i
-
1
]
,
Y
[
n
]
(
u
❘
u
[
i
-
1
]
,
j
,
y
[
n
]
,
j
)
ifi
∈
ℒ
V
❘
Y
u
^
r
(
i
,
ℛ
)
,
j
+
1
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
c
f
r
(
i
,
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
)
,
j
ifi
∈
ℒ
V
❘
Y
c
⋂
ℋ
V
❘
S
.
27. The data device as in claim 26 , wherein the processor is configured to return an estimated message {circumflex over (m)} [|H V|S ∩L V|Y |−|H V|S c ∩L V|Y c |],[k] =û (H V|S ∩L V|Y )\R,[k] .