译码算法

译码算法（共8篇）

译码算法 篇1

0引言

LDPC(低密度校验)码是一种特殊的具有稀疏奇偶校验矩阵的线性纠错码,最初由Gallager于1963年提出,但是由于当时集成电路的限制,没有受到人们的重视。直到1995年才被Mackey和Neal重新发现,并作为一种性能接近香农极限而且在目前条件下可以实现的编译码方案,几乎适用于所有信道,描述和实现简单,因此成为编码界研究的重点。Mackey和Neal证明采用置信传播(BP)迭代译码算法,LDPC码在AWGN信道下具有接近Shannon限的性能。后来,研究发现LDPC码在RICE信道下采用修正的BP译码算法也具有非常优良的性能。虽然BP译码算法与Turbo码的MAP译码算法相比复杂度大大降低,但在硬件实现上复杂度仍很高。乘性修正最小和译码算法是对BP译码的最佳近似,而且实现复杂度低。部分并行译码是完全并行译码和串行译码的折衷,是译码器的一种可行的实现方法,但一般的部分并行译码器的吞吐率不高,交迭的部分并行译码算法不但降低了实现复杂度,而且使得同样复杂度的译码器的吞吐率提高了近1倍。这种算法的提出为设计高速率LDPC译码器,奠定了理论基础。

1算法描述

1.1乘性修正最小和译码算法

LDPC的译码算法主要有概率BP译码算法、对数似然比LLR(Log Likely Rate) BP译码算法、最小和译码算法、乘性修正最小和译码算法NMSA(Normalized Min-sum Algorithm)等。概率BP译码算法需要大量的乘法,运算时间太长;对数似然比LLR BP译码算法把大量的乘法运算变为加法运算,减少了运算时间,由于需要对数运算,实现复杂度仍然很大;最小和译码是对数似然比译码的近一步简化,只需要比较运算,但性能有一定的损失;乘性修正最小和译码算法是对最小和译码算法的修正,使其性能更接近对数似然比LLR BP译码算法,而且其实现复杂度也比较低。乘性修正最小和译码算法的初始化软信息yi/δ2,δ2的影响可以忽略不计,初始化软信息变为yi,因此不需要对信道估计。下面给出该算法的描述。

M(n)表示与变量节点n有连接关系的校验节点集合;N(m)表示与校验节点m有连接关系的变量节点集合;η为乘性修改因子,取值0.8;rundefined(b)(b=0,1)表示校验节点j传给变量节点i的外部校验信息;qundefined(b)(b=0,1)表示变量节点i传给校验节点j的外部校验信息;L(pundefined)表示接收比特的对数似然比;L(qundefined)表示变量节点i传给校验节点j的外部校验信息的对数似然比;L(rundefined)表示校验节点j传给变量节点i的外部校验信息的对数似然比;L(pundefined)表示变量节点i收到的所有外部信息的对数似然比;最大迭代次数max。

初始化:L(pundefined)=yi,i=1,2,3,…n。 (1)

式中,yi为接收软值。

迭代计算:

第1步:校验节点处理单元计算。

undefinedβ(qundefined)。 (2)

式中, α(qundefined)=sign(qundefined), β(qundefined)=|qundefined|,

第2步:变量节点处理单元计算。

undefined

第3步:判决。

对每个变量节点i在完成计算后,对式(3)进行判决,如果L(pundefined)<0,则undefined,否则为0;如果undefined成立,则译码结束,否则跳到第1步直至满足校验等式或达到最大迭代次数max为止。

1.2部分并行译码

目前LDPC译码器的实现结构主要有全并行译码、串行译码和部分并行译码。全并行译码器的译码速度快,但是实现复杂度高、资源开销多;串行译码器的实现复杂度低、资源开销少,但是译码速度慢;部分并行结构避免了完全并行结构资源消耗过多、硬件实现复杂度高的缺点,同时译码速度比串行结构快,比较符合实际应用。假如译码器中有3个校验节点处理单元CNFU(Check Node Function Unit),5个变量节点处理单元VNFU(Variable Node Function Unit),R阵(存储校验节点处理单元的输出信息)按照行均匀分为3块,Q阵(存储变量节点处理单元的输出信息)按照列均匀分为5块,R阵每一块包含的行数L,Q阵每一块包含的列数M,这样每个校验节点处理单元CNFU要处理的节点数为L,每个变量节点处理单元VNFU要处理的节点数为M,则变量节点处理单元VNFU和校验节点处理单元CNFU依次轮流工作直到成功译码或达到最大迭代次数。部分并行结构的一次迭代可以用图1加以说明。首先如图1(a)所示,3个校验节点处理单元CNFU同时工作,校验节点处理单元CNFU更新R阵中各块的第1行,然后如图1(b)所示更新Q阵中第2行,以此类推直道如图1(c)所示第L行。校验节点处理单元CNFU处理完成之后,变量节点处理单元VNFU开始工作,如图1(d)～(f)所示依次处理1～M列。由图1可以看出,硬件实现时译码器如采用部分并行译码结构需要L+M个时钟才能完成一次迭代。然后进行下一次迭代,直到达到最大迭代次数max。译码器需要max*(L+M)个周期才能完成迭代译码。

1.3交迭的部分并行译码

一般情况,部分并行译码的执行都是按照:更新R阵,接着更新Q阵,再更新R阵……这样循环的顺序来进行迭代的。这样做的好处是:更新R阵时用的是最新的Q阵信息,更新Q阵时也是如此。但是这样做增加了很多等待时间。

交迭的部分并行译码算法的主要思想在于同时更新R阵和Q阵,其他方面和部分并行译码算法是一致的。它的优势很明显,如果R阵和Q阵的更新分别是按照串行实现的,那么该算法迭代一次的时间仅仅是部分并行译码算法的一半。虽然R阵和Q阵的更新无法利用全新的Q阵和R阵信息,以致单纯地从迭代次数上看,该算法的收敛速度大大低于部分并行译码算法。不过在相同的时间里,该算法可以比部分并行译码算法获得多1倍的迭代次数,这足以弥补它收敛速度慢的缺点。

对于一种LDPC码,为了应用该算法首先要将R阵和Q阵分块。R阵按照行均匀分块,Q阵按照列均匀分块,与部分并行译码不同的是R阵每一块包含的行数应当和Q阵每一块包含的列数一致,设为L,这样R阵和Q阵才能够在相同的时间里完成迭代。校验节点处理单元CNFU每次从各块R阵中各更新一行,同时变量节点处理单元VNFU从各块Q阵中更新一列。例如:假如译码器中有3个校验节点处理单元CNFU,5个变量节点处理单元VNFU,把一个LDPC码的R阵分为3块,Q阵分为5块,各块中的起始位置都为0,3个校验节点处理单元CNFU和5个变量节点处理单元VNFU同时工作,即在第1个计算周期里如图2(a)所示,更新Q阵中每块的第1列和R阵中每块的第1行;在下一个周期里,更新Q阵中每块的第2列和R阵中每块的第2行如图2(b)所示;……;直到第L个周期如图2(c)所示。由图2所示可以看出,硬件实现时译码器如采用交迭的部分并行译码结构需要L个时钟就能完成一次迭代。然后进行下一次迭代,直到达到最大迭代次数max。译码器需要max*L个周期才能完成迭代译码。

2算法的具体实现及仿真结果分析

这种算法的具体实现步骤如下:

步骤1:初始化。

① 用式(1)计算每个变量节点上的L(pundefined);

② 对Q阵赋初值,Q0(i,j)=L(qundefined)=L(pundefined),i=1,2,3,…,M;j=1,2,3,…,N;M,N为H矩阵的行数和列数;

③ 将R阵清零,R0(i,j)=0,i=1,2,3,…,M;j=1,2,3,…,N;M,N为H矩阵的行数和列数;

④ k=1;初始化迭代次数;

⑤ 设置η的初始值为0.8;

步骤2:如果k>max,结束这帧的译码,否则继续。

