Vitaly Skachek - Venia Legendi

Klipi teostus: Mirjam Paales 07.05.2012 3600 vaatamist Arvutiteadus

Vitaly Skachek - Venia Legendi

"Pseudocodeword Redundancy and Efficient Decoding of LDPC Codes"

Joint work with Jens Zumbraegel and Mark Flanagan.


Error-correcting codes are used for correction of data errors in communications and information storage devices. Linear error-correcting codes are defined as null-spaces of the corresponding parity-check matrices. Low-density parity-check (LDPC) code is a linear code with a sparse parity-check matrix.

Recently, LDPC codes with their respective message-passing decoding algorithms became a standard for correction of errors in a wide variety of systems. It was observed that adding additional (redundant) rows to a parity-check matrix can improve the performance of the LDPC code. In order to explain this phenomenon, the graph-cover pseudocodewords and their corresponding pseudoweights were introduced.

In this work, we define various types of pseudocodeword redundancy for a given code as the smallest number of rows in a parity-check matrix such that the minimum pseudoweight (over the corresponding channel) is equal to the minimum Hamming distance. For a binary linear code and erasure channel, the pseudocodeword redundancy
is known to be finite. In this work we show that most binary linear codes do not have a finite pseudocodeword redundancy over some other popular channels. We also provide bounds on the pseudocodeword redundancy for some families of codes, including codes
based on designs. Finally, we obtain the exact values of pseudocodeword redundancies for some short codes.



Vitaly Skachek received the B.A., M.Sc. and Ph.D. degrees from the Technion---Israel Institute of Technology. In the summer of 2004, he visited the Mathematics of Communications Department at Bell Laboratories. During 2007--2012, Dr. Skachek held visiting positions with the Claude Shannon Institute and the School of Mathematical
Sciences, University College Dublin, Ireland, with the School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, and with the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign. He is now with McGill University in Montreal, Canada.