📘 第 7 章：通信系统

这一篇在干嘛？

FPGA 在通信里的两大应用：加密（编码理论、分组码、卷积码）与调制解调（相干/非相干解调的设计实现）。 原书代码为 VHDL，本篇所有代码已改写为 Verilog。

• 第7章
• 通信系统
• 7.1 差错控制和加密技术
• 1. 使用海明码纠错
• 2. 纠错码综述
• 3. 编码边界
• 1. 编码器
• 2. 译码器
• 1. 维特比极大似然序列译码器
• 2. QLI 译码器的纠错性能
• 3. 伴随式代数译码器
• 4. 逐次逼近译码器的纠错能力
• 5. 最终的比较
• 1. 线性反馈移位寄存器算法
• 例7.1 长度为6的LFSR
• 例7.2 三同步LFSR
• 2. 组合 LFSR
• 3. 基于 DES 的算法
• 4. 加密性能比较
• 5. 加密安全的注意事项
• 7.2 调制和解调
• 例7.3 采用CORDIC的通用调制器
• 例7.4 零IF接收器
• 窄带接收器的简化
• 1. 线性锁相环
• 2. 数字锁相环
• 3. 边环(Costas loop)
• 7.3 练习

---

自测一下

汉明码能纠几位错？校验位怎么定？

能纠 1 位错。校验位放在 2 的幂次位置，每个校验位负责所有”二进制位权含该位”的数据位；出错时校验子拼出的二进制数就是错误位置。

卷积码的约束长度和码率分别指什么？

约束长度 K=寄存器级数+1（输出与多少位输入相关）；码率 k/n=每次输入 k 位输出 n 位（如 1/2 码率：1 位进 2 位出，效率 50%）。

维特比译码为什么能最优？

它按网格图做最大似然序列估计：保留每个状态的最优路径（加-比-选），丢弃不可能路径，最终全局最优路径必在其中。

相干解调比非相干多需要什么？

相干解调需要在接收端恢复出与载波同频同相的参考（锁相环/科斯塔斯环），换取更好的误码率；非相干（如包络检波）不用载波恢复但损失约 1~2 dB。

第7章 通信系统

FPGA 有一个 PDSP（可编程数字信号处理器）难以匹敌的天然优势：它可以按”位”来构造电路。通信系统里的差错控制和加密算法，恰恰大量使用逐位运算和移位寄存器，这类结构在 FPGA 上实现得又快又省。一个直观的例子：如果用一个 $N$ 位的 LFSR 做 $M$ 步多步数字发生器，FPGA 相比 PDSP 或微处理器至少有 $MN$ 倍的速度优势。本章先介绍差错控制与加密的两个基本构件——有限域运算和线性反馈移位寄存器（LFSR），再用一个 FPGA 接收器设计说明低系统成本、高吞吐量和快速原型设计的可行性。

7.1 差错控制和加密技术

是什么：纠错编码能在受频带限制的信道上比专用调制模式更好地利用信道容量（图 7-1 给出了各种调制模式的性能对比）。所以寻呼机、移动电话、卫星传输等现代通信系统都用算法来纠正传输错误；此外大多数系统还会叠加加密算法，既防止消息被窃听，也防止消息被篡改。

图 7-1 调制模式的性能。实线表示相干解调，虚线表示非相干解调

放在哪里：如图 7-2 所示，编码器（纠错或加密）位于数据源和调制器之间；接收端译码器位于解调器和数据目的地之间。编码器和译码器通常合并成一个电路，叫 CODEC（coder/decoder，编/译码器）。

图 7-2 典型的通信系统配置

为什么用 FPGA：典型的纠错和加密算法都依赖有限域运算，可以用逐位运算或 LFSR 高效实现，这正对 FPGA 的胃口；而 PDSP 是面向乘加优化的，做这类位级运算并不划算。有些 CODEC 需要大容量查找表，选算法时就要注意哪些才适合 FPGA。本节给出的算法已实际用于低频寻呼系统和无线电控制监视器的纠错模式。

7.1.1 编码理论的基本概念

1. 从重复码到海明码

最笨但最直白的办法——重复码：把消息原样发几遍。例如重复 5 次：

$$0\iff 00000\text{\hspace{1em}(7-1)}$$ $$1\iff 11111\text{\hspace{1em}(7-2)}$$

左边是第 $k$ 个信息位，右边是 $n$ 位码字。两个码字之间的最短距离叫海明距离（Hamming Distance）$d^{\ast }$，重复码的 $d^{\ast }=n$，记作 $(n,k,d^{\ast })=(5,1,5)$，最多能纠正 $\lfloor (n-1)/2\rfloor$ 个随机错误（5 位里错 2 位以内都能投票投回来）。但信道效率只有 1/5，太浪费。如果信道是双向的，用奇偶校验加自动重复请求（ARQ）更划算——PC 内存里的奇偶校验就是这个思路。

聪明一点——海明码：把几个奇偶校验位组合起来，就能不但发现错误，还能定位错误。设校验位用模 2 运算（即 XOR）计算：

$$P_{1,0}=i_{21}\oplus i_{22}\oplus i_{23}\oplus i_{24}\oplus i_{25}\oplus i_{26}\oplus i_{27}$$ $$P_{1,1}=i_{21}\oplus i_{23}\oplus i_{25}\oplus i_{27},P_{1,2}=i_{21}\oplus i_{22}\oplus i_{25}\oplus i_{26},P_{1,3}=i_{21}\oplus i_{22}\oplus i_{23}\oplus i_{24}$$

译码端把”新算出的校验”与”收到的校验”逐个 XOR，得到的 $(S_{1,0},\dots ,S_{1,3})$ 称为伴随式（syndrome）。巧妙之处在于校验的选择：伴随式模式正好等于二进制表示的差错位位置，于是用一个 $3\to 7$ 译码器（信号分离器）就能直接指出错在哪一位。图 7-3(a) 是编码器，图 7-3(b) 是含校正逻辑的译码器。

图 7-3(a) 海明码的编码器

图 7-3(b) 海明码的译码器

用矩阵可以写得更紧凑。奇偶校验矩阵：

$$\mathbf{H}=\left[{\mathbf{P}}^T:\mathbf{I}\right]=\left[\begin{array}{ccccccccccc}1& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 1\end{array}\right]\text{\hspace{1em}(7-3)}$$

编码器则用生成矩阵 $\mathbf{G}=[\mathbf{I}:\mathbf{P}]$（单位矩阵 + 奇偶位矩阵），码字由信息字与生成矩阵模 2 相乘得到：

$$v=i\times \mathbf{G}\text{\hspace{1em}(7-4)}$$

图 7-3 的编码器对应 $(11,7,3)$ 海明码，可检测并纠正 1 个差错。一般地，4 个校验位最多可保护 15 个信息位，即 $(15,11,3)$ 码可以缩短成 $(11,7,3)$。距离为 3 的海明码结构是 $(2^m-1,2^m-m,3)$。例如无线电控制监视器里的日期编码成 22 位，把 $(31,26,3)$ 海明码缩短成 $(27,22,3)$，就得到单差错纠错码，其奇偶校验矩阵为：

$$\mathbf{H}=\left[\begin{array}{ccccccccccccccccccccccccccc}1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 0& 0& 0& & & & \\ 1& 1& 0& 0& 1& 1& 0& 0& 1& 1& 0& 0& 1& 1& 0& 0& 1& 1& 0& 0& 1& 1& 0& 1& 0& 0& 0\\ 1& 1& 1& 1& 0& 0& 0& 0& 1& 1& 1& 1& 0& 0& 0& 0& 1& 1& 1& 1& 0& 0& 0& 0& 1& 0& 0\\ 1& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\end{array}\right]$$

此时校正逻辑就是一个简单的 $5\to 22$ 译码器。表 7-1 给出了该监视器用 Xilinx FPGA 实现时按 CLB 计的预计工作量，分钟、小时、日期三个数据块各用一套。

表 7-1 海明码纠错的预计工作量

分组海明码	分钟(11,7,3)	小时(10,6,3)	日期(27,22,3)
寄存器	6	6	14
伴随式计算	5	5	16
校正逻辑	4	4	22
输出寄存器	4	4	11
和	19	19	63
总计	101

总之，对分钟块用额外的 $3+3+5=11$ 位校验（约 100 个 CLB），就能纠正三个数据块各自的一个差错。

2. 纠错码综述

实际系统通常一个发射器对多个接收器（寻呼机、无线电都是如此），所以译码器的工作量更受关注。图 7-4 给出了可行的译码器框图。

图 7-4 用于纠错的译码器

按生成过程是否使用”存储器”，编码分两大类。两者都用编码率 $R=k/n$（信息位数与码长的比）描述。对带存储器的树型码，当前输出的 $n$ 位不仅取决于当前的 $k$ 个信息位，还依赖前面 $m$ 个符号（图 7-5）；其特征还有存储长度 $v=m\times k$、距离剖面、自由距离 $d_f$ 和最小距离 $d_m$。分组码通常用有限域代数方法构造，而树型码一般只出现在计算机仿真中。

图 7-5 卷积编码器的参数

若限定为线性码（两个码字之和仍是码字），译码器实现会简化：海明距离总可以按”码字与零字之差”来计算，便于比较编码性能。线性树型码因可用类 FIR 结构构造而得名卷积码。卷积码分灾难性与非灾难性：灾难性编码会把单个差错一直传播下去，可以证明系统卷积码总是非灾难性的。此外还常区分随机差错校正码（差错可出现在码字任意位置）与突发差错校正码（能对付一长串连续差错或删除）。

3. 编码边界

编码边界给出编码纠错能力的理论上限，译码器不可能超过它；实际设计常故意低于边界以降低译码复杂度。

辛格顿界（Singleton Bound）：最小海明距离的上限受奇偶位数量 $(n-k)$ 限制。可纠正差错数 $t$ 与可删除数 $e$ 满足：

$$e+2t+1⩽d^{\ast }⩽n-k+1\text{\hspace{1em}(7-5)}$$

$d^{\ast }=n-k+1$ 的码叫最大距离可分码，但二进制下除重复码和奇偶校验码外不存在。对表 7-1 的例子，11 个校验位的上限是纠正 5 个差错。

海明界：$t$ 位纠错二进制码须满足

$$2^{n-k}⩾\sum _{m=0}^t\left(\genfrac{}{}{0ex}{}{n}{m}\right)\text{\hspace{1em}(7-6)}$$

直观理解：奇偶校验模式的可能数量（$2^{n-k}$）必须覆盖所有可能的差错模式数量。等号成立时称为完全码（Perfect Code）——海明码就是完全码。举一个计算示例：要保护无线电控制监视器每分钟传输的全部 44 位，试用 13 个校验位：

$$2^{13}>\left(\genfrac{}{}{0ex}{}{44}{0}\right)+\left(\genfrac{}{}{0ex}{}{44}{1}\right)+\left(\genfrac{}{}{0ex}{}{44}{2}\right)\text{\hspace{1em}(7-7)}$$

但

$$2^{13}<\left(\genfrac{}{}{0ex}{}{44}{0}\right)+\left(\genfrac{}{}{0ex}{}{44}{1}\right)+\left(\genfrac{}{}{0ex}{}{44}{2}\right)+\left(\genfrac{}{}{0ex}{}{44}{3}\right)\text{\hspace{1em}(7-8)}$$

也就是说，能找到纠正 2 个随机差错的编码，但纠正 3 个差错的编码不存在。

7.1.2 分组码

线性循环二进制 BCH 码（以 Bose、Chaudhuri、Hocquenghem 命名）及其子类 Reed-Solomon 码构成一大类分组码，时域和频域都有高效译码器。下面以 $(57,44,6)$ BCH 码为例。编码以 $\mathrm{GF}(2^6)$ 到 $\mathrm{GF}(2)$ 的变换为基础，需要一个 6 次本原多项式，例如 $P(x)=x^6+x+1$。生成多项式由 $\mathrm{GF}(2^6)$ 中前 $d-1=5$ 个最小多项式的最小公倍数算出：设 $\alpha$ 为本原元素，${\alpha }^0=1$ 的最小多项式是 $m_1(x)=x-1$；$\alpha$、${\alpha }^2$、${\alpha }^4$ 共享 $m_{\alpha }(x)=x^6+x+1$；${\alpha }^3$ 的最小多项式是 $m_{{\alpha }^3}(x)=x^6+x^4+x^2+x+1$。于是：

