第5講 信道編碼：基本概念、線性分組碼

信道編碼例如：假設(shè)要傳送A、B兩個消息編碼一：消息A----“0”；消息B----“1”若產(chǎn)生錯碼（“0”錯成“1”或“1”錯成“0”）收端無法發(fā)現(xiàn)，該編碼無檢錯糾錯能力此時的編碼沒有冗余編碼二：消息A----“00”；消息B----“11”若一位產(chǎn)生錯碼，變成“01”或“10”，因“01”“10”為禁用碼組，收端可發(fā)現(xiàn)有錯，但無法確定錯碼位置，不能糾正，增加一位冗余后具有檢出一位錯碼的能力編碼三：消息A----“000”；消息B----“111”傳輸中產(chǎn)生一位或是兩位錯碼，都將變成禁用碼組，具有檢出兩位錯碼的能力在產(chǎn)生一位錯碼情況下，收端可根據(jù)“大數(shù)”法則進(jìn)行正確判決，能夠糾正這一位錯碼，該編碼具有糾正一位錯碼的能力在產(chǎn)生兩位錯碼情況下，只具有檢錯能力這表明增加兩位冗余碼元后碼具有檢出兩位錯碼及糾正一位錯碼的能力上述編碼方法被稱為重復(fù)碼，記為(n,1)，編碼方法：把每個信息比特u重復(fù)n遍形成一個碼組c=(u,u,…,u)譯碼方法：若譯碼器收到的一個n個比特碼組y=(yn-1,yn-2,…,y0

)，判決碼組y中比特“1”和“0”的個數(shù)：1）若比特“1”的個數(shù)多則判決發(fā)送的“1”碼；2）若比特“0”的個數(shù)多則判決發(fā)送的“0”碼仍然出錯的概率（其中p為信道誤碼率）：n表示碼組長度，1表示信息碼元的個數(shù)信源編碼信道編碼發(fā)送濾波器接收濾波器信道譯碼信源解碼調(diào)制器解調(diào)器信源信道信宿信道編碼的相關(guān)概念：碼重、碼距等簡單的信道編碼漢明碼循環(huán)碼卷積碼原因：在數(shù)字信號的傳輸過程中，實際信道不理想，存在噪聲和干擾，導(dǎo)致接收端的誤判，產(chǎn)生差錯控制差錯的方法：1）合理的設(shè)計基帶信號；2）選擇調(diào)制、解調(diào)方式；3）均衡技術(shù)；4）增大發(fā)送功率在此基礎(chǔ)之上再采用信道編碼技術(shù)控制差錯信道編碼的目的添加冗余位信道編碼：1）保持信息的位數(shù)不變的情況下，采用增加碼長的方法降低誤碼率2）基本思想：通過對信息碼元序列作某種變換：使原來彼此相互獨立，沒有關(guān)聯(lián)的信息碼元序列，經(jīng)過這種變換后，產(chǎn)生某種規(guī)律性或相關(guān)性；在接收端可根據(jù)這種規(guī)律性來檢查，或者糾正傳輸序列中的差錯3）實現(xiàn)：發(fā)送端按照某種規(guī)則在信息序列上附加監(jiān)督碼元，接收端則按照同一規(guī)則檢查兩者間關(guān)系信源編碼：是指將信源中多余的信息除去，即降低冗余度，以提高傳輸?shù)男?，即有效性編碼1）去除冗余2）提高傳輸速率信道編碼：為了對抗信道中的噪音和衰減，通過增加冗余，來提高抗干擾能力以及糾錯能力，即可靠性編碼1）添加冗余2）降低差錯率：犧牲通信的有效性（信息傳輸速率）來提高可靠性因此信道編碼又可稱為差錯控制編碼按照差錯的類型可將信道分為：1）獨立隨機差錯信道差錯隨機出現(xiàn)，且相互獨立，主要有高斯白噪聲引起2）突發(fā)差錯信道信道傳輸?shù)牟焕硐?，存在比較大的脈沖干擾導(dǎo)致差錯成串出現(xiàn)信道中差錯的種類差錯控制方式—檢錯重發(fā)能夠發(fā)現(xiàn)錯誤的碼判決信號發(fā)收檢錯重發(fā)（ARQ）接收端按一定規(guī)則對收到的碼組進(jìn)行有無錯誤的判別。若發(fā)現(xiàn)有錯，則通知發(fā)送端重發(fā)，直到正確收到為止具體實現(xiàn)時，通常有3種形式2發(fā)送端：接收端：133124ACKACKNAK發(fā)現(xiàn)錯誤(a)停止等待重發(fā)TiTw1）如果未發(fā)現(xiàn)錯誤，則發(fā)回ACK信號給發(fā)送端，發(fā)送端收到ACK信號再發(fā)下一個碼組2）若檢測到錯誤，則發(fā)回NAK信號，發(fā)送端收到NAK信號后重發(fā)前一碼組，并再次等候ACK信號或NAK信號發(fā)送端：接收端：1234562341034562345678956789發(fā)現(xiàn)錯誤NAK從碼組2開始重發(fā)(b)返回重發(fā)1）不停地送出一個個連續(xù)碼組，不再等候收端返回的ACK信號，收到到NAK則開始重發(fā)2）N的大小取決于信號傳遞及處理所帶來的延時發(fā)送端：接收端：12345627812345627899發(fā)現(xiàn)錯誤NAK重發(fā)碼組2(c)選擇重發(fā)與返回重發(fā)不同的是，發(fā)端并不重發(fā)錯誤碼組后的所有碼組，而只重發(fā)有錯的那個碼組能夠糾正錯誤的碼發(fā)收前向糾錯（FEC）發(fā)送端將信息序列編碼成能夠糾正錯誤的碼，接收端根據(jù)編碼規(guī)則進(jìn)行檢查，如果有錯自動糾正，特點如下：不需要反饋信道，特別適合只能提供單向信道場合自動糾錯，不要求檢錯重發(fā)，延時小，實時性好糾錯碼必須與信道的錯誤特性密切配合若糾錯較多，則編、譯碼設(shè)備復(fù)雜，傳輸效率低差錯控制方式—前向糾錯能夠發(fā)現(xiàn)和糾正錯誤的碼發(fā)收混合糾錯檢錯（HEC）判決信號FEC與ARQ的結(jié)合發(fā)端發(fā)出同時具有檢錯和糾錯能力的碼，收端收到后，檢查錯誤情況：如果錯誤在糾錯能力之內(nèi)，則自動糾正；若超出糾錯能力，但在檢錯能力之內(nèi)，則經(jīng)反向信道要求重發(fā)差錯控制方式—混合糾錯檢錯信道編碼的幾個基本概念1）碼重：碼字中非零位的數(shù)目定義為該碼組的重量，即所含“1”的個數(shù)簡稱碼重，記為Wc。如“10011”碼組的碼重為32）碼距：兩個碼組中對應(yīng)碼位上具有不同二進(jìn)制碼元的位數(shù)被定義為兩碼組的距離，稱為漢明（Hamming）距離，簡稱碼距，記為d(ci,cj

)。如兩碼組“10011”與“11010”間碼距為23）編碼效率：指一個碼組中信息位所占比重，用η

