TWI854675B

TWI854675B - 重排ｌｄｐｃ碼而改善ｌｄｐｃ重組解碼器並行的方法

Info

Publication number: TWI854675B
Application number: TW112120129A
Authority: TW
Inventors: 魏大鈞; 曾戈忠
Original assignee: 睿寬智能科技有限公司
Priority date: 2023-05-30
Filing date: 2023-05-30
Publication date: 2024-09-01
Also published as: TW202448130A

Abstract

LDPC重組解碼器(LDPC shuffle decoder)有兩個核心及兩個記憶體，依序處理一個LDPC矩陣的所有欄位。處理每一欄位時，把它的非零元素的讀(reading)與寫(writing)均分給兩個記憶體。依此分派方式，LDPC重組解碼器可在最少的循環完成此LDPC矩陣的讀及寫。

Description

重排LDPC碼而改善LDPC重組解碼器並行的方法

本發明關於對LDPC重組解碼器，尤其關於重排LDPC碼而改善LDPC重組解碼器並行的方法。

在LDPC重組解碼(LDPC shuffle decoding)中，解碼器以欄位為單位處理上述矩陣。

有鑑於上述習知技藝之問題，本發明之目的是提供一種重排LDPC碼欄位而縮短LDPC重組解碼器延遲的方法。

為達成上述目的，上述方法包括：為上述LDPC重組解碼器提供兩個記憶體，平均分配上述LDPC碼的矩陣的非零元素給上述兩個記憶體，依上述分配方式，從上述兩個記憶體讀上述非零元素，並寫上述非零元素到上述兩個記憶體，更新分配方式，判斷是否達最大遞迴數。若未達最大遞迴數，則回上述平均分配上述非零元素給上述兩個記憶體的步驟。若達最大遞迴數，則判斷分配是否成功。若分配成功，則產生排程檔案，否則結束。

S20:分配的第一階段

S21:累計某欄位中分別從兩個記憶體來的非零元素數量

S23:暫存當今整體分配狀態當最佳分配狀態

S25:從兩個記憶體讀取的數量平衡？

S27:回溯次數達上限？

S29:執行回溯

S31:回復先前暫存之最佳狀況

S33:依平衡寫入條件隨機分配給記憶體

S35:已達矩陣的最後欄位？

S37:處理開頭欄位中未確認的記憶體讀取資訊

S39:每一欄位的讀取數量皆平衡或已達最大遞迴數？

S40:分配的第二階段

S41:依記憶體分配方式，從對應的記憶體依序讀取非零元素

S43:讀完此欄位所有的非零元素？

S45:目的記憶體滿？

S47:依記憶體分配方式，把一個非零元素寫入對應的記憶體

S49:寫完此欄位的非零元素？

S51:達最後欄位？

S53:執行環繞

S55:在此次環繞時有覆蓋發生？

S57:達最大環繞次數？

S59:記錄失敗一次

S60:更新最佳結果

S70:判斷是否達最大遞迴數

S80:判斷分配是否成功

S90:產生重組解碼器的指令檔案

〔圖1〕現一個LDPC碼；

〔圖2〕呈現一個典型的LDPC並行解碼器；

〔圖3〕是本發明的重排LDPC碼而改善LDPC重組解碼器並行的方法的流程圖；

〔圖4〕是圖3所示之重排LDPC碼而改善LDPC重組解碼器並行的方法的一道子程序的流程圖；

〔圖5〕呈現一個被簡化的LDPC碼與其平衡讀寫之分配；

〔圖6〕呈現另一個LDPC碼的一種失衡分配方式；

〔圖7〕呈現圖6之LDPC碼回溯後的一種平衡分配；

〔圖8〕呈現圖6之LDPC碼回溯後的另一種失衡分配；

〔圖9〕呈現圖6之LDPC碼可能產生的巢狀回溯分配；

〔圖10〕是圖3所示之重排LDPC碼而改善LDPC重組解碼器並行的方法的另一道子程序的流程圖；

〔圖11〕呈現以一種記憶體的容量處理一個LDPC碼；

〔圖12〕呈現處理圖11所示的LDPC碼的第一次環繞；

〔圖13〕呈現處理圖11所示的LDPC碼的第二次環繞；及

〔圖14〕呈現以另一種記憶體容量處理圖11的LDPC碼的第一次環繞。

以下參考相關圖式進一步說明本發明的較佳實施例。為便於理解本發明，以下用相同符號標示相同元件。

參考圖1，LDPC(low-density parity check)碼以矩陣的形式存在。此矩陣有M列(row)*N欄位(column)的元素，每一個元素是一個較小的循環矩陣(circulant)。若循環矩陣僅包括數值0，則此元素是「零元素」(圖中，用X表示)。若循環矩陣包含數值1，則此元素是「非零元素」(圖中，用數字表示循環位移值)。實務上，運算LDPC碼時僅須用非零元素。受限於解碼器硬體限制，LDPC重組解碼以「欄」為單位向後進行運算。

