TIME DE-INTERLEAVING CIRCUIT AND METHOD THEREOF

Abstract

A time de-interleaving circuit and a time de-interleaving method perform a time de-interleaving process through writing and reading a plurality of sets of time interleaved data into and from a first memory and a second memory. The time de-interleaving method includes: selecting a set of first time interleaved data and a set of second time interleaved data from the plurality of sets of time interleaved data, the set of first time interleaved data and the set of second time interleaved data having the same delay length; writing the set of first time interleaved data into the first memory; and writing the set of second time interleaved data into the second memory. The first memory utilizes a bit length as an access unit, and the second memory has an access unit smaller than the bit width.

Claims

1. A time de-interleaving method, performing a time de-interleaving process through writing and reading a plurality of sets of time interleaved data into and from a storage circuit, the method comprising: selecting a K sets from the sets of time interleaved data, the K sets of time de-interleaved data having a same delay length, K being an integer greater than 1; generating data to be written, the data to be written comprising the K sets of time interleaved data; and in a same writing operation, writing the data to be written into the storage circuit; wherein, a bit width of the storage circuit is greater than or equal to a data size of the data to be written.

2. The time de-interleaving method according to claim 1, wherein the K sets of data are respectively selected from K groups of time interleaved data groups, and the K groups of time interleaved data correspond to a same time interleaving length.

3. The time de-interleaving method according to claim 1, further comprising: determining a value of K according to a data size of one set of time interleaved data and the bit width of the storage circuit.

4. The time de-interleaving method according to claim 3, wherein the value of K is smaller than a maximum integer of a quotient obtained by dividing the bit width by the data size of the one set of time interleaved data.

5. The time de-interleaving method according to claim 1, wherein the storage circuit comprises a first memory and a second memory, the first memory uses the bit width as an access unit and stores the data to be written, and the second memory has an access unit smaller than the bit width; the method further comprising: selecting a set of target time interleaved data, the set of target time interleaved data and the K sets of time interleaved data having the same delay length; and writing the set of target time interleaved data into the second memory.

6. A time de-interleaving circuit, comprising: a buffer circuit, buffering a plurality of sets of time interleave data; a storage circuit; and a control circuit, coupled to the buffer circuit and the storage circuit, selecting K sets of the time interleaved data from the storage circuit to form data to be written, and writing the data to be written into the storage circuit in a same writing operation; wherein, the K sets of time interleaved data have a same delay length, K is an integer greater than 1, and a bit width of the storage circuit is greater than or equal to a data size of the data to be written.

7. The time de-interleaving circuit according to claim 6, wherein the K sets of time interleaved data are selected from K groups of time interleaved data groups, respectively, and the K groups of time interleaved data correspond to a same time interleaving length.

8. The time de-interleaving circuit according to claim 6, wherein the control circuit further determines a value of K according to a data size of one set of time-interleaved data and the bit width of the storage circuit.

9. The time de-interleaving circuit according to claim 8, wherein K is a maximum integer of a quotient obtained by dividing the bit width by the data size of one set of the time interleaved data.

10. The time de-interleaving circuit according to claim 6, wherein the storage circuit comprises: a first memory, utilizing the bit width as an access unit, storing the data to be written; and a second memory, having an access unit smaller than the bit width; wherein, the control circuit further selects a set of target time de-interleaved data from the buffer circuit and writes the set of target time interleaved data into the second memory, and the set of target time interleaved data and the K sets of time interleaved data have the same delay length.

11. A time de-interleaving method, performing a time de-interleaving process through writing and reading a plurality of sets of time interleaved data into and from a first memory and a second memory, the method comprising: selecting a set of first time interleaved data and a set of second time interleaved data from the sets of time interleaved data, the set of first time interleaved data and the set of second time interleaved data having a same delay length; writing the set of first time interleaved data into the first memory; and writing the set of second time interleaved data into the second memory; wherein, the first memory utilizes a bit width as an access unit, and the second memory has an access unit smaller than the bit width.

12. The time de-interleaving method according to claim 11, wherein the set of first time interleaved data and the set of second time interleaved data are simultaneously generated.

13. The time de-interleaving method according to claim 11, further comprising: selecting (K-1) sets from the plurality of sets of time interleaved data, the (K-1) sets of time interleaved data and the set of first time interleaved data having the same delay length, K being an integer greater than 1; wherein, the set of first time interleaved data and the (K-1) sets of time interleaved data are simultaneously written into the first memory, and a total data size of the set of first time interleaved data and the (K-1) sets of time interleaved data is smaller than the bit width.

