CN110233628B - 极化码的自适应置信传播列表译码方法 - Google Patents
极化码的自适应置信传播列表译码方法 Download PDFInfo
- Publication number
- CN110233628B CN110233628B CN201910427731.7A CN201910427731A CN110233628B CN 110233628 B CN110233628 B CN 110233628B CN 201910427731 A CN201910427731 A CN 201910427731A CN 110233628 B CN110233628 B CN 110233628B
- Authority
- CN
- China
- Prior art keywords
- decoding
- max
- factor graph
- list
- belief propagation
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 63
- 241000169170 Boreogadus saida Species 0.000 title claims abstract description 20
- 230000003044 adaptive effect Effects 0.000 title claims abstract description 20
- 125000004122 cyclic group Chemical group 0.000 claims abstract description 22
- 239000011159 matrix material Substances 0.000 claims description 26
- 238000013507 mapping Methods 0.000 claims description 6
- 230000010287 polarization Effects 0.000 claims 4
- 230000035772 mutation Effects 0.000 claims 1
- 230000002688 persistence Effects 0.000 claims 1
- 230000000694 effects Effects 0.000 abstract description 4
- 238000010276 construction Methods 0.000 description 3
- 238000005265 energy consumption Methods 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 3
- 238000005457 optimization Methods 0.000 description 2
- 241000894007 species Species 0.000 description 2
- 230000005540 biological transmission Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 239000013589 supplement Substances 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/09—Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
本发明公开了一种极化码的自适应置信传播列表译码方法,首先根据接收端拥有的BP译码器数量,确定该方法的最大列表数,通过高斯近似方法进行计算获得能取得较好译码效果的BP译码因子图,然后对列表中记录的BP译码器选定不同的BP译码因子图进行译码,对译码结果进行排序后进行循环冗余校验,若存在通过循环冗余校验的结果则译码成功并停止译码,否则自动调整列表大小,将列表数扩大为原来的两倍,继续使用列表中的BP译码器进行译码。
Description
技术领域
本发明涉及一种极化码的自适应置信传播列表译码方法,属于无线通信中的信道编码技术领域。
背景技术
极化码技术作为一种新型的信道编码技术,在码长趋于无穷时,传输速率能达到在二进制输入无记忆对称信道的信道容量。目前极化码较为主流的译码方式有两类,一类基于串行抵消(Successive Cancellation,SC)译码方法,包括了基于SC译码的串行抵消列表(Successive Cancellation List,SCL)译码方法,基于SC的极化码译码方法属于序贯译码,已经译出的信息比特对后续信息比特的估计产生影响,因此必须逐个估计码字中的信息比特,由此产生了较大的译码时延。极化码的另外一类主流译码方法基于置信传播(Belief Propagation,BP)译码方法,包括置信传播列表(Belief Propagation List,BPL)译码方法,基于BP的译码方法由于其并行迭代计算的性质,其译码时延显著低于基于SC的译码方法并且对码字长度不敏感,因此BP译码方法适用于对时延要求较高的应用场景。但是传统的BP译码方法误码率和误帧率性能较差,BPL译码方法在BP译码方法的基础上提高了误码率和误帧率性能,但是带来了更高的计算复杂度和硬件要求。
发明内容
本发明提供一种极化码的自适应置信传播列表译码方法,使用的码字是循环冗余校验(Cyclic Redundancy Check,CRC)码和极化码形成的级联码。自适应置信传播列表译码方法的列表用于记录能同时进行译码的BP译码器,列表数定义为列表中的BP译码器数目,最大列表数定义为能同时进行译码的BP译码器数量上限。
本发明中提出的自适应置信传播列表译码方法,首先根据接收端拥有的BP译码器数量,确定该方法的最大列表数,通过高斯近似方法进行计算获得能取得较好译码效果的BP译码因子图,然后对列表中记录的BP译码器选定不同的BP译码因子图进行译码,对译码结果进行排序后进行循环冗余校验,若存在通过循环冗余校验的结果则译码成功并停止译码,否则自动调整列表大小,将列表数扩大为原来的两倍,继续使用列表中的BP译码器进行译码。
现有的BP译码方法误码率和误帧率性能较差,而BPL译码方法采用多个BP译码器同时进行译码的方法,以更高的计算复杂度和硬件能耗为代价提高了误码率和误帧率性能。极化码的自适应置信传播列表译码方法相较BP译码方法和BPL译码方法而言获得了更好的误码率和误帧率性能,并且为完成译码所需的列表数在中高信噪比条件下所需的列表数显著小于BPL译码方法的列表数。这说明极化码的自适应置信传播列表译码方法在中高信噪比条件下需要启动的BP译码器数目显著少于采用恒定列表数的BPL译码方法,从而达到显著降低计算复杂度,降低硬件能耗的效果。
本发明为解决上述技术问题采用以下技术方案:
本发明提供一种极化码的自适应置信传播列表译码方法,包括以下步骤:
第一步:初始化允许的最大列表数Lmax,构造用于BP译码的2Lmax-1种因子图对应的置换矩阵permutation_matrix,具体为:
(1)根据接收端拥有的BP译码器数量,自主确定最大列表数Lmax;
(2)缩小所需置换因子图的搜索范围:对于码长为N=2n的极化码,在编码时需要经过n个编码阶段{l0,...,ln-1},译码时采用的因子图与L={l0,l1,...,ln-1}中元素的全排列为一一映射关系;定义参数k,使k满足条件:(n-k)!≥Lmax,记集合L的一个子集为Lh={lk,lk+1,...,ln-1},获取集合Lh中元素的(n-k)!种全排列,再在每种排列前均加上顺序不变的前k个编码阶段{l0,l1,...,lk-1},从而得到集合L中所有元素的(n-k)!种排列,由因子图与L中元素排列的一一映射关系即得到对应的(n-k)!种因子图,从而将置换因子图的搜索范围缩小为(n-k)!种;
(3)从置换因子图搜索范围中选出需要的因子图:对于步骤(2)中得到的集合L中所有元素的(n-k)!种排列,分别计算对应的因子图在高斯近似方法下得到的误帧率,选出其中误帧率最小的2Lmax-1种因子图;
(4)构造2Lmax-1种因子图对应的置换矩阵permutation_matrix:构造出2Lmax-1行n列的置换矩阵permutation_matrix,permutation_matrix中的每一行对应步骤(3)中选出的2Lmax-1种集合L的全排列中的一种;
第二步,进行极化码的自适应置信传播列表译码,具体为:
(A)初始化:初始化当前能同时进行极化码的置信传播译码的BP译码器数量l=1;
(B)利用l个独立的BP译码器同时进行BP译码,每个BP译码器采用permutation_matrix中尚未使用过的1行元素对应的因子图分别独立地进行BP译码,BP译码器的输出结果为和计算出每个译码器得出的码字估计与接收信号之间的欧式距离d,其中,是对信息比特ui的估计,是对信息比特ui经过级联编码后得到的码字比特xi的估计,yi表示接收信号的第i个比特;
(D)对步骤(C)中排序过的l组信息比特估计逐个进行循环冗余校验:如果当前待校验的译码结果满足循环冗余校验,则自适应置信传播列表译码方法译码成功,返回该译码结果,整个译码流程结束;否则对下一组信息比特估计进行循环冗余校验,若l组信息比特估计均未通过循环冗余校验,则转入步骤(E);
作为本发明的进一步优化方案,步骤(1)中k的取值由接收端根据自身计算能力和时延要求自行确定。
本发明采用以上技术方案与现有技术相比,具有以下技术效果:本发明中的极化码的自适应置信传播列表译码方法先将列表数设定为较小的值,再对现有列表中的译码结果进行循环冗余校验,并且在循环冗余校验失败后加大列表数继续进行译码。相比于传统的BP译码方法,极化码的自适应置信传播列表译码方法显著改善了误码率和误帧率性能,并且在中高信噪比区间内的平均译码时延与计算复杂度仅略高于传统BP译码方法。相比现有的BPL译码方法,极化码的自适应置信传播列表译码方法提高了误码率和误帧率性能,并且逐步增加列表数的方式避免了在BPL译码方法中大量不必要的计算和硬件能耗,在中高信噪比区间内,能将计算复杂度降低一个数量级,以接近传统BP译码方法的计算复杂度和硬件能耗开销获得超过BPL译码方法的误码率性能。这说明本发明中的方法能够以较小的译码时延为代价获取误码率性能的增益和计算复杂度的简化。
附图说明
图1是极化码的自适应置信传播列表译码方法流程图;
图2是码长为8,包含3个编码阶段(l0、l1、l2)的3种不同因子图的示意图,其中,(a)是依次经过l2、l0、l1的因子图,(b)是依次经过l1、l2、l0的因子图,(c)是依次经过l1、l0、l2的因子图。
具体实施方式
下面结合附图对本发明的技术方案做进一步的详细说明:
本发明中极化码的自适应置信传播列表译码方法,以码长N=2048,信息比特数K=1024,循环冗余校验码长度r=8为例进行说明。本例中的极化码的构造方法为高斯近似,码字构造信噪比为2.5分贝,循环冗余校验码的生成多项式为g(x)=x8+x6+x3+x2+1。
如图1所示,包括如下步骤:
第一步:初始化允许的最大列表数Lmax(本例中Lmax=4),构造用于BP译码的2Lmax-1(本例中2Lmax-1=7)种因子图对应的置换矩阵permutation_matrix。本步骤包括如下流程:
(1)根据接收端拥有的BP译码器数量,自主确定最大列表数Lmax。转入步骤(2)。
(2)缩小所需置换因子图的搜索范围(置换因子图是已有的概念,本步骤简述构造方法)。对于码长为N=2n的极化码,在编码时需要经过n个编码阶段{l0,...,ln-1},记集合L={l0,l1,...,ln-1}。译码时采用的因子图与L中元素的全排列为一一映射关系,如图2表示n=3时的三种不同的因子图。集合L中元素的全排列共有n!种,因此共有n!种不同的译码因子图。定义参数k,使k满足条件:(n-k)!≥Lmax,(k的取值关系到因子图搜索范围的大小,具体取值可由接收端根据自身计算能力和时延要求自行确定)。记集合L的一个子集为Lh,Lh={lk,lk+1,...,ln-1}。获取集合Lh中元素的(n-k)!种全排列,再在每种排列前均加上顺序不变的前k个编码阶段{l0,l1,...,lk-1},从而得到集合L中所有元素的(n-k)!种排列,由因子图与L中元素排列的一一映射关系即可得到对应的(n-k)!种因子图。这就完成了置换因子图的搜索范围由原来的n!种缩小为现在的(n-k)!种。转入步骤(3)。
(3)从置换因子图搜索范围中选出需要的因子图。对于步骤(2)中得到的集合L中所有元素的(n-k)!种排列,分别计算对应的因子图在高斯近似方法下得到的误帧率,选出其中误帧率最小的2Lmax-1种因子图对应的集合L中所有元素的排列。转入步骤(4)。
(4)构造所需的因子图对应的置换矩阵permutation_matrix。构造出大小为2Lmax-1行n列的置换矩阵permutation_matrix,permutation_matrix中的每一行对应步骤(3)中选出的2Lmax-1种集合L的全排列中的一种。本流程结束。本例中的permutation_matrix为如下所示的一个大小为7行11列的矩阵:
第二步:进行极化码的自适应置信传播列表译码。本步骤包括如下流程:
(2)同时启动l个BP译码器按照不同的因子图进行译码。记和为BP译码器的输出结果,其中是指对信息比特ui的估计,是对信息比特经过级联编码后得到的码字比特xi的估计。利用l个独立的BP译码器同时进行BP译码,每个BP译码器采用permutation_matrix中尚未使用过的1行元素对应的因子图分别独立地进行BP译码。计算出每个译码器得出的码字估计与接收信号之间的欧式距离d,转入步骤(3)。
(4)对步骤(3)中排序过的l组信息比特估计逐个进行循环冗余校验。若当前待校验的译码结果满足循环冗余校验,则自适应置信传播列表译码方法译码成功,返回该译码结果,整个译码流程结束。否则对下一组信息比特估计进行循环冗余校验。若l组信息比特估计均未通过循环冗余校验,则转入步骤(5)。
本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代,但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。
Claims (3)
1.极化码的自适应置信传播列表译码方法,其特征在于,包括以下步骤:
第一步:初始化允许的最大列表数Lmax,构造用于BP译码的2Lmax-1种因子图对应的置换矩阵permutation_matrix,具体为:
(1)根据接收端拥有的BP译码器数量,自主确定最大列表数Lmax;
(2)缩小所需置换因子图的搜索范围:对于码长为N=2n的极化码,在编码时需要经过n个编码阶段{l0,...,ln-1},译码时采用的因子图与L={l0,l1,...,ln-1}中元素的全排列为一一映射关系;定义参数k,使k满足条件:(n-k)!≥Lmax,记集合L的一个子集为Lh={lk,lk+1,...,ln-1},获取集合Lh中元素的(n-k)!种全排列,再在每种排列前均加上顺序不变的前k个编码阶段{l0,l1,...,lk-1},从而得到集合L中所有元素的(n-k)!种排列,由因子图与L中元素排列的一一映射关系即得到对应的(n-k)!种因子图,从而将置换因子图的搜索范围缩小为(n-k)!种;
(3)从置换因子图搜索范围中选出需要的因子图:对于步骤(2)中得到的集合L中所有元素的(n-k)!种排列,分别计算对应的因子图在高斯近似方法下得到的误帧率,选出其中误帧率最小的2Lmax-1种因子图;
(4)构造2Lmax-1种因子图对应的置换矩阵permutation_matrix:构造出2Lmax-1行n列的置换矩阵permutation_matrix,permutation_matrix中的每一行对应步骤(3)中选出的2Lmax-1种集合L的全排列中的一种;
第二步,进行极化码的自适应置信传播列表译码,具体为:
(A)初始化:初始化当前能同时进行极化码的置信传播译码的BP译码器数量l=1;
(B)利用l个独立的BP译码器进行BP译码,每个BP译码器采用permutation_matrix中尚未使用过的1行元素对应的因子图分别独立地进行BP译码,BP译码器的输出结果为和计算出每个译码器得出的码字估计与接收信号之间的欧式距离d,其中,是对信息比特ui的估计,是对信息比特ui经过级联编码后得到的码字比特xi的估计,yi表示接收信号的第i个比特;
(D)对步骤(C)中排序过的l组信息比特估计逐个进行循环冗余校验:如果当前待校验的译码结果满足循环冗余校验,则自适应置信传播列表译码方法译码成功,返回该译码结果,整个译码流程结束;否则对下一组信息比特估计进行循环冗余校验,若l组信息比特估计均未通过循环冗余校验,则转入步骤(E);
2.根据权利要求1所述的极化码的自适应置信传播列表译码方法,其特征在于,步骤(1)中k的取值由接收端根据自身计算能力和时延要求自行确定。
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN201910427731.7A CN110233628B (zh) | 2019-05-22 | 2019-05-22 | 极化码的自适应置信传播列表译码方法 |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN201910427731.7A CN110233628B (zh) | 2019-05-22 | 2019-05-22 | 极化码的自适应置信传播列表译码方法 |
Publications (2)
Publication Number | Publication Date |
---|---|
CN110233628A CN110233628A (zh) | 2019-09-13 |
CN110233628B true CN110233628B (zh) | 2023-01-17 |
Family
ID=67860966
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN201910427731.7A Active CN110233628B (zh) | 2019-05-22 | 2019-05-22 | 极化码的自适应置信传播列表译码方法 |
Country Status (1)
Country | Link |
---|---|
CN (1) | CN110233628B (zh) |
Families Citing this family (5)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN110798284B (zh) * | 2019-11-25 | 2022-01-21 | 安徽大学 | 一种基于双bp译码图并行译码技术的极化码传输方法 |
CN111446973B (zh) * | 2020-04-17 | 2022-03-25 | 北京交通大学 | 基于多翻转比特集合的极化码置信传播译码方法 |
CN112953559B (zh) * | 2021-02-08 | 2022-11-08 | 东南大学 | 基于冻结位对数似然值修正的极化码译码方法 |
CN114285419A (zh) * | 2021-12-17 | 2022-04-05 | 扬州大学 | 一种自适应码长低复杂度bpl译码器 |
CN114448575B (zh) * | 2022-03-17 | 2024-02-06 | 东南大学 | 基于动态拷贝映射的极化码重传译码方法 |
Citations (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN105897379A (zh) * | 2016-04-08 | 2016-08-24 | 哈尔滨工业大学深圳研究生院 | 一种极化码级联空时码系统及其级联极化码编码方法 |
CN107659318A (zh) * | 2017-11-07 | 2018-02-02 | 东南大学 | 一种自适应的极化码译码方法 |
CN108462560A (zh) * | 2018-03-26 | 2018-08-28 | 西安电子科技大学 | 一种用于极化码级联的编译码方法 |
-
2019
- 2019-05-22 CN CN201910427731.7A patent/CN110233628B/zh active Active
Patent Citations (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN105897379A (zh) * | 2016-04-08 | 2016-08-24 | 哈尔滨工业大学深圳研究生院 | 一种极化码级联空时码系统及其级联极化码编码方法 |
CN107659318A (zh) * | 2017-11-07 | 2018-02-02 | 东南大学 | 一种自适应的极化码译码方法 |
CN108462560A (zh) * | 2018-03-26 | 2018-08-28 | 西安电子科技大学 | 一种用于极化码级联的编译码方法 |
Non-Patent Citations (2)
Title |
---|
Belief Propagation Bit-Flip Decoder for Polar Codes;YONGRUN YU等;《IEEE Access》;20190110;第10937-10946页 * |
极化码置信传播算法早期终止准则的研究;邢超等;《信号处理》;20160331;第32卷(第3期);第253-259页 * |
Also Published As
Publication number | Publication date |
---|---|
CN110233628A (zh) | 2019-09-13 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
CN110233628B (zh) | 极化码的自适应置信传播列表译码方法 | |
CN110278002B (zh) | 基于比特翻转的极化码置信传播列表译码方法 | |
US7539920B2 (en) | LDPC decoding apparatus and method with low computational complexity algorithm | |
CN107241106A (zh) | 基于深度学习的极化码译码算法 | |
CN100425000C (zh) | 双涡轮结构低密度奇偶校验码解码器及解码方法 | |
CN103929210B (zh) | 一种基于遗传算法与神经网络的硬判决译码方法 | |
CN105763203B (zh) | 一种基于硬可靠度信息的多元ldpc码译码方法 | |
CN109842418A (zh) | 一种基于比特翻转的极化码置信传播译码方法 | |
CN109921803B (zh) | 基于神经网络的高密度线性分组码译码方法 | |
CN108847848A (zh) | 一种基于信息后处理的极化码的bp译码算法 | |
CN114421971A (zh) | 一种适用于多元ldpc码的动态多符号翻转译码方法 | |
CN112929035B (zh) | 一种非二进制极化码的编码与译码方法 | |
CN116760425A (zh) | 一种ldpc码的crc辅助osd译码方法 | |
CN111130567B (zh) | 添加噪声扰动和比特翻转的极化码置信传播列表译码方法 | |
CN110739977B (zh) | 一种基于深度学习的bch码译码方法 | |
CN103220007B (zh) | 一种自适应调整子码不可靠位数的tpc迭代译码算法 | |
CN113556135B (zh) | 基于冻结翻转列表的极化码置信传播比特翻转译码方法 | |
CN110995279A (zh) | 一种极化码联合scf球形列表翻转译码方法 | |
CN106452675A (zh) | 一种极化码的球形译码方法 | |
CN101552613A (zh) | 基于外信息符号变化的低密度校验码译码方法 | |
CN106877883A (zh) | 一种基于受限玻尔兹曼机的ldpc译码方法和装置 | |
CN115378443B (zh) | 一种低精度的深度神经网络极化码sc译码算法 | |
CN113014271B (zh) | 一种缩小翻转集的极化码bp译码方法 | |
CN113872614B (zh) | 一种基于深度神经网络的里德-所罗门码译码方法及系统 | |
CN113285722B (zh) | 一种短极化码的多偏差分段冗余校验辅助统计译码方法 |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
PB01 | Publication | ||
PB01 | Publication | ||
SE01 | Entry into force of request for substantive examination | ||
SE01 | Entry into force of request for substantive examination | ||
GR01 | Patent grant | ||
GR01 | Patent grant |