# Patent

## Title
Data rate matching method and apparatus for use in mobile communication systems

## Abstract

Disclosed are a data rate matching method and apparatus for use in mobile communication systems that can perform parallel interleaving at a high speed without a collision between encoded data input in parallel. A set of first parameters (f1) is calculated on the basis of a length (D) of encoded input data and a set of second parameters (f2) is calculated on the basis of a set of prime numbers constituting a value of the length (D) of the input data. Interleaving is performed on the basis of the set of first parameters (f1), the set of second parameters (f2), and the length (D) of the input data.

## Background
CLAIM FOR PRIORITY
This application claims priority to Korean Patent Application No. 10-2010-0133081 filed on Dec. 23, 2010 in the Korean Intellectual Property Office (KIPO), the entire contents of which are hereby incorporated by reference.
BACKGROUND
1. Technical Field
Example embodiments of the present invention relate to data transmission of mobile communication systems, and more particularly, to a data rate matching method and apparatus for use in mobile communication systems.
2. Related Art
In 3rd Generation Partnership Project (3GPP) and long term evolution (LTE)-advanced systems, a rate matcher performs data rate matching for matching a length of turbo encoded data or convolutionally encoded data with a length of data required for wireless transmission in a data encoding process of a transmission stage, and a de-rate matcher performs de-rate matching for matching a length of data received by wireless transmission with a length of input data of a turbo decoder or a convolutional decoder in a data decoding process of a reception stage opposite to the transmission stage.
However, because a sub-block interleaver of a rate matcher of the related art is configured to process only a single-bit input for input bit data, there is a disadvantage in that processing of parallel data input of two or more bits may not be possible. That is, the rate matcher of the related art has a problem in that a data collision occurs in a memory where input data is stored, if data is input in parallel to the rate matcher of the related art.
SUMMARY
Accordingly, example embodiments of the present invention are provided to substantially obviate one or more problems due to limitations and disadvantages of the related art.
Example embodiments of the present invention provide a data rate matching method for use in mobile communication systems that can perform parallel interleaving at a high speed without a collision between encoded data input in parallel.
Example embodiments of the present invention also provide a data rate matching apparatus for use in mobile communication systems that can perform parallel interleaving at a high speed without a collision between encoded data input in parallel.
In some example embodiments, a data rate matching method for use in a data rate matching apparatus including a plurality of interleavers in mobile communication systems, includes: calculating a set of first parameters (f1) based on a length (D) of encoded input data input to the plurality of interleavers in series or parallel; calculating a set of second parameters (f2) based on a set of prime numbers constituting a value of the length (D) of the input data; and performing interleaving based on the set of first parameters (f1), the set of second parameters (f2), and the length (D) of the input data.
The calculating of the set of first parameters (f1) may include: calculating all values satisfying 1, which is a greatest common divisor of the first parameter (f1) and the length (D) of the input data, as the first parameters when the length (D) of the input data is not a multiple of 2, or is a multiple of 4.
The calculating of the set of first parameters (f1) may include: calculating all values satisfying 1, which is a greatest common divisor of the first parameter (f1) and half the length (D) of the input data, as the first parameters when the length (D) of the input data is a multiple of 2 and not a multiple of 4.
The calculating of the set of second parameters (f2) may include: calculating the set of second parameters (f2) using f2=ΠpεP pnF,p for all p satisfying nF,p≧1 and nN,p≧1, where P is a set of prime numbers among divisors of the length (D) of the input data, and p is an element of the set of prime numbers, when the length (D) of the input data is not a multiple of 2, or is a multiple of 4.
The calculating of the set of second parameters (f2) may include: calculating the set of second parameters (f2) using f2=ΠpεP pnF,p for all p satisfying nF,p≧1, p≠2, and nN,p≧1, where a sum of the first to parameter (f1) and the second parameter (f2) is an odd number, when the length (D) of the input data is a multiple of 2 and not a multiple of 4.
The performing of the interleaving may include: generating interleaved output data by applying the first parameter (f1) and the second parameter (f2) to Π(k)=mod((f1k+f2k2), D), where k=0, 1, . . . , KΠ and KΠ denotes the size of a matrix.
In other example embodiments, a data rate matching apparatus for use in mobile communication systems, includes: a plurality of sub-block interleavers configured to calculate a set of first parameters (f1) based on a length (D) of encoded input data input in series or parallel, calculate a set of second parameters (f2) based on a set of prime numbers constituting a value of the length (D) of the input data, and perform interleaving based on the set of first parameters (f1), the set of second parameters (f2), and the length (D) of the input data.



