第一章 糾錯碼的基本概念

糾錯編碼技術(shù)第一章 糾錯碼的基本概念福州大學(xué)陽光學(xué)院本章主要內(nèi)容1.1編碼系統(tǒng)模型1.2信道錯誤類型與信道模型1.3差錯控制的基本方式1.4糾錯碼的分類1.5最大后驗與最大似然譯碼1.6糾錯碼的基本概念1.7幾種常用的編碼方式12/15/20232糾錯編碼技術(shù)本章要求掌握：差錯控制方式糾錯碼的基本概念理解：最大似然譯碼了解：糾錯編碼的作用、基本思想和編碼系統(tǒng)模型12/15/20233糾錯編碼技術(shù)1.1編碼系統(tǒng)模型12/15/20234糾錯編碼技術(shù)1.1編碼系統(tǒng)模型信源編碼器：將信源發(fā)出的消息如語言、圖像、文字等轉(zhuǎn)換成為二進制(也可轉(zhuǎn)換成為多進制)形式的信息序列。信源編碼器的設(shè)計目標(biāo)：（1）以最低的比特率表示信源的輸出消息；（2）信源的輸出可由信息序列{m}準(zhǔn)確的重現(xiàn)。12/15/20235糾錯編碼技術(shù)1.1編碼系統(tǒng)模型信道編碼器：將信息序列{m}變換成離散的編碼序列{C}，稱之為碼字。本課程的主要內(nèi)容之一，就是設(shè)計和實現(xiàn)信道編碼器，以抵抗傳輸或存儲碼字所面臨的噪聲環(huán)境的影響。12/15/20236糾錯編碼技術(shù)1.1編碼系統(tǒng)模型調(diào)制器或?qū)懭雴卧簩⑿诺谰幋a器輸出的每個符號，轉(zhuǎn)換為持續(xù)時間為T秒的適合傳輸（或記錄）的波形，這些波形進入信道或存儲媒質(zhì)，并受到噪聲的干擾。解調(diào)器或讀出單元：處理收到的每個持續(xù)時間為T秒的波形，然后產(chǎn)生離散（量化）或連續(xù)（非量化）的輸出。解調(diào)器的輸出序列稱為接收序列{R}。12/15/20237糾錯編碼技術(shù)1.1編碼系統(tǒng)模型信道譯碼器：將接收序列{R}變換為二進制序列，稱之為估計信息序列。本課程的另一主要內(nèi)容，就是設(shè)計和實現(xiàn)使譯碼錯誤概率最小的信道譯碼器。譯碼策略根據(jù)信道編碼規(guī)則和信道的噪聲特性設(shè)計。12/15/20238糾錯編碼技術(shù)1.1編碼系統(tǒng)模型編碼系統(tǒng)的簡化模型12/15/20239糾錯編碼技術(shù)1.2信道錯誤類型與信道模型隨機錯誤和隨機信道突發(fā)錯誤和突發(fā)信道混合錯誤和混合信道12/15/202310糾錯編碼技術(shù)1.2信道錯誤類型與信道模型隨機錯誤和隨機信道隨機錯誤：信道傳輸中，信息序列各碼元發(fā)生的出錯事件彼此獨立，即每個碼元獨立的按一定的概率發(fā)生差錯。只存在隨機錯誤的信道稱為無記憶信道（隨機信道），用信道轉(zhuǎn)移概率來描述。例如，二進制對稱信道BSC和離散無記憶信道DMC。12/15/202311糾錯編碼技術(shù)二進制對稱信道（BinarySymmetricChannel,BSC）P(0/0)=1-pP(1/0)=pP(1/1)=1-pP(0/1)=p輸入符號取值集合X={0，1}輸出符號取值集合Y={0，1}0101XYpp1-p1-p1.2信道錯誤類型與信道模型12/15/202312糾錯編碼技術(shù)離散無記憶信道（DiscreteMemorylessChannel,DMC）輸入符號取值集合 X={x0,x1,…,xq-1}輸出符號取值集合 Y={y0,y1,…,yQ-1}qQ個條件概率：P(yj/xi)=pij其中，i=0,1,…q-1;j=0,1,…Q-1x0x1xq-1...y0y1y2...yQ-1P(y0/x0)P(y1/x0)P(y2/x0)P(yQ-1/x0)P(y0/x1)P(y1/x1)P(y2/x1)P(yQ-1/x1)1.2信道錯誤類型與信道模型12/15/202313糾錯編碼技術(shù)1.2信道錯誤類型與信道模型突發(fā)錯誤和突發(fā)信道突發(fā)錯誤：噪聲對各傳輸碼元的影響不是獨立的，從而導(dǎo)致差錯是一連串出現(xiàn)的。例如移動通信中信號在某一段時間內(nèi)發(fā)生衰落，造成一串差錯；光盤上的一條劃痕等等。存在突發(fā)錯誤的信道，稱之為有記憶信道（突發(fā)信道）。12/15/202314糾錯編碼技術(shù)1.2信道錯誤類型與信道模型混合錯誤和混合信道混合錯誤：既有突發(fā)錯誤又有隨機錯誤。突發(fā)錯誤和隨機錯誤并存的信道稱之為混合信道。12/15/202315糾錯編碼技術(shù)錯誤圖樣：設(shè)發(fā)送的是序列C（碼元長度為n），通過信道傳輸后，接收端的序列為R。由于信道中存在干擾，R序列中的某些碼元和C序列中的對應(yīng)碼元的值可能不同，如果信道中的干擾采用二進制序列e表示，相應(yīng)有錯誤的位取值為1，無錯的位取值為0，可得e=C⊕R。1.2信道錯誤類型與信道模型12/15/202316糾錯編碼技術(shù)例：發(fā)送序列C：（1111100000），收到的序列R：（1001010000），第二、三、五、六位產(chǎn)生了錯誤，因此錯誤圖樣e的二、三、五、六位取值為1，即e：(0110110000)對于突發(fā)信道，錯誤圖樣中，第一個“1”和最后一個“1”之間的碼元總個數(shù)稱為突發(fā)長度，其圖樣成為突發(fā)圖樣。該例中，突發(fā)圖樣是（11011），突發(fā)長度為5。1.2信道錯誤類型與信道模型12/15/202317糾錯編碼技術(shù)1.3差錯控制的基本方式反饋重傳方式前向糾錯方式混合方式12/15/202318糾錯編碼技術(shù)1.3差錯控制的基本方式反饋重傳方式(ARQ)工作原理：發(fā)送端發(fā)送檢錯碼，通過信道傳輸?shù)浇邮斩?，接收端譯碼器根據(jù)編碼規(guī)則判斷是否有錯誤，并把判決信號通過反饋信道送回發(fā)送端。發(fā)送端根據(jù)判決信號確定是否重新發(fā)送，直到接收端檢查無誤為止。12/15/202319糾錯編碼技術(shù)1.3差錯控制的基本方式優(yōu)點：1.編譯碼設(shè)備簡單2.糾錯能力強3.對信道的適應(yīng)性強缺點：1.需反饋信道2.控制電路復(fù)雜3.傳送信息的實時性、連貫性差信源編碼器和緩存器重發(fā)控制雙向信道反饋控制器檢錯碼譯碼器信宿緩存器ARQ通信系統(tǒng)組成12/15/202320糾錯編碼技術(shù)前向糾錯方式(FEC)工作原理：發(fā)送端發(fā)送能糾正錯誤的碼字，在接收端根據(jù)接收到的碼字和編碼規(guī)則，能自動糾正傳輸中的錯誤。不需要反饋信道，實時性好。隨著糾錯能力的提高，編譯碼設(shè)備復(fù)雜。1.3差錯控制的基本方式發(fā)端收端糾錯碼12/15/202321糾錯編碼技術(shù)1.3差錯控制的基本方式混合方式(HEC)工作原理：結(jié)合前向糾錯和ARQ的系統(tǒng)，在糾錯能力范圍內(nèi)，自動糾正錯誤，超出糾錯范圍則要求發(fā)送端重新發(fā)送。發(fā)端收端檢糾錯碼判決信號12/15/202322糾錯編碼技術(shù)1.4糾錯碼的分類按差錯控制編碼的不同功能：檢錯碼：發(fā)現(xiàn)錯誤的碼糾錯碼：自動糾正錯誤的碼按信息碼元與附加監(jiān)督碼元間檢驗關(guān)系：線性碼(LinearCode)：監(jiān)督碼元與信息碼元滿足線性關(guān)系非線性碼(NonlinearCode)：監(jiān)督碼元與信息元不滿足線性關(guān)系12/15/202323糾錯編碼技術(shù)1.4糾錯編碼的分類按信息碼元與監(jiān)督碼元間約束方式：分組碼(BlockCode)：信息序列每k位分成一組，產(chǎn)生r位監(jiān)督元，輸出長度為n=r+k的碼字。r位監(jiān)督元只與本分組的k位信息元有關(guān)，記為（n,k）。卷積碼(ConvolutionalCode)：編碼器給每k0位信息加上n0-k0位監(jiān)督元得到長度為n0的碼字。該碼字的運算，不僅與本段k0位信息有關(guān)，還與其前面m組k0位信息有關(guān)。稱這種碼為（n0，k0，m）卷積碼。12/15/202324糾錯編碼技術(shù)1.4信道編碼的分類按信息碼元在編碼后是否保持原來的形式：系統(tǒng)碼、非系統(tǒng)碼按糾正錯誤的類型：糾正隨機錯誤的碼、糾正突發(fā)錯誤的碼按每個碼元取值：二進制碼、多進制碼12/15/202325糾錯編碼技術(shù)分組碼的定義分組碼是對每段k位長的信息組，以一定規(guī)則增加r=n-k個校驗元，組成長為n的序列：（cn-1，cn-2，...，c2，c1）,稱這個序列為碼字（碼組、碼矢）。在二進制情況下，信息組總共有2k個，因此通過編碼器后，相應(yīng)的碼字也有2k個，稱這個2k個碼字集合為（n，k）分組碼。12/15/202326糾錯編碼技術(shù)分組碼將k個比特編成n個比特的碼字（Codewords）通常記分組碼為（n，k）碼。（n，k）碼中有2k個碼字。（n，k）碼中有2k個n重碼字。但是nbit的二進制序列具有2n種不同的組合序列；分組碼的編碼規(guī)則就是從2n種不同序列中選擇2k個碼字，建立信息序列與碼字的對應(yīng)關(guān)系；分組碼的定義12/15/202327糾錯編碼技術(shù)許用碼組、禁用碼組這2k個碼字組成的集合稱為許用碼組，剩余的2n-2k個n重向量組成的集合稱為禁用碼組。碼重:碼字中非0碼元的個數(shù)，又稱漢明重量。如碼字x=(11000)，則碼重w(x)=2碼距:碼字x與碼字y對應(yīng)位取值不同的個數(shù)，又稱為漢明距離。例如:x=(10111101),y=(01110101)，則碼距d(x,y)=3分組碼的定義12/15/202328糾錯編碼技術(shù)1.5最大后驗與最大似然譯碼信源編碼信道譯碼信宿mcrm’根據(jù)編碼規(guī)則，在信息序列基礎(chǔ)上增加監(jiān)督碼元，生成碼字根據(jù)一套譯碼規(guī)則，由接收序列r給出與發(fā)送序列m最接近（最好是相同）的估值序列m’已知條件：1）實際接收的碼字r（必要條件）2）發(fā)送端采用的編碼算法和產(chǎn)生的碼集Xn（必要條件）3）信道模型和信道參數(shù)12/15/202329糾錯編碼技術(shù)1.5最大后驗與最大似然譯碼編碼：m=>c譯碼：r=>c’=>m’由于信息序列與碼字之間存在一一對應(yīng)關(guān)系，所以等價于譯碼器根據(jù)r產(chǎn)生一個c的估值序列c’。顯然當(dāng)且僅當(dāng)c’=c時，m’=m，此時譯碼器正確譯碼。信源編碼信道譯碼信宿mcrm’c’12/15/202330糾錯編碼技術(shù)1.5最大后驗與最大似然譯碼最大后驗譯碼(MaximumAPosteriori,MAP)對于給定接收序列r，譯碼器的條件譯碼錯誤概率為：譯碼錯誤概率最小，有對于輸入r，譯碼器在2k個碼字中選擇一個使P(c*/r)最大的碼字c*作為c的估值序列c’，會使譯碼輸出錯誤概率最小，這種譯碼準(zhǔn)則為最大后驗譯碼。12/15/202331糾錯編碼技術(shù)1.5最大后驗與最大似然譯碼最大后驗譯碼(MaximumAPosteriori,MAP)最優(yōu)的譯碼算法，所以也稱最佳譯碼但是實際譯碼時，定量地找出后驗概率值很困難通常情況下，可以知道信道的前向（發(fā)->收）轉(zhuǎn)移概率，比如BSC信道模型中的p12/15/202332糾錯編碼技術(shù)1.如果發(fā)送端發(fā)送每個碼字的概率相同，最大似然譯碼等價于最大后驗譯碼。2.譯碼器對于輸入r，在2k個碼字中選擇一個使似然概率最大的碼字c*作為c的估值序列c’。1.5最大后驗與最大似然譯碼最大似然譯碼(MaximumLikelihoodDecoding,MLD)

