1. 从“循环”说起为什么我们需要循环码如果你学过信息论或者编码理论大概率对线性分组码、汉明码这些概念不陌生。它们就像是给原始信息穿上了一层“防弹衣”在传输过程中即使被“子弹”噪声击中也能通过校验位把错误找出来甚至纠正。但今天我们要聊的循环码它不仅是“防弹衣”更是一件“有特殊编织纹理的防弹衣”。这个“纹理”就是“循环性”。我第一次接触循环码时觉得这个概念有点“绕”。什么叫“循环”简单说就是码字一个合法的编码序列向左或向右循环移位任意位后得到的新序列仍然是一个合法的码字。比如一个码字是1101000把它循环左移一位变成1010001这个新序列也必须是这个码集合里的一个码。这个性质听起来有点数学美感但它的威力远不止于此。正是这个看似简单的循环特性让循环码的编码和译码电路变得异常简单和高效——你几乎可以用一个带反馈的移位寄存器就搞定编码这在硬件实现上简直是福音。那么为什么在信息论的复习中循环码是绕不开的重点因为它是连接理论抽象和工程实践的一座关键桥梁。线性分组码告诉了我们纠错码的数学框架而循环码则在这个框架上引入了多项式环这个强大的代数工具让码的构造、分析和实现都变得系统化。无论是你手机里的4G/5G信号还是Wi-Fi传输、卫星通信甚至是光盘和二维码QR Code里循环码或其衍生码如BCH码、RS码都扮演着核心角色。搞懂循环码你才算真正摸到了现代数字通信和存储系统可靠性的“门道”。2. 核心基石如何用多项式“描述”一个码要玩转循环码你必须先掌握它的“语言”——多项式。这不是高等数学里那种求导积分的多项式而是系数在二元域GF(2)就是0和1加法是异或乘法是与上的多项式。一个长度为n的二进制序列可以直接对应成一个次数不超过n-1的多项式。举个例子码字1101通常我们认为最左边是最高位对应的多项式就是1*x^3 1*x^2 0*x^1 1*x^0 x^3 x^2 1。看到了吗序列的每一位就是多项式对应次幂的系数。循环码的整个理论大厦就建立在一条核心性质上一个 (n, k) 循环码即长度为 n信息位为 k 的循环码中所有码字多项式都是某个称为“生成多项式” g(x) 的倍式。同时g(x) 本身必须是x^n 1的一个因式且其次数为r n - k。这有点抽象我们拆开看生成多项式 g(x)这是循环码的“灵魂”。它是一个r次多项式r n - k。一旦确定了 g(x)整个码的所有码字就都确定了。所有码字多项式c(x)都可以写成c(x) m(x) * g(x)其中m(x)是次数小于k的任意信息多项式。x^n 1的因式这个条件保证了码的“循环性”。它意味着如果你对一个码字多项式进行循环移位相当于乘以x再对x^n 1取模结果仍然会是g(x)的倍式从而还是一个合法码字。实操中的关键点如何找到一个可用的 g(x)这通常需要分解x^n 1。在二元域下x^n 1可以分解成若干个“既约多项式”类似于整数中的质数的乘积。选择其中一些因子的乘积作为 g(x)就能生成一个循环码。例如x^7 1可以分解为(x1)(x^3x1)(x^3x^21)。如果我们选择g(x) (x^3x1)那么就能得到一个 (7, 4) 循环码因为 g(x) 次数为 3所以n7, k4。这个码其实就是著名的 (7,4) 汉明码它恰好是一个循环码。注意这里有个容易混淆的地方。不是所有线性码都是循环码但汉明码中有一些特定的参数如(7,4), (15,11)可以构成循环码。当你看到“循环汉明码”时指的就是这种具有循环结构的特殊汉明码。3. 编码实战两种方法从原理到电路知道了 g(x)我们怎么把一个 k 位的信息组m编成一个 n 位的码字c呢有两种主流方法它们本质相通但思路不同。3.1 方法一非系统码编码这是最直接的方法。既然码字c(x) m(x) * g(x)那么直接把信息多项式m(x)和生成多项式g(x)在GF(2)上乘起来就行了。步骤将 k 位信息组表示为信息多项式m(x)次数 k。计算c(x) m(x) * g(x)。将c(x)的系数写出得到一个 n 位码字因为m(x)最高k-1次g(x)是r次乘起来最高n-1次。例子对于 (7,4) 循环码g(x)x^3x1。假设信息m1101则m(x)x^3x^21。 计算c(x) (x^3x^21)(x^3x1) x^6 x^5 x^4 x^3 x^2 x 1在 GF(2) 上计算注意110。 所以码字c1111111。看所有位都是1。特点简单粗暴但生成的码字不是“系统码”。也就是说在码字c中你无法直接看到原始的信息位m信息位和校验位是混合在一起的。这在某些需要直接提取信息的场景下不太方便。3.2 方法二系统码编码更常用我们更希望码字的前 k 位或后 k 位就是原始信息位后面跟着 r 位校验位。这种形式称为系统码。循环码可以很方便地编成系统码。步骤将信息多项式m(x)乘以x^r即左移 r 位得到x^r * m(x)。这相当于在信息位后面预留出 r 个校验位的位置。用g(x)去除x^r * m(x)得到一个余式r(x)次数小于 r。x^r * m(x) q(x) * g(x) r(x)构造码字多项式c(x) x^r * m(x) r(x)。因为r(x)是余数所以c(x)必定能被g(x)整除因为c(x) q(x)*g(x) r(x) r(x) q(x)*g(x)在 GF(2) 中r(x)r(x)0。此时c(x)的前 k 位系数对应m(x)高位后 r 位系数对应r(x)正是我们想要的系统码形式。例子同样对于 (7,4) 码g(x)x^3x1r3。信息m1101m(x)x^3x^21。x^3 * m(x) x^6 x^5 x^3。用g(x)除x^6x^5x^3x^6 / x^3 x^3计算x^3*g(x) x^6 x^4 x^3相减异或得余项x^5 x^4。x^5 / x^3 x^2计算x^2*g(x) x^5 x^3 x^2相减得余项x^4 x^3 x^2。x^4 / x^3 x计算x*g(x) x^4 x^2 x相减得余项x^3 x^2 x。x^3 / x^3 1计算1*g(x) x^3 x 1相减得余项x^2 x 1。 所以余式r(x) x^2 x 1对应111。码字多项式c(x) x^6x^5x^3 (x^2x1) x^6x^5x^3x^2x1。 对应码字c 1101 111。看前4位1101就是原始信息电路实现宝藏所在系统码编码可以用一个简单的线性反馈移位寄存器实现。这个电路的核心就是一个根据g(x)系数连接的移位寄存器。对于g(x)x^3x1系数为1, 0, 1, 1对应x^3, x^2, x^1, x^0其编码电路如下图所示文字描述一个3级移位寄存器D触发器b0, b1, b2初始为零。反馈连接根据g(x)的系数除最高次项x^2系数为0所以无连接x^1系数为1所以b2输出反馈到加法器x^0系数为1所以b0输出也反馈到加法器。操作前k个时钟周期开关打到“信息输入”位置信息位m_k-1, ..., m_0一边输出为码字高位一边送入LFSR计算余数。后r个时钟周期开关打到“校验输出”位置将移位寄存器中的余数校验位依次输出。 通过这个简单的电路无需进行复杂的多项式除法运算就能完成系统码编码。这是循环码在硬件上极具优势的体现。4. 译码与纠错伴随式解码的循环妙用码发出去经过有噪声的通道接收端收到一个可能出错的向量r对应多项式r(x)。译码器的任务就是判断是否有错以及错了哪几位。对于任何线性分组码伴随式都是译码的核心。对于循环码伴随式的计算和利用因其循环特性而变得更加高效。伴随式 s(x) 的定义用生成多项式g(x)除接收多项式r(x)所得的余式。r(x) a(x) * g(x) s(x)其中s(x)次数小于r。如果s(x) 0则认为r(x)是一个码字传输无误当然也可能错成了另一个码字这是不可检测的错误但概率极低。如果s(x) ≠ 0则传输一定发生了错误。假设错误图样为e(x)错误的位置为1正确为0那么r(x) c(x) e(x)。因为c(x)能被g(x)整除所以s(x)实际上等于e(x)除以g(x)的余式s(x) e(x) mod g(x)。循环码译码的关键思路相同的错误图样即使循环移位后计算出的伴随式也具有循环关系。这意味着我们不需要为所有可能的错误位置单独计算和存储伴随式。我们只需要针对那些“最可能发生的错误图样”比如重量较小的错误建立一个伴随式-错误图样查询表。当收到一个伴随式s(x)后查表如果找到对应的错误图样e(x)则纠正c_hat(x) r(x) e(x)。如果没找到则将伴随式循环移位相当于将接收向量循环移位同时更新伴随式这也有对应的简单电路操作再查表。重复这个过程最多n次。这个过程称为梅吉特译码它极大地简化了译码器的结构。译码器主要包含三部分一个用于计算伴随式的除法电路和编码电路类似、一个伴随式循环移位寄存器、一个只存储少数典型错误图样的查询表ROM。举例说明对于 (7,4) 循环汉明码它能纠正1位错误。所有可能的单比特错误图样只有7种0000001,0000010, ...,1000000。译码器预先计算好这7种错误图样对应的伴随式s(x)并存入表格。接收端计算s(x)。如果s(x)为0判为无错。如果s(x非0则在表格中查找。如果找到直接纠正对应位。如果没找到说明可能是多位错误超出了码的纠错能力则进入循环移位流程将接收向量循环左移一位重新计算伴随式这可以通过电路快速完成无需重新做除法再查表。最多移位7次。如果始终找不到匹配则宣布为不可纠正错误。这种方法将译码的复杂度从“应对2^n种可能接收向量”降低到“应对n种循环等价类”对于硬件实现来说节省了大量的存储和计算资源。5. 从循环码到实用强码BCH码与RS码理解了循环码你就拿到了学习两类极其重要的实用纠错码——BCH码和RS码的钥匙。它们都是循环码家族的扩展。5.1 BCH码纠多个随机错误的利器BCH码是以其发明者 Bose, Chaudhuri, Hocquenghem 命名的。它是一种可以精确设计纠错能力的循环码。对于任意给定的正整数m和t存在一个二元 BCH 码其参数为码长n 2^m - 1校验位数n - k ≤ m * t最小距离d_min ≥ 2t 1纠错能力能纠正t个或更少的随机错误。它的强大之处在于你可以直接指定“我要一个能纠t3个错的码”然后通过一套代数方法涉及有限域GF(2^m)和极小多项式构造出它的生成多项式g(x)。而传统的循环码设计往往是通过试凑x^n1的因式纠错能力不直观。BCH码的生成多项式g(x)是由若干个极小多项式的乘积构成的。具体来说若α是GF(2^m)的一个本原元则一个纠t个错误的 BCH 码的生成多项式g(x)是以α, α^2, α^3, ..., α^(2t)为根的所有多项式中系数在GF(2)上的最低次多项式。这个定义保证了码的最小距离至少为2t1。应用场景BCH码广泛用于卫星通信、深空通信、无线通信如DVB-S2标准、NAND闪存如SSD、U盘的控制器中用于纠正存储单元产生的随机比特错误。5.2 RS码纠突发错误的王者RS码是里德-所罗门码的简称它是 BCH 码的一个重要子类但其符号定义在更大的有限域GF(2^m)上而不仅仅是GF(2)。一个(n, k)RS 码有如下特点每个符号是GF(2^m)中的一个元素可以看作是一个m位的字节。码长n 2^m - 1个符号。信息段k个符号。最小距离d_min n - k 1这是一个最大值称为 Singleton 界RS码达到了这个界所以是 MDS 码。纠错能力能纠正最多t floor((n-k)/2)个符号错误。RS码的核心理念是“符号纠错”。一个符号m比特无论里面错了1位还是全错了都算一个符号错误。这使得RS码特别擅长纠正突发错误。因为一长串连续的比特错误在字节符号视角下可能只影响到少数几个连续的符号。例子一个GF(2^8)上的(255, 223)RS码每个符号是一个字节8比特码长255字节信息位223字节校验位32字节。它可以纠正最多(255-223)/2 16个字节的错误。这意味着即使信道中发生了长达16*8128比特的连续突发错误只要这些错误集中在不超过16个字节内RS码就能完全纠正这是二进制码难以做到的。应用场景RS码是数据存储和传输领域的“标配”。CD、DVD、蓝光光盘使用RS码来抵抗盘片划伤产生的长突发错误。早期的硬盘、现在的RAID 6系统、二维码QR Code、以及许多数据广播标准如DVB-T中都使用了RS码。在通信中它常作为外码与作为内码的卷积码或LDPC码级联构成强大的级联编码系统。个人经验在学习RS码时一定要跳出“比特”的思维建立起“符号”或“字节”的概念。它的编解码算法如伯利坎普-梅西算法虽然复杂但核心思想仍然是基于伴随式和错误位置多项式只是运算是在GF(2^m)上进行的。很多开源库如Python的reedsolo提供了RS码的实现动手调库跑几个例子对理解符号运算帮助巨大。6. 复习要点与常见误区梳理最后我们来梳理一下信息论中循环码部分的复习要点并澄清几个常见的理解误区。核心知识脉络定义与性质循环移位封闭性 - 用多项式表示码字 - 生成多项式g(x)的概念 -g(x)整除x^n1。编码非系统编码c(x)m(x)g(x)。系统编码重点c(x)x^r m(x) [x^r m(x) mod g(x)]。电路实现基于LFSR的除法电路务必能画出给定g(x)的编码电路图。译码伴随式s(x) r(x) mod g(x)。伴随式与错误图样的关系s(x) e(x) mod g(x)。循环码的译码优势伴随式的循环特性 - 梅吉特译码 - 简化译码器。进阶码型BCH码定义在GF(2)上可精确设计纠错能力t生成多项式由α, α^2, ..., α^(2t)的极小多项式构成。RS码定义在GF(2^m)上进行符号纠错是MDS码擅长纠突发错误。常见误区与难点误区一循环码一定是系统码。不对。循环码是一个码的集合这个集合具有循环特性。我们可以用系统形式或非系统形式来生成这个集合中的码字。通常我们采用系统编码方法但码本身的性质不依赖于编码方法。误区二生成多项式g(x)的常数项必须为1。不一定。但通常我们选择的g(x)是不可约的或者是由不可约多项式乘积构成这些多项式在二元域下的常数项通常为1除了x1这类因子。如果常数项为0意味着g(x)能被x整除这通常不是我们想要的好码。难点一多项式运算。在GF(2)上的多项式乘除法是基础必须熟练。特别是除法是编码和计算伴随式的核心。建议多手算几个例子直到形成肌肉记忆。难点二伴随式译码流程。梅吉特译码的“循环移位查表”过程容易绕晕。关键要理解电路上对接收向量的循环移位等价于在数学上对伴随式进行一个固定的线性变换。这个变换可以通过一个简单的反馈电路实现无需重新计算除法。难点三BCH/RS码的域转换。这是最大的跳跃。从比特到符号从GF(2)到GF(2^m)。理解GF(2^m)的构造本原多项式、元素表示多项式、指数、二进制向量以及其上的运算加、乘、求逆是看懂BCH/RS码教科书的前提。不要试图绕过找一些带有具体小域如GF(2^3)例子一步步推导的教程会豁然开朗。给实践者的建议理论学习之外强烈建议用代码如Python实现一个简单的 (7,4) 或 (15,11) 循环汉明码的编码和伴随式译码。自己写一下多项式除法、伴随式计算和查表纠错的流程对理解整个闭环有质的帮助。再尝试调用一个RS码的库对一个字节数组进行编码然后故意篡改几个字节再看能否成功译码恢复。这种实操带来的理解深度是纯看书无法比拟的。循环码的魅力在于它用一个优雅的数学性质循环性催生出了一系列高效、实用的编解码算法与硬件结构。它像是一座桥一头连着抽象的代数结构另一头连着实实在在的通信芯片和存储控制器。把这部分啃下来信息论这门课才算没白学。