北京邮电大学学报

计算维数l	1次两两计算加法次数	1次两两计算节约计算量	1次迭代中包含两两计算次数	1次迭代节约计算量
64	8192	6080	800	4.864×10⁶
32	2112

计算维数l	1次两两计算加法次数	1次两两计算节约计算量	1次迭代中包含两两计算次数	1次迭代节约计算量
64	8192	6080	800	4.864×10⁶
32	2112

北斗三号B1C信号多进制LDPC译码改进算法

PDF下载

贾文娟 , 姚高乐 , 陈广通

北京邮电大学学报 | 研究报告 2025,48(5): 167-172

收起

北京邮电大学学报 | 研究报告 2025, 48(5): 167-172

北斗三号B1C信号多进制LDPC译码改进算法

全屏

贾文娟, 姚高乐, 陈广通

作者信息

交通运输部　北海航海保障中心，天津　300220

贾文娟（1988—），女，工程师，邮箱：824845497@qq.com。

M-ary LDPC Decoding Improved Algorithm of BeiDou 3 B1C Signal

Wenjuan JIA, Gaole YAO, Guangtong CHEN

Affiliations

Beihai Navigation Assurance Center, Ministry of Transport, Tianjin 300220, China

doi: 10.13190/j.jbupt.2024-154

文章导航

摘要

收起

针对多进制低密度奇偶校验码（LDPC）译码计算量大且译码复杂度高的问题，基于北斗三号（BD-3）B1C卫星信号特点提出了一种多进制LDPC译码改进算法。该算法一方面采用缩维补边方式，通过缩减校验方程更新过程中两两节点计算维数，来实现译码计算量的减小；另一方面利用节点同时更新方式，在更新校验节点的同时，更新变量节点，从而实现译码复杂度的降低。仿真结果表明，在BD-3 B1C卫星信号接收电平动态范围内，改进算法在不影响译码性能的前提下，缩减了译码计算量，降低了译码复杂度，当以维数为32计算时，1次迭代运算中计算量缩减为原来的25%，同时更新节点算法节省了2万多次数据的存储和读取操作，且随着信噪比（SNR）的提高，可采用更小维数，以进一步降低译码计算量和复杂度。

关键词

B1C信号 / 改进算法 / 缩维补边 / 更新节点

Abstract

收起

Aimingat solving the problems of large amounts of computation and simplifying high complexity of M-ary low density parity check code (LDPC) decoding algorithm, a M-ary LDPC improved decoding algorithm is proposed based on the characteristics of BeiDou-3 (BD-3) B1C satellite signal. On the one hand, the proposed algorithm adopts the dimension reduction and edge complement mode to reduce the calculated amount of decoding algorithm by reducing the calculation dimension between nodes in the updating process of verification equation；On the other hand, to reduce the decoding complexity, the algorithm uses the way in which the nodes update simultaneously, which means the check node updates as the variable node updates. The simulation results show that the improved algorithm reduces the decoding computation and simplifies the decoding algorithm complexity without affecting the decoding performance in the dynamic range of receiving level of BD-3 B1C satellite signals. Compared with before optimization, the calculation amount is reduced to 25% of the original algorithm in one iteration, and 20000 times of data storaging and reading operations are saved when the calculation dimension is 32 by updating the node algorithm. Moreover, with the improvement of signal to noise ratio (SNR), the decoding computation amount and complexity can be more simplified by using smaller dimensions.

Key words

B1C signal / improved algorithm / reduce dimension and supplement edge / update nodes

引用本文

贾文娟, 姚高乐, 陈广通. 北斗三号B1C信号多进制LDPC译码改进算法. 北京邮电大学学报, 2025 , 48 (5) : 167 -172 . DOI: 10.13190/j.jbupt.2024-154

Wenjuan JIA, Gaole YAO, Guangtong CHEN. M-ary LDPC Decoding Improved Algorithm of BeiDou 3 B1C Signal[J]. Journal of Beijing University of Posts and Telecommunications, 2025 , 48 (5) : 167 -172 . DOI: 10.13190/j.jbupt.2024-154

正文

收起

M-ary LDPC Decoding Improved Algorithm of BeiDou 3 B1C Signal

低密度奇偶校验码（LDPC，low density parity check code）是由Gallager博士^[1]于1963年提出的一类具有稀疏校验矩阵的线性分组码，它不仅具有逼近Shannon限的良好性能，而且结构灵活可进行快速并行迭代译码，是近年信道编译码领域研究的热点，已广泛应用于深空通信、光纤通信、卫星通信等领域^[2]。

