【摘 要】動(dòng)態(tài)規(guī)劃屬算法設(shè)計(jì)方案，多用在尋找問問題最優(yōu)解方面。若把動(dòng)態(tài)規(guī)劃的所有子問題皆看作有向圖的節(jié)點(diǎn)，則動(dòng)態(tài)規(guī)劃便可被考慮成對(duì)應(yīng)的有向無圈圖。針對(duì)某些具有特殊結(jié)構(gòu)的有向無圈圖，其往往可以為動(dòng)態(tài)規(guī)劃提供更大的便捷度。移動(dòng)通信通常采用優(yōu)化通信編碼方案，已達(dá)到控制宿主能耗的目的。本文就移動(dòng)通信內(nèi)降低能耗的前綴碼的動(dòng)態(tài)規(guī)劃加速問題展開討論。

【關(guān)鍵詞】移動(dòng)通信 前綴碼 動(dòng)態(tài)規(guī)劃 時(shí)間復(fù)雜度

一、前綴碼

所謂前綴碼，其一直被定性為計(jì)算機(jī)科學(xué)和信息論領(lǐng)域的經(jīng)典問題。如果要對(duì)n個(gè)符號(hào)予以二進(jìn)制編碼，則Huffman編碼僅需依托貪婪算法和O（nlgn）的時(shí)間復(fù)雜度便可獲取該組符號(hào)的最優(yōu)編碼。Huffman編碼亦可用來推到r個(gè)碼元的最優(yōu)編碼。如果單詞以排序狀態(tài)出現(xiàn)頻率，Huffman編碼算法可把時(shí)間復(fù)雜度控制到O（m）階段。針對(duì)前綴碼問題，諸多學(xué)者皆做了大量的研究。研究證實(shí)，編碼后字符串內(nèi)碼元的分布位置對(duì)對(duì)應(yīng)碼元的長(zhǎng)度起決定性的作用?；诖?，本文引入了一種構(gòu)造前綴碼的動(dòng)態(tài)規(guī)劃改進(jìn)法，即把動(dòng)態(tài)規(guī)劃的狀態(tài)集合以若干批次呈現(xiàn)出來，而狀態(tài)結(jié)合間呈相互依賴關(guān)系。通過對(duì)各狀態(tài)值予以成批量計(jì)算后，便可把計(jì)算各狀態(tài)的平攤時(shí)間復(fù)雜度控制到O（1）。

二、預(yù)備知識(shí)

（一）問題定義

為了實(shí)現(xiàn)對(duì)問題的形式化定義，本文引入如下參數(shù)量：N為待編碼的符號(hào)集合；n為符號(hào)集合的取值；pi為各符號(hào)的分布概率。本文認(rèn)為概率的排序問題對(duì)算法時(shí)間復(fù)雜度的影響并不大。基于此，本文假定概率已排序（p1≥p2≥p3……≥pn），編碼后的字符串集合記做W=﹛w1，w2，w3……，wn-﹜， w1的長(zhǎng)度記做，wi內(nèi)1的個(gè)數(shù)記做wt（wi）。那么，該編碼的期望長(zhǎng)度可表示為：

本文討論的問題為：移動(dòng)任一可行編碼的宿主，由此發(fā)出的任一單詞wi的耗能皆存有上界U，其中。此時(shí)，本文需要從整個(gè)編碼W內(nèi)挑選出一個(gè)滿足最小的。

（二）最優(yōu)樹性質(zhì)

若編碼為二進(jìn)制，則一個(gè)前綴碼通常可映射到一棵二叉樹，其中二叉樹的葉節(jié)點(diǎn)與前綴碼的待編碼符號(hào)呈一一對(duì)應(yīng)關(guān)系。針對(duì)二叉樹的邊，本文把向左的邊記做1，向右的邊記做0，此時(shí)可把葉節(jié)點(diǎn)與根節(jié)點(diǎn)間分布的01字符串假定為葉節(jié)點(diǎn)對(duì)應(yīng)符號(hào)的編碼。就節(jié)點(diǎn)v而言，如果節(jié)點(diǎn)與根節(jié)點(diǎn)間的距離長(zhǎng)約i，則該節(jié)點(diǎn)便被看作分布在第i層。如果僅對(duì)二叉樹第i層及以上部分作出考慮，則此情況可被稱作i層數(shù)或i層部分樹。本文把i層樹的節(jié)點(diǎn)深度表述為d（v），而通常把節(jié)點(diǎn)與根節(jié)點(diǎn)間分布的1的個(gè)數(shù)表述為wt（v），即節(jié)點(diǎn)的權(quán)重。如果編碼后的符號(hào)wi與葉節(jié)點(diǎn)vi間呈一一對(duì)應(yīng)關(guān)系，其中該節(jié)點(diǎn)的概率被記做pi，。那么，此二叉樹的代價(jià)可被表述為：

（為葉節(jié)點(diǎn)）

