基于矩陣譯碼算法的改進(jìn)研究

范 迪 蕭 楓 唐 聃

(成都信息工程大學(xué)軟件工程學(xué)院 四川 成都 610225)

0 引 言

隨著計(jì)算機(jī)技術(shù)的迅猛發(fā)展，信息技術(shù)在各個(gè)行業(yè)和領(lǐng)域都得到廣泛的普及，數(shù)據(jù)也呈爆炸性的增長(zhǎng)，使得人們對(duì)存儲(chǔ)系統(tǒng)的要求越來(lái)越高。日益增長(zhǎng)的存儲(chǔ)需求使得存儲(chǔ)系統(tǒng)中的存儲(chǔ)節(jié)點(diǎn)數(shù)量和單節(jié)點(diǎn)容量都呈指數(shù)級(jí)增長(zhǎng)，這就意味著發(fā)生節(jié)點(diǎn)失效的概率以及單節(jié)點(diǎn)中的扇區(qū)失效的概率越來(lái)越大，因此數(shù)據(jù)容錯(cuò)是存儲(chǔ)系統(tǒng)中一項(xiàng)不可或缺的關(guān)鍵技術(shù)。目前使用較多的容錯(cuò)技術(shù)為多副本復(fù)制技術(shù)，通過(guò)復(fù)制副本進(jìn)行容錯(cuò)。另外一種是糾刪碼容錯(cuò)技術(shù)，通過(guò)編碼進(jìn)行容錯(cuò)。編碼理論始于1948年Claudo Shannon發(fā)表的著名文獻(xiàn)[1]。最初編碼理論的主要應(yīng)用領(lǐng)域?yàn)橥ㄐ牛m刪碼是為了解決網(wǎng)絡(luò)傳輸問(wèn)題中多址傳送而提出來(lái)的，比較重要的一篇文獻(xiàn)是 1997 年Luigi Rizzo的文獻(xiàn)[2],該文主要提出了利用糾刪碼提高通信協(xié)議可靠性的方法，使用前向糾錯(cuò)碼 Reed Solomon 來(lái)解決網(wǎng)絡(luò)傳輸中一定數(shù)量的數(shù)據(jù)包丟失，原始數(shù)據(jù)還能恢復(fù)，并提出了一套可行的方案，同時(shí)該文提出糾刪碼可以應(yīng)用于分布式存儲(chǔ)系統(tǒng)。糾刪碼技術(shù)主要是依靠糾刪碼算法將原始的數(shù)據(jù)進(jìn)行編碼得到冗余元素后存儲(chǔ)，以達(dá)到容錯(cuò)的目的。在存儲(chǔ)系統(tǒng)中，它的主要思想是通過(guò)將k塊原始的數(shù)據(jù)元素編碼得到m塊冗余元素，當(dāng)其中有m塊元素失效時(shí)，可以通過(guò)一定的解碼算法利用余下的元素將丟失元素恢復(fù)出來(lái)。與多副本容錯(cuò)技術(shù)相比，糾刪碼容錯(cuò)技術(shù)可以在顯著降低存儲(chǔ)空間消耗的同時(shí)提供相同甚至較高的數(shù)據(jù)容錯(cuò)能力。

