Reverse-link interleaving for communication systems based on closed-form expressions

• US 6,295,287 B1
• Filed: 03/13/1998
• Issued: 09/25/2001
• Est. Priority Date: 03/13/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.)
• Inventors: Prasad, Mohit K.
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US09/039,157
• Time in Patent Office: 1,292 Days
• Field of Search: 370/203, 370/320, 370/335, 370/342, 370/441, 370/487, 370/538, 370/235, 375/130, 375/295, 375/135, 455/403, 455/422, 455/456
• US Class Current: 370/342
• CPC Class Codes: H03M 13/2707 Simple row-column interleaver, i.e. pure block interleaving
• CPC Class Codes: H03M 13/2764 Circuits therefore
• CPC Class Codes: H03M 13/6569 Implementation on processors, e.g. DSPs, or software implementations
• CPC Class Codes: H04J 13/00 Code division multiplex systems for frequency hopping H04B1/713
• CPC Class Codes: H04L 1/0043 Realisations of complexity reduction techniques, e.g. use of look-up tables
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27
• CPC Class Codes: H04L 1/12 by using return channel

Abstract

Interleaving of reverse-link channels is performed by implementing closed-form expressions that are equivalent to the table-based processing specified in the cdmaOne telecommunication specification. The implementation can be in either hardware or software or a combination of both. For each cdmaOne reverse-link channel, the closed-form expression relates each un-interleaved symbol position to a corresponding interleaved symbol position, which is used to generate an interleaved symbol stream from the un-interleaved symbol stream. In one hardware implementation, the reverse-link interleaver of the present invention has an address generation unit made from a modulo counter, five muxes, a multiplier, and an adder.

Claims

1. A method for interleaving a reverse-link channel of a communication system, comprising the steps of:

(a) receiving an un-interleaved symbol stream for the reverse-link channel;

(b) implementing, for each symbol in the un-interleaved symbol stream, a closed-form expression relating an un-interleaved symbol position for said each symbol to an interleaved symbol position in an interleaved symbol stream to generate the interleaved symbol position for said each symbol, wherein the closed-form expression corresponds to two or more different sets of mathematical operations being applied to two or more different sets of bits in a binary value representing the un-interleaved symbol position to generate bits in a binary value representing the interleaved symbol position, wherein;

the two or more different sets of mathematical operations comprise a first set of mathematical operations and a second set of mathematical operations different from the first set;

the first set of mathematical operations is applied to a first set of bits in the binary value representing the un-interleaved symbol position to generate a first partial result;

the second set of mathematical operations is applied to a second set of bits in the binary value representing the un-interleaved symbol position, different from the first set of bits, to generate a second partial result; and

the first and second partial results are combined in generating bits in the binary value representing the interleaved symbol position; and

(c) generating the interleaved symbol stream from the un-interleaved symbol stream using the interleaved symbol position for said each symbol.

2. The method of claim 1, wherein:

the closed-form expression is given by;

3. The method of claim 2, wherein:

if the reverse-link channel is a reverse-link Access channel, the closed-form expression for the interleaved symbol position N_OUT(ACCESS) is given by;

4. The method of claim 3, wherein the closed-form expression is implemented in software.

5. The method of claim 3, wherein the closed-form expression is implemented in hardware.

6. The method of claim 5, wherein the closed-form expression is implemented in a single integrated circuit.

7. The method of claim 6, wherein the closed-form expression is implemented in the single integrated circuit using XOR, AND, and OR gates.

8. The method of claim 5, wherein the hardware implementation comprises:

(1) a modulo-576 or higher counter adapted to generate the 10-tuple (c₉, c₈, c₇, c₆, c₅, c₄, c₃, c₂, c₁, c₀) from the un-interleaved symbol position;

(2) a bit permutation unit adapted to generate the 5-tuple (e₄, e₃, e₂, e₁, e₀) from the ₅-tuple (c₄, c₃, c₂, c₁, c₀) based on the channel;

(3) a multiply-by-18 block adapted to multiply a value corresponding to the 5-tuple (e₄, e₃, e₂, e₁, e₀) by 18; and

(4) an adder to add a value corresponding to a 5-tuple (c₉, c₈, c₇, c₆, c₅) and a value generated by the multiply-by-18 block to generate the interleaved symbol position.

9. The method of claim 8, wherein the bit permutation unit comprises five 5-input muxes, wherein:

bits from the 5-tuple (c₄, c₃, c₂, c₁, c₀) form the inputs to the five muxes; and

three control bits corresponding to the channel determine which input appears at the output of each mux.

25. The method of claim 1, wherein the closed-form expression is implementable without relying on any lookup tables.

10. An interleaver for interleaving a reverse-link channel of a communication system, comprising:

(a) means for receiving an un-interleaved symbol stream for the reverse-link channel;

(b) means for implementing, for each symbol in the un-interleaved symbol stream, a closed-form expression relating an un-interleaved symbol position for said each symbol to an interleaved symbol position in an interleaved symbol stream to generate the interleaved symbol position for said each symbol, wherein the closed-form expression corresponds to two or more different sets of mathematical operations being applied to two or more different sets of bits in a binary value representing the un-interleaved symbol position to generate bits in a binary value representing the interleaved symbol position, wherein;

