【2022】通信原理-第11章

移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室東南大學(xué)通信原理教學(xué)團(tuán)隊(duì)

國(guó)家級(jí)一流本科課程

通信原理

信道編碼第11章高等院校電子信息類重點(diǎn)課程名師精品系列教材

2知識(shí)要點(diǎn)信道編碼的系統(tǒng)模型和基本概念線性分組碼、校正子及校正子譯碼方法循環(huán)碼及其多項(xiàng)式描述方法、編解碼電路卷積碼及其描述方法、編碼電路和維特比譯碼算法網(wǎng)格編碼調(diào)制相關(guān)概念及實(shí)例Turbo碼、LDPC碼Polar碼等信道編解碼技術(shù)第11章信道編碼

311.1引言411.1引言有效性和可靠性是數(shù)字通信系統(tǒng)的主要性能指標(biāo)由于信道噪聲和干擾的影響，信息傳輸過程中的差錯(cuò)不可避免差錯(cuò)就是指經(jīng)過信道傳輸后的接收碼元和原始發(fā)送碼元之間的差異信道編碼通過發(fā)現(xiàn)或糾正差錯(cuò)來(lái)改善通信系統(tǒng)的傳輸質(zhì)量，從而提高通信系統(tǒng)的可靠性信道編碼也稱為糾錯(cuò)編碼或差錯(cuò)控制編碼5引言不同的通信信道造成的差錯(cuò)形式也不盡相同隨機(jī)信道，噪聲獨(dú)立、隨機(jī)地影響每個(gè)傳輸碼元，因此最終的差錯(cuò)不僅是統(tǒng)計(jì)獨(dú)立的，而且出現(xiàn)概率具有隨機(jī)性太空信道、衛(wèi)星信道、光纜信道等突發(fā)信道，噪聲和干擾的影響往往前后相關(guān)，因此差錯(cuò)將成串集中出現(xiàn)，即在短時(shí)間內(nèi)會(huì)出現(xiàn)大量錯(cuò)碼，但這些時(shí)間段之間會(huì)存在較長(zhǎng)的無(wú)差錯(cuò)區(qū)間短波信道、散射信道、移動(dòng)通信信道等混合信道，既存在隨機(jī)差錯(cuò)，也存在突發(fā)差錯(cuò)針對(duì)不同的差錯(cuò)形式，信道編碼也應(yīng)采取不同的形式6引言信道編碼的基本思想按照一定的規(guī)律在原始發(fā)送信息碼元中加入一些冗余碼元，這些冗余碼元被稱為監(jiān)督碼元或校驗(yàn)碼元接收端則利用校驗(yàn)碼元與信息碼元的關(guān)系發(fā)現(xiàn)或糾正差錯(cuò)信道編碼犧牲部分系統(tǒng)的有效性換取可靠性的提高711.2信道編碼的基本原理811.2.1信道編碼的基本概念信道編碼系統(tǒng)簡(jiǎn)化模型該模型體現(xiàn)的是一種不需要反饋的差錯(cuò)控制方式編碼信道，編碼器與解碼器之間的全部模塊9差錯(cuò)控制方式的分類前向糾錯(cuò)(FEC)不需要反饋鏈路，發(fā)送端在信息碼元中加入校驗(yàn)碼元，接收端解碼器執(zhí)行譯碼適合應(yīng)用于實(shí)時(shí)傳輸系統(tǒng)自動(dòng)重發(fā)請(qǐng)求(ARQ)校驗(yàn)碼元具有較強(qiáng)的檢錯(cuò)能力執(zhí)行解碼發(fā)現(xiàn)有誤碼時(shí)，利用反向信道通知發(fā)送端重發(fā)實(shí)時(shí)性上存在缺陷，設(shè)備簡(jiǎn)單經(jīng)濟(jì)混合糾錯(cuò)當(dāng)誤碼較少，并在糾錯(cuò)碼的糾錯(cuò)范圍之內(nèi)時(shí)，使用FEC方式直接糾錯(cuò)解碼當(dāng)誤碼較多，并超出糾錯(cuò)碼的糾錯(cuò)范圍時(shí)，利用ＡＲＱ10ARQ的三種方式停止等待ARQ發(fā)送碼字后發(fā)射機(jī)停止發(fā)送，等待接收端的應(yīng)答接收端校驗(yàn)正確反饋確認(rèn)(ACK)，不正確反饋否認(rèn)(NAK)發(fā)送端根據(jù)應(yīng)答的不同結(jié)果決定發(fā)送下一組數(shù)據(jù)還是重發(fā)剛才的數(shù)據(jù)帶后退的連續(xù)ARQ發(fā)送端對(duì)發(fā)送的數(shù)據(jù)按碼字編號(hào)后進(jìn)行連續(xù)發(fā)送接收端檢測(cè)出錯(cuò)誤碼字后，把編號(hào)反饋給發(fā)送端發(fā)送端從反饋的編號(hào)位置開始重發(fā)碼字序列選擇重發(fā)連續(xù)ARQ發(fā)送端在收到接收端的錯(cuò)誤反饋后，只重發(fā)錯(cuò)誤碼字效率提升，復(fù)雜度增大11其他糾錯(cuò)碼分類按照信息碼元和校驗(yàn)碼元之間的約束方式，分為分組碼和卷積碼分組碼假設(shè)碼字長(zhǎng)度為n(碼長(zhǎng))，在分組碼中，信息序列每k位分為一組，按照編碼規(guī)則附加上n-k位校驗(yàn)碼元，這樣的碼稱為(n,k)分組碼對(duì)應(yīng)的長(zhǎng)為n的碼字集合稱為碼組無(wú)量綱比值r=k/n稱為編碼效率，簡(jiǎn)稱為碼率卷積碼校驗(yàn)碼元不僅與本碼字里的信息碼元有關(guān)，還與前面M組碼字的信息碼元有約束關(guān)系卷積碼記作(n,k,K)，K=M+1為卷積碼的約束長(zhǎng)度和分組碼比，編碼器中有存儲(chǔ)器，卷積碼編出的碼字之間存在關(guān)聯(lián)按照校驗(yàn)碼元和信息碼元之間的關(guān)系，分為線性碼和非線性碼線性碼，校驗(yàn)碼元和信息碼元之間是線性關(guān)系非線性碼，校驗(yàn)碼元和信息碼元是非線性關(guān)系12例11.1考慮一個(gè)(４,２)分組碼，碼字表示為c0c1c2c3，其中c2c3為信息碼元，c0c1為校驗(yàn)碼元，可能的信息分組是００、１０、０１、１１，舉例說(shuō)明線性編碼和非線性編碼13【解】線性編碼:設(shè)定校驗(yàn)規(guī)則為c1

=c2、

c0

=c2+c3編出的４個(gè)碼字為００００、１１１０、１００１、０１１１線性碼中任意兩個(gè)碼字的和仍然是碼字集合中的一個(gè)非線性編碼:設(shè)定校驗(yàn)規(guī)則為c1

=c2+c2c3、c0=c2c3+1編出的４個(gè)碼字為１０００、１１１０、１００１、００１１誤碼率、Eb/N0、差錯(cuò)控制編碼的關(guān)系Eb/N0決定了誤碼率誤碼率達(dá)不到系統(tǒng)要求使用差錯(cuò)控制編碼，改善Eb/N0，改善誤碼率誤碼率達(dá)到系統(tǒng)要求使用差錯(cuò)控制編碼，降低Eb/N0要求，可降低系統(tǒng)的發(fā)送功率如果保持實(shí)際信息速率不變，由于冗余的存在，需要增加帶寬，使得帶寬利用率降低；若保持帶寬不變，則實(shí)際信息速率會(huì)降低14差錯(cuò)控制編碼的影響11.2.2群、環(huán)、域的基本概念信道編碼涉及一些近世代數(shù)和線性代數(shù)的知識(shí)群令Ｇ為一組元素的集合，在該集合內(nèi)定義了一種代數(shù)運(yùn)算(●)，如果滿足以下４條公理，則稱Ｇ對(duì)運(yùn)算(●)構(gòu)成一個(gè)群群中的恒等元和逆元是唯一的如果群還滿足交換律，則稱該群是交換群或阿貝爾群15群、環(huán)、域的基本概念(續(xù))例如，整數(shù)集合對(duì)加法運(yùn)算構(gòu)成群，而且是阿貝爾群，恒等元是０，逆元是原整數(shù)的相反數(shù)；當(dāng)整數(shù)群里元素個(gè)數(shù)是無(wú)限的時(shí)，該群稱為無(wú)限群，反之，元素個(gè)數(shù)有限的群則稱為有限群非零實(shí)數(shù)對(duì)乘法構(gòu)成群，恒等元是１，逆元是其倒數(shù)環(huán)在非空集合Ｒ中，若定義了兩種運(yùn)算--加法和乘法，且滿足如下條件，則稱Ｒ