對(duì)于糾刪碼而言，最重要的就是其編解碼算法，每一類(lèi)糾刪碼都有本身所對(duì)應(yīng)的解碼算法，優(yōu)秀的解碼算法可以幫助提高存儲(chǔ)系統(tǒng)故障恢復(fù)的效率。同時(shí)也存在一些通用性的解碼算法。例如歸并譯碼和矩陣譯碼等。文獻(xiàn)[3]中提出的一種在二元域上的糾刪碼解碼算法(簡(jiǎn)稱(chēng)歸并譯碼)，通過(guò)對(duì)校驗(yàn)矩陣分塊并求逆來(lái)重建磁盤(pán)數(shù)據(jù)元素，但是此算法的運(yùn)算過(guò)程涉及到逆矩陣的計(jì)算，因而當(dāng)恢復(fù)單錯(cuò)時(shí)效率較高，一旦出現(xiàn)多錯(cuò)，求逆運(yùn)算會(huì)很大程度影響到運(yùn)算的速度，從而影響解碼效率。文獻(xiàn)[4]中提出一種針對(duì)糾刪碼的通用解碼算法，這種算法基于生成矩陣及其偽逆矩陣(簡(jiǎn)稱(chēng)矩陣譯碼)，對(duì)于丟失數(shù)據(jù)扇區(qū)，一般聲明為兩種結(jié)果，一種是算法可恢復(fù)即理論上可恢復(fù)，此時(shí)算法會(huì)提供一個(gè)由可讀數(shù)據(jù)構(gòu)成的公式來(lái)恢復(fù)丟失扇區(qū)，一種是理論上即不可恢復(fù)的扇區(qū)。對(duì)于陣列碼，矩陣譯碼算法還可以恢復(fù)隨機(jī)數(shù)據(jù)扇區(qū)的故障，解決了隨機(jī)扇區(qū)丟失的問(wèn)題，由此提供了更好的實(shí)用性，也提高了存儲(chǔ)系統(tǒng)的性能。矩陣譯碼算法既解決了陣列碼中隨機(jī)扇區(qū)丟失的恢復(fù)問(wèn)題，同時(shí)摒棄了求逆矩陣的運(yùn)算，使其效率很高；同樣是一種通用性的解碼算法，適用于任意的糾刪碼，最適合用于陣列碼。矩陣譯碼算法存在優(yōu)點(diǎn)，同時(shí)也有不足，其不足之處在于當(dāng)故障類(lèi)型包含冗余節(jié)點(diǎn)錯(cuò)誤時(shí)，不能隨原始數(shù)據(jù)節(jié)點(diǎn)同時(shí)恢復(fù)，需要在數(shù)據(jù)節(jié)點(diǎn)恢復(fù)完成后利用編碼將其恢復(fù)，由此會(huì)降低故障恢復(fù)的效率。本文將對(duì)矩陣譯碼算法的優(yōu)勢(shì)進(jìn)行描述，然后對(duì)其不足進(jìn)行改進(jìn)研究，最后基于改進(jìn)研究算法做出具體的實(shí)驗(yàn)分析。

1 矩陣譯碼算法

矩陣譯碼算法是一種通用的經(jīng)典糾刪碼解碼算法。其最大的特點(diǎn)在于：(1) 通用于任意糾刪碼；(2) 可以恢復(fù)隨機(jī)數(shù)據(jù)節(jié)點(diǎn)扇區(qū)的丟失。因?yàn)殛嚵写a特殊的矩陣結(jié)構(gòu)，矩陣譯碼算法可以更好地應(yīng)用在陣列碼中。對(duì)于普通的糾刪碼解碼，矩陣譯碼同時(shí)也消除了矩陣求逆的運(yùn)算過(guò)程，另外其效率也較高。

1.1 基本概念及定義

為了更好地描述算法，更加清晰明白地了解算法，介紹本文中涉及的基本概念和原理。對(duì)于糾刪碼的基本概念本文將不再贅述，可參考文獻(xiàn)[4-5]。

以下給出一些矩陣譯碼算法所用到的線(xiàn)性代數(shù)定義及原理。

定義1左偽逆矩陣：矩陣A右乘矩陣B得到單位陣I，則稱(chēng)B為A的右偽逆矩陣。當(dāng)矩陣A行滿(mǎn)秩且行數(shù)小于列數(shù)時(shí)，右偽逆矩陣一定存在。

定義2零空間：零空間是指與矩陣的每個(gè)行向量正交的所有向量的集合。零空間基則是指零空間中一個(gè)線(xiàn)性獨(dú)立向量的最大集合。

假定G為大小為R×C的矩陣，為編碼理論中的生成矩陣。H為編碼理論中的偽逆矩陣且R≤C，當(dāng)B為G的零空間基，U為G的右偽逆矩陣，X在大小C×(R-C)的二進(jìn)制矩陣上變化時(shí)，其中Ok為半單位陣：

G·(U+(B·X))=Ok

(1)

式中：U+(B·X)在所有部分偽逆上運(yùn)行，X是在U的每一列增加一個(gè)零空間向量。

在編碼理論中存在兩個(gè)重要等式，分別為D×G=T和T×H=0。其中D為編碼前元素向量，T為編碼后元素向量。由此可推出：

D×G×H==0

(2)

由式(2)即可看出H是G的零空間基，因此可以利用校驗(yàn)矩陣來(lái)求生成矩陣的偽逆矩陣。