the two or more different sets of mathematical operations comprise a first set of mathematical operations and a second set of mathematical operations different from the first set;

the first set of mathematical operations is applied to a first set of bits in the binary value representing the un-interleaved symbol position to generate a first partial result;

the second set of mathematical operations is applied to a second set of bits in the binary value representing the un-interleaved symbol position, different from the first set of bits, to generate a second partial result; and

the first and second partial results are combined in generating bits in the binary value representing the interleaved symbol position; and

(c) means for generating an interleaved symbol stream from the un-interleaved symbol stream using the interleaved symbol positions.

11. The interleaver of claim 10, wherein:

the closed-form expression is given by;

12. The interleaver of claim 11, wherein:

if the reverse-link channel is a reverse-link Access channel, the closed-form expression for the interleaved symbol position N_OUT(ACCESS) is given by;

13. The interleaver of claim 12, wherein the closed-form expression is implemented in software.

14. The interleaver of claim 12, wherein the closed-form expression is implemented in hardware.

15. The interleaver of claim 14, wherein the closed-form expression is implemented in a single integrated circuit.

16. The interleaver of claim 15, wherein the closed-form expression is implemented in the single integrated circuit using XOR, AND, and OR gates.

17. The interleaver of claim 14, wherein the hardware implementation comprises:

(1) a modulo-576 or higher counter adapted to generate the 10-tuple (c₉, c₈, c₇, c₆, c₅, c₄, c₃, c₂, c₁, c₀) from the un-interleaved symbol position;

(2) a bit permutation unit adapted to generate the 5-tuple (e₄, e₃, e₂, e₁, e₀) from the 5-tuple (c₄, c₃, c₂, c₁, c₀) based on the channel;

(3) a multiply-by-18 block adapted to multiply a value corresponding to the 5-tuple (e₄, e₃, e₂, e₁, e₀) by 18; and

(4) an adder to add a value corresponding to a 5-tuple (c₉, c₈, c₇, c₆, c₅) and a value generated by the multiply-by-18 block to generate the interleaved symbol position.

18. The interleaver of claim 17, wherein the bit permutation unit comprises five 5-input muxes, wherein:

bits from the 5-tuple (c₄, c₃, c₂, c₁, c₀) form the inputs to the five muxes; and

three control bits corresponding to the channel determine which input appears at the output of each mux.

26. The interleaver of claim 10, wherein the closed-form expression is implementable without relying on any lookup tables.

19. An integrated circuit having an interleaver for interleaving a reverse-link channel of a communication system, wherein the interleaver comprises:

(A) a symbol buffer; and

(B) an address generation unit adapted to generate symbol addresses for reading un-interleaved symbols from or writing interleaved symbols to the symbol buffer, wherein the address generation unit implements, for each symbol in an un-interleaved symbol stream, a closed-form expression relating an un-interleaved symbol position for said each symbol to an interleaved symbol position in an interleaved symbol stream to generate the interleaved symbol position for said each symbol, wherein the closed-form expression corresponds to two or more different sets of mathematical operations being applied to two or more different sets of bits in a binary value representing the un-interleaved symbol position to generate bits in a binary value representing the interleaved symbol position, wherein;

the two or more different sets of mathematical operations comprise a first set of mathematical operations and a second set of mathematical operations different from the first set;

the first set of mathematical operations is applied to a first set of bits in the binary value representing the un-interleaved symbol position to generate a first partial result;

the second set of mathematical operations is applied to a second set of bits in the binary value representing the un-interleaved symbol position, different from the first set of bits, to generate a second partial result; and

the first and second partial results are combined in generating bits in the binary value representing the interleaved symbol position.

20. The integrated circuit of claim 19, wherein:

the closed-form expression is given by;

21. The integrated circuit of claim 20, wherein:

if the reverse-link channel is a reverse-link Access channel, the closed-form expression for the interleaved symbol position N_OUT(ACCESS) is given by;

22. The integrated circuit of claim 21, wherein the closed-form expression is implemented using XOR, AND, and OR gates.

23. The integrated circuit of claim 21, wherein the address generation unit comprises:

(1) a modulo-576 or higher counter adapted to generate the 10-tuple (c₉, c₈, c₇, c₆, c₅, c₄, c₃, c₂, c₁, c₀) from the un-interleaved symbol position;

(2) a bit permutation unit adapted to generate the 5-tuple (e₄, e₃, e₂, e₁, e₀) from the 5-tuple (c₄, c₃, c₂, c₁, c₀) based on the channel;

(3) a multiply-by-18 block adapted to multiply a value corresponding to the 5-tuple (e₄, e₃, e2, e₁, e₀) by 18; and

(4) an adder to add a value corresponding to a 5-tuple (c₉, c₈, c₇, c₆, c₅) and a value generated by the multiply-by-18 block to generate the interleaved symbol position.

24. The integrated circuit of claim 23, wherein the bit permutation unit comprises five 5-input muxes, wherein:

bits from the 5-tuple (c₄, c₃, c₂, c₁, c₀) form the inputs to the five muxes; and

three control bits corresponding to the channel determine which input appears at the output of each mux.

27. The integrated circuit of claim 19, wherein the closed-form expression is implementable without relying on any lookup tables.