信道編碼新進展簡介-2014

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

10.2空時分組碼X為T

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

T

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

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

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

NM

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

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

bits的分組所選定的兩個符號，發(fā)射機在第一個時隙從第一個天線發(fā)射x1，從第二個天線發(fā)射x2

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

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

廣義實正交設(shè)計

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

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

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

；另一方面，校驗節(jié)點的計算結(jié)果會傳遞給變量節(jié)點，該計算結(jié)果定義為

；最后，總的計算結(jié)果由所有節(jié)點的

、

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

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

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

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

（10.22）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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