Abstract:
A method, adapted to a 3GPP turbo coder, for interleaving a plurality of data of a data frame and a circuit thereof is provided. The present invention computes a value of Row Parameter according to the size of the data frame, computes an index for a table according to the value of Row Parameter, and searches for a value of Column Parameter, a value of Prime Parameter and a value of Primitive Parameter from the table.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]     This Application claims priority to Taiwan Patent Application No. 093110101 filed on Apr. 12, 2004.  
       FIELD OF INVENTION  
       [0002]     The present invention relates to a method for interleaving a plurality of data in a data frame and a circuit thereof. The method and the circuit are adapted for a turbo coder implemented to encode data under the regulation of 3rd generation partnership project (3GPP).  
       BACKGROUND OF THE INVENTION  
       [0003]     Turbo coding is frequently applied to modern communication systems because of low power and narrow bandwidth requirement. One characteristic of turbo coding is that there is an interleaver used to re-arrange the order of a plurality of data in a data frame prior to data transmission.  
         [0004]     Under the regulation of 3GPP, data are processed, or interleaved, by referring to four parameters: a row parameter, a column parameter, a prime parameter and a primitive parameter. The row and column parameters are configured to generate a new column address. The column, prime and primitive parameters are configured to generate a new row address. According to the new column and row addresses, the interleaver interleaves the data.  
         [0005]      FIG. 1  shows a block diagram of an interleaver implemented for 3GPP. The interleaver includes an interleaver parameter calculator  101 , a column address generator  103 , a row address generator  105  and an adder  107 . The interleaver parameter calculator  101  is configured to receive a datum  100 , and, according to the datum  100 , to calculate to output a row parameter  102 , a column parameter  104 , a prime parameter  106  and a primitive parameter  108 . The column address generator  103  is configured to receive the row parameter  102  and the column parameter  104  to generate a column address  110 . The row address generator  105  is configured to receive the column parameter  104 , the prime parameter  106  and the primitive parameter  108  to generate a row address  112 . The column address  110  and the row address  112 , after being calculated by the adder  107 , form an interleaving address  114 , which is used to interleave the datum  100 .  
         [0006]     The interleaver parameter calculator  101  of the prior art includes a table configured to store all available values of the four parameters  102 ,  104 ,  106  and  108 . Under the regulation of 3GPP, the row parameter  102 , the column parameter  104 , the prime parameter  106  and the primitive parameter  108  are respectively 5 bits, 9 bits, 9 bits and 5 bits, and the valid sizes of a data frame are in a range from 40 to 5114, which means that the table has 5075 rows. Therefore, the table of the interleaver parameter calculator  101  needs a total of (5+9+9+5)×5075=142100 bits. When the interleaver is implemented by means of VLSI technology, cost will stay high because the table occupies a large IC area.  
       SUMMARY OF THE INVENTION  
       [0007]     The present invention provides a method for a turbo coder to interleave a plurality of data in a data frame. The turbo coder, following 3GPP regulations, has a table particularly designed and is able to interleave the plurality of data according to a row parameter R, a column parameter C, a prime parameter P and a primitive parameter V.  
         [0008]     The method includes the steps of receiving and storing the data frame; calculating a value of the row parameter R according to a size K of the data frame; calculating a table index TI corresponding to the table according to the value of the row parameter R; looking up the table to obtain a value of the column parameter C, a value of the prime parameter P and a value of the primitive parameter V according to the table index TI; and interleaving the plurality of data according to the value of the row parameter R, the value of the column parameter C, the value of the prime parameter P and the value of the primitive parameter V.  
         [0009]     The step of looking up the table further includes: looking up the table according to the table index TI to obtain at least one possible value of the prime parameter P, at least one possible value of the primitive parameter V, at least one possible value of a column offset parameter CO, and at least one possible value of a check parameter CK; comparing a plurality of least significant bits LSB of the table index TI with at least one possible value of the check parameter CK to respectively select the appropriate values of the prime parameter P, the primitive parameter V, and the column offset parameter CO from the at least one possible value of the prime parameter P, the at least one possible value of the primitive parameter V and at least one possible value of a column offset parameter CO; and calculating the value of the column parameter C according to the value of the column offset parameter CO.  
         [0010]     The method, which can be implemented by a computer, reduces the layout size of the table so that cost is saved.  
         [0011]     The present invention further provides an interleaver parameter calculator adapted for the above-mentioned turbo coder. The interleaver parameter calculator includes a first circuit array, a second circuit array, a control circuit and a third circuit array. The first circuit array is configured to receive a datum D from the plurality of data and, according to a plurality of particular values, perform subtraction calculation to generate a plurality of first signals. The second circuit array is configured to receive the plurality of first signals and generate a plurality of second signals and third signals, wherein the second signals include information of the size of the data frame and the third signals include the information of the datum D. The control circuit is configured to receive the second signals and, according to the size of the data frame, generate a control signal and a value of the row parameter. The third circuit array is configured to receive the third signals and, according to the control signal, select a value of the column parameter, a value of prime parameter and a value of primitive parameter. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]      FIG. 1  illustrates an interleaver of the prior art;  
         [0013]      FIG. 2A  illustrates a table for R=5;  
         [0014]      FIG. 2B  illustrates a table for R=10;  
         [0015]     FIGS.  2 C-E illustrate a first sub-table for R=20;  
         [0016]     FIGS.  2 F-G illustrate a second sub-table for R=20;  
         [0017]      FIG. 2H  illustrates a third sub-table for R=20;  
         [0018]      FIG. 3  illustrates a flow chart of the present invention;  
         [0019]      FIG. 4  illustrates a flow chart when step  307  of the present invention is executed;  
         [0020]      FIG. 5  illustrates an interleaver parameter calculator in accordance with the present invention; and  
         [0021]      FIG. 6  illustrates the circuitry of the interleaver parameter calculator. 
     
    
     DETAILED DESCRIPTION  
       [0022]     The method of the present invention utilizes a set of equations in order to derive a value of the row parameter R, and re-builds the table according to the properties of the row parameter R, the column parameter C, the prime parameter P and the primitive parameter V under 3GPP regulations. The present invention further simplifies the table by introducing two additional parameters: a column offset parameter CO and a check parameter CK.  FIG. 2  (FIGS.  2 A-H) shows the simplified table. According to the regulations of 3GPP, the row parameter R includes three possible values: R=5, R=10 and R=20.  FIG. 2A  shows the table for R=5, including a first sub-table  201 , a second sub-table  203  and a third sub-table  205 .  FIG. 2B  shows the table for R=10, including a first sub-table  207 , a second sub-table  209  and a third sub-table  211 . FIGS.  2 C-E show a first sub-table for R=20. FIGS.  2 F-G show a second sub-table for R=20.  FIG. 2H  shows a third sub-table for R=20. It is noted that some rows are ignored in the second and third sub-tables for R=20 if the corresponding parameters are invalid.  
         [0023]     As  FIG. 2  shows, the tables or sub-tables applied to the present invention include four parameters: a check parameter CK, a prime parameter P, a primitive parameter V and a column offset parameter CO, wherein the check parameter CK is adapted to check which row of the tables is desired and the column offset parameter CO is adapted to derive the column parameter  104 . According to the tables, values of the row parameter  102 , the column parameter  104 , the prime parameter  106  and the primitive parameter  108  under 3GPP regulations can be derived.  
         [0024]     The method of the present invention is shown in  FIG. 3 . In step  301 , an interleaver receives and stores a data frame. More particularly, the interleaver receives and stores the data in the data frame in order. In step  303 , a value of the row parameter R is calculated according to a size K of the data frame. In step  305 , a table index TI corresponding to the table shown in  FIG. 2  is calculated according to the value of the row parameter R derived in step  303 . In step  307 , looking up the table, according to the table index TI derived in step  305 , is executed to obtain a value of the column parameter C, a value of the prime parameter P and a value of the primitive parameter V. In step  309 , the interleaver interleaves the plurality of data according to an interleaving address formed by the values of the row parameter R, the column parameter C, the prime parameter P and the primitive parameter V. More detailed descriptions of some steps are set forth below.  
         [0025]     In step  303 , the value of the row parameter R is derived by a first set of equations: 
 
