助力5G的LDPC信道编码技术,基于迭代编码算法的交集构造算法

原标题:【学术论文】基于迭代编码算法的混合构造算法

▲ 点击关注,每日推送不同角度的科技解读

定义

皇家赌场hj883官网 1

LDPC码定义

皇家赌场hj883官网 2

规则码和非规则码

皇家赌场hj883官网 3

(n, j, k)

摘要:

皇家赌场hj883官网 4

LDPC是一种信道编码方式

皇家赌场hj883官网 5

LDPC是一种信道编码方式

皇家赌场hj883官网 6

本质是增加通信可靠性

为了确保第五代移动通信(5G)技术的可靠性、稳定性、高传输速率的优势,基于具有线性编码复杂度的迭代编码算法,提出了混合校验矩阵构造算法。该算法首先对传统迭代编码算法进行改进,使其适用于多元低密度奇偶校验(NB-LDPC)码;然后采用后向迭代法改变编码方案和校验矩阵构造方式使渐进边增长(PEG)算法具有下三角结构,并将其作为基矩阵;最后采用改进后具有下三角结构的QC-LDPC算法生成循环移位矩阵和有限域系数矩阵,同时消除短环影响,从中选取最优的校验矩阵。仿真结果表明,混合构造算法所构造的多元LDPC码不仅具有线性的编码和存储复杂度,且有较强的纠错能力。

5G 信道编码 3GPP
LDPC Turbo Polar
共计2440 字 | 建议阅读时间 6 分钟

LDPC是一种线性分组码

皇家赌场hj883官网 7

线性分组码

皇家赌场hj883官网 8

LDPC是一种线性分组码

皇家赌场hj883官网 9

校验矩阵和生成矩阵

LDPC码终于被5G通信采纳

Tanner图

皇家赌场hj883官网 10

Tanner图

0 引言

2016年10月14日,在葡萄牙里斯本,阿尔蒂斯大酒店,3GPP
RAN1会议终于确定5G通信将使用LDPC码作为移动宽带(eMBB)业务数据信息的长码块编码方案。在问世53年之后,LDPC终于被主流移动通信系统接纳了。这对从事LDPC码研究的专家或者学者来说(笔者也是其中之一),无疑是一件令人兴奋的事情。

利用稀疏矩阵有利于降低译码复杂度

LDPC编码是基于校验矩阵定义和构造的一类线性分组码,其校验矩阵为稀疏矩阵,也就是说,其校验矩阵大部分元素均为零,只有极少量的非零元素。
在接收端,使用和-积算法对该编码进行译码。
使用稀疏校验矩阵构造编码,有利于降低译码复杂度

随着移动互联网和物联网的不断发展,第五代移动通信(Fifth-Generation Mobile
Communication Technology,5G)面临移动通信爆发式增长[1-2]。5G技术不仅需要大幅度提升频谱利用效率,而且需要具备支持海量设备连接的能力[3-6]。由于低密度奇偶校验(Low Density
Parity Check,LDPC)码具有高可靠性、快速收敛性及较强抗突发错误能力[7-8],可以提高系统有效性[9-10],使得3GPP
RAN1会议在2016年确定在5G移动通信中使用LDPC码作为移动带宽eMBB业务数据的长码块编码方案。

皇家赌场hj883官网 11

References:

https://wenku.baidu.com/view/3d9a3c4676eeaeaad1f330f8.html?from=search
https://wenku.baidu.com/view/a2fc62ba4b35eefdc8d333c8.html?from=search
https://wenku.baidu.com/view/b143ea60a32d7375a41780bd.html?from=search
https://wenku.baidu.com/view/42081368b84ae45c3b358c22.html?from=search

本文对2004年由王鹏提出的LDPC码迭代编码算法[11]进行改进,转变为适用于多元LDPC码的编码算法,称为多元迭代编码算法;2005年,Hu
Xiaoyu提出了渐进边增长(Progressive Edge Growth,PEG)构造算法[12],该算法译码性能好,但编码复杂度较高。本文针对PEG算法具有高编码复杂度这一缺点,提出改进的PEG算法,即irPEG算法;结构化构造算法,即QC-LDPC构造算法[13],该算法复杂,译码性能差于随机构造算法,但复杂度大幅度下降,硬件实现性强。本文提出一种改进的QC-LDPC算法,使校验矩阵具有下三角结构,降低复杂度,加快收敛速度,构造出无短环的校验矩阵。然后,从编码复杂度和纠错性能两方面考虑,基于多元迭代编码算法,提出混合构造算法,即HC构造算法,将随机构造和结构化构造算法结合,irPEG算法构造基矩阵,改进的QC-LDPC算法生成循环移位矩阵和有限域系数矩阵,消除短环影响,设置校验矩阵个数,从中选取最优校验矩阵。该算法既具有随机构造的随机性,又保持结构化构造的低复杂度,降低结构化构造对误码性能带来的损失,是比较折中的算法。

