The Peeling Decoder: Theory and Applications Parts I & II

Abstract: The peeling decoder is a simple greedy decoder that can be used to decode classes of codes defined on graphs, such as low density parity check (LDPC) codes and low density generator matrix codes, on the erasure channel. This deceptively simple decoder suffices to design capacity achieving coding schemes for the erasure channel. In addition, the peeling decoder can also be used to design optimal universal rateless codes as shown by Luby in the design of LT codes. In part I of this two-part tutorial, we will explain the main theoretical ideas behind the analysis of the peeling decoder and the design of optimal fixed rate and rateless codes for the erasure channel. We will also discuss how the peeling decoder can be used to decode generalized LDPC codes and product codes when used with non-erasure channels. We will conclude part I with a discussion of the relationship between channel coding and syndrome source coding for the compression of sparse sources. Krishna Narayanan received the B.E. degree from Coimbatore Institute of Technology in 1992, M.S. degree from Iowa State University in 1994 and the Ph.D. degree in Electrical Engineering from Georgia Institute of Technology in 1998. Since 1998, he has been with the Department of Electrical and Computer Engineering at Texas A&M University, where he is currently a professor.