步骤3:for(l=0;l

{

根据式(2)和Qk-1,计算各块R阵中的第l行;

根据式(4)和Rk-1,计算各块Q阵中第l列;

更新各块R阵中的第l行;

更新各块Q阵中第l列;

}

步骤4:通过式(3)计算每个变量节点的L(pundefined);

步骤5:根据步骤4的结果做硬判,得到一个输出序列Vk,if(L(pundefined (1))>0,then?vundefined=1, else?vundefined=0,如果该序列使得所有校验式满足,则将之作为译码输出,并结束迭代,否则k=k+1,跳转到步骤2。

为了验证交迭的部分并行译码与部分并行译码具有相同的性能,构造了准循环结构的QC-LDPC,1/2码率,1 008码长,为了方便比较吞吐率,设定部分并行译码和交迭的部分并行译码的R阵和Q阵各块的大小都为L。QC-LDPC译码器部分并行译码的吞吐率公式throughput=NRf/2LP,交迭的部分并行译码的吞吐率公式throughput=NRf/LP,N为码长;R为码率;f为译码器工作时钟;L为子矩阵的大小;P为迭代次数。用MATLAB软件进行仿真,发现2种译码算法的性能相同,交迭的部分并行译码的平均迭代次数比部分并行译码多将近一次,SNR=3 dB时吞吐率提高了63.6%。

3结束语

本文主要研究了LDPC在硬件实现时可以采用的具有较高吞吐率的译码算法,并对其性能进行了MATLAB仿真,仿真结果表明交迭的部分并行译码比部分并行译码具有更高的吞吐率,又结合乘性修正最小和译码实现复杂度低的优点,为实现较高吞吐率的译码器提供了一种可行的方案。

参考文献

[1]HUX,ELEFTHERIOU E,ARNOLD D M,et al.Efficient Implementations of the Sum-product Algorithm for Decoding LDPC Codes[J].IEEE Proc.of Globecom,2001(2):1036-1036.

[2]ZHANGT,PARHI K K.A54Mbps(3,6)-regular FPGALDPC Decoder[J].SIPS’02,2002(10):16-18.

[3]CHENY,PARHI K K.High Throughput Overlapped Message Passingfor LowDensity Parity Check Codes[J].ACMProc.of GLSVLSI,2003(6):245-248.

[4]岳田.裴保臣.LDPC码的几种译码算法比较[J].无线电通信技术,2006,32(4):24-26.

“话语”与“译码” 篇2

关键词：多媒体课件 话语 译码 艺术设计

对于人文学科而言，一个好的多媒体课件既反映着对某个阶段或某节课的基本知识的把握，又体现出教师的主观精神和个性风格。因此，多媒体课件运用到课堂教学中，也产生了一种共性与个性、整体与局部相互作用而形成的复杂效应。法国思想家福柯认为话语是一种语言及与言语结合而成的更为丰富和复杂的具体社会形态，涉及到说话人、受话人、文本、沟通、语境等各种要素。在这个意义上，话语不仅具有言语者的主观效力，又产生了整体环境效应。多媒体课件设计也需要考虑到这两个因素，以突出“话语”的意识和方式。教师在工作和生活中形成的个体感知、经验积累和人生观照，转化为独特的人格魅力，这也往往成为教学中一个不可忽视的因素。将独特的“话语”融入到课件的文字、内容、界面、版式中，可以营造良好的课堂氛围，有助于学生在融洽的环境中获得知识。高校课堂面对的是一群心智相对成熟、具有一定知识能力、但又需加以引导的学生，在教学中的课件设计需要充分了解和研究学生心理。尤其是在艺术设计这样一个鼓励学生发挥自己创造性思维的专业中，侧重视觉艺术的课件设计对于他们具有更好的辅助作用，这也需要对教师的主导性、学生的主体性以及师生之间的互动关系有全盘的考虑。

一、话语：教师的主导性方式

“话语”（Discourse）源于一个语言学概念，表现人们说出来或写出来的语言，又可以理解为说写者在特定语境中使用语言达到交流目的的言语手段。教师在多媒体课件中的“话语”体现为教师主体性和能动性的充分发挥，使课件以一种个性化和独特化的形式来服务教学。教师在设计课件时既要将自己的认知合理的融入到课件内容中，同时也要在课件的版面设计上要体现特色，使多媒体课件起到积极的作用。

首先，“话语”的主导性表现为教师以主观和个性的方式来实现对艺术设计知识的理解和传授。相对而言，高校人文学科的各种知识，包括艺术设计专业知识体系的构建，需要一种由研究者不断丰富和完善的学术标准。艺术设计专业既带有工科特征，又具有艺术学科特色，在行业中大多数人看来，这个专业带有较大的学科弹性，因为对艺术和设计作品的评价往往没有一个绝对的标准，有的只是建立的主体观念和客体事物相对应的辩证体系中的一种自我阐释效力。教师的主导性表现为教师对课件内容、方式上的选择权和决定权。根据教学目标和教学任务，教师可以选择合适合理的内容；同时在面对课堂突发情况和学生特殊差异的时候，教师还可以随时调整自己的教学方法。所以一个课件往往会根据每年的教学情况进行及时的改善，也可以根据当年的学生情况进行改动。比如在《标志设计》中，笔者在介绍设计方法时总会保留一些经典案例，同时每年替换一些当年的新作品，特别是一些与时代联系紧密的作品，来介绍标志设计的新特色，增强学生的时代感和责任感。另外，在课程的几个阶段，笔者还选择一些学生作业放到课件中，采用课堂点评的方式激发学生对自己和他人作品的评价欲望。当然，课件内容选择，最终还需要教师根据教学实际来全面考量。多媒体课件的设计突出了教师的主导性，强化了人文学科的学习方法和研究特点。因此每个课件都是独特的。

其次，教师的“话语”还体现在教学过程中，基于一种人文关怀而形成的问题意识。问题意识是在把握了教学整体内容的基础上，提炼出隐含在普通问题中的核心问题，这些核心问题是指导学生进入研究情境的重要渠道。因为课件制作往往与内容和方法的特殊性联系在一起。高校所讲授的设计知识更多是依赖于教师平时的职业积累，直接诉诸教师平时个体直观体验基础上的视觉和触觉，以形成全面的知识布局，一些重要问题往往是打开设计之门的重要契机。比如，在《设计史》课件中，笔者专门用了一段内容将工艺美术运动、新艺术运动、装饰艺术运动等几个重要的设计风格进行对比，然而描述这些风格的文字语言是抽象的，所以最好的方式是将代表着不同风格的典型作品列举展示出来，通过生动、直观的形象向学生展示几件设计作品的特点。选择作品的原则是既体现作品的风格倾向，又能让学生能较为容易的分辨出设计作品的不同之处，鼓励学生参与分析和讨论，提高他们的研究问题的能力。

另外，课件中的“话语”还表现为教师的个性语言和个体风格所形成的课件的艺术风格倾向。艺术设计专业本身就一个与视觉美打交道的学科，所以多媒体课件的界面设计要美观、得体，程序设计要符合课程内容的特色，操作方式也繁简得当。“课件需要借助一定的艺术形式，但不能单纯地位艺术而艺术，停留在做表面文章上。”课件设计既要服务于教学内容，有助于教学活动的顺利开展，又不至于喧宾夺主或华而不实，因为好的设计既要有好的形式，又要有好的内容。

二、译码：学生的主体性感知

对于艺术设计专业的学生而言，“译码”（code）是基于他们的认知结构而形成的对设计现象和问题的解读方式。大学阶段是世界观塑造过程中的一个承上启下的重要节点，学生有着多种渠道来拓展自己的视野，他们获取知识的方式也更加多样，同时对教师“话语”的“译码”也显得更为丰富甚至多义。

首先，多媒体课件设计可以有效的激发学生的主体性感知，形成解码的能力。优秀的多媒体课件设计，可以有效的改善高校课堂沉闷、枯燥的气氛，将声光电技术与课堂教学紧密的结合起来，一方面从生理、心理角度出发调动了学生的兴趣，一方面又潜移默化的将教师所设计的教学内容隐含其中，传授给学生。所以完美的多媒体课件可以起到画龙点睛、事半功倍的教学效果。然而，笔者曾发现，大一的学生很大程度上还延续着高中阶段的学习习惯和方法，往往在课堂上被动的接受知识。对于人文学科而言，这样的做法常常使学生成为背诵和记忆的机器，不利于学生的学习主动性和质疑精神的培养。在大一课程的课件设计中，多注重课件的界面和版面设计，多增加设计案例而少用文字，通过学生的直观体验，加上教师和学生的语言归纳最终形成一定的看法。而相比而言，大三、大四的多媒体课件则可以采用相对较多的文字来介绍设计事件和现象，通过抽象思辨和逻辑推理来形成见解。不论是大一还是大四，学习方法是逐渐形成的。多媒体课件的设计方法有很多种，需要根据教学内容，进行合理的调整。学生的学习兴趣和接受能力都是课件设计中需要考虑的，要结合他们的专业特点和自身兴趣，将课件的内容和形式都落实到具体的课件中。经过一些实践尝试，可以发现，课件设计无需面面俱到，给学生留下想象的空间，同时也为学生提供了思考的空间。

其次，学生的主体性需要借助于合理的方式，在教师的主导下获取译码。相对而言，高校学生在学习方面也有着一些明显的问题，他们毕竟没有经历过社会的磨练，缺少对社会更为全面、客观的理解和感受，在专业训练和设计思维等方面还有所欠缺。这些由年龄、经历所导致的弱点决定了他们需要借助学校和教师的指引。而环境的影响因素也不可忽视。在消费社会的大背景下，目前国内很多艺术院系的学生出现了急功近利的心态，导致设计作品过于商业化，“工具理性”的成分给过度夸大了，而缺失了艺术研究和批判精神。脱离了思想，设计行为便显得单薄和无力。艺术设计专业的学生今后大多从事的是设计行业，而当下很多设计师在工作中出现了重实践轻理论的倾向，致使很多光鲜的设计作品常常经不起推敲，所以有必要使他们在大学读书期间的培养良好的专业思维和艺术感悟能力。因为从学生就业后反馈的情况来看，大多数学生一旦走上工作岗位，很快就能在技术上适应要求，甚至成为单位的技术骨干，但是很多人到了一定的阶段往往会觉得因缺少艺术灵感而在工作上力不从心。高校的优势在于学生除了学习技术，更重要的是融于技术之中的艺术判断和设计思维。笔者曾在课件中将一个著名建筑方案和一个2016里约奥运标志进行对比分析，将两个方案的不同创作阶段以相对应的顺序进行平行比较，分析其中修改的思路，最终学生找到了不同设计案例中相同的文化内涵。多媒体中设计案例展示的各个时间节点也在教师的掌控中，课件展示顺序的设计与课堂讨论的不同阶段相切合，学生踊跃参与的场面使课堂教学效果得到极大的提升，正是由于教师的合理控制，将学生的劣势转化为课堂效率的一种尝试。

三、设计：课堂的互动性呈现

一门课程的教学过程往往会延续数周或一学期时间，师生之间会逐渐适应彼此的特点。正是在这种熟悉和磨合的过程中，师生之间才出现了一种特有的默契和共鸣，使知识传授和接受都更加的愉悦和方便。在哈贝马斯看来，言语行为只能被有能力的听众接受，而且有能力的听众可以转换自己的角色和立场。“人们必须说同样的语言，处身于一个由语言共同体所确立并且具有主体间性结构的生活世界当中，以便真正从对自然语言的反思当中获得好处，并把对言语行为的描述建立在理解这种言语行为内在自我解释的基础上。”师生之间的新型位置关系其实就是一种“主体间性结构”的反映。知识的传授者和接受者都是不可缺少的，而且在辩证的意义上看，这两种角色也是对称的、可互换的，而不同角色之间的互换可以有无数的可能性，这也形成了课堂教学中更为融洽和热烈的气氛。学生在某一课程中所接受的知识不可避免要受到任课老师的影响，所以教师应该尽可能的将这种影响控制在良性范围内。在多媒体课件中，教师要考虑到课件在内容和形式上的延续性，使学生能在课件的版式、操作方式、字体、色彩等各方面感受到亲切感和认同感，而不能在每次课件中追求迥异的风格而导致学生的不适应。当然，随着新内容的讲授，课件设计的变与不变，需要根据教学内容来进行调整。

归根到底，课件是无生命的，但在教师的主导性和学生的主动性共同作用下，多媒体课件才在课堂教学中焕发出自己强大的生命力。“在信息社会中，只有掌握和洞悉媒介运作过程，才能更好地批判媒介和利用媒介，因此，利用媒介‘在做中学是必不可少的过程。”多媒体课件不是单纯的播放画面或影像，而是服从于课堂教学的一个重要的辅助因素，其主要因素则是教师的讲授与学生的接受。“多媒体课件制作之前，教师要充分做好选题论证工作，尽量避免不必要的投入，要选择那些学生难以理解、教师不易讲解清楚的重点和难点问题，特别是要选择那些能充分发挥图像、动画效果的、不宜用语言和板书表达的内容，对那些课堂上较易讲解的内容就完全没必要采用多媒体课件的方式。”有些教师通过网络下载等方式获得别人的课件，不加修改甚至毫无改变的运用到自己的课堂教学中，往往很难取得理想的教学效果。当然，“他山之石，可以攻玉”，借鉴优秀的课件，学习他们的设计方法，有助于高校教学整体水平的提高，更有益于高校教学资源的利用和共享。“需要强调的是教学设计的理论和方法原本就应该为全体教师所掌握，而不是少数人的专利。”随着“天空教室网络教学平台”等多个多媒体网络平台的发展，高校教师可以方便快捷的获取更多资源，为设计更合理的多媒体课件创造了条件。在教师的主导性得到强化的同时，学生的主动性自然也被激发。良好的交互设计，也使多媒体课件极大的提高了课堂效率，为师生互动带来了便利。通过软件开发，在课件中植入更多的技术因素，可以形成生动的界面和效果，借助技术手段促进师生之间的多方面交流。课堂互动最终是依靠师生双方共同完成，形成一种合力状态。

结语

作为一门人文学科，艺术设计专业教学方法的多样性需要强调教师的主体性，这样才可以充分发挥教师的能动性，设计出内容合理、版式美观的多媒体课件。“艺术教育系统的运行是以媒介为中心（手段），不断调整艺术教育运作的过程。施教者、受教者、教育媒介三个因素或缓解作为双向回环的行程，是相互联系、相互制约的，它不可避免地存在着矛盾和差异。”合理巧妙的课件设计作为一种媒介，可以适度的化解课堂教学中的矛盾，促进教与学两方面的顺利进行。在充分研究高校艺术设计专业学生特点的情况下，教者通过巧妙的课件“话语”形成独特的“译码”，并将之与合理的课堂教学结合起来，有助于构建一种师生之间主动、互动的新型结构关系。“话语”的“译码”能够使课堂教学形成一种师生合力状态，顺利完成知识传播和接受过程，最终促进学生的全面发展。

注释：

王军，孙爱国.多媒体课件制作中的美学特性[J].现代教育技术，2006（5）.

德】哈贝马斯，曹卫东，付德根译.后形而上学思想[M].南京：译林出版社，2001.

白传之，闫欢.媒介教育论[M].北京：中国传媒大学出版社，2008.

陈贵平.现代教育技术[M].北京：科学出版社，2012.

李芒，金林，郭俊杰.教育技术学导论[M].北京：北京大学出版社，2013.

贺志朴，姜敏.艺术教育学[M].北京：人民出版社，2001.

LDPC编译码算法分析 篇3

利用信道编码技术检测并纠正信号传输过程中引入的错误,是保证数据传输可靠性的重要手段[1]。 LDPC 码是一种纠错能力很强的一种编码方式[2],其校验矩阵具有稀疏的特性,故存在高效的译码算法,可进行并行操作,便于硬件实现,吞吐量大,极具高速译码潜力,应用前景相当广泛。目前,在保证LDPC码纠错性能的前提下,降低编译码器实现的复杂度是研究的重点。

1 校验矩阵的构造

LDPC码是一种线性分组码,表示为(N,K),N代表码长,K代表信息序列长度。每个LDPC码由其校验矩阵H唯一定义,H是M行N列的稀疏矩阵,其中M=N-K,构造H矩阵是LDPC码的关键[3]。

H矩阵的构造需要满足以下3个条件:① 每行不超过Dr 个元素为1,每列不超过Dc 个元素为1,且Dr 和Dc 与码长N 的比值远小于1;② 任意2行(列)最多只有1 个相同位置上的1;③ 线性无关的行(列)数尽可能得大。

Dr和Dc分别代表行重和列重。条件①带来的矩阵低密度性,一方面保证了LDPC码的线性结构;另一方面使得解码时可以采取适当的并行结构进行迭代解码。

H矩阵的构造方法有多种,可以分为确定性构造和随机性构造2种方法来得到。每一种设计方法都只能对应LDPC码的一个子集。一般确定性构造的LDPC码易于实现,而随机性构造的LDPC码则性能更优。具体的构造方法包括Gal1ager构造法[4]和欧式几何构造法[5]等。

2 编码

如果采用传统的编码方法,通过生成矩阵生成码字,其最大弊端是高斯消元破坏了矩阵的稀疏性。其复杂度和码长的平方成正比,将导致编码时需要大量的硬件资源和很长的延时。

下三角矩阵编码法可以有效地解决巨大的运算量和存储空间消耗的问题,其主要思想是通过行列变换把校验矩阵H转化为近似的下三角阵形式。H矩阵可以化分成子矩阵形式[6]:

$\mathit{{\rm H}}=\left\{\begin{array}{c}\begin{array}{ccc}\mathit{A}& \mathit{B}& \mathit{{\rm T}}\end{array}\\ \begin{array}{ccc}\mathit{C}& \mathit{D}& \mathit{E}\end{array}\end{array}\right\}$。 (1)

式中,A为(m-z)×(n-m)的矩阵;B为(m-z)×z的矩阵;T为(m-z)×(m-z)下三角矩阵;C为z×(n-m)的矩阵;D为z×z的矩阵;E为z×(m-z)的矩阵,z为扩展因子。

设码字矢量表示为(s,p1,p2),其中s为信息位;p1与p2表示校验部分。码字矢量与各校验子矩阵的关系为:

$\{\begin{array}{c}p{}_1^{\text{Τ}}=-(-\mathit{E}\mathit{{\rm T}}{}^{-1}\mathit{B}+\mathit{D}){}^{-1}(-\mathit{E}\mathit{{\rm T}}{}^{-1}\mathit{A}+\mathit{C})\cdot s{}^{\text{Τ}}\hfill \\ p{}_2^{\text{Τ}}=-\mathit{{\rm T}}{}^{-1}(\mathit{A}\cdot s{}^{\text{Τ}}+\mathit{B}\cdot p{}_1^{\text{Τ}})\hfill \end{array}$。 (2)

计算过程中,(-ET-1B+D)-1的计算复杂度为O(z2),其他计算过程均为线性关系O(n)。

然而,当码长较大时,编码过程将会有很大的计算和存储复杂度。研究发现,基于一定数学基础构造的LDPC码可以实现线性复杂度的编码。对IEEE802.16e标准中定义的LDPC码而言,(-ET-1B+D)-1矩阵的计算结果为单位矩阵,从而可以对下三角矩阵编码法进行简化:

$\{\begin{array}{c}p{}_1^{\text{Τ}}=(\mathit{E}\mathit{{\rm T}}{}^{-1}\mathit{A}+\mathit{C})\cdot s{}^{\text{Τ}}\hfill \\ p{}_2^{\text{Τ}}=\mathit{{\rm T}}{}^{-1}(\mathit{A}\cdot s{}^{\text{Τ}}+\mathit{B}\cdot p{}_1^{\text{Τ}})\hfill \end{array}$。 (3)

根据下三角矩阵编码划分子矩阵的方法,可以采用编码器结构进行实现,如图1所示。

编码器主要包括输入串并变换模块、矩阵乘法器模块、前向置换器模块、缓存模块和码字合成模块5个部分。

由于LDPC 编码器数据位位数通常较大(千位以上)。因此,有必要通过串—并模块和并—串模块的转化,将处理模块设计成并行处理,这样可以提高运算速度,减少延迟时间。

3 译码

LDPC通常采用软判决译码方式,其基础算法是置信传播算法,也称和积算法。BP算法每次迭代包括2步:校验节点的处理和变量节点的处理。BP算法的消息通常是概率形式表示。传播的消息还可以表示为对数似然比形式。似然比BP算法相对于概率BP算法的优势是大量的乘法运算变为加法运算,减少运算复杂。

假设系统采用二进制调制,取值为{0,1}的码字ci映射为取值为{+1,-1}的符号xi,i=0…n-1,经信道传输后接收符号为yi=xi+ni,ni为统计独立同分布的高斯噪声变量,均值为0,方差为σ2。似然比BP算法为:

① 初始化。

L(0)(qij)=L(Pi)=2yi/δ2,

i=0…n-1,j∈C(i)。 (4)

式中,L(Pi)为变量节点i的初始似然比信息;C(i)为与变量节点i相关联的校验节点;L(l)(qij)为第l次迭代变量节点i传向校验节点j的似然比信息。

② 校验节点信息处理。

$L{}^{(l)}(r{}_{ji})=2\tanh {}^{-1}\left({\displaystyle \prod _{i\text{'}\in R{}_{j}i}\text{t}}\text{a}\text{n}\text{h}\left(\frac{1}{2}L{}^{(l-1)}(q{}_{i\text{'}j})\right)\right)$。 (5)

③ 变量节点信息处理。

$L{}^{(l)}(q{}_{ij})=L({\rm P}{}_i)+{\displaystyle \prod _{j\text{'}\in C{}_{i}j}L}{}^{(l)}(r{}_{j\text{'}i})$。 (6)

式中,L(l)(rji)为第l次迭代校验节点j传向变量节点i的似然比信息;L(l)(qij)为变量节点i传向校验节点j的似然比信息;$\tanh (x)=\frac{e{}^x-e{}^{-x}}{e{}^x+e{}^{-x}}$;Rj为与校验节点j相关联的变量节点集合;Rji为集合Rj中除去变量节点i;Cij为集合Ci中除去校验节点j。

④ 检验结果。

$\{\begin{array}{l}L{}^{(l)}(q{}_i)=L({\rm P}{}_i)+{\displaystyle \prod _{j\in C{}_i}L}{}^{(l)}(r{}_{ji})\\ \widehat{c}{}_i=0,L{}^{(l)}(q{}_i)>0\\ \widehat{c}{}_i=1,L{}^{(l)}(q{}_i)<0\end{array}$。 (7)

式中,$\widehat{c}{}_i$为译码结果。

为了进一步降低BP算法的复杂度,将似然比BP算法中变量节点信息和校验节点信息的计算都进一步简化。简化方法如下,将式(5)替换为:${}_k^{(j)}$。 (8)

这样,可以使译码运算时避免了对tanh(x)及tanh-1(x)函数的考虑,整个算法中仅剩加法运算和绝对值大小比较运算。因此译码器实现的复杂程度大大降低。

4 编译码结果分析

根据上述的编译码方法,对LDPC码进行了性能仿真。采用式(3)给出的简化编码方法对IEEE802.16e标准中定义的准循环LDPC码进行了编码,码率为1/2,码长包括2 304和576两种,译码算法分别采用了似然比BP算法及其简化方法。

在高斯信道下,码长576时编译码系统的误码率随信噪比变化的曲线如图2(a)所示。

在高斯信道下,码长2 304时编译码系统的误码率随信噪比变化的曲线如图2(b)所示。仿真结果显示,简化的译码算法在降低了译码运算复杂度的同时也带来了编译码性能的损失。因此,应在系统实现复杂度及性能之间进行慎重的权衡。

5 结束语

LDPC码是一种可接近香农极限的编码技术,已经作为信道编码方案应用在多种通信系统中。其编译码方法有多种,运算复杂度不同,性能也有差异。总体而言,性能好的译码方法对应的复杂度要高。如何解决编译复杂程度和纠错性能之间的矛盾,对LDPC码的应用具有重要意义。 

摘要：低密度奇偶校验(LDPC)码是一种线性分组码,其纠错能力可以接近香农极限。针对LDPC码的编译码问题,分析了校验矩阵的构造方法。给出了LDPC码的编码算法以及算法的实现结构。分析了基于软判决的置信传播(BP)译码算法,并给出了可以进一步降低计算复杂度的简化译码方法。通过仿真对比了不同的译码算法在高斯信道下的译码性能。

关键词：纠错码,低密度奇偶校验码,校验矩阵,置信传播算法

参考文献

[1]魏瑞刚,陈晖,邱金蕙,等.高速数据传输中的LDPC码译码算法研究[J].无线电工程,2011,41(3):20-22.

[2]MACKAY D J C,NEAL R M.Near Shannon Limit Perform-ance of Low Density Parity Check Codes[J].ElectronicLetters,1996,32(18):1 645-1 646.

[3]LI Z W,CHEN L,ZENG L Q,et al.Efficient Encoding ofQuasi-Cyclic Low-Density Parity-Check Codes[J].IEEETransactions on Communications,2006,54(1):71-81.

[4]GALLAGER R G.Low Density Parity Check Codes[J].IRETransactions on Information Theory,1962,8(3):208-220.

[5]KOU Y,LIN S,FOSSORIER M P C.Low-density Parity-check Codes Based on Finite Geometries:a Rediscoveryand New Results.IEEE Transactions on Information Theo-ry,2001,47(7):2711-2736.

译码算法 篇4

关键词：低密度奇偶校验码,偏置BP算法,可信程序对数可能比例 (Log-likehood-ratio-based-progration, LLR-BP) 算法

LDPC 码具有逼近香农限的性能, 几乎适用于所有信道, 已成为近年来编码界研究的热点。信道编码的译码算法是决定编码性能和应用前景的一个重要因素。尤其是在长码的条件下, 译码算法的复杂度决定了编码的发展。为减小LDPC 码译码算法的计算复杂度, 促进LDPC 码的发展, 国内外许多学者都对此作出了大量贡献, 一些简化的译码算法相继被提出:硬判决译码算法、概率域BP算法、基于Tanh法则和基于Gallager方案的LLR-BP算法的译码、基于Gallager方案的LLR-BP算法的简化的译码算法等[1,2,3]。

本文在对经典译码算法进行深入研究的基础上, 重点研究了基于Gallager方案的LLR-BP算法以及其简化的译码算法 (最小和算法、偏置BP算法和归一化BP算法) ;最后应用Matlab软件仿真比较基于Gallager方案的LLR-BP算法及其三种简化译码算法的性能。

1 基于Gallager方案的LLR-BP算法

基于Gallager方案的LLR-BP算法译码步骤如下:

(1) 初始化

对于每一个i和j, 对L (qij) 进行初始化L (。

(2) 校验节点计算

对于每一个i和j, 对L (rji) 进行更新L 。

上式中, $\text{α}{}_{\text{i}\text{j}}=sign\left(\text{L}(\text{q}{}_{\text{i}\text{j}})\right)‚\text{β}{}_{\text{i}\text{j}}=\left|\text{L}(\text{q}{}_{\text{i}\text{j}})\right|$。

(3) 变量节点计算

对于每一个i和j, 对L (qij) 进行更新L

(4) 计算伪后验LLR值

对于每一个i, 进行更新

(5) 译码判决

对于每一个i, 即对码字中的每一位进行判决, 如果, 则xi=0, 否则判为1。在所有比特被译出时, 得到译码码字x∧=x∧1, x∧2, …, x∧N。然后判断校验等式x∧HT=0是否成立, 如果成立, 则结束本次译码, 否则返回步骤 (2) 直到满足校验等式或超过最大迭代次数为止。

LLR-BP算法充分利用了信息节点和校验节点性质以及接收序列的所有信息, 从而可以得到逼近香农限的译码性能;该算法在二分图中没有环的条件下可等效为最大似然译码算法。在迭代过程中, 如果校验等式成立, 译码过程立即结束, 而不是进行固定次数的迭代, 所以收敛也比较快;同时采用了并行的迭代算法, 这种并行实现能够极大地提高译码速度, 从而使复杂度和译码延时都很低。

2 LLR-BP算法的简化译码算法

基于Gallager方案的LLR-BP算法校验节点更新计算中用到对合变换 (x) , 其计算复杂, 实际应用中要采用查表来实现。为了降低基于Gallager方案的LLR-BP算法的计算复杂度, LDPC码的研究学者们提出了多种基于Gallager方案的LLR-BP算法的简化译码算法, 这几种简化译码算法都是通过简化基于Gallager方案的LLR-BP算法中的校验节点的更新计算来降低译码的复杂度, 以便于LLR-BP译码算法在工程实际中的应用。

2.1最小和算法

最小和算法[4]主要是针对基于Gallager方案的LLR-BP算法中不断用到函数 (x) 而言的, 函数 (x) 在x>0的范围内随着x的增大而减小。由此可知式中求和的部分受最小βij的影响大, 所以有下式成立

所以能够推

最小和算法的译码步骤如下:

(1) 初始化

对于每一个i和j, 对L (qij) 进行初始化L (qij) =L (si yi) =yi。

可见, 最小和算法不需要任何信道信息, 只要将接收到的信号序列值直接作为初始化输入, 此通用于各种信道。

(2) 校验节点计算

对于每一个i和j, 对L (rji) 进行更新

(3) 变量节点计算

对于每一个i和j, 对L (qij) 进行更新

(4) 计算伪后验LLR值

对于每一个i, 对L Qi进行更新

(5) 译码判决

对于每一个i, 即对码字中的每一位进行判决, 如果, 则xi=0, 否则判为1。在所有比特被译出时, 得到译码码字x∧=x∧1, x∧2, …, x∧N。然后判断校验等式x∧HT=0是否成立, 如果成立, 则结束本次译码, 否则返回步骤 (2) 直到满足校验等式或超过最大迭代次数为止。

2.2归一化BP算法

最小和算法中的校验节点更新计算中的L (rji) 大于基于Gallager方案的LLR-BP算法中的校验节点更新计算中的L (rji) , 所以导致最小和算法译码性能差, 为了改善最小和算法译码性能, J.H.Chen提出归一化BP算法[5]。

归一化BP算法是在最小和算法的译码步骤 (2) 校验节点计算表达式中引入一个常数α (α>1) , 即将式。

可见归一化BP算法的译码性能取决于常数α的选取, 可以使用密度进化方法推导出α的最佳值, 为了简化算法通常将α设为一个常数。

归一化BP算法的译码步骤与最小和算法的译码步骤相似, 区别仅在于步骤 (2) 验节点更新计算不同。

2.3偏置BP算法

由J.H.Chen提出的偏置BP算法即在最小和算法校验节点更新计算表达式中减去一个正常数β, 即偏置BP算法的校验节点更新计算表达式如下:。可见偏置BP算法与最小和算法不同之处在于偏置BP算法中将绝对值幅度小于β的LLR信息设置为0, 消除了其在下次变量节点更新过程中造成的不利影响

偏置BP算法的译码步骤与最小和算法的译码步骤相似, 区别仅在于步骤 (2) 校验节点更新计算不同。

3 简化译码算法性能仿真分析

本文研究LLR-BP算法时, 假设传输信道为加性高斯白噪声信道, LDPC码的编码码字为X= (x1, x2, …, xN) , 采用的调制方式为2PSK, 即将LDPC编码后的码字xn根据规则sn=1-2xn, (n=1, 2, …, N) 映射为序列S= (s1, s2, …, sN) 。则在接收端针对发送符号为sn的接收符号可表示为yn=sn+wn。其中, 对于1≤n≤N, wn是均值为0, 方差为σ2的统计独立的高斯随机变量。

本文应用Matlab软件对基于Gallager方案的LLR-BP算法及其上述三种简化译码算法的误码率性能进行仿真比较。仿真时选用码长为500的规则LDPC码, 仿真框图如图1所示。编码方法选用基于近似下三角校验矩阵的线性编码方法, 译码算法分别采用基于Gallager方案的LLR-BP算法、最小和算法、归一化BP算法和偏置BP算法, 译码迭代次数选取20。归一化BP算法中的常数选为α=1.25, 偏置BP算法中的常数选为β=0.15。基于Gallager方案的LLR-BP算法及其三种简化译码算法的误码率性能仿真结果如图2所示。

从图2的仿真结果可以看出, 基于Gallager方案的LLR-BP算法与其简化译码算法中的归一化BP算法和偏置BP算法的误码率性能相差不多, 当信噪比大于2 dB时, 归一化BP算法和偏置BP算法比基于Gallager方案的LLR-BP算法的误码率性能稍好。最小和算法虽然避免了进行复杂的计算和查表, 但与基于Gallager方案的LLR-BP算法的误码率性能相比, 其误码率性能较差。

4 总结

本文在分析LLR-BP算法译码步骤的基础上, 主要应用MATLAB仿真比较基于Gallager方案的LLR-BP算法及其三种简化译码的性能, 从仿真结果可以看出:基于Gallager方案的LLR-BP算法与归一化BP算法和偏置BP算法的误码率性能相差不多, 当信噪比大于2 dB时, 归一化BP算法和偏置BP算法比基于Gallager方案的LLR-BP算法的误码率性能稍好, 最小和算法误码率性能相对最差。

参考文献

[1]赵传钢, 林雪红, 林家儒.低密度校验码的研究进展.电信科学, 2005; (5) :48—51

[2]王芳, 岳殿武.低密度奇偶校验码及其应用研究.大连海事大学学报, 2006;32 (1) :76—82

[3]胡君萍, 陈宁.LDPC码译码算法的性能分析.武汉理工大学学报, 2006;28 (7) :71—74

[4]岳田, 裴保臣.LDPC码的几种译码算法比较.无线电通信技术, 2006;32 (4) :24—26

译码算法 篇5

关键词：Turbo码,Log-MAP算法,SW-Log-MAP算法,滑动窗

Turbo码是近年来编码理论上的一个重大突破,在大的交织器和BER近似为10-5条件下,它可以逼近理论最优的Shannon信道编码的极限。由于具有出色的纠错性能,Turbo码在各种通信系统中获得了应用,如移动通信、个人通信、深空通信、卫星通信等,其在第三代移动通信(3G)中的应用尤其令人关注。在3G系统中对译码时延要求不高(相对于语音通信而言)的非实时数据通信中广泛采用Turbo编码。Turbo码的优异性能来源于独特的码结构和迭代译码算法。

Turbo码在3G系统中结构[1]可以参见3GPP的建议3G TS25.222,它由一个内部交织器和两个结构相同的RSC分量编码器并行级联而成。Turbo码是一种带有交织器的并行级联码, 它的组成方框图如图1所示。 RSC的生成多项式可表示为$G(D)=\left[1,\frac{g{}_1(D)}{g{}_0(D)}\right]$,其中逆向反馈多项式g0(D)=1+D2+D3,前向反馈多项式g1(D)=1+D+D3。

传统的迭代译码分别对两个RSC码进行最优译码,以迭代的方式使两者分享共同的信息,并利用反馈环路来改善译码器的译码性能。Turbo码的迭代译码器的基本结构如图2所示。

Turbo译码中关于两个分量码译码器DEC1和DEC2的算法有多种,其中MAP算法具有最优的性能,但计算太复杂,因此在实际中最常用到的是既能够保证译码性能,计算复杂度又可以接受的Log-MAP算法[2]。与MAP算法相比较,Log-MAP算法[2]把乘法运算转换成对数域的加法运算,可以减少运算复杂度,更利于实际实现。尽管如此,进一步简化Log-MAP算法的运算量和降低Log-MAP对存储空间的要求对算法的具体实现具有重要意义。

传统的Log-MAP算法通过式(1)计算出对数似然比LLR

$\begin{array}{l}L(b{}_k)=\underset{b{}_k=1}{{\displaystyle \underset{(s^{\prime },s)}{{\displaystyle \max }}}}{}^{*}(\delta {}_{k-1}(s^{\prime })+\xi {}_k(s^{\prime },s)+\\ \epsilon {}_k(s))-\underset{b{}_k=0}{{\displaystyle \underset{(s^{\prime },s)}{{\displaystyle \max }}}}{}^{*}(\delta {}_{k-1}(s^{\prime })+\\ \xi {}_k(s^{\prime },s)+\epsilon {}_k(s))(1)\end{array}$

其中,δk(s)=lnαk(s),ξk(s′,s)=lnγk(s′,s),εk(s)=lnβk(s),αk(s),βk(s)和γk(s′,s)分别为MAP算法中的前向递推、后向递推和分支转移概率。

max*(x,y)=ln(ex+ey)=max(x,y)+ln(1+exp{-y-x})=max(x,y)+fc(y-x),计算max*(x,y)的传统办法有两种:一是通过查表,计算纠正函数fc(y-x)=ln(1+exp{-y-x}),这种方法固然快捷,但要求大量存储空间,而且过于频繁地进行存取也不可取;二是忽略对数分量,将其简化成max(·),此时译码算法退变为次优算法Max-Log-MAP,但性能将受到影响。

1 改进的SW-Log-MAP算法

本文从以下几个方面对传统的LOG-MAP算法进行改进[3,4,5,6],它在保证译码性能的前提下,大大降低其运算复杂度和存储空间。

① 计算对数似然比LLR需要反复调用前向递归α和后向递归β,因此对α和β进行简化,这样能省掉大量的运算量。

② 计算α,β和LLR均需要分支度量γ,而γ中相同的常数在计算软输出时最终被抵消,利用这一规律对γ进行简化,能有效地减少运算量。

③ 针对译码器DEC2进行简化,省掉了DEC2的系统输入的交织操作,并对其引起的其他影响进行修正。

④ 对指数和对数运算进行简化。Log-MAP算法中的max*(·)分成两部分,其中max(·)很容易实现,因此主要困难在于函数fc(x),它是一个单调递减的非线性函数。可采用数值分析的方法对其进行简化,找到逼近fc(x)的简单计算方法,在运算量和存储空间之间取得最佳结合点。

⑤ 由于前向递归α和后向递归β所需存储空间非常大,如果将滑动窗的方法应用于SISO译码模块,将大大减少存储空间,由此得到SW-LOG-MAP算法。SW-Log-MAP算法的Turbo译码器结构框图如图3所示。

2 具体译码过程

第1步:将接收数据(xk,y${}_k^{(1)}$,y${}_k^{(2)}$)分解成(xk,y${}_k^{(1)}$)和(0,y${}_k^{(2)}$),分别作为码字信息送到DEC1和DEC2中。

第2步:设迭代次数j=1,对于DEC1,z1k=0,k=1,2,…,M。

第3步:对于DEC1,利用滑动窗方法对每块数据进行处理,比如每块数据长度取256,两块数据之间交迭长度为30。

改进后的前向递归和后向递归分别为:

α′(sk)=max*[α′(sk-1,bs1)+

γ′(sk-1→sk,bs1),

β′(sk)=max*[β′(sk+1,bs1)+

γ′(sk→sk+1,bs1),

其中,α′(sk-1,bs2)+γ′(sk-1→sk,bs2)],β′(sk+1,bs2)+γ′(sk→sk+1,bs2)],γ′(sk→sk+1)=mk·z1k+xk·mk+y${}_k^{(1)}$·c${}_{1k}^p$,max*(·)中的函数fc(x)采用拟合曲线来表示。

①保留α′(s227)作为下一块数据的α′(sk)的初值。

②根据式(3)计算每一块的外信息lk,并将每块数据中有效的软输出外信息放入总的外信息l1k。

$l{}_k=\ln \left\{\frac{{\displaystyle {\sum }_{S{}_1}\text{e}}\text{x}\text{p}[{\alpha }^{\prime }(s{}_k)+{\gamma }^{\prime }{}^e(s{}_k\to s{}_{k+1})+{\beta }^{\prime }(s{}_{k+1})]}{{\displaystyle {\sum }_{S{}_0}\text{e}}\text{x}\text{p}[{\alpha }^{\prime }(s{}_k)+{\gamma }^{\prime }{}^e(s{}_k\to s{}_{k+1})+{\beta }^{\prime }(s{}_{k+1})]}\right\}(3)$

直到最后一块数据计算完,一个SISO过程结束;

第4步:根据式(4),由外信息l1k和系统数据xk得到DEC2的先验信息z2k送入DEC2。

z2k=(l′1k)interleaver=(l1k+xk)interleaver (4)

第5步:对于DEC2,首先,根据与DEC1同样的滑动窗算法计算l2k。

然后,如果j<最大迭代次数,根据式(5)由前L位外信息l2k得到DEC1的先验信息z1k,送入DEC1中。

z1k=(l′2k)interleaver=(l2k)interleaver (5)

第6步:j=j+1,如果j<最大迭代次数,继续执行第3步进行下一次迭代。

第7步:当j=最大迭代次数,利用式(6)计算总信息Λ2k

Λ2k=l′2k+z2k (6)

第8步:将Λ2k解交织得到对数似然比LLR,与0门限相比较,进行硬判决,得到译码比特$\widehat{b}{}_k$的估计值:

若L(bk)≥0,则译码比特$\widehat{b}{}_k$为1

若L(bk)<0,则译码比特$\widehat{b}{}_k$为0

第9步:执行完当前帧的译码数据后,转到第1步对下一帧数据进行译码。

3 算法性能分析

下面将通过MATLAB仿真对Turbo码的误码率性能进行研究,仿真中的相关约定如下:

①信道类型:AWGN。

②编码方案:3GPP提出的Turbo码编码方案。

③调制类型:BPSK。

④SW-Log-MAP算法的滑动窗参数:每块数据长度为256,两块数据交迭长度为30。

⑤交织长度为1024,8次迭代。

图4所示的仿真表明:虽然改进的SW-Log-MAP在算法复杂度和存储空间上比传统的Log-MAP性能减少了很多,但是保持着原有Log-MAP算法的优良性能。

参考文献

[1]3GPP TS25.222V3.5.0,3rd Generation Partnership Project;Tech-nical Specification Group Radio access Network;Multiplexing and channel coding(TDD),2000-12[Z].

[2]Robertson P,Hoeher P,Villebrun E.Optimal and sub-optimal maxi-muma posteriori algorithms suitable for turbo decoding[J].European Trans.On Telecommun.Mar.-Apr.1997,8(2):119-125.

[3]Pietrobon S S.Efficient Implementation of Continuous MAP Decoders and a Synchronisation Technique for Turbo Decoders[C].Proc.Int.Symp.Inform.Theory Appl.,Victoria,Canada,Sep,1996:586-589.

[4]Benedetto S,Divsalar D,Montorsi G,et al.Soft-Output Decoding Algorithms for Continuous Decoding of Parallel Concatenated Convolu-tional Codes[C].Proc.ICC’96,Dallas,USA,June,1996:112-117.

[5]Viterbi AJ.An Intuitive Justification and a Simplified Implementation of the MAP Decoderfor Convolutional Codes[J].IEEEJ.Selected Ar-ea in ommun.,1998,16(2):260-264.

LT编译码算法的DSP实现 篇6

LT(Lucy Transform)码是第一类基于纠删码技术的高效率无码率码[1],同时也是第一类Fountain码。Fountain码的设计思想来源于水喷泉:服务器可以随机生成编码信息包,一个客户端从一个或者多个服务器接收编码包,一旦接收到足够的编码包N就可以重构出源信号,N的数量与信道特性无关。Fountain码的特性决定其十分适合用于计算机网络、广播信道、无线传感器网络等信道的信息传输。2003年Lucy提出LT码[2],LT码对于具有不同删除概率的各种删除信道均是逼近最优的。

鉴于DSP技术精度高、速度快、成本低、灵活性强、可靠性好的特点,DSP技术被越来越多地运用于信道编码领域。通过研究,Turbo码[3]、卷积码[4]、LDPC码[5]等大部分早期码的编译码器都通过DSP等技术得以实现。但由于LT编译码器的数据运算量和内存使用量随编码长度的增加而快速增大[6],使用DSP技术实现LT码编译码器必须要解决两个难题:1)如何设计编译码算法,简化程序,减少CPU负担;2)如何建立信息储存机制,存储度邻接信号表,合理利用DSP芯片片上内存资源。

本文使用反馈控制信号,控制编码信号的码长,降低编码器功耗;引入冗余信息处理程序,剔除编码信号中的冗余,提高LT译码效率;建立度邻接信号表的位置系数储存机制,合理存储度邻接信号信息,减少DSP芯片片上内存使用量。最终采用TI公司的TMS320VC5416芯片,在CCS(Code Composer Studio)集成开发环境下使用C语言编程[7],设计和实现了LT编译码器。

1 LT编译码算法的DSP硬件实现

本文采用TI公司的TMS320VC5416芯片,整个系统的硬件结构如图1所示。

在编码器中,源信号通过串口(RS-232接口)传入芯片。由于数据采用异步传输,可以采用DSP的McBSP结合DMA,在不扩展硬件的情况下,用软件实现异步数据传输。但该方法软件设计复杂,加大了CPU的负担,因此添加TI公司的TL16C550异步串行通信收发器来实现异步数据传输。此外,使用TI公司的双路低压差电源调节器芯片TPS767D301给TMS320VC5416芯片供电,使用TI公司的Flash芯片AM29LV800保存编译码程序段,以便在系统启动时将编(译)码程序装载进DSP内部DARAM运行。

译码器从通信信道异步接收到编码信号后进行译码。译码过程中译码器通过通信信道发送反馈信息给编码器,控制编码器的工作。

2 LT编译码法的DSP软件实现

2.1 LT编码算法的DSP软件实现

图2为LT编码算法的软件流程图。编码器接收到k个信源信号后,根据信道删除率设定编码信号的数量N=B×k, 1.0<B<2.0。根据稳健弧波分布确定N个编码信号的度值,随机均匀选择每个编码信号的度邻接信号,异或运算得到N个编码信号,通过通信信道发送。

2.1.1 反馈控制信号ACK

使用反馈控制信号ACK,控制编码器工作。ACK由译码器判定生成,初值设定为ACK=0。

当译码器未成功译码时,译码器生成ACK=1,反馈到编码器。编码器在接收到ACK=1信号后,根据信源信号码长k确定添加N=b×k,0.01≤b≤0.10个编码信号。

当译码算法结束,ACK=0,编码器停止工作,LT编译码算法结束。

2.1.2 编码信号度值的确定

稳健弧波分布(Robust Soliton distribution)μ(k)是LT编译码算法中普遍使用的度分布函数。其将理想弧波分布ρ(i)和补充分布τ(i)相结合,并且通过统一化处理得到。如式(1)～(4)所示

$\begin{array}{l}\rho (i)=\{\begin{array}{l}1/k,i=1\\ 1/i(i-1),i=2,3‚...,k\end{array}(1)\\ \tau (i)=\{\begin{array}{l}R/(ik),i=1,...,k/R-1\\ R\text{l}\text{n}(R/\delta )/k,i=k/R\\ 0,i=k/R+1,...,k\end{array}(2)\\ \beta ={\displaystyle \sum _{i=1}^k\rho }(i)+\tau (i)(3)\\ \mu (i)=(\rho (i)+\tau (i))/\beta ,i=1,2‚...,k(4)\end{array}$

式中:$R=c\cdot \ln (k/\delta )\sqrt{k}$;c和δ为两个独立的参数。

根据稳健弧波分布确定编码信号的度分布率函数μ(k)。根据μ(k)将时隔[0,1]划分成非重复且不等的k个子时隔,每个子时隔与每个度值一一对应[8]。例如:0.0～μ(1)对应度值1,μ(i) ～μ(i+1)对应度值i+1。

本文使用srand函数设置随机数发生器的初始化种子seed=s1。当第一次生成编码信号时,使用rand函数生成[0,1]区间长度为N的随机数列。确定随机数列中第i项值所处的子时隔,根据对应关系确定第i个编码信号的度值di。记M为添加编码信号的次数,T为已生成的编码信号的数量,T=B×k+(M-1)×b×k。当添加编码信号时生成[0,1]区间长度为T+N的随机数列,确定随机数列中第T+i项值所处的子时隔,根据对应关系确定新加的第i个编码信号的度值di。

2.1.3 编码信号度邻接信号的确定

编码信号的度邻接信号从k个信源信号中随机均匀选择,所以随机均匀选择的效果将直接影响到LT编译码算法的效率。

设置随机数发生器的初始化种子seed=s2(s1≠s2),当第一次生成编码信号时,生成[0,k]区间长度为di的不重复随机数列{adi}。取出{adi}中第ai(i=1,2,…,di)个信源信号做为该编码信号的度邻接信号。当添加编码信号时,记前T个编码信号的度值总和为n,先生成[0,k]区间长度为n的不重复随机数列,再生成[0,k]区间长度为di的不重复随机数列{bdi}。取出{bdi}中第bi(i=1,2,…,di)个信源信号做为该编码信号的度邻接信号。

2.2 LT译码算法的DSP软件实现

在发送端和接收端建立seed表,接收端在接收编码分组后根据seed表序列号确定seed值,进而得到编码信号的度和度邻接信号表,进行译码。图3为LT译码算法的软件流程图。

将编码信号及其度邻接信号表存储后,根据反馈控制信号ACK,对新添加的编码信号及其度邻接信号表进行冗余信号处理。寻找度为1的编码信号开始进行译码。当编码信号被释放后,删除该编码信号及其度邻接信号表。重复以上步骤,至度为1的编码信号耗尽。如信源信号未被完全恢复,则生成反馈控制信号ACK=1,编码器添加编码信号。

2.2.1 度邻接信号表的位置系数存储机制

在LT译码算法中,存储编码信号的度邻接信号表占用了大量的DSP芯片片上内存空间,所以采用合理的度邻接信号表存储机制,可以减少DSP芯片片上内存使用量。

若不经处理直接对度邻接信号表进行存储,1个16 bit的整形数据中仅能存储1位度邻接信号表信息,对DSP片上内存空间造成了极大浪费,极大地限制了信源信号数量k的选择范围。

为了克服原始存储机制的缺点,可使用二进制位存储机制。通过位操作在16 bit的整型数据中存储16位的度邻接信号表信息。这样能够将存储度邻接信号表所需的内存缩小为原先的1/16左右。但当k值较大时,使用该存储机制存储仍需占用很大的存储空间。例如,当k=1 024时,每一个编码信号的度邻接信号表都需要占用约64×16 bit的内存空间。

根据文献[2]所述,编码信号的平均度为

D=O(ln(k/δ)) (5)

式中:当k值较大时,编码信号的度小于k/16,所以通过存储度邻接信号的位置系数可以减小度邻接信号表的存储空间。本文使用位置系数存储机制将将每个编码信号的度邻接信号位置系数按顺序存储。

通过使用位置系数存储机制,减小了用于储存编码信号度邻接信号表的内存,提高了可选信源信号数量k的上限值。表1为3种度邻接信号表存储机制的性能参数。采用二进制存储机制可以在原始存储机制的基础上提高k的上限4倍,而采用位置系数存储机制又可以在二进制存储机制的基础上再提高k的上限3倍。

2.2.2 冗余信息处理程序

当ACK=1时,译码程序已经恢复了部分源信号,新添加的编码信号带有冗余信息,需要进行处理,删除冗余信息,提高节点携带信息质量,加快译码算法。

经过译码,信源信号si已经被恢复。译码端接收到N个新编码信号,其中一部分编码信号携带了信源信号si的信息(该编码信号的度邻接信号表中存储有信源信号si的位置系数i),则将该编码信号与源信号si进行异或运算,并将其度邻接信号表中的位置系数i置0。重复上述操作,至N个新编码信号及其度邻接信号表都得到处理。

3 实验数据与结论

本文设置信源信号数量k=1 536,c=0.01,δ=0.05,B=1.05,b=0.01,即第一次生成编码信号数量为N=1.05×k≈1 612,添加的编码信号数量为N=0.01×k≈15,进行100次实验。

图4显示了该LT译码器译码码长N的分布柱状图。通过观察发现,译码码长集中于1 672～1 717,当N的值增加至1 717时,LT译码器的译码成功率达到了86%。通过分析,修改设置B=1.12,b=0.01,可以在不添加编码信号的情况下使译码器以很高的概率恢复信源信号,降低译码延时,提高LT码的传输效率。

图5显示当B=1.12,b=0.01时LT译码器译码成功率与添加编码信号次数M的关系曲线。通过观察发现当第一次生成编码信号的数量为N=1.12×k≈1 720时,译码成功率已经达到89%,即使译码不成功也只需添加很少数量的编码信号就能保证译码成功率达到100%。通过计算得到,通过重新设置,当信源信号长度k=1 536时,LT译码器译码码长的均值为1 726,编码效率达到0.890。

4 结论

本文使用反馈控制信号,控制编码信号的长度,降低了LT编码算法功耗;使用C语言函数生成随机数列,改善了编码信号的度和度邻接信号的随机选择效果;建立位置系数储存机制、缩小了储存信息所需的DSP芯片片上内存空间,提高了LT编译码器的性能;引入冗余信息处理程序,剔除编码信号的冗余,提高了译码效率。通过实验表明,当信源信息码长为1 536时,本文提出的基于DSP技术实现的LT编译码算法的译码码长均值为1 726,编码效率为0.890。

参考文献

[1]MACKAY D J C.Fountain codes[C]//Proc.IEEE Communications.[S.l.]:IEEE Press,2005:1062-1068.

[2]LUBY M.LT Codes[C]//Proc.43rd Annual IEEE Symposium onFoundations of Computer Science.[S.l.]:IEEE Press,2002:271-280.

[3]彭玉吉.Turbo码编译码技术的研究及DSP实现[D].成都:电子科技大学,2007.

[4]张博.卷积码的译码研究及DSP实现[D].天津:天津大学,2008.

[5]陈蓉.LDPC编译码的DSP实现[D].苏州:苏州工业大学,2009.

[6]侯登峰,朱晓晶,崔慧娟,等.Raptor码在TMS320C55X DSP上的实现及优化[J].电视技术,2010,34(S2):26-30.

[7]张勇.C/C++语言硬件程序设计——基于TMS320C5000系列DSP[M].西安:西安电子科技大学出版社,2003.

译码算法 篇7

低密度奇偶校验码(Low-density parity-check,LDPC codes)由Gallager提出[1],它具有逼近香农极限的性能,编码增益高,正逐步应用于深空通信、压缩图像传输、图像数字水印等技术中。[]

1962年,Gallager提出BF算法[1]采用硬判决译码方式,复杂度低,易于硬件实现,但译码性能差。1996年,MacKay证明[2,3]BP算法译码性能优异,但复杂度高,需要运算时间和硬件资源较多。因此有人提出了BP算法和BF算法相结合的HBF译码算法[4],在相同译码复杂度时,通过设置迭代次数,提高译码性能。2001年,WBF算法[5]被提出,利用接收序列的可靠性信息对校验节点传递给变量节点的翻转判据进行加权来增强纠错能力。

本文结合深空通信信道的特点[6],将BP算法和WBF算法相结合,提出一种LDPC码改进译码算法,在保持优异译码性能的同时,能够降低译码运行时间,并且分析不同情况对改进译码算法性能的影响。

1 LDPC码译码算法

1.1 BP算法

BP(Belief Propagation)算法[3]属于软判决算法,各节点间传递的信息是概率或置信信息。

设系统输入码字为x=[x1,x2,…,xN],译码器接收码字为y=[y1,y2,…,yN],校验矩阵H的维数为M×N。定义Vj为校验矩阵第j行中的“1”的列标的集合,即与校验节点cj相邻的变量节点的集合;Vji为除变量节点vi外其它与校验节点cj相邻的变量节点的集合;Ci为校验矩阵中第i列中的“1”的行标的集合,即与变量节点vi相邻的校验节点的集合;Cij为除校验节点cj外其它与变量节点vi相邻的校验节点的集合;Pi为迭代前仅由信道特征得到的码字中第i个比特是“1”的概率;rji(b)为在码字中第i个比特为b且其它比特服从分布{qij'}j≠j'时,满足第j个校验方程的条件概率;qji(b)为除校验节点cj外其它校验节点提供外信息时变量节点vi为b的概率;Kij为qij(b)的归一化因子,以保证qij(0)+qij(1)=1;Qi(b)为比特i的伪后验概率;Ki为Qi(b)的归一化因子,以保证Qi(0)+Qi(1)=1。概率域BP算法译码过程如下:

1)对所有满足校验矩阵hji=1的j、i,将Pi、1-Pi作为先验信息对qji(b)进行初始化:

2)校验节点更新。更新rji(b),定义δqji≡qji(0)-qji(1),δrji≡rji(0)-rji(1),则有:

3)变量节点更新。更新qji(b),则有:

4)计算比特i的伪后验概率Qi(b),则有:

5)译码判决,若Qi(1)>0.5,令xi=1,否则令xi=0,得到码字x=(x1,x2,…,xN),计算xHT是否为零向量,若是,则结束循环;若不是,返回步骤2)继续循环直至得到许用码字或达到最大循环次数。

