Method and apparatus for vertical layered decoding of quasi-cyclic low-density parity check codes built from clusters of circulant permutation matrices

Abstract

This invention presents a method and the corresponding hardware apparatus for decoding LDPC codes using a vertical layered (VL) iterative message passing algorithm. The invention operates on quasi-cyclic LDPC (QC-LDPC) codes, for which the non-zero circulant permutation matrices (CPMs) are placed at specific locations in the parity-check matrix of the codes, forming concentrated clusters of CPMs. The purpose of the invention is to take advantage of the organization of CPMs in clusters in order to derive a specific hardware architecture, consuming less power than the classical VL decoders. This is achieved by minimizing the number of read and write accesses to the main memories of the design.

What is claimed: 
     
         1 . A method for vertical layered decoding of quasi-cyclic low-density parity-check codes operating on a parity-check matrix with a structure composed of one or more higher-order generalized layers of order greater or equal than one, wherein each higher-order generalized layer is composed of non-overlapping groups of clusters of one or more circulant permutation matrices (CPMs) with the number of non-overlapping groups at most equal to the order of the higher-order generalized layer, the method comprising:
 receiving, as inputs, channel values belonging to a channel output alphabet;   using the channel values for initializing, iteratively processing groups of messages between variable nodes and check nodes within block-columns in an arbitrary order, and sequentially from one block-column to another block-column, generating hard decision estimates and validating to check if the hard-decision estimates constitute a codeword based upon which the decoding is terminated;   computing, during the initializing, respective signs of the variable-to-check messages using the signs of the channel values;   computing, during the initializing, the initial value of the sign state associated to each check node, by using the signs of the variable-to-check messages;   further computing, during the initializing, the initial value of the magnitude state associated to each check node, using the channel values;   storing the check node states in a check node memory, with each check node state associated to a check node comprising, a sign state of the associated check node computed from the signs of the variable-to-check messages, and a magnitude state composed of a set of values comprising one or more smallest magnitudes of the variable-to-check messages of the associated check node along with the same number of respective block-column indices;   iteratively processing a block-column, wherein the iterative processing includes:
 computing one or more groups of new check-to-variable messages corresponding to each cluster of CPMs, where each cluster of CPMs belongs to a non-overlapping group of clusters in a higher-order generalized layer, using a check node update-generator (CNU-Generator) step, with inputs comprising the check node states and the signs of the one or more groups of variable-to-check messages corresponding to the cluster of CPMs; 
 computing new variable-to-check messages with inputs comprising the channel values and the check-to-variable messages, using one or more variable node update functions; 
 computing hard decision estimates using the channel values and the check-to-variable messages, 
 updating the check node states corresponding to each cluster of CPMs, where each cluster belongs to a non-overlapping group of clusters in a higher-order generalized layer, to new values using a check node update-updater (CNU-Updater) step, with inputs comprising the current values of the check node states, one or more groups of variable-to-check messages corresponding to the cluster of CPMs, and the signs of the one or more groups of variable-to-check messages corresponding to the cluster of CPMs from the previous iteration. 
   computing, during the validating, the syndrome bits associated to the check nodes corresponding to the entire parity check matrix to check if the hard-decision estimates constitute a codeword; and   outputting the codeword, in accordance with the hard decision estimates constituting a codeword.