Efficient method for the reconstruction of digital information
US7472334B1 · kind B1 · utility
Inventors
Key dates
| Filing date | Oct 15, 2004 |
| Grant date | Dec 30, 2008 |
| Priority date | — |
| Expiry date | Jan 6, 2027 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M13/151
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
Improved method of encoding and repairing data for reliable storage and transmission using erasure codes, which is efficient enough for implementation in software as well as hardware. A systematic linear coding matrix over GF(2q) is used which combines parity for fast correction of single erasures with the capability of correcting k erasures. Finite field operations involving the coding and repair matrices are redefined to consist of bitwise XOR operations on words of arbitrary length. The elements of the matrix are selected to reduce the number of XOR operations needed and buffers are aligned for optimal processor cache efficiency. Decode latency is reduced by pre-calculating repair matrices, storing them in a hashed table and looking them up using a bit mask identifying the erasures to be repaired.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.