信道編碼新進(jìn)展簡(jiǎn)介-2014

信道編碼新進(jìn)展簡(jiǎn)介背景移動(dòng)通信、衛(wèi)星通信、無(wú)線互聯(lián)網(wǎng)的快速發(fā)展無(wú)線城域網(wǎng)（WMAN，WirelessMetropolitanAreaNetwork） 無(wú)線局域網(wǎng)（WLAN，WirelessLocalArea） 無(wú)線個(gè)域網(wǎng)（WPAN，WirelessPersonalAreaNetwork） 無(wú)線傳感器網(wǎng)絡(luò)（WSN，WirelessSensorNetwork） 物聯(lián)網(wǎng)（IoT，InternetofThings） 無(wú)線自組織網(wǎng)絡(luò)（WAN，WirelessAdHocNetwork）新概念的提出及推廣使用，使信息論的研究工作逐漸轉(zhuǎn)向網(wǎng)絡(luò)信息理論領(lǐng)域，以解決復(fù)雜電磁環(huán)境中寬帶和多媒體通信所面臨的理論問(wèn)題。信息理論與編碼基礎(chǔ)背景本章僅對(duì)Turbo碼、空時(shí)編碼（STC，SpaceTimeCoding）、低密度奇偶校驗(yàn)碼（LDPC，LowDensityParityCheck）碼以及網(wǎng)絡(luò)編碼與協(xié)作進(jìn)行簡(jiǎn)要討論。信息理論與編碼基礎(chǔ)本章內(nèi)容提要10.1Turbo碼10.1.1Turbo碼的編碼及其性能10.1.2Turbo碼的譯碼簡(jiǎn)介10.2空時(shí)分組碼10.2.1正交空時(shí)分組碼10.2.2正交空時(shí)分組碼的譯碼10.2.3準(zhǔn)正交空時(shí)分組碼10.2.4準(zhǔn)正交空時(shí)分組碼的譯碼10.3低密度奇偶校驗(yàn)碼10.3.1低密度奇偶校驗(yàn)碼的定義10.3.2低密度奇偶校驗(yàn)碼的譯碼10.4網(wǎng)絡(luò)編碼與協(xié)作10.4.1網(wǎng)絡(luò)編碼10.4.2網(wǎng)絡(luò)編碼協(xié)作Turbo碼10.1Turbo碼在傳統(tǒng)的編碼方式中，通常通過(guò)構(gòu)造大量代數(shù)結(jié)構(gòu)的碼來(lái)選擇出一個(gè)好碼。但是，這種結(jié)構(gòu)設(shè)計(jì)方法的缺點(diǎn)是，為了盡量接近香農(nóng)信道容量的理論極限，要求增加線性分組碼碼字的長(zhǎng)度或增加卷積碼的約束長(zhǎng)度，從而導(dǎo)致最大似然估計(jì)譯碼器的計(jì)算復(fù)雜度隨碼字長(zhǎng)度增加按指數(shù)增加，這又使得在實(shí)際應(yīng)用中譯碼器難以實(shí)現(xiàn)。10.1Turbo碼各種構(gòu)造具有較大“等效”分組長(zhǎng)度的編碼方法運(yùn)用而生。這些方法的基本思想是盡管“編碼長(zhǎng)度”較大但在譯碼過(guò)程中能夠?qū)⑺鼈兎纸鉃樵S多較容易實(shí)現(xiàn)的步驟來(lái)完成。在這一研究領(lǐng)域，Turbo碼是一個(gè)成功的例子，它以一種嶄新的方式構(gòu)造好碼并且以較為合理的復(fù)雜度進(jìn)行譯碼。10.1Turbo碼10.1.1Turbo碼的編碼及其性能Turbo碼的基本形式如圖10.1所示。它看起來(lái)像一個(gè)典型的系統(tǒng)分組碼，其編碼輸出分成消息比特和校驗(yàn)比特兩大部分，而校驗(yàn)比特又分為z1、z2兩部分，其不同之處在于其中一個(gè)含有交織器而另一個(gè)則沒(méi)有。圖10.1Turbo碼編碼器框圖10.1Turbo碼通常情況下，圖10.1中的兩個(gè)編碼器都采用相同的結(jié)構(gòu)，但是也可以采有不同的編碼器組合。Turbo碼推薦使用的編碼器是短限長(zhǎng)的遞歸系統(tǒng)卷積碼（RSC，RecursiveSystematicConvolutional）。采用卷積碼遞歸，也即將一個(gè)或多個(gè)抽頭的輸出反饋到移位寄存器的輸入端，其原因是使移位寄存器的內(nèi)部狀態(tài)與它過(guò)去的輸出有關(guān)，以此對(duì)錯(cuò)誤圖樣的狀態(tài)施加影響，因?yàn)橄到y(tǒng)碼的單個(gè)誤碼會(huì)引起多個(gè)校驗(yàn)誤碼，而基于這種方法就可以獲得更好的整體編碼效益以提高性能。10.1Turbo碼圖10.28狀態(tài)遞歸系統(tǒng)卷積碼編碼器圖10.2給出了一個(gè)8狀態(tài)遞歸系統(tǒng)卷積碼編碼器。10.1Turbo碼交織器主要可分為周期交織器和偽隨機(jī)交織器兩種。Turbo碼使用的是偽隨機(jī)交織器，對(duì)系統(tǒng)比特進(jìn)行交織，實(shí)質(zhì)上相當(dāng)于對(duì)另一組信息比特m’送給編碼器，因此等效的碼長(zhǎng)擴(kuò)大了1倍。雖然Turbo碼中的兩個(gè)編碼器都使用卷積碼，但整體上它是分組碼，其分組長(zhǎng)度取決于交織的長(zhǎng)度。由于圖10.1的兩個(gè)RSC卷積碼編碼器都是線性的，因此可認(rèn)為Turbo碼是線性分組碼。10.1Turbo碼Turbo碼采用并行編碼方案，輸入的消息比特一方面直接進(jìn)入編碼器1，另一方面經(jīng)過(guò)交織器重新排序后輸入到編碼器2。信息比特和由兩個(gè)編碼器生成的兩組校驗(yàn)比特組成了Turbo編碼器的輸出。10.1Turbo碼由于并行編碼方案使用了遞歸的系統(tǒng)卷積碼，并在兩個(gè)編碼器之間引入了偽隨機(jī)交織器。因此，Turbo碼對(duì)信道誤碼實(shí)質(zhì)上表現(xiàn)出隨機(jī)的特性，同時(shí)，其結(jié)構(gòu)又使得譯碼方案切實(shí)可行。根據(jù)編碼理論可知，如果分組足夠大，隨機(jī)選取的碼可以接近香農(nóng)的信道容量，這是Turbo碼具有優(yōu)越性能的真正原因。10.1Turbo碼圖10.3給出了一個(gè)碼率為1/2且具有較大分組長(zhǎng)度的Turbo碼經(jīng)AWGN信道傳輸時(shí)的誤碼性能。為了便于比較，圖中還給出了在相同AWGN信道條件下的另外兩條曲線，即未編碼的數(shù)據(jù)傳輸（碼率=1）曲線和碼率為1/2時(shí)的香農(nóng)理論極限。圖10.3Turbo碼的誤碼性能及相關(guān)比較10.1Turbo碼對(duì)圖10.3進(jìn)行分析可以看出，雖然在Eb/N0較低時(shí)，Turbo碼進(jìn)行傳輸時(shí)的誤比特率明顯高于未編碼的數(shù)據(jù)傳輸，但是當(dāng)Eb/N0達(dá)到某一臨界值時(shí)，Turbo碼的誤比特率會(huì)迅速下降。尤其值得注意的是，當(dāng)誤比特率達(dá)到10-5時(shí)，Turbo碼要求的Eb/N0僅比香農(nóng)理論極限值大0.5dB。然而必須指出，如此高的性能改善，其代價(jià)是交織器的大小或Turbo碼的分組長(zhǎng)度必須足夠大。此外，改善性能所需的大量迭代也會(huì)增加譯碼器的等待時(shí)間，其原因主要是信息的數(shù)字處理沒(méi)有對(duì)反饋提供幫助。10.1Turbo碼10.1.2Turbo碼的譯碼簡(jiǎn)介Turbo碼的譯碼原理如圖10.4所示。它通過(guò)對(duì)系統(tǒng)噪聲模型和兩個(gè)譯碼器中兩組校驗(yàn)比特的運(yùn)算，產(chǎn)生原始信息比特的估計(jì)值。在討論具體譯碼過(guò)程之前，先介紹內(nèi)部信息和外部信息的概念。圖10.4Turbo碼的譯碼原理10.1Turbo碼外部信息實(shí)際上是通過(guò)挖掘信息比特和譯碼器產(chǎn)生的原始輸入數(shù)據(jù)比特之間的相關(guān)性而得到的增量信息。外部信息可以用對(duì)數(shù)似然比值來(lái)表示，并用如圖10.5所示的兩個(gè)對(duì)數(shù)似然比的差計(jì)算。由消息比特譯碼段產(chǎn)生的外部信息，定義為在該譯碼段的輸出端計(jì)算得到的對(duì)數(shù)似然比與內(nèi)部信息的差值，此內(nèi)部信息由反饋到這個(gè)譯碼段輸入端的對(duì)數(shù)似然比表示。實(shí)際應(yīng)用的Turbo碼譯碼算法頗為復(fù)雜，這里僅僅給出一些基本概念，具體內(nèi)容就不再討論了。圖10.5外部信息10.2空時(shí)分組碼空時(shí)編碼將編碼和信號(hào)處理技術(shù)相結(jié)合，使用多個(gè)發(fā)射和接收天線進(jìn)行信息的發(fā)送和接收，在多個(gè)發(fā)射天線和各個(gè)時(shí)間周期的發(fā)射信號(hào)之間能夠產(chǎn)生空域和時(shí)域的相關(guān)性，這種空時(shí)相關(guān)性可以使接收機(jī)克服多輸入多輸出（MIMO，Multi-inputMulti-output）信道衰落和減少接收誤碼，從而有效改善無(wú)線通信系統(tǒng)的信息容量、信息率和誤碼率性能，可以在不犧牲帶寬的情況下獲得更高的編碼增益。多輸入多輸出系統(tǒng)圖

