JPEG-LS游程编码硬件实现方法

摘要

JPEG-LS游程编码硬件实现方法，对JPEG-LS游程编码的标准流程进行了改进和优化，引入编码映射操作，通过比较查表操作流水线实现编码，解决原算法中多个时钟周期循环编码的问题。另外，根据只残差编码采用索引值RUNindex单周期更新操作，同时游长编码和残差编码采用索引值RUNindex双周期更新操作，提高了编码的速度。本发明方法全部通过FPGA实现，具有全流水线、实时性好的特点，可以应用于JPEG-LS无损和近无损压缩的硬件算法。

权利要求

1.JPEG-LS游程编码硬件实现方法，其特征在于步骤如下：

(1)输入前次游程编码更新后的范围在0～31之间的索引值RUNindex和游程长度RUNcnt，然后根据二者计算得到比较标志CompareFlag、映射值Map_Value和编码减值Sub_Jvalue[RUNindex]，其中，CompareFlag的计算公式如下：

编码减值Sub_Jvalue[i]的计算公式如下：

映射值Map_Value＝x0x1…xj…X30X31，j＝0～31，xj的计算公式如下：其中， J_Value[p]＝2J[p]，p＝0～31

J_Trans_RUNindex[q]＝J_Trans[q]-Sub_Jvalue[q]，q＝0～31；

J_Trans、J_Trans_RUNindex、Sub_Jvalue和J_Value均采用映射表的形式存储在FPGA内部，采用索引值RUNindex和游程长度RUNcn查表获得具体值；

(2)输入行尾标志EOLine，根据行尾标志EOLine以及步骤(1)得到的比较标志CompareFlag、映射值Map_Value计算出更新后的索引值RUNindex，计算时采用两级更新，其中一级更新完成RUNindex的累加运算，一级更新后RUNindex的值为映射值Map_Value中1的个数，二级更新完成RUNindex保持不变或者RUNindex的值减1运算；当比较标志CompareFlag为0时，只进行二级更新操作，当比较标志CompareFlag为1时，先进行一级更新，而后进行二级更新，当输入行尾标志EOLine为1时，二级更新操作 为保持RUNindex不变，当输入行尾标志EOLine为0时，二级更新操作为RUNindex的值减1运算；一级更新采用寄存器、查找表实现，二级更新采用加法器、多路选择器和寄存器实现，每级更新执行各自占用一个时钟周期；

(3) 根据游程长度RUNcnt，步骤(1)得到的映射值Map_Value、编码减值Sub_Jvalue[RUNindex]以及初始索引值RUNindex计算出游长编码和残差编码，其中游长编码为映射值Map_Value中由全部1组成的码段，残差编码为J[k+1]比特的y，计算公式为y＝RUNcnt-J_Trans[k]+Sub_Value[RUNindex]，其中k应同时满足以下两个关系式，RUNcnt≥J_Trans_RUNindex[k]且RUNcnt＜J_Trans_RUNindex[k+1]；J[k+1]、J[i]、J[p]均通过查询J表获得，J表即J[0..31]＝{0，0，0，0，1，1，1，1，2，2，2，2，3，3，3，3，4，4，5，5，

6，6，7，7，8，9，10，11，12，13，14，15}；

(4) 将步骤(3)得到的游长编码、残差编码和行尾编码’1’、分隔编码’0’按照8种不同情况完成编码合成，输出合成后的编码值和编码长度并等待下一次编码开始；所述的8种情况如下表所示，上表中当残差编码值大于零时残差标志为1，当残差编码值不大于零时残差标志为0，&为连接符号，游长编码值用V1表示，游长编码长度用L1表示，残差编码值用V2表示，残差编码长度用L2表示，游程编码值用V表示，游程编码长度用L表示。

说明书

JPEG-LS游程编码硬件实现方法

技术领域

[0001] 本发明属于图像处理领域，涉及一种基于FPGA实现JPEG-LS游程编码的方法。

背景技术

[0002] JPEG-LS(Information Technology-Lossless/near-losslesscompressionstandard for continuous-tone still images)算法 是联 合图 像 专家 组(Joint
Photographic Experts Group)制定的一种图像压缩标准，相比于其它的压缩算法，
JPEG-LS在无损和近无损压缩领域具有更高的压缩性能，在医疗、遥感图像通信等对恢复
图像质量要求高的领域有着广泛的应用。JPEG-LS标准算法采用两种模式对像素进行编
码-游程模式和常规模式，常规模式对预测残差进行Golomb编码，而游程模式对游程长
度进行编码，用来压缩图像的平坦区域，从而对平滑图像可以进行大倍率的压缩，因此对
JPEG-LS压缩比提高起着至关重要的作用。

[0003] JPEG-LS游程编码的输入是游程长度RUNcnt和行尾标志EOLine，游程编码需要使用J表和RUNindex索引，J表即J[0..31]＝{0，0，0，0，1，1，1，1，2，2，2，2，3，3，3，3，4，4，5，
5，6，6，7，7，8，9，10，11，12，13，14，15}，RUNindex索引初始值为0，范围为0～31，编码过程中RUNindex索引不断计算更新，并且通过RUNindex索引查找J表相应值。

[0004] 游程编码按照下面的流程执行：