1.2 WBF算法

WBF(Weighted Bit Flipping)算法[5]属于硬判决译码算法,设校验矩阵H的维数为M×N,定义:

其中l∈{0,N-1},j∈{1,M},Sl和El分别表示码元l处的校验和与加权校验和,e=(e0,e1,…,eN-1)表示加权一步多数逻辑(weighted one-step majoritylogic,weighed-MLG)译码算法[7]的错误图样,则WBF算法的实现步骤如下:

1)计算校验和,若校验矩阵全满足,停止译码;

2)用公式(10)计算码元l的加权校验和El;

3)计算El的最大值,找到其对应的码元l;

4)将步骤3)的码元l所对应的变量节点的比特翻转,得到新的译码码字;

5)重复上述步骤,直至所有的校验方程都满足或者达到预先设定的最大迭代次数为止。

2改进的LDPC码译码算法

2.1改进译码算法过程

BP算法具有优异的译码性能,但是复杂度大,运行时间长,且会在临界值处产生较大的误码率[4]。通常,码字临界处恰好对应接收符号幅度接近0的位置。WBF算法正是利用信道输出幅度的最小值作为加权因子,才增强了算法的纠错能力,因此将WBF算法的提高纠错能力的方法应用于BP算法,并保持BP迭代基本结构不变。设译码器接收码字为y=(y1,y2,…,yN),改进译码算法具体步骤描述如下:

