Time and cell de-interleaving circuit and method for performing time and cell de-interleaving

Abstract

A method for performing time and cell de-interleaving on an interleaved signal including a plurality of cells is provided. The method includes: providing a first memory for storing the cells, the first memory written and read each time in a unit of one cell group, the cell group including K cells, where K is a positive integer greater than 1; providing a second memory for storing the cells read from the first memory; reading the cells from the first memory, and writing the cells to the second memory according to a writing rule of a plurality of permutation rules, K consecutive cells written to the second memory being from the same cell group; and reading the cells from the second memory according to a reading rule of the permutation rules, to cause the cells read from the second memory to be complete with time de-interleaving and cell de-interleaving.

Claims

1. A time and cell de-interleaving circuit, located at a signal receiver of a communications system operating according to a predetermined broadcasting standard transmission protocol requiring time de-interleaving and cell de-interleaving on an interleaved signal, the interleaved signal comprising a plurality of cells, the time and cell de-interleaving circuit reducing the required number of times a memory storing the interleaved signal is accessed, comprising: a first memory device, storing the cells of said interleaved signal; a storage control circuit, controlling an access operation of the first memory device, the access operation performed for one cell group at a time, each cell group comprising K cells, where K is a positive integer greater than 1; a second memory device, storing the cells read from the first memory device; and a rule generating unit, generating a plurality of permutation rules including a set of writing rules and a set of reading rules according to time interleaving and cell interleaving characteristics of said predetermined broadcasting standard transmission protocol of the interleaved signal, the plurality of permutation rules specifying a respective memory address for reading or writing each of the cells during reading and writing operations, writing the cells read from the first memory device to the second memory device according to a writing rule of the permutation rules, and reading the cells from the second memory device according to a reading rule of the permutation rules, wherein the plurality of permutation rules are generated using the number of cells in each cell group K, a total number of cell groups of the first memory device, a total number of rows of the first memory device, and a total number of columns of the first memory device such that the cells of the interleaved signal read from the second memory device in accordance with the reading rule of the permutation rules are simultaneously cell de-interleaved and time de-interleaved.

2. The time and cell de-interleaving circuit according to claim 1, wherein the interleaved signal comprises a plurality of forward error correction (FEC) blocks, the plurality of permutation rules comprise one writing rule and K reading rules, the writing rule implemented for writing every of the FEC blocks, and the K reading rules implemented for reading different FEC blocks of the FEC blocks, respectively.

3. The time and cell de-interleaving circuit according to claim 2, wherein the writing rule causes the cells read from the first memory device to be written to the second memory device according to a sequence of reading the cells from the first memory device.

4. The time and cell de-interleaving circuit according to claim 1, wherein the interleaved signal comprises a plurality of FEC blocks, the plurality of permutation rules comprise one reading rule and K writing rules, the reading rule implemented for reading every of the FEC blocks, and the K writing rules implemented for writing different FEC blocks of the FEC blocks, respectively.

5. The time and cell de-interleaving circuit according to claim 4, wherein a result of the rule generating unit writing the cells to the second memory device according to the writing rule is equivalent to a result of the cells sequentially written to the second memory device according to a sequence of having undergone time de-interleaving, and the reading rule is a rule of cell de-interleaving.

6. The time and cell de-interleaving circuit according to claim 1, further comprising: a buffering memory, buffering a part of the cells before the cells are written to the first memory device to arrange a sequence for writing the cells to the first memory device; and a selection unit, selecting one of writing the cells of the interleaved signal to the first memory device and writing the cells buffered in the buffering memory to the first memory device.

7. The time and cell de-interleaving circuit according to claim 6, wherein during time de-interleaving and cell de-interleaving, for each cell group, the first memory device is written only once and read only once.

8. The time and cell de-interleaving circuit according to claim 6, wherein a time block of the interleaved signal comprises N FEC blocks, and the buffering memory is at least capable of simultaneously storing N(K1) cells, where N is a positive integer greater than 1.

9. A method, applied to a signal receiver of a communication system operating according to a predetermined transmission protocol, for performing time and cell de-interleaving on an interleaved signal, the interleaved signal comprising a plurality of cells, the method reducing the required number of times a memory storing the interleaved signal is accessed, comprising: providing a first memory device, the first memory device storing the cells of said interleaved signal, the cells read and written one cell group at a time, each cell group comprising K cells, where K is a positive integer greater than 1; providing a second memory device, the second memory device storing the cells read from the first memory device; generating a plurality of permutation rules including a set of writing rules and a set of reading rules according to time interleaving and cell interleaving characteristics of said predetermined broadcasting standard transmission protocol of the interleaved signal, the plurality of permutation rules specifying a respective memory address for reading or writing each of the cells during reading and writing operations; reading the cells from the first memory device, and writing the cells to the second memory device according to a writing rule of the plurality of permutation rules, K consecutive cells written to the second memory device being from a same cell group; and reading the cells from the second memory device according to a reading rule of the permutation rules, wherein the cells read from the second memory device in accordance with the reading rule of the permutation rules are simultaneously time de-interleaved and cell de-interleaved; wherein said permutation rules are generated using the number of cells in each cell group K, a total number of cell groups of the first memory device, a total number of rows of the first memory device, and a total number of columns of the first memory device according to time interleaving and cell interleaving settings of said predetermined broadcasting standard transmission protocol such that the cells of the interleaved signal read from the second memory device in accordance with the reading rule of the permutation rules are simultaneously cell de-interleaved and time de-interleaved.

10. The method according to claim 9, wherein the interleaved signal comprises a plurality of forward error correction (FEC) blocks, the plurality of permutation rules comprise one writing rule and K reading rules, the writing rule implemented for writing every of the FEC blocks, and the K reading rules implemented for reading different FEC blocks of the FEC blocks, respectively.

11. The method according to claim 9, wherein the writing rule causes the cells read from the first memory device to be written to the second memory device according to a sequence of reading the cells from the first memory device.

12. The method according to claim 9, wherein the interleaved signal comprises a plurality of FEC blocks, the permutation rules comprise one of the reading rule and K writing rules, the reading rule implemented for reading every of the FEC blocks, and the K writing rules implemented for writing different FEC blocks of the FEC blocks, respectively.

13. The method according to claim 9, further comprising: providing a buffering memory, the buffering memory buffering a part of the cells before the cells are written to the first memory device; and after receiving the cells and before writing the cells to the first memory device, selectively buffering the cells in the buffering memory.

14. The method according to claim 13, wherein during time de-interleaving and cell de-interleaving, for each cell group, the first memory device is written only once and read only once.

