差錯控制的基本概念

差錯控制的基本概念第1頁，共67頁，2022年，5月20日，4點51分，星期三1本章內(nèi)容提要差錯控制系統(tǒng)及其理論基礎(chǔ)糾錯編碼的基本概念及其本質(zhì)糾錯編碼方法的性能評價、基于圖形的編碼第2頁，共67頁，2022年，5月20日，4點51分，星期三2差錯控制的理論基礎(chǔ)主要是香農(nóng)第二定理和近世代數(shù)。

（1）香農(nóng)第二定理

這個抗干擾信道編碼定理作為一個存在性定理，指出可以用任意接近信道容量的信息傳輸速率傳送消息，且出錯的概率可以任意小。引發(fā)了人們對糾錯碼的研究。糾錯碼理論的中心任務(wù)就是要針對具有不同干擾特性的各種信道設(shè)計出編碼效率高、抗干擾性能好、而編譯碼設(shè)備又較簡單的糾錯碼或檢錯碼。

9.1.1差錯控制的理論基礎(chǔ)9.1差錯控制系統(tǒng)及其基礎(chǔ)第3頁，共67頁，2022年，5月20日，4點51分，星期三3

（2）近世代數(shù)經(jīng)典代數(shù)學(xué)以數(shù)為主要的研究對象，而近世代數(shù)將研究對象由數(shù)擴展到向量、矩陣等，以研究更為一般的代數(shù)運算的規(guī)律和性質(zhì)為目標(biāo)，推動了以討論群、環(huán)、域、多項式、向量空間等性質(zhì)和結(jié)構(gòu)為主要內(nèi)容的理論的發(fā)展。近世代數(shù)又稱為抽象代數(shù)，在研究信道編碼的許多具體構(gòu)造規(guī)律時，發(fā)現(xiàn)用近世代數(shù)的理論能夠?qū)幋a結(jié)構(gòu)給予非常吻合的描述，因此成為信道編碼的重要理論基礎(chǔ)。

9.1.1差錯控制的理論基礎(chǔ)9.1差錯控制系統(tǒng)及其基礎(chǔ)第4頁，共67頁，2022年，5月20日，4點51分，星期三4差錯控制系統(tǒng)根據(jù)它們的糾、檢錯能力；對信道的要求及適應(yīng)性；編、譯碼器的復(fù)雜性；編、譯碼的實時性等性能指標(biāo)可以分為如下4類自動請求重傳系統(tǒng)前向糾錯系統(tǒng)信息重復(fù)查詢系統(tǒng)混合糾錯系統(tǒng)9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)第5頁，共67頁，2022年，5月20日，4點51分，星期三5圖9.1ARQ系統(tǒng)(1)自動請求重傳系統(tǒng)

通信系統(tǒng)在接收端檢測到傳輸錯誤并自動告知發(fā)送方，請求發(fā)送方重發(fā)，稱為自動請求重發(fā)，簡稱反饋重傳。系統(tǒng)構(gòu)成如圖9.1所示。9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)第6頁，共67頁，2022年，5月20日，4點51分，星期三6該系統(tǒng)接收端在收到的信碼中檢測出錯碼時，即設(shè)法通知發(fā)送端重發(fā)，直到正確收到為止。所謂檢測出錯碼，是指在若干接收碼元中知道有一個或一些是錯的，但不一定知道該錯碼的準(zhǔn)確位置。圖9.2列舉了3種最流行的ARQ方式停止–等待式ARQ具有回拉功能的連續(xù)ARQ具有選擇性重發(fā)功能的連續(xù)ARQ9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)第7頁，共67頁，2022年，5月20日，4點51分，星期三7圖9.2

自動請求重發(fā)（ARQ）第8頁，共67頁，2022年，5月20日，4點51分，星期三8停止–等待式ARQ只需要半雙工連接，因為發(fā)射機在接到確認(rèn)信號后才進行下一個傳送；具有回拉功能的連續(xù)ARQ需要全雙工連接，通信雙方的終端設(shè)備同時傳輸，發(fā)送方傳送信息數(shù)據(jù)，接收方傳送確認(rèn)信號和非確認(rèn)信號，在ARQ過程中，發(fā)送方被“拉回”到錯誤傳送的消息處，從錯誤消息開始處重發(fā)所有的信息數(shù)據(jù)；具有選擇性重發(fā)功能的連續(xù)ARQ也需要全雙工連接，但它只要求錯誤的消息重發(fā)，然后發(fā)射機從先前停止的地方繼續(xù)發(fā)送原序列而不重發(fā)已經(jīng)正確接收的消息。9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)第9頁，共67頁，2022年，5月20日，4點51分，星期三9ARQ系統(tǒng)的優(yōu)點是：糾錯能力強；檢錯能力與信道干擾變化無關(guān)，適應(yīng)性強；由于只要檢測錯誤就可以了，因此編譯碼器比較簡單。ARQ系統(tǒng)的缺點：必須有反向信道，否則只能檢錯收、發(fā)兩端必須互相配合信源能夠被控制實時性較差因此它只適用于當(dāng)發(fā)生錯誤需要重發(fā)的情況。9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)第10頁，共67頁，2022年，5月20日，4點51分，星期三10(2)前向糾錯（FEC）系統(tǒng)系統(tǒng)的接收端不僅能在收到的消息序列中發(fā)現(xiàn)錯誤，還能夠?qū)⑵浼m正。前向糾錯系統(tǒng)的基本組成如圖9.3所示。

