On the Hamming Weight Distribution of Subsequences of Pseudorandom Sequences
Mahyar Shirvanimoghaddam · 2021
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.