第10章-信道編碼與差錯(cuò)控制

第10章---信道編碼與差錯(cuò)控制第一頁(yè)，共94頁(yè)。2學(xué)習(xí)要求1.理解差錯(cuò)控制的基本概念及其原理等；2.掌握信道編碼的基本原理；3.了解常用檢錯(cuò)碼的特性；4.掌握線性分組碼的一般特性；5.掌握漢明碼以及循環(huán)碼的編譯碼及其實(shí)現(xiàn)原理；6.了解卷積碼的基本概念。第二頁(yè)，共94頁(yè)。3差錯(cuò)控制與信道編碼概述糾錯(cuò)編碼的基本原理糾錯(cuò)編碼系統(tǒng)的性能奇偶監(jiān)督碼線性分組碼循環(huán)碼卷積碼Turbo碼和LDPC碼第三頁(yè)，共94頁(yè)。4為什么需要信道編碼？在數(shù)字信號(hào)的傳輸中，實(shí)際信道不是理想的，存在噪聲和干擾，會(huì)導(dǎo)致接收端的誤判，這樣就產(chǎn)生了差錯(cuò)。可采取的辦法：合理設(shè)計(jì)基帶信號(hào)選擇調(diào)制、解調(diào)方式采用均衡技術(shù)增大發(fā)送功率仍然達(dá)不到要求，就需要信道編碼概述第四頁(yè)，共94頁(yè)。信道編碼：目的：提高信號(hào)傳輸?shù)目煽啃浴７椒ǎ涸黾佣嘤啾忍?，以發(fā)現(xiàn)或糾正錯(cuò)誤。差錯(cuò)控制：包括信道編碼在內(nèi)的一切糾正錯(cuò)誤手段。產(chǎn)生錯(cuò)碼的原因：乘性干擾引起的碼間串?dāng)_加性干擾引起的信噪比降低信道分類：按照加性干擾造成錯(cuò)碼的統(tǒng)計(jì)特性不同劃分隨機(jī)信道：錯(cuò)碼隨機(jī)出現(xiàn)，例如由白噪聲引起的錯(cuò)碼突發(fā)信道：錯(cuò)碼相對(duì)集中出現(xiàn)，例如由脈沖干擾引起的錯(cuò)碼?；旌闲诺栏攀龅谖屙?yè)，共94頁(yè)。差錯(cuò)控制技術(shù)的種類：檢錯(cuò)重發(fā)：能發(fā)現(xiàn)錯(cuò)碼，但是不能確定錯(cuò)碼的位置。通信系統(tǒng)需要有雙向信道。前向糾錯(cuò)(FEC)：利用加入的差錯(cuò)控制碼元，不但能夠發(fā)現(xiàn)錯(cuò)碼，還能糾正錯(cuò)碼。反饋校驗(yàn)：將收到的碼元轉(zhuǎn)發(fā)回發(fā)送端，將它和原發(fā)送碼元比較。缺點(diǎn)：需要雙向信道，傳輸效率也較低。檢錯(cuò)刪除：在接收端發(fā)現(xiàn)錯(cuò)碼后，立即將其刪除。適用在發(fā)送碼元中有大量多余度，刪除部分接收碼元不影響應(yīng)用之處。第六頁(yè)，共94頁(yè)。7信源編碼，目的是實(shí)現(xiàn)模擬信號(hào)數(shù)字化信道編碼，目的是提高數(shù)字通信的可靠性差錯(cuò)率是信噪比的函數(shù)信道編碼，差錯(cuò)控制編碼，抗干擾編碼信道編碼過(guò)程：信息碼元序列＋監(jiān)督碼元→編碼碼組信道譯碼過(guò)程：編碼碼組→檢錯(cuò)或糾錯(cuò)→信息碼元序列概述第七頁(yè)，共94頁(yè)。8信道編碼的構(gòu)造在發(fā)送端，在待發(fā)送的信息序列中加入一些多余的碼元（監(jiān)督碼元），這些監(jiān)督碼元和信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)，即滿足一定的約束關(guān)系。在接收端，按既定的規(guī)則檢驗(yàn)信息碼元與監(jiān)督碼元之間的約束關(guān)系。約束關(guān)系被破壞就意味著傳輸中有差錯(cuò)（檢錯(cuò)）；借助于約束關(guān)系甚至還可以糾正錯(cuò)誤（糾錯(cuò)）。概述第八頁(yè)，共94頁(yè)。編碼序列的參數(shù)n－編碼序列中總碼元數(shù)量k－編碼序列中信息碼元數(shù)量r－編碼序列中差錯(cuò)控制碼元數(shù)量（差錯(cuò)控制碼元，以后稱為監(jiān)督碼元或監(jiān)督位）k/n－碼率(n-k)/n=r/n－冗余度概述第九頁(yè)，共94頁(yè)。10常用的差錯(cuò)控制方式有三種：前向糾錯(cuò)（FEC:forwarderrorcorrection）發(fā)送能糾錯(cuò)的碼，在譯碼時(shí)自動(dòng)發(fā)現(xiàn)并糾正傳輸中的錯(cuò)誤只需正向信道，實(shí)時(shí)性好編譯碼設(shè)備復(fù)雜，適合單向信道和一發(fā)多收系統(tǒng)檢錯(cuò)重發(fā)（ARQ:automaticrepeatrequest）發(fā)送端發(fā)出能夠檢錯(cuò)的碼，接收端檢驗(yàn)，接收端發(fā)出反饋應(yīng)答信號(hào)，發(fā)送端重新傳輸直到正確接收為止工作原理簡(jiǎn)單，正向信道+反向信道，傳輸效率低混合糾錯(cuò)（HEC:hybriderrorcorrection）前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合與折衷外層先采用前向糾錯(cuò)，當(dāng)前向糾錯(cuò)不能解決問(wèn)題時(shí)，內(nèi)層再采用檢錯(cuò)重發(fā)。概述第十頁(yè)，共94頁(yè)。自動(dòng)要求重發(fā)(ARQ)系統(tǒng)停止等待ARQ系統(tǒng)拉后ARQ系統(tǒng)第十一頁(yè)，共94頁(yè)。選擇重發(fā)ARQ系統(tǒng)ARQ和前向糾錯(cuò)比較：優(yōu)點(diǎn)監(jiān)督碼元較少，即碼率較高檢錯(cuò)的計(jì)算復(fù)雜度較低能適應(yīng)不同特性的信道缺點(diǎn)需要雙向信道。不適用于一點(diǎn)到多點(diǎn)的通信系統(tǒng)或廣播系統(tǒng)。傳輸效率降低，可能因反復(fù)重發(fā)而造成事實(shí)上的通信中斷。第十二頁(yè)，共94頁(yè)。13糾錯(cuò)編碼的基本原理差錯(cuò)控制編碼的分類分組碼舉例分組碼概念編碼的糾檢錯(cuò)能力第十三頁(yè)，共94頁(yè)。14

