信道編碼上課

1、信道編碼,2024/1/21,2,第6章 信道編碼,目的：了解信道編碼的作用與意義掌握幾種典型的信道編碼、譯碼方法對信道編碼的研究方法和成果有基本認(rèn)識，為進(jìn)一步研究打下基礎(chǔ)特點：基本概念、物理意義、基本方法為主,2024/1/21,3,主要內(nèi)容,基本概念和方法線性分組碼循環(huán)碼（實驗）BCH卷積碼,2024/1/21,4,6.1 用于可靠傳輸和存儲數(shù)據(jù)的編碼,信道編碼的引入信道編碼的基本思想編碼系統(tǒng)模型,2024/1

2、/21,5,6.1 用于可靠傳輸和存儲數(shù)據(jù)的編碼 ——信道編碼的引入,移動通信,通信網(wǎng),小張,小李,,2024/1/21,6,6.1 用于可靠傳輸和存儲數(shù)據(jù)的編碼 ——信道編碼的引入,通信的目的在于傳輸信息通信系統(tǒng)主要質(zhì)量指標(biāo)是通信的有效性和可靠性在實際信道上傳輸信號時，由于信道傳輸特性不理想及噪聲的影響，接收端收到的

3、信號不可避免地會發(fā)生錯誤,,發(fā)送端,,接收端,干擾,2024/1/21,7,6.1 用于可靠傳輸和存儲數(shù)據(jù)的編碼 ——信道編碼的引入,隨著差錯控制編碼理論的完善和數(shù)字電路技術(shù)的發(fā)展，信道編碼不僅應(yīng)用于各種通信系統(tǒng)中，在計算機(jī)存儲、運(yùn)算系統(tǒng)以及超大規(guī)模集成電路的設(shè)計中也得到日益廣泛的應(yīng)用。,2024/1/21,8,6.1 用于可靠傳輸和存儲數(shù)據(jù)的編碼

4、 ——信道編碼的作用,,信道編碼是在數(shù)據(jù)傳輸/存儲中所采用的降低系統(tǒng)差錯率，提高系統(tǒng)可靠性的一種數(shù)字處理技術(shù)。,2024/1/21,9,6.1 用于可靠傳輸和存儲數(shù)據(jù)的編碼 ——信道編碼的基本思想,通過對信息碼元序列作某種變換,即增加一定數(shù)量的多余碼元，使原來彼此相互獨立、沒有關(guān)聯(lián)的信息碼元,經(jīng)過變換后,產(chǎn)生某種規(guī)律性或相關(guān)性,從而在接收端可根據(jù)這種規(guī)律性來檢查、糾正傳輸序列中

5、的差錯。編碼的實質(zhì)——利用冗余降低差錯概率。,2024/1/21,10,6.1 用于可靠傳輸和存儲數(shù)據(jù)的編碼 ——信道編碼的基本思想,舉例：ASCII碼的偶校驗過程ASCII碼：7bit表示符號，例如“L”的ASCII是 0011001偶校驗：使得編碼后輸出的碼字中“1”的個數(shù)為偶數(shù) 0011001->00110011接收端驗證“1”的個數(shù)是否為偶數(shù)這一“規(guī)律

6、”（關(guān)系）是否成立來檢驗錯誤是否發(fā)生,啟示需要增加冗余碼元（8，7） 監(jiān)督碼元與信息碼元建立了一組關(guān)系 接收端利用這組關(guān)系檢查和糾正錯誤,2024/1/21,11,6.1 用于可靠傳輸和存儲數(shù)據(jù)的編碼 ——編碼系統(tǒng)模型,,,信源：輸出的是信息序列（信息碼元）信道：廣義信道，也稱編碼信道,,,,,2024/1/21,12,信息序列