[0005] a、当RUNcnt≥2J[RUNIndex]时执行

[0006] I输出比特‘1’

[0007] II RUNcnt＝RUNcnt-2J[RUNIndex]

[0008] III当RUNindex＜31，RUNindex＝RUNindex+1

[0009] 该步骤的编码结果定义为游长编码。

[0010] b、当到达行尾，即EOLine＝＝1时执行

[0011] I当RUNcnt＞0，输出比特‘1’

[0012] II跳出游程编码

[0013] 该步骤的编码结果定义为行尾编码。

[0014] c、输出比特‘0’，该步骤的编码结果定义为分隔编码。

[0015] d、输出J[RUNindex]比特RUNcnt二进制数(MSB开始)，

[0016] 该步骤的编码结果定义为残差编码。

[0017] e、当RUNindex＞0，RUNindex减1。

[0018] 然后，跳出游程编码。

[0019] 上述流程如附图1所示，为JPEG-LS标准算法采用的游程编码方法。从中可以看出，游程编码的判断分支较多，码字分多次追加输出并且下一次编码用到前一次更新后的
J[RUNIndex]
RUNindex值，这些都不利于FPGA硬件实现。在a步骤中，需要不断判断RUNcnt≥2 ，
循环次数不确定，造成设计复杂，资源占用较多，难于流水实现。另外，RUNindex每次编码完更新，给下一次游程编码使用，这相当于在硬件上实现数据环路。再者，d步骤的码字与a步骤后残差RUNcnt和更新后的RUNindex相关，也就是输出的码字可变，这也给硬件设计
带来了困难。

[0020] 国内外关于FPGA实现JPEG-LS的非专利文献较多，但都没有涉及游程编码的具体实现。例如，清华大学学报(自然科学版)2007年第47卷第10期，《低功耗全流水线JPEG-LS无损图像编码器的VLSI设计》一文提出了一种多时钟域全流水线设计实现JPEG-LS，文中
对Golomb编码的设计做了详细介绍，并且介绍了中断编码、游程编码和常规编码的三种码
字合成，但是并未对游程编码的设计作叙述。弹道与制导学报2006年第26卷第2期，《基
于FPGA的JPEG-LS无损压缩算法的实现》一文提出的编码器具有处理高分辨率图像的能
力，但是系统的数据吞吐率约为64Mbps，也就是相当于像元时钟为8Mhz(以图像位深度为
8bit计算)，并且也没有提到游程编码的实现过程。

[0021] 专利申请号为CN200710141738.X，名称为《用于医学图像的基于快速JPEG-LS的压缩方法》的中国专利公开了一种图像数据压缩和重建技术优化方法，优化可以被应用于
基于JPEG-LS的算法以使处理加速约50％，同时保持误差可控性和压缩比。但是，该专利中也未涉及游程编码的FPGA硬件实现的内容。

发明内容

[0022] 本发明的技术解决问题是：克服现有技术的不足，提供了一种处理速度高、实时性好、便于流水设计的JPEG-LS游程编码硬件实现方法。

[0023] 本发明的技术解决方案是：JPEG-LS游程编码硬件实现方法，步骤如下：

[0024] (1)输入前次游程编码更新后的范围在0～31之间的索引值RUNindex和游程长度RUNcnt，然后根据二者计算得到比较标志CompareFlag、映射值Map_Value和编码减值
Sub_Jvalue[RUNindex]，

[0025] 其中，CompareFlag的计算公式如下：

[0026]

[0027] 编码减值Sub_Jvalue[i]的计算公式如下：

[0028]

[0029] 映射值Map_Value＝x0x1...xj...x30x31，j＝0～31，xj的计算公式如下：

[0030]

[0031] 其中， J_Value[p]＝2J[p]，p＝0～31

[0032] J_Trans_RUNindex[q]＝J_Trans[q]-Sub_Jvalue[q]，q＝0～31；

[0033] J_Trans、J_Trans_RUNindex、Sub_Jvalue和J_Value均采用映射表的形式存储在FPGA内部，采用索引值RUNindex和游程长度RUNcn查表获得具体值；

[0034] (2)输入行尾标志EOLine，根据行尾标志EOLine以及步骤(1)得到的比较标志CompareFlag、映射值Map_Value计算出更新后的索引值RUNindex，计算时采用两级更新，
其中一级更新完成RUNindex的累加运算，一级更新后RUNindex的值为映射值Map_Value
中1的个数，二级更新完成RUNindex保持不变或者RUNindex的值减1运算；当比较标志
CompareFlag为0时，只进行二级更新操作，当比较标志CompareFlag为1时，先进行一级更
新，而后进行二级更新，当输入行尾标志EOLine为1时，二级更新操作为保持RUNindex不
变，当输入行尾标志EOLine为0时，二级更新操作为RUNindex的值减1运算；一级更新采
用寄存器、查找表实现，二级更新采用加法器、多路选择器和寄存器实现，每级更新执行各自占用一个时钟周期；

