Message passing memory and barrel shifter arrangement in LDPC (Low Density Parity Check) decoder supporting multiple LDPC codes

Abstract

Message passing memory and barrel shifter arrangement in LDPC (Low Density Parity Check) decoder supporting multiple LDPC codes. A novel approach is presented by which a barrel shifter may be implemented in conjunction with a single message passing memory within an LDPC decoder. This arrangement also allows for a single bit/check processor to be employed that is operable to perform updating of edge messages with respect to check nodes as well as updating of edge messages with respect to bit nodes. There are a variety of embodiments by which the barrel shifter and the message passing memory may be implemented. By using this approach, a common architecture and design may operate to decode various types of LDPC coded signals including those whose code rate and/or modulation (including constellation shape and mapping) may vary as frequently as on a frame by frame basis or even on a block by block basis.

1 . A decoder that is operable to decode an LDPC (Low Density Parity Check) coded signal, the decoder comprising: 
 a message passing memory that is operable to: 
 receive a plurality of edge messages with respect to a plurality of bit nodes that corresponds to an LDPC bipartite graph by which a symbol of the LDPC coded signal is generated; and  
 store each edge message of the plurality of edge messages with respect to the plurality of bit nodes in a respective location therein;  
   a barrel shifter, situated after and communicatively coupled to the message passing memory, that is operable to: 
 receive each edge message of the plurality of edge messages with respect to the plurality of bit nodes from the message passing memory; and  
 shift each edge message of the plurality of edge messages with respect to the plurality of bit nodes based on each edge message's connectivity between a given bit node of the plurality of bit nodes and a given check node of a plurality of check nodes that corresponds to the LDPC bipartite graph by which the symbol of the LDPC coded signal is generated so that the plurality of edge messages with respect to the plurality of bit nodes is arranged for use in subsequent check node processing that involves updating a plurality of edge messages with respect to the plurality of check nodes using the shifted plurality of edge messages with respect to the plurality of bit nodes;  
   wherein the message passing memory is operable to: 
 receive the updated plurality of edge messages with respect to the plurality of check nodes generated during the check node processing; and  
 store each updated edge message of the plurality of edge messages with respect to the plurality of check nodes in a respective location therein; and  
   wherein the barrel shifter is operable to: 
 receive each updated edge message of the plurality of edge messages with respect to the plurality of check nodes from the message passing memory; and  
 shift each updated edge message of the plurality of edge messages with respect to the plurality of check nodes based on each edge message's connectivity between a given check node of the plurality of check nodes and a given bit node of the plurality of bit nodes that corresponds to the LDPC bipartite graph by which the LDPC coded signal is generated so that the updated plurality of edge messages with respect to the plurality of check nodes is arranged for use in subsequent bit node processing that involves updating the plurality of edge messages with respect to the plurality of bit nodes using the shifted, updated plurality of edge messages with respect to the plurality of check nodes.  
   
   
   
       2 . The decoder of  claim 1 , further comprising: 
 a plurality of bit/check processors, communicatively coupled to the barrel shifter and to the message passing memory, that is operable to perform both the bit node processing that involves updating the plurality of edge messages with respect to the plurality of bit nodes and the check node processing that involves updating the plurality of edge messages with respect to the plurality of check nodes to perform parallel processed decoding of the LDPC coded signal.    
   
   
       3 . The decoder of  claim 1 , wherein: 
 the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of bit nodes in a direction; and    the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of check nodes in the direction.    
   
   
       4 . The decoder of  claim 1 , wherein: 
 the plurality of bit nodes include is partitioned into a plurality of groups such that each group contains a predetermined number of bit nodes;    the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of bit nodes a corresponding first amount; and    the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of check nodes a corresponding second amount that is a difference between the corresponding first amount and the predetermined number of bit nodes contained within each group of the plurality of groups.    
   
   
       5 . The decoder of  claim 1 , wherein: 
 the plurality of bit nodes include is partitioned into a plurality of groups such that each group contains 360 bit nodes;    each edge message of the plurality of edge messages with respect to the plurality of bit nodes has a corresponding index that is m×n, where n is an integer value between 0 and 359, and m is an integer;    the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of bit nodes a corresponding amount that is n; and    the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of check nodes a corresponding amount that is n×mod(360).    
   
   
       6 . The decoder of  claim 1 , wherein: 
 the message passing memory addresses each edge message of the plurality of edge messages with respect to the plurality of bit nodes sequentially when storing each edge message in its respective location therein; and    the message passing memory addresses each edge message of the plurality of edge messages with respect to the plurality of check nodes based on control signals provided by a controller when storing each edge message in its respective location therein.    
   
   
       7 . The decoder of  claim 1 , wherein: 
 the message passing memory addresses each edge message of the plurality of edge messages with respect to the plurality of bit nodes based on control signals provided by a controller when storing each edge message in its respective location therein; and    the message passing memory addresses each edge message of the plurality of edge messages with respect to the plurality of check nodes sequentially when storing each edge message in its respective location therein.    
   
   
       8 . The decoder of  claim 1 , further comprising a plurality of macro blocks that is arranged in a parallel configuration such that each macro block of the plurality of macro blocks comprises a corresponding plurality of bit/check processors and a corresponding message passing memory; 
 wherein the message passing memory is implemented within one macro block of the plurality of macro blocks;    wherein the barrel shifter is implemented outside of the plurality of macro blocks, is communicatively coupled to each corresponding message passing memory within each macro block of the plurality of macro blocks, and is operable to perform shifting of edge messages stored within each corresponding message passing memory; and    wherein, within each macro block, the corresponding plurality of bit/check processors is communicatively coupled to the barrel shifter and to the corresponding message passing memory contained within that macro block and is operable to perform both the bit node processing that involves updating the plurality of edge messages with respect to the plurality of bit nodes and the check node processing that involves updating the plurality of edge messages with respect to the plurality of check nodes to perform parallel processed decoding of the LDPC coded signal.    
   
   
       9 . The decoder of  claim 1 , wherein: 
 the LDPC coded signal is a variable code rate signal and is also a variable modulation signal;    the first symbol of the LDPC coded signal has a first code rate and a first modulation having a first constellation shape and a corresponding first mapping; and    the second symbol of the LDPC coded signal has a second code rate and a second modulation having a second constellation shape and a corresponding second mapping.    
   
   
       10 . The decoder of  claim 1 , wherein: 
 the decoder is operable to decode LDPC coded signals that are compliant with at least one of DVB-S2 (Digital Video Broadcasting Project-Satellite Version 2) standard and recommended practices provided by IEEE (Institute of Electrical & Electronics Engineers) P802.3an (10GBASE-T) Task Force.    
   
   
       11 . A decoder that is operable to decode an LDPC (Low Density Parity Check) coded signal, the decoder comprising: 
 a barrel shifter that is operable to: 
 receive a plurality of edge messages with respect to a plurality of bit nodes that corresponds to an LDPC bipartite graph by which a symbol of the LDPC coded signal is generated; and  
 shift each edge message of the plurality of edge messages with respect to the plurality of bit nodes based on each edge message's connectivity between a given bit node of the plurality of bit nodes and a given check node of a plurality of check nodes that corresponds to the LDPC bipartite graph by which the symbol of the LDPC coded signal is generated so that the plurality of edge messages with respect to the plurality of bit nodes is arranged for use in subsequent check node processing that involves updating a plurality of edge messages with respect to the plurality of check nodes using the shifted plurality of edge messages with respect to the plurality of bit nodes;  
   a message passing memory, situated after and communicatively coupled to the barrel shifter, that is operable to: 
 receive the shifted plurality of edge messages with respect to the plurality of bit nodes from the barrel shifter; and  
 store each edge message of the shifted plurality of edge messages with respect to the plurality of bit nodes in a respective location therein;  
 output each edge message of the shifted plurality of edge messages with respect to the plurality of bit nodes for use in the subsequent check node processing;  
   wherein the barrel shifter is operable to: 
 receive the updated plurality of edge messages with respect to the plurality of check nodes generated during the check node processing; and  
 shift each updated edge message of the plurality of edge messages with respect to the plurality of check nodes based on each edge message's connectivity between a given check node of the plurality of check nodes and a given bit node of the plurality of bit nodes that corresponds to the LDPC bipartite graph by which the LDPC coded signal is generated so that the updated plurality of edge messages with respect to the plurality of check nodes is arranged for use in subsequent bit node processing that involves updating the plurality of edge messages with respect to the plurality of bit nodes using the shifted, updated plurality of edge messages with respect to the plurality of check nodes;  
   wherein the message passing memory is operable to: 
 receive the shifted plurality of edge messages with respect to the plurality of check nodes from the barrel shifter;  
 store each edge message of the shifted plurality of edge messages with respect to the plurality of check nodes in a respective location therein;  
 output each edge message of the shifted plurality of edge messages with respect to the plurality of check nodes for use in the subsequent bit node processing.  
   
   
   
       12 . The decoder of  claim 11 , further comprising: 
 a plurality of bit/check processors, communicatively coupled to the barrel shifter and to the message passing memory, that is operable to perform both the bit node processing that involves updating the plurality of edge messages with respect to the plurality of bit nodes and the check node processing that involves updating the plurality of edge messages with respect to the plurality of check nodes to perform parallel processed decoding of the LDPC coded signal.    
   
   
       13 . The decoder of  claim 11 , wherein: 
 the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of bit nodes in a direction; and    the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of check nodes in the direction.    
   
   
       14 . The decoder of  claim 11 , wherein: 
 the plurality of bit nodes include is partitioned into a plurality of groups such that each group contains a predetermined number of bit nodes;    the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of bit nodes a corresponding first amount; and    the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of check nodes a corresponding second amount that is a difference between the corresponding first amount and the predetermined number of bit nodes contained within each group of the plurality of groups.    
   
   
       15 . The decoder of  claim 11 , wherein: 
 the plurality of bit nodes include is partitioned into a plurality of groups such that each group contains 360 bit nodes;    each edge message of the plurality of edge messages with respect to the plurality of bit nodes has a corresponding index that is m×n, where n is an integer value between 0 and 359, and m is an integer;    the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of bit nodes a corresponding amount that is n; and    the barrel shifter shifts each edge message of the plurality of edge messages with respect to the plurality of check nodes a corresponding amount that is n×mod(360).    
   
   
       16 . The decoder of  claim 11 , wherein: 
 the message passing memory addresses each edge message of the plurality of edge messages with respect to the plurality of bit nodes sequentially when storing each edge message in its respective location therein; and    the message passing memory addresses each edge message of the plurality of edge messages with respect to the plurality of check nodes based on control signals provided by a controller when storing each edge message in its respective location therein.    
   
   
       17 . The decoder of  claim 11 , wherein: 
 the message passing memory addresses each edge message of the plurality of edge messages with respect to the plurality of bit nodes based on control signals provided by a controller when storing each edge message in its respective location therein; and    the message passing memory addresses each edge message of the plurality of edge messages with respect to the plurality of check nodes sequentially when storing each edge message in its respective location therein.    
   
   
       18 . The decoder of  claim 11 , further comprising a plurality of macro blocks that is arranged in a parallel configuration such that each macro block of the plurality of macro blocks comprises a corresponding plurality of bit/check processors, a corresponding barrel shifter, and a corresponding message passing memory; 
 wherein the barrel shifter is implemented within one macro block of the plurality of macro blocks;    wherein the message passing memory is implemented within one macro block of the plurality of macro blocks; and    wherein, within each macro block, the corresponding plurality of bit/check processors is communicatively coupled to the corresponding barrel shifter and to the corresponding message passing memory contained within that macro block and is operable to perform both the bit node processing that involves updating the plurality of edge messages with respect to the plurality of bit nodes and the check node processing that involves updating the plurality of edge messages with respect to the plurality of check nodes to perform parallel processed decoding of the LDPC coded signal.    
   
   
       19 . The decoder of  claim 11 , wherein: 
 the LDPC coded signal is a variable code rate signal and is also a variable modulation signal;    the first symbol of the LDPC coded signal has a first code rate and a first modulation having a first constellation shape and a corresponding first mapping; and    the second symbol of the LDPC coded signal has a second code rate and a second modulation having a second constellation shape and a corresponding second mapping.    
   
   
       20 . The decoder of  claim 11 , wherein: 
 the decoder is operable to decode LDPC coded signals that are compliant with at least one of DVB-S2 (Digital Video Broadcasting Project-Satellite Version 2) standard and recommended practices provided by IEEE (Institute of Electrical & Electronics Engineers) P802.3an (10GBASE-T) Task Force.    
   
   
       21 . A barrel shifter implemented in a decoder that is operable to decode an LDPC (Low Density Parity Check) coded signal, wherein: 
 during a first time period, the barrel shifter is operable to: 
 receive a plurality of edge messages with respect to a plurality of bit nodes that corresponds to an LDPC bipartite graph by which a symbol of the LDPC coded signal is generated; and  
 shift each edge message of the plurality of edge messages with respect to the plurality of bit nodes based on each edge message's connectivity between a given bit node of the plurality of bit nodes and a given check node of a plurality of check nodes that corresponds to the LDPC bipartite graph by which the symbol of the LDPC coded signal is generated so that the plurality of edge messages with respect to the plurality of bit nodes is arranged for use in subsequent check node processing that involves updating a plurality of edge messages with respect to the plurality of check nodes using the shifted plurality of edge messages with respect to the plurality of bit nodes; and  
   during a second time period, the barrel shifter is operable to: 
 receive a plurality of edge messages with respect to a plurality of check nodes that corresponds to the LDPC bipartite graph by which the symbol of the LDPC coded signal is generated; and  
 shift each edge message of the plurality of edge messages with respect to the plurality of check nodes based on each edge message's connectivity between a given check node of the plurality of check nodes and a given bit node of the plurality of bit nodes that corresponds to the LDPC bipartite graph by which the symbol of the LDPC coded signal is generated so that the plurality of edge messages with respect to the plurality of check nodes is arranged for use in subsequent bit node processing that involves updating the plurality of edge messages with respect to the plurality of bit nodes using the shifted plurality of edge messages with respect to the plurality of check nodes.  
   
   
   
       22 . The decoder of  claim 21 , further comprising: 
 a message passing memory, situated after and communicatively coupled to the barrel shifter, that during the first period of time is operable to: 
 receive the shifted plurality of edge messages with respect to the plurality of bit nodes from the barrel shifter; and  
 store each edge message of the shifted plurality of edge messages with respect to the plurality of bit nodes in a respective location therein; and  
 output each edge message of the shifted plurality of edge messages with respect to the plurality of bit nodes for use in the subsequent check node processing;  
   wherein, during the second period of time, the message passing memory is operable to: 
 receive the shifted plurality of edge messages with respect to the plurality of check nodes from the barrel shifter; and  
 store each edge message of the shifted plurality of edge messages with respect to the plurality of check nodes in a respective location therein; and  
 output each edge message of the shifted plurality of edge messages with respect to the plurality of check nodes for use in the subsequent bit node processing.  
   
   
   
       23 . The decoder of  claim 21 , wherein: 
 the LDPC coded signal is a variable code rate signal and is also a variable modulation signal;    the first symbol of the LDPC coded signal has a first code rate and a first modulation having a first constellation shape and a corresponding first mapping; and    the second symbol of the LDPC coded signal has a second code rate and a second modulation having a second constellation shape and a corresponding second mapping.    
   
   
       24 . The decoder of  claim 21 , wherein: 
 the decoder is operable to decode LDPC coded signals that are compliant with at least one of DVB-S2 (Digital Video Broadcasting Project-Satellite Version 2) standard and recommended practices provided by IEEE (Institute of Electrical & Electronics Engineers) P802.3an (10GBASE-T) Task Force.