1)计算信道输出码字幅度的最小值:

2)进行一次的传统BP译码,设得到的译码输出结果为^Z°=(^z°1,^z°2,…,^z°N);

3)设校验矩阵HM×N=[h1,h2,…,hM]T,由公式(13)得校验和^Sk-1=(^sk-11,^sk-12,…,^sk-1M)。若^Sk-1=0,停止迭代;若^Sk-1≠0,进行步骤4);

4)用公式(14)计算传递给变量节点的软信息;

5)用公式(15)计算每个变量节点的翻转判据;

6)翻转最大的fk-1n对应的比特zk-1n,得到新码字^Zk;

7)用公式(16)重新计算校验和^Sk。若^Sk=0,停止迭代;如果^Sk≠0,进行步骤1);

8)重复2)至7),直到所有校验式都满足或者达到事先设定的最大迭代次数为止。

2.2改进译码算法性能分析

设LDPC码的码长为N,校验矩阵的列重为d。从译码算法可知,BP迭代译码算法迭代1次需要(2d2+2d+1)N次加法和(4d2+5d+4)N次乘法;WBF算法迭代1次需要(4d+1)N次加法和d次乘法。由于校验矩阵是稀疏的,故列重d远小于码长N,因此BP算法迭代1次的运算量远大于WBF算法。当BP算法和改进译码算法的最大迭代次数分别为p+1和p次时,前者的复杂度分别为(p+1)×(2d2+2d+1)N次加法,(p+1)(4d2+5d+4)N次乘法,后者的复杂度为p(2d2+6d+2)N次加法和p(4d2+5d+4)N+pd次乘法,可见后者的复杂度远小于前者,而且由于改进译码算法中加入了加权比特翻转和两次校验式判断以提高获得许用码字的速度,当获得许用码字时实际需要的迭代次数小于设定的最大迭代次数,所以实际译码过程中改进译码算法的复杂度比上述计算结果还要小,亦即小于BP算法的复杂度。