是一個(gè)環(huán)對(duì)加法運(yùn)算構(gòu)成阿貝爾群對(duì)乘法運(yùn)算滿足封閉性和結(jié)合律加法和乘法之間有分配律16群、環(huán)、域的基本概念(續(xù))如果乘法運(yùn)算還滿足交換律，則稱其為交換環(huán)例如，所有整數(shù)集合，在實(shí)數(shù)相加和相乘運(yùn)算下，構(gòu)成交換環(huán)；所有系數(shù)是整數(shù)的多項(xiàng)式集合的全體，在整數(shù)相加和相乘運(yùn)算下，也構(gòu)成交換環(huán)域在非空元素集合Ｆ中，如果定義了加法和乘法兩種代數(shù)運(yùn)算，且滿足如下條件，則稱Ｆ是一個(gè)域Ｆ對(duì)加法構(gòu)成阿貝爾群，加法恒等元記作０Ｆ中全體非０元素對(duì)乘法構(gòu)成阿貝爾群，乘法恒等元記作１加法和乘法之間滿足分配律有理數(shù)全體、實(shí)數(shù)全體、復(fù)數(shù)全體對(duì)加法和乘法都分別構(gòu)成域，且都是無(wú)限域17GF(2)若域中的元素有限，則稱為有限域，也稱伽羅華域。域中元素的個(gè)數(shù)ｑ，稱為域的階。ｑ

階有限域用ＧＦ(ｑ)表示。例如0、1兩個(gè)元素在模２加和模２乘運(yùn)算下，構(gòu)成有兩個(gè)元素的２階有限域，記作ＧＦ(２)在信道編碼系統(tǒng)中，收發(fā)雙方傳輸?shù)男畔⑹峭ㄟ^有限字符集表示的，當(dāng)這個(gè)字符集是二進(jìn)制符號(hào)０和１，又定義了加法和乘法時(shí)，就認(rèn)為編碼是定義在ＧＦ(２)上的ＧＦ(２)上的加法和乘法規(guī)則如圖1811.2.3編碼信道編碼信道由調(diào)制器、信道和解調(diào)器組成編碼器輸出二進(jìn)制序列時(shí)如果解調(diào)器在輸出時(shí)采用二進(jìn)制量化，即直接將接收信號(hào)判決為兩個(gè)二進(jìn)制符號(hào)之一，則稱這種判決方式為硬判決，相應(yīng)的譯碼稱為硬判決譯碼或代數(shù)譯碼如果輸出時(shí)采用多級(jí)量化，即信道解碼器利用多級(jí)量化的結(jié)果進(jìn)行譯碼，則稱這種判決方式為軟判決，相應(yīng)的譯碼稱為軟判決譯碼或概率譯碼硬判決會(huì)造成信息的損失，優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單；軟判決性能較好，但是實(shí)現(xiàn)相對(duì)復(fù)雜19二進(jìn)制對(duì)稱信道信道可以用一組轉(zhuǎn)移概率ｐ(ｊ｜ｉ)來(lái)描述，ｉ表示調(diào)制器的輸入符號(hào)，ｊ表示解調(diào)器的輸出符號(hào)在二進(jìn)制硬判決的情況下，信道的輸入/輸出都是二進(jìn)制序列，這時(shí)編碼信道通常用二進(jìn)制對(duì)稱信道(BSC)模型信道轉(zhuǎn)移概率是對(duì)稱的，正確概率均

為１－ｐ，錯(cuò)誤概率均為ｐ(概率ｐ

稱為轉(zhuǎn)移概率)BSC是一種離散無(wú)記憶信道2011.2.4碼距和糾錯(cuò)能力由香農(nóng)信道編碼定理，當(dāng)一個(gè)編碼通信系統(tǒng)的信息速率為Ｒ時(shí)，若要實(shí)現(xiàn)可靠傳輸，即差錯(cuò)概率任意小，系統(tǒng)的信噪比不能低于某個(gè)理論極限，這個(gè)信噪比的極限值通常稱為香農(nóng)限。一個(gè)能可靠工作的編碼方案的最低信噪比越接近于香農(nóng)限，其性能越好信道編碼發(fā)現(xiàn)錯(cuò)誤、糾正錯(cuò)誤的能力和碼的結(jié)構(gòu)密切相關(guān)以(ｎ,ｋ)線性分組碼為例，存在許用碼組和禁用碼組如果接收碼字出現(xiàn)在禁用碼組集合里，則說(shuō)明一定發(fā)生了錯(cuò)誤定義碼字中非零碼元的個(gè)數(shù)為碼字的漢明重量，簡(jiǎn)稱碼重兩個(gè)長(zhǎng)為ｎ的碼字ｃ１和ｃ２中對(duì)應(yīng)位置上碼元不同的個(gè)數(shù)定義為碼字的漢明距離，簡(jiǎn)稱碼距，記作

ｄ(ｃ１，ｃ２)碼字也稱碼矢量。在一種編碼方案下，碼組中任意兩個(gè)碼矢量之間的最小距離定義為該碼的最小碼距

ｄmin21最小碼距和糾錯(cuò)能力為檢測(cè)ｅ個(gè)錯(cuò)誤，最小碼距必須滿足為糾正ｔ個(gè)錯(cuò)誤，最小碼距必須滿足譯碼的原則是選擇和接收碼字距離最近的許用碼字作為譯碼輸出把碼字看作多維空間中的點(diǎn)，一個(gè)發(fā)送碼字錯(cuò)誤ｔ位后，接收碼字將處在以該碼字為圓心、半徑為ｔ的球體上22最小碼距和糾錯(cuò)能力(續(xù))為糾正ｔ個(gè)錯(cuò)誤的同時(shí)，檢測(cè)ｅ個(gè)錯(cuò)誤，最小碼距必須滿足最小碼距和碼的糾檢錯(cuò)能力直接相關(guān)2311.2.5譯碼準(zhǔn)則譯碼的目標(biāo)是使得譯碼輸出錯(cuò)誤的概率最小接收的碼字為ｒ，屬于碼字集合Ｒ，發(fā)送碼字為ci，屬于許用碼組集合Ｃ譯碼的任務(wù)就是根據(jù)ｒ判斷出發(fā)送端發(fā)送的是哪個(gè)碼字，并給出其估值最佳判決準(zhǔn)則--最大后驗(yàn)概率準(zhǔn)則解碼器找出使Ｐ(ｃｉ

/ｒ)最大的ci作為譯碼估值計(jì)算后驗(yàn)概率通常是比較困難最大似然(ＭＬ)準(zhǔn)則當(dāng)輸入信號(hào)等概率分布時(shí)，最大后驗(yàn)概率準(zhǔn)則等效為最大似然準(zhǔn)則找出使Ｐ(ｒ

/ｃｉ

)最大的ci作為譯碼估值，Ｐ(ｒ

/ｃｉ

)稱為似然函數(shù)實(shí)際信源輸出的碼字不一定等概率，但通過處理可以接近等概率由于ｌｎｘ是ｘ的單調(diào)函數(shù)，實(shí)際系統(tǒng)中通常采用使對(duì)數(shù)似然函數(shù)ｌｎＰ(ｒ

/ｃｉ)最大的ci作為譯碼估值2411.3線性分組碼25線性分組碼一個(gè)(ｎ,ｋ)的線性分組碼，既是分組碼，又是線性碼當(dāng)編碼符號(hào)是二進(jìn)制時(shí)，編碼是定義在二元域ＧＦ(２)上的碼字中的信息比特不發(fā)生變化的分組碼稱為系統(tǒng)碼，系統(tǒng)碼較非系統(tǒng)碼在實(shí)現(xiàn)上更為簡(jiǎn)便2611.3.1生成矩陣和校驗(yàn)矩陣通常系統(tǒng)碼可以采用下圖所示的結(jié)構(gòu)ｎ－ｋ個(gè)校驗(yàn)比特是ｋ個(gè)信息比特的線性和系數(shù)定義如下系數(shù)的選擇要使各校驗(yàn)等式是唯一的27生成矩陣和校驗(yàn)矩陣(續(xù))把碼字和信息以及校驗(yàn)用行矢量ｃ、ｍ和ｂ表示確定則校驗(yàn)比特的校驗(yàn)關(guān)系式可以用矩陣表示為其中，系數(shù)矩陣Ｐ是一個(gè)ｋ×(ｎ－ｋ)的矩陣則碼矢量，進(jìn)一步Ｉｋ是ｋ×ｋ的單位矩陣28生成矩陣和校驗(yàn)矩陣(續(xù))定義ｋ×ｎ的矩陣稱Ｇ為(ｎ,ｋ)線性分組碼的生成矩陣，則上式中，生成矩陣Ｇ包含一個(gè)ｋ階單位矩陣，它生成的碼是系統(tǒng)碼，這樣的生成矩陣Ｇ稱為生成矩陣的標(biāo)準(zhǔn)形式，簡(jiǎn)稱標(biāo)準(zhǔn)生成矩陣一般的生成矩陣通過初等變換可以轉(zhuǎn)化為標(biāo)準(zhǔn)生成矩陣生成矩陣的各行之間是線性獨(dú)立的式(１１.４)表示的一組校驗(yàn)關(guān)系可以改寫成用矩陣表示為(ｎ－ｋ)×ｎ的Ｈ矩陣定義為稱其為(ｎ,ｋ)線性分組碼的校驗(yàn)矩陣，也稱為監(jiān)督矩陣標(biāo)準(zhǔn)形式的生成矩陣和校驗(yàn)矩陣具有如下關(guān)系最小距離即矩陣ＨＴ中行求和為０的最小行數(shù)29例11.2已知一個(gè)(７,４)線性分組碼的校驗(yàn)矩陣為求其生成矩陣，求編碼器輸入為１００１時(shí)，編碼器的輸出碼字；分析該碼的糾檢錯(cuò)能力3031【解】先將給出的校驗(yàn)矩陣轉(zhuǎn)化為標(biāo)準(zhǔn)形式由校驗(yàn)矩陣的標(biāo)準(zhǔn)形式，得到生成矩陣

