跳到正文

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 與儲存詳情