引入

章节目标

在week1与week2中已经学习了无线信道的特性，无线信道发展遇到的挑战，信道容量等。

那么要如何使得真实的系统逼近理论信道容量极限呢？如何在无线信道中发送数字信号呢？如何解决信道干扰呢？

本小节的主题将会使用信道编码来解答这三个问题。本节将介绍一些典型的信道编码，他们的功能，以及性能分析。

信道编码：编码增益（Coding Gain）

信道编码将会引入一些冗余，来使得错误可以被纠正和发现。

Coding gain（编码增益）表示在相同误码率（BER）条件下，使用编码后的系统相比未编码系统所需的信噪比（SNR）降低量。简单来说，它告诉我们：通过引入冗余和纠错机制，我们可以“省下”多少信号功率来达到同样的可靠性。

例如下图，在同样的SNR下，uncoded的错误率比coded更高，$C_{g1}$和$C_{g2}$就被称为编码增益。但随着信噪比（SNR）的增加，编码系统会表现出误码率瓶颈（error floor）现象。在超过某一阈值的信噪比范围内，误码概率下降得明显变慢，如下图coded曲线末端，这是因为在该信噪比区间内，最小距离误码事件最终成为影响编码性能的主要因素。

信道编码：带宽延展

在信道编码中，我们通过加入冗余信息（冗余位）来提高抗误码能力。这种做法虽然能提升可靠性，但也会带来一个副作用：原始信息的比特数变多了，传输时需要更多的带宽或时间资源。

假设我们有原始信息比特数：k；编码后的比特数：n(n > k)。信道内数据速率为$R_b$，那么因为信道编码的带宽延展，数据速率将会损失为$(k/n)R_b$。

其中$k/n$被称为编码率（Code Rate）

信道编码方式

信道编码整体来看可以分为两种：块码（Block code）和卷积码（Convolutional Code）。块码是给我k个bits，我就将这个k个bits增加冗余信息，还你n个bits；编码后的n bits仅与输入的k有关，无记忆。卷积码是给我k个bits，我根据当前的这k个bits和之前的输入，还给你编码后的n，有记忆性。

块码（Block Code）

引入：单比特奇偶校验码（Single-bit parity check code）

单比特奇偶校验码在数据中添加额外的1bit，用于存储奇偶校验，以此来检测传输错误。对于奇校验，会通过添加的这1bit使整个数据的1的个数为奇数；偶检验则是使其为偶数。一旦传输过程中某一bit出错，则奇数/偶数规则将不满足。下图是偶校验的编码。

单比特奇偶校验只能检测1bit错误的情况，而且无法纠错。

概念：线性块码（Linear Block Code）

线性快码是将输入的k bits线性映射到输出的n bits。下图是一个简单的例子，假设k=2bits，n=3bits。则按照下图的规则进行编码。

编码后的数据相较于原数据增加了1bit，这1bit可以为它带来更大的汉明距离，按照最大的汉明距离映射也是线性块码的映射原则。这些将在下面的内容详细介绍。

下面将从1. 生成矩阵（编码）； 2. 极性校验矩阵（解码）； 3. 错误检测； 4.最小距离来逐个介绍线性块码

线性块码：生成矩阵（如何编码）

将需要被编码的k bits表达成矩阵$U_i=[u_{i1},u_{i2},…,u_{ik}]$，将编码后的信息表达成矩阵$C_i=[c_{i1},c_{i2},…,c_{ik}]$。记生成矩阵为$G$，编码信息可以通过如下表达式来计算

$C_i=U_iG$

其中，生成矩阵$G$是$k\times n$的（k行n列）。注意，如果信息矩阵和生成矩阵为二进制数，那么计算矩阵乘法时需要遵循二进制乘法和二进制加法，即乘法按照原有规则，加法按照异或计算

例子：已知生成矩阵G为：

$\mathbf{G} = \begin{bmatrix} \mathbf{V}_1 \\ \mathbf{V}_2 \\ \mathbf{V}_3 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}$

求信息$U_i=[0,0,0]$和$U_i=[1,1,0]$编码后的结果

$C_i=[0,0,0]\times\begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}=[0, 0, 0, 0, 0, 0, 0]$ $C_i=[1,1,0]\times\begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}=[1, 0, 1, 1, 1 ,0]$