參考圖2，為增加LDPC解碼效率，可拓展LDPC解碼器，此時解碼器擁有兩個記憶體(A及B)及兩個核心(1及2)。核心1及2都是處理器。理想上，核心1從記憶體A(或B)讀資料時，核心2從記憶體B(或A)讀資料。接著，LDPC解碼器處理這些資料。然後，核心1把被處理的資料寫回記憶體A(或B)時，核心2把被處理的資料寫回記憶體B(或A)。核心1及核心2同時運作被稱為「並行」(parallelization)。然而，同一列之相異欄位的非零元素有相依性(dependency)，就是處理每一個非零元素時所需的資料皆是讀取同列先前欄位所載內容(因記憶體位置須相同)。此外，LDPC矩陣中非零元素的分布是稀疏且不規則，因此運算每一欄時，兩個核心可能須同時讀(或寫)單一記憶體A(或B)。此時，只有一個核心工作，須閒置另一核心，導致整體系統延宕。

圖3呈現本發明的較佳實施例的重排LDPC碼而改善LDPC重組解碼器的方法。本發明的方法重排上述LDPC碼而改善上述LDPC重組解碼器並行。換言之，本發明的方法避免一個核心(1或2)運作時，另一個核心(2或1)閒置。具體而言，本發明的方法把每一欄位的非零元素的資料讀取與寫入排序(sort)或分配，致平行且平衡處理這些非零元素而最佳化上述LDPC重組解碼器的效能。

在步驟S20，進行分配的第一階段。檢視整個矩陣，標示且安排每一欄位的一些非零元素到記憶體A，標示且安排每一欄位的另一些非零元素到記憶體B，並確保兩個記憶體有最適當的平衡狀態。重複此步驟，兩個記憶體平衡或達最大遞迴數(兩個記憶體失衡)時才停。

在步驟S40，進行分配的第二階段。用此舉發現記憶體A或B是否因上述分配而導致記憶體溢出(overflow)的錯誤，並傳遞錯誤標記到步驟S60。

在步驟S60，依限制及硬體要求，更新最佳結果。只留一個結果當最後結果。為此，把本次遞迴的結果與先前貯存的結果相比。若把本次遞迴的結果優於先前貯存的結果，則用本次遞迴的結果取代先前貯存的結果，否則留先前貯存的結果。

在步驟S70，判斷是否達最大遞迴數。若是，則到步驟S80，否則回步驟S20。因此，重複步驟S20、S40及S60，達最大遞迴數才停。

在步驟S80，判斷分配是否成功。若是，則到步驟S90，否則結束。

在步驟S90，產生重組解碼器的指令檔案當最後輸出資料。此指令檔案被稱為「排程檔案」(scheduling files)。

參考圖4，詳細描述步驟S20。步驟S20的目標是以平衡的方式把非零元素投入記憶體A及記憶體B。步驟S20包括步驟S21、S23、S25、S27、S29、S31、S33、S35、S37、S39。步驟S21、S23、S25、S27、S29及S31屬於讀的階段，步驟S33屬於寫的階段，步驟S35、S37、S39屬於後續處理的階段。

在步驟S21，作為讀取的第一步驟，累計某欄位中分別從記憶體A及B來的非零元素的數量。為此，須檢視前一或數個欄位在同一列的非零元素是寫入記憶體A或記憶體B。應注意，此時矩陣最前面的幾個欄位可能無先前記憶體資訊，故暫不累計此欄位的元素數量，但假定其來自兩個記憶體的數量平衡，使在步驟S25滿足條件並進入步驟S33而繼續寫入記憶體的步驟。這些未確認的讀取記憶體資訊，稍後會在步驟S37被處理。

在步驟S23，若當今欄位是新欄位(表示分配已進行到新欄位)，則暫存當今整體分配狀態當最佳分配狀態，並記錄現今最大欄位序號。此最大欄位序號紀錄可用來判斷現今欄位是否為新欄位，若現今欄位序號大於先前最大欄位序號，則此欄位是新欄位。

在步驟S25，取用步驟S21的結果，判斷分別從兩個記憶體A及B讀取的數量是否平衡。換言之，判斷此欄位之非零元素們從記憶體A讀取的量是否等於從記憶體B讀取的量(若非零元素總數為奇數，則滿足平衡之條件為相差1)。若是，則到步驟S33，否則到步驟S27。

