信息與編碼理論 第2版 課件 5.5 循環(huán)碼

§5.5循環(huán)碼5.5.1循環(huán)碼的定義與基本性質(zhì)循環(huán)碼定義具有循環(huán)移位性質(zhì)的線性分組碼：如果碼字中元素在經(jīng)過一次循環(huán)移位后得到的向量仍是該碼的一個碼字。碼字多項式研究循環(huán)碼的結(jié)構(gòu)時，方便的方法是將碼字向量表示成如下的碼字多項式：(5-42)顯然，碼字多項式的階不可能超過，并且只有當(dāng)時碼字多項式的階才為。對于二進(jìn)制編碼，碼字多項式中系數(shù)的取值為0或1。將碼字多項式定義式的等號兩邊同時乘上，可得

(5-43)該多項式的階可能會等于（當(dāng)時），所以不能代表一個碼長為的碼字。不過，如果將除以，可得

(5-44)式中

(5-45)注意：是碼字向量對應(yīng)的碼字多項式，而是碼字向量循環(huán)移位1次后得到的碼字向量。由式(5-44)可知，是除以之后得到的余式，故該關(guān)系也可以記作

(5-46)推廣可知，對于某循環(huán)碼的一個碼字向量，若其碼字多項式為，則也表示該循環(huán)碼的一個碼字多項式，該關(guān)系可以表示為

(5-47)式中是商式，而余式表示了該循環(huán)碼的一個碼字多項式，它對應(yīng)于碼字向量循環(huán)移位次后得到的碼字向量?！纠?-11】對于長度為的碼字向量，驗證循環(huán)碼的循環(huán)特性?！窘狻繉?yīng)于碼字向量的碼字多項式為

利用多項式的長除法，容易求得于是、、、除以之后所得余式對應(yīng)的向量分別為顯然上面四個向量是碼字向量分別循環(huán)1次、2次、3次和4次之后的結(jié)果。5.5.2循環(huán)碼的生成多項式生成多項式（GeneratorPolynomial）循環(huán)碼可以利用生成多項式來生成?？梢宰C明：循環(huán)碼的生成多項式是的一個因式，且階為，故可以表示為

(5-48)對應(yīng)于消息向量的消息多項式可以定義為

(5-49)于是，是一個不大于階的多項式，可以表示一個碼字多項式。循環(huán)碼碼字的生成循環(huán)碼共有個消息多項式，，因此通過一個給定的可以生成對應(yīng)的全部個碼字多項式，即

(5-50)循環(huán)性質(zhì)的證明：假設(shè)表示由上式得到的任意一個碼字多項式，則由式(5-44)可知其循環(huán)移位1次后可得

(5-51)因為可以整除和，故也可以整除，從而可知也是一個碼字多項式。不同碼長的循環(huán)碼存在性僅當(dāng)可以整除且階為的多項式存在時，循環(huán)碼才存在。因此設(shè)計一個循環(huán)碼的過程等效于對進(jìn)行因式分解的問題。右表給出了常用的因式分解結(jié)果。注意：表中因式分解的結(jié)果是用八進(jìn)制數(shù)字來表示的。例如多項式對應(yīng)的向量為，與其對應(yīng)的八進(jìn)制表示為15?！纠?-12】利用表5-8設(shè)計一個循環(huán)碼?！窘狻坎楸砜芍囊蚴椒纸饨Y(jié)果為3.15.13，表示的二進(jìn)制數(shù)字分別為011、001101、001011，對應(yīng)的多項式分別為即

所以，為了生成循環(huán)碼，可以選用或作為生成多項式，它們生成的循環(huán)碼是相互等效的。其中，由生成的循環(huán)碼的所有碼字向量如下頁表中所示。生成多項式為下式的循環(huán)碼：【例5-13】對于碼長為的循環(huán)碼，確定的可能取值?！窘狻坎楸?-8可知的因式分解結(jié)果為3.37.4102041，表示的二進(jìn)制數(shù)字分別為011、011111、100001000010000100001，對應(yīng)的多項式分別為所以，的可能取值為1、4、20或5、21、24，其中后三個數(shù)值來自于兩個多項式乘積的階，于是的可能取值分別為24、21、5、20、4、1。5.5.3循環(huán)碼的監(jiān)督多項式監(jiān)督多項式（ParityCheckPolynomial）假設(shè)是循環(huán)碼的生成多項式，這樣是的一個因式，所以

