第七章 分組碼和卷積信道碼

第七章分組碼和卷積信道碼第1頁，共116頁，2023年，2月20日，星期三本章的主要內(nèi)容6.1線性分組碼6.2卷積碼6.3帶限信道的編碼調(diào)制——網(wǎng)格編碼調(diào)制2第2頁，共116頁，2023年，2月20日，星期三本章的主要內(nèi)容6.1線性分組碼6.2卷積碼6.3帶限信道的編碼調(diào)制——網(wǎng)格編碼調(diào)制3第3頁，共116頁，2023年，2月20日，星期三線性分組碼線性分組碼的描述生成矩陣和奇偶校驗矩陣一些特殊的線性分組碼循環(huán)碼線性分組碼的最佳軟、硬判決譯碼線性分組碼的最小距離的邊界非二進制分組碼和級聯(lián)分組碼突發(fā)差錯信道中編碼數(shù)據(jù)的交織串行與并行級聯(lián)分組碼4第4頁，共116頁，2023年，2月20日，星期三線性分組碼線性分組碼的描述生成矩陣和奇偶校驗矩陣一些特殊的線性分組碼循環(huán)碼線性分組碼的最佳軟、硬判決譯碼線性分組碼的最小距離的邊界非二進制分組碼和級聯(lián)分組碼突發(fā)差錯信道中編碼數(shù)據(jù)的交織串行與并行級聯(lián)分組碼5第5頁，共116頁，2023年，2月20日，星期三線性分組碼的描述分組碼： 分組碼由一組固定長度稱為碼字的矢量構(gòu)成。碼字的長度是矢量元素的個數(shù)，用n表示。碼字的元素選自由q個元素組成的字符集。字符集由0，1兩個元素組成時，該碼就是二進制碼。長度為n的二進制分組碼可能有種可能的碼字。從這種碼字中可以選擇個碼字（k<n）組成一種碼。這樣一個k比特信息的分組可以映射到長度為n的一個碼字，這樣得到的分組碼稱為（n,k）碼，定義k/n≡為碼率。碼字的重量：既該碼字包含的非零元素的個數(shù)。編碼中所有碼字重量的集合形成該碼的重量分布。如果全部M個碼字都具有相同的重量，這種碼叫做固定重量碼或者恒重碼。

6第6頁，共116頁，2023年，2月20日，星期三線性分組碼的描述分組碼編、解碼的功能體現(xiàn)為對碼字實行乘、加算數(shù)運算，算數(shù)運算的規(guī)則服從元素所在字符集代數(shù)域的慣例。碼是由有限個元素的域構(gòu)成的。具有q個元素的有限域通常稱為伽羅華域，用GF(q)表示。一般的，若q是素數(shù)，可構(gòu)成一個由元素{0，1，…q-1}組成的q元域GF(q)。在域中的加、乘運算定義為模q運算，寫做（modq）。通常，有限域只有當q是素數(shù)或者是素數(shù)的冪時才能構(gòu)成。當q是素數(shù)時，乘法和加法基于模q運算。如果（p是素數(shù)，m是任意正整數(shù)），有可能將GF(q)域擴展成GF（）7第7頁，共116頁，2023年，2月20日，星期三線性分組碼線性分組碼的描述生成矩陣和奇偶校驗矩陣一些特殊的線性分組碼循環(huán)碼線性分組碼的最佳軟、硬判決譯碼線性分組碼的最小距離的邊界非二進制分組碼和級聯(lián)分組碼突發(fā)差錯信道中編碼數(shù)據(jù)的交織串行與并行級聯(lián)分組碼8第8頁，共116頁，2023年，2月20日，星期三生成矩陣和奇偶校驗矩陣設是編進碼字里的k個信息比特。輸入編輯器的k位信息可寫做編碼器輸出矢量記為編碼運算可以用一組n個方程表示如下

9第9頁，共116頁，2023年，2月20日，星期三生成矩陣和奇偶校驗矩陣線性方程組可以用矩陣的形式表示如下式中G稱為該碼的生成矩陣10第10頁，共116頁，2023年，2月20日，星期三生成矩陣和奇偶校驗矩陣任何碼字都是G的矢量的線性組合，即生成矩陣G的行矢量必須是線性無關(guān)的，即它們必須擴張成整個k維子空間。子空間是k維的，因而G的秩是k。（n,k）碼的任何生成矩陣都可以通過行運算（以及列置換）簡華成系統(tǒng)形式：

11第11頁，共116頁，2023年，2月20日，星期三生成矩陣和奇偶校驗矩陣如果生成的矩陣產(chǎn)生的（n,k）碼不具備上式所示的系統(tǒng)形式，則該碼叫做非系統(tǒng)碼。如果一個矩陣能通過行運算和列置換得到另一個矩陣，這兩個矩陣稱為等效的，非系統(tǒng)形式的生成矩陣可以和另一個系統(tǒng)形式的生成矩陣等效。由兩個等效的生成矩陣生成的兩個（n,k）線性碼也是等效的，可以通過置換各碼字的位置，從一個碼得到另一個碼。每個（n,k）線性碼可以和一個系統(tǒng)的（n,k）線性碼等效。任何一個（n,k）線性碼都有一個n-k維對偶碼與之關(guān)聯(lián)。對偶碼是一種（n,n-k）線性碼。對偶碼的生成矩陣用H表示，是由零空間中n-k個線性無關(guān)的碼矢量組成的。

12第12頁，共116頁，2023年，2月20日，星期三生成矩陣和奇偶校驗矩陣（n,k）碼的任意一個碼字均正交于其對偶碼的任意一個碼字，因此（n,k）碼的任意一個碼字均正交于矩陣H的每一行，即：式中，0代表由n-k個元素組成的全零行矢量，是（n,k）碼的一個碼字。于是假定（n,k）線性碼是系統(tǒng)碼，其生成矩陣G可化為系統(tǒng)形式，因此必有

13第13頁，共116頁，2023年，2月20日，星期三生成矩陣和奇偶校驗矩陣H的列矢量線性相關(guān)。如果用代表（n,k）線性碼中重量最小的碼字，由于最小重量等于最小距離，可以斷言H的個列一定是線性相關(guān)的，則對于最小距離為的二進制（n,k）線性碼，可給每個碼字添加一位奇偶校驗而構(gòu)成一個二進制（n+1,k）線性碼。這個附加的校驗位通常用來對碼字的所以比特進行校驗。