14. The time de-interleaving method according to claim 13, wherein the set of first time interleaved data and the (K-1) sets of time interleaved data are selected from K groups of time interleaved data groups, respectively, and the K groups of time interleaved data groups correspond to a same time interleaving length.

15. The time de-interleaving method according to claim 13, further comprising: determining a value of K according to a data size of one set of the time interleaved data and the bit width, the value of K being maximum integer of a quotient obtained by dividing the bit width by the data size of the time interleaved data.

16. A time de-interleaving circuit, comprising: a buffer circuit, buffering a plurality of sets of time interleaved data; a first memory, utilizing a bit width as an access unit; a second memory, having an access unit smaller than the bit width; and a control circuit, coupled to the buffer circuit, the first memory and the second memory, selecting a set of first time interleaved data and a set of second time interleaved data from the buffer circuit, and writing the set of first time interleaved data into the first memory and writing the set of second time interleaved data into the second memory; wherein, the first memory utilizes a bit width as an access unit, and the second memory has an access unit smaller than the bit width.

17. The time de-interleaving circuit according to claim 16, wherein the set of first time interleaved data and the set of second time interleaved data are simultaneously generated.

18. The time de-interleaving circuit according to claim 16, wherein the control circuit further selects (K-1) sets of time interleaved data from the buffer circuit, and simultaneously writes the set of first time interleaved data and the (K-1) sets of time interleaved data into the first memory, the (K-1) sets of time interleaved data and the set of first time interleaved data have the same delay length, and a total data size of the set of first time interleaved data and the (K-1) sets of time interleaved data is smaller than the bit width.

19. The time de-interleaving circuit according to claim 18, wherein the set of first time interleaved data and the (K-1) sets of time interleaved data are selected from K groups of time interleaved data groups, respectively, and the K groups of time interleaved data groups correspond to a same time interleaving length.

20. The time de-interleaving circuit according to claim 18, wherein the control circuit further determines a value of K according to a data size of one set of the time interleaved data and the bit width, and the value of K is maximum integer of a quotient obtained by dividing the bit width by the data size of one set of the time interleaved data.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0012] FIG. 1 is a schematic diagram of a time de-interleaving process;

[0013] FIG. 2 is a block diagram of a time de-interleaving circuit according to an embodiment of the present invention; and

[0014] FIG. 3 and FIG. 4 are flowcharts of a time de-interleaving method according to an embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

[0015] The disclosure of the present invention includes a time de-interleaving circuit and method. In possible implementation, one person skilled in the art my select equivalent elements or steps to achieve the present invention based on the disclosure of the application; that is, the implementation of the present invention is not limited to the embodiments below.

[0016] FIG. 2 shows a block diagram of a time de-interleaving circuit according to an embodiment of the present invention. FIG. 3 and FIG. 4 show flowcharts of a time de-interleaving method according to an embodiment of the present invention. A time de-interleaving circuit 220 receives time interleaved data (i.e., the foregoing data DX.sub.p, q) from a frequency de-interleaving circuit 210, and buffers the time interleaved data in a buffer circuit 222 (step S310). A control circuit 224 then writes and reads data into and from a storage circuit 225 to complete time de-interleaving. The data read from the storage circuit 225 is buffered in the buffer circuit 223, and is outputted according to a normal time de-interleaving sequence. The storage circuit 225 includes a first memory 226 and a second memory 228. The first memory 226 (e.g., DRAM or SDRAM) is accessed in a unit of one bit width each time; the second memory 228 may be a DRAM or SDRAM having a bit width smaller than the bit width of the first memory 226, or a memory that does not have a minimum access unit (e.g., a static random access memory (SRAM)).

[0017] Referring to FIG. 1, several of the 13 convolutional de-interleaving circuits 110 have the same time interleaving length l. For example, assuming that the 0.sup.th convolutional de-interleaving circuit 110-1 and the 1.sup.st convolutional de-interleaving circuit 110-1 have the same time interleaving length l, according to equation (1), data D0.sub.0, q and data D1.sub.0, q undergo the same delay length, and data D0.sub.1, q and data D1.sub.1, q undergo the same delay length, and so forth. Further, data having the same q value is generated simultaneously. That is, all of the data D0.sub.p, 0, data D1.sub.p, 0, . . . and data D12.sub.p, 0 corresponding to the parameter p in values 0 to (n-1) is simultaneously generated, all of data D0.sub.p, 1, data D1.sub.p, 1, . . . and data D12.sub.p, 1 corresponding to the parameter p in values 1 to (n-1) is simultaneously generated, and so forth.

