HP Labs Technical Reports

Finding the Position of a Subarray in a Pseudo-Random Array

Lloyd, Sheelagh; Burns, John

HPL-91-159

Keyword(s):

Abstract: Pseudo-random arrays have the property that each possible subarray of a certain size except the all zero one occurs exactly once in the array. They are the two-dimensional analogue of pseudo-random sequences. These sequences are used in a number of position-finding applications, and psuedo-random arrays could also be useful in such applications. The problem is, given a subsequence (or subarray), to determine its position in the sequence (or array). Until recently, the only solution to this problem was the clever use of look-up tables and generation of subsequent subsequences. In this paper, we present a novel approach to this problem, and show how to reduce it to the well-known one of discrete logarithms.

Back to Index