High-throughput low-latency erasure error correction in an integrated circuit

Patent metadata

Field	Value
Publication number	US-9985654-B1
Application number	US-201615098709-A
Country	US
Kind code	B1
Filing date	Apr 14, 2016
Priority date	Apr 14, 2016
Publication date	May 29, 2018
Grant date	May 29, 2018

Abstract

An example method of erasure error correction in an IC includes receiving input data from a channel coupled to the IC, determining a bit pattern indicating survived blocks and erased blocks of a plurality of blocks in the input data and determining a number of integers, in a finite set of integers, greater than or less than an integer representing the bit pattern, the finite set of integers representing a finite set of possible values of the bit pattern based on an (m, k) erasure coding scheme. The method further includes generating an address for a memory, which stores a plurality of pre-computed decoding matrices based on the (m, k) erasure coding scheme, from the determined number of integers to obtain a pre-computed decoding matrix associated with the bit pattern. The method further includes recovering the erased blocks through matrix multiplication using the pre-computed decoding matrix and the survived blocks as parametric input.

First claim

What is claimed is:

1. A method of erasure error correction in an integrated circuit (IC), comprising:
receiving input data from a channel coupled to the IC;
determining a bit pattern indicating survived blocks and erased blocks of a plurality of blocks in the input data;
determining, at an address generator circuit, a number of integers, in a finite set of integers, greater than or less than an integer representing the bit pattern, the finite set of integers representing a finite set of possible values of the bit pattern based on an (m, k) erasure coding scheme;
generating, at the address generator circuit, an address signal for a memory, from the determined number of integers to obtain a pre-computed decoding matrix associated with the bit pattern;
receiving the address signal from the address generator circuit at a memory that stores a plurality pre-computed decoding matrices based on the (m, k) erasure coding scheme;
receiving the survived blocks, and a signal from the memory indicative of the pre-computed decoding matrix, at a matrix multiplication circuit and recovering the erased blocks through matrix multiplication using the pre-computed decoding matrix and the survived blocks as parametric input.

2. The method of claim 1 , wherein the bit pattern comprises an erasure pattern having one's representing the erased blocks and zero's representing the survived blocks.

3. The method of claim 2 , wherein the step of determining the number of integers comprises:
iteratively processing the bits of the erasure pattern.

4. The method of claim 2 , wherein the step of determining the number of integers comprises:
computing the number of integers with a closed-form expression that is a function of m, k, and a set of integers indicating indices of the erased blocks.

5. The method of claim 1 , wherein the step of recovering comprises:
providing the pre-computed decoding matrix and the survived data blocks as parametric input to a matrix multiplication circuit.

6. The method of claim 1 , wherein the number of integers comprises an offset and wherein the step of generating the address comprises adding the offset to a base address.

7. The method of claim 6 , further comprising:
selecting a base address from a plurality of base addresses respectively associated with a plurality of different (m, k) erasure coding schemes.

8. An erasure codec circuit, comprising:
an input configured to receive input data from a channel;
an address generation circuit configured to:
receive a signal indicative of the bit pattern;
determine a bit pattern indicating survived blocks and erased blocks of a plurality of blocks in the input data;
determine a number of integers, in a finite set of integers, greater than or less than an integer representing the bit pattern, the finite set of integers representing a finite set of possible values of the bit pattern based on an (m, k) erasure coding scheme; and
generate an address signal for a memory, which stores a plurality of pre-computed decoding matrices based on the (m, k) erasure coding scheme, from the determined number of integers to obtain a pre-computed decoding matrix associated with the bit pattern; and

a matrix multiplication circuit configured to receive the survived blocks, and a signal from the memory indicative of the pre-computed decoding matrix, and to recover the erased blocks through matrix multiplication using the pre-computed decoding matrix and the survived blocks as parametric input.

9. The erasure codec circuit of claim 8 , wherein the bit pattern comprises an erasure pattern having one's representing the erased blocks and zero's representing the survived blocks.

10. The erasure codec circuit of claim 9 , wherein the address generation circuit is configured to:
iteratively process the bits of the erasure pattern.

11. The erasure codec circuit of claim 9 , wherein the address generation circuit is configured to:
compute the number of integers with a closed-form expression that is a function of m, k, and a set of integers indicating indices of the erased blocks.

12. The erasure codec circuit of claim 8 , wherein the number of integers comprises an offset and wherein the address generation circuit is configured to add the offset to a base address.

13. The erasure codec circuit of claim 12 , wherein the address generation circuit is configured to select a base address from a plurality of base addresses respectively associated with a plurality of different (m, k) erasure coding schemes.

14. An integrated circuit (IC), comprising:
an input configured to receive input data from a channel;
a memory configured to store a plurality of pre-computed decoding matrices based on the (m, k) erasure coding scheme;
an address generation circuit configured to:
receive a signal indicative of the bit pattern;
determine a bit pattern indicating survived blocks and erased blocks of a plurality of blocks in the input data;
determine a number of integers, in a finite set of integers, greater than or less than an integer representing the bit pattern, the finite set of integers representing a finite set of possible values of the bit pattern based on the (m, k) erasure coding scheme; and
generate an address signal for the memory from the determined number of integers to obtain a pre-computed decoding matrix associated with the bit pattern; and

a matrix multiplication circuit configured to receive the survived blocks, and a signal from the memory indicative of the pre-computed decoding matrix, and to recover the erased blocks through matrix multiplication using the pre-computed decoding matrix and the survived blocks as parametric input.

15. The IC of claim 14 , wherein the bit pattern comprises an erasure pattern having one's representing the erased blocks and zero's representing the survived blocks.

16. The IC of claim 15 , wherein the address generation circuit is configured to:
iteratively process the bits of the erasure pattern.

17. The IC of claim 15 , wherein the address generation circuit is configured to:
compute the number of integers with a closed-form expression that is a function of m, k, and a set of integers indicating indices of the erased blocks.

18. The IC of claim 8 , wherein the number of integers comprises an offset and wherein the address generation circuit is configured to add the offset to a base address.

19. The IC of claim 18 , wherein the address generation circuit is configured to select a base address from a plurality of base addresses respectively associated with a plurality of different (m, k) erasure coding schemes.

20. The IC of claim 14 , wherein the address generation circuit and the matrix multiplication circuit are configured in a programmable fabric.

Assignees

• Xilinx Inc

Inventors

• Ruan Ming

Classifications

• H03M13/154 Primary

  Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial · CPC title

• H03M13/616

  Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations · CPC title

• H03M13/373

  with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes · CPC title

• H03M13/1515

  Reed-Solomon codes · CPC title