Abstract:
A method for determining update candidates in a low-density parity-check decoding process includes dividing the quasi-cyclic columns into groups and identifying an update candidate in each group. One or more of the identified update candidates are then updated.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    In an irregular decoder of a regular code, variables with better quality metrics have a greater chance of receiving message updates in early decoding stages. In later stages, variables with worse quality metrics have a greater chance of receiving updates. 
         [0002]    During low-density parity-check decoding iterations, columns are sorted to determine which columns to update. Sorting of a long vector involves long latency and extra sorting logic in circuit. 
         [0003]    Consequently, it would be advantageous if an apparatus existed that is suitable for selecting update candidates in a low-density parity-check decoding process without sorting all of the message columns. 
       SUMMARY OF THE INVENTION 
       [0004]    Accordingly, the present invention is directed to a novel method and apparatus for selecting update candidates in a low-density parity-check decoding process without sorting all of the message columns. 
         [0005]    At least embodiment of the present invention is a method for selecting a low-density parity-check update candidate. A decoder divides all of the message columns into two or more groups. Each message column has a quality metric; within each group, the quality metrics are compared to determine one update candidate from each group. One or more of the update candidates is then updated. 
         [0006]    It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention claimed. The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate an embodiment of the invention and together with the general description, serve to explain the principles. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]    The numerous advantages of the present invention may be better understood by those skilled in the art by reference to the accompanying figures in which: 
           [0008]      FIG. 1  shows a block diagram of a system useful for implementing embodiments of the present invention; 
           [0009]      FIG. 2  shows a parity check matrix for a low-density parity-check decoder; 
           [0010]      FIG. 3  shows a quasi-cyclic circulant matrix representing an element in a parity check matrix; 
           [0011]      FIG. 4  shows a flowchart of a method for selecting circulants to receive updates; 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0012]    Reference will now be made in detail to the subject matter disclosed, which is illustrated in the accompanying drawings. The scope of the invention is limited only by the claims; numerous alternatives, modifications and equivalents are encompassed. For the purpose of clarity, technical material that is known in the technical fields related to the embodiments has not been described in detail to avoid unnecessarily obscuring the description. 
         [0013]    In irregular decoding of a regular low-density parity-check code, better quality variable nodes (variable nodes having metrics such as log-likelihood-ratios indicating a relatively better ability to produce a hard decision) have a better chance of receiving message updates in the early decoding stages. In later stages, worse variable nodes have a better chance of receiving updates. Irregular decoding of regular low-density parity-check codes provides better signal-to-noise ratio gain as compared to regular decoding. 
         [0014]    Referring to  FIG. 1 , a block diagram of a system useful for implementing embodiments of the present invention is shown. The computing device includes a processor  100  connected to a memory  102 . The processor  100  is configured to execute computer executable program code to implement methods according to embodiments of the present invention. The memory  102  is configured to store computer executable program code to implement methods according to embodiments of the present invention and to store output of embodiments of the present invention in appropriate data structures. In at least one embodiment of the present invention, the processor  100  and memory  102  are part of a communication system configured to decode low-density parity-check encoded messages. 
         [0015]    Referring to  FIG. 2 , a parity check matrix for a low-density parity-check decoder is shown. In some embodiments of the present invention, a parity check matrix is a K by L matrix having zero elements  202 ,  204  and non-zero elements defined by a circulant matrix  200 ,  206 . 
         [0016]    Referring to  FIG. 3 , a quasi-cyclic circulant matrix representing an element in a parity check matrix; is shown. A parity check matrix useful in at least one embodiment of the present invention comprises a finite Galois Field. The parity check matrix comprises twelve circulant rows and one hundred eight circulant columns; each circulant in the parity check matrix comprises a sub-matrix. 
         [0017]    Each sub-matrix comprises a forty-eight by forty-eight matrix. A circulant sub-matrix according to at least one embodiment of the present invention includes columns having zero elements  300  and non-zero elements  302  that are defined as an element over a Galois Field. 
         [0018]    In at least one embodiment of the present invention, a low-density parity-check code is decoded. The low-density parity-check code comprises a parity check matrix having elements that are quasi-cyclic circulants. Each quasi-cyclic-circulant is a ninety-six by ninety-six matrix. The parity-check matrix comprises three rows and two hundred eighty-eight columns of quasi-cyclic-circulant matrices. 
         [0019]    Variables within a quasi-cyclic matrix are processed in parallel. An irregular decoder requires sorting of the quality metrics of the two hundred eighty-eight quasi-cyclic columns before message updates. The decoder decides which quasi-cyclic columns will be updated. Sorting quality metrics of the two hundred eighty-eight quasi-cyclic columns takes a substantial amount of time and requires extra circuit logic. Where columns are updated randomly, the quality metric of the column with the highest quality metric out of n columns is approximately 
         [0000]    
       
         
           
             
               θ 
                
               
                 ( 
                 
                   
                     log 
                      
                     
                         
                     
                      
                     n 
                   
                   
                     log 
                      
                     
                         
                     
                      
                     log 
                      
                     
                         
                     
                      
                     n 
                   
                 
                 ) 
               
             
             . 
           
         
       
     
         [0020]    At least one embodiment of the present invention is a load-balancing decoding method to decode a low-density parity-check encoded message without sorting on the quality metrics. 
         [0021]    Load balancing is a methodology in computer science to distribute workload across multiple processors, computers or a computer cluster, network links, central processing units, disk drives, or other resources, to achieve optimal resource utilization, maximize throughput, minimize response time, and avoid overload. 
         [0022]    In at least one embodiment of the present invention, in each iteration, one hundred forty-four pairs of quasi-cyclic columns are chosen  400  in parallel by an affine permutation randomized over time, for example by the global iteration index and local iteration index. The groupings of quasi-cyclic columns are effectively chosen at random. Within each pair, the quality metrics of the two quasi-cyclic columns are compared  402  without regard to any other pair of quasi-cyclic columns. 
         [0023]    Low-density parity-check decoding often requires numerous iterations of updates to unsatisfied constraints. In at least one embodiment of the present invention, the decoder determine  404  if decoding is currently in the first half of global iterations. During the first half of global iterations, the higher quality quasi-cyclic column if each pair is updated  406 , while the lower quality quasi-cyclic column receives no update. During the second half of global iterations, the lower quality quasi-cyclic column if each pair is updated  408 . 
         [0024]    By this method, the maximum quality metric is 
         [0000]    
       
         
           
             
               θ 
                
               
                 ( 
                 
                   
                     log 
                      
                     
                         
                     
                      
                     log 
                      
                     
                         
                     
                      
                     288 
                   
                   
                     log 
                      
                     
                         
                     
                      
                     2 
                   
                 
                 ) 
               
             
             , 
           
         
       
     
         [0000]    or more generally 
         [0000]    
       
         
           
             θ 
              
             
               ( 
               
                 
                   log 
                    
                   
                       
                   
                    
                   log 
                    
                   
                       
                   
                    
                   n 
                 
                 
                   log 
                    
                   
                       
                   
                    
                   2 
                 
               
               ) 
             
           
         
       
     
         [0000]    for n quasi-cyclic columns. Furthermore, while the forgoing discussion specifically concerned pairs of quasi-cyclic columns, the same principle applied to other groupings of columns would yield a maximum quality metric of 
         [0000]    
       
         
           
             θ 
              
             
               ( 
               
                 
                   log 
                    
                   
                       
                   
                    
                   log 
                    
                   
                       
                   
                    
                   n 
                 
                 
                   log 
                    
                   
                       
                   
                    
                   d 
                 
               
               ) 
             
           
         
       
     
         [0000]    where d is the number of columns in each grouping. 
         [0025]    It is believed that the present invention and many of its attendant advantages will be understood by the foregoing description of embodiments of the present invention, and it will be apparent that various changes may be made in the form, construction, and arrangement of the components thereof without departing from the scope and spirit of the invention or without sacrificing all of its material advantages. The form herein before described being merely an explanatory embodiment thereof, it is the intention of the following claims to encompass and include such changes.