（微电子学与固体电子学专业论文）容错ip核的软硬件协同设计.pdf

上海人学硕士学位论文 摘要 片上系统( s o t ) 是集成电路( i c ) 飞速发展的产物，它满足了市场对芯片成 本、面积、功耗及上市时间的要求。为了保证s o c 功能和时序的正确，需要在 设计过程中对s o c 进行反复验证。然而，s o c 设计复杂度的日益提高给s o c 的验证带来了极大的挑战。 单从硬件角度设计s o c ，因为硬件结构调整不灵活，使得需要花更长的时 间进行设计和验证；单从软件角度考虑验证问题，软件的不稳定性给设计增加 了许多不确定因素。软硬件协同设计正好结合了两方面的优点、弥补了彼此的 缺点。 软硬件协同设计的验证阶段是给出一个算法，该算法能自动寻找面向约束 条件的软硬件最佳折中点、并以此生成切实的系统架构。软硬件协同设计的方 法可以使软件设计者在硬件完成之前接触到硬件模块，同时可以使硬件设计者 尽早接触软件，因此，软硬件协同设计在减少s o c 的设计和验证时间上有着明 显的优点，使设计在早期进行系统级验证，减少了s o c 设计中的盲目性。正是 基于此考虑，本课题利用软硬件协同设计技术来实现容错d 核的设计与验证。 本文主要讨论了v i t c r b i 译码器容错口核的原理和实现方法、软硬件协同 设计的原理和软硬件划分原则、软硬件协同设计平台的构建、v i t e r b i 译码器容 错核的f p g a 设计过程、软硬件数据交换的通信接口设计和验证界面的开发 等，内容涉及到通信领域的纠错码、计算机领域的软硬件技术和i c 设计的相关 知识。开发工具和平台有m o d e l s i m 、s y n p l i f yp r o 、q u a r t u si i 、g n u 工具链和 a r m l i n u x 嵌入式设计平台。开发语言用到c c + + 、汇编语言和v e r i l o gh d l 。 本文根据软硬件划分算法的理论，自主开发了用于软硬件协同设计的系统 平台，并根据软硬件划分算法对平台进行了软硬件划分。在软件方面，我们利 用a r m l i n u x 平台，用图形界面窗口来产生测试激励，使验证方便而快捷； 在硬件方面，我们利用f p g a 平台，保证了容错m 核在较高时钟频率下运行。 软件平台和硬件平台之间通过通信接口进行信息交换，测试数据利用通信接口 v 上海大学硕士学位论文 在软件和硬件之间传递。从结果来看，用软硬件协同设计的方法来设计容错口 核比传统方法具有明显的优点，达到了我们期望的目标，对i c 设计新方法的探 索具有一定的参考意义。 关键词：协同设计，嵌入式系统，软硬件划分，维特比译码器，容错口核 v i 上海大学硕士学位论文 a bs t r a c t s o c ( s y s t e mo nc h i p ) i sb a s eo nt h er a p i dd e v e l o p m e n to fi n t e g r a t e dc i r c u i t s s o cc a nm e e tt h em a r k e td e m a n df o rc h i p sc o s t ，s i z e ，p o w e rc o n s u m p t i o na n dt i m e t om a r k e t i no r d e rt oe n s u r es o cf u n c t i o nc o r r e c t l y , i ti sn e c e s s a r yt ov e n f y r e p e a t e d l yo nt h es o c i nd e s i g np r o c e s s h o w e v e r , c o m p l e x i t yo fs o c d e s i g np o s e s ag r e a tc h a l l e n g ef o rt h et e s t i n go fs o c j u s tf r o mp e r s p e c t i v eo ft h eh a r d w a r e ，h a r d w a r ei sn o tf l e x i b l ef o rs t r u c t u r a l a d j u s t m e n t ，s oi tn e e d st os p e n dal o n g e rt i m ef o rd e s i g na n dv e r i f i c a t i o n ；j u s tf r o m p e r s p e c t i v eo ft h es o f t w a r e ，t h es o f t w a r ei sn o ts t a b l e ，s oi ti n c r e a s e st h e u n c e r t a i n t i e so fs o cd e s i g n h a r d w a r ea n ds o f t w a r ec o d e s i g ni sau n i o no f c o m b i n i n gt h ea d v a n t a g e so f b o t ha n do fm a k i n gu pf o re a c ho t h e r ss h o r t c o m i n g s v e r i f i c a t i o n s t a g eo fh a r d w a r ea n ds o f t w a r ec o - d e s i g ng i v e sa na l g o r i t h m ， w h i c hc a na u t o m a t i c a l l ys e a r c hf o rt h eb e s tc o m p r o m i s ep o i n to fs o f t w a r e - h a r d w a r e t of a c et h ec o n s t r a i n t s ，a n dg e n e r a t ee f f e c t i v es y s t e ma r c h i t e c t u r e t h ea p p r o a c ho f s o f t w a r e - h a r d w a r ec o - d e s i g ne n a b l e ss o f t w a r ed e s i g n e ra c c e s st ot h eh a r d w a r e m o d u l e ，a n dh a r d w a r ed e s i g n e r sa ss o o na sp o s s i b l ea c c e s st ot h es o f t w a r em o d u l ea t a ne a r l ys t a g eo fs y s t e m l e v e lv e r i f i c a t i o n s oi ti sp o s s i b l et od e c r e a s er i s ko ft h e f a i l u r e b a s eo nt h i sc o n s i d e r a t i o n ，t h es u b j e c tm a k e su s eo fh a r d w a r ea n ds o f t w a r e c o d e s i g nt e c h n o l o g yt oa c h i e v ef a u l t t o l e r a n ti pc o r ed e s i g na n dv e r i f i c a t i o n t h i sp a p e rm a i n l yd i s c u s s e dt h ep r i n c i p l eo fv i t e r b id e c o d e ra n dt h er e a l i z a t i o n o f m e t h o d s ，h a r d w a r e s o f t w a r ec o - d e s i g np r i n c i p l e sa n d t h e p r i n c i p l e o f h a r d w a r e - s o f t w a r ep a r t i t i o n i n g ，a r m l i n u xe m b e d d e dp l a t f o r m ，f p g ad e s i g no f v i t e r b id e c o d e r , t h ed e s i g no fh a r d w a r e - s o f t w a r ei n t e r f a c ea n dd e v e l o p m e n to f v e r i f i c a t i o np l a t f o r m t h ec o n t e n to ft h i sp a p e ri sr e l a t e dt oe r r o r - c o r r e c t i n gc o d e s ， c o m p u t e rh a r d w a r ea n ds o f t w a r ea n di cd e s i g nt e c h n o l o g y t h ed e v e l o p m e n tt o o l s a n dp l a t f o r m si n c l u d em o d e l s i m ，s y n p l i f yp r o ，q u a r t u si i ，g n ut o o lc h a i na n dt h e a r me m b e d d e dd e s i g np l a t f o r m t h ed e v e l o p m e n tt h e l a n g u a g e sm a k eu s eo f v i i 上海大学硕上学位论文 c c + + ，a s s e m b l yl a n g u a g ea n dv e r i l o gh d l b a s e do nh a r d w a r e - s o f t w a r e p a r t i t i o n i n ga l g o r i t h mt h e o r y , w ed e v e l o p i n d e p e n d e n t l yt h es y s t e mp l a t f o r mf o rh a r d w a r ea n ds o f t w a r ec o - d e s i g n i nt e r m so f h a r d w a r e ，w ed e v e l o pag r a p h i c a li n t e r f a c ew i n d o wt og e n e r a t et h et e s ts t i m u l u s ；i n t e r m so fh a r d w a r e ，w eu s ef p g ap l a t f o r mt oe n s u r et h ef a u l t t o l e r a n ti pc o r ea ta h i g h e ro p e r a t i o nc l o c kf r e q u e n c y s o f t w a r ep l a t f o r ma n dh a r d w a r ep l a t f o r m s e x c h a n g ei n f o r m a t i o nt h r o u g ht h ec o m m u n i c a t i o ni n t e r f a c e ，a n dt e s t i n gd a t ai s d e l i v e r e db e t w e e ns o f t w a r ea n dh a r d w a r e j u d g i n gf r o mt h er e s u l t s ，h a r d w a r ea n d s o f t w a r ec o d e s i g nh a sm o r ea d v a n t a g e st h a nt h et r a d i t i o n a lm e t h o df o rd e s i g no f f a u l t t o l e r a n ti pc o r ea n dr e a c ho u rg o a l so fd e s i g n i ti san e ws i g n i f i c a n tm e t h o do f i cd e s i g n k e y w o r d s ：c o d e s i g n ，e m b e d d e ds y s t e m ，h a r d w a r e - s o f t w a r ep a r t i t i o n i n g ，v i t e r b i d e c o d e r , f a u l t t o l e r a n ti pc o r e v i i i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 墨! b 日期：竺芏：兰：塑 上海大学硕上学位论文 1 1 课题来源 第一章绪论 在数字通信系统中，数据在传输过程中会不可避免地受到干扰而出现错误。 差错编码控制是数据在信道传输过程中的纠错技术，其中卷积码是一种应用广泛 的前向纠错编码。卷积码的译码通常采用v i t e r b i 译码器，它充分发挥了卷积码的 特点，使译码性能得到很大的提高。但是在设计v i t e r b i 译码器的时候，仿真验证 复杂，依靠复杂的公式推导去计算误码率等性能指标与实际的情况不一定吻合， 在短时间内设计出性能优越的v i t e r b i 译码器是非常困难的。 但是，s o c 技术的出现能解决这一问题。大规模集成电路的复杂度依照摩尔 定律即每1 8 个月单位元件数增加一倍的速度迅速发展，现在已经能够在单一硅芯 片上集成m c u 、m p u 、d s p 等模拟与数字混合电路，从而构成一个完整的系统， 这就是片上系统( s y s t e m o nc h i p ，s o c ) 。s o c 是2 1 世纪集成电路发展的必然趋 势，s o c 系统将原来由许多芯片完成的功能，集中到一块芯片中完成。s o c 系统 采用知识产权( i p ) 模块，但s o c 不是各个芯片功能的简单叠加，而是从整个系 统的功能和性能出发。 1 2 课题研究的目的和意义 s o c 系统芯片之间互连的复杂性和对时序的严格要求，给验证工作带来了麻 烦。验证在s o c 设计过程中所占的比重越来越大，已经达到7 0 。设计方法从 传统的电路设计转向系统设计，设计的重心也从逻辑综合、布局布线转向系统的 设计及仿真。在s o c 设计中，为了既可缩短开发周期，又能取得更好的设计效果， 软硬件协同设计技术能满足这一要求。软硬件协同的方法可以使软件设计者在硬 件完成之前接触到硬件模块，从而更好地设计硬件的驱动、应用程序、操作系统 等软件，同时可以使硬件设计者尽早接触软件，为软件设计者提供高性能的硬件 平台，减少了设计中的盲目性。 上海大学硕士学位论文 本课题从s o c 设计的角度出发，搭建了软硬件协同验证平台，该平台能方便 地对v i t e r b i 译码器的误码率性能指标进行验证，节约了仿真和验证的时间，使设 计达到了期望的指标，对以后的集成电路设计具有参考意义。 1 3 论文的主要研究内容 本文介绍了v i t e r b i 译码器的算法原理、软硬件协同设计与验证方法、软硬件 平台的设计方法、嵌入式软硬件系统的设计和用于系统级验证的验证界面，旨在 探究一种用软硬件协同设计的开发方法，并在此基础上开发用于软硬件设计的通 用平台，此平台不仅能实现对v i t e r b i 译码器的验证，还能够实现对其他i p 核的 验证。 第一章主要对本文相关内容作介绍； 第二章详细介绍了卷积码的编码方法及卷积码的译码方法，着重介绍了 v i t e r b i 译码器的原理及其算法，并讨论了v i t e r b i 译码器用于容错i p 中的方法： 第三章介绍了软硬件协同设计理论，讨论了软硬件划分的原则和算法。根据 软硬件划分原则和嵌入式软硬件平台的特点，我们对系统进行了软硬件划分。根 据仿真验证的特点，我们把测试激励用软件来实现；根据v i t e r b i 译码器的结构和 容错口核的特点，我们把这部分用硬件来实现： 第四章是本文的主要内容，根据软硬件划分的结果，对软硬件的各个部分进 行详细的研究和设计。设计包括v i t e r b i 译码器的f p g a 实现、软件平台的构建、 软硬件通信接口的设计和硬件平台的设计； 第五章通过开发验证界面，很方便地对系统进行验证，我们得到了期望的结 果； 第六章是结论与展望。 2 上海大学硕上学位论文 第二章v i t e r b i 译码器原理及其在容错i p 核中的应用 2 1 卷积码基础 卷积码是1 9 5 5 年由爱里斯( e l i a s ) 提出的【l 】，它与分组码不同，分组码是把 k 个信息比特的序列编成n 个比特的码组，每个码组的n k 个校验元仅与本码组 的k 个信息元有关，而与其它码组无关。分组码译码时，也仅从本码组的码元内 提取有关译码信息，而与其它各组无关。为了达到一定的纠错能力和编码效率， 分组码的码组长度一般都比较大。编译码时必须把整个信息码组存储起来，由此 产生的译码延时随n 的增加而增加。 卷积码也是将k 个信息比特编成n 个比特，但k 和n 通常很小，可以以串行 和并行的方式进行传输，时延小。与分组码不同，卷积码编码后的n 个码元不仅 与当前的k 个信息有关，而且还与以前m 1 时刻输入的信息有关，通常将卷积码 记为( n ，k ，m ) ，其中，m 为编码约束长度，r = k n 是编码率。 卷积码的纠错性能随m 的增加而增大，而差错率随r n 的增加而指数下降。 在编码器复杂性相同的情况下，卷积码的性能优于分组码。但卷积码没有分组码 那样严密的数学分析手段，目前大多是通过计算机进行好的的卷积码的搜索。 2 1 1 卷积码编码器 下面通过一个例子来简要说明卷积码的编码工作原理。正如前面已经指出的 那样，卷积码编码器在一段时间内输出的n 位码，不仅与本段时间内的k 位信息 位有关，而且还与前面m 段规定时间内的信息位有关，这里的m - n 1 通常用( n ， k ，m ) 表示卷积码( 注意：有些文献中也用( n ，k ，n ) 来表示卷积码) 。图l 就是一个卷积码的编码器，该卷积码的n = 2 ，k = 1 ，m = 2 ，因此，它的约束长 度n n = n x ( m + 1 ) = 2 x 3 = 6 。 同样，在卷积码译码过程中，不仅要根据当前时刻输入到译码器的字码，还 要根据以后很长一段时间如m a 段单位时间内，收到的各子码，才能译出一个子 码信息元，通常i l l d 大于m 。我们称r n a + l = n d 为译码约束度。 3 上海大学硕士学位论文 输出2 b 3 图2 1 ( 2 ，l ，2 ) 卷积码编码器 在图1 中，d l 与d 2 为移位寄存器，它们的起始状态均为零。c l 、c 2 与b 1 、 b 2 ，b 3 之间的关系如式2 1 所示。 c l = 翻+ + 岛 e = b l + 6 3 、7 假如输入的信息为d = 1 1 0 1 0 ，为了使信息d 全部通过移位寄存器，还必须在信 息位后面加3 个零。 卷积码编码器可以看作是一个m e a l y 机，编码器的输出是当前状态和当前 输入的一个函数。它包括一个或多个移位寄存器和多个异或门。输入的信息数据 流入移位寄存器的输入端并且随后移入输出端。异或门与移位寄存器和当前的输 入相连，产生数据输出。这儿没有移位寄存器与异或门相互连接最佳位置的理论， 它是完全凭经验得到的。上述位置是由互连函数所决定的，这如同存储器单元数 量决定了最小汉明距离，最小汉明距离决定了一次能够纠正错误数据的个数。 2 1 2 编码器的子生成元表示 定义一个m 位的子生成元q ： g j = ( g j l ，g j 2 ”，固l 。”，g j m ) j = 1 ，2 ，n ( 2 2 ) 其中，子生成元是一个m 位的矢量，m 为移位寄存器的状态数，含有n 个子生成 元，a 为模2 和加法器的数目。通过编码率为r = k n 的子生成元很容易画出编码器 4 上海大学硕士学位论文 的框图。子生成元是指示模2 和加法器与m k 级移位寄存器状态之间连接方式的 符号。 如编码率为1 2 ，约束长度为3 的卷积码编码器，其子生成元为：g i = ( 1 1 1 ) ， g 2 = ( 1 0 1 ) 。 2 1 3 编码器的生成多项式表示 也可以用1 1 个生成多项式来表示一个卷积编码器，每个对应于n 个模2 和 加法器中的一个。这种方法和编码器子生成元表示法密切相关，因此可以很容易 地通过m 位编码子生成元g j 写出o j ( x ) ： 如编码率为1 2 ，约束长度为9 的卷积码编码器，其子生成元和生成多项式 的对应关系如下： g 1 = ( 1 1 1 1 0 1 0 1 1 ) g 1 ( x ) = l + x + x 2 + x 3 + x 5 + x 7 + x 8 ( 2 3 ) g 2 = ( 1 0 1 1 1 0 0 0 1 ) g 2 ( x ) = 1 + x 2 + x 3 + x 4 + x 8 ( 2 4 ) 2 1 4 编码器的状态图表示 还有一种方法可以非常有效地描述卷积码编码器的工作过程，即状态图表达 法。考虑图2 2 所示的( 2 ，1 ，2 ) 编码器。 输出2 图2 2( 2 ，1 ，2 ) 卷积码编码器 5 b 3 上海大学硕士学位论文 o o 图2 3 ( 2 ，1 ，2 ) 卷积码编码器状态图 编码器寄存器中任一时刻的存数称为编码器的一个状态，以s i 表示。对于( 2 ， l ，2 ) 编码器，编码存储为2 ，编码器由两级存储器组成。因此，存储器中的存 数只有4 种可能：o o ，1 0 ，o l 和1 1 ，相应于编码器有4 个状态：s o ，s 1 ，s 2 和s 3 。 随着信息序列的不断送入，编码器就不断地从一个状态转移到另一个状态， 并输出相应的码序列。如果把这种状态变化画一流程图，则此图就表征了编码器 的工作特征，这种图就称为编码器的状态图，图2 3 就是( 2 ，1 ，2 ) 编码器的状 态图。由图2 3 看出：若编码器的初始状态处于s o ，输入信息元为1 时，编码器 从s o 转移到s 1 状态，并输出分支1 1 ；若输入的信息元为0 时，则仍停留在s 0 状 态，输出分支o o ，如此等等。随着信息的不断输入，编码器就不断的从一个状态 转移到另一个状态，并输出相应的分支，组成对应于输入信息序列的一个输出码 序列。图2 3 中，实线表示输入为0 ，虚线表示输入为1 。 2 1 5 卷积编码器的网格( t r e l l i s ) 图表示 卷积编码器的状态表达法能够描述编码器在不同输入的信息序列下各个状态 之间的转移关系，但不能表示状态转移与时间的关系。为了表示这种状态转移与 时间的关系，可以使用网格( t r e l l i s ) 图。图2 4 所示是r = 1 2 ，m = 3 ，g i = ( 1 1 1 ) ，g 2 = ( 1 0 1 ) 的卷积编码器的网格图。 6 上海人学硕士学位论文 图2 4 ( 2 ，l ，2 ) 码l = 5 时的网格图 网格图中每一状态有两个输入分支和两个输出分支。在某一时间单位( 节点) i ，离开每一状态的虚线分支( 下面分支) ，表示输入编码器中的信息是1 ；而实 线分支( 上面分支) 表示此时刻输入编码器的信息是o ；每一分支上的2 个数字， 表示第i 时刻编码器输出的信息c i - ( c ：，c ；) ，因而网格图中的每一条路径都 对应于不同输入信息的输出码序列。 2 2v i t e r b i 译码算法 2 2 1 最大似然译码 卷积码概率译码的基本思路是以断续的接收码流为基础，逐个计算它与其他 所有可能出现的、连续的篱笆图路径距离，选出其中可能性( 概率) 最大的一条作 为译码估计输出，概率最大在大多数场合可理解为最大似然译码( m a x i m u m l i k e l i h o o dd e c o d i n g ，m l d ) ，与分组码的最大似然译码在原理上是一致的，但实现 方法略有不同，主要区别在于分组码是孤立地求解单个码组地相似度，而卷积码是 求码字序列之间的相似度【2 】。 如果所有的输入信息序列等概率，则通过比较各个条件概率( 也称为似然函 数) p i ：z i 矿) ，选择其中的最大者，就可以得到具有最小差错概率的译码。设z 是 7 上海大学硕士学位论文 接收序列，u 4 是可能的发送序列，如果u 满足公式，译码器就选择u 作为发送 信息序列： p ( ziu 埘) = m a x p ( ziu 删。)( 对所有的u “)( 2 5 ) 上式即为最大似然译码判决准则。 假定信道无记忆，帮噪声独立的影响各个码元，编码效率秀1 n 的卷积码的似 然涵数为： p ( z l u 研) = u p l 研肌) = n 兀p ( 孙修) ( 2 6 ) i = 1 i = l 户l 其中，z i 是接收序列z 的第i 个分支字，u 是网格图中的一条特定码序列 u ( 避) 的第i 个分支字，z 瑟是第压个码元，珏是u ；第j 个码元，每个分支毒撞个码 t 卅，f 埘 元组成。令s 为发送码元序列，r 为接收码元序列，r k = z i j ，s k = u ，其中k = j i ，表示序 列中的码元标号，设传送的序列共有l 个码元，则译码问题即是卷积码网格图中寻 找一条路径( 每条可能路径对应着一个码元序列) 使得式( 2 3 ) 取得最大值： 丌p ( r k l s 。) 七 此时对数似然函数定义为： e ( z l a “) = l o g p ( r k l s t ) 2 2 。2 v i t e r b i 译码算法原理和实现 ( 2 7 ) ( 2 8 ) 如前所述，虽然状态图能表示卷积编码器在不同输入的信息序列下，编码器 各状态之间的转移关系，但并不能表示出编码器状态转移与时问的关系。为了表 示这种状态与时闻的关系，我们用篱笆圈来表示卷积码编码的过程，如下图2 。5 y 一 所不： 8 上海大学硕上学位论文 0 图2 5 ( 2 ，1 ，2 ) 码l = 5 时的网格图 图2 5 是l = 5 ( 输入五个信息元) 、( 2 ，1 ，2 ) 卷积码的状态转移时间关系 图，它由节点和分支组成，共有u - m + 1 个时间单位( 节点) ，我们以o 至l 恤予 以标号。若编码器从s o ( 0 0 ) 状态开始，并且结束于s o 状态，则最先的m = 2 个 时间单位( o ，1 ) ，相应于编码器由s o 状态出发往各个状态行进，而最后m = 2 个 时间( 6 ，7 ) ，相应于编码器由各状态返回到s o 状态。因此，在开始和最后m 个 时间单位，编码器不可能处于任意状态，而只能处在某些特定状态，仅仅从第 m ( 2 ) 至第l ( 5 ) 时间单位，编码器可以处于任何状态之中( 即4 个状态s o ，s 1 ，s 2 ， s 3 中之任一个) 。 在篱笆图表示法中，每一状态有两个输入分支和两个输出分支。在某一时间 单位i ，离开每一状态的虚线分支，表示输入编码器的信息元m i = o ，即输入为0 ； 而实线分支表示此时刻输入至编码器的信息元m i = 1 ，即输入为1 。每一分支上 l2 的2 位数字，表示i 时刻编码器输出的子组c i ( c ，c i ) ，因而篱笆图中的每一 条路径都对应于不同输入的信息序列。 例如，输入至图中编码器的信息序列m = ( 1 0 1 1 1 0 0 ) ，则由编码器输出的码 序列c = ( 1 1 ，1 0 ，o o ，0 1 ，1 0 ，0 1 ，1 1 ) ，它相应于篱笆图中的一条路径。如下 图2 6 ： 9 上海大学硕士学位论文 o o q o j o | ooo i 图2 6 ( 2 ，1 ，2 ) 编码器输出路径 一般情况下，( n ，k ，m ) 卷积码编码器共有2 拥个状态，若输入的信息序列 长度是l k + m k ( 后m k 个码元全为零) ，则进入和离开每一状态的各有2 。条分支， 在篱笆图上有2 盯条不同的路径，相应于编码器输出的2 盯个码序列。编码器送出 的码序列c ，经过离散无记忆信道( d m c ) 传输后送入译码器的是序列r = c + e ， e 是信道错误序列。译码器根据接收序列r ，按最大似然译码准则力图找出编码 器在网格图上走过的路径，这个过程就是译码计算、寻找最大似然函数 m a x l 0 9 6p ( r c j ) j = 1 ，2 ，3 ，o eoooo 9 2 削 ( 2 9 ) 的过程，或者说译码器计算、寻找有最大“度量”的路径的过程，即寻找 m a x ( m ( r - c ，) )j = l ，2 ，3 ，2 削( 2 1 0 ) 的过程。式中，m ( r - c ) = l 0 9 6p ( r c j ) 是c j 的自然函数也称c j 的路径度量。 对b s c ( 二进制对称信道) 信道而言，计算和寻找有最大度量的路径，等价于寻 找与r 有最小汉明距离的路径，即寻找 m i nd ( r ，c ，) j = = 1 ，2 ，3 ，2 射( 2 1 1 ) 对二进制输入q 进制输出的d m c 信道而言，就是寻找与r 有最小软距 离的路径，此时的度量就是软判决距离。 但是用上述这些方法译码是难以实现的。例如l = 5 0 ，n = 3 ，k = - 2 ，则共有 1 0 。o，o：o。o 上海人学硕士学位论文 2 h ：2 1 0 0 1 0 3 0 个码序列( 或网格图上的路径) ；若m = 5 ，则( l + m ) = 5 5 。如果在一 秒钟内送出这k l = 1 0 0 个信息元，则信息传输率只有l o o b i t s ，这是很低的。但 即使是在如此低的信息速率下，也要求译码器在一秒钟内计算、l l 较i o 蛐个似然 函数( 或汉明距离、软距离) ，这相当于要求译码器计算每一似然函数的时间小于 1 0 删s ，这是根本无法实现的。更何况通常情况下l 不是几十，而是成百上千， 因此，必须寻找新的最大似然译码算法。 v i t e r b i 算法正是在解决上述困难中所引入的一种最大似然译码算法。它并不 是在网格图上一次比较所有可能的2 削条路径( 序列) ，而是接收一段，计算、比 较一段，选择一段最可能的码段( 分支) ，从而达到整个码序列是一个有最大似然 函数的序列。现在把v i t e r b i 译码算法的步骤简述如下： ( 1 ) 从某一时间单位j = h i 开始，对进入每一状态的所有长为j 段分支的部 分路径，计算部分路径度量。对每一状态，挑选并存储一条有最大度量的部分路 径及其部分度量值，称此部分路径为留选路径。 ( 2 ) 增加1 ，把此时刻进入每一状态的所有分支度量，和同这些分支相连的 前一时刻的留选路径的度量相加，得到了此时刻进入每一状态的留选路径，加以 存储并删去其它所有路径，因此留选路径延长了一个分支。 ( 3 ) 若j l 斗1 i l ，则重复以上各步，否则停止，译码器得到了有最大路径度量 的路径。 下面我们举一个简单的例子来说明v i t e r b i 译码算法的过程： 输入至( 2 ，1 ，2 ) 编码器的信息序列m = ( i o l l l 0 0 ) ，编码器输出的码序列 c = ( 1 l ，1 0 ，o o ，0 1 ，1 0 ，0 1 ，1 1 ) ，通过b s c 送入译码器的序列r = ( i o ，1 0 ， o o ，0 1 ，1 l ，0 1 ，1 1 ) 有两个错误，下面我们利用v i t e r b i 译码算法输出估计信息 序列m 和码序列c 。基于图2 4 的网格图，v i t e r b i 译码器接收序列r 的过程 示于下图2 7 中。 1 第1 时刻接收子码r 。= 1 0 土簿采攀颟士学垃论空 瞳 潮2 7 t 2 ；蒸星鬻瓣攘睫子舔g i = t 0 0 i毫 3 。辩3 瞄赫攘姨予褥l 萼，- - 0 0 0- 瀑2 , 7 2 d 1 囊 d 瀚 l 2 0 0 ) 2 ( o i ) 嵇鳓 雾 搬) 黧 0 0 1 ) 蘑 姆l 辩 蕊 姆ii ) 上海大学硕士学位论文 第4 时刻接收子码r 3 = 0 1 o 图2 7 3 23 4 第4 时刻接收子码r 。- - 1 1 o 图2 7 4 d 23 4 5 八 u 第6 时刻接收子码e = 0 1 3 ( 0 0 0 0 ) 3 ( 0 0 0 1 ) 3 ( 1 0 1 0 ) 图2 7 5 1 3 d 3 ( 1 0 1 0 0 ) 3 ( 0 0 0 0 d 2 ( 1 0 1 1 0 ) 2 ( 1 0 1 1 1 ) 上海大学硕士学位论文 0 i o o 1 l 23 o o ，务| 9 u ! o o 图2 7 6 7 第7 时刻接收子码民= 1 1 0i o o l l o ，- 。 。| o oo 一 dm 2 ( 1 0 1 1 l o o ) 图2 7 7 图2 7 画出了各时刻进入每一状态的留选路径及其度量值最小汉明距离，以及 与此相应的译码器估计的信息序列m 。当l + m = 7 个时刻以后，4 条留选路径只剩 一条，它就是译码器输出的估值序列c = ( 1 1 ，1 0 ，0 0 ，0 1 ，1 0 ，1 0 ，1 1 ) ，相应的 估值信息序列m = ( 1 0 1 1 1 0 0 ) 中的两个错误得到了纠正。 由图看出，在某一时刻，如时，进入状态的留选路径的确定过程可叙述如下：进 入状态的有两条路径：一条是由( o o ) 分支加上与此分支相连的前一时刻( 第2 时刻) 的留选路径c 0 1 = ( o o ，o o ) 连接组成的路径( c 0 1 ，0 0 ) = ( 0 0 ，0 0 ，0 0 ) ， 1 4 。o，o：o 上海大学硕士学位论文 d ( r 2 ，0 0 ) = d ( 0 0 ，0 0 ) = o ，因而d ( c 0 10 0 ，r o r l r 2 ) - - d ( c 0 1 ，r o r l ) + d ( r 2 ， 0 0 ) = 2 + 0 = - 2 ，所以该路径的度量值d 是2 ；另一条路径是由( 1 1 ) 分支加上与此 分支相连的前一时刻( 第2 时刻) 的留选路径c 0 1 - - - - ( 1 1 ，1 0 ) 连接组成的路径( c 0 1 ， 1 1 ) = ( 1 1 ，1 0 ，1 1 ) ，它的度量值d = d ( c 0 11 1 ，凡r l r 2 ) = d ( c o l ，凡r 1 ) + d ( r 2 ， 1 1 ) = l + 2 = 3 。根据最小汉明距离准则可得在第3 时刻s 0 的留选路径是c 0 1 2 = ( o o ， 0 0 ，0 0 ) ，它的度量值d = 2 。 在其它时刻及进入其余状态的留选路径的选择与此完全相同。若某一时刻进 入某一状态的两条路径有相同的度量，如第4 时刻，进入s 2 状态的两条路径( 1 1 ， 1 0 ，0 0 ，1 0 ) 和( 0 0 ，1 1 ，0 1 ，0 1 ) ，它们的度量值d 都为3 ，故可任选一条作为 s 2 状态的留选路径，在图中选( 1 1 ，l o ，0 0 ，1 0 ) 这种任意选的结果，并不会影响 最后结果的正确性。 能用有限状态组成的篱笆图描写其编译码过程的码称为网格或篱笆码，也称 为t r e l l i s 码，它是树码的一个大类。因此，卷积码是一类满足线形叠加原理、子 生成元不随时间变化的线形网格码。 2 3 基于v i t e r b i 译码器的容错状态机算法 近年来随着半导体集成度的不断提高，在超大规模集成电路( v l s i ) 中经常出 现软故障。软故障是随机的能自动恢复的非重现性的故障，恢复后不会留下与其 相关的物理缺陷，但它却会对超大规模集成电路的性能造成很大的影响。这种随 机出现的软故障就很有可能使有限状态机( f s m ) 电路进入死循环或跳出预定的循 环状态，而有限状态机电路在许多电路设计中是很关键的，那么在有限状态机上 实现容错技术是非常必要的。 关于有限状态机的检错和纠错方法，人们提出了很多方案，包括复制完整有 限状态机电路方法、m o u t o f - n 编码方法、汉明码编码方法等等。文献【3 】使用 m o u t o f - n 方法来对有限状态机的状态进行编码。还有一种叫免干扰的实时自检 测有限状态机设计方法【4 】，这个方法利用根据位状态编码来代替复制整个完整的 有限状态机，额外增加的硬件面积比复制整个完整的有限状态机这个方法增加的 1 5 上海人学硕士学位论文 面积最高能减少3 3 。再者文献【5 1 提到一种有效的部分自检测f s m 设计方法，基 于实时监测f s m 的状态转变。另外文献 6 】提出了一种f s m 的状态用汉明码编码 的自纠正控制单元设计，在同一时钟周期内，这种方法能够纠正一位错误和检测 两位错误。 2 3 1 算法思想 有限状态机( f i n i t es t a t em a c h i n e ，简称之为f s m ) 适合于程序复杂的有规律的 逻辑，它的另外一个名称是程序状态机。 根据输出信号产生方法的不同，状态机可区分为m o o r e 状态机与m e a l y 状态 机。m o o r e 状态机的输出只与目前的状态有关，而与输入无关；m e a l y 状态机则 和二者都有关。 图2 8 时钟同步的状态机结构( m o o r e 状态机) 出 出 图2 9 时钟同步的状态机结构( m e a l y 状态机) 图2 8 、2 9 分别表示的是数字电路设计中常用的m o o r e 状态机和m e a l y 状态 机时钟同步状态机的结构。其中状态寄存器是由一组触发器组成，用来记忆状态 机当前所处的状态。图中的f 和g 两部分都是纯组合逻辑。 状态机有三种表示方法：状态图、状态表和流程图，这三种表示方法是等价 的，相互之间可以转换。其中状态图是最常用的表示方式。 1 6 上海大学硕士学位论文 2 3 2 算法实现 图2 1 0 描述了一种基于v i t e r b i 译码算法的有限状态机的纠错方法。这个纠 错方法中，短暂的错误恰好持续一个时钟周期的，因此只影响一个f s m 的状态转 变过程。这个方法不用改变原始f s m 中电路，只需在外部增加一些电路。 图2 1 0 纠错f s m 结构 具体地讲，一个给定的有限状态机由组合逻辑电路和状态寄存器组成。为了 实现实时纠错，得增加三部分电路。第一部分是k e yg e n e r a t o r ，它是一个组合逻 辑电路，对于f s m 的每个状态的改变，k e yg e n e r a t o r 就会产生一个特定k e y 。 在有限状态机正确的活动期间，生成的k e y 序列是正常的卷积码序列。实质上，通 过指派适当的k e y ( 在正常的f s m 活动期间通过k e yg e n e r a t o r 产生的) ，有限状 态机的状态转变可以先验的被编码成卷积码。第二部分是一个简单的校验器。在 任何给定的模型中的自纠错单元中，一个不正确的f s m 的状态转变，会产生一个 无效的卷积码序列的k e y 序列。那么在卷积码的延迟时间内，这就会被校验器检 测到。第三部分是v i t e r b i 译码器。v i t e r b i 译码器能够译码出正确的下个状态，使 得f s m 进入正确的工作状态。 当f s m 状态转变出现错误的时候，k e yg e n e r a t o r 就会产生一个无效的k e y 序列。校验器检测到后，就会发送有效e r r o r 信号给f s m 中的组合逻辑电路，告 诉f s m 输入发生错误了。f s m 就会等待d e c o d e r 译码出正确的下个状态，继而 f s m 回到正确的工作状态中去。 1 7 上海大学硕士学位论文 图2 1 1 多路选择器的结构图 此处的译码器采用的是v i t e r b i 译码器。v i t e r b i 译码器算法在本文前面部分已 经介绍。举个例子来看纠错f s m 是如何工作的。 表2 1 ( 3 , 2 ，1 ) 卷积码的转移矩阵 浆 0 00 11 01 1 0 00 0 0 0 1 11 0 11 1 0 0 11 0 0 1 1 10 0 10 1 0 1 01 1 l1 0 00 l o 0 0 1 1 l0 1 10 0 01 1 01 0 1 卷积编码可由它的转移矩阵来描述【7 1 。卷积码( 3 ，2 ，1 ) 的转移矩阵如表2 1 所 示