[發明專利]一次反饋條件下度漸增的噴泉碼的編碼方法

有效

• 申請號: 201310594878.8
• 申請日: 2013-11-21
• 公開（公告）號: CN103716134A
• 公開（公告）日: 2014-04-09
• 發明（設計）人: 謝磊;陳惠芳;應挺;王匡
• 申請（專利權）人: 浙江大學
• 主分類號: H04L1/16
• 分類號: H04L1/16;H04L1/00
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 杜軍

技術領域

本發明屬于通信技術領域，具體是信道編碼中的糾刪碼領域，涉及一種一次反饋條件下度漸增的噴泉碼的編碼方法。

背景技術

隨著計算機網絡通信技術的快速發展，急速增長的數據量與互聯網絡的傳輸能力形成了一對亟需解決的矛盾，而對通信可靠性的要求也越來越高。目前的網絡可靠性主要靠傳輸協議來保證，比如TCP/IP協議，用重傳機制來保證可靠性。然而在很多情況下，由于時延及鏈路質量的因素，重傳并不適用，而且會造成嚴重的帶寬浪費。

1998年，M.Luby首次提出數字噴泉(Digital?Fountain)的概念，它最初是針對大規模數據分發及廣播業務而提出的一種低開銷的可靠的網絡編碼方式。但當時并沒有找到一種可靠的編碼設計方案。第一種切實可行的數字噴泉碼——LT碼由M.Luby于2002年首次提出，憑借其強大的應用潛力，數字噴泉碼得到了廣泛的關注，獲得越來越多的實際應用。

數字噴泉碼是一種特殊的編碼，它具有碼率不受限的特性，即，它能從輸入數據符號中編碼生成無限多個碼字，并且接收端只要得到其中足夠數量的碼字，就能從中可靠的解碼出輸入數據符號，而不依賴于網絡參數的變化，以及接收到的是哪些碼字和接收的順序。噴泉碼的編碼過程就如同源源不斷產生水滴(編碼分組)的噴泉(編碼器)，而我們只要用杯子(譯碼器)接收足夠數量的水滴，即可達到飲用(成功譯碼)的目的，因此該種編碼被稱為噴泉碼。

噴泉碼的特點與優點主要包括：

(1)原始數據信息被分散在各個編碼信息單元內，不需要重傳，可通過后續信息單元的接收恢復原始數據；

(2)付出的代價則是需要的編碼信息單元數比原始信息單元數量略有增加，而這可通過對度分布的設計優化而達到較好的折中。

與傳統的信道編碼技術相比，數字噴泉碼更加靈活。物理層的信道編碼僅能糾正點到點鏈路上因誤碼帶來的錯誤，對鏈路層或由于碰撞擁塞導致的丟包則無能為力，因此無法為具體業務提供全面的端到端的可靠保障。數字噴泉碼恰好可以有效解決上述問題。在傳輸層或應用層采用時，因碰撞或網絡擁塞而導致的丟包可以被噴泉碼所恢復。

互聯網正在深入到生活的各個方面，隨之涌現出越來越多的多媒體實時業務，比如視頻點播、視頻會議、IPTV等。與傳統數據業務相比，這些多媒體業務具有數據量巨大、持續時間長、時延敏感性高等特點，并且要求極高的可靠性，而傳統的重傳機制在大數據量是很容易造成網絡的反饋擁塞，嚴重時會導致網絡癱瘓。數字噴泉碼的低編譯碼復雜度、不需反饋重傳、不依賴信道條件等優點使其可以提供一種具有良好擴展性的端到端的可靠解決方案，具有廣闊的應用前景。

發明內容

本發明的目的是基于存在反饋信道這一事實，設計一種一次反饋條件下度漸增的噴泉碼的編碼方法。該方法改進標準LT碼的編碼結構，度的生成采用健壯性的孤子分布，同時編碼器基于接收到的反饋信息不斷的調整度生成器，在保證編碼有效性的前提下，使編譯碼復雜度得到明顯的降低。

本發明方法中帶反饋的噴泉碼是指譯碼器在某個特定的時間告訴編碼器某些特定的信息，編碼器根據這些信息，調整它的編碼方式，以達到更優的性能。

本發明的噴泉碼的編碼方法具體步驟是：

步驟(1)：首先采用伯努利隨機試驗，試驗結果只取0和1，其中取到1的概率為λ；其次以k表示輸入符號的個數，對每一個輸入符號從0到k-1編號；從輸入符號0開始，對于每一個輸入符號，做一次伯努利隨機試驗；若試驗結果為1，則將這個輸入符號直接作為一個碼字發送，且這一個碼字以此輸入符號的序號作為它的序號；若試驗結果為0，則跳過這一輸入符號，而去處理下一個輸入符號；以此類推，依序處理了所有的輸入符號之后，此步驟的編碼結束；

步驟(2)：編碼器以標準LT碼的編碼方法對輸入符號開始編碼，具體步驟是：

a.由標準度生成器中隨機產生一個度，s；

b.從k個輸入符號中隨機的選取s個輸入符號；

c.將所有s個輸入符號異或在一起，作為一個碼字，該碼字的編號為k；

d.度生成器不斷隨機產生新的度，重復步驟b和c，生成的碼字從k+1開始編號,直到編碼器接收到譯碼器的反饋信息為止；

步驟(3)：當譯碼器接收到一個碼字，其序號大于等于k時，譯碼器將其接收到的序號小于k的碼字的個數反饋給編碼器，編碼器在接收到該信息之后設計漸增度生成器以取代LT碼的標準度生成器；此后編碼器利用漸增度生成器采用與標準LT碼相同的編碼方法不斷的生成碼字，直到譯碼器反饋譯碼成功的信息為止，碼字的序號按順序繼承自步驟(2)中的碼字。