14第14頁，共116頁，2023年，2月20日，星期三生成矩陣和奇偶校驗矩陣這種（n+1,k）碼叫做擴展碼，其校驗矩陣是：式中，H是原碼的校驗矩陣。15第15頁，共116頁，2023年，2月20日，星期三線性分組碼線性分組碼的描述生成矩陣和奇偶校驗矩陣一些特殊的線性分組碼循環(huán)碼線性分組碼的最佳軟、硬判決譯碼線性分組碼的最小距離的邊界非二進制分組碼和級聯(lián)分組碼突發(fā)差錯信道中編碼數(shù)據(jù)的交織串行與并行級聯(lián)分組碼16第16頁，共116頁，2023年，2月20日，星期三一些特殊的線性分組碼漢明碼漢明碼具有的共同特性是其中，m是任意正整數(shù)。例如m=3時，有（7，4）漢明碼。漢明碼的校驗矩陣H具有特殊的性質(zhì)，H中沒有哪兩個列是線性相關(guān)，除非這兩個列相等。在m＞1時，有可能找到H的3個列，它們之和為零矢量。有此可得（n,k）漢明碼的。如果給(n,k)漢明碼添加一位奇偶校驗位，得到一個的（n+1,k）擴展?jié)h明碼。反之，在生成矩陣G中刪除l行，或等效地在校驗矩陣H中刪除l列，漢明碼可以縮短為（n-l,k-l）碼。（n,k）漢明碼的重量分布是已知的，可以用一種緊湊的形式即重量估計算式表示它：17第17頁，共116頁，2023年，2月20日，星期三一些特殊的線性分組碼這里是重量為i的碼字的數(shù)目。哈達碼（Hadamard）碼哈達碼是選取哈達碼矩陣的行作為碼字而得到的碼。哈達碼矩陣是一個由“0”和“1”構(gòu)成的n*n維矩陣（n是偶數(shù))。18第18頁，共116頁，2023年，2月20日，星期三一些特殊的線性分組碼哈達碼矩陣的特性：拿出它的任意兩行相比較，都一點不差地在n/2個位置上取不同值；矩陣中有一行是全0行，其他行都包含n/2個“0”和n/2個“1”。當n=2時，哈達碼矩陣為進一步按照下述規(guī)律可以由產(chǎn)生哈達碼矩陣

19第19頁，共116頁，2023年，2月20日，星期三一些特殊的線性分組碼反復使用上式可以生成分組長度，的哈達碼（m是正整數(shù)）。高萊（Golay）碼高萊碼是二進制（23，12）線性碼。其最小距離。在（23，12）碼上添加一位奇偶位即可得二進制線性（24，12）擴展高萊碼，其最小距離。

20第20頁，共116頁，2023年，2月20日，星期三線性分組碼線性分組碼的描述生成矩陣和奇偶校驗矩陣一些特殊的線性分組碼循環(huán)碼線性分組碼的最佳軟、硬判決譯碼線性分組碼的最小距離的邊界非二進制分組碼和級聯(lián)分組碼突發(fā)差錯信道中編碼數(shù)據(jù)的交織串行與并行級聯(lián)分組碼21第21頁，共116頁，2023年，2月20日，星期三循環(huán)碼循環(huán)碼的概念：循環(huán)碼是線性碼的一個子集，它滿足下列循環(huán)移位特性：如果是某個循環(huán)碼的碼字，那么由C的元素循環(huán)移位得到的也是該循環(huán)碼的一個碼字，即碼字C的所有循環(huán)移位都是碼字。循環(huán)碼的性質(zhì)將其碼字與一個不大于n-1次的多項式C（p）聯(lián)系起來，該多項式定義為兩邊同乘以p,得多項式

22第22頁，共116頁，2023年，2月20日，星期三循環(huán)碼再將pC(p)除以可得：這里該多項式代表碼字，正是由原碼字C循環(huán)移位得到的。因此：C(p)代表循環(huán)碼的一個碼字。23第23頁，共116頁，2023年，2月20日，星期三循環(huán)碼那么也一定是該循環(huán)碼的一個碼字，于是：式中，剩余多項式代表循環(huán)碼的一個碼字，Q（p）是商。可以用一個n-k次的生成多項式g（p）產(chǎn)生一個循環(huán)碼。（n,k）循環(huán)碼的生成多項式一定是多項式的因子，其通式為定義消息多項式X（p）如下這里的代表k位比特信息。X（p）g(p)的乘積代表一碼字。24第24頁，共116頁，2023年，2月20日，星期三循環(huán)碼把這些碼字寫成對C（p）循環(huán)移位產(chǎn)生則可以表示為25第25頁，共116頁，2023年，2月20日，星期三線性分組碼線性分組碼的描述生成矩陣和奇偶校驗矩陣一些特殊的線性分組碼循環(huán)碼線性分組碼的最佳軟、硬判決譯碼線性分組碼的最小距離的邊界非二進制分組碼和級聯(lián)分組碼突發(fā)差錯信道中編碼數(shù)據(jù)的交織串行與并行級聯(lián)分組碼26第26頁，共116頁，2023年，2月20日，星期三線性分組碼的最佳軟判決譯碼本節(jié)推導在AWGN信道上接收機使用最佳（非量化）軟判決譯碼時，二進制線性分組碼的性能。假定各個碼字等概率發(fā)生，具有相同的先驗概率。令表示發(fā)送任一指定碼字后匹配濾波器的n個輸出取樣。信號是用相干二進制PSK傳輸?shù)?。當碼字的第j比特是1時，表示為當碼字的第j比特是0時，表示為變量表示取樣瞬間的加性高斯白噪聲。根據(jù)已知的M種可能發(fā)送的碼字和接收到的值，最佳譯碼器形成M個相關(guān)度。式中，表示第i個碼字第j個位置上的比特。27第27頁，共116頁，2023年，2月20日，星期三線性分組碼的最佳最佳軟判決譯碼和其余M-1個碼字之間的互相關(guān)系數(shù)為式中，表示第m個碼字的重量。的概率是因此

