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

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

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

3、差錯(cuò)圖樣中的“1”既是符號(hào)差錯(cuò)也是比特差錯(cuò),差錯(cuò)的個(gè)數(shù)叫漢明距離。0:傳輸中無錯(cuò)1:傳輸中有錯(cuò)8 隨機(jī)差錯(cuò)： 差錯(cuò)是相互獨(dú)立的,不相關(guān) 存在這種差錯(cuò)的信道是無記憶信道或隨機(jī)信道 突發(fā)差錯(cuò)： 指成串出現(xiàn)的錯(cuò)誤,錯(cuò)誤與錯(cuò)誤間有相關(guān)性,一個(gè)差錯(cuò)往往要影響到后面一串字 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 從功能角度講,差錯(cuò)碼分為檢錯(cuò)碼和糾錯(cuò)碼 檢錯(cuò)碼：用于發(fā)現(xiàn)差錯(cuò) 糾錯(cuò)碼：能自動(dòng)糾正差錯(cuò) 糾錯(cuò)碼與檢錯(cuò)碼在理論上沒有本質(zhì)區(qū)別,只是應(yīng)用場合不同,而側(cè)重的性能參數(shù)也不同。10 按照對信息序列的處理方法,有分

4、組碼和卷積碼 分組碼： 將k個(gè)信息碼元分成一組,由這k個(gè)碼元按照一定規(guī)則產(chǎn)生r個(gè)監(jiān)督碼元,組成長度n = k + r的碼字 卷積碼： 先將信息序列分組,不同的是編解碼運(yùn)算不僅與本組信息有關(guān),而且還與前面若干組有關(guān)。kk010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrnr11 按照碼元與原始信息位的關(guān)系,分為 線性碼：所有碼元均是原始信息元的線性組合,編碼器不帶反饋回路。 非線性碼：碼元并不都是信息元的線性組合,可能還與前面已編的碼元有關(guān),編碼器可能含反饋回路。 由于非線性碼的分析比較困難,早期實(shí)用的糾錯(cuò)碼多為線性碼,但當(dāng)今發(fā)現(xiàn)的很多好碼恰恰是非線性碼

5、。12 按照適用的差錯(cuò)類型,分成: 糾隨機(jī)差錯(cuò)碼:用于隨機(jī)差錯(cuò)信道,其糾錯(cuò)能力用碼組內(nèi)允許的獨(dú)立差錯(cuò)的個(gè)數(shù)來衡量。 糾突發(fā)差錯(cuò)碼:針對突發(fā)差錯(cuò)而設(shè)計(jì),其糾錯(cuò)能力主要用可糾突發(fā)差錯(cuò)的最大長度來衡量13 前向糾錯(cuò)(FEC)： 發(fā)端發(fā)送糾錯(cuò)碼,收端譯碼器自動(dòng)發(fā)現(xiàn)并糾正錯(cuò)誤 特點(diǎn)： 單向連續(xù)傳輸,實(shí)時(shí)性好 譯碼電路復(fù)雜 14 自動(dòng)請求重發(fā)(ARQ)： 發(fā)端發(fā)送檢錯(cuò)碼,收端譯碼器判斷當(dāng)前碼字傳輸是否出錯(cuò)； 當(dāng)有錯(cuò)時(shí)按某種協(xié)議通過一個(gè)反向信道請求發(fā)送端重傳已發(fā)送的碼字（全部或部分）。 特點(diǎn)： 需反饋信道,但譯碼設(shè)備不會(huì)很復(fù)雜,對突發(fā)錯(cuò)誤特別有效。15 混合糾錯(cuò)(HEC)： 是FEC與ARQ方式的結(jié)合。 發(fā)

6、端發(fā)送同時(shí)具有自動(dòng)糾錯(cuò)和檢測能力的碼組,收端收到碼組后,檢查差錯(cuò)情況,如果差錯(cuò)在碼的糾錯(cuò)能力以內(nèi),則自動(dòng)進(jìn)行糾正。 如果信道干擾很嚴(yán)重,錯(cuò)誤很多,超過了碼的糾錯(cuò)能力,但能檢測出來,則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。 特點(diǎn)： 充分發(fā)揮碼的檢錯(cuò)和糾錯(cuò)性能,在較差的信道中仍可收到較好的效果。 需反饋信道和較復(fù)雜的譯碼電路16 信息反饋(IRQ)： 收端把收到的信息原封不動(dòng)反饋回發(fā)端,發(fā)端比較反饋信息與原信息,若有錯(cuò),重發(fā)。 特點(diǎn)： 沒有檢錯(cuò)和糾錯(cuò)編碼,電路簡單， 需反饋信道,且傳輸速率低。17 從概念上分析糾錯(cuò)編碼的基本原理,可以把糾錯(cuò)能力的獲取歸結(jié)為兩條： 利用冗余度 噪聲均化(隨機(jī)化、概率化)

