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

劉銳，黎勇

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044）

0 引言

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

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

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

但是，多節(jié)點(diǎn)分布式系統(tǒng)中某些節(jié)點(diǎn)可能出現(xiàn)通信繁忙、資源搶占、節(jié)點(diǎn)失效等情況，從而影響整體任務(wù)。這些節(jié)點(diǎn)被稱為掉隊(duì)節(jié)點(diǎn)。為了克服節(jié)點(diǎn)掉隊(duì)的問題，傳統(tǒng)的副本策略使用多個(gè)節(jié)點(diǎn)負(fù)責(zé)相同的任務(wù)，只要任意節(jié)點(diǎn)完成當(dāng)前任務(wù)即可繼續(xù)后續(xù)計(jì)算。然而，副本策略中成倍增加的資源消耗使其在資源利用率方面表現(xiàn)欠佳。

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

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

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

本文受系統(tǒng)型MDS 碼編碼計(jì)算方案[13]啟發(fā)，針對(duì)多元LDPC 碼的FHT-QSPA 譯碼，設(shè)計(jì)了FHT的編碼計(jì)算加速方案，提升了多元 LDPC 碼FHT-QSPA 譯碼的效率。具體來看，本文的貢獻(xiàn)有以下三點(diǎn)。

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

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

3) 多個(gè)不同參數(shù)多元LDPC 碼的耗時(shí)對(duì)比和譯碼性能分析表明，編碼分布式FHT 方案相比傳統(tǒng)單節(jié)點(diǎn)FHT 方案最高加速了約3.8 倍，顯著提升了FHT-QSPA 譯碼效率，且沒有譯碼性能損失。

1 相關(guān)工作

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

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

1) 等效變換

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

2) 快速哈達(dá)瑪變換

3) 逆快速哈達(dá)瑪變換

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

式(1)～式(4)表示FHT-QSPA 校驗(yàn)節(jié)點(diǎn)更新過程，需要根據(jù)校驗(yàn)矩陣中的非零元素對(duì)信道概率向量進(jìn)行兩組變換。若將校驗(yàn)矩陣所有非零元素對(duì)應(yīng)的各符號(hào)信道概率表示為一個(gè)矩陣，則FHT-QSPA在校驗(yàn)節(jié)點(diǎn)更新過程的各計(jì)算步驟復(fù)雜度如表1 所示。復(fù)雜度最高的是FHT 及IFHT，為 O(r×2r×N)，其中，r表示擴(kuò)展域階數(shù)，2r表示有限域元素?cái)?shù)量，N表示校驗(yàn)矩陣中非零元素?cái)?shù)量。

表1 校驗(yàn)節(jié)點(diǎn)更新過程的各計(jì)算步驟復(fù)雜度

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

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

表2 FHT 和IFHT 耗時(shí)占比

2 系統(tǒng)型MDS 碼編碼分布式FHT 方案

正如前文分析，當(dāng)校驗(yàn)矩陣中非零元素增加時(shí)，式(2)的規(guī)模快速增大。例如，當(dāng)有限域階數(shù)為64，校驗(yàn)矩陣中非零元素?cái)?shù)量為600 時(shí)，需要變換的qmn矩陣大小為64 ×600。此時(shí)，單節(jié)點(diǎn)執(zhí)行FHT需要進(jìn)行 6×64×600=230 400次加減法操作。此時(shí)，若使用分布式計(jì)算，則可以將qmn矩陣劃分為多個(gè)子矩陣，并將其卸載到從節(jié)點(diǎn)中并行執(zhí)行，提高FHT 效率。

然而，在分布式計(jì)算的實(shí)際場(chǎng)景中，各計(jì)算節(jié)點(diǎn)受計(jì)算優(yōu)先級(jí)、網(wǎng)絡(luò)通暢程度等因素的影響，可能呈現(xiàn)出不同的計(jì)算速度。這樣的節(jié)點(diǎn)掉隊(duì)現(xiàn)象使分布式并行的加速效果受到部分掉隊(duì)節(jié)點(diǎn)的拖累，降低整體加速效果。因此，針對(duì)FHT 設(shè)計(jì)一套抗節(jié)點(diǎn)掉隊(duì)的分布式并行加速算法成為加速多元LDPC碼譯碼的關(guān)鍵所在。

