通訊原理第11章

通信原理1整理ppt通信原理第11章過失控制編碼2整理ppt第11章過失控制編碼11.1概述信道分類：從過失控制角度看隨機(jī)信道：錯碼的出現(xiàn)是隨機(jī)的突發(fā)信道：錯碼是成串集中出現(xiàn)的混合信道：既存在隨機(jī)錯碼又存在突發(fā)錯碼過失控制技術(shù)的種類檢錯重發(fā)前向糾錯反響校驗檢錯刪除3整理ppt第11章過失控制編碼過失控制編碼：常稱為糾錯編碼監(jiān)督碼元：上述4種技術(shù)中除第3種外，都是在接收端識別有無錯碼。所以在發(fā)送端需要在信息碼元序列中增加一些過失控制碼元，它們稱為監(jiān)督碼元。不同的編碼方法，有不同的檢錯或糾錯能力。多余度：就是指增加的監(jiān)督碼元多少。例如，假設(shè)編碼序列中平均每兩個信息碼元就添加一個監(jiān)督碼元，那么這種編碼的多余度為1/3。編碼效率(簡稱碼率)：設(shè)編碼序列中信息碼元數(shù)量為k，總碼元數(shù)量為n，那么比值k/n就是碼率。冗余度：監(jiān)督碼元數(shù)(n-k)和信息碼元數(shù)k之比。理論上，過失控制以降低信息傳輸速率為代價換取提高傳輸可靠性。4整理ppt第11章過失控制編碼自動要求重發(fā)(ARQ)系統(tǒng)3種ARQ系統(tǒng)停止等待ARQ系統(tǒng)數(shù)據(jù)按分組發(fā)送。每發(fā)送一組數(shù)據(jù)后發(fā)送端等待接收端確實認(rèn)(ACK)答復(fù)，然后再發(fā)送下一組數(shù)據(jù)。圖中的第3組接收數(shù)據(jù)有誤，接收端發(fā)回一個否認(rèn)(NAK)答復(fù)。這時，發(fā)送端將重發(fā)第3組數(shù)據(jù)。系統(tǒng)是工作在半雙工狀態(tài)，時間沒有得到充分利用，傳輸效率較低。接收碼組ACKACKNAKACKACKNAKACKt1233455發(fā)送碼組12334556t有錯碼組有錯碼組5整理ppt第11章過失控制編碼拉后ARQ系統(tǒng)發(fā)送端連續(xù)發(fā)送數(shù)據(jù)組，接收端對于每個接收到的數(shù)據(jù)組都發(fā)回確認(rèn)(ACK)或否認(rèn)(NAK)答復(fù)。例如，圖中第5組接收數(shù)據(jù)有誤，那么在發(fā)送端收到第5組接收的否認(rèn)答復(fù)后，從第5組開始重發(fā)數(shù)據(jù)組。在這種系統(tǒng)中需要對發(fā)送的數(shù)據(jù)組和答復(fù)進(jìn)行編號，以便識別。顯然，這種系統(tǒng)需要雙工信道接收數(shù)據(jù)有錯碼組有錯碼組91011101112214365798576ACK1NAK5NAK9ACK5發(fā)送數(shù)據(jù)57695214367981011101112重發(fā)碼組重發(fā)碼組6整理ppt第11章過失控制編碼選擇重發(fā)ARQ系統(tǒng)它只重發(fā)出錯的數(shù)據(jù)組，因此進(jìn)一步提高了傳輸效率。接收數(shù)據(jù)有錯碼組有錯碼組921436575981011131412發(fā)送數(shù)據(jù)995852143671011131412重發(fā)碼組重發(fā)碼組NAK9ACK1NAK5ACK5ACK97整理ppt第11章過失控制編碼ARQ的主要優(yōu)點(diǎn)：和前向糾錯方法相比監(jiān)督碼元較少即能使誤碼率降到很低，即碼率較高；檢錯的計算復(fù)雜度較低；檢錯用的編碼方法和加性干擾的統(tǒng)計特性根本無關(guān)，能適應(yīng)不同特性的信道。ARQ的主要缺點(diǎn)：需要雙向信道來重發(fā)，不能用于單向信道，也不能用于一點(diǎn)到多點(diǎn)的通信系統(tǒng)。因為重發(fā)而使ARQ系統(tǒng)的傳輸效率降低。在信道干擾嚴(yán)重時，可能發(fā)生因不斷反復(fù)重發(fā)而造成事實上的通信中斷。在要求實時通信的場合，例如通信，往往不允許使用ARQ法。8整理ppt第11章過失控制編碼ARQ系統(tǒng)的原理方框圖在發(fā)送端，輸入的信息碼元在編碼器中被分組編碼〔參加監(jiān)督碼元〕后，除了立即發(fā)送外，還暫存于緩沖存儲器中。假設(shè)接收端解碼器檢出錯碼，那么由解碼器控制產(chǎn)生一個重發(fā)指令。此指令經(jīng)過反向信道送到發(fā)送端。由發(fā)送端重發(fā)控制器控制緩沖存儲器重發(fā)一次。接收端僅當(dāng)解碼器認(rèn)為接收信息碼元正確時，才將信息碼元送給收信者，否那么在輸出緩沖存儲器中刪除接收碼元。當(dāng)解碼器未發(fā)現(xiàn)錯碼時，經(jīng)過反向信道發(fā)出不需重發(fā)指令。發(fā)送端收到此指令后，即繼續(xù)發(fā)送后一碼組，發(fā)送端的緩沖存儲器中的內(nèi)容也隨之更新。9整理ppt第11章過失控制編碼11.2糾錯編碼的根本原理 分組碼根本原理：舉例說明如下。設(shè)有一種由3位二進(jìn)制數(shù)字構(gòu)成的碼組，它共有8種不同的可能組合。假設(shè)將其全部用來表示天氣，那么可以表示8種不同天氣， 例如：“000〞〔晴〕，“001〞〔云〕， “010〞〔陰〕，“011〞〔雨〕， “100〞〔雪〕，“101〞〔霜〕， “110〞〔霧〕，“111〞〔雹〕。其中任一碼組在傳輸中假設(shè)發(fā)生一個或多個錯碼，那么將變成另一個信息碼組。這時，接收端將無法發(fā)現(xiàn)錯誤。10整理ppt第11章過失控制編碼假設(shè)在上述8種碼組中只準(zhǔn)許使用4種來傳送天氣，例如：“000〞＝晴 “011〞＝云“101〞＝陰“110〞＝雨這時，雖然只能傳送4種不同的天氣，但是接收端卻有可能發(fā)現(xiàn)碼組中的一個錯碼。例如，假設(shè)“000〞〔晴〕中錯了一位，那么接收碼組將變成“100〞或“010〞或“001〞。這3種碼組都是不準(zhǔn)使用的，稱為禁用碼組。接收端在收到禁用碼組時，就認(rèn)為發(fā)現(xiàn)了錯碼。當(dāng)發(fā)生3個錯碼時，“000〞變成了“111〞，它也是禁用碼組，故這種編碼也能檢測3個錯碼。但是這種碼不能發(fā)現(xiàn)一個碼組中的兩個錯碼，因為發(fā)生兩個錯碼后產(chǎn)生的是許用碼組。11整理ppt第11章過失控制編碼檢錯和糾錯上面這種編碼只能檢測錯碼，不能糾正錯碼。例如，當(dāng)接收碼組為禁用碼組“100〞時，接收端將無法判斷是哪一位碼發(fā)生了錯誤，因為晴、陰、雨三者錯了一位都可以變成“100〞。要能夠糾正錯誤，還要增加多余度。例如，假設(shè)規(guī)定許用碼組只有兩個：“000〞〔晴〕，“111〞〔雨〕，其他都是禁用碼組，那么能夠檢測兩個以下錯碼，或能夠糾正一個錯碼。例如，當(dāng)收到禁用碼組“100〞時，假設(shè)當(dāng)作僅有一個錯碼，那么可以判斷此錯碼發(fā)生在“1〞位，從而糾正為“000〞〔晴〕。因為“111〞〔雨〕發(fā)生任何一位錯碼時都不會變成“100〞這種形式。但是，這時假設(shè)假定錯碼數(shù)不超過兩個，那么存在兩種可能性：“000〞錯一位和“111〞錯兩位都可能變成“100〞，因而只能檢測出存在錯碼而無法糾正錯碼。12整理ppt第11章過失控制編碼分組碼的結(jié)構(gòu)將信息碼分組，為每組信息碼附加假設(shè)干監(jiān)督碼的編碼稱為分組碼。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。信息位和監(jiān)督位的關(guān)系：舉例如下信息位監(jiān)督位晴000云011陰101雨11013整理ppt第11章過失控制編碼分組碼的一般結(jié)構(gòu)分組碼的符號：(n,k)N－碼組的總位數(shù)，又稱為碼組的長度〔碼長〕，k－碼組中信息碼元的數(shù)目，n–k＝r－碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。14整理ppt第11章過失控制編碼分組碼的碼重和碼距碼重：把碼組中“1〞的個數(shù)目稱為碼組的重量，簡稱碼重。碼距：把兩個碼組中對應(yīng)位上數(shù)字不同的位數(shù)稱為碼組的距離，簡稱碼距。碼距又稱漢明距離。例如，“000〞＝晴，“011〞＝云，“101〞＝陰，“110〞＝雨，4個碼組之間，任意兩個的距離均為2。最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最小碼距(d0)。例如，上面的編碼的最小碼距d0=2。15整理ppt第11章過失控制編碼碼距的幾何意義對于3位的編碼組，可以在3維空間中說明碼距的幾何意義。每個碼組的3個碼元的值(a1,a2,a3)就是此立方體各頂點(diǎn)的坐標(biāo)。而上述碼距概念在此圖中就對應(yīng)于各頂點(diǎn)之間沿立方體各邊行走的幾何距離。由此圖可以直觀看出，上例中4個準(zhǔn)用碼組之間的距離均為2。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a116整理ppt第11章過失控制編碼碼距和檢糾錯能力的關(guān)系一種編碼的最小碼距d0的大小直接關(guān)系著這種編碼的檢錯和糾錯能力為檢測e個錯碼，要求最小碼距d0e+1 【證】設(shè)一個碼組A位于O點(diǎn)。假設(shè)碼組A中發(fā)生一個錯碼，那么我們可以認(rèn)為A的位置將移動至以O(shè)點(diǎn)為圓心，以1為半徑的圓上某點(diǎn)，但其位置不會超出此圓。 假設(shè)碼組A中發(fā)生兩位錯碼，那么其位置不會超出以O(shè)點(diǎn)為圓心，以2為半徑的圓。因此，只要最小碼距不小于3，碼組A發(fā)生兩位以下錯碼時， 不可能變成另一個準(zhǔn)用 碼組，因而能檢測錯碼 的位數(shù)等于2。0123BA漢明距離ed017整理ppt第11章過失控制編碼 同理，假設(shè)一種編碼的最小碼距為d0，那么將能檢測(d0-1)個錯碼。反之，假設(shè)要求檢測e個錯碼，那么最小碼距d0至少應(yīng)不小于(e+1)。為了糾正t個錯碼，要求最小碼距d02t+1【證】圖中畫出碼組A和B的距離為5。碼組A或B假設(shè)發(fā)生不多于兩位錯碼，那么其位置均不會超出半徑為2以原位置為圓心的圓。這兩個圓是不重疊的。判決規(guī)那么為：假設(shè)接收碼組落于以A為圓心的圓上就判決收到的是碼組A，假設(shè)落于以B為圓心的圓上就判決為碼組B。 這樣，就能夠糾 正兩位錯碼。BtA漢明距離012345td018整理ppt第11章過失控制編碼 假設(shè)這種編碼中除碼組A和B外，還有許多種不同碼組，但任兩碼組之間的碼距均不小于5，那么以各碼組的位置為中心以2為半徑畫出之圓都不會互相重疊。這樣，每種碼組如果發(fā)生不超過兩位錯碼都將能被糾正。因此，當(dāng)最小碼距d0＝5時，能夠糾正2個錯碼，且最多能糾正2個。假設(shè)錯碼到達(dá)3個，就將落入另一圓上，從而發(fā)生錯判。故一般說來，為糾正t個錯碼，最小碼距應(yīng)不小于(2t+1)。19整理ppt第11章過失控制編碼為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距 在解釋此式之前，先來分析以下圖所示的例子。圖中碼組A和B之間距離為5。按照檢錯能力公式，最多能檢測4個錯碼，即e=d0–1=5–1=4，按照糾錯能力公式糾錯時，能糾正2個錯碼。但是，不能同時作到兩者，因為當(dāng)錯碼位數(shù)超過糾錯能力時，該碼組立即進(jìn)入另一碼組的圓內(nèi)而被錯誤地“糾正〞了。例如，碼組A假設(shè)錯了3位，就會被誤認(rèn)為碼組B錯了2位造成的結(jié)果，從而被 錯“糾〞為B。這就 是說，檢錯和糾錯 公式不能同時成立 或同時運(yùn)用。BtA漢明距離012345td020整理ppt第11章過失控制編碼 所以，為了在可以糾正t個錯碼的同時，能夠檢測e個錯碼，就需要像以下圖所示那樣，使某一碼組〔譬如碼組A〕發(fā)生e個錯誤之后所處的位置，與其他碼組〔譬如碼組B〕的糾錯圓圈至少距離等于1，不然將落在該糾錯圓上從而發(fā)生錯誤地“糾正〞。因此，由此圖可以直觀看出，要求最小碼距 這種糾錯和檢錯結(jié)合的工作方式簡稱糾檢結(jié)合。ABe1tt漢明距離21整理ppt第11章過失控制編碼 這種工作方式是自動在糾錯和檢錯之間轉(zhuǎn)換的。當(dāng)錯碼數(shù)量少時，系統(tǒng)按前向糾錯方式工作，以節(jié)省重發(fā)時間，提高傳輸效率；當(dāng)錯碼數(shù)量多時，系統(tǒng)按反響重發(fā)方式糾錯，以降低系統(tǒng)的總誤碼率。所以，它適用于大多數(shù)時間中錯碼數(shù)量很少，少數(shù)時間中錯碼數(shù)量多的情況。22整理ppt第11章過失控制編碼11.3糾錯編碼的性能系統(tǒng)帶寬和信噪比的矛盾：由上節(jié)所述的糾錯編碼原理可知，為了減少接收錯誤碼元數(shù)量，需要在發(fā)送信息碼元序列中參加監(jiān)督碼元。這樣作的結(jié)果使發(fā)送序列增長，冗余度增大。假設(shè)仍須保持發(fā)送信息碼元速率不變，那么傳輸速率必須增大，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中噪聲功率增大，使信噪比下降。信噪比的下降反而又使系統(tǒng)接收碼元序列中的錯碼增多。一般說來，采用糾錯編碼后，誤碼率總是能夠得到很大改善的。改善的程度和所用的編碼有關(guān)。23整理ppt第11章過失控制編碼編碼性能舉例未采用糾錯編碼時， 假設(shè)接收信噪比等于 7dB，編碼前誤碼率 約為810-4，圖中A 點(diǎn)，在采用糾錯編碼 后，誤碼率降至約4 10-5，圖中B點(diǎn)。這樣， 不增大發(fā)送功率 就能 降低誤碼率約一個半 數(shù)量級。10-610-510-410-310-210-1編碼后Pe

