（信息与通信工程专业论文）星用双模应答机中纠错编码技术的研究.pdf

国防科学技术大学研究生院学位论文 摘要 由于卫星信道传输特性不理想，并且叠加了大量噪声和干扰， 应答机与地面 站或用户星进行通信时， 数字信号会产生失真。 为了能正确恢复原始消息，引入 r s 码和卷积码的级联码进行差错控制。 论文首先分析了r s码编译码实现的关键技术。根据有限域以及实现平台的 特征，采用二表法实现有限域内的乘法运算，并设计了二表法对称编码器进行 r s 码的时域编码。 r s 码译码采用了频域译码技术， 伴随式的计算和错误值的求 解使用了 迭代算法进行了 简化。 在求解错误位置时， 根据经典的b m迭代算法本 文推导了一种简单算法， 并采用修正b m算法大大减少了迭代次数， 降低了运算 量，缩短了迭代周期。 卷积码采用分段编码和译码的方法，并以d s p为实现平台。本文鉴于d s p 便于字操作的特点， 设计了移位异或并行算法， 大大提高了编码效率。 在接收端， 采用软判决方法译码。 在分析网格图蝶形结构的基础上， 简化了复杂的分支度量 计算。 在加比选操作和幸存度量管理中， 本文采用了指针方法实现了加比 选和寄 存器交换，大大降低了时钟资源的开销，节省了存储空间。由于采用分段译码， 路径度量值是一个有限值，因此不存在度量溢出的问题。 数字信号通过卫星信道后， 译码器不能与发送信号建立同步， 因此在编码端 发送码组中插入了同步码组. 在接收端通过搜索同步码组确定数字信号的起始时 刻。 为了提高同步搜索速度， 降低同步建立时间， 本文采用了双路并行搜索机制 和并行异或相关算法。 【 关键字】 应答机，r s 码，卷积码，同步，有限域，幸存路径 绍i 页 国防科学技术大学研究生院学位论文 abs tract b e c a u s e o f t h e u n i d e a l t r a n s m i tt i n g c h a r a c t e r i s t i c o f s a t e l l i t e c h a n n e l a n d a l a r g e a m o u n t o f n o i s e s a n d i n t e r f e r e , t h e d i g i t a l s i g n a l w i l l b e d i s t o rt e d w h e n t h e t r a n s p o n d e r c o m m u n i c a t e s w i t h g r o u n d s t a t i o n s o r u s e r s a t e l l i a t e s . i n o r d e r t o r e s u m e o r ig in a l m e s s a g e s c o r r e c t l y , a c o n c a t e n a t e d c o d e , c o m p o s e d o f r s c o d e a n d c o n v o l u t i o n a l c o d e , i s i n t r o d u c e d t o c o n t r o l e r r o r s i n t h e r e c e i v e d s i g n a l . f i r s t l y , t h i s p a p e r a n a l y z e s t h e k e y t e c h n o l o g y w h i c h i s a d o p t e d i n r s e n c o d i n g a n d d e c o d i n g . a n d a c c o r d i n g t o t h e c h a r a c t e r i s t i c o f g a l o i s f i e l d a n d t h e p l a t f o r m w h e r e r s e n c o d i n g i s c a r r i e d o u t , m u lt i p l i c a t i v e o p e r a t i o n i n g f i s r e a l i z e d b y t w o - t a b l e m e t h o d . wi t h t w o - t a b l e m e t h o d a n d s y m m e t r y , a n e n c o d e r r e a l i z e d in t i m e f i e ld h a s b e e n d e s i g n e d . r s d e c o d i n g i s a c h i e v e d i n fr e q u e n t f i e l d . c a l c u l a t i n g t h e s y n d r o m e a n d s o l v i n g w r o n g v a l u e s i s s i m p l i f i e d b y u s i n g i t e r a t i v e a l g o r it h m . f o r d e t e r m i n i n g t h e w r o n g p o s i t i o n , t h i s p a p e r i n d u c e s a k i n d o f s i m p l e a l g o r i t h m f r o m t h e c l a s s i c a l b m a l g o r i t h m . a n d i t e r a t i v e t i m e s i s r e d u c e d g r e a t l y b y m e t h o d s o f m o d i f i e d b m a l g o r i t h m , w h i c h l e a d s t o r e d u c e o p e r a t i o n a l q u a n t i t y a n d s h o r t e n t h e it e r a t i v e p e r i o d . c o n v o l u t i o n a l e n c o d i n g a n d d e c o d i n g i s a c c o m p l i s h e d b y m e t h o d s o f fr a g m e n t i n g , r e a l i z e d i n d s p . s e e i n g t h a t d s p h a s t h e c h a r a c t e r i s t i c t h a t i t i s c o n v e n i e n t t o o p e r a t e b a s e d o n w o r d s , t h i s p a p e r d e s i g n s a p a r a l l e l s h i ft x o r a l g o r it h m t o r e a l i z e c o n v o l u t i o n a l e n c o d i n g , w h i c h h a s i m p r o v e d t h e e n c o d i n g e ff i c i e n c y g r e a t l y . i n t h e r e c e i v e r , s o ft j u d g e m e n t i s a d o p t e d i n d e c o d i n g . o n t h e b a s i s o f a n a l y z in g t h e b u tt e r f l y s t r u c t u r e o f t r e l l i s , c o m p le x b r a n c h m e t r i c c a l c u l a t i o n i s s i m p l i f i e d . i n a c s u a n d s mu s , t h i s p a p e r r e a l i z e s a d d - c o m p a r e - s e l e c t a n d r e g i s t e r - e x c h a n g e b y p o i n t e r , w h i c h r e d u c e s t h e r e q u i r e d t i m e a n d s a v e s t h e s t o r a g e g r e a t ly . b e c a u s e a d o p t i n g f r a g m e n t d e c o d i n g , t h e rou t e m e t r i c i s l i m i t e d w h i c h m a k e t h e m e t r i c o v e r f l o w u n c o n s i d e r e d. a ft e r d i g i t a l s i g n a l p a s s i n g t h e s a t e l l i t e c h a n n e l , d e c o d e r c a n t s y n c h r o n i z e w i t h t r a n s m i t t e d m e s s a g e . s o s y n c h r o n i z i n g c o d e g r o u p s a r e i n s e rt e d i n t r a n s m i t t e d c o d e g r o u p s . t h r o u g h s e a r c h i n g t h e s y n c h r o n i z i n g c o d e g r o u p i n t h e r e c e i v e r , t h e s t a r t i n g m o m e n t i s d e t e r m i n e d . f o r r a i s i n g s e a r c h i n g s p e e d a n d r e d u c e s y n c h r o n i z i n g s e tt i n g t i m e , t h i s p a p e r p r o p o s e s a m e t h o d t h a t s y n c h r o n i z in g c o d e g r o u p s a r e s e a r c h e d in t w o w a y s in t h e s a m e t i m e a n d t h e r e l a t i v i t y b e t w e e n s y n c h r o n i z i n g c o d e g r o u p a n d r e c e i v e d c o d e s e q u e n c e i s c a l c u l a t e d b y p a r a l l e l x o r a l g o r i t h m . k e y wo r d s t r a n s p o n d e r , r s c o d e , c o n v o l u t i o n a l c o d e , s y n c h r o n i z e , g a l o i s f i e l d s , s u r v i v i n g r o u t e - 不薪 不于一一一一一一一一 一 一 ， 一一 一 独创性声明 本人声明所呈交的学位论文 是我本人在导师指导下进行的研究工作及取得 的 研究 成果。 尽我 所知， 除了 文中 特 别加以 标注和致谢的 地方外， 论文中 不 包含 其 他人已 经发表和撰写过的 研究 成 果， 也不 包含为 获得国防 科学 技术大学 或其它 教育机构的学 位或证书而 使用过的 材料。 与我一同 工作的同志 对本研究 所做的 任 何贡献均已 在论文中作了明确的说明并表示谢意. 学位论文题目:星 用双 模应 答 机中 纠 错编码 技术的 研究 名 : 夸、虱 华。 期 : ， 年， 月 : h 学位论文版权使用授权书 本人完 全了 解国防 科学技术大学有关 保留、 使用学 位论文的 规定。 本人授权 国防 科学技术大学可以 保留 并向国家有关部门或机构送交论文的复印 件和电子 文 档， 允许论文 被查阅 和 借阅; 可以 将学 位论文的 全部或部分内 容编入有关 数据 库进行检索， 可以 采用影印 、 缩印 或扫描等复制手段保存、汇 编学 位论文. ( 保密学 位论文在解密后适用本授权书. ) 学位论文题目: 学位论文作者签名 作者指导教师签名 国防科学技术大学研究生院学位论文 图目录 图 1 . 1双 模 式 应 答 机 功 能 框 图 . . . 1 . ， ，一 3 图2 . 1 有限域加法器基本结构， . 卜 . . . . . . . . . . . . . . . . . . . . . . . ， 二 ， .， . . . . 6 图 2 .2对 偶 基 法 实 现 乘 法 器 . ，、，一 9 图 2 .3剩 余 多 项 式 实 现 框 图 二 ，二 ， ， ，. i i 图2 .4 二表法对称r s 编码器. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 图 3 . 1卷 积 编 码 串 行 编 码 器. .， ， ， . 1 9 图3 .2卷 积 码( 2 , 1 ， 3 ) 编 码 器 ， . ，. . . . . . . . . . . . 2 1 图3 .3卷 积 码 状 态 转 移图. ，.一 ， ，. . . . . . . . . . . . . . . 2 2 图3 .4 ( 2 , 1 , 3 )卷积码状态转移图 卜 ， . ， 二 . . ， 二 ， ， .， ， . . . . . . . . . . . . . . . . . . . . . . 2 3 图3 . 5 ( 2 , 1 , 3 )卷积码网格图. . . ， 二 ，. . . . . . . . . . ， ， 二“ . . . . 2 3 图3 .6卷 积 码蝶 形图. . . . . . . . ， ，. . . . . . . . . . . . . . 2 4 图3 . 7 ( 2 , 1 ,3 ) 卷积码蝶形图. . . . . . . . ， . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2 4 图3 .8 卷积码 ( 2 , 1 ，7 )编码结构图. . . . . . . . . . . . . . . . . . . . . . . . . . . 卜 ， . . . . . . . . . . . . . . 2 5 图 3 .9 v i te r b i 译 码 流 程二 、 ， . ， . 卜. . . . . 】 ，、， 一 2 7 图3 . 1 0 v i t e r b i 译码器原理框图. ， ， ， ， . . . . . . . . . ， ，. ， . ， . . . . 2 8 图 3 .1 1 基 二 算 法 原 理 图 . . . ，. . . . .3 1 图 3 .1 2 基 四 算 法 原 理 图 . ，. 卜 卜 . ， 一 “ ” 一 “ . . . . . . . . .3 1 图3 . 1 3基二算法的加比选单元 ， 二 . . . . . ， ， ， .， 二 ， .， . . ， 二 ， 二 二3 2 图3 . 1 4 l l n的卷积码的蝶形图. . . . . . . . . . . . . . ， . . . . ， . ， . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 图 3 .1 5 寄 存 器 交 换 过 程 . ，. ， ，. .3 4 图3 . 1 6 ( 2 , 1 , 7 ) 卷积码蝶形图. 卜 . . . . . . . . . . . . ， ， 二 ， 二 ， .， . . ， . . . . . . . . . . . . 3 6 图3 . 1 7 ( 2 , 1 ,7 ) 卷积码分支度量单元卜. . . . . . . . . . . . . . ， ， . ， .， . ， ， 卜 二 3 6 图3 . 1 8 ( 2 , 1 ,7 ) 卷积码蝶形加比 选单元， 一 ， ， :价 . ， . . . . . . . 3 7 图3 . 1 9 ( 2 , 1 ,7 ) 卷积码蝶形幸存度量管理单元. . ， . ， . . . . . . . . . ， . ， 二 . ， 二 3 7 图3 .2 0卷积码 ( 2 , 1 ，7 )译码器. . . . . . ， ， .， . . . . . . . . . . ， ， ， . ， 二3 9 图4 . 1帧 同 步 码 的 插 入 方 式. . ， . . . .， . . . 一 4 0 图4 .2 级联码同步码插入点. 卜. ，二 ，. . . ，二 ， . .， ， . ， . ， ， ， ， 卜 ， ，. . . . . 4 2 图4 .3 同步码自 相关函数. . . . . . . ， ， ， ， ， ， 二 ， ， . ， . ，. ， ， . . ， . . . . . 4 3 图4 .4 级联码结构. . ， ， ， . ， ， . ， . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 7 图4 .5 卷积码译码总体流程图 . . . . . . . . . . ， . ， 二 ， . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8 图4 .6 分支度量流程. . ， . ， . . . . . . . 卜. . . . . . . . . . . . . . . . . 4 8 图4 . 7 加比选流程. ， . . . . . . . . . . . . ， . ， . ， . . . . ，. . . . . ._ 4 8 图4 .8 幸存度量管理示意图. . . . . . . . . . . . . . . . . . . . . . . . . . . . ， 二 ， ， . ， ， . ， ， . ， 二， 二 ， ， . ， ， 二 4 9 图4 .9 伴随式计算流程图. ， ，. ，二 、 . ， . . ， . . . . . . . . . . . . . . . . . . . . . . . . . . ， 二 5 2 图4 . 1 0错误位置多项式流程图 ， 二卜 . . . . . . . . . . . . . . . . . . . . . _ 5 2 图4 . 1 1错误谱多项式流程. . . . . . . 一， ， ， ，. ， .一 ， ， ， ， ， . ， ，.， 价 一 ， ， ， 卜 5 3 图4 . 1 2级联码仿真性能图 . 卜 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 第 i i i 页 国防科学技术大学研究生院学位论文 第一章 绪论 1 . 1 课题研究的背景 1 9 4 8 年美国科学家香农发表了 通信的数学原理 一文， 奠定了现代信息论 的基础， 他的理论核心是:当信息传输率小于信道容量时， 通过适当的编码， 可 以 实现高效无误的信息传输。 根据这个理论， 很多人在编码方面做了大量的工作， 在信道编码方面取得了很大进展， 对它的 研究也成为信息论的一个重要分支， 并 且很多研究成果己 经被大量地运用到通信系统的设计和实现中。 随着数字通信技术特别是数字卫星通信技术的发展， 以 及数据信息传输及交 换、 处理和存储用的大规模、 高 速数据网的出 现， 根据不同的通信业务， 人们对 误码率提出了不同的要求。 一般来说降低误码率可采取两方面的措施: 一是降低 信道本身引起的误码率， 选择合适的数据传输线路， 改善信道的传输特性， 提高 信噪比， 采用均衡技术，选用抗干扰性能较强的调制方案，改善信道带宽性能。 二是采用差错控制， 即纠错编码技术。 纠错编码使得传输的信息序列通过编码器 以 一定的 规律产生相关性强的码序列， 然后经信道传输。 由 于噪声和干扰的影响， 将导致码序列出 错， 而接收端能够利用编码规律检查码序列的相关性是否受到破 坏， 从而按照一定的译码规则自 动实现纠错和检错， 以 较低的误码率恢复原始序 列， 提高通信的可靠性。 采用纠错编码技术后， 对原始的信息码元增加了冗余码 元，若要提供相同的信息量，则要求传输速度和译码速度都有一定程度的提高。 所以， 在译码器的设计过程中， 传输速率也是一个关键问题。 纠错编码理论正是 在这样的应用背景下得到了发展。 目 前我国的卫星遥测通信系统大多采取提高发射功率来获得高信噪比， 降低 信 道 误 码率， 从 而 获得 较 好的 通 信 质 量， 然而 考虑 到卫 星 遥测 信道的 带 宽 相对 而 言不是很紧张， 但星上的空间很紧张， 要求达到小型化和低功耗， 因此可以 采取 适当的 信道编码，能达到同样的效果而同时大大地减少对信道信噪比的要求。 1 . 2课题研究的来源及意义 在我国，正在使用的遥测遥控系统是统一载波体制即u s b 系统，能够支持同 步轨道、中低轨道航天器的测控任务。虽然u s b 系统能够满足目 前及今后一段时 间内大多数任务的需要， 但是该系统本身所存在的许多不足， 如抗干扰性能很差， 第 i 页 国防科学技术大学研究生院学位论文 对中低轨航天器的轨道覆盖率低 ( 小于1 5 %) ，数传速率低 ( 最高反向数传速率 为2 m b p s ) 等，将会成为制约我国航天事业发展的不利因素。只有建立中继卫 星系统才是提高覆盖率和实时性的根本途径。 数字中继卫星系统可同时为多颗在 轨中、 低、高度航天器 ( 卫星、飞船、空间站等) 提供近连续覆盖， 反向数传速 率高并能精确测轨。因此，发展数字中继卫星系统 ( t d r s s )也成为航天测控 网发展的必然趋势。当前的世界航天测控网正经历着从地基网向天基网的发展。 鉴于我国的现状， u s b系统还将在相当长一段时间内继续发挥作用，而且 t d r s s 在导弹测控或航天器发射测控应用中，由于受到路径衰减大及多径干扰的 影响， 在许多场合下仍要用u s b 系统进行测控。 因此， 为了在将来建立数字中继 卫星系统做好准备并解决两种工作体制共存的问题， 研制一种兼容两种工作体制 的用户应答机是非常必要的。这种用户应答机既可以与传统的u s b地面测控站 配合完成传统的t t 接 收 支 路中 ， 进 入 译 码器的 速率为4 k b p s 左 右， 而 译 码输出 速率 为2 k b p s 。 来自 台站的前向 链路信号工作于扩频模式或 p m 模式，经天线进入接收支 路， 经简单处理后， 根据模式识别电 路提供的 信号进行判决， 进入相应的 模式解 调支路进行解调，解调信号通过卷积译码单元和r s 译码单元译码输出。 第 2页 国防科学技术大学研究生院学位论文 发送支路将输入信号进行通过r s 编码单元和卷积编码单元进行信道编码， 并通过模式选择某种调制模式进行调制形成返回链路信号，发送到台站。 图1 . 1中示出了双模式应答机的基本功能框图，并给出了编码单元和译码单 元在整个应答机中的位置，上图为发射支路，下图为接收支路。 图1 . 1 双模式应答机功能框图 互 1 . 4本文主要工作 对星用双模应答机中r s 码和卷积码的编码和译码的进行方案设计和实现， 并给出帧同步码组的设计与实现方法。本文的结构安排为: 第二章 r s 码编译码的设计。 从理论上分析了r s 码的编译码，并给出设计 方案，给出了基于二表法的对称编码器; 第三章 卷积码编译码的设计。分析了卷积码的实现原理，设计了卷积码的 实现方案。 第四章 帧同步码与级联码的实现。简要分析了帧同步码，并给出了帧同步 码的实现结构，以及适合于d s p实现的快速搜索方式。根据经典b m迭代算法 推导了计算错误位置多项式的一种简单算法。基于 d s p的特点，设计了快速并 行的编码结构，提高了卷积码的编码效率，并且采用指针的方法大大降低了 v i t e r b i 译码器中大量的寄存器交换， 不仅降低了存储空间的需求， 而且节省了时 钟开销。 第3页 国防科学技术大学研究生院学位论文 第二章 r s 码的编译码设计 r s ( r e e d - s o l o m n )码首先是由里德 ( r e e d )和索洛蒙 ( s o l o m n )于 1 9 6 0 年应用ms多项式构造出来的，是二进制b c h码的多进制推广，也是一种典型 的代数几何码， 具有很强的纠错能力， 不仅可以纠正随机错误， 还可以纠正突发 错误。 该码的一个很重要的特点就是其最小距离d为监督码元数r = n 一k加l . 达到了s n g l e t o n 限， 这是一个线性码所能达到的最大最小距离， 从这个意义上讲， r s 码是最佳的， 因此也称为极大最小距离可分码， 简称md s ( ma x i m u m d i s t a n c e s e p a r a b l e ) 码。 r s 码 是建 立 在有限 域g f ( 2 与上， 。是 任意 正 整 数， 且 具 有极 大最 小 距离 特性， 它卓越的纠错能力使得它在工程应用中引 人注目 。 r s码除了 译码设备略 复杂之外， 它的卓越的纠错能力， 无论是纠突发错误还是随机错误的能力，以及 它的译码速度，均是其它码类所无法比拟的。近年来，r s码不断地被应用到在 短波、无线通信和有线通信， 第三代移动通信标准家族 i mt -2 0 0 0中最重要的 标准之一的wc d m a中的高质量业务就采用了 在卷积编码的基础上增加 r s 编 码或采用t u r b o 码的编码方法。 另外， 在计算机存储系统的纠错技术中也广泛采 用r s 码，包括高速计算机存储器以 及磁盘和光盘，如i b m1 3 6 0计算机序列光 盘存储器中采用了r s ( 3 6 6 , 3 0 0 ) , d i g i t i a l c y p re s s 中采用了 缩短r s ( 6 1 , 5 0 ) . 2 . 1有限域上的代数运算 由于r s 码的码元是取值有限域， 所以r s 码的编译码中不可避免地要涉及 有限域上的代数运算， 包括有限域加法运算、 乘法运算和除法运算以及求逆运算。 这些基本的代数运算是r s 码编译码算法实现的基础和关键， 如何简单快速地实 现这些代数运算关系着 r s 编译码算法的实现速度。下面对此进行论述。 定义 2 . 1 2 1非空元素集合f， 足下述公理: ( 1 ) f关于加法构成阿贝尔群， 若f中定义了加法和乘法两种运算，且满 其加法恒等元记为0 ，且唯一 a+0-a ( 2 ) f中非零元素全体对乘法构成阿贝尔群，其乘法恒等元记为1 ，且唯一 axl 二a ( 3 )加法和乘法间满足分配律: 第 4页 国防科学技术大学研究生院学位论文 a x ( b + c ) = a x b + a x c ( b + c ) x a = b x a + c x a 则称集合f是一个域。 很明显，域是由符合加法和乘法两种运算的一些元素组成，而且域内元素满 足以下条件: ( 1 )域内的两种运算都是封闭的，即域内任何两个元素之和或积仍在域内: ( 2 )域内每个元素a 都有一个唯一的加法逆元一 a, a + ( - a ) = 0 ( 3 ) 任何 一个 非 零 元素a 时， 都 有一 个唯 一 的 乘 法 逆元a - ， 存 在， a x ai = 1 . 域内 元 素 数目 叫 做域的 阶， 可为 有限 或 无 限。 有限 域以g f ( q ) 表示， 也 称 为 伽罗 华 域，q 是域内 元素 数目 。 对 任何的p . ， 都存 在一 个 有限 域g f ( p ) . 这 里p 是 个素 数， m为 整数。 有限 域最 简 单的 例 子就 是素 域g f ( p ) ， 由 全 部 模 p 的 整 数 集 合组 成， p 是 大 于1 的 任 何 一 个 素 数， 加 法与 乘 法 运 算都 是 模p 的 。 将若干个乘法恒元相加， 能产生加法恒元的所需的最少乘法恒元的数目， 叫做域 的 特征， 很明 显，g f ( p ) 的 特征是p 定义 2 .2 2 1域中非 零元素 所构成的 乘法群之阶 称为域中该 元素的 级。 若 g f ( 的中 某 一 元 素 的 级 为q 一 1 ， 则 该 元 素 称 为 本 原 域 元 素。 有限 域的 一 个 重要 性 质是 每 个 有限 域g f ( q ) 至少 包括一 个 本原 域元 素a。 该 元 素的 小 于q 一 1 的 任 意次 幂都 是 该 域中 非 零 元 素， 且 互不 相等， 就 是说，域 中 任一个非零元素可表示为a的前q 一 1 个幂次。 定 义2 .3 12 11 系 数 取自 g f ( p ) 上的以 g f ( p ) 中 本原 域元素a 为 根的 最小 多项式，称为本原多项式，且最高次为是m次的。 设g f ( p ) 的 本 原 多 项 式 为 f ( x ) = x + a , - , x ， 一 + 十 a ix + a , ， 有 f ( a ) = 0 ， 得 到 关 系 式 a + a m - , a ， 一 十 + a ,a + a o = 0 , a 二 g f ( p ) 。 由 域乘法运算知道，域中任何一个高于m- 1 阶的非零元素有递推式 a _ 气 一 产 r- i + . 二 十 % a ,- m 。 因 此 域 内 任 一 元 素 都 可 表 示 为1 , a , ，二 ， a ， 一 ， 的 线 性 组 合 。 如 果 将 g f ( p ) 看 成 一 个 矢 量 空 间 ， 那 么1 , a ， ， a m - 就 是 该 空间的一组基， 称为自 然基底， 而域中元素的基的线性表示就是该元素在基上的 投影，形成一个矢量，由该矢量可以完全地表示域中的元素。 第 5页 国防科学技术大学研究生院学位论文 域g f ( 2 8 ) 的 本 原 多 项 式 为 f ( x ) = x 8 十 x 7 + x 2 十 x 十 1 ， 它 的 递 推 式 为 a = a - + a - 6 十 a - 7 + a - 8 ， 自 然 基 为1 , a ， ， a 7 。 g f ( 2 8 ) 中 元 素 澎 就可以表示为矢量 ( 1 0 1 0 1 1 0 1 ) . 2 . ， . 1加法器的设计 r s 编 译码中 大量地应用伽罗 华域g f ( p , ) 的 加法运算， 不存在进位， 所以 伽罗华域中的加法运算比算术加法运算更为简单。 通 过上 面的 分 析，g f ( p ) 中 的 任 何一 个 元 素都 可以 表示 为一 个矢 量， 因 此要对两个元素的相加， 只需要将元素的矢量表示按位异或， 结果是域空间内的 另一个矢量。设域内任意两元素a,b.c，它们的矢量表现形式分别为 a = ( a o a l . . . a . - 1 ) b = ( b o b , . . . b . - 1 ) c= ( c c 1 . . . c . - i ) 若c= a + b， 则 有c i = a i o乓 ，a ; , 乓 , c ; e g f ( p ) ，i 二 0 , 1 , . . . , m一 1 。 111 如 : g f ( 2 $ ) 中 元 素 a 8 二( 1 0 0 0 0 1 1 1 ) , a 1 1 = ( 1 0 1 0 1 1 0 1 ) c = a s + a = ( 0 0 1 0 1 0 1 0 ) = a 。 加 法 器 的 基 本 结 构 如 图2 . 1 0 a m - 1 a m - 2a m - 3a ,a o 队 月 匕 : 软 : 厂 巨 厂到、 厂 一 b . _ 2 b . - ,b , b o c m - 1c m _ zc m - 3 c tc o 图2 . 1有限域加法器基本结构 2 . 1 . 2乘法器的设计 由 前 面 的 分析 可 知，g f ( p ) 上的 元 素 既 可以 表示 为 矢 量 ( 即 多 项 式) 的 形式， 也可以 本原域元素的幂次给出。 以不同的方法设计出来的乘法器在运算速 度和运算量上都有很大的区别。 1 .系数法 实现乘法器最传统和直接的方法就是两元素的多项式直接相乘， 将乘积转化 为自 然基表示，得到乘积的矢量表示。 设q和y 有限域内的任意两个非零元素，它们的乘积表示为: 第 6页 国防科学技术大学研究生院学位论文 刀x y=( a p + a l a + a 2 a 2 而十 a l a 十 杰护 + . . . + a ,- la m - 1 ) x ( b o + b la + b 2 a 2 + + b,_1 a m - 1 ) 十 十 a m - l a m - 1 洲艺k=j a ， 二 y- a , b 一 ， + f_ c ，m ， 一 ，a k b n e + l - ,- k e g f ( p ) ，刃表示元素a 矢量表 示的 第 维 元 素 计 算 艺 a , b ,- i 和 / = 0 艺a k b + 、 一 】一 * 时 ， 可 以 先 将 (b - ,b m - 2 . . .b ub o ) 移 位 ， 与 k = j ( a 。 一 ，a m - 2 . . . a , a o ) 相 与 后 异 或 得 到 。 计 算 可 得 运 行 一 次 乘 法 平 均 所 需 的 与 运 算 为 ( m ， 一 2 m + 4 。 一 1 ) / 2 。 2 、类乘法 系数法虽然只有与和异或操作， 但是系数的运算复杂， 而且运算量大。 据此， 本文对系数法加以改进， 得到一种新的方法， 这里称之为类乘法， 因为其实现类 同于实数域中的一般乘法规则， 只是在进行相加时不考虑进位。 类乘法可以大大 降低运算复杂度和运算量。 ,6 x y = ( a , + a ,a + a 2 a 2 + . . . + a 。 一 。a 一 ， ) x ( 6 a + b ,a + b 2 a 2 + 一 + b . - , a 一 ， ) = b 9 十 b ,a 十 凡 。 ， + 十 b , . - , a 2 m - 2 十 q b i 川 式中，b , = + . . . + a - ,瓦m + , i ? m ，i = 0 , 1 ， 二 ， 2 m一 2 ，b , e g f ( p ) 。 将 式 中 位 置b ; 不 为 零 上 的 a , 按 位 异 或 ， 即 得 到 了 乘 积 值。 以 g f ( 2 ) 上 的 a lo x a 为例进行说明，作如下运算: 1 1 1 0 x 0 1 1 1 i 1 1 0 i 1 1 0 由 1 1 1 0 1 0 1 0 1 0 则b , = 几“ b s = 卜其 它b ; = 0 , 所以 a i o x a l l = a+ a + a 5 二 0 0 1 0 田1 0 0 0 00 1 1 0 = 1 1 0 0 = a 6 很明显，类乘法的乘法规则实际上就是根据一个乘数中 “ 1 ”码的位置对另 一个乘数移位后进行异或运算的过程，最大移位不超过m一 i 位，因此移位的次 数也就不超过、- 1 次，而且不存在与运算。将类乘法与系数法比较可以发现， 两者都是采用了多项式表示形式，但是最大的区别是在计算时，高m- 1 个元素 展开的时刻和方式不同。比较可知， 类乘法的运算量要大大小于系数法， 平均只 需要，一 1 次异或运算和，一 2 次移位。 第 ， 页 国防科学技术大学研究生院学位论文 三、二表法 g f ( p m ) 上乘 法 运算 是 封闭 的， 而 且 域内 任 一 非 零 元 素都 可以 表 示为 本原 域 元素a的指数形式， 因此， 域内中任何两个非零元素的乘法运算都可以转化为指 数的加法运算。 a x a =a i+ j = a ( i+ j ) m o d p 由于零元无法表示为a的幂次， 因此与零元相乘时不能采用指数的方式， 可 以通过判断，然后直接输出零或者不参加运算。 要将乘法运算转化为指数的加法运算时需要在元素与指数之间进行转化， f l 此需要建立两张数据存储表，即元素表和指数表，指数表用于根据a 来查找指 数i ，而元素表则是由 指数i 来查找对应元素岔。由于元素和指数是一一对应， 而且指数和元素都是连续分布的， 因此可以直接采用连续的元素和指数分别作为 指数表和元素表的偏移地址， 查找时 可以 迅速定位。 因此作乘法运算时， 首先找 到乘数和被乘数的指数表示， 再将两者相加求模得到乘积的指数， 差表即可得到 对应的乘积值。 很明显，二表法不需要任何与或移位运算，只涉及到一次算术加、一次模 运算以 及三次查表操作， 计算量大大降低， 无论是软件实现还是硬件实现都比较 方便，但是制表存储量比 较大，随二呈指数上升。 四、 对偶基法4 1 3 5 1 g f ( p m ) 上自 然 基 为 ( l , a ， 一 ， a . - i ) ， 对 偶 基 为 ( 几， 八 ， 风- 1 ) o g f ( p ) 上 的 迹 定 义 为 t r ( a ) = a + a p + a p 2 + - - - + a p m -i 。 g f ( p ) o x ，y 为g f ( p ) 上任两 个元素， 令 二 = x 0 + x la + x 2 a 2 + _ 二 十 x r la m - i , y = y o 几+ y ,乃+ 乃 几+.二 + y . - i几 一 ， z = x y = ( x o + x la + x 2 a 2 + . 二 + x . - ia m - i ) (y o a o + y a + y 2 a 2 + . 二 十 y . - ,)6 .