數(shù)字電視第5章 信道編碼.

1、數(shù)字電視廣播的目的是要將圖像、聲音和數(shù)據(jù)等信息快速、實(shí)時(shí)、高質(zhì)、可靠地傳輸至接收端，供用戶滿意地收看、收聽(tīng)。5.1 5.1 概概 論論5.2 5.2 差錯(cuò)控制編碼差錯(cuò)控制編碼5.3 5.3 線性分組碼線性分組碼5.4 5.4 循循 環(huán)環(huán) 碼碼5.5 5.5 RSRS碼碼( (里德索羅蒙碼里德索羅蒙碼) )5.6 5.6 RSRS碼糾錯(cuò)原理碼糾錯(cuò)原理5.7 5.7 交交 織織 碼碼5.8 5.8 卷卷 積積 碼碼5.9 5.9 編碼與調(diào)制相結(jié)合的卷積碼編碼與調(diào)制相結(jié)合的卷積碼( (TCM)TCM)最主要的可概括為兩點(diǎn)。其一，附加一些數(shù)據(jù)信息以實(shí)現(xiàn)最大的檢錯(cuò)糾錯(cuò)能力，這就涉及到差錯(cuò)控制編碼原理和特

2、性。其二，數(shù)據(jù)流的頻譜特性適應(yīng)傳輸通道的通頻帶特性，以求信號(hào)能量經(jīng)由通道傳輸時(shí)損失最小，因此有利于載波噪聲比(載噪比，C/N)高，發(fā)生誤碼的可能性小。 5.1.2 信道模型(1) 隨機(jī)信道 隨機(jī)信道是指數(shù)據(jù)流在其中傳輸時(shí)會(huì)受到隨機(jī)噪聲的干擾，使高低電平的碼元在信道輸出端產(chǎn)生電平失真，導(dǎo)致接收端解碼時(shí)發(fā)生碼元值的誤判決，形成誤碼。(2) 突發(fā)信道傳輸通道中常有一些瞬間出現(xiàn)的短脈沖干擾，它們引起的不是單個(gè)碼元誤碼，而往往是一串碼元內(nèi)存在大量誤碼，前后碼元的誤碼之間表現(xiàn)為有一定的相關(guān)性。 (3) 混合信道實(shí)際的傳輸通道通常不是單純的隨機(jī)信道或突發(fā)信道，而是二者兼有，或者以某個(gè)信道屬性為主。 5.1.

3、3 誤碼的產(chǎn)生及誤碼率與信噪比的關(guān)系1.二元碼的誤碼產(chǎn)生 不歸零二元碼傳輸過(guò)程中受噪聲影響產(chǎn)生誤碼的情況。 2.誤碼率與信噪比的關(guān)系(1) 誤碼率數(shù)字信號(hào)傳輸系統(tǒng)中，誤碼的輕重程度通常以誤碼率(誤比特率BER或誤符號(hào)率SER)衡量，它表示為單位時(shí)間內(nèi)誤碼數(shù)目占總數(shù)據(jù)數(shù)目的比例值。 假設(shè)二元碼中對(duì)應(yīng)數(shù)據(jù)“1”的電平為A，對(duì)應(yīng)于數(shù)據(jù)“0”的電平為0，則在噪聲干擾的情況下，數(shù)據(jù)“1”和“0”的輸出為數(shù)據(jù)“1”：Y(KT)=An(KT)數(shù)據(jù)“0”： Y(KT)=n(KT) 式中，K為0，1，2，N的正整數(shù)，T為碼元的時(shí)間長(zhǎng)度。平均值為零的高斯白噪聲的幅度概率密度函數(shù)P (n)為當(dāng)發(fā)送瑞傳輸數(shù)據(jù)“0”