CDE

A

B信噪比(dB)24整理ppt第11章過失控制編碼由圖還可以看出，假設(shè) 保持誤碼率在10-5， 圖中C點(diǎn)，未采用編 碼時，約需要信噪比 Eb/n0=10.5dB。在 采用這種編碼時，約 需要信噪比7.5dB，圖 中D點(diǎn)?？梢怨?jié)省功率 2dB。通常稱這2dB為 編碼增益。上面兩種情況付出的代 價是帶寬增大。10-610-510-410-310-210-1編碼后Pe

CDE

A

B信噪比(dB)25整理ppt第11章過失控制編碼傳輸速率和Eb/n0的關(guān)系 對于給定的傳輸系統(tǒng) 式中，RB為碼元速率。 假設(shè)希望提高傳輸速率， 由上式看出勢必使信 噪比下降，誤碼率增 大。假設(shè)系統(tǒng)原來工作 在圖中C點(diǎn)，提高速率后 由C點(diǎn)升到E點(diǎn)。但加用 糾錯編碼后，仍可將誤碼 率降到D點(diǎn)。這時付出的 代價仍是帶寬增大。10-610-510-410-310-210-1編碼后Pe

CDE

A

B信噪比(dB)26整理ppt第11章過失控制編碼11.4簡單的實用編碼11.4.1奇偶監(jiān)督碼奇偶監(jiān)督碼分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼兩種，兩者的原理相同。在偶數(shù)監(jiān)督碼中，無論信息位多少，監(jiān)督位只有1位，它使碼組中“1〞的數(shù)目為偶數(shù)，即滿足下式條件： 式中a0為監(jiān)督位，其他位為信息位。 這種編碼能夠檢測奇數(shù)個錯碼。在接收端，按照上式求“模2和〞，假設(shè)計算結(jié)果為“1〞就說明存在錯碼，結(jié)果為“0〞就認(rèn)為無錯碼。 奇數(shù)監(jiān)督碼與偶數(shù)監(jiān)督碼相似，只不過其碼組中“1〞的數(shù)目為奇數(shù)：27整理ppt第11章過失控制編碼11.4.2二維奇偶監(jiān)督碼〔方陣碼〕二維奇偶監(jiān)督碼的構(gòu)成 它是先把上述奇偶監(jiān)督碼的假設(shè)干碼組排成矩陣，每一碼組寫成一行，然后再按列的方向增加第二維監(jiān)督位，如以下圖所示 圖中a01a02a0m為m行奇偶監(jiān)督碼中的m個監(jiān)督位。 cn-1cn-2c1c0為按列進(jìn)行第二次編碼所增加的監(jiān)督位，它們構(gòu)成了一監(jiān)督位行。28整理ppt第11章過失控制編碼二維奇偶監(jiān)督碼的性能這種編碼有可能檢測偶數(shù)個錯碼。因為每行的監(jiān)督位雖然不能用于檢測本行中的偶數(shù)個錯碼，但按列的方向有可能由cn-1