7、：mi=[mi1 , mi2 ,…, mik],編碼后的發(fā)送序列：Ci=[Ci1 , Ci2 ,… , Cin],,,受到干擾后的接收序列：ri=[ri1 , ri2 ,…, rin],,信息序列：m’i=[m’i1 , m’i2 , … , m’ik],,編碼,譯碼,,發(fā)送端,接收端,信道（干擾）,編碼系統(tǒng)模型下的數(shù)字序列變換,2024/1/21,13,6.1 用于可靠傳輸和存儲數(shù)據(jù)的編碼 ——編

8、碼系統(tǒng)模型,三點說明：1.不可無限的增加冗余碼2.盡可能的重現(xiàn)m，即 使m′盡量接近m3.編譯碼算法易實現(xiàn)，設(shè)備費(fèi)用盡量低,研究各種編碼和譯碼方法是信道編碼所要解決的問題。,,噪聲干擾,2024/1/21,14,6.2 錯誤類型與信道模型,,噪聲干擾,,,輸入,輸出,,轉(zhuǎn)移概率,,2024/1/21,15,6.2 錯誤類型與信道模型,隨機(jī)錯誤和隨機(jī)信道突發(fā)錯誤和突發(fā)信道混合錯誤和混合信道,2024/1/21,16,6.2 錯誤

9、類型與信道模型,隨機(jī)錯誤和隨機(jī)信道隨機(jī)錯誤：各碼元是否出現(xiàn)錯誤，與前、后碼元是否差錯沒有關(guān)系，每個碼元獨立的按一定的概率發(fā)生差錯。一般是由加性高斯白噪聲引起的。只存在隨機(jī)錯誤的信道稱為無記憶信道/隨機(jī)信道，用信道轉(zhuǎn)移概率來描述。比如，二進(jìn)制對稱信道BSC。,2024/1/21,17,二進(jìn)制對稱信道（Binary Symmetric Channel, BSC）,,P(1/0)=pP(0/1)=pP(1/1)=1-pP(0/0)

10、=1-p,,輸入符號取值集合 X={0，1},輸出符號取值集合 Y={0，1},,,,0,,,1,0,1,X,Y,p,p,1-p,1-p,6.2 錯誤類型與信道模型,2024/1/21,18,6.2 錯誤類型與信道模型,突發(fā)錯誤和突發(fā)信道突發(fā)錯誤：噪聲對各傳輸碼元的影響不是獨立的，從而導(dǎo)致差錯是一連串出現(xiàn)的。例如移動通信中信號在某一段時間內(nèi)發(fā)生衰落，造成一串差錯；光盤上的一條劃痕等。存在突發(fā)錯誤的信道，稱之為有記憶信道/突發(fā)信

11、道。,2024/1/21,19,6.2 錯誤類型與信道模型,混合錯誤和混合信道混合錯誤：既有突發(fā)錯誤又有隨機(jī)錯誤。突發(fā)錯誤和隨機(jī)錯誤并存的信道稱之為混合信道。,2024/1/21,20,錯誤圖樣： 設(shè)發(fā)送的是序列C（碼元長度為n），通過信道傳輸后，接收端的序列為R。由于在傳輸過程中受到信道噪聲干擾，R序列中的某些元素和C序列中的對應(yīng)碼元的值可能不同，如果信道中的噪聲干擾采用二進(jìn)制序列e表示，相應(yīng)有錯誤的位取值為1，無錯的位取值為

12、0，可得 e=C R,6.2 錯誤類型與信道模型,2024/1/21,21,例：發(fā)送序列C：（1111100000），收到的序列R：（1001010000），第二、三、五、六位產(chǎn)生了錯誤，因此錯誤圖樣e的二、三、五、六位取值為1，即e：(0110110000)對于突發(fā)信道，錯誤圖樣中，第一個“1”和最后一個“1”之間的碼元總個數(shù)稱為突發(fā)長度，其圖樣稱為突發(fā)圖樣。該例中，突發(fā)圖樣是（11011），突發(fā)長度為5。,6.2

