内容简介

本书汇聚了作者十多年的研究成果，重在探讨利用拟阵理论构造线性分组码的设计方法及其应用。全书共分为12章。第1~6章主要介绍线性分组码基本理论、拟阵理论以及拟阵理论与编码之间的关系，研究如何利用拟阵理论构造线性分组码。第7~12章主要介绍LDPC码的构造与应用以及利用译码求解布尔多项式的方法，研究如何利用编码构造哈希函数。最后，抛砖引玉，探讨了相关领域未来可能开展的研究工作。本书将复杂的理论研究用浅显易懂的方式加以呈现，可供具有高等代数、概率论知识背景的人员阅读，也可供数学、通信工程、信息安全专业的高校师生及相关专业的科研人员参考。

前言概述

目前计算机飞速发展，特别是量子计算机研究突飞猛进，例如2019年10月IBM构造了53个量子位的量子计算机，意味着经典的基于大整数分解和离散对数问题的密码体系在量子计算下将被攻破。现有研究显示，目前能抵抗量子计算攻击的公钥密码系统主要有以下四种：(1)基于Hash的公钥密码系统，典型的是1979年基于Merkles哈希树公钥签名系统。(2)基于编码的公钥密码系统，有代表性的是1978年基于Goppa码的McEliece公钥加密系统。(3)基于格的公钥密码系统，最引人注意的当属1998年，Hoffstein-Pipher-Silverman的“NTRU”公钥加密系统。
(4)基于多变量方程的公钥密码系统，著名的例子之一是1996年Patarin的“HFEv”公钥签名系统，后来Matsumoto和Imai进一步发展了该系统。本书主要讨论基于编码的公钥密码系统中编码构造问题，并介绍拟阵理论与编码的关系，利用拟阵理论构造具有很好性能的纠错码，为设计基于编码的公钥密码系统提供坚实的理论基础。编码需要的数学理论有代数、几何、概率统计等，拟阵理论最早是1935年Whitney提出的一种更具抽象的独立性，也是线性代数独立性的推广的代数系统。1948年，在贝尔实验室工作的香农提出了信息论的基本框架，发表了经典论文A
mathematicaltheoryofcommunications，指明了纠错编码的发展方向。研究编码领域主要有两个研究方向：一个是以拥有严密代数结构为主的代数编码设计，该类码的设计主要是寻求最小距离最大化及其相应的译码方法；另一个是以靠近香农限为主题的随机编码设计及其译码方法。本书主要以前者为研究对象，探讨基于拟阵理论的二进制线性分组码的最优码设计。在本书中，最优码是指给定码长n和信息位k，具有最大的最小距离d的码。在过去的几十年，研究发现了很多最优码，其中QC码是众所周知的一类好码。然而，如何寻求最优的系统QC码，尤其是最优的二进制线性分组码以及二进制系统的低密度奇偶校验码，是一个值得研究的问题。本书借助拟阵理论对二进制线性分组码型进行设计，其主要内容包括：
(1)利用拟阵理论得到码的生成矩阵和最小距离之间的一种函数关系式，借助该关系式构造码率为1p的系统QC码的生成矩阵；同时提出拟阵搜索算法，进一步找到最优码率为1p的系统的QC码。计算机实验表明，基于拟阵搜索算法可以找到新的七十多个好码，其中有9个QC码的最小距离比Gulliver等构造的QC码的最小距离大。由于构造的码具有系统的生成矩阵，因此很容易就可以得到它们的对偶码。(2)对于一般的二进制线性码的编码设计，如何构造系统的最大化最小距离的码或称最优码仍然是一个很有挑战性的工作。本书利用拟阵理论建立码的生成矩阵和最小距离之间的关系式，构造了一类最优的系统的(n，k，d)二进制线性码,其中参数为n=2k-1…2k-δ，d=2k-2…2k-δ-1，k≥4，1≤δ＜k，这类码在同构意义下是一类1962年被Solomon-Stiffler发明的码（非系统）；选择适当的删除方法，进而设计了一类新的最优系统(n，k，d)二进制线性码，其中参数为n=2k-1…2k-δ-3u，d=2k-2…2k-δ-1-2u，2≤u≤4,2≤δ＜k。利用拟阵理论一个很明显的优势是可以构造系统的生成矩阵。
(3)短的高码率LDPC码可以应用于未来的手持数字视频广播中，本书基于拟阵理论提出一种新的短的高码率系统LDPC码的构造方法：在列重量一定的情况（通常列重量wc≥3），构造满足一定围长条件下的子矩阵，然后将该子矩阵和单位阵合并成LDPC码的校验矩阵。本书构造了28×76和64×328的校验矩阵，仿真结果表明，基于该方法构造的两个LDPC码在AWGN信道下，和当下最好的短码的校验矩阵为42×105、170×425、66×330的LDPC码的性能相比，本书构造的码有更好的BER性能。同时，基于拟阵理论本书给出了围长的充分条件，该条件可以运用于构造给定围长的LDPC码。最后还构造了码率更长的LDPC码，其性能更好。
(4)利用LDPC码的译码方法比特翻转算法和纠错码理论可以求解布尔多项式方程组解的问题，该问题对分析侧信道攻击至关重要。(5)首次提出了利用纠错码构造安全性能更好的Hash函数，Hash函数是区块链技术中的核心技术，Hash函数的安全性至关重要，决定了一个区块链系统的安全性。本书是国家自然科学基金项目（基于拟阵理论的二进制线性分组码的设计及其应用研究，编号11461031）研究成果。由于本人学识有限，书中不妥之处，恳请读者批评指正。