cn-2

c1

c0等監(jiān)督位檢測出來。有一些偶數(shù)錯碼不可能檢測出來。例如，構(gòu)成矩形的4個錯碼，譬如圖中 錯了，就檢測不出。這種二維奇偶監(jiān)督碼適于檢測突發(fā)錯碼。因為突發(fā)錯碼常常成串出現(xiàn)，隨后有較長一段無錯區(qū)間。由于方陣碼只對構(gòu)成矩形四角的錯碼無法檢測，故其檢錯能力較強(qiáng)。二維奇偶監(jiān)督碼不僅可用來檢錯，還可以用來糾正一些錯碼。例如，僅在一行中有奇數(shù)個錯碼時。29整理ppt第11章過失控制編碼11.4.3恒比碼在恒比碼中，每個碼組均含有相同數(shù)目的“1〞〔和“0〞〕。由于“1〞的數(shù)目與“0〞的數(shù)目之比保持恒定，故得此名。這種碼在檢測時，只要計算接收碼組中“1〞的數(shù)目是否對，就知道有無錯碼。恒比碼的主要優(yōu)點(diǎn)是簡單和適于用來傳輸電傳機(jī)或其他鍵盤設(shè)備產(chǎn)生的字母和符號。對于信源來的二進(jìn)制隨機(jī)數(shù)字序列，這種碼就不適合使用了。30整理ppt第11章過失控制編碼11.4.4正反碼正反碼的編碼：它是一種簡單的能夠糾正錯碼的編碼。其中的監(jiān)督位數(shù)目與信息位數(shù)目相同，監(jiān)督碼元與信息碼元相同或者相反那么由信息碼中“1〞的個數(shù)而定。例如，假設(shè)碼長n=10，其中信息位k=5，監(jiān)督位r=5。其編碼規(guī)那么為：當(dāng)信息位中有奇數(shù)個“1〞時，監(jiān)督位是信息位的簡單重復(fù)；當(dāng)信息位有偶數(shù)個“1〞時，監(jiān)督位是信息位的反碼。例如，假設(shè)信息位為11001，那么碼組為1100111001；假設(shè)信息位為10001，那么碼組為1000101110。31整理ppt第11章過失控制編碼正反碼的解碼在上例中，先將接收碼組中信息位和監(jiān)督位按模2相加，得到一個5位的合成碼組。然后，由此合成碼組產(chǎn)生一個校驗碼組。假設(shè)接收碼組的信息位中有奇數(shù)個“1〞，那么合成碼組就是校驗碼組；假設(shè)接收碼組的信息位中有偶數(shù)個“1〞，那么取合成碼組的反碼作為校驗碼組。最后，觀察校驗碼組中“1〞的個數(shù)，按下表進(jìn)行判決及糾正可能發(fā)現(xiàn)的錯碼。32整理ppt第11章過失控制編碼校驗碼組和錯碼的關(guān)系

例如，假設(shè)發(fā)送碼組為1100111001，接收碼組中無錯碼，那么合成碼組應(yīng)為1100111001=00000。由于接收碼組信息位中有奇數(shù)個“1〞，所以校驗碼組就是00000。按上表判決，結(jié)論是無錯碼。校驗碼組的組成錯碼情況1全為“0”無錯碼2有4個“1”和1個“0”信息碼中有1位錯碼，其位置對應(yīng)校驗碼組中“0”的位置3有4個“0”和1個“1”監(jiān)督碼中有1位錯碼，其位置對應(yīng)校驗碼組中“1”的位置4其他組成錯碼多于1個33整理ppt第11章過失控制編碼 假設(shè)傳輸中產(chǎn)生了過失，使接收碼組變成1000111001，那么合成碼組為1000111001＝01000。由于接收碼組中信息位有偶數(shù)個“1〞，所以校驗碼組應(yīng)取合成碼組的反碼，即10111。由于其中有4個“1〞和1個“0〞，按上表判斷信息位中左邊第2位為錯碼。 假設(shè)接收碼組錯成1100101001，那么合成碼組變成1100101001＝10000。由于接收碼組中信息位有奇數(shù)個“1〞，故校驗碼組就是10000，按上表判斷，監(jiān)督位中第1位為錯碼。 最后，假設(shè)接收碼組為1001111001，那么合成碼組為1001111001＝01010，校驗碼組與其相同，按上表判斷，這時錯碼多于1個。上述長度為10的正反碼具有糾正1位錯碼的能力，并能檢測全部2位以下的錯碼和大局部2位以上的錯碼。34整理ppt第11章過失控制編碼11.5線性分組碼根本概念代數(shù)碼：建立在代數(shù)學(xué)根底上的編碼。線性碼：按照一組線性方程構(gòu)成的代數(shù)碼。在線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的。線性分組碼：按照一組線性方程構(gòu)成的分組碼。本節(jié)將以漢明碼為例引入線性分組碼的一般原理。35整理ppt第11章過失控制編碼漢明碼～能夠糾正1位錯碼且編碼效率較高的一種線性分組碼漢明碼的構(gòu)造原理。在偶數(shù)監(jiān)督碼中，由于使用了一位監(jiān)督位a0，它和信息位an-1…a1一起構(gòu)成一個代數(shù)式： 在接收端解碼時，實際上就是在計算 假設(shè)S=0，就認(rèn)為無錯碼；假設(shè)S=1，就認(rèn)為有錯碼?，F(xiàn)將上式稱為監(jiān)督關(guān)系式，S稱為校正子。由于校正子S只有兩種取值，故它只能代表有錯和無錯這兩種信息，而不能指出錯碼的位置。36整理ppt第11章過失控制編碼假設(shè)監(jiān)督位增加一位，即變成兩位，那么能增加一個類似的監(jiān)督關(guān)系式。由于兩個校正子的可能值有4中組合：00，01，10，11，故能表示4種不同的信息。假設(shè)用其中1種組合表示無錯，那么其余3種組合就有可能用來指示一個錯碼的3種不同位置。同理，r個監(jiān)督關(guān)系式能指示1位錯碼的(2r–1)個可能位置。一般來說，假設(shè)碼長為n，信息位數(shù)為k，那么監(jiān)督位數(shù)r＝n－k。如果希望用r個監(jiān)督位構(gòu)造出r個監(jiān)督關(guān)系式來指示1位錯碼的n種可能位置，那么要求 下面通過一個例子來說明如何具體構(gòu)造這些監(jiān)督關(guān)系式。37整理ppt糾錯碼——海明碼