13、 錯誤類型與信道模型,2024/1/21,22,6.3 差錯控制的基本方式,反饋重傳方式 前向糾錯方式 混合方式,2024/1/21,23,6.3 差錯控制的基本方式,反饋重傳方式(Automatic Repeat reQuest, ARQ)工作原理：發(fā)送端發(fā)送的是檢錯碼，通過信道傳輸?shù)浇邮斩耍邮斩俗g碼器只需根據(jù)編碼規(guī)則判斷是否有錯誤，并把判決信號通過反饋信道送回發(fā)送端。發(fā)送端根據(jù)判決信號將收端認(rèn)為有錯誤的重新發(fā)送，直到接收端檢

14、查無誤為止。,2024/1/21,24,6.3 差錯控制的基本方式,發(fā)端,收端,,檢錯碼,,判決信號,反饋重傳方式(Automatic Repeat reQuest, ARQ)分為兩類：等待式和連續(xù)式,2024/1/21,25,6.3 差錯控制的基本方式,,前向糾錯方式 (Forward Error Correction, FEC)工作原理：發(fā)送端發(fā)送能糾正錯誤的碼字，在接收端根據(jù)接收到的碼字和編碼規(guī)則，能自動糾正傳輸中的錯誤。

15、不需要反饋信道，實時性好。隨著糾錯能力的提高，編譯碼設(shè)備復(fù)雜。,2024/1/21,26,6.3 差錯控制的基本方式,,混合方式 (Hybrid Error Correction, HEC)工作原理：結(jié)合前向糾錯和ARQ的系統(tǒng)，在糾錯能力范圍內(nèi)，自動糾正錯誤，超出糾錯范圍則要求發(fā)送端重新發(fā)送?！壑苑桨?。,2024/1/21,27,6.4 信道編碼的分類,按差錯控制編碼的不同功能：檢錯碼：發(fā)現(xiàn)錯誤的碼糾錯碼：自動糾正錯誤的

16、碼按信息碼元與附加監(jiān)督碼元間檢驗關(guān)系：線性碼(Linear Code)：監(jiān)督碼元與信息碼元滿足線性關(guān)系非線性碼(Nonlinear Code)：監(jiān)督碼元與信息碼元不滿足線性關(guān)系,2024/1/21,28,6.4 信道編碼的分類,按信息碼元與監(jiān)督碼元間約束方式：分組碼(Block Code)：信息序列每k位分成一組，產(chǎn)生r位監(jiān)督元，輸出長度為n=r+k的碼字。r位監(jiān)督元只與本分組的k位信息元有關(guān)，記為（n, k）。卷積碼(Con

17、volutional Code)：編碼器給每k0位信息加上r0位監(jiān)督元得到長度為n0的碼字。該碼字的運(yùn)算，不僅與本組k0位信息有關(guān)，還與其前面m組k0位信息有關(guān)。稱這種碼為（n0，k0，m）卷積碼。,2024/1/21,29,6.4 信道編碼的分類,按信息碼元在編碼后是否保持原來的形式：系統(tǒng)碼、非系統(tǒng)碼按糾正錯誤的類型：糾正隨機(jī)錯誤的碼、糾正突發(fā)錯誤的碼按每個碼元取值：二進(jìn)制碼、多進(jìn)制碼,2024/1/21,30,6.4 信道

18、編碼的分類,2024/1/21,31,6.5 信道編碼定理,香農(nóng)信道編碼定理性能指標(biāo)分組碼及相關(guān)基本概念,2024/1/21,32,6.5 信道編碼定理,香農(nóng)信道編碼定理 對于一個給定的有擾信道，若信道的容量為C，只要發(fā)送端以低于C的速率發(fā)送信息，則一定存在一種編碼方法，使譯碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值，表示為 這里E(R)稱為可靠性函數(shù)。,2024/1/21,33,6.

