[發明專利]增壓碼

有效

• 申請號: 201310036994.8
• 申請日: 2013-01-30
• 公開（公告）號: CN103227693A
• 公開（公告）日: 2013-07-31
• 發明（設計）人: 埃里克·斯托弗;沈八中;喬爾杰·圖吉口維克;蘇梅·查克拉博爾蒂;黃靖;希瓦·普拉卡什·謝特;卡姆利什·拉斯;戴維·加勒特;安德魯·布蘭克斯比
• 申請（專利權）人: 美國博通公司
• 主分類號: H04L1/00
• 分類號: H04L1/00
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 田喜慶

相關申請的交叉引用

本申請要求于2012年1月30日提交的美國臨時專利申請第61/592,202號、于2012年4月10日提交的美國臨時專利申請第61/622,223號、于2012年5月11日提交的美國臨時專利申請第61/646,037號、于2012年9月26日提交的美國臨時專利申請第61/706,045號以及于2013年1月25日提交的美國專利申請第13/750,280號的權益，將所有這些申請結合于此供參考。

技術領域

本申請總體上涉及對經由擦除信道傳輸的符號的編碼，且更具體地，涉及對經由數據包擦除信道傳輸的數據包的編碼。

背景技術

數據包擦除信道是一種接收或丟失所發送的數據包且了解任何丟失的數據包的位置的通信信道模型。通常可將互聯網模型化為數據包擦除信道。這是因為由于損壞或堵塞，可能會丟失經由互聯網傳輸的數據包，且可從每個所接收的數據包的報頭或有效載荷內包括的序列號中推測出任何丟失的數據包的位置。

根據由數據包流攜帶的數據的類型，丟失的數據包可能降低數據質量或者甚至給予在接收器處不可用的數據。因此，恢復機制通常被用于提供將接收經由擦除信道發送的數據包的某種可靠性水平。例如，重新傳輸機制被用于恢復多個基于數據包的網絡中丟失的數據包，但例如在發送器和接收器之間有很大的距離時，或者在信道嚴重受損時，重新傳輸可能造成很長延遲。由于這一和其他原因，使用擦除碼的前向糾錯（FEC）通常代替或結合常規重新傳輸機制來實施。

擦除碼將k個數據包串編碼為較長的n個數據包串，使得在接收器處可從n個數據包的子集中恢復原始的k個數據包串，而無需任何重新傳輸。擦除碼的性能可基于其接收效率和與其編碼和解碼算法相關的計算復雜性來表征。擦除碼的接收效率由分數k’/k給出，其中，k’為n個數據包的需要接收以恢復原始的k個數據包串的最小數量。特定擦除碼具有最佳接收效率（即，最高可獲得的接收效率）且可使用所發送的n個數據包中的任何（且僅）k個數據包來恢復原始的k個數據包串。

里德-所羅門（Reed-Solomon）碼是具有最佳接收效率的MDS碼，但用于實施里德-所羅門碼的典型編碼和解碼算法具有很高相關計算的復雜性。具體地，其計算復雜性隨著數據包數量n而增長，且其階（order）為O(nlog(n))。這使得對于許多基于數據包的網絡（包括互聯網）而言無法實行純粹的里德-所羅門解決方案，這些網絡支持被分段成多個可能很大的數據包的大文件/流的傳輸。

發明內容

本發明提供了一種用于對形成消息的輸入符號擦除編碼的方法，包括：基于所述消息來實施分別提供第一組碼字、第二組碼字和第三組碼字的至少三個塊編碼操作；基于所述第一組碼字來實施分別提供第四組碼字和第五組碼字的至少兩個濾波器編碼操作；為所述兩個濾波器編碼操作中的至少一個修改考慮到所述第一組碼字的位的順序；以及并行連接所述第二組碼字、所述第三組碼字、所述第四組碼字和所述第五組碼字以形成用于經由擦除信道傳輸的編碼符號。

上述方法還包括：在所述第二組碼字和所述第三組碼字與所述第四組碼字和所述第五組碼字并行連接之前，實施分別重復所述第二組碼字和所述第三組碼字一定次數的重復編碼操作。

上述方法中，使用異或運算來并行連接所述第二組碼字、所述第三組碼字、所述第四組碼字和所述第五組碼字。

上述方法還包括：在并行連接所述第二組碼字、所述第三組碼字、所述第四組碼字和所述第五組碼字之前，以無規律方式一起多路復用所述第四組碼字和所述第五組碼字。

上述方法中，所述塊編碼操作中的提供所述第一組碼字的一個塊編碼操作實施二進制塊碼。

上述方法中，所述塊編碼操作中的提供所述第二組碼字的一個塊編碼操作在有限域上實施非二進制塊碼。

上述方法中，所述非二進制塊碼為里德-所羅門塊碼。

上述方法中，所述塊編碼操作中的提供所述第三組碼字的一個塊編碼操作實施二進制塊碼。

上述方法中，所述兩個濾波器編碼操作中的至少一個使用咬尾濾波器。