Methods and apparatus for interleaving in OFDM/OFDMA systems

1. A method of interleaving a binary vector for transmission by an OFDM/OFDMA transmitter, comprising:

generating a forward error correction encoded binary vector from binary data to be transmitted;

reshaping the forward error correction encoded binary vector into a matrix;

rotating bits in respective columns of the matrix;

dividing the bits in respective rows of the matrix into an integer number of interleaving blocks; and

interleaving the bits in the respective interleaving blocks until each interleaving block in the matrix has been interleaved,

wherein the steps of reshaping the forward error correction encoded binary vector, rotating the bits, dividing the rows into interleaving blocks and interleaving the bits in each interleaving block are performed in a single bit reordering operation on bits in the forward error correction encoded binary vector using a rotation/interleaving index lookup table.

2. The method as claimed in claim 1 wherein the forward error correction encoded binary vectors are represented by v=[v 1 v 2 . . . v m ] where v i =[b i,1 ′ . . . b i,N i ′] is a binary sequence received from an encoder, and reshaping the forward error correction encoded binary vector comprises reshaping each v i into an N b/sub by N i /N b/sub sub-matrix

M

i

=

[

b

i

,

1

′

b

i

,

2

′

…

b

i

,

N

i

/

N

b

/

sub

′

b

i

,

N

i

/

N

b

/

sub

+

1

′

b

i

,

N

i

/

N

b

/

sub

+

2

′

…

b

i

,

2

⁢

N

i

/

N

b

/

sub

′

…

…

…

…

]

,

and reshaping the vector v into a matrix M=[M 1 M 2 . . . M m ].

3. The method as claimed in claim 2 wherein rotating the bits in the respective columns of the matrix M comprises rotating an i'th column [b 0,i . . . b j,i . . . b N b/sub −1,i ] T ={b j,i } (j=0, . . . , N b/sub −1) of the matrix so that the rotated column is {b j′,i }, where j′=mod [(i−1)·k d +k 0 +j, N b/sub ]; k 0 is a rotated index for b 0,1 ; and, k d is a rotation step size.

4. The method as claimed in claim 3 wherein parameters for k d and k 0 are k d =1 or −1, k 0 =0.

5. The method as claimed in claim 2 wherein interleaving the bits in the respective interleaving blocks comprises computing interleaved indices L (k) for respective bits of the respective interleaving blocks using:

L

⁡

(

k

)

=