28第28頁，共116頁，2023年，2月20日，星期三線性分組碼的最佳軟判決譯碼利用該式求二進制差錯事件總和，可得一個碼字平均差錯概率的邊界為由于可求得松散的邊界為29第29頁，共116頁，2023年，2月20日，星期三線性分組碼的最佳軟判決譯碼一對編碼波形之間的最大互相關(guān)系數(shù)為在的假定下得到的差錯概率只是上界。所以，上述的給出的性能邊界也同樣適合用QPSK傳輸碼字的一對比特的情況，因為QPSK可以等效地看做是兩個以正交相位獨立傳輸?shù)亩M制PSK在加性高斯白噪聲信道中用二進制正交FSK傳送碼字的每個比特，最佳接收機可用兩個匹配濾波器實現(xiàn)。再接一個譯碼器，用來計算與M個可能的發(fā)送波形相對應的M個相關(guān)度。30第30頁，共116頁，2023年，2月20日，星期三線性分組碼的最佳軟判決譯碼令和表示輸入到組合器的抽樣值，譯碼器得到的相關(guān)度式中代表第i個碼字的第j個比特。與的最大值相對應的碼字挑選出來作為對發(fā)送碼字的判決結(jié)果。若二進制PSK波形是相干檢測，假設發(fā)送的是全零碼字，那么這里是互相統(tǒng)計獨立的高斯隨機變量，均值為0，方差為。由于是互相有關(guān)聯(lián)的，再次使用聯(lián)合邊界。相關(guān)系數(shù)是

31第31頁，共116頁，2023年，2月20日，星期三線性分組碼的最佳軟判決譯碼

的概率是 可以看出，如果達到同樣的性能，相干PSK對信噪比要求小3dB。如假定發(fā)送的是全零碼字，送到譯碼器的輸入變量將是相關(guān)度為

因此，可表達為

32第32頁，共116頁，2023年，2月20日，星期三線性分組碼的最佳軟判決譯碼和的差是在和間判決時，差錯概率的表達式是式中，定義

33第33頁，共116頁，2023年，2月20日，星期三線性分組碼的最佳軟判決譯碼換一種方法，用最小距離，而不用重量分布求一個較寬松的上邊界二進制的差錯概率是因此

34第34頁，共116頁，2023年，2月20日，星期三線性分組碼的最佳軟判決譯碼碼字差錯概率的聯(lián)合邊界是在信息速率為R=秒的情況下，用來發(fā)送k個信息比特和n-k個冗余（校驗）比特（共n比特）的時間是,所以因此編碼波形的帶寬擴展系數(shù)為

35第35頁，共116頁，2023年，2月20日，星期三線性分組碼的最佳軟判決譯碼不管什么情況，將隨編碼效率的減小而增加，或者等效的說，隨分組長度n的增加而線性增大。在高信噪比情況下，如果,在此條件下，正交信號的帶寬擴展系數(shù)為和之比為該比值可用來衡量正交傳輸波形和相干PSK編碼傳輸波形的相對帶寬。36第36頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼本節(jié)只考慮把與碼字單個比特對應的每個樣值量化成0、1兩個電平的極端情況，即不管發(fā)送的碼字比特是0還是1，都實行硬判決。這樣處理后得到的離散時間信道（由調(diào)制器、AWGN信道及解調(diào)器組成）構(gòu)成一個交叉概率為P的二進制對稱信道（BSC）。如果用相干PSK信號發(fā)送和接收碼字比特，有如果用FSK信號發(fā)送每個碼字比特并用相干檢測，那么37第37頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼用非相干檢測時最小距離（最大似然）譯碼：一種有效的硬判決譯碼方法是使用校驗矩陣H。為了方便研究，假定是發(fā)送碼字，Y是解調(diào)器輸出的接收碼字，一般地，Y可以表示為這里，e代表一個任意的二進制差錯矢量的乘積為其中，（n-k）維矢量S叫做差錯圖案的伴隨式。換言之，當所有一致校驗方程都滿足時，矢量S的所有元素為零；并非所有的一致方程都滿足時，矢量S一定含有非零元素，即S包含在一致校驗中失敗的圖案38第38頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼如果構(gòu)造一個譯碼表，其中第一行列出所有個可能的碼字，而以全0碼字作為開頭放在該行的第一列（最左一列）。這個全0碼字同時代表了全0差錯圖案。在第一列接下去的行填上所有n-1個重量為1的差錯圖案。如果，再列出全部2個差錯的圖案，然后是3個差錯圖案，依次類推，直到填滿第一列的全部項。這樣，表的行數(shù)是，等于伴隨式的數(shù)目。下一步，把第一列的每個差錯圖案加到對應的碼字上，就把表的其余項都填滿了，如下圖所示39第39頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼這個表稱為標準陣列，它的每一行，包括第一行，含有個可能的接收碼字?？赡艿慕邮沾a字是由第一行的碼字和第一列對應的差錯圖案造成的。每一行稱為一個陪集。陪集的第一個（最左）接收碼字叫陪集首（或叫差錯圖案）。因此，陪集是由同一個特定差錯圖案（陪集首）導致的所有可能的接收碼字。循環(huán)碼的伴隨式譯碼：考慮一個系統(tǒng)的循環(huán)碼，用多項式表示碼字Y。一般地，，這里的C是發(fā)送的碼字，e是差錯矢量。于是假如用Y（p）除以生成多項式g(p),得

40第40頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼器