改进译码算法中虽然加入了WBF迭代并且多了一次校验式判断,但其基本迭代结构仍和传统BP算法相似,所以改进译码算法依然可以保持和传统BP算法相似的优异译码性能。

3 仿真结果和分析

本文选取加性高斯白噪声(Additive white Gaussian noise, AWGN)信道,归一化信噪比表示为Eb/N0=A2/2Rσ2,其中,Eb为单位比特平均能量,No为噪声功率谱密度,A为传输信号幅度,R为码率,σ2为噪声方差(见图1)。算法的运行时间是复杂度的衡量指标之一,复杂度越大,算法运行时间越长。设传统BP算法和改进译码算法的平均运行时间分别为t1和t2,记Ratio=(t1-t2)/t1×100%为改进译码算法相对于传统BP算法平均运行时间减少的比例。

3.1 不同最大迭代次数条件下的仿真结果

图2表示不同最大迭代次数对改进译码算法误码率的影响。其中传统BP算法最大迭代次数为20次,改进译码算法的最大迭代次数分别为5、10、15、20、30、40、50、60次。可以看出,对于改进译码算法的误码率总体趋势是随着Eb/N0增加而降低,最大迭代次数从5次增加到20次时,误码率明显降低,但是当最大迭代次数增大到大于20次后,误码率改善程度微乎其微。当改进译码算法最大迭代次数与传统BP译码算法一样时,其误码性能和传统BP算法近似相等。当改进算法最大迭代次数大于传统BP译码算法时,其误码性能略好于传统BP算法,但是最大迭代次数的增大对改进算法误码性能的改善程度的影响很小。当改进算法最大迭代次数小于传统BP算法时,其误码性能比传统BP算法差,而且最大迭代次数越小,改进算法误码性能和传统BP算法相差越明显,当最大迭代次数是传统BP算法的1/4时,在误码率为10-6时,改进算法比传统BP算法性能差0.3 dB。

