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

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

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

【部分圖文】：

第一次連線圖

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

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


本文編號(hào)：2934005