15. The method according to claim 13, wherein a time block of the interleaved signal comprises N FEC blocks, and the buffering memory is at least capable of simultaneously storing N(K1) cells, where N is a positive integer greater than 1.

16. A time and cell de-interleaving circuit, located in a signal receiver of a communication system operating according to a predetermined transmission protocol requiring time de-interleaving and cell de-interleaving on an interleaved signal, the interleaved signal comprising a plurality of cells, the time and cell de-interleaving circuit reducing the required number of times a memory storing the interleaved signal is accessed, comprising: a storage control circuit, controlling an access operation of a first memory device to write and read the cells of said interleaved signal into and from the first memory device, the access operation performed one cell group at a time, each cell group comprising K cells, where K is a positive integer greater than 1; a second memory device, storing the cells read from the first memory device; and a rule generating unit, generating a plurality of permutation rules including a set of writing rules and a set of reading rules according to time interleaving and cell interleaving characteristics of said predetermined broadcasting standard transmission protocol of the interleaved signal, the plurality of permutation rules specifying a respective memory address for reading or writing each of the cells during reading and writing operations, writing the cells read from the first memory device to the second memory device according to a writing rule of the permutation rules to cause K consecutive cells written to the second memory device to be from a same cell group, and reading the cells stored in the second memory device according to a reading rule of the permutation rules, wherein the plurality of permutation rules are generated to cause using the number of cells in each cell group K, a total number of cell groups of the first memory device, a total number of rows of the first memory device, and a total number of columns of the first memory device such that the cells of the interleaved signal read from the second memory device in accordance with the reading rule of the permutation rules to be simultaneously time de-interleaved and cell de-interleaved.

17. The time and cell de-interleaving circuit according to claim 16, wherein the interleaved signal comprises a plurality of FEC blocks, the plurality of permutation rules comprise one writing rule and K reading rules, the writing rule implemented for writing every of the FEC blocks, and the K reading rules implemented for reading different FEC blocks of the FEC blocks, respectively.

18. The time and cell de-interleaving circuit according to claim 17, wherein the writing rule causes the cells read from the first memory device to be written to the second memory device according to a sequence of reading the cells from the first memory device.

19. The time and cell de-interleaving circuit according to claim 16, wherein the interleaved signal comprises a plurality of FEC blocks, the plurality of permutation rules comprise one reading rule and K writing rules, the reading rule implemented for reading every of the FEC blocks, and the K writing rules implemented for writing different FEC blocks of the FEC blocks, respectively.

20. The time and cell de-interleaving circuit according to claim 19, wherein a result of the rule generating unit writing the cells to the second memory device according to the writing rule is equivalent to a result of the cells sequentially written to the second memory device according to a sequence of having undergone time de-interleaving, and the reading rule is a rule of cell de-interleaving.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a block diagram of a conventional signal receiver;

(2) FIG. 2a and FIG. 2b are configuration diagrams of a memory conventionally used for time de-interleaving process;

(3) FIG. 3 is a block diagram of a time de-interleaving circuit and a cell de-interleaving circuit of a conventional signal receiver;

(4) FIG. 4a and FIG. 4b are sequences of writing/reading addresses of a memory in a conventional time de-interleaving process when a memory bandwidth is equal to the size of cells;

(5) FIG. 5 is a schematic diagram of a storage state, a permutation rule and an output sequence of cells of a conventional CDI buffer 142;

(6) FIG. 6a and FIG. 6b are schematic diagrams of storage addresses and reading/writing sequences of cells in a memory in a conventional time de-interleaving process and when a memory bandwidth is four times the size of cells;

(7) FIG. 7a and FIG. 7b are other diagrams of storage addresses and reading/writing sequences of cells in a memory in a conventional time de-interleaving process and when a memory bandwidth is four times the size of cells;

(8) FIG. 8 is a function block diagram of a time and cell de-interleaving circuit according to an embodiment of the present invention;

(9) FIG. 8a is a function block diagram of a time and cell de-interleaving circuit according to another embodiment of the present invention;

(10) FIG. 9a to FIG. 9d are schematic diagrams of memory addresses, cell numbers, reading/writing sequences and permutation rules of a memory 814 and a memory 821 when the present invention is applied for time and cell de-interleaving and a memory bandwidth is four times the size of cells;

(11) FIG. 10a to FIG. 10c are schematic diagrams of memory addresses, cell numbers and reading/writing sequences of a memory 814 when the present invention is applied for time and cell de-interleaving and a memory bandwidth is twice the size of cells;

(12) FIG. 11a to FIG. 11c are schematic diagrams of memory addresses, cell numbers and reading/writing sequences of a memory 814 when the present invention is applied for time and cell de-interleaving and a memory bandwidth is eight times the size of cells;

(13) FIG. 12 shows the number of times of reading/writing a memory 814 under different LDPC block lengths and different modulation modes, and a ratio to the number of times of reading/writing a conventional memory;

(14) FIG. 13 is a function block diagram of a time and cell de-interleaving circuit according to another embodiment of the present invention;

(15) FIG. 14a to FIG. 14d are schematic diagrams of address numbers, cell numbers, read/writing sequences and permutation rules of a memory 1314, a memory 1321 and a memory 1341 when the present invention is applied for time and cell de-interleaving and a memory bandwidth is four times the size of cells;

(16) FIG. 15a to FIG. 15c are schematic diagrams of address numbers, cell numbers and read/writing sequences of a memory 1314 and a memory 1321 when the present invention is applied for time and cell de-interleaving and a memory bandwidth is twice the size of cells;

(17) FIG. 16 shows the number of times of reading/writing a memory 1314 under different LDPC block lengths and different modulation modes, and a ratio to the number of times of reading/writing a conventional memory;

(18) FIG. 17 is a flowchart of a method for performing time and cell de-interleaving according to an embodiment of the present invention; and

(19) FIG. 18 is a flowchart of a method for performing time and cell de-interleaving according to another embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

(20) Technical terms of the application are based on the general definition in the technical field of the application. If the application describes or explains one or some terms, definitions of the terms are based on the description or explanation of the application.

(21) The present invention discloses a time and cell de-interleaving circuit and a method for performing time and cell de-interleaving capable of reducing the number of times of accessing a memory. In possible implementations, one skilled person in the art may choose equivalent elements or steps to implement the disclosure based on the disclosure of the application. That is, the implementation of the disclosure is not limited in the embodiments disclosed in the disclosure. Further, a part of the elements included in the time and cell de-interleaving circuit of the disclosure may be individually known elements. Without affecting the full disclosure and possible implementation of the device, details of the known elements are omitted. Further, the method for performing time and cell de-interleaving of the present invention may be performed by the time and cell de-interleaving circuit of the present invention or an equivalent device. Without affecting full disclosure of the present invention and possible implementation, the description of the method of the application focuses on the steps instead of hardware.

