差错控制

噪声、码间串扰、多接入干扰和邻小区干扰都可能造成误码。匹配滤波和最佳判决可以减小差错概率，却不能保证差错完全消失，因此还要在传输中加入适当的冗余。差错控制有两条基本路线：

自动请求重传（Automatic Repeat reQuest, ARQ）：接收端先检错，发现错误后通过反馈信道要求发送端重传。
前向纠错（Forward Error Correction, FEC）：发送端加入有结构的冗余，接收端不依赖反馈，直接从收到的序列中纠错。

FEC不需要反馈，瞬时传输速率稳定，适合实时业务；代价是占用额外的传输资源并增加编译码复杂度。ARQ只有在出错时才增加冗余，信道较好时效率较高，但传播、反馈和重传都会带来不确定的时延。实际系统也常把两者结合起来。

信道编码与编码增益

信道编码通常指用于FEC的纠错编码。它可以按线性码与非线性码、分组码与卷积码、系统码与非系统码分类。实用编码只能采用有限码长，所以误码率不可能严格为零；引入代数结构，则是为了让编译码可以实现。评价一个码时，要同时看误码率和码率：前者衡量可靠性，后者衡量有效性。

若每次输入编码器的\(k\)个信息比特被编码为\(n\)个码元，码率为

\[ R_c=\frac{k}{n} \]

若每个信息比特的平均能量为\(E_b\)，每个编码码元的平均能量为\(E_s\)，则课件采用的能量关系为

\[ E_s=E_bR_c \]

在给定误比特率下，编码系统所需的\(E_b/n_0\)低于未编码系统所需的信噪比，两者以dB表示时的差称为编码增益。编码增益不是“凭空增加能量”，而是用冗余和译码复杂度换取更低的差错率。

以交叉概率为\(p_e\)的二进制对称信道为例，一个比特只传一次时错误概率为\(p_e\)。若把它重复三次并采用多数判决，至少两次传错才会误判，因此

\[ P_e=\binom{3}{2}p_e^2(1-p_e)+p_e^3\mathop{\approx}_{p_e\to0}3p_e^2 \]

差错概率的阶数从\(p_e\)变成了\(p_e^2\)，但码率也降到了\(1/3\)。这正体现了可靠性和有效性的交换。

二进制域 \(\mathrm{GF}(2)\)

本讲讨论的码主要定义在二元有限域\(\mathrm{GF}(2)=\{0,1\}\)上。加法就是异或，乘法就是普通的二进制乘法：

\[ 0+0=0,\quad 0+1=1+0=1,\quad 1+1=0 \]

\[ 0\cdot0=0,\quad 0\cdot1=1\cdot0=0,\quad 1\cdot1=1 \]

因而加法和减法没有区别，均可写成模2加。这一点贯穿生成矩阵、监督矩阵和校正子的全部运算。

分组码与汉明距离

分组码把信息序列分成长度为\(k\)的组，每组独立映射为一个长度为\(n\)的码字，记为\((n,k)\)码。监督码元只由本组的信息码元决定，共有\(2^k\)个许用码字，码率为\(k/n\)。最简单的例子是奇偶监督码：在\(n-1\)个信息位后加入一位

\[ a_n=a_1+a_2+\cdots+a_{n-1} \]

正确的偶校验码字满足

\[ a_1+a_2+\cdots+a_n=0 \]

它能检出任意奇数位错误，却会漏掉偶数位错误，因此只能检错，不能确定错误位置并纠错。

