Abstract

Most people are familiar with SUDOKU puzzles published in our daily newspapers. There is a close connection between SUDOKU puzzles and error-correction codes used in telecommunication receivers. The algorithm that runs in our brains to solve SUDOKU puzzles is similar to the iterative decoding algorithms for Low-Density Parity-Check (LDPC) codes.

While this connection is obvious to coding theorists, we are not aware that anyone has constructed coding systems based on SUDOKU puzzles. We set about realising such a system as a simple and fun exercise. As this talk will illustrate, this turned out not to be as simple as first appeared, and soon became a complex engineering project bringing together many techniques from coding, information theory, and mathematics.

This talk will not assume any prior knowledge of error correction coding and will introduce every technique used in a tutorial manner. Although SUDOKU puzzles will also be introduced, members of the audience are encouraged to solve many puzzles in preparation for the talk as it will make it easier for them to follow the arguments.

Bio:Dr. Jossy Sayir received his engineering diploma (Dipl. El. Ing. ETH ) in 1991 and doctorate (Dr. Sc. Techn.) in 1999, both from the Swiss Federal Institute of Technology in Zurich, Switzerland (ETHZ). From 1991 until 1993, he worked as a development engineer for Motorola Communications in Tel Aviv, Israel, on the design and quality assurance of a digital mobile radio system. From 1993 until 1999, he worked as a research and teaching assistant under the supervision of Prof. James L. Massey while writing his dissertation “On Coding by Probability Transformation”. From 2000 until 2009, he was a senior researcher at the Telecommunications Research Center in Vienna, Austria (ftw.) and managed part of the centre’s strategic research activities from 2002 until 2008. Since June 2009, he has been with the Department of Engineering at the University of Cambridge on an Intra-European Marie Curie Fellowship that lasted until November 2011. In September 2011, he was appointed as a fixed-term lecturer in Communications at the Department of Engineering of the University of Cambridge for the academic year 2011/12. He also served on the executive board of the European FP7 Network of Excellence in Wireless Communications (NEWCOM++) and chaired theEC concertation cluster “Radio Access and Spectrum” (RAS) that includes 30 EC projects. His research interests include information theory, iterative decoding, sub-optimal and quantized decoders.