[0035] (3)根据游程长度RUNcnt，步骤(1)得到的映射值Map_Value、编码减值Sub_Jvalue[RUNindex]以及初始索引值RUNindex计算出游长编码和残差编码，其中游长编
码为映射值Map_Value中由全部1组成的码段，残差编码为J[k+1]比特的y，计算公式
为y＝RUNcnt-J_Trans[k]+Sub_Value[RUNindex]，其中k应同时满足以下两个关系式，
RUNcnt≥J_Trans_RUNindex[k]且RUNcnt＜J_Trans_RUNindex[k+1]；

[0036] (4)将步骤(3)得到的游长编码、残差编码和行尾编码’1’、分隔编码’0’按照8种不同情况完成编码合成，输出合成后的编码值和编码长度并等待下一次编码开始；所述的8种情况如下表所示，

[0037]

[0038] 上表中当残差编码值大于零时残差标志为1，当残差编码值不大于零时残差标志为0，&为连接符号，游程编码值用V1表示，游程编码长度用L1表示，残差编码值用V2表
示，残差编码长度用L2表示，游程编码值用V表示，游程编码长度用L表示。

[0039] 本发明与现有技术相比的优点在于：

[0040] (1)本发明JPEG-LS游程编码硬件实现方法可以全部采用FPGA实现，具有全流水线、实时性好的特点；

[0041] (2)本发明方法通过引入编码映射操作，解决了原标准算法中多个时钟周期循环编码的问题，具体方法是预先计算生成四个表，存储在FPGA内部的查找表和块存储器中，
通过比较查表得到编码需要的映射值、比较标志和编码减值，这样可以零周期实现循环编
码操作；

[0042] (3)本发明方法，根据只游长编码采用索引值RUNindex单周期更新操作，同时游长编码和残差编码采用索引值RUNindex双周期更新操作。该RUNindex更新和编码映射构
成数据环路，通过编码映射引入四个映射表和RUNindex更新引入单双周期，解决了游程编
码中数据环路的路径过长瓶颈问题，使得更新后的RUNindex可以提供给下一次游程编码，
能使游程编码全流水实现；

[0043] (4)本发明方法预先计算出游长编码和残差编码所有可能的结果，存储在FPGA内部的查找表和块存储器中，通过比较映射值查表可以得到相应的结果。该步骤的查表可以
单周期完成，流水线实现；

[0044] (5)本发明方法提出的编码输出由固定位宽的编码值和编码长度组成的格式，相对于不固定位宽的编码输出，在编码合成时易于操作，实现简单，可移植性好。

附图说明

[0045] 图1为采用JPEG-LS标准算法进行游程编码的流程图；

[0046] 图2为采用本发明方法进行游程编码的流程图；

[0047] 图3为本发明映射产生步骤的流程图；

[0048] 图4为本发明RUNindex更新步骤的流程图。

具体实施方式

[0049] 如图2所示，为本发明方法的流程框图，主要包括四个步骤，即映射产生、RUNindex更新、码字产生和码字合成。下面分别介绍四个步骤：

[0050] 1)映射产生

[0051] 映射产生步骤所需要的输入为索引值RUNindex和游程长度RUNcnt，然后根据二者计算得到比较标志CompareFlag、映射值Map_Value和编码减值Sub_Jvalue[RUNindex]。
映射产生的流程如图3所示，主要包含四个映射表：J_Trans、J_Trans_RUNindex、Sub_
Jvalue和J_Value。

[0052] J_Trans表由J表得到，公式为 其中n＝0～31，即J_Trans[0..31] ＝ {1，2，3，4，6，8，10，12，16，20，24，28，36，44，52，60，76，92，124，156，220，
284，412，540，796，1308，2332，4380，8476，16668，33052，65820}。

[0053] 上面是RUNindex初始值为0的J_Trans表，对于初始值不为0的RUNindex，J_Trans表 更 新 为 J_Trans_RUNindex表，J_Trans_RUNindex[q] ＝ J_Trans[q]-Sub_
Jvalue[q]，Sub_Jvalue表由J_Trans表得到，Sub_Jvalue[q]的取值在硬件上通过q查
Sub_Jvalue表得到，表示为公式如下：

[0054]

[0055] 通过RUNcnt和J_Trans_RUNindex[0..31]一一做比较，即采用RUNcnt和J_Trans_RUNindex[0]比较得到x0、和J_Trans_RUNindex[1]比较得到x1，...，和J_Trans_
RUNindex[j]比较得到xj，...，和J_Trans_RUNindex[30]比较得到x30，和J_Trans_
RUNindex[31]比较得到x31，然后拼接x0，x1，...，xj，...，x30.x31得到映射值Map_Value，拼接公式为Map_Value＝x0x1...xj...x30x31，j＝0～31，xj的计算公式如下：

[0056]

[0057] 映射值Map_Value中包含的1的个数即为标准算法中a步骤II执行次数。J[p]

[0058] 另外，J_Value 表的 产 生 公式 J_Value[p]＝2 (p＝0 ～31)，可得 J_Value[0..31] ＝ {1，1，1，1，2，2，2，2，4，4，4，4，8，8，8，8，16，16，32，32，64，64，128，128，
256，512，1024，2048，4096，8192，16384，32764}，通 过 输 入 RUNindex查 表 J_Value得到J_Value[RUNindex]，然后采用RUNcnt和J_Value[RUNindex]比较得到比较标志
CompareFlag，CompareFlag的公式如下：

