基于編碼分布式快速哈達瑪變換的多元LDPC 碼譯碼算法研究

劉銳，黎勇

（重慶大學計算機學院，重慶 400044）

0 引言

非二元/多元 LDPC（NB-LDPC,non-binary LDPC）碼是由二元LDPC 碼在有限域（GF,galois field）上擴展而來的[1]。相比二元LDPC 碼，多元LDPC 碼更好地消除了Tanner 圖中的短環，提高了糾錯性能[2]。多元LDPC 碼用多個比特表示一個多元符號，獲得了較二元LDPC 碼更好的抗突發錯誤能力[3]。另外，多元符號與高階調制更匹配，提升了頻譜利用率[4]。

盡管多元LDPC 碼有多重優勢，但其更高的譯碼復雜度極大地阻礙了多元LDPC 碼的實際應用。多元LDPC 碼的譯碼算法以多元和積算法（QSPA,q-ary sum-product algorithm）為代表[1]，后續針對QSPA 計算復雜度問題，研究者提出了FHT-QSPA[5]、FFT-QSPA[3]等改進算法。此外，Min-Max[6]、Min-Sum[7]、EMS[8]等譯碼算法簡化了QSPA 中的迭代步驟，如替換和積操作、降低信息傳遞數量等，以不同程度的糾錯性能損失換取了譯碼復雜度的降低?，F有多元LDPC 碼的硬件加速多基于簡化譯碼算法展開，并在FPGA 和GPU 等專用芯片的支持下實現更高的譯碼吞吐量[9]。

因此，若要在單點計算資源有限且難以搭載昂貴專用芯片的設備上應用低誤碼率、高復雜度的多元LDPC 碼QSPA 譯碼，則可借鑒分布式計算思路，利用多個節點的算力，共同完成計算密集型的譯碼任務，從而在糾錯譯碼性能和算法復雜度兩方面做出更好的折中。

但是，多節點分布式系統中某些節點可能出現通信繁忙、資源搶占、節點失效等情況，從而影響整體任務。這些節點被稱為掉隊節點。為了克服節點掉隊的問題，傳統的副本策略使用多個節點負責相同的任務，只要任意節點完成當前任務即可繼續后續計算。然而，副本策略中成倍增加的資源消耗使其在資源利用率方面表現欠佳。

近年來，編碼分布式計算（CDC,coded distributed computing）（簡稱編碼計算）借鑒編碼理論，巧妙地在計算任務中嵌入了冗余信息，克服了節點掉隊問題、保護了數據隱私、優化了通信負載，成為分布式計算領域的研究熱點[10-13]。以主從架構的編碼計算方案為例，主節點能夠通過部分從節點的計算結果直接恢復出掉隊節點的計算結果，完成整體計算，克服掉隊節點的拖累[10]。

在諸多編碼計算研究中，大規模矩陣乘法（矩陣-矩陣/矩陣-向量乘法）作為機器學習算法的核心模塊受到了較多關注。多項式碼編碼計算方案在矩陣乘法中嵌入了多項式結構[11]，使主節點可以通過部分從節點結果左乘編碼系數矩陣的逆矩陣，求出掉隊節點的計算結果。然而多項式碼的編碼矩陣作為一個范德蒙矩陣，其條件數隨節點數量增加呈指數級增加，極大地影響了編碼矩陣求逆，導致該方案在實數矩陣的譯碼恢復上數值穩定性很差。針對此問題，文獻[12]通過切比雪夫多項式進一步改進了多項式嵌入結構，大幅提升了譯碼恢復過程的數值精度，使實數域上的編碼分布式矩陣乘法成為可能。此外，文獻[13]設計了一套基于系統型MDS（max distance separable）碼的矩陣-矩陣乘法編碼計算方案，其編碼系數矩陣為隨機系數矩陣，不具備范德蒙矩陣結構，在保證可譯碼性的同時，不會產生譯碼恢復過程的數值穩定性問題。但是，該方案僅進行了理論推導，未進行實驗驗證。

除了關注矩陣乘法，編碼計算還研究了如何利用掉隊節點的部分計算結果[14]計算稀疏性保持[15]等問題。此外，編碼分布式計算也嵌入了邊緣計算架構[16]、多無人機集群[17]等應用場景，為多種單點資源有限的分布式集群性能優化提供了新方案。