相當于所得余式R（p）是次數(shù)小于等于n-k-1的多項式。由上述式子綜合可得因此式中，S（p）是次數(shù)小于等于n-k-1的伴隨式多項式。如果g(p)能整除Y（p）,則S（p）=0，譯碼碼字就是。Y（p）與g(p)的除法可以用一個移位器實現(xiàn)。41第41頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼檢錯和糾錯能力當伴隨式為全0時，接收碼字是個可能發(fā)送的碼字之一。因為一對碼字間最小的分隔距離是，重量為的差錯圖案有可能把碼字集中個碼字之一轉(zhuǎn)變?yōu)榱硪粋€碼字。如果發(fā)生，就產(chǎn)生了一個不可檢的差錯。另一方面，如果差錯數(shù)小于，伴隨式即為非零重量。如果發(fā)生，說明已檢測出信道的一個或多個差錯。（n,k）分組碼有能力檢測出個差錯。差錯檢錯和反饋重發(fā)結(jié)合使用，讓發(fā)錯了的碼重發(fā)。最小距離為的（n,k）分組碼有能力糾正個差錯。一般地，一個最小距離為的碼能檢個差錯，糾個差錯，這里42第42頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼糾錯以后的差錯概率任何一個差錯數(shù)高達的碼字都是可糾正的。由于二進制對稱信道是無記憶的，比特差錯獨立地發(fā)生，在n比特碼塊中出現(xiàn)m個差錯的概率就是因此，碼字差錯概率上邊界的表達式為僅當線性分組碼是完備碼時，上式等號成立。43第43頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼一個糾t差錯的碼必然滿足不等式即完備碼的特性：圍繞個可能發(fā)送碼字、漢明距離為 的所有球都是不相交的，每一個接收碼字都落在這些球的某一個中。因此對于上式，每個接收碼字離開可能發(fā)送碼字的距離至多為t，這時式子取等號。對于這種碼，所有重量小于或者等于t的差錯圖案都能能用最佳（最小距離）譯碼器得到糾正。另一方面，任何重量等于或大于t+1的差錯圖案都不能糾正。所以上式給出的差錯概率可以取等號。44第44頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼差錯概率的下邊界是如果把這些球外的碼字等分成個集合，每一集合對應到個球之一，則每個球由于加上如下數(shù)量的碼字而擴大了：準完備碼的譯碼器差錯概率可以表示為45第45頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼上邊界和下邊界為由契爾諾夫邊界求得譯碼差錯概率的上邊界為46第46頁，共116頁，2023年，2月20日，星期三線性分組碼的硬判決譯碼綜合這些二進制判決可得到聯(lián)合上邊界如用替代重量分布，得到更簡單的形式為47第47頁，共116頁，2023年，2月20日，星期三線性分組碼線性分組碼的描述生成矩陣和奇偶校驗矩陣一些特殊的線性分組碼循環(huán)碼線性分組碼的最佳軟、硬判決譯碼線性分組碼的最小距離的邊界非二進制分組碼和級聯(lián)分組碼突發(fā)差錯信道中編碼數(shù)據(jù)的交織串行與并行級聯(lián)分組碼48第48頁，共116頁，2023年，2月20日，星期三線性分組碼最小距離的邊界一個（n,k）線性分組碼最小距離的上邊界，即

。用分組長度n可將此式歸一化，即式中，是碼率，當n很大時，因子可以忽略。最小距離的上邊界，即漢明界為令，可以得到該式的漸進形式?？梢宰C明當時，任何（n,k）分組碼之比決不會超過這里，滿足等式式中，H（x）是二進制熵函數(shù)。

49第49頁，共116頁，2023年，2月20日，星期三線性分組碼最小距離的邊界將漢明界推廣到非二進制碼，即另一個最小距離上邊界是普洛特金1960年推出的，說明如下：在一個（n,k）線性分組碼中，為了達到最小距離所的校驗位數(shù)目必須滿足不等式

50第50頁，共116頁，2023年，2月20日，星期三線性分組碼最小距離的邊界其中q是字符集大小。對二進制編碼來說，該式可以表示成

在而的極限情況下，式子可以簡化成以漸近線形式表示為

51第51頁，共116頁，2023年，2月20日，星期三線性分組碼最小距離的邊界式中參數(shù)A與碼率有關(guān)，兩者之間的關(guān)系式為（n,k）分組碼最小距離的下邊界同樣存在，特別是具有歸一化最小距離的二進制分組碼，它們漸進地滿足不等式式中，α通過下列等式與碼率建立聯(lián)系這個下邊界是吉爾伯特和烏沙莫夫提出的下邊界的一個特例，適用于非二進和二進制分組碼。52第52頁，共116頁，2023年，2月20日，星期三線性分組碼線性分組碼的描述生成矩陣和奇偶校驗矩陣一些特殊的線性分組碼循環(huán)碼線性分組碼的最佳軟、硬判決譯碼線性分組碼的最小距離的邊界非二進制分組碼和級聯(lián)分組碼突發(fā)差錯信道中編碼數(shù)據(jù)的交織串行與并行級聯(lián)分組碼53第53頁，共116頁，2023年，2月20日，星期三非二進制分組碼和級聯(lián)分組碼非二進制分組碼非二進制分組碼是由一組固定長度的碼字構(gòu)成，碼長用N表示，信息符號長度用K表示，每K個信息符號編成N符號長的一個分組。非二進制碼的最小距離用表示。一個系統(tǒng)的（N,K）分組碼由K個信息符號加上N-K個一致校驗符號組成。各種類型的非二進制線性分組碼中，最重要的實用型編碼是里德-所羅門碼（簡稱RS碼）。這種碼是BCH碼的一個子類，BCH碼又是循環(huán)碼的子類。參數(shù)可以表示為54第54頁，共116頁，2023年，2月20日，星期三非二進制分組碼和級聯(lián)分組碼這種碼可確保糾正t個符號差錯，其中RS碼的重量分布已知。在碼重多項式中各項的系數(shù)是式中及。RS碼之所以重要，原因之一是該碼的距離特性好，其次是因為存在一種有效的硬判決譯碼算法，使得在許多需要長碼的應用場合，該碼能夠被實現(xiàn)。信號在AWGN信道傳輸時劣化，接收這種信號的最佳解調(diào)器由M個匹配濾波器（或互相關(guān)器組成）。匹配濾波器的輸出以軟判決或硬判決形式送到譯碼器。55第55頁，共116頁，2023年，2月20日，星期三非二進制分組碼和級聯(lián)分組碼調(diào)制器、AWGN信道和解調(diào)器構(gòu)成了一個等效的離散（M進制）輸入、離散（M進制）輸出的對稱無記憶信道，其特性可以用轉(zhuǎn)移概率和描述。這種模型是二進制對稱信道(BSC)模型的推廣。硬判決譯碼器的性能可用下述碼字差錯概率上邊界表示式中，t是確保該碼能糾正的差錯的個數(shù)。在碼字產(chǎn)生差錯時，對應的符號差錯概率是56第56頁，共116頁，2023年，2月20日，星期三非二進制分組碼和級聯(lián)分組碼如果將符號轉(zhuǎn)換成二進制數(shù)字，對應的比特差錯概率為級聯(lián)分組碼級聯(lián)碼是由兩個獨立的碼結(jié)合而成的一種較長的碼。通常，其中一個選用非二進制碼，另一個選用二進制碼。兩個碼的級聯(lián)如圖所示