(5-52)式中是一個階為的多項式，稱為該碼的監(jiān)督多項式。對偶碼定義的互反多項式（ReciprocalPolynomial）為

(5-53)顯然互反多項式也是的一個因式，所以是循環(huán)碼的生成多項式，該碼是由生成的循環(huán)碼的對偶碼?！纠?-14】求生成的循環(huán)碼的對偶碼?！窘狻坑衫?-12可知于是該循環(huán)碼的監(jiān)督多項式為

上式的互反多項式為

由可以生成循環(huán)碼的對偶碼，即循環(huán)碼，該對偶碼的所有碼字向量如下頁表中所示。循環(huán)碼：生成多項式為5.5.4循環(huán)碼的生成矩陣對于線性分組碼，其生成矩陣可以用任意個線性獨立的碼字向量來構(gòu)造。如果已知某循環(huán)碼的生成多項式為，那么最容易找到的個線性獨立的碼字向量分別是對應(yīng)于、……、、、等多項式的碼字向量，所以可以定義

(5-54)用中各個行多項式的系數(shù)來充當(dāng)行向量便可以最后得到該碼的生成矩陣。【例5-15】給出循環(huán)碼的生成矩陣?！窘狻恐灰_定循環(huán)碼的生成多項式，那么生成矩陣的4個行向量可以通過計算來獲得，其中。由例5-12可知，和兩個生成多項式均可生成循環(huán)碼，所以它們各自對應(yīng)的生成矩陣和分別為5.5.5截短循環(huán)碼截短碼（ShortenedCode）若表示一個最小距離為的線性分組碼，則為了生成的截短碼，應(yīng)僅考慮開頭為個零的個信息向量（），因為這個零不攜帶任何信息因此可以刪除不要，這樣留下的個碼字就構(gòu)成了的截短碼。截短碼是碼率為的線性分組碼，其中小于原碼的碼率。由于截短碼的碼字是將原碼中的碼字去掉個零之后的結(jié)果，所以截短碼的最小重量不會小于原碼的最小重量，如果的取值較大，則截短碼通常會比原碼的最小重量大一些。截短循環(huán)碼的用途由例5-13和表5-8可知，對于任意給定的和的值，并不一定恰好有循環(huán)碼存在，此時可以使用截短碼的方法來構(gòu)造滿足參數(shù)要求的新碼。在進(jìn)行碼設(shè)計的時候，為了滿足預(yù)先給定的參數(shù)要求，可以將循環(huán)碼截短位從而得到碼。為了生成截短循環(huán)碼，需要將消息向量中前位直接取0值從而不再傳輸這些位的信息，這樣得到的碼一般不再是循環(huán)碼；在接收機(jī)處重新加上刪掉的個0值之后，便可以使用原循環(huán)碼的任意譯碼器來進(jìn)行譯碼。截短循環(huán)碼的方法普遍用于RS碼的截短和循環(huán)冗余校驗（CRC）碼的構(gòu)造中，其中CRC碼是計算機(jī)通信網(wǎng)中錯誤檢測的主要方法。5.5.6系統(tǒng)循環(huán)碼對于系統(tǒng)形式的循環(huán)碼，消息向量應(yīng)整體出現(xiàn)在對應(yīng)的碼字向量中?？梢詫⒄w左移位來充當(dāng)碼字向量的左側(cè)位，然后將對應(yīng)的校驗比特放在碼字向量的右側(cè)位。為了將左移位，可以通過其消息多項式來實現(xiàn)，即

(5-55)將上式等號兩端同時除以生成多項式，可得

