Block Codes for Asynchronous Data Transmission Designed from Binary Trees
Vladimir B. Balakirsky · The Computer Journal · 2002
We describe a class of codes that can be effectively used when one of $q^n$ vectors of length $n$ has to be delivered to the receiver over a noiseless $q$-ary channel in asynchronous mode assuming that the latter one receives the transmitted vector with the delay $\\tau\\in\\{0,\\dotsc,n-1\\}$, unknown in advance, while all other received symbols are arbitrarily chosen. The codes are specified for any $n$ by a regular algorithm, which is based on properties of ordered, oriented, rooted, binary trees, and have length $N\\approx n + 2$ log$_q n$. We show that these codes can be used in such a way that encoding and decoding complexities are measured by linear functions of $n$.