在北斗三号（BD-3，BeiDou-3）卫星导航通信系统中，信号采用“数据支路+导频支路”的设计方案^[3]。为提高导频支路对弱信号的捕获跟踪性能，信号功率在分配给导频支路的同时，导致数据支路功率减小，因此在BD-3 B1C信号中采用64进制LDPC编译码方式，以提高电文数据的准确性。为更好发挥LDPC码的纠错性能^[4]，多进制LDPC一般采用软判决迭代译码方式，其中概率域置信传播（BP，belief propagation）算法是多进制LDPC译码算法的基础^[5]，适用于各类信道，但其译码复杂度高且与多进制LDPC码的进制数q成指数关系，当B1C信号中q为64时，整个译码过程所需的计算量，硬件几乎无法做到，为了不降低译码性能而简化译码算法，在BP算法的基础上提出了对数似然比（LLR，log likelihood ratio）译码算法，该算法完全消除了乘法运算，但却以增加加法运算和雅可比（Jacobi）运算为代价^[6]。为进一步降低算法复杂度，将LLR算法中的Jacobi运算采用选最大值（max）运算来替代，这种替代的合理性在张誉论文中有详细验证^[7]，由于算法是在BP基础上对LLR算法中的Jacobi运算以max运算来代替，因此也称这种算法为LLR-max-BP算法。

虽然经过多次优化，LLR-max-BP算法已经得到质的飞跃，但多进制LDPC译码复杂度高的另外一个原因，在于每个节点对应的信息不是1维而是q维，并且q维信息都参与校验节点和变量节点的更新^[8]。因此，笔者在LLR-max-BP算法的基础上根据BD-3 B1C卫星信号特征，对校验节点更新过程中的64维信息进行降序排列处理后，选择前l维信息参与节点运算，这样使得每个校验节点更新过程中的计算量缩减为原来的l/64，另外在完成校验节点更新的同时完成变量节点更新^[9]，由于变量节点不再单独更新，从而节省了中间大量重复的存储和读取工作，使得译码迭代速度大大提升。

1　LLR-max-BP算法原理

收起

LDPC码通常由1个校验矩阵H确定^[10]，它包含2类节点，一类是变量节点，节点个数为分组码的码长，等于H矩阵中的列数N；另一类是校验节点，表示分组码中每个变量节点之间的约束关系，通常也称为校验方程，校验方程个数为分组码的校验节点信息长度，即H矩阵的行数M。给定1个稀疏的奇偶校验矩阵H，它就确定了信息序列和校验序列之间的校验关系。

因此，LDPC译码的核心就是围绕校验矩阵H在行方向和列方向上做周而复始的迭代运算，通过信息在校验节点与变量节点之间的来回传递，实现对接收电文的差错控制^[11-12]。以B1C北斗民用导航信号第1版（B-CNAV1，BeiDou civil navigation signal version 1）电文格式子帧2为例，64进制LDPC（200，100）校验矩阵H是固定不变的，其行数M为100，列数N为200，每行非零元素个数d_c =4，每列非零元素个数d_v =2，每个节点包含q（q =64）个信息，其LLR-max-BP译码算法具体步骤如下。

步骤1 初始化各节点对数似然比L（

）

其中：n指某列信息，

表示第n列节点取值为t（t的取值范围为0～q）时对应的初始概率，

表示第n列节点取值为t时对应的初始对数似然比^[13]。

步骤2 转置与逆转置运算

转置运算^[14]是将节点信息与校验矩阵H中非零元素h_mn进行伽罗华域上的乘法运算，反之逆转置是进行伽罗华域上的除法运算，即与校验矩阵H中的非零元素

相乘。其中，h_mn为H矩阵中第m行n列的非0元素，

为非0元素h_mn的倒数。

步骤3 更新校验节点向变量节点传递的信息

其中：

为译码过程中第m行n列节点取值为t时更新校验节点向变量节点传递的信息，

为第m行n列节点取值为t时对应的校验节点对数似然比。

为简化上述算法，定义2个部分和为

则式（2）可简化为

其中：将α_m（n-_1）+ β_m（n+_1）称为两两计算，更新完1个校验方程的所有节点需要d_c（d_c-2）次两两计算，每次两两计算又包括q²次普通域概率加法、q²次伽罗华域加法和q²次选大运算（α_m（n-_1）和β_m（n+_1）均为q维）。

步骤4 更新变量节点向校验节点传递的信息

其中：

为译码过程中第m行n列节点取值为t时对应的变量节点似然比，