4、(幅值0)時(shí)，疊加噪聲后接收端的信號(hào)幅度概率密度函數(shù)P0(Y)當(dāng)發(fā)送瑞傳輸數(shù)據(jù)“1” (幅值1)時(shí)，疊加噪聲后接收端的信號(hào)幅度概率密度函數(shù)P1(Y) 現(xiàn)假設(shè)“0”碼(信號(hào)幅度為零)錯(cuò)判為“1”，碼(信號(hào)幅度為A的概率為Pbo，“1”，碼錯(cuò)判為“o”的概率為Pb1，則:總的誤碼概率Pb應(yīng)為令變量Zy/s，則Z2Y2/s2，dZdy/s，數(shù)學(xué)上稱為Q函數(shù)，可表示為 假設(shè)二元碼基帶信號(hào)波形為矩形，且“0”碼概率Po與“1”碼概率P1相等，即P0P1，則平均信號(hào)功率S為SA22，而平均噪聲功率N為Ns2對(duì)于單極性不歸零二元碼，總的誤碼概率Pb與信噪比SN的關(guān)系式可表示為5.2.1 差錯(cuò)控制編碼的方式1

5、.反饋重發(fā)(ARQ，自動(dòng)重發(fā)請(qǐng)求)方式 要消除誤碼造成接收端獲得的信息發(fā)生差錯(cuò)的影響，需要在信道編碼中實(shí)施差錯(cuò)控制以使得出現(xiàn)誤碼時(shí)接收端能夠檢知并予以糾正，這就是差錯(cuò)控制編碼。5.2.2 糾錯(cuò)碼的分類(lèi)糾錯(cuò)碼按照檢錯(cuò)糾錯(cuò)功能的不同，可分為檢錯(cuò)碼、糾錯(cuò)碼和糾刪碼三種。 糾錯(cuò)碼按照誤碼產(chǎn)生原因的不同，可分為糾隨機(jī)誤碼的糾錯(cuò)碼和糾突發(fā)誤碼的糾錯(cuò)碼兩種。前者應(yīng)用于主要產(chǎn)生獨(dú)立性隨機(jī)誤碼的信道，后者應(yīng)用于易產(chǎn)生突發(fā)性局部誤碼的信道。 糾錯(cuò)碼按照信息碼元與監(jiān)督碼元之間的檢驗(yàn)關(guān)系，可分為線性碼和非線性碼。如果信息碼元和監(jiān)督碼元之間存在線性關(guān)系，可用一組線性方程式表示，就稱為線性(糾錯(cuò))碼2.許用碼組和禁用碼組

6、信道編碼后總碼長(zhǎng)為n的不同碼組值可有2”個(gè)。其中，發(fā)送的信息碼組有2k個(gè)，通常稱之為許用碼組，其余的(2n一2k)個(gè)碼組不予傳送，稱之為禁用碼組3.編碼效率通常，將每個(gè)碼組內(nèi)信息碼元數(shù)k值與總碼元數(shù)n 值之比k/n稱為信道編碼的編碼效率，即k/nk/(k+r)4.碼重和碼距在分組編碼中，每個(gè)碼組內(nèi)碼元“1” 的數(shù)目稱為碼組的重量，簡(jiǎn)稱碼重。 每?jī)蓚€(gè)碼組間相應(yīng)位置上碼元值不相同的個(gè)數(shù)稱為碼距，又稱為漢明距離，通常用d表示。對(duì)于(n，A)分碼組，許用碼組為2“個(gè)，各碼組之間的碼距5.最小碼距與檢錯(cuò)和糾錯(cuò)能力的關(guān)系最小碼距d0的大小與信道編解碼檢錯(cuò)糾錯(cuò)能力密切相關(guān)。 總碼組數(shù)為238個(gè)，許用碼組數(shù)為

7、212個(gè)，其余6個(gè)碼組為禁用碼組。A與B有4種選擇方式，即(000與l11)、(00l與ll0)、 (0l0與101)和(011與l00)，它們都是d3。一般地，對(duì)于分組碼，可得出以下三條關(guān)于最小碼距與檢錯(cuò)糾錯(cuò)能力間關(guān)系的結(jié)論。(1)在一個(gè)碼組內(nèi)為了檢知e個(gè)誤碼，要求最小碼距應(yīng)滿足d0e+1;(2)在一個(gè)碼組內(nèi)為了糾正t個(gè)誤碼，要求最小碼距應(yīng)滿足d02t+1;(3)在一個(gè)碼組內(nèi)為了糾正t個(gè)誤碼并同時(shí)檢知e個(gè)誤碼(et)，最小碼距應(yīng)滿足d0e+t+1。 1. 1. 含有全零碼字。含有全零碼字。 2.2.任意兩個(gè)許用碼字之和仍是一個(gè)許用碼字。（封閉性）任意兩個(gè)許用碼字之和仍是一個(gè)許用碼字。（封閉性

8、） 3.3.最小碼距最小碼距d d0 0等于非零碼字的最小重量即等于非零碼字的最小重量即d d0 0= =w wminmin （由此性質(zhì)可以方便的確定出線性分組碼的最小碼距，（由此性質(zhì)可以方便的確定出線性分組碼的最小碼距， 進(jìn)而明確其糾錯(cuò)能力。）進(jìn)而明確其糾錯(cuò)能力。） 可用線性方程組表述碼的規(guī)律性的分組碼稱為線性可用線性方程組表述碼的規(guī)律性的分組碼稱為線性分組碼。線性碼建立在代數(shù)學(xué)群論基礎(chǔ)上，線性碼各許用碼分組碼。線性碼建立在代數(shù)學(xué)群論基礎(chǔ)上，線性碼各許用碼的集合構(gòu)成代數(shù)學(xué)中的群，因此，又稱為群碼。的集合構(gòu)成代數(shù)學(xué)中的群，因此，又稱為群碼。在群中只有一種運(yùn)算，就是模在群中只有一種運(yùn)算，就是模2

9、 2和。和。線性分組碼的性質(zhì)線性分組碼的性質(zhì)： 奇偶監(jiān)督碼是一種最簡(jiǎn)單的線性碼，我們?cè)?jīng)作了奇偶監(jiān)督碼是一種最簡(jiǎn)單的線性碼，我們?cè)?jīng)作了偶校驗(yàn)的例子。偶校驗(yàn)的例子。0021aaann稱為稱為監(jiān)督方程監(jiān)督方程。 接收時(shí)，為了檢測(cè)傳輸時(shí)是否有錯(cuò)，還要做同樣接收時(shí)，為了檢測(cè)傳輸時(shí)是否有錯(cuò)，還要做同樣的計(jì)算：的計(jì)算：01234bbbbbs有錯(cuò)無(wú)錯(cuò)10s這里這里S S稱為稱為校正子校正子，上式也稱，上式也稱伴隨式伴隨式。奇偶監(jiān)督碼中只有一位監(jiān)督碼，因此只能表示有否錯(cuò)誤。奇偶監(jiān)督碼中只有一位監(jiān)督碼，因此只能表示有否錯(cuò)誤。當(dāng)監(jiān)督位增加，則監(jiān)督方程增加，校正子增加。當(dāng)監(jiān)督位增加，則監(jiān)督方程增加，校正子增加。r

