糾錯(cuò)編碼中的代數(shù)理論與方法

屈龍江，　?！￡浚±睢〕?/p>

(國(guó)防科學(xué)技術(shù)大學(xué)理學(xué)院，湖南長(zhǎng)沙410073)

?

糾錯(cuò)編碼中的代數(shù)理論與方法

屈龍江，海昕，李超

(國(guó)防科學(xué)技術(shù)大學(xué)理學(xué)院，湖南長(zhǎng)沙410073)

[摘要]糾錯(cuò)編碼是保證通信可靠性的重要手段.本文首先介紹了糾錯(cuò)編碼的基本概念和主要數(shù)學(xué)問(wèn)題，然后基于線性代數(shù)、抽象代數(shù)的理論與方法，討論了兩類常見(jiàn)的糾錯(cuò)編碼——線性碼、循環(huán)碼.

[關(guān)鍵詞]糾錯(cuò)編碼； 線性代數(shù)； 抽象代數(shù)； 線性碼； 循環(huán)碼

1問(wèn)題引入

當(dāng)今社會(huì)，信息無(wú)處不在，且已高度數(shù)字化. 各種類型的信息，包括文字、圖片、音頻、視頻等，往往按照一定的編碼格式編成二進(jìn)制比特串，然后送上信道傳輸. 信道也具有多種表現(xiàn)形式，如電話線、網(wǎng)絡(luò)光纖、大氣層(借助于它，嫦娥號(hào)才能傳回月球表面圖片)等. 由于信道質(zhì)量問(wèn)題，信息有時(shí)會(huì)發(fā)生錯(cuò)誤. 如果發(fā)送端不對(duì)信息進(jìn)行任何處理的話，那么接收端接收到信息后就不知道信息是否出錯(cuò)，以及哪位出錯(cuò). 為了解決這個(gè)問(wèn)題，需要在信息中加入冗余. 讓我們先看一個(gè)簡(jiǎn)單例子.

例1電話的噪音很大時(shí)，常常把講話重復(fù)幾遍. 現(xiàn)在把每個(gè)信息0=(00)，1=(10)，2=(01)，3=(11)重復(fù)三遍，即變?yōu)?/p>

0=(000000)，1=(101010)，2=(010101)，3=(111111).

注意到上述4個(gè)信息向量中任兩個(gè)至少有3位不同. 若碼字x只有1位出錯(cuò)變成y，則y與x只有1位不同，而y與其他信息向量至少有2位不同，于是可將y“就近”譯成x，從而糾正該位錯(cuò)誤. 因此，該編碼方法可檢測(cè)2位錯(cuò)誤，并可糾正1位錯(cuò)誤. 但需要說(shuō)明的是，冗余的增加使得通信效率降低了，用6維向量傳遞2位信息，效率減為原來(lái)的1/3.

從上例可看出糾錯(cuò)編碼的本質(zhì). 為了使通信系統(tǒng)具有糾錯(cuò)能力，需要在編碼中加入冗余，而這往往以犧牲效率為代價(jià). 如何在效率降低最少的條件下，獲得最大的糾錯(cuò)能力，就成了糾錯(cuò)編碼理論中一個(gè)最基本的問(wèn)題. 要圓滿解決它，數(shù)學(xué)手段當(dāng)仁不讓.

經(jīng)歷了半個(gè)多世紀(jì)的發(fā)展，糾錯(cuò)編碼理論已成為應(yīng)用數(shù)學(xué)的一個(gè)重要分支，代數(shù)、幾何、組合等數(shù)學(xué)理論與方法日漸滲透其中，取得了非常豐富的成果[1-3]. 盡管如此，許多工科研究生對(duì)糾錯(cuò)編碼往往缺乏了解，即便對(duì)一些修過(guò)糾錯(cuò)碼課程的學(xué)生來(lái)說(shuō)，其中蘊(yùn)涵的數(shù)學(xué)理論，尤其是代數(shù)理論與方法也是淺嘗輒止，未曾掌握.

