一种基于码谱数值算法的改进算法

刘亚允，来智勇，方　勇

（西北农林科技大学 信息工程学院，陕西 杨陵　712100）

一种基于码谱数值算法的改进算法

刘亚允，来智勇，方勇

（西北农林科技大学 信息工程学院，陕西 杨陵712100）

码谱是一种分析分布式算术码的编码性能和解码复杂度的工具，能有效提高编码性能。码谱的计算一般采用数值算法，该方法是一个迭代计算的过程，时间复杂度很高。针对时间复杂度高这个问题，通过去掉多余的函数精简数值算法，提出一种基于码谱数值算法的改进算法，进而降低时间复杂度。从理论上证明改进数值算法的正确性，实验结果表明，改进后的数值算法能有效提高码谱的计算效率，拓宽码谱的实际应用范围。

分布式算术码；码谱；数值算法；迭代计算

0　引　言

随着信息技术的不断发展，海量的数据不断产生，数据存储的需求越来越大，编码技术在其中起着越来越重要的作用［1⁃2］。分布式算术码以其接近香农极限的优良性能得到广泛应用［3⁃7］。其中算术码码谱能改进分布式算术码的编解码过程，降低实际解码错误率［8⁃10］，对分布式算术码的实际应用有重要作用［11］。码谱的计算一般采用数值计算的方法。该方法是一个迭代计算的过程，主要分四步：离散化、初始化、迭代和归一化。迭代过程是将区间划分为三部分，clip函数将区间内参数范围限制到［0，N-1］，是整个迭代过程最耗时的部分。而该数值算法的主要计算集中在迭代过程，随着迭代次数的增加，算法的效率会大幅度降低［7⁃8］。

针对数值算法计算复杂度高、效率低的问题，简化现有的数值算法，提出一种改进算法。理论证明划分后的区间在不需要clip函数的情况下，参数也能保证在区间［0，N-1］内，进而提出一种去clip函数的改进算法。本文在理论上证明改进算法的正确性，实验结果表明改进算法能够有效提高计算效率。

1　算术码码谱

式中，0≤u＜1。式（1）是一个关于函数 f（u）的方程，该方程的解就是码谱的初始谱。

将信源集合X分为两个子集X0和X1，其中X0和X1分别表示首个符号为“0”和“1”的信源构成的子集。f0（u）表示X0的初始谱，f1（u）表示X1的初始谱，则 f（u），f0（u）和 f1（u）三者的关系满足：

为了求解初始谱的显式解，需要借助傅里叶变换，式（3）中给出了详细求解过程，初始谱的显式解形式如下：

由于涉及到卷积，初始谱显式解的求解过程非常复杂，一般利用数值算法来求解码谱初始谱。

2　码谱数值算法

数值算法的具体过程如下：

从“画家”“操纵者”“创造性叛逆”者等比喻可见，这一时期的译学研究赋予了译者前所未有的自由，充分肯定了译者在翻译中所起的重要作用，使其主体性得到进一步彰显。

（2）初始化。 f（t）（n）表示t次迭代后 f（n）的值，f（0）（n）满足，初始化 f（0）（n）=1。

（3）迭代。令L=rnd（N（1-q）），H=rnd（Nq）。L和H将整个区间划分为三个子区间，对于各个子区间，其迭代函数分别为：

（5）终止判断。对两次连续迭代的结果，计算其均方差作为判断结果的条件，设阈值为Δ，迭代结束的条件为：

3　改进的码谱数值算法

上述的码谱数值算法中，clip函数是为了将参数的范围限定在区间中，即保证rnd函数值在区间。但是本文通过理论证明发现rnd函数值本身的取值范围就在区间中，所以clip函数是可以简化掉的，证明过程如下。

在式（4）中，当0≤n＜L时，可以得到：

从上面的推论可以得知rnd（·）函数本身的取值范围就是［0，N-1］，而clip函数的作用是保证rnd（·）函数值的范围在［0，N-1］之间，可见clip函数是多余的，因此可以去掉clip函数，简化迭代运算，提高计算速度。

改进后码谱数值算法主要体现在迭代运算，过程如下：

迭代：令L=rnd（N（1-q）），H=rnd（Nq）。对于各个子区间，其迭代函数分别为0≤n＜L时，对应的子区间为，迭代函数为：

4　实　验

该部分主要通过实验说明改进算法的正确性和效率。在相同的实验条件下，参数设置为：N=105，f（0）（n）=1，0≤n＜N。

（1）正确性。利用数值算法计算算术码码谱，实验选取不同的参数来比较两种数值算法的正确性和稳定性，这里选取q=0.7和q=0.9两个参数给出说明，结果如图1所示。

图1　两种数值算法的计算结果比较

图1中浅灰色的虚线和实线线表示不同参数（q=0.7和q=0.9）下经典的数值算法计算的码谱值，黑色的“五角星”线和“+”线表示改进后的数值算法计算的码谱值，图1可以看出相同参数下，不同方法得到的曲线完全重合，说明改进后数值算法的正确性和稳定性。

（2）效率。实验取不同参数，比较改进前后数值算法的运行时间，结果如表1和图2所示。

