Dynamic minimum-memory interleaving
View Patent ↗Minimum-memory-implementation is available with any depth and period in DSL interleaving/deinterleaving, always allowing the minimum amount of memory to be used in both transmitter and receiver without loss of performance or of basic triangular structure, even if the interleaver/deinterleaver parameters change dynamically. A novel cell-scheduling process ensures availability of the minimum amount of memory (or any other desired memory usage) to implement an image of the perfect triangle and works for any co-prime depth and interleaver period. Minimal memory use may be further characterized by a simple off-line method that determines an addressing order for each of the memory cells in a minimum-memory (or other) implementation of an interleaver/deinterleaver according to the invention. Time variation of interleaver depth in operation can be accommodated easily with absolute minimum memory requirement at all time instants.
1. A method for performing convolutional interleaving or deinterleaving of a data flow, with a depth D and a period I, the method comprising:
determining a schedule for each of a plurality of R memory cells based on an array having a plurality of rows, each row comprising a first element defining a period index P and a second element defining a byte index B, wherein the array is constructed by:
generating a first row of the array, comprising:
setting the first element of the first row of the array equal to a period index initialization value;
setting the second element of the first row of the array equal to a byte index initialization value;
generating a next row of the array, comprising:
setting P equal to the period index initialization value;
setting B equal to the byte index initialization value;
setting a position index L equal to one of the following:
B+(B*(D−1)); or
B+((I−1−B)*(D−1));
resetting P, wherein P is one of the following:
P
=
P
+
⌊
B
I
⌋
when the position index L equals B+(B*(D−1)); or
P
=
P
+
⌊
L
I
⌋
when the position index L equals B+((I−1−B)*(D−1));
resetting B, wherein B=L mod I;
setting the first element of the next row of the array equal to P; and
setting the second element of the next row of the array equal to B; and
repeating generating the next row of the array until the second element of the next row of the array equals the second element of the first row of the array;
performing for each time sample the following operations:
selecting a first memory cell from the R memory cells based on the schedules of the R memory cells;
reading a first byte stored in the first memory cell;
writing the first byte to the interleaver output;
receiving a second byte at the input of the interleaver;
writing the second byte to the first memory cell.
2. The method of claim 1 wherein selecting a first memory cell from the R memory cells based on the schedules of the R memory cells comprises examining the schedules of the R memory cells to identify the memory cell whose schedule includes a current time sample.
3. The method of claim 1 wherein selecting a first memory cell from the R memory cells based on the schedules of the R memory cells comprises reading a scheduling table, wherein the scheduling table has rows and columns corresponding to period and byte indices, and wherein the contents of the table consist of pointers to memory cells for period/byte index pairs corresponding to time samples.
4. The method of claim 1 wherein
R
=
(
D
-
1
)
·
(
I
-
1
)
2
.
5. The method of claim 1 , further comprising:
determining a first schedule set for a plurality of R memory cells, wherein:
D is a first depth;
I is an interleaving period; and
R is based on D and I;
performing the read and write operations on the R memory cells using the first schedule set;
determining a second schedule set for a plurality of R′ memory cells, wherein:
D′ is a second depth; and
R′ is based on D′ and I; and
switching to read and write operations on the R′ memory cells using the second schedule set.
6. The method of claim 5 wherein D′ is greater than D; and
further wherein switching to read and write operations on the R′ memory cells using the second schedule set comprises transferring from the first schedule set to the second schedule set immediately.
7. The method of claim 5 wherein D′ is smaller than D; and
further wherein switching to read and write operations on the R′ memory cells using the second schedule set comprises transferring from the first schedule set to the second schedule set using a transition period;
further wherein no interleaver write operations are performed on cells during the transition period;
further wherein interleaver read operations on cells continue before the end of the transition period using an interleaver output byte delay that corresponds to a depth equal to D; and
further wherein interleaver read operations on cells continue after the end of the transition period using an interleaver output byte delay that corresponds to a depth equal to D′.
8. The method of claim 5 wherein determining the first schedule set for R memory cells comprises, for each of the R memory cells, constructing a first schedule set array having a plurality of rows, wherein each row of the array comprises a first element defining a period index P and a second element defining a byte index B, and
further wherein determining the second schedule set for R′ memory cells comprises, for each of the R′ memory cells, constructing a second schedule set array having a plurality of rows, wherein each row of the array comprises a first element defining a period index P and a second element defining a byte index B.
9. The method of claim 5 wherein performing read and write operations on the R memory cells using the first schedule set comprises selecting a first memory cell from the R memory cells based on the first schedule set; and
further wherein performing read and write operations on the R′ memory cells using the second schedule set comprises selecting a first memory cell from the R′ memory cells based on the second schedule set.
10. The method of claim 5 wherein
R
=
(
D
-
1
)
·
(
I
-
1
)
2
;
and further wherein
R
′
=
(
D
′
-
1
)
·
(
I
-
1
)
2
.
11. A system for performing convolutional interleaving of a data flow, with a depth D and a period I, the system comprising:
means for determining a schedule for each of a plurality of R memory cells based on an array having a plurality of rows, each row comprising a first element defining a period index P and a second element defining a bite index B, wherein the array is constructed by:
generating a first row of the array, comprising:
setting the first element of the first row of the array equal to a period index initialization value;
setting the second element of the first row of the array equal to a byte index initialization value;
generating a new row of the array, comprising:
setting P equal to the period index initialization value;
setting B equal to the byte index initialization value;
setting a position index L equal to one of B+(B*(D−1)) and B+((I−1−B)*(D−1));
resetting P, wherein
P
=
P
+
⌊
B
I
⌋
resetting B, wherein B=L mod I;
setting the first element of the next row of the array equal to P; and
setting the second element of the next row of the array equal to B; and
repeating generating the next row of the array until the second element of the next row of the array equals the second element of the first row of the array;
means for performing for each time sample the following operations:
selecting a first memory cell from the R memory cells based on the schedules of the R memory cells;
reading a first byte stored in the first memory cell;
writing the first byte to the interleaver output;
receiving a second byte at the input of the interleaver;
writing the second byte to the first memory cell.
12. The system of claim 11 wherein selecting a first memory cell from the R memory cells based on the schedules of the R memory cells comprises examining the schedules of the R memory cells to identify the memory cell whose schedule includes a current time sample.
13. The system of claim 11 wherein selecting a first memory cell from the R memory cells based on the schedules of the R memory cells comprises reading a schedule table, wherein the scheduling table has rows and columns corresponding to period and byte indices, and wherein the contents of the table consist of pointers to memory cells for period/byte index pairs corresponding to time samples.
14. The system of claim 11 wherein
R
=
(
D
-
1
)
·
(
I
-
1
)
2
.
15. The system of claim 11 , further comprising:
means for determining a first schedule set for a plurality of R memory cells, wherein:
D is a first depth;
I is an interleaving period; and
R is based on D and I;
means for performing the read and write operations on the R memory cells using the first schedule set;
means for determining a second schedule set for a plurality of R′ memory cells, wherein:
D′ is a second depth; and
R′ is based on D′ and I; and
means for switching to read and write operations on the R′ memory cells using the second schedule set.
16. The system of claim 15 wherein D′ is greater than D; and
further wherein switching to read and write operations on the R′ memory cells using the second schedule set comprises transferring from the first schedule set to the second schedule set immediately.
17. The system of claim 15 wherein D′ is smaller than D; and
further wherein switching to read and write operations on the R′ memory cells using the second schedule set comprises transferring from the first schedule set to the second schedule set using a transition period;
further wherein no interleaver write operations are performed on cells during the transition period;
further wherein interleaver read operations on cells continue before the end of the transition period using an interleaver output byte delay that corresponds to a depth equal to D; and
further wherein interleaver read operations on cells continue after the end of the transition period using an interleaver output byte delay that corresponds to a depth equal to D′.
18. The system of claim 15 , wherein determining the first schedule set for R memory cells comprises, for each of the R memory cells, constructing a first schedule set array having a plurality of rows, wherein each row of the array comprises a first element defining a period index P and a second element defining a byte index B, and
further wherein determining the second schedule set for R′ memory cells comprises, for each of the R′ memory cells, constructing a second schedule set array having a plurality of rows, wherein each row of the array comprises a first element defining a period index P and a second element defining a byte index B.
19. The system of claim 15 wherein performing read and write operations on the R memory cells using the first schedule set comprises selecting a first memory cell from the R memory cells based on the first schedule set; and
further wherein performing read and write operations on the R′ memory cells using the second schedule set comprises selecting a first memory cell from the R′ memory cells based on the second schedule set.
20. The system of claim 15 wherein
R
=
(
D
-
1
)
·
(
I
-
1
)
2
;
and further wherein
R
′
=
(
D
′
-
1
)
·
(
I
-
1
)
2
.