3. 卷积码
卷积码指Convolutional Code。
卷积码，将k位信息编码成n位（当前组），这n个bit的生成不仅和这k位有关，还和之前的N-1个组的信息有关。总共关联的有N * n 个bit。 我们一般记为 (n,k,N) 卷积码 。
可以看出来，当N增加时，纠错能力也增加，差错率随着N增大而指数下降。我们记N为卷积码的约束长度。
编码
（n,k,N） 卷积码由下面部分组成。
- N组k级输入移位寄存器 （一个长度为N * k 的存储空间，理解成一维数组接收数据输入，或理解成N * k 的二维数组暂存状态信息）
- n级输出移位寄存器 和 n个模二加法器 （每一级输出寄存器对应一个加法器）
如上图，每个异或（模二加法器）对应的输入是输入序列（N组k级寄存器）中的某些特定位。这些位是在编码中固定的。卷积码的生成矩阵就是在描述 N * K 位输入移位寄存器和每个模二加法器的连接关系。
一开始输入寄存器里全是0. 然后第一组k个bit输入，接着输出n个bit，再接着输入第二组bit，再输出第二组bit ...
一般来说，卷积码都是 (n,1,N) 的形式。在阅读了一些论文发现采用的都是 (2,1,N) 的形式，如(2,1,3),(2,1,6)等 （为什么）
很明显，当k=1时，每一个bit都要编码成n个bit去传输，流量 * n. 所以n不能太大，2、3可能就已经是极限。
libcorrect 的编码实现
我们可以对 https://github.com/quiet/libcorrect 的源码做分析。
// \src\convolutional\encode.c
...
size_t correct_convolutional_encode(correct_convolutional *conv,
const uint8_t *msg,
size_t msg_len,
uint8_t *encoded) {
...
for (size_t i = 0; i < 8 * msg_len; i++) {
// shiftregister has oldest bits on left, newest on right
shiftregister <<= 1;
shiftregister |= bit_reader_read(conv->bit_reader, 1);
shiftregister &= shiftmask;
// shift most significant bit from byte and move down one bit at a time
// - 移位寄存器左移，留出空位（右侧最低位）存储新的bit。旧bit在最高位通过掩码shiftmask完成删除。 shiftmask = (1 << conv->order) - 1;
// we do direct lookup of our convolutional output here
// all of the bits from this convolution are stored in this row
unsigned int out = conv->table[shiftregister];
bit_writer_write(conv->bit_writer, out, conv->rate);
// 注意到完成多次模二加法（异或）也是需要时间的,改用查表即可。预先将结果放在table里即可。
}
注意到上面代码中的 *conv ，是一个卷积对象，我们可以进入其头文件查看相关的定义。
// \include\correct\convolutional\convolutional.h
struct correct_convolutional {
const unsigned int *table; // size 2**order
// 空间换时间，因为是N个bit，所以对应2^N个空间
size_t rate; // e.g. 2, 3...
// 明显的，这里的rate 指的是 (n,1,N) 中的n, 即模二加法器的个数 或是每次编码的bit数
size_t order; // e.g. 7, 9...
// 明显的, 这里的order 指的是 (n,1,N) 中的N，即状态寄存器的个数。又因为
unsigned int numstates; // 2**order
bit_writer_t *bit_writer;
bit_reader_t *bit_reader;
// 读写操作
...
};
考虑如何预填写table。
// src\convolutional\lookup.c
void fill_table(unsigned int rate,
unsigned int order,
const polynomial_t *poly, // 每个模二加法器的输入位关联关系可以用一个多项式来表示，
unsigned int *table) {
for (shift_register_t i = 0; i < 1 << order; i++) { // N位bit从全0到全1，用i循环来表示
unsigned int out = 0;
unsigned int mask = 1;
for (size_t j = 0; j < rate; j++) {
out |= (popcount(i & poly[j]) % 2) ? mask : 0;
/*
注意到模二加法器的多项式本质上是一个系数只有0和1的式子
所以我们可以用一个二进制串（整数）来表示这个多项式
那么rate(n)个加法器对应着n个整数，存储在poly[]数组里
tmp = i&poly[j]
tmp 表示i状态对第j个模二加法器运算后的每一位串联的结果
但是我们想要的是每一位的异或，所以本质上还是要tmp的每一位异或起来
可以统计tmp中1的个数，若为偶数个则异或结果为0.
统计个数可以用popcount函数。这是一个魔法函数,能O(1)算出来。
利用mask放到out对应的位上。从低位到高位，依次对应的是j个加法器。
*/
mask <<= 1;
}
table[i] = out;
}
}
这说明这里实现的是一个（n,1,N）的卷积码编码。
树状图 网格图
树状图与网格图可以直观的体现所有码字的可能性，更可以帮助设计解码算法。
由于k=1，每次新输入一个bit，取值只能为0或1，所以我们可以将 前N-1个 寄存器串联看成一个状态节点，根据新输入的不同可得两个分叉，分别对应两个新的状态节点... 如此往复，可以构造出一个二叉状态树。(其实是每次输入k个bit，对应一个节点有 个分叉 )
以(2,1,3) 卷积码为例
如上图，寄存器初始状态全为0，所以状态根节点a=00.
如果此时输入的新bit为0，则下一步状态节点还是a=00 ，但如果输入的是1，则下一步状态节点就变成b=01.（从保存数据最旧的寄存器开始看，或者说从右往左记录为状态） 同理类推。因为是前N-1个，所以总共可能出现的状态就 种，之后的状态必定是循环回去了。
注意上图的树边，所标记的数字表示的是输出。即在当前这个状态下，根据新输入bit的不同而输出的不同。
例如a=00状态时，输入的新比特为0，三个寄存器全为0的输出是"00"。 再例如状态b=01，如果新比特输入的是0 （即010），输出是10；若新比特输入的是1（即011），输出的是01。（输出从左往右看，这是根据加法器编号从小到大来看的）。
同理，我们只需要保证每个状态以及其后续变化都出现过就行了，所以像树的上方递归3层的a状态可以省略不画，因为本质上是一样的。
我们可以将同种状态剥离合并（同状态的后续变化过程与之前状态无关），画成网格形式。
网格图内每一次的状态变化被称为“一节”。像右边的红框内每一次状态可能变化都是一样的，被称为稳态。根据网格图可以进行编码。如输入的bit依次是1100，则经过状态分别是abdcb，输出11010100。
译码
卷积码有多种译码算法，如维特比译码（Viterbi decoding algorithm)，序列译码，门限译码等。其中维特比译码性能是接近最优的，但实现起来也很复杂。 libcorrect 也是用的维特比译码算法，这里着重介绍这个算法。
先考虑网格图译码过程。例如接受的码字是11010100，我们可以根据网格图进行对比。可以直接得出结果。
如果出现误码，我们可以选择与接收序列更接近的一种变化继续下去。但也可能出现所有变化都等距的情况（例如收到的是10，两个变化分别是00和11）。一种朴素的想法是：考虑往后几步的多种变化，再选最小距离的。然而这会导致延时与性能问题，故引入到维特比译码算法。
维特比算法是基于最大似然译码算法（通过概率推导出应该是哪个码最接近），（通过一阵复杂的概率公式推导得出）在这里它等效于最小距离译码。
记状态变化的路径量度（可理解成一条边的权值）为该路径输出与收到序列之间的距离。（一般是汉明距离）。整条路径的路径量度是各边的权值和。
维特比算法是一种类似 动态规划思想 的算法。本质上是用动态规划在这个特殊图上求最短路问题。
- 初始状态为
a=00 - 当前是第
i步译码，前i-1步译码后停留在状态j时的最小路径度量值是f[i-1][j] - 考虑
f[i][j]的变化。选择一个可以使f[i][j]值最小的状态j'，由其状态j'变化而来。 - 每种状态都确定好之前由哪一个状态变化而来，也意味着有多少个状态就有多少个不同的路径。这些路径被称为“幸存路径”
- 若幸存路径中有相同重叠的部分，则可以直接输出这部分（作为部分译码结果）。
- 若译码未结束返回到第2步。若译码结束且有多种相同度量值的路径可供选择，则随机选择一种。否则选择度量值最小的那个路径。
例如：
- 接收的第一段是11，一开始状态 a，可能的两种变化分别是：
- 输出00 到状态a （aa，累计路径度量 = 2）
- 输出11 到状态b （ab，累计路径度量 = 0）
注意到这里两条路径(aa,ab)都是“幸存路径”，且没有重合部分，所以继续译码。
- 接收的第二段是01，在第一步之后的两个幸存路径分别对应状态是aa,ab.
- aa状态
- 输出00，到状态a（aaa，累计路径度量=2+1=3）
- 输出11，到状态b（aab，累计路径度量=2+1=3）
- ab状态
- 输出10，到状态c（abc， 累计路径度量=0+2=2）
- 输出01，到状态d（abd，累计路径度量=0+0=0）
如下图左侧
到译码第三段时，可以发现：f[3][a]即第三段译码后状态是a的可能性有两种，即 aaa-a 或 abc-a，分别对应路径度量值是4和3。所以这里保留abc-a这条路路径，而不是aaa-a。
同理，其他状态经过同样操作后，剩余的幸存路径都用红色标出。他们有重合部分即最开始的 a-b，对应的译码结果是1。而最开始的a-a 路径分支就被舍弃了。
到译码第四段 接收到10时，也有如下变化，最后每种状态保留一条幸存路径。注意，在上一步输出译码为1后，这四条幸存路径并没有新的重合部分。 所以需要继续读取并进行译码。
最后结果如下：
注意到最后四条路径里以d状态结尾的转移路径的度量值最低，所以选择这条路径做为译码结果。即11001111. 并且这也可以推出是第4段和第7段产生了误码。