圖9.3FEC系統(tǒng)9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)第11頁，共67頁，2022年，5月20日，4點51分，星期三11糾錯編碼主要應(yīng)用在數(shù)字通信中，根本目的是提高通信的可靠性。根據(jù)香農(nóng)第二定理，只要信道的信息傳輸速率小于信道容量，接近無差錯傳輸?shù)木幋a就是一定存在的，且信道容量C、信號帶寬B和到達接收端的信噪比S/N滿足香農(nóng)公式。因此，可以把糾錯編碼看成這3個參量相互影響彼此權(quán)衡的結(jié)果。在數(shù)字通信中，信噪比通常用Eb/N0來表示，其中Eb和

N0分別為信號的比特能量和噪聲的功率譜密度，它們在數(shù)值上和S/N相等。9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)第12頁，共67頁，2022年，5月20日，4點51分，星期三12通信系統(tǒng)誤比特率與Eb/N0關(guān)系的曲線兩者采用相同的調(diào)制方法和同樣的信道，可見信道編碼使得在同樣信噪比情況下降低了誤比特率，或者在更低的信噪比情況下也能達到誤比特率的要求。

9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)圖9.4

典型編碼與未編碼的差錯性能比較第13頁，共67頁，2022年，5月20日，4點51分，星期三13定義9.1

對于給定的誤比特率，編碼增益G是指通過編碼所能實現(xiàn)的Eb/N0的減少量，即：

(9.1)

其中和分別表示未編碼及編碼后所需要的Eb/N0

。例如，為了獲得低于10–4

的誤比特率，對于未編碼情況必須使Eb/N0至少保持在12dB以上，而采用編碼后僅需至少保持在8dB以上，在這種情況下獲得了4dB的編碼增益。9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)第14頁，共67頁，2022年，5月20日，4點51分，星期三14FEC系統(tǒng)的優(yōu)點是：收端可自動發(fā)現(xiàn)錯誤、糾正錯誤；不需反向信道；能進行一點對多點的同播，可以是雙向通信或單向通信；與ARQ相比，譯碼實時性好；控制電路比ARQ簡單。

FEC系統(tǒng)的缺點主要有：譯碼比較復(fù)雜；所選用的糾錯碼要和信道的干擾情況相匹配，對信道的適應(yīng)性較差，一般以最壞的信道條件來設(shè)計糾錯碼；通常是以注入冗余度為代價來換取編碼增益，注入的冗余度越大編碼增益越高，一般情況下編碼效率較低。9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)第15頁，共67頁，2022年，5月20日，4點51分，星期三15(3)信息重復(fù)查詢系統(tǒng)（IRQ）是指接收端將收到的消息原封不動地轉(zhuǎn)發(fā)回發(fā)送端，在發(fā)送端與原發(fā)送消息相比較的系統(tǒng)。如果發(fā)現(xiàn)錯誤，則發(fā)送端再進行重發(fā)，直至正確為止。原理和設(shè)備都較簡單，但需要有雙向信道，因為相當(dāng)于每一消息都至少傳送了兩次，所以傳輸效率較低。

(4)混合糾錯系統(tǒng)（HEC）HEC系統(tǒng)將反饋重傳技術(shù)與前向糾錯技術(shù)相結(jié)合。當(dāng)出現(xiàn)少量錯碼并在接收端能夠糾正時，即用前向糾錯方法糾正之；當(dāng)錯碼較多超過其糾正能力但尚能檢測時，就進行自動反饋重傳。混合糾錯結(jié)合了ARQ和FEC兩者的優(yōu)點。

9.1.2差錯控制系統(tǒng)9.1差錯控制系統(tǒng)及其基礎(chǔ)第16頁，共67頁，2022年，5月20日，4點51分，星期三161.差錯控制碼的分類

不同的差錯控制系統(tǒng)需要不同的差錯控制碼。從差錯控制碼功能的角度，可將常見的差錯控制碼分為以下3類：

（1）檢錯碼：只能發(fā)現(xiàn)錯誤，不能糾正錯誤。在一些僅需給出錯誤提示以及ARQ系統(tǒng)中使用這類碼。

（2）糾錯碼：能夠發(fā)現(xiàn)錯誤也能糾正錯誤。FEC和HEC系統(tǒng)都使用這類碼。

（3）糾刪碼：能夠發(fā)現(xiàn)并糾正或刪除錯誤。糾錯碼的應(yīng)用最為廣泛。9.2.1糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第17頁，共67頁，2022年，5月20日，4點51分，星期三172.糾錯碼的分類

