第9章差錯控制編碼

會計學(xué)1第9章差錯控制編碼常用的差錯控制方法有以下幾種：檢錯重發(fā)法——接收端在收到的信碼中檢測出(發(fā)現(xiàn))錯碼時，即設(shè)法通知發(fā)送端重發(fā)，直到正確收到為止。前向糾錯法——接收端不僅能發(fā)現(xiàn)錯碼，還能夠確定錯碼的位置，能夠糾正它。反饋校驗法——接收端將收到的信碼原封不動地轉(zhuǎn)發(fā)回發(fā)送端與原信碼比較。若發(fā)現(xiàn)錯誤則發(fā)端重發(fā)。三種差錯控制方法可以結(jié)合使用。第1頁/共118頁接收端根據(jù)什么來識別有無錯碼——由發(fā)送端的信道編碼器在信息碼元序列中增加一些監(jiān)督碼元。這些監(jiān)督碼和信碼之間有確定的關(guān)系，使接收端可以利用這種關(guān)系由信道譯碼器來發(fā)現(xiàn)或糾正可能存在的錯碼。在信息碼元序列中加入監(jiān)督碼元就稱為差錯控制編碼，有時也稱為糾錯編碼。差錯控制編碼原則上是以降低信息傳輸速率為代價來換取傳輸可靠性的提高。第2頁/共118頁ARQ系統(tǒng)組成信源編碼器和緩沖存儲重發(fā)控制雙向信道譯碼器指令產(chǎn)生緩沖存儲收信者ARQ優(yōu)點：冗余碼元少、對信道有自適應(yīng)能力、成本和復(fù)雜性低；ARQ缺點：需要反向信道、重發(fā)控制較復(fù)雜、干擾大通信效率低、實時性差。第3頁/共118頁例：3位二進制數(shù)字構(gòu)成的碼組，共有8種不同的組合。若將其全部利用來表示天氣，則可以表示8種不同的天氣。000(晴)，001(多云)，010(陰)，011(雨)，100(雪)，101(霜)，110(霧)，111(雹)。任一碼組在傳輸中若發(fā)生一個或多個措碼．則將變成另一信息碼組。這時接收端將無法發(fā)現(xiàn)錯誤?！?.2糾錯編碼的基本原理第4頁/共118頁若：000=晴001=不可用010=不可用011=云100=不可用101=陰110=雨111=不可用則：雖然只能傳送4種不同的天氣．但是接收消卻有可能發(fā)現(xiàn)碼組中的一個錯碼。例如，若000(晴)中錯了一位，則接收碼組將變成100或010或001，這三種碼組都是不準許使用的，稱為禁用碼組，故接收端在收到禁用碼組時，就認為發(fā)現(xiàn)了錯碼。第5頁/共118頁但是這種碼不能發(fā)現(xiàn)兩個措碼，因為發(fā)生兩個錯碼后產(chǎn)生的是許用碼組。上述碼只能檢測錯誤，不能糾正錯誤。例如，當(dāng)收到的碼組為禁用碼組100時，無法判斷是哪一位碼發(fā)生了錯誤．因為晴、陰、雨三者錯了一位都可以變成100。要想能糾正錯誤，還要增加多余度。例如，苦規(guī)定許用碼組只有兩個：000(晴)、111(雨)、其余都是禁用碼組。這時，接收場能檢測兩個以下錯碼，或能糾正一個錯碼。第6頁/共118頁分組碼的一般概念。為了傳輸4種不同的信息，用兩位二進制碼組就夠了，它們是：00、01、10、11。代表所傳信息的這些兩位碼，稱為信息位。前面使用3位碼，多出的一位稱為監(jiān)督位。信息碼分組，每組信碼附加若干監(jiān)督碼的編碼集合，稱為分組碼。例如第7頁/共118頁第8頁/共118頁分組碼的結(jié)構(gòu)符號(n，k)表示分組碼k——信息碼元數(shù)n——碼組長度(碼長)n-k——監(jiān)督碼元數(shù)an-1an-2ar…………ar-1a0k位信息位r位監(jiān)督位n=k+r時間第9頁/共118頁碼重、碼距與碼的糾檢錯能力碼重——“1”的數(shù)量稱為碼組的重量碼距——兩個碼組對應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距。又稱漢明(Hamming)距離。最小碼距——某種編碼中各個碼組間距離的最小值稱為最小碼距(d0)。若記：d0——最小碼距；

