循環(huán)碼的編碼方法研究

摘 要 本文對循環(huán)碼的編碼方法進行了深入的分析和探討，循環(huán)碼具有很高的可靠性，在通信、軍事等領(lǐng)域應(yīng)用非常廣泛。

關(guān)鍵詞 循環(huán)碼 編碼

中圖分類號：G202文獻標(biāo)識碼：A

0 引言

循環(huán)碼是線性分組碼最重要的子集。它除了具有線性分組碼的一般性質(zhì)外，還有許多特殊的性質(zhì)，這些性質(zhì)有助于按照要求的糾錯能力系統(tǒng)地構(gòu)造這類碼，并且簡化譯碼算法。循環(huán)碼還有易于實現(xiàn)的特點，很容易用帶反饋的移位寄存器實現(xiàn)其硬件。正是由于循環(huán)碼具有碼的代數(shù)結(jié)構(gòu)清晰、檢糾錯能力強、編譯碼易于實現(xiàn)，具有很高的可靠性等特點，因此在通信、軍事等領(lǐng)域應(yīng)用非常廣泛。

1 循環(huán)碼的相關(guān)概念

1.1 循環(huán)碼的特性

表1給出了（7，3）循環(huán)碼的所有碼字，我們可以直觀的看出循環(huán)碼具有如下特性：（1）封閉性。（線性性）：任何許用碼組的線性和還是許用碼組。（2）循環(huán)性：任何許用的碼組循環(huán)移位后的碼組還是許用碼組。

表1 （7，3）循環(huán)碼

1.2 循環(huán)碼的碼多項式

用碼多項式來表示來表示循環(huán)碼，可以方便的利用代數(shù)理論對其進行研究。若許用碼字為C = (，，…，)：，碼多項式可表示為：C(x) =++ … + c1x + c0其中：對于二元碼組，多項式的每個系數(shù)是0或者1； x僅是碼元位置的標(biāo)志，并不關(guān)心x的取值。

利用碼多項式可以方便的表示循環(huán)移位特性。若C(x) 是一個長為n的許用碼字，則xi C(x) （左乘xi）在按模xn+1運算下，亦是一個許用碼字，也就是：xiC(x) = Ci(x) （模xn + 1），正是C(x) 代表的碼組向左循環(huán)移位次的結(jié)果。

1.3 循環(huán)碼的生成多項式和生成矩陣

循環(huán)碼的生成多項式g(x)是一個常數(shù)項為1，且能除盡xn + 1的r = n - k次多項式；循環(huán)碼中其它碼多項式都是g(x)的倍式。由生成多項式可以表示出生成矩陣G(x)為：

1.4 循環(huán)碼的監(jiān)督多項式和監(jiān)督矩陣

利用循環(huán)碼的特點來確定監(jiān)督矩陣H， 由于循環(huán)碼中是的因式，因此可令：h(x) == xk + hk-1xk-1 + … + h1x + 1，這里稱為監(jiān)督多項式。

與G(x)相對應(yīng)，監(jiān)督矩陣表示為：

其中：h*(x)是h(x)逆多項式，h*(x) = xk + h1xk-1 + h2xk-2 + … + hk-1x + 1。

2 循環(huán)碼編碼的具體實現(xiàn)方法

2.1 利用生成矩陣編碼

2.1.1 求解生成多項式

根據(jù)g(x)的特性，g(x)是xn + 1的一個r次因式。因此，先對xn + 1進行因式分解，找到它的r次因式。以（7，3）循環(huán)碼為例進行分析：

第一步：對x7 + 1進行因式分解得：x7 + 1 = (x + 1)(x3 + x2 + 1)(x3 + x + 1)

第二步：構(gòu)造生成多項式g(x)，即找r = n - k = 4次因子。不難看出，這樣的因子有兩個，即：

(x + 1)·(x3 + x2 + 1) = x4 + x2 + x + 1

(x + 1)·(x3 + x+ 1) = x4 + x3 + x2 + 1

2.1.2 編碼

由g(x)得到生成矩陣為：

循環(huán)碼是線性碼的一種，根據(jù)線性碼編碼的特點，生成矩陣確定，碼組也就確定了。

C = mG

其中，C是編碼之后的碼字，m是信息碼元序列，G是生成矩陣。

2.2 利用監(jiān)督矩陣編碼

由h*(x)得到監(jiān)督矩陣為：

根據(jù)線性碼編碼的特點，監(jiān)督矩陣確定，碼組也就確定了。

HCT = 0其中，C是編碼之后的碼字，H是監(jiān)督矩陣。

2.3 循環(huán)碼的系統(tǒng)碼編碼方法

設(shè)要產(chǎn)生(n，k)循環(huán)碼，m(x)表示信息多項式，編碼步驟如下：

（1）用xn-k乘m(x)。根據(jù)碼多項式的特點，左乘xn-k實際上是把信息位左移位(n-k)，即在信息碼后加上(n-k)個“0”。例如，信息碼為110，它相當(dāng)于m(x) = x2 + x。當(dāng)n-k = 7-3 = 4時， xn-k·m(x) = x6 + x5，它相當(dāng)于1100000。而希望的到得系統(tǒng)循環(huán)碼多項式應(yīng)當(dāng)是C(x) = xn-k·m(x) + r(x)

（2）求r(x)。由于循環(huán)碼多項式C(x)都可以被g(x)整除，也就是：

==+

（3）求C(x)，C(x) = xn-k·m(x) + r(x)

例如，對于（7，3）循環(huán)碼，若選用g(x) = x4 + x2 + x + 1，信息碼110時，則： = ，求得r(x) = x2 + 1，這時的編碼輸出為：1100101。

3 結(jié)論

本文深入系統(tǒng)地分析了循環(huán)碼的編碼技術(shù)。隨著數(shù)字技術(shù)的高速發(fā)展，循環(huán)碼糾錯技術(shù)已經(jīng)廣泛應(yīng)用于各種通信系統(tǒng)中。其編碼和譯碼都可以通過簡單的反饋移位寄存器來完成，實現(xiàn)簡單，糾錯能力強 ，可以降低誤碼率，保證數(shù)據(jù)傳輸?shù)目煽啃裕蟠筇岣咄ㄐ刨|(zhì)量。

參考文獻

[1] 周蔭清.信息理論基礎(chǔ)[M].北京:北京航空航天大學(xué)出版社，2006.9.

[2] 李國華.循環(huán)碼在數(shù)字通信中的應(yīng)用[J].信息技術(shù)，2003.7.

[3] 鄧友娥.循環(huán)碼糾錯在編譯碼中的應(yīng)用[J].韶關(guān)學(xué)院學(xué)報，2004.6.