Abstract:
Solid codes provide outstanding fault-tolerance when used for
information transmission through a noisy channel involving not
only symbol substitutions, but also synchronisation errors and
black-outs. In this paper we provide an automaton theoretic characterisation of solid codes which takes this fault-tolerance into account.
The fault-tolerance afforded by a solid code L can be summarised
as follows: Consider messages, encoded using L, being sent through
a noisy channel. Any code words in L, which are present in the received message, will be decoded correctly, unless they themselves
happen to be the results of errors. Thus, errors in the received
message will not lead to incorrect decodings of those parts which
are error-free.
In this paper we consider acceptors which are fault-tolerant in
this sense when analysing such received messages. These acceptors characterise the class of solid codes. For finite solid codes an
automaton characterisation was published in the sixties by Levenshtein and Romanov. The characterisation uses state-invariant
finite-state transducers which act as decoders in such a way that
an output is generated exactly when a code word has been read
completely. State-invariance means that acceptance does not depend on the initial state - every state can be used as the initial
state.
The results of Levenshtein and Romanov depend strongly on
the fact that the code is finite. In this paper we provide a general automaton theoretic characterisation of arbitrary solid codes
without any such restriction. Moreover, the solid code is regular
as a language if and only if the automaton used in the characterisation can be reduced to an equivalent finite automaton with
equivalent properties.
The main results of this paper are as follows: Every acceptor
defines a solid code. For every solid code there is a fault-tolerant
acceptor defining the code. Such acceptors expose the decomposition of potentially faulty received messages according to the code.
For solid codes which are regular as languages these acceptors can
be chosen to be finite while preserving all important combinatorial
properties.