[0059]

[0060] 比较标志CompareFlag为0时，只进行残差编码(标准算法d步骤)，比较标志CompareFlag为1时，既进行游长编码(标准算法a步骤)，又产生残差编码(标准算法d
步骤)。

[0061] 上述两个比较过程均采用来硬件来实现，如图3所示，编码映射步骤由J_Trans表、J_Trans_RUNindex表、Sub_Jvalue表、J_Value表和33个比较器组成。

[0062] 第 一，上 次 游 程 编 码 更 新 后 的RUNindex 查 表Sub_Jvalue得 到 Sub_Jvalue[RUNindex]；

[0063] 第二，J_Trans表减去Sub_Jvalue[RUNindex]得到J_Trans_RUNindex表，输入的RUNcnt和J_Trans_RUNindex表的值通过32个比较器一一比较得到映射值Map_Value；

[0064] 第三，上次游程编码更新后的RUNindex查表J_Value得到J_Value[RUNindex]，输入的RUNcnt和J_Value[RUNindex]通过比较器比较得到比较标志CompareFlag。

[0065] 该步骤的第一和第三在硬件上同时执行，由于都是查表比较操作，可以零周期实现编码映射。

[0066] 该步骤将原算法a步骤循环不确定的问题，预先计算映射生成四个表，存储在FPGA内部的查找表和块存储器中，采用索引值RUNindex和游程长度RUNcnt的一系列查表
比较得到比较标志CompareFlag、映射值Map_Value和编码减值Sub_Jvalue[RUNindex]，提
供给下面的步骤完成RUNindex更新和码字产生。

[0067] 上面操作的原理如下：

[0068] 假设RUNcnt＝r，EOLine＝0，RUNindex＝s(0≤s≤31)，分两种情况考虑：

[0069] (1)RUNcnt≥2J[RUNIndex]情况

[0070] 该种情况下，既产生游长编码(标准算法a步骤)，又产生残差编码(标准算法d步骤)。

[0071] 按 照 标 准 算 法 a 步 骤，RUNcnt 可 以 展 开 为 下 式，RUNcnt ＝J[s] J[s+1] J[k] J[k+1]
2 +2 +...+2 +y(k≥s，y为残差且y＜2 )。下面以1≤s≤31的情况进行讨
论(s＝0的情况，定义Sub_Jvalue[0]＝0，计算方法和结果与1≤s≤31的情况一致)

[0072] 定义，J[0]

[0073] J_Trans[0]＝2J[0] J[s-1]

[0074] J_Trans[s-1]＝2 +...+2

[0075] J_Trans[s]＝2J[0]+...+2J[s-1]+2J[s]

[0076] J_Trans[k]＝2J[0]+...+2J[s-1]+2J[s]+...+2J[k]

[0077] J_Trans[k+1]＝2J[0]+...+2J[s-1]+2J[s]+...+2J[k+1]

[0078] J_Trans[31]＝2J[0]+...+2J[s-1]+2J[s]+...+2J[31]

[0079] 以上各式分别减Sub_Jvalue[s]＝2J[0]+2J[1]+...+2J[s-1]得，

[0080] J_Trans_RUNindex[0]＝-(2J[1]+...+2J[s-1])

[0081] J_Trans_RUNindex[s-1]＝0

[0082] J_Trans_RUNindex[s]＝2J[s]

[0083] J_Trans_RUNindex[k]＝2J[s]+...+2J[k]

[0084] J_Trans_RUNindex[k+1]＝2J[s]+...+2J[k+1]

[0085] J_Trans_RUNindex[31]＝2J[s]+...+2J[31]

[0086] 采用RUNcnt＝2J[s]+2J[s+1]+...+2J[k]+y(k≥s，y为残差)与上式做一一比较得，[0087] x0＝RUNcnt≥J_Trans_RUNindex[0]＝1

[0088] xs-1＝RUNcnt≥J_Trans_RUNindex[s-1]＝1

[0089] xs＝RUNcnt≥J_Trans_RUNindex[s]＝1

[0090] xk＝RUNcnt≥J_Trans_RUNindex[k]＝1

[0091] xk+1＝RUNcnt≥J_Trans_RUNindex[k+1]＝0

[0092] x31＝RUNcnt≥J_Trans_RUNindex[31]＝0

[0093] 拼接x0、x1、......x31得到Map_Value＝x0x1...x30x31。

[0094] (2)RUNcnt＜2J[RUNIndex]情况

[0095] 该种情况下，不执行标准算法的a步骤，所以无游长编码，a步骤后RUNindex值保持不变，还是s。

[0096] 残差编码可以表示为J[RUNindex]比特的RUNcnt，即J[s]比特的r。

[0097] 2)RUNindex更新

[0098] 该步骤所需要的输入为索引值RUNindex、比较标志CompareFlag和映射值Map_Value，通过单双周期更新操作得到更新后的RUNindex，更新后的RUNindex提供给下一次
游程编码使用。