7、冗余度 就是在信息流中插入冗余比特,這些冗余比特與信息比特之間存在著特定的相關(guān)性。 在傳輸過程中個(gè)別信息受損,可以利用相關(guān)性從其他未受損的冗余比特中推測出受損比特的原貌,保證了信息的可靠性。18 0:晴,1:雨 若10,01。收端無法發(fā)現(xiàn)錯(cuò)誤00晴1001110011雨能發(fā)現(xiàn)一個(gè)錯(cuò)誤禁用碼組 插入1位監(jiān)督碼后具有檢出1位錯(cuò)碼的能力,但不能予以糾正。19000晴010001111000111雨晴 在只有1位錯(cuò)碼的情況下,可以判決哪位是錯(cuò)碼并予以糾正,可以檢檢出2位或2位以下的錯(cuò)碼。100011101110雨20 最大似然譯碼： 將接收到的碼字譯碼為與它的許用碼字,并且認(rèn)為這個(gè)許用碼字就是它所對應(yīng)

8、的發(fā)送碼字,從而在碼字的糾錯(cuò)能力內(nèi)實(shí)現(xiàn)自動(dòng)糾錯(cuò)。 糾錯(cuò)編碼之所以具有檢錯(cuò)、糾錯(cuò)能力,是因?yàn)樵谛畔⒋a元之外加入了監(jiān)督碼。監(jiān)督碼不載信息,只是用來監(jiān)督信息碼在傳輸中有無差錯(cuò)。 糾錯(cuò)編碼所提高的可靠性,是以犧牲信道利用率為代價(jià)換取的。 監(jiān)督碼引入越多,檢錯(cuò)、糾錯(cuò)能力越強(qiáng),但信道的傳輸效率下降也越多。21 傳輸冗余比特必然要?jiǎng)佑萌哂嗟馁Y源。 時(shí)間： 比如一個(gè)比特重復(fù)發(fā)幾次,或一段消息重復(fù)發(fā)幾遍,或根據(jù)收端的反饋重發(fā)受損信息組。 頻帶： 插入冗余比特后傳輸效率下降,若要保持有用信息的速率不變,方法之一是增大符號(hào)傳遞速率(波特率),結(jié)果就占用了更大的帶寬。 功率： 采用多進(jìn)制符號(hào),用8進(jìn)制ASK符號(hào)代替4

9、進(jìn)制ASK符號(hào)來傳送2比特信息,可騰出位置另傳1冗余比特。 8進(jìn)制ASK符號(hào)的平均功率肯定比4進(jìn)制時(shí)要大,這就是動(dòng)用冗余的功率資源來傳輸冗余比特。 設(shè)備復(fù)雜度： 加大碼長,采用網(wǎng)格編碼調(diào)制,是在功率、帶寬受限信道中實(shí)施糾錯(cuò)編碼的有效方法,代價(jià)是算法復(fù)雜度的提高,需動(dòng)用設(shè)備資源。22 信道編碼 在被傳輸信息中附加一些冗余碼冗余碼,即監(jiān)督碼元,利用附加碼元與信息碼元間的約束關(guān)系加以校驗(yàn),以。 信源編碼減少了 冗余度是隨機(jī)的、無規(guī)律的 信道編碼增加了 冗余度是特定的、有規(guī)律的,故可利用其在接收端進(jìn)行檢錯(cuò)和糾錯(cuò)。23 噪聲均化 設(shè)法將危害較大的、較為集中的噪聲干擾分?jǐn)傞_來,使不可恢復(fù)的信息損傷最小。