10.2空時(shí)分組碼X為T

個(gè)時(shí)隙從N個(gè)發(fā)射天線發(fā)射的信號(hào)發(fā)射矩陣（T×N）10.2空時(shí)分組碼R為接收矩陣（T×M），包含

T

個(gè)時(shí)隙中的所有接收信號(hào)信道矩陣H，為（N×M）維路徑增益10.2空時(shí)分組碼噪聲矩陣n，（T×M）維得到信道輸入輸出關(guān)系的矩陣表示形式：R=X·H+n10.2空時(shí)分組碼10.2空時(shí)分組碼空時(shí)編碼主要分為空時(shí)網(wǎng)格碼和空時(shí)分組碼。當(dāng)其他分集方式可能受限或者不存在時(shí)，空時(shí)分組碼是實(shí)現(xiàn)發(fā)射分集的一種簡(jiǎn)單而有效的方法，常見(jiàn)的有正交空時(shí)分組碼和準(zhǔn)正交空時(shí)分組碼。正交空時(shí)分組碼首先由Alamouti提出，是一種發(fā)射天線數(shù)為2的滿碼率滿分集雙路分集傳輸結(jié)構(gòu)，接收端采用最大似然譯碼。研究表明，當(dāng)發(fā)射天線數(shù)大于2時(shí)，不可能存在各元素為復(fù)數(shù)的滿碼率正交空時(shí)分組碼，Jafarkhani提出了發(fā)射天線數(shù)為4的滿碼率準(zhǔn)正交空時(shí)分組碼。本節(jié)簡(jiǎn)要介紹這兩種碼。考慮發(fā)端有N