在步驟S27，表示從兩記憶體讀取的數量不平衡，須執行回溯(rolling back)予以修正。首先判斷回溯次數是否達上限。若是，則到步驟S31，否則到步驟S29執行回溯。回溯次數為統計在固定欄位範圍內(未往後執行到任何新欄位的狀況下)執行回溯的次數，即是在此範圍裡，每回溯1次，就把回溯次數加1。同時定義回溯次數上限，以避免在找不到任何平衡的分配狀態時，陷於無限回溯之迴路。此次回溯可能在先前的回溯中，即在執行回溯時，可能觸發另一次的回溯，但只要發生在此固定範圍內，每次回溯都應觸發次數加1。

在步驟S29，實際執行回溯。隨機選一個造成失衡狀況的非零元素，回到同一列中前一個非零元素，並從步驟S21重新開始處理它所在的那一個欄位。重新處理此欄位時，因在步驟S33是依平衡寫入條件隨機分配寫到記憶體A或記憶體B，將有機會把後續欄位(包括上述造成失衡的那一個欄位)的讀取數量重新分配而達到平行狀態。

在步驟S31，若回溯時未發現更佳組合且回溯次數已達上限，則回復先前暫存之最佳狀況(在步驟S23被貯存)。

在步驟S33，依平衡的寫入條件，隨機分配非零元素的資料寫到記憶體A或記憶體B。

在步驟S35，判斷是否已達矩陣的最後欄位。若是，則到步驟S37，否則回步驟S21繼續處理下一欄位。

在步驟S37，處理開頭欄位中未確認的記憶體讀取資訊。參考最後幾個欄位的寫入資訊，得知資料所存放之記憶體，再回到開頭欄位中填入其相對應讀取的記憶體。換言之，視最後幾個欄位視為在最前面幾個欄位以前的先前記憶體資訊。

在步驟S39，判斷是否每一欄位的讀取數量皆平衡(不必判斷寫入，因寫入時依平衡之數量寫入)或已達最大遞迴數。若是，則到步驟S40，否則回步驟S21。

參考圖5，舉例描述如何執行本發明的方法。

在步驟S21，暫不處理欄位1之資料讀取，因不知列2、3、5或6先行資料的寫被分配到記憶體A或記憶體B。在步驟S23，記錄當今狀態，並假設讀取數量平衡而由步驟S25跳至步驟S33。在步驟S33，將非零元素資料依平衡之數量寫入記憶體A與記憶體B。

在步驟S21，暫不處理欄位2之資料讀取，因不知列1、4先行資料的寫被分配到記憶體A或記憶體B。在步驟S23，記錄當今狀態，並假設讀取數量平衡而由步驟S25跳至步驟S33。在步驟S33，將非零元素資料依平衡之數量寫入記憶體A與記憶體B。

在步驟S21，處理欄位3，可知列1的資料須從記憶體A讀取(由欄位2列1寫入)，列2的資料須從記憶體A讀取(由欄位1列2寫入)，列3的資料須從記憶體B讀取(由欄位2列3寫入)，列4的資料須從記憶體B讀取(由欄位2列4寫入)。

在步驟S23，判斷欄位3是新欄位，並因此存當今分配狀態當最佳狀態。

在步驟S25，從步驟S21的結果，判斷兩個記憶體平衡，並因此到步驟S33。

在步驟S33，把非零元素資料依平衡之數量寫入記憶體。此時，分配列1及2的寫到記憶體A，並分配列3及4的寫到記憶體B。

在步驟S35，判斷欄位3非最後欄位，並因此回步驟S21。

在步驟S21，處理欄位4，可知列2的資料須從記憶體A讀取(由欄位3列2寫入)，列4的資料須從記憶體B讀取(由欄位3列4寫入)，列5的資料須從記憶體A讀取(由欄位2列5寫入)，列6的資料須從記憶體B讀取(由欄位1列6寫入)。

在步驟S23，判斷欄位4是新欄位，並因此存當今分配狀態當最佳狀態。

在步驟S33，把非零元素資料依平衡之數量隨機分配寫入記憶體。此時分配列2及5的寫到記憶體A，並分配列4及6的寫到記憶體B。

在步驟S35，判斷欄位4非最後欄位，並因此回步驟S21。

在步驟S21，處理欄位5，可知列2的資料須從記憶體A讀取(由欄位4列2寫入)，列3的資料須從記憶體B讀取(由欄位3列3寫入)，列5的資料須從記憶體A讀取(由欄位4列5寫入)，列6的資料須從記憶體B讀取(由欄位4列6寫入)。

在步驟S23，判斷欄位5是新欄位，並因此存當今分配狀態當最佳狀態。

在步驟S33，把非零元素資料依平衡之數量寫入記憶體。此時，分配列2及3的寫到記憶體A，並分配列5及6的寫到記憶體B。

在步驟S35，判斷欄位5是最後欄位，並因此到步驟S37。

