自适应算术编码的FPGA

3.2 码表的设计及修改  

自适应算术编码器可以在许多场合中得到应用。本文实现的自适应算术编码器应用在采用6符号对小波变换系数进行零树编码的小波域视频编码中，因此设计的码表中含有六个符号。这样根据自适应算术编码的基本原理，将区间分成六个子区间，整个区间含水量有七个分割点。所以码表可以用七个8 位寄存器表示。初始时设定等概率，这时七个寄存器可以顺序地存储0 到6 这七个数，即每个子区间的数值为1。随着符号不断地输入，自适应地修改码表，并且在修改码表的过程中时刻要保持寄存器中的数值是递增的。  

修改码表时，首先判断输入符号，确定其所在区间，同时为后续模块输出该子区间的两个端点值l_count 和h_count 以及码表的最后一个端点值scale，然后进行码表的修改：将当前符号所在区间之后的所有端点值都加1，即当前区间及后面所有子我间的h_count=h_count+1,这样即完成了码表的修改。在数值不断累加过程中，寄存器中的数值为255 时，需要对每一个寄存器中的值都取半，并同时对相邻的两个寄存器中的值进行比较，时刻保持数值是递值的。这样，处理前后的概率十分接近，对压缩比影响不大。  

修改码表模块在输出h_count、l_count 和scale 之后，后面的计算子区间的模块即可进行计算；而修改码表模块在输出h_count、l_count 和scale 之后，亦可进行码表的修改。因此，这两个操作可以采用并行处理的方法实现，极大地节省了所用的时钟周期，相应地提高了速度，达到了优化的目的。表3 给出了输入符号为3（对应于寄存器2 与寄存器3 之间的区间）时码表的修改过程。  

表3 码表修改前后对照表寄存器  

  
3.3 区间计算及确定  

初始时符号所在的总区间为high=0xff,low=0(high 和low 分别表示已编码的符号序列所在子区间的上下界)。随着符号的不断输入，high 和low 的值也不断地减小，用以表示输入符号序列所对应的子区间。通过如下的公式可确定输入符号的区间：  

  

计算时，最耗资源的是乘法器和除法器。本方案中乘法器采用参数化模块lpm 中的lpm_mult生成。而除法器则自动编写。虽然占用的时钟周期较多，但与使用lpm 相比，这样做可以大大地提高工作频率，从总体上提高性能。  

3.4 并行编码  

在区间计算过程中，high 和low 总是有限值，不可能无限制地划分下去。为了能够实现连续的编码，通过对high 和low 的处理，可以实现利用有限长的寄存器表示无限精度的区间，即在不断修改high 和low 的过程中输出high 和low 中相同的高端位，形成输出码流。详细过程如下：  

在区间确定之后，将low 和high 按位比较，若首位相同，则输出首位二进制码，产生输出码流，同时把low 和high 左移，low 末位补0，high 末位补1。循环比较输出，直到首位不同为止。如：   

high = 00110110
low = 00100111

输出码流为001,而high 和low 的结果为：

high = 10110111
low = 00111000  

通过这种连续地处理便可生成符号序列的自适应算术编码结束。但随着待编码符号序列的不断输入，可能会出现high 和low 十分接近，并且high 和low 的首位没有相同位的情况，如：

high = 10000000
low = 01111111  

称这种现象为产生了下溢。产生下溢后，后面的编码都失去了意义，此时需要特殊处理。  

对于下溢的处理方法为：保留首位，同时删除紧接在首位后的high 中连续的0 和low 中连续的1，并且保证对high 和low 删除的位数相同，若连续0 和连续1 的位数不同，则取其较小者；然后high 和low 左移相同的位数，同时high 的低位补1，low 的低位补0。表4给出了下溢处理前后high 和low 值。  

表4 下溢处理前后对照表  
  

经过处理后，扩大了区间，使得后面的编码可以顺利地进行。  

在考虑了下溢的编码输出中，下溢作为输出码流的一部分，使得解码时能对下溢进行同样的处理，达到编解码的一致。但是下溢产生后并不马上输出，只记下下溢的个数，下溢则是在下一个符号编码时进行输出的。在下一个符号编码时，如果high 和low 比较后高端有相同位则输出下溢，即在第一个输出后紧接着插入首位的反，插入首则反的个数为前面产生下溢的个数，然后输出相同的次高位及以后相同的各位。这样处理既保留了下溢的信息又使得输出码流不偏离编码符号所在的子区间，使得解码时很容易处理。但是如此high 和low 比较后没有相同输出则不输出下溢，而是把两次产生的下溢的个数进行累加，再输入下一个符号，直到high 和low 有相同首位才输出下溢。  

例如：在一个符号编码计算后得到的high=11010010 和low=11001101，而前一个符号编码产生的下溢为1 个，比较后输出为1010，同时记录下产生的下溢2 个，如表5 所示。  

表5 含有下溢的编码输出