嵌入式块解码器研究与硬件设计

中南民族大学硕士学位论文嵌入式块解码器研究与硬件设计姓名:陈方强申请学位级别:硕士专业:通信与信息系统指导教师:熊承义20090607中南民族大学硕士学位论文摘要嵌入式优化截断块编码(EmbeddedBlockCoderwithOptimizedTruncation,简记为EBCOT算法是由DavidTaubman提出的一种图像压缩编码技术。EBCOT编码算法采用了独特的两层编码结构,并引入了多通道位平面编码以及分层组织比特流的技术,这样不仅具有更好的压缩性能,而且使得生成的码流具有分辨率可伸缩、质量可伸缩、随机访问和处理等优秀的特性。EBCOT算法被最新的静止图像压缩标准JPEG2000采纳为其编解码引擎。在JPEG2000的诸多应用中,如数码相机、高清电视、卫星遥感图像处理,考虑到速度、面积和功耗的需求,研究高性能EBCOT编解码器的硬件实现具有十分重要的意义。论文的主要工作包括:首先对静态图像压缩标准JPEG2000及其主要架构进行了简要的介绍。然后详细介绍了JPEG2000中的EBCOT算法以及整体架构,并对位平面解码BPD算法进行了重点介绍。在此基础上,针对硬件高速实现,对其进行了优化。采用了基于选择性采样跳过策略和推测处理方式的位平面解码架构,这样就可以大大减小关键路径的延迟。相对于现有方法的基本BPD架构,改进的算法可以将吞吐量提高50%-100%,同时只增加25%-30%的硬件消耗。在介绍MQ算术解码算法的基础上,详细分析了架构中解码的工作流程及各个流水级模块的设计。进行相应算法优化的基础上,提出了基于4级流水线的高性能MQ解码器结构。在QuartusII开发环境下对设计进行RTL级描述,用Modelsim进行了相应的功能仿真;针对Altera系列FPGACycloneIIEP2C35F484C8进行综合,并完成时序仿真。实验结果表明:该设计的最高工作频率可达37.64MHz,占资源为557个LE。在利用有限资源的情况下可以大幅度提高MQ算术解码器的速度,基本能满足JPEG2000系统的要求。关键词:嵌入式优化截断块编码位平面解码MQ算术解码现场可编程门阵列-I-I嵌入式块解码器研究与硬件设计AbstractEBCOT(EmbeddedBlockCoderwithOptimizedTruncationalgorithmisanimagecompressioncodingtechniquesproposedbyDavidTaubman.EBCOTencodingalgorithmusesauniquetwo-tiercodingstructureandintroducethetheoryofmulti-channelbit-planecodingandthehierarchicalorganizationofbit-stream.Thus,ithasnotonlybettercompressionperformance,butalsomakesthegeneratedcodestreamwithOutstandingcharacteristicsofscalableresolution,scalablequality,andrandomaccess.EBCOTalgorithmisadoptedascodecengineofthelateststillimagecompressionstandardJPEG2000.Inconsiderationofspeed,areaandpower,thestudyonthehardwareimplementationofhighperformanceEBCOTcodecissignificantinmanyrealsystemsusingJPEG2000,suchasdigitalcamera,highdefinitiontelevision,Satelliteremotesensingimageprocessingandsoon.Thecontributionsofthisthesisincludes:Atfist,abriefintroductionofstillimagecompressionstandardJPEG2000anditsmainstructurewasmadeinthispaper.WedescribedtheEBCOTalgorithmindetail,aswellastheoverallframework.Basedonspecialintroductionofbit-planedecoderalgorithm,weoptimizedthedecoderflowforthehigh-speedhardwareimplement.Wehavestudiedanovelselectivesample-skippingstrategyforBPDtoincreasetheoverallblockdecoderthroughput.Thecriticalpathoftheproposedarchitectureisfurtherimprovedbytheuseofspeculativeprocessing.Thethroughputratesoftheusedarchitecturesarehigherby50%-100%,thanthebaselinearchitecturethatisbasedonexistingapproaches.Theincreasedthroughputratesarearchivedwithonlya25%-30%increaseoftheBPDhardwarecost.Then,theMQarithmeticdecodingalgorithmhasbeeninvestigatedindepthinthispaper.AhighperformancearchitectureofMQdecoderwith4-stagepipelinehasbeenproposedbyalgorithmoptimization.ThisdesignhasbeendescribedbyusingRTLHDL,andimplementedwithAltera’sFPGACycloneIIEP2C35F484C8.ThefunctionalsimulationandtimingsimulationarecarriedoutunderQuartusIIsoftware.Experimentalresultsindicatethatthemaximumoperationfrequencyoftheproposeddesigncanreachashighas37.64MHz,using557LE.Byusingonlylimitedresources,thespeedofMQdecodercanbeefficientlyincreased,whichalsomeettherequirementsofJPEG2000system.Keywords:EBCOTBPDMQdecoderFPGAII中南民族大学学位论文原创性声明本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名:日期:年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权中南民族大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密□,在______年解密后适用本授权书。√2、不保密□。(请在以上相应方框内打“√”作者签名:日期:年月日导师签名:日期:年月日中南民族大学硕士学位论文第1章绪论1.1课题背景近些年来,随着多媒体技术和互联网的不断发展,图像压缩技术也获得了空前的进步。数码相机、数码摄像机等手持式设备的普及应用,要求图像压缩技术能够在较高的压缩比下实现较好的图像质量,以满足存储空间有限条件下的海量数据压缩问题。同时,医疗,遥感等应用领域要求图像压缩提供较好的灵活性和延展性。传统的JPEG标准已无法满足人们对于多媒体图像处理的要求,由此诞生了新一代静止图像压缩标准JPEG2000[1]。相对于JPEG来说,JPEG2000提供了一套新的标准,它所具有的一些特征对于一些互联网和多媒体技术应用是非常重要的。JPEG的四种模式——顺序模式、渐进模式、无损模式和分层模式被集成在一个新的标准之中。在编码端以最佳的压缩质量(包括无失真压缩和最大的图像分辨率压缩图像,在解码端可以从码流中以任意的图像质量和分辨率解压图像。因而,JPEG2000可以在大多数图像领域得到应用,如数码相机、互联网、彩色传真、数字摄像、医疗图像、移动通信、数字电影等。JPEG2000编码系统的基本架构可以分为预处理、空间变换、位平面建模和算术编码等几个部分。其中,空间变换采用DWT[2](DiscreteWaveletTransformation,离散小波变换,在相同的图像压缩率下,对静止图像,DWT编码能够获得比DCT编码高约1dB的峰值信噪比[3]。JPEG2000引入全新的EBCOT(EmbeddedBlockCodingwithOptimizedTruncation算法,它是JPEG2000体系中的关键部分,数据压缩和码流控制都在这里实现,具有计算密集,以位处理为主,耗时较大的特点。EBCOT编码算法采用了独特的两层编码结构,第一层(Tier-1包括上下文环境建模[4]和算术编码[5]两部分,进行嵌入式块编码产生压缩的码流。第二层(Tier-2对生成的压缩码流进行分层组织,采用了压缩后率失真优化算法和质量层技术。在整个JPEG2000编解码系统中,EBCOT编解码器已经成为系统运算速度的瓶颈。因此,如何立足于硬件实现,提高EBCOT编解码效率成为JPEG2000编解码系统硬件高速实现需要解决的关键问题之一。因此在本课题中,需要对JPEG2000中的位平面解码算法和算术解码算法进行优化,降低其算法复杂度,并使其适合于硬件实现;同时设法提高编解码效率和降低硬件规模,使其达到高速解码及节省硬件资源的要求。-1-11.2研究现状在JPEG2000编解码系统的实现上,有基于软件的实现方案和基于硬件的实现方案。其中,Jasper[6],Kakadu,OpenJPEG等都是比较流行的JPEG2000编解码软件。与基于软件的解决方案相比,基于VLSI的硬件解决方案在编解码效率上更高,更适合实时编解码的要求,但其开发的复杂度也更高,调试更困难。自从JPEG2000标准诞生以来,多家公司和研发机构发布了基于JPEG2000标准的硬件解决方案,其中最成功的是ADI公司的ADV202芯片[7]。它是一款单片JPEG2000编解码芯片,具有实时压缩和解压缩标准清晰度(SD视频信号和高清晰度(HDTV视频信号功能,该芯片带有一个灵活接口,适用于多种视频和静止图像格式。ADV202有两种工作模式,一种是编码模式,另一种是解码模式。在编码模式下,视频数据通过VDATA总线输入ADV202,由小波核对输入的数据进行小波变换,并把所有频率子带的小波系数存入ADV202内部的存储器。每一个子带根据ADV202编码参数的设置进一步分成编码子块,然后由熵编码器对编码子块执行内容建模和算术编码,运算的结果存入内部存储器。随后由内部DMA传输到CODEFIFO,通过HDATA总线把压缩数据流输出ADV202。在解码模式下,工作过程是编码模式的逆过程[8]。然而,由于JPEG2000编解码算法的复杂性,直到目前为止,其VLSI实现的大规模市场应用尚未展开,因此,研究JPEG2000编解码系统的高性能低资源占用的VLSI实现仍然是当前的一个研究热点,而其中对于作为系统速度瓶颈的自适应算术编解码VLSI实现的研究尤其具有重要意义。算术编码是一种到目前为止最佳的熵编码方法。但早期的算术编码存在无限精度运算的问题,即随着编码消息长度的增加,递归运算需要的计算精度随之增加,表示数据所需的位数也随之增多,这导致软硬件实现的成本太高,阻碍了它的应用。直到有人证明编码过程可以用有限精度处理技术逼近,算术编码才真正开始得到广泛的应用。算术编码的另一缺陷是编码速度太低,这是因为编码迭代过程中含有整数乘除运算,这些运算对于软件执行和硬件设计是十分不利的。IBM公司对算术编码进行了大量的研究,提出了一个用移位和加法实现二值算术编码的方法,从而避免了复杂的乘除运算,并发表了著名的Q编码器[9][10],随后又提出QM编码器[11](用于JBIG标准和MQ编码器(用于JBIG2和JPEG2000标准。MQ编码器在Q编码器的基础上,进一步改进了符号概率估计系统。在MQ算术编解码器的VLSI实现方面,国内外的研究人员做了大量的研究,提出了很多有价值的实现方案,并采用了很多先进的VLSI设计技术。本文对当前国内外在该方向的研究现状和先进技术进行了了解并加以综合分析,以作为本文的参考和借鉴。1.3本文的主要内容和结构论文共分5章,第1章绪论,第2-4章为论文的主体部分,第5章为总结和展望。论文的详细安排如下:第2章为本论文的理论基础。主要对静态图像压缩标准JPEG2000及其主要架构进行了简要的介绍。然后详细介绍了JPEG2000中的EBCOT算法以及整体架构。第3章对位平面解码算法进行了重点介绍,并在此基础上,针对硬件高速实现,对其进行了优化,采用了基于选择性采样跳过策略和推测处理方式的位平面解码架构,并做了相应的性能分析。第4章在详细介绍了MQ解码算法的基础上,详细分析了架构中解码的工作流程及各个流水级模块的设计,并进行了相应的算法优化,提出基于4级流水线的高性能MQ解码器结构。最后进行了性能分析和功能仿真。第5章得出结论,对本文的成果进行了总结,并对今后的研究进行了展望。第2章JPEG2000标准介绍本章阐述了最新的静态图像压缩标准——JPEG2000核心编码技术的发展背景,介绍了该标准的应用领域及其新特征、编码系统结构、标准文件格式和相对JPEG所采用的新技术。2.1JPEG2000核心编码技术的发展基于小波变换的图像编码方法是上个世纪90年代左右提出的新方法,它吸收了变换编码和子带编码的优点,克服了传统DCT[12]编码在低比特率时会产生方块效应的缺点,能够更好的利用人的视觉特性。另外,由于小波变换具有非常好的能量聚集性能,而且能够用于图像变换的小波基非常丰富,因此基于小波变换的图像编码成为目前图像压缩领域的一个研究热点。最新的静态图像压缩标准——JPEG2000中采用的是一种基于最优截断的嵌入式块编码算法(EBCOT:EmbeddedBlockCodingwithOptimizedTruncation,它是将图像小波变换后生成的子带进一步分成小的矩形码块。每个码块采用基于位平面的方式进行独立编码,并采用基于内容模型的算术编码进行压缩生成压缩码流。为了使编码图像达到目标比特率,对每个码块计算率失真曲线上的几个分割点,并由此实现对每个码块的比特数进行最优分配。因此在编码时,首先对每个码块用较高的比特率编码,然后再根据最优比特率分配计算确定的分割点来截断每个块的比特流。对应于一个目标比特率集合,可以确定其对应的最优分割点集。码块的比特流一旦被截断来达到目标比特率,就按通常的位平面顺序重新组织形成嵌入式比特流。EBCOT编码算法得到的比特流具有多分辨率和多层次质量优化的特征,其率失真性能略优于SPIHT算法,但复杂程度也高于SPIHT算法。2.2JPEG2000的应用及特征JPEG2000标准提供了一套新的特征,它把JPEG的四种模式(顺序模式、渐进模式、无损模式和分层模式集成在一个标准之中。在编码端以最大的压缩质量和最大的图像分辨率压缩图像,在解码端可以从码流中以任意的图像质量和分辨率解压图像,最大可达到编码时的图像质量和分辨率。JPEG2000应用的领域包括互联网、传真、打印、扫描、数字摄像、遥感、移动通信、医疗图像和电子商务等等。它的最主要的特征如下:(l高压缩率:由于在离散子波变换算法中,图像可以转换成一系列更加有效存储像素模块的“子波”,因此,JPEG2000格式的图片压缩比可在现在的JPEG基础上再提高10%—30%,而且压缩后的图像显得更加细腻平滑。(2无损压缩和有损压缩:JPEG2000提供无损和有损两种压缩方式,无损压缩在许多领域是必须的,例如医学图像中有时有损压缩是不能忍受的。同时JPEG2000提供的是嵌入式码流,允许从有损到无损的渐进解压。(3渐进传输:采用JPEG2000格式的图像支持渐进传输(ProgressiveTransmission。即先传输图像轮廓数据,再逐步传输其他数据来不断提高图像质量。(4感兴趣区域压缩:可以指定图片上感兴趣区域(RegionofInterest,然后在压缩时对这些区域指定压缩质量,或在恢复时指定某些区域的解压缩要求。这是因为子波在空间和频率域上具有局域性,要完全恢复图像中的某个局部,并不需要所有编码都被精确保留,只要对应它的一部分编码没有误差就可以了。(5码流的随机访问和处理:这一特征允许用户在图像中随机地定义感兴趣区域,使得这一区域的图像质量高于其它区域,码流的随机处理允许用户进行旋转、移动、滤波和特征提取等操作。(6容错性:在码流中提供容错性有时是必要的,例如在无线等传输误码很高的通信信道中传输图像时,没有容错性是让人不能接受的。(7开放的框架结构:为了在不同的图像类型和应用领域优化编码系统,提供一个开放的框架结构在是必须的,在这种开放的结构中编码器只实现核心的工具算法和码流的解析,如果需要,解码器可以要求数据源发送未知的工具算法。(8基于内容的描述:图像文档、图像索引和搜索在图像处理中是一个重要的领域,基于内容的描述在JPEG2000中是压缩系统的特性之一。2.3JPEG2000编码系统结构国际标准15444中给出了JPEG2000标准核心处理算法的处理流程。这里给出了详细的编码器结构如图2.1所示。图2.1JPEG2000编码框图在编码过程中,首先对输入图像进行预处理和直流变换,分成不同的图像分量和基本的编码单元块(称为Tile,然后对每个Tile进行小波变换,变换后的数据根据要求选择是否进行标量量化处理。然后将处理后的各个子带数据分成固定尺寸的码块(CodeBlock,每个码块单独地进行位平面编码和算术编码处理,生成各个码块的嵌入式码流。然后,按照率失真最优理论分层组织,形成不同质量的层(Layer对每一层,按照一定的码流格式打包,输出压缩码流。解码过程是编码过程的逆过程,根据压缩码流中存储的参数,对应于编码器各个部分进行逆向操作,首先对码流进行算术解码、位平面解码,然后解量化和小波反变换,最后生成重建图像。JPEG2000编码过程主要分为以下几个过程:预处理、核心处理、码率控制和位流组织。预处理部分包括直流变换(DC变换、分量变换和图像分片。核心处理部分由离散小波变换、量化、位平面编码和算术编码组成。码流组织部分则包括区域划分、码块、层和包的组织。2.4JPEG2000的文件格式在ISO-15444Part1规定基本的文件格式JP2。文件格式JP2提供了如下一种机制,即可以将应用规范与JPEG2000的码流数据关联起来。虽然,JPEG2000的码流是完全自包含的,但是在应用的时候必须对其进行解码,此外一些与厂商相关的信息以及版权信息是无法在JPEG2000的压缩数据码流中包含的,而这些应用规范的内容可以以包含在JPEG2000的文件格式中。这种文件格式提供了知识产权信息和厂商信息,可以做到添加水印以保护产权。根据上面的说明,我们相信JPEG2000将会成为主流的静态图像压缩标准,广泛得应用于因特网、移动和便携设备、印刷、扫描(出版物预览、数字摄影、遥感、传真(包括彩色和因特网传真、医学应用、数字图书馆、电子商务等领域。2.5JPEG2000与JPEG标准比较较之前身JPEG静态图像压缩标准,JPEG2000标准有了很大的发展。其编解码器采用了如下的很多新技术:(1用离散二维小波变换(DWT取代离散余弦变换(DCT;(2在应用离散小波变换时,分别引入对数据整型到整型(IntegertoInteger的可逆(Reversible变换和实型到实型(RealtoReal的不可逆(Irreversible变换,从而实现对图像的无损(Lossless压缩和有损(Lossy压缩两种不同的编码处理;(3采用了较以往各种零树编码更优越的编码算法——EBCOT算法(基于优化截断的嵌入式块编码算法;(4对量化后的小波变换系数采用基于位平面的多通道编码技术;(5采用基于上下文关系(Context-Based的自适应二进制算术编码器(MQCoder实现高效的算术熵编码;(6采用两级原语表示编码后的图像,分别为码流和文件格式原语。2.6EBCOT算法简介嵌入式优化截断块编码EBCOT(EmbeddedBlockCoderwithOptimizedTruncation算法是由DavidTaubman提出的一种最新的图像压缩编码技术。EBCOT编码算法采用了独特的两层编码结构,引入了多通道位平面编码及分层组织位流的思想,因此不仅具有更好的压缩效果,而且生成的码流具有分辨率可伸缩性、质量可伸缩性、随机访问及处理等优良的特性。EBCOT被采纳为最新的静止图像压缩标准JPEG2000的编解码引擎。由EBCOT生成的嵌入码具有下列优秀的特征:1可伸缩性的实现。通过以代码块为单位对小波变化后的子带信号进行为平面编码,可以实现分辨率、失真(SNR和位置的可伸缩性。还由于对色彩图像也增加了分量的可伸缩性,所以,在JPEG2000中可在这些四维度上实现可伸缩性编码。2紧密的内嵌处理。在通常的位平面编码中,由于以位平面进行压缩码的截断,所以,构成嵌入码时的截断精度粗糙。在EBCOT中,再以3个编码扫描对一个位平面进行编码,将各个扫描结束时间点选为代码截断点,因此,可实现更精密的内嵌处理。3可并行处理。由于能以代码块为单位单独进行编码,所以,可通过编码和解码的并行处理实现高速处理。4高容错性。由于码流被分层为空间位置、质量层,使子带分层化,所以,可使部分码流里引起的错误限制在局部区域。EBCOT算法的两层编解码结构如图2.2所示。第一层(Tier-1包括上下文环境建模和算术编码两部分,进行嵌入式块编码产生压缩的码流。第二层(Tier-2对生成的压缩码流进行分层组织,采用了压缩后率失真优化算法和质量层技术。具体来说第一层编码由以下几个步骤组成:(1将经过小波变换和量化后的子带系数组织成编码块(code-block;(2对每个编码块进行独立的多通道位平面编码(fractionalbit-planecoding,形成相应位样本的上下文环境和决策数据对(Context-Decisiondatapairs;(3用基于上下文环境的自适应算术编码器(MQ-coder对形成的上下文环境(Context和数据(Data进行算术编码,产生嵌入式位流(embeddedbit-stream。EBCOT算法的第二层编码对压缩位流进行分层组织,即按照率失真最优的原则,选取合适的截断点截断每一个编码块的压缩位流,在满足目标码率的要求下,将位流组织成具有分辨率可伸缩性和质量可伸缩性的最终码流。图2.2EBCOT算法架构在EBCOT算法的两层编码结构中,其编码独立地实现于每一个编码子块,基于每个编码块的独立编码使得随机存取及分辨率可伸缩性〔resolutionscalable〕成为可能。EBCOT算法中的上下文环境建模引入多通道分数位平面编码的思想,由此可得到比单一位平面编码更多的截断点个数。越多的截断点,表明图像可提供更多的质量选择。EBCOT算法在第二层编码中通过采用率失真优化及质量层的技术保证了压缩码流具有质量层的可伸缩性(SNRscalable。2.7小结本章首先介绍了JPEG2000核心编码技术的发展及其应用和特征;详细说明了JPEG2000编码系统结构中的划分:其中包括预处理、核心处理、码率控制,及这三个部分的工作原理,JPEG2000的文件格式;然后对JPEG2000和JPEG标准进行了比较,最后介绍了EBCOT算法、特征及其特殊的两层结构。第3章位平面解码器的硬件设计研究3.1研究现状为满足多媒体应用和互联网产品如数码相机,高清电视等的高速实时运行的要求,位平面编解码器的硬件实现成为一种必然,为此高速高性能位平面编解码器的VLSI实现已成为国内外有很多机构和学者研究的热点。迄今为止,已经出现很多新的技术[13-23]能够很好的提高位平面解码器的性能,其中主要包括三类:通道并行编码,优化串行编码和位平面并行编码。为提高位平面编解码器的吞吐量,必须减少扫描冗余时间,提高处理的并行性;为了降低系统功耗可以考虑减少对存储单元的访问次数;为减小系统VLSI实现的面积,通常会尽量减少中间存储单元的的规模.在减少冗余扫描时间方面,Lian等人[24]首先提出了一种基于采样跳跃(sampleskipping和样条组跳跃(Group-of-columnskipping的优化串行位平面编码扫描技术,朱悦心等人[25]提出了一种基于多级查询表的位平面扫描优化方法,它们都可以一定程度上减少冗余扫描时间.在并行编解码方面,Chiang等人[26]提出了一种通道并行编码技术,在提出对当前样条列的重要性传播通道,延迟样条列的幅度细化通道和清除通道并行处理的基础上,实现了3个编码通道对位平面的扫描一次完成.在改进存储单元访问方面,Fang等人[17]提出了一种基于字级(位平面并行的编码算法和结构,在文献[18]中Fang等人又提出用两次扫描来完成字级位平面并行编码,这种方法需要较多的中间存储单元.Amit等人[27]提出一种基于选择性样本跳过方法的位平面解码器结构,它与Dyer等人[28]提出的低延迟算术解码器级联可以减少位平面解码器在解码过程中的等待时间,大大提高了处理速度和吞吐量。3.2位平面编解码概述上下文建模又称为位平面编码(BPC,Bit-PlaneCoding,上下文建模就是将小波变换系数划分成固定大小的代码块,再将各个变换系数作位平面展开,对码块进行逐个位平面的扫描,对每个位形成一个上下文标志(CX,ContextLabel和判决位(D,Decision。图3.1上下文建模扫描方式在上下文建模过程中,编码过程从最重要的位平面开始依次进行扫描编码,每次编码一个系数位平面;每个位平面按照规定的顺序进行数据扫描。扫描过程从位平面的左上面的系数开始,连续扫描第一列的第一组4个系数后,然后转向扫描第二列的第一组4个系数,如此一直扫描到最后一列的第一组4个系数;然后,转向扫描第一列的第二组4个系数,一直到最后一列的第二组4个系数;按照这样的顺序依次扫描整个位平面。这里定义各列4个系数组成的数据块为一个数据编码带(stripe。图3.1给出了每个位平面的扫描方式示意图。每个位平面按照上述方式进行三次扫描,分别对应着三种编码过程:重要性传播编码过程(SignificancePropagationPass、幅度精炼编码过程(MagnitudeRefinementPass和清除编码过程(CleanupPass。这种多次位平面扫描编码方式的主要优点是可以生成最优的嵌入式码流,可以提供多个率失真截断点。在编码过程中,编码块中的每个系数对应着一个状态变量,用来表示编码过程中对应系数的状态情况,这样每个码块对应着一个状态变量平面。编码的初始化时,状态变量平面的各个状态初始化为“0”,表示相应的系数为不重要.在编码过程中,当遇到每个系数的第一个比特“1”时,该系数对应的状态变量变为“1”,表示该系数成为重要系数.编码过程中,每个位平面的各个编码系数比特对应着一个内容矢量。该内容矢量是由编码的系数比特周围的8个相邻系数比特重要性情况组成,如图3.2中系数内容窗所示。D0V0D1H0XH1D2V1D3图3.2每个系数的8个相邻位在EBCOT编码算法中的上下文环境建模模块执行对码块的每个非零位平面进行多通道编码,产生相应被编码样本的上下文环境和决策数据对。在对每个位平面的编码包含3个编码通道:重要性传播编码通道、幅度细化编码通道和清除编码通道。上下文环境建模包含4个编码原语:零编码原语、符号编码原语、幅度细化编码原语和游程编码原语。重要性传播编码通道执行零编码原语,如果被编码样本的幅度值为1,紧接着还将执行符号编码原语完成对该系数的符号编码。幅度细化编码通道执行幅度细化编码原语。清除编码通道执行零编码原语,如果被编码样本的幅度值为1,紧接着也将执行符号编码原语完成对该系数的符号编码。在清除编码通道,如果连续4个样本处在同一条带列,且4个样本的8邻域重要性贡献都为0,满足游程编码的条件时,将启动游程编码原语。游程编码结束后,将继续采用零编码原语和符号编码原语进行剩余样本的上下文环境建模,直到再次检测到游程编码的条件满足。3.3位平面解码过程在一个编码子块中每个系数有一个关联的二进制状态变量,即称为系数的重要性状态。重要性状态初始化为0,表示系数不重要,并且可能在对编码子块编码过程中变为1,表示系数重要。一个给定的当前系数的上下文矢量是一个由它的8个最近的邻点重要性状态组成的二进制矢量。在对一个当前系数的位编码时,任何处于当前系数的编码子块外面的最邻近点被认为是不重要的,即它被当作有一个值为零的重要性状态。一般地,当前一个系数可以有256种可能的上下文矢量。这些矢量根据以下的上下文信息规则被分成数目不多的几个组。这里定义了4条上下文信息规则,每条针对4种编码操作之一:重要性编码,符号编码,幅度细化编码以及清除编码。这些编码操作在每个位平面上分三个编码通道执行:重要性和符号编码位于重要性传播通道,幅度细化编码位于幅度细化通道,而清除和符号编码位于清除通道。对于一个给定的编码操作,提供给算术编码引擎的上下文标号是一个赋于当前系数的上下文的一个标号。从最高有效位开始的、不含任何重要系数(即仅含不重要比特的位平面个数在数据包头中指明。第一个带有一个非零元素的比特面只有一个清除通道。剩下的位平面在三个通道中进行编码。一个系数比特在哪一个通道中编码取决于该通道的条件。一般地,重要性传播通道包含那些被预测为、或者“极有可能”变为重要的系数,以及他们的符号。幅度细化通道包含已经成为重要系数的比特。清除通道则包含所有剩余的系数。当前系数(如图3.2的8个最邻近的系数用于产生9个上下文区域,依据是其中有多少个系数和哪些系数为重要系数。如果一个系数是重要的,则在产生上下文时赋于1,反之为0。上下文的映射也依赖于(在给定小波分解级上编码子块位于哪个子带。表3.1为这些上下文。重要性传播通道仅包含那些不重要系数(即他们的最高有效比特尚未遇到的比特,但其上下文非零。所有其他系数被跳过。上下文与比特流一起被传送到算术解码器,解码系数比特被返回。如果该比特值为1,则重要性状态被设置为1,而且紧接着的下一个被解码比特是该系数的符号比特。否则,重要性状态保持为0。当考虑连续的系数和编码通道的上下文时,系数最近的重要性状态则被使用。表3.1重要性编码通道和清除通道的上下文LLandLHsubbandHLsubbandHHsubbandContextLableiH∑iV∑iD∑iH∑iV∑iD∑(iiDV+∑iD∑2xxx2xx≥381≥1x≥11x≥12710≥101≥1026100010≥21502x20x11401x10x01300≥200≥2≥202001001101000000正负符号位解码的上下文标志使用另外一种邻点的上下文来决定。上下文标志的计算可以看作一个两步骤的处理。第一步是总结垂直和水平邻点的贡献,第二步是把这些贡献减少到5种上下文标号中的一种。在第一步,两个垂直的邻点被一起考虑。每个邻点可能有三种状态之一:重要的正数,重要的负数,或不重要。如果这两个垂直邻点都是重要的,且符号相同,或者只有一个是重要的,则垂直方向的贡献为1(符号为正或-1(符号为负。表3.2垂直(和水平方向邻点对符号上下文的贡献0V(或0H1V(或1HV(或H的贡献重要,正重要,正1重要,负重要,正0不重要重要,正1重要,正重要,负0重要,负重要,负-1不重要重要,负-1重要,正不重要1重要,负不重要-1不重要不重要如果两个垂直邻点均为不重要的,或者他们虽然都是重要的但符号相反,则垂直方向的贡献为0。水平方向的贡献也类似计算。再者,如果邻点落在编码子块的外面,则他们就被认为的不重要的。表3.2列出了这些贡献。第二步将垂直和水平贡献的9种排列减少到5种上下文标号。表3.3显示了这些上下文的标号。这些上下文随着比特流提供给算术解码器。解码器返回的比特再与表3.3中的XORbit进行逻辑异或运算,由此得到符号比特。该过程由以下等式表示:(SignbitACcontextlabelXORbit=⊕(3.1式中,Signbit是当前系数的符号位(1表示系数为负,0表示系数为正。(ACcontextlabel是在给定上下文标号和比特流时,算术解码器的返回值。当前上下文标号对应的XORbit参见表3.3。表3.3垂直和水平方向贡献产生的符号上下文水平方向贡献垂直方向贡献上下文标号XORbit11130101201-11100110000900-1101-11111-10121-1-1131幅度细化通道包含已经成为重要系数的比特,但要除去刚好在此之前的那个重要性传播通道后才被确定的重要比特。使用的上下文由水平、垂直以及对角邻点重要性状态之和决定。这些是解码器当前已知的状态,而不是在重要性解码通过之前使用的状态。而且,上下文依赖于当前是否是第一个细化比特(即紧接着重要性和符号比特。表3.4为细化通道的三种上下文区域。表3.4幅值细化的编码规则iiiHVD++∑∑∑是当前系数第一次细化上下文标号任意否16≥1是150是14所有剩余的系数是不重要的,而且他们的上下文值在重要性传播通过期间为零。这些系数的编码都在清除通道。该通道不仅使用邻点之间的上下文,例如在重要性传播通道中表3.1的上下文,而且也使用一个游程长度上下文。首先,在此通道的系数邻点的上下文由表3.1重新计算。注意到上下文标号现在可以有任何值,因为在重要性传播通道中被发现为重要的系数在清除通道被认为是重要的。游程长度被用唯一的单上下文解码。如果编码扫描时一列中的4个连续系数都在此清除通道编码,而且所有的上下文标号为0(包括前一个幅度重要性和清除通道的上下文系数,那么该唯一的游程长度上下文将与比特流一起供给算术解码器。如果符号0被返回,则该列所有4个连续系数仍然为不重要。此外,如果符号1被返回,则该列中至少有4个连续系数中的一个为重要的。接着2比特由UNIFORM上下文返回,他们注明该列中从上到下哪一个系数被首先发现是重要的。这两个用UNIFORM上下文解码的比特先是MSB,然后是LSB。该系数的符号位的确定如3.2节描述。对所有剩下的系数的解码如3.2节的方式继续。如果一列中的4个连续系数不全在清除通道中解码。注意到这里使用与重要性传播时同样的上下文(状态和模型被使用。表3.5为清除通道的逻辑。表3.5清除通道的游程长度解码器一列中4个连续系数仍然待解码,并且各系数当前上下文值为0带有游程长度上下文的符号4个待解码的连续比特为用UNIFORM上下文解码的符号待解码的系数个数是0是无无是1否跳至第一个系数符号跳至第一个系数符号跳至第一个系数符号跳至第一个系数符号MSBLSB00011011321否无任意无剩下的列如果一个编码子块的剩余行少于4行,则不使用游程长度编码。需要重申的是,任何系数的重要性状态在解码第一个“1”量值比特后立即改变。表3.6是一个例子,显示了在扫描中一个4个采样的列的量化系数的编码次序。该例子中假定没有被包括在表中的所有邻点同为0,而且指出每个比特在哪一个通道被编码子块中最早的通道总是一个清除通道,因为它可能没有被预测成重要的或细化的比特。在第一次通过后,第一个系数的解码出的“1”比特将引用起第二个系数在下一个比特面的重要性通道中编码。而在第二次清除通道中的最后一个系数的编码的“1”比特将引起第三个系数在下一个重要性通道中被编码。表3.6子位平面编码次序好重要性传播示例系数值编码通道1013-7清除1+00000重要性幅度细化清除01-01+11重要性幅度细化清除1+011重要性幅度细化清除当上下文被初始化或重新初始化时,其值设置为表3.7的值。在每一个编码通道结束时或者仅在每个编码子块结束时,上下文被重新初始化。标记COD和COC指示上下文被重新初始化的位置。表3.7所有上下文的初始状态上下文初始下标MPSUNIFORM460游程长度30全0邻点40其它所有上下文00表3.8算术编码器的终止模式示例编号通道编码运算仅在最后的通道终止编码通道在每个通道终止1清除AC(算术编码器AC,终止2重要性传播ACAC,终止2幅度细化ACAC,终止2清除ACAC,终止…………最后重要性传播ACAC,终止最后幅度细化ACAC,终止最后清除AC,终止AC,终止在正常运算时(即不是选择性算术编码通过,算术编码器必须或者终止在每个编码通道的结尾,或者仅仅终止在每个编码子块的结尾处。表3.8显示了在一个编码子块中编码通道的两个终止模式的例子。其中用到了COD或COC标记,他们指示所用的终止模式。当算术编码器提供了多重终止时,每个被终止的字段的长度在数据包头中指示。对于解码器而言,给定字节的码流将在算术编码器终止之前解码出给定次数的编码通道。在解码时,数据按字节从码流连续取出直到该编码通道的所有字节被解码使用完毕。编码通道中对应的字节数在数据包头规定。通常编码通道中有许多符号待解码。因此,解码器必须根据需要用0xFF字节把输入比特流扩展到算术编码器,直到所有符号被解码。实际添加两个以内0xFF字节就足够了。这将使得算术编码器在其输入有至少一对连续的0xFF字节,他们被解释成一个码流结束标记。比特流中实际上不含一个终止标记。然而,字节长度被显示指示,由此可以为算术编码器合成一个终止标记。3.4位平面解码器的硬件设计本节中我们将介绍BPD的基本架构,相关的实验结果将用于与本文后面提出的架构做比较。该基本架构学习了一些已有的架构[29-32]并做了一些关键修改:(1在文献[33]中提到的适应性JPEG200解码器中,BPD有正常和因果两种工作模式。(2该结构是基于改进的样本跳跃算法基础上的。(3在该结构中每个位置只需要用到两个状态位。图3.3样条s列c中每个取样位置的处理过程以及相应上下文窗口这个架构是基于条带-列处理进程的。一个条带列的上下文窗口中所有位置的状态、数据、符号位信息如图3.3所示。一个高有效的启动信号load会在每次样条-列处理进程结束时产生,以装载下一个列。假定样条s列c为当前解码列,一个高有效启动信号load将列c-1写入存储器单元。与此同时对列寄存器左移三位,将一个新列从存储器单元中写入到列c+1。如图3.4所示为基本BPD算法的VLSI实现。在每个时钟周期里,更新位单元(UpdateBit依据当前解码位置(locp、上下文类型(typec、该样条-列当前产生的上下文总数(gentcx以及判决位(dbit等信息更新样条-列c的当前数据和符号位。已更新的数据位和状态位传递到通道选择单元(flagsPGeneration产生通道选择标志flagsP。采样跳过生成单元(Sample-skippingGeneration负责处理flagsP、locp、typec和gentcx信息以产生下一组locp、typec和load信号。上下文生成单元(ContextGeneration根据上下文类型、状态位、数据和符号位产生上下文。图3.4基本BPD算法的VLSI实现采样跳过算法要求在产生样条-列最后一个上下文的同时产生load信号。但是在BPD算法中存在一些困难,因为判决位dbit只能在两个时钟周期后到达(现有算术解码器解码一个dbit通常需要2~3个时钟周期。为此在BPD算法中我们引入一种改进的采样跳过策略,即在没有更多的位置需要解码时才产生load信号。举例说明,如图3所示样条-列c处于SP通道中,假定位置A和B都已经成为重要位。由图3.5的时序图中可知,位置0的1typec在第k个时钟周期产生,在第k+1个时钟周期里BPD处于停止状态,等待AD产生dbit。假设dbit=0,在第k+2个时钟周期内BPD为位置1产生一个上下文。这个时候即便样条-列c的最后一个上下文已经产生也并不产生load信号。在下一个时钟周期里(k+3,BPD等待AD产生dbit。在第k+4个时钟周期里,仅当dbit为0时load信号被置高,否则解码继续。需要说明的是该架构是与文献8中提到的AD级联,而且假定AD只有一个解码延迟周期。01stallstall00110stallstallstall01160stallplocctypeloaddbit图3.5改进的采样跳过策略时序图通过分析位平面解码算法,我们知道BPD存在两种可能的状态:依赖(statep=1和独立(statep=0。当处于依赖的状态时,下一个上下文的产生取决于当前上下文的dbit值。如表3.9所示typec的转换方式取决于已产生的dbit值。对于1typec和3typec,下一个typec取决于dbit,当dbit=1时,他们分别转换成4typec和6typec;而当dbit=0时,对于3typec则产生load信号,对于1typec则有两种可能:如果有更多的位置需要解码时下一个typec为1typec,否则将产生load信号。当处于独立的状态时(2,4,5,6时,下一个typec与相应的dbit值无关。对于每个转换都有一个对应已知的下一状态,或者产生load信号(仅对于2typec和6typec,且当前样条-列的所有上下文都已经产生时。在基本BPD架构中,无论一个样条-列是否处于依赖状态都需要一个额外的时钟周期。为了避免这个额外的时钟周期,我们引入一种选择性采样跳过算法(SelectiveSample-Skipping。表3.9取决于解码判决位dbit的上下文类型转换方式State(PstateNextContext-typePresentContext-typedbit=0dbit=1111/load6202/load31load4405506601/load图3.6用于改进算法的4*6位寄存器在选择性采样跳过策略中,我们用一个4*6位寄存器去存储4列的状态、符号、数据位信息。如图3.6所示这些寄存器用于当前样条-列c(set0以及下一个样条-列c+1(set1的上下文窗口的状态、符号和数据的存取。我们用dp信号来表示BPD当前处于依赖状态而且可能正在处理当前样条-列的最后一个上下文(1lastcx=。dp用于当前上下文窗口set0到下一个上下文窗口set1的转换过程中,具体依据如下:(lastgencpcxtcxt===(4.2(1&dstatelastppcx===(4.3其中cpt表示在当前样条-列中出现的所有上下文总数,并且在解码过程的每个时钟周期更新。dp将被存储并用于当dbit可用时在下一个时钟周期推动上下文转变。如果dp=1,当dbit=1时BPD选择set0,否则选择set1。如果选择set1,load信号将在读入一个新列c+3时或样条-列c在当前通道中不在产生上下文时被触发。这种策略可以很有效的避免额外的时钟周期需求。在处于独立状态时(statep=0,是否改变上下文取决于当前typec(表3.9,如果当前以产生的上下文为该样条-列的最后一个上下文,则load信号将被触发以载入下一个列。图3.7基于SelectiveSample-Skipping策略的BPD结构框图如图3.7所示为基于SelectiveSample-Skipping策略的BPD结构框图,更新位单元(UpdateBit根据load值、上下文窗口的选择、typec和locp来接收dbit数据和更新样条-列c-1或者c的数据和符号位。窗口选择单元(ChooseSet根据dp和dbit值选择寄存器组中的一个窗口并更新set信号。选择性采样跳过生成单元(SelectiveSample-SkippingGeneration负责生成新的dp、typec、locp和load信号以及更新符号位、数据和状态值。将该BPD架构与文献[33]中提出的低延迟AD级联,则可以避免BPD在解码过程中处于停止等待状态。上节提到的级联方式有助于避免依赖状态下的BPD处于停止状态,与此同时AD中dbit生成路径上的延迟也会增加BPD的关键路径延迟。为了减小关键路径延迟我们引入推测处理方式(speculativeprocess,即根据dbit的两种可能值进行两种操作。如图3.8中所示为基于推测处理的BPD结构框图。图3.8基于SpeculativeProcess的BPD结构框图通过分析整个解码架构的关键路径,我们需要将推测处理一直进行到选择性采样跳过生成单元。这样的推测方式可以严格控制BPD的关键路径,使其接近于最小额外消耗下AD的关键路径。而整个块解码器的关键路径取决于BPD的模式,这点与前面提到的基于选择性采样跳过策略的结构恰恰相反。3.5实验结果分析我们采用Altera公司的CyloneII系列FPGA作为硬件实现平台,对基本架构和改进架构下的BPD的硬件消耗和性能做了分析和比较。表3.10中列举了3种架构下的硬件消耗和工作频率,其中基本架构下的BPD工作频率最高,这是因为改进算法需要为上下文窗口选择器增加额外的逻辑单元。推测模式下的BPD相对与选择性采样跳过策略的BPD在工作频率上有更多优势,这是因为它的关键路径中不包含dbit逻辑。表3.10三种结构的性能比较硬件消耗(ofLogicCells架构位平面解码器(BPD算术解码器(AD工作频率(MHz基本(Baseline654162454.6选择性跳过(Selective820196032.3推测方式(Speculative980200446.53.6小结本节中我们介绍了位平面解码器的基本原理,并采用了一种基于选择性采样跳过策略的BPD架构,该结构可以增加整个块解码器的吞吐量。然后又在上述架构基础上引入推测处理方式,这样就可以大大减小关键路径的延迟。相对于现有方法的基本BPD架构,改进的算法可以将吞吐量提高50%-100%,同时只增加25%-30%的硬件消耗。第4章MQ算术解码器研究与硬件设计4.1研究现状在JPEG2000标准的嵌入式块编码模块部分,采用了一种自适应二元算术编码算法,MQ编码器,来实现对原始数据的熵编码。在JPEG2000标准,MQ编码器用来读入位于前端的位平面编码模块产生的子块系数位样本的上下文环境标签和数据对,经过编码得到每个独立子块系数的数据压缩的码流。MQ算术编码具有很好的压缩性能,但同时其算法也要复杂很多,软件的处理速度己经远远不够,MQ算术编解码器的高速硬件实现已经成为一种必然。在基于FPGA的MQ算术解码器的VLSI实现方面,文献[34]提出了一种动态流水线结构,并使用RAM_I和ROM_Qe来实现动态的概率估计;文献[35]在解码器部分对解码算法进行了一些优化,并采用资源复用技术,将编解码器合并,大大提高了资源利用率;文献[36]中修改了基于概率估计的状态机方法,能最大幅度的消减解码器延迟。本文对MQ解码算法进行了进一步深入研究和总结,并对优化后的算法分模块实现,最后提出一种基于4级流水线的MQ算术解码器结构,该结构在利用有限资源的情况下可以大幅度提高MQ算术解码器的速度,基本能满足JPEG2000系统的要求。4.2MQ算术编解码原理20世纪60年代Elias为算术编码奠定了理论基础[37],在Elias编码中,对于具有“0”或“1”值的二进制符号序列,以各自概率值比率将当前概率区间划分成两个子区间,被分配给实际产生符号的概率值区间下限值构成代码串。即代码串按二进制符号序列的输入逐次被递归地修改下去。算术编码将一串输入码流编码成表示概率的小数,输入码流越长越复杂,概率区间划分的越细,输出也越长,大概率符号细化的较慢,小概率符号细化得较快,因此大概率符号越多,压缩效果越明显。MQ算术编码的基本操作是递归划分当前子区间。当编码器接收到了一个新的待压缩码D及对应的上下文CX,根据D将当前子区间划分成更小的2个子区间。子区间的下限值被更新,并且指向由待压缩码流所选定的新子区间的下边界,子区间的间隔值也更新为新子区间的间隔。MQ编码器用区间寄存器A来记录当前子区间的区间长度,用寄存器C来记录当前子区间的下限值。MQ编码过程的当前区间可以表示为[C,C+A]。随着编码次数的增加,这一子区间的精度会不断提高,意味着C和A的有效位数不断增加。由于实际可操作的寄存器位数是有限的,因此引入区间重归一化的概念,即当满足一定条件时,将C和A进行左移操作,同时将C寄存器不再变化的高位送入存储区。在充分考虑进位的影响后将该字节输出,这就是输出的压缩码流CD。对于MQ编码器来说,进行区间重整的条件是A<0.75,当该条件满足时,将C和A都乘以2(左移1位,直到0.75≤A<1.5。MQ解码过程与编码很类似,根据输入的压缩码流CD及对应的上下文CX判断当前码流属于大概率区间还是小概率区间,一边逐个地对二进制判决解码,同时从编码器生成的压缩数据中去掉已完成解码的代码字节。其结构图如图4.1所示。图4.1MQ算术解码器图4.2MQ算术解码器流程4.3算术解码过程图4.2为MQ编码的解码器流程。解码器的初始化由INTDEC完成。所有的CX和所需的压缩数据字节被读入DECODE。DECODE子程序解码二进制判决D,返回一个0或1的值。概率估计过程内置在DECODE中,它提供了对每个上下文概率的自适应估计。当所有上下文被读入处理后(即图中的“已完成?”判决为真时,压缩数据被解码完毕。本节的解码流程图所假设的解码器寄存器结构如表4.1。Chigh和Clow可以被认为是一个32比特的C寄存器,因为对C重新归一化将新数据的一个比特从Clow的MSB移位到Chigh的LSB。但是,解码比较只用Chigh。新数据被一次1字节地插入Clow的“b”比特处。表4.1解码器寄存器结构MSBLSB寄存器Chighxxxxxxxxxxxxxxxx寄存器Clowbbbbbbbb00000000寄存器Aaaaaaaaaaaaaaaaa对于带有填充比特的数据处理的详细描述将在本节的后面部分给出。注意到本节中假定了所示的各种过程中的比较精度大于16比特。用16比特精度可以使用逻辑比较。解码器一次解码一个二进制判决。解出该判决后,解码器从压缩数据中减去由编码器加入的任何数值。留在压缩数据中的数值是从当前区间的基到一个子区间的偏移。该子区间是分配给所有尚未被解码的二进制判决。在DECODE过程(如图4.2进行的第一次检测中,Chigh寄存器与LPS子区间的尺寸进行比较。只要不需要进行条件交换,这一检测决定是否有一个MPS或LPS被解码。如果Chigh逻辑上大于或等于存贮在CX的当前下标I的LPS概率估计值Qe,那么Chigh将被减去这一数值。如果A不小于0x8000,存贮在CX的MPS的意义被用于设置被解码的判决D。当需要一次重新归一化时,MPS/LPS的条件交换可能发生。MPS路径的条件交换过程如图4.3。只要图中第一步计算的MPS子区间尺寸A逻辑上不小于LPS的概率估计值Qe(I(CX,则出现一个MPS,判决可以从MPS(CX设置。然后,下标I(CX从表中的下一个MPS下标栏(NMPS更新。但是如果LPS子区间较大,条件交换发生,而且出现一个LPS。如果SWITCH栏为1,概率刷新切换MPS的意义,并且根据表4.2中下一个LPS下标栏(NLPS更新下标I(CX。注意到解码器中的概率估计需要与解码器中的概率估计完全相同。图4.3解码器MPS路径的条件交换过程表4.2Qe概率估值表NLPSSWITCHIndexQeNMPS00x560111110x340126020x180139030x0AC1412040x0521529050x05213833060x560176170x5401814080x4801914090x380110140100x300111170110x240112180120x1C0113200130x160129210140x560115141150x540116140160x510117150170x480118160180x380119170190x340120180200x300121190210x280122190220x240123200230x220124210240x1C0125220250x180126230260x160127240270x140128250280x120129260290x110130270300x0AC131280310x09C132290320x08A133300330x052134310340x044135320350x02A136320360x022137340370x014138350380x011139360390x008540370400x004941380410x002542390420x001543400430x000944410440x000545420450x000145430460x560146460解码器LPS路径的条件交换过程如图4.4。同样的MPS子区间A和LPS子区间Qe(I(CX的逻辑比较决定是否发生了条件交换。在图中所有两条路径上,新的子区间A被设置为Qe(I(CX。在左边和右边的路径上,分别对应条件交换发生时,对于MPS和LPS的判决和刷新处理。图4.4解码器LPS路径的条件交换过程解码器中的重新归一化过程RENORMD如图4.5。通过一个计数器跟踪寄存器C的Clow分部的压缩比特的数目。当CT为零时,一个新字节被BYTEIN过程插入Clow。所有子区间寄存器A和码字寄存器C被一次1比特移位,直到A不再小于0x8000。图4.5解码器中的重新归一化过程RENORMD调用的BYTEIN过程如图4.6。该过程读入1个字节的数据,同时补偿处理中跟在0xFF后面的任何填充比特。它也检测在编码扫描结尾处或再同步区间必须出现的标记码字。本过程中寄存器C是Chigh和Clow寄存器的级联。图中B为压缩数据缓存指针BP指向的字节。如果B不为0xFF字节。BP加1,新的B值插入到Clow的高8位比特。图4.6解码器的BYTEIN过程如果B是0xFF字节,那么B1(由BP+1指向的字节被检测。如果B1超过0x8F,则B1必须是一个标记码字。该码字被根据需要解释,而缓存指针仍然指向该标记码字的0xFF前缀。这个标记码字停止了算术压缩数据。之后,若干“1”比特被一只填充到解码器的解码结束。图中该过程由将寄存器C加0xFF00和设置比特计数器CT为8来显示。如果B1不是一个标记码字,则BP加1,指向包含一个填充比特的下一个字节。B被加到寄存器C,其字节对准的条件是使填充比特(它包含任何进位比特被加到Chigh的低位比特。INITDEC过程用于启动算术解码器。图4.7为其基本步骤。压缩数据指针BP初始化为BPST,指向压缩数据的第一个字节。压缩数据第一个字节被移入Chigh的低位字节,然后再读入一个新字节。寄存器C然后移动7位,并将CT减7,使得寄存器C与A的起始值对齐。区间寄存器A设置为与编码器中的起始值相匹配。图4.7解码器初始化解码中某些时刻,一些或者所有的算术编码统计参数被重新设置。它包括对某些或所有CX值,把I(CX和MPS(CX设置为零。在某些情况下,解码器需要保存或恢复某些I(CX和MPS(CX的值。4.4MQ解码器算法优化与硬件实现在JPEG2000中,为达到更好的压缩效果,MPS和LPS所对应的概率值是动态更新的,解码器根据当前CX查索引表I得到I和当前MPS,然后再根据查Qe表得到的NLPS、NMPS和SWITCH,在下一个时钟周期更新索引表I,以实现概率值动态更新。在硬件实现上本设计采用文献[34]提出的用RAM来实现I表,与此同时,由于Qe表是一个具有47个不同状态的状态机,本设计采用有限状态机来实现,其中索引值I为输入变量,Qe的47个状态加上一个Idle状态构成状态表。RAM_I与fsm_Qe相互配合可以在两个时钟周期内实现读取I表和读取Qe表的操作。该模块的主要功能是实现MPS或LPS解码,完成区间寄存器A和解码寄存器C的更新。标准算法中的解码区间更新分DECODE、MPS_EXCHANGE、LPSEXHCHANGE3个子流程,算法复杂,且是串行操作,效率很低;为提高处理速度,本设计对该算法流程进行了归纳总结,将该流程分成5种情况并行处理,流程图如图4.8所示。图4.8解码区间更新在解码区间更新模块完成一个D解码同时产生一个更新信号I_update给RAM_I,配合当前NLPS、NMPS和SWITCH,在下一个时钟周期更新索引表I,与此同时进行重新归一化操作。对标准算法中重新归一化进行进一步分析:每次完成一个D解码,A都有两种更新方式A=A-Qe或A=Qe;当A=A-Qe时,由于A≥0.75(0x8000,Qe的最大值是0x5601,则更新后A≥0x2901,要满足0.75≤A<1.5,则A至多需要左移2位;当A=Qe时,由于只有在A<2Qe时才会出现这种情况,又因为A≥0.75(0x8000,所以Qe≥0x4000,更新后A≥0x4000,则A至多需要左移1位;而无论当前CT为何值A至少要左移一次,总结得到重新归一化中对A的操作只有2种:左移一次或者两次。根据文献[36]所提到的前导零检测方法,只需要检测A[14]是否为零即可判断A是左移一位还是两位,具体流程图如图4.9所示。图4.9重新归一化字节读入模块在初始化和重新归一化时调用,主要功能是读入新的待解码数据。为解决不同模块之间数据处理速度不匹配的问题,本设计在字节读入模块中引入一个16*8的同步FIFO作为数据缓冲区,并在字节读入模块中设定两个8位寄存器B、B1作为缓存器,每次完成一次自己读入都会从FIFO读入一个字节更新B1,用之前的B1更新B。图4.10字节输入本文在归纳标准算法后,将BYTEIN分成3种情况[35],其中情况B=0xff&&B1>0x8f表明缓存器指针指向了终结算术解码标记符,即完成该段压缩数据CD的解码工作。具体流程图如图4.10所示。解码器在开始读入数据解码之前需要进行各个模块的初始化,主要包括RAM_I的初始化,Qe表的初始化,解码区间的初始化,字节读入的初始化,本设计中通过引入reset_I,reset_Qe控制完成前面两个的初始化,而解码区间的初始化是在字节读入初始化完成之后产生的A_init,C_init和reset_Interval控制完成的。由于位平面解码器BPD和MQ解码器并不能同步解码,通常是BPD工作时MQ解码器处于等待状态,MQ工作时BPD等待;另外,各个算术解码阶段所用的时间也不一样,也有同时处于等待状态的过程,如果有效的将这些等待时间利用起来,将大大提高解码速度。当BPD传递的CX到来时,首先读I表和Qe表,再进行MPS或LPS解码,由于此时解码数据已经得到,更新索引表I和重新归一化可以并行处理,与此同时BPD可以开始下一次解码CX,以此来实现流水操作,具体实现图如图4.11所示。update_I、图4.114级流水线MQ解码器结构4.5仿真及试验结果该设计采用VerilogHDL对MQ解码器进行了RTL级描述,采用Altera公司的CycloneII系列FPGA作为硬件平台,并在QuartusII平台下进行了设计、综合,与此同时还进一步在Modelsim平台下进行功能仿真,实验结果与软件仿真结果一致,且最高工作频率可达37.64MHz。试验结果表明,该设计可以大大提高MQ解码器的运行效率,基本可以满足JPEG2000实时解码系统的需要。功能仿真结果如图4.12所示,资源使用情况如表4.3所示。图4.12功能仿真图表4.3实验结果工作频率37.64MHz总逻辑单元数557个总组合函数551个专用逻辑寄存器123个总寄存器123个总引脚数27个总存储单元位120位4.6小结本节分析了JPEG2000标准中MQ解码器的算法流程,对其中几个流程进行了相应的算法优化,并提出了一种基于4级流水线的MQ算术解码器结构,该结构可以在平均每两个时钟周期解码一个D判决,该设计选取AlteraCycloneIIEP2C35F484C8系列FPGA进行实现,结果表明所占用的资源只有557LE,最高工作频率可以达到37.64MHz,在利用有限资源的情况下可以大幅度提高MQ算术解码器的速度,基本能满足JPEG2000系统的要求。第5章总结与展望5.1.全文总结本文主要做了以下几方面的工作:首先介绍了位平面解码器的基本原理,并采用了一种基于选择性采样跳过策略的BPD架构,该结构可以增加整个块解码器的吞吐量。然后又在上述架构基础上引入推测处理方式,这样就可以大大减小关键路径的延迟。相对于现有方法的基本BPD架构,改进的算法可以将吞吐量提高50%-100%,同时只增加25%-30%的硬件消耗。然后分析了JPEG2000标准中MQ解码器的算法流程,对其中几个流程进行了相应的算法优化,并提出了一种基于4级流水线的MQ算术解码器结构,该结构可以在平均每两个时钟周期解码一个D判决。在QuartusII开发环境下对设计进行RTL级描述,用Modelsim进行了相应的功能仿真;针对Altera系列FPGACyclo