在編碼前先把信息序列分為k位一組（稱為信息碼），然后附加m位監(jiān)督碼，形成n=k+m位的碼組。1、按信息碼和附加監(jiān)督碼間的檢驗(yàn)關(guān)系線性碼：監(jiān)督碼是信息碼的線性組合非線性碼：監(jiān)督碼是信息碼的非線性組合2、按信息碼和監(jiān)督碼間的約束方式分組碼：監(jiān)督碼僅與本碼組的信息碼有關(guān)卷積碼：監(jiān)督碼與之前的若干個(gè)信息碼組的碼元有約束關(guān)系差錯(cuò)控制編碼的分類第十四頁(yè)，共94頁(yè)。分組碼舉例設(shè)：有一種由3個(gè)二進(jìn)制碼元構(gòu)成的編碼，它共有23=8種 不同的可能碼組： 000–晴001–云010–陰011–雨 100–雪101–霜110–霧111–雹 這時(shí)，若一個(gè)碼組中發(fā)生錯(cuò)碼，則將收到錯(cuò)誤信息。若在此8種碼組中僅允許使用4種來(lái)傳送天氣，例如：令 000–晴011–云101–陰110–雨 為許用碼組，其他4種不允許使用，稱為禁用碼組。 這時(shí)，接收端有可能發(fā)現(xiàn)（檢測(cè)到）碼組中的一個(gè)錯(cuò)碼。這種編碼只能檢測(cè)錯(cuò)碼，不能糾正錯(cuò)碼。若規(guī)定只許用兩個(gè)碼組：例如 000–晴111–雨 就能檢測(cè)兩個(gè)以下錯(cuò)碼，或糾正一個(gè)錯(cuò)碼。 第十五頁(yè)，共94頁(yè)。分組碼概念分組碼＝信息位＋監(jiān)督位分組碼符號(hào)：(n,k) 其中，n－碼組總長(zhǎng)度，

k－信息碼元數(shù)目。

r=n–k－監(jiān)督碼元數(shù)目。 右表中的碼組為(3,2)碼。分組碼的一般結(jié)構(gòu)：分組碼的參數(shù)：碼重：碼組內(nèi)“1”的個(gè)數(shù)碼距：兩碼組中對(duì)應(yīng)位取值不同的位數(shù)，又稱漢明距離最小碼距(d0)：各碼組間的最小距離第十六頁(yè)，共94頁(yè)。碼距的幾何意義：以n=3的編碼為例一般而言，碼距是n維空間中單位正多面體頂點(diǎn)之間的漢明距離。第十七頁(yè)，共94頁(yè)。一種編碼的糾檢錯(cuò)能力：決定于最小碼距d0的值。為了能檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距為了能糾正t個(gè)錯(cuò)碼，要求最小碼距第十八頁(yè)，共94頁(yè)。為了能糾正t個(gè)錯(cuò)碼，同時(shí)檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距 糾檢結(jié)合工作方式：當(dāng)錯(cuò)碼數(shù)量少時(shí)，系統(tǒng)按前向糾錯(cuò)方式工作，以節(jié)省重發(fā)時(shí)間，提高傳輸效率；當(dāng)錯(cuò)碼數(shù)量多時(shí)，系統(tǒng)按反饋重發(fā)的糾錯(cuò)方式工作，以降低系統(tǒng)的總誤碼率。第十九頁(yè)，共94頁(yè)。20糾錯(cuò)編碼系統(tǒng)的性能誤碼率性能和帶寬的關(guān)系功率和帶寬的關(guān)系傳輸速率和帶寬的關(guān)系編碼增益第二十頁(yè)，共94頁(yè)。 采用編碼降低誤碼率 所付出的代價(jià)是帶寬的增大。誤碼率性能和帶寬的關(guān)系第二十一頁(yè)，共94頁(yè)。采用編碼以節(jié)省功率，并保持誤碼率不變，付出的代價(jià)也是帶寬增大。功率和帶寬的關(guān)系第二十二頁(yè)，共94頁(yè)。

對(duì)于給定的傳輸系統(tǒng)，其傳輸速率和Eb/n0的關(guān)系： 式中，RB－碼元速率。提高傳輸速率，采用編碼以保持誤碼率不變；付出的代價(jià)仍是帶寬增大。傳輸速率和帶寬的關(guān)系第二十三頁(yè)，共94頁(yè)。 定義：在保持誤碼率恒定條件下，采用糾錯(cuò)編碼所節(jié)省的信噪比Eb/n0稱為編碼增益：

