第8章 信道編碼

1、第8章 信道編碼知識點基本內(nèi)容：通過第1章了解信道特征和仙農(nóng)信道容量公式基本概念基礎上，主要介紹波形編碼和分組碼、循環(huán)碼以及卷積碼等的基本編解碼方法及評價。知識點及層次(1) 波形編碼主要認識基于正交的哈德瑪正交碼的特性。(2) 基于漢明距離的差錯控制定理（掌握）。(3) 線性分組碼(n，k)碼的結構、編碼方法、解碼、檢糾錯計算（掌握）。(4) 循環(huán)碼的構成特征及編、解碼方法（掌握），以及CRC、R-S、BCH碼的特征（了解）。(5) 卷積碼的基本特征（熟悉概念），TCM（一般認識）。 8.1 波形編碼 信道編碼包括信號波形編碼與差錯控制編碼（也稱結構化序列），前者是較一般自然碼具有較小的誤符

2、號性能，后者則旨在接收端發(fā)現(xiàn)錯誤或自動糾錯。我們首先介紹基于正交概念的各類波形編碼，作為前面章節(jié)中編碼技術的進一步討論。 正交信號 優(yōu)良的信號設計應首先是基于正交為目標。如：雙極性不歸零碼、2PSK等，均屬于“正反信號對”，即二元信號波形滿足 ，它們的相關系數(shù)為 ；其次，如CPFSK，頻移指數(shù) ，相關系數(shù) ，而 的例子就更多，如：ASK、FSK、MSK、DQPSK、QPSK、QAM、MFSK等，由于這些信號均值都為0，它們的二元信號、4元或 元信號間均不相關，亦即正交。因此 就是正交。一般地，任何信號 與 之間的相關性（系數(shù)）不外乎有1 1。在傳輸信號設計中，總是在1 0范圍內(nèi)制定設計策略，當

3、1 <0時稱為超正交， 0為正交。 基于相關檢測的波形編碼     一個簡單的相關系數(shù)表示式包含了正交關系與相關性，即1 1，但它涉及到整個通信系統(tǒng)設計的幾乎是實質性的因素 取值范圍的左一半，即1 0，總是需要在發(fā)送信號設計中致力于考慮的因素，而經(jīng)過信道失真的接收信號檢測，又總是利用 取值范圍的右邊一半：0< 1，即對于要正確檢測的信號（已含有干擾，即前面提到的混合波形），以提供特定樣本與接收信號最相像（ ）為最佳判決，這就是相關接收或最佳接收的概念。 1.  二元正交碼模式 l     &#

4、160;   最簡單的數(shù)據(jù)0、1，這兩個信息代碼，可由00與01代表，則為正交碼字集，即 （8-1）</SPAN< p> l         4元數(shù)據(jù)：00、01、10、11，其正交碼字集為（8-2）</SPAN< p> 正交碼的特性，其相關系數(shù)為 （8-5）</SPAN< p> 2. 雙正交碼 我們只利用上面 位數(shù)據(jù)的正交碼集 的右邊半矩陣，可構成 位數(shù)據(jù)的雙正交碼集 （8-9）</SPAN< p> 雙正交碼的相關系數(shù)為：

5、 （8-11）</SPAN< p> 3.截短正交碼 從式（8-5）的正交碼集的定義看，若兩碼相對位同號的位數(shù)少于異號位數(shù)，總滿足 ，即超正交條件。對照正交碼字（符號）序列，首位總是“0”，因此可以去掉如式（8-2）中各正交碼字首位的“0”之后，變?yōu)檫@種超正交，這種正交碼也稱“單形”碼（Simplex）。 如： 去掉首位得： （8-12）</SPAN< p> 它的相關系數(shù)通式為 （8-13）</SPAN< p> 4.結論 1）在波形編碼序列中，具有碼字間正交特性的以上三種情況，均為最佳信號設計。 2）它們的正交條件均為 0，（ ），其中 在1

6、 0范圍內(nèi)， 值越負，在同樣接收信噪比 或 時，就具有越小的誤差率；反之，在同樣誤差率時，則需要的 或 代價更小，進而，在相同噪聲信道中，要節(jié)省發(fā)送功率。3）保持正交特性，必須付出代價就是以有效性換取可靠性，如00、01、10、11通常表示的4個信源符號，若利用正交碼，則去掉了“11”，因此4個信碼應由截短正交碼表示為式（8-12）。同樣，碼長 8的PCM碼，共 個，若利用正交碼，則只有8個碼字，其余248個均禁用，這個代價是不小的。當然在實際通信中，話音PCM無須如此正交碼。8.2 差錯控制概述 二元對稱信道和錯誤格式 1.   二元對稱信道特征 在“信息論”中詳細討論過

7、二進制無記憶及有記憶信道特征，本書第二章曾列舉過二元不對稱無記憶信道的后驗概率計算，并可由此計算出“后驗熵”（損失熵），它是信源平均信息量和信道實際傳送的信息量之差，正是造就接收誤差的主因。我們的分析，把信道看作線性時不變系統(tǒng)，且以二元對稱無記憶信道為重點討論。二元對稱信道（BSC）通常是無記憶的，即傳輸?shù)拿總€碼元符號不相關或統(tǒng)計獨立，因此產(chǎn)生的傳輸差錯是隨機性的，而這種信道主要是加性高斯白噪聲導致隨機差錯，因而稱其為隨機信道。隨機差錯率是傳輸錯誤轉移概率造成的。 2.  錯誤格式將發(fā)生錯誤看成是因為加入（模2加）了某種“錯誤格式” 的結果。由于隨機差錯可能發(fā)生在 長碼字的某1位、某

