Enhanced channel interleaving for optimized data throughput

• US 6,987,778 B2
• Filed: 05/22/2001
• Issued: 01/17/2006
• Est. Priority Date: 05/22/2001
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Black, Peter J., Sindhushayana, Nagabhushana
• Primary Examiner(s): Sam, Phirin
• Application Number:
  US09/863,196
• Publication Number:
  US 20030053435A1
• Time in Patent Office: 1,701 Days
• Field of Search: 370/328, 370/329, 370/335, 370/341, 370/342, 370/394, 370/395.4, 370/395.41, 370/437, 370/441, 370/465, 370/468, 370/479, 370/536, 370/320, 370/393, 714/702, 714/755, 714/756, 714/784, 714/790, 714/791
• US Class Current: 370/468
• CPC Class Codes: H04L 1/0002 by adapting the transmission rate
• CPC Class Codes: H04L 1/0003 by switching between different modulation schemes
• CPC Class Codes: H04L 1/0007 by modifying the frame length
• CPC Class Codes: H04L 1/0009 by adapting the channel coding H04L1/1812 takes precedence
• CPC Class Codes: H04L 1/0025 Transmission of mode-switching indication
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0059 Convolutional codes
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes
• CPC Class Codes: H04L 1/0069 Puncturing patterns
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27
• CPC Class Codes: H04L 1/0083 Formatting with frames or packets; Protocol or part of protocol for error control
• CPC Class Codes: H04L 1/18 Automatic repetition systems, e.g. Van Duuren systems
• CPC Class Codes: H04L 5/0048 Allocation of pilot signals, i.e. of signals known to the receiver

Abstract

In a transmission scheme wherein multi-slot packet transmissions to a remote station can be terminated by an acknowledgment signal from the remote station, code symbols can be efficiently packed over the multi-slot packet so that the remote station can easily decode the data payload of the multi-slot packet by decoding only a portion of the multi-slot packet. Hence, the remote station can signal for the early termination of the multi-slot packet transmission, which thereby increases the data throughput of the system.

Claims

1. An apparatus for increasing data throughput of a wireless communication system, comprising:

a scheduler unit configured to schedule a multi-slot packet transmission to a remote station in accordance with a scheduling algorithm, wherein the scheduling algorithm uses a data request message from the remote station to determine an initial set of transmission parameters and uses an acknowledgment signal from the remote station to determine a subsequent set of transmission parameters; and

a channel interleaver configured to perform a permutation of a plurality of data symbols separately from a permutation of a plurality of parity symbols, wherein the scheduler unit schedules the plurality of permuted data symbols for transmission at the beginning of the multi-slot packet transmission and schedules the plurality of permuted parity symbols at the end of the multi-slot packet transmission.

2. The apparatus of claim 1, wherein the scheduler unit schedules the multi-slot packet to carry a variable amount of the plurality of permuted parity symbols in each slot, so that the beginning of the multi-slot packet carries little or no portion of the plurality of permuted parity symbols and the end of the multi-slot packet carries most or all of the plurality of permuted parity symbols.

3. The apparatus of claim 1, wherein the channel interleaver comprises:

a look-up table, wherein the look-up table comprise a sequence of addresses defining a permutation for a plurality of input symbols; and

a control processor coupled to the look-up table for reading the plurality of input symbols in accordance with the sequence of addresses in the look-up table in order to generate a sequence of output symbols.

4. The apparatus of claim 1, wherein the channel interleaver comprises:

a memory element; and

a control element coupled to the memory element, wherein the control element is configured to store and to reorder the plurality of data symbols in a representation of a rectangular array of K rows and M columns in the memory element, wherein storing occurs in a row-wise manner from left to right and from top to bottom, and the reordering occurs by;

end-around shifting the symbols of each column by a predetermined amount;

switching the j^th column with the corresponding bit-reversed j^th column, wherein j=0, . . . , M−

1; and

reading the rectangular array in a column-wise manner from top to bottom and from left to right.

5. The apparatus of claim 4, wherein the control element is further configured to store and to reorder the plurality of parity symbols in a second representation of a rectangular array of K rows and M columns in the memory element, wherein the storing occurs in a row-wise manner from left to right and from top to bottom, and the reordering occurs by:

end-around shifting the symbols of each column by a second predetermined amount;

switching the j^th column with the corresponding bit-reversed j^th column, wherein j=0, . . . , M−

1; and

reading the second rectangular array in a column-wise manner from top to bottom and from left to right.

6. The apparatus of claim 1, wherein the channel interleaver comprises:

a memory element; and