式中，(Eb/n0)u－未編碼時(shí)的信噪比(dB)； (Eb/n0)c－編碼后所需的信噪比(dB)。編碼增益第二十四頁(yè)，共94頁(yè)。25奇偶監(jiān)督碼一維奇偶監(jiān)督碼二維奇偶監(jiān)督碼重復(fù)碼（補(bǔ)充）恒比碼（補(bǔ)充）正反碼（補(bǔ)充）第二十五頁(yè)，共94頁(yè)。奇偶監(jiān)督碼－分為奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼兩類。在奇偶監(jiān)督碼中，監(jiān)督位只有1位，故碼率等于k/(k+1)。偶數(shù)監(jiān)督碼中，此監(jiān)督位使碼組中“1”的個(gè)數(shù)為偶數(shù)： 式中，a0為監(jiān)督位，其他位為信息位。奇數(shù)監(jiān)督碼中，此監(jiān)督位使碼組中“1”的個(gè)數(shù)為奇數(shù)：一維奇偶監(jiān)督碼第二十六頁(yè)，共94頁(yè)。27一般情況下：譯碼方法(與編碼方法相對(duì)應(yīng))不滿足校驗(yàn)關(guān)系，傳輸一定錯(cuò)誤！奇偶校驗(yàn)只能發(fā)現(xiàn)奇數(shù)個(gè)(單個(gè))錯(cuò)誤，不能檢測(cè)出偶數(shù)個(gè)錯(cuò)誤。編碼方法簡(jiǎn)單且實(shí)用性強(qiáng)，適用于檢測(cè)隨機(jī)零星錯(cuò)碼滿足校驗(yàn)關(guān)系，傳輸一定準(zhǔn)確嗎？一維奇偶監(jiān)督碼第二十七頁(yè)，共94頁(yè)。檢錯(cuò)能力－能夠檢測(cè)奇數(shù)個(gè)錯(cuò)碼。設(shè)：碼組長(zhǎng)度為n， 碼組中各個(gè)錯(cuò)碼的發(fā)生是獨(dú)立的和等概率的， 則在一個(gè)碼組中出現(xiàn)j個(gè)錯(cuò)碼的概率為

式中， —為在n個(gè)碼元中有j個(gè)錯(cuò)碼的組合數(shù)。奇偶監(jiān)督碼不能檢測(cè)碼組中出現(xiàn)的偶數(shù)個(gè)錯(cuò)碼，所以在一個(gè)碼組中有錯(cuò)碼而不能檢測(cè)的概率等于: －當(dāng)n為偶數(shù)時(shí) －當(dāng)n為奇數(shù)時(shí)第二十八頁(yè)，共94頁(yè)。[例]右表中的編碼是偶數(shù)監(jiān)督碼。 設(shè)信道的誤碼率為10-4，錯(cuò)碼的出 現(xiàn)是獨(dú)立的。試計(jì)算其不能檢測(cè) 的誤碼率。 將給定條件代入式 計(jì)算得出 由計(jì)算結(jié)果可見(jiàn)，此編碼可以將誤碼率從10-4降低到10-8量級(jí)。效果非常明顯。一維奇偶監(jiān)督碼第二十九頁(yè)，共94頁(yè)。30將奇偶校驗(yàn)碼的若干碼組排列成矩陣每一碼組寫(xiě)成一行m個(gè)碼組m行m個(gè)監(jiān)督位構(gòu)成了一監(jiān)督位列按列的方向增加第二維校驗(yàn)位n個(gè)監(jiān)督位構(gòu)成了一監(jiān)督位行二維奇偶監(jiān)督碼第三十頁(yè)，共94頁(yè)。碼率等于有可能檢測(cè)偶數(shù)個(gè)錯(cuò)碼適合檢測(cè)突發(fā)錯(cuò)碼能夠糾正部分錯(cuò)碼二維奇偶監(jiān)督碼第三十一頁(yè)，共94頁(yè)。32——(3，1)重復(fù)碼兩個(gè)碼字為000和111，其最小碼距為3；——(n，1)重復(fù)碼也只有全0碼和全1碼兩個(gè)碼字，其最小碼距為n，卻有2n-2個(gè)禁用碼組，隨著碼長(zhǎng)的增大，其冗余也變得很大；——該碼隨碼長(zhǎng)增加，具有很強(qiáng)的糾檢錯(cuò)能力，但其編碼效率的急劇下降；——重復(fù)碼并不是一種優(yōu)秀的編碼方案，僅用于速率很低的數(shù)據(jù)通信系統(tǒng)中?！貜?fù)碼只有一位信息碼元，監(jiān)督碼元是信息碼元的重復(fù)，所以僅有兩個(gè)碼字；重復(fù)碼第三十二頁(yè)，共94頁(yè)。33

從固定碼長(zhǎng)的碼組中選擇那些1和0的比例恒定的碼組作為許用碼組，如五單位保護(hù)電碼等。

——目前我國(guó)電傳通信中普遍采用3：2碼，又稱5中取3碼。——國(guó)際上通用的ARQ電報(bào)通信系統(tǒng)中，采用7中取3碼。恒比碼第三十三頁(yè)，共94頁(yè)。34——該碼型多用于10單位碼的前向糾錯(cuò)設(shè)備中，可以糾正一位錯(cuò)誤，發(fā)現(xiàn)全部?jī)蓚€(gè)以下的錯(cuò)誤，以及大部分兩個(gè)以上的錯(cuò)誤，其本質(zhì)就是五單位碼的重復(fù)；

編碼規(guī)則——信息碼組中1的數(shù)目為奇數(shù)時(shí)，監(jiān)督碼是信息碼的重復(fù)即正碼；信息碼組中1的數(shù)目為偶數(shù)時(shí)，監(jiān)督碼是信息碼的反碼。

