LDPC decoder and operating method thereof
An operating method of a low density parity check (LDPC) decoder, the operating method includes: initially updating codewords to variable nodes; determining an update order in which a plurality of variable node groups are updated, which is determined based on reliability of each of the variable node groups; executing local iterations including update of check nodes associated with a select variable node group among the variable node groups and update of the select variable node group based on the updated check nodes until all the variable node groups are updated based on the update order; performing syndrome check to determine whether LDPC decoding is successful, based on an operation of the updated variable nodes and a parity check matrix.
1. An operating method of a low density parity check (LDPC) decoder, the operating method comprising:
initially updating codewords to variable nodes;
determining an update order in which a plurality of variable node groups are updated, which is determined based on reliability of each of the variable node groups;
executing local iterations including update of check nodes associated with a select variable node group among the variable node groups and update of the select variable node group based on the updated check nodes, until all the variable node groups are updated based on the update order;
performing syndrome check to determine whether LDPC decoding is successful, based on an operation of the updated variable nodes and a parity check matrix; and
wherein each cycle of the determining of the update order, the executing local iterations and the performing of the syndrome check represents a global iteration, which is repeated until the decoding is successful or the number of global iterations performed reaches a maximum number.
2. The operating method of claim 1 , wherein the determining of the update order comprises:
each of the variable node groups based on a log likelihood ratio (LLR) value of each variable node of the corresponding variable node group.
3. The operating method of claim 2 , wherein the determining of the reliability of each of the variable node groups comprises:
for each variable node group, summing the LLR values of the variable nodes belonging to that variable node group.
4. The operating method of claim 1 , wherein the determining of the update order comprises:
determining reliability of each of the variable node groups based on the number of unsatisfied check nodes (USCs) connected to each variable node of the corresponding variable node group,
wherein the USC is determined in the syndrome check of a previous global iteration.
5. The operating method of claim 4 , wherein the determining the reliability of each of the variable node groups comprises:
assigning higher reliability to a variable node having a lower number of connected USCs than a variable node having a higher number of connected USCs; and
determining the reliability of each of the variable node groups as a sum of reliabilities of the variable nodes belonging to the respective variable node groups.
6. The operating method of claim 1 , wherein the determining of the update order comprises:
generating the plurality of variable node groups by grouping the plurality of variable nodes sorted in descending order of reliability into a set number of groups; and
determining the update order such that a variable node group with lower reliability among the plurality of variable node groups is updated before a variable node group with higher reliability.
7. The operating method of claim 1 , wherein the determining of the update order comprises:
generating the plurality of variable node groups by grouping the plurality of variable nodes, which have been sorted in an order of the codewords, into a set number of groups; and
determining the update order such that a variable node group with lower reliability among the plurality of variable node groups is updated before a variable node group with higher reliability.
8. A low density parity check (LDDC) decoder comprising:
a main decoder configured to initially update codewords to variable nodes; and
a scheduler configured to determine an update order in which a plurality of variable node groups are updated, which is determined based on reliability of each of the variable node groups,
wherein the main decoder executes local iterations including update of check nodes associated with a select variable node group among the variable node groups and update of the select variable node group based on the updated check nodes, until all the variable node groups are updated based on the update order, and performs syndrome check to determine whether LDPC decoding is successful, based on an operation of the updated variable nodes and a parity check matrix, and
wherein each cycle of the determining of the update order, the executing of the local iterations, and the performing of the syndrome check represents a global iteration, which the LDPC decoder repeats until the decoding is successful or the number of global iterations performed reaches a maximum number.
9. The LDPC decoder of claim 8 , wherein the scheduler determines reliability of each of the variable node groups based on a log likelihood ratio (LLR) value of each variable node of the corresponding variable node group.
10. The LDPC decoder of claim 9 , wherein the scheduler determines the reliability of each the variable node group as a sum of LLR values of variable nodes belonging to the corresponding variable node group.
11. The LDPC decoder of claim 8 , wherein the scheduler determines reliability of each of the variable node groups based on the number of unsatisfied check nodes (USCs) connected to each variable node of the corresponding variable node group, and
the USC is determined in the syndrome check of a previous global iteration.
12. The LDPC decoder of claim 11 , wherein the scheduler assigns higher reliability to a variable node having a lower number of connected USCs than a variable node having a higher number of connected USCs, and determines the reliability of each of the variable node groups as a sum of reliabilities of the variable nodes belonging to the respective variable node groups.
13. The LDPC decoder of claim 8 , wherein the scheduler generates the plurality of variable node groups by grouping the plurality of variable nodes, which have been sorted in descending order of reliability, into a set number of groups, and determines the update order such that a variable node group with lower reliability among the plurality of variable node groups is updated before a variable node group with higher reliability.
14. The LDPC decoder of claim 8 , wherein the scheduler generates the plurality of variable node groups by grouping the plurality of variable nodes, which have been sorted in an order of the codewords, into a set number of groups, and determines the update order such that a variable node group with lower reliability among the plurality of variable node groups is updated before a variable node group with higher reliability.
15. The LDPC decoder of claim 14 , wherein the set number is determined based on the maximum number of variable nodes that are updatable by the main decoder in one local iteration.
16. A low density parity check (LDPC) decoding device comprising:
a scheduler configured to group a plurality of variable nodes based on error information to generate multiple variable node groups, and determine the order of decoding the variable node groups based on the number of errors associated with each variable node group, such that a variable node group with a higher number of errors is decoded before a variable node group with lower number of errors; and
a decoder configured to decode the multiple variable node groups based on the decoding order.