NAUKA W SŁUŻBIE LUDU. Photo by Marcin Simonides on Unsplash

编码理论笔记

日期：2024/9/12 分类： 备忘 标签： 编码理论 Coding theoryCheck ISBNWhat 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 codesNonsingular Codes每个源的元素都映射到不同的码字即每个源符号都有唯一的编码，不会有两个源符号映射到同一个码字Uniquely Decodable Codes保证接收到的码字序列可以唯一解码为原始信息符号序列Prefix Code没有任何码字是其他码字的前缀 ——这是防止编码产生歧义的关键特性，保证了→即时解码的可能性Design:C1: singularC2: non-singularC3: UDCC4: 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 gainThe 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 errorSyndrome of encoded message , . Let . The syndrome of isHamming codeConstruct (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 decodingSuppose . 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 mininumMinimum

2023 年 12 月 29 日写于 RemNote．