數(shù)字信號最佳接收PPT課件

1、1第11章差錯控制編碼 11.2 糾錯編碼的基本原理 分組碼的結構 將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼 。 在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。 信息位和監(jiān)督位的關系：舉例如下信息位監(jiān)督位晴000云011陰101雨110第1頁/共75頁2第11章差錯控制編碼 分組碼的一般結構 分組碼的符號：(n, k)N 碼組的總位數(shù)，又稱為碼組的長度（碼長），k 碼組中信息碼元的數(shù)目，n k r 碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。 第2頁/共75頁3第11章差錯控制編碼 分組碼的碼重和碼距 碼重：把碼組中“1”的個數(shù)目稱為碼組的重量，簡稱碼重。 碼距：把兩個碼組中對應位上

2、數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距。碼距又稱漢明距離。 例如，“000”晴，“011”云，“101”陰，“110”雨，4個碼組之間，任意兩個的距離均為2。 最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最小碼距(d0)。例如，上面的編碼的最小碼距d0 = 2。第3頁/共75頁4第11章差錯控制編碼 碼距和檢糾錯能力的關系 一種編碼的最小碼距d0的大小直接關系著這種編碼的檢錯和糾錯能力 為檢測e個錯碼，要求最小碼距 d0 e + 1 為了糾正t個錯碼，要求最小碼距d0 2t + 1 為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距)(10teted第4頁/共75頁5第11章差錯控制編碼 1

3、1.4簡單的實用編碼 11.4.1 奇偶監(jiān)督碼 奇偶監(jiān)督碼分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼兩種，兩者的原理相同。在偶數(shù)監(jiān)督碼中，無論信息位多少，監(jiān)督位只有1位，它使碼組中“1”的數(shù)目為偶數(shù)，即滿足下式條件：式中a0為監(jiān)督位，其他位為信息位。這種編碼能夠檢測奇數(shù)個錯碼。在接收端，按照上式求“模2和”，若計算結果為“1”就說明存在錯碼，結果為“0”就認為無錯碼。奇數(shù)監(jiān)督碼與偶數(shù)監(jiān)督碼相似，只不過其碼組中“1”的數(shù)目為奇數(shù)：0021aaann1021aaann第5頁/共75頁6第11章差錯控制編碼 11.4.2 二維奇偶監(jiān)督碼（方陣碼） 二維奇偶監(jiān)督碼的構成它是先把上述奇偶監(jiān)督碼的若干碼組排成矩陣，每一碼

4、組寫成一行，然后再按列的方向增加第二維監(jiān)督位，如下圖所示圖中a01 a02 a0m為m行奇偶監(jiān)督碼中的m個監(jiān)督位。cn-1 cn-2 c1 c0為按列進行第二次編碼所增加的監(jiān)督位，它們構成了一監(jiān)督位行。012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn第6頁/共75頁7第11章差錯控制編碼 11.4.3 恒比碼 在恒比碼中，每個碼組均含有相同數(shù)目的“1”（和“0”）。由于“1”的數(shù)目與“0”的數(shù)目之比保持恒定，故得此名。 這種碼在檢測時，只要計算接收碼組中“1”的數(shù)目是否對，就知道有無錯碼。 恒比碼的主要優(yōu)點是簡單和適于用來傳輸電傳機或其他

5、鍵盤設備產生的字母和符號。對于信源來的二進制隨機數(shù)字序列，這種碼就不適合使用了。第7頁/共75頁8第11章差錯控制編碼 11.4.4 正反碼 正反碼的編碼： 它是一種簡單的能夠糾正錯碼的編碼。其中的監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼元與信息碼元相同或者相反則由信息碼中“1”的個數(shù)而定。 例如，若碼長n = 10，其中信息位 k = 5，監(jiān)督位 r = 5。其編碼規(guī)則為： 當信息位中有奇數(shù)個“1”時，監(jiān)督位是信息位的簡單重復； 當信息位有偶數(shù)個“1”時，監(jiān)督位是信息位的反碼。 例如，若信息位為11001，則碼組為1100111001；若信息位為10001，則碼組為1000101110。第8頁/共

6、75頁9第11章差錯控制編碼 11.5 線性分組碼 基本概念 代數(shù)碼：建立在代數(shù)學基礎上的編碼。 線性碼：按照一組線性方程構成的代數(shù)碼。在線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的。 線性分組碼：按照一組線性方程構成的分組碼 。本節(jié)將以漢明碼為例引入線性分組碼的一般原理。第9頁/共75頁10第11章差錯控制編碼 漢明碼能夠糾正1位錯碼且編碼效率較高的一種線性分組碼。 漢明碼的構造原理。 在偶數(shù)監(jiān)督碼中，由于使用了一位監(jiān)督位a0，它和信息位an-1 a1一起構成一個代數(shù)式：在接收端解碼時，實際上就是在計算若S = 0，就認為無錯碼；若S = 1，就認為有錯碼?，F(xiàn)將上式稱為監(jiān)督關系式，S稱

7、為校正子。由于校正子S只有兩種取值，故它只能代表有錯和無錯這兩種信息，而不能指出錯碼的位置。 0021aaann021aaaSnn第10頁/共75頁11第11章差錯控制編碼 如果希望用r個監(jiān)督位構造出r個監(jiān)督關系式來指示1位錯碼的n種可能位置，則要求1212rknrr或第11頁/共75頁12第11章差錯控制編碼 例：以分組碼(n, k)中的（7,4）漢明碼為例，用S1、S2和S3表示3個監(jiān)督關系式中的校正子，則S1、S2和S3的值與錯碼位置的對應關系可以規(guī)定如下表所列：S1 S2 S3錯碼位置S1 S2 S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無

8、錯碼漢明碼的最小碼距d0 = 3。因此，這種碼能夠糾正1個錯碼或檢測2個錯碼。由于碼率k/n = (n - r) /n =1 r/n，故當n很大和r很小時，碼率接近1?？梢姡瑵h明碼是一種高效碼。 第12頁/共75頁13第11章差錯控制編碼由表中規(guī)定可見，僅當一位錯碼的位置在a2 、a4、a5或a6時，校正子S1為1；否則S1為零。這就意味著a2 、a4、a5和a6四個碼元構成偶數(shù)監(jiān)督關系：同理， a1、a3、a5和a6構成偶數(shù)監(jiān)督關系：以及a0、a3、a4 和a6構成偶數(shù)監(jiān)督關系24561aaaaS13562aaaaS03463aaaaS第13頁/共75頁14第11章差錯控制編碼 在發(fā)送端編碼

9、時，信息位a6、a5、a4和a3的值決定于輸入信號，因此它們是隨機的。監(jiān)督位a2、a1和a0應根據(jù)信息位的取值按監(jiān)督關系來確定，即監(jiān)督位應使上3式中S1、S2和S3的值為0（表示編成的碼組中應無錯碼）：上式經過移項運算，解出監(jiān)督位給定信息位后，可以直接按上式算出監(jiān)督位， 結果見下表：000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa第14頁/共75頁15第11章差錯控制編碼信息位a6 a5 a4 a3監(jiān)督位a2 a1 a0信息位a6 a5 a4 a3監(jiān)督位a2 a1 a0000000010001110001011100110000101011

10、0100100011110101100101001101100001010110111010100110011111010001110001111111第15頁/共75頁16第11章差錯控制編碼 接收端收到每個碼組后，先計算出S1、S2和S3，再查表判斷錯碼情況。例如，若接收碼組為0000011，按上述公式計算可得：S1 = 0，S2 = 1，S3 = 1。由于S1 S2 S3 等于011，故查表可知在a3位有1錯碼。 第16頁/共75頁17第11章差錯控制編碼 線性分組碼的一般原理 線性分組碼的構造H矩陣上面(7, 4)漢明碼的例子有現(xiàn)在將上面它改寫為上式中已經將“”簡寫成“+”。 0000

11、34613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa第17頁/共75頁18第11章差錯控制編碼上式可以表示成如下矩陣形式：上式還可以簡記為H AT = 0T 或A HT = 0010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa）（模20001011001110101011101000123456aaaaaaa第18頁/共75頁19第11章差錯控制編碼H AT = 0T 或A HT = 0式

12、中 A = a6 a5 a4 a3 a2 a1 a00 = 000右上標“T”表示將矩陣轉置。例如，HT是H的轉置，即HT的第一行為H的第一列，HT的第二行為H的第二列等等。將H稱為監(jiān)督矩陣。 只要監(jiān)督矩陣H給定，編碼時監(jiān)督位和信息位的關系就完全確定了。 101100111010101110100H第19頁/共75頁20第11章差錯控制編碼H矩陣的性質： 1) H的行數(shù)就是監(jiān)督關系式的數(shù)目，它等于監(jiān)督位的數(shù)目r。H的每行中“1”的位置表示相應碼元之間存在的監(jiān)督關系。例如，H的第一行1110100表示監(jiān)督位a2是由a6 a5 a4之和決定的。H矩陣可以分成兩部分，例如 式中，P為r k階矩陣，I