图3表示不同最大迭代次数对改进译码算法平均运行时间的影响。因此可以发现,和传统BP算法相比较,在Eb/N0不大于1 dB的情况下,当改进译码算法的最大迭代次数为传统BP算法的3倍时,改进译码算法相对于传统BP算法平均运行时间减少的比例只有10%左右,随着最大迭代次数的减少,改进译码算法相对于传统BP算法平均运行时间减少的比例逐渐增大。当二者的最大迭代次数相等时,改进译码算法相对于传统BP算法平均运行时间减少的比例约为66%,当改进BP算法的最大迭代次数减少到传统BP算法的1/4时,改进译码算法相对于传统BP算法平均运行时间减少的比例89%左右。这是由于改进BP算法中增加了比特翻转和进一步的校验式判断,所以加快了迭代收敛的速度,减少了实际迭代次数,从而减少了译码算法运行时间。

当Eb/N0大于1 dB时,改进译码算法相对于传统BP算法平均运行时间减少的比例增大为92%以上,但是最大迭代次数的选择对改进译码算法的运行时间影响不大,改进译码算法相对于传统BP算法平均运行时间减少的比例基本不变。这是由于随着Eb/N0的增大,迭代译码发生误判的可能性减小,虽然设置的最大迭代次数不同,但实际上进行的迭代次数达到某一小于最大迭代次数的数值后,译码结果已经满足校验式,迭代提前结束。

