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

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

(5-43)該多項(xiàng)式的階可能會(huì)等于（當(dāng)時(shí)），所以不能代表一個(gè)碼長(zhǎng)為的碼字。不過(guò)，如果將除以，可得

(5-44)式中

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

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

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

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

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

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

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

(5-51)因?yàn)榭梢哉?，故也可以整除，從而可知也是一個(gè)碼字多項(xiàng)式。不同碼長(zhǎng)的循環(huán)碼存在性僅當(dāng)可以整除且階為的多項(xiàng)式存在時(shí)，循環(huán)碼才存在。因此設(shè)計(jì)一個(gè)循環(huán)碼的過(guò)程等效于對(duì)進(jìn)行因式分解的問(wèn)題。右表給出了常用的因式分解結(jié)果。注意：表中因式分解的結(jié)果是用八進(jìn)制數(shù)字來(lái)表示的。例如多項(xiàng)式對(duì)應(yīng)的向量為，與其對(duì)應(yīng)的八進(jìn)制表示為15?！纠?-12】利用表5-8設(shè)計(jì)一個(gè)循環(huán)碼。【解】查表可知的因式分解結(jié)果為3.15.13，表示的二進(jìn)制數(shù)字分別為011、001101、001011，對(duì)應(yīng)的多項(xiàng)式分別為即

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

(5-52)式中是一個(gè)階為的多項(xiàng)式，稱(chēng)為該碼的監(jiān)督多項(xiàng)式。對(duì)偶碼定義的互反多項(xiàng)式（ReciprocalPolynomial）為

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

上式的互反多項(xiàng)式為

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

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

(5-55)將上式等號(hào)兩端同時(shí)除以生成多項(xiàng)式，可得

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

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

(5-59)顯然，上式的等號(hào)左端表示一個(gè)合法碼字，因?yàn)樵摱囗?xiàng)式的階不大于，且能被生成多項(xiàng)式整除。將式(5-55)和式(5-57)代入上式，可得碼字多項(xiàng)式對(duì)應(yīng)的碼字向量為

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

于是有

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

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

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

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

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

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

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

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

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

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

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

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

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

(5-73)及其伴隨式為

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