信息論與編碼第6章信道編碼課件

1、信道編碼 第6章26.1 糾錯編譯碼的基本原理與分析方法6.2 線性分組碼6.3 卷積碼內(nèi)容3信源編碼提高數(shù)字信號有效性將信源的模擬信號轉(zhuǎn)變?yōu)閿?shù)字信號降低數(shù)碼率,壓縮傳輸頻帶(數(shù)據(jù)壓縮)信道編碼提高數(shù)字通信可靠性 數(shù)字信號在信道的傳輸過程中,由于實際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會產(chǎn)生誤碼。編碼46.1 糾錯編譯碼的基本原理與分析方法56.1.1 差錯和差錯控制系統(tǒng)分類差錯率是衡量傳輸質(zhì)量的重要指標之一,它有幾種不同的定義。碼元差錯率/符號差錯率指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯的碼元數(shù)所占的比例(平均值),簡稱誤碼率。是指信號差錯概率 比特差錯率 /比特誤碼率：在傳輸?shù)谋忍乜倲?shù)

2、中發(fā)生差錯的比特數(shù)所占比例是指信息差錯概率 對二進制傳輸系統(tǒng),符號差錯等效于比特差錯;對多進制系統(tǒng),一個符號差錯對應多少比特差錯卻難以確定6差錯率根據(jù)不同的應用場合對差錯率有不同的要求:在電報傳送時,允許的比特差錯率約為: 104105；計算機數(shù)據(jù)傳輸,一般要求比特差錯率小于: 108109；在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯率7差錯圖樣為定量地描述信號的差錯,定義差錯圖樣E E=CR (模M )最常用的二進制碼可當作特例來研究,其差錯圖樣等于收碼與發(fā)碼的模2加,即 E = CR 或 C = RE設(shè)發(fā)送的碼字C 1 1 1 1 1 1 1 1 1 1 接收的碼字R

3、 1 0 0 1 0 0 1 1 1 1 差錯的圖樣E 0 1 1 0 1 1 0 0 0 0 差錯圖樣中的“1”既是符號差錯也是比特差錯,差錯的個數(shù)叫漢明距離。0:傳輸中無錯1:傳輸中有錯 8差錯圖樣隨機差錯：差錯是相互獨立的,不相關(guān)存在這種差錯的信道是無記憶信道或隨機信道突發(fā)差錯：指成串出現(xiàn)的錯誤,錯誤與錯誤間有相關(guān)性,一個差錯往往要影響到后面一串字E: 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 突發(fā)長度= 4突發(fā)長度= 69糾錯碼分類 從功能角度講,差錯碼分為檢錯碼和糾錯碼檢錯碼：用于發(fā)現(xiàn)差錯糾錯碼：能自動糾正差錯糾錯碼與檢錯碼在

4、理論上沒有本質(zhì)區(qū)別,只是應用場合不同,而側(cè)重的性能參數(shù)也不同。10糾錯碼分類 按照對信息序列的處理方法,有分組碼和卷積碼分組碼：將k個信息碼元分成一組,由這k個碼元按照一定規(guī)則產(chǎn)生r個監(jiān)督碼元,組成長度n = k + r的碼字 卷積碼：先將信息序列分組,不同的是編解碼運算不僅與本組信息有關(guān),而且還與前面若干組有關(guān)。kk010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrnr11糾錯碼分類 按照碼元與原始信息位的關(guān)系,分為線性碼：所有碼元均是原始信息元的線性組合,編碼器不帶反饋回路。非線性碼：碼元并不都是信息元的線性組合,可能還與前面已編的碼元有關(guān),編碼器

5、可能含反饋回路。由于非線性碼的分析比較困難,早期實用的糾錯碼多為線性碼,但當今發(fā)現(xiàn)的很多好碼恰恰是非線性碼。12糾錯碼分類 按照適用的差錯類型,分成:糾隨機差錯碼:用于隨機差錯信道,其糾錯能力用碼組內(nèi)允許的獨立差錯的個數(shù)來衡量。糾突發(fā)差錯碼:針對突發(fā)差錯而設(shè)計,其糾錯能力主要用可糾突發(fā)差錯的最大長度來衡量13差錯控制系統(tǒng)分類 前向糾錯(FEC)：發(fā)端發(fā)送糾錯碼,收端譯碼器自動發(fā)現(xiàn)并糾正錯誤特點：單向連續(xù)傳輸,實時性好譯碼電路復雜 14差錯控制系統(tǒng)分類 自動請求重發(fā)(ARQ)：發(fā)端發(fā)送檢錯碼,收端譯碼器判斷當前碼字傳輸是否出錯；當有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的碼字（全部或