表示

η

=k/n其中k為信息碼元的數(shù)目，n為碼長。η

值越大表明信息位所占的比重越大，碼組傳輸信息的有效性越高若某信源產(chǎn)生兩個符號A與B，假設(shè)分別用兩個長度為4的碼組（已被信道編碼）進(jìn)行表示：A=0110；B=1100，碼距d=2，此時只有這兩個碼組是許用碼組，其他4位二進(jìn)制比特位的組合均為禁用碼組（不能代表任何消息）假設(shè)這種信道編碼方式具有檢錯能力，下面分析碼距與檢錯能力的關(guān)系1）消息A經(jīng)過傳輸后發(fā)生一位錯誤后的情況可能為：A(0110)→{1110，0010，0100，0111}2）消息A經(jīng)過傳輸后發(fā)生二位錯誤后的情況可能為：A(0110)→{1010，0000，0101，1100，1111，0011}A碼組的誤碼集合中存在許用碼組B，可知該編碼方法不能檢查二位以上的錯誤因此編碼的檢錯能力與碼距有關(guān)最小碼距與檢、糾錯能力關(guān)系在一個碼組集合中，任意兩個碼組間距離的最小值，即碼組集合中任意兩元素間的最小距離，記為dmin假設(shè)A和B是某個許用碼組集合中的兩個許用碼組，它們之間的距離n是該集合的最小碼距，則：碼組A發(fā)生n位錯誤后構(gòu)成的誤碼集合中必然包含許用碼組B，此時便失去了檢錯能力有上述分析可知：假設(shè)一個碼能檢測e個獨立錯誤，則要求其最小碼距

