Enhanced channel interleaving for optimized data throughput

• US 7,953,062 B2
• Filed: 01/12/2006
• Issued: 05/31/2011
• 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:
  US11/332,722
• Publication Number:
  US 20060114910A1
• Time in Patent Office: 1,965 Days
• Field of Search: None
• US Class Current: 370/345
• 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 generating ordered sequences to be transmitted in multi-slot packets in a wireless communication system, the apparatus comprising a channel interleaver configured to receive a plurality of systematic bits and a plurality of parity bits and to generate an output sequence, comprising:

the channel interleaver to demultiplex 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;

reorder the plurality of sequences;

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

permute elements of each block, wherein the output sequence comprises the permuted elements from each block, 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.

2. The apparatus of claim 1, further comprising a symbol generation element, the symbol generation element configured to puncture the output sequence in accordance with a predetermined puncture pattern.

3. The apparatus of claim 2, wherein the symbol generation element is further configured to repeat a portion of the output sequence in accordance with a predetermined repetition pattern.

4. An apparatus for generating ordered sequences to be transmitted in multi-slot packets in a wireless communication system, the apparatus comprising a channel interleaver configured to receive a plurality of systematic bits and a plurality of parity bits and to generate an output sequence, comprising:

the channel interleaver to demultiplex 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;

reorder the plurality of sequences;

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

permute elements of each block, wherein the output sequence comprises the permuted elements from each block, wherein the channel interleaver further permutes elements of each block by swapping a plurality of bit groups with a corresponding plurality of bit groups, the swapping being performed upon those bit groups that occupy selected locations within each block.

5. The apparatus of claim 4, further comprising a symbol generation element, the symbol generation element configured to puncture the output sequence in accordance with a predetermined puncture pattern.

6. The apparatus of claim 5, wherein the symbol generation element is further configured to repeat a portion of the output sequence in accordance with a predetermined repetition pattern.

32. The apparatus of claim 4, wherein the channel interleaver is further configured to perform the swapping so as to distribute the systematic bits and parity bits uniformly along the output sequence.

33. The apparatus of claim 4, further comprising a modulator coupled to the channel interleaver, the modulator being configured to perform modulation upon the output sequence (of interleaved symbols) to produce modulation a modulation pattern, wherein the channel interleaver is configured to perform the swapping in accordance with a type of modulation scheme so that the systematic bits and parity bits are distributed uniformly in the modulation pattern.

7. An apparatus for generating ordered sequences to be transmitted in multi-slot packets in a wireless communication system, the apparatus comprising a channel interleaver configured to receive a plurality of systematic bits and a plurality of parity bits and to generate an output sequence, comprising:

the channel interleaver to demultiplex the plurality of systematic bits and the plurality of parity hits 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;

reorder the plurality of sequences;

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

permute elements of each block, wherein the output sequence comprises the permuted elements from each block, wherein the channel interleaver further permutes elements of each block by;

entering the plurality of sequences 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 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.

8. An apparatus adapted for wireless communications, comprising:

a memory; and

a processor operably connected to said memory, said processor configured to;

receive a plurality of systematic bits and a plurality of parity hits;

demultiplex 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;

reorder the plurality of sequences;

form a plurality of blocks from the reordered plurality of sequences;

permute elements of each block; and

generate an output sequence based on the permuted elements from each block.

9. The apparatus of claim 8, wherein the processor is further configured to permute 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.

10. The apparatus of claim 9, wherein the processor is further configured to puncture the output sequence in accordance with a predetermined puncture pattern.

11. The apparatus of claim 10, wherein the processor is further configured to repeat a portion of the output sequence in accordance with a predetermined repetition pattern.

12. The apparatus of claim 8, wherein the processor is further configured to permute elements of each block by swapping a plurality of bit groups with a corresponding plurality of bit groups, the swapping being performed upon those bit groups that occupy selected locations within each block.

13. The apparatus of claim 12, wherein the processor is further configured to puncture the output sequence in accordance with a predetermined puncture pattern.

14. The apparatus of claim 13, wherein the processor is further configured to repeat a portion of the output sequence in accordance with a predetermined repetition pattern.

15. The apparatus of claim 8, wherein the processor is further configured to:

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

reorder 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

swap groups of bits in accordance with a swapping pattern.

16. An apparatus adapted for wireless communications, comprising:

a memory; and

a processor operably connected to said memory, said processor configured to;

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

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

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

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

17. The apparatus of claim 16, wherein the processor is further configured to truncate the output sequence in accordance with a desired code symbol rate.

18. The apparatus of claim 16, wherein the processor is further configured to permute the plurality of data symbols to form a first permutation block 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 hit-reversed j^th column, wherein j=0, 1, . . . , M−

1.

19. The apparatus of claim 16, wherein the processor is further configured to permute the plurality of parity symbols to form a second permutation block 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 column of the rectangular array with the bit-reversed j^th column, wherein j=0, 1, . . . , M−

1.

20. The apparatus of claim 16, wherein the processor is further configured to permute the plurality of data symbols to form a first permutation block 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 hits in accordance with a swapping pattern.

