助力5G的LDPC信道编码才能,从信道编码定理聊起

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

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

摘要:

可靠的线上网赌网站 1

1948年,美国贝尔实验室的Claude E.
Shannon在贝尔技术杂志上发表了题为《通信的数学理论》的长篇论文,这篇论文用概率统计的方法研究了信息传输的内在特性,揭示了通信系统中传送的对象是信息,并定义了信息的度量和单位;系统设计的中心问题是在干扰噪声中如何有效而可靠地传送信息。指出可以用编码方法实现这一目标,提出了二个信源编码定理和一个信道编码定理;并在理论上证明了信息传输的基本性能限。这篇论文是信息理论的奠基性论文,它开创了信息论与信源和信道编码理论这一新兴学科。

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

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

在这篇论文中,Shannon首次提出了熵与信道容量的概念(在Shannon
1948年的原文中,既没有使用“互信息”也没有用一个特殊符号来记它,而总是使用不确定性之差。术语“mutual
information”及符号I是后来由Fano引入的),并指出:任一通信信道都有一个参数C,称之为信道容量,如果信息传输速率R小于C,则存在一种编码方法,当码长充分长时,系统的错误概率可以达到任意小。这就是著名的。虽然Shannon给出的仅仅是一个编码的存在性定理,但它不仅开创了信道编码理论这一富有活力的研究领域,而且给出了达到信道容量的编译码方法的指导性路线,即构造随机长码和采用最大似然译码(信道编码定理最初是Shannon基于典型序列方法证明的,后来Gallager基于最大似然译码给出了强编码定理)。此后,构造可达到信道容量或者可逼近信道容量的信道编码具体方法,及其可实用的有效译码算法一直是信道编码理论与技术研究的中心任务,也就是如何构造出能接近或达到Shannon限的码(称为Shannon码或渐近好码)是编码学者长期追求的目标。

LDPC码终于被5G通信采纳

在编码方法上,人们先后提出了Hamming码、Muller码、Reed-Solomon码和BCH码、Goppa码等线性分组码以及卷积码。BCH码和RS码均可采用代数译码算法进行快速有效译码,RS码同时具有优异的纠随机和突发错误能力,因此被广泛应用于CD、硬盘等存储领域。卷积码是由Elias于1955年提出的。Wozencraft给出了卷积码的序列译码算法。后来,Fano改进了该算法。卷积码的一个重要进展是1967年Viterbi提出了Viterbi译码算法,1973年Forney证明了Viterbi算法实际上是卷积码的最大似然译码算法。在Linkabit公司和美国国家航空航天局JPL实验室的推动下,Viterbi算法很快成为了NASA深空通信标准的一部分,并且得到了广泛的商用。

0 引言

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

上述各信道编码方案虽然译码复杂度大多在可接受的范围内,然而由于码长较短,其性能距Shannon限有较大距离。为了构造出译码复杂度可接受且差错控制性能优异的长码,Elias在发明卷积码的前一年便提出了乘积码的概念,这是第一个由短码构造长码的方法。乘积码以两个线性分组码作为分量码,其码长为各分量码码长的乘积,译码可通过对各分量码单独译码从而得到次优的结果。1966年,Forney提出了另一种由短分量码构造长码的编码方案:级联码。级联码通过将内码和外码进行串行级联,在不增加译码复杂度的同时获得较大的性能提升。上世纪70年代,NASA采用以卷积码为内码(并用Viterbi译码)、RS码为外码的级联码作为空间通信用的信道编码标准,在理论上展示了这种码距离Shannon限在3dB以内,并在实际中取得了极好的效果(据估计,在60年代每dB的编码增益可以节约100万美元的开发与发射成本;90年代每dB编码增益对深空网络的价值已增加到8000万美元)。人们将深空通信与编码的结合称为“天仙配”(最初是由我们111基地的学术大师J.
Massey给出的,称为“marriage made in
heaven”)。这是第一个构造出并在实际中使用的比较接近Shannon限的好码。需要说明的是,几乎同一时期,Gallager提出了低密度校验码,这是一种直接构造长码并采用低复杂度的迭代译码来解决译码问题的编码方法,但在随后的几十年中,由于受硬、软件所限以及级联码的影响,低密度校验码并没有引起太多关注。

