(SD2023-333) A System for Decoding Error-Correcting Codes

Abstract

This invention is a new system of algorithms for decoding linear block codes. Given the received message block, the decoding algorithm is designed to recover the truly transmitted symbols.

Engineers from UC San Diego have invented a decoding system that can be shown to achieve near-optimal decoding performance for general linear codes of dimension less than or equal to 128. In particular, for Reed–Muller codes, this new algorithm is the first to be shown with simulation evidence to achieve the optimal block error rate for communications over binary symmetric channels. This invention employs multiple Monte Carlo Markov chain subdecoders in parallel, which is a novel idea compared to the existing art.

Technology Description

Researchers from UC San Diego have invented a parallel block Gibbs Monte Carlo Markov chain (MCMC) decoding algorithm for decoding linear codes. They showed through numerical experiments that, for short Reed–Muller codes, the error probability of the proposed decoder is close to the optimal value achieved by the maximum likelihood (ML) decoding. The near optimality of the parallel MCMC decoder is, however, not code-specific. In fact, the engineers have also observed similar results for short blocklength low density parity check (LDPC) codes. Moreover, there are several variations of the proposed decoder that can achieve even faster convergence than the previous results. The inventors further note that the parallel MCMC algorithm has applications beyond the framework of channel decoding. The proposed idea suggests a way to build practically feasible solvers for other problems in statistical signal processing where posterior sampling offers an alternative to optimal inference. For instance, the UCSD engineers have developed a fast-converging parallel MCMC detector for signal detection in MIMO systems. The parallel detector can be shown to efficiently achieve approximately ML detection and improve the existing results.

Applications

Advantages

State Of Development

Intellectual Property Info

UC San Diego has filed for patent protection and welcomes interest from companies pursuing commercial applications.

Related Materials

• Jiun-Ting Huang and Young-Han Kim. A System for Decoding Error-Correcting Codes. submitted to IEEE International Symposium on Information Theory (ISIT)