礦業固體廢物

[拼音]：fenzuma

[英文]：block code

一類重要的糾錯碼，它把信源待發的資訊序列按固定的κ位一組劃分成訊息組，再將每一訊息組獨立變換成長為n(n＞κ)的二進位制數字組，稱為碼字。如果訊息組的數目為M(顯然M≤2κ)，由此所獲得的M個碼字的全體便稱為碼長為n、資訊數目為M的分組碼，記為[n，M]。把訊息組變換成碼字的過程稱為編碼，其逆過程稱為譯碼。

線性分組碼與非線性分組碼

分組碼就其構成方式可分為線性分組碼與非線性分組碼。

線性分組碼是指[n，M]分組碼中的M個碼字之間具有一定的線性約束關係，即這些碼字總體構成了n維線性空間的一個κ維子空間。稱此κ維子空間為(n，κ)線性分組碼，n為碼長，κ為資訊位。此處M＝2κ。

非線性分組碼[n，M]是指M個碼字之間不存線上性約束關係的分組碼。d為M個碼字之間的最小距離。非線性分組碼常記為[n，M，d]。非線性分組碼的優點是：對於給定的最小距離d，可以獲得最大可能的碼字數目。非線性分組碼的編碼和譯碼因碼類不同而異。雖然預料非線性分組碼會比線性分組碼具有更好的特性，但在理論上和實用上尚缺乏深入研究（見非線性碼）。

線性分組碼的編碼和譯碼

用

V

n表示 GF(2)域的n維線性空間，

V

κ是

V

n的κ維子空間，表示一個(n，κ)線性分組碼。

E

i=（vi1，vi2…，vin）是代表

V

κ的一組基底(i=1，2，…，κ)。以這組基底構成的矩陣

稱為該(n，κ)線性碼的生成矩陣。對於給定的訊息組

m

＝(m1，m2，…，mκ)，按生成矩陣

G

，

m

被編為

mG

＝m1

E

1＋m2

E

2＋…＋mκ

E

這就是線性分組碼的編碼規則。若

之秩為n-κ並且滿足

GH

T=0，僅當

=(v1，v2，…，vn)∈

n滿足

H

T =0時，才為

κ中的碼字。稱

H

為(n，κ)線性分組碼

κ的均等校驗矩陣，稱

H

T為向量

的伴隨式。假設

v

是傳送的碼向量，在接收端獲得一個失真的向量

r

＝

v

＋

E

，式中

E

＝(e1，e2，…，en)稱為錯誤型。由此

r

H

T＝(

v

＋

e

)

H

T＝

e

H

線性碼的譯碼原則便以此為基礎。

漢明碼

這是最早提出的一類線性分組碼，已廣泛應用於計算機和通訊裝置。它是由R.W.漢明於1950年提出的。若碼的均等校驗矩陣

H

由2r-1個、按任一次序排列且彼此相異的二進位制 r維列向量構成。這樣得到的線性分組碼稱為漢明碼，其分組長為n=2r-1，資訊位為κ=n-r =2r-1-r，即為(2r-1，2r-1-r)碼。例如，以矩陣

為均等校驗矩陣的線性分組碼便為(7，4)漢明碼。漢明碼的譯碼十分簡單。例如，假定

=(1001100)為傳送的碼字，其第3位有錯，即接收向量為

r

=(1011100)。於是

恰為矩陣

H

的第 3 列，因而判定原來發送的碼字為

=(1001100)。這種譯碼方式是一般性的。如果接收向量

r

在第i位有錯，則其伴隨式

Hr

T剛好為矩陣

H

的第i列。漢明碼是可以糾正單個錯誤的線性分組碼。

迴圈碼

具有某種迴圈特性的線性分組碼，如果(n，κ)線性分組碼

V

κ具有如下的性質:對於每一個

=(ɑ0，ɑ1，…，

)∈

V

n，只要

∈

V

κ，其迴圈移位(

)亦屬於

V

κ，則稱

V

