線性分組碼本章內(nèi)容：5.1數(shù)字通信中的編碼信道5.2差錯(cuò)控制系統(tǒng)的基本概念5.3線性分組碼5.4線性分組碼的檢錯(cuò)和糾錯(cuò)能力5.5循環(huán)碼5.6循環(huán)碼的仿真實(shí)例緒論數(shù)字信號(hào)在傳輸過(guò)程中會(huì)受到各種影響，導(dǎo)致系統(tǒng)誤碼率增大加性高斯白噪聲（AWGN，AdditiveWhiteGaussianNoise）干擾和衰落等不利因素信道編碼（ChannelCoding）也叫做差錯(cuò)控制編碼（ErrorControlCoding）為了降低系統(tǒng)誤碼率而進(jìn)行的一種特殊信號(hào)變換目的：使得發(fā)射信號(hào)能夠更好的抵抗各種信道損傷，改善通信系統(tǒng)的誤碼率性能§5.1數(shù)字通信中的編碼信道一個(gè)完整的點(diǎn)到點(diǎn)數(shù)字通信系統(tǒng)的基本結(jié)構(gòu)下圖：在研究不同差錯(cuò)控制編碼性能時(shí)采用編碼信道模型比較合適！5.1.1編碼信道的概念按照錯(cuò)碼分布規(guī)律的不同，編碼信道可以分為三類(lèi)：隨機(jī)信道（RandomChannel）：接收到的碼元序列中的錯(cuò)誤是獨(dú)立隨機(jī)出現(xiàn)的。突發(fā)信道（BurstChannel）：錯(cuò)碼成串集中出現(xiàn)，在一些短促的時(shí)間段內(nèi)會(huì)出現(xiàn)大量錯(cuò)碼。混合信道（MixedChannel）：既存在隨機(jī)錯(cuò)誤又存在突發(fā)錯(cuò)誤，且兩種錯(cuò)誤都不能忽略不計(jì)的信道。5.1.2有噪信道編碼定理1.錯(cuò)誤概率與譯碼規(guī)則以二元對(duì)稱(chēng)信道為例平均錯(cuò)誤概率為如果更改譯碼規(guī)則，將輸出端接收到的“1”譯為“0”，接收到的“0”譯為“1”，則平均錯(cuò)誤概率變?yōu)榭芍e(cuò)誤概率確實(shí)與譯碼規(guī)則有關(guān)！假定收到后的譯碼規(guī)則為如果發(fā)送端發(fā)送的就是，則譯碼正確；如果發(fā)送的不是，則譯碼錯(cuò)誤。正確譯碼的概率為錯(cuò)誤譯碼的概率為平均錯(cuò)誤概率為最大后驗(yàn)概率準(zhǔn)則（最小錯(cuò)誤概率準(zhǔn)則）譯碼函數(shù)應(yīng)為使其滿(mǎn)足其中，。2.有噪信道編碼定理（香農(nóng)第二定理）設(shè)離散無(wú)記憶信道，是信道傳遞概率，信道容量為。當(dāng)信息傳輸率時(shí)，總可以找到一種編碼，當(dāng)碼長(zhǎng)足夠長(zhǎng)時(shí)，譯碼平均錯(cuò)誤概率任意小，即，為任意大于零的正數(shù)。反之，當(dāng)時(shí)，任何編碼的必大于零。§5.2差錯(cuò)控制系統(tǒng)的基本概念5.2.1差錯(cuò)控制的方式重傳反饋方式（ARQ,AutomaticRepeatQuery）優(yōu)點(diǎn)：編譯碼設(shè)備比較簡(jiǎn)單糾錯(cuò)能力極強(qiáng)適應(yīng)性很強(qiáng)需要有反饋信道，且要求收發(fā)兩端的配合與協(xié)作。前向糾錯(cuò)方式（FEC,ForwardErrorCorrection）優(yōu)點(diǎn)：支持一個(gè)用戶(hù)對(duì)多個(gè)用戶(hù)的同播通信譯碼實(shí)時(shí)性較好控制電路比ARQ簡(jiǎn)單不僅能自動(dòng)發(fā)現(xiàn)錯(cuò)誤，且在一定糾錯(cuò)能力之內(nèi)可以自動(dòng)糾正碼字中的錯(cuò)誤。混合方式（HEC,HybridErrorCorrection）接收端收到碼序列以后，首先檢驗(yàn)錯(cuò)誤情況，如果在糾錯(cuò)碼的糾錯(cuò)能力之內(nèi)，則自動(dòng)進(jìn)行糾錯(cuò)；如果錯(cuò)誤很多，超過(guò)了碼的糾錯(cuò)能力，但能檢測(cè)出來(lái)，則接收端通過(guò)反饋信道要求發(fā)送端重新傳送有錯(cuò)的消息。5.2.2信道編碼的分類(lèi)

按照校驗(yàn)碼元與消息碼元之間的關(guān)系，可以分為：線性碼（LinearCode）校驗(yàn)符號(hào)與消息符號(hào)之間的關(guān)系是線性關(guān)系（滿(mǎn)足線性疊加原理）。非線性碼（Non-linearCode）分析非常困難，實(shí)現(xiàn)較為復(fù)雜，且沒(méi)有形成嚴(yán)密完整的理論體系。下文中主要討論線性碼。

5.2.3分組碼的基本概念

對(duì)于二進(jìn)制分組碼而言，兩個(gè)碼字之間的漢明距離實(shí)際上就是兩個(gè)碼字模2加（異或）結(jié)果的漢明重量！【例5-1】設(shè)某分組碼的兩個(gè)碼字分別為和，求兩個(gè)碼字各自的漢明重量以及它們之間的漢明距離?！窘狻扛鶕?jù)定義，易知碼字和的漢明重量分別為和，而二者之間對(duì)應(yīng)位置取值不同的個(gè)數(shù)為3，所以?xún)蓚€(gè)碼字之間的漢明距離為容易驗(yàn)證：，于是可得

