# CS3031 編碼理論 Coding Theory
Reference:
* Ling, S., & Xing, C. *Coding Theory: A First Course*.
* [Guruswami, V., Rudra, A., & Sudan, M. *Essential Coding Theory*.](https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book)

Instructor: 鄧惟中 Teng, Wei-Chung
###### tags: `TaiwanTech`, `CS`
## Syllabus
* Meaning of "code": 規則、準則
* 編碼
* 有規則
* 一串可重複字母排列，以碼字為單位
* 一個碼字識別一個符號
* 詞彙
* 符號：資訊基本元素，或是基本元素的特定排咧
* 字母：排列碼的基本元素
* 碼字：字母的特定排列，對應一個符號
* 碼：一套碼字與符號對應的規則
* 編碼：符號轉碼字
* 解碼：碼字轉符號
* 固定長度編碼：易裁切易設計，可用碼字數量固定
* 變動長度編碼
* coding space：給定的可用碼字數量
* 好的碼
* 連續排列近似隨機字串（密碼學
* 平均長度接近理論下限（資料壓縮
* 理論下限：資訊理論 Imformation Theory
* 偵錯除錯（通訊儲存
* 編碼的不可顛倒順序：壓縮source coding、加密encrypt、檢錯channel coding
## Basic Definition
* 偵錯與除錯的應用
* 偵錯：重送
* TCP、身分證、ISBN
* 除錯：校正
* 儲存體、太空通訊
* 偵錯除錯一概使用固定長度碼
* 以 block 為單位
> 資料壓縮一概使用變動長度碼
* Shannon
* 消息理論（channel coding）
* channel 不出錯的機率為零，但可以趨近該 channel 的 capability
* 加密
* 定義
* n: 字母的數量
* m: 符號的數量
* C: 碼字的集合
* $[x]$: 第x個符號
* E: 編碼的對應
* [n,k,d]~q~(線性碼)
* (n,M(=q^k^),d)~q~(任何碼)
* Parity Code
* 加一個 parity bit，令/sum位元值mod2=0
* 可以偵測奇數個bit出錯
* odd rarity 在矩形碼行列數一偶一奇無法使用˙˙
* redundancy（冗餘，code word多出來的比例
* \frac{1}{原碼長度}
* rate of code（每位元資訊量
* $k=\log_n|C|=\log_nm$
* $R=\frac{k}{l}$
* Weight Code
* 每個位元乘上權重
* 可以避免碼字換位
* 各位元權重應取不同值
* mod取質數較佳
* 2-out-of-5 code
* 五位元裡兩個1的排列
* 軟體啟動序號
* 公式不公開~~（啥廢話~~
* error
* 與原訊息XOR
* t-error-detecting: 最多偵測t位元錯誤的編碼
* white noise
* 每位元error是獨立事件
* 每位元error機率相等
* BSC(binary symmetric channel)
* 0變1和1變0的error機率是對稱的
* Simple Burst Error
* 雷擊等偶然爆發且密集一段的error
* TCP/UDP的加總checksum
* Error-Correcting Code
* 也有漏error的問題
* Repetition Code
* 重複傳奇數次
* rate低、效率低
* Hamming Distance
* 兩個長度n，同樣字母集形成的字串x與y
* 表記為d(x,y)=d(x_1,y_1)+d(x_2,y_2)+...+d(x_n,y_n)
* x_1 = y_1, d = 0; x_1 \neq y_1, d = 1
* 純粹偵錯最多可以漢銘距離-1位的錯誤（直到漢銘距離會使一個碼字完全變成另一個碼字）
## Hamming Code
* Rectangular Codes
* l=a*b
* Hybercube
* 緯度增加，效率增加，但緯度長度增加時的效率明顯降低
* 1位元檢查漢明碼效率最高
## Finite Field
* 體 Field
* 滿足以下加法與乘法性質
* 封閉性
* 交換律、結合律、分配律
* 加法單元、乘法單元
* 加法逆元、乘法逆元
* 整數不是field（缺乏乘法逆元－倒數）
* 沒有乘法逆元會退化成ring
## Linear Subspaces and Linear Codes
## Hamming Code
* Hamming code 效率證明
* perfect code 完全碼，已經到達資訊效率的頂
* STANDARD binary code速算
* Hadamard code
* 對simplex code加一行0，湊整數(2的次方)
## Linear Code
* Hamming weight在線性碼中，非全偶數權重即奇偶各半
* 可rerange
* 可針對同bit進行乘法
* Standard Form
* 拉一個I矩陣在前方
* Coset
* 數個向量，加上原集合會產生相同codeword集合
## Characteristics of Fields
* field裡用的不應該是x(變數)
* $F_4=F[x]/(1+x+x^2)$(over F2)
* x替換成alpha後的所有根
* F8: a0+a1x+a2x^2, a0, a1, a2 in F0
* x^3+x+1 over F2
* F9: x^2+x+1 over F3
* 通用表記
* $F[x]/(F(x))$
* $F[\alpha]={a_0+a_1\alpha+...+a_{n-1}\alpha^{n-1}}$
* 為何不可約
* 就跟找質數方法一樣
* 用前面的質數去檢驗
* f(x)=a g(x) h(x) over F_g
* 若考慮最高次係數=1，則g(x)、h(x)最高次係數也必=1
* (考慮x2+x+1overF5)若x,x+1,x+2,x+3,x+4除不盡即不可約
* 費馬小定理 Fermat's Little Theorem
* 若p為質數
* $a^p\equiv a\mod p$
* 若a, p互質，$a^{p-1}\equiv1\mod p$
* 若非質數取mod會出現鏡像和／或循環
* 台科研究所口試題：a的p次方（大數）是多少？
* 反面不成立，a^m\equiv =a\mod m不代表m是質數
* Carmichael number: 561, 1101, 1729...
* Euler: 若a ,m互質，$a^{\phi(n)}\equiv1\mod n$
* $\phi(n)=n(1-1/p_1)(1-1/p_2)...(1-1/p_k)$, p為n的質因數集合
* 此定理對於所有有限體皆成立
* Primitive element / generator
* $F_q=\{0, \alpha, \alpha^2,...,\alpha^{q-1}(1)\}$
* $F_4=F_2[\alpha]$, $(1+x+x^2)$
* $x^2=-(1+x)$
* Order
* $ord(\alpha)$
* alpha最少幾次方後與1同餘
* 必能整除q-1
* 有利找到primitive element
* 1+x+x^3^ over F~7~:
* 7進位的1011
* 1+q+q^3^=(a~0~+a~1~q)(b~0~+b~1~q+b~2~q^2^)
* Minimal Polynomial
* 最低次方的非零首一多項式使得f(alpha)=0
* 唯一且不可約
* 證明：假設有餘數，但餘數會為零，所以沒有餘數
* Cyclotomic Cosets 分圓陪集
* 快速找到一個有限體中不可約的多項式
* 4的次方(乘上特定倍數)mod7會創造421與356兩組餘數循環
* 4與7互質
* 有n、q互質，陪集$C_i={(i*q^j(\mod n))\in Z_n}$
* 分圓：元素湊再一起能把所有餘數湊滿
* 分圓陪集parition Z~n~
* n=q^m^-1 (ex. 15=2^4^-1, 26=3^3^-1
* 每個分圓陪集最多m個元素
* 若i, q^m^-1互質，|C~i~|=m
* C~1~={1,q,q^2^,q^3^,...,q^n-1^}
* C~i~={i,iq,iq^2^,...iq^n-1^}
* 每個質因式都是一個分圓陪集
* 每個質因式都屬於F~q^m^~
* (a+b)^p^=a^p^+b^p^
* A\inF~q^m^~ over F~q~; aq=0
* 3.4.10
* F~9~ over F~3~: 3 mod 8 (F~q^m^~ over F~q~ -> q mod q^m^-1)
* 2+x+x^2^=(x-a)(x-a^3^)
* a^4^=a^2^a^2^=(1-a)(1-a)
## Golay code
* (24,12, 6+2)
* G Matrix簡單
* Property
* A 對稱
* self-dual: 任兩個codeword內積為0
* H也是一個合法的G，G也是一個合法的H
* weight都是4的倍數
* a是4的倍數，b是4的倍數，反證a+b不是4的倍數
* 三元code
* 12 6 6
* 1949 6 月，比Hamming code早
* 原始論文不滿一頁
* 線性
* 循環
* extended版本，比原始版更對稱
* trivial perfect code
* d=1(無偵錯除錯能力)
* 編碼空間只有一個codeword(只有一個狀態沒有傳輸資料的能力)，d定義為無限大
* 奇數長度二元重複碼，d=n
## Cyclic code
* 線性碼
* 所有的編碼解碼很容易用硬體實作
* Hamming code, Simplex code, Goley code 都是 Cyclic code
* 目前沒有除錯兩位的 perfect code
* 定義: shift right 後（超出邊界的的位元填回最高位）的結果也在編碼空間裡
* dual code 也是循環碼
* $S(3,2)與Sim_{r,q}兩表記等價$
* ideal 理想子環
* 決定n後用X^n-1^當作polynomial找出n-1次的排列
* 循環碼有幾種：$X^n-1=\prod_{i=1}^rp_i^{e_i}(x)$
* G: 找出g()然後一路右移
* 互反矩陣形成對偶碼dual code
* 分圓陪集除0集合外可以互相找到成對的（或與自己成對）
* 除錯不盡然需要查表，可用計算
* deg(s(x)) < n-k
* deg(g(x)) = n-k
* s(x)是餘數（沒有餘數就是沒有出錯）
## Bounds in coding theory
* q元(n,M,d)
* 若n固定，M, d呈反向關係
* Main coding theory problem: 給定nd，M最大可以是多少
* relative minimum distance: $\delta=(d-1)/n$（只有這本書）
* d/n（通常）
* The main coding theory problem
* R1 Definition 5.1.4
* R1 5.1.6 線性碼版本
* Extended code
* 在既有的code加一個chk bit
* d是奇數時，extended可使d加1；偶數不會
* perfect code extended 也是 perfect
* Sphere-covering bound
* 以n為核心擴散
* 給出一個lower bound
* t-ECC 兩個 codeword 距離至少是 2t+1
* 擴充到 2t 是碰觸到其他 codeword 前的極限距離，此時 space 內若還有沒被任何 sphere cover 的點，該點也可用作一個 codeword
* 所有 sphere 的體積都擴大到佔據整個 space，則至少要有幾個 sphere（數字公式參見）
* 觀察得出結果
* q-ary hamming
* [(q^r^-1)/(q-1), (q^r^-1)/(q-1)-r, 3] code
* G = ((q^r^-1)/(q-1)-r) * (q^r^-1)/(q-1)
* H = r * (q^r^-1)/(q-1)
## BCH code
* 推廣的 hamming code
* perfect code
* x^q^m^-x=0^
* BCH code length n = 2^m^-1, designed distance 𝛿 = 2t + 1, then dimension n - m(𝛿-1)/2
* error locator polynomial
* σ(z) := !l−1 j=0 (1 − αi j z)
* z = alpha^n-i^
## RS code
* Singleton bound
* $A_q(n,d)\leq q^{n-d+1}$
* MDS code
* Reed-Solomon code
* BCH code
* 循環碼
* 所有分圓陪集都只有一個成員
* d>1, q>=3
* Extend code
* 照著上面的方式decode就可以
## QR code
* 1990 起開始研究二維碼
* QR: quick response
* 1994 日本電裝
* 由 Android 原生支援
* Version 1(21\*21) to 40(177\*177) 每一階加4

霍夫曼
變動長度碼
壓縮用
層次
singular and nonsingular

## HW4

2. k=n-log_q\sum_i=0^(d-1)/2(n i)(q-1)^i,
3.
(1) q-ary hamming bound 不等式（同上題）, 5.3.15, 右邊是全部出錯的可能性，左邊是所有可表示錯誤的symdrome
(2) 把第一小題代入
6. (2) p20 of topic 12, error locator poly