为第m行n列节点取值为t时更新变量节点向校验节点传送的信息。变量节点更新需要在所有校验节点更新完成后才可进行，因此在每个校验节点更新完成后需要将结果暂存在存储器中，等待所有校验节点更新完成后，再将结果从存储器中读出，经过式（5）计算后，再次存入存储器以供下次迭代使用。

步骤5 计算节点概率，并进行判决：

经计算判决后得到码子序列C ={x_n}，利用CH^T =0^T验证是否满足条件，如果等式成立，译码结束，否则继续迭代运算。

2　LLR-max-BP改进算法

收起

对LLR-max-BP译码原理分析可知，基于信度传播的迭代译码算法，复杂度主要集中在步骤3校验节点与步骤4变量节点的更新上，其中校验节点更新过程中消耗大量的运算资源，变量节点更新过程中需要大量的存储和读取操作。因此，对LLRmax-BP算法的改进考虑缩小校验节点更新的维数，但又要确保译码性能不受影响，因此在缩小节点更新维度的前提下，采用补边算法补充受损的译码性能，即针对校验节点的更新改进算法采用缩维补边的方法；同时经过对LLR-max-BP算法的研究可知，变量节点更新的实质是每个信息位除去本节点外，其他节点似然比的和与该信息位的初始似然比

相加。因此，利用BD-3 B1C信号中64进制LDPC编译码方式的H矩阵中列重为2的特点，将变量节点更新融合在校验节点更新过程中，从而实现对LLR-max-BP算法的改进与优化。

2.1　校验节点缩维补边算法

校验方程是由校验节点构成，每个校验节点对应校验方程中的1个未知数，因此校验节点更新的实质是求解校验方程中每个未知数的q维元素中概率最大的元素（每个元素都对应1个概率）。在BD-3B1C卫星信号接收端，对于LDPC译码来说，其信噪比是很高的（受前端捕获和跟踪灵敏度限制），校验方程中每个未知数的可能取值会很快收敛，即其所对应的概率值会很快变大且持续保持，在后续迭代过程中未知数元素的可能取值只在概率相对较大的取值中变动，而对应概率较小的元素基本不变且不会影响未知数的求解。因此，经过研究分析提出了采用缩维补边方法对校验方程更新过程中的两两计算进行优化。先将q维元素以其对应概率大小为依据进行降序排列，选取排列后前l维元素进行两两计算，因此将参与运算节点维数由原来的q维缩减为l维，为不影响译码性能和迭代速度，在利用l维计算时采用补边方法，确保校验节点两两计算后能够得到完整的q维结果，两两计算具体如下。

1）排序，在进行两两计算前分别对α_m（n-_1）和β_m（n+_1）的q维元素的可能取值以概率大小为依据进行降序排列。

2）缩维，选取α_m（n-_1）排列后的前l维元素及其概率值与β_m（n+_1）的前l维元素及其概率值，进行普通域上的概率加法运算和伽罗华域上的元素加法运算，得到l²个元素结果和概率结果。

3）补边，α_m_（_n_-1）（1）与β_m_（_n_+1）（l+ 1～q）的q-l维元素进行普通域上的概率运算和伽罗华域上的加法运算，得到q-l个结果。确保最终l² + q-l个结果中包含所有q维元素。在计算得到的l² + q-l个结果中只有q维元素是互不相同的，即每个元素可能出现1次或多次，同样也对应1个或多个概率结果。

4）筛选，每个元素从其对应的1个或多个概率值中经过比较，选取概率值最大的作为其对应的概率，最后得到q维结果后完成1次两两计算。

经过优化后每个两两计算量由原来的q²次概率加法运算和q²次伽罗华域运算简化为l²+q-l次，具体如图1所示。

优化前1次两两计算计算量为图1左斜杠q²面积，优化后计算量简化为右斜杠面积加最上面1行即l² +q-l。

2.2　2节点同时更新算法

根据式（5）可知，变量节点更新的实质是每个信息位除去本节点外，其他节点似然比的和与该信息位的初始似然比

相加。由于BD-3 B1C卫星信号校验矩阵H列重d_v为2，变量节点在更新时按照式（5）除去其本身节点外，就等于另外1个节点的似然比

与该信息位的初始似然比

相加。因此，针对B1C信号列重为2的特点，可将变量节点更新过程简化为该信息位的另外1个节点似然比与其初始似然比之和，即在更新完校验节点后将其似然比与该信息位的初始似然比相加，就得到该信息位对应的另外1个变量节点的更新值。在更新完校验节点后也完成了变量节点的更新，从而节省了中间大量的存储和读取操作。以第20位信息位为例，举例说明优化后变量节点的更新过程。