如果將某分組碼中所有許用碼字構(gòu)成的集合記做，則稱(chēng)任意兩個(gè)碼字之間距離的最小值為該分組碼的最小漢明距離，簡(jiǎn)稱(chēng)最小碼距（MinimumDistance），即5.2.4分組碼的譯碼準(zhǔn)則譯碼利用收到的接收向量得到發(fā)送碼字向量的估計(jì)結(jié)果。最大后驗(yàn)概率譯碼信道譯碼器的最優(yōu)譯碼準(zhǔn)則在發(fā)送碼字先驗(yàn)等概的前提下，該準(zhǔn)則等效于最大似然譯碼（MLD，MaximumLikelihoodDecoding）準(zhǔn)則，即將譯碼為指由所有許用碼字構(gòu)成的集合最小距離譯碼對(duì)于離散無(wú)記憶信道（DiscreteMemorylessChannel），只要錯(cuò)誤轉(zhuǎn)移概率，則最大似然譯碼準(zhǔn)則會(huì)等效于最小距離譯碼（MDD，MinimumDistanceDecoding）準(zhǔn)則，即將譯碼為證明：因?yàn)閷?duì)于接收向量，如果其與中某一碼字向量之間的漢明距離記為，即

則

由上式顯然可知：只要，則是的單調(diào)遞減函數(shù)，因此只要找到的那個(gè)碼字向量，便是能使最大的譯碼結(jié)果。5.2.5簡(jiǎn)單的分組碼重復(fù)碼（RepetitionCode）具有參數(shù)的分組碼，即長(zhǎng)的碼字中只有一個(gè)消息符號(hào)，而其它個(gè)都是校驗(yàn)符號(hào)，且均是消息符號(hào)取值的重復(fù)。故碼率為該碼只有兩個(gè)許用碼字，其中一個(gè)為全0碼字，另一個(gè)為全1碼字。顯然，該碼的最小碼距為奇偶檢驗(yàn)碼（Parity-CheckCode）具有參數(shù)的分組碼，該碼的碼字可以表示為其中為校驗(yàn)符號(hào)，為個(gè)消息符號(hào)，它們之間的關(guān)系可以表示為或偶校驗(yàn)碼（Even-ParityCode）奇校驗(yàn)碼（Odd-ParityCode）碼率為譯碼：在接收端通過(guò)檢測(cè)每個(gè)碼字中所有符號(hào)的和是不是0（或1）來(lái)判斷傳輸過(guò)程中是否發(fā)生了錯(cuò)誤。檢錯(cuò)能力：奇偶檢驗(yàn)碼只能用于檢錯(cuò)，且只能檢測(cè)出所有奇數(shù)個(gè)錯(cuò)誤?！纠?-2】給出偶檢驗(yàn)碼的所有碼字。如果該碼通過(guò)錯(cuò)誤轉(zhuǎn)移概率為

的二進(jìn)制對(duì)稱(chēng)信道傳輸，求該碼不能檢測(cè)出錯(cuò)誤的概率?！窘狻匡@然，該碼的共有個(gè)碼字，消息向量與碼字向量之間的對(duì)應(yīng)關(guān)系可以用下表來(lái)表示：該碼可以檢測(cè)出所有1個(gè)和3個(gè)錯(cuò)誤，因此該碼不能檢測(cè)出錯(cuò)誤的概率為二維奇偶檢驗(yàn)碼（Two-DimensionalParity-CheckCode）也稱(chēng)作方陣碼（RectangleCode）或乘積碼（ProductCode）。該碼首先將消息符號(hào)序列排列成一個(gè)行列的方陣，然后在每一行后面加上1位水平校驗(yàn)符號(hào)，在每一列的下面加上1位垂直校驗(yàn)符號(hào)，這樣得到的行列方陣便構(gòu)成了一個(gè)碼字。該碼的碼率為顯然，碼字方陣中發(fā)生1個(gè)符號(hào)錯(cuò)誤的時(shí)候會(huì)導(dǎo)致該符號(hào)所在的行和列均校驗(yàn)失敗，而該行和該列的交叉點(diǎn)便是發(fā)生錯(cuò)誤的位置，因此該碼可以糾正1位錯(cuò)誤。例如，一個(gè)二維奇偶校驗(yàn)碼的三個(gè)碼字實(shí)例如下圖所示：恒比碼（ConstantRatioCode）所有碼字中均含有相同數(shù)目的1和0。在接收端只要檢測(cè)每個(gè)碼字中1的個(gè)數(shù)，便可以判斷是否發(fā)生了錯(cuò)誤。因?yàn)榇a字中1的個(gè)數(shù)稱(chēng)為該碼字的重量，因此該碼也稱(chēng)作等重碼。恒比碼不是線性碼，其最大的優(yōu)點(diǎn)是簡(jiǎn)單，主要用于傳輸電傳機(jī)或其它鍵盤(pán)設(shè)備產(chǎn)生的字母和符號(hào)。群計(jì)數(shù)碼該碼在編碼時(shí)首先計(jì)算消息向量中1的個(gè)數(shù)，然后用二進(jìn)制數(shù)表示這個(gè)數(shù)目并作為監(jiān)督位附在消息符號(hào)后面。例如要傳輸?shù)南⑾蛄繛?1101，那么監(jiān)督位應(yīng)該是100（十進(jìn)制的4），編出的群計(jì)數(shù)碼為11101100。顯然，該碼除了能發(fā)現(xiàn)所有奇數(shù)個(gè)錯(cuò)誤之外，還可以發(fā)現(xiàn)一些偶數(shù)個(gè)錯(cuò)誤。在消息符號(hào)中，除了0變?yōu)?和1變?yōu)?成對(duì)出現(xiàn)外，所有其它形式的錯(cuò)碼都會(huì)使得消息符號(hào)中1的數(shù)目與監(jiān)督位指示的數(shù)字不符，所以該碼的檢錯(cuò)能力較強(qiáng)。5.2.6編碼增益的概念采用信道編碼之后，通信系統(tǒng)在正常信噪比范圍內(nèi)的誤碼率總是能夠得到較大的改善，改善的程度和所用的具體編碼方式有關(guān)。編碼增益（CodingGain）：在誤碼率一定的條件下，非編碼系統(tǒng)需要的輸入信噪比與采用了糾錯(cuò)編碼的系統(tǒng)所需的輸入信噪比之間的差值（用dB表示）。如果某數(shù)字通信系統(tǒng)的誤碼率如左圖所示，則當(dāng)誤碼率為時(shí)的編碼增益為3dB。§5.3線性分組碼概述線性分組碼：具有線性性質(zhì)的分組碼。最為重要的一類(lèi)信道編碼技術(shù)，它是討論其它各類(lèi)碼的基礎(chǔ)。線性分組碼可以用的形式來(lái)描述。如果符號(hào)只取自于由兩個(gè)元素（0和1）構(gòu)成集合，則稱(chēng)為二進(jìn)制碼。

