差錯(cuò)控制的基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

(9.1)

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

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

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

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

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

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

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

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

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

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

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

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

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

,m)，或稱為(n0,k0

,m)碼。

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

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

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

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

(9.4)定義9.4

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

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

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

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

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

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

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

–1,cn

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

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

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

(9.8)

對(duì)于卷積碼，有R=k0/n0

(9.9)

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

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

越大，糾錯(cuò)能力越強(qiáng)。若未編碼時(shí)接收的錯(cuò)誤概率為

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

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

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

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

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

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

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

(1)檢測(cè)a

個(gè)隨機(jī)錯(cuò)誤，則要求d≥a+1；

(2)糾正t

個(gè)隨機(jī)錯(cuò)誤，則要求d≥2t+1；

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

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

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

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

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

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

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

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

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

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

、f2

和f3

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

、f2

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

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

碼成員關(guān)系標(biāo)識(shí)函數(shù)還可看作是概率質(zhì)量函數(shù)，表示在二進(jìn)制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)量形式。對(duì)任何給定的接收y，后驗(yàn)概率質(zhì)量函數(shù)p(x|y)由函數(shù)g(x1,…,xn

)=[(x1,…,xn

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

x

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

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

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

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

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

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

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

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

f

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

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

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