19、5 信道編碼定理,定理告訴我們：當(dāng)信息速率小于信道容量時，總存在一種編碼方式使差錯率低于任一給定值ε；為減小差錯概率，可增大碼長n或增大E(R) 增大E(R)可：可以增大信道容量；（增大帶寬、增大功率、降低噪聲）減小碼率；,2024/1/21,34,6.6線性分組碼,分組碼及參數(shù)分組碼：將信息序列分成k位一組，按照一定的校驗關(guān)系增加r位校驗位，構(gòu)成n(n=k+r)位碼分組，稱為碼字（Code words )，所有可能碼字

20、構(gòu)成的集合稱為一個分組碼，記為(n,k)分組碼分組碼的校驗關(guān)系僅限于一個碼分組之內(nèi),2024/1/21,35,6.6線性分組碼,分組碼及參數(shù)主要參數(shù)：信息分組：m=(mk-1 mk-2 … m1 m0)碼字：C=(cn-1 cn-2 … c1 c0)碼長n，信息位個數(shù)k，校驗位個數(shù)r=n-k碼字個數(shù)(二進(jìn)制)：2k編碼效率：R=k/n,2024/1/21,36,6.6 線性分組碼,許用碼組、禁用碼組（n，k）碼中有2k

21、個n重碼字。但是n bit的二進(jìn)制序列具有2n種不同的組合序列；分組碼的編碼規(guī)則就是從2n種不同序列中選擇2k個碼字，建立信息序列與碼字的對應(yīng)關(guān)系；,這2k個碼字組成的集合稱為許用碼組，剩余的2n-2k個n重向量組成的集合稱為禁用碼組。,2024/1/21,37,6.6 分組碼基本概念,碼重、碼距 碼重：碼字中非0碼元的個數(shù)，又稱漢明重量。 例如碼字 x=(11000)，則碼重w(x)=2 碼距：碼字x與碼字y對應(yīng)位取值不同的

22、個數(shù)，又稱為漢明距離。 例如：x=(10111101)，y=(01110101),2024/1/21,38,6.6 分組碼的基本概念,最小碼距（最小漢明距離）最小碼距：（n，k）分組碼中，任何兩個碼字之間距離的最小值，稱為該分組碼的最小漢明距離，簡稱最小距離，用d表示。最小碼距描述分組碼特性的重要參量，決定了碼的糾錯、檢錯性能。(n,k)分組碼通常也記為(n,k,d)分組碼。,2024/1/21,39,6.6 分組碼的基本概念

23、,最小碼距（最小漢明距離）[例]： (2,1)重復(fù)碼，{00,11} d=？ (3,1)重復(fù)碼，{000,111}d=？(4,1)重復(fù)碼，{0000, 1111} d=？,2024/1/21,40,6.6 分組碼的基本概念,最小漢明距離譯碼準(zhǔn)則：在許用碼組中，判斷與接收序列r “最近”的碼字為發(fā)送碼字,2024/1/21,41,分組碼的檢糾錯能力,分組碼的檢糾錯能力碼的最小距

24、離為d0 = e+1，其檢錯能力為e。,2024/1/21,42,分組碼的檢糾錯能力,分組碼的檢糾錯能力糾錯能力：一個(n,k)分組碼，如果能糾正碼字內(nèi)的所有小于或等于t個(位)錯誤，則稱該碼的糾錯能力為t,2024/1/21,43,分組碼的檢糾錯能力碼的最小距離為d0 = 2t+1，其糾錯能力為t。且當(dāng)d*=2t+1或d*=2t+2時，都不能糾正t+1個錯誤。,2024/1/21,44,分組碼的檢糾錯能力,分組碼的檢糾錯能力同時

