Low latency interleaving and deinterleaving

• US 20050180332A1
• Filed: 12/07/2004
• Published: 08/18/2005
• Est. Priority Date: 02/13/2004
• Status: Abandoned Application

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Kim, Joonsuk, Hansen, Christopher James
• Application Number:
  US11/005,100
• Publication Number:
  US 20050180332A1
• Time in Patent Office: Days
• US Class Current: 370/244
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/2707 Simple row-column interleaver, i.e. pure block interleaving
• CPC Class Codes: H03M 13/2778 Interleaver using block-wise interleaving, e.g. the interleaving matrix is sub-divided into sub-matrices and the permutation is performed in blocks of sub-matrices
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2936 comprising an outer Reed-Solomon code and an inner convolutional code
• CPC Class Codes: H03M 13/2966 Turbo codes concatenated with another code, e.g. an outer block code
• CPC Class Codes: H03M 13/6527 IEEE 802.11 [WLAN]
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A method for interleaving contents of a frame begins by partitioning the frame into a plurality of frame segments, wherein the frame includes x rows of y columns of the content, and wherein at least one of the plurality of frame segments includes x rows of z columns of the content, where z is less than y. The method continues by storing the content of the x rows of z columns of the at least one of the plurality of frame segments in accordance with a first pattern to produce stored content. The method continues by retrieving the stored content in accordance with a second pattern to produce interleaved content.

Claims

1. A method for interleaving contents of a frame, the method comprising the steps of:

partitioning a frame into a plurality of frame segments, wherein the frame includes x rows of y columns of contents, and wherein at least one of the plurality of frame segments includes x rows of z columns of the contents, where z is less than y;

storing the x rows of z columns of the contents of the at least one of the plurality of frame segments in accordance with a first pattern to produce stored content; and

retrieving the stored content in accordance with a second pattern to produce interleaved content;

wherein x, y and z comprise integers.

2. The method of claim 1, wherein:

when y is a multiple of z, the method further comprises;

storing contents of the x rows of z columns of a first one of the plurality of frame segments in accordance with the first pattern to produce first stored content;

retrieving the first stored content in accordance with the second pattern to produce first interleaved content;

storing contents of the x rows of z columns of a second one of the plurality of frame segments in accordance with the first pattern to produce second stored content; and

retrieving the second stored content in accordance with the second pattern to produce second interleaved content.

3. The method of claim 1, wherein:

when y is not a multiple of z such that y=a*z+b, where a is whole number and b is a remainder, for each of the plurality of frame segments corresponding to the a*z term the method further comprises;

storing contents of the x rows of z columns in accordance with the first pattern to produce the stored content; and

retrieving the stored content in accordance with the second pattern to produce the interleaved content; and

for a remainder frame segment of the plurality of frames that corresponds to the b term;

storing the content of the x rows of z columns in accordance with a third pattern to produce remainder stored content; and

retrieving the remainder stored content in accordance with a fourth pattern to produce remainder interleaved content.

4. The method of claim 3 wherein:

when b equals one, the method further comprises;

storing contents of x rows of one column sequentially to produce the remainder stored content; and

retrieving the remainder stored content in a same sequential manner to produce remainder interleaved content.

5. The method of claim 3 wherein:

when b is greater than one, the method further comprises;

storing contents of x rows of b columns sequentially across the b columns from row to row of the x rows produce the remainder stored content; and

retrieving the remainder stored content sequentially down a row of the x rows from column to column of the b columns to produce remainder interleaved content.

6. The method of claim 1, wherein:

the first pattern includes storing the content of x rows of y columns sequentially across the y columns from row to row of the x rows to produce the stored content; and

the second pattern includes retrieving the remainder stored content sequentially down a row of the x rows from column to column of the y columns to produce the interleaved content.

7. The method of claim 1, wherein:

the first pattern includes storing the content of x rows of y columns sequentially down a row of the x rows from column to column of the y columns to produce the stored content; and

the second pattern includes retrieving the remainder stored content sequentially across the y columns from row to row of the x rows to produce the interleaved content.

8. A method for deinterleaving contents of a frame, the method comprising the steps of:

partitioning a frame into a plurality of frame segments, wherein the frame includes x rows of y columns of contents, and wherein at least one of the plurality of frame segments includes x rows of z columns of the contents, where z is less than y;

storing contents of the x rows of z columns of the at least one of the plurality of frame segments in accordance with a first pattern to produce stored content; and

retrieving the stored content in accordance with a second pattern to produce deinterleaved content;

wherein x, y and z comprise integers.

