Tile based interleaving and de-interleaving for digital signal processing

Patent metadata

Field	Value
Publication number	US-11755474-B2
Application number	US-202117529954-A
Country	US
Kind code	B2
Filing date	Nov 18, 2021
Priority date	Aug 30, 2012
Publication date	Sep 12, 2023
Grant date	Sep 12, 2023

Abstract

Tile based interleaving and de-interleaving of row-column interleaved data is described. In one example, the de-interleaving is divided into two memory transfer stages, the first from an on-chip memory to a DRAM and the second from the DRAM to an on-chip memory. Each stage operates on part of a row-column interleaved block of data and re-orders the data items, such that the output of the second stage comprises de-interleaved data. In the first stage, data items are read from the on-chip memory according to a non-linear sequence of memory read addresses and written to the DRAM. In the second stage, data items are read from the DRAM according to bursts of linear address sequences which make efficient use of the DRAM interface and written back to on-chip memory according to a non-linear sequence of memory write addresses.

First claim

What is claimed is:

1. A transfer engine for use in a digital signal processing system, the transfer engine comprising:
a first memory port arranged to connect to a memory space, the memory space comprising a first storage region and a second storage region, the first storage region arranged to store a plurality of data items arranged in a first sequence; and
a second memory port arranged to connect to a dynamic random access memory (DRAM);
wherein, during a first transfer, the transfer engine is arranged to read the plurality of data items from the first storage region according to a generated non-linear or non-consecutive sequence of memory read addresses and to write the plurality of data items read from the first storage region to the DRAM, and
wherein, during a subsequent transfer, the transfer engine is arranged to read the plurality of data items from the DRAM according to linear or consecutive address sequences, and to write the plurality of data items to the second storage region according to a generated non-linear or non-consecutive sequence of memory write addresses, such that the plurality of data items are arranged in a second sequence in the second storage region that is different from the first sequence and wherein the second sequence is either interleaved or de-interleaved with respect to the first sequence.

2. The transfer engine according to claim 1 , wherein the memory space is static random access memory (SRAM).

3. The transfer engine according to claim 1 , further comprising the DRAM.

4. The transfer engine according to claim 1 , wherein the plurality of data items comprises a subset of a block of data items and the transfer engine is further arranged to perform a plurality of transfers until all the block of data items has been written to the second storage region.

5. The transfer engine according to claim 1 , further comprising at least one address generating element arranged to generate the non-linear or non-consecutive sequence of memory read addresses and the non-linear or non-consecutive sequence of memory write addresses.

6. The transfer engine according to claim 1 , wherein the plurality of data items comprises a subset of a block of data items and the block of data items is defined as being arranged as a grid comprising a number of rows of data items and a number of columns of data items.

7. The transfer engine according to claim 6 , wherein the grid further comprises a plurality of tiles, each tile comprising a rectangular portion of the grid and further comprising R rows and C columns of data items and wherein the plurality of data items comprises one or more tiles.

8. The transfer engine according to claim 7 , wherein the non-linear or non-consecutive sequence of memory read addresses comprises, for each tile in the first plurality of data items: a sequence of non-consecutive memory addresses separated by a fixed number of memory addresses and starting at an initial starting address, the fixed number corresponding to one less than the number of rows in the grid, until a boundary of the tile is reached, followed by one or more additional sequences of non-consecutive memory addresses, each additional sequence starting at an offset initial starting address.

9. The transfer engine according to claim 7 , wherein the generated non-linear or non-consecutive sequence of memory write addresses comprises: a sequence of groups of C consecutive memory addresses separated by a fixed number of memory addresses in the second memory and starting at an initial starting address in the second memory, the fixed number corresponding to C less than the number of columns in the grid.

10. The transfer engine according to claim 7 , wherein the plurality of data items comprises a tile of the grid.

11. The transfer engine according to claim 7 , wherein during the subsequent transfer, the linear or consecutive address sequences comprises a sequence of X consecutive memory addresses separated by a fixed number of memory addresses in the second storage region and starting at an initial starting address in the second storage region, where X is equal to the number of data items in a tile of the grid.

12. The transfer engine according to claim 7 , wherein during the first transfer, the transfer engine is arranged to write the plurality of data items to the DRAM according to linear or consecutive address sequences, each linear or consecutive address sequence having a length selected based on a DRAM interface burst size.

13. The transfer engine according to claim 12 , wherein during the first transfer, the linear or consecutive address sequences comprises a sequence of X consecutive memory addresses separated by a fixed number of memory addresses in the second storage region and starting at an initial starting address in the second storage region, where X is equal to the number of data items in a tile of the grid.

14. The transfer engine according to claim 7 , wherein a tile is sized based on a size of the DRAM interface burst.

15. A method of performing an interleaving or de-interleaving operation on data items in a digital signal processing system, the method comprising:
reading, from a first storage region of a memory space, a first plurality of data items stored in a first sequence according to a generated non-linear or non-consecutive sequence of memory read addresses;
writing the first plurality of data items to a dynamic random access memory (DRAM);
reading, from the DRAM, the first plurality of data items according to linear or consecutive address sequences; and
writing the first plurality of data items to a second storage region of the memory space according to a generated non-linear or non-consecutive sequence of memory write addresses, such that the first plurality of data items are stored in the second storage region and are arranged in a second sequence in the second storage region that is different from the first sequence and wherein the second sequence is either interleaved or de-interleaved with respect to the first sequence.

16. The method according to claim 15 , wherein the first plurality of data items comprises a subset of a block of data items, wherein the block of data items is defined as being arranged as a grid comprising a number of rows of data items and a number of columns of data items, the grid further comprising a plurality of tiles, each tile comprising a rectangular portion of the grid and further comprising R rows and C columns of data items and wherein the first plurality of data items comprises one or more tiles, and wherein reading, from a first storage region, a first plurality of data items stored in a first sequence according to a generated non-linear or non-consecutive sequence of memory read addresses comprises, for each tile in the first plurality of data items:
(i) reading a data item at an initial starting address in the first storage region;
(ii) skipping a fixed number of data items, the fixed number corresponding to one less than the number of rows in the grid;
(iii) reading a data item;
(iv) repeating steps (ii) and (iii) until a boundary of the tile is reached;
(v) adding an offset to the initial starting address; and
(vi) repeating steps (i)-(v) until each data item in the tile has been read.

17. The method according to claim 15 , wherein the first plurality of data items comprises a subset of a block of data items, wherein the block of data items is defined as being arranged as a grid comprising a number of rows of data items and a number of columns of data items, the grid further comprising a plurality of tiles, each tile comp

Assignees

• Imagination Tech Ltd

Inventors

• Murrin Paul
• Anderson Adrian J
• El-Hajjar Mohammed

Classifications

• H03M13/276

  Interleaving address generation · CPC title

• H03M13/2707 Primary

  Simple row-column interleaver, i.e. pure block interleaving · CPC title

• G06F12/0607 Primary

  Interleaved addressing · CPC title

• H03M13/6505

  Memory efficient implementations · CPC title