8、幾位，甚至全錯，因此其錯誤格式種類為 （只有1個全0時的 ，沒有差錯），在這 個可能的錯誤中， 長碼總錯誤概率為 （8-16）隨機信道產(chǎn)生錯誤的概率以錯1位為最大。 差錯控制分類     在數(shù)字或數(shù)據(jù)通信系統(tǒng)中，利用抗干擾編碼進行差錯控制，一般分為4類：前向糾錯（FEC），反饋重發(fā)（ARQ），混合糾錯（HEC）和信息反饋（IRQ） 1.      前向糾錯（FEC） FEC方式是在信息碼序列中，以特定結構加入足夠的冗余位稱為監(jiān)督元（或校驗元），接收端解碼器可以按照雙方約定的這種特定的監(jiān)督規(guī)則，自動識別出少量差錯，并

9、能予以糾正。FEC最適于高速數(shù)傳而需實時傳輸?shù)那闆r。2.      反饋重發(fā)（ARQ） 在非實時數(shù)據(jù)傳輸中，常用ARQ差錯控制方式。解碼器對接收碼組逐一按編碼規(guī)則檢測其錯誤。如果無誤，向發(fā)送端反饋“確認”ACK信息；如果有錯，則反饋回ANK信息，以表示請求發(fā)送端重復發(fā)送剛剛發(fā)送過的這一信息。ARQ優(yōu)點在于編碼冗余位較少，可以有較強的檢錯能力，同時編解碼簡單。由于檢錯與信道特征關系不大，在非實時通信中具有普遍應用價值。3.      混合糾錯方式（HEC） 此種方式是上述兩種方式的有機結合，即在糾

10、錯能力內(nèi)，實行自動糾錯，而當超出糾錯能力的錯誤位數(shù)時，可以通過檢測而發(fā)現(xiàn)錯碼，不論錯碼多少，利用ARQ方式進行糾錯。HEC往往是一種折衷性應用，如上述指出的 長碼字錯1位的概率 ，比錯2位時大得多，因此為使編解碼結構避免較高速數(shù)傳要求，常出現(xiàn)1位差錯可以隨時自動糾錯，而2位以及更多錯誤則以ARQ糾錯，但HEC也適于實時傳輸。4.      信息反饋（IRQ） 這是一種全回執(zhí)式最簡單差錯控制方式，接收端將收到的信碼原樣轉發(fā)回發(fā)送端，并與原發(fā)送信碼相比較，若發(fā)現(xiàn)錯誤，則發(fā)送端再進行重發(fā)。只適于低速非實時數(shù)據(jù)通信，是一種較原始的做法。 常用差錯控制碼

11、在介紹差錯控制碼之前，先列出幾種簡單的常用差錯控制碼，對以后理解糾錯碼原理可以有所啟發(fā)。1.        奇、偶校驗碼 對于一般的數(shù)字序列，為了能發(fā)現(xiàn)傳輸中的一位或更多差錯，一種很簡單的方法是在碼字后面加1個冗余碼元（校驗元）。加1位監(jiān)督元后，稱為有檢錯功能的“碼字”，碼長為 。此結果表明，當信碼組的碼重等于 為奇數(shù)，若加入 ，為偶校檢碼；偶數(shù)時加入 構成偶校檢碼；反之亦反。實際上，奇偶檢驗碼就是下面將介紹的 線性分組碼的一種特例，即 ，它們可以檢測出奇數(shù)個錯。2.     

12、;   水平垂直校驗碼（方陣碼） 方陣碼的構成，是將 組 位信碼先排為 行× 列的陣列，然后按既定的奇（偶）校驗規(guī)則，在每行及每列中分別加入奇偶校驗位。因此，它的總碼長為 。其中，信碼數(shù)為 ，校驗位為 + 位。因此它是 分組碼。方陣碼的檢錯優(yōu)勢在于它可以檢測出突發(fā)錯長度不大于 位的行發(fā)生的突發(fā)錯誤，或不大于 位的列突發(fā)錯誤。此種檢錯作用是相當于把1行或1列的突發(fā)錯誤分散到相鄰各碼組中，起到后面將介紹的“交織編碼”的作用。它的好處是，可將突發(fā)錯誤的幾個連續(xù)錯位分散到相鄰碼字中各含1位錯，于是就可糾正。這對于不設反饋信道的單向低速傳輸是有利的。 3. 

13、60;    恒重碼（或等比碼） 這是從 個碼組中，只選出一些特定結構的碼組作為許用碼字，如“五中取三”碼，就是從 32個碼組中，只選用碼重為3的10個碼組作為傳輸碼字，可代表10個信息符號（如10字阿拉伯數(shù)字），而其余22個是禁用碼組。 4.      重復碼 重復碼是與奇偶校驗相反意義的一種簡單分組碼，它是碼長為 ，信碼只有1位的（ ，1）分組碼。如（3，1）重復碼包括000及111兩個碼字。重復碼付出 位的冗余代價，即有 組為禁用，當然可以換取較大的可靠性。（3，1）碼顯然可以糾1位錯，而作為檢錯碼利用，可以

14、有檢出2位錯的能力，這種碼并非優(yōu)秀，只是簡單地用于很低速率的數(shù)據(jù)通信。 信道編碼定理與差錯控制定理 仙農(nóng)（Shannon）信道容量公式為通信研究指出了方向性定律 （8-22） 在高斯白噪聲信道中，每秒信道容量 與信道傳輸帶寬 和信噪比 的定量關系。由仙農(nóng)這一公式，可以直接和間接地推演出信道編碼定理和差錯控制定理。 1信道編碼定理 對于有擾信道的數(shù)字傳輸，仙農(nóng)歸納出：一個具有確定信道容量 的有擾信道，對于任何小于 的信息傳輸速率 ，總存在一種碼長為 ，碼率為 的分組碼，其接收解碼的誤差概率的下限為（8-23） 式中， 為某常數(shù)， 為碼長， 為誤差指數(shù)，它是 的正的實值函數(shù)。增加碼長 ， 就將隨

