Turbo interleaving apparatus and method

A turbo encoder comprising:na first encoder configured for encoding a frame of K input information bits to generate first coded symbols;an interleaver configured fornreceiving sequentially 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, andand 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; anda 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.

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:na 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.

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:na 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 Cj(i) in the row in accordance with an algorithm given byni) permute a base sequence C(i)=[g0×C(i−1)] mod p, i=1,2, . . . , (p−2) and C(0)=1ii) perform row permutation Cj(i)=C([i×pj] mod (p−1)),nj=0,1,2, . . . , (R−1), i=0,1,2, . . . , (p−1 2), Cj(p−1)=0, and Cj(p)=piii) exchange CR-1(p) with CR-1(0)where p (prime number) indicates a minimum prime number which is closest to K/R satisfying 0≦(p+1)−K/R, g0(primitive root) indicates a predetermined number corresponding to an associated primitive root for p, and pj indicates a primitive number set.

A 2-dimensional interleaving method comprising the steps of:nstoring 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; andchanging exchanging an information bit address existing at the a last position of the a last group to a address preceding the last position with an information bit address existing at a first position of the last group, subsequent to the permuting.

A 2-dimensional interleaving method comprising the steps of:nwriting 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 shifting exchanging an address of an information bit written in the a last position of the a last group to a position preceding with an address of an information written in a first position of the last group, subsequent to the permuting.

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:na) 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.

A 2-dimensional interleaving method comprising the steps of:nsequentially writing input sequences of information bits of the a frame in an R a Row (R)×C Column rectangular matrix;selecting a primitive root g0 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 withnC(i)=[g0×C(i−1)] mod p, i=1,2, . . . , (p−2), and C(0)=1;ncalculating a minimum prime integer set {qj}(j=0,1,2, . . . , R−1) by determiningng.c.d{qj,p−1}=1nqj>6, qj>q(j-1) where g.c.d is a greatest common divider and q0=1;intra-row permuting {qj} usingnpP(j)=qj, j=0,1, . . . , R−1nwhere P(j) indicates a predetermined selecting order for selecting the R rows;when C=p+1, permuting sequences in a jth row in accordance withnCj(i)=C([i×pj] mod(p−1)),nwhere j=0,1,2, . . . , (R−1), i=0,1,2, . . . , (p−1 2), Cj(p−1)=0, and Cj(p)=p,and if (K=C×R), then CR-1(p) is exchanged with CR-1(0),selecting R rows according to a predetermined order P(j), and selecting one input sequence from the selected row; andproviding the selected input sequence as a read address for interleaving the information bits of the input frame.

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:na memory configured for storing the information bits frame sequentially; anda randomizer configured fornintra-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, andreading out the information bits, column by column, starting in the first row of the first column.

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:nan 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 Cj(i) in the row, where, j can be 0,1,2 . . . , or R−1, in accordance with an algorithm given byiv) 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 Cj(i)=C([i×pj] mod (p−1)), j=0,1.2, . . ,(R−1), i=0,1,2, . . . , (p−2), Cj(p−1)=0, and Cj(p)=p,vi) exchange CR-1(p) with CR-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 pj indicates a prime number set.

A two-dimensional interleaving method comprising the steps of:nsequentially 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; andexchanging 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.

A two-dimensional interleaving method comprising the steps of:nwriting 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; andexchanging 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.

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:na) permuting information bit positions of the groups according to predetermined interleaving rule; andb) 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.

A two-dimensional interleaving method comprising the steps of:nsequentially 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 withnC(i)=[g0×C(i−1)] mod p, i=1,2, . . . ,(p−2), and C(0)=1;calculating a minimum prime integer set {qi}(j=0,1,2, . . . ,R−1) by determiningng.c.d{qj,p−1}=1qj>6, qj>q(j-1) where g.c.d is a greatest common divider and q0=1;intra-row permuting {qj} usingnpP(j)=qj, j=0,1, . . . ,R−1where P(j) indicates a predetermined selecting order for selecting the R rows;when C=p+1, permuting sequences in a jth row in accordance withnCj(i)=C([i×pj] mod (p−1)),where j=0,1,2, . . . ,(R−1), i=0,1,2, . . . ,(p−2), Cj(p−1)=0, and Cj(p)=p,and if (K=C×R), then CR-1(p) is exchanged with CR-1(0),selecting R rows according to a predetermined order P(j);selecting an input sequence from the selected rows; andproviding the selected input sequence as read addresses for interleaving the information bits of the input frame.

A two-dimensional interleaving method comprising the steps of:nsequentially 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; andexchanging 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.

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:na) permuting the information bit positions of the groups according to predetermined interleaving rule; andb) 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.

A turbo encoder comprising:na first encoder configured for encoding a frame of K input information bits to generate first coded symbols;an interleaver configured fornsequentially 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, andreading out the information bits from the permuted R×C rectangular matrix, column by column, starting in the first row of the first column; anda 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.