3.2 不同码长条件下的仿真结果

图4表示不同码长对改进译码算法误码率的影响。其中码长的选择范围为512,576,1 024,1 536,2 048,2 304。由此可以看出,对于改进译码算法,其误码率曲线总体趋势是随着Eb/N0的增加,误码率降低,当Eb/N0不大于1 dB时,码长对误码率的影响很小,当Eb/N0大于1 dB时,在相同Eb/N0下,码长越长,误码率越低。在码长相同时,改进BP算法的误码率和传统BP算法近似相等。

图5表示不同码长对改进译码算法平均运行时间的影响。可见随着Eb/N0的增大,改进译码算法相对于传统BP算法平均运行时间减少的比例逐渐增大,即改进译码算法的复杂度比传统BP算法降低的越多。码长越长,改进译码算法相对于传统BP算法平均运行时间减少的比例越大。在码长为512时,Eb/N0较低情况下,改进译码算法相对于传统BP算法平均运行时间减少的比例约为30%,随着Eb/N0的增加,改进译码算法相对于传统BP算法平均运行时间减少的比例增大为81%;而当码长增加到2 304时,Eb/N0较低情况下,改进译码算法相对于传统BP算法平均运行时间减少的比例约为86%,随着Eb/N0的增加,改进译码算法相对于传统BP算法平均运行时间减少的比例增大到96%以上。

3.3 不同码率条件下的仿真结果

图6为不同码率对改进译码算法误码率的影响。码率选择范围为1/2,2/3,3/4,5/6。可见,对于改进译码算法,当Eb/N0不大于1 dB时,码率对误码率的影响很小,当Eb/N0大于1 dB时,在相同Eb/N0下,码率越小,误码率越低。码率相同时,改进译码算法的误码率和传统BP算法近似相等。