本文受系統型MDS 碼編碼計算方案[13]啟發，針對多元LDPC 碼的FHT-QSPA 譯碼，設計了FHT的編碼計算加速方案，提升了多元 LDPC 碼FHT-QSPA 譯碼的效率。具體來看，本文的貢獻有以下三點。

1) 提出了基于系統型MDS 碼的編碼分布式FHT 方案。該方案在主節點上將信道概率建模為矩陣并對其進行切分，再編碼生成冗余子矩陣；其后，將所有子矩陣卸載到從節點并行執行FHT 和IFHT，然后將計算結果傳回主節點并完成最終譯碼。

2) 在子矩陣編碼中，通過隨機系數編碼生成了冗余子矩陣，嵌入了冗余信息，克服了節點掉隊問題；同時，本文證明了隨機系數編碼矩陣能夠以概率1 的可能完成譯碼恢復，且恢復誤差很小。此外，本文方案還保持了FHT 的高效蝶形運算結構。

3) 多個不同參數多元LDPC 碼的耗時對比和譯碼性能分析表明，編碼分布式FHT 方案相比傳統單節點FHT 方案最高加速了約3.8 倍，顯著提升了FHT-QSPA 譯碼效率，且沒有譯碼性能損失。

1 相關工作

定義在有限域GF(q)上的多元LDPC 碼可稱為q-元LDPC 碼，其中q=pr，p為素數，且r〉 1。令α表示有限域GF(q)的本原元，則有限域GF(q)中的所有元素均可用本原元的冪次來表示，即αi,i∈{0,1,…,q-2,-∞}，其中α-∞0。當p=2時，GF(2r)表示二元域的擴展域，其中每一個元素都可以唯一地映射為一個長為r的二元序列。因此，GF(2r)上的多元LDPC碼的碼字符號可以由r個二進制比特來表示。與二元LDPC 碼不同，多元LDPC碼的校驗矩陣中的非零元不是1，而是有限域GF(q)中的q-1個非零元αi,i∈{0,1,…,q-2}，即一個(n,k)q-元LDPC 碼C 可由有限域GF(q)上的校驗矩陣Hm×n=[hi,j]的零空間來定義，其中，hi,j是有限域GF(q)中的元素。合法碼字c和校驗矩陣H的乘積為0，即HTc=0。

多元和積算法（QSPA）（又稱BP 算法）是多元LDPC 碼的經典譯碼算法。在QSPA 譯碼中，一次迭代譯碼可大致分為校驗節點更新，變量節點更新和嘗試譯碼三步[9]。針對QSPA 譯碼校驗節點更新復雜度高的問題，文獻[13]提出了等效變換，改進了每個有限域元素相應概率的計算方式，通過快速哈達瑪變換代替了校驗節點更新中的乘積操作，加速了譯碼算法。令表示變量節點n的值為有限域元素a時校驗節點m被滿足的概率；表示變量節點n的值固定為a時校驗節點m被滿足的概率。集合 N(m)表示與校驗節點m相連的變量節點的集合。FHT-QSPA 譯碼的校驗節點更新具體步驟如下。

1) 等效變換

其中，÷操作表示有限域上的乘法逆操作。

2) 快速哈達瑪變換

3) 逆快速哈達瑪變換

其中，?表示有限域上的乘法操作。

式(1)～式(4)表示FHT-QSPA 校驗節點更新過程，需要根據校驗矩陣中的非零元素對信道概率向量進行兩組變換。若將校驗矩陣所有非零元素對應的各符號信道概率表示為一個矩陣，則FHT-QSPA在校驗節點更新過程的各計算步驟復雜度如表1 所示。復雜度最高的是FHT 及IFHT，為 O(r×2r×N)，其中，r表示擴展域階數，2r表示有限域元素數量，N表示校驗矩陣中非零元素數量。

表1 校驗節點更新過程的各計算步驟復雜度