(22) FIG. 8 shows a function block diagram of a time and cell de-interleaving circuit according to an embodiment of the present invention. A time and cell de-interleaving circuit 800 includes a storage circuit 810 and a de-interleaving operation circuit 820. The storage circuit 810 includes a buffering unit 811 and a memory module 812. In the embodiment, the bandwidth of the memory module 812 is w bits (i.e., a word accessed each time is w bits), and the size of one cell is c bits. After the buffering unit 811 (e.g., a first-in-first-out (FIFO) buffer) stores w/c cells (i.e., one word, w bits), the w/c cells are together written into the memory 814 of the memory module 812. The memory module 812 includes a writing address generator 813 and a reading address generator 815, which respectively generate target memory addresses for writing and reading operations of the memory 814. The writing address generator 813 and the reading address generator 815 form a storage control circuit of the memory 814. The de-interleaving operation circuit 820 includes a memory 821 and a rule generating unit 822. The memory 821 may be implemented by a static random access memory (SRAM). The rule generating unit 822 generates a plurality of permutation rules. The cells outputted from the storage circuit 810 are written into and read from the memory according to these permutation rules to complete time and cell de-interleaving. The output of the de-interleaving operation circuit 820 is a result that has undergone time de-interleaving and cell de-interleaving. In this embodiment, the memory 814 is included in the time and cell de-interleaving circuit 800. As shown in FIG. 8a, in practice, the time and cell de-interleaving circuit may also buffer the cells of the interleaved signal by using an external memory. At this point, the time and cell de-interleaving circuit does not internally include the memory 814, and the function of the memory 814 is replaced by an external memory 814a. The time and cell de-interleaving circuit 800a controls the access operation of the interleaved signal from the memory 814a by using the storage control circuit 816.

(23) FIG. 9a, FIG. 9b, FIG. 9c and FIG. 9d are schematic diagrams of memory addresses, cell numbers, reading/writing sequences and permutation rules of the memory 814 and the memory 821 when the present invention is applied for time de-interleaving and a memory bandwidth is four times the size of cells. FIG. 9a depicts address numbers of the memory 814. There are a total of 24 (0 to 23) addresses, and each address may be written by one cell group (including four cells). FIG. 9b depicts a sequence for writing to the memory 814. The cell groups are written sequentially and horizontally from the upper left corner, and a next row is written after a previous row is fully written. The writing address generator 813 generates addresses according to a rule below:

(24) $\mathrm{for}\left(i=0\text{:}i<.Math.\frac{N_c}{4}.Math.N_r\text{:}i=i+1\right)\{C_i=i\mathrm{mod}.Math.\frac{N_c}{4}.Math.K_i=\mathrm{idiv}.Math.\frac{N_c}{4}.Math.{\mathrm{WR}}_i=C_i{N}_r+R_i\}$

(25) In the above, i represents the number of the cell group that the buffering unit 811 sequentially outputs, there are a total of

(26) $\left(\frac{N_c}{4}\right)N_r$
cell groups (the divisor 4 means that each word includes four cells), mod is an operator for obtaining the remainder, and div is an operator for obtaining the quotient, and WR.sub.i is a written address. Thus, written addresses and written contents are as follows. In the 0.sup.th writing operation, the cell group including cells numbered {0, 8, 16, 24} is written to the memory address 0; in the 1.sup.st writing operation, the cell group including cells numbered {32, 40, 48, 56} is written to the memory address 8; in the 2.sup.nd writing operation, the cell group including cells numbered {64, 72, empty string, empty string} is written to the memory address 16 (the empty string is null data, and serves a purpose of forming a cell group with meaningful data); . . . ; in the 22.sup.nd writing operation, the cell group including cells numbered {39, 47, 55, 63} is written to the memory address 15; and in the 23.sup.rd writing operation, the cell group including cells numbered {71, 79, empty string, empty string} is written to the memory address 23.

(27) FIG. 9c depicts the sequence of reading from the memory 814. The cell groups are sequentially and vertically read from the upper left corner, and a next column is read after a previous column is completely read. The reading address generator 815 generates addresses according to a rule below, and the cell groups read from the memory 814 are then written to the memory 821 according to rules below:

(28) $\mathrm{for}\left(i=0\text{:}i<\left(\frac{N_c}{5}2\right)N_r\text{:}i=i+1\right)\{C_i=\left(\mathrm{idiv}8N_r\right)5N_r|\left(\left(i\mathrm{mod}8N_r\right)|N_r\right)\mathrm{div}\left(2N_r\right)R_i=i\mathrm{mod}{N}_r{\mathrm{RD}}_i=C_i{N}_r+R_i$

(29) Writing into the memory 821:

(30) TABLE-US-00001 { if ((i div N.sub.r) mod 8) = 0, DRAM[0: 32 4 1] (4 cells, when r mod 4 = 0) else if ((i div N.sub.r) mod 8) = 1, DRAM[0:32 1 1] (1 cell, when r mod 4 = 0) else if ((i div N.sub.r) mod 8) = 2, DRAM[32 1:32 4 1] (3 cells, when r mod 4 = 1) else if ((i div N.sub.r) mod 8) = 3, DRAM[0:32 2 1] (2 cells, when r mod 4 = 1) else if ((i div N.sub.r) mod 8) = 4, DRAM[32 2:32 4 1] (2 cells, when r mod 4 = 2) else if ((i div N.sub.r) mod 8) = 5, DRAM[0:32 3 1] (3 cells, when r mod 4 = 2) else if ((i div N.sub.r) mod 8) = 6, DRAM[32 3:32 4 1] (1 cell, when r mod 4 = 3) else if ((i div N.sub.r) mod 8) = 7, DRAM[0:32 4 1] (4 cells, when r mod 4 = 3) } }

(31) RD.sub.i is an address for reading from the memory 814. It should be noted that, only a part of the cells of the cell group read from the memory 814 are written to the memory 821 in some situations. As shown by the above rules, DRAM[X:Y] represent bit addresses of the read cell group to be written to the memory 821. For example, DRAM[0:127] means that all of the 128 bits in the cell group (i.e., four cells) are to be written to the memory 821; DRAM[0:31] and DRAM[63:127] mean that data of the first 32 bits (i.e., one cell) and the last 64 bits (i.e., two cells) is to be written to the memory 821, and so forth. In the above, r represents the number of the FEC block. It is discovered that, in this embodiment, there are four types of distributions of all of the cells of one FEC block in the memory 821:

(32) 1. For the FEC block numbered 4n (where n is a positive integer greater than 0), all data of 8 cell groups is successively written, and data of the 1.sup.st cell of the 8 following cell groups is then successively written.

