datasheet

非规则LDPC码译码改进算法及其DSP实现

2008-03-18来源: 清华大学 关键字:改进算法  码长  译码  LDPC  定点DSP  码元  误比特率  量化精度  元素个数

  摘 要:为了降低非规则低密度奇偶校验(low-densityparity-check,LDPC)码译码算法的复杂度,提出一种适合数字信号处理嚣(digital signal processor,DSP)实现的低运算复杂度、低误码平台译码的改进算法。该算法校验节点的运算采用修正最小和算法,外信息的更新采用串行方式,既保持了串行和积算法在有限迭代次数下译码门限低的优点,又降低了节点运算复杂度和误码平台。用定点DSP芯片实现的非规则LDPC码译码器的实测结果表明,该算法能以较低的实现复杂度获得低的误码平台和译码门限。

  关键词:信道编码;LDPC码;修正最小和算法;数字信号处理器

  低密度奇偶校验(low-density paruty-check,LDPC)码是一种非常有效的信道编码方案,已经成为新一代数字卫星广播(DVB-S2)等标准的信道编码方案,具有重要的应用价值。

  LDPC码译码器设计的实现成为近年来研究的热点。LDPC码译码器的实现方法主要有2种:一种是基于超大规模集成电路(VLSI)的设计;另外一种是基于数字信号处理器(digital signalprocessor,DSP)等指令串行执行系统的实现。

  LDPC码译码多采用和积(sum-product,SP)译码算法,影响其复杂度的因素有迭代次数和每次迭代的运算复杂度。由于DSP芯片指令串行执行的特点,要实现较高速率的LDPC码译码器,必须同时减少迭代译码次数和每次迭代的运算量。文提出一种逐个校验节点串行更新的迭代译码算法(S-SP),并说明在二进制对称信道(BSC)下可以有效降低迭代译码的次数;为降低每次迭代的运算复杂度,校验节点的运算存在一些简化的译码算法,如修正最小和算法(modified mim-sum,MMS)等,但这些算法的译码门限有一定的损失。

  本文研究非规则LDPC码的S-SP算法在加性高斯白噪声(AWGN)信道下的性能,说明该算法虽能降低迭代次数,但是存在误码平台较高的问题。考虑到简化的译码算法(例如MMS算法)有复杂度和误码平台低的特点,本文综合这2类算法的特点,提出了串行MMS(S-MMS)算法,该算法在有限迭代次数下具有低的误码平台和较低的译码门限,实现了复杂度和性能的较好折衷,适合于用DSP实现。

  1 LDPC码简介和迭代译码算法

  1.1 LDPC码简介

  LDPC码是一种分组码。其校验矩阵为超稀疏随机矩阵,设为H。对于任何一个合法的码字v,都有校验方程。由该方程可知,校验矩阵中每行的非零元素,将所对应的LDPC码元映射成一个相当于校验码的约束,定义这种约束关系为一个校验节点。校验矩阵中每列的非零元素对应LDPC码的同一个码元,形成了一个相当于重复码的约束,定义这种约束关系为一个变量节点,而矩阵中的非零元素,既参与了变量节点的重复码的约束关系,又参与了校验节点的校验码的约束关系;因此定义矩阵中非零元素所对应的关系为连结这2种节点的“连结线”。因此,LDPC码的结构也可以用图1的因子图表示。

  LDPC码的编码,先利用校验矩阵得到对应的生成矩阵,然后直接用信息序列和生成矩阵相乘即可得到编码码字,而LDPC码的译码则利用校验节点和变量节点的约束关系,在2类节点间通过“连结线”进行外信息的传递,从而实现迭代译码。

  1.2 LDPC码迭代译码算法

  定义为变量节点n的先验信息,即对数似然比;表示第k次迭代中,从校验节点m到变量节点n的外信息;表示第k次迭代中,从变量节点n到校验节点m的外信息;为第k次迭代后变量节点n的后验信息;M(n)表示和变量节点n相连的校验节点的集合;N(m)表示和校验节点m相连的变量节点的集合。

  标准的和积(SP)译码算法如下。

  步骤l 初始化。

  其中:xn为发送比特;yn为接收符号。采用二进制相移键控(BPSK)调制,信道为AWGN信道。

  步骤2迭代译码。

  迭代译码包括2个步骤,变量节点的计算和校验节点的计算。本文中设定固定的迭代次数K,然后判决输出。

  1)变量节点的运算(对所有的变量节点n)。

  2)校验节点的运算(对所有的校验节点m)。

  其中k≥1.

  步骤3后验信息计算和判决输出。

  串行和积译码算法(S-SP),在计算校验节点m时,需要将上面和积(SP)算法中的步骤2变量节点的运算修改为

  其k≥1,假设校验节点的计算从1开始,也即m依次取1,2,3,…,M,这里M为校验节点的个数,如图1所示。

  S-SP算法和SP算法的不同点在于:在SP算法中,所有与校验节点m相邻的变量节点更新时所使用的校验节点外信息都来自上一次的迭代输出,然后进行校验节点m的运算。而在S-SP算法中,计算校验节点m时,和其相连变量节点的更新可以使用本次迭代中已经更新过的外信息。从上面的分析也可看出,S-SP算法的复杂度和SP算法相同,另外,可通过合理设计,使得该算法需要的存储资源可降低为原来的1/2。

  2 改进的迭代译码算法和优化设计

  文指出,在BSC信道下,S-SP算法可以有效降低迭代译码次数。本文研究了该算法在AWGN信道下的特点,发现该算法虽可以降低迭代译码次数,但是存在误码平台较高的缺点。后面将利用仿真结果说明这一特点。

  本文将S-SP算法与修正最小和算法(MMS)结合,提出了改进算法,将外信息的更新采用串行更新策略,校验节点的计算采用修正最小和算法,称为串行修正最小和算法(S-MMS)。该算法解决了S-SP算法的误码平台较高的问题,译码门限和标准的SP算法相比,性能损失很小。

  提出的串行修正最小和算法(S-MMS),其迭代译码步骤2修改如下。

  设定固定的迭代次数K,对校验节点m,依次取1,2,3,…,M,进行下面的2个步骤。

  1)变量节点的运算(只计算和校验节点m相连的变量节点)。

  

  

  其中:r=│N(m)│表示集合N(m)中的元素个数,即非规则码的校验节点m的阶数;βr为非规则码不同阶校验节点的偏移因子;sgn()为符号函数。

  最优的偏移因子βr值,可以采用密度演化或者计算机仿真的方法得到。

  本算法变量节点的运算只包括求和运算,校验节点只包括最大、最小和减法操作,与SP算法的校验节点运算的非线性函数ln(tanh())相比,量化噪声对其影响小。本文针对定点DSP芯片特点,信道观测值和迭代译码中的外信息,都采用16 b的量化精度,有利于优化指令并行度,并可以降低存储器读取、存储延时。

  3 算法性能仿真测试

  为验证本文算法的有效性,结合非规则LDPC码对算法的性能进行了计算机仿真,并利用TI公司的定点DSP对其性能进行了测试。

  仿真采用的非规则LDPC码的码长为4.096kb,码率为1/2,变量节点和校验节点的度分布分别为λ(x)=0.27x+0.25x2+0.01x3+0.47x9和ρ(x)=0.47_x6+0.53x7。

  据ρ(x)可知,非规则LDPC码校验节点的阶数为7和8,通过计算机仿真得到的最优偏移因子分别为β7=0.45,β8=O.60。

  图2给出了不同迭代次数下S-SP译码算法和SP算法的性能比较。可以看出,在AWGN信道下,S-SP算法仍可以有效地降低迭代译码次数,或者说在相同的有限迭代译码次数下,尤其是迭代次数为10次和20次时,性能有明显改善;但是,S-SP算法的缺点是有较高的误码平台。

  

  

  图3给出了不同迭代次数下,S-MMS算法和SP算法的性能比较。可以看出,S-MMS算法误码平台降低,译码门限略高于SP算法,在迭代次数较小时,性能仍有明显改善。当迭代次数为20,Eb/No较小时,S-MMS算法与SP算法相比性能略有恶化,但Eb/No较大时,性能有明显改善,且误码平台降低,例如误比特率Pe为10-5时,信噪比改善约0.1 dB。在误码率10-6时,信噪比改善约0.25 dB。当迭代次数为50,Eb/No较小时,译码门限恶化约0.15 dB,Eb/No较大时,性能仍有所改善,误码平台降低。

  综合比较图2和图3,S-MMS算法和S-SP算法相比,Eb/No较小时,译码门限恶化约为0.1~0.2 dB,Eb/No较大时,例如在误比特率Pe为10-6时,性能仍有所改善。考虑到一般通信系统要求译码后的误码率低于10-5,S-MMS算法在Eb/No较小时的性能恶化对其应用影响不大,适合实际应用。

  图4给出了不同迭代次数下,利用TI公司的DSP芯片TMS320C6416T实现的采用量化SMMS算法的译码器的仿真测试性能和未量化S-MMS算法的比较。可以看出,定点DSP芯片上实现的S-MMS算法和未量化的算法性能几乎完全一致,进一步说明了本算法利用DSP芯片实现的有效性。DSP芯片实现的译码器的具体性能见表1。

  

  

  文中用DSP实现的LDPC码译码器采用的码长为10.228 kb,码率为1/2,在误码率10-5时,信噪比为1.65 dB。本文设计的译码器采用的LDPC码的码长为4.096 kb,码率也为1/2,若采用50次迭代,在误码率10-5时,信噪比为1.55 dB;因此,本文实现的译码器的纠错性能优于文中设计的译码器。另一方面,本文译码器设计使用C语言实现,指令级的优化可进一步提高工作速率。

  4 结 论

   本文提出了一种适合数字信号处理器(DSP)实现的低复杂度、低误码平台的译码算法。该算法校验节点运算采用MMS算法,节点间的外信息更新采用串行方式,既保持了S-SP算法有限迭代次数下译码门限低的优点,又利用MMS算法的优点降低了误码平台和实现复杂度,克服了S-SP算法的复杂度高、误码平台高的明显缺点,获得了较好的性能折衷,很好地适应了DSP芯片指令串行执行的特点。

 