(5-56)式中是商式，是余式，故其階不會超過，于是(5-57)式(5-56)的關(guān)系也可以表示成

(5-58)將加至式(5-56)的等號兩端，可得

(5-59)顯然，上式的等號左端表示一個合法碼字，因為該多項式的階不大于，且能被生成多項式整除。將式(5-55)和式(5-57)代入上式，可得碼字多項式對應(yīng)的碼字向量為

(5-60)式中表示消息比特，表示校驗比特。歸納起來，生成系統(tǒng)循環(huán)碼的步驟如下：將消息多項式乘上；將除以生成多項式，求得余式；將余式加至，即得碼字多項式。生成循環(huán)碼的系統(tǒng)形式生成矩陣的方法如下：對于，將除以生成多項式，求得余式則是一個碼字多項式，對應(yīng)的碼字向量可以充當(dāng)生成矩陣的第行，即最后將每行的多項式系數(shù)作為行向量便能得到系統(tǒng)形式的生成矩陣。【例5-16】對于生成多項式為的循環(huán)碼，求消息向量生成的系統(tǒng)形式碼字向量?！窘狻肯蛄繉?yīng)的多項式為

于是有

將上式除以，可得于是所以碼字多項式為對應(yīng)的碼字向量為。【例5-17】求上例中循環(huán)碼的系統(tǒng)形式生成矩陣和監(jiān)督矩陣?！窘狻恳阎摯a的生成多項式為，易得于是所以，系統(tǒng)形式的生成矩陣為

容易驗證，由該系統(tǒng)生成矩陣和例5-15中的生成的碼字完全一樣。此外，與對應(yīng)的系統(tǒng)形式的監(jiān)督矩陣為5.5.7循環(huán)碼的編碼器多項式除法電路給定兩個多項式

(5-62)(5-63)其中，那么除以的結(jié)果為

(5-64)式中是商式，是余式。完成上式運(yùn)算的多項式除法電路如下圖所示，該電路由級反饋移位寄存器來組成。首先，圖中所有的寄存器都初始化為0；然后，的系數(shù)按照從高階到低階的順序，在每個時鐘內(nèi)依次輸入該電路一位；在第次移位之后，輸出端開始輸出商多項式的系數(shù)，按照從高階至低階的順序依次輸出；在次移位之后，寄存器中的最終內(nèi)容便為余式多項式的系數(shù)，右側(cè)為高階系數(shù)，左側(cè)為低階系數(shù)?！纠?-18】對于多項式和，給出完成除以運(yùn)算的除法電路。【解】利用長除法容易求得這兩個多項式的相除結(jié)果為

顯然這里，，故完成上述除法運(yùn)算的電路如下圖所示：圖中所有寄存器的初始狀態(tài)為0，之后該電路的狀態(tài)變化如下表所示：在次移位時鐘后，商式系數(shù)開始依次輸出，為1110，因此商多項式為。在次移位時鐘之后，寄存器的最終內(nèi)容是余式系數(shù)，為110，于是余式多項式為。循環(huán)碼編碼電路生成系統(tǒng)形式循環(huán)碼的步驟中最為重要的一步是計算除以之后得到的余式，該操作可以使用前述的多項式除法電路來實現(xiàn)。如果某循環(huán)碼的生成多項式為，則該循環(huán)碼的系統(tǒng)形式編碼電路如下圖所示：在前個移位時鐘內(nèi)，開關(guān)1閉合，而開關(guān)2接通下方的端口，于是編碼器的輸出為位消息比特，同時這比特也依次送入了移位寄存器；當(dāng)位消息比特全送入編碼器后，寄存器中的內(nèi)容便是與余式多項式系數(shù)分別對應(yīng)的位校驗比特，此時開關(guān)1斷開，開關(guān)2接通上方的端口，然后在接下來的個移位時鐘內(nèi)，寄存器中的校驗比特依次輸出?？傊诿總€移位循環(huán)的周期內(nèi)，移位的次數(shù)共為。【例5-19】對于生成矩陣為的循環(huán)碼，請給出該碼的編碼電路，并對消息向量進(jìn)行系統(tǒng)編碼。【解】由例5-16結(jié)果可知，消息向量對應(yīng)的碼字向量為。生成多項式為的循環(huán)碼的編碼電路如下圖所示：該編碼電路在輸入下的狀態(tài)變化如下表所示：當(dāng)4位消息比特都送入編碼電路之后，寄存器中的內(nèi)容就是校驗比特，注意左側(cè)寄存器的內(nèi)容表示低位，右側(cè)寄存器的內(nèi)容表示高位，所以最后可得碼字向量為