由貝葉斯公式，若發(fā)送端發(fā)送每個碼字的概率P(c*)均相同，且由于P(r)與譯碼方法無關(guān)，所以

12/15/202333糾錯編碼技術(shù)1.5最大后驗與最大似然譯碼最大似然譯碼(MLD)對于無記憶信道，碼字的似然函數(shù)等于組成碼字的各碼元的似然函數(shù)之積，即若r=(r1,r2,…rn),c=(c1,c2,…,cn)碼字最大似然函數(shù)也就是各碼元似然函數(shù)之積的最大化

12/15/202334糾錯編碼技術(shù)1.6糾錯碼的基本概念性能指標(biāo)香農(nóng)信道編碼定理分組碼的檢糾錯能力12/15/202335糾錯編碼技術(shù)性能指標(biāo)編碼效率

分組碼（n，k），R表明了信息元在碼字中所占的比重，是衡量編碼有效性的基本參數(shù)。n-k監(jiān)督位，監(jiān)督位越多，糾錯能力越強，效率越低。n越大，編、譯碼延時越大。1.6糾錯碼的基本概念12/15/202336糾錯編碼技術(shù)性能指標(biāo)香農(nóng)信道編碼定理分組碼的檢糾錯能力1.6糾錯碼的基本概念12/15/202337糾錯編碼技術(shù)香農(nóng)信道編碼定理對于一個給定的有擾信道，若信道的容量為C，只要發(fā)送端以低于C的速率發(fā)送信息，則一定存在一種編碼方法，使譯碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值，表示為這里E(R)稱為誤差指數(shù)。1.6糾錯碼的基本概念12/15/202338糾錯編碼技術(shù)定理說明：當(dāng)信息速率小于信道容量時，總存在一種編碼方式使差錯率低于任一給定值ε；為減小差錯概率，可增大碼長n或增大E(R)。1.6糾錯碼的基本概念12/15/202339糾錯編碼技術(shù)性能指標(biāo)香農(nóng)信道編碼定理分組碼的檢糾錯能力1.6糾錯碼的基本概念12/15/202340糾錯編碼技術(shù)分組碼的檢糾錯能力最小碼距:(n,k)分組碼中，任何兩個不同碼字之間距離的最小值，稱為該分組碼的最小漢明距離，簡稱最小距離，用d0表示。最小碼距決定了碼的糾錯、檢錯性能。最小漢明距離譯碼準(zhǔn)則:在許用碼組中，判斷與接收序列r“最近”的碼字為發(fā)送碼字。1.6糾錯碼的基本概念12/15/202341糾錯編碼技術(shù)分組碼的檢糾錯能力檢錯能力：一個(n,k)分組碼，如果能檢出一個碼字內(nèi)的所有小于或等于e個(位)錯誤，則稱該碼的檢錯能力為e糾錯能力：一個(n,k)分組碼，如果能糾正一個碼字內(nèi)的所有小于或等于t個(位)錯誤，則稱該碼的糾錯能力為t1.6糾錯碼的基本概念12/15/202342糾錯編碼技術(shù)分組碼的檢糾錯能力同時糾檢錯能力：一個(n,k)分組碼，如果能糾正一個碼字內(nèi)的所有小于或等于t個(位)錯誤，同時又能檢出所有小于或等于e(e>t)個(位)錯誤，則稱該碼的同時糾檢錯能力為糾t個錯同時檢e個錯1.6糾錯碼的基本概念12/15/202343糾錯編碼技術(shù)分組碼的檢糾錯能力為了檢測e個錯誤，要求分組碼的最小碼距d0≥e+11.6糾錯碼的基本概念12/15/202344糾錯編碼技術(shù)分組碼的檢糾錯能力為了糾正t個錯誤，要求分組碼的最小碼距d0≥2t+11.6糾錯碼的基本概念12/15/202345糾錯編碼技術(shù)分組碼的檢糾錯能力為了糾正t個錯誤，同時檢測e個錯誤(e>=t)，要求最小碼距d0≥e+t+11.6糾錯碼的基本概念12/15/202346糾錯編碼技術(shù)分組碼的檢糾錯能力由此定理可知，一個距離為d的分組碼，（1）至多能糾正t＝［(d0-1)／2］(［x］是x的整數(shù)部分)個錯誤。（2）至多能發(fā)現(xiàn)e＝（d0-1）個錯誤。1.6糾錯碼的基本概念12/15/202347糾錯編碼技術(shù)分組碼的檢糾錯能力d0是分組碼的一個重要參數(shù)，它表明了分組碼抗干擾能力的大小。設(shè)計碼時，要同時考慮d0和R舉例重復(fù)碼（校驗元是信息元的重復(fù)，錯誤概率P）