图7表示不同码率对改进译码算法平均运行时间的影响。可见,随着Eb/N0的增大,改进译码算法相对于传统BP算法平均运行时间减少的比例逐渐增大。码率越小,改进译码算法相对于传统BP算法平均运行时间减少的比例越大。在码长为5/6时,Eb/N0较低情况下,改进译码算法相对于传统BP算法平均运行时间减少的比例约为18%,随着Eb/N0的增加,改进译码算法相对于传统BP算法平均运行时间减少的比例约为42%甚至更大;当码率减小到1/2时,Eb/N0较低情况下,改进译码算法相对于传统BP算法平均运行时间减少的比例约为43%,随着Eb/N0的增加,改进译码算法相对于传统BP算法平均运行时间减少的比例增大到83%以上。

4 结论

本文将BP算法和WBF算法相结合,提出一种改进的LDPC码译码算法,首先进行一次BP迭代,然后计算是否满足校验方程,若满足则将已经产生的结果作为译码结果输出,若不满足,则对译码结果中翻转判据最大的码元进行翻转,再次进行校验式检验,决定是否继续进行迭代译码。所以改进译码算法可以增强迭代过程的纠错能力,加快得到许用码字的速度,从而降低译码实际迭代次数,减少译码算法运行时间。在BP迭代中加入校验式判断和比特翻转的同时不改变BP算法的基本迭代结果,所以改进译码算法可保持和BP算法相近的优异译码性能。

本文还在不同最大迭代次数、不同码长、不同码率情况下,仿真了改进译码算法的性能,并与传统BP算法进行比较。结果表明,最大迭代次数越大,改进译码算法相对于传统BP算法平均运行时间减少的比例越小,即译码复杂度降低程度越小,在一定范围内其误码率越低,但是当最大迭代次数增大到一定数值后,改进译码算法误码性能几乎不再变化;码长越长,改进译码算法相对于传统BP算法平均运行时间减少的比例越大,即译码复杂度降低程度越大,但是在相同情况下其误码率越小;码率越大,译码算法的误码率越大,而且相对同样条件下的传统BP译码算法平均运行时间减少的比例越小,即译码复杂度降低程度越小。

摘要：针对传统BP算法运算复杂度较高的问题,将BP算法和WBF算法相结合提出LDPC码改进译码算法。在每次BP迭代译码中加入校验式判断,并利用一定的翻转判据进行加权。然后对满足条件的位进行翻转,再次进行校验式判断,加快获得许用码字的速度。在加性高斯白噪声信道下的仿真结果表明,此改进译码算法能有效降低译码的平均运行时间,并且能够保持和传统BP算法一样的优异译码性能。并针对不同最大迭代次数,不同码长,不同码率情况,对改进译码算法和传统BP算法的性能进行详细比较。

关键词：低密度校验码,置信传播译码算法,加权比特翻转译码算法,比特误码率,平均运行时间

参考文献

[1] Gallager R G.Low-density parity-check codes.IRE Transactions onInformation Theory,1962;1:21—28

[2] MacKay D J C.Good error-correcting codes based on very sparse ma-trices.IEEE Transactions on Information Theory,1999;3,45(3):399—431

[3] MacKay D J C,Neal R M.Near Shannon limit performance of lowdensity parity check codes.Electronics Letter's,1996;32(18):1645—1646

[4]周立媛,张立军,陈常嘉.低密度校验码的混合比特反转译码算法.北京交通大学学报,2005;29(2):47—50

[5] Kou Y,Lin S,Fossorier M.Low-density parity-check codes based onfinite geometries:a rediscovery and new results.IEEE Transactions onInformation Theory,2001;11,47(7):2711—2736

[6]翟政安,罗伦,时信华.深空通信信道编译码技术研究.飞行器测控学报,2005;6,24(3):1—5

译码算法 篇8

关键词：线性分组码,BCH,译码性能,误码率

1引言

衡量一种纠错码译码方法性能好坏的主要标准是其误码率指标。而要评估该译码方法在指定误码率下所需的输入信噪比,就需要获取较宽信噪比范围内的误码率曲线。目前对误码率的评估均是通过计算机数值仿真得出,由蒙特卡罗仿真原理,通常需要测得100个误码才能确保统计得到的误码率有足够好的置信度。比如某应用系统要求误码率指标低于10-5,则仿真样本至少为107,如此大量的数据仿真耗费的计算机资源和计算时间是相当惊人的,甚至是不可实现的。

然而,高信噪比条件下的高斯白噪信道中,信道传输出现大量错误的概率是非常小的,因此可以只考虑在每个码字中出现很少几位错误的情况,而忽略发生概率极小的出现多位错误的情况。基于这种认识,本文提出了一种数值仿真和理论估算相结合的方法:在信噪比低于阈值时,用传统的数值仿真技术得出其误码率;当信噪比高于阈值时,用理论估算得出其误码率,把两段误码率曲线拼接起来即可得到整个信噪比范围内的误码率曲线。采用该方法可以在普通的计算机配置和可接受的仿真时间内,准确地获取整个信噪比范围的误码率曲线。

2线性分组码的硬译码性能分析

2.1 译码方法

线性分组码是目前研究最多也是应用最广的一种纠错码,因此本文以线性分组码的硬译码性能为研究对象进行讨论。

在以下讨论中,约定以C表示发送码字,E表示高斯白噪信道产生的错误图样,E′表示译码器得出的错误图样,R表示接收矢量的硬判决结果,S表示接收矢量的伴随式,undefined表示译码结果,H表示线性分组码的一致校验矩阵。

对线性分组码的硬译码分以下几步完成[1]:

(1) 对接收信号进行硬判决,R=C+E;

若ri<0,则Ri=1;若ri≥0,则Ri=0

(2) 由R得到接收矢量的伴随式,S=R·HT=(C+E)·HT=E·HT;

(3) 根据伴随式S确定错误图样E′;

(4) 得出译码结果,undefined。

2.2 理论分析

对于最多可纠正t位错的(n,k,t)线性分组码,由纠错码理论可知,其一致校验矩阵H中任意2t列均线性无关[1],即:

hi1+hi2+…+hit+hi(t+1)≠hj1+hj2+…+hj(t-1) (1)

其中,hip,hjq,(1≤ip≤n,1≤jq≤n)是H矩阵的列向量,且hip≠hjq。

假设对发送码字C,信道产生的错误图样E的重量W(E)=t+1时, 则接收矢量R的伴随式为:

undefined

由式(1)得:

undefined

即S不可能写成H中任何t-1个列向量之和,这说明译码器得到的错误图样E′的重量W(E′)>t-1。又因为(n,k,t)线性分组码错误图样的重量W(E′)≤t,由此得到W(E′)=t。因此,式(2)可写为:

undefined

即该接收矢量的伴随式S既可以用H中的t+1个列向量来表示,也可以用H中的t个列向量来表示。

只要式(4)中第二个等号两边的2t+1项有一项相同,则余下2t-1项线性相关,这与(n,k,t)码H矩阵任意2t列均线性无关矛盾。因此式(4)中所有2t+1项均不相同,即译码器得出的错误图样E′与信道本身产生的错误图样E在非零码元位置上完全不重合。因此纠错译码将在硬判决t+1位误码的基础上,再增加t位误码,导致该码字最终结果有2t+1位发生误码。

2.3 误码率估计

在分析误码性能时,假设发送端发送全零码字而不失一般性。经过加性高斯白噪信道传输,接收信号的每一位都服从均值为A(信号幅度)方差为σ2(噪声功率)的正态分布,由此得接收矢量R每一位发生错误的概率[3]:

其中信噪比SNR=A2/(2σ2)。

由2.2节的分析可知,当信道传输出现t位以内的错误时,(n,k,t)线性分组码可以完全纠正传输错误,误码为0。当信道传输出现t+1位错误时,纠错译码后共有2t+1位误码。忽略信道传输出现大于t+1位错误的情况,得到对(n,k,t)线性分组码在高信噪比时的误码率估计[2]:

undefined

若假设由伴随式S确定的错误图样E′最大限度地不同于实际传输错误图样E,则误码率的上限可以由下式表示:

undefined

因此由式(6)得到的误码率估计与实际误码率相对误差的上限为:

undefined

由式(8)得出最大相对估计误差与信噪比的关系如图1所示。

图1画出了BCH(15,11,1),BCH(15,7,2)和BCH(31,16,3)三种线性分组码的误码率估计相对误差与信噪比的关系。可以看出,当信噪比为6 dB时,最大相对误差约10-2,并且相对误差随信噪比增大而迅速减小。这说明当信噪比大于6 dB时,式(6)的估计可以得到与实际误码率几乎一致的结果,因此将BCH码的信噪比阈值定为6 dB。

2.4 仿真结果

最终的试验验证以BCH(15,11,1)码的硬译码误码率计算为例,在Matlab平台上进行仿真。

由图 2可知,当信噪比大于6 dB时,实际误码率与估计误码率的差别已经非常小,从而验证了上述理论推导的结论。由图2还可以看出,对应于仿真时间约9 h,只能得到7 dB以内的有效误码率曲线(仿真点数107,有效误码率为10-5量级)。若要得到更高信噪比下的误码性能,必须使仿真点数按指数增长,从而使得仿真时间迅速增加以致不可接受。

利用本文提出的方法可以很方便地得到BCH(15,11,1)码译码算法在整个信噪比范围内的误码率性能曲线。由图 2的理论估算曲线可知,信噪比为6 dB时,误码率约10-4,因此仿真点数取106。此时在同样的计算机配置下,只需大约80 min,大大节约了仿真时间。最后结果如图3所示。

通过以上分析,得到译码算法的快速性能分析步骤如下:

(1) 由式(8)得到数值仿真和理论估算的信噪比阈值。

(2) 由式(6)计算信噪比阈值处的误码率,由此得到所需的仿真点数。

(3) 分别做计算机数值仿真和误码率理论估算。信噪比低于阈值部分误码率取自仿真数据,信噪比高于阈值部分误码率取自理论计算数据,将两部分误码率拼接起来即可得到整个信噪比范围内的误码率曲线。

3结语

本文提出的低信噪比下进行数值仿真与高信噪比下进行理论估算相结合的方法来获取较宽信噪比范围内的纠错码误码性能,可以大大节省仿真时间,并且有很高的准确度。通过仿真试验,证实了该方法对线性分组码是可行和有效的。并且在可以比较方便地估计出高信噪比条件下误码率时,该方法也可以推广到其他纠错码的硬译码以及软译码中。

参考文献

[1]王新梅,肖国镇.纠错码———原理与方法(修订版)[M].西安:西安电子科技大学出版社,2001,

[2]张力军,张宗橙,郑宝玉.数字通信[M].4版.北京:电子工业出版社,2003.