$$g(x)=m_1(x)\times m_{\alpha }(x)\times m_{{\alpha }^3}(x)\text{\hspace{1em}(7-9)}$$ $$=x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^6+x^3+x+1\text{\hspace{1em}(7-10)}$$

1. 编码器

要得到系统码（码字前段就是信息位本身），校验位由移位后的信息位对 $g(x)$ 取模得到：

$$p(x)=i(x)\times x^{n-k}\mathrm{mod}g(x)\text{\hspace{1em}(7-11)}$$

这个模化简可以用一个递归移位寄存器实现（图 7-6），工作流程：开关 A、B 闭合，C 断开；信息位（MSB 先）一方面直接输出为码字，一方面送入寄存器算校验；信息位处理完后，A、B 断开、C 闭合，把校验位移入码字。

图 7-6 BCH 码(57, 44, 6)的编码器

2. 译码器

译码器通常比编码器复杂得多。Meggitt 译码器利用 BCH 码的循环性质：只校正 MSB 位置上的差错，然后循环移位再算，最终所有被破坏的位都会经过 MSB 位置而被纠正（图 7-7）。它对只需校正少量差错的码特别有效。这类译码器也有现成的 FPGA IP 模块（“虚拟组件”VC）可商用。

图 7-7 Meggitt 译码器的基本模块

要用缩短码并恢复循环性质，必须对收到的数据计算前向耦合。把码缩短 $b$ 位时按式(7-12)处理：

$$s(x)=a(x)i(x)\mathrm{mod}g(x)=x^{n-k+b}i(x)\mathrm{mod}g(x)\text{\hspace{1em}(7-12)}$$

对缩短的 BCH 码 $(57,44,6)$：

$$\begin{array}{rl}a(x)& =x^{63-50+6}\mathrm{mod}g(x)=x^{19}\mathrm{mod}g(x)\\ & =x^{19}\mathrm{mod}(x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^6+x^3+x+1)\\ & =x^{10}+x^7+x^6+x^5+x^3+x+1\end{array}$$

该码能纠 2 个差错。只校正 MSB 位差错时，需要存储 $1+56=57$ 种差错模式（表 7-2），这些伴随值可通过仿真算出。

表 7-2 可能的差错模式

编号	差错模式
1	0	0	0	…	0	0	1
2	0	0	0	…	0	1	1
3	0	0	0	…	1	0	1
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
56	0	1	0	…	0	0	1
57	1	0	0	…	0	0	1

图 7-8 BCH 码(57, 44, 6)的 Meggitt 译码器

Meggitt 译码器分两级（图 7-8）：初始化阶段对收到的位做模 $g(x)$ 运算计算伴随式，共 57 个循环；第二阶段实纠错——把伴随式寄存器内容与伴随式表比较，命中则输出 1（瞬时干扰位），与移位寄存器中的接收位 XOR，把差错”剔出”移位寄存器；瞬时干扰位同时回馈给伴随式寄存器，把差错模式也从伴随式中剔除。如此循环，最终移位寄存器应包含校正后的码字，伴随式寄存器应为全零；若不为零，说明出现了 2 个以上无法校正的差错。

FPGA 实现的关键是伴随式表有 13 个输入，而 FPGA 的 LUT 通常只有 4~8 个输入。可用外部 EPROM 或一个 M9K 嵌入式存储器实现 $2^{13}\times 1$ 的表（表接到地址线，57 个伴随式位置输出 1，其余输出 0）；也可用逻辑合成工具在内部逻辑中算出。旧式合成器需 132 个 $2^4\times 2$ 位 LUT，现代 BDD（二进制决策图）合成器可降到 58 个（代价是额外延迟）。表 7-3 比较了三种伴随式表方案的资源。

表 7-3 对于 3 种 Meggitt 译码器版本，Altera FPGA 器件的预计工作量（嵌入式存储器用作 $2^{11}\times 1$ ROM）

功能组	使用M9K	仅有LE	BDD
接口	36 LE	36 LE	36 LE
伴随式表	2 LE + 1 M9K	264 LE	116 LE
64位FIFO	64 LE	64 LE	64 LE
Meggitt译码器	12 LE	12 LE	12 LE
状态机	21 LE	21 LE	21 LE
总计	135 LE + 1 M9K	397 LE	249 LE

7.1.3 卷积码

下面探讨适合 FPGA 的卷积纠错译码器。先约定典型通信系统的约束条件：译码器复杂度优先最低（编码器复杂度其次）；编码线性、卷积、允许随机差错校正。规定系统码可提供一种”断电模式”——只接收到达的位而不纠错；信道缓慢衰减时须用随机差错校正码。图 7-9 给出树型码的框架，图 7-4 给出译码器框图。Fano 译码器和栈译码器因组织栈太复杂，不适合 FPGA，传统 $\mu$P/$\mu$C 更合适。下面在硬件复杂度（Xilinx CLB 计）与可实现的纠错能力两方面，比较极大似然序列译码器和代数算法。

图 7-9 树型码的框架

1. 维特比极大似然序列译码器

维特比（Viterbi）译码器用最小海明距离判定发送序列，是格子图上的最优无记忆干扰序列估计器（MLSE）。它的优点是译码时间恒定且具有 MLSE 最优性；缺点是存储需求大，因而只能用约束长度很短的码。图 7-10、图 7-11 给出 $R=k/n=1/2$ 的编码器（译码器）和伴随格子图。约束长度 $v=m\times k=2$，格子有 $2^v$ 个节点，每个节点引出 $2^k=2$ 条边、引入至多 2 条边。二进制格子（$k=1$）习惯上把上边沿当 0、下边沿当 1。

图 7-10 R=1/2 卷积译码器的编码器

图 7-11 R=1/2 卷积译码器的格子

MLSE 译码只需存储每个时刻通过各节点的 $2^v$ 条路径（及其度量），因为最优路径必然经过其中之一；度量更小的引入路径可以直接丢弃。路径存储器取 4~5 倍约束长度即可，无限存储并无明显收益（这类似用存储器解调数字 FM 信号时对局部错误的否决）。维特比译码器硬件有三块：带输出译码器的路径存储器（图 7-12，$4v{2}^v$ 位，$2v{2}^v$ 个 CLB；输出译码器用 $(1+2+\dots +2^{v-1})$ 个 2→1 多路复用器）、残存路径计算与最大值检测（图 7-13）。度量加法器、寄存器、比较器位宽为 $(\lceil {\log }_2(v\times n)\rceil +1)$ 位。

图 7-12 约束长度为 4v 和 2^(v=2) 个节点的维特比译码器：路径存储器和输出译码器

图 7-13 约束长度为 4v 和 2^(v=2) 个节点的维特比译码器：度量标准计算

$k>1$ 的译码器在当今 FPGA 上太复杂；$n>2$ 时信息率 $R=1/n$ 太低。所以最适合的编码率是 $R=1/2$。表 7-4 列出 $v=2,3,4$ 及一般情形的硬件复杂度——复杂度随 $v$ 指数增长，所以约束长度要尽量短；短约束长度的纠错窗口虽小，但 MLSE 算法仍保证可接受的性能。

表 7-4 对于 R=1/2 的维特比译码器，当 v=2、3、4 时和一般情况下的硬件复杂性（按 CLB 计算）

功能	v=2	v=3	v=4	v∈N
路径存储器	16	48	128	$4\times v\times 2^{v-1}$
输出译码器	1.5	3.5	6.5	$1+2+\dots +2^{v-2}$
度量标准 $\Delta M$	4	4	4	4
度量标准清除	1	2	4	$\lceil (2+4+\dots +2^{v-1})/4\rceil$
度量标准加法器	24	64	128	$(\lceil {\log }_2(nv)\rceil +1)\times 2^{v+1}$
残存部分多路复用器	6	24	48	$(\lceil {\log }_2(nv)\rceil +1)\times 2^{v-1}$
度量标准比较	6	24	48	$(\lceil {\log }_2(nv)\rceil +1)\times 2^{v-1}$
最大值比较	4.5	14	30	$(\lceil {\log }_2(nv)\rceil +1)\times \frac{1}{2}\times (1+2+\cdots +2^{v-1})$
多路复用器	3	12	28	$(2+\cdots +2^{v-1})\times \frac{1}{2}\times (\lceil {\log }_2(nv)\rceil +1)$
译码器	1	2	4	$\lceil (2+\dots +2^{v-1})/4\rceil$
状态机	4	4	4
总计	67	197.5	428.5

生成多项式的选择：非系统码性能优于系统码，但系统码才能满足”使用未纠错信息位”的断电要求。快速搜索（Quick Look In, QLI）码是 $R=1/2$ 的非系统卷积码，距离性能与已知同约束长度的码一样好，且信息序列重构只需一个 XOR 门。$v=2$ 至 4 的 QLI 码分别有 $d_f=5$ 至 7 的距离，是低功耗场景的良好折中。表 7-5 上半部分给出八进制形式的生成多项式。

2. QLI 译码器的纠错性能

用”一致限”方法计算：QLI 码是线性的，差错序列可按与零序列之差求。若一个序列从空状态出发、在 $j$ 个独立时间步长内偏离空字且含至少 $j/2$ 个 1，MLSE 译码器就会误判，其概率为：

