分組碼的幾種碼限的討論

馮天樹(shù)

（北京科技大學(xué)天津?qū)W院，天津 301830）

0 引言

給定q元信息，位長(zhǎng)k，增加m=n-k個(gè)監(jiān)督編碼元，編碼為n長(zhǎng)碼n(n＞k)，構(gòu)成分組碼(n,k,d)或(q,n,k,d)。分組碼用符號(hào)(q,n,k,d)表示，包括線性分組碼和非線性分組碼。線性分組碼下文中也用符號(hào)[q,n,k,d]表示，是群碼，有封閉性和包含全0碼字。

設(shè)C是q元n長(zhǎng)碼，即C是的子集。d是碼C的最小距離，表示為：

式中：d(x,y)表示x和y的漢明距離，即x和y不相同的位數(shù)。

如何構(gòu)造(q,n,k,d)碼達(dá)到香農(nóng)極限，一直是信道編碼工作者們追求的目標(biāo)，科學(xué)家們?cè)诓粩嗟貥?gòu)造出新的好碼。在構(gòu)造新碼的過(guò)程中，不可不免地遇到一個(gè)問(wèn)題：哪些碼可以構(gòu)造出來(lái)，哪些碼構(gòu)造不出來(lái)，如果能構(gòu)造出來(lái)，那么該如何構(gòu)造？現(xiàn)在信道編碼理論中出現(xiàn)了分組碼的四個(gè)限或界（bound）：漢明限、Plotkin 限、Singleton 限，Gilbert-Varshamov 限。但所有信道編碼教材都對(duì)幾碼限介紹的非常簡(jiǎn)潔，本文對(duì)這四個(gè)碼限進(jìn)行詳細(xì)的討論和分析，希望對(duì)信道編碼工作者在構(gòu)造達(dá)到香農(nóng)極限的新碼時(shí)有所幫助。

1 幾種碼限

1.1 漢明限

1.1.1 碼限問(wèn)題

漢明給出了分組碼(q,n,k,d)的d的一個(gè)上限，這就是漢明限[1]。漢明限為：

說(shuō)明：

（1）漢明限是必要條件，不是充分的。所有的碼必須滿足此條件，不滿足的這條件的碼肯定不存在。

當(dāng)式（1）取等號(hào)時(shí)的碼叫完備碼。令d=2t+1，參數(shù)為(n,k,2t+1)的q元完備碼滿足：

但遺憾的是滿足式（3）的q、n、k、d很少。

Golay 求出滿足式（3）的參數(shù)(q,n,k,d)的只有(2,23,12,7)，(2,90,78,5)，(3,11,6,5)三組；但Golay 發(fā)現(xiàn)二元(90,78,5)不存在[2]，只存在二元(23,12,7)碼和三元(11,6,5)碼。二元Golay (23,12,7)碼滿足：

完備的線性分組碼只有以上幾種，后來(lái)數(shù)學(xué)家們找到一些非線性的q元完備碼[2]。

（2）q元(n,n,1)碼是完備碼，但毫無(wú)糾錯(cuò)能力，沒(méi)增加任何校驗(yàn)位。

（3）二元碼(2t+1,1,2t+1)奇數(shù)長(zhǎng)的重復(fù)碼，是完備碼，許用碼組只有兩個(gè)碼：全1 碼、全0 碼。

（4）q元漢明碼的碼距d=3，是碼。q=2 時(shí)，為(2m-1,2m-1-m,3)，m=n-k是監(jiān)督位個(gè)數(shù)。

（5）并不是任意給定q、n、k、d，都能構(gòu)造出相應(yīng)的(q,n,k,d)碼，使q、n、k、d滿足式（2）的約束。

對(duì)達(dá)不到漢明限的非完備碼，有個(gè)覆蓋半徑問(wèn)題。

1.1.2 覆蓋半徑問(wèn)題

[定義1]覆蓋半徑：碼集合C（許用碼組）是的子集，以每一個(gè)屬于C的碼v為球心，以ρ為半徑的球，對(duì)許用碼組的所有碼字做這樣的球，讓這些球并集等于。最小的ρ稱(chēng)為碼C的覆蓋半徑，記為t(C)。