在步驟S37，開始進行後續的環繞分配，由欄位1開始填補缺失的讀取資訊。此時可知列2的資料須從記憶體A讀取(由欄位5列2寫入)，列3的資料須從記憶體A讀取(由欄位5列3寫入)，列5的資料須從記憶體B讀取(由欄位5列5寫入)，列6的資料須從記憶體B讀取(由欄位5列6寫入)。

以此方式繼續填補欄位2缺的讀取資訊。可知列1的資料須從記憶體A讀取(由欄位3列1寫入)，列3的資料須從記憶體A讀取(由欄位1列3寫入)，列4的資料須從記憶體B讀取(由欄位4列4寫入)，列5的資料須從記憶體B讀取(由欄位1列5寫入)。

在步驟S39，判斷所有欄位在讀取數量上皆為平衡(從記憶體A的讀與記憶體B的讀平衡)，並因此結束步驟S20。

參考圖6及圖7，描述回溯1次，從一種失衡的分配狀態變成一種平衡的分配狀態。

在圖6，欄位1到欄位k+2中，每一欄位從兩個記憶體讀取的數量平衡。在欄位k+3讀取資料時，從兩個記憶體讀取的數量失衡，可知列1到列3的讀取是從記憶體A，僅列4的讀取是從記憶體B。

在步驟S21，發現欄位k+3有3個非零元素的讀取是從記憶體A，1個非零元素的讀取是從記憶體B。

在步驟S23，判斷欄位k+3是新欄位，並因此存當今分配狀態當最佳狀態。

在步驟S25，從步驟S21的結果，判斷從兩個記憶體讀取的數量失衡，並因此到步驟S27。

在步驟S27，判斷回溯次數未達上限，並因此到步驟S29。

在步驟S29，隨機選列1(圖7)，回欄位k+2，並回步驟S21。此時，回溯次數須加1。

參考圖7，在步驟S21，發現欄位k+2有2個非零元素的讀取是從記憶體A，2個非零元素的讀取是從記憶體B。

在步驟S23，判斷欄位k+2是舊欄位，並因此不存當今分配狀態當最佳狀態。

在步驟S25，從步驟S21的結果，判斷從兩個記憶體讀取的數量平衡，並因此到步驟S33。

在步驟S33，把非零元素資料依平衡數量且隨機分配的方式寫入記憶體，此時分配列3及5的寫到記憶體A，並分配列1及4的寫到記憶體B。

在步驟S35，判斷欄位k+2非最後欄位，並因此回步驟S21。

在步驟S21，發現欄位k+3有2個非零元素的讀被分配到記憶體A，2個非零元素的讀被分配到記憶體B。

在步驟S23，判斷欄位k+3是舊欄位，並因此不存當今分配狀態當最佳狀態。

在步驟S25，從步驟S21的結果，判斷從兩個記憶體讀取的數量平衡，並因此到步驟S33執行資料寫入步驟。此時，資料讀取已由原本失衡的分配狀態，變成一種平衡的分配狀態。

參考圖6及圖8，描述回溯1次，從一種失衡的分配狀態到另一種失衡分配狀態的可能狀況及後續處置方式。

參考圖6，在步驟S21，發現欄位k+3有3個非零元素的讀取是從記憶體A，1個非零元素的讀取是從記憶體B。

在步驟S23，判斷欄位k+3是新欄位，並存當今分配狀態當最佳狀態。

在步驟S27，判斷回溯次數未達上限，並因此到步驟S29。

在步驟S29，隨機選列3，回欄位k+2，並回步驟S21。此時回溯次數須加1。

參考圖8，在步驟S21，發現欄位k+2有2個非零元素的讀取是從記憶體A，2個非零元素的讀取是從記憶體B。

在步驟S33，將非零元素資料依平衡數量且隨機分配的方式寫入記憶體，分配列1及4的寫到記憶體A，並分配列3及5的寫到記憶體B。

在步驟S35，判斷欄位k+2非最後欄位，並因此回步驟S21。

在步驟S25，從步驟S21的結果，判斷從兩個記憶體讀取的數量依舊失衡，並因此到步驟S27。在此失衡的狀態，須在步驟S27判斷是否達回溯次數上限，並根據結果再執行回溯(回溯次數須加1)或如後述在S31執行回復。

若一直未能使分配狀態從失衡到平衡，則在某次回溯的步驟S27時，判斷回溯次數已達上限，並因此到步驟S31。在步驟S31，因無法找到更佳分配狀態，所以採用先前儲存之最佳分配狀態作為回復(在此狀況中為欄位k+3)。接著進入步驟S33執行資料寫入部分，並在步驟S35判斷是否處理下一欄位或已處理完畢。

參考圖6及圖9，描述回溯1次後，從一種失衡的分配狀態到另一種失衡分配狀態的可能狀況，並須進行第2次且巢狀式(多次涵蓋式)回溯，並敘述相關後續處置。