如果傳輸?shù)臄?shù)據(jù)位是m位，加了r位冗余位，那么總共傳輸?shù)臄?shù)據(jù)單元是m+r位。為了能夠發(fā)現(xiàn)這m+r位數(shù)據(jù)單元在傳輸?shù)侥康亩撕笫欠癯鲥e，并能夠指明是在哪一位出錯，那么r至少應(yīng)該能夠代表m+r+1種狀態(tài)。r比特能夠代表2r不同狀態(tài)。因此，2r>=m+r+1假設(shè)m=7，那么滿足上式的最小r值為：4。38整理ppt海明校驗碼(校驗位置)校驗位和數(shù)據(jù)位是如何排列的校驗位排列在2i(i=0,1,2,…)的位置上例：有一個BCD碼為D4D3D2D1,由此生成一個海明碼

7654321D4D3D2P3D1P2P1

22

2120

有一字節(jié)的信息需生成海明碼

D8D7D6D5P4D4D3D2P3D1P2P1

842139整理ppt校驗位取值公式及計算舉例海明碼的校驗位Pi和數(shù)值位Di的關(guān)系例：BCD碼為1011P3=D4⊕D3⊕D2

0=

1⊕0⊕1P2=D4⊕D3⊕D1

0=

1⊕0⊕1P1=D4⊕D2⊕D1

1=

1⊕1⊕1

最后

海明碼為1010101765432122D4D3D2P321D4D3D1P220D4D2D1P140整理ppt1位糾錯海明碼的實現(xiàn)把m+r=n個數(shù)據(jù)=>HnHn-1...H2H1(海明碼〕,每個校驗位Pi在海明碼中被分配在2i-1位置上。舉例：m=8，r=4，那么海明碼為：H12H11H10H9H8H7H6H5H4H3H2H1P4,P3,P2,P1根據(jù)規(guī)那么，分別對應(yīng)于：H8,,H4,,H2,,H1這樣，P1=m1m2m4m5m7P2=m1m3m4m6m7P3=m2m3m4m8P4=m5m6m7m841整理ppt1位糾錯海明碼的實現(xiàn)(續(xù))P1=M1

M2

M4

M5

M7P2=M1

M3

M4

M6

M7P3=M2

M3

M4

M8P4=M5

M6

M7

M812111098765432120M7M5M4M2M1P121M7M6M4M3M1P222M8M4M3M2P323M8M7M6M5P442整理ppt海明碼的糾錯原理海明碼的接收端的公式:S3=P3⊕D4⊕D3⊕D2

S2=P2⊕D4⊕D3⊕D1

S1=P1⊕D4⊕D2⊕D1假定海明碼1010101在傳送中變成了1000101S3=P3⊕D4⊕D3⊕D2=0⊕1⊕0⊕0=1

S2=P2⊕D4⊕D3⊕D1=0⊕1⊕0⊕1=0S1=P1⊕D4⊕D2⊕D1=1⊕1⊕

0

⊕1=1

因此,由S3S2S1=101,指出第5位錯,應(yīng)由0變143整理ppt練習(xí)比照特序列10011101計算其海明碼1211109876543212001101P112100111P21221110P31231001P40最終形成的海明碼為：10010110111144整理ppt第11章過失控制編碼例：設(shè)分組碼(n,k)中k=4，為了糾正1位錯碼，由上式可知，要求監(jiān)督位數(shù)r3。假設(shè)取r=3，那么n=k+r=7。我們用a6a5a0表示這7個碼元，用S1、S2和S3表示3個監(jiān)督關(guān)系式中的校正子，那么S1、S2和S3的值與錯碼位置的對應(yīng)關(guān)系可以規(guī)定如下表所列：S1S2

S3錯碼位置S1S2

S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯碼45整理ppt第11章過失控制編碼 由表中規(guī)定可見，僅當(dāng)一位錯碼的位置在a2、a4、a5或a6時，校正子S1為1；否那么S1為零。這就意味著a2、a4、a5和a6四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系： 同理，a1、a3、a5和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系： 以及a0、a3、a4和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系46整理ppt第11章過失控制編碼在發(fā)送端編碼時，信息位a6、a5、a4和a3的值決定于輸入信號，因此它們是隨機(jī)的。監(jiān)督位a2、a1和a0應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定，即監(jiān)督位應(yīng)使上3式中S1、S2和S3的值為0〔表示編成的碼組中應(yīng)無錯碼〕： 上式經(jīng)過移項運(yùn)算，解出監(jiān)督位 給定信息位后，可以直接按上式算出監(jiān)督位，結(jié)果見下表：47整理ppt第11章過失控制編碼信息位a6a5a4a3監(jiān)督位a2a1a0信息位a6a5a4a3監(jiān)督位a2a1a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111148整理ppt第11章過失控制編碼接收端收到每個碼組后，先計算出S1、S2和S3，再查表判斷錯碼情況。例如，假設(shè)接收碼組為0000011，按上述公式計算可得：S1=0，S2=1，S3=1。由于S1S2S3等于011，故查表可知在a3位有1錯碼。按照上述方法構(gòu)造的碼稱為漢明碼。表中所列的(7,4)漢明碼的最小碼距d0=3。因此，這種碼能夠糾正1個錯碼或檢測2個錯碼。由于碼率k/n=(n-r)/n=1–r/n，故當(dāng)n很大和r很小時，碼率接近1?？梢姡瑵h明碼是一種高效碼。49整理ppt第11章過失控制編碼線性分組碼的一般原理線性分組碼的構(gòu)造H矩陣 上面(7,4)漢明碼的例子有 現(xiàn)在將上面它改寫為 上式中已經(jīng)將“〞簡寫成“+〞。

50整理ppt第11章過失控制編碼上式可以表示成如下矩陣形式：上式還可以簡記為

H

AT=0T

或A

HT=0

51整理ppt第11章過失控制編碼 HAT=0T或AHT=0 式中 A=[a6a5a4a3a2a1a0] 0=[000] 右上標(biāo)“T〞表示將矩陣轉(zhuǎn)置。例如，HT是H的轉(zhuǎn)置，即HT的第一行為H的第一列，HT的第二行為H的第二列等等。 將H稱為監(jiān)督矩陣。 只要監(jiān)督矩陣H給定，編碼時監(jiān)督位和信息位的關(guān)系就完全確定了。52整理ppt第11章過失控制編碼H矩陣的性質(zhì)： 1)H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，它等于監(jiān)督位的數(shù)目r。H的每行中“1〞的位置表示相應(yīng)碼元之間存在的監(jiān)督關(guān)系。例如，H的第一行1110100表示監(jiān)督位a2是由a6a5a4之和決定的。H矩陣可以分成兩局部，例如 式中，P為rk階矩陣，Ir為rr階單位方陣。我們將具有[PIr]形式的H矩陣稱為典型陣。53整理ppt第11章過失控制編碼 2)由代數(shù)理論可知，H矩陣的各行應(yīng)該是線性無關(guān)的，否那么將得不到r個線性無關(guān)的監(jiān)督關(guān)系式，從而也得不到r個獨(dú)立的監(jiān)督位。假設(shè)一矩陣能寫成典型陣形式[PIr]，那么其各行一定是線性無關(guān)的。因為容易驗證[Ir]的各行是線性無關(guān)的，故[PIr]的各行也是線性無關(guān)的。G矩陣： 上面漢明碼例子中的監(jiān)督位公式為

也可以改寫成矩陣形式：54整理ppt第11章過失控制編碼

或者寫成 式中，Q為一個k

r階矩陣，它為P的轉(zhuǎn)置，即Q=PT

