The 2011 Canadian Workshop on Information Theory - Frank Kschischang

Frank R. Kschischang
University of Toronto

Title: Subspace Codes and Network Coding

Abstract: In classical coding theory, information transmission is modeled as vector transmission: the transmitter sends a vector, the receiver gathers a vector possibly perturbed by noise, and the coding problem is to design a codebook having a large minimum distance between vectors. In this talk we generalize to the case of network coding and, motivated by the property that linear network coding is vector-space preserving, we model information transmission as vector-space transmission: the transmitter sends a (basis for a) vector space, the receiver gathers a (basis for a) vector space possibly perturbed by noise, and the coding problem is to design a codebook having a large minimum distance between vector spaces. We will show that so-called "lifted" maximum rank distance (MRD) codes such as Gabidulin codes play essentially the same role as that played by maximum distance separable (MDS) codes such as Reed-Solomon codes, both for information transmission in the presence of adversarial errors and for security against a wiretapper. When errors are introduced randomly (rather than chosen by an adversary), we show that a simple matrix-based coding scheme can approach capacity. Finally, we describe how some of these ideas may be useful in the context of lattice-theoretic physical-layer network-coding schemes based on compute-and-forward relaying.

Biography: Frank R. Kschischang received the B.A.Sc. degree (with honours) from the University of British Columbia, Vancouver, BC, Canada, in 1985 and the M.A.Sc. and Ph.D. degrees from the University of Toronto, Toronto, ON, Canada, in 1988 and 1991, respectively, all in electrical engineering. He is a Professor of Electrical and Computer Engineering at the University of Toronto, where he has been a faculty member since 1991. During 1997-98, he was a visiting scientist at MIT, Cambridge, MA and in 2005 he was a visiting professor at the ETH, Zurich. His research interests are focused primarily on the area of channel coding techniques, applied to wireline, wireless and optical communication systems and networks. In 1999 he was a recipient of the Ontario Premier's Excellence Research Award and in 2001 (renewed in 2008) he was awarded the Tier I Canada Research Chair in Communication Algorithms at the University of Toronto. In 2010 he was awarded the Killam Research Fellowship by the Canada Council for the Arts, and the University of Toronto Faculty Award of Excellence. Jointly with Ralf Koetter he received the 2010 Communications Society and Information Theory Society Joint Paper Award. Dr. Kschischang has received a number of teaching awards at the University of Toronto, including the Applied Science and Engineering Faculty Teaching Award. He is a Fellow of IEEE and of the Engineering Institute of Canada. During 1997-2000, he served as an Associate Editor for Coding Theory for the IEEE TRANSACTIONS ON INFORMATION THEORY. He also served as technical program co-chair for the 2004 IEEE International Symposium on Information Theory (ISIT), Chicago, and as general co-chair for ISIT 2008, Toronto. He served as the 2010 President of the IEEE Information Theory Society.