劉亞允，來(lái)智勇，方　勇

（西北農(nóng)林科技大學(xué) 信息工程學(xué)院，陜西 楊陵　712100）

一種基于碼譜數(shù)值算法的改進(jìn)算法

劉亞允，來(lái)智勇，方勇

（西北農(nóng)林科技大學(xué) 信息工程學(xué)院，陜西 楊陵712100）

碼譜是一種分析分布式算術(shù)碼的編碼性能和解碼復(fù)雜度的工具，能有效提高編碼性能。碼譜的計(jì)算一般采用數(shù)值算法，該方法是一個(gè)迭代計(jì)算的過(guò)程，時(shí)間復(fù)雜度很高。針對(duì)時(shí)間復(fù)雜度高這個(gè)問(wèn)題，通過(guò)去掉多余的函數(shù)精簡(jiǎn)數(shù)值算法，提出一種基于碼譜數(shù)值算法的改進(jìn)算法，進(jìn)而降低時(shí)間復(fù)雜度。從理論上證明改進(jìn)數(shù)值算法的正確性，實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的數(shù)值算法能有效提高碼譜的計(jì)算效率，拓寬碼譜的實(shí)際應(yīng)用范圍。

分布式算術(shù)碼；碼譜；數(shù)值算法；迭代計(jì)算

0　引　言

隨著信息技術(shù)的不斷發(fā)展，海量的數(shù)據(jù)不斷產(chǎn)生，數(shù)據(jù)存儲(chǔ)的需求越來(lái)越大，編碼技術(shù)在其中起著越來(lái)越重要的作用［1?2］。分布式算術(shù)碼以其接近香農(nóng)極限的優(yōu)良性能得到廣泛應(yīng)用［3?7］。其中算術(shù)碼碼譜能改進(jìn)分布式算術(shù)碼的編解碼過(guò)程，降低實(shí)際解碼錯(cuò)誤率［8?10］，對(duì)分布式算術(shù)碼的實(shí)際應(yīng)用有重要作用［11］。碼譜的計(jì)算一般采用數(shù)值計(jì)算的方法。該方法是一個(gè)迭代計(jì)算的過(guò)程，主要分四步：離散化、初始化、迭代和歸一化。迭代過(guò)程是將區(qū)間劃分為三部分，clip函數(shù)將區(qū)間內(nèi)參數(shù)范圍限制到［0，N-1］，是整個(gè)迭代過(guò)程最耗時(shí)的部分。而該數(shù)值算法的主要計(jì)算集中在迭代過(guò)程，隨著迭代次數(shù)的增加，算法的效率會(huì)大幅度降低［7?8］。

針對(duì)數(shù)值算法計(jì)算復(fù)雜度高、效率低的問(wèn)題，簡(jiǎn)化現(xiàn)有的數(shù)值算法，提出一種改進(jìn)算法。理論證明劃分后的區(qū)間在不需要clip函數(shù)的情況下，參數(shù)也能保證在區(qū)間［0，N-1］內(nèi)，進(jìn)而提出一種去clip函數(shù)的改進(jìn)算法。本文在理論上證明改進(jìn)算法的正確性，實(shí)驗(yàn)結(jié)果表明改進(jìn)算法能夠有效提高計(jì)算效率。

1　算術(shù)碼碼譜

式中，0≤u＜1。式（1）是一個(gè)關(guān)于函數(shù) f（u）的方程，該方程的解就是碼譜的初始譜。

將信源集合X分為兩個(gè)子集X0和X1，其中X0和X1分別表示首個(gè)符號(hào)為“0”和“1”的信源構(gòu)成的子集。f0（u）表示X0的初始譜，f1（u）表示X1的初始譜，則 f（u），f0（u）和 f1（u）三者的關(guān)系滿足：

為了求解初始譜的顯式解，需要借助傅里葉變換，式（3）中給出了詳細(xì)求解過(guò)程，初始譜的顯式解形式如下：

由于涉及到卷積，初始譜顯式解的求解過(guò)程非常復(fù)雜，一般利用數(shù)值算法來(lái)求解碼譜初始譜。

2　碼譜數(shù)值算法

數(shù)值算法的具體過(guò)程如下：

從“畫家”“操縱者”“創(chuàng)造性叛逆”者等比喻可見，這一時(shí)期的譯學(xué)研究賦予了譯者前所未有的自由，充分肯定了譯者在翻譯中所起的重要作用，使其主體性得到進(jìn)一步彰顯。

（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將整個(gè)區(qū)間劃分為三個(gè)子區(qū)間，對(duì)于各個(gè)子區(qū)間，其迭代函數(shù)分別為：

（5）終止判斷。對(duì)兩次連續(xù)迭代的結(jié)果，計(jì)算其均方差作為判斷結(jié)果的條件，設(shè)閾值為Δ，迭代結(jié)束的條件為：

3　改進(jìn)的碼譜數(shù)值算法

上述的碼譜數(shù)值算法中，clip函數(shù)是為了將參數(shù)的范圍限定在區(qū)間中，即保證rnd函數(shù)值在區(qū)間。但是本文通過(guò)理論證明發(fā)現(xiàn)rnd函數(shù)值本身的取值范圍就在區(qū)間中，所以clip函數(shù)是可以簡(jiǎn)化掉的，證明過(guò)程如下。

在式（4）中，當(dāng)0≤n＜L時(shí)，可以得到：

