抽象代数在信息领域的两个重要应用

许秋雨，2024.8.10

伽罗瓦为证明5次或5次以上的多项式没有一般的代数表达式根而提出的群环域是现代数学的开始，特别是抽象代数的开始。数学是一切理工学科的工具，但是现代数学在工程上的真正应用在哪里？在很多数学的应用里，有的可能并非必不可少，如有的应用尽管用了近代数学，但实质上也许完全可以用非现代数学来解决。所以，在哪些应用里，现代数学必不可少？也许并不是很多人一下就能举出这样的例子。我下面举两个例子，在这两个例子里，抽象代数不可缺少。

第一个例子是Reed-Solomon（RS）码（BCH码也是）。RS码也许是纠错码里最有名的码。我以前也介绍过很多次。在实际应用中，纠错码有无快速编码和解码的方法很重要，而线性码就是很重要的一类。一个线性码等价于一个常量矩阵，叫生成矩阵，而一个码字就是一个信息向量乘以这个矩阵。因为解码必须是唯一的，所以这个生成矩阵必须可逆。一个好的线性码不光是生成矩阵可逆，还要码字间的最小距离（即汉明距离）大。设计一个好的线性码就是找一个好的生成矩阵，显然，越多的可选矩阵，能选到好的生成矩阵的可能性就越大。

最早的线性码都是二进制的，即它们对应的生成矩阵里的每个元素都只是0或1，这样就大大地限制了生成矩阵的选择。RS码的出发点就是把二进制的二元素域推广任何一个有限域，即生成矩阵里的元素可以在一个有限个元素的集合里取，比如每个元素本身就是一个二元素向量。为什么非要是域的原因就是在解码时要能做除法，这就是为解决解码唯一性，即正确解码。

有了这个想法后，RS码就是选择了一个最直接的生成矩阵，即由一个本元素所产生的范德蒙行列式中的高阵，这样能保证每个主方阵还是一个范德蒙行列式，从而可逆，这也决定了RS码的最小距离。大家可以看出，这里没有系统的有限域的知识是不可能有RS码的。其实讲白一点，有限域就是为向量（向量里的元素取自同一个有限集合，如｛0，1｝）定义加减乘除法，这样就可以系统地解向量值的线性方程组了。

第二个例子是不久前讲到的南加州大学的Golomb教授发明的m序列，其m代表的是maximum length。正像上例中说的，在工程应用中，能否有简单的产生方法很重要，而线性移位寄存器（LFSR）就是最简单的一种。问题是给定一个LFSR的长度m，其产生的最长的没有重复的序列是多长？怎么选这个LFSR？这就必须要用到有限域的知识，类似于RS码，没有有限域的知识是不可能的。它说了，如果一个LFSR的生成多项式是m阶本元多项式，那么这时它产生的不重复序列的长度最长，即最小周期最长，如在二进制系数下的长度是2^m —1。注意，如输入二进制序列的长度为m，那么它的LFSR输出非0序列的最大周期长度就是2^m—1。所以m序列已经达到了最大可能的最长周期长度，即最大可能的不重复的序列长度，或者说m序列是可用m个输入值能被LFSR产生的随机性好的最长序列。所以m序列是最重要的一类伪随机序列，在很多应用里有着不可被替代的作用。

有意思的是，Reed和Golomb都是南加大电子工程系通信所（CSI）的教授。

除了上面这两个例子外，抽象代数在密码学里也不可缺少，其实第二个例子已经与广义的密码很有关系了。除了这些外，在我们领域（偏算法的EE）我还一下想不起别的非它不可的重要应用，在此欢迎朋友们指出别的例子。

从上面两个例子我们可以看到，从某种意义上说，非0元素的可逆性，不可分解性，素元素性，不重复性，有限域，是差不多等价的。例如每个素数就决定一个有限域，那么理解素数能否从理解不重复性得到一些启迪呢？