[0099] 在标准游程编码流程中，有两个环节完成RUNindex的更新，即背景技术中提及的a步骤和e步骤。由于RUNindex更新步骤与映射产生步骤构成数据环路，为了保证流水
实现和满足速度要求，RUNindex分为两级更新，每级更新都插入一级寄存器。一级更新完
成a步骤的RUNindex累加运算，采用查找表实现，通过输入的映射值Map_Value可以查表
1得到更新后的RUNindex；二级更新完成原算法b步骤RUNindex不变操作，硬件上为直通
或者e步骤的RUNindex减1运算。当输入行尾标志EOLine为1时，二级更新操作为保持
RUNindex不变，当输入行尾标志EOLine为0时，二级更新操作为RUNindex的值减1运算。

[0100] 表1RUNindex一级更新结果表

[0101]序号 4字节映射值Map_Value(十六进制) 索引值RUNindex一级更新后结果(十进制)
1 Ox00_00_00_00 0
2 Ox80_00_00_00 1
3 Oxc0_00_00_00 2
4 Oxe0_00_00_00 3
5 Oxf0_00_00_00 4
6 Oxf8_00_00_00 5
7 Oxfc_00_00_00 6
8 Oxfe_00_00_00 7
9 Oxff_00_00_00 8
10 Oxff_80_00_00 9
11 Oxff_c0_00_00 10
12 Oxff_e0_00_00 11
13 Oxff_f0_00_00 12
14 Oxff_f8_00_00 13
15 Oxff_fc_00_00 14
16 Oxff_fe_00_00 15
17 Oxff_ff_00_00 16
18 Oxff_ff_80_00 17
19 Oxff_ff_c0_00 18
20 Oxff_ff_e0_00 19
21 Oxff_ff_f0_00 20
22 Oxff_ff_f8_00 21
23 Oxff_ff_fc_00 22
24 Oxff_ ff_fe_00 23
25 Oxff_ff_ff_00 24
26 Oxff_ff_ff_80 25
27 Oxff_ff_ff_c0 26
28 Oxff_ff_ff_e0 27
29 Oxff_ff_ff_f0 28
30 Oxff_ff_ff_f8 29
31 Oxff_ff_ff_fc 30
32 Oxff_ff_ff_fe 31
33 Oxff_ff_ff_ff 31

[0102] 根据映射产生步骤中的原理推导可知，Runlndex更新后的值为(k+1)，Map_Value和k+1一一对应可以得到表1，表1中4字节映射值Map_Value中1的个数为标准算法中a
步骤II执行的次数，每增加一个1，说明Runlndex的值就加1。例外情况是Map_VAlue＝
0xff_ff_ff_ff，若按照上述规律Runlndex的值应为32，而按照标准算法Runlndex的最大
值为31，因此已在表1中做了修正。

[0103] 比较标志CompareFlag为0或者1是RUNindex单双周期的选择信号，RUNindex更新的流程如图4所示，一级更新采用寄存器和查找表组成，二级更新采用加法器、多路选择器和寄存器组成，两级更新之间的多路选择器用来选择执行只执行二级更新还是同时一二
级更新，具体硬件实现描述如下。

[0104] 当RUNcnt初始值小于2J[RUNIndex]，比较标志CompareFlag为0，不执行一级更新，即不执行a步骤，只执行RUNindex二级更新。在图4中，CompareFlag为0，多路选择器MUX执行0分支，也就是输出的RUNindex经多路选择器MUX的0分支执行RUNindex二级更新，
二级更新按照下面的公式：

[0105]

[0106] 整个RUNindex更新步骤需要一个时钟周期(单周期)运算，能保证流水线实现，可以提供给下一个游程编码更新后的RUNindex值，符合JPEG-LS算法要求。

[0107] 当RUNcnt初始值大于等于2J[RUNIndex]，比较标志CompareFlag为1，同时执行一级更新和二级更新，也就是执行a步骤和e步骤。在图4中，CompareFlag为1，多路选择器MUX执行1分支，也就是输入的RUNindex首先经一级更新查表运算，继续执行RUNindex二级更
新，然后输出更新后的RUNindex。整个RUNindex更新步骤包含两个寄存器需要两个时钟周
期(双周期)运算，也满足JPEG-LS算法要求。

[0108] 3)码字产生

[0109] 码字产生步骤所需要的输入为初始RUNindex、游程长度RUNcnt、映射值Map_Value和编码减值Sub_Jvalue[RUNindex]，查表2生成游长码字和残差码字，并给出残差标
志Leaving_Flag，传递给下一级码字合成步骤完成合成操作。

[0110] 表2游程编码映射表