13、r為r r階單位方陣。我們將具有P Ir形式的H矩陣稱為典型陣。rPIH001101101011011001110第20頁/共75頁21第11章差錯控制編碼G矩陣：上面漢明碼例子中的監(jiān)督位公式為也可以改寫成矩陣形式：346035614562aaaaaaaaaaaa3456012101111011110aaaaaaa第21頁/共75頁22第11章差錯控制編碼或者寫成式中，Q為一個k r階矩陣，它為P的轉置，即 Q = PT 上式表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產生出監(jiān)督位。3456012101111011110aaaaaaaQ34563456012011101110111aaaa

14、aaaaaaa第22頁/共75頁23第11章差錯控制編碼我們將Q的左邊加上1個k k階單位方陣，就構成1個矩陣G G稱為生成矩陣，因為由它可以產生整個碼組，即有或者因此，如果找到了碼的生成矩陣G，則編碼的方法就完全確定了。具有IkQ形式的生成矩陣稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼稱為系統(tǒng)碼。 0110001101001011001001111000QGkI I G34560123456aaaaaaaaaaaGA3456aaaa第23頁/共75頁24第11章差錯控制編碼 錯碼矩陣和錯誤圖樣 一般說來，A為一個n列的行矩陣。此矩陣的n個

15、元素就是碼組中的n個碼元，所以發(fā)送的碼組就是A。此碼組在傳輸中可能由于干擾引入差錯，故接收碼組一般說來與A不一定相同。 若設接收碼組為一n列的行矩陣B，即則發(fā)送碼組和接收碼組之差為B A = E (模2)它就是傳輸中產生的錯碼行矩陣 式中0121bbbbnnB0121eeeennEiiiiiababe當當, 1, 0第24頁/共75頁25第11章差錯控制編碼因此，若ei = 0，表示該接收碼元無錯；若ei = 1，則表示該接收碼元有錯。 B A = E 可以改寫成 B = A + E例如，若發(fā)送碼組A = 1000111，錯碼矩陣E = 0000100，則接收碼組B = 1000011。錯碼矩

