版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
2023/2/51第六章信道編碼2023/2/52問(wèn)題的提出愿望:信息傳輸多快好省。現(xiàn)實(shí):(1)速度:受信道容量的限制,不可能無(wú)限大;(2)質(zhì)量:受信道噪聲的干擾,傳輸錯(cuò)誤不可避免。衡量信息傳輸可靠性的指標(biāo):平均差錯(cuò)率Pe。Pe與信道的統(tǒng)計(jì)特性有關(guān),不可能為零,有時(shí)甚至很大。降低Pe的方法:先對(duì)消息進(jìn)行編碼再送入信道傳送,這種為降低平均差錯(cuò)率而進(jìn)行的編碼稱為信道編碼;在信道輸出端加信道譯碼器進(jìn)行信息還原。香農(nóng)第二編碼定理所給出的結(jié)論:只要信道編碼和譯碼的方法得當(dāng),就可使平均差錯(cuò)率趨于零。
編碼信道信道編碼器f信道信道譯碼器F2023/2/536.1
有擾離散信道的編碼理論6.2
糾錯(cuò)編譯碼的基本原理與分析方法6.3線性分組碼6.4卷積碼6.5
其它信道編碼內(nèi)容2023/2/546.1有擾離散信道的編碼定理6.1.1差錯(cuò)和差錯(cuò)控制系統(tǒng)分類
6.1.2矢量空間與碼空間
6.1.3隨機(jī)編碼與信道編碼定理2023/2/556.1.1差錯(cuò)和差錯(cuò)控制系統(tǒng)分類差錯(cuò)率是衡量傳輸質(zhì)量的重要指標(biāo)之一,它有幾種不同的定義。碼元差錯(cuò)率/符號(hào)差錯(cuò)率指在傳輸?shù)拇a元總數(shù)中發(fā)生差錯(cuò)的碼元數(shù)所占的比例(平均值),簡(jiǎn)稱誤碼率(Errorsymbolrate)。是指信號(hào)差錯(cuò)概率比特差錯(cuò)率/比特誤碼率(Errorbitrate):在傳輸?shù)谋忍乜倲?shù)中發(fā)生差錯(cuò)的比特?cái)?shù)所占比例是指信息差錯(cuò)概率對(duì)二進(jìn)制傳輸系統(tǒng),符號(hào)差錯(cuò)等效于比特差錯(cuò);對(duì)多進(jìn)制系統(tǒng),一個(gè)符號(hào)差錯(cuò)對(duì)應(yīng)多少比特差錯(cuò)卻難以確定2023/2/56為定量地描述信號(hào)的差錯(cuò),定義差錯(cuò)圖樣E:
E=C-R(模M)最常用的二進(jìn)制碼可當(dāng)作特例來(lái)研究,其差錯(cuò)圖樣等于收碼與發(fā)碼的模2加,即E=C⊕R
或C=R⊕E設(shè)發(fā)送的碼字C1111111111
接收的碼字R1001001111
差錯(cuò)的圖樣E
0110110000差錯(cuò)圖樣中的“1”既是符號(hào)差錯(cuò)也是比特差錯(cuò),差錯(cuò)的個(gè)數(shù)叫漢明距離。差錯(cuò)圖樣類型隨機(jī)差錯(cuò),突發(fā)差錯(cuò):差錯(cuò)圖樣2023/2/57糾錯(cuò)碼分類從功能角度講,差錯(cuò)碼分為檢錯(cuò)碼和糾錯(cuò)碼按照對(duì)信息序列的處理方法,有分組碼和卷積碼按照碼元與原始信息位的關(guān)系,分為線性碼和非線性碼按照適用的差錯(cuò)類型,分成:糾隨機(jī)差錯(cuò)碼和糾突發(fā)差錯(cuò)碼按照構(gòu)造碼的理論:代數(shù)碼、幾何碼、算術(shù)碼和組合碼。2023/2/58信道編碼的基本思想信道編碼按一定規(guī)則給數(shù)字序列m增加一些多余的碼元,使不具有規(guī)律性的信息序列m變換為具有某種規(guī)律性的數(shù)碼序列C;碼序列中的信息序列碼元與多余碼元之間是相關(guān)的;信道譯碼器利用這種預(yù)知的編碼規(guī)則譯碼。檢驗(yàn)接收到的數(shù)字序列R是否符合既定的
規(guī)則,從而發(fā)現(xiàn)R中是否有錯(cuò),或者糾正其中的差錯(cuò);根據(jù)相關(guān)性來(lái)檢測(cè)/發(fā)現(xiàn)和糾正傳輸過(guò)程中產(chǎn)生的差錯(cuò)就是信道編碼的基本思想。2023/2/59差錯(cuò)控制系統(tǒng)分類前向糾錯(cuò)(FEC):發(fā)送端的信道編碼器將信息碼組編成具有一定糾錯(cuò)能力的碼。自動(dòng)請(qǐng)求重發(fā)(ARQ):發(fā)端發(fā)送檢錯(cuò)碼,如CRC(循環(huán)冗余校驗(yàn)碼)混合糾錯(cuò)(HEC):是FEC與ARQ方式的結(jié)合。信息反饋(IRQ):2023/2/5106.1.2矢量空間與碼空間分組碼的一個(gè)碼字可以看作一個(gè)n重矢量,所以可以用矢量空間來(lái)分析和理解分組碼。F表示碼元所在的數(shù)域,對(duì)于二進(jìn)制碼,F(xiàn)代表二元域{0,1}。設(shè)n重有序元素的集合V={Vi
},
則稱集合V是數(shù)域F上的n維矢量空間,或稱n維線性空間,n維矢量又稱n重(n-tuples)。線性空間的基底、自然基底、子空間、矢量正交、矢量空間正交、對(duì)偶空間“重?cái)?shù)”:構(gòu)成矢量的有序元素的個(gè)數(shù);“維數(shù)”:張成矢量空間基底的個(gè)數(shù);維數(shù)不可能大于重?cái)?shù),而當(dāng)維數(shù)小于重?cái)?shù)時(shí)說(shuō)明這是個(gè)子空間。2023/2/511碼空間和分組編碼的任務(wù)
消息k長(zhǎng) (n,k)碼字n長(zhǎng)
qk
種分組編碼器qn種
k維k重矢量n維n重矢量
通常qn>>qk,分組編碼的任務(wù)是要在n維n重矢量空間的qn種可能組合中選擇其中的qk個(gè)構(gòu)成一個(gè)碼空間,其元素就是許用碼的碼集。選擇一個(gè)k維n重子空間作為碼空間。確定由k維k重信息空間到k維n重碼空間的映射方法。碼空間的不同選擇方法,以及信息組與碼組的不同映射算法,就構(gòu)成了不同的分組碼。2023/2/5126.1.3隨機(jī)編碼與信道編碼定理
如果不考慮編碼的具體方法,而是運(yùn)用概率統(tǒng)計(jì)的方法在特定信道條件下對(duì)編碼信號(hào)的性能作出統(tǒng)計(jì)分析,求出差錯(cuò)概率的上,下限邊界,其中最優(yōu)碼所能達(dá)到的差錯(cuò)概率上界稱為隨機(jī)碼界。隨機(jī)編碼的含義2023/2/513錯(cuò)誤概率的上界對(duì)于離散無(wú)記憶信道(DMC)。錯(cuò)誤平均概率的上界為:E(R)為可靠性函數(shù),也叫誤差指數(shù)碼率:R=(lbM)
/N
M是可能的信息組合數(shù),M=qKN是每碼字的碼元數(shù),R表示每碼元攜帶的信息量,單位是每符號(hào)比特(bit/symbol)是全部碼集的平均差錯(cuò)概率2023/2/514正定理:只要傳信率R小于信道容量C,總存在一種信道碼(及解碼器),可以以所要求的任意小的差錯(cuò)概率實(shí)現(xiàn)可靠的通信。逆定理:信道容量C是可靠通信系統(tǒng)傳信率R的上邊界,如果R>C,就不可能有任何一種編碼能使差錯(cuò)概率任意小。上述兩定理統(tǒng)稱為有擾或噪聲信道的信道編碼定理信道編碼定理2023/2/5156.2糾錯(cuò)編譯碼的基本原理與分析方法6.2.1糾錯(cuò)編碼的基本原理6.2.2譯碼方法---最優(yōu)譯碼和最大似然譯碼2023/2/5166.2.1糾錯(cuò)編碼的基本原理6.2.1糾錯(cuò)編碼的基本思想一、從編碼定理出發(fā)討論糾錯(cuò)碼的基本原理:從上面的公式可以看出:要減小Pe:(1)增大N;(2)增大Er(R);1增大信道容量C(1)擴(kuò)展帶寬。(2)加大功率。(3)減小噪聲功率。2減小碼率R(=KlbQ/N)增大碼長(zhǎng)NC,R,K/N不變2023/2/517二、從冗余度和噪聲均化討論糾錯(cuò)碼的基本原理:冗余度:就是在信息流中插入冗余比特,插入的冗余比特與信息比特存在著特定的相關(guān)性。這樣如果在傳輸過(guò)程中有個(gè)別信息比特受損,也可以從冗余比特中恢復(fù)或發(fā)現(xiàn)受損比特。從而保證了信息傳輸?shù)目煽啃浴鬏斎哂啾忍乇厝灰獎(jiǎng)佑萌哂嗟馁Y源:
時(shí)間,頻帶,功率,設(shè)備復(fù)雜度噪聲均勻化:就是讓差錯(cuò)隨機(jī)化,以便符合編碼定理的條件從而得到符合編碼定理結(jié)果。其基本思想是設(shè)法將危害較大的,較為集中的噪聲干擾分?jǐn)傞_(kāi)來(lái),使不可恢復(fù)的信息損傷最小。(1)增加碼長(zhǎng)。(2)卷積。(3)交織。2023/2/518譯碼算法的已知條件是要求已知:(1)實(shí)際接收到的碼字序列{r},r=(r1,r2,…..rN)。(2)發(fā)送端所采用的編碼算法和該算法產(chǎn)生的碼集XN,滿足(3)信道模型及信道參數(shù)。消息組m(N,K)編碼器信道最佳/最大似然譯碼消息還原6.2.2譯碼方法---最優(yōu)譯碼和最大似然譯碼2023/2/519
譯碼規(guī)則與錯(cuò)誤概率信道編碼是一個(gè)一一對(duì)應(yīng)的變換或函數(shù),稱為編碼函數(shù)f;信道譯碼也是一個(gè)函數(shù),稱為譯碼函數(shù)F。編碼信道信道編碼器f信道信道譯碼器F
由于
是一一對(duì)應(yīng)變換,其反變換
唯一確定。因此,討論譯碼函數(shù)時(shí),只考慮從中還原出就可以了。平均差錯(cuò)率Pe與譯碼規(guī)則F有關(guān)。2023/2/520兩種典型的譯碼規(guī)則兩種典型的譯碼規(guī)則:最佳譯碼規(guī)則、極大似然譯碼規(guī)則
1、最佳譯碼規(guī)則:平均差錯(cuò)率最小的譯碼規(guī)則。DMC信道譯碼F
按“后驗(yàn)概率最大”原則定出,又稱最大后驗(yàn)概率譯碼規(guī)則
按“聯(lián)合概率最大”原則定出,又稱最大聯(lián)合概率譯碼規(guī)則
2023/2/5212、極大似然譯碼規(guī)則
按“轉(zhuǎn)移概率最大”原則定出,稱為極大似然譯碼規(guī)則。實(shí)際應(yīng)用中,經(jīng)常只知道信道的統(tǒng)計(jì)特性(轉(zhuǎn)移概率),而不知道信源的統(tǒng)計(jì)特性(輸入概率),這時(shí)求不出聯(lián)合概率和后驗(yàn)概率,因此無(wú)法確定最佳譯碼規(guī)則。既然只知道轉(zhuǎn)移概率,就只能按轉(zhuǎn)移概率的某種約束條件制訂譯碼規(guī)則。按最大轉(zhuǎn)移概率條件來(lái)確定的譯碼規(guī)則,稱為極大似然譯碼規(guī)則。2023/2/522極大似然譯碼規(guī)則與最佳譯碼規(guī)則等價(jià)的條件極大似然譯碼規(guī)則最佳譯碼規(guī)則結(jié)論:信道輸入等概時(shí),極大似然譯碼規(guī)則與最佳譯碼規(guī)則等價(jià)。證明:
輸入等概(1)信道輸入是近似等概的:因?yàn)樾诺狼凹?jí)有信源編碼器存在。(2)極大似然譯碼規(guī)則近似最佳,可以放心使用。
注:2023/2/523最佳譯碼,也叫最大后驗(yàn)概率譯碼(MAP)最大似然譯碼(MLD)
消息組mi
碼字ci
接收碼r
估值
消息信道消息還原編碼器譯碼2023/2/524碼字的似然函數(shù)為了方便計(jì)算,可以利用對(duì)數(shù)運(yùn)算將乘法運(yùn)算轉(zhuǎn)化為加法運(yùn)算。即:2023/2/525BSC信道2023/2/526漢明距離譯碼是一種硬判決譯碼。由于BSC信道是對(duì)稱的,只要發(fā)送的碼字獨(dú)立、等概,漢明距離譯碼也就是最佳譯碼。最大似然譯碼等效于最小漢明距離譯碼。2023/2/5276.3線性分組碼6.3.1線性分組碼的生成矩陣和校驗(yàn)矩陣6.3.2伴隨式與標(biāo)準(zhǔn)陣列譯碼6.3.3碼距,糾錯(cuò)能力,MDC碼等6.3.4完備碼,循環(huán)碼,BCH和RS碼6.3.5分組碼的擴(kuò)展,縮短和CRC2023/2/5286.3線性分組碼(n,k)分組碼是把信息流分割成一串前后獨(dú)立的k比特信息組,再將每組信息元映射成n個(gè)碼元組成的碼字。如下圖:m0m1m2……mk-1m0m1m2…..mk-1m0m1m2……mk-1….
C0C1C3………...Cn-1C0C1C3……....Cn-1C0C1C3………....Cn-1K個(gè)信息元可以寫成矢量(mk-1,….m1,m0)或者矩陣的形式[mk-1,….m1,m0]。同樣碼字可以表示為(Cn-1,….C1,C0)或者[Cn-1,….C1,C0].(碼矢,碼字,碼組)2023/2/529線性分組碼中,必須考慮的問(wèn)題:(1)碼集C能否構(gòu)成n維n重矢量空間的一個(gè)k維n重子空間。(2)如何尋找最佳的碼空間。(3)qk個(gè)信息元組以怎樣的算法一一映射到碼空間。碼率對(duì)于二元分組碼(n,k),其碼率定義為:RC=k/n對(duì)于q元分組碼(n,k),其碼率定義為:RC=klbq/n
消息m (n,k)碼字c
m=(mk-1,…,m1,m0)分組編碼器c=(cn-1,…,c1,c0)
qk<qn2023/2/5306.3.1 生成矩陣和校驗(yàn)矩陣
線性分組碼的碼空間C
是由k
個(gè)線性無(wú)關(guān)的基底
gk-1,,...g1,g0
張成的k維n重子空間,所有碼字都可寫成k個(gè)基底的線性組合,即 c=
mk-1
gk-1+…+
m1
g1+m0g02023/2/531生成矩陣
當(dāng)信息元確定后,碼字僅由G矩陣決定,因此我們稱這k×n
矩陣G為該(n,k)線性分組碼的生成矩陣。如果已知線性分組碼的生成矩陣,則任何一個(gè)k位信息組對(duì)應(yīng)的碼字都可以由mG運(yùn)算得到。
2023/2/532生成矩陣G(k×n)的特點(diǎn)想要保證(n,k)線性分組碼能夠構(gòu)成k維n重子空間,G的k個(gè)行矢量gk-1,…,g1,g0必須是線性無(wú)關(guān)的,只有這樣才符合作為基底的條件。由于k個(gè)基底即G的k個(gè)行矢量線性無(wú)關(guān),矩陣G的秩一定等于k。由于基底不是唯一的,所以G也就不是唯一的。不同的基底有可能生成同一碼集,但因編碼涉及碼集和映射兩個(gè)因素,碼集一樣而映射方法不同也不能說(shuō)是同樣的碼。2023/2/533例如2023/2/534系統(tǒng)形式的生成矩陣(n,k)碼的任何生成矩陣都可以通過(guò)行運(yùn)算(不改變碼集,只改變映射規(guī)則)簡(jiǎn)化成“系統(tǒng)形式”。G=[Ik
P]=Ik是k×k單位矩陣,P是k×(n-k)矩陣。2023/2/535復(fù)習(xí):定義
下面三種變換稱為矩陣的初等行變換:1.
互換兩行;2.
以數(shù)k
乘以某一行;3.
把某一行的k倍加到另一行上。若將定義中的“行”換成“列”,則稱之為初等列變換,初等行變換和初等列變換統(tǒng)稱為初等變換。2023/2/536系統(tǒng)碼前k位由單位矩陣Ik決定,等于把信息組m原封不動(dòng)搬到碼字的前k位;
mG=m[Ik
P]=[mIk
mP]=[mmP]其余的n-k位叫冗余位或一致校驗(yàn)位,是前k個(gè)信息位的線性組合。這樣生成的(n,k)碼叫做系統(tǒng)碼。若生成矩陣G不具備系統(tǒng)形式,則生成的碼叫做非系統(tǒng)碼。系統(tǒng)化不改變碼集,只是改變了映射規(guī)則。2023/2/537由上面的生成矩陣生成的碼字的特點(diǎn):特點(diǎn):碼字的前面k位就是信息組中的k位,而后面的校驗(yàn)位為信息組的線性組合。2023/2/538空間構(gòu)成n維n重空間有相互正交的n個(gè)基底選擇k個(gè)基底構(gòu)成碼空間C選擇另外的(n-k)個(gè)基底構(gòu)成空間DC和D是對(duì)偶的
n維n重空間V
k維k重k維n重n-k維信息組碼空間n重D
空間m
C
H
G2023/2/539校驗(yàn)矩陣將D空間的n-k個(gè)基底排列起來(lái)可構(gòu)成一個(gè)(n-k)×n矩陣,稱為校驗(yàn)矩陣H,也稱監(jiān)督矩陣。用來(lái)校驗(yàn)接收到的碼字是否是正確的;即:若c為碼空間C中的任意碼字,則若不滿足此等式,則c必定不是碼空間C中的碼字。2023/2/5402023/2/5412023/2/5422023/2/543校驗(yàn)矩陣G是(n,k)碼的生成矩陣,H是它的校驗(yàn)矩陣;H是(n,n-k)對(duì)偶碼的生成矩陣,它的每一行是對(duì)偶碼的一個(gè)碼字。G則是它的校驗(yàn)矩陣。GHT=0,H=[-
PTIn-k],二進(jìn)制時(shí),負(fù)號(hào)可省略。2023/2/544校驗(yàn)矩陣與生成矩陣的關(guān)系如果系統(tǒng)碼的生成矩陣為G=[IK|P],則其對(duì)應(yīng)的校驗(yàn)矩陣為H=[-PT|In-k]GHT=0或者HGT=02023/2/545例6-2
某線性分組碼,其生成矩陣是
G=求:(1)計(jì)算碼集,列出信息組與碼字的映射關(guān)系。(2)將該碼系統(tǒng)化處理后,計(jì)算系統(tǒng)碼碼集并列出映射關(guān)系。(3)計(jì)算系統(tǒng)碼的校驗(yàn)矩陣H。若收碼r=[100110],檢驗(yàn)它是否碼字?
(4)根據(jù)系統(tǒng)碼生成矩陣畫出編碼器電原理圖。
111010①110001②011101③2023/2/546例6-2碼集與映射關(guān)系信息碼字系統(tǒng)碼字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111 010110 111010做初等行變換2023/2/547例6-2二元(6,3)線性分組碼編碼器m0
m1
m2
輸入 輸出
c0
c1
c22023/2/548下面是某線性二元碼的全部碼字:
。⑴求n,k的值;⑵構(gòu)造這碼的生成矩陣G;(找3個(gè)線性無(wú)關(guān)的碼字構(gòu)成G,并化為系統(tǒng)形式)⑶構(gòu)成這碼的一致校驗(yàn)矩陣H。
2023/2/5496.3.2伴隨式與標(biāo)準(zhǔn)陣列譯碼mC=(cn-1,…,c1,c0)R=(rn-1,…,r1,r0)
(n,k)信道定義差錯(cuò)圖案EE=(en-1,…,e1,e0)=R-C
=(rn-1-cn-1,…,r1-c1,r0-c0)二進(jìn)制碼中模2加與模2減是等同的,因此有 E=R+C及 R=C+E 2023/2/550伴隨式S的定義因?yàn)镃HT=0所以RHT=(C+E)HT=CHT+EHT=EHT如果收碼無(wú)誤:必有R=C即E=0,則EHT=0RHT=0。如果收碼有誤:即E0,則RHT=EHT0。在HT固定的前提下,RHT僅僅與差錯(cuò)圖案E有關(guān),而與發(fā)送碼C無(wú)關(guān)。定義伴隨式SS=(sn-k-1,…,s1,s0)=RHT=EHT
2023/2/551從物理意義上看,伴隨式S并不反映發(fā)送的碼字是什么,而只是反映信道對(duì)碼字造成怎樣的干擾。差錯(cuò)圖案E是n重矢量,共有2n個(gè)可能的組合,而伴隨式S是(n-k)重矢量,只有2n-k個(gè)可能的組合,因此不同的差錯(cuò)圖案可能有相同的伴隨式。接收端收到R后,因?yàn)橐阎狧T,可求出S=RHT;如果能知道對(duì)應(yīng)的E,則通過(guò)C=R+E而求得C。
RHT=S ?C=R+ERSEC
只要E正確,譯出的碼也就是正確的。伴隨式S的意義2023/2/552譯碼過(guò)程框圖
(R=B)2023/2/553例
一個(gè)(5,2)系統(tǒng)線性碼的生成矩陣是G=設(shè)收碼R=(10101),構(gòu)造標(biāo)準(zhǔn)陣列譯碼表,譯出發(fā)碼的估值解:(1)構(gòu)造標(biāo)準(zhǔn)陣列譯碼表。分別以信息組m=(00)、(01)、(10)、(11)及已知的G求得4個(gè)許用碼字為C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。求出校驗(yàn)矩陣:
H=[PTI3]=2023/2/554列出方程組:由RHT確定S后,對(duì)應(yīng)的E可以有2k(22=4)個(gè)解,究竟取哪一個(gè)作為差錯(cuò)圖樣E的解?最簡(jiǎn)單明了的處理方法是概率譯碼,即對(duì)所有2k個(gè)解的重量(差錯(cuò)圖樣E中1的個(gè)數(shù))進(jìn)行比較,選擇重量最小的作為E的估值。由于E=R+C,E重量最小,就是R和C的漢明距離最小。2023/2/555依據(jù):若BSC信道的差錯(cuò)概率是p,則長(zhǎng)度n的碼中錯(cuò)誤概率
0個(gè)錯(cuò)1個(gè)錯(cuò)2個(gè)錯(cuò)…n個(gè)錯(cuò)概率
(1-p)n
p(1-p)n-1
p2(1-p)n-2
pn
由于p<<1,則(1-p)n>>p(1-p)n-1>>p2(1-p)n-2>>…>>
pn
出錯(cuò)越少的情況,發(fā)生概率越大,E的重量越輕,所以該譯碼方法實(shí)際上體現(xiàn)了最小距離譯碼準(zhǔn)則,即最大似然譯碼。顯然,在進(jìn)行概率譯碼時(shí),每接收一個(gè)碼字就要解一次線性方程,非常復(fù)雜麻煩。但如果n-k不太大,我們可以預(yù)先把不同校正子S情況下的所有方程組都預(yù)先解出來(lái),將各種情況下的最大概率譯碼輸出列成一個(gè)標(biāo)準(zhǔn)陣列譯碼表。這樣,在實(shí)際譯碼時(shí)就不必解方程,只要查譯碼表就可以了。2023/2/556伴隨式有2n-k=23=8種組合,差錯(cuò)圖案中代表無(wú)差錯(cuò)的有一種,代表一個(gè)差錯(cuò)的圖案有種,已有6種。代表兩個(gè)差錯(cuò)的圖案有種。只需挑選其中的兩個(gè),挑選方法可有若干種,不是唯一的。先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的線性方程組,解得對(duì)應(yīng)的Sj分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中,(011)所對(duì)應(yīng)的差錯(cuò)圖案是2k個(gè)即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最輕,任選其中一個(gè)如(00011)。同樣可得伴隨式(110)所對(duì)應(yīng)的最輕差錯(cuò)圖案之一是(00110)。例6-3譯碼表的構(gòu)成2023/2/557S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例6-3標(biāo)準(zhǔn)陣列譯碼表2023/2/558例6-3將接收碼R=10101譯碼可選以下三種方法之一譯碼:直接搜索碼表,查得(10101)所在列的子集頭是(10111),因此譯碼輸出取為(10111)。先求伴隨式RHT=(10101)HT=(010)=S4,確定S4所在行,再沿著行對(duì)碼表作一維搜索找到(10101),最后順著所在列向上找出碼字(10111)。先求出伴隨式RHT=(010)=S4并確定S4所對(duì)應(yīng)的陪集首(差錯(cuò)圖案)E4=(00010),再將陪集首與收碼相加得到碼字C=R+E4=(10101)+(00010)=(10111)。2023/2/559差錯(cuò)圖案E的求解(1)
可以通過(guò)解線性方程求解E:
S=(sn-k-1,…,s1,s0)=EHT
=(en-1,…e1,e0)得到線性方程組:
sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0
s1=en-1h1(n-1)+…+e1h11+e0h10
s0=en-1h0(n-1)+…+e1h01+e0h002023/2/560上述方程組中有n個(gè)未知數(shù)en-1,…e1,e0
,卻只有n-k個(gè)方程,可知方程組有多解。在有理數(shù)或?qū)崝?shù)域中,少一個(gè)方程就可能導(dǎo)致無(wú)限多個(gè)解,而在二元域中,少一個(gè)方程導(dǎo)致兩個(gè)解,少兩個(gè)方程四個(gè)解,以此類推,少n-(n-k)=k個(gè)方程導(dǎo)致這組未知數(shù)有2k組解。概率譯碼:把所有2k個(gè)解的重量(差錯(cuò)圖案E中1的個(gè)數(shù))作比較,選擇其中最輕者作為E的估值。該方法概念上很簡(jiǎn)單但計(jì)算效率不高。差錯(cuò)圖案E的求解(2)
2023/2/561標(biāo)準(zhǔn)陣列譯碼表
在伴隨式S的數(shù)目是有限的2n-k個(gè),如果n-k不太大,我們可以預(yù)先把不同S下的方程組解出來(lái),把各種情況下的最大概率譯碼輸出列成一個(gè)碼表。這樣,在實(shí)時(shí)譯碼時(shí)就不必再去解方程,而只要象查字典那樣查一下碼表就可以了。這樣構(gòu)造的表格叫做標(biāo)準(zhǔn)陣列譯碼表。表中所列碼字是接收到的碼字R;將沒(méi)有任何差錯(cuò)時(shí)的收碼R放在第一行,收碼等于發(fā)碼R=C(CCi,i=0,1,…2k-1),差錯(cuò)圖案為全零E0=(0,0…0),伴隨式為全零S0=(0,0…0)。由于有2k個(gè)碼字,碼表有2k列。2023/2/562在第2到第n+1的n行中差錯(cuò)圖案的所有重量為1(共n個(gè))。如果(1+n)<2n-k,再在下面行寫出全部帶有2個(gè)差錯(cuò)的圖案(共個(gè))。標(biāo)準(zhǔn)陣列譯碼表的構(gòu)成
如果總行數(shù)(1+n+)仍然小于2n-k,再列出帶有3個(gè)差錯(cuò)的圖案,以此類推,直到放滿2n-k行,每行一個(gè)Ej,對(duì)應(yīng)一個(gè)不同的伴隨式Sj。這樣,表的行數(shù)2n-k正好等于伴隨式的數(shù)目。2023/2/563S0E0S1E1
SjEj
E0+C0=0+0=0E0+C1=C1E0+Ci=CiE1+C0=E1
E1+CiEj+C0=EjEj+C1Ej+Ci
標(biāo)準(zhǔn)陣列譯碼表
E1+C1
2023/2/564
在制定標(biāo)準(zhǔn)陣列譯碼表的過(guò)程中,由S決定差錯(cuò)圖案E時(shí)只有前6行真正體現(xiàn)了最大似然譯碼準(zhǔn)則,而第7、8行的差錯(cuò)圖案選擇不是唯一的。比如第7行可有(00011)和(10100)兩個(gè)選擇,如果當(dāng)時(shí)選的不是(00011)而是(10100),那么碼表第7行就不是現(xiàn)在這樣了。那么在譯碼時(shí)最后的結(jié)果也就不一樣了。為什么會(huì)出現(xiàn)這種情況呢?伴隨式的個(gè)數(shù)2n-k與n、k及糾錯(cuò)能力t
有一定的數(shù)量關(guān)系。對(duì)例6-3的分析2023/2/5656.3.3碼距、糾錯(cuò)能力、MDC碼及重量譜
N重碼矢c=(cn-1,cn-2,…c1,c0)可與N維矢量空間XN中的一個(gè)點(diǎn)對(duì)應(yīng),全體碼字所對(duì)應(yīng)的點(diǎn)構(gòu)成矢量空間里的一個(gè)子集發(fā)碼一定在這個(gè)子集里,傳輸無(wú)誤時(shí)的收碼也一定位于該子集當(dāng)出現(xiàn)差錯(cuò)時(shí),接收的N重矢量:對(duì)應(yīng)到子集外空間某一點(diǎn)
對(duì)應(yīng)到該子集,卻對(duì)應(yīng)到該子集的另一點(diǎn)上
2023/2/566td=7dmin=3d=5C1C2C3C4C5碼集各碼字間的距離是不同的,碼距最小者決定碼的特性,稱之為最小距離dmin這里dmin=3,糾錯(cuò)能力是1,檢錯(cuò)能力是2碼距2023/2/567定理6.1
任何最小距離dmin的線性分組碼,其檢錯(cuò)能力為(dmin-1),糾錯(cuò)能力t為最小距離dmin表明碼集中各碼字差異的程度,差異越大越容易區(qū)分,抗干擾能力就越強(qiáng),是衡量分組碼性能的最重要的指標(biāo)之一。定理6.2
線性分組碼的最小距離等于碼集中非零碼字的最小重量
dmin=min{w(Ci)} CiC及Ci
0 糾錯(cuò)能力2023/2/568定理6.3(n,k)線性分組碼最小距離等于dmin的充要條件是:校驗(yàn)矩陣H中有(dmin-1)列線性無(wú)關(guān)。定理6.4(n,k)線性分組碼的最小距離必定小于等于
(n-k+1),即
dmin
(n-k+1) 糾錯(cuò)能力
糾錯(cuò)能力
定理6.3(應(yīng)為):
對(duì)于(n,k)線性分組碼:校驗(yàn)矩陣H中的任意t列線性無(wú)關(guān)而t+1列線性相關(guān),則碼的最小距離dmin或碼字的最小重量為t+1.反之,若碼字的最小重量或碼的最小距離為t+1則H的任意t列線性無(wú)關(guān)而t+1列線性相關(guān)。見(jiàn)《信息論基礎(chǔ)教程》,李亦農(nóng),李梅編著,北京郵電大學(xué)出版社。P1592023/2/5692023/2/570例:
H=(7,4)線性碼各列都不相同,任意2列之和不等于0,2列線性無(wú)關(guān);任意2列之和一定等于矩陣中某一列,任意3列線性相關(guān)。所以該碼的最小距離為3,小于n-k+1=4。糾錯(cuò)能力
2023/2/571(2)為糾正t個(gè)錯(cuò)碼,要求最小碼距(1)為檢測(cè)e個(gè)錯(cuò)碼,要求最小碼距最小碼距與檢錯(cuò)能力圖示(3)為糾正t個(gè)錯(cuò)碼,同時(shí)檢測(cè)e個(gè)錯(cuò)碼,要求最小碼距(e>t)2023/2/572(n,k)線性碼最小距離dmin的上邊界是n-k+1。如果我們?cè)O(shè)計(jì)的(n,k)線性碼的dmin達(dá)到了n-k+1,就是達(dá)到了設(shè)計(jì)性能的極點(diǎn)。因此,dmin=n-k+1的碼稱為極大最小距離碼
(MDC–MaximizedminimumDistanceCode)。
(1)二進(jìn)制碼中,除了將一位信息重復(fù)n次的(n,1)碼外,不存在其它二進(jìn)制MDC碼;
(2)非二進(jìn)制碼中,MDC碼是存在的,如RS碼(reed-solomon)。MDC碼(MaximizedminimumDistanceCode)2
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 出租房屋協(xié)議模板范本
- 2025女方離婚協(xié)議書
- 運(yùn)動(dòng)障礙性腦癱病因介紹
- 表皮囊腫病因介紹
- 質(zhì)量策劃方案20241219
- (案例)標(biāo)準(zhǔn)件項(xiàng)目立項(xiàng)報(bào)告
- (2024)冷渣器生產(chǎn)建設(shè)項(xiàng)目可行性研究報(bào)告(一)
- 2022-2023學(xué)年天津市高一(上)期末語(yǔ)文試卷
- 2022-2023學(xué)年天津四中高二(上)期末語(yǔ)文試卷
- 重慶2020-2024年中考英語(yǔ)5年真題回-學(xué)生版-專題07 閱讀理解之說(shuō)明文
- 國(guó)省干線公路隧道維修加固工程專項(xiàng)施工方案
- 機(jī)械優(yōu)化設(shè)計(jì)完整版PPT課件.ppt
- 重慶開(kāi)縣井噴事故
- 浙美版六年級(jí)上冊(cè)美術(shù)復(fù)習(xí)資料
- 年度工作總結(jié)ppt美觀模板
- 臨時(shí)施工用電工程監(jiān)理實(shí)施細(xì)則
- 低壓鑄造常見(jiàn)缺陷及預(yù)防
- 輻照滅菌與其他主要滅菌方式對(duì)比所存在的優(yōu)點(diǎn)
- 訂單評(píng)審作業(yè)流程
- 側(cè)鉆井工藝技術(shù)簡(jiǎn)介
- 設(shè)計(jì)加熱爐推料機(jī)傳動(dòng)裝置 - 副本
評(píng)論
0/150
提交評(píng)論