跳到正文

MATH4260

编码及密码

线性码、循环码、BCH 码与求值码、编码界、有限域、信息论与噪声信道、古典及公钥密码、密钥协商与消息认证。

16 章 · 32 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 32 节已标记完成

下一节: 距离、线性码与伴随式

完成记录保存在此浏览器中。

这门课在网上

MATH4260 笔记里的内容

定理卡
82
定义
48
反例
34
概念视角
22
思想史
6
证明透视
32

有思想史的节

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 32 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

在网上定理卡 82 · 定义 48 · 反例 34 · 概念视角 22 · 思想史 6 · 证明透视 32

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 32 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

第 1 章 · 4 节

线性码

二元域上的距离、纠错与伴随式。

定理 14 · 定义 8反例 4视角 4思想史 1证明透视 5

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 1.1

    距离、线性码与伴随式

    推导纠错保证、二元线性码和伴随式译码。

  2. 1.2

    扩展汉明码与单错纠正、双错检测

    推导扩展汉明码的伴随式译码器、单错纠正与双错检测保证,以及保证不成立时的局限。

  3. 1.3

    填充、覆盖与码大小的极限

    证明有限与渐近形式的 Hamming、Gilbert–Varshamov 与 Plotkin 界,并区分存在性、线性性与有效构造。

  4. 1.4

    重量枚举多项式与 MacWilliams 对偶

    利用加法特征标的正交性推导对偶重量变换,得到精确的系数约束与矩约束,并检验候选码的重量分布。

第 2 章 · 2 节

2. 循环码

连续根与有限伴随式译码器。

定理 4反例 2视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 2.1

    连续根与循环码译码

    证明连续根距离下界,并为二元长度七循环码译码。

  2. 2.2

    作为多项式理想的循环码

    将循环移位与模 x^n−1 的乘法联系起来,构造二元循环码。

第 3 章 · 4 节

3. 信息论

有限信源的熵与二元前缀码。

定理 13 · 定义 11反例 6视角 1思想史 1证明透视 4

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 3.1

    熵与二元前缀码

    推导熵下界,并为有限信源构造前缀码。

  2. 3.2

    Huffman 编码与无损分块信源码率

    证明贪心前缀码算法及其精确的代价证书与熵界,然后说明独立分块如何逼近信源熵。

  3. 3.3

    噪声信道、互信息与译码逆定理

    度量有限信道所保留的信息,并证明可靠二元通信的一个必要码率界。

  4. 3.4

    有限无记忆信道的编码定理

    通过信息密度阈值译码证明容量可达性,并对任意输入相关性证明弱逆定理。

第 4 章 · 4 节

4. 公钥算术

RSA 正确性与教材算术的安全界限。

定理 9 · 定义 5反例 3视角 3思想史 2证明透视 4

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 4.1

    RSA:模运算与公钥加密

    证明 RSA 在所有剩余类上的正确性,并区分教材算术与安全加密。

  2. 4.2

    ElGamal 加密与条件保密性证明

    在判定性 Diffie–Hellman 假设下证明正确性与选择明文安全性,说明有界公平比特采样的误差,并展示可延展性。

  3. 4.3

    RSA 签名与全域哈希

    定义选择消息伪造,展示教科书式 RSA 的攻击,并在随机预言机模型中证明一个条件性的全域哈希定理。

  4. 4.4

    Schnorr 身份识别与随机数重用

    证明离散对数身份识别协议的正确性、提取性与诚实验证者模拟,然后考察其签名变换与随机数(nonce)失效。

第 5 章 · 2 节

5. 古典密码

仿射代换与精确信息泄漏。

定理 6 · 定义 4反例 2视角 2思想史 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 5.1

    古典密码:仿射密码及其保留的信息

    推导仿射解密公式,从已知观察恢复密钥,并区分精确的信息泄漏与统计频率分析。

  2. 5.2

    矩阵密码、周期密钥与信息泄露

    用模线性代数、已知明文与精确的保密性障碍来分析 Hill 密码与 Vigenère 密码。