在上述四步變換中，主要包括有限域上乘法GF(?)和有限域上乘法逆運算GF(÷)，以及實數域上的乘法 R (×)和加法 R(+)。式(1)和式(4)對應的是等效變換和逆等效變換，這兩步在有限域上的乘法和乘法逆運算可以通過LUT（lookup table）來加速。而式(2)和式(3)所代表的FHT 和IFHT 是對浮點數類型的信道概率值進行更新。當碼字有限域增大或碼長增加時，FHT 和IFHT 的計算復雜度也隨之快速增大。

表2 統計了定義在不同有限域以及不同碼長的多元LDPC 碼在單次校驗節點更新中FHT和IFHT 兩步耗時之和占單次校驗節點更新總耗時的比例。由表2 可知，不同碼長的FHT 耗時和IFHT 耗時之和超過了單次校驗節點更新耗時的82%；而隨著碼字有限域增大，其耗時占比超過90%，成為校驗節點更新的主要性能瓶頸。若通過分布式并行加速FHT 和IFHT，則可加速多元LDPC 碼校驗節點更新，從而加速整體譯碼過程。

表2 FHT 和IFHT 耗時占比

2 系統型MDS 碼編碼分布式FHT 方案

正如前文分析，當校驗矩陣中非零元素增加時，式(2)的規?？焖僭龃?。例如，當有限域階數為64，校驗矩陣中非零元素數量為600 時，需要變換的qmn矩陣大小為64 ×600。此時，單節點執行FHT需要進行 6×64×600=230 400次加減法操作。此時，若使用分布式計算，則可以將qmn矩陣劃分為多個子矩陣，并將其卸載到從節點中并行執行，提高FHT 效率。

然而，在分布式計算的實際場景中，各計算節點受計算優先級、網絡通暢程度等因素的影響，可能呈現出不同的計算速度。這樣的節點掉隊現象使分布式并行的加速效果受到部分掉隊節點的拖累，降低整體加速效果。因此，針對FHT 設計一套抗節點掉隊的分布式并行加速算法成為加速多元LDPC碼譯碼的關鍵所在。

2.1 總體流程

設有一個n+1個節點組成的分布式計算系統，其中，主節點W0負責FHT-QSPA 的總體執行、子矩陣編碼和掉隊結果譯碼恢復。首先，主節點按列劃分概率矩陣 [qmn]2r×N得到子矩陣序列B={B1,B2,…,Bk}。其后，主節點對子矩陣序列進行隨機線性組合，得到編碼子矩陣。之后，主節點將計算復雜度最高的FHT 和IFHT 卸載到從節點Wi,i∈{1,2,…,n}中并行執行。其中，k個從節點收到的是未編碼子矩陣，而另外n-k個從節點收到的是編碼后的子矩陣。從節點Wi分別對子矩陣進行FHT，并將計算結果返回給主節點。主節點只需收到最快完成的k個子矩陣變換結果便能恢復其他掉隊子矩陣變換結果，從而克服了掉隊節點對總體計算速度的拖累。方案整體流程如算法1 所示。

算法1基于系統MDS 碼的編碼分布式FHT方案

圖1 展示了由5 個從節點組成的編碼分布式FHT 方案，其中前3 個節點計算未編碼子矩陣，后2 個節點計算編碼子矩陣。主節點將FHT 卸載到各個從節點上，主節點上僅需要進行編碼和譯碼操作。多個從節點收到了尺寸更小的子矩陣，并行執行FHT，實現分布式并行加速。圖1 中×所示節點為掉隊節點，而主節點可基于其他節點結果恢復掉隊節點的計算結果。

圖1 編碼分布式FHT 方案架構

下面將圍繞主節點編碼環節、可譯碼性證明、譯碼環節和從節點FHT 計算來展開分析。

2.2 編碼環節

首先，本節詳細描述了系統型MDS 碼編碼分布式FHT 方案的子矩陣編碼思路。主節點按列切分概率矩陣得到子矩陣序列B={B1,B2,…,Bk}。

此時，其上半部分I為單位矩陣，而下半部分為標準高斯分布 N(0,1)上采樣的隨機數子矩陣PB。因此，通過生成矩陣和未編碼子矩陣序列的乘法，即可求出分配給所有從節點的子矩陣序列B

PB中的每行確定了一組隨機系數，對未編碼子矩陣進行線性組合，得到對應的編碼子矩陣。即=bi,1B1+…+bi,kBk,i∈{k+1,k+2,…,n}。