線性分組碼的t(C)實(shí)際上是編碼矩陣陪集首（或譯碼校驗(yàn)子）的最大漢明重量[1]，即：

[定義2]每一個(gè)屬于C的碼v為球心，以ρ為半徑的球，所有球不相交的半徑ρ的最大值叫碼C的球半徑，記為S(C)。

顯然有：

如果t(C)=S(C)，式（2）取等號(hào)，碼C就是完備碼。例如，漢明碼C的=1=S(C)，二元Golay 碼(23,12,7)的=3=S(C)。

對(duì)非完備分組碼C求覆蓋半徑t(C)，是一非常難的問(wèn)題，數(shù)學(xué)家們一直在探索[3-4]，覆蓋半徑t(C)和相應(yīng)的碼的碼重分布沒(méi)有對(duì)應(yīng)關(guān)系，雖然線性碼的最小碼重等于最小碼距。

t(C)越小，空間中包含的許用碼組的碼字越多，越接近完備碼，因而t(C)越小的碼越好。但如何構(gòu)造小t(C)的碼，人類(lèi)仍然未知。

1.2 Plotkin 限

1.2.1 碼 限

Plotkin 也給出了線性分組碼[q,n,k,d]的d的一個(gè)上限，被稱(chēng)為Plotkin 限[5]，碼限為：

Plotkin 是根據(jù)同一[n,k]線性分組碼，有qk(n-k)個(gè)不同的生成矩陣；每個(gè)矩陣產(chǎn)生的許用碼組的總重量相同，為n(q-1)qk-1；每碼的非零最小碼重（最小碼距）不會(huì)大于平均碼重：。

對(duì)非線性分組碼(q,n,k,d)，M是碼字總數(shù)(對(duì)應(yīng)線性碼的qk)，有如下結(jié)論：

證明思路是分組碼的總距離小于等于nM2(q-1)/q，再除以總碼子對(duì)M(M-1)。

式（8）的條件也是[q,n,k,d]碼存在的必要條件，分組碼必須滿足此條件。

1.2.2 等重碼

[定義3]等重碼：式（8）取等號(hào)時(shí)的碼叫等重碼或單純碼（simplex code），這時(shí)碼組的所有非零碼的碼重一樣。

線性等重碼的性質(zhì)如下：

（1）可以證明[6]：q元等重線性碼[q,n,k,d]是q元漢明碼的對(duì)偶碼，對(duì)漢明碼m=n-k是監(jiān)督位長(zhǎng)度，對(duì)等重碼m是信息位長(zhǎng)度。

（2）當(dāng)q=2時(shí)，二進(jìn)制線性等重碼[2m-1,m,2m-1]，碼 長(zhǎng)n為2m-1，信息位數(shù)為m，校驗(yàn)位數(shù)2m-1-m，許用碼組個(gè)數(shù)為2m，每個(gè)非零碼字的重量（碼距）是，例如，[3,2,2]、[7,3,4]、[15,4,8]碼等等。

（3）以等重碼所有許用碼為行構(gòu)成碼矩陣，碼矩陣的列數(shù)比行數(shù)多一，即是(2m-1)×2m矩陣。

（4）因?yàn)榈戎卮a的碼矩陣的列互換，碼的重量不變，那么碼矩陣列互換不影響碼重或碼距，生成矩陣列互換即可得到。

1.2.3 二元碼線性等重碼的構(gòu)造方法

（1）方法1

先構(gòu)造漢明碼，再用漢明碼的H矩陣做G矩陣即可生成等重碼。m（信息位個(gè)數(shù)）位二元共2m個(gè)組合，去除全0 碼，剩下的2m-1 列構(gòu)成的矩陣就是等重碼的生成矩陣。

也可用循環(huán)碼生成，xn-1=g(x)h(x)，單純碼的生成多項(xiàng)式是其對(duì)偶漢明循環(huán)碼的h(x)。

（2）方法2

將2m×2m階0,1 Walsh-Hardamark 矩陣(即 將普通±1 的Walsh-Hardamark 矩陣的1 變?yōu)?、-1變?yōu)?)，去掉全0 列，得到(2m-1)×2m矩陣即為許用碼矩陣[7]。

非線性等重分組碼這里不做討論。

