High-throughput software-defined convolutional interleavers and de-interleavers

Patent metadata

Field	Value
Publication number	US-11722154-B2
Application number	US-202117193354-A
Country	US
Kind code	B2
Filing date	Mar 5, 2021
Priority date	Mar 5, 2021
Publication date	Aug 8, 2023
Grant date	Aug 8, 2023

Abstract

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.

First claim

What is claimed:

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 pro

Assignees

• Aerospace Corp

Inventors

• Grayver Eugene
• Kubiak Mark

Classifications

• H03M13/2732 Primary

  Convolutional interleaver; Interleavers using shift-registers or delay lines like, e.g. Ramsey type interleaver · CPC title

• G06F12/0813

  with a network or matrix configuration · CPC title

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F2212/603

  of operating mode, e.g. cache mode or local memory mode · CPC title

• H03M13/2782

  Interleaver implementations, which reduce the amount of required interleaving memory · CPC title