原理1由矩陣譯碼算法得來(lái)的偽逆矩陣U中，任意理論可恢復(fù)的數(shù)據(jù)元素對(duì)應(yīng)U中的一個(gè)非零列，列中每個(gè)非零位置對(duì)應(yīng)哪些數(shù)據(jù)元素與冗余元素，它們的異或和即為該理論可恢復(fù)數(shù)據(jù)元素。一個(gè)直接可讀的數(shù)據(jù)元素對(duì)應(yīng)U中一個(gè)單位列(即只有一個(gè)1的列)。一個(gè)數(shù)據(jù)丟失事件(理論不可恢復(fù)數(shù)據(jù))對(duì)應(yīng)U中一個(gè)全零列。

證明令T代表編碼后包含所有元素的向量，T′代表丟失后的編碼向量，即丟失對(duì)應(yīng)位置為零，很明顯。

D·G′=T′

(3)

丟失元素在G′中對(duì)應(yīng)全零列。因此有:

T′·U=D·G′·U=D·Ok=D′

(4)

式中：D′的零元素位置對(duì)應(yīng)Ok對(duì)角線(xiàn)上為零的位置，同時(shí)Ok對(duì)應(yīng)偽逆矩陣U中的全零列。Ok中對(duì)角線(xiàn)上的非零位置對(duì)應(yīng)D′中的非零元素，而Ok中對(duì)角線(xiàn)上的非零位置同時(shí)對(duì)應(yīng)偽逆矩陣U中的非零列，由此偽逆矩陣U的每一行就對(duì)應(yīng)D′中的每一個(gè)元素。同時(shí)，因?yàn)門(mén)′·U=D′，所以偽逆矩陣U中的每一列，每一個(gè)位置對(duì)應(yīng)T中的一個(gè)元素，由此每列對(duì)應(yīng)一個(gè)數(shù)據(jù)元素，且每一非零位對(duì)應(yīng)一個(gè)已知可得的元素。

1.2 矩陣譯碼算法核心

矩陣譯碼算法的核心為偽逆矩陣U的構(gòu)造，因此接下來(lái)描述偽逆矩陣構(gòu)造的過(guò)程。首先定義一個(gè)丟失元素列表L，記錄丟失元素在D中的位置，H為校驗(yàn)矩陣。

步驟一：構(gòu)造一個(gè)方陣W，W=(U|H)，初始的偽逆矩陣U由一個(gè)單位陣和(R-C)行全0行構(gòu)成。

步驟二：對(duì)于丟失元素列表L，另r表示丟失元素對(duì)應(yīng)W中行向量，進(jìn)行如下操作：

(1) 查找H中r行有1的列b，如果不存在，將U中b列對(duì)應(yīng)有1的行置零，然后繼續(xù)下一個(gè)冗余元素。

(2)W中r行有1的每個(gè)列c，如果c≠b，那么將列b加到列c上。

(3) 將H中列b置零。

步驟三：利用所得U將丟失數(shù)據(jù)元素恢復(fù)出來(lái)。

1.3 矩陣譯碼算法分析

矩陣譯碼算法作為一種糾刪碼譯碼算法，可以用于任意糾刪碼，更適用于二元域的陣列碼。當(dāng)其應(yīng)用于陣列碼時(shí)，該算法有兩大優(yōu)勢(shì)：(1) 是一種通用性的解碼算法，它可以適用于任意陣列碼解碼；(2) 可以恢復(fù)任意數(shù)據(jù)失效扇區(qū)。