上式表示，在信息位給定后，用信息位的行矩陣乘矩陣Q就產(chǎn)生出監(jiān)督位。55整理ppt第11章過失控制編碼我們將Q的左邊加上1個kk階單位方陣，就構(gòu)成1個矩陣G G稱為生成矩陣，因為由它可以產(chǎn)生整個碼組，即有 或者 因此，如果找到了碼的生成矩陣G，那么編碼的方法就完全確定了。具有[IkQ]形式的生成矩陣稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼稱為系統(tǒng)碼。56整理ppt第11章過失控制編碼G矩陣的性質(zhì)： 1)G矩陣的各行是線性無關(guān)的。因為由上式可以看出，任一碼組A都是G的各行的線性組合。G共有k行，假設(shè)它們線性無關(guān)，那么可以組合出2k種不同的碼組A，它恰是有k位信息位的全部碼組。假設(shè)G的各行有線性相關(guān)的，那么不可能由G生成2k種不同的碼組了。 2)實際上，G的各行本身就是一個碼組。因此，如果已有k個線性無關(guān)的碼組，那么可以用其作為生成矩陣G，并由它生成其余碼組。57整理ppt第11章過失控制編碼錯碼矩陣和錯誤圖樣一般說來，A為一個n列的行矩陣。此矩陣的n個元素就是碼組中的n個碼元，所以發(fā)送的碼組就是A。此碼組在傳輸中可能由于干擾引入過失，故接收碼組一般說來與A不一定相同。假設(shè)設(shè)接收碼組為一n列的行矩陣B，即 那么發(fā)送碼組和接收碼組之差為 B–A=E(模2) 它就是傳輸中產(chǎn)生的錯碼行矩陣 式中58整理ppt第11章過失控制編碼 因此，假設(shè)ei=0，表示該接收碼元無錯；假設(shè)ei=1，那么表示該接收碼元有錯。 B–A=E可以改寫成B=A+E 例如，假設(shè)發(fā)送碼組A=[1000111]，錯碼矩陣E=[0000100]，那么接收碼組B=[1000011]。 錯碼矩陣有時也稱為錯誤圖樣。59整理ppt第11章過失控制編碼校正子S 當(dāng)接收碼組有錯時，E0，將B當(dāng)作A代入公式(AHT=0)后，該式不一定成立。在錯碼較多，已超過這種編碼的檢錯能力時，B變?yōu)榱硪辉S用碼組，那么該式仍能成立。這樣的錯碼是不可檢測的。在未超過檢錯能力時，上式不成立，即其右端不等于0。假設(shè)這時該式的右端為S，即 BHT=S 將B=A+E代入上式，可得 S=(A+E)HT=AHT+EHT 由于AHT=0，所以 S=EHT 式中S稱為校正子。它能用來指示錯碼的位置。 S和錯碼E之間有確定的線性變換關(guān)系。假設(shè)S和E之間一一對應(yīng)，那么S將能代表錯碼的位置。60整理ppt第11章過失控制編碼線性分組碼的性質(zhì)封閉性：是指一種線性碼中的任意兩個碼組之和仍為這種碼中的一個碼組。 這就是說，假設(shè)A1和A2是一種線性碼中的兩個許用碼組，那么(A1+A2)仍為其中的一個碼組。這一性質(zhì)的證明很簡單。假設(shè)A1和A2是兩個碼組，那么有 A1HT=0, A2HT=0 將上兩式相加，得出 A1HT+A2HT=(A1+A2)HT=0 所以(A1+A2)也是一個碼組。 由于線性碼具有封閉性，所以兩個碼組(A1和A2)之間的距離〔即對應(yīng)位不同的數(shù)目〕必定是另一個碼組(A1+A2)的重量〔即“1〞的數(shù)目〕。因此，碼的最小距離就是碼的最小重量〔除全“0〞碼組外〕。61整理ppt第11章過失控制編碼11.6循環(huán)碼11.6.1循環(huán)碼原理循環(huán)性：循環(huán)性是指任一碼組循環(huán)一位〔即將最右端的一個碼元移至左端，或反之〕以后，仍為該碼中的一個碼組。在下表中給出一種(7,3)循環(huán)碼的全部碼組。 例如，表中的第2碼組向右移一位即得到第5碼組；第6碼組向右移一位即得到第7碼組。碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001062整理ppt第11章過失控制編碼 一般說來，假設(shè)(an-1an-2…a0)是循環(huán)碼的一個碼組，那么循環(huán)移位后的碼組 (an-2an-3…a0an-1) (an-3an-4…an-1an-2) ……… (a0an-1…a2a1) 也是該編碼中的碼組。63整理ppt第11章過失控制編碼碼多項式碼組的多項式表示法 把碼組中各碼元當(dāng)作是一個多項式的系數(shù)，即把一個長度為n的碼組表示成 例如，上表中的任意一個碼組可以表示為 其中第7個碼組可以表示為 這種多項式中，x僅是碼元位置的標(biāo)記，例如上式表示第7碼組中a6、a5、a2和a0為“1〞，其他均為0。因此我們并不關(guān)心x的取值。64整理ppt第11章過失控制編碼碼多項式的按模運(yùn)算在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模2運(yùn)算中，有 1+1=20(模2)， 1+2=31(模2)， 23=60(模2) 等等。一般說來，假設(shè)一個整數(shù)m可以表示為 式中，Q－整數(shù)， 那么在模n運(yùn)算下，有 mp(模n) 即，在模n運(yùn)算下，一個整數(shù)m等于它被n除得的余數(shù)。65整理ppt第11章過失控制編碼在碼多項式運(yùn)算中也有類似的按模運(yùn)算。 假設(shè)一任意多項式F(x)被一n次多項式N(x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)，即 那么寫為 這時，碼多項式系數(shù)仍按模2運(yùn)算，即系數(shù)只取0和1。例如，x3被(x3+1)除，得到余項1。所以有 同理 因為

xx3+1x4+x2+1

x4

+x

x2+x+1應(yīng)當(dāng)注意，由于在模2運(yùn)算中，用加法代替了減法，故余項不是x2

–

x+1，而是x2+x+1。66整理ppt第11章過失控制編碼循環(huán)碼的碼多項式在循環(huán)碼中，假設(shè)T(x)是一個長為n的許用碼組，那么xiT(x)在按模xn+1運(yùn)算下，也是該編碼中的一個許用碼組，即假設(shè) 那么T(x)也是該編碼中的一個許用碼組。 【證】因為假設(shè) 那么 〔模(xn+1)〕 所以，這時有67整理ppt第11章過失控制編碼 上式中T(x)正是T(x)代表的碼組向左循環(huán)移位i次的結(jié)果。因為原已假定T(x)是循環(huán)碼的一個碼組，所以T(x)也必為該碼中一個碼組。例如，循環(huán)碼組 其碼長n=7?，F(xiàn)給定i=3，那么 其對應(yīng)的碼組為0101110，它正是表中第3碼組。 由上述分析可見，一個長為n的循環(huán)碼必定為按模(xn+1)運(yùn)算的一個余式。68整理ppt第11章過失控制編碼循環(huán)碼的生成矩陣G由上節(jié)中公式 可知，有了生成矩陣G，就可以由k個信息位得出整個碼組，而且生成矩陣G的每一行都是一個碼組。例如，在此式中，假設(shè)a6a5a4a3=1000，那么碼組A就等于G的第一行；假設(shè)a6a5a4a3=0100，那么碼組A就等于G的第二行；等等。由于G是k行n列的矩陣，因此假設(shè)能找到k個碼組，就能構(gòu)成矩陣G。如前所述，這k個碼組必須是線性不相關(guān)的，否那么給定的信息位與編出的碼組就不是一一對應(yīng)的。在循環(huán)碼中，一個(n,k)碼有2k個不同的碼組。假設(shè)用g(x)表示其中前(k-1)位皆為“0〞的碼組，那么g(x)，xg(x)，x2g(x)，，xk-1g(x)都是碼組，而且這k個碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。69整理ppt第11章過失控制編碼在循環(huán)碼中除全“0〞碼組外，再沒有連續(xù)k位均為“0〞的碼組，即連“0〞的長度最多只能有(k-1)位。否那么，在經(jīng)過假設(shè)干次循環(huán)移位后將得到一個k位信息位全為“0〞，但監(jiān)督位不全為“0〞的一個碼組。這在線性碼中顯然是不可能的。因此，g(x)必須是一個常數(shù)項不為“0〞的(n-k)次多項式，而且這個g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一多項式。因為如果有兩個，那么由碼的封閉性，把這兩個相加也應(yīng)該是一個碼組，且此碼組多項式的次數(shù)將小于(n–k)，即連續(xù)“0〞的個數(shù)多于(k–1)。顯然，這是與前面的結(jié)論矛盾的，故是不可能的。我們稱這唯一的(n–k)次多項式g(x)為碼的生成多項式。一旦確定了g(x)，那么整個(n,k)循環(huán)碼就被確定了。70整理ppt第11章過失控制編碼因此，循環(huán)碼的生成矩陣G可以寫成例：在上表所給出的(7,3)循環(huán)碼中，n=7,k=3,n–k=4。由此表可見，唯一的一個(n–k)=4次碼多項式代表的碼組是第二碼組0010111，與它相對應(yīng)的碼多項式〔即生成多項式〕g(x)=x4+x2+x+1。將此g(x)代入上式，得到 或71整理ppt第11章過失控制編碼 由于上式不符合G=[IkQ]的形式，所以它不是典型陣。不過，將它作線性變換，不難化成典型陣。 我們可以寫出此循環(huán)碼組，即 上式說明，所有碼多項式T(x)都可被g(x)整除，而且任意一個次數(shù)不大于(k–1)的多項式乘g(x)都是碼多項式。需要說明一點(diǎn)，兩個矩陣相乘的結(jié)果應(yīng)該仍是一個矩陣。上式中兩個矩陣相乘的乘積是只有一個元素的一階矩陣，這個元素就是T(x)。為了簡潔，式中直接將乘積寫為此元素。72整理ppt第11章過失控制編碼如何尋找任一(n,k)循環(huán)碼的生成多項式 由上式可知，任一循環(huán)碼多項式T(x)都是g(x)的倍式，故它可以寫成