[0111]4字节比较标志
序 游长编码值 游长编码长度 残差编码值 残差编码长度
Map_Value
号 (十六进制) (十进制) (十六进制) (十进制)
(十六进制)
1 Ox00_00_00_00 Ox0 0 Ox0 0
2 Ox80_00_00_00 Ox1 1-RUNindex Ox0 0
3 Oxc0_00_00_00 Ox3 2-RUNindex Ox0 0
4 Oxe0_00_00_00 Ox7 3-RUNindex Ox0 0
RUNcnt-4+Sub_Jv
5 Oxf0_00_00_00 Oxf 4-RUNindex 1
alue[RUNindex]
RUNcnt-6+
6 Oxf8_00_00_00 Ox1f 5-RUNindex Sub_Jvalue[RUNin 1
dex]
RUNcnt-8+
7 Oxfc_00_00_00 Ox3f 6-RUNindex Sub_Jvalue[RUNin 1
dex]
RUNcnt-10+
8 Oxfe_00_00_00 Ox7f 7-RUNindex Sub_Jvalue[RUNin 1
dex]
RUNcnt-12+
9 Oxff_00_00_00 Oxff 8-RUNindex Sub_Jvalue[RUNin 2
dex]
RUNcnt-16+
10 Oxff_80_00_00 Ox1_ff 9-RUNindex Sub_Jvalue[RUNin 2
dex]
RUNcnt-20+Sub_J
11 Oxff_c0_00_00 Ox3_ff 10-RUNindex 2
value[RUNindex]
RUNcnt-24+Sub_J
12 Oxff_e0_00_00 Ox7_ff 11-RUNindex 2
value[RUNindex]
RUNcnt-28+Sub_J
13 Oxff_f0_00_00 Oxf_ff 12-RUNindex 3
value[RUNindex]
RUNcnt-36+Sub_J
14 Oxff_f8_00_00 Ox1f_ff 13-RUNindex 3
value[RUNindex]
RUNcnt-44+Sub_J
15 Oxff_fc_00_00 Ox3f_ff 14-RUNindex 3
value[RUNindex]
RUNcnt-52+Sub_J
16 Oxff_fe_00_00 Ox7f_ff 15-RUNindex 3
value[RUNindex]
RUNcnt-60+Sub-J
17 Oxff_ff_00_00 Oxff_ff 16-RUNindex 4
value[RUNindex]
RUNcnt-76+Sub_J
18 Oxff_ff_80_00 Ox1_ff_ff 17-RUNindex 4
value[RUNindex]
RUNcnt-92+Sub_J
19 Oxff_ff_c0_00 Ox3_ff_ff 18-RUNindex 5
value[RUNindex]
RUNcnt-124+Sub_
20 Oxff_ff_e0_00 Ox7_ff_ff 19-RUNindex 5
Jvalue[RUNindex]
RUNcnt-156+Sub_
21 Oxff_ff_f0_00 Oxf_ff_ff 20-RUNindex 6
Jvalue[RUNindex]
RUNcnt-220+Sub_
22 Oxff_ff_f8_00 Ox1f_ff_ff 21-RUNindex 6
Jvalue[RUNindex]
RUNcnt-284+Sub_
23 Oxff_ff_fc_00 Ox3f_ff_ff 22-RUNindex 7
Jvalue[RUNindex]
RUNcnt-412+Sub_
24 Oxff_ff_fe_00 Ox7f_ff_ff 23-RUNindex 7
Jvalue[RUNindex]
RUNcnt-540+Sub_
25 Oxff_ff_ff_00 Oxff_ff_ff 24-RUNindex 8
Jvalue[RUNindex]
RUNcnt-796+Sub_
26 Oxff_ff_ff_80 Ox1_ff_ff_ff 25-RUNindex 9
Jvalue[RUNindex]
RUNcnt-1308+Sub
27 Oxff_ff_ff_c0 Ox3_ff_ff_ff 26-RUNindex 10
_Jvalue[RUNindex]
RUNcnt-2332+Sub
28 Oxff_ff_ff_e0 Ox7_ff_ff_ff 27-RUNindex 11
_Jvalue[RUNindex]
RUNcnt-4380+Sub
29 Oxff_ff_ff_f0 Oxf_ff_ff_ff 28-RUNindex 12
_Jvalue[RUNindex]
30 Oxff_ff_ff_f8 Ox1f_ff_ff_ff 29-RUNindex RUNcnt-8476+Sub 13
_Jvalue[RUNindex]
RUNcnt-16668+Su
31 Oxff_ff_ff_fc Ox3f_ff_ff_ff 30-RUNindex b_Jvalue[RUNindex 14
]
RUNcnt-33052+Su
32 Oxff_ff_ff_fe Ox7f_ff_ff_ff 31-RUNindex b_Jvalue[RUNindex 15
]
RUNcnt-65820+Su
33 Oxff_ff_ff_ff Oxff_ff_ff_ff 32-RUNindex b_Jvalue[RUNindex 15
]

[0112] 根据映射产生步骤中的原理推导可知，游长编码输出(k+1-s)个’1’，这样可以得到表2中Map_Value和游长编码值、游长编码长度的对应关系。表2中游长编码值所在列为游长编码的结果，游长编码长度为(k+1-s)。残差编码值的计算方式如下面的推导过程所示。

[0113] 残差编码计算对RUNcnt＝2J[s]+2J[s+1]+...+2J[k]+y左右两边加2J[0]+...+2J[s-1]得[0114] 2J[0]+...+2J[s-1]+RUNcnt＝2J[0]+...+2J[s-1]+2J[s]+2J[s+1]+...+2J[k]+y

[0115] Zs-1+RUNcnt＝Zk+y

[0116] y＝RUNcnt-Zk+Zs-1

[0117] 由于

[0118]

[0119] Sub_Jvalue[RUNindex]＝J_Trans[RUNindex-1]

[0120] y＝RUNcnt-J_Trans[k]+J_Trans[s-1]

[0121] 可得＝r-J_Trans[k]+J_Trans[s-1]