16、陣有時也稱為錯誤圖樣。第25頁/共75頁26第11章差錯控制編碼 校正子S當接收碼組有錯時，E 0，將B當作A代入公式(A H T = 0)后，該式不一定成立。在錯碼較多，已超過這種編碼的檢錯能力時，B變?yōu)榱硪辉S用碼組，則該式仍能成立。這樣的錯碼是不可檢測的。在未超過檢錯能力時，上式不成立，即其右端不等于0。假設這時該式的右端為S，即B H T = S將B = A + E代入上式，可得S = (A + E) H T = A H T + E H T由于A HT = 0，所以S = E H T式中S稱為校正子。它能用來指示錯碼的位置。S和錯碼E之間有確定的線性變換關系。若S和E之間一一對應，則S將

17、能代表錯碼的位置。第26頁/共75頁27第11章差錯控制編碼 線性分組碼的性質 封閉性：是指一種線性碼中的任意兩個碼組之和仍為這種碼中的一個碼組。這就是說，若A1和A2是一種線性碼中的兩個許用碼組，則(A1+A2)仍為其中的一個碼組。這一性質的證明很簡單。若A1和A2是兩個碼組，則有A1 HT = 0,A2 HT = 0將上兩式相加，得出A1 HT + A2 HT = (A1 + A2) HT = 0所以(A1 + A2)也是一個碼組。由于線性碼具有封閉性，所以兩個碼組(A1和A2)之間的距離（即對應位不同的數(shù)目）必定是另一個碼組(A1 + A2)的重量（即“1”的數(shù)目）。因此，碼的最小距離就

18、是碼的最小重量（除全“0”碼組外）。第27頁/共75頁28第11章差錯控制編碼 11.6 循環(huán)碼 11.6.1 循環(huán)碼原理 循環(huán)性：循環(huán)性是指任一碼組循環(huán)一位（即將最右端的一個碼元移至左端，或反之）以后，仍為該碼中的一個碼組。在下表中給出一種(7, 3)循環(huán)碼的全部碼組。例如，表中的第2碼組向右移一位即得到第5碼組；第6碼組向右移一位即得到第7碼組。 碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010第28頁/共75頁29