(33) 2. For the FEC block numbered 4n+1, data of the last 3 cells of 8 cell groups is successively written, and data of the first 2 cells of the 8 following cell groups is then successively written.

(34) 3. For the FEC block numbered 4n+2, data of the last 2 cells of 8 cell groups is successively written, and data of the first 3 cells of the 8 following cell groups is then successively written.

(35) 4. For the FEC block numbered 4n+3, data of the last cell of 8 cell groups is successively written, and all data of the 8 following cell groups is then successively written.

(36) Thus, read addresses and read contents of the memory 814, and contents outputted to the de-interleaving operation circuit 820 from the memory 814 are as follows. In the 0.sup.th reading operation, the cell group including cells numbered {0, 8, 16, 24} are read from the memory address 0, and all of the read data (DRAM[0:127]) is outputted; in the 1.sup.st reading operation, the cell group including cells numbered {1, 9, 17, 25} is read from the memory address 1, and all of the read data (DRAM[0:127]) is outputted; . . . ; in the 7.sup.th reading operation, the cell group including cells numbered {7, 15, 23, 31} is read from the memory address 7, and all of the read data (DRAM[0:127]) is outputted; in the 8.sup.th reading operation, the cell group including cells numbered {32, 40, 48, 56} is read from the memory address 8, and the first cell (DRAM[0:31]) of the read data is outputted; . . . ; in the 15.sup.th reading operation, the cell group including cells numbered {39, 47, 55, 63} is read from the memory address 15, and the first cell (DRAM[0:31]) of the read data is outputted; in the 16.sup.th reading operation, the cell group including cells numbered {32, 40, 48, 56} is read from the memory address 8, and the last 3 cells (DRAM[32:127]) of the read data are outputted; . . . , in the 23.sup.rd reading operation, the cell group including cells numbered {39, 47, 55, 63} is read from the memory address 15, and the last three cells (DRAM[32:127]) of the read data are outputted; in the 24.sup.th reading operation, the cell group including cells numbered {64, 72, empty string, empty string} is read from the memory address 16, and the first two cells (DRAM[0:63]) of the read data are outputted; . . . ; in the 31.sup.st reading operation, cell group including cells numbered {71, 79, empty string, empty string} is read from the memory address 23, and the first two cells (DRAM[0:63]) of the read data are outputted.

(37) The rule generating unit 822 may generate a plurality of permutation rules, including writing rules and reading rules. FIG. 9d shows a schematic diagram of a storage state, a permutation rule and an output sequence of the memory 821 in the de-interleaving operation circuit 820 according to an embodiment of the present invention. In one preferred embodiment, when the cells are written to the memory 821, the cells are written to the memory 821 according to an increasing order of the addresses of the memory 821 as well as the sequence of reading the cells from the memory 814. Taking the 4n.sup.th FEC block for example, it is written according to the sequence of the cells outputted from the memory 814 to obtain the result shown on the left of the drawing. The memory 821 is read according to the reading rule shown in the middle of the drawing to obtain the cell de-interleaved result shown on the right of the drawing. For the (4n+1).sup.th FEC block, it has the same writing rule as the writing rule of the 4n.sup.th FEC block but a different reading rule. The reason is that, in this embodiment (w/c=4), the cells of one FEC block have four types of distributions (as previously described), and so the same writing rule needs to coordinate with four different reading rules. These four reading rules may be represented as follows:

(38) For the block numbered 4n, the reading rule of L.sub.r, 0(q) is used:

(39) $L_{r,0}\left(q\right)=\{\begin{array}{cc}\mathrm{if}{L}_r\left(q\right)<N_{r}4,& \left(L_r\left(q\right)\mathrm{mod}{N}_r\right)4+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)\\ \mathrm{else},& L_r\left(q\right)\end{array}$

(40) For the block numbered 4n+1, the reading rule of L.sub.r, 1(q) is used:

(41) $L_{r,1}\left(q\right)=\{\begin{array}{cc}\mathrm{if}{L}_r\left(q\right)<N_{r}3,& \left(L_r\left(q\right)\mathrm{mod}{N}_r\right)3+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)\\ \mathrm{else},& \left(L_r\left(q\right)\mathrm{mod}{N}_r\right)2+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)+\left(N_r-1\right)3\end{array}$

(42) For the block numbered 4n+2, the reading rule of L.sub.r, 2(q) is used:

(43) $L_{r,2}\left(q\right)=\{\begin{array}{cc}\mathrm{if}{L}_r\left(q\right)<N_{r}2,& \left(L_r\left(q\right)\mathrm{mod}{N}_r\right)2+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)\\ \mathrm{else},& \left(L_r\left(q\right)\mathrm{mod}{N}_r\right)3+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)+\left(N_r-1\right)2\end{array}$

(44) For the block numbered 4n+3, the reading rule of L.sub.r, 3(q) is used:

(45) $L_{r,3}\left(q\right)=\{\begin{array}{cc}\mathrm{if}{L}_r\left(q\right)<N_{r}1,& \left(L_r\left(q\right)\mathrm{mod}{N}_r\right)1+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)\\ \mathrm{else},& \left(L_r\left(q\right)\mathrm{mod}{N}_r\right)4+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)+\left(N_r-1\right)1\end{array}$

(46) Wherein, L.sub.r(q) is the reading rule of the sequence of the input cells having undergone time de-interleaving (corresponding to a simple drawing in FIG. 5), and is used for performing cell de-interleaving. L.sub.r(q) is usually specified in the specifications of broadcasting standards. For example, when the time and cell de-interleaving circuit of the present invention is applied to a DVB-T2 system, the corresponding L.sub.r(q) may be obtained from the DVB-T2 specifications.

(47) In another embodiment, there are four writing rules (used in turn by the FEC blocks numbered 4n, 4n+1, 4n+2 and 4n+3), and there is only one reading rule. These four reading rules may be represented as follows:

(48) The writing rule of the FEC block numbered 4n is:

(49) TABLE-US-00002 for (i 0; i < N.sub.r 4; i i + 1){ CDI_WR.sub.i = (i div 4) + (i mod 4) N.sub.r } for (i = N.sub.r 4; i < N.sub.r 5; i = i + 1){ CDI_WR.sub.i = i }

(50) The writing rule of the FEC block numbered 4n+1 is:

(51) TABLE-US-00003 for (i = 0; i < N.sub.r 3; i = i + 1){ CDI_WR.sub.i = (i div 3) + (i mod 3) N.sub.r } for (i = N.sub.r 3; i < N.sub.r 5; i = i + 1){ j = i 3N.sub.r CDI_WR.sub.i = (j div 2) + (j mod 2) N.sub.r + 3N.sub.r }