T(x)=h(x)

g(x)

而生成多項式g(x)本身也是一個碼組，即有

T

(x)=g(x)

由于碼組T

(x)是一個(n–k)次多項式，故xkT

(x)是一個n次多項式。由下式 可知，xkT

(x)在模(xn+1)運(yùn)算下也是一個碼組，故可以寫成73整理ppt第11章過失控制編碼

上式左端分子和分母都是n次多項式，故商式Q(x)=1。因此，上式可以化成 將T(x)和T(x)表示式代入上式，經(jīng)過化簡后得到 上式說明，生成多項式g(x)應(yīng)該是(xn+1)的一個因子。這一結(jié)論為我們尋找循環(huán)碼的生成多項式指出了一條道路，即循環(huán)碼的生成多項式應(yīng)該是(xn+1)的一個(n–k)次因式。例如，(x7+1)可以分解為 為了求(7,3)循環(huán)碼的生成多項式g(x)，需要從上式中找到一個(n–k)=4次的因子。不難看出，這樣的因子有兩個，即74整理ppt第11章過失控制編碼

以上兩式都可作為生成多項式。不過，選用的生成多項式不同，產(chǎn)生出的循環(huán)碼碼組也不同。75整理ppt第11章過失控制編碼11.6.2循環(huán)碼的編解碼方法循環(huán)碼的編碼方法編碼原那么 在編碼時，首先要根據(jù)給定的(n,k)值選定生成多項式g(x)，即從(xn+1)的因子中選一個(n-k)次多項式作為g(x)。 由于所有碼多項式T(x)都可以被g(x)整除。根據(jù)這條原那么，就可以對給定的信息位進(jìn)行編碼： 設(shè)m(x)為信息碼多項式，其次數(shù)小于k。用xn-k乘m(x)，得到的xn-km(x)的次數(shù)必定小于n。用g(x)除xn-km(x)，得到余式r(x)，r(x)的次數(shù)必定小于g(x)的次數(shù)，即小于(n–k)。將此余式r(x)加于信息位之后作為監(jiān)督位，即將r(x)和xn-km(x)相加，得到的多項式必定是一個碼多項式。因為它必須能被g(x)整除，且商的次數(shù)不大于(k–1)。76整理ppt第11章過失控制編碼編碼步驟：用xn-k乘m(x)。這一運(yùn)算實際上是在信息碼后附加上(n–k)個“0〞。例如，信息碼為110，它相當(dāng)于m(x)=x2+x。當(dāng)n–k=7–3=4時，xn-km(x)=x4(x2+x)=x6+x5，它相當(dāng)于1100000。用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即 例如，假設(shè)選定g(x)=x4+x2+x+1，那么 上式相當(dāng)于77整理ppt第11章過失控制編碼編出的碼組T(x)為

T(x)=xn-km(x)+r(x)

在上例中，T(x)=1100000+101=1100101，它就是上表中的第7碼組。78整理ppt第11章過失控制編碼循環(huán)碼的解碼方法解碼要求：檢錯和糾錯。檢錯解碼原理：由于任意一個碼組多項式T(x)都應(yīng)該能被生成多項式g(x)整除，所以在接收端可以將接收碼組R(x)用原生成多項式g(x)去除。當(dāng)傳輸中未發(fā)生錯誤時，接收碼組與發(fā)送碼組相同，即R(x)=T(x)，故接收碼組R(x)必定能被g(x)整除；假設(shè)碼組在傳輸中發(fā)生錯誤，那么R(x)T(x)，R(x)被g(x)除時可能除不盡而有余項，即有 因此，就以余項是否為零來判別接收碼組中有無錯碼。 需要指出，有錯碼的接收碼組也有可能被g(x)整除。這時的錯碼就不能檢出了。這種錯誤稱為不可檢錯誤。不可檢錯誤中的誤碼數(shù)必定超過了這種編碼的檢錯能力。79整理ppt第11章過失控制編碼糾錯解碼原理：為了能夠糾錯，要求每個可糾正的錯誤圖樣必須與一個特定余式有一一對應(yīng)關(guān)系。因為只有存在上述一一對應(yīng)的關(guān)系時，才可能從上述余式唯一地決定錯誤圖樣，從而糾正錯碼。因此，原那么上糾錯可按下述步驟進(jìn)行：用生成多項式g(x)除接收碼組R(x)，得出余式r(x)。按余式r(x)，用查表的方法或通過某種計算得到錯誤圖樣E(x)；例如，通過計算校正子S和查表，就可以確定錯碼的位置。從R(x)中減去E(x)，便得到已經(jīng)糾正錯碼的原發(fā)送碼組T(x)。通常，一種編碼可以有幾種糾錯解碼方法，上述解碼方法稱為捕錯解碼法。目前多采用軟件運(yùn)算實現(xiàn)上述編解碼運(yùn)算。80整理ppt第11章過失控制編碼11.6.3截短循環(huán)碼截短目的：在設(shè)計糾錯編碼方案時，常常信息位數(shù)k、碼長n和糾錯能力都是預(yù)先給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。這時，可以采用將碼長截短的方法，得出滿足要求的編碼。截短方法：設(shè)給定一個(n,k)循環(huán)碼，它共有2k種碼組，現(xiàn)使其前i(0<i<k)個信息位全為“0〞，于是它變成僅有2k-i種碼組。然后從中刪去這i位全“0〞的信息位，最終得到一個(n–i,k–i)的線性碼。將這種碼稱為截短循環(huán)碼。截短循環(huán)碼性能：循環(huán)碼截短前后至少具有相同的糾錯能力，并且編解碼方法仍和截短前的方法一樣。例：要求構(gòu)造一個能夠糾正1位錯碼的(13,9)碼。這時可以由(15,11)循環(huán)碼的11種碼組中選出前兩信息位均為“0〞的碼組，構(gòu)成一個新的碼組集合。然后在發(fā)送時不發(fā)送這兩位“0〞。于是發(fā)送碼組成為(13,9)截短循環(huán)碼。81整理ppt第11章過失控制編碼11.6.4BCH碼什么是BCH碼？它是一種獲得廣泛應(yīng)用的能夠糾正多個錯碼的循環(huán)碼，是以3位創(chuàng)造這種碼的人名(Bose-Chaudhuri-Hocguenghem)命名的。BCH碼的重要性在于它解決了生成多項式與糾錯能力的關(guān)系問題，可以在給定糾錯能力要求的條件下尋找到碼的生成多項式。有了生成多項式，編碼的根本問題就隨之解決了。BCH碼分類：本原BCH碼：其生成多項式g(x)中含有最高次數(shù)為m的本原多項式，且碼長為n=2m–1，(m3，為正整數(shù))。非本原BCH碼：其生成多項式中不含這種本原多項式，且碼長n是(2m–1)的一個因子，即碼長n一定除得盡2m–1。本原多項式的概念將在下一章介紹。82整理ppt第11章過失控制編碼BCH碼的性能：碼長n與監(jiān)督位、糾錯個數(shù)t之間的關(guān)系： 對于正整數(shù)m(m3)和正整數(shù)t<m/2，必定存在一個碼長為n=2m–1，監(jiān)督位為n–kmt，能糾正所有不多于t個隨機(jī)錯誤的BCH碼。假設(shè)碼長n=(2m-1)/i〔i>1，且除得盡(2m-1)〕，那么為非本原BCH碼。漢明碼是能夠糾正單個隨機(jī)錯誤的碼?？梢宰C明，具有循環(huán)性質(zhì)的漢明碼就是能糾正單個隨機(jī)錯誤的本原BCH碼。例如，(7,4)漢明碼就是以g1(x)=x3+x+1或g2(x)=x3+x2+1生成的BCH碼，而用g3(x)=x4+x+1或g4(x)=x4+x3+1都能生成(15,11)漢明碼。83整理ppt第11章過失控制編碼BCH碼的設(shè)計在工程設(shè)計中，一般不需要用計算方法去尋找生成多項式g(x)。因為前人早已將尋找到的g(x)列成表，故可以用查表法找到所需的生成多項式。下表給出了碼長n

