HP Labs Technical Reports
Click here for full text:
Finding the Position of a Subarray in a PseudoRandom Array
Lloyd, Sheelagh; Burns, John
HPL91159
Keyword(s):
Abstract: Pseudorandom 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 twodimensional analogue of pseudorandom sequences. These sequences are used in a number of positionfinding applications, and psuedorandom 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 lookup 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 wellknown one of discrete logarithms.
Back to Index