2.1 總體流程

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

算法1基于系統(tǒng)MDS 碼的編碼分布式FHT方案

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

圖1 編碼分布式FHT 方案架構(gòu)

下面將圍繞主節(jié)點(diǎn)編碼環(huán)節(jié)、可譯碼性證明、譯碼環(huán)節(jié)和從節(jié)點(diǎn)FHT 計(jì)算來展開分析。

2.2 編碼環(huán)節(jié)

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

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

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

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

2.3 可譯碼性證明

本節(jié)分析系統(tǒng)型MDS 碼編碼分布式FHT 方案的可譯碼性。通過對(duì)其編碼矩陣行列式的分析，證明其子方陣行列式以概率1 的可能是一個(gè)非零多項(xiàng)式，從而證明該方案能夠以概率1 的可能完成譯碼。

引理1[18]若矩陣G的每一個(gè)子方陣都是非奇異矩陣時(shí)，該矩陣可以成為一個(gè)系統(tǒng)型MDS 碼的編碼矩陣。

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

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

此矩陣的行列式可以寫為

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

定理1若編碼計(jì)算方案由生成矩陣G確定，PB為矩陣G的子矩陣，其大小為(n-k)×k，且PB中的元素均為標(biāo)準(zhǔn)高斯分布 N(0,1)中的獨(dú)立同分布采樣得到。此時(shí)，該方案給定了一個(gè)系統(tǒng)型的MDS 碼編碼計(jì)算方案，當(dāng)主節(jié)點(diǎn)收到n個(gè)子矩陣變換結(jié)果中的任意k個(gè)時(shí)，即可以概率1 的可能譯碼恢復(fù)掉隊(duì)節(jié)點(diǎn)對(duì)應(yīng)的子矩陣變換結(jié)果。

在定理1 所確定的系統(tǒng)型MDS 碼編碼計(jì)算方案中，從節(jié)點(diǎn)數(shù)量為n個(gè)，其中有k個(gè)節(jié)點(diǎn)執(zhí)行未編碼子任務(wù)，有n-k個(gè)節(jié)點(diǎn)執(zhí)行編碼子任務(wù)。此時(shí)，該方案的恢復(fù)閾值為n-k，即該方案最多可以容忍n-k個(gè)節(jié)點(diǎn)掉隊(duì)或失效。

2.4 譯碼環(huán)節(jié)

在n個(gè)從節(jié)點(diǎn)和一個(gè)主節(jié)點(diǎn)組成的分布式計(jì)算系統(tǒng)中，簡(jiǎn)便起見，可令前k個(gè)節(jié)點(diǎn)為未編碼子任務(wù)節(jié)點(diǎn)，后n-k個(gè)節(jié)點(diǎn)為編碼子任務(wù)節(jié)點(diǎn)。設(shè)從節(jié)點(diǎn)索引集合為i∈{1,2,…,k,k+1,…,n}，則2 種節(jié)點(diǎn)對(duì)應(yīng)索引集合可規(guī)定為Iu={i1,i2,…,ik}和Ic={ik+1,ik+2,…,in}。

由定理1 可知，當(dāng)主節(jié)點(diǎn)收到最快完成的k個(gè)子任務(wù)結(jié)果時(shí)即可完成計(jì)算。此時(shí)，主節(jié)點(diǎn)根據(jù)接收到的未編碼子任務(wù)計(jì)算結(jié)果數(shù)量nu來判斷是否需要進(jìn)行譯碼。最好情況下，前k個(gè)未編碼子任務(wù)都很快完成了計(jì)算任務(wù)，并將結(jié)果返回給主節(jié)點(diǎn)，即nu=k。此時(shí)，由于主節(jié)點(diǎn)收到了所有想要的未編碼子任務(wù)計(jì)算結(jié)果，并不需要進(jìn)行譯碼恢復(fù)，可直接進(jìn)行后續(xù)計(jì)算任務(wù)。