圖9.5糾錯碼分類示意圖9.2.1糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第18頁，共67頁，2022年，5月20日，4點51分，星期三18(1)根據(jù)對信息元的處理方法分類按照對信息元處理方法的不同，可以將糾錯碼分為分組碼和卷積碼。分組碼的構(gòu)成如圖所示。

其碼長為n=k+r，其中k是信息元個數(shù)，r是監(jiān)督（校驗）元個數(shù)，監(jiān)督元只與本組信息元有關(guān)。通常將分組碼寫成碼(n,k)，或稱為(n,k)碼。9.2.1糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第19頁，共67頁，2022年，5月20日，4點51分，星期三19卷積碼的構(gòu)成如圖所示，其中n0≥k0

。最主要特點是n0－k0個監(jiān)督元不僅與本組的信息元有關(guān)，還與前m段的信息元有關(guān)。類似于分組碼，也稱n0為卷積碼的碼長，k0為信息元個數(shù)，m為存儲級數(shù)。通常將卷積碼寫成碼(n0,k0

,m)，或稱為(n0,k0

,m)碼。

9.2.1糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第20頁，共67頁，2022年，5月20日，4點51分，星期三20（2）根據(jù)校驗元與信息元之間的關(guān)系分類根據(jù)校驗元與信息元之間關(guān)系的不同，可以將糾錯碼分為線性碼和非線性碼。（3）根據(jù)糾正錯誤的類型分類糾隨機錯誤碼糾突發(fā)錯誤碼糾同步錯誤碼既糾隨機又糾突發(fā)錯誤碼。（4）根據(jù)每個碼元的取值分類二進制碼q進制碼，其中q=pm，p為素數(shù)，m為正整數(shù)。（5）根據(jù)碼的結(jié)構(gòu)特點分類

循環(huán)碼、非循環(huán)碼、系統(tǒng)碼，完備碼等。9.2.1糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第21頁，共67頁，2022年，5月20日，4點51分，星期三219.2.2糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)幾個基本定義定義9.2

設(shè)碼字v=(v0,v1,…,vn-1)C，令w(v)為碼字v中那些不為0的碼元的個數(shù)，即(9.2)則w(v)是碼字v的漢明重量，簡稱重量。定義9.3

碼C中所有那些不等于0的碼字的重量的最小值稱為碼C的最小重量。即(9.3)第22頁，共67頁，2022年，5月20日，4點51分，星期三22根據(jù)最小漢明距離的定義，(n，k)碼的最小漢明距離d為該種編碼中任兩個碼字間距離的最小值，即

(9.4)定義9.4

設(shè)發(fā)碼C:(cn-1,…,c1,c0)

或(c0,c1,…,cn-1)

，收碼R:(rn-1,…,r1,r0)或(r0,r1,…,rn-1)

，則定義信道的錯誤圖樣為E:(en-1,…,e1,e0)或(e0,e1,…,en-1)

，其中(9.5)由定義可知R=C+E(9.6)E=C–R(9.7)9.2.2糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第23頁，共67頁，2022年，5月20日，4點51分，星期三23定義9.5

在錯誤圖樣中，若“1”集中于某個長度b內(nèi)，則稱該種錯誤為長度為b的突發(fā)錯誤，其中b稱為突發(fā)錯誤長度，該圖樣稱為突發(fā)錯誤圖樣。典型的突發(fā)錯誤圖樣為：0…011…110…0，中間含有b個連續(xù)的1。對于一些編碼（例如循環(huán)碼），突發(fā)錯誤圖樣也包括首尾相接的錯誤，其錯誤圖樣為：1…100…001…1，其中兩段分別連續(xù)的1的個數(shù)共為b。9.2.2糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第24頁，共67頁，2022年，5月20日，4點51分，星期三24定義9.6

分組碼是對每段k位長的信息組，以一定規(guī)則增加r=n–k個監(jiān)督(校驗)元，組成長為n的序列(cn

–1,cn

–2,…c1,c0)，稱這個序列為碼字或碼組、碼矢。在二進制的情況下，k位長的信息組共2k個，通過編碼器后，碼字還是2k個，稱這2k個碼字的集合為(n，k)分組碼。n長序列的可能排列共有2n種，其中只有2k個n重構(gòu)成了(n,k)分組碼，稱它們?yōu)樵S用碼組，其余的2n–2k個n重為禁用碼組。9.2.2糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第25頁，共67頁，2022年，5月20日，4點51分，星期三25定義9.7

(n0,k0,m)卷積碼是對每段k0長的信息組以一定的規(guī)則增加r0=n0–k0個監(jiān)督(校驗)元，組成長為n0的碼段；n0–k0個校驗元不僅與本段的信息元有關(guān)，且與前m段的信息元有關(guān)；編碼約束長度nc=n0(m+1)，它表示k0個信息元從輸入編碼器到離開時，在碼序列中影響的碼元數(shù)目。定義9.8

將信息位在碼字中所占的比例稱為編碼效率，也稱為碼字效率，通常也用R表示。對于分組碼，有R=k/n

(9.8)

對于卷積碼，有R=k0/n0

(9.9)

