datasheet
超过460,000+ 应用技术资源下载
pdf

Turbo乘积码的译码算法及FPGA实现

  • 1星
  • 日期: 2014-03-05
  • 大小: 1.78MB
  • 所需积分:1分
  • 下载次数:0
  • favicon收藏
  • rep举报
  • 分享
  • free评论
标签: Turbo乘积码的译码算法及FPGA实现

在信道编码的发展进程中,编码研究人员一直致力于追寻性能尽可能的接近Shannon极限,且译码复杂度较低的信道编码方案。1993年Berrou等提出了Turbo码,这种码在接近香农极限的低信噪比下仍能够获得较低的误码率,它的出现在编码界引起了广泛的关注,并成为编码研究领域最新的发展方向之一。但Turbo码也有其缺点,由于交织器的存在,致使译码复杂度高,译码时延长且因为低码重码字,存在错误平台现象。在Turbo码的基础上,1994年,Pyndiah等提出了Turbo乘积码,Turbo乘积码继承了Turbo码的优点,又因为Turbo乘积码的构造采用了线性分组码,所以译码方法比Turbo码简单。Turbo乘积码近年来开始被广泛到应用到各种通信场合,大有取代传统的卷积码之势。 本文首先围绕Turbo乘积码的编译码原理,阐述了涉及到的基础知识;又据Turbo乘积码目前的应用状况,回顾了Turbo码的发展历史;其次,根据Turbo乘积码的构造原理,探讨了构造的方法,交织类型,子码的选择及子码的性能;再次,研究了Turbo乘积码的概率译码,基于外信息的迭代算法,研究了Chase的译码算法;最后通过软件仿真实现了该迭代译码算法,得到的结果达到了通信接收的要求。 本文还初步的阐述了Turbo乘积码硬件实现系统的设计方案。据实际工作中碰到的非标准信号,给出了整体模块设计图,及相应模块的功能和模块问连接的各种参数。并实现了模态下的同步搜索和去除相位模糊功能。最后根据研究中碰到的各种问题,提出了下一步工作建议和研究方向。

