Sudoku Codes, a Class of Non-Linear Iteratively Decodable Codes

Jossy Sayir

Department of Engineering, University of Cambridge, Cambridge, United Kingdom

Abstract:

A class of non-linear codes with local constraints inspired from SUDOKU puzzles is introduced. The constraint node operation in belief propagation decoding for this type of code is shown to be equivalent to the computation of a Cauchy permanent. A trellis-based decoder is presented whose complexity, while still of factorial order in the alphabet size, is much reduced for alphabet sizes of interest. Transmission over erasure channels is investigated and the constraint node operation is modified into a partial trellis search method with improved complexity with respect to other known methods. A universal encoder is discussed based on erasure decoders. Density evolution is developed and results analyzed. The study of non-linear codes with local constraints is motivated, and possible applications in wireless communications are discussed.

Biography:

Jossy Sayir received his doctorate (Dr. sc. techn.) from ETH Zurich in 1999. From 1991 to 1993, he worked as a development engineer for Motorola Communications in Tel Aviv, Israel. From 1993 to 1999, he worked as a research assistant under the supervision of Prof. James L. Massey while writing his dissertation "On Coding by Probability Transformation". From 2000 until 2009, he was with the Telecommunications Research Centre (ftw.) in Vienna, Austria, as a senior researcher and project manager in charge of part of the centre's strategic research activities. Since 2009, he has been with the Department of Engineering of the University of Cambridge, first as a Intra-European Marie Curie fellow and then as a fixed-term and affiliated lecturer. He is a Fellow of Robinson College and Director of Studies for first year engineering students. He has served on the organization committees of several international conferences, most recently as TPC co-chair of ISIT 2013 and will serve as general co-chair of ITW 2016. His research interests focus around low complexity iterative decoding algorithms.