Method and apparatus for deinterleaving interleaved data stream in a communication system

• US 20040114596A1
• Filed: 10/29/2003
• Published: 06/17/2004
• Est. Priority Date: 10/29/2002
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Ahn, Seong-Woo, Kim, Min-Goo, Ha, Sang-Hyuck, Heo, Seo-Weon, Yu, Nam-Yul
• Granted Patent: US 7,702,970 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H03M 13/271 Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column permutations
• CPC Class Codes: H03M 13/275 Interleaver wherein the permutation pattern is obtained using a congruential operation of the type y=ax+b modulo c
• CPC Class Codes: H03M 13/276 Interleaving address generation
• CPC Class Codes: H03M 13/2764 Circuits therefore
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

An apparatus and method for reading written symbols by deinterleaving to decode a written encoder packet in a receiver for a mobile communication system supporting turbo coding and interleaving, such that a turbo-coded/interleaved encoder packet has a bit shift value m, an up-limit value J and a remainder R, and a stream of symbols of the encoder packet is written in order of column to row. The apparatus and method perform the operations of generating an interim address by bit reversal order (BRO) assuming that the remainder R is 0 for the received symbols; calculating an address compensation factor for compensating the interim address in consideration of a column formed with the remainder; and generating a read address by adding the interim address and the address compensation factor for a decoding-required symbol, and reading a symbol written in the generated read address.

Claims

1. A method for reading code symbols by deinterleaving to decode a encoder packet in a receiver for a mobile communication system supporting interleaving, wherein an interleaved encoder packet has (2^m*J+R) bits, a bit shift value m, an up-limit value J and a remainder R, the method comprising the steps of:

generating an interim address by bit reversal order (BRO) operation on an index of a code symbol;

calculating an address compensation factor for compensating the interim address in consideration of the remainder; and

generating a read address by adding the interim address to the address compensation factor for the code symbol, and reading the code symbol written in the generated read address.

2. The method of claim 1, wherein the interim address generation step comprises the step of generating the interim address by excluding the (J+1)^th column when the number of the code symbols of the (J+1) column is less than a half of 2^m code symbols, and generating the interim address by including the (J+1)^th column when the number of the code symbols of the (J+1)^th last column is more than a half of 2^mcode symbols.

3. The method of claim 2, wherein the address compensation factor calculation step comprises the step of increasing the address compensation factor by one each time a code symbol appears in the (J+1)^th last column when the (J+1)^th last column is less than a half of 2^m code symbols, and decreasing the address compensation factor by one each time a code symbol is excluded from the (J+1)^th last column when the (J+1)^th last column is more than a half of 2^m code symbols.

4. The method of claim 1, wherein if a size of the subblock is 408, the read address is generated in accordance with the equation

5. The method of claim 1, wherein if a size of the subblock is 792, the read address is generated in accordance with the equation

6. The method of claim 1, wherein if a size of the subblock is 1560, the read address is generated in accordance with the equation

7. The method of claim 1, wherein if a size of the subblock is 3096, the read address is generated in accordance with the equation

8. The method of claim 1, wherein if a size of the subblock is 6168, the read address is generated in accordance with the equation

9. The method of claim 1, wherein if a size of the subblock is 12312, the read address is generated in accordance with the equation

10. The method of claim 1, wherein if a size of the subblock is 2328, the read address is generated in accordance with the equation

11. The method of claim 1, wherein if a size of the subblock is 3864, the read address is generated in accordance with the equation

12. The method of claim 1, wherein if a size of the subblock is 4632, the read address is generated in accordance with the equation

13. The method of claim 1, wherein if a size of the subblock is 9240, the read address is generated in accordance with the equation

14. The method of claim 1, wherein if a size of the subblock is 15384, the read address is generated in accordance with the equation

15. The method of claim 1, wherein the address compensation factor calculation step comprises the step of calculating an address compensation factor by the following equation when the (J+1)^th last column is less than a half or more of 2^m code symbols;

16. The method of claim 1, wherein the address compensation factor calculation step comprises the step of calculating an address compensation factor by the following equation when the (J+1)^th last column is more than a half of 2^m code symbols;

17. The method of claim 1, wherein the step of generating the interim address further comprising:

performing BRO operation of column indexe of the code symbol indexe; and

adding the BRO operated column indexe and a column index of the code symbol indexe;

18. The method of claim 17, wherein the BRO operation of column indexe of the code symbol indexes is performed by BRO operation of column index generated by dividing the code symbol indexes k into 2^m.

19. The method of claim 17, wherein the column index is a quotient generated by dividing the code symbol indexes k into 2^m.

20. An apparatus for reading code symbols by deinterleaving in a receiver for a communication system supporting interleaving, wherein an interleaved encoder packet has (2{circumflex over ( 

)}m*J+R) bits, a bit shift value m, an up-limit value J and a remainder R, the receiver including a buffer for writing symbols of the encoder packet and a channel decoder for decoding the written encoder packet, the apparatus comprising;

an interim address generator for generating an interim address by performing a bit reversal order (BRO) operation on an index of a code symbol requested by the channel decoder;

an address compensator for calculating an address compensation factor for compensating the interim address in consideration of the remainder; and

an adder for generating a read address for reading the code symbol requested by the channel decoder from the buffer, by adding the address compensation factor to the interim address.

21. The apparatus of claim 20, wherein the interim address generator comprises:

a first divider for outputting a maximum integer not exceeding a quotient obtained by dividing an index of a code symbol requested by the channel decoder by 2^m;

a BRO operator for grouping bits obtained by dividing the code symbol index by 2^m, and performing a BRO operation on row indexes for symbols of each group;

a multiplier for multiplying an output of the BRO operator by (J<sup>−

1</sup>); and