9. The method of claim 8, wherein:

when y is a multiple of z, the method further comprises;

storing contents of the x rows of z columns of a first one of the plurality of frame segments in accordance with the first pattern to produce first stored content;

retrieving the first stored content in accordance with the second pattern to produce first deinterleaved content;

storing contents of the x rows of z columns of a second one of the plurality of frame segments in accordance with the first pattern to produce second stored content; and

retrieving the second stored content in accordance with the second pattern to produce second deinterleaved content.

10. The method of claim 8, wherein:

when y is not a multiple of z such that y=a*z+b, where a is whole number and b is a remainder, for each of the plurality of frame segments corresponding to the a*z term, the method further comprises;

storing contents of the x rows of z columns in accordance with the first pattern to produce the stored content; and

retrieving the stored content in accordance with the second pattern to produce the deinterleaved content; and

for a remainder frame segment of the plurality of frames that corresponds to the b term;

storing contents of the x rows of z columns in accordance with a third pattern to produce remainder stored content; and

retrieving the remainder stored content in accordance with a fourth pattern to produce remainder deinterleaved content.

11. The method of claim 10, wherein:

when b equals one, the method further comprises;

storing the content of x rows of one column sequentially to produce the remainder stored content; and

retrieving the remainder stored content in a same sequential manner to produce remainder deinterleaved content.

12. The method of claim 10 further comprising, when b is greater than 1:

storing the content of x rows of b columns sequentially across the b columns from row to row of the x rows produce the remainder stored content; and

retrieving the remainder stored content sequentially down a row of the x rows from column to column of the b columns to produce remainder deinterleaved content.

13. The method of claim 8, wherein:

the first pattern includes storing the content of x rows of y columns sequentially across the y columns from row to row of the x rows to produce the stored content; and

the second pattern includes retrieving the remainder stored content sequentially down a row of the x rows from column to column of the y columns to produce the deinterleaved content.

14. The method of claim 8, wherein:

the first pattern includes storing the content of x rows of y columns sequentially down a row of the x rows from column to column of the y columns to produce the stored content; and

the second pattern includes retrieving the remainder stored content sequentially across the y columns from row to row of the x rows to produce the deinterleaved content.

15. A radio frequency (RF) transmitter, said transmitter comprising:

a baseband processing means for performing an outer encoding function on outbound data to produce outer encoded data, interleaving the outer encoded data to produce interleaved outer encoded data, and converting a portion of the interleaved outer encoded data into outbound baseband signals; and

a transmitting means for converting the outbound baseband signals into outbound RF signals;

wherein the baseband processing means further comprises;

partitioning means for partitioning a frame of the outer encoded data into a plurality of frame segments, wherein the frame includes x rows of y columns of bytes of the outer encoded data, and wherein at least one of the plurality of frame segments includes x rows of z columns of bytes of the outer encoded data, where z is less than y;

storing means for storing the bytes of the outer encoded data of the x rows of z columns of the at least one of the plurality of frame segments in accordance with a first pattern to produce stored bytes of the outer encoded data; and

retrieving means for retrieving the stored bytes of the outer encoded data in accordance with a second pattern to produce the portion of the interleaved outer encoded data.

16. The RF transmitter of claim 15, wherein, when y is a multiple of z, the baseband processing means is configured to:

store the bytes of the outer encoded data of the x rows of z columns of a first one of the plurality of frame segments in accordance with the first pattern to produce first stored bytes of the outer encoded data;

retrieve the first stored bytes of the outer encoded data in accordance with the second pattern to produce first interleaved bytes of the outer encoded data;

store the bytes of the outer encoded data of the x rows of z columns of a second one of the plurality of frame segments in accordance with the first pattern to produce second stored bytes of the outer encoded data; and

retrieve the second stored bytes of the outer encoded data in accordance with the second pattern to produce second interleaved bytes of the outer encoded data.

17. The RF transmitter of claim 15, wherein when y is not a multiple of z such that y=a*z+b, where a is whole number and b is a remainder, for each of the plurality of frame segments corresponding to the a*z term, the baseband processing means is configured to:

store the bytes of the outer encoded data of the x rows of z columns in accordance with the first pattern to produce the stored bytes of the outer encoded data; and

retrieve the stored bytes of the outer encoded data in accordance with the second pattern to produce the interleaved bytes of the outer encoded data; and

for a remainder frame segment of the plurality of frames that corresponds to the b term, the baseband processing means is configured to;

store the bytes of the outer encoded data of the x rows of z columns in accordance with a third pattern to produce remainder stored bytes of the outer encoded data; and

