（微电子学与固体电子学专业论文）dct+ip核的vlsi设计与实现.pdf

哈尔滨工业大学工学硕士学位论文 摘要 离散余弦变换( d c t ) 在图像编码方而应用十分广泛，至今已被j p e g 、 m p e g l 、m p e g 2 、m p e g 4 和h 2 6 x 等国际标准采用。由于d c t 的计算量 较大，软件实现d c t 往往难以满足实时处理的要求，因而在很多实际应用 中需要采用硬件设计的d c t 处理电路来满足对处理速度的要求。本文所研 究的内容就是针对图像处理应用的8 8 点阵二维d c t 处列! 核的硬什实现。 本文首先介绍了d c t 在图像处理中的作用和原理，详细说明了d c t 变 换实现图像压缩的过程，用与其它变换相比较的方法来说明用d c t 变换实 现图像压缩的优势。然后，分析研究各种d c t 快速算法，总结前人对d c t 快速算法及其v l s i 实现所做的研究。根据图像处理的特点和基于i p 复用 的设计思想，结合d c t 快速算法和硬件实现的特点，以提高速度、减少设 计面积和功耗为目标，术文给出了一种d c t 的硬件设计方案。 该方案利用d c t 的行列分离特性，采用流水线设计技术，将二维d c t 实现转化为两次的一维d c t 实现。复用一维d c t 运算模块，从向避免了采 用串行设计所造成的资源和面积的浪费。由于采用_ 流水线技术和并行操作 方式，提高了运算速度。 最后，对所设计的d c t 处理核进行了综合、仿真验证和布局布线，结 果表明所设计的d c t 处理核能够在6 2 5 m h z 的时钟频率卜能够正确完成 8 8d c t 的逻辑运算。采用t s m c0 1 8g mc m o s 工艺库，使用s y n o p s y s 公司的综合工具d e s i g nc o m p i l e r 对d c t 综合后得到i p 核卣积为 4 3 5 5 5 8 8 1 2 5 9 m 2 。 关键词离散余弦变换；i p ；v l s i ；流水线；并行 坠玺鎏三些查耋三耋至圭兰竺竺兰 a b s t r a c t d i s c r e t ec o s i n et r a n s f o r mi sw i l d l yu s e di nt h ec o d i n go fi m a g ep r o c e s s i n g s of h r ，i th a sb e e na d o p t e db ym a n yi n t e r n a “o r l a ls t a n d a r d ss u c ha sj p e g m p e g l ，m p e g 2 ，m p e g 4a n dh 2 6 xe t c b e c a u s eo ft h eh e a v yq u a n t i t yo f c o m p u t i n g ，i ti sd i f f i c u l tt os a t i s f yt h er e a l t i m er e q u i r e m e n tb yt h es o f t w a r e d e s i g n t h e r e f o r e ，w ec a na d o p tt h es p e c i f i ch a r d w a r ec i r c u i t st os a t i s f yt h e s p e e dr e q u i r e m e n ti nm a n yp r a c t i c a la p p l i c a t i o n s t h em a i nc o n t e n to ft h i st h e s i s i st h a tt h ed e s i g na n di m p l e m e n t a t i o no f8 x 82 - dd c ti pc o r ef o rt h ei m a g e p r o c e s s i n g i nt h i st h e s i s ，t h e p r i n c i p l ea n de f f e c to fd c ti ni m a g ep r o c e s s i n g a r e i n t r o d u c e da tf i r s t t h e n ，t h ep r o c e s so fd c ti m a g ec o m p r e s s i o ni se x p l a i n e di n d e t a i l f u r t h e r m o r e ，t h ea d v a n t a g eo fd c tt r a n s f o r mi se l a b o r a t e d i na d d i t i o n v a r i o u sf a s ta l g o r i t h m so fd c ta r ea n a l y z e da n ds t u d i e d ，t h ee x i s t e dw o r k i n gf o r d c tf a s ta l g o r i t h m sa n di t sv l s ii m p l e m e n t a t i o n sa r es u m m a r i z e di nt h i st h e s i s b a s e do nc h a r a c t e r i s t i c so fi m a g ep r o c e s sa n di pd e s i g ni d e a ，c o m b i n i n gd c t f a s ta l g o r i t h m sa n dh a r d w a r ei m p l e m e n t a t i o n ，ad c ts o f ti pt h a ti m p r o v es p e e d a n dd e c r e a s et h ea r e aa n dp o w e ri sp r e s e n t e di nt h i st h e s i s t h e 、i pc o r ea d o p t e dt h ep i p e l i n ea r c h i t e c t u r ea n dc h a n g e d2 - dd c tt ot w o t i m e s1 - dd c tb a s e dd nc h a r a c t e r i s t i co fr o w c o l u m nd e c o m p o s i t i o n i nt h e2 d d c t d e s i g n ，w ec a ns a v ed e s i g nr e s o u r c e sw h i l ei m p r o v et h es p e e db e c a u s eo f r e u s i n gt h e1 - dd c t a n dm a k i n gu s eo ft h ep i p e l i n et e c h n o l o g y a tl a s t ，t h es y n t h e s i sa n dv e r i f i c a t i o n ，p l a c e m e n t & r o u t i n gf o rt h ed e s i g n h a v eb e e nd o n e t h er e s u l ts h o w st h a tt h ed e s i g nc a no p e r a t ec o r r e c t l yw h e nt h e c l o c kf r e q u e n c yi s6 2 5 m h z ，t h r o u g hu t i l i z i n gt h et s m c0 18 9 mc m o s t e c h n o l o g yl i b r a r ya n dt h es y n o p s y sd c ，t h ea r e ai s4 3 5 5 5 8 8 1 2 5 9 m 2 k e y w o r d sd i s c r e t ec o s i n et r a n s f o r m ，i p , v l s i ，p i p e l i n e ，p a r a l l e l 儿- 哈尔滨工业大学工学硕士学位论文 1 1 研究背景及意义 第1 章绪论 随着科技的飞速发展，我们正在进入数字化时代。数字化后的信息，尤其 是数字化后的视频和音频信息具有数据海量性，如声音、音乐、电视、电影这 些重要的信号数字化后，每秒需要更多的比特数去存储或传输，这样就造成了 高成本。它给信息的存储和传输造成较大的困难，成为阻碍人类有效地获取和 使用信息的瓶颈问题之一。因此，作为数字化技术核心之一的数字压缩备受人 们关注【i l 。 对于图像数据而言，一个显著特点就是信息量大，根据计算，在不进行编 码压缩处理的情况下，一张6 0 0 m 的光盘仅能存放2 0 s 左右的6 4 0 4 8 0 像 素的图像信息，这就使得在对图像的存储和处理中所遇到的困难和所需成本是 非常高的口j 。同时，在现代通信中，图像传输已经成为重要内容，传输信息量 的大小是影响传输速度的重要原因之一。要想提高通信速度，一个必要的手段 就是采用图像的编码压缩技术，减少传输的数据量。组成图像的各像素之间， 无论是在行方向还是在列方向上，都存在着一定的相关性。应用某种编码方法 提取或者减少这种相关性，就可以达到压缩数据的目的。从信息论的观点看， 描述图像信源的数据是由有效信息量和冗余量两部分组成，去除冗余量能够节 省图像存储和传输中的开销，同时又要不损害图像信源的有效信息量，保证重 构图像的质量。所谓图像压缩编码技术就是对要处理的图像源数据按一定的规 则进行变换和组合，从而达到以尽可能少的代码( 符号1 来表示尽可能多的数据 信息【3 【4 】。 离散余弦变换( d i s c r e t ec o s i n et r a n s f o r m ) 简称d c t 。任何连续的实对称函 数的傅里叶变换中只含余弦项，因此余弦变换与傅里叶变换一样有明确的物理 量意义。d c t 是先将整体图像分成n n 像素块，然后对n n 像素块逐一进 行d c t 变换。由于大多数图像的高频分量较小，相应于图像高频成分的系数 经常为零，加上人眼对高频成分的失真不太敏感，所以可用更粗的量化，凶 此传送变换系数所用的数码率要大大小于传送图像像素所用的数码率。到达接 收端后再通过反离散余弦变换回到样值，虽然会有一定的失真，但人眼是可以 接受的。 竺耋鎏苫些查耋矗兰2 圭兰黧鎏兰 离散余弦变换( d c t ) 能有效的消除图像的空域冗余，因而被广泛应用于图 像编酝蘧缭中，至今b 竣j p e g 、m p e g l 、m p e g 2 、m p e g 4 鞠h ，2 6 x 等翅际 标准所采用【5 】【6 1 。但由于其运算量较大，为了满足实时疆求，常常采用硬件来 实现奠功能。两d c t 所具有的快速算法也为d c t 的硬传实现提供了便利。尽 管d c t 快速算法缀翠就被掇出，并已被研究和应用了几十年，僵= 维8 8 d c t 快速算法，仍然还未成熟，现在的算法所要求的乘法次数还远高于理论 值。黼蔷蕃，还在不舞懿有薪懿映速算法被挺毫帮痤蠲，霹d c t 舞法瓣疆究仍 然是当今图像雁缩编码研究的艇点之一。 在考瘩d c t 魏v l s i 实现辩，投攒不同豹疲用基豹，缝合不阉夔雾法，有 不同的实现方式。集成电路设计技术发展到今天，逻辑功能的寨现已经不是很 大的挑战了，丽怎样农最短的时间设计出面积小，速度快，功耗低的电路才是 最大酌锈战。所敬，郄便采用黼一算法，餐在设计方法、工艺毅术上不蕊，设 计出的电路的性能也会大相径庭。因此，对d c t 的硬件实现的研究仍是十分 有意义豹。 1 2 国内外_ 囊开究情况 d c t 首先由n a h m e d 等人于1 9 7 4 年提出j 。之后，许多快速算法被提 塞。1 9 7 7 年，w , h c h e n 等人缀握变羧矩薄其蠢对称热，第一次萎l 耩臻楚簿分 解法褥到d c t - i i 快速算法。这种算法不仅结构简单，且使用余弦系数做乘 子，阁丽比前述各算法均优越，但其实现结构复杂。n r c m 方法即直接分解 法，典型的徽法是2 - i ) 矢量基d c t 冀注。1 9 8 7 年，几乎同时有三篇论文论述 了d c t 的递归算法，其中h s h o u 的快速算法较具有代表性。2 一d 矢避基算 法主餮骞基予b 。g l e e 戆雾法帮基于h o u 豹冀法。对予鞍长长夜戆d c t ，基予 h o u 的算法较基于l e e 的算法性能优越。目前避有效的2 - dd c t 直接分解算 法主要商森| | 嶷孝等人戆与n 。 。c h o 等人瞧算法。这溅莘申算法郝壤算法运算量 减至传统行列分解法的5 0 。森川良拳采用切比雪夫多项式同余形式提出了2 一dd c t 的囊接算法。n l 。c h o 的快速算法激用三角姻数法，将长度为2 的 殍次攀静2 一dd c t 表示为淹个薪的二维交换之帮，褥羁蠲羧滂移僚和隆加 实数加法运算。f e i w i n o g r a d 证明了在有理域上计算长度为2 的n 次幂的2 - d d c t 疆嚣最，l 、实黍次数燕2 2 ”n 2 “一2 ”2 ，瑰在还无法迭j 迦投袋。 九十年代以来，随着j p e g 、m p e g 、h d t v 的发展，d c t 的v l s i 实现 也有了缀大进展，各菁申快速算法的提如及工艺的改进趣为d c t 结构的发展刨 哈尔滨工业大学1 学硕士学位论文 造了条件。现在，d c t 的v l s i 实现主爱还是黎于行一列分解法，因为此方法 骞较嫠攀兹数擐传递绩擒。曩兹d c t 中姻黍法器多采髑d a 箕法实现，因其 精度高，结构规则，占用面积相对较少。但随着工艺的改进，特别是在深亚微 米级，同一硅片将集成较以往聪多的晶体管，因此晶体管数这一芯片性能参数 斡重要程存耩降低，弥渤阵确络梅有了定静袋装。 当前的一维d c t 算法结构主要有旗于乘法器的d c t 结构、基于分配算法 翡d c t 维橡、基于辣璜阵列豹d c t 绩擒帮萋予c o r d l e 运冀技寒的d c t 结 构等。 基于乘法器的d c t 结构多采用w h c h e n 的算法直接用娠法器求实现 d c t 运算，改善此类d c t 结构的关键在于乘法器结构的改谶。铆如，采用 b o o t h 乘法算法的乘法器，与普通的乘法器栩比，减少了乘法过程中的加法 搡 筝，挺离了聚法运棼速度，浚善了d c t 懿绞链。餐众辑周知，乘法器豹引 入也将导致面积的增加。另外，此类结构虽具有模块化，但结构不规则，不利 于布局、毒线。 e b 于基于分配算法的d c t 结构紧凑，规剃，精度商，速度快被广泛应用 在备领域中。其基本思想是通过r o m 遣找表法，利用r o m 和累加器代替乘 法器。它是秘掰d c t 中静余弦系数溺定酶特点，将褶寝的输入数裾鲍乘法结 果余弦算好，并存于r o m 中，根据输入数据对r o m 取址即可。由于分配算 法具有裹褒麴蠼澍绫稳，盈困诗算戳分酝方式遴嚣，截戆被隈截，医露撬获缛 较其它结构更高的精胰，很适合于v l s i 实现。但大量r o m 的使用同样大大 增加了设计的疆积， i 蘑且对r o m 的频繁访闷和此算法结构袋用豹位串行实 现，黼样极大的限制了速度，难以获褥很高的时钟频率。另外，此结构爰求的 工艺凝杂，要同时用到三种工艺，因此成本比较高。由于很多f p g a 芯片本身 有r o m 模涣，嚣量f p g a 辩镑频率 瑟不可镶离，鬻疆，这耱方法，多霞予 f p g a 的实现上。 辣动薄捌概念最早自珏。t 。k u n g 于1 9 8 2 年提出。躲动簿列l 曩一组籀警重复 的处残单元( p e ) 组成，每个p e 执行固定盼、简单的操作，每个p e 只与相邻盼 p e 有规则地联结，操作时，数据经过连成流水线的p e ，沿途褥到连续的有效 处理。诧高庭并彳亍处瑗结构，大大提裔了v l s i 速度，麓结构斑弼。d c t 的豫 动阵列种类多，采用的算法也各异，结构实现的主要工作是选取合适的p e 单 元。辣凌阵列暹过势符及滚承操终可获褥较裹戆楚理速发，显懿鸯模块纯、缝 构规则、局部内联等特点，适台于v i 。s i 实现。但脉动阵列往往要求多个数据 嗣时参与计算，因此i o 处理邋常较为复杂。翳辨，因每个p e 内有多种算术 哈尔滨工业大学上学硕士学位论文 运算、截断与舍入误差会影响精度。而且，由于个p e 内多种运算并存，有 时会有多个乘法运算，因而面积往往很大，且脉动阵列结构的时钟控制电路复 杂。这些原因使得现在各种应用中采用脉动阵列d c t 结构的并不多见。 c o r d i c 是坐标旋转数字计算机的同义词。这种计算是v o i d e r 于1 9 5 9 年 提出来的。这个概念虽然由来已久，但它的实现与应用还在继续发展，因为此 技术简化了体系结构，提高了速度，降低了算术模块的功耗。c o r d i c 算法是 一个通过以角度凹2 a r c t a n 2 进行矢量旋转而得到的迭代过程。通过采用 c o r d i c 算法，旋转运算中的乘法器可仅由a n 减法器和移位寄存器来实现， 减少了电路，并通过流水线结构，加快了数据传输速度。1 9 9 0 年，d u b 与w u 首次将c o r d i c 引入d c t 计算中。e p m a r i a t o r s 等人的旋转结构利1 j | d c t 中 每个c o r d i c 旋转危度是预先确定的事实，找到角度目的表达式，减少了运算 量，减少了硬件。而f z o u 等人是将d c t 结构改进，使得完成一个d c t 需要 较少的c o r d i c 计算，获得了较高吞吐量。 总之，目前d c t 新算法正在被不断的提出，相应的新的v l s i 实现方法也 在不断产生 8 1 。 1 3 本论文的研究内容 本文的内容安排共分为六个章节，各章节内容如下： 第章：绪论。主要介绍了本课题研究的目的与意义、国内外研究状况以 及本文的研究内容和安排等 第二章：d c t 在图像处理中的作用及i p 设计技术。本章主要介绍图像压 缩的相关知识、d c t 的数学意义、d c t 在图像处理中的作用和工作原理。另 外，还对a s i c 设计方法和i p 设计技术作了简要介绍。 第三章：d c ti p 核的算法及结构设计。本章主要研究一种一维d c t 快速 算法及应用了此快速算法的二维d c t 的v l s i 实现结构。首先对几种流行的算 法结构做了介绍，分析了各种算法结构的优缺点，介绍了流水线和并行的结构 设计相关知识，然后给出了自己的设计结构，并作了详细介绍和说明。 第四章：d c ti p 核的模块设计。本章主要研究了d c t1 p 核v l s i 实现的 模块设计，对设计的各模块做了详细的说明，并对设计中应该注意的问题作了 详细介绍和说明。 第五章：综合和验证。本章对所设计的d c ti p 核做了功能仿真，综合和 略尔滨上业太学工学硕士学位论文 门级仿真验证，对仿真和综合过程作了详细说明，给出了仿真和综合结果，并 对缝果送行了分耩。 总结：本部分对所做的研究工作做了概括和总结。 哈尔滨工业大学工学硕士学位论文 第2 章d c t 在图像处理中的作用及i p 设计技术 2 1d c t 介绍 离散余弦变换( o c t ) 实际上是离散傅立叶变换( d f t ) 的一种特殊形式。傅立 叶级数展开式中，如果被展开的函数是实偶函数，其傅立叶级数中只包含余弦 项，由此可导出d c t 变换。假如已知函数f ( x ) o o ) ，并非实偶函数，人为 的把它对称扩展到x 0 ，构成实偶函数，。( x ) ，那么，( x ) 的傅立叶变换的f 弦项被抵消，余弦项是傅立叶变换_ 厂( z ) 中余弦项的两倍”。 2 2d c t 在图像处理中的作用 d c t 变换的目的是消除图像的空域冗余，实现图像的压缩。离散余弦变换 d c t 可被看作为一个谐波分析仪，把离散余弦反变换i d c t 看作个谐波合成 器。每个8 x 8 二维源图像采样数据块，实际上是6 4 点离散信号，该信号足空 间二维参数x 和y 的函数。1 d c t 把这些信号作为输入然后把它分解成6 4 个 正交基信号，每个正交基信号对应于6 4 个独立二维( 2 d ) 空间频率中的一个， 这些空间频率是由输入信号的频谱组成。i d c t 的输出是6 4 个基信号的幅值， 或称d c t 系数，每个系数值由6 4 点输入信号唯一地确定，即离散余弦变换的 变换系数。在频域平面上变换系数是二维频域变量n 和v 的函数。对应丁 = 0 ，v = 0 的系数，称为直流分量，即d c 系数，其余6 3 个系数称作a c 系 数，即交流分量。因为在一幅图像中象素之间的灰度或色差信号变化缓慢，在 8 x 8 子块中象素之问的相关眭很强，d c t 变换实现图像数据压缩正是利用图像 相邻象素点之间相关性很强的特点( 这表明相邻象素点之间的象素差很小) ，把 图像从时域变换到频域，这样，变换后的矩阵表示的不再是图像的象素值，而 是图像的频率分布。通过离散余弦变换处理后，d c 系数代表了图像的平均能 量，即变换前6 4 个图像象素的平均值；而a c 系数，代表图像的各个频率成 分，离d c 系数越远的a c 系数代表越高的频率成分。变换后的矩阵数值主要 集中在矩阵的左上角，而越靠近右下角的数据数值越小。它所代表的物理意义 是图像的能量主要集中在图像的低频部分，而高频分量则很小。根据视觉特 性，人的眼睛对图像的高频成分不敏感，这就大人的方便了我们进行数据压 性，人的眼睛对图像的高频成分不敏感，这就大大的方便了我们进行数据压 哈尔滨工业大学工学硕士学位论文 第2 章d c t 在图像处理中的作用及i p 设计技术 2 id c t 介绍 离散余弦变换c t ) 实际上是离散傅立叶变换( d f t ) 的一种特殊形式。傅立 叶级数展开式中，如果被展开的函数是实偶函数，其傅立叶级数中只包含余弦 项，由此可导出d c t 变换。假如已知函数f ( x ) o ) ，并非实偶函数，人为 的把它对称扩展到x 霹表示为： 蜀= x e + 南 毋= 屯十 芝= 五+ 只= x 2 + x 5 = p o + 只 薯，= 曼毪 鼻o o = 只o + # l ( 3 - 1 1 ) i = m o c l + m l c 7 + m 2 c 3 + m 3 c 5 墨= m # # 7 一m l q m 2 # 5 + m 3 岛 爿j = m o c 3 一m l c s m 2 c 7 一 如q 参= m o c s 埘一 埘：q + m 3 白( 3 - 1 2 ) 五= m 1 0 c 2 + m l i c 6 x 6 = m l o 一m l l q x 42 m l 。4 x o = e c 4 翻表达式( 3 一1 2 ) 可鹜示辩鎏3 一l ： 一1 5 - 堕玺鎏三些奎兰三主2 圭耋堡竺三一 图3 - 1 第一步8 点d c t 结构图 f i g 3 - 1t h ef i r s ts t e p8 - p o i n td c t s l a u c t u m 将图3 - 1 中的两个丰要模块做如下变换 x ( 1 ) x ( 7 ) x ( 5 ) x ( 3 ) x ( 2 ) x ( 6 ) x ( 0 ) x ( 4 ) 黑蹲等舞令；i x ( 0 ) x ( 1 ) 一_ 一_ 可得图3 3 图3 - 2 模块定义 f i g 3 2m o v i ed e f i n i t i o n s 1 6 - x ， y x ， y m x x x x x x x x 哈尔泼f 工业大学学硕士学傲论文 圈3 - 3 第二步8 点d c t 缩稳图 f i g 3 3t h es e c o n ds t e p8 - p o i n td c ts t r u c t u r e x ( ? ) x ( 5 ) x ( 3 ) x ( 2 ) x 1 6 ) x ( o ) x ( 4 ) 如圈3 3 所示的d c t 交换实现方法使用了2 2 个乘法器和2 8 个加法器。 接下来，对图3 2 种的第二个模块进行优化。此模块的实现使用了4 个乘 法器耧2 个鸯羹法器。经过翔国3 叠懿交纯螽，哥羯3 拿象法器秘3 令撩法嚣寒 实现它。所作变换如下。 兔对输入进毒亍加减踅余项鲢据分，然后再重缀可得： 瓣+ b y 嚣船一b x 十搬+ b y 端( x + y ) x b + ( 玎- b ) x，、 b x a y 蕊b x + b y a y b y ( x + 曲b 一( d 十b ) x y 、 图示翻下： x y a x + b y h 。 b y 蛰3 - 4 模块傀诧 f i g 3 4m o d u l eo p t i m i z a t i o n a x + b y b x a y 经过如憩交往，瞬3 - 3 中的d c t 燮换就可娃臻t 7 个乘法耩帮3 3 个葫法 器来实现。相对于加法器的增加，乘法器数量的减少是让我们值得这样做的理 啦矿 4 1 6 2 s x x x x x x x x 函 哈尔演工业大学l 学硕士学位论文 由。 最矮，我们澍图3 - 4 中的表达隽式避一步进行优化。如图3 - 5 所示，将输 出位髯调换并对、b 进行a = s i n 口，6 = c o s 6 j 替换后得到角度旋转公式。 f i 百一一一一1 ；邈牵b 咐x - 。a y ，壁 ；j = 瞄捌 埔，豢瑟甄螂也州蜘；。 囤3 - 6 角度旋转公式的推导 f i g 3 - 6d e d u c t i o no f t h er o t a t ef o r m u l a 将图3 - 2 中的后模块表示为如图3 。7 所示。 圈一瞄c o s 8 - 一s i n 日 ； 唏；j 似一- - 图3 7 角度旋转公式的模块形式 f i g 3 - 7m o d u t a r i z a t i o no f t h er o t a t ef o r m u l a ； 不褥螽 旋转角 ( b ) 国) 上圈中的旋转角度浚远方式有如图3 - 8 掰表示的重要特矬，列： x y e 萝唏；到r o t 一，口：l - - ；： 圈3 - 8 角度旋转公式的性质 f i g 3 - 8c h a r a c t e ro f t h er o t a t ef o r m u l a 堕玺薹三些銮：士兰翟圭兰堡兰兰 此外还有： x y r o t 2 _ 4 jj xx yy丁三孔 一1 1jc 4 | 图3 - 9 特殊角度的旋转公式 f i g 3 - 9s p e c i a lr o t a t ef o r m u l a 这样图3 3 中的丰要运算部分可化简为： m 1 m 2 x ， y 圈3 1 0 运算部分中的模块优化 f i g 3 - 1 0m o d u l eo p t i m i z a t i o no f t h ea l u 进而利用图3 - 8 和图3 - 9 的特性对图3 1 0 进行拆分及重组，可将运算部分优化 成如图3 - 1 1 ，3 - 1 2 所表示的形式： m 0 m 1 奇m 1 ”m 1 m 1 j 一等1 日卅r o ，；_ 1 6r _ _ r h4 卜_ j 兰三兰 x i ： 1 _ _ 广一 图3 1 1 角度旋转公式性质的运用 f i g 3 11a p p l i c a t i o no f r o t a t ef o r m u l a a b e r c d g m 2 m 3 m 2 今 m 3 丑二童目兰 i。，一 【。，一 图3 1 2 角度旋转公式性质的运用 f i g 3 1 2a p p l i c a t i o no f t h er o t a t ef o r m u l a 将上述变换带入到图3 - 3 中，我们可以得到一维d c t 的最终硬件实现方 案。如图3 1 3 所示： 图3 - 1 3 优化的8 点d c t 结构图 f i g 3 1 3o p t i m i z e dg - p o i n td c ts t r u c t u r e 在图3 1 3 的变换中使用了1 3 个乘法器和3 1 个加法器。这与图3 - 1 相比 硬件开销显然得到了大幅的消减。 3 _ 2 流水线设计技术 提高处理器效率丰要有两种方法：是流水线技术( p i p e l i n i n g ) ，将一个任 啪加 蚋m m 啪 m 啪 堕玺鎏王些銮兰王兰翟圭耋毖鎏兰 务分解成为多个连续的子任务，在处理前一个子任务的同时就开始准备下一- 个 子任务鲍数据并进行子处理器攀元的视始位，当嗣时使耀多条滤水线耐，藏称 之为越流水线技术或者并行流水线技术；另一个鲻就是超标量技术，它程处理 器内部设置多个平行的处理部件，将多个相互无关的任务在这些处理部件中分 羽进行猛立筵灌。氇就是说：流隶线愚分嫠| 成多个子任务并行鲶淫，忝怒标量 是无关任务同时并行处理，在本质上悬有区别的，流水线技术将处理器的等待 数据| j l 雩闫尽量减小，最大眼凄撬蔻楚理搂兹效率，磊超轹量技术藏是磐数据躲 等待时间尽量减小，最大限度掇高数据的利用效率。 流水线是计算机将作业分成一系列部分完成程序的处理技术。透过将较大 的作蛾分成较小而部分重叠的作业，流水线可丽于将性能表现撼高于菲流水线 作业方式的极限。流水线程序启动后，除了通过的程序数目外，指令的执行率 氆较齑。 当然，流水线技术也不可能无限制的提高遗行速度。流水线有下面几条限 制：蓠先，由予黉没蠢真正减少每条攒令( 或最小单元运算步骤黪执行辩超， 从而限制了流水线的深度。这建流水线延迟引入的限制；其次。由于时钟不能 快于最慢的漉水节拍，所以形成流水节拍不平循引入的限制；最后，由于流水 线寄存器的延避和露释歪辩，形成流承线斡辩擒开镑弓l 入翡限截臻”。 3 3 辨行处理技术 所谓并行处理( p a r a l l e lp r o c e s s i n g ) 技术是指在同一时间间隔内增加操作数 量静技术，所谓著嚣计算辊( p a r a l l e lc o m p u t e r ) $ l j 市蠢并行处理耩设计懿计算鞔 系统，相应地在并行计算机上求解问题称为并行计算( p a r a l l e lc o m p u t i n g ) ，在 并行诗算飒主求簿润题夔冀法琢为蒡 予葵法( p a r a l l e la l g o r i t h m s ) 。 并行处理是一种强调开发计算过稷中并发攀件( c o n c u r r e n te v e n t ) 的有效的 信息处理方式。若发性( c o n c u r r e n c y ) 包含并行性( p a r a l l e l i s m ) 、阐时性 f s i m u l t a n e i t y ) 和流承线( p i p e l i n i n g ) 。并行事件可良在同一时闻闻隔蠹发生在多 个资源中，同时事件可在同一时刻发生，流水线事件可在部分激叠的时间内出 瑷。 并行处理的四个级别是；作业或程序之间的并行，是指多个作业或多道程 序麴势行执行；任务鼓进程之间的黉抒，是指多个任务或程序段豹菇行执行： 指令之问的并行，使之多条指令的并行执行：指令内部的并行，是指一条指令 内部番微操作之间的并行执行j 。 哈尔滨工业大学工学硕士学位论文 3 4 总体结构设计 本文的d c ti p 核设计研究是针对图像数据压缩应用的。在m p e g ，j p e g 等标准中，数据以码流的形式被处理。为了提高编解码的处理效率，节约硬件 资源，流水线的设计是非常重要的。对于j p e g 来说，图像的每一帧都是帧内 编码图像( i 帧) ，所以图像的d c t 变换的输入是0 2 5 5 ( 象素点灰度级) ，而输 出是一1 0 2 4 1 0 2 3 ，相应的需要8 位的输入和1 1 位的输出；对于m p e g 来 说，要处理的不单有帧内编码的i 帧图像，还有帧间编码的p 帧图像和b 帧图 像，p 帧和b 帧图像表示的是两帧图像象素点的差值，所以其d c t 变换的输 入值表示范围为2 5 5 2 5 5 ，d c t 变换输出值范围为- - 2 0 0 0 2 0 0 0 ，相应的需 要9 位和1 2 位来表示，i d c t 则相反【2 3 】。本文的设计研究是按j p e g 的标准进 行的。 对于2 dd c t 的结构，也分为行列分解法( r c m ) 及非行列分解法c n r c m ) 两类。对于2 一dd c tn r c m ，采用的算法是各种非行列分解2 - dd c t 快速算 法，它往往要求整个n n 输入数据同时参与计算，因此i o 处理及数据传递 电路复杂，使得它们的v l s i 实现在性能上不如r c m 系统。现在行一列分解 法( r c m ) 仍被广泛应用在2 - dd c t 芯片设计中。本文也是采用r c m 的设计结 构，其结构如图3 1 4 所示，此结构采用的算法为各种一维d c t 快速算法，行 和列的1 dd c t 结构相同，为了减少面积只用一个1 一dd c t 处理单元完成两 次1 dd c t 计算。为了获得较高的吞吐量，本文的设计采用并行算法。对于 所设计的r c m 系统，必须在两次的1 dd c t 处理电路之间对完成一次l d d c t 运算的输出数据进行行列转换，这就需要设计中间数据转换电路。 图3 1 42 d d c t 结构图 f i g 3 1 42 - dd c ts t r u c t u r e 哈尔滨工业大学j 二学硕士学位论文 3 5 一维d c t 结构设计 3 5 1 算法结构介绍 一般一个算法结构的优劣主要决定于三个性能参数：面积、速度、精度， 在此三个参数基础上，还要求结构规则，具有模块化，这样有利于设计及版图 布局布线。现在已有多种一维d c t 算法结构被提出，这些结构都有各自的缺 点，网此在各种应用中这些结构并存。另外，因为每种d c t 算法有自己的特 殊性和应用领域，不是所有的算法都适合于v l s i 实现。一个算法v l s i 实现 的有效性主要基于算法中算术单元之间的数据传递的复杂性，而不是算法的运 算量。正如许多研究人员指出的那样，像很多f f t 算法，它们有较低数量的乘 法运算，但这些算法并不适合于v l s l 实现。d c t 算法也遇到了同样的问题。 当前的一维d c t 算法结构主要有以下几类： ( 1 ) 基于乘法器的d c t 结构此结构多采用w h c h e n 的算法直接用乘法器 来实现d c t 运算，改善此类d c t 结构的关键在于乘法器结构的改进。例如， 采用b o o t h 乘法算法的乘法器，与普通的乘法器相比，减少了乘法过程中的 加法操作，提高了乘法运算速度，改善了d c t 的性能1 2 4 j 。但众所周知，乘法 器的引入也将导致面积的增加。另外，此类结构虽具有模块化，但结构不规 则，不利于布局、布线。 ( 2 ) 基于分配算法的d c t 结构基于分配算法的d c t 结构由于其结构紧 凑，规则，精度高，速度快被广泛应用在各领域中。其基本思想是通过r o m 查找表法，利用r o m 和累加器代替乘法器。它是利用d c t 中的余弦系数固 定的特点，将相应的输入数据的乘法结果余弦算好，并存于r o m 中，根据输 入数据对r o m 取址即可瞄j 【”j 。由于分配算法具有高度的规则结构，且因计算 以分配方式进行，截断被限制，因而能获得较其它结构更高的精度，很适合于 v l s i 实现。但大量r o m 的使用同样大大增加了设计的面积，而且对r o m 的 频繁访问和此算法结构采用的位串行实现，同样极大的限制了速度，难以获得 很高的时钟频率。另外，此结构要求的工艺复杂，要同时用到三种工艺，因此 成本比较高。由于很多f p g a 芯片本身有r o m 模块，而且f p g a 时钟频率也 珥i 可能很高，所以，这种方法，多用于f p g a 的实现上。 ( 3 ) 基于脉动阵列的d c t 结构脉动阵列概念最早由h t k t m g 于1 9 8 2 年提 出【2 7 1 。脉动阵列由一组简单重复的处理单元( p e ) 组成，每个p e 执行固定的、 哈尔滨工业大学工学硕士学位论文 简单的操作，每个p e 只与相邻的p e 有规则地联结，操作时，数据经过连成 流水线的p e ，沿途得到连续的有效处理。此高度并行处理结构，大大提高了 v l s i 速度，且结构规则。d c t 的脉动阵列种类多，采用的算法也各异，结构 实现的主要工作是选取合适的p e 单元i z 副唧j 。脉动阵列通过并行及流水操作可 获得较高的处理速度，且具有模块化、结构规则、局部内联等特点，适合于 v l s i 实现。但脉动阵列往往要求多个数据同时参与计算，因此i o 处理通常 较为复杂。另外，因每个p e 内有多种算术运算、截断与舍入误差会影响精 度。而且，由于一个p e 内多种运算并存，有时会有多个乘法运算，因而面积 往往很大，且脉动阵列结构的时钟控制电路复杂。这些原因使得现在各种应用 中采用脉动阵列d c t 结构的并不多见。 ( 4 ) 基于c o r d l c 运算技术的d c t 结构c o r d l c 是坐标旋转数字计算机 的同义词。这种计算是v o i d e r 于1 9 5 9 年提出来的p 。这个概念虽然由来已 久，但它的实现与应用还在继续发展，因为此技术简化了体系结构，提高了速 度，降低了算术模块的功耗。c o r d i c 算法是一个通过以角度叼2a r c t a n z 。进 行矢量旋转而得到的迭代过程。通过采用c o r d i c 算法，旋转运算中的乘法 器可仅由：j h 减法器和移位寄存器来实现，减少了电路，并通过流水线结构， 加快了数据传输速度。1 9 9 0 年，d u h 与w u 首次将c o r d i c 引入d c t 计算中 3 h 。e p m a r i a t o r s 等人的旋转结构利用d c t 中每个c o r d i c 旋转角度是预先 确定的事实，找到角度p 的表达式，减少了运算量，减少了硬件【3 ”。而f z o u 等人是将d c t 结构改进1 3 ”，使得完成一个d c t 需要较少的c o r d i c 计算， 获得了较高吞吐量。 3 5 2 结构设计考虑 以上对当前流行的几种算法结构做了介绍，它们都有各自的优缺点。在选 择或者设计一个算法结构时，首先要考虑自己的设计的应用对象，设计要求。 本文所研究的设计是一个l p 核的a s i c 设计，所以设计要独立化，模块化，以 适于s o c 设计技术。另外，结构设计还应该考虑到设计对性能的影响，比如速 度、面积以及结构的规则性等。这些因素之间往往是一对一对的矛盾，有时为 了更高速度而牺牲面积，有时为了节约硬件资源减小面积也会以牺牲速度为代 价。所以，设计者需要根据实现的要求和条件在这些性能指标之间做出折中， 以最大程度的利用硬件资源，满足设计的要求【j 。 哈尔滨工业大学工学硕士学位论文 3 5 3 结构设计实现 为了提高处理器的时钟频率，电路采用了5 级流水线结构，第一级用于前级 a n 减法，第二、三级用于做角度旋转的乘a n 操作，第四级用于后级加法，第 五级用于最后的乘法。流水线的引入缩短了运算模块中的最长周期，明显的提 高了时钟频率。同时由于一维d c t 运算模块采用了并行结构，计算结果 x ( i ，0 ) x ( i ，7 ) 得以并行的方式输出到转置存储器中。 缓冲器每两个时钟周期被写满一次，即每两个时钟周期缓冲器向一维d c t 运算模块输入8 字节数据，此时流水线寄存器组工作在l 2c l o c k 频率下。经过 2 5 = 1 0 个流水周期后开始逐行输出变换完的数据到转置存储器。在经过 2 x3 = 6 个流水周期，一个8 x 8 = 6 4 的数据块输入完毕，此时流水线寄存器组 开始工作在1c l o c k 频率下。工作方式如图3 1 5 所示： c l o c k 儿_ _ nnnnr u r | 厂| nn 几几l 厂lr | 儿几_ i n p u t o u t p u t 图3 1 5维d c t 变换数据波形图 f i g 3 151 dd c t & a t a b a s ew a v e f o i m 其中i n p u t 为数据经选通器到一维d c t 运算模块的输入，o u t p u t 为一维 d c t 运算模块的输出。从图3 1 4 可以看出，输入数据经过初始的1 1 周期( 包括 一周期的选通器延时) 流水线延时，从第1 2 1 7 周期输出3 行变换后的数据， 从第1 8 2 2 周期输出5 行变换后的数据到转置存储器。 上述算法结构，一方面减少了采用通用乘法器所产生的面积和资源的浪 费，另一方面也避免了采用查找表方法实现乘法而需要的存储器设计。5 级流 水线的设计更体现了此结构具有的高速度和高吞吐量。因此，本文所采用的结 构具有面积小