10、 r位監(jiān)督碼除了用全位監(jiān)督碼除了用全“0”0”表示無(wú)錯(cuò)外，可表示表示無(wú)錯(cuò)外，可表示r21種錯(cuò)誤圖樣。種錯(cuò)誤圖樣。( (n,kn,k) )碼可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為：碼可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為： 我們把接收碼組我們把接收碼組R R與發(fā)射碼組與發(fā)射碼組C C的差稱為錯(cuò)誤圖樣，的差稱為錯(cuò)誤圖樣，用用E E表示：表示：E=C-RE=C-R，或者，或者 C=R+EC=R+E ( (n,kn,k) )中，信息碼為中，信息碼為k k位，可傳輸位，可傳輸M=2M=2k k種信息，種信息，當(dāng)增加當(dāng)增加r r位的監(jiān)督位后，有位的監(jiān)督位后，有2 2n n種狀態(tài)，但只取種狀態(tài)，但只取2 2k k 種為種為許用狀態(tài)，其他為禁用

11、，許用狀態(tài)，其他為禁用，( (n,kn,k) )碼可檢測(cè)的錯(cuò)誤圖樣數(shù)為碼可檢測(cè)的錯(cuò)誤圖樣數(shù)為 2 2n n-2-2k k2 2 n-kn-k -1=2 -1=2 r r-1-1 不可檢測(cè)的錯(cuò)誤圖樣數(shù)為不可檢測(cè)的錯(cuò)誤圖樣數(shù)為2 2k k-1-11nc2nctnctiinc12 2 n-kn-k-1 -1 + + + + =+ =對(duì)于能糾正對(duì)于能糾正 t t 個(gè)錯(cuò)誤的線性分組碼個(gè)錯(cuò)誤的線性分組碼( (n,kn,k) )應(yīng)滿足：應(yīng)滿足：inc是錯(cuò)是錯(cuò) i i 位的個(gè)數(shù)。位的個(gè)數(shù)。如果滿足如果滿足 ，則有可能構(gòu)造出糾正一位或一，則有可能構(gòu)造出糾正一位或一位以上的線性碼。位以上的線性碼。i=1i=1時(shí)，

12、時(shí)，1nnc 即對(duì)于碼組長(zhǎng)度為即對(duì)于碼組長(zhǎng)度為n n，信息碼元信息碼元k k位，監(jiān)督元位，監(jiān)督元r r，nr12下面我們通過(guò)例子來(lái)說(shuō)明如何構(gòu)造線性碼。下面我們通過(guò)例子來(lái)說(shuō)明如何構(gòu)造線性碼。 設(shè)設(shè)(n(n，k)k)中，中，k=4k=4，要求能糾一位錯(cuò)，現(xiàn)取要求能糾一位錯(cuò)，現(xiàn)取 r=3r=3，可指示可指示2 23 3-1=7-1=7種錯(cuò)誤，種錯(cuò)誤， 碼長(zhǎng)碼長(zhǎng)n=4+3=7n=4+3=7，表示為：表示為： C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0 其中其中C C6 6C C5 5C C4 4C C3 3為信息碼元，為信息碼元，C C2 2C C1 1

13、C C0 0為監(jiān)督元為監(jiān)督元由由r=3r=3，可有三個(gè)監(jiān)督方程和校正子，設(shè)為可有三個(gè)監(jiān)督方程和校正子，設(shè)為s s1 1s s2 2s s3 321rn 恰好滿足恰好滿足 , ,故可糾一位錯(cuò)。故可糾一位錯(cuò)。設(shè)設(shè)s s1 1s s2 2s s3 3三位校正三位校正子與誤碼位置的對(duì)子與誤碼位置的對(duì)應(yīng)關(guān)系為：應(yīng)關(guān)系為：0 0 00 0 00 0 10 0 10 1 00 1 01 0 01 0 00 1 10 1 11 0 11 0 11 1 01 1 01 1 11 1 1誤碼位置誤碼位置無(wú)錯(cuò)無(wú)錯(cuò) C C0 0 C C1 1 C C2 2 C C3 3 C C4 4 C C5 5 C C6 6S S

14、1 1 S S2 2 S S3 3 于是監(jiān)督碼元于是監(jiān)督碼元C C2 2C C1 1C C0 0應(yīng)應(yīng)由以下由以下監(jiān)督方程監(jiān)督方程決定。決定。C C2 2=C=C6 6+C+C5 5+C+C4 4C C1 1=C=C6 6+C+C5 5+C+C3 3C C0 0=C=C6 6+C+C4 4+C+C3 3監(jiān)督元與信息元之間的線性方程組監(jiān)督元與信息元之間的線性方程組s s1 1=C=C2 2+C+C6 6+C+C5 5+C+C4 4=0=0s s2 2=C=C1 1+C+C6 6+C+C5 5+C+C3 3=0=0s s3 3=C=C0 0+C+C6 6+C+C4 4+C+C3 3=0=0于是得到于

15、是得到(7(7，4)4)線性分組碼如下：線性分組碼如下： 序序 碼碼 字字 號(hào)號(hào) 信息元信息元 監(jiān)督元監(jiān)督元 8 1 0 0 0 1 1 18 1 0 0 0 1 1 1 9 1 0 0 1 1 0 0 9 1 0 0 1 1 0 0 10 1 0 1 0 0 1 0 10 1 0 1 0 0 1 0 11 1 0 1 1 0 0 1 11 1 0 1 1 0 0 1 12 1 1 0 0 0 0 1 12 1 1 0 0 0 0 1 13 1 1 0 1 0 1 0 13 1 1 0 1 0 1 0 14 1 1 1 0 1 0 0 14 1 1 1 0 1 0 0 15 1 1 1 1 1