κ為迴圈碼。迴圈碼的優點在於其編碼和譯碼手續比一般線性碼簡單，因而易於在裝置上實現。使

V

n中的每一個向量

=(ɑ0，ɑ1，…，

)，對應於域GF(2)上的多項式ɑ(x)=ɑ0+ɑ1x +…+

xn-1。於是

V

n中的全體n維向量便與上述多項式之間建立了一一對應的關係。基於這種對應，使

V

n中除了線性運算而外，還建立了向量之間的乘法運算。

A

=(ɑ0，ɑ1，…，

)與

B

=(b0，b1，…，

)的乘積

ab

可視為ɑ(x)b(x)[mod(xn-1)]所對應的向量。因此，一個(n，κ)迴圈碼的生成矩陣及均等校驗矩陣可分別由生成多項式及均等校驗多項式h(x)所代替，從而簡化了編碼及譯碼運算。

BCH碼

它是一類重要的迴圈碼，能糾正多個錯誤。假設m是滿足2m呏1(mod n)的最小正整數，β是域GF(2m)的n次單位原根，作迴圈碼的生成多項式g(x)，以d0-1個接續的元素

為根，其中m0，d0均為正整數，且d0≥2。於是

其中mj(x)代表

的最小多項式。由這個g(x)所生成的，分組長為 n的迴圈碼稱為BCH碼。它由R.C.Bose，D.K.Ray-Chaudhuri及A.Hocquenghem三人研究而得名。BCH碼的主要數量指標是：碼長n，首元指數m0，設計距離d0，資訊位數

（

表示多項式 g(x)的次數）。BCH碼的重要特性在於：設計距離為d0的BCH碼，其最小距離至少為d0，從而可至少糾正

個獨立錯誤。BCH碼譯碼的第一步是計算伴隨式。假設

為傳送碼向量，

為接收向量，而

E

＝(E0，E1，…，En-1)為錯誤向量，或記為

稱為錯誤多項式。於是伴隨向量之諸

S

=(S1，S2，…，S2t)分量Sκ由

決定（κ=1，2，…2t；為簡便計，設m0=1，d0=2t+1）。假設有e個錯誤出現(1≤e≤t)，則對應於e個錯誤的Ei厵0。如果

E

的第j個（從左至右）非零分量是Ei，則稱Xj=βi為這個錯誤Ei的錯位，而稱Yj＝Ei為這個錯誤的錯值。稱

為錯位多項式。BCH碼譯碼的關鍵是由諸sκ(κ=1，2，…，2t)求出

(z)。這可用著名的伯利坎普－梅西迭代演算法來完成。這種演算法相當於線性移位暫存器的綜合問題。最後一步是求出

(z)的全部根，可用錢天聞搜尋演算法完成，從而可以定出接收向量

r

的全部錯位。

裡德-索洛蒙碼

這是一種特殊的非二進位制BCH碼。對於任意選取的正整數s，可構造一個相應的碼長為n=qs-1的q進位制BCH碼，其中碼元符號取自有限域GF(q)，其中q為某一素數的冪。當s=1，q＞2時所建立的碼長為n=q-1的q進位制BCH碼便稱為裡德-索洛蒙碼，簡稱為RS碼。當q=2m(m＞1)，碼元符號取自域GF(2m)的二進位制RS碼可用來糾正成區間出現的突發錯誤。這種碼在短波通道中特別有用。

戈帕碼

這是一種重要的線性分組碼，它不僅包括常見的諸如本原BCH碼等大量的迴圈碼類，還包括相當多的非迴圈線性分組碼類，並且後一種碼具有良好的漸近特性。戈帕碼的理論實質在於將每一個碼向量與一個有理分式相對應。q是某一個素數冪，g(z)是域GF(qm)上的任意多項式，L表示域GF(qm)中所有不為g(z)之根的元素所成之集合，|L|代表L中元素的數目。於是存在一個以GF(q)為符號域，以GF(qm)為位置域的線性分組碼。碼長為|L|，它的各碼元用L中的元素來標誌。這種碼可定義為滿足條件