在步驟S25，從步驟S21的結果，判斷從兩個記憶體讀取的非零元素的數量失衡，並因此到步驟S27。

在步驟S27，判斷回溯次數未達上限，並因此到步驟S29。

在步驟S29，隨機選列2，回欄位k+2，並回步驟S21。此時，回溯次數須加1。

參考圖9，在步驟S21，發現欄位k+1有2個非零元素的讀取是從記憶體A，2個非零元素的讀取是從記憶體B。

在步驟S23，判斷欄位k+1是舊欄位，並因此不存當今分配狀態當最佳狀態。

在步驟S33，把非零元素資料依平衡數量且隨機分配的方式寫入記憶體，分配列3及5的寫到記憶體A，並分配列2及6的寫到記憶體B。

在步驟S35，判斷欄位k+1非最後欄位，並因此回步驟S21。

在步驟S21，發現欄位k+2有3個非零元素的讀取是從記憶體A，1個非零元素的讀取是從記憶體B。

在步驟S25，從步驟S21的結果，判斷從兩個記憶體讀取的數量依舊失衡，並因此到步驟S27。在此失衡的狀態，須在步驟S27判斷是否達回溯次數上限，並根據結果再執行回溯(回溯次數須加1)，或在S31執行回復。若判斷為可執行回溯，因此時仍在先前未完成之回溯中，同時再執行回溯，就是巢狀回溯。可重複執行回溯，直到達回溯次數上限，或成功向後續欄位推進(在步驟S23判斷現今欄位為新欄位)才結束。

分配的第二階段(步驟S40)是在前一階段已完成的記憶體A(或B)分配情況下，進一步安排所對應之記憶體位址，以檢查記憶體的可用性。參考圖10，步驟S40包括步驟S41、S43、S45、S47、S49、S51、S53、S55、S57、S59。步驟S41、S43屬於讀的階段，步驟S45、S47、S49屬於寫的階段，步驟S53、S55、S57則是後續處理環繞(wrap around)的階段。

步驟S41，在某一欄位中，依在步驟S20決定的記憶體分配方式，從對應的記憶體依序讀取一個非零元素的資料，讀取後將此元素資料從記憶體中移除。

在步驟S43，判斷是否讀完此欄位所有的非零元素。若是，則到步驟S45執行安排寫入的步驟，否則回步驟S41繼續讀取。

在步驟S45，先判斷目的記憶體是否為滿。若是，則表示記憶體空間不足以實現此分配方法，立即到步驟S59結束第二階段，否則到步驟S47繼續寫入的步驟。

在步驟S47，依在步驟S20決定的記憶體分配方式，依序把上述欄位中的一個非零元素的資料，寫入對應的記憶體中一個可用的位址(宜從可用的空間隨機選擇位址以增加分配多樣性)。

在步驟S49，判斷是否寫完此欄位的非零元素資料。若是，則到步驟S51，否則回步驟S45繼續寫入。

在步驟S51，判斷是否達最後欄位。若是，則到步驟S53，否則回步驟S41處理下一欄位。

在步驟S53，執行環繞(wrap around)，再處理整個矩陣的記憶體讀取與寫入。若寫入時發生衝突(前次指定的寫入位址已被佔)，則從現今可用的記憶體空間，隨機指定一個位址覆蓋(overwrite)之前的分配。此外，此衝突發生時，註記此次環繞曾發生覆蓋。

在步驟S55，判斷在此次環繞時(步驟S53)是否曾有覆蓋發生。若有，則到步驟S57判斷是否須再環繞，否則表示第二階段完成，分配無誤可直接結束至步驟S60。

在步驟S57，判斷是否達最大環繞次數。若是，則到步驟S59準備結束，否則回步驟S53再執行環繞。

在步驟S59，表示在第二階段發現記憶體空間無法實現此分配方法，記錄S20與S40兩階段分配的失敗一次，到步驟S60執行後續工作。

參考圖11，舉例描述步驟S40的執行。令記憶體A及B都有3個記憶空間。依序處理欄位1、欄位2、欄位3。

處理欄位1時，暫不執行步驟S41及S43，因無任何記憶位址的資訊。

在步驟S45，判斷預期寫入之記憶體未滿，因此到步驟S47，把一個非零元素的資料寫入對應的記憶體中一位址。

重複執行步驟S45、S47及S49，直到把欄位1元素對應資料皆寫入記憶體為止。參考圖11下方結果，列1之資料被寫到記憶體A的位址1，列2之資料被寫到記憶體A的位址2，列3之資料被寫到記憶體B的位址1，列5之資料被寫到記憶體B的位址2。

在步驟S51，判斷欄位1非最後欄位，並回步驟S41。