15、而指數(shù)下降，于是要付出編碼冗余度，且使編解碼系統(tǒng)復雜性增加，而成本加大，這一方法正是本章差錯控制的基本原理。2.        漢明距離      任何一個表示 個信源符號集的碼字集合中的兩個碼字，必定至少有一位不同，如果碼長為 ，這種差距可能為1至 ，如 3時， 8個3位碼字，最小距離為1，最大為3（000與111），將其置為3維空間，稱其為（3維）漢明空間。 我們定義碼組間距離為漢明距離（8-24）按此式，（3，1）重復碼漢明距離 ，即漢明空間中的（111）與（000）。

16、但是，在差錯控制中，我們最關心的是一個許用碼字集合里，它們彼此之間的最小漢明距離 ，它是表明差錯控制能力的下限。大部分正交碼都因不同的冗余，而具有一定差錯控制能力。最簡單的奇偶校驗碼的 2，因此它可檢1位或奇數(shù)個錯。3. 差錯控制定理   線性分組碼 碼，它是碼長為 ，信息碼長為 ，編碼效率（碼率）為 糾錯碼。視其加入的冗余位監(jiān)督元（校驗元）的位數(shù) 的多少，來決定 碼的差錯控制能力。以 表明差錯控制能力的差錯控制定理內(nèi)容如下：（1）       如果欲在接收解碼時檢測出 位錯，則漢明距離應滿足（8-25）（2）&#

17、160;      如果需（自動）糾 位錯，則需（8-26）（3）       如果要求糾 位錯，且同時可檢出 位錯 () （8-27） 最后一個關系式，實際上提供的是混合糾錯方式（HEC）如： 2， 1， 4（至少），后面將介紹的 分組碼就滿足這一關系。該碼的 個許用碼字（包括全0碼字），碼長 ， ，它可以通過一定規(guī)則加入監(jiān)督元 位冗余位，可自動糾正1位錯，同時當發(fā)生2位差錯時，雖然不能糾正，即無法自動找出在7位碼字中哪2位發(fā)生錯誤，但它卻“知道”是錯碼，因而可以通過反向信道，以AR

18、Q方式進行重發(fā)，直至正確檢測，或只有1位錯可糾正為止。   線性分組碼線性分組碼是本章重點介紹的差錯控制碼，由于認識此種碼的思路與概念直觀而條理清晰，并對編碼中的一些重要參量和糾錯能力提供一系列明確的概念，從而也為介紹其它差控碼奠定有力基礎。  線性分組碼的構成1.        監(jiān)督方程組通過上面的邏輯推斷，我們得到式（8-32）這一（7，4）分組碼的一種可監(jiān)督檢測接收碼字是否有錯的模式，然而尚無得到驗證，并且，也需要給出明確的編碼過程?？梢詫⑸鲜竭M行運算，并分出三個獨立的線性方程（8-33）矩陣表示為

19、：（8-34）這個聯(lián)立方程組就是式（8-32）的等效表示，這意味著只要能使它等于0陣時，必定是正確編制的具有糾錯能力的碼字。其中為3個監(jiān)督元，它們分別是（）信息碼組中有關一些碼元的線性組合，即矩陣形式為            （8-35）我們稱式(8-35)為監(jiān)督方程組，它們嚴格規(guī)定了信息碼與監(jiān)督元的制約關系。由方程組與式（8-32）對照，式中組與監(jiān)督元對應的數(shù)值矩陣，是該方程組的各元素權系數(shù)構成的，其突出特點是右邊3行、3列是個單位矩陣，由式（8-35）三個監(jiān)督方程，由于最低次項從上

20、到下各為，因此在數(shù)值矩陣中必然在式(8-32)或(8-36)的數(shù)字矩陣中，出現(xiàn)右邊的單位陣。此外，式（8-32）的模式以及監(jiān)督方程組的產(chǎn)生，前提是表8-2中我們指定了與各碼字位置對應關系，其實本例完全可以“隨意”規(guī)定，仍不失我們上面的可行性思路的正確性。如：我們可以將上面數(shù)值矩陣右邊列亂序排列（其他例子未必合適），則得（8-37）它所對應的監(jiān)督方程組為（8-38）該聯(lián)立方程組中每個監(jiān)督方程均為信碼線性組合，各方程為線性獨立，符合線性迭加原理，因此也是合理的，但依不同的監(jiān)督方程組構成形式，此后編制出的碼的具體碼字不會完全相同，不過，它們的本質特征及其差錯控制能力毫無差異，其它碼可能會有例外，后面

21、將要進一步說明。2.      一致監(jiān)督（校驗）矩陣我們將上述形成的監(jiān)督方程組中,各元素排列的權系數(shù)構成的矩陣稱為一致監(jiān)督（校驗）矩陣，并以表示，于是由式（8-32），有（8-39）矩陣由兩部分拼成，即包括與兩個陣列即             （單位陣）（8-40）矩陣將在接收解碼時起到檢測及糾正錯誤的作用。至于在有了矩陣后，如何生成個非全0的位長的糾錯碼，可通過獲得生成矩陣來加以解決。3.   

22、   生成矩陣碼的生成矩陣可以通過已得的監(jiān)督方程組式（8-34）得到，即在式中，再加上碼的7位碼中尚未列出的4個信息碼元，則得（8-41）這一完善的個方程組，就是分組碼的通式。為明了起見，我們將其表示為矩陣運算形式，則該碼碼字為              （8-42）這里，“”表示矩陣轉置，即將原矩陣行變列，列變行。式中，作為生成矩陣，在本例中（8-43）這里是4×4單位矩陣。對式（8-39）中矩陣左半部分矩陣與得到的矩陣中右半部分矩陣