16、 1 1 15 1 1 1 1 1 1 1 序序 碼碼 字字 號(hào)號(hào) 信息元信息元 監(jiān)督元監(jiān)督元 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 2 0 0 1 0 1 0 1 2 0 0 1 0 1 0 1 3 0 0 1 1 1 1 0 3 0 0 1 1 1 1 0 4 0 1 0 0 1 1 0 4 0 1 0 0 1 1 0 5 0 1 0 1 1 0 1 5 0 1 0 1 1 0 1 6 0 1 1 0 0 1 1 6 0 1 1 0 0 1 1 7 0 1 1 1 0 0 0 7 0 1 1 1 0 0

17、 0 將前面的監(jiān)督方程改寫(xiě)成矩陣的形式，將前面的監(jiān)督方程改寫(xiě)成矩陣的形式， C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0 可看成為編碼矢量，于是有：可看成為編碼矢量，于是有：記做：記做：TTHC00TCH監(jiān)督方程監(jiān)督方程H - H - 監(jiān)督矩陣監(jiān)督矩陣 不滿足以上關(guān)系的為非典型矩陣，典型矩陣和不滿足以上關(guān)系的為非典型矩陣，典型矩陣和非典型矩陣之間可以轉(zhuǎn)換。非典型矩陣之間可以轉(zhuǎn)換。2/ H2/ H矩陣各行是線性無(wú)關(guān)的。矩陣各行是線性無(wú)關(guān)的。行數(shù)行數(shù)-監(jiān)督元的個(gè)數(shù)監(jiān)督元的個(gè)數(shù)r r列數(shù)列數(shù)-碼組長(zhǎng)度碼組長(zhǎng)度 n nI Ir r為為r r階單位陣階單位陣

18、1/ 1/ 當(dāng)有當(dāng)有H=P H=P IrIr 時(shí)稱為典型矩陣，時(shí)稱為典型矩陣，利用監(jiān)督方程，我們可以對(duì)線性碼的封閉性加以證明利用監(jiān)督方程，我們可以對(duì)線性碼的封閉性加以證明 設(shè)監(jiān)督方程設(shè)監(jiān)督方程A A1 1、A A2 2均為均為線性碼集合中的許用碼線性碼集合中的許用碼組，因此有組，因此有 令兩許用碼組相加令兩許用碼組相加 A A1 1+A+A2 2帶入監(jiān)督方程，有：帶入監(jiān)督方程，有：02THA01THA因此，因此， A A1 1+A+A2 2亦為許用碼組。亦為許用碼組。0)(2121TTTHAHAHAA,/3TTOCH 當(dāng)給出信息組后，如何方便迅速地求出整個(gè)當(dāng)給出信息組后，如何方便迅速地求出整個(gè)

19、編碼碼組，即如何生成編碼矢量？編碼碼組，即如何生成編碼矢量？C C2 2=C=C6 6+C+C5 5+C+C4 4C C1 1=C=C6 6+C+C5 5+C+C3 3C C0 0=C=C6 6+C+C4 4+C+C3 3由監(jiān)督元與信息元之間的關(guān)系：由監(jiān)督元與信息元之間的關(guān)系：TPCCCCCCC3456012或者可以寫(xiě)成：或者可以寫(xiě)成：QCCCCCCC3456012令：令：QPT則有：則有：給給Q Q的左邊，加一個(gè)的左邊，加一個(gè)k kk k階的單位矩陣，則構(gòu)成：階的單位矩陣，則構(gòu)成：G=G=I Ik k Q Q稱為稱為生成矩陣生成矩陣，且為典型形式。典型，且為典型形式。典型G G矩陣矩陣行數(shù)行

20、數(shù)- - 信息元的個(gè)數(shù)信息元的個(gè)數(shù)k k列數(shù)列數(shù)- - 碼組長(zhǎng)度碼組長(zhǎng)度 n n每行本身就是一個(gè)許用碼組每行本身就是一個(gè)許用碼組TTHG00TGH于是有：于是有：矩陣和非典型矩陣之間可以轉(zhuǎn)換。矩陣和非典型矩陣之間可以轉(zhuǎn)換。生成矩陣生成矩陣編碼碼組編碼碼組CM G6543Mcccc. )2階矩陣，各行線性無(wú)關(guān)為nkG1）由G和信息組即可產(chǎn)生全部碼字.通過(guò)典型生成矩陣產(chǎn)生的一定是系統(tǒng)碼。通過(guò)典型生成矩陣產(chǎn)生的一定是系統(tǒng)碼。G稱為典型生成矩陣。3) kGI Q011010101001110100G （1）試確定(n,k)，并求H ； (2) 寫(xiě)出監(jiān)督元與信息元的關(guān)系式及 該（n,k）碼的全部碼字；

21、(3) 確定最小碼距及檢錯(cuò)能力。解：解：該題目不涉及繁雜的推導(dǎo)，但包含許多概念（1）確定（n,k）,求HG G矩陣矩陣行數(shù)行數(shù)- - 信息元的個(gè)數(shù)信息元的個(gè)數(shù)k=3k=3列數(shù)列數(shù)- - 碼組長(zhǎng)度碼組長(zhǎng)度 n=6n=6（6 6，3 3）碼）碼110100011010101001求H，需確定P，TQPQPT應(yīng)將已知的那個(gè)G轉(zhuǎn)換成典型形式，求出Q，再利用 求出G。011010101001110100G011010110100101001H=P H=P IrIr=100101010110001011rTIQ (2) 0THC0000101010110001011012345cccccc設(shè)C= 0123