(2,1)碼：d0=2,R=1/2，能檢1個錯，若與ARQ結(jié)合，譯碼錯誤概率為p2；不能糾錯；1.6糾錯碼的基本概念12/15/202348糾錯編碼技術(shù)分組碼的檢糾錯能力舉例重復(fù)碼（校驗元是信息元的重復(fù)，錯誤概率P）(3,1)碼：d0=3,R=1/3，（1）若僅用來檢錯，能檢2個錯；（2）能夠糾1個錯。1.6糾錯碼的基本概念12/15/202349糾錯編碼技術(shù)舉例2重復(fù)碼（校驗元是信息元的重復(fù)）(4,1)碼：d0=4,R=1/4，若僅用來檢錯，能檢3個錯；若同時糾檢錯，則能糾1個錯同時檢2個錯

編碼的任務(wù)：構(gòu)造出R一定、d0盡可能大的碼，或者d0一定、R盡可能大的碼1.6糾錯碼的基本概念12/15/202350糾錯編碼技術(shù)1.7幾種常用的編碼方式奇偶校驗碼群計數(shù)碼恒比碼（等重碼）12/15/202351糾錯編碼技術(shù)1.7幾種常用的編碼方式奇偶校驗碼偶校驗碼：加入監(jiān)督位后，碼字中“1”的個數(shù)為偶數(shù)個，即所有位的模二和為0。（即偶數(shù)個1）奇校驗碼：加入監(jiān)督位后碼字中“1”的個數(shù)為奇數(shù)個，即所有位的模二和為1。（即奇數(shù)個1）這是一種最簡單的檢錯碼，在計算機數(shù)據(jù)傳輸中得到廣泛應(yīng)用。12/15/202352糾錯編碼技術(shù)1.7幾種常用的編碼方式群計數(shù)碼將碼字中“1”的計數(shù)值作為監(jiān)督碼例如，信息組為01011，共3個1，用011表示，得到(8,5)碼。群計數(shù)碼的碼字為01011011檢錯能力很強，除了0錯成1和1錯成0成對發(fā)生的情況外，其它形式的錯誤都能發(fā)現(xiàn)。為了降低發(fā)送碼元中的冗余度，有時只傳送計數(shù)碼元中最后幾位。特別的只傳輸最后1位監(jiān)督元，則群計數(shù)碼變成奇偶校驗碼12/15/202353糾錯編碼技術(shù)1.7幾種常用的編碼方式恒比碼碼字中“1”和“0”的個數(shù)保持相同的比例，即每個碼字中1的個數(shù)相同。恒比碼的譯碼可以采用查表方法，檢錯時查1或0的個數(shù)。