23、進行比較，可以發(fā)現(xiàn)，與二者互為轉置關系即            或     （8-46）并且，與矩陣的特點之一是：矩陣右方為單位矩陣（這里為），矩陣左方總是單位矩陣，（這里為），加之兩陣中含有的與關系，因此在由監(jiān)督方程組系數(shù)構成矩陣后，可以很方便地得到矩陣只要按直接寫出即可?，F(xiàn)在可由矩陣，對于給出的任何信碼組與進行矩陣運算，可得全部碼結構的個非全0碼字，而個碼組則為禁用碼組。例如，按上面碼的矩陣式（8-42），可求出的相應碼字這一結果是由信碼序列

24、1101與矩陣逐列相乘后，4個乘得的結果進行模2加，而得到7個結果數(shù)值，就是相應編碼碼元值。模2加法：，模2乘法：，通過上述運算，我們可以得到分組碼的全部（個）非全0碼，加上全0碼，其許用碼字為個，可以表示有糾錯能力的個信源編碼進行糾錯傳輸。4.      與矩陣的特征（1）與矩陣的關系由與的分塊表示的矩陣形式   及      而   或       則有   &#

25、160; 或   （8-50）（2）矩陣的特點1）矩陣是通過設計碼的個監(jiān)督方程之后，抽取其系數(shù)構成的。2）它的行數(shù)為行，矩陣的右半部分為單位矩陣，這種形式的構成的碼稱為系統(tǒng)碼長碼字中信息碼組均在前位，后位為監(jiān)督位，是碼的標準形式。3）矩陣與碼的任何一個許用碼字進行相乘的結果必等于0，即若是任一碼字，則必有。若不屬于許用碼字，或有傳輸差錯，且差錯位數(shù)在碼糾錯能力內(nèi)，則運算結果將為非0值，此時，可以糾錯或檢錯重發(fā)。如本例中發(fā)生1位錯時，其運算結果一定會等于矩陣的某一列，這就表明是接收碼組中的該對應碼位發(fā)生錯誤，于是能夠即時自動糾錯，這一基本原理在下面伴隨式解碼運算時將

26、進一步解釋。4）矩陣中不含全0列。對于本例碼的矩陣，除其中單位陣外，其余列為矩陣（），因此陣中含非0列共列，從001至111全部被利用。于是，不論個監(jiān)督方程怎樣構成，即中矩陣中各列如何排列，如式（8-37），只要符合線性獨立，均可得到同樣能力的碼。但是，另一方面，如碼，則矩陣為4行×7列，由于，因此，除了單位矩陣的4列之外，只尚需3列，它們從個未被利用的非全0的4位碼組中合理選用返回到設計個監(jiān)督方程組如何設計就必須慎重。（3）矩陣的特點1）矩陣的行中的每一行，長度為，均為碼的碼字，并且任意兩行模2加，也是一個許用碼字這一特點稱為分組碼的封閉性質。2）由矩陣求全部非0碼字時，由于其構成

27、為形式，與矩陣的相對應，這種結構特征生成的碼為系統(tǒng)碼編出的全部碼字，中的前位完全對應是信息碼序列而后面位全是監(jiān)督元，如碼的全部碼字，從高位數(shù)共位，均為源編碼信息碼組。這就是系統(tǒng)碼特征。因此在以來編制碼時，可以直接把的這位信碼寫出而不必計算，只是以與中矩陣的列分別運算，依次得到個監(jiān)督位，再寫在序列之后，就得到的一個碼字。由于中已含有個碼字，因此只需計算個，即得全部個非0碼5.         分組碼的糾錯能力     由糾錯定理我們已經(jīng)明確認識到，一個分組碼的差錯控制

28、能力大小，完全取決于漢明距離，碼的個碼字中由于包括全0碼，因此欲求出該碼的，只需從非全0碼中找到最小碼重就是最小漢明距離。值除通過碼字來逐一計算得出外，后面可通過與的關系給出估算的關系式。知道了，則可以按照糾錯定理，就決定了分組碼的差錯控制能力。例如：碼的，并且從表8-3也可以看出，它可糾1位錯。  伴隨式解碼解碼過程是對經(jīng)過信道傳輸后，受到干擾及信道加性高斯白噪聲影響的數(shù)字信號波形，進行最佳接收及合適的判斷后，再確認它是否在碼字序列中含有錯誤，這種檢測是否能發(fā)現(xiàn)錯誤，發(fā)現(xiàn)什么樣的錯誤，完全取決于差錯控制能力。若在該設計碼的能力范圍內(nèi)，則可立即實施自動糾錯，或者以ARQ方式重發(fā)糾錯，

29、如果由于偶爾傳輸干擾使碼字波形失真太大，在一個接收碼字內(nèi)發(fā)生的錯誤數(shù)超出該碼差控能力，就不能發(fā)現(xiàn)或糾正錯誤，或者以“一誤再誤”反而糾而更錯。從目標而言，應當在碼字確認為正確時方可解碼而準確恢復為原信息。1.        伴隨式解碼上面已經(jīng)涉及到，如果許用碼字，也就是接收碼組序列無錯誤，則它與矩陣運算結果必有反之，則表明收碼有錯為，即（8-51）其中，是含有錯誤的接收碼組。它是由于信道噪聲與干擾導致誤碼結果，其錯誤格式為，因此有（8-52）于是（8-53）可見，接收錯碼序列與矩陣運算由一致監(jiān)督矩陣進行校驗，也就是錯誤格式與的