在这次会议中,关于5G 通信中候选的信道编码技术,其实有三个不同的阵营:
美国主推 LDPC码,代表的阵营有高通、NOKIA、Intel和三星
法国主推 Turbo码,代表的阵营有Orange和爱立信
中国主推 Polar码,代表的阵营有华为

1 多元迭代编码算法

皇家赌场hj883官网 12

在图1中对角线上的元素全部为GF(q)域上的非“0”元素,并且剩余的非“0”元素全部对应于对角线左边。若构造出的多元LDPC校验矩阵具有图1的结构,则在编码过程中可直接采用迭代编码算法编码。

美国以高通领队,法国派出了最强团队(94年 Turbo 元老级 Claude Berrou
团队),中国则以华为为首。这是一场美、欧、中三方的通信标准之争。
LDPC码阵营认为,Turbo码译码时延大,不适用于5G高速率、低时延应用场景。
Turbo码阵营反驳,Turbo码已使用于3G、4G,在应用中不断改进的Turbo码是能够满足5G极端场景的。
Polar码则似乎有些弱势,目前还没有大规模应用采纳。
经过几百份提案和无数次讨论之后,最终3GPP 选定 LDPC码为 5G
中长码编码方案。短码的悬念留到了下次会议决定,Polar码和
Turbo码仍有望在未来的 5G 短码编码标准中占一席之地。
什么是信道编码

皇家赌场hj883官网 13

在移动通信中,由于存在干扰和衰落,信号在传输过程中会出现差错,所以需要对数字信号采用纠、检错技术,即纠、检错编码技术,以增强数据在信道中传输时抵御各种干扰的能力,提高系统的可靠性。对要在信道中传送的数字信号进行的纠、检错编码就是信道编码。
信道编码是为了降低误码率和提高数字通信的可靠性而采取的编码。信道编码之所以能够检出和校正接收比特流中的差错,是因为加入一些冗余比特,把几个比特上携带的信息扩散到更多的比特上。为此付出的代价是必须传送比该信息所需要的更多的比特。
传统的信号编码有汉明码、BCH码、RS码和卷积码。目前应用较广的有Turbo码,以及5G即将使用的LDPC码,还有具有应用潜力的Polar码等。不同的信道编码,其编译码方法也有所不同,性能也有所差异。
关于LDPC码与Polar码
****LDPC码****

皇家赌场hj883官网 14

LDPC码和Polar码都是当今5G备选技术里炙手可热的信道编码技术,也是当今信道编码研究领域的热点。在这里不详细讲述具体的技术,只是给大家科普一下关于LDPC码和Polar码的知识。
LDPC码的发明人是美国人Robert Gallager,Polar码的发明人是土耳其人Erdal
Arikan。同为顶尖的信息论高手,两个人同时也是师徒关系。

皇家赌场hj883官网,其中,l∈[0,n-k-1],hi,j表示校验矩阵H中第i行j列上的元素,且k=n-m。由式(1)知,多元迭代编码算法过程为利用校验矩阵H中各行约束关系,采用后项迭代算法,逐次计算每个校验位符号值。

皇家赌场hj883官网 15

对迭代编码算法改进,将二元迭代编码时采用的与(AND)和异或(XOR)运算,改进为GF(q)域上乘法和加法运算。同时多元迭代编码算法的运算过程中引入了GF(q)域上除法运算。对运算量简化,将对角线上元素设置为1,式(1)改为式(2)。

LDPC码于1962年由Robert
Gallager提出,由于当时计算机处理能力和硬件实现水平有限,之后很长一段时间没有受到人们的重视。直到1993年Berrou等提出了Turbo码,纠错码理论经过近50年缓慢的发展,突然取得了巨大的进步。人们发现Turbo码从某种角度上说也是一种LDPC码,近几年人们重新认识到LDPC码所具有的优越性能和巨大的实用价值。在80年代,Tanner用图论的方式解释了LDPC码,并改进了译码方法。
到了90年代,剑桥大学卡文迪许实验室的David J.C.
MacKay研究表明,采用LDPC长码可以达到Turbo码的性能,LDPC码在此进入了学术界的视野。随后学术界对LDPC投入了大量的关注,对编码矩阵构造、译码算法优化等关键技术展开研究。
其中比较关键的突破包括:高通的Thomas J.
Richardson提出的Multi-Edge构造方法可以灵活的得到不同速率LDPC码,非常适合通信系统的递增冗余(IR-HARQ)技术;再加上LDPC的并行译码可以大幅度降低LDPC码的解码时间和复杂度,LDPC从理论进入通信系统的障碍被全部扫清了。现在,LDPC码被公认为是性能最接近香农极限的信道编码之一。

皇家赌场hj883官网 16