個(gè)發(fā)射天線、收端有M

個(gè)接收天線的系統(tǒng)?？諘r(shí)編碼設(shè)計(jì)的目標(biāo)就是獲得最大分集增益

NM

、最大編碼增益和可能的最大吞吐量。空時(shí)分組碼可視為一種能提供滿分集增益和具有非常低的編碼和譯碼復(fù)雜度的多個(gè)發(fā)射天線的系統(tǒng)。10.2空時(shí)分組碼Alamouti碼發(fā)射機(jī)方案圖10.2空時(shí)分組碼假定一個(gè)具有2發(fā)射天線和單接收天線的系統(tǒng)采用的是Alamouti碼，將每bbits映射為一個(gè)具有2b個(gè)符號(hào)的星座圖中的一個(gè)符號(hào)來(lái)發(fā)射b

bits/周期的信號(hào)。星座圖可以是實(shí)的或者復(fù)的星座圖，如PAM、PSK、QAM等。10.2空時(shí)分組碼首先發(fā)射機(jī)通過(guò)一個(gè)包含2bbits的分組從星座圖中選出兩個(gè)符號(hào)，若x2和x1是由包含2b

bits的分組所選定的兩個(gè)符號(hào)，發(fā)射機(jī)在第一個(gè)時(shí)隙從第一個(gè)天線發(fā)射x1，從第二個(gè)天線發(fā)射x2

。接著在第二個(gè)時(shí)隙從第一個(gè)天線發(fā)射，從第二個(gè)天線發(fā)射。因此發(fā)射碼字為

10.2空時(shí)分組碼分別用和來(lái)表示天線1和天線2上的發(fā)射序列。Alamouti方案的主要特征是兩根發(fā)射天線的發(fā)射序列是正交的10.2空時(shí)分組碼最大似然譯碼過(guò)程以2個(gè)發(fā)射天線，1個(gè)接收天線的Alamouti碼為例，接收信號(hào)的矩陣表達(dá)式為：以Alamouti碼為發(fā)射碼10.2空時(shí)分組碼10.2空時(shí)分組碼10.2空時(shí)分組碼得到判決統(tǒng)計(jì)為：Alamouti碼具有兩個(gè)重要性質(zhì)：譯碼簡(jiǎn)單：通過(guò)線性處理，每個(gè)符號(hào)被分別譯碼。最大分集：滿足秩準(zhǔn)則，因此能夠提供最大分集。10.2空時(shí)分組碼實(shí)正交設(shè)計(jì)

廣義實(shí)正交設(shè)計(jì)

復(fù)正交設(shè)計(jì)

廣義復(fù)正交設(shè)計(jì)10.2空時(shí)分組碼當(dāng)天線數(shù)更大時(shí)，能否設(shè)計(jì)出類似的空時(shí)碼？

