Block codes for asynchronous data transmission designed from binary trees

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$.