處理欄位2時，重複執行步驟S41及S43，直到讀完欄位2(列4暫不執行步驟S41及S43，因無任何記憶位址的資訊)。參考圖11下方結果，列1從記憶體A的位址1讀，列3從記憶體B的位址1讀，列5從記憶體B的位址2讀。讀取時還把資料從相對應的記憶體位址移除，此時剩記憶體A的位址2仍有資料。

在步驟S45，判斷預期寫入之記憶體未滿，並因此到步驟S47，把一個非零元素的資料寫入對應的記憶體中一位址。

重複執行步驟S45、S47及S49，直到把欄位2元素對應資料皆寫入記憶體為止。參考圖11下方結果，列1之資料被寫到記憶體A的位址1，列3之資料被寫到記憶體A的位址3(因位址2已有資料)，列4之資料被寫到記憶體B的位址1，列5之資料被寫到記憶體B的位址2。若記憶體A及B都只有2個記憶空間，則在寫列3以前在步驟S45會判斷記憶體A已滿而無法執行寫入，直接步驟S59記錄錯誤與結束排序。

在步驟S51，判斷欄位2非最後欄位，並回步驟S41。

處理欄位3時，重複執行步驟S41及S43，直到讀完欄位2。參考圖11下方結果，列1從記憶體A的位址1讀，列2從記憶體A的位址2讀，列4從記憶體B的位址2讀，列5從記憶體B的位址2讀。讀取時還把資料從相對應的記憶體位址移除，此時剩記憶體A的位址3仍有資料。

重複執行步驟S45、S47及S49，先判斷對應記憶體空間再寫入，直到寫完欄位3資料為止。參考圖11下方結果，列1之資料被寫到記憶體A的位址1，列2之資料被寫到記憶體B的位址1，列4之資料被寫到記憶體A的位址2，列5之資料被寫到記憶體B的位址2。

在步驟S51，判斷欄位3是最後欄位，並因此到步驟S53。

參考圖12，在步驟S53，執行第一次環繞，就是返回開頭重新檢查整個矩陣、填補缺少的資訊、並處理任何覆蓋的情形。

檢驗欄位1的讀取。列1從記憶體A的位址1讀，列2從記憶體B的位址1讀，列3從記憶體A的位址3讀(因圖11中列3最後是寫入記憶體A的位址3)，列5從記憶體B的位址2讀。讀取時還把資料從相對應的記憶體位址移除，此時剩記憶體A的位址2仍有資料。

接著，檢驗欄位1的寫入。列1之資料被寫到記憶體A的位址1，列2之資料發生衝突無法寫到記憶體A的位址2，列3之資料被寫到記憶體B的位址1，列5之資料被寫到記憶體B的位址2。注意，因列2之資料原指定之記憶體A位址2被佔，故寫入位址3。發生覆蓋情形，予以紀錄。

檢驗欄位2的讀取。列1從記憶體A的位址1讀，列3從記憶體B的位址1讀，列4從記憶體A的位址2讀，列5從記憶體B的位址2讀。讀取時還把資料從相對應的記憶體位址移除，此時剩記憶體A的位址3仍有資料。

接著，檢驗欄位2的寫入。列1之資料被寫到記憶體A的位址1，列3之資料被寫到記憶體A的位址2，列4之資料被寫到記憶體B的位址1，列5之資料被寫到記憶體B的位址2。

檢驗欄位3的讀取。列1從記憶體A的位址1讀，列3從記憶體A的位址3讀，列4從記憶體B的位址1讀，列5從記憶體B的位址2讀。讀取時還把資料從相對應的記憶體位址移除，此時剩記憶體A的位址2仍有資料。

接著，檢驗欄位3的寫入。列1之資料被寫到記憶體A的位址1，列2之資料被寫到記憶體B的位址1，列4之資料發生衝突而無法寫到記憶體A的位址2，列5之資料被寫到記憶體B的位址2。注意，列4之資料因原指定之記憶體A位址2被佔，故寫入位址3。發生覆蓋情形，予以紀錄。第1次環繞結束，離開步驟S53。

在步驟S55，由上述紀錄判斷此次環繞有覆蓋發生，並到步驟S57。

在步驟S57，令最大環繞次數為10，當今環繞次數為1，其數目小於10，因此回步驟S53再環繞。

參考圖13，在步驟S53，執行第二次環繞，就是返回開頭重新檢查整個矩陣、填補缺少的資訊、並處理任何覆蓋的情形。

與第一次環繞作法相同，依序檢驗欄位1的讀跟寫，欄位2的讀跟寫，欄位3的讀跟寫。注意，第1欄列2寫資料時，因原指定之記憶體A位址3被佔，故寫入位址2。發生覆蓋情形，予以紀錄。第3欄列4寫入資料時，因原指定之記憶體A位址3被佔，故寫入位址2。發生覆蓋情形，予以紀錄。第2次環繞結束，離開步驟S53。