本文將對(duì)糾錯(cuò)編碼中的代數(shù)理論與方法做一簡(jiǎn)單梳理，目的是向讀者展示這一優(yōu)美的數(shù)學(xué)理論，同時(shí)深化讀者對(duì)代數(shù)學(xué)工具的理解. 在這里，我們假定讀者已經(jīng)學(xué)習(xí)了“線性代數(shù)”理論和“抽象代數(shù)”理論. 否則，請(qǐng)參考文獻(xiàn)[4]，[5].

本文結(jié)構(gòu)如下：第2節(jié)介紹糾錯(cuò)碼的基本概念和主要數(shù)學(xué)問(wèn)題；第3，4節(jié)分別介紹線性碼和循環(huán)碼，基于的主要代數(shù)理論分別是線性代數(shù)和抽象代數(shù)；第5節(jié)是結(jié)束語(yǔ).

2糾錯(cuò)碼的基本概念和主要數(shù)學(xué)問(wèn)題

設(shè)α=(a1，…，an)∈，則wt(α)=#{i|ai≠0}為α的Hamming重量. 由此定義C的最小距離為

證設(shè)發(fā)方發(fā)送x∈C，由于信道干擾，收方收到y(tǒng)=x+ε，其中ε≠0.

圖1

d≤d(x，x′)≤d(x，y)+d(x′，y)，

由三角不等式有

這表明與y距離最小的碼字x即為正確碼字.

定理2.1說(shuō)明一個(gè)糾錯(cuò)碼的最小距離衡量了它的糾錯(cuò)能力.

糾錯(cuò)碼的主要數(shù)學(xué)問(wèn)題：

(i) 構(gòu)造好碼，即構(gòu)造碼率盡可能高、最小距離盡可能大的糾錯(cuò)碼.

(ii) 尋找好的譯碼算法. 一個(gè)碼要想在實(shí)際中取得良好應(yīng)用，必須有好的譯碼方法.

在給定碼長(zhǎng)n和最小距離d的情況下，問(wèn)題(i)就是要尋找盡可能多的碼字，以便其中兩個(gè)不同碼字之間的最小距離≥d. 這是一個(gè)組合數(shù)學(xué)問(wèn)題. 下面有兩個(gè)界.

定理2.2(Hamming界)設(shè)C為q元(n，M，d)碼，則

定義2.3若碼C使得Hamming界成立，則C稱為完全碼(perfect code).

定理2.4(Singleton界)設(shè)C為q元(n，M，d)碼，則M≤qn-(d-1).

定義2.5達(dá)到Singleton界的碼稱為極大距離可分碼(maximal distance separable code，簡(jiǎn)稱MDS碼).

下面將用代數(shù)理論刻畫、構(gòu)造完全碼與MDS碼.

3線性碼

線性碼是最重要、最基本的一類糾錯(cuò)碼，其研究成果也最為豐富，主要原因是可用線性代數(shù)理論研究它.

對(duì)于線性碼，它的最小距離有一個(gè)更簡(jiǎn)單的刻畫.

定義3.3設(shè)C為一個(gè)q元[n，k]線性碼. C的生成矩陣G是以C的一組基為行向量所構(gòu)成的k×n矩陣，即

其中α1，…，αk為C的一組q-基.

對(duì)于線性碼C來(lái)說(shuō)，只要生成矩陣確定了，它的全部碼字也就知道了. 事實(shí)上，C中任意向量c均可表示為c=(x1，…，xk)G，其中(x1，…，xk)∈.

C的對(duì)偶空間稱為C的對(duì)偶碼，記為C⊥，即

C⊥={x∈，?c∈C}.

C⊥的一個(gè)生成陣H稱為C的一個(gè)校驗(yàn)陣，即對(duì)任意c∈C，總有H·cT=0. 事實(shí)上，容易證明對(duì)任意x∈，x∈C當(dāng)且僅當(dāng)H·xT=0. 這也是校驗(yàn)矩陣得名的由來(lái).

