（计算机应用技术专业论文）80216e前向纠错编码的设计及其fpga实现.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重麽由e 电太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 虢互氢期：刁锄蝈 学位论文版权使用授权书 本学位论文作者完全了解 重麽邮电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重麽邮电太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者擗司舒 签字日期少罗年s 月、谓l 导师签名： 袋瞎穸 飙叮叮此明 重 摘要 提高数据传输的可靠性和有效性，一直以来都是计算机通信领域所追求的目 标。因此，一套优秀的纠错编码方案，是改善误码率，提高数据传输的可靠性的 必要手段，经过几十年的发展，已经出现了比较多的纠错编码算法，如海明码、 b c h 码、r s 码、卷积码和t u r b o 码等。 8 0 2 1 6 e 是针对移动性的无线城域网标准，其无线信道环境复杂而且具有很高 的数据传输率。为保障无线城域网提供更好的数据通信服务，在数据进入无线信 道前需要编码，优秀的纠错编码算法不仅能最大程度的纠正信道中出现的错误， 而且在增加冗余度的同时较少的影响数据的传输速率。基于这些要求，8 0 2 1 6 e 物 理层提供三种编码方案：级联的r s c c ( r e e d s o l o m o n - c o n v o l u t i o i l a lc o d i n g ) 、 b t c ( b l o c kt u r b oc o d i n g ) 、c t c ( c o n v o l u t i o n a lt 吡b oc o d i n g ) 。 本文通过分析比较，选择了实时性更高的r s c c 级联编码，因为该方案相比 另外的两种编码，在移动通信环境下更为实用。接下来详细的分析了r s ( 6 4 ，4 8 ，8 ) 截断码、参数为( 2 ，1 ，7 ) 的卷积码以及增加了交织编码的卷积码的纠错性能。分析表 明r s 码具有同时纠正突发错误和随机错误的能力，适用于数据通信和数据存储系 统的差错控制中；卷积码比较适合在噪声干扰严重的无线环境中。因此，本文将 r s 码作为内码，卷积码作为外码，联合交织编码构成纠错编码系统。 用f p g a ( f i e l d p r o g r a m m a b l eg a t ea 1 1 r a y ，现场可编程门阵列) 技术实现8 0 2 1 6 e 的前向纠错编码系统是本文的重点。f p g a 的优势是处理速度快，稳定性高，但设 计过程中需要充分考虑到时序。本文使用砧t e r a 公司的q u 枷si i 作为软件平台， c y c l o n ei i if p g a 芯片e p 3 c 2 5 q 2 4 0 c 8 n 作为硬件资源，设计并实现了在q m 1 6 调制方式下的前向纠错编码系统，该系统除了完成编码外，还设计了与删芯片 和d s p 芯片的通信接口，最后通过了8 0 2 1 6 e 基带系统的联合调试。 关键词。可编程逻辑门阵列，前向纠错编码，卷积码，级联 i m p r o v i n gt l l er e l i a b i l i t y 锄dv a l i d i t yo fd a t at r a n s m i s s i o ni st h em a i nt a 唱e ti nt h e f i e l do fc o m p u n i c a t i o na l ll o n g ，s oak i n do fe x c e l l e n te m 3 r - c o r r e c t i n gs c h e m ei sa n i m p o r t a n tm e t h o dt 0r e d u c em eb i te r r o rr a t e a r l de n h a n c em ea c c u r a c yo fd a t a t r a i l s m i s s i o n t h e r ch a v ee m e 唱e dm a i l yd i 髓r e n t e r r o r c o r r e c t i n ga l g o r i t h n s i i l a p p l i c a t i o n ，s u c ha sh 锄姗i n gc o d e ，b c h ，r s ，c c ，t 1 j r t l 0c o d e 锄ds oo n 8 0 2 16 ei sam o b i l es t a n d a r do fw m a n ，w h i c hh 嬲af e wc h a r a c t e r ss u c h 硒t h e c o m p l e x i 妙o fw i r e l e s sc h 锄e la n dg o o db 锄d 谢d t l l ，s ot l l ed e m a r l df o rc h a i l l l e lc o d ei s m o r er i g i d l yi ni t t h eg o o de r r o r c o r r e c t i n ga l g o r i t h i i ln o to n l yc 肌c o r r e c tt l l ee 盯o r s ， b u t 、v o u l d n ti i l 】f l u e n c em ed a _ t ar a t emt r a n s m i s s i o no b v i o u s l y t h e r ea r e l r e ec o d i n g s c h e m e si n8 0 2 16 e ：r s - c c ，c t c 锄db t c t i l ea n a l y s i so f “sp 印e rs h o w s l a t ，c o n c a t e n a t e dr s c ci sm o r ep r a c t i c a b l yi n w i r e l e s sc o m m u l l i c a t i o ns y s t e mb e c a u s eo fi t sc 蛔陬c t e r sr e l a t i v et oo t h e rt 、i 帕s r s ( 6 4 ，4 8 ，8 ) ，c c ( 2 ，1 ，7 ) 肌di n t e r l e a v ec o d ea r ea l s oa i l a l y s e de x p l i c i t l y ，锄di ti n d i c a t e s t l l a tr sc a nb eu s e di nv a r i o u se r r o r c o n e c t i n gs y s t e m sb e c a u s ei tc a nb o t l lc o r r e c t l e s t o c h a s t i c 肌db u r s te n o r s ，c ci sm o r ea d a p tt 0 叭r e l e s se n v i r o 眦e n tw h e nc h a n n e li s b a d s or si su s e d 弱i i l s i d ec o d e ，c ci so u t s i d ec o d ca n dj o i l l si n t e r l e a v ec o d et 0 c o n s t i t u t ea ne r r o 卜c o r r e c t i n gc o d i n gs y s t e m t i l ee m p h 嬲i so f “sp 印e ri st 0d e s i 印e 仃0 r c o r r e c t i n gc o d es y s t e mo f8 0 2 16 e l 塔i n gf p g a r a 研d n e s s 锄ds t a b i l i t y a r em em a i na d v 孤t a g e so ff p g a ，b u tt l l e d i m c u l t yi st l l ec l o c kd e l a ys h o u l db ec o n s i d e r e dc a r e 如l l y q l 塌r h 塔i i 觚dc y c i o n ei i i f p g ac h i po fa l t e r aa r eu s e d 嬲s o 脚e 强d h 砌、v a r ep l a t f o 肌r e s p e c t i v e l y 锄dt l l i s p a p e ri m p l e m e n tt h ef e cs y s t e mi nt l l em o d u l a t i o nm o d eo fq a m - 1 6i n c l u d i n gt l l e i n t e r f a c e s 诵t l la i t m 锄d d s p f i n a l l y ，t 1 1 es y s t e mp 勰s e st 1 1 ej o i n tt e s ti nt h et e s tb o a r d o f8 0 2 16 eb 嬲e b 锄ds y s t e m k e yw o r d s ：f p g a ，f o m 瑚r de m r - c o r r e c t i n g ，c c ，c o n c a t e n a t e n 重庆邮电大学硕士论文 目录 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 选题背景1 1 2 研究现状2 1 2 18 0 2 1 6 协议的研究与发展2 1 2 2 纠错码的研究现状3 1 3 论文主要工作5 1 4 论文组织结构一5 第二章纠错编码理论6 2 1 纠错编码概述6 2 2r s 码7 2 2 1r s 编码原理7 2 2 2r s 译码原理8 2 3 卷积码1o 2 3 1 卷积编码原理1o 2 3 2 维特比译码原理1 l 2 4 交织编码1 3 2 5 小结13 第三章8 0 2 1 6 e 前向纠错编码性能分析1 4 3 18 0 2 1 6 e 前向纠错编码参数1 4 3 1 1r s c c 级联编码参数1 4 3 1 2 交织编码参数16 3 2 纠错编码性能分析j 1 7 3 2 1r s ( 6 4 ，4 8 ，8 ) 码性能分析1 7 3 2 2 卷积码( 2 ，l ，7 ) 性能分析1 8 3 2 3 交织编码性能分析2 0 3 3 小结2 l 第四章f p g a 软硬件开发环境：2 2 4 1f p g a 2 2 4 2a l t e r a 开发环境2 3 4 2 1q 嘣u si i 软件平台2 3 i u 重庆邮电大学硕士论文 目录 4 2 2f p g a 芯片2 4 4 3a l t e r a 环境下的f p g a 开发2 5 4 - 3 1 开发方式2 5 4 3 2 时序控制2 6 4 3 3 开发流程2 7 4 4 ，j 、结2 8 第五章8 0 2 1 6 e 前向纠错编码系统的f p g a 设计2 9 5 1 系统结构2 9 5 2 接口的设计3 0 5 2 1f p g a 与a i 洲芯片的接口3 0 5 2 2f p g a 与d s p 芯片的接口3 3 5 3 编码部分的设计3 5 5 3 1 扰码的设计3 5 5 3 2r s 编码器3 6 5 3 3 卷积编码j 3 9 5 3 4 打孔4 0 5 3 5 交织4 1 5 4 译码部分的设计4 3 5 4 1 解交织4 3 5 4 2 填充。4 4 5 4 3 维特比译码4 5 5 4 4r s 译码4 8 5 4 5 解扰。5l 5 5 设计结果与测试5l 5 5 1 设计结果5 l 5 5 2 芯片测试5 2 5 6 小结5 3 第六章结论及未来的工作5 4 6 1 结论5 4 6 2 未来的工作5 4 致谢5 5 攻硕期间从事的科研工作及取得的研究成果5 6 参考文献5 7 i v 重庆邮电大学硕士论文 第一章绪论 1 1 选题背景 第一章绪论 随着用户对数据、语音、视频以及方便接入互联网的需求，计算机网络的宽 带化与无线化成为一个重要的发展趋势。近些年以来，宽带无线通信系统发展非 常迅速，以i e e e8 0 2 系列为基础的宽带无线接入标准化工作正在快速进行中，包 括无线局域网( w l a n ) 【1 1 、无线城域网( w m a n ) 、无线广域网( w w a n ) 、无 线个域网( w p a n ) 等，在这些宽带无线接入技术中，w l a n 在全球的发展最为 成熟，但由于覆盖的范围较近，对于用户随心所欲的无线接入需求非常有限，而 w w a n 还有待研究，相比前面的两种技术，w m a n 在5 0 l ( i i l 的地域范围内能够提 供更加成熟的宽带接入以及更好的移动性。 无线城域网泛指运营商在城市及郊区范围内提供多种业务的所有网络，它是 以宽带光传输为开放平台，通过各类网关实现语音、数据图像、多媒体、i p 接入 和各种增值业务及智能业务，并与各运营商长途网和p s t n 互通的本地综合网络。 w m a n 既可以使用无线电波也可以使用红外广播来传送数据，提供给用户以高速 访问i n t e m e t 的无线访问网络带宽。i e e e 成立8 0 2 1 6 工作组从事w m a n 的标准 化研究，其中，w i m a x ( w b r i d 、) v i d ei n t e r o p e r a b i l i t ) rf o rm i c r o w a v ea c c e s s ，微波接 入全球互操作性) 1 2 】用于基于i e e e8 0 2 1 6 的无线宽带接入设备的推广，目的是确 保不同宽带无线接入设备之间的兼容性和互操作性，w i m a x 已经成为了i e e e 8 0 2 1 6 标准的代名词，是一种面向城域网的宽带无线接入技术，能提供面向互联 网的高速无线接入。 基于i e e e8 0 2 1 6 技术的w i m a x 系统的优势主要有以下几个方面： 1 ) 覆盖范围广。w i m a x 网络的无线信号覆盖距离最远可以达到5 0 k i i l ，远 远超出了w l a n 信号的覆盖距离，因此只需要少量的基站就可以实现全覆盖，大 大扩展了无线网络的应用范围； 2 ) 数据带宽高。w i m a x 所能提供的最高接入速率是7 0 m b i t s ，这个速率是 3 g 所能提供的宽带速率的5 2 0 倍，w i m a x 采用o f d m 调制方式，每个频道的 带宽为2 0 m h z ，通过室外固定天线稳定地收发无线电波： 3 ) 广泛的多媒体接入服务。w i m a x 比w i f i ( 、矾r e l e s sf i d e l i t y ，无线保真) 技术具有更好的可扩展性和安全性，从而能够实现电信级的多媒体通信服务。其 中包括语音、数据、视频的传输。 2 ) 上，码长n = q - 1 的本原b c h 码称为r s 码。 r s 码的主要特点之一是码元取自g f ( q ) 上，而它的生成多项式的根也在g f ( q ) 上，所以r s 码是符号域和根域相一致的b c h 码。 7 重庆邮电大学硕士论文 第二章纠错编码理论 在有限域g f ( 2 m ) 上，对于纠正t 个错误的r s ( n ，k ) 码的参数如表2 1 所示： 表2 1r s ( n ，k ) 码参数 码长 信息位校验位字符长度( b i t ) 最小码距 最大纠错能力 nkn km2 t + 1t 码元符号取自有限域g f ( 2 m ) ，此时码元符号可以表示成相应的二元数组，因 此在有限域g f ( 2 m ) 上纠正t 个错误的r s 码的生成多项式为式2 ，2 ： g ( x ) = ( x 一口) ( x 一口2 ) ( x 一口列)( 2 2 ) 其中，0 【1 g f ( 2 m ) ，i = l ，2 ，2 t 。 生成多项式的幂次等于监督码元数，口的连续2 t 次幂就是多项式的根，指定 g ( x ) 的根为：a ，a 2 ，a 孔。 接下来，将以时域算法对r s 码编码【1 2 】，令待编码的信息码矢量为式2 3 ： 朋( 功= 【- l ，- 2 ，嬲，】 ( 2 3 ) 相应的信息元多项式为式2 4 ： 聊( x ) = 朋t l x 一1 + 一2 x 一2 + + 聊l x + ( 2 4 ) 令设编码之后的码矢量为式2 5 ： c ( x ) = q - l ，q 一2 ，q ，c o 】 ( 2 5 ) 相应的码元多项式为式2 6 ： c ( x ) = q l x ”- 1 + 巳一2 x ”一2 + + q x + c b ( 2 6 ) 把信息元多项式历( x ) 乘以x 巾k ，再将x n 。k m ( x ) 除以生成多项式g ( x ) ，其可以表 示为式2 7 ： ( x ”聊( x ) ) g ( x ) = 6 ( x ) + ，( x ) g ( x ) ( 2 7 ) 得到的余数多项式为校验多项式2 8 ： ，( x ) = i x ”一1 + l 4 - 2 x ”一一2 + + 乃x 2 + x + ( 2 8 ) 经过编码之后的码字多项式为式2 9 ： c ( x ) = x “一研( x ) + ，( x ) 编码之后的码矢量就是编码之后的r s 码，其中，前k 位是信息位， n k 为是校验位，编码之后的数据如式2 1 0 ： c ( x ) = 【i - 2 ，小i ，士2 ，i ，】 2 2 2r s 译码原理 ( 2 9 ) 后面的 ( 2 1 0 ) 与编码算法相比，r s 的译码算法比较复杂，需要的运算量也比较大。其中， 比较有代表性的算法是b m 算、法【1 3 1 和e u c l i d 算法【1 4 】，本文使用的是b m 算法。 重庆邮电大学硕士论文 第二章纠错编码理论 假设发送的码字c ( x ) 为式2 1 1 ： c ( x ) = e l x ”一1 + c 一2 x ”一2 + c 2 x 2 + c l x l + c o ( 2 1 1 ) 接收码字r ( x ) 为式2 1 2 ： r ( x ) = b l x ”一1 + r 一2 x ”一2 + 是x 2 + 玛x 1 + r ( 2 1 2 ) 设含有e ( e t ) 个错误的错误图样多项式e ( x ) 为式2 1 3 ： e ( x ) = e l x ”1 + 乜一2 x ”2 + 易x 2 + 墨x 1 + 毛 ( 2 1 3 ) 同时令e ( x ) 为式2 1 4 ： e ( x ) = x 五+ k k + 匕一l 置一l + e 鼍 ( 2 1 4 ) 其中x i 是第i 个错误的位置，并定义五= 口。，y i 是其对应的错误值。由上式， 则有式2 1 5 ： 尺( x ) = c ( x ) + e ( x ) ( 2 1 5 ) 译码算法的过程为： 1 ) 从接收序列计算伴随式s j ( j = 1 ，2 ，2 t ) 。 把口( j = l ，2 ，2 t ) 分别代入多项式r ( x ) 得到式2 1 6 ： s i = r ( 口) = r 。i ( 口) 小1 + r 。- 2 ( 口) 帕+ r 2 ( 口) 2 + r l 口+ r o ( 2 1 6 ) 又由式2 1 7 ： 尺( 口o ) = c ( 口o ) + e ( 口) = e ( 口。) ( 2 1 7 ) 所以得到式2 1 8 ： s ，= r ( 口7 ) = e ( 口) = e l ( 口7 ) ”1 + e 一2 ( 口7 ) 扣2 + + 巨口7 + 扇 ( 2 1 8 ) 建立方程组式2 1 9 ： s = x 五+ k 五+ z 一。五一。+ r 置 岛= x ( 五) 2 + k ( 五) 2 + r l ( 置一t ) 2 + z ( 工y ( 2 1 9 ) 逆，= k ( 互) 2 + k ( 五) a + z l ( 置一1 ) 2 + z ( x 。) 2 2 ) 由伴随式s j0 = l ，2 ，2 t ) 计算错误位置多项式o ( x ) 。 直接求解方程组2 1 9 比较复杂，在由伴随式s i 寻找错误图样e ( x ) 时，可先确 定错误位置x i ，再求错误值y i 。将方程组转换成线性方程组，用错误位置多项式 盯( x ) 来求解，则将使求解变得容易实现。错误位置多项式仃( x ) 定义为式2 2 0 ： l 仃( x ) = ii ( 1 一x 一) = l + q x + + q x ( 2 2 0 ) - l r 若是第i 个错误位置x = x ，一，则仃( z 。) = o 。因此将求解方程组转换为求解 错误位置多项式仃( x ) 的根。求解盯( x ) 的根的推导过程详见文献【”】。 3 ) 用c h i e n 搜索法寻求错误位置。 为了确定错误位置多项式盯( x ) 的根，确定错误位置，可以用c h i e n 搜索法【1 6 】 9 重庆邮电大学硕士论文 第二章纠错编码理论 来寻找。设尺( x ) = r l x + 兄一2 x ”2 + 恐x 2 + 蜀x 1 + r ，要检验第一位r n 1 是否错 误，相当于要检验a 加1 是否为错误位置数，或者说相当于检验a 卜n 是否为盯( x ) 的根。 所以在得到盯( x ) 以后，为了译出色- i ，译码器首先计算口，口：口2 ，口，然后计 算它们之和是否为1 。若是，则矿以是错误位置数，k 1 错误；否则，心i 正确。 4 ) 计算错误值y i 。 得到错误位置x i 之后，根据线性方程组x i y i = s i ( i - 1 ，2 ，2 t ) ，代入即可直接求 出y i 。 5 ) 计算错误值，将误码加以纠正。 将得到的错误值加到相应的错误位置上，即可以得出译码结果c ( x ) 。 2 3 卷积码 卷积码是1 9 5 5 年由e l 协发明的，通过异或运算使得信息码之间产生相关性， 增大信息码之间的码距，从而使得编译码具有纠错能力。由于卷积码的编码过程 充分利用了码字间的相关性，因此在码率和复杂性相同的条件下，卷积码的性能 要优于线性分组码。 2 3 1 卷积编码原理 卷积码是一个有限记忆系统，它将信息序列切割成长度为k 的一个个分组， 与分组码不同的是，卷积码中编码后的n 个码元不仅与当前分组的k 个信息有关， 而且也与前面m 个分组的信息有关。由于码字的产生一共受到m + 1 个信息分组的 制约，因此将l = m + l 称作约束长度。卷积码常用如( n ，k ，l ) 的形式表示，其中n 是 码长，信息位为k ，约束长度为l 。约束长度之所以以分组为单位而不以码元数为 单位，是因为编码和译码的时候，相关分组数一定而码元数不同，编码时，相关 的码元数是( m + 1 ) k ；译码时，相关的码元数是( m + 1 ) n 。 卷积码的常见的参数见表2 2 。 表2 2 参数为( n ，l ( l ) 的卷积码 输入( b i t )输出( b i t ) 速率记忆长度约束长度 knl ( nml = m + l 卷积码一般有三种描述方式：多项式矩阵表示法，标量矩阵表示法和移位寄 存器表示法。在硬件设计过程当中，最常用的要数移位寄存器表示法。 卷积码的编码相对比较简单，图2 2 是参数为( 2 ，l ，3 ) 卷积码的状态转移图。其 中，a ，b ，c ，d 分别对于移位寄存器右两位的四种状态：0 0 ，0 l ，l o ，1 l ，实线 1 0 重庆邮电大学硕士论文 第二章纠错编码理论 表示输入“o ”时的状态转移，虚线表示输入“l 时的状态转移， 状态转移时的编码输出，其生成多项式为式2 2 l ： g = 【z 2 + 1 ，x 2 + x + 1 】 b 线上的值表示 ( 2 2 1 ) 图2 2 ( 2 ，l ，3 ) 卷积码的状态转移图 图2 3 参数为( 2 ，l ，3 ) 卷积码的截断网格图。其中j 表示时间深度，l 为对j 的截 断深度。从图2 2 和图2 3 都可以看出，若输入的信息流为1 1 0 1 0 0 ，编码之后输 出为1 1 1 0 1 0 0 0 0 1 1 1 。 345678 图2 3 ( 2 ，l ，3 ) 卷积码的【，- 6 截断网格图 2 3 2 维特比译码原理 卷积码的译码比较复杂，因此，对于卷积码的研究一直是围绕如何去寻找好 的编译码方法进行的。其中，1 9 6 7 年由维特比( t e r b i ) 提出的t e r b i 算法【r 7 】是 研究的最广泛的算法。 v i t e r b i 算法是一种基于码的网格图基础上的一种最大似然译码算法，是一种最 佳的概率译码算法。目前最流行也是最重要的卷积码译码算法，当码的约束长度 较小时，t e r b i 算法比序列译码算法效率更高、速度更快。 重庆邮电大学硕士论文 第二章纠错编码理论 在图2 3 中，假设收到的信息流为i p 【1 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 】。若对信息流进行维特 比译码，就需要找出6 4 个码字中与r 的汉明距离最短的那个码作为译码输出。而这 些码字正好对应图中的6 4 条路径。将图2 3 线上的标注转换为原标注与对应的r 的值 之间的汉明码距就可以得到图2 4 的网格图。 这样译码的过程就转换为求所有路径中的最短路径了，假设从a o 到a 8 的最短路 径p 经过某个中间结点x ，p l 和p 2 分别表示从a o 到x 、x 到a 8 的路径。显然p l 是从a o 到x 的最短路径，t e r b i 译码的方法就是：对于每个深扇，找到从a o 至f j j 级的每个节点 的最短路径列表，则a o 到( i + 1 ) 级的最短路径列表很容易从上一级得到，所以。深度 为( i + 1 ) 的最短路径只需要将深度j 最短路径往前延伸一个支路就可以得到。 图2 4 ( 2 ，l ，3 ) 卷积码网格图另外一种形式 假设s 表示状态集 a ，b ，c ，d ) ，如果s ，f s ，并且状态可以直接从s 转到t 或者t 转到 s ，则定义b ( j ，) 来表示此时的输入信息：若状态从s 转到t ，编码器输入信息为0 ， 则j 6 f ( j ，f ) = 0 ，否则，b ( j ，) = l 。若s 和t 之间的状态不能直接转变，则b ( s ，r ) 就没有 定义。同样，定义，( s ，f ) 是网格图中连接s j 1 和1 ；i 支路上的标注。如果不存在这条支 路，定义，- l ( s ，) = 。 t e r b i 算法首先需要计算两个量：测度和幸存路径。测度；( s ) ，s s ，表示从a o 到s i 最短路径的长度；保留路径b ，( s ) = 是一个长度为j 的二进制字符串，记录了从 a 0 到s j 的最短路径。如鼠( 6 ) = l o l 0 表示从a o 到b 4 的最短路径是a o c l b 2 c 3 b 4 。 v i t e r b i 算法的译码过程为： 1 ) 设定初始值：鳓( a ) 卜0 ，对所有s a ，有鳓( s ) = 佃。且鼠( a ) = a ，= 1 。 2 ) 对任意s s ，找出一个t s ，使，1 ( ，) + ，- i i ( ，s ) 的值最小。然后设 ，( s ) 卜，一l ( f ) + ，i j ( ，s ) ( 2 2 2 ) 曰，( s ) 一b - i ( ，) 0 b ( f ，s ) ( 2 2 3 ) 3 ) 如果= 上+ m ，输出口，( a ) 的前l 比特并停止；否则，令卜+ l ，回到2 ) 。 从上面过程可以看出，译码的时候首先从接收序列中确定的码序列，并使它 和原发送序列的匹配概率最高。它由距离修改和回溯【l8 】两个部分组成。在距离修 改部分中，对基于当前输入符号的所有状态概率都要累加。通过网格图，一旦确 1 2 重庆邮电大学硕士论文第二章纠错编码理论 定路径，追溯跟踪部分就重构数据。 参数为( 2 ，l ，7 ) 的卷积码由于约束长度比较长，需要6 4 个状态，因此难以用网格 图的方式描述，但其原理是( 2 ，l ，3 ) 的卷积码的推广。 2 4 交织编码 在衰落信道中，差错往往是突发性【1 9 】的，一个突发差错将引起一连串错误， 这时纠正独立差错的信道编码，就显得无能为力，因为连续误码个数超过了他的 纠错能力。若要纠正多个误码且不限于一次突发的突发性差错，通过改变信号的 编码状态将原来属于突发差错的有记忆信道改变为基本上是独立差错的随机无记 忆信道，并保证原有的各类用于无记忆信道纠正独立差错的信道编码仍可正常使 用，这就是交织编码技术。 交织主要有两种：分组交织和卷积交织。本文只讨论分组交织，其一般原理 是：交织是将输入信息序列按行写入一个m n 矩阵中，然后按列读出。编码数据 经交织器重新排序以后在信道上传输。解交织是交织的逆变换，是在接收端解调 以后将接收到的信息也存放到m n 的矩阵中，然后按行读出。 由于交织解交织的效果，突发错误在时间上被扩展，于是每个码字上的错误 显得独立了。对给定的一个【n ，k 码，通过分组交织变成一个 m n ，m k 】码，即将 码长和信息元扩大了m 倍，通常定义交织度为i ( i = m ) 。显然，当且仅当每行中的 错误图样是原码中可以纠正的错误图样时，该错误图样对整个阵列来说才是可以 纠正的。长度为m 的突发错误无论从哪一位开始，都至多影响每行中的一位。因 此，若原码能纠正长度为t 或者更短的任何单个突发错误，则交织码将可以纠正长 为m t 或更短的突发错误。如果【n ，k 】码具有最大可能的纠正突发错误的能力，则 交织后的【m n ，m k 】码也具有最大可能的纠正突发错误的能力。 在实际的通信系统中，交织编码技术常常是跟分组码、卷积码同时工作的。 2 5 小结 本章是课题设计前的理论基础，首先介绍了纠错编码的种类，和纠错编码一 些基础码，接下来重点从理论上介绍了与本文密切相关的r s 编译码、卷积码、维 特比译码和交织编码。 重庆邮电大学硕士论文 第三章8 0 2 1 6 e 前向纠错编码性能分析 第三章8 0 2 1 6 e 前向纠错编码性能分析 3 18 0 2 1 6 e 前向纠错编码参数 i e e e8 0 2 1 6 e 定义了三种物理层规范，分别是基于s c ( s i n g l ec a 玎i e r ，单载 波) 、o f d m 和o f d m a ( o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l ea c c e s s ，正交频 分复用多址) 【2 0 】的调制方式。由于o f d m 调制可以有效抵抗无线信道的多径衰落， 因此基于o f d m 或o f d m a 的物理层技术被广泛用于低于1 1 g h z 的非视距环境 下。本文采用的是基于o f d m 的物理层技术，在o f d m 调制模式下，所采用的纠 错编码方案为基于r s c c 的级联编码和交织编码。 3 1 1r s c c 级联编码参数 r s c c 级联编码是以r e e d s o l o m o n 作为外码，速率相适配的卷积码作为内码， 当编码的时候，块状数据经过第一个r s 编码器编码后，将通过一个初值为0 的卷 积编码器。 系统r s 码( n - 2 5 5 ，k - 2 3 9 ，仁8 ) 使用g f ( 2 8 ) 导出r e e d s o l o m o n 编码。 r s ( 2 5 5 ，2 3 9 ，8 ) 的生成多项式如式3 1 ： g ( x ) = ( x + 口o ) ( x + 口1 ) ( x + 口2 一1 ) ，口= 0 2 腿r ( 3 1 ) 域多项式为式3 2 ： p ( x ) = x 3 + x 4 + x 3 + x 2 + 1 ( 3 2 ) 为了适应不同的块长度和不同的纠错能力，码字可以被缩短和收缩。当块的 数据字节数短至k 时，要增加2 3 9 k 个零字节作为前缀，这些零字节将在编码后 被丢弃。当需要对t 个字节进行纠正时，应收缩码字，并仅使用总共1 6 个奇偶校 验字节中的第一个2 t 字节。比特字节转换时m s b ( m o s ts i 弘i f i c 锄tb i t ，最高有 效位) 优先。 经过r s 编码后的数据，在卷积编码前需要进行并串转换，将8 位的并行数据 转化为比特流。二进制卷积编码器对该比特流进行编码，卷积码采用的编码参数 是( 2 ，l ，7 ) ，约束长度等于7 ，编码率为1 2 。l 2 编码率的卷积码编码是一个串行的 比特输入x ，两个并行的串行输出端x 和y 。 卷积码的生产多项式系数为： 对于x ：g l = 1 7 l o c t 或g i = 1 1l l 0 0 1 2 1 4 重庆邮电大学硕士论文 第三章8 0 2 1 6 e 前向纠错编码性能分析 对于y ：g 2 = 1 3 3 0 c t 或g 2 = 1 0 1 1 0 1 1 2 为降低数据的冗余度，一般会在c c 后进行数据打孔。表3 1 列出了为实现不 同码率而使用的收缩模式和串联顺序，其中，“l 表示发送比特而“0 ”表示删除 比特。 表3 1 带缩短配置的内部卷积编码 编码率 速率 l 22 33 45 6 xl1 01 0 l 1 0 1 0 1 yl l l1 l o1 1 0 1 0 x y x l y lx i y l y 2 x l y l y 2 x 3x l y l y 2 x 3 y 4 x 5 块状数据经过第一个r s 编码器编码后，将通过卷积编码器。0 x o o 尾字节应 在随机化后附在每个突发的末尾。r s 编码器中，冗余比特在输入比特前进行发送， 并在分配数据块的末尾保留0 x o o 尾字节。为了保证卷积编码器能被n 。b p 。整除后 的比特数，在进入编码器前，0 填充比特被加到末尾o 比特后面。0 填充比特不 应进行随机化。需要注意的是，这种情况仅发生在子信道化模式中，而且不应使 用r s 编码。 在不同的调制模式下，需要采用不同的参数进行编码，表3 2 列出了不同调 制方式和编码率的块长度和编码速率。 表3 2 不同调制方式下的编码 序号调制方式未编码块长度编码块长度总编码率r s 码c c 码率 ( 字节)( 字节) lb p s k1 22 4l 2 ( 1 2 ，1 2 ，o ) 1 2 2 q p s k 2 44 8 l 2 ( 3 2 ，2 4 ，4 ) 2 3 3 q p s k 3 64 83 4 ( 4 0 ，3 6 ，2 ) s 1 6 4 1 6 一q a m 4 89 6l 2 ( 6 4 ，4 8 ，8 ) 2 3 5 1 6 一q a m 7 2 9 6 3 4 ( 8 0 ，7 2 ，4 ) 5 6 6 6 4 - q a m 9 61 4 42 3 ( 1 0 8 ，9 6 ，6 ) 3 4 7 6 4 q a m 1 0 81 4 43 4 ( 1 2 0 ，1 0 8 ，6 ) s | 6 本文是对表3 2 中序号为4 的编码方式的分析和设计，其调制方式是1 6 q a m 。 对于一块4 8 字节的原始数据，经过r s c c 编码之后，得到9 6 字节的编码块。 重庆邮电大学硕士论文 第三章8 0 2 1 6 e 前向纠错编码性能分析 3 1 2 交织编码参数 经过r s c c 级联编码后的所有数据比特均应经过块交织器，交织器的块尺寸 与每个被分配的子信道上、每个o f d m 符号的编码比特数n c b p 。相一致。交织器由 一个两步骤的排序处理来确定。第一步确保相邻编码比特映射到不相邻的子载波 上。第二步保证相邻编码比特交替映射到星座的低或高比特位上，这样可避免长 期使用不可靠的比特。 n 。b p 。是每个子载波上的编码比特数，b p s k 、q p s k 、16 - q a m 或6 4 - q a m 分 别为l ，2 ，4 或6 。设s = c e i l ( n 。b p 以) 。在n c b p 。比特的发送块中，假设k 是编码比 特经过排序第一步前的序列号；m k 是编码比特经过排序第一步但未经过第二步时 的序列号；j k 是编码比特经过排序第二步但未经过调制映射时的序列号。 式3 3 、式3 4 分别定义了排序的第一步和第二步。 = ( 札细d ) 毛。o d l 2 + b d ，( 七d ) ，七= o ，1 ，札呐一1 ，d = 1 6 ( 3 3 ) 五= s b d ，( 肌i s ) + ( 朋i + 0 细一夕b d ，( d 么声) ) 。d ( ，) ，七= o ，1 ，7 0 一l ，d = 1 6 ( 3 4 )