此外，特別值得指出的是，在式(6)中，子矩陣Bi被視為標量，生成矩陣GB中對應的單位矩陣I維度也設定為矩陣劃分后的子矩陣數量，即k×k。然而，實際情況中，每個子矩陣Bi的維度是。因此，編碼環節僅需要針對未編碼子矩陣進行隨機系數標量和子矩陣的乘法，之后再進行線性組合，即可求出對應的編碼子矩陣。

2.3 可譯碼性證明

本節分析系統型MDS 碼編碼分布式FHT 方案的可譯碼性。通過對其編碼矩陣行列式的分析，證明其子方陣行列式以概率1 的可能是一個非零多項式，從而證明該方案能夠以概率1 的可能完成譯碼。

引理1[18]若矩陣G的每一個子方陣都是非奇異矩陣時，該矩陣可以成為一個系統型MDS 碼的編碼矩陣。

引理2若子矩陣PB中的元素都是在標準高斯分布中 N(0,1)獨立同分布地采樣，子矩陣PB的每一個子方陣都以概率1 的可能是非奇異矩陣。

證明首先通過數學歸納法證明任意r×r階子矩陣(r≤(n-k))的行列式都是非零多項式。當r=1時，假設顯然成立。接著，假設每一個(r-1)×(r-1)階子矩陣的行列式都是非零多項式。此時，任意一個r×r階子矩陣可寫為

此矩陣的行列式可以寫為

在引理1 和引理2 的基礎上，本文給出下列定理。

定理1若編碼計算方案由生成矩陣G確定，PB為矩陣G的子矩陣，其大小為(n-k)×k，且PB中的元素均為標準高斯分布 N(0,1)中的獨立同分布采樣得到。此時，該方案給定了一個系統型的MDS 碼編碼計算方案，當主節點收到n個子矩陣變換結果中的任意k個時，即可以概率1 的可能譯碼恢復掉隊節點對應的子矩陣變換結果。

在定理1 所確定的系統型MDS 碼編碼計算方案中，從節點數量為n個，其中有k個節點執行未編碼子任務，有n-k個節點執行編碼子任務。此時，該方案的恢復閾值為n-k，即該方案最多可以容忍n-k個節點掉隊或失效。

2.4 譯碼環節

在n個從節點和一個主節點組成的分布式計算系統中，簡便起見，可令前k個節點為未編碼子任務節點，后n-k個節點為編碼子任務節點。設從節點索引集合為i∈{1,2,…,k,k+1,…,n}，則2 種節點對應索引集合可規定為Iu={i1,i2,…,ik}和Ic={ik+1,ik+2,…,in}。

由定理1 可知，當主節點收到最快完成的k個子任務結果時即可完成計算。此時，主節點根據接收到的未編碼子任務計算結果數量nu來判斷是否需要進行譯碼。最好情況下，前k個未編碼子任務都很快完成了計算任務，并將結果返回給主節點，即nu=k。此時，由于主節點收到了所有想要的未編碼子任務計算結果，并不需要進行譯碼恢復，可直接進行后續計算任務。

而當nu〈k時，即未編碼節點出現了掉隊情況，則主節點需要收到至少k-nu個編碼子任務計算結果來恢復未編碼子任務的計算結果。設主節點收到nc個編碼子任務節點結算結果，2 種節點對應的索引集合分為Su={u1,u2,…,unu},Su?Iu；Sc={c1,c2,…,cnc},Sc?Ic，且nc+nu=k。此時，主節點已經收到了足夠數量的子任務結果，來恢復掉隊節點子任務結果Ss=IuSu，完成譯碼恢復。

于是，可以得到下列由已知的編碼子任務計算結果、未編碼子任務結果、掉隊未編碼子任務結果確定的方程組

因此，掉隊的未編碼子任務結果可以通過求解上述方程組來獲得。此時方程組(9)中的未知數為FHT(Bs),s∈Ss，未知數的數量ns≤nc，即掉隊的未編碼子任務的數量小于或等于主節點收到的編碼子任務數量。此外，由定理1 可知，若編碼矩陣中的系數為高斯分布中獨立同分布采樣得到，則滿足任意r階子矩陣均是非奇異矩陣，即任意r階子矩陣均為可逆矩陣。根據上述兩點，對方程組(9)進行求解即可得到掉隊的未編碼子任務結果FHT(Bs),s∈Ss。

