Patent Publication Number: US-7584157-B2

Title: Method, device and computer program product for learning correlation matrix

Description:
FIELD OF THE INVENTION 
   The present invention relates to a method, a device and a computer program product for learning a correlation matrix to obtain an optimal correlation matrix used for a decoding system. More particularly, the present invention relates to a method, a device and a computer program product for learning a correlation matrix to decode a block code as an error correction code by using the correlation matrix. 
   BACKGROUND OF THE INVENTION 
   A system for decoding a block code as an error correction code may use, for example, a correlation matrix. A correlation matrix represents correlation between an original pre-coded codeword and a coded codeword, and can be obtained through learning. 
   According to a conventional method for learning and obtaining a correlation matrix, a coded codeword and a pre-learned correlation matrix are used to perform a predetermined calculation, thereby obtaining a result containing multiple components. Then, each of the components contained in the result is compared with a predetermined threshold TH. Based on the comparison, elements of the pre-learned correlation matrix are updated to obtain a post-learned correlation matrix. 
   Specifically, assuming that the original pre-coded codeword has M bits and the coded codeword has N bits, their correlation matrix has N rows and M columns. When this correlation matrix is multiplied by the coded codeword, the result will contain M number of components corresponding to respective bits of the original pre-coded codeword. On the other hand, a threshold TH is set for each of the components of the original pre-coded codeword. Specifically, when a component of the original pre-coded codeword is “+1”, then the threshold is set to “+TH” (TH&gt;0). When a component of the original pre-coded codeword is “0”, then the threshold is set to “−TH”. Each of the components resulting from the calculation is compared with the corresponding threshold “+TH” or “−TH”. When the components resulting from the calculation are to be compared to threshold “+TH”, the components in the corresponding column of the correlation matrix are updated only when their values are lower than “+TH”. On the other hand, when the components resulting from the calculation are to be compared to threshold “−TH”, the components in the corresponding column of the correlation matrix are updated only when their values are higher than “−TH”. 
   Specifically, when the component from the calculation is judged to be lower than the threshold “+TH”, then an update value “±ΔW k ” (ΔW k &gt;0) is added to each component in the corresponding column of the correlation matrix. When a component resulting from the calculation is judged to be higher than the threshold “−TH”, then an update value “±ΔW k ” is subtracted from each component in the corresponding column of the correlation matrix. The sign “±” of the update value for each row depends on the sign “±” of the corresponding bit of the coded codeword. 
   Thereafter, the above-described learning operation is repeated for all of the codewords until update can be no longer performed for the elements of the correlation matrix for all of the codewords. Once the correlation matrix is completely updated, the learning operation is converged and correlation matrix is obtained, which can be used for decoding. 
   When the elements of the correlation matrix have no difference in the calculation results before and after the update, the operation enters an endless loop. In this case, the update value is changed from “±ΔW k ” to “±ΔW k+1 ” (ΔW k &gt;ΔW k+1 &gt;0) and the above-describe learning operation is continued. 
   According to a conventional method for learning a correlation matrix, the update value for learning the correlation matrix is initially set to a high value, and gradually decreased as the learning operation proceeds to rapidly converge the learning operation. However, when the range given by the threshold “TH” set in the learning operation is very large, the number of runs of the learning operation required for all of the codewords becomes larger, thus requiring longer time. 
   Another problem is that an optimal threshold “TH” for converging the learning operation of the correlation matrix for all of the multiple (many) codewords and at the same time for obtaining a sufficient margin for occurrence of bit error of “±TH” for all codewords is unknown. 
   In view of the above-described problems, the present invention has an objective of providing a method, a device and a computer program product for learning a correlation matrix, where the correlation matrix is learned while gradually changing a threshold for learning the correlation matrix to search optimal thresholds for all of the multiple codewords, thereby rapidly obtaining an optimal correlation matrix for all of the codewords. 
   SUMMARY OF THE INVENTION 
   The present invention provides a correlation matrix learning method for obtaining an optimal correlation matrix used for obtaining an original codeword from a codeword, the method comprising the steps of: performing a predetermined calculation with the codeword and a pre-learned correlation matrix; comparing the results from the calculation step with a threshold; updating the pre-learned correlation matrix based on the comparison results obtained in the comparison step to obtain a post-learned correlation matrix; and using the obtained post-learned correlation matrix as a new pre-learned correlation matrix to repeat from the calculation step through the updating step, thereby obtaining an optimal correlation matrix. Every time the comparison results are obtained, it is judged whether or not the comparison results satisfy a first predetermined condition, if so, the threshold (absolute value) is increased at a predetermined rate. 
   The present invention also provides a correlation matrix learning device for obtaining an optimal correlation matrix used for obtaining an original codeword from a codeword, the device comprising; an arithmetic unit for performing a predetermined calculation using the codeword and a pre-learned correlation matrix; a comparison unit for comparing the calculation results output from the arithmetic unit with a threshold; and a learning state monitor for updating the pre-learned correlation matrix based on the comparison results output from the comparison unit to obtain a post-learned correlation matrix, where the obtained post-learned correlation matrix is used as a new pre-learned correlation matrix to repeat the predetermined calculation, the comparison and the updating to obtain an optimal correlation matrix. Every time the learning state monitor receives the comparison results, it judges whether or not the comparison results satisfy a first predetermined condition, and the device further comprises a threshold controller for increasing the threshold (absolute value) at a predetermined rate when the first predetermined condition is satisfied. 
   The present invention further provides a correlation matrix learning computer program product for obtaining an optimal correlation matrix used for obtaining an original codeword from a codeword, the program commanding a computer to execute the steps of: performing a predetermined calculation with the codeword and a pre-learned correlation matrix; comparing the results from the calculation step with a threshold; updating the pre-learned correlation matrix based on the comparison results obtained in the comparison step to obtain a post-learned correlation matrix; using the obtained post-learned correlation matrix as a new pre-learned correlation matrix to repeat from the calculation step through the updating step, thereby obtaining an optimal correlation matrix; and judging whether or not the comparison results satisfy a first predetermined condition every time the comparison result is obtained, if so, the threshold (absolute value) is increased at a predetermined rate. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a block diagram showing a configuration of a correlation matrix learning device according to one embodiment of the invention; 
       FIG. 2  is a flowchart for illustrating the operation by the correlation matrix learning device shown in  FIG. 1 ; 
       FIG. 3  is a diagram for illustrating a range of calculation result y used upon judging whether or not the learning operation for the correlation matrix has converged in the correlation matrix learning device shown in  FIG. 1 ; and 
       FIGS. 4A and 4B  are diagrams showing a rule of learning a correlation matrix in the correlation matrix learning device shown in  FIG. 1 , where  FIGS. 4A and 4B  show the cases where a bit of the original codeword is “1” and “0”, respectively. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   Hereinafter, an embodiment of the present invention will be described in detail with reference to the drawings. 
     FIG. 1  is a block diagram showing a configuration of a correlation matrix learning device for performing a correlation matrix learning method according to the present embodiment of the invention. The correlation matrix learning device is provided with: an original codeword input unit  11  for inputting an original M-bit codeword Y; an encoder  12  of an encoding rate (N, M) for performing block encoding on the original M-bit codeword Y input into the original codeword input unit  11  to obtain an N-bit codeword X; a codeword input unit  13  for inputting the N-bit codeword X coded by the encoder  12 ; a storage  14  for storing a correlation matrix W having N rows and M columns; an arithmetic unit  15  for multiplying the codeword X input into the codeword input unit  13  by the correlation matrix W with N rows and M columns stored in the storage  14 , and outputting results y for M columns; a threshold updating unit  16  for changing M number of thresholds TH corresponding to the respective bits of the original codewords Y based on threshold update signals described later; a comparison unit  17  having M number of comparators for comparing the calculation results y for M columns output from the arithmetic unit  15  with the respective M number of thresholds TH set by the threshold updating unit  16 ; and a learning state monitor  18  for monitoring the comparison results output from the comparators  171 - 17 M of the comparison unit  17 , judging the learning convergence state based on the comparison results, outputting threshold update signals to the threshold updating unit  16  based on the judgment results, and determining an update value ΔW for the correlation matrix W based on the same comparison results from the comparison unit  17  to update the correlation matrix W stored in the storage  14 . 
   Hereinafter, operation by the correlation matrix learning device shown in  FIG. 1  will be described with reference to  FIG. 2 . 
   In the initial state, an arbitrary matrix with N rows and M columns is stored as a pre-learned correlation matrix W in the storage  14 . Moreover, in the initial state, a threshold TH and an update value ΔW are set to TH 0  and ΔW 0 , respectively, in the learning state monitor  18 . 
   According to the results of the learning operation described below, the threshold TH is successively updated as TH 0 □TH 1 □TH 2 □TH 3 □ . . . , increasing at a predetermined rate (e.g., incrementally or at a constant rate). Here, TH 0 &lt;TH 1 &lt;TH 2 &lt;TH 3 &lt; . . . . The update value ΔW is also successively updated according to the results of the learning operation, as ΔW 0 □ΔW 1 □ΔW 2 □ΔW 3 □ . . . at a predetermined rate to converge to zero. Here, TH 0 &gt;ΔW 0 &gt;ΔW 1 &gt;ΔW 2 &gt;ΔW 3 &gt; . . . &gt;0. Hereinafter, the threshold TH and the update value ΔW are represented by general expressions TH j  (j=0, 1, 2, . . . ) and ΔW k  (k=0, 1, 2, . . . ), respectively. 
   First, a first original M-bit codeword Y is input into the original codeword input unit  11 . Then, the encoder  12  performs block encoding on the original codeword Y at an encoding rate (N, M), and inputs the encoded N-bit codeword X into the codeword input unit  13 . Here, the bits of the original codeword are represented as Y m  (m=1, 2, . . . , M−1, M) and bits of the coded codeword X are represented as X n  (n=1, 2, . . . , N−1, N). 
   Once the coded codeword X is input into the codeword input unit  13 , the arithmetic unit  15  multiplies the row vectors indicating the codeword X by the correlation matrix W to obtain calculation results for M elements, y 1 , y 2 , . . . , y m , . . . , y M−1 , y M . The obtained calculation results for M columns are output to the respective comparators  171 - 17 M of the comparison unit  17  (Step S 201 ). 
   On the other hand, once the original codeword Y is input into the original codeword input unit  11 , the threshold updating unit  16  sets thresholds TH for the respective bits of the original codeword Y based on the threshold update signals from a threshold controller  181  of the learning state monitor  18 . In the initial state, a threshold update signal indicating the initial state is input into the threshold updating unit  16  from the learning state monitor  18 , and thus the value of the threshold TH j  (absolute value) is “TH 0 ”. The threshold updating unit  16  sets “+TH j  ” and “−TH j ” for bits “1” and “0”, respectively. 
   By receiving the calculation results y for M columns from the arithmetic unit  15 , the comparators  171 - 17 M of the comparison unit  17  compare the calculation results with the corresponding thresholds TH j , respectively (Step S 202 ). Then, the comparison unit  17  notifies the learning state monitor  18  of the results of comparison as well as the calculation results y. 
   The learning state monitor  18  stores the calculation results y notified by the comparison unit  17 . The learning state monitor  18  also receives the results of comparison from the comparison unit  17 , and judges that update of the correlation matrix W using the update value ΔW k  is unnecessary if |y m |≧TH j  or that update of the correlation matrix W using the update value ΔW k  is necessary if |y m |&lt;TH j  (Step S 203 ). In other words, where bit Y m  of the original codeword Y is “1”, the correlation matrix W m  (‘m’th column of the correlation matrix W) is not updated if the result y m  of the calculation is “+TH j ” or higher, and updated if the result y m  of the calculation is lower than “+TH j ”. Where bit Y m  of the original codeword Y is “0”, the correlation matrix W m  is not updated if the result y m  of the calculation is “−TH j ” or lower, and updated if the result y m  of the calculation is higher than “−TH j ”. Thus, no update takes place when y m  falls within the shaded range shown in  FIG. 3 , otherwise, update takes place. 
   When the original codeword Y m  is “1”, update of the correlation matrix W m  takes place by adding or subtracting “ΔW k ” to or from each element of W m  according to the sign (i.e., ±) of the codeword X n . On the other hand, when the original codeword Y m  is “0”, update of the correlation matrix W m  takes place by adding or subtracting “−ΔW k ” to or from each element of W m  according to the sign (i.e., ±) of the codeword X n . 
   Specifically, where the elements of W m  is W N,m , W N−1,m , . . . , W 1,m , each element is updated as follows. 
   When Y m  is “1”, 
   
     
       
         
           
             
               
                 
                   W 
                   
                     N 
                     , 
                     m 
                   
                 
                 = 
                 
                   
                     W 
                     
                       N 
                       , 
                       m 
                     
                   
                   + 
                   
                     
                       
                         Sgn 
                         ⁡ 
                         
                           ( 
                           
                             X 
                             n 
                           
                           ) 
                         
                       
                       · 
                       Δ 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       W 
                       k 
                     
                   
                 
               
             
           
           
             
               
                 
                   W 
                   
                     
                       N 
                       - 
                       1 
                     
                     , 
                     m 
                   
                 
                 = 
                 
                   
                     W 
                     
                       
                         N 
                         - 
                         1 
                       
                       , 
                       m 
                     
                   
                   + 
                   
                     
                       
                         Sgn 
                         ⁡ 
                         
                           ( 
                           
                             X 
                             
                               n 
                               - 
                               1 
                             
                           
                           ) 
                         
                       
                       · 
                       Δ 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       W 
                       k 
                     
                   
                 
               
             
           
           
             
               ⋮ 
             
           
           
             
               
                 
                   W 
                   
                     1 
                     , 
                     m 
                   
                 
                 = 
                 
                   
                     W 
                     
                       1 
                       , 
                       m 
                     
                   
                   + 
                   
                     
                       
                         Sgn 
                         ⁡ 
                         
                           ( 
                           
                             X 
                             1 
                           
                           ) 
                         
                       
                       · 
                       Δ 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       W 
                       k 
                     
                   
                 
               
             
           
         
       
     
   
   When Y m  is “0”, 
   
     
       
         
           
             
               
                 
                   W 
                   
                     N 
                     , 
                     m 
                   
                 
                 = 
                 
                   
                     W 
                     
                       N 
                       , 
                       m 
                     
                   
                   - 
                   
                     
                       
                         Sgn 
                         ⁡ 
                         
                           ( 
                           
                             X 
                             n 
                           
                           ) 
                         
                       
                       · 
                       Δ 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       W 
                       k 
                     
                   
                 
               
             
           
           
             
               
                 
                   W 
                   
                     
                       N 
                       - 
                       1 
                     
                     , 
                     m 
                   
                 
                 = 
                 
                   
                     W 
                     
                       
                         N 
                         - 
                         1 
                       
                       , 
                       m 
                     
                   
                   - 
                   
                     
                       
                         Sgn 
                         ⁡ 
                         
                           ( 
                           
                             X 
                             
                               n 
                               - 
                               1 
                             
                           
                           ) 
                         
                       
                       · 
                       Δ 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       W 
                       k 
                     
                   
                 
               
             
           
           
             
               ⋮ 
             
           
           
             
               
                 
                   W 
                   
                     1 
                     , 
                     m 
                   
                 
                 = 
                 
                   
                     W 
                     
                       1 
                       , 
                       m 
                     
                   
                   - 
                   
                     
                       
                         Sgn 
                         ⁡ 
                         
                           ( 
                           
                             X 
                             1 
                           
                           ) 
                         
                       
                       · 
                       Δ 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       W 
                       k 
                     
                   
                 
               
             
           
         
       
     
   
   In the above equations, Sgn(X n ) represents the sign ± of X n . However, when X n  is 0, X n  is replaced by “−1” in the calculation. The state of this update can be illustrated as shown in  FIGS. 4A and 4B . 
   Once the correlation matrix W is updated, the arithmetic unit  15  multiplies the updated correlation matrix W (i.e., the post-learned correlation matrix W) by the codeword X and outputs the calculation results y again. Where the elements of the products of the above-mentioned pre-learned correlation matrix W and the codeword X are represented as [y m ] t , the present calculation results are represented as [y m ] t+1 . The comparison unit  17  compares the obtained current calculation results y with the thresholds TH j  and notifies the learning state monitor  18  of the comparison results as well as the calculation results y. 
   In this manner, a first run of learning operation is completed for the first codeword X (Step S 204 ). 
   Next, the learning state monitor  18  judges whether the learning operation has taken place for all of the codewords X (Step S 205 ). Here, since the learning operation for only the first codeword X has just completed, the operation returns to Step S 201  and the above-described operation is repeated for the second codeword X. Thereafter, the above-described operation of Steps S 201  through S 205  are repeated for the rest of the codewords X. 
   After the learning operation has taken place for all of the codewords X, the learning state monitor  18  judges whether |y m |≧TH j  applies to all of the codewords X based on the comparison results sent from the comparison unit  17  (Step S 206 ). In other words, the learning state monitor  18  judges, for all of the codewords X, whether or not the correlation matrix needs further update operation. 
   When |y m |≧TH j  applies to all of the codewords X, learning operation for the correlation matrix using the update value ΔW k  is converged for the threshold TH j  (Step S 207 ). The threshold is updated from TH j  to TH j+1 , the update value ΔW k  is reset to the initial value ΔW 0  (Step S 208 ), and the operation returns to Step S 201 . 
   Thereafter, the correlation matrix learning device uses the new threshold TH j+1  to execute Steps S 201  through S 204  for all of the codewords X again. Steps S 201  through S 206  are repeatedly executed while updating the threshold (via Steps S 207  and S 208 ) until |y m |≧TH j  no longer applies to any of the codewords in Step S 206 . 
   When |y m |≧TH j  no longer applies to any of the codewords X in Step S 206 , the learning state monitor  18  judges whether or not the present calculation result [y m ] t+1 is the same as the previous calculation result [y m ] t for all of the codewords respectively (Step S 209 ). When the calculation result [y m ] t+1 output from the arithmetic unit  15  does not match the previous calculation result [y m ] t, the operation returns to Step S 201  to execute the above-described operation for all of the codewords X. 
   When [y m ] t+1 equals [y m ] t in Step S 209 , the learning operation using the update value ΔW k  is considered to be saturated (Step S 210 ) and the learning state monitor  18  updates the update value from ΔW k  to ΔW k+1  (Step S 211 ). Then, the learning state monitor  18  judges whether or not the new update value ΔW k+1  equals 0 (or equals substantially 0) (Step S 212 ). If the new update value ΔW k+1  is not 0, then the operation returns to Step S 201  to execute the above-described operation for all of the codewords X again. 
   When the new update value ΔW k+1  is judged to be 0 in Step S 212 , the learning operation is completed (Step S 213 ), and the threshold TH j  at this point is the optimal value for all of the codewords and the resulting correlation matrix is the optimal correlation matrix for each codeword (Step S 214 ). 
   In the correlation matrix learning device according to the present embodiment, when the calculation results y output from the arithmetic unit  15  after the learning operation fall within the shaded region shown in  FIG. 3  with respect to the threshold TH j , the learning operation with the threshold TH j  is judged to be converged, whereby the threshold is changed (increased) to TH j+1  to repeat the learning operation. 
   On the other hand, when the calculation results y output from the arithmetic unit  15  after the learning operation do not fall within the shaded region shown in  FIG. 3  while the values of the calculation results y equal the values resulting from the previous calculation, the learning state using the present update value ΔW k  is judged to have reached the saturation state and thus the update value is changed (decreased) from ΔW k  to ΔW k+1  to repeat the learning operation. 
   Accordingly, the correlation matrix learning device according to the present embodiment provides an optimal threshold TH j  for all of the multiple codewords X as well as an optimal correlation matrix W used for obtaining the original codeword Y from all of the codewords X. 
   According to the above-described embodiment, a special purpose computer specified in the learning operation has been illustrated. However, the above-described operation of the present invention can be realized as a program to be executed on a general computer. 
   In a method for learning a correlation matrix according to the present invention, the results of the calculation of a codeword and the pre-learned correlation matrix are compared to thresholds, based on which the pre-learned correlation matrix is updated to obtain a post-learned correlation matrix, wherein learning operation for the correlation matrix is repeated while the threshold (absolute value) is stepwisely increased as the learning operation proceeds. As a result, a threshold as well as a correlation matrix that are optimal for all of the multiple codewords can readily and rapidly be obtained. 
   The invention may be embodied in other specific forms without departing from the spirit or essential characteristic thereof. The present embodiments are therefore to be considered in all respects as illustrative and not restrictive, the scope of the invention being indicated by the appended claims rather than by the foregoing description and all changes which come within the meaning and rage of equivalency of the claims are therefore intended to be embraced therein. 
   The entire disclosure of Japanese Patent Application No. 2001-119614 (Filed on Apr. 18, 2001) including specification, claims, drawings and summary are incorporated herein by reference in its entirety.