1.3 Singleton 限

1.3.1 碼限

設(shè)Aq(n,d)表示長(zhǎng)為n最小碼距為d的q元分組碼所能容納的碼字個(gè)數(shù)的最大值，即Aq(n,d)=max{M|存在分組碼(n,m,d),給定n,d}。

Singleton給出了分組碼(n,k,d)的Aq(n,d)的上限：

當(dāng)分組碼為線性碼[n,k,d]時(shí)，d的上限為：

這時(shí)碼限與q無(wú)關(guān)。

式（10）和式（11）表示的極限叫Singleton 限。對(duì)線性分組碼，Singleton 的證明思路是：對(duì)線性分組碼，最小碼距是最小的非0 碼重，此時(shí)信息位不可能全0，至少一個(gè)1，而n-k位監(jiān)督信息最多有n-k個(gè)1，所以最小的非0 碼重至少為n-k+1。

1.3.2 MDS 碼

[定義4]使式（11）等號(hào)成立的碼叫極大距離可分（Maximum Distance Separable，MDS）碼，此時(shí)達(dá)到Singleton 限.

對(duì)二進(jìn)制線性分組碼，只有重復(fù)碼(n,1,n)奇偶校驗(yàn)碼(n,n-1,2)及(n,n,1)碼，這三類(lèi)碼是MDS 碼，叫平凡MDS 碼。2 ≤k≤n-2 的(n,k,d)MDS 碼叫非平凡MDS 碼。

對(duì)二進(jìn)制線性碼，MDS 碼都是平凡MDS 碼，沒(méi)有非平凡的MDS碼。因?yàn)閝=2時(shí)n=3，(3,1,3)，(3,2,2)碼都是平凡碼。

著名的里德-所羅門(mén)（Reed-Solomon，RS）碼q=2，n=q-1=2m-1 是非平凡多進(jìn)制MDS 碼。

線性[n,k,n-k+1]MDS 碼的對(duì)偶碼是[n,n-k,k+1]碼，也是MDS 碼。

1.3.3 MDS 碼的猜想

設(shè)M(k,d)=max{n|存在(q,n,k,n-k+1)碼}

[命題1]如果q≤k，那么M(k,d)=k+1

q元分組MDS 碼猜想[8]為：

對(duì)線性碼，設(shè)m(k,d)=max{n|存在線性碼(q,n,k,n-k+1)}

這猜想至今沒(méi)被完整證明，只部分被證明，n、k、d是小數(shù)字時(shí)可以驗(yàn)證。

1.3.4 多項(xiàng)式碼

[定義5]多項(xiàng)式碼：設(shè)a1,a2,…,an是Fq中n個(gè)不同的元素(n≤q)(1 ≤k≤n)，則集合：

是q元[n,k,d]線性MDS 碼。

可以證明多項(xiàng)式碼的d=n-k+1，只要多項(xiàng)式的次數(shù)小于等于k-1,n≤q，則可構(gòu)造一大類(lèi)MDS 碼。擴(kuò)展RS 碼是f(x)取固定某函數(shù)的特殊多項(xiàng)式碼，多項(xiàng)式碼提供了一大類(lèi)構(gòu)造MDS 碼的方法。

1.4 Gilbert-Varshamov 限

1.4.1 碼 限

Gilbert 用代數(shù)的方法證明分組碼(n,M,d)（不一定線性），如果存在下關(guān)系：

那么這樣的(n,M,d)分組碼一定存在。

如果線性分組碼[q,n,k,d]存在以下關(guān)系：

或者是：

那么這樣的線性[n,k,d]碼一定存在，這就是Gilbert 限，該條件是碼存在的充分條件，不是必要的。

Gilbert 的證明思路：以許用碼的每碼字為中心，以d-1 為半徑的漢明球的并的集合個(gè)數(shù)，肯定超過(guò)的元素個(gè)數(shù)。

Varshamov 用概率統(tǒng)計(jì)的對(duì)線性分組碼方法證明了：

設(shè)q≥2，對(duì)每個(gè)，且0＜ε≤1-Hq(δ)，那么一定存在(n,k,d)碼

式中：R=k/n，δ=d/n，Hq(δ)是q元熵函數(shù)：