BRIEF DESCRIPTION OF DRAWINGS
Example embodiments of the present invention will become more apparent by describing in detail example embodiments of the present invention with reference to the accompanying drawings, in which:
FIG. 1 is a block diagram showing a rate matcher of a 3GPP LTE system;
FIG. 2 is an output memory address of a sub-block interleaver;
FIG. 3 shows the relationship between an output memory address and a collision when data is input to the sub-block interleaver in parallel;
FIG. 4 is a block diagram showing a configuration of a data rate matching apparatus according to an example embodiment of the present invention;
FIG. 5 is a conceptual diagram showing a configuration of an internal memory of the sub-block interleaver according to an example embodiment of the present invention;
FIG. 6 shows an output address of the sub-block interleaver according to an example embodiment of the present invention;
FIG. 7 is a conceptual diagram showing a configuration of an internal memory of a sub-block interleaver according to another example embodiment of the present invention; and
FIG. 8 shows an output address of the sub-block interleaver according to another example embodiment of the present invention.



DESCRIPTION OF EXAMPLE EMBODIMENTS
Example embodiments of the present invention are disclosed herein. However, specific structural and functional details disclosed herein are merely representative for purposes of describing example embodiments of the present invention, however, example embodiments of the present invention may be embodied in many alternate forms and should not be construed as limited to example embodiments of the present invention set forth herein.
Accordingly, while the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit the invention to the particular forms disclosed, but on the contrary, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention. Like numbers refer to like elements throughout the description of the figures.
It will be understood that, although the terms first, second, A, B, etc. may be used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another. For example, a first element could be termed a second element, and, similarly, a second element could be termed a first element, without departing from the scope of the present invention. As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items.
It will be understood that when an element is referred to as being “connected” or “coupled” to another element, it can be directly connected or coupled to the other element or intervening elements may be present. In contrast, when an element is referred to as being “directly connected” or “directly coupled” to another element, there are no intervening elements present. Other words used to describe the relationship between elements should be interpreted in a like fashion (i.e., “between” versus “directly between,” “adjacent” versus “directly adjacent,” etc.).
The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. As used herein, the singular forms “a,” “an,” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises,” “comprising,” “includes,” and/or “including,” when used herein, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.
Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. It will be further understood that terms, such as those defined in commonly used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the relevant art and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein.
Hereinafter, example embodiments of the present invention will be described in detail with reference to the accompanying drawings. To understand the invention easily, the same elements are designated using the same reference numerals, and redundant description thereof is omitted.
FIG. 1 is a block diagram showing a rate matcher of a 3GPP LTE system, and FIG. 2 is an output memory address of a sub-block interleaver. FIG. 3 shows the relationship between an output memory address and a collision when data is input to the sub-block interleaver in parallel.
The rate matcher for data rate matching of turbo encoded data includes a plurality of sub-block interleavers 10 for interleaving three bit streams d(0)k, d(1)k, and d(2)k, a bit collector 20, and a bit selector 30.
The plurality of sub-block interleavers 10 interleave input bit streams d(i)k into interleaved data streams v(i)k (where i=0, 1, 2 and k=0, 1, . . . , KΠ). Bits are selected from the interleaved data streams through a virtual circular buffer according to output bit size, and then a sequence of bits qk is output.
The sub-block interleaver 10 interleaves input bits d(i)0, d(i)1, d(i)2, . . . , d(i)D−1 (where D is the number of input bits and i=0, 1, 2), and outputs bits v(i)0, v(i)1, v(i)2, . . . , v(i)KΠ−1 (where KΠ is defined below and i=0, 1, 2).
An output bit sequence of the sub-block interleaver 10 is derived as follows.
First, the number of columns of a matrix is denoted by Csubblock=32 (where the columns of the matrix are numbered 0, 1, 2, . . . , Csubblock−1 from left to right), and a minimum integer Rsubblock satisfying D≦(Rsubblock×Csubblock) is calculated. Here, the rows of the rectangular matrix are numbered 0, 1, 2, . . . , Rsubblock−1 from top to bottom.
If (Rsubblock×Csubblock)>D, ND=(Rsubblock×Csubblock−D) dummy bits are added (that is, yk=<NULL> and k=0, 1, . . . , ND−1). An input bit sequence is written into a (Rsubblock×Csubblock) matrix (that is, yND+k=d(i)k and k=0, 1, . . . , D−1). At this time, a matrix is configured row by row starting with bit y0 within column 0 of row 0 of the matrix as shown in Expression (1).




  
    
      
        [
        
          
            
              
                y
                0
              
            
            
              
                y
                1
              
            
            
              
                y
                2
              
            
            
              ...
            
            
              
                y
                
                  
                    C
                    subblock
                  
                  -
                  1
                
              
            
          
          
            
              
                y
                
                  C
                  subblock
                
              
            
            
              
                y
                
                  
                    C
                    subblock
                  
                  +
                  1
                
              
            
            
              
                y
                
                  
                    C
                    subblock
                  
                  +
                  2
                
              
            
            
              ...
            
            
              
                y
                
                  
                    2
                    ⁢
                    
                      C
                      subblock
                    
                  
                  -
                  1
                
              
            
          
          
            
              ⋮
            
            
              ⋮
            
            
              ⋮
            
            
              ⋱
            
            
              ⋮
            
          
          
            
              
                y
                
                  
                    (
                    
                      
                        R
                        subblock
                      
                      -
                      1
                    
                    )
                  
                  ×
                  
                    C
                    subblock
                  
                
              
            
            
              
                y
                
                  
                    
                      (
                      
                        
                          R
                          subblock
                        
                        -
                        1
                      
                      )
                    
                    ×
                    
                      C
                      subblock
                    
                  
                  +
                  1
                
              
            
            
              
                y
                
                  
                    
                      (
                      
                        
                          R
                          subblock
                        
                        -
                        1
                      
                      )
                    
                    ×
                    
                      C
                      subblock
                    
                  
                  +
                  2
                
              
            
            
              ...
            
            
              
                y
                
                  (
                  
                    
                      
                        R
                        subblock
                      
                      ×
                      
                        C
                        subblock
                      
                    
                    -
                    1
                  
                  )
                
              
            
          
        
        ]
      
    
    
      
        (
        1
        )
      
    
  




