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

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

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

3、 1 0 1 1 0 0 0 0 差錯圖樣中的“1”既是符號差錯也是比特差錯, 差錯的個數(shù)叫漢明距離。 0:傳輸中無錯 1:傳輸中有錯 8 隨機差錯： 差錯是相互獨立的,不相關 存在這種差錯的信道是無記憶信道或隨機信 道 突發(fā)差錯： 指成串出現(xià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ā)長度= 6 9 從功能角度講,差錯碼分為檢錯碼和糾錯碼 檢錯碼：用于發(fā)現(xiàn)差錯 糾錯碼：能自動糾正差錯 糾錯碼與檢錯碼在理論上沒有本質(zhì)區(qū)別,只是應 用場合不同,而側重的

4、性能參數(shù)也不同。 10 按照對信息序列的處理方法,有分組碼和卷積碼 分組碼： 將k個信息碼元分成一組,由這k個碼元按照一定 規(guī)則產(chǎn)生r個監(jiān)督碼元,組成長度n = k + r的碼字 卷積碼： 先將信息序列分組,不同的是編解碼運算不僅與 本組信息有關,而且還與前面若干組有關。 kk 010 101 010 001 110 010 xxxx 101xxxx 010 xxxx r n r 11 按照碼元與原始信息位的關系,分為 線性碼：所有碼元均是原始信息元的線性組 合,編碼器不帶反饋回路。 非線性碼：碼元并不都是信息元的線性組合, 可能還與前面已編的碼元有關,編碼器可能含 反饋回路。 由于非線性碼的

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

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

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

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

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

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

11、也 加進了相關性,譯碼時不是根據(jù)單個碼字,而 是一串碼字來作判決 交錯(交織) 25 c1, 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,

