Turbo interleaving apparatus and method

Abstract

A 2-dimensional interleaving method is disclosed. The method comprises dividing a frame of input information bits into a plurality of groups and sequentially storing the divided groups in a memory; permuting the information bits of the groups according to a given rule and shifting an information bit existing at the last position of the last group to a position preceding the last position; and selecting the groups according to a predetermined order, and selecting one of the information bits in the selected group.

What is claimed is: 
     
       1. A turbo encoder comprising:
 a first encoder configured for encoding a frame of K input information bits to generate first coded symbols; 
 an interleaver configured for
 receivingsequentially writing the K information bits into a Row (R)×Column (C) rectangular matrix, row by row, starting in a first column of a first row, 
 intra row permuting positions of the K information bits in the R×C rectangular matrix in each row according to a given interleaving rule, 
 exchanging a position of an information bit in a last column of a last row with a position of an information bit in the first column of the last row, after the intra row permuting, 
 performing inter-row permutations of the R×C rectangular matrix, and 
 and interleaving the information bits position such that an information bit existing at the last position of the frame is shifted to a position preceding the last position for not generating Critical Information Sequence Pattern (CISP)reading out the information bits from the permuted R×C rectangular matrix, column by column, starting in the first row of the first column; and 
 
 a second encoder configured for encoding the interleaved read out information bits to generate second coded symbols, 
 wherein the R×C rectangular matrix includes R rows and C columns, K=R×C, and K indicates a number of the information bits included in the frame. 
 
     
     
       2. The turbo encoder as claimed in  claim 1 , wherein the interleaver comprises:
 a controller for writing the information bits sequentially in memory and dividing the information bits into R groups each having the C information bits; permuting the an address of the an information bit written in a jth row (where, j=0,1,2, . . . , R−1) to positions C j (i) in the row in accordance with an algorithm given by
 i) C(i)=[g 0 ×C(i−1)] mod p, i=1,2, . . . , (p−2) and C(0)=1 
 ii) C j (i)=C([i×p j ] mod (p−1)),
 j=0,1,2, . . . , (R−1), i=0,1,2, . . . , (p−1 2), C j (p−1)=0, and C j (p)=p 
 
 iii) exchange C R-1 (p) with C R-1 (0) 
 where p (prime number) indicates a minimum prime number which is closest to K/R satisfying 0≦(p+1)−K/R, g 0  (primitive root) indicates a predetermined number corresponding to an associated primitive root for p, and p j  indicates a primitive number set. 
 
 
     
     
       3. The turbo encoder as claimed in  claim 2 , wherein the interleaver comprises:
 a memory for storing the information bit frame sequentially;   a randomizer for permuting the address of the stored informnation bits according as shifting the address of an informnation bit existing at the last position to a position preceding the last position in the last group.   
     
     
       4. The turbo encoder as claimed in  claim 3 , wherein the randomizer exchanges an information bit address existing at the last position of the last group with an information bit address existing at a first position of the last group. 
     
     
       5. A device for permuting information bit addresses of an input frame which have R Row (R) groups, each of the R groups having C Column (C) information bits, in a prime interleaver (PIL) used as an internal interleaver for a turbo encoder, the device comprising:
 a memory for storing the information bit frame sequentially; and  
 a randomizer for permuting the addresses of the information bit frame according to a given interleaving rule, and changing the exchanging an address of an a last information bit to a position preceding the position in the position with an address of an information bit existing at a first position of a last group, after the permuting. 
 
     
     
       6. The device as claimed in  claim 5 , wherein the randomizer exchanges an information bit position existing at the last position of the last group with an information bit position existing at a first position of the last group. 
     
     
       7. A device for interleaving a frame of K information bits which have R Row (R) groups, each of the R groups having C Column (C) information bits, in a PIL interleaver prime interleaver (PIL) used as an internal interleaver for a turbo encoder, the device comprising:
 a controller for writing input information bits of a frame in a memory sequentially and permuting the position positions of the information bits written in a jth row (where, j can be 0,1,2, . . . , or R−1) to position C j (i) in the row in accordance with an algorithm given by
 i) permute a base sequence C(i)=[g 0 ×C(i−1)] mod p, i=1,2, . . . , (p−2) and C(0)=1 
 ii) perform row permutation C j (i)=C([i×p j ] mod (p−1)),
 j=0,1,2, . . . , (R−1), i=0,1,2, . . . , (p−1 2), C j (p−1)=0, and C j (p)=p 
 
 iii) exchange C R-1 (p) with C R-1 (0) 
 where p (prime number) indicates a minimum prime number which is closest to K/R satisfying 0≦(p+1)−K/R, g 0  (primitive root) indicates a predetermined number corresponding to an associated primitive root for p, and p j  indicates a primitive number set. 
 
 
     
     
       8. A 2-dimensional interleaving method comprising the steps of:
 storing a frame of K input information bits into a memory sequentially and dividing an the information bits into R Row (R) groups, each of the R groups having C Column (C) information bits; 
 permuting the information bits addresses of the each group according to a given rule; and 
 changingexchanging an information bit address existing at thea last position of thea last group to a address preceding the last positionwith an information bit address existing at a first position of the last group, subsequent to the permuting. 
 
     
     
       9. A The 2-dimensional interleaving method as claimed in  claim 8 , wherein the permuting the information bits addresses, comprises:
 determining a minimum prime number p which is closest to K/R satisfying 0≦(p+1)−K/R, sequentially writing input sequences of information bits of a frame in a memory; 
 selecting a primitive root g 0  corresponding to the minimum prime number p, and generating a base sequence C(i) for intra-row permuting the input sequences written in the rows in accordance with
   C(i)=[g 0 ×C(i−1)] mod p, i=1,2, . . . , (p−2), and C(0)=1;
 
 
 calculating a minimum prime integer set {q j }(j=0,1,2, . . . , R−1) by determining
   g.c.d{q j ,p−1}=1
 
   q j >6, q j >q (j-1)    
 where g.c.d is a greatest common divider and q 0 =1; 
 
 intra-row permuting {q j } using
   p P(j) =q j , j=0,1, . . . , R−1
 
 where P(j) indicates a predetermined selecting order for selecting the R rows; 
 
 when C=p+1, permuting sequences in a jth row in accordance with
   C j (i)=C([i×p j ] mod(p−1)),
 
 where j=0,1,2, . . . , (R−1), i=0,1,2, . . . , (p−1 2), C j (p−1)=0, and C j (p)=p, 
 and if (K=C×R), then C R-1 (p) is exchanged with C R-1 (0). 
 
 
     
     
       10. The 2-dimensional interleaving method as claimed in  claim 8 , wherein an information bit address existing at the last position of the last group is exchanged with an information bit address existing at a first position of the last group. 
     
     
       11. A 2-dimensional interleaving method comprising the steps of:
 writing input sequences of a frame of input information bits which have R Row (R) groups, each of the R groups having C Column (C) information bits, in a memory; 
 permuting the address addresses of the information bits written in the memory according to a given rule; and  
 shiftingexchanging an address of an information bit written in thea last position of thea last group to a position precedingwith an address of an information written in a first position of the last group, subsequent to the permuting. 
 
     
     
       12. The 2-dimensional interleaving method as claimed in  claim 11 , wherein the input sequence written in the last position of the last group is exchanged with an input sequence written in a first position of the last group. 
     
     
       13. A method for interleaving a frame of input information bits which have R Row (R) groups, each of the R groups having C Column (C) information bits, in a PIL interleaver prime interleaver (PIL) used as an internal interleaver for a turbo encoder, the method comprising the steps of:
 a) permuting the information bits position positions of the groups according to a predetermined PIL interleaving rule; and  
 b) changing exchanging an information bit existing at the a last position of the frame to a position preceding the last position a last group with an information bit existing at a first position of the last group, subsequent to the permuting. 
 
     
     
       14. The method as claimed in  claim 13 , wherein an information bit position existing at the last position of the last group is exchanged with an information bit existing at a first position of the last group. 
     
     
       15. The method as claimed in  claim 13 , wherein in the step a and b), the information bits position positions of the frame written in an a jth row (where j=0,1,2, . . . , R−1) are permuted to positions C j (i) in the row in accordance with the steps of an algorithm given by the steps of
 i) calculating C(i)=[g 0 ×c(i−1)] mod p, i=1,2, . . . , (p−2) and C(0)=1 
 ii) calculating C j (i)=C([i×p j ] mod(p−1)), where
 j=0,1,2, . . . , (R−1), i=0,1,2, . . . , (p−1 2), C j (p−1)=0, and C j (p)=p 
 
 iii) exchanging C R-1 (p) with C R-1 (0)
 where p (prime number) indicates a minimum prime number which is closest to K/R satisfying 0≦(p+1)−K/R, K indicates a number of the input information bits in the frame, g 0  (primitive root) indicates a predetermined number corresponding to an associated primitive root for p, p j  indicates a primitive number set, and c j (i) is the an input bit position of an ith output after the permutation of a jth row. 
 
 
     
     
       16. A 2-dimensional interleaving method comprising the steps of:
 sequentially writing input sequences of information bits of the a frame in an R a Row (R)×C Column rectangular matrix; 
 selecting a primitive root g 0  corresponding to the a minimum prime number p, and generating a base sequence c(i) for intra-row permuting the input sequences written in the rows of the R×C rectangular matrix in accordance with
   C(i)=[g 0 ×C(i−1)] mod p, i=1,2, . . . , (p−2), and C(0)=1;
 
 
 calculating a minimum prime integer set {q j }(j=0,1,2, . . . , R−1) by determining
   g.c.d{q j ,p−1}=1
 
   q j >6, q j >q (j-1)    
 where g.c.d is a greatest common divider and q 0 =1; 
 
 intra-row permuting {q j } using
   p P(j) =q j , j=0,1, . . . , R−1
 
 where P(j) indicates a predetermined selecting order for selecting the R rows; 
 
 when C=p+1, permuting sequences in a jth row in accordance with
   C j (i)=C([i×p j ] mod(p−1)),
 
 where j=0,1,2, . . . , (R−1), i=0,1,2, . . . , (p−1 2), C j (p−1)=0, and C j (p)=p, 
 and if (K=C×R), then C R-1 (p) is exchanged with C R-1 (0), 
 
 selecting R rows according to a predetermined order P(j), and selecting one input sequence from the selected row; and 
 providing the selected input sequence as a read address for interleaving the information bits of the input frame. 
 
     
     
       17. The turbo encoder as claimed in claim 1, wherein the interleaver is further configured for permuting addresses of the information bits written in a jth row, where, j=0, 1, 2, . . . , R−1, to positions C j (i) in the row in accordance with an algorithm given by
 i) C(i)=[g0×C(i−1)] mod p, i=1,2, . . . ,(p−2) and C(0)=1 
 ii) C j (i)=C([i×p j ] mod (p−1)), j=0,1,2, . . . ,(R−1), i=0,1,2, . . . ,(p−2), C j (p−1)=0, and C j (p)=p 
 iii) exchange C R-1 (p) with C R-1 (0) 
 where p indicates a minimum prime number satisfying 0≦(p+1)−K/R, g0 indicates an associated primitive root for p, and p j  indicates a prime number set. 
 
     
     
       18. A device for permuting information bit addresses of an input frame, the input frame having Row (R) groups, each of the R groups having Column (C) information bits, the device being configured in an internal interleaver for a turbo encoder, the device comprising:
 a memory configured for storing the information bits frame sequentially; and   a randomizer configured for
 intra-row permuting an address of the stored information bits in each row according to a given interleaving rule, 
 exchanging an address of an information bit existing at a last position of a last group with an address of an information bit existing at a first position of the last group, after the intra-row permuting, 
 performing inter-row permutations, and 
   reading out the information bits, column by column, starting in the first row of the first column.   
     
     
       19. A device for interleaving a frame of K information bits, the frame having Row (R) groups, each the R groups having Column (C) information bits, the device comprising:
 an interleaver for two-dimensional interleaving for a turbo encoder configured for sequentially writing input information bits of a frame in a memory and permuting positions of the information bits written in a jth row to a position C j (i) in the row, where, j can be 0,1,2 . . . , or R−1, in accordance with an algorithm given by   iv) permute a base sequence C(i)=[g0×C(i−1)] mod p, i=1,2, . . . ,(p−2) and C(0)=1,   v) perform row permutation C j (i)=C([i×p j ] mod (p−1)), j=0,1.2, . . ,(R−1), i=0,1,2, . . . , (p−2), C j (p−1)=0, and C j (p)=p,   vi) exchange C R-1 (p) with C R-1 (0);   where K specifies a number of input information bits in a frame, p indicates a minimum prime number satisfying 0≦(p+1)−K/R, g0 indicates an associated primitive root for p, and p j  indicates a prime number set.   
     
     
       20. The device according to claim 19, further comprising a randomizer configured for permuting the addresses of the stored information bits in accordance with exchanged positions of the stored information bits. 
     
     
       21. A two-dimensional interleaving method comprising the steps of:
 sequentially storing a frame of K input information bits, the frame having Row (R) groups, each of the R groups having Column (C) information bits;   permuting information bit addresses of the each of the R groups according to a given interleaving rule; and   exchanging an address of an information bit existing at a last position of a last group with an address of an information bit existing at a first position of the last group, subsequent to the permuting.   
     
     
       22. The two-dimensional interleaving method as claimed in claim 21, wherein the step of permuting comprises:
 determining a minimum prime number p satisfying 0≦(p+1)−K/R;   selecting a primitive root g0 associated with the minimum prime number p, and   generating a base sequence C(i) for intra-row permuting of the input sequences written in the rows in accordance with   C(i)=[g0×C(i−1)] mod p, i=1,2, . . . ,(p−2), and C(0)=1;   calculating a minimum prime integer set {q j }(j=0,1,2, . . . ,R−1) by determining
 g.c.d{q j ,p−1}=1 
 q j >6, q j >q (j-1)    
 where g.c.d is a greatest common divider and q 0 =1; 
   intra-row permuting {q j } using
 p P(j) =q j , j=0,1, . . . ,R−1 
 where P(j) indicates a predetermined selecting order for selecting the R rows; and 
   when C=p+1, permuting sequences in a jth row in accordance with
 C j (i)=C([i×p j ] mod (p−1)), 
 where j=0,1,2, . . . ,(R−1), i=0,1,2, . . . ,(p−2), C j (p−1)=0, and C j (p)=p, 
 and if (K=C×R), then C R-1 (p) is exchanged with C R-1 (0). 
   
     
     
       23. A two-dimensional interleaving method comprising the steps of:
 writing input sequences of a frame of input information bits in a memory, the frame having Row (R) groups, each of the R groups having Column (C) information bits;   permuting addresses of the information bits written in the memory according to a given interleaving rule; and   exchanging an address of an information bit written in a last position of a last group with an information bit written in a first position of the last group, subsequent to the permuting.   
     
     
       24. A method for interleaving a frame of input information bits, the frame having Row (R) groups, each of the R groups having Column (C) information bits, the method for use in an internal interleaver of a turbo encoder, the method comprising the steps of:
 a) permuting information bit positions of the groups according to predetermined interleaving rule; and   b) exchanging an information bit existing at a last position of a last group with an information bit existing at a first position of the last group.   
     
     
       25. The method as claimed in claim 24, wherein in the step a) and b), the R groups are rows and the information bits positions of the frame written in a jth row, where j=0,1,2, . . . ,R−1, are permuted with positions C j (i) in the row in accordance with an algorithm given by
 i) calculating C(i)=[g0×C(i−1)] mod p, i=1,2, . . . ,(p−2) and C(0)=1 
 ii) calculating C j (i)=C([i×p j ] mod (p−1)), where
 j=0,1,2, . . . ,(R−1), i=0,1,2, . . . ,(p−2), C j (p−1)=0, and C j (p)=p 
 
 iii) exchanging C R-1 (p) with C R-1 (0) 
 where k specifies a number of input information bits in a frame, p indicates a minimum prime number satisfying 0≦(p+1)−K/R, g0 indicates an associated primitive root for p, p j  indicates a prime number set, and C j (i) is the input bit position of an ith output after the permutation of a jth row. 
 
     
     
       26. A two-dimensional interleaving method comprising the steps of:
 sequentially writing input sequences of information bits of a frame in a Row (R)×Column (C) rectangular matrix, the frame having R groups, each of the R groups having C information bits;   selecting a primitive root g0 corresponding to a minimum prime number p satisfying 0≦(p+1)−K/R;   generating a base sequence C(i) for intra-row permuting the input sequences written in the rows in accordance with
 C(i)=[g0×C(i−1)] mod p, i=1,2, . . . ,(p−2), and C(0)=1; 
   calculating a minimum prime integer set {q i }(j=0,1,2, . . . ,R−1) by determining
 g.c.d{q j ,p−1}=1 
 q j >6, q j >q (j-1)    
 where g.c.d is a greatest common divider and q 0 =1; 
   intra-row permuting {q j } using
 p P(j) =q j , j=0,1, . . . ,R−1 
 where P(j) indicates a predetermined selecting order for selecting the R rows; 
   when C=p+1, permuting sequences in a jth row in accordance with
 C j (i)=C([i×p j ] mod (p−1)), 
 where j=0,1,2, . . . ,(R−1), i=0,1,2, . . . ,(p−2), C j (p−1)=0, and C j (p)=p, 
 and if (K=C×R), then C R-1 (p) is exchanged with C R-1 (0), 
   selecting R rows according to a predetermined order P(j);   selecting an input sequence from the selected rows; and   providing the selected input sequence as read addresses for interleaving the information bits of the input frame.   
     
     
       27. A two-dimensional interleaving method comprising the steps of:
 sequentially storing a frame of K input information bits, the frame having Row (R) groups, each of the R groups having Column (C) information bits;   permuting the information bits addresses of each of the R groups according to a given interleaving rule; and   exchanging an address of an information bit existing at a last position of a last group with an information bit existing at a first position of the last group, subsequent to the permuting.   
     
     
       28. A method for interleaving a frame of input information bits, the frame having Row (R) groups, each of the R groups having Column (C) information bits, the method for use in an internal interleaver of a turbo encoder, the method comprising the steps of:
 a) permuting the information bit positions of the groups according to predetermined interleaving rule; and   b) exchanging an information bit position existing at a last position of a last group with an information bit existing at a first position of the last group.   
     
     
       29. The method as claimed in claim 28, wherein in the step a) and b), the R groups are rows and the information bit positions of the frame written in a jth row, where j=0, 1, 2, . . . , R−1, are permuted with positions C j (i) in the row in accordance with the steps of an algorithm given by
 i) calculating C(i)=[g0×C(i−1)] mod p, i=1, 2, . . . , (p−2) and C(0)=1 
 ii) calculating C j (i)=C([i×p j ] mod (p−1)), j=0, 1, 2, . . . , (R−1), i=0, 1, 2, . . . , (p−21), C j (p−1)=0, and C j (p−1)=p 
 iii) exchanging C R-1 (p) with C R-1 (0) 
 where K specifies a number of input information bits in a frame, p indicates a minimum prime number, which is closest to K/R while satisfying 0≦(p+1)−K/R, g0 indicates an associated primitive root for predetermined number corresponding to p, p j  indicates a primitive prime number set and C j (i) is the information bit position of an ith output after the permutation of a jth row. 
 
     
     
       30. A turbo encoder comprising:
 a first encoder configured for encoding a frame of K input information bits to generate first coded symbols;   an interleaver configured for
 sequentially writing the K input information bits into a Row (R)×Column (C) rectangular matrix, row by row, starting in a first column of a first row, 
 intra row permuting positions of the information bits in the R×C rectangular matrix in each row according to a given interleaving rule, 
 exchanging a position of an information bit in a last column of a last row with a position within the last row which precedes the last column, after the intra row permuting, 
 performing inter-row permutations of the R×C rectangular matrix, and 
 reading out the information bits from the permuted R×C rectangular matrix, column by column, starting in the first row of the first column; and 
   a second encoder configured for encoding the read out information bits to generate second coded symbols,   wherein the R×C rectangular matrix includes R rows and C columns, K=R×C, and K indicates a number of the input information bits included in the frame.   
     
     
       31. The turbo encoder as claimed in claim 30, wherein the turbo encoder is further configured to store the input information bits in a memory, to perform the interleaving of the information bits in the R×C rectangular matrix based on generated read addresses corresponding to the permuted R×C rectangular matrix, and to output the information bits from the memory using the generated read addresses. 
     
     
       32. The turbo encoder as claimed in claim 30, wherein the turbo encoder is further configured to exchange the position of the information bit in the last column of the last row with a position of an information bit in the first column of the last row.