編碼效率是衡量編碼有效性的基本參數(shù)。9.2.2糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第26頁，共67頁，2022年，5月20日，4點51分，星期三262.糾錯碼舉例

（1）重復(fù)碼重復(fù)碼是k=1的分組碼(n,1),它的(n–1)個校驗元是信息元的重復(fù)。對二進制系統(tǒng)，只有兩個碼字：00….0，11…..1，其中1和0的個數(shù)均為n。重復(fù)碼的譯碼采用大數(shù)判決方法，也稱為大數(shù)準(zhǔn)則，或最大似然準(zhǔn)則、最小距離準(zhǔn)則，即譯碼時以大于n/2的最小整數(shù)作為判決門限。若n是奇數(shù)，可以實現(xiàn)完全的譯碼，稱為完備譯碼；若n是偶數(shù)，則會出現(xiàn)1、0個數(shù)相等的情況，將導(dǎo)致譯碼失敗，稱為不完備譯碼，但由于檢出了錯誤，可作刪除處理或結(jié)合ARQ進行譯碼。9.2.2糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第27頁，共67頁，2022年，5月20日，4點51分，星期三27重復(fù)碼特點：d=n，隨著n的增大，抗干擾能力越來越強，但R=1/n隨之下降，編碼效率越來越低；檢錯能力大于或等于糾錯能力，距離d

越大，糾錯能力越強。若未編碼時接收的錯誤概率為

，經(jīng)過n次重復(fù)編碼后，如果結(jié)合ARQ技術(shù)，其接收的錯誤概率可降低到。9.2.2糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第28頁，共67頁，2022年，5月20日，4點51分，星期三28

（2）奇偶校驗碼奇偶校檢碼是只有一個校驗元的分組碼(n,n–1)，即k=n–1，其組成和方法如圖9.8所示。若每個碼字中1的個數(shù)為偶數(shù)，則為偶校驗；若每個碼字中1的個數(shù)為奇數(shù)，則為奇校驗。圖9.8奇偶校檢碼的組成和編碼方法9.2.2糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第29頁，共67頁，2022年，5月20日，4點51分，星期三29由于每個碼字均按同一規(guī)則構(gòu)成，所以奇偶校驗碼是一種－致校驗碼。碼的性能在接收端，譯碼過程包括檢驗碼字的各比特的模2和是否為0，如果結(jié)果是1，則代表碼字中存在錯誤。它是一種檢錯碼且只能檢測奇數(shù)個錯。假設(shè)所有比特發(fā)生錯誤的可能性是相同的，且相互獨立，則一個n比特長的符號發(fā)生j位錯誤的可能性為

(9.10)9.2.2糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第30頁，共67頁，2022年，5月20日，4點51分，星期三30設(shè)無法檢測的錯誤概率為Pnd，則有

(9.12)如果是奇校驗，則求和的上限值為(n–1)/2。 奇偶校驗碼特點：（1）d=2，能檢1個錯，也能檢奇數(shù)個錯；（2）R=(n–1)/n，編碼效率很高。隨著n的增大，編碼效率趨近于1，但d/n

則趨近于0，即抗干擾能力隨之下降。

9.2.2糾錯編碼的分類9.2糾錯編碼的基本概念及其本質(zhì)第31頁，共67頁，2022年，5月20日，4點51分，星期三31糾錯編碼的本質(zhì)是通過在發(fā)端的碼字中引入可控的冗余度換取傳輸可靠性的提高。以分組碼為例，它獲得糾、檢錯能力的本質(zhì)，是由于加入了(n–k)個監(jiān)督碼元。k個碼元的消息集合最多具有2k個消息組合，同樣，n個碼元的碼字集合最多具有2n個消息組合許用碼組的個數(shù)為2k而禁用碼組的個數(shù)為(2n–2k)。若由于錯誤使接收到的碼字落到了禁用碼組里，就必然可被檢測出來，同時也給糾正提供了可能，這取決于編碼的結(jié)構(gòu)。如果由于錯誤而使接收到的碼字落到了許用碼組里，則無無法判別是無錯還是有錯，從而造成不可檢測的錯誤。糾錯編碼的本質(zhì)9.2糾錯編碼的基本概念及其本質(zhì)第32頁，共67頁，2022年，5月20日，4點51分，星期三32這種以注入冗余度來獲取可靠性提高的方法，必然帶來信息傳輸速率的降低。但根據(jù)香農(nóng)第二定理，信息傳輸速率接近于信道容量且具有任意小錯誤概率的通信是存在的，即編碼效率接近于1且又能使錯誤概率任意小的信道編碼是存在的，這就給編碼工作者提出了嚴(yán)峻的課題。在后面幾章將會看到，人們發(fā)現(xiàn)的所謂“好碼”，主要是在同樣的編碼效率下具有更高的糾錯或檢錯功能。9.2糾錯編碼的基本概念及其本質(zhì)糾錯編碼的本質(zhì)第33頁，共67頁，2022年，5月20日，4點51分，星期三33編碼性能優(yōu)劣可以用最小碼距d的大小來表征。定理9.1