e——檢錯位數(shù)；

t——糾錯位數(shù)；則有：第10頁/共118頁（1）e

+1≤d0，即碼的檢錯能力e比最小碼距d0小1位；（2）2t+1≤d0，即碼的糾錯能力t的2倍比最小碼距d0小1位；（3）e

+t+1≤d0，即若碼同時糾t個錯并檢出e個錯誤，則e

+t比最小碼距d0小1位。以下說明：第11頁/共118頁（1）e

+1≤d0第12頁/共118頁（2）2t

+1≤d0第13頁/共118頁（3）t

+e+1≤d0第14頁/共118頁差錯控制編碼的效用

假設(shè):發(fā)送“0”的錯誤概率和發(fā)送“1”的錯誤概率相等，都等于P，且P<<1，則在碼長為n的碼組中恰好發(fā)生r個錯碼的概率為例如，當(dāng)碼長n＝7時，p=10-3則有P7(1)≈7p=7×10-3

；P7(2)≈21p2=2.1×10-5

；第15頁/共118頁P7(3)≈35p3=3.5×10-8?？梢?，采用差錯控制編碼，即使僅能糾正(或檢測)這種碼組中1—2個錯誤，也可以使誤碼率下降幾個數(shù)量級。這就表明，即使是較簡單的差錯控制編碼也具有較大實際應(yīng)用價值。第16頁/共118頁§9.3常用的簡單編碼1．奇偶監(jiān)督碼——奇偶監(jiān)督碼包括奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼。只有一位監(jiān)督位。在偶監(jiān)督碼中，監(jiān)督位使碼組中“l(fā)”的個數(shù)為偶數(shù)，即滿足下式條件在奇監(jiān)督碼中，監(jiān)督位使碼組中“l(fā)”的個數(shù)為奇數(shù)，即滿足下式條件第17頁/共118頁2．二維奇偶監(jiān)督碼——又稱方陣碼。每一行是奇偶監(jiān)督碼的一個碼組，若干碼組再按列排列成矩陣，每列增加一位監(jiān)督位。第18頁/共118頁二維奇偶監(jiān)督碼特點：可檢測偶數(shù)個錯誤適于檢測突發(fā)錯碼。不僅可檢錯，還可糾一些錯。檢錯能力強。第19頁/共118頁3．恒比碼——每個碼組均含有相同數(shù)目的“1”(和“0”)。應(yīng)用：電傳機傳輸漢字，每個漢字用4位阿拉伯?dāng)?shù)字表示。每個阿拉伯?dāng)?shù)字又用5位二進制符號構(gòu)成的碼組表示。每個碼組的長度為5位，其中恒有3個1，稱為5中取3恒比碼?？赡芫幊傻牟煌a組數(shù)等于從5中取3組合數(shù)＝30。30種許用碼組恰好可用來表示10個阿拉伯?dāng)?shù)字。第20頁/共118頁4．正反碼——一種簡單的能夠糾正錯碼的編碼。其中的監(jiān)督位數(shù)與信息位數(shù)相同，監(jiān)督碼元與信息碼元相同(是信息碼的重復(fù))或者相反(是信息碼的反碼)。由信息碼中“1”的個數(shù)而定。解碼方法：先將接收碼組中信息位和監(jiān)督值按位模2相加，產(chǎn)生校驗碼組。最后，觀察校驗碼組中“1”的個數(shù)，按表9—3進行判決及糾正可能發(fā)現(xiàn)的錯碼。第21頁/共118頁§9.4線性分組碼