22、45cccccc于是有：110100011010101001345cccGMC監(jiān)督元與信息元的關(guān)系式用三位二進(jìn)制數(shù)的所有8種狀態(tài)帶入，可得到所有碼字如右表。 序號(hào) 碼 字 0 0 0 0 0 0 0 1 0 0 1 0 1 1 2 0 1 0 1 1 0 3 0 1 1 1 0 1 4 1 0 0 1 0 1 5 1 0 1 1 1 0 6 1 1 0 0 1 1 7 1 1 1 0 0 0(3) 確定最小碼距及 檢錯(cuò)能力所以有：所以有：d d0 0=3=3可用于檢兩位錯(cuò)或糾一位錯(cuò)。利用性質(zhì)知：最小碼距d0 0等于非零碼字的最小重量即d0 0=wminmin發(fā)送端經(jīng)過(guò)編碼后給出：發(fā)送端經(jīng)過(guò)編碼

23、后給出：0121cccccnn接收端收到的碼組為：接收端收到的碼組為：0121rrrrRnn兩者的差記為：兩者的差記為：0121eeeeCREnniiiiicrcre10表示第表示第 i i 位無(wú)錯(cuò)位無(wú)錯(cuò)表示第表示第 i i 位有錯(cuò)位有錯(cuò)E E稱為錯(cuò)誤圖樣。共有稱為錯(cuò)誤圖樣。共有2 2n n個(gè)錯(cuò)誤圖樣。個(gè)錯(cuò)誤圖樣。當(dāng)當(dāng) E E為全零錯(cuò)誤圖樣時(shí)，為全零錯(cuò)誤圖樣時(shí)，R=C R=C 沒(méi)有傳輸錯(cuò)誤沒(méi)有傳輸錯(cuò)誤; ;TTHR0可可利用利用E E檢出或糾正錯(cuò)誤；檢出或糾正錯(cuò)誤；TTHR0傳輸中的錯(cuò)誤超出了可糾錯(cuò)的范圍。傳輸中的錯(cuò)誤超出了可糾錯(cuò)的范圍。但可能有兩種情況：但可能有兩種情況：(n,k)(n,k)

24、可檢測(cè)的錯(cuò)誤圖樣數(shù)為可檢測(cè)的錯(cuò)誤圖樣數(shù)為 2 2n n - 2- 2k k(n,k)(n,k)可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為 2 2n-k n-k - 1- 1這時(shí)的錯(cuò)誤圖樣稱為不可檢測(cè)的錯(cuò)誤圖樣這時(shí)的錯(cuò)誤圖樣稱為不可檢測(cè)的錯(cuò)誤圖樣一般來(lái)講，一般來(lái)講，E=0E=0， 則則R=CR=C，可滿足監(jiān)督方程可滿足監(jiān)督方程E0E0，則，則RCRC，不滿足監(jiān)督方程不滿足監(jiān)督方程檢錯(cuò)：當(dāng)檢錯(cuò)：當(dāng)S=0S=0時(shí)，認(rèn)為時(shí)，認(rèn)為E=0E=0，當(dāng)，當(dāng)S S 0 0時(shí)，認(rèn)為時(shí)，認(rèn)為E E 0,0,校正子校正子 S S 的計(jì)算的計(jì)算TTTTTEHEHCHHECRHS)(即校正子只與錯(cuò)誤圖樣即校正子只與錯(cuò)誤圖樣

25、E E有關(guān)。有關(guān)。TTEHRHS 110100010001110101011111 1100000例：例：已知監(jiān)督矩陣：已知監(jiān)督矩陣：若接收為：若接收為： R= 0 0 0 0 0 1 1 R= 0 0 0 0 0 1 1 ，試確定是否錯(cuò)誤，試確定是否錯(cuò)誤，若接收錯(cuò)誤，試進(jìn)行糾錯(cuò)。若接收錯(cuò)誤，試進(jìn)行糾錯(cuò)。解：計(jì)算校正子解：計(jì)算校正子0 0 00 0 00 0 10 0 10 1 00 1 01 0 01 0 00 1 10 1 11 0 11 0 11 1 01 1 01 1 11 1 1誤碼位置誤碼位置無(wú)錯(cuò)無(wú)錯(cuò) C C0 0 C C1 1 C C2 2 C C3 3 C C4 4 C C5

26、5 C C6 6S S1 1 S S2 2 S S3 3錯(cuò)誤圖樣：錯(cuò)誤圖樣： E= 0 0 0 1 0 0 0 E= 0 0 0 1 0 0 0 對(duì)照校正子與誤碼位置，確定錯(cuò)誤圖樣：對(duì)照校正子與誤碼位置，確定錯(cuò)誤圖樣：011TEH于是：于是：R=R+E= 0 0 0 0 0 1 1 + 0 0 0 1 0 0 0 由于由于 ，當(dāng)只發(fā)生一位錯(cuò)碼時(shí)，矩陣，當(dāng)只發(fā)生一位錯(cuò)碼時(shí)，矩陣E中中只有一個(gè)非零元素，與只有一個(gè)非零元素，與H的轉(zhuǎn)置相乘的結(jié)果是選的轉(zhuǎn)置相乘的結(jié)果是選出其中的一列，即校正子與出其中的一列，即校正子與H矩陣的哪一列相同，矩陣的哪一列相同，則該列即為碼元發(fā)生錯(cuò)誤的位置。則該列即為碼元發(fā)生

27、錯(cuò)誤的位置。 TEHS = 0 0 0 1 0 1 1 編碼過(guò)程：編碼過(guò)程： 設(shè)線性分組碼為設(shè)線性分組碼為(n(n，k)k)，0121mmmmMkk信息碼為：信息碼為：1) 1) 根據(jù)生成矩陣或監(jiān)督矩陣，根據(jù)生成矩陣或監(jiān)督矩陣，2) 2) 由由C=MGC=MG0 0 求出所有碼字，且為系統(tǒng)碼。求出所有碼字，且為系統(tǒng)碼。H H0 0=P =P IrIr G G0 0=I Ik k Q QQPT求出典型生成矩陣；求出典型生成矩陣；譯碼過(guò)程：譯碼過(guò)程：1 1） 由收到的碼組由收到的碼組R R計(jì)算校正子計(jì)算校正子S S；TRHS TTHRS或2 2） 由由S S判決是否有錯(cuò)并通過(guò)判決是否有錯(cuò)并通過(guò) 找

