US2011041033A1PendingUtilityA1
Method and System for Decoding Graph-Based Codes Using Message-Passing with Difference-Map Dynamics
Est. expiryAug 14, 2029(~3.1 yrs left)· nominal 20-yr term from priority
G06F 7/5057G06F 7/5443H04L 2209/46H04L 2209/50H04L 9/3218H04B 10/6165H03M 13/1111H03M 13/658
48
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
A code to be decoded by message-passing is represented by a factor graph. The factor graph includes variable nodes indexed by i and constraint nodes indexed by a connected by edges for transferring messages m i→a outgoing from the variable nodes to the constraint nodes and messages m a→i incoming from the constraint nodes to the variable nodes. The messages m i→a are initialized based on beliefs b i of a received codeword. The messages m a→i are generated by overshooting the messages m i→a at the constraint nodes. The beliefs b i are updated at the variable nodes using the messages m a→i . The codeword is outputted if found, otherwise, the messages m i→a are updated using a correction for the overshooting.
Claims
exact text as granted — not AI-modified1 . A method for decoding a code using message-passing, wherein the code is represented by a factor graph, wherein the factor graph includes variable nodes indexed by i and constraint nodes indexed by a, wherein the variable nodes and the constraint nodes are connected by edges for transferring messages m i→a outgoing from the variable nodes to the constraint nodes and messages m a→i incoming from the constraint nodes to the variable nodes, and wherein the messages m i→a are initialized using beliefs b i of the set of variables nodes based on a received set of symbols y, and a processor for iteratively performing steps of the method, comprising the steps of:
generating the messages m a→i by overshooting the messages m i→a at the constraint nodes; updating the beliefs b i at the variable nodes using the messages m a→i ; determining if the codeword has been found; outputting the codeword if true; and otherwise updating the messages m i→a using a correction for the overshooting if false.
2 . The method of claim 1 , further comprising:
terminating if a termination condition is reached.
3 . The method of claim 1 , wherein the decoding is performed in a divide and concur belief propagation (DCBP) decoder.
4 . The method of claim 1 , wherein the decoding is performed in a difference map belief propagation (DMBP) decoder.
5 . The method of claim 1 , wherein the decoding is applied in a high data rate application.
6 . The method of claim 1 , wherein the decoding is applied in a high-density storage application.
7 . The method of claim 1 , wherein the code includes symbols, and the symbols have two values or more.
8 . The method of claim 3 , wherein the codeword includes symbols, and wherein the factor graph has one constraint node for each parity check constraint, and one variable node for each symbol x i in the codeword c, and all the variable nodes are connected to an energy constraint node, and the energy constraint node is connected to a set of log-likelihood ratio (LLR) nodes L i .
9 . The method of claim 8 , wherein the symbols are bits having values 0 or 1, and further comprising:
mapping 0 to +1, and mapping 1 to −1.
10 . The method of claim 1 , wherein next messages m i→a from the variable nodes to the constraint nodes depend upon a current messages m a→i and the same messages m i→a during previous iterations.
11 . The method of claim 10 , wherein next messages m i→a from the variable nodes to the constraint nodes are updated by subtracting a difference between the messages m i→a and the messages m a→i from the belief b i according to
m i→a ( t+ 1)= b i ( t )−λ[ m a→i ( t )− m i→a ( t )],
where λ is a predetermined parameter.
12 . The method of claim 11 , wherein λ=½.
13 . The method of claim 1 , wherein each belief b i is an average
b
i
(
t
)
=
1
M
(
i
)
∑
a
∈
M
(
i
)
m
a
→
i
(
t
)
,
where the variable node i is subject to the set of constraint nodes, and t represents an iteration.
14 . The method of claim 8 , wherein the energy constraint is E≦E max , where
E max is a parameter and E=−ΣL i x i .
15 . The method of claim 14 , wherein the parameter E max is set to a value such that the energy constraint is never satisfied to keep the beliefs b i substantially the same as the received symbols y.
16 . The method of claim 4 , wherein the factor graph has one constraint node for each parity check constraint, and one variable for each bit in the codeword c, and each variable node is connected to an energy constraint node, and each energy constraint node is connected to a log-likelihood ratio node L i .
17 . The method of claim 16 , wherein the messages m a→i are updated using
m
a
→
i
=
(
min
j
∈
N
(
a
)
\
i
m
j
→
a
)
∏
j
∈
N
(
a
)
\
i
sgn
(
m
j
→
a
)
,
where sgn(m j→a )=1 if m j→a >0, sgn(m j→a )=−1 if m j→a <0, and 0 otherwise.
18 . The method of claim 16 , wherein the messages m a →i are updated according to
m
a
→
i
=
2
tanh
-
1
(
∏
j
∈
N
(
a
)
\
i
tanh
(
m
j
→
a
/
2
)
)
.
19 . The method of claim 1 , wherein each belief b i is updated according to
b
i
=
z
(
L
i
+
∑
a
∈
M
(
i
)
m
a
→
i
)
,
where z is a parameter selected to optimize a performance of the decoding.
20 . The method of claim 19 , where the parameter z is set to a value in a range 0.25 to 0.5.
21 . The method of claim 20 , where the messages m i→a are updated according to
m
i
→
a
(
t
+
1
)
=
α
(
2
zL
i
+
(
2
z
-
1
)
m
a
→
i
(
t
)
+
2
z
∑
b
∈
M
(
i
)
\
a
m
b
→
i
(
t
)
)
+
(
1
-
α
)
m
i
→
a
(
t
)
,
where α is a damping” parameter that controls how much the message m i→a at time t+1 depends on a value of the message at time t.
22 . The method of claim 21 , where the parameter α equals ½.
23 . A decoder for decoding a code using message-passing, wherein the code is represented by a factor graph, wherein the factor graph includes variable nodes indexed by 1 and constraint nodes indexed by a, wherein the variable nodes and the constraint nodes are connected by edges for transferring messages m i→a outgoing from the variable nodes to the constraint nodes and messages m a→i incoming from the constraint nodes to the variable nodes, wherein the messages m i→a are initialized based on beliefs b i based on a received set of symbols y, comprising a processor, comprising:
means for generating the messages m a→i by overshooting the messages m i→a at the constraint nodes; means for updating the beliefs b i using the messages m a→i ; means for determining if the codeword has been found; means for outputting the codeword if true; and otherwise means for updating the messages m i→a using correction for the overshooting if false.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.