生成矩陣和校驗(yàn)矩陣既是線性碼的簡(jiǎn)潔表示，反映其全部性質(zhì)，也是研究線性碼的有力工具，可以給出其性質(zhì)的更多刻畫. 下面是關(guān)于最小距離的一個(gè)例子.

定理3.4設(shè)C為q元[n，k]線性碼，H為C的一個(gè)校驗(yàn)陣，則C的最小距離為d當(dāng)且僅當(dāng)H中任意d-1列線性無(wú)關(guān)，且存在d列線性相關(guān).

對(duì)于線性碼，Singleton界變?yōu)閗≤n-(d-1)，此時(shí)MDS碼有如下刻畫.

定理3.5設(shè)C為q元[n，k]線性碼，則下列四個(gè)條件等價(jià)：

(i)C為MDS碼，即d=n-k+1.

(ii)C的生成陣G中任意k列線性無(wú)關(guān).

(iii) C⊥為MDS碼，即C⊥為[n，n-k，k+1]線性碼.

(iv) C的校驗(yàn)陣H中任意n-k列線性無(wú)關(guān).

證(i) ? (iv).由定理3.4可得.

(iv) ? (i).顯然d≥n-k+1，再由Singleton界d≤n-k+1知恰有d=n-k+1.

(i) ? (ii).設(shè)

其中αi∈若C不是MDS碼，即d≤n-k，則由最小距離定義知C中非零碼字c=(c1，…，cn)至少有k位為零. 不妨設(shè)c1=…=ck=0，則有0≠a=(a1，…，ak)∈，使得

從而

即齊次方程組

考慮到H又是C⊥的生成陣，結(jié)合(i)，(ii)等價(jià)知(iii)，(iv)也等價(jià).

下面介紹利用多項(xiàng)式理論構(gòu)造的一類重要線性碼.

定理3.6(多項(xiàng)式碼)設(shè)a1，a2，…，an是中n個(gè)不同元素，k≤n≤q，定義

C={cf=(f(a1)，f(a2)，…，f(an))|f∈q[x]，degf≤k-1}，

則C為一個(gè)q元[n，k，n-k+1]的MDS碼.

證顯然C為一個(gè)q元n長(zhǎng)線性碼. 由于次數(shù)≤k-1的非零多項(xiàng)式至多有k-1個(gè)零點(diǎn)，故cf=cg當(dāng)且僅當(dāng)f=g，即證C為[n，k]線性碼. 再設(shè)0≠cf∈C，則wt(cf)≥n-k+1，即d≥n-k+1. 另一方面，由Singleton界d≤n-k+1，即證C為MDS碼.

本節(jié)的最后介紹一類重要的完全碼——Hamming碼. 為此，先引入一些概念. 設(shè)α，β為{0}中的任意兩個(gè)向量，定義α，β等價(jià)當(dāng)且僅當(dāng)存在λ∈，使得α=λβ，那么{0}中向量恰好可分成個(gè)等價(jià)類. 在每個(gè)等價(jià)類中任取一個(gè)代表元，作為列向量，構(gòu)造一個(gè)m×n矩陣H，再以H為校驗(yàn)矩陣構(gòu)造一個(gè)線性碼C，稱之為Hamming碼.

定理3.7設(shè)C為如上定義的Hamming碼，則它是參數(shù)為

的q元完全碼.

證顯然

由H的構(gòu)造方法易知它的任意2列是線性無(wú)關(guān)的. 而H中存在3列線性相關(guān)，因此d=3.

又由于

故C為完全碼.

4循環(huán)碼

循環(huán)碼是最重要的一類線性碼，編、譯碼的硬件實(shí)現(xiàn)十分便捷. 已知的大多數(shù)好的糾錯(cuò)碼都是循環(huán)碼.

