1. 项目概述从Tanner图的一个环说起在通信系统的底层数据ాలు在嘈杂的信道中穿行就像一艘艘小船在暴风雨中航行错误是不可避免的。信道编码就是为这些小船装上“纠错”的罗盘和冗余的船体结构。在众多纠错码中低密度奇偶校验码LDPC码因其能够无限逼近香农极限的纠错能力成为了现代通信标准如5G、Wi-Fi 6、卫星通信的基石。然而LDPC码的性能并非凭空而来其核心秘密隐藏在一种叫做“Tanner图”的结构中。想象一下Tanner图是一个社交网络有两种节点“变量节点”代表数据位“校验节点”代表校验方程。连接它们的边就代表了数据位参与了哪个校验方程。LDPC码的“低密度”意味着这个社交网络非常稀疏每个节点只和少数几个其他节点相连。译码器比如著名的置信传播算法的工作就是让这些节点之间反复“交换消息”逐步修正错误。ాలు问题来了如果这个社交网络里存在很小的“朋友圈”即短环那么消息就会在这个小圈子里来回打转形成“回声室效应”导致译码器过早地对自己的错误判断变得过分自信从而陷入错误无法纠正的“错误平层”。这个最小“朋友圈”的大小在图论中称为“围长”。因此构造大围长的LDPC码是提升其纠错性能、压低错误平层的关键。而在工程上我们尤其偏爱一类具有规则结构的LDPC码——准循环LDPC码。它的校验矩阵由循环置换矩阵组成这种结构使得编码器可以用简单的移位寄存器实现译码器也能进行高效的并行处理硬件实现复杂度大大降低。本文聚焦的正是LDPC码研究中的一个经典且重要的问题Tanner等人基于素数域乘法群构造的一类317正则QC-LDPC码其围长究竟如何分布具体来说这类码的码长为17pp为素数校验矩阵的每一行有3个非零块每一列有17个非零块结构非常规整。我们的目标就是为所有满足p ≡ 1 (mod 51)的素数p画出一张清晰的“围长地图”哪些p对应的码围长是6哪些是8或10而哪些幸运的p能让码达到理论最大围长122. 核心思路拆解将图形问题转化为代数方程面对这样一个涉及图论和编码理论的复杂问题直接在图上游走寻找最短环对于码长动辄成千上万的情况无疑是计算灾难。本文的精妙之处在于建立了一套将Tanner图中的“环ాలు”等价转化为有限域ాలు“多项式方程”ాలు的框架RR然后利用欧几里得除法算法这个强大的代数工具来系统化地求解。2.1 从循环置换矩阵到RR校验矩阵RR首先RR我们明确研究对象。ాలుTannerRR (3RR17)-正则QC-LDDC码ాలు的校验矩阵Hాలు是一个3p × 17pRR的矩阵RRRR它由3×1751个p×pRR的循环置换矩阵RRCPMRR构成RR。RR每个CPMI(n^s m^t)都由一个单位矩阵循环右移(n^s m^t mod p)位得到。这里n和m是素数域F_p中的两个非零元素且它们的阶分别为J3和L17。由于我们要求p ≡ 1 (mod 51)这意味着F_p中存在51次本原单位根记作β。于是我们可以优雅地设n β^17,m β^3。这样校验矩阵中第s行、第t列的CPM就对应指数(17s 3t)整个矩阵的构造变得非常清晰和代数化。2.2 环的代数化表示一个长度为2k的环在Tanner图上表现为变量节点和校验节点交替出现的一个闭合路径。在QC-LDPC码的矩阵表示下这个环对应着k个特定的CPM它们按顺序连接成一个环。研究表明这个环存在的充要条件可以表达为一个关于β的指数和的模p同余方程即所谓的“基本方程”Σ (β^{17s_i} - β^{17s_{i1}}) * β^{3t_i} ≡ 0 (mod p)其中求和i从0到k-1并且路径的起点和终点重合 (s_k s_0,t_k t_0)同时相邻的CPM不能来自同一行或同一列 (s_i ≠ s_{i1},t_i ≠ t_{i1})。2.3 等价类型划分与问题简化对于我们要研究的围长不超过10即长度为4、6、8、10的环其对应的s_i序列称为环的“类型”是有限的。通过对称性和等价变换分析我们可以将所有可能的短环归类为五种等价类型Type (0,1) 对应所有4环。Type (0,1,2) 对应所有6环。Type (0,1,0,1)和Type (0,1,0,2) 对应所有8环。Type (0,1,2,0,1) 对应所有10环。这个归类是突破性的。它意味着我们不需要去检查成千上万个具体的环只需要针对这五种类型分析其对应的基本方程是否有解。由于β^17 ≠ 1我们可以从基本方程中约去公因子(1-β^17)得到更简洁的“修正基本方程”。例如对于6环Type (0,1,2)其修正基本方程为1 β^{3e17} β^{3(ef)-17} ≡ 0 (mod p)其中e t1 - t0,f t2 - t1且e, f ∈ {±1, ±2, ..., ±8}因为列索引差模17不能为0。至此一个复杂的图论搜索问题被完美地转化为了一个有限域上的多项式方程求解问题对于每一种环类型以及其下参数(e, f, ...)的所有可能取值组合称为“有效情况”判断其对应的修正基本方程在F_p中是否有非平凡解即解不是β的幂次单位根。如果有解就意味着对应参数的环存在从而码的围长就不会大于该环的长度。3. 核心武器欧几里得除法算法的巧妙应用问题转化后我们面对的是形如P(β) 0的方程其中P(x)是一个系数为整数或有理数的多项式。我们需要判断在F_p中是否存在51次本原单位根β满足该方程。直接代入检验是不可行的因为β是未知的。这里本文的核心创新点——欧几里得除法算法登场了。它的应用基于一个关键的观察β作为51次本原单位根必然是多项式x^51 - 1的根但更重要的是它是x^51 - 1的某个素因式的根。由于p ≡ 1 (mod 51)x^51 - 1在F_p中可以完全分解为一次因式的乘积其根就是所有51次单位根。β是本原根意味着它不是任何更低阶单位根因此它满足Φ_51(x) 0其中Φ_51(x)是第51个分圆多项式在F_p中可约但其不可约因式次数很高。关键技巧我们并不需要显式地知道Φ_51(x)在F_p中的具体分解式。我们只需要利用β是51次单位根这一性质即β^51 1。由此可以推导出β必须满足一个特定的多项式关系式文中公式(5)。这个关系式是x^51 - 1除以(x^17 - 1)(x^3 - 1)后再除以(x-1)得到的多项式在F_p中它刻画了本原51次单位根满足的约束。欧几里得除法算法的作战流程如下方程化简对于每个有效情况将其修正基本方程P(x) 0写成多项式形式。通常P(x)可以因式分解其中一个因子是(x^2 x 1)对应β^3 1的解但我们排除这种情况因为β是51次根3不是51的因子所以β^3 ≠ 1。约去这个公因子后我们得到一个“简约形式”的多项式R(x)。代数约束β必须满足从51次单位根性质推导出的约束多项式C(x) 0即文中公式(5)。应用欧几里得除法以C(x)为被除式R(x)为除式在有理数域Q上进行多项式带余除法。我们得到一系列余式r_0(x), r_1(x), ..., r_n最后一个r_n是一个非零常数。解的存在性判定这个常数余项r_n是一个有理数。核心结论如果β同时满足R(β)0和C(β)0那么它也必须满足每一步余式等于0。最终这就要求常数余项r_n在F_p中等于0即r_n ≡ 0 (mod p)。由于r_n是一个固定的有理数这等价于p整除r_n的分母与分子的某个线性组合。因此只有当素数p是常数余项r_n的某个特定因子时方程R(β)0才可能有解。筛选与验证对于每个有效情况我们计算其常数余项r_n并找出所有能整除相关整数使r_n ≡ 0 (mod p)成立且满足p ≡ 1 (mod 51)的素数p。这些p就是该情况下的“候选素数”。最后我们需要验证对于这些候选p前面的余式是否也在F_p中为0以确保解确实是本原51次根从而确认环的存在性。这个方法的美妙之处在于它将无限域所有满足条件的素数p上的存在性问题转化为有限个有理数常数的整除性检验问题。通过系统性地对所有有效情况执行这一套流程我们就能地毯式地搜索出所有会导致短环围长12出现的“坏素数”p。4. 实战推演以6环Type (0,1,2)为例让我们跟随论文的思路详细拆解对6环Type (0,1,2)的分析过程这是理解整个方法的最佳示例。4.1 参数空间与方程建立对于6环参数是(e, f)。由于t_i是模17的整数且相邻t_i不等e和f的取值范围是{±1, ±2, ..., ±8}。同时为了避免路径退化即t2 t0我们要求e f ≠ 0 (mod 17)。论文中的表1列出了所有255种可能的(e, f)组合并标记了其中15种无效情况ef ≡ 0。对于每个有效的(e, f)修正基本方程为1 β^{3e17} β^{3(ef)-17} 0。 令a β^{3e17}。由于β是51次本原根且3e17模51不为0因为e不是17的倍数所以a也是51次本原单位根。代入方程我们得到关于a的方程1 a a^k 0其中k的值取决于(e, f)。例如当(e, f) (e, 2e)时3(ef)-17 3e6e-17 9e-17。由于a β^{3e17}我们需要找到a的哪个幂次等于β^{9e-17}。利用β^{51}1和a β^{3e17}可以计算a^{20} β^{20*(3e17)} β^{60e340} β^{9e-17}因为60e340 ≡ 9e-17 (mod 51)。因此方程化为1 a a^{20} 0。 论文表1系统地列出了所有15种有效(e, f)组合对应的k值即a的指数。4.2 多项式化简与欧几里得除法执行以(e, f) (e, 2e)为例方程为1 a a^{20} 0。因式分解注意到a^3 - 1 (a-1)(a^2a1)。由于a是51次根a^3 ≠ 1所以a^2a1 ≠ 0。我们可以验证a^{20}a1包含因子(a^2a1)。进行多项式除法a^{20}a1 (a^2a1)(a^{18} - a^{17} a^{15} - a^{14} a^{12} - a^{11} a^9 - a^8 a^6 - a^5 a^3 - a^2 1)。 因此简约形式多项式为R(a) a^{18} - a^{17} a^{15} - a^{14} a^{12} - a^{11} a^9 - a^8 a^6 - a^5 a^3 - a^2 1。约束多项式a作为51次本原单位根必须满足从β的性质推导出的约束。论文中给出了一个51次多项式C(a)公式(5)它是a必须满足的条件。执行欧几里得除法以C(a)为被除式R(a)为除式在有理数域上进行计算。这是一个机械但繁琐的过程涉及多项式的长除法。论文中详细列出了每一步得到的余式r0(a) a^{15} - a^{14} - a^{13} ... 1 r1(a) a^{14} a^{13} - a^{12} ... - a^3 ... r_{n-1}(a) -(12/49)a^2 (64/49)a 176/49 r_n(a) -(637/9)a - 4655/36 r_{n1} 12861 / 33124 一个常数解的存在性条件最终余数是一个常数12861/33124。要使a同时满足R(a)0和C(a)0必须要求这个常数余项在F_p中等于0即12861/33124 ≡ 0 (mod p)。这等价于12861 ≡ 0 (mod p)因为分母33124在F_p中可逆p是素数且不整除分母。计算12861的质因数分解12861 3 * 3 * 1429。因此只有当p 3或p 1429时才可能使余数为0。候选素数筛选但我们的p必须满足p ≡ 1 (mod 51)。p3不满足3 mod 51 3。p1429呢检查1429 mod 5151*281428所以1429 mod 51 1满足条件因此p1429是此情况下的一个候选素数。回溯验证我们还需要验证当p1429时前面的所有非恒定余式r_i(a)是否也在F_p中为0或与R(a)、C(a)兼容。论文指出对于p1429前面的余式不为零这意味着R(a)和C(a)在F_p中不互质存在公因子即存在a同时满足两者。因此当p1429时存在参数(e, f) (e, 2e)使得6环方程有解这意味着对应码的围长g ≤ 6。4.3 系统化扫描与结论汇总对表1中所有15种有效(e, f)组合重复上述过程。例如(e, 3e)得到候选p2347。(e, 4e)得到候选p2347。(e, 5e)得到候选p1429。(e, 8e)和(e, -2e)的常数余项非零意味着对所有p都无解。其他组合也分别得到候选p1429或p2347或无解。最终结论对于6环Type (0,1,2)只有当p 1429或p 2347时Tanner (3,17) 码中才存在长度为6的环。对于所有其他满足p ≡ 1 (mod 51)的素数p码中不存在6环因此其围长至少为8。5. 围长分布全景从理论推导到具体列表通过对另外四种环类型4环、两种8环、10环进行同样系统而艰巨的欧几里得除法分析我们最终可以绘制出完整的围长分布图。5.1 4环与6环的快速判定4环 (Type (0,1))其修正基本方程为(1-β^17)(1-β^{3e}) 0。由于β^17 ≠ 1且β^{3e} ≠ 1e不是17的倍数方程恒不成立。因此在所有满足条件的p下Tanner (3,17) 码中均不存在4环。这是一个非常强的性质意味着这类码的围长至少为6。6环 (Type (0,1,2))如上节所述仅当p 1429或p 2347时存在。所以对于这两个素数码的围长g 6。5.2 8环与10环的详尽搜索对于8环和10环参数组合的数量急剧增加8环有(e,f,g)三个参数10环有(e,f,g,h)四个参数。论文通过组合分析列出了所有“无效情况”参数和模17为0导致路径非简单环和“有效情况”。然后对每一个有效情况执行欧几里得除法流程筛选出会产生8环或10环的素数p。8环对应两种类型(0,1,0,1ాలు)RR和(0,1,0,2)。RR经过对所有有效情况的筛查RR发现共有37个素数p会导致码中存在8环。RR论文中给出了这个集合S8RR包括103, 307, 409, 613, 919,ాలు ..., RR120124ాలు39RR等。RR对于ాలు这些pRR如果该码RR不存在6环RR即pRR不是1429RR或2347RR那么RR它的围长就是8。10环对应类型(0,1,2,0,1)。筛查过最为复杂有效情况多达3855种。最终论文给出了一个包含446个素数p的集合S10。对于这些p如果码中不存在6环或8环那么它的围长就是10。5.3 ాలు最终围长分布RR定理RR综合以上所有分析RR我们可以得到RR关于Tanner (3, 17)-正则QC-LDPCాలు码围ాలు长分布的ాలు完整结论令pాలు为一个素数且RRpRR ≡ 1 (RRmod 51)RR。RR令RRg(p)RR表示码长RR为17p的Tanner (3,17)-正则QC-LDPCాలు码的围长RR。RR则有 1ాలు. RR对于所有ాలు这样的pRRాలు均有RRg(p) ≥ 6。RRాలు不存在围长为RR4的码。 2. 当RR且仅当RRp ∈ {1429, 2347RR}RR时RRRRg(p) 6。 3. RR当且仅当RRpRR ∈RR S8RR \ {1429, 2347}时g(p) 8其中S8是包含37个素数的集合见论文。 4. 当且仅当p ∈ S10 \ (S8 ∪ {1429, 2347})时g(p) 10其中S10是包含446个素数的集合见论文。 5. 对于所有其他满足p ≡ 1 (mod 51)的素数p即除了上述有限个素数以外的无穷多个素数均有g(p) 12达到了此类码的理论最大围长。核心洞见这个结论具有重大理论价值。它表明导致围长下降12的“坏素数”是有限的。对于绝大多数符合条件的素数p我们都能“免费”获得最大围长12的优质QC-LDPC码。这为编码构造者提供了极大的便利只需随机选择一个足够大的、满足同余条件的素数p并避开那几百个已知的“坏素数”就能以极高的概率构造出围长为12的码。6. 实操启示与工程意义这项高度理论化的研究对工程实践有着深刻的指导意义。6.1 如何利用此结果构造好码参数选择如果你想构造一个围长为12的Tanner (3,17) QC-LDPC码首先需要确定码长N 17p。选择一个较大的、满足p ≡ 1 (mod 51)的素数p。例如p 100003100003 mod 51 1。查表避坑查询本文给出的“坏素数”列表{1429, 2347}∪S8∪S10确保你选的p不在其中。对于p100003它远大于列表中的最大素数因此可以安全使用其围长必为12。生成矩阵在素数域F_p中找到一个51次本原单位根β这可以通过随机搜索并验证β^511且β^k ≠ 1对于所有k51成立来实现。然后按照公式H [I(β^{17s3t})]生成校验矩阵其中0 ≤ s ≤ 2,0 ≤ t ≤ 16。性能验证在仿真中该码应表现出优异的纠错性能和极低的错误平层。6.2 方法论的普适性本文展示的“环类型划分 - 方程化 - 欧几里得除法筛查”的研究范式不仅适用于 (3,17) 码可以推广到其他(J, L)正则的Tanner QC-LDPC码族。对于J和L较小的码如 (3,5), (3,7), (3,11) 等此方法可以完全解析地确定围长分布。对于更大的J或L虽然计算复杂度会组合爆炸但思路依然清晰通过分析更短的环如4、6、8环来确保一个较大的下界对于更长的环则可以结合概率方法和计算机搜索进行辅助分析。6.3 对译码器设计的启示围长为12意味着Tanner图中最短的环长度为12。这对于置信传播译码器而言是一个非常好的消息更独立的 extrinsic 信息在迭代译码中信息在变量节点和校验节点间传递。大围长使得信息在回到原始节点前经过了更长的路径经历了更多次的“混合”从而减少了短环带来的自相关性提高了译码的可靠性。更低的错误平层错误平层通常与码的陷阱集有关而短环是构成小陷阱集的基础。消除短环特别是4环和6环能有效消除小的基本陷阱集从而显著降低错误平层。迭代收敛性大围长通常有助于译码算法更快、更稳定地收敛。7. 总结与展望本文的工作可以看作是代数编码理论与计算机代数一次漂亮的结合。它将一个复杂的组合图论问题通过巧妙的建模转化为有限域上多项式方程的解的存在性问题并借助经典的欧几里得除法算法这个“老工具”给出了系统、完整、解析的解答。这项研究最令人振奋的结论是它的“有限性”在无穷的素数序列中只有屈指可数的几百个“坏苹果”会导致围长损失。这意味着在工程上我们几乎可以“无视”短环问题随机选取的大素数p几乎总能给出围长最优的码。这极大地简化了高性能QC-LDPC码的构造流程。当然这项工作也留下了进一步探索的空间更大围长的探索本文分析了长度≤10的环。对于围长为12的码是否存在长度为12的环如果存在其对应的素数p是否有规律这需要分析更复杂的环类型。其他环特性的影响围长是最短环的长度但环的数量、分布如ACE值同样影响译码性能。未来的工作可以基于本文的框架进一步分析这些环的分布特性。构造方法的扩展能否将欧几里得除法算法与更现代的计算机代数系统如Gröbner基结合自动化地分析更复杂的码类或更大的环长与性能的直接关联理论上的大围长确保了良好的译码潜力但最终的比特误码率性能还需要通过蒙特卡洛仿真来验证。可以将本文确定的不同围长的码进行仿真比较直观展示围长从6提升到12所带来的性能增益。总而言之本文不仅解决了一个关于特定QC-LDPC码族围长分布的具体问题更重要的是提供了一套强大、清晰、可推广的分析工具。它再次证明了在通信与编码的深水区深刻的数学工具依然是照亮前路、创造性能奇迹的灯塔。对于从事信道编码研究和工程实现的同行来说理解并掌握这类将结构问题代数化的思想是迈向更高级别设计的关键一步。