而當(dāng)nu〈k時(shí)，即未編碼節(jié)點(diǎn)出現(xiàn)了掉隊(duì)情況，則主節(jié)點(diǎn)需要收到至少k-nu個(gè)編碼子任務(wù)計(jì)算結(jié)果來恢復(fù)未編碼子任務(wù)的計(jì)算結(jié)果。設(shè)主節(jié)點(diǎn)收到nc個(gè)編碼子任務(wù)節(jié)點(diǎn)結(jié)算結(jié)果，2 種節(jié)點(diǎn)對(duì)應(yīng)的索引集合分為Su={u1,u2,…,unu},Su?Iu；Sc={c1,c2,…,cnc},Sc?Ic，且nc+nu=k。此時(shí)，主節(jié)點(diǎn)已經(jīng)收到了足夠數(shù)量的子任務(wù)結(jié)果，來恢復(fù)掉隊(duì)節(jié)點(diǎn)子任務(wù)結(jié)果Ss=IuSu，完成譯碼恢復(fù)。

于是，可以得到下列由已知的編碼子任務(wù)計(jì)算結(jié)果、未編碼子任務(wù)結(jié)果、掉隊(duì)未編碼子任務(wù)結(jié)果確定的方程組

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

例如圖1 所示的編碼分布式FHT 方案，由5 個(gè)從節(jié)點(diǎn)組成。其中未編碼子任務(wù)節(jié)點(diǎn)為Iu={1,2,3},Ic={4,5}。若假設(shè)主節(jié)點(diǎn)收到最快完成計(jì)算任務(wù)的從節(jié)點(diǎn)集合為Su={2},Sc={4,5}，則1 號(hào)節(jié)點(diǎn)和3 號(hào)節(jié)點(diǎn)所負(fù)責(zé)的未編碼子任務(wù)結(jié)果出現(xiàn)了掉隊(duì)情況，需要通過收到的編碼子任務(wù)來求解，即求解下列齊次線性方程組，便可求出對(duì)應(yīng)掉隊(duì)任務(wù)結(jié)果。

2.5 從節(jié)點(diǎn)FHT 計(jì)算

前文主要闡述了FHT 的編碼分布式并行加速方案，本節(jié)圍繞FHT 的計(jì)算方式，闡述了編碼分布式FHT 方案在從節(jié)點(diǎn)上的計(jì)算任務(wù)。

FHT 本身可以通過蝶形運(yùn)算的形式來表示，圖2展示了一個(gè)4 維向量通過蝶形運(yùn)算完成FHT 的過程?？傮w來看，F(xiàn)HT 的復(fù)雜度可以表示為 O(r×2r×N)，其中2r×N表示了待變換矩陣的規(guī)模。而經(jīng)過前文所述的編碼環(huán)節(jié)，每個(gè)子矩陣的大小都變?yōu)榱?。因此，從?jié)點(diǎn)上的計(jì)算復(fù)雜度降為。

圖2 FHT 蝶形運(yùn)算計(jì)算順序

3 實(shí)驗(yàn)驗(yàn)證

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

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

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

3.2 復(fù)雜度分析

本文所提編碼分布式FHT 方案的主要計(jì)算步驟包括編碼環(huán)節(jié)和譯碼環(huán)節(jié)，以及從節(jié)點(diǎn)FHT。編碼分布式FHT 方案計(jì)算復(fù)雜度如表3 所示。

表3 編碼分布式FHT 方案計(jì)算復(fù)雜度

3.2.1 編碼環(huán)節(jié)復(fù)雜度對(duì)比