图2　两种数值算法的运行速度比较

表1　两种数值算法的实验结果对比

表1取8组实验数据，由于计算过程有随机性，每组结果取5 000次实验后的平均值。实验结果如表1所示，表中第一列表示参数q，第二列表示改进前数值算法的运行时间，第三列表示改进后数值算法的运行时间，第四列表示改进后数值算法的加速比。由表1可以看出，改进后的数值算法的运行速度相比改进前的数值算法得到了1.1～1.3倍的加速比。实验结果充分证明了改进后的数值算法的有效性和可行性。图2是对表1中8组不同参数设置下两种数值算法速度对比效果图，其中灰色是改进后的运行时间。

去掉clip函数后，可以简化计算过程，从时间复杂度来看改进前数值算法的时间复杂度为O（3N+KN），简化后的算法去掉了clip函数，算法的时间复杂度为O（N+KN），K表示迭代次数，实验表明K的值并不是很大。比较时间复杂度可知，该改进后的算法在效率上有一定的提升。由以上实验结果可知，改进后的数值算法不仅保证计算结果的正确性，而且有效提高计算效率，大大提升码谱的实用性。

5　结　语

通过分析经典码谱数值方法的迭代过程，提出一种去clip函数的基于码谱数值算法的改进算法。不仅在理论上证明了该方法的正确性，而且实验结果表明，相比经典的码谱数值算法，提出的改进算法在效率上有1.1～1.3倍的提升，一定程度上缓解了经典码谱数值算法效率低的问题。码谱计算的难点在于数值计算，解决了这个问题，以后工作的重点是将码谱推广到一般信源。

注：本文通讯作者为来智勇。

［1］陈运.信息论与编码［M］.2版.北京：电子工业出版社，2011：49⁃52.

［2］RISSANEN J J.Generalized Kraft inequality and arithmetic coding［J］.IBM journal of research development，1976，20 （3）：198⁃203.

［3］GRANGETTO M，MAGLI E，OLMO G.Distributed arithmetic coding［J］.IEEE communication letters，2007，11（11）：883⁃885.

［4］GRANGETTO M，MAGLI E，TRON R，et al.Rate⁃compatible distributed arithmetic coding［J］.IEEE communication letters，2008，12（8）：575⁃577.

［5］GRANGETTO M，MAGLI E，OLMO G.Distributed joint source⁃channel arithmetic coding［C］//Proceedings of IEEE ICIP.［S.l.］：IEEE，2007：3717⁃3720.

［6］GRANGETTO M，MAGLI E，TRON R，et al.Distributed arith⁃metic coding for the Slepian⁃Wolf problem［J］.IEEE transac⁃tions on signal process，2009，57（6）：2245⁃2257.

［7］FANG Yong.DAC spectrum of binary sources with equally⁃like⁃ ly symbols［J］.IEEE transactions on communication，2013，61 （4）：1584⁃1594.

［8］FANG Yong.Distribution of distributed arithmetic codewords for equiprobable binary sources［J］.IEEE signal processing let⁃ters，2009，16（12）：1079⁃1082.

［9］FANG Yong.Asymmetric Slepian⁃Wolf coding of nonstationarily⁃correlated M⁃ary sources with sliding⁃window belief propagation ［J］.IEEE transactions on communication，2013，61（12）：5114⁃5124.

［10］LIU Yayun，FANG Yong.Codebook cardinality spectrum of distributed arithmetic codes for nonuniform binary sources［J］. Communications in computer and information science，2015，547：458⁃467.

［11］FANG Yong，CHEN Liang.Improved binary DAC codec with spectrum for equiprobable sources［J］.IEEE transactions on communication，2014，62（1）：256⁃268.

An improved algorithm based on code spectrum numerical algorithm

LIU Yayun，LAI Zhiyong，FANG Yong
（College of Information Engineering，Northwest Agriculture&Forestry University，Yangling 712100，China）

Code spectrum is a tool of analyzing the encoding performance and decoding complexity of distributed arithmetic coding，which can effectively improve the encoding performance.The numerical algorithm is usually used in code spectrum cal⁃culation，but it is an iterative calculation process，in which the time complexity is very high.To solve this problem，an im⁃proved algorithm based on code spectrum numerical algorithm is proposed，which simplifies the numerical algorithm by remov⁃ing the unnecessary functions.The correctness of the improved numerical algorithm is verified theoretically in the paper.The ex⁃perimental results show that the improved numerical algorithm can effectively improve the computational efficiency of code spec⁃trum，and broaden the practical application range of code spectrum.

distributed arithmetic code；code spectrum；numerical algorithm；iterative calculation

TN911⁃34；TN911.2

A

1004⁃373X（2016）18⁃0001⁃03

10.16652/j.issn.1004⁃373x.2016.18.001

刘亚允（1990—），女，硕士研究生。研究方向是算术码码谱、分布式算术码。来智勇（1959—），男，教授，博士。研究方向为嵌入式系统。方勇（1979—），男，教授，博士。研究方向为编码、分布式算术编码。

2016⁃01⁃22

国家自然科学基金资助项目：算术码码谱及其应用研究（61271280）