6、部分）。特點：需反饋信道,但譯碼設(shè)備不會很復雜,對突發(fā)錯誤特別有效。15差錯控制系統(tǒng)分類 混合糾錯(HEC)：是FEC與ARQ方式的結(jié)合。發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組,收端收到碼組后,檢查差錯情況,如果差錯在碼的糾錯能力以內(nèi),則自動進行糾正。如果信道干擾很嚴重,錯誤很多,超過了碼的糾錯能力,但能檢測出來,則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。特點：充分發(fā)揮碼的檢錯和糾錯性能,在較差的信道中仍可收到較好的效果。需反饋信道和較復雜的譯碼電路16差錯控制系統(tǒng)分類 信息反饋(IRQ)：收端把收到的信息原封不動反饋回發(fā)端,發(fā)端比較反饋信息與原信息,若有錯,重發(fā)。特點：沒有檢錯和糾錯編碼,電路簡單

7、，需反饋信道,且傳輸速率低。176.1.2 糾錯編碼的基本思路 從概念上分析糾錯編碼的基本原理,可以把糾錯能力的獲取歸結(jié)為兩條：利用冗余度噪聲均化(隨機化、概率化)冗余度就是在信息流中插入冗余比特,這些冗余比特與信息比特之間存在著特定的相關(guān)性。在傳輸過程中個別信息受損,可以利用相關(guān)性從其他未受損的冗余比特中推測出受損比特的原貌,保證了信息的可靠性。18檢錯與糾錯原理 0:晴,1:雨若10,01。收端無法發(fā)現(xiàn)錯誤00晴1001110011雨能發(fā)現(xiàn)一個錯誤禁用碼組插入1位監(jiān)督碼后具有檢出1位錯碼的能力,但不能予以糾正。19檢錯與糾錯原理 000晴010001111000111雨晴在只有1位錯碼的情

8、況下,可以判決哪位是錯碼并予以糾正,可以檢出2位或2位以下的錯碼。100011101110雨20檢錯與糾錯原理最大似然譯碼：將接收到的碼字譯碼為與它差別最小的許用碼字,并且認為這個許用碼字就是它所對應的發(fā)送碼字,從而在碼字的糾錯能力內(nèi)實現(xiàn)自動糾錯。糾錯編碼之所以具有檢錯、糾錯能力,是因為在信息碼元之外加入了監(jiān)督碼。監(jiān)督碼不載信息,只是用來監(jiān)督信息碼在傳輸中有無差錯。糾錯編碼所提高的可靠性,是以犧牲信道利用率為代價換取的。監(jiān)督碼引入越多,檢錯、糾錯能力越強,但信道的傳輸效率下降也越多。21傳輸冗余比特必然要動用冗余的資源。時間：比如一個比特重復發(fā)幾次,或一段消息重復發(fā)幾遍,或根據(jù)收端的反饋重發(fā)受

9、損信息組。頻帶：插入冗余比特后傳輸效率下降,若要保持有用信息的速率不變,方法之一是增大符號傳遞速率(波特率),結(jié)果就占用了更大的帶寬。功率：采用多進制符號,用8進制ASK符號代替4進制ASK符號來傳送2比特信息,可騰出位置另傳1冗余比特。8進制ASK符號的平均功率肯定比4進制時要大,這就是動用冗余的功率資源來傳輸冗余比特。設(shè)備復雜度：加大碼長,采用網(wǎng)格編碼調(diào)制,是在功率、帶寬受限信道中實施糾錯編碼的有效方法,代價是算法復雜度的提高,需動用設(shè)備資源。22信道編碼在被傳輸信息中附加一些冗余碼,即監(jiān)督碼元,利用附加碼元與信息碼元間的約束關(guān)系加以校驗,以檢測和糾正錯誤。信源編碼減少了冗余度冗余度是隨機