10、噪聲干擾的危害大小不僅與噪聲總量有關(guān),而且與其分布有關(guān)。 集中的噪聲干擾(突發(fā)差錯(cuò))的危害甚于分散的噪聲干擾(隨機(jī)差錯(cuò))。 噪聲均化正是將差錯(cuò)均勻分?jǐn)偨o各碼字,達(dá)到提高總體差錯(cuò)控制能力的目的。24 噪聲均化的方法主要有3種： 增加碼長N 增加碼長可使譯碼誤差減小的原因在于:碼長越大,具體每個(gè)碼字中誤碼的比例就越接近統(tǒng)計(jì)平均值。 卷積 卷積碼在一定約束長度內(nèi)的若干碼字之間也加進(jìn)了相關(guān)性,譯碼時(shí)不是根據(jù)單個(gè)碼字,而是一串碼字來作判決 交錯(cuò)(交織)25c1, c2, c3, c4, c5, c6, c7, c8, c9, 輸入寫交織傳輸寫去交織輸出c1, c2, c3, c4, c5, c6, c7

11、, 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, 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,

12、 1, 突發(fā)差錯(cuò)離散差錯(cuò)傳輸去交織輸出27 譯碼器的任務(wù) 從受損的信息序列中盡可能正確地恢復(fù)出原信息。 碼字： ci = (ci1, ci2, , ciN) 接收碼： r = (r1,r2, rN)28 最佳譯碼(最大后驗(yàn)概率譯碼)： 在已知r的條件下找出可能性最大的發(fā)碼c作為譯碼估值： )|(maxrcpcii 最佳譯碼是一種通過經(jīng)驗(yàn)與歸納由收碼推測發(fā)碼的方法,是我們認(rèn)為的最優(yōu)譯碼算法。 在實(shí)際譯碼時(shí),后驗(yàn)概率的定量確定是很困難的29 最大似然譯碼： 在已知r的條件下使先驗(yàn)概率最大的譯碼算法,即令)|(maxiicrpc p(r | c)：似然函數(shù)30 根據(jù)貝葉斯公式可以建立先驗(yàn)概率和后驗(yàn)概

13、率之間的關(guān)系 p(ci)是發(fā)送碼字c的概率 p(r)是接收碼為r的概率 p(r |c)是先驗(yàn)概率 p(ci|r)是后驗(yàn)概率)()|()()|(rpcrpcprcpiii31 BSC信道的最大似然譯碼可以簡化為最小漢明距離譯碼。 當(dāng)逐位比較發(fā)碼和收碼時(shí),僅存在兩種可能性: 相同或不同。 兩種情況發(fā)生的概率分別是：)(1)()|(jijjijijjrcprcpcrp 如果r中有d個(gè)碼元與ci的碼元不同,則r與ci的漢明距離是d 。32 漢明距離NjijjiicrcrWcrdisd1)(),( 發(fā)送的碼字C 1 1 1 1 1 1 1 1 1 1 接收的碼字R 1 0 0 1 0 0 1 1 1 1

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

15、距離為dmin，可以檢測出任意小于等于l = dmin1個(gè)差錯(cuò)可以糾正任意小于等于 個(gè)差錯(cuò)21mindt可以檢測出任意小于等于l同時(shí)糾正小于等于t個(gè)差錯(cuò)， 其中l(wèi)、t滿足： l + t dmin1 t l36 編碼效率： 一個(gè)組中信息所占的比重nkR k：信息碼元的數(shù)目 n：編碼組碼元的總數(shù)目 n = k+ r r：監(jiān)督碼元的數(shù)目37 奇偶校驗(yàn)碼(n，n-1)(k+1，k)0110pmmmk p 為偶校驗(yàn)位 則 C =(m0,m1,m2,mk1,p) 為一個(gè)偶校驗(yàn)碼字。C 中一定有偶數(shù)個(gè)“1”準(zhǔn)用碼000011101110m2m1 00 01 10 11 p0110禁用碼00101010011

16、138 n重復(fù)碼： 碼率為 1/n,僅有兩個(gè)碼字C0和C1,傳送1比特(k=1)消息； C0=(000),C1=(111) n重復(fù)碼可以檢測出任意小于 n/2 個(gè)差錯(cuò)的錯(cuò)誤圖案 BSC信道：p1/2,n比特傳輸中發(fā)生差錯(cuò)數(shù)目越少,概率越大 (1p)N p(1p)N 1 pd(1p)Nd pN 總認(rèn)為發(fā)生差錯(cuò)的圖案是差錯(cuò)數(shù)目較少的圖案。3940 等重碼/定比碼 設(shè)計(jì)碼字中的非0符號(hào)個(gè)數(shù)恒為常數(shù),即 C 由全體重量恒等于 m 的 n 重向量組成。 5中取3等重碼可以檢測出全部奇數(shù)位差錯(cuò),對某些碼字的傳輸則可以檢測出部分偶數(shù)位差錯(cuò)。4142 重復(fù)碼(n,l)： n,可靠性,有效性 奇(偶)監(jiān)督碼(n

17、,nl)： n,有效性,抗干擾性 只能發(fā)現(xiàn)單個(gè)或奇數(shù)個(gè)獨(dú)立隨機(jī)差錯(cuò) 我們要尋找的是： 隨著n增長 差錯(cuò)率Pe0 的信道編碼 編碼效率R1 迄今為止,已找到的絕大多數(shù)實(shí)用編碼方法,都無法同時(shí)滿足上述既可靠又有效的要求。43 線性分組碼： 可用線性方程組表述碼的規(guī)律性的分組碼。 分組碼： 把信源輸出的信息序列按k個(gè)相繼碼元分為一組并按一定規(guī)律對每一信息組增加r個(gè)監(jiān)督碼元,組成長為 的碼字。44 線性分組碼的編碼： 二進(jìn)制： 碼長n 2n 種組合 分組碼(n,k) 2k 碼字集合 分組碼的編碼問題就是定出一套:45 例： (7,3) 線性分組碼。 n =7,k =3, r =4, 碼率R=k/n=3

18、/7 輸入編碼器的信息分為3個(gè)一組:m = m3 m2 m1 設(shè)碼字為:(c6c5c4c3c2c1c0) c6c5c4為信息元 c3c2c1c0為監(jiān)督元,每個(gè)碼元取“0”或“1”46mGc101110011100100111001)(123mmm47 G:生成矩陣 (kn)矩陣 ,可以產(chǎn)生整個(gè)碼組 mGc101110011100100111001)(123mmm48 例:信息碼組 (101),即c6=1,c5=0,c4 =1由信息碼組 (101) 編出的碼字為:1010011101110011100100111001101c49500000100011001000110010111000110

19、10123456ccccccc51000010001100100011001011100011010123456ccccccc52 假定(n，k)線性碼是， G =IkP 則： H =PTIn-k (7,4)線性分組碼:1 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 1H1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1G53 線性分組碼 生成矩陣G 校驗(yàn)矩陣H 54 伴隨式譯碼 設(shè)發(fā)送碼組C = cn-1 c1c0 接收碼組R = rn-1 r1 r0 差錯(cuò)圖樣E = en-1 e1 e0ECRCRCRE收碼有

20、錯(cuò)收碼無錯(cuò)00(TTTTTEHEHCHE)HCRH55 定義： (n,k)線性分組碼的伴隨式是一個(gè)r維向量S S = (sr-1 s1 s0) = RHT =EHT56 采用伴隨式糾錯(cuò)譯碼的方法是(圖6-13)按最可能出現(xiàn)的2r (qr )個(gè)差錯(cuò)圖案E,計(jì)算相應(yīng)的伴隨式S,并構(gòu)造伴隨式差錯(cuò)圖樣表S，E對接收向量R計(jì)算伴隨式S查S,E表得E糾錯(cuò)計(jì)算ERC57 例：已知(6,3)線性分組碼的生成矩陣：ES000000000100000111010000110001000011000100100000010010000001001100010101100010001110011111IPHT1101

21、00011010111001G58001100010001110011111100110TRHS100111000001100110ERC5960 標(biāo)準(zhǔn)陣列的構(gòu)造方法是：選擇所有碼字構(gòu)成陣列的第0行,通常將全零碼字 C0作為第0行第 1列元素。選擇差錯(cuò)圖案Ei作為第0列,通常以無差錯(cuò)圖案E0= (00)作為第0列第 1行元素。陣列中的i行j列元素為EiCj; i =0,l,2r，j = 0,l,2k對越小的i, Ei選擇為越容易出現(xiàn)的差錯(cuò)圖案，61C0000000C1001011C2010110C3011101C4100111C5101100C6110001C7111010SE0000000 E0 +C0E0 +C1E0 +C2E0 +C3E0 +C4E0 +C5E0 +C6E0 +C7000E1100000E1 +C0E1 +C1101011111E2010000E2 +C0110E3001000E3 +C0Ei +Cj010101011E4000100E4 +C0100E5000010E5 +C0010E600