別玉濤, 李兆璽, 李 蛟, 張宇楠, 趙宏偉

(吉林大學 a.公共計算機教學與研究中心; b.通信工程學院; c.圖書館; d.教務處; e.計算機科學與技術學院, 長春 130012)

0 引 言

隨著云計算、大數(shù)據(jù)技術的不斷發(fā)展, 4K視頻、虛擬現(xiàn)實(VR: Virtual Reality)、視頻直播等應用模式的出現(xiàn), 多因素促使光傳輸網(wǎng)不斷向高速大容量發(fā)展[1]。如何在不增加干線重建成本的基礎上, 實現(xiàn)光傳輸網(wǎng)向超高速大容量的平滑升級, 是當前光通信系統(tǒng)面臨的主要問題之一。研究表明, 采用高階調(diào)制格式可以有效提升系統(tǒng)傳輸容量[2]。

高維調(diào)制的基本思想是：將比特標簽映射到N維實數(shù)向量代表的N維空間星座點上, 并同時應用光場中的模式[3]、偏振態(tài)[4]、載波[5]、時隙和軌道角動量等多個自由度對N維信息向量統(tǒng)一進行編碼調(diào)制[6]。在復用的基礎上, 通過進一步利用這些維度資源, 實現(xiàn)了在不損失譜效率的前提下, 最大化星座點間的最小歐氏距離, 從而增大了信號的功率效率。通過調(diào)制格式的優(yōu)化, 較好地解決了譜效率與功率效率之間的矛盾, 大幅提升了現(xiàn)有系統(tǒng)的傳輸距離。

在高維調(diào)制中, 為獲得較高的編碼增益, 通常在高維晶格點中選取一定數(shù)目的格點作為星座點集[7], 將比特信息映射到這些選定的格點上的過程即為晶格編碼(LC: Lattice Code), 逆過程即為晶格解碼(LD: Lattice Decode)[8-9]。與二維調(diào)制相比, 調(diào)制維度的增加使相同譜效率下星座點集規(guī)模更大, 星座圖結(jié)構(gòu)更復雜。如何在高速傳輸下, 實現(xiàn)比特信息到大規(guī)模高維晶格點集的實時映射和解映射至關重要。因此, 高維晶格編解碼技術是高維調(diào)制系統(tǒng)的關鍵技術之一。

1 晶格編解碼策略

目前, 實現(xiàn)高維晶格編解碼的方法主要有兩類。

第1類：公式化方法。該方法的基本思想是：建立比特標簽與晶格點的代數(shù)關系, 通過公式化方法使編碼時間復雜度獨立于星座點集規(guī)模。Conway等[10]提出了Voronoi編碼, 首次實現(xiàn)了公式化晶格編解碼。但由于Voronoi編碼星座點集的選取與晶格的Voronoi區(qū)域的形狀有關, 無法選取點數(shù)恰為M=2n(n∈Z+)的星座點集, 格點總功率也無法控制, 從而嚴重影響了Voronoi編碼的實用性。為了彌補這一不足, Kurkoski[11]又提出了嵌套晶格編碼方法, 該方法通過分別選取編碼格和成型域, 將成型域內(nèi)滿足點數(shù)要求的格點作為星座點集, 實現(xiàn)了任意點數(shù)M的選取。但該方法要求編碼格的生成矩陣是三角矩陣, 否則無法完成公式化編碼, 但生成矩陣為三角矩陣的格, 其編碼增益無法保證, 導致功率效率較低。Sommer等[12]提出了低密度晶格編碼方法 LDLC(Low-Density Lattice Codes), 該方法的編碼過程與 Voronoi編碼相同, 解碼時采用校驗矩陣迭代譯碼實現(xiàn), 迭代譯碼器的收斂性和復雜度受調(diào)制維度限制。同時, 該方法需要對編碼格設計, 以確保校驗矩陣的稀疏性。此外, 還出現(xiàn)了在LDLC基礎上演變的迭代譯碼型方法[13-14], 這些方法雖然能實現(xiàn)公式化編碼, 但譯碼器復雜, 對編碼格也具有選擇性?？梢? 目前的公式化編碼方法雖然能通過簡單代數(shù)運算實現(xiàn)比特到星座點的實時映射, 但不能普適于各種高維調(diào)制格式。因此, 公式化晶格編碼方法在高維調(diào)制系統(tǒng)中并沒有得到廣泛應用。