a control element coupled to the memory element, wherein the control element is configured to store and to reorder the plurality of data symbols in a representation of a rectangular array of K rows and M columns in the memory element, wherein the storing occurs in a row-wise manner from left to right and from top to bottom, and the reordering occurs by;

switching the j^th column with the corresponding bit-reversed j^th column, wherein j=0, . . . , M−

1;

swapping a chosen group of bits with a designated swapping partner, wherein the designated swapping partner is determined in accordance with a predetermined swapping pattern stored in the memory element; and

reading the rectangular array in a column-wise manner from top to bottom and from left to right.

7. The apparatus of claim 1, wherein the channel interleaver comprises:

a memory element; and

a control element coupled to the memory element, wherein the control element is configured to store and to reorder the plurality of parity symbols in a representation of a rectangular array of K rows and M columns in the memory element, wherein the storing occurs in a row-wise manner from left to right and from top to bottom, and the reordering occurs by;

switching the j^th column with the corresponding bit-reversed j^th column, wherein j=0, . . . , M−

1;

swapping a chosen group of bits with a designated swapping partner, wherein the designated swapping partner is determined in accordance with a predetermined swapping pattern in the memory element; and

reading the rectangular array in a column-wise manner from top to bottom and from left to right.

8. The apparatus of claim 6, wherein the memory element stores a plurality of swapping patterns.

9. The apparatus of claim 8, wherein the predetermined swapping pattern is chosen by the scheduling unit in accordance with the initial set of transmission parameters.

10. The apparatus of claim 7, wherein the memory element stores a plurality of swapping patterns.

11. The apparatus of claim 10, wherein the predetermined swapping pattern is chosen by the scheduling unit in accordance with the initial set of transmission parameters.

12. The apparatus of claim 1, wherein the transmission parameters are stored in a look-up table that can be accessed by the scheduling unit.

13. The apparatus of claim 1, further comprising a turbo encoder for encoding data bits into a plurality of data symbols and a plurality of parity symbols for subsequent input into the channel interleaver, wherein the turbo encoder comprises:

a first constituent encoder;

a second constituent encoder operating in parallel with the first constituent encoder, wherein the first constituent encoder and the second constituent encoder are configured in accordance with a recurrence relation;

G(D)=[1, n₀(D)/d(D), n₁(D)/d(D)],

wherein d(D)=1+D²+D³, n₀(D)=1+D+D³, and n₁(D)=1+D+D²+D³, and a plurality of systematic bits is generated by clocking both the first constituent encoder and the second constituent encoder at the same time, whereas a plurality of parity bits is generated by clocking the first constituent encoder and the second constituent encoder at different times;

a turbo interleaver situated in front of the second constituent encoder and parallel to the first constituent encoder; and

a symbol generation element for puncturing and repeating the outputs of the first constituent encoder and the second constituent encoder in order to generate the plurality of data symbols and the plurality of parity symbols.

14. The apparatus of claim 13, further comprising a linear shift feedback register (LSFR), wherein the output of the LSFR is XORed with the plurality of data symbols and the plurality of parity symbols from the turbo encoder to produce a plurality of scrambled data symbols and a plurality of scrambled parity symbols for input into the channel interleaver.

15. An apparatus for generating ordered sequences that can be transmitted in multi-slot packets in a wireless communication system, the apparatus comprising a scheduling unit configured to schedule a multi-slot racket transmission to a remote station in accordance with a scheduling algorithm, and a channel interleaver configured to receive a plurality of systematic bits and a plurality of parity bits and to generate an output sequence, wherein the generating the output sequence comprises:

demultiplexing the plurality of systematic bits and the plurality of parity bits into a plurality of sequences, wherein the plurality of systematic bits and the plurality of parity bits are sequentially distributed among the plurality of sequences;

reordering the plurality of sequences;

forming a plurality of blocks from the reordered plurality of sequences; and

permuting elements of each block of the plurality of blocks, wherein the output sequence comprises permuted elements from each block of the plurality of blocks.

16. The apparatus of claim 15, wherein the channel interleaver further permutes elements of each block by:

end-around shifting downward each element in each column of each block; and

switching the order of the columns within each block.

17. The apparatus of claim 15, wherein the channel interleaver further permutes elements of each block by swapping a plurality of bit groups with a corresponding plurality of bit groups, wherein swapping is performed upon those bit groups that occupy selected locations within each block.

18. The apparatus of claim 16, further comprising a symbol generation element, the symbol generation element for puncturing the output sequence in accordance with a predetermined puncture pattern.

19. The apparatus of claim 18, wherein the symbol generation element is further for repeating a portion of the output sequence in accordance with a predetermined repetition pattern.