(52) The writing rule of the FEC block numbered 4n+2 is:

(53) TABLE-US-00004 for (i = 0; i < N.sub.r 2; i = i + 1){ CDI_WR.sub.i = (i div 2) + (i mod 2) N.sub.r } for (i = N.sub.r 2; i < N.sub.r 5; i = i + 1){ j = i 2N.sub.r CDI_WR.sub.i = (j div 3) + (j mod 3) N.sub.r + 2N.sub.r }

(54) The writing rule of the FEC block numbered 4n+3 is:

(55) TABLE-US-00005 for (i = 0; i < N.sub.r 1; i = i + 1){ CDI_WR.sub.i = i } for (i = N.sub.r 1; i < N.sub.r 5; i = i + 1){ j = i N.sub.r CDI_WR.sub.i = (j div 4) + (j mod 4) N.sub.r + N.sub.r }

(56) Wherein, CDI_WRi is the writing address for writing the i.sup.th cell to the memory 821.

(57) In practice, the result of writing the cells outputted from the storage circuit 810 to the memory 821 according to the above sequence is equivalent to the result of sequentially writing the cells having undergone time de-interleaving to the memory 821, i.e., as shown by the CDI buffer in FIG. 5. Thus, as the reading rule of this embodiment is the rule of a conventional cell de-interleaving process (as the permutation rule shown in FIG. 5), the final output result of the de-interleaving operation circuit 820 is a result that is complete with time de-interleaving and cell de-interleaving.

(58) It is known from the foregoing description that, to reduce the number of times of accessing the memory 814, the cells have not yet undergone time de-interleaving when they are read out from the memory 814. Thus, when generating the permutation rules, the rule generating unit 822 needs to simultaneously consider time interleaving characteristics and cell interleaving characteristics of the cells to accordingly generate appropriate permutation rules, such that the cells of the interleaved signal are simultaneously complete with time de-interleaving and cell de-interleaving after the cells are accessed from/to the memory 821. In practice, the rule generating unit 822 may be a storage control circuit of the memory 821, and may be formed by a logic circuit. The rule generating unit 822 learns the time de-interleaving characteristics and the cell de-interleaving characteristics of the cells of the interleaved signal according to the broadcasting standard of the interleaved signal, and obtains the permutation rules according to the rules of the cells accessed from/to the memory 814. Further, the rule generating unit 822 writes the cells read from the memory 814 to the memory 821 according to the permutation rules to complete time de-interleaving and cell de-interleaving.

(59) FIG. 10a, FIG. 10b and FIG. 10c show schematic diagrams of memory addresses, cell numbers and reading/writing sequences of the memory 814 when the present invention is applied for time and cell de-interleaving and a memory bandwidth is twice the size of cells. FIG. 10a depicts the address numbers of the memory 814. There are 40 (0 to 39) addresses, and each of the addresses may be written by one cell group (including two cells). FIG. 10b depicts the sequence for writing to the memory 814. The cell groups are written sequentially and horizontally from the upper left corner, and a next row is written after a previously row is fully written. The writing address generator 813 generates the addresses according to the rule below:

(60) $\mathrm{for}\left(i=0;i<.Math.\frac{N_c}{2}.Math.N_r;i=i+1\right)\{C_i=i\mathrm{mod}.Math.\frac{N_c}{2}.Math.R_i=i\mathrm{div}.Math.\frac{N_c}{2}.Math.{\mathrm{WR}}_i=C_i{N}_r+R_i\}$

(61) Wherein, i represents the number of the cell group that the buffer unit 811 sequentially outputs. There are a total of

(62) $\left(\frac{N_c}{2}\right)N_r$
cell groups (the divisor 2 means that each word includes two cells).

(63) FIG. 10c depicts the sequence for reading the memory 814. The cell groups are read sequentially and vertically from the upper left corner, and a next column is read after a previous column is completely read. The reading address generator 815 generates the addresses according to the rule below:

