  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.