針對(duì)與最優(yōu)編碼呈對(duì)應(yīng)關(guān)系的二叉樹，其主要性質(zhì)如下所示，其中本文假定最優(yōu)編碼已排序（p1≥p2≥p3……≥pn），葉節(jié)點(diǎn)與編碼后字符串wi間呈對(duì)應(yīng)關(guān)系，為葉節(jié)點(diǎn)對(duì)應(yīng)符號(hào)的分布概率。

性質(zhì)①，如果，那么，；

性質(zhì)②，針對(duì)一棵滿二叉樹，其代價(jià)等效于最優(yōu)二叉樹，且其葉節(jié)點(diǎn)個(gè)數(shù)滿足：（如果葉節(jié)點(diǎn)個(gè)數(shù)>n，則pt=0，i>n）。

性質(zhì)③，就一棵最優(yōu)樹任何層i而言，任一分支節(jié)點(diǎn)及任一葉節(jié)點(diǎn)v皆滿足：。

三、批處理加速

由最優(yōu)樹的遞歸構(gòu)造（此部分省略）可知，簽名總數(shù)共O（nU），則其對(duì)應(yīng)的動(dòng)態(tài)規(guī)劃時(shí)間復(fù)雜度記做O（nU+1），下文欲就簽名總數(shù)為O（nU）的集合予以分批加速動(dòng)態(tài)規(guī)劃?；诖耍疚亩x了如下集合：

式中，

d滿足1≤d≤n+1；囊括了全部簽名。

就d而言，上述兩類集合皆囊括了指數(shù)個(gè)簽名。就簽名而言，由指數(shù)個(gè)可擴(kuò)展成簽名，則就任一而言，其可能存在的個(gè)數(shù)很多，而其中必然包含了一個(gè)最有選擇?；诖?，本文引入了“轉(zhuǎn)換”計(jì)算方向法，即對(duì)I’（d）內(nèi)經(jīng)簽名擴(kuò)展后的代價(jià)予以批處理計(jì)算，并就I（d）簽名的最優(yōu)代價(jià)與I’（d）簽名的代價(jià)予以對(duì)比分析。

就“轉(zhuǎn)換”計(jì)算方向法而言，首先應(yīng)考慮各變量在遞推關(guān)系中的相互聯(lián)系，并由此得出如下結(jié)論：就任一而言，所有可擴(kuò)展到對(duì)應(yīng)簽名的皆屬I’（d），其最有代價(jià)間的相互關(guān)系可描述為：

其次應(yīng)選擇I’（d）內(nèi)O（n）個(gè)的簽名，即設(shè)定一個(gè)多元組（長(zhǎng)度約U-2）：

現(xiàn)把上述多元組與I（d）的某個(gè)子集對(duì)應(yīng)，此子集如下：

就O（nU）的時(shí)間復(fù)雜度而言，1個(gè)d通常對(duì)應(yīng)O（nU-2）個(gè)多元組，而任一多元組皆需O（n）時(shí)間查找出最小值。那么，單個(gè)d所需時(shí)間可記做O（nU-1），由此可知計(jì)算最優(yōu)代價(jià)總時(shí)間復(fù)雜度應(yīng)記做O（nU）。

四、結(jié)束語

綜上所述，本文的研究對(duì)象為編碼方面的動(dòng)態(tài)規(guī)劃加速問題。若符號(hào)的個(gè)數(shù)和通信內(nèi)符號(hào)分布的概率既定，且各符號(hào)經(jīng)編碼后1分布的個(gè)數(shù)≤U，本文由此引入了一種計(jì)算編碼最優(yōu)期望長(zhǎng)度的方法。計(jì)算結(jié)果顯示，其時(shí)間復(fù)雜度為O（nU），則O（n2）的時(shí)間復(fù)雜度遠(yuǎn)小于由傳統(tǒng)計(jì)算方法所獲取的時(shí)間復(fù)雜度。

參考文獻(xiàn)：

[1] 構(gòu)造移動(dòng)通信中降低能耗的前綴碼的動(dòng)態(tài)規(guī)劃加速[J].計(jì)算機(jī)工程與科學(xué)，2009，31（12）：134-137.

[2] 張丙杰，胡捍英，王大鳴等.一種增強(qiáng)的GEO衛(wèi)星CDMA通信系統(tǒng)隨機(jī)接入方式[J].電路與系統(tǒng)學(xué)報(bào)，2010，15（5）：122-126.

[3] 肖尚輝，張忠培，史治平等.多基站協(xié)作下行系統(tǒng)中異步空時(shí)碼構(gòu)造與分析[J].電子科技大學(xué)學(xué)報(bào)，2010，39（3）：335-339.

[4] 孔繁庭.循環(huán)前綴在OFDM系統(tǒng)中的作用及應(yīng)用研究[D].蘭州大學(xué)，2008.

作者簡(jiǎn)介：

劉磊，1983年1月出生，現(xiàn)就職于河北張家口移動(dòng)公司。