19、第11章差錯控制編碼 碼多項式 碼組的多項式表示法把碼組中各碼元當作是一個多項式的系數(shù)，即把一個長度為n的碼組表示成例如，上表中的任意一個碼組可以表示為其中第7個碼組可以表示為這種多項式中，x僅是碼元位置的標記，例如上式表示第7碼組中a6、a5、a2和a0為“1”，其他均為0。因此我們并不關心x的取值。 012211)(axaxaxaxTnnnn012233445566)(axaxaxaxaxaxaxT11010011)(25623456xxxxxxxxxxT第29頁/共75頁30第11章差錯控制編碼 碼多項式的按模運算 在整數(shù)運算中，有模n運算。例如，在模2運算中，有1 + 1 = 2 0

20、(模2)，1 + 2 = 3 1 (模2)， 2 3 = 6 0 (模2)等等。一般說來，若一個整數(shù)m可以表示為式中，Q 整數(shù)，則在模 n 運算下，有m p (模n)即，在模 n 運算下，一個整數(shù)m等于它被 n 除得的余數(shù)。 npnpQnm,第30頁/共75頁31第11章差錯控制編碼 在碼多項式運算中也有類似的按模運算。若一任意多項式F(x)被一 n 次多項式N (x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)，即則寫為這時，碼多項式系數(shù)仍按模2 運算，即系數(shù)只取 0 和1。例如，x3被(x3 + 1)除，得到余項1。所以有同理因為)()()()(xRxQxNxF）（模)()()(xN

21、xRxF）（模)1(133xx）（模) 1(113224xxxxx xx3 + 1 x4 +x2 + 1 x4 + x x2 +x +1應當注意，由于在模2運算中，用加法代替了減法，故余項不是x2 x + 1，而是x2 + x + 1。第31頁/共75頁32第11章差錯控制編碼 循環(huán)碼的碼多項式 在循環(huán)碼中，若T(x)是一個長為n的許用碼組，則xiT(x)在按模xn + 1運算下，也是該編碼中的一個許用碼組，即若則T (x)也是該編碼中的一個許用碼組?！咀C】因為若則（模(xn + 1)）所以，這時有）（模) 1()()(nixxTxTx012211)(axaxaxaxTnnnninininin

22、niniinininninniaxaxaxaxaxaxaxaxaxaxTx1102211011112211)(ininininninaxaxaxaxaxT1102211)(第32頁/共75頁33第11章差錯控制編碼上式中T (x)正是T(x)代表的碼組向左循環(huán)移位i次的結果。因為原已假定T(x)是循環(huán)碼的一個碼組，所以T (x)也必為該碼中一個碼組。例如，循環(huán)碼組其碼長n = 7。現(xiàn)給定i = 3，則其對應的碼組為0101110，它正是表中第3碼組。由上述分析可見，一個長為n的循環(huán)碼必定為按模(xn + 1)運算的一個余式。ininininninaxaxaxaxaxT1102211)(1)(2

23、56xxxxT）（模) 1() 1()(7235358925633xxxxxxxxxxxxxxTx第33頁/共75頁34第11章差錯控制編碼 循環(huán)碼的生成矩陣G 在循環(huán)碼中，一個(n, k)碼有2k個不同的碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是碼組，而且這k個碼組是線性無關的。因此它們可以用來構成此循環(huán)碼的生成矩陣G。 在一個（n,k）循環(huán)碼中，有 且只有一個次數(shù)為 (n k)的多項式g(x)，稱其為碼的生成多項式。一旦確定了g(x)，則整個(n, k)循環(huán)碼就被確定了。 第34頁/共75頁35第11章差錯控制

24、編碼 因此，循環(huán)碼的生成矩陣G可以寫成 例：在上表所給出的(7, 3)循環(huán)碼中，n = 7, k = 3, n k = 4。由此表可見，唯一的一個(n k) = 4次碼多項式代表的碼組是第二碼組0010111，與它相對應的碼多項式（即生成多項式）g(x) = x4 + x2 + x + 1。將此g(x)代入上式，得到或)()()()()(21xgxxgxgxxgxxkkG)()()()(2xgxxgxgxxG001011101011101011100)(xG第35頁/共75頁36第11章差錯控制編碼由于上式不符合G = IkQ的形式，所以它不是典型陣。不過，將它作線性變換，不難化成典型陣。我們

25、可以寫出此循環(huán)碼組，即上式表明，所有碼多項式T(x)都可被g(x)整除，而且任意一個次數(shù)不大于(k 1)的多項式乘g(x)都是碼多項式。)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG第36頁/共75頁37第11章差錯控制編碼 如何尋找任一(n, k)循環(huán)碼的生成多項式 由上式可知，任一循環(huán)碼多項式T(x)都是g(x)的倍式，故它可以寫成T(x) = h(x)g(x)而生成多項式g(x)本身也是一個碼組，即有 T (x) = g(x)由于碼組T (x)是一個(n k)次多項式，故xk T (x)是一個