第 6 章 · 1 节

6. 信源压缩

构造最优有限二元前缀码。

定理 4 · 定义 1反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 6.1

    Huffman 编码与最优前缀树

    证明贪心构造对有限信源的期望前缀码长度最小。

第 7 章 · 1 节

7. 噪声信道

研究二元对称信道的信息与纠错。

定理 2 · 定义 2反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 7.1

    二元对称信道与重复码

    计算单次使用信道的互信息,并在明确的噪声模型下研究有限重复码。

第 8 章 · 1 节

8. 秘密共享

证明门限重构及信息论保密性。

定理 2 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 8.1

    多项式门限秘密共享

    证明有限域门限方案的重构性与完全保密性。

第 9 章 · 1 节

9. 多项式求值码

研究求值码的距离、错误与擦除。

定理 2 · 定义 2反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 9.1

    求值码、错误与擦除

    推导多项式求值码的距离和错误与擦除保证。

第 10 章 · 2 节

10. 密钥协商

研究模运算密钥协商及其安全假设。

定理 4 · 定义 3反例 3视角 2证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 10.1

    Diffie–Hellman 密钥协商

    推导模运算密钥协商,区分其算术、身份认证和安全性。

  2. 10.2

    Diffie–Hellman 安全实验

    比较被动安全实验、计算假设与主动替换。

第 11 章 · 1 节

11. 消息认证

研究一次性认证实验及其限制。

定理 1 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 11.1

    一次性认证实验

    证明一次性仿射标签的替换概率,并研究密钥重用。

第 12 章 · 1 节

12. 译码限制

联系有限字母表的估计错误与条件熵。

定理 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 12.1

    错误概率与条件熵

    证明有限字母表的 Fano 界并解释其限制。

第 13 章 · 1 节

13. 编码界

比较贪心存在性界与汉明装箱界。

定理 2 · 定义 1反例 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 13.1

    贪心码与汉明界

    以贪心法构造有限码,比较存在性与装箱界。

第 14 章 · 3 节

有限域

有限域的构造、结构与离散对数。

定理 9 · 定义 5反例 3视角 3证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 14.1

    有限域为何存在,以及其子域如何相互嵌套

    由不可约多项式构造有限域,并证明其元素个数为素数幂、非零元乘法群是循环群、Frobenius 映射的周期以及子域的分类。

  2. 14.2

    以可验证的检验来计算并构造有限域

    实现多项式剩余类算术,证明一个不可约性检验,并给出带明确失败概率、随机性有界的有限域构造。

  3. 14.3

    元素的阶、单位根与离散对数

    构造指定阶的单位根,并在明确的代价假设下证明小步大步算法与素数幂离散对数算法。

第 15 章 · 2 节

BCH 码

BCH 码的设计距离与伴随式解码。

定理 4 · 定义 4反例 2视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 15.1

    连续根与 BCH 距离保证

    由扩域中的根构造循环码,证明范德蒙距离界,并构造一个长度为十五的二元码。

  2. 15.2

    由 BCH 伴随式定位两个比特错误

    为二元长度十五的 BCH 码推导完整的二错译码器,并区分有保证的纠正与错误半径之外的行为。

第 16 章 · 2 节

求值码

Reed-Solomon 码与 Berlekamp-Welch 解码。

定理 5反例 2视角 2思想史 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 16.1

    多项式求值、插值与最优距离

    构造 Reed–Solomon 码,证明其参数与擦除恢复,并由插值推导校验关系。

  2. 16.2

    未知错误化为线性方程组

    利用首一错误定位多项式证明 Reed–Solomon 码的多项式时间唯一译码,包括失败证书与未用完的错误预算。

Vercel 访问统计与公开页面性能测量分别征求同意,均非使用网站的必要条件。

网站功能存储(按需使用)

安全、登录和你选择的偏好会按需使用存储,与可选统计分开处理。

撤回会停止后续统计;需要卸载已加载的统计程序时,页面会刷新。已发送的数据不会因此删除。

查看 Cookie 与存储详情