[0018] Thus, from the buffer circuit 222, the control circuit 224 may simultaneously obtain the data D0.sub.0, 0 and the data D1.sub.0, 0, which both correspond to the same delay length; that is, the data D0.sub.0, 0 and the data D1.sub.0, 0 may be written into the storage circuit 225 at the same time and read from the storage circuit 225 at the same time by the control circuit 224 to complete the time de-interleaving process. Therefore, when writing into the first memory 226, the control circuit 224 may consider these two sets of data as one group of data to be written to save the memory space. More specifically, according to the bit width W of the first memory 226 and the code-word length C of the data DX.sub.p, q, the control circuit 224 may first calculate that a group of data to be written includes k=[W/C] sets of data DX.sub.p, q (step S320). According to the value k, k sets of data DX.sub.p, q having the same delay length are selected to form the set of group to be written (step S330), and the group of data to be written is written into the storage circuit 225 (step S340). More specifically, at this point, the group of data to be written is written into the first memory 226. Table-2 below lists the mapping relationship between several W values and k values (taking C=21 bits for instance).

TABLE-US-00002 TABLE 2 Number of sets of data included in one Bit width (W) group of data to be written 64 3 128 6 256 12

[0019] Taking actual numbers for instance (the scenario 1), assume that the transmission mode of the 13 groups of time interleaved data is 1 and the 13 groups of time interleaved data have the same time interleaving length l=16, the bit width of the first memory 226 is W=128 bits, and the code-word length of the data DX.sub.p, q is C=21 bits. Thus, the memory size (bits) that a conventional time de-interleaving method needs is:

[00001] ${{.Math.}_{i = 0}^{95} .Math. .Math. 16 \times (95 - ((i \times 5) .Math. \mod .Math. .Math. 96))} \times 128 \times 13 = 121 .Math., .Math. 405 .Math., .Math. 440$

[0020] In contrast, the time de-interleaving method of the present invention utilizes k−┐128/21┌−6 sets of data DX.sub.p, q as one group of data to be written, and so the required memory size (bits) is:

[00002] ${{.Math.}_{i = 0}^{95} .Math. .Math. 16 \times (95 - ((i \times 5) .Math. \mod .Math. .Math. 96))} \times 128 \times .Math. \frac{13}{6} .Math. = 28 .Math., .Math. 016 .Math., .Math. 640$

[0021] According to the embodiment of the present invention, the memory size needed is only ⅓ of that of the above conventional method.

[0022] More specifically, in the foregoing embodiment, D0.sub.p, q, D1.sub.p, q, D2.sub.p, q, D3.sub.p, q, D4.sub.p, q and D5.sub.p, q may be used as one group of data to be written T0.sub.p, q; D6.sub.p, q, D7.sub.p, q, D8.sub.p, q, D9.sub.p, q, D10.sub.p, q and D11.sub.p, q may be used as one group of data to be written T1.sub.p, q; D12.sub.p, q may be used as one group of data to be written T2.sub.p, q. The data DX.sub.p, q may be obtained through the buffer circuit 222, and is the (x*108+p).sup.th set of data at the p.sup.th time point in the buffer circuit 222. The control circuit 224 may accordingly generate an appropriate control signal to write the data DX.sub.p, q into the storage circuit 225. According to the delay length d.sub.i corresponding to each set of the data corresponding DX.sub.p, q, the control circuit 224 reads the data DX.sub.p, q from the storage circuit 225 at corresponding time points. In the foregoing embodiment, the data DX.sub.p, q is delayed by 16×(95−(p×5)mod 96) time units and then outputted; that is, the set of data to be outputted T0.sub.0, q undergoes 16×(95−(0×5)mod 96)=1520 time units in the storage circuit 225, and is then outputted. At the time point q=1520, T0.sub.0, 0 is outputted, and T0.sub.0, 1520 may be written at a position where T0.sub.0, 0 is originally located in the storage circuit 225. When T0.sub.1, 80 is outputted, T0.sub.1, 1520 is written at a position where T0.sub.1, 80 is originally located in the storage circuit 225. That is, when T0.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96) is outputted, T0.sub.p, 1520 is written at a position where T0.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96) is originally located in the storage circuit 225. The control circuit 224 stores the data DX.sub.p, q in the buffer circuit 223 after reading the data DX.sub.p, q from the storage circuit 225. It is known from the foregoing reading sequence that, in the buffer circuit 223, the data DX.sub.p, q is sequentially D0.sub.0, 0, D1.sub.0, 0, D2.sub.0, 0, D3.sub.0, 0, D4.sub.0, 0, D5.sub.0, 0, D0.sub.1, 80, D1.sub.1, 80, D2.sub.1, 80, D3.sub.1, 80, D4.sub.1, 80, D5.sub.1, 80, . . . , D0.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), D1.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), D2.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), D3.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), D4.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), D5.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), . . . , D12.sub.0, 0, D12.sub.1, 80, . . . , D12.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), . . . , D12.sub.94, 1376 and D12.sub.95, 1456. Next, by adjusting the sequence of outputting the data DX.sub.p, q from the buffer circuit 223, the data DX.sub.p, q is outputted into the sequence D0.sub.0, 0, D0.sub.1, 80, D0.sub.2, 160, . . . , D0.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), . . . , D0.sub.94, 1376, D095, 1456, D1.sub.0, 0, D1.sub.1, 80, D1.sub.2, 160, . . . , D1.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), . . . , D1.sub.94, 1376, D1.sub.95, 1456, D2.sub.0, 0, D2.sub.1, 80, D2.sub.2, 160, . . . , D2.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), . . . , D11.sub.94, 1376, D11.sub.95, 1456, D12.sub.0, 0, D12.sub.1, 80, D12.sub.2, 160, . . . , D12.sub.p, 1520−16*.sub.(95−(p*.sub.5)mod96), . . . , D12.sub.94, 1376 and D12.sub.95, 1456.

