TY - GEN
T1 - Ultra-small block-codes for binary discrete memoryless channels
AU - Chen, Po-Ning
AU - Lin, Hsuan Yin
AU - Moser, Stefan M.
PY - 2011/12/21
Y1 - 2011/12/21
N2 - Block-codes with a very small number of codewords are Investigated for the two special binary memoryless channels, the binary symmetric channel (BSC) and the Z-channel (ZC). The optimal (In the sense of minimum average error probability, using maximum likelihood decoding) code structure Is derived for the cases of two, three, and four codewords and an arbitrary blocklength. It Is shown that for two possible messages, on a BSC, the so-called flip codes of type t are optimal for any t, while on a ZC, the flip code of type 0 Is optimal. For codes with three or four messages It Is shown that the so-called weak flip codes of some given type are optimal where the type depends on the blocklength. For all cases an algorithm Is presented that constructs an optimal code for blocklength n recursively from an optimal code of length n 1. For the ZC a recursive optimal code design Is conjectured In the case of live possible messages. The derivation of these optimal codes relies heavily on a new approach of constructing and analyzing the code-matrix not row-wise (codewords), but column-wise. Moreover, these results also prove that the minimum Hamming distance might be the wrong design criterion for optimal codes even for very symmetric channels like the BSC.
AB - Block-codes with a very small number of codewords are Investigated for the two special binary memoryless channels, the binary symmetric channel (BSC) and the Z-channel (ZC). The optimal (In the sense of minimum average error probability, using maximum likelihood decoding) code structure Is derived for the cases of two, three, and four codewords and an arbitrary blocklength. It Is shown that for two possible messages, on a BSC, the so-called flip codes of type t are optimal for any t, while on a ZC, the flip code of type 0 Is optimal. For codes with three or four messages It Is shown that the so-called weak flip codes of some given type are optimal where the type depends on the blocklength. For all cases an algorithm Is presented that constructs an optimal code for blocklength n recursively from an optimal code of length n 1. For the ZC a recursive optimal code design Is conjectured In the case of live possible messages. The derivation of these optimal codes relies heavily on a new approach of constructing and analyzing the code-matrix not row-wise (codewords), but column-wise. Moreover, these results also prove that the minimum Hamming distance might be the wrong design criterion for optimal codes even for very symmetric channels like the BSC.
UR - http://www.scopus.com/inward/record.url?scp=83655164994&partnerID=8YFLogxK
U2 - 10.1109/ITW.2011.6089371
DO - 10.1109/ITW.2011.6089371
M3 - Conference contribution
AN - SCOPUS:83655164994
SN - 9781457704376
T3 - 2011 IEEE Information Theory Workshop, ITW 2011
SP - 175
EP - 179
BT - 2011 IEEE Information Theory Workshop, ITW 2011
T2 - 2011 IEEE Information Theory Workshop, ITW 2011
Y2 - 16 October 2011 through 20 October 2011
ER -