De Bruijn sequences with efficient decoding algorithms (Q1841913)

Based on previous results in the binary case, this paper gives a construction for de Bruijn sequences of arbitrary span over alphabets of arbitrary size, together with an associated decoding procedure. A hybrid construction for such sequences is given and analysed more closely in the binary case. It is shown that the storage requirements of the decoding algorithm can be eliminated, at the expense of a small extra amount of computation. The paper is concluded by showing how de Bruijn sequences of arbitrary span over alphabets of arbitrary even size may be constructed that may be decoded quickly and without the use of storage tables.