有擾離散信道的編碼定理課件

2019年6月261編碼調(diào)制的設(shè)計有兩條基本途徑是什么?

一條是代數(shù)途徑，即運用編,解碼技術(shù)來設(shè)計特定種類的碼，比如分組碼、卷積碼等。

第二條途徑是采用概率方法，在給定信道特性的條件下對編碼信號的性能作統(tǒng)計分析，求出差錯概率的上下限邊界，其中最優(yōu)碼所能達到的差錯概率的上界，稱作隨機碼界。用這種方法不能得知最優(yōu)碼是如何具體編出來的，卻能得知最優(yōu)碼可以好到什么程度，并進而推導出有擾離散信道的編碼定理，對指導編碼技術(shù)具有特別重要的理論價值。5.2有擾離散信道的編碼定理感謝你的觀看2019年6月261編碼調(diào)制的設(shè)計有兩條基本途徑是什么?52019年6月262碼空間

消息k長 (n,k)碼字n長

qk

種分組編碼器qn種

k維k重矢量n維n重矢量

通常qn>>qk，分組編碼的任務(wù)是要在n維n重矢量空間的qn種可能組合中選擇其中的qk個構(gòu)成一個碼空間，其元素就是許用碼的碼集。感謝你的觀看2019年6月262碼空間2019年6月263分組編碼的任務(wù)選擇一個ｋ維n重子空間作為碼空間。確定由k維k重信息空間到ｋ維n重碼空間的映射方法。碼空間的不同選擇方法，以及信息組與碼組的不同映射算法，就構(gòu)成了不同的分組碼。感謝你的觀看2019年6月263分組編碼的任務(wù)選擇一個ｋ維n重子空間作2019年6月2645.2.1隨機編碼(N,K)分組編碼器DMC信道圖5-2-1分組編碼與隨機編碼感謝你的觀看2019年6月2645.2.1隨機編碼(N,K)DMC圖5-2019年6月265在(N,K)分組編碼器中隨機選定的碼集有qNM種碼集點數(shù)M=qK占N維矢量空間總點數(shù)qN的比例是 F=qK/qN

=q-(N-K)

當K和N的差值拉大即冗余的空間點數(shù)增加時，平均而言碼字的分布將變得稀疏，碼字間的平均距離將變大，平均差錯概率將變小。當F

0即(N-K)

時，能否讓平均差錯概率？

感謝你的觀看2019年6月265在(N,K)分組編碼器中隨機選定的碼集有2019年6月266在(N,K)分組編碼器中隨機選定的碼集有qNM種第m個碼集(記作{c}m)被隨機選中的概率是設(shè)與這種選擇相對應(yīng)的條件差錯概率是Pe({c}m)全部碼集的平均差錯概率是感謝你的觀看2019年6月266在(N,K)分組編碼器中隨機選定的碼集有2019年6月267必定存在某些碼集某些碼集若

，就必然存在一批碼集即差錯概率趨于零的好碼一定存在感謝你的觀看2019年6月267必定存在某些碼集感謝你的觀看2019年6月268Gallager在1965年推導了的上邊界，并證明這個上邊界是按指數(shù)規(guī)律收斂的。感謝你的觀看2019年6月268Gallager在1965年推導了2019年6月269碼率：R=(lnM)

/N

M是可能的信息組合數(shù)，M=qKN是每碼字的碼元數(shù)，R表示每碼元攜帶的信息量，單位是每符號比特（bit/symbol）5.2.2信道編碼定理感謝你的觀看2019年6月2695.2.2信道編碼定理感謝你的觀看2019年6月2610E(R)為可靠性函數(shù)，也叫誤差指數(shù)E(R)定義為感謝你的觀看2019年6月2610E(R)為可靠性函數(shù)，也叫誤差指數(shù)感謝2019年6月261101圖5-2-201CRR0感謝你的觀看2019年6月261101圖5-2-201CRR0感謝你的觀2019年6月2612感謝你的觀看2019年6月2612感謝你的觀看2019年6月2613R在[0,R0]區(qū)間時E(R)~R曲線是斜率為-1（-45

）的直線，E(R)反比于R；而當R=C時E(R)=0即可靠性為零。

E(R)

C

R0R0-45