任一(n，k)分組碼，若要在碼字內(nèi)：

(1)檢測a

個隨機錯誤，則要求d≥a+1；

(2)糾正t

個隨機錯誤，則要求d≥2t+1；

(3)檢測a個并糾正t(t<a)個隨機錯誤，則要求d≥a+t+1。證明（1）可以由圖9.9(a)簡單證明：

9.3糾錯編碼方法的性能評價圖9.9(a)第34頁，共67頁，2022年，5月20日，4點51分，星期三34設(shè)一碼組A位于0點。若碼組A中發(fā)生一位錯碼，則可以認(rèn)為A的位置將移動至以0點為圓心、以1為半徑的圓上某點，但其位置不會超出此圓；若碼組A中發(fā)生兩位錯碼，則其位置不會超出以0點為圓心、以2為半徑的圓。因此，只要最小碼距不小于3（如圖中B點），在此半徑為2的圓上及圓內(nèi)就不會有其它碼組。這就是說，碼組A發(fā)生兩位以下錯碼時，不可能變成另一任何許用碼組，因而能檢測錯碼的位數(shù)等于2。同理，如果一種編碼的最小距離為d，則將能檢測(d–1)個錯碼；反之，若要求檢測a個錯碼，則最小碼距d至少應(yīng)不小于(a+1)。9.3糾錯編碼方法的性能評價第35頁，共67頁，2022年，5月20日，4點51分，星期三35

（2）可以圖9.9(b)來加以說明。

9.3糾錯編碼方法的性能評價圖9.9碼距與檢錯和糾錯能力的關(guān)系（b）第36頁，共67頁，2022年，5月20日，4點51分，星期三36圖中畫出碼組A和B的距離為5。碼組A或B若發(fā)生不多于兩位錯碼，則其位置均不會超出以原位置為圓心，以2為半徑的圓。若接收碼組落于以A為圓心的圓上，就判決收到的是碼組A；若落于以B為圓心的圓上，就判決為碼組B。這樣，就能夠糾正兩位錯碼。若這種編碼中除碼組A和B外，還有許多種不同碼組，但任兩碼組之間的碼距均不小于5，則以各碼組的位置為中心、以2為半徑畫出的圓都不會互相重疊。每種碼組如果發(fā)生不超過兩位錯碼都將能被糾正。因此，當(dāng)最小碼距d=5時，能夠糾正兩個錯碼，且最多能糾正兩個。若錯碼達到3個，就將落于另一圓上，從而發(fā)生錯判。為糾正t個錯碼，最小碼距d應(yīng)不小于(2t+1)。9.3糾錯編碼方法的性能評價第37頁，共67頁，2022年，5月20日，4點51分，星期三379.3糾錯編碼方法的性能評價(3)先說明什么是“檢測a個并糾正t(t<a)個錯誤”（簡稱“糾檢結(jié)合”）。在某些情況下，要求對于出現(xiàn)較頻繁但錯碼數(shù)很少的碼組，按前向糾錯方式工作，以節(jié)省反饋重發(fā)時間；同時又希望對一些錯碼數(shù)較多的碼組，在超過該碼的糾錯能力后，能自動按檢錯重發(fā)方式工作，以降低系統(tǒng)的總誤碼率。這種工作方式就是“糾檢結(jié)合”。在上述“糾檢結(jié)合”系統(tǒng)中，差錯控制設(shè)備按照接收碼組與許用碼組的距離自動改變工作方式。若接收碼組與某一許用碼組間的距離在糾錯能力t范圍內(nèi)，則按糾錯方式工作；若與任何許用碼組間的距離都超過t，則按檢錯方式工作。第38頁，共67頁，2022年，5月20日，4點51分，星期三38以圖9.9(c)來加以說明。設(shè)碼的檢錯能力為a，則當(dāng)碼組A中存在a個錯碼時，該碼組與任一許用碼組（例如圖中碼組B）的距離應(yīng)至少為t+1，否則將進入許用碼組B的糾錯能力范圍內(nèi)，而被錯糾為B。這樣就要求最小碼距d至少為a+t+1。9.3糾錯編碼方法的性能評價（c）圖9.9碼距與檢錯和糾錯能力的關(guān)系第39頁，共67頁，2022年，5月20日，4點51分，星期三399.4基于圖形的編碼編碼的主要挑戰(zhàn)是設(shè)計接近信道容量同時具備合理的譯碼復(fù)雜度的編碼方案。Turbo碼、低密度奇偶校驗碼（LDPC）等專門的Turbo類編碼采用簡單的迭代譯碼算法，在許多重要的信道上都能非常接近香農(nóng)極限，它們的共同特征是都可作為基于圖形的編碼來理解。圖形編碼方案在保持合理的譯碼復(fù)雜度的同時接近信道容量。低密度奇偶校驗碼、Turbo碼和大部分可譯的接近香農(nóng)極限的糾錯碼都可以理解成圖形編碼。圖形能構(gòu)造出用于迭代譯碼的和積譯碼算法。因式（因子）圖用來描述編碼以及在譯碼時必須處理的聯(lián)合概率分布。第40頁，共67頁，2022年，5月20日，4點51分，星期三409.4基于圖形的編碼9.4.1編碼的圖形建模（1）Tanner圖Tanner定義了一種稱為Tanner圖的二次分裂圖，將碼字的符號與這些符號必須滿足的限制聯(lián)系起來.Tanner還介紹了兩種基于圖形的譯碼算法，即和積算法和最小和算法。圖9.10給出（7，4）漢明碼的兩種Tanner圖。第41頁，共67頁，2022年，5月20日，4點51分，星期三41圖9.10（7，4）漢明碼的兩種Tanner圖：a)局部校驗;

