Question

Error Detection / Error Correction

“错误侦测”和“错误更正”。侦测较简单，更正较複杂。

有些时候，我们只需要侦测，不需要更正。例如网路传输，如果发现出错了，麻烦对方马上重传一次就好。例如身份证字号，最后一码是验证码，一方面避免卡号连续、一方面避免行政人员输入错误；如果输入错误，重新输入就好。侦测错误的演算法非常多，例如 Luhn Algorithm。

有些时候，我们必须要更正。例如 CD 光碟片，时间久了染料变质了，资料不正确，就必须更正资料。例如火星探勘太空船发送到地球的讯息，由于距离太远了，重传太花时间，必须直接更正。

Channel

天有不测风云，人有旦夕祸福。资料损毁变异怎麽办？

电脑世界当中，资料通常是经过传输而损毁。于是数学家想像有一个“通道”，宛如函数，一笔资料经过通道得到一笔资料，可能不变，可能出错。

数学家引入机率的概念、引入递增法化整为零的概念，令每一个位元有固定机率出错。现实生活有著千奇百怪的出错原因；数学家便设计了 各式各样的通道 ，儘量符合现实情况。

以下文章不谈通道，让事情单纯一点！

Encode / Decode

不像压缩与加密特别订立新名词，更正直接沿用旧名词。

“编码”是资料变码。“解码”是码变资料。码经过“通道”将有一定机率损毁变异。

“编码”是补强资料。“解码”是复原资料。

         encode
0010001 -------> 001000100100010010001
                           ↓ channel
0010001 <------- 001100110100010010000="" decode="" (detect="" correct)="" <="" pre="">

Repetition Code

以重複备份侦测错误、更正错误

资料损毁变异怎麽办？制作备份，有备无患。

原始资料：时今
备份资料：时令

发现错别字“今”，应该改成“令”。

前面假设备份资料绝对没问题。如果备份资料可能有问题呢？

时今　时令　时令
发现错别字“今”，应该改成“令”。

时令　时今　时今　时令
无法确定错别字。

时令　时今　时令　时今　时今　时今
错别字误判为“令”。

只要正确资料过半，就能正确修复。然而无论多少备份，仍有机会毁损达半，无法修复。我们只能多建立备份，避免憾事发生。

如果需要更细腻的结论，可以引入机率：设定毁损机率、计算修复机率。

Repetition Code

00110001 ---> 001100010011000100110001

电脑世界也有类似的演算法：原始资料重複数次。

此演算法有两种视角：备份资料放在原始资料尾端（主从、狭观）、各份资料相互支援（平等、宏观）。

电脑以位元为单位。针对一个特定位元，只要所有对应的位元，正确比错误多，即可正确地侦测错误、更正错误。

此演算法相当耗费记忆体空间、耗费处理时间。因此有人研发更好的演算法。

如果需要更细腻的结论，可以引入“通道”：设定毁损机率、计算修复机率。

编码：资料重複 N-1 次（一共 N 份），变成码。
解码：针对每个位元，找到所有对应位元（一共 N 个），投票过半者，推定为正解。

Hadamard Code

以最短距离来侦测错误、更正错误

资料长度为 N 个位元。一共 2^N 种资料。

码长度为 N+K 个位元。(N+K) 维空间，挑选 2^N 个相异座标点，当作码。自由规定资料与码的对应方式。

想要侦测错误、更正错误，最常见的手法是增加资料长度。因此此处的码长度（空间维度）略大于资料长度。

侦测错误：给定一个待测码，从 2^N 个码之中，找到相同的码。找不到就表示有错误。

更正错误：给定一个待测码，从 2^N 个码之中，找到差异最小、距离最近的那一个码，直接更正成那一个码。

我们在意的是：错误位元有几个？于是距离设为“相异位元的数目”，即“ Hamming Distance ”。距离是整数。

N=5 example:
          [0]   [0]                   [1]   [0]      
hamming   [1]   [1]         hamming   [1]   [0]      
distance( [1] , [0] ) = 2   distance( [1] , [0] ) = 5
          [1]   [0]                   [1]   [0]      
          [1]   [1]                   [1]   [0]      

          [1]   [1]                   [1]   [0]      
hamming   [1]   [1]         hamming   [1]   [0]      
distance( [0] , [0] ) = 0   distance( [0] , [1] ) = 5
          [1]   [1]                   [0]   [1]      
          [1]   [1]                   [0]   [1]      

