線性糾錯(cuò)碼的基石——奇偶校驗(yàn)

糾錯(cuò)編碼的核心設(shè)計(jì)思想是通過(guò)增加冗余信息，使得原始信息的編碼之間有足夠大的區(qū)別。

編碼距離

還記得蛋蛋表白的時(shí)候，信息為“我 喜 歡 你”四個(gè)字，為了防止女神聽不到，他添加了冗余信息。經(jīng)過(guò)蛋蛋添加冗余后變?yōu)榱恕拔?我 我 喜 喜 喜 歡 歡歡 你 你 你”，其實(shí)女神收到的信號(hào)為（我 我 餓 T x x 歡 花 歡 x x 里），其中x表示為鄰座大媽的霸氣的笑聲，女神是如何正確的捕捉到蛋蛋的意圖呢？顯然女神在這方面很有經(jīng)驗(yàn)，識(shí)破了蛋蛋重復(fù)三遍的伎倆，電光火石間，在她腦海里飛速搜索比對(duì)推理，得出一個(gè)通順而有意義的結(jié)論。換句話說(shuō)，在女神的詞典中，有意義的語(yǔ)句全都列出來(lái)，發(fā)現(xiàn)跟蛋蛋發(fā)出聲音最相似的就是：“我我 我 喜 喜 喜 歡 歡 歡 你 你 你“

女神的詞典可以看成所有可能編碼的集合，如何衡量這個(gè)編碼集合中，容易混淆的程度呢？這個(gè)參數(shù)就是編碼距離。什么是距離呢，這里指的是漢明距離，指的是兩個(gè)信號(hào)之間有多少bit 不同。比如信號(hào)（0，1，1）與（0，0，0）的距離為2，（1，1，1）與（0，0，0）的距離為3.

蛋蛋有4個(gè)信息，為00，01，10，11. 現(xiàn)在如何插入冗余呢？

首先想到的是重復(fù)法：

q 00 變?yōu)?00 00 00 00

q 01 變?yōu)?01 01 01 01

q 10 變?yōu)?10 10 10 10

q 11 變?yōu)?11 11 11 11

現(xiàn)在接收到信號(hào) 為 00 01 00 00， 我們發(fā)現(xiàn)跟這個(gè)信號(hào)最相似的是 00 00 00 00，距離為1.

一個(gè)編碼集合里，大家不一定是均勻分布的，有些編碼之間距離比較近，有些比較遠(yuǎn)，編碼距離指的是最近的兩個(gè)編碼之間距離。

解碼的時(shí)候，一個(gè)最暴力的方法就是一一比較接收到的信號(hào)和所有有效編碼之間的編碼距離，選擇編碼距離最小的。所以編碼距離的重要作用是可以指示編碼可以糾錯(cuò)的bit個(gè)數(shù)。蛋蛋和阿呆住在不同的地方，相距為d，蛋蛋養(yǎng)了一群羊，阿呆也養(yǎng)了一群羊。羊會(huì)亂跑，顯然只要羊跑的距離小于d/2 距離，就可以判斷羊?qū)儆诘暗斑€是阿呆。所以對(duì)糾錯(cuò)碼而言，編碼距離為d，只要bit翻轉(zhuǎn)個(gè)數(shù)小于d/2，我們可以根據(jù)離得誰(shuí)近就歸誰(shuí)的原則去糾錯(cuò)（趕羊回家）。

線性糾錯(cuò)碼的基石——奇偶校驗(yàn)（parity-Check）

收錢的阿姨狐疑地拿起蛋蛋遞過(guò)來(lái)的皺巴巴的100塊錢，迎著燈光仔細(xì)打量過(guò)后，又取出了紫外線燈從頭到尾照了一下，終于把錢放進(jìn)錢盒子里，找了蛋蛋99塊5。阿姨擔(dān)心收到假幣，她檢查鈔票可不敢馬虎。

阿姨檢查鈔票的行為叫做信號(hào)校驗(yàn)，信號(hào)校驗(yàn)的基本模型是：

對(duì)信號(hào)進(jìn)行某種特定的處理后，得到期望的結(jié)果是為校驗(yàn)通過(guò)，否則校驗(yàn)失敗。

這里信號(hào)用表示，特定的處理用H表示，表示對(duì)信號(hào)y進(jìn)行了處理。處理結(jié)果用CR表示。

在二進(jìn)制的世界里，最基礎(chǔ)的校驗(yàn)方法是奇偶校驗(yàn)即parity-Check。

對(duì)于nbit 二進(jìn)制信號(hào):

例如長(zhǎng)度為16的二進(jìn)制數(shù)據(jù)：1000100111011011，其中1的個(gè)數(shù)為9，故CR = 1。