從上面的推論可以得知rnd（·）函數(shù)本身的取值范圍就是［0，N-1］，而clip函數(shù)的作用是保證rnd（·）函數(shù)值的范圍在［0，N-1］之間，可見clip函數(shù)是多余的，因此可以去掉clip函數(shù)，簡(jiǎn)化迭代運(yùn)算，提高計(jì)算速度。

改進(jìn)后碼譜數(shù)值算法主要體現(xiàn)在迭代運(yùn)算，過(guò)程如下：

迭代：令L=rnd（N（1-q）），H=rnd（Nq）。對(duì)于各個(gè)子區(qū)間，其迭代函數(shù)分別為0≤n＜L時(shí)，對(duì)應(yīng)的子區(qū)間為，迭代函數(shù)為：

4　實(shí)　驗(yàn)

該部分主要通過(guò)實(shí)驗(yàn)說(shuō)明改進(jìn)算法的正確性和效率。在相同的實(shí)驗(yàn)條件下，參數(shù)設(shè)置為：N=105，f（0）（n）=1，0≤n＜N。

（1）正確性。利用數(shù)值算法計(jì)算算術(shù)碼碼譜，實(shí)驗(yàn)選取不同的參數(shù)來(lái)比較兩種數(shù)值算法的正確性和穩(wěn)定性，這里選取q=0.7和q=0.9兩個(gè)參數(shù)給出說(shuō)明，結(jié)果如圖1所示。

圖1　兩種數(shù)值算法的計(jì)算結(jié)果比較

圖1中淺灰色的虛線和實(shí)線線表示不同參數(shù)（q=0.7和q=0.9）下經(jīng)典的數(shù)值算法計(jì)算的碼譜值，黑色的“五角星”線和“+”線表示改進(jìn)后的數(shù)值算法計(jì)算的碼譜值，圖1可以看出相同參數(shù)下，不同方法得到的曲線完全重合，說(shuō)明改進(jìn)后數(shù)值算法的正確性和穩(wěn)定性。

（2）效率。實(shí)驗(yàn)取不同參數(shù)，比較改進(jìn)前后數(shù)值算法的運(yùn)行時(shí)間，結(jié)果如表1和圖2所示。

圖2　兩種數(shù)值算法的運(yùn)行速度比較

表1　兩種數(shù)值算法的實(shí)驗(yàn)結(jié)果對(duì)比

表1取8組實(shí)驗(yàn)數(shù)據(jù)，由于計(jì)算過(guò)程有隨機(jī)性，每組結(jié)果取5 000次實(shí)驗(yàn)后的平均值。實(shí)驗(yàn)結(jié)果如表1所示，表中第一列表示參數(shù)q，第二列表示改進(jìn)前數(shù)值算法的運(yùn)行時(shí)間，第三列表示改進(jìn)后數(shù)值算法的運(yùn)行時(shí)間，第四列表示改進(jìn)后數(shù)值算法的加速比。由表1可以看出，改進(jìn)后的數(shù)值算法的運(yùn)行速度相比改進(jìn)前的數(shù)值算法得到了1.1～1.3倍的加速比。實(shí)驗(yàn)結(jié)果充分證明了改進(jìn)后的數(shù)值算法的有效性和可行性。圖2是對(duì)表1中8組不同參數(shù)設(shè)置下兩種數(shù)值算法速度對(duì)比效果圖，其中灰色是改進(jìn)后的運(yùn)行時(shí)間。

去掉clip函數(shù)后，可以簡(jiǎn)化計(jì)算過(guò)程，從時(shí)間復(fù)雜度來(lái)看改進(jìn)前數(shù)值算法的時(shí)間復(fù)雜度為O（3N+KN），簡(jiǎn)化后的算法去掉了clip函數(shù)，算法的時(shí)間復(fù)雜度為O（N+KN），K表示迭代次數(shù)，實(shí)驗(yàn)表明K的值并不是很大。比較時(shí)間復(fù)雜度可知，該改進(jìn)后的算法在效率上有一定的提升。由以上實(shí)驗(yàn)結(jié)果可知，改進(jìn)后的數(shù)值算法不僅保證計(jì)算結(jié)果的正確性，而且有效提高計(jì)算效率，大大提升碼譜的實(shí)用性。

5　結(jié)　語(yǔ)

通過(guò)分析經(jīng)典碼譜數(shù)值方法的迭代過(guò)程，提出一種去clip函數(shù)的基于碼譜數(shù)值算法的改進(jìn)算法。不僅在理論上證明了該方法的正確性，而且實(shí)驗(yàn)結(jié)果表明，相比經(jīng)典的碼譜數(shù)值算法，提出的改進(jìn)算法在效率上有1.1～1.3倍的提升，一定程度上緩解了經(jīng)典碼譜數(shù)值算法效率低的問(wèn)題。碼譜計(jì)算的難點(diǎn)在于數(shù)值計(jì)算，解決了這個(gè)問(wèn)題，以后工作的重點(diǎn)是將碼譜推廣到一般信源。

注：本文通訊作者為來(lái)智勇。

［1］陳運(yùn).信息論與編碼［M］.2版.北京：電子工業(yè)出版社，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，F(xiàn)ANG 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，F(xiàn)ANG 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—），女，碩士研究生。研究方向是算術(shù)碼碼譜、分布式算術(shù)碼。來(lái)智勇（1959—），男，教授，博士。研究方向?yàn)榍度胧较到y(tǒng)。方勇（1979—），男，教授，博士。研究方向?yàn)榫幋a、分布式算術(shù)編碼。

2016?01?22

國(guó)家自然科學(xué)基金資助項(xiàng)目：算術(shù)碼碼譜及其應(yīng)用研究（61271280）