[發明專利]用于編碼數據的方法和裝置

有效

• 申請號: 201580083722.0
• 申請日: 2015-10-09
• 公開（公告）號: CN108156838B
• 公開（公告）日: 2021-02-12
• 發明（設計）人: 彼得·弗拉基米羅維奇·特里福;王元鋼;陳晨
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H03M13/03
• 分類號: H03M13/03;H03M13/29;H03M13/37;G06F11/10;H03M13/15
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 熊永強;李稷芳

1.一種用于從部分糾刪的編碼數據對數據進行恢復的方法，其特征在于，對所述編碼數據進行編碼以存儲在n個存儲節點(220、230)的存儲設備(222、224、232、234、360)中，使得所述數據在多達r個存儲節點發生故障和多達s個存儲設備發生故障之后可恢復，所述方法包括：

用一個或多個外碼對所述數據進行外編碼(110、320)以獲得外編碼數據；

用一個或多個捎帶內碼對所述外編碼數據進行編碼(120、340)以獲得編碼數據；

所述外碼為GF(2m)上的C_i(ν，K_i，v-K_i+1)碼，其中，對于0＜i≤n，ν≤2^m，其中K₁＝...＝K_r＝0，

如果t_s+t'_b≤r，其中，t_s是發生故障的存儲節點的數量，且是存儲節點的數量，其中，存儲設備i發生故障，則所述方法包括：將內碼解碼算法應用于所述部分糾刪的編碼數據的碼字的每一列。

2.根據權利要求1所述的方法，其特征在于，所述一個或多個外碼和/或一個或多個內碼是最大距離可分碼。

3.根據前述權利要求任一項所述的方法，其特征在于，所述編碼數據(350)可表示為n×mv矩陣(400)，其中，所述方法包括：將所述矩陣的第i行(410)存儲在第i個存儲節點中，將來自第(pm+j)列(422、424)的一個或多個符號存儲在第p個存儲設備的第j個塊中。

4.根據權利要求1所述的方法，其特征在于，所述方法包括：

構造內碼和外碼的級聯對應的校驗矩陣H＝(I|A)P，其中，P是將單位子矩陣映射到部分糾刪數據的一個或多個糾刪符號的位置上的置換矩陣；

將碼字c的一個或多個糾刪符號c_j恢復為c_j＝i_i≠jc_iH_ji。

5.根據權利要求4所述的方法，其特征在于，所述校驗矩陣通過高斯消除從方程GH^T＝0中獲得，其中，G⁽ⁱ⁾是第i個外碼生成器矩陣，是所述一個或多個捎帶內碼的生成器矩陣的第i行。

6.一種用于對數據進行編碼以存儲在n個存儲節點(220、230)的存儲設備(222、224、232、234)中的裝置(210)，使得所述數據在多達r個存儲節點發生故障和多達s個存儲設備發生故障之后可恢復，其特征在于，所述裝置包括：

第一編碼器(212)，用于用一個或多個外碼對所述數據進行外編碼以獲得外編碼數據；

第二編碼器(214)，用于用一個或多個捎帶內碼對所述外編碼數據進行編碼以獲得編碼數據，其中，所述裝置用于執行根據權利要求1至4中任一項所述的方法；

所述外碼為GF(2m)上的C_i(ν，K_i，v-K_i+1)碼，其中，對于0＜i≤n，ν≤2^m，其中K₁＝...＝K_r＝0，

如果t_s+t'_b≤r，其中，t_s是發生故障的存儲節點的數量，且是存儲節點的數量，其中，存儲設備i發生故障，則所述方法包括：將內碼解碼算法應用于所述部分糾刪的編碼數據的碼字的每一列。

7.根據權利要求6所述的裝置，其特征在于，所述第一編碼器和/或所述第二編碼器以硬件實現，特別地，以ASIC和/或FPGA實現。

8.一種用于對部分糾刪的編碼數據進行恢復的裝置，其特征在于，包括解碼器，用于對所述部分糾刪的編碼數據進行解碼；其中，所述編碼數據已經使用一個或多個外碼和一個或多個內碼的級聯進行編碼，其中，所述一個或多個外碼和所述一個或多個內碼是捎帶的最大距離可分離碼；其中，特別地，所述裝置用于執行根據權利要求4或5所述的方法。

9.一種存儲了程序代碼的計算機可讀存儲介質，其特征在于，所述程序代碼包括用于執行根據權利要求1至5中任一項所述的方法的指令。