28、出錯(cuò)誤圖樣；找出錯(cuò)誤圖樣；TEHS 3 3） 按照按照 R+E=C R+E=C 計(jì)算并還原計(jì)算并還原 C C；4 4）將碼組）將碼組C C還原成原信息組還原成原信息組M M。漢明碼是用于糾一位錯(cuò)誤的線性分組碼。漢明碼是用于糾一位錯(cuò)誤的線性分組碼。特點(diǎn)：特點(diǎn)：12 rn最小碼距：最小碼距： 30d糾錯(cuò)能力：糾錯(cuò)能力：1t編碼效率編碼效率 ：R1knrrnnn Rn當(dāng) 很大時(shí)，n=15n=15的漢明碼，其監(jiān)督位為多少？編碼的漢明碼，其監(jiān)督位為多少？編碼效率為多少？效率為多少？解：解：4161212rnnrr，可知：由于是其信息位有于是其信息位有 15-4=11 15-4=11 位位此漢明碼為（此漢

29、明碼為（1515，1111）碼）碼編碼效率：編碼效率：R/11/1573%k n其監(jiān)督位有其監(jiān)督位有 15-11=4 15-11=4 位位 漢明碼是線性分組碼，因此其監(jiān)督矩陣同樣漢明碼是線性分組碼，因此其監(jiān)督矩陣同樣有有n n列、列、r r行，當(dāng)監(jiān)督位數(shù)給定后，即可構(gòu)造出行，當(dāng)監(jiān)督位數(shù)給定后，即可構(gòu)造出漢明碼。漢明碼。例，例，r=3r=3H H矩陣的矩陣的n n列由除了全零以外的列由除了全零以外的 個(gè)個(gè)r r位碼位碼構(gòu)成，每碼組出現(xiàn)一次且全部出現(xiàn)。（構(gòu)成，每碼組出現(xiàn)一次且全部出現(xiàn)。（H H不唯一）不唯一）21r0001011001010101001101000111G1011001110101

30、01110100H構(gòu)造構(gòu)造得到的漢明碼如下所示：得到的漢明碼如下所示：信息位監(jiān)督位信息位監(jiān)督位a6a5a4a300000001001000110100010101100111a2a1a0000011101110110101011000a6a5a4a310001001101010101100110111101111a2a1a0111100010001001010100111（7 7，4 4）漢明碼編碼器）漢明碼編碼器a6a5a4a3信息組信息組a0a1a2a3a4碼字碼字+a5a6+ 糾正單個(gè)錯(cuò)誤的漢明碼中，糾正單個(gè)錯(cuò)誤的漢明碼中，r r 位校正子碼組與位校正子碼組與誤碼圖樣一一對(duì)應(yīng)，最充分地利

31、用了監(jiān)督位所能誤碼圖樣一一對(duì)應(yīng)，最充分地利用了監(jiān)督位所能提供的信息。提供的信息。 在一般情況下，對(duì)于能糾正在一般情況下，對(duì)于能糾正t t個(gè)錯(cuò)誤的線性分個(gè)錯(cuò)誤的線性分組碼組碼(n(n，k)k)，應(yīng)滿足以下不等式：應(yīng)滿足以下不等式： 因此，漢明碼也是糾一位錯(cuò)的線性分組因此，漢明碼也是糾一位錯(cuò)的線性分組碼中，編碼效率最高的。碼中，編碼效率最高的。tiintnnnknrCCCC1211212tiintnnnknrCCCC1211212 上式取等號(hào)時(shí)，校正子與誤碼不超過(guò)上式取等號(hào)時(shí)，校正子與誤碼不超過(guò)t t個(gè)的所個(gè)的所有圖樣一一對(duì)應(yīng)，監(jiān)督碼元得到最充分的利用，有圖樣一一對(duì)應(yīng)，監(jiān)督碼元得到最充分的利用，這

32、種線性分組碼即完備碼。這種線性分組碼即完備碼。 除漢明碼外，迄今為止，找到的唯一能糾除漢明碼外，迄今為止，找到的唯一能糾正多個(gè)錯(cuò)誤的完備碼為正多個(gè)錯(cuò)誤的完備碼為(23(23，12)12)戈雷碼。戈雷碼。 t=3t=3漢明碼就是一種完備碼。漢明碼就是一種完備碼。 該式亦稱為漢明界，它給出已知該式亦稱為漢明界，它給出已知k k和和t t時(shí)，時(shí)，所需要的監(jiān)督位數(shù)。所需要的監(jiān)督位數(shù)。列陣的個(gè)來(lái)構(gòu)成時(shí)，可任選其中nHnrn12 但此時(shí)構(gòu)成的則非漢明碼。但此時(shí)構(gòu)成的則非漢明碼。 通常選擇碼重最小的矢量?jī)?yōu)先。通常選擇碼重最小的矢量?jī)?yōu)先。試構(gòu)造一個(gè)試構(gòu)造一個(gè)k=5k=5的可糾一個(gè)錯(cuò)的線性分組碼的可糾一個(gè)錯(cuò)的線