定義4.1設(shè)C為一個(gè)q元n長(zhǎng)的線性碼，若對(duì)任意c=(c0，c1，…，cn-1)∈C，總有

(cn-1，c0，c1，…，cn-2)∈C，

則稱C為循環(huán)碼.

本文中均假定(n，q)=1，這是因?yàn)楹玫募m錯(cuò)碼大都屬于此種情形. 此時(shí)循環(huán)碼也可視為一個(gè)理想. 因此，對(duì)它的研究不僅可使用線性代數(shù)理論工具，更需要抽象代數(shù)的理論與方法. 這正是循環(huán)碼的研究結(jié)果特別豐富、構(gòu)造的好碼的數(shù)量尤為可觀的根本原因.

定義如下映射

φ:=q[x]/(xn-1)，

定理4.2設(shè)C為一個(gè)q元n長(zhǎng)的線性碼，則C為循環(huán)碼當(dāng)且僅當(dāng)φ(C)為中的理想.

degg=n-k，

其中k=dimC，C=(g(x))={a(x)g(x)|a(x)∈q[x]，dega

循環(huán)碼具有多種描述方式. 如上所述，我們可用其生成式或校驗(yàn)式來(lái)刻畫，即對(duì)任意c∈，有

c∈C ? c(x)h(x)=0 ? g(x)|c(x).

另一方面，設(shè)

為其在分裂域中的分解，則由g(x)|xn-1與(n，q)=1知α1，…，αn-k為不同的n階單位根. 進(jìn)一步

c∈C?g(x)|c(x)?c(αi)=0，1≤i≤n-k.

于是，也稱C是以α1，…，αn-k為根的循環(huán)碼. 這表明循環(huán)碼也可用它的根來(lái)表示. 利用該表示，我們可以就給出著名的BCH碼.

叫做設(shè)計(jì)距離為δ的BCH碼. 若n=qm-1，即，則此時(shí)的BCH碼也稱為本原BCH碼.

定理4.4設(shè)C為如上定義的BCH碼，則C的最小距離d≥設(shè)計(jì)距離δ.

即

記H=[β(i+l)j]0≤i≤δ-2，0≤j≤n-1為上述齊次線性方程組的系數(shù)矩陣，則H可視為C在擴(kuò)域中的一個(gè)校驗(yàn)陣. 取H的任意δ-1列，不妨設(shè)為i1，i2，…，iδ-1列，考慮對(duì)應(yīng)的δ-1階子式

由于βi1，βi2，…，βiδ-1兩兩不同且均不為零，而上式右邊的Vandermonde行列式也不為零，從而H的任意δ-1列線性無(wú)關(guān). 由定理3. 4可知d≥δ.

m1(x)=(x-β)(x-β2)(x-β4)(x-β8)(x-β16)，

則β3，β5，β7的極小多項(xiàng)式分別為

m3(x)=(x-β3)(x-β6)(x-β12)(x-β24)(x-β17)，

m5(x)=(x-β5)(x-β10)(x-β20)(x-β9)(x-β18)=m9(x)，

m7(x)=(x-β7)(x-β14)(x-β28)(x-β25)(x-β19).

令g(x)=m1(x)m3(x)m5(x)m7(x)，則C=(g(x))為一個(gè)本原BCH碼，且其設(shè)計(jì)距離為9. 由m9(x)=m5(x)知，C的最小距離≥11.

上例表明BCH界不緊. 給出BCH碼最小距離的精確公式或更好的下界是一個(gè)很重要也很難的數(shù)學(xué)問(wèn)題.

相較一般線性碼，BCH碼的代數(shù)結(jié)構(gòu)更好，所以它具有更高效的譯碼算法，比如廣為熟悉的B-M綜合算法[1]. 另一方面，BCH碼還能設(shè)計(jì)出任意大的最小距離，因此BCH碼在實(shí)際中得到了廣泛應(yīng)用，特別是下面的一個(gè)子類.

定義4.6設(shè)α是q的一個(gè)本原元，n=q-1，2≤d≤n，以α，α2，…αd-1為根的q元n-1長(zhǎng)的BCH碼叫做Reed-Solomon碼(RS碼)，即

顯然RS碼C的生成式為

從而C的維數(shù)k=n-d+1. 由BCH界知C的最小距離≥d，結(jié)合Singleton界知C的最小距離恰為d，即證RS碼為MDS碼.

RS碼事實(shí)上是定理3. 6中多項(xiàng)式碼的子類. 為說(shuō)明這一點(diǎn)，設(shè)={1，α，α2，…，αq-2}，定義如下一類多項(xiàng)式碼

C′={cf=(f(1)，f(α)，f(α2)，…，f(αq-2))|f∈q[x]，degf≤k-1=n-d}.

5結(jié)束語(yǔ)

從前文可以看出，在線性碼和循環(huán)碼研究中，線性代數(shù)和抽象代數(shù)理論與方法起到了十分重要而深刻的作用. 事實(shí)上，上述內(nèi)容已有幾十年的歷史，屬于經(jīng)典糾錯(cuò)碼的范疇. 現(xiàn)代糾錯(cuò)編碼理論更加豐富多彩，涌現(xiàn)了代數(shù)幾何碼、有限環(huán)上編碼、網(wǎng)絡(luò)編碼、量子糾錯(cuò)碼、空時(shí)碼等富有活力的新分支，而對(duì)這些內(nèi)容的研究用到了更多、更深刻、更現(xiàn)代的代數(shù)理論. 比如代數(shù)幾何碼以代數(shù)幾何、代數(shù)曲線理論為基本研究工具，有限環(huán)上編碼以有限環(huán)論為基本研究工具，量子糾錯(cuò)碼的基本研究工具是復(fù)向量空間，空時(shí)碼的研究用到了豐富而深刻的群表示理論等等. 綜上，糾錯(cuò)編碼中的代數(shù)理論與方法研究豐富多彩、魅力迷人，無(wú)論從理論上還是在實(shí)踐中都有重要的意義. 我們希望更多的青年才俊投身該領(lǐng)域的研究之中.

[參考文獻(xiàn)]

[1]馮克勤. 糾錯(cuò)碼的代數(shù)理論[M]. 北京：清華大學(xué)出版社，2005.

[2]MacWilliamsFJ，SloaneNJA.TheTheoryofError-CorrectingCodes[M].Amsterdam:North-HollandPublishingCompany， 1977.

[3]VanLintJH.IntroductiontoCodingTheory[M]. 3thed.Berlin:Springer-Verlag， 2000.

[4]馮良貴，戴清平，李超，謝端強(qiáng). 線性代數(shù)與解析幾何[M]. 北京：科學(xué)出版社，2008.

[5]李超，謝端強(qiáng)，馮良貴，戴清平. 代數(shù)學(xué)基礎(chǔ)[M]. 長(zhǎng)沙：國(guó)防科技大學(xué)出版社，2000.

AlgebraicTheoryandMethodsofError-CorrectingCode

QU Long-jiang，HAI Xin，LI Chao

(CollegeofScience，NationalUniversityofDefenseTechnology，Changsha，Hunan410073，China)

Abstract:Error-correctingcodeisanimportantmeansofensuringthereliabilityofcommunication.ThefundamentalconceptionsandprimarymathematicalproblemsofError-correctingcodeareinitiallypresented.Thenbasedonthetheoryandmethodsoflinearalgebraandabstractalgebra,twotypesofthefamiliarerror-correctingcode,linearcodeandcycliccode,arefurtherdiscussed.

Keywords:error-correctingcode;linearalgebra;abstractalgebra;linearcode;cycliccode

[中圖分類號(hào)]O29

[文獻(xiàn)標(biāo)識(shí)碼]A

[文章編號(hào)]1672-1454(2015)01-0007-07