從上節(jié)介紹的一些簡單編碼可以看出，每種編碼所依據(jù)的原理各不相同，而且是大不相同，其中奇偶監(jiān)督碼的編碼原理利用了代數(shù)關(guān)系式。我們把這類建立在代數(shù)學(xué)基礎(chǔ)上的編碼稱為代數(shù)碼。在代數(shù)碼中，常見的是線性碼。線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的，或者說，線性碼是按一組線性方程構(gòu)成的。本節(jié)將以漢明(Hamming)碼為例引入線性分組碼的一般原理。第22頁/共118頁回顧奇偶監(jiān)督碼在接收端解碼時，實際上就是在計算若S＝0，認為無錯；若S＝1，認為有錯。上式稱為監(jiān)督關(guān)系式，S稱為校正子。S只有兩種取值，只能代表有、無錯兩種信息，不能指出錯碼位置。如果監(jiān)督位增加一位，則增加一個監(jiān)督關(guān)系式。由于兩個校正子的可能值有4種組合：00，01，10，11，故能表示4種不同狀態(tài)。第23頁/共118頁若用其一種表示無錯，則其余3種就可能用來指示一位錯碼的3種不同位置。同理r個監(jiān)督關(guān)系式能指示一位錯碼的(2r-1)個可能位置。一般地，若碼長為n，信息位數(shù)為k，則監(jiān)督位數(shù)r=n-k。如果希望用r個監(jiān)督位構(gòu)造出r個監(jiān)督關(guān)系式來指示一位錯碼的n種可能位置，則要求

2r-1≥n，或者2r≥r+k+1第24頁/共118頁舉例說明如何構(gòu)造監(jiān)督關(guān)系式：設(shè)(n，k)分組碼中r=4。為了糾正一位錯碼，要求監(jiān)督拉數(shù)r≥3。若取r=3，則n=k+r=7。校正子與錯碼位置的對應(yīng)關(guān)系如表9—4規(guī)定(也可以另外規(guī)定)。S1S2S3錯碼位置S1S2S3錯碼位置001A0101A4010A1110A5100A2111A6011A3000無錯第25頁/共118頁由表可見，當(dāng)一錯碼在a2,a4，a5或a6時校正子S為1；否則S為0即構(gòu)成如下關(guān)系同理在發(fā)送端編碼時，信息位a6a5a4a3的值決定于穩(wěn)入信號，因此它們是隨機的。監(jiān)督值a2a1ao應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定．即監(jiān)督位應(yīng)使上三式中的值為零(表示編成的碼組中應(yīng)無錯碼)，由此得到方程組第26頁/共118頁由此解出給定信息位后，可直接按上式算出監(jiān)督位，其結(jié)果如表9—5所列。第27頁/共118頁信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111第28頁/共118頁

接收端收到每個碼組后，先按監(jiān)督方程計算出S1、S2、S3，再按表9—4判斷錯碼情況。例，接收0000011，可得：S1S2S3=011。由表9—4可知在a3位有錯碼。

(7，4)漢明碼：最小碼距d0=3糾一個錯碼或檢測兩個錯碼。編碼效率k/n=(2r-1-r)／(2r-1)=I-r／n。當(dāng)n很大時，則編碼效率接近1。第29頁/共118頁線性分組碼的—般原理。線性分組碼是指信息位和監(jiān)督位滿足一組線性方程的編碼。改寫為第30頁/共118頁(模2)簡記為或第31頁/共118頁稱為監(jiān)督矩陣H矩陣的各個行是線性無關(guān)的行數(shù)=監(jiān)督位數(shù)，列數(shù)=碼字長度典型陣第32頁/共118頁第33頁/共118頁轉(zhuǎn)置得第34頁/共118頁稱為生成矩陣第35頁/共118頁生成矩陣G的每一行都是一個碼組。例如，（參照前頁矩陣G）。利用生成矩陣，碼字再由得，第36頁/共118頁譯碼,若發(fā)送碼組為接收碼組為二者之差為其中E稱為錯誤圖樣。表示該位接收碼元無錯；表示該位接收碼元有錯。第37頁/共118頁