在H矩阵第20列上对应的非零元素有2个，分别是m为18和78，涉及到第20位信息位的节点是

和

，在更新变量节点

时，使用的是

校验节点更新完后的似然比值与初始似然比

之和；在更新变量节点

时，使用的是

校验节点更新完后的似然比与初始似然比

之和。因此，将

校验节点更新完后的似然比与初始似然比

之和，直接存储在节点

的存储位置；

校验节点更新完后的似然比与初始似然比

之和，存储在节点

的存储位置。在下次迭代更新校验节点

时，从节点

的存储器中读取数据；更新校验节点

时，从节点

的存储器中读取数据，从而实现2节点同时更新。

2.3　改进后LLR-max-BP算法

对LLR-max-BP算法改进后，译码基本原理未发生变化，仍是通过置信度在校验节点与变量节点之间的传递来实现，但在校验节点更新过程中，采用缩维补边算法，将q维元素对应的概率值降序排列，使得有效的校验信息排列在序列前列（概率值越大，校验信息有效性越高），选取排列后的前l维元素进行两两计算，采用补边算法，确保校验节点在两两计算后得到完整的q维结果，通过对校验节点更新过程的优化，使得1次两两计算的计算量缩减为原来的l/q倍，l越小，计算量缩减得越多。另外，根据BD-3 B1C卫星信号校验矩阵H列重d_v为2的特点，采用2节点同时更新算法，在校验节点更新过程中完成变量节点的更新，从而节省了译码过程中大量的读取和存储操作。经过对校验节点和变量节点更新过程的优化，使得译码复杂度和计算量都有很大简化，优化后译码整体流程如图2所示。

3　性能仿真与分析

收起

对于BD-3 B1C子帧2信号的64进制LDPC（200，100），H矩阵中包含100个校验方程，每个校验方程包含4个校验节点，每个校验节点更新过程中包含2个两两计算，因此1次译码迭代需要计算的两两次数为800。当l取值为32时，校验节点采用缩维补边优化后，1次迭代运算节约计算量约为4.864×10⁶，计算量缩减为原来的1/4，在接收信噪比为2.35dB时，优化前后译码性能不受影响。具体如表1所示。

2节点同时更新算法简化的是译码复杂度，完成1次译码迭代节约了25600（2×64×200，2为每个信息位对应的节点数，即H矩阵的列数，64为更新完成后每个节点的维数，200为共200个信息位）次数据的重复读取和存储，加上校验节点的优化使得1次译码迭代时间变为原来的1/3。

对优化后的LLR-max-BP算法性能进行仿真分析，仿真结果如图3所示。

图3中维数l=64为优化前LLR-max-BP译码误码率，维数l=16和l=32为优化后LLR-max-BP译码误码率，从曲线图3中可以看出，当l取值为32，信噪比取值范围在2.1～2.5dB（针对BD-3 B1C信号接收电平为-149.9～-149.5dBm，其中包括2dB前端噪声系数）时，误码率与未优化相比（l取值为64未优化时）基本没有差别。由于蒙特卡洛仿真的波动，优化后偶尔有个别点低于优化前，但不影响整体趋势。当l取值为16，信噪比低于2.35时，误码率与其他2者相比略有差别，但信噪比高于2.35时不论l取值为16，32还是64，3者的误码率基本没有差别。

从图4整体仿真结果可以看出，当信噪比越高时，l整体的取值越小。图4中横坐标为l维数，纵坐标为误码率值，如果指标要求误码率为1×10 ^-4，当信噪比为2（以圈为标记的曲线）时，l的取值大约为25，当信噪比为3（以米为标记的曲线）时，l的取值为5，当信噪比为4（以小三角为标记的曲线）时，l的取值为3。由此可知，在指标要求误码率范围内，随着信噪比提升，校验节点两两计算维数l可适当减小，从而可进一步简化计算量，缩短译码时间，提升译码速度。

4　结束语

收起