譯碼方法——首先將收到的碼字重的信息位和監(jiān)督位按對(duì)應(yīng)位作模2運(yùn)算，得到一個(gè)5位碼組，若該碼字中有奇數(shù)個(gè)1，則將其作為校驗(yàn)碼組，若有偶數(shù)個(gè)1，則取其反碼作為校驗(yàn)碼組。然后，按照下表進(jìn)行糾檢錯(cuò)譯碼正反碼第三十四頁(yè)，共94頁(yè)。35正反碼錯(cuò)誤判決表正反碼第三十五頁(yè)，共94頁(yè)。36線性分組碼基本概念糾錯(cuò)基本原理漢明碼分組碼的一般原理第三十六頁(yè)，共94頁(yè)。代數(shù)碼－利用代數(shù)關(guān)系式產(chǎn)生監(jiān)督位的編碼線性分組碼－代數(shù)碼的一種，其監(jiān)督位和 信息位的關(guān)系由線性代數(shù)方程決定漢明碼－一種能夠糾正一個(gè)錯(cuò)碼的線性分組碼校正子： 在偶數(shù)監(jiān)督碼中，計(jì)算 實(shí)際上就是計(jì)算 并檢驗(yàn)S是否等于0。 S稱為校正子。監(jiān)督關(guān)系式：基本概念第三十七頁(yè)，共94頁(yè)。38近世代數(shù)學(xué)有限域的概念：有限個(gè)元素的集合，按規(guī)定可以進(jìn)行的代數(shù)四則運(yùn)算，其運(yùn)算結(jié)果仍屬于該集合中有限的元素。最簡(jiǎn)單的有限域{0，1}——Galois域1+1=0、1+0=1、0+1=1、0+0=01x1=1、1x0=0、0x0=0、0x1=0定義線性分組碼的加法為模2加，乘法為二進(jìn)制乘法。且碼字與碼字的運(yùn)算是各個(gè)相應(yīng)比特位上的上述二進(jìn)制運(yùn)算規(guī)則?；靖拍畹谌隧?yè)，共94頁(yè)。39中，S只有兩種取值，故只能表示有錯(cuò)和無(wú)錯(cuò)，而不能進(jìn)一步指明錯(cuò)碼的位置。若此碼組長(zhǎng)度增加一位，則能增加一個(gè)監(jiān)督關(guān)系式。這樣，就能得到兩個(gè)校正子。兩個(gè)校正子的可能取值有4種組合，即00，01，10，11，故能表示4種不同的信息。若用其中一種組合表示無(wú)錯(cuò)碼，則還有其他3種組合可以用于指明一個(gè)錯(cuò)碼的3種不同位置。從而可以有糾錯(cuò)能力。一般而言，若有r個(gè)監(jiān)督關(guān)系式，則r個(gè)校正子可以指明一個(gè)錯(cuò)碼的(2r–1)個(gè)不同位置。當(dāng)校正子可以指明的錯(cuò)碼位置數(shù)目等于或大于碼組長(zhǎng)度n時(shí)，才能夠糾正碼組中任何一個(gè)位置上的錯(cuò)碼，即要求糾錯(cuò)基本原理第三十九頁(yè)，共94頁(yè)。40例：要求設(shè)計(jì)一個(gè)能夠糾正1個(gè)錯(cuò)碼的分組碼(n,k)，給定的碼組中有4個(gè)信息位，即k=4。由 這時(shí)要求監(jiān)督位數(shù)r

3。若取r=3，則n=k+r=7?，F(xiàn)在用a6

a5

a4

a3

a2

a1

a0表示這7個(gè)碼元，用S1S2

S3表示校正子，則這3個(gè)校正子恰好能夠指明23–1=7個(gè)錯(cuò)碼的位置。若規(guī)定校正子和錯(cuò)碼位置的關(guān)系如下表，則僅當(dāng)在a6

a5

a4

a2位置上有錯(cuò)碼時(shí)，校正子S1的值才等于1；否則S1的值為零。這就意味著a6

a5

a4

a2四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：同理，有漢明碼第四十頁(yè)，共94頁(yè)。41在編碼時(shí)，信息位a6

a5

a4

a3的值決定于輸入信號(hào)，它們是隨機(jī)的。監(jiān)督位a2

a1

a0是按監(jiān)督關(guān)系確定的，應(yīng)該保證上列3式中的校正子等于0，即有 給定信息位后，為了 計(jì)算監(jiān)督位，上式可 以改寫(xiě)為 按照上式計(jì)算結(jié)果為漢明碼第四十一頁(yè)，共94頁(yè)。42在接收端解碼時(shí)，對(duì)于每個(gè)接收碼組，先按式 計(jì)算出校正子S1，S2和S3，然后按照表 判斷錯(cuò)碼的位置。 例：若接收碼組為0000011，則按上三式計(jì)算得到：S1=0，S2=1，S3=1。這樣，由上表可知，錯(cuò)碼位置在a3。漢明碼第四十二頁(yè)，共94頁(yè)。43上例中的漢明碼是(7,4)碼，其最小碼距d0=3。由式可知，此碼能夠檢測(cè)2個(gè)錯(cuò)碼，或糾正1個(gè)錯(cuò)碼。漢明碼的碼率：

當(dāng)r(或n)很大時(shí)，上式趨近于1。所以漢明碼是一種高效編碼。漢明碼第四十三頁(yè)，共94頁(yè)。44線性分組碼的監(jiān)督位和信息位的關(guān)系 可以改寫(xiě)為 上式中，已經(jīng)將“”簡(jiǎn)寫(xiě)成“+”。分組碼的一般原理第四十四頁(yè)，共94頁(yè)。45監(jiān)督矩陣 上式可以寫(xiě)成矩陣形式：

（模2）

將上式簡(jiǎn)寫(xiě)為

HAT=0T或AHT=0分組碼的一般原理第四十五頁(yè)，共94頁(yè)。46

HAT=0T

式中， －稱為監(jiān)督矩陣監(jiān)督矩陣的性質(zhì)監(jiān)督矩陣H確定碼組中的信息位和監(jiān)督位的關(guān)系。H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，即監(jiān)督位數(shù)r。H的每行中“1”的位置表示相應(yīng)的碼元參與監(jiān)督關(guān)系。

H可以分成兩部分，例如 －典型監(jiān)督矩陣式中，P為r

k階矩陣，Ir為r

r階單位方陣。

A=[a6

a5

a4

a3

a2

a1

a0]