retrieve the remainder stored bytes of the outer encoded data in accordance with a fourth pattern to produce remainder interleaved bytes of the outer encoded data.

18. The RF transmitter of claim 17, wherein when b equals one, the baseband processing means is configured to:

store the bytes of the outer encoded data of x rows of one column sequentially to produce the remainder stored bytes of the outer encoded data; and

retrieve the remainder stored bytes of the outer encoded data in a same sequential manner to produce remainder interleaved bytes of the outer encoded data.

19. The RF transmitter of claim 17, wherein when b is greater than one, the baseband processing means is configured to:

store the bytes of the outer encoded data of x rows of b columns sequentially across the b columns from row to row of the x rows produce the remainder stored bytes of the outer encoded data; and

retrieve the remainder stored bytes of the outer encoded data sequentially down a row of the x rows from column to column of the b columns to produce remainder interleaved bytes of the outer encoded data.

20. The RF transmitter of claim 15, wherein:

the first pattern includes storing the bytes of the outer encoded data of x rows of y columns sequentially across the y columns from row to row of the x rows to produce the stored bytes of the outer encoded data; and

the second pattern includes retrieving the remainder stored bytes of the outer encoded data sequentially down a row of the x rows from column to column of the y columns to produce the interleaved bytes of the outer encoded data.

21. The RF transmitter of claim 15, wherein:

the first pattern includes storing the bytes of the outer encoded data of x rows of y columns sequentially down a row of the x rows from column to column of the y columns to produce the stored bytes of the outer encoded data; and

the second pattern includes retrieving the remainder stored bytes of the outer encoded data sequentially across the y columns from row to row of the x rows to produce the interleaved bytes of the outer encoded data.

22. A radio frequency (RF) receiver, wherein said receiver comprising:

receiver means for converting inbound RF signals into inbound baseband signals; and

baseband processing means for converting the inbound baseband signals into interleaved outer encoded data;

deinterleaving the interleaved outer encoded data to produce deinterleaved outer encoded data and performing an outer decoding function on deinterleaved bytes of the interleaved outer encoded data to produce partial inbound data,

the baseband processing means further comprising;

partitioning means for partitioning a frame of the interleaved outer encoded data into a plurality of frame segments, wherein the frame includes x rows of y columns of bytes of the interleaved outer encoded data, and wherein at least one of the plurality of frame segments includes x rows of z columns of the bytes of the interleaved outer encoded data, where z is less than y;

storing means for storing the bytes of the interleaved outer encoded data of the x rows of z columns of the at least one of the plurality of frame segments in accordance with a first pattern to produce stored bytes of the interleaved outer encoded data; and

retrieving means for retrieving the stored bytes of the interleaved outer encoded data in accordance with a second pattern to produce the deinterleaved bytes of the interleaved outer encoded data.

23. The RF receiver of claim 22 wherein, when y is a multiple of z, the baseband processing means is configured to:

store the bytes of the interleaved outer encoded data of the x rows of z columns of a first one of the plurality of frame segments in accordance with the first pattern to produce first stored bytes of the interleaved outer encoded data;

retrieve the first stored bytes of the interleaved outer encoded data in accordance with the second pattern to produce first deinterleaved bytes of the interleaved outer encoded data;

store the bytes of the interleaved outer encoded data of the x rows of z columns of a second one of the plurality of frame segments in accordance with the first pattern to produce second stored bytes of the interleaved outer encoded data; and

retrieve the second stored bytes of the interleaved outer encoded data in accordance with the second pattern to produce second deinterleaved bytes of the interleaved outer encoded data.

24. The RF receiver of claim 22 wherein, when y is not a multiple of z such that y=a*z+b, where a is whole number and b is a remainder, for each of the plurality of frame segments corresponding to the a*z term, the baseband processing means is configured to:

store the bytes of the interleaved outer encoded data of the x rows of z columns in accordance with the first pattern to produce the stored bytes of the interleaved outer encoded data; and

retrieve the stored bytes of the interleaved outer encoded data in accordance with the second pattern to produce the deinterleaved bytes of the interleaved outer encoded data; and

for a remainder frame segment of the plurality of frames that corresponds to the b term, the baseband processing means is configured to;

store the bytes of the interleaved outer encoded data of the x rows of z columns in accordance with a third pattern to produce remainder stored bytes of the interleaved outer encoded data; and

retrieve the remainder stored bytes of the interleaved outer encoded data in accordance with a fourth pattern to produce remainder deinterleaved bytes of the interleaved outer encoded data.