57第57頁，共116頁，2023年，2月20日，星期三非二進制分組碼和級聯(lián)分組碼非二進制碼（N,K）碼作為外碼，二進制碼作為內(nèi)碼。將kN個信息比特組成的一個數(shù)據(jù)塊分割成K組，每組k比特，稱之為一個符號。級聯(lián)碼的最小距離為，其中是外碼的最小距離，是內(nèi)碼的最小距離。此外，級聯(lián)碼的碼率是，等于兩個碼率相乘。 級聯(lián)碼采用硬判決譯碼很方便，只需分解為一個內(nèi)譯碼器和一個外譯碼器即可。級聯(lián)碼也可用軟判決譯碼，當外碼和內(nèi)碼都采用軟判決譯碼時，性能有可能顯著增益，這也證實了增加譯碼復雜度的合理性。58第58頁，共116頁，2023年，2月20日，星期三線性分組碼線性分組碼的描述生成矩陣和奇偶校驗矩陣一些特殊的線性分組碼循環(huán)碼線性分組碼的最佳軟、硬判決譯碼線性分組碼的最小距離的邊界非二進制分組碼和級聯(lián)分組碼突發(fā)差錯信道中編碼數(shù)據(jù)的交織串行與并行級聯(lián)分組碼59第59頁，共116頁，2023年，2月20日，星期三突發(fā)差錯信道中編碼數(shù)據(jù)的交織一個長度為b的突發(fā)差錯定義為有b比特差錯的序列該序列的第一位和最后一位是“1”。碼的糾突發(fā)差錯能力定義為比最短的不可糾突發(fā)差錯的長度少1。不難看出，有n-k校驗位的（n,k）系統(tǒng)碼能夠糾正長度為的突發(fā)差錯。處理突發(fā)差錯信道的一個有效的辦法是對編碼數(shù)據(jù)實行交織，把突發(fā)差錯信道轉(zhuǎn)變?yōu)榻y(tǒng)計獨立差錯的信道。采用交織技術(shù)的系統(tǒng)框圖為60第60頁，共116頁，2023年，2月20日，星期三線性分組碼線性分組碼的描述生成矩陣和奇偶校驗矩陣一些特殊的線性分組碼循環(huán)碼線性分組碼的最佳軟、硬判決譯碼線性分組碼的最小距離的邊界非二進制分組碼和級聯(lián)分組碼突發(fā)差錯信道中編碼數(shù)據(jù)的交織串行與并行級聯(lián)分組碼61第61頁，共116頁，2023年，2月20日，星期三串行與并行級聯(lián)分組碼交織器和級聯(lián)碼結(jié)合可構(gòu)成碼字非常長的編碼。在串行級聯(lián)分組碼（SCBC）中，交織器插在兩個編碼器之間。如圖所示：編碼和交織的具體過程為mk位信息比特經(jīng)外編碼器變?yōu)镹=mp位編碼比特，這些編碼比特進入交織器，按交織器的置換算法以不同的順序讀出。交織器輸出的mp編碼比特然后分隔成長度p的分組送入內(nèi)編碼器，這樣mk位信息比特被SCBC編成了mn的碼塊。最終碼率是內(nèi)、外編碼器碼率的乘積。利用交織，可用類似的辦法構(gòu)成并行級聯(lián)分組碼（PCBC）。62第62頁，共116頁，2023年，2月20日，星期三本章的主要內(nèi)容6.1線性分組碼6.2卷積碼6.3帶限信道的編碼調(diào)制——網(wǎng)格編碼調(diào)制63第63頁，共116頁，2023年，2月20日，星期三本章的主要內(nèi)容6.1線性分組碼6.2卷積碼6.3帶限信道的編碼調(diào)制——網(wǎng)格編碼調(diào)制64第64頁，共116頁，2023年，2月20日，星期三卷積碼卷積碼的描述卷積碼的譯碼卷積碼譯碼的差錯概率刪余卷積碼并行級聯(lián)卷積碼65第65頁，共116頁，2023年，2月20日，星期三卷積碼的描述卷積碼的概念：將發(fā)送的信息序列通過一個線性的、有狀態(tài)的移位寄存器而產(chǎn)生的碼卷積碼編碼器由K級（每級k比特）移位寄存器和n個線性代數(shù)函數(shù)生成器構(gòu)成輸入：k比特二進制信息沿移存器每次移動k比特輸出：n比特二進制信息碼率：Rc=k/n對于這樣的卷積碼記作[n,k,K]66第66頁，共116頁，2023年，2月20日，星期三卷積碼原理圖卷積碼編碼器原理圖：卷積碼編碼器67第67頁，共116頁，2023年，2月20日，星期三卷積碼原理圖卷積碼編碼器由時序邏輯電路組成，所以時序邏輯電路的描述方法在此適用：樹圖、網(wǎng)格圖、狀態(tài)圖、轉(zhuǎn)移函數(shù)等例：n=3，k=1，K=3的卷積碼編碼器原理圖基本生成矩陣生成矢量輸入＋＋123輸出68第68頁，共116頁，2023年，2月20日，星期三卷積碼樹圖樹圖每個比特所對應的3個比特的輸出序列取決于：輸入比特和移位寄存器中的4種可能的狀態(tài)：a=00b=01c=10d=11碼率為1|3K=3卷積碼樹圖69第69頁，共116頁，2023年，2月20日，星期三卷積碼網(wǎng)格圖abcd000000000000000101101101111111111111111001001001001110110110110011011011100100100aa0ba0cb0db0ac1ba1cd1dd1碼率1/3，K=3卷積碼的網(wǎng)格圖網(wǎng)格圖01001001070第70頁，共116頁，2023年，2月20日，星期三卷積碼狀態(tài)圖狀態(tài)b01狀態(tài)c10狀態(tài)c11狀態(tài)a00100001010011111110000101碼率1/3，K=3卷積碼的狀態(tài)圖狀態(tài)圖71第71頁，共116頁，2023年，2月20日，星期三b卷積碼轉(zhuǎn)移函數(shù)acdeD3DDD2D2轉(zhuǎn)移函數(shù)由于卷積碼的線性，所以樹圖中截止到某級長度的所有碼字序列與全零碼字序列的漢明距離的集合，同所有碼字序列與其他任何一個碼字序列的距離集合相同。假設輸入到編碼器的是全零碼字序列。下圖是經(jīng)過處理的狀態(tài)圖，D的指數(shù)：該分支輸出比特序列與全零分支輸出比特序列（000）的漢明距。D2經(jīng)過處理后的狀態(tài)圖72第72頁，共116頁，2023年，2月20日，星期三卷積碼狀態(tài)方程狀態(tài)方程：定義轉(zhuǎn)移函數(shù)： ，可得：其中，ad定義為：轉(zhuǎn)移函數(shù)第一項表明：存在1條d=6的路徑，該路徑從全零路徑分叉出去后又在某個定節(jié)點與全零路徑匯合。（見網(wǎng)格圖，可知該路徑為acbe）轉(zhuǎn)移函數(shù)第二項表明：從a節(jié)點（輸入）到e節(jié)點（輸出）有2條d=8的路徑（acdbe和acbcbe）依此類推……其中最小距離稱為最小自由距dfree，該例中dfree73第73頁，共116頁，2023年，2月20日，星期三卷積碼狀態(tài)圖中引入因子J和N：每個分支引入一個J當輸入比特為1而引發(fā)的轉(zhuǎn)移的分支上引入N狀態(tài)方程：bacdeJND3JDJDJD2JND2JND2引入因子J和N后的狀態(tài)圖：74第74頁，共116頁，2023年，2月20日，星期三卷積碼狀態(tài)方程轉(zhuǎn)移函數(shù)（Xe/Xa）：該轉(zhuǎn)移函數(shù)給出了卷積碼中的所有的路徑特性：第一項表明：距離d=6的路徑長度（分支書）為3，有3個輸入比特信息（J的指數(shù)為3），其中一個比特是1（N的指數(shù)為1）。第二項和第三項表明：有2條距離為8的路徑，其中一條長度為4（4的輸入比特信息）另一條長度為5（5個輸入比特信息）。在長度為4的的路徑中有2個輸入比特為1，在長度為5的路徑中有2個輸入比特是1。 下面的項依此類推……75第75頁，共116頁，2023年，2月20日，星期三卷積碼的譯碼常用的卷積碼的譯碼方法序列譯碼算法堆棧算法反饋譯碼軟輸出算法維特比算法——卷積碼最佳譯碼器76第76頁，共116頁，2023年，2月20日，星期三卷積碼的最佳譯碼——維特比譯碼卷積碼的最佳譯碼——維特比算法最佳：在加性高斯白噪聲、p<1/2的二進制對稱信道中，該算法的差錯概率最小。卷積碼的最佳譯碼器是最大似然序列估計器譯碼的目標：搜遍整個網(wǎng)格圖找到最有可能的序列。如下圖兩條路徑（綠色（i=0）和藍色（i=1））：abcd00000000000000010110110111111111111111100100100100111011011011001101101110010010001001001077第77頁，共116頁，2023年，2月20日，星期三維特比譯碼兩條路徑分別對應信息000和100對應的發(fā)送序列分別為：000000000和111000011{cjm,j=1,2,3;m=1,2,3}:發(fā)送比特;{rjm,j=1,2,3;m=1,2,3}:解調(diào)器的輸出j表示第j個分支，m表示該分支的第m個比特硬判決譯碼：解調(diào)器輸出0或者1軟判決譯碼：聯(lián)合條件概率對數(shù)：由B分支組成的第i條路徑的量度定義為：例如,接收序列為{101000100}，并執(zhí)行硬判決譯碼78第78頁，共116頁，2023年，2月20日，星期三維特比譯碼兩條路徑的量度：式中，p是比特差錯概率p<1/2，求得PM(0)>PM(1)序列{101000100}和{000000000}的漢明距為d=3序列{101000100}和{111001011}的漢明距為d=5說明對于硬判決譯碼來說漢明距是一種等效的量度。79第79頁，共116頁，2023年，2月20日，星期三維特比譯碼軟判決譯碼解調(diào)器的輸出的PDF：第i條路徑的第j分支的分支量度：此例中n=3這兩條路徑的相對量度：80第80頁，共116頁，2023年，2月20日，星期三維特比譯碼維特比算法在卷積碼譯碼中的應用：兩條路徑經(jīng)過3次轉(zhuǎn)移在a點匯合滿足CM(0)>CM(1)那么，任何起源于a節(jié)點的路徑CM(0)將仍然大于CM(1)以后可以不用再考慮與CM(1)對應的路徑，將其去除對于從零時刻開始的每一時刻，維特比譯碼器都要比較進入每一狀態(tài)的所有的路徑值，并把最大值的路徑與它的度量值一起存儲下來，這些路徑稱為幸存路徑（Survivor）。此例中幸存路徑是與CM(0)對應的路徑同理，根據(jù)度量大小，在b、c、d狀態(tài)混合的兩條路徑也可以去除其中之一。3次狀態(tài)轉(zhuǎn)移后只剩下4條路徑，每個狀態(tài)作為其中的一條的終點，并且每條幸存路徑有相應的度量。在每個時間間隔段中，在網(wǎng)格圖中每一級都重復這樣的步驟。81第81頁，共116頁，2023年，2月20日，星期三維特比譯碼維特比譯碼的步驟：步驟1：從時間j=m開始，計算進入每個狀態(tài)的路徑的部分度量。存儲每一狀態(tài)的路徑（幸存路徑）及度量值。步驟2：j增加1。計算進入每一狀態(tài)所有的路徑的部分度量。這個度量值是進入該狀態(tài)的分支度量加上與該分支相連的前一步的幸存路徑的度量值。對于每個狀態(tài)，共有2k這樣的度量值，從中選擇最大度量的路徑（幸存路徑），并刪除其他路徑。步驟3：如果j<L+m，重復步驟2，否則停止計算。從0到m時刻，從零狀態(tài)逐步翻倍擴展到2m個狀態(tài)。從m到L時刻的每一個時刻，都共有2k條幸存路徑分別與2k個狀態(tài)對應。L時刻以后幸存路徑逐步減少，直至L+m時刻只剩一條路徑進入s0狀態(tài)最后，從L+m時刻的s0回溯，維特比算法找到的最后的幸存路徑一定就是最大似然路徑。如果卷積碼為歸零，那么L時刻度量值最大的那個狀態(tài)是最有可能的末狀態(tài)，從該時刻回溯可以找到最大似然路徑。82第82頁，共116頁，2023年，2月20日，星期三維特比譯碼分支度量的計算和最大似然路徑的物理意義AWGN信道：接收信息：ri、vi、ni都是n維向量：分支度量：即：所以分支度量與信號的歐式距離成反比，即：對于AWGN，維特比算法找到的最大似然路徑就是與接收信號的歐式距離最小的網(wǎng)格圖路徑。83第83頁，共116頁，2023年，2月20日，星期三維特比譯碼BSC信道：信道的轉(zhuǎn)移概率矩陣:根據(jù)BSC的性質(zhì)：將上式整理一下：所以：即對于BSC，維特比算法找到的最大似然路徑就是與接收信號漢明距離最小的網(wǎng)格圖路徑84第84頁，共116頁，2023年，2月20日，星期三維特比譯碼例：[3,1,2]卷積碼，輸入序列為{1，0，1，0，0}對應的網(wǎng)格圖上的編碼路徑如下圖所示輸出碼字為{111，001，100，001，011}經(jīng)過BSC信道假設錯一個碼字，接收碼字為{111，011，100，001，011}，作為維特比解碼器的輸入序列rabcd000000000000000101111111111001001001110110011011011100歸零卷積碼的維特比解碼的網(wǎng)格圖01001001342585第85頁，共116頁，2023年，2月20日，星期三維特比譯碼狀態(tài)時刻abcd0a;0無無無1a;3無a;0無2a;5c;1a;4c;23b;4d;4b;1d;34b;5c;1無無5b;1無無無表中記錄了0時刻到5時刻，維特比解碼器所存儲的4個狀態(tài)所對應的上一個狀態(tài)（前一個值）和部分路徑度量（后一個值）。[3,1,2]維特比解碼的運算過程表86第86頁，共116頁，2023年，2月20日，星期三維特比譯碼時刻0到2，狀態(tài)數(shù)由1個遞增到4個時刻3到5，狀態(tài)數(shù)由4個遞減到1個第3時刻：狀態(tài)a3的前一個狀態(tài)可能是a2也可能是b2a2