接收端譯碼時計算當(dāng)接收碼組無錯時．S等于零有錯但不超過檢錯能力時，S不等于零。在錯碼超過檢錯能力時，B變?yōu)榱硪辉S用碼組，仍能成立S等于零。這樣的錯碼是不可檢測的。S稱為校正子(伴隨式)。S只與E有關(guān)，而與A無關(guān)，意味著S與E有的線性變換關(guān)系，能與E一一對應(yīng)，可指示錯碼位置。第38頁/共118頁

線性碼重要性質(zhì)之一，是它具有封閉性。若：A1和A2是線性碼中的兩個許用碼組，則：(A1+A2)仍為其中的一個碼組。由封閉性，兩個碼組之間的距離必是另一碼組的重量。故碼的最小距離即是碼的最小重量(除全“0”碼組外)。線性碼又稱群碼，這是由于線性碼的各許用碼組構(gòu)成代數(shù)學(xué)中的群。第39頁/共118頁§9.5

循環(huán)碼9.5.1循環(huán)碼原理：在線性分組碼中，有一種重要的碼稱為循環(huán)碼。循環(huán)碼除了具有線性碼的一般性質(zhì)外．還具有循環(huán)性，即任一碼組循環(huán)一位(將最右端的碼元移至左端，或反之)以后，仍為該碼中的一個碼組。即若是許用碼組，則也是許用碼組。第40頁/共118頁循環(huán)碼舉例——(7,3)循環(huán)碼碼組信息位監(jiān)督位碼組信息位監(jiān)督位編號a6a5a4a3a2a1a0編號a6a5a4a3a2a1a00000000041001011100101115101110020101000611001013011100171110010第41頁/共118頁碼組的多項式表示——碼多項式。例如A=1100101A(x)=1x6+1x5+0x4+0x3+1x2+0x1+1x0=x6+x5+x2+1碼多項式表示具有線性的性質(zhì)第42頁/共118頁碼多項式的按模運算循環(huán)移位對應(yīng)的碼多項式如果規(guī)定xn=x0，即規(guī)定xn+1=0，則有第43頁/共118頁這種xn+1=0的規(guī)定，實質(zhì)上是一xn+1為模的運算。對于整數(shù)m,若可以表示為則稱m=p(模n)，或稱m與p是同余的。碼多項式也有類似的運算。多項式F(x)被n次多項式N(x)除，得到商式q(x)和一個次數(shù)小于n的余式R(x)，即

F(x)＝q(x)N(x)+R(x)則寫為F(x)＝R(x)(模N(x))第44頁/共118頁碼多項式系數(shù)仍按模2運算，即只取值0和1。例如于是，可以有由此可見為了使xn=1，只需做模xn+1的運算即可。例如：x4+x2+1=x2+x+1模x3+1第45頁/共118頁由前面的分析可知，若T(x)是碼多項式，則在模xn+1的運算條件下，xiT(x)仍然是碼多項式。

第46頁/共118頁2．循環(huán)碼的生成矩陣G

若能找到k個線性無關(guān)的碼組,就能構(gòu)成矩陣G。在循環(huán)碼中，一個(n，k)碼有2k個不同碼組，若用g(x)表示其中前(k-1)位皆為0的碼組，即

g(x)=0…1x…xk位n-k位則g(x)、xg(x)，x2g(x)，…，xk-1g(x)都是碼組，而且這k個碼組是線性無關(guān)的。因此可以用來構(gòu)成循環(huán)碼的生成矩陣G。

第47頁/共118頁第48頁/共118頁例表9—6的循環(huán)碼,唯一的一個(n-k)次碼多項式代表的碼組是0010111，相對應(yīng)的碼多項式為一旦確定了g(x)，則整個(n．k)循環(huán)碼就被確定了。因此,循環(huán)碼的生成矩陣G可以寫成第49頁/共118頁這個生成矩陣不是系統(tǒng)碼的生成矩陣，可以通過行變換，變換成系統(tǒng)碼的生成矩陣。g(x)＝x4+x2+x+1將此g(x)代入上式，得到第50頁/共118頁g(x)的性質(zhì)：g(x)必須是一個常數(shù)項a0=1；次數(shù)為(n-k)次；唯一的(n-k)次多項式；我們稱這唯一的g(x)為碼的生成多項式。g(x)是xn+1的因式（見后面分析）。第51頁/共118頁說明g(x)是xn+1的因式。因為任碼多項式T(x)都是g(x)的倍式，所以有