关键字:改进算法  码长  译码  LDPC  定点DSP  码元  误比特率  量化精度  元素个数

编辑:ssb 引用地址:http://www.eeworld.com.cn/afdz/2008/0318/article_531.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:H.264中基于编码模式的自适应重叠块运动补偿
下一篇:利用FPGA的DSP功能提高图像处理的实例分析

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利

推荐阅读

谷歌正在测试AI训练新模式 能直接在手机上改进算法

eeworld网晚间报道,谷歌(微博)研发出一种训练人工智能(AI)的新模式,可以直接在用户的智能手机上训练并改进AI算法。当大型科技公司利用机器学习来改进软件时,其过程通常是非常集中的。举例来说,谷歌和苹果等公司会收集有关用户如何使用其应用程序的信息,并将这些数据存放在服务器上的某个地方,然后使用聚合数据来训练新算法。最后,用户将获得改进后的应用更新。这种AI算法训练方法是有效的,但更新应用和收集反馈数据的过程是非常耗时的。而且,这种方式不利于保护用户隐私,因为公司必须在其服务器上存储有关用户如何使用其应用的数据。为了解决这些问题,谷歌正在尝试一种新的AI训练方式,并把它称为Federated Learning
发表于 2017-04-11

改进双向启发式搜索算法及其车载导航仪中应用