码之间的距离越远，容忍越多错误！令码的两两距离皆大于等于 d，中点为分野，当 d 是偶数、奇数，即便错 d/2、(d-1)/2 个位元，仍可正确侦测；即便错 d/2-1、(d-1)/2 个位元，仍可完全修复。如果错太多，就误判了。

挑选 2^N 个座标点，只要令两两距离大于等于 d，就能容忍将近 d/2 个错误位元，正确侦测、完全修复！

增加码长度（空间维度），得拉开两两距离、增加 d、调整 d、调整容忍程度。代价是码变长，耗费记忆体空间、耗费处理时间。

编码：建立表格，2^N 种资料对应到 2^N 个座标点。
解码：穷举 2^N 个座标点，找到 Hamming 距离最小者。

Hadamard Code

利用“ Hadamard Matrix ”，N 个向量当作码，两两距离皆大于等于 N/2。证明交给读者。

HN = [HN/2 HN/2]
     [HN/2 HN/2]

H₂     H₄         H₈
[0 0]  [0 0 0 0]  [0 0 0 0 0 0 0 0]
[0 1]  [0 1 0 1]  [0 1 0 1 0 1 0 1]
       [0 0 1 1]  [0 0 1 1 0 0 1 1]
       [0 1 1 0]  [0 1 1 0 0 1 1 0]
                  [0 0 0 0 1 1 1 1]
                  [0 1 0 1 1 0 1 0]
                  [0 0 1 1 1 1 0 0]
                  [0 1 1 0 1 0 0 1]

通常扩充成 2N 个码。原本数值反转即得。

H₂         H₄                 H₈
[0 0|1 1]  [0 0 0 0|1 1 1 1]  [0 0 0 0 0 0 0 0|1 1 1 1 1 1 1 1]
[0 1|1 0]  [0 1 0 1|1 0 1 0]  [0 1 0 1 0 1 0 1|1 0 1 0 1 0 1 0]
           [0 0 1 1|1 1 0 0]  [0 0 1 1 0 0 1 1|1 1 0 0 1 1 0 0]
           [0 1 1 0|1 0 0 1]  [0 1 1 0 0 1 1 0|1 0 0 1 1 0 0 1]
                              [0 0 0 0 1 1 1 1|1 1 1 1 0 0 0 0]
                              [0 1 0 1 1 0 1 0|1 0 1 0 0 1 0 1]
                              [0 0 1 1 1 1 0 0|1 1 0 0 0 0 1 1]
                              [0 1 1 0 1 0 0 1|1 0 0 1 0 1 1 0]

码长度、码数量皆已确认！那麽资料长度呢？

引入线性组合的概念，找到这些向量的 basis。基底向量的个数，设定成资料长度；一笔资料套用线性组合求得对应的码！

H₂     H₄       H₈
basis  basis    basis       (H₄ example)
[1 1]  [1 1 1]  [1 1 1 1]        encode              encode      
[1 0]  [1 1 0]  [1 1 1 0]   101 -------> 0101   111 -------> 1001
       [1 0 1]  [1 1 0 1]   [1 1 1] [1]   [0]   [1 1 1] [1]   [1]
       [1 0 0]  [1 1 0 0]   [1 1 0] [0] = [1]   [1 1 0] [1] = [0]
                [1 0 1 1]   [1 0 1] [1]   [0]   [1 0 1] [1]   [0]
                [1 0 1 0]   [1 0 0]       [1]   [1 0 0]       [1]
                [1 0 0 1]
                [1 0 0 0]

资料长度呈线性成长，码长度却呈指数成长，付出代价极大！

矩阵 | 码　 | 基底 | 资料 | 码　 | 两两   | 侦测 | 更正 | 编码率
大小 | 数量 | 向量 | 长度 | 长度 | 距离   | 错误 | 错误 | 资料与码的比例
-----|------|------|------|------|--------|------|------|---------------
N=2  | 4 种 | 2 个  | 2    | 2    | 至少 1  | 0    | 0    | 2/2（毫无功能）
N=4  | 8 种 | 3 个  | 3    | 4    | 至少 2  | 1    | 0    | 3/4（只能侦测）
N=8  | 16 种 | 4 个  | 4    | 8    | 至少 4  | 2    | 1    | 4/8
N=16 | 32 种 | 5 个  | 5    | 16   | 至少 8  | 4    | 3    | 5/16
N=32 | 64 种 | 6 个  | 6    | 32   | 至少 16 | 8    | 7    | 6/32