[0122] ＝r-J_Trans[k]+Sub_Value[s]

[0123] 这样残差编码输出J(k+1)比特的y，可以得到表2的Map_Value和残差编码值、残差编码长度的对应关系。例外情况是Map_Value＝0xff_ff_ff_ff，按照标准算法15比特
的y，已在表中做了修正。

[0124] 本发明中，游长码字由游长编码值和游长编码长度组成这样可以唯一确定码字，并且游长编码值采用4字节二进制数(最多32位“1”)表示，游长编码长度采用6位二进
制数(最大值32)表示，这样使用统一固定数据宽度的表达形式，相对于不定长数据宽度形
式易于硬件编码合成的操作。同理，残差码字由残差编码值和残差编码长度组成，残差编码
15
值采用2字节二进制数(最大值为2 -1＝32767，至少采用15位二进制数表示)表示，残
差编码长度采用4位二进制数(最大值15)表示。

[0125] 由于原算法b步骤I分步中输出比特‘1’的前提条件之一是残差大于0，所以定义残差标志Leaving_Flag给码字合成步骤使用。通过判断残差编码值是否大于零，得到残差
标志Leaving_Flag。当残差编码值大于零，残差标志Leaving_Flag为1；当残差编码值不
大于零，残差标志Leaving_Flag为0。

[0126] 4)码字合成

[0127] 码字合成步骤需要的输入为行尾标志EOLine、比较标志CompareFlag、残差标志Leaving_Flag、游长编码值、游长编码长度、残差编码值、残差编码长度，通过将各码字合成生成最终的编码值和编码长度。

[0128] 经过分析原算法中三个码字产生条件比较标志CompareFlag、残差标志Leaving_Flag和行尾标志EOLine，对各种出现的码字合成方式进行归类共有8种合成方式。同样，
通过比较标志、残差标志和行尾标志决定执行某一种合成方式，详细设计见下面编码连接
真值表。

[0129] 表3编码连接真值表

[0130]

[0131] 表格中&为连接符号，即‘1’&‘0’的连接结果为二进制数“10”。

[0132] 游程编码值用V1表示，游程编码长度用L1表示。

[0133] 残差编码值用V2表示，残差编码长度用L2表示。

[0134] 游程编码值用V表示，游程编码长度用L表示。

[0135] 该步骤在硬件上采用多路选择器、加法器和寄存器实现，通过某一方式的编码合成完成最终的编码值和编码长度输出，然后跳转到映射产生步骤，等待下一次编码开始。

[0136] 实施例

[0137] 以两次编码RUNcnt＝5，且EOLine为0为例说明。

[0138] (一)采用标准算法

[0139] ●第一次编码RUNcnt＝5，EOLine＝0

[0140] ■a步骤

[0141] 此时RUNindex＝0，即2J[RUNIndex]＝2J[0]＝20＝1

[0142] 按照编码流程，RUNcnt≥2J[RUNIndex]即5≥1，输出比特’1’；同时RUNcnt＝J[RUNIndex]
RUNcnt-2 ＝4；RUNindex加1变为1。

[0143] 由于RUNcnt≥2J[RUNIndex]即4≥1，继续执行a步骤，输出比特’1’；同时RUNcnt＝J[RUNIndex]RUNcnt-2 ＝3；RUNindex加1变为2。

[0144] 由于RUNcnt≥2J[RUNIndex]即3≥1，继续执行a步骤，输出比特’1’；同时RUNcnt＝J[RUNIndex]RUNcnt-2 ＝2；RUNindex加1变为3。

[0145] 由于RUNcnt≥2J[RUNIndex]即2≥1，继续执行a步骤，输出比特’1’；同时RUNcnt＝J[RUNIndex]RUNcnt-2 ＝1；RUNindex加1变为4。

[0146] 由于RUNcnt≥2J[RUNIndex]即1≥2不成立，跳出a步骤。

[0147] 这样a步骤循环执行了四次，输出码字为“1111”，RUNindex值为4。

[0148] ■b步骤

[0149] 由于EOLine为0，不执行直接跳出b步骤。

[0150] 此时的码字为“1111”，RUNindex值为4。

[0151] ■c步骤

[0152] 输出比特’0’，跳出c步骤。

[0153] 此时的码字为“11110”，RUNindex值为4。

[0154] ■d步骤

[0155] 输出J[RUNindex]比特RUNcnt二进制数(MSB开始)，即输出1比特‘1’；

[0156] 跳出d步骤。

[0157] 此时的码字为“111101”，RUNindex值为4。

[0158] ■e步骤

[0159] 由于RUNindex值为4大于0，执行减1变为3。

[0160] 完成所有的编码流程，跳到a步骤，等待下一次编码。

[0161] 最终的码字为“111101”，RUNindex值为3。

[0162] ●第二次编码RUNcnt＝5，EOLine＝0

[0163] ■a步骤

[0164] 由于上一次的最终值RUNindex＝3，即2J[RUNIndex]＝2J[3]＝20＝1

[0165] 按照编码流程，RUNcnt≥2J[RUNIndex]即5≥1，输出比特’1’；同时RUNcnt＝J[RUNIndex]
RUNcnt-2 ＝4；RUNindex加1变为4。