顯然得到的碼字向量與之前計算的結(jié)果一致。5.5.8循環(huán)碼的譯碼器譯碼原理編碼器輸出的碼字向量在傳輸過程中會受到噪聲的干擾，因此接收向量可能會和發(fā)送的碼字向量不同，即可以表示為，其中是錯誤圖樣。與碼字對應(yīng)的碼字多項式為，與錯誤圖樣對應(yīng)的錯誤多項式為，那么與接收向量對應(yīng)的接收多項式可以表示為

(5-66)通過計算是否能夠被生成多項式整除，可以判斷是否為一個有效的碼字多項式。伴隨多項式（SyndromePolynomial）可以將除以之后得到的余式定義為伴隨多項式，即

(5-67)在上式的計算過程利用了可以整除的事實。顯然，伴隨多項式的階不可能大于，因此其對應(yīng)的伴隨式可以用個元素組成的向量來表示。此外，由上式可以發(fā)現(xiàn)，模得到的余式與模得到的余式完全一樣，所以通過接收多項式計算得到的包含了糾正錯誤圖樣所需要的信息。根據(jù)上面的討論可知，取決于錯誤圖樣而不是碼字。由于所有可能的伴隨多項式有個，而所有可能的錯誤圖樣有個，所以不同的錯誤圖樣可能會導(dǎo)致相同的伴隨多項式。最大似然譯碼（Maximum-LikelihoodDecoding）準(zhǔn)則要求找到對應(yīng)于所得的所有錯誤圖樣中重量最小的那個，然后將其加至從而獲得最為可能的發(fā)送碼字多項式。伴隨多項式的計算仍然可以利用前述的多項式除法電路來完成，其工作原理與編碼器基本相同，如下頁圖中所示。伴隨式計算電路起初圖中各個寄存器的初始值均為0，開關(guān)位于位置1；當(dāng)比特的接收向量都移入寄存器后，個寄存器中的內(nèi)容便組成了伴隨式，左側(cè)低位右側(cè)高位；接下來，開關(guān)打到位置2，寄存器中的伴隨式會依次輸出。得到伴隨式之后，便可按照5.3.7小節(jié)介紹的查表法來找到最為可能的錯誤圖樣。【例5-20】對于生成多項式為的循環(huán)碼，請給出該碼的伴隨式計算電路，并對接收向量進(jìn)行譯碼?！窘狻吭摯a的伴隨式計算電路如下圖，該電路的狀態(tài)變化如下表所示：伴隨式為。因為該碼的最小碼距為，所以可以確保糾正1位錯誤，并且容易求得該碼的伴隨式查詢表如下所示：現(xiàn)在已得伴隨式為，通過查詢左表可知對應(yīng)于該伴隨式最為可能的錯誤圖樣為，因此譯碼結(jié)果為于是信息比特為討論利用計算伴隨式然后查詢標(biāo)準(zhǔn)陣列的譯碼方法當(dāng)值不大的時候容易實現(xiàn)，但是當(dāng)值較大的情況下會對存儲和計算設(shè)備要求很高。例如時標(biāo)準(zhǔn)陣列中共有（約1百萬）個陪集首，此時要從如此多的元素中篩選匹配出一個錯誤圖樣來是非常耗費(fèi)存儲空間和時間的。在確定錯誤圖樣之后，可以用模2加的方法將其加至接收向量來完成譯碼，此時若采用5.3.8小節(jié)介紹的并行方式（1次位）來實現(xiàn)的話需要個異或門，但此時也可以只用1個異或門從而以串行方式（1次1位）來完成譯碼。實際上，利用循環(huán)碼良好的代數(shù)特性可以簡化尋找錯誤圖樣的過程，從而簡化譯碼電路。如果對應(yīng)于錯誤多項式，表示循環(huán)移位一次得到多項式，則對應(yīng)于的伴隨多項式將是，即