笔者以LLR-max-BP译码算法为基础，针对B1C卫星信号特点，对校验节点更新过程采取缩维补边方法进行优化，通过缩减两两节点计算维数，实现对译码计算量的大幅缩减，优化后1次译码迭代运算减少了约4.864×10⁶次加法运算，同时采用补边方式确保校验节点更新完成后维数q保持不变。经过仿真验证分析，当维数l取值为32，译码信号接收电平为-149.9～-149.5dBm时，采取校验节点缩维补边算法，可在保证译码性能不受损失的前提下，节约大量加法运算；同时对变量节点更新过程进行优化，利用校验节点与变量节点同时更新，1次译码迭代中省去了约2.56万次数据的存储和读取，实现对译码复杂度的降低和译码读写时序的简化，从而加快译码迭代速度。另外，译码节点更新维数l可根据信噪比的变化而进行动态调整，空间信号接口控制文件规定倾斜地球同步轨道（IGSO，inclined geo synchronous orbit）卫星发射的B1C信号，到达地面接收最小功率电平为-145dBm（-145dBm为折算到导频之路的信号功率），与仿真-149.9dBm相比仍有将近5dB余量，因此在BD-3实际应用中l可采用更小维数以进一步降低译码计算量和复杂度。

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

GALLAGER

R G

. Low-density parity-check codes[M]. Cambridge: MIT Press, 2003: 70-81.

[2]

王鑫尧.面向深空通信的多进制LDPC译码算法研究及实现[D].电子科技大学,2022.

WANG

X Y

. Research and implementation of multi-base LDPC decoding algorithms for deep space communication[D]. University of Electronic Science and Technology of China,2022.

[3]

宿晨庚,郭树人,刘旭楠,等.北斗三号基本系统空间信号质量评估[J].电子与信息学报, 2020, 42(11): 2689-2697.

C G

, GUO

S R

, LIU

X N

, et al. Quality assessment of BeiDou-3 basic system space signals[J]. Journal of Electronics and Information Technology, 2020, 42(11):2689-2697.

[4]

SHU

Y Q

, ZHANG

L F

, HU

Z R

, et al. Research and performance evaluation of 64-ary LDPC decoding algorithm for hardware implementation[J]. Radio Engineering, 2022, 52(4): 657-663.

[5]

程志强.基于变量节点可靠度的LDPC译码调度算法研究[D].华中科技大学,2023.

CHENG

Z Q

. Research on LDPC decoding scheduling algorithms based on variable node reliability[D]. Huazhong University of Science and Technology,2023.

[6]

巨策划.多进制LDPC码的构造与译码算法研究[D].西安电子科技大学,2009.

C H

. Research on the construction and decoding algorithms of multi-base LDPC codes[D]. Xi'an University of Electronic Science and Technology,2009.

[7]

张誉.多进制LDPC码译码算法的研究[D].国防科学技术大学,2011.

ZHANG

. Research on decoding algorithms for multi base LDPC codes[D]. National University of Defense Technology,2011.

[8]

YOON

, KIM

S Y

. LDPC decoding with low complexity for OFDM index modulation[J]. IEEE Access, 2021(9):68435-68444.

[9]

BENHAYOUN

, RAZI

, MANSOURI

. Low-complexity LDPC decoding algorithm based on layered vicinal variable node scheduling[J]. Modelling and Simulation in Engineering Volume, 2022, 78(4): 23-56.

[10]

, LI

, FANG

. An improved 5G NR LDPC decoding algorithm based on box-plus operation[C]//2022 IEEE/CIC International Conference on Communications in China (ICCC), IEEE, 2022: 110-114.

[11]

CHEN

H Q

, WANG

Y L

, WEI

W J

. Two sign-flipped multivariate LDPC decoding algorithms with reduced complexity[J]. Journal of Electronics and Information Technology, 2021, 43(1): 51-59.

[12]

李锦明,王国栋. CCSDS标准下LDPC码的编译码算法研究[J].电子学报, 2020, 48(11): 2114-2121.

J M

, WANG

G D

. Research on coding and decoding algorithm of LDPC code under CCSDS standard[J]. Electronic Journals, 2020, 48(11): 2114-2121.

[13]

赵亚通.多进制LDPC码译码技术的研究[D].北京邮电大学,2023.

ZHAO

Y T

. Research on decoding techniques for nonbinary LDPC codes[D]. Beijing University of Posts and Telecommunications,2023.

[14]

王瑞雪.多进制LDPC码编译码算法实现[D].天津大学,2021.

WANG

R X

. Implementation of multi-base LDPC coding and decoding algorithms[D]. Tianjin University,2021.

2025年第48卷第5期

PDF下载

103

引用本文

BibTeX

文章信息

doi: 10.13190/j.jbupt.2024-154

接收时间：2024-07-17
首发时间：2026-04-16

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-07-17

基金

作者信息

交通运输部　北海航海保障中心，天津　300220

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/bjyddxxb/CN/10.13190/j.jbupt.2024-154

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT