Method and Apparatus for Elementary Updating a Check Node During Decoding of a Block Encoded with a Non-binary LDPC Code

Abstract

Method of elementary updating a check node of a non-binary LDPC code during a decoding of a block encoded with said LDPC code, comprising receiving a first input message (U) and a second input message (V) each comprising n m doublets having a symbol and an associated metric, delivering an output message (S) possessing n m output doublets by computing a matrix of n m 2 combined doublets on the basis of a combination of the doublets of the two input messages (U,V), and reducing the number of the combined doublets so as to obtain the n m output doublets of the output message (S) possessing the n m largest or lowest metrics. The method further includes tagging redundant symbols within each input message (U, V) and fixing same at a reference value, the value of the metric of each combined doublet resulting from a combination of at least one doublet comprising a tagged redundant symbol.

What is claimed is: 
     
         1 . A method of elementary updating of a check node of a graph of a non-binary low density parity check (LDPC) code, the method comprising:
 receiving a first set of ordered doublets and a second set of ordered doublets, each of the doublets comprising a symbol and a metric value;   combining the first set of ordered doublets and the second set of ordered doublets into a matrix of combined doublets;   determining, by a processor, a first subset from the matrix of combined doublets based on the metric values, the first subset forming a pattern within the matrix of combined doublets;   marking redundant symbols in the matrix of combined doublets, the marking comprising setting the respective metric value to a reference value for each combined doublet comprising a redundant symbol; and   reducing, by a processor, the first subset of combined doublets to a second subset of combined doublets based on the metric values.   
     
     
         2 . The method of  claim 1 , wherein the first subset is the combined doublets from the matrix of combined doublets with the largest metric values, wherein the second subset is the combined doublets from the first subset with the largest metric values, and wherein the reference value is a minimum value. 
     
     
         3 . The method of  claim 1 , wherein the first subset is the combined doublets from the matrix of combined doublets with the smallest metric values, wherein the second subset is the combined doublets from the first subset with the smallest metric values, and wherein the reference value is a maximum value. 
     
     
         4 . The method of  claim 1  further comprising at a same time as combining the first set of ordered doublets and the second set of ordered doublets into a matrix of combined doublets, tagging the redundant symbols within the first set and second set of ordered doublets. 
     
     
         5 . The method of  claim 1 , wherein reducing, by a processor, the first subset of the combined doublets to a second subset of the combined doublets based on the metric values further comprises:
 grouping the first subset of combined doublets into a diagonal group and non-diagonal groups within the matrix of combined doublets, wherein each non-diagonal group comprises two vectors comprising a same number of combined doublets; and   removing half of the combined doublets from the non-diagonal groups.   
     
     
         6 . The method of  claim 1  further comprising:
 sorting the second subset of combined doublets; and 
 selecting a first number of the sorted second subset combined doublets forming a third subset of combined doublets. 
 
     
     
         7 . The method of  claim 6 , wherein the first set and the second set of ordered doublets each have a same number of doublets as the third subset of combined doublets. 
     
     
         8 . The method of  claim 1 , wherein the first set and the second set of ordered doublets each have less doublets than the first subset of combined doublets. 
     
     
         9 . A decoder comprising:
 an input for receiving a block encoded with a non-binary low density parity check code;   an elementary update module comprising:
 an input configured to receive a first set of ordered doublets and a second set of ordered doublets, each of the doublets comprising a symbol and a metric value; 
 a combining module configured to:
 combine the first set of ordered doublets and the second set of ordered doublets into a matrix of combined doublets; and 
 determine a first subset from the matrix of combined doublets based on the metric values, the first subset forming a pattern within the matrix of combined doublets; 
 
 a tagging module configured to tag redundant symbols within first set and the second set of ordered doublets; 
 a marking module configured to set the respective metric value for each tagged redundant symbol to a reference value for each combined doublet comprising a tagged redundant symbol; and 
 a reducing module configured to reduce the first subset of combined doublets to a second subset of combined doublets based on the metric values. 
   
     
     
         10 . The decoder of  claim 9 , wherein the first subset is the combined doublets from the matrix of combined doublets with the largest metric values, wherein the second subset is the combined doublets from the first subset with the largest metric values, and wherein the reference value is a minimum value. 
     
     
         11 . The decoder of  claim 9 , wherein the first subset is the combined doublets from the matrix of combined doublets with the smallest metric values, wherein the second subset is the combined doublets from the first subset with the smallest metric values, and wherein the reference value is a maximum value. 
     
     
         12 . The decoder of  claim 9 , wherein the tagging module comprises a first and a second tagging module, the first tagging module configured to tag the redundant symbols within the first ordered set of doublets, and the second tagging module configured to tag the redundant symbols within the second ordered set of doublets. 
     
     
         13 . The decoder of  claim 12 , wherein the combining module is configured to receive the first and second ordered sets of doublets in parallel with the first and second tagging modules. 
     
     
         14 . The decoder of  claim 9 , wherein the reducing module comprises:
 a grouping module configured to group the first subset of combined doublets into a diagonal group and non-diagonal groups within the matrix of combined doublets, wherein each non-diagonal group comprises two vectors comprising a same number of combined doublets; and   at least two sub-reducing modules, each of the sub-reducing modules configured to remove half of the combined doublets from a non-diagonal group.   
     
     
         15 . The decoder of  claim 9  further comprising:
 a selection module configured to:
 sort the second subset of combined doublets; and 
 select a first number of the sorted second subset combined doublets forming a third subset of combined doublets; and 
 an output configured to transmit the third subset of combined doublets. 
 
 
     
     
         16 . The decoder of  claim 15 , wherein the first set and the second set of ordered doublets each have a same number of doublets as the third subset of combined doublets. 
     
     
         17 . The decoder of  claim 9 , wherein the first set and the second set of ordered doublets each have less doublets than the first subset of combined doublets. 
     
     
         18 . An elementary update module of a non-binary low density parity check (LDPC) decoder comprising:
 an input configured to receive a first ordered message and a second ordered message, the first and second messages each comprising a vector of metric values and a vector of symbols, each metric value associated with a symbol forming a doublet;   a combining module configured to:
 combine the first ordered message and the second ordered message into a matrix of combined doublets; and 
 determine a first subset from the matrix of combined doublets based on the metric values, the first subset forming a pattern within the matrix of combined doublets; 
   a tagging module configured to tag redundant symbols within first ordered message and the second ordered message;   a marking module configured to set the respective metric value for each tagged redundant symbol to a reference value for each combined doublet comprising a tagged redundant symbol;   a reducing module configured to reduce the first subset of combined doublets to a second subset of combined doublets based on the metric values; and   an output configured to transmit an output message comprising a subset of the second subset of combined doublets.   
     
     
         19 . The elementary update module of  claim 18  further comprising:
 a selection module configured to:
 sort the second subset of combined doublets; and 
 select a first number of the sorted second subset combined doublets forming a third subset of combined doublets, the output message comprising the third subset of combined doublets. 
 
 
     
     
         20 . The elementary update module of  claim 19 , wherein the reducing module comprises:
 a grouping module configured to group the first subset of combined doublets into a diagonal group and non-diagonal groups within the matrix of combined doublets, wherein the diagonal group is output to the selection module, and wherein each non-diagonal group comprises two vectors comprising a same number of combined doublets; and   at least two sub-reducing modules, each of the sub-reducing modules configured to remove half of the combined doublets from a non-diagonal group.