通过观察不难发现，上面这个例子的生成矩阵可以分为两部分：

$\mathbf{G} = \begin{bmatrix} 1 & 1 & 0 &| 1 & 0 & 0 \\ 0 & 1 & 1 &| 0 & 1 & 0 \\ 1 & 0 & 1 &| 0 & 0 & 1 \end{bmatrix}$

后半部分的$\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}$会使得$C_i$的后三位等于原始信息，就像上例中对0,0,0编码之后后三位是0,0,0；对1,1,0编码之后后三位是1,1,0。这是生成矩阵的一个特性：原始信息为编码后信息的一部分。

而前面的$\begin{bmatrix}
1 & 1 & 0\\
0 & 1 & 1 \\
1 & 0 & 1
\end{bmatrix}$会使得被编码的3bit两两做异或运算，这样就得到了他们两两之间的极性码。

因为这种编码的编码和解码需要进行大量矩阵运算，试想一下，手机正在以10Mbps速度传输，那么用CPU来进行这些运算定然是不科学的。因此线性快码需要借助芯片/FPGA来实现编解码。那么应该如何在硬件上实现编码运算呢？

对于前面例子的G，它可以分为两部分，头是对$u_{i1},u_{i2},u_{i3}$分别两两做异或，得到$P_1,P_2,P_3$。然后将$P_1,P_2,P_3$与$u_{i1},u_{i2},u_{i3}$直接拼在一起即可。如下图，$C_i$首先获取极性吗的输出，然后转获取原始信息的输出。

线性块码：极性校验矩阵（用于错误检测）

极性校验矩阵是由生成矩阵推导而来的，它与生成矩阵之间满足$GH^T=0$。这样，假设收到的信息无错误$R_i=C_i$，那么将收到的信息乘极性检验矩阵的转置可以得到：

$R_iH^T=C_iGH^T=0_{n-k的单位0矩阵}$

极性校验矩阵的推导过程如下：

对于任意的生成矩阵，其可以分为校验位$P$与复制信息位的单位矩阵的组合。其标准形式是信息位在前，校验位在后，如下式：（其中$I_k$表示$k\times k$的单位矩阵）

$G=[I_k|P]$

线性块码的极性校验矩阵 $H$被定义为：

$H=[P^T|I_{n-k}]$

其中$P^T$是$G$中极性校验部分的转置。

举个例子：考虑生成矩阵G

$G= [I_3 |P] = \begin{bmatrix} 1 & 0 & 0 &| 1 & 1 \\ 0 & 1 & 0 &| 0 & 1 \\ 0 & 0 & 1 &| 1 & 0 \end{bmatrix}$

其极性校验部分$\begin{bmatrix}
1 & 1 \\
0 & 1 \\
1 & 0
\end{bmatrix}^T=\begin{bmatrix}
1 & 0 & 1 \\
1 & 1 & 0
\end{bmatrix}$。输出n=5 bits，输入k=3bit，$n-k=2$

$H=[P^T|I_{n-k}]=\begin{bmatrix} 1 & 0 & 1 &| 1 & 0 \\ 1 & 1 & 0 &| 0 & 1 \\ \end{bmatrix}$

验证一下其性质：

$GH^T=\begin{bmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{bmatrix}\begin{bmatrix} 1 & 1\\ 0 & 1\\ 1 & 0\\ 1 & 0\\ 0 & 1\end{bmatrix}=\begin{bmatrix} (1+1) & (1+1)\\ (0) & (1+1)\\ (1+1) & (0) \end{bmatrix}=\begin{bmatrix} 0 & 0\\ 0 & 0\\ 0 & 0 \end{bmatrix}$

线性块码：综合症检测（Syndrome Test）（错误检测与纠正）

在信道编码中，综合症是通过接收码字与奇偶校验矩阵计算得到的，用于判断是否发生错误。因此综合征检测就是在检错和纠错。线性快码的综合征检测就是将收到的$R$与$H^T$乘起来。记综合征检测结果为$S$

$S=RH^T$

前面已经提到，如果收到的数据与发送数据相同$R=C$，则$S=0$。若R发生了部分比特错误，则其会变成$R=C+e$，对应的S也会变成：

$S=RH^T=CH^T+eH^T=0_{n-k}+eH^T$

举个例子：假设$C=[1\ 0\ 1\ 1\ 1\ 0]$，$R=[0\ 0\ 1\ 1\ 1\ 0]$, $
H^T = \begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 1 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1
\end{bmatrix}
$，那么：

$S=[0\ 0\ 1\ 1\ 1\ 0]\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix}=[1\ 0\ 0]=eH^T$