if 40≦K≦159, R=5; 
 
if 160≦K≦200 or 481≦K≦530, R=10; and 
 
if K=otherwise, R=20. 
 
 i.e., the row parameter R has three possible values (5, 10 and 20) and is determined by the size K of the data frame. 
 
         [0026]     In step  305 , the value of the table index TI corresponding to the table is derived by a second set of equations:  
           when   ⁢           ⁢   R     =   5     ,       TI   =     [       K   -   40     8     ]       ;         
           when   ⁢           ⁢   R     =       10   ⁢           ⁢   and   ⁢           ⁢   160     ≤   K   ≤   200       ,       TI   =     [       K   -   160     16     ]       ;         
           when   ⁢           ⁢   R     =       10   ⁢           ⁢   and   ⁢           ⁢   481     ≤   K   ≤   530       ,       TI   =     [       K   -   481     16     ]       ;         
           when   ⁢           ⁢   R     =       20   ⁢           ⁢   and   ⁢           ⁢   201     ≤   K   ≤   481       ,       TI   =     [       K   -   210     32     ]       ;   and         
           when   ⁢           ⁢   R     =       20   ⁢           ⁢   and   ⁢           ⁢   530     ≤   K       ,     TI   =       [       K   -   531     32     ]     .           
 
 The value of the table index TI is associated with the row parameter R and the size K of the data frame. It is noted that the symbol [ ] denotes Gaussian calculation which takes the quotient and ignores the remainder. 
 
         [0027]     Step  307  further includes the steps shown in  FIG. 4 . Step  401  includes looking up the table according to the table index TI derived in step  305  to obtain at least one possible value of the prime parameter P, at least one possible value of the primitive parameter V, at least one possible value of the column offset parameter CO, and at least one possible value of the check parameter CK. In step  403 , a plurality of least significant bits LSB of the table index TI are compared with at least one possible value of the check parameter CK. The comparison ways are: when R=5, comparing three least significant bits LSB of the table index TI with at least one possible value of the check parameter CK; when R=10, comparing four least significant bits LSB of the table index TI with at least one possible value of the check parameter CK; and when R=20, comparing five least significant bits LSB of the table index TI with at least one possible value of the check parameter CK. The table index TI whose least significant bits are smaller than or equal to the value of the check parameter CK is the desired table index TI. Based on the desired table index TI, the values of the prime parameter P, the primitive parameter V, and the column offset parameter CO are respectively and appropriately selected from those possible values of the prime parameter P, the primitive parameter V and the column offset parameter CO. In step  405 , the value of the column parameter C is calculated according to the value of the column offset parameter CO and the prime parameter P. A third equation to derive the value of the column parameter C is: 
 
 C=CO+P  
 
         [0028]     The check parameter CK and the column offset parameter CO for the table of the present invention are both 5 bits at most, and the prime parameter P and the primitive parameter V under 3GPP regulations are respectively 9 bits and 5 bits. Therefore, the required bits for all four parameters are 24 bits. There are 30 valid rows of the table for R=5, 11 valid rows of the table for R=10 and 285 valid rows of the table for R=20. Accordingly, the required bits are 24*(30+11+285)=7824 in total. Its layout area is only 5.5% of that of the table of prior art (142100 bits). This layout area reduction saves a lot of cost.  
         [0029]     An example is described herein to expound the characteristics of the present invention. Assume that a data frame with K=71 is received in step  301 . In step  303 , the value of the row parameter R can be derived to be  5  according to the first set of equations. As  FIG. 2A  shows, the table for R=5 includes the first sub-table  201 , the second sub-table  203  and the third sub-table  205 . In step  305 , TI can be derived to be 3 according to the second set of equations  
         (     TI   =       [       71   -   40     8     ]     =   3       )     .       
 
 In step  401 , three possible rows (bold frames in the sub-tables  201 ,  203  and  205 ) whose TIs are equal to 3 are determined by looking up the table. Therefore, the possible values of CK, P, V and CO are: CK=1, P=13, V=2, CO=0 for the first sub-table  201 ; CK=6, P=13, V=2, CO=1 for the second sub-table  203 ; and CK=7, P=17, V=3, CO=−1 for the third sub-table  205 . Since R=5, three least significant bits LSB of the table index TI ((71−40) mod 2 3 =7) are compared with the three possible values of the check parameter CK in step  403 . One can observe that only the CK value of the sub-table  205  is not smaller than the three least significant bits LSB of the table index TI so the corresponding P, V and CO values (P=17, V=3 and CO=−1) are determined. In step  405 , C can be derived by using the third equation and the value is C=CO+P=−1+17=16. Accordingly, the parameters for interleaving data are R=5, C=16, P=17 and V=3. The interleaver then is able to interleave data based on these parameters in step  309 . 
 
         [0030]     The present invention further provides an interleaver parameter calculator for generating the above-mentioned parameters.  FIG. 5  shows an interleaver parameter calculator  5  that includes a first circuit array  501 , a second circuit array  503 , a control circuit  505  and a third circuit array  507 . The first circuit array  501  is configured to receive a datum  500  of a data frame and, according to a plurality of particular values associated with the first set of equations, to perform subtraction calculation to generate a plurality of first signals  502 . The second circuit array  503  is configured to receive the first signals  502  and to generate a plurality of second signals  504  and third signals  506 , wherein the second signals  504  include information of the size K of the data frame and the third signals  506  include the datum  500 . The control circuit  505  is configured to receive the second signals  504  and, according to the size K of the data frame, to generate a control signal  516  and a value of the row parameter  508 . The third circuit array  507  is configured to receive the third signals  506  and, according to the control signal  516 , to select a value of the column parameter  510 , a value of prime parameter  512  and a value of primitive parameter  514 . It is noted that each of the bold signal lines in  FIG. 5  represents that more than one signal is transmitted thereby.  
         [0031]      FIG. 6  shows an embodiment of the interleaver parameter calculator  5 . The first circuit array  501  includes five subtracters to respectively perform subtraction calculation according to one of five particular values, wherein the first value adapted for a first subtracter  615   a  is 40, the second value adapted for a second subtracter  615   b  is 160, the third value adapted for a third subtracter  615   c  is 201, the fourth value adapted for a fourth subtracter  615   d  is 481 and the fifth value adapted for a fifth subtracter  615   e  is 531. The second circuit array  503  receives signals  601   a - e  (i.e., the first signals  502  in  FIG. 5 ) and generates signals  603   a - e , signals  605   a - e  and signals  607   a - d . The signals  605   a - e  indicate the above-mentioned least significant bits LSB. The signals  603   a - e  indicate the signals  601   a - e  excluding the least significant bits LSB. The signals  607   a - d  indicate a positive value or a negative value after the datum  500  is subtracted by the first circuit array  501 . The signals  603   a - e  and the signals  605   a - e  together form the third signals  506  in  FIG. 5 . The signals  607   a - d  form the second signals  504  in  FIG. 5 .  
         [0032]     The third circuit array  507  of the interleaver parameter calculator  5  includes tables  609   a - c  which are identical to the tables shown in  FIG. 2  respectively for R=5, R=10 and R=20. The third circuit array  507  receives the signals  603   a - e  to obtain table indexes to look up the tables and, therefore, derives at least one possible value of the prime parameter P, at least one possible value of the primitive parameter V, at least one possible value of the columm offset parameter CO, and at least one possible value of the check parameter CK. The third circuit array  507  subsequently compares the signal  605   a - e  with at least one possible value of the check parameter CK, and, according to the control signal  516 , selects the value of the column offset parameter CO by a multiplexer  617 , the value  514  of the prime parameter P and the value  512  of the primitive parameter V as a row  611  shows. The value  510  of the column parameter C can be derived by adding the value of the column offset parameter CO and the value  514  of the prime parameter P by an adder  613 .  
         [0033]     The control circuit  505  can determine and output the value  508  of the row parameter R according to the signals  607   a - d . For example, if the signals  607   a - d  are all negative, it means the size K of the data frame being less than 160 and the control circuit  505  determines R=5.  
         [0034]     The above description of the preferred embodiments is expected to clearly expound the characteristics of the present invention but not expected to restrict the scope of the present invention. Those skilled in the art will readily observe that numerous modifications and alterations of the method and the interleaver parameter calculator may be made while retaining the teaching of the invention. Accordingly, the above disclosure should be construed as limited only by the bounds of the claims.