,为了实现路径规划模块,对单车辆路径规划算法进行了研究。 1 路径规划算法 所谓路径规划,就是在路网中找到任意给定两点之间的最优路径。最优的标准是旅行费用最小或最大。旅行费用可以是距离、时间或速度等因素。路径规划主要算法有:迪杰斯特拉(Dijkstra)算法及其改进算法、启发式搜索算法、双向搜索算法和双向启发式搜索算法等。 迪杰斯特拉算法是解决两点之间最短距离的有效算法。算法的思想是?从原节点开始,算法每前进一步,都找到一个与原节点之间费用(距离)最小的节点,直至找到所有节点离原节点的最小费用。该算法的特点是?只要各段路径的费用非负,一定可以找到从原节点到各节点的最优解。缺点是需遍历所有节点。算法的运行时间为O
发表于 2016-10-10
改进双向启发式搜索算法及其车载导航仪中应用

一种改进的多传感器加权融合算法

,在实际应用中,效果并未达到最优。本文采用二次加权的方法,并引入最优比例权重的概念,先对单个传感器进行加权,再对整体进行加权并导出基于改进算法的加权融合公式。通过仿真,并与加权平均融合算法中采用的等权重融合算法进行比较,验证该算法的有效性。   多传感器数据加权融合   加权数据融合是多个传感器对某一个环境中的同一特征参数的数据进行量测,兼顾每个传感器的局部估计,按某一原则给每个传感器制定权重,最后通过加权综合所有的局部估计得到一个全局的最佳估计值。   加权平均融合算法   假设在n个传感器的融合系统中,传感器s1,s2,…,sn对同一个目标进行状态估计,第i个传感器在第k时刻的局部状态估计
发表于 2016-10-09
一种改进的多传感器加权融合算法

