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

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

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

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

表示

η

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

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

dmin≥e

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

dmin

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

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

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

→Cn

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

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

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

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

階矩陣,Ir矩陣為r×r

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

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

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