0=[000]第四十六頁(yè)，共94頁(yè)。47H矩陣的各行應(yīng)該是線性無(wú)關(guān)的，否則將得不到r個(gè)線性無(wú)關(guān)的監(jiān)督關(guān)系式。若一個(gè)矩陣能寫(xiě)成典型陣形式[PIr]，則其各行一定是線性無(wú)關(guān)的。生成矩陣?yán)? 可以寫(xiě)為 上式兩端分別轉(zhuǎn)置后，可以變成式中，Q為k

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

第四十七頁(yè)，共94頁(yè)。48 將Q的左邊加上一個(gè)k階單位方陣，稱為生成矩陣： －生成矩陣

G稱為生成矩陣，因?yàn)榭梢杂盟a(chǎn)生整個(gè)碼組A，即有生成矩陣的性質(zhì)具有[IkQ]形式的生成矩陣稱為典型生成矩陣。由典型生成矩陣得出的碼組A中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼組稱為系統(tǒng)碼。矩陣G的各行也必須是線性無(wú)關(guān)的。如果已有k個(gè)線性無(wú)關(guān)的碼組，則可以將其用來(lái)作為生成矩陣G，并由它生成其余碼組。分組碼的一般原理第四十八頁(yè)，共94頁(yè)。49錯(cuò)誤圖樣 設(shè)：發(fā)送碼組A是一個(gè)n列的行矩陣： 接收碼組是一個(gè)n列的行矩陣B： 令接收碼組和發(fā)送碼組之差為

E就是錯(cuò)碼的行矩陣 －稱為錯(cuò)誤圖樣 式中， (i=0,1,…,n-1) 若ei

=0，表示該碼元未錯(cuò)；若ei=1，表示該碼元為錯(cuò)碼。B–A=E(模2)分組碼的一般原理第四十九頁(yè)，共94頁(yè)。50校正子矩陣

B–A=E可以改寫(xiě)成B=A+E上式表示發(fā)送碼組A與錯(cuò)碼矩陣E之和等于接收碼組B。例如，若發(fā)送碼組A=[1000111]， 錯(cuò)碼矩陣E=[0000100]，則 接收碼組B=[1000011]。在接收端解碼時(shí)，將接收碼組B代入式

AHT=0 中A的位置進(jìn)行計(jì)算。若接收碼組中無(wú)錯(cuò)碼，則B=A。代入后，該式仍成立，即有

BHT=0 只有當(dāng)錯(cuò)碼未超出檢測(cè)能力時(shí)，上式才不成立。 假設(shè)，這時(shí)該式的右端等于S，即有

BHT=S 將B=A+E代入上式，得到:S=(A+E)HT=AHT+EHT第五十頁(yè)，共94頁(yè)。51 S=(A+E)HT=AHT+EHT上式右端第一項(xiàng)等于0，所以

S=EHT－校正子矩陣當(dāng)H確定后，上式中S只與E有關(guān)，而與A無(wú)關(guān)。這意味著，S和錯(cuò)碼E之間有確定的線性變換關(guān)系。 若S和E有一一對(duì)應(yīng)關(guān)系，則S將能代表錯(cuò)碼位置。線性碼的封閉性：若A1和A2是一種線性碼中的兩個(gè)碼組，則(A1+A2)仍是其中一個(gè)碼組。 『證』若A1和A2是兩個(gè)碼組，則有：A1HT=0,A2HT=0 將上兩式相加，得出

A1HT+A2HT=(A1+A2)HT=0

所以(A1+A2)也是一個(gè)碼組。 由于線性碼具有封閉性，所以兩個(gè)碼組(A1和A2)之間的距離（即對(duì)應(yīng)位不同的數(shù)目）必定是另一個(gè)碼組(A1+A2)的重量（即“1”的數(shù)目）。因此，碼的最小距離就是碼的最小重量（除全“0”碼組外）。第五十一頁(yè)，共94頁(yè)。52循環(huán)碼循環(huán)碼的概念循環(huán)碼的運(yùn)算循環(huán)碼的編碼方法循環(huán)碼的解碼方法截短循環(huán)碼BCH碼RS碼第五十二頁(yè)，共94頁(yè)。53

循環(huán)性是指任一碼組循環(huán)一位后仍然是該編碼中的一個(gè)碼組。

例：一種(7,3)循環(huán)碼的全部碼組如下

表中第2碼組向右移一位即得到第5碼組；第5碼組向右移一位即得到第7碼組。循環(huán)碼的概念第五十三頁(yè)，共94頁(yè)。54一般情況 若(an-1

an-2…a0)是循環(huán)碼的一個(gè)碼組，則循環(huán)移位后的碼組： (an-2

an-3…a0

an-1) (an-3

an-4…an-1

an-2) …… (a0

an-1…a2

a1)仍然是該編碼中的碼組。多項(xiàng)式表示法 一個(gè)長(zhǎng)度為n的碼組(an-1

an-2…a0)可以表示成

上式中x的值沒(méi)有任何意義，僅用它的冪代表碼元的位置。例：碼組1100101可以表示為循環(huán)碼的概念第五十四頁(yè)，共94頁(yè)。55

整數(shù)的按模運(yùn)算

在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模2運(yùn)算中，有1+1=20(模2)， 1+2=31(模2)，23=60(模2)等等。 一般說(shuō)來(lái)，若一個(gè)整數(shù)m可以表示為 式中，Q為整數(shù)，則在模n運(yùn)算下，有

m

p(模n) 所以，在模n運(yùn)算下，一個(gè)整數(shù)m等于它被n除得的余數(shù)。循環(huán)碼的運(yùn)算第五十五頁(yè)，共94頁(yè)。56碼多項(xiàng)式的按模運(yùn)算 若任意一個(gè)多項(xiàng)式F(x)被一個(gè)n次多項(xiàng)式N(x)除，得到商式Q(x)和一個(gè)次數(shù)小于n的余式R(x)，即 則在按模N(x)運(yùn)算下，有 這時(shí)，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算。 例1：x3被(x3+1)除，得到余項(xiàng)1，即 例2： 因?yàn)?/p>

x

x3+1x4+x2+1

x4+x