25、糾檢錯能力：一 (n,k)分組碼，如果能糾正碼字內(nèi)的所有小于或等于t個(位)錯誤，同時又能檢出所有小于或等于e(e >t)個(位)錯誤，則稱該碼的同時糾檢錯能力為糾t個錯同時檢e個錯。,2024/1/21,45,分組碼的檢糾錯能力碼最小碼距 d0=e+t+1， 其中e>t，該碼能夠糾正t個錯誤，同時檢測e個錯誤。,2024/1/21,46,6.7 幾種常用的編碼方式,奇偶校驗(監(jiān)督)碼水平一致監(jiān)督碼水平垂直一致監(jiān)督碼

26、群計數(shù)碼恒比碼（等重碼）,2024/1/21,47,6.7 幾種常用的編碼方式,奇偶校驗碼是(n,n-1)碼。假設(shè)奇偶校驗碼的碼字表示為偶校驗碼：加入監(jiān)督位后，碼字中“1”的個數(shù)為偶數(shù)個，即所有位的模二和為0。 （即偶數(shù)個1）,2024/1/21,48,6.7 幾種常用的編碼方式,奇偶監(jiān)督（校驗）碼奇校驗碼：加入監(jiān)督位后碼字中“1

27、”的個數(shù)為奇數(shù)個，即所有位的模二和為1。 （即奇數(shù)個1）可以檢測任意奇數(shù)個錯誤；構(gòu)造簡單，易于實現(xiàn)，在計算機(jī)內(nèi)部數(shù)據(jù)傳送和輸入輸出設(shè)備中經(jīng)常使用。,2024/1/21,49,6.7 幾種常用的編碼方式,水平一致監(jiān)督碼將原信息序列以適當(dāng)長度排成一行，如每k位信息為一行，設(shè)共有m行。對每行進(jìn)行偶（奇）校驗經(jīng)，構(gòu)成(m(k+1),mk)分

28、組碼傳輸時按列傳輸；譯碼時排成表，檢驗每行的校驗關(guān)系,2024/1/21,50,6.7 幾種常用的編碼方式,水平一致監(jiān)督碼可以發(fā)現(xiàn)所有長度b≤m的單個突發(fā)錯誤,2024/1/21,51,6.7 幾種常用的編碼方式,水平垂直一致監(jiān)督碼經(jīng)奇偶校驗后的若干碼字排列成矩陣，每個碼字排成一行，然后再按列的方向增加垂直校驗位，就構(gòu)成了二維奇偶校驗碼((m(k+1)+k,mk)傳輸時可以按行傳輸，也可以按列傳輸。,2024/1

29、/21,52,6.7 幾種常用的編碼方式,水平垂直一致監(jiān)督碼,2024/1/21,53,6.7 幾種常用的編碼方式,水平垂直一致監(jiān)督碼糾檢錯能力強(qiáng)：可檢測每一行中奇數(shù)個錯和每一列中奇數(shù)個錯；二維奇偶碼適用于檢測突發(fā)錯誤。如果采用按照列的順序傳輸，可以發(fā)現(xiàn)長度t≤m+2的突發(fā)錯；如果按照行的順序傳輸，可以發(fā)現(xiàn)t ≤k+2。應(yīng)用于穿孔紙帶、磁帶記錄系統(tǒng)中。,2024/1/21,54,6.7 幾種常用的編碼方式,群計數(shù)碼將碼字中“1

30、”的計數(shù)值作為監(jiān)督碼元例如，信息組為01011，共3個1，用011表示，得到(8,5)碼。群計數(shù)碼的碼字為01011011檢錯能力很強(qiáng)，除了0錯成1和1錯成0成對發(fā)生的情況外，其它形式的錯誤都能發(fā)現(xiàn)。為了降低發(fā)送碼元中的冗余度，有時只傳送計數(shù)碼元中最后幾位。特別的只傳輸最后1位監(jiān)督元，則群計數(shù)碼變成奇偶校驗碼,2024/1/21,55,6.7 幾種常用的編碼方式,恒比碼碼字中“1”和“0”的個數(shù)保持相同的比例，即每個碼字中1的個

31、數(shù)相同。恒比碼的譯碼可以采用查表方法，檢錯時查1或0的個數(shù)。恒比碼是一種檢錯碼。恒比碼一般用在電報。,2024/1/21,56,6.7 幾種常用的編碼方式,恒比碼例：發(fā)漢字電報時，每個漢字用4位阿拉伯?dāng)?shù)字表示，每個阿拉伯?dāng)?shù)字用5個比特的碼字表示。由于阿拉伯?dāng)?shù)字只有10個，因此從32中可能的碼字中挑出 =10個1的個數(shù)為3的碼字作為阿拉伯?dāng)?shù)字的編碼方式。,2024/1/21,57,6.8 信道編碼理論的發(fā)展歷史,1948年香

