糾刪碼

2024年2月15日發(fā)(作者：瓷玫瑰)

一 糾刪碼概念和原理

前向糾錯(cuò)(Forward Error Correcting，F(xiàn)EC)技術(shù)近年來(lái)廣泛應(yīng)用于信息處理的各個(gè)領(lǐng)域。各種糾錯(cuò)碼，諸如漢明碼、BCH碼、Reed-Solomon(RS)碼、卷積碼、Turbo碼、低密度奇偶校驗(yàn)碼(Low

Density Parity check codes，LDPC)等，，所討論的錯(cuò)誤檢測(cè)和糾錯(cuò)多用于低層協(xié)議(如鏈路層)以比特串為單位的糾錯(cuò)。

糾錯(cuò)碼糾正的誤碼位置一般是未知的，誤碼位置可知的錯(cuò)誤被稱為刪除錯(cuò)誤，糾正刪除錯(cuò)誤的糾錯(cuò)碼稱為糾刪碼(Erasure Codes)。糾刪碼對(duì)提高網(wǎng)絡(luò)通信的質(zhì)量和可靠性有著重要的意義。

糾刪碼的原理可簡(jiǎn)述為：發(fā)送方將k個(gè)源數(shù)據(jù)包編碼為n(n>k)個(gè)編碼包，將這n個(gè)編碼包在網(wǎng)絡(luò)上傳輸，接收方只要接收到一定數(shù)量的編碼包就可以將原始數(shù)據(jù)恢復(fù)。

目前主要有三類糾刪碼：RS類糾刪碼、級(jí)聯(lián)低密度糾刪碼和數(shù)字噴泉碼。RS類糾刪碼包括范德蒙碼(Vandermonde Code)和柯西碼(Cauchy Code)。級(jí)聯(lián)型低密度糾刪碼(Cascaded Low-Density

Erasure Code)是由級(jí)聯(lián)隨機(jī)稀疏二部圖和一個(gè)傳統(tǒng)的糾刪碼構(gòu)造而成的一種特殊的糾刪碼，如Tornado碼。數(shù)字噴泉碼(Digital

Fountain Codes)的概念由等人于1998年首次提出，在2002年提出了第一類通用的噴泉碼——LT(Luby Transform)碼。

為了克服LT碼的局限性，隨后Shokrollahi提出了Raptor碼，它

由一個(gè)預(yù)編碼和LT碼構(gòu)成，是數(shù)字噴泉碼模型中用于可靠傳輸?shù)淖钚麓a。下面分別介紹這幾類糾刪碼的原理，分析其各自的特點(diǎn)并討論

糾刪碼的應(yīng)用及發(fā)展方向。

RS類糾刪碼

RS碼是一類有很強(qiáng)糾錯(cuò)能力的多進(jìn)制BCH碼，首先由Reed和Solomon于1960年提出，它不僅能糾正突發(fā)錯(cuò)還可以糾正隨機(jī)錯(cuò)誤。RS類糾刪碼根據(jù)其生成矩陣不同分為兩類：范德蒙碼和柯西碼。一個(gè)(m,n)線性糾刪碼可表示為：y=xG，其中x?(x1,x2,?,xm)是元數(shù)據(jù)包向量，y?(y1,y2,?yn)是編碼后得到的數(shù)據(jù)包，Gm?n為線性糾刪碼的生成矩陣。

范德蒙矩陣

1?g0?2?g03G??g0????m??g01g11g22g23g21??gn?1?2?gn?1?3??gn?1?

????m?gn?1??g12g13??g1mg2m即G的任意K列組成的子方陣G'都是非奇異的，因此這樣得到的矩陣滿足糾刪碼生成矩陣的特性。

柯西矩陣

??x?1???x2G????x3??????xm1?y11?y11?y1?1?y11x1?y21x2?y21x3?y2?1xm?y21x1?y31x2?y31x3?y3?1xm?y3??????1x1?yn???1?x2?yn??

1?x3?yn?????1?xm?yn??

其中?x1,x2,?xm?和{y1,y2,?,yn}為同一個(gè)有限域的兩個(gè)元素子集，它們必須滿足：（1）不同子集中的任意兩個(gè)元素相加不能為0（2）這兩個(gè)子集中的每個(gè)元素都不相同。

在有限域上，Ik?k為單位矩陣，Ck?(n?k)為柯西矩陣，若取生成矩陣G?(I/C)，則稱所得到的糾刪碼為柯西碼。

