Séminaire ICI : Jossy Sayir
Titre du séminaire et orateur
Coding by SUDOKU: not as simple as it looks!
Jossy Sayir, University of Cambridge, UK.
Date et lieu
Mardi 25 juin 2013, 11h00.
ENSEA, Cergy-Pontoise, salle 384.
In 2007, when a friend invited me to teach a tutorial on "performance analysis for iterative processing" in Peyresq, I had the funny idea of illustrating iterative decoders for low-density parity-check (LDPC) codes by analogy with a SUDOKU puzzle solver. My friend liked this analogy, as did many of the students, and I began using the example in all my lectures on coding. When I taught my first course at the University of Cambridge in 2010, I also gave the students an optional homework of implementing an encoder for codes based on SUDOKU puzzles and corresponding iterative decoders. To my surprise, despite having a very strong and hard-working group of students that year, none of the students did the homework. The next year I decided to prepare a solution of the homework myself to show the students how easy it was. I soon realised that building a real coding system based on SUDOKU is a lot harder than it looks, and turns out to be a very fruitful project with many interesting problems to solve on the way.
In this talk, I will give an introductory description of why SUDOKU puzzles are related to error correcting codes and how one might use such puzzles in practice. I will show that the iterative decoder for SUDOKU puzzles needs to compute the permanent of a matrix at every node and at every iteration. The permanent is a matrix function introduced by Cauchy that is closely related to the determinant but whose computation is known to be extremely complex. I will discuss lower complexity approaches to the decoding problem. On the transmitter side, I will show how a decoder for erasure channels can be used in conjunction with arithmetic coding and a prefix reservation scheme to realise a SUDOKU encoder, which incidentally can also serve as a neat generator of SUDOKU puzzles with any desired difficulty level. Finally, although one conclusion of this talk is that the precise use of regular 9x9 SUDOKU puzzles as codes is likely to be of purely academic interest, I will argue that some of the techniques introduced may have a wider interest for communications and related applications.