实务上 N 都很小，因此不必研发特别的解码演算法。解码採用试误法，简单而迅速。

编码：预先建立所有码的 basis。资料经过线性组合得到码。
解码：穷举所有资料并且求得码，找到 Hamming 距离最小者。
　　　一旦发现 Hamming 距离小于 N/2，即可立即结束，推定为正解。

由于付出代价极大，实务上不採用此演算法。

Reed-Muller Code

http://homepages.math.uic.edu/~leon/mcs425-s08/handouts/Hadamard_codes.pdf

以 Hadamard Code 的基底向量作为素材，两两内积（甚至三三内积、四四内积），构造更複杂的基底向量。

Hill Code（Under Construction!）

以备忘录侦测错误、更正错误

http://wdjoyner.org/papers/hill-vs-hamming.pdf

https://wdjoyner.files.wordpress.com/2016/08/hill-error-checking-notes-unpublished.pdf

原本文字长度 r
设定一组权重 a1...ar
把权重一次方、二次方、三次方、...、k 次方，得到 k 组权重
k 个 parity，是 k 个加权平均值

一种方便的设定方式是找到一个大矩阵，
其中每个子矩阵都有反矩阵，
如此就可以从中随意挑选一个矩阵来编码。

Hamming Code

以前后文侦测错误、更正错误

最简单的方法是：原始资料直接重複好几次。更聪明的方法是：补充说明，依照前后文推敲正文。

资料：好人气
不知是否有错别字。

资料：好人气 青空万里 
发现错别字“人”，应该改成“天”。
发现错别字“青”，不过没关係。

Parity Check

电脑世界当中，由于物理电子电机已臻化境，网路线传输、无线传输、USB 传输、烧录光碟、读取光碟，资料毁损机率极低，只需容忍很少的错误位元。因此有人研发容忍程度极低、却非常节省空间时间的演算法。接下来介绍仅容忍一个错误位元的演算法，只能侦测错误，无法更正错误。

00110001 ---> 00110001   1 
0+0+1+1+0+0+0+1 =   1 (mod 2)

10101001 ---> 10101001   0 
1+0+1+0+1+0+0+1 =    0 (mod 2)

00110001   1 ✔
0+0+1+1+0+0+0+1+   1 = 0 (mod 2)

10101101   0 ✖
1+0+1+0+1+1+0+1+   0 = 1 (mod 2)

编码：资料所有位元 xor（先求和、再模二），
　　　得到一个位元（称作 parity），添在资料尾端。
侦测：码所有位元 xor，等于 0 则对，等于 1 则错。

错零个位元、错一个位元，保证正确侦测错误；错两个位元以上，不保证正确侦测错误。无法更正错误。

最后附上一个益智问题：

阵列裡放入 1 到 100 的正整数，但是少了一个。请找出少了哪一个？
使用 Counting Sort ，时间複杂度极低，但是空间複杂度极高。
有没有更节省记忆体的方法呢？

UVa 541

Hamming Code：编码

接下来介绍仅容忍一个错误位元的演算法，可以更正错误。

增为三个 parity。这是经过精心设计的，有很强的数学性质。

写成代数式子：

x4 = x0 + x1 + x2
x5 = x0 + x1 + x3
x6 = x0 + x2 + x3

范例：

0123  encode  0123   456 
0000 -------> 0000   000 
1111 -------> 1111   111 
0011 -------> 0011   110 
1010 -------> 1010   010 

Hamming Code：所有的码

从属关係改成平等关係。

x0 + x1 + x2 + x4 = 0
x0 + x1 + x3 + x5 = 0
x0 + x2 + x3 + x6 = 0

联立所有式子，所有解就是所有码。