k元組（k-tuples）

n元組（n-tuples）線性映射5.3.1向量空間定義所有二進(jìn)制元組構(gòu)成的集合稱(chēng)為二進(jìn)制域（包括0和1兩個(gè)元素）上的一個(gè)向量空間，記作。二進(jìn)制域中的運(yùn)算在不混淆的情況下也常常用“+”來(lái)表示模2加法。5.3.2線性分組碼的結(jié)構(gòu)子空間向量空間的一個(gè)子集如果滿(mǎn)足下列兩個(gè)條件，則稱(chēng)為的一個(gè)子空間：1)中包含全零向量；2)中任意兩個(gè)向量的和仍然在內(nèi)（封閉性質(zhì)）。線性分組碼構(gòu)成一個(gè)子空間假設(shè)和是某二進(jìn)制分組碼中的兩個(gè)碼字向量，則該碼是線性碼的充要條件是也為該碼的許用碼字向量。例如，向量空間中共包括下列個(gè)4元組：顯然，下列元素構(gòu)成的子集是的一個(gè)子空間：容易驗(yàn)證子集中任意兩個(gè)向量的和任然是中的一個(gè)向量。00000001001000100100100010011010110001010110001111011110011111110000010110101111總結(jié)：對(duì)于二進(jìn)制編碼，個(gè)元組構(gòu)成的集合是一個(gè)線性分組碼的充要條件是該集合為向量空間（包括所有的元組）的一個(gè)子空間。線性分組碼是由個(gè)長(zhǎng)度為的二進(jìn)制向量組成的碼字集合；對(duì)于任意兩個(gè)碼字向量均有；零向量將會(huì)是任意線性分組碼中的一個(gè)合法碼字向量。對(duì)于線性分組碼，碼字重量和碼字之間的距離存在一一對(duì)應(yīng)的關(guān)系：由式(5-6)可知，而也是一個(gè)合法碼字。最小重量某線性分組碼中所有非零碼字重量的最小值，即線性分組碼的最小重量與最小碼距相等，即線性分組碼的幾何解釋?zhuān)簜€(gè)元組（圖中所有圓點(diǎn)與方點(diǎn)）構(gòu)成了向量空間，而該向量空間內(nèi)的個(gè)元組（圖中所有方點(diǎn)）構(gòu)成了一個(gè)碼字向量子空間，這些方點(diǎn)代表了合法碼字（或稱(chēng)許用碼字）。由圖可知選擇編碼方案的基本目標(biāo)：1）為了提高編碼效率，應(yīng)該在向量空間中安排盡可能多的碼字向量，這樣才能減少碼字向量中的冗余度；2）許用碼字之間的距離要盡可能的遠(yuǎn)，這樣，即使發(fā)送碼字在傳輸過(guò)程中受到擾亂，仍然能夠以較高的概率實(shí)現(xiàn)正確譯碼。例：線性分組碼該碼共有個(gè)消息向量，因此共有8個(gè)碼字，但是在向量空間中共有個(gè)6元組，所以需要在64個(gè)6元組中選擇8個(gè)來(lái)構(gòu)成碼的所有許用碼字。下表中的8個(gè)碼字構(gòu)成了向量空間的一個(gè)子空間，因此這些碼字就構(gòu)成了一個(gè)線性分組碼。5.3.3生成矩陣對(duì)于線性分組碼，利用前述的方法可以建立消息向量與碼字之間的對(duì)應(yīng)關(guān)系，并可以用類(lèi)似于表格的結(jié)構(gòu)存儲(chǔ)下來(lái)，這樣編碼器便可以通過(guò)查表的方法來(lái)實(shí)現(xiàn)對(duì)不同消息向量的編碼操作。如果的取值較大，則利用查表法實(shí)現(xiàn)編碼器的復(fù)雜度會(huì)非常巨大。以碼為例，該碼共有個(gè)（約為）碼字，此時(shí)如果仍使用簡(jiǎn)單的查表法來(lái)進(jìn)行編碼的話，會(huì)對(duì)計(jì)算機(jī)的內(nèi)存空間提出巨大需求。因此需要尋找更為實(shí)用的編碼實(shí)現(xiàn)方法：可以通過(guò)按需生成而非存儲(chǔ)所有碼字的方法來(lái)減小編碼過(guò)程的復(fù)雜度。子空間的基一個(gè)線性分組碼的碼字集合是二進(jìn)制維向量空間的一個(gè)維子空間（），所以通?？梢哉业缴儆趥€(gè)的元組構(gòu)成的集合，該集合中的向量可以生成所有的個(gè)碼字，此時(shí)稱(chēng)這些向量張成了一個(gè)子空間，張成該子空間的最小線性獨(dú)立集合稱(chēng)為子空間的基，而其中包含的向量個(gè)數(shù)稱(chēng)為子空間的維數(shù)。設(shè)由個(gè)線性獨(dú)立的元組向量組成的集合構(gòu)成一個(gè)基，這樣可以使用這些向量來(lái)生成所需的線性分組碼，即個(gè)碼字中的每一個(gè)碼字均可以表示為（取值為0或1）為消息比特。生成矩陣（GeneratorMatrix）如果由個(gè)比特組成的消息序列可以表示為如下的行向量則碼字向量可以如下得到：維矩陣。【例5-3】確定表5-3中線性分組碼的生成矩陣。【解】選取下列3個(gè)線性獨(dú)立的碼字向量來(lái)構(gòu)成生成矩陣：這樣，使用該生成矩陣便可以生成表5-3中的所有碼字，例如：討論：顯然，碼字向量是生成矩陣中行向量的線性組合。因?yàn)橐粋€(gè)線性分組碼可以由其生成矩陣來(lái)完全確定，因此編碼器僅僅需要存儲(chǔ)的個(gè)行向量，而不用存儲(chǔ)所有的個(gè)碼字向量。對(duì)于本例而言，相比于表5-3中顯示的維碼字向量矩陣，編碼器僅需要存儲(chǔ)維的生成矩陣，這可以極大的降低編碼器的復(fù)雜度。5.3.4系統(tǒng)線性分組碼系統(tǒng)碼碼字向量中有連續(xù)位的內(nèi)容與消息向量完全一樣，而剩下的位表示校驗(yàn)比特。系統(tǒng)線性分組碼的生成矩陣具有如下形式：使用系統(tǒng)碼可以進(jìn)一步減小編碼器的復(fù)雜度。系統(tǒng)形式碼字的生成公式為于是【例5-4】給出表5-3中線性分組碼的碼字生成公式?！窘狻恳?yàn)樵诶?-3中已經(jīng)給出了該碼的生成矩陣，因此該碼的碼字可以如下生成：顯然，利用上式得到的碼字為系統(tǒng)碼。5.3.5監(jiān)督矩陣對(duì)于某個(gè)碼維的生成矩陣，一定存在一個(gè)維的監(jiān)督矩陣（Parity-CheckMatrix），該矩陣的行向量與生成矩陣的行向量正交，即對(duì)于該碼的任意一個(gè)碼字，均有判斷碼字是由矩陣生成的充要條件為。對(duì)于系統(tǒng)碼而言，其生成矩陣形式為，為了保證與生成矩陣之間的正交性要求，其監(jiān)督矩陣顯然應(yīng)具有如下結(jié)構(gòu)【例5-5】給出表5-3中碼的監(jiān)督矩陣，并驗(yàn)證。【解】由例5-3可知該碼的生成矩陣，于是可知監(jiān)督矩陣為因此，可得由例5-4可知，代入上式可得線性分組碼的最小碼距和監(jiān)督矩陣之間關(guān)系假如選擇是具有最小重量（或）的碼字，那么由關(guān)系式可知監(jiān)督矩陣中有列是線性相關(guān)的；另一方面，由于沒(méi)有重量小于的碼字，所以中不可能會(huì)有少于列是線性相關(guān)的。例：觀察例5-5中碼的監(jiān)督矩陣，可以發(fā)現(xiàn)其線性相關(guān)的列向量的最小數(shù)目為3，所以可以確定該碼的最小碼距為。