例如圖1 所示的編碼分布式FHT 方案，由5 個從節點組成。其中未編碼子任務節點為Iu={1,2,3},Ic={4,5}。若假設主節點收到最快完成計算任務的從節點集合為Su={2},Sc={4,5}，則1 號節點和3 號節點所負責的未編碼子任務結果出現了掉隊情況，需要通過收到的編碼子任務來求解，即求解下列齊次線性方程組，便可求出對應掉隊任務結果。

2.5 從節點FHT 計算

前文主要闡述了FHT 的編碼分布式并行加速方案，本節圍繞FHT 的計算方式，闡述了編碼分布式FHT 方案在從節點上的計算任務。

FHT 本身可以通過蝶形運算的形式來表示，圖2展示了一個4 維向量通過蝶形運算完成FHT 的過程?？傮w來看，FHT 的復雜度可以表示為 O(r×2r×N)，其中2r×N表示了待變換矩陣的規模。而經過前文所述的編碼環節，每個子矩陣的大小都變為了。因此，從節點上的計算復雜度降為。

圖2 FHT 蝶形運算計算順序

3 實驗驗證

本節針對前述系統型MDS 碼編碼分布式FHT方案進行了實驗驗證，分析了編碼環節、譯碼環節以及從節點FHT 的復雜度，并在AWS EC2 計算集群上驗證了所提方案的有效性。首先，簡要介紹了實驗環境設置和實驗參數設置；其次，針對系統型MDS 碼編碼分布式FHT 方案的編碼環節、譯碼環節以及從節點FHT 進行了復雜度分析；之后，以目前北斗導航系統中采用的64 元200 碼長的多元LDPC 碼為基礎[19-20]，分析了類似參數的其他多元LDPC 碼字的譯碼加速效果。此外，還與FHT-QSPA進行了譯碼性能對比，證明了本文方案可以在保證相同的譯碼精度的情況下，通過分布式并行計算，顯著加速FHT-QSPA 譯碼。

3.1 實驗環境設置

為驗證本文所提編碼分布式FHT 方案的譯碼加速性能，本節基于AWS EC2 環境搭建了分布式計算集群，并基于MPI 消息傳遞庫開發了編碼分布式FHT 方案。測試碼字上以北斗系統中使用的64 元(200,100)LDPC 碼為基礎，并拓展了不同的有限域階數和不同的碼長。有限域階數包括GF(16)、GF(32)、GF(64)、GF(128)和GF(256)。碼長則包括200、400、800、1 600 和2 000。在EC2 實例的選擇上，本文選擇了t2.micro 類型的實例，其具體配置為1 vCPU 和1 GB 內存。在此基礎上，測試了上述碼字的FHT 環節和IFHT 環節經系統型MDS 碼編碼分布式FHT 方案后取得的加速效果。所有的耗時數據均為100個碼字完成譯碼或達到最大迭代次數后單次校驗節點更新中各個計算步驟耗時數據的均值。

3.2 復雜度分析

本文所提編碼分布式FHT 方案的主要計算步驟包括編碼環節和譯碼環節，以及從節點FHT。編碼分布式FHT 方案計算復雜度如表3 所示。

表3 編碼分布式FHT 方案計算復雜度

3.2.1 編碼環節復雜度對比

在編碼分布式FHT 方案的編碼環節中，主節點需要對劃分好的子矩陣進行隨機線性組合，即每個子矩陣先乘以一個隨機系數再進行相加。因此，編碼環節的復雜度由冗余節點數量和子矩陣大小構成。k表示從節點中執行未編碼子任務的節點數量，反映了加速倍數。k越大，則加速倍數越大，對應n-k越小，掉隊節點抑制能力也越小，此時編碼復雜度越低。因此，本文方案的編碼環節復雜度和掉隊節點抑制能力存在一個折中。

3.2.2 譯碼環節復雜度對比

此外，若未編碼從節點不掉隊，本文方案不需要執行譯碼；若未編碼從節點出現掉隊，則譯碼環節需要求解由ns個方程組成的齊次線性方程組。相應的復雜度主要由未編碼子任務中的掉隊節點數量ns和子矩陣大小構成。

