High-throughput software-defined convolutional interleavers and de-interleavers
High-throughput software-defined convolutional interleavers and de-interleavers are provided herein. In some examples, a method for generating convolutionally interleaved samples on a general purpose processor with cache is provided. Memory is represented as a three dimensional array, indexed by block number, row, and column. Input samples may be written to the cache according to an indexing scheme. Output samples may be generated every MN samples by reading out the samples from the cache in a transposed and vectorized order.
1. A method for processing a stream of time ordered samples of a signal, the method being performed by at least one computer processor core in operable communication with memory, the method comprising:
(a) writing a subset of the samples to memory blocks such that temporally adjacent samples are written to different memory blocks than one another, and at least some non-temporally adjacent samples are written to the same memory blocks as one another, wherein the memory includes M memory blocks each of dimension MN, where M is an integer equal to the number of rows in each of the memory blocks, and Nis an integer equal to the number of columns in each of the memory blocks;
(b) generating a vector by reading out the samples from at least one of the memory blocks, wherein operation (b) comprises transposing and vectorizing the at least one of the memory blocks; and
(c) repeating operations (a) and (b) for additional subsets of the samples and additional memory blocks to generate a sequence of vectors forming a stream of convolutionally interleaved samples of the signal.
2. The method of claim 1 , wherein a portion of operation (a) and a portion of operation (b) are performed by a first processor core, and another portion of operation (a) and another portion of operation (b) are performed by a second processor core.
3. The method of claim 2 , further comprising, by a third processor core:
(d) receiving the vector of the samples generated in operation (b) by the first processor core and the vector of the samples generated in operation (b) from the second processor core;
(e) concatenating the vectors of operation (d) to generate a portion of the stream of convolutionally interleaved samples of the signal;
(f) outputting to the first processor core a portion of one of the additional subsets of the samples and outputting to the second processor core another portion of one of the additional subsets of the samples; and
(g) repeating operations (d) through (f), synchronously with operations (a) and (b), for the additional subsets of the samples.
4. The method of claim 1 , wherein a size of the subset of the samples is selected to fit entirely within a cache of the at least one computer processor core.
5. The method of claim 1 , wherein operation (a) comprises:
in a first memory block, writing a first sample of the subset to a first location;
in a second memory block, writing a second sample of the subset to a first location that is shifted within the second memory block relative to the first location within the first memory block; and
in a third memory block, writing a third sample of the subset to a first location that is shifted within the third memory block relative to the first location within the first memory block and relative to the first location within the second memory block.
6. The method of claim 5 , wherein:
the first location within the first memory block is in a row within the first memory block and a column within the first memory block;
the first location within the second memory block is in a row within the second memory block immediately below the row within the second memory block that corresponds to the row of the first location within the first memory block, and in a column within the second memory block that corresponds to the column of the first location within the first memory block; and
the first location within the third memory block is in a row within the third memory block immediately below the row within the third memory block that corresponds to the row of the first location within the second memory block, and in a column within the third memory block that corresponds to the column of the first location within the second memory block.
7. The method of claim 5 , wherein operation (a) comprises:
in the first memory block, writing a first sample of the subset to a second location;
in the second memory block, writing a second sample of the subset to a second location that is shifted within the second memory block relative to the second location within the first memory block, where the first sample of the subset immediately temporally precedes the second sample of the subset in the subset; and
in the third memory block, writing a third sample of the subset to a second location that is shifted within the third memory block relative to the second location within the first memory block and relative to the second location within the second memory block, where the second sample of the subset immediately temporally precedes the third sample of the subset in the subset.
8. The method of claim 1 , wherein operation (b) is performed responsive to respective rows of the memory blocks being respectively filled with the samples of the subset being written to them.
9. The method of claim 8 , wherein operation (b) is performed responsive to:
a row of a first memory block being filled;
a row of a second memory block immediately below the row of the second memory block that corresponds to the row of the first memory block being filled; and
a row of a third memory block immediately below the row of the third memory that corresponds to the row of the second memory block being filled.
10. The method of claim 1 , wherein the at least one of the memory blocks comprises locations that have been initialized but to which a sample has not yet been written.
11. The method of claim 1 , wherein operation (c) comprises, for at least one of the additional subsets of the samples, writing samples of that subset to the same locations of the memory blocks to which samples were written during operation (a).
12. The method of claim 1 , wherein the at least one computer processor core comprises a central processing unit (CPU) or a graphical processing unit (GPU).
13. The method of claim 1 , wherein each of the samples comprises a multiple-bit sequence.
14. A non-transitory computer-readable medium storing instructions for execution by at least one computer processor core in operable communication with memory, the instructions being for causing the at least one computer processor core to perform operations on a stream of time ordered samples of a signal, the operations comprising:
(a) writing a subset of the samples to memory blocks such that temporally adjacent samples are written to different memory blocks than one another, and at least some non-temporally adjacent samples are written to the same memory blocks as one another wherein the memory includes M memory blocks each of dimension MN, where M is an integer equal to the number of rows in each of the memory blocks, and Nis an integer equal to the number of columns in each of the memory blocks;
(b) generating a vector by reading out the samples from at least one of the memory blocks, wherein operation (b) comprises transposing and vectorizing the at least one of the memory blocks; and
(c) repeating operations (a) and (b) for additional subsets of the samples and additional memory blocks to generate a sequence of vectors forming a stream of convolutionally interleaved samples of the signal.
15. The non-transitory computer-readable medium of claim 14 , wherein the instructions cause a portion of operation (a) and a portion of operation (b) to be performed by a first processor core, and another portion of operation (a) and another portion of operation (b) to be performed by a second processor core.
16. The non-transitory computer-readable medium of claim 14 , the instructions further comprising, and causing to be performed by a third processor core:
(d) receiving the vector of the samples generated in operation (b) by the first processor core and the vector of the samples generated in operation (b) from the second processor core;
(e) concatenating the vectors of operation (d) to generate a portion of the stream of convolutionally interleaved samples of the signal;
(f) outputting to the first processor core a portion of one of the additional subsets of the samples and outputting to the second processor core another portion of one of the additional subsets of the samples; and
(g) repeating operations (d) through (f), synchronously with operations (a) and (b), for the additional subsets of the samples.
17. The non-transitory computer-readable medium of claim 14 , wherein the instructions cause a size of the subset of the samples to be selected to fit entirely within a cache of the at least one computer processor core.
18. The non-transitory computer-readable medium of claim 14 , wherein operation (a) comprises:
in a first memory block, writing a first sample of the subset to a first location;
in a second memory block, writing a second sample of the subset to a first location that is shifted within the second memory block relative to the first location within the first memory block; and
in a third memory block, writing a third sample of the subset to a first location that is shifted within the third memory block relative to the first location within the first memory block and relative to the first location within the second memory block.
19. The non-transitory computer-readable medium of claim 18 , wherein:
the first location within the first memory block is in a row within the first memory block and a column within the first memory block;
the first location within the second memory block is in a row within the second memory block immediately below the row within the second memory block that corresponds to the row of the first location within the first memory block, and in a column within the second memory block that corresponds to the column of the first location within the first memory block; and
the first location within the third memory block is in a row within the third memory block immediately below the row within the third memory block that corresponds to the row of the first location within the second memory block, and in a column within the third memory block that corresponds to the column of the first location within the second memory block.
20. The non-transitory computer-readable medium of claim 18 , wherein operation (a) comprises:
in the first memory block, writing a first sample of the subset to a second location;
in the second memory block, writing a second sample of the subset to a second location that is shifted within the second memory block relative to the second location within the first memory block, where the first sample of the subset immediately temporally precedes the second sample of the subset in the subset; and
in the third memory block, writing a third sample of the subset to a second location that is shifted within the third memory block relative to the second location within the first memory block and relative to the second location within the second memory block, where the second sample of the subset immediately temporally precedes the third sample of the subset in the subset.
21. The non-transitory computer-readable medium of claim 14 , wherein the instructions cause operation (b) to be performed responsive to respective rows of the memory blocks being respectively filled with the samples of the subset being written to them.
22. The non-transitory computer-readable medium of claim 21 , wherein the instructions cause operation (b) to be performed responsive to:
a row of a first memory block being filled;
a row of a second memory block immediately below the row of the second memory block that corresponds to the row of the first memory block being filled; and
a row of a third memory block immediately below the row of the third memory that corresponds to the row of the second memory block being filled.
23. The non-transitory computer-readable medium of claim 14 , wherein one of the memory blocks comprises locations that have been initialized but to which a sample has not yet been written.
24. The non-transitory computer-readable medium of claim 14 , wherein operation (c) comprises, for at least one of the additional subsets of the samples, writing samples of that subset to the same locations of the memory blocks to which samples were written during operation (a).
25. The non-transitory computer-readable medium of claim 14 , wherein the at least one computer processor core comprises a central processing unit (CPU) or a graphical processing unit (GPU).
26. The non-transitory computer-readable medium of claim 14 , wherein each of the samples comprises a multiple-bit sequence.