On a Construction of Easily Decodable Sub-de Bruijn Arrays

Abstract

We consider the two-dimensional generalizations of de Bruijn sequences; i.e., the integer-valued arrays whose all fragments of a fixed size (windows) are different. For these arrays, dubbed sub-de Bruijn, we consider the complexity of decoding; i.e., the determination of a position of a window with given content in an array. We propose a construction of arrays of arbitrary size with arbitrary windows where the number of different elements in the array is of an optimal order and the complexity of decoding a window is linear.