随着移动互联网和物联网的不断发展,第五代移动通信(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业务数据的长码块编码方案。

可靠的线上网赌网站 2

现代编码始于1993年。在1993年的IEEE国际通信会议会议上,来自法国ENST
Bretagne的C.
Berrou等人提出了对于信道编码界具有革命性意义的Turbo码。这是第一种能有效逼近信道容量的实用编码方案(码率为1/2的Turbo码在AWGN信道上距信道容量限仅约0.5dB)。Turbo码巧妙地将两个简单的分量码通过伪随机交织器并行级联在一起,从而构造了长码并实现了Shannon随机编码的思想。在接收端Turbo码采用低复杂度的迭代译码来逼近最大似然译码。Turbo码的提出迅速激起了编码界对迭代可译码的研究热情。目前,Turbo码已广泛应用于各种数字通信系统中,例如:CCSDS的深空通信标准、数字视频广播标准、第三代移动通信系统以及3GPP
LTE标准。

本文对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码,代表的阵营有华为

Turbo码问世后不久,剑桥大学的MacKay和MIT的Spielman等人几乎同时发现:Gallager早在1962年提出的LDPC码在迭代译码算法下也能够逼近信道容量(如码率为1/2、码长为107比特的LDPC
码距离Shannon限不到0.04dB)。这些成果让这个沉寂三十多年的码重新焕发活力,同时迅速引发了又一轮对迭代译码研究的热潮。

1 多元迭代编码算法

可靠的线上网赌网站 3

上述LDPC码属于分组码,1999年Felstrom和Zigangirov提出了LDPC卷积码及其编译码技术,它可以看作是将一些标准LDPC分组码以链的形式耦合在一起而得到的,因而也被称为空间耦合LDPC码。LDPC卷积码可以通过基于滑窗结构的迭代译码器进行译码,因而编译码时延小,适宜于不需要将数据分块的连续数据传输系统以及可变帧长的包通信系统中。

在图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 短码编码标准中占一席之地。
什么是信道编码

虽然Turbo码和LDPC码的性能已经非常接近信道容量,但都是通过仿真验证的。2008年Arikan提出了Polar码,这是第一类可理论证明,达到任意二进制输入离散无记忆对称信道容量,也就是可以迏到Shannon限的码,并且具有线性复杂度编译码器的信道码。Polar码构造的核心是“信道极化(channel
polarization)”。通过极化,多个独立二进制输入信道被变换为容量接近于0或1的极端信道,然后可以在容量接近于1的无噪信道上直接传输信息。

可靠的线上网赌网站 4

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

目前,LDPC码已经在通信系统中获得了广泛应用,例如无线局域网(IEEE
802.11n), WiMax (IEEE 802.16e), 数字视频广播 ,10GBase-T以太网 (IEEE
802.3an),
NASA的近地轨道卫星通信以及深空通信中。LDPC码在光通信与固态存储器中的应用也正在研究中。LDPC码和Polar码是下一代通信系统中信道编码方案的强力候选者。

可靠的线上网赌网站 5

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

在译码方法上,早期的编码方案主要采用了硬判决译码,即解调器首先对调制器输入符号做出最佳判决,然后将此硬判决结果送给译码器;译码器再对编码器输入消息做一个最佳判决,以纠正解调器可能发生的错误判决,这就是所谓“纠错码”的观点。但这种译码方法损失了一部分信道所提供的有用信息,因而译码性能并不理想。后来,为了提高通信系统的性能,人们从Shannon的数据处理定理出发,提出了软判决译码方法。即如果解调器能送给译码器一个关于“不同调制器输入符号可能性”的似然信息序列,或未量化的输出,让译码器将这些信息与编码信息综合在一起做出判决,则系统性能可以得到较大提高。这就是“软判决”,即在一个高效的数字通信系统中,实际判决是译码器而不是解调器的任务。

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

可靠的线上网赌网站 6

总结信道编译码技术的发展,可以看出:由短码通过级联、交织构造长码,或由随机和代数方法直接构造长码,并采用软判决迭代译码逼近最大似然译码,从编码、译码两个方面共同努力,达到了逼近Shannon容量限的性能。我们将上述逼近容量限的具体编译码方法归纳为:

对迭代编码算法改进,将二元迭代编码时采用的与(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码被公认为是性能最接近香农极限的信道编码之一。

●串/并行级联码、乘积码:由简单的短码构造好的长码;基于迭代译码解决长码的可实用最佳译码问题。

可靠的线上网赌网站 7

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

●LDPC码:通过随机或代数方法直接构造好的长码;用消息传递算法解决最佳软译码问题。

2 混合构造算法

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

●空间耦合码:将Turbo、LDPC码等进一步耦合,构造更长的普适码;用滑窗译码解决译码时延问题。

2.1 irPEG构造算法

可靠的线上网赌网站 8

●Polar码:创建极端信道,每个比特子信道具有不等保护能力,在好信道上直接传输信息;极化后的信道可用简单的逐次干扰抵消译码。

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

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

信息论是通信与信息系统的基础理论,是现代通信发展的动力和源泉。现代数字通信的重大突破均源自于Shannon信息理论的重要成果。关于信息论对通信系统发展的指导作用,高通公司前技术总监J.
Viterbi博士有一个形象的比喻:

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

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

在国内,我校是我国最早从事信息与编码理论研究的单位之一。早在50年代末,在陈太一院士和胡征教授的建议下,在我校无线电物理系组建了信息论组,由汪漱玉任组长,组内有顾慰文、梁传甲、王育民、杨洽、全西成、王新梅、王以铭、张铭三、应新瑜、蔣锦星、黄铣卿、丘京扬、卢永寿等老师(以后还陆续来了张玉璞、谢武军、吉筮琴、党英等,以及由我校信息论专业的早期毕业生中选留了王永康、张启明、俞在青、宋国文、张甫翊、王冶平、喻尚威等作为老师),并组织了信息论讨论班,开展了学习和相关的教学和研究工作,逐步形成了信息论基础、信道编码、随机过程和信号检测与估值等研究方向。1959年我校无线电物理系开始招收信息论专业的大学生,并由我们信息论教研室开设了信息论与编码类课程,是我国最早开设这类课程的学校之一。

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

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

60年代末和70年代初,由肖国镇、梁传甲、王育民和王新梅等老师组织了编码与密码研讨班,由肖国镇老师主持并讲述学习编码和密码所需的数学知识,在校图书馆和当时的馆长金有巽教授的大力支持下,我们几位老师一起学习讨论编码和密码中的几本经典著作和论文,撰写了:代数理论基础、纠错码、差错控制、伪随机序列、组合数学等参考学习资料,并在校资料室经费的全力支持下,使得我们所写的上述约四、五百万字的资料得以刻写油印出版,这些资料不仅仅是我们讨论班学习、研究的总结,也为以后我们撰写有关教材奠定了坚实基础,并为我们以后进行有关科研、招收硕士、博士生奠定了扎实的理论基础。并且作为我校与我国各有关单位作交换资料,对提高我校知名度和促进我国在编码和密码领域的发展也起到了积极推动作用。

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

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

从80年代初开始,我校以信道编码与密码作为二个主要研究方向,开始招收硕士研究生,并在胡征教授指导下从80年代末开始招收博士研究生。开设了代数编码理论以及密码的研究生课程,并且组织了讨论班,定期地与学生一起讨论、研究问题,并一直坚持至今。目前,根据国际通信与信息编码理论的发展趋势,在我校的研究生课程中,既设有信息论基础课程,也有网络信息论作为学位课,既有经典的纠错码基础、代数编码理论,还同时开设有现代数字通信与编码理论,课程体系比较完整,这在国内高校中也是很少见的。

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

在信道编码方向上,直至目前已培养了约百名博士和百多名硕士,在这些硕士和博士中,既包括有学术界的马建华、马啸(中山大学数据科学与计算机学院执行副院长、教授)、吴暇(同済大学计算机学院院长、教授)、黄本雄、谢显中、贺玉成、陈西宏、杜伟章、柏春燕(美国罗德岛大学教授)等,以及本校的白宝明、马文平、李颖、慕建军、刘东苏等教授,也包括工业界和研究院所的周晓迈、孙韶辉、殷贯西、张国华以及在国外各大公司工作的李元兴、刘斌、刘丰、徐胜波等。2010年左右,我校的几位老师还一起组建了信息传输与编码研究中心。

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

我们在70年代就开展了代数码软判决译码的研究。从80年代中开始,我们在国内率先开展了基于纠错码的密码系统的研究,在世界上首先构造了基于纠错码的数字签名体制,以及纠错与加密相结合的体制等。在90年代中开始率先在国内开始了Turbo码的研究,随后结合国际发展趋势,较早地开展了LDPC码、空间耦合码、喷泉码和Polar码等的研究工作,先后承担了多项国家科技重大专项、973计划项目、863计划项目、自然科学基金项目等。在通信与编码研究方向上,先后提出了Turbo/Trellis码的逐符号前向译码算法、物理层网络编码与信道编码的联合设计方法,马啸提出的RS码译码算法还被美国T.
K. Moon教授写入了其2005年出版的教科书《Error Correction Coding:
Mathematical Methods and
Algorithms》中;针对多元LDPC码及其编码调制系统,提出了多种构造方法与高效译码算法,目前正与有关公司合作将其推向5G移动通信;针对数字磁记录信道,马啸和A.
Kavcic提出了称为匹配信息速率码的串行级联码,该成果2006年获得IEEE通信学会颁发的最佳论文奖。近期我们还与马啸教授一起提出了分组马尔科夫叠加传输方法,可以在一定范围内实现任意错误概率、任意码率的信息传输。在工程实践方面,我们与多个研究所合作,为航天测控、无人机、移动卫星通信等系统研制了FEC编译码器。在2006年我们开始研究量子密码和量子纠错码,我校的博士后曾贵华率先在国内开展了量子纠错码的研究,以后我校的李卓副教授和王云江副教授等在量子纠错码中都做出许多优秀的科研成果。目前,我们正面向5G通信系统和空间信息网络,以及数据存储系统、宽带无线接入系统、互联网和量子通信等开展新型信道编码理论与应用的研究工作。

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

可靠的线上网赌网站 9

可靠的线上网赌网站 10

1986年在美国召开的国际信息论会议(ISIT’1986)上,C.E.Shannon
与中国学者在一起(前排左一是王新梅教授)

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

可靠的线上网赌网站 11

2.2 混合构造算法

2013年在我校召开的通信与信息论国际研讨班(前排左一是白宝明教授)

虽然irPEG算法结合多元迭代编码算法可大大降低编码复杂度,但更适用于中短码硬件实现,对于长码来说,硬件实现复杂度依然较高。此时牺牲多元LDPC码一定纠错性能,在改进的QC-LDPC算法的基础上使其具有下三角结构,同时采用irPEG算法构造基矩阵WJ×L,提高多元LDPC码随机性,降低结构化构造对纠错性能带来的损失。将改进的QC-LDPC构造算法与irPEG算法结合,称为混合构造算法,即HC构造算法。HC构造算法步骤如下:

在国际学术交流方面,早在70年代末我们就邀请了美国夏威夷大学计算机系主任著名的编码学者、第一本纠错码专著的作者W.W.Peterson教授,他是改革开放后我校邀请的第一位外国教授,以后还陆续邀请了许多知名的各国专家、教授如:Massey、Blahut、林舒、曾开明(K.M.Tzeng)
、Imai等到我校访问和讲学。自1982年至今我们已多人多次地参加了国际信息论会议以及其它有关国际学术会仪,并在1961年由陈太一院士主持,由我校主办了全国首届信息论会议。2013年我们在西电校园承办了通信与信息理论国际研讨会,这是国际上唯一一次将信息与编码理论领域的7位学术大师(MIT的Gallager、Forney,
我校名誉教授UC Davis的Shu Lin等)聚集在一起进行研讨的盛会。

(1)irPEG算法构造基矩阵WJ×L。

今年是Shannon诞辰一百周年(Shannon
1916年出生于美国密歇根州)。从Shannon于1948年创立信息论算起,也已经过去近70年了,人们在信道编码定理的指引下,一步步地从构造出比较接近容量限的码到提出可逼近容量限的码,最后终于研究出了能够达到信道容量限的实用编译码方法。目前,信道编码已经作为信息传输与存储等领域的一项关键技术而获得了广泛应用。在时延非严格受限的通信系统中,我们已经能够在简单的点对点信道上实现逼近容量限的信息传输。但在时延受限的情况下,我们还需要继续寻找好码。另外,在复杂信道环境以及网络通信情况下的信道容量,许多还是未知的,需要继续探索。对于网络通信,信息论与排队论还未完成有效的联合。从90年代开始,仿照信道编码的编译码方法,国内外开展了量子纠错码的研究,虽然取得了一系列成果,但是并没有取得突破性进展,仍需深入研究。此外,Shannon信息论在各个领域(如量子信息论、生物信息论等)的应用研究和推广也正方兴未艾。

给定多元LDPC码度分布,根据irPEG算法构造出具有下三角结构二元基矩阵,大小为J×L。

Shannon创建信息论至今已接近七十年了,无论是信源编码、信道编码还是密码等,虽然已取得了许多优秀成果,并在实际中得到了广泛应用,但是仍有许多问题没有完全解决,需要我们继续努力!Shannon在信息科学界中的地位和作用如同牛顿在物理领域内的地位和作用,他们所提出的学术思想与理论将在各自的领域内永放光辉!

(2)确定有限域元素系数矩阵GcJ×L,根据基矩阵非“0”元素位置,在(0,q-1)间随机选择gcj,l值。

(3)基矩阵WJ×L确定循环移位系数矩阵SJ×L。

将循环移位系数矩阵SJ×L对角线上系数设为0,随机选择移位系数sj,l,通过WJ×L结合避免长度为2i的充分必要条件,如式(5)所示,确定移位系数矩阵SJ×L中移位系数sj,l。

可靠的线上网赌网站 12

可靠的线上网赌网站 13

其中,0表示p×p维的零矩阵,P表示p×p维的单位阵,码长为n=p×L,码率为r=(1-J/L)。HC构造算法的流程图如图2所示。

可靠的线上网赌网站 14

3 编码复杂度分析

PEG算法、irPEG算法、HC算法的编码复杂度如表1所示。其中,w是生成矩阵的平均列重,n是码长,k是信息位长。

可靠的线上网赌网站 15

在存储复杂度方面,HC算法构造的LDPC码存储矩阵时存储一个p×p维目标方阵P、一个J×L维多元系数矩阵GcJ×L及一个J×L循环移位系数矩阵SJ×L。irPEG算法构造同样大小校验矩阵,存储一个p×J×p×L大小的校验矩阵。可见,HC算法与irPEG算法相比具有更简单的矩阵存储结构。

在编码复杂度方面,PEG算法采用高斯消去编码算法,irPEG算法和HC算法采用多元迭代编码算法。高斯消去编码复杂度包含预处理,运算复杂度为o(n3),编码复杂度为o(n2),整个编码过程需wn次乘法,(w-1)n次加法。多元迭代编码算法整个编码过程用到(w-1)(n-k)次加法,w(n-k)次乘法。

irPEG算法和HC算法能直接构造出下三角校验矩阵,避免了校验矩阵预处理的同时保证了校验矩阵的稀疏性。因此,w相对于n可以看成非常小的常数,实现多元LDPC码的线性复杂度编码,与传统的构造算法相比,大幅度地降低了编码的复杂度。

4 仿真结果及分析

仿真参数设置:度分布服从式(4)的多元LDPC码,矩阵通过PEG算法和irPEG算法生成,在十六进制1/2码率(Code1)和3/4码率(Code2)下进行仿真,Code1时,信息位长为512
bit;Code2时,信息位长为176 bit。译码采用Mixed Log-FFT-BP译码算法[15],迭代次数25,BPSK调制,AWGN信道。

图3和图4分别为Code1和Code2时不同码率下的纠错性能。由图3和图4可知,irPEG算法与PEG算法误码率相比,性能相差不大,表明irPEG算法构造具有下三角结构的多元LDPC码在大幅度降低硬件实现复杂度的同时,具有较强的纠错能力。

可靠的线上网赌网站 16

可靠的线上网赌网站 17

对Code1和Code2译码时间进行测量,保持仿真环境一致性,如表2和表3所示。由表2可知,irPEG算法时间明显比PEG算法少,当误比特数较少时,时间节省量少于50%,随着误比特数增加,时间节省量稳定在50%,因此,irPEG算法耗费时间仅为PEG算法50%。Code2在信噪比为4
dB时的仿真测试结果如表3所示,同样表明译码所需时间减少一半。

可靠的线上网赌网站 18

可靠的线上网赌网站 19

参数设置如下:码率1/2、2/3、3/4、4/5、6/7,矩阵通过PEG和HC生成,十六进制(Code3)下仿真,1/2码率时,基矩阵16列,目标矩阵P为24×24单位阵;2/3码率时,基矩阵18列,P为16×16单位阵;3/4码率时,基矩阵16列,P为16×16单位阵;4/5码率时,基矩阵20列,P为12×12单位阵;6/7码率时,基矩阵14列,P为16×16单位阵,固定信息位长768
bit。图5为Code3情况时,PEG算法与HC算法在不同码率下的误比特率性能。

可靠的线上网赌网站 20

由图5可知,HC算法与PEG算法构造的多元LDPC码在低信噪比时没有明显差别;在高信噪比下HC算法性能略差于PEG算法构造的多元LDPC码,因此两种算法具有一致的编码增益。

5 结论

本文提出基于多元LDPC码迭代编码算法的混合校验矩阵构造算法,首先对迭代编码算法改进,使其适用于多元LDPC码;然后采用后项迭代法使PEG算法具有下三角结构,并将其作为混合构造算法基矩阵;最后采用改进后具有下三角的QC-LDPC码算法生成循环移位矩阵和有限域系数矩阵,设置校验矩阵的个数,从中选取最优的校验矩阵,该校验矩阵消除了短环影响,形成混合构造算法。仿真结果表明,本文提出的算法可以更好地适用于5G移动通信系统且满足译码算法的需求,对于高速通信设备来说是一种很好的候选校验矩阵构造算法。

参考文献

[1] TANG B,YANG S H.An LDPC approach
for chunked network codes[J].IEEE-ACM Transactions on
Networking,2018,26(1):605-617.

[2] MENG J H,ZHAO D F,TIAN H,et
al.Sum of the Magnitude for hard decision decoding algorithm based on
loop update detection[J].Sensors,2018,18(1):236.

[3] ZHANG C,HUANG Y H,SHEIKH
F.Advanced baseband processing algorithm[J].Circuits, and
Implementations for 5G Communication.IEEE Journal on Emerging and
Selected Topics in Circuits and Systems,2017,7(4):477-490.

[4] DJORDJEVIC I B.Multidimensional
OAM-Based secure high-speed wireless communications[J].IEEE
Access,2017,5(4):16416-16428.

[5] MALANDRINO F,CHIASSERINI C
F,KIRKPATRICK C.Cellular network traces towards 5G:using,analysis and
generation[J].IEEE Transactions on Mobile
Computing,2018,17(3):529-542.

[6] SOTELO M,MARCO A,MAESTRE V,et
al.Reasoning and knowledge acquisition framework for 5G network
analytics[J].Sensors,2017,17(10):2405.

[7] YU Y,CHEN W.Design of low
complexity non-binary LDPC codes with an approximated
performance-complexity tradeoff[J].IEEE Communications
Letters,2012,16(4):514-517.

[8] SONG L Y,HUANG Q,WANG Z L.Two
enhanced reliability-based decoding algorithm for nonbinary LDPC
codes[J].IEEE Transactions on
Communications,2016,64(2):479-489.

[9] ZHAO S C,MA X.Construction of
high-performance array-based non-binary LDPC codes with moderate
rates[J].IEEE Communications Letters,2016,20(1):13-16.

[10] XIA T,WU H C.Blind identification
of nonbianry LDPC codes using average LLR of syndrome a posteriori
proba-bility[J].IEEE Communications
Letters,2013,17(7):1301-1304.

[11]
王鹏,王新梅.LDPC码的快速编码研究[J].西安电子科技大学学报,2004,6(31):934-938.

[12] Hu Xiaoyu,EVANGELOS E,DIETER M
A.Progressive edge growth tanner graphs[J].IEEE Transactions on
Information Theory,2005,51(1):995-1001.

[13] DRAGOI V,KALACHI H
T.Cryptanalysis of a public key encryption scheme based on QC-LDPC and
QC-MDPC codes[J].IEEE Transactions on Information
Theory,2018,22(2):264-267.

[14] TONG N N.Research of encode and
decode algorithm optimization and application for non-binary LDPC
codes[D].Harbi:Harbin Engineering University,2014.

[15] SONG H,CRUZ J
R.Reduced-complexity decoding of Qary LDPC codes for magnetic
recording[J].IEEE Transactions on
Magnetics,2003,39(2):1081-1087.

作者信息:

孟嘉慧,赵旦峰,张 良

(哈尔滨工程大学
信息与通信工程学院,黑龙江 哈尔滨150001)返回搜狐,查看更多

责任编辑: