（电路与系统专业论文）离散余弦变换ip核的设计.pdf

中国科学技术大学硕士学位论文 摘要 近十年来，因特网对多媒体数据的要求呈爆炸性的增长，导致数据通信技 术的提高非常重要。视频和音频数据在未压缩的情况下，传输需要占用巨大的带 宽，保存也会占用大量的存储单元。许多多媒体数据压缩方法被提出来，其中一 些使用离散余弦变换( d c t ) 做变换编码。d c t 是1 9 7 4 年首先由a h m e d ，n a t a r a j a n 和r a o 提出，现在已经成为信号处理中最重要的变换之一。正向和反向离散余 弦变换( f d c t i d c t ) 是图像、音频和视频编解码的核心操作，在许多相关的 标准中均采用d c t ，如：p e g 、h 2 6 1 、h 2 6 3 、m p e g l 、m p e g 2 、m p e g - 4 和数字电视等。 在图像和视频信号压缩的变换编码方法中，离散余弦变换被广泛认为是最高 效的一种方法，已经经过多年实践证明。d c t 是当前众多图像和视频编码标准 的核心，之所以得到如此广泛应用，主要归困于两点：一是变换后的图像数据易 于压缩，且效率高；二是可以在软件和硬件上高效的执行。随着集成电路产业的 飞速发展，现代电子系统的整个功能被集成在一块芯片上，即片上系统( s o c ) 。 s o c 意味着更大的设计规模和更高的复杂度，而电子产品的生命周期却在不断 的缩短，为了满足产品上市时间的压力，在芯片设计中采用i p ( i n t e l l e c t u a l p r o p e r t y ) 是i c 设计发展到s o c 时代的必然选择。口模块的再利用，除了可以 缩短s o c 芯片设计时间以外，还可以提高设计效率、节省人力、降低设计成本， 提高可靠性，以及满足面市时间( t i m e - t o - m a r k e t ) 的要求。因此，研发可嵌入 式的能重复利用的i p 功能模块将在集成电路设计和现代s o c 电子系统研发领域 具有广泛的应用前景和现实意义。 本文的主要工作和特色在于： 1 对不同的d c t 算法和不同的电路实现结构做了简单的介绍，在每一种类 型中，对一些代表性的论文做了简短的描述和比较，个别部分做了深入分析，指 出了其优缺点，给出了定性和一些定量描述。 2 研究了正向和反向d c t 算法的实现形式，给出设计思路，做了算法推导， 重点选择了快速算法( c h e n 算法) 和分布式算法。讨论了在音频和视频中得到 广泛应用的不同的d c t 硬件实现方式，在综合考虑计算量和规则性的基础上， 中国科学技术大学硕士学位论文 设计了两种不同的d c t i p 核结构。一种应用于低速低功耗的情况，如在数码相 机中的j p e g 静态压缩和音频；另一种应用于实时视频解码，如数字电视等要求 高速应用的情况。 3 i p 核设计结合了快速算法和分布式算法，利用分布式算法的特例，串行 逐位输入，布线简单。利用余弦系数的对称性，预先以二进制补码建立查找表， 在基于存储器查找表的并发体系结构上实现流水线操作。一个i p 核设计处理不 同字长的外部数据，可以执行f d c t 和i i ) c t ；另一个i p 核设计用来处理固定1 2 位字长的i d c t 。设计中，遵循现代i c 设计自顶向下( t o p t o d o w n ) 的设计方法， 从系统总体要求出发，由上至下分层次分模块地逐步将设计内容细化，最后完成 系统的整体电路设计，得到了两个不需要乘法器，只需存储器、加法器和寄存器 的高性能的i p 核电路设计。综合实现结果表明，该设计结构简单、层次清晰， 具有高度的规则性和模块性。 4 对比了软件、硬件和i p 核实现d c t 的不同，给出了i p 核设计的思路。 最重要的是可移植性，要能够通用，保证在不同的工艺、不同的硬件、不同的外 部模块嵌入中，均能够保证i p 核的逻辑功能和时序关系。在设计芯片时，要综 合考虑价格、速度和面积( 功耗) 。 关键词：离散余弦变换( d o t ) i p 核 分布式算法( d a ) 正向反向离散余弦变换( f d c t i d c t ) 2 ! 里型兰篓查查堂堡主兰垡笙茎 a b s t r a c t i nt h el a s td e c a d et h ea d v a n c e m e n ti nd a t ac o m m u n i c a t i o n t e c h n i q u e w a s s i g n i f i c a n t ，d u r i n g t h e e x p l o s i v eg r o w t h o ft h ei n t e r a c tt h ed e m a n df o r u s i n g m u l t i m e d i ah a si n c r e a s e d v i d e oa n da u d i od a t as t r e a m sr e q u i r eah u g eb a n d w i d t ht o b et r a n s f e r r e di na nu n c o m p r e s s e df o r m s e v e r a lw a y so f c o m p r e s s i n gm u l t i m e d i a s t r e a m s e v o l v e d ，s o m e o ft h e mu s et h ed i s c r e t ec o s i n e t r a n s f o r m ( d c t ) f o r t r a n s f o r mc o d i n g d c tf i r s ta p p e a r e di na h m e d ，n a t a r a j a a ，a n dr a o sp i o n e e r i n g p a p e ri n1 9 7 4 i th a sb e c o m e o n eo f t h em o s ti m p o r t a n tt r a n s f o r mi ns i g n a lp r o c e s s i n g t h ef o r w a r da n di n v e r s ed c t ( f d c t i d c t ) a r ee s s e n t i a lo p e r a t i o n si na u d i o ，i m a g e ， v i d e o c o d i n g ，a n d h a v eb e e ni n c l u d e di ns e v e r a l i m a g e a u d i o v i d e o s t a n d a r d s p e c i f i c a t i o n s ，i n c l u d i n gj p e gs t i l li m a g ec o m p r e s s i o n ，h 2 6 1 ，h 2 6 3 ，m p e g - 1 ， m p e g - 2 ，m p e g 一4 ，a n d t h ea t s cs t a n d a r df o rh d t v a m o n gm a n y o fm e t h o d so ft r a n s f o r ma n de n c o d i n go fi m a g ea n dv i d e os i g n a l ， d c ti sb r o a d l yr e g a r d e da st h em o s te f f i c i e n to n e i th a sp r o v e dp a r t i c u l a r l yd u r a b l e a n di sa tt h ec o r eo fm o s to ft h ec u r r e n tg e n e r a t i o no fi m a g ea n dv i d e oc o d i n g s t a n d a r d s t h e r ea r et w om a i nr e a s o n sf o ri t sp o p u l a r i t y f i r s t l y , i ti se f f e c t i v ea t t r a n s f o r m i n gi m a g ed a t a i n t oaf o r mt h a ti s e a s y t o c o m p r e s s s e c o n d l y ，i t i s i m p l e m e n t e de f f i c i e n t l y i ns o f t w a r ea n dh a r d w a r e 。w i t ht h ef a s td e v e l o p m e n to f i n t e g r a t e dc i r c u i t ，t h e w h o l ef u n c t i o no fm o d e me l e c t r o n i cs y s t e m si si n t e g r a t e da c h i p ，n a m e l ys y s t e mo nac h i p ( s o c ) s o cm e a n sl a r g e rd e s i g ns c a l ea n dh i g h e r c o m p l i c a t i o n ，b u t t h el i f e t i m eo fe l e c t r o n i cp r o d u c tb e c o m eg r a d u a l l ys h o r t e r i no r d e r t os a t i s f yt h er e q u i r e m e n to ft h ep r o d u c t st i m et om a r k e t ，u s i n gi p ( i n t e l l e c t u a l p r o p e r t y ) i nc h i pd e s i g n i st h en e c e s s a r yc h o i c ei nt h es o ce r a t h er e u s eo fi p m o d u l ec a r ln o to n l ys h o r t e nt h et i m e o fs o c c h i pd e s i g n b u ta l s oi m p r o v et h ed e s i g n e f f i c i e n c y , s a v ew o r k f o r c e ，r e d u c ed e s i g nc o s t ，e n h a n c er e l i a b i l i t ya n ds a t i s f y t h e r e q u i r e m e n t o f t i m e - t o - m a r k e t t h e p r i m a r yw o r k s a n dm a i nc h a r a c t e r i s t i c so f t h ep a p e ra r ea sf o l l o w s ： 1 t h ep a p e rp r o v i d e sa no v e r v i e wo fd c ta l g o r i t h m sa n dd i f f e r e n tt y p e so f 3 中国科学技术大学硕士学位论文 a r c h i t e c t u r e s w i t h i ne a c ht y p e ，af e w r e p r e s e n t a t i v ep a p e r sa r eb r i e f l yd e s c r i b e da n d c o n t r a s t e d ，a n dah a n d f u lo fi n t e r e s t i n gd e s i g nc a s e sa r ed i s c u s s e di nd e p t h 2 t h ep a p e rh a sr e s e a r c h e dt h ea l g o r i t h mm a i i z a t i o no ft h ef o r w a r da n di n v e r s e d c t f a s ta l g o r i t h m ( c h e na l g o r i t h m ) a n dd i s t r i b u t e da r i t h m e t i ca r es e l e c t e d i t d i s c u s s e sd i f f e r e n tw a y so f i m p l e m e n t i n gd c t h a r d w a r ec o d e r st h a tc o u l db eu s e di n aw i d er a n g eo fv i d e oa n da u d i oa p p l i c a t i o n s i ti n t r o d u c e st w od i f f e r e n td c t c o r e s ， o n ec o u l db eu s e di nl o w p o w e ra p p l i c a t i o n s ，s u c ha sj p e gs t i l li m a g ec o m p r e s s i o n f o r p e r s o n a ld i g i t a l c a m e r a sa n da u d i oa p p l i c a t i o n s t h eo t h e rc o u l db eu s e di n r e a l t i m ev i d e o d e c o d i n g ，s u c h a sd i g i t a lt va n do t h e rh i g h s p e e d a p p l i c a t i o n s 3 t h ec o r ei sd e s i g n e dap a r a l l e la r c h i t e c t u r ec o m b i n i n gd i s t r i b u t e da l g o r i t h m a n dl o o k - u pt a b l eb a s e dm e m o r i e s t h ef i r s tc o r ei sd e s i g n e dt oh a n d l ed i f f e r e n tw o r d s i z e sa n di tc a np e r f o r mb o t hf d c ta n di d c t ，w h i l et h es e c o n dc o r eh a n d l e saf i x e d w o r ds i z eo f12 b i t sa n dp e r f o r m si d c to n l y a c c o r d i n gt ot h em o d e m i cd e s i g n m e t h o do ft o pt od o w n ，t h ew h o l es y s t e mi sd i v i d e di n t om o d u l e sf r o mt h et o pt o d o w n a f t e rt h ew h o l es y s t e mc i r c u i t sa r ef i n i s h e d ，t w oh i 曲p e r f o r m a n c ei pc o r eg e t t h e r ea r en om u l t i p l i e rb u to n l ym e m o r i e s ，a d d e r s ，a n dr e g i s t e r s t h es i m u l a t i o na n d s y n t h e s i sr e s u l t si n d i c a t et h ed e s i g nh a ss i m p l es t r u c t u r e s ，p l a i na r r a n g e m e n t s ，a n d g o o dr e g u l a r i t ya n dm o d u l a r i t y 4 d c t i m p l e m e n t s i ns o f b e e a r e ，h a r d w a r e ，a n di pc o r ea r eb r i e f l yc o n t r a s t e d f o r i pc o r e ，t h em o s ti m p o r t a n tp r o p e r t yi sr e u s e w h e nw ed e s i g nac h i p ，w es h o u l d c o n c i d e r p r i c e ，s p e e da n da r e a ( p o w e rc o n s u m p t i o n ) o f t h ec h i p - k e y w o r d s ：d i s c r e t e c o s i n et r a n s f o r m i p c o r e d i s t r i b u t e da r i t h m e t i c f o r w a r d i n v e r s ed i s e r e t ec o s i n et r a s f o r l n 4 中国科学技术大学硕士学位论文 第一章绪论 1 1d c t i d c t i p 核设计背景 在图像处理领域，需要对大量图像数据的传输和存储进行压缩，而变换编码 是绝大部分视频编码系统和标准的核心。在空间域中，图像相邻象素点之间高度 相关，能量往往是均匀分布在整幅图象，因此，从本质上讲，在不影响图象质量 的情况下，希望通过舍弃部分数据或者降低数据精度来进行数据压缩是很困难 的。但是，通过选择合适的变换，在变换域中可以相对比较容易的进行数据压缩。 为进行数据压缩而选择的变换最好有以下属性：压缩图象的能量，去除数据的相 关，以及易于在软件或者硬件上迸行实际应用执行。典型的图象变换算法有d f t 、 d c t 、哈达马变换、h a r t 变换、s l a n t 变换和k - l 变换等，其中离散余弦变换( d c t ) 是一种常用的图象变换算法。d c t 在去除信号相关性方面要比离散傅立叶变换 ( d f t ) 更优越，对于协方差矩阵为t o e p l i t x 矩阵形式的数据，它更接近于最佳 变换。 随着图像处理数据量的增大，用软件实现图像数据的解压已经不能满足图像 处理的速度要求，用硬件实现图像处理算法已经成为必然趋势。在图像和视频信 号压缩的变换编码方法中，离散余弦变换( d c t ) 是最接近于统计最优变换卡 南一洛伊夫变换( k l t ) 的正交变换，因此自a h m e d 、n a t a r a ja 1 1 和r a p 于1 9 7 4 年提 出离散余弦变换概念以来，d c t 已被广泛应用于数字信号处理的各个领域。特 别是图象压缩领域，被广泛用于运动或静止图像的压缩编码算法中，在h d t v 、 h 2 6 1 、h 2 6 3 、j p e g 、m p e g 等压缩标准中，都采用了基于d c t i d c t 的压缩 编码。 随着j p e g 、m p e g 、h d t v 等标准的确立，国外的高校和大公司的研究机构 在d c t i d c t 方面投入了巨大的人力和物力，并迅速将成果转换为产品。当前， 随着集成电路产业的飞速发展，片上系统s o c ( s y s t e m o na c h i p ) 成为发展趋势， 它可以集成不同的功能，比如逻辑功能、存储功能、a d 转换等。s o c 的设计要 求产品能有更短的设计时间、更好的性能和更低的成本，因而人们把目光投向了 高层设计和i p ( i n t e l l e c t u a lp r o p e r t y ) 。分析家们认为，新的i p 时代的到来将给 中国科学技术大学硕士学位论文 系统设计和i c 芯片开发带来根本性的改变，使得它们在功能上分为两类，一个 集中开发i p 核，而另个致力于系统级的集成设计。i p 核的再利用，可以缩短 设计时间，提高设计效率，降低成本，提高可靠性，因此研发可嵌入式的能重复 利用的i p 功能模块具有广泛的应用前景和现实意义。 目前国内拥有多条i c 的工艺生产线，比如上海华虹n e c ，首钢n e c ，无锡华 晶、中芯国际等，工艺水平也已达n o 1 9 u m ，并正在积极筹建几条0 1 3 u r n 的生产 线，可以说在整体制造能力上已经接近国际先进水平。由于i p 的最终实施通常是 依托于工艺生产线进行的，因此我国的整体制造能力为i p 的实现提供了可靠的保 证。但目前国内总体来说在i p 模块的设计开发和应用方面做的不够。建立起来的 现有工艺线基本上是裸线，除流片力n i c b ，不能为设计提供任何条件，整个的i c 设计需要从最基本的晶体管级做起，工艺线失去了这一主要市场。 近年来，国家在“十五”计划将电子信息产业和大规模集成电路的开发列为 关系国家发展、安全的战略地位。为搞好大规模集成电路的开发，科技部于2 0 0 0 年启动了“十五”国家8 6 3 计划超大规模集成电路s o c 专项工作，希望通过这一努 力，初步建成具有自主知识产权、品种较为齐全和管理科学的国家级i p 核库。 通过项目的研究，掌握国际先进水平的s o c 软硬件协同设计、i p 核复用和超深亚 微米集成电路设计的关键技术。 1 2i p 核设计简介 i pr i n t e l l e c t u a lp r o p e r t y ) 核是一个用于f p g a 或a s i c 产品的逻辑模块或数据 模块。作为设计复用( d e s i g nr e u s e ) 的基本单元，i p 核代表了目前正在成长的e d a 工业的趋势，即先前设计的部件能被重复使用而不是只能用一次，这样就可以大 大提高产量和缩短设计周期。理想的口核应该是完全可移植的，就是说能被轻 易的嵌入到任何的用户技术和设计方法中。一般来说，i p 是一个已经完成了设 计和验证的电路模块，就其本质来讲即是一个能提供正确接1 2 i 信号的功能模块。 作为预先设计好的集成电路功能模块，它能够快速有效地集成到系统芯片中。按 其存在形式，i p 核可以分为硬核( h a r dc o r e ) 、固核( f i n nc o r e ) 和软核( s o f tc o r e ) 三种，软核为能综合的h d l 描述，硬核为芯片版图，固核为门级h d l 描述。 6 中国科学技术大学硕士学位论文 所谓的硬核是指经过预先布局且不能由系统设计者修改的i p 。硬i p 核的 电路布局及其与特定工艺相联系的物理版图是固定的，包括全物理的晶体管和互 连掩膜信息，完成了全部的前端和后端设计并己被投片验证正确，特点是提供可 预测的性能和快速的设计，可以被新设计作为特定的功能模块直接调用。硬核设 计有效地保护了设计者的知识产权，但由于硬核的布局不能被系统设计者修改， 所以也使系统设计的布局布线变得更加困难，特别是当在一个系统中集成多个硬 核设计时，系统的布局布线几乎不可能。i p 硬核由于依赖特定的工艺库，目前 国内还没有专门设计i p 硬核的公司，其主要来源是外国的i p 专业供应商、设计 服务公司和f o u n d r y 厂。 固核由r t l ( 寄存器传输级) 的描述和可综合的网表组成，固i p 核在软核 基础上开发，是介于硬i p 和软i p 之间的i p ，是一种可综合的、并带时序信息以 及布局布线规划的设计，以r t l 代码和对应具体工艺网表的混合形式提供，固 i p 既不是独立的，也不是固定的，可以根据用户的需要进行修改，使其适合于 某种可实现的工艺制程。与硬核相比，固核可以在系统级重新布局布线。 软核是一个仅仅以软件形式存在的可综合的完全用h d l 语言描述出来的 i p 模块。软口核通常为抽象的、较高层次的功能描述，用硬件描述语言h d l 或c 语言写成，是对设计的算法级描述或功能级描述，包括逻辑描述、网表和 用于功能仿真的行为模拟以及不能物理实现的用于测试的文档，软d 需要综合、 进行布局布线等。特点是灵活性大、可移植性好，用户能方便地把r t l 和门级 h d l 表达的软i p 修改为应用场合所需要的设计，综合到选定的加工工艺上。但 与硬i p 相比，可预测性差，设计时间长。在目前的综合工具的水平下，可综合 软核在寄存器传输级( r t l ，r e g i s t e r t r a n s f e rl e v e l ) 完成描述。由于其与制造 工艺库完全没有关系，可以作为国内在集成电路设计领域追赶国际先进水平的突 破口。 一个真正的i p 设计有许多特性，如可扩展性、可分割性、软件独立性、可 测性等。关于i p 设计，各个e d a 和器件厂家都有自己的标准。统一的i p 设计 规范还在进一步制定当中。i p 设计随着片上系统的发展而成为目前a s i c 设计中 一个非常活跃的领域。 中国科学技术人学硕士学位论文 i p 模块的再利用，除了可以缩短s o c 芯片设计时间以外，还可以提高设计 效率、节省人力、降低设计成本，提高可靠性，以及满足面市时间( t i m e - t o m a r k e t ) 的要求，因此，研究开发可嵌入式的能重复利用的i p 功能模块将在集成电路设 计和现代s o c 电子系统研发领域具有广泛的应用前景和现实意义。 1 3d c t ，i d c t 的i p 设计 为此，本文根据i p 核设计理念。深入研究了正向和反向离散余弦变换 ( d c t i d c t ) 的实现算法，针对d c t i d c t 的变换特点和变换矩阵系数固有的 对称特性，设计了结合分布式算法和基于存储器查表的并发体系结构。在此基础 上，利用e d a 工具q u a r t u si i ，遵循现代i c 设计自顶向下( t o p t od o w n ) 的 设计方法，从系统总体要求出发，由上自下分层次分模块地逐步将设计内容细化， 最后完成系统的整体电路设计，得到了一个不需要乘法器，只需存储器、加法器 和寄存器的高性能的i p 核电路设计。仿真综合实现结果表明，该设计结构简单、 层次清晰，具有高度的规则性和模块性。 1 4 本文结构 第一章绪论介绍了本文的相关背景和课题意义：第二章介绍了d c t 的正向 和反向f d c t i d c t 基本原理；第三章对不同的d c t 算法和不同的结构做了简 单的介绍，在每一种类型中，对一些代表性的论文散了简短的描述和比较；第四 章介绍了基于实现算法的i p 核电路的具体设计；第五章对全文做了总结和展望， 给出了一些不同的算法和思路。 8 一 一! 里型兰垫查查堂堡主兰垡堡苎 第二章离散余弦变换，反变换( d c t i d c t ) 原理 2 1 简介 自1 9 7 4 年a h m e d 、n a t a r a j a n 和r a o 首次提出离散余弦变换( d c t ，d i s c r e t e c o s i n et r a n s f o r m ) 以来，d c t 已广泛地应用在图象及数字信号处理中，特别是 在数据压缩领域，因为d c t 基向量类似于正交变换中的最佳变换卡南洛伊 夫变换( ) 。正交变换的晟重要的应用是数据压缩，而其关键是给信号以有 效的表达方式，即将一组离散信号( n 个采样植) 由时域映射到n 维变换域， 使其能量在变换域中更集中于某一区域。即，与在时域相比，该信号在变换域中 的编码只需用较少的比特数表示，而不致引起明显误差，从而剔除了信息冗余度， 压缩了数据量。在均方误差最小的意义下，获得数据压缩的最佳变换是卡南洛 伊夫变换( k l t ) ，它使得信号在变换域中各值之间互不相关。但k l t 的变换矩 阵是由原信号的协方差矩阵的本征矢量组成且没有快速算法，在硬件上难以实 现，所以没有得到广泛的应用，一般只做理论分析。对众多的具有快速算法的正 交变换( d f t 、w h t 、h t 、d c t 等等) 的研究结果表明，d c t 的性能最好，最 接近k l t 的正交变换，同时，它所产生的混叠现象较之d f t 、w h t 等要小得多， 是一种高效的变换编码方式。 目前在图象压缩中应用最广泛的两种变换是离散余弦变换( d c t ) 和离散小 波变换( d w t ) 。进行变换时，前者通常用于图象中小块规则的采样点，例如8 x 8 的方阵；而后者通常用于大片区域或者整幅图像。实践证明，d c t 非常适合数 据压缩，因而被选做当前大部分图像和视频标准的核心变换，包括j p e g 、h 2 6 1 、 h 2 6 3 、m p e g - 1 、m p e g - 2 和m p e g 4 均采用d c t ；d w t 因为在静态图像编码 中性能优于d c t ，正开始逐步流行，在新的j p e g 2 0 0 0 和m p e g - 4 纹理静态图 像编码中选用了d w t 。但是在时域中基于小波变换，且易于计算的运动估测依 然没有找到，所以在运动视频压缩中，小波没有得到广泛的应用。d c t 现在已 经成为图象数据压缩中最通用的图像和视频编码变换，其变换后的图像数据易于 进行高效的压缩，速度快，算法简单，易于在软件和硬件上实现。 9 中国科学技术大学硕士学位论文 正向离散余弦变换( f d c t ，f o r w a r dd c t ) 将空间域的象素点变换到频域中 的系数，该变换是可逆的，反向离散余弦变换( i d c t ，i n v e r s ed c t ) 在解码时， 将频域中的系数恢复为空间域中的象素点。在图像和视频压缩中，通常选用维 或者二维变换。d c t 压缩时，去除数据相关性，将能量聚集，在左上角的系数 最大值对应于低频的能量，而向右下角的快速减小的系数对应于高频部分：许多 系数的数值很小，可以在不影响图像视觉效果的前提下丢弃。离散余弦变换的去 相关和压缩效果会随着所选图像块尺寸的大小而增加，但其计算的复杂度也会呈 指数增加。 所有的d c t 都遵循下面的变换模式： 饥明= 缸” 甜付虹以】_ x 【七玢“ 该模式是由w a n g 观察得到的。四种不同d c t 实例的核函数c 铲分别由 d c t - i ：四。= 2 c 【川e 【】c o s ( 酞 k = o ，l ，n d c t - i i ：甜= 厕 1 s ( 坳+ 吉) 景) 础- 0 ，k - 一l d c t - i i i ：四= 4 - 2 f n c k c o s ( 撒+ 圭) 斋) 蛳_ o ，1 ，肛1 d c t - i v ：甜= 丽c 。s ( ( i + 争( 斛主) 旁蛳- 0 ，l t ，1 定义。其中除了缸o 】- l 互外，c 【纠= 1 。d c t - i i 的二维变换常在图像压缩中应 用，是j p e g 、h 2 6 1 、h 2 6 3 、m p e g 1 、m p e g - 2 和m p e g - 4 的核心变换，因此， 本文中的离散余弦变换均选用d c l - i i 。 2 2 正交变换特性 d c t 是正交变换的一种。它是通过正交变换把图象从空间域转换到能量比较 集中的变换域，然后对变换系数进行量化、编码，从而达到压缩数据的目的。 正交变换之所以能够压缩数据，主要有以下性质： 1 交变换具有熵保持性，即通过正交变换后并不丢失信息。 2 变换具有能量保持性，并能把能量重新分配与集中。这就有可能采用熵压 缩法来压缩系数，即在质量允许的情况下，舍弃一些能量很小的系数，而对能量 较大的系数分配较多的比特，对能量较小的系数分配较少的比特，从而使数据有 1 0 中国科学技术大学硕士学位论文 较大的压缩。 3 去相关性，可使高度相关的空间样值变为相关性较弱的变换系数，从而减 少空间样值之间冗余度。 常见的正交变换有d f t ( 离散傅立叶变换) 、d w h t ( 离散沃什哈达玛变 换) 、d c t ( 离散余弦变换) 、s t ( 斜变换) 、k - l ( 卡南一洛伊夫变换) 等。目前， 在图象数据的压缩编码方案中广泛采用d c t 变换，有以下几个原因：一是d c t 变换接近最佳k l 变换。因为k l 变换能产生非相关的变换系数( 非相关变换系 数对压缩极为重要) ，可以单独处理各系数而不损失压缩效率，但k l 变换至今 没有快速算法，因此，因此无法用硬件来实现。二是用d c t 而不用d f t 的原因在 于，d f t 要进行复数运算，一次复数相当于四次实乘和二次实加，因而d f t 需要 的运算量很大，难于满足实时图象处理的要求，而d c t 是一种实数域的变换，需 要的运算量比d f t 要少很多。 2 3d c t i d c t 原理 2 3 1i df d c t i d c t 的定义 正向维离散余弦变换的定义由下式表示： 脚) = 后c 薹m ) c o s l ( 2 x + r 1 ) u x ( 1 ) 其中，当u = 0 时，c ) = 1 三，否则c ( “) = 1 。式中f ) 是第u 个余弦变换系 数，u 是广义频域变量，“= 0 ，l ，1 一，n 一1 ；，( 功是时域n 点序列，z = 0 1 ，n 一1 。 反向一维离散余弦变换的定义由下式表示： 似) = 厝c 篓脚o s l ( 2 x + r 1 ) u 7 r ( 2 ) 其中，各变量含义同( 1 ) 式。若定义 c 】为变换矩阵，【f ( 甜) 】为变换系数矩阵， 【，( x ) 】为时域数据矩阵，则一维d c t 的矩阵定义式可写成如下形式： 【f ( 甜) 】= 【c 【，( 戈) 】；【，( z ) 】= 【c 】1 【f ( “) 】 一一! 里型兰垫查查鲎堡主堂垡堡塞 2 3 2 2 d f d c t ，i d c t 的定义 正向二维离散余弦变换的定义由下式表示： ，( 甜，。) ：昙窆n - i c ( “) c ( v ) 厂( x , y ) e o s 垦型丝c o s ( 2 y + 1 ) w r ( 3 ) 脚，归素x - o y = 0 c ( 彬( v ) 厂鼍笋1 厂( 3 ) v 二vz v 其中，c ( o ) = l 压；当“，v 0 时，c ) = c ( v ) ：1 。x ，y 是空间域象素的坐 标，f ( x ，y ) 表示空间域二维向量的象素值，“，v 是d c t 空间的坐标，f ( u ，v ) 是 d c t 空间中的变换系数值。x ，y = 0 ，l ，1 一，n 1 ，v = o ，l ，1 ，n 一1 ，式中表示的 阵列为n x n 。 反向二维离散余弦变换的定义由下式表示： r ( ty ) ：三爹爹c ( u ) c ( v ) f ( u , v ) c o s ( 2 x + 1 ) u z rc o s ( 2 y + 1 ) v x ( 4 ) 似，y ) 2 专u = o v = o2 百( 4 ) y二y二v 式中各变量含义同( 3 ) 式。若定义【c 】为变换矩阵，【f ( x ，y ) 】为空间数据 阵列，【f ( u ，v ) 】为交换系数阵列，则二维d c t 的矩阵定义式可写成如下形式： f ( u ，v ) = 【c l f ( x ，_ y ) 】 c r ：【f ( x ，y ) 】= c 九f ( “，v ) 】 c 】 2 4d c t 算法 f d c t 和i d c t 的二维变换，可以直接将n x n 个数据输入做变换，这种经 过最优化的二维变换算法被称作直接二维算法。当然，也可以通过多重一维变换 来实现二维变换，这是由于二维d c t 的可分离属性，可以先在每行上进行一 维变换，然后在每一列上再做一维变换，这种方法需要2 n 次n 点一维d c t 来 实现n x n 的二维d c t 。 方程中的系数因子和在d c t 变换中是固定不变的，许多d c t 算 法在处理该因子时选用不同的因子值或者省略该值。因为一般情况下选定的该值 是2 的幂，可以在后续的量化中加以处理，所以不会影响计算的复杂度。实现 f d c t 和i d c t 最直接的方法就是直接计算完全矩阵向量乘法，用该方法执行一 维d c t 需要2 次乘法和n ( n 1 ) 次加法，二维d c t 需要4 次乘法和2 ( 2 1 ) 中国科学技术大学硕士学位论文 次加法。尽管该方法需要最多的操作次数，但是最大的优点是非常规则，最适合 向量处理器或者深度流水线结构，不会因为计算不规则导致不能充分利用处理资 源。大部分已提出的快速算法复杂度为o ( n l o g n ) ( 1 - dd c t ) 和o ( n 2l o g n ) ( 2 - dd c t ) 。 2 4 1 基于f f t 计算 在d c t 最初被a h m e d 、n a t a r a j a n 和r a o 提出时，采用的就是基于f f t 的 计算方法。n 点d c t 可以通过2 n 点f f t 和后续处理来实现。根据d c t 的定义， 并且忽略公式前的系数因子和c ( u ) ，可有下式： 脚) ：n - i 俐c o s l ( 2 x + f 1 ) u n ：r e 艺f ( x ) e 一等i x = 0 二- v _ x = 0l 戢p 芝x = 0m 1 等h e 茜篓胛叭蝴 ( 5 ) 式中f f t ( f ( u ) ) 是n n c f ( o ) ，f ( 1 ) ，f ( n 一1 ) ，o ，o 】的2 n 点离散傅立叶变换，即在x ) 后加上n 个0 。利用快速傅立叶变换可以将向量乘法的计算复杂度从o ( n 2 ) 降低 到o ( n l o g n ) 。因为式( 6 ) 中的2 n 点f f t 只需要实数输入，因此可以用现有 的一些f f t 算法加上后续处理，来进一步降低计算的复杂度。 2 4 2 奇偶分解算法 奇偶分解法是d c t 中最明显的可以减少乘法和加法次数的方法。该算法利 用余弦系数的对称性和反对称性。以8 点d c t 为例进行说明： f ) =厂( x ) = c f ( x ) ( 6 ) 式中c 表示c o s ( i t c 1 6 ) 。观察( 6 ) 式会发现，第一列和最后一列除了符号不同 出石西石西以靠砌 西砌靠西力凸砌“出以以凸乃砌玉石 靠白以如臼出“凸 出力砌出玉以以凸小曲砌所西出以以 凸出以石力西西n 西“靠力乃以而册， q q 鼍 n q q n 叮 嗡 1 ! 塑型堂茎查查兰塑主兰堡堡兰 外，数值一样；第二列和倒数第二列也是同样，其它列以此类推。利用矩阵的对 称性和反对称性将矩阵分为左右两部分，则( 6 ) 式可重新表示如下： f ( 0 ) f ( 1 ) f ( 2 ) f ( 3 ) f ( 4 ) f ( 5 ) f ( 6 ) f ( 7 ) c 4矗 岛吒 c 4 c 4 气c 2 00 00 00 00 1o 0 0o0 ol0 00o 0 01oo1 00011o 1ooooo o1o000 0 0l00 一l oo 01一lo ( 7 ) 此种表达方式只需要计算3 2 次乘法和3 2 次加法，而前面所述完全矩阵向量乘法 需要6 4 次乘法和5 6 次加法来完成变换。对( 7 ) 式的余弦系数矩阵的左上角1 4 做分解处理，则可以进一步减少乘法的次数。以8 点d c t 为例，变换为f 8 ) 式只 需要2 2 次乘法和2 8 次加法。 利用( 7 ) 式计算d c t 被称作级奇偶分解算法，利用( 8 ) 式被称作全级 奇偶分解，或者简单的称做奇偶分解算法。在( 8 ) 式中，2 2 次乘法里有2 次涉 及到比例因子c 4 = i 4 2 ，如果将整个余弦矩阵乘以2 ，就可以在改变其它因子 ，( o ) f ( 2 ) f ( 4 ) f ( 6 ) f 0 ) f o ) f ( 5 ) f ( 7 ) 1o 一1o o1 0 o 00 o o o o 00 1 4 o o o o白鸭岛1 o o o 0岛q唧岛 o 。o o已，1飞 o o 0 o q 巳乌岛 q 乞q 吒o o o o 一 一 q q e o o o o m圆 八八八八八八八八 ，0 o 0 j o o o o 1 o o o 1 o o o o o o岛，q 1 0 o o 0幺畸q q o o o o岛，1， o o o o q 岛略唧 0 0 吒0 o o o 一 0 o 乞吒o o o o o q 0 o o o o o 气o o o o o o o 儿 0 o o o o o 0 l 、 o o o o o o 1 o o o o o o ，o 0 o o o o l o 0 o o 0 0 l 0 d 0 0 00 oo o1 1o 00 o0 0一l 10 f