第一章 糾錯(cuò)碼的基本概念

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

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

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

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

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

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

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