等于中線性相關(guān)的列向量的最小數(shù)目，也就是說(shuō)的列空間是維的。對(duì)偶碼一個(gè)線性分組碼是向量空間的一個(gè)維子空間，因此會(huì)有一個(gè)正交補(bǔ)集（OrthogonalComplement），即由所有正交于的向量組成的集合。顯然，正交補(bǔ)集是向量空間的一個(gè)維子空間，所以也表示了一個(gè)線性分組碼，稱(chēng)為碼的對(duì)偶碼（DualCode）?？梢宰C明，碼的生成矩陣是對(duì)偶碼的一個(gè)監(jiān)督矩陣。5.3.6伴隨式校驗(yàn)錯(cuò)誤圖樣（ErrorPattern）對(duì)于編碼器輸出的一個(gè)碼字，傳輸過(guò)程中某些位可能會(huì)出錯(cuò)，這樣經(jīng)過(guò)信道傳輸后的接收向量可以表示為式中表示信道傳輸引起的錯(cuò)誤向量，稱(chēng)為錯(cuò)誤圖樣。顯然，對(duì)于長(zhǎng)度為的二進(jìn)制碼字，一共有個(gè)可能的非零錯(cuò)誤圖樣。伴隨式（Syndrome）對(duì)于接收向量，定義下面的維向量為對(duì)應(yīng)于的伴隨式：譯碼器為了進(jìn)行校驗(yàn)會(huì)計(jì)算其伴隨式：如果是一個(gè)合法碼字，則其對(duì)應(yīng)的伴隨式；如果中包含可檢測(cè)到的錯(cuò)誤，則其對(duì)應(yīng)的伴隨式中會(huì)有非零元素值；如果中包含可糾正的錯(cuò)誤，則其伴隨式中會(huì)有特殊的非零值來(lái)標(biāo)記特定的錯(cuò)誤圖樣。顯然即由受擾碼字向量或是對(duì)應(yīng)的錯(cuò)誤圖樣得到的伴隨式是一樣的。線性分組碼有一個(gè)重要的性質(zhì)（譯碼的基礎(chǔ)）：可糾正的錯(cuò)誤圖樣和伴隨式是一一對(duì)應(yīng)的。由上式可知，監(jiān)督矩陣應(yīng)具有下列兩個(gè)重要性質(zhì)：監(jiān)督矩陣的列向量不能有全零向量。否則，在對(duì)應(yīng)的碼字位置發(fā)生的錯(cuò)誤不會(huì)改變伴隨式，故該種錯(cuò)誤不能檢測(cè)到。監(jiān)督矩陣的所有列向量必須彼此不同。否則，如果中的兩列是相同的，則發(fā)生在這兩個(gè)對(duì)應(yīng)位置的錯(cuò)誤將是不可區(qū)分的?！纠?-6】仍考慮前例中的線性分組碼，假設(shè)當(dāng)發(fā)送碼字為時(shí)，接收向量是。求伴隨式，并驗(yàn)證其等于?！窘狻坑山邮障蛄靠傻闷浒殡S式為