（2時刻的狀態(tài)是a）：到3時刻的a狀態(tài)輸出是000，與輸入r2=100的漢明距是1，所以分支度量也是1；而a2由表中可知部分度量值是5，所以a3(3時刻a狀態(tài))部分度量值是5+1=6。b2（2時刻的狀態(tài)是b）：到3時刻的a狀態(tài)輸出是011，與輸入r2=100的漢明距是3，所以分支度量也是3；而b2由表中可知部分度量值是1，所以a3(3時刻a狀態(tài))部分度量值是3+1=4。比較這兩個不同的路徑，選取部分度量小的作為3時刻的a狀態(tài)部分度量值，也就是4按上述方法逐步遞推就可以得到表中運算的結(jié)果最后譯碼出{111，001，100，001，011}即對應 {1，0，1，0，0}87第87頁，共116頁，2023年，2月20日，星期三軟判決譯碼的差錯概率軟判決譯碼的差錯概率加性高斯白噪聲中使用軟判決譯碼時維特比算法的差錯概率假定發(fā)送的是全零序列，求誤判成另一個序列的概率。路徑量度：設i=0表示全零路徑，其路徑量度：把節(jié)點B上與全零路徑匯合的路徑的量度首次超過全零路徑量度的概率定義為首次差錯事件概率i=1的路徑比全零路徑有d比特差異（i=1路徑上有d個1其余為0）88第88頁，共116頁，2023年，2月20日，星期三軟判決譯碼的差錯概率比較CM(0)和CM(1)，得差錯概率：即：出現(xiàn)d比特差錯的概率：首次差錯概率上邊屆：由Q函數(shù)的性質(zhì)得：上邊界另一種形式：89第89頁，共116頁，2023年，2月20日，星期三軟判決譯碼的差錯概率轉(zhuǎn)移函數(shù)T(D,N)中因子N的指數(shù)代表與全零路徑匯合與某節(jié)點B的所選的錯誤路徑中差錯比特。對N求導，并令N=1：比特差錯概率的上邊界：K比特符號的差錯概率上邊界：90第90頁，共116頁，2023年，2月20日，星期三硬判決譯碼的差錯概率硬判決譯碼的差錯概率二進制對稱信道，采用維特比譯碼。假定發(fā)送的也是全零路徑，求誤判成另一序列的概率選擇錯誤路徑的總概率：聯(lián)合下邊界：較寬松的上邊界：比特差錯概率上邊界：當k>1時，上式定義的Pb的結(jié)果應再除以k91第91頁，共116頁，2023年，2月20日，星期三卷積碼譯碼的差錯概率K=3,k=1，n=3卷積碼的軟判決譯碼和硬判決譯碼的比較92第92頁，共116頁，2023年，2月20日，星期三刪余卷積碼刪余卷積碼在某些場合需要用到一些高碼率的卷積碼。而高碼率卷積碼的譯碼非常復雜，因此我們通過刪余（puncturing）低碼率卷積碼的某些比特來生成高碼率卷積碼以碼率為1/n的卷積碼為母本，并定義刪余周期p對應于輸入到編碼器的p個信息比特。在這個周期里，編碼器輸出np個編碼比特。如果我們在np個比特中刪除N比特，碼率為：與之對應的是刪余矩陣P：P中元素為0或者1。元素為1是，對應的編碼器輸出比特被傳送出去。若元素為0，對應的編碼器輸出比特被刪除。93第93頁，共116頁，2023年，2月20日，星期三刪余卷積碼例：用碼率為1/3，K=3的卷積碼，構(gòu)造一個碼率為3/4的碼。令善于周期p=3，選擇P為：下圖表明了刪余過程和刪余碼對應的網(wǎng)格圖輸入＋＋輸出刪余矩陣……111011……0011刪除比特……1101編碼器……100194第94頁，共116頁，2023年，2月20日，星期三刪余卷積碼從碼率1/3卷積碼生成碼率3/4刪余碼不同的刪余矩陣會有不同的漢明距，通過計算機搜索可以得到好的刪余矩陣，使得刪余后的漢明距與同碼率未刪余的卷積碼的漢明距相同或小1個比特。abcd0000000110111111110000011111000110195第95頁，共116頁，2023年，2月20日，星期三多碼率兼容刪余卷積碼多碼率兼容的刪余碼不同類型的信息比特群重要程度不同，采取的差錯保護程度也就不同以同一個低碼率1/n卷積碼為基礎(chǔ)刪除不同數(shù)量的“余”實現(xiàn)多碼率碼率刪余矩陣1/31111111111111111111111114/111111111111111111111011102/51111111111111111101010104/9111111111111111110001000由碼率1|3,K=4碼構(gòu)造的多碼率兼容刪余卷積碼96第96頁，共116頁，2023年，2月20日，星期三多碼率兼容刪余卷積碼碼率刪余矩陣1/21111111111111111000000004/71111111111101110000000004/61111111110101010000000004/51111111110001000000000008/9111111111000000000000000由碼率1/3，K=4碼構(gòu)造的多碼率兼容刪余卷積碼（續(xù)表）97第97頁，共116頁，2023年，2月20日，星期三并行級聯(lián)卷積碼——Turbo碼并行級聯(lián)卷積碼帶交織的并行級聯(lián)卷積碼（PCCC）也叫Turbo碼，是1993年Berrou等人提出。Turbo碼編碼器是一個遞歸系統(tǒng)的編碼器，由兩個并聯(lián)的卷積碼編碼器組成，并且在第二個編碼器之前串接了一個交織器。這兩個遞歸卷積碼編碼器可以是相同的也可以不同。交織器的作用是：在信息比特進入下一級編碼器之前，對信息比特進行重新排序。通常選用塊狀的偽隨機交織器。交織使得連續(xù)錯誤分散，利于糾錯；還使得原始信息序列的相關(guān)性減弱，實現(xiàn)編碼的隨機性；并且交織還起到改變碼字重量分布的作用，使得Turbo碼輸出的碼字中重量輕的碼字數(shù)量很少，有利用譯碼性能提高。98第98頁，共116頁，2023年，2月20日，星期三并行級聯(lián)卷積碼編碼器并行級聯(lián)卷積碼（Turbo碼）編碼器99第99頁，共116頁，2023年，2月20日，星期三并行級聯(lián)卷積碼Turbo碼的譯碼Turbo碼使用基于MAP準則的迭代譯碼。PCCC（Turbo碼）迭代解碼器方框圖100第100頁，共116頁，2023年，2月20日，星期三并行級聯(lián)卷積碼對于傳輸比特x=1和x=-1，我們將逐符號MAP解碼器的輸出定義為后驗對數(shù)相似比：先驗信息：信息比特x的軟輸出：解碼器1計算得出的外信息：解碼器1計算得出的外信息：最后一次迭代中，解碼器2計算軟輸出時將兩個外信息值結(jié)合在一起：101第101頁，共116頁，2023年，2月20日，星期三并行級聯(lián)卷積碼Turbo碼是非常優(yōu)秀的信道編碼器，仿真結(jié)果表明，在采用長度為65536的隨機交織器并譯碼迭代18次情況下，在信噪比Eb/N0≧0.7dB并采用BPSK調(diào)制時，碼率為1/2的turbo碼在AWGN信道上的BER≦10-5，達到了與香農(nóng)限僅差0.7dB的優(yōu)異性能。102第102頁，共116頁，2023年，2月20日，星期三本章的主要內(nèi)容6.1線性分組碼6.2卷積碼6.3帶限信道的編碼調(diào)制——網(wǎng)格編碼調(diào)制103第103頁，共116頁，2023年，2月20日，星期三本章的主要內(nèi)容6.1線性分組碼6.2卷積碼6.3帶限信道的編碼調(diào)制——網(wǎng)格編碼調(diào)制104第104頁，共116頁，2023年，2月20日，星期三網(wǎng)格編碼調(diào)制 TCM(網(wǎng)格編碼調(diào)制)是Ungerboeck于1982年提出的一種將編碼和調(diào)制結(jié)合在一起，利用狀態(tài)記憶和分集映射來增大編碼序列之間距離的編碼方法?；驹恚菏峭ㄟ^分集(setpartitioning)方法將編碼器對信息比特的編碼轉(zhuǎn)換為對信號節(jié)點的編碼，使得在信道中傳輸?shù)男盘桙c序列遵從一定的規(guī)則，即符合網(wǎng)格圖中的某條路徑。一方面它擴大星座尺寸為糾錯碼提供冗余度，另一方面?zhèn)鬏數(shù)男盘栃蛄惺蔷W(wǎng)格圖中的某條特定路徑，進而在信號點之間引入了相關(guān)性。TCM特點：把編碼和調(diào)制作為一個統(tǒng)一的整體，而并非相互獨立的過程，從而避免了在接收端解調(diào)器作硬判決時帶來的信息損失，其優(yōu)點在于其能夠在不增加信道帶寬、不降低有效信息傳輸速率的情況下獲得明顯的編碼增益，使系統(tǒng)的頻帶和功率利用率同時達到最佳。105第105頁，共116頁，2023年，2月20日，星期三網(wǎng)格編碼調(diào)制 分集對于給定的信號星座，將其分割成子集，使得分割后的子集內(nèi)的最小歐氏距離隨著每次分集變大。例：將一個8-PSK信號星座按最小歐氏距離逐級增大的原則劃分子集信號點位于半徑r的圓上，各點間最小歐氏距離：第一次分集：8點分成2個子集，每個子集4點，最小距離：第二次分集：2個子集又各分成2個子集，最小距離：