當(dāng)發(fā)射天線數(shù)大于2時(shí)，不可能存在各元素為復(fù)數(shù)的滿碼率正交空時(shí)分組碼，Jafarkhani提出了發(fā)射天線數(shù)為4的滿碼率準(zhǔn)正交空時(shí)分組碼。10.2空時(shí)分組碼準(zhǔn)正交空時(shí)分組碼-編碼過(guò)程Alamouti碼的生成矩陣：為了設(shè)計(jì)一個(gè)滿速率的碼，放寬簡(jiǎn)單獨(dú)立譯碼條件。設(shè)計(jì)一族碼，即準(zhǔn)正交空時(shí)分組碼（QOSTBC），可以進(jìn)行符號(hào)對(duì)的獨(dú)立譯碼。10.2空時(shí)分組碼式中矩陣是矩陣的復(fù)共軛，例如10.2空時(shí)分組碼將的第i列表示為。對(duì)于任意的待定變量 ，有組與組正交，組內(nèi)不正交，滿足準(zhǔn)正交關(guān)系。碼字的分集階數(shù)為2。10.2空時(shí)分組碼最大似然譯碼過(guò)程以4個(gè)發(fā)射天線，1個(gè)接收天線舉例接收信號(hào)的矩陣表達(dá)式為：10.2空時(shí)分組碼10.2空時(shí)分組碼式中10.2空時(shí)分組碼取其中10.2空時(shí)分組碼10.2空時(shí)分組碼得到判決統(tǒng)計(jì)為10.2空時(shí)分組碼式中10.2空時(shí)分組碼成對(duì)譯碼準(zhǔn)正交空時(shí)分組碼的最大似然譯碼就等價(jià)于求如下最小問(wèn)題：通過(guò)代數(shù)處理求得上述最大似然譯碼等價(jià)于最小化和式為10.2空時(shí)分組碼式中10.2空時(shí)分組碼以及10.2空時(shí)分組碼因?yàn)楠?dú)立于，并且獨(dú)立于，所以符號(hào)對(duì)和可以獨(dú)立的譯碼。10.2空時(shí)分組碼旋轉(zhuǎn)準(zhǔn)正交空時(shí)分組碼當(dāng)有個(gè)接收天線時(shí)，碼率為1時(shí)獲得的最大分集階數(shù)為。若所有的符號(hào)都選自同一星座，那么在這種情況下，速率為1的復(fù)正交碼不可能達(dá)到的 分集階數(shù)。為了達(dá)到滿分集，對(duì)不同的發(fā)射符號(hào)選用不同的星座。10.2空時(shí)分組碼例如，可以在發(fā)射之前將符號(hào)和旋轉(zhuǎn)，將旋轉(zhuǎn)后的版本分別表示為和。用代替時(shí)，準(zhǔn)正交空時(shí)分組碼就有可能達(dá)到滿分集。生成矩陣為10.2空時(shí)分組碼旋轉(zhuǎn)角度，變?yōu)?，則上式變?yōu)?0.2空時(shí)分組碼將的第i列表示為。對(duì)于任意的待定變量 ，有組與組正交，組內(nèi)不正交，滿足準(zhǔn)正交關(guān)系。10.2空時(shí)分組碼10.3低密度奇偶校驗(yàn)碼LDPC碼和大部分可譯的接近香農(nóng)極限的糾錯(cuò)碼都可以理解成圖形編碼。圖形不但能描述編碼，更重要的是能構(gòu)造出用于迭代譯碼的和積譯碼算法。這種編碼方案在保持了合理的譯碼復(fù)雜度的同時(shí)，可使信息傳輸速率接近信道容量。本節(jié)首先介紹LDPC碼的定義，然后對(duì)其編、譯碼進(jìn)行簡(jiǎn)要討論10.3低密度奇偶校驗(yàn)碼10.3.1低密度奇偶校驗(yàn)碼的定義LDPC碼是一種線性分組碼，該碼不是通過(guò)生成矩陣來(lái)定義，而是通過(guò)奇偶校驗(yàn)矩陣來(lái)定義的。該種碼最主要的問(wèn)題是如何譯碼而不是編碼，因此LDPC碼最主要的問(wèn)題是尋找一種便于譯碼的算法。其校驗(yàn)矩陣非常大，然而矩陣中非零元素卻很少，更準(zhǔn)確地說(shuō)，非零元素在所有元素中所占比例很低，這就是稱為“低密度”碼的原因。Gallager對(duì)LDPC給出了如下定義：一個(gè)（N，p，q）LDPC碼，長(zhǎng)度為N，奇偶校驗(yàn)矩陣H中每列“1”的個(gè)數(shù)為p，每行“1”的個(gè)數(shù)為q；每一行中非零元素的個(gè)數(shù)稱為行重，每一列中非零元素的個(gè)數(shù)稱為列重，因此，行重為q，列重為p；如果所有行都是線性無(wú)關(guān)的，則碼字的碼率為(q-p)/q。10.3低密度奇偶校驗(yàn)碼奇偶校驗(yàn)矩陣H的構(gòu)造原則是：任意兩列只有一個(gè)“1”相同；任意兩行最多只有一個(gè)“1”相同。矩陣的密度r定義為“1”的個(gè)數(shù)與所有元素個(gè)數(shù)的比。例如構(gòu)造一個(gè)（12，2，4）碼字，其奇偶校驗(yàn)矩陣為（10.20）很顯然這種結(jié)構(gòu)滿足上面的規(guī)則：即每列有p個(gè)“1”，每行有q個(gè)“1”，即列重p=2，行重q=4，密度r=1/3。很顯然這種結(jié)構(gòu)是很隨機(jī)的。為了描述的方便，LDPC碼（N，p，q）等價(jià)地表示為（N，k）形式，其中，k=NpN/q為信息位。 N×碼率10.3低密度奇偶校驗(yàn)碼假設(shè)碼字為，其中是信息位，而是校驗(yàn)位，上面校驗(yàn)矩陣可以用校驗(yàn)方程表示為（10.21）10.3低密度奇偶校驗(yàn)碼也可以用圖來(lái)表示，通常稱為Tanner圖。本例校驗(yàn)矩陣對(duì)應(yīng)的Tanner圖如圖10.6所示。圖10.6校驗(yàn)矩陣的Tanner圖表示10.3低密度奇偶校驗(yàn)碼圖中上一行由N個(gè)變量節(jié)點(diǎn)（用圓圈表示）組成，表示碼字的信息位，用表示，對(duì)應(yīng)奇偶校驗(yàn)矩陣的列；下一行由k個(gè)校驗(yàn)節(jié)點(diǎn)（用方塊表示）組成，表示碼字的校驗(yàn)位，用表示，對(duì)應(yīng)奇偶校驗(yàn)矩陣的行。節(jié)點(diǎn)之間通過(guò)邊連接，同類節(jié)點(diǎn)之間沒(méi)有邊連接，只有兩類節(jié)點(diǎn)之間有邊存在。與變量節(jié)點(diǎn)連接的邊的條數(shù)稱為的度，與校驗(yàn)節(jié)點(diǎn)連接的邊的條數(shù)稱為的度。對(duì)一個(gè)正則LDPC碼，所有信息位的度都相同，所有檢驗(yàn)位的度也相同，這樣一個(gè)Tanner圖就稱為正則的。如果校驗(yàn)矩陣的第i行第j列元素為“1”，則Tanner圖中的第j個(gè)變量節(jié)點(diǎn)與第i個(gè)校驗(yàn)節(jié)點(diǎn)有一條邊相連。10.3低密度奇偶校驗(yàn)碼10.3.2低密度奇偶校驗(yàn)碼的譯碼正如上面所提，奇偶校驗(yàn)矩陣的稀疏結(jié)構(gòu)是譯碼的關(guān)鍵，因?yàn)樗鼪Q定譯碼的復(fù)雜度。采用最大似然譯碼是一個(gè)N-p困難問(wèn)題（也就是說(shuō)，必須檢查所有可能的碼字，并與接收信號(hào)進(jìn)行比較）。因此通常采用迭代算法進(jìn)行譯碼，該種算法稱為置信算法。通過(guò)Tanner圖進(jìn)行譯碼稱為置信算法或者消息傳遞。每個(gè)節(jié)點(diǎn)收集傳入的信息，按照局部規(guī)則進(jìn)行計(jì)算，得出每個(gè)變量節(jié)點(diǎn)值為0的概率。然后每個(gè)節(jié)點(diǎn)再把計(jì)算結(jié)果傳給其他節(jié)點(diǎn)，這種傳遞是雙向的。10.3低密度奇偶校驗(yàn)碼一方面，變量節(jié)點(diǎn)的計(jì)算結(jié)果會(huì)傳遞給校驗(yàn)節(jié)點(diǎn)，該計(jì)算結(jié)果定義為