當(dāng)輸入序列是１００１時(shí)，可得在Ｈ矩陣的標(biāo)準(zhǔn)形式中，列１、２、４的和為零矢量，其他任意兩列的和都不為０，所以最小碼距等于３。因此該碼可以檢２位錯(cuò)誤，或者糾１位錯(cuò)誤11.3.2校正子和譯碼把信道干擾造成的錯(cuò)誤用矢量ｅ表示，稱為錯(cuò)誤圖樣或誤碼矢量ｅｉ(ｅ中第ｉ位)為１表示該位有錯(cuò)誤，為０表示無(wú)錯(cuò)誤則接收矢量ｒ可表示為定義接收端的校正子矢量為這個(gè)１×(ｎ－ｋ)的校正子矢量簡(jiǎn)稱校正子，又稱為接收矢量ｒ的伴隨式如果接收矢量ｒ

沒有錯(cuò)誤，等于發(fā)送矢量ｃ，則校正子為０。因此可以用校正子判斷接收矢量是否有誤碼32校正子性質(zhì)校正子由錯(cuò)誤圖樣決定，與發(fā)送的具體碼字無(wú)關(guān)校正子等于０，則判斷沒有誤碼所有許用碼字在同一個(gè)錯(cuò)誤圖樣下具有相同的校正子接收端譯碼時(shí)根據(jù)接收矢量ｒ和校驗(yàn)矩陣Ｈ計(jì)算出校正子ｓ，通過ｓ尋找對(duì)應(yīng)的錯(cuò)誤圖樣來(lái)完成譯碼。但是校正子有２ｎ－ｋ個(gè)，而錯(cuò)誤圖樣有２ｎ

個(gè)，因此存在多個(gè)錯(cuò)誤圖樣ｅ對(duì)應(yīng)一個(gè)校正子ｓ的情況，這時(shí)一般根據(jù)最小漢明距離譯碼準(zhǔn)則，選擇與接收碼字距離最小的碼字作為發(fā)送碼字的估值，即選取漢明重量最小的錯(cuò)誤圖樣33校正子譯碼(ｎ,ｋ)線性分組碼的２ｋ個(gè)許用碼字，在一個(gè)錯(cuò)誤圖樣ｅ下，得到的２ｋ個(gè)接收矢量，稱為一個(gè)陪集。則該碼共有２ｎ－ｋ個(gè)可能的陪集，每個(gè)陪集具有唯一的校正子對(duì)接收矢量按照陪集進(jìn)行劃分，得到

線性分組碼的標(biāo)準(zhǔn)陣列標(biāo)準(zhǔn)陣列中每一行是一個(gè)陪集，陪集的第一個(gè)元素

稱為陪集首每個(gè)陪集對(duì)應(yīng)一個(gè)校正子，陪集首按照最小漢明距離

準(zhǔn)則選擇校正子譯碼由接收碼矢量計(jì)算出校正子，根據(jù)校正子找到標(biāo)準(zhǔn)陣列中對(duì)應(yīng)的陪集并得到陪集首，用該陪集首和接收碼矢量相加，得到發(fā)送碼矢量的估值，即譯碼輸出34例11.3一個(gè)(５,２)線性分組碼具有如下參數(shù)分組長(zhǎng)度:ｎ＝５信息比特?cái)?shù):ｋ＝２校驗(yàn)比特?cái)?shù):ｎ－ｋ＝３其生成矩陣為求其校驗(yàn)矩陣、生成的碼字集合、標(biāo)準(zhǔn)陣列以及接收矢量為１０１００時(shí)的譯碼結(jié)果3536【解】可得其校驗(yàn)矩陣為信息分組共有４個(gè)，對(duì)應(yīng)的碼字如表

非零碼字的最小漢明重量是３，即最小碼距為３，因此只能糾正１位錯(cuò)誤37該碼的校正子共有２ｎ－ｋ＝８?jìng)€(gè)，含有一位錯(cuò)誤的錯(cuò)誤圖樣共有５個(gè)，可計(jì)算出這５個(gè)錯(cuò)誤圖樣對(duì)應(yīng)的校正子。剩下２個(gè)非零的校正子，分別是１１０和０１１，可以解出各自４個(gè)對(duì)應(yīng)的錯(cuò)誤圖樣，任選其中重量最小的錯(cuò)誤圖樣。這樣得到譯碼的標(biāo)準(zhǔn)陣列當(dāng)接收矢量為ｒ＝１０１００時(shí)，計(jì)算得到校正子ｓ＝１０１，查表得到其陪集首，即錯(cuò)誤圖樣為ｅ２

＝０００１０，故得譯碼輸出為ｒ＋ｅ２＝１０１１０

11.4循環(huán)碼38循環(huán)碼循環(huán)碼是線性分組碼的一個(gè)重要子類循環(huán)碼首先是線性分組碼，它具有線性特性具有循環(huán)性，即碼組中任一碼字經(jīng)循環(huán)移位后仍然在這個(gè)碼組中如果用來(lái)表示(ｎ,ｋ)循環(huán)碼的一個(gè)碼字，則下述所列舉的各循環(huán)移位的結(jié)果，仍然是該碼組中的一個(gè)碼字3911.4.1循環(huán)碼的多項(xiàng)式描述循環(huán)碼通常用多項(xiàng)式來(lái)描述對(duì)于任意一個(gè)碼字用多項(xiàng)式表示為稱ｃ(Ｘ)為碼字ｃ

的碼多項(xiàng)式，此多項(xiàng)式是系數(shù)定義在ＧＦ(２)上的多項(xiàng)式循環(huán)碼的循環(huán)移位特性可以用多項(xiàng)式表示式中ｉ表示右移的位數(shù)，ｍｏｄ表示取模運(yùn)算40例11.4(７,４)循環(huán)碼的碼字為１００１０１１，求其循環(huán)右移３位的碼字【解】該碼字表示成多項(xiàng)式，寫為

循環(huán)右移３位其中取模運(yùn)算使用多項(xiàng)式的長(zhǎng)除法，

所得的余式就是取模的結(jié)果余式為，對(duì)應(yīng)的碼字為０１１１００１41生成多項(xiàng)式取最高ｋ－１位都是０的碼多項(xiàng)式ｇ(Ｘ)，其最高次冪為ｎ－ｋ，根據(jù)循環(huán)碼特性，把ｇ(Ｘ)向右逐次移位，得到的多項(xiàng)式都是碼多項(xiàng)式，?。雮€(gè)這樣移位得到的多項(xiàng)式組成生成矩陣可見，ｇ(Ｘ)確定了碼的生成矩陣，因此能唯一確定一個(gè)循環(huán)碼，故稱ｇ(Ｘ)為碼的生成多項(xiàng)式42生成多項(xiàng)式(續(xù))循環(huán)碼中，生成多項(xiàng)式具有如下性質(zhì)ｇ(Ｘ)是碼多項(xiàng)式中常數(shù)項(xiàng)不為０的最低階的多項(xiàng)式，且是唯一的

ｎ－ｋ次多項(xiàng)式，可以寫成如下形式碼組中的每個(gè)碼多項(xiàng)式都可以表示為生成多項(xiàng)式ｇ(Ｘ)的倍式

