共计 4385 个字符，预计需要花费 11 分钟才能阅读完成。
本专栏蕴含信息论与编码的外围常识，按知识点组织，可作为教学或学习的参考。markdown 版本已归档至【Github 仓库：https://github.com/timerring/information-theory】或者公众号【AIShareLab】回复 信息论 获取。
m 序列 (最长线性反馈移位寄存器序列)
线性反馈移位寄存器的特色多项式
线性反馈移位寄存器的递推关系式
递推关系式又称为反馈逻辑函数或递推方程。设图 2 所示的线性反馈移位 寄存器的初始状态为 $(a_{0} a_{1} \ldots a_{n-2} a_{n-1})$ , 经一次移位线性反馈, 移位寄存器 左端第一级的输出为
$$
a_{n}=c_{1} a_{n-1}+c_{2} a_{n-2}+\cdots+c_{n-1} a_{1}+c_{n} a_{0}=\sum_{i=1}^{n} c_{i} a_{n-i}
$$
若经 $\boldsymbol{k}$ 次移位, 则第一级的输出为
$$
a_{l}=\sum_{i=1}^{n} c_{i} a_{l-i}
$$
其中, $l=n+k-1 \geq n, k=1,2,3, \ldots$
由此可见, 移位寄存器第一级的输出, 由反馈逻辑及移位寄存器的原状态所决定。上式称为递推关系式。
线性反馈移位寄存器的特色多项式
用多项式 f(x) 来形容线性反馈移位寄存器的反馈连贯状态:
$$
f(x)=c_{0}+c_{1} x+\cdots+c_{n} x^{n}=\sum_{i=0}^{n} c_{i} x^{i}
$$
称为特色多项式或特征方程。其中, $x^{i}$ 存在, 表明 $c_{i}=\mathbf{1}$ , 否则 $c_{i}=\mathbf{0}$ , x 自身的取值并无实际意义。$c_{i}$ 的取值决定了移位寄存器的反馈连贯。因为 $c_{0}=c_{n}=1$ , 因而, f(x) 是一个常数项为 1 的 n 次多项式, n 为移位寄存器级数。
一个 n 级线性反馈移位寄存器能产生 m 序列的充要条件是它的特色 多项式为一个 n 次本原多项式。若一个 n 次多项式 f(x) 满足下列条件:
(1) f(x) 为既约多项式(即不能分解因式的多项式);
(2) f(x) 可整除 $(x^{p}+1), p^{n}-1$ ;
(3) f(x) 除不尽 $(x^{q+1}), q \lt p$。
则称 f(x) 为本原多项式。以上为咱们形成 m 序列提供了实践依据。
m 序列产生器
用线性反馈移位寄存器形成 m 序列产生器, 要害是由特色多项式 f(x) 来确定反馈 线的状态, 而且特色多项式 f(x) 必须是本原多项式。
现以 n=4 为例来阐明 m 序列产生器的形成。用 4 级线性反馈移位寄存器产生的 m 序列, 其周期为 $p=2^{4}-1=15$ , 其特色多项式 f(x) 是 4 次本原多项式，能整除 $(x^{15}+1)$。先将 $(x^{15}+1)$ 合成因式, 使各因式为既约多项式, 再寻找 f(x)。
$$
\begin{aligned}
x^{15}+1 & =(x+1)(x^{2}+x+1)(x^{4}+x+1) \\
& \cdot(x^{4}+x^{3}+1)(x^{4}+x^{3}+x^{2}+x+1)
\end{aligned}
$$
其中, 4 次既约多项式有 3 个, 但 $(x^{4}+x^{3}+x^{2}+x+1)$ 能整除 $(x^{5}+1)$ , 故它不是本原多 项式。因而找到两个 4 次本原多项式 $(x^{4}+x+1)$ 和 $(x^{4}+x^{3}+1)$。由其中任何一个都可 产生 m 序列。用 $\mathrm{f}(\mathrm{x})=(\mathrm{x}^{4}+\mathrm{x}+\mathbf{1})$ 形成的 $\mathrm{m}$ 序列产生器如图所示。
设 4 级移位寄存器的初始状态为 1000 ,$c_{4}=c_{1}=c_{0}=1, c_{3}=c_{2}=0$。输入序列 $\{a_{k}\}$ 的周期长度为 15。
m 序列的性质
平衡个性(平衡性)
m 序列每一周期中 1 的个数比 0 的个数多 1 个。因为 $p=2^{n}-1$ 为奇 数, 因此在每一周期中 1 的个数为 $(p+1) / 2=2^{n-1}$ (偶数), 而 0 的 个数为 $(p-1) / 2=2^{n-1}-1$ (奇数)。上例中 p=15,1 的个数为 8,0 的个 数为 7。当 p 足够大时, 在一个周期中 1 与 0 呈现的次数根本相等。
游程个性(游程散布的随机性)
咱们把一个序列中取值 (1 或 0) 雷同连在一起的元素合称为一个游程。在一个游程中元素的个数称为游程长度。例如图中给出的 $\boldsymbol{m}$ 序列
在其一个周期的 15 个元素中, 共有 8 个游程
长度为 4 的游程 1 个, 即 1111 ;
长度为 3 的游程 1 个, 即 000 ;
长度为 2 的游程 2 个, 即 11 与 00 ;
长度为 1 的游程 4 个, 即 2 个 1 与 2 个 0。
m 序列的一个周期 $(p=2^{n-1})$ 中, 游程总数为 $2^{n-1}$。
长度为 1 的游程个数占游程总数的 1 / 2 ; 长度为 2 的游程个数占游 程总数的 $1 / 2^{2}=1 / 4$ ; 长度为 3 的游程个数占游程总数的 $1 / 2^{3}=1 / 8$ 等等。
个别地, 长度为 k 的游程个数占游程总数的 $1 / 2^{k}=2^{-k}$ , 其 中 $1 \leq k \leq(n-2)$。而且, 在长度为 k 的游程中, 连 1 游程与连 0 游程各占一半, 长为 (n-1) 的游程是连 0 游程, 长为 n 的游程是连 1 游程。
移位相加个性(线性叠加性)
$\boldsymbol{m}$ 序列和它的位移序列模二相加后所得序列仍是该 $\boldsymbol{m}$ 序列的某个 位移序列。设 $m_{r}$ 是周期为 p 的 m 序列 $m_{p}$ 的 r 次提早移位后的序列, 那么
$$
m_{p} \oplus m_{r}=m_{s}
$$
其中, $m_{s}$ 为 $m_{p}$ 某次提早移位后的序列。例如，
$$
m_{p}=000111101011001, \ldots
$$
$m_{p}$ 提早两位后得 $m_{r}$ , 再模二相加
$$
\begin{array}{l}
m_{r}=\mathbf{0} 10001111010 \\
m_{\mathrm{s}}=\boldsymbol{m}_{\mathrm{p}} \oplus \boldsymbol{m}_{r}=\mathbf{0} 10110, \ldots
\end{array}
$$
可见, $m_{\mathrm{s}}=m_{\mathrm{p}} \oplus m_{r}$ 为 $m_{p}$ 提早 8 位后的序列。
自相干个性
$\boldsymbol{m}$ 序列具备十分重要的自相干个性。在 $\boldsymbol{m}$ 序列中, 经常用 +1 代表 0 , 用 - 1 代表 1。此时定义：设长为 p 的 $\boldsymbol{m}$ 序列, 记作
$$
a_{1}, a_{2}, a_{3}, \ldots, a_{p}(p=2^{n-1})
$$
通过 $\boldsymbol{j}$ 次移位后, $\boldsymbol{m}$ 序列为
$$
a_{j+1}, a_{j+2}, a_{j+3}, \ldots, a_{j+p}
$$
其中, $a_{i+p}=a_{i}$ (以 p 为周期), 以上两序列的对应项相乘而后相加, 利用所得的总和
$$
a_{1} \cdot a_{j+1}+a_{2} \cdot a_{j+2}+a_{3} \cdot a_{j+3}+\cdots+a_{p} \cdot a_{j+p}=\sum_{i=1}^{p} a_{i} a_{j+i}
$$
来掂量一个 m 序列与它的 j 次移位序列之间的相干水平, 并把它叫 做 $\boldsymbol{m}$ 序列 $(a_{1}, a_{2}, a_{3}, \ldots, a_{p})$ 的自相干函数。记作
$$
R(j)=\sum_{i=1}^{p} a_{i} a_{j+i}
$$
当采纳二进制数字 0 和 1 代表码元的可能取值时, 上式可示意为
$$
R(j)=\frac{A-D}{A+D}=\frac{A-D}{p}
$$
式中, A、D 别离是 $\boldsymbol{m}$ 序列与其 j 次移位的序列在一个周期中对应元素雷同、不雷同的数目, 还能够改写为
$$
R(j)=\frac{[a_{i} \oplus a_{i+j}=0] \text {的数目}-[a_{i} \oplus a_{i+j}=1] \text {的数目}}{p}
$$
由移位相加个性可知, $a_{i} \oplus a_{i+j}$ 仍是 m 序列中的元素, 所以式分子就等于 m 序列中一个周期中 0 的数目与 1 的数目之差。另外由 $\boldsymbol{m}$ 序列的均衡性可知, 在一个周期中 0 比 1 的个数少一个, 故得 $A-D=- 1$ (j 为非零整数时) 或 p(j 为零时)。因而得
$$
R(j)=\{\begin{array}{ll}
1 & j=0 \\
\frac{-1}{p} & j=\pm 1, \pm 2, \ldots, \pm(p-1)
\end{array}.
$$
$\mathrm{m}$ 序列的自相干函数只有两种取值 (1 和 -1 / p)。R(j) 是一个周期函数, 即
$$
\boldsymbol{R}(j)=\boldsymbol{R}(j+k p)
$$
式中, $k=1,2, \ldots, p=(2^{n}-1)$ 为周期。而且 $R(j)$ 是偶函数, 即
$$
R(j)=R(-j) \quad j=\text {整数}
$$
伪噪声个性
如果咱们对一个正态分布白噪声取样，若取样值为正，记为 +1，
若取样值为负，记为 -1，将每次取样所得极性排成序列，能够写成 …+1,-1,+1,+1,+1,-1,-1,+1,-1,…
这是一个随机序列，它具备如下根本性质:(1)序列中 + 1 和 - 1 呈现的概率相等;
序列中长度为 1 的游程约占 1 / 2 , 长度为 2 的游程约占 1 / 4 , 长度为 3 的游程约占 1 / 8, $\ldots$ 个别地, 长度为 $\mathrm{k}$ 的游程约占 $1 / 2^{k}$ , 而且 +1、-1 游程的数目各占一半;
因为白噪声的功率谱为常数, 因而其自相干函数为一冲击函数 $\delta(\tau)$。把 $\boldsymbol{m}$ 序列与上述随机序列比拟, 当周期长度 $\boldsymbol{p}$ 足够大时, $\boldsymbol{m}$ 序列与随机序列的性质是十分相似的。可见, $\boldsymbol{m}$ 序列是一种伪喿声个性较好的伪随机序列, 且易产生, 因而利用非常宽泛。
参考文献：
- Proakis, John G., et al. Communication systems engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
- Proakis, John G., et al. SOLUTIONS MANUAL Communication Systems Engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
- 周炯槃. 通信原理（第 3 版）[M]. 北京：北京邮电大学出版社, 2008.
- 樊昌信, 曹丽娜. 通信原理（第 7 版）[M]. 北京：国防工业出版社, 2012.