第2類：查找表方法。查找表法即是建立以比特標簽為地址索引, 以高維星座點坐標為存儲內(nèi)容的映射表, 發(fā)送端直接查表完成高維晶格編碼, 接收端經(jīng)判決后查表完成晶格解碼[15-18], 是二維調(diào)制常用的映射方法。由于其對調(diào)制維度、編碼格、星座點數(shù)均透明, 具有通用性, 因此, 目前高維調(diào)制系統(tǒng)中依然采用查找表法完成晶格編解碼[19-20]。然而, 由于現(xiàn)有的查找表方法中的比特標簽與格點的存儲是線性無序的, 只能順序查找,M點的線性無序查找表, 順序查表時間復雜度高達O(M), 而對于高維調(diào)制系統(tǒng), 相同譜效率下的星座點總數(shù)M隨維度陡增, 順序查表會帶來較大的時間延遲。要實現(xiàn)與16QAM相同的譜效率, 僅8維調(diào)制格式, 就要面臨65 536個8維星座點的查表規(guī)模。這樣, 即使中等譜效率的高維調(diào)制格式, 晶格編解碼產(chǎn)生的時間延遲仍然很大, 無法滿足高速大容量實時通信要求。因此, 在現(xiàn)有報道的高維調(diào)制系統(tǒng)的實驗驗證中, 只給出了維度較小, 譜效率和傳輸速率較低的實驗結(jié)果[21]。目前, Ciena公司已投入使用的8維調(diào)制技術下的跨太平洋相干通信系統(tǒng), 也僅實現(xiàn)了與BPSK(Binary Phase Shift Keying)和QPSK(Differential Phase Shift Keying)同譜效率的高速通信[22]?？梢? 由線性查表完成高維晶格編解碼帶來的時間延遲, 嚴重阻礙了高維調(diào)制技術在高速大容量光通信系統(tǒng)中的應用。

為此, 筆者提出了一種基于樹存儲的低復雜度高維晶格編解碼方法。該方法的基本思想是：利用晶格的空間分布規(guī)律, 提取高維晶格點的空間分布特征, 以這些特征為關鍵字, 將空間內(nèi)無序的高維格點存儲為有序的樹結(jié)構(gòu), 通過建立樹存儲結(jié)構(gòu)下更高效的索引算法, 將高維晶格編解碼過程簡化為由根到葉子的路徑尋址過程, 路徑即為地址；解碼過程簡化為特征檢測, 路徑恢復過程。該方法大大降低了高維晶格編解碼順序查表帶來的時間延遲, 使高維調(diào)制系統(tǒng)向更高傳輸容量升級成為可能。

2 基于樹結(jié)構(gòu)的晶格編解碼

由比特標簽(索引)搜索到它所對應的星座點, 以及從接收星座點找到比特標簽, 即是高維晶格編碼和解碼過程。筆者希望通過構(gòu)造能體現(xiàn)星座點分布規(guī)律的特征向量, 以此特征向量為結(jié)點生成樹結(jié)構(gòu)。這樣, 高維晶格編碼過程就可以簡化成從根到葉子的路徑尋址過程, 而高維晶格解碼過程可以通過檢測接收信號的幅度特征和相位特征恢復出尋址路徑以完成。

2.1 建 樹

樹是由結(jié)點和邊組成的(可能是非線性的)且不存在任何環(huán)的一種數(shù)據(jù)結(jié)構(gòu), 完美二叉樹是樹中一種特殊的結(jié)構(gòu), 除了葉子結(jié)點外的每個結(jié)點都有且只有兩個孩子結(jié)點, 即對層數(shù)為k的樹, 結(jié)點總數(shù)是2k-1。二叉搜索樹作為一種字典類型的數(shù)據(jù)結(jié)構(gòu), 能快速有效地支持搜索和插入操作, 對于有n個結(jié)點的二叉樹, 操作的時間復雜度是O(logn)。筆者應用完美二叉搜索樹進行晶格的編解碼, 能有效減少執(zhí)行時間。

