針對RS（Reed-Solomon）算法編碼過程涉及有限域運算,復(fù)雜度高,效率低,運算代價難以被大規(guī)模分布式存儲系統(tǒng)所接受等問題,提出了一種RS柯西碼編碼改進(jìn)算法。該算法用貪心算法選取局部最優(yōu)柯西矩陣,減少柯西碼的計算量。同時,引入二進(jìn)制矩陣替換柯西矩陣中的有限域元素進(jìn)行陣列化,將有限域運算轉(zhuǎn)換為異或運算,并對陣列進(jìn)行運算優(yōu)化,進(jìn)一步減少計算量,增加柯西碼的編碼效率。根據(jù)仿真實驗表明,改進(jìn)后RS柯西碼與通過遍歷得到的最優(yōu)柯西矩陣的柯西碼相比,計算量更小,與編碼效率著稱的陣列碼中的EVENODD碼和STAR碼相比,編碼效率更高。并且具有類似陣列碼性質(zhì),能夠選擇更簡單高效的譯碼方法,在一定程度上提高解碼效率。 

【文章來源】：計算機工程與應(yīng)用. 2020年11期 北大核心

【文章頁數(shù)】：7 頁

【部分圖文】：

第一次連線圖

在有了二進(jìn)制矩陣替換有限域元素的方法，將復(fù)雜的有限域運算轉(zhuǎn)換為簡單的異或運算，RS柯西碼的計算復(fù)雜度得到了一定程度的降低。但集合X、Y的不同，對RS柯西碼的編碼效率影響非常大。目前，并沒有一個好的方法去得到最優(yōu)集合X和Y，只能通過遍歷得到，隨著規(guī)模加大，得到最優(yōu)集合的代價也會隨之增加。也有采取隨機的方式來選取集合X和Y，但得到的柯西矩陣的1的數(shù)量無法得到保證。圖2展示了優(yōu)化后的RS柯西碼與遍歷最優(yōu)RS柯西碼、隨機RS柯西碼的編碼所需異或數(shù)對比情況，并且以兩種不同條件進(jìn)行更全面的展示。圖2(a）展示的是在保持校驗塊數(shù)為4，有限域為GF(24)的條件下，數(shù)據(jù)塊數(shù)從4到9編碼所需的異或數(shù)變化情況。圖2(b）展示的是在保持?jǐn)?shù)據(jù)塊數(shù)為4，有限域為GF(24)的條件下，校驗塊數(shù)從4到8編碼所需的異或數(shù)變化情況。從圖中可以看出經(jīng)過優(yōu)化后的RS柯西碼編碼所需的異或數(shù)遠(yuǎn)小于文獻(xiàn)[14]的遍歷最優(yōu)RS柯西碼，并且選取集合X、Y的代價也相對較小。編碼效率不僅能夠通過編碼所需的異或數(shù)來體現(xiàn)。通過編碼時間也能更直觀地反應(yīng)編碼的效率。圖3與圖4分別展示了優(yōu)化后的RS柯西碼與EVENODD碼、STAR碼分別對1～10 MB的文件進(jìn)行編碼的編碼時間對比情況，并分為數(shù)據(jù)塊數(shù)為5和7分別進(jìn)行對比。從圖中可以看出經(jīng)過優(yōu)化的RS柯西碼的編碼時間與以編碼效率著稱的陣列碼中的代表EVENODD碼和STAR碼相差不大，甚至有一些優(yōu)勢。并且對于EVENODD碼和STAR碼，容錯超過3便失效了�？梢妰�(yōu)化后的RS柯西碼編碼效率有了很大幅度的提升。

編碼效率不僅能夠通過編碼所需的異或數(shù)來體現(xiàn)。通過編碼時間也能更直觀地反應(yīng)編碼的效率。圖3與圖4分別展示了優(yōu)化后的RS柯西碼與EVENODD碼、STAR碼分別對1～10 MB的文件進(jìn)行編碼的編碼時間對比情況，并分為數(shù)據(jù)塊數(shù)為5和7分別進(jìn)行對比。從圖中可以看出經(jīng)過優(yōu)化的RS柯西碼的編碼時間與以編碼效率著稱的陣列碼中的代表EVENODD碼和STAR碼相差不大，甚至有一些優(yōu)勢。并且對于EVENODD碼和STAR碼，容錯超過3便失效了�？梢妰�(yōu)化后的RS柯西碼編碼效率有了很大幅度的提升。圖4 優(yōu)化后的RS柯西碼與STAR碼的編碼時間對比


本文編號：2934005