dmin≥e

+1反之，若碼的最小距離為dmin，則最多能檢測dmin-1個錯碼若某信源產(chǎn)生兩個符號A與B，假設(shè)分別用兩個長度為4的碼組（已被信道編碼）進(jìn)行表示：A=0110；B=1000，碼距d=3假設(shè)這種信道編碼方式具有糾錯能力，下面分析碼距與糾錯能力的關(guān)系1）若信道中只可能發(fā)生一位或兩位錯誤，則消息A與消息B經(jīng)過傳輸后發(fā)生一位錯誤后的情況分別可能為：A(0110)→{1110，0010，0100，0111}B(1000)→{0000，1100，1010，1001}若該種編碼方法可以糾正t=1個錯誤，此時上面兩個誤碼集合是沒有交集的。因此可以完全的糾錯，即可以分別將誤碼集合中的碼字糾正為A或B2）若信道中最多可以發(fā)生兩位以內(nèi)錯誤，消息A與消息B經(jīng)過傳輸后發(fā)生一位或兩位錯誤后的情況分別可能為：A(0110)→{1110，0010，0100，0111，1010，0000，0101，1100，1111，0011}B(1000)→{0000，1100，1010，1001，0100，1110，1011，1010，1001，1101}每個誤碼集合中前4個碼組為誤碼一位的碼組，后6個位誤碼兩位的碼組若該種編碼方法可以糾正t=2個錯誤，即d<2t+1；觀察發(fā)現(xiàn)兩個誤碼集合存在交集，交集中的碼組用相應(yīng)的顏色標(biāo)出；兩個集合中黑色字體的碼組都可以被正確的糾正，但對于其他顏色的碼組，比如1110，它在兩個集合中都存在，此時接收端不知道該糾正為A還是B。因此當(dāng)d<2t+1時不能完全正確的進(jìn)行糾錯由上述分析可知：一個碼能糾正t個錯碼，則要求其最小碼距

dmin

≥2t+1反之，若碼的最小距離為dmin

，則最多能糾正(dmin-1)/2個錯碼一個碼能糾正t個錯碼，同時能檢測e個錯碼，則要求其最小碼距

dmin≥e+t+1(e>t)糾正t個錯碼，同時能檢測e個錯碼，稱為糾檢結(jié)合，錯碼數(shù)較少時執(zhí)行糾錯方式，錯碼數(shù)較多時執(zhí)行檢錯方式有限域的簡單知識所謂有限域是指包含有限個元素的集合，按照所規(guī)定的運算規(guī)則運算后的結(jié)果仍為集合中的元素編碼理論中有限域為{0,1}二元集合，記為GF(2)GF(2)的加法與乘法：1）加法：相同為0，相異為1；2）乘法：除了1·1=1，其他均為0二元擴展域，記為GF(2n)：由GF(2)中的元素構(gòu)成的長為n的序列的集合，若1）加法2）乘法二、線性分組碼線性分組碼的數(shù)學(xué)定義：信道編碼可表示為由編碼前的信息碼元空間Uk到編碼后的碼字空間Cn的一個映射f，即：f：Uk

→Cn

