Abstract
In his world-famous paper of 1948, Shannon defined channel capacity as
the ultimate rate at which information can be transmitted over a
communication channel with an error probability that will vanish if we
allow the blocklength to get infinitely large. While this result is of
tremendous theoretical importance, the reality of practical systems
looks quite different: no communication system will tolerate an
infinite delay caused by an extremely large blocklength, nor can it
deal with the computational complexity of decoding such huge
codewords. On the other hand, it is not necessary to have an error
probability that is exactly zero either, a small, but finite value
will suffice.
Therefore, the question arises what can be done in a practical
scheme. In particular, what is the maximal rate at which information
can be transmitted over a communication channel for a given fixed
maximum blocklength (i.e., a fixed maximum delay) if we allow a
certain maximal probability of error? In this project, we have started
to study these questions.
Block-codes with very short blocklength over the most general binary
channel, the binary asymmetric channel (BAC), are investigated. It
is shown that for only two possible messages, flip-flop codes are
optimal, however, depending on the blocklength and the channel
parameters, not necessarily the linear flip- flop code. Further it is
shown that the optimal decoding rule is a threshold rule. Some
fundamental dependencies of the best code on the channel are given.
In the special case of a Z-channel, the optimal code is derived for
the cases of two, three, and four messages. In the situation of two
and four messages, the optimal code is shown to be linear.
Keywords
Channel capacity, binary asymmetric channel (BAC), error probability,
finite blocklengths, ML, optimal codes, Z-channel.
-||- _|_ _|_ / __|__ Stefan M. Moser 
[-] --__|__ /__\ /__ Senior Scientist, ETH Zurich, Switzerland
_|_ -- --|- _ / / Adjunct Professor, National Yang Ming Chiao Tung University, Taiwan
/ \ [] \| |_| / \/ Web: https://moser-isi.ethz.ch/
Last modified: Fri Jun 11 11:56:49 UTC+8 2010