可以證明式（16）當(dāng)n→∞時(shí)和（18）是一樣的，都稱(chēng)Gilbert-Varshamov（GV）限。

式（16）叫非漸進(jìn)GV 限，式（18）叫漸進(jìn)GV 限。

1.4.2 碼限說(shuō)明

式（16）這個(gè)限很松，給定n和k，d存在下限，或給定n和k，d存在下限。當(dāng)n、k、d、q是小數(shù)字時(shí)，漢明碼、等重碼、RS 都比非漸近GV 限好；但比式（16）下限小的碼，是存在的。

[命題2]更緊的非漸進(jìn)GV 限是：

t(C)碼C的覆蓋半徑，所以求碼的覆蓋半徑很重要。證明略。

[命題3]對(duì)任意(n,k)線性分組碼，總存在d=1的碼。

證明：當(dāng)生成矩陣的第k行為n長(zhǎng)(0,0,…,0,1)或第k行有奇數(shù)個(gè)1 時(shí)，當(dāng)發(fā)送信息為k長(zhǎng)的(0,0,…,0,1)時(shí)，碼字為n長(zhǎng)(0,0,…,0,1)，最小非0碼重為1，所以d=1。

[命題4]式（16）的等號(hào)，不可能存立，除非d=1。

證明：因?yàn)槿〉忍?hào)時(shí)，以碼為球心以d-1 為半徑的球，會(huì)兩不相交，并覆蓋整個(gè)空間。這等效于：完備碼的以碼為球心以(d-1)/2 為半徑的球覆蓋整個(gè)空間，(d-1)/2=d-1，所以d=1。證畢。

2 4 種碼限的比較和說(shuō)明

如圖1 所示是q=2 時(shí)的幾種限。

圖1 二進(jìn)制碼限

圖1 中Plotkin bound2 曲線是：

2.1 對(duì)幾種碼限的比較說(shuō)明

2.1.1 說(shuō)明一

在幾種上限（Plotkin、漢明、Singleton）中，任意一碼，只能滿足3個(gè)限中最小的。圖1中，R＜0.4時(shí)，碼限應(yīng)小于Plotkin 限；R＞0.4 時(shí)，碼限應(yīng)小于漢明限。意味著：想構(gòu)造完備碼，R必須是大于0.4高碼率碼；想構(gòu)造等重碼，必須R小于0.4。

例如：

二進(jìn)制漢明碼(15,11,3) 碼，其Plotkin 限為dplotkin=7，其Singleton 限為dsingleton=4。

真實(shí)d=3 ＜dplotkin，d＜dsingleton。

二進(jìn)制等重碼(15,4,8) 碼，其漢明限為dhamming=7，其Singleton 限為dsingleton=15-4+1=12。

因?yàn)椋?15-4＞C(15,0)+C(15,1)+C(15,2)+C(15,3)

等重碼也是滿足漢明限。

二進(jìn)制等重碼(15,4,8)碼在GV 限曲線的上面，則：

2.1.2 說(shuō)明二

GV 限條件是充分條件不是必要的，分組碼可以位于GV限曲線的下面，并不是所有的碼都滿足GV限。

例如(15,4,5)碼：

但該碼存在。

2.1.3 說(shuō)明三

表1 是n=16 的所有k的二進(jìn)制循環(huán)碼及其最小d。

表1 n=16 的所有k 的二進(jìn)制循環(huán)碼及其最小d 的碼限

圖2 是n=16 的所有k的二進(jìn)制循環(huán)碼在碼限圖上的情況（小圓圈）。

圖2 n=16 的所有k 的二進(jìn)制循環(huán)碼及其最小d 的碼限

2.2 關(guān)于Singleton 限圖的一個(gè)問(wèn)題的解釋

在圖1 的碼限圖中，Singleton 限曲線在漢明限曲線和Plotkin 限曲線的上面，而漢明限Plotkin 限是必要條件。讓人感到奇怪的是：達(dá)到Singleton 限的MDS 碼，怎么會(huì)滿足漢明限和Plotkin 限呢？下面舉例說(shuō)明。

例如：RS 碼(7,2,3)(t=1,q=8)滿足漢明限。滿足Plotkin 限。