25. The RF receiver of claim 24, wherein when b equals one, the baseband processing means is configured to:

store the bytes of the interleaved outer encoded data of x rows of one column sequentially to produce the remainder stored bytes of the interleaved outer encoded data; and

retrieve the remainder stored bytes of the interleaved outer encoded data in a same sequential manner to produce remainder deinterleaved bytes of the interleaved outer encoded data.

26. The RF receiver of claim 24, wherein when b is greater than one, the baseband processing means is configured to:

store the bytes of the interleaved outer encoded data of x rows of b columns sequentially across the b columns from row to row of the x rows produce the remainder stored bytes of the interleaved outer encoded data; and

retrieve the remainder stored bytes of the interleaved outer encoded data sequentially down a row of the x rows from column to column of the b columns to produce remainder deinterleaved bytes of the interleaved outer encoded data.

27. The RF receiver of claim 22, wherein:

the first pattern includes storing the bytes of the interleaved outer encoded data of x rows of y columns sequentially across the y columns from row to row of the x rows to produce the stored bytes of the interleaved outer encoded data; and

the second pattern includes retrieving the remainder stored bytes of the interleaved outer encoded data sequentially down a row of the x rows from column to column of the y columns to produce the deinterleaved bytes of the interleaved outer encoded data.

28. The RF receiver of claim 22, wherein:

the first pattern includes storing the bytes of the interleaved outer encoded data of x rows of y columns sequentially down a row of the x rows from column to column of the y columns to produce the stored bytes of the interleaved outer encoded data; and

the second pattern includes retrieving the remainder stored bytes of the interleaved outer encoded data sequentially across the y columns from row to row of the x rows to produce the deinterleaved bytes of the interleaved outer encoded data.

29. A radio frequency (RF) transceiver, said transceiver comprising:

a baseband processor, configured to perform an outer encoding function on outbound data to produce outer encoded data, to interleave the outer encoded data to produce interleaved outer encoded data, to convert a portion of the interleaved outer encoded data into outbound baseband signals, to convert inbound baseband signals into other interleaved outer encoded data, to deinterleave the other interleaved outer encoded data to produce deinterleaved outer encoded data and to perform an outer decoding function on deinterleaved bytes of the interleaved outer encoded data to produce partial inbound data;

a transmitter, configured to convert the outbound baseband signals into outbound RF signals; and

a receiver, configured to convert inbound RF signals into the inbound baseband signals;

wherein the baseband processor further comprises;

a partitioner, configured to partition a frame of the outer encoded data into a plurality of frame segments and to partition a frame of the interleaved outer encoded data into another plurality of frame segments, wherein the frame includes x rows of y columns of bytes of data, and wherein at least one of the plurality of frame segments and the another plurality of frame segments includes x rows of z columns of bytes of the data, where z is less than y;

a data storer, configured to store the bytes of the data of the x rows of z columns of the at least one of the plurality of frame segments and the another plurality of frame segments in accordance with a first pattern to produce stored bytes of the outer encoded data and to produce stored bytes of the interleaved outer encoded data; and

a data retriever, configured to retrieve the stored bytes of the outer encoded data and stored bytes of the interleaved outer encoded data in accordance with a second pattern to produce the portion of the interleaved outer encoded data and to produce the deinterleaved bytes of the interleaved outer encoded data.

30. The RF receiver of claim 29, wherein:

the first pattern includes storing the bytes of the interleaved outer encoded data and the bytes of the outer encoded data of x rows of y columns sequentially across the y columns from row to row of the x rows to produce the stored bytes of the interleaved outer encoded data and the stored bytes of the outer encoded data; and

the second pattern includes retrieving the remainder stored bytes of the interleaved outer encoded data and the remainder stored bytes of the outer encoded data sequentially down a row of the x rows from column to column of the y columns to produce the deinterleaved bytes of the interleaved outer encoded data and the interleaved bytes of the outer encoded data.

31. The RF receiver of claim 29, wherein:

the first pattern includes storing the bytes of the interleaved outer encoded data and the bytes of the outer encoded data of x rows of y columns sequentially down a row of the x rows from column to column of the y columns to produce the stored bytes of the interleaved outer encoded data and the stored bytes of the outer encoded data; and

the second pattern includes retrieving the remainder stored bytes of the outer encoded data and the remainder stored bytes of the interleaved outer encoded data sequentially across the y columns from row to row of the x rows to produce the interleaved bytes of the outer encoded data and the deinterleaved bytes of the interleaved outer encoded data.