第五章 信道編碼2

第五章信道編碼,信道編碼的基本概念和基本原理線性分組碼循環(huán)碼、卷積碼和秩距離碼突發(fā)錯誤的糾正級連碼、交織碼及TCM碼糾錯碼的應用,編碼信道：包括信道編碼器、實際信道、信道譯碼器。該模型是研究信道糾錯編碼和譯碼的模型，集中研究通信可靠性。通信可靠性問題：消息通過信道傳輸的時候，如何選擇編碼方案來減少差錯。首先與信道統(tǒng)計特性有關，其次與編碼方法、譯碼方法也有關系。,第一節(jié)信道編碼的基本概念和基本原理,信道是信號從信源傳送到信宿的通路。由于信道有干擾，使得傳送的數據流(碼流)中產生誤碼。誤碼的處理技術有糾錯、交織、線性內插等。信道編碼的目的是提高信息傳輸或通信的可靠性。信道編碼的任務是降低誤碼率，使系統(tǒng)具有一定的糾錯能力和抗干擾能力，提高數據傳輸效率。信道編碼的過程是在源數據碼流中加插一些碼元，達到在接收端進行檢錯和糾錯的目的。在帶寬固定的信道中，總的傳送碼率是固定的，由于信道編碼增加了數據量，其結果只能是以降低傳送有用信息碼率為代價了。,一、信道編碼概念,目的：降低錯誤譯碼概率PE。對象：信息序列（設碼元間彼此無關且等概出現）。,方法：在傳輸的信息碼之中按一定規(guī)律產生一些附加數字，經信道傳輸，在傳輸中若碼字出現錯誤，收端能利用編碼規(guī)律發(fā)現碼的內在相關性受到破壞，從而按一定的譯碼規(guī)則自動糾正或發(fā)現錯誤，降低誤碼率。,一、信道編碼概念,實質：在保持一定傳輸信息速率條件下，通過增加一定的碼元多余度，使輸出的碼字具有特定的相關性，從而使收端易于發(fā)現或糾正由于信道噪聲而引起的傳輸錯誤。,q=rk個k維矢量,信息序列,許用碼組,編碼過程,M,C,校驗元,信息序列,碼字,編碼規(guī)則,rk個,傳輸模式,PE信道傳輸特征PE譯碼方法,C2kCiC2n-1,許用碼組,禁用碼組,不可檢出錯誤傳輸,正確傳輸,可檢出錯誤傳輸,二、信道編碼的基本原理（檢錯、糾錯原理）,尋找一種編碼方法，使所加的監(jiān)督碼元最少，而檢錯糾錯能力又高，且便于實現。,理論基礎：香農第二定理對于一個給定的有擾信道，如信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息，則一定存在一種編碼方法，使編碼錯誤概率p隨碼長n的增加，按指數下降到任意小的值。也就是說，可以通過編碼使通信過程實際上不發(fā)生錯誤，或使錯誤控制在允許數值之下。即：,信息傳輸率,E(R),隨機編碼指數,碼長,Pexp-nE(R),E(R)意義：n給定，則最佳編碼的P上界既定。,適用于DMC，有記憶信道及連續(xù)信道;,香農第二定理說明：,PE0，可靠編碼條件：,有噪信道編碼逆定理設離散無記憶信道X，p(y|x)，Y的信道容量為C，R是信息傳輸率，當RC時，則無論碼長N多長，總找不到一種編碼，使譯碼的平均錯誤概率任意小。,表述二、設某信道有r個輸入符號，s個輸出符號，信道容量為C。只要碼長N足夠長，總可以在輸入的rN個符號的集合中找到M（M2N(C-)，為任意小的正數）個碼字，分別代表M個等可能性的消息，組成一個碼以及相應的譯碼規(guī)則，使信道輸出端的平均錯誤譯碼概率PE達到任意小。,1)差錯類型1隨機錯誤:數據流中發(fā)生的錯誤彼此無關,表現為錯誤之間的無相關性.2突發(fā)錯誤:數據流中一個錯誤的發(fā)生,帶來一連串錯誤的發(fā)生,表現為誤錯之間的相關性.2)差錯控制的途徑1增加信道容量措施擴展帶寬、提高發(fā)送功率、降低噪聲2編碼措施減小碼率、增加碼長、交織器、糾錯碼3傳輸方式措施重復發(fā)送、反饋重發(fā)、多進制信號,三、差錯控制,需要雙向信道，和前向信道有相同的通信容。引入較大的停頓（不實時）。可以糾正任何錯誤。,1反饋檢驗法(IRQ),3)差錯控制的分類,2檢錯重發(fā)法（ARQ）,自動請求重發(fā)也需要反向信道，但容量可以降低，也會引入停頓,3前向糾錯（FEC）,不需要雙向信道不會引入停頓靠糾錯編碼,3混合糾錯檢錯（HEC）,4)差錯控制編碼的基本原理,如用三位二進制編碼來代表八個字母000A100E001B101F010C110G011D111H不管哪一位發(fā)生錯誤，都會使傳輸字母錯誤如用三位字母傳四個字母000A011B101C110D發(fā)生一位錯誤，準用碼字將變成禁用碼字，接收端就能知道出錯，但是不能糾錯。,如用三位字母傳二個字母000A111B檢三個錯誤，糾正一個錯誤。大數法則糾錯。結論具有檢錯或糾錯的碼組，其所用的比特數必須大于信息碼組原來的比特數引入余度。,5）、檢錯、糾錯能力,碼重(weight)一個碼組中“1”的數目碼距(distance)兩個碼組之間對應位置上1、0不同的位數，又叫漢明(Hamming)距。10110碼重：3011002距離：3,為檢查出個錯誤，要求最小碼距為為糾正個錯誤，要求最小碼距為為糾正個錯誤，同時檢查出個錯誤，要求最小碼距為糾正個錯誤和p個刪除，要求最小碼距為：,檢錯、糾錯能力,按功能分檢錯碼糾錯碼糾刪碼（發(fā)現不可糾正的錯誤時，可發(fā)出指示或刪除）按信息碼元和監(jiān)督碼元之間的校驗關系分線性碼非線性碼按信息碼元和監(jiān)督碼元之間的約束方式分分組碼卷積碼,6）、差錯控制編碼分類,卷積碼,非線性碼,線性碼,糾錯碼,分組碼,循環(huán)碼,非循環(huán)碼,糾隨機錯誤碼,糾突發(fā)錯誤碼,糾隨機和突發(fā)錯誤碼,糾同步錯誤碼,糾錯碼分類,第二節(jié)線性分組碼,表示：(n,k)n:幀（組）長k/n:編碼效率特點監(jiān)督碼只用來監(jiān)督本幀中的信息位分類線性碼信息碼與監(jiān)督碼之間為線性關系非線性碼不存在線性關系,一、基本概念,分組碼的監(jiān)督方程矩陣形式,監(jiān)督矩陣H矩陣稱為典型形式，各行一定是線性無關的。而一個非典型形式的經過初等變換運算可以化成典型形式，通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關系。,生成矩陣，通過監(jiān)督矩陣可以得到生成碼組。如果輸入碼組為A=0011,編碼器輸出碼字為:C=AG,由這種方式得到的生成矩陣稱為典型生成矩陣，由它產生的分組碼必定為系統(tǒng)碼，也就是信息碼字保持不變，監(jiān)督位附加其后，每行一定是線性無關的，每行都是一個生成碼組。,定理：設二元線性分組碼CI是由監(jiān)督矩陣H所定義的，若X和Y為其中的任意兩個碼字，則X+Y也是CI中的一個碼字。線性碼的封閉性,對偶碼：以G作監(jiān)督矩陣，以H為生成矩陣，得到另一個碼CJ（n，n-k）線性碼。CJ為原碼CI的對偶碼。它們的碼矢彼此正交，兩個子空間是互為零化空間。,縮短碼：將分組碼最左邊i位為0的消息和對應的碼字挑選出來，把最左邊的0刪去，構成（n-i，k-i）線性分組碼。糾錯檢錯能力與原碼相同。,縮短碼的監(jiān)督矩陣：（n，k）一致監(jiān)督矩陣刪去最左邊一列?？s短碼的生成矩陣：（n，k）生成矩陣刪去最左邊一列和最上面的一行。,二、漢明碼能糾正單個錯誤的線性分組碼,漢明碼的監(jiān)督矩陣H的列為所有非零的r維向量組成，一旦r給定，就可以構造出具體的（n，k）漢明碼。,例1：構造一個二元的（7，4，3）漢明碼。,分析：r=n-k=3,除0以外的所有2r個元素構成矩陣H的列。,截短漢明碼,(n,k)(n-x,k-x)如(15,11)(12,8)監(jiān)督矩陣H是將原H的前3列去掉截短漢明碼的最小碼距至少和原來碼的碼距相同，因為監(jiān)督位沒有變。,能糾t個錯誤的(n,k)應滿足取等號時為完備碼不同結構的線性碼其糾錯能力不同，能力和dmin有關，dmin越大越好。,如果在漢明碼基礎上，再加上一位對所有碼字進行校驗的監(jiān)督位監(jiān)督碼字由r位增加到r+1位信息位不變碼長碼結構糾1位錯，檢測2位錯如（8，4），（16，11）,擴展?jié)h明碼,擴展?jié)h明碼的監(jiān)督矩陣,編碼器的實現上例m=(m1m2m3m4)m1,m2,m3,m40,1Ci=mGCi=(c1c2c3c4c5c6c7)=(m1m2m3m4m1+m2+m3m2+m3+m4m1+m2+m4)m1c1m2c2m3c3m4c4c5c6c7,+,+,+,三、線性分組碼的編碼,根據線性碼的監(jiān)督矩陣或生成矩陣將長為k的信息組變換成長為n（nk）的碼字。,四、線性分組碼的譯碼,當給定接收碼字R時，譯碼器的錯誤譯碼概率表示經過譯碼后平均接受到一個碼字所產生的錯誤大小。平均錯誤概率：,1、最大似然譯碼1)編碼譯碼過程源數據碼流劃分為信息組m,編碼譯碼過程如下:信息組m碼字Ci接收字RCi的估值干擾2)譯碼發(fā)送碼字Ci,接收字R;譯碼器根據編碼規(guī)則和信道特性,對接收碼字R作出判決,此過程稱為譯碼.譯碼器的基本任務就是根據一套譯碼規(guī)則或算法,由接收字R給出與發(fā)送信息組m的最好估計值.由于m與C之間是一一對應的,這就等價于譯碼器根據R對C的估計.,編碼器,譯碼器,信道,3)最佳譯碼在已知接收字R的條件下,找出可能性最大的發(fā)送碼字Ci作為譯碼的估值,令這種譯碼方法叫做最佳譯碼或最大后驗譯碼(MAP)根據Bayes公式式中p(Ci)發(fā)送碼字Ci的概率p(R)接收字R的概率p(R|Ci)先驗概率,如果以下條件成立碼C中的qk個碼字以等概率發(fā)送,p(Ci)=1/qkp(R)對于任何R都有相同的值,p(R)=1/qn則后驗概率p(Ci|R)最大,等同于先驗概率p(R|Ci)最大.4)最大似然譯碼在已知接收字R的條件下,使得先驗概率最大的譯碼方法稱為最大似然譯碼對于無記憶信道,若Ci=(ci1,ci2,cin),R=(r1,r2,rn)則最大似然函數,對數似然函數5)最小距離譯碼對于BSC信道,最大似然譯碼可以簡化為最小距離譯碼.碼C中任一碼字Ci與R的距離為d,則d表示Ci在BSC信道傳輸過程中碼元傳錯的個數.因此此時的似然函數,結論(1-p)n是常數,而p/(1-p)1)的余數相同;或稱為a和b對于模m同余.最小非負剩余:a=r(modm);0rn-k+1，則（n-k）循環(huán)碼不能檢測概率為2-（n-k）（能檢測的概率為1-2-（n-k）,5循環(huán)碼的伴隨多項式：,假設發(fā)送的碼多項式C(x)和錯誤圖樣多項式e(x)以及接收的碼多項式R(x)分別為：,則對于加性信道有：R(x)=C(x)+e(x)設g(x)為碼的生成多項式，由于碼字多項式C(x)能被g(x)除盡，故有：R(x)modg(x)=e(x)modg(x),定義伴隨多項式為：S(x)=e(x)modg(x),根據伴隨式的定義，若無錯誤傳輸，則S(x)=0，否則S(x)0，由此可實現循環(huán)碼的檢錯。因為g(x)的次數為n-k，e(x)的次數為n-1，所以伴隨式的最高次數為n-k-1，那么S(x)共有n-k項，故有2n-k種可能的伴隨式。若滿足2n-kn+1，則循環(huán)碼具有糾錯能力。,例7：前例中的（7，3）循環(huán)碼，若接收到的碼字為1100100，判斷是否為許用碼字。,解：接收碼字1100100碼多項式為：R(x)=x6+x5+x2，g(x)=x4+x2+x+1由伴隨式S(x)=R(x)modg(x)=e(x)modg(x)，有S(x)=x6+x5+x2mod(x4+x2+x+1)=1S(x)0，該碼字不是（7，3）循環(huán)碼的許用碼字。,6循環(huán)碼的編碼器,步驟：用xn-k乘以信息多項式M(x)。用g(x)除以xn-kM(x)得到余式b(x)。作碼字b(x)+xn-kM(x)多項式。(7,4)系統(tǒng)循環(huán)碼為例:u=(1001)即,7循環(huán)碼的譯碼器,譯碼三步伴隨式S的計算由S得到錯誤圖樣糾正,生成多項式g(x)去除接收碼字R(x),校正子S的計算,5.5卷積碼(連環(huán)碼),在分組碼中,任何特定的時間單位內編碼器所產生的n個碼元的碼組,僅取決于該時間單位內k個消息位.存在著另一種碼,由編碼器在特定的時間內所產生的碼元不但取決于這個特定時間段內進入的信息組,而且也與前面的時間段內的信息組有關,這種碼稱為卷積碼.卷積碼的編碼可用移位寄存器來完成,卷積碼有多種描述方法，分為兩類解析描述法：生成矩陣法，離散卷積法，生成多項式法。解析法多用于編碼。圖形描述法：包括狀態(tài)圖、數圖、網格圖等。譯碼采用圖形法，尤其是網格圖。,一、定義：對于任一給定時刻，編碼器的一個輸出碼字不僅與該時刻的當前輸入碼字有關，還與編碼器的移位寄存器中存儲的前面m個輸入信息碼字有關。因此卷積碼記為(n0,k0,m0)卷積碼。n0為輸出的每個碼字的位數；k0為輸入的每個信息碼字的位數；m0為移位寄存器中存儲的信息碼字個數（級連的移位寄存器個數）,定義：m0為卷積碼的記憶長度。(m0+1)為卷積碼的碼字約束長度，相應的比特（碼元）約束長度為(m0+1)n0。卷積碼的碼率為R=k0/n0，它也表示卷積碼的編碼效率。,卷積碼可以是線性碼，但不是分組碼，卷積碼是有記憶的編碼,例8：給出一個（3，2，1）卷積碼編碼器的原理圖,該編碼器由2個移位寄存器構成。編碼器每個并行輸入一個2位信息碼字：則并行輸出一個3位卷積碼字：Pi為監(jiān)督元，有：可見，卷積碼當前碼字的監(jiān)督元不僅與當前輸入的信息元有關，還與前次輸入的2個信息碼元有關。,二、卷積碼的生成序列卷積碼的生成序列設卷積碼編碼器輸入碼序列（待編碼的信息序列）為Uu0(1)u0(2)u0（k0）u1(1)u1(2)u1(k0)us(1)us(2)us(k0)編碼器輸出碼序列為Cc0(1)c0(2)c0(n0)c1(1)c1(2)c1(n0)cs(1)cs(2)cs(n0)則編碼器輸出碼序列中任一子碼可以由如下卷積關系給出：,gt(i,j)為非系統(tǒng)卷積碼的生成序列,系統(tǒng)碼的生成矩陣系統(tǒng)卷積碼序列中，對應于前k0位，生成序列g(i,j)中有k0k0個生成序列是固定的，即:,（i，jk0）,對應后(n0-k0)個監(jiān)督位，k0(n0-k0)個生成序列需要給定,以便確定每個子碼中n0-k0個監(jiān)督元,則碼字:,g(i,j)為系統(tǒng)卷積碼的生成序列,例9：（3，1，2）系統(tǒng)卷積碼的生成序列為：,則其任一碼字為：,三、卷積碼的生成矩陣和監(jiān)督矩陣卷積碼的生成矩陣上例中,假設輸入為：U=(u1,u2,u3,),則輸出為：C=(u1u1u1,u2u2u2,u3u3u3+u1,u4u4u4+u2),寫成矩陣形式：C=UG,卷積碼的基本生成矩陣。,生成矩陣可以改寫為：,Ik0為k0k0階單位矩陣0為k0k0階全0方陣pl為k0(n0-k0)階矩陣。,考慮一個約束長度內的碼序列：U=u0u1u2um0得到卷積碼的初始截短碼組C：C=c0c1c2cm0,截短碼組的生成矩陣:g=Ik0p00p10pm0,例10：（3，1，2）系統(tǒng)卷積碼的生成序列為：,卷積碼的監(jiān)督矩陣(n0，k0，m0)碼的基本監(jiān)督矩陣為：,式中：h(n0-k0)n0N階矩陣。(n0，k0，m0)碼的監(jiān)督矩陣為,式中：(n0-k0)Nn0N階矩陣。,(n0，k0，m0)碼的監(jiān)督矩陣為,【例512】設(3，1，2)系統(tǒng)碼的生成序列為g(1,1)1g(1,2)g0(1,2),g1(1,2),g2(1,2)g(1,3)g0(1,3),g1(1,3),g2(1,3)求該碼的監(jiān)督矩陣。由公式式得(3，1，2)碼的監(jiān)督矩陣