PolarList - Improved Error-Correction Coding Software Using Polar Codes (C++)

Background

Error correcting codes are used in a multitude of applications, including wireless communications (e.g. cell phones), computer hard disks, deep-space and satellite communications. Discovered in 2009, polar codes are a major breakthrough in coding theory, the only family of codes known to have an explicit construction and efficient encoding and decoding algorithms, while also being “capacity achieving” over binary input symmetric memoryless channels.

A limitation of polar codes to date is that their performance at short to moderate block lengths is disappointing. There are two possible culprits: the codes themselves are inherently weak at these lengths, or the successive cancellation decoder employed to decode them is significantly degraded with respect to maximum likelihood decoding performance. These two possibilities are complementary, and so both may occur.

Technology Description

Engineers from UC San Diego have developed “PolarList”, a new implementation of polar codes with greatly improved error-correcting performance. The software (C++ implementation) incorporates a new decoding method for polar codes as well as a modification of the codes themselves. The resulting performance is better than the current state-of-the-art in error-correction coding.

This software greatly improves the error-correcting performance of polar codes, with only a moderate increase in complexity. This is achieved by virtue of a new decoding method for polar codes as well as a modification of the codes themselves. The resulting performance is often better than the current state-of-the-art in error-correction coding.

Related Materials

• Leroux C, AJ Raymond, G Sarkis, I Tal, A Vardy, WJ Gross. 2012 Hardware Implementation of Successive-Cancellation Decoders for Polar Codes Journal of Signal Processing Systems,69, 305-315. http://www.springerlink.com/content/04236015n4017877/ http://www.springerlink.com/content/1939-8018/
• Tal, I and A Vardy. 2011 List Decoding of Polar Codes 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), July 31 2011-Aug. 5 2011

Patent Status