{ x0 + x1 + x2 + x4 = 0
{ x0 + x1 + x3 + x5 = 0
{ x0 + x2 + x3 + x6 = 0

                [x0]
                [x1]
[1 1 1 0 1 0 0] [x2]   [0]
[1 1 0 1 0 1 0] [x3] = [0]
[1 0 1 1 0 0 1] [x4]   [0]
                [x5]
                [x6]
       H         x   =  0

Hamming Code：码的两两距离

证明过程非常奇葩，绝非常人所能及。看看就好。

一、Hx=0。码即解。

                [0]        |                 [1]         
                [0]        |                 [0]         
[1 1 1 0 1 0 0] [1]   [0]  | [1 1 1 0 1 0 0] [1]   [0]   
[1 1 0 1 0 1 0] [1] = [0]  | [1 1 0 1 0 1 0] [0] = [0]   
[1 0 1 1 0 0 1] [1]   [0]  | [1 0 1 1 0 0 1] [0]   [0]   
                [1]        |                 [1]         
                [0]        |                 [0]         
       H         x   =  0  |        H         x   =  0   

二、两个码的距离，等于，两个码相加后有几个 1。

          [0]   [1]           [0]   [1]              [0]   [1]  
          [0]   [0]     how   [0]   [0]              [0]   [0]  
hamming   [1]   [1]     many  [1]   [1]     hamming  [1]   [1]  
distance( [1] , [0] ) = 1s? ( [1] + [0] ) = weight ( [1] + [0] )
          [1]   [0]           [1]   [0]              [1]   [0]  
          [1]   [1]           [1]   [1]              [1]   [1]  
          [0]   [0]           [0]   [0]              [0]   [0]  

三、运用矩阵运算的线性、运用模数运算的封闭性：两个解相加，恰是，某一个解！所有解两两相加，恰是，所有解（剔除零向量）！ 所有解的两两距离，变成，所有解（剔除零向量）数 1。

[0]   [1]   [1]
[0]   [0]   [0]
[1]   [1]   [0]
[1] + [0] = [1]  会是 Hx=0 的某一个解
[1]   [0]   [1]
[1]   [1]   [0]
[0]   [0]   [0]

四、运用线性组合：一个解的 1，变成，1 所对应的矩阵向量，相加等于零向量。

                [0]
   ↓   ↓   ↓    [1]←
[1 1 1 0 1 0 0] [0]    [0]
[1 1 0 1 0 1 0] [1]← = [0]
[1 0 1 1 0 0 1] [0]    [0]
                [1]←
                [0]
       H         x   =  0

有两个解（码）距离为 3。
有一个解恰有三个 1。
矩阵 H 有三个向量相加是零向量。

五、採用试误法，尝试各种距离。採用反证法，证明各种距离不成立。 运用矩阵向量，判断码的距离。

有两个码（解）距离为 0：码皆相异，显然不成立。
有两个码（解）距离为 1：某一个解仅有一个 1，某一个矩阵向量是零向量。
　　　　　　　　　　　 但是矩阵没有零向量。不成立。
有两个码（解）距离为 2：某一个解仅有两个 1，某两个矩阵向量相加等于零向量。
　　　　　　　　　　　 但是矩阵向量两两相加都不是零向量。不成立。
有两个码（解）距离为 3：仿前。确实有三个向量相加是零向量。成立。

故码的两两距离皆大于等于 3。错 1 个位元，仍可完全修复。

六、码的两两距离大于等于 n，变成，矩阵向量没有零向量、两两相加没有零向量、三三相加没有零向量、……、n-1n-1 相加没有零向量，而 nn 相加可得零向量。

也就是说，仔细设计 parity 式子，得以调整容忍程度。

Hamming Code：解码

试误法是穷举 2^N 种资料可能性，N 是资料长度。以下介绍更快的演算法。

x 是正确的码。x+e 是毁损的码，e 是误差。
Hx = 0                    前面谈过
H(x+e) = Hx + He = He     H(x+e) 和 He 的结果恰好一样

因为只容许一个错误位元，
所以 e 只能是这 8 个向量的其中一种：
[0] [1] [0] [0] [0] [0] [0] [0]
[0] [0] [1] [0] [0] [0] [0] [0]
[0] [0] [0] [1] [0] [0] [0] [0]
[0] [0] [0] [0] [1] [0] [0] [0]
[0] [0] [0] [0] [0] [1] [0] [0]
[0] [0] [0] [0] [0] [0] [1] [0]
[0] [0] [0] [0] [0] [0] [0] [1]
 0  e0  e1  e2  e3  e4  e5  e6
至于其他情况，无法保证正确修复，不讨论。

预先计算 He，代入 8 种可能性。
H0  He0 He1 He2 He3 He4 He5 He6
[0] [1] [1] [1] [0] [1] [0] [0]
[0] [1] [1] [0] [1] [0] [1] [0]
[0] [1] [0] [1] [1] [0] [0] [1]
以线性组合的观点，其实就是 H 的各个向量。

解码。给定一个码 x+e，计算 H(x+e)，即 He。判断 He 是 H0 He0 ... He6 当中哪一个，就知道 e 是多少，就知道错误位元。

(example 1)

      encode           channel           decode
1111 -------> 1111   111 --------> 1110   111 -------> ?

                [1]                  [0]
                [1]                  [0]
[1 1 1 0 1 0 0] [1]   [0]            [0]
[1 1 0 1 0 1 0] [0] = [1]   =>   e = [1]   =>   bit x3 is wrong.
[1 0 1 1 0 0 1] [1]   [1]            [0]
                [1]                  [0]
                [1]                  [0]
       H       (x+e)= He3

(example 2)

      encode           channel           decode
1111 -------> 1111   111 --------> 1111   110 -------> ?

                [1]                  [0]
                [1]                  [0]
[1 1 1 0 1 0 0] [1]   [0]            [0]
[1 1 0 1 0 1 0] [1] = [0]   =>   e = [0]   =>   bit x6 is wrong.
[1 0 1 1 0 0 1] [1]   [1]            [0]
                [1]                  [0]
                [0]                  [1]
       H       (x+e)= He6

(example 3)

      encode           channel           decode
1111 -------> 1111   111 --------> 1111111 -------> ?

                [1]                  [0]
                [1]                  [0]
[1 1 1 0 1 0 0] [1]   [0]            [0]
[1 1 0 1 0 1 0] [1] = [0]   =>   e = [0]   =>   all right!
[1 0 1 1 0 0 1] [1]   [0]            [0]
                [1]                  [0]
                [1]                  [0]
       H       (x+e)= H0

编码：三个 parity 式子。
　　　分别计算 parity，添在资料尾端。
解码：三个 parity 式子，形成矩阵 H。
　　　码代入 H。若为 0，则正确。
　　　若对应到 H 的向量，则错误；错误位元编号即是向量编号。

硬体设备已经内建 Hamming Code 的电路，其实没有必要用程式语言实作。

Hamming Code：其他性质

画成图论的二分图（Bipartite Graph）。

画成集合论的文氏图（Venn Diagram）。

调动位元顺序、矩阵直行顺序，让横列逐步右挪。更好编码。

                [x0]        |                 [x4]      
                [x1]        | row right shift [x5]      
[1 1 1 0 1 0 0] [x2]   [0]  | [1 0 1 1 1 0 0] [x2]   [0]
[1 1 0 1 0 1 0] [x3] = [0]  | [0 1 0 1 1 1 0] [x1] = [0]
[1 0 1 1 0 0 1] [x4]   [0]  | [0 0 1 0 1 1 1] [x0]   [0]
                [x5]        |                 [x3]      
                [x6]        |                 [x6]      
                            |
0123  encode  0123   456       | 0123  encode     45 2103   6 
0000 -------> 0000   000       | 0000 ------->    00 0000   0 
1111 -------> 1111   111       | 1111 ------->    11 1111   1 
0011 -------> 0011   110       | 0011 ------->    11 1001   0 
1010 -------> 1010   010       | 1010 ------->    01 1010   0 

调动位元顺序、矩阵直行顺序，让直行由小到大。更好解码。

                [x0]        |  lexico order   [x6]      
                [x1]        |  ------------>  [x5]      
[1 1 1 0 1 0 0] [x2]   [0]  | [0 0 0 1 1 1 1] [x3]   [0]
[1 1 0 1 0 1 0] [x3] = [0]  | [0 1 1 0 0 1 1] [x4] = [0]
[1 0 1 1 0 0 1] [x4]   [0]  | [1 0 1 0 1 0 1] [x2]   [0]
                [x5]        |                 [x1]      
                [x6]        |                 [x0]      

推广位元数量、矩阵大小。码的两两距离依然皆大于等于 3，依然只容许一个错误位元。

资料长度呈指数成长，parity 数量仅呈线性成长，代价锐减！

3 x 2³-1       4 x 2⁴-1       5 x 2⁵-1
[0 0 0     1]  [0 0 0     1]  [0 0 0     1]
[0 1 1 ... 1]  [0 0 0     1]  [0 0 0     1]
[1 0 1     1]  [0 1 1 ... 1]  [0 0 0 ... 1]
               [1 0 1     1]  [0 1 1     1]
                              [1 0 1     1]

7bit 补足为 8bit = 1byte，补入 Parity Check。更好储存。

x4 = x0 + x1 + x2     | x4 = x0 + x1 + x2
x5 = x0 + x1 + x3     | x5 = x0 + x1 + x3
x6 = x0 + x2 + x3     | x6 = x0 + x2 + x3
                      | x7 = x0 + x1 + x2 + x3 + x4 + x5 + x6
                      |
0123  encode  0123   456 | 0123  encode  0123   4567 
0000 -------> 0000   000 | 0000 -------> 0000   0000 
1111 -------> 1111   111 | 1111 -------> 1111   1111 
0011 -------> 0011   110 | 0011 -------> 0011   1100 
1010 -------> 1010   010 | 1010 -------> 1010   0101 

LDPC Code（Low-density Parity-check Code）

自由设计 parity，令矩阵稀疏。

x0 + x1 + x2 + x3 + x5 + x7 + x9 = 0
x0 + x2 + x3 + x6 + x7 + x8 + x9 = 0
x1 + x3 + x7 = 0
x0 + x4 + x6 + x7 + x8 + x9 = 0
x2 + x3 + x4 + x6 + x8 = 0

                      [x0]
                      [x1]
[1 1 1 1 0 1 0 1 0 1] [x2]   [0]
[1 0 1 1 0 0 1 1 1 1] [x3]   [0]
[0 1 0 1 0 0 0 1 0 0] [x4] = [0]
[1 0 0 0 1 0 1 1 1 1] [x5]   [0]
[0 0 1 1 1 0 1 0 1 0] [x6]   [0]
                      [x7]
                      [x8]
                      [x9]
          H            x   =  0

表示成二分图。

解码。自由设计之后，缺乏数学性质。求最佳解是 NP-Hard 问题，只好求近似解。其中一种演算法：Belief Propagation Decoding，採用 Iterative Method，用二分图的一侧算出另一侧，两侧交替计算，直到收敛为止。有兴趣的读者请自行研究。

简易范例： http://sigpromu.org/ldpc/

LDPC Code 是当前“资料与码的比例”最高的演算法，节省空间与时间，非常实用！例如无线通讯 Wi-Fi (IEEE 802.11)、WiMAX (IEEE 802.16) 就有使用。

由于硬体设备已经内建 LDPC Code 的电路，其实没有必要用程式语言实作。

Reed-Solomon Code（Under Construction!）

Cyclic Redundancy Check（CRC）

资料看作馀数多项式，係数模二。

11100010 <-> x⁷ + x⁶ + x⁵ + x

两造事先约定一个质式，作为除数。

11000101          <-> x⁷ + x⁶ + x² + 1
1100000001111     <-> x¹² + x¹¹ + x³ + x² + x + 1
11000000000100001 <-> x¹⁶ + x¹⁵ + x⁵ + 1

编码：资料尾端补零，数量是除数最高次方。实施长除法。馀数当作 parity，添在原始资料尾端。

11100010 ---> 11100010   0010111 

11100010   0000000 ÷ 11000101 = 10111011 ...    0010111 

11100010   0000000 
11000101        1
--------------- 
 01001110       
 00000000       0
--------------- 
  10011100      
  11000101      1
--------------- 
   10110010     
   11000101     1
--------------- 
    11101110    
    11000101    1
--------------- 
     01010110   
     00000000   0
--------------- 
      10101100  
      11000101  1
--------------- 
       11010010 
       11000101 1
--------------- 
           0010111 

侦测：码除以除数。整除即正确，不整除即错误。

11100010   0010111 ✔
11100010   0010111 ÷ 11000101 = 0

毁损的位元，跟除数不一样，侦测结果就正确。

UVa 128

Damm Algorithm

【待补文字】

Reed-Solomon Code

http://www.math.umn.edu/~garrett/coding/Overheads/19_hamming_bch.pdf

BCH Code（Under Construction!）

BCH Code（Bose-Chaudhuri-Hochquenghem Code）

http://w3.math.sinica.edu.tw/math_media/d184/18404.pdf

http://www.aqdi.com/bch.pdf

更正多个错误。

要增加距离，就让矩阵向量四四相加不是零向量、五五相加不是零向量、……。

手法是套用“ Finite Field ”，延长每个向量，补入奇数次方。

编码：算好 parity，添在尾端。

解码：解馀数多项式方程式。穷举法。因式分解。

Convolution Code（Under Construction!）

Convolution Code

引入“ Hidden Markov Model ”的概念，画成状态转移图。

解码，即是找到最好的路径，Viterbi Algorithm。有人把动态规划的过程图，叫做 Trellis Diagram。

Turbo Code