T(x)=h(x)g(x)g(x)本身也是一個碼組，其次數(shù)為n-k次。把它循環(huán)移位k次仍為一個碼組。所以xkg(x)是n次多項式，在模xn+1運算下，所以即第52頁/共118頁因為xkg(x)是n次的，所以Q(x)=1。所以所以即g(x)是xn+1的因式。這樣就可以通過對xn+1的因式分解得到g(x).第53頁/共118頁因為所有碼多項式T(x)都可被g(x)整除。所以非系統(tǒng)碼編碼：T(x)=m(x)g(x)系統(tǒng)碼編碼：用xn-k乘m(x)，即把m(x)左移n-k位；用xn-k除以g(x)，得余式r(x)；T(x)=xn-km(x)+r(x)9.5.2

循環(huán)碼的編、解碼方法第54頁/共118頁例：信息碼110，信息碼多項式m(x)=x2+x生成多項式g(x)=x4+x2+x+1即于是，編出碼字1100000+101=1100101第55頁/共118頁硬件實現(xiàn)——固定除式的多項式除法abcd○○○信息碼元輸入移存器反饋輸出mabcddf0000001111011110011101010100010100000101100001000000011校驗碼元第56頁/共118頁2．循環(huán)碼的解碼方法——檢錯解碼的要求有兩個：檢錯和糾錯。——碼多項式T(x)應(yīng)能被生成多項式g(x)整除。若接收碼組與發(fā)送碼組相同，即R(x)=T(x)，則接收碼組R(x)必定能被g(x)整除；若碼組在傳輸中發(fā)生錯誤，則R(x)除以g(x)時可能有余項，即有

R(x)/g(x)=Q(x)+r(x)/g(x)第57頁/共118頁檢錯電路見圖9-7(a)接收碼組緩沖移位寄存器除法電路反相與門重發(fā)指令輸出信息碼余式等于1時輸出1余式等于0時輸出0第58頁/共118頁2．循環(huán)碼的解碼方法——糾錯前提：每個可糾正的錯誤圖樣必須與伴隨式一一對應(yīng)。步驟：由接收多項式除以生成多項式得到余式r(x)；通過余式r(x)與錯誤圖樣的關(guān)系得到錯誤圖樣e(x)；從接收多項式中減去錯誤圖樣村e(x)。電路如下：第59頁/共118頁圖9-7(b)第60頁/共118頁假定接收碼組為10*O0101，其中右上角打*號者為錯碼。此碼組進入除法電路后，移位寄存器各級的狀態(tài)變化過程列于表9—7(b)。(見演示)輸入移存器輸出fabcde0000001111000*01110011010010000110100001010100100000011000000第61頁/共118頁9.5.3縮短循環(huán)碼通過縮短循環(huán)碼，可以滿足系統(tǒng)設(shè)計中，碼長、信息位和糾錯能力的不同要求。對于(n,k)循環(huán)碼，使前i(0<i<k)個信息位為零可得到有2k-i個碼組的集合，然后從這些碼組中刪去這i個零信息位，得到一種新的(r-i，k-i)的線性碼，稱為縮短循環(huán)碼。縮短循環(huán)碼與產(chǎn)生該碼的原循環(huán)碼至少具有相同的糾錯能力。縮短循環(huán)碼的編碼和譯碼可用原循環(huán)碼使用的電路完成。第62頁/共118頁例：若要求構(gòu)造一個能夠糾正一位錯誤的(13，9)碼，則可以由(15，11)漢明碼選出前面兩個信息位均為零的碼組。然后在發(fā)送時，這兩個零信息不發(fā)送，即發(fā)送的是(13，9)縮短循環(huán)碼。因校驗位數(shù)相同，(13，9)碼與(15，11)循環(huán)碼具有相同的糾錯能力。第63頁/共118頁9.5.4BCH碼BCH碼是一類糾正多個隨機錯誤的特殊的循環(huán)碼。特點是可以根據(jù)給定的糾錯能力，找出生成多項式。BCH碼分兩類：本原BCH碼和非本原BCH碼。本原BCH碼的碼長為n=2m-1(M≥3)，生成多項式g(x)中含有最高次數(shù)為m次的本原多項式；非本原BCH碼的碼長n是2m-1的一個因子，它的生成多項式中不含有最高次數(shù)為m的本原多項式。第64頁/共118頁對于正整數(shù)m(M≥3)和t(t≥2)必存在有下列參數(shù)的二進制BCH碼：碼長n=2m-1，監(jiān)督位數(shù)r≤mt，能糾正所有的小于或等于t個隨機錯誤的BCH碼。BCH碼生成多項式