10、的、無規(guī)律的信道編碼增加了冗余度冗余度是特定的、有規(guī)律的,故可利用其在接收端進行檢錯和糾錯。信道編碼23糾錯編碼的基本思路噪聲均化設(shè)法將危害較大的、較為集中的噪聲干擾分攤開來,使不可恢復的信息損傷最小。噪聲干擾的危害大小不僅與噪聲總量有關(guān),而且與其分布有關(guān)。集中的噪聲干擾(突發(fā)差錯)的危害甚于分散的噪聲干擾(隨機差錯)。噪聲均化正是將差錯均勻分攤給各碼字,達到提高總體差錯控制能力的目的。24糾錯編碼的基本思路噪聲均化的方法主要有3種：增加碼長N 增加碼長可使譯碼誤差減小的原因在于:碼長越大,具體每個碼字中誤碼的比例就越接近統(tǒng)計平均值。卷積 卷積碼在一定約束長度內(nèi)的若干碼字之間也加進了相關(guān)性,譯

11、碼時不是根據(jù)單個碼字,而是一串碼字來作判決 交錯(交織)25c1, c2, c3, c4, c5, c6, c7, c8, c9, 輸入寫讀交織傳輸讀寫去交織輸出交織c1, c2, c3, c4, c5, c6, c7, c8, c9, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12,c13, c14, c15, c16,c1, c5, c9, c13, c2, c6, c10, c14, c3, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12,c13, c14, c15, c16,260,

12、 0, 0, 1, 1, 1, 1, 0, 0, 0, 0,0, 1, 0, 0 0, 1, 0, 0 0, 1, 0, 0 1, 0, 0, 0讀寫0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 突發(fā)差錯離散差錯交織傳輸去交織輸出276.1.3 譯碼方法 譯碼器的任務從受損的信息序列中盡可能正確地恢復出原信息。碼字： ci = (ci1, ci2, , ciN) 接收碼： r = (r1,r2, rN)28最佳譯碼最佳譯碼(最大后驗概率譯碼)：在已知r的條件下找出可能性最大的發(fā)碼c作為譯碼估值： 最佳譯碼是一種通過經(jīng)驗與歸納由收碼推測發(fā)碼的方法,是我們認為的最優(yōu)

13、譯碼算法。在實際譯碼時,后驗概率的定量確定是很困難的29最大似然譯碼最大似然譯碼：在已知r的條件下使先驗概率最大的譯碼算法,即令p(r | c)：似然函數(shù)30譯碼方法根據(jù)貝葉斯公式可以建立先驗概率和后驗概率之間的關(guān)系p(ci)是發(fā)送碼字c的概率p(r)是接收碼為r的概率p(r |c)是先驗概率p(ci|r)是后驗概率31最大似然譯碼BSC信道的最大似然譯碼可以簡化為最小漢明距離譯碼。當逐位比較發(fā)碼和收碼時,僅存在兩種可能性:相同或不同。兩種情況發(fā)生的概率分別是：如果r中有d個碼元與ci的碼元不同,則r與ci的漢明距離是d 。32漢明距離漢明距離發(fā)送的碼字C 1 1 1 1 1 1 1 1 1

14、1接收的碼字R 1 0 0 1 0 0 1 1 1 1差錯的圖樣E 0 1 1 0 1 1 0 0 0 0 d= 433似然函數(shù) 式中,(1p )N是常數(shù),而 p / (1p )1。d越大,似然函數(shù)p(r |ci)越小,因此求最大似然函數(shù)max p(r |ci)的問題可轉(zhuǎn)化成求最小漢明距離 mind的問題。34碼距與檢錯、糾錯能力糾錯編碼的檢錯糾錯能力,要取決于碼組的碼距碼距越大,檢錯、糾錯能力越強。漢明距離：二個碼組對應碼位碼元不同的個數(shù)。最小碼距dmin：一個碼組的集合中任意二個碼組間的最小漢明距離。碼重W：碼組中非0的數(shù)目。35碼距與檢錯、糾錯能力定理：若糾錯碼的最小距離為dmin，可以

