Abstract:
A method and apparatus for block interleaving that eliminates the step of intermediary buffering. The method includes: (a) calculating a memory address at which first output data, of which number is equal to the number of rows of a first encoder is stored, (b) storing the first output data at the calculated memory address of a circular buffer, (c) storing second output data at an address which is incremented by a specific constant value from the calculated memory address of the circular buffer, and (d) storing (n+1) th  output data at an address which is incremented by n from the calculated memory address of the circular buffer.

Description:
CLAIM OF PRIORITY 
       [0001]    This application claims the benefit under 35 U.S.C. § 119(a) from a Korean patent application filed in the Korean Intellectual Property Office on Sep. 20, 2007 and assigned Serial No. 2007-95628, the entire disclosure of which is hereby incorporated by reference in its entirety. 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to techniques for improving/reducing the buffering occurring in a block interleaving system. More particularly, the present invention relates to an apparatus and method for block interleaving in a Long Term Evolution (LTE) communication system. 
         [0004]    2. Description of the Related Art 
         [0005]    Block interleaving is a technique of data transmission whereby data sequences are changed into a specific pattern (as opposed to continuous transmission of the data sequences), in order to reduce occurrence of burst errors (i.e., continuously generated errors). 
         [0006]      FIG. 1  is a block diagram illustrating a structure of a conventional sub-block interleaving method. 
         [0007]    Referring now to  FIG. 1 , in the conventional method, before a read-address controller  130  interleaves outputs of a turbo encoder  110 , the encoder output values are stored in a plurality of buffers  120 ,  125 , and  127 . 
         [0008]    The read-address controller  130  functions to interleave outputs of the plurality of buffers  120 ,  125 , and  127  and then stores the interleaved outputs in circular buffers  140  and  145 . 
         [0009]    When using the conventional method as shown in  FIG. 1 , there are disadvantages in that the buffers  120 ,  125 , and  127  are required to store the encoder output values. 
         [0010]    In addition, since the encoder output values are stored in the buffers  120 ,  125 , and  127  and then interleaving is performed according to the read address controller, there is an additional problem of a increased time delay. 
       SUMMARY OF THE INVENTION 
       [0011]    Accordingly, an exemplary aspect of the present invention is to provide an apparatus and method for block interleaving in a mobile communication system. 
         [0012]    Another exemplary aspect of the present invention is to provide an apparatus and method for performing block interleaving without an intermediary buffer in a mobile communication system. 
         [0013]    Another exemplary aspect of the present invention is to provide an apparatus and method for performing block interleaving without the inherent delay resulting from the use of an intermediary buffer in a mobile communication system. 
         [0014]    In accordance with an exemplary embodiment of the present invention, a method for block interleaving includes: (a) calculating a memory address at which first output data, of which number is equal to the number of rows of a first encoder, is stored; (b) storing the first output data at the calculated memory address of a circular buffer; (c) storing second output data at an address which is incremented by a specific constant value from the calculated memory address of the circular buffer; and (d) storing (n+1) th  output data at an address which is incremented by n from the calculated memory address of the circular buffer. 
         [0015]    In accordance with another exemplary embodiment of the present invention, an apparatus for block interleaving includes: an address controller for calculating a memory address at which first output data, of which number is equal to the number of rows of a first encoder is stored, for storing the first output data at the calculated memory address of a circular buffer, and for storing second output data at an address which is incremented by a specific constant value from the calculated memory address of the circular buffer, and for storing (n+1) th  output data at an address which is incremented by n from the calculated memory address of the circular buffer. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0016]    The above and other exemplary aspects, features and advantages of certain exemplary embodiments of the present invention will be more apparent from the following detailed description taken in conjunction with the accompanying drawings, in which: 
           [0017]      FIG. 1  is a block diagram illustrating a structure of a conventional sub-block interleaving method; 
           [0018]      FIG. 2  is a flowchart illustrating a process of creating a table considering pruning according to an exemplary embodiment of the present invention; 
           [0019]      FIG. 3  is a flowchart illustrating a process of operating sub-block interleaving according to an exemplary embodiment of the present invention; and 
           [0020]      FIG. 4  is a block diagram for sub-block interleaving according to an exemplary embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0021]    Exemplary embodiments of the present invention will be described below with reference to the accompanying drawings. For the purposes of clarity and simplicity, well-known functions or constructions may not be described in detail as they would obscure appreciation of the present invention by a person of ordinary skill in the art with unnecessary detail. 
         [0022]    Hereinafter, an apparatus and method for block interleaving in a mobile communication system will be described in conjunction with  FIGS. 2 ,  3  and  4 . In a brief overview, it will be assumed that a 32-bit column is used for interleaving in the present invention. 
         [0023]    According to one exemplary aspect of the present invention, among all inputs, only an address of first unit data (i.e., values filled in a first row of a block interleaver) output from an encoder is calculated and stored in a circular buffer. 
         [0024]    Second unit data is stored in the circular buffer according to an address which is incremented by +1 from the address of first unit data. That is, subsequent output addresses are recursively obtained. 
         [0025]    Accordingly, without having to perform complex calculations to obtain all address values, subsequent address values can be easily obtained after calculating the address of the first unit data to be stored in the circular buffer. 
         [0026]    The encoder of the present invention may comprise, for example, a turbo encoder  140 , an example of which is shown in  FIG. 4 . An output format of the turbo encoder is predetermined, and as a result, pruning is also determined. 
         [0027]    In case of 3rd Generation Partnership Project Long Time Evolution (3GPP LTE), if a column length of the output format is 32 bits, four types of pruning are determined. The four types of pruning are created and stored in the format of a table according to the procedure to be described below. Values to be used are loaded from the table. 
         [0028]    Now referring to  FIG. 2 , which is a flowchart illustrating a process of creating a table considering pruning according to an exemplary embodiment of the present invention, inputs of the process are input numbers from 0 to 31 included in unit data. N denotes a pruning number (indicating any one of four types of pruning). In addition, an output of the process is the number of shifts. 
         [0029]    First, at step  210 , it is determined whether an input value is 0. 
         [0030]    If the input value is 0, then at step  212 , an output value is determined to 0, and the output value is returned in step  245 . 
         [0031]    Otherwise, if the input value is not 0, at step  215 , a local variable i is determined to 0. Thereafter, if a value of Bit Reverse Ordering (BRO) (i) is less than N in step  220 , the output value is incremented by 1 in step  225 . The BRO( ) denotes a 5-bit reverse ordering number depending on the input value. For example, since a hexadecimal format of 5 is ‘00101’, the result of BRO [5] is ‘10100’ (=20), that is, BRO [5]=20. 
         [0032]    If a value of BRO (output) is equal to the local variable i in step  230 , the output value in step  225  is returned in step  245 . 
         [0033]    Otherwise, if the value of BRO (output) is different from the location variable i in step  230 , the local variable i is incremented by 1, and step  220  and subsequent steps from the step of  220  are repeated. 
         [0034]    The above procedure is repeated with respect to all input numbers from 0 to 31. 
         [0035]    A process that considers pruning is performed using the output values as shift values. After ending the procedure of  FIG. 2 , an address value to be stored in the circular buffer is calculated. The address value is for first unit data to be interleaved and stored. The address value is calculated according to Equation (1) below. 
         [0000]        Addr[i]= BRO[ i %32 ]*N _row−Pruning[ i %32]  Equation (1) 
         [0036]    In Equation (1), i denotes an input ordering number. Addr[i] denotes an address to be stored. BRO[ ] denotes a 5-bit reverse ordering number depending on the input value. For example, since a hexadecimal format of 5 is ‘00101’, the result of BRO[5] is ‘10100’ (=20), that is, BRO[5]=20. Pruning[ ] is a value obtained by calculating a pruning number in a storage region according to an input address. N_row represents ceil(N/32), and is a value obtained by dividing an input size by a unit data number (i.e., 32). 
         [0037]    When an address of the first unit data is generated, respective encoder outputs in subsequent unit data are generated by adding +1 to previously calculated 32 address values. All encoder outputs are thus processed in this manner, and sub-block interleaved data is stored in the circular buffer. 
         [0038]    If it is assumed that outputs of the turbo encoder are generated by receiving them when the address of the first unit data is generated, then the following three address types can be required. The three address types can be obtained according to Equation (2) below. 
         [0039]    for outputs of a systematic node, 
         [0000]        Addr[i ]=BRO[ i %32 ]*N _row−Pruning[ i %32]  Equation (2) 
         [0040]    For the outputs of systematic node, Equation (2) is identical to the Equation (1). 
         [0041]    In Equation (2), i denotes an output ordering number. Addr[i] denotes an address to be stored. BRO[ ] denotes a 5-bit reverse ordering number depending on the input value. For example, since a hexadecimal format of 5 is ‘00101’, the result of BRO[5] is ‘10100’ (=20), that is, BRO[5]=20. Pruning[ ] is a value obtained by calculating a pruning number in a storage region according to an input address. N_row represents ceil(N/32), and is a value obtained by dividing an input size by a unit data number (i.e., 32). 
         [0042]    for outputs of a parity 1 node, 
         [0000]        Addr[i]= 2*(BRO[ i %32] *N _row)−Pruning[ i %32] 
         [0043]    Herein, i denotes an input ordering number. Addr[i] denotes an address to be stored. BRO[ ] denotes a 5-bit reverse ordering number depending on the input value. For example, since a hexadecimal format of 5 is ‘00101’, the result of BRO[5] is ‘10100’ (=20), that is, BRO[5]=20. Pruning[ ] is a value obtained by calculating a pruning number in a storage region according to an input address. N_row represents ceil(N/32), and is a value obtained by dividing an input size by a unit data number (i.e., 32). 
         [0044]    For outputs of a parity 2 node, 
         [0000]        Addr[i]= 2*(BRO[ i %32 ]*N _row)−Pruning[ i %32] 
         [0045]    Herein, i denotes an input ordering number. Addr[i] denotes an address to be stored. BRO[ ] denotes a 5-bit reverse ordering number depending on the input value. For example, since a hexadecimal format of 5 is ‘00101’, the result of BRO[5] is ‘10100’ (=20), that is, BRO[5]=20. Pruning[ ] is a value obtained by calculating a pruning number in a storage region according to an input address. N_row represents ceil(N/32), and is a value obtained by dividing an input size by a unit data number (i.e., 32). 
         [0046]    An (n+1) address for an output of each of the parity 1 node and the parity 2 node is obtained by adding 2 to the calculated addressed stored in the storage buffer. 
         [0047]    According to the address calculated according to the first unit data, an output of the turbo encoder is stored in the circular buffer. 
         [0048]    Subsequent unit data is stored in the circular buffer according to addresses which are incremented by +1 or +2 from 32 first addresses. That is, subsequent output addresses are recursively obtained. 
         [0049]      FIG. 3  is a flowchart illustrating a process of operating sub-block interleaving according to an exemplary embodiment of the present invention. 
         [0050]    Referring now to  FIG. 3 , a table is created according to the procedure of  FIG. 2  by considering a unit data number and pruning (step  310 ). This step is performed only one time. 
         [0051]    By using an address value calculated using Equation (2) above, an output of a turbo encoder is stored in a circular buffer (step  320 ). In this particular case, 32 address values are first calculated. 
         [0052]    By using an address value which is incremented by +1 from the address value obtained in step  320 , the output of the turbo encoder is stored in the circular buffer in step  330  (referred to as a first process). The first process is repeated until outputting of the turbo encoder is finished (step  340 ). 
         [0053]      FIG. 4  is a block diagram for sub-block interleaving according to an exemplary embodiment of the present invention. 
         [0054]    Referring now to  FIG. 4 , values output from a Systematic (S) node, a Parity 1 (P1) node, and a Parity 2 (P2) node of a turbo encoder  410  are block-interleaved by an address controller  420 , and then are stored in circular buffers  440  and  445 . 
         [0055]    According to this particularly exemplary embodiment in  FIG. 4 , a value output from the S node of the turbo encoder  410  is stored in the circular buffer  440 . Values output from the P1 and P2 nodes of the turbo encoder  410  are alternately stored in the circular buffer  450 . An address, at which the output value of the P1 node is stored, is obtained by multiplying 2 by an address at which the output value of the S node. An address, at which the output value of the P2 node is stored, is obtained by adding 1 to an address at which the output value of the P1 node is stored. 
         [0056]    The address controller  420  calculates 32 address values of first unit data (i.e., values output from the turbo encoder and filled in a first row of a block interleaver) by using a table considering pruning. The address values are incremented by +1 to obtain subsequent address values. The obtained address values are stored in the circular buffers  440  and  445 . 
         [0057]    According to exemplary embodiments of the present invention, a hardware structure can be simplified by eliminating an intermediary buffer. In addition, a time delay can be reduced by omitting operations that require the use of the intermediary buffer. 
         [0058]    While the present invention has been shown and described with reference to certain exemplary embodiments thereof in the description, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the appended claims.