范德蒙碼的編碼時(shí)間復(fù)雜度為O(n2)，解碼時(shí)需要對(duì)矩陣求逆，解2碼時(shí)間復(fù)雜度高于O(n2)。而柯西碼的編碼時(shí)間復(fù)雜度為O(n)，但是柯西碼解碼不用求大矩陣的逆，而且把乘法除法運(yùn)算分別轉(zhuǎn)化為有限域上的加法和減法運(yùn)算，可用異或?qū)崿F(xiàn)，因此，柯西碼運(yùn)算復(fù)雜度低于范德蒙碼。

級(jí)聯(lián)低密度糾刪碼

為了構(gòu)造一種具有低運(yùn)算復(fù)雜度，且能以接近信道容量的速率進(jìn)行傳輸?shù)募m刪碼，Spileman用基于擴(kuò)展圖的LDPC碼，設(shè)計(jì)了具有線性編碼時(shí)間和良好糾錯(cuò)性能的碼，Tornado碼就是如此，其譯碼算法能以很高的概率和O?nln1/??的運(yùn)行時(shí)間恢復(fù)刪除錯(cuò)誤，其編碼時(shí)間為O?nln1/??。Tornado碼不僅提供接近最優(yōu)的損失保護(hù)，而且能以線性時(shí)間編碼和解碼，大大提高了編解碼的速度。

與RS碼相比較，Tornado碼編碼和譯碼過(guò)程只使用簡(jiǎn)單的二進(jìn)制異或運(yùn)算，而RS糾刪碼需要在有限域上進(jìn)行復(fù)雜的矩陣運(yùn)算，因此其編譯碼速度比RS糾刪碼快很多。但是它與RS碼一樣都是具有固定碼率的糾刪碼，其編譯碼算法過(guò)慢，這使得Tornado碼在許多要求低碼率的實(shí)際應(yīng)用中并不適用。

數(shù)字噴泉碼

數(shù)字噴泉碼是一類碼率不受限的糾刪碼(RatelessErasure Codes)，也稱為無(wú)速率編碼，其原理類似噴泉的特性，即從k個(gè)源符號(hào)在線編碼產(chǎn)生的編碼符號(hào)序列是無(wú)限的，每個(gè)編碼符號(hào)等于若干隨機(jī)獨(dú)立選取的源符號(hào)的異或和，接收方只要收到其中任意m個(gè)編碼符號(hào)(m一般略大于k)，就可通過(guò)譯碼以高概率成功恢復(fù)全部k個(gè)源符號(hào)。2002年Luby提出了一類通用的數(shù)字噴泉碼——LT碼，其對(duì)于具有不同刪除概率的各種刪除信道均是最優(yōu)逼近的。LT碼的構(gòu)造中最為關(guān)鍵的是度分布的設(shè)計(jì)，因?yàn)槎确植贾苯記Q定了LT碼的譯碼能否成功，也決定著產(chǎn)生編碼包所需要的運(yùn)算量，LT碼目前采用較多的是Robust

Soliton度分布，該度分布設(shè)計(jì)能以很高的概率成功譯碼。Raptor碼在編碼之前，首先對(duì)數(shù)據(jù)進(jìn)行預(yù)先處理，然后再用LT編碼算法進(jìn)行編碼。由于生成的中間編碼包不同，預(yù)編碼可以分為單層預(yù)編碼技術(shù)和多層預(yù)編碼技術(shù)。

二 糾刪碼編碼與解碼的具體細(xì)節(jié)

假設(shè)數(shù)據(jù)塊B長(zhǎng)度為L(zhǎng)，使用（m,n）線性糾刪碼生成矩陣Gm?n對(duì)其進(jìn)行編碼。具體過(guò)程如下：

（1）將L分割成長(zhǎng)度為m的數(shù)據(jù)段，共有L/m個(gè)段，當(dāng)L/m不是整數(shù)時(shí)，就取整數(shù)位加1，共有[L/m]+1個(gè)段。

（2）對(duì)每一個(gè)段Mi進(jìn)行編碼計(jì)算Mi'?MiGm?n，所有編碼后的段共有n個(gè)列向量Pi，每個(gè)列向量有[L/m]或者[L/m]+1行。

i1,i2,?im?[1,n]，（3）如果接收方收到m個(gè)列向量Pi1,Pi2,?Pim，

?m矩陣，此矩陣的行向量為Si，這m個(gè)列向量組成(L/m)1?i?L/m。利用糾刪碼生成矩陣G中的i1,i2,?im列構(gòu)造m?m矩陣G’，因?yàn)镚’可逆，因此可以得到Si'?Si(G')?1，這樣就恢復(fù)了原數(shù)據(jù)塊B。