Decoding Algorithm Combining Syndrome Decoding and Guessing Random Additive Noise Decoding

SHI Yue-zhuang; KONG Ling-jun; LIU Hai-yang

doi:10.12263/DZXB.20240981

您当前的位置：

首页 >

文章列表页 >

Decoding Algorithm Combining Syndrome Decoding and Guessing Random Additive Noise Decoding

Advances and Future of Coding Theory and Technology | 更新时间：2025-12-10

- Decoding Algorithm Combining Syndrome Decoding and Guessing Random Additive Noise Decoding
- ACTA ELECTRONICA SINICA Vol. 53, Issue 7, Pages: 2201-2209(2025)
- 作者机构：
  
  1.中国科学院微电子研究所，北京 100029
  2.中国科学院大学，北京 100049
  3.金陵科技学院网络与通信工程学院，江苏南京 211169
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62271482)
- DOI：10.12263/DZXB.20240981
  CLC： TN911.22;
- Received：29 October 2024，
  
  Revised：2025-06-24，
  
  Published：25 July 2025
- 稿件说明：
移动端阅览
石月壮, 孔令军, 刘海洋. 基于校正子和猜测随机加性噪声的混合译码算法[J]. 电子学报, 2025, 53(07): 2201-2209.

SHI Yue-zhuang, KONG Ling-jun, LIU Hai-yang. Decoding Algorithm Combining Syndrome Decoding and Guessing Random Additive Noise Decoding[J]. Acta Electronica Sinica, 2025, 53(07): 2201-2209.
石月壮, 孔令军, 刘海洋. 基于校正子和猜测随机加性噪声的混合译码算法[J]. 电子学报, 2025, 53(07): 2201-2209. DOI：10.12263/DZXB.20240981

SHI Yue-zhuang, KONG Ling-jun, LIU Hai-yang. Decoding Algorithm Combining Syndrome Decoding and Guessing Random Additive Noise Decoding[J]. Acta Electronica Sinica, 2025, 53(07): 2201-2209. DOI：10.12263/DZXB.20240981

摘要

猜测随机加性噪声译码算法（Guessing Random Additive Noise Decoding，GRAND）是线性码的一类通用译码算法.其中，ORBGRAND（Ordered Reliability Bits GRAND）算法是一种软判决猜测随机加性噪声译码算法，具有运算简单、易于实现等优点，引发了广泛的研究和关注.但是，在限定查询次数的条件下，ORBGRAND算法的译码性能与软判决最大似然译码有一定差距.针对这一问题，本文提出了一种基于校正子译码（Syndrome Decoding，SD）算法和ORBGRAND算法的混合译码算法.该算法为ORBGRAND算法引入一种辅助度量，将接收序列并行输入SD算法和ORBGRAND算法进行译码，选择二者中与接收软判决序列具有最大相关值的码字估计作为译码输出.仿真结果表明，提出的混合译码算法在增加不多复杂度的条件下相对ORBGRAND算法能够获得译码性能改善，并且随着信噪比的增加改善更明显.此外，提出的混合译码算法保持了ORBGRAND算法的通用性，适合于各种类型的线性码译码.

Abstract

Guessing random additive noise decoding (GRAND) algorithms are a class of general decoding algorithms for linear codes. Among them

ORBGRAND (Ordered Reliability Bits GRAND) algorithm

a soft-decision GRAND algorithm that has attracted a lot of attention

is simple and easy to implement. However

there is a gap between the performance of ORBGRAND algorithm and soft-decision maximum likelihood decoding algorithm if the number of queries is limited. To tackle this problem

this paper proposes a hybrid decoding algorithm based on syndrome decoding (SD) algorithm and ORBGRAND algorithm. By introducing an assistant metric for ORBGRAND algorithm

the proposed algorithm performs SD algorithm and ORBGRAND algorithm in parallel for the received sequences and selects the codeword that has the maximum correlation value with the received soft-decision sequences as the decoding output. Simulation results indicate that the proposed hybrid decoding algorithm can outperform ORBGRAND algorithm at the expense of little complexity increase. As the signal-to-noise ratio increases

