Ultra-small block-codes for binary discrete memoryless channels

Po-Ning Chen*, Hsuan Yin Lin, Stefan M. Moser

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations


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.

Original languageEnglish
Title of host publication2011 IEEE Information Theory Workshop, ITW 2011
Number of pages5
StatePublished - 21 Dec 2011
Event2011 IEEE Information Theory Workshop, ITW 2011 - Paraty, Brazil
Duration: 16 Oct 201120 Oct 2011

Publication series

Name2011 IEEE Information Theory Workshop, ITW 2011


Conference2011 IEEE Information Theory Workshop, ITW 2011


Dive into the research topics of 'Ultra-small block-codes for binary discrete memoryless channels'. Together they form a unique fingerprint.

Cite this