编码理论笔记

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

      •