CN104683806B - 基于深度流水的mq算术编码器高速fpga实现方法 - Google Patents
基于深度流水的mq算术编码器高速fpga实现方法 Download PDFInfo
- Publication number
- CN104683806B CN104683806B CN201510091224.2A CN201510091224A CN104683806B CN 104683806 B CN104683806 B CN 104683806B CN 201510091224 A CN201510091224 A CN 201510091224A CN 104683806 B CN104683806 B CN 104683806B
- Authority
- CN
- China
- Prior art keywords
- pipeline
- value
- output
- register
- stage pipeline
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims abstract description 26
- XLYOFNOQVPJJNP-UHFFFAOYSA-N water Substances O XLYOFNOQVPJJNP-UHFFFAOYSA-N 0.000 title abstract 2
- 238000010606 normalization Methods 0.000 claims description 3
- 238000006073 displacement reaction Methods 0.000 claims description 2
- 238000012423 maintenance Methods 0.000 claims description 2
- 238000005516 engineering process Methods 0.000 abstract description 4
- 238000004458 analytical method Methods 0.000 abstract description 3
- 238000000354 decomposition reaction Methods 0.000 abstract description 3
- 238000004519 manufacturing process Methods 0.000 abstract 3
- 230000007704 transition Effects 0.000 abstract 1
- 230000006835 compression Effects 0.000 description 6
- 238000007906 compression Methods 0.000 description 6
- 238000010586 diagram Methods 0.000 description 6
- 101000695686 Bacteroides fragilis Metallo-beta-lactamase type 2 Proteins 0.000 description 1
- 101001013272 Homo sapiens Mediator of RNA polymerase II transcription subunit 29 Proteins 0.000 description 1
- 101000727020 Kitasatospora aureofaciens Non-heme chloroperoxidase CPO-A1 Proteins 0.000 description 1
- 102100029668 Mediator of RNA polymerase II transcription subunit 29 Human genes 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
- 230000009466 transformation Effects 0.000 description 1
Landscapes
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
Abstract
基于深度流水的MQ算术编码器高速FPGA实现方法，属于计算机、数字图像处理领域，为了提高MQ编码算法执行速度，在原有四级流水线结构的基础上，通过更合理的分配工作负荷和拓展流水线，提出了一种新的基于六级流水线的块速MQ算数编码实现方式，通过合理的分配工作负荷，减少同一级流水线中必须的串行工作量；通过增加流水线级数，减少每一级流水线中的最大转型工作负荷；通过对CX表更新和算术编码间隔A更新之间的相关环的控制信号的分析，得出了通过超前预测取数技术和多索引值分析选择技术的新的三级分解的实现方式，即前三级流水线；以新的寄存器分配方式同时提高了加法速度和多路选择的速度，从而提高了MQ编码器的整体执行速度。
Description
技术领域
本发明提出了一种基于多级深度流水线的应用于FPGA系统的MQ算术编码器的高速实现方法，可以有效的提高使用FPGA实现JPEG2000中MQ编码算法时的编码速度，属于计算机、数字图像处理领域。
背景技术
JPEG2000图像压缩算法是新一代的静态图像压缩标准，它不仅有优良的压缩性能，同时支持有损压缩、无损压缩、指定区域压缩等可选择方式和很强的抗误码特性。由于具有这些优良的特性，JPEG2000算法已经应用在越来越多的领域。
虽然JPEG200O拥有上述众多的优越性,但由于JPEG2O00具有较高的算法复杂性,尤其是JPEG2000算法专用的MQ算术编码算法的控制结构和运算单元都比较复杂，且具有很强的串行性和前后相关性，从而导致JPEG2000编码算法速度很慢。
为了提高MQ算术编码的执行速度，进而提高JPEG2000编码算法的整体工作速度，现有的使用FPGA或VLSI实现MQ编码器的方案中都使用了流水线的工作形式。现在常用的流水线实现方式为四级流水线结构，该结构在论文Michael Dyer,David Taubman,SaeidNooshabadi,and Amit Kumar Gupta.Concurrency Techniques for Arithmetic Codingin JPEG2000.IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS[J].2006,53(6)中进行了详细的阐述。但是该结构对制约MQ编码器执行速度的两个前后强相关环(CX表更新和算术编码间隔A更新之间的相关环，如图1所示；编码数据输出相关环，如图2所示)的分解深度不够，导致第一级流水线中存在两级查表操作、第四级中存在18位加法和21:1多路选择器实现的移位操作，这些操作耗时较长，从而降低了MQ编码器的工作速度。
发明内容
为了提高MQ编码算法执行速度，本发明基于深度流水的MQ算术编码器高速FPGA实现方法，其包括以下步骤：
步骤1，第一级流水线中，对输入的(CX,D)数据对查表找到对应的MQ编码器概率表索引和MPS值，实现工作过程中对CX数据对查找表的更新和维护，实现多个同一CX值输入时的初步更新—查表冲突的处理；
步骤2，第二级流水线中，实现概率表索引值到概率值的查表，首先由是否连续两个或三个输入同一CX值判断概率值的索引值是选择来自第一级流水线的输入、第三级流水线的输入、上一次查表结果的NMPS或上一次查表结果的NLPS；
步骤3，第三级流水线中，根据第二级流水线输出的概率值，对当前的算术编码区间A进行重新划分，由输入数据D与MPS是否相同选择A等于A-Qe或是Qe，并执行归一化操作；
步骤4，第四级流水线中，由第三级流水线的输出结果决定输出寄存器C的值，如果是MPS状态，A<Qe则C不更新，否则C等于C+Qe；如果是LPS状态，A<Qe则C等于C+Qe，否则C不更新；
步骤5，第五级流水线中，实现对寄存器C的高位管理，依据JPEG2000协议，CH在数据的输出过程中是长度可变的，由CT对CH中的数据位数进行计数，同时由CT和来自第四级流水线的位移数确定CH的更新值和B0、B1的输出值；
步骤6，第六级流水线中，实现对JPEG2000协议中的最后输出字节B的管理，如果B等于0xff，则直接输出BOut0为B，否则BOut0为B加上来自第五级流水线的进位，同时依据第五级流水线输出的字节数，更新BOut1和B。
本发明的发明构思可以总结为：
1、通过合理的分配工作负荷，减少同一级流水线中必须的串行工作量；
2、通过增加流水线级数，减少每一级流水线中的最大转型工作负荷；
3、通过对CX表更新和算术编码间隔A更新之间的相关环的控制信号的分析，得出了通过超前预测取数技术和多索引值分析选择技术的新的三级分解的实现方式，即前三级流水线；
4、针对现有的四级流水线算法数据输出级由于具有18位加法和21:1多路选择器而导致编码速度低的问题，提出了新的寄存器分配方式同时提高了加法速度和多路选择的速度，从而提高了MQ编码器的整体执行速度。
本发明的有益效果是：本方案通过对现有MQ编码器瓶颈的分析，使用超前预测取数技术、多索引值分析选择技术和新的字节数据输出方案，增加了流水线级数，减少了每级流水线的最大执行时间，提高了MQ编码器的整体执行速度。本方案在提高执行速度的同时，保证了资源利用率没有改变，适于对性能、资源占用要求严格的FPGA实现的编码系统。
附图说明
图1CX表更新和算术编码间隔A更新之间的相关环节流程图。
图2编码数据输出相关环节流程。
图3六级流水线实现方法结构框图。
图4流水线第一级工作流程图。
图5流水线第二级工作流程图。
图6流水线第三级工作流程图。
图7流水线第四级工作流程图。
图8流水线第五级工作流程图。
图9流水线第六级工作流程图。
具体实施方式
下面结合附图对本发明做进一步详细说明。
如图3所示，本发明基于深度流水的MQ算术编码器高速FPGA实现方法，采用六级流水线MQ编码器实现方式，包括以下步骤：
步骤1，第一级流水线中，负责通过输入的(CX,D)数据对在CX表中找到对应的MQ编码器概率表索引和MPS值，并生成连续输入2次或3次同一CX值时的数据冲突控制信号。
在该级流水线中，使用分布式RAM实现CX到MQ编码器概率表索引值和MPS值的查找表；使用寄存器Cx1保存上一时钟周期时的输入CX值；使用寄存器Cx2保存一个时钟周期之前的输入CX值；使用寄存器Cx3保存两个时钟周期之前的输入CX值；使用寄存器D1保存输入数据D；使用寄存器Ni1保存查表输出的概率表索引值；使用寄存器Mps保存查表输出的MPS值；使用寄存器MpsEq保存输入数据值D与当前查表输出MPS的比较结果；使用Cx12E保存当前输入CX与Cx1中保存值的比较结果；使用Cx13E保存当前输入CX与Cx2中保存值的比较结果。
第一级流水线中，对每个输入的CX都通过查表得到对应的概率表索引值和MPS值，并把CX数据保存到Cx1、Cx2、Cx3中；当CX值等于Cx3时选择来自第三级流水线的CX表更新值作为输出保存在Ni和Mps中，CX值不等于Cx3时选择查表输出的CX表更新值作为输出保存在Ni和Mps中；把输入数据D和Mps进行逻辑与操作，结果保存在MpsEq中；保存CX与Cx1的比较结果到Cx12E；保存CX与Cx2的比较结果到Cx13E；该级流水线具体实现流程，如图4所示。
步骤2，第二级流水线实现概率表索引值到概率值的查表。
在该级流水线中，使用ROM实现概率表PET，其中保存JPEG2000标准概率值信息；使用寄存器Pb保存输出概率值；使用寄存器Ni2保存查表使用的索引值；使用寄存器Ni保存预测索引值；使用寄存器Lz保存左移位数；使用寄存器Mps2保存预测的Mps值；使用寄存器MpsMatch2保存Mps比较结果的更新值；使用寄存器MpsSelect2保存Mps值选择控制信息；使用寄存器MED保存上一时钟周期时的MpsEq值；使用寄存器MED2保存一个时钟周期之前的MpsEq值。
第二级流水线的主要工作是预测概率表查表索引值，并通过查表输出概率值和索引表的下一索引值；首先依据Cx12E和Cx13E的内容选择相应的信号值作为ME结果，再依据Cx12E、Cx13E和ME等到概率表查表索引值的选择值，并通过多路选择器选择相应的索引值进行查表得到概率值；该级流水线具体实现流程，如图5所示。
步骤3，第三级流水线实现编码区间A的计算。
在该级流水线中，使用寄存器ARN保存编码区间A归一化信号；使用寄存器CxUpdate保存用于更新第一级流水线中CX表的更新信息；使用寄存器MpsUpdate保存用于更新第一级和第二级流水线中mps信号的更新信息；使用寄存器Lz3保存左移位数；使用寄存器Pb3保存输出概率值；使用寄存器CAS保存输出选择。
首先根据当前的流水线状态，判断是使用第二级流水线的输出概率值还是使用上一次的概率值，然后使用编码区间A减去概率值来实现对当前的算术编码区间A进行重新划分，最后由输入数据D与MPS是否相同选择A等于A-Qe或是Qe，并执行归一化操作，该级流水线实现流程，如图6所示。
步骤4，第四级流水线中，由第三级流水线的输出结果决定输出寄存器C的值。
使用寄存器C输出暂存结果；使用寄存器BPC保存输出进位位；使用寄存器BPO0保存进位输出高位字节；使用寄存器BPO1保存进位输出低位字节；使用寄存器CCRA保存右对齐的输出数据；使用Lz4保存左移位数。
与MQ算法的4级流水线结构使用16位寄存器C不同，本专利结构使用19位寄存器C，因为在MQ算法中使用的是28位寄存器C，它的低16位是用来与概率值Pb相加操作长度固定，它的高9位是用来输出操作的长度可变，这样中间还有3位数据，实际上这三位数据表示的是如果处于MPS状态，算法中A<Pb时则C不更新，否则C等于C+Pb；如果是处于LPS状态，算法中A<Pb时则C等于C+Pb，否则C不更新，该级流水线实现流程，如图7所示。
步骤5，第五级流水线中，实现对寄存器C的高位CH[7:0]的管理。
使用寄存器Bc保存输出结果；使用寄存器Len保存输出长度；使用寄存器CH保存C的高位数据；使用寄存器CT保存CH中有效位的位数。
依据JPEG2000协议，CH在数据的输出过程中是长度在0～7之间可变的，由CT对CH中的数据位数进行计数，同时由CT和来自第四级流水线的位移数确定CH的更新值和Bc的输出值，使用CH中保留的位数值更新CT计数器，该级流水线实现流程，如图8所示。
步骤6，第六级流水线中，实现对JPEG2000协议中的最后输出字节B的管理。
使用寄存器B保存暂存数据；使用寄存器BOut0保存高位输出；使用寄存器BOut1保存低位输出。
如果B等于0xff，则直接输出BOut0为B，否则BOut0为B加上来自第五级流水线的进位位，同时依据第五级流水线输出的字节数，更新BOut1和B，该级流水线实现流程，如图9所示。
本发明和基于四级流水线技术的同型号FPGA实现的速率、资源比较见表1。
表1：
Claims (1)
1.基于深度流水的MQ算术编码器高速FPGA实现方法，其特征是，其包括以下步骤：
步骤1，第一级流水线中，对输入的(CX,D)数据对查表找到对应的MQ编码器概率表索引和MPS值，实现工作过程中对CX数据对查找表的更新和维护，实现多个同一CX值输入时的初步更新—查表冲突的处理；
步骤2，第二级流水线中，实现概率表索引值到概率值的查表，首先由是否连续两个或三个输入同一CX值判断概率值的索引值是选择来自第一级流水线的输入、第三级流水线的输入、上一次查表结果的NMPS或上一次查表结果的NLPS；
步骤3，第三级流水线中，根据第二级流水线输出的概率值，对当前的算术编码区间A进行重新划分，由输入数据D与MPS是否相同选择A等于A-Qe或是Qe，并执行归一化操作；
步骤4，第四级流水线中，由第三级流水线的输出结果决定输出寄存器C的值，如果是MPS状态，A<Qe则C不更新，否则C等于C+Qe；如果是LPS状态，A<Qe则C等于C+Qe，否则C不更新；
步骤5，第五级流水线中，实现对寄存器C的高位CH的管理，依据JPEG2000协议，CH在数据的输出过程中是长度可变的，由寄存器CT对寄存器C的高位CH中的数据位数进行计数，同时由寄存器CT和来自第四级流水线的位移数确定CH的更新值和寄存器Bc的输出值；
步骤6，第六级流水线中，实现对JPEG2000协议中的最后输出字节B的管理，使用寄存器B保存暂存数据；使用寄存器BOut0保存高位输出；使用寄存器BOut1保存低位输出；如果B等于0xff，则直接输出BOut0为B，否则BOut0为B加上来自第五级流水线的进位，同时依据第五级流水线输出的字节数，更新BOut1和B。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510091224.2A CN104683806B (zh) | 2015-02-28 | 2015-02-28 | 基于深度流水的mq算术编码器高速fpga实现方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510091224.2A CN104683806B (zh) | 2015-02-28 | 2015-02-28 | 基于深度流水的mq算术编码器高速fpga实现方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN104683806A CN104683806A (zh) | 2015-06-03 |
| CN104683806B true CN104683806B (zh) | 2017-12-26 |
Family
ID=53318291
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201510091224.2A Expired - Fee Related CN104683806B (zh) | 2015-02-28 | 2015-02-28 | 基于深度流水的mq算术编码器高速fpga实现方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN104683806B (zh) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108900840A (zh) * | 2018-07-10 | 2018-11-27 | 珠海亿智电子科技有限公司 | 针对硬件实现的h264宏块级码率控制方法 |
| CN110365346B (zh) | 2019-07-22 | 2021-07-06 | 浙江大华技术股份有限公司 | 一种算术熵编码方法及系统 |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1477879A (zh) * | 2003-07-03 | 2004-02-25 | 复旦大学 | 适用于jpeg2000标准的高速低功耗mq编码器 |
| CN1564196A (zh) * | 2004-04-07 | 2005-01-12 | 西安交通大学 | 同步流水算术编码器的vlsi实现方法 |
| CN101820549A (zh) * | 2010-03-19 | 2010-09-01 | 西安电子科技大学 | 基于jpeg2000标准的高速实时处理算术熵编码系统 |
| CN102088607A (zh) * | 2011-02-28 | 2011-06-08 | 西安电子科技大学 | 基于jpeg2000标准的mq编码方法和电路 |
| CN103248896A (zh) * | 2013-05-15 | 2013-08-14 | 中国科学院光电技术研究所 | Mq算术编码器 |
-
2015
- 2015-02-28 CN CN201510091224.2A patent/CN104683806B/zh not_active Expired - Fee Related
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1477879A (zh) * | 2003-07-03 | 2004-02-25 | 复旦大学 | 适用于jpeg2000标准的高速低功耗mq编码器 |
| CN1564196A (zh) * | 2004-04-07 | 2005-01-12 | 西安交通大学 | 同步流水算术编码器的vlsi实现方法 |
| CN101820549A (zh) * | 2010-03-19 | 2010-09-01 | 西安电子科技大学 | 基于jpeg2000标准的高速实时处理算术熵编码系统 |
| CN102088607A (zh) * | 2011-02-28 | 2011-06-08 | 西安电子科技大学 | 基于jpeg2000标准的mq编码方法和电路 |
| CN103248896A (zh) * | 2013-05-15 | 2013-08-14 | 中国科学院光电技术研究所 | Mq算术编码器 |
Non-Patent Citations (5)
| Title |
|---|
| A NEW PIPELINED ARCHITECTURE FOR JPEG2000 MQ-CODER;M.AHMADVAND ET.AL;《PROCEEDING OF THE WORLD CONGRESS ON ENGINEERING AND COMPUTER SCIENCE》;20121026(第2期);第1至第7页 * |
| CONCURRENCY TECHNIQUES FOR ARITHMETIC CODING IN JPEG2000;MICHAEL DYER;《IEEE TRANSACTIONS ON CIRCUITS ANS SYSTEMS》;20060630;第6卷(第53期);第1203至1212页 * |
| JEPG2000中的MQ编码模块的研究与FPGA实现;刘彬;《中国优秀硕士学位论文全文数据库》;20100415(第4期);第25页至34页 * |
| JPEG2000MQ编码器的设计与实现;雷磊;《图形、图像与多媒体》;20090817(第24期);第56至63页 * |
| JPEG2000MQ编码算法的优化和FPGA实现;何国栋等;《技术纵横》;20140901(第9期);第35至37页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN104683806A (zh) | 2015-06-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN110765709B (zh) | 一种基于fpga的基2-2快速傅里叶变换硬件设计方法 | |
| CN102681815B (zh) | 用加法器树状结构的有符号乘累加算法的方法 | |
| CN107544942A (zh) | 一种快速傅里叶变换的vlsi设计方法 | |
| CN104683806B (zh) | 基于深度流水的mq算术编码器高速fpga实现方法 | |
| CN104090737B (zh) | 一种改进型部分并行架构乘法器及其处理方法 | |
| CN110837624B (zh) | 一种针对sigmoid函数的近似计算装置 | |
| CN101478311A (zh) | bzip2压缩算法硬件加速实现方法 | |
| CN107547201B (zh) | 一种提高椭圆曲线密码体制中的标量乘计算效率的方法 | |
| CN102314215B (zh) | 集成电路系统中小数乘法器的低功耗优化方法 | |
| Molahosseini et al. | A new five-moduli set for efficient hardware implementation of the reverse converter | |
| CN103176766B (zh) | 基于增强型lut5结构的二进制加减法器 | |
| CN102724505A (zh) | Jpeg_ls游程编码fpga实现方法 | |
| CN110705196B (zh) | 一种基于随机计算的无误差加法器 | |
| Kumar et al. | Design and Implementation of Vedic Multiplier using Compressors | |
| Pathan et al. | An optimised 3× 3 shift and add multiplier on FPGA | |
| CN102156434A (zh) | 基于fpga实现的超高吞吐量md5暴力破解装置 | |
| CN104536719B (zh) | 一种用于变系数乘法器的并行伪csd编码器 | |
| Singh | Design of low area and low power modified 32-BIT square root carry select adder | |
| Paradhasaradhi et al. | An area efficient enhanced SQRT carry select adder | |
| Silviyasara et al. | Efficient architecture reverse converter design using Han Carlson structure with carry look ahead adder | |
| Siewobr et al. | Modulo Operation Free Reverse Conversion in the {2 (2n+ 1)-1, 2n, 22n-1} Moduli Set | |
| Morady et al. | A developed adding and latency reducing method for high speed pipelined adders | |
| Venkatrao et al. | Design of Area-Delay-Power Efficient Carry Select Adder Using Cadence Tool | |
| CN111597770A (zh) | 快速查找数据最高有效比特位的电路装置及查找方法 | |
| Rao et al. | An efficient carry select adder with less delay and reduced area application |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20171226 Termination date: 20200228 |