现在知道了$eH^T$存在，接收的信息有误，如何纠错呢？答案是查表。需要先建立一个Error pattern到 Syndrome的关系表，如下图

由于这个例子中编码数据的纠错能力为1bit，因此需要将所有的1bit情况列举出来，通过$eH^T$算好它对应的Syndrome，填入下表。然后查表发现$[1\ 0\ 0]$的对应错误图案为$[1\ 0\ 0\ 0\ 0\ 0]$，则将$R$加上错误图案，即可完成纠错。记纠错的结果为$\hat C$

$\hat C=R+\hat e=[0\ 0\ 1\ 1\ 1\ 0]+[1\ 0\ 0\ 0\ 0\ 0]=[1\ 0\ 1\ 1\ 1\ 0]$

至此就完成了纠错

线性块码：最小距离——错误纠正能力分析

上面提到上例纠错能力为1bit，那么这个1bit是如何确定的呢？它是由码字间最小汉明距离$d_{min}$得到的，公式如下：

$t=\bigg\lfloor\frac{d_{min}-1}{2}\bigg\rfloor$

这里需要科普一个概念：汉明重量与汉明距离。

汉明距离是两个向量之间不同位的数量
汉明重量是一个向量与全零向量之间的汉明距离，即一个二进制向量中 “1”的个数。
在线性卷积码生成矩阵设计时，最小汉明重量就是汉明距离。

举个例子：假设原始数据和编码后数据如下表

观察编码后数据，它的任意码字汉明重量最小为3，对于线性块码则其不同码间最小汉明距离$d_{min}=3$。

$t=\bigg\lfloor\frac{3-1}{2}\bigg\rfloor=1bit$

因此上例的纠错能力为1bit。

用图像来形象理解一下这个公式，假设现在有$C=[U\ V]$，$d_{min}=5$，那么$t=2$：

只要错误在2bit内，都还能纠回原来的$U$或$V$点，但是一旦超过2bit，则会越过中线，被纠正为错误的结果。

线性快码：最小距离——检错能力

从上面的纠错能力可以看出，这玩意只要不偏得太离谱，直接从一个码偏成了另一个码，那纵然无法恢复正确的码字但是是可以检出错误的。因此线性块码的检错能力为

$e=d_{min}-1$

卷积码（Conventional Code）

卷积码：编码

卷积码的系统框图如下图所示。输入序列为m1,m2,m3……; 最开始输入的移位寄存器内全部为0。输入端送入第一个bit，移位寄存器（Shift Register）内所选取的元素进行异或得到一组输出（U1,U2,U3….）；输入第二个元素，移位寄存器内所选取的元素进行异或得到第二组输出（U1,U2,U3….）…如此往复直到编码完成。

生成多项式$g$决定了进行异或时选取移位寄存器中的哪些bit。例如$g_1=1+x^k-2+x^k$就表示上图中选取右边第0位，左边倒数第3位，左边倒数第1位进行异或，输出结果为$U_1$。每个输出序列都是输入序列与生成多项式的模二卷积。

生成多项式的选择直接影响卷积码的纠错能力（最短自由距离）、是否灾难性传播等性能指标。

一个编码的例子：

现在有生成多项式$g_1=1+x+x^2, g_2(x)=1+x^2$，输入序列为101，求编码结果。

Input Stream (Waiting)	Shift Buffer	$g_1g_2$
10	100	11
1	010	10
-	101	00
-	010	10
-	001	11

因此编码后的结果是11 10 00 10 11。

卷积码：编码率

假设每个编码器有$k$个输出，输入序列的长度为$m$，移位寄存器的阶数为n，则卷积码的编码效率为

$CR=\frac{m}{k\times[m+(n-1)]}$

例如上面例子的Code Rate为$CR=\frac{3}{2\times(3+2)}=10$

卷积码：状态图（State Diagram）