21. The apparatus of claim 16, wherein the processor is further configured to permute the plurality of parity symbols to form a second permutation block 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

22. A method for symbol transmission comprising:

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

interleaving said plurality of data symbols;

interleaving said plurality of parity symbols separately from said plurality of data symbols;

transmitting said interleaved data and parity symbols over a plurality of slots;

transmitting each of said plurality of data symbols during the first slot of said plurality of slots; and

terminating said transmitting over said plurality of slots in response to receiving an acknowledgment signal,

wherein said generating a plurality of data symbols and a plurality of parity symbols comprises turbo encoding said plurality of data symbols, and

wherein said turbo encoding said plurality of data symbols comprises;

generating a first plurality of parity symbols from said plurality of data symbols using a first constituent encoder;

interleaving said plurality of data symbols using a turbo interleaver;

generating a second plurality of parity symbols from said plurality of interleaved data symbols using a second constituent encoder;

selectively puncturing and repeating said plurality of data symbols and said plurality of parity symbols.

23. The method of claim 22, wherein said turbo encoding further comprises:

generating a third plurality of parity symbols using said first constituent encoder;

generating a fourth plurality of parity symbols using said second constituent encoder;

interleaving said first and second plurality of parity symbols separately from said third and fourth plurality of parity symbols; and

transmitting each of said first and second plurality of parity symbols before transmitting said third and fourth plurality of parity symbols over said plurality of slots.

24. A method for symbol transmission comprising:

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

interleaving said plurality of data symbols;

interleaving said plurality of parity symbols separately from said plurality of data symbols;

transmitting said interleaved data and parity symbols over a plurality of slots;

transmitting each of said plurality of data symbols during the first slot of said plurality of slots; and

terminating said transmitting over said plurality of slots in response to receiving an acknowledgment signal,

wherein said interleaving comprises re-ordering the symbols of a symbol sequence, and further comprising;

assigning each symbol an address, wherein consecutive symbols have consecutive addresses;

assigning each symbol a column index;

re-ordering the symbols such that;

symbols having a lower column index are ordered before symbols having a higher column index;

for symbols having the same column index, symbols having a lower address are ordered before symbols having a higher address.

25. The method of claim 24, wherein said assigning each symbol a column index comprises setting the column index equal to the greatest integer smaller than or equal to the quotient of dividing the address of said symbol by a column number parameter.

26. The method of claim 25, wherein said turbo encoding said plurality of data symbols comprises:

generating a first plurality of parity symbols from said plurality of data symbols using a first constituent encoder;

interleaving said plurality of data symbols using a turbo interleaver;

generating a second plurality of parity symbols from said plurality of interleaved data symbols using a second constituent encoder;

selectively puncturing and repeating said plurality of data symbols and said plurality of parity symbols.

29. The method of claim 24, wherein said interleaving comprises re-ordering the symbols of a symbol sequence, said permuting comprising:

assigning each symbol an address, wherein consecutive symbols have consecutive addresses;

assigning each symbol a column index;

re-ordering the symbols such that;

symbols having a lower column index are ordered before symbols having a higher column index;

for symbols having the same column index, symbols having a lower address are ordered before symbols having a higher address.

30. The apparatus of claim 29, wherein said means for assigning each symbol a column index comprises setting the column index equal to the greatest integer smaller than or equal to the quotient of dividing the address of said symbol by a column number parameter.

31. The apparatus of claim 29, wherein said means for assigning each symbol a column index comprises setting a first index equal to the greatest integer smaller than or equal to the quotient of dividing the address of said symbol by a column number parameter, and means for setting the column index equal to the bit-reversed value of said first index, wherein said bit reversal is performed over a number of bits corresponding to said column number parameter.

27. An apparatus for symbol transmission comprising:

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

means for interleaving said plurality of data symbols;

means for interleaving said plurality of parity symbols separately from said plurality of data symbols;

means for transmitting said interleaved data and parity symbols over a plurality of slots;

means for transmitting each of said plurality of data symbols during the first slot of said plurality of slots; and

means for terminating said transmitting over said plurality of slots in response to receiving an acknowledgment signal,

wherein said means for generating a plurality of data symbols and a plurality of parity symbols comprises means for turbo encoding said plurality of data symbols, and

wherein said means for turbo encoding said plurality of data symbols comprises;

means for generating a first plurality of parity symbols from said plurality of data symbols using a first constituent encoder;

means for interleaving said plurality of data symbols using a turbo interleaver;

means for generating a second plurality of parity symbols from said plurality of interleaved data symbols using a second constituent encoder;

means for selectively puncturing and repeating said plurality of data symbols and said plurality of parity symbols.

28. The apparatus of claim 27, wherein said means for turbo encoding further comprises:

means for generating a third plurality of parity symbols using said first constituent encoder;

means for generating a fourth plurality of parity symbols using said second constituent encoder;

means for interleaving said first and second plurality of parity symbols separately from said third and fourth plurality of parity symbols; and

means for transmitting each of said first and second plurality of parity symbols before transmitting said third and fourth plurality of parity symbols over said plurality of slots.