15、檢測出任意小于等于l = dmin1個差錯可以糾正任意小于等于 個差錯可以檢測出任意小于等于l同時糾正小于等于t個差錯，其中l(wèi)、t滿足： l + t dmin1 t l36編碼效率編碼效率：一個組中信息所占的比重k：信息碼元的數(shù)目n：編碼組碼元的總數(shù)目 n = k+ rr：監(jiān)督碼元的數(shù)目37檢錯碼奇偶校驗碼(n，n-1)(k+1，k)p 為偶校驗位則 C =(m0,m1,m2,mk1,p) 為一個偶校驗碼字。C 中一定有偶數(shù)個“1”準用碼000011101110m2m1 00 01 10 11 p0110禁用碼00101010011138n重復碼：碼率為 1/n,僅有兩個碼字C0和C1,傳送1

16、比特(k=1)消息；C0=(000),C1=(111)n重復碼可以檢測出任意小于 n/2 個差錯的錯誤圖案BSC信道：p1/2,n比特傳輸中發(fā)生差錯數(shù)目越少,概率越大 (1p)N p(1p)N 1 pd(1p)Nd pN總認為發(fā)生差錯的圖案是差錯數(shù)目較少的圖案。糾錯碼39糾錯碼40糾錯碼等重碼/定比碼設(shè)計碼字中的非0符號個數(shù)恒為常數(shù),即 C 由全體重量恒等于 m 的 n 重向量組成。5中取3等重碼可以檢測出全部奇數(shù)位差錯,對某些碼字的傳輸則可以檢測出部分偶數(shù)位差錯。416.3 線性分組碼42重復碼(n,l)：n,可靠性,有效性奇(偶)監(jiān)督碼(n,nl)：n,有效性,抗干擾性只能發(fā)現(xiàn)單個或奇數(shù)個

17、獨立隨機差錯我們要尋找的是：隨著n增長 差錯率Pe0 的信道編碼 編碼效率R1迄今為止,已找到的絕大多數(shù)實用編碼方法,都無法同時滿足上述既可靠又有效的要求。抗干擾(檢、糾錯)能力主要決定于碼組間的最小距離dmin43線性分組碼線性分組碼：可用線性方程組表述碼的規(guī)律性的分組碼。分組碼：把信源輸出的信息序列按k個相繼碼元分為一組并按一定規(guī)律對每一信息組增加r個監(jiān)督碼元,組成長為n的碼字。kk010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrnr線性分組碼：信息位與監(jiān)督位之間有某種線性關(guān)系44線性分組碼的編碼：二進制： 碼長n 2n 種組合分組碼(n,k)

18、2k 碼字集合分組碼的編碼問題就是定出一套規(guī)則:線性分組碼 2k 2n 2n2k qk qn qnqk 準用碼組 禁用碼組 準用碼組 禁用碼組 不同的選取規(guī)則組成不同的(n，k)碼456.2.1 線性分組碼的生成矩陣和校驗矩陣 例： (7,3) 線性分組碼。 n =7,k =3, r =4, 碼率R=k/n=3/7輸入編碼器的信息分為3個一組:m = m3 m2 m1 設(shè)碼字為:(c6c5c4c3c2c1c0)c6c5c4為信息元c3c2c1c0為監(jiān)督元,每個碼元取“0”或“1”46按下列線性方程編碼 c6= m3 c5 = m2 c4 = m1 c3 = m3 + m1 c2 = m3 +

19、m2 + m1 c1 = m3 + m2 c0 = m2 + m1 寫成矩陣形式：生成矩陣 47生成矩陣 G:生成矩陣 (kn)矩陣 ,可以產(chǎn)生整個碼組 若生成矩陣G能分解成下列兩個子矩陣: G =IkP其中Ik為k維單位方陣,則稱C為系統(tǒng)碼,G為系統(tǒng)碼的生成矩陣G48例:信息碼組 (101),即c6=1,c5=0,c4 =1由信息碼組 (101) 編出的碼字為:其它7個碼字如表49校驗矩陣 將線性方程： c6= m3 c5 = m2 c4 = m1 c3 = m3 + m1= c6 + c4 c2 = m3 + m2 + m1= c6 + c5 + c4 c1 = m3 + m2 = c6