矩陣譯碼算法可以用于所有陣列碼，例如：STAR碼[6]、EVENODD碼[7]、RDP碼[8]等。尋常的陣列碼譯碼算法是利用循環(huán)迭代的方式進(jìn)行解碼，當(dāng)一個(gè)節(jié)點(diǎn)中任意扇區(qū)失效時(shí)，都被認(rèn)為是該節(jié)點(diǎn)失效，從而對(duì)整個(gè)節(jié)點(diǎn)進(jìn)行恢復(fù)。但是隨著數(shù)據(jù)量的不斷增大，硬件不斷增多，某個(gè)節(jié)點(diǎn)中扇區(qū)丟失的現(xiàn)象越來(lái)越多。當(dāng)重建整個(gè)節(jié)點(diǎn)時(shí)，也會(huì)重建那些不必要重建的扇區(qū)從而造成重復(fù)，增加不必要的計(jì)算量，因此針對(duì)隨機(jī)元素或扇區(qū)丟失的恢復(fù)也成為糾刪碼解碼的一個(gè)重要問(wèn)題。矩陣譯碼算法就可以實(shí)現(xiàn)這一目標(biāo)，可以恢復(fù)理論可恢復(fù)的任意扇區(qū)失效。可以達(dá)到這一目標(biāo)的譯碼算法還有一個(gè)比較有代表性的，是文獻(xiàn)[3]中提出的歸并譯碼算法。歸并譯碼算法與矩陣譯碼算法的最大區(qū)別在于矩陣譯碼算法無(wú)需進(jìn)行矩陣的求逆運(yùn)算，計(jì)算的時(shí)間復(fù)雜度低，歸并譯碼算法仍然涉及矩陣求逆運(yùn)算，出現(xiàn)單個(gè)錯(cuò)誤時(shí)，譯碼時(shí)間可以接受，但是當(dāng)有兩個(gè)及以上的錯(cuò)誤時(shí)，譯碼的時(shí)間成本仍然很高。因此相比較來(lái)講矩陣譯碼算法在時(shí)間復(fù)雜度上要更優(yōu)一點(diǎn)。

矩陣譯碼算法也存在缺點(diǎn)，就是當(dāng)錯(cuò)誤元素中包含有冗余元素時(shí)，不能直接求出冗余元素，而需要在求出數(shù)據(jù)元素后利用編碼計(jì)算出冗余元素。當(dāng)出現(xiàn)冗余元素錯(cuò)誤時(shí)，這個(gè)缺點(diǎn)也會(huì)在一定程度上影響計(jì)算的時(shí)間復(fù)雜度，因此如果可以在求解數(shù)據(jù)元素的同時(shí)將冗余元素求出，必將在一定程度上提高計(jì)算時(shí)間復(fù)雜度。

2 矩陣譯碼算法改進(jìn)研究

上一節(jié)中對(duì)于矩陣譯碼算法進(jìn)行了描述以及原理證明，又分別給出了算法的優(yōu)缺點(diǎn)。本節(jié)中，針對(duì)矩陣譯碼算法的不足之處，提出本文的改進(jìn)研究方案。該改進(jìn)算法可以恢復(fù)任意理論可解的情況，減少了對(duì)于冗余元素的計(jì)算量，降低了計(jì)算時(shí)間復(fù)雜度。本節(jié)中，首先對(duì)改進(jìn)算法步驟進(jìn)行描述，并對(duì)其中冗余元素的求取進(jìn)行正確性證明，最后根據(jù)情況舉出具體的實(shí)例。

2.1 改進(jìn)算法描述

為了與平時(shí)編碼理論習(xí)慣相一致，在改進(jìn)算法中，生成矩陣G采用縱向矩陣，校驗(yàn)矩陣H采用橫向矩陣方式表示，因此偽逆矩陣變?yōu)橛覀文婢仃?。將?shù)據(jù)丟失元素列表記為L(zhǎng)。以下描述本算法步驟：

步驟二：判斷構(gòu)成A的校驗(yàn)矩陣H的右半部分是否為單位陣，若不是，通過(guò)校驗(yàn)矩陣行與行間初等行變換即異或?qū)⑵渥優(yōu)閱挝魂嚭筮M(jìn)行運(yùn)算，如下例：

RDP(4,3)的校驗(yàn)矩陣如下：

由上式可看出RDP校驗(yàn)矩陣的右半部分并不是校驗(yàn)矩陣，因?yàn)檫M(jìn)行初等行變換，將第一行與第二行進(jìn)行異或并放置于第二行，則可得到單位陣，可得結(jié)果如下式：

步驟三：對(duì)工作空間A進(jìn)行行變換也相當(dāng)于求逆的過(guò)程，具體求逆過(guò)程在下面會(huì)進(jìn)行描述；

步驟四：得出變換后的工作空間A即可恢復(fù)出丟失元素，A中一行代表一個(gè)數(shù)據(jù)元素，每行中非零位置代表已知可得的數(shù)據(jù)元素。

其中將工作空間A進(jìn)行初等行變換求逆的具體步驟如下：

