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 -