摘要：纠错编码是提升信道可靠性的重要途径。里德-穆勒（Reed-Muller）码作为最古老和最流行的码之一，其独特的码字结构使得编码和译码都具有较低的复杂度，并且可为其他码型的研究提供参考。2017年，RM码被证明可以在二进制擦除信道上实现信道容量，使得RM码的理论
《移动通信》2025年第2期目录
面向6G的RM码编译码方案
11121（1.安徽大学计算智能与信号处理教育部重点实验室，安徽 合肥 230601；
2.上海第二工业大学计算机与信息工程学院，上海 201209）
【摘 要】纠错编码是提升信道可靠性的重要途径。里德-穆勒（Reed-Muller）码作为最古老和最流行的码之一，其独特的码字结构使得编码和译码都具有较低的复杂度，并且可为其他码型的研究提供参考。2017年，RM码被证明可以在二进制擦除信道上实现信道容量，使得RM码的理论与应用再次引起关注。对RM码的编码结构和现有的译码算法进行论述与总结，并对当前译码算法的改进和发展进行综合论述。最后，对RM码作为6G的候选编码方案，未来需要开展的研究方向进行展望。
【关键词】RM码；RM码编码；递归列表译码；递归投影聚合译码；删余
doi:10.3969/j.issn.1006-1010.20241209-0002
中图分类号：TN929.5 文献标志码：A
文章编号：1006-1010(2025)02-0051-07
引用格式：陈芳,陈景灿,秦海生,等. 面向6G的RM码编译码方案[J]. 移动通信, 2025,49(2): 51-57.
CHEN Fang, CHEN Jingcan, QIN Haisheng, et al. RM Code for 6G：Encoding and Decoding Scheme[J]. Mobile Communications, 2025,49(2): 51-57.
0 引言
近年来，第五代（Fifth Generation，5G）移动通信技术一直被学术界和工业界推进，现在5G服务已经覆盖了多个国家和地区。尽管5G通信技术凭借其高速和低时延的特点，在物联网、智能家居、以及工业自动化等众多领域扮演着至关重要的角色，然而在智能驾驶、远程医疗等对时效性要求极高的领域，仍迫切需求更为高效且时延更低的通信技术，以保障用户的生命安全和操作可靠性。鉴于当前通信需求的不断演进，第六代（Sixth Generation，6G）通信技术作为驱动未来发展的核心动力，逐步显现为技术前沿的焦点。在首届全球6G峰会上发布的《6G无线智能无处不在的关键驱动与研究挑战》白皮书中明确指出，6G通信技术的时延可降至0.1 ms，相较于5G技术，实现了时延缩短至原来的十分之一[1]。文献[2]进一步对6G相关的性能指标进行了详尽分析，并从信道编码的角度探讨了这些指标的具体数值。为促进6G技术的进步并满足所述通信需求，信道编码技术，作为潜在塑造未来通信格局的核心技术，持续成为增强数据传输可靠性的关键技术和研究途径。里德-穆勒（Reed-Muller, RM）码作为一种最古老、最经典的线性分组码，其起源可追溯至1954年，由Muller首次提出[3]，同年，Reed给出了大数逻辑译码算法[4]。该算法下的RM短码特别适合于那些对系统响应时间延迟零容忍或极低容忍度的实时嵌入式应用，例如在安全气囊系统中的防抱死制动系统（Anti-lock Braking System，ABS）以及心脏起搏器等关键医疗设备中的应用场景，为实现6G通信技术中超低延迟的需求，贡献了理论支持。RM码的分层结构，也为其他差错控制编码的理论提供了丰富的理论分析支撑，也已被应用于3GPP协议当中[5]。不仅如此，RM码在其他领域也得到了很好的运用，比如1969-1977年所有水手号（Mariner）深空通信的控制链路使用码长为32的RM码[6]；RM码也是移动通信3G、4G、5G中控制信道极短码长的编码方案[7-8]。近年来，研究表明RM码在二进制擦除信道（Binary Erasure Channel，BEC）和二进制无记忆对称（Binary Memoryless Symmetric，BMS）信道上能够达到信道容量[9-10]，从而满足高可靠性传输的要求。基于这一特性，RM码有望被纳入面向6G通信系统的信道编码方案之中。本文对几种常见的RM码的编码构造以及相应的译码算法进行了梳理。RM码每一种编码构造都对应不同的译码算法，所以针对不同的构造方式，对RM码的几种译码算法进行分析，重点描述RM码译码算法的研究进展，并对RM码未来的研究方向进行展望。
1 RM码基本原理
2 RM码构造方案
2.1 生成向量法基本思想
2.2 Plotkin构造
2.3 递归生成矩阵构造
3 RM码译码方案
3.1 大数逻辑译码
3.2 递归译码
3.3 递归列表译码
3.4 递归投影聚合译码
递归投影聚合（Recursive Projection-Aggregation，RPA）译码是近几年提出的一种译码算法[22]，这种译码器适用于短码或低阶RM码（一般不超过三阶）。这种算法在二阶RM码且码长不大于1024的前提下，能够实现接近ML译码的误码率。该算法可分为三个过程，分别是投影、递归译码、聚合。具体过程如下：投影操作是把一个RM(r,m)码从m维二进制向量空间中投影到一个t维（一般定义t=1）的子空间，得到子码RM(r-t,m-t)。考虑t=1的情况，即投影到一维子空间。第一次投影，共有2m-1个子空间；第二次投影，对第一次投影子空间的每一个子空间都进行扩展，第二级共有(2m-1)×(2m-1-1)个子空间。以此类推，直到投影到一阶RM码，可使用FHT译码器进行译码。译码后每个子空间的译码结果向上返回，通过聚合操作，逐级修正上一级的输入似然比。经过投影和逐级返回，返回到根节点处，可得到2m-1个聚合结果，进行多数投票（Majority Voting），类似大数逻辑译码中的判决操作。最后一级聚合后，如果没有达到停止条件，开始新一轮递归投影聚合译码。3.5 递归投影聚合译码复杂度
RPA译码器具有近似ML的译码性能，但由于其在每一级的投影空间数目大，最终投影到一阶子码时每个子码都需要使用FHT进行译码，因此具有较高的计算复杂度。FHT的译码次数通常用于衡量RPA译码算法的复杂度[23]。对于5G以及未来的6G通信，需要满足超可靠低时延通信的需求[24]，为节约计算资源并降低译码时延，降低RAP译码算法的复杂度是亟需解决的问题。文献[25]提出一种调度方案（Scheduling Scheme, SCH），每次迭代时有计划的减少需要计算的投影子空间数目。具体方案是设定了一个衰减参数d>1，第p (1≤p≤Nmax)次各级迭代保留4 RM码速率适配研究
为适应多种信道环境的要求，需要对信道编码中码字的码长和码率进行调整。由于RM码分层结构的限制，其码字构造是分阶完成的，因此只能得到固定的码长码率。一般对于RM码的研究，其码长限制于2的幂次。对RM码速率适配的研究是解决RM码在实际场景中灵活应用的关键，删余和缩短是解决速率适配问题的两种常用技术。删余RM码是按照特定的删余方案删余一些码字中的比特，以减少传输过程中实际的传输码字符号。通过改变删余比特的数量，实现RM码的码长灵活和码率可变。若使用二进制删余向量来识别删余的位置，0表示删余的位置，1表示保留下来的码字比特位置。在信息传输过程中，被删余的码字符号不会被传输，因此，在接收端并不知道删余位置的传输比特信息，其相应的LLR位置设置为0。在RM码的母码（未删余）长度为N，信息位长度为K，根据预先设置的删余模式对该码字符号进行删余，得到长度为M的码字，此时RM码的码率为R=K/M。
自RM码提出以来，相关文献中对于RM码删余方案的研究相对较少。在 1977 年的文献[27]中，删余一位的 RM 码被提及，利用 RM 码的布尔多项式构造，删除所有生成多项式在m维零向量上的值所对应的列，形成码长为2m-1的删余 RM码。2013年Kapralova和Dumer定义了一种球面删余技术[28]（这个工作在2017年进行了更加详细地分析[29]），将r阶的RM码映射到半径为b的球体上，只保留一种阶数的码字符号，其余的全部作为删余位置，该作者设计了复杂度为O(NlogN)的递归解码算法。文献[30]的工作将RM码的删余技术应用于密码系统，它可以防止方码（Square Code）攻击的影响，并确保密码系统可以恢复。除此之外，文献[31]给出有关RM码删余技术的研究，仅适用于低码率的RM码，并不具有普适意义。本文对RM码递归生成矩阵进行研究，提出基于RM码生成矩阵列权重的删余方案。RM码生成矩阵每一列的列索引值都可以用一个二进制比特序列表示，比如对于N=256码长的RM码来说，列索引3，5，9分别对应的二进制展开为(3)222=(0000,1001)。首先，将生成矩阵的列权重值做一个升序排列，可以得到一个有序数组，将该数组存储在集合P中；观察集合P可以发现，有些列的权重值相等，将相等列权重值的索引存储到集合Dj，0≤j≤m中，对集合Dj中的索引值按照二进制展开，其中，集合P={D}。可以观察出，对存储在同一个集合Dj中的元素的二进制展开中比特1的数量是相等的。如果二进制序列中只有一个比特1，则以最低有效位（Least Significant Bit，LSB）为优先级，将比特1从b1m12）向最高有效位（Most Significant Bit，MSB）移动。按照此过程选出排序的元素，这种删余排序方案称之为按照最低有效位的权重删余法（Column Weights with a Preference of LSB，CW-LSB）。图6展示了CW-LSB方式的选取规则：
在编码器的输出端，位于删余集合的码字比特不被传输，即实际传输的码长变短。在解码端，将删余位置的对数似然比设为零，不改变译码器的结构，用RM码的递归列表译码器完成解码。
目前已经仿真了不同删余方案下的误块率（Block Error Rate，BLER）结果。图7给出了码长N=256，信息位K=93，列表大小L=8的RM(3,8)码的三种不同删余方案的性能对比。将本文所提的CW-LSB方案与随机删余方案和准均匀删余（Quasi-Uniform Puncturing ，QUP）方案[32]的性能进行了比较。当删余比特数Q=36和Q=60时，极化码的QUP方案在RM码的递归列表译码中几乎完全失效，特别是在删余数量比较多的情况下。随机删余比QUP具有更好的性能，CW-LSB比现有的随机删余和QUP具有更好的解码性能。在这三种删余设计中，CW-LSB具有最佳的BLER性能。在BLER=10-1，删余数量Q=36的条件下，CW-LSB比随机删余有0.27 dB的性能增益。图8展示了使用递归列表译码，列表长度L=4时，RM(3,9)码的三种删余方案的性能对比。从图8中可以观察到，本文提出的删余方案CW-LSB在删余数量较多的时候呈现出优异的误码性能，QUP方案以及随机删余方案在相应删余数量下的误码性能远不如CW-LSB。
5 结束语
本文面向6G的数据传输可靠性需求，对纠错编码中的RM码进行介绍和研究。从RM码的编码结构出发，介绍RM码的特征以及构造思想。针对RM码不同构造方式，介绍RM码的译码算法，并对RM的速率适配研究进行介绍。RM码未来需要进行的研究包括以下内容：（1）目前关于RM码的研究只能设置固定的码长和信息位，码率灵活调整的问题亟待解决；（2）RPA译码具有良好的译码性能，但译码算法的复杂度居高不下，亟需低复杂度高性能译码理论及实现架构的突破。针对上述问题的研究将成为未来提升RM码性能的关键。
参考文献：（上下滑动浏览）
[1] 未来移动通信论坛. 6G无线智能无处不在的关键驱动与研究挑战[R]. 2019.
[2] 张华滋,王俊,童文. 面向6G的信息论与信道编码[J]. 移动通信, 2024,48(5): 94-98.
[3] Muller D E. Application of Boolean algebra to switching circuit design and to error detection[J]. Transactions of the I.R.E. Professional Group on Electronic Computers, 1954, EC-3(3): 6-12.
[4] Reed I.. A class of multiple-error-correcting codes and the decoding scheme[J]. Transactions of the IRE Professional Group on Information Theory, 1954, 4(4): 38-49.
[5] 3GPP, TS 25.212 V3.11.0, Multiplexing and channel coding (FDD) (Release 1999)[R]. 2002-09.
[6] Bhargava V K, Haccoun D, Matyas R, et al. Digital communications by satellite: modulation, multiple access and coding[J]. NASA STI/Recon Technical Report A, 1981, 82: 25219.
[7] 3GPP, TS 36.212 V10.8.0, Multiplexing and channel coding (Release 10)[R]. 2013-06.
[8] 3GPP, TS 38.212 V15.1.1, Multiplexing and channel coding (Release 15)[R]. 2018.
[9] Kudekar S, Kumar S, Mondelli M, et al. Reed–Muller Codes Achieve Capacity on Erasure Channels[J]. IEEE Transactions on Information Theory, 2017, 63(7): 4298-4316.
[10] Abbe E, Sandon C. A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels[C]//2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, Santa Cruz, CA, USA: 2023: 177-193.
[11] Shu Lin, Daniel J. Costello. 差错控制编码[M]. 晏坚,等译. 第二版. 北京: 机械工业出版社, 2007.
[12] Abbe E, Shpilka A, Ye M. Reed–Muller codes: Theory and algorithms[J]. IEEE Transactions on Information Theory, 2020, 67(6): 3251-3277.
[13] Be'ery Y, Snyders J. Optimal soft decision block decoders based on fast Hadamard transform[J]. IEEE transactions on information theory, 1986, 32(3): 355-364.
[14] 黄俊杰.Reed-Muller码软判决译码算法研究[D]. 厦门: 厦门大学, 2015.
[15] Dumer I, Krichevskiy R. Soft-decision majority decoding of Reed-Muller codes[J]. IEEE Transactions on Information Theory, 2000, 46(1): 258-264.
[16] Dumer I. Soft-decision decoding of Reed-Muller codes: a simplified algorithm[J]. IEEE transactions on information theory, 2006, 52(3): 954-963.
[17] 张艳.Polar码和Reed-Muller码的改进译码算法研究[D]. 福州: 福建师范大学,2019.
[18] Dumer I. Recursive decoding and its performance for low-rate Reed-Muller codes[J]. IEEE Transactions on Information Theory, 2004, 50(5): 811-823.
[19] Arikan E. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE Transactions on information Theory, 2009, 55(7): 3051-3073.
[20] Dumer I, Shabunov K. Soft-decision decoding of Reed-Muller codes: recursive lists[J]. IEEE Transactions on information theory, 2006, 52(3): 1260-1266.
[21] Dumer I, Kabatiansky G, Tavernier C. List decoding of biorthogonal codes and the Hadamard transform with linear complexity[J]. IEEE Transactions on Information Theory, 2008, 54(10): 4488-4492.
[22] Ye M, Abbe E. Recursive projection-aggregation decoding of Reed-Muller codes[J]. IEEE Transactions on Information Theory, 2020, 66(8): 4948-4965.
[23] Fathollahi D, Farsad N, Hashemi S A, et al. Sparse multi-decoder recursive projection aggregation for Reed-Muller codes[C]//2021 IEEE International Symposium on Information Theory (ISIT). IEEE, Melbourne, Australia: 2021: 1082-1087.
[24] 赵军辉,任瑞星,刘聪聪,等. 面向6G的超可靠低延迟通信关键技术：研究进展与展望[J]. 移动通信, 2024,48(10): 49-57.
[25] Li J, Abbas S M, Tonnellier T, et al. Reduced complexity RPA decoder for Reed-Muller codes[C]//2021 11th International Symposium on Topics in Coding (ISTC). IEEE, Montreal, QC, Canada: 2021: 1-5.
[26] Hashemipour-Nazari M, Debets R, Goossens K, et al. Recursive/Iterative Unique Projection-Aggregation Decoding of Reed-Muller Codes[C]//ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, Rhodes Island, Greece: 2023: 1-5.
[27] MacWilliams F J. The theory of error-correcting codes[J]. Elsevier Science Publishers BV google schola, 1977, 2: 39-47.
[28] Kapralova O, Dumer I. Spherically punctured reed-muller codes[C]//2013 IEEE International Symposium on Information Theory. IEEE, Istanbul, Turkey: 2013: 1047-1051.
[29] Dumer I, Kapralova O. Spherically Punctured Reed–Muller Codes[J]. IEEE Transactions on Information Theory, 2017, 63(5): 2773-2780.
[30] Lee W, No J S, Kim Y S. Punctured Reed–Muller code‐based McEliece cryptosystems[J]. IET Communications, 2017, 11(10): 1543-1548.
[31] Guruswami V, Jin L, Xing C. Efficiently list-decodable punctured Reed-Muller codes[J]. IEEE Transactions on Information Theory, 2017, 63(7): 4317-4324.
[32] Niu K, Chen K, Lin J R. Beyond turbo codes: Rate-compatible punctured polar codes[C]//2013 IEEE International Conference on Communications (ICC). IEEE, Budapest, Hungary: 2013: 3423-3427. ★
【25专题征稿】6G空口技术、语义通信、通感算一体化
《移动通信》杂志由中国电子科技集团公司主管，中国电子科技集团公司第七研究所主办，是中国期刊方阵“双效期刊”、工业和信息化部精品电子期刊、中国科技论文统计源刊、中国通信学会《信息通信领域高质量科技期刊分级目录》入选期刊、中国电子学会《电子技术、通信技术领域高质量科技期刊分级目录》入选期刊、中国应用型核心期刊、日本JST收录期刊。国内连续出版物号：CN44-1301/TN，国际连续出版物号：ISSN1006-1010，邮发代号：46-181。
来源：移动通信编辑部