；另一方面，校驗(yàn)節(jié)點(diǎn)的計(jì)算結(jié)果會(huì)傳遞給變量節(jié)點(diǎn)，該計(jì)算結(jié)果定義為

；最后，總的計(jì)算結(jié)果由所有節(jié)點(diǎn)的

、

和外部信息得出。如圖10.7所示，接收信號(hào)矢量為

。圖10.7消息傳遞因子圖10.3低密度奇偶校驗(yàn)碼對(duì)AWGN信道，有如下的譯碼步驟：（1）首先，知道接收信號(hào)矢量

的值，就可以決定數(shù)據(jù)比特的值。知道了噪聲

的統(tǒng)計(jì)值之后，就可以計(jì)算變量節(jié)點(diǎn)為“1”或“0”的概率，然后把信息傳遞給校驗(yàn)節(jié)點(diǎn)。反之，校驗(yàn)節(jié)點(diǎn)暫時(shí)不能把有用信息傳遞給變量節(jié)點(diǎn)，因此，有

（10.22）

（10.23）10.3低密度奇偶校驗(yàn)碼（2）其次，校驗(yàn)節(jié)點(diǎn)給每個(gè)變量節(jié)點(diǎn)傳遞一個(gè)不同的信息。假設(shè)與第i個(gè)變量節(jié)點(diǎn)相連的所有校驗(yàn)節(jié)點(diǎn)的集合為Ai，則每個(gè)校驗(yàn)節(jié)點(diǎn)包含兩種重要的信息： ①它知道與該校驗(yàn)節(jié)點(diǎn)相連的所有數(shù)據(jù)比特的值（或概率大?。? ②進(jìn)入校驗(yàn)節(jié)點(diǎn)的所有數(shù)據(jù)位之和為0mod2，這是奇偶校驗(yàn)矩陣的關(guān)鍵點(diǎn)，根據(jù)這些信息，可以計(jì)算第j個(gè)數(shù)據(jù)位發(fā)生的概率。10.3低密度奇偶校驗(yàn)碼因?yàn)槭茿WGN信道，會(huì)產(chǎn)生連續(xù)輸出，由于不是二進(jìn)制信道，因此需要用對(duì)數(shù)似然來(lái)代替簡(jiǎn)單的概率，信息變?yōu)椋?0.24）式中：A(i)-j指“A(i)中除去第j個(gè)校驗(yàn)節(jié)點(diǎn)的集合”，即去除第j個(gè)校驗(yàn)節(jié)點(diǎn)之后，與第i個(gè)變量節(jié)點(diǎn)相連的所有校驗(yàn)節(jié)點(diǎn)的集合；上標(biāo)(l-1)是指第