Thereafter, for d(0)k and d(1)k, inter-column permutation of the matrix is performed on the basis of an inter-column permutation pattern P(j)jε{0, 1, . . . , Csubblock−1} of Table 1. Here, P(j) denotes an original column position of a j-th permutated column. After permutation of the columns, the inter-column permutated (Rsubblock×Csubblock) matrix is defined as Expression (2)




  
    
      
         
        
          [
          
            
          
          ⁢
          
            
              
                
                  y
                  
                    P
                    ⁡
                    
                      (
                      0
                      )
                    
                  
                
              
              
                
                  y
                  
                    P
                    ⁡
                    
                      (
                      1
                      )
                    
                  
                
              
              
                
                  y
                  
                    P
                    ⁡
                    
                      (
                      2
                      )
                    
                  
                
              
              
                ...
              
              
                
                  y
                  
                    P
                    ⁡
                    
                      (
                      
                        
                          C
                          subblock
                        
                        -
                        1
                      
                      )
                    
                  
                
              
            
            
              
                
                  y
                  
                    
                      P
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                    +
                    
                      C
                      subblock
                    
                  
                
              
              
                
                  y
                  
                    
                      P
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                    +
                    
                      C
                      subblock
                    
                  
                
              
              
                
                  y
                  
                    
                      P
                      ⁡
                      
                        (
                        2
                        )
                      
                    
                    +
                    
                      C
                      subblock
                    
                  
                
              
              
                ...
              
              
                
                  y
                  
                    
                      P
                      ⁡
                      
                        (
                        
                          
                            C
                            subblock
                          
                          -
                          1
                        
                        )
                      
                    
                    +
                    
                      C
                      subblock
                    
                  
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                ⋱
              
              
                ⋮
              
            
            
              
                
                  y
                  
                    
                      P
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                    +
                    
                      
                        (
                        
                          
                            R
                            subblock
                          
                          -
                          1
                        
                        )
                      
                      ×
                      
                        C
                        subblock
                      
                    
                  
                
              
              
                
                  y
                  
                    
                      P
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                    +
                    
                      
                        (
                        
                          
                            R
                            subblock
                          
                          -
                          1
                        
                        )
                      
                      ×
                      
                        C
                        subblock
                      
                    
                  
                
              
              
                
                  y
                  
                    
                      P
                      ⁡
                      
                        (
                        2
                        )
                      
                    
                    +
                    
                      
                        (
                        
                          
                            R
                            subblock
                          
                          -
                          1
                        
                        )
                      
                      ×
                      
                        C
                        subblock
                      
                    
                  
                
              
              
                ...
              
              
                
                  y
                  
                    
                      P
                      ⁡
                      
                        (
                        
                          
                            C
                            subblock
                          
                          -
                          1
                        
                        )
                      
                    
                    +
                    
                      
                        (
                        
                          
                            R
                            subblock
                          
                          -
                          1
                        
                        )
                      
                      ×
                      
                        C
                        subblock
                      
                    
                  
                
              
            
          
          ⁢
          
            
          
          ]
        
      
    
    
      
        (
        2
        )
      
    
  