x2+x+1 在模2運(yùn)算中加法和減法一樣。第五十六頁(yè)，共94頁(yè)。57循環(huán)碼的數(shù)學(xué)表示法 在循環(huán)碼中，設(shè)T(x)是一個(gè)長(zhǎng)度為n的碼組，若 則T(x)也是該編碼中的一個(gè)碼組。 [證]設(shè)一循環(huán)碼為 則有 上式中的T(x)正是碼組T(x)向左循環(huán)移位i次的結(jié)果。 例：一循環(huán)碼為1100101，即 若給定i=3，則有 上式對(duì)應(yīng)的碼組為0101110，它正是T(x)向左移3位的結(jié)果。結(jié)論：一個(gè)長(zhǎng)為n的循環(huán)碼必定為按模(xn+1)運(yùn)算的一個(gè)余式。第五十七頁(yè)，共94頁(yè)。58循環(huán)碼的生成有了生成矩陣G，就可以由k個(gè)信息位得出整個(gè)碼組： 例： 式中， 生成矩陣G的每一行都是一個(gè)碼組。因此，若能找到k個(gè)已知的碼組，就能構(gòu)成矩陣G。如前所述，這k個(gè)已知碼組必須是線性不相關(guān)的。在循環(huán)碼中，一個(gè)(n,k)碼有2k個(gè)不同的碼組。若用g(x)表示其中前(k-1)位皆為“0”的碼組，則g(x)，xg(x)，x2g(x)，，xk-1g(x)都是碼組，而且這k個(gè)碼組是線性無(wú)關(guān)的。因此它們可以用來(lái)構(gòu)成此循環(huán)碼的生成矩陣G。循環(huán)碼的運(yùn)算第五十八頁(yè)，共94頁(yè)。59在循環(huán)碼中除全“0”碼組外，再?zèng)]有連續(xù)k位均為“0”的碼組。否則，在經(jīng)過(guò)若干次循環(huán)移位后將得到k位信息位全為“0”，但監(jiān)督位不全為“0”的一個(gè)碼組。這在線性碼中顯然是不可能的。因此，g(x)必須是一個(gè)常數(shù)項(xiàng)不為“0”的(n-k)次多項(xiàng)式，而且這個(gè)g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一一個(gè)多項(xiàng)式。因?yàn)槿绻袃蓚€(gè)，則由碼的封閉性，把這兩個(gè)相加也應(yīng)該是一個(gè)碼組，且此碼組多項(xiàng)式的次數(shù)將小于(n–k)，即連續(xù)“0”的個(gè)數(shù)多于(k–1)。顯然，這是與前面的結(jié)論矛盾的。我們稱這唯一的(n–k)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式。一旦確定了g(x)，則整個(gè)(n,k)循環(huán)碼就被確定了。循環(huán)碼的運(yùn)算第五十九頁(yè)，共94頁(yè)。60因此，循環(huán)碼的生成矩陣G可以寫(xiě)成例： 上表中的編碼為(7,3)循環(huán)碼，n=7,k=3,n–k=4，其中唯一的一個(gè)(n–k)=4次碼多項(xiàng)式代表的碼組是第二碼組0010111，與它對(duì)應(yīng)的碼多項(xiàng)式，即生成多項(xiàng)式，為

g(x)=x4+x2+x+1。第六十頁(yè)，共94頁(yè)。61 g(x)=x4+x2+x+1即“10111” 將此g(x)代入上矩陣，得到 或 上式不符合G=[IkQ]形式，所以它不是典型生成矩陣。但它經(jīng)過(guò)線性變換后，不難化成典型陣。 此循環(huán)碼組的多項(xiàng)式表示式T(x)： 上式表明，所有碼多項(xiàng)式T(x)都能夠被g(x)整除，而且任意一個(gè)次數(shù)不大于(k–1)的多項(xiàng)式乘g(x)都是碼多項(xiàng)式。第六十一頁(yè)，共94頁(yè)。62尋求碼生成多項(xiàng)式

因?yàn)槿我庖粋€(gè)循環(huán)碼T(x)都是g(x)的倍式，故它可以寫(xiě)成 T(x)=h(x)g(x) 而生成多項(xiàng)式g(x)本身也是一個(gè)碼組，即有

T

(x)=g(x) 由于碼組T

(x)是一個(gè)(n–k)次多項(xiàng)式，故xkT

(x)是一個(gè)n次多項(xiàng)式。由 可知，xk

T

(x)在模(xn+1)運(yùn)算下也是一個(gè)碼組，所以有 上式左端分子和分母都是n次多項(xiàng)式，故相除的商式Q(x)=1。因此，上式可以寫(xiě)成循環(huán)碼的運(yùn)算第六十二頁(yè)，共94頁(yè)。63將T(x)=h(x)g(x)和T

(x)=g(x)代入 化簡(jiǎn)后，得到上式表明，生成多項(xiàng)式g(x)應(yīng)該是(xn+1)的一個(gè)因子。例：(x7+1)可以分解為 為了求出(7,3)循環(huán)碼的生成多項(xiàng)式g(x)，需要從上式中找到一個(gè)(n–k)=4次的因子。這樣的因子有兩個(gè)，即 以上兩式都可以作為生成多項(xiàng)式。 選用的生成多項(xiàng)式不同，產(chǎn)生出的循環(huán)碼碼組也不同。循環(huán)碼的運(yùn)算第六十三頁(yè)，共94頁(yè)。64用xn-k乘m(x)。這一運(yùn)算實(shí)際上是在信息碼后附加上(n–k)個(gè)“0”。例如，信息碼為110，它寫(xiě)成多項(xiàng)式為m(x)=x2+x。當(dāng)n–k=7–3=4時(shí)，xn-km(x)=x4(x2+x)=x6+x5，它表示碼組1100000。用g(x)除xn-km(x)，得到商Q(x)和余式r(x)，即有 例：若選定g(x)=x4+x2+x+1，則有 上式是用碼多項(xiàng)式表示的運(yùn)算。它和下式等效：編出的碼組T(x)為：T(x)=xn-km(x)+r(x) 在上例中，T(x)=1100000+101=1100101 循環(huán)碼的編碼方法第六十四頁(yè)，共94頁(yè)。65