[0166] 由于RUNcnt≥2J[RUNIndex]即4≥2，继续执行a步骤，输出比特’1’；同时RUNcnt＝J[RUNIndex]RUNcnt-2 ＝2；RUNindex加1变为5。

[0167] 由于RUNcnt≥2J[RUNIndex]即2≥2，继续执行a步骤，输出比特’1’；同时RUNcnt＝J[RUNIndex]RUNcnt-2 ＝0；RUNindex加1变为6。

[0168] 由于RUNcnt≥2J[RUNIndex]即0≥2不成立，跳出a步骤。

[0169] 这样a步骤循环执行了三次，输出码字为“111”，RUNindex值为6。

[0170] ■b步骤

[0171] 由于EOLine为0，不执行直接跳出b步骤。

[0172] 此时的码字为“111”，RUNindex值为6。

[0173] ■c步骤

[0174] 输出比特’0’，跳出c步骤。

[0175] 此时的码字为“1110”，RUNindex值为6。

[0176] ■d步骤

[0177] 输出J[RUNindex]比特RUNcnt二进制数(MSB开始)，即输出1比特’0’；

[0178] 跳出d步骤。

[0179] 此时的码字为“11100”，RUNindex值为6。

[0180] ■e步骤

[0181] 由于RUNindex值为6大于0，执行减1变为5。

[0182] 完成所有的编码流程，跳到a步骤，等待下一次编码。

[0183] 最终的码字为“11100”，RUNindex值为5。

[0184] (二)采用本发明方法

[0185] ●第一次编码RUNcnt＝5，EOLine＝0

[0186] ■编码映射步骤

[0187] 此时RUNindex＝0，查表得Sub_Jvalue[0]＝0，J_Value[RUNindex]＝1。

[0188] J_Trans_RUNindex[0..31] ＝ J_Trans[0..31]-Sub_Jvalue[3] ＝ J_Trans[0..31]。

[0189] 采用RUNcnt＝5和J_Trans_RUNindex一一比较并且拼接，结果Map_Value为0xf0_00_00_00。采用RUNcnt和J_Value[RUNindex]比较得CompareFlag为1。

[0190] 可得，Map_Value为0xf0_00_00_00，CompareFlag为1。

[0191] ■RUNindex更新步骤

[0192] CompareFlag为1，执行一级和二级更新。一级更新通过Map_Value＝0xf0_00_00_00查表1的RUNindex为4；二级更新RUNindex减1为3。

[0193] 最终，RUNindex更新后的结果为3。

[0194] ■码字产生步骤

[0195] 通过Map_Value为0xf0_00_00_00查表2，

[0196] 游长编码输出为“1111”，残差编码输出‘1’。

[0197] 另外，由于残差编码值大于零，残差标志Leaving_Flag为1。

[0198] ■码字合成步骤

[0199] 比较标志为1、残差标志为1，行尾标志为0，所以，采用表3序号1的码字合成方式完成输出，结果为“1111”&’0’&’1’即“111101”。

[0200] 最终的输出结果为“111101”，RUNindex为3。

[0201] ●第二次编码RUNcnt＝5，EOLine＝0

[0202] ■编码映射步骤

[0203] 此时RUNindex＝3，查表得Sub_Jvalue[3]＝3，J_value[RUNindex]＝1。

[0204] J_Trans_RUNindex[0..31] ＝ J_Trans[0..31]-Sub_Jvalue[3] ＝ J_Trans[0..31]。

[0205] 采用RUNcnt＝5和J_Trans_RUNindex一一比较并且拼接，结果Map_Value为0xfc_00_00_00。采用RUNcnt＝5和J_Value[RUNindex]＝1比较得CompareFlag为1。

[0206] 可得，Map_Value为0xfc_00_00_00，CompareFlag为1。

[0207] ■RUNindex更新步骤

[0208] CompareFlag为1，执行一级和二级更新。一级更新通过Map_Value＝0xfc_00_00_00查表1的RUNindex为6；二级更新RUNindex减1为5。

[0209] ■码字产生步骤

[0210] 通过Map_Value为Oxfc_00_00_00查表2，

[0211] 游长编码输出为“111”，残差编码输出‘0’。

[0212] 另外，由于残差编码值不大于零，残差标志Leaving_Flag为0。

[0213] ■码字合成步骤

[0214] 比较标志为1、残差标志为0，行尾标志为0，所以，采用表3序号1的码字合成方式完成输出，结果为“1111”&’0’&’0’即“111100”。

[0215] 最终的输出结果为“111100”，RUNindex为5。

[0216] 可见，本发明方法通过引入编码映射操作和RUNindex单双周期更新操作，可以流水线实时实现JPEG-LS游程编码算法。而原标准算法由于a步骤的循环编码需要多个时钟
周期以及a、b和e步骤都需要更新索引值，在本次编码还未结束时下一次编码又到来的情
况会出现，所以不能完成流水线实时编码要求。对比标准算法，本发明方法硬件实现采用多路选择器、寄存器、查找表和块存储器实现，时钟频率可达80MHz，可以广泛应用于JPEG-LS无损或近无损压缩硬件算法。

[0217] 本发明说明书中未作详细描述的内容属本领域技术人员的公知技术。