Nested polarized constructions: properties and design

Tuesday, November 25, 2014 - 4:00pm to Wednesday, November 26, 2014 - 3:55pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Ilya Dumer


Univ. of California, Riverside

Building and Room number



Polar codes can achieve channel capacity with low decoding complexity and have become one of the most exciting recent developments in coding theory. Reed-Muller (RM) codes - known for 60 years - lately have garnered a lot of interest in the theory of computation, mostly due to their simple structure based on the multivariate Boolean polynomials. One particularly important problem is that of learning Boolean polynomials with partially corrupted values.

In this talk, we employ a generic tree-like structure that is common for polar and RM codes. First, this design leads to recursive recalculations of code symbols and gives low decoding complexity of order n log n in blocklength n. Secondly, pruning this tree-like structure can optimize code distance of recursive constructions, with RM codes as a result, or can yield capacity-achieving polar codes. We begin with RM codes and survey the latest results on their decoding performance versus decoding complexity. We then proceed with polar codes and wish to improve their performance on moderate lengths. To do so, we end our tree structure at the low-order RM codes instead of the single information bits used in polar design. In addition, we apply maximum-likelihood decoding for these end RM codes. We also construct a new family of long high-rate polar codes that substantially outperform BCH codes while keeping low decoding complexity.


Ilya Dumer received his Ph.D. degree from the Institute for Information Transmission Problems of the Russian Academy of Sciences, in 1981. He was with this Institute from 1983 to 1995, first as a Junior Researcher and then as a Senior Researcher. Since 1995, he has been a Professor of Electrical Engineering at the University of California, Riverside. During 1992-1993, he was a Royal Society Guest Research Fellow at Manchester University, Manchester, U.K., and during 1993-1994, an Alexander von Humboldt Fellow at the Institute for Experimental Mathematics in Essen, Germany.  Dr. Dumer works in the fields of coding theory, discrete geometry, and their applications. His specific areas of research address low-complexity decoding algorithms, design of non-binary, concatenated, and quantum codes, and spherical coverings in the Hamming and Euclidean spaces. He is a Fellow of IEEE.