WARF: P120149US01

Linear Programming for Practical, Real-Time Error Correction and Decoding


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.
OVERVIEWTo 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.
THE INVENTIONUW–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.
  • Digital communications
  • Magnetic storage and optical transport networks
  • Improving data integrity and reliability
  • 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  
  • 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.
Contact Information
For current licensing status, please contact Jeanine Burmania at or 608-960-9846.
The WARF Advantage

Since its founding in 1925 as the patenting and licensing organization for the University of Wisconsin-Madison, WARF has been working with business and industry to transform university research into products that benefit society. WARF intellectual property managers and licensing staff members are leaders in the field of university-based technology transfer. They are familiar with the intricacies of patenting, have worked with researchers in relevant disciplines, understand industries and markets, and have negotiated innovative licensing strategies to meet the individual needs of business clients.