山东大学 硕士学位论文 Turbo乘积码的译码算法及FPGA实现 姓名:顾丽旺 申请学位级别:硕士 专业:电子与通信工程 指导教师:袁东风;徐军 20070907 原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独 立进行研究所取得的成果。除文中已经注明引用的内容外,本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体,均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名:团。丝盟 蝉’ 日期: 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定,同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版,允许论 文被查阅和借阅;本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索,可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 (保密论文在解密后应遵守此规定) 论文作者签名:硒随鱼。导师签名 摘要 在信道编码的发展进程中,编码研究人员一直致力于追寻性能尽可能的接近 Shannon极限,且译码复杂度较低的信道编码方案.1993年Berrou等提出了Turbo 码,这种码在接近香农极限的低信噪比下仍能够获得较低的误码率,它的出现在 编码界引起了广泛的关注,并成为编码研究领域最新的发展方向之一.但Turbo 码也有其缺点,由于交织器的存在,致使译码复杂度高,译码时延长且因为低码 重码字,存在错误平台现象。在Turbo码的基础上,1994年,Pyndiah等提出了 Turbo乘积码,Turbo乘积码继承了Turbo码的优点。又因为Turbo乘积码的构造 采用了线性分组码,所以译码方法比Turbo码简单。Turbo乘积码近年来开始被 广泛到应用到各种通信场合,大有取代传统的卷积码之势。 本文首先围绕Turbo乘积码的编译码原理,阐述了涉及到的基础知识;又据 Turbo乘积码目前的应用状况,回顾了Turbo码的发展历史;其次,根据Turbo 乘积码的构造原理,探讨了构造的方法,交织类型,子码的选择及子码的性能; 再次,研究了Turbo乘积码的概率译码,基于外信息的迭代算法,研究了Chase 的译码算法;最后通过软件仿真实现了该迭代译码算法,得到的结果达到了通信 接收的要求。 本文还初步的阐述了Turbo乘积码硬件实现系统的设计方案。据实际工作中 碰到的非标准信号,给出了整体模块设计图,及相应模块的功能和模块间连接的 各种参数。并实现了模态下的同步搜索和去除相位模糊功能。最后根据研究中碰 到的各种问题,提出了下一步工作建议和研究方向。 关键词:Turbo乘积码 交织SISO Chase算法外信息 迭代译码FP6A 山东大学硕士学位论文 ABSTRACT During the development of channel encoding,The code Researchers are always finding a kind ofcode which has near-optimum perform加ce,low bit enw rate and low decoding complexity.Berrou advanced Turbo codes in 1993.The Turbo codes have the near-optimum performance and low bit error rate,SO it gets the wide care.But the Turbo cod鼹also have shortcuts such as high decoding complexity,and long decoding latency.On the base ofTurbo codes,1994,Pyndiah suggested the Turbo Product Codes. The Turbo Product Codes remain the merits from Turbo codes,and because of its linear oodes,the decoding structure is simpler than Turbo codes.These years,Tpc has benn used in many communication fields,and will take place ofconvolutional code. Fi斌.The paper surrounds The theory of endoding and decoding,describes related now,ms basis knowledge.and for the application back OVer the past.Scend,from the structure of Tpc,discussed the building Inea璐,interleaving ways,the choice and the performance ofsubcodes.Third,study probability decoding ofTpe,iterative decoding algorithm and Chase algorithm.Finally,The algorithm has been realized,and the result reached our requirement. The paper has been described the realization way of hard ware.For the non-standard signal in the working.Designed the cha/'t of the whole module and the function of the module.Finding s”lcIlI删a肌s code and phase fuzzy have been settled. At the conclusion of this thesis are a summary of the accomplished work and my out/ook ofthe successive research. Key words:TPC,interleaving,SISO,Chase algorithm,eglorflal information, iterative decoding,FPGA 2 山东大学硕士学位论文 第一章绪论 §1.1引言 20世纪40年代Shannon创立了信息论,为通信系统的发展奠定了坚实的理 论基础。长期以来人们一直在追寻性能上尽可能地接近Shannon理论极限、误码 率低和译码复杂度低的编码方案,以此来改善通信质量。 Shannon理论的核心是:在通信系统中采用适当的编码,能够实现高效率和 高可靠性的信息传输,并据此提出了信源编码定理和信道编码定理。它们在理论 上阐明了通信系统中各种因素的相互关系,为寻找最佳的通信系统提供了重要的 理论依据。 Shannon信源编码定理从概率论形成的语法信息出发,去掉冗余而达到压缩 码率的目的。从无失真信源编码定理出发,1948年Shannon给出了简单的编码方 法,1952年Fano提出费诺码,同年D.A.Huffman构造了一种霍夫曼编码方法, 并证明了它是最佳码。霍夫曼码是有限长度的块码中最好的码。1968年,EElias 发展了Shannon-Fano码,提出了算术编码的初步思路。但对概率特性未知或不确 知的信源进行有效的编码,上述方法很难做到。1977年由齐弗J.Ziv和兰佩尔 A.Lempel提出了LZ算法,它是适合于通用信源编码的方法之一。1978年他们又 提出了改进算法,齐弗也证明此方法可达到信源的熵值。1990年,贝尔T.C.Bell 等在I_Z算法的摹础上又作了一系列的变化和改进,现在LZ码已经广泛应用于文 本数据的压缩算法中。 ’ 信道编码即检纠错编码,在检纠错码发展的历史中,分组码最先出现。Gallager 根据香农理论证明了最优分组码的误码率随着码长N的增加呈指数关系下降。为 达到一定的纠错能力和编码效率,分组码的码长一般都比较大。若采用最大似然 译码,其译码复杂度将随着码长呈指数级增长,从而使译码器的计算量增加到难 以实现的程度。Elias于1954年提出了卷积码的概念,在编码复杂度相同的情况 下,卷积码性能优于分组码。然而与分组码相比,卷积码的数学分析相对困难。 3 山东大学硕士学位论文 Forney设计了级联码,并证明了级联码的译码复杂度并不随码长的增加呈指数增 加,而是随码长以较小的幂次增加,以此降低了译码的复杂度。以Rs码作为外码, BCH或卷积码作为内码的级联码,具有较强的纠突发和随机错误的能力。然而, 在诸多码型中,没有一个码性能达到或接近香农容量极限,长期以来截至速率被 认为是实际传输速率的极限。1993年,C.Berrou等首先提出并行级联码Turbo 码,实现了接近香农极限的数字传输。最初通常采用的是以卷积码为子码的Turbo 码,但主要依赖删除实现码率的调整。大量的有用信息被删除,致使这类码的性 能大大下降。1994年,Pyndiah等提出了基于SISO译码方法,以分组码为子码的 Turbo码。经过大量的实验证明,与以卷积码为子码的Turbo通常需要采用6-8 次迭代相比,分组码具有收敛速度快,仅需4—5次就能达到较好的系统性能。采 用SISO译码方法的Turbo乘积码在译码性能上获得了近似PCCC SISO译码的编码 增益。 在近几年军事通信领域的攻防中,大量侦获使用分组码的Turbo码信号,因 其高性能的差错控制理论及接近Shannon理论极限的性能,在军事通信应用中己 越来越广泛和普及。但军事通信因受天气、地理、保密等因素的影响,致使各国 通信体制繁多,大都不采用民用标准。所以,如何快速的识别和判断其编码结构 和通信体制,在恶劣的通信环境中进行正确的译码,并机动灵活的实时接收和侦 控该类型的信号,对军事通信防御和电子对抗中有着不可低估的意义。 §1.2信道模型和信息度量 1.2.1信道模型 通信的目的是将信源信息通过信道传输到信宿,最简单的模型如图卜1所示, 某时刻信源x发送消息符号集合,中的某一个符号x,输入到信道中,信宿接收的 Y是可能符号集合0中的某一个符号y,x和Y都是随机变量,X,Y是取值。 4 山东大学硕士学位论文 图1-1 通信系统基本模型 1.2.2信息度量 为了衡量通信系统的传输能力,需要对被传输的信息进行定量的测度。哈莱 特首先提出采用消息出现概率的对数作为离散消息的信息度量单位。如:某离散 消息携带的信息量: 7G,)。109厕1=。109 OG,))(1-1) 式中,pb)为该消息发生的概率。对数以2为底时,信息量单位称为比特,对数 以e为底时,信息量单位称为奈特。 数字通信系统中,发送端发出的消息和接收端收到的消息可以分别看成离散 符号集合X和Y,x为发送的符号集合,通常它的概率是已知的,,“)称为先验 概率。接收端根据接收到的消息集合Y中的一个符号儿后,接收者要重新估计发 送端各符号t的出现概率分布,条件概率p(形)又称为后验概率。 定义后验概率和先验概率之比的对数为互信息量,即: 眠执)扎g雩削 mz, 互信息量反映了两个随机事件之问的统计关联程度。在通信系统中其物理意 义也就是接收端所能获取的关于信源的信息。当消息很长时,通常用平均信息量 的概念来计算。如N个符号的离散消息源的平均信息量为 山东大学硕士学位论文 日乜)=一∑pG瑚09 p“) f-I (卜3) 上述平均信息量的计算公式与热力学和统计力学中关于系统熵的公式一样, 因此也把信源输出的消息的平均信息量叫做信源的熵。 存在两个离散信源X和Y时。同时出现的平均信息量称为联合熵。定义联合 熵 日(册’)=—∑∑pk,Y:)logp(xl,M) (1—4) f 』 已知X中出现五条件下Y中出现M的条件平均信息量为 日(致)=一莩PG,乃)t唱<%) c-一s, 日够幺)又称为条件熵。互信息量的统计平均值称为平均互信息量,定义为 ,(丘y)=日(柳一日(z7y)2军莩烈而,乃y“,乃)(1-6) H(x/y1表示接受Y后信道损失的x的信息量。 §1.3信道容量和Shannon信道编码定理 1.3.1信道容量 单位时间内信道上所能传输的最大信息量称为信道容量。实际信道中都存在 干扰,所以输入符号与输出符号之间存在某种随机性,不存在一一对应的确定关 系,而具有一定的统计相关性,这种相关性取决于信道的转移概率,所以离散信 道的特性可以用转移概率来描述。对离散无记忆信道,其容量定义如下 C={肘缸,似,聊·B 小J (卜7) 特别地,二进制对称信道的容量是 c=I-瓯G) (1喝) 式中,占是信道的差错转移概率,既G)表示二进制熵函数。 吃G)=-xiog(x)-(I-x)log(I一0 (1啕) 6 山东大罕坝士罕但论又 带限加性高斯白噪声信道的容量是 c圳d-+争矽吐-+去卜脚(1-10) 式中,S是信号功率,W是信道所能提供的带宽,n。是噪声的功率谱密度。 对于均值为0。噪声方差为N。/2的加性高斯白噪声(AWGN)信道,若令信 道速率R<C,既=鲧为每比特的信号能量,则由公式(卜10)可以得到 参<参礼《t+参·矧(1-11) 令r=R/W是单位普宽的传信率,称为谱比特率,则可由(卜II)式推出下列关系: 墨>型 (卜12) No r 式(卜12)给出了带宽和平均功率都受限的高斯信道传信率的上限。当平均功率受 限而带宽不受限时,可令W_oo,此时有r一0,根据罗比达法则可得 争>型>_ln2¨、 5她、 )“ } (1—13) Ⅳo , 这是在功率受限的A%N信道中实现无误码传输所需要的最低急,称为Sh卸non 限。在数字通信系统中惫是一个非常重要的量,经常用它来衡量信号与噪声之 间的强弱关系。毛是平均发送一个比特信息所花费的能量,No是平均每Hz带宽 上的噪声功率。一般来说只要使E/No足够大,任意小的误码率都是可以达到的. 未编码系统所需要的惫与编码后系统的急之差称为编码增益,正的编码增益意 味着编码后系统为达到相同的误比特率可以节约发射功率。信道编码是降低通信 所需惫的一种有效方法,也是目前所知道的唯一方法。 1 3 2 Shannon信措编码定理 7 山东大学硕士学位论文 对于一个给定的有扰信道,若信道容量为C,只要发送端以低于C的速率R发 送信息,则一定存在一种编码方法,使编码的错误概率P随着码长n的增加,按 指数下降到任意小的值。表示为 p<_Ae-旺似) (卜14) 这里,A是常数,E(R)为正实函数,称为误差指数,它与R,C的关系如图所示 lⅦR, ≥《 /I R 圈1-2 E(R'与R,C的关系图 这就是Shannon编码定理,由式(卜14)和图卜2可以知道信道容量c、码长n 和编码错误功率P之间的关系。为了满足用户对误码率P的要求。可以用下面三 种方法: 1)降低码率R但是对于给定的信源速率,减小码率意味着提高传输速率,从 而增加了对带宽的需求。 2)增加信道容量C,从而使得E(R)增大。增加系统带宽或信噪比,都能增加 信道容量。这些方法可以从根本上改善信道条件,减少误码率,是通信设 计工作者常常采用的传统方法。然而,在给定信道和给定带宽内,增加信 道容量意味着必须增加信号功-率。 3)在信道容量c及信息速率R一定的条件下,增加码长n,可以使错误概率呈 指数下降。但n的增加使可能发送的码字数量(2“)呈指数增加,相应地也 增加了译码设备的复杂度。这种方法就是信道编码定理所指出的减少误码 率的另一方向,它为通信设计工作者提供了一条新的路径和设计自由度。 Shannon定理是一个存在定理,证明时假设码长无限长,随机编码,最大似然译 山东大学硕士学位论文 码,并没有给出构造好码的方法,但是它指明了获得可靠高速通信的方向.以 Shannon定理为基础,产生了信道编码领域,以构造接近信道容一的信道编码,设 计相应的编码方法和译码方法,实现信息的高可靠性和高有效性传输. §1.4信道编译码规则及编码性能测度 1.4.1信道编码原则 根据信道编码定理,如下的通信系统图1-3所示。离散无记忆信源产生某个 信源序列“=O。,“:,...,‰),每一个q(f=l'…,七)都是Q元集合中的符号,共有矿种 消息。编码后得到信道输入序列善=(^毛,..‘),每一个五仍是Q元集合中的符号, 信道输出序列为),=cy.见,..以)。根据接收的Y序列和译码规则,得到信源序列的 估计为v=(vlv2,..以)。 图l-3 一个通信系统框图 码长为n的序列的可能排列共有矿个,而对k维的信息序列共有矿个码字与 之对应.因此编码问题就是定出一种规则,从矿个序列中选取胜矿个与信源序列 对应,每一个序列称为一个码字。被选取的g‘个序列为许用码组,称为一个码集, 其余的矿一q‘个为禁用码组。 码字x中非零码元的个数,称为汉明重量,用W(x)表示。 两个码字x1和x2之间对应位值不同的个数,称为码字之问的汉明距离,表示 为d---w(xb x0。 9 山东大学硕士学位论文 g‘个许用码组中,任意两个码字之间汉明距离的最小值,称为该码组的最小 汉明距离,简称最小距离d。 对信道编码,码率r:生:l092 M和ld、距离d是最重要的参数。码率是衡量 栉 n 码的有效性的基本参数,表示信息位在码字中所占的比重,r越大,信息位所占的 比重越大,码传输信息的有效性越高。最小距离表明码的抗干扰能力,d越大,抗 干扰能力越强。通常情况下,r越大,码的冗余度就越小,抗干扰能力越差。由此 可见,信道编码的码率和抗干扰能力是一对矛盾.因此,编码的原则是:在矿个序 列中挑选的g‘个码字之间,任意两个不同码字之间的最小汉明距离尽量大,即码 字之间越不相似越好。此时,可以使译码的平均错误概率尽量小。综合起来,信 道编码的任务是构造r一定,d尽可能大的码,或d一定,r尽可能高的码。 1.4.2信道译码规则 译码器的基本任务是根据译码规则,由接收序列Y得到与发送信息序列u 最相似的估值序列v。由于x和u是一一对应的,等价于译码器根据Y产生一个x A 的估值序列,当且仅当,=工时,U=V,译码器正确译码。否则,译码器错误译码。 给定接收序列Y,译码的错误概率为p(x≠xlyl,故译码器的平均译码错误概率 为 见=∑p(二≠工1),).p0,)(1-15) y p(y)是接收为Y的概率,与译码方法无关。因此,译码错误概率最小的译码 规则是使 ^ ^ min只=minp(x≠x/y)j maxp(x=x/y) , , (1—16) 因此,如果译码器对输入Y,能在q‘个码字中选择一个使 , p(‘=J力)(i=l,...,g‘)最大的码字x。作为x的估值序列,则可以使译码错误概 率取小,称为最大后验概率译码(MAP)。 10 山东大学硕士学位论文 由Bayes公式 p(薯ty):出掣(1-17) pU' 可知,若发送的每个码字的p“)概率相同,且p(y)与译码无关,故 粉p(而ly净,翳ptylx,) ‘¨8’ DMC信道p(ylxl)=np饥I而),其中,发送码字五=“.,%,...,‰),接收 一 序列y=∽y:,..以)。此时,译码规则称为最大似然译码(MLD),pO I x)称为似然 函数,相应的译码器为最大似然译码器。对DMC信道,当发送端每一个码字等概 分布时,MLD译码器是最佳译码器,使错误概率最小. 1.4.3信道性能测度 一般情况下,编码的通信系统的性能可以用在一定码率下的错误概率和编码 增益表示。 如果以码字为单位统计错误概率,称为块错误率或帧错误率。如果以比特为 单位统计错误概率,称为比特错误率。 如果R为输入信道的平均比特能量,no为信道噪声的单边功率谱密度,将平 均符号能量归一化为1,则接收机的输入信噪比为3NR=乜/‰∞)。对未加信道 编码的系统,在码率r时,达到某个错误概率见需要的信噪比为SNR,。加入信道 编码后,相同条件下需要的信噪比为SNRz。此时,系统的编码增益定义为 SNR:SNR,。 设计通信系统时,为节约系统资源,常常希望可以用尽量小的SNR来获得一 定的见和一定的r,也就使编码增益最大。理论上的最小值称为Shannon极限。 因此,对某种信道编码,可以用其与Shannon极限的距离来衡量其最终的性能。 信道的Shannon极限是由信道容量计算出来的。 除Shannon极限外,MACKAY给出了好码的定义:在给定信道中,采用低于信 道容量的任意非零速率传输,可以获得任意小的错误概率,就称为好码,否则为 山东大学硕士学位论文 坏码。 同时,从实际应用的角度,还要考虑编码和译码的复杂度,希望得到一种低 复杂度的实用的码。采用一种广泛被计算机科学家接受的观点,码长为N的码, 其编码和译码运行时间及其存储需求都可以用N的多项式表示,那么就是一种实 用的码。 综合起来,希望构造的信道编码,性能上尽可能地接近Shannon极限,且复 杂度较低,可以实现,即是实用好码。 §1.5本文的主要工作及内容安排 本文针对工作中遇到的非标准Turbo乘积码信号,进行理论和算法研究,提 出了FPGA设计方案。主要内容涉及Turbo乘积码的理论基础,Turbo乘积码的原 理及译码算法仿真,Turbo乘积码硬件实现,Turbo乘积码下一步工作的建议等方 面,主要的工作和安排如下: 第一章从总体上介绍了信息论、信道编码领域的基本原理和信道编码从理论 到实践的发展。包括信道模型、信息度量、信道容量、Shannon信道编码定理、 信道编译码规则及编码性能测度。 第二章丰要介绍了线性分组码的理论基础,为Turbo乘积码的研究及仿真奠 定了基础。包括信道编码的概念、线性分组码的概念、常见的线性分组码及线性 分组码的译码。 第三章主要介绍了Turbo乘积码的历史发展和现状、Turbo乘积码构造原理、 Turbo乘积码的交织种类、Chase Turbo乘积码的迭代译码算法原理和基于Chase II的迭代译码算法的仿真。 第四章主要描述了,算法实现的硬件环境,FPGA设计流程和具体的Turbo乘 积码的FPGA的实现。 第五章总结全文,并提出了对一些非标准Turbo乘积码研究建议和一些值得 探讨的问题。 山东大学硕士学位论文 第二章线性分组码 §2.1信道编码的概念 2.1.1信道编码的概念 信道编码的基本概念是:在发送端,信道编码器按照一定的约束关系给被传 输的信息序列附加上一些监督码元,这些多余码元与信息码元构成编码序列一同 被发往信道。在接收端信道译码器按照即定的规则对所接收到的码序列中的监督 码元和信息码元问的关系进行检验,一旦传输过程中发生差错,则两者问的关系 就会受到破坏,从而可以发现错误,乃至纠正错误。信道编码就是研究各种编译 码算法的性能和应用的~门科学。 2.1.2信道编码的一般分类 差错控制系统中使用的信道编码可以有多种。图2-1为信道编码技术的简单 分类。 图2-1信道编码的分类 按照信息码元和附加的监督码元之间的检验关系可以分为线性码和非线性 码。若信息码元与监督码元之间的关系为线性关系,即满足一组线性方程式,则 山东大学硕士学位论文 称为线性码。反之,若两者不存在线性关系,则称为非线性码。 按照信息码元和监督码元之间的约束方式不同可以分为分组码和卷积码。在 分组码中,编码后的码元序列每刀位分为一组,其中k个是信息码元,,个是附 加的监督码元,F矿七,监督码元仅与本码组的信息码元有关,而与其他码组的信 息码元无关:而卷积码的监督码元不但与本组信息码元有关,与前面码组的信息 码元也有约束关系。 按照信息码元在编码后是否保持原来的形式不变,可划分为系统码和非系统 码。在差错控制编码中,通常信息码元与监督码元在分组内有确定的位置。在系 统码中,编码后的信息码元保持原样不变,而非系统码中的信息码元则改变了原 有的信号形式。 按照纠正错误的类型不同,可以分为纠正随机错误码和纠正突发错误码。前 者主要用于发生零星独立错误的信道,而后者则用于对付以突发错误为主的信道。 §2.2线性分组码的概念 信道编码时,在长度为k的信息序列后面,以一定的规则增加长度为n—k位 的检验码元,组成长度为n的码字。如果检验码元的产生仅仅与本组的K个信息 位有关,与其他组的信息位无关,译码时也仅仅处用本组的码元,这种码称为分 组码,用(n,k)表示分组码集合。如果本组的检验码元的产生不仅与本组的信息 位有关,而且与此刻之前输入编码器的信息位有关,译码时同样也要利用前面码 组的有关信息,这种码称为卷积码,常用(n,k,m)表示卷积码的集合,m为约 束长度。 分组码是建立在码的代数结构基础上的,有关的代数基础可参考文献。 2.2.1线性分组码的定义 定义:码长为n,有寸个码了的分组码c,当且仅当其q‘个码字构成域GF(q) 上所有n维向量空间n的一个k维子空间时,称该分组码为[n,k]。线性分组码, 且称k为C的维数。 线性分组码编码的实质就是在n维向量空间中找出满足一定规则的,由q。个 山东大学硕士学位论文 向量组成的k维向量子空间。或者说,在给定的条件下(如最小距离和码率),由 已知的k个信息元求出m=n-k个检验码元,然后将信息元与检验元合在一起构成 一个码子。 2.2.2分组码的生成和校验矩阵 线性分组码可由其检验矩阵或生成矩阵唯一确定。 2.2.2.1生成矩阵 由于(n,k)。线性分组码的q‘个码字组成了n维向量空间的一个k维子空间, 因此,这些码字可以由k个独立向量所生成的基生成。设此k个向量生成矩 阵形式为: …gJk gl“l…91月 …gk gI“I…92一 G= (2.1) gkJ gk2…gn gI。tH…gh 任何码字都可以由这组基的线性组合生成。如果信息序列 Ⅳ=h,“:,...,‰】∈露是由k个信息元组成的信息组,则其编码后的码字为: l蜀 …岛. C=uG:kⅣ2…‰1 921I如gn…鼠 (2-2) Igk,gk2…g“ 就是说,每给一个信息组,通过(2-2)式可以求得相应的码字,故称k个独立的 基所构成的k*n维的矩阵G为(n,k)码的生成矩阵。 定义设C是[n,k]。码,其牛成矩阵是一个空间n上的k*n的矩阵,使得 c={uatu∈片j(2-3) 生成矩阵的含义是: (1)生成矩阵是一个k行n列的矩阵。 (2)生成矩阵的k行就是k个线性无关的码字,它们的线性组合生成全部码字。 因此,G确定。也就解决了编码问题。 (3)生成矩阵G可以有多种形式,但都生成同一个(n,k)。码。 山东大学硕士学位论文 (4)由于G中的每一行都是码字,故有GH’=O或HG7=O,即检验矩阵H和 生成矩阵G彼此正交。 2.2.2.2校验矩阵 任一(n,k)线性分组码,c=b c2…q】是一个码字,满足如下线 性方程组 简写为 啊。 ^: 如, ||122 kl J|I。2 k =0 k—k }=。oo.且 q乞~% 胁7=0 (2-4) (2-5) 或 cH7=0 (2-6) 其中矩阵H称为线性分组码的检验矩阵。 定义设C g En,k]。码,其检验矩阵是一个空间域刀上的(n—k)}n的矩阵, 使得 c=t∈嚣:Hc’=o} (2—7) 其意义为: (1)H矩阵的每一行代表一个线性方程组的系数,表示求一个检验元的线性方 程。 (2)H矩阵必须有M行,且各行之间必须线性无关。 (3)若向量c的各个元素是由H所确定的M个线性方程组的解,则c是一个码 字。反之,若C是一个码字,则一定满足由H所确定的n1个线性方程组。 因此,只要H确定,便可由信息元求出检验元,完成编码过程。 2.2.3码重和距离 16 山东大学硕士学位论文 定义设x,ye刀是空间中的元素,则x和Y之间的汉明距离定义为 d(五力:=p鼍f:毛≠乃}(2-8) 而x的汉明重量为 ,矿(曲=p《f:‘≠o}=d仁o) (2—9) 符号舻表示计算个数或数目. 正是定义了汉明距离,使得空间刀成为一个测度空间,测度满足 (1)d(x,y120,当切仅当x=y时成立。 (2)d∽,)=d(弘力 (3)d“z)5d阮力+d0,,z),h,YE曰 定义设ccC是一个码,其最小距离为 d=dn(c)=man{a(x,y):x,yec,J≠_),} 如果[n,k]。码的最小距离为d,可将其写为[n,k,d]。 (2一lo) 对[n,k】。线性分组码C,每一个码字都是子空间中的向量。如果cI∈C、岛eC, 则(q+c2)eC(q进制加法),在此q、c2的汉明距离等于(q+c2)的重量。故线 性分组码C的最小距离等于码中非零码字的最小重量,即 dm(c)=埘m(c)=rain{wt c):cecc≠o) (2一11) 因此,码的最小距离可以通过计算非零码字的最小重量来获得。 两个码字之间的距离表示它们的差别和相似程度。距离越大,则从一个码字 变成另一个码字的可能性越小。最小距离与纠错能力直接相关。 定理码C纠正t个错误的充要条件是其最小距离d≥2t+l。 定理码c的最小距离为D,是其检验矩阵H中线性相关列的最小数目,即H 的任何d-1列组成的子集都是线性无关的。 上述定理说明,检验矩阵的结构与码的纠错能力具有内在联系,如果矩阵H 的任意2t及更少的列组成的子集都是线性无关的,则这个码可以纠正t个错误。 17 山东大学硕士学位论文 同时,也可以利用检验矩阵来计算码的最小距离。 2.2.4分组码的最小距离界 码的纠错能力与该码的最小距离直接相关,而线性分组码编码的任务是在给 定码率k/n时找到具有最大最小距离的码。对短码,可以用计算机穷举得到。但 一般情况下,希望得到最小距离的上界和下界,这意味着可以在没有构造码的前 提下来分析码的纠错能力。同时,以最小距离为基础,可以来评价某种码与理论 极限的接近程度,以及来判断具有某种参数的码是否存在等等。 2.2.4.1 汉明(Hamming)界 考虑GF(q)域上的(n,k)码C,共有qk个码字,将每个码字看作是GF(q)域上 的n维空间中的点,以每个码字为球心,与这个码了汉明距离为t的码字在半径 为t的球上。这个球就是这个码字最小距离译码的区域。在各个球不相交的情况 下,码字可以纠正t个错误,t与最小距离的关系为f=[血F],求出最大的t, 即可得到最大的dmin。 以某个码字为球心的球,半径为t,包含了与这个码字汉明距离为0,1,…, t的所有向量,这些向量的个数称为n维体积,表示为 弘妻(弦ty ∽埘 如果GF(q)域上rl维空问的体积大于等于这个qk个码字的总体积,则所有的 球都不会相交。因此,上面就是码字可以纠正t个错误的条件 g‘嘉(;]ca一-y≤g“ cz一·。, 或 变成对数形式为 ∥≥杰f讹一ly i砷\J) (2-14) 山东大学硕士学位论文 一一七≥t。s。(妻(;)cg一-y] (2-is) 利用上式,在给定n,k时,可得到t的最大值,从而得到最小距离的最大值。 称为汉明球包界。对所有的分组码都适用。、 2.2.4.2 辛格尔顿(Sinfleton)界 线性分组码的最小距离的上界很容易求出来,但是一般是达不到的。一个线性 码的最小距离就是非零码字的最小汉明重量。对一个非零码字,k个信息位中至 少有一位是非零的,而n-k个检验位的最大重量就是n—k,因此码字的最小距离 不能超过n_k+1,即d二<n-k+l。达到这个上界的码称为MAXIMUN DISTANCE SE队llABLE(MSD)码,常用的一种MSD码是REED-SOLOMON码。 根据SINGLETON界,可以得到 翌女量≤l一生+! 订 再 n (2—16) 对码长较长的码,必须要满足‰,月小于等于卜k/n=l—r。同时,由于 dm 22H.1则f≤竺j≥,也就是要纠正一个错误至少需要两个检验符号。 二 2.2.4.3普罗特金(Plotkin)界 GF(q)域上的(n,k)线性码C,所有qk个码字的平均重量为 %=等擎 ∞∽ 而最小距离不能超过平均码字重量,故有 ‰≤等竿 (2—18) 这是用n,k,q得到的最小距离的另一种上界,上式变换为 争以 s掣q挲t一1 ㈨,, 、 ’ 鱼二照与码率无关,故是一个比较松的界,特别是高码率,q较大时。 19 山东大学硕士学位论文 §2.3常见的线性分组码 2.3.1汉明码 汉明码是一种线性分组码。线性分组码是指将信息序列划分为长度为k的序 列段,在每一段后面附加r位的监督码,且监督码和信息码之间构成线性关系, 即它们之间可由线性方程组来联系。这样构成的抗干扰码称为线性分组码。 设码长为n,信息位长度为k,监督位长度为r=n—k。如果需要纠正一位出错, 因为长度为n的序列上每一位都可能出错,一共有n种情况,另外还有不出错的 情况,所以我们必须用长度为r的监督码表示出n+1种情况。而长度为r的监督 码一共可以表示27种情况。因此 27≥一+l, 即r2log(n+1) 我们以一个例子来说明汉明码。假设k=4,需要纠正一位错误,则 27≥n+l=k+,+l=4+r+l ,解得 r 2 3。我们取r=3,则码长为3+4=7。 用a6,a5….ao表示这7个码元。用S1,S2,S3表示三个监关系式中的校正子。我 们作如下规定(这个规定是任意的): S1 S2 S3 O O 0 l 1 O O l 1 O l 1 l 1 O O 错码的位置 aO al a2 a3 a4 a3 a6 无错 按照表中的规定可知,仅当一个错码位置在a2,a4,a5或a6时校正子Sl 山东大学硕士学位论文 为1,否则S1为0。这就意味着a2,a4,a5。a6四个码元构成偶校验关系: S1 = a6申a50a40a2 (1)式 同理,可以得到: S2 = a60a5审a30al (2)式 S1 = a60a40a30aO (3)式 在发送信号时,信息位a6,a5,a4,a3的值取决于输入信号,是随机的.监督 为a2,al,a0应该根据信息位的取值按照监督关系决定,即监督位的取值应该使上 述(1)(2)(3)式中的sl,S2,S3为0,这表示初始情况下没有错码.即 a60a50a4由a2 =0 a60a50a30al =0 a60a40a30aO =0 由上式进行移项运算,得到: a2 = a60a5ea4 al = a6西a50a3 aO = a60a4毒a3 已知信息位后,根据上式即可计算出a2,a1,a0三个监督位的值。 接收端受到每个码组后,先按照(1)’(3)式计算出s1,s2,S3,然后查表可知 错码情况。 例如,若接收到的码字为0000011,按照(1)’(3)计算得到: S1 =0, S2 = 1, S3 = 1 查表可得在a3位有一个错码。 2.3.2循环码 循环码是线性分组码的一个重要子集,是目前研究得最成熟的一类码。它有 许多特殊的代数性质,这些性质有助于按所要求的纠错能力系统地构造这类码, 且易于实现;同时循环码的性能也较好,具有较强的检错和纠错能力。 21 2.3.2.1循环码的特点 山东大学硕士学位论文 循环码的特点就是码字的循环特性,所谓循环特性是指:循环码中任一许用 码组经过循环移位后,所得到的码组仍然是许用码组。若(口“吒刁…4I盘0) 为一循环码组,则(气句气寸…40 4.-1)、(a,4 a,40.a-I%q)、……还 是许用码组。也就是说,不论是左移还是右移,也不论移多少位,仍然是许用的 循环码组。表2—2给出了一种(7,3)循环码的全部码字。由此表可以直观地看 出这种码的循环特性。例如,表中的第2码字向右移一位,即得到第5码字:第 6码字组向右移一位,即得到第3码字。 为了利用代数理论研究循环码,可以将码组用代数多项是来表示,这个多项 式被称为码多项式,对于许用循环码乒(4“气一2…口1 40),可以将它的码多 项式表示为: 4《xj=4“,‘.[.att_2Xtt'2+…+4lx+ao (2—20) 对于二进制码组,多项式的每个系数不是0就是1,石仅是码元 位置的标志。因此,这里并不关心J的取值。而表2—2中的任一码组可以表示为: 以)=%≯+毋,+铂一+匈≯+d2≯+alx+aa (2—21) 表2-2一种(7,3)循环码的全部码字 序号 码字 信息位 监督位 序号 码字 信息位 监督位 a6 a5 a4 1 000 2 0O l 3 O 1O 4 O11 a3 a2 al aO OO OO 0 l ll 1 1 l0 lOO l a6 a5 a4 5 l OO 6 1 01 7 1 10 8 l ll a3 a2 al aO l0 l1 1 lO O O l01 O O 1O 山东大学硕士学位论文 例如,表中的第7码字可以表示为: 4仁)=1.≯+1.,+o.,+o.尹+1.p+o.X+I ;≯+≯+≯+1 (2—22) 在整数运算中,有模疗运算。例如,在模2运算中,有I+I=2;0(模2), I+2=3iI(模2),2X3=6—0(模2)等。因此,若一个整数m可以表示为: 詈。口+詈,<一揪数 疗 刀 (【2Z-—2Z33)J 则在模疗运算下,有用sp(模疗),也就是说,在模力运算下,一整数凹等于 其被灯除所得的余数。 在码多项式运算中也有类似的按模运算法则。若一任意多项式以曲被一个 刀次多项式似力除,得到商式口(匐和一个次数小于由的余式斤(力,也就是: 矧嘶j+锱 ∽。。) 则可以写为:尺力s曰(曲(模Ⅳ(神)。 这时,码多项式系数仍按模2运算,即只取值0和1,假设:计算x4+卫2+I 除以船+1的值可得: 一+p+1 p+x+1 ——一’+广1 —一=X+——,百+—1一 (2-25) 注意,在上述运算中,由于是模2运算,因此,加法和减法是等价的,在式 子中通常用加法运算符,具体模2运算的规则定义如下: 障2加|o+0=0Io+l=l l+0=1 1+1=0 陲2剥o×o=o 0×1=0 l×0=0 l×l=l 这样式(2—26)也可以表示为: x4+≯+1兰x2+x+1恒p+i) (2-26) 在循环码中,若彳(茹是一个长为n的许用码组,则一·4扛)在按模妒+1运算 下,亦是一个许用码组,也就是假如:一.4x)兰∥仁)(模矿+1),可以证明』1xj 亦是~个许用码组,并且,小x)正是彳(曲代表的码组向左循环移位f次的结果。 山东大学硕士学位论文 例如,由式(2—23)表示的循环码,其码长n----7,现给定1=3,则: 妒.局仁):x,.p+,+p+1):B9+xs+,+尹) :p+夕+p+x)嘛7+1) (2-27) 其对应的码组为0101110,它正是表2—2中第3码字。 通过上述分析和演算可以得到了一个重要的结论:一个长度为/7的循环码, 它必为按模(矿+1)运算的一个余式。 2.3.2.2循环码的生成多项式和生成矩阵 (全0码字除外)生成多项式,用g(力表示。可以证明生成多项式g(曲具有 以下特性: (1)F(曲是一个常数项为1的r=n—k次多项式; (2)占(力是)c}l+1的一个因式: (3)该循环码中其它码多项式都是F(曲的倍式。 为了保证构成的生成矩阵占的各行线性不相关,通常用g(曲来构造生成矩阵, 这时,生成矩阵G(X)如下: Xtt-I.g《石l 一.g(xt GfzI- z‘g{石 glz (2—28) 其epglzb z7+4一,1+…+4'x+l,因此,一旦牛成多项式g(曲确定以 后,该循环码的生成矩阵就可以确定,进而该循环码的所有码字就可以确定。显 然,式(2—29)不符合G2阪Q J形式,所以此生成矩阵不是典型形式,不过, 可以通过简单的代数变换将它变成典型矩阵。 现在以表2—2的(7,3)循环码为例,来构造它的生成矩阵和生成多项式, 这个循环码主要参数为,n----7,/声--3,_i-=--4。从表中可以看到,其生成多项式可 24 山东大学硕士学位论文 以用第1码字构造: 矧 吕(习=^B)=一+,+x+1 ≯g㈨ 喇= 醒B)|_ .暑B列 (2—29) 一 10 G州10 i;]1 G-l l l0 1 0l O 1 0 1 1 1l 协,n。。n“, 首先,生成多项式g(∞是矿+1的一个因式,其次g(神是一个,次因式。因 此,就可以先对,+避行因式分解,找到它的,次因式。下面仍以(7,3)循环 ,+1:仁+1)p+尹+1)6c3+x+1) (2-32) B+1).仁3+妒+1):一+尹+x+1 (2-33) 0+1)S3+x+1):一+≯+≯+1 (2也) 山东大学硕士学位论文 由于(刀J膏)循环码中F(曲是矿+1的因式,因此可令: 荆=两xn+l=≯+概一1x¨+..-+魄x+1 (2—35) 这里h(x)称为监督多项式。与式(8-29)所表示的口(曲相对应,监督矩阵表 示为: x”b1.^’仁) ,廿~.矗’b) 日仁)= x.h+扛) 矿仁) (2—36) 其中矿扛)是^&’逆多项式。 矗。仁)=≯+^≯一1+吃x‘一2+…+圾一lx+l (2—37) 对于表8—7中的(7,3)循环码,g{x)=x4+p+一+1,则: 矗∽=豁=≯。+,j硝刁=,…,(2-。。) ≯+≯+p] 日&)= t+●≯l ,+r+x l p+x+1 J 1 0 1 1 0 0 0] I 0 1 0 1 1 0 0 l j日: oo1 o1 l o 1J o o o 1 o 1 (2—39) 2.3.3 BCH码和RS码 2.3.3.1 BCH码 GF(口)域循环码牛成多项式F(力,若含有2}个连续幂次的根a“,a、“…争研“ 由F(曲生成的(马曲循环码称为g进制BCH码。连续幂次起始值加的选取并无多 大实际意义,通常固定取加=l。 若q=2,称为二进制(二元)BCtt码。 若根a是本原元ft.,称该码为本原BCH码,其码长n=qm--1。若根a是非本原 山东大学硕士学位论文 元口,称该码为非本原BcH码,其码长打是qm-1的因子,满足刀I(qm-1)。 BCH码限定理:若BCH码生成多项式F(力中含有2 t个连续幂次的根,则该码 的最小距离控2t+l 证明:...BCH码多项式“力=厨(曲F(力 ...F(曲的2t个连续幂次根a、…、a2t也是“力的根 设C(力=cO+clx+c2死+…+Ic曰一1 J打一1 以根石=旺代入, 得cO+cla+c2 o【2+…+cn-1 a|『r1:0 以j=a2代入, i 得cO+cla2+c2(a2)2+...+c,rl(a2)n-l=0 以J=e2f代入, 得c0+clo.2t+c2(a2幻2+…+c扩1(a2幻矿l=0 将上面2£个方程写作矩阵形式,得 CA7=0 (2—40) 其中 l 4 l口2 A= 1口 … 口“-1 1 42…(口4。1)2 (2-41) l 42‘ 品一 1口“…(Qn-I)2‘ 可见,A是范得蒙(Vander∞onde)矩阵。已有数学证明:范得蒙矩阵一定是满秩矩 阵,即矩阵A的秩是2t或者说有2t列线性无关。码的最小距离砌等于校验矩阵 中线性无关的列数加1,因此BCH码的 口妇=2t+1 (2—42) 本原BCH码构造法 ①由关系式rF2m-1算出面找到一个m次本原多项式尸(力,产生一个GF(2痂扩 域。 ②在GF(2m)上找一个本原元a,分别计算2t个连续幂次根a、a2、…、a2t所 对应的GF(2)域上的最小多项式m(∞、庇(曲…庇£(曲。 ③计算这些最小多项式的最小公倍式,得到生成多项式g(力 占(力=LCM[ml(力比(力…应f(神] (2-43) 山东大学硕士学位论文 ④由关系式C(x)=lIl(x)g(x)求BCH码字,这步就是BCH编码。 对于二元BCH码,无需列出全部2£个连续幂次的根,而只要列出其中一半(奇数 幂次的根)就可以了。这是因为任何一个偶数拍可写成一个小于它的奇数如与 2的』次幂的乘积 抬=i伊21。f从ie (2-44) 比如2=1×21,4=1×22,10=5×21,12=3×22… 。因此任何一个偶次幂根都 是奇次幂根的共轭元 口‘一=a io 21=(口io)21 (2—45) 它们对应同一个最小多项式,于是在计算最小公倍式时将不起作用。当码长/7 确定后,BCH码纠错能力f的选择并不是任意的,而要受到一定限制。对于口元 BCH码,2f个根对应2£个最小多项式,每个最小多项式的次数不会超过西于是 2 t个最小多项式的最小公倍式g(曲的次数 deg[g(神]=(n-k)≤2加 对于二元BCH码,f个根对应t个最小多项式,因此 (2—46) deg[g(力]=白—∞≤加 (2—47) p一1)一共有17个根,连续幂次根不能超过根的总数: 2t s 17 如果要求的码长月既不是24一l又不是2“一1的因子,那么就不能直接得到BCH 码,值可以通过码的扩展和缩短间接地得到。 以宅矽 扩展 (肿l,七毋1)扩展BCH码 (23,12,7)扩展 (24,12,8)扩展戈莱码(纠3检4) 扩展戈莱码在实践中用得很多,比如ITU—T H.324(PSTN和无线信道上低比特率的 多媒体通信协议L采用的就是(24,12)扩展Golay码。相反,我们也可以从 (见丘功BCH码出发,构成(疗一‘膏‘口》缩短BCH码。缩短BCH码的编,译码电路 只是在原BCH码电路基础上稍作修改即可。 2.3.3.2 RS码(Reed-Solomon code)里德一索洛蒙码 RS码是BCH码最重要的一个子类。可视为BcH码的特例,是肝1,加=1时的口 元本原BCH码。由于最小多项式的次数不会超过皿当m=l时,2£个连续幂次的 山东大学硕士学位论文 根(r0【)(rcl2)…(r酽’既是q元扩域GV(q1)上的根多项式,又是q元基域 GF(q)上的最小多项式。这种性质给多元BCH码的设计带来了很多的方便,因为我 们在前面已经看到,由扩域f次幂根ai求基域对应的最小多项式是十分麻烦的 事,而RS码的一次根式(ra)就是最小多项式,无需另外再去计算。 本原RS码具有如下参数: 码长:rFq-1 校验位:n-It=-2 t 最小距离:dmirF2 t+l 生成多项式:F(力:(r伍)(r∥)…(r费’ =aH而t手岛+l确+…+函z诋 (2-48) 式中,F(曲的各次系数出取自扩域GF(q1) a,∈{0,1,a,嘞,…,CL,r'z) (仁O…n-k) 由以上参数可见 L^nin=2t+l=n-k+l (2—49) 因此,RS码也是MDC码(极大最小距离) 注意:GF(q)和GF(q1)含义不同GF(q)是数域, q必须是素数。GF(q1)是多项式 域,q不一定是素数,工程上,q通常取为2的幂次。 一般来说,一个纠随机差错能力为t的Rs码,其二进衍生码可以纠正小于等 于t个随机差错,或者纠正单个长度为b的突发差错, 6≤(t-1)m+l (2—50) 以及其它大量错误图样。可见,二进衍生码特别适用于纠突发差错,这就是它在 无线通信中被广泛采用的原因 §2.4线性分组码的译码 只要找到了H矩阵或G矩阵,便解决了编码问题,编码后的码字,由于信道 干扰可能出错,接收端要检错和纠错,就是译码问题。 如果发送码字为C,通过信道接收序列为R,线性分组码的最大似然译码是可 实现的,复杂度随码长指数增长。常用的是一种代数译码,称为伴随式译码。 山东大学硕士学位论文 若发送的码字为c=【cl C2…q】,接收量为,=k屹…,=l】。最大似然 扎译码是在码集合C中找到使似然函数p(r/c;)取大的Ct作为发送码字c的估计。 对离散无记忆信道,似然函数表示为乘积的形式 p婶|c)=l-Ip(rjlcv)(2-20) Jtl 此时可采用对数似然准则,最佳译码为 ;=arg c』max∑logp(rj/cu) (2-20 j=l 一般的甩译码需要qk个求和运算,同时需要找到具有取最大对数似然函数的 码,复杂度是码长的指数形式,不是多项式形式,是不可实现的。但是,中等码 长或有限码长的译码可以采用一些次最佳的算法来逼近札译码。 另外,利用码字之间的汉明距离也可以进行译码,即选择与发送码字c距离 d(r。c。)最小的C。,作为c的估计,称为最小汉明距离译码。可以采用计算机穷举 方法找到最小距离的码字。但是常采用的是伴随式译码。 接收向量可表示为r=c+e,e是上GF(q)的量。求和也是GF(q)上的和,称为码 字c的错误图样,描述了码字在传输过程中发生错误的情况。当e=O时,没有错 误,由于d(r,c,)=wt(r,q)=wt(e),d(r,cf)最小意味着e的重量取最小。在所有 的错误图样中找到最小重量的一个,从r中减去e,即可得到最小距离译码。将 接收量进行检验,有埘7=如+P)Ⅳ7=eli7。由此,定义S=rH7=掰7为接收量 r的伴随式或校正子,含有接收量的全部信息。显然,若e=O,S=O,没有错误, r=C,若e≠0,则S≠0,发牛错误,如能从S得到e,则由C=r—e即可恢复发送 的码字。可见,s仅与e有关,反映了信道干扰的情况,与发送的码字无关。 由上述讨论可知,译码的步骤为 (1)计算接收量的伴随式 (2)找到对应的错误图样 (3)通过C=r-e实现译码 值得注意的是,若错误图样e本身是一个码字时,S=O,此时的错误不能发现, 山东大学硕士学位论文 也无法纠正,为不可检测错误模式。 另外,处用陪集首与伴随式的对应关系,可以通过查表法进行译码。 §2.5本章小结 线性分组码是一类重要且应用最广泛的分组码,他的信息码元和校验码元是 用线性方程联系起来的,可有校验矩阵或生成矩阵唯一的确定,且校验矩阵和生 成矩阵满足正交关系。 码重和距离是分组码的重要参数,最小距离与码的纠错能力直接相关,利用 校验矩阵的线性无关的列数可以计算码的最小距离。最小距离界计算是分组码的 一种理论分析方法,同时,以最小距离为基准,可以用来评价某种码与理论极限 的接近程度,以及判断具有某种参数的码是否存在.常用的有汉明(Hamming)界, 辛格尔顿(Sinfleton)界和普罗特金(Plotkin)界,利用这些最小距离界,来界定 码长、信息码元长度、码元的维数和最小距离的关系。 常见的线性分组码有汉明码和循环码,循环码包括常见的BCH码和Rs码,通 过介绍码的特点和原理,为下一步Turbo乘积码的研究打下基础。 最大似然译码和最小汉明距离译码都是最佳译码的方法,但随码长的增加实 现会更加困难。最常用的线性分组码的译码是伴随式译码。 山东大学硕士学位论文 第三章Turbo乘积码的原理及其算法仿真 §3.I Turbo乘积码 3.1.1 Turbo码 1993年C.Berrou等最先提出了Turbo码,它是并行级联带反馈的系统卷积 码。由于Turbo码在接近香农极限的低信噪比下仍能够获得较低的误码率,所以 引起了编码界广泛的兴趣,并成为编码研究领域最新的发展方向之一。Turbo码 是在汲取传统级联码优点基础上的一种改进,它的编码器采用并行级联结构,它 通常由两个或两个以上递归系统卷积编码器组成,在某时刻进入的信息序列直接 送往信道的编码器,同时,将它依次通过交织的序列分别送往其他予编码器,各 子编码器所产生的校验位经删截矩阵的删取后送往信道.通过改变删截矩阵即可 得到不同码率的Turbo码。交织是Turbo编码器中的一个独特之处:输入的信息序 列首先被送入第一个编码器进行编码,同样的序列被打乱后送入第二个编码器编 码,交织器的作用是改善码距分布。这是Turbo码在编码方面性能优异的原因, 因为采用交织器后,第二个编码器产生的校验位并不是第一个编码器校验位的简 单重复,它和第一个编码器的校验位和系统位共同构成一个新编码。 d到RSC一2卜蟹 .I RSC…卜_蟹 多 路 复 A 口 图3-1 Turbo编码 Turbo码的译码主要采用迭代译码。译码器的关键是发送端的成员编码器对 应的成员译码器,译码器首先把对应于成员编码器1的系统位和校验位的软判决 信息送给译码器1进行译码:译码器1输出的软信息中包含内信息与外信息两部 山东大学硕士学位论文 分,外部信息是译码器2的先验信息,但是要通过去交织处理后才能与系统位相 对应,然后译码器2开始译码,输出的软信息中可分离出译码器1所需的先验信 息,各轮译码中的信息连接就是通过外部信息得到的。译码过程反复进行多次, 最后通过对软信息进行硬判决得到最终译码输出。 Y,, Y5 yP2 图3-2 Turbo译码器 最早提出Turbo码时,采用的是基于Bahl等提出的MAP译码算法.MAP算法 是一种基于码元的最大后验概率译码算法,对于线性块编码和卷积码,它能使比 特错误率最小。但MAP算法始终存在几个难以克服的缺点,需要较大的运算复杂 度和大的存储空间。相比之下,在卷积码译码中,维特比算法(VA)具有计算简单、 存储量小、性能良好等优点,得到了广泛的应用。维特比译码算法输出的是使后 验似然概率最大的比特序列,而不是使每个比特具有最大后验似然比。为将vA 应用于Turbo码中,Hageaue等对维特比译码作了改进,提出软判决输出维特比 译码(SOVA)算法,使其可以逐比特输出与MAP算法类似的软判决信息。SOVA算法 保持了vA算法计算简单、存储量小、易于硬件实现的优点。 3.1.2 Turbo乘积码的提出和发展 Berrou等人提出的Turbo码在接近香农极限的低信噪比下,能够获得较低的 误码率,从而使Turbo码的研究成为了编码界的一个研究热点,并开始在各种通 信系统中实现应用。然而随着新一代移动通信系统研究的开展,人们对通信的传 输速率、可靠性、频带利用率的需求越来越高。可以肯定新一代移动通信系统的 峰值传输速率将大大超过第三代移动通信系统,传统的Turbo卷积码译码器由于 其译码复杂度高、译码延时较大,将很难适应新~代移动通信系统的要求。乘积 码是1954年由Elias提出来的。但当时的硬件水平限制了它的应用。1993年, C.Berrou提出的并行级联卷积码,实现了接近香农极限的数字传输。最初通常采 山东大学硕士学位论文 用的是以卷积码为子码的码,但主要依赖删除实现码率的调整。大量的有用信息 被删除,致使这类码的性能会大大下降。1994年,Pyndiah等提出了基于SISO 译码方法以分组码为子码的码,这就是Trubo乘积码。经过大量的实验证明,与 卷积码通常需要采用6-8次迭代相比,分组码收敛速度快,仅需4—5次就能达到 较好的系统性能。采用SISO译码方法的分组码在译码性能上获得了近似卷积码 SISO译码的编码增益.与卷积Turbo码技术(PCCC)相比,Turbo乘积码可以在 较高的编码效率(比如R>2/3)情况下,仍然保持相当强的纠错能力,有利于提 高频谱利用率,可提供更好的抗衰落性能,并能较好地改善BEli-_SNR性能曲线 的误码平层效应(当误码率下降到一定程度后,随着信噪比的提高,误码率改善 比较平缓)。分组turbo码在信道条件较差的无线通信应用有着很大应用潜力。 随着Turbo乘积码的提出,有关Turbo乘积码编译码方法的专利和文献不断 涌现,其中Thesling设计了基于伪最大似然的乘积码译码算法。ShuLin和 Fossorier设计了基于排序统计的译码方法。Turbo乘积码的译码较之Turbo卷积 码相对简单,但是迭代译码的结构决定了Turbo乘积码的译码时问是制约通信速 率的瓶颈。最初的Turbo乘积码译码器的行译码与列译码是采用串联方式,整个 乘积码在进行下半个迭代译码之前需要对行或列进行N次软译码,其中N为码矩 阵的行或列数。这种译码结构所需的硬件少,复杂度低,但Turbo乘积码的速度 严重受限于译码速度。为了缩短Turbo乘积码的译码延迟,近年来通信工作者们 进行了相关研究。 并行操作是提高译码速度的有效方法。2002年Cenk Argon与Steven WMclaughlin提出了一种并行译码结构,在一个并行形式中同时执行行和列译码, 这样就使操作速度提高一倍。然而它要求多出一半的存储器,且不能获得更高的 速度。为了适应更高数据速率的应用,还必须降低硬件复杂度中等消耗的译码反 应时间。Chase算法的译码器即可用于行译码又可用与列译码,节约了译码器一 半的数目。 §3.2 Turbo乘积码的构造原理 3.2.1 Turbo乘积码子码的选择 山东大学硕士学位论文 Trubo乘积码为块状码, 一般由两个或两个以上的分组码经编码后成为二 维、三维或多维的编码块。这里的分组码在乘积码中常称为子码,这些子码可以 相同也可以不同,可以是BCH码,单奇偶校验码、扩展Haming码等,并可对乘 积码的编码块进行截短,从而构成满足通信系统要求的码率。目前,全球已有A}IA、 Xilinx、ECC等数家公司生产出了针对Turbo乘积码的专用芯片并投入应用。目 前卫星通信中,以奇偶扩展Hamming码作为子码的居多。 3.2.2 Turbo乘积码编码结构 本节以二维乘积码为例来说明Turbo乘积码的构造方法:有两个线性分组 子码cJ“,kl,d。。)和c2G:,如,d。:)构成,可用clo c2表示·其中码为码子长度, 砖为信息为长度,d。为最小汉明距离。如图所示,乘积码编码时: l、将待编码的信息位按行读入顺序,置于数组的前kl行和前如列。 2、对毛行信息位进行c2瓴,岛,d。:)编码· 3、对岛列信息位进行clO。,kl,J。。)编码。 然后数据流在按列顺序读出,这样便编码完毕。 I— 一 k. information check iT】l引I|lf0 chcck chick 图3-3二维编码图 所构成的乘积码的主要参数为: 1、码长:捍=啊×以2 2、信息位:七=毛×屯 山东大学硕士学位论文 3、码率:R:墨。马:丘。蔓 4、最小汉明距离:dmin=dminI×dmin2 由编码理论知,若cI码能纠正fI=[竽卜随机错误,c2码能2qiEt2=[生胡个 随机错误,iuJC,固c2乘积码最多可纠正f=[尘%!]个随机错误。且cI固c2乘积 码还能纠正^个长度小于等于%的突发错误,或纠正f2个长度小于等于啊的突发 错误,以及其他很多错误图样,所以乘积码是一类强有力的纠错码。同理,由二 维乘积码可推广到三维或名维乘积码。 §3.3 Turbo乘积码的交织种类 较多的通信系统中都用到了交织器,其位置一般在信道编码器之后和调制之 前,作为一相对独立的模块,其作用主要是为了分离传输中相关信道的衰落所引 起的连续突发错误。众所周知,一般的信道纠错编码对于纠独立的随机错误是有 效的,而对于突发的连续错误显得没有效果。所以用了交织器之后,就可以把突 发错误分离为近似的随机错误,有利于纠错码的有效纠错。从分集的角度来说, 交织器是一种隐性的时间分集方式。大量的研究表明,交织器的结构和长度在 Turbo码的纠错性能中扮演着重要的角色。 3.3.1交织设计原则 3.3.1.1汉明重原则 在AWGN信道下采用最大似然算法的线性纠错码的性能,和此种纠错码的最 小汉明距离(d。)或自由距离(Jm)有关。Turbo乘积码作为一种线性码,在 AWGN信道下,误比特率近似等于 忍m气产·Qf (3-1) 山东大学硕士学位论文 由于Turbo码可被看作是一种线性分组码,dm也就是最小汉明重量。其中 ^,二是码重等于最小汉明重量的码字的数量,Ⅳ是交织器的长度,ⅥIliII是产生 最小汉明重量码字的输入序列的平均汉明重量。R是编码速率,乓是未编码前 的信息比特的平均能量,高斯白噪声的单边带功率谱密度是Ⅳ0。 由式(3-1)可以看出,对于Turbo码,当交织器长度Ⅳ固定时,要想获得更 好的纠错性能,可以通过增加d二或者减小Ⅳ二两种途径。实际上,一种线性码 的纠错性能不只和最小汉明重量的码字有关系,和汉明重接近最小汉明重量的码 字也有很大关系。也就是说,所有码字中,较低汉明重量的码字极大地影响了这 个码的纠错性能。因此在设计具有更好纠错性能的Turbo码时,可以通过交织器 结构的改变来改变这些低汉明重码字的数量和重量。我们就可通过交织器来打乱 输入序列产生较高汉明重量的校验码字,这样对于整个编码输出码字,就有比较 高的汉明重量。从此种观点来看,交织器的设计就是尽量地提高码字的“J血, 尽量地减少低汉明重量码字的数量Ⅳ。iIl,这就是汉明重原则。 3.3.1.2随机性原则 Shannon在证明Shannon定理时,采用的就是随机编码方式。他从所有g。种 码字中随机挑选出了矿个码字,他指出,当n趋于无穷时,若信息传输速率五 低于信道容量c,就可达到任意低的误码率。显然“n 趋于无穷”在运用中 是不现实的,因此目前的所有信道编码方法都是按照确定性的方法获得。但 Shannon在证明中给了我们一种启示还是不容忽略的,这就是具有随机性的编码 方式会获得较好的结果。Turbo乘积码的译码不是采用最优的最大似然译码算法, 而是采用了次优的迭代译码算法。采用最大似然译码算法时,影响码性能的关键 是码的最小汉明距离或自由距离。而在次优的迭代译码算法中,每次迭代输入的 先验信息和从信道获得的比特信息的相关性将极大地影响译码的性能。因为先验 信息是由另一成员译码器输出的外在信息经交织或反交织获得的。从此种角度来 山东大学硕士学位论文 讲,使外在信息和信道比特信息二者越不相关越好。因此交织器应尽量的使二者 不相关,我们称之为随机性原则。 3.3.2块交织 块交织器(block interleaver)是一种常见的交织器。它沿用了通信系统 中常见的交织器结构。一般来说,交织器的长度是m×弹,交织过程如下:把肌×玎 个输入数据放入一个m行n列的矩阵中,按列的顺序从上到下、从左到右地填入, 等全部m×一个数据填满后,再开始按行的顺序从左到右、从上到下地读出。 块交织器是一种基于汉明重原则设计的交织器,它能比较有效的打乱码重为 2的输入序列,使其能产生较高码重的输出码字。但是块交织器有一个很大的缺 点,就是它不能打乱一些特殊的序列,例如图3_4所示的序列块是无法被一个块 交织器打乱的,而且即使增加了块交织器的长度,这样的序列也是无法被打乱。 类似不能被块交织器所打乱的序列还有很多,这样就会使Turbo码产生许多低重 量码字,从而影响了Turbo码的性能。 图3-4无法被块交织器打乱的序列块 而且,交织器长度越长,不能被块交织器所打乱的序列就越多。所以在长数据帧 的情况下,不可以采用块交织器来构造Turbo码。而在短数据帧的情况下,这一 缺点表现得不是很明显,所以块交织器一般只用于短数据帧的Turbo码。 3.3.3螺旋交织 螺旋交织是沿着编码数据块的对角线方向进行的,译码时再做块交织译码。 具体的交织过程如下列示意图,如:32乘32的方阵 38 山东大学硕士学位论文 l 2 4 63 3 图3-5螺旋交织顺序图 数据按上述方块读入,在按对角线上的顺序数读出如:0 33 66…1023 1 34…992 2 35……31 65…1022的数据流。 螺旋交织相对块交织,把数据的相关性降得更低,突发错误更加随机化,相 应的汉明距离增大,产生高码重的码字。 §3.4基于Chase Turbo乘积码的迭代译码算法 3.4.1 Turbo乘积码的代数译码 代数译码也叫硬判决译码。如果一致校验矩阵为H的分组码C(n,k,d)经信 道传输后对应的码字为R。代数译码器的主要任务就是设法从R中得到正确的错 A A 误图样E,然后计算估值码字C。具体的译码步骤如下: 1)计算伴随式S=HxR’ ^ 2)根据伴随式S找出错误图样E 3)得到译码器的输出——估值码字cA:R一全,若会:c,则译码正确,否则译码错 误。 图3-6硬判决迭代译码 山东大学硕士学位论文 经过解调硬判决的Turbo乘积码数据也可通过行列迭代进行代数译码,如图 3-7所示。如果在比较优质的信道中,也能保证通信的质量。但比软判决算法大 概需要3db多的信号增益,在恶劣的通信条件下纠错性能会大大下降。它体现不 出Turbo乘积码性能优势,但又比单纯的分组码译码性能要好,如图3—6,行译 码时码字有两个错误,不能就错,但列译码能纠正一个错误,然后行在纠错时就 只剩下一个错误,经过两次迭代后便完成了纠错。 ( ) () ( ) o 、 J- JL ^ 1r 'r 、/ V ( ) () ( ) o o () ( ) o 厂、 J- J- ^ V 1r 1r V o () () o 圈3-7迭代后能纠正的错误图样 图3-8不能纠正的错误图样 代数译码在低误码率的情况下,也有它的译码硬伤,如图3—8, “#”字 形的错误图样,即使在低误码率的情况下,代数译码也不能完成纠错。但在“#” 字形错误嵌套比较少的情况下,通过穷尽进行纠错也是个比较好的方法,但这又 是以牺牲译码速度为代价的。所以在数据通信中,信道质量好,对数据的要求不 是很高的情况下,这种快速的代数译码方法还是得到了部分应用,在军事通信侦 查中还是有推广的价值。 3.4.2 Chas@算法 1972年契斯(Chase)提出了一种使码字错误概率最小的软判决译码算法,它 的性能接近于最大似然译码。该算法的基本原理是:利用硬判决译码器,根据不同 的试探序列产生几个候选码字,然后把他们与接收序列进行比较,挑选一个与接 收序列有最小软距离的候选码字作为译码器的输出码字。 Chase译码器的工作过程如下: 1)从解调器输出的接收序列F中,得到一个硬判决序列冠和可信序列a。 , 2)选择一个试探序列T,把它与墨相加,得到一个新的序列R=心十Ta 山东大学硕士学位论文 3)把墨送入硬判决译码器进行译码,得到一个错误图样E-咒十q,这里e是 硬判决译码器所得的一个候选码字. 此时, 因为 巨=R-c,=风+T-C,=F+G+T-C,=F+r,所以译码器认为存在于兄中的 候选错误图样是E=r+F。 4)重复2.3步骤,直到根据错误图样集合所确定的试探序列全部试探完毕,得到 ’ 一组候选的错误图样集合(E}。 5)译码器在集合{E}中,挑选出一个有最小软重量的错误图样点0作为译码器最后 所确定的错误图样。最后,译码器输出己译码字C--风一E。· 根据试探序列集合的大小,Chase算法可分为三种: 1)Chase—I算法:译码器产生所有重量为(t/2)的试验序列,共c=蟛个。这种算这 算法能提供最好的译码性能,但译码器也最复杂,故这种算法只适合于短码和矗 较小的码。 2)Chase—II算法:仅考虑dh/21个最低可信度码元位置错误的情况,即译码器产生 2(%)个试探序列。这种算法的复杂度比chase I低,特别是n很大时更是如此, 但其性能比Chase—I算法稍差。 3)chaseIII算法:译码器产生瓴/2+1)个试探序列。每一个试探序列在i个可信度 最低的码元位置上取l。若以为偶数,则i取0,1,3….,‘-1。若t为奇数, 则i取0,2,4….,以一l。这里i=0,相应于全0试探序列。与前两种算法相比, 这种算法所需的试探序列最少,计算量和复杂度也最小。特别当码的最小距离以 很大时,这种算法的优点更为突出。 3.4.3 Turbo乘积码的软判决算法 假设用线性分组码C(n,k,万),然后把编码码字转化成双极性符号卜1,+1) 在高斯信道上传输。把发送码字记作E={岛,…,吃,…巳},其中el∈{-n1),经信 41 山东大学硕士学位论文 道传输后的接受码字记作R=轨,…,屹,…‘}。R和E的关系可表示为 R=E+G,G=k,…,92,…晶}是标准方差为盯的加性高斯白噪声(AwGN)抽样。 根据最大似然原则,最优判决码字D={dl,…,4,…,或)的判决规则是: 如果陋一∥12<JR—C个,Vz∈【l,2‘】且,≠f,贝lJD=C。(3-2) 式中,CI(d,…,c;,…c:)是c的第i个码字,陋一c,12=∑n(咋一c;)‘是R和c‘之 间的平方欧式距离。 使用(3-2)式的判决规则时,计算复杂度将随着k的增加而指数增长,k>lO 后计算变得非常困难。Chase算法是一种寻找码字D的低复杂度次优算法,它 的原理是:在高信噪比情况下,码字D以很大的可能性位于以R的硬判决码字 y=(乃,…,乃,…,以)为球心, (艿一1)为半径的球体内, 其中 乃=O.5(1+s刚巧))∈(o,1),而在球体内用(3—2)式寻找D能减少很多计算量。为了 进一步减少需要考虑的候选码字,必须用信道信息R去选择球体内最可能的码字, 组成(C}的子集Q,具体过程如下: (1) 用R确定Y中,=p/2】个具有最低可信度的二进制元素的位置。Y中 的元素的可信度定义为: M=J生Pr{e/=趔-I/r/}J1乩[高矧H毫矧卜s, 在信源满足条件Prp,=+1)=Pr和,=-l}z0.5时, A饥)=(事)。o(3-4) 假设信道为平稳信道,且对A∽)按21cr2进行归一化,则乃的可信度定义为 ¨ (2)产生2p个试探模型P。P被定义为一组n维二进制向量,包括一个 。1”在可信度最低的位置上,“0”在其它的位置上:两个“1”在可信度最 (3)形成试探序列z’,其中彳=乃。吁。用代数译码器(或硬判决译码器) D={吐,…,4,…,以}中的元素嘭的可信度用发送码字的对数似然比来定义: 删地毫器器, 伊s, Pr也=+l/R)=EPr征=c‘/R}(3-6) PrG,=一I/R)=EPf{E=c‘/R)(3-Z) 式中,s;‘是{c‘)种满足条件0=+l的码字子集,‘1是{C‘}种满足条件c=一1 具有相同的分布,贝lJA(dj)可以表示成: f∑Pr{R/E=C” A也’叫嚣丽硒l 。.8’ I—Es? J 州E删=c而1,4d一一R-C12] c。-∞ 山东大学硕士学位论文 删岩一州叫2_|~州叫2,+倒 仔∽ 式中, 马4=∞中=[懿21二兰p!(=笋掣]≤·卜,c‘毋∈s“w“)) 当信噪比较高时,盯_o’莩4 4莩局呻o,可忽落‘3—10’式的第二项,把A(嘭) ^:(嘭)=刍(卜c-I(门12-IR形w’12) 把表达式陋一c‘12=窆(巧一d)‘代入(3一11)式,可得 崛,=孔+,勃∥甸 式中, 所=位 , l| n i彳 , ≠ 9中 n (3-11) ∽㈣ (卜埒) 假设盯是常数,对进行标准化得: 丛善:rj+w,2/2 o 。J jj j (3-14) w,=∑rIc?“”P, ,=1.f≠, (3—15) 标准化的厶噱(,:;)是译码器的软输出,它的符号和哆相同,它的绝对值反映了判 决的可信度。(3—14)式表明,:;是软输入数据,:,和外信息一之和,M是一个具有 高斯分布的随机变量。 根据以上分析可知,计算‘是需要两个码字c“‘n和c。∽·最优判决码字D 就是二者之一,另一个码字用c来表示。C是D的竞争码字,它和R之间的欧式 距离最小,且满足c,≠dj。为了找到竞争码字C,必须增加Chase译码码器中最 低可信度位置的个数P,但是同时试探序列的个数(q=2,)也随之增加,找到c 的可能性和译码的复杂性都随着P的增加而增大。为了降低系统复杂度,实际应 用中P不可能无限制地增加,这意味着有时可能找不到竞争码字C。 软输出r:和外信息W,可用以下的公式计算: ‘:{(蝤掣kQ ∽蚓 l卢×乃+rj,c芒。 一;{(蝤掣hcEQ 悟埘 【 夕×乃,c匹Q 其中,口≥0,它的值主要通过实验来确定,可用式来计算。 卢aIln。(咐Pr(ds吲=es)』l=-n(矧] 仔埘 ∥其意义为当正确的判决的概率接近1时,则d,的可靠度趋于无穷,而当正确的判决 的概率接近0.5时,则d,的可靠度趋于零。在实践中可根据经验人为的设定卢值, 虽然在(3—16)中下式不如上式精确,但我们知道对那些存在于R的欧式距离比 D与R的欧式距离仅有微小差别的竞争码字C的判决,需要较精确的软输出估计, 若C与R相距较远,用(3-16)中下式近似估计就足够了。 3.4.5 Turbo乘积码的迭代译码算法 如图3-9所示.单元译码器包括一个基于Chase算法的软输入硬输出译码器 和一个用于把硬输出转化为软输出的外信息计算部分。在单元译码器口∽)和 觑m)称为调节系数。[R]和[w(m)]的抽样标准差不同,[w(m)]的标准差在开始迭 山东大学硕士学位论文 代的时候较大,随着迭代次数的增加而逐步减小,a(m)在迭代初期信噪比比较大 的情况下抑制了[w(m)]的作用。觑m)控制软输出信息的输出峰值范围。 1)l 1w(m 图3_9 Turbo乘积码单元译码框图 单元译码器的工作过程可以分为四步: 1)计软输jr(m)]=[R]+口∽)[w(m)]; 2)由Chase译码器确定子集Q,求得码字D并选出竞争码字c: 3)用C和D计算出外信息[W(m+1)]和输出[R|(m)】: 4)将外信息送入下一个译码器中,作为下一级译码器的先验信息。TPC码的 迭代译码过程如图3—7所示。设发送乘积码码字矩阵[E],相应的接收矩阵为[R], 外信息矩阵为[w(m)](m表示第m个单元译码器,设[w(1)]=O),那么第1n个单元 译码器的输入矩阵为 ER(m)]=Er]+a(m)[W(m)] (3—19) a(m1是第m个单元译码器的调节系数,可以根据子码码型和迭代步数进行调 整。[r(m)]输入到软输入软输出译码器,逐行(或逐列)进行译码,得到软输出矩阵 【R.(m)】,并计算出下一级译码器的先验信息为: [w(m+1)]=【R’(m)】一Er(m)] (3—20) 然后利用外信息矩阵[W(m+1)]按上述过程逐列(或逐行)进行软译码这样就, 完成了两维乘积码的一次完整的迭代译码。也就是说,行译码和列译码都只完成 了半次迭代译码,二者一起才能被称为一次完整的迭代译码。将多个图3一lO所示 山东大学硕士学位论文 的单元译码器串联起来就可以实现不同迭代次数的译码。 图p10 Turbo乘积码译码过程框图 §3.5 Chase II的迭代译码算法的仿真结果 3.5.1 Turbo乘积码的仿真技术参数 用国际卫星上的战例信号作为仿真技术参数,该信号可作为硬件设备的调试 信号源.该信号是典型的Turbo码乘积信号,但与国际通用标准信号相比又有其 特点。该信号的具体参数格式如下: 调制方式:QPSK 信息速率:1.544Mb/s 组网方式:FDMA/VSAT 经解调器解调,对1/I采样的数据分析,信道结构有如下几个特点: l、存在4种相位模糊。 2、去除相位模糊,数据帧长为32768bit,子帧长4096bit,8予帧为一复帧。 3、同步码24bit+lbit。 4、置位式伪随机扰码(11,9,0),加扰长度32768bit,同步跳过加扰(部 分信号在译码完毕后加扰)。 5、去扰后,为(64,57)}(64,57)的Turbo乘积码,且第一个子码前24bit作为 同步码,且第3249bit亦作同步用。 6、(64,57)为扩展汉明码。 7、该乘积码的交织方式为矩阵交织。 8、经过Turbo乘积码译码,该信号为Tl一次群信号。 47 山东大学硕士学位论文 该信号增益比较低,I/1的报面分析,误码率比较高,所以进行乘积码的概 率译码很有必要。由该信号的特点可得我们的仿真思路,首先要在解调后,未判 决前,进行同步搜索、去模糊和去扰处理,然后再进行乘积码的SIS0译码,这与 标准信号的去扰都在译码后进行有明显的不同。同时也增加了工程的难度。 3.5.2 Turbo乘积码的译码编程实现 针对上述信号,数据编程处理流程如图3-11所示: 据流 图3-11数据处理流程图 Chase迭代译码模块的详细编程思路如图3—12所示。 48 山东大学硕士学位论文 图3-12 Chase迭代译码算法流程图 山东大学硕士学位论文 3.5.3 Turbo乘积码的性能分析 p(m)的取值一般人为的设定,如要迭代8次。卢(m)=[o.2、0.4、0.6、0.8、 1.0、1.O、1.0、1.0】,口(m)是用来减小迭代初期[、Ⅳ】对软输出的影响,并且根 据经验人为地设定的,口(m)=【o.0、0.2、0.3、0.5、0.7、0.9、1.0、1.o】。 Turbo乘积码的Chase算法的性能图如下,在AWGN信道上,用~latlab 进行的仿真。 图3-12 P变化,迭代4次Chase迭代算法性能 山东大学硕士学位论文 图3—13 P变化,迭代8次Chase迭代算法性能 图3-14 P变化,迭代4次Chase迭代算法性能 山东大学硕士学位论文 图3—15 P变化,迭代8次Chase迭代算法性能 比较以上图3一13、图3一14、图3一15和图3-16,我们可以看出,R越大的码 字误码率越大,予码为(32,26)要比子码为(64,57)的码字的性能要好0.5db 左右。同时,P和迭代次数的值越大,系统的性能越好,误码率越低,收敛速度 越快。但同时,译码的复杂度及时延也在增大。如何选择一个好的系统,肯定要 在计算速度与性能之间有个折衷。 §3.6本章小结 本章首先介绍了Turbo码的发展历史及现状,Turbo乘积码的优势,然后介 绍了Turbo乘积码的构成原理,分别介绍了乘积码的子码选择及构造过程中的交 织原则和交织种类。 Turbo乘积码的优势在于其概率译码,主要介绍了软判决译码理论原理,Turbo 乘积码的迭代译码算法。 又根据工作中碰到的非标准Turbo乘积码信号,解决了在软值情况下的同步码 搜索,软值情况下的相位模糊处理,及改进迭代算法,在算法中加进去扰的方法。 保证了译码的正确性。 山东大学硕士学位论文 最后,对算法用Matlab进行了仿真,测得了具体数值,确定了具体的性能要 求,得出了迭代次数和不确定位置对迭代算法的影响,并为下一步硬件设计的复 杂度及时延的折衷,提供了调节依据。 山东大学硕士学位论文 第四章Turbo乘积码的FPGA实现 §4.1硬件实现工具简介 随着半导体技术、集成技术和计算机技术的发展,电子系统的设计方法和设 计手段发生了很大的变化,传统的“固定功能集成块+连线”的设计方法已经被基 于芯片的设计方法所取代。其中,可编程ASIC已经成为当今世界上最富吸引力的 半导体器件.只要拥有一台计算机、一套相应的EDA软件和空白的可编程逻辑器 件,在实验室里就可以完成数字系统的设计与生产。 EDA(Electronics Design Automation)技术提供了一种“自顶向下”的全 新设计方法。这种设计方法首先从系统设计入手,在顶层进行功能方框图的划分 和结构设计。在方框图一级进行仿真、纠错,并用硬件描述语言对高层次的系统 行为进行描述,在系统一级进行验证。然后用综合优化工具生成具体门电路的网 表,其对应的物理实现级是可编程逻辑器件。由于设计的主要仿真和调试过程是 在高层次上完成的,这不仅有利于早期发现结构设计上的错误,避免设计工作的 浪费,而且也减少了逻辑功能仿真的工作量,提高了设计的成功率。 在可编程逻辑器件方面,我们选择了FPGA(现场可编程门阵列),其基本特 点主要有: 1)采用FPGA设计ASIC电路,用户不需要投片生产,就能得到合用的芯片。 2)FPGA可做其它全定制或半定制ASIC电路的中试样片。 3)FPGA内部有丰富的触发器和I/0引脚。 4)FPGA是ASIC电路中设计周期最短、开发费用最低、风险最小的器件之一。 5)FPGA采用高速CHMOS工艺,功耗低,可以与CMOS、TTL电平兼容。 可以说,FPGA芯片是小批量系统提高系统集成度、可靠性的最佳选择之一。 由于该算法的实现需要的资源比较大,工作频率高,又受到器件封装的限制, 因此选择了Xilinx公司的VirtexE系列的xcv400e-6P0240C来实现。它有9800 个LC(109ic cell),是目前贴片封装类资源最丰富的一类,适合焊接。 山东大学硕士学位论文 硬件描述语言是一种用于设计电子系统硬件的计算机语言,它以软件编程的方 式来描述电子系统的逻辑功能、电路结构和连接形式,硬件描述语言适合大规模 电子系统的设计。硬件语言具有入门快,操作简单,功能强大的特点,因此该算 法可用硬件语言Veri log HDL完成。 我们的设计输入是采用Verilog HDL语言方法实现的。Verilog HDL语言描述 能力强,覆盖面广,语言简练,抽象能力和可读性强,适合于硬件模型建模,其 功能涵盖了电路描述、电路合成、电路仿真等设计工作。改进序列译码算法对用 FPGA实现来说,由于涉及到许多数学运算、数据存储、比特操作等功能的设计, 相对于传统的原理图输入、状态机输入法,Veri log HDL语言具有非常明显的优 势,实现起来更加方便、灵活。设计实现和设计仿真是在Xilinx公司的ISE集成 开发平台下完成的 §4.2 FPGA设计流程 FPGA的设计是通过专用的EOA工具来完成的,主要包括设计输入(Design Entry)、设计实现(Design Implementation)和设计仿真(Design Simulation) 的。在设计过程中,根据设计的需要,基于可用的元件库和IP库资源,设计者可 反复调用工具、交错进行电路设计、实现和仿真。其设计流程如图4-I。 4.2.I设计输入 设计输入包括使用硬件描述语言HDL、状态图与原理图输入三种方式。HDL 设计方式是现今设计大规模数字集成电路的良好形式,除IEEE标准中VHDL与 Verilog HDL两种形式外,尚有各自FPGA厂家推出的专用语言,如Quartus下的 AHDL。HDL语言描述在状态机、控制逻辑、总线功能方面较强,使其描述的电路 能特定综合器(如Synopsys公司的FPGA Compiler II或FPGA Express)作用下 以具体硬件单元较好地实现;而原理图输入在顶层设计、数据通路逻辑、手工最 优化电路等方面具有图形化强、单元节俭、功能明确等特点,另外,在Altera 公司Ouartus软件环境下,可以使用Momory Editor对内部memory进行直接编辑 置入数据。常用方式是以HDL语言为主,原理图为辅,进行混合设计以发挥二者 山东大学硕士学位论文 各自特色。通常,FPGA厂商软件与第三方软件设有接口,可以把第三方设计文件 导入进行处理。如Quartus与Foundation都可以把EDIF网表作为输入网表而直 接进行布局布线,布局布线后,可再将生成的相应文件交给第三方进行后续处理。 图4_l FPGA设计流程图 山东大学硕士学位论文 4.2.2设计综合 综合,就是针对给定的电路实现功能和实现此电路的约束条件,如速度、功 耗、成本及电路类型等,通过计算机进行优化处理,获得一个能满足上述要求的 电路设计方案。也就是是说,被综合的文件是HDL文件(或相应文件等),综合的 依据是逻辑设计的描述和各种约束条件,综合的结果则是一个硬件电路的实现方 案,该方案必须同时满足预期的功能和约束条件.对于综合来说,满足要求的方 案可能有多个,综合器将产生一个最优的或接近最优的结果。因此,综合的过程 也就是设计目标的优化过程,最后获得的结构与综合器的工作性能有关。FPGA Compiler II是一个完善的FPGA逻辑分析、综合和优化工具,它从HDL形式未优 化的网表中产生优化的网表文件,包括分析、综合和优化三个步骤。其中。分析 是采用Synopsys标准的HDL语法规则对HDL源文件进行分析并纠正语法错误:综 合是以选定的FPGA结构和器件为目标,对HDL和FPGA网表文件进行逻辑综合; 而优化则是根据用户的设计约束对速度和面积进行逻辑优化,产生一个优化的 FPGA网表文件,以供FPGA布局和布线工具使用,即将电路优化于特定厂家器件 库,独立于硅持性,但可以被约束条件所驱动。利用FPGA Compiler II进行设计 综合时,应在当前Project下导入设计源文件,自动进行语法分析,在语法无误 并确定综合方式、目标器件、综合强度、多层保持选择、优化目标等设置后,即 可进行综合与优化。在此可以将两步独立进行,在两步之间进行约束指定,如时 钟的确定、通路与端口的延时、模块的算子共享、寄存器的扇出等。如果设计模 型较大,可以采用层次化方式进行综合,先综合下级模块,后综合上级模块。在 进行上级模块综合埋设置下级模块为Don’t Touch,使设计与综合过程合理化。 综合后形成的网表可以以EDIF格式输出,也可以以VHDL或Verilog HDL格式输 出,将其导入FPGA设计J一商提供的可支持第三方设计输入的专用软件中,就可进 行后续的FPGA芯片的实现。综合完成后可以输出报告文件,列出综合状态与综合 结果,如资源使用情况、综合后层次信息等。 4.2.3仿真验证 从广义上讲,设计验证包括功能与时序仿真和电路验证。仿真是指使用设计 山东大学硕士学位论文 软件包对已实现的设计进行完整测试,模拟实际物理环境下的工作情况。前仿真 是指仅对逻辑功能进行测试模拟,以了解其实现的功能否满足原设计的要求,仿 真过程没有加入时序信息,不涉及具体器件的硬件特性,如延时特性;而在布局 布线后,提取有关的器件延迟、连线延时等时序参数,并在此基础上进行的仿真 称为后仿真,它是接近真实器件运行的仿真。 4.2.4设计实现 实现可理解为利用实现工具把逻辑映射到目标器件结构的资源中,决定逻辑 的最佳布局,选择逻辑与输入输出功能连接的布线通道进行连线,并产生相应文 件(如配置文件与相关报告)。通常可分为如下五个步骤。 l、转换:将多个设计文件进行转换并合并到一个设计库文件中。 2、映射:将网表中逻辑门映射成物理元素,即把逻辑设计分割到构成可编程 逻辑阵列内的可配置逻辑块与输入输出块及其它资源中的过程。 3、布局与布线:布局是指从映射取出定义的逻辑和输入输出块,并把它们分 配到FPGA内部的物理位置,通常基于某种先进的算法,如最小分割、模拟退火和 一般的受力方向张弛等来完成;布线是指利用自动布线软件使用布线资源选择路 径试着完成所有的逻辑连接。因最新的设计实现工具是时序驱动的,即在器件的 布局布线期间对整个信号通道执行时序分析,因此可以使用约束条件操作布线软 件,完成设计规定的性能要求.在布局布线过程中,可同时提取时序信息形成报 靠。 4、时序提取:产生一反标文件,供给后续的时序仿真使用。 5、配置:产生FPGA配置时的需要的位流文件。 在实现过程中可以进行选项设置。因其支持增量设计,可以使其重复多次布 线,且每次布线利用上一次布线信息以使布线更优或达到设计H标。在实现过程 中应设置默认配置的下载形式,以使后续位流下载正常。 4.2.5时序分析 在设计实现过程中,在映射后需要对~个设计的实际功能块的延时和估计的 布线延时进行时序分析;而在布局布线后,也要对实际布局布线的功能块延时和 山东大学硕士学位论文 实际布线延时进行静态时序分析。从某种程序来讲,静态时序分析可以说是整个 FPGA设计中最重要的步骤,它允许设计者详尽地分析所有关键路径并得出一个有 次序的报告,而且报告中含有其它调试信息,比如每个网络节点的扇出或容性负 载等。静态时序分析器可以用来检查设计的逻辑和时序,以便计算各通中性能, 识别可靠的踪迹,检测建立和保持时间的配合,时序分析器不要求用户产生输入 激励或测试矢量。虽然Xilinx与Altera在FPGA开发套件上拥有时序分析工具, 但在拥有第三方专门时序分析工具的情况下,仅利用FPGA厂家设计工具进行布局 布线,而使用第三方的专门时序分析工具进行时序分析,一般FPGA厂商在其设计 环境下皆有与第三方时序分析工具的接口。Synopsys公司的PrimeTime是一个很 好的时序分析工具,利用它可以达到更好的效果。将综合后的网表文件保存为db 格式,可在PrimeTime环境下打开.利用此软件查看关键路径或设计者感兴趣的 通路的时序,并对其进行分析,再次对原来的设计进行时序结束,可以提高工作 主频或减少关键路径的跹时。与综合过程相似,静态时序分析也是一个重复的过 程,它与布局布线步骤紧密相连,这个操作通常要进行多次直到时序约束得到很 好的满足。在综合与时序仿真过程中交互使用PrimeTime进行时序分析,满足设 计要求后即可进行FPGA芯片投片前的最终物理验证。 4.2.6下载验证 下载是在功能仿真与时序仿真正确的前提下,将综合后形成的位流下载到具 体的FPGA芯片中,也叫芯片配置。PPGA设计有两种配置形式:直接由计算机经 过专用下载电缆进行配置:由外围配置芯片进行上电时自动配置。因FPGA具有掉 电信息丢失的性质,因此可在验证初期使用电缆直接下载位流,如有必要再将烧 录配置芯片中(如Xilinx的XCl8V系列,Altera的EPC2系列)。使用电缆下载 时有多种直载方式,如对Xilinx公司的FPGA下载可以使用JTAG Programmer、 Hardware Programmer、PROM Programmer三种方式,而对Altera公司的FPGA可 以选择JTAG方式或Passive Serial方式。因FPGA大多支持IEEE的JTAG标准, 所以使用芯片上的JTAG口是常用下载方式。将位流文件下载到FPGA器件内部后 进行实际器件的物理测试即为电路验证,当得到正确的验证结果后就证明了设计 的正确性。电路验证对PPGA投片生产具有较大意义。 山东大学硕士学位论文 §4.3 Turbo乘积码的FPGA实现 4.3.1技战术指标 信号输入接口:750,BNC 信号输出接口:750,BNc 信号输入方式:串行数据, TTL电平,时钟占空比50%±105,相位可选 输入数据格式:6bit量化 信号输出方式:同步输出, 时钟下降沿对准数据沿,时钟占空比5096±1%, 相位可选 数据输入速率:lkbps~8Mbps 译码器入锁:当数据输入速率为1Mbps时,入锁时间≥250ms 误码率:信噪比为4.OdB时,译码误码率数量级在104左右 4.3.2具体实现的硬件结构 FPGA实现的硬件结构比较简单,主要要做好程序的下载与配置。下载是指通 过JTAG从计算机将程序文件下载到EEPROM中,配置是指上电时从EEPROM中读取 数据来配置FPGA。 图4—2硬件结构图 FPG^内部功能划分为输入模块、迭代译码模块和输出模块。信号输入部分为 6bit的已量化软值,其前端为数字解调器的输出,即在I\0路上的采样量化输出。 因前端设备这一功能,省去了A/D模数转化设备。FPGA的内部模块划分如图4-3 所示: 输入模块实现把数据接收下来,经过串并转换,按6bit一字节,离位补零存 60 山东大学硕士学位论文 到输入数据存储区中,当存入数据存储区中的数据达到一个量值,就产生一个后 续模块的启动信号。主要包括串/并转换,双口EAM,地址管理,译码搜索模块接 口,错误处理等。其中输入数据存储区设计和错误处理是本模块的难点. 输入数据存储区应设计为双缓存区。当第一个存储区存满数据时,启动译码 器对第一个存储区数据译码,而以后接收的数据存储到第二个存储区,直到第二 个存储区存满数据时,再启动译码器对第二个存储区数据译码。这样做虽然增加 了存储器开销,但是可以减少了缓冲器控制电路的复杂性,减少了因误码太多导 致译码器搜索次数增加引起的数据覆盖的可能性。在某一位置产生误码集中时, 增加的搜索次数将与其它位置平均,可以降低对译码时钟的要求。因此,输入数 据存储区应足够大。 图}3 FPGA内部模块化分 ?……………j霜£瓣…一…。………。。.: l I 。耐.叫i: :I.…………………………………….●: 图}4输入模块 6I 山东大学硕士学位论文 我们把译码模块划分为几个部分进行设计: 1、同步检索模块 在6bit量化的软值里进行同步码的搜索,可先进行0、l硬判决,从中找同 步码,然后根据找到的位置,确定软值的起始位置,也可通过极性的变化来找同 步码,极性的变化不用再进行硬判决,大大地降低了计算量及时间延迟,所以在 我们的检索中用极性的变化来找同步码。根据同步码来进行相位模糊的调整,在 软值上进行去相位模糊的处理。 2、加扰处理模块 该设备针对工作中特有的信号编码格式展开。该信号是在编码后进行加扰, 所以在译码前要先进行去扰,如何在软值上进行去扰?这个问题给我们的工作带 来了很大的困难,它不同于相位模糊的极性简单调整处理。在深入地研究了迭代 译码的基础上,我们采取在软值上不进行去扰处理,因扰码与信息也只是简单的 线性模二加,所以只在硬判决后使用代数译码时,可先去扰,进行译码判断。外 部信息在软值上相加,可只认为对信息部分的加权。对迭代译码结束,再对硬判 决的数据进行去扰处理。 3、迭代译码模块 (1)存储器的管理 我们设计了五个功能不同的存储器:分别是输入缓存存储器、软输出信号存 储器、外信息存储器、测试序列T存储器和码字子集C存储器。 输入缓存存储器用于存储模糊处理的待译码的原始数据。我们将输入缓存存 储器设计为一个循环存储器,同时设计了两个地址控制器:当前处理码字地址控 制器和输入数据存放地址控制器。每个地址指向6bits单元。首先向存储器中写 入6bits原始数据,输入数据存放地址加1,指向下一次数据存放的地址。每次 读入一块数据即:4096*6bit。 软输出信号存储器,用来存储[R(m)]=[R]+a(m)[w(m)]的值。外信息存储器用 来存储[W(m+1)]=【R’(m)】一[R(n1)]的值。测试序列T存储器用来存储由不确定位 置P所确定的当前须判断码字的集合。码字子集C存储器存储的是对测试序列T 进行代数译码后的码字集合。为了不影响译码速度和避免数据被覆盖,我们对应 山东大学硕士学位论文 软输出信号存储器、外信息存储器、测试序列T存储器和码字子集c存储器增加 了相同深度和宽度的镜像寄存器,采用了并行比较、并行存储、并行处理方式, 在一次操作中即可完成排序存储工作,大大提高了译码速度。 (2)一次迭代单元的设计和实现 迭代译码是行列反复迭代进行得,因此,我们可以先来设计一次迭代过程的 实现方法。一次块迭代是数据块中每一行码字都进行一次迭代,所以块划分到单 个码字迭代是最小的基本单位,我们只须完成一个码字一次迭代,其原理框图如 图4-5所示。 出绝对值比较大小。确定 可信度最小的位置p1..p4 形成铡试序列T ,T存储器 读 教 出 据 —— 缓 十 存 码 器字 大于O判为1,小于0判为o ,形成硬判决码字 与c集合中的字码分掰l 计算欧式距离。取值j 最小的判为最佳码字D 厂一—] }代数译爵{ | …J 了 形成码字集合| c存储器 I 扰守列 存储器 由最佳玛字D。逐比特在c集合中找,并计算欧 式距离,找次最佳码字c。井计算软输出【赳m)1 及外信息【w(m+1)】 【。 。 。1。 。 。 “’ 。 。1。— ’。 。— 一 l更新软输出R【m】存储器j …一i、之一一一 I教输出Rm牌判决赣出| DA^cLl( V V 『一…… 一] I竺竺璺翌竺竖堕到 图4.5单个码字迭代过程的实现原理 山东大学硕士学位论文 (3)分时钟处理和同步操作 算法涉及到读数据、量值的计算和比较、存数据和输出等,每译一个码字都 要至少做这样一次操作,在一个时钟内是不能完成的。我们对主时钟进行了计数, 每一次操作都经若干个时钟来完成,这样能够稳定的实现每一次操作,不过影响 了译码速度。 算法涉及到寄存器读写和数据操作比较多,因此选系统时钟进行同步,可以 确保译码的正确性和稳定性。 输出模块将译码结果缓存,然后以输入码率的0.79输出。包括输出数据存储 区和输出控制电路。输出数据存储区与输入数据存储区相类似,也是双缓冲区。 当第一个输出数据存储区存满时,启动数据输出。 §4.4本章小结 本章先介绍了目前硬件设计的发展情况及使用工具,指出了FPGA的特点和一 般的设计流程。为下一步具体的应用,打下了基础。 Turbo乘积码的FPGA的实现,按照先整体设计,再逐模块设计和调试展开。 整体模块分为输出模块、译码模块和输出模块。输出和输入模块涉计到存储器的 设计。译码模块包括了,模态下的同步码搜索模块、模态下的相位模糊处理模块、 迭代译码模块。 此设备的模拟实验阶段是从2007年6月开始的,由于工作量比较大,我们将 研制工作分成了两部分:FPGA芯片的程序加载和工作,对实时信号的调试。 实时译码工作正确与否的调试又分为输入模块调试,译码模块调试,输出模 块调试。调试中首先由自己编写发送数据,通过数据采集发送设备(SLUOllD)发 送理想数据验证译码的正常。 山东大学硕士学位论文 第五章结论与展望 在这一章,我对本论文中的主要研究工作进行概括和总结,并且根据自己对 turbo乘积码的学习体会和研发经历,就本论文的后续工作提出了若干建议: 1.在掌握有关信息论、信道编码领域的基本原理的基础上,总结阐述了编码原 则及译码规则,并从应用的角度给出有关信道的Shannon极限及性能测度。 2.概括了线性分组码基础知识,给出了其校验矩阵、生成矩阵及线性分组码的 重量和距离参数,总结了一般线性分组码的译码方法,给出了有关分组码的 常用的最小距离界,来评价分组码的纠错性能。 3.给出了Turbo乘积码发展情况,给出了编码原理,交织种类及交织设计原则, 介绍了基于Chase Turbo乘积码的迭代译码算法,进行了基于Chase II的迭 代译码算法的仿真,仿真的结果验证了算法正确,并达到了设计的要求。 4.给出了硬件设计的发展情况及开发工具,指出了FPGA的特点和一般的设计流 程。Turbo乘积码的FPGA的实现,按照先整体设计,再逐模块设计和调试展 开。实现模块分为输入模块,译码模块和输出模块。输出和输入模块涉及到 存储器的设计。译码模块包括了,同步搜索模块、相位模糊处理模块、迭代 译码模块及去扰模块。并给出了设计框图,初步设计出电路板,模块结构。 5.本论文的创新点,在于成功仿真出了基于Chase II迭代译码算法,并在算法 的初始化上给出了更利于速度实现的调整,提高了设备对时间延迟要求的性 能。在模拟数据上解决了同步搜索和相位模糊问题,为算法实现上做好了先 决条件。 6.Chase算法需要执行复杂的运算,占用庞大的存贮空间,给硬件的开发,带 来了一定的难度,对高速的信号,时间延迟成为该算法实时处理的一个瑕点。 下一步应继续进行算法的摸索,尝试其他资料反映的译码方法,和改进现有 的方法,比较性能,折衷考虑硬件设备的要求和算法,开发出更适宜的工作 设备。 山东大学硕士学位论文 7.不同交织方法对turbo乘积码算法及性能的影响。在先前的数据分析工作中, 发现交织的种类有矩阵交织和螺旋交织两种,矩阵交织又有单比特交织、双 比特交织和字节交织;螺旋交织一般符合标准。交织种类的不同,就会影响 迭代过程中算法,及这种算法性能。因工作中,非标准的交织方式很多,双 比特及字节的交织算法及硬件开发有必要迸一步展开. 8.在Rayleigh衰落信道中,turbo码仍然是性能出色的纠错码。目前短波信道 中,也侦获turbo乘积码信号,继续探讨Rayleigh衰落信道下的译码算法设 计,在当前算法下有如何的改进和修改,将关系到工作面的开源和短波阵地 的建设。 9.turbo乘积码的子码目前仅限于汉明码,在实际的工作中发现,子码还有缩 短的汉明码,BCH码,循环码,缩短的BCH码和缩短循环码,对这些子码构 成的Turbo乘积码研究和设备扩展,有必要进一步展开。 10.工作中对一些非标准信号的数据源分析发现,同步码作为子码的一部分参加 编码,同时又做同步码用;校验部分还有复帧同步的插入;这些现象都对译 码的完整性构成了用难,有待进一步检验,改进算法。 11.如何解决去扰问题。加扰的方式破坏了Chase算法中的代数译码及置信度的 取舍,目前有加扰的该类信号解决方法仅实现了代数迭代的译码,其性能结 果远低于软判决译码的性能。如何实现该类信号的软判决译码,是下一步工 作的当务之急。 12.要想把turbo乘积码的研究做的深入,仅靠仿真是不够的,必须同时借助理 论分析,要做到这一点,需要有近世代数等良好的数理基础,以及对信息论 的深入理解。 13.更多的非标准turbo码信号的侦获,要求我们应加快设备的研发速度,DSP 和FPGA各有其优点,可以相互结合使用,尽快的建立起一套通信的一般接收 模板,根据不同的参数,及时调整硬件程序,为侦查提供得力的设备。 14.目前,我单位的多通道解调器项目正在研制开发中,信道解码是一个很重要 的组成部分,如何实现更多非标准信号软迭代解码,对系统的性能改善和设 计指标至关重要,所以有必要继续投入精力研究利用外信息的迭代译码研究。 山东大学硕士学位论文 参考文献 【1】C.E.Shannon,"AMathematicalTheoryofConanunication',BellSyat.Tech.J.,27,PP. 379-423(Part 1),623-656(Paft 2)’July 1948. 【2】J.Viterbi end J.k Omura,Principles ofDigital Commun记ation and Coding.McGraw-Hill。 NewYork,1979. 【31 SHU LIN and D.J.CoatcUo,Jr.,Error Control Coding Fundamentals and Applications, Prentice-Hall,Englewood Clif瑰N.J.,1983. 【4】樊昌信,詹道庸等,超蔗原a吕国防工业出版社.北京,1995年第4版。 【5l王新梅肖国镇,‘纠错码一原理与方法》,西安电子科技大学出版,出版日期,2001.4 【6】刘东华,Turbo码原理与应用技术,电子工业出版社,2004年1月第1版 [7]吴伟陵。通向信息编码定理的Turbo码及其性能分析电子学 报,1998,26(7):35-40,. [8J s.Benedetto,D.Divsalar,G.Montorsi,etaL Soft-Output Decoding Algorithms in Iterafive Decoding of Turbo Codes[J].The Teloconanunication and Data Acquisition Progress Report.Feb 1996:63—87· 【9】C.Berrou,A.Glavietw,,and P.Thitimajshin瑰"Near Shannon Limit Error-Correcting Coding and Decoding:.Turbo-Codes"ICC’93,Geneva,Switzerland,May 93,PP.1064-1070. 【10】曹志刚,钱亚生,现代通信原理,清华大学出版社,北京,1992年第1版。 【11]R Pyndiah,et a1.Near Optimum Decoding of Product Codes[A].Pruc.IEEE GLOBECOM'94 Conf.,v01.1[c].SanCA:Francisco.1994.330~343。 【12】Reynd觚NearOptimumDecodingofProductCodes:BlockTurbocodesrJ3.IEEETram. Oil Comxnunications,1998,46(8)。 【13】xu磁Wei,AliNAkaasu.OnParallelIterativeDecodingofProductCode[A].inVTC2001 Fall(v01.4)[c].October 2001.2483’2486。 【14】仇佩亮:‘信息论与编码》高等教育出版社,2003 【15】郭阅仑:(Turbo码的设计与实现》,上海交通大学,硕士论文,2001 IHill●___I-—_●●_____-_______●-山__东__大__学__硕__士 ___学_●位-论-—文_●__●_-_●-_--_lI_--___________- 116}方敏:《分组1、西。码的研究》,四川大学,硕士论文,2003 【17】郭阅仑,罗汉文,宋文涛,“Turbo Code译码算法的硬件实现”,兽詹Z嘲2000 【18】钱良,罗汉文,宋文涛,“FPGA实现WCDMA系统中Turbo码解码方法”,翦子产拱 型男,2000年第3期。 【l 9】王立宁,乐光新,詹菲.MATLAB与通信仿真.北京:人民邮电出版社,1999 【20】刘宝琴.ALTERA可编程逻辑器件及其应用.北京:清华大学出版社,1995 [23】白宝明,马啸,王新梅.三维Turbo码的设计与性能分析EJJ.西安电子科技大学学 报,1998,25(5):570~574 【241袁东风-张海霞,编码调制技术原理及应用 ,清华大学出版社2006第一版 [25】袁东风,张海霞,宽带移动通信中的先进信道编码技术.北京邮电大学2004 【26]刘玉君,信道编码河南科学技术出版社1992年第一版 【z7]王新梅,马啸,软判决译码研究的进展,电子学报1998(7) 山东大学硕士学位论文 致谢 在论文完成之际,我要向所有关心和支持我论文工作的老师、同事和朋友表 示我诚挚的谢意。 首先要感谢我的导师——袁东风教授。袁老师在我就读研究生期间始终给予 了耐心细致的指导和无私的帮助,我所取得的成绩均得益于他的引导与启发。在 此我向我的导师表示真挚的感谢和崇高的敬意!袁老师严谨的治学态度、夜以继 日的工作精神,敏捷的创新思维、渊博的学识及儒雅学者风范都给我留下了深刻 印象,是我今后工作和学习的榜样。 感谢我的妻子和我可爱的~岁女儿给予了我世界上最无私,最无微不至的关 怀和精神上的慰籍。 对在百忙之中抽出时问来审阅我的论文,参加我的答辩的各位老师,在此表 示衷心的感谢。 感谢山东大学电二子工程系各位老师的培养以及通信实验室各位成员的支持和 帮助。 还要感谢山东大学上学期间亲密的战友,所给予的学习上的帮助和牛活上的 照顾。 另外,还要感谢济南军区技术局五处的领导,及一科的全体同志,特别是李 太杰博士和徐军科长的帮助和指导。 感谢所有没有感谢到的人和事。 Turbo乘积码的译码算法及FPGA实现 作者: 学位授予单位: 顾丽旺 山东大学 相似文献(7条) 1.会议论文 刘伟.张海林.刘增基 比特交织Turbo乘积码编码调制 2003 本文研究AWGN信道和Rayleigh平坦衰落信道中比特交织Turbo乘积编码调制(BITPCM)的实现方法,并采用硬判决反馈迭代解调方法方法进一步改善 BITPCM系统的性能.通过对BITPCM、网格编码调制和比特交织编码调制的性能比较,结果表明无论是AWGN信道还是Rayleigh衰落信道,BITPCM的性能都优于 传统的网格编码调制和比特交织编码调制. 2.学位论文 金姝 Turbo乘积码的应用实现研究 2004 在信道编码的发展过程中,人们一直在追寻误码率低、译码复杂度可以忍受的编码方法.1993年Berrou等提出了Turbo码,这种码在接近香农极限的低 信噪比下仍能够获得较低的误码率,它的出现在编码界引起了广泛的关注,并成为编码研究领域最新的发展方向之一.但是Turbo码存在着译码结构复杂,译 码延时大的缺陷.因此在Turbo码的基础上,有学者提出了Turbo乘积码,Turbo乘积码继承了Turbo码的优点,又因为Turbo乘积码的构造采用了线性分组码 ,所以译码方法比Turbo码简单.Turbo乘积码近年来开始受到关注,因为其低误码率与较小的译码延迟而适用于各种通信场合.该文首先研究了TPC的编译码 原理.TPC的编码主要是由两到三个线性子码的组合构成一个矩阵,并对行和列分别编码.在编码中加入交织可以减少信道传输中的突发错误;译码采用的是 软输入软输出迭代译码结构.依照TPC编码的原理,该文阐述了一个编码8×8码块的TPC编码器的设计方案.在实际的应用中,编译码器均采用了AHA公司生产 的第一代TPC编译码芯片AHA4501,该芯片通过对内部寄存器的控制能够完成不同TPC码的编译码.但是由于芯片缺少码块同步的功能,这一点在实际设计中 需要利用外部电路加以弥补.该文还在理论研究的基础上阐述了TPC硬件实现系统的设计方案.系统的外部电路基本上都由FPGA完成,首先介绍AHA4501芯片 的初始化流程,使之能够正确完成TPC的编译码,然后阐述FPGA实现的AHA4501传输码块的同步功能设计方案与流程.最后介绍电路板的制作与调试. 3.学位论文 娄渊志 基于无线信道的H.264编码端抗误码研究 2005 本文详细分析了H.264的两种数据划分的方法,一种方法是视频图像可以划分为ROI区域和非ROI区域。另一种方法是H.264的码流数据可依据不同的 语法元素划分为不同的类别。我们划分数据的根本目的是对重要的信息提供更好的误码保护,对不重要的信息提供一般的误码保护。 对角交织的应用,使得低判决可信度比特集中分布在TPC的某些数据页,结果TPC的纠错能力急剧下降。本文用双映射的方法解决了低判决可信度比特 集中分布的问题,保证低判决可信度比特在数据页之间平均分布,并且保证低判决可信度比特在数据页内分散分布。这使得TPC迭代纠错译码的性能得到 最好的利用,既有利于提高抗误码纠错能力,又有利于减少迭代次数、译码运算量和译码时间。 4.期刊论文 徐进廷.李红信.XU Jin-ting.LI Hong-Xin Turbo乘积码梯度译码算法研究 -通信技术2008,41(12) Turbo乘积码(简称TPC码)是一类采用简单的行列交织器将分组码进行串行级联而构成的纠错码.文中针对二进制turbo乘积码提出了一种快速的软判 决译码算法一梯度译码算法.该算法是以迭代Chase算法为基础,通过利用chase算法上次迭代译码而得到的每行(或列)最优判决码D(m-1)来代替竞争码字 C,节省了寻找C的过程,从而简化了外信息和软输出的计算.仿真结果表明:梯度算法能在基本保持turbo乘积码的Chase算法译码性能基础上,提高了译码速 度,降低了译码复杂度. 5.学位论文 张乐 MIMO-OFDM无线通信系统中迭代接收与自适应技术的研究 2006 近年来,移动通信技术在全球范围内得到了迅猛的发展.市场需求的不断扩大刺激着移动通信技术在数据速率和系统容量上的要求不断提升.但是 ,3G移动通信技术提供的最高2Mbps的数据业务能力已经不能满足未来移动通信高速数据业务以及多媒体业务的需求.在有限的频谱资源上提供高速、高质 量的数据传输业务将成为未来移动通信系统中无线传输技术必须解决的问题. 针对新的业务要求,近年来,宽带无线移动通信系统对传输技术的需求和应用迅速增长.能够支持更高数据传输速率的新一代移动通信系统(Beyond 3G/4G)已经成为研究的热点.而被广泛用于无线局域网络(Wireless Local Area Network,WLAN)和高清晰度电视(High Definition TV,HDTV)地面传输等 标准的正交频分复用技术(Orthogonal Frequency Division Multiplexing,OFDM)和近年来崭露头角的多入多出技术 (Multiple Input Multipie Output),被认为是B3G/4G通信系统的有效、可行的实现方案. 本文以B3G/4G通信系统研究为背景,深入研究了基于MIMO-OFDM技术的无线移动通信系统中与迭代接收和自适应技术相关的若干关键问题.主要内容包 括:研究了双二元Turbo码译码器的终止迭代准则及自适应译码算法;研究了 Turbo 乘积码的随机交织编译码方案;研究了一类基于整环上置换多项式的交 织器;研究了基于3GPP编码方案的交织器存储方法;针对GSTBCMIMO-OFDM这种多天线多载波系统架构,研究了结合信道估计、MIMO解调与信道译码单元的迭 代接收机设计方法. 研究MIMO-OFDM系统中基于奇异值分解的自适应技术. 首先,对MIMO信道作了深入研究,分析了它的容量特性、空时编码方法以及空时信号检测算法,并对信道编码中的 Turbo 码编译码方法进行分析,为后 续提出的纠错码编译码方法以及迭代接收机设计的研究奠定了基础. 论文的重点之一是对多种纠错编码的研究和分析.双二元Turbo码和Turbo乘积码都是在一些无线通信标准中得到广泛应用的纠错码.在Turbo码译码算 法的基础上,论文推导了双二元Turbo码的译码算法,分析了软输入软输出译码器的软信息统计值,通过仿真得到了终止迭代度量的门限值.并提出了一种根 据软信息值变化在Log-MAP和Max-Log-Map算法之间进行切换的自适应译码算法.该算法可以有效减少译码迭代次数,从而减小译码延迟并降低硬件复杂度 .另一方面,通过分析Turbo乘积码的译码错误原因,文中还给出了一种简化的基于随机交织的Turbo乘积码编码方法.该编码方法有利于增大乘积码的最小 码重和减少最小码重的码字个数,因此可以有效地降低Turbo乘积码的误码率,简化编码时的交织模式. 研究表明,交织器是Turbo码等纠错码中非常重要的组成部分.论文介绍了交织器的基本原理,并给出了一些比较重要的交织器类型和设计准则.同时 ,研究了一类基于整环上置换多项式的交织器,介绍了相关的数学理论和设计准则.特别地,针对三次多项式,得到了置换多项式的判别方法和较好的交织图 样,并证明这类交织器都是最大无冲突的,为进一步的理论研究和硬件实现打下了坚实的基础.为了在现有标准体系下实现高速Turbo译码,论文提出了一种 用于并行'Turbo译码的交织器存储方案,可以有效地防止存储访问冲突,从而可提高译码速率,并可以灵活地实现多种3GPP交织码长的片上配置. 论文的另一研究重点是针对一种特定的空时OFDM系统架构(GSTBCMIMO-OFDM),提出了一种迭代接收机的设计方案.借鉴Turbo原理的思路,此设计方案 结合了信道估计、MIMO解调与信道译码单元间的软信息交换,通过在三者之间交互外信息使信号检测更加精确.而且针对系统特点,采用EM算法等方法以减 少矩阵求逆操作的复杂度,有利于提高系统的可实现性.论文对影响迭代接收机性能的各个参数,如信道归一化多普勒频移、导频间隔、迭代次数等进行了 仿真,给出该迭代接收机的适用场合以及合适的接收机设置参数. 在MIMO-OFDM系统中,自适应传输技术也是亟待解决的关键技术之一.论文研究了基于奇异值分解的MIMO-OFDM系统的比特加载和功率分配问题;介绍了 基于SVD的MIMO-OFDM系统上的空频注水算法;研究了引入"平坦频率限制"假设的简化算法,研究了基于"平坦频率限制"假设的简化算法,并从理论上证明 "平坦频率限制"假设的合理性:利用信道矩阵奇异值排序统计特性,提出基于SVD的MIMO-OFDM系统的改进比特分配方案与相应算法.相比基于平坦频率限制 假设的算法,虽然该算法的运算复杂度有所增加,但可以明显减少功率损失,并且逼近最优注水方法的性能.同时还可以通过选择奇异值分类数量,使之在运 算量和性能之间进行折衷,具有一定的灵活性. 最后,论文进一步小结了所完成的研究工作和取得的一些成绩.并指出了MIMO-OFDM系统中其他一些关键技术进一步研究的方向. 6.期刊论文 李烜.宋文涛.罗汉文 基于比特交织和调制分集的Turbo乘积编码调制系统性能 -上海交通大学学报 2003,37(3) 将比特交织和调制分集引入到Turbo乘积编码调制中,提出一种具有良好抗衰落性能的编码调制机制.分析了该机制的误比特率性能,导出了适合迭代 译码的软输入软输出(SISO)度量算法,给出了一种简单有效的星座旋转角度设计方法.仿真结果表明,与传统Turbo乘积编码调制相比,该机制在瑞利衰落条 件下可获得2.5 dB以上的编码增益,为Turbo乘积码和高效调制结合应用于无线通信系统提供了良好的解决方法. 7.学位论文 赵肖 Turbo乘积码的仿真软件设计 2005 本文从理论和仿真的角度对Turbo乘积码的编译码方式加以研究。首先,分析了TPC的编译码原理。TPC的编码主要是由两个或两个以上线性子码的组 合构成一个矩阵,并对行和列分别编码。在编码中加入交织可以减少信道传输中的突发错误;译码采用的是软输入软输出并行迭代译码结构,在保持同 样的译码性能的同时降低了误码延时。在理论研究的基础上阐述了TPC系统软件实现的设计方案。本系统的TPC编码采用(64,57)×(64,57)的二维扩展 汉明码作为子码,信道码率为0.793;译码采用以扩展汉明码为子码的乘积码迭代译码,基于2次循环伪最大似然算法(Cyclic-2PML)。最后还给出了 TPC编译码的matlab软件流程图和仿真结果。 本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y1271798.aspx 授权使用:北京理工大学(北京理工大学),授权号:2c8a9cd3-30a8-4dc3-a723-9e2e0010ad82 下载时间:2010年11月14日
更多简介内容

评论

下载专区


TI最新应用解决方案

工业电子 汽车电子 个人电子
$(function(){ var appid = $(".select li a").data("channel"); $(".select li a").click(function(){ var appid = $(this).data("channel"); $('.select dt').html($(this).html()); $('#channel').val(appid); }) })