步驟一：對(duì)丟失元素列表L中的每個(gè)數(shù)據(jù)元素s，循環(huán)遍歷L中s，首先判斷數(shù)據(jù)元素s的類(lèi)型，是屬于原始數(shù)據(jù)的還是冗余數(shù)據(jù)，若為數(shù)據(jù)元素繼續(xù)進(jìn)行操作進(jìn)入步驟二，若為冗余元素則跳過(guò)進(jìn)行下一個(gè)元素的判斷；

步驟二：在校驗(yàn)矩陣H中找s列為1的行h。如果不存在這樣的行h，那么將U中s列有1的行置零(說(shuō)明此元素s理論上不可恢復(fù))；

步驟三：若找到列表h后，如果L中沒(méi)有包含冗余元素，即沒(méi)有冗余元素丟失，那么就從找到的列表h中選擇最稀疏的一行(即漢明重量最小的一行)f，如果L中包含冗余元素，則將L中丟失的冗余元素對(duì)應(yīng)行號(hào)從找到的列表h中去除后再在列表h中選擇最稀疏的一行f(為了保留丟失的冗余元素對(duì)應(yīng)行的值，最后可以同時(shí)求出)；

步驟四：對(duì)于工作空間A中第s列為1的行E列表，如果E中每一個(gè)元素e≠f，那么將f與e相加(異或)并替換掉e；

步驟五：將構(gòu)成工作空間的行H中第f行置零；

至此，對(duì)于算法改進(jìn)的研究步驟基本描述完畢。最后得到的工作空間既可以恢復(fù)數(shù)據(jù)元素，又可以恢復(fù)校驗(yàn)元素，也就是可以恢復(fù)所有理論上可恢復(fù)的情況。

2.2 正確性證明

本文提出的改進(jìn)研究算法中保留了對(duì)于數(shù)據(jù)元素恢復(fù)的偽逆矩陣，同時(shí)生成了一個(gè)新的用于恢復(fù)冗余元素的冗余矩陣，用H′表示。下面將對(duì)冗余矩陣進(jìn)行正確性證明。

校驗(yàn)矩陣是用來(lái)檢驗(yàn)碼字是否正確的一種矩陣，它的每一列代表一個(gè)元素位置，每一行代表一個(gè)冗余元素，同時(shí)也是一個(gè)方程式(每一行中所有非0位置進(jìn)行異或后結(jié)果為0)。上面所提到的冗余矩陣便是由校驗(yàn)矩陣變換得來(lái)。

原理2由本文的改進(jìn)算法得出的冗余矩陣，它的非零行代表一個(gè)理論上可恢復(fù)的冗余元素，這一行中每個(gè)非零位置對(duì)應(yīng)的元素異或和即為該行對(duì)應(yīng)的冗余元素的值。每一個(gè)全零行代表一個(gè)已知可讀的冗余元素。

證明校驗(yàn)矩陣的每一行異或結(jié)果均為零，因此將校驗(yàn)矩陣進(jìn)行初等行變換后并不會(huì)改變此性質(zhì)。而根據(jù)異或邏輯運(yùn)算，如果兩個(gè)值不相同，異或結(jié)果為1；如果兩個(gè)值相同，則異或結(jié)果為0。當(dāng)進(jìn)行求冗余矩陣的步驟時(shí)，將丟失冗余元素對(duì)應(yīng)列置零后，冗余矩陣中每一個(gè)非零行上其余元素的異或和應(yīng)等于丟失元素的值，由此即可證明出原理即冗余矩陣的正確性。下面將給出一個(gè)例子說(shuō)明。

以STAR(6,3)的校驗(yàn)矩陣為例，其校驗(yàn)矩陣如下：

校驗(yàn)矩陣的每一行都代表一個(gè)冗余元素，STAR(6,3)的冗余元素為(P0,P1|Q0,0,Q1,0|Q0,1,Q1,1)。假設(shè)丟失的冗余元素為P1，那么在算法的最后將P1對(duì)應(yīng)的列也就是第7列置零，則第2行剩余非零位置所應(yīng)對(duì)的元素異或和即為P1的值，公式如下：

d1,0+d1,1+d1,2=P1

2.3 具體實(shí)例

上一小節(jié)中證明了該算法的正確性，本小節(jié)將采用典型的實(shí)例來(lái)進(jìn)一步分析和說(shuō)明本算法。