(5-68)證明：如果對應(yīng)于錯誤多項式的伴隨式多項式為，那么顯然有

(5-69)式中是除以之后得到的商式，是余式。而由式(5-51)得

(5-70)式中是錯誤多項式中最高階那項的系數(shù)。將式(5-69)代入式(5-70)，可得

(5-71)由上式可知，除以之后得到的余式，也就是對應(yīng)于的伴隨多項式將是由式(5-68)給出的。于是，為了獲得對應(yīng)于的伴隨式，需要將乘以之后再除以來求得余式，這等效于圖5-14中的移位寄存器內(nèi)容在沒有輸入之后繼續(xù)移位。這意味著，從計算的組合邏輯電路也可以用于由計算。這種譯碼器叫做梅吉特譯碼器（MeggitDecoder）。梅吉特譯碼器基本思路首先，將接收向量輸入伴隨式計算電路來求出，然后將伴隨式送往組合電路來計算，接著將該電路的輸出與模2相加來進(jìn)行糾正；之后，將伴隨式循環(huán)移位一次，再使用相同的組合邏輯電路來計算；該過程重復(fù)次。假如錯誤圖樣是可糾正的（陪集首之一），則譯碼器可以糾正該錯誤。梅吉特譯碼原理首先，由確定出伴隨多項式；接著，譯碼電路檢查是否對應(yīng)于一個在最高位存在差錯（即）的可糾正錯誤圖樣，然后根據(jù)情況選擇如下兩種處理方法：(1)如果由得到的錯誤圖樣中，則將接收多項式和伴隨式多項式同時循環(huán)移位一次，這樣便得到了以及與其對應(yīng)的伴隨式。此時的次高位變成了的最高位，同一譯碼電路將會檢查是否與在位置存在差錯的錯誤模式相對應(yīng)。(2)如果與位有錯的錯誤圖樣相對應(yīng)（即），則接收向量中的最高位必定為差錯位，可以通過來實現(xiàn)糾錯，于是得到的修正后接收多項式為

(5-72)為了得到與修正接收多項式對應(yīng)的伴隨式，可以通過將與模2相加從中消除差錯位對伴隨式的影響，于是的伴隨多項式為然后，將及其伴隨多項式同時循環(huán)移位一次，可得

(5-73)及其伴隨式為

(5-74)所以，若在對伴隨式進(jìn)行移位時將1加上便可得到。注意在上式的推導(dǎo)中用到了式(5-68)和關(guān)系式?？傊诘玫胶停ɑ蚴呛停┲?，譯碼電路接著對此時的最高位接收元素進(jìn)行譯碼，具體的譯碼方法和對的處理一樣。將上述過程重復(fù)次后，譯碼過程結(jié)束。梅吉特譯碼器的結(jié)構(gòu)(1)接收向量全部移入伴隨式寄存器并計算得到伴隨式，同時也存入到接收向量寄存器；(2)將伴隨式讀入錯誤圖樣檢測電路，當(dāng)且僅當(dāng)伴隨式寄存器中的內(nèi)容對應(yīng)于最高位存在可糾正錯誤時，該檢測電路的輸出才為1，其它情況下的輸出均為0；(3)從接收向量寄存器中讀出一個接收符號，并將上步得到的檢測電路輸出加至該符號進(jìn)行譯碼，同時檢測電路的輸出值也被反饋回伴隨式寄存器參與移位操作，用于修正伴隨式；(4)用上步得到的新伴隨式來檢測第二個接收符號（此時其位于接收向量寄存器的最右端）是否有錯，具體操作與步驟(2)和(3)相同；(5)譯碼器按照以