---
# System prepended metadata

title: CS3031 編碼理論 Coding Theory
tags: [CS, TaiwanTech]

---

# 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