卷积码的状态图用于表明下一个输入的bit对当前的输出的影响。对于任意一个时刻的移位寄存器，其MSB是最新输入的bit（input），其他的bit就是当前寄存器的状态(state)。状态图在方框内表明当前寄存器的状态，用不同的线表示当前的input，线指向该input输入后的下一个状态；同时，在线上写出当前卷积码的输出。一个4状态的状态图如下图所示。

举个例子：还是考虑前面的$g_1=1+x+x^2, g_2(x)=1+x^2$，下图展示了它的卷积码计算器和状态矩阵绘制过程

网格图与Viterbi卷积码译码（Viterbi Convolutional Decoding）

状态图可以被画成另一种形式：网格图（Trellis Diagram）。以上例的状态转换图为例，其有4个状态：00,01,11,10。将这几个状态化作网格图如下图所示绘制：

网格图的最左侧为状态，通过两排点表示状态的转换。其余部分与状态转换图一致。

有了网格图，即可进行Viterbi译码。卷积码译码遵循最大似然译码，即，选择最像的那个。Viterbi译码使用“码距（distance）”来衡量收到的码与当前码的相似性。假设原始数据为11011，经过上例中$g_1=1+x+x^2, g_2(x)=1+x^2$编码为11 01 01 00 01进行传输，收到数据为11 01 01 10 01，倒数第二个数据发生了一个错误。下面将展示Viterbi译码与卷积码纠错。

Step1：初始state为00，首先收到11，从00出发有两条路：00到10，输出为11；00到00，输出为00。保留这两条路，并计算这一步的码距：00与11有2bit不同，因此码距为2；11与11无bit不同，因此码距为0。

Step2：现在state可能为00，可能为10。从00和10又分别发散input1和input0的情况，并按照上面的方法各自计算码距，往后再加一排点进行绘制。Step1 & 2如下图所示

Step3：现在4中state都有一条路径通达。继续接收第三位数据01，并画出所有可能计算码距。此时发现每一个点都有2条路可以通达，根据他们的码距，保留码距较低的一条，如下图所示：

Step4：继续接收第四个数据10，并重复step3的操作

Step5：此时接收最后一位数01，并和前面一样算出所有可能路径的码距。此时码距最低的一个就是结果。根据这条路径的红蓝颜色逐个翻译成bit就行。如下图，最低码距为1，颜色为红红蓝红红，因此译码结果为11011

最终选择的数据总码距为1，那么代表其在传输过程中产生了1个错误。

卷积码的纠错能力：最短自由距离（Minimum Free Distance）

在卷积码中，第一个与汇合到0的分支与“收到全0数据”的码距就是最短自由距离。如下图所示，第一个汇合到0的分支是下图红线。它的第一次状态转换需要收到11，因此与00码距为2；第二次状态转换需要收到10，与00码距为1；第三次状态转换需要收到11，与00码距2。因此下例的最短自由距离为$d_f=2+1+2=5$

信道的纠错能力为：

$t=\bigg\lfloor\frac{d_f-1}{2}\bigg\rfloor$

在上例子$d_f=5$的编码中，纠错能力就是2bit。

在块码中，我们将原始信息直接存储在编码后的码字内。而卷积码中则不这样做，因为这样的生成函数会使得其最短自由距离更小，有损其纠错性能。

在本课中，不交如何设计生成函数；如果有需要，去查已经设计好的生成函数即可。

现代编码

串联编码（Concatenated Code）

串联编码的思想是将两种编码和在一起，如下图所示。原始数据先传入Outer Encoder，对其进行一次编码，然后使用交织器对其码序按照特定的顺序打乱，再传入Inner Encoder进行二次编码。在解码时进行逆操作。

Outer Encoder和Inner Encoder可以不是一种编码，例如outer使用块码，Inner使用卷积码。

Turbo 码

Turbo码在3G中使用。Turbo码由两个递归系统卷积码（RSC）编码器组成，中间通过一个伪随机交织器连接。这种结构使得编码具有“伪随机性”，增强了抗干扰能力。

下图是解码端的结构，收到的数据首先被放入译码器1，然后进行交织，交织后的信息再放入译码器2，然后解交织扔回译码器1，这样重复迭代进行解码。从下右图可以看出，多次迭代能显著降低BER。

因为迭代的两个Decoder涡轮一样，和发动机互相辅助，因此被称为Turbo码。