Colloquia
Ian Blake Abstract
CAM/EE COLLOQUIUM
“Coding for the Binary Erasure Channel”
Ian Blake
Department of Computer and Electrical Engineering
University of Toronto
Friday September 8, 2006
3:30PM in 356 Fitzpatrick Hall
*TEA – 3:00PM in 356 Fitzpatrick*
Abstract:
Recent interest in the iterative decoding of block codes has arisen largely out of three landmark contributions: the work of Gallager on low density parity check (LDPC) codes; the work of Tanner on the graphical interpretation of such codes and the work of Glavieux et al on the iterative decoding of turbo codes. These important contributions, among others, have shown how to get performance arbitrarily close to the Shannon bound for many discrete channels. The impact of this work on coding for the binary erasure channel (BEC) has been of particular interest resulting in coding schemes that achieve performance close to capacity with linear decoding complexity. The results in this area are reviewed from the perspective of rank properties of binary random matrices. Such a perspective reveals the relationship between the overhead of the scheme and the decoding algorithm. It also examines the trade-offs that are possible between overhead, decoding complexity and probability of successful decoding. Some combinatorial problems introduced by these problems are also noted.