30、運算結果，由于，所以，我們利用這一檢驗方法至少可以表明是否有錯，茲設符號來代表，即（8-54）這里，將稱為誤差伴隨矢量，簡稱“伴隨式”（Syndrome），詞意是它伴隨誤差而存在，在碼字中的全部錯誤格式為個（個可能碼組格式中，只有一個是不錯的碼字），若計算結果不等于0，則全部錯誤格式的錯碼在解碼之前均可以被發(fā)現(xiàn)。2.        伴隨式特點通過上面分析，伴隨式有以下兩個基本特點：（1）伴隨式僅僅與錯誤格式有關，而與傳輸?shù)拇a字無關。（2）同樣、的碼的不同碼字，都有同樣種全部誤差格式，個。不是一個簡單的數(shù)值，而是位數(shù)等于矩陣列

31、數(shù)，即位的矢量。由于伴隨式包括及兩種類型的可能結果，因此錯碼組與運算時，只要與的某列或（多列）相乘后的個元素模2加等于1，就不為全0，就表明有錯，如上述碼，如果收碼為，則這一結果，即正與矩陣第5列相同，表明收碼中，從高位開始第5個碼元差錯，如果只是有1位錯，則尚可立即糾正為。又如，上述碼，如果收碼，則這里與運算中每列相乘的模2和均為1，其結果，是矩陣第1列（即的第1行），因此首位差錯，糾正為。上面對碼和碼計算的伴隨式結果，均表明它確可以檢出并且可以糾正1位錯，并且與兩碼差控能力（分別為4和3）相符合。同時也驗證了在開始介紹分組碼設計個監(jiān)督元的初衷。下面進一步分析，由于碼的漢明距離，比碼付出的冗

32、余代價大，它能否有更大的差錯控制能力呢？為此，我們從碼（例8-1）矩陣中任意抽出一行，它一定是許用碼字，如，若任意錯2位，如變?yōu)?，即?、2位均錯，我們求其伴隨式。這一結果，接收端并“不知道”是兩位錯，而按常規(guī)運算得到伴隨式，需從矩陣中去找與之相同的列，但此時卻不存在。這表明碼沒有糾兩位錯的能力，但卻檢出為“有錯”，且為2位或更多位錯。此時，可以通過反饋信道，利用ARQ方式重傳糾錯。其實（1001）（1110）（0111）是矩陣的第1、2列的模2和，而計算并得不到是哪兩列之和，因此只能檢錯而無法糾正。這里我們驗證了差錯控制定理差控能力的正確性。從上面計算，我們可以看出碼雖然與碼一樣只能糾1位錯

33、，但碼在可糾1位錯同時，若出現(xiàn)2位或更多個錯，都還有檢錯能力，而通過ARQ仍能糾錯?？梢则炞C，碼卻不能發(fā)現(xiàn)2位錯，如碼的碼字（1000111）錯為（1000001），第5、6位錯，伴隨式可計算為（110），它是矩陣第2列，自然會加以“糾正”為（1100001），反而糾錯，因此碼的碼率為，它符合漢明碼的定義，即碼是后面將介紹的漢明碼，是剛能糾1位錯的高效碼。順便提及，編碼理論表明，具有且的碼，除全0碼外，其余個碼字的重量相等，稱為極長碼，只用作檢錯時，它不可檢錯概率最小，是一個最佳檢錯碼，如（7,3）碼即為此種碼，。同時奇偶校驗與重復碼也是最佳檢錯碼，而碼是等重碼（全0碼外，其余1個碼字全為1）

34、.  漢明碼與對偶碼上面已經(jīng)多次例舉了（7，4）與（7，3）兩個分組碼，下面具體分析一下這兩個碼的不同點與相關性，從而指出漢明碼與對偶碼的特征，這里（7，4）碼為漢明碼的特例，（7，4）與（7，3）碼是對偶碼的一例。  漢明碼通過線性分組碼的編制過程，我們已經(jīng)明確，作為系統(tǒng)碼的結構，是在給定的信息碼之后，按一定規(guī)則加入個監(jiān)督元，此種冗余可以使編碼的碼率為的碼字具有位糾錯能力。現(xiàn)在提出一個問題，若欲使碼糾正1位或位差錯，至少值為多少位（監(jiān)督位），也就是說，按照糾錯定理確保漢明距離，至少為21，那么，上述問題就變?yōu)椋喝粲幹埔粋€指定的下限值，即最小漢明距離剛好確?？杉m位錯，這個

35、碼就是可糾位錯的高效碼漢明碼。1    且碼長（8-57）2信息位  （8-58）如：3，則碼長2317，7323134。所以（7，4）碼是漢明碼，它的伴隨式可能取的不同組合數(shù)為個（且均為3位）是矩陣全部非全0列的數(shù)目漢明碼的哪一位有錯，伴隨式就等于矩陣的相應順序的列。并且矩陣的個列可以任意倒換位置，而不影響糾錯能力，當將矩陣排布為標準形式時，則可以通過相應生成矩陣（也時標準形式）構成系統(tǒng)碼。漢明碼可在相同碼長的碼中，利用較少的監(jiān)督位，即最高碼率，達到同樣的糾錯能力。還可以構成多進制的漢明碼，本章只介紹二元碼。通過漢明碼的特征討論，表明漢明碼就是上面提到

36、的完備碼監(jiān)督元得到最充分的利用，即矩陣（不含全0列）列等于個監(jiān)督元構成的時的情況。  漢明碼的擴展與擴展碼3的漢明碼，即符合結構時，如（7,4）碼，若將它的每個碼字再加進一個對全部碼字都進行監(jiān)督（校驗）的監(jiān)督位，即得（8-59）或  （8-60）稱上式為“全監(jiān)督方程”，此種漢明碼的監(jiān)督位增加為1，而信息位不變，碼長也增加一位，此時漢明碼變?yōu)椋Q為擴展?jié)h明碼。在漢明碼3時，由于必然至少有一個碼字的碼重為3（見表8-？），對該碼字加入，則變?yōu)榕紨?shù)“1”（碼重為4），而原來漢明碼其它碼字碼重為偶數(shù)時則加，碼重不變，因此擴展?jié)h明碼最小碼距由3，變?yōu)?。于是擴展?jié)h明碼的一致監(jiān)督矩陣為