其中(n>k)若f進(jìn)一步滿足線性關(guān)系：則稱f為線性編碼映射，若f為一一對應(yīng)映射，則稱f為唯一可譯線性編碼，由f編寫的碼c=(cn-1cn-2…c0)稱為線性分組碼，u=(un-1un-2…u0)為編碼前的信息分組，其中k為信息位數(shù)，n為碼長，其編碼效率為η=k/n數(shù)學(xué)定義的解釋：1）“線性”是指碼組中碼元之間的約束關(guān)系為線性；2）“分組”是在編碼時將每k個信息位分為一組進(jìn)行獨立處理；3）將其變換成長度為n（n>k）的二進(jìn)制碼組，一般稱為（n,k）線性分組碼線性分組碼的特征：1）加法封閉性：碼組集合中任意兩個碼組相加仍為集合中的一個許用碼組；2）全零序列是線性分組碼中的一個碼字；3）碼組集合中碼組之間的最小碼距等于某非零碼字的最小碼重偶監(jiān)督偶校驗碼發(fā)送端編碼：將一位監(jiān)督碼元附加在信息碼元后，使得碼組中“1”碼元個數(shù)為偶數(shù)（偶監(jiān)督）接收端譯碼校驗：1）計數(shù)接收碼組中“1”碼元個數(shù)是否為偶數(shù)，即計算S=an-1+an-2+……+a02）S=0認(rèn)為沒錯，S=1認(rèn)為有錯3）上式稱為監(jiān)督方程（監(jiān)督關(guān)系式），其中S稱為校正子（校驗子、伴隨式）4）S只能判斷有錯無錯，而不能糾錯漢明碼的構(gòu)造

假設(shè)有1個信息碼組由4位二進(jìn)制位組成，在其后添加3位二進(jìn)制位作為監(jiān)督碼元，最后所組成的碼組表示為：c=(u6u5u4u3c2c1c0)并且令：1）c2監(jiān)督u6u5u4，即2）c1監(jiān)督u6u5u3，即3）c0監(jiān)督u6u4u3，即接收端譯碼校驗，得到監(jiān)督方程：對于上式，若無錯誤發(fā)生，三個校驗子均為0；假設(shè)傳輸過程中有且僅有一位發(fā)生錯誤：1）若c0發(fā)生錯誤，觀察監(jiān)督方程，則三個校驗子S2S1S0的組合為001；2）若c1發(fā)生錯誤，S2S1S0=010；3）若c2發(fā)生錯誤，S2S1S0=100；4）若u3發(fā)生錯誤，S2S1S0=011；5）若u4發(fā)生錯誤，S2S1S0=101；6）若u5發(fā)生錯誤，S2S1S0=110；7）若u6發(fā)生錯誤，S2S1S0=111；因此依據(jù)監(jiān)督關(guān)系式就可計算出所有4位二進(jìn)制信息位u6u5u4u3的監(jiān)督位c2c1c0，這一過程即為(7,4)線性碼的構(gòu)造過程，其碼組空間為：表中所示為(7,4)線性碼的碼組空間監(jiān)督矩陣的推導(dǎo)將監(jiān)督關(guān)系式進(jìn)行變換觀察發(fā)現(xiàn)上式即為一個線性方程組，因此可用矩陣方程來表示：對于上面的矩陣方程，令：則矩陣方程可化簡為：H·CT=OT

或C·HT=O那么H稱為線性碼監(jiān)督矩陣，r×n

階的矩陣，由r（監(jiān)督位個數(shù)）個線性獨立方程組的系數(shù)組成，每一行代表了監(jiān)督位與信息位間的監(jiān)督關(guān)系。觀察矩陣H：把具有(P·Ir)形式的H矩陣稱為典型形式的監(jiān)督矩陣，其中P矩陣為r×k

階矩陣,Ir矩陣為r×r

階單位方陣H矩陣的各行應(yīng)線性無關(guān)。矩陣若能寫成典型形式，則其各行一定線性無關(guān)生成矩陣的推導(dǎo)對監(jiān)督關(guān)系式進(jìn)行移項變換（移動紅色部分）：觀察上面的矩陣方程：其中系數(shù)矩陣與監(jiān)督矩陣H中的P矩陣一樣，對此矩陣方程兩邊做轉(zhuǎn)置變換：其中Q=PT，為k×r

階矩陣；U矩陣表示信息位由上面的矩陣方程可知，只要用信息位與矩陣Q相乘就可得到監(jiān)督位，然后拼接在信息位之后就是一個（n,k）線性分組碼集合中的一個碼字雖然通過Q矩陣可以產(chǎn)生線性分組碼，但需要分為兩步，如果對Q矩陣做變換：

在Q矩陣的左邊加上一個k×k階單位陣，即：則一個（n,k）線性分組碼可以通過下面的矩陣方程產(chǎn)生矩陣G則被稱為線性分組