33、性分組碼1/ 1/ 計(jì)算最短的碼長(zhǎng)；計(jì)算最短的碼長(zhǎng)；2/ 2/ 構(gòu)造構(gòu)造H H；3/ 3/ 求生成矩陣求生成矩陣G G；4/ 4/ 求信息組為求信息組為(10101)(10101)的編碼碼字的編碼碼字C C。解：解： 1/ 1/ 因?yàn)橐驗(yàn)閠 t 等于等于1, 1, 且要求且要求k=5, k=5, 可用試探法確定可用試探法確定n n設(shè)：設(shè)：n-k=3n-k=3，則則 不滿足糾錯(cuò)要求；不滿足糾錯(cuò)要求； 853712123nkn設(shè)：設(shè)：n-k=4n-k=4，則則 滿足糾錯(cuò)要求；滿足糾錯(cuò)要求； 9541512124nkn于是取于是取n=9n=9，此時(shí)此時(shí)r = r = n-kn-k = 4 = 4，(

34、9, 5)(9, 5)線性分組碼線性分組碼2/ r=42/ r=4，四位碼共有四位碼共有 種狀態(tài)，除全零種狀態(tài)，除全零外都可用于構(gòu)造外都可用于構(gòu)造H H矩陣。矩陣。1624 為了構(gòu)造典型矩陣，選為了構(gòu)造典型矩陣，選10001000，01000100，00100010，00010001四碼組，然后從其余的四碼組，然后從其余的1111個(gè)碼組中，再選出個(gè)碼組中，再選出5 5個(gè)，通常個(gè)，通常按照碼重從小到大選擇。按照碼重從小到大選擇。100010100010011010001001001000100111HP PI Ir r實(shí)際只需實(shí)際只需9 9個(gè)個(gè)11001000001100100010010010

35、0010100010001100001 QIGk4/ M=1 0 1 0 14/ M=1 0 1 0 1C=MG=1 0 1 0 1 0 1 1 0C=MG=1 0 1 0 1 0 1 1 0Q Q3/ 3/ 求生成矩陣求生成矩陣 已知已知 TPQ I Ik k于是有：于是有：定義與特性定義與特性 循環(huán)碼是線性分組碼的一個(gè)重要子類(lèi)，也是目循環(huán)碼是線性分組碼的一個(gè)重要子類(lèi)，也是目前研究最成熟的一類(lèi)碼。它不僅有封閉性，且還有前研究最成熟的一類(lèi)碼。它不僅有封閉性，且還有循環(huán)性。循環(huán)性。(n(n，k)k)碼組碼組0121CCCCCnna則將則將所有碼元向左循環(huán)一位，得到的：所有碼元向左循環(huán)一位，得到的

36、：10132nnnbCCCCCC也是許用碼組。也是許用碼組。是許用碼組。是許用碼組。即即10111iiniCC CC CCC 若線性分組碼的若線性分組碼的任一碼組循環(huán)移位所任一碼組循環(huán)移位所得碼組仍在該碼組集得碼組仍在該碼組集中，則此碼為循環(huán)碼。中，則此碼為循環(huán)碼。序號(hào) 碼 字 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 2 0 1 0 0 1 1 1 3 0 1 1 1 0 1 0 4 1 0 0 1 1 1 0 5 1 0 1 0 0 1 1 6 1 1 0 1 0 0 1 7 1 1 1 0 1 0 0 循環(huán)碼的循環(huán)圈數(shù)循環(huán)碼的循環(huán)圈數(shù)2W=00W=42156734

37、同一循環(huán)圈內(nèi)，碼字的同一循環(huán)圈內(nèi)，碼字的重量相同重量相同 序號(hào) 碼 字 0 0 0 0 0 0 0 1 0 0 1 0 0 1 2 0 1 0 0 1 0 3 0 1 1 0 1 1 4 1 0 0 1 0 0 5 1 0 1 1 0 1 6 1 1 0 1 1 0 7 1 1 1 1 1 1W=00W=2124W=4536W=67循環(huán)碼的特點(diǎn)：循環(huán)碼的特點(diǎn)： 由于具有循環(huán)性，編譯碼設(shè)備較簡(jiǎn)單；由于具有循環(huán)性，編譯碼設(shè)備較簡(jiǎn)單； 可以用代數(shù)的方法分析和設(shè)計(jì)編碼。可以用代數(shù)的方法分析和設(shè)計(jì)編碼。已知碼組：已知碼組：0121CCCCCnn設(shè)設(shè)x x為一個(gè)任意的實(shí)變量，其冪次代表移位的次數(shù)，為一個(gè)任

