On the Hamming Weight Distribution of Subsequences of Pseudorandom Sequences

In this paper, we characterize the average Hamming weight distribution of subsequences of maximum-length sequences (m-sequences). In particular, we consider all possible m-sequences of dimension $k$ and find the average number of subsequences of length $n$ that have a Hamming weight $t$. To do so, we first characterize the Hamming weight distribution of the average dual code and use the MacWilliams identity to find the average Hamming weight distribution of subsequences of m-sequences. We further find a lower bound on the minimum Hamming weight of the subsequences and show that there always exists a primitive polynomial to generate an m-sequence to meet this bound. We show via simulations that when a proper primitive polynomial is chosen, subsequences of the m-sequence can form a good rateless code that can meet the normal-approximation benchmark.

I. Introduction

A maximum-length linear sequence (m-sequence) is a binary sequence which satisfies the linear recurrence that is characterized by a binary primitive polynomial of degree for , which is referred to as the connection polynomial. In particular, an m-sequence, , can be generated by , where all operations are over GF(2). This recurrence relation generates an infinite sequence which is uniquely determined by . Some of the properties of these sequences have been studied for short subsequences, whose length is less than . In particular, all bits in a short subsequence (of length less than k) are independent and the sum of these bits follows a (nearly) binomial distribution. For subsequences of lengths greater than , the bits are related by the recurrence relation. Therefore, the distribution of the sum of successive bits of subsequences usually deviates from the binomial distribution [1].