多項式碼編碼矩陣乘法方案[11]由于其特殊的冪次多項式編碼嵌入結構，使多項式碼方案在浮點型數據的譯碼恢復精度很差。而在FHT 中，多項式碼方案隨著節點數量增加已不能正確譯碼。文獻[12]和后文恢復誤差分析也說明了這一點。但文獻[12]所提的正交多項式碼編碼矩陣乘法的譯碼復雜度為O(N×2r×k2)，仍然高于本文方案的。

3.2.3 從節點計算環節復雜度對比

另外，從節點上執行的是規模更小的FHT，其復雜度是單節點執行的，并且多個從節點并行執行可以加速FHT。然而，與文獻[11]和文獻[12]所提出的編碼矩陣乘法方案相比，2 種方案將待變換矩陣和FHT 系數矩陣均進行了編碼，破壞了FHT系數矩陣的蝶形運算結構，使從節點上FHT 由蝶形運算退化為矩陣乘法，其計算復雜度則由大幅增加為。而本文方案優化了編碼冗余嵌入方式，在從節點上維持了FHT 的高效蝶形運算結構，降低了從節點上的計算復雜度。

3.3 數值穩定性

文獻[11]中的多項式碼編碼矩陣乘法方案，由于其編碼生成矩陣內生的范德蒙矩陣結構，其矩陣條件數隨著從節點數量增加而快速增加，使編碼系數矩陣求逆的數值穩定性很差，極大地影響了浮點型數據的譯碼恢復，文獻[12]的實驗同樣反映了這一點。

針對FHT-QSPA 的FHT 和IFHT，其計算的是多元符號所對應的各個有限域元素的概率值。而這意味著FHT-QSPA 對編碼分布式算法造成的譯碼恢復誤差更加敏感，一旦譯碼恢復數值精度較差，必然會影響后續的譯碼性能。所以，本文采取的恢復誤差計算式為

其中，[Qmn]表示單節點自行完成FHT 的結果，表示采用編碼分布式計算得到的FHT 結果。本文對比了所提系統MDS 碼的編碼分布式FHT方案和文獻[11]中提出的多項式碼編碼矩陣乘法方案以及文獻[12]中提出的正交多項式編碼矩陣乘法方案的最大恢復誤差，統計結果如表4 所示。

表4 3 種方案最大恢復誤差

從表4 可以看出，3 種編碼分布式方案的數值精度隨著從節點數量n的增加都呈現增加的趨勢。然而正如前文分析，多項式碼方案的數值穩定性隨著節點數量增加而急劇惡化，當從節點超過5 個時，其最大恢復誤差已經大于0.01，而這樣的誤差無疑會對FHT-QSPA 的概率更新產生極大影響；而當節點數繼續增大時，多項式碼方案已不能正確完成譯碼恢復。對比來看，正交多項式碼方案著重改進了多項式碼方案的數值穩定性，在20 個從節點的分布式設置中仍舊保持了1×10-13級別的恢復誤差。而本文所提的基于系統型MDS 碼的編碼分布式FHT 方案的最大恢復誤差是三者中最小的。

3.4 加速效果

在本文方案中，主要的設計參數有從節點的總數n、未編碼從節點的數量k、節點的掉隊程度λ和掉隊節點數量s。其中，從節點總數n比較容易理解，n越大，分布式并行加速效果越好。而參數k則表示主節點在n個從節點中選擇前k個節點作為未編碼節點，分配未編碼子矩陣；剩下的n-k個節點則作為冗余節點，分配編碼子矩陣。因此本文所提編碼分布式FHT 方案所能容忍的掉隊節點數量等于n-k，而對FHT 和IFHT 的理論加速倍數為k。換言之，本文使用冗余節點換取了分布式方案中對掉隊節點的容忍。

此時，節點的掉隊程度或計算速度可以由主節點進行監控，當節點計算速度正?；虻絷牫潭容^低時，k可以設置得較大，換取較好的加速效果；而當節點繁忙程度增加，節點計算速度下降時，k則可設得較小，使n-k較大，換取較好的掉隊抑制效果。