数字PID控制及其改进算法的应用

可能的误差的校正。下面结合转台的控制过程对数字PID控制及其改进算法作具体的讨论。 1 Simulink仿真 转台的PID控制的Simulink仿真框图如图1所示。其中包含了两个子系统PID Controller(PID控制器)和Turn-table(转台)。对理想模型进行Simulink仿真实验。选用不同参数的PID控制器,它们对幅值为0.2的参考输入的阶越响应的过程曲线如图2所示。图中实线为只采用比例控制,取Kp=1;点画线、虚线和粗线均为采用比例微分控制,点画线的KI=1,KD=200;虚线的Kp=1,KD=600;粗线的Kp=10,KD=1000;图中点线为PID控制,Kp=1,KI=0.0005,KD=200
发表于 2015-08-25
数字PID控制及其改进算法的应用

一种用于FPGA的改进算法弱化了方波重影

波动。  如果将DDS 频率合成器看成分频器,在满足奈奎斯特采样定理[4]的条件下,可以得出如下结论:输出正弦波等连续信号时,DDS可以实现任意比例的分频;输出方波等存在跳变沿的信号时,这类信号的周期只能是系统时钟周期的整数倍,否则出现重影。  2 方波改进算法的研究与实现  为了解决方波重影问题,可从时域的角度分析。将若干个不同周期的方波叠加到一起,可得示意图如图3所示。     图3 中,使a 点和d 点向下抖动,使b 点和c 点向上抖动,多次叠加后可有效弱化方波重影,甚至彻底消除。但是,如何准确地判断a、b、c、d 四个点,成为实现这一方法的最大障碍。  仔细观察图3和图2,引入时钟节拍的概念,便能找到依据判断a、b
发表于 2014-08-26
一种用于FPGA的改进算法弱化了方波重影

单片机中实现KEELOQ的改进加密算法

件芯片IC(以Mirochip公司的HCS300为代表)实现,主要应用于汽车阵盗系统和门禁系统,是无钥进入系统领域的首选芯片。但也由于硬件芯片本身的限制(其所能加密的数据必须预先写入EEPROM中),使之很难用于其它(如数据加密)领域。 本文把这项封装在芯片里的KEELOQ加密技术用软件方式实现,并针对单片机的特性进行了适当改进。这种在单片机中实现的改进算法不仅包含了原来 HCS300所具备的所有功能,而且在系统安全性、灵活性、可扩展性、传输效率等方面均有较大改善,同时对改进算法在数据加密领域作为全新的尝试,以其特殊的密钥管理方法独立于对称型加密(如DES)与不对称型加密算法(即公开密钥体制,如RSA),成为一种适用于无线传输领域
发表于 2014-08-14
单片机中实现KEELOQ的改进加密算法

小广播

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版

站点相关: 视频监控 智能卡 防盗报警 智能管理 处理器 传感器 其他技术 综合资讯 安防论坛

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2018 EEWORLD.com.cn, Inc. All rights reserved
pt type="text/javascript" src="//v3.jiathis.com/code/jia.js?uid=2113614" charset="utf-8">