32、農(nóng)（Shannon）在其論文《通信中的數(shù)學(xué)理論》中提出有擾信道編碼定理——奠定了信道編碼的基石。50年代至60年代初，信道編碼從無到有得到了迅速的發(fā)展：奠定了線性分組碼的理論基礎(chǔ)；提出了著名的BCH碼編譯碼方法以及卷積碼的序列譯碼。,,2024/1/21,58,6.8信道編碼理論的發(fā)展歷史,60年代至70年代初，信道編碼發(fā)展最為活躍的時期：提出了門限譯碼、迭代譯碼、軟判決譯碼和維特比譯碼等有效的譯碼方法，并注重糾錯碼的實用化；在此期間

33、以代數(shù)方法特別以有限域理論為基礎(chǔ)的線性分組碼理論趨于成熟。,,2024/1/21,59,70年代至80年代，理論上，戈帕（Goppa）為首的一批學(xué)者構(gòu)造了一類Goppa碼，其中的子碼能達(dá)到香農(nóng)碼所能達(dá)到的性能，這在糾錯碼的發(fā)展史上具有劃時代的意義；在實際應(yīng)用中，70年代初發(fā)射的旅行者號宇宙飛船成功應(yīng)用了糾錯碼技術(shù)，從30億公里的距離向地面?zhèn)骰亓颂焱跣恰⒑Ｍ跣堑刃求w的天文圖片。,1.8信道編碼理論的發(fā)展歷史,2024/1/21,60,6.

34、8 信道編碼理論的發(fā)展歷史,80年代以來，戈帕等學(xué)者從幾何觀點討論分析糾錯碼，利用代數(shù)曲線構(gòu)造了一類代數(shù)幾何碼，其中的某些碼達(dá)到了香農(nóng)碼所能達(dá)到的性能；計算機(jī)的推廣應(yīng)用極大促進(jìn)了糾錯碼的發(fā)展，1993年，法國學(xué)者提出了性能接近香農(nóng)限的Turbo碼，其優(yōu)異的性能引起了信息與編碼理論界的轟動，信道編碼在實際中得到了更加廣泛的應(yīng)用。,2024/1/21,61,6.8 信道編碼理論的發(fā)展歷史,隨著網(wǎng)絡(luò)編碼理論的提出與發(fā)展，2002年蔡寧和楊偉豪

35、提出了網(wǎng)絡(luò)糾錯碼的概念，將傳統(tǒng)糾錯碼思想推廣到經(jīng)典網(wǎng)絡(luò)編碼領(lǐng)域。2006年起逐漸引起其他學(xué)者重視，目前已形成了網(wǎng)絡(luò)糾錯碼的理論基礎(chǔ)，為后續(xù)研究提供了方向。,,,6.8 信道編碼理論的發(fā)展歷史,2024/1/21,63,作業(yè),描述基本的數(shù)字通信系統(tǒng)模型描述信道編碼的作用、基本思想和編碼系統(tǒng)模型。發(fā)送端發(fā)送的碼字為（100100），經(jīng)信道傳輸后，接收端接收到的信息序列為（000101），求錯誤圖樣。簡要介紹幾種差錯控制方式。書Pag