3.4.1 從節點數n對加速效果的影響

首先，分析系統型MDS 碼編碼分布式并行加速的FHT 和IFHT 在執行耗時上的效果。在碼字選擇上，統計了碼長為200 的64 元LDPC 碼在校驗節點更新中FHT 和IFHT 的耗時，并在分布式環境下進行了對應的耗時分析，具體結果如圖3 所示。

圖3 200 碼長的64 元LDPC 碼編碼分布式FHT 和IFHT 耗時

圖3 中共有6 組實驗結果。第一組數據表示由單節點自行計算FHT 和IFHT 的總耗時，200 碼長的64元LDPC 碼在單次校驗節點更新過程中，FHT 和IFHT總耗時約為191 ms。第二組數據(n=5)中的白色部分表示使用5個從節點對FHT和IFHT進行分布式計算，其耗時總計約42 ms，加速倍數約為4.5 倍；而灰色柱則表示使用編碼分布式FHT 方案對FHT 和IFHT 進行加速，其耗時約為49 ms，加速倍數約為3.9 倍。因此，編碼分布式FHT 方案通過設置冗余節點，雖造成分布式并行加速倍數稍有降低，但克服了掉隊節點的拖累，使分布式FHT 獲得了穩定的加速。

3.4.2 掉隊程度λ對加速效果的影響

圖3 的第二組數據的白色部分表示分布式并行實驗，即5 個從節點中未設置掉隊節點，此時分布式加速倍數接近于理想加速倍數5 倍。但是當節點出現不同程度的掉隊時，其加速性能無疑會劣化。后4 組數據中的白色部分反映了當5 個節點中有1 個節點出現掉隊情況時，分布式執行的FHT 和IFHT 總耗時。其中，λ表示節點的掉隊程度，即掉隊節點的計算速度退化為未掉隊節點的。4 組數據中的白色部分反映了當節點掉隊程度加深，分布式計算的實際加速效果不斷退化，甚至超過未采用分布式計算的耗時(λ=5)。

加入系統型MDS 編碼分布式計算后的實驗數據繪制如圖3 后4 組數據中的灰色部分所示。在編碼分布式FHT 方案中冗余節點數量設置為1，因此該方案可以對抗5 個節點中任意1 個節點的掉隊，而該方案的理論加速性能為4 倍。與5 個節點純分布式計算相比，1 個冗余節點的編碼分布式FHT 方案相比純分布式方案理論加速性能略弱，總耗時約為50 ms。但是隨著節點掉隊程度的加深，編碼分布式FHT 方案的加速性能不受掉隊節點的影響，穩定在50 ms 左右。因此，編碼分布式FHT 方案能夠通過冗余節點設計抵抗掉隊節點的影響，且節點掉隊程度加深對整體加速性能沒有劣化。

3.4.3 掉隊節點數量s對加速效果的影響

由于編碼分布式FHT 方案中通過設置冗余節點來克服節點掉隊，而圖3 反映了節點掉隊程度的加深對并行算法的加速效果有很大的影響。因此，圖4 對掉隊節點數量進行了實驗，其中從節點數量為n=10，冗余節點數量為n-k=5，節點掉隊程度為λ=2，碼字參數與圖3 實驗一致。編碼分布式FHT 方案可以在冗余節點數量范圍內容忍不同數量的掉隊節點，而不增加FHT 和IFHT 耗時，即基于系統型(n,k)MDS碼的編碼分布式FHT 方案能夠抵抗任意小于或等于n-k個節點掉隊。當節點掉隊數量超過了冗余節點數量時，此時整個分布式系統中的掉隊情況更加嚴重。例如，當10 個從節點中有6 個節點掉隊時，主節點在收到4 個從節點結果的基礎上至多還需要等待任意1 個從節點的計算結果便可完成譯碼恢復。因此，當掉隊節點數量超過冗余節點數量時，主節點可以在下一次迭代更新中進一步增大冗余節點數量，以實現更好的抗節點掉隊效果；反之，當節點掉隊數量小于冗余節點數量時，主節點也可在下一次迭代更新中降低冗余節點數量，達到更好的并行加速效果。

圖4 不同掉隊節點數量s 對編碼FHT 和IFHT 的耗時影響