判斷信號(hào)里的1的個(gè)數(shù)為奇還是偶，有非常簡(jiǎn)單的方法。在二進(jìn)制里，有一種異或

(即xor)運(yùn)算，符號(hào)為 ，運(yùn)算方式先進(jìn)行加法運(yùn)算，然后運(yùn)算結(jié)果對(duì)2取余數(shù)（mod（2）），或者更簡(jiǎn)單的記憶為“相加不進(jìn)位”：

圖1 異或運(yùn)算表達(dá)式

可以驗(yàn)證只要把二進(jìn)制的每一個(gè)bit依次進(jìn)行xor運(yùn)算，奇數(shù)個(gè)bit 1的結(jié)果為1，偶數(shù)個(gè)bit 1的結(jié)果為0，與bit 0的個(gè)數(shù)無(wú)關(guān)。

所以，用 表示第bit i的值（0或1），有

利用奇偶校驗(yàn)可以構(gòu)造最簡(jiǎn)單的校驗(yàn)碼——單bit校驗(yàn)碼SPC（即single bit parity check code）。

把長(zhǎng)度為n的二進(jìn)制信息，增加1 bit 變成y’，使得：

現(xiàn)在y’構(gòu)成了y的單bit校驗(yàn)碼。（a）又叫做奇偶校驗(yàn)方程。

顯然，y’中任意一個(gè)bit如果發(fā)生bit反轉(zhuǎn)，無(wú)論從0到1，還是1到0，校驗(yàn)方程 CR = 1 。

SPC 可以探知任意單bit的反轉(zhuǎn)。對(duì)于偶數(shù)個(gè)bit 反轉(zhuǎn)SPC無(wú)法探知。而且校驗(yàn)方程并無(wú)法知道是bit反轉(zhuǎn)的位置，所以無(wú)法糾錯(cuò)。

一個(gè)自然的想法是，增加SPC的個(gè)數(shù)，增加冗余的校驗(yàn)信息。同一個(gè)bit被好幾個(gè)校驗(yàn)方程保護(hù)，當(dāng)它出現(xiàn)錯(cuò)誤時(shí)候，就不會(huì)被漏掉。

后面的文章中，用 + 代替

校驗(yàn)矩陣H和 生成矩陣G

蛋蛋的丈母娘，在女兒結(jié)婚前對(duì)未來(lái)女婿有一個(gè)要求列表，前五條是1）一定是博士學(xué)位，2）脾氣要好，3）人要長(zhǎng)得帥，4）會(huì)做家務(wù)， 5）財(cái)政上交

這樣，蛋蛋的丈母娘通過(guò)提出要求，就輕而易舉實(shí)現(xiàn)了對(duì)地球上所有男性同胞的一個(gè)劃分。每一條要求都是一個(gè)校驗(yàn)方程。什么樣的校驗(yàn)方程組，決定了這個(gè)男性同胞群到底有哪些人組成。

多個(gè)校驗(yàn)方程可以表示為校驗(yàn)矩陣 H。有了H 就可以確定所有可能的編碼。

對(duì)于所有x(〖x_0 ,x〗_1 ,x_2,x_3,x_4,x_5…)，只要滿足

Hx^T= 0

x 就是合理的編碼。如果不滿足，x不屬于合理的編碼，認(rèn)為在傳輸?shù)倪^(guò)程中x出現(xiàn)了錯(cuò)誤。

舉例：長(zhǎng)度為4的信號(hào)，x(x_0 ,x_1 ,x_2,x_3),有2個(gè)校驗(yàn)方程：

x_0+x_2=0

x_1+x_2+x_3=0

現(xiàn)在用 + 代替 ?，

可見，H矩陣?yán)锩恳恍锌梢员硎疽粋€(gè)校驗(yàn)方程。行里的1的位置i表示信號(hào)中第i bit 參與校驗(yàn)方程。

所有滿足奇偶校驗(yàn)方程的x組成了一個(gè)編碼集合。一般來(lái)說(shuō)，編碼長(zhǎng)度為n bit，有r個(gè)線性獨(dú)立的校驗(yàn)方程，則可以提供k = （n – r）個(gè)有效信息bit，和r個(gè)校驗(yàn)bit。

對(duì)于線性分組編碼而言，原始信號(hào)u經(jīng)過(guò)一定的線性變換可以生成糾錯(cuò)碼c。完成冗余的添加。線性變換可以寫成矩陣的形式，這個(gè)矩陣就是生成矩陣G。

表示為，c =uG

c為 n bit 信號(hào)。u 為k bit 信號(hào)，G 為 k x n 大小的矩陣。由H 矩陣可以推導(dǎo)出生成矩陣G。