# Cross-correlation of maximum length sequence with noise

Background

I am using a maximum length sequence to find the impulse response of a linear system. I want to calculate the expected SNR. I know that my signal amplitude is scaled by the length of the sequence after cross-correlation, but I am not sure what happens to noise.

Idea

Since the sign of noise is random, the sign of an element in a maximum length sequence doesn't matter: [1,1,-1] may as well be [1,1,1]. Cross-correlation with a maximum length sequence then is like using a moving average filter except the coefficients are all 1's instead of 1/n where n is length of the filter. A moving average filter reduces noise power by the length of filter, and scaling by the length of the filter increases noise power by the length of the filter squared. Therefore the noise power increases by the length of the filter.

Questions

What is the cross-correlation of a maximum length sequence and thermal noise?

What is the cross-correlation of a maximum length sequence with a discrete sine (e.g. EMI from a clock signal)?

I assume that this is a discrete-time problem where the maximum-length sequence is a pseudorandom sequence $$x[k]$$ of $$\pm 1$$ values and the noise is a sequence $$n[k]$$ of independent identically distributed (iid) zero-mean random variables with variance $$\sigma^2$$. Then, $$\sum_{k=0}^{N-1} x[k]n[k]$$ is also a sum of $$N$$ iid random variables and its variance is $$N\sigma^2$$, that is, the noise power increases in proportion to the length of the filter, exactly as you have conjectured. So, the crosscorrelation of the maximum length sequence and the noise is a zero-mean random variable with variance $$N\sigma^2$$ where $$N$$ is the length of the sequence being correlated against. If the noise is modeled as Gaussian, then crosscorrelation value is also a Gaussian random variable.

To answer your second question: To determine the cross correlation with discrete tones you can get the frequency response of your correlation by treating the sequence as the time reversed coefficients of an FIR filter (since the FIR filter performs convolution of your signal with the coefficients, and correlation is convolution with one of the sequences time reversed).

So you can see this using Matlab/Octave or Python Sciiy.signal using the freqz command. Here's how I did it using Python giving a meaningful magnitude answer in dB by scaling by the length of the sequence. By doing this, the result is the expected level in dB for a sinusoidal tone of peak amplitude 1 ($$cos{\omega t}$$) at any given normalized frequency $$0\le \omega < 1$$ relative to the peak correlation of an incoming sequence matched to the code with amplitude of +1/-1 (given that such a sequence would grow to $$2^i-1$$ in the correlator):

import numpy as np
import scipy.signal as sig
import matplotlib.pyplot as plt
mls_r, seed = sig.max_len_seq(5)    # sequence length 2**5-1
mls = list(mls_r*2-1)               # map to +/-1

f,m = sig.freqz(np.flip(mls),2**i-1)  # frequency response (DTFT)
plt.plot(f/(2*np.pi),20*np.log10(np.abs(m)))
plt.grid()
plt.xlabel("Normalized Frequency (cycles/sample)")
plt.ylabel("Magnitude (dB)")
plt.title("Frequency Response of one particular 31 chip MLS")


In general we are seeing the expected attenuation given by $$10Log10(N)$$ which is this case with $$N=31$$ would be $$14.9$$ dB.

Repeating with a 1023 length sequence results in the following plot, where we see the expected 30 dB attenuation, but also see that the results for any single tone can vary significantly including regions where the leakage can be as high as 5 dB stronger:

• So if I am only concerned with the magnitude of the frequency response, which is basically flat for the maximum length sequence, then single tones pass through unattenuated. Thanks! – DavidG25 Jan 20 '20 at 19:17
• Single tones are indeed attenuated—- they get spread by your sequence just as your data would. Further you will get varying results based on the coherence of your single tone with the sequence —- compare an integer number of cycles of your tone in one sequence with non-integer. The frequency response I suggested would show this. – Dan Boschen Jan 20 '20 at 20:18
• I plotted the frequency response of my sequence with greater resolution and it is not flat at all: some frequencies are attenuated while others are amplified. Thanks again. – DavidG25 Jan 20 '20 at 23:23
• Yes and some codes (Gold Codes for example) have higher values at certain frequencies that are vulnerabilities where there is more leakage. Can you share your result in a update to your post? – Dan Boschen Jan 20 '20 at 23:34
• Then simply use a FIR filter as your correlator, design the nulling filter you like best as another FIR filter, and convolve the coefficients. (Or keep as separate filters). Basically you want to filter out the interference and both are a linear process so you can do in either order. – Dan Boschen Jan 21 '20 at 4:04