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

• US 6,185,200 B1
• Filed: 03/13/1998
• Issued: 02/06/2001
• Est. Priority Date: 03/13/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Prasad, Mohit K.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US09/039,151
• Time in Patent Office: 1,061 Days
• Field of Search: 370/203, 370/320, 370/335, 370/342, 370/441, 370/487, 370/538, 370/479, 375/295, 375/130, 375/134, 375/135, 375/140, 375/145, 455/403, 455/422, 455/456
• US Class Current: 370/342
• 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/2764 Circuits therefore
• CPC Class Codes: H04L 1/0052 Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

De-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 interleaved symbol position to a corresponding de-interleaved symbol position, which is used to generate a de-interleaved symbol stream from the interleaved symbol stream. In one hardware implementation, the reverse-link de-interleaver of the present invention has an address generation unit made from two modulo counters and five muxes.

Claims

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

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

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

(c) generating a de-interleaved symbol stream from the interleaved symbol stream using the de-interleaved symbol positions.

2. The method of claim 1, wherein:

the closed-form expression is given by;

3. The method of claim 2, wherein:

for a reverse-link Access channel, the closed-form expression for the de-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 5, wherein the hardware implementation comprises:

(1) a modulo-18counter adapted to generate the 5-tuple (t₄, t₃, t₂, t₁, t₀) from the interleaved symbol position to generate the most significant bits of the de-interleaved symbol position;

(2) a modulo-32 or higher counter adapted to generate the 5-tuple (q₄, q₃, q₂, q₁, q₀) based on the carry bit from the modulo-18 counter; and

(3) a bit permutation unit adapted to generate the 5-tuple ( c₄, c₃, c₂, c₁, c₀) from the 5-tuple (q₄, q₃, q₂, q₁, q₀) based on the channel to generate the least significant bits of the de-interleaved symbol position.

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

bits from the 5-tuple (q₄, q₃, q₂, q₁, q₀) 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.

9. The method of claim 7, wherein the modulo-32 or higher counter generates the 5-tuple (q₄, q₃, q₂, q₁, q₀) based on the carry bit from the modulo-18 counter and the interleaved symbol position.

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

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

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

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

(c) means for generating a de-interleaved symbol stream from the interleaved symbol stream using the de-interleaved symbol positions.

11. The de-interleaver of claim 10, wherein:

the closed-form expression is given by;

12. The de-interleaver of claim 11, wherein:

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

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

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

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

16. The de-interleaver of claim 14, wherein the hardware implementation comprises:

(1) a modulo-18counter adapted to generate the5-tuple (t₄, t₃, t₂, t₁, t₀) from the interleaved symbol position to generate the most significant bits of the de-interleaved symbol position;

(2) a modulo-32 or higher counter adapted to generate the 5-tuple (q₄, q₃, q₂, q₁, q₀) based on the carry bit from the modulo-18 counter; and

(3) a bit permutation unit adapted to generate the 5-tuple (c₄, c₃, c₂, c₁, c₀) from the 5-tuple (q₄, q₃, q₂, q₁, q₀) based on the channel to generate the least significant bits of the de-interleaved symbol position.

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

bits from the 5-tuple (q₄, q₃, q₂, q₁, q₀) 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.

18. The de-interleaver of claim 16, wherein the modulo-32 or higher counter generates the 5-tuple (q₄, q₃, q₂, q₁, q₀) based on the carry bit from the modulo-18 counter and the interleaved symbol position.

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

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

(A) a symbol buffer; and

(B) an address generation unit adapted to generate symbol addresses for reading interleaved symbols from or writing de-interleaved symbols to the symbol buffer, wherein the address generation unit implements a closed-form expression relating each interleaved symbol position to a corresponding de-interleaved symbol position to generate a de-interleaved symbol position for each symbol in an interleaved symbol stream wherein the closed-form expression corresponds to two or more different sets of mathematical operations being applied to bits in a binary value representing each interleaved symbol position to generate bits in a binary value representing a corresponding de-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:

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

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

(1) a modulo-18counter adapted to generate the 5-tuple (t₄, t₃, t₂, t₁, t₀) from the interleaved symbol position to generate the most significant bits of the de-interleaved symbol position;

(2) a modulo-32 or higher counter adapted to generate the 5-tuple (q₄, q₃, q₂, q₁, q₀) based on the carry bit from the modulo-18 counter; and

(3) a bit permutation unit adapted to generate the 5-tuple (c₄, c₃, c₂, c₁, c₀) from the 5-tuple (q₄, q₃, q₂, q₁, q₀) based on the channel to generate the least significant bits of the de-interleaved symbol position.

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

bits from the 5-tuple (q₄, q₃, q₂, q₁, q₀) 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.

24. The integrated circuit of claim 22, wherein the modulo-32 or higher counter generates the 5-tuple (q₄, q₃, q₂, q₁, q₀) based on the carry bit from the modulo-18 counter and the interleaved symbol position.

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