第一章-糾錯碼的基本概念資料課件

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

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

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

7/20/202334糾錯編碼技術1.6糾錯碼的基本概念性能指標香農信道編碼定理分組碼的檢糾錯能力7/20/202335糾錯編碼技術性能指標編碼效率

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

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

編碼的任務：構造出R一定、d0盡可能大的碼，或者d0一定、R盡可能大的碼1.6糾錯碼的基本概念7/20/202350糾錯編碼技術1.7幾種常用的編碼方式奇偶校驗碼群計數(shù)碼恒比碼（等重碼）7/20/202351糾錯編碼技術1.7幾種常用的編碼方式奇偶校驗碼偶校驗碼：加入監(jiān)督位后，碼字中“1”的個數(shù)為偶數(shù)個，即所有位的模二和為0。（即偶數(shù)個1）奇校驗碼：加入監(jiān)督位后碼字中“1”的個數(shù)為奇數(shù)個，即所有位的模二和為1。（即奇數(shù)個1）這是一種最簡單的檢錯碼，在計算機數(shù)據(jù)傳輸中得到廣泛應用。7/20/202352糾錯編碼技術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ù)碼變成奇偶校驗碼7/20/202353糾錯編碼技術1.7幾種常用的編碼方式恒比碼碼字中“1”和“0”的個數(shù)保持相同的比例，即每個碼字中1的個數(shù)相同。恒比碼的譯碼可以采用查表方法，檢錯時查1或0的個數(shù)。