ａ(Ｘ)是任一次冪不大于ｋ－１的多項(xiàng)式(ｎ,ｋ)循環(huán)碼的生成多項(xiàng)式ｇ(Ｘ)是ｘｎ＋１的一個(gè)ｎ－ｋ次因式43循環(huán)碼的編碼把信息序列表示成多項(xiàng)式ｍ(Ｘ)構(gòu)造系統(tǒng)碼，對(duì)信息序列右移ｎ－ｋ位校驗(yàn)序列用多項(xiàng)式表示為碼多項(xiàng)式可以表示為上兩式兩邊同時(shí)除以生成多項(xiàng)式ｇ(Ｘ)，得到可見，校驗(yàn)多項(xiàng)式ｂ(Ｘ)是Ｘｎ－ｋｍ(Ｘ)除以ｇ(Ｘ)的余式44循環(huán)碼的編碼(續(xù))系統(tǒng)碼形式循環(huán)碼的編碼步驟如下用Ｘｎ－ｋ乘信息多項(xiàng)式ｍ(Ｘ)，得到Ｘｎ－ｋｍ(Ｘ)用ｇ(Ｘ)除Ｘｎ－ｋｍ(Ｘ)，得到余式，即校驗(yàn)多項(xiàng)式ｂ(Ｘ)ｂ(Ｘ)和Ｘｎ－ｋｍ(Ｘ)相加，得到碼多項(xiàng)式ｃ(Ｘ)45校驗(yàn)多項(xiàng)式ｇ(Ｘ)是ｘｎ＋１的一個(gè)ｎ－ｋ次因式，則有其中ｈ(Ｘ)是和ｇ(Ｘ)對(duì)應(yīng)的一個(gè)ｋ階多項(xiàng)式，稱為碼的校驗(yàn)多項(xiàng)式，定義為定義校驗(yàn)多項(xiàng)式的反多項(xiàng)式，則校驗(yàn)矩陣可以表示為注意，這樣得到的生成矩陣和校驗(yàn)矩陣，都不是系統(tǒng)形式的，通過矩陣的初等變換，可以把它們轉(zhuǎn)換為系統(tǒng)形式46例11.5漢明碼是能糾正單個(gè)錯(cuò)誤的循環(huán)碼，其生成多項(xiàng)式是本原多項(xiàng)式。漢明碼具有如下參數(shù)碼長(zhǎng):ｎ＝２ｍ－１信息比特?cái)?shù):ｋ＝２ｍ－ｍ－１校驗(yàn)比特?cái)?shù):ｎ－ｋ＝ｍ其中，ｍ≥３。當(dāng)ｍ＝３時(shí)，得到(７,４)漢明碼。求其生成多項(xiàng)式、生成矩陣、校驗(yàn)矩陣，并計(jì)算其全部碼字【解】將Ｘｎ＋１分解因式，可以得到其生成多項(xiàng)式分解后，得到兩個(gè)３階本原多項(xiàng)式。這里選擇有了生成多項(xiàng)式，可以確定其生成矩陣取其系數(shù)，得到轉(zhuǎn)換后得到系統(tǒng)碼的生成矩陣

47根據(jù)校驗(yàn)多項(xiàng)式和生成多項(xiàng)式的關(guān)系，可得校驗(yàn)多項(xiàng)式校驗(yàn)多項(xiàng)式的反多項(xiàng)式由此可得校驗(yàn)矩陣，將其轉(zhuǎn)換為標(biāo)準(zhǔn)形式對(duì)信息序列１００１進(jìn)行編碼，可以采用矩陣相乘的方法

48也可以采用生成多項(xiàng)式的方法，把信息序列表示為多項(xiàng)式把ｍ(Ｘ)右移ｎ－ｋ位用Ｘｎ－ｋｍ(Ｘ)除以ｇ(Ｘ)得到余式則碼多項(xiàng)式為得到的碼字是０１１１００１該漢明碼的最小碼距是３，可以發(fā)現(xiàn)２位錯(cuò)誤或糾正１位錯(cuò)誤4911.4.2循環(huán)碼的編譯碼電路系統(tǒng)碼形式的循環(huán)碼的編碼電路50該編碼電路的主體是一個(gè)除法電路，由ｎ－ｋ級(jí)線性反饋移位寄存器構(gòu)成。圖中的觸發(fā)器具有０和１兩種狀態(tài)，其個(gè)數(shù)等于生成多項(xiàng)式ｇ(Ｘ)的階數(shù)。ｇｉ表示反饋連接，對(duì)應(yīng)于ｇ(Ｘ)的系數(shù)。該除法電路完全由ｇ(Ｘ)確定，用來(lái)完成將輸入序列除以ｇ(Ｘ)的功能。除法運(yùn)算所得的余式存儲(chǔ)在移位寄存器里編碼電路編碼電路的工作過程初始化，移位寄存器的初始狀態(tài)全部置０。輸出開關(guān)置于下方，門打開信息比特從右端進(jìn)入除法電路、同時(shí)輸出。從右端進(jìn)入，相當(dāng)于Ｘｎ－ｋｍ(Ｘ)除以ｇ(Ｘ)信息比特每進(jìn)入一位，除法電路反饋并更新狀態(tài)一次信息比特輸入完畢后，輸出開關(guān)轉(zhuǎn)到上方，門關(guān)閉。這時(shí)移位寄存器里保存的就是余式，即校驗(yàn)比特。由于門關(guān)閉，切斷了反饋，校驗(yàn)比特保持不變校驗(yàn)比特順次輸出，和前面輸出的信息比特共同構(gòu)成一個(gè)系統(tǒng)碼的碼字51譯碼電路譯碼主要步驟由接收到的碼矢量計(jì)算校正子根據(jù)校正子確定錯(cuò)誤圖樣將錯(cuò)誤圖樣和接收的碼字相加，糾正錯(cuò)誤計(jì)算校正子同樣用到除法電路，用接收碼矢量除以生成多項(xiàng)式ｇ(Ｘ)

把接收碼矢量用多項(xiàng)式表示為則定義ｅ(Ｘ)除以ｇ(Ｘ)的余式為校正子多項(xiàng)式，如下式。也稱為伴隨式52譯碼電路(續(xù))校正子計(jì)算電路解碼器計(jì)算出校正子后，接著就是尋找和校正子匹配的錯(cuò)誤圖樣。匹配過程通常用到校正子多項(xiàng)式的特性，主要有如果接收碼多項(xiàng)式ｒ(Ｘ)的校正子是ｓ(Ｘ)，那么，ｒ(Ｘ)循環(huán)移位后Ｘｒ(Ｘ)的校正子是Ｘｓ(Ｘ)。注意，Ｘｒ(Ｘ)使用時(shí)需要對(duì)Xｎ＋１取模，Ｘｓ(Ｘ)需要對(duì)ｇ(Ｘ)取模假如誤碼被限制為ｎ－ｋ個(gè)接收碼多項(xiàng)式ｒ(Ｘ)的奇偶校驗(yàn)比特，則校正子多項(xiàng)式ｓ(Ｘ)與錯(cuò)誤圖樣多項(xiàng)式ｅ(Ｘ)是相同的。這是由于生成多項(xiàng)式ｇ(Ｘ)是ｎ－ｋ階的，當(dāng)誤碼在碼多項(xiàng)式的校驗(yàn)比特區(qū)域時(shí)，錯(cuò)誤圖樣多項(xiàng)式ｅ(Ｘ)的階數(shù)小于等于ｎ－ｋ－１，因此ｅ(Ｘ)就等于ｓ(Ｘ)53例11.6對(duì)于例１１.４中的(７,４)漢明碼，當(dāng)生成多項(xiàng)式ｇ(Ｘ)＝１＋Ｘ＋Ｘ３

時(shí)，畫出其編碼電路和校正子計(jì)算電路【解】根據(jù)生成多項(xiàng)式和除法電路的關(guān)系，可得其編碼電路如圖其校正子計(jì)算電路如圖