37、   或   表示（7,4）漢明碼擴展后的（8,4）擴展?jié)h明碼一致監(jiān)督矩陣，由前面（7,4）碼矩陣（式8-37）變?yōu)椋?-61）有時將擴展?jié)h明碼稱為漢明增余碼。我們可以將上述漢明碼字加上全監(jiān)督位的方法，再推廣到最小碼距為奇數(shù)的碼，則變?yōu)椋浯a距也加1個，為（1）偶數(shù)，稱此種碼為原碼碼的擴展碼。例如：原碼為（5，2）碼，其與矩陣為：       和      它的碼字（4個）為：（00000）、（01101）、（10111）、（11010），對每個

38、碼字加上一個全校驗位，則按碼重為奇數(shù)的碼字加，偶重碼字加，這4個碼字變?yōu)椋海?00000）、（011011）、（101111）、（110101）對應的及矩陣分別為：         顯然最小漢明距離為4  完備碼（exhaust）上面討論的（7，4）漢明碼，它的矩陣共有列，即等于碼碼長，而且由個監(jiān)督位，且有，此時由個監(jiān)督元的組合，除全0（即000）外，尚有7組全部用于矩陣的列元素組，并且可以證明無論這7組三位碼元在矩陣中如何排序，均會得到正確（7，4）碼，也就是說對應的個監(jiān)督方程組只要3個方程組線性獨立，

39、且均由位信碼任意構成，均符合正確編碼規(guī)則。這種情況正是式（8-55）漢明界不等式中等式成立的情況，即完備碼定義為，（8-63）符號這一關系的參量構成的碼稱為完備碼。顯然由上面關系，（7,4）漢明碼是完備碼，同時由漢明碼的構成特征式（8-57）與（8-58），一切漢明碼都是完備碼，（7,3）碼由于，這就是說，個監(jiān)督元，可有15組非全0的4位碼組，通過設計組監(jiān)督方程構成的矩陣中，只涉及到這15組中的7組（列），至于用哪些組，一定嚴格遵守監(jiān)督方程組設計條件。通過對照完備與不完備碼，我們得到另一個啟示是，當為完備碼時，不用設計監(jiān)督方程后再抽取系數(shù)而得到矩陣，而是隨意將個非全0的位碼組以任何順序放入矩陣

40、即可。  循環(huán)碼循環(huán)碼是線性分組碼中最重要的一個子類碼，它的基本特點是編碼電路及伴隨式解碼電路簡單易行；循環(huán)碼代數(shù)結構具有很多有用的特性，便于找到有效解碼方法。因此在實際差錯控制系統(tǒng)中所使用的線性分組碼，幾乎都是循環(huán)碼。下面將介紹循環(huán)碼的多項式表示及其性質，同時簡介幾種重要的循環(huán)碼，CRC、BCH和R-S碼等。  循環(huán)碼的描述1.        碼多項式及其運算     通式表示為：（8-69）于是稱與為“同余”式，即   &

41、#160;        模（8-70）如： 則     模    即能被整除利用這一運算原理，我們可對一個碼字進行移位表示：如：的多項式表示為： 使碼組向左移2位（循環(huán)）則有對應多項式然后以去除得：這一結果表明，以作除法運算（稱模）后，即 與為同余因此，         （模）應注意，利用這種同余式表示，必須加注（模），否則就不明確在什么條件下得到的這一同余關系式。

42、2.      循環(huán)碼的構成循環(huán)碼的構成突出特點是只要是該碼中的一個許用碼組碼字，通過循環(huán)位其結果則可包括全部個非全0碼字，如上面介紹的（7，3）分組碼，從信碼位0 0 1構成的碼字（0011101）開始逐一向左（或者向右）移一位，可得其余6個碼字：（0111010）、（1110100）、（1101001）、（1010011）、（0100111）、（1001110）。若把這些碼字寫成碼多項式，都具有同一個移位運算模式，并設（0011101）對應的碼多項式    ，于是，有：    &#

43、160;   （模)（8-71）這樣，就構成了（7，3）循環(huán)碼，如表8-4。從表8-4看出，循環(huán)得到的（7，3）碼，仍為系統(tǒng)碼，信息碼組均在表中碼字的高位（左方）。表8-4  （7，3）循環(huán)碼移位（7，3）碼碼多項式（模）00 0 11 1 0 110 1 11 0 1 021 1 10 1 0 031 1 01 0 0 141 0 10 0 1 150 1 00 1 1 161 0 01 1 1 0  循環(huán)碼生成多項式與生成矩陣1.        生成多項式由表8-4構成個

44、非全0碼字多項式的過程與結果看，我們從開始進行逐一循環(huán)，并以模運算，該碼字正是信碼組中最低位為1，對應碼字多項式，在全部非全0碼字中，它的最高位階次也最低，并等于，即最高次項為，隨后一系列碼字都源于它的移位而形成，因此稱其為生成多項式，即（8-72）然后再從的因式分解來進一步分析（8-73）我們可以將三個既約多項式因式任意組合成兩個因式，可有（8-74）如：（8-75）（8-76）其中可以組合為二因式中包含最高次為4次的情況有兩種，即展開式的第4及第5兩組，都可以作為階次最高為4的即（8-77）（8-78）在展開式中選用了其中一個（組合）因式為后，余下一個因式，則稱其為循環(huán)碼的監(jiān)督多項式，如式