{

L

0

,

k

=

0

;

mod

⁡

[

L

⁡

(

k

-

1

)

+

L

d

,

K

]

,

k

>

1.

where: K is the interleaving block size, L 0 ε[0, K−1] is an integer value, and L d ε[1, K−1] is a modulo difference between neighboring L(k)'s.

6. The method as claimed in claim 5 wherein the largest common divisor of L d and K is 1.

7. An orthogonal frequency-division multiplexing (OFDM) transceiver, comprising:

generating a forward error correction encoded binary vector from binary data to be transmitted;

a vector reshaper that reshapes a the forward error correction encoded binary vector into a matrix;

a bit rotator that rotates bits in respective columns of the matrix; and

an interleaver that divides respective rows of the matrix into an integer number of interleaving blocks, and interleaves the bits in the respective interleaving blocks until each interleaving block in the matrix has been interleaved,

wherein the vector reshaper, the bit rotator and the interleaver comprise a single bit reordering operation that uses a rotation/interleaving index lookup table to reorder the bits in the forward error correction encoded binary vector.

8. The OFDM transceiver as claimed in claim 7 wherein the binary vectors are represented by v=[v 1 v 2 . . . v m ] where v i =[b i,1 ′ . . . b i,N i ′] is a binary sequence received from an encoder, and the vector reshaper reshapes each v i into an N b/sub by N i /N b/sub sub-matrix

M

i

=

[

b

i

,

1

′

b

i

,

2

′

…

b

i

,

N

i

/

N

b

/

sub

′

b

i

,

N

i

/

N

b

/

sub

+

1

′

b

i

,

N

i

/

N

b

/

sub

+

2

′

…

b

i

,

2

⁢

N

i

/

N

b

/

sub

′

…

…

…

…

]

,

and then reshapes the vector v into a matrix M=[M 1 M 2 . . . M m ].

9. The OFDM transceiver as claimed in claim 7 wherein the bit rotator rotates the bits in the respective columns of the matrix M by rotating an i'th column [b 0,i . . . b j,i . . . b N b/sub −1,i ] T ={b j,i } (j=0, . . . , N b/sub −1) of the matrix M so that the rotated column is {b j′,i }, where j′=mod [(i−1)·k d +k 0 +j, N b/sub ]; k 0 is arotated index for b 0,1 ; and, k d is a rotation step size.

10. The OFDM transceiver as claimed in claim 9 wherein the interleaver interleaves the bits in the respective interleaving blocks by computing interleaved indices L (k) of respective bits of the respective interleaving blocks using:

L

⁡

(

k

)

=

{

L

0

,

k

=

0

;

mod

⁡

[

L

⁡

(

k

-

1

)

+

L

d

,

K

]

,

k

>

1.

where: K is the interleaving block size, L 0 ε[0, K−1] is an integer value, and L d ε[1, K−1] is a modulo difference between neighboring L(k)'s.

11. An orthogonal frequency-division multiplexing multiple access (OFDMA) transceiver, comprising:

generating a forward error correction encoded binary vector from binary data to be transmitted;

a vector reshaper that reshapes a the forward error correction encoded binary vector into a matrix;

a bit rotator that rotates bits in respective columns of the matrix; and

an interleaver that divides the bits in respective rows of the matrix into an integer number of interleaving blocks, and interleaves the bits in the respective interleaving blocks until each interleaving block in the matrix has been interleaved,

wherein the vector reshaper, the bit rotator, and the interleaver comprise a single bit reordering operation that uses a rotation/interleaving index lookup table to reorder the bits in the forward error correction encoded binary vector.

12. The OFDMA transceiver as claimed in 11 wherein the binary vectors are represented by v=[v 1 v 2 . . . V m ] where v i =[b i,1 ′ . . . b i,N i ′] is abinary sequence received from an encoder, and the vector reshaper reshapes each v i into an N b/sub by N i /N b/sub sub-matrix

M

i

=

[

b

i

,

1

′

b

i

,

2

′

…

b

i

,

N

i

/

N

b

/

sub

′

b

i

,

N

i

/

N

b

/

sub

+

1

′

b

i

,

N

i

/

N

b

/

sub

+

2

′

…

b

i

,

2

⁢

N

i

/

N

b

/

sub

′

…

…

…

…

]

,

and then reshapes the vector v into a matrix M=[M 1 M 2 . . . M m ].

13. The OFDMA transceiver as claimed in claim 11 wherein the bit rotator rotates the bits in the respective columns of the matrix by rotating an i'th column [b 0,i . . . b j,i . . . b N b/sub −1,i ] T ={b j,i } (j=0, . . . , N b/sub −1) of the matrix so that the rotated column is {b j′,i }, where j′=mod [(i−1)·k d +k 0 +j, N b/sub ]; k 0 is a rotated index for b 0,1 ; and, k d is a rotation step size.

14. The OFDMA transceiver as claimed in claim 13 wherein the interleaver interleaves the bits in the respective interleaving blocks by computing interleaved indices L (k) for respective bits of the respective interleaving blocks using:

L

⁡

(

k

)

=

{

L

0

,

k

=

0

;

mod

⁡

[

L

⁡

(

k

-

1

)

+

L

d

,

K

]

,

k

>

1.

where: K is the interleaving block size, L 0 ε[0, K−1] is an integer value, and L d ε[1, K−1] is a modulo difference between neighboring L(k)'s.

15. A method of interleaving a binary vector for transmission by an OFDM/OFDMA transmitter, comprising:

generating a forward error correction encoded binary vector from binary data to be transmitted;

reshaping the binary vector into a matrix;

dividing the bits in respective rows of the matrix into an integer number of interleaving blocks;

interleaving the bits in the respective interleaving blocks until each interleaving block in the matrix has been interleaved; and

rotating bits in respective columns of the matrix,

wherein the steps of reshaping the binary vector, dividing the rows into interleaving blocks, interleaving the bits in each interleaving block, and rotating the bits are performed in a single bit reordering operation on bits in the binary vector using a rotation/interleaving index lookup table.

16. The method as claimed in claim 15 wherein the binary vectors are represented by v=[v 1 v 2 . . . v m ] where v i =[b i,1 ′ . . . b i,N i ′] is a binary sequence received from an encoder, and reshaping the binary vector comprises reshaping each v i into an N b/sub by N i /N b/sub sub-matrix

M

i

=

[

b

i

,

1

′

b

i

,

2

′

…

b

i

,

N

i

/

N

b

/

sub

′

b

i

,

N

i

/

N

b

/

sub

+

1

′

b

i

,

N

i

/

N

b

/

sub

+

2

′

…

b

i

,

2

⁢

N

i

/

N

b

/

sub

′

…

…

…

…

]

,

and reshaping the vector v into a matrix M=[M 1 M 2 . . . M m ].

17. The method as claimed in claim 15 wherein interleaving the bits in the respective interleaving blocks comprises computing interleaved indices L(k) for respective bits of the respective interleaving blocks using:

L

⁡

(

k

)

=

{

L

0

,

k

=

0

;

mod

⁡

[

L

⁡

(

k

-

1

)

+

L

d

,

K

]

,

k

>

1.

where: K is the interleaving block size, L 0 ε[0, K−1] is an integer value, and L d ε[1, K−1] is a modulo difference between neighboring L(k)'s.

18. The method as claimed in claim 17 wherein the largest common divisor of L d and K is 1.

19. The method as claimed in claim 17 wherein rotating the bits in the respective columns of the matrix M comprises rotating an i'th column [b 0,i . . . b j,i . . . b N b/sub −1,i ] T ={b j,i } (j=0, . . . , N b/sub −1) of the matrix so that the rotated column is {b j′,i }, where j′=mod [(i−1)·k d +k 0 +j, N b/sub ]; k 0 is a rotated index for b 0,1 ; and, k d is a rotation step size.

20. The method as claimed in claim 19 wherein parameters for k d and k 0 are k d =1 or −1, k 0 =0.