26、n次多項式。由下式可知，xk T (x)在模(xn + 1)運算下也是一個碼組，故可以寫成）（模) 1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx第37頁/共75頁38第11章差錯控制編碼上式左端分子和分母都是n次多項式，故商式Q(x) = 1。因此，上式可以化成將T(x)和T(x)表示式代入上式，經過化簡后得到上式表明，生成多項式g(x)應該是(xn + 1)的一個因子。這一結論為我們尋找循環(huán)碼的生成多項式指出了一條道路，即循環(huán)碼的生成多項式應該是(xn +1)的一個(n k)次因式。例如，(x7 + 1)可以分解為為了求(7, 3)循環(huán)碼的生成多項式g(x)，需要從上

27、式中找到一個(n k) = 4次的因子。不難看出，這樣的因子有兩個，即1)()(1)(nnkxxTxQxxTx)() 1()(xTxxTxnk)()(1xhxxgxkn) 1)(1)(1(13237xxxxxx第38頁/共75頁39第11章差錯控制編碼以上兩式都可作為生成多項式。不過，選用的生成多項式不同，產生出的循環(huán)碼碼組也不同。1) 1)(1(2423xxxxxx1) 1)(1(2343xxxxxx第39頁/共75頁40第11章差錯控制編碼 11.6.2 循環(huán)碼的編解碼方法 循環(huán)碼的編碼方法 編碼原則在編碼時，首先要根據(jù)給定的(n, k)值選定生成多項式g(x)，即從(xn + 1)的因子

28、中選一個(n - k)次多項式作為g(x)。第40頁/共75頁41第11章差錯控制編碼 編碼步驟： （1）用xn - k乘m(x)。這一運算實際上是在信息碼后附加上(n k)個“0”。例如，信息碼為110，它相當于m(x) = x2 + x。當n k = 7 3 = 4時，xn - k m(x) = x4 (x2 + x) = x6 + x5，它相當于1100000。 （2）用g(x)除xn - k m(x)，得到商Q(x)和余式r(x)，即例如，若選定g(x) = x4 + x2 + x + 1，則 上式相當于)()()()()(xgxrxQxgxmxkn11) 1(1)()(2422245

29、6xxxxxxxxxxxxgxmxkn10111101111101111100000第41頁/共75頁42第11章差錯控制編碼（3）編出的碼組T(x)為T(x) = xn - k m(x) + r(x) 在上例中，T(x) = 1100000 + 101 = 1100101，它就是上表中的第7碼組。第42頁/共75頁43第11章差錯控制編碼 循環(huán)碼的解碼方法 解碼要求：檢錯和糾錯。 檢錯解碼原理：由于任意一個碼組多項式T(x)都應該能被生成多項式g(x)整除，所以在接收端可以將接收碼組R(x)用原生成多項式g(x)去除。當傳輸中未發(fā)生錯誤時，接收碼組與發(fā)送碼組相同，即R(x) = T(x)，故

30、接收碼組R(x)必定能被g(x)整除；若碼組在傳輸中發(fā)生錯誤，則R(x) T(x)，R(x)被g(x)除時可能除不盡而有余項，即有因此，就以余項是否為零來判別接收碼組中有無錯碼。需要指出，有錯碼的接收碼組也有可能被g(x)整除。這時的錯碼就不能檢出了。這種錯誤稱為不可檢錯誤。不可檢錯誤中的誤碼數(shù)必定超過了這種編碼的檢錯能力。)(/ )()()(/ )(xgxrxQxgxR第43頁/共75頁44第11章差錯控制編碼糾錯解碼原理：為了能夠糾錯，要求每個可糾正的錯誤圖樣必須與一個特定余式有一一對應關系。因為只有存在上述一一對應的關系時，才可能從上述余式唯一地決定錯誤圖樣，從而糾正錯碼。因此，原則上糾

31、錯可按下述步驟進行：用生成多項式g(x)除接收碼組R(x)，得出余式r(x)。按余式r(x)，用查表的方法或通過某種計算得到錯誤圖樣E(x)；例如，通過計算校正子S和查表，就可以確定錯碼的位置。從R(x)中減去E(x)，便得到已經糾正錯碼的原發(fā)送碼組T(x)。通常，一種編碼可以有幾種糾錯解碼方法，上述解碼方法稱為捕錯解碼法。 目前多采用軟件運算實現(xiàn)上述編解碼運算。第44頁/共75頁45第11章差錯控制編碼 11.7 卷積碼 非分組碼概念： 卷積碼是一種非分組碼。通常它更適用于前向糾錯，因為對于許多實際情況它的性能優(yōu)于分組碼，而且運算較簡單。 卷積碼在編碼時雖然也是把k個比特的信息段編成n個比特

32、的碼組，但是監(jiān)督碼元不僅和當前的k比特信息段有關，而且還同前面m = (N 1)個信息段有關。所以一個碼組中的監(jiān)督碼元監(jiān)督著N個信息段。通常將N稱為編碼約束度，并將nN稱為編碼約束長度。一般說來，對于卷積碼，k 和 n 的值是比較小的整數(shù)。我們將卷積碼記作(n, k, N)。碼率則仍定義為k / n。 第45頁/共75頁46第11章差錯控制編碼 11.7.1 卷積碼的基本原理 編碼器原理方框圖編碼輸出每次輸入k比特1k1k1k1k 1 k2k3kNk 12nNk級移存器n個模2加法器每輸入k比特旋轉1周第46頁/共75頁47第11章差錯控制編碼 例： (n, k, N) = (3, 1, 3)

33、卷積碼編碼器 方框圖 設輸入信息比特序列是bi-2 bi-1 bi bi+1，則當輸入bi時，此編碼器輸出3比特ci di ei，輸入和輸出的關系如下：bi-2bi輸入bibi-1編碼輸出dicieiM2M3M121 2iiiiiiiiibbbebbdbc第47頁/共75頁48ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt輸入輸出第11章差錯控制編碼在下圖中用虛線示出了信息位bi的監(jiān)督位和各信息位之間的約束關系。這里的編碼約束長度nN等于9。 第48頁/共75頁49第11章差錯控制編碼 11.7.2 卷積碼的代數(shù)表述上式表示卷積碼也是一種線性碼。一個線性碼完

34、全由一個監(jiān)督矩陣H或生成矩陣G所確定。下面就來尋找這兩個矩陣。 監(jiān)督矩陣H現(xiàn)在仍從上面的實例開始分析。假設上圖中在第1個信息位b1進入編碼器之前，各級移存器都處于“0”狀態(tài)，則監(jiān)督位di、ei和信息位bi之間的關系可以寫為第49頁/共75頁50第11章差錯控制編碼 左式可以改寫為在上面兩個式子和后面的式子中，為簡便計，用“”代替“”。將上式用矩陣表示時，可以寫成11112222133133214424432dbebdbebbdbbebbbdbbebbb 1111221221331233244234400000000bdbebdbbebbdbbbebbdbbbe 第50頁/共75頁51第11章差

35、錯控制編碼與11.5節(jié)公式H AT = 0T對比，可以看出監(jiān)督矩陣為Oedbedbedbedb44433322211101000100100110001000001100100101100000111001010001110111第51頁/共75頁52第11章差錯控制編碼由此例可見，卷積碼的監(jiān)督矩陣H是一個有頭無尾的半無窮矩陣。此外，這個矩陣的每3列的結構是相同的，只是后3列比前3列向下移了兩行。例如，第4 6列比第1 3列低2行。自第7行起，每兩行的左端比上兩行多了3個“0”。 01000100100110001000001100100101100000111001010001110111H

36、第52頁/共75頁53第11章差錯控制編碼雖然這樣的半無窮矩陣不便于研究，但是只要研究產生前9個碼元（9為約束長度）的監(jiān)督矩陣就足夠了。不難看出，這種截短監(jiān)督矩陣的結構形式如下圖所示：由此圖可見，H1的最左邊是n列(n-k)N行的一個子矩陣，且向右的每n列均相對于前n列降低(n - k)行。H1 =nn k(n k)N第53頁/共75頁54第11章差錯控制編碼此例中碼的截短監(jiān)督矩陣可以寫成如下形式：式中 2階單位方陣； Pi 1 2階矩陣，i = 1, 2, 3； O2 2階全零方陣。2122232122211100100101100000111001010001110111IPOPOPIPO

37、PIPH01102I第54頁/共75頁55第11章差錯控制編碼一般說來，卷積碼的截短監(jiān)督矩陣具有如下形式：式中 In-k (n k)階單位方陣； Pi k (n k)階矩陣； On-k (n k)階全零方陣。有時還將H1的末行稱為基本監(jiān)督矩陣hh = PN On-k PN-1 On-k PN-2 On-k P1 In-k它是卷積碼的一個最重要的矩陣，因為只要給定了h，則H1也就隨之決定了?；蛘哒f，我們從給定的h不難構造出H1。knknNknNknNknknknknknknIPOPOPOPIPOPOPIPOPIPH1211231211第55頁/共75頁56第11章差錯控制編碼 生成矩陣G上例中的

38、輸出碼元序列可以寫成 b1 d1 e1 b2 d2 e2 b3 d3 e3 b4 d4 e4 = b1 b1 b1 b2 b2 (b2 + b1) b3 (b3 + b1) (b3 + b2 + b1) b4 (b4 + b2) (b4 + b3 + b2) 00000000000000000000000000100000000000001110000000000001111000000001100111100000000110011114321bbbb第56頁/共75頁57第11章差錯控制編碼此碼的生成矩陣G即為上式最右矩陣： 它也是一個半無窮矩陣，其特點是每一行的結構相同，只是比上一行向右

39、退后3列（因現(xiàn)在n = 3）。0000000000000000000000000010000000000000111000000000000111100000000110011110000000011001111G第57頁/共75頁58第11章差錯控制編碼 截短生成矩陣：類似地，也有截短生成矩陣式中 I1 一階單位方陣；Qi 2 1階矩陣。與H1矩陣比較可見，Qi是矩陣PiT的轉置：Qi = PiT (i = 1, 2, )一般說來，截短生成矩陣具有如下形式：1121132111111000000001111000011001111QIQOQIQOQOQIG第58頁/共75頁59第11章差錯控

40、制編碼式中 Ik k階單位方陣； Qi (n k)k階矩陣； Ok k階全零方陣。并將上式中矩陣第一行稱為基本生成矩陣g Ik Q1 Ok Q2 Ok Q3Ok QN同樣，如果基本生成矩陣g已經給定，則可以從已知的信息位得到整個編碼序列。1211213211QIQOQIQOQOQIQOQOQOQIGkNkkNkkkNkkkk第59頁/共75頁60第11章差錯控制編碼 11.7.3 卷積碼的解碼 分類： 代數(shù)解碼：利用編碼本身的代數(shù)結構進行解碼，不考慮信道的統(tǒng)計特性。大數(shù)邏輯解碼，又稱門限解碼，是卷積碼代數(shù)解碼的最主要一種方法，它也可以應用于循環(huán)碼的解碼。大數(shù)邏輯解碼對于約束長度較短的卷積碼最為

41、有效，而且設備較簡單。 概率解碼：又稱最大似然解碼。它基于信道的統(tǒng)計特性和卷積碼的特點進行計算。針對無記憶信道提出的序貫解碼就是概率解碼方法之一。另一種概率解碼方法是維特比算法。當碼的約束長度較短時，它比序貫解碼算法的效率更高、速度更快，目前得到廣泛的應用。第60頁/共75頁61第11章差錯控制編碼 大數(shù)邏輯解碼 工作原理 圖中首先將接收信息位暫存于移存器中，并從接收碼元的信息位和監(jiān)督位計算校正子。然后，將計算得出的校正子暫存，并用它來檢測錯碼的位置。在信息位移存器輸出端，接有一個模2加電路；當檢測到輸出的信息位有錯時，在輸出的信息位上加“1”，從而糾正之。 校正子計算信息位移存器校正子移存器

42、錯碼檢測 輸入輸出修正校正子信息位監(jiān)督位第61頁/共75頁62第11章差錯控制編碼 例：(2, 1, 6)卷積碼 編碼器方框圖 監(jiān)督位和信息位的關系當輸入序列為b1 b2 b3 b4 時，監(jiān)督位為c1 = b1c2 = b2c3 = b3c4 = b1 + b4c5 = b1 + b2 + b5c6 = b1 + b2 + b3 + b6 b6b5b4b3b2b1bi ci輸入輸出bici第62頁/共75頁63第11章差錯控制編碼 監(jiān)督關系式 參照11.5節(jié)中監(jiān)督關系的定義式，容易寫出 S1 = c1 + b1S2 = c2 + b2S3 = c3 + b3S4 = c4 + b1 + b4S

43、5 = c5 + b1 + b2 + b5S6 = c6 + b1 + b2 + b3 + b6上式中的Si (i = 1 6)稱為校正子。 正交校驗方程組上式經過簡單線性變換后，得出如下正交校驗方程組：第63頁/共75頁64第11章差錯控制編碼S1 = c1 + b1S4 = c4 + b1 + b4S5 = c5 + b1 + b2 + b5S2 + S6 = c2 + c6 + b1 + b3 + b6在上式中，只有信息位b1出現(xiàn)在每個方程中，監(jiān)督位和其他信息位均最多只出現(xiàn)一次。因此，在接收端解碼時，考察b1、c1至b6、c6等12個碼元，僅當b1出錯時，式中才可能有3個或3個以上方程等

44、于“1”。從而能夠糾正b1的錯誤。 第64頁/共75頁65輸入輸出Yb6b5b4b3b2b1S6S5S4S3S2S1門限電路：“1”的個數(shù) 3？校正子Si校正子移存器信息位移存器重算監(jiān)督位ci接收監(jiān)督位計算校正子Si6 5 4 3 2 1第11章差錯控制編碼 解碼器方框圖按照這一原理畫出的此(2, 1, 6)卷積碼解碼器方框圖如下第65頁/共75頁66第11章差錯控制編碼由此圖可見，當信息位出現(xiàn)一個錯碼時，僅當它位于信息位移存器的第6、3、2和1級時，才使校正子等于“1”。因此，這時的校正子序列為100111；反之，當監(jiān)督位出現(xiàn)一個錯碼時，校正子序列將為100000。由此可見，當校正子序列中出

45、現(xiàn)第一個“1”時，表示已經檢出一個錯碼。后面的幾位校正子則指出是信息位錯了，還是監(jiān)督位錯了。圖中門限電路的輸入代表式中4個方程的4個電壓。門限電路將這4個電壓（非模2）相加。當相加結果大于或等于3時，門限電路輸出“1”，它除了送到輸出端的模2加法器上糾正輸出碼元b1的錯碼外，還送到校正子移存器糾正其中錯誤。 此卷積碼除了能夠糾正兩位在約束長度中的隨機錯誤外，還能糾正部分多于兩位的錯誤。 第66頁/共75頁67第11章差錯控制編碼 卷積碼的幾何表述 碼樹圖：現(xiàn)仍以上面(3, 1, 3)碼為例，介紹卷積碼的碼樹 起點信息位狀態(tài) M3M2 a 0 0 b 0 1 c 1 0 d 1 1信息位信息位

46、11 0 1000111c1d1e1000111001110011100010101000111001110011100010101c4d4e4111000001110c2d2e22000100111011001101110010c3d3e3abcdabcdabcdabcd上半部下半部ba10aabcdabcdcdab011001第67頁/共75頁68第11章差錯控制編碼將圖中移存器M1，M2和M3的初始狀態(tài)000作為碼樹的起點?，F(xiàn)在規(guī)定：輸入信息位為“0”，則狀態(tài)向上支路移動；輸入信息位為“1”，則狀態(tài)向下支路移動。于是，就可以得出圖中所示的碼樹。設現(xiàn)在的輸入碼元序列為1101，則當?shù)?個信息位b1 = 1輸入后，各移存器存儲的信息分別為M1 = 1，M2 = M3 = 0。此時的輸出為c1 d1 e1= 111，碼樹的狀態(tài)將從起點a向下到達狀態(tài)b；此后，第2個輸入信息位b2 = 1，故碼樹狀態(tài)將從狀態(tài)b向下到達狀態(tài)d。這時M2 = 1，M3 = 0，此時，c