LDPC码是一种线性分组码,它是一种校验矩阵密度(“1”的数量)非常低的分组码,核心思想是用一个稀疏的向量空间把信息分散到整个码字中。普通的分组码校验矩阵密度大,采用最大似然法在译码器中解码时,错误信息会在局部的校验节点之间反复迭代并被加强,造成译码性能下降。
反之,LDPC的校验矩阵非常稀疏,错误信息会在译码器的迭代中被分散到整个译码器中,正确解码的可能性会相应提高。简单的说:普通的分组码的缺点是错误集中并被扩散;而LDPC的优点是错误分散并被纠正。

2 混合构造算法

由于LDPC码优异的性能,已经被5G通信所认可并采纳。对于LDPC码来说,不仅可以应用到移动通信当中,还可以应用到存储领域(笔者目前正从事这方面的研究)。目前,国内外已经有研究利用LDPC码应用到高密度闪存(如现在的MLC/TLC
NAND
Flash)以提高存储的可靠性,在此之前主要应用的是BCH码。由于存储芯片制造尺寸日益减小,可靠性是一个需要被重视的问题,LDPC码的应用无疑具有重要的意义。
Polar码

2.1 irPEG构造算法

皇家赌场hj883官网 17

针对PEG算法具有较高编码复杂度的缺点,提出一种具有下三角结构非规则的PEG算法,即irPEG算法。该算法从编码方案、构造校验矩阵方面改进,以降低编码复杂度,提升纠错性能。具体步骤如下:

Polar码是2007年Erdal
Arika在他的一篇关于信道计划理论的文章中提出来的。在近来的研究中,Polar码被发现其具有接近香农限的性能,而且编解码具有较低复杂度,逐渐成为纠错码研宄新的热点。

(1)确定基矩阵中各参数

Polar码构造的核心是通过“信道极化”的处理,在编码侧,采用编码的方法使各个子信道呈现出不同的可靠性,当码长持续增加时,一部分信道将趋向于容量接近于1的完美信道(无误码),另一部分信道趋向于容量接近于0的纯噪声信道,选择在容量接近于1的信道上直接传输信息以逼近信道容量。
在译码侧,极化后的信道可用简单的逐次干扰抵消译码的方法,以较低的实现复杂度获得与最大似然译码相近的性能。Polar码作为目前唯一可理论证明达到香农极限,并且具有可实用的线性复杂度编译码能力的信道编码技术,在未来移动通信当中将具有很大的应用潜力。

行列数、变量节点度分布序列,并且初始化基矩阵的信息,包括与变量节点相互连接的校验节点的集合以及它的补集。

在中国,华为大力推进Polar码的研究。华为在中国IMT-2020(5G)推进组5G第一阶段外场的信道编码实际测试中,测试了Polar码在静止和移动场景下的性能,通过极化编码的使用和译码算法的动态选择,同时实现了短包(大连接物联网场景)和长包(高速移动场景,如自动驾驶等低时延要求)场景中的稳定的性能增益,使现有的蜂窝网络的频谱效率有近10%的提升,还与毫米波结合达到27Gbps的速率,实测结果证明Polar码可以同时满足ITU的超高速率、低时延大连接的移动互联网和物联网三大类应用场景。
新空口技术是5G区别于传统通信技术最革命性的创新,华为通过多种新空口技术(F-OFDM,Polar
Code,SCMA,GrantFree,ShortTTI)的组合,总体可使5G空口提升3倍频谱效率,为5G关键技术选型做好了充分的准备工作。
笔者解读

(2)构造基矩阵对角线右侧下三角部分

笔者认为无论是LDPC码或者Polar码,由于之前大多的研究主要集中在理论上,但随着计算机与硬件水平的发展,更多的理论会得到实践,两者在未来都将具有非常大的应用潜力。最后感谢一下5GNR,科技蜘蛛,网优雇佣军提供的材料。

首先采用后项迭代算法从最后一列变量节点构造,根据变量节点度分布[14]向前连接校验节点。每列中第一个非“0”元素位置必须与对角线上校验节点连接,其余非“0”元素需添加在对角线左侧。寻找所有与该变量节点连接的校验节点集合,从中筛选度数最小的校验节点集合。若该集合含有多元素,则从中删除构成短环的校验节点,随机连接剩余某校验节点,若只有一个元素,则直接连接该校验节点。

(3)构造基矩阵的前n-m列

从第n-m个变量节点依次向前构造。根据初始化变量节点度分布序列选择度数最小的校验节点,保证每行行重相比于平均行重相差不大。删除构成短环的校验节点后,从剩余校验节点中随机连接。

皇家赌场hj883官网 18

由于构造出的矩阵具有下三角结构,构造时在满足式(4)度分布的基础上,将矩阵最后一列列重设置为1,校验部分对角线上元素均为1,下三角部分均为0元素。由此可见,可以利用式(2)直接采用后多元迭代编码算法进行编码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注