第五章 信道編碼2

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