E(R)和R的關(guān)系曲線感謝你的觀看2019年6月2613R在[0,R0]區(qū)間時E(R)~R曲線2019年6月2614正定理：只要傳信率R小于信道容量C，總存在一種信道碼（及解碼器），可以以所要求的任意小的差錯概率實現(xiàn)可靠的通信。逆定理：信道容量C是可靠通信系統(tǒng)傳信率R的上邊界，如果R>C，就不可能有任何一種編碼能使差錯概率任意小。信道編碼定理感謝你的觀看2019年6月2614正定理：只要傳信率R小于信道容量C，總2019年6月26155.3差錯控制與信道編譯碼的基本原理

差錯和差錯系統(tǒng)分類差錯符號：由符號發(fā)生差錯引起，也叫信號差錯，信號差錯概率用誤碼元率表示差錯比特：由信息比特發(fā)生差錯引起，也叫信息差錯，信息差錯概率用誤比特率表示對于二進制傳輸系統(tǒng)，符號差錯等效于比特差錯；對于多進制系統(tǒng)，一個符號差錯到底對應(yīng)多少比特差錯卻難以確定。因為一個符號由多個比特組成。感謝你的觀看2019年6月26155.3差錯控制與信道編譯碼的基本原理

2019年6月2616差錯圖樣（errorpattern）定量地描述信號的差錯，收、發(fā)碼之“差”： 差錯圖樣E＝發(fā)碼C－收碼R

（模M）例：8進制(M=8)碼元， 若發(fā)碼 C=（0,2,5,4,7,5,2） 收碼變?yōu)? R=（0,1,5,4,7,5,4） 差錯圖樣 E=C－R=（0,1,0,0,0,0,6）（模8）二進制碼：E=C

R或

C=R

E