5411.4.3常用循環(huán)碼介紹循環(huán)冗余校驗(yàn)碼簡(jiǎn)稱為ＣＲＣ碼，使用循環(huán)碼的生成多項(xiàng)式，可以生成系統(tǒng)碼，但數(shù)據(jù)位長(zhǎng)度可變，因此在傳輸ＣＲＣ碼前需要指示長(zhǎng)度具有較強(qiáng)的檢測(cè)誤碼能力，能夠檢測(cè)多種突發(fā)錯(cuò)誤、隨機(jī)錯(cuò)誤，以及組合錯(cuò)誤國(guó)際組織對(duì)一些常用的ＣＲＣ碼做了規(guī)范，給定了校驗(yàn)位長(zhǎng)度，指定了生成多項(xiàng)式ＢＣＨ碼是一類重要的循環(huán)碼，得名于３位發(fā)現(xiàn)者名字的首字母糾錯(cuò)能力強(qiáng)，能夠糾正ｔ個(gè)隨機(jī)錯(cuò)誤。具有嚴(yán)格的代數(shù)結(jié)構(gòu)，給定糾錯(cuò)個(gè)數(shù)ｔ后，就可以構(gòu)造出生成多項(xiàng)式，方便地實(shí)現(xiàn)編解碼ＢＣＨ碼分為兩類，本原ＢＣＨ碼和非本原ＢＣＨ碼如果生成多項(xiàng)式ｇ(Ｘ)中含有最高次冪為ｍ(ｍ≥３)的本原多項(xiàng)式，且碼長(zhǎng)ｎ＝２ｍ－１，則生成本原ＢＣＨ碼如果生成多項(xiàng)式中不含這種本原多項(xiàng)式，且碼長(zhǎng)是２ｍ－１的因子，則生成非本原ＢＣＨ碼漢明碼就是糾單個(gè)錯(cuò)誤的本原ＢＣＨ碼常采用查表法獲得ＢＣＨ碼的生成多項(xiàng)式55常用循環(huán)碼ＲＳ碼是一種多進(jìn)制ＢＣＨ碼，由其兩位發(fā)明人的名字命名碼元符號(hào)取自有限域ＧＦ(ｑ)，ｑ為某個(gè)素?cái)?shù)的冪。通常?。瘢剑玻?，ｍ>１糾ｔ個(gè)錯(cuò)誤的ｑ進(jìn)制的ＲＳ碼，有如下參數(shù)碼長(zhǎng):ｎ＝２ｍ－１個(gè)符號(hào)或ｍ(２ｍ－１)ｂｉｔ信息長(zhǎng)度:ｋ個(gè)符號(hào)或ｍｋｂｉｔ校驗(yàn)長(zhǎng)度:ｎ－ｋ＝２ｔ個(gè)符號(hào)或ｍ(ｎ－ｋ)＝２ｍｔｂｉｔ最小碼距:ｄｍｉｎ＝２ｔ＋１個(gè)符號(hào)或ｍ(２ｔ＋１)ｂｉｔ由于ＲＳ碼的碼元含有ｍｂｉｔ，因此具有很強(qiáng)的糾突發(fā)錯(cuò)誤的能力。在多進(jìn)制調(diào)制的場(chǎng)合，多進(jìn)制的ＲＳ碼更為適宜5611.5卷積碼5711.5卷積碼由伊利亞斯(Ｐ.Ｅｌｉａｓ)在１９５５年提出，是一種非分組碼信息比特是串行進(jìn)入編碼器的，通過模２卷積輸出一個(gè)長(zhǎng)為ｎ

的碼字校驗(yàn)比特不僅和本組的信息比特有關(guān)，還和前面Ｍ個(gè)時(shí)刻的信息有關(guān)，需要存儲(chǔ)前Ｍ個(gè)時(shí)刻的信息每個(gè)輸入信息將影響Ｋ＝Ｍ＋１個(gè)編碼輸出，Ｋ

稱為卷積碼的約束長(zhǎng)度通常把卷積碼表示為(ｎ,ｋ,Ｋ)卷積碼通常采用非系統(tǒng)碼結(jié)構(gòu)，其性能一般優(yōu)于分組碼58卷積碼(２,１,３)卷積碼編碼電路如圖兩級(jí)觸發(fā)器起到了存儲(chǔ)作用，編碼器輸出和３個(gè)時(shí)刻的輸入有關(guān)信息編碼器工作時(shí)信息序列連續(xù)輸入，因此卷積碼比較適宜連續(xù)信息流的場(chǎng)景，編碼輸出是一個(gè)近似無(wú)限長(zhǎng)的序列當(dāng)一組信息序列編碼完成后，編碼器的Ｍ個(gè)觸發(fā)器里仍然存有信息，因此通常額外再輸入Ｍ個(gè)全０數(shù)據(jù)，使得觸發(fā)器里的信息能夠輸出，同時(shí)把編碼器恢復(fù)到全０狀態(tài)。這一階段的編碼輸出稱為編碼尾5911.5.1卷積碼的解析描述本節(jié)主要討論ｋ＝１的情況用單位時(shí)延變量多項(xiàng)式來(lái)表示編碼器各個(gè)輸出支路的生成多項(xiàng)式每個(gè)支路的輸出特性，可以用該支路移位寄存器初始化為０后的沖激響應(yīng)來(lái)表示沖激響應(yīng)就是該支路輸入為１時(shí)的響應(yīng)用ｇｉ(Ｄ)表示第ｉ支路的沖激響應(yīng)，啞元Ｄ表示單位時(shí)延變量定義第ｉ支路的生成多項(xiàng)式為式中Ｍ表示時(shí)延，系數(shù)等于０或１60卷積碼的解析描述如編碼器的輸入信息序列為ｍ０,ｍ１,ｍ２,…，則輸入多項(xiàng)式為編碼器各個(gè)支路的輸出是輸入信息序列和該支路生成多項(xiàng)式的離散卷積根據(jù)傅里葉變換，時(shí)域的卷積可以轉(zhuǎn)化為Ｄ域的乘積。因此第ｉ路的輸出可以表示為編碼器的輸出由各個(gè)支路的輸出復(fù)接得到。正因?yàn)榫幋a器的輸出是輸入信息序列和編碼器沖激響應(yīng)的卷積，所以被稱為卷積碼61例11.7一個(gè)(２,１,３)卷積碼編碼電路如圖１１.１１所示。寫出它的生成多項(xiàng)式，并計(jì)算輸入信息序列為１０１１１時(shí)的編碼輸出【解】其上支路的沖激響應(yīng)是(１,１,１)，相應(yīng)的生成多項(xiàng)式是下支路的沖激響應(yīng)是(１,０,１)，對(duì)應(yīng)的生成多項(xiàng)式是輸入序列１０１１１對(duì)應(yīng)的信息多項(xiàng)式是上支路的編碼輸出下支路的編碼輸出上支路的輸出為１１００１０１，下支路的輸出為１００１０１１。兩個(gè)支路的輸出復(fù)接后，得到的編碼輸出序列為注意，輸入信息序列是５ｂｉｔ，輸出是７×２＝１４ｂｉｔ，多出的２組(４ｂｉｔ)就是編碼尾62編碼效率當(dāng)輸入信息序列長(zhǎng)度為Ｌ

時(shí)，(ｎ,１,Ｋ)卷積碼編碼輸出的長(zhǎng)度是

ｎ(Ｌ＋Ｋ－１)ｂｉｔ。定義編碼效率ｒ

為編碼效率簡(jiǎn)稱碼率。當(dāng)Ｌ遠(yuǎn)大于Ｋ

時(shí)，碼率通常定義為6311.5.2卷積碼的圖形描述卷積碼常用的圖形描述，有碼樹、網(wǎng)格圖和狀態(tài)圖以圖１１.１１所示的(２,１,３)卷積碼編碼器為例，為了方便描述，對(duì)編碼器的狀態(tài)進(jìn)行命名當(dāng)編碼器的觸發(fā)器個(gè)數(shù)為Ｍ

時(shí)，編碼器共有２Ｍ個(gè)狀態(tài)64碼樹碼樹可以動(dòng)態(tài)地描述輸入序列對(duì)應(yīng)的編碼過程碼樹中節(jié)點(diǎn)表示狀態(tài)，初始狀態(tài)ａ是根節(jié)點(diǎn)輸入比特０時(shí)碼樹分支向上，輸入比特１時(shí)碼樹分

支向下每輸入１ｂｉｔ后，編碼器的后續(xù)狀態(tài)是下一個(gè)節(jié)

點(diǎn)，編碼器此時(shí)的輸出標(biāo)記在相應(yīng)的橫枝上經(jīng)過分支個(gè)數(shù)等于約束長(zhǎng)度Ｋ

后，碼樹開始重復(fù)圖例中，當(dāng)輸入序列為１０１１１時(shí)，碼樹的狀態(tài)變化為ａ,ｂ,ｃ,ｂ,ｄ，根據(jù)相應(yīng)分支上的輸出，對(duì)應(yīng)編碼為１１,１０,００,０１,１０。根據(jù)編碼規(guī)則，還需額外輸入兩個(gè)０得到編碼尾，對(duì)應(yīng)的狀態(tài)變化是ｃ,ａ，輸出是０１,１１65網(wǎng)格圖把碼樹在時(shí)間節(jié)點(diǎn)上狀態(tài)相同的分支合并，則得到網(wǎng)格圖每一行上的節(jié)點(diǎn)都代表同一個(gè)狀態(tài)每個(gè)狀態(tài)輸入０后的輸出分支用實(shí)

線表示，輸入１后的分支用虛線表

示