在步驟S55，由上述紀錄判斷此次環繞依舊有覆蓋發生，並到步驟S57。

在步驟S57，因最大環繞次數為10，當今環繞次數為2，其數目小於10，因此回步驟S53再環繞。

在此例，因執行步驟S53環繞時，第1欄列2之寫入與第3欄列4之寫入，會不斷在記憶體A的位址2與位址3切換，故每次環繞時皆會導致覆蓋情況發生，並經步驟S55到步驟S57判斷環繞次數上限，然後回步驟S53執行下次環繞。最後一次環繞在步驟S57因為達到環繞次數10次的上限，到步驟S59記錄錯誤並結束第二階段排序。

在以上描述，每一個記憶體都有3個記憶空間。在以下描述，每一個記憶體都有4個記憶空間。記憶體的空間愈多，發生覆蓋的可能性愈低，因而更有機會成功找到排序。

參考圖14，舉例描述在圖11排列後，使用4個記憶空間的記憶體(記憶體A及B都各有4個記憶空間)來做環繞，並在環繞時執行檢驗與覆蓋，最後成功完成排序的過程。環繞時，依序處理欄位1、欄位2、欄位3。

接著，檢驗欄位1的寫入。列1之資料被寫到記憶體A的位址1，列2之資料發生衝突無法寫到記憶體A的位址2，列3之資料被寫到記憶體B的位址1，列5之資料被寫到記憶體B的位址2。注意，列2之資料因原指定之記憶體A位址2被佔，故依隨機方式選擇現今可用之空間，此處假設隨機指定結果為使用記憶體A之位址4。由於列2在此發生覆蓋情形，予以紀錄。

檢驗欄位2的讀取。列1從記憶體A的位址1讀，列3從記憶體B的位址1讀，列4從記憶體A的位址2讀，列5從記憶體B的位址2讀。讀取時還把資料從相對應的記憶體位址移除，此時剩記憶體A的位址4仍有資料。

接著，檢驗欄位2的寫入。列1之資料被寫到記憶體A的位址1，列3之資料被寫到記憶體A的位址3，列4之資料被寫到記憶體B的位址1，列5之資料被寫到記憶體B的位址2。

檢驗欄位3的讀取。列1從記憶體A的位址1讀，列3從記憶體A的位址4讀，列4從記憶體B的位址1讀，列5從記憶體B的位址2讀。讀取時還把資料從相對應的記憶體位址移除，此時剩記憶體A的位址3仍有資料。

接著，檢驗列3的寫入。列1之資料被寫到記憶體A的位址1，列2之資料被寫到記憶體B的位址1，列4之資料被寫到記憶體A的位址2，列5之資料被寫到記憶體B的位址2。第1次環繞結束，離開步驟S53。

在步驟S57，假定最大環繞次數為10，當今環繞次數為1，其數目小於10，因此回步驟S53再次環繞。

在步驟S53執行第二次環繞，用第一次環繞結果進行分配檢驗，確認分配方式無變動，因此任何覆蓋紀錄。

在步驟S55判斷無覆蓋，分配成功，並因此離開此第二階段排序。

以上僅為描述本發明的較佳實施方式，非用以限定本發明的範圍。本技術領域內的一般技術人員根據上述實施例所作的均等變化，以及本領域內技術人員熟知的改變，仍在本發明的範圍內。

S20:分配的第一階段

S40:分配的第二階段

S60:更新最佳結果

S70:判斷是否達最大遞迴數

S80:判斷分配是否成功

S90:產生重組解碼器的指令檔案

Claims

一種重排LDPC碼而改善LDPC重組解碼器並行的方法，包括下列步驟：

為上述LDPC重組解碼器提供兩個記憶體；

平均分配上述LDPC碼的矩陣的非零元素給上述兩個記憶體(S20)；

依上述分配方式，寫上述非零元素到上述兩個記憶體(S40)；

更新分配方式(S60)；

判斷是否達最大遞迴數(S70)；

若未達最大遞迴數，則回上述平均分配上述非零元素給上述兩個記憶體的步驟(S20)；

若達最大遞迴數，則判斷分配是否成功(S80)；

若分配成功，則產生排程檔案(S90)；及

若分配失敗，則結束。
如請求項1所述之重排LDPC碼而改善LDPC重組解碼器並行的方法，其中達最大遞迴數，或每一欄位的資料讀取皆已平衡後，還包括以下步驟：

依上述分配方式，在某一欄位中，從對應的記憶體依序讀取一個非零元素，讀取後將此元素從記憶體中移除(S41)；

判斷是否讀完此欄位所有的非零元素資料(S43)；

