【文章內(nèi)容簡介】 。正是由于循環(huán)碼具有碼的代數(shù)結(jié)構(gòu)清晰、性能較好、編譯碼簡單和易于實(shí)現(xiàn)的特點(diǎn)，因此在目前的計(jì)算機(jī)糾錯(cuò)系統(tǒng)中所使用的線性分組碼幾乎都是循環(huán)碼。它不僅可以用于糾正獨(dú)立的隨機(jī)錯(cuò)誤，而且也可以用于糾正突發(fā)錯(cuò)誤。 在描述循環(huán)碼之前，先看以下例子。 設(shè)（ 7， 4）漢明碼 C的生成矩陣和校驗(yàn)矩陣為： 于是可以得到相應(yīng)的 16 個(gè)碼組： （ 1000101）（ 0001011）（ 0010110）（ 0101100）（ 1011000）（ 0110001）（ 1100010）（ 0100111）（ 1001110）（ 0011101）（ 0111010）（ 1110100）（ 1101001）（ 1010011）（ 1111111）（ 0000000） 由上述這些碼組可以看到，如果 是 C的碼組，則它的左右移位都是 C的碼組，具有這種特性的線性分組碼稱為 循環(huán)碼 。 循環(huán)碼具有以下一些性質(zhì)： 封閉性（線性性）。任何許用碼組的線性和還是許用碼組。由此性質(zhì)可以知：線性碼都包含全零碼。且最小碼重就是最小碼距。 循環(huán)性。任何許用的碼組循環(huán)移位后的碼組還是許用碼組。 循環(huán)碼可以用多項(xiàng)式來表示。為了用代數(shù)理論的方法研究循環(huán)碼的特性，我們經(jīng)常將循環(huán)碼表示成碼多項(xiàng)式的形 式：通常將碼 的碼多項(xiàng)式定義如下： 其中， D、 。 這里， GF（ 2）表示 2元域，在 GF（ 2）內(nèi)只有兩種元素 0， 1，且 0、 1 滿足如下的加法和乘法運(yùn)算規(guī)則： 1+1=0、 1+0= 0+1= 0+0=0； 1 1= 1 0=0、 00=0、 0 1=0。例如（ 1011000）碼的多項(xiàng)式表 示為 。 循環(huán)碼的生成多項(xiàng)式： 循環(huán)碼完全由其碼長 n 和生成多項(xiàng)式構(gòu)成。其中 g（ D）是一個(gè)能除盡 的nk 階多項(xiàng)式。階數(shù)低于 n 并能被 g（ D）除盡的一組多項(xiàng)式就構(gòu)成一個(gè)（ n， k）循環(huán)碼。也就是說，階數(shù)小于 n1且能被 g（ D）除盡的每個(gè)多項(xiàng)式都是循環(huán)碼的許用碼組。例如，（ 7， 4）循環(huán)碼的生成多項(xiàng)式 ，則階數(shù)低于 n1 能被 g（ D）除盡的多項(xiàng)式為 ，其中 。 假設(shè) ，則對(duì)應(yīng)的循環(huán)碼多項(xiàng)式為 則對(duì)應(yīng)的循環(huán)碼組為（ 1111111）。 我們知道，循環(huán)碼中任何碼組的循環(huán)移位還是許用碼組。用多項(xiàng)式的形式表示為： 碼組 ，經(jīng)過移位 位，可得到碼組 則可以證明得到（證明略）： ，即 例如，（ 7， 4）循環(huán)碼（ 1000101）的碼多項(xiàng)式為 ，移位 1位后變成 ，將它被 除，得到 因此，循環(huán)左移一位的余式為 ，其相對(duì)應(yīng)的碼組為（ 0001011），正好是（ 1000101）循環(huán)左移一位的結(jié)果。 另一個(gè)重要的結(jié)論是，（ n， k）循環(huán)碼的生成多項(xiàng)式 一定是的因式，即 。反之，如果 是一個(gè) nk次多項(xiàng)式，且能除盡 ，則此 一定生成一個(gè)（ n， k）循環(huán)碼。（證明略） 為尋找生成多項(xiàng)式，必須對(duì) 因式分解。因式分解可以通過計(jì)算機(jī)分解的方式分解，也可以通過查表（通常一些參考書已給出了這種因式分解的表格）。例如， 可分解為 ；（ 7， 4）循環(huán)碼的 生成多項(xiàng)式可以選擇 或 ；而（ 7， 3）循環(huán)碼的生成多項(xiàng)式可以選擇 或 ；（ 7， 6）循環(huán)碼的生成多項(xiàng)式為 D+1，實(shí)際上就是簡單的偶校驗(yàn)碼。 循環(huán)碼的生成矩陣與監(jiān)督矩陣： 循環(huán)碼的生成矩陣可以很容易地由生成多項(xiàng)式得到。我們知道，循環(huán)碼的碼組多項(xiàng)式是生成多項(xiàng)式 g（ D）的倍式，且根據(jù)線性碼的生成矩陣的特性，（ n， k）碼的生成矩陣實(shí)際上可以由（ n， k）碼中 k個(gè)不相關(guān)的碼組構(gòu)成。因此，根據(jù)以上兩 點(diǎn)，我們可以挑選出 k 個(gè)循環(huán)碼組的碼多項(xiàng)式如下： 非系統(tǒng)碼的生成矩陣 （非系統(tǒng)碼的生成矩陣） 輸入信息碼元為 時(shí)，相應(yīng)的循環(huán)碼組多項(xiàng)式為： 由上式得到的碼組不是系統(tǒng)碼。系統(tǒng)碼的生成矩陣必須為典型形式 [Ik,Q]。其中Ik為單位矩陣。例如，已知（ 7， 4）循環(huán)碼的生成多項(xiàng)式為 ，可按下面的推導(dǎo)過程求出非系統(tǒng)碼生成矩陣。 因?yàn)椋? 所以， 系統(tǒng)碼的生成矩陣 系統(tǒng)碼可 定義為，（ n， k）系統(tǒng)碼的碼組中前 k個(gè)比特是信息比特，后 nk 個(gè)比特是循環(huán)監(jiān)督位。那么在已知生成多項(xiàng)式 g（ D）時(shí)，如何構(gòu)造系統(tǒng)碼的生成矩陣呢？在系統(tǒng)碼中，碼組應(yīng)該具備如下的形式： 其中， 的次數(shù)小于等于 n－ k－ 1。 實(shí)際上，上式表示了如何生成系統(tǒng)碼，即將信息碼多項(xiàng)式升 nk次，然后以 g（ D）為模，求出余式 r（ D）。我們?nèi)匀灰裕?7， 4）碼為例，已知（ 7， 4）系統(tǒng)循環(huán)碼的生成多項(xiàng)式為 ，求其系統(tǒng)碼的生成矩陣。系統(tǒng)碼的生成矩陣形式肯定是典型形式 [Ik,Q]，因此我們選擇信息多項(xiàng)式為 、 1。將 提升 n－ k=3 次，得到 ，求 除以 g（ D）的余式得到 因此，系統(tǒng)生成矩陣為 表示成矩陣形式，得到 循環(huán)碼的監(jiān)督矩陣可以由下述方法得到。由于 g（ D）能除盡 ，即 （ *） 這里， 稱為生成多項(xiàng)式， 稱為監(jiān)督多項(xiàng)式。由（ *式）可知： 所以，如果生成矩陣是 則監(jiān)督矩陣為： 它完全由 的系數(shù)確定?？梢钥吹剑鲜鰞烧邼M足 。例如，已知（ 7， 3）碼的生成多項(xiàng)式為 ，求生成矩陣和監(jiān)督矩陣如下： 因?yàn)楸O(jiān)督多項(xiàng)式為 所以， 監(jiān)督矩陣為 ，可以驗(yàn)證 。 循環(huán)碼的譯碼： 糾錯(cuò)碼的譯碼是該編碼能否得到實(shí)際應(yīng)用的關(guān)鍵所在。譯碼器往往比編碼較難實(shí)現(xiàn)，對(duì)于糾錯(cuò)能力強(qiáng)的糾錯(cuò)碼更復(fù)雜。根據(jù)不同的糾錯(cuò)或檢錯(cuò)目的，循環(huán)碼譯碼器可分為用于糾錯(cuò)目的和用于檢錯(cuò)目的的循環(huán)碼譯碼器。 通常，將接收到的循環(huán)碼組進(jìn)行除法運(yùn)算，如果除盡，則說明正確傳輸；如果未除盡，則在寄存器中的內(nèi)容就是錯(cuò)誤圖樣，根據(jù)錯(cuò)誤圖樣可以確定一種邏輯，來確定差錯(cuò)的位置，從而達(dá)到糾錯(cuò)的目的。用于糾錯(cuò)目的的循環(huán)碼的譯碼算法比較 復(fù)雜，感興趣的話可以參考一些參考書。而用于檢錯(cuò)目的循環(huán)碼，一般使用 ARQ通信方式。檢測(cè)過程也 是將接受到的碼組進(jìn)行除法運(yùn)算，如果除盡，則說明傳輸無誤；如果未除盡，則表明傳輸出現(xiàn)差錯(cuò)，要求發(fā)送端重發(fā)。用于這種目的的循環(huán)碼經(jīng)常被成為循環(huán)冗余校驗(yàn)碼，即 CRC 校驗(yàn)碼。 CRC校驗(yàn)碼由于編碼電路、檢錯(cuò)電路簡單且易于實(shí)現(xiàn)，因此得到廣泛的應(yīng)用。在通過 MODEM 傳輸文件的協(xié)議如ZMODEM、 XMODEM 協(xié)議中均用到了 CRC 校驗(yàn)技術(shù)。在磁盤、光盤介質(zhì)存儲(chǔ)技術(shù)中也使用該方法。 在 SystemView 中沒有提供專用的 CRC 循環(huán)冗余校驗(yàn)碼編碼器，讀者可根據(jù)有關(guān)參考書設(shè)計(jì)一個(gè)相應(yīng)的仿真電路。如果不想親自動(dòng)手設(shè)計(jì)，