(64) 0$\mathrm{for}\left(i=0;i\left(\frac{N_c}{5}3\right)N_r;i=i+1\right)\{C_i=\left(i\mathrm{div}6N_r\right)4N_r+\left(\left(i\mathrm{mod}6N_r\right)+N_r\right)\mathrm{div}\left(2N_r\right)R_i=i\mathrm{mod}{N}_r{\mathrm{RD}}_i=C_i{N}_r+R_i$

(65) writing to the memory 821:

(66) TABLE-US-00006 { if ((i div N.sub.r) mod 6) = 0, DRAM[0: 32 2 1] (2 cells, when r mode 2 = 0) else if ((i div N.sub.r) mod 6) = 1, DRAM[0:32 2 1] (2 cells, when r mode 2 = 0) else if ((i div N.sub.r) mod 6) = 2, DRAM[0:32 1 1] (1 cell, when r mode 2 = 0) else if ((i div N.sub.r) mod 6) = 3, DRAM[0:32 2 1] (1 cell, when r mode 2 = 1) else if ((i div N.sub.r) mod 6) = 4, DRAM[0:32 2 1] (2 cells, when r mode 2 = 1) else if ((i div N.sub.r) mod 6) = 5, DRAM[0:32 2 1] (2 cells, when r mode 2 = 1)

(67) It should be noted that, only a part of the cells of the cell group read from the memory 814 are written to the memory 821 in some situations. It is discovered that, in this embodiment, there are only two types of distributions for all of the cells of one FEC block in the memory 821:

(68) 1. For the FEC block numbered 2n, all data of 16 cell groups is successively written, and a first half of data of 8 following cell groups is successively written.

(69) 2. For the FEC block numbered 2n+1, data of a second half of 8 cell groups is successively written, and all data of 16 following cell groups is then successively written.

(70) The plurality of permutation rules generated by the rule generating unit 822 include writing rules and reading rules. In one preferred embodiment, when the cells are written to the memory 821, the cells are written to the memory 821 according to an increasing order of the addresses of the memory 821 as well as the sequence of reading the cells from the memory 814. Thus, in this embodiment (w/c=2), there are two types of distributions for the cells of one FEC block in the memory 821 (as previously described), and so the same writing rule needs to coordinate with two different reading rules (used in turn by the FEC blocks numbered 2n and 2n+1). These two reading rules may be represented as follows:

(71) For the block numbered 2n, the reading rule of L.sub.r, 0(q) is used:

(72) $L_{r,0}\left(q\right)=\{\begin{array}{cc}\mathrm{if}{L}_r\left(q\right)<N_{r}2,& \left(L_r\left(q\right)\mathrm{mod}{N}_r\right)2+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)\\ \mathrm{else}\mathrm{if}{L}_r\left(q\right)<N_{r}4,& \begin{array}{c}\left(L_r\left(q\right)\mathrm{mod}{N}_r\right)2+\\ \left(L_r\left(q\right)\mathrm{div}{N}_r\right)+\left(N_r-1\right)2\end{array}\\ \mathrm{else},& L_r\left(q\right)\end{array}$

(73) For the block numbered 2n+1, the reading rule of L.sub.r, 1(q) is used:

(74) $L_{r,1}\left(q\right)=\{\begin{array}{cc}\mathrm{if}{L}_r\left(q\right)<N_{r}1,& L_r\left(q\right)\\ \mathrm{else}\mathrm{if}{L}_r\left(q\right)<N_{r}3,& \begin{array}{c}\left(L_r\left(q\right)\mathrm{mod}{N}_r\right)2+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)+\\ \left(N_r-1\right)1\end{array}\\ \mathrm{else},& \begin{array}{c}\left(L_r\left(q\right)\mathrm{mod}{N}_r\right)2+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)+\\ \left(N_r-1\right)3\end{array}\end{array}$

(75) In another preferred embodiment, there are two writing rules (used in turn by the FEC blocks numbered 2n and 2n+1). These two writing rules may be represented as follows:

(76) The writing rule of the FEC block numbered 2n is:

(77) TABLE-US-00007 for (i = 0; i < N.sub.r 2; i = i + 1){ CDI_WR.sub.i = (i div 2) + (i mod 2) N.sub.r } for (i = N.sub.r 2; i < N.sub.r 4; i = i + 1){ CDI_WR.sub.i = ((i 2N.sub.r) div 2) + ((i 2N.sub.r) mod 2) N.sub.r + 2N.sub.r = (i div 2) (i mod 2) N.sub.r | N.sub.r } for (i N.sub.r 4; i < N.sub.r 5; i i + 1){ CDI_WR.sub.i = i }

(78) The writing rule of the FEC block numbered 2n+1 is:

(79) TABLE-US-00008 for (i = 0; i < N.sub.r 1; i = i + 1){ CDI_WR.sub.i = i } for (i = N.sub.r 1; i < N.sub.r 3; i = i + 1){ CDI_WR.sub.i = ((i N.sub.r) div 2) + ((i N.sub.r) mod 2) N.sub.r + N.sub.r } for (i = N.sub.r 3; i < N.sub.r 5; i = i + 1){ CDI WR.sub.i = ((i 3N.sub.r) div 2) + ((i 3N.sub.r) mod 2) N.sub.r + 3N.sub.r }

(80) The corresponding reading rule is the rule of a conventional cell de-interleaving process.

(81) FIG. 11a, FIG. 11b and FIG. 11c show schematic diagrams of memory addresses, cell numbers and reading/writing sequences of the memory 814 when the present invention is applied for time and cell de-interleaving and a memory bandwidth is eight times the size of cells. Operation details may be deduced by one person skilled in the art based on the above embodiments, and shall be omitted herein.

(82) FIG. 12 shows the number of times of reading/writing the memory 814 (when the memory bandwidth is twice, four times and eight times the size of cells) under different LDPC block lengths and different modulation modes, and the ratio to the number of times of reading/writing a conventional memory. The results show that, under the same LDPC block length and the same modulation mode, regardless of the multiple (w/c) of the bandwidth size to the size of cells, compared to the prior art, the present invention effectively reduces the number of times of accessing (reading/writing) the memory, and such effect is particularly significant as w/c gets larger.

(83) FIG. 13 shows a function block diagram of a time and cell de-interleaving circuit according to another embodiment of the present invention. A time and cell de-interleaving circuit 1300 includes a storage circuit 1310, a de-interleaving operation circuit 1320, a selection unit 1330 and a buffering memory module 1340. The storage circuit 1310 includes a buffering unit 1311 and a memory module 1312. In this embodiment, the memory module 1312 has a bandwidth of w bits, and the size of one bit is c bits. After the buffering unit 1311 (e.g., a FIFO buffer) stores w/c cells, the w/c cells are together written into the memory 1314 of the memory module 1312. The memory module 1312 includes a writing address generator 1313 and a reading address generator 1315, which respectively generate target memory addresses for writing and reading operations of the memory 1314. The buffering memory module 1340 includes a buffering memory 1341 and an address generator 1342. The address generator 1342 generates writing addresses or reading addresses for accessing the buffering memory 1341. In practice, for example, the buffering memory module 1340 may be an SRAM. The de-interleaving operation circuit 1320 includes a memory 1321 and a rule generating unit 1322. The memory 1321 may be implemented by an SRAM. The rule generating unit 1322 generates a plurality of permutation rules, according to which the cells outputted from the storage circuit 1310 are written to and read from the memory 1321 to complete time and cell de-interleaving. The output of the de-interleaving operation circuit 1320 is a result that has undergone time de-interleaving and cell de-interleaving.

(84) FIG. 14a, FIG. 14b, FIG. 14c and FIG. 14d show schematic diagrams of address numbers, cell numbers, read/writing sequences and permutation rules of the memory 1314, the memory 1321 and the memory 1341 when the present invention is applied for time and cell de-interleaving and a memory bandwidth is four times the size of cells. FIG. 14a depicts the address numbers of the memory 1314. There are a total of 20 addresses (16 in the horizontal direction, and 4 in the vertical direction), and each of the addresses may be written by one cell group (including 4 cells). The size of the memory 1314 may be represented by a general equation as: horizontal

(85) $\frac{N_c}{5}{N}_{r}4$
cells, and vertical

(86) $\frac{N_c}{5}.Math.\frac{N_r}{2}.Math.4$
cells. FIG. 14b depicts buffered contents in the buffering memory 1341 and the sequence of the selection unit 1330 writing data to the memory 1314. In the previous embodiment, when one cell group includes 4 cells (as shown in FIG. 9), the data belonging to the same FEC block and the data belonging to different FEC blocks form a cell group that is written to the memory 814 (e.g., in FIG. 9, the cell numbered 32 and the cells numbered 40, 48 and 56 form one cell group that is written to the memory 814). Thus, in a reading operation, one reading operation needs to be performed on each of the first and second FEC blocks for that cell group. To further reduce the number of times of accessing (reading/writing) the memory, in this embodiment, some cells are first stored using the buffering memory 1341 to arrange the sequence of writing these cells to the memory module, and the selection unit 1330 determines to output the newly arrived cells or the buffered cells to the storage circuit 1314. As such, the written data is appropriately reorganized, so that the cell groups are read from the memory 1314 more efficiently to reduce the number of times of accessing the memory 1314. The size of the buffering memory 1341 is N.sub.FEC(w/c1) cells. In this example, N.sub.FEC=N.sub.c/3=2, and w/c=4. Thus, the buffering memory 1341 is capable of storing a total of 23=6 cells. The writing address generator 1313 generates addresses according to the rule below:

(87) For horizontal memory addresses:

(88) $\mathrm{for}\left(i=0;i<\frac{N_c}{5}{N}_r;i=i+1\right)$$\left\{\begin{array}{c}{C}_i=i\mathrm{mod}\frac{N_c}{5}\\ R_i=i\mathrm{div}\frac{N_c}{5}\\ {\mathrm{WR}}_i=C_i{N}_r+R_i\end{array}\right\}$

(89) For vertical memory addresses:

(90) $\mathrm{for}\left(i=0;i<\frac{N_c}{5}{N}_r;i=i+1\right)$$\left\{\begin{array}{c}{C}_i=i\mathrm{mod}\frac{N_c}{5}\\ R_i=i\mathrm{div}\frac{N_c}{5}\\ {\mathrm{WR}}_i=C_i.Math.\frac{N_r}{4}.Math.+R_i\end{array}\right\}$

(91) Writing addresses and written contents are as follows. In the 0.sup.th writing operation, the cell group including cells numbered {0, 8, 16, 24} is written to the horizontal address 0, and the buffering memory 1341 buffers the cell numbered 32; in the 1.sup.st writing operation, the cell group including cells numbered {40, 48, 56, 64} is written to the horizontal memory address 8, and the buffering memory 1314 buffers the cell numbered 72; in the 2.sup.nd writing operation, the cell group including cells numbered {1, 9, 17, 25} is written to the horizontal address 1, and the buffering memory 1341 buffers the cell numbered 33; . . . ; in the 6.sup.th writing operation, the cell group including the cells numbered {3, 11, 19, 27} is written to the horizontal memory address 3; in the 7.sup.th writing operation, the cells numbered 32, 33 and 34 are first read from the buffering memory 1341, and the newly arrived cell numbered 35 and the read cells form one cell group, which is then written to the vertical memory address 2; in the 8.sup.th writing operation, the cell group including cells numbered {43, 51, 59, 67} is written to the horizontal memory address 11; in the 9.sup.th writing operation, the cells numbered 72, 73, and 74 are read from the buffering memory 1314, and the newly arrived cell numbered 75 and the read cells form one cell group, which is then written to the vertical memory address 2; in the 10.sup.th writing operation, the cell group including cells numbered {4, 12, 20, 28} is written to the horizontal memory address 4, and the buffering memory 1341 buffers the cell numbered 36; in the 11.sup.th writing operation, the cell group including the cells numbered {44, 52, 60, 68} is written to the horizontal memory address 12, and the buffering memory 1341 buffers the cell numbered 76; . . . ; in the 17.sup.th writing operation, the cells numbered 36, 37 and 38 are read from the memory 1341, the newly arrived cell numbered 39 and the read cells form one cell group, which is then written to the vertical memory address 1; in the 18.sup.th writing operation, the cell group including cells numbered {47, 55, 63, 71} is written to the horizontal memory address 15; and in the 19.sup.th writing operation, the cells numbered 76, 77 and 78 are read from the buffering memory 1341, the newly arrived cell numbered 79 and the read cells form one cell group, which is then written to the vertical memory address 3.

(92) FIG. 14C shows a sequence for reading from the memory 1314. The reading address generator 1315 generates addresses according to the rules below:

(93) For horizontal memory addresses:

(94) $\mathrm{for}\left(i=0;i<\frac{N_c}{5}{N}_r;i=i+1\right)$$\left\{\begin{array}{c}{C}_i=i\mathrm{div}{N}_r\\ R_i=i\mathrm{mod}{N}_r\\ {\mathrm{RD}}_i=C_i{N}_r+R_i=i\end{array}\right\}$

(95) For vertical memory addresses:

(96) $\mathrm{for}\left(i=0;i<\frac{N_c}{5}.Math.\frac{N_r}{4}.Math.;i=i+1\right)$$\left\{\begin{array}{c}{C}_i=i\mathrm{div}.Math.\frac{N_r}{4}.Math.\\ R_i=i\mathrm{mod}.Math.\frac{N_r}{4}.Math.\\ {\mathrm{RD}}_i=C_i.Math.\frac{N_r}{4}.Math.+R_i=i\end{array}\right\}$

(97) In the above equations, RD.sub.i is a read address. Read addresses and read contents are as follows. In the 0.sup.th reading operation, the cell group including cells numbered {0, 8, 16, 24} is read from the horizontal memory address 0, and written to the memory 1321; in the 1.sup.st reading operation, the cell group including cells numbered {1, 9, 17, 25} is read from the horizontal memory address 1, and written to the memory 1321; . . . ; in the 8.sup.th reading operation, the cell group including cells numbered {32, 33, 34, 35} is read from the vertical memory address 0, and written to the memory 1321; in the 9.sup.th reading operation, the cell group including cells numbered {36, 37, 38, 39} is read from the vertical memory address 1, and written to the memory 1321; in the 10.sup.th reading operation, the cell group including cells numbered {40, 48, 56, 64} is read from the horizontal memory address 8, and written to the memory 1321; . . . ; in the 18.sup.th reading operation, the cell group including cells numbered {72, 73, 74, 75} is read from the vertical memory address 2, and written to the memory 1321; and in the 19.sup.th reading operation, the cell group including cells numbered {76, 77, 78, 79} is read from the vertical memory address 3, and are written to the memory 1321.

(98) FIG. 14d shows a schematic diagram of a storage state, permutation rules and an output sequence of cells in the memory 1321 of the de-interleaving operation circuit 1320 of the present invention. In one preferred embodiment, the cells are sequentially written to the memory 1321 according to an increasing order of the addresses of the memory 1321 as well as the sequence of reading the cells from the memory 1314. As shown in FIG. 14d, taking the 0.sup.th FEC block for example, it is written according to the sequence of the cells outputted from the memory 1314 to obtain the result shown on the left of the drawing. The memory 1321 is read according to the reading rule shown in the middle of the drawing to obtain the cell de-interleaved result shown on the right of the drawing. For the 1.sup.st FEC block, it has the same writing rule and the same reading rule as the writing rule of the 0.sup.th FEC block. The reason is that, in this embodiment, the relative position for reading data from the memory 1314 is the same for every FEC block, and so the same arrangement is also present in the memory 1321. Thus, only one reading rule needs to be followed. This reading rule may be represented as follows:

(99) $L_{r,\mathrm{new}}\left(q\right)=\{\begin{array}{cc}\mathrm{if}{L}_r\left(q\right)<N_{r}4,& \left(L_r\left(q\right)\mathrm{mod}{N}_r\right)4+\left(L_r\left(q\right)\mathrm{div}{N}_r\right)\\ \mathrm{else},& L_r\left(q\right)\end{array}$

(100) The new reading rule (L.sub.r, new(q)) may have different operation methods according to the range of L.sub.r(q). L.sub.r(q) is the reading rule of the sequence of the input cells having undergone time de-interleaving (corresponding to a simple drawing in FIG. 5), and is used for performing cell de-interleaving.

(101) In another preferred embodiment, the rule generating unit 1322 changes the sequence for writing the cells to memory 1321, such that the sequence of writing the cells to the memory 1321 is equivalent to the sequence of having undergone time de-interleaving. Thus, the reading rule used for cell de-interleaving of the prior art can be used for reading the cells from the memory 1321, and need not be adjusted. This writing rule is as follows:

(102) TABLE-US-00009 for (i = 0; i < N.sub.r 4; i = i + 1){ CDI_WR.sub.i = (i div 4) (i mod 4) N.sub.r } for (i = N.sub.r 4; i < N.sub.r 5; i = i + 1){ CDI_WR.sub.i i }

(103) FIG. 15a, FIG. 15b and FIG. 15c show schematic diagrams of address numbers, cell numbers and read/writing sequences of the memory 1314 and the memory 1321 when the present invention is applied for time and cell de-interleaving and a memory bandwidth is twice the size of cells. Associated operation details may be deduced by one person skilled in the art based on the foregoing embodiments, and shall be omitted herein.

(104) FIG. 16 shows the number of times of reading/writing the memory 1314 (when the memory bandwidth is twice and four times the size of cells) under different LDPC block lengths and different modulation modes, and the ratio to the number of times of reading/writing a conventional memory. The results show that, under the same LDPC block length and the same modulation mode, regardless of the ratio (w/c) of the bandwidth size to the size of cells, compared to the prior art, the present invention effectively reduces the number of times of accessing (reading/writing) the memory, and such effect is particularly significant as w/c gets larger.

(105) FIG. 17 shows a flowchart of a method for performing time and cell de-interleaving according to an embodiment of the present invention. In addition to the foregoing time and cell de-interleaving circuit, the present invention correspondingly discloses a method for performing time and cell de-interleaving method applied to a signal receiver of a communication system. The method may be performed by the foregoing time and cell de-interleaving circuit 800 or an equivalent circuit. As shown in FIG. 17, the method for performing time and cell de-interleaving according to an embodiment of the present invention includes following steps.

(106) In step S1710, a first memory is provided. The first memory stores a plurality of cells of an interleaved signal. The interleaved signal includes a plurality of FEC blocks, and each of the FEC blocks includes a plurality of cells. Reading/Writing operations of the first memory are performed in a unit of one cell group (i.e., a word of the first memory) that includes K cells, where K is a positive integer greater than 1.

(107) In step S1720, a second memory is provided. The second memory stores the cells read from the first memory, and is capable of simultaneously storing all cells of one FEC block. The cells read from the first memory are not complete with time de-interleaving; that is to say, the sequence of the cells read from the first memory is not in a sequence of having undergone time de-interleaving.

(108) In step S1730, the cells are read from the first memory, and are written to the second memory according to a writing rule of a plurality of permutation rules.

(109) In step S1740, the cells are read from the second memory according to a reading rule of the permutation rules, such that the cells read from the second memory are complete with time de-interleaving and cell de-interleaving.

(110) In one preferred embodiment, the cells of each FEC block are written to the second memory according to the same writing rule, but the cells are read from the second memory according to different reading rules based on different FEC blocks. The writing rule is sequentially writing to the second memory according to the sequence of reading from the first memory. There are K corresponding reading rules, which are used in turn by the FEC blocks according to the sequence of writing to the second memory.

(111) In another preferred embodiment, the cells of each FEC block are read from the second memory according to the same reading rule, but the cells are written to the second memory according to different writing rules based on different FEC blocks. There are K corresponding writing rules, which are used in turn by the FEC blocks according to the sequence of writing to the second memory. The cells written to the second memory according to the writing rule display the distribution of having undergone time de-interleaving, and so the K writing rules correspond to the same reading rule. The reading rule is a rule of cell de-interleaving of the prior art, i.e., the cells read from the second memory according to the reading rule are complete with cell de-interleaving.

(112) FIG. 18 shows a flowchart of a method for performing time and cell de-interleaving according to another embodiment of the present invention. This method may be performed by the foregoing time and cell de-interleaving circuit 1300 or an equivalent device. As shown in FIG. 18, the method for performing time and cell de-interleaving according to an embodiment of the present invention includes following steps.

(113) In step S1810, a first memory is provided. The first memory stores a plurality of cells of an interleaved signal. The interleaved signal includes a plurality of FEC blocks, and each of the FEC blocks includes a plurality of cells. Reading/Writing operations of the first memory are performed in a unit of one cell group (i.e., a word of the first memory) that includes K cells, where K is a positive integer greater than 1.

(114) In step S1820, a second memory is provided. The second memory stores the cells read from the first memory, and is capable of simultaneously storing all cells of one FEC block. The cells read from the first memory are not complete with time de-interleaving; that is to say, the sequence of the cells read from the first memory is not in a sequence of having undergone time de-interleaving.

(115) In step S1830, after receiving the cells and before writing the cells to the first memory, the cells are selectively buffered. Some of the cells are first buffered before being stored to the first memory, and jointly form one cell group with later cells and written to the first memory. As such, during the process of reading all of the cells of the same FEC block, data of other FEC blocks is not read, hence enhancing the reading efficiency.

(116) In step S1840, the cells are read from the first memory, and written to the second memory according to a writing rule of a plurality of permutation rules.

(117) In step S1850, the cells are read from the second memory according to a reading rule of the permutation rules, such that the cells read from the second memory are complete with time de-interleaving and cell de-interleaving.

(118) In this method, for the same cell group, the first memory is read once and written once. The cells of each FEC block are written to the second memory according to the same writing rule, and read according to the same reading rule. In one preferred embodiment, the reading rule is writing to the second memory according to the sequence of reading the cells from the first memory, and the sequence of the cells read according to the reading rule are in a sequence of having undergone time de-interleaving and cell de-interleaving. In another preferred embodiment, the cells written to the second memory according to the writing rule display a distribution of having undergone time de-interleaving, and the reading rule is a rule of cell de-interleaving of the prior art; that is, the cells read from the second memory according to the reading rule are complete with cell de-interleaving.

(119) 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.