例1：以EVENODD(5,3)[7]為例，將磁盤(pán)數(shù)據(jù)展開(kāi)來(lái)排成一個(gè)行向量，可以寫(xiě)為T(mén)=(d0,0,d1,0|d0,1,d1,1|d0,2,d1,2|P0,P1|Q0,Q1)，此時(shí)假設(shè)丟失元素為d0,0、d0,1、P1、Q0，則丟失元素列表為L(zhǎng)=(0,2,7,8)。

首先構(gòu)造一個(gè)10×10的工作單元A：

(5)

判斷構(gòu)成工作單元的校驗(yàn)矩陣右半部分是否為單位陣，由式(5)可以看出符合條件，那么繼續(xù)進(jìn)行操作，循環(huán)遍歷丟失元素列表s。當(dāng)s=0時(shí)，0屬于數(shù)據(jù)元素，所以在H中找第0列為1的行h，可以找到h=6,8。因?yàn)?也是丟失元素，將其排除，選擇h=6。將第6行分別加到第0行，第8行后，第6行置零，結(jié)果所得工作單元A為：

(6)

繼續(xù)當(dāng)s=2時(shí)，2屬于數(shù)據(jù)元素，所以在H中找第2列為1的行h，可以找到h=8,9。因?yàn)?為丟失元素，將其排除，選擇h=9。將第9行分別加到第0行，第2行和第8行后，第9行置零，結(jié)果所得工作單元A為：

(7)

當(dāng)s=7時(shí)，7屬于冗余元素，所以跳過(guò)；當(dāng)s=8時(shí)，8屬于冗余元素，所以跳過(guò)。丟失元素列表循環(huán)完畢，將7、8列置零。最終所得工作空間A為：

(8)

工作單元A中，上半部分為求解數(shù)據(jù)元素的偽逆矩陣，下半部分為求解冗余元素的冗余矩陣。因此可恢復(fù)出丟失的數(shù)據(jù)元素與冗余元素d0,0、d0,1、P1、Q0。具體公式如下：

(9)

例1：以RDP(4,3)為例，將磁盤(pán)數(shù)據(jù)展開(kāi)來(lái)排成一個(gè)行向量，可以寫(xiě)為T(mén)=(d0,0,d1,0|d0,1,d1,1|P0,P1|Q0,Q1)，此時(shí)假設(shè)丟失元素為d0,0、d0,1、P0、P1，則丟失元素列表為L(zhǎng)=(0,2,4,5)。

首先構(gòu)造一個(gè)8×8的工作單元：

(10)

判斷構(gòu)成工作單元的校驗(yàn)矩陣右半部分是否為單位陣，由式(10)可看出，不符合條件，因此將第5行加到第6行，使其變?yōu)閱挝魂嚕?/p>

(11)

開(kāi)始循環(huán)遍歷丟失元素列表。當(dāng)s=0時(shí)，尋找H中第0列為1的行h，可得h=4,6。因?yàn)?同樣為丟失元素，拋棄掉，選擇h=6。將第6行分別加到第0行和第4行后，第6行置零。當(dāng)s=2時(shí)，在H中找第2列中為1的行，h=(4,7)，但是因?yàn)?在L中，所以排除4，選擇h=7，選定后將第7行加到0、4行，然后第7行置零。當(dāng)s=4時(shí)，4為冗余元素，跳過(guò)；當(dāng)s=5時(shí)，5為冗余元素，跳過(guò)。丟失列表元素循環(huán)完畢，將4、5列置零，最后可得工作單元式(12)：

(12)

工作單元A中，上半部分為求解數(shù)據(jù)元素的偽逆矩陣，下半部分為求解冗余元素的冗余矩陣。因此可恢復(fù)出丟失的數(shù)據(jù)元素與冗余元素d0,0、d0,1、P0、P1。具體公式如下：

(13)

3 實(shí)驗(yàn)分析

就糾刪碼的性能而言，關(guān)鍵還在于它的編解碼，本文主要研究的是糾刪碼的解碼算法。