两个二元向量\(\mathbf x,\mathbf x'\)的汉明距离，是它们取值不同的位置数，也等于模2和中“1”的个数：

\[ d_H(\mathbf x,\mathbf x')=w(\mathbf x+\mathbf x') \]

其中\(w(\mathbf x)\)为汉明重量，即向量中“1”的个数。一个码的最小码距定义为任意两个不同许用码字之间的最小距离：

\[ d_{\min}=\min_{\mathbf c_i\ne\mathbf c_j}d_H(\mathbf c_i,\mathbf c_j) \]

最小码距决定了码字周围可以留出多大的判决区域。若要求纠正不超过\(t\)位错误，同时还能检出不超过\(e\)位错误，并取\(t\le e\)，则必须满足

\[ d_{\min}\ge t+e+1 \]

两个常用的特例是

\[ t=0:\quad d_{\min}\ge e+1 \]

\[ t=e:\quad d_{\min}\ge2t+1 \]

所以，只考虑纠错时最多可保证纠正

\[ t_{\max}=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor \]

位错误；只考虑检错时最多可保证检出\(d_{\min}-1\)位错误。设计分组码的两个方向也由此得到：在可靠性上尽量增大\(d_{\min}\)，在有效性上则希望同一码长内保留尽可能多的许用码字。

线性分组码

若许用码字在\(\mathrm{GF}(2)\)上构成线性空间，就得到线性分组码。课件采用行向量记法：信息向量\(\mathbf X\)与生成矩阵\(G\)相乘得到码字\(\mathbf A\)，

\[ \mathbf A=\mathbf XG \]

任意两个许用码字之和仍是许用码字，所以线性码的最小码距也等于非零码字的最小重量：

\[ d_{\min}=\min_{\mathbf A\in\mathcal C,\,\mathbf A\ne0}w(\mathbf A) \]

\(G\)是\(k\times n\)矩阵，应当行满秩，且不含全零列。行满秩保证不同信息向量不会映射到同一码字；全零列始终不能携带信息，应当删去。系统线性码的典型生成矩阵为

\[ G=[I_k\ Q] \]

此时码字的前\(k\)位就是原始信息位，后\(r=n-k\)位为监督位。相应的监督矩阵可取

\[ H=[Q^{\mathrm T}\ I_r] \]

于是

\[ GH^{\mathrm T}=[I_k\ Q]\begin{bmatrix}Q\\I_r\end{bmatrix}=Q+Q=0 \]

所有许用码字都满足

\[ \mathbf AH^{\mathrm T}=0 \]

对一般的线性码，\(G\)不必含有显式的单位阵，但\(H\)仍可取为\(G\)零空间的一组基，使\(GH^{\mathrm T}=0\)。通过高斯消元和列置换可以把\(G\)化成系统形式，再按上式求\(H\)，最后把列顺序还原。

校正子

设接收向量为

\[ \mathbf B=\mathbf A+\mathbf E \]

其中差错图样\(\mathbf E\)在发生翻转的位置取1。接收端计算校正子

\[ \mathbf S=\mathbf BH^{\mathrm T}=(\mathbf A+\mathbf E)H^{\mathrm T}=\mathbf EH^{\mathrm T} \]

校正子与发送的码字\(\mathbf A\)无关，只由差错图样决定。\(\mathbf S=0\)表示“没有检出错误”，但也可能是码字恰好错成了另一个许用码字；\(\mathbf S\ne0\)则一定发生了可检出的错误。

若只考虑一位错，第\(v\)位出错时，\(\mathbf S\)就是\(H\)第\(v\)列的转置。要区分“无错”和\(n\)种单比特错误，\(r\)位校正子至少要表示\(n+1\)种情况：

\[ 2^r\ge n+1,\qquad r\ge\left\lceil\log_2(n+1)\right\rceil \]

因此，能纠正任意一位错的监督矩阵不能含全零列，而且各列必须互不相同。

Hamming码

当上面的界恰好取等号时，得到二进制Hamming码：

\[ n=2^r-1,\qquad k=n-r=2^r-1-r \]

其监督矩阵的\(n\)列恰好遍历全部非零\(r\)维二元向量，所以每个非零校正子都唯一对应一个错误位置。Hamming码的基本参数为

\[ d_{\min}=3,\qquad t=1,\qquad R_c=\frac{2^r-1-r}{2^r-1} \]

\(d_{\min}=3\)可以从监督矩阵看出：\(H\)没有零列，也没有两列相同，故重量为1或2的非零码字不存在；任意两列之和又是某个非零列，所以存在重量为3的码字。若在纠正一位错的同时讨论保证检出的额外错误，则由\(d_{\min}\ge t+e+1\)得\(e=1\)。如果不做纠错、只做检错，\(d_{\min}=3\)则可检出两位错。

以\(r=3\)的\((7,4)\)Hamming码为例，课件选取

\[ Q=\begin{bmatrix}1&1&1\\1&1&0\\1&0&1\\0&1&1\end{bmatrix} \]

从而

\[ G=\begin{bmatrix}1&0&0&0&1&1&1\\0&1&0&0&1&1&0\\0&0&1&0&1&0&1\\0&0&0&1&0&1&1\end{bmatrix} \]

\[ H=\begin{bmatrix}1&1&1&0&1&0&0\\1&1&0&1&0&1&0\\1&0&1&1&0&0&1\end{bmatrix} \]

\(H\)的七列依次为\(111,110,101,011,100,010,001\)，正好标识七个错误位置。例如\(\mathbf X=0010\)编码为\(\mathbf A=0010101\)。若第一位出错，收到\(1010101\)，校正子为\(111\)，接收端翻转第一位即可恢复。若第三、六位同时出错，校正子也可能等于某个单比特错误对应的列；单错译码器会按错误的位置再翻转一次，反而造成误纠正。因此普通Hamming码只能保证纠正一位错。

Hamming码还是完备码。每个码字本身和距它为1的\(n\)个向量恰好填满整个码字空间：

\[ 2^k(1+n)=2^k2^r=2^n \]

在交叉概率为\(\varepsilon\)的BSC上，\((7,4)\)Hamming码只有出现至少两位错才会造成误块，故

\[ P_B=\sum_{i=2}^{7}\binom{7}{i}\varepsilon^i(1-\varepsilon)^{7-i}\mathop{\approx}_{\varepsilon\to0}21\varepsilon^2 \]

若同样用\((7,4)\)的长度和码率，却简单地把三个监督位固定为0，则\(d_{\min}=1\)，

\[ P_B=1-(1-\varepsilon)^7\mathop{\approx}_{\varepsilon\to0}7\varepsilon \]

两者码率相同，但误块率的阶数不同，这就是码字集合设计带来的编码增益。

陪集、陪集首与标准阵列

设线性码的码字集合为\(\mathcal C\)。对固定差错图样\(\mathbf E\)，集合

\[ \mathbf E+\mathcal C=\{\mathbf E+\mathbf A:\mathbf A\in\mathcal C\} \]

称为一个陪集。陪集内所有向量具有相同的校正子，因为

\[ (\mathbf E+\mathbf A)H^{\mathrm T}=\mathbf EH^{\mathrm T} \]

译码时通常把该陪集中重量最小的向量选作陪集首，优先解释为较少位的差错。收到\(\mathbf B\)后，先由校正子找到相应的陪集首\(\hat{\mathbf E}\)，再作

\[ \hat{\mathbf A}=\mathbf B+\hat{\mathbf E} \]

标准阵列把这种划分完整列出：第一行是\(2^k\)个许用码字，第一列是\(2^{n-k}\)个陪集首，每一行由该陪集首分别加上全部许用码字得到。因此阵列共有\(2^{n-k}\)行、\(2^k\)列，恰好覆盖全部\(2^n\)个二元向量。

校正子只有\(2^{n-k}\)种，所以译码器只能为每种校正子指定一个首选差错图样。除全零图样外，如果非零校正子的数量大于\(n\)，在标识全部单比特错误后还可以标识一部分多比特错误；如果小于\(n\)，就连所有单比特错误也不能完全区分。Hamming码中每个非零校正子都已用于一位错，正好没有剩余。

交织与突发错误

分组码擅长处理分散的随机错误，但衰落等因素常使错误连续出现。交织器不增加码字本身的纠错能力，而是改变码元的发送次序，把一段突发错误在解交织后打散到多个码字中。

对宽度为\(n\)、深度为\(m\)的分组交织器，可把\(m\)个长度为\(n\)的码字逐行写入矩阵，再逐列读出；接收端执行逆置换。原来同一码字中相邻的码元在信道上被拉开，信道上的连续错误则分散到不同的行。若每个分组码字可以纠正\(b\)个错误，理想情况下交织后可以抵抗长度不超过\(mb\)的突发错误。增大交织深度能提高抗突发错误能力，但也会增加缓存和编译码时延。

例如，把五个\((7,4)\)Hamming码字排成\(5\times7\)矩阵后交织，一段连续五位的突发错误可被分到五个码字，每个码字只留下一位错，仍可由Hamming译码器纠正。

卷积码

分组码的译码依赖一个完整码字。码长增大时，译码时延和复杂度也随之增大。卷积码不把输入切成彼此独立的有限分组，而是让每次输出只依赖当前输入和有限段历史输入，因此可以在序列持续到达时不断编码和译码。

课件用\((n,k,N)\)描述卷积码：每次有\(k\)位信息进入移位寄存器，输出\(n\)位编码结果，寄存器级数\(N\)称为约束长度，码率为

\[ R_c=\frac{k}{n} \]

若把当前输入所在的一级排除，决定后续转移的记忆状态共有\(k(N-1)\)位，所以状态数为

\[ M=2^{k(N-1)} \]

以课件中的\((2,1,3)\)码为例，两路生成抽头分别为\(111\)和\(101\)。若输入为\(u_i\)，则

\[ v_{i,1}=u_i+u_{i-1}+u_{i-2},\qquad v_{i,2}=u_i+u_{i-2} \]

全部运算仍在\(\mathrm{GF}(2)\)上。寄存器从全零状态开始时，输入\(1101\)对应的输出为

\[ 11\,01\,01\,00 \]

树状图、状态图与网格图

树状图从初始状态展开所有可能输入。每个时刻有\(2^k\)种输入，因此每个节点产生\(2^k\)条分支，分支上标出本次输出。它最直观地展示了输入序列和输出序列之间的对应关系，但同一种寄存器状态会在不同分支上反复出现，树会指数增长。

状态图把相同的寄存器状态合并成一个节点，边表示一次状态转移，并标记相应的编码输出。对上述\((2,1,3)\)码，令状态按\((u_{i-2},u_{i-1})\)排列，有四种状态：

当前状态	输入0：下一状态/输出	输入1：下一状态/输出
\(00\)	\(00/00\)	\(01/11\)
\(01\)	\(10/10\)	\(11/01\)
\(10\)	\(00/11\)	\(01/00\)
\(11\)	\(10/01\)	\(11/10\)

网格图又称Trellis图，它把状态图沿时间轴逐级展开。每一列列出当前可能的状态，相邻两列之间的边就是允许的状态转移。树状图适合枚举和观察距离，状态图适合分析状态转移与自由距，网格图则直接用于编码路径表示和Viterbi译码。

图中状态\(00,01,10,11\)分别对应课件里的\(a,b,c,d\)。红色路径从全零状态出发，依次经过\(01,11,10,01\)，四条分支输出为\(11,01,01,00\)，与前面的编码结果一致。

自由距

卷积码也是线性码，所以两个编码序列之间的距离可转化为某个非零编码序列相对全零序列的重量。由于卷积码没有固定的码字边界，更有意义的距离参数是自由距：所有从全零状态出发、经过非零状态后第一次重新并入全零状态的路径中，输出汉明重量的最小值。

\[ d_{\mathrm{free}}=\min_{\substack{\text{路径离开零状态}\\\text{并重新回到零状态}}}w(\text{路径输出}) \]

对上面的\((2,1,3)\)码，最短的非零回归路径输出为\(11,10,11\)，重量为5，因此

\[ d_{\mathrm{free}}=5 \]

自由距越大，两个可能的无限长编码序列越不容易被噪声混淆。

Viterbi译码

若接收序列没有错误，就能在网格图上找到一条输出与它完全一致的路径；有错误时，则选择与接收序列距离最小的路径。对硬判决输入，整条路径的代价就是各分支汉明距离之和：

\[ \Lambda(\mathcal P)=\sum_i d_H(\mathbf y_i,\mathbf v_i(\mathcal P)) \]

直接枚举所有路径的复杂度随序列长度指数增长。Viterbi算法利用动态规划：在每个时刻、对每个状态，只比较所有进入该状态的候选路径，保留累计代价最小的幸存路径；下一时刻只从这些幸存路径继续延伸。其依据是，到达某状态的非最优前缀以后不可能反超具有相同后续选择的最优前缀。待各幸存路径充分汇合后回溯，就可以逐步给出译码结果。译码器只需维护与状态数同阶的路径，而不必保存所有历史可能性。

硬判决译码器的输入已经被量化为确定的0或1，通常用汉明距离作分支度量。软判决保留接收样值对0或1的置信度，用多比特数值、概率或对数似然比表示，并按欧氏距离或负对数似然计算分支度量。软判决没有提前丢掉“这一位有多可靠”的信息，通常比硬判决性能更好，广泛用于卷积码的Viterbi译码以及迭代译码。

自动请求重传

ARQ是数据链路层的重要协议。设一个长度为\(n\)的分组经过BSC传输，单比特交叉概率为\(\varepsilon\)，定义

\[ P_c=(1-\varepsilon)^n \]

为分组正确概率，\(P_d\)为发生错误且被检出的概率，\(P_m\)为发生错误却漏检的概率，则

\[ P_c+P_d+P_m=1 \]

被检出的错误会触发重传，漏检错误则会被当成正确分组交付。经过任意多次重传后，最终交付错误分组的概率为

\[ P_b=P_m+P_dP_m+P_d^2P_m+\cdots=\frac{P_m}{1-P_d}=\frac{P_m}{P_c+P_m} \]

理想重传仍受到传播、分组传输、译码计算和ACK/NAK反馈时延的限制。若信道符号速率为\(R\)，每个分组含\(k\)个信息比特、编码后有\(n\)个符号，记

\[ T_m=\frac{n}{R} \]

为分组传输时间，\(T_d\)为单程传播时延，\(T_c\)为译码计算时间，\(T_a\)为ACK或NAK的传输与处理时间，并令

\[ T_{dca}=2T_d+T_c+T_a \]

下面的吞吐量\(\eta\)以“单位信道可传符号所承载的有效信息比特数”归一化，因此无差错、无等待时的上限就是码率\(k/n\)。

停-等ARQ

停-等（Stop-Wait, SW）协议发送一个分组后必须等待ACK/NAK；收到ACK才发送下一个分组，收到NAK或超时则重传当前分组。一次发送和等待周期为

\[ T_D=T_m+T_{dca} \]

即使总是一次成功，其吞吐量上限也只有

\[ \eta_{\mathrm{SW},0}=\frac{k}{T_DR}=\frac{k}{n+T_{dca}R} \]

每次以概率\(P_d\)触发重传，直到不再检出错误，平均发送次数为

\[ N_R=\frac{1}{1-P_d} \]

所以平均吞吐量为

\[ \eta_{\mathrm{SW}}=\frac{k}{T_DR}(1-P_d)=\frac{(k/n)(1-P_d)}{1+T_{dca}R/n} \]

若检错能力完美，即所有含错分组都能检出，则\(P_d=1-(1-\varepsilon)^n\)，从而

\[ \eta_{\mathrm{SW}}=\frac{k/n}{1+T_{dca}R/n}(1-\varepsilon)^n \]

停-等实现简单，但在传播往返时延较大时，发送端大部分时间都在等待。

返回N ARQ

返回N（Go-Back-N, GBN）采用流水发送，不必等前一分组的反馈就继续发送后续分组。若某分组检出错误，则从这个分组开始，把已经发出的后续分组一起重传。没有重传时，流水线填满后的吞吐量上限为

\[ \eta_{\mathrm{GBN},0}=\frac{k}{n} \]

把一次往返反馈时间折算成整数个分组传输时间，记

\[ T_{dca}'=\left\lceil\frac{T_{dca}}{T_m}\right\rceil T_m \]

课件给出的平均吞吐量为

\[ \eta_{\mathrm{GBN}}=\frac{(k/n)(1-P_d)}{1+(RT_{dca}'/n)P_d} \]

完美检错时

\[ \eta_{\mathrm{GBN}}=\frac{(k/n)(1-\varepsilon)^n}{1+(RT_{dca}'/n)\left[1-(1-\varepsilon)^n\right]} \]

GBN消除了逐包等待，却可能因一个错误重传一串已经正确到达的分组。

选择重传ARQ

选择重传（Selective Repeat, SR）同样连续发送，但只重传真正出错的分组。假定窗口和缓存足够、反馈机制理想，其无差错吞吐量上限与GBN相同：

\[ \eta_{\mathrm{SR},0}=\frac{k}{n} \]

成功交付一个分组所需的平均传输时间为

\[ \overline T=T_m(1-P_d)+2T_mP_d(1-P_d)+3T_mP_d^2(1-P_d)+\cdots=\frac{T_m}{1-P_d} \]

因此理想选择重传的平均吞吐量为

\[ \eta_{\mathrm{SR}}=\frac{k}{\overline TR}=\frac{k}{n}(1-P_d) \]