Min-sum decoder for row-irregular low density parity check codes
Decoding method and memory system that classify check nodes in a matrix having irregular check node weights into different groups according to the check node weights, apply different scaling factors to respective constant node to variable node (C2V) messages in the different groups of the check nodes, and optionally add a compensation term to at least one of the C2V messages of the MS decoder.
1. A decoding method for decoding data read from a memory, comprising:
determining check node weights in a matrix used for decoding the data and having irregular check node weights;
classifying check nodes in the matrix having the irregular check node weights into different groups according to different check node weights; and
decoding the data read from the memory using scaled min-sum decoding by applying different scaling factors to respective check node to variable node (C2V) messages in the different groups of the check nodes having the different check node weights,
wherein
the different scaling factors applied in the scaled min-sum decoding reduce a value of the C2V messages to approximate a correction performance obtainable by a sum-product algorithm if the data read from the memory were decoded by the sum-product algorithm.
2. The method of claim 1 , wherein
the different groups having different check node weights comprise a low weight group, a median weight group, and a high weight group,
the low weight group has a check node weight lower than that of the medium weight group, and
the median weight group has a check node weight lower than that of the high weight group.
3. The method of claim 1 , further comprising:
applying a compensation term to at least one of the C2V messages.
4. The method of claim 3 , further comprising applying the compensation term to an output C2V message when there are multiple input variable node to check node (V2C) messages with a same minimum magnitude.
5. The method of claim 3 , further comprising selecting values of the different scaling factors that minimize an amount of compensation.
6. The method of claim 3 , further comprising utilizing one additional bit, in each C2V message, to indicate when there are multiple input messages with a same minimum magnitude.
7. The method of claim 6 , further comprising:
initializing the additional bit to 0 at a beginning of decoding;
when a variable node to check node (V2C) message matches with a minimum value, setting the additional bit to 1; and
when the minimum value is replaced by a different value, setting the additional bit to 0.
8. The method of claim 7 , wherein, when the additional bit is equal to 1 and a V2C index is equal to a first minimum index, set the C2V message equal to a minimum value proceeding a second minimum value, otherwise set the C2V message to the second minimum value.
9. The method of claim 1 , wherein a compensation term is calculated using the following equation:
y
=
∏
sign
(
m
i
)
*
min
~
(
❘
"\[LeftBracketingBar]"
m
i
❘
"\[RightBracketingBar]"
)
where
min
~
(
❘
"\[LeftBracketingBar]"
m
i
❘
"\[RightBracketingBar]"
)
=
min
1
-
d
d
=
1
,
if
min
1
=
min
2
,
else
0
where y is a mathematical product of a) a sign of the V2N message m i received and b) a magnitude of mi having a lowest value if min 1 is not equal to min 2 , else a magnitude of min 1 is offset by a value of 1.
10. A memory system, comprising:
a storage; and
a min-sum decoder for decoding data read from the storage, coupled to the storage, and configured to:
determine check node weights in a matrix used for decoding the data and having irregular check node weights;
classify check nodes in the matrix having the irregular check node weights into different groups according to different check node weights; and
decode the data read from the storage using scaled min-sum decoding by applying different scaling factors to respective check node to variable node (C2V) messages in the different groups of the check nodes having the different check node weights,
wherein
the different scaling factors applied in the scaled min-sum decoding reduce a value of the C2V messages to approximate a correction performance obtainable by a sum-product algorithm if the data read from the storage were decoded by the sum-product algorithm.
11. The memory system of claim 10 , wherein
the different groups having different check node weights comprise a low weight group, a median weight group, and a high weight group,
the low weight group has a check node weight lower than that of the medium weight group, and
the median weight group has a check node weight lower than that of the high weight group.
12. The memory system of claim 10 ,
wherein the decoder is configured to add a compensation term to at least one of the C2V messages of the min-sum decoder which further approximates the correction performance obtainable by the sum-product algorithm.
13. The memory system of claim 12 , wherein the decoder is configured to apply the compensation term to the output C2V message when there are multiple input variable node to check node (V2C) messages with a same minimum magnitude.
14. The memory system of claim 12 , further comprising selecting values of the different scaling factors that minimize an amount of compensation.
15. The memory system of claim 12 , wherein the decoder is configured to utilize one additional bit, in each C2V message, to indicate when there are multiple input messages with a same minimum magnitude.
16. The memory system of claim 15 , wherein the decoder is configured to:
initialize the additional bit to 0 at a beginning of decoding;
when a variable node to check node (V2C) message matches with a minimum value, set the additional bit to 1; and
when the minimum value is replaced by a different value, set the additional bit to 0.
17. The memory system of claim 16 , wherein the decoder is configured to:
when the additional bit is equal to 1 and a V2C index is equal to a first minimum index, set the C2V message equal to a minimum value proceeding a second minimum value, otherwise set the C2V message to the second minimum value.
18. The memory system of claim 10 , wherein a compensation term is calculated using the following equation:
y
=
∏
sign
(
m
i
)
*
min
~
(
❘
"\[LeftBracketingBar]"
m
i
❘
"\[RightBracketingBar]"
)
where
min
~
(
❘
"\[LeftBracketingBar]"
m
i
❘
"\[RightBracketingBar]"
)
=
min
1
-
d
d
=
1
,
if
min
1
=
min
2
,
else
0
where y is a mathematical product of a) a sign of the V2N message m i received and b) a magnitude of mi having a lowest value if min 1 is not equal to min 2 , else a magnitude of min 1 is offset by a value of 1.