相應(yīng)的輸出比特標(biāo)記在分支上網(wǎng)格圖的橫向表示時(shí)間變化，每單

位時(shí)間輸入１ｂｉｔ信息，輸入序列

的編碼過程體現(xiàn)為網(wǎng)格圖中的一條路徑經(jīng)過約束長(zhǎng)度Ｋ個(gè)時(shí)間單位后，網(wǎng)格圖進(jìn)入穩(wěn)定狀態(tài)。后面開始重復(fù)此狀態(tài)。在此(２,１,３)卷積碼下，穩(wěn)定狀態(tài)時(shí)網(wǎng)格圖每個(gè)節(jié)點(diǎn)都有兩路輸出、兩路輸入66狀態(tài)圖網(wǎng)格圖在穩(wěn)定狀態(tài)下的一節(jié)網(wǎng)格，包含了全部編碼器狀態(tài)以及這些狀態(tài)之間的轉(zhuǎn)換關(guān)系。把這節(jié)網(wǎng)格里相同的狀態(tài)合并，即可得到編碼器的狀態(tài)圖實(shí)線表示的分支是輸入為０的結(jié)果虛線表示的分支是輸入為１的結(jié)果

相應(yīng)的輸出比特標(biāo)記在分支上更簡(jiǎn)潔，但不能表示狀態(tài)轉(zhuǎn)移和時(shí)間之間的關(guān)系6711.5.3卷積碼的譯碼譯碼方法上先后出現(xiàn)了序列譯碼、門限譯碼、維特比譯碼等最小距離譯碼準(zhǔn)則在二進(jìn)制對(duì)稱信道下，卷積碼的發(fā)送碼矢量ｃ的長(zhǎng)度如果用Ｎ表示，接收矢量ｒ的長(zhǎng)度也為Ｎ，則有取對(duì)數(shù)，得到對(duì)數(shù)似然函數(shù)比特錯(cuò)誤傳輸概率為ｐ，正確傳輸概率為１－ｐ。假定接收矢量ｒ和發(fā)送碼矢量ｃ之間總共有ｄｂｉｔ不同，則最大似然譯碼準(zhǔn)則要求上面的對(duì)數(shù)似然函數(shù)最大，二進(jìn)制對(duì)稱信道的參數(shù)ｐ是確定的，通常錯(cuò)誤概率ｐ<１/２，上式右邊兩項(xiàng)中第一項(xiàng)為負(fù)值，因此對(duì)數(shù)似然函數(shù)最大等效于參數(shù)ｄ最小即在二進(jìn)制對(duì)稱信道下，最大似然譯碼等效為最小距離譯碼68維特比譯碼算法問題：以(ｎ,１,Ｋ)卷積碼為例，假定發(fā)送的碼矢量長(zhǎng)度為Ｌｂｉｔ，則接收端收到碼矢量后進(jìn)行最小距離譯碼，需要和２Ｌ個(gè)可能的碼矢量進(jìn)行比較，當(dāng)Ｌ較大時(shí)，計(jì)算量巨大解決方案：維特比譯碼算法利用網(wǎng)格圖，該算法在網(wǎng)格圖中尋找一條和接收矢量距離最小的路徑作為譯碼路徑，但它不是一次比較所有可能的路徑，而是采用分段計(jì)算的方法，極大地縮減了計(jì)算量部分說(shuō)明接收矢量和某個(gè)可能編碼路徑的漢明距離等于它們?cè)诟鱾€(gè)時(shí)間節(jié)點(diǎn)對(duì)應(yīng)的分支上的漢明距離的和把分支上的漢明距離稱為這個(gè)分支的分支度量，則一條編碼路徑的度量值是其分支度量的和，稱為累計(jì)度量在ｊ時(shí)刻連接到某一狀態(tài)的編碼路徑有多條時(shí)，選擇累計(jì)度量值最小的那個(gè)保留下來(lái)，稱為留存路徑留存路徑是和接收矢量漢明距離最小的編碼路徑，非留存路徑不再保留，將被舍棄69維特比譯碼算法(續(xù))維特比譯碼算法描述如下ｊ＝０時(shí)，將累計(jì)度量初始化為０，初始節(jié)點(diǎn)為編碼器的初始狀態(tài)從ｊ＝１時(shí)刻開始，計(jì)算該時(shí)鐘時(shí)間內(nèi)各個(gè)分支度量，并和前面的累計(jì)度量相加得到新的累計(jì)度量。每個(gè)狀態(tài)比較到達(dá)該狀態(tài)的所有編碼路徑，當(dāng)編碼路徑不止一個(gè)時(shí)，選擇并保留留存路徑，存儲(chǔ)每個(gè)狀態(tài)的留存路徑及其累計(jì)度量ｊ增加１，重復(fù)步驟(２)，每次網(wǎng)格圖向后計(jì)算一個(gè)時(shí)刻，直到對(duì)接收序列計(jì)算完畢。最后的留存路徑就是判決結(jié)果由于(ｎ,１,Ｋ)卷積碼狀態(tài)總數(shù)是２Ｋ－１

，因此留存路徑的個(gè)數(shù)不超過２Ｋ－１維特比算法在每一步里的計(jì)算量是有限的70例11.8如圖１１.１１所示(２,１,３)卷積碼編碼器，輸入信息序列為１０１１，發(fā)送序列是１１,１０,００,０１,０１,１１，如果接收序列是１１,１１,００,００,０１,１１，試用維特比算法給出接收序列的譯碼【解】利用網(wǎng)格圖，使用維特比譯碼算法ｊ＝０時(shí)，初始化累計(jì)度量為０，初始狀態(tài)為ａｊ＝１時(shí)，接收序列是１１，此時(shí)刻有２個(gè)狀態(tài)，每個(gè)狀態(tài)有一個(gè)輸入分支，對(duì)應(yīng)的分支度量分別是２，０。分支度量加上前一時(shí)刻對(duì)應(yīng)狀態(tài)的累計(jì)度量，得到新的累計(jì)度量。此步驟每個(gè)狀態(tài)只有１輸入分支，不需要選擇留存路徑ｊ

＝２時(shí)，和前面類似，不需要選擇留存路徑。此步驟結(jié)束時(shí)有４個(gè)狀態(tài)，各對(duì)應(yīng)一條編碼路徑ｊ

＝３時(shí)，有４個(gè)狀態(tài)，各自有２條輸入路徑，計(jì)算分支度量和累計(jì)度量后，狀態(tài)ａ有２條輸入路徑，累計(jì)度量分別是４和３，選擇３對(duì)應(yīng)的編碼路徑作為狀態(tài)ａ的留存路徑；同樣，狀態(tài)ｂ選擇累計(jì)度量為１的編碼路徑；狀態(tài)ｃ選擇累計(jì)度量為２的編碼路徑；狀態(tài)ｄ選擇累計(jì)度量為２的編碼路徑接收序列計(jì)算完畢后，只剩余一條留存路徑，如圖所示，其路徑可以由狀態(tài)變化表示為ａｂｃｂｄｃａ，累計(jì)度量是２這條路徑作為譯碼輸出，即發(fā)送碼序列的估值１１,１０,００,０１,０１,１１。根據(jù)網(wǎng)格圖，可以得到其對(duì)應(yīng)的信息序列是１０１１此例中，維特比算法糾正了接收序列里２ｂｉｔ的錯(cuò)誤71例11.87211.5.4卷積碼的糾錯(cuò)能力卷積碼的糾錯(cuò)能力取決于碼的自由距離ｄｆｒｅｅ自由距離定義為任意兩個(gè)碼字間的漢明距離，以網(wǎng)格圖為例，即一個(gè)卷積碼的自由距離等于全零路徑與從０狀態(tài)重新回到０狀態(tài)的最小非零路徑之間的路徑度量之差要糾正ｔ個(gè)誤碼，ｄｆｒｅｅ必須大于２ｔ卷積碼的自由距離可以從信號(hào)流圖中求得以圖１１.１４所示的(２,１,３)卷積碼的狀態(tài)圖為例，把分支上的輸出比特序列標(biāo)記轉(zhuǎn)換成Ｄｉ

Ｌ，ｉ表示該分支上１的個(gè)數(shù)，即分支上輸出序列和全零序列的漢明距離，Ｌ

表示分支長(zhǎng)度，這里為１。把節(jié)點(diǎn)ａ分成兩個(gè)節(jié)點(diǎn)，ａ

表示狀態(tài)圖的輸入，ｅ

表示輸出。這樣得到卷積碼的信號(hào)流圖由信號(hào)流圖，可得其狀態(tài)方程定義轉(zhuǎn)移函數(shù)為ｅ和ａ的比值，