，差錯圖樣中的“１”既是符號差錯也是比特差錯，差錯的個數(shù)叫漢明距離。感謝你的觀看2019年6月2616差錯圖樣（errorpattern）2019年6月2617差錯圖樣類型隨機差錯：若差錯圖樣上各碼位的取值既與前后位置無關(guān)又與時間無關(guān)，即差錯始終以相等的概率獨立發(fā)生于各碼字、各碼元、各比特；突發(fā)差錯：前后相關(guān)、成堆出現(xiàn)。突發(fā)差錯總是以差錯碼元開頭、以差錯碼元結(jié)尾，頭尾之間并不是每個碼元都錯，而是碼元差錯概率超過了某個額定值。感謝你的觀看2019年6月2617差錯圖樣類型隨機差錯：若差錯圖樣上各2019年6月2618糾錯碼分類從功能角度：檢錯碼、糾錯碼對信息序列的處理方法：分組碼、卷積碼碼元與原始信息位的關(guān)系：線性碼、非線性碼差錯類型：糾隨機差錯碼、糾突發(fā)差錯碼、介于中間的糾隨機/突發(fā)差錯碼。構(gòu)碼理論：代數(shù)碼、幾何碼、算術(shù)碼、組合碼等感謝你的觀看2019年6月2618糾錯碼分類從功能角度：檢錯碼、糾錯2019年6月2619差錯控制系統(tǒng)分類前向糾錯（FEC）：發(fā)端信息經(jīng)糾錯編碼后傳送，收端通過糾錯譯碼自動糾正傳遞過程中的差錯反饋重發(fā)（ARQ）：收端通過檢測接收碼是否符合編碼規(guī)律來判斷，如判定碼組有錯，則通過反向信道通知發(fā)端重發(fā)該碼混合糾錯（HEC）：前向糾錯和反饋重發(fā)的結(jié)合，發(fā)端發(fā)送的碼兼有檢錯和糾錯兩種能力感謝你的觀看2019年6月2619差錯控制系統(tǒng)分類前向糾錯（FEC）：2019年6月26205.3.1差錯控制的途徑1、途徑一從信道編碼定理的公式出發(fā)，可知減小差錯概率應(yīng)增大碼長N或增大可靠性函數(shù)E(R)。增大E(R）就要增大信道容量或減小碼率R。R不變，信道容量大者其可靠性函數(shù)E(R)也大；C不變，碼率減小時其可靠性函數(shù)E(R)增大

E(R) R0R1<R2C1

<C2

增大E(R)的途徑感謝你的觀看2019年6月26205.3.1差錯控制的途徑1、途徑一E(2019年6月2621（1）增大信道容量C

擴展帶寬比如開發(fā)新的寬帶媒體，有線通信從明線（150kHz）、對稱電纜（600kHz）、同軸電纜（1GHz）到光纖（25THz），無線由中波、短波、超短波到毫米波、微米波。又比如采取信道均衡措施，如加感時/頻域的自適應(yīng)均衡器。加大功率如提高發(fā)送功率、提高天線增益、將無方向性的漫射改為方向性強的波束或點波束、分集接收等。降低噪聲如采用低噪聲器件、濾波、屏蔽、接地、低溫運行等。在糾錯編碼技術(shù)發(fā)展之前，通信系統(tǒng)設(shè)計者傳統(tǒng)上主要就是靠增大C來提高通信可靠性。感謝你的觀看2019年6月2621（1）增大信道容量C感謝你的觀看2019年6月2622（2）減小碼率R

對于二進制（N，K）分組碼，碼率R=K/N比特/符號；對于q進制（N，K）分組碼，碼率比特/符號.q、N不變而減小K

即降低信息源速率，每秒少傳一些信息。q、K不變而增大N即提高符號速率，占用更大帶寬。N、K不變而減小q即減小信道的輸入輸出符號集，在發(fā)送功率固定時提高信號間的區(qū)分度，從而提高可靠性。在一定通信容量下減小R,等效于拉大C和R之差，因此說這是用增加信道容量的冗余度來換取可靠性。從50年代到70年代，主要的糾錯編碼方法都是以這種冗余度為基礎(chǔ)的。感謝你的觀看2019年6月2622（2）減小碼率R感謝你的觀看2019年6月2623（3）增大碼長N如果要保持碼率R不變，增加碼長N的同時應(yīng)增大信息位K，以保持K/N之比不變。在C和R固定的情況下加大N并沒有增加信道容量的冗余度，它是利用了隨機編碼的特點：隨著N增大，矢量空間以指數(shù)級增加，從統(tǒng)計角度而言碼字間距離也將加大，從而可靠性提高。另外碼長N越大，其實際差錯概率就越能符合統(tǒng)計規(guī)律。增加碼長N所帶來的好處，付出的代價是碼長越長，編碼算法就越復(fù)雜，編碼解碼器也就越昂貴。當前，通過增加碼長N來提高可靠性已成為糾錯編碼技術(shù)的主要途徑之一，它實際上是以設(shè)備的復(fù)雜性換取可靠性，從這個意義上講，妨礙數(shù)字通信系統(tǒng)系能提高的真正限制因素是設(shè)備的復(fù)雜性。感謝你的觀看2019年6月2623（3）增大碼長N感謝你的觀看2019年6月26242、從概念上分析糾錯編碼原理從概念上分析糾錯編碼原理，可以把糾錯能力的獲取歸為兩條，一條是利用冗余度，另一條是噪聲均化（隨機化）。（1）利用冗余度根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一些冗余碼元，這些冗余碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。在接收端按照既定的規(guī)則檢驗信息碼元與監(jiān)督碼元之間的關(guān)系。如果傳輸過程出錯，則信息碼元與監(jiān)督碼元之間的關(guān)系將受到破壞，從而可以發(fā)現(xiàn)錯誤乃至糾正錯誤?！m錯碼為了傳輸這些冗余比特，必須要動用冗余的資源。這些資源可以是：時間比如一個比特重發(fā)幾次，或一段消息重發(fā)幾遍，或者根據(jù)收端的反饋重發(fā)受損信息組，如ARQ系統(tǒng)。感謝你的觀看2019年6月26242、從概念上分析糾錯編碼原理感謝你的觀2019年6月2625頻帶插入冗余比特后傳輸效率下降，若要保持有用信息的速率不變，最直接的方法就是增大符號傳遞速率，結(jié)果就占用了更大的帶寬。比如采用二進制碼（1比特/符號）,編成（8，4）分組碼后使符號速率增大一倍，所占帶寬也增大一倍。功率采用多進制符號，比如用一個八進制ASK符號代替一個四進制ASK符號來傳輸2比特信息，可騰出位置另傳1比特冗余。但為了維持信號集各點之間的距離不變，八進制ASK符號的平均功率可定比四進制時要大，這就是動用冗余的資源來傳輸冗余比特。設(shè)備復(fù)雜度加大碼長N，采用網(wǎng)格編碼調(diào)制(TCM)，是在功率、帶寬受限信道中實施糾錯編碼的有效方法，代價是算法復(fù)雜度的提高，需動用設(shè)備資源。感謝你的觀看2019年6月2625頻帶感謝你的觀看2019年6月2626（2）噪聲均化噪聲均化的基本思想是設(shè)法將危害較大的、較為集中的噪聲干擾分攤開來，使不可恢復(fù)的信息損傷最小。這是因為噪聲干擾的危害不僅與噪聲總量有關(guān)，而且與它們的分布有關(guān)。集中的噪聲干擾（稱之為突發(fā)差錯）的危害甚于分散的噪聲干擾（稱之為隨機差錯）。噪聲均化正是將差錯均勻分攤給各碼字，達到提高總體差錯控制能力的目的。噪聲均化的方法有三種：增加碼長N增加碼長可使譯碼差錯小的原因在于：碼長越大，具體每個碼字中誤碼元的比例就越接近統(tǒng)計平均值，換言之，噪聲按平均數(shù)被均攤到各碼字上。而如果真的均攤了，譯碼就不會發(fā)生任何差錯，因為信道的差錯概率（Pe=1%）遠遠小于編碼后的糾錯能力10%。感謝你的觀看2019年6月2626（2）噪聲均化感謝你的觀看2019年6月2627如圖5-1-2所示的某BSC信道誤碼概率Pe=0.01,假如編碼后的糾錯能力是10%，即長度N的碼字中，只要差錯碼元個數(shù)少于等于N的10%，就可以通過譯碼加以糾正。若碼長N=10,則碼字中多余一個碼元出錯時就會產(chǎn)生譯碼差錯，差錯概率為如果保持碼率R不變，將碼長增加N=40,那么當碼字中多余4個碼元出錯時就會產(chǎn)生譯碼差錯，差錯的概率為感謝你的觀看2019年6月2627如圖5-1-2所示的某BSC信道誤碼概2019年6月2628卷積上面的例子是把信息流分割成K位一組，每組在編成N長的碼字，也就是相關(guān)性僅限于加在各個碼字內(nèi)，而各個碼字之間是彼此無關(guān)的。卷積碼在一定約束長度內(nèi)的若干碼字之間也加進了相關(guān)性，譯碼時不是根據(jù)單個碼字而是一串碼字來做判決。如果再加上適當?shù)木幾g碼方法，就能夠使噪聲分攤到碼字序列而不是一個碼字上，達到噪聲均化的目的。交錯（或稱交織）是對付突發(fā)差錯的有效措施。突發(fā)噪聲使碼流產(chǎn)生集中的、不可糾的差錯，若能采取某種措施，對編碼器輸出的碼流與信道上的符號流做順序上的變換，則信道噪聲造成的符號流中的突發(fā)差錯，有可能被均化而轉(zhuǎn)化為碼流上隨機的、可糾正的差錯。加了交錯器的傳輸系統(tǒng)如圖5-3-2所示。感謝你的觀看2019年6月2628卷積感謝你的觀看2019年6月2629編碼器交錯器去交錯信道交錯的效果取決于信道噪聲的特點和交織方式。最簡單的交錯器是n×m的存儲陣列，碼流按行輸入后按列輸出。圖5-3-3是一個適用于碼長N=7的5×7行列交錯器的示意圖。從圖中看到，碼流的順序1，2，3…7，8，…經(jīng)交錯器后變?yōu)?，8，15，22，29，2，9…。先假設(shè)信道中產(chǎn)生5個連續(xù)的差錯，如果不交錯，這5個差錯集中在1個或2個碼字上，很可能就不可糾。如果采用交錯方法，去交錯后差錯分攤給5個碼字上，每碼字僅1個。譯碼器數(shù)據(jù)入數(shù)據(jù)出圖5-3-2帶交錯器的傳輸系統(tǒng)感謝你的觀看2019年6月2629編碼器交錯器去交錯信道交錯的效果取決于2019年6月263076543211413121110982120191817161528272625242322353433323130297654321141312111098212019181716152827262524232235343332313029229221581入出交錯器去交錯器出入信道中5個連續(xù)的突發(fā)差錯信道圖5-3-35×7行列交錯器工作原理示意圖感謝你的觀看2019年6月263076543211413121110982019年6月26315.3.2碼距、糾錯能力N重碼矢c=(cn-1,cn-2,…c1,c0)可與N維矢量空間XN中的一個點對應(yīng)，全體碼字所對應(yīng)的點構(gòu)成矢量空間里的一個子集，該子集所包含的點只是全部N維空間點的一部分。發(fā)碼一定在這個子集里，傳輸無誤時的收碼也一定位于該子集當出現(xiàn)差錯時，接收的N重矢量:對應(yīng)到子集外空間某一點（能判斷出有差錯）對應(yīng)到該子集，卻對應(yīng)到該子集的另一點上（不能判斷出有差錯）感謝你的觀看2019年6月26315.3.2碼距、糾錯能力N重碼矢c=2019年6月2632子集的任意兩點間存在一定的距離，設(shè)子集兩點間的最小距離是，那么一個能使空間點位置便宜的差錯組合（稱之為重量的差錯圖案）有可能把接收矢量所對應(yīng)的空間點位置從子集的一個點偏移到另一個點，導致從一個碼字譯成另一個碼字。這種情況下，就是說產(chǎn)生了一個“不可檢的差錯”。另一方面，如果差錯數(shù)小于，就不可能從子集一點偏移到子集另一個點，就可以檢錯出差錯的存在。顯然，對于（n,k）分組碼而言，我們有能力檢測出-1個差錯。感謝你的觀看2019年6月2632子集的任意兩點間存在一定的距離，設(shè)子集2019年6月2633碼的糾錯能力也同樣取決于最小距離。為了確定（n,k）分組碼的糾錯能力，一種方便的辦法是個碼字看作是位于n維空間的點。如果以每個碼字為球心，以漢明距離t為半徑做個球體，那么使他們之中任意一對球體兩兩不相交（包括不相切）的t的最大取值是這里INT[.]表示取整。在每一個球內(nèi)含有與該碼字距離小于等于t的所有可能接收碼字。譯碼時，所有落在球內(nèi)的接收碼字都被譯為位于球心的那個碼字。圖5-3-4是碼字和球的兩維示意圖。感謝你的觀看2019年6月2633碼的糾錯能力也同樣取決于最小距離。為了2019年6月2634td=7dmin=3d=5C1C2C3C4C5碼集各碼字間的距離是不同的，碼距最小者決定碼的特性，稱之為最小距離dmin分組碼若單獨考慮檢錯或單獨考慮糾錯，則可檢dmin-1個差錯或糾t=INT[（dmin-1）/2]個差錯。這里dmin=3，糾錯能力是1，檢錯能力是25.3.2碼距、糾錯能力感謝你的觀看2019年6月2634td=7dmin=3d=5C1C2C32019年6月2635一般性的結(jié)論是若最小距離dmin的碼同時能檢ed

