An exact information spectrum-type formula for the maximum size of finite length block codes subject to a minimum pairwise distance constraint is presented. This formula can be applied to codes for a broad class of distance measures. As revealed by the formula, the largest code size is fully characterized by the information spectrum of the distance between two independent and identically distributed (i.i.d.) random codewords drawn from an optimal distribution. A new family of lower bounds to the maximal code size is thus established, and the well-known Gilbert-Varshamov (GV) lower bound is a special case of this family.
By duality, an explicit expression for the largest minimum distance of finite length block codes of a fixed code size is also obtained. Under an arbitrary uniformly bounded symmetric distance measure, the asymptotic largest code rate (in the block length n) attainable for a sequence of (n,M,nδ)-codes is given exactly by the maximum large deviation rate function of the normalized distance between two i.i.d. random codewords. The exact information spectrum-type formula also yields bounds on the second-order terms in the asymptotic expansion of the optimum finite length rate for block codes with a fixed normalized minimum distance.
Vincent Y. F. Tan was born in Singapore in 1981. He is an Assistant Professor in the Department of Electrical and Computer Engineering (ECE) and the Department of Mathematics at the National University of Singapore (NUS). He received the B.A. and M.Eng. degrees in Electrical and Information Sciences from Cambridge University in 2005. He received the Ph.D. degree in Electrical Engineering and Computer Science (EECS) from the Massachusetts Institute of Technology in 2011. He was a postdoctoral researcher in the Department of ECE at the University of Wisconsin-Madison in 2011 and following that, a scientist at the Institute for Infocomm Research (I2R), A*STAR, Singapore from 2012 to 2013. His research interests include information theory, machine learning and statistical signal processing.
Dr. Tan has received several awards including the MIT EECS Jin-Au Kong outstanding doctoral thesis prize in 2011; the A*STAR Philip Yeo prize for outstanding achievements in research in 2011; and the NUS Young Investigator Award in 2014. He was also placed in the NUS Faculty of Engineering Teaching commendation list in 2016. He has authored a research monograph titled “Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities” in the Foundations and Trends® in Communications and Information Theory Series (NOW Publishers). A Senior Member of the IEEE, he served as a member of the IEEE “Machine Learning for Signal Processing” Technical Committee within the IEEE Signal Processing Society. He is currently serving as an Associate Editor for the IEEE Transactions on Communications and the IEEE Transactions on Green Communications and Networking.