Maximum-Length Sequence
Posted on Fri 16 March 2018 in Digital Signal Processing
簡介
Maximum-Length Sequence (MLS) 是一種二值序列，長度\(P=2^N-1\)，其中\(N\)代表整數。MLS 可以利用以下的關係式遞迴產生：
$$n(k+3)=n(k) \oplus n(k+2),$$
其中\(\oplus\)代表 XOR 運算。若將將產生出來的\(0,1\)邏輯值由下式轉換成\(1,-1\)，則為 MLS 訊號：
$$0 \rightarrow 1$$
$$1 \rightarrow -1.$$
性質
在 MLS 當中，\(0\)與\(1\)的數量大約相同，有\(2^{N-1}\)個\(1\)和\(2^{N-1}-1\)個\(0\)。另一個的性質是 MLS 訊號的自相關為 delta function。
範例
在 Scipy 的函示庫中的 signal 模組有實作 MLS，其範例如下：
import scipy as sp
import matplotlib.pyplot as plt
from scipy.signal import max_len_seq
N = 6 # nbits
seq = max_len_seq(N)[0]
print(seq)
[1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0
1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0]
將序列轉換成訊號，驗證自相關性質：
from numpy.fft import fft, ifft, fftshift, fftfreq
spec = fft(seq)
acorrcirc = ifft(spec * sp.conj(spec)).real
P = len(seq)
plt.figure()
plt.plot(sp.arange(-P/2+1, P/2+1), fftshift(acorrcirc), '.-')
plt.show()