轉換用於低密度奇偶校驗編碼的奇偶校驗矩陣的方法
2023-06-01 04:48:31 3
專利名稱：轉換用於低密度奇偶校驗編碼的奇偶校驗矩陣的方法
技術領域：
本發明涉及一種創建用於糾錯的奇偶信息的方法，更具體地講，涉及一種轉換用於低密度奇偶校驗編碼的奇偶校驗矩陣的方法。
背景技術：
低密度奇偶校驗(LDPC)編碼方法已經被廣泛用於創建用於糾錯的信息。LDPC編碼方法用於通過使用僅包含0和1的低密度奇偶校驗矩陣H來獲得奇偶信息，其中，1的數量遠小於0的數量。如果奇偶校驗矩陣H的每一行和每一列包含相同數量的1，那麼LDPC碼是規則的，否則就是不規則的。包括在奇偶校驗矩陣H的每一行和每一列中的1的數量分別稱為「行秩(rowdegree)」和「列秩(column degree)」。
通過使用LDPC編碼方法來創建奇偶信息的方法通常基於下面的方程來被實現方程1HX＝0，其中，H是m×n奇偶校驗矩陣；X是包括m個消息數據和p個奇偶數據的碼字；並且m+p＝n(其中，m、n、和p是整數)。
在D.J.Mackay，「Good Error-correction Codes Based on Very SparseMatrices，」IEEE Trans.on Information Theory，Vol.45，No.2，pp.399-431中公開了LDPC編碼的基本概念。根據該公開，可以通過利用使用高斯消去法的矩陣處理求解上面的方程1，來創建奇偶信息。但是，這樣的矩陣處理需要大量的計算。
最近，引入了一種求解上面的方程1的更方便的方法。根據該方法，奇偶校驗矩陣H被轉換為重新排列的奇偶校驗矩陣H′，其包括特定類型的子塊，稱為下三角矩陣。轉換的奇偶校驗矩陣H′用於以順序的方式創建奇偶信息。在T.Richardson，R.Urbanke，「Efficient Encoding of Low Density Parity CheckCodes，」IEEE Trans.on Information Theory，Vol.47，No.2，pp.638-656，2001中公開了該方法。
現在將參照圖1和圖2A到圖2F來描述轉換奇偶校驗矩陣H的傳統方法。
圖1是示出將奇偶校驗矩陣H轉換為重新排列的奇偶校驗矩陣H′的傳統方法的流程圖，圖2A到圖2F示出了從圖1中顯示的每個操作中得出的矩陣。該傳統方法稱為「貪婪算法」。
在操作110中，矩陣H中的所有與第一行連接的列構成矩陣H的最左列。這裡，「與特定行連接的列」是具有該特定行中的1的列，並且可以通過i)交換或ii)移動行或列，來移動連接的列。圖2A顯示了在執行了操作110之後的矩陣，其中，第一行包括4個1。
在操作120中，當前搜索區域被定義為圖2B中的不包括矩陣H中的第一行以及與第一行連接的列的矩陣A1。搜索區域A1用作用於在以下面的方式實現的行搜索或列搜索中確定1的數量的參考區域。
在操作130中，在矩陣A1中發現具有行秩為1的行R1、R2、...Rk。在圖2C中，標號R1、R2、...Rk表示搜索區域A1中的具有一個「1」(即，行秩為1)的行。
在操作140中，由搜索的結果來確定具有秩為1的行是否被發現。如果具有秩為1的行被發現，那麼操作150、160、170和180被執行。
在操作150中，行R1、R2、...Rk以及與行R1、R2、...Rk連接的列C1、C2、...Cm分別通過行移動和列移動被順序地移至矩陣A1的左上側。例如，如果行R1和R2的秩為1，那麼與行R1連接的列C1構成矩陣A1的最左列，並且行R1構成矩陣A1的最上行。然後，與行R2連接的列C2構成矩陣A1中的第二最左列，並且行R2構成矩陣A1中的第二最上行。其結果是，如圖2D所示，在矩陣A1的左上側創建了單元矩陣(unit matrix)I1。
在操作160中，表示當前搜索區域中的第一列的索引的當前索引i以在操作130中發現的行的數量k遞增。例如，在圖2D中，當前索引i為5，行的數量k為2。
在操作170中，如圖2E所示，當前搜索區域被更新為不包括搜索區域A1中的單位矩陣I1的矩陣A2。
在操作180中，確定當前索引i是否大於奇偶校驗矩陣H的列的數量n。如果當前索引i小於列的數量n，那麼再次執行操作130。否則，矩陣轉換過程結束。
如果在操作140中沒有發現秩為1的行，那麼執行操作155、165、175和185。
在操作155中，在矩陣A1中搜索具有最小秩的行Rmin。
在操作165中，與行Rmin連接的列Cmin1、Cmin2、...Cmin1(1是整數)被發現，並且如圖2F所示，並且除了列Cmin1、Cmin2、...Cmin1中的一個之外全部構成矩陣H的最左列。
在操作175中，表示當前搜索區域中的第一列的索引的當前索引i以1-1遞增。例如，在圖2F中，當前索引i為5，列的數量1為3。
在操作185中，如圖2G所示，搜索區域被更新為不包括在操作165中被移動的列的矩陣A2。
在操作195中，確定當前索引i是否大於奇偶校驗矩陣H的列的數量n。如果當前索引i小於列的數量n，那麼再次執行操作130。否則，矩陣轉換過程結束。
圖2H示出了根據傳統方法而生成的轉換的矩陣H′。圖2H中顯示的轉換的矩陣H′包括由在對角線方向上相連的單元矩陣組成的單位矩陣(identitymatrix)。通過使用右上塊D來執行奇偶信息計算，該右上塊D僅被0填充。
作為順序地計算奇偶信息的必要條件，轉換的矩陣H′應該包含具有對角線1的子矩陣，並且該子矩陣應該是下三角矩陣。圖2H中的轉換的矩陣H′滿足該條件。
計算矩陣H中的奇偶信息的負荷隨著子矩陣I的大小增加而減少。換句話說，根據該傳統方法，隨著子矩陣的大小增加，創建奇偶信息的計算負荷減少。
但是，由於圖2H中的子矩陣I必須是單位矩陣，所以子矩陣I的大小只能夠被增加到有限的程度。換句話說，根據傳統技術，由於用於順序奇偶計算的子矩陣是單位矩陣，所以子矩陣I的大小只能夠被增加到有限的量。矩陣I的大小越有限，使用奇偶校驗矩陣H來解碼的計算量越增加。但是，期望轉換的矩陣H′的子矩陣I是下三角矩陣而不是單位矩陣，從而子矩陣I的大小大於圖2H中所示的子矩陣I的大小。
發明內容
本發明提供一種通過不以單位矩陣的形式構建子矩陣來生成具有增加了大小的下三角子矩陣的轉換的矩陣的方法。
根據本發明的一方面，提供了一種轉換用於低密度奇偶校驗編碼的奇偶校驗矩陣的方法，其包括移動該奇偶校驗矩陣的行和列，從而該奇偶校驗矩陣包括下三角子矩陣。
在本發明的一方面中，該方法包括將與奇偶校驗矩陣中的第一行連接的列移至奇偶校驗矩陣的左側；將包括與第一行連接的列和不包括第一行的子矩陣定義為當前搜索區域，並且將當前搜索區域右側的子矩陣定義為當前補充搜索區域；選擇在其中包括在當前搜索區域中的1的數量等於(行秩-1)的行；和如果行被選擇，那麼通過選擇的行之一和與選擇的行之一連接的列的行移動和/或列移動，將位於選擇的行之一和與選擇的行之一連接的列的交叉點的元素移至當前補充搜索區域的左上角。
在本發明的一方面中，移動元素的步驟包括通過列移動使與選擇的行之一連接的列構成當前補充搜索區域的最左列，並且通過行移動使選擇的行之一構成補充搜索區域中的最上行。
在本發明的一方面中，該方法包括如果沒有行被選擇，那麼將當前補充搜索區域的至少一列移至奇偶校驗矩陣的左側；和更新當前搜索區域以包括已經被移至奇偶校驗矩陣的左側的列，並且通過將位於更新的當前搜索區域的右側的區域定義為當前補充搜索區域來更新當前補充搜索區域。
在本發明的一方面中，移動當前補充搜索區域的至少一列的步驟包括在包括在當前搜索區域中的行中選擇在當前補充搜索區域中包含最小數量的1的條件行；和使與選擇的條件行連接的列之一構成奇偶校驗矩陣的最左列。
根據本發明的另一方面，提供了一種通過在低密度奇偶校驗編碼中使用奇偶校驗矩陣來創建奇偶信息的方法，其中，奇偶校驗矩陣包括子塊，其對角線的元素被「1」填充，相對於對角線的上塊被「0」填充，並且相對於對角線的下塊包含「0」或「1」，並且其中，通過奇偶校驗矩陣的行移動和/或列移動來生成該子塊。
本發明的另外方面和/或優點將在下面的描述中部分地闡明，並且從描述中部分是清楚的，或者通過本發明的實施可以被理解。
通過結合附圖，從實施例的下面描述中，本發明這些和/或其他方面及優點將會變得清楚，並且更易於理解，其中圖1是示出將奇偶校驗矩陣轉換為重新排列的奇偶校驗矩陣的傳統方法的流程圖；圖2A到圖2H示出了從圖1中顯示的操作中得出的矩陣；圖3是示出根據本發明實施例的生成轉換的矩陣的方法的流程圖；圖4A到圖4I示出了從圖3中顯示的操作中得出的矩陣；和圖5A和圖5B分別示出了根據傳統技術和根據本發明實施例的奇偶校驗矩陣的結構。
具體實施例方式
現在將詳細描述本發明的實施例，其示例在附圖中示出，其中，相同的標號始終表示同一部件。下面通過參照附圖來描述這些實施例以解釋本發明。
圖3是根據本發明實施例的創建轉換的矩陣的方法的流程圖，圖4A到圖4I示出了從圖3中顯示的操作中得出的矩陣。現在將參照圖4A到圖4I來描述圖3中所示的方法。
在操作310中，所有與奇偶校驗矩陣H的第一行連接的列構成奇偶校驗矩陣H的最左列。這裡，「與特定行連接的列」是具有該特定行中的1的列，並且可以通過i)交換或ii)移動行或列，來移動連接的列。
例如，如果列C2、C4、C7、和C15與第一行連接，那麼基於當它們被檢測到時將它們移至矩陣H的最左側，然後剩餘的列被移至右側。列C2、C4、C7、和C15的順序不重要。圖4A中的第一子矩陣SB1由操作310的結果而包含1。因為所有包含1的列必須構成矩陣H的最左列，所以第二子矩陣SB2隻包含0。
在操作320中，矩陣H中的在第一子矩陣SB1下面的子矩陣A1被定義為當前搜索區域A1。搜索區域用作在行或列搜索中計算行或列的秩的基礎。另外，矩陣H中的在當前搜索區域A1右側的區域被定義為當前補充搜索區域A1′。在圖4B中，當前搜索區域子矩陣A1被顯示為被斜線填充的塊，並且當前補充搜索區域A1′是在當前搜索區域子矩陣A1右側的矩陣。
在操作330中，在子矩陣A1中具有等於(行秩-1)個1的行R1、R2、...Rk在子矩陣A1中形成。例如，在圖4C中，由於行R1的行秩為3，並且在子矩陣A1中包含兩個1，所以行R1滿足以上條件。另外，由於行R2的行秩為4，並且在子矩陣A1中包含三個1，所以行R2也滿足以上條件。
在操作340中，如果由操作330的結果發現至少一個滿足以上條件的行，那麼執行操作350、360、370、和380。
在操作350中，通過執行行移動和列移動將行R1移至補充矩陣A1′的左上側。
首先，與行R1連接的列C1構成當前補充搜索區域A1′的最左列(即，矩陣H中的第五列)。最初在列C1左側的列被順序地右移。
然後，行R1構成當前補充搜索區域A1′的最上行。最初在行R1上面的行被順序地下移。
圖4D顯示了從操作350得出的矩陣。
在操作360中，表示當前搜索區域A1中的第一行的索引的當前索引j以1遞增。
在操作370中，當前搜索區域A1和當前補充搜索區域A1′被更新。換句話說，通過將由操作350的結果而移動的行排除並將由操作350的結果而移動的列包括，來將當前搜索區域A1更新為第二當前搜索區域A2。在圖4E中，被斜線填充的區域是第二當前搜索區域A2，並且位於第二當前搜索區域A2右側的區域是第二補充搜索區域A2′。
在操作380中，確定當前索引j是否大於奇偶校驗矩陣H的列的數量n。如果當前索引j大於列的數量n，那麼矩陣轉換過程結束。否則，再次執行操作330。
在操作340中，如果不存在第二當前搜索區域A2中的1在其中的數量等於(行秩-1)的行，那麼執行操作355、365、375、385和395。如果由操作330的結果沒有發現第二當前搜索區域A2中的1在其中的數量等於(行秩-1)的行，那麼操作355到395通過列移動來產生這樣的行。
在操作355中，通過搜索第二當前搜索區域A2中的行來尋找在第二補充搜索區域A2′中包含最小數量的1的條件行(conditional row)，例如，Rmax1、Rmax2、...Rmax1。這裡，1是條件行的數量。
在圖4F中，行Ra對應與在第二補充搜索區域A2′中包含最小數量的1的行。
在操作365中，與在操作355中被搜索到的條件行連接的條件列(conditional column)Cmax1、Cmax2、...Cmaxm中的一個被移動以作為奇偶校驗矩陣H的最左列。圖4G示出了條件列Cmax如何構成矩陣H中的最左列，圖4H示出了在移動了條件列Cmax之後的奇偶校驗矩陣H。
在操作375中，表示第二當前搜索區域A2中的第一行的索引的當前索引j以1遞增。
在操作385中，第二當前搜索區域A2和第二補充搜索區域A2′被更新。換句話說，通過將條件列Cmax加到第二當前搜索區域A2來形成第三當前搜索區域A3，並且位於第三當前搜索區域A3右側的第三補充搜索區域A3′被設置為第三當前補充搜索區域。圖4I示出了形成第三當前搜索區域A3和第三補充搜索區域A3′之後的奇偶校驗矩陣H。
在操作395中，確定當前索引j是否大於奇偶校驗矩陣H中的列的數量n。如果當前索引j大於列的數量n，那麼矩陣轉換過程結束。否則，再次執行操作330。
如果由操作330的結果沒有發現第二當前搜索區域A2中的1在其中的數量等於(行秩-1)的行，那麼操作355、365、375、385和395通過列移動來產生這樣的行。這是因為，由於包含具有最小秩的行中的1的列構成奇偶校驗矩陣H的最左列，所以包括在當前搜索區域中的1的數量增加。當前搜索區域中的1的數量的增加促進了搜索區域中的1在其中的數量等於(行秩-1)的行的產生。
在圖3中所描述的方法中，在操作340到380中，通過搜索區域中的1在其中的數量等於(行秩-1)的行和與該行連接的列的行移動和列移動來產生下三角矩陣。如果這樣的行不存在，那麼操作355、365、375、385和395被執行以促進產生如上所述的這樣的行。
圖5A和圖5B分別示出了根據傳統技術和根據本發明實施例的奇偶校驗矩陣的結構。
作為方便地求解方程1以創建奇偶信息的必要條件，轉換的奇偶校驗矩陣應該包括下三角矩陣形式的子矩陣，其中，i)對角線只被1填充，並且ii)對角線的上子塊只被0填充。
參照圖5A，根據傳統技術生成的奇偶校驗矩陣Ha包括滿足上面的條件i)和ii)的子矩陣SBa。具體地講，根據傳統技術，該子矩陣的下子矩陣Da_down和上子矩陣Da_up只包含0。
參照圖5B，根據本發明實施例生成的奇偶校驗矩陣Hb包括與子矩陣SBa類似的滿足上面的條件i)和ii)的子矩陣SBb。但是，與傳統技術不同，下子矩陣Db_down可以包含0和1。
由行移動和列移動的結果，奇偶校驗矩陣被分別轉換為根據傳統技術和根據本發明實施例的圖5A和圖5B所示的矩陣。因此，當採用同一奇偶校驗矩陣開始時，根據本發明實施例生成的子矩陣SBb可以大於根據傳統技術生成的子矩陣SBa。這是因為子矩陣SBa應該是單位矩陣，而子矩陣SBb應該僅是下三角矩陣。
由於求解方程1的計算負荷隨著子矩陣SBa或SBb的大小增加而減少，所以當使用根據本發明實施例的用於生成轉換的奇偶校驗矩陣的方法時，可以減少求解上述方程1的計算負荷。轉換的奇偶校驗矩陣可用在通信系統中或用在任何數據記錄和/或再現裝置中，以能夠使用該轉換的奇偶校驗矩陣來執行對數據的糾錯。
本發明也可以被實施為能夠由計算機執行的計算機可讀記錄介質上的計算機可讀代碼。計算機可讀記錄介質是能夠存儲其後能夠由計算機系統讀出的數據的任何數據存儲裝置。計算機可讀記錄介質的例子包括只讀存儲器(ROM)、隨機存取存儲器(RAM)、CD-ROM、磁帶、軟盤、光學數據存儲裝置、和載波(如通過網際網路的數據傳輸)。計算機可讀記錄介質也可以分布在連接計算機的網絡上，從而計算機可讀代碼以分布式方式被存儲和執行。(另外，本發明所屬領域的程式設計師能夠容易地理解用於實現本發明的功能程序、代碼、和代碼段。)根據本發明的一方面，可以基於與傳統技術不同的方法通過移動行和列，來生成能夠減少創建奇偶信息的計算負荷的奇偶校驗矩陣。
雖然本發明是參照其實施例來被具體顯示和描述的，但是本領域的技術人員應該理解，在不脫離由所附權利要求及其等同物限定的本發明的精神和範圍的情況下，可以對其進行形式和細節的各種修改。示例性的實施例應被理解為只是描述的意義，而不是為了限制的目的。因此，本發明的範圍不是由本發明的具體描述所限定，而是由所附權利要求及其等同物所限定，並且在該範圍內的所有差別應被理解為包括在本發明內。
權利要求
1.一種轉換用於低密度奇偶校驗編碼的奇偶校驗矩陣的方法，其包括移動該奇偶校驗矩陣的行和列，從而對角線的元素被「1」填充，相對於對角線的上塊的元素被「0」填充，並且相對於對角線的下塊是元素包含至少一個「1」。
2.根據權利要求1所述的方法，其中，移動行和列的步驟包括將與奇偶校驗矩陣中的第一行連接的列移至奇偶校驗矩陣的左側；將包括與第一行連接的列和不包括第一行的子矩陣定義為當前搜索區域，並且將當前搜索區域右側的子矩陣定義為當前補充搜索區域；選擇在其中包括在當前搜索區域中的1的數量等於(行秩-1)的行；和如果行被選擇，那麼通過選擇的行之一和與選擇的行之一連接的列的行移動和/或列移動，將位於選擇的行之一和與選擇的行之一連接的列的交叉點的元素移至當前補充搜索區域的左上角。
3.根據權利要求2所述的方法，其中，移動元素的步驟包括通過列移動使與選擇的行之一連接的列構成當前補充搜索區域的最左列，並且通過行移動使選擇的行之一構成補充搜索區域中的最上行。
4.根據權利要求2所述的方法，其中，移動元素的步驟包括使與選擇的行之一連接的第一列構成當前補充搜索區域的最左列；和使選擇的行之一構成補充搜索區域中的最上行。
5.根據權利要求2所述的方法，還包括更新當前搜索區域以包括在移動元素期間被移動列並且不包括選擇的行之一，並且將當前補充搜索區域更新為位於更新的當前搜索區域右側的子矩陣。
6.根據權利要求5所述的方法，還包括通過更新當前搜索區域和當前補充搜索區域來反覆地執行行的選擇；和反覆地更新當前搜索區域直到達到奇偶校驗矩陣的最後一行。
7.根據權利要求2所述的方法，還包括如果沒有行被選擇，那麼將當前補充搜索區域的至少一列移至奇偶校驗矩陣的左側；和更新當前搜索區域以包括被移至奇偶校驗矩陣的左側的至少一列，並且通過將位於更新的當前搜索區域的右側的區域定義為當前補充搜索區域來更新當前補充搜索區域。
8.根據權利要求7所述的方法，其中，移動當前補充搜索區域的至少一列的步驟包括在包括在當前搜索區域中的行中選擇在當前補充搜索區域中包含最小數量的1的條件行；和使當前補充搜索區域的與選擇的條件行連接的列之一構成奇偶校驗矩陣的最左列。
9.根據權利要求7所述的方法，還包括通過更新當前搜索區域和當前補充搜索區域來反覆地執行行的選擇；和反覆地更新當前搜索區域直到達到奇偶校驗矩陣的最後一行。
10.一種創建在數據的糾錯中被使用的奇偶信息的方法，包括在低密度奇偶校驗編碼中使用奇偶校驗矩陣，其中，奇偶校驗矩陣包括子塊，其對角線的元素被「1」填充，相對於對角線的上塊被「0」填充，並且相對於對角線的下塊包含至少一個「1」；和通過奇偶校驗矩陣的行移動和/或列移動來生成該子塊。
11.根據權利要求10所述的方法，其中，通過行移動和/或列移動來生成該子塊的步驟包括將與奇偶校驗矩陣中的第一行連接的列移至奇偶校驗矩陣的左側；將包括與第一行連接的列和不包括第一行的子矩陣定義為當前搜索區域，並且將當前搜索區域右側的子矩陣定義為當前補充搜索區域；選擇在其中包括在當前搜索區域中的1的數量等於(行秩-1)的行；和如果行被選擇，那麼通過選擇的行之一和與選擇的行之一連接的列的行移動和/或列移動，將位於選擇的行之一和與選擇的行之一連接的列的交叉點的元素移至當前補充搜索區域的左上角。
12.根據權利要求11所述的方法，還包括如果沒有行被選擇，那麼將當前補充搜索區域的至少一列移至奇偶校驗矩陣的左側；和更新當前搜索區域以包括被移至奇偶校驗矩陣的左側的至少一列，並且通過將位於更新的當前搜索區域的右側的區域定義為當前補充搜索區域來更新當前補充搜索區域。
13.一種存儲用於實現根據權利要求2所述的方法的程序的計算機可讀記錄介質。
14.一種產生與記錄和/或再現系統一起使用的轉換的奇偶校驗矩陣H以根據低密度奇偶校驗編碼方法將數據進行編碼來執行糾錯的方法，該方法包括識別與奇偶校驗矩陣的第一行連接的列；移動連接的列以構成奇偶校驗矩陣的最左列；在連接的列中將第一搜索區域設置為奇偶校驗矩陣的剩餘的行；在非連接的列中將第二搜索區域設置為奇偶校驗矩陣的剩餘的行；從剩餘的行中識別秩行，該秩行在第一搜索區域中包括1的數量比該秩行的行秩小1；在第二搜索區域中移動與識別的秩行連接的秩列以構成第二搜索區域的最左列，並且移動識別的秩行以構成第一和第二搜索區域的最上行；當沒有識別出秩行時，從剩餘的行中識別在第二搜索區域中包含最小數量的1的條件行；和在第二搜索區域中移動與條件行連接的最大條件列以構成奇偶校驗矩陣的最左列。
15.根據權利要求14所述的方法，還包括在連接的列和秩列或最大條件列中將第一搜索區域更新為第一行或秩行下面的剩餘的行；在非連接的列中將第二搜索區域更新為第一行或秩行下面的剩餘的行，其中，該方法被執行直到達到奇偶校驗矩陣的最後一行。
16.根據權利要求15所述的方法，其中，記錄和/或再現系統使用具有值1的奇偶校驗矩陣對角線元素，並且在達到最後一行以執行糾錯之後，相對於對角線元素的奇偶校驗矩陣的下塊的至少一個元素具有值1。
全文摘要
一種轉換用於低密度奇偶校驗編碼的奇偶校驗矩陣的方法，其包括移動該奇偶校驗矩陣的行和列，從而該奇偶校驗矩陣包括下三角子矩陣。可以通過使用包括下三角子矩陣的轉換的奇偶校驗矩陣，來降低創建奇偶信息的計算負荷。
文檔編號G06F11/10GK1691521SQ20051006465
公開日2005年11月2日 申請日期2005年4月19日 優先權日2004年4月19日
發明者金炫廷, 金其鉉, 李胤雨 申請人:三星電子株式會社