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

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

(5-44)式中

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

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

(5-47)式中是商式，而余式表示了該循環碼的一個碼字多項式，它對應于碼字向量循環移位次后得到的碼字向量。【例5-11】對于長度為的碼字向量，驗證循環碼的循環特性。【解】對應于碼字向量的碼字多項式為

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

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

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

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

(5-51)因為可以整除和，故也可以整除，從而可知也是一個碼字多項式。不同碼長的循環碼存在性僅當可以整除且階為的多項式存在時，循環碼才存在。因此設計一個循環碼的過程等效于對進行因式分解的問題。右表給出了常用的因式分解結果。注意：表中因式分解的結果是用八進制數字來表示的。例如多項式對應的向量為，與其對應的八進制表示為15。【例5-12】利用表5-8設計一個循環碼。【解】查表可知的因式分解結果為3.15.13，表示的二進制數字分別為011、001101、001011，對應的多項式分別為即

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

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

(5-53)顯然互反多項式也是的一個因式，所以是循環碼的生成多項式，該碼是由生成的循環碼的對偶碼。【例5-14】求生成的循環碼的對偶碼。【解】由例5-12可知于是該循環碼的監督多項式為

上式的互反多項式為

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

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

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

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

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

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

(5-60)式中表示消息比特，表示校驗比特。歸納起來，生成系統循環碼的步驟如下：將消息多項式乘上；將除以生成多項式，求得余式；將余式加至，即得碼字多項式。生成循環碼的系統形式生成矩陣的方法如下：對于，將除以生成多項式，求得余式則是一個碼字多項式，對應的碼字向量可以充當生成矩陣的第行，即最后將每行的多項式系數作為行向量便能得到系統形式的生成矩陣。【例5-16】對于生成多項式為的循環碼，求消息向量生成的系統形式碼字向量。【解】向量對應的多項式為

于是有

將上式除以，可得于是所以碼字多項式為對應的碼字向量為。【例5-17】求上例中循環碼的系統形式生成矩陣和監督矩陣。【解】已知該碼的生成多項式為，易得于是所以，系統形式的生成矩陣為

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

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

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

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

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

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

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

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

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

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

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

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

(5-73)及其伴隨式為

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