TABLE 1





Number of Columns
Inter-column permutation pattern


Csubblock
<P(0), P(1), . . . , P(Csubblock − 1)>







32
<0, 16, 8, 24, 4, 20, 12, 28, 2, 18, 10, 26, 6, 22,



14, 30, 1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27,



7, 23, 15, 31>









The sub-block interleaver 10 generates an output by reading the inter-column permutated (Rsubblock×Csubblock) matrix as described above in units of columns. Sub-block-interleaved bits are v0(i), v1(i), v2(i), . . . , vKΠ−1(i). Here, v0(i)=yP(0), v1(i) is yP(0)+Csubblock . . . , and KΠ=(Rsubblock×Csubblock).
In addition, for dk(2), outputs of the sub-block interleaver 10 become v0(2), v1(2), v2(2), . . . , vKΠ−1(2). Here, vk(2)=yπ(K) and




  
    π
    ⁡
    
      (
      k
      )
    
  
  =
  
    
      (
      
        
          P
          ⁡
          
            (
            
              ⌊
              
                k
                
                  R
                  subblock
                
              
              ⌋
            
            )
          
        
        +
        
          
            C
            subblock
          
          ×
          
            (
            
              k
              ⁢
              
                
              
              ⁢
              mod
              ⁢
              
                
              
              ⁢
              
                R
                subblock
              
            
            )
          
        
        +
        1
      
      )
    
    ⁢
    mod
    ⁢
    
      
    
    ⁢
    
      
        K
        ∏
      
      .
    
  




The bit collector 20 generates a virtual circular buffer having a length Kw=3KΠ by Expression (3).

wk=vk(0) for k=0, . . . ,KΠ−1 

wKΠ+2k=vk(1) for k=0, . . . ,KΠ−1 

wKΠ+2k+1=vk(2) for k=0, . . . ,KΠ−1  (3)

In addition, the bit collector 20 calculates a start position K0 of bit selection of the rate matcher using Expression (4).




  
    
      
        
          k
          0
        
        =
        
          
            R
            subblock
          
          ·
          
            (
            
              
                2
                ·
                
                  ⌈
                  
                    
                      N
                      cb
                    
                    
                      8
                      ⁢
                      
                        
                      
                      ⁢
                      
                        R
                        subblock
                      
                    
                  
                  ⌉
                
                ·
                
                  rv
                  idx
                
              
              +
              2
            
            )
          
        
      
    
    
      
        (
        4
        )
      
    
  




In Expression (4), Rsubblock denotes the number of rows, and Ncb denotes a buffer size (for example, Ncb=Kw). In addition, rvidx (rvidx=0, 1, 2 or 3) denotes a redundancy version number of hybrid automatic repeat request (HARQ).
The bit selector 30 transmits output data by the following method:















Set k = 0 and j = 0



while { k < E }



 if w(k0 + j)mod Ncb ≠< NULL >



   ek = wj mod Ncb



   k = k +1



 end if



 j = j +1



end while