20. The apparatus of claim 17, further comprising a symbol generation element, the symbol generation element for puncturing the output sequence in accordance with a predetermined puncture pattern.

21. The apparatus of claim 20, wherein the symbol generation element is further for repeating a portion of the output sequence in accordance with a predetermined repetition pattern.

22. A method for interleaving data and parity symbols for transmission from a base station to a remote station in a wireless communication system, comprising:

permuting a plurality of data symbols to form a first permutation block;

permuting a plurality of parity symbols to form a second permutation block;

generating an output sequence by sequentially reading elements of the first permutation block and the second permutation block; and

scheduling a multi-slot packet transmission from the base station to the remote station in accordance with a scheduling algorithm, wherein the scheduling packs data symbols of the output sequence at the beginning of the multi-slot packet and parity symbols of the output sequence at the end of the multi-slot packet.

23. The method of claim 22, wherein generating the output sequence is followed by truncating the output sequence in accordance with a desired code symbol rate.

24. The method of claim 22, wherein the permuting of the plurality of data symbols to form a first permutation block is performed by:

entering the plurality of data symbols into a rectangular array with K rows and M columns, starting from the top row and continuing from left to right;

end-around shifting the symbols of each column of the rectangular array downward by a predetermined value; and

reordering the columns of the rectangular array by switching the j_th column of the rectangular array with the bit-reversed j^th column, wherein j=0, 1, . . . , M−

1.

25. The method of claim 22, wherein the permuting of the plurality of parity symbols to form a second permutation block is performed by:

entering the plurality of parity symbols into a rectangular array with K rows and M columns, starting from the top row and continuing from left to right;

end-around shifting the symbols of each column of the rectangular array downward by a predetermined value; and

reordering the columns of the rectangular array by switching the j^th column of the rectangular array with the bit-reversed j^th column, wherein j=0, 1, . . . , M−

1.

26. The method of claim 22, wherein the permuting of the plurality of data symbols to form a first permutation block is performed by:

entering the plurality of data symbols into a rectangular array with K rows and M columns, starting from the top row and continuing from left to right;

reordering the columns of the rectangular array by switching the j^th column of the rectangular array with the bit-reversed j^th column, wherein j=0, 1, . . . , M−

1; and

swapping groups of bits in accordance with a swapping pattern.

27. The method of claim 22, wherein the permuting of the plurality of parity symbols to form a second permutation block is performed by:

entering the plurality of parity symbols into a rectangular array with K rows and M columns, starting from the top row and continuing from left to right;

reordering the columns of the rectangular array by switching the j^th column of the rectangular array with the bit-reversed j^th column, wherein j=0, 1, . . . , M−

1; and

swapping groups of bits in accordance with a swapping pattern.

28. A method for increasing the data throughput of a base station to a remote station, comprising:

generating a plurality of data symbols and a plurality of parity symbols;

interleaving the plurality of data symbols separately from the plurality of parity symbols to form an output sequence in which the plurality of interleaved data symbols are located at the beginning of the output sequence and the plurality of interleaved parity symbols are located at the end of the output sequence;

scheduling a multi-slot packet transmission from the base station to the remote station in accordance with a scheduling algorithm; and

transmitting the output sequence over a multi-slot packet, wherein the remote station can signal for the termination of the multi-slot packet transmission, thereby increasing the data throughput of the base station.

29. In a communication system, a method for transmitting data at a high data rate, comprising:

transmitting a data rate message from a remote station to a base station;

generating a plurality of data symbols and a plurality of parity symbols at the base station;

interleaving the plurality of data symbols separately from the plurality of parity symbols to form an output sequence in which the plurality of interleaved data symbols are located at the beginning portion of the output sequence and the plurality of interleaved parity symbols are located at the end portion of the output sequence;

partitioning the output sequence into a plurality of blocks comprising consecutive symbols of the output sequence;

storing the plurality of blocks in a buffer;

transmitting a first block of the plurality of blocks from the base station to the remote station;

transmitting a negative acknowledgment from the remote station to the base station if the remote station cannot decode the received first block, else transmitting a positive acknowledgment if the remote station can decode the received first block;

if the base station receives the negative acknowledgment, then transmitting the next block to the remote station; and

transmitting successive blocks from the plurality of blocks in response to negative acknowledgments from the remote station until a positive acknowledgment is received or until all blocks have been transmitted.

30. The method of claim 29, wherein if a negative acknowledgment arrives from the remote station after the last block of the plurality of blocks is transmitted from the base station, then retrieving the plurality of blocks from the buffer and retransmitting the plurality of blocks in a successive manner in response to negative acknowledgments.