$$p_j=\{\begin{array}{ll}{\sum }_{i=(j+1)/2}^j\left(\genfrac{}{}{0ex}{}{j}{i}\right)p^i{q}^{j-i}& j\text{为奇数}\\ \frac{1}{2}\left(\genfrac{}{}{0ex}{}{j}{j/2}\right)p^{j/2}{q}^{j/2}+{\sum }_{i=j/2+1}^j\left(\genfrac{}{}{0ex}{}{j}{i}\right)p^i{q}^{j-i}& j\text{为偶数}\end{array}\text{\hspace{1em}(7-13)}$$

剩下的工作只是数出权重为 $j$ 的路径数量 $w_j$（简单编程即可），且 $P_j$ 随 $j$ 指数衰减，只需算前几项。总错误概率：

$$P_b<\frac{1}{k}\sum _{j=0}^{\infty }{w}_j{P}_j\text{\hspace{1em}(7-14)}$$

表 7-5 下半部分给出了 $j=0$ 至 20 的 $w_j$。

表 7-5 采用 QLI 码的维特比译码器 v=2~4 的一致限权重

代码	O1=7	O1=74	O1=66
	O2=5	O2=54	O2=46
约束长度	v=2	v=3	v=4
距离	权重 $w_j$
0至4	0	0	0
5	1	0	0
6	4	2	0
7	12	7	4
8	32	18	12
9	80	49	26
10	192	130	74
11	448	333	205
12	1024	836	530
13	2304	2069	1369
14	5120	5060	3476
15	11264	12255	8470
16	24576	29444	19772
17	53079	64183	43062
18	109396	126260	83346
19	103665	223980	147474
20	262144	351956	244458

3. 伴随式代数译码器

伴随式译码器（图 7-14）与编码器（图 7-15）同分组码一样计算若干奇偶位：译码器新算的奇偶位与收到的奇偶位 XOR 得到”伴随”字，无差错时伴随字为零；差错的位置和值由伴随值确定。与只用一个生成多项式的分组码不同，编码率 $R=k/n$ 的卷积码有 $k+1$ 个生成多项式，可写成 $n\times k$ 生成矩阵。图 7-15 编码器（$R=1/2$、约束长度 $v=22$ 的系统码 (44,22)）的矩阵：

$$\mathbf{G}(x)=\left[1x^{21}+x^{20}+x^{19}+x^{17}+x^{16}+x^{13}+x^{11}+1\right]\text{\hspace{1em}(7-15)}$$

图 7-14 J=8 的逐次逼近多数逻辑译码器

图 7-15 数据传输率 R=1/2 且约束长度 v=22 的系统编码器(44,22)

对系统码 $\mathbf{G}(x)=[\mathbf{I}:\mathbf{P}(x)]$，由 $\mathbf{G}\times {\mathbf{H}}^T=0$ 得奇偶校验矩阵 $\mathbf{H}(x)=[-\mathbf{P}(x{)}^T:\mathbf{I}]$，伴随式向量为 $\mathbf{S}=v\times {\mathbf{H}}^T$（$v$ 为收到的位序列）。译码器查表找校正序列；为限制表规模，只允许第一位位置出现一个差错。要纠多个差错时，校正后不清除伴随式，而是把伴随值从伴随式寄存器中减去（图 7-14 中的”多数”信号）。

标准卷积译码器需要 22 位宽的表，而 FPGA 查找表很难做到超过 4~11 位地址。多数编码（一类特殊的伴随式可译码编码）在此显出优势：标准自正交编码（CSOC）的奇偶校验矩阵 $\{A_k\}$ 第一行有专有的 1，$J$ 列构成计算伴随式的正交集，于是第一位位置的每个差错都会在伴随式寄存器中产生至少 $\lceil J/2\rceil$ 个 1。译码规则：

$$e_0^i=\{\begin{array}{ll}1& {\sum }_{k=1}^J{A}_k>\lceil J/2\rceil \\ 0& \text{其他}\end{array}\text{\hspace{1em}(7-16)}$$

“多数”之名由此而来：除了昂贵的伴随式表，只需要”多数表决”。Massey 设计的逐次逼近码不直接算伴随式向量，而是操纵伴随位的组合得到与 $e_0^i$ 正交的向量，硬件成本略增但纠错性能更佳。表 7-6列出 $R=1/2$ 的几个逐次逼近码；图 7-14 是 $J=8$ 的译码器；表 7-7给出 $J=4$ 至 10 的复杂度。

表 7-6 一些多数可译码的逐次逼近代码

J	$t_{MD}$	v	生成多项式	正交方程式
2	1	2	$1+x$	$s_0,s_1$
4	2	6	$1+x^3+x^4+x^5$	$s_0,s_3,s_4,s_1+s_5$
6	3	12	$1+x^6+x^7+x^9+x^{10}+x^{11}$	$s_0,s_6,s_7,s_9,s_1+s_3+s_{10},s_4+s_8+s_{11}$
8	4	22	$1+x^{11}+x^{13}+x^{16}+x^{17}+x^{19}+x^{20}+x^{21}$	$s_0,s_{11},s_{13},s_{16},s_{17},s_2+s_3+s_6+s_{19},s_4+s_{14}+s_{20},s_1+s_5+s_8+s_{15}+s_{21}$
10	5	36	$1+x^{18}+x^{19}+x^{27}+x^{28}+x^{29}+x^{30}+x^{32}+x^{33}+x^{35}$	$s_0,s_{18},s_{19},s_{27},s_1+s_9+s_{28},s_{10}+s_{20}+s_{29},s_{11}+s_{30}+s_{31},s_{13}+s_{21}+s_{23}+s_{32},s_{14}+s_{33}+s_{34},s_2+s_3+s_{16}+s_{24}+s_{26}+s_{35}$

表 7-7 J=4 至 10 的多数译码器的复杂性（按 CLB 计算）

功能	J=4	J=6	J=8	J=10
寄存器	6	12	22	36
XOR门	2	4	7	11
多数电路	1	5	7	15
和	9	22	36	62

4. 逐次逼近译码器的纠错能力

在 $2\times$ 约束长度的窗口内，编码允许多达 $\lfloor J/2\rfloor$ 位差错：

$$P(J)=\sum _{k=0}^{\lfloor J/2\rfloor }\left(\genfrac{}{}{0ex}{}{2v}{k}\right)p^k(1-p{)}^{2v-k}\text{\hspace{1em}(7-17)}$$

$10^6$ 位的计算机仿真结果与上式吻合良好（图 7-16）。$(n,k)$ 编码的等效单差错概率 $P_B$ 由下式换算：

$$P(J)=P(0)=(1-P_B{)}^k\Rightarrow P_B=1-e^{\ln (P(J))/k}\text{\hspace{1em}(7-18)}$$

图 7-16 维特比和多数逻辑译码器的性能比较

5. 最终的比较

在可比的硬件成本下（维特比译码器：$v=2$、$d_f=5$、67 个 CLB；逐次逼近译码器：$t=5$、62 个 CLB），多数译码器因为允许大得多的约束长度，性能立刻胜出——维特比算法的 MLSE 最优性弥补不了它的短约束长度。

7.1.4 FPGA 的加密算法

许多通信系统用数据流密码保护信息（图 7-17）：密钥序列 $K$ 是一个收发双方都知道的”伪随机序列”，利用 XOR 的模 2 性质，明文 $P$ 可在接收端重构：

$$P\oplus K\oplus K=P\oplus 0=P\text{\hspace{1em}(7-20)}$$

图 7-17 同步数据流密码的规则

下面比较基于 LFSR 的算法和 DES（数据加密标准）算法。两者都不需要大容量表，都非常适合 FPGA。

1. 线性反馈移位寄存器算法

具有最大序列长度的 LFSR 是理想安全密钥的好素材：统计性质良好，密码分析者难以分析该序列；而 FPGA 按位设计的特性使 LFSR 实现比 PDSP 高效得多。图 7-18 给出长度为 8 的两种 LFSR 实现。XOR 型 LFSR 存在全零字的可能，但全零态永远不该出现——只要从任意非零字启动，循环长度就是 $2^l-1$。如果 FPGA 上电唤醒时恰好是全零字，用”镜像”或翻转的 LFSR 更方便；若希望全零字是有效模式，就用 XNOR 门代替 XOR 门。

图 7-18 LFSR 的可行实现

例 7.1 长度为 6 的 LFSR

原书 VHDL 改写为 Verilog：

module lfsr (              // 接口
    input  wire clk,       // 系统时钟
    input  wire reset,     // 异步复位
    output wire [6:1] y    // 系统输出
);
 
    reg [6:1] ff;
 
    always @(posedge clk or posedge reset) begin
        if (reset)                       // 异步清零
            ff <= 6'b000000;
        else begin
            ff[1] <= ~(ff[5] ^ ff[6]);   // 用 XNOR 实现长度6的LFSR
            ff[6:2] <= ff[5:1];          // 抽头延迟线：移位一位
        end
    end
 
    assign y = ff;                       // 连接到输出单元
 
endmodule

从图 7-19 的仿真结果可以得出结论：LFSR 走遍除全零外的所有位模式，生成最大序列长度 $2^6-1=63\approx 630\text{ns}/10\text{ns}$。该设计使用 6 个 LE，未用嵌入式乘法器，TimeQuest 缓慢 85C 模型下时序性能 $F_{max}=944.29\text{MHz}$。

图 7-19 LFSR 的仿真结果

注意：LFSR 序列的完整循环满足 Golomb 定义的、最优长度 $2^l-1$ 伪随机序列的三个条件：

1. 一个循环中，1 和 0 的数量之差不超过 1。
2. 行程为 $k$ 的游程（如 111… 序列、000… 序列）占总游程的 $1/2^k$。
3. 自相关函数 $C(\tau )$ 在 $\tau \in [1,n-1]$内为常数。

LFSR 通常用 GF(2) 中的本原多项式按图 7-18 电路构造。Stahnke 编译了多达 168 阶的本原多项式列表，可用 MAPLE、MUPAD 或 MAGMA 等数学软件扩展。下面是计算 $x^l+x^a+1$ 型且 $a$ 最小的本原多项式的 MAPLE 代码示例：

With(numtheory): for l from 2 by 1 to 45 do
    for a from 1 by 1 to l-1 do
    if (Primitive(x^l-x^a+1) mod 2) then
    print(l,a);
    break;
    fi;
    od;
od;

表 7-8 按图 7-18(a) 给出前 45 个最大长度 LFSR 所需的抽头指数。例如 $l=14$ 的 (14, 13, 11, 9) 意味着本原多项式为：

$$p_{14}(x)=x^{14}+x^{14-13}+x^{14-11}+x^{14-9}+1=x^{14}+x^5+x^3+x+1$$

$l>2$ 时这些本原多项式都有等价多项式（也是本原的），即时域可逆形式 $x^l+x^{l-a}+1$。

表 7-8 前 45 个 LFSR 的列表

l	指数	l	指数	l	指数
1	1	16	16, 14, 13, 11	31	31, 28
2	2, 1	17	17, 14	32	32, 30, 29, 23
3	3, 2	18	18, 11	33	33, 20
4	4, 3	19	19, 18, 17, 14	34	34, 31, 30, 26
5	5, 3	20	20, 17	35	35, 33
6	6, 5	21	21, 19	36	36, 25
7	7, 6	22	22, 21	37	37, 36, 33, 31
8	8, 6, 5, 4	23	23, 18	38	38, 36, 33, 31
9	9, 5	24	24, 23, 21, 20	39	39, 35
10	10, 7	25	25, 22	40	40, 37, 36, 35
11	11, 9	26	26, 25, 24, 20	41	41, 38
12	12, 11, 8, 6	27	27, 26, 25, 22	42	42, 39, 38, 35
13	13, 12, 10, 9	28	28, 25	43	43, 41, 40, 36
14	14, 13, 11, 9	29	29, 27	44	44, 42, 41, 37
15	15, 14	30	30, 29, 26, 24	45	45, 44, 43, 41

Stahnke 还计算了 $x^l+x^a+1$ 型本原多项式：$l<45$ 时不存在 4 元（4 个非零项）本原多项式 $x^l+x^b+x^a+1$，但存在 $x^l+x^{a+b}+x^b+x^a+1$ 型，他用后者填补了 $l=8、12、13$ 等处三项式缺失的空位。表 7-8 的 2 抽头和 4 抽头数据是按”抽头指数和 $a+b$ 最大”计算的——后面会看到，这在多步 LFSR 实现中能把复杂度降到最低。

多步 LFSR：如果想一次取 $n$ 位随机位，通常做法是把 LFSR 用时钟驱动 $n$ 次；只取最低 $n$ 位不是好办法——那样随机性弱、安全性低。更好的做法是计算”一次时钟生成 $n$ 个新随机位”的方程组，用 LFSR 的状态空间描述最容易推导。

例 7.2 三同步 LFSR

设本原多项式长度为 6，$p=x^6+x+1$，目标是一个时钟周期内算出 3 个”新”位。先写 LFSR 的状态空间描述 $x(t+1)=Ax(t)$：

$$\left[\begin{array}{l}{x}_6(t+1)\\ x_5(t+1)\\ x_4(t+1)\\ x_3(t+1)\\ x_2(t+1)\\ x_1(t+1)\end{array}\right]=\left[\begin{array}{llllll}0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\\ 1& 1& 0& 0& 0& 0\end{array}\right]\left[\begin{array}{l}{x}_6(t)\\ x_5(t)\\ x_4(t)\\ x_3(t)\\ x_2(t)\\ x_1(t)\end{array}\right]\text{\hspace{1em}(7-21)}$$

要算 $x(t+2)$ 只需 $x(t+2)=Ax(t+1)=A^{2}x(t)$，再迭代得 $x(t+3)=A^{3}x(t)$。$n$ 同步 LFSR 的方程由 $A^n\mathrm{mod}2$ 给出。$n=3$ 时：

$$A^3\mathrm{mod}2=\left[\begin{array}{cccccc}0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\\ 1& 1& 0& 0& 0& 0\\ 0& 1& 1& 0& 1& 0\\ 0& 0& 1& 1& 0& 1\end{array}\right]\text{\hspace{1em}(7-22)}$$

正如所料：寄存器 $x_6\sim x_4$ 只是移 3 位，而 $x_1\sim x_3$ 要用 XNOR 计算出新值。原书 VHDL 改写为 Verilog：

module lfsr6s3 (           // 接口
    input  wire clk,       // 系统时钟
    input  wire reset,     // 异步复位
    output wire [6:1] y    // 系统输出
);
 
    reg [6:1] ff;
 
    always @(posedge clk or posedge reset) begin
        if (reset)                              // 异步清零
            ff <= 6'b000000;
        else begin                              // 三步长度6LFSR（XNOR）
            ff[6] <= ff[3];
            ff[5] <= ff[2];
            ff[4] <= ff[1];
            ff[3] <= ff[5] ~^ ff[6];
            ff[2] <= ff[4] ~^ ff[5];
            ff[1] <= ff[3] ~^ ff[4];
        end
    end
 
    assign y = ff;                              // 连接到输出单元
 
endmodule

图 7-20 给出三同步 LFSR 的仿真结果。与图 7-19 的单步 LFSR 对比可以得出结论：序列每 3 个值出现一次，周期长度从 $2^6-1$ 降为 $(2^6-1)/3=21$。本设计用 6 个 LE，未用嵌入式乘法器，TimeQuest 缓慢 85C 模型下 $F_{max}=931.97\text{MHz}$。

图 7-20 多步 LFSR 仿真结果

实现多步 LFSR 时应选择使电路工作量最小的本原多项式，可通过统计 $A^k\mathrm{mod}2$ 中的非零项数（或寄存器的最大扇入，即每行 1 的个数）来评估。移位步数少时，图 7-18(a) 的电路扇入更有优势；还可以看到，若反馈信号在矩阵 A 中闭合，$A_k$ 中一些项会因模 2 运算变成 0。表 7-8 中的 2 抽头和 4 抽头数据按抽头和最大来选；和相同时选最小抽头值更大者，如 (11, 12) 优于 (10, 13)——因为最大长度 LFSR 必须含抽头 $l$，其他抽头应尽量靠近它。

举个例子：若采用 Stahnke 的 $s_{14,a}(x)=x^{14}+x^{12}+x^{11}+x+1$，$n=8$ 的多步 LFSR 会生成 58 项；而采用表 7-8 的 $p_{14}=x^{14}+x^5+x^3+x+1$（抽头 14、13、11、9），$A^8\mathrm{mod}2$ 矩阵只有 35 项。图 7-21 给出两种多项式（分别用图 7-18 两种结构）的 LFSR 中 1 的总数，图 7-22 给出其最大扇入（即一个 LC 需要的最大输入位宽）。结论：仔细选择多项式和 LFSR 结构可以大幅节省资源；图 7-22 还表明，多步 LFSR 合成时图 7-18(b) 的扇入更小，但对较长的多步 $k$，表 7-8 本原多项式的工作量则旗鼓相当。

图 7-21 A_14^k 中 1 的数量

图 7-22 长度为 14 的多步 LFSR 的最大扇入

组合 LFSR

单个 LFSR 生成的伪随机序列虽然是最大长度的，但它本质上是一个线性系统：只要攻击者拿到 2L 个连续输出位，用 Berlekamp-Massey 算法就能把反馈多项式完整”猜”出来，密钥随即失效。因此实际的数据流密码很少只用一个 LFSR，而是把几个不同长度的 LFSR 并联起来，再用一个非线性函数把它们合并成密钥流——线性结构负责”便宜、快速”，非线性组合负责”抗分析”。

在多种已知的线性和非线性组合方案中，实现代价与安全性的折中比较好的是”带阈值的非线性组合”：三个 LFSR 各输出一位，用多数表决（阈值函数）决定最终输出。对长度分别为 $L_1$、$L_2$、$L_3$ 的三个 LFSR，这种组合的线性复杂度（即：用一个等效的单 LFSR 再现该序列所需的最短寄存器长度，可用 Berlekamp-Massey 算法测出）为：

$$L_{\mathrm{ges}}=L_1\times L_2+L_2\times L_3+L_1\times L_3\text{\hspace{1em}(7-23)}$$

注意这个结果远大于三个长度之和：非线性组合让”等效线性长度”大约乘了一个量级，这正是安全性的来源。图 7-23 给出了这一方案的实现。

图 7-23 使用 3 个 LFSR 的数据流密码的实现

书中选定的分页格式规定密钥为 50 位，因此三个寄存器的总长度取 $2\times 50=100$ 位，反馈多项式选为：

$$p_{33}(x)=x^{33}+x^6+x^4+x+1\text{\hspace{1em}(7-24)}$$ $$p_{29}(x)=x^{29}+x^2+1\text{\hspace{1em}(7-25)}$$ $$p_{38}(x)=x^{38}+x^6+x^5+x+1\text{\hspace{1em}(7-26)}$$

三个多项式都是本原多项式，这保证了每个移位寄存器都能产生最大长度序列（m 序列）。代入式(7-23)算一下线性复杂度：

$$L_1=33,L_2=29,L_3=38$$ $$L_{\mathrm{total}}=33\times 29+33\times 38+29\times 38=957+1254+1102=3313$$

也就是说，花了 100 位寄存器的成本，却换来了等效于 3313 级 LFSR 的线性复杂度——攻击者若想用线性方法破译，需要收集约 $2\times 3313=6626$ 个连续密钥位，这已经超过了多数短报文的长度。

还有一个实际细节：每次编码之后密钥都会丢失（一次性使用），所以还需要额外 50 位寄存器来存储这把密钥，且这 50 个密钥位要被使用两次（一次进 LFSR 初值，一次留作他用）。表 7-9 给出了在 Xilinx Spartan-6 系列 FPGA 上所需的硬件资源（按数量计算）。

表 7-9 Xilinx Spartan-6 系列 FPGA 的成本(按数量计算)

功能组	数量
50位密钥寄存器	6.25
100位移位寄存器	12.5
反馈	0.75
阈值	0.25
与消息 XOR	0.25
总计	20

可以看到整个密码机只花约 20 个单位的资源，其中大部分是移位寄存器本身——这正是 LFSR 类密码”极便宜”的体现。但它安全吗？下面用 DES 做个对照。

基于 DES 的算法

图 7-24 所示的数据加密标准（Data Encryption Standard, DES）是最经典的分组密码：一次加密一整块数据，而不是一位一位地加密。若选择”输出反馈模式”（Output Feedback Mode, OFB），分组密码也可以改造成数据流密码用（参阅图 7-25）——思路是让 DES 反复加密一个初始向量产生密钥流，再把密钥流与明文逐位异或。相反，DES 的其他模式（ECB、CBC、CFB）一般不适合通信系统，原因在于”雪崩效应”：传输中一个比特出错，解密后会导致整个分组中接近一半的比特出错，而流密码的差错只影响出错的那一位。

图 7-24 分组加密系统(DES)的状态机

图 7-25 在 OFB 模式中用作数据流密码的分组密码

图 7-26 Feistel 网络的原理

先复习 DES 的原理。DES 本质上是一个把明文组变成密文组的有限状态机：把待加密的组载入状态寄存器（32 位），先扩展到 48 位，与 48 位的轮密钥组合，然后送入 8 个 6→4 位宽的 S 盒做非线性代替，最后逐位置换。这一轮循环可以重复多次（每轮更换密钥）。DES 中密钥每轮移 1 或 2 位，16 轮之后回到初始位置。由于 DES 可以看作 Feistel 密码（图 7-26）的迭代应用——左右两半交替处理，其中一半只通过可逆方式影响另一半——所以 S 盒本身允许是不可逆的。

直接照搬标准 DES 对 FPGA 并不友好，因此书中做了一些简化改进：把状态寄存器降到 25 位、取消扩展步骤，并采用表 7-10 的末置换。

表 7-10 置换表

开始位	0	1	2	3	4	5	6	7	8	9	10	11	12
到达位	20	4	5	10	15	21	0	6	11	16	22	1	7
开始位	13	14	15	16	17	18	19	20	21	22	23	24
到达位	12	17	23	2	8	13	18	24	3	9	14	19

第二个改进针对 S 盒：大多数 FPGA 的查询表（LUT）只有 4~5 个输入，标准 DES 的 6→4 S 盒无法塞进单个 LUT。表 7-11 给出了专为 5 输入 LUT 设计的 5 个新 S 盒（5→5 位）。

表 7-11 5 个新设计的代替方框(S 盒)

输入	方框1	方框2	方框3	方框4	方框5	输入	方框1	方框2	方框3	方框4	方框5
0	1E	F	14	19	6	10	19	B	1C	17	19
1	13	1	1D	14	E	11	16	1E	A	9	A
2	14	13	16	D	1A	12	7	18	1B	3	4
3	1	1F	B	4	3	13	1C	D	3	10	14
4	1A	19	5	1C	B	14	1D	5	19	A	13
5	1B	1C	E	1A	1E	15	5	14	D	16	11
6	E	12	8	1E	0	16	2	15	0	12	10
7	B	11	F	1	2	17	1F	9	2	1F	12
8	D	8	4	C	1D	18	F	3	15	B	5
9	10	7	C	F	C	19	11	10	6	2	F
A	3	1B	1E	1B	18	1A	C	6	7	6	8
B	0	0	13	1D	17	1B	18	17	12	18	16
C	4	1A	10	5	1	1C	9	4	1F	11	1C
D	6	C	1	15	15	1D	15	16	1A	8	7
E	A	1D	18	E	1B	1E	8	E	9	7	D
F	17	2	17	13	9	1F	12	A	11	0	1F

5 输入 S 盒每个正好占用一个 5 输入 LUT，5 个 S 盒并排一次完成 25 位的代替，硬件代价极低。虽然这套 S 盒本来只是为 OFB 流密码模式设计的，但表 7-12 显示它们是以可逆方式生成的，因此改进后的 DES 也能当作标准的分组密码使用（电子源码书 ECB 模式）。

如何评价一个 S 盒的好坏？常用工具是独立矩阵：它统计”当某些输入位翻转时，每个输入/输出组合的输出位发生翻转的次数”。雪崩效应的理想概率是 1/2。由于每个 5 输入 S 盒有 $2^5=32$ 种可能的输入向量，理想计数值就是 16。表 7-12 给出了 5 个新 S 盒的独立矩阵（绝对次数，理想值为 16）。

表 7-12 5 个代替方框的独立矩阵(理想值是 16)

方框1						方框2
20	12	20	20	20		20	16	20	12	20
12	20	12	16	16		20	20	20	16	16
12	16	16	12	8		12	20	20	16	8
16	16	20	12	16		16	24	12	16	12
20	16	20	12	12		16	20	16	20	20

方框3						方框4						方框5
20	12	16	16	16		20	16	20	20	16		12	20	8	12	20
16	20	16	16	16		12	16	12	16	20		20	12	16	24	20
16	16	20	12	12		20	16	16	20	16		16	12	12	20	16
16	8	12	16	20		20	16	16	20	24		16	20	16	20	12
20	12	12	20	12		16	12	28	20	16		12	16	16	12	24

可以看到多数数值贴近 16，个别偏大的（如方框4 中的 28）来自随机生成 S 盒时还必须满足”可逆”这一约束——完全随机又完全可逆的映射很难处处贴着理想值。表 7-13 总结了这套基于改进 DES 的算法的硬件开销。

表 7-13 基于改进的 DES 的算法的硬件工作量

功能组	数量
25位密钥寄存器	3.125
25位附加位	6.25
25位状态寄存器	3.125
5个S盒5→5	0.75
置换	0
25位初始化向量	3.125
多路复用:初始化向量/S盒	3.125
与消息XOR	0.25
总计	19.75

总量约 19.75，与三 LFSR 方案（20）几乎持平——所以单看成本分不出胜负，得靠安全测试。

加密性能比较

接下来对基于 LFSR 和基于 DES 的两种方案做安全性能比较。安全测试有很多种，这里选两个差异最明显的（其余测试两者表现接近）。两个测试都生成 100 个随机密钥，并使用 64 位明文（参阅图 7-17），明文内容任意：

• 测试 1（雪崩效应）：对每个随机密钥翻转其中一位，加密同一段明文，统计密文中翻转的位数。平均应有约 50% 的位翻转。
• 测试 2（密钥位置敏感性）：与测试 1 类似，但这次统计的是输出密钥流序列中翻转位的数量，它主要取决于密钥发生变化的位置。理想情况下翻转位同样占 50% 左右。

测试 1 的理想累计值是 $64\times 0.5\times 100=3200$；测试 2 中输出序列取 50 位，理想值是 $50\times 0.5\times 100=2500$。图 7-27 和图 7-28 分别给出了结果。

图 7-27 第 1 个测试的结果

图 7-28 第 2 个测试的结果

两个测试都清楚表明：DES-OFB 模式对密钥变化的敏感程度明显高于三 LFSR 模式。测试 2 的结果尤其说明问题：LFSR（移位寄存器 SR）模式下，密钥位的变化大约要经过 32 步移位才会影响到输出序列——中间存在一段”盲区”；而 DES-OFB 模式只有最初 4 个样本与理想值 2500 有明显差别，之后立刻贴住理想值。鉴于良好的测试结果，优先选择 DES-OFB 模式而不是 LFSR 模式。

加密安全的注意事项

要断言”某个加密系统是安全的”其实非常困难。除了密钥可能被窃取之外，你永远无法证明”快速解密算法不存在”。此外，攻击未必针对算法本身：近年来出现的差分能量攻击通过测量电路的功耗泄露来寻找实现上的薄弱环节${}^{[238]}$。还有利用强大计算机进行的”蛮力攻击”和并行攻击。

56 位密钥的 DES 就是前车之鉴。它多年被当作标准，但 1997 年最终被宣布不再安全：最先由 Internet 上一批志愿计算机机主组成的网络用 39 天破译了密钥；随后电子前沿基金会（EFF）完成了专用破译计算机的设计，全部图纸和软件源代码已汇集成书${}^{[239]}$，可从 http://www.eff.org 下载。这台机器执行穷举密钥搜索，破译任何 56 位密钥用时不到 5 天。它全部由定制芯片构成，每块芯片含 24 个破译单元，29 块开发板每块装 64 片”深度破译（Deep Crack）“芯片——总计 1856 块芯片、44544 个单元，系统造价 25 万美元。作为对比：DES 在 1977 年推出时，同等算力的造价估计是 2000 万美元（相当于今天的 4000 万美元）。这是摩尔定律（每 18 个月处理器规模或速度翻倍、价格减半）的绝佳注脚：从 1977 到 1998 年共经历约 22 个半年周期，价格应降到 $40\times 10^6/2^{22/1.5}\approx 1500$ 美元——也就是说，如今用一台普通工作站级别的预算就能造出一台 DES 破译器，这一点已被 EFF 证实。

所以 56 位 DES 已不再安全，但现在通常采用三重 DES（图 7-29，即用不同密钥串接加密-解密-加密）或 128 位密钥系统。表 7-14 表明这些系统今后几年仍是安全的：例如 EFF 破译器破译三重 DES 大约需要 $5\times 2^{112}$ 天，即 $7\times 10^{31}$ 年。

图 7-29 三重DES（$K_l$=密钥；E=单个加密；D=单个解密）

表 7-14 加密算法${}^{[240]}$

算法	密钥长度(位)	数学操作/原理	对称性	开发者(年)
DES	56	XOR、固定S盒	s	IBM(1977)
三重 DES	112~168	XOR、固定S盒	s	不详
AES	128~256	XOR、固定S盒	s	Daemen/Rijmen(1998)
RSA	可变	质因数	a	Rivest/Shamir/Adleman(1977)
IDEA	128	XOR、加、乘	s	Massey/Lai(1991)
Blowfish	<448	XOR、加、固定S盒	s	Schneider(1993)
RC5	<2048	XOR、加、旋转	s	Rivest(1994)
CAST-128	40~128	XOR、旋转、S盒	s	Adams/Tavares(1997)

表中第一列是通用加密算法的缩写，第二、三列是典型参数。对称算法（第 4 列标 s）通常基于 Feistel 结构，加解密用同一把密钥；非对称算法（标 a，如 RSA）用于公钥/私钥体系。最后一列是开发者与首次公布年份。

7.2 调制和解调

长期以来，通信系统设计者的梦想是全数字接收器：一根天线加一块完全可编程电路，数字滤波、纠错解调/译码乃至加密全部在单片可编程芯片上完成。今天 FPGA 的门数已超过 100 万，全数字接收器成为现实。正像 Carter 预言的：“很显然，FPGA 将会是通信系统进入 21 世纪的关键技术”${}^{[214]}$。本节开发用 FPGA 设计和实现的通信系统。

7.2.1 基本的调制概念

最基本的通信系统在载波频率 $f_0$ 上收发信息。载波可以用幅值、频率或相位三种方式携带信息信号 $x(t)$。图 7-30 给出了二进制传输的三种调制波形：分别称为幅移键控（Amplitude Shift Keying, ASK）、相移键控（Phase Shift Keying, PSK）和频移键控（Frequency Shift Keying, FSK）。

图 7-30 ASK、PSK 和 FSK 调制

分析调制信号时，“旋转箭头”比时域波形更有效：把已调信号想象成复平面中一个长度和角度随时间变化的旋转矢量，实信号就是这个矢量在实轴上的投影：

$$s(t)=\Re \left\{A(t)e^{j\left(2\pi f_{0}t+\Delta \varphi (t)+{\varphi }_0\right)}\right\}=A(t)\cos \left(2\pi f_{0}t+\Delta \varphi (t)+{\varphi }_0\right)\text{\hspace{1em}(7-27)}$$

其中 ${\varphi }_0$ 是（随机的）初始相位偏移，$A(t)$ 是幅值包络，$\Delta \varphi (t)$ 是频率/相位调制分量，如图 7-31 所示。从式(7-27)还能得出一个重要结论：AM 分量（乘在矢量长度上）和 PM/FM 分量（加在角度上）在数学上是相互独立的，可以同时用来传输两路不同的信号。

图 7-31a 调制信号在复平面中的旋转矢量表示

图 7-31 复平面中的调制

图 7-31c 幅值包络 $A(t)$ 与相位/频率分量 $\Delta \varphi (t)$ 的分解示意

实现通用调制器（AM+PM+FM 一体）的高效方案是不需要大规模查找表的 CORDIC 算法（第 2 章已介绍）。让它工作在旋转模式——即作为 $(R,\theta )\to (X,Y)$ 的坐标变换器——就得到图 7-32 的完整调制器。

图 7-32 采用 CORDIC 的通用调制器

三个输入各自对应一种调制：

• AM：信号 $A(t)$ 直接接到 CORDIC 的半径 $R$ 输入。旋转模式的 CORDIC 输出半径会线性增大（增益因子 1.6468，参阅表 2-1），这相当于放大器的增益变化，对 AM 方案本身通常无需处理；若不希望有这个放大，可用比例 $1/1.6468$ 的常系数乘法器对输入或输出做缩放。
• FM：需要恒定载波 $2\pi f_{0}t$，可用一个相位累加器生成线性递增的相位；要叠加 FM 时，用 $\Delta f$ 修改 $f_0$，或再增加一个累加器计算 $2\pi \Delta ft$，两个累加器结果相加。
• PM：在相位上叠加一个不随时间增长的常数偏移。

所有相位分量求和后送入 CORDIC 的角度输入 $z$（或 $\theta$），Y 寄存器迭代初值置 0。下面的示例给出了完整的流水线实现。

例 7.3 采用 CORDIC 的通用调制器

根据图 7-32，AM、PM 和 FM 信号的通用调制器可用如下 Verilog HDL 设计（原书 VHDL 改写为 Verilog）。设计采用 4 级流水线，各级分别完成 90°、45°、26°、14° 的微旋转；45°、26°、14° 旋转中的乘 $\tan 45°=1$、$\tan 26.6°\approx 0.5$、$\tan 14°\approx 0.25$ 分别用直通、右移 1 位、右移 2 位实现，因此不需要任何乘法器：

// 原书 VHDL 改写为 Verilog：4 级流水线 CORDIC 通用调制器
module ammod (
    input  wire               clk,      // 系统时钟
    input  wire               reset,    // 异步复位
    input  wire signed [8:0]  r_in,     // 半径(幅度)输入, S9: -256..255
    input  wire signed [8:0]  phi_in,   // 相位输入
    output reg  signed [8:0]  x_out,    // x / 实部输出
    output reg  signed [8:0]  y_out,    // y / 虚部输出
    output reg  signed [8:0]  eps       // 残余相位误差
);
    // 4 级流水线的寄存器阵列(对应原书的 A0_3S9 数组)
    reg signed [8:0] x [0:3];
    reg signed [8:0] y [0:3];
    reg signed [8:0] z [0:3];
 
    always @(posedge clk or posedge reset) begin
        if (reset) begin
            x_out <= 0; y_out <= 0; eps <= 0;
            x[0] <= 0; y[0] <= 0; z[0] <= 0;
            x[1] <= 0; y[1] <= 0; z[1] <= 0;
            x[2] <= 0; y[2] <= 0; z[2] <= 0;
            x[3] <= 0; y[3] <= 0; z[3] <= 0;
        end else begin
            // 先输出上一拍的结果(4 拍流水线延迟)
            x_out <= x[3];
            eps   <= z[3];
            y_out <= y[3];
 
            // 第 4 级：旋转 14 度 (tan14° ≈ 1/4)
            if (z[2] >= 0) begin
                x[3] <= x[2] - (y[2] >>> 2);
                y[3] <= y[2] + (x[2] >>> 2);
                z[3] <= z[2] - 14;
            end else begin
                x[3] <= x[2] + (y[2] >>> 2);
                y[3] <= y[2] - (x[2] >>> 2);
                z[3] <= z[2] + 14;
            end
 
            // 第 3 级：旋转 26 度 (tan26.6° ≈ 1/2)
            if (z[1] >= 0) begin
                x[2] <= x[1] - (y[1] >>> 1);
                y[2] <= y[1] + (x[1] >>> 1);
                z[2] <= z[1] - 26;
            end else begin
                x[2] <= x[1] + (y[1] >>> 1);
                y[2] <= y[1] - (x[1] >>> 1);
                z[2] <= z[1] + 26;
            end
 
            // 第 2 级：旋转 45 度 (tan45° = 1)
            if (z[0] >= 0) begin
                x[1] <= x[0] - y[0];
                y[1] <= y[0] + x[0];
                z[1] <= z[0] - 45;
            end else begin
                x[1] <= x[0] + y[0];
                y[1] <= y[0] - x[0];
                z[1] <= z[0] + 45;
            end
 
            // 第 1 级：处理 |phi_in| > 90 的情形(旋转 90 度)
            if (phi_in > 90) begin
                x[0] <= 0;
                y[0] <= r_in;
                z[0] <= phi_in - 90;
            end else if (phi_in < -90) begin
                x[0] <= 0;
                y[0] <= -r_in;
                z[0] <= phi_in + 90;
            end else begin
                x[0] <= r_in;
                y[0] <= 0;
                z[0] <= phi_in;
            end
        end
    end
endmodule

图 7-33 给出了 AM 信号的仿真结果。注意 Altera 仿真工具允许直接用有符号数据显示（若用无符号二进制表示，负值会带 512 的偏移量）。可以看到 4 个步骤的流水线延迟；输入半径 100 被约 1.6 的 CORDIC 增益放大；半径 r_in 从 100 切换到 25 时，输出最大值 x_out 相应从 163 降到 42，验证了 AM 调制功能。时序方面，采用 TimeQuest 缓慢 85C 模型时该 CORDIC 调制器的 $F_{max}=197.39\mathrm{MHz}$，使用 264 个 LE，没有使用嵌入式乘法器。

图 7-33 采用 CORDIC 算法的 AM 调制器的仿真结果

解调分为相干与非相干两类：相干接收器必须复现未知的载波相位 ${\varphi }_0$，非相干接收器则不用。若接收器使用中频（Intermediate Frequency, IF）频带，称为超外差接收器；使用两个 IF 频带的称双变频超外差接收器，IF 接收器也常被称作外差接收器；完全不使用 IF 级的则是零 IF（零差）接收器。图 7-34 给出了各种接收器的系统性综述：有的只支持一种调制方式，能同时处理 AM、PM、FM 的称为通用接收器。下面先讨论非相干接收器，再讨论相干接收器。

图 7-34 相干和非相干解调方案

无论哪种接收器，都要用集约型滤波器（第 3、4 章讨论过）选出有用的信号分量。外差接收器还要额外抑制镜像频率——它来源于频移（混频）过程：时域相乘对应频域搬移，正负两个频率位置都会出现副本：

$$s(t)\times \cos (2\pi f_{m}t)\leftrightarrow S(f+f_m)+S(f-f_m)\text{\hspace{1em}(7-28)}$$

7.2.2 非相干解调

非相干方案中，假定接收器已知载波频率，但初始相位 ${\varphi }_0$ 未知。

这里有个选择问题：只需解调某一种模式（如 AM 或 FM），还是要通用解调？非相干 AM 解调不过是一个全波或半波检波器加一个低通滤波器；对 AM 或 FM，限幅器/鉴频器型解调器是高效实现——它先把输入信号限幅到 $\pm 1$，再测量两个过零点之间的距离来还原频率。这类接收器用 FPGA 很容易实现，但相位信号中经常出现 $2\pi$ 的跳变（所谓”咯呖声（clicks）”${}^{[2426,2437]}$），性能也有限。

我们的重点是采用同相/正交（I/Q）分量的通用接收器：它把式(7-27)的调制过程”倒过来”做。第一步，从接收到的余弦信号中分离出与发送端正弦分量正交的 $Q$ 相以及同相的 $I$ 相，用 $I$、$Q$ 两路重构复平面中随载波旋转的箭头。此时整个处理恰好是图 7-32 电路的逆过程：让 CORDIC 工作在向量模式，做 $X,Y\to R,\theta$ 的坐标变换（$I=X$，$Q=Y$），输出 $R$ 正比于 AM 分量，PM/FM 分量则由 $\theta$（即 Z 寄存器）重构。

难点在于 I/Q 的生成，通常有两种方法：正交方案和希尔伯特变换。

正交方案中，输入信号与两个本地振荡信号 $2\cos (2\pi f_{\mathrm{m}}t)$ 和 $-j2\sin (2\pi f_{\mathrm{m}}t)$ 相乘，再用滤波器选出 IF 频带 $f_{\mathrm{IF}}=f_0-f_{\mathrm{m}}$ 内的信号，两路信号的复数和就是复平面上旋转箭头的重构。图 7-35 给出了方案框图，图 7-36 是 I/Q 生成过程的频谱示例——注意最终信号已经没有负频谱分量，这正是非相干接收器的典型特征，这样的信号被称为分析信号。

图 7-35 采用正交方案的 $I/Q$ 相的生成

图 7-36 $I/Q$ 相生成的频谱示例

为了减少滤波器工作量，IF 频率最好选得接近零。模拟方案里（尤其对 AM）这会带来放大器漂移进饱和区的新问题，但全数字接收器可以放心地构造零中频（零 IF）接收器：带通滤波器随之简化为低通滤波器，而高抽取率低通滤波器的高效实现正是第 5 章介绍的 Hogenauer CIC 滤波器。图 7-37 给出了相应频谱：实输入信号以 $2\pi$ 的采样频率采样，分别与余弦信号 $S_{2\cos }(e^{j\omega })$ 和正弦信号 $S_{-j2\sin }(e^{j\omega })$ 相乘，得到同相分量 $S_1(e^{j\omega })$ 和正交分量 $j{S}_Q(e^{j\omega })$；两者组合成复分析信号 $S_1+j{S}_Q$；最后的低通滤波之后做一次抽取，降低采样率。

图 7-37 零 IF 接收器的频谱，采样频率是 $2\pi$

这样，就用 FPGA 技术构造了一个 LF 频段的全数字零 IF 接收器${}^{[244]}$。

例 7.4 零 IF 接收器

该接收器由天线、可编程增益调节器（AGC）、一个 7 阶 Cauer 低通滤波器和其后级的 8 位音频 A/D 转换器组成。对 50 kHz150 kHz 的输入信号采用 8 倍过采样（对应采样率 0.4 MHz1.2 MHz）。正交乘法器采用 8 位×8 位阵列乘法器。两级 CIC 滤波器的积分器精度分别为 24 位和 19 位，梳状部分精度分别为 17 位和 16 位。最终抽取比降到 64。整个设计可放置在 Atlys 板上的 Xilinx Spartan-6 FPGA 中。表 7-15 给出了单个单元的工作量。

表 7-15 单个单元的工作量

设计部分	数量
带有sin/cos表的混频器	18.5
两个CIC滤波器	42
状态机和PDSP接口	4.5
频率合成器	8
总计	73

其中可调频率合成器的累加器还可以用作模拟锁相环（PLL）的参考${}^{[4]}$。图 7-38 给出了这种频率合成器的结构，图 7-39 显示了实测性能。累加器合成器可以跑很高的时钟频率，因为加法器只需要输出溢出位，所以采用逐位进位保存加法器（carry-save adder）即可。以累加器为参考的 PLL 能生成：

$$F_{\mathrm{out}}=M_2{F}_{\mathrm{in}}^{\prime }=\frac{M_1{M}_2{F}_{\mathrm{in}}}{2^N}$$

图 7-38 以累加器为参照的 PLL

HP 5371A Frequency And Time Interval Analyzer

图 7-39(a) $F_{\mathrm{out}}$ 从 $900\mathrm{kHz}$ 切换到 $1.2\mathrm{MHz}$ 时合成器的运行状态

HP 5371A Frequency And Time Interval Analyzer

图 7-39(b) 频率误差的柱状图(小于 2Hz)

希尔伯特变换器方案

另一种 I/Q 生成方法的事实依据是：正弦信号可以由余弦信号相位延迟 90° 得到。如果用滤波器实现这个 90° 移相（即希尔伯特变换器，图 7-40），则要求滤波器对所有频率的幅度响应恒为 1、相位恒为 90°。由傅里叶变换的定义可得其脉冲响应与传递函数：

$$h(t)=\frac{1}{\pi t}\leftrightarrow H(j\omega )=-j\gamma (\omega )=\{\begin{array}{ll}j& -\infty <\omega <0\\ -j& 0<\omega <\infty \end{array}\text{\hspace{1em}(7-29)}$$

其中符号函数 $\gamma (\omega )=-1(\forall \omega <0)$，$\gamma (\omega )=1(\forall \omega ⩾0)$。注意 $h(t)=1/(\pi t)$ 是无限长且非因果的，所以希尔伯特滤波器只能用 FIR 滤波器近似，具体系数可参阅文献[186, 245, 246]或[88]。

图 7-40 希尔伯特变换器

窄带接收器的简化

如果输入是窄带信号——传输的位速率远小于载波频率——解调方案还能进一步简化。在输入采样方案中，可以按载波速率或其周期 $T_0=1/f_0$ 的整数倍采样，这样采样值与载波分量完全无关。

若零 IF 接收器以 $4f_0$ 的速率采样，正交方案就不再必要了：此时正弦/余弦分量的取值只有 0、1 或 -1，载波相位只有 0、90°、180° 等，这被称为”复采样”${}^{[247,248]}$。还可以采用欠采样——采样器每两三个载波周期才取一次样——采样信号仍然与载波频率无关。

如果信号以 $T_0/4$ 的速率采样，希尔伯特变换器也能简化：可采用 $Q_{-1}=1$ 的一阶希尔伯特采样器，或采用对称系数 $Q_1=-0.5$、$Q_{-1}=0.5$，以及非对称系数 $Q_{-1}=1.5$、$Q_{-3}=0.5$ 的二阶希尔伯特采样器${}^{[249]}$。表 7-16 给出了三种短项希尔伯特变换器的系数以及允许的最大频率偏移 $\Delta f$（相对精度）。

表 7-16 希尔伯特采样器的系数

类型	系数	位	$\Delta f/f_0$
零阶	$Q_{-1}=1.0$	8	0.005069
零阶	$Q_{-1}=1.0$	12	0.000320
零阶	$Q_{-1}=1.0$	16	0.000020
一阶非对称	$Q_{-1}=1.5;Q_{-3}=0.5$	8	0.032805
一阶非对称	$Q_{-1}=1.5;Q_{-3}=0.5$	12	0.008238
一阶非对称	$Q_{-1}=1.5;Q_{-3}=0.5$	16	0.002069
一阶对称	$Q_1=-0.5;Q_{-1}=0.5$	8	0.056825
一阶对称	$Q_1=-0.5;Q_{-1}=0.5$	12	0.014269
一阶对称	$Q_1=-0.5;Q_{-1}=0.5$	16	0.003584

可以看出：系数越多、量化位数越高，允许的频偏/载波比就越大。图 7-41 展示了解调无线电控制监视器信号时一阶希尔伯特采样器的两种实现${}^{[250,251]}$：第一种用 3 个采样-保持电路，第二种用 3 个 A/D 转换器。

图 7-41(a) 一阶希尔伯特采样器的第一种实现方式

图 7-41(b) 一阶希尔伯特采样器的第二种实现方式

图 7-42 给出了按 1/2 直接欠采样的希尔伯特采样器的频谱特性。

图 7-42 欠采样的希尔伯特采样器的频谱

7.2.3 相干解调

如果接收端已知相位 ${\varphi }_0$，解调就简化为乘法加低通滤波。做法是：AM 信号乘以 $2\cos ({\omega }_{0}t+{\varphi }_0)$；PM 或 FM 信号乘以 $-2\sin ({\omega }_{0}t+{\varphi }_0)$。利用积化和差，两倍频项被低通滤除后剩下基带项：

AM：

$$A(t)\cos (2\pi f_{0}t+{\varphi }_0)\times 2\cos (2\pi f_{0}t+{\varphi }_0)=\underset{\text{低通分量}}{\underbrace{A(t)}}+A(t)\cos (4\pi f_{0}t+2{\varphi }_0)\text{\hspace{1em}(7-30)}$$ $$s_{\mathrm{AM}}(t)=A(t)-A_0\text{\hspace{1em}(7-31)}$$

PM：

$$-2\sin (2\pi f_{0}t+{\varphi }_0)\times \cos (2\pi f_{0}t+{\varphi }_0+\Delta \varphi (t))=\underset{\text{低通分量}}{\underbrace{\sin (\Delta \varphi (t))}}+\cos (4\pi f_{0}t+2{\varphi }_0+\Delta \varphi (t))\text{\hspace{1em}(7-32)}$$

当相位偏差较小时：

$$\sin (\Delta \varphi (t))\approx \Delta \varphi (t)\text{\hspace{1em}(7-33)}$$ $$s_{\mathrm{PM}}(t)=\frac{1}{\eta }\Delta \varphi (t)\text{\hspace{1em}(7-34)}$$

FM： 对相位求导即得频率：

$$s_{\mathrm{FM}}(t)=\frac{1}{\eta }\frac{d\Delta \varphi (t)}{dt}\text{\hspace{1em}(7-35)}$$

其中 $\eta$ 称为调制指数。

适合 FPGA 实现的相干接收器，其信噪比通常比非相干接收器好 1 dB 以上（参阅图 7-1）。同步（相干）FM 接收器用一个环路中的压控振荡器（Voltage-Controlled Oscillator, VCO）跟踪输入信号的载波相位；VCO 控制电压的直流（DC）分量正比于 FM 信号。PM 解调需要对 VCO 控制信号积分，AM 解调则需要另一个混频器与一个带低通滤波的 $\pi /2$ 移相器相加。相干解调的风险是：在低信噪比信道中环路可能失锁，性能会急剧下降。

通用相干接收环有两种：锁相环（Phase-Locked Loop, PLL）和边环/科斯塔斯环（Costas Loop, CL），框图见图 7-43 与图 7-44。可以看出 CL 的复杂度几乎是 PLL 的两倍（要用 3 个相位检测器和 3 个低通滤波器）。每种环都可用模拟电路（线性 PLL/CL）或全数字电路（ADPLL/ADCL）实现（参阅文献[252255]）；环的稳定性分析超出本书范围，可参阅文献[256260]。下面讨论 PLL 和 CL 的高效实现${}^{[261,262]}$，第一种就是把模拟 PLL 直接映射到 FPGA 技术。

图 7-43 锁相环(PLL)和(必需的)带通滤波器 $h_{\mathrm{BP}}(t)$、相位检测器(PD)、低通滤波器 $h_{\mathrm{LP}}(t)$ 和压控振荡器(VCO)

图 7-44 边环(CL)和(必需的)带通滤波器 $h_{\mathrm{BP}}(t)$、3 个相位检测器(PD)、3 个低通滤波器 $h_{\mathrm{LP}}(t)$ 和带 $\pi /2$ 移相器的压控振荡器(VCO)

线性锁相环

“线性环”与”数字环”的区别在于输入信号类型：线性 PLL/CL 用快速乘法器做相位检测器，可以处理多电平输入信号；数字 PLL/CL 只能处理二进制输入信号（这里的”数字”指输入信号的品质，不是硬件实现方式）。

如图 7-43 所示，线性 PLL 有 3 个主要模块：

• 作为相位检测器的乘法器
• 环路滤波器
• VCO

要保证环不失锁，环路输出信噪比必须大于 4 dB 且不大于 6 dB${}^{[255]}$。通常天线的选择难以窄到这个程度，因此要在图 7-43 和图 7-44 中额外加一个窄带带通滤波器${}^{[262]}$。“级联带通梳状（Cascaded Bandpass Comb）“滤波器（参阅表 5-6）就是一个有效示例；不过若采用固定 IF（如超外差或双变频超外差接收器），这个滤波器的设计会简单得多。

VCO（ADPLL 中对应数控振荡器 DCO）的振荡频率为 ${\omega }_2={\omega }_0+K_0\times U_f(t)$，其中 ${\omega }_0$ 是静止点，$K_0$ 是 VCO/DCO 增益。对正弦输入信号，低通滤波器输出：

$$u_{\mathrm{dem}}(t)=K_d\sin (\Delta \varphi (t))\text{\hspace{1em}(7-36)}$$

其中 $\Delta \varphi (t)$ 是 DCO 输出与带通滤波器输入信号之间的相位差。相差较小时 $\sin$ 可用自变量近似，于是 $u_{\mathrm{dem}}(t)\propto \Delta \varphi (t)$，环保持锁定。若输入信号相位发生突变，环就会失锁。图 7-45 给出了环的不同运行区域：约束范围 ${\omega }_0\pm \Delta {\omega }_H$ 是静态运行界限（只对频率合成器有意义）；锁定范围是 PLL 能在频率差 ${\omega }_1-{\omega }_2$ 的单个周期内锁定的区域；捕捉范围内环会在捕捉时间 $T_L$ 内完成锁定，$T_L$ 可以超过 ${\omega }_1-{\omega }_2$ 的一个周期；失锁范围是环在不失锁前提下能承受的最大频率跳变；${\omega }_0\pm \Delta {\omega }_{PO}$ 则是调制中使用的动态运行界限。关于 PD、环路滤波器和 VCO 增益的优化还有很多文献，参阅[256~260]。

图 7-45(a) 环路运行区域的定义示意

图 7-45 两个对应的运行区域

线性环的优点是噪声抑制能力好，但缺点同样明显：用作 PD 的快速乘法器硬件成本高，而且这种 PD 在 $\pi /2$ 相移处存在一个不稳定的静止点（$-\pi /2$ 才是稳定点），会妨碍锁定。表 7-17 估算了线性 PLL 通用解调器的硬件成本（与例 7.4 的 8 位非相干接收器采用相同功能模块，按数量计算）。若在 AM 和 PM 调制复用中采用硬件乘法器，右列电路成本可降低 58 个 CLB（约 14.5 片 Spartan-6），从而放进最小的 Spartan-6 器件。

表 7-17 Xilinx Spartan-6 FPGA 中线性 PLL 通用解调器的成本(按数量计算)

功能模块	仅有FM	FM、AM和PM
相位检测器(8位×8位乘法器)	16.25	18
环路滤波器(两级CIC)	21	42
频率合成器	8.5	8.5
DCO(N/N+K个除法器,sin/cos表)	4	4.5
PDSP接口	3.75	3.75
总计	53.5	76.75

与非相干接收器对比：不用 CORDIC 解调的相干接收器共用 292 个 CLB（约 73 片 Spartan-6），若再配一个额外 CORDIC 处理器则需 367.5 个 CLB（约 91.875 片 Spartan-6）${}^{[77]}$——线性 PLL 只带来有限的改进。如果只需要 FM 和 PM 解调，下面讨论的数字 PLL 或 CL 能显著降低复杂度。

这些设计都是为了解调气象传真图片而开发的，图片由欧洲中部的低频无线电台 DCF37 和 DCF54（载波 117.4 kHz 和 134.2 kHz；频率调制 F1C：±150 Hz）播发。

数字锁相环

如上所述，数字 PLL 处理二进制输入信号，相位检测器比快速乘法器简单得多，通常选 XOR 门、边沿触发的 J-K 触发器，或带少量附加门的成对 RS 触发器${}^{[255]}$。图 7-46 的相位检测器虽然最复杂，但它同时具备相位和频率灵敏度，并具有近似无限的约束范围。

图 7-46 相位检测器${}^{[22]}$

DPLL 的环路滤波器可以用改进的计数器实现：可以是 $N/(N+K)$ 型计数器，或多级计数器（如 N/M 除法器），分别设 UP 和 DOWN 计数器，第三个计数器统计两者之差；若差值不超过某个阈值，就可以中断后续信号处理。DCO 则可以使用任何典型的全数字频率合成器——累加器、除法器或乘法生成器都行；最常用的是可调除法器，因为它相位误差最小，而其低分辨率可以通过降低接收器 IF 来弥补${}^{[263]}$。

一种非常简单的 DPLL 是采用”脉冲窃取（pulse stealing）“设计的 74LS297 电路。用相位和频率都敏感的 J-K 触发器可以改进该方案，如图 7-47 所示。其工作原理：“检测触发器”的静止频率满足

$$F_{\mathrm{comp}}=\frac{F_{\mathrm{in}}}{N}=\frac{F_{\mathrm{osc}}}{KM}\text{\hspace{1em}(7-37)}$$

图 7-47 “脉冲窃取” PLL${}^{[264]}$

为了能跟踪高于静止频率的输入频率，振荡器频率 $F_{\mathrm{osc}+}$ 要设置得略高一些：

$$T_{\mathrm{comp}}-T_{\mathrm{comp}+}=\frac{1}{2}{T}_{\mathrm{osc}}\text{\hspace{1em}(7-38)}$$

这样 B 点信号比 $F_{osc}$ 快半个周期。大约在静止频率两个周期之后，检测器触发器内必然锁存一个 1；该信号经抗尖峰干扰触发器和延迟触发器，去抑制”÷K”除法器的一个脉冲——这就是”脉冲窃取”名称的由来。窃走一个脉冲后 B 处信号被延迟，A 处信号的相位便跑到 B 处之后，如此循环往复，环始终被拉回锁定。PLL 锁定范围有一个下边界 $F_{in}{|}_{min}=0\mathrm{Hz}$，上边界取决于最大输出频率 $F_{osc}/K$，于是锁定范围为：

$$\pm △{\omega }_L=\pm N\times F_{\mathrm{osc}+}/(K\times M)\text{\hspace{1em}(7-39)}$$

接收器还可以通过省略计数器 N 和 M 进一步简化。在气象传真图像译码应用中，双变频超外差接收器的第二个 IF 设置为：300 Hz 的频率调制（$\delta f=0\mathrm{Hz}\to$ 白色；$\delta f=300\mathrm{Hz}\to$ 黑色）精确对应 32 个窃取脉冲，于是窃取脉冲数与灰度级直接对应。设计取 1920 波特的像素率和 16.6 kHz 的 IF；每个像素确定 4 个”窃取值”（一个时间间隔内的窃取脉冲数量），总计移位 ${\log }_2(2\times 4)=3$ 位即可计算 16 个灰度级的值。表 7-18 给出了这种 PLL 类型的硬件复杂性。

表 7-18 脉冲窃取 DPLL 的硬件复杂性(4 个 CLB≈1 片 Spartan-6)${}^{[263]}$

功能组	CLB
DCO	4
相位检测器	1.25
环路滤波器	1.5
求平均值	2.75
PC接口	2.5
频率合成器	6.5
状态机	2.5
总计	21

对比表 7-17 可以看出：把输入限幅成二进制后，相位检测器和环路滤波器的成本几乎降了一个数量级，整个数字 PLL 仅约 21 个 CLB——这正是”牺牲多电平信息换取硬件简洁”的典型权衡。

3. 边环（Costas loop）

3.1 它是什么：为”没有载波的信号”找回载波

在通信系统中，有一大类调制方式（如抑制载波的双边带调制 DSB-SC、PSK 数字调制等）会把载波本身”藏起来”——发射信号中不含离散的载波分量。此时接收端如果还想用普通锁相环（PLL）去锁定载波，就会发现鉴相器拿不到可以比较的载波参考，环路根本无法入锁。

1956 年，John P. Costas 提出了一种巧妙的改进结构，后来被称为边环（Costas loop，简称 CL），专门用于这类信号的载波恢复。它的核心思想是：既然载波被抑制了，那就先把它”假装”解调出来——用本地振荡器产生两路正交的本振信号，分别与输入信号相乘，得到同相（I）路和正交（Q）路；再把这两路结果相乘，乘积的极性恰好能反映出本地载波与真实载波之间的相位误差方向。用这个误差去控制本地振荡器，环路就能把本地载波”拉”到与信号载波对齐的位置上。

与 PLL 相比，边环多了 $\pi /2$ 移相器、第三个鉴相器（PD）以及配套的低通滤波器，复杂度大约是 PLL 的两倍；但换来的是：对信号的锁定速度也快了约两倍。这笔”用面积换速度”的交易在工程上通常是划算的。

边环还有一个鲜明的工程特点：它对同相支路和正交支路增益的微小失配非常敏感——模拟电路里两个通道的增益很难做到完全一致，失配会直接污染误差信号。因此边环总是应该采用全数字电路实现：数字乘法器、数字滤波器的增益可以精确到位，从根上消除模拟失配问题。FPGA 正是实现这类全数字环路（全数字锁相环/全数字 Costas 环）的理想工具。

3.2 数学原理：I、Q 两路如何”合成”出误差信号

设输入信号为

$$U(t)=A(t)\sin ({\omega }_{0}t+\Delta \varphi (t))$$

其中 $A(t)$ 是幅度（对载波恢复而言可视为缓变的包络），$\Delta \varphi (t)$ 是本地载波与信号载波之间的相位误差——它正是环路要消灭的对象。

在边环内部，本地振荡器给出同相、正交两路参考，分别与 $U(t)$ 相乘（混频），再各自经过低通滤波器滤除二倍频分量。混频乘积中的高频项 $\cos (2{\omega }_{0}t+\cdots )$ 被低通滤掉后，剩下的是”慢变”的两路输出：

$$U_I(t)=K_{d}A(t)\cos (\Delta \varphi (t))\text{\hspace{1em}(7-40)}$$ $$U_Q(t)=K_{d}A(t)\sin (\Delta \varphi (t))\text{\hspace{1em}(7-41)}$$

其中 $2K_d$ 是鉴相器的增益。可以直观地理解这两式：当相位误差 $\Delta \varphi$ 趋近 0 时，$U_I$ 最大、$U_Q$ 趋近 0——能量全部集中在同相支路；误差越大，能量就越多地”泄漏”到正交支路。所以 $U_Q$ 与 $U_I$ 的比值本质上就是 $\tan (\Delta \varphi )$，误差信息全部藏在这两路信号的相对大小之中。

接下来是 Costas 结构的点睛之笔：把 $U_I(t)$ 与 $U_Q(t)$ 送入第三个鉴相器直接相乘，再经低通滤波，得到 DCO 的控制信号：

$$U_{I\times Q}(t)\sim K_d\sin (2△\varphi (t))\text{\hspace{1em}(7-42)}$$

这是因为

$$U_I\cdot U_Q=K_d^2{A}^2(t)\cos (\Delta \varphi )\sin (\Delta \varphi )=\frac{K_d^2{A}^2(t)}{2}\sin (2\Delta \varphi ),$$

低通去掉包络的缓变部分后，就得到正比于 $\sin (2\Delta \varphi )$ 的误差项。

与 PLL 的比较：PLL 的鉴相特性在小误差时近似为 $K_d\sin (\Delta \varphi )$（见原书式 7-36），而边环是 $K_d\sin (2\Delta \varphi )$。当 $\Delta \varphi$ 很小时，$\sin (2\Delta \varphi )\approx 2\Delta \varphi$，也就是说在同样的相位误差下，边环输出的控制电压是 PLL 的两倍——误差信号斜率翻倍，等效环路增益翻倍，环路自然锁得更快。

一个数值示例：设相位误差 $\Delta \varphi =5°$。PLL 给出的误差信号约为 $K_d\sin 5°=K_d\times 0.0872$；而边环给出 $K_d\sin 10°=K_d\times 0.1736$，正好约两倍。误差更”响亮”，环路纠正得更果断。

需要提醒初学者的是：$\sin (2\Delta \varphi )$ 在 $\Delta \varphi =0$ 和 $\Delta \varphi =\pi$ 处斜率都为正，二者都是稳定锁定点，因此边环存在 180° 相位模糊——环能锁定，但锁上的相位可能与真实载波相差 $\pi$。这正是实际通信系统还要配合差分编码等手段解决相位模糊的原因。

与 PLL 中一样，如果环路只承担 FM 或 PM 信号的解调（不追求精确的绝对相位），鉴相器完全可以做成全数字的，这也是下一节全数字实现的基础。

3.3 一个完整实例：气象传真接收机中的全数字边环

图 7-48 给出了一个实际工程中使用的全数字边环框图，它服务于气象传真图片的接收——传真是靠”一行行像素”传输的图片信号，像素的灰度由载波频率（FM 调制）携带，因此接收机必须精确跟踪载波频率，环路性能直接决定图片质量。

图7-48 边环的结构

对照框图，信号的处理流程如下：

1. 前端滤波与数字化。天线信号先经过一个 4 阶巴特沃思带通滤波器滤除带外噪声并放大，然后送入 8 位 ADC，以载波基带频率的 32 倍或 64 倍采样率进行数字化。过采样率越高，相位检测的分辨率越细（后面会算出具体数值），代价是硬件量略微增加。
2. 信号分离。数字化后的信号被分离成两路，分别进入过零区间检测器和最小值/最大值检测器。在全数字实现中，鉴相不需要真的做乘法——通过检测信号波形的过零点和极值点出现的时刻，就能比较”信号相位”与”参考相位”的先后关系。
3. 参考相位的合成。信号的 $\pi /2$ 移相副本由一个时间常数较大的 PLL 与参考累加器合成。这个辅助 PLL 只负责产生平滑的相位参考，不承担快速跟踪任务，所以可以做得”慢而稳”。
4. 四个相位检测器。每个相位检测器配有两个边沿检测器，总共可以生成 4 个 UP 信号和 4 个 DOWN 信号。它们的含义非常直白：如果某个检测周期内 UP 脉冲多于 DOWN 脉冲，说明本地参考的相位落后于信号，即参考频率太低，需要调高；反之就是参考频率太高，需要调低。
5. 环路滤波（累加器）。所有 UP/DOWN 信号汇入一个 13 位累加器构成的环路滤波器。在一个像素的持续时间内，累加器对 $\sum \mathrm{UP}-\sum \mathrm{DOWN}$ 的差进行累加。这个累加和既反映了频差的大小，也反映了频差持续的方向。
6. 像素转换器与 DCO。累加结果送入像素转换器，后者按查表方式给出 DCO 的”校正值”（见表 7-19）。同时，累加和还被用作像素的灰度值（4 位，0~15），传递给 PC 存储并显示气象传真图片——也就是说，同一个累加器一手控制频率跟踪，一手输出解调结果，一物两用，非常经济。

3.4 环路滤波器输出与 DCO 校正：表 7-19 的读法

表 7-19 列出了 32 倍过采样时，13 位累加器在不同区间的输出所对应的 DCO 校正量、灰度值和频率偏移：

下溢	溢出	累加和 $s$	DCO-IN	灰度值	$f_{carrier}\pm \delta f$
是	否	$s<-(2^{13}-1)$	3	0	+180Hz
否	否	$-(2^{13}-1)⩽s<-2048$	2	0	+120Hz
否	否	$-2048⩽s<-512$	1	4	+60Hz
否	否	$-512⩽s<512$	0	8	+0Hz
否	否	$512⩽s<2048$	-1	12	-60Hz
否	否	$2048⩽s<2^{13}-1$	-2	15	-120Hz
否	是	$s⩾2^{13}-1$	-3	15	-180Hz

这张表的逻辑可以用三个要点读懂：

• 死区：$|s|<512$ 时 DCO 校正为 0，对应频率偏差 0 Hz。这个”死区”防止噪声引起的微小抖动让 DCO 频繁微调，相当于给环路加了一级平滑。
• 分段校正与饱和：累加值偏离零越远，说明频差越大、越持续，校正步长从 ±1、±2 一直加到 ±3，对应的频偏为 ±60 Hz、±120 Hz、±180 Hz。一旦累加器下溢（$s<-(2^{13}-1)$，即严重低于 $-8191$）或溢出（$s⩾2^{13}-1$），说明误差已经顶满量程，校正取最大值 ±3。
• 灰度值：灰度值与校正量的方向相反——频偏为正（+180 Hz，对应黑色像素区域之类的极端情况）时灰度值取 0，频偏为负时灰度值取 15，中间 0 Hz 对应灰度 8。这样频率信息被原样映射成 4 位像素灰度，供 PC 成像。

下述硬件结构可以用下面的 Verilog 描述（原书 VHDL 改写为 Verilog）：

// 原书 VHDL 改写为 Verilog：Costas 环的 13 位环路滤波器与 DCO 校正逻辑
module costas_loop_filter (
    input  wire               clk,       // 像素时钟（2 k 波特）
    input  wire               rst_n,     // 低有效复位
    input  wire        [2:0]  up_cnt,    // 本像素内 ∑UP（4 个边沿检测器）
    input  wire        [2:0]  down_cnt,  // 本像素内 ∑DOWN
    output reg  signed [12:0] acc,       // 13 位累加和，兼作像素灰度值
    output reg  signed [2:0]  dco_in     // DCO 校正值，范围 -3 ~ +3
);
    // 一个像素内 ∑UP - ∑DOWN 的差值
    wire signed [3:0] diff = $signed({1'b0, up_cnt})
                           - $signed({1'b0, down_cnt});
 
    // 13 位累加器：累加 ∑UP - ∑DOWN，带正/负饱和
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n)
            acc <= 13'sd0;
        else if (acc ==  13'sd8191)          // 正向溢出：保持饱和
            acc <= acc;
        else if (acc == -13'sd8191)          // 负向下溢：保持饱和
            acc <= acc;
        else
            acc <= acc + diff;
    end
 
    // 像素转换器：按表 7-19 分段给出 DCO 校正值
    always @(*) begin
        if      (acc <= -13'sd8191) dco_in =  3'sd3;  // 下溢 → +3
        else if (acc <  -13'sd2048) dco_in =  3'sd2;
        else if (acc <  -13'sd512)  dco_in =  3'sd1;
        else if (acc <   13'sd512)  dco_in =  3'sd0;  // 死区 → 0
        else if (acc <   13'sd2048) dco_in = -3'sd1;
        else if (acc <   13'sd8191) dco_in = -3'sd2;
        else                        dco_in = -3'sd3;  // 溢出 → -3
    end
endmodule

这段代码是纯可综合风格：累加器用带同步使能结构的时序逻辑实现，分段查表用组合逻辑实现，饱和判断显式写出，任何 FPGA 综合器都能直接映射。

3.5 性能指标：分辨率、灰度级与锁定时间

最小可检测相移与频率分辨率。对于 2k 波特的像素率，32 倍过采样意味着每个载波周期被切成 32 份，采样周期为

$$t_{ph37}=\frac{1}{32\times 117\mathrm{kHz}}\approx 266\mathrm{ns}$$

这个 266 ns 就是一个采样周期内相位检测器能分辨的最小时间间隔。把它折算到”一个像素持续时间内能检测的最小相移”，就得到式 (7-43)：

$$f_{\mathrm{carrier}}+1=\frac{1}{1/f_{\mathrm{carrier}}-t_{ph37}\times 2\mathrm{k}\mathrm{波特}/f_{\mathrm{carrier}}}=117.46\mathrm{kHz}\text{\hspace{1em}(7-43)}$$

代入数值验证一下：$1/117.4\mathrm{kHz}\approx 8.518\mu \mathrm{s}$；而 $t_{ph37}\times 2000/117400\approx 266\mathrm{ns}\times 0.01704\approx 4.53\mathrm{ns}$；两者相减得 $8.513\mu \mathrm{s}$，其倒数正是 $117.46\mathrm{kHz}$。也就是说，环路能分辨出的最小频率变化是

$$117.46\mathrm{kHz}-117.4\mathrm{kHz}=60\mathrm{Hz}$$

这恰好与表 7-19 中每档校正量对应 60 Hz 相互印证——硬件的时间分辨率决定了频率分辨率，两处结果完全自洽。

灰度级。气象传真的灰度信息靠 ±300 Hz 的频率调制携带（频偏范围 600 Hz）。既然环路每 60 Hz 分辨一档，那么 $600/60=10$ 档之上再配合死区中心，可以区分出 5 个灰度值——这正是表 7-19 中灰度值一列只有 0、4、8、12、15 等少数几档的原因。像素灰度被量化得较粗，这是 2k 波特、32 倍过采样条件下频率分辨率 60 Hz 的直接结果；若把过采样率提高到 64 倍，$t_{ph37}$ 减半，分辨率可提升到约 30 Hz。

最长锁定时间。相位误差最大可达 $\pi$，即半个载波周期：

$$\frac{1}{2}\times \frac{1}{117\mathrm{kHz}}\approx 4.26\mu \mathrm{s}\approx 16\times 266\mathrm{ns}$$

也就是 16 个采样周期。而环路每采样一次最多能纠正 $16/3$ 个采样周期的相位（满量程校正步长为 3），所以最长锁定时间为

$$T_L=\lceil \frac{16}{3}\rceil =6\text{ 次采样}\approx 1.5\mu \mathrm{s}$$

微秒量级的锁定时间对传真这类低速应用绰绰有余，也直观展示了”误差斜率翻倍”带来的捕获速度优势。

3.6 复杂性评估：全数字边环要花多少硬件

表 7-20 给出了全数字边环在 32 倍和 64 倍过采样时的硬件开销（以 CLB 为单位，4 个 CLB 约相当于一片 Spartan-6 的一个基本单元量级）：

功能组	32倍过采样时的CLB	64倍过采样时的CLB
频率合成器	33	36
零点检测	42	42
最大值检测	16	16
四相位检测器	8	8
环路滤波器	51	51
DCO	12	15
TMS接口	11	11
总计	173	179

从这张表可以读出几个有启发性的结论：

• 开销大头不在”核心算法”。环路的核心——四个相位检测器——只占 8 个 CLB；而零点检测（42）和环路滤波器（51）这两个”外围但精细”的模块占了全部开销的一半以上。这与第 2 节数字 PLL 的结论一致：环路滤波器往往是数字环中最昂贵的部件。
• 提高过采样率的代价很小。过采样率从 32 倍翻到 64 倍，总开销只从 173 增加到 179（约 3.5%），主要变化在频率合成器和 DCO 上（计数器需要多一位分辨率）。如果应用需要更细的频率分辨率，提高过采样率是一笔非常便宜的买卖。
• 全数字实现的可行性。整个边环不到 180 个 CLB，在现代 FPGA（如 Cyclone IV E 系列的 EP4CE115 器件，拥有上万个 LE）上只占很小的比例。这也再次印证了本节开头的判断：对增益失配敏感的边环，全数字实现不仅”正确”，而且”便宜”。

3.7 小结

边环是相干环的扩展：用 I/Q 正交解调加上第三乘法器，把被抑制的载波信息”乘”出来作为误差信号。与 PLL 相比，它的误差斜率在小相移时翻倍（$\sin 2\Delta \varphi$ 对比 $\sin \Delta \varphi$），锁定速度快约两倍，代价是复杂度翻倍和 180° 相位模糊。本章的气象传真实例展示了全数字边环的完整工程链路：带通滤波、8 位 ADC 过采样、过零/极值检测、四相位检测器、13 位累加器环路滤波、查表式 DCO 校正，最后同一个累加和还兼作像素灰度输出。频率分辨率 60 Hz、5 个灰度级、最长锁定时间约 1.5 μs、总开销不到 180 个 CLB——这些环环相扣的数字，正是”采样率决定分辨率、分辨率决定校正档位、校正档位决定锁定速度”这一全数字环路设计逻辑的最佳注脚。