Here, E denotes the length of a rate matching output sequence, and ek (k=0, 1, . . . , E−1) denotes a rate matching output bit sequence.
In the rate matcher as described above, ND=(Rsubblock×Csubblock−D) dummy bits are padded (that is, yk=<NULL>) if (Rsubblock×Csubblock)>D in the sub-block interleaving process. The dummy bits should be removed in the output data transmission process of the rate matcher. In implementation of the rate matcher that removes the dummy bits as described above, (Q+ND) data should be processed for an output of the rate matcher in spite of the length of output data Q of the rate matcher. This causes the output of the rate matcher to be discontinuous, and hence makes signal control with a module interfacing with an output stage of the rate matcher complex.
The sub-block interleaver 10 of the above-described rate matcher may process a single-bit input as input bit data, but may not process parallel data input of two or more bits.
For example, when the length of input data of the sub-block interleaver is D=64 and an input data sequence is input to one memory bit by bit, an input/output data relationship of the sub-block interleaver is as follows.

    
    
        Interleaver Input Bits: d(i)0, d(i)1, d(i)2, . . . , d(i)63, i=0, 1, 2
        Interleaver Input Bits: v(i)0, v(i)1, v(i)2, . . . , v(i)63, i=0, 1, 2
        Main Parameters of Interleaver: Csubblock=32, Rsubblock=2, ND=0
    
    


The rate matcher output data corresponding to the above-described interleaver output bits is output from data of each memory through the interleaver address generation method as described above. That is, as shown in FIG. 2, a memory address to be used for output data generation of the sub-block for 1-bit input data is processed without a problem for a 1-bit output.
However, when the length of input data of the sub-block interleaver is D=64 and an input data sequence is input to two memories to which bits are input in parallel two by two, input data bits are simultaneously input two by two and stored in two memories as shown in FIG. 3.
Interleaver Input Bits
bank 0: d(i)0, d(i)2, d(i)4, . . . , d(i)2k, . . . , d(i)62, k=0, 1, 2, . . . , 31, i=0, 1, 2
bank 1: d(i)1, d(i)3, d(i)5, . . . , d(i)63, k=0, 1, 2, . . . , 31, i=0, 1, 2
Interleaver Output Bits
bank 0: v(i)0, v(i)2, v(i)4, . . . , v(i)2k, . . . , v(i)62, k=0, 1, 2, . . . , 31, i=0, 1, 2
bank 1: v(i)1, v(i)3, v(i)5, . . . , v(i)2k+1, . . . , d(i)63, k=0, 1, 2, . . . , 31, i=0, 1, 2
Main Parameters of Interleaver: Csubblock=32, Rsubblock=2, ND=0
The rate matcher as shown in FIG. 3 has a problem in that a collision between two memories occurs when data is input to the sub-block interleaver in parallel.
Hereinafter, a data rate matching apparatus and method capable of performing parallel interleaving at a high speed without a collision between data input in parallel will be described.
FIG. 4 is a block diagram showing a configuration of a data rate matching apparatus according to an example embodiment of the present invention. FIG. 5 is a conceptual diagram showing a configuration of an internal memory of the sub-block interleaver according to an example embodiment of the present invention. FIG. 6 shows an output address of the sub-block interleaver according to an example embodiment of the present invention. FIG. 7 is a conceptual diagram showing a configuration of an internal memory of the sub-block interleaver according to another example embodiment of the present invention. FIG. 8 shows an output address of the sub-block interleaver according to another example embodiment of the present invention.
Referring to FIGS. 4 to 8, the data rate matching apparatus according to the example embodiment of the present invention includes a plurality of sub-block interleavers 110, a bit collector 130, and a bit selector 150.
The sub-block interleavers 100 interleave three information bit streams d(0)k, d(i)k, and d(2)k input in parallel, and output interleaved data streams v(i)k (i=0, 1, 2 and k=0, 1, . . . , KΠ). After the interleaved data streams v(i)k are collected in a virtual circular buffer generated in the bit collector 130, bits are selected by the bit selector 150 according to output bit size, and a sequence of bits qk is output.
The sub-block interleaver 100 interleaves input bits d(i)0, d(i)1, d(i)2, . . . , d(i)D−1 (where D is the number of input bits and i=0, 1, 2), and outputs vΠ(0)(i), vΠ(1)(i), vΠ(2)(i), . . . , vΠ(k)(i), . . . , vΠ(D−1)(i) (where k=0 to D−1 and vΠ(k)(i) is a sub-block interleaver address). An output bit sequence of the sub-block interleaver is derived for vΠ(k)(i) according to an interleaver address as follows.
The sub-block interleaver 110 interleaves input data using the following Expression (5):