[0023] The 13 groups of time interleaved data may correspond to multiple time interleaving lengths l (the scenario 2). For example, the l value is 16 for four of the groups, 8 for eight of the groups, and 4 for the remaining one group. When the control circuit 224 determines the group of data to be written (step S330) (k=6 in continuation of the above example), the data DX.sub.p, q of the four groups with l=16 may form 1 (=┌4/6┐) group of data to be written A, the data DX.sub.p, q of the eight groups with l=8 may form 2 (=┌8/6┐) groups of data to be written (respectively data to be written B (including six sets of data) and data to be written C (including two sets of data)), and the remaining one group of data DX.sub.p, q form 1 (=┌1/6┐) group of data to be written D. It is discovered that, two of the four groups of data to be written (the data to be written C and the data to be written D) in fact include only one set and two sets of the time interleaved data DX.sub.p, q, respectively. Such occurrence results a waste in the first memory 226. Thus, when the control circuit 224 writes the group of data to be written to the storage circuit 225 (step S340), a detailed process in FIG. 4 is further included.

[0024] In step S342, the control circuit 224 determines whether a difference between the bit width W of the first memory 226 and the data size of the group of data to be written is greater than the data size of one set of the time-interleaved data DX.sub.p, q. If so, the group of data to be written is written into the first memory 226 or the second memory 228 according to a determination condition (step S346). If not, the group of data to be written is written into the first memory 226 (step S344). In continuation of the above scenario 2, the data to be written B is written into the first memory 226 (step S344), and the control circuit 224 then determines to write the data to be written C into the first memory 226 or the second memory 228 according to the determination condition. For example, the determination condition may be (1) whether the actual data size of the group of data to be written exceeds one-half of the bit width W; or (2) the group of data to be written includes only one set of the data DX.sub.p, q. For the condition (1), the actual data size of the data to be written A exceeds one-half of the bit width W, and is thus written into the first memory, and the data to be written C and the data to be written D are written into the second memory 228. For the condition (2), the data to be written A and the data to be written C are written into the first memory 226, and the data to be written D is written into the second memory 228. For either the condition (1) or the condition (2), given that the second memory 228 is implemented by a DRAM or SDRAM having bit width that is smaller than the bit width of the first memory 226, or even implemented by an SRAM, the effect of saving memory space is achieved. Further, in continuation of the scenario (1), whether determination is performed based on the condition (1) or the condition (2), the control circuit 224 writes the data to be written that includes only one set of data DX.sub.p, q into the second memory 228 (an SRAM for example). At this point, the space (in bits) used by the first memory 226 is:

[00003] ${{.Math.}_{i = 0}^{95} .Math. .Math. 16 \times (95 - ((i \times 5) .Math. \mod .Math. .Math. 96))} \times 128 \times .Math. \frac{12}{6} .Math. = 18 .Math., .Math. 677 .Math., .Math. 760$

[0025] And the space (in bits) used by the second memory space 228 is:

[00004] ${{.Math.}_{i = 0}^{95} .Math. .Math. 16 \times (95 - ((i \times 5) .Math. \mod .Math. .Math. 96))} \times 21 \times 1 = 1 .Math., .Math. 532 .Math., .Math. 160$