在編碼分布式FHT 方案的編碼環(huán)節(jié)中，主節(jié)點(diǎn)需要對(duì)劃分好的子矩陣進(jìn)行隨機(jī)線性組合，即每個(gè)子矩陣先乘以一個(gè)隨機(jī)系數(shù)再進(jìn)行相加。因此，編碼環(huán)節(jié)的復(fù)雜度由冗余節(jié)點(diǎn)數(shù)量和子矩陣大小構(gòu)成。k表示從節(jié)點(diǎn)中執(zhí)行未編碼子任務(wù)的節(jié)點(diǎn)數(shù)量，反映了加速倍數(shù)。k越大，則加速倍數(shù)越大，對(duì)應(yīng)n-k越小，掉隊(duì)節(jié)點(diǎn)抑制能力也越小，此時(shí)編碼復(fù)雜度越低。因此，本文方案的編碼環(huán)節(jié)復(fù)雜度和掉隊(duì)節(jié)點(diǎn)抑制能力存在一個(gè)折中。

3.2.2 譯碼環(huán)節(jié)復(fù)雜度對(duì)比

此外，若未編碼從節(jié)點(diǎn)不掉隊(duì)，本文方案不需要執(zhí)行譯碼；若未編碼從節(jié)點(diǎn)出現(xiàn)掉隊(duì)，則譯碼環(huán)節(jié)需要求解由ns個(gè)方程組成的齊次線性方程組。相應(yīng)的復(fù)雜度主要由未編碼子任務(wù)中的掉隊(duì)節(jié)點(diǎn)數(shù)量ns和子矩陣大小構(gòu)成。

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

3.2.3 從節(jié)點(diǎn)計(jì)算環(huán)節(jié)復(fù)雜度對(duì)比

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

3.3 數(shù)值穩(wěn)定性

文獻(xiàn)[11]中的多項(xiàng)式碼編碼矩陣乘法方案，由于其編碼生成矩陣內(nèi)生的范德蒙矩陣結(jié)構(gòu)，其矩陣條件數(shù)隨著從節(jié)點(diǎn)數(shù)量增加而快速增加，使編碼系數(shù)矩陣求逆的數(shù)值穩(wěn)定性很差，極大地影響了浮點(diǎn)型數(shù)據(jù)的譯碼恢復(fù)，文獻(xiàn)[12]的實(shí)驗(yàn)同樣反映了這一點(diǎn)。

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

其中，[Qmn]表示單節(jié)點(diǎn)自行完成FHT 的結(jié)果，表示采用編碼分布式計(jì)算得到的FHT 結(jié)果。本文對(duì)比了所提系統(tǒng)MDS 碼的編碼分布式FHT方案和文獻(xiàn)[11]中提出的多項(xiàng)式碼編碼矩陣乘法方案以及文獻(xiàn)[12]中提出的正交多項(xiàng)式編碼矩陣乘法方案的最大恢復(fù)誤差，統(tǒng)計(jì)結(jié)果如表4 所示。

表4 3 種方案最大恢復(fù)誤差

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

3.4 加速效果

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

此時(shí)，節(jié)點(diǎn)的掉隊(duì)程度或計(jì)算速度可以由主節(jié)點(diǎn)進(jìn)行監(jiān)控，當(dāng)節(jié)點(diǎn)計(jì)算速度正?；虻絷?duì)程度較低時(shí)，k可以設(shè)置得較大，換取較好的加速效果；而當(dāng)節(jié)點(diǎn)繁忙程度增加，節(jié)點(diǎn)計(jì)算速度下降時(shí)，k則可設(shè)得較小，使n-k較大，換取較好的掉隊(duì)抑制效果。

3.4.1 從節(jié)點(diǎn)數(shù)n對(duì)加速效果的影響

首先，分析系統(tǒng)型MDS 碼編碼分布式并行加速的FHT 和IFHT 在執(zhí)行耗時(shí)上的效果。在碼字選擇上，統(tǒng)計(jì)了碼長(zhǎng)為200 的64 元LDPC 碼在校驗(yàn)節(jié)點(diǎn)更新中FHT 和IFHT 的耗時(shí)，并在分布式環(huán)境下進(jìn)行了對(duì)應(yīng)的耗時(shí)分析，具體結(jié)果如圖3 所示。

圖3 200 碼長(zhǎng)的64 元LDPC 碼編碼分布式FHT 和IFHT 耗時(shí)

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