在檢錯(cuò)時(shí)：當(dāng)接收碼組沒(méi)有錯(cuò)碼時(shí)，接收碼組R(x)必定能被g(x)整除，即下式 中余項(xiàng)r(x)應(yīng)為零；否則，有誤碼。當(dāng)接收碼組中的錯(cuò)碼數(shù)量過(guò)多，超出了編碼的檢錯(cuò)能力時(shí)，有錯(cuò)碼的接收碼組也可能被g(x)整除。這時(shí)，錯(cuò)碼就不能檢出了。在糾錯(cuò)時(shí)：用生成多項(xiàng)式g(x)除接收碼組R(x)，得出余式r(x)。按照余式r(x)，用查表的方法或計(jì)算方法得出錯(cuò)誤圖樣E(x)。從R(x)中減去E(x)，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組T(x)。循環(huán)碼的解碼方法第六十五頁(yè)，共94頁(yè)。66截短目的： 在設(shè)計(jì)時(shí)，通常信息位數(shù)k、碼長(zhǎng)n和糾錯(cuò)能力都是預(yù)先給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。故采用截短碼長(zhǎng)截短，得出滿足要求的編碼。截短方法： 設(shè)給定一個(gè)(n,k)循環(huán)碼，它共有2k種碼組，現(xiàn)使其前i(0<i<k)個(gè)信息位全為“0”，于是它變成僅有2k-i種碼組。然后從中刪去這i位全“0”的信息位，最終得到一個(gè)(n–i，k–i)的線性碼。將這種碼稱為截短循環(huán)碼。截短循環(huán)碼與截短前的循環(huán)碼至少具有相同的糾錯(cuò)能力，并且截短循環(huán)碼的編解碼方法仍和截短前的方法一樣。例：要求構(gòu)造一個(gè)能夠糾正1位錯(cuò)碼的(13,9)碼。 這時(shí)可以由(15,11)循環(huán)碼的11種碼組中選出前兩信息位均為“0”的碼組，構(gòu)成一個(gè)新的碼組集合。然后在發(fā)送時(shí)不發(fā)送這兩位“0”。于是發(fā)送碼組成為(13,9)截短循環(huán)碼。截短循環(huán)碼第六十六頁(yè)，共94頁(yè)。67BCH碼是能夠糾正多個(gè)隨機(jī)錯(cuò)碼的循環(huán)碼。BCH碼分為兩類：本原BCH碼和非本原BCH碼。本原BCH碼：碼長(zhǎng)n=2m–1(m

3，任意正整數(shù))，它的生成多項(xiàng)式g(x)中含有最高次數(shù)為m次的本原多項(xiàng)式；非本原BCH碼：碼長(zhǎng)n是(2m–1)的一個(gè)因子，它的生成多項(xiàng)式g(x)中不含有最高次數(shù)為m的本原多項(xiàng)式。BCH碼的工程設(shè)計(jì)：可以用查表法找到所需的生成多項(xiàng)式。 例：二進(jìn)制非本原BCH碼的生成多項(xiàng)式系數(shù) 表中g(shù)(x)是用8進(jìn)制數(shù)字表示的；t為糾錯(cuò)能力。BCH碼第六十七頁(yè)，共94頁(yè)。68常用BCH碼：戈萊(Golay)碼：(23,12)非本原BCH碼，它能糾正3個(gè)隨機(jī)錯(cuò)碼，并且容易解碼。擴(kuò)展BCH碼(n+1,k)：BCH碼的長(zhǎng)度為奇數(shù)。在應(yīng)用中，為了得到偶數(shù)長(zhǎng)度的碼，并增大檢錯(cuò)能力，可以在BCH碼生成多項(xiàng)式中乘上一個(gè)因式(x+1)，從而得到擴(kuò)展BCH碼(n+1,k)。擴(kuò)展BCH碼已經(jīng)不再具有循環(huán)性。擴(kuò)展戈萊碼(24,12)：其最小碼距為8，碼率為1/2，能夠糾正3個(gè)錯(cuò)碼和檢測(cè)4個(gè)錯(cuò)碼。BCH碼第六十八頁(yè)，共94頁(yè)。69幾種二進(jìn)制分組碼的性能比較2PSK漢明碼(7,4)t=1漢明碼(31,26)t=1擴(kuò)展戈萊碼(24,12)t=3BCH碼(127,64)t=10Eb/n0(dB)Pe第六十九頁(yè)，共94頁(yè)。70RS碼：是q進(jìn)制BCH碼的一個(gè)特殊子類，并且具有很強(qiáng)的糾錯(cuò)能力。RS碼的參數(shù)：碼長(zhǎng)n=q–1，監(jiān)督位數(shù)目r=2t，其中t是能夠糾正的錯(cuò)碼數(shù)目；其生成多項(xiàng)式為

g(x)=(x+)(x+2)…(x+2t) 式中，為伽羅華域GF(2m)中的本原元。RS碼的主要優(yōu)點(diǎn)：它是多進(jìn)制糾錯(cuò)編碼，所以特別適合用于多進(jìn)制調(diào)制的場(chǎng)合；它能夠糾正t個(gè)q位二進(jìn)制錯(cuò)碼，即能夠糾正不超過(guò)q個(gè)連續(xù)的二進(jìn)制錯(cuò)碼，所以適合在衰落信道中糾正突發(fā)性錯(cuò)碼。RS碼第七十頁(yè)，共94頁(yè)。71卷積碼卷積碼的編碼卷積碼的解碼第七十一頁(yè)，共94頁(yè)。72卷積碼的特點(diǎn)：監(jiān)督碼元不僅和當(dāng)前的k比特信息段有關(guān)，而且還同前面m=(N–1)個(gè)信息段有關(guān)。將N稱為碼組的約束度。將卷積碼記作(n,k,m)，其碼率為k/n。卷積碼第七十二頁(yè)，共94頁(yè)。73一般原理方框圖編碼輸出每次輸入k比特1k…1k…1k…1k……