38、意的實(shí)變量，其冪次代表移位的次數(shù)，以以C Ci i 作為多項(xiàng)式的系數(shù)，則可以得到碼多項(xiàng)式：作為多項(xiàng)式的系數(shù)，則可以得到碼多項(xiàng)式： )(012211CxCxCxCxCnnnn)(012211CxCxCxCxCnnnn每循環(huán)一位，相當(dāng)于碼多項(xiàng)式乘以每循環(huán)一位，相當(dāng)于碼多項(xiàng)式乘以x x，仍為許用碼組仍為許用碼組)(10212312) 1 (nnnnnCxCxCxCxCxC0 1 1 1 0 1 0 xxxxxC345)(1 1、 生成多項(xiàng)式與生成矩陣生成多項(xiàng)式與生成矩陣0 0 1 1 1 0 11)(234xxxxC例：即：那么，那么，)()()()(12xgxxgxxxgxgk，都是許用碼組，都是

39、許用碼組，而這而這k k個(gè)碼組是線性無(wú)關(guān)的。個(gè)碼組是線性無(wú)關(guān)的。于是用它們組成的矩陣則為生成矩陣于是用它們組成的矩陣則為生成矩陣)()()()(21xgxxgxgxxgxGkk0121mmmmMnn設(shè)信息碼組為：設(shè)信息碼組為：其對(duì)應(yīng)多項(xiàng)式為：其對(duì)應(yīng)多項(xiàng)式為：012211)(mxmxmxmxmkkkk)()()()(210121xgxgxxgxxgxmmmmkknn)(012211xgmxmxmxmkkkk)()(xgxm則編碼碼組為：則編碼碼組為：)()(xMGxC由上式可看出：用由上式可看出：用G(x)G(x)生成的碼字，都是生成的碼字，都是g(x)g(x)的倍式，的倍式， 都可以被都可以被

40、g(x)g(x)整除。整除。已知編碼碼組為：已知編碼碼組為：)()()(xgxmxC生成多項(xiàng)式是一個(gè)生成多項(xiàng)式是一個(gè)n-kn-k次的多項(xiàng)式，且本身也是次的多項(xiàng)式，且本身也是)()(xgxC一個(gè)許用碼組：一個(gè)許用碼組：)(xCxk為一個(gè)為一個(gè)n n次多項(xiàng)式，它是在模次多項(xiàng)式，它是在模1nx運(yùn)算下的一個(gè)許用碼組，即：運(yùn)算下的一個(gè)許用碼組，即：1)()(1)(nnkxxCxQxxCx分子分母均分子分母均為為n n次，故次，故Q(x)=1Q(x)=1于是上式成為：于是上式成為：)( 1)(xCxxCxnk( )m(x)g(x)( )g(x)( )1( )knC xC xx C xxC x將、帶入 )(

41、)()()(1xhxgxmxxgxkn有有就是說(shuō)：就是說(shuō)：的一個(gè)因式。是1)(nxxgg(x)g(x)的三個(gè)特性：的三個(gè)特性：的一個(gè)因式是1)(nxxg次多項(xiàng)式為knxg)(的常數(shù)項(xiàng)不為零)(xg 也就是說(shuō)，尋找也就是說(shuō)，尋找g(x)g(x)的過(guò)程，就是對(duì)的過(guò)程，就是對(duì) 進(jìn)行因式分解的過(guò)程。進(jìn)行因式分解的過(guò)程。1nx) 1)(1)(1(13237xxxxxx 為了尋找為了尋找(7(7，3)3)循環(huán)碼的生成多項(xiàng)式，只需找出循環(huán)碼的生成多項(xiàng)式，只需找出(n-k)=(7-3)=4(n-k)=(7-3)=4次的因式即可。次的因式即可。1) 1)(1(2423xxxxxx1) 1)(1(2343xxxx

42、xx兩者均可，但將產(chǎn)生出不同的編碼碼組。兩者均可，但將產(chǎn)生出不同的編碼碼組。(7(7，6)6)碼：碼：1)( xxg(7(7，1)1)碼：碼：(7(7，4)4)碼：碼：1)(3xxxg1)(23xxxg) 1)(1()(323xxxxxg1 1、 循環(huán)碼的編碼方法循環(huán)碼的編碼方法首先根據(jù)給定的首先根據(jù)給定的(n,k)(n,k)選定生成多項(xiàng)式選定生成多項(xiàng)式g(x)g(x)并求出并求出G(x)G(x)；由由C(x)=MG(x)C(x)=MG(x)可以生成所有碼字，但不是系統(tǒng)碼；可以生成所有碼字，但不是系統(tǒng)碼；生成系統(tǒng)碼的步驟如下：生成系統(tǒng)碼的步驟如下：1/ 1/ knxxm)(做，即在信息碼后附加

43、，即在信息碼后附加n-kn-k個(gè)零；個(gè)零；如：如：m=110m=110， n-kn-k=7-3=4=7-3=4時(shí)，時(shí)，xxxm2)(5624)()(xxxxxxxmkn相當(dāng)于：相當(dāng)于：110000011000002/ 2/ 用用g(x)g(x)除除 得到商得到商Q(x)Q(x)和余式和余式r(x)r(x)knxxm)()()()()()(xgxrxQxgxxmkn 余式余式r(x)r(x)的次數(shù)必小于的次數(shù)必小于g(x)g(x)的次數(shù)的次數(shù)n-kn-k，將此余式將此余式加于信息位之后，成為編碼多項(xiàng)式。加于信息位之后，成為編碼多項(xiàng)式。3/3/編出碼組編出碼組 )()()(xrxxmxCkn它必能被它必能被g(xg(x) )整除。整除。例例： （7 7，3 3）碼，選定）碼，選定1)(234xxxxg解解：11) 1(1)()(24222456xxxxxxxxxxxxgxxmknm=110m=110，試編碼。，試編碼。2m( ) xxxn k4xx10111101111101111100000編出碼組為：編出碼組為： 110010111001012 2、 循環(huán)碼的譯碼方法循環(huán)碼的譯碼方法0121rrrrRnn設(shè)接收碼組為設(shè)接收碼組為z z：對(duì)應(yīng)多項(xiàng)式為對(duì)應(yīng)多項(xiàng)式為R(x)R(x