Abstract
We introduce a new construction for the balancing
of non-binary sequences that make use of Gray codes for prefix
coding. Our construction provides full encoding and decoding
of sequences, including the prefix. This construction is based on
a generalization of Knuth’s parallel balancing approach, which
can handle very long information sequences. However, the overall
sequence—composed of the information sequence, together with
the prefix—must be balanced. This is reminiscent of Knuth’s
serial algorithm. The encoding of our construction does not make
use of lookup tables, while the decoding process is simple and
can be done in parallel.