编码理论笔记

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．

编码理论笔记

评论