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 的二維數組暫存狀態(tài)信息）
- n級輸出移位寄存器 和 n個模二加法器 （每一級輸出寄存器對應一個加法器）
如上圖，每個異或（模二加法器）對應的輸入是輸入序列（N組k級寄存器）中的某些特定位性雄。這些位是在編碼中固定的秒旋。卷積碼的生成矩陣就是在描述 N * K 位輸入移位寄存器和每個模二加法器的連接關系。
一開始輸入寄存器里全是0. 然后第一組k個bit輸入煤蚌，接著輸出n個bit细卧，再接著輸入第二組bit，再輸出第二組bit ...
一般來說蜘犁，卷積碼都是 (n,1,N) 的形式止邮。在閱讀了一些論文發(fā)現采用的都是 (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甚脉，即狀態(tài)寄存器的個數铆农。又因為
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循環(huán)來表示
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狀態(tài)對第j個模二加法器運算后的每一位串聯的結果
但是我們想要的是每一位的異或，所以本質上還是要tmp的每一位異或起來
可以統(tǒng)計tmp中1的個數猾昆，若為偶數個則異或結果為0.
統(tǒng)計個數可以用popcount函數骡苞。這是一個魔法函數,能O(1)算出來。
利用mask放到out對應的位上么抗。從低位到高位，依次對應的是j個加法器螟加。
*/
mask <<= 1;
}
table[i] = out;
}
}
這說明這里實現的是一個（n,1,N）的卷積碼編碼捆探。
樹狀圖 網格圖
樹狀圖與網格圖可以直觀的體現所有碼字的可能性，更可以幫助設計解碼算法曾雕。
由于k=1助被，每次新輸入一個bit，取值只能為0或1搔弄，所以我們可以將 前N-1個 寄存器串聯看成一個狀態(tài)節(jié)點丰滑，根據新輸入的不同可得兩個分叉，分別對應兩個新的狀態(tài)節(jié)點... 如此往復炫刷，可以構造出一個二叉狀態(tài)樹浑玛。(其實是每次輸入k個bit，對應一個節(jié)點有 個分叉 )
以(2,1,3) 卷積碼為例
如上圖失晴，寄存器初始狀態(tài)全為0拘央，所以狀態(tài)根節(jié)點a=00.
如果此時輸入的新bit為0，則下一步狀態(tài)節(jié)點還是a=00 拆又，但如果輸入的是1栏账，則下一步狀態(tài)節(jié)點就變成b=01.（從保存數據最舊的寄存器開始看，或者說從右往左記錄為狀態(tài)） 同理類推竖般。因為是前N-1個茶鹃，所以總共可能出現的狀態(tài)就 種闭翩，之后的狀態(tài)必定是循環(huán)回去了。
注意上圖的樹邊兑障，所標記的數字表示的是輸出流译。即在當前這個狀態(tài)下肤无，根據新輸入bit的不同而輸出的不同宛渐。
例如a=00狀態(tài)時眯搭，輸入的新比特為0鳞仙，三個寄存器全為0的輸出是"00"笔时。 再例如狀態(tài)b=01，如果新比特輸入的是0 （即010）借笙，輸出是10较锡；若新比特輸入的是1（即011）蚂蕴，輸出的是01。（輸出從左往右看熔号，這是根據加法器編號從小到大來看的）鸟整。
同理，我們只需要保證每個狀態(tài)以及其后續(xù)變化都出現過就行了吃嘿，所以像樹的上方遞歸3層的a狀態(tài)可以省略不畫兑燥，因為本質上是一樣的琴拧。
我們可以將同種狀態(tài)剝離合并（同狀態(tài)的后續(xù)變化過程與之前狀態(tài)無關）蚓胸，畫成網格形式。
網格圖內每一次的狀態(tài)變化被稱為“一節(jié)”扔枫。像右邊的紅框內每一次狀態(tài)可能變化都是一樣的短荐，被稱為穩(wěn)態(tài)。根據網格圖可以進行編碼痕貌。如輸入的bit依次是1100糠排，則經過狀態(tài)分別是abdcb，輸出11010100哺徊。
譯碼
卷積碼有多種譯碼算法乾闰，如維特比譯碼（Viterbi decoding algorithm)汹忠，序列譯碼，門限譯碼等谣膳。其中維特比譯碼性能是接近最優(yōu)的铅乡，但實現起來也很復雜。 libcorrect 也是用的維特比譯碼算法花履，這里著重介紹這個算法挚赊。
先考慮網格圖譯碼過程荠割。例如接受的碼字是11010100，我們可以根據網格圖進行對比夺克『啃啵可以直接得出結果哟忍。
如果出現誤碼陷寝，我們可以選擇與接收序列更接近的一種變化繼續(xù)下去盼铁。但也可能出現所有變化都等距的情況（例如收到的是10尝偎，兩個變化分別是00和11）致扯。一種樸素的想法是：考慮往后幾步的多種變化，再選最小距離的鲤看。然而這會導致延時與性能問題耍群，故引入到維特比譯碼算法蹈垢。
維特比算法是基于最大似然譯碼算法（通過概率推導出應該是哪個碼最接近），（通過一陣復雜的概率公式推導得出）在這里它等效于最小距離譯碼溉瓶。
記狀態(tài)變化的路徑量度（可理解成一條邊的權值）為該路徑輸出與收到序列之間的距離谤民。（一般是漢明距離）张足。整條路徑的路徑量度是各邊的權值和。
維特比算法是一種類似 動態(tài)規(guī)劃思想 的算法嗅榕。本質上是用動態(tài)規(guī)劃在這個特殊圖上求最短路問題吵聪。
- 初始狀態(tài)為
a=00 - 當前是第
i步譯碼吟逝，前i-1步譯碼后停留在狀態(tài)j時的最小路徑度量值是f[i-1][j] - 考慮
f[i][j]的變化赦肋。選擇一個可以使f[i][j]值最小的狀態(tài)j'，由其狀態(tài)j'變化而來囱井。 - 每種狀態(tài)都確定好之前由哪一個狀態(tài)變化而來庞呕，也意味著有多少個狀態(tài)就有多少個不同的路徑。這些路徑被稱為“幸存路徑”
- 若幸存路徑中有相同重疊的部分地啰，則可以直接輸出這部分（作為部分譯碼結果）亏吝。
- 若譯碼未結束返回到第2步盏混。若譯碼結束且有多種相同度量值的路徑可供選擇，則隨機選擇一種止喷。否則選擇度量值最小的那個路徑启盛。
例如：
- 接收的第一段是11僵闯，一開始狀態(tài) a藤滥，可能的兩種變化分別是：
- 輸出00 到狀態(tài)a （aa，累計路徑度量 = 2）
- 輸出11 到狀態(tài)b （ab向图，累計路徑度量 = 0）
注意到這里兩條路徑(aa,ab)都是“幸存路徑”标沪，且沒有重合部分金句，所以繼續(xù)譯碼。
- 接收的第二段是01贞瞒，在第一步之后的兩個幸存路徑分別對應狀態(tài)是aa,ab.
- aa狀態(tài)
- 輸出00，到狀態(tài)a（aaa棕洋，累計路徑度量=2+1=3）
- 輸出11掰盘，到狀態(tài)b（aab簇抵，累計路徑度量=2+1=3）
- ab狀態(tài)
- 輸出10碟摆，到狀態(tài)c（abc， 累計路徑度量=0+2=2）
- 輸出01断盛，到狀態(tài)d（abd，累計路徑度量=0+0=0）
如下圖左側
到譯碼第三段時愉舔，可以發(fā)現：f[3][a]即第三段譯碼后狀態(tài)是a的可能性有兩種钢猛，即 aaa-a 或 abc-a，分別對應路徑度量值是4和3轩缤。所以這里保留abc-a這條路路徑命迈，而不是aaa-a。
同理火的，其他狀態(tài)經過同樣操作后壶愤，剩余的幸存路徑都用紅色標出。他們有重合部分即最開始的 a-b馏鹤，對應的譯碼結果是1。而最開始的a-a 路徑分支就被舍棄了湃累。
到譯碼第四段 接收到10時勃救，也有如下變化，最后每種狀態(tài)保留一條幸存路徑治力。注意蒙秒，在上一步輸出譯碼為1后，這四條幸存路徑并沒有新的重合部分宵统。 所以需要繼續(xù)讀取并進行譯碼税肪。
最后結果如下：
注意到最后四條路徑里以d狀態(tài)結尾的轉移路徑的度量值最低，所以選擇這條路徑做為譯碼結果。即11001111. 并且這也可以推出是第4段和第7段產生了誤碼益兄。