b)全局校驗9.4基于圖形的編碼9.4.1編碼的圖形建模第42頁，共67頁，2022年，5月20日，4點51分，星期三429.4基于圖形的編碼9.4.1編碼的圖形建模圖9.10(a)有7個變量頂點，用圓圈表示，對應(yīng)每個碼字中的7個符號x1,x2,…,x7。三個校驗頂點，表示每個碼字必須滿足的二進制線性方程。一個有效碼字，它每個校驗頂點的鄰點（即與校驗頂點相連的變量）都必須形成模二和為零（即有偶數(shù)個1）的構(gòu)造。例如(x1,x2,…,x7)=(1,1,1,0,0,0,0)和(x1,x2,…,x7)=(0,1,1,1,0,1,0)是有效碼字，(x1,x2,…,x7)=(1,1,1,0,1,1,0)則不是，因為不是每個校驗式都滿足上述關(guān)系?？梢詫anner圖中的多個校驗頂點聚合成一個，如圖9.10(b)所示，稱為全局校驗，而將圖9.10(a)的形式稱為局部校驗。第43頁，共67頁，2022年，5月20日，4點51分，星期三439.4基于圖形的編碼9.4.1編碼的圖形建模（2）因式圖通常將含有狀態(tài)變量的Tanner圖稱為因式圖。圖9.11(a)是(7,4)漢明碼的格圖，圖9.11(b)是對應(yīng)的因式圖。格圖中從最左邊頂點出發(fā)向右一系列路徑上的標(biāo)示代表漢明碼的16個碼字。輔助變量s0,s1,…,s7不直接表示碼字符。第i個格區(qū)約束了(si-1,xi,si)的可能的組合；事實上，在此線性格圖的例子里，這些三元組總能形成線性碼。

第44頁，共67頁，2022年，5月20日，4點51分，星期三44圖9.11

(a)（7，4）漢明碼的trellis圖；(b)對應(yīng)的因式圖

第45頁，共67頁，2022年，5月20日，4點51分，星期三459.4基于圖形的編碼9.4.1編碼的圖形建模例如，第3個格區(qū)由（00,1,01），（01,0,10）等8個線性組合構(gòu)成了局部編碼。這碼可以認(rèn)為是二進制（5,3）碼，如圖9.11(b)所示。注意到狀態(tài)變量通常并不是二進制的，圖9.11(b)的因式圖用并行線的數(shù)量對應(yīng)構(gòu)成每個狀態(tài)變量的比特數(shù)。兩端的狀態(tài)s0和s7規(guī)定總為0，因此實際上它們是零比特變量或常量，于是它們與圖9.11(b)因式圖的連接用虛線表示。第46頁，共67頁，2022年，5月20日，4點51分，星期三469.4基于圖形的編碼9.4.1編碼的圖形建模因式圖可用于建模許多編碼結(jié)構(gòu)。例如Turbo碼便是根據(jù)圖9.12(a)所示編碼原理構(gòu)成的。此編碼器輸入k信息比特x=(x1,…,xk)，產(chǎn)生兩個不同的奇偶校驗比特流p=(p1,…,pk)和q=(q1,…,qk)，選擇(x,p)對和(x,q)對，使其分別是(2k,k)碼C1和C2中的碼字，通常選擇C1和C2為同樣的編碼器，圖中Π代表信息比特的置換，即用于計算q的信息比特與p的相同，但順序不同。圖9.12(b)是對應(yīng)的因式圖，其組成碼均由單個校驗頂點建模而成。在圖9.12(c)中，這些全局校驗被分解為與C1和C2的格圖表示相對應(yīng)的鏈狀圖。第47頁，共67頁，2022年，5月20日，4點51分，星期三47圖9.12(a)并行鏈接碼的編碼；(b)對應(yīng)的因式圖；(c)格圖結(jié)構(gòu)碼的因式圖第48頁，共67頁，2022年，5月20日，4點51分，星期三489.4基于圖形的編碼9.4.2采用和積算法譯碼當(dāng)考慮到譯碼問題時，基于圖形建模的編碼的作用就顯現(xiàn)出來了。譯碼本質(zhì)上是一個統(tǒng)計推導(dǎo)問題：給定一系列的觀察（噪聲信道輸出對發(fā)送的碼字的響應(yīng)），推測最有可能發(fā)送的是哪一個碼字（ML譯碼），或者各碼元最可能的取值（逐碼元MAP譯碼）。和積算法試圖通過沿著因式圖的邊線傳遞消息的方式來解決逐碼元MAP譯碼問題。第49頁，共67頁，2022年，5月20日，4點51分，星期三499.4基于圖形的編碼9.4.2采用和積算法譯碼（1）概率質(zhì)量函數(shù)的因式圖表示因式圖可用來建模編碼，也可用于表示一個含許多變量的函數(shù)的因式分解結(jié)構(gòu)。例如，設(shè)函數(shù)g(x1,…,x7)可因式分解為3個函數(shù)f1(x1,x2,x4,x5)、f2(x2,x3,x4,x6)和f3(x4,x5,x6,x7)的乘積，則g的因式圖同圖9.11(b)所示漢明碼因式圖的結(jié)構(gòu)一樣，只是校驗頂點由對應(yīng)于f1、f2和

