糾錯編碼的核心設計思想是通過增加冗余信息，使得原始信息的編碼之間有足夠大的區別。

編碼距離

還記得蛋蛋表白的時候，信息為“我 喜 歡 你”四個字，為了防止女神聽不到，他添加了冗余信息。經過蛋蛋添加冗余后變為了“我 我 我 喜 喜 喜 歡 歡歡 你 你 你”，其實女神收到的信號為（我 我 餓 T x x 歡 花 歡 x x 里），其中x表示為鄰座大媽的霸氣的笑聲，女神是如何正確的捕捉到蛋蛋的意圖呢？顯然女神在這方面很有經驗，識破了蛋蛋重復三遍的伎倆，電光火石間，在她腦海里飛速搜索比對推理，得出一個通順而有意義的結論。換句話說，在女神的詞典中，有意義的語句全都列出來，發現跟蛋蛋發出聲音最相似的就是：“我我 我 喜 喜 喜 歡 歡 歡 你 你 你“

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

蛋蛋有4個信息，為00，01，10，11. 現在如何插入冗余呢？

首先想到的是重復法：

q 00 變為 00 00 00 00

q 01 變為 01 01 01 01

q 10 變為 10 10 10 10

q 11 變為 11 11 11 11

現在接收到信號 為 00 01 00 00， 我們發現跟這個信號最相似的是 00 00 00 00，距離為1.

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

解碼的時候，一個最暴力的方法就是一一比較接收到的信號和所有有效編碼之間的編碼距離，選擇編碼距離最小的。所以編碼距離的重要作用是可以指示編碼可以糾錯的bit個數。蛋蛋和阿呆住在不同的地方，相距為d，蛋蛋養了一群羊，阿呆也養了一群羊。羊會亂跑，顯然只要羊跑的距離小于d/2 距離，就可以判斷羊屬于蛋蛋還是阿呆。所以對糾錯碼而言，編碼距離為d，只要bit翻轉個數小于d/2，我們可以根據離得誰近就歸誰的原則去糾錯（趕羊回家）。

線性糾錯碼的基石——奇偶校驗（parity-Check）

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

阿姨檢查鈔票的行為叫做信號校驗，信號校驗的基本模型是：

對信號進行某種特定的處理后，得到期望的結果是為校驗通過，否則校驗失敗。

這里信號用表示，特定的處理用H表示，表示對信號y進行了處理。處理結果用CR表示。

在二進制的世界里，最基礎的校驗方法是奇偶校驗即parity-Check。

對于nbit 二進制信號:

例如長度為16的二進制數據：1000100111011011，其中1的個數為9，故CR = 1。

判斷信號里的1的個數為奇還是偶，有非常簡單的方法。在二進制里，有一種異或

(即xor)運算，符號為 ，運算方式先進行加法運算，然后運算結果對2取余數（mod（2）），或者更簡單的記憶為“相加不進位”：

圖1 異或運算表達式

可以驗證只要把二進制的每一個bit依次進行xor運算，奇數個bit 1的結果為1，偶數個bit 1的結果為0，與bit 0的個數無關。

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

利用奇偶校驗可以構造最簡單的校驗碼——單bit校驗碼SPC（即single bit parity check code）。

把長度為n的二進制信息，增加1 bit 變成y’，使得：

現在y’構成了y的單bit校驗碼。（a）又叫做奇偶校驗方程。

顯然，y’中任意一個bit如果發生bit反轉，無論從0到1，還是1到0，校驗方程 CR = 1 。

SPC 可以探知任意單bit的反轉。對于偶數個bit 反轉SPC無法探知。而且校驗方程并無法知道是bit反轉的位置，所以無法糾錯。

一個自然的想法是，增加SPC的個數，增加冗余的校驗信息。同一個bit被好幾個校驗方程保護，當它出現錯誤時候，就不會被漏掉。

后面的文章中，用 + 代替

校驗矩陣H和 生成矩陣G

蛋蛋的丈母娘，在女兒結婚前對未來女婿有一個要求列表，前五條是1）一定是博士學位，2）脾氣要好，3）人要長得帥，4）會做家務， 5）財政上交

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

多個校驗方程可以表示為校驗矩陣 H。有了H 就可以確定所有可能的編碼。

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

Hx^T= 0

x 就是合理的編碼。如果不滿足，x不屬于合理的編碼，認為在傳輸的過程中x出現了錯誤。

舉例：長度為4的信號，x(x_0 ,x_1 ,x_2,x_3),有2個校驗方程：

x_0+x_2=0

x_1+x_2+x_3=0

現在用 + 代替 ?，

可見，H矩陣里每一行可以表示一個校驗方程。行里的1的位置i表示信號中第i bit 參與校驗方程。

所有滿足奇偶校驗方程的x組成了一個編碼集合。一般來說，編碼長度為n bit，有r個線性獨立的校驗方程，則可以提供k = （n – r）個有效信息bit，和r個校驗bit。

對于線性分組編碼而言，原始信號u經過一定的線性變換可以生成糾錯碼c。完成冗余的添加。線性變換可以寫成矩陣的形式，這個矩陣就是生成矩陣G。

表示為，c =uG

c為 n bit 信號。u 為k bit 信號，G 為 k x n 大小的矩陣。由H 矩陣可以推導出生成矩陣G。