[發(fā)明專利]一類糾刪碼的譯碼方法

有效

• 申請?zhí)枺?/td>: 201710973448.5
• 申請日: 2017-10-18
• 公開（公告）號(hào): CN107665152B
• 公開（公告）日: 2020-10-16
• 發(fā)明（設(shè)計(jì)）人: 唐聃;舒紅平;王亞強(qiáng);劉敦龍;高燕;岳希
• 申請（專利權(quán)）人: 成都信息工程大學(xué)
• 主分類號(hào): G06F11/10
• 分類號(hào): G06F11/10;G06F3/06
• 代理公司: 成都賽恩斯知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 51212
• 代理人: 張端陽

本發(fā)明屬于計(jì)算機(jī)信息存儲(chǔ)技術(shù)領(lǐng)域，具體是一種糾刪碼的譯碼方法。目前對(duì)基于二進(jìn)制異或運(yùn)算的糾刪碼，解碼方法幾乎都采用了循環(huán)迭代法，即不斷循環(huán)遍歷，這造成了解碼的算法時(shí)間復(fù)雜度高，解碼的速度低下；并且在沒有解碼前，難以對(duì)是否完全解碼成功進(jìn)行預(yù)判。本發(fā)明所述的一種糾刪碼的譯碼方法與傳統(tǒng)循環(huán)迭代譯碼方法相比，解碼的時(shí)間復(fù)雜度降低、速度提高；且適用于任何基于二進(jìn)制異或運(yùn)算的糾刪碼，包括EVENODD碼、X碼、STAR碼、RDP碼、斜率碼等，應(yīng)用范圍廣。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)信息存儲(chǔ)技術(shù)領(lǐng)域，具體是一種糾刪碼的譯碼方法。

背景技術(shù)

隨著網(wǎng)絡(luò)和服務(wù)器的迅速成長，數(shù)據(jù)的容量越來越大，數(shù)據(jù)的重要性和安全性也更加得到重視。為了應(yīng)對(duì)由數(shù)據(jù)量的快速增長而帶來的數(shù)據(jù)存儲(chǔ)可靠性問題，海量存儲(chǔ)系統(tǒng)必須能夠提供安全的存儲(chǔ)服務(wù)、以及持續(xù)的在線運(yùn)行和高效、可靠的容錯(cuò)機(jī)制；同時(shí)也為了提高數(shù)據(jù)訪問的并發(fā)效率和降低成本，通常有效的做法是使用多個(gè)存儲(chǔ)節(jié)點(diǎn)共同構(gòu)建一個(gè)存儲(chǔ)系統(tǒng)，該存儲(chǔ)系統(tǒng)通常是基于網(wǎng)絡(luò)的分布式存儲(chǔ)系統(tǒng)。

針對(duì)傳統(tǒng)數(shù)據(jù)冗余保護(hù)技術(shù)在大容量磁盤存儲(chǔ)系統(tǒng)中所表現(xiàn)出的不足，以分布式、大規(guī)模、大容量磁盤存儲(chǔ)為特點(diǎn)的海量存儲(chǔ)系統(tǒng)中出現(xiàn)了一種更加高效的數(shù)據(jù)冗余技術(shù)——糾刪碼。糾刪碼起源于通信傳輸領(lǐng)域，目前逐漸出現(xiàn)在大規(guī)模存儲(chǔ)系統(tǒng)中，特別是分布式存儲(chǔ)環(huán)境。糾刪碼技術(shù)基本思想是將一份數(shù)據(jù)劃分為k塊原始的數(shù)據(jù)，基于k塊原始數(shù)據(jù)冗余計(jì)算獲得m塊冗余數(shù)據(jù)。對(duì)于這k+m塊數(shù)據(jù)，其中任意的m塊碼元出錯(cuò)時(shí)，存儲(chǔ)系統(tǒng)均可以通過重構(gòu)算法恢復(fù)出原來的k塊數(shù)據(jù)，糾刪碼冗余保護(hù)技術(shù)解決了傳統(tǒng)冗余保護(hù)技術(shù)不適于分布式生產(chǎn)存儲(chǔ)系統(tǒng)的問題。

糾刪碼可以用于有大量數(shù)據(jù)和任何需要容錯(cuò)的應(yīng)用程序或系統(tǒng)中，比如磁盤陣列系統(tǒng)、數(shù)據(jù)網(wǎng)格、分布式存儲(chǔ)應(yīng)用程序、對(duì)象存儲(chǔ)或歸檔存儲(chǔ)。基于糾刪碼的方法與傳統(tǒng)的鏡像、副本技術(shù)相比，具有冗余度低、磁盤利用率高等優(yōu)點(diǎn)。目前，糾刪碼的一個(gè)常見的使用案例是基于對(duì)象的云存儲(chǔ)，其針對(duì)云計(jì)算、大數(shù)據(jù)業(yè)務(wù)對(duì)海量存儲(chǔ)系統(tǒng)的多樣性、大規(guī)模存儲(chǔ)容量需求，能夠較好的適應(yīng)分布式存儲(chǔ)應(yīng)用環(huán)境。

糾刪碼是一類特殊的編碼刪碼，它是一種前向錯(cuò)誤糾正技術(shù)，即在譯碼時(shí)碼字中錯(cuò)誤的位置已知。目前對(duì)基于二進(jìn)制異或運(yùn)算的糾刪碼而言，解碼方法幾乎都采用了循環(huán)迭代法，即不斷循環(huán)遍歷。這造成了解碼的算法時(shí)間復(fù)雜度高，解碼的速度低下；并且在沒有解碼前，難以對(duì)是否完全解碼成功進(jìn)行預(yù)判。

發(fā)明內(nèi)容

本發(fā)明的目的是，提供一種降低解碼算法時(shí)間復(fù)雜度、提升解碼速度、適用范圍廣的糾刪碼譯碼方法。

為實(shí)現(xiàn)上述目的，本發(fā)明所述糾刪碼的譯碼方法的具體方案如下：

已知某糾刪碼的校驗(yàn)矩陣H和錯(cuò)誤的位置，碼字中數(shù)據(jù)位的個(gè)數(shù)為dNum，所述方法求得錯(cuò)誤碼元的值的具體步驟為：

S1、假設(shè)矩陣H的尺寸為m×n；構(gòu)造一個(gè)dNum×dNum的單位矩陣，記作I；構(gòu)造一個(gè)(n-dNum)×(n-dNum)的零矩陣，記作O；根據(jù)矩陣H、I、O，拼接出一個(gè)新的矩陣W，如下所示：

S2、對(duì)碼字中每一個(gè)碼元賦予一個(gè)從0開始的遞增整數(shù)編號(hào)：0、1、2、...；將所有發(fā)生錯(cuò)誤碼元的編號(hào)集合，記作errIDs；按順序從errIDs中取出一個(gè)碼元，即錯(cuò)誤碼元的編號(hào)，記作eID；

S3、搜索矩陣W的第eID列中等于1的所有行，記作dqRows，其中，行列編號(hào)均從0開始；然后遍歷dqRows中的行編號(hào)，找出對(duì)應(yīng)矩陣W中行重最小且編號(hào)大于等于dNum的編號(hào)，記作bRow；

S4、矩陣W中，將bRow對(duì)應(yīng)的行采用異或運(yùn)算加到dqRows中其他所有編號(hào)對(duì)應(yīng)的行，結(jié)果模2；

S5、矩陣W中，將bRow對(duì)應(yīng)的行中的所有值置0；