Abstract:
An apparatus for random parity check and correction with BCH code is provided, including a Bose-Chaudhuri-Hocquenghem (BCH) parity check code encoder, a channel, a BCH parity check code decoder, and a static random access memory (SRAM). The BCH parity check code encoder uses the BCH encoding to encode the parity check code in writing to flash memory. The channel is connected to the BCH parity check code encoder to compute the parity check code and the message polynomial into receiving data. The BCH parity check code decoder is connected to the channel for inputting the receiving data and using BCH decoding to compute the eigen value and error address. The SRAM is connected to the BCH parity check code decoder so as to read error address from static RAM, correct the data and restores the corrected data to the SRAM. Therefore, this achieves the object of random parity check and correction with BCH code.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to an apparatus for random parity check and correction with BCH code and, more particularly, to an apparatus applicable to flash data writing and capable of BCH encoding and decoding, and random parity checking and correction with BCH code. 
     2. The Related Arts 
     Flash memory is widely used in many digital equipments, such as, flash drives, and MP3 players. However, during the writing to the flash memory, it is necessary to perform the parity checking and correction on the codes written to the flash memory to ensure the correctness of the data. 
     The conventional parity check and correction of the flash memory data access uses the byte-based Reed-Solomon code. The encoder and the decoder of the Reed-Solomon code is more complicated. For example, the encoder includes a parity check unit b(x), generator polynomial g(x), encoding vector v(x), and message u(x), and the relations among them are: 
     
       
         
           
             
               g 
               ⁡ 
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               1 
               + 
               
                 
                   g 
                   1 
                 
                 ⁢ 
                 x 
               
               + 
               
                 
                   g 
                   2 
                 
                 ⁢ 
                 
                   x 
                   2 
                 
               
               + 
               
                 
                   g 
                   3 
                 
                 ⁢ 
                 
                   x 
                   3 
                 
               
               + 
               
                 … 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   g 
                   
                     n 
                     - 
                     k 
                     - 
                     1 
                   
                 
                 ⁢ 
                 
                   x 
                   
                     n 
                     - 
                     k 
                     - 
                     1 
                   
                 
               
               + 
               
                 x 
                 
                   n 
                   - 
                   k 
                 
               
             
           
         
       
       
         
           
             
               v 
               ⁡ 
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               
                 u 
                 ⁡ 
                 
                   ( 
                   x 
                   ) 
                 
               
               * 
               
                 g 
                 ⁡ 
                 
                   ( 
                   x 
                   ) 
                 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     v 
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                     
                   ⁢ 
                   
                     
                       b 
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                     + 
                     
                       
                         x 
                         
                           n 
                           - 
                           k 
                         
                       
                       ⁢ 
                       
                         u 
                         ⁡ 
                         
                           ( 
                           x 
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       b 
                       0 
                     
                     + 
                     
                       
                         b 
                         1 
                       
                       ⁢ 
                       x 
                     
                     + 
                     
                       … 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         b 
                         
                           n 
                           - 
                           k 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         x 
                         
                           n 
                           - 
                           k 
                           - 
                           1 
                         
                       
                     
                     + 
                     
                       
                         u 
                         0 
                       
                       ⁢ 
                       
                         x 
                         
                           n 
                           - 
                           k 
                         
                       
                     
                     + 
                     
                       
                         u 
                         1 
                       
                       ⁢ 
                       
                         x 
                         
                           n 
                           - 
                           k 
                           - 
                           1 
                         
                       
                     
                     + 
                     … 
                     + 
                   
                 
               
             
             
               
                 
                     
                   ⁢ 
                   
                     
                       u 
                       
                         k 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         1 
                       
                     
                     ⁢ 
                     
                       x 
                       
                         n 
                         - 
                         1 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     [ 
                     
                       
                         b 
                         0 
                       
                       , 
                       
                         b 
                         1 
                       
                       , 
                       
                         … 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           b 
                           
                             n 
                             - 
                             k 
                             - 
                             1 
                           
                         
                       
                       , 
                       
                         u 
                         0 
                       
                       , 
                       
                         u 
                         1 
                       
                       , 
                       
                         … 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           u 
                           
                             k 
                             - 
                             1 
                           
                         
                       
                     
                     ] 
                   
                 
               
             
           
         
       
     
     The above polynomial relation ids disclosed as in  FIG. 1  of a conventional parity check encoder circuit. The parity check computation units b 0 -b n-k-1  are added, and the generator polynomial units g 0 -g n-k-1  are multiplied. The conventional parity check encoder circuit requires 4096 cycles to shift to the last stage of parity check unit b n-k-1 . The problem of long computation time is a major drawback of error parity checking and correction. 
     In addition, the conventional parity check encoder circuit uses Reed-Solomon code for computing the eigen value, error address polynomial, and error address, which requires a longer computing time. Also, the conventional parity check encoder circuit requires at least fourteen 13-bit multipliers and twelve 13-bit adders to accomplish the computation. The circuit is more complex and the manufacturing cost is high. 
     Taiwan Patent No. 1226758 disclosed an apparatus and method for encoding interleaved periodic code, which is a typical Reed-Solomon code parity check and correction. That is, the disclosed patent also has the drawbacks of long computing time and high hardware cost. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to provide an apparatus for random parity check and correction with Bose-Chaudhuri-Hocquenghem (BCH) code, including the use of BCH encoder for parity check to reduce the computing time and the stages of computing. 
     Another object of the present invention is to provide an apparatus for random parity check and correction with BCH code, including the use of a BCH decoder to decode the parity check code to reduce the hardware design complexity and cost. 
     To achieve the above objects, the present invention provides an apparatus for random parity check and correction with BCH code, including a BCH parity check code encoder, a channel, a BCH parity check code decoder, and a static random access memory (SRAM). The BCH parity check code encoder uses the BCH encoding to encode the parity check code in writing to flash memory. The channel is connected to the BCH parity check code encoder to compute the parity check code and the message polynomial into receiving data. The BCH parity check code decoder is connected to the channel for inputting the receiving data and using BCH decoding to compute the eigen value and error address. The SRAM is connected to the BCH parity check code decoder so as to read error address from static RAM, correct the data and restores the corrected data to the SRAM. Therefore, this achieves the object of random parity check and correction with BCH code. 
     These and other objects, features, and advantages of the invention will be apparent to those skilled in the art, from a reading of the following brief description of the drawings, the detailed description of the preferred embodiment, and the appended claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The present invention can be understood in more detail by reading the subsequent detailed description in conjunction with the examples and references made to the accompanying drawings, wherein: 
         FIG. 1  shows a block diagram of a conventional parity check encoder; 
         FIG. 2  shows a block diagram of an apparatus of the present invention; 
         FIG. 3  shows a detailed block diagram of BCH parity check code decoder of the present invention; 
         FIG. 4  shows a simplified parity check code bit circuit; 
         FIG. 5  shows a flowchart of the decoding process of the present invention; and 
         FIG. 6  shows a flowchart of the error address detection and data correction process of the error address computing circuit and the SRAM of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       FIG. 2  shows an apparatus  100  for random parity check and correction with BCH code, including a BCH parity check code encoder  10 , a channel  20 , a BCH parity check code decoder  30  and a SRAM  40 . The BCH parity check code encoder  10  uses a BCH code to encode parity check code. The present invention uses BCH(8191, 8139) as an embodiment for description. Other BCH encoding methods are also within the scope of the present invention. 
     The signals of  FIG. 2  include a parity check bit b(x), BCH(8191,9139) generator polynomial g(x), receiving data r(x), and message u(x). 
     The BCH(8191,8139) generator polynomial g(x) is:
 
 g ( x )={1101,0101,0110,0001,1101,0101,1100,0010,0000,1100,0100,1010,0010,1}  (4-1)
 
where g(0)=1, . . . , g(51)=0, g(52)=1
 
     The 4096-bit data requires 4096 cycles to each the last stage of the conventional parity check code encoder circuit. That means 4096 cycles in encoding time when using the conventional parity check code encoder. The present invention simplifies the b(x) to reduce the encoding time. The BCH parity check code encoder  10  of the present invention simplifies the parity check bit b(x) after the 8 th  cycle to one cycle as following:
 
 b   x ( i )= b   x ( i− 8)+ g ( i− 7) k   0   +g ( i− 6) k   1   +g ( i− 5) k   2   +g ( i− 4) k   3   +g ( i− 3) k   4   +g ( i− 2) k   5   +g ( i− 1) k   6   +g ( i ) k   7   (4-2)
 
where i=1 to 51.
 
     The “+” is a modulo-2 addition, which can be realized with a plurality of XOR gates. Based on the above equations (4-1) and (4-2), a constant polynomial k(x) can be simplified as follows:
 
∵ k   0   =b   x (51)+ u (7), g (51)=0
 
∴ k   1   =b   x (50)+ g (51) k   0   +u (6)= b   x (50)+ u (6)  (4-3)
 
Similarly,
 
 k   2   =b   x (49)+ g (50) k   0   +u (5)
 
 k   3   =b   x (48)+ g (50) k   1   +u (4)
 
 k   4   =b   x (47)+ g (50) k   2   +u (3)
 
 k   5   =b   x (46)+ g (50) k   3   +u (2)
 
 k   6   =b   x (45)+ g (46) k   0   +g (50) k   4   +u (1)
 
 k   7   =b   x (44)+ g (46) k   1   +g (50) k   5   +u (0)  (4-4)
 
And, based on equations (4-1), (4-2), (4-3) and (4-4):
 
 b   x (7)= b   x (51)+ u (7)+ g (1) k   1   +g (3) k   3   +g (5) k   5   +g (7) k   7  
 
 b   x (6)= b   x (50)+ u (6)+ g (1) k   2   +g (3) k   4   +g (5) k   6  
 
 b   x (5)= b   x (49)+ g (50) k   0   +u (5)+ g (1) k   3   +g (3) k   5   +g (5) k   7  
 
 b   x (4)= b   x (48)+ g (50) k   1   +u (4)+ g (1) k   4   +g (3) k   6  
 
 b   x (3)= b   x (47)+ g (50) k   2   +u (3)+ g (1) k   5   +g (3) k   7  
 
 b   x (2)= b   x (46)+ g (50) k   3   +u (2)+ g (1) k   6  
 
 b   x (1)= b   x (45)+ g (46) k   0   +g (50) k   4   +u (1)+ g (1) k   7  
 
 b   x (0)= b   x (44)+ g (46) k   1   +g (50) k   5   +u (0)= k   7   (4-5)
 
Based on equations (4-3), (4-4), and (4-4), it is clear that the BCH parity check code encoder  10  of the present invention can be realized with a plurality of OXR gates, and encoding time is reduced from the original 4096 cycles to 512 cycles.
 
     The channel  20  is connected to the BCH parity check code encoder  10  to compute the 8-bit message u(x) and 52-bit parity check bits b(x) into a receiving data r(x). 
     Also referring to  FIG. 3 , the BCH parity check code decoder  10  includes a minimum polynomial processing circuit  31 , an eigen value computing circuit  32 , an error address polynomial computing circuit  33 , and an error address computing circuit  34 . The minimum polynomial processing circuit  31  is connected to the channel  20  for simplifying the parity check bits b(x) to reduce from 8 cycles to 1 cycle.
 
Eigen value  S=r·H   T   (5-1)
 
Receiving data r(x) can be expressed as:
 
 r ( x )= a   i ( x )φ i φ i ( x )+ b   i ( x )  (5-2)
 
When the minimum polynomial φ i =0, the following equation can be obtained:
 
 S=r (α i )= b (α i )= b   0   +b   1   α+ . . . b   n-1 α (n-1)   (5-3)
 
Based on above computation, the BCH(8191, 8139) decoding polynomial is:
 
Original polynomial:  P ( x )=1 +x+x   3   +x   4   (5-31)
 
     BCH decoded generator polynomial:
 
 g ( x )= LCM ((φ 1 ( x ),φ 3 ( x ),φ 5 ( x )φ 7 ( x ))  (5-4)
 
     The minimum polynomial:
 
φ 1 ( x )=1 +x+x   3   +x   4   +x   13  
 
φ 3 ( x )=1 +x   4   +x   5   +x   7   +x   9   +x   10   +x   13  
 
φ 5 ( x )=1 +x+x   4   +x   7   +x   8   +x   11   +x   13  
 
φ 7 ( x )=1 +x+x   2   +x   3   +x   6   +x   8   +x   9   +x   10   +x   13  
 
     The following description refers to  FIG. 4 . The minimum polynomial φ 1 (x)=1+x+x 3 +x 4 +x 13 =0 is used to simplify parity check bits b(x), where:
 
 b   12 (8)= b   4 (0)
 
 b   11 (8)= b   4 (1)= b   3 (0)+ b   12 (0)
 
 b   10 (8)= b   4 (2)= b   3 (1)+ b   12 (1)= b   2 (0)+ b   12 (0)+ b   11 (0)  (5-5)
 
Using the similar computation, the following can be obtained:
 
 b   9 (8)= b   4 (3)= b   1 (0)+ b   11 (0)+ b   10 (0)
 
 b   8 (8)= b   4 (4)= b   0 (0)+ b   12 (0)+ b   10 (0)+ b   9 (0)
 
 b   7 (8)= b   4 (5)= u (0)+ b   12 (0)+ b   11 (0)+ b   9 (0)+ b   8 (0)
 
 b   6 (8)= b   4 (6)= u (1)+ b   11 (0)+ b   10 (0)+ b   8 (0)+ b   7 (0)
 
 b   5 (8)= b   4 (4)= u (2)+ b   10 (0)+ b   9 (0)+ b   7 (0)+ b   6 (0)
 
 b   4 (8)= u (3)+ b   9 (0)+ b   8 (0)+ b   6 (0)+ b   5 (0)
 
 b   3 (8)= u (4)+ b   8 (0)+ b   7 (0)+ b   5 (0)
 
 b   2 (8)= u (5)+ b   7 (0)+ b   6 (0)
 
 b   0 (8)= u (6)+ b   6 (0)+ b   5 (0)
 
 b   0 (8)= u (7)+ b   5 (0)  (5-6)
 
Where message u(x) is the data read from flash memory, and the “+” in (5-5), (5-6) is “modulo-2 addition”. Similarly, when the minimum polynomial
 
φ 3 ( x )=1 +x   4   +x   5   +x   7   +x   9   +x   10   +x   13 =0
 
φ 5 ( x )=1 +x+x   4   +x   7   +x   8   +x   11   +x   13 =0
 
φ 7 ( x )=1 +x+x   2   +x   3   +x   6   +x   8   +x   9   +x   10   +x   13 =0
 
the circuit of parity check bits b(x) of  FIG. 4  can be found. The “+” between the parity check bits B 0 -B 12  is “modulo-2 addition”, and can be realized by XOR gates. Modulo-2 addition is performed on message u(x) and parity check bit unit B 0  to reduce the circuit from the original 8 cycles to 1 cycle.
 
     The eigen value computing circuit  32  is connected to the minimum polynomial processing circuit  31  to compute the following 8 eigen values:
 
 S   1   =r (α)= b (α)= b   0   +b   1   α+ . . . +b   12 α 12  
 
 S   2   =r (α 2 )= b (α 2 )= b   0   +b   1 α 2   + . . . +b   12 α 24  
 
 S   3   =r (α 3 )= b (α 3 )
 
 S   4   =r (α 4 )= b (α 4 )
 
 S   5   =r (α 5 )= b (α 5 )
 
 S   6   =r (α 6 )= b (α 6 )
 
 S   7   =r (α 7 )= b (α 7 )
 
 S   8   =r (α 8 )= b (α 8 )  (5-7)
 
The eigen values S1-S8 computed by the eigen value computing circuit  32  are used to determine the parity check. If all the eigen values S1-S8 are all zero, the data is correct, and the read of data can be continued. On the other hand, if the eigen values are not zero, the data is incorrect. The 512-bit eigen values S1-S8 can be obtained, and the correction capability is 4 bits.
 
     The error address polynomial computing circuit  33  is connected to the eigen value computing circuit  32  for computing the error address polynomial if the eigen values S1-S8 are not zero. The computing of error address polynomial is based on the inversionless Berlekamp-Massey algorithm, as follows:
 
(1 +S ) V ( k )=(1 +S   1   Z+ . . . +S   7   Z   7 )( v   0   +v   1   Z+ . . . v   4   Z )
 
 k= 0 →d   (1)   =v   0   S   1   +v   1  
 
 k= 1 →d   (3)   =v   0   S   3   +v   1   S   2   +v   2   S   1   +v   3  
 
 k= 2 →d   (5)   =v   0   S   5   +v   1   S   4   +v   2   S   3   +v   3   S   2   +v   4   S   1  
 
 k= 3 →d   (7)   =v   0   S   7   +v   1   S   6   +v   2   S   5   +v   3   S   4   +v   4   S   3  
 
k=4→finish  (5-12)
 
Based on (5-12), the error address polynomial computing circuit  33  includes a 13-bit adder and a 13-bit multiplier.
 
     The error address computing circuit  34  is connected to the error address polynomial computing circuit  33 . Based on equation (5-12), each bit is substituted in the following equation:
 
 v ( x )= v   0   +v   1   x+v   2   x   2   +v   3   x   3   +v   4   x   4   (5-13)
 
where x=α 1 . Therefore, the error address computing circuit  34  includes a 13-bit adder and a 13-bit multiplier, and the adder and the multiplier can compute at different time.
 
     The SRAM  40  is for storing address data with parity check error, and is connected to the error address computing circuit  34  of BCH parity check code decoder  30 . If the degree of encoding vector V(x) is equal to the degree of the error address polynomial of equation (5-12), the next task is to find the error address, and the data of the error address is read from the SRAM  40 , corrected by a plurality of inverters  41 , and written back to the SRAM  40 . Thus, the parity check and correction is accomplished. The correction capability is 4 bits, and the flash memory can read the next piece of data. On the other hand, if the degree of encoding vector V(x) is not equal to the degree of the error address polynomial of equation (5-12), an error has occurred, and correction is impossible. Hence, an error message is issued. 
       FIG. 5  shows the flowchart of the decoding process of the BCH parity check code decoder  30  of the present invention, including the following steps: 
     ( 200 ) Minimum polynomial computing on parity check bits, for the minimum polynomial processing circuit  31  to perform minimum polynomial simplification on parity check bits b(x); 
     ( 210 ) Computing eigen values, for the eigen value computing circuit  32  to compute the eigen values S1-S8 based on b(x) of step ( 200 ); 
     ( 220 ) Determining whether the eigen values of step ( 210 ) being all zero, if not, proceed to step  230 , otherwise, proceed to step  260 ; 
     ( 230 ) Searching for error address polynomial, for the error address polynomial computing circuit  33  to compute error address polynomial when S1-S8 are all non-zero, indicating an error in writing data; 
     ( 240 ) Searching for error address, for the error address computing circuit  34  to compute the error address based on the error address polynomial of step ( 230 ); 
     ( 250 ) Correcting error data, by reading error data from the SRAM, correcting error data, and storing corrected data back to the SRAM; and 
     ( 260 ) Finishing BCH parity check code decoding. 
       FIG. 6  shows the flowchart of the parity check error address and correction process of the error address computing circuit  34  of the BCH parity check code decoder  30  and the SRAM  40  of the present invention, including the following steps: 
     ( 300 ) Computing encoding vector V(x), for the error address computing circuit  34  to compute encoding vector V(x); 
     ( 310 ) Determining whether the degree of encoding vector being equal to the degree of error address polynomial, for the error address computing circuit  34  to determine whether the degree of encoding vector is equal to the degree of error address polynomial, if so, proceed to step ( 320 ), otherwise, proceed to step ( 340 ); 
     ( 320 ) Correctable error, the error address computing circuit  34  identifying as a correctable error; 
     ( 321 ) Reading data of error address from the SRAM, by reading data at error address computed by the error address computing circuit  34  from the SRAM  40 ; 
     ( 322 ) Corrected data from the SRAM, by correcting data from step ( 321 ) with the inverter  41 ; 
     ( 323 ) Storing corrected data to SRAM, by storing corrected data in step ( 322 ) to the SRAM  40 ; and accomplishing data parity check and correction; 
     ( 330 ) End; 
     ( 340 ) Non-correctable error, the error address computing circuit  34  identifying as a non-correctable error; and 
     ( 341 ) Issuing error message, for the error address computing circuit  34  to issue an error message and retuning to step ( 330 ). 
     The apparatus for random parity check and correction with BCH code of the present invention has the following advantages: 
     (1) The parity check code encoding time and eigen value computing time are reduced from 4148 cycles to 528 cycles; 
     (2) The BCH parity check code encoder  10  and the BCH parity check code decoder  30  are simplified in hardware design, and the cost is reduced; and 
     (3) The hardware circuit reaches 8-bit random parity check on 512-bit data and random 4-bit correction capability. 
     While the invention has been described in connection with what is presently considered to the most practical and preferred embodiment, it is to be understood that the invention is not to be limited to the disclosed embodiment, but on the contrary, is intended to cover various modifications and equivalent arrangement included within the spirit and scope of the appended claims.