g(x)=LCM[m1(x)，m2(x)，…，m2t-1(x)]式中t——可糾正的錯誤個數(shù)；mi(x)——最小多項式;LCM()——指取括號內(nèi)所有多項式的最小公倍式.第65頁/共118頁查表法得到生成多項式，用八進制數(shù)表示。例如當(dāng)n=7,k=4,t=1g=(13)8意指

g=(001011)2g(x)=x3+x+1n=3ktg(x)117n=7ktg(x)41131377表9—8（部分）第66頁/共118頁R-S碼是一類具有很強糾措能力的多進制BCH碼。伽羅華域(即有限域)：對于有限個符號，若符號的數(shù)目是一素數(shù)的冪，可以定義有加法和乘法，則構(gòu)成符號域為有限域；若它是2m個符號的域．則稱之為伽羅華域GF(2m).例如，兩個符號0、1，定義有模2加法和模2乘法，即0+0=0，0+1=1，1+1=0；0·0=0，0·1=1，1·1＝1，則稱之為二元域，也是伽羅華域。9.5.5里德-索羅門碼（R-S碼）第67頁/共118頁從兩個符號0和1及一個m次多項式p(x)開始，并引入一個新符號α

，設(shè)p(α)=0。若適當(dāng)?shù)剡x擇p(x)．就可得到α的各次冪，一直到2m-2次冪，都不相同，并且αm-1=1。這樣一來，構(gòu)成GF(2m)的所有元素。域中每個非零元素還可以用上面元素的和來表示。例如，m=4和p(x)=x4+x+1，則第68頁/共118頁得到GF(24)的所有元素，詳見表9--10。01αα2

α3

α4=α+1

α5=α(α+1)=α2+α

α6=α(α2+α)=α3+α2第69頁/共118頁α7=α(α3+α2)=α3+α2=α3+α+1α8=α(α3+α+1)=α4+α2+1=α2+1α9=α(α2+1)=α3+αα10=α(α3+α)=α2+α+1

α11=α(α2+α+1)=α3+α2+α

α12=α(α3+α2+α)=α3+α2+α+1

α13=α(α3+α2+α+1)=α3+α2+1

α14=α(α3+α2+1)=α3+1第70頁/共118頁R-S碼是q進制BCH碼的子類。具有如下的參數(shù)：碼長：n=q-1符號監(jiān)督位數(shù)：r=2t符號糾錯位數(shù)：t符號生成多項式：每個碼元都是q進制的，通常令q=2m，則每個q進制碼元都可以表示為m位二進制碼元，于是碼長mn位，監(jiān)督位數(shù)mr位，信息位數(shù)：mn-mr位。第71頁/共118頁R-S碼應(yīng)用：由于采用多進制，所以對于多進制調(diào)制是自然和方便的編碼手段;因為RS碼能夠糾正t個q位二進制碼，即對以糾t個連續(xù)的突發(fā)性二進制錯誤,所以適合衰落信道應(yīng)用;RS碼可應(yīng)用在計算機存儲系統(tǒng)中．以克服系統(tǒng)的差錯。第72頁/共118頁卷積編碼則把k比特信息段編成n比特的碼組，但所編的n長碼組不僅同當(dāng)前的k比特信息段有關(guān)聯(lián)，而且還同前面的(N-1)個信息段有關(guān)聯(lián)，人們常稱這N為該卷積碼的約束長度。一般來說，對于卷積碼，k和n是較小的整數(shù),常把卷積碼記作(n,k,N)卷積碼，它的編碼效率為R=k/n。