127的二進(jìn)制本原BCH碼生成多項式。84整理ppt第11章過失控制編碼n=3k

t

g(x)117n=63k

t

g(x)571103512124714531701317394166623567365103350042330615746416534724717323260404441181013630265123517251611633114136723545310134726223055272501557155231045543503271737131全部為1n=7k

t

g(x)41131377n=15k

t

g(x)1112372721532467177777785整理ppt第11章過失控制編碼n=31kt

g(x)26145212355116310765711554233256731336504711517777777777n=127k

t

g(x)1201211113241567106311554743994344702327192562473002232785613070447632227378726230002166130115719625501071325312775364101206534025570773100045571123526525250570505351772150135444651252331401242150142143151772177221365122752122057434336

153146074666522075044764574721735292240311446136767060366753014117615522231233760704047225224354456266376470431527220570424456045547705230137622176043538317047264052751030651476224271567733130217163全部為186整理ppt第11章過失控制編碼表中給出的生成多項式系數(shù)是用8進(jìn)制數(shù)字列出的。例如，g(x)=(13)8是指g(x)=x3+x+1，因為(13)8=(1011)2，后者就是此3次方程g(x)的各項系數(shù)。下表列出了局部非本原BCH碼的生成多項式參數(shù)。nktg(x)nktg(x)1721233341912122221223247271663534351456647133476565732453404652444307335710761354300067171777353787整理ppt第11章過失控制編碼戈萊碼： 在上表中的(23,12)碼稱為戈萊(Golay)碼。它能糾正3個隨機(jī)錯碼，并且容易解碼，實際應(yīng)用較多。擴(kuò)展BCH碼：

BCH碼的長度都為奇數(shù)。在應(yīng)用中，為了得到偶數(shù)長度的碼，并增大檢錯能力，可以在BCH碼生成多項式中乘上一個因式(x+1)，從而得到擴(kuò)展BCH碼(n+1,k)。擴(kuò)展BCH碼相當(dāng)于在原BCH碼上增加了一個校驗位，因此碼距比原BCH碼增加1。擴(kuò)展BCH碼已經(jīng)不再具有循環(huán)性。例如，廣泛實用的擴(kuò)展戈萊碼(24,12)，其最小碼距為8，碼率為1/2，能夠糾正3個錯碼和檢測4個錯碼。它比漢明碼的糾錯能力強(qiáng)很多，付出的代價是解碼更復(fù)雜，碼率也比漢明碼低。此外，它不再是循環(huán)碼了。88整理ppt第11章過失控制編碼11.6.5RS碼：它是一類具有很強(qiáng)糾錯能力的多進(jìn)制BCH碼。假設(shè)仍用n表示RS碼的碼長，那么對于m進(jìn)制的RS碼，其碼長需要滿足下式： n=m–1=2q–1 式中q2，為整數(shù)。對于能夠糾正t個錯誤的RS碼，其監(jiān)督碼元數(shù)目為r=2t，這時的最小碼距d0=2t+1。RS碼的生成多項式為 g(x)=(x+)(x+2)…(x+2t) 式中，－伽羅華域GF(2q)中的本原元。假設(shè)將每個m進(jìn)制碼元表示成相應(yīng)的q位二進(jìn)制碼元，那么得到的二進(jìn)制碼的參數(shù)為： 碼長：n=q(2q–1)〔二進(jìn)制碼元〕 監(jiān)督碼：r=2qt 〔二進(jìn)制碼元〕89整理ppt第11章過失控制編碼由于RS碼能夠糾正t個m進(jìn)制錯碼，或者說，能夠糾正碼組中t個不超過q位連續(xù)的二進(jìn)制錯碼，所以RS碼特別適用于存在突發(fā)錯誤的信道，例如移動通信網(wǎng)等衰落信道中。此外，因為它是多進(jìn)制糾錯編碼，所以特別適合用于多進(jìn)制調(diào)制的場合。90整理ppt第11章過失控制編碼11.7卷積碼非分組碼概念：卷積碼是一種非分組碼。通常它更適用于前向糾錯，因為對于許多實際情況它的性能優(yōu)于分組碼，而且運(yùn)算較簡單。卷積碼在編碼時雖然也是把k個比特的信息段編成n個比特的碼組，但是監(jiān)督碼元不僅和當(dāng)前的k比特信息段有關(guān)，而且還同前面m=(N–1)個信息段有關(guān)。所以一個碼組中的監(jiān)督碼元監(jiān)督著N個信息段。通常將N稱為編碼約束度，并將nN稱為編碼約束長度。一般說來，對于卷積碼，k和n的值是比較小的整數(shù)。我們將卷積碼記作(n,k,N)。碼率那么仍定義為k/n。91整理ppt第11章過失控制編碼11.7.1卷積碼的根本原理編碼器原理方框圖編碼輸出每次輸入k比特1k…1k…1k…1k……

…

…

1…k…2k3kNk……

…

…

…

…

…

…

…

12nNk級移存器n個模2加法器每輸入k比特旋轉(zhuǎn)1周92整理ppt第11章過失控制編碼例：(n,k,N)=(3,1,3)卷積碼編碼器方框圖設(shè)輸入信息比特序列是bi-2bi-1bibi+1，那么當(dāng)輸入bi時，此編碼器輸出3比特cidiei，輸入和輸出的關(guān)系如下：bi-2bi輸入bibi-1編碼輸出dicieiM2M3M193整理pptci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi－1bitt輸入輸出第11章過失控制編碼 在以下圖中用虛線示出了信息位bi的監(jiān)督位和各信息位之間的約束關(guān)系。這里的編碼約束長度nN等于9。94整理ppt第11章過失控制編碼11.7.2卷積碼的代數(shù)表述 上式表示卷積碼也是一種線性碼。一個線性碼完全由一個監(jiān)督矩陣H或生成矩陣G所確定。下面就來尋找這兩個矩陣。監(jiān)督矩陣H 現(xiàn)在仍從上面的實例開始分析。假設(shè)上圖中在第1個信息位b1進(jìn)入編碼器之前，各級移存器都處于“0〞狀態(tài)，那么監(jiān)督位di、ei和信息位bi之間的關(guān)系可以寫為95整理ppt第11章過失控制編碼 左式可以改寫為在上面兩個式子和后面的式子中，為簡便計，用“＋〞代替“〞。將上式用矩陣表示時，可以寫成96整理ppt第11章過失控制編碼與11.5節(jié)公式HAT=0T比照，可以看出監(jiān)督矩陣為97整理ppt第11章過失控制編碼

