Information Technology
Linear Programming for Practical, Real-Time Error Correction and Decoding
WARF: P120149US01
Inventors: Stark Draper, Benjamin Recht, Siddharth Barman
The Wisconsin Alumni Research Foundation (WARF) is seeking commercial partners interested in developing a method for efficient and highly reliable communication of digital data based on a novel approach to error-correction decoding. This approach casts the decoding problem as a linear program, which is decomposed into independent parallelizable sub-problems amenable to implementation.
Overview
To reliably transmit and store data, error detection/correction techniques are employed to guard against data corruption. Generally, such protection can be achieved by inserting redundant bits in the transmitted or stored data. For example, an eight-bit message might have a ninth ‘parity bit.’ This parity bit is set or reset to make the total number of bits an even number. Any corruption during data transmission or storage will be readily detected by checking if the total number of bits is still even. If not, an error can be assumed.
More sophisticated error detection/correction systems may use low density parity check (LDPC) codes in which small, overlapping subsets of bits have to meet such constraints. But decoding information prepared in this way is computationally demanding. One decoding method, called belief propagation, is often successful but cannot be guaranteed to converge to a set of bits meeting the constraint. Also, the method is limited in its ability to detect and correct errors.
More sophisticated error detection/correction systems may use low density parity check (LDPC) codes in which small, overlapping subsets of bits have to meet such constraints. But decoding information prepared in this way is computationally demanding. One decoding method, called belief propagation, is often successful but cannot be guaranteed to converge to a set of bits meeting the constraint. Also, the method is limited in its ability to detect and correct errors.
The Invention
UW–Madison researchers have developed a decoder for LDPC codes, and other similar coding systems, that can be proven to converge and may be parallelized for high-speed processing.
The method provides an error correction circuit including a buffer memory for holding a received string of bits derived from a transmitted (or stored) string. A parity rule memory holds a set of parity rules for the transmitted string, with each rule describing a predefined intended relationship between a subset of the bits as originally transmitted. The buffer and parity rule memories communicate with an optimizer, which generates a corrected string of bits using a linear programming (LP) process.
The method provides an error correction circuit including a buffer memory for holding a received string of bits derived from a transmitted (or stored) string. A parity rule memory holds a set of parity rules for the transmitted string, with each rule describing a predefined intended relationship between a subset of the bits as originally transmitted. The buffer and parity rule memories communicate with an optimizer, which generates a corrected string of bits using a linear programming (LP) process.
Applications
- Digital communications
- Magnetic storage and optical transport networks
- Improving data integrity and reliability
Key Benefits
- Robust, extremely reliable error correction/detection
- Proven convergence
- Not subject to an error floor, unlike belief propagation method
- May provide for simpler hardware implementation
- Improved speed and scalability with long data words
- Novel way to provide parallelism in LP error solution
Publications
For current licensing status, please contact Jeanine Burmania at [javascript protected email address] or 608-960-9846
- Barman S., Liu X., Draper S.C. and Recht B. 2011. Decomposition Methods for Large Scale LP Decoding. Communication, Control, and Computing (Allerton). 253-260.