# US 8,572,456 B1 · Avoiding interleaver memory conflicts

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,572,456 B1
- Document ID: US8572456B1
- Status: Granted
- Kind: B1
- Application number: 12/470,959
- Filed: 2009-05-22
- Granted: 2013-10-29
- Earliest claimed: 2009-05-22
- Assignees: Altera Corporation
- Applicants: Zhengjun Pan; Volker Mauer
- Inventors: Zhengjun Pan; Volker Mauer
- Web page: https://patentgrep.com/patent/US8572456B1

## CPC

- H03M 13/2775: {Contention or collision free turbo code internal interleaver}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

Interleaving and deinterleaving schemes for operating in parallel on sections of a data block to load memories with respective segments of a reordered version of the block, in a manner which can avoid memory conflicts.

## Claims

### Claim 1

An interleaving system comprising:
a plurality of interleavers, each interleaver arranged to address data items from a respective section of a block of data items with destinations in segments of an interleaved version of the block;
a plurality of sets of first-in, first out buffers (FIFOs), a respective set of FIFOs for each interleaver such that each set of FIFOs is associated with a respective interleaver, each set of FIFOs containing a plurality of FIFOs, each FIFO in the respective set of FIFOs is associated with a respective one of the segments to which the respective interleaver can address data items, and the respective interleaver is associated with each FIFO in the respective set of FIFOs;
a plurality of memories, each memory for a respective one of the segments; and
a router arranged to direct into each FIFO data items addressed to a memory associated with the FIFO by the respective interleaver associated with the FIFO and arranged to direct into each memory only data items from FIFOs associated with the memory.

### Claim 2 (depends on 1)

The interleaving system of claim 1, wherein:
each interleaver is arranged to deduce for a data item a first address component indicating a segment to which the data item should be consigned.

### Claim 3 (depends on 1)

The interleaving system of claim 1, wherein:
each interleaver is arranged to deduce for a data item a second address component indicating a position that the data item should adopt in a segment to which the data item is to be assigned.

### Claim 4 (depends on 1)

The interleaving system of claim 1, wherein:
the router comprises a plurality of demultiplexers, a respective demultiplexer for each interleaver, each demultiplexer being arranged to route data items from its respective interleaver to the set of FIFOs associated with that interleaver.

### Claim 5 (depends on 2)

The interleaving system of claim 2, wherein:
the router comprises a plurality of demultiplexers, a respective demultiplexer for each interleaver, each demultiplexer being arranged to route data items from its respective interleaver to the set of FIFOs associated with that interleaver; and
each demultiplexer is arranged to route a data item from its respective interleaver to a FIFO on the basis of the first address component of the data item, wherein the FIFO is in the set of FIFOs associated with the respective interleaver.

### Claim 6 (depends on 3)

The interleaving system of claim 3, wherein:
each interleaver joins each data item to its second address component for loading into one of the FIFOs as a packet.

### Claim 7 (depends on 1)

The interleaving system of claim 1, wherein:
the router comprises a plurality of multiplexers, a respective multiplexer for each memory, each multiplexer being arranged to multiplex into its respective memory data items loaded into those FIFOs that are associated with that memory.

### Claim 8 (depends on 1)

A turbo decoder comprising the interleaving system of claim 1.

### Claim 9 (depends on 8)

A radio communications network base station including the turbo decoder of claim 8.

### Claim 10 (depends on 1)

A FPGA hosting an implementation of the interleaving system of claim 1.

### Claim 11

An interleaving system comprising:
a plurality of interleavers, each interleaver arranged to address data items from a respective section of a block of data items with destinations in segments of an interleaved version of the block;
a plurality of sets of first-in, first out buffers (FIFOs), a respective set of FIFOs for each interleaver such that each set of FIFOs is associated with a respective interleaver, each set of FIFOs containing a plurality of FIFOs, each FIFO in the respective set of FIFOs is associated with a respective one of the segments to which the respective interleaver can address data items, and the respective interleaver is associated with each FIFO in the respective set of FIFOs; and
a router for directing contents of the queues into their respective segments,
wherein:
the router directs data items from the queues into a given segment serially.

### Claim 12

A deinterleaving system comprising:
a plurality of deinterleavers, each deinterleaver arranged to address data items from a respective section of an interleaved version of a block of data items with destinations in segments of a deinterleaved version of the block;
a plurality of sets of first-in, first-out buffers (FIFOs), a respective set of FIFOs for each deinterleaver such that each set of FIFOs is associated with a respective deinterleaver, each set of FIFOs containing a plurality of FIFOs, each FIFO in the respective set of FIFOs is associated with a respective one of the segments to which the respective deinterleaver can address data items, and the respective deinterleaver is associated with each FIFO in the respective set of FIFOs;
a plurality of memories, each memory for a respective one of the segments; and
a router arranged to direct into each FIFO data items addressed to a memory associated with the FIFO by the respective deinterleaver associated with the FIFO and arranged to direct into each memory only data items from FIFOs associated with the memory.

### Claim 13 (depends on 12)

The deinterleaving system of claim 12, wherein:
each deinterleaver is arranged to deduce for a data item a first address component indicating a segment to which the data item should be consigned.

### Claim 14 (depends on 12)

The deinterleaving system of claim 12, wherein:
each deinterleaver is arranged to deduce for a data item a second address component indicating a position that the data item should adopt in a segment to which the data item is to be assigned.

### Claim 15 (depends on 12)

The deinterleaving system of claim 12, wherein:
the router comprises a plurality of demultiplexers, a respective demultiplexer for each deinterleaver, each demultiplexer being arranged to route data items from its respective deinterleaver to the set of FIFOs associated with that deinterleaver.

### Claim 16 (depends on 13)

The deinterleaving system of claim 13, wherein:
the router comprises a plurality of demultiplexers, a respective demultiplexer for each deinterleaver, each demultiplexer being arranged to route data items from its respective deinterleaver to the set of FIFOs associated with that deinterleaver; and
each demultiplexer is arranged to route a data item from its respective deinterleaver to a FIFO on the basis of the first address component of the data item, wherein the FIFO is in the set of FIFOs associated with the respective deinterleaver.

### Claim 17 (depends on 14)

The deinterleaving system of claim 14, wherein:
each deinterleaver joins each data item to its second address component for loading into one of the FIFOs as a packet.

### Claim 18 (depends on 12)

The deinterleaving system of claim 12, wherein:
the router comprises a plurality of multiplexers, a respective multiplexer for each memory, each multiplexer being arranged to multiplex into its respective memory data items loaded into those FIFOs that are associated with that memory.

### Claim 19

A deinterleaving system comprising:
a plurality of deinterleavers, each deinterleaver arranged to address data items from a respective section of an interleaved version of a block of data items with destinations in segments of a deinterleaved version of the block;
a plurality of sets of first-in, first-out buffers (FIFOs), a respective set of FIFOs for each deinterleaver such that each set of FIFOs is associated with a respective deinterleaver, each set of FIFOs containing a plurality of FIFOs, each FIFO in the respective set of FIFOs is associated with a respective one of the segments to which the respective deinterleaver can address data items, and the respective deinterleaver is associated with each FIFO in the respective set of FIFOs; and
a router for directing contents of the queues into their respective segments,
wherein:
the router directs data items from the queues into a given segment serially.