陣列碼是一種僅通過(guò)異或運(yùn)算構(gòu)造的碼制，它本身的解碼算法是利用循環(huán)迭代來(lái)進(jìn)行解碼。當(dāng)一個(gè)條塊中的一個(gè)元素丟失即認(rèn)為是整個(gè)條塊乃至整個(gè)磁盤(pán)的丟失，恢復(fù)時(shí)會(huì)重建整個(gè)磁盤(pán)，且每種陣列碼的原始解碼均不相同。文獻(xiàn)[4]提出一種恢復(fù)隨機(jī)數(shù)據(jù)元素的算法——矩陣譯碼，利用生成矩陣的偽逆理論重建數(shù)據(jù)元素，適用于任意的糾刪碼，但是卻不能同時(shí)恢復(fù)冗余元素。而Tang在文獻(xiàn)[3]中提出一種歸并譯碼算法，通過(guò)對(duì)校驗(yàn)矩陣分塊并求逆來(lái)重建磁盤(pán)數(shù)據(jù)元素，可以同時(shí)恢復(fù)數(shù)據(jù)元素和冗余元素，但是這種算法需要計(jì)算逆矩陣，增加了計(jì)算復(fù)雜度，效率不高。本文提出的改進(jìn)解碼算法是基于矩陣譯碼算法的改進(jìn)，可以恢復(fù)理論上可以恢復(fù)的任一情況，包括同時(shí)恢復(fù)數(shù)據(jù)元素與冗余元素。因此本節(jié)將使用幾種不同的糾刪碼譯碼方法作為容錯(cuò)方案構(gòu)建存儲(chǔ)仿真系統(tǒng)，在存儲(chǔ)仿真系統(tǒng)中對(duì)失效數(shù)據(jù)進(jìn)行重構(gòu)。構(gòu)建存儲(chǔ)仿真系統(tǒng)所使用的語(yǔ)言平臺(tái)為Python。構(gòu)建存儲(chǔ)仿真系統(tǒng)所用到的計(jì)算機(jī)主要配置為：CPU Inter Core i5-6200U，內(nèi)存8 GB，磁盤(pán)容量250 GB。

對(duì)于EVENODD碼，一般常用的解碼算法為循環(huán)迭代的解碼算法，因此我們?cè)诜抡娲鎯?chǔ)系統(tǒng)中首先對(duì)EVENODD進(jìn)行編碼，素?cái)?shù)選取5。模擬數(shù)據(jù)丟失事件，然后利用幾種不同的譯碼算法對(duì)其進(jìn)行比較分析。設(shè)置文件存儲(chǔ)的塊大小為10 240 B，對(duì)于不同文件的大小，分別利用四種解碼算法進(jìn)行對(duì)比實(shí)驗(yàn)分析。針對(duì)不同尺寸文件的單節(jié)點(diǎn)失效和雙節(jié)點(diǎn)失效，其中雙節(jié)點(diǎn)失效模擬節(jié)點(diǎn)0和節(jié)點(diǎn)5失效。

實(shí)驗(yàn)1在以上所描述的實(shí)驗(yàn)條件下，首先對(duì)于歸并譯碼和改進(jìn)方法進(jìn)行對(duì)比，時(shí)間效率對(duì)比圖如圖1和圖2所示。圖1為單節(jié)點(diǎn)失效的時(shí)間效率對(duì)比圖，圖2為雙節(jié)點(diǎn)時(shí)間效率對(duì)比圖。在單節(jié)點(diǎn)失效時(shí)，歸并譯碼與改進(jìn)算法相差并不是很多，這也說(shuō)明了歸并譯碼方法在單節(jié)點(diǎn)失效時(shí)效率不低。但是從圖2可以很明顯看出文獻(xiàn)[3]的歸并譯碼效率遠(yuǎn)不及改進(jìn)方法的時(shí)間效率。同樣的前提下，當(dāng)發(fā)生兩個(gè)節(jié)點(diǎn)失效時(shí)，歸并譯碼幾乎是改進(jìn)方法的1.5倍。之后隨著文件尺寸的增大，歸并譯碼有可能呈現(xiàn)指數(shù)級(jí)的增長(zhǎng)，而本改進(jìn)譯碼方法隨著文件尺寸的增大，時(shí)間消耗呈直線(xiàn)性增長(zhǎng)。

圖1 單節(jié)點(diǎn)失效譯碼時(shí)間對(duì)比圖

圖2 雙節(jié)點(diǎn)失效譯碼時(shí)間對(duì)比圖