Π(k)=mod((f1k+f2k2),D)  (5)

In Expression (5), mod(a,b) is a modulus calculated value of a divided by b and is a remainder obtained by dividing a by b.
In Expression (5), f1 and f2 are set to differ according to the length of input data D of the sub-block interleaver 110. If D is not a multiple of 2 or is a multiple of 4, f1 is calculated as defined in Expression (6), and f2 is calculated as defined in Expression (7).

f1 satisfying gcd(f1,D)=1  (6)

In Expression (6), gcd(a,b) denotes the greatest common divisor of a and b.

f2=ΠpεPpnF,p for all p satisfying nF,p≧1 and nN,p≧1  (7)

Alternatively, if D is a multiple of 2 and not a multiple of 4, f1 is calculated as defined in Expression (8), and f2 is calculated as defined in Expression (9).

f1 satisfying gcd(f1,D/2)=1  (8)

f2=ΠpεPpnF,p for all p satisfying nF,p≧1, p≠2, and nN,p≧1, where f1+f2 is an odd number  (9)

For example, because P={2, 5} and D=23×5 when D=40, f1ε{3, 7, 9, 11, 13, . . . , 39} and f2ε{10, 20, 30, 40}.
In Expressions (7) and (9), P denotes a set of prime numbers constituting the length D of input data of the sub-block interleaver, and elements of P is P={p1, p2, . . . , pN}. Here, K=Πpεp pnN,p.
Conditions of the following Expressions (10) to (12) should be satisfied to calculate K=ΠpεPpN,p and f2=ΠpεPpnF,p.




  
    
      
        
          n
          
            F
            ,
            2
          
        
        ≥
        
          {
          
            
              
                
                  max
                  ⁡
                  
                    (
                    
                      
                        ⌈
                        
                          
                            
                              n
                              
                                K
                                ,
                                2
                              
                            
                            -
                            2
                          
                          2
                        
                        ⌉
                      
                      ,
                      1
                    
                    )
                  
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    
                      n
                      
                        K
                        ,
                        2
                      
                    
                  
                  >
                  0
                
              
            
            
              
                0
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    
                      n
                      
                        K
                        ,
                        2
                      
                    
                  
                  =
                  0
                
              
            
          
        
      
    
    
      
        (
        10
        )
      
    
  
  
    
      
        
          n
          
            F
            ,
            3
          
        
        ≥
        
          {
          
            
              
                
                  max
                  ⁡
                  
                    (
                    
                      
                        ⌈
                        
                          
                            
                              n
                              
                                K
                                ,
                                3
                              
                            
                            -
                            1
                          
                          2
                        
                        ⌉
                      
                      ,
                      1
                    
                    )
                  
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    
                      n
                      
                        K
                        ,
                        3
                      
                    
                  
                  >
                  0
                
              
            
            
              
                0
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    
                      n
                      
                        K
                        ,
                        3
                      
                    
                  
                  =
                  0
                
              
            
          
        
      
    
    
      
        (
        11
        )
      
    
  
  
    
      
        
          n
          
            F
            ,
            p
          
        
        ≥
        
          
            
              
                ⌈
                
                  
                    n
                    
                      K
                      ,
                      p
                    
                  
                  2
                
                ⌉
              
            
            
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    p
                  
                  ≠
                  2
                
                ,
                3
              
            
          
        
      
    
    
      
        (
        12
        )
      
    
  




Using results calculated on the basis of the above Expressions (10) to (12), f2 is defined as shown in Expression (13).

f2=mod(ΠpεPpnF,p,D)  (13)

For example, because P={2, 3, 5} and D=2×32×5 when D=90, f1ε{7, 11, 13, . . . , 89} and f2ε{2×3×5×1, 2×3×5×2, 2×3×5×3}. At this time, data is interleaved using Expression (5) as an interleaver address generator polynomial by selecting values of f1 and f2 one by one.
In addition, because P={2} and D=2×2×2×2×2×2 when D=64, f1ε{2} and f2ε{4×1, to 4×2, 4×3, . . . , mod(4×m, D)} (where m=1, 2, 3, . . . ). At this time, data is interleaved using Expression (5) as an interleaver address generator polynomial by selecting values of f1 and f2 one by one.
As compared to the related art, the sub-block interleaver 10 according to an example embodiment of the present invention may process bits in parallel two by two because a memory collision does not occur in an interleaving process when the length of input data is D=64 and bits are input in parallel two by two. For example, the sub-block interleaver 110 may interleave data by applying f1=3 and f2=4.
That is, when data bits are input to the sub-block interleavers two by two as described below, the data bits are stored in two memories as shown in FIGS. 5 and 6. For output data, data of the memories is interleaved and output according to the above-described method. At this time, in an interleaving method according to an example embodiment of the present invention, parallel processing may be performed without a collision between the two memories.
Sub-Block Interleaver Input Bits
bank 0: d(i)0, d(i)2, d(i)4, . . . , d(i)2k, . . . , d(i)62, k=0, 1, 2, . . . 31, i=0, 1, 2
bank 1: d(i)1, d(i)3, d(i)5, . . . , d(i)2k+1, . . . , d(i)63, k=0, 1, 2, . . . , 31, i=0, 1, 2
Sub-Block Interleaver Output Bits
bank 0: v(i)0, v(i)2, v(i)4, . . . , v(i)2k, . . . , d(i)62, k=0, 1, 2, . . . , 31, i=0, 1, 2
bank 1: v(i)1, v(i)3, v(i)5, . . . , v(i)2k+1, . . . , d(i)63, k=0, 1, 2, . . . , 31, i=0, 1, 2
Main Parameter of Sub-Block Interleaver
Π(k)=mod((f1k+f2k2), D), where f1=3 and f2=4
Alternatively, when bits of data having an input data length D=64 are input to the sub-block interleavers in parallel four by four as described below, the data bits are stored in four memories as shown in FIGS. 7 and 8. For output data, data of the memories is interleaved and output according to the above-described method. At this time, in an interleaving method according to an example embodiment of the present invention, parallel processing may be performed without a collision between the four memories.
Sub-Block Interleaver Input Bits
bank 0: d(i)0, d(i)4, d(i)8, . . . , d(i)4k, . . . , d(i)60, k=0, 1, 2, . . . , 15, i=0, 1, 2
bank 1: d(i)1, d(i)5, d(i)9, . . . , d(i)4k+1, . . . , d(i)61, k=0, 1, 2, . . . , 15, i=0, 1, 2
bank 2: d(i)2, d(i)6, d(i)10, . . . , d(i)4k+2, . . . , d(i)62, k=0, 1, 2, . . . , 15, i=0, 1, 2
bank 3: d(i)3, d(i)7, d(i)11, . . . , d(i)4k+3, . . . , d(i)63, k=0, 1, 2, . . . , 15, i=0, 1, 2
Sub-Block Interleaver Output Bits
bank 0: v(i)0, v(i)4, v(i)8, . . . , v(i)4k, . . . , v(i)60, k=0, 1, 2, . . . , 15, i=0, 1, 2
bank 1: v(i)1, v(i)5, v(i)9, . . . , v(i)4k+1, . . . , v(i)61, k=0, 1, 2, . . . , 15, i=0, 1, 2
bank 2: v(i)2, v(i)6, v(i)10, . . . , v(i)4k+2, . . . , v(i)62, k=0, 1, 2, . . . , 15, i=0, 1, 2
bank 3: v(i)3, v(i)7, v(i)11, . . . , v(i)4k+3, . . . v(i)63, k=0, 1, 2, . . . , 15, i=0, 1, 2
Main Parameter of Sub-Block Interleaver
Π(k)=mod((f1k+f2k2), D), where f1=3 and f2=4
According to the data rate matching method and apparatus for use in mobile communication systems as described above, a sub-block interleaver of a data rate matching apparatus of a transmitter provides a parallel processing function for parallel input data, and provides a high-speed efficient signal processing function by removing signal processing of dummy bits occurring according to the length of input data.
A decoding stage of a receiver can also provide a signal processing function for parallel input data in a data rate de-interleaving process by applying a sub-block interleaver according to an example embodiment of the present invention. This enables hardware to signal processing time to be reduced in an encoder and a decoder for transmission data, so that data can be transmitted at a high speed in a mobile communication system.
While the example embodiments of the present invention and their advantages have been described in detail, it should be understood that various changes, substitutions and alterations may be made herein without departing from the scope of the invention.

## Claims

1. A data rate matching method for use in a data rate matching apparatus including a plurality of interleavers in mobile communication systems, comprising:
calculating a set of first parameters (f1) based on a length (D) of encoded input data input to the plurality of interleavers in series or parallel;
calculating a set of second parameters (f2) based on a set of prime numbers constituting a value of the length (D) of the input data; and
performing interleaving based on the set of first parameters (f1), the set of second parameters (f2), and the length (D) of the input data,
wherein the performing of the interleaving includes generating interleaved output data by applying the first parameter (f1) and the second parameter (f2) to Π(k)=mod((f1k+f2k2), D), where k=0, 1, . . . , KΠ and KΠ denotes a size of a matrix.

2. The data rate matching method of claim 1, wherein the calculating of the set of first parameters (f1) includes:
calculating all values satisfying 1, which is a greatest common divisor of the first parameter (f1) and the length (D) of the input data, as the first parameters when the length (D) of the input data is not a multiple of 2, or is a multiple of 4.

3. The data rate matching method of claim 1, wherein the calculating of the set of first parameters (f1) includes:
calculating all values satisfying 1, which is a greatest common divisor of the first parameter (f1) and half the length (D) of the input data, as the first parameters when the length (D) of the input data is a multiple of 2 and not a multiple of 4.

4. The data rate matching method of claim 1, wherein the calculating of the set of second parameters (f2) includes:
calculating the set of second parameters (f2) using


f2=ΠpεPpnF,p for all p satisfying nF,p≧1 and nN,p≧1,


where P is a set of prime numbers among divisors of the length (D) of the input data, and p is an element of the set of prime numbers, when the length (D) of the input data is not a multiple of 2, or is a multiple of 4.

5. The data rate matching method of claim 1, wherein the calculating of the set of second parameters (f2) includes:
calculating the set of second parameters using


f2=ΠpεPpnF,p for all p satisfying nF,p≧1, p≠2, and nN,p≧1,


where a sum of the first parameter (f1) and the second parameter (f2) is an odd number, when the length (D) of the input data is a multiple of 2 and not a multiple of 4.

6. A data rate matching apparatus for use in mobile communication systems, comprising:
a plurality of sub-block interleavers configured to calculate a set of first parameters (f1) based on a length (D) of encoded input data input in series or parallel, calculate a set of second parameters (f2) based on a set of prime numbers constituting a value of the length (D) of the input data, and perform interleaving based on the set of first parameters (f1), the set of second parameters (f2), and the length (D) of the input data,
wherein the plurality of subblock interleavers each generate interleaved output data by applying the first parameter (f1) and the second parameter(f2) to Π(k)=mod((f1k+f2k2), D), where k=0, 1, . . . , KΠ, and KΠ denotes a size of a matrix.

7. The data rate matching apparatus of claim 6, wherein the plurality of sub-block interleavers each calculate all values satisfying 1, which is a greatest common divisor of the first parameter (f1) and the length (D) of the input data, as the first parameters when the length (D) of the input data is not a multiple of 2 and is a multiple of 4.

8. The data rate matching apparatus of claim 6, wherein the plurality of sub-block interleavers each calculates all values satisfying 1, which is a greatest common divisor of the first parameter (f1) and half the length (D) of the input data, as the first parameters when the length (D) of the input data is a multiple of 2 and not a multiple of 4.

9. The data rate matching apparatus of claim 6, wherein the plurality of sub-block interleavers each calculate the set of second parameters (f2) using


f2=ΠpεPpnF,p for all p satisfying nF,p≧1 and nN,p≧1,

where P is a set of prime numbers among divisors of the length (D) of the input data, and p is an element of the set of prime numbers, when the length (D) of the input data is not a multiple of 2, or is a multiple of 4.

10. The data rate matching apparatus of claim 6, wherein the plurality of sub-block interleavers each calculate the set of second parameters (f2) using


f2=ΠpεPpnF,p for all p satisfying nF,p≧1, p≠2, and nN,p≧1,

where a sum of the first parameter (f1) and the second parameter (f2) is an odd number, when the length (D) of the input data is a multiple of 2 and not a multiple of 4.