12、 c14, c15, c16, 26 0, 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ā)差錯 離散差錯 傳輸 去交織 輸出 27 譯碼器的任務 從受損的信息序列中盡可能正確地恢復出原 信息。 碼字： ci = (ci1, ci2, , ciN) 接收碼： r = (r1,r2, rN) 28 最佳譯碼(最大后驗概率譯碼)： 在已知r的條件下找出可能性最大的發(fā)碼c作 為譯碼估值： )|(maxrcpc ii

13、最佳譯碼是一種通過經(jīng)驗與歸納由收碼推測發(fā) 碼的方法,是我們認為的最優(yōu)譯碼算法。 在實際譯碼時,后驗概率的定量確定是很困難的 29 最大似然譯碼： 在已知r的條件下使先驗概率最大的譯碼算 法,即令 )|(max ii crpc p(r | c)：似然函數(shù) 30 根據(jù)貝葉斯公式可以建立先驗概率和后驗概率 之間的關系 p(ci)是發(fā)送碼字c的概率 p(r)是接收碼為r的概率 p(r |c)是先驗概率 p(ci|r)是后驗概率 )( )|()( )|( rp crpcp rcp ii i 31 BSC信道的最大似然譯碼可以簡化為最小漢明 距離譯碼。 當逐位比較發(fā)碼和收碼時,僅存在兩種可能性: 相同或不

14、同。 兩種情況發(fā)生的概率分別是： )(1 )( )|( jij jij ijj rcp rcp crp 如果r中有d個碼元與ci的碼元不同,則r與ci的 漢明距離是d 。 32 漢明距離 N j ijjii crcrWcrdisd 1 )(),( 發(fā)送的碼字C 1 1 1 1 1 1 1 1 1 1 接收的碼字R 1 0 0 1 0 0 1 1 1 1 差錯的圖樣E 0 1 1 0 1 1 0 0 0 0 d= 4 33 似然函數(shù) 1 ( | )( | )(1)() 1 1 N N dN dd ijij j p pr cpr cppp p 式中,(1p )N是常數(shù),而 p / (1p )1。

15、d越大,似然函數(shù)p(r |ci)越小,因此求最大似然函數(shù) max p(r |ci)的問題可轉化成求最小漢明距離 mind 的問題。 34 糾錯編碼的檢錯糾錯能力,要取決于碼組的碼距 碼距越大,檢錯、糾錯能力越強。 漢明距離： 二個碼組對應碼位碼元不同的個數(shù)。 最小碼距dmin： 一個碼組的集合中任意二個碼組間的最小漢 明距離。 碼重W： 碼組中非0的數(shù)目。 35 定理：若糾錯碼的最小距離為dmin， 可以檢測出任意小于等于l = dmin1個差錯 可以糾正任意小于等于 個差錯 2 1 min d t 可以檢測出任意小于等于l同時糾正小于等于t 個差錯， 其中l(wèi)、t滿足： l + t dmin1

16、 t l 36 編碼效率： 一個組中信息所占的比重 n k R k：信息碼元的數(shù)目 n：編碼組碼元的總數(shù)目 n = k+ r r：監(jiān)督碼元的數(shù)目 37 奇偶校驗碼(n，n-1)(k+1，k) 0 110 pmmm k p 為偶校驗位 則 C =(m0,m1,m2,mk1,p) 為一個偶校驗碼字。 C 中一定有偶數(shù)個“1” 準用碼 000 011 101 110 m2m1 00 01 10 11 p 0 1 1 0 禁用碼 001 010 100 111 38 n重復碼： 碼率為 1/n,僅有兩個碼字C0和C1,傳送1比特 (k=1)消息； C0=(000),C1=(111) n重復碼可以檢測出

17、任意小于 n/2 個差錯的錯誤 圖案 BSC信道：p1/2,n比特傳輸中發(fā)生差錯數(shù)目 越少,概率越大 (1p)N p(1p)N 1 pd(1p)Nd pN 總認為發(fā)生差錯的圖案是差錯數(shù)目較少的圖 案。 39 40 等重碼/定比碼 設計碼字中的非0符號個數(shù)恒為常數(shù),即 C 由全 體重量恒等于 m 的 n 重向量組成。 5中取3等重碼可以檢測出全部奇數(shù)位差錯,對 某些碼字的傳輸則可以檢測出部分偶數(shù)位差錯。 41 42 重復碼(n,l)： n,可靠性,有效性 奇(偶)監(jiān)督碼(n,nl)： n,有效性,抗干擾性 只能發(fā)現(xiàn)單個或奇數(shù)個獨立隨機差錯 我們要尋找的是： 隨著n增長 差錯率Pe0 的信道編碼

18、編碼效率R1 迄今為止,已找到的絕大多數(shù)實用編碼方法,都 無法同時滿足上述既可靠又有效的要求。 43 線性分組碼： 可用線性方程組表述碼的規(guī)律性的分組碼。 分組碼： 把信源輸出的信息序列按k個相繼碼元分為一 組并按一定規(guī)律對每一信息組增加r個監(jiān)督碼元, 組成長為 的碼字。 44 線性分組碼的編碼： 二進制： 碼長n 2n 種組合 分組碼(n,k) 2k 碼字集合 分組碼的編碼問題就是定出一套: 45 例： (7,3) 線性分組碼。 n =7,k =3, r =4, 碼率R=k/n=3/7 輸入編碼器的信息分為3個一組:m = m3 m2 m1 設碼字為:(c6c5c4c3c2c1c0) c6c

19、5c4為信息元 c3c2c1c0為監(jiān)督元,每個碼元取“0”或“1” 46 mG c 1011100 1110010 0111001 )( 123 mmm 47 G:生成矩陣 (kn)矩陣 ,可以產(chǎn)生整個碼組 mGc 1011100 1110010 0111001 )( 123 mmm 48 例:信息碼組 (101),即c6=1,c5=0,c4 =1 由信息碼組 (101) 編出的碼字為: 1010011 1011100 1110010 0111001 101 c 49 50 0 0 0 0 1000110 0100011 0010111 0001101 0 1 2 3 4 5 6 c c c

20、c c c c 51 0 0 0 0 1000110 0100011 0010111 0001101 0 1 2 3 4 5 6 c c c c c c c 52 假定(n，k)線性碼是， G =IkP 則： H =PTIn-k (7,4)線性分組碼: 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 H 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 G 53 線性分組碼 生成矩陣G 校驗矩陣H 54 伴隨式譯碼 設發(fā)送碼組C = cn-1 c1c0 接收碼組R = rn-1 r1 r0 差錯圖

21、樣E = en-1 e1 e0 ECR CRCRE 收碼有錯 收碼無錯 0 0 ( TTTTT EHEHCHE)HCRH 55 定義： (n,k)線性分組碼的伴隨式是一個r維向量S S = (sr-1 s1 s0) = RHT =EHT 56 采用伴隨式糾錯譯碼的方法是(圖6-13) 按最可能出現(xiàn)的2r (qr )個差錯圖案E,計算相應的 伴隨式S,并構造伴隨式差錯圖樣表S，E 對接收向量R計算伴隨式S 查S,E表得E 糾錯計算 ERC 57 例：已知(6,3)線性分 組碼的生成矩陣： ES 000000000 100000111 010000110 001000011 000100100 0

22、00010010 000001001 100010101 100 010 001 110 011 111 I P H T 110100 011010 111001 G 58 001 100 010 001 110 011 111 100110 T RHS 100111000001100110 ERC 59 60 標準陣列的構造方法是： 選擇所有碼字構成陣列的第0行,通常將全零碼 字 C0作為第0行第 1列元素。 選擇差錯圖案Ei作為第0列,通常以無差錯圖案 E0= (00)作為第0列第 1行元素。 陣列中的i行j列元素為EiCj; i =0,l,2r，j = 0,l,2k 對越小的i, Ei選擇為越容易出現(xiàn)的差錯圖案， 61 C0 000000 C1 001011 C2 010110 C3 011101 C4 100111 C5 101100 C6 110001 C7 111010 S E0 000000 E0 +C0E0 +C1E0 +C2E0 +C3E0 +C4E0 +C5E0 +C6E0 +C7000 E1 100000 E1 +C0 E1 +C1 101011 111 E2 010000 E2 +C0110 E3 001000 E3 +C0 Ei +Cj 010101 011 E4 000100 E4 +C0100 E5 000010 E5 +C0010