Abstract:
An iterative decoder for receiving a sequence of samples representing a series of symbols, and for decoding the received sequence to the series. The decoder includes a plurality of variable-nodes. Each node receives and stores a sample from the sequence, iteratively passes messages to, and receives messages from, at least two connected check-nodes in a plurality of check-nodes, sends each connected check-node a message determined in accordance with the stored sample and message received from the at least one other check-node segment, and provides as output a decoded symbol determined in accordance with the received messages from the connected check-nodes and the stored sample.

Description:
FIELD OF THE INVENTION 
   The present invention relates generally to methods and systems for iteratively decoding coded received signals. More particularly, the present invention relates to methods and systems for hybrid iterative decoding of received coded signals. 
   BACKGROUND OF THE INVENTION 
   In the field of telecommunications, there is great interest in iterative decoding algorithms. Some error correcting codes, such as turbo-codes and low-density parity-check (LDPC) codes require iterative decoding to properly determine the encoded message after transmission through a noisy channel. Attention is directed to iterative decoding methods due to their contribution to the overall coded channel performance. 
   After their introduction by Gallager in the 1960&#39;s, LDPC codes were considered to be too computationally complex to be easily implemented. However, as computational power of telecommunications equipment advanced, and in concert with the interest paid to turbo-codes, LDPC codes have been an area of great focus and development. 
   The iterative decoding of turbo and LDPC codes is an area of particular interest in the field. Improvements in decoding techniques have allowed greater utilization of telecommunication channels. 
   For the sake of clarity, the following discussion will focus on the iterative decoding of LDPC codes, through one skilled in the art will appreciate that similar approaches are employed in other iterative decoding approaches. 
   A graphical representation of an iterative decoder  100  known in the art is provided in  FIG. 1 . A plurality of variable-nodes, labelled v 1    102 , v 2    104 , v 3    106 , v 4    108 , v 5    110 , and v 6    112 , receive a sequence of samples representing a series of symbols, forming a code word, transmitted by an encoder. Due to the presence of noise in the transmission channel, the sequence of samples cannot be simply mapped to a series of symbols using a look up table. However, with sufficient use of error-correction coding, a received sequence of samples can be decoded to a candidate codeword with a desired amount of certainty. Each variable-node is connected to at least one of the check-nodes labelled c 1    114 , c 2    116 , c 3    118  and c 4    120 . Each connection between a variable-node and a check-node is referred to as an edge. Along these edges, messages are passed between the nodes. Each node, either check or variable, applies a predefined function to the received message prior to passing the result back. 
   The functions performed by the variable and check-nodes correspond to a desired decoding algorithm such as majority-based (MB) algorithms, minimum sum (min-sum) algorithms and belief propagation algorithms. MB algorithms can be implemented with minimal computational complexity, and a small implementation area, as they rely upon hard decisions. Min-sum and belief propagation algorithms provide faster convergence than MB algorithms, which can be used to reduce the number of iterations required to obtain the desired certainty in decoding, however, both these algorithm types rely upon soft decisions, and are thus more computationally complex, and require a greater implementation area for the increased logic required. The more computationally complex algorithms also allow reliable communication to be achieved over channels with worse characteristics than the worst channel that MB algorithms can reliably work over. 
   In conventional iterative decoding systems, such as the one illustrated in  FIG. 1 , decoder  100  will iteratively decode the received sequence of samples using a selected algorithm by repeatedly passing extrinsic messages between the variable and check-nodes. The algorithm used by the nodes is selected based on an acceptable trade-off in the number of iterations required, the time required by each iteration, and the implementation complexity. The implemented algorithm is preferably selected and implemented with knowledge about the characteristics of the transmission channel and the encoding method. The arrangement of the edges is specifically related to the encoding methodology, and allows for the decoding of encoded messages. The selection of the decoding algorithm based on knowledge of the transmission channel allows algorithms to be refined to improve their decoding performance based on specific channel properties such as noise distribution. 
   Although soft decision algorithms provide improved performance, they impose implementation complexity penalties related to the time required to execute each iteration and to the required implementation area. Decoders implemented solely in software are concerned largely with the first of the penalties, while dedicated hardware decoders are more concerned with the second of the penalties. In a hardware decoder, the increased logic required to implemented soft decoding algorithms also imposes a power consumption penalty, which often serves as an incentive to use hard decision algorithms such as MB algorithms despite the longer convergence time. 
   In the 1960&#39;s Gallager offered a hybridized decoder architecture that offers some of the performance advantages of soft decision decoding while reducing the computational complexity required by conventional soft decision decoders. The decoder taught by Gallager is a type of a hybrid switch type (H ST ) decoder. If a decoding operation can be represented by a function Δ, the hybrid switch type decoding operation is represented by a function Δ(l), where l represents the iteration number. The simplest of the hybrid switch type decoders is represented by the function 
   
     
       
         
           
             Δ 
             ⁡ 
             
               ( 
               l 
               ) 
             
           
           = 
           
             { 
             
               
                 
                   
                     
                       
                         Δ 
                         A 
                       
                       , 
                       
                         0 
                         ≤ 
                         l 
                         ≤ 
                         x 
                       
                     
                   
                 
                 
                   
                     
                       
                         Δ 
                         B 
                       
                       , 
                       
                         x 
                         &lt; 
                         l 
                       
                     
                   
                 
               
               . 
             
           
         
       
     
   
   Graphically represented, the decoder is identical to the decoder illustrated in  FIG. 1  for 0≦l≦x. However, after the x th  iteration, a new set of operators are performed by the check and variable-nodes to perform the decoding operation. This allows a switch between decoding algorithms. After the x th  iteration, the hybrid switch type decoder is represented by decoder  122  of  FIG. 2 . Variable-node v 1B    124 , v 2B    126 , v 3B    128 , v 4B    130 ,  132  and v 6B    134  connect to the check-nodes c 1B    136 , c 2B    138 , c 3B    140  and c 4B    142 , same configuration as the decoder of  FIG. 1 , however, both the check and the variable-nodes perform different operations that correspond to the new decoding function Δ B . Along with the new operators, the style of message passed along the edges can also change at the switch point. 
   The H ST  architecture decoders allow for a fixed number of iterations to be performed using a more complex decoding algorithm, while allowing the bulk of the iterations to be performed with simple to implement decoding algorithms such as MB algorithms. Even a few iterations using a more robust operation, such as min-sum, greatly reduces the performance gap between the robust and the computationally simple implementations, while also reducing the overall computational intensity of the decoding operation. It has also been found the even if only MB algorithms are used, H ST  implementations provide performance improvements over the constituent codes. One great detriment to the implementation of hardware based H ST  decoders is the increased implementation area required. Because the variable and check-nodes for each iteration grouping perform different operations, different sets of variable and check-nodes must be provided, as does message routing circuitry for managing the switchover between operations.  FIG. 3  illustrates an exemplary logical implementation of an H ST  decoder for 
             Δ   ⁡     (   l   )       =     {               Δ   A     ,     0   ≤   l   ≤   x                   Δ   B     ,     x   &lt;   l             .             
As illustrated in  FIG. 3 , the implementation of an H ST  decoder  144  requires the connection of decoder  100  to decoder  122 . The overall structure includes the variable and check-nodes corresponding to function Δ A , v 1A    102 , v 2A    104 , v 3A    106 , v 4A    108 , v 5A    110 , v 6A    112 , c 1A    114 , c 2A    116 , c 3A    118  and c 4A    120  arranged as they are in  FIG. 1 . However, the check-nodes, c 1A    114 , c 2A    116 , c 3A    118  and c 4A    120 , have an external control so that after a predetermined number of iterations, in this example after the x th  iteration, the check-nodes pass the message to the variable-nodes corresponding to the second decoding function Δ B , v 1B    124 , v 2B    126 , v 3B    128 , v 4B    130 , v 5B    132  and v 6B    134 . The second set of variable-nodes iteratively pass messages to the second set of check-nodes c 1B    136 , c 2B    138 , c 3B    140  and c 4B    142 , with the same edge configuration. The connection of the first set of check-nodes to the second set of variable-nodes uses the same edge mapping as the first stage. One skilled in the art will appreciate that if the function performed by the first and second set of check-nodes is the same, the second set of check-nodes could be omitted, and the messages would be passed along the edges between the check-node and each of the two sets of variable-nodes as determined by the routing control. In another embodiment, if the variable-nodes perform the same operation, but the check-nodes perform a different operation after the switch, the variable-nodes can be reused.
 
   The implementation of  FIG. 3  illustrates one of the great disadvantages of the hardware implementation of an H ST  decoder. Because the variable-nodes and check-nodes perform different operations, each function used in an H ST  decoder must have its own set of variable-nodes. Thus, the performance benefit of the H ST  decoder is offset by an implementation complexity penalty. Re-use of circuitry between the two different sets of variable-nodes is difficult as the logic used for different operators does not typically provide a great deal of overlap. Furthermore, soft decision operators heavily rely upon a characterization of the transmission channel, and repeated iterations using soft decision operators relying upon an erroneous characterization are known to decrease the performance of a decoder. 
   Codes can be classified as either regular or irregular based on their graphical representations. In a regular code, each variable-node connects to the same number of check-nodes as every other variable-node, and similarly every check-node connects to the same number of variable-nodes as every other check-node. Thus a code described as a regular (d v , d c ) code has every variable-node connected to d v  check-nodes, and every check-node connected to d c  variable-nodes. In such a code, the variable-nodes are referred to as being of degree d v  as they each have d v  edges. In an irregular code, nodes can be grouped by their degree, so that one grouping of variable-nodes are of degree d v1 , while another grouping are of degree d v2 . Thus the variable-nodes in the first grouping connect to d v1  check-nodes, while the variable-nodes in the second grouping connect to d v2  check-nodes. Check-nodes can be similarly partitioned. 
   In an irregular H ST  decoder, each node in a degree grouping switches to the next constituent algorithm with the other nodes in its group, but not necessarily with the all other nodes of its type. As a result, an H ST  decoder having 20% of its variable-nodes of degree d v1 , and 80% of its variable-nodes of degree d v2 , switching between MB algorithms can have all variable-nodes start with MB 0 , after the 10 th  iteration have all variable-nodes of degree d v1  switch to MB 1 , after the 15 th  iteration have all variable-nodes of degree d v2  switch to MB 2 , and after the 20 th  iteration have all variable-nodes of degree d v1  also switch to MB 2 . Irregular H ST  decoders provide performance improvements over regular H ST  decoders with proper selection of the degree groupings, the constituent algorithms assigned to the groupings and the iteration at which algorithms are switched. In each of the MB algorithms, the check-nodes perform the same operation, so switching between consistent algorithms in the check-nodes is not necessary. The irregularity described above relates to an irregular edge structure. 
   From the above discussion it is apparent to one skilled in the art, that standard iterative decoders either lack sufficient performance and require too many iterations to converge, or rely upon complex circuitry and channel characterizations that must be accurate, while H ST  decoders are difficult to implement in hardware, and regardless of how they are implemented are heavily reliant upon the correct characterization of the transmission channel to obtain desired performance. Though channel characterization is possible, it is often found that the laboratory characterization of channel does not identically correspond to real world situations, where installation of a physical channel can introduce irregularities in the channel properties, as does the aging of an installed channel. Non-installed channels, such as wireless communications links, are also subject to unplanned changes in their characteristics over finite time intervals, which adversely affect the performance of functions dependent upon accurate channel characterization. 
   It is, therefore, desirable to provide an iterative decoder architecture that simplifies implementation in hardware, and offers a reasonable degree of immunity to variation in the characterization of a channel. 
   SUMMARY OF THE INVENTION 
   It is an object of the present invention to obviate or mitigate at least one disadvantage of previous iterative decoders. 
   In a first aspect of the present invention, there is provided an iterative decoder for receiving a sequence of sample representing a series of symbols, and for decoding the received sequence to the series. The decoder comprises a plurality of variable-nodes. Each node for receiving and storing a sample from the sequence, for iteratively passing messages to, and receiving messages from, at least two connected check-nodes in a plurality of check-nodes, for sending each connected check-node a message determined in accordance with the stored sample and message received from the at least one other check-node segment, and for providing as output a decoded symbol determined in accordance with the received messages from the connected check-nodes and the stored sample. At least one node selected from the plurality of variable-nodes and the plurality of check-nodes forms a partition in the respective plurality, the at least one node being of the same degree as at least one node in the at least one other partition, the nodes in each partition using an operation unique to the partition to determine the message to pass to connected nodes. 
   In an embodiment of the first aspect of the present invention, the number of nodes in each partition is determined using a probability mass function. In another embodiment, the operations performed by each node correspond to either a hard decision based decoding operation, such as a majority based decoding operation, or a soft decision based decoding operation such as max-log, max-log-APP, belief propagation, and min-sum decoding operations. In another embodiment, each variable-node is connected to at least 2 check-nodes. 
   In another aspect of the present invention, there is provided an iterative decoder for decoding a sequence of samples to a series of symbols. The decoder has a plurality of nodes. The plurality has a check-node segment and a variable-node segment. Each segment has at least two nodes. Each node in the plurality has a degree, preferably defined by the number of nodes connected to it. Each node is connected to at least two other nodes in the other segment for receiving a message from the connected nodes. Each of the nodes in the variable-node segment is for receiving and storing a sample from the sequence of samples, for sending each connected node in the check-node segment a message determined in accordance with the stored sample and messages received from the at least one other node in the check-node segment, and for providing as output a decoded symbol determined in accordance with the received messages from connected nodes in the check-node segment and the stored sample. Each of the nodes in the check-node segment is connected to at least two nodes in the variable-node segment, and is for receiving and transmitting messages to each connected node in the variable-node segment, the transmitted messages determined in accordance with the result of an operation performed on messages received from the at least one other connected node. At least one of the nodes in the plurality determines messages in accordance with a different operation than at least one other node having the same degree in the same segment. 
   In a further aspect of the present invention, there is provided a method of decoding a sequence of samples to a series of symbols in an iterative decoder having a plurality of variable-nodes and plurality of check-nodes, each of the nodes in each plurality connected to at least two nodes in the other plurality, the number of connections to any node in the plurality defining the degree of the node. The method comprises receiving and storing one of the samples in the sequence at each of the variable-nodes in the plurality; passing a message from each variable-node in the plurality of variable-nodes, to the connected nodes in the plurality of check-nodes, the message determined in accordance with an operation performed on the stored sample; passing a message from each check-node to the connected nodes in the plurality of variable-nodes, the message for each connected node determined in accordance an operation performed on the at least one other message received at the check-node; at each of the variable-nodes in the plurality, receiving at least two messages from connected nodes, and passing a message to each connected node, the message for each connected node determined in accordance with the message received from the at least one other connected node and the stored sample; repeating both the steps of passing a message and the step of receiving and passing, for a predetermined number of iterations, in at least one of the iterations, at least one of the nodes selected from either of the pluralities for passing a message determined in accordance with an operation distinct from the operation performed by at least one other node of the same degree in its plurality; and providing as an output, from each variable-node in the plurality of variable-nodes a decoded symbol determined in accordance with the messages received from the connected nodes in the final iteration and the stored sample. 
   In an embodiment of the present invention, each sample is one bit in length. In another embodiment, the operation performed by each variable-node is selected from a list including soft decision and hard decision decoding operations such as a majority based operation. In another embodiment, the operation performed by each check-node is selected from a list including soft decision and hard decision decoding operations, where preferably the operation is a majority based operation. In another embodiment, the number of iterations is predetermined to provide an acceptable error rate, and optionally wherein in all iterations, at least one node passes a message determined in accordance with an operation distinct from the operation performed by at least one other node of the same degree in its plurality. In a further embodiment, the number of nodes passing a message determined in accordance with an operation distinct from the operation performed by at least one other node of the same degree in its plurality, is determined by a probability mass function. In another embodiment, the operation used by each node to determine messages is time invariant. In a further embodiment, the particular nodes passing a message determined in accordance with an operation distinct from the operation performed by at lest one other node of the same degree in its plurality are determined randomly. In a further embodiment at least one check-node and at least one variable-node pass messages determined using operations distinct from the operations performed by at least one other node of the same degree in their respective pluralities. 
   Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Embodiments of the present invention will now be described, by way of example only, with reference to the attached Figures, wherein: 
       FIG. 1  is an illustration of a logical representation of a prior art iterative decoder; 
       FIG. 2  is an illustration of a logical representation of the second stage of a prior art hybrid switch type iterative decoder; 
       FIG. 3  is an illustration of a logical representation of a two stage hybrid switch type decoder; 
       FIG. 4  is an illustration of the logical representation of a system of the present invention; 
       FIG. 5  is a graph showing the density-evolution of an H TI  algorithm; 
       FIG. 6  is a graph showing the density-evolution of an H ST  algorithm; 
       FIG. 7  is a graph showing convergence domains associated with ε* {MB H     TI     } , 0.9ε* {MB H     TI     } , and 0.8ε* {MB H     TI     } ; 
       FIG. 8  is a graph comparing the bit error rate performance of finite length H ST  and H TI  decoders 
       FIG. 9  is a graph showing error-rate curves versus iteration number, for the two algorithms and for several channel parameters; 
       FIG. 10  is a graph showing the density-evolution of H TI  and H ST  decoders; and 
       FIG. 11  is a graph comparing the convergence times for H TI  and H ST  algorithms with misestimated ε values. 
   

   DETAILED DESCRIPTION 
   The present invention relates to a novel iterative decoder architecture. Though the discussion presented below is directed to the iterative decoding of LDPC codes, this is solely to provide a compact discussion. The novel method and system of the present invention can be applied to other code types requiring iterative decoding, including turbo-codes. 
     FIG. 4  illustrates the logical graph representation of a decoder  200  of the present invention. Where prior art systems use one decoding algorithm per decoder, or per decoder iteration, for each node degree, the present invention utilizes multiple decoding algorithms. Nodes having different decoding operations, and thus nodes that perform different decoding operations, are represented by different node symbols in  FIG. 4  for the sake of clarity. 
   Because the structure of the decoder utilizes multiple algorithms it can be classified as a hybrid decoder. In distinction to the H ST  decoder taught in the prior art, the present invention can be implemented in a time invariant manner, so that the distribution of the multiple algorithms does not vary between iterations. As a result the present invention is herein referred to as a hybrid time-invariant (H TI ) decoders. In another embodiment, the distribution of the decoding algorithms is fixed, but the operation performed by a node can vary between iterations. Where irregularly structured decoders in the prior art provide performance advantages over regularly structured decoders, the present invention takes advantage of an irregularity in the decoding operation which can be implemented with either regularly or irregularly structured decoders. 
     FIG. 4  illustrates the logical architecture of H TI  decoder  200 . Decoder  200  has a plurality of nodes segmented into variable-nodes, which are also referred to as bit nodes, H TI v 2   204 , H TI v 3   206 , H TI v 4   208 , H v v 5   210  and H TI v 6    212  and check-node H TI C 1    214 , H TI c 2    216 , H TI c 3    218  and H TI c 4    220 . The variable-nodes are partitioned according to the operation that they each perform. H TI V 1    202 , H TI v 3    206  and H TI v 5   210  form a partition, while H TI V 2    204  and H TI v 6    212  form another. The check-nodes are similarly partitioned, with H TI C 1    214 , H TI c 3    218  and H TI c 4    220  forming one partition, while H TI c 2    216  forms the other. 
   Each node performs an operation defined by a decoding algorithm that it shares with the other nodes in the same partition. Each partition has its own defined algorithm. The nodes in each partition need not be limited to nodes of the same degree. While an irregular decoder may have all nodes of a first degree performing one decoding operation, while all nodes of a second degree perform another, the decoder of the present invention, does not require that the partitions be made using degree as a distinction. Thus, the present invention utilizes a node performing a decoding operation different than the operation performed by at least one other node of the same degree. Thus, H TI  decoders can be either regular or irregular in structure and still perform a plurality of decoding operations in at least one decoding iteration. 
     FIG. 4  should be viewed as exemplary and not as restrictive. Any number of nodes can form a partition, and the number of partitions in the check and variable segments need not be the same. Thus, the present invention can be reduced to an almost standard decoder where one node performs a different operation than at least one other node of the same type and having the same degree in at least one iteration. 
   In operation, decoder  200  receives a sequence of sample corresponding to a series of symbols transmitted over a channel. The sequence of samples cannot be simply mapped to a series of symbols because noise during transmission may have corrupted the transmission. However, the error-correcting code used in the encoding process allows for the decoding operation to correct a predetermined number of incorrect symbols. As in a standard decoder, each variable-node receives a sample representing a channel message. As a function of the received channel message, a message is determined and is passed to each connected check-node along the defined edges. Each check-node then determines a message to pass back along the edges based on the other messages received. Thus, if a check-node has three edges, it determines three different messages to pass back, each message a function of the received messages. To complete the iteration, each variable-node receives one message per edge. In the next iteration, a new extrinsic message, for each edge, is determined in accordance with the channel message, and the message received from the other edges. This process repeats until the required number of iterations is completed. In the present invention, each variable-node receives a sample, and performs an operation defined by an algorithm shared by other nodes in the same partition. For the sake of simplicity, the following discussion will focus only upon standard MB algorithms to allow for a simpler performance analysis. One skilled in the art will appreciate that other algorithms can be used without departing from the scope of the present invention. Thus, H TI v 1    202 , H TI  v 3    206  and H TI v 5   210  perform one standard decoding operation, such as MB 0 , while H TI v 2   204  and H TI v 6   212  perform another, such as MB 1 . Each operation is performed at a variable-node, and a message is passed from the variable-nodes to the check-nodes that they are connected to by edges. H TI c 1    214 , H TI c 3    218  and H TI c 4    220  then perform one check-node operation, while H TI c 2    216  performs forms another. Upon completion of the check-node operation, a message is passed back to the variable-nodes, where a further operation is performed using the received message. This process continues for a predefined number of iterations, until the process terminates, and the variable-nodes contain the decoded sequence. The selection of nodes for each partition can be done randomly using a probability mass function as is described below. 
   A more technical view of the present invention will now be presented. 
   An LDPC code, like any other linear block code, can be fully described by its parity-check matrix. A “1” located at position (i, j) of the code&#39;s parity-check matrix indicates that the j th  bit of any codeword participates in the i th  parity-check equation. However, as the adjective low-density suggests, the parity-check matrix of a typical LDPC code is sparse. This property results in iterative decoding algorithms having feasible complexity even at large block lengths. The structure of an LDPC code is well portrayed using bipartite graphs, such as the one provided in  FIG. 4 , constructed based on the code&#39;s parity-check-matrix. The two sets of nodes in such graphs, the variable-nodes and the check-nodes, correspond to the columns and the rows of the parity-check matrices, respectively. In the graphical representation of a code, an edge connects variable-node v j  and check-node c i  if and only if a “1” is located at position (i, j) of the parity-check matrix. 
   In a regular LDPC code, column and row weights of the parity-check matrix are fixed. In particular, a (d v , d c )-regular LDPC code is a code described by a parity-check matrix in which the column weight is d v  (meaning that each bit participates in d v  parity-check equations) and the row weight is d c  (meaning that each parity-check equation checks the parity among d c  bits). If all the rows are linearly independent, the rate of such a code is 1-d v /d c . In a graphical representation, each variable-node connects to d v  check-nodes, and each check-node connects to d c  variable-nodes. Codes that do not follow this pattern are regarded as irregular codes. As described above, in an irregular LDPC code, column and row weights of the parity-check matrix are chosen according to some degree distributions. By carefully choosing the distributions, code&#39;s error performance can be considerably improved. The decoding process is performed by iteratively exchanging messages between variable-nodes and check-nodes along the edges of the graph representing the code in both directions. An iterative decoding algorithm is said to be based on message-passing if only extrinsic messages are exchanged. A message-passing decoding algorithm is specified by its variable-node and check-node message mappings, which represent the processing performed at the variable-nodes and the check-nodes, respectively. 
   Hybrid decoding algorithms belong to the family of message-passing decoding algorithms, and are devised by combining existing algorithms. Hybrid algorithms are capable of improving error performance and convergence speed at the expense of a small increase in the complexity of the decoder&#39;s structure. 
   Consider C n (d v , d c ), the ensemble of (d v , d c )-regular LDPC codes of length n, and suppose that Δ 0 ,Δ 1 , . . . , Δ N-1  are N message-passing algorithms which can be used to decode C n (d v , d c ) over a given channel. Each algorithm Δ i , 0≦i≦N-1, is specified in iteration l, l≧0, by Ψ i,v   (l)  and Ψ i,c   (l)  its variable-node and check-node message maps, respectively. Assuming that all messages have the same alphabet space M, a new message-passing decoding algorithm Δ can be formulated and defined based on Δ 0 ,Δ 1 , . . . ,Δ N-1  as follows. In iteration l of Δ, variable-nodes and check-nodes are randomly partitioned into N groups according to probability mass function (pmf) vectors {right arrow over (α)} (l) =(α 0   (l) ,α 1   (l) , . . . ,α N-1   (l) ) and {right arrow over (β)} (l) =(β 0   (l) ,β 1   (l) , . . . , β N-1   (l) ), respectively, and the nodes in group i, 0≦i≦N-1, process the messages in accordance with the constituent algorithm Δ i . The new algorithm is said to be the hybrid of Δ 0 ,Δ 1 , . . . ,Δ N-1  according to hybridization sequences {{right arrow over (α)} (l) } l=0   ∞  and {{right arrow over (β)} (l) } l=0   ∞ , and this is denoted by Δ=H(Δ 0 ,Δ 1 , . . . ,Δ n-1 ,{{right arrow over (α)} (l) } l=0   ∞ , {{right arrow over (β)} (l) } l=0   ∞ ). Note that Δ can be symbolically specified with message maps 
               Ψ   v     (   l   )       =       ∑     i   =   0       N   -   1       ⁢           ⁢       α   i     (   l   )       ⁢     Ψ     i   ,   v       (   l   )             ,         
and
 
   
     
       
         
           
             Ψ 
             c 
             
               ( 
               l 
               ) 
             
           
           = 
           
             
               ∑ 
               
                 i 
                 = 
                 0 
               
               
                 N 
                 - 
                 1 
               
             
             ⁢ 
             
                 
             
             ⁢ 
             
               
                 β 
                 i 
                 
                   ( 
                   l 
                   ) 
                 
               
               ⁢ 
               
                 
                   Ψ 
                   
                     i 
                     , 
                     c 
                   
                   
                     ( 
                     l 
                     ) 
                   
                 
                 . 
               
             
           
         
       
     
   
   The above definition of hybrid algorithms is quite general and covers both H TI  and H ST  algorithms. In H TI  algorithms, {{right arrow over (α)} (l) } l=0   ∞  and {{right arrow over (β)} (l) } l=0   ∞  are independent of l. 
   In the following, a few illustrative examples are examined to show how hybrid algorithms can improve error performance and convergence speed. In all the examples, as well as the rest of the paper, it is assumed that hybrid algorithms&#39; constituents belong to the family of majority-based (MB) algorithms. More precisely, it is assumed that in all the examples C ∞ (d v , d c ) is decoded over a binary symmetric channel (BSC), using Δ=H(MB 0 ,MB 1 , . . . ,MB d     v     −1−┌d     v     /2┐ , {{right arrow over (a)} (l) } l=0    ∞ . {{right arrow over (β)} (l) } l=0   ∞  is omitted from the equation because a plurality of MB codes are being used, and all check-nodes perform the same operation for MB decoding. As a result, the check-nodes are not partitioned, and only the variable-nodes are partitioned according to the pmf. Such hybrid algorithms are referred to as MB hybrid algorithms. The assumption of majority-based constituents makes the analysis simpler since keeping track of the expected fraction of incorrect messages throughout the iteration process can be performed using closed form formulas. 
   For a given channel parameter ε, an MB algorithm of order ω, 0≦ω≦d v −1−┌d v /2┐ can be represented by a density-evolution curve ƒ ε   ω (x). Using such a curve, the evolution of the expected fraction of erroneous messages passed in each iteration from a variable-node to a check-node can be tracked. Similarly, the curve 
               h   ɛ     α   -&gt;       ⁡     (   x   )       =       ∑     ω   =   0         d   v     -   1   -     ⌈       d   v     /   2     ⌉         ⁢           ⁢       α   ω     ⁢       f   ɛ   ω     ⁡     (   x   )                 
which is a linear combination of ƒ ε   ω (x) curves represents the density-evolution of the H TI  algorithm devised by blending MB algorithms according to the vector {right arrow over (α)}=(α 0 ,α 1 , . . . ,α d     v     −1−┌d     v     /2 ┐). The sequence of error probabilities for such an H TI  algorithm is monotonic, and is strictly decreasing, constant or strictly increasing if and only if h ε   {right arrow over (α)} (ε) is less than, equal to, or greater than ε, respectively. The sequence also iteratively converges to zero if and only if h ε   {right arrow over (α)} (x)&lt;x, ∀x∈(0,ε].
 
   Consider C ∞ (8, 9) and the four MB algorithms that can be used to decode this ensemble over a BSC, namely MB 0 , MB 1 , MB 2 , and MB 3 . Also, consider Δ 0 , the H TI  algorithm that blends these MB algorithms according to {right arrow over (α)}=(0,0.2,0.8,0).  FIG. 5  depicts the curves representing Δ 0  and its constituents for a channel with ε=0.0720. 
   One can see that the necessary and sufficient condition for the convergence of error probability to zero, i.e., ƒ ε     0     ω (x)&lt;x, ∀x∈(0, ε 0 ] is not satisfied for either one of constituent MB algorithms. (It can be easily verified that the average probability of error increases with iterations for MB 0  and MB 1 , while for MB 2  and MB 3 , although the average error probability decreases with iterations, it does not approach zero). On the other hand, as the portrayed evolution of the expected fraction of erroneous messages for Δ 0  shows, the average probability of error for this H TI  algorithm converges to zero by increasing the number of iterations, and there is still room for Δ 0  to cope with even worse channels. Much the same as H TI  algorithms, an H ST  algorithm can be represented by a combination of the curves representing its constituents. This combination, however, is piecewise instead of linear. 
   An H ST  algorithm is presented below for comparison purposes to the above described H TI  algorithm. Δ 0  is specified by 
               α   -&gt;     0     (   l   )       =     {               (     0   ,   0   ,   1   ,   0     )     ,     l   ≤   4                   (     0   ,   1   ,   0   ,   0     )     ,   otherwise           .               FIG. 6  illustrates the curve representing Δ 0  and its constituents for a channel with ε=0.0720.  FIG. 6  also illustrates the evolution of the expected fraction of erroneous messages for Δ 0 , which converges monotonically to zero with iterations.
 
   In decoding simulations comparing the exemplary H TI  and H ST  algorithms to each other, it was found that both decoding algorithms provide improved decoding performance over a standard decoder, though the H ST  decoder still offers improved performance over the H TI  decoder. However, the H TI  algorithm does converge, though more slowly than the H ST  algorithm, while its consistent codes MB 1  and MB 3  do not provide a guarantee of convergence to as small a target error rate. The H TI  algorithms also provide an easier implementation in hardware than the corresponding H ST  algorithm. Additional convergence properties of H TI  decoders are described below. 
   For a message-passing algorithm, the supremum of all channel parameters for which the probability of error converges to zero, is called the threshold. The convergence of an MB hybrid algorithm&#39;s error probability to zero for a channel parameter ε implies its convergence to zero for every channel parameter ε 1 &lt;ε. Therefore, for all channel parameters less than an MB hybrid algorithm&#39;s threshold, the expected fraction of erroneous messages passed in iteration l approaches zero as l tends to infinity, and for all channel parameters greater than the threshold, this fraction is bounded away from zero. For MB hybrid algorithms, the threshold can be maximized over all sequences {{right arrow over (α)} (l) } l=0   ∞ ; the maximum threshold is denoted by ε* {MB H     TI     } . For MB H TI  algorithms, in particular, we can formulate the maximum threshold as 
   
     
       
         
           
             ɛ 
             
               { 
               
                 MBH 
                 TI 
               
               } 
             
             * 
           
           = 
           
             
               max 
               
                 α 
                 -&gt; 
               
             
             ⁢ 
             
               
                 { 
                 
                   sup 
                   ⁢ 
                   
                     ⌊ 
                     
                       
                         
                           ɛ 
                           ∈ 
                           
                             [ 
                             
                               0 
                               , 
                               0.5 
                             
                             ] 
                           
                         
                         ❘ 
                         
                           
                             
                               h 
                               ɛ 
                               
                                 α 
                                 -&gt; 
                               
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           &lt; 
                           x 
                         
                       
                       , 
                       
                         ∀ 
                         
                           x 
                           ∈ 
                           
                             ( 
                             
                               0 
                               , 
                               ɛ 
                             
                             ] 
                           
                         
                       
                     
                     ⌋ 
                   
                 
                 } 
               
               . 
             
           
         
       
     
   
   Consider C ∞ (d v , d c ) and all the MB H TI  algorithms that can be used to decode this ensemble, either successfully or unsuccessfully, over a binary symmetric channel (BSC) with parameter ε. It is clear that the convergence of the error probability to zero with iterations for an MB H TI  algorithm depends on the corresponding pmf vector {right arrow over (α)}, as well as the value of channel parameter ε. Any pmf vector {right arrow over (α)}=(α 0 ,α 1 , . . . α d     v     −1−┌d     v     /2┐ ) represents a single point in the d v −1−┌d v /2┐-dimensional hyperplane defined by 
               ∑     ω   =   0         d   v     -   1   -     ⌈       d   v     /   2     ⌉         ⁢           ⁢     α   ω       =   1.         
Depending on ε, the average probability of error converges to zero with iterations for some points in this hyperplane. We call the set of all such points convergence domain associated with ε, and denote it by              ε , which can be shown to be convex. It is also not difficult to see that            ε ⊂           ε′  if ε′&gt;ε. Thus by increasing ε, the convergence domain shrinks. In the limit, as ε tends to the maximum threshold ε* {MB H     TI     } , the domain shrinks to a single-element set containing {right arrow over (α)}* {MB H     TI     } .

   Consider C ∞ (5, 10). The maximum threshold ε* {MB H     TI     }  for this ensemble is equal to 0.0374, which is achieved using a {right arrow over (α)} {MB H     TI     } =(0.2589, 0.7411). The thresholds for constituent algorithms MB 0  and MB 1  are 0.0248 and 0.0277, respectively, both of which are considerably smaller than ε* {MB H     TI     } .  FIG. 7  illustrates the convergence domains associated with channel parameters ε* {MB H     TI     } , 0.9ε* {MB H     TI     } , and 0.8ε* {MB H     TI     } . Notice that the hyperplane and the convergence domains here are one-dimensional (line segments). Also, notice that              ε*     {MB HTI}   ⊂           0.9ε*     {MB HTI}    ⊂           0.8ε*     {MB HTI}   .
   It is worth mentioning that if the objective is to maximize algorithm&#39;s speed of convergence at a target error-rate ι for a channel parameter ε, the problem of finding the optimal vector {right arrow over (α)}* ε,ι , which does not necessarily belong to              ε , can be formulated as the minimization problem. The objective is to minimize for l≧0, subject to α ω ≧0,0≦ω≦d v −1−┌d v /2┐ and
               ∑     ω   =   0         d   v     -   1   -     ⌈       d   v     /   2     ⌉         ⁢           ⁢     α   ω       =   1         
and
 
                       h   ɛ     α   -&gt;       ∘           ⁢     h   ɛ     α   -&gt;       ∘           ⁢   …   ⁢           ∘           ⁢     h   ɛ     α   -&gt;         ︸       l   ⁢           ⁢   times       ⁢     (   ɛ   )       ≤   i     ,         
where ‘∘’ denotes the composition of two functions.
 
   Table 1, presented below, lists the threshold values of MB algorithms and the maximum threshold values of MB H TI  and H ST  algorithms for several (d v , d c ) pairs. As can be seen, both hybrid algorithms have significantly higher (maximum) thresholds compared to their constituents, which is an indivation of their superior performance. 
   
     
       
             
             
             
             
             
             
             
           
         
             
               TABLE 1 
             
             
                 
             
             
               (d v , d c ) 
               ε* MB     0     
               ε* MB     1     
               ε* MB     2     
               ε* MB     3     
               ε*{ MB H     TI   } 
               ε*{ MB H     ST   } 
             
             
                 
             
           
           
             
               (4, 5) 
               0.0260 
               0.0833 
               — 
               — 
               0.0947 
               0.0963 
             
             
               (4, 6) 
               0.0159 
               0.0666 
               — 
               — 
               0.0724 
               0.0747 
             
             
               (4, 7) 
               0.0107 
               0.0555 
               — 
               — 
               0.0586 
               0.0611 
             
             
               (4, 8) 
               0.0077 
               0.0476 
               — 
               — 
               0.0491 
               0.0516 
             
             
               (4, 9) 
               0.0058 
               0.0416 
               — 
               — 
               0.0423 
               0.0447 
             
             
               (4, 10) 
               0.0045 
               0.0370 
               — 
               — 
               0.0371 
               0.0378 
             
             
               (5, 6) 
               0.0650 
               0.0500 
               — 
               — 
               0.0822 
               0.0865 
             
             
               (5, 7) 
               0.0482 
               0.0416 
               — 
               — 
               0.0640 
               0.0686 
             
             
               (5, 8) 
               0.0374 
               0.0357 
               — 
               — 
               0.0520 
               0.0566 
             
             
               (5, 9) 
               0.0301 
               0.0312 
               — 
               — 
               0.0436 
               0.0480 
             
             
               (5, 10) 
               0.0248 
               0.0277 
               — 
               — 
               0.0374 
               0.0416 
             
             
               (6, 7) 
               0.0306 
               0.0806 
               0.0333 
               — 
               0.0851 
               0.0858 
             
             
               (6, 8) 
               0.0236 
               0.0648 
               0.0285 
               — 
               0.0691 
               0.0704 
             
             
               (6, 9) 
               0.0188 
               0.0536 
               0.0250 
               — 
               0.0576 
               0.0593 
             
             
               (6, 10) 
               0.0155 
               0.0453 
               0.0222 
               — 
               0.0491 
               0.0510 
             
             
               (7, 8) 
               0.0494 
               0.0854 
               0.0238 
               — 
               0.0858 
               0.0858 
             
             
               (7, 9) 
               0.0405 
               0.0717 
               0.0208 
               — 
               0.0724 
               0.0724 
             
             
               (7, 10) 
               0.0339 
               0.0615 
               0.0185 
               — 
               0.0623 
               0.0624 
             
             
               (8, 9) 
               0.0296 
               0.0601 
               0.0719 
               0.0178 
               0.0756 
               0.0756 
             
             
               (8, 10) 
               0.0247 
               0.0511 
               0.0640 
               0.0158 
               0.0664 
               0.0664 
             
             
               (9, 10) 
               0.0409 
               0.0653 
               0.0552 
               0.0138 
               0.0701 
               0.0702 
             
             
                 
             
           
        
       
     
   
   Comparison of ε* {MB H     TI     }  and ε* {MB H     ST     }  values in Table 1 shows that MB H TI  algorithms are slightly inferior, in terms of performance, to their switch-type counterparts. However, at finite lengths the trend can change with MB H TI  algorithms slightly outperforming MB H ST  algorithms. Moreover, MB H TI  algorithms are more robust and can better cope with unknown or changing channel conditions.  FIG. 8  compares the finite length H TI  and H ST  decoders to their constituent MB decoders. In this example the code is a randomly constructed (8,9)-regular LDPC code of length 9×10 3 , decoded by MB 0 , MB 1 , MB 2 , MB 3 , Δ* TI =H TI (MB 0 ,MB 1 ,MB 2 ,MB 3 ,{right arrow over (α)}* {MB H     TI     }   (l) =(0,0.15885,084115,0), and 
                     Δ   ST   *     =       H   T1     ⁡     (       MB   0     ,     MB   1     ,     MB   2     ,     MB   3     ,       {       α   -&gt;       {     MB   ⁢           ⁢     H   ST       }       *     (   l   )         }       l   =   0     ∞       )         ⁢     
     ⁢   for                   α   -&gt;       {     MB   ⁢           ⁢     H   ST       }       *     (   l   )         =     {             (     0   ,   0   ,   1   ,   0     )             if   ⁢           ⁢   l     ≤   19               (     0   ,   1   ,   0   ,   0     )             if   ⁢           ⁢   20     ≤   l   ≤   29               (     1   ,   0   ,   0   ,   0     )         otherwise         .                   
all the simulated results, the maximum number of iterations was set to 500. The threshold values for the MB algorithms are ε* MB     0   =0.0296, ε* MB     1   =0.0601, ε* MB     2   =0.0719, and ε* MB =0.0178. Both hybrid algorithms have threshold value of 0.0756. From  FIG. 8  it can bee seen that the H TI  decoder slightly outperforms the H ST  decoder in spite of both algorithms having the same maximum threshold.
 
   Consider C ∞ (4, 5) and the two MB algorithms that can be used to decode this ensemble over a BSC, namely MB 0  and MB 1 . For this ensemble, the maximum thresholds for MB H TI  and H ST  algorithms are ε* {MB H     TI     } =0.0947 and ε* {MB H     ST     } =0.0963, respectively. Assuming that the channel parameter is unknown, and our main concern is to ensure the convergence of MB H TI  or H ST  algorithms for as wide a range of channel parameters as possible, we set both algorithms to achieve their maximum thresholds.  FIG. 9  illustrates error-rate curves versus iteration number, for the two algorithms and for several channel parameters. One can see that although the convergence of MB H ST  algorithms is faster than that of MB H TI  algorithms when the channel parameter is close to the maximum threshold, the performance of H TI  decoders can outpace that of H ST  decoders for a wide range of target error probabilities, and for a wide range of channel parameters less than the maximum threshold.  FIG. 10  illustrates the curves representing MB 0  and MB 1  for Δ* TI , and the corresponding H TI  decoder in a channel with ε 0 =0.8ε* {MB H     ST     } . Also shown is the evolution for Δ* ST =H ST (MB 0 ,MB 1 , {ε* {MB H     SI     } } l=0   ∞ ) on the same channel. It can be seen that because of the non-optimality of the channel parameter setting, the MB H ST  algorithm fails to switch to the right constituent algorithm at the right time, which adversely affects its performance. In this situation, H TI  provides better performance over a wide range of target error probabilities. 
   Consider again C ∞ (4, 5), MB 0 , and MB 1 , and suppose that while the actual channel parameter is ε act =0.0915, due to changes in channel condition, or estimation errors, we underestimate the channel parameter, and set MB H TI  and H ST  algorithms for their fastest convergence at target error-rate of 10 −6  over a channel with estimated parameter ε est =0.0900. (For MB H TI  algorithms, we have {right arrow over (α)} 0.0900,10     −6   =(0.1353,0.8647) and {right arrow over (a)} 0.0915,10     −6   =(0.1310,0.8690). For MB H ST  algorithms, Gallager&#39;s algorithm B provides the optimal switching-sequence. Here, the fastest convergence is achieved by starting with MB 1 , and switching to MB 0  after iteration 11 for ε=0.0900, and iteration 13 for ε=0.0915. The two algorithms are graphically compared in  FIG. 11 . (The subscripts and the superscripts of the curve labels represent ε act  and ε est , respectively.) 
   One can see that while underestimation of the channel parameter results in the failure of the MB H ST  algorithm to converge it has a small effect on the performance of the MB H TI  algorithm. A comparison of TI 0.0915   0.0900  and TI 0.0915   0.0915  shows that the number of iterations required to achieve an error-rate of 10 −6  increases by less than 15% (281 to 320) due to the underestimation of the channel parameter. 
   Also comparing TI 0.0915   0.0947  with TI 0.0915   0.0915  shows that the performance of the algorithm designed to achieve the maximum threshold ε* {MB H     TI     } , on a channel with parameter ε=0.0915 is only slightly inferior to that of the MB H TI  algorithm particularly optimized for this channel (and for target error probability of 10 −6 ), requiring less than 15% increase in the number of iterations. This is in contrast to the case for MB H ST  algorithm. The comparison between ST 0.0915   0.0963 , (ε* {MB H     ST     } =0.0963) and ST 0.0915   0.0915  indicates an increase of nearly 180% in the number of iterations required to achieve an error-rate of 10 −6  (22 to 62). 
   The above examples show that, unlike MB H ST  algorithms, the optimal design for MB H TI  algorithms of the present invention is universal in the sense that the MB H TI  algorithm designed for ε* {MB H      TI     } , performs close to optimal, in terms of convergence speed, on a wide range of channels with ε&lt;ε* {MB H     TI     } . 
   One skilled in the art will appreciate that the present invention can be combined with the H ST  architecture, so that in each iteration a plurality of decoding algorithms are being used, but that at predefined iterations the decoding algorithms are changed. Thus, a decoder, and corresponding method, can be provided that only uses partitioned check- or variable-nodes of the same degree in a single iteration, and logically resembles a standard decoder in all other iterations. The present invention is described as time-invariant due to the fact that in some embodiments, a time-invariant decoder can be constructed. The time invariant nature can be related to either the node-by-node algorithms used, or the pmf distribution of the decoding algorithms. 
   The above-described embodiments of the present invention are intended to be examples only. Alterations, modifications and variations may be effected to the particular embodiments by those of skill in the art without departing from the scope of the invention, which is defined solely by the claims appended hereto.