由上面方程組得到令Ｌ＝１，將上式按二項(xiàng)式展開上式第一項(xiàng)的指數(shù)就是碼的自由距離。該碼的自由距離等于５，可以糾正２個(gè)錯(cuò)誤上式假定Ｔ(Ｄ,１)中單位時(shí)延變量Ｄ的冪級(jí)數(shù)是收斂的，否則有限的誤碼會(huì)導(dǎo)致無(wú)限的譯碼錯(cuò)誤。這樣的卷積碼稱為惡性碼。7311.5.5遞歸系統(tǒng)卷積碼系統(tǒng)卷積碼不會(huì)是惡性碼，但其自由距離通常小于非系統(tǒng)碼遞歸系統(tǒng)卷積碼(ＲＳＣ)兼有非系統(tǒng)碼的自由距離特性和系統(tǒng)碼的安全性編碼器中遞歸將一個(gè)或多個(gè)移位寄存器抽頭的輸出反饋到輸入，使得編碼器的輸出前后關(guān)聯(lián)，可以獲得更好的系統(tǒng)性能74例11.9假設(shè)一個(gè)ＲＳＣ碼的生成多項(xiàng)式如下，式中Ｄ是單位時(shí)延變量畫出其編碼器結(jié)構(gòu)【解】生成多項(xiàng)式矩陣ｇ(Ｄ)的第一項(xiàng)１表明其是系統(tǒng)碼，第二項(xiàng)是反饋移位寄存器的轉(zhuǎn)移函數(shù)，定義為輸出多項(xiàng)式除以輸入多項(xiàng)式。對(duì)應(yīng)的編碼器如圖7511.6網(wǎng)格編碼調(diào)制76網(wǎng)格編碼調(diào)制常用的信道編碼方法，降低了帶寬利用率在帶寬受限的應(yīng)用場(chǎng)景中，如衛(wèi)星、太空、微波、雙絞線、同軸等通信系統(tǒng)，需要一種不降低帶寬利用率的編碼方案網(wǎng)格編碼調(diào)制(ＴＣＭ)，將編碼和調(diào)制作為一個(gè)整體來(lái)設(shè)計(jì)，利用信號(hào)點(diǎn)的冗余來(lái)獲得抗干擾性能，能更有效地利用帶寬和功率。其特征如下在調(diào)制星座圖中使用信號(hào)點(diǎn)的個(gè)數(shù)大于相同速率下該調(diào)制方式所需的信號(hào)點(diǎn)個(gè)數(shù)。因此在不擴(kuò)大帶寬的情況下，多余的信號(hào)點(diǎn)帶來(lái)了冗余，可用于糾錯(cuò)信號(hào)點(diǎn)之間通過卷積碼提供關(guān)聯(lián)，使得只有某些信號(hào)點(diǎn)序列允許出現(xiàn)信號(hào)點(diǎn)代表某個(gè)確定相位的已調(diào)信號(hào)波形，接收端將這些波形映射為網(wǎng)格圖，可以使用維特比算法，將解調(diào)和解碼作為整體一次性完成7711.6.1歐氏距離和信號(hào)空間劃分調(diào)制信號(hào)的糾錯(cuò)能力主要取決于已調(diào)信號(hào)在信號(hào)空間中的歐氏距離傳統(tǒng)調(diào)制方式中，除了二進(jìn)制ＰＳＫ和ＱＰＳＫ，歐氏距離的最大化不等同于漢明距離的最大化以８ＰＳＫ調(diào)制信號(hào)的星座圖為例如果恰當(dāng)選擇，最小歐氏距離可以達(dá)到ｄ３網(wǎng)格編碼調(diào)制把調(diào)制和編碼相結(jié)合，

使得編碼符號(hào)映射到信號(hào)空間點(diǎn)集

時(shí)，信號(hào)點(diǎn)之間具有最大的最小歐

氏距離，這可以通過對(duì)信號(hào)空間點(diǎn)

的劃分來(lái)實(shí)現(xiàn)7811.6.2網(wǎng)格編碼調(diào)制器的結(jié)構(gòu)和實(shí)例網(wǎng)格編碼調(diào)制器的一般結(jié)構(gòu)如圖部分信息比特經(jīng)過卷積碼編碼，編碼后的比特用于選擇劃分過的調(diào)制信號(hào)空間點(diǎn)的子集；剩余的部分信息比特直接選擇子集中的信號(hào)點(diǎn)。這樣保證了發(fā)送信號(hào)序列中信號(hào)間歐氏距離的最大化一個(gè)８ＰＳＫ網(wǎng)格編碼調(diào)制實(shí)例每個(gè)調(diào)制符號(hào)傳輸兩比特信息，使用碼率為１/２的卷積碼79網(wǎng)格編碼調(diào)制器的結(jié)構(gòu)和實(shí)例(續(xù))該例中用擁有傳輸３ｂｉｔ信息能力的８ＰＳＫ調(diào)制來(lái)傳輸２ｂｉｔ信息，通過在信號(hào)空間中引入冗余信息來(lái)獲得糾錯(cuò)能力例子中使用的卷積碼有兩級(jí)觸發(fā)器，狀態(tài)數(shù)是４，可以制作出信號(hào)的網(wǎng)格圖從一個(gè)狀態(tài)轉(zhuǎn)化為另一個(gè)狀態(tài)的路徑存在兩條，并不唯一，這一特性稱為并行轉(zhuǎn)移。并行轉(zhuǎn)移是因?yàn)榇嬖冢保猓椋粑淳幋a信息，網(wǎng)格圖分支上輸出的前１ｂｉｔ就是這個(gè)未編碼比特接收端檢測(cè)的第一步就是確定每個(gè)子集中距離接收信號(hào)點(diǎn)最近的信號(hào)點(diǎn)，然后分支量度計(jì)算信號(hào)點(diǎn)與接收信號(hào)點(diǎn)之間的歐氏平方距離，再執(zhí)行維特比算法使用了擴(kuò)展的星座圖，在固定信噪比的情況下，平均符號(hào)差錯(cuò)概率會(huì)增加，因此采用軟判決譯碼8011.6.3漸近編碼增益編碼增益表示在誤碼率一定的條件下非編碼系統(tǒng)與編碼系統(tǒng)輸入信噪比的差值(用ｄＢ表示)編碼增益描述了采用了糾錯(cuò)編碼之后，對(duì)原先非編碼系統(tǒng)的性能改善程度通常把系統(tǒng)在高信噪比時(shí)所獲得的編碼增益稱為漸近編碼增益網(wǎng)格編碼調(diào)制系統(tǒng)的漸近編碼增益定義為ｄｆｒｅｅ是自由歐氏距離，指編碼后允許信號(hào)星座圖子集中信號(hào)之間的最小歐氏距離；ｄｒｅｆ是具有相同信號(hào)能量的未編碼調(diào)制系統(tǒng)的最小歐氏距離以８ＰＳＫ的網(wǎng)格編碼調(diào)制為例，ｄｆｒｅｅ值為2，對(duì)應(yīng)的未編碼系統(tǒng)采用ＱＰＳＫ調(diào)制，其ｄｒｅｆ如圖１１.１４中的ｄ１所示，值為，計(jì)算出此時(shí)漸近編碼增益為３ｄＢ在工程實(shí)踐中，網(wǎng)格編碼調(diào)制的編碼增益在３ｄＢ~６ｄＢ8111.7先進(jìn)信道編碼技術(shù)82先進(jìn)信道編碼技術(shù)分組碼和卷積碼，這些傳統(tǒng)的編碼為了接近香農(nóng)信道容量的理論極限，需要增加線性分組碼碼字的長(zhǎng)度或增加卷積碼的約束長(zhǎng)度，實(shí)現(xiàn)困難尋找構(gòu)造具有大“等效”分組長(zhǎng)度的有效編碼方法，以既能夠接近香農(nóng)限，又能相對(duì)簡(jiǎn)便地實(shí)現(xiàn)編解碼Ｔｕｒｂｏ碼和ＬＤＰＣ碼，共同特點(diǎn)是碼長(zhǎng)長(zhǎng)、接近于香農(nóng)限、編解碼易于實(shí)現(xiàn)極化碼是一種被嚴(yán)格證明達(dá)到香農(nóng)限的信道編碼方法，具有明確且簡(jiǎn)單的編解碼算法，其性能超過ＬＤＰＣ碼和Ｔｕｒｂｏ碼8311.7.1Ｔｕｒｂｏ碼1993年提出，是一種并行級(jí)聯(lián)碼，采用兩個(gè)并聯(lián)的編碼器和一個(gè)交織器，具有很大的分組長(zhǎng)度，譯碼時(shí)使用兩個(gè)分量碼解碼器，相互迭代譯碼，過程類似渦輪結(jié)構(gòu)，因此被稱為Ｔｕｒｂｏ碼編碼器結(jié)構(gòu)如圖編碼器１和編碼器２都是系統(tǒng)碼編碼器，可以相同，也可以不同交織器對(duì)輸入信息起到存儲(chǔ)、交織的作用Ｔｕｒｂｏ碼常使用偽隨機(jī)交織器，由偽隨機(jī)序列控制數(shù)據(jù)在交織器中的讀寫位置交織使數(shù)據(jù)隨機(jī)化，改變數(shù)據(jù)的碼重分布84Ｔｕｒｂｏ碼(續(xù))兩個(gè)編碼器，推薦使用ＲＳＣ碼ＲＳＣ碼移位寄存器的內(nèi)部狀態(tài)與它過去的輸出有關(guān)，這會(huì)影響到錯(cuò)誤圖樣的狀態(tài)，能夠獲得更好的編碼性能由于使用了交織器，Ｔｕｒｂｏ碼可以看作分組碼，分組長(zhǎng)度取決于交織器的長(zhǎng)度。Ｔｕｒｂｏ碼使用的交織器長(zhǎng)度通常很大，可以看作碼長(zhǎng)很大的分組碼由于偽隨機(jī)交織器的優(yōu)點(diǎn)，Ｔｕｒｂｏ碼在信道傳輸時(shí)表現(xiàn)出隨機(jī)的特性對(duì)長(zhǎng)碼進(jìn)行譯碼時(shí)，如使用最大似然譯碼，需要比較的碼字序列數(shù)量巨大，難以實(shí)現(xiàn)。Ｔｕｒｂｏ碼提出了迭代譯碼的思想，降低了復(fù)雜度85Ｔｕｒｂｏ碼的譯碼解碼器有兩個(gè)解碼器單元兩個(gè)解碼器單元可以采用并行級(jí)聯(lián)方式，也可以采用串行級(jí)聯(lián)方式采用并行級(jí)聯(lián)的Ｔｕｒｂｏ碼解碼器結(jié)構(gòu)如圖兩個(gè)獨(dú)立的子解碼器都使用軟輸入軟輸出(ＳＩＳＯ)的迭代譯碼算法每次迭代都有３路輸入，除了信息位和相應(yīng)的校驗(yàn)位外，還有一路來(lái)自另一個(gè)解碼器的輸出，稱之為外信息外信息對(duì)子解碼器的譯碼起到參考作用，它使得該解碼器的輸入信息量增加，提高了譯碼的正確性每個(gè)子解碼器的輸出均是軟輸出，不僅包含本次譯碼輸出的估值，還包含用似然度表示的這些估值的可信程度86Ｔｕｒｂｏ碼的譯碼(續(xù))由于外信息的存在，一個(gè)子解碼器的軟輸出作為另一個(gè)子解碼器的外信息輸入，使得兩個(gè)子解碼器能夠迭代譯碼，直到給出譯碼結(jié)果或者預(yù)設(shè)的迭代次數(shù)耗盡兩個(gè)子解碼器使用的軟輸入軟輸出算法有最大后驗(yàn)概率(ＭＡＰ)算法、軟輸出維特比算法(ＳＯＶＡ)等。其中以ＢＣＪＲ算法為代表的ＭＡＰ算法應(yīng)用最廣泛無(wú)論是在ＡＷＧＮ信道還是在衰落信道中，Ｔｕｒｂｏ碼都體現(xiàn)出良好的性能，具有接近香農(nóng)限的糾錯(cuò)能力8711.7.2ＬＤＰＣ碼低密度奇偶校驗(yàn)(ＬＤＰＣ)碼是另一種接近香農(nóng)限的信道編碼方法和Ｔｕｒｂｏ碼相比，ＬＤＰＣ碼具有更強(qiáng)的糾錯(cuò)能力，更接近香農(nóng)限，同時(shí)在譯碼上比Ｔｕｒｂｏ碼簡(jiǎn)單ＬＤＰＣ碼是碼長(zhǎng)非常大的線性分組碼普通的線性分組碼在碼長(zhǎng)很大時(shí)會(huì)導(dǎo)致譯碼復(fù)雜度令人難以接受ＬＤＰＣ碼不同，其特殊之處在于校驗(yàn)矩陣Ｈ屬于稀疏矩陣，其中１的個(gè)數(shù)很少，或者說(shuō)１的密度很低根據(jù)校驗(yàn)矩陣Ｈ的類型，ＬＤＰＣ分為兩類如果Ｈ中各行和各列都有相同的重量，即１的個(gè)數(shù)相同，這樣的碼稱為規(guī)則ＬＤＰＣ碼否則稱為非規(guī)則ＬＤＰＣ碼，非規(guī)則ＬＤＰＣ碼比規(guī)則ＬＤＰＣ碼性能更好88ＬＤＰＣ碼規(guī)則ＬＤＰＣ碼的校驗(yàn)矩陣Ｈ常用(ｎ,ｔｃ

,ｔｒ

)表示ｎ