a first adder for calculating the interim address by adding an output of the multiplier to an output of the first divider.

22. The apparatus of claim 21, wherein if a size of the encoder packet is any one of 408, 792, 1560, 3096, 6168 and 12312, the address compensator comprises:

a second adder for adding 2<sup>m−

5−

1</sup> to an output of the BRO operator;

a second divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the second adder by 2<sup>m−

5</sup>;

a third divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the second adder by 2<sup>m−

3</sup>; and

an adder for calculating the address compensation factor by subtracting an output of the third divider from an output of the second divider.

23. The apparatus of claim 21, wherein if a size of the encoder packet is 2328, the address compensator comprises:

a second adder for adding 3 to an output of the BRO operator;

a second divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the second adder by 4;

a third adder for adding 29 to an output of the BRO operator;

a third divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the third adder by 32;

a fourth divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the third adder by 128; and

a fourth adder for calculating the address compensation factor by adding an output of the third divider to an output of the second divider and then subtracting an output of the fourth divider from the addition result.

24. The apparatus of claim 20, wherein a size of the encoder packet is 3864, the interim address generator comprises:

a first divider for outputting a maximum integer not exceeding a quotient obtained by dividing an index of a code symbol requested by the channel decoder by 2^m;

a BRO operator for grouping bits obtained by dividing the code symbol index by 2^m, and performing a BRO operation on row indexes for symbols of each group;

a multiplier for multiplying an output of the BRO operator by J; and

a first adder for calculating the interim address by adding an output of the multiplier to an output of the first divider; and

the address compensator comprises;

a second divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the BRO operator by 8;

a second adder for adding 56 to an output of the BRO operator;

a third divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the second adder by 64;

a fourth divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the second adder by 256; and

a third adder for calculating the address compensation factor by subtracting an output of the second divider and an output of the fourth divider from an output of the third divider.

25. The apparatus of claim 21, wherein if a size of the encoder packet is 4632, the address compensator comprises:

a second adder for adding 3 to an output of the BRO operator;

a second divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the second adder by 4;

a third adder for adding 61 to an output of the BRO operator;

a third divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the third adder by 64;

a fourth divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the third adder by 256; and

a fourth adder for calculating the address compensation factor by adding an output of the third divider to an output of the second divider and then subtracting an output of the fourth divider from the addition result.

26. The apparatus of claim 21, wherein if a size of the encoder packet is 9240, the address compensator comprises:

a second adder for adding 3 to an output of the BRO operator;

a second divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the second adder by 4;

a third adder for adding 125 to an output of the BRO operator;

a third divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the third adder by 128;

a fourth divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the third adder by 512; and

a fourth adder for calculating the address compensation factor by adding an output of the third divider to an output of the second divider and then subtracting an output of the fourth divider from the addition result.

27. The apparatus of claim 20, wherein if a size of the encoder packet is 15384, the interim address generator comprises:

a first divider for outputting a maximum integer not exceeding a quotient obtained by dividing an index of a code symbol requested by the channel decoder by 2^m;

a BRO operator for grouping bits obtained by dividing the code symbol index by 2^m, and performing a BRO operation on row indexes for symbols of each group;

a multiplier for multiplying an output of the BRO operator by J; and

a first adder for calculating the interim address by adding an output of the multiplier to an output of the first divider; and

the address compensator comprises;

a second divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the BRO operator by 8;

a second adder for adding 248 to an output of the BRO operator;

a third divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the second adder by 256;

a fourth divider for outputting a maximum integer not exceeding a quotient obtained by dividing an output of the second adder by 1024; and

a third adder for calculating the address compensation factor by subtracting an output of the second divider and an output of the fourth divider from an output of the third divider.

28. A method for performing addressing so as to generate deinterleaved symbols from an input buffer that performs a bit reversal order (BRO) operation on column indexes of symbols in 2^m columns among (2^m×

J+R) symbols, where 2^m is the number of columns, J is the number of columns and R is the number of remaining symbols in a (J+1)^th column, and sequentially writes interleaved symbols corresponding to code symbol indexes k, the method comprising the steps of;

performing BRO operation of column indexes of the code symbol indexes;

generating a interim addresses by adding the BRO operated column indexes to a column index of the code symbol indexes;

generating address compensation factor for compensating addresses of remaining symbols from the code symbol index of (J+1)^th; and

generating addresses by adding the interim address values and the address compensation factors, and applying the addresses to the buffer.

29. The method of claim 28, wherein the interim address generation step comprises the step of generating the interim address by excluding the (J+1)^th column if the (J+1)^th column having the R remaining symbols is less than 2^m code symbols, and generating the interim address by including the (J+1)^th column if the (J+1)^th column has more than half of 2^m code symbols.

30. The method of claim 28, wherein the BRO operation of column indexes of the code symbol indexes is performed by BRO operation of column index generated by dividing the code symbol indexes k into 2′

.

31. The method of claim 28, wherein the column index is a quotient generated by dividing the code symbol indexes k into 2^m.

32. An apparatus for performing addressing so as to generate deinterleaved symbols from an input buffer that performs a bit reversal order (BRO) operation on column indexes of symbols in 2^m columns among (2^m×

J+R) symbols, where 2^m is the number of columns, J is the number of columns and R is the number of remaining symbols in a (J+1)^th column, and sequentially writes interleaved symbols corresponding to code symbol indexes k, the apparatus comprising;

an interim address generator for performing BRO operation of column indexes of the code symbol indexes and adding the BRO operated column indexes to a column index of the code symbol indexes;

an address compensation factor calculator for generating address compensation factor for compensating addresses of remaining symbols from the code symbol index of (J+1)^th column; and

an adder for adding output of the interim address generator and output of the address compensation factor calculator.