HP Labs Technical Reports

Click here for full text: PDF

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

Lloyd, Sheelagh; Burns, John



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

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map] [Home] [Hewlett-Packard]