§9.6卷積碼第73頁/共118頁9．6．1卷積碼的圖形描述(3,1,3)卷積碼編碼器第74頁/共118頁編碼器的輸入和輸出第75頁/共118頁樹狀圖第76頁/共118頁狀態(tài)圖第77頁/共118頁狀態(tài)圖第78頁/共118頁網(wǎng)格圖第79頁/共118頁網(wǎng)格圖特點：有2N-1種狀態(tài)；對于k個輸入信息比特，相應(yīng)出現(xiàn)有2k條支路；碼樹中的上支路用實線表示，下支路用虛線表示：支路上標注的碼元為輸出比特；從第N個節(jié)點開始，圖形開始重復(fù)，且完全相同。第80頁/共118頁

例9--1(3,1,3)編碼器，起始狀態(tài)為a，輸入序列為1101011，求輸出序列和相應(yīng)狀態(tài)變化路徑。解：由卷積碼的網(wǎng)格圖，可找出編碼時網(wǎng)格圖中的編碼路徑如圖9—13所示，由此即可得到輸出序列。為第81頁/共118頁第82頁/共118頁9.6.2卷積碼的解析描述1．生成矩陣卷積碼是一種線性碼。一個線性碼完全由一個監(jiān)督矩陣H或生成矩陣G所確定。生成矩陣G

輸入第一個信息比特m1時，y1,1=m1；y21=m1；y31=m1。輸入第二個信息比特m2時，y1,2=m2；y22=m2；y32=m1+m2。第83頁/共118頁輸入第j個信息比特mj時，

y1j=mj；

y2j=mj+mj-2；

y3j=mj+mj-1+mj-2上式可寫成矩陣形式

[mj+mj-1+mj-2]A=[y1jy2jy3j]第84頁/共118頁其中生成矩陣為在過渡時刻

[m100]T1=[y11y21y31][m1m20]T2=[y12y22y32]其中第85頁/共118頁輸出矩陣與輸入矩陣的關(guān)系有

Y=MG第86頁/共118頁111001011111001011111001011111001011111001011111001

上面矩陣空白處均為0元素。該生成矩陣是半無限矩陣。第87頁/共118頁2.多項式描述例如：輸入序列1101110…可表示為

m(x)=1+x+x3+x4+x5+…連接關(guān)系表示為

g1(x)=1g2(x)=1+x2g3(x)=1+x+x2編碼輸出為

y1(x)=m(x)g1(x)=1+x+x3+x4+x5+…y2(x)=m(x)g2(x)=(1+x+x3+x4+x5+…)(1+x2)第88頁/共118頁=1+x+x3+x4+x5+…+x2+x3+x5+x7+…=1+x+x2+x4+x7…y3(x)=(1+x+x3+x4+x5+…)(1+x+x2)=1+x+x3+x4+x5+…x+x2+x4+x5+x6+…x2+x3+x5+x6+x7+…=1+x5+x7+…對應(yīng)的序列為第89頁/共118頁y1=11011100…；

y2=11101001…

y3=10000101…

總的輸出序列為