建樹的基本過程為：把M個星座點作為葉子結(jié)點, 為每個特征參量選取相應的權重值, 構(gòu)造成代價值C, 然后以C為關鍵字排序建立星座點優(yōu)先隊列Q, 由自底向上的順序按照貪心選擇的原則一次確定當前要合并的2棵具有最小代價值的樹, 并依次給組合的左分支指定為0, 右分支指定為1。按照這樣的組合原則, 每次2棵具有最小代價值的樹合并后, 都會產(chǎn)生一棵新的樹, 并根據(jù)代價值算法重新為根結(jié)點計算代價值。將這棵樹添加到優(yōu)先隊列Q′中, 同時從隊列Q中刪除已選擇的兩棵樹, 經(jīng)過M/2次合并后, 隊列Q變?yōu)榭? 完成一層建樹操作。按照上述原則經(jīng)過log2M次遞歸, 即可得到要求的樹T。T是一棵二叉搜索樹, 從根結(jié)點到每個葉子結(jié)點都有唯一的路徑, 組成路徑的01序列即為該葉結(jié)點的索引。

葉子結(jié)點的尋址過程即是編碼過程。路徑恢復過程即是解碼過程。需要指出的是, 樹結(jié)點的生成過程離線完成, 結(jié)點信息存儲在發(fā)射和接收端用于高維晶格編解碼, 編解碼的在線處理過程只需按照樹存儲結(jié)構(gòu)讀取結(jié)點信息即可完成。

要建立樹存儲結(jié)構(gòu), 需要構(gòu)建以晶格分布特征為關鍵字的樹結(jié)點。高維晶格編解碼過程可通過這些特征向量包含的信息完成尋址。如何利用晶格的空間分布規(guī)律設計特征向量, 以盡量小的向量維度包含可實現(xiàn)尋址的有效信息, 是構(gòu)建樹結(jié)點特征向量的關鍵問題。根據(jù)晶格的幾何特點, 高維空間格點按照一定幾何規(guī)律分布在多個超球殼上, 格點在幅度, 偏振態(tài), 相位等方面具備一定規(guī)律性。筆者選取能最大程度表征格點特征的參量組成特征向量, 比如星座點的層半徑、功率分配比、坐標相位角等, 并將這些分布特征融合成用于索引的特征值。

設需要編碼的星座點集合為ζ={χ1,χ2,…,χi,…,χM},χi(i∈[1,M])為N維實數(shù)向量。χi的幅度特征向量、功率分配比和相位特征向量分別為r、p、α和β, 計算代價值時將按照順序給每個關鍵字分配不同的權重值, 并融合成為一個實數(shù)代價值C, 最后以代價值排序。對于二叉樹T, T.lChild和T.rChild分別表示左右子樹。

樹結(jié)構(gòu)生成步驟：

1)以χ1,χ2,…,χM為葉結(jié)點, 按照C升序排列, 構(gòu)造M棵只有一個葉結(jié)點的二叉樹Ti, 從而得到一個二叉樹的有序隊列Q={Τ1,Τ2,…,ΤM}。

2)從隊列Q中選取最前端的兩棵二叉樹Ti、Tj分別作為左、右子樹構(gòu)造一棵新的二叉樹Tk(左子樹Ci小, 右子樹Cj大), 由代價函數(shù)重新計算根結(jié)點Tk的代價值Ck, 并指定左分支為0, 右分支為1。

圖1 由8個星座點建立的樹結(jié)構(gòu)

3)在隊列Q中刪除Ti、Tj, 并將新建立的二叉樹Tk加入到有序隊列Q′中。

4)重復2),3)兩步, 直到Q為空。再令Q=Q′,Q′={}。

5)重復2),3),4)3步, 直到Q′中只剩下一棵二叉樹時, 這棵二叉樹便是所要建立的編解碼樹T。由根結(jié)點到葉結(jié)點χi的路徑即為該星座點的索引號, Index(χi), 長度為樹的高度log2M-1。

定義代價值C的計算方法如下

C=w1r+w2p+w3α+β

(1)

2.2 編 碼

編碼過程是根據(jù)索引碼查找星座點的過程。對于給定的索引碼Index(χi), 根據(jù)索引號對應到樹結(jié)構(gòu)的路徑上, 從而找到對應的星座點。

編碼算法

輸入：T是由星座點建立的樹, Index(χi)是星座點對應的索引碼。

輸出：索引碼對應的星座點。

變量：flag標識當前索引碼的位置。

begin

flag=0;

while (T!=null)

flag=flag+1;

if Index(χi)[flag]==0

T←T.lChild;

elseT←T.rChild;

end

end

returnT;

end

