Subsequences of Pseudorandom Sequences

Abstract

The properties of subsequences of long <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> sequences are studied using the moments of the subsequence weight distributions. These moments are shown to be an aid for selecting good <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> sequences for correlation-detection problems. In particular, the first four moments are described in detail for subsequence lengths <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M \leq 100</tex> digits for six different <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> sequences. Two simple algorithms are described for determining the third and fourth moments. An algorithm for calculating the fourth moment and a detailed description of this moment for the six <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> sequences are presented in this paper. Using the moments, a relationship is shown between the subsequences of the pseudorandom binary sequence and subsequences composed of random binary digits. Estimates for the moments of the subsequence weight distribution are obtained by sampling the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> sequence. A statistical analysis of these results is presented.