3.5 不同參數NB-LDPC 碼加速效果

根據前文分析，編碼分布式FHT 加速方案不受節點掉隊程度影響，實現了穩定加速。因此，本文繼續使用5 個從節點，其中有1 個冗余節點的編碼分布式參數設定，分析不同碼長和不同有限域階數上的加速效果。選擇掉隊節點數量為1 個，節點掉隊程度λ為2。在不同碼長的64 元LDPC 碼上，編碼分布式方案對FHT和IFHT加速效果如圖5所示。當碼長從200 增長到2 000，FHT+IFHT 的總耗時從191 ms 快速增加到了2 105 ms。而編碼分布式FHT+IFHT 方案能夠穩定地并行加速FHT 和IFHT，提升兩者計算效率。

圖5 不同碼長的64 元LDPC 碼FHT 和IFHT 耗時

接下來，固定碼長為200，將有限域階數從16增加到256 時，對應的編碼分布式FHT 加速方案效果如圖6 所示。隨著有限域階數的增加，FHT+IFHT的總耗時從49 ms 增長到866 ms。因此，如圖5 和圖6 中灰色數據所示，特別是針對碼長變長和有限域變大的情況，編碼分布式FHT 方案大幅節約了FHT 和IFHT 計算時間，加速了校驗節點更新，從而加速了整體FHT-QSPA 譯碼過程。

圖6 200 碼長的不同有限域階數LDPC 碼FHT 和IFHT 耗時

3.6 譯碼性能對比

本節選用了碼長為800 的16 元LDPC 碼作為測試碼字。首先通過隨機方法得到了碼字生成矩陣，之后對隨機生成的信息進行編碼，并進行BPSK調制，其后經過AWGN 信道加噪，最后分別使用FHT-QSPA 和基于編碼分布式方案的FHT-QSPA 進行譯碼，分析其譯碼性能。圖7 給出了2 種算法的譯碼性能曲線。從圖7 可以看出，基于編碼分布式FHT 方案的譯碼算法的譯碼性能相較于原始算法沒有損失。

圖7 FHT-QSPA 和編碼FHT-QSPA 的譯碼性能曲線

除此之外，本文還進一步分析了FHT-QSPA 和編碼分布式FHT-QSPA在單次校驗節點迭代中FHT和IFHT 的耗時情況，如表5 所示。其中編碼分布式FHT 采用了5 個從節點，其中有1 個冗余節點的分布式設置，而掉隊節點數量設置為1 個。從表5 可以看出，通過編碼分布式的改造，使FHT 和IFHT 這2 個耗時最長環節得到了穩定加速。

表5 2 種譯碼算法單次迭代耗時

4 結束語

本文提出了一種基于系統型MDS 碼的編碼分布式FHT 方案。該方案在主節點上將信道概率建模為矩陣并對其進行切分，再編碼生成冗余子矩陣；其后，主節點將所有子矩陣卸載到從節點并行執行FHT 和IFHT，然后從節點將計算結果傳回主節點完成最終譯碼。通過設置不同的冗余節點數量，該方案可以在加速性能和抗節點掉隊性能之間取得折中。此外，本文證明了所提系統型MDS 碼編碼計算方案能夠以概率1 的可能完成掉隊任務結果的譯碼恢復，而譯碼過程僅需對齊次線性方程組進行求解。

總體來看，本文方案的編譯碼環節的復雜度均較低，這使編碼分布式FHT 加速方案針對FHT 和IFHT 均獲得了接近于k倍的加速。將本文方案的譯碼恢復誤差與其他編碼矩陣乘法方案進行對比，驗證了本文方案優秀的數值穩定性。而不同有限域和碼長的多元LDPC 碼譯碼耗時分析，確認了本文方案的加速效果。譯碼性能曲線對比表明了本文方案可以在不損失譯碼性能的情況下，穩定地加速譯碼過程。

另外，本文方案還適于其他變換，例如FFT 等。通過對待變換矩陣進行編碼分布式加速，可以同時實現較高的抗節點掉隊性能和保持高效變換計算結構。后續本文將繼續研究該方案在其他變換上的應用，拓展系統型MDS 碼編碼分布式加速方案的應用場景，提高計算效率。