實(shí)驗(yàn)2在本節(jié)剛開(kāi)始所描述的實(shí)驗(yàn)條件下，對(duì)矩陣譯碼方法和本改進(jìn)譯碼方法進(jìn)行時(shí)間效率的對(duì)比，對(duì)比時(shí)間效果圖如圖3和圖4，圖3為單節(jié)點(diǎn)失效時(shí)的時(shí)間對(duì)比圖，圖4為雙節(jié)點(diǎn)失效的時(shí)間對(duì)比圖。從圖3可以看出，單節(jié)點(diǎn)時(shí)，因?yàn)橹换謴?fù)一個(gè)數(shù)據(jù)節(jié)點(diǎn)，因此并不能體現(xiàn)出改進(jìn)的優(yōu)點(diǎn)。從圖4雙節(jié)點(diǎn)丟失的對(duì)比圖可以看出兩者的效率相差雖不多，但還是有一定的差別，本改進(jìn)算法的時(shí)間消耗始終比矩陣譯碼方法的效率高，也說(shuō)明了同時(shí)恢復(fù)數(shù)據(jù)元素和冗余元素比先恢復(fù)數(shù)據(jù)元素再根據(jù)編碼恢復(fù)冗余元素效率要高。

圖3 單節(jié)點(diǎn)失效譯碼時(shí)間對(duì)比圖

圖4 雙節(jié)點(diǎn)失效譯碼時(shí)間對(duì)比圖

實(shí)驗(yàn)3仍然利用與前兩個(gè)實(shí)驗(yàn)相同的實(shí)驗(yàn)條件，對(duì)循環(huán)迭代法和改進(jìn)方法進(jìn)行時(shí)間效率對(duì)比，對(duì)比圖如圖5和圖6，圖5為單節(jié)點(diǎn)失效的時(shí)間對(duì)比圖，圖6為雙節(jié)點(diǎn)失效的對(duì)比圖。兩張圖都可以很明顯地看出循環(huán)迭代法的效率要比改進(jìn)方法的效率高，但是相差不多。從另一個(gè)方法看，改進(jìn)方法可以是對(duì)于不同節(jié)點(diǎn)中隨機(jī)扇區(qū)進(jìn)行理論可行的恢復(fù)，而循環(huán)迭代法只能針對(duì)節(jié)點(diǎn)進(jìn)行恢復(fù)，當(dāng)一個(gè)節(jié)點(diǎn)中某一個(gè)扇區(qū)丟失時(shí)，必須要恢復(fù)整個(gè)節(jié)點(diǎn)，增加了很多不必要的計(jì)算量。目前在存儲(chǔ)系統(tǒng)中，發(fā)生扇區(qū)失誤的概率很高，因此，兩者平衡下，改進(jìn)方法要相對(duì)好一些。

圖5 單節(jié)點(diǎn)失效譯碼時(shí)間對(duì)比圖

圖6 雙節(jié)點(diǎn)失效譯碼時(shí)間對(duì)比圖

從以上三個(gè)實(shí)驗(yàn)可以很明顯看出，本文提出的改進(jìn)算法的計(jì)算效率比較優(yōu)異且在各方面的性能比較均衡。

實(shí)驗(yàn)4為了證明本改進(jìn)算法的通用性，利用與上面三個(gè)實(shí)驗(yàn)相同的實(shí)驗(yàn)條件，將改進(jìn)方法應(yīng)用于RDP碼中，模擬雙節(jié)點(diǎn)丟失的事件，并與其余三種譯碼方法進(jìn)行對(duì)比。時(shí)間效果對(duì)比圖如圖7所示，也從另一方面驗(yàn)證了上述三個(gè)實(shí)驗(yàn)結(jié)果的正確性。

圖7 RDP雙節(jié)點(diǎn)失效譯碼時(shí)間對(duì)比圖

4 結(jié) 語(yǔ)

針對(duì)糾刪碼解碼算法，本文首先介紹了一種通用性的解碼算法——矩陣譯碼，在保留了原算法的優(yōu)勢(shì)下，對(duì)其不足之處進(jìn)行改進(jìn)研究，最后在仿真存儲(chǔ)系統(tǒng)中進(jìn)行實(shí)驗(yàn)數(shù)據(jù)分析，可以看出確實(shí)在性能中有所改變，可以廣泛應(yīng)用于隨機(jī)扇區(qū)丟失的場(chǎng)景。本文提出的這種改進(jìn)算法目前是運(yùn)行在二進(jìn)制矩陣上的針對(duì)陣列碼的運(yùn)算，以后改進(jìn)研究可以將此算法推廣至非二進(jìn)制上進(jìn)行解碼運(yùn)算。