(l-1)次迭代。10.3低密度奇偶校驗(yàn)碼（3）然后，利用校驗(yàn)節(jié)點(diǎn)傳遞的信息來(lái)更新對(duì)數(shù)據(jù)比特所做的判決。規(guī)則為 (10.4)式中：

是指去除第i個(gè)變量節(jié)點(diǎn)之后，與第j個(gè)校驗(yàn)節(jié)點(diǎn)相連的所有變量節(jié)點(diǎn)的集合。10.3低密度奇偶校驗(yàn)碼（4）根據(jù)上面的討論，可以計(jì)算出數(shù)據(jù)位是“1”或“0”的近似后驗(yàn)概率，為

（10.43）由此可以對(duì)譯出的碼字進(jìn)行初步判決，如果譯出碼字與發(fā)射碼字相同，即校驗(yàn)和為0，則停止譯碼。10.3低密度奇偶校驗(yàn)碼例10.1已知一LDPC碼的奇偶校驗(yàn)矩陣為假設(shè)發(fā)射的碼字為信道為AWGN信道，噪聲方差為接收端對(duì)應(yīng)的信噪比為接收碼字為求譯碼結(jié)果。下面給出一個(gè)利用低密度奇偶校驗(yàn)矩陣進(jìn)行譯碼的例子。dB10.3低密度奇偶校驗(yàn)碼接收似然值的硬門限會(huì)導(dǎo)致譯出的碼字中第2位出現(xiàn)1個(gè)錯(cuò)誤，即消息傳遞迭代算法和糾錯(cuò)過(guò)程如圖10.8所示。a.計(jì)算

，進(jìn)行初步估計(jì)，得出校驗(yàn)和不為零，找出錯(cuò)誤位置，然后計(jì)算μ(1)和L，對(duì)譯出碼字進(jìn)行判斷，計(jì)算出校驗(yàn)和不為零，即10.3低密度奇偶校驗(yàn)碼10.3低密度奇偶校驗(yàn)碼b.繼續(xù)迭代，計(jì)算

、μ(2)和L，對(duì)譯出碼字進(jìn)行判斷，計(jì)算出校驗(yàn)和不為零，即10.3低密度奇偶校驗(yàn)碼c.繼續(xù)迭代，計(jì)算

、μ(3)和L，對(duì)譯出碼字進(jìn)行判斷，計(jì)算出校驗(yàn)和不為零，即10.3低密度奇偶校驗(yàn)碼d.繼續(xù)迭代，計(jì)算

、μ(4)和L，對(duì)譯出碼字進(jìn)行判斷，計(jì)算出校驗(yàn)和不為零，即10.3低密度奇偶校驗(yàn)碼e.繼續(xù)迭代，計(jì)算

、μ(5)和L，對(duì)譯出碼字進(jìn)行判斷，計(jì)算出校驗(yàn)和不為零，即10.3低密度奇偶校驗(yàn)碼f.繼續(xù)迭代，計(jì)算

、μ(6)和L，對(duì)譯出碼字進(jìn)行判斷，計(jì)算出校驗(yàn)和不為零，即10.3低密度奇偶校驗(yàn)碼g.繼續(xù)迭代，計(jì)算