這是因?yàn)閳D1 畫(huà)的二進(jìn)制碼限圖，滿足Singleton 限的MDS 碼應(yīng)是q進(jìn)制碼（不是二進(jìn)制），且必須滿足q＞n，而把Singleton 限畫(huà)在二進(jìn)制碼限圖上（某些文獻(xiàn)也這樣畫(huà)Singleton 限曲線），就會(huì)產(chǎn)生誤解。

3 碼限對(duì)香農(nóng)信道編碼定理的意義

香農(nóng)給出了著名的信道編碼定理：在存在差錯(cuò)概率的信道上，如果傳送碼率不超過(guò)信道容量C，那么一定存在一種糾錯(cuò)編碼的方法，使接收端能夠無(wú)誤碼接收。香農(nóng)信道定理的證明的方法是：隨機(jī)碼、碼長(zhǎng)n無(wú)窮長(zhǎng)和最大似然譯碼。

香農(nóng)在信道編碼定理中使用隨機(jī)碼和n→∞時(shí)，當(dāng)R=k/n＜信道容量C，那么平均誤碼率將趨近0。R＜C；但R不能趨近0，R越接近C，碼越好。

從上文中的幾個(gè)碼限可以得出，為達(dá)到香農(nóng)限，不可能無(wú)限增加d，因?yàn)閐的增大是受碼限約束的，并且d的增大對(duì)Pe的減少是有限的，為達(dá)到香農(nóng)限只能想別的辦法。

[定義6]q≥2，設(shè)有一組{ni}i≥1，是一組遞增的分組碼長(zhǎng)度，假設(shè)存在序列{ki}i≥1和{di}i≥1，使得存在q元分組碼Ci=(ni,ki,di)，那么碼序列Ci={Ci}i≥1是碼序列。C的碼率定義為：對(duì)漢明碼CH∶ni=2i-1，ki=2i-1-i，di=3，R(CH)=1，δ(CH)=0。

而構(gòu)造香農(nóng)碼要求：R＜信道容量C，要Pe→0，δ不能→0，否則沒(méi)糾錯(cuò)能力。R不能→0，否則Pe→0 的代價(jià)不是在R略小于容量C時(shí)得到的。顯然漢明碼不能滿足香農(nóng)定理的要求。

同樣，等重碼簇的R=0，δ=0.5，RS 碼簇、MDS 碼簇都不能滿足n→∞時(shí)，R和δ能同時(shí)保持大于0，不趨近0。

漸進(jìn)GV 限，如式（18），對(duì)構(gòu)造香農(nóng)碼的意義：是否存在能用代數(shù)方法規(guī)則構(gòu)造出來(lái)的碼，n→∞時(shí)R和δ能同時(shí)保持大于0，不趨近0。

所以數(shù)學(xué)家們?cè)跇?gòu)造n→∞時(shí)R、δ都不趨近0 的碼。1972 年Justesen 構(gòu)造出這種碼，但離漸進(jìn)GV 限有點(diǎn)距離。

現(xiàn)在數(shù)學(xué)家們把碼空間的碼解釋為代數(shù)幾何中的影射空間的曲線，在構(gòu)造漸進(jìn)GV 碼如仙農(nóng)碼方面有一定的進(jìn)展[9]。

4 結(jié)語(yǔ)

本文對(duì)信道編碼中的分組碼的漢明限、Plotkin限、Singleton 限、Gilbert_Varshamov 限四種距離限進(jìn)行了討論和分析，說(shuō)明達(dá)到這些限時(shí)的碼的性質(zhì)和碼的構(gòu)造方法，并對(duì)這些碼限進(jìn)行了比較和分析。結(jié)果說(shuō)明：要降低誤碼率到達(dá)香農(nóng)限，增加碼距的作用對(duì)是有限的，關(guān)鍵還是靠增加碼長(zhǎng)和構(gòu)造新的編譯碼方法。這些碼限特別是GV 限對(duì)構(gòu)造香農(nóng)理想碼有重要意義。這種思路和工程界構(gòu)造的Turbo碼、LDPC 碼和polar 碼，不是一條思路。另外，分組碼還有Johnson限、Griesmer限、Elias-Bassalygo限，本文未做討論。