the performance improvement becomes more obvious. In addition

the proposed hybrid decoding algorithm maintains the generality of ORBGRAND algorithm and is suitable for decoding various types of linear codes.

关键词

Keywords

references

POPOVSKI P , TRILLINGSGAARD K F , SIMEONE O , et al . 5G wireless network slicing for eMBB, URLLC, and mMTC: A communication-theoretic view [J ] . IEEE Access , 2018 , 6 : 55765 - 55779 .

SYBIS M , WESOLOWSKI K , JAYASINGHE K , et al . Channel coding for ultra-reliable low-latency communication in 5G systems [C ] // 2016 IEEE 84th Vehicular Technology Conference . Piscataway : IEEE , 2016 : 1 - 5 .

CHEN H , ABBAS R , CHENG P , et al . Ultra-reliable low latency cellular networks: Use cases, challenges and approaches [J ] . IEEE Communications Magazine , 2018 , 56 ( 12 ): 119 - 125 .

DURISI G , KOCH T , POPOVSKI P . Toward massive, ultrareliable, and low-latency wireless communication with short packets [J ] . Proceedings of the IEEE , 2016 , 104 ( 9 ): 1711 - 1726 .

SHIRVANIMOGHADDAM M , MOHAMMADI M S , ABBAS R , et al . Short block-length codes for ultra-reliable low latency communications [J ] . IEEE Communications Magazine , 2019 , 57 ( 2 ): 130 - 137 .

BERLEKAMP E , MCELIECE R , VAN TILBORG H . On the inherent intractability of certain coding problems (Corresp.) [J ] . IEEE Transactions on Information Theory , 1978 , 24 ( 3 ): 384 - 386 .

林舒 , 科斯特洛 . 差错控制编码(原书第二版) [M ] . 晏坚, 何元智,潘亚汉, 等译. 北京 : 机械工业出版社 , 2007 .

FOSSORIER M P C , LIN S . Soft-decision decoding of linear block codes based on ordered statistics [J ] . IEEE Transactions on Information Theory , 2006 , 41 ( 5 ): 1379 - 1396 .

WONTERGHEM J V , ALLOUM A , BOUTROS J J , et al . On performance and complexity of OSD for short error correcting codes in 5G-NR [EB/OL ] . ( 2017-01-01 )[ 2024-09-29 ] . https://www.researchgate.net/profile/Amira-Alloum/publication/316840274_On_Performance_and_Complexity_of_OSD_for_Short_Error_Correcting_Codes_in_5G-NR/links/591316d64585152e199a75b6/On-Performance-and-Complexity-of-OSD-for-Short-Error-Correcting-Codes-in-5G-NR.pdf https://www.researchgate.net/profile/Amira-Alloum/publication/316840274_On_Performance_and_Complexity_of_OSD_for_Short_Error_Correcting_Codes_in_5G-NR/links/591316d64585152e199a75b6/On-Performance-and-Complexity-of-OSD-for-Short-Error-Correcting-Codes-in-5G-NR.pdf .

VAN WONTERGHEM J , ALLOUM A , BOUTROS J J , et al . On short-length error-correcting codes for 5G-NR [J ] . Ad Hoc Networks , 2018 , 79 : 53 - 62 .

JIN W Y , FOSSORIER M . Efficient box and match algorithm for reliability-based soft-decision decoding of linear block codes [C ] // 2007 Information Theory and Applications Workshop . Piscataway : IEEE , 2007 : 160 - 169 .

SCHOLL S , STUMM C , WEHN N . Hardware implementations of Gaussian elimination over GF(2) for channel decoding algorithms [C ] // 2013 Africon . Piscataway : IEEE , 2013 : 1 - 5 .

DUFFY K R , LI J G , MÉDARD M . Guessing noise, not code-words [C ] // 2018 IEEE International Symposium on Information Theory (ISIT) . New York : ACM , 2018 : 671 - 675 .