…

…

1…k…2k3kNk……

…

…

…

…

…

…

…

12nNk級(jí)移存器n個(gè)模2加法器每輸入k比特旋轉(zhuǎn)1周卷積碼的編碼第七十三頁(yè)，共94頁(yè)。74卷積碼編碼器的實(shí)例方框圖：(n,k,m)=（3,1,2）每當(dāng)輸入1比特時(shí)，此編碼器輸出3比特c1c2c3：編碼器的工作狀態(tài)123b3b1輸入b2編碼輸出c2c1c3第七十四頁(yè)，共94頁(yè)。75碼樹(shù)搜索法：(3,1,2)卷積碼的碼樹(shù)圖 此法不實(shí)用：因?yàn)殡S信息位增多，分支數(shù)目按指數(shù)規(guī)律增長(zhǎng)000111001110011100010101000111001110011100010101c1c2c3000100111011001101110010c1c2c3111000001110c1c2c3信息位 1 1 0 1ba起點(diǎn)信息位000111c1c2c3abcdabcdabcdabcd上半部下半部10a狀態(tài)b3b2a00b01c10d11abcdabcdcdab↑0↓1↓1↑0↑0↓1第七十五頁(yè)，共94頁(yè)。76狀態(tài)圖和網(wǎng)格圖移存器狀態(tài)和輸入輸出碼元的關(guān)系狀態(tài)圖123b3b1輸入b2編碼輸出c2c1c3abcd000111101110010011100001第七十六頁(yè)，共94頁(yè)。77(3,1,2)卷積碼網(wǎng)格圖網(wǎng)格圖中的編碼路徑舉例輸入信息位為1101時(shí)輸出編碼序列是： 111110010100011…110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100abcd000111101110010011100001abcdabcd110010001111100第七十七頁(yè)，共94頁(yè)。78維特比算法基本原理：將接收到的序列和所有可能的發(fā)送序列作比較，選擇其中漢明距離最小的序列當(dāng)作是現(xiàn)在的發(fā)送序列例：設(shè)卷積碼為(n,k,m)=(3,1,2)碼現(xiàn)在的發(fā)送信息位為1101為了使移存器中的信息位全部移出，在信息位后面加入了3個(gè)“0”，即1101000編碼后的發(fā)送序列：111110010100001011000接收序列：111010010110001011000(紅色為錯(cuò)碼)由于這是一個(gè)(3,1,2)卷積碼，發(fā)送序列的約束度為N=m+1＝3，所以首先需考察3個(gè)信息段，即考察3n＝9比特，即接收序列前9位“111010010”。卷積碼的解碼第七十八頁(yè)，共94頁(yè)。79解碼第1步由網(wǎng)格圖可見(jiàn)，沿路徑每一級(jí)有4種狀態(tài)a,b,c和d。每種狀態(tài)只有兩條路徑可以到達(dá)。故4種狀態(tài)共有8條到達(dá)路徑。比較網(wǎng)格圖中的這8條路徑和接收序列之間的漢明距離。例如，由出發(fā)點(diǎn)狀態(tài)a經(jīng)過(guò)3級(jí)路徑后到達(dá)狀態(tài)a的兩條路徑中上面一條為“000000000”。它和接收序列“111010010”的漢明距離等于5；下面一條為“111001011”,它和接收序列的漢明距離等于3。110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100第七十九頁(yè)，共94頁(yè)。80將這8個(gè)比較結(jié)果列表如下：比較到達(dá)每個(gè)狀態(tài)的兩條路徑的漢明距離，將距離小的一條路徑保留，稱為幸存路徑。這樣，就剩下4條路徑了，即表中第2,4,6和8條路徑。卷積碼的解碼第八十頁(yè)，共94頁(yè)。81解碼第2步：繼續(xù)考察接收序列中的后繼3個(gè)比特“110”計(jì)算4條幸存路徑上增加1級(jí)后的8條可能路徑的漢明距離。計(jì)算結(jié)果列于下表中。表中總距離最小為2，其路徑是abdc+b，相應(yīng)序列為111110010100。它和發(fā)送序列相同，故對(duì)應(yīng)發(fā)送信息位1101。第八十一頁(yè)，共94頁(yè)。82按照上表中的幸存路徑畫(huà)出的網(wǎng)格圖示于下圖中。圖中粗線路徑是距漢明離最小（等于2）的路徑。abcd011010010101001abcd111100100110110卷積碼的解碼第八十二頁(yè)，共94頁(yè)。83在編碼時(shí)，信息位后面加了3個(gè)“0”。若把這3個(gè)“0”仍然看作是信息位，則可以按照上述算法繼續(xù)解碼。這樣得到的幸存路徑網(wǎng)格圖示于下圖中。圖中的粗線仍然是漢明距離最小的路徑。110011010010101101001001abcdabcd000111100100000011011001101卷積碼的解碼第八十三頁(yè)，共94頁(yè)。84若已知這3個(gè)碼元是（為結(jié)尾而補(bǔ)充的）“0”，則在解碼時(shí)就預(yù)先知道在接收這3個(gè)“0”碼元后，路徑必然應(yīng)該回到狀態(tài)a。而由圖可見(jiàn)， 只有兩條路徑可以回到a狀態(tài)。所以，這時(shí)上圖可以簡(jiǎn)化成：110011010010101101001001abcdabcd000111100100000011011001110011010010101101001001abcdabcd000111100100000011011001101第八十四頁(yè)，共94頁(yè)。85在上例中卷積碼的約束度為N=3，需要存儲(chǔ)和計(jì)算8條路徑的參量。由此可見(jiàn)，維特比算法的復(fù)雜度隨約束度N按指數(shù)形式2N增長(zhǎng)。故維特比算法適合約束度較小（N10）的編碼。對(duì)于約束度大的卷積碼，可以采用