顯然錯(cuò)誤圖樣為，于是5.3.7錯(cuò)誤糾正標(biāo)準(zhǔn)陣列（StandardArray）對(duì)于一個(gè)碼，標(biāo)準(zhǔn)陣列是由所有個(gè)可能的比特長(zhǎng)的接收向量組成的列行的陣列。結(jié)構(gòu)如下：第一行由所有的合法碼字構(gòu)成，其中第一個(gè)元素為全零碼字；第一列包含所有可糾正的錯(cuò)誤圖樣；每一行稱(chēng)為一個(gè)陪集（Coset），每行的第一個(gè)元素表示一個(gè)錯(cuò)誤圖樣，稱(chēng)為陪集首（CosetLeader），每行后面的元素都是合法碼字被該行陪集首擾亂后的接收向量。標(biāo)準(zhǔn)陣列的結(jié)構(gòu)：結(jié)構(gòu)特點(diǎn)：標(biāo)準(zhǔn)陣列第一行第一列的元素為全零碼字，該元素有雙重作用：既是合法碼字之一，又可看作是一個(gè)錯(cuò)誤圖樣，表示傳輸過(guò)程中沒(méi)有錯(cuò)誤發(fā)生，即。標(biāo)準(zhǔn)陣列包含了向量空間中所有的個(gè)元組，每個(gè)元組在標(biāo)準(zhǔn)陣列中僅出現(xiàn)一次，這樣，每個(gè)陪集包含個(gè)元組，標(biāo)準(zhǔn)陣列中共有個(gè)陪集。利用標(biāo)準(zhǔn)陣列的譯碼思想：將受擾的接收向量（標(biāo)準(zhǔn)陣列中第一行之外的其它元組）糾正為該向量所在列頂部的合法碼字。假設(shè)一個(gè)合法碼字（）通過(guò)一個(gè)噪聲干擾的信道傳輸，得到的受擾接收向量為，式中。如果信道引起的錯(cuò)誤圖樣是一個(gè)陪集首，接收向量會(huì)被正確的糾正為傳輸碼字；如果錯(cuò)誤圖樣不是一個(gè)陪集首，則會(huì)導(dǎo)致譯碼錯(cuò)誤發(fā)生。陪集的伴隨式如果是第個(gè)陪集的陪集首（即錯(cuò)誤圖樣），則將會(huì)是該陪集中的一個(gè)元組，該元組的伴隨式為因?yàn)槭且粋€(gè)合法碼字，所以，于是上式變?yōu)閺纳鲜娇芍号慵?biāo)準(zhǔn)陣列的每行）中的每一個(gè)元素均有相同的伴隨式，而不同陪集對(duì)應(yīng)的伴隨式則彼此均不相同，這樣便可以通過(guò)伴隨式來(lái)估計(jì)對(duì)應(yīng)的錯(cuò)誤圖樣。糾錯(cuò)譯碼的步驟：(1)計(jì)算接收向量的伴隨式；(2)從標(biāo)準(zhǔn)陣列中找到某個(gè)陪集首（錯(cuò)誤圖樣），使得其伴隨式也等于；(3)利用式將接收向量糾正為合法碼字。該式可以理解為從接收向量中減去了找到的錯(cuò)誤圖樣，由于是二進(jìn)制運(yùn)算，所以減法和加法是相同的。例：對(duì)前面討論的碼使用標(biāo)準(zhǔn)陣列來(lái)進(jìn)行譯碼。給出該碼的一個(gè)標(biāo)準(zhǔn)陣列，如下表：8個(gè)合法碼字構(gòu)成了標(biāo)準(zhǔn)陣列的第一行。第一列中的7個(gè)非零陪集首表示可糾正的錯(cuò)誤圖樣。在剩下的8個(gè)6元組構(gòu)成的陪集中，可以靈活的選擇一個(gè)作為陪集首。所有重量為1的錯(cuò)誤圖樣（共有6個(gè)）均是可以糾正的。注意：當(dāng)且僅當(dāng)信道引起的真實(shí)錯(cuò)誤圖樣是該標(biāo)準(zhǔn)陣列中的一個(gè)陪集首時(shí)，譯碼結(jié)果才是正確的。對(duì)于一個(gè)糾錯(cuò)能力為的碼，如果標(biāo)準(zhǔn)陣列的陪集首正好包含所有的不大于個(gè)錯(cuò)誤的錯(cuò)誤圖樣，且不包含任何其它錯(cuò)誤圖樣（即沒(méi)有多余的糾錯(cuò)能力），則稱(chēng)該碼為完美碼（PerfectCode）。陪集首的選擇：應(yīng)按照錯(cuò)誤圖樣重量從小到大的順序來(lái)排列。重量小的錯(cuò)誤圖樣出現(xiàn)的概率更高，這樣才能使得正確譯碼的概率最高。例如，對(duì)于錯(cuò)誤轉(zhuǎn)移概率為的二進(jìn)制對(duì)稱(chēng)信道，上述碼的碼字經(jīng)過(guò)該信道傳輸之后，不發(fā)生錯(cuò)誤的概率為：發(fā)生1比特錯(cuò)誤的概率為：發(fā)生2比特錯(cuò)誤的概率為：發(fā)生3比特錯(cuò)誤的概率為：以此類(lèi)推。接下來(lái)，通過(guò)計(jì)算的值可以獲得每個(gè)陪集首對(duì)應(yīng)的伴隨式，而這些伴隨式均對(duì)應(yīng)可以糾正的錯(cuò)誤圖樣。即故各個(gè)陪集首對(duì)應(yīng)的伴隨式計(jì)算結(jié)果如右表：糾錯(cuò)對(duì)于接收向量，在計(jì)算得到其伴隨式之后，可以通過(guò)形如上頁(yè)的伴隨式查詢(xún)表來(lái)找到對(duì)應(yīng)的錯(cuò)誤圖樣。這樣得到的錯(cuò)誤圖樣是實(shí)際錯(cuò)誤圖樣的一個(gè)估計(jì)值，可以記作，然后譯碼器將其與接收向量相加，便可得到發(fā)送碼字的估計(jì)值：由上式可知：假如估計(jì)的錯(cuò)誤圖樣與實(shí)際的錯(cuò)誤圖樣相同，即，那么得到的碼字估計(jì)值與發(fā)送的實(shí)際碼字相等；假如錯(cuò)誤圖樣的估計(jì)值不正確，則譯碼器得到的碼字估計(jì)值不是實(shí)際的發(fā)送碼字，這會(huì)導(dǎo)致無(wú)法檢測(cè)的譯碼錯(cuò)誤發(fā)生?！纠?-7】繼續(xù)考慮上述碼，假設(shè)當(dāng)發(fā)送碼字為時(shí)的接收向量為，利用表5-6所示的伴隨式查詢(xún)表對(duì)進(jìn)行譯碼?！窘狻坑山邮障蛄靠梢郧蟮冒殡S式為通過(guò)伴隨式查詢(xún)表可知與該伴隨式對(duì)應(yīng)的錯(cuò)誤圖樣的估計(jì)值為于是糾正后的碼字估計(jì)值為顯然，得到的錯(cuò)誤圖樣估計(jì)值與實(shí)際的錯(cuò)誤圖樣一樣，所以譯碼結(jié)果正確。討論：對(duì)于所有重量為1的錯(cuò)誤圖樣，該碼均可以正確譯碼；對(duì)于重量為2以上的錯(cuò)誤圖樣，該碼僅可以對(duì)錯(cuò)誤圖樣為時(shí)的接收向量實(shí)現(xiàn)正確譯碼。例如，對(duì)于同樣的發(fā)送碼字，經(jīng)過(guò)三次不同傳輸之后的接收向量分別為、和，易得它們對(duì)應(yīng)的伴隨式均為，查表5-6之后可得錯(cuò)誤圖樣的估計(jì)值均為，于是、和譯碼后得到的碼字估計(jì)值分別為顯然只有第一次傳輸?shù)慕邮障蛄靠梢詫?shí)現(xiàn)正確譯碼，而后兩次傳輸?shù)慕邮障蛄繒?huì)發(fā)生譯碼錯(cuò)誤。5.3.8譯碼器電路對(duì)于碼長(zhǎng)較短的線性分組碼，可以用異或門(mén)和與門(mén)構(gòu)成的簡(jiǎn)單電路來(lái)實(shí)現(xiàn)譯碼。接下來(lái)以碼為例說(shuō)明譯碼器電路的結(jié)構(gòu)。根據(jù)前述譯碼程序，先根據(jù)接收向量來(lái)計(jì)算其對(duì)應(yīng)的伴隨式：接著，利用得到的伴隨式進(jìn)而確定錯(cuò)誤圖樣的估計(jì)值，然后將錯(cuò)誤圖樣的估計(jì)值與接收向量進(jìn)行模2加即可完成譯碼。碼的譯碼電路為圖中電路只能糾正1位錯(cuò)誤，若是想要實(shí)現(xiàn)對(duì)2位錯(cuò)誤的糾正則需要更多的額外電路。如果線性分組碼的碼長(zhǎng)較長(zhǎng)，這種電路的實(shí)現(xiàn)將會(huì)非常復(fù)雜，更好的譯碼方法是使用串行方法來(lái)代替此處的并行方法。§5.4線性分組碼的檢錯(cuò)和糾錯(cuò)能力通過(guò)一個(gè)例子來(lái)討論線性分組碼的檢錯(cuò)和糾錯(cuò)能力。圖中和表示兩個(gè)合法碼字，它們之間的漢明距離為5，而圖中的實(shí)心圓點(diǎn)表示發(fā)送碼字受擾后可能得到的接收向量。根據(jù)最大似然譯碼準(zhǔn)則，如果接收向量落在區(qū)域1則譯碼為，如果接收向量落在區(qū)域2則譯碼為。如果接收向量如圖(a)中的，即離和的距離分別為1和4，那么會(huì)將譯碼為。假如是碼字發(fā)生1位錯(cuò)誤的結(jié)果，那么譯碼器便能實(shí)現(xiàn)正確的譯碼；假如是碼字發(fā)生4位錯(cuò)誤的結(jié)果，那么譯碼器會(huì)發(fā)生譯碼錯(cuò)誤。如果接收向量如圖(b)中的，即與和的距離分別為2和3，那么會(huì)將譯碼為。假如是碼字發(fā)生2位錯(cuò)誤的結(jié)果，那么譯碼器便能實(shí)現(xiàn)正確的譯碼；假如是碼字發(fā)生3位錯(cuò)誤的結(jié)果，那么譯碼器會(huì)發(fā)生譯碼錯(cuò)誤。如果接收向量如圖(c)中的，即與和的距離分別為3和2，那么會(huì)將譯碼為。假如是碼字發(fā)生2位錯(cuò)誤的結(jié)果，那么譯碼器便能實(shí)現(xiàn)正確的譯碼；假如是碼字發(fā)生3位錯(cuò)誤的結(jié)果，那么譯碼器會(huì)發(fā)生譯碼錯(cuò)誤。如果將該碼只用于檢錯(cuò)，那么所有落在圖中實(shí)心圓點(diǎn)上的接收向量均可以被檢測(cè)出錯(cuò)誤，即可以檢查出4位以下的錯(cuò)誤。但是，如果傳輸過(guò)程中發(fā)生了5位錯(cuò)誤，那么一個(gè)合法碼字會(huì)被錯(cuò)譯為另一個(gè)合法碼字，此時(shí)會(huì)發(fā)生不可檢測(cè)的譯碼錯(cuò)誤。從上面的討論可以發(fā)現(xiàn)：線性分組碼的檢錯(cuò)和糾錯(cuò)能力與該碼的最小碼距之間有著密切的關(guān)系。求得線性分組碼最小碼距的方法：只需要找到所有合法碼字（全零碼字除外）中漢明重量最小的那個(gè)碼字，其重量便是該碼的最小碼距。由線性分組碼的定義可知，任意兩個(gè)合法碼字之和仍然是一個(gè)合法碼字，即對(duì)于某個(gè)線性分組碼，如果碼字，則有。對(duì)于二進(jìn)制線性分組碼而言，由5.2.3小節(jié)的討論可知，兩個(gè)碼字之間的漢明距離實(shí)際上就是兩個(gè)碼字模2相加結(jié)果的漢明重量?？梢宰C明，對(duì)于一個(gè)最小碼距為的線性分組碼，關(guān)于其檢錯(cuò)和糾錯(cuò)能力有如下結(jié)論：如果該碼只用于糾錯(cuò)，可以確保能夠糾正的錯(cuò)誤位數(shù)最多為如果該碼只用于檢錯(cuò)，可以確保檢測(cè)出的錯(cuò)誤位數(shù)最多為如果該碼同時(shí)用于糾正個(gè)錯(cuò)誤、檢測(cè)個(gè)錯(cuò)誤（），則要求最小碼距和糾錯(cuò)能力的關(guān)系：討論1：只用于糾錯(cuò)的公式對(duì)于能夠確保糾正個(gè)以下錯(cuò)誤的碼，也可能具有糾正某些個(gè)錯(cuò)誤的能力。例如表5-5中標(biāo)準(zhǔn)陣列給出的(6,3)碼的最小碼距為，因此可以確保糾正1位錯(cuò)誤，但是也能糾正一個(gè)2位的錯(cuò)誤。一般來(lái)說(shuō)，能夠糾正個(gè)錯(cuò)誤的線性分組碼一共能夠糾正個(gè)錯(cuò)誤圖樣。討論2：只用于檢錯(cuò)時(shí)的公式對(duì)于能夠確保可以檢測(cè)出位以下錯(cuò)誤的碼，也有可能檢測(cè)出一部分多于位錯(cuò)誤的錯(cuò)誤圖樣。一般來(lái)說(shuō)，線性分組碼一共能夠檢測(cè)出個(gè)錯(cuò)誤圖樣。因?yàn)樵摯a共有個(gè)可能的非零錯(cuò)誤圖樣，其中有個(gè)與非零碼字相同的錯(cuò)誤圖樣是不能檢測(cè)出來(lái)的（一個(gè)碼字會(huì)錯(cuò)為另一個(gè)碼字），因此共有個(gè)可以檢測(cè)出的錯(cuò)誤圖樣。譯碼器不能檢測(cè)出錯(cuò)誤的概率對(duì)于線性分組碼，令表示重量為的碼字?jǐn)?shù)量，則稱(chēng)為該碼的重量分布（WeightDistribution）。假如該碼僅用于檢錯(cuò)并通過(guò)二進(jìn)制對(duì)稱(chēng)信道傳輸（錯(cuò)誤轉(zhuǎn)移概率為），可以證明譯碼器不能檢測(cè)出錯(cuò)誤的概率為如果該碼的最小碼距為，那么顯然從到的值都是0。【例5-8】如果將表5-3中的碼用于檢錯(cuò)，并假設(shè)傳輸信道為錯(cuò)誤轉(zhuǎn)移概率為的二進(jìn)制對(duì)稱(chēng)信道，求該碼不能檢測(cè)出錯(cuò)誤的概率。由表中的碼字可以統(tǒng)計(jì)出：，，，，因此，不能檢測(cè)出錯(cuò)誤的概率為討論3：同時(shí)糾正個(gè)錯(cuò)誤、檢測(cè)個(gè)錯(cuò)誤（）的公式由上式可知：如果不多于個(gè)錯(cuò)誤發(fā)生，該碼可以檢測(cè)和糾正這些錯(cuò)誤；如果多于個(gè)但是小于個(gè)錯(cuò)誤發(fā)生，則該碼可以檢測(cè)到錯(cuò)誤的存在但是僅僅能糾正其中一部分。例如，對(duì)于最小碼距為的線性分組碼，可以采用下表中的方案之一來(lái)進(jìn)行檢錯(cuò)或糾錯(cuò)。糾錯(cuò)意味著首先要檢錯(cuò)。比如：當(dāng)發(fā)生3位錯(cuò)誤時(shí)，該碼可以檢測(cè)所有錯(cuò)誤并能進(jìn)行糾正；而當(dāng)發(fā)生5位錯(cuò)誤時(shí)，該碼可以檢測(cè)出所有錯(cuò)誤但是僅能糾正其中1位錯(cuò)誤的情況?！纠?-9】討論重復(fù)碼和重復(fù)碼的檢錯(cuò)和糾錯(cuò)能力?！窘狻肯葋?lái)考慮重復(fù)碼，顯然兩個(gè)合法碼字分別是和，且該碼的碼率為，最小碼距為。如果該碼用于檢錯(cuò)，由可知該碼最多可以檢測(cè)出2個(gè)錯(cuò)誤。例如，當(dāng)發(fā)送碼字為時(shí)，只要錯(cuò)誤比特個(gè)數(shù)不超過(guò)兩個(gè)均可以發(fā)現(xiàn)，如下圖：如果該碼用于糾錯(cuò)，由可知該碼可以糾正1個(gè)錯(cuò)誤。例如下圖，對(duì)于發(fā)送碼字，根據(jù)最小距離譯碼準(zhǔn)則，只有當(dāng)接收向量為、或時(shí)才能實(shí)現(xiàn)正確譯碼，而當(dāng)接收向量為、或時(shí)會(huì)被錯(cuò)誤的糾正為碼字。當(dāng)該碼通過(guò)錯(cuò)誤轉(zhuǎn)移概率為的二進(jìn)制對(duì)稱(chēng)信道傳輸時(shí)，譯碼錯(cuò)誤概率為接著考慮重復(fù)碼，顯然兩個(gè)合法碼字分別是和，且該碼的碼率為，最小距離為。如果該碼用于檢錯(cuò)，由可知該碼最多可以檢測(cè)出3個(gè)錯(cuò)誤。例如當(dāng)發(fā)送碼字為時(shí)，只要錯(cuò)誤個(gè)數(shù)不超過(guò)三個(gè)均可以發(fā)現(xiàn)，如下圖：如果只用于糾錯(cuò)，由可知該碼只可以糾正1個(gè)錯(cuò)誤，如下面左圖所示；如果同時(shí)用于檢錯(cuò)和糾錯(cuò)，由可知該碼可以同時(shí)糾正1個(gè)錯(cuò)誤、檢查出2個(gè)錯(cuò)誤，如下面右圖所示。接收向量為下列情況時(shí)可以實(shí)現(xiàn)正確譯碼：接收向量為下列情況時(shí)可以檢測(cè)出錯(cuò)誤：接收向量為下列情況時(shí)會(huì)被錯(cuò)誤的糾正為其他碼字：當(dāng)該碼通過(guò)錯(cuò)誤轉(zhuǎn)移概率為的二進(jìn)制對(duì)稱(chēng)信道傳輸時(shí)，譯碼錯(cuò)誤概率為討論：隨著碼長(zhǎng)的增加，重復(fù)碼的抗干擾能力會(huì)越來(lái)越強(qiáng)，但是碼率會(huì)越來(lái)越低，且隨著的增加會(huì)趨近于零?！纠?-10】討論碼長(zhǎng)分別為時(shí)偶校驗(yàn)碼的檢錯(cuò)和糾錯(cuò)能力?！窘狻肯瓤紤]偶校驗(yàn)碼，顯然該碼只有2個(gè)合法碼字，分別為和，且該碼的碼率為，最小碼距為，因此該碼僅能檢測(cè)出1個(gè)錯(cuò)誤。若該碼通過(guò)錯(cuò)誤轉(zhuǎn)移概率為的二進(jìn)制對(duì)稱(chēng)信道傳輸，顯然發(fā)生2位錯(cuò)誤時(shí)譯碼器不能檢測(cè)出錯(cuò)誤，因此譯碼器不能檢測(cè)出錯(cuò)誤的概率為如果用碼字重量來(lái)計(jì)算，該碼的重量分布為，于是有接著考慮偶校驗(yàn)碼，顯然該碼有個(gè)碼字，分別為該碼的碼率為，最小碼距為，因此該碼也只能檢測(cè)出1個(gè)錯(cuò)誤。若該碼通過(guò)錯(cuò)誤轉(zhuǎn)移概率為的二進(jìn)制對(duì)稱(chēng)信道傳輸時(shí)，顯然發(fā)生2位錯(cuò)誤時(shí)譯碼器不能檢測(cè)出錯(cuò)誤，因此譯碼器不能檢測(cè)出錯(cuò)誤的概率為如果用碼字重量來(lái)計(jì)算，該碼的重量分布為，，于是有再來(lái)考慮偶校驗(yàn)碼，顯然該碼有個(gè)碼字，分別為該碼的碼率為，最小碼距為，由公式可知該碼可以確保檢測(cè)出1個(gè)錯(cuò)誤，但是容易發(fā)現(xiàn)實(shí)際上該碼也可以檢測(cè)出所有的3個(gè)錯(cuò)誤。若該碼通過(guò)錯(cuò)誤轉(zhuǎn)移概率為的二進(jìn)制對(duì)稱(chēng)信道傳輸時(shí)，顯然發(fā)生2位或4位錯(cuò)誤時(shí)譯碼器不能檢測(cè)出錯(cuò)誤，因此譯碼器不能檢測(cè)出錯(cuò)誤的概率為如果用碼字重量來(lái)計(jì)算，該碼的重量分布為，，，于是有討論：推廣開(kāi)來(lái)可以發(fā)現(xiàn)，隨著碼長(zhǎng)的增加，當(dāng)時(shí)奇偶校驗(yàn)碼的碼率，但最小距離總是，系統(tǒng)誤碼率會(huì)接近無(wú)編碼系統(tǒng)時(shí)的情況，即隨著碼長(zhǎng)的增加，奇偶校驗(yàn)碼的抗干擾能力接近于零?！?.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)移位次后得到的碼字向量?！纠?-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)碼存在性?xún)H當(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)碼?！窘狻坎楸砜芍囊蚴椒纸饨Y(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ì)偶碼。【解】由例5-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)行向量便可以最后得到該碼的生成矩陣。【例5-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)造滿(mǎn)足參數(shù)要求的新碼。在進(jìn)行碼設(shè)計(jì)的時(shí)候，為了滿(mǎn)足預(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)的碼字向量為。【例5-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ù)?！纠?-18】對(duì)于多項(xiàng)式和，給出完成除以運(yùn)算的除法電路。【解】利用長(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ù)共為?！纠?-19】對(duì)于生成矩陣為的循環(huán)碼，請(qǐng)給出該碼的編碼電路，并對(duì)消息向量進(jìn)行系統(tǒng)編碼?！窘狻坑衫?-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)行譯碼?！窘狻吭摯a的伴隨式計(jì)算電路如下圖，該電路的狀態(tài)變化如下表所示：伴隨式為。因?yàn)樵摯a的最小碼距為，所以可以確保糾正1位錯(cuò)誤，并且容易求得該碼的伴隨式查詢(xún)表如下所示：現(xiàn)在已得伴隨式為，通過(guò)查詢(xún)左表可知對(duì)應(yīng)于該伴隨式最為可能的錯(cuò)誤圖樣為，因此譯碼結(jié)果為于是信息比特為討論利用計(jì)算伴隨式然后查詢(xún)標(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)譯碼器按照以上步驟對(duì)接收到的符號(hào)進(jìn)行逐位譯碼，直到從寄存器中讀出整個(gè)接收向量為止?！纠?-21】給出生成多項(xiàng)式為的循環(huán)碼的梅吉特譯碼器結(jié)構(gòu)，并給出接收向量為時(shí)的譯碼過(guò)程?！窘狻吭摯a的梅吉特譯碼器如下圖所示。圖中伴隨式寄存器的結(jié)構(gòu)由決定，顯然與圖5-15一致；錯(cuò)誤圖樣檢測(cè)電路的結(jié)構(gòu)由表5-14中第一行結(jié)果來(lái)決定，即只有當(dāng)伴隨式向量為時(shí)，與門(mén)的輸出才為1；而接收向量寄存器此時(shí)是一個(gè)7位的移位寄存器。根據(jù)上圖結(jié)構(gòu)和輸入的接收向量，該譯碼器的具體譯碼過(guò)程可以用下表來(lái)詳細(xì)表示。由該表的最右側(cè)一列可知最后的譯碼結(jié)果為。5.5.9循環(huán)碼實(shí)例漢明碼（HammingCode）漢明碼是信道編碼理論研究歷史上較早出現(xiàn)的一種線性分組編碼方案，該碼具有如下的參數(shù)設(shè)置：

(5-75)漢明碼的構(gòu)造用其監(jiān)督矩陣來(lái)描述比較方便。由前面對(duì)線性分組碼的討論可知監(jiān)督矩陣的維度為，而漢明碼監(jiān)督矩陣的各列分別由所有個(gè)非全零的二進(jìn)制元組構(gòu)成。漢明碼的碼率為

(5-76)顯然，隨著值的變大漢明碼的碼率會(huì)趨近于1。漢明碼的最小碼距始終為?！纠?-22】設(shè)計(jì)一個(gè)的漢明碼?！窘狻吭摯a的碼長(zhǎng)為，消息符號(hào)個(gè)數(shù)為