由此例可見，卷積碼的監(jiān)督矩陣H是一個有頭無尾的半無窮矩陣。此外，這個矩陣的每3列的結(jié)構(gòu)是相同的，只是后3列比前3列向下移了兩行。例如，第4~6列比第1~3列低2行。自第7行起，每兩行的左端比上兩行多了3個“0〞。98整理ppt第11章過失控制編碼 雖然這樣的半無窮矩陣不便于研究，但是只要研究產(chǎn)生前9個碼元〔9為約束長度〕的監(jiān)督矩陣就足夠了。不難看出，這種截短監(jiān)督矩陣的結(jié)構(gòu)形式如以下圖所示： 由此圖可見，H1的最左邊是n列(n-k)N行的一個子矩陣，且向右的每n列均相對于前n列降低(n-k)行。H1=nn–k(n–k)N99整理ppt第11章過失控制編碼此例中碼的截短監(jiān)督矩陣可以寫成如下形式：式中

—2階單位方陣；

Pi —1

2階矩陣，i=1,2,3；

O2 —2階全零方陣。100整理ppt第11章過失控制編碼 一般說來，卷積碼的截短監(jiān)督矩陣具有如下形式： 式中In-k—(n–k)階單位方陣； Pi—k(n–k)階矩陣； On-k—(n–k)階全零方陣。 有時還將H1的末行稱為根本監(jiān)督矩陣h h=[PNOn-kPN-1On-kPN-2On-kP1In-k] 它是卷積碼的一個最重要的矩陣，因為只要給定了h，那么H1也就隨之決定了?；蛘哒f，我們從給定的h不難構(gòu)造出H1。101整理ppt第11章過失控制編碼生成矩陣G

上例中的輸出碼元序列可以寫成

[b1d1e1b2d2e2b3d3e3b4d4e4

]=

[b1b1b1b2b2(b2+b1)b3(b3+b1)(b3+b2+b1)b4(b4+b2)(b4+b3+b2)

]102整理ppt第11章過失控制編碼 此碼的生成矩陣G即為上式最右矩陣：

它也是一個半無窮矩陣，其特點(diǎn)是每一行的結(jié)構(gòu)相同，只是比上一行向右退后3列〔因現(xiàn)在n=3〕。103整理ppt第11章過失控制編碼截短生成矩陣：類似地，也有截短生成矩陣 式中 I1－一階單位方陣； Qi－21階矩陣。 與H1矩陣比較可見，Qi是矩陣PiT的轉(zhuǎn)置： Qi=PiT (i=1,2,) 一般說來，截短生成矩陣具有如下形式：104整理ppt第11章過失控制編碼 式中 Ik－k階單位方陣； Qi－(n–k)k階矩陣； Ok－k階全零方陣。 并將上式中矩陣第一行稱為根本生成矩陣 g＝[IkQ1OkQ2OkQ3OkQN] 同樣，如果根本生成矩陣g已經(jīng)給定，那么可以從的信息位得到整個編碼序列。105整理ppt第11章過失控制編碼11.7.3卷積碼的解碼分類：代數(shù)解碼：利用編碼本身的代數(shù)結(jié)構(gòu)進(jìn)行解碼，不考慮信道的統(tǒng)計特性。大數(shù)邏輯解碼，又稱門限解碼，是卷積碼代數(shù)解碼的最主要一種方法，它也可以應(yīng)用于循環(huán)碼的解碼。大數(shù)邏輯解碼對于約束長度較短的卷積碼最為有效，而且設(shè)備較簡單。概率解碼：又稱最大似然解碼。它基于信道的統(tǒng)計特性和卷積碼的特點(diǎn)進(jìn)行計算。針對無記憶信道提出的序貫解碼就是概率解碼方法之一。另一種概率解碼方法是維特比算法。當(dāng)碼的約束長度較短時，它比序貫解碼算法的效率更高、速度更快，目前得到廣泛的應(yīng)用。106整理ppt第11章過失控制編碼大數(shù)邏輯解碼工作原理圖中首先將接收信息位暫存于移存器中，并從接收碼元的信息位和監(jiān)督位計算校正子。然后，將計算得出的校正子暫存，并用它來檢測錯碼的位置。在信息位移存器輸出端，接有一個模2加電路；當(dāng)檢測到輸出的信息位有錯時，在輸出的信息位上加“1〞，從而糾正之。校正子計算信息位移存器校正子移存器錯碼檢測

輸入輸出修正校正子信息位監(jiān)督位107整理ppt第11章過失控制編碼這里的錯碼檢測是采用二進(jìn)制碼的大數(shù)邏輯解碼算法。它利用一組“正交〞校驗方程進(jìn)行計算。這里的“正交〞定義：假設(shè)被校驗的那個信息位出現(xiàn)在校驗方程組的每一個方程中，而其他的信息位至多在一個方程中出現(xiàn)，那么稱這組方程為正交校驗方程。這樣就可以根據(jù)被錯碼影響了的方程數(shù)目在方程組中是否占多數(shù)來判斷該信息位是否錯了。下面將用一個實例來具體講述這一過程。108整理ppt第11章過失控制編碼例：(2,1,6)卷積碼編碼器方框圖監(jiān)督位和信息位的關(guān)系 當(dāng)輸入序列為b1

b2

b3

b4

時，監(jiān)督位為

c1=b1

c2=b2

c3=b3

c4=b1+b4

c5=b1+b2+b5

c6=b1+b2+b3+b6

b6b5b4b3b2b1

bici

輸入輸出bici109整理ppt第11章過失控制編碼監(jiān)督關(guān)系式 參照11.5節(jié)中監(jiān)督關(guān)系的定義式，容易寫出

S1=c1+b1

S2=c2+b2

S3=c3+b3

S4=c4+b1+b4

S5=c5+b1+b2+b5

S6=c6+b1+b2+b3+b6

上式中的Si

(i=1~6)稱為校正子。正交校驗方程組 上式經(jīng)過簡單線性變換后，得出如下正交校驗方程組：110整理ppt第11章過失控制編碼 S1=c1+b1 S4=c4+b1+b4 S5=c5+b1+b2+b5 S2+S6=c2+c6+b1+b3+b6 在上式中，只有信息位b1出現(xiàn)在每個方程中，監(jiān)督位和其他信息位均最多只出現(xiàn)一次。因此，在接收端解碼時，考察b1、c1至b6、c6等12個碼元，僅當(dāng)b1出錯時，式中才可能有3個或3個以上方程等于“1〞。從而能夠糾正b1的錯誤。111整理ppt輸入輸出Yb6b5b4b3b2b1S6S5S4S3S2S1門限電路：“1”的個數(shù)

3？校正子Si校正子移存器信息位移存器重算監(jiān)督位ci接收監(jiān)督位計算校正子Si654321第11章過失控制編碼解碼器方框圖 按照這一原理畫出的此(2,1,6)卷積碼解碼器方框圖如下112整理ppt第11章過失控制編碼 由此圖可見，當(dāng)信息位出現(xiàn)一個錯碼時，僅當(dāng)它位于信息位移存器的第6、3、2和1級時，才使校正子等于“1〞。因此，這時的校正子序列為100111； 反之，當(dāng)監(jiān)督位出現(xiàn)一個錯碼時，校正子序列將為100000。 由此可見，當(dāng)校正子序列中出現(xiàn)第一個“1〞時，表示已經(jīng)檢出一個錯碼。后面的幾位校正子那么指出是信息位錯了，還是監(jiān)督位錯了。 圖中門限電路的輸入代表式中4個方程的4個電壓。門限電路將這4個電壓〔非模2〕相加。當(dāng)相加結(jié)果大于或等于3時，門限電路輸出“1〞，它除了送到輸出端的模2加法器上糾正輸出碼元b1的錯碼外，還送到校正子移存器糾正其中錯誤。此卷積碼除了能夠