f3的因式頂點代替。設(shè)g是自變量x1,…,xn,的某種全局函數(shù)，且g=，其中各個fj是以x1,…,xn的某個子集為自變量的局部函數(shù)。因式圖表示g的因式分解具有n個變量頂點和m個因式頂點。當(dāng)且僅當(dāng)xi是fj的一個自變量時，變量頂點xi和因式頂點fj之間有一條邊連接。第50頁，共67頁，2022年，5月20日，4點51分，星期三509.4基于圖形的編碼9.4.2采用和積算法譯碼標(biāo)識函數(shù)是因式圖應(yīng)用中的重要函數(shù)。若P(x1,…,xn)是對變量x1,…,xn的某種預(yù)測，則P的標(biāo)識函數(shù)記作[P]，當(dāng)P在x1,…,xn構(gòu)造上判為真時就取值1，反之為0。例如[x1x2…xn

=0]判為1，當(dāng)且僅當(dāng)二進制變量x1,…,xn構(gòu)成偶校驗式。僅當(dāng)所有的標(biāo)識函數(shù)都判為1時它們的積判為1。由此，如果g(x1,…,x7)是f1

、f2

和f3

的乘積，g判為1當(dāng)且僅當(dāng)f1

、f2

和f3都判為1時，即當(dāng)且僅當(dāng)變量x1,…,xn滿足定義(7,4)漢明碼的3個奇偶校驗方程時。因此g可看作是碼成員關(guān)系的標(biāo)識函數(shù)g=[(x1,…,x7

)C]，其中C表示(7,4)漢明碼。由此，圖9.10(a)一是理解為漢明碼的Tanner圖，另一個是理解為漢明碼成員關(guān)系標(biāo)識函數(shù)的因式圖。第51頁，共67頁，2022年，5月20日，4點51分，星期三519.4基于圖形的編碼9.4.2采用和積算法譯碼

碼成員關(guān)系標(biāo)識函數(shù)還可看作是概率質(zhì)量函數(shù)，表示在二進制n元組上的分布，在碼字上是均勻分布的，而非碼字上的分布為0。假設(shè)據(jù)此選出一碼字x=(x1,…,xn)C，將它在無記憶信道上發(fā)送，接收到的矢量為y=(y1,…,yn)。無記憶性表明其聯(lián)合概率密度函數(shù)p(y,x)可分解因式成p(y,x)=p(x)，其中p(x)是[xC]的標(biāo)量形式。對任何給定的接收y，后驗概率質(zhì)量函數(shù)p(x|y)由函數(shù)g(x1,…,xn

)=[(x1,…,xn

)C]乘以一個比例因子給定，其中x1,…,xn是的g的自變量，且給定的y1,…,yn作為固定參數(shù)使用。第52頁，共67頁，2022年，5月20日，4點51分，星期三529.4基于圖形的編碼9.4.2采用和積算法譯碼當(dāng)然，g(x1,…,xn)具有較好的因式分解結(jié)構(gòu)，所以可用因式圖表示。這樣的因式圖具有和C一樣的因式圖結(jié)構(gòu)，除了與變量頂點xi相連的是表示p(yi|xi)的待定因式頂點。此待定頂點表示在任何給定的譯碼問題中必須處理的確證。這樣的確證頂點如圖9.13所示，圖中(a)所示的方向表示左至右消息mxf，概括了左邊子圖中收集的確證，(a)所示的方向表示右至左消息mf

x

，概括了右邊子圖中收集的確證。第53頁，共67頁，2022年，5月20日，4點51分，星期三53圖9.13樹圖中的和積算法運算過程第54頁，共67頁，2022年，5月20日，4點51分，星期三549.4基于圖形的編碼9.4.2采用和積算法譯碼（2）非循環(huán)因式圖中的和積算法計算碼元xi的后驗概率質(zhì)量函數(shù)p(xi|y)時，逐碼元最大后驗（MAP）譯碼要求能夠選擇出與xi最相似的值。顯然函數(shù)g(x1,…,xn)表示標(biāo)乘一個比例因子后的聯(lián)合后驗概率質(zhì)量函數(shù)。計算p(xi|y)需進行邊界化運算，即計算：和積算法用于同時計算各個邊界值，只要所需處理的因式是非循環(huán)的，就可以得到有效和精確的計算結(jié)果。和積算法可以理解成沿著因式圖的邊線傳遞消息的運算。第55頁，共67頁，2022年，5月20日，4點51分，星期三559.4基于圖形的編碼9.4.2采用和積算法譯碼消息的本質(zhì)首先，消息就是函數(shù)。因式圖的邊線總是連著變量頂點x和函數(shù)頂點f，如圖9.13所示。消息可以沿這條邊線以任何方向通過（xf

