LDPC硬判决译码算法:维特比译码算法

来源:初中教育 发布时间:2019-04-21 05:57:21 点击:

  摘要: 本文介绍了低密度奇偶校验码(LDPC)原理,并基于LDPC硬判决译码算法的思想提出了一种实用的实现步骤。   关键词: LDPC码;硬判决   
  1引言
  在现代无线通信系统中,信道编码技术是提高系统传输数据可靠性的有效方法,主要是其能降低信号传播功率和解决信号在无线传播环境中不可避免的衰落问题。低密度奇偶校验码(LDPC)最初是由Gallager[1]在1962年提出的,具有逼近香农限的性能,几乎适用于所有信道,因此成为近年来编码界研究的热点。
  LDPC译码算法本质上都是基于Tanner图的消息传递迭代解码算法(Message Passing)[2]。算法的性能随量化阶数的增加而提高,复杂度也随之增加。最简单的是量化为两阶,即成为硬判决算法;当量化阶数趋向于无穷时,即成为BP[3] (Belief Propagation)算法,也叫做SPA算法(Sum Product Algorithm)。
  在硬判决中,采用的方法是“位翻转”(Bit Flipping),因此通常称为BF[1]算法。该算法只需计算模2校验和,并用计算结果进行判决,因此计算复杂度相当低,并且主要采用异或门和比较器,所以易于硬件实现。每次迭代中翻转的比特位数称为门限(Threshold),通常用δ表示。和BP算法相比,BF算法的性能较差,所以BF算法一般只适合用于光纤通信等信道条件较好的情况。另外,BF算法还可用于粗略的判断校验矩阵H对应的LDPC码是否具有良好的纠错性能等。
  2 LDPC码简介
  低密度奇偶校验码本质上是一种线性分组码,它通过一个生成矩阵G将信息序列映射成发送序列,也就是码字序列。对于生成矩阵G,完全等效的存在一个奇偶校验矩阵H,所有的码字序列V构成了H的零空间,即HVT=0。LDPC 码的奇偶校验矩阵H是一个稀疏矩阵,相对于行与列的长度(N, M),校验矩阵每行、列中非零元素的数目(我们习惯称作行重、列重,分别用j、k或ρ、γ表示)非常小,这也是LDPC 码之所以称为低密度码的原因。
  根据行重列重是否固定值可以将码分为正则码(又叫规则码)和非正则码(又叫非规则码)。校验矩阵H的构造方法有随机化和系统化两种方法。
  Gallager给出的奇偶校验矩阵实例[1]如图1所示。由该矩阵构造出的是随机的正则码。
  3 硬判决算法的流程
  3.1 硬判决算法的思想
  假设信道是二进制对称信道(BSC),信道噪声为加性高斯白噪声(AWGN),噪声均值为0,功率普密度是No/2。用BPSK调制,能量为1,编码后序列被映射成,这里映射公式是。接收匹配滤波器的输出作为软判决的输入,,。序列作为硬判决的输入,这里
  。这里先给出几个符号的定义 :假设H是一个J行n列的校验矩阵,用h1,h2,……,hJ表示H的各行,其中hi(1当且仅当s=0时表示接收到的码字z是正确的,否则,在z中存在可检测的错误。也就是说,当接收到的码字中存在错误时,则s中必至少有一位为1。因此在译码的一次迭代过程中,首先根据s翻转z中的某些比特位,得到新的z后,可以得到更新后的s,由s是否为0判断译码是否正确。BF正是根据上述思想来进行迭代译码。
  3.2BF的步骤
  第一步:由接收序列z根据式(1)计算校验和s;若s为全零,表示接收正确,停止译码并退出;否则转第二步。
  第二步:计算每一位码字所对应的不满足校验和的校验方程的数目,记为fi,i=0,1,……,n-1。
  第三步:根据门限值δ的大小对f0,f1,……,fn-1进行相应的从大到小的排序,将排在前面第1到第δ的fi的下标放入集合F中。
  第四部:将下标在F中的码字比特进行翻转。
  第五步:重复一至四步,直至所有的校验方程都得到满足(此时,译码正确并能在第一步退出)或超过了最大的迭代次数(此时没有能够正确译码,即译码失败)。
  4 结论
  LDPC码不仅具有逼近Shannon限的良好性能,而且译码复杂度较低, 结构灵活,是近年信道编码领域的研究热点,目前已广泛应用于深空通信、光纤通信、卫星数字视频和音频广播等领域,并已成为第四代通信系统(4G)中的首选。
  
  
  参考文献:
  [1] R.G.Gallager .Low-Density Parity-Check Codes.IRE Trans Inform Theory. IT-8:21-28, January 1962
  [2] RICHARDSONT, URBANKER.The capacity of low - density parity- check codes under message - passing decoding[J ].IEEE Trans on Inform Theory ,2000 ,47 :599~6181
  [3] T.Richardson, A.Shokrollahi, and R.Urbanke. Design of capacity approaching irregular codes. IEEE Trans. Inform. Theory, vol. 47, pp. 619�637, Feb. 2001.

推荐访问:译码 判决 算法 LDPC
上一篇:[技术创造财富创新强盛中国] 智慧创造财富作文800字
下一篇:最后一页

Copyright @ 2013 - 2018 四八文档网-文档下载,办公室文档软件 All Rights Reserved

四八文档网-文档下载,办公室文档软件 版权所有 沪ICP备09019570号-4