Localized Error Correction in Projective Space

Prof. Ning CAI
Xidian University, China
Monday, 20 August, 2012
11:00 am - 12:00 pm
Room 833, Ho Sin Hang Engineering Building The Chinese University of Hong Kong

The localized error correction code was introduced by L. A. Bassalygo, S. I. Gelfand, and M. S. Pinsker, 1989, when they studied writing on unreliable medium. They found the side information of possible error positions at encoder can increase the ability of error correction of codes and therefore introduced localized error correction. The proven Hamming bound in fact is the capacity of binary localized error correction codes. Regardless its application, the problem itself is a beautiful research object in combinatorial coding theory. Error correction code in projective space, was introduced by Koetter and Kschischang, in 2008, in the context of network error correction. From combinatorial view, it can be considered as an extension of coding theory in Hamming space from Boolean lattice to the subspace lattice. 

In this work we extend localized error correction code from Hamming space to the projective space. For constant dimensional localized error correction codes in projective space, we have a lower bound and an upper bound of the capacity, which are asymptotically tight when z < x ≤ (n - z)/2, where x, z, and n are dimensions of codewords, error configurations, and the ground space respectively. We determine the capacity of non-constant dimensional localized error correction codes when z < n/3. Our results show, that like in binary Hamming space, the side information increases the capacity, and unlike in the binary Hamming space, our lower bound beats Hamming Bound. 


Ning Cai received the B.S. degree in mathematics from the Normal College of Beijing, Beijing, China in 1982, the M.S. degree in mathematics from Academia Sinica, Beijing, China, in 1984, and the Dr. degree in mathematics from the University of Bielefeld, Bielefeld, Germany, in 1988, respectively. He was with the University of Bielefeld, Germany, the Chinese University of Hong Kong, and the National University of Singapore, during 1989-2005. Since 2006, he is a distinguished professor in the Xidian University, China. 

Dr. Cai is a recipient of the 2005 IEEE Information Theory Society Paper Award (for his paper ``Linear network coding'' co-authored with S.-Y. R. Li and R. W. Yeung). He served as an IEEE IT Society Awards Committee member in 2008 and 2009, and a guest editor of joint Special Issue of IEEE Trans. On Information Theory and IEEE/ACM ``on Networking on Networking Information Theory", 2006. He has served on the committees of a number of information theory symposiums and workshops.