45、（8-74）生成多項式與相應監(jiān)督多項式乘積等于多項式。上例二種情況，有   （8-79）（8-80）循環(huán)碼的監(jiān)督多項式，最高階次為，與最高階次之和為碼長，按照上列與的不同分配方案，可以產(chǎn)生具有不同監(jiān)督位數(shù)的（7，）循環(huán)碼，如表8-5示，顯然可由兩種（7，3）碼與（7，4）碼，（7，6）碼是個奇偶校驗碼，（7，1）碼是重復碼，上述表8-4的（7，3）碼采用了。表8-5  的因式分解及6種不同碼順序生成多項式最高階次監(jiān)督多項式碼11（7，6）23（7，5）33（7，4）44（7，3）54（7，3）66（7，1）在中，由于與最高階次之和為，且兩者最高階次分別為與，即（8

46、-81）其中，只有及，這兩個乘積項分別構成中的和1，因此，其余各全部為0，由式（8-81）的展開式中的系數(shù)，構成循環(huán)碼的一致監(jiān)督矩陣。2.        生成矩陣多項式和編碼方法在分組碼中，生成矩陣為陣列，輸入的位信息碼組，可以由矩陣生成全部非0碼字。對于循環(huán)碼，可由 ，共行碼字多項式構成生成矩陣多項式（8-82）于是前面由構成的（7，3）循環(huán)碼生成矩陣為（8-83）相應的系數(shù)表示的生成矩陣為（8-84）可以化為其標準形式為（8-85）再按與的關系，直接寫出標準形式的矩陣（8-86）與分組碼一樣，利用可生成碼字多項

47、式。設信息編碼（位）為則（8-87）由于我們設計循環(huán)碼為系統(tǒng)碼，應當將信碼多項式晉升到從項的最高位開始，即將向左移位，是碼字多項式的最高位開始的前1項，其后應續(xù)排項的監(jiān)督多項式，則該系統(tǒng)碼結構為（8-88）式中為監(jiān)督多項式：（8-89）式（8-88）可寫為（8-90）是碼字多項式，必能為整除，即 或 ，    （模（8-91）     （8-92）即        （8-93）由上面幾個關系式，特別是式（8-93），我們可以得到循環(huán)碼的編碼方法步

48、驟在選定生成多項式之后，按下面步驟構成全部碼字多項式：（1）給出信息碼組后，寫出其多項式為（2）將提升左移位，得；（3）除以生成多項式，求得的余式為；    （4）由式（8-93）可得；  循環(huán)碼、對偶碼與縮短碼1.         對偶碼與前述分組碼具有對偶碼一樣，循環(huán)碼也具有對偶碼關系。上面我們選用構成了（7，3）循環(huán)碼，其監(jiān)督多項式為構成了（7，3）循環(huán)碼，其監(jiān)督多項式為（表8-5）同時，我們也可選用作為生成多項式，同樣構成（7，3）循環(huán)碼，其監(jiān)督多項式為。這

49、兩種（7,3）碼雖構成有所不同，但它們都有同樣的糾錯能力。而且兩者均存在對偶碼，即分別以它們的監(jiān)督多項式及作為生成多項式，可分別構成對偶碼（7,4）碼，即              （8-94）               （8-95）構成它們對偶碼的另一種方法是：由一個循環(huán)碼的監(jiān)督多項式的反項多項式即取的逆序系數(shù)構成多項式作為

50、生成多項式，可以得到碼，與碼互為對偶。如：（7,3）碼，其系數(shù)序列為其反序排列為：對應的對偶監(jiān)督多項式為：（8-96）再以反序多項式作為對偶生成多項式：（8-97）于是由原先的（7,3）碼，變?yōu)榱似鋵ε即a，（7,4）循環(huán)碼，即（7,3）與（7,4）碼互為對偶循環(huán)碼。另外，表8-5中第1欄與第6欄的（7,6）與（7,1）也是對偶碼。2.        縮短循環(huán)碼在實際應用的循環(huán)碼設計中，由于的因子多項式數(shù)目較少，難以達到設計要求的與的多種取值，常常利用碼的縮短碼，如碼縮短為碼，可由上面（7,3）碼為例縮短1位，即1，可得（6,

51、2）縮短碼。具體做法可將式（8-84）矩陣與式（8-79）矩陣進行適當舍去：可只取矩陣中首位含0的行，且將此二行的首位0舍去后，可得（8-98）矩陣舍去最左1列，可得（8-99）該縮短后的（6，2）碼的碼字為：（000000）、（100111）、（011101）和（111010）又如，可以將（7,4）漢明循環(huán)碼縮短為（5,2）碼，（2）。由本章開始時介紹的（7,4）碼的與矩陣為     矩陣縮短2列后得縮短方式只取第3、4行，然后舍去二者前面兩位0，可得于是，縮短后得（5,2）碼碼字為：（00000）、（10101）、（01011）和（11110）

52、60; 循環(huán)碼解碼與伴隨式計算由分組碼的概念，當發(fā)送碼字為，而在高斯噪聲信道中傳輸可能發(fā)生隨機差錯，則收碼為于是通過計算收碼的伴隨式，結果若為全0列則表明無錯，若有1位錯，則必等于與錯位對應的矩陣中的那1列，因此可自動糾錯。對于系統(tǒng)碼形式的循環(huán)碼接收，我們可以很方便地求出收碼多項式的伴隨多項式。設收碼多項式為，利用設計的生成多項式，可有（8-100）式中，除以的商式，若有錯，為未知量，它并不等于碼字的商式。這里，余式多項式的最高階次不超過，這個伴隨多項式應是×1的系數(shù)矩陣構成。1. 伴隨多項式的性質及作用式（8-100）可以再寫為正確碼字與誤差多項式之和，即：（8-101）或

