Description:
Efficient Decoding Algorithms for Reed-Muller Codes, Recursive Projection-Aggregation and List-Decoding
Princeton Docket # 19-3543-1
Reed-Muller (RM) codes are among the oldest families of error-correcting codes. Compared to polar codes, RM codes have the advantage of having a simple and universal code construction, though RM codes do not yet possess the generic analytical framework of polar codes (i.e., polarization theory). While it has been shown that RM codes achieve capacity on the Binary Erasure Channel (BEC) at a constant rate, as well as extremal rates for BEC and Binary Symmetric Channels (BSC), obtaining such results for a broader class of communication channels and rates remain open. Furthermore, RM codes are still missing a guaranteed efficient decoder for RM codes that is competitive in the low rate/block-length regime.
To address this problem, Princeton researchers have developed a novel decoding algorithm for Reed-Muller codes that can be applied for data transmission in cellular network or wireless network, as well as in the narrowband IoT (Internet of Things) applications. This new decoding algorithm significantly decreases the decoding error probability over the currently used polar codes in industry. More precisely, it has a 0.75dB gain over polar codes in the regime where polar codes are applied in practice and in 5G standards.
As the second part of the invention, Princeton researchers have devised a generic list decoding procedure that can be applied to any decoding algorithm for any code family and improves the decoding error probability. When applying this list decoding procedure together with the novel decoding algorithm for Reed-Muller codes, the inventors achieved the smallest possible decoding error possibility. As another variation, the generic list decoding procedure can be used together with the code concatenation method to further reduce the decoding error probability, and this method can also be applied to any code family.
Applications
• Decoding RM codes over any binary-input memoryless channels (e.g., AWGN channels)
• Can be used in data transmission and compression (e.g., wireless / cellular transmission, Internet of Things (IoT), data storage)
• Can be implemented in hardware (e.g., as part of a receiver in a communications system) or software (e.g., as instructions stored on a computer-readable medium)
• Additional application potential in 5G/6G standards
Advantages
• Significantly reduced decoding error probability compared to previous RM decoding methods and polar codes with the same parameters
• Allows for natural parallel implementations, unlike some other decoders
• Can achieve near-optimal performance (close to maximum likelihood decoding) for certain practical parameter regimes
• Exploits the self-similarity structure of RM codes, ensuring that projected codes are also RM codes
Experimental Verification
Researchers have tested the invention experimentally, showing their novel algorithm has about 0.75dB advantage over polar codes, the technology planned for use in standards. The algorithm was implemented in C++, and the implementation is available for examination for interested parties.
Publication
Recursive Projection-Aggregation Decoding of Reed-Muller Codes | IEEE Journals & Magazine | IEEE Xplore
Inventors
Min Ye, Ph.D. is currently a Staff Researcher at IonQ, focusing on quantum error connection. Previously, he completed his postdoctoral studies at Princeton University in the Electrical and Computer Engineering Department. Dr. Ye received his Ph.D. in the Department of Electrical and Computer Engineering, University of Maryland, College Park and his B.S. in Electrical Engineering from Peking University, Beijing, China. He is the recipient of the 2017 IEEE Data Storage Best Paper Award. His research interests include coding theory, information theory, differential privacy, and machine learning.
Emmanuel Abbe, Ph.D., is a Professor in the Mathematics Institute and the School of Computer and Communication Sciences, where he holds the Chair of Mathematical Data Science, at the École Polytechnique Fédérale de Lausanne in Switzerland. Dr. Abbe was previously an Associate Professor in the Program for Applied and Computational Mathematics and the Department of Electrical and Computer Engineering, as well as an associate faculty in the Department of Mathematics at Princeton University. Dr. Abbe received his Ph.D. degree from the EECS Department at the Massachusetts Institute of Technology (MIT), and his M.S. degree from the Department of Mathematics at the Ecole Polytechnique Fédérale de Lausanne (EPFL).
He is the recipient/co-recipient of the Foundation Latsis International Prize; the Bell Labs Prize; the NSF CAREER Award; the Google Faculty Research Award; the Walter Curtis Johnson Prize from Princeton University; the von Neumann Fellowship from the Institute for Advanced Study; the IEEE Information Theory Society Paper Award; the Simons-NSF Mathematics of Deep Learning Collaborative Research Award; the ICML Outstanding Paper Award; the Frontiers of Science Award.
He is also a member of the Deepfoundations collaboration on the theoretical foundations of deep learning, the former director of the new Bernoulli Center for Fundamental Studies at EPFL, as well as a senior research scientist at Apple MLR.
Intellectual Property & Development status
U.S. patent has been issued (Patent Number: 11,736,124) and European patent protection is pending.
Princeton is currently seeking commercial partners for the further development and commercialization of this opportunity.
Contact
Renee Sanchez, JD
Princeton University Tech Licensing & New Ventures • Phone: (609) 258 6762 • Email: rs1453@princeton.edu
