Seminari MoMA

www.mat.uniroma1.it/ricerca/seminari/moma

Venerdi’ 11 aprile, ore 12-14, aula Consiglio

Guido Montorsi

Analog Digital Belief Propagation and its application to channel decoders

Sunto

As required by information theory, channel codes with long code words are necessary building blocks in a transmission system to achieve reliable communications with minimal power and maximal throughputs over noisy physical channels. Nowadays capacity-achieving large random binary codes are actually adopted in most telecommunication standards. The breakthrough that allowed their practical use has been to substitute the optimal maximum likelihood decoding techniques at the receiver with suboptimal iterative techniques based on “belief” propagation. Belief propagation is a powerful inference technique working on graphs used in many different applications. Graph nodes are associated to factors or constraints of the model while graph edges are associated to random variables. Belief propagation algorithm proceeds by iteratively updating messages associated to the random variables, according to the constraints imposed by nodes. In the framework of channel decoding the graph nodes represent the deterministic, usually linear, code constraints. They are either associated to a (binary) parity check sum, or to a repetition of the variable. Belief propagation is initialized with a set of messages obtained from the noisy channel observations of the transmitted bits and proceeds iteratively, updating the messages according to the code constraints until convergence is reached. Most practically used codes are linear and binary codes, so that messages propagated in the graph are binary messages usually represented with a single scalar (the Log-Likelihood Ratio). In order to increase the throughput of communication systems, the use of non binary codes is an attractive solution as each symbol can carry more information bits. Non binary codes can be constructed over groups, rings, or fields and there is a vast literature on the design of capacity achieving non binary codes. The extension of the application of belief propagation to the non binary codes however poses several complexity problems as both message representation and message updating at check node grows at least linearly with the cardinality of the non binary alphabet and consequently exponentially with the increase of required throughput. In this talk I will start by recalling the fundamental ideas and terminology beyond binary channel coding constructions and corresponding iterative decoding with belief propagation and other iterative techniques. I will then extend the concepts to non binary codes and summarize the main algorithms and complexity problems related with them. I will then introduce a new algorithm, named Analog Digital Belief Propagation (ADBP) which solves the complexity problems of belief propagation for non binary codes. I will discuss the main properties of the algorithm, its possible extensions and code design problems related to the adoption of this algorithm.