53、0;            （8-102）將式及式（8-87）代入上式，得（8-103）由此看出，也是誤差多項式的伴隨式。所以只要計算出收碼或誤差的伴隨式，也就可以檢測誤差，這是的一個重要特性。第二個特性是，若是收碼多項式的伴隨式，那么移1位后的，即的伴隨式等于移1位，即，由這種循環(huán)特性可得：（8-104）也就是說，是由去除所得的余式，并且上式可推廣為：（8-105）即如果是的伴隨多項式，那么是收碼移位后的移位多項式的伴隨式。第三個特性是對檢、糾錯更為有用的特點：如果誤差發(fā)生在監(jiān)督位中

54、任一項，則其誤差多項式與伴隨式相同。這就是說，如果由收碼求出的，其最高次冪不超過，則可以輕易求得，而即可糾錯2.        利用伴隨式糾錯分析下面，利用以上三個特點，來處理可能含有差錯得接收碼。設表8-4中（7,3）循環(huán)碼的一個碼字（0111010），其碼字多項式為設在監(jiān)督項中發(fā)生錯誤，如項，收碼則為收碼處理如下即  這里，   其中階次3小于734，因此有于是立即可以糾錯，正確碼字應為即  現(xiàn)在再來試分析，如果中后二項均發(fā)生錯誤，即，試求伴隨式即有   其中

55、，   可糾錯后由此結果，居然可以發(fā)現(xiàn)2位錯，且可糾正同樣若后三項均錯，照樣求得，也可以糾錯。上述情況表明，只要錯誤發(fā)生在監(jiān)督多項式的各項，均可以以直接糾錯，這一點顯然與相對應的（7，3）分組碼，因4，只能糾任何碼元的1位錯與檢出2位錯，有所不同。  卷積碼  卷積碼概念前面介紹的線性分組碼的基本特征是以位信息碼組，按監(jiān)督規(guī)則構成個監(jiān)督位，監(jiān)督位只與本碼組信息位（位）有關，亦即它們只監(jiān)督本碼組的碼字，因此碼是各長度為的碼字獨立生成并獨立檢、糾差錯，它更適于以分組包進行數(shù)據(jù)通信的檢錯及反饋重發(fā)糾錯。現(xiàn)在討論與分組碼機制不同的另一類糾錯碼卷積碼（Convol

56、utional Code），我們以表示其碼長和信息位數(shù)。卷積碼顯著特征是，信息位不以分組（位）進入編碼器緩存而形成它們的監(jiān)督之后再輸出，而是以很短的信息碼段位（甚至1、2位）連續(xù)進入編碼器，每個信息段形成的監(jiān)督位不但與本段有關，而且與它之前的（）個信息段有關，因此監(jiān)督元對包括個信息段在內(nèi)的段信息具有相關性，即具有段監(jiān)督作用，每段編碼為長度的子碼。我們把稱為卷積碼約束長度（constraint length），稱為“約束度”。為了闡明卷積碼基本原理，茲給出一個簡單的編碼器的工作過程，如圖8-12所示。電路由2個移位寄存器（）與一個模2加法器構成。輸入信息可以緩存并直接輸出。若電路推動節(jié)拍與信息比

57、特流同步，門電路按上下半拍輪流接向信息位和監(jiān)督位，則輸出編碼序列為。  圖8-12  (2,1,2)卷積碼編碼器如信息序列=（101101001），茲設信息段為最小段，即，由此設計電路（圖8-12所示），按電路工作狀態(tài)變化，監(jiān)督元在每位信息比特之后穿插的輸出監(jiān)督序列為（111011101），于是編碼輸出為（11,01,11,10,01,11,01,00,11），結果為系統(tǒng)碼形式。其實在本例中，每位監(jiān)督元都是本位與其前一位信息位之和，即（8-113）輸出的編碼是每位信息位之后有一個監(jiān)督位，約束長度是相鄰兩個碼段，即，記作（）（2,1,2）卷積碼。然后考慮在接收端如何

58、解碼與糾錯。根據(jù)編碼的過程與規(guī)則，應當找出接收信息位的伴隨式：由于發(fā)送時每個監(jiān)督元是的結果，我們?nèi)绻麑⒔邮盏摹氨O(jiān)督元”與接收中重新計算的“監(jiān)督元”進行模2加，結果若為“0”則無錯，若為“1”則在此位發(fā)生了差錯。各伴隨式可表示為（8-114）由上列伴隨式看出，每位信息均包含在兩個相鄰伴隨式中，如同時與和兩個方程有關，與和有關。但每相鄰兩個伴隨式均與5個碼元有關（如：、與、有關）。反之，這5個碼元中，與兩個伴隨式都有關系的只有1個信息位，如只有與、兩者都有關，其余碼元只與1個或者有關。這時稱伴隨式方程、正交于，或者稱、方程構成的正交方程組。然后回到式（8-113），若只是簡單地按是否等于0來判決與

59、糾錯是不能完全奏效的，由上述正交性關系，當差錯不超過1位時，接收判決規(guī)則為：（1）當及兩方程均等于“0”時，解碼的伴隨式（8-113）與編碼方程式一致，判為無錯。（2）當與均等于“1”時，一定是有錯，并立即糾正。（3）當與中只有一個為“1”時，只可能是、中之一有錯，而不可能錯。結論對于（2,1,2）卷積碼，在只可能發(fā)生1個傳輸錯誤時，其判決規(guī)則為只有當      則判（8-115）根據(jù)上述解碼與判決過程，可以設計出（2,1,2）卷積碼的解碼器電路，如圖8-13示，門電路的作用以及、移存器，模2加法器1的作用均與編碼器相類比，而模2加法器2則完成式（8-114）產(chǎn)生解碼伴隨式，其輸出與移存器3的1位延遲輸入到“與門”完成判決作用，最后模2加法器3完成糾錯輸出功能。 圖8-13  （2,1,2）卷積碼解碼電路由解碼電路及解碼過程可知，解碼正交方程組