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 analysed. The study of non-linear codes with local constraints is motivated, and possible applications in wireless communications are discussed.
Jossy Sayir obtained his engineering diploma and PhD from ETH Zurich in 1991 and 1999, respectively. From 1991 until 1993, he worked for Motorola Communications Israel Ltd. as a development engineer. He then worked as a teaching and research assistant under Prof. J.L. Massey leading to his thesis “On Coding by Probability Transformaton”. From 2000, he was a senior researcher at the Telecommunications Research Centre (ftw.) in Vienna, Austria, where he managed a part of the centre’s strategic research activities from 2002. Since 2009, he has been at the Department of Engineering at the University of Cambridge, first as a Marie Curie Intra-European Research Fellow, then as a fixed-term and currently as an affiliate lecturer for communications. He teaches lectures in years 1, 3 and 4 of the engineering course, is a Teaching Fellow of Robinson College and Director of Studies for first year engineers. He has participated in several EC funded projects, headed the “Radio Access and Spectrum” cluster of projects, and served on the organisation committees of various international conferences, including recently as TPC co-chair of the IEEE International Symposium on Information Theory (ISIT) 2013.