編碼算法中, 根據(jù)索引碼的01序列, 從根結(jié)點開始查找葉子結(jié)點, 當前索引碼為0時, 查找左孩子, 索引碼為1時, 查找右孩子。對于M個葉子結(jié)點的完美二叉樹, 路徑(索引碼)長度n=log2M, 算法執(zhí)行過程中, 加法運算2(n+1)次, 乘法運算2n次, 共計4n+2次運算。而查找表方法在編碼時, 無需乘法運算, 但是加法運算需要24n+4n次, 樹結(jié)構(gòu)的編碼算法復雜度明顯優(yōu)于查找表法。

2.3 解 碼

解碼過程是給定星座點的坐標, 通過確定該星座點是樹結(jié)構(gòu)中哪個葉子結(jié)點, 進而確定根結(jié)點到該葉子結(jié)點的路徑(即索引碼)的過程。算法Search(T,χ)實現(xiàn)在二叉樹T中遞歸查找結(jié)點χ。

算法Search(T,χ)

輸入：T是待搜索的完美二叉樹的根結(jié)點,χ是待查找的星座點。

Begin

while(T!=null)

計算qi;

if(qi==0)

else

end

end

end

(2)

解碼算法中, 先計算待查找路徑的星座點的代價值, 然后根據(jù)式(2)的策略確定當前索引碼的碼值, 最終構(gòu)成長度為n=log2M的索引碼。該算法執(zhí)行過程中需要加法運算5n(5n+13)次, 乘法運算5n(n+11)次, 共計5n(6n+24)次；而查找表法在解碼時雖不需要乘法運算, 但加法運算次數(shù)達到46(24n+4n)次, 樹結(jié)構(gòu)算法在解碼時仍明顯優(yōu)于查找表法。

3 實驗仿真與性能分析

3.1 實驗條件設定

仿真實驗在Matlab軟件上進行, 選取D4晶格前10層的星座點坐標生成了1 080個星座點, 按照代價函數(shù)的計算結(jié)果進行升序排列, 截取前1 024個星座點, 創(chuàng)建一棵11層的完美搜索二叉樹, 最底層的1 024個葉子結(jié)點從左至右按照代價函數(shù)值升序排列。

星座點的幅度特征向量r選用星座點距離超球體中心的歐氏距離的平方值, 功率分配比p選擇四維坐標的前兩位發(fā)送功率與星座點發(fā)送功率的比值, 相位特征向量α采用四維坐標的前兩位形成的相位角,β采用后兩位形成的相位角。

3.2 實驗結(jié)果及分析

1)算法復雜度。圖2對比了查找表方法和樹結(jié)構(gòu)算法在編碼(映射)和解碼(解映射)過程中所需要的總計算次數(shù), 其中橫軸n表示每符號含有的比特數(shù),n=log2M(M為星座點數(shù))，縱軸表示基本操作次數(shù)。通過圖2可以看出, 算法復雜度上, 查找表算法隨著星座點數(shù)量的增加, 計算復雜度呈幾何倍數(shù)增長, 而樹結(jié)構(gòu)算法隨著星座點數(shù)的增多, 計算復雜度并沒有明顯變化, 計算時間顯著優(yōu)于查找表法。

a 映射復雜度 b 解映射復雜度

圖3 誤碼率曲線圖

2)誤碼性能分析。對比實驗分別用查找表法和樹結(jié)構(gòu)算法, 對隨機產(chǎn)生的40 960個碼元進行編碼并解碼的操作, 圖3給出了誤碼率隨信噪比的變化曲線。從圖3中可以看出, 隨著信噪比的增加, 誤碼率不斷下降, 當信噪比達到15 dB時, 誤碼率達到10-3, 可見，該方法可以實現(xiàn)有效編解碼。

4 結(jié) 語

針對高維調(diào)制技術時間延遲的問題, 提出將數(shù)據(jù)結(jié)構(gòu)理論中的樹形結(jié)構(gòu)用于高維晶格編解碼中, 通過提取高維晶格點的空間分布特征, 將空間內(nèi)無序的高維格點存儲為有序的樹結(jié)構(gòu)。實現(xiàn)了將高維晶格編解碼過程轉(zhuǎn)化為樹存儲結(jié)構(gòu)下的路徑搜索和恢復過程的新方法。突破了現(xiàn)有高維晶格編解碼時間復雜度高產(chǎn)生的延遲大, 對傳輸速率和譜效率的限制, 從根本上改變了高維晶格編解碼的研究理念。在特征向量的選取和組合方式, 以及代價函數(shù)的構(gòu)造上進一步改進優(yōu)化, 將會降低高維晶格編解碼的誤碼率。