（电路与系统专业论文）高速无线寻呼系统信道译码的研究与实现.pdf

摘要 随着我国移动通信事业的迅速发展，我们迎i i 受研究学握其巾的戈键技 术，丌发出捌有自主知识产权的产品。信道编码技术是移动通信系统的关键技术 之。本文介绍了f l e x 高速无线寻呼系统中的笠锵控制编码技术以及b c h ( 3 2 ，2 1 ) 纠错码的构成和译码方法，重点讨论了f l e x 高速寻呼解码芯片的 f p g a 设计与实现。该设计采用自顶向下的设计方法，刈f l e x 解码系统进行 功能层次上的划分，系统主要包括：物理层处理模块，数掘链路层处理模块，解 码及纠错模块，以及数据接收和发送模块。设计的b c h 解码器采用了m c u 的 基本框架，译码器结构简单，译码速度快。整个系统在x i l i n x 公司的f o u n d a t i o n 3 1 i 软件平台上采用v h d l 语言进行描述，并完成了系统仿真。 关键词：f l e x 差错控制交织b c h 码f p g av h d l a b s t r a c t w i t ht h ed e v e l o p m e n to fm o b i l ec o m m u n i c a t i o n s t u d i n gt h ek e yt e c h n o l o g a n dd e v e l o p i n gt h ep r o d u c t s 、 i t hi n d e p e n d e n ti n t e l l e c t u a lp r o p e r t y h a v eb e c o m ea n e ws u b j e c ti nn a t i o n a li n f o r m a t i o ni n d u s t d c h a n n e lc o d i n gi so n eo ft h ek e t e c h n o l o g yo f m o b i l ec o m m u n i c a t i o n t h i sp a p e rd e s c r i b e st h ee r r o rc o n t r o lc o d i n go f t h ef l e xp a g i n gs y s t e m w i t he m p h a s i so nt h ed e s i g na n di m p l e m e n to ft h ef l e x d e c o d e rc i r c u i tb ym e a n so ft h ef p g at e c h n o l o g y t h ef l e xd e c o d e rd e s i g n e di nt h i sp a p e ri n c l u d e st h ep h y s i c a ll a y e rb l o c k t h e d a t el i n kl a y e rb l o c k t h eb c hd e c o d e ra n dt h es p ii n t e r t h c ec i r c u i t t h e c o n f i g u r a t i o no fm c u i sa d o p t e di nt h ed e s i g no ft h eb c hd e c o d e r w h i c hm a k et h e b c hd e c o d e rh a ss i m p l es t r u c t u r ea n dh i g hd e c o d i n gs p e e d a l lo ft h ec i r c u i t sa r e d e s c r i b e db yv h d la n ds i m u l a t e do nt h ef l a to ff o u n d a t i o n3 1i w h i c hb e l o n g st o t h ex i l i n xc o m p a n y k e y w o r d ： f l e x ，e r r o rc o n t r o l ，i n t e r l e a v i n g ，b c hc o d e f p g a ，v h d l + j ：i 航。航人人j ：f i l i ! t 、j ：。f ? ，| 文 概述 一、f l e x 高速寻呼系统及其差错控制技术 f l e x 寻呼编码是m o t o r o l a 公司在1 9 9 3 年6 月公m 】的一个多速率、令同步、i i i 性能的寻呼协议。是当d “全球寻呼系统采用的主要标准( 传输速率为2 4 k b p s f 内 p o c s a g 、6 2 5 k b p s 的e r m e s 及目前最新的f l e x 吣议) 之一。f l e x 寻呼编码的 提出是为了解决低速寻呼系统运营中出现的一些问题，与p o c s a g 和e r m e s 斗t l 比， f l e x 在系统容量、电池寿命、速率及与现有系统兼容性方面均有突出的表现。1 9 9 6 年1 月，中国邮电部决定进行全国高速无线寻呼网的建设并采用f l e x 寻呼编码作 为系统编码格式。1 9 9 7 年1 0 月1r 丌通的覆盖全国的高速寻呼网1 9 8 1 9 9 采用了卫 星联网、f l e x 编码及多频漫游技术，现已开通2 9 1 个城市。 在有扰信道中为提高数据传输质量，普遍采用差错控制技术，即信道编码。常用 的信道编码有：前向纠错( f e c ) 、检错重发( a r q ) 和混合纠错( h e c ) 。由于寻呼信道是 单向信道，故只能采用f e c 。 在许多同时出现随机错误和突发错误的复合信道上，如短波、对流层散射等信道 中，往往发生一个错误时，波及后面一串数据，导致突发误码超过纠错码的纠错能力， 使纠错能力下降。因此，编码技术只有与数字交织技术相结合，才能取得良好的效果。 交织的主要作用就是将原始数据序列打乱，使得交织前后数据序列的相关性减弱，这 样做很突出的一个优点便是大大降低了数据突发错误的影响。实际使用中，在信号发 送端纠错编码器后接数字交织单元，接收端解调后接解交织器，通过交织、解交织电 路的作用，将突发错误信道改造成独立的随机错误信道，使突发错误散布在纠错编码 器纠错范围之内，以提高信道纠错能力。f l e x 寻呼编码采用前向信道纠错编码和数 字交织技术，大大提高了信号的抗衰落能力。 本文主要研究在f l e x 高速无线寻呼系统中信道译码的方法和接收机中差错控 制的硬件实现，重点是b c h 码译码器和解交织器的f p g a 设计与实现。 二、a s i c 设计 现代电子产品的复杂度日益加深，一个电子系统可能由数万个中小规模集成电路 构成，这就带来了体积大、功耗大、可靠性差的问题，解决这一问题的有效方法就是 采用a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t s ) 芯片进行设计。a s i c 按照设计方法 的不同可分为：全定制a s i c ，半定制a s i c ，可编程a s i c ( 也称为可编程逻辑器件) 。 可编程a s i c 由于具有用户可编程的特性，使得电子系统的设计工程师利用与器件相 应的c a d 软件，在办公室或实验室里就可以设计自己的a s i c 器件因此发展特别 迅速，自七十年代以来经历了p a l 、g a l 、c p l d 、f p g a 几个发展阶段，其中 c p l d f p g a 属高密度可编程逻辑器件，集成度已超过百万门。 集成电路设计已进入片上系统( s y s t e mo na c h i p ) 的时代c p l d 和f p g a ( 尤 l 迷尤线 r 系统信道l 牛_ _ l i l ! j 川7 io 爻j 见 其是f p g a ) 的结构和规模也都一u 以满足芯片内集成系统的要求，凶此朵川仃系统 级性能的c p l d f p g a 实现可编程片上系统也是“# 发展的个弧要技术。 近十年来，电子信息类产r 怙的丌发出现了两个i j 娃的特点：一足，。仙的复杂稚眨 加深，二是产品的上市时限紧迫。因此基于门级描述的传统设计方法已4 ：能适应新的 形势，一种系统绒的设计方法应运而生。采用系统级设计技术，设汁人员无颁j l 亘过1 “j 级原理图描述电路，而是针对设计目标进行功能拙述，通过软件丌发一f ：具完成硬什i 乜 路的实现，大大缩短了产品的研制周期。不仅如此，系统缎设汁可以只定义系统的行 为特性，不涉及实现工艺，在厂家综合库的支持下，利用综合优化工具可以将高层次 描述转换成针对某种工艺优化的网表，工艺转化变得轻松容易。 系统级设计步骤如下： 1 按照“自顶向下”的设计方法进行系统划分。 2 输入h d l 代码，这是高层次设计中最为普遍的输入方式。此外，还可以采用 图形输入方式( 框图，状态图等) ，这种输入方式具有直观、容易理解的优点。 3 将以上的设计输入编译成标准的h d l 文件。对于大型设计，还要进行代码级 的功能仿真，主要是检验系统功能设计的下确性，因为对于大型设计，综合、适配要 花费数小时，在综合前对源代码仿真，可以大大减少设计重复的次数和时间。 4 利用综合器对h d l 源代码进行综合优化处理，生成门级描述的网表文件，这 是将高层次描述转化为硬件电路的关键步骤。综合优化是针对a s i c 芯片供应商的某 一产品系列进行的，所以综合的过程要在相应的厂家综合库支持下才能完成。综合后， 可利用产生的网表文件进行适配前的时序仿真，仿真过程不涉及具体器件的硬件特 性，较为粗略。 5 利用适配器将综合后的网表文件针对某一具体的目标器件进行逻辑映射操作， 包括底层器件配置、逻辑分割、逻辑优化和布局布线。适配完成后，产生多项设计结 果：适配报告，包括芯片内部资源利用情况，设计的布尔方程描述情况等：适配 后的仿真模型：器件编程文件。根据适配后的仿真模型，可以进行适配后的时序仿 真，因为已经得到器件的实际硬件特性( 如时延特性) ，所以仿真结果能比较精确地 预期未来芯片的实际性能。如果仿真结果达不到设计要求，则需要修改v h d l 源代 码或选择不同速度品质的器件，直至满足设计要求。 6 将适配器产生的器件编程文件通过编程器或下载电缆载入到目标芯片f p g a 或c p l d 中。如果是大批量产品开发，通过更换相应的厂家综合库，可以很容易转由 a s i c 形式实现。 按照自顶向下的设计方法，f l e x 解码器的顶层设计可划分为4 个模块：数据接 收和发送模块、物理层处理模块、数据层处理模块、解码及纠错模块。各模块均采用 v h d l 语言没计实现。 三、f l e x 解码芯片的研究意义 f l e x 寻呼协议标准是美国m o t o r o l a 公司的一项专利性协议。在中田邮电部与 m o t o r o l a 公r 可签署的叶r 1 # 人比共 i 惦i i l i | 5 i u 部与胯托岁 t 公ij 疋j t ：- 述、呼技术合f 1 。 谅解备忘录中舰定：中国高速寻呼网络采用f l e x 编码i l j f | ，i j r 【乍产f l e xi f ? j 述 寻呼机及其解码芯片在国内使用，不需向m o t o r o l a 公- 日交纳擘利使j u 册。m q 已建成了高速寻呼全国网，但幽内还没有厂家生产高速；j 呼衅卵 芯片。现在国内的 f l e x 解码芯片全部依赖于进口，没有自主的知u 产议受制j 一人，7 “品的成本较f ；。 。 本课题是江苏省信腾高科技发展有限责任公司的个合作丌发i i j 的重要滞分， 1 的 是用f p g a 实现f l e x 解码器的功能，为丌发出钏订自二1 二知1 u 产十义的f l e x 高速寻呼 解码芯片打下基础，并为今后进行其它产品的研究1 ：发秘祟经验。 第一章寻呼系统中的差错控制 1 1 差错控制系统和纠错码分类 在工程实践中并不存在理想的数字信道，信号，【：备种媒体的传输过程巾总会产，l 畸变和非等时时延，对数字信号来激就意味着产7 i 三误鹏羊| j 抖动，而抖动的墩终结粜也 反睦在系绞豹漩鹃上，信号的失爽滋戴两产生。为了掇赢三菹箍豹可靠蛙，黪逡采羽差 错控制技术，瑟秀鼋疆的信道编礴。 1 1 1 差错掇制方式 数字通偿系统中，剩用纠错残梭错码进行差错掇制的基本方式大致分为四类： 嚣淘錾链( f e c ) ；重簧反续( a r q ) ；漫舍终锩( h e c ) 秘售怠反镶( i r e ) 方式。 出于寻呼信邋慰蕈向信道，故只髓采用f e c ，其系统模整如图l l 所示。 为各部 分的输出序列。 重n ( 0 干扰、罐声 蹦1 - lf e c 的系统模刑 采用f e c 方式不需要反馈储道，发送端发送能够纠错的码，接收端收到这些码 后，通过纠错泽妈器自动地纠正传输中的错误，译码的实时性好。缺点怒译码比较复 杂，j 秀选用熟绸错鹃必须与信遭予撬情嚣握匹配，霹聪蹲信遂交纯豹逶疲镶爰。为了 获褥跑铰低纳谟鹃率，往往以最鞴的信道条件柬设诗纠错码，敖所瘸绸镶鹕的冗余度 比较大，导致编码效率降低。 1 1 2 纠错码分类 寻簿系绞中绸错编舀赘最主要熬嚣豹是纠锘，毽强国堍超过绸镑藐力熬错误露应 给出指示，郎筑够检错，且要求枪镨能力总是大于纠锚能力。通常按以下方式一- 。：4 。t h 5 1 = 码进行分类。 一、按照对信源编码的输出序列处理方式的玎：i 司，分为分组码与卷积码两大类。 分组码邈把信息序列以每k 个码元分组，通过编硝器把每组k 个信熙元按一定 胤律产! l ! r 个多余码元( 称为校验7 或舱督兀) ，输【乇为n = k + r 的。个： ( 组) 。 短一码组的r 个校验元仅与本组的信息，仃天，m 1o 刚纠【几天。分组弼刖( n k ) 表_ ：， n 表示码长，k 表示信息位数目。r = k n 称为分自l 们的编放：年，简称码；缸，表示信 息组在码字中所占的比重，它是衡量分组码有效f - ( f f j1 个j 占小参数。分组码f 】按照码 的结构特点，又可分为循环码与非循环码。卷积码足将信息睁列以k o 个码元分为一 段，对每段k 0 长的信息组以一定的规则增力r 产n 0 k 。个佼验元，自l 成长为n o 的码段， 但( n o - k o ) 个校验元不仅与本段的信息组有关，日与胁m 段的信息组有关，r = k 。n 。 仍为码率，另称n c = n o ( m + 1 ) 为卷积码的码约束长度。卷积码的洋码往往比分组码复杂 得多，在已经应用的一些寻呼系统中，几乎都是采斤j 分组码。 二、根据校验元与信息元之间的关系分为线性码与非线性码。 若校验元与信息元之间的关系是线性关系( 满足线性迭加原理) 则称为线性码。 如校验方程中，信息元与校验元之问的关系为非线性关系，则称为非线性码。 三、按照纠j 下错误的类型可分为纠正随机错误的码和纠f 突发错误的码，以及既 能纠f 随机错误又能纠正突发错误的码。 误码是受干扰和噪声的影响而引起的。在寻呼应用中，既可能遇到随机干扰，又 可能遇到突发干扰，因此在设计纠错时最好考虑到这两种因素。由于随机干扰的可能 性更大，故在目前的寻呼系统中以纠随机错误为主，但一些新推出的寻呼系统已经考 虑到这两种因素，其编码方法已能既纠随机错误又纠突发错误。表1 1 列出了目前几 种典型的寻呼系统的纠错编码的情况。 表1 - 1 几种典型的寻呼系统中使用的纠错编码 特性p o c s a g s c ( 美r d s ( 瑞典) f l e xe r m f sa p o c g国1 编码类型扩展g o l a v k a s a m i ( 2 6 1 6 1 截 扩展b c h ( 3 2 ，缩鲁j 和艟打展b c h ( 3 2 ，2 1 ) 或缩 b c h ( 2 3 ，12 )短循环码2 1 1 发8 垂交织 b c l l ( 3 0 i8 ) 缸b c h ( 2 8 1 8 1 技按帧交 ( 3 2 2 1 )，土9 垂交织 织 汉i 卿距离 673666 编码效率 06 605 206 206 606 606 6 系统码速5 1 2 ，1 2 0 03 0 0 ，6 0 0 l l8 75 1 6 0 0 ，3 2 0 06 2 5 01 2 0 0 2 4 0 0 3 2 0 0 ：# ( b p s ) ，6 4 0 04 8 0 0 1 6 4 0 0 ：i 述七线、j 丁；系统f 1 ；, 2 1 【t 旧t , i t i 艾j m 1 2 线性分组码 1 2 1 基本概念 一个( n , k ) 分组码，表示码组长为n ，其中有k n 化信息元，n k 个校验7 。长 为n 的所有二进制组( 或称n 重) 共有2 “个，但长为k 1 ：j 信息组共有! o 个，而分组 编码其实就是以一定的规则从2 “个n 重中挑选出2 。个n 重，使2 。个信息组与2 0 个n 重之剧建立一一对应关系，这2 。个n 重组成了一个( n 、k ) 分组码。因此称这2 “个n 重为许用码组，简称码组或码字，而其余的( 2 “- 2 。) 个n 重为禁用码组。 如果任一个( n ，k ) 分组码，信息元和校验元之问的关系为线性的，则称为线性 分组码【3 】| “，否则称为非线性码。( n , k ) 码的每一个码字有n k 个校验元，要从k 个 信息元中求出n k 个校验元，必须有n k 个独立的线性方程，根据求校验元的不同线 性方程，就得到不同的( n , k ) 分组码。以( 7 ，3 ) 码为例，设三个信息元为c 6 , c 5 ，c 4 ，四 个校验元为c 3 , c 2 , c l ，c o ，可根据以下四个线性方程求校验元。 c 2 = c 6 + c 5 + c 4 c l = c 6 十c s c 02 c5 + c 4 ( 式1 1 ) 上式中的相加按模2 运算，称这四个线性方程为码的一致校验关系或一致校验方 程组。已知三个信息元，由( 式1 1 ) 可以很快得到四个校验元。( 7 ，3 ) 码共有2 3 = 8 个许用码组，它们是按照( 式1 一1 ) 的一致校验关系从2 7 = 1 2 8 个码组中挑选出来的， 如表1 - 2 所示。 表1 - 2 按( 式1 - 1 ) 编出的( 7 3 ) 码 码纤 信息组 c 6c 5c 4 c 3 c ， c lc o 000oo00o0o 0010o11101 0io0loo111 0l l ol1101o l00 l0o1110 l0ll 01o011 ll0l l0 1 0o1 l11i1101o0 其中任意两个码组对应位按模2 相加，则得到另一个6 - 5 字。这八个码纽具有封闭 性，封闭性是线性码的重要特点。从表中还可看到侮个码字的c 6 , c s ，c 。位是原来的 6 信息位，后而赴l h 这：个信髓、1 讧求得的校验化缘返种心r l i 构们线r k 分绀_ i f 5 称为线 性系统码。 如果把( 式1 1 ) 移项并记成妇蚋：j 髟式，! j 1 1 j ( 1 1 ) 成为： c 6 101l000 1 c 5 111o1oo 怦 11o o o 1 o9 c 3 o1looo1 怦 。h c o c 7 = p i 。k 7 = 0 ( 式1 2 ) 即：ch7 = 0( 式1 3 ) 称h 为( 7 ，3 ) 码的监督矩阵或校验矩阵。c 1 和h 。分别是码字c 和矩阵h 的转置 p 为4 3 阶矩阵，1 4 为4 阶单位方阵。 通常情况下，二进制( m k ) 系统码校验矩阵的般形式为： h = 巨 p 2 1 | d 2 1 p 1 1 0 0 p t 2 o l 0 p ! 。一tp 。一t 0 0 1 = 【尸，。】 ( 式1 4 ) 这是一个( n - k ) x n 阶矩阵，式中p 是( n k ) x k 阶矩阵，i n - k 是n k 阶单位方阵。 如果在( 7 ，3 ) 码的八个码字中挑选出线性无关的三个码字作行，组成如下形式的矩 阵： 1 001ll 0 g = l0 l00111 l = ，q 】 1 0 0 l1 1 0 1 j 式中1 3 是3 阶单位方阵，q 是3 4 阶矩阵。 显然由g 矩阵行的所有线性组合，能生成( 7 ，3 ) 码的所有八个码字，故称g 矩阵 为( 7 ，3 ) 码的生成矩阵，把g 矩阵与( 式1 - 2 ) 的h 矩阵对照可知，g 矩阵中的q 矩 阵就是h 中p 阵的转置，即q = p 1 。因此一般情况下，二进制( n , k ) 系统码的h 矩 阵为( 式1 4 ) 形式，则它的生成矩阵g 有如下形式： g ：【，。p7 - 1 0 一0 p l ip ” 0 1 0 p ! i p 1 2 0 0 1 p 女ip k2 因为g 矩阵的每行都是一个码字，因此山( 式1 3 ) 必然可得 川 柑 p p g h 7 = 【，女】【川】= 0 ( j i 一5 ) 甑上巍l 涂露戴，j 臻弼瓣g 蹙眸战h 筵t 阵确定了，喇煞粥鲴凌巍夔譬决l 1 2 2 伴随式署检错 令c = ( c 引c 。2 c 0 ) 是邋避蔫道传送敬妫缎。r = 轴f 。2 r l ；) 跫救瞒缓渡到懿鹃。 鼎然r = c + e 遮罩e i ( e “e 们e o ) 是错误图样。若e i = 1 说明码字的c i 位发 3 - y 锚误。 山于每个码字c 必须满足h 矩阵每行所确定的线性方程，h i 必须满足( 式1 3 ) ，因 此对接收到的r 后可用( i 弋1 3 ) 检查，羞等于0 则认为是码字，没有错误；否刚r 不是羁字，产，圭了错误。 定义：s = o n - k - i j 一2 ) = r h 7 = ( c + ) ；c 7 + e - h7 = e 辩7 ( 式l 一6 ) 称s 为伴随式，它是一个( n 一轴重序剜。显然s 仪与错误图样脊薨，而与发送的是 什么码字无关。若e = ( 0 0 o ) ，则s 为0 ，否则s 不为0 。因此可以根据s 是否为0 进行检错。如莱信道中产，土的错误图样难好是一个码字；s = e h 墩为0 ，此时收端 译码器载不簸发瑗，遮藏产鬟三了不可捡渊豹错误。n ，k ) 线蛙分缍鹚不麓稔锘豹橛率 随校验元的数目增加而呈指数下降。 1 2 3 汉明亟量与汉明距离 设c = ( c 州o n - 2 c o ) 是一个二进制r l 煎，c 的汉明羹餐w ( c ) 定义为c 中非0 分最的 数目。如c = ( 1 0 0 1 1 1o ) 的汉明重量是4 。令c l 和c 2 是两个n 重，则c i 和c 2 之间的汉 明距离d ( c 1 c 2 ) 定义为对敷分量不同的数嚣。蟊c l 一( 1 0 0 1 1 1 0 ) ，e 2 一0 1 0 0 1 1 1 ，它嬲 的第1 ，2 ，4 ，7 位不同，敬d ( c i ，c 2 ) = 4 。 对( n ，k ) 线性码的2 0 个码字进行计算，得到所有可能出现的码字对之间的汉明距 离。其中最小距离称为该码的最小汉明距离，用d 表示。可以证明一个( n ，k ) 分缎码， 鳃鬃要旋捡渊玛字孛d 1 令睫橇罐谟，瓣要求玛豹趱小距离为d ；若要求舀髓纠匿t 个随机错误，则要求码的最小距离d = 2 t + l ；若要求蹴疆纠n ：t 个黼机错误，又要舱测 d 个( d t ) 错谡，则要求码的最小距离d q 十d 十1 。 1 3 锤嚣鹳察b c h 玛 循环码魑线性分组鹤中最重要的一个子类，它的结构完全建立在有1 5 睦域苯础上， 具有以下两个特点：一是粥鳇编码电路及l 半随式计算f 皂路非常简单。耪于实现：二是 8 南瓜航1 j 自f l 几j7 。! 卜川，o e 上 瓶环码的代数结构具有 1 3 多有川的，r l ：质，功j 二找刘仃效的i 千f i 5 力刊i 。此酗、篪锚 ： 制系统中所使用的线性分组俨5 几乎鄙地循环码。 1 3 1 循环码的基本概念0 4 1 1 6 一个( n k 、循环码是码长为n ，有k 个信息儿的线性码。它i 仃姗f 特_ i ：侄码 组的每一次循环移位( 左移或右移) 得到的是码r i j 另一鹏纠【。i 订这利，衙环移他h ： 变性的线性分组码称为循环码。 为便于用代数方法来研究循环码，将长为n 的鹏组与n1 次多项式建立如下对j 堂 关系。若码组c = ( c 。m c 。_ 2 ，c o ) ，相应的多项式表示为： c ( z ) = c n _ l x 卜+ c n - 2 工肛2 + - + c i x + c o 称c ( x ) 为码多项式。对循环码来说， c 。= ( c 。_ 2 c 。- 3 ，c o ，cn - 1 ) 也是( n ，k ) 码的码字。 若c = ( 。n _ l c2 c o ) 是( n k ) 码的码字则 用多项式表示为： c ( x ) 相应于x c ( x ) 用x n _ 1 多项式除后所得之余式。 1 生成多项式与生成矩阵 循环码是线性码，因此必有k 个线性无关的码字作基底，生成2 。个码字。若从( n k ) 循环码的2 。个码字中，挑出一个前面k - 1 位都是0 的n k 次码多项式 g ( 工) = 1 十g l x + g ! 工! + - + g ，- k - i 工”一。1 + x 卜。 则g ( x ) ，x g ( x ) ，x 2 9 ( x ) ，x 卜l g ( x ) 都是码字，且这k 个码字线性无关，因而可以用 这k 个码字作为循环码的基底，并以该基底作为矩阵g 的行。称g 矩阵为码的生成 矩阵，g ( x ) 为码的生成多项式。可以证明生成多项式g ( x ) 是2 。个码字集合中唯一的一 个次数为n k 次的多项式。 生成矩阵g 的多项式表示为： g ( x ) = b “1 9 ( x ) ，x ! g ( x ) ，x g ( x ) ，g ( x ) l 。 ( 式l 7 ) 设( n ，k ) 码中的k 个信息元为( m k - 2 m l m o ) ，9 ：! | j 码多项式 c ( x ) = ( m h i 一2 = l m l ，” 一2 m l m o ) g ( x ) g ( r ) 叩。，卜加) | kj = 占( x ) ( ，2 t l 工+ m 一 工一! + + 厅7 0 ) ( 式1 8 ) 尚述尤线、l - l f f 系统信j 煎汗，i j 5 的圳究1j 1 划m 根据( m m “m i m o ) 的刁i 同以值，i ：h 卜，【l = l ， 到( n k ) ：；, i j d , i i “i ：j 所仃2 。个f i j 5 i i j 此可得出以下结论：( n ，k ) 衙坏码的每个码多项揶怂乍成多坝g ( x ) f l j 俏。反之， 能被g ( x ) 除尽的次数不大于n l 的多项式，也必址多式。 由( 式l 一8 ) 可知，用信息多项式r e ( x ) = m h “。十”t h f “! + + l o 乘以g ( x ) 就 得到一个码多项式，但是用这种相乘方法得到的酽5 1 ；是系统码，也就是信息位平校验 位不容易区分。为了得到系统循环码的编码方法，可作如卜运算： ( 1 ) 以x ”“乘以信息多项式m ( x ) ，则x ”。m ( x ) f f u 次数小于n 。 ( 2 ) 用g 【x ) 除x ”。m ( x ) 得到余式r ( x ) ，它的次数小一j 二n k ，把此余式的的系数 作为校验元附加在信息组后面，就得到一个能被g ( x ) 除尽的码多项式c ( x ) ，即： x ”一月 ( x ) = q ( x ) g ( 工) + r ( x ) c ( x ) = x n - km ( x ) + r ( x ) = q ( x ) g ( x ) 由此可得到以多项式表示的系统循环码的生成矩阵为： 工卜1 + _ 一( 工) g ( x ) ：ij ”一2 + _ 一z z l ( 式l 一9 ) b 埤出) j 式中：r n ( x ) 是甙x ) 除x ”所得的余式。由该式中多项式之系数可得到码的系统形式的 生成矩阵g 以及h 。 2 伴随式计算和错误检测 令c ( x ) 与r ，( x ) 分别是发送和接收的码多项式。用生成多项式g ( x ) 除r ，( x ) 得： r ，( t ) = c ( x ) + e ( x ) = g7 ( j ) - g ( x ) + s ( x ) s ( x ) = c ( x ) + g ( x ) t g ( x ) + e ( x ) 式中s ( x ) 为伴随式，e ( x ) 是错误多项式，因为c ( x ) 是码字它必是g ( x ) 的倍式即 c “) = m ( x ) g ( x ) ，所以 s ( x ) = r e ( x ) + q ( x ) g ( x ) 十e ( 工) 三( 工) m o d g ( x ) ( 式1 1 0 ) 说明循环码的伴随式计算电路就是一个用g ( x ) 除r ，( x ) 求余式的除法电路，s ( x ) 就是所 得的余式。 在循环码所确定的检错能力以内，若接收的r ，i x ) 没。 1 。1 + t 以，则e ( x ) = 0 ，s ( x ) = o 否则s ( x ) o 。因此循环码的检错电路就是一个除法f u 踏。 由于g ( x ) 的次数为n k ，若错误图样e ( x ) 是一个长为n k 的突发错误： 0 f 柯j j ! 航。1 i 航人人产f ! i 。j ：nl t e ( z ) = e j x + e , 1 x + + e , + n - k h x h “一= 工+ e7 ( x ) g ( x ) 除h i 尽x 1 ，1 ix 1 与e ( x ) 1 索，e ( x ) 的次数义小rn k ，i f , i i l t l i o ) 搿j js ( x ) 决不等于零。由此可知任何一个n k 衙环码一定能发现所仃k 嫂1 i 人fn k 的突发饼 误。 1 3 2b c h 码的主要特征 b c h 码是一类纠正多个随机错误的循环码，4 有严 各的代数结构，它构造容易， 根据码的最小距离，可以由x “1 的因式得到码的生成多i 页式g ( x ) 。 为了解b c h 码的构造，首先介绍有关有限域g f ( 2 ”) ( m 1 的整数) 的一些基本知 识1 4 l 【”。通常有q 个元素组成的有限域g f ( q ) 称为q 阶有限域，这旱q 是素数或素数 的幂。因此在g f ( 2 ) 有限域中有2 个元素，分别以0 、o0 ，o ，o2 ，q ( 仁2 一2 ) 表示。 其中每个元素又可用二进制m 重表示。 在g f ( 2 “1 有限域中，元素之i h j 定义了相加和相乘两种运算。其中元素之间的相 加运算，是元素所对应的m 重之间的模2 和。而元素a1 、。，之f h j 的相乘运算足它们 的指数相加，其中指数i + j 按模2 一l 运算。如g f ( 2 。) 中 d5 q6 ；a1 1 三q 4 m o d7 可知o7 - 1 。在有限域中能使元素n ”= l 成立的最小1 3 ，称舟浚元素的级。可知上例中 的n 是7 级元素。g f ( 2 ”1 中某一元素o 。的绒若是2 一1 ，则称元素1 为域的本原元 或生成元，用该元素的所有幂次能生成o f ( 2 ) 中的所有2 m 一1 个非零元素。g f ( 2 ) 中的生成元或本原元可以不止一个，如g f ( 2 4 ) 中，若a 是本原元，则o ”= 1 ，而a 2 q4 ，7 ，8 ，q1 1 ，1 3 和q1 4 也是该域的本原元，因为它们的绒均是1 5 。 由有限域的理论可知【3 1 【”，g f ( 2 ”】域中的2 “一1 个非零元素一定是方程 x 2 ”- l 一1 = 0 的根，因而该方程在g f ( 2 ) 上可分解成一次因式的乘积 另一方面，x ”一1 多项式在g f ( 2 ) 2 2 也可分解成次数除得尽m 的所有不可约( 既约) 多项式m ( x ) 之积： x ! 。一1 = 兀肛) j 式中d i 表示m ( x ) 的次数，m i ( x ) 是g f ( 2 ) j 2 的既约多项式即m ( x ) 的系数仅墩1 和0 。 由以上两式可知m ( x ) 一定以g f ( 2 ) e l l 的d 个元素为根，f jm ( x ) 一定在g f ( 2 ”) 域巾 口一x n = 之， 口一r口一x 口 一 x ) 一 r = 一 r x 选见线f _ | f 系统信道i f 的d , j ij i 。爻j 地 完令分解成一次冈f 门乘私： 坍，( ) = ( x 一口1 ) ( 一口：)( 工一d ) 式l 】ai ( i = l ，2 ，d i ) 是g f ( 2 ) 中的元素。 由多项式理论可知，g f ( 2 ) j ：的既约多项式m ( x ) j ? 以ui 为+ m ，则它必以 髓，( 口，) 二( 口，) 2 ，。，( a ) 二 为根，称这组根为l l l i i x ) 的共轭根系，式中i 是满足 27 = l ，m o d ( a 的级)( 式1 - 1 1 ) 的最小1 。如o f ( 2 4 ) ，是生成元，它的级是1 5 ，ob = l ，则o = u3 的级是3 ，满 足式( 1 1 1 ) 的l 是2 ，因而m ( x ) = ”5 ( x ) 的共轭根系有两个根：o5 ，a1 0 它是g f ( 2 ) 上的二次既约多项式。 m 5 ( x ) = ( x 一口5 ) ( x 一1 0 ) = x2 + x + l 称以n1 为根的、g f ( 2 ) 上的次数最低的首一既约多项式m ，( x ) 为a 。的最小多项式。 最小多项式在g f ( 2 ) 上一定是既约的，若m i ( x ) 是n 。的最小多项式，则m ( x ) 也必是它 的共轭根系中所有元素的最小多项式。 以g f ( 2 ”) 中的本原元n 为根的、g f ( 2 ) j 2 的最小多项式p ( x ) ，称为本原多项式。 本原元。的级必是2 一1 ，因为( 式1 - 1 1 ) 的最小l = m ，所以本原多项式p ( x ) 一定以 口，口2 ，口4 ，口”“共m 个元素作为共轭根系，它在g f ( 2 ) 上必是一个m 次既约多项式。 1 b c h 码的定义【4 】 q 进制循环码的生成多项式g ( x ) ，若含有以下( 5 1 ) 个连续根 口肌a ”n 制，口”+ d ! 则由g ( x ) 生成的( n ，k ) 循环码称为q 进制b c h 码，码的生成多项式为 g ( x ) = l c m m o ( j ) ，m i ( x ) ，一m “0 ) ) 式中：m ( x ) 是口”的最小多项式：口是g f ( q ) 域中的n 级元素：m o 是整数：l c m 表示最小公倍。 二进制b c h 码的定义可简化，驭m o = 1 ，占= 2 t + 1 ，又设口是g f ( 2 ) 域中的n 级元素，则二进制码的g ( x ) v aq ，q2 ，q4 ，q2 1 为根，g x ) = l c m m l ( x ) m 2 ( x ) “2 i ( x ) ) 。 但是由麸轭根的定义可知，g f ( 2 ”) 域中1 2 。与( 口) ! ( ) 、一，她下“是一组共轭根， 它们有相同的最小多项式，所以二进制码的生成多项式g ( x ) = ”i ( x ) ”3 ( x ) m 2 卜l ( x ) 。 定义：二进制循环码的生成多项式g ( x ) 若以。o3 ，o5 ，n ! 。1 为根，l i g ( x ) 2 m l ( x ) m 3 ( x ) m 2 l i ( x ) 则此g ( x ) 生成的循环码称为二二进制b c h 码，订坡小_ l ，离d 2 t + i ，6 5k n = l c m ( e i ，e 3 ，。一e 2 。il 式r 1a 是g f ( 2 ) 域中的n 级元索，e ( i = l ，3 ，二t 一1 ) 址c - 。f n 缎。 在f l e x 系统中使用的是b c h ( 3 1 1 ) ，t = 2 ，l lp ( x ) = x + x 二；1 足j 个本瞰多项 式，由于t = 2 ，m l ( x ) = p ( x ) ，因此只要再计算m 3 ( x ) ，就【】j _ 以算山其7 l 成多项j g ( x ) 。 为此先求a 3 的共轭根系：口3 ：( 口3 ) 2 = a6 ：( a3 ) 、= 。”“3 ) ：= 口u ：( 口3 ) y = 口”： ( 口3 ) = 口3 。故有 用3 ( 工) = ( + 口3 ) ( 工+ a6 ) ( 工+ a 1 2 ) ( x + 口二4 ) ( 工+ 口l7 ) ( 式1 1 2 ) 由于a 是本原元，p ( a ) = o ，故有口5 = 2 + 1 ，因此g f ( 2 5 ) 中的全部元素均可以用小于 5 次的n 的多项式来表示，该a 多项式恰好与二进制的5 重数组存在着一一对应的关 系，故可将多项式的加法运算转化成5 比特的二进制异或运算。g f ( 25 ) 中的元素、小 于5 次的q 的多项式及对应的二进制的5 重数组之问的关系，列于表1 3 表1 - 3g f ( 2 5 1 域元素的三种表示 g f ( 2 5 ) 小于5 次的 对心的- 二 小j - 5 次的 对心的一 进制的5 g f ( 23 1 中 进制的5 中的元素 口的多项儿 的l 崇 口的多项式 重数组董数组 1 1 0 1 l 1 1 0 0 0 0 l 口1 6口4 + a + a + 1 1 0 0 u 口d 0 0 0 1 0 a 1 7 口。+ 口+ 1 0 0 i 0 0 乜1 8a + l0 0 0 1 1 a 一口。 0 0 l l o 口3a 3 0 1 0 0 0 口l 。口一+ 口 a 4d 4 1 0 0 0 0 a 二0口3 + a 二 0 1 1 0 0 口5口3十1 0 0 1 0 1 口! la j4 - 口3 1 1 0 0 0 口6口3+ 口 0 1 0 1 0 口4+ a 二+ 1 1 0 1 0 l 口一 0 l l l l 口7口4 + a 二 1 0 1 0 0 a 二3盘+ a = + 口+ 1 a 8 口3 + a ! + 1 0 l l o l a 1 4 盘4 + a ) + 口二+ a 1 l l l 0 a 9n+a 3 + a 1 1 0 1 0 口4 + a 、 + 1 i l ( ) 0 1 口 让尤线叶系统信j n i f n ，j 川，l i 止吣 口1 0口4 + 1 1 0 0 0 l 口h口。口! 十口十1 儿】l 0 0 1 1 1 、1 【】1 0 1 【 口i ia 一+ a + l。+ 口十i 0 1 1 1 0 口! h口+ 口一+ 口 l ( j l l 【) 口1 2a 1 + 口十口 0 1 0 0 1 口1 3 口4 + 口3 + 口二 1 0 02 9 d 、+ 1 口1 4口4 + a3+a 2 + 1 1 1 1 0 l c g 3 1 1 a 4 + 口 1 0 ( 】1 0 口l 5 a4 + d 3 + 口! + 口+ 1 l l l l l 口j 1 l0 0 0 0 l 利用该表可将式( 卜1 2 ) 简化为 m 】( 工) = 工5 + x 4 + x3 + 工+ 1 ( 式l 一1 3 ) 从而求得b c h ( 3 1 ，2 1 ) 的生成多项式为 g ( x 1 = x 。o + j 9 + x 8 + x 6 + 工5 + 工3 十l 2 。码的尘成 b c h 码是一种循环码，因此其生成方法和一般的循环码完全相同。设r e ( x ) 是消 息多项式，则码字多项式c ( x ) 为 或 c _ 簪。 c ( 工) = c l z ”1 + 一2 x 俨2 + - + c 2 2 2 + c l x + c o ( 式1 1 6 ) 其系数为1 或0 。可以证明g ( x ) 能除尽c ( x ) ，而且c ( x ) 也以甜，口2 ，口4 ，d ! 为根。 3 h 矩阵 因为对于l i 2 t ，a 是码字多项式c ( x ) 的根，故有 c ( a 。) = c 。1 ( 口。) ”一+ c 一2 ( d ) ”一2 + + c ! ( 口。) ! + c i 甜十c o = 0 ( 式1 17 ) 写成矩阵形式，有 ( c 。一1 c ! ，- ，c 2 ，c l ，c o ) _ ( 口7 ) 肛1 ( 盘。) 忙! - ( 口7 ) 2 a ) l ，1 17 = 0 ( 1 - 18 ) 对于全部1 i s2