Y=[y11,y21,y31,y12,y22,y32,…

=111,110,010,100,110,101,000,011,…結(jié)果與網(wǎng)格圖是一樣的。第90頁/共118頁卷積碼編碼器的一般結(jié)構(gòu)第91頁/共118頁9.6.3卷積碼譯碼卷積碼的譯碼方法有兩類：一類是大數(shù)邏輯譯碼，又稱門限譯碼：另一類是概率譯碼。概率譯碼又分為維特比譯碼和序列譯碼兩種。門限譯碼方法是以分組碼理論為基礎(chǔ)的其譯碼設(shè)備簡單，速度快，但其誤碼性能要比概率譯碼法差。下面只介紹維特比譯碼。第92頁/共118頁9.6.3維特比譯碼維特比譯碼算法，簡稱VB算法。維特比(viterbi)譯碼和序列譯碼都屬于概率譯碼。當(dāng)卷積碼的約束長度不太大時，與序列譯碼相比，維持比譯碼器比較簡單，計算速度更快。VB算法在前向糾錯系統(tǒng)中用得較多，在衛(wèi)星通信中已被采用作為標準技術(shù)。第93頁/共118頁概率譯碼的基本想法是：把已接收序列與所有可能的發(fā)送序列做比較，選擇其中碼距最小的一個序列作為發(fā)送序列。如果發(fā)送L組信息比特，對于(n,k)卷積碼來說，可能發(fā)送的序列有2kL個，計算機或譯碼器需存儲這些序列并進行比較，以找到碼距最小的那個序列。當(dāng)傳信率和信息組數(shù)人較大時，使得澤碼器難以實現(xiàn)。第94頁/共118頁VB算法則對上述概率譯碼(又稱最大似然譯碼)做了簡化，使其成為一種實用的譯碼算法。它并不是在網(wǎng)格圖上一次比較所有可能的2kL條路徑(序列)，而是接收一段，計算和比較一段，選擇一段有最大似然可能的碼段。從而達到整個碼序列是一個有最大似然值的序列。以下以（2,1,3)卷積碼為例說明：第95頁/共118頁第96頁/共118頁第97頁/共118頁設(shè)輸入信息數(shù)目L=5，所以畫有L+N=8個時間單位。編碼器從a狀態(tài)開始工作。該網(wǎng)格圖的每一條路徑都對應(yīng)著不同的輸入信息序列。由于所有的可能輸入信息序列共有2kL=32個.第98頁/共118頁設(shè)輸入編碼器的信息序列為(11011000)，則由編碼器輸出的序列

y＝(1101000010,11100)，編碼器的狀態(tài)轉(zhuǎn)移路線為abdcbdca。若收到的序列為R=0101011001011100，對照網(wǎng)格圖來說明維特比譯碼的方法。前3步輸入R=010101；根據(jù)不同輸入信息，編碼器的輸出序列以及它們與接收序列的距離見下表第99頁/共118頁R=010101信息編碼路徑距離000000000aaaa3001000011aaab3010001110aabc4011001101aabd2100111011abca4101111000abcb4110110101abdc1111110110abdd3前3步對應(yīng)網(wǎng)格圖幸存路徑，如下頁第100頁/共118頁對應(yīng)4條幸存路徑的序列分別為：

a-a-a-a——000000a-a-a-b——000011a-b-d-c——110101a-a-b-d——001101.第101頁/共118頁到第5步的幸存路徑和對應(yīng)的序列分別為：

a-a-b-d-d-c——0011011001.a-b-d-c-a-a——1101011100a-b-d-c-a-b——1101011111a-b-d-c-b-d——1101011101第102頁/共118頁到第8步的幸存路徑和對應(yīng)的序列分別為：

a-----b-----d-----c-----b-----d-----c-----a----a110101,0001011100對應(yīng)信息11011000與發(fā)送信息相同。對比接收0*101011*001011100糾正了兩個錯誤。第103頁/共118頁總結(jié)與復(fù)習(xí)第一章緒論通信系統(tǒng)的基本組成模型；模擬與數(shù)字通信系統(tǒng)組成；通信系統(tǒng)分類；數(shù)字通信系統(tǒng)優(yōu)點；模擬與數(shù)字通信系統(tǒng)的性能指標；離散消息的信息量和平均信息量；例題：例1.4.1，習(xí)題2、4、6、7第104頁/共118頁第二章隨機信號分析平穩(wěn)隨機過程的定義、性質(zhì)；什么是廣義平穩(wěn)隨機過程？平穩(wěn)隨機過程的自相關(guān)函數(shù)與功率譜密度如何定義，有何性質(zhì)？平穩(wěn)隨機過程通過線性系統(tǒng)后，均值、自相關(guān)與方差、功率譜密度有何關(guān)系？第105頁/共118頁什么是高斯噪聲？什么是高斯白噪聲？什么是窄帶高斯噪聲？窄帶高斯噪聲的幅度和相位服從什么分布？窄帶高斯噪聲的同相分量和正交分量服從什么分布？習(xí)題