若未讀完此欄位的非零元素資料，則回上述從對應的記憶體讀某一欄位中一個非零元素資料的步驟(S41)；

若讀完此欄位的所有非零元素資料，則判斷預期寫入記憶體是否滿(S45)；

若任何上述記憶體滿，則記錄分配失敗一次並結束(S59)；

若預期寫入記憶體未滿，則依上述分配方式，依序把上述欄位中的一個非零元素資料，寫入對應的記憶體中一個可用的位址(S47)；

判斷是否寫完此欄位的非零元素資料(S49)；

若未寫完此欄位的所有非零元素資料，則回上述判斷任何上述記憶體是否滿的步驟(S45)；

若寫完此欄位的所有非零元素資料，則判斷是否達最後欄位(S51)；

若未達最後欄位，則回上述從對應的記憶體依序讀某一欄位一個非零元素的步驟(S41)；

若達最後欄位則執行環繞，檢驗整個矩陣是否有位址衝突需重新分配(S53)；

判斷此次環繞時有無覆蓋(S55)；

若此次環繞時無覆蓋，則結束；

若此次環繞時有覆蓋，則判斷環繞次數是否達一個上限(S57)；

若環繞次數未達上述上限，則回上述執行環繞的步驟(S53)；及

若環繞次數達上述上限，則記錄分配失敗一次並結束(S59)。
一種改善LDPC重組解碼器並行的方法，其包括下列步驟：為上述LDPC重組解碼器提供兩個記憶體；計算上述LDPC碼的矩陣的一個欄位中非零元素資料，分別從上述兩個記憶體讀取之數量(S21)；若當今欄位是新欄位，則存當今整體分配狀態當最佳狀態(S23)；判斷此欄位中分屬於上述兩個記憶體的非零元素資料讀取量是否相等(S25)；若分屬於上述兩個記憶體的非零元素資料讀取量不相等，則判斷回溯次數是否達上限(S27)；若回溯次數未達上限，則隨機選一個造成失衡狀況的非零元素，回到同一列中前一個非零元素，並重新處理它所在的那一個欄位(S29)；若回溯次數達上限，則回復先前最佳狀況(S31)；若分屬於上述兩個記憶體的非零元素量相等，則平均且隨機地分配上述非零元素的資料寫入到上述兩個記憶體(S33)；判斷是否達最後欄位(S35)；若未達最後欄位，則回上述計算下個欄位中非零元素資料，分別從上述兩個記憶體讀取之數量(S21)；若達最後欄位，則利用最後幾個欄位的寫入資訊，得知資料所存放之記憶體，再回到開頭欄位中填入其相對應讀取的記憶體，並記錄前面每個欄位中分別從兩個記憶體讀取之數量(S37)；判斷是否達最大遞迴數，或每一欄位的資料讀取皆已平衡(S39)；若未達最大遞迴數，且每一欄位的資料讀取皆未平衡，則回上述計算LDPC碼的矩陣的一個欄位中非零元素資料，分別從兩個記憶體讀取之數量(S21)；及若達最大遞迴數，或每一欄位的資料讀取皆已平衡，則結束。
如請求項3所述之改善LDPC重組解碼器並行的方法，其中達最大遞迴數，或每一欄位的資料讀取皆已平衡後，還包括以下步驟：依上述分配方式，在某一欄位中，從對應的記憶體依序讀取一個非零元素，讀取後將此元素從記憶體中移除(S41)；判斷是否讀完此欄位所有的非零元素資料(S43)；若未讀完此欄位的非零元素資料，則回上述從對應的記憶體讀某一欄位中一個非零元素資料的步驟(S41)；若讀完此欄位的所有非零元素資料，則判斷預期寫入記憶體是否滿(S45)；若任何上述記憶體滿，則記錄分配失敗一次並結束(S59)；若預期寫入記憶體未滿，則依上述分配方式，依序把上述欄位中的一個非零元素資料，寫入對應的記憶體中一個可用的位址(S47)；判斷是否寫完此欄位的非零元素資料(S49)；若未寫完此欄位的所有非零元素資料，則回上述判斷任何上述記憶體是否滿的步驟(S45)；

若寫完此欄位的所有非零元素資料，則判斷是否達最後欄位(S51)；

若未達最後欄位，則回上述從對應的記憶體依序讀某一欄位一個非零元素的步驟(S41)；

若達最後欄位則執行環繞，檢驗整個矩陣是否有位址衝突需重新分配(S53)；

判斷此次環繞時有無覆蓋(S55)；

若此次環繞時無覆蓋，則結束；

若此次環繞時有覆蓋，則判斷環繞次數是否達一個上限(S57)；

若環繞次數未達上述上限，則回上述執行環繞的步驟(S53)；及

若環繞次數達上述上限，則記錄分配失敗一次並結束(S59)。