编码理论笔记

Coding theory

Check ISBN
- What is the check digit of ISBN 0-306-40615-??↓
- Check the ISBN 9-219-53894-6.
- Why we use mod 11 here?
  - The modulo-11 algorithm yields a near-100% guarantee that, if any two accounts differ in a single digit, their check digits will also be different. This gives us a minimum Hamming distance of , which allows us to detect any single-digit error.
- Find two coding methodologies in daily life and describe each of them.
  - Morse code (trinary!),
  - RAID-5,
  - Barcode, etc.
Design codes
- Nonsingular Codes
  - 每個源的元素都對映到不同的碼字
    即每個源符號都有唯一的編碼，不會有兩個源符號對映到同一個碼字
- Uniquely Decodable Codes
  - 保證接收到的碼字序列可以唯一解碼為原始資訊符號序列
- Prefix Code
  - 沒有任何碼字是其他碼字的字首
  - ——這是防止編碼產生歧義的關鍵特性，保證了→即時解碼的可能性
- Design:
  - C1: singular
  - C2: non-singular
  - C3: UDC
  - C4: Prefix
  - +---------+----+-----+-----+-----+ | Message | C1 | C2 | C3 | C4 | +---------+----+-----+-----+-----+ | A | 0 | 0 | 10 | 0 | | B | 0 | 010 | 00 | 10 | | C | 0 | 01 | 11 | 110 | | D | 1 | 10 | 110 | 111 | +---------+----+-----+-----+-----+
- Make a nonsingular code but not uniquely decodable. Then make a uniquely decodable code but not prefix code.
- Examples
  - Note that Instantaneous ⇒ Uniquely Decodable ⇒ Non-singular
  - is an [...]instantaneous code (and therefore uniquely decodable and non-singular).
  - is [...]non-singular since no two codewords are the same. However it is not uniquely decodable since and are indistinguishable (it follows that it is not an instantaneous code either).
  - is [...]singular since and have the same codeword (hence not uniquely decodable and not an instantaneous code).
  - is [...]uniquely decodable: when you get a it is the start of a new symbol and the previous symbol is given by counting how many 's since the previous . It is not a instantaneous code since the first codeword is a prefix of all the others.
  - is not an instantaneous code since is a prefix of . Since all codewords have even length we can rewrite it as a -ary code . It is easy to see that this is uniquely decodable since only ever appears as the second half of . Thus if an is followed by anything other than , it represents a .
Coding gain
- The limit of coding gain of some code is its gain compared to Shannon limit.
- What is the limit of coding gain of rate one half code at BER ?↓
Dual space
- Dual space of , is an -dimensional subspace.
- Each vector in is linearly independent and is in .
Linear block code
- Generative matrix
  - 從 code words 中選個向量，末尾正好為單位陣
- Code word
- Parity check matrix
  - 滿足
- Detect error
  - Syndrome of encoded message , .
    Let . The syndrome of is
Hamming code
- Construct (the parity-check matrix of) a hamming code of length 7? How about length 8?
  - Parity-check matrix 應滿足，並且每列不重複、不為
  - Length 7
  - Length 8
- What is the minimum for correcting 2 errors?→
Global decoding
- Suppose . Please give the encoded codeword .↓
- 寫出譯碼順序
  - 算
  - 算
  - 根據已知，算
  - 算
  - 總結：先解 [...]probability 大的，後解[...]重複次數少的
Tanner graph
- 坦納圖表示的是 LDPC 的校驗矩陣
- Write the parity-check matrix according to the Tanner graph.↓
- Find the shortest cycle in the Tanner graph.↓
Network coding
- 利用兩個資料包的異或（XOR）和作為冗餘資料來加快傳輸
Max-flow min-cut theorem
- 割（s-t cut）：把節點分成兩個集合，位於中，位於中
- ：離開（流出）的邊（箭頭）的權重之和
- 最大流最小割（Max-flow min-cut）定理：最大流的值 = 最小割的 capacity
  - 在網路中，源點到匯點的最大流量與網路中的最小割集所能承載的容量相等
- 定義
  - 圖是一個有向圖，其中是源點，是匯點；邊的容量表示從源點到匯點的流量↓
  - 流量的值表示從源點流向匯點的總流量
  - s-t割 是頂點集合的一個劃分，使得，。割集是從集合中的一個頂點指向集合中的一個頂點的所有邊的集合，即
- 例子
  - Not mininum
  - Minimum

2023 年 12 月 29 日寫於 RemNote．

編碼理論筆記

評論