個、糾ec個差錯，則必有ed+

ec≤

dmin

-1及ec

≤ed對于線性碼來說，碼距的特性也就是碼的重量特性（碼重可視為該碼與全零碼的距離）。如果有個碼字，就存在個距離，這些距離是大小不一的，碼的總體性能取決于這些距離的分布特性（重量譜），而糾錯能力取決于其中的最小者dmin。正如各符號等概時熵最大一樣，從概念上可以聯(lián)想到：當所有碼距相等時碼的性能最好，或者退后一步，當各碼距相差不大時性能應(yīng)該較好。感謝你的觀看2019年6月2635一般性的結(jié)論是若最小距離dmin的碼同2019年6月2636對于轉(zhuǎn)移概率為p的BSC信道，由于無記憶，各比特差錯的發(fā)生是獨立的，如果不加糾錯編碼，k位信息組出錯的概率是如果采用糾錯能力為t的（n,k）分組碼，當差錯個數(shù)在（t+1）到n之間時該碼可能出錯，因此差錯概率的上限為感謝你的觀看2019年6月2636對于轉(zhuǎn)移概率為p的BSC信道，由于無記2019年6月26375.3.3最優(yōu)譯碼與最大似然譯碼譯碼器的任務(wù)是從受損的信息序列中盡可能正確地恢復(fù)出原信息。譯碼算法的已知條件是：實際接收到的碼字序列{r},r=(r1,r2,…,rN)發(fā)端所采用的編碼算法和該算法產(chǎn)生的碼集XN,滿足信道模型及信道參數(shù)。感謝你的觀看2019年6月26375.3.3最優(yōu)譯碼與最大似然譯碼譯碼器2019年6月2638最佳譯碼，也叫最大后驗概率譯碼(MAP)最大似然譯碼(MLD)5.3.3最優(yōu)譯碼與最大似然譯碼

消息組mi

碼字ci

接收碼r

估值

消息（N,K）編碼器信道譯碼消息還原感謝你的觀看2019年6月2638最佳譯碼，也叫最大后驗概率譯碼