（信号与信息处理专业论文）rs码编译码及其快速实现.pdf

r s 码的编译码及其快速实现 电子科技大学硕士论文 abs tract w e a l l k n o w r e l i a b l i t y a n d v e l o c i t y a r e a l w a y s c o n fl i c t . i f t r a n s m i t t i n g m e s s a g e s q u i c k l y , t h e n i t w i l l s h o r t t h e t i m e o f t r a n s m i t t i n g a c o d e w o r d ,n a r r o w t h e w a v e f o r m a n d l e s s t h e p o w e r. s o t h e p r o b a b l i t y o f a r i s i n g e r r o r s w i l l i n c r e a s e w h e n e n c o u n t e r r i n g n o i s e a n d i n t e r f e r e n c e , a n d t h e s p e e d o f t r a n s m i t t i n g m e s s a g e s w i l l s l o w d o w n .h o w t o s o l v e t h e c o n fl i c t i s t h e k e y p r o b l e m i n d e s i g n i n g a c o m m u n i c t i o n s y s t e m. t h i s p a p e r g i v e s a a b o r a t i v e r e s e a r c h i n g o f n o t o n l y t h e w i d e l y u s e d c o d e s s u c h a s b c h c o d e s a n d c y c l i c c o d e s， b u t a l s o c o m p u t e r s i m u l a t i o n o f t h e d e c o d i n g o r c o d i n g o f r s c o d e s . i n t h i s p a p e r t h e k n o w n d e c o d i n g p r o c e d u r e s f o r r e e d - s o l o m o n ( r s ) c o d e s a r e m o d i f i e d t o o b t a i n a r e p e t i t i v e a n d r e c u r s i v e d e c o d i n g t e c h n i q u e w h i c h i s s u i t a b l e f o r f p g a / c p l d b as e d o n v h d l i m p l e m e n t a t i o n a n d p i p e l i n i n g . i t i s s h o w t h a t t h i s r s s y s t e m s h as t h e p o t e n t i a l a d v a n t a g e o f a c h e v i n g a h i g h d e c o d i n g s p e e d t h r o n g h p a r a l l e l - p i p e l i n e p ro c e s s i n g .i t c a n c o r r e c t b o t h r a n d o m a n d b u r s t e r r o r s o v e r a c o m m u n i c a t i o n c h a n n e l . s o i t i m p r o v e t h e p r o b l e m i n a s u i t a b l e w a y . a t t h e s a m e t i m e i t g i v e s t h e fl o w o f d e s i g n i n g a c o m m o n p r o g r a mm e d l o g i c d e v i c e . i n t h e e n d t h e m o s t w i d e l y u s e d c o d e s s u c h as c o n v o l u t i n a l c o d e s a n d t u r b o c o d e s a r e a l s o i n t rod u c e d k e y w o r d s c h a n n e l c o d i n g ,t h e fi n it e f i e l d ,b c h c o d e s ,p a r r a ll e l p r o c e s s i n g ,p i p e l i n e p r o c e s s i n g ,t u r b o c o d e s , r e e d - s o l o m o n c o d e s ,c y c l i c c o d e s , c o n v o l u t i o n a l c o d e s , v h d l ,c p l d / f p g a . r s 码的编译码及其快速实现 电子科技大学硕士论文 第一章绪论 1 . 1 课题意义及应用背景 在现代社会中，信息对经济、 科学和文化的发展起着日 益显著的作用。它 为提高各种社会活动提供了条件， 并促进了 生产的发展。 信息的交换、 处理和 传输是现代通信的任务。 数字信号经过传输， 会产生错误。可靠的数字通信系 统必须将差错率控制在允许的范围内。 提高信息传输的可靠性和有效性，始 终 是通信工作所追求的目 标。纠错码技术是提高信息传输可靠性的一种重要手段。 随着信息时代的到来和微电子技术的飞速发展，纠 错码技术已成为一门标准技 术而被广泛应用。在通信领域中， c r c循环校验已成为各类线路传输中必不可 少的一部分;在移动通信中，纠错码被广泛应用于模拟体制的信令传输及数字 体制的整个传输，以提高传输的可靠性和节省珍贵的频谱资源;在卫星通信中， 纠错码技术已用来对高功放的要求和减少地球站天线孔径的尺寸的经济可靠的 方法;在电话网的数据传输中，纠错码、差错控制技术已是高速数据传输成为 现实的关键技术。纠错码技术还广泛应用于计算机存储和运算系统中。 在数字通信系统中 可靠和快速往往是一对矛盾， 随着c p l d / f p g a的出 现， 研究c p l d / f p g a在通信工程中的 应用 一直是热点。 本论文正是从这一点出 发， 用c p l d / f p g a实现了r s 编译码， 从而使得可靠并快速传输信息成为现实 。 由于本系统是与巨浪通信公司合作，结果已被他们采用。 1 . 2 数字通信系统的组 成和信道编码理论 所有的数字通信系统如通信、 雷达、 遥控遥测、 数字计算机的 存储系统和 内 部运算以及计算机之间的数据传输等都可以归结成如图1 所示的模型: 图卜 1 数字通信系统模型 对于图中的信源编码器是为了提高传输的有效性， 信道编码器是为了抗击 传输过程中的各种干扰，通过人为地添加冗余度，使系统具有自 动纠错的能力 r s 码的编译码及其快速实现 电子科技大学硕士沦文 而进行的编码处理，又称纠错编码。 s h a n n o n 信道编码理论: 每个信道具有确定的信道容量c ，对 任何小于c的码率r ， 存在速率为r码长 为n 的分组码及( n o ,k ,m ) 卷积码， 若用最大似然法 译码， 则随着码长的增加其译 码错误概率p 可任意小。 信道纠错编码中的码字分类: 信道编码中 用到的码类很多， 为简便起见， 我们用下面的图1 - 2 说明: 纠错码 非线性码线性码 卷积分组码 非循环码循环码 纠随机错误码 纠 群发 错 误 叫 】 纠 随 机与 群 发 错 误码 图i - 2纠错码的分类 4 同步错误码 1 . 3 可编程a 9 i c的概述 专 用 数 字 集 成电 路a s i c ( a p p l i c a t io n s s p e c ifi c i n te r g r a t e d c i r c u i t ) 按目 前 的 制造方法， 可分为全定制a s i c ， 半定制a s i c和可编程a s i c 。可编程a s i c 芯片各层均由工厂预先制造好， 不需要定制任何掩膜，用户可以用开发工具按 照自 己的设计对可编程器件编程，以实现特定的逻辑功能。 可 编 程逻 辑器 件 ( p r o g r a m m a b l e l o g i c d e v i c e ) 简 称 p l d ， 是 新一 代的 数 字器件， 它不仅有很高的 速度和可靠 性， 还具有可重复编 程的特点。 它的分类如图1 - 3 : 图 卜 3 r s 码的编译码及其快速实现 电子科技大学硕士论文 f p g a现场可编程门阵列器件通常由布 线资源围绕的可编程单元 ( 或宏单 元) 构成阵列，又由可编程 i / o单元围绕阵列构成整个芯片。f p g a是由掩膜 可编程门阵列和可编程逻辑器件演变而来的， 将它们的特性结合在一起， 使得 f p g a既有门阵列的高逻辑密度和通用性，又有可编程逻辑器件的用户可编程 特性。 按逻辑功能块规模的大小可分为粗粒度和细粒度: 按照逻辑块的构造可 分为 两类: 其一是查找表类型; 其二是多 路开 关类型。 第一种是具有可编程内连线的通道型门阵列。 它采用分段互连线， 利用不 同长度的多种金属线经传输管将各种逻辑单元连接起来。 这包括x l i n x公司和 a c t e l 公司的产品。 第二种是具有类似 p l d可编程逻辑块阵列的固定内连布线，采用连续互连 线， 利用相同的金属线实现逻辑单元之间的互连， 布线延时是固 定的， 并可预 测。 a l t e r a公司的产品就属于这种类型。 r s 码的编译 码及其快速实 现 电子科技大学硕士论文 第二章线性分组码， 循环码和b c h码 2 . 1线性分组码 线性分组码是差错控制编码中 极重要的 一类码， 它是讨论其它各类码的基 础。虽然这类码的概念很简单， 但却非常重要。特别是关于码的生成矩阵 g和 检验矩阵h的概念， 它们之间的关系。 实际上，由于 g , h概念易于理解，即 便是非线性分组码的 r s码和卷积码也通常用 g , h矩阵表示，并导出与之相 关的重要特性。 2 . 1 . 1 线 性分组 码的 基 本概念 在数据传输系统中，假设数字源输出二元数字符号序列。对分组码来说， 二元数字符号序列被分成长度确定的一组组消息，每组消息由 k个信息数字组 成， 以 符 号u 表 示， u = iu p ,u-, u r -, j ， 分 组编 码 器将u 按一定的 编 码 规则变 换成 二元n 重v , v = i v o ,v- - - ,v , , 1 , v 称为 码字( 码 矢) 。 码字v 与u 之间 的 关 系 必须 是一一对应的。2 “ 个不同的消息对应着 2 “ 个不同的码字。这 2 “ 个码字的集合称 为分组码。 长为n ，有2 1 个码字的分组码c ，当且仅当c构成域 g f ( 2 ) 上n 维矢量 空间的v n 的一个k 维子空间时， 称c为线性分组码。 v n是一个矢量空间， 线 性分组码是 v n的一个 k维子空间， 对于加法运算它是一交换群。故线性分组 码又称群码。 2 . 1 . 2线性分组 码的 生 成 矩阵 线性分组码 c是矢量空间v n 的一个k 维子空间v n , k 。在 v n , k中可以找 到k 个线 性独立的 矢 量g o ,g n9 k - l ， 它们的 线 性组 合 v = n 0 9 0 + u i g i + . . . + u r - l g t - l 产生了 v n ,k的全部矢量，即线性分组码 c的所有码字。其中 u ; e g f ( 2 ) ,0 _ i k . g o ,g v9 k -1 均是二元n 重。 以这线性独立的k个矢量作为 矩 阵的行矢量，可构成下列k x n 阶矩阵 8 0 .n - 1 91 . n - 0 gg 0010: gg g k - 1 .0 g k - 1 .1 ” g k - 1 .a d 一 - 9091:红 一一 g 其 中s = ( g io 8 u , g : - 1 1 ，0 _ i d c , 设u = i u o ,u l , 一u k - 1 1 是要编码的 消息， 则相 应的 码字v 为 v = u g r s 码的 编译码及其快速实现 电子科 技大学硕士论文 90岛歇 二 u o ,u l , u k - 1 1 = u 0 b 0 + u 1 s 1 + . . . + u k . 1 9 k . 1 g 的行张成 v n , k 或说 g的行生成线性分组码c o矩阵g称为c的生成矩 阵。由此可以看出，一个线性分组码可由生成矩阵完全确定。因此线性分组码 只 要存储g矩阵的k 行， 并根据输人消息u = i u o ,u , . . . , u k - ) 构成这k 行的一个 线 性组合，即码字。 2 . 1 . 3 一致 检验矩阵 线性分组码由它的生成矩阵完全确定。 根据矢量空间中零化空间的知识， 对任意有 k个线性独立行的 k x n阶矩阵 g 、存在一个具有 n - k个线性独立的( n - k ) x n 阶矩阵 h , g的行空间中的矢量都和h的行正交，且与 h的行正交的任意 矢量都在g的行空间中。因此， 我们也可这样来定义由g生成的线性分组码: 一个 n 重 v是 g生成的码中的码字，其充要条件是 v h t = o 。 矩阵h叫做码 的一致检验矩阵 或简称检验矩阵) 。即有 g t h = 0 或 g h t = o 说明由g和h的行生成的空间互为零空间。 2 . 1 . 4 系统码 定义: 若信息组以不变的形式在码组的任意 k位 ( 通常在最前面)中出现 的码称为系统码，否则为非系统码。它的结构形式如下: k 位信息位 n - k位检验位 图2 . 1系统码的一种结构形式 由 于系统码的码字的前k 位是原来的 信息组， 故由g的定义式可知， g矩 阵 左边k 列必组成一个单位方阵k , 因 此系 统码的 生成矩阵 通常为 g = i f t p l 式中， p是 k x ( n - k ) 阶矩阵。 如果信息组不在码字的前k位， 而在码字 的 后k 则g矩阵中的i r 方阵p 矩阵的 右边。 因为g和h矩阵所组成的空间 互 为零空间，所以与上式相对应的h矩阵为 h = - p t n -4 l 式中， - p r 是一个( n - k ) x k阶矩阵， 它是 p矩阵的转置， “” 表示一 p r 阵中的 每一个元素是 p阵中对应元素的逆元，在二进制情况下， 仍是该元素自 己。显 然由此得到的h满足 g ht=i!一 、 pli-k j 系统码的编码相对而言较为简单， 且由g可以 方便地得到h( 反之亦然) ， 容易检查编出的码字是否正确，同时，对分组码而言，系统码与非系统码的纠 错能力完全相同因此， 若无特别声明， 本文仅 讨论系统码形式。 r s 码 的 编译 码 及其快 速实现 电子科技大学硕士论文 2 . 2 循环码研究 循环码介绍: 循环码是最重要的一类码， 也是工程应用最多的码，因 此也是我 们研究的重点。循环码具有严谨的代数结构，它的性能易于分析，同时。由于 循环码具有的循环特性，它的编码电路简单，易于实现。 定 义: 一 个n 重 子 空 间v , 声 v n ,若 对 任 何 一 个v =(a , 十 a . .2 + . . . 十 a , ) e vk , 恒 有v i= ( a -s + a -3+ . . . . . + a o + a 。_1 ) e v .t ,则 称v _、 为 循 环 子 空 间 或 循 环 码 也就是说， 一个 ( n ,k ) 线性码 c ，若它的一个码字的每一个循环移位都是c的 一个码字， c就是一个循环码。 表示循环码的方法，用码多项式最方便， 一个码矢对应一个码多项式。例 如， 对 码字c = ( c . c z , -. . . , c o ) ,它的 码多 项式 为: c ( x ) = c , x + c _z x . . . . . . . . . c ,x 嫣 码字c左移1 位的新的码字对应的码多项式为: c ( x ) 二 c ._l x + c _,.z x -z + . . . . . . + c o x + c-ix 一，+ c .zx -z . . . . . . . + c , ; c ( x ) 与c ( x ) 之间 存在重要的 代数 关系， 我们将c ( x ) 多 项式两端乘x , 即 x c ( x ) = c . ,x 一， + - - - + c .;_, x + - - - + c , x + + c o x = c , x i,( x + 1 ) + + c . , x ( x + 1 ) + c , ( x + 1 ) + c . ;_ ,x + c o x + c _ ,x + . . . + c ; x + c . ; = q ( x ) ( x + 1 ) + c ( x ) 其中 q ( x ) = c , , x + - - - + c _;+ , x + c .; 由 此可以 看到， 码多项式c ( x ) 就是x + 1 除多项式x ; c ( x ) 所得之余式， 这 一重要结论为 循环码的编码莫定了 基础。 循环码由于有清晰的代数结构，使得对码的分析能较容易的以数字的方式 进行，为我们在工程上进行应用提供了许多便利。 众多的科学家，致力于循环 码的代数特性的研究，提出并完善地证明了许多重要定理，这里仅说明生成多 项式的重要概念。 定义: 生成多项式g ( x ) 是模x + 1 剩余类代数中， 一个理想的 次数最低的 非零首 一多项式，它是理想或循环码的生成元。 定 理1 : g f ( q ) ( q为 素 数或 素 数的 幂 ) 上的 n ,k 循环 码中， 存 在 有 唯 一的n - k 次 首 一 多 项 式g ( x ) = x -k 十 若g ( x ) 是 一个n - k 次多 项 式且是x + 1 的 因 式， 则g ( x ) 生成一( n ,k ) 循 环码。 由定理2 ，寻找合适的 ( n , k ) 循环码，就是如何对x + i 多项式进行因式分 解的问题。x + 1 的因式分解问题建立在有限域理论基础上。 定 理3 : 设g f ( p ) 上 多 项 式a x ) 在o f ( p = q ) 有。 为 根 则 a 亦 是f ( x ) 的 根 。 2 . 3 b c h码 自1 9 5 0年汉明发表了纠正单个错误的码以来，几乎过了 1 0 年的时间， 才 于1 9 5 9 年由 霍昆 格姆 ( h o c q u e n g h e m ) , 1 9 6 0 年由 博 斯 ( b o s e ) 和雷 一 查 得胡 里 ( r a y - c h a u d h u ri ) 分别提出了纠正多个随机错误的 循环码-b c h码的构造方 法。b c h码是目 前所发现的一类很好的 线性纠 错码类。它的纠 错能力很强， 特 别是在短和中等码长下，其性能接近理论值， 并且构造方便，编码简单。特别 是它具有严格的代数结构，因 此它在编码理论中 起着重要的 作用。 b c h码是迄 今为止研究得最为详尽，分析得最为透彻，取得成果也最多的码类之一。 1 9 6 0 年彼得逊 ( p e t e r s o n )从理论上解决了二进制b c h码的译码算法， 奠 定了b c h码译码的理论基础。 稍后， 格林斯坦 ( g o r e n s t e n ) 和齐勒尔 ( z i e r l e r ) 把它推 广到多 进制。1 9 6 6 年伯利 坎谱 ( b e r l e k a m p ) 利用迭 代法 译码b c h码， 从而大大地提高了译码速度， 从实际上解决了 b c h码的译码问题。由 于 b c h 码性能优良， 结构简单， 编译码设备不太复杂， 使得它在实际 使用中 受到工程 技术人员的欢迎， 是目 前用得最为广泛的码类之一。 定 义: 给定 任一有限 域g f ( q ) 及其 扩域g f ( q ) ， 其中q 是素 数 或素 数的 幂， m为 某一 正 整数。 若码元取自g f ( q ) 上的 一 循环 码， 它的 生成多 项式g ( x ) 的 根集合r中含有以下s - 1 个连续根: r 二 仁 0 ,a 、 十!,.,a “ 十 一， 时， 则由g ( x ) 生成的 循环码称为q 进制b c h码。 其中，。e g f ( q ) 是域中 的n 级元素， a - * g g f ( q ) ( 0 -i - s - 2 ) ,rn o 是 任 意 整 数， 但 对于 最 常 见的 情 况m 0 7 - 。 或i 。 若n ro = 1 ，则 称 这 类b c h 码 为 狭 义 b c h码。 设m ;( x ) 和 e ， 分别是a ( i = 0 , 1 , . . . , s - 2 ) 元素的 最小多 项式和级， 则b c h 码的生成多项式和码长分别为: g ( x ) = l c m( m o ( x ) , m , ( x ) , - - , m , _ 2 ( x ) ) n = l c m( e o ,e n , e e 一) 如果生成多项式g ( x ) 的根中， 有一个g f ( q ) 中的本原域元素， 则n = q m - 1 ，称 这种码长n = q - 1 的b c h码为 本原b c h码， 否 则 称为 非 本原b c h码 g f ( q ) 中 元素 的 级 一 定 是q m - 1 的因 子， 所以 非 本 原b c h 码 的 码长 也 一 定 是q . - i 的因子。 r s 码的 编译 码及其 快速实 现 电子科技大学硕士沦文 第三章r s 码 r s码是一类有很强的纠错能力的码。 是二进制 b c h码的多进制推广。 也 是一种典型的代数几何码， 它首先由里得 ( r e e d ) 和索洛蒙 ( s o l o m o n ) 应用 ms 多项式于1 9 6 0 年构造出来的。 所以简称r s 码。 由于r s 码是建立在g f ( 2 ) ( m - 1 3 , m是任意整数) 有限域上， 且r s 码是m d s 码， 具有极大最小距离特性， 它的卓越的纠错能力使得它在工程应用中引人注目。 r s码除了译码设备略有点 复杂之外， 它的 卓越的纠错能力， 无论是纠群发错还是随机错的能力，以及它 的快速译码速度， 均是其它码类所无法比 拟的。 由于短波、无线通信信道和有线通信信道中均以群发干扰为主，显然， 重 点研究r s 码有重要的意义。它在磁盘和光盘的纠错技术中也很有用途。 特别使随着 c p l d / f p g a技术的出现，极大地提高了它的译码速度。 本文 用到的流水线型结构算法就是改进了原有经典迭代译码算法，使之更适合用基 于 v h d l的 c p l d实现。性能有了质的飞跃。 从下文的 分析中我们可知，r s 码构造于g f ( 2 ) 有限域上， 随着m的不同， 可构造出不同码长的本原r s 码 但是，由 于 g f ( 2 ) 域随 m的 不同， 其本原多 项式各不相同， 且本原多项式 并无通用的规律可循， 无法做出适应各类大小信息流的纠错能力可变的通用 r s ( n ,k ) 码编、 译码器。但是注意到缩短 r s码其性能不变的特性，我们可在同 一有限域上， 作出纠错能力可调节的 r s ( n ,k ) 码编、译码器。 我所做的每一 模块都可在m相同的情况下随意调用。 3 . 1 r s 码简介 r s 码是一类有很强纠错能力的码，它 是q 进制b c h码中 最重要的 子类。 当然用ms 多项式产生的是非系统码，而用b c h码构造方法能产生系统码。本 文是用后一种方法。 定 义: g f ( q ) 上( q # 2 ) ， 码长n = q - 1 的 本 原b c h 码 称 为r s 码。 因 为x 0 一- 1 = rl( x - a ) a 的 最 小 多 项 式 为 : m ( x ) = x - a a , g f ( q ) 所以， 长为n = q - 1 . 设计 距离为6 的r s 码， 它的生成多项式为 g ( x ) = ( x + a ) ( x + a ) . . . ( x + a b 勺 通常情况下， k = 1 ， 此时 g ( x ) = ( x + a ) ( x + a z ) . . . ( x + a 一) 码的 描述: n = q - l ;n - k = 2 t ;d ,. ;, 6 = 2 t + 1 所以:g ( x ) = ( x + a ) ( x + a ) . . . ( x + a z ) 由r s 码的 定 义 可 知， 生 成 一 个q 进 制( 一 般q = 2 ) 的( q - l ,q - 8 ) r s 码， 有最小距离6 ，由于线性码的最大可能距离是校验元的 个数加 1 ，而r s 码恰好 做到了这一点，因此， 称r s 码为极大最小距离可分码， 简称md s 码。如果我 们要设计 一个8 = 9的r s 码， 显然此 r s 码的 冗余位为8 一 1 = 8 ， 能纠4 个错。 它的生成多项式为 g ( x ) = ( x + a ) ( x + a z ) . . . ( x + a ) r s码的编译码及其快速实现 电子科技大学硕士论文 3 . 2 r s码的编码方法 系统码的g矩阵为 g二 lp l 左边是k x k 阶单位方阵。这相当于码字多项式的第 n - 1 次至n - k 次的系数是信 息位， 而其余为检验位，即 c ( x ) = m ( x ) x + r ( x ) = 0 ( m o d g ( x ) ) 式中m ( x ) = m r -l x c -i+ -z x t -z + . . . 十 m , x + m o 是信息多项式， ( m ,_ ,， mm o ) 是信息位， 而 r ( x ) = r - -,x -c + r -r .z x -z + . . . + r ,x + r o 是检验位多项式，相应的系数就是码元的检验位。由上式可得 - r ( x ) = c ( x ) + m ( x ) x 三 m ( x ) x - ( m o d g ( x ) ) 所以 要 构造 用g ( x ) 生成的系 统码， 首 先必须 将 信息组 乘以x 后， 用 g ( x ) 除， 得到余式 r ( x ) ; 再将其各项系数取加法逆元， 变成 x - m ( x ) ;然 就得到了所要求的 检验位。因 此， 循环码系 统码的编码问 题就是以g ( x ) 为模的除 法问 题。 3 . 3 r s码的时域译码算法 3 . 3 . 1 解方程组法 g f ( q ) 上的 n ,k r s 码以。 ，。 z，。 为根， 它的生 成多项式 g ( x ) = ( x + 设 。 ) ( x + a z ) . . 一( x 十 a z ) , 。 是g f ( q ) 上的 本原域元素， t 是可纠错误个数。 发送码字 接收码字 错误图样 c ( x ) = q ( x ) g ( x ) r ( x ) = c ( x ) + e ( x ) 若信道产生t e ( x ) = e x + e -z x -2 + . . . . . . + e x + e 0 个错误，则 e ( x ) = y ,x + y , , x 0 + + y , x 一 艺y .x 其中y , e g f ( q ) : 错误 值 x : 错 误 位 置 由 伴随式定义: 梦= hr t = he t r s 码的 编译码及其快速实现 电y 科 技大学硕上论文 ，llwe.es.es，es.es，es，es，es，es 00艺:0八u袄00 尸一!lllllllllseil ，leeeeee井eeeeleeij .j勺.通，:1几 a矿 a - 口 卜 2 ( a 2 ) - ( a l t ) ” 一 ， ( a 2 ) n - 2 (a 2 , y - 2口2 产111十il -一 y ( a ) f , + 玖 ( a )+ + y , ( a ) y ( a 2 * ) , + 长 ( a ) , + . . . + y ( a 2 , ) f s ， 二 e ( a ) s z = e ( a 2 ) 卜，二.胜，.!1rwe.es，哥，1.l 一一一- 令a e ( a 2 ) s , = y x : 十 长 x 2 十 十 y , x , 二 艺长 凡 = y ( x , ) 2 1 + y 2 (x , ) 2 + . 一 + y ( x , ) , 二 i y ( x k ) 2 , .月 ，山 s rlll之.lllt j“切 m男 译 码 就 是 解2 t 个 方 程中 未 知 数y i,x i( 1 = 1 ,2 , - 二，2 t ) 先求错误位置x ; 定 义: 定 义“( x ) = ( 1 - x , x ) ( 1 - x 2 x ) 二( i - x ,x ) 为 错 误 位 置 多 项 式， 若 第k 个 错 误 位置x = x 扩 ，则。( x 之 ) = 0 。 求错 误位 置就是 求。( x ) 的 根。 展开 。 o ( x ) , ( x ) = n( 1 一 x ,x ) 二 1 一 ( x ,+ x 2 + . . . + x ,) x + ( x ,x 2 + x ,x , + . .+ x ,. , x ,) x 2 + _+ ( 一 1 ) x , x 2 . . . x ,x 令。 = - ( x ,+ x 2 + - - + x ,) r s 码的 编译码及其快速实现 电子科技大学硕士论文 a 2 = x i x 2 + x i x 3 + . + x ,_ i x , 。 = 一 1 ) x i x 2 . . . x 则。( x ) = 1 + 0 lx + 0 2x 2+ . . .+ 0 , x = n( 1 一 x i x ) 若x k l 为 错 误位置 则a ( x - 1 ) = 1 + v ,万， + a 2 x k 2 +一 + a , x k ， 二 0 两 边 乘 以 x ; x ; + a ,x 犷 ， + a 2 x ; 2 + . . . + a t = 0 两 边 乘y k x k j = 1 ,2 , . - - , t k = 1 , 2 , - - - y , x k + l + 6 ,y k x k 一 ， + 对 k求和: + a玖 叮 = 0 k = 1 , 2 , t 艺 y k x k a + a 1 1 y k x i + ,- i + . . . + a , i y k x i 二 0 艺 y k x k + , = s j+ t 众 - 1 s j+ ,+ a i s j+ ,.,+ . . . + a ,s j= o a is;., 卜.。 k = 1 , 2 ， 一，t 1十 + a ,s j= - s j+ l a , s , + 一+ o a, s , 几s , + , + + 氏s 2 “s ,+ , = s , + 2 71s2,-1+ 以矩阵形式表示: + a , s , i ml s 2 1 二 s 灿蝙szt - 氏几民 51气凡 s 卜 1 s , s 2 卜2 凡st+l:标 这 样 ， 由 伴 随 式明= 1 ,2 , - - , 2 t ) 可 解a ;( i= 1 ,2 , -二 ， t) 当有t 个错误产生，m满秩， 解方程可得解; 若 网卜0 ， 则 对 矩 阵m降 阶 ， 重 复 以 上 方 法 ， 直 到 得 解 ， 最 后， 可 得。( x ) = 1 + a ,x + a 2x z + . . + a ,x 得到a ( x ) ，利用钱氏搜索法， 解出。( x )的根， 就得到了各错误位置。 钱氏搜索:已知。( x ) ，如何简单地求出它的根， 得到错误位置， 是编码界 研 r s 码的编译码及其快速实现 电子科技大学硕士论文 究的 重要课题。 钱氏搜索是钱闻天提出的、 简便的求错误位置的方法，并一直 被编码界沿用至今。 钱氏搜索原理:解 。 ( x )的根，就是确定 r ( x ) 中哪几位产生了错误 r ( x ) = r , .,x 0 - + r , -2 x 2 + - 二 + r , x + r , ， 为了 要 检 验 第 一 位r o- ， 是否 错误， 相当 于 译 码 器 确 定。 ” 一 ， 是否是错误位置数，这等于检验a .(n - b是否是。( x )的根，则: 。( 。 “ ，) ) 二 o( 。 ) = 1 + a , a . . . . . . . + a 。 a = 0 或。 : 。 +一+ 。 。 a 1= 1 所以 得到。( x ) 后， 为了 译r , ) ,译码 器 首 先计 算。 ， 。 ， ，。 a ， 然 后 计 算它 们的 和 是否为1 ， 若是， 则。 n - 1 是 错 误位置， r . . ， 码 元是 错误的; 否 则r . - 、 是 正 确 的。 因 此 为了 译r . ,) 译 码 器 首 先 计 算。 ， 。 a 2 (1 ” ， 。 。 。， 并 计 算它 们 的 和，若 。 ， a ,+ a . a 8 + . . .+ o , a 0 = 1 r -、 有 错 。 , q ,+ a 2 a 2)+ - - + a t a 0 # 1 r -, 正 确 这样依次 对每 一个 _， ( 1 = 1 ,2 , - 二 ， n ) 进行检验， 就求得了。( x ) 的根。 再求错误值:( 对二元b c h 码， 此步可不作: 对非二元b c h码) 解 得 错 误 位 置x , x 2 ， 一 ， x , 后 ， 代 人s ， 二 艺ykjy k x k .，月，1.，es.卫es.es月， 51几凡 尸一leel 工l .，.口，.，.胜，j 芍玖耳 n“”u韭 气对x: 丸心戒 xl对:可 显 然这 是 一个 范 德蒙 矩阵， 只 有在x , # x 2 # . . . # x t # 0 ， 方程有 解。 当真实的 错误值小于i 时， 对矩阵降阶求解。 由一般译码原理可知，如系统纠错能力较小，由于三阶以下行列式计算比 较简单， 就能 很容易地通过代 数方法 译码。 通常情况下， 若产生一个错误， t = 1 , 则由上述原理可得: s , a ,= s :即a 。 = s , / s l ( x ) = 1 + ( s 2 l s , ) x 若产生两个错误，则 az 二 s . i r 6 . i r s . i s 2 j l 6 2 j l s u ) 又，喃:卜 其中m; = s ,. 1 ( i 司,2 , . - , t ) 已j4 s改 ，1 ss s ; . 1 s ;+ 2s 2 - 定理:如接收码字中含有p 蕊 t 个错误位， 则位于第a 位上 r ; 的出错的充 分必要条件是: 0 一 廿.月.卜月.月.几.! 又凡 j呢 s , 一 o f s 2 s 2 一 o f s 3 s 。 一 o f s n + 1 一 o f s 3 一 a f s , s ,一 “ f s n . 2 . . . . . . . n - 1 ) o s 厂o f s n + 1 s,+, 一 o f s n + 2 s , ， 一 ， 一 a f 5 23, 其中f = q - l - i ( i= 0 , 1 , 定理:如接收码字r 中的 错误位数“ -2 ,. 二 ， 2 t 处为 零。 若 码 字 在 传 输中 受 到干 扰， 错 误 图 样为e ( x ) , e = ( e ;i = 0 , 1 , ， n - 1 则 r t = t r t = t ( c t + e t ) = t c t + t e t = c + e 式中e 是e 的傅立叶变换， c是c 的傅立叶变换。 当i = l 2 . -, 2 t 时， e := r . 其余的马司由卜 式推出: 乓 十 e _ , a , + e_2 a z + . . . + 乓 一。 o b = q 式中a i( i = 1 , 2 , 二， b ) 是错误多项式a ( x ) 的系数。 求a ( x ) 的方法仍是迭代算 法，只是此时求。 ( x ) 是在频域内 进行的。 综上所述，r s 码的频域译码可概括成以下几步: 计 算 接收 矢 量r 的 傅 立叶 变 换r , 得 到2 t 个 伴 随 式s ;- r j 利 用b e r l e k a m p - m a s s e y 算 法 求。 ( x ) ; 由a ( x ) 和ss ， s ， 计算e ; 川(2)(3) ( 4 )求r - e的 逆变换， 得到正 确的码字c . 下面把时域译码和频域译码简单地对比 一下: ( 1 ) 频域译码中，在计算接收矢量的傅立叶变换时， 可采用不同形式的 快速傅立叶 变换算法， 而且随着 a s i c i f p g a的出 现， 结构，因而可以快速实现。 本文就是基于此。 频 域 译 码 更 适 合p i p e l i n e ( 2 ) 在频域译码中， 无需求出差错位置数和差错值， 从而减少了计算量。 3 . 5 频域译码的 计算机模拟 t 随机 数的 产生和信道的 模拟 在用计算机进行译码的模拟时，必须先产生均匀分布的随机数，以用来根 据信道的 模型产生能反映移动信道特性的差 错序列( e ; 。 在进行编码时， 也必须 产生随机数以 形成信息流。 采用乘同 余法产生编码信息流， 公式如下; r ; = x r ;( m o d m) 参数选择如下: m = 8 3 8 8 6 0 8 , 7 = 2 0 4 5 r = 8 3 8 8 6 0 7 . 用以 产生差错图样的随机数由 混合同 余法 产生， 其递推公式是: e ;. ， 二 入 e ;+ c ( m o d m ) 参数的取值如下:a = 9 . e = 3 6 5 4 7 2 , c = 6 4 5 7 2 3 ,m= 5 2 4 2 8 8 . r s 码 的编译码及其快 速实 理 电子科技大学硕上沦文 在 一定的置信度范围内，可以 接受上述两种方法产生的随机数是 ( o , 1 ) 区间上均匀分布的随机数的假设。 错误图样的形式完全受信道特性的影响。在用随机数产生错误图样时，根 据我们选用的ma r k o v 移动信道三状态模型， 判断各随机数判为0 或判为1 有限分群的ma r k o v 移动信道三状态模型参数: 0 , 9 9 5 6 6 3 1 5 0 0 . 1 6 5 5 0 0 6 2 0 0 . 7 3 8 0 9 8 1 4 0 . 8 1 7 0 4 5 5 2 0 . 0 0 4 3 3 6 8 5 0 . 2 6 1 9 0 1 8 6 0 . 0 1 7 4 5 3 8 6 rfleel.esl -一 飞f.，.，二.胜 凡几称 凡几气 君几几 一 p 产生错误图样的过程如下: ( 1 )任意指定一个初始状态s , ( s o = 1 ,2 ,3 ) : ( 2 )根据递推公式， 产生一个随机数r ,; ( 3 )确定本状态下的e 值， 同时对 下一状态的 转向 作出 判断: 若: = 3 ，则e ,= 1 ，而 1 ( 当 p , 1时) 2 ( 当 几 、 “ 凡 ， + p a z 时) 3 ( 当 七 凡 ， + 只 z 时) 州 若s j= j -,- 3 ，则e ,= o , 而 .j ( 当 r, p y 时 ) 3 ( 当 弓 之