、μ(7)和L，對(duì)譯出碼字進(jìn)行判斷，計(jì)算出校驗(yàn)和為零，譯碼停止，譯出碼字與發(fā)射碼字相同，即10.3低密度奇偶校驗(yàn)碼圖10.8低密度奇偶校驗(yàn)消息傳遞的迭代過(guò)程LDPC碼還有很多譯碼算法，感興趣的讀者可以參考相關(guān)文獻(xiàn)。10.4網(wǎng)絡(luò)編碼與協(xié)作10.4.1網(wǎng)絡(luò)編碼網(wǎng)絡(luò)編碼是一種基于網(wǎng)絡(luò)層的編碼技術(shù)，允許網(wǎng)絡(luò)節(jié)點(diǎn)在傳統(tǒng)數(shù)據(jù)轉(zhuǎn)發(fā)的基礎(chǔ)上參與數(shù)據(jù)處理，是一種提高網(wǎng)絡(luò)吞吐量、穩(wěn)健性和安全性的有效方法。其核心思想是在傳統(tǒng)存儲(chǔ)轉(zhuǎn)發(fā)的路由算法基礎(chǔ)上，通過(guò)允許對(duì)接收的多個(gè)數(shù)據(jù)包進(jìn)行編碼信息融合，增加單次傳輸?shù)男畔⒘浚岣呔W(wǎng)絡(luò)整體性能。網(wǎng)絡(luò)編碼概念一經(jīng)提出便引起了國(guó)際學(xué)術(shù)界的關(guān)注，其理論和應(yīng)用已成為通信領(lǐng)域研究的新熱點(diǎn)。10.4網(wǎng)絡(luò)編碼與協(xié)作1.網(wǎng)絡(luò)編碼的相關(guān)概念下面通過(guò)一個(gè)例子來(lái)介紹網(wǎng)絡(luò)編碼的相關(guān)概念。圖10.9給出了傳統(tǒng)路由方法與網(wǎng)絡(luò)編碼進(jìn)行比較的示意圖，可以用圖10.9(b)來(lái)闡述網(wǎng)絡(luò)編碼的基本原理。圖中s是信源，x、y是信宿，各條點(diǎn)對(duì)點(diǎn)的傳輸鏈路的信道容量都是1，現(xiàn)要將2比特?cái)?shù)據(jù)a、b同時(shí)從s傳到x、y。易知s與z、y之間均分別存在兩條獨(dú)立路徑，若采用傳統(tǒng)路由方法，如圖10.9(a)所示，由于兩組路徑間存在共有鏈路wz，a、b不能同時(shí)在wz上傳輸，則s到z、y的最大信息傳輸速率為1.5比特/單位時(shí)間。若采用網(wǎng)絡(luò)編碼方法，在節(jié)點(diǎn)w上對(duì)a、b執(zhí)行異或操作并轉(zhuǎn)發(fā)，則節(jié)點(diǎn)x可以通過(guò)aba計(jì)算解出b，同理y也可以解出a，從而使s到z、y的信息流速率達(dá)到2比特/單位時(shí)間，帶寬利用率提高33％。10.4網(wǎng)絡(luò)編碼與協(xié)作

（a）傳統(tǒng)路由方法示意圖

（b）網(wǎng)絡(luò)編碼示意圖圖10.9傳統(tǒng)路由方法與網(wǎng)絡(luò)編碼的比較10.4網(wǎng)絡(luò)編碼與協(xié)作該例表明，只要允許網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼，網(wǎng)絡(luò)的傳輸效率就能得到進(jìn)一步的提升。當(dāng)然，所用的編碼和解碼方案是要通過(guò)網(wǎng)絡(luò)協(xié)議進(jìn)行協(xié)商的。事實(shí)上，網(wǎng)絡(luò)編碼理論突破了傳統(tǒng)的路由概念，允許通信網(wǎng)絡(luò)的中間節(jié)點(diǎn)對(duì)接收到的信息進(jìn)行編碼處理，可以有效提升通信網(wǎng)絡(luò)的傳輸能力。10.4網(wǎng)絡(luò)編碼與協(xié)作下面用三元組(S，T，X來(lái))描述組播通信。信源S將一組消息X＝(x1,,xn)

通過(guò)中繼節(jié)點(diǎn)傳遞給一組信宿T=(t1,,tn),x1,,xn均是某個(gè)字母表上的符號(hào)。網(wǎng)絡(luò)編碼就是一組滿足某些約束條件的邊函數(shù)的集合。通過(guò)為節(jié)點(diǎn)

iI的每條出邊找到一個(gè)映射，使得所有信宿

tiT能同時(shí)接收到消息集合X，并保證節(jié)點(diǎn)的輸出信息完全由其輸入信息和生成信息決定，則稱網(wǎng)絡(luò)具有網(wǎng)絡(luò)編碼解。10.4網(wǎng)絡(luò)編碼與協(xié)作2.編碼方法網(wǎng)絡(luò)編碼的基本特征就是在網(wǎng)絡(luò)層對(duì)傳輸?shù)男畔⑦M(jìn)行智能化處理，包括采用各種編碼策略。對(duì)一個(gè)給定的組播網(wǎng)絡(luò)，如何設(shè)計(jì)網(wǎng)絡(luò)編碼實(shí)現(xiàn)最大流傳輸是一個(gè)重要的問(wèn)題。網(wǎng)絡(luò)編碼按照節(jié)點(diǎn)輸出和輸入的關(guān)系可劃分為線性網(wǎng)絡(luò)編碼和非線性網(wǎng)絡(luò)編碼，根據(jù)編碼系數(shù)生成的隨機(jī)性可劃分為隨機(jī)網(wǎng)絡(luò)編碼和確定網(wǎng)絡(luò)編碼。這里僅討論目前比較成熟的網(wǎng)絡(luò)編碼構(gòu)造方法－代數(shù)法，信息流法，隨機(jī)網(wǎng)絡(luò)編碼方法10.4網(wǎng)絡(luò)編碼與協(xié)作（1）代數(shù)法代數(shù)型編碼方法是由R.Kotter和M.Medard提出，其核心思想是將網(wǎng)絡(luò)中節(jié)點(diǎn)輸入信息與輸出信息之間的關(guān)系利用矩陣的形式表示出來(lái)，從中發(fā)現(xiàn)一些內(nèi)在的聯(lián)系。這樣可以幫助人們從網(wǎng)絡(luò)系統(tǒng)的角度重新認(rèn)識(shí)信息傳輸?shù)膬?nèi)在規(guī)律，包括網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的編碼設(shè)計(jì)。Koetter等人給出了網(wǎng)絡(luò)編碼構(gòu)造的代數(shù)框架，將系統(tǒng)轉(zhuǎn)移矩陣M分解為T個(gè)子矩陣