20、+ c5 c0 = m2 + m1= c5 + c4c6 + c4 + c3 = 0c6 + c5 + c4 + c2 = 0c6 + c5 + c1 = 0 c5 + c4 + c0 = 050校驗矩陣 c6 + c4 + c3 = 0c6 + c5 + c4 + c2 = 0c6 + c5 + c1 = 0 c5 + c4 + c0 = 0HH:校驗矩陣 (監(jiān)督矩陣)51校驗矩陣 HcT = 0TcHT = 0cT 、HT、0T分別表示c、H、0的轉(zhuǎn)置矩陣。52系統(tǒng)碼假定(n，k)線性碼是系統(tǒng)碼， G =IkP則： H =PTIn-k(7,4)線性分組碼:53生成矩陣和校驗矩陣的關(guān)系 線性

21、分組碼生成矩陣G 校驗矩陣H H GT = 0TG HT = 0若把(n,k)碼的H矩陣看成(n,n-k) 碼的生成矩陣G 把(n,k)碼的G矩陣看成(n,n-k) 碼的校驗矩陣H則由G生成的(n,k)碼與G生成的(n,n-k)互為對偶碼 (7,3)(7,4)546.2.1 伴隨式與標準陣列譯碼 伴隨式譯碼設(shè)發(fā)送碼組C = cn-1 c1c0 接收碼組R = rn-1 r1 r0 差錯圖樣E = en-1 e1 e0利用碼字與校驗矩陣的正交性CHT=0,可校驗收碼R是否有錯,即令S=RHT =EHT55伴隨式譯碼 定義：(n,k)線性分組碼的伴隨式是一個r維向量S S = (sr-1 s1 s

22、0) = RHT =EHTS 0: 傳輸中一定有錯誤發(fā)生 S 0: 傳輸中無差錯發(fā)生或差錯圖案恰好為一個碼字56伴隨式譯碼 采用伴隨式糾錯譯碼的方法是(圖6-13)按最可能出現(xiàn)的2r (qr )個差錯圖案E,計算相應的伴隨式S,并構(gòu)造伴隨式差錯圖樣表S，E對接收向量R計算伴隨式S查S,E表得E糾錯計算57例：已知(6,3)線性分組碼的生成矩陣：求:列出S與E的對照表：解： S = EHTES00000000010000011101000011000100001100010010000001001000000100110001010158求:當收到碼組R = 100110時,判斷是否碼字？ 解：

23、查表：E = 000001S 0R不是碼字59求: E = 100000 S = 111 E = 010001 S = 111(6,3)線性分組碼的糾錯能力為1,對二位錯誤的情況不能糾正。由于S0,故譯碼器能檢測到發(fā)現(xiàn)了二位錯誤。伴隨式S是一個r重矢量,二進制時只有2r 種可能組合,而差錯圖案E是一個n重矢量,有2n 種可能的組合,因此S與E不存在一一對應關(guān)系。對應每一個確定的S,差錯圖案E有2k個解,但最終只能取其中一個。最簡單合理的處理方法是概率譯碼以2k個解的重量為依據(jù),選擇最輕者為E的估值60標準陣列譯碼 標準陣列的構(gòu)造方法是：選擇所有碼字構(gòu)成陣列的第0行,通常將全零碼字 C0作為第0

24、行第 1列元素。選擇差錯圖案Ei作為第0列,通常以無差錯圖案E0= (00)作為第0列第 1行元素。陣列中的i行j列元素為EiCj; i =0,l,2r，j = 0,l,2k對越小的i, Ei選擇為越容易出現(xiàn)的差錯圖案，61標準陣列譯碼表(6,3)碼C0000000C1001011C2010110C3011101C4100111C5101100C6110001C7111010SE0000000 E0 +C0E0 +C1E0 +C2E0 +C3E0 +C4E0 +C5E0 +C6E0 +C7000E1100000E1 +C0E1 +C1101011111E2010000E2 +C0110E3001000E3 +C0Ei +Cj010101011E4000100E4 +C0100E5000010E5 +C0010E6000001E6 +C0E6 +C7001E7100010E7 +C010100111010011111100010100111001001101100010162伴隨式S有23=8種組合,差錯圖案:中代表無差錯的有一種代表一個差錯的圖案有 代表兩個差錯的圖案有要把8個伴隨式