[0026] Thus, it is equivalently exchanging a space having 1,532,160 bits in the second memory 228 for a space having 9,338,880 (=28,016,640−18,677,760) bits in the first memory 226. Such design effectively enhances the memory utilization efficiency.

[0027] More specifically, in the embodiment in the scenario 2, D0.sub.p, q, D1.sub.p, q, D2.sub.p, q and D3.sub.p, q may be used as one group of data to be written T0.sub.p, q, D4.sub.p, q, D5.sub.p, q, D6.sub.p, q and D7.sub.p, q may be used as one group of data to be written T1.sub.p, q, D8.sub.p, q and D9.sub.p, q may be used as one group of data to be written T2.sub.p, q, and D12.sub.p, q may be used as one group of data to be written T3.sub.p, q. The data DX.sub.p, q may be obtained through the buffer circuit 222, and is the (x*108+p).sup.th set of data at the p.sup.th time point in the buffer circuit 222. Similarly, the control circuit 224 reads the data DX.sub.p, q from the storage circuit 225 according to the time points respectively corresponding to the respective delay lengths Di of the sets of the DX.sub.p, q. The data of D0˜3.sub.p, q is delayed by 16×(95−(p×5)mod 96) time units in the storage circuit 225 and outputted; that is, T0.sub.0, q undergoes 16×(95−(0×5)mod 96)=1520 time units in the storage circuit 225 and is then outputted. The data of D4˜11.sub.p, q is delayed by 8×(95−(p×5)mod 96) time units in the storage circuit 225 and outputted; that is, T1.sub.0, q and T2.sub.0, q undergo 8×(95−(0×5)mod 96)=760 time units in the storage circuit 225 and are then outputted. The data of D12.sub.p, q is delayed by 4×(95(p×5)mod 96) time units in the storage circuit 225 and outputted; that is, T3.sub.0, q undergoes 4×(95−(p×5)mod 96)=380 time units in the storage circuit 225 and is then outputted. After reading the data DX.sub.p, q from the storage circuit 225, the control circuit 224 stores the data DX.sub.p, q in the buffer circuit 223. Next, through adjusting the sequence of outputting the data data DX.sub.p, q from the buffer circuit 223, the control circuit 224 outputs the data DX.sub.p, q to complete the time de-interleaving process.

[0028] In an example below, spaces that the first memory 226 and the second memory 228 may occupy for different bit widths of the first memory 226 are listed (taking the scenario 1 for instance):

Bit Width W=64 Bits

[0029]

TABLE-US-00003 Ratio of numbers of sets of Space (in bits) used data DX.sub.p,q in first memory Space (in bits) used by second memory 226 and second memory 228 by first memory 226 228 13:0 23,347,200 0 12:1 18,677,760 1,532,160 9:4 14,008,320 6,128,640 6:7 9,338,880 10,725,120 3:10 4,669,440 15,321,600 0:13 0 19,918,080

Bit Width W=128 Bits

[0030]

TABLE-US-00004 Ratio of numbers of sets of Space (in bits) used data DX.sub.p,q in first memory Space (in bits) used by second memory 226 and second memory 228 by first memory 226 228 13:0 28,016,640 0 12:1 18,677,760 1,532,160 6:7 9,338,880 10,725,120 0:13 0 19,918,080

Bit Width W=256 Bits

[0031]

TABLE-US-00005 Ratio of numbers of sets of Space (in bits) used data DX.sub.p,q in first memory Space (in bits) used by second memory 226 and second memory 228 by first memory 226 228 13:0 37,355,520 0 12:1 18,677,760 1,532,160 0:13 0 19,918,080

[0032] One person skilled in the art may understand implementation details and variations of the present invention with reference to the disclosure of the device in FIG. 2 and the disclosure of the method in FIG. 3 and FIG. 4. While the invention has been described by way of example and in terms of the preferred embodiments, it is to be understood that the invention is not limited thereto. On the contrary, it is intended to cover various modifications and similar arrangements and procedures, and the scope of the appended claims therefore should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements and procedures.

TIME DE-INTERLEAVING CIRCUIT AND METHOD THEREOF

Inventors

Cpc classification

Classification Explorer

H04L69/22

ELECTRICITY

Classification Explorer

H03M13/2732

ELECTRICITY

Classification Explorer

H04L1/0043

ELECTRICITY

Classification Explorer

H04L1/0071

ELECTRICITY

Classification Explorer

H03M13/6505

ELECTRICITY

International classification

Classification Explorer

H04L27/26

ELECTRICITY

Classification Explorer

H04L29/06

ELECTRICITY

Abstract

Claims

Description