，通過(guò)構(gòu)造一組參數(shù)使得每個(gè)子矩陣的行列式非0，從而得到網(wǎng)絡(luò)編碼解?；诖鷶?shù)法的構(gòu)造算法的優(yōu)點(diǎn)在于可借助成熟的矩陣?yán)碚摲治龈黝愅負(fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)編碼問(wèn)題，其缺點(diǎn)是可擴(kuò)展性差、計(jì)算量大。10.4網(wǎng)絡(luò)編碼與協(xié)作（2）信息流法信息流法利用解耦技術(shù)，將網(wǎng)絡(luò)編碼問(wèn)題分解為確定編碼子圖和給子圖分配碼字兩個(gè)子問(wèn)題分別求解。Jaggi等人給出了一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的網(wǎng)絡(luò)編碼構(gòu)造算法，分為兩個(gè)步驟：首先采用流算法為每個(gè)信宿找到從信源到信宿的n條邊不重疊的路徑集合，然后采用貪心策略對(duì)已知路徑的邊按拓?fù)漤樞蚍峙渚€性碼，并保證任意信宿的n條入邊上的全局編碼向量線性獨(dú)立，且能擴(kuò)張成有限域，從而獲得網(wǎng)絡(luò)編碼解。信息流法的優(yōu)點(diǎn)在于解耦合的兩個(gè)子問(wèn)題可結(jié)合成熟的優(yōu)化理論采用分布式算法分別求解，難點(diǎn)在于保證所有信宿的人邊上的編碼向量均線性獨(dú)立。10.4網(wǎng)絡(luò)編碼與協(xié)作（3）隨機(jī)網(wǎng)絡(luò)編碼方法所謂隨機(jī)的網(wǎng)絡(luò)編碼方法，就是每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)獨(dú)立的隨機(jī)選取一種映射方式將它自己接收到的輸入信息映射到相應(yīng)的輸出鏈路上。通常情況下，該映射方式選取為線性映射，即在給定的一個(gè)有限數(shù)域上為每個(gè)輸入信息流選取相應(yīng)的加權(quán)系數(shù)。利用這種方法，可以證明在進(jìn)行組播信號(hào)時(shí)，每個(gè)接收節(jié)點(diǎn)可以以很高的概率恢復(fù)原始信號(hào)。10.4網(wǎng)絡(luò)編碼與協(xié)作3.網(wǎng)絡(luò)編碼的應(yīng)用舉例考慮如圖10.10所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的信息傳輸系統(tǒng)，S表示信源節(jié)點(diǎn)，D表示目的節(jié)點(diǎn)，A、B和C表示中繼節(jié)點(diǎn)，負(fù)責(zé)將信源S的信息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)D。10.4網(wǎng)絡(luò)編碼與協(xié)作圖10.10抗一條鏈路中斷的網(wǎng)絡(luò)編碼模式10.4網(wǎng)絡(luò)編碼與協(xié)作從圖10.10的拓?fù)浣Y(jié)構(gòu)可知，當(dāng)每條鏈路的最大傳輸容量均為一個(gè)信息單位時(shí)，則從信源S到目的節(jié)點(diǎn)D的最大傳輸容量為3個(gè)信息單位。對(duì)這種點(diǎn)到點(diǎn)的網(wǎng)絡(luò)傳輸，只采用多路徑的傳輸模式，就可以實(shí)現(xiàn)最大傳輸容量的傳輸。在本結(jié)構(gòu)中，這3條路徑分別為：S→A→D，S→B→D和S→C→D。然而，如果在這些路徑中某一條鏈路發(fā)生中斷，則目的節(jié)點(diǎn)D就無(wú)法恢復(fù)信源S發(fā)送的信息。例如B→D這條路徑中斷了或出現(xiàn)故障，此時(shí)需要通知源節(jié)點(diǎn)調(diào)整發(fā)送方式或修改傳輸路徑。而B(niǎo)→D這條路徑中信源發(fā)送的信息會(huì)全部丟掉。顯然，這種單純的多路由網(wǎng)絡(luò)傳輸模式是無(wú)法抗網(wǎng)絡(luò)鏈路故障的。10.4網(wǎng)絡(luò)編碼與協(xié)作與此對(duì)應(yīng)的是，如果采用如圖10.10所示的網(wǎng)絡(luò)編碼的模式，在路徑S→A→D傳輸信息a，在路徑S→B→D傳輸信息b，在路徑S→C→D傳輸信息a+b，那么一旦有一條路徑出現(xiàn)問(wèn)題使得信息無(wú)法正常傳輸，目的節(jié)點(diǎn)D仍能正確恢復(fù)信源S發(fā)送的信息。例如B→D這條路徑中斷了或出現(xiàn)