DUFFY K R , LI J G , MÉDARD M . Capacity-achieving guessing random additive noise decoding [J ] . IEEE Transactions on Information Theory , 2019 , 65 ( 7 ): 4023 - 4040 .

SOLOMON A , DUFFY K R , MÉDARD M . Soft maximum likelihood decoding using GRAND [C ] // ICC 2020 - 2020 IEEE International Conference on Communications . Piscataway : IEEE , 2020 : 1 - 6 .

DUFFY K R . Ordered reliability bits guessing random additive noise decoding [C ] // ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing . Piscataway : IEEE , 2021 : 8268 - 8272 .

孔挺 , 余鹏 , 王浩 . 纠三错BCH码改进查找表译码算法研究及其实现 [J ] . 计算机与数字工程 , 2018 , 46 ( 2 ): 247 - 250, 275 .

KONG T , YU P , WANG H . Research and implementation of improved lookup table decoding algorithm for triple-error-correcting BCH code [J ] . Computer & Digital Engineering , 2018 , 46 ( 2 ): 247 - 250, 275 . (in Chinese)

LEE H P , CHANG H C , LIN T C , et al . A weight method of decoding the binary BCH code [C ] // Proceedings of the 2008 Eighth International Conference on Intelligent Systems Design and Applications - Volume 03 . New York : ACM , 2008 : 545 - 549 .

ABBAS S M , JALALEDDINE M , GROSS W J . List-GRAND: A practical way to achieve maximum likelihood decoding [J ] . IEEE Transactions on Very Large Scale Integration (VLSI) Systems , 2022 , 31 ( 1 ): 43 - 54 .

CONDO C , BIOGLIO V , LAND I . High-performance low-complexity error pattern generation for ORBGRAND decoding [C ] // 2021 IEEE Globecom Workshops . Piscataway : IEEE , 2021 : 1 - 6 .

CONDO C . A fixed latency ORBGRAND decoder architecture with LUT-aided error-pattern scheduling [J ] . IEEE Transactions on Circuits and Systems I: Regular Papers , 2022 , 69 ( 5 ): 2203 - 2211 .

ABBAS S M , TONNELLIER T , ERCAN F , et al . High-throughput VLSI architecture for soft-decision decoding with ORBGRAND [C ] // ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing . Piscataway : IEEE , 2021 : 8288 - 8292 .

FAN J L . Constrained Coding and Soft Iterative Decoding [M ] . Boston, MA : Springer US , 2001 .

CHASE D . Class of algorithms for decoding block codes with channel measurement information [J ] . IEEE Transactions on Information Theory , 1972 , 18 ( 1 ): 170 - 182 .

AN W , MÉDARD M , DUFFY K R . CRC codes as error correction codes [C ] // ICC 2021 - IEEE International Conference on Communications . Piscataway : IEEE , 2021 : 1 - 6 .

张国华 , 孙爱晶 , 倪孟迪 , 等 . 无小环大列重QC-LDPC短码的显式构造 [J ] . 电子学报 , 2024 , 52 ( 6 ): 1862 - 1868 .

ZHANG G H , SUN A J , NI M D , et al . Explicit constructions of short QC-LDPC codes free of small cycles and with large column weight [J ] . Acta Electronica Sinica , 2024 , 52 ( 6 ): 1862 - 1868 . (in Chinese)

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research of a Method of Direct Acquisition Based on P Code in Frequency Domain

MAP Estimation for Noisy Speech Enhancement Based on Inter-Frame Correlation

A New Spatial Smoothing Algorithm——Random Spatial Gain Method

Related Author

PAN Cheng-sheng

FENG Yong-xin

TIAN Ming-hao

ZHAO Xiao-hui

OU Shi-feng

ZHOU Zheng

ZHAO Cheng-lin

MAO Fei

Related Institution

Department of AutomatizationNanjing University of TechnologyNanjingJiangsu 210094China

Communication and Network Institute,Shenyang Ligong University

Department of Automatization,Nanjing University of Technology

Communication and Network InstituteShenyang Ligong UniversityShenyangLiaoning110168China

Laboratory of Information Science,College of Communication Engineering,Jilin University

⁰