作者介绍

巫光福男1977年11月出生，博士，2012年12月获得厦门大学信息科学与技术学院通信与信息系统工学博士学位，江西理工大学信息工程学院副教授、硕士生导师。讲授本科生课程《计算机密码学》，《信息论与编码》，《通信原理》等，讲授研究生课程《高级算法分析与设计》，《现代编码理论》，《信息安全新技术》。现主持完成国家基金项目一项，参与国家基金项目两项，主持完成江西省教育厅重点科技类项目一项，参与江西省级项目三项。发表SCI论文6篇，EI期刊论文2篇，申请发明专利25项，其中授权专利两项。2019年荣获天融信杯密码数学挑战赛明星导师奖，从2016年到2020年指导学生荣获全国高校密码数学挑战赛中南赛区一等奖8项，国家三等奖7项。指导硕士研究生已毕业5人，在学硕士研究生12人。

目录

1  绪论

  1.1  引言

  1.2  QC码的发展与现状

  1.3  本章小结

2  拟阵理论与编码理论的基本知识

  2.1  拟阵的基本定义与概念

  2.2  编码理论的基础知识

  2.3  MacWilliams等式

  2.4  通信系统的基本模型

  2.5  信道模型与信道编码定理

  2.6  本章小结

3  基于拟阵理论构造一类好的二进制线性码

  3.1  Griesmer界

  3.2  二进制线性分组码合并构造方法

    3.2.1  扩展构造法构造扩展码

    3.2.2  删余法构造删余码

    3.2.3  增广法构造增广码

    3.2.4  增余删信法构造增余删信码

    3.2.5  增信法构造延长码

    3.2.6  直积法构造直积码

    3.2.7  直和法构造直和码

    3.2.8  笛卡儿积法构造码

    3.2.9  链接法构造码

    3.2.10  (C1，C1+C2)法构造的码

    3.2.11  X构造方法

    3.2.12  X3构造方法

    3.2.13  Y1构造方法

    3.2.14  XX构造方法

  3.3  拟阵理论与编码理论的基本关系

  3.4  一类系统的(n，k，d)线性分组码的构造

    3.4.1  二进制线性C(2k-1,k,2k-2)分组码的构造(即δ=1)

    3.4.2  二进制线性C(2k-1+2k-2,k,2k-2+2k-3)码的构造

(即δ=2)

    3.4.3  当δ≥3时二进制线性分组码的构造

  3.5  一类新的二进制系统线性分组码的构造

  3.6  二进制线性分组码C(n,k,d)的对偶码构造

  3.7  本章小结

4  基于拟阵理论构造码率为1/p系统的二进制QC码

  4.1  QC码的基本定义

  4.2  QC码与拟阵理论的基本关系

  4.3  拟阵搜索算法寻找系统的QC码

  4.4  随机拟阵搜索算法寻找系统的QC码

  4.5  本章小结

5  基于拟阵理论构造码率可变的二进制QC码

  5.1  码率可变拟阵搜索算法

  5.2  码率可变拟阵搜索算法计算结果

  5.3  本章小结

6  二进制移位对偶码的构造

  6.1  移位对偶码的定义

  6.2  移位对偶码的性质和定理

  6.3  移位对偶码的构造方法

  6.4  仿真结果

  6.5  本章小结

7  LDPC码的基本理论

  7.1  香农定理

  7.2  LDPC码发展简史

  7.3  LDPC码的定义与表示

  7.4  LDPC码的构造方法

    7.4.1  校验矩阵的随机构造方法

    7.4.2  Gallager的构造法

    7.4.3  Mackay的构造法

    7.4.4  Davey的构造法

    7.4.5  校验矩阵的结构化构造法

    7.4.6  几何构造法

    7.4.7  组合设计法

    7.4.8  PEG构造法

    7.4.9  ACE构造法

    7.4.10  基于下三角矩阵的编码

    7.4.11  半随机LDPC码的编码方法

  7.5  LDPC码的译码方法

    7.5.1  比特翻转译码算法

    7.5.2  置信传播译码算法

  7.6  本章小结

8  译码算法求解布尔多项式方程组

  8.1  布尔多项式方程

  8.2  布尔多项式的问题描述

  8.3  算法描述

    8.3.1  BF算法

    8.3.2  全局最优的贪婪算法

    8.3.3  随机的Muti-BF算法

  8.4  本章小结

9  基于纠错码求解布尔多项式方程组

  9.1  基于纠错码的算法

  9.2  实验结果分析

  9.3  基于纠错码的改进算法

  9.4  本章小结

10  基于拟阵理论构造LDPC码

  10.1  短的高码率LDPC码的构造理论

  10.2  短的高码率LDPC码的构造算法

  10.3  短的高码率LDPC码的性能分析

  10.4  长的高码率LDPC码的构造

  10.5  长的高码率LDPC码的仿真结果分析

  10.6  本章小结

11  基于纠错码的Hash函数的设计与分析

  11.1  引言

  11.2  MD5算法

    11.2.1  填充消息

    11.2.2  划分分组

    11.2.3  对MD缓冲区进行初始化

    11.2.4  数据处理

    11.2.5  输出散列值

  11.3  基于纠错码的Hash散列函数构造

  11.4  本章小结

12  总结与展望

  12.1  本书的主要贡献

  12.2  未来研究的展望

附录

参考文献

后记