低密度奇偶校驗(ldpc)碼的編碼和解碼的製作方法
2023-04-24 21:36:56 2
專利名稱：低密度奇偶校驗(ldpc)碼的編碼和解碼的製作方法
技術領域：
本申請針對用於出於檢測和/或校正二進位數據中的錯誤的目的而對數 據進行編碼和解碼的方法和裝置，例如，通過使用諸如低密度奇偶校驗 (LDPC)碼之類的奇偶校驗碼。
背景技術：
糾錯碼在通信和數據存儲系統中是普遍存在的。近年來，對稱為低密 度奇偶校驗(LDPC)碼的一類代碼逐漸產生非常大的興趣。
通常採用被稱為特納圖(Tanner graph)的二分圖(bipartite graph)來表示 LDPC碼，在所述二分圖中， 一組節點，即可變節點，對應於碼字的比特， 而另一組節點，即約束節點，有時稱為校驗節點，對應於用於定義所述代 碼的一組奇偶校驗約束。所述圖中的邊連接可變節點和約束節點。如果可 變節點和約束節點通過所述圖中的邊相連，則所述可變節點和所述約束節 點被稱為鄰居。為了簡單起見，通常假設一對節點通過最多一條邊相連。
若且唯若對於每個約束節點，與約束節點相鄰的比特(經由它們與可變 節點之間的關聯)的求和模2為0， gp，它們包括偶數個比特時，與所述可 變節點一一關聯的比特序列是所述代碼的碼字。
在一些情況下，可以對碼字進行打孔。這指的是從所述碼字移除或打 孔某些比特而並不實際發送它們的動作。然而，當對LDPC碼進行編碼時， 仍然確定要被打孔的比特。因此，打孔對編碼過程的影響較小或沒有影響。 為此，在本申請的剩餘部分中將不考慮打孔的可能性。
9通過在所述圖內沿著所述邊交換消息並且通過基於輸入的消息在所述
節點處執行計算來更新這些消息，用於對LDPC碼字進行解碼的解碼器和 解碼算法進行操作。這種算法通常被稱為消息傳遞算法。所述圖中的每個 可變節點初始具備有被稱為接收值的軟比特，所述接收值用於指示通過來 自例如通信信道的觀測所確定的關聯比特值的估計。所述編碼過程還部分 地沿著所述圖的邊來進行操作，但是所述連接不夠準確。
與節點(即，可變節點或約束節點)相連的邊的數目被稱為該節點的度。 正則圖或正則碼是所有可變節點都具有相同的度j而所有約束節點都具有 相同的度k的圖或代碼。在這種情況下，所述代碼是(j,k)正則碼。這些代碼 最初由Gallager發明(1961年)。與"正則"碼相反，非正則碼的約束節點和 /或可變節點具有不同的度。例如， 一些可變節點的度可以為4，另一些可 變節點的度可以為3，以及又一些可變節點的度可以為2。
儘管非正則碼的表示和域實現更為複雜，但是己經表明，與正則LDPC 碼相比，非正則LDPC碼可以提供更好的錯誤校正/檢測性能。
儘管對於要被實踐來在寬範圍的設備(例如，消費設備)中使用的編碼和 /或解碼系統而言，編碼效率和高數據速率是重要的，但是能夠以合理的成 本實現編碼器和/或解碼器也是重要的。因此，需要例如就硬體成本而言有 效率地實現用於錯誤校正和/或檢測目的的編碼/解碼方案。
發明內容
一個特徵提供用於對數據進行編碼的裝置和方法。特別地，提供了用 於使用低密度奇偶校驗(LDPC)碼來對數據進行編碼的方法，所述LDPC碼 能夠採用二分圖表示。為了對所述數據進行編碼，可以生成多個低度可變 節點的累加鏈。所述累加鏈隨後可以被閉合來兩次形成環， 一次使用低度 可變節點，而一次使用比該低度可變節點更高的較高度可變節點，其中該 較高度可變節點包括非閉環邊。在一個實施例中，所述多個低度可變節點 可以在每條邊上具有相同的置換(permutation)。
在所述方法中，所述多個低度可變節點可以包括多個核度為2的可變 節點，所述較高度可變節點可以包括核度為3的可變節點，所述低度閉環 可變節點可以包括核度為2的閉環可變節點。所述方法還可以包括使用提升圖(lifted graph),所述提升圖包括所述 累加鏈的多個置換副本、所述低度閉環可變節點的多個置換副本以及所述 較高度閉環可變節點的多個置換副本。
所述方法還可以包括使用循環提升後的低密度奇偶校驗(LDPC)碼， 在所述循環提升後的LDPC碼中，對於一些基本可變節點，所述提升後的 可變節點中的一半可以是信息節點， 一半可以是奇偶節點。
所述方法還可以包括使用核度為3的編碼節點的非閉環邊上的非閉 環邊置換，其中所述非閉環邊置換可以為O，並且對於在參與所述環的核度 為2的可變節點的邊上的所有其它置換，使用值0或-1 mod 2n。
類似地，提供了一種裝置，所述裝置包括通信接口和處理器。所述通 信接口可以被配置來接收和發送數據。所述處理器可以被配置來(a)生成多 個低度可變節點的累加鏈，以及(b)閉合所述累加鏈來兩次形成環， 一次使 用低度可變節點， 一次使用較高度可變節點，所述較高度可變節點高於所 述低度可變節點，其中，所述較高度可變節點包括非閉環邊。
所述裝置還可以包括使用提升圖，所述提升圖包括所述累加鏈的多 個置換副本、所述低度閉環可變節點的多個置換副本以及所述較高度閉環 可變節點的多個置換副本。
所述裝置還可以包括使用循環提升後的低密度奇偶校驗(LDPC)碼， 在所述循環提升後的LDPC碼中，對於一些基本可變節點，所述提升後的 可變節點中的一半可以是信息節點， 一半可以是奇偶節點。
所述裝置還可以包括使用核度為3的編碼節點的非閉環邊上的非閉 環邊置換，其中所述非閉環邊置換可以為0，並且對於在參與所述環的核度 為2的可變節點的邊上的所有其它置換，使用值0或-lmod2n。
相應地，提供了一種裝置，所述裝置包括(a)用於生成多個低度可變節 點的累加鏈的模塊，以及(b)用於閉合所述累加鏈來兩次形成環的模i央，一 次使用低度可變節點， 一次使用較高度可變節點，所述較高度可變節點高 於所述低度可變節點，其中，所述較高度可變節點包括非閉環邊。
所述裝置還可以包括用於使用提升圖的模塊，所述提升圖包括所述 累加鏈的多個置換副本、所述低度閉環可變節點的多個置換副本以及所述 較高度閉環可變節點的多個置換副本。所述裝置還可以包括用於使用循環提升後的低密度奇偶校驗(LDPC) 碼的模塊，在所述循環提升後的LDPC碼中，對於一些基本可變節點，所 述提升後的可變節點中的一半可以是信息節點， 一半可以是奇偶節點。
所述裝置還可以包括用於使用核度為3的編碼節點的非閉環邊上的 非閉環邊置換的模塊，其中所述非閉環邊置換可以為O,並且對於在參與所 述環的核度為2的可變節點的邊上的所有其它置換，使用值0或-1 mod 2n。
類似地，提供了一種處理器可讀介質，所述處理器可讀介質具有可在 編碼器上運行的一個或多個指令，用實現於使用低密度奇偶校驗(LDPC)碼 來對數據編碼，所述LDPC碼可以由二分圖表示，當由所述處理器執 行時，所述指令使得所述處理器(a)生成多個低度可變節點的累加鏈，以及 (b)閉合所述累加鏈來兩次形成環， 一次使用低度可變節點， 一次使用較高 度可變節點，所述較高度可變節點高於所述低度可變節點，其中，所述較 高度可變節點包括非閉環邊。
類似地，提供了一種處理器，所述處理器具有處理電路，所述處理電 路被配置來執行功能來實現(a)生成多個低度可變節點的累加鏈，以及(b)閉 合所述累加鏈來兩次形成環， 一次使用低度可變節點， 一次使用較高度可 變節點，所述較高度可變節點高於所述低度可變節點，其中，所述較高度 可變節點包括非閉環邊。
根據下面結合附圖闡述的詳細描述，本發明的特徵、特點和優點將變 得更加顯而易見，在整個所述附圖中，類似的參考標記相應地表示相同的 部件。
圖1例示長度為10的正則LDPC碼的小二分圖表示； 圖2是圖1中圖形例示的代碼的矩陣表示； 圖3是小LDPC碼的圖形表示；
圖4例示了圖3中圖形例示的小LDPC碼的奇偶校驗矩陣表示； 圖5例示了用於對圖3中例示的LDPC碼進行編碼的預前處理的實例； 圖6例示了用於使用預先計算出的矩陣來對信息塊進行編碼的過程； 圖7例示了作為與圖3中示出的LDPC碼對應的兩個簡單指令/操作的序列的編碼過程；
圖8例示了通常的LDPC編碼器；
圖9例示了長度為10的正則LDPC碼的大二分圖表示；
圖10例示了圖9中例示的LDPC圖的奇偶校驗矩陣表示；
圖11例示了用循環置換矩陣來替換圖9中示出的3x3單位矩陣的效果;
圖12例示了在經歷循環置換後，如何從可變節點側開始按照順序列舉
圖11中示出的代碼中的邊，以及如何從約束節點側開始呈現所述相同的邊; 圖13例示了用於對圖11中例示的LDPC碼進行編碼的可能的前處理
步驟；
圖14例示了在給定圖11中例示的示例性LDPC碼的預先計算出的矩 陣時，用於對信息塊進行編碼的過程；
圖15例示了作為一序列操作的LDPC編碼過程；
圖16例示了用於對圖7中的編碼器進行矢量化的LDPC編碼器；
圖17例示了基本圖的奇偶校驗矩陣；
圖18例示了基本編碼結構的特納圖19例示了圖17的圖的更為完整的基本圖的奇偶校驗矩陣表示； 圖20例示了除去度為1的可變節點和相關邊的更為完整的基本圖的奇 偶校驗矩陣表示；
圖21例示了具有附加的度為2的可變節點的基本編碼結構的擴展，所 述附加的度為2的可變節點用於閉合累加鏈來形成環；
圖22例示了圖21的擴展的基本編碼結構的Z=8的提升； 圖23例示了圖22中的圖的擴展；
圖24是例示用於使用低密度奇偶校驗(LDPC)碼來對數據進行編碼的 編碼器的方框圖25例示了在編碼器上運行的示例性方法。
具體實施例方式
在下面的描述中，為了提供對實施例的全面理解，給出了許多具體細 節。然而，本領域普通技術人員將理解的是，可以在沒有這些具體細節的 情況下實現所述實施例。例如，電路可以以方框圖的形式示出以使得實施
13例不被不必要的細節所混淆。在其它例子中，可以詳細地示出公知的電路、 結構和技術，以便不對所述實施例產生混淆。
而且，要注意的是，所述實施例被描述為過程，所述過程被描述為流 程圖、流程圖表、結構圖或方框圖。儘管流程圖可以將所述操作描述為順 序過程，但是所述操作中的多個操作可以並行或同時執行。另外，可以重 排所述操作的順序。當過程的操作完成時，所述過程終止。過程可以對應 於方法、函數、步驟、子例程、子程序等。當過程對應於函數時，所述過 程的終止對應於所述函數返回到調用函數或主函數。
此外，存儲介質可以表示一個或多個用於存儲數據的設備，包括只讀
存儲器(ROM)、隨機存取存儲器(RAM)、磁碟存儲介質、光存儲介質、快閃記憶體 設備和/或其它用於存儲信息的機器可讀介質。術語"機器可讀介質"包括 但不限於，可攜式或固定存儲設備、光存儲設備、無線信道和能夠存儲、 包含或承載指令和/或數據的各種其它介質。
此外，實施例可以採用硬體、軟體、固件、中間件、微代碼或其任何 組合來實現。當採用軟體、固件、中間件或微代碼實現時，用於執行必需 任務的程序代碼或代碼段可以存儲在諸如存儲介質或其它存儲設備的機器 可讀介質中。處理器可以執行所述必需任務。代碼段可以表示步驟、函數、 子程序、程序、例程、子例程、模塊、軟體包、類、或指令、數據結構或 程序語句的任何組合。 一個代碼段可以通過傳遞和/或接收信息、數據、自 變量、參數或存儲器內容，耦合到另一代碼段或硬體電路。信息、自變量、 參數、數據等可以經由任何合適的機制傳遞、轉發或發送，所述任何合適 的機制包括存儲器共享、消息傳遞、令牌傳遞、網絡傳輸等。
結合本文公開的實例描述的各種例示性的邏輯塊、模塊、電路、元件 和/或組件可以採用被設計來執行本文所描述的功能的下述部件實現或執 行通用處理器、數位訊號處理器(DSP)、專用集成電路(ASIC)、現場可編 程門陣列(FPGA)或其它可編程邏輯組件、分立門或電晶體邏輯、分立硬體 組件、或其任何組合。通用處理器可以是微處理器，但是在替換實例中， 所述處理器可以是任何傳統處理器、控制器、微控制器或狀態機。處理器 還可以被實現為計算組件的組合，例如，DSP和微處理器、多個微處理器、 一個或多個微處理器結合DSP內核的組合，或任何其它此種配置。結合本文所公開的實例描述的方法和算法可以直接以硬體、由處理器
執行的軟體模塊或兩者的組合，以處理單元、編程指令或其它指令(direction) 的形式體現，所述方法或算法可以包含在單個設備中或者分布在多個設備 之間。軟體模塊可以駐留在RAM存儲器、快閃記憶體、ROM存儲器、EPROM 存儲器、EEPROM存儲器、寄存器、硬碟、可移動盤、CD-ROM，或本領 域中公知的其它形式的存儲介質中。存儲介質可以與所述存儲器耦合，以 便所述存儲器可以從所述存儲介質讀取信息或者向所述存儲介質寫入信 息。在替換實例中，所述存儲介質可以與所述處理器集成在一起。
LDPC碼
圖1例示了用於確定長度為10且碼率為1/2的(3,6)正則LDPC碼的二 分圖100的實例。長度10指示存在10個可變節點V1-V10 102，每個用碼 字的一個比特X1-X10標識。碼率1/2指示校驗節點的個數為可變節點的一 半，即，存在5個校驗節點Cl-C5 106。碼率l/2還可以指示5個約束是線 性獨立的，如下所述。
儘管圖l例示了與長度為IO的代碼相關聯的圖，但是可以明白的是， 對長度為1000的碼字的圖的表示將複雜100倍。
圖2例示了圖1中示出的LDPC碼的奇偶校驗矩陣表示，其是特納圖(或 二分圖)表示的替換。奇偶校驗矩陣包括對所發送的比特的一組線性約束。 在代碼的該種表示中，通常被稱為奇偶校驗矩陣的矩陣H 202可以包括相 關邊連接、可變節點和約束節點信息。在矩陣H 202中，每列可以對應於 所述可變節點中的一個可變節點；而每行可以對應於所述約束節點中的一 個約束節點。由於在示例性代碼中存在10個可變節點和5個約束節點，所 以矩陣H包括10個列和5個行。如果在所述圖中存在邊，即，如果特定的 可變節點和特定的約束節點是鄰居，則與該特定的可變節點和特定的約束 節點對應的矩陣的項可以被設置為1;否則，所述矩陣的項被設置為O。例 如，由於可變節點V,通過一個邊連接到約束節點d，則矩陣H202的最左 上角為l。然而，可變節點Vs不與約束節點d相連，因此矩陣H202的第 一行的第5個位置為0，這表示對應的可變節點和約束節點不相連。如果矩 陣H 202的行在GF[2](階為2的Galois域)上是線性獨立的矢量，則所述約束可以是線性獨立的。
在矩陣表示的情況下，要被發送的碼字X可以被表示為矢量206，所 述矢量206包括要被處理的碼字的比特Xl-Xn。若且唯若矩陣206和202 的乘積為0， g卩，Hx=0，時，比特序列X1-Xn才可以是碼字。
對LDPC碼進行編碼
對LDPC碼的編碼過程可以是從輸入信息比特到LDPC碼字的映射。 這種映射可以採用多種可能的形式。
在2001年2月的正EE Trans, on Information Theory,第2期第47巻的 第638-656頁上出版的Thomas J. Richardson和Ruediger L. Urbanke的名稱 為"E伍cient Encoding ofLow Density Parity Check Codes"的論文中，詳細 地描述了對LDPC碼進行編碼的通用方案。
本申請的編碼過程可以與用於實現對所述一類LDPC碼進行快速並行 編碼的通用編碼設備一起使用，所述一類LDPC碼可以由美國專利申請No. 09/975，331(現在為美國專利No. 6,633,856)中公開的解碼器支持。在專利 6,633,856中，考慮特定結構的一類LDPC碼，並且為該類LDPC碼提供解 碼器架構。在本申請中，該解碼器架構的特定特徵可以再現為編碼器結構 的一部分。
在本申請的編碼過程中，mxn奇偶校驗矩陣可以具有iiKn和秩m，即 行是線性獨立的。當m〉n時，冗餘行可以被移除，而不會改變所述代碼。
首先，將描述作為設計編碼器的過程的一部分的特定操作。如下描述 的前處理計算可以在軟體中作為代碼設計的一部分來執行，並且可以不是 編碼器的實際實現的一部分。
編碼器的設計的第一步驟可以是重排行和列，以將矩陣H置為合適的 下三角形式。
formula see original document page 16
其中，A是(附-g)X(" —7W) , B是(附-g)xg， T是(附-g)x(附-g) ， C是 gx(n-/n)， D是gxg， E是gx(m-g)。矩陣T可以是下三角矩陣，其中所有對角項等於l。將矩陣H左乘
，得到
^ 醜 r
接著，-可以被定義為- = (-ET-力+ D)且是非奇異的。隨後，可以計算 和保存矩陣f。在-不可逆的情況下，H的行可以被認為是線性獨立的，
並且在子矩陣
C D
內部置換所述列，以確保-是不可逆的。如果H的行
不是線性獨立的，則可以移除H的一些行，以便剩餘行可以是線性獨立的， 而不會改變代碼的定義。應該注意的是，所有上述計算可以是與要被編碼 的數據無關，可以是編碼過程的一部分。這些步驟可以作為編碼器設計的 一部分正常地執行一次，並在編碼器使用期間可以或可以不重複。
將數據編碼為碼字
碼字可以被表示為x-(s,pl,p2)，其中S可以表示系統部分，組合的pl 和p2可以表示奇偶部分，pl可以具有長度g，而p2可以具有長度(m-g)。 編碼問題是在給定s的情況下找到pl和p2。限定等式Hx、T可以被自然 地分裂為下述兩個等式
(-ET-1 A + C)sT + (-ET"B + D)pf = 0
根據上述等式，可以得出p〖z-^(-ET-'A + C)/。由於所有矩陣是稀疏 的，所以可以有效地計算出(-ET"A + C)s1，並且在給定j/的情況下，可以
通過對等式rz-x/進行求解來使用z回代，有效地找到r-^/。矩陣f通
常可以是密集的，但是可以通過設計來使得g非常小，並且可以預先計算
出該矩陣。因此，可以有效地得到^。現在，可以通過求解2>〖=」滻-5, 來容易且有效地確定W (參見圖6和7)。
上述描述提供了用於對任何LDPC碼進行編碼的方法。可以明白，LDPC 碼的許多構造可以產生其它固有的編碼機制，例如，RA碼。
本申請提供了並行編碼器，該並行編碼器可以使用二進位碼的編碼方 法，諸如如上所述的，並且將它們和奇偶校驗矩陣一起提升為"矢量化的"
17LDPC碼的並行編碼引擎。提升是一種用於根據小的"基本碼"的若干副本 來生成大的LDPC碼的技術，所述小的基本碼是小的奇偶校驗矩陣，大小 為(no,ko)。它可以實現並行編碼和解碼算法以及減少大代碼的描述複雜度。 在名稱為"Methods and Apparatus for Decoding LDPC Codes"的美國專 利申請No. 09/975,331，現在為2003年10月14日授權的美國專利No. 6,633,856，中，描述和推動了結構化矢量化的一類LDPC圖。在專利 6,633,856中，所述推動用於提供高效解碼器架構。本申請針對可以適用於 對與專利6,633,856中的代碼的類別相同的一類代碼進行編碼的對應架構。 然而，與專利6,633,856不同，本申請可以包括可以有效且並行地執行的編 碼操作，並且因此所述架構可以允許對特定LDPC碼的規格進行編程。
小LDPC圖
圖3例示了簡單非正則LDPC的圖300。所述代碼的長度可以為5，由 5個可變節點VI到V5 302指示。4個校驗節點Cl到C4 306可以通過總共 12條邊304耦合到可變節點302。
圖4例示了使用矩陣402、 404以奇偶校驗矩陣形式的圖3中示出的 LDPC碼。可以在置換矩陣H 402中，使用l來表示邊。比特xi可以與可 變節點W相關聯。
圖5和圖6例示了圖3中示出的LDPC碼的編碼過程。如上所述，編 碼前處理步驟可以包括將圖4中示出的奇偶校驗矩陣H 404的行和列重排 為下三角形式。圖5例示了對圖4中的矩陣的重排的實例。可以通過交換 第2行和第4行來對所述矩陣進行重排。
在圖5中，矩陣H 501示出了重排後的不同分量。出於注釋的目的， 子矩陣(rl，r2;cl，c2)可以被定義為包括原矩陣中的行索引在[rl,r2]中以及列 索引在[cl，c2]中的所有項。矩陣A 502可以被定義為矩陣H 501的子矩陣 (1，3;1,1)。矩陣B 503可以被定義為矩陣H的子矩陣(1，3;2，2)。矩陣T 504 可以被定義為矩陣H的子矩陣(1，3;3，5)，其可以是下三角形式。矩陣C505 可以被定義為矩陣H的子矩陣(4，4;1，1)。矩陣D 506可以被定義為矩陣H的 子矩陣(4,4;2，2)。矩陣E 507可以被定義為矩陣H的子矩陣(4，4;3，5)。在508 中例示了採用Gaussian排除法來導出—(-￡廠力+巧，其中可以獲得- 509
18和其逆--' 510。
圖6例示了在給定信息塊^[1] 601和圖5中示出的預計算出的矩陣的 情況下的實際編碼過程。標準的矢量與矩陣的相乘可以允許計算A 602、 r、 603、,^ 604、 f廠^+Cy 605、 ；j, -'Cfin+C" 606、浙607、 608和/72=廠'(^+A) 609。應該注意的是，可以通過使用回代來 執行與r-'的相乘。在最後的結果中，可以在矢量610中示出編碼後的比特
二進位矢量和二進位矩陣的相乘可以被分解為簡單操作序列。例如，
考慮在硬體處理器中將二進位矩陣U(mxn)與二進位矢量v(nxl灘乘。可 以假設在相乘之前，可以在開始於索引s的一些物理位置，例如存儲器，獲 得矢量v，並且結果可以存儲在開始於索引t的位置。此外，可以假設矩陣 U的行/， /e
，在被索引為/,,1,/,,2，...，/"的列處具有非0項，艮卩，1。可 以如下定義兩個指令(l) (0 ab)和(2) (1 ab): (0 ab)可以指示處理器讀出位置 b處的值，並將該值寫入到位置a; (1 ab)可以指示讀出位置b處的值，並 將其添加到位置a，即與位置a處的當前值異或。換言之，第二個操作可以 累加位置a處的值；第一個操作重寫位置a處的值。現在，矢量v與U的 相乘可以被分解為這兩個簡單操作的下述序列(Ots+Z。，,),(1 ts+/。，2)， ...，(l ts+/。,t。)； (0t+l s+/u)，(l t+l s+G),…，(1 t+l s+");…；(0t+m-l s+/ —u)， (1 t+m-l s+/ —12)， ...， (1 t+m-l s+/ —1A ,)。指令的總數目可以與矩陣中的非零 項的數目相同。
圖7例示了作為與圖3中示出的LDPC碼對應的兩個簡單指令/操作序 列的編碼過程。存儲器設備702可以存儲信息比特、編碼比特和中間變量。 存儲器702的位置0可以被分配來存儲單個信息比特s 710;位置1可以被 分配來存儲奇偶比特^'712;位置2到4可以被分配來存儲奇偶比特^714。 另外的存儲器空間可以被提供來保持中間值。示例性存儲器902可以提供 位置5到7來存儲A 716的值以及稍後存儲斷+A的值；它可以提供位置 8到10來存儲廠^ 718;以及可以提供位置11來存儲WMy 720。
相對於存儲器702的上述分配，作為與矢量間的矩陣乘法的圖6中例 示的編碼過程可以被分解為表704中列出的操作(O ab)和(l ab)的序列。為 了清楚起見，表704示出了指令序列(每行一個)以及它們的相應的矩陣乘法對等方。例如，乘法A可以被分解為兩個指令(0 5 0)，其後為(0 7 0)。表 706示出了在執行表704中的對應行中示出的指令時存儲器位置0到11的 內容。執行表704上的指令的結果可以在表706的下一行中示出。例如， 通過將"[1]存儲在位置0中，如表706的第一行中所例示，可以如圖5中 所示來對相同的信息比特進行編碼。執行其後為指令(O 7 O)的指令(O 5 O)的 操作可以給出從5到7的位置中的結果A=(l 0 1)，如塊706的第3行中所 示。這可以是與圖5中的其對等方相同的結果。表706例示了在執行表704 中的基本指令序列時針對存儲器位置O到11的內容的完整編碼過程。
表704的序列指令可以被容易地轉化為硬體實現。在硬體實現期間可 以進行簡單的修改，以例如符合所使用的硬體的存儲器操作約束。
通用LDPC編碼器
圖8例示了通用LDPC編碼器800。單元操作處理器808可以執行由所 接收的指令指示的三種可能的操作中的一種。所述單元操作處理器808可 以將求和比特清零，將求和比特與從存儲器讀取的比特進行異或或者將求 和比特輸出到編碼存儲器806。要執行的操作可以由編碼器控制模塊800中 的操作控制模塊810上的操作來選擇，並且以一個或多個指令的形式指定 給單元操作處理器808。讀/寫控制模塊804、編碼器控制模塊800可以指定 訪問編碼存儲器806的順序。操作控制模塊810和讀/寫控制模塊804兩者 的定時形式可以由編碼器控制模塊800中的編碼器定時控制模塊802控制， 該編碼器定時控制模塊802通過定時控制信號確定編碼器的數據流。編碼 存儲器806可以是雙埠存儲器塊，其可以通過使用SIMD讀或寫指令而 被獨立地寫入或讀取。
編碼過程的矢量化
在給定矢量化的LDPC圖的情況下，本申請的編碼過程可以被如下矢 量化。所述編碼器可以如同它正在同步且並行地對所投影的LDPC碼的Z 個副本進行編碼一樣進行操作。對編碼過程的控制可以對應於所投影的 LDPC圖，並可以在所述Z個副本之間共享。因此，所述編碼器可以被描 述為對若干個比特矢量進行操作，每個矢量具有Z個元素。對Z個投影圖的完全分離地並行編碼的一個變型可以是在編碼過程期間，在比特矢量內 對比特進行重新排序。這種重新排序操作可以稱為旋轉。所述旋轉可以實 現由^定義的置換操作，其中^可以表示用於定義所述置換的組。由於所述
旋轉，投影圖的z個副本的處理路徑可以混合，由此將它們連結以形成單
個大圖。可以獲得用於指定所述旋轉的控制信息以及投影圖的控制信息。 幸運的是，所述旋轉控制信息可以使用相對小的存儲器來指定。
儘管各種置換可以用於所述旋轉，但是使用循環置換特別值得關注， 因為利用它可以容易地實現此種置換。為了簡單起見，可以假設甲包括循
環置換的組。在這種情況下，大LDPC圖可以被約束為具有準循環結構。 出於該實例的目的，W可以是圖中的可變節點的數目，M可以是圖中的約 束節點的數目。可以假設iV和M都是Z的倍數，iV-"Z和M-附Z,其中Z 可以表示循環的階數。
節點可以通過使用雙索引來標識。因此，可變節點 可以是投影圖的 第i個副本的第j個可變節點。由於^是循環置換的組，所以若且唯若對於 hl，…，Z，節點v,^^連接到約束節點c。+^^時，可變節點、才可以連接 到約束節點c。"
大LDPC圖
可以參照圖9-16來進一步描述用於使用非常小的圖形表示和旋轉信息 來表示大圖的本申請的技術，所述圖9-16涉及圖3中的圖300的矢量化。 參照這些圖形描述的本申請的技術可以適用於非常大的LDPC圖。
可以通過對圖3中示出的小圖進行複製，即實現多個副本，並隨後執 行旋轉操作來互連所複製的圖的各個副本來生成更大的圖。出於討論的目 的，更大的圖結構內的小圖在下文中將被稱為投影圖。
圖9例示了大圖900，其是對圖3中例示的小圖進行三次並行拷貝的結 果。可變節點卯2'、卯2"和902"，分別對應於第一到第三圖，所述第一到第 三圖是通過對圖3中的圖進行三次拷貝得到的。另夕卜，校驗節點906'、卯6" 和906"，分別對應於第一到第三圖，所述第一到第三圖是通過進行三次拷貝 得到的。應該注意的是，沒有邊連接所述三個圖中的一個圖的節點和所述 三個圖中的另一圖的節點。相應地，這種拷貝過程將基本圖"提升"了三倍，產生三個分離的相同圖。
圖10使用矩陣1002和1004例示了如上討論的拷貝過程的結果。應該 注意的是，為了得到原始圖3的圖的三個副本，圖4的矩陣402中的每個 非零元素使用3x3單位矩陣來替換。因此，矩陣402中的每個l使用3x3矩 陣來替換，以生成矩陣1002，其中所述3x3矩陣中沿著對角線為1而其餘 地方為O。應該注意的是，矩陣1002中的邊的數目是圖4中的矩陣402的 邊的數目的3倍，圖3中示出的基本圖的3個副本的每個具有12條邊。這 裡，變量xij可以對應於可變節點Vij。
編碼器的修改
圖8的編碼器800可以被修改來對如上所述的(Z-3個)並行圖進行編 碼。可以將單元操作處理器1008形成為能夠並行地同時處理3個相同的操 作的矢量單元操作處理器。所述單元操作處理器1008的所有輸出可以被矢 量化，從而承載3倍於原先承載的數據。可以使編碼存儲器1006變為3倍 大，使得能夠在單個SIMD指令的指導下並行地寫入或讀取3個比特。這 些存儲器的輸出可以是3比特寬的矢量。然而，單元操作控制1010、排序(讀 /寫)控制1004和編碼器定時控制模塊1002可以保持與圖8中的相同命名的 元件相同或相似。
旋轉
可以通過利用圖11中示出的3x3循環置換矩陣替換圖10中示出的3x3 單位矩陣中的每個來引入旋轉。應該注意的是，圖ll中使用的循環置換矩 陣可以存在三種可能性。可以通過指示特定置換矩陣在該置換矩陣的第一 行中的第一、第二或第三位置上是否存在1，來指示該置換矩陣替換單位矩 陣。例如，在矩陣1102的情況下，從左上方開始進行到右下角，可以利用 序列(2,2,3,3,1,1,1,3，2,1，2，3)來指定所述旋轉。
圖12例示了在約束節點側執行循環置換(旋轉)的效果。由於所述置換 可以在約束節點側執行，所以可變節點側的邊之間的關係，例如排序，保 持不變，如行1202，、 1202"和1202"'中所示。然而，在所述約束側，所述 置換導致列內的邊，例如特定矢量邊內的邊，被重新排序，如行1204'、 1204"和1204"，中所示。這可以產生與所述投影圖的不同副本對應的節點之間的 互連。
應該注意的是，作為矢量邊置換操作的結果，約束節點Cu現在可以連 接到與邊(1,1)相對的邊(2，1)，約束節點Cu可以耦合到與邊(2,1)相對的邊 (3,1)，約束節點C3J可以耦合到與邊(3，1)相對的邊(1,1)。
通過將開關引入到消息路徑來執行旋轉，可以如圖11中所定義地對 LDPC碼進行編碼。
通過應用如上所述的通用LDPC編碼過程，可以進一步地理解矢量編 碼過程。取代對二進位數據進行處理，所述編碼器可以對Z個比特的矢量 進行處理，所述Z個比特對應於投影圖中的比特的Z個並行副本。奇偶校 驗矩陣H 1102可以包括ZxZ全零矩陣或表示為一，"[G，z—U的ZxZ循環置 換矩陣的項。循環矩陣一與Z比特二進位矢量的相乘可以等價於將所述矢 量右移k個比特。在域GF(2"中，除了當測試-的可逆性時所述矩陣可以首 先恢復到二進位表示之外，可以與二進位數據情形一樣處理所述編碼過程。
編碼過程的實例
圖13和14例示了圖11中示出的LDPC碼的示例性編碼過程。編碼前 處理步驟可以將奇偶校驗矩陣H的行和列重排為下三角形式。在圖13中示 出了一個示例性重排H， 1301。 H， 1301可以通過置換原始矩陣H' 1102的第 2行和第4行來獲得。
在構造編碼器時，前處理可以提取和存儲特定信息。矩陣A1302可以 是矩陣H， 1301的子矩陣(1,3;1,1)。矩陣B 1303可以是子矩陣(1，3;2，2)。矩 陣T 1304可以是子矩陣(1,3;3，5)，其是下三角形式。矩陣C 1305可以是子 矩陣(4，4;1，1)。矩陣D 1306可以是子矩陣(4,4;2，2)。矩陣E 1307可以是子矩 陣(4,4;3,5)。在1308和1309中例示了採用Gaussian排除法得到 - = ET一B + D)，並且隨後計算出它的逆f1 1310。
在給出離線預先計算出的矩陣的情況下，圖14例示了示例性信息塊 s = [100] 1401的實際編碼過程。與矢量間的矩陣乘法計算出矢量Cs 1402、 A 1404、廠^ 1405、五廠、1406、 E廠'Ay + Cs 1407、 A —-(五n + Cs) 1408、浙1409、 1410和; 2="他+刷1411。在1412中示出了所得到的碼字。
類似於上述和圖7中例示的二進位矩陣乘法分解，當結合旋轉，例如， 循環移位，時，域GF(2"中的上述矩陣操作可以被分解為簡單操作序列。可 以如下定義兩個指令(O a r b)和(l a r b): (0 a r b)指示處理器讀出位置b處的 值，將所述值循環左移r，並且將結果寫入到位置a; (larb)指示處理器讀 出位置b處的值，將所述值循環左移r，並將所述結果與位置a處的值相加。
乘法矩陣的分解
當對包括ZxZ循環矩陣或零矩陣的項的矩陣U (mxn)與Z比特數據的 矢量v (nxl)間的乘法進行分解時，可以假設在乘法之前，源數據可以保持 在Z比特數據寬的某一存儲器中的位置s, s+l,.，.，s+n-l處，所得到的數據將 存儲在同一存儲器中的位置t,…,t+m-l處。還可以進一步假設矩陣U的行i， /e
，在列/,,1，/,,2,.,^, ， its[O,Z-l]，具有非零項，艮卩， 一，所述非零 項具有循環移位值",，,，"",...，"a，e[O,Z-l]。在這些假設的情況下，U與v間的 乘法等價於下述操作序列formula see original document page 24指令的總數目與所述矩陣中的非零項的 數目相同。
編碼過程
圖15例示了作為對圖11中示出的矢量LDPC碼進行的一序列操作(Oa r b)和(l a r b)的編碼過程。存儲器1502可以存儲信息比特、編碼比特和中 間變量。存儲器位置O，到ll，中的每個位置的內容在對應的存儲器位置上方 的行1503中示出。存儲器可以具有Z比特數據寬度，即，簡單SIMD指令 的訪問單位為Z比特矢量，並且每個存儲器位置O，到ll'保持Z個比特。存 儲器1502的位置O'可以被分配來存儲單個信息矢量s;位置r可以被分配 來存儲奇偶矢量A;位置2'到4'可以被分配來存儲奇偶矢量^。另外的存 儲器空間可以被提供來保持中間值。存儲器1502可以提供位置5'到7'來存 儲A的值以及稍後存儲^,+A的值；它可以提供位置9'到ir來存儲廠'A;以及可以提供位置12'來存儲E廠1^ 。
相對於存儲器1502的上述分配，作為與矢量間的矩陣乘法的圖14中 例示的編碼過程可以被分解為表1504中列出的操作(O a r b)和(l a r b)的序 列。為了清楚起見，表1504示出了指令序列以及它們的相應的矩陣乘法對 等方。例如，乘法A可以被分解為兩個指令(0510)，其後為(0 7 0 0)。 可以通過將^[100]存儲在位置0中，如表706的第一行中所例示，可以對 與圖14中相同的信息比特進行編碼。執行指令(O 5 1 0)和(0 7 0 O)的操作 可以給出從5，到7，的位置中的結果^=(001，000,100)，與圖14中其對等方 相同。表1506例示了在執行指令序列時針對存儲器1502的內容的完整編 碼過程。
表1504中列出的指令可以被容易地轉化為硬體實現。所述指令集的許 多變型是可能的，包括例如移除所述指令集中的冗餘，將指令添加到所述 指令集中以避免對所述存儲器進行初始化，或者優化所述指令集以符合存 儲器操作特性。此種變型可以被認為在本申請的範圍內。
編碼器
圖16例示了編碼器1600。編碼器1600可以利用旋轉來對編碼器800 進行完全地矢量化。編碼器1600和編碼器800之間的相似性是顯而易見的。 具體地，編碼器控制模塊1612和操作控制模塊1610可以按照與編碼器800 中的它們的對等方802和812相同或相似的方式進行工作。例如，為了對 圖12和13中定義的LDPC碼進行編碼，這些組件的操作與編碼器800中 的它們的對等方在對圖3中的示例性代碼300進行編碼時的操作完全相同。 編碼存儲器1606可以是編碼器800中的它的對等方806的矢量化版本。在 編碼器800中，存儲器存儲單個比特，然而，編碼器1600中的對應存儲器 可以存儲集合，S卩，Z比特矢量。這些矢量可以通過使用SIMD指令作為單 個單元寫入以及讀取。因此，從排序(讀/寫)控制1604發送到存儲器的消息 標識符，即存儲器索引，可以等價於或類似於編碼器800中的那些。除了 編碼器800中的它的對等方804的角色外，排序或讀/寫控制模塊1604還具 有下述其它角色存儲和提供所述置換信息，例如旋轉信息。
在編碼實例300中，編碼器800將多個單個步驟的順序存儲在其排序模塊1004中，其中所述多個單個步驟一起執行一系列矩陣乘法。考慮使用 編碼器1600來對圖11中的代碼進行編碼。所述排序模塊1604可以存儲與 上述相同的順序來在編碼期間訪問Z比特矢量，並且還存儲用於描述與Z 比特矢量的順序相同的順序相關聯的旋轉的順序。該順序用作生成旋轉信 號的基礎，所述旋轉信號被排序模塊1604用來使得開關1616旋轉矢量。 所述矢量單元操作處理器1608與編碼器800中的它的對等方808相同，除 了矢量單元操作處理器1608對Z比特矢量而不是對單個比特進行操作(清 零、累加或輸出)之外。
如上討論的編碼方法和裝置的一些變型可以導致在一些實現時減少復 雜度。下面是可以減少如上討論的控制存儲器1604和編碼存儲器1606兩 者的存儲器要求的一些變型。實現可以結合一個或多個如下所述的變化。
首先，可以簡化指令表示如上所述，在各個實施例中，編碼指令是 兩個基本指令(Oarb)和(larb)的有序序列，當執行所述序列時，產生實際 的編碼。此種指令序列可以通過將某一矩陣與某一矢量的乘法連續地分解 為基本指令序列來生成。 一些示例性分解包括佔壓倒性百分比的下述模式 的子序列(0a 6。)，(la "' 、)， ...，(la ^ ~)。在該子序列中對a的重 復可以是冗餘的。可以通過修改基本指令來容易地去除該冗餘。因此，可 以如下定義兩個新的指令(O 0 a)和(l r a): (1 r a)可以指示處理器讀出位置a 處的值，將該值循環左移r，並將該值與累加器中的當前值進行異或；(0 0 a) 可以指示處理器將累加器中的當前值寫入到位置a，並將累加器中的值復位 為0。從舊指令到新指令的轉換可以如下(Oarb)可以被轉換為(l rb)和(OO a); (1 arb)可以被轉換為(l 0a)、 (lrb)和(00a)。按照這個規則，示例性序 列(O a ^ 6。)， (1 a ri 6')，…，(1 a ^ 、)可以轉換為(1 r° 6°)， (1 ri 、)，...，(l ^ 60，和(00a)，從而去除所述冗餘。按照這種方式對指令集 進行轉換可以減少實現所述編碼存儲器1606所需要的存儲器的量。
接著，可以減少指令集的基數(cardinality):當將LDPC編碼看作矩陣 和矢量乘法的序列1600時，編碼過程可以被粗分為3個階段。在第一階段， 可以通過先求解乂Z然後求解7^-^4/來得到r-U/;在第二階段，可以得到 P)T;在最後階段，在給定P'T的情況下，可以通過求解7>〖="/-^^來得到 W，這可以通過使用回代來有效地完成。在原始形式中，每個階段中的矩陣和矢量乘法可以被分解為指令子集。這些三個子集的順序級聯可以是完 整的指令集，並且所述指令集的結束暗示編碼過程的結束。然而，在第一 階段和最後階段之間共享指令子集是可能的，並且從而可以減少指令集的 基數。
可以注意到，如果P "被初始化為O，則可以通過求解7>〖=-^/-5/^來
得到r-U/。接著，可以定義要成為最後階段和第二階段的指令子集的級聯
的指令的順序。因此，編碼可以包括1)將P^初始化為0; 2)運行最後階段 的指令子集(得到廠M/); 3)運行第二階段的指令子集(得到P。； 4)再次運行 最後階段的指令子集(得到p)。
這種指令集共享可以減少編碼器控制設備1612中的存儲器，並且因為 r-^/現在可以保存在的位置處並且可以不需要保存，所以它還可以減少 編碼存儲器1606。
基本編碼結構
圖17例示了奇偶校驗矩陣1700(包含圖形符號的塊指示1，沒有圖形符 號或空塊指示0)，圖18例示了特納圖，它們都是基本編碼結構A的表示， 如下所述。當圖18中的圖被提升時，矩陣(這裡被描述為方陣)中的每個項 可以變為置換矩陣或零矩陣。零矩陣對應於空塊，而置換矩陣對應於具有 圖形符號的塊。在循環提升的情況下，所述置換矩陣可以是循環置換矩陣。 應該理解的是，在作為奇偶校驗矩陣的結構的表示中，行和列可以被顯示 為被置換。類似地，特納圖可以以置換的方式顯現。此外，所述矩陣和所 述圖可以是較大的結構的子矩陣和子圖。
投影圖還可以被公知為基本圖。完整圖可以被公知為提升圖。所述提 升圖可以通過製作基本圖的Z個副本並在所述副本間置換相似的邊來獲得。 為了簡單起見，關注循環置換。
基本圖中具有的簡便的編碼結構可以是度為2的可變節點的累加鏈與 度為3的單個可變節點。所述結構主要包括單環1800，所述單環1800穿過 所述累加鏈中的所有度為2的可變節點VrV9以及所述度為3的可變節點 Vp所述度為3的可變節點上的邊中的兩條邊(1802,1804)參與所述環。所 述度為3的可變節點V,上的第三邊1806可以屬於所述環外的任意校驗節點，從而使得相關聯的奇偶校驗矩陣可逆。(在圖18中，校驗節點可以包括 CrC9)。這種編碼結構可以稱為基本編碼結構A，並在圖18中示出。在一 些實施例中，所述度為3的節點V,可能不形成包括所述累加鏈中的所有度 節點的環。這種編碼結構可以稱為基本編碼結構B。因此，基本編碼結構A 可以是基本編碼結構B的特殊情形。
基本圖的核可以包括上述結構以及可以與參與上述環的約束節點相連 的其它可變節點。可以存在根據屬於所述基本圖1900的核的可變節點所形 成的其它奇偶校驗比特，如圖19中所示。
一旦所有其它比特被確定，對度為1的可變節點的編碼可以非常簡單。
因此，對於編碼，首先關注的可以是除去這些節點的結構。圖20給出與圖 19對應的不包括所除去的節點的實例2000。當所述核包含基本編碼結構A 作為子結構時，如圖19中的實例，則使用基本編碼結構A可以要求將其它 可變節點設置為信息節點，其也可以稱為系統節點。根據所述信息比特分 配與這些節點相關的比特的值。隨後，可以計算與基本編碼結構A相關聯 的比特，以完成所述編碼。 一旦確定基本編碼結構A中的所述度為3的可 變節點的值，則通過簡單巻積型處理確定所述累加鏈比特。如果添加GF[2] 上的所述核基本圖中的所有約束，即，在編碼時，從約束節點到可變節點 的偶數個邊等於0個邊，而從約束節點到可變節點的奇數個邊等於1個邊， 則可以觀察到，基本編碼結構A中的度為3的節點可以寫入作為對所述核 基本圖中的具有奇數度的信息可變節點的簡單奇偶校驗。
如果在圖被提升時，與所述累加鏈中的度為2的可變節點相關聯的每 對邊被賦予相同的提升值，則可以為所述核提升圖預留所述核基本圖的如 上所述的關鍵特性。特別地，除了現在以逐塊的方式之外，類似於向基本 圖添加約束，添加所提升的奇偶置換矩陣，與所述累加鏈中的度為2的節 點相關聯的邊有效地彼此消除，留下度為3的提升後的可變節點作為信息 提升節點的奇偶校驗。所得到的與度為3的可變節點相關聯的矩陣為矩陣 (D。
在提升基本編碼結構B的一個實施例中，與度為3的節點相關聯的邊 中的兩條邊上的旋轉值可以採取形式^和s + L/4，而第三邊採取任意的不同 值。這裡，s是任意的整數，而L是提升尺寸。在這種情況下，矩陣(D-'可
28以被證明是最多9個置換矩陣的和，即，與①-'的乘法包括對矢量最多置換 9次，並且相加最多9個副本。這種編碼結構可以稱為提升後的編碼結構B。
在提升基本編碼結構B的另一實施例中，與度為3的節點相關聯的環 邊中的兩條邊上的旋轉值可以採取形式^和s+L/2 ，而第三邊採取任意的不 同值。在這種情況下，矩陣0-i可以被證明是最多3個置換矩陣的和，艮P， 與。-'的乘法包括對矢量最多置換3次，並且相加最多3個副本。這種編碼 結構可以稱為提升後的編碼結構C。
在提升基本編碼結構B的另一實施例中，與度為3的節點相關聯的邊 中的兩條邊上的旋轉值可以採取值"而第三邊採取任意的不同值。在這種 情況下，矩陣0)一可以被證明是單個置換矩陣，即，與0-'的乘法包括僅僅 一個簡單置換。這種編碼結構可以稱為提升後的編碼結構D。
應該注意的是，提升後的編碼結構B、 C和D可以都是對基本編碼結 構B的提升。在一些實施例中，度為3的節點的兩個指定邊可以是基本編 碼結構A中的度為3的節點的兩條環邊。在提升後的編碼結構B、 C和D 中，D可以具有最小的複雜度，而B可以具有最大的複雜度，C可以在兩 者之間。相反，B的優點是，在提升圖中，通過度為2的節點的環還可以 通過4個度為3的節點，這可以改進圖的性能，尤其是在高信噪比時。與 之形成對照，在結構C中，通過度為2的鏈的環可以通過僅僅兩個度為3 的節點，而在結構A中，它可以通過僅僅一個度為3的節點。因此，編碼 結構B、 C和A可以提供性能和複雜度之間的不同折衷。
對於編碼結構B的大多數提升版本，在對與所述累加鏈相關聯的置換 的上述約束的情況下，矩陣①將是三個置換矩陣的和。如果度為3的節點 的邊中的兩條邊具有相同的置換，則矩陣O可以是置換矩陣。這可以是提 升後的編碼結構D的情形。如果提升後的編碼結構D是基本編碼結構A的 提升，並且具有相同置換的邊是度為3的基本節點的兩條提升後的環邊， 則這種結構可以稱為提升後的編碼結構A。如果與剩餘的未刪除的邊相關 聯的旋轉為0，或者如果O是單位矩陣，則所述結構可以稱為具有等同性 (identity)的提升後的編碼結構A。
對於解碼器中的大並行度，具有大值的提升尺寸Z是有利的。對應地， 可以期望具有小的基本圖。這可能在使用上述編碼結構時產生難度。特別地，如果基本圖小，則累加鏈可以非常短。當使用提升後的編碼結構A時， 可以產生Z個環，所述環包括所述提升後的度為3的可變節點的一個副本 和其長度為基本圖累加鏈的度為2的節點的鏈。因此，這種編碼環非常短， 並且這可以導致代碼的性能差。
這裡所呈現的結構可以允許有效地增加從L到2L+1的編碼環中的累加 鏈，同時保持小的基本圖。在利用提升尺寸Z擴充基本圖後，所述編碼結 構A可以顯示為基本圖的大小為2倍且提升尺寸為Z/2的結構。這種擴充 不會改變所述圖，僅僅改變作為基本圖和提升的解釋。
整數集(0，…,Z-1)是集合(0,2，…,Z-2〉和集合(U，…,Z-1〉的交織。可以通過 向右循環移位S來執行對隊..，Z-l)的循環置換，並且對{0,...，2-1}的循環置 換可以等效地表示為偶數元素{0，2，...,Z-2}和奇數元素{1，3，...,Z-1}的循環置換 和兩者的交織。如果S是偶數，則對所述序列的再交織可以開始於偶數子 集；如果S是奇數，則對所述序列的再交織可以開始於奇數子集。偶數序 列的循環移位可以為K，其是最多為S/2的最大整數，而奇數序列的循環移 位將是S-K。
開始於作為對基本圖的尺寸為Z的提升的圖，每個基本圖節點可以被 複製， 一個是偶數節點，而另一個是奇數節點，將提升尺寸減小到Z/2，並 且使用上述的表示，準確地再生與具有兩倍於原始尺寸的尺寸為Z/2的基本 圖的提升相同的圖。如果在原始圖中，提升後的可變節點通過置換S與提 升後的校驗節點相連，則在對所述節點進行複製後，如果S是偶數，則可 變節點的偶數副本可以連接到校驗節點的偶數副本，而可變節點的奇數副 本可以連接到校驗節點的奇數副本。如果S是奇數，則偶數可變節點可以 連接到奇數校驗節點，而奇數可變節點可以連接到偶數校驗節點。與這兩 條邊相關聯的提升可以是K和S-K。
其目標是使提升後的編碼結構A顯示為這種兩倍於基本圖大小的進行 Z/2提升後的結構。因此，所述編碼結構應該隱含在原始的經過Z提升後的 較小的基本圖結構中。
為了實現這，將用於閉合累加鏈的所述環的另一度為2的節點添加到
30基本編碼結構A中。在基本圖中，這個節點的邊平行於度為3的節點的邊 中的兩條邊。當執行所述提升時，這個節點上的邊可以採取整數值A和A-l ， 所有值被解釋為對Z求模。按照這種方式，在基本圖的Z個副本中出現的 通過度為2的節點的Z個環變為單個環的Z倍長。除了在編碼結構中的度 為3的可變節點的環邊上的這種循環置換為整數B-1與B模Z之外，其中， 在所述基本圖中，所述B-l置換可與連接到與具有提升值A的度為2的環 可變節點上的邊相同的約束節點的邊相關聯。在這種結構的情況下，如上 所述，可以擴充所述基本圖，並且可以將所述提升尺寸減半，從而所得到 的圖將包含提升後的編碼結構A,在該提升後的編碼結構A中，另一度為 2的可變節點的一個副本現在參與所述編碼結構，而其它副本不會參與所述
編碼結構；並且度為3的可變節點的兩個副本中的一個參與所述編碼結構， 而另一副本不會參與所述編碼結構。
這裡，可以進行一些概括。首先，暫時假設提升Z是2的冪，當對基 本圖進行擴展時，可以將提升值S的LSB移入到基本圖中。可以使用不同 的比特。如果使用第k個比特(目前k^0)，貝lj取代上述A-l和B-l，將得到 A-2k和B-2k。在這種情況下，所述提升後的累加結構不能形成單個大環， 而是形成若干個環。其次，儘管這種關注集中在2的冪，但是對於Z，可以 使用其它值。通常，可以按照這種方式將基本圖增加因子F，只要F是Z 的因子。
一些代碼設計中期望的另一特性是提升的縮放性(scalability)，艮P，可以 採用不同的提升尺寸Z來使用相同的基本圖。而且，通常可以從單個提升 中導出不同尺寸的提升。特別地，可以關注於支持作為2的冪的Z值，所 述Z值從16直到512或1024。另一目標是在所述縮放下保留上述的編碼結 構。這限制了縮放參數。可以提供一種縮放規則，在該縮放規則中，定義 最大提升尺寸的提升，並且通過從所述提升值中移除合適數目的LSB來導 出較小的提升。這種縮放定律通常可以如下表述。如果S是與提升尺寸Zmax 相關聯的提升，則與提升尺寸zi相關聯的提升可以是最大整數，最多為8* Z1/Zmax。期望在縮放下保留所述編碼結構。存在兩個特定的提升值數目， 即O和-l mod2n，其在這種類型的縮放下總是保留。因此，如果所述編碼 結構僅僅使用這兩個值，則它將在縮放下保留。因此， 一個選項是在度為3的節點的環邊上具有提升值O和-l，而在非 環邊上具有任意值。當這種基本圖被擴充2倍時，它具有提升後的編碼結 構A。在採用所有2的冪進行的縮放下，這種結構可以保留，因為值0和-l 可以在此種縮放下保留。此外，現在可以使用提升後的編碼結構A，這意 味著在擴充後的圖中，0>-'是置換矩陣。
另一可能期望的特徵是度為3的編碼節點的非環邊上的置換為0，艮P, 具有等同性的提升後的編碼結構A。這與具有0或-l的值且在所述圖中同 時避免低度可變節點的短環的編碼結構中的所有其它循環置換相衝突。
然而，如果對所述編碼結構的保留僅僅局限於比2大的一些最小的提 升尺寸，例如16，那麼可以使用除O和-l之外的值。
度為2的提升環結構和度為3的編碼列的主要特徵是對於某一整數K， 提升置換採用值K和K-1。對於降至尺寸2的所有提升，僅僅K-0可以保 留這一點。然而，如果降至尺寸為16的提升，仍要保留這種特性，則對於 K可以選擇不同值。如果K的長度為n比特，對應於Z-2"，其中n大於或 等於4，則可以選擇K的n-3個LSB為0，而其它為任意值。遵循K-lmod 2"的n-3個LSB為1 。在這種情況下，保留以1區分的提升值的主要特徵。 例如，如果K是此種n比特數，並且J是給定的m比特數作為開始的m個 比特，換言之，K的m個MSB，其中m是4或更大，貝lj J-l mod 2"等於 K-l mod 2"的m個MSB。換言之，如果從K和K-l中丟掉n-m個LSB， 則結果是J與J-1 mod 2""的二進位表示。這可以用來設置編碼結構中的度 為3的非環邊上的置換，從而在擴充後的編碼結構中，參與提升後的編碼 結構A的編碼的度為3的可變節點的副本具有採用置換值0提升的非環邊。 因此，所述擴充後的編碼結構是具有等同性的提升後的編碼結構A。其中 最後n-3個比特為0的n比特數將被稱為n-3 0比特數。
圖21例示了基本編碼結構A的擴展，其具有可變節點、-V4和約束節 點d-C4以及另一度為2的可變節點Vx，該另一度為2的可變節點Vx用於 閉合所述累加鏈來形成環2102。
圖22例示了對圖21中的擴展後的基本編碼結構A2100的Z-8的提升。
使用圖形符號來區分奇數副本和偶數副本。在該圖中，僅僅使用0和-l的 移位。未示出度為3的節點的非環邊，並且沒有給出其置換。由於對提升後的度為3的節點的環邊上的置換的選擇，這不表示提升後的編碼結構A。 可變節點、2可以對應於第1到第8圖，其中x是圖的數目，z是提升尺寸。 約束節點Cw可以對應於第1到第8圖，其中x是圖的數目，z是提升尺寸。 圖23例示了在提升尺寸為4和雙倍基本圖時的對圖22中示出的圖的 擴充。注意，所述圖現在可以包含使用度為3的奇數可變節點和度為2的 可變節點中的一半可變節點的提升後的編碼結構A，所述度為2的可變節 點中的一半可變節點用於閉合圖22中的累加環。
奇偶校驗矩陣
上述申請可以在第三代合作夥伴計劃2(3GPP2)無線通信系統中使用。 在共同待決的美國臨時專利申請No. 60/862,730中對此種系統進行了一定 程度的描述，該申請在此引入作為參考，並且形成本申請的一部分。此外， 這些實例的所提出的編碼可以使用提升後的編碼結構A作為編碼基礎。換 言之，在擴充圖中出現的提升後的編碼結構A表示內核的奇偶比特。應該 理解的是，實例中的對所述列或可變節點的重新排序不會顯著地改變所述 實例。類似地，對所述行或約束節點的重新排序不會改變所述實例。類似 地，將常數與列中的所有提升值相加，不會顯著地改變所述實例。
圖24是例示用於使用低密度奇偶校驗(LDPC)碼來對數據進行編碼的 編碼器2400的方框圖。所述編碼器能夠利用二分圖來表示編碼後的數據。 編碼器2400可以包括與通信接口 2704耦合的處理電路(例如，處理器、處 理模塊等)2402和用於存儲編碼數據的存儲器設備2406，其中所述通信接口 2604能夠接收和發送數據。所述處理電路2402可以與控制模塊2408耦合， 以向處理電路2402提供一個或多個指令。所述指令可以包括但不限於，訪 問存儲器設備2406的順序和數據流的定時。所述處理電路2402可以執行 實現下述的功能(a)生成多個低度可變節點的累加鏈；以及(b)閉合所述累 加鏈來兩次形成環， 一次使用低度可變節點，而一次使用比所述低度可變 節點高的較高度可變節點，其中所述較高度可變節點包括非環閉合邊。
圖25例示了在用於使用低密度奇偶校驗(LDPC)碼來對數據進行編碼 的編碼器上操作的示例方法。所述編碼器能夠利用二分圖來表示編碼數據。 當編碼器接收到用於編碼的低密度奇偶校驗(LDPC)碼時開始操作示例方法
33(2502)。接著，所述編碼器可以生成低度可變節點的累加鏈(2504)。在一種 配置中，所述多個低度可變節點可以在每邊上具有相同的置換。接著，可 以閉合(2506)所述累加鏈來兩次形成環， 一次使用低度可變節點，而一次使 用比所述低度可變節點高的較高度可變節點，其中所述較高度可變節點包 括非環閉合邊(2508)。
根據另一配置，編碼器中的電路可以用於使用低密度奇偶校驗(LDPC) 碼來對數據進行編碼，所述LDPC碼能夠利用二分圖表示。相同的電路、 不同的電路、或該相同的電路或不同的電路的第二部分可以用於生成累加 鏈，該累加鏈創建多個低度可變節點的環，所述多個低度可變節點在每條 邊上具有相同的置換。另外，相同的電路、不同的電路、或該相同的電路 或不同的電路的第三部分可以用於使用低度可變節點和比所述低度可變節 點高的較高度可變節點來閉合所述環，其中所述較高度可變節點包括非閉 環邊。類似地，所述相同電路、不同電路或第四部分可以用於使用提升圖， 所述提升圖包括所述累加鏈的多個置換後的副本、所述環低度可變節點的 多個置換後的副本和所述較高度可變節點的多個置換後的副本。本領域的 普通技術人員將認識到，通常，在本公開中描述的所述處理的大部分可以 按照類似的方式實現。任何電路或電路部分可以單獨實現或作為集成電路 的一部分與一個或多個處理器組合實現。所述電路中的一個或多個可以在 集成電路、高級RISC機(ARM)處理器、數位訊號處理器(DSP)、通用處理 器等上實現。
總之，本申請可以提供許多優點，包括但不限於，關於基本圖
1、 具有所有度為2的可變節點的累加鏈可以在每條邊上具有相同的置換。
2、 用於閉合所述環的另一度為2的可變節點，度為2的環節點，以及 也用於閉合所述環的度為3的可變節點。所述度為3的可變節點的第三邊 可以是非環邊。
關於提升-
3、 在度為2的環可變節點邊上的置換為n-3 0比特數A與A-lmod 2"， 其中2"是最大提升大小。
4、 在度為3的可變節點的環邊上的置換為n-3 0比特數B與B-l mod2n，其中，在基本圖中，B-l置換與連接到與具有提升值A的度為2的環 可變節點上的邊相同的約束節點的邊相關聯。
5、度為3的可變節點的非環邊上的置換為C。
此外，具體實例可以包括C=0。當所述結構被擴充時，所述擴充後的
圖包含提升後的編碼結構A，並且如果C=0,則它可以包括具有等同性的
提升後的編碼結構A，其中，所述提升後的編碼結構A包括所有累加的度
為2的可變節點，所述度為2的環可變節點中的一半對應於在所述擴充後
的基本圖中出現的度為2的環節點的兩個副本中的一個，而度為3的可變
節點中的一半對應於在所述擴充後的基本圖中出現的度為3的節點的兩個 副本中的一個。
所公開的實施例可以應用於下述技術中的任何一個或組合碼分多址 (CDMA)系統、多載波CDMA(MC-CDMA)、寬帶CDMA(W-CDMA)、高速 下行分組接入(HSPDA)、時分多址(TDMA)系統、頻分多址(FDMA)系統和 正交頻分多址(OFDMA)系統。
這裡所描述的信令傳輸技術可以採用各種手段實現。例如，這些技術 可以採用硬體、軟體或其組合實現。對於硬體實現，用於處理(例如，壓縮 和編碼)信令的處理單元可以在下述部件中實現 一個或多個專用集成電路 (ASIC)、數位訊號處理(DSP)、數位訊號處理設備(DSPD)、可編程邏輯設備 (PLD)、現場可編程門陣列(FPGA)、處理器、控制器、微控制器、微處理器、 被設計來執行這裡所描述的功能的其它電子單元、或其組合。用於解碼和 解壓縮所述信令的處理單元也可以利用一個或多個ASIC、 DSP等實現。
對於軟體實現，信令傳輸技術可以利用執行本文所描述的功能的模塊 (例如，過程，函數等)實現，並且可以存儲在諸如緊湊計算機盤的機器可讀 介質上。軟體代碼可以存儲在存儲器單元中，並且由處理器執行。所述存 儲器單元可以在所述處理器內部或外部實現。
圖8、 16、 24和25中例示的所述組件、步驟和/或功能中的一個或多個 可以被重排和/或合併為單個組件、步驟或功能，或者在若干個組件、步驟 或功能中具體體現。還可以在不背離所述範圍的情況下，添加其它元件、 組件、步驟和/或功能。圖8、 16和域24中例示的裝置、設備和/或組件可 以被配置來執行如上所述的方法、特徵或步驟中的一個或多個。本文所描述的新型算法可以在軟體和/或嵌入式硬體中有效地實現。
本領域的技術人員還將明白的是，結合本文所公開的實施例描述的各 種示例性邏輯塊、模塊、電路和算法步驟可以被實現為電子硬體、計算機 軟體或兩者的組合。為了清楚地例示硬體和軟體的這種互換性，就各種示 例性的組件、塊、模塊、電路和步驟的功能，如上對其進行了一般性的描 述。此種功能是被實現為硬體還是被實現為軟體，取決於具體應用和對整 個系統施加的設計約束。
可以在不背離所述範圍的情況下，在不同的系統中實現本文所述的申 請的各個特徵。例如，可以在計算機、個人數字助理、數字組織器等上執 行本申請的一些實現。
應該理解的是，上述實施例僅僅是實例，而不應被解釋為限制範圍。 實施例的描述意在例示，而不限制權利要求的範圍。而且，本教導可以容 易地應用於其它類型的裝置，並且對於本領域的技術人員而言，許多替換、 修改和變動是顯而易見的。
權利要求
1、一種用於使用低密度奇偶校驗(LDPC)碼來對數據進行編碼的方法，所述LDPC碼能夠採用二分圖表示，所述方法包括生成多個低度可變節點的累加鏈；以及閉合所述累加鏈以兩次形成環，一次使用低度可變節點，一次使用比所述低度可變節點高的較高度可變節點，其中所述較高度可變節點包括非閉環邊。
2、 如權利要求l所述的方法，其中，所述多個低度可變節點在每個邊 上具有相同的置換。
3、 如權利要求l所述的方法，其中， 所述多個低度可變節點包括多個核度為2的可變節點； 所述較高度可變節點包括核度為3的可變節點；並且 所述低度閉環可變節點包括核度為2的閉環可變節點。
4、 如權利要求1所述的方法，還包括使用提升圖，所述提升圖包括所述累加鏈的多個置換副本、所述低度 閉環可變節點的多個置換副本以及所述較高度閉環可變節點的多個置換副 本。
5、 如權利要求4所述的方法，其中，所述低度閉環可變節點的多個置 換副本包括利用n-3 0比特數A與A+C-l mod 2"進行的低度閉環置換，其 中2"是最大提升尺寸，而C也是n-30比特數。
6、 如權利要求5所述的方法，其中，所述較高度閉環可變節點的多個 置換副本的多個置換的非閉環邊包括利用n-3 0比特數B與B+C-l mod 2" 進行的非閉環置換，其中C是n-30比特數，並且在基本圖中，所述B+C-1 置換與連接到與具有利用數A進行的置換的所述低度閉環可變節點上的邊相同的約束節點的邊相關聯。
7、 如權利要求l所述的方法，其中，在所述較高度可變節點的非閉環 邊上的置換為0。
8、 如權利要求6所述的方法，還包括使用循環提升後的低密度奇偶校 驗(LDPC)碼，在所述循環提升後的LDPC碼中，對於一些基本可變節點， 所述提升後的可變節點中的一半為信息節點， 一半為奇偶節點。
9、 如權利要求8所述的方法，其中，所述LDPC碼的基本圖結構包括 具有另一度為2的可變節點的基本編碼結構A，所述另一度為2的可變節 點包括度為2的閉環可變節點，所述度為2的閉環可變節點閉合結構A的 所述累加鏈的所述環。
10、 如權利要求9所述的方法，其中，除所述提升後的度為2的閉環 可變節點之外的所有提升後的節點也都是響應於它們各自的基本節點的奇 偶節點或信息節點。
11、 如權利要求3所述的方法，其中，所述核度為2的閉環可變節點 具有置換X與X+C-l模Z，其中C是n-3 0比特數。
12、 如權利要求ll所述的方法，其中，C是0。
13、 如權利要求1所述的方法，其中，所述較高度可變節點的閉環邊 具有相關聯的提升置換Y與Y+C-l模Z。
14、 如權利要求9所述的方法，其中，附接到具有置換X的所述邊上 的度為2的閉環可變節點的所述約束節點連接到具有置換Y+C-l的所述較 高度可變節點。
15、 如權利要求9所述的方法，其中，當利用因子2對所述基本圖結 構進行擴充，並通過將一個比特從所述提升移入到所述基本圖中來將所述 提升尺寸降低因子2時，所得到的編碼結構是具有等同性或不具有等同性 的提升後的編碼結構A。
16、 如權利要求l所述的方法，其中，使用核度為3的編碼節點的非閉環邊上的非閉環邊置換，其中所述非 閉環邊置換為0;以及對於參與所述環的核度為2的可變節點的邊上的所有其它置換，使用 值0或-1 mod 2"。
17、 一種用於使用低密度奇偶校驗(LDPC)碼來對數據進行編碼的裝置， 所述LDPC碼能夠採用二分圖表示，所述裝置包括存儲器設備，用於存儲編碼後的數據； 控制模塊；在所述存儲器設備和所述控制模塊之間耦合的處理電路，所述處理電 路被配置來生成多個低度可變節點的累加鏈；以及閉合所述累加鏈以兩次形成環， 一次使用低度可變節點， 一次使用 比所述低度可變節點高的較高度可變節點，其中所述較高度可變節點包 括非閉環邊。
18、 如權利要求17所述的裝置，其中，所述多個低度可變節點在每個 邊上具有相同的置換。
19、 如權利要求17所述的裝置，其中， 所述多個低度可變節點包括多個核度為2的可變節點； 所述較高度可變節點包括核度為3的可變節點；並且 所述低度閉環可變節點包括核度為2的閉環可變節點。
20、 如權利要求17所述的裝置，其中，所述處理電路還被配置來使用 提升圖，所述提升圖包括所述累加鏈的多個置換副本、所述低度閉環可變 節點的多個置換副本以及所述較高度閉環可變節點的多個置換副本。
21、 如權利要求20所述的裝置，其中，所述低度閉環可變節點的多個 置換副本包括利用n-3 0比特數A與A+C-l mod 2"進行的低度閉環置換， 其中2"是最大提升尺寸，而C也是n-3 0比特數。
22、 如權利要求21所述的裝置，其中，所述較高度閉環可變節點的多 個置換副本的多個置換的非閉環邊包括利用n-3 0比特數B與B+C-1 mod 2"進行的非閉環置換，其中C是n-3 0比特數，並且在基本圖中，所述B+C-l 置換與連接到與具有利用數A進行的置換的所述低度閉環可變節點上的邊 相同的約束節點的邊相關聯。
23、 如權利要求17所述的裝置，其中，所述處理電路還被配置來使用 循環提升後的低密度奇偶校驗(LDPC)碼，在所述循環提升後的LDPC碼中， 對於一些基本可變節點，所述提升後的可變節點中的一半為信息節點，一 半是奇偶節點。
24、 如權利要求23所述的裝置，其中，所述LDPC碼的基本圖結構包 括具有另一度為2的可變節點的基本編碼結構A，所述另一度為2的可變 節點包括度為2的閉環可變節點，所述度為2的閉環可變節點閉合結構A 的所述累加鏈的所述環。
25、 如權利要求24所述的裝置，其中，除所述提升後的度為2的閉環 可變節點之外的所有提升的節點也都是響應於它們各自的基本節點的奇偶 節點或信息節點。
26、 一種用於使用低密度奇偶校驗(LDPC)碼來對數據進行編碼的裝置， 所述LDPC碼能夠採用二分圖表示，所述裝置包括用於生成多個低度可變節點的累加鏈的模塊；以及 用於閉合所述累加鏈以兩次形成環的模塊， 一次使用低度可變節點，一次使用比所述低度可變節點高的較高度可變節點，其中所述較高度可變節點包括非閉環邊。
27、 如權利要求26所述的裝置，其中，所述多個低度可變節點在每個 邊上具有相同的置換。
28、 如權利要求26所述的裝置，其中， 所述多個低度可變節點包括多個核度為2的可變節點； 所述較高度可變節點包括核度為3的可變節點；並且 所述低度閉環可變節點包括核度為2的閉環可變節點。
29、 如權利要求26所述的裝置，還包括使用提升圖的模塊，所述提升 圖包括所述累加鏈的多個置換副本、所述低度閉環可變節點的多個置換副 本以及所述較高度閉環可變節點的多個置換副本。
30、 如權利要求29所述的裝置，其中，所述低度閉環可變節點的多個 置換副本包括利用n-3 0比特數A與A+C-l mod 2"進行的低度閉環置換， 其中2"是最大提升尺寸，C也是n-3 0比特數。
31、 如權利要求30所述的裝置，其中，所述較高度閉環可變節點的多 個置換副本的多個置換的非閉環邊包括利用n-3 0比特數B與B+C-1 mod 2"進行的非閉環置換，其中C是n-3 0比特數，並且在基本圖中，所述B+C-l 置換與連接到與具有利用數A進行的置換的所述低度閉環可變節點上的邊 相同的約束節點的邊相關聯。
32、 一種具有一個或多個指令的處理器可讀介質，所述一個或多個指 令在編碼器上運行，用於實現使用低密度奇偶校驗(LDPC)碼來對數據進行 編碼，所述LDPC碼能夠採用二分圖表示，當由處理器執行時，所述指令使得所述處理器生成多個低度可變節點的累加鏈；以及閉合所述累加鏈以兩次形成環， 一次使用低度可變節點， 一次使用比 所述低度可變節點高的較高度可變節點，其中所述較高度可變節點包括非閉環邊。
33、 如權利要求32所述的處理器可讀介質，其中，所述多個低度可變 節點在每個邊上具有相同的置換。
34、 如權利要求32所述的處理器可讀介質，其中， 所述多個低度可變節點包括多個核度為2的可變節點； 所述較高度可變節點包括核度為3的可變節點；並且 所述低度閉環可變節點包括核度為2的閉環可變節點。
35、 如權利要求32所述的處理器可讀介質，還具有一個或多個指令， 當由處理器執行時，所述一個或多個指令使得所述處理器使用提升圖，所述提升圖包括所述累加鏈的多個置換副本、所述低度 閉環可變節點的多個置換副本以及所述較高度閉環可變節點的多個置換副 本。
36、 如權利要求35所述的處理器可讀介質，其中，所述低度閉環可變 節點的多個置換副本包括利用n-3 0比特數A與A+C-l mod 2"進行的低度 閉環置換，其中2"是最大提升尺寸，C也是n-3 0比特數。
37、 如權利要求36所述的處理器可讀介質，其中，所述較高度閉環可 變節點的多個置換副本的多個置換的非閉環邊包括利用n-3 0比特數B與 B+C-l mod 2"進行的非閉環置換，其中C是n-3 0比特數，並且在基本圖 中，所述B+C-1置換與連接到與具有利用數A迸行的置換的所述低度閉環 可變節點上的邊相同的約束節點的邊相關聯。
38、 一種處理器，包括處理電路，其被配置來執行功能以實現生成多個低度可變節點的累加鏈；閉合所述累加鏈以兩次形成環， 一次使用低度可變節點， 一次使用 比所述低度可變節點高的較高度可變節點，其中所述較高度可變節點包 括非閉環邊。
39、 如權利要求38所述的處理器，其中，所述多個低度可變節點在每 個邊上具有相同的置換。
40、 如權利要求38所述的處理器，其中， 所述多個低度可變節點包括多個核度為2的可變節點； 所述較高度可變節點包括核度為3的可變節點；並且 所述低度閉環可變節點包括核度為2的閉環可變節點。
41、 如權利要求38所述的處理器，其中，所述處理器還被配置來使用 提升圖，所述提升圖包括所述累加鏈的多個置換副本、所述低度閉環可變 節點的多個置換副本以及所述較高度閉環可變節點的多個置換副本。
全文摘要
提供了一種新型的裝置和方法，用於使用能夠採用二分圖表示的低密度奇偶校驗(LDPC)碼來對數據進行編碼。為了對所述數據進行編碼，可以生成多個低度可變節點的累加鏈。所述累加鏈隨後可以被閉合來兩次形成環，一次使用低度可變節點，一次使用比該低度可變節點更高的較高度可變節點，其中該較高度可變節點包括非閉環邊。在一個實施例中，所述多個低度可變節點可以在每個邊上具有相同的置換，其中置換被使用來將小尺寸的基本圖提升為LDPC碼的圖。
文檔編號H03M13/11GK101632230SQ200880007735
公開日2010年1月20日 申請日期2008年3月10日 優先權日2007年3月9日
發明者A·漢德卡爾, N·布尚, T·理查森 申請人:高通股份有限公司