表示分組的碼長(zhǎng)，ｔｃ表示矩陣各列中１的個(gè)數(shù)，ｔｒ表示矩陣各行中１的個(gè)數(shù)，ｔｃ、ｔｒ都遠(yuǎn)小于ｎ通常用二分圖表示ＬＤＰＣ碼的結(jié)構(gòu)，二分圖是校驗(yàn)矩陣的圖形化描述以(１０,３,５)ＬＤＰＣ碼為例，其校驗(yàn)矩陣和二分圖如圖變量節(jié)點(diǎn)，代表碼字中的每個(gè)比特校驗(yàn)節(jié)點(diǎn)，代表校驗(yàn)方程Ｈ中的每一行就是一個(gè)校驗(yàn)節(jié)點(diǎn)，每一列就是一個(gè)變量節(jié)點(diǎn)節(jié)點(diǎn)間的連線表示碼字比特和校驗(yàn)方程的關(guān)系，稱為二分圖的邊校驗(yàn)矩陣可以通過計(jì)算機(jī)搜索獲得，但是通常是按照一定的結(jié)構(gòu)和規(guī)則來(lái)設(shè)計(jì)89ＬＤＰＣ碼的譯碼譯碼時(shí)使用迭代的算法，常用的算法有消息傳遞(ＭＰ)算法和置信傳播(ＢＰ)算法這些算法利用二分圖，在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間傳遞可靠性信息，反復(fù)迭代，完成譯碼運(yùn)算普通的線性分組碼在碼長(zhǎng)很大時(shí)，二分圖十分復(fù)雜，難以使用上述譯碼方法ＬＤＰＣ碼由于校驗(yàn)矩陣Ｈ的稀疏特性，使得算法復(fù)雜度大幅降低，其實(shí)際譯碼復(fù)雜度低于Ｔｕｒｂｏ碼ＬＤＰＣ碼性能優(yōu)異，比Ｔｕｒｂｏ碼更接近香農(nóng)限，譯碼實(shí)現(xiàn)相對(duì)簡(jiǎn)易9011.7.3Ｐｏｌａｒ碼２００９年提出，是目前唯一一種被證明在二進(jìn)制刪除信道(ＢＥＣ)和二進(jìn)制離散無(wú)記憶信道(Ｂ-ＤＭＣ)下能夠達(dá)到香農(nóng)限的信道編碼方法Ｐｏｌａｒ碼的理論基礎(chǔ)是信道極化信道極化由信道合并和信道分裂組成如一個(gè)Ｂ－ＤＭＣ信道Ｗ，被重復(fù)使用Ｎ

次，經(jīng)線性變換合并成ＷＮ，合并信道經(jīng)過分裂轉(zhuǎn)化為Ｎ個(gè)相互關(guān)聯(lián)的子信道ＷＮ(ｉ)當(dāng)Ｎ足夠大時(shí)，會(huì)出現(xiàn)部分子信道的信道容量趨于１，剩余部分子信道的信道容量趨于０的現(xiàn)象，即出現(xiàn)無(wú)噪信道和全噪信道，這種現(xiàn)象稱為信道極化Ｐｏｌａｒ碼選擇Ｋ個(gè)無(wú)噪信道傳輸信息比特，在剩余Ｎ－Ｋ個(gè)全噪信道上傳輸凍結(jié)比特(通常置為０)，即可實(shí)現(xiàn)碼率為Ｋ

/Ｎ的編碼91Ｐｏｌａｒ碼考慮碼長(zhǎng)Ｎ是２的冪，即Ｎ＝２ｎ

，ｎ≥０，Ｐｏｌａｒ碼的編碼可以表示為ｘ表示編碼后的比特，ｕ

表示待編碼信息比特，ＧＮ

是生成矩陣可見，Ｐｏｌａｒ碼是線性分組碼令Ａ為{１,…,Ｎ}的一個(gè)子集，元素個(gè)數(shù)為Ｋ，表示ＧＮ中傳輸信息的行的標(biāo)