或fx）。在與變量x相連的邊線上傳遞的消息總是定義x的符號集上的函數(shù)。例如設(shè)x是定義在符號集{0，1}上的二進制變量，則在與x相連的任何邊線上傳遞的消息都是形如μ(x)的函數(shù)。此函數(shù)可由矢量[μ(0),μ(1)]或比率μ(0)/μ(1)及l(fā)b[μ(0)/μ(1)]表示。由此，消息就是一個一系列值所指定的函數(shù)。我們將從變量頂點x到因式頂點f的消息記為μx

f(x)，而從因式頂點f到變量頂點x的消息記為μfx

(x)。第56頁，共67頁，2022年，5月20日，4點51分，星期三569.4基于圖形的編碼9.4.2采用和積算法譯碼

因為消息就是函數(shù)，因此可像函數(shù)一樣作乘積運算。由此，如果μ1(x)和μ2(y)分別是x和y的函數(shù)，則它們的積μ1(x)μ2(y)是（x,y）的函數(shù)。和積算法由兩個更新準(zhǔn)則和一個終止準(zhǔn)則定義。用N(v)表示因式圖中頂點v的鄰點集合。如果wN(v)，則v和w有公共邊線，且集合N(v)\w表示除w外與v相鄰的點。變量頂點的更新準(zhǔn)則：由變量頂點x到相鄰的因式頂點fN(x)的消息μxf表示為(9.13)即由變量頂點x發(fā)送到相鄰的因式頂點fN(x)的消息，可由在x處收到的來自除f外所有鄰點的消息的乘積得到。第57頁，共67頁，2022年，5月20日，4點51分，星期三579.4基于圖形的編碼9.4.2采用和積算法譯碼因式頂點的更新準(zhǔn)則：從因式頂點f到相鄰的變量頂點xN(f)={x,y1,y2,…,ym}的消息μfx

由下式得到：(9.14)即由f到相鄰的變量頂點x的消息得到：先將f處來自除x外其他鄰點的消息與f相乘，再對得到的函數(shù)關(guān)于x邊界化。終止準(zhǔn)則：x的邊界函數(shù)由下式得到：(9.15)即x的邊界函數(shù)是x收到的所有消息的乘積。第58頁，共67頁，2022年，5月20日，4點51分，星期三589.4基于圖形的編碼9.4.2采用和積算法譯碼

在非循環(huán)因式圖中，由任何頂點v發(fā)出的消息都可以計算并沿邊線e送出，只要能得到沿除e外其他所有邊線到達v的消息。由此可知，消息傳遞始于葉狀頂點，因為這些點能在一開始時提供所有需要的信息。一旦每個變量頂點都已收到所有鄰點的消息，則算法終止。對于一個含E條邊線的有限非循環(huán)因式圖，不超過2E步便可滿足終止條件（即一條邊線上不再需要發(fā)送超過兩條消息，每個消息一個方向）。定理9.2

在一個表示函數(shù)g(x1,…,xn)的有限非循環(huán)因式圖中，由和積算法根據(jù)式(9.15)計算得的函數(shù)μ(xi)是xi.的邊界函數(shù)。第59頁，共67頁，2022年，5月20日，4點51分，星期三599.4基于圖形的編碼9.4.2采用和積算法譯碼當(dāng)g(x1,…,xn)表示在給定某個觀察確證點e下n個隨機變量的條件概率質(zhì)量函數(shù)p(x1,…,xn|e)時，非循環(huán)因式圖中和積算法運算過程中所傳遞的消息具有特定的含義。非循環(huán)因式圖的每條邊線都促使圖形劃分為兩個子圖，即左子圖和右子圖，且將確證分為左確證el和右確證er，分別和左、右子圖相連。消息μx

f

(x)是給定左確證條件下x的條件概率質(zhì)量函數(shù)。消息μfx

(x)是給定右確證條件下x的條件概率質(zhì)量函數(shù)。這些消息的乘積就是給定所有確證時x的條件概率質(zhì)量函數(shù)。第60頁，共67頁，2022年，5月20日，4點51分，星期三60

非循環(huán)因子圖的一個重要例子就是格圖。在描述格圖的鏈形因式圖中，和積算法的運算導(dǎo)致了消息沿因式圖邊線的前向和后向傳播(如圖9.12(b)所示)，從而得到了著名的前向/后向算法或稱BCJR算法。前向傳播消息常用符號α表示，后向傳播消息用β表示。從非循環(huán)因式圖中對消息的一般闡述的觀