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 (

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.

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