3.4.2 掉隊(duì)程度λ對(duì)加速效果的影響

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

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

3.4.3 掉隊(duì)節(jié)點(diǎn)數(shù)量s對(duì)加速效果的影響

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

圖4 不同掉隊(duì)節(jié)點(diǎn)數(shù)量s 對(duì)編碼FHT 和IFHT 的耗時(shí)影響

3.5 不同參數(shù)NB-LDPC 碼加速效果

根據(jù)前文分析，編碼分布式FHT 加速方案不受節(jié)點(diǎn)掉隊(duì)程度影響，實(shí)現(xiàn)了穩(wěn)定加速。因此，本文繼續(xù)使用5 個(gè)從節(jié)點(diǎn)，其中有1 個(gè)冗余節(jié)點(diǎn)的編碼分布式參數(shù)設(shè)定，分析不同碼長(zhǎng)和不同有限域階數(shù)上的加速效果。選擇掉隊(duì)節(jié)點(diǎn)數(shù)量為1 個(gè)，節(jié)點(diǎn)掉隊(duì)程度λ為2。在不同碼長(zhǎng)的64 元LDPC 碼上，編碼分布式方案對(duì)FHT和IFHT加速效果如圖5所示。當(dāng)碼長(zhǎng)從200 增長(zhǎng)到2 000，F(xiàn)HT+IFHT 的總耗時(shí)從191 ms 快速增加到了2 105 ms。而編碼分布式FHT+IFHT 方案能夠穩(wěn)定地并行加速FHT 和IFHT，提升兩者計(jì)算效率。

圖5 不同碼長(zhǎng)的64 元LDPC 碼FHT 和IFHT 耗時(shí)

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

圖6 200 碼長(zhǎng)的不同有限域階數(shù)LDPC 碼FHT 和IFHT 耗時(shí)

3.6 譯碼性能對(duì)比

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

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

除此之外，本文還進(jìn)一步分析了FHT-QSPA 和編碼分布式FHT-QSPA在單次校驗(yàn)節(jié)點(diǎn)迭代中FHT和IFHT 的耗時(shí)情況，如表5 所示。其中編碼分布式FHT 采用了5 個(gè)從節(jié)點(diǎn)，其中有1 個(gè)冗余節(jié)點(diǎn)的分布式設(shè)置，而掉隊(duì)節(jié)點(diǎn)數(shù)量設(shè)置為1 個(gè)。從表5 可以看出，通過編碼分布式的改造，使FHT 和IFHT 這2 個(gè)耗時(shí)最長(zhǎng)環(huán)節(jié)得到了穩(wěn)定加速。

表5 2 種譯碼算法單次迭代耗時(shí)

4 結(jié)束語

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

總體來看，本文方案的編譯碼環(huán)節(jié)的復(fù)雜度均較低，這使編碼分布式FHT 加速方案針對(duì)FHT 和IFHT 均獲得了接近于k倍的加速。將本文方案的譯碼恢復(fù)誤差與其他編碼矩陣乘法方案進(jìn)行對(duì)比，驗(yàn)證了本文方案優(yōu)秀的數(shù)值穩(wěn)定性。而不同有限域和碼長(zhǎng)的多元LDPC 碼譯碼耗時(shí)分析，確認(rèn)了本文方案的加速效果。譯碼性能曲線對(duì)比表明了本文方案可以在不損失譯碼性能的情況下，穩(wěn)定地加速譯碼過程。

另外，本文方案還適于其他變換，例如FFT 等。通過對(duì)待變換矩陣進(jìn)行編碼分布式加速，可以同時(shí)實(shí)現(xiàn)較高的抗節(jié)點(diǎn)掉隊(duì)性能和保持高效變換計(jì)算結(jié)構(gòu)。后續(xù)本文將繼續(xù)研究該方案在其他變換上的應(yīng)用，拓展系統(tǒng)型MDS 碼編碼分布式加速方案的應(yīng)用場(chǎng)景，提高計(jì)算效率。