TWI898775B - Ldpc解碼器及最小值搜尋方法 - Google Patents

Abstract

本發明提出一種LDPC解碼器及最小值搜尋方法。LDPC解碼器包括儲存單元及至少一運算引擎。儲存單元儲存一LDPC矩陣。運算引擎執行LDPC解碼演算法，以根據LDPC矩陣對一碼字估算出一解碼結果。運算引擎包括一最小值搜尋單元，以在LDPC解碼演算法執行到一最小值搜尋演算時，根據複數輸入值輸出一最小值搜尋結果。最小值搜尋單元執行：將此些輸入值轉換為複數獨熱向量；建立複數第一向量，每一第一向量呈現此些獨熱向量中在一獨熱位元索引上的獨熱位元間執行或運算的結果；及對此些第一向量優先解碼出一最小值。

Description

LDPC解碼器及最小值搜尋方法

本發明是有關於通訊解碼技術，特別是指一種LDPC解碼器及最小值搜尋方法。

低密度奇偶校驗（Low-Density Parity-Check，LDPC）編碼用於被動光纖網路（Passive Optical Network，PON）、乙太網路和其他資料通訊協定的錯誤更正碼，因為低密度奇偶校驗的糾錯能力相當接近理論最大值，即香農（Shannon）極限。用於執行解碼和糾錯的一種常見演算法是最小和（min-sum）演算法。

最小和引擎的一種實現方式是，將當前最小值與一個待比較值比較出新的最小值，如此迭代地完成所有待比較值的比較。然而，這種方法（使用線性最小值比較/多工器）相當緩慢，因為每次比較均需要一比較器和一多工器才能完成計算，因而需要與待比較值的數量成線性關係的數量的比較器和多工器。

另一種最小和引擎的實現方式是，以樹狀方式將每兩個待比較值比較出一最小值（第一層），該些最小值中每兩個再進行比較（第二層），如此執行樹縮減至最終結果。此方法（使用樹狀最小值比較/多工器）雖比第一種方法（使用線性最小值比較/多工器）快，但樹狀結構導致需要待比較值數量的二進制對數（log-base-2）數量的層。例如，17~32個待比較值將需要五層的比較器和多工器。層之間的流水線化(pipeline)無助於加快運算速度，因為最終結果需要用於下一輪計算。如果樹被流水線化，樹的第一階段必須等到樹的最後一階段完成第一輪迭代才能開始第二輪迭代。因此，總體計算時間仍然相同。

有鑑於此，本發明一實施例提出一種LDPC解碼器及一種（使用線性最小值比較/多工器）方法，透過扁平結構來執行計算，可提高計算的速度。

有鑑於此，本發明一實施例提出了一種LDPC解碼器和LDPC解碼方法（使用扁平化最小和計算引擎(flattened min-sum computation engine)），該方法透過將集合中的所有數值扁平化為獨熱向量(one-hot vectors)來一次性對所有數值進行選擇並優先解碼出最小值，來達到減少總體計算時間。以解決使用線性或樹狀的方式迭代地比較兩個數值所導致總體計算時間過長的問題。

LDPC解碼器包括一儲存單元及至少一運算引擎。儲存單元儲存一LDPC矩陣。運算引擎執行一LDPC解碼演算法，以根據LDPC矩陣對一碼字估算出一解碼結果。其中運算引擎包括一最小值搜尋單元，以在LDPC解碼演算法執行到一最小值搜尋演算時，根據複數輸入值輸出一最小值搜尋結果。最小值搜尋單元係執行：將此些輸入值轉換為複數獨熱向量，每一獨熱向量具有複數獨熱位元，在同一獨熱向量中的此些獨熱位元分別對應不重複的一獨熱位元索引；建立複數第一向量，每一第一向量不重複地對應於此些獨熱位元索引中的一目標位元索引，且每一第一向量呈現此些獨熱向量中在目標位元索引上的此些獨熱位元間執行或運算的結果；及根據此些獨熱位元索引，由低位元至高位元，對此些第一向量優先解碼出一最小值，此最小值為第一個其值為「1」的第一向量所對應的目標位元索引，其中最小值搜尋結果包括此最小值。

最小值搜尋方法由LDPC解碼器執行，適於根據複數輸入值輸出一最小值搜尋結果。最小值搜尋方法包括：將此些輸入值轉換為複數獨熱向量，每一獨熱向量具有複數獨熱位元，在同一獨熱向量中的此些獨熱位元分別對應不重複的一獨熱位元索引；建立複數第一向量，每一第一向量不重複地對應於此些獨熱位元索引中的一目標位元索引，且每一第一向量呈現此些獨熱向量中在目標位元索引上的此些獨熱位元間執行或運算的結果；及根據此些獨熱位元索引，由低位元至高位元，對此些第一向量優先解碼出一最小值，此最小值為第一個其值為「1」的第一向量所對應的目標位元索引，其中最小值搜尋結果包括此最小值。

根據本發明一些實施例的LDPC解碼器及一種最小值搜尋方法，透過扁平化設計可快速找出最小值、第二最小值或/及經偏移處理的最小值，可滿足高速通訊的高效解碼需求。

參照圖1，係本發明一實施例之LDPC解碼器100的架構示意圖。LDPC解碼器100包括一儲存單元110及一扁平化最小和計算引擎120，以執行一LDPC解碼方法。儲存單元110儲存一LDPC矩陣200（如圖2所示）。扁平化最小和計算引擎120為具有多個運算引擎130的區塊。在獲得一碼字（codeword）140之後，運算引擎130執行一LDPC解碼演算法，以根據LDPC矩陣200對碼字140估算出一解碼結果150。運算引擎130中的一最小值搜尋單元131透過將集合中的所有數值扁平化為獨熱向量300（如圖5所示）來一次性對所有數值進行選擇並優先解碼來找出最小值，而不是以線性或樹狀的方式迭代地比較兩個數值。

參照圖2，係本發明一實施例之LDPC矩陣200的部份示意圖。在此，以25G PON（被動光纖網路）使用的LDPC矩陣200為例，LDPC矩陣200是256x256子矩陣（sub-matrices）的69x12陣列構成的17664x3072稀疏矩陣（sparse matrix）。圖2所示的每一格子代表一個子矩陣。此些子矩陣為零矩陣（zero-matrix）或平移的單位矩陣（shifted identity matrix）。圖2所示LDPC矩陣200中空白的格子表示為零矩陣。圖2所示LDPC矩陣200中標示數字的格子表示為平移的單位矩陣，所示數字表示單位矩陣的平移量。舉例來說，若標示數字為“0”，表示此子矩陣為單位矩陣，若標示數字為“5”，表示此子矩陣為單位矩陣的各個橫列向右循環式位移（circular shift）5個元素。圖2僅提供一具體示例來說明本發明一實施例的LDPC矩陣200，LDPC矩陣200非以此示例的直行數量與橫列數量為限，也非限於所示例的該等子矩陣的位置與平移量。

LDPC矩陣200的每一直行視為一個變量節點（variable node），該等變量節點分別與碼字140的各位元相對應。LDPC矩陣200的每一橫列視為一個校驗節點（check node），每一校驗節點對應一校驗方程式。LDPC矩陣200中為“1”的元素表示其所在橫列的校驗節點與其所在直行的變量節點具有連結關係。LDPC解碼演算法是基於有迭代性（iterative）的置信度傳播（belief propagation）演算法，變量節點與校驗節點之間透過連結互相傳遞其計算的更新資訊。

參照圖3，係本發明一實施例之LDPC解碼演算法的流程圖。步驟S31為初始化步驟，對變量節點與校驗節點的資訊進行初始化。步驟S32為校驗節點更新步驟，校驗節點根據其連結的變量節點的資訊進行更新運算。步驟S33為變量節點更新步驟，變量節點根據其連結的校驗節點的資訊進行更新運算。步驟S34為終止判斷步驟，判斷是否滿足終止條件。若是，則結束流程；若否，則返回步驟S32，繼續下一次迭代。

參照式1及式2，係為步驟S31之初始化運算式。變量節點根據式1執行資訊初始化，校驗節點根據式2執行資訊初始化。其中，i代表迭代次數。N為變量節點總數，M為校驗節點總數。n代表第n個變量節點的編號，m代表第m個校驗節點的編號。N _m代表所有與第m個校驗節點連結的變量節點的集合。M _n代表所有與第n個變量節點連結的校驗節點的集合。 代表在第k次迭代中第n個變量節點傳遞給第m個校驗節點的資訊。 代表在第k次迭代中第m個校驗節點傳遞給第n個變量節點的資訊。I _n代表第n個變量節點的內在資訊（intrinsic information），用來表達此變量節點所對應的碼字140的位元為1或0的事後機率（posterior probability）。∀代表任意一個，∈代表屬於。在一些實施例中，內在資訊為對數似然比（Log-Likelihood Ratio，LLR）。

(式1)

(式2)

參照式3，係為步驟S32之校驗節點的更新運算式。其中，Π為求積符號（product symbol）。sgn()為符號函式（sign function），根據函式內的數值為0、正值或負值，分別返回0、1或-1。min()為最小值函數。N _m\n代表除了變量節點n之外的所有與第m個校驗節點連結的變量節點的集合。

(式3)

參照式4，係為步驟S33之變量節點的更新運算式。其中，∑為求和符號（summation symbol）。M _n\m代表除了校驗節點m之外的所有與第n個變量節點連結的校驗節點的集合。

(式4)

在步驟S34中，執行硬決策（hard decision）來解碼，並判斷是否滿足終止條件。若滿足條件，則結束流程。所述終止條件係，解碼結果150正確或迭代次數超出閾值。參照式5及式6，係為硬決策的運算式。其中，式5係計算每一變量節點的事後機率 。根據式5的計算結果，利用式6判斷出每一變量節點對應的位元值z _n，即獲得解碼結果150（序列z ₁, z ₂, …, z _n）。式7是用來確認解碼結果150是否正確（滿足式7則為正確），其中H代表LDPC矩陣200， 代表解碼結果150（序列z ₁, z ₂, …, z _n）的轉置（transpose）。

(式5)

(式6)

(式7)

根據上述說明可以看到（如式3及式4），在迭代過程中會計算 資訊之總和（ ），並從中找出最小值，因此在此說明的LDPC解碼演算法稱為最小和演算法。在校驗節點的更新運算（式3）中，需要執行最小值搜尋演算，以從變量節點集合N _m\n所對應的內在資訊中找出最小值。因此，如圖1所示，每一運算引擎130包括一最小值搜尋單元131，以在LDPC解碼演算法執行到一最小值搜尋演算時，該等最小值搜尋單元131執行一最小值搜尋程序，根據複數輸入值（於此為變量節點集合N _m\n所對應的內在資訊）輸出一最小值搜尋結果。在一些實施例中，每一輸入值為對應變量節點的內在資訊（如對數似然比）。

在一些實施例中，運算引擎130的數量是依據子矩陣的橫列數量決定。如前述圖2之例，運算引擎130的數量為256個。每一運算引擎130分別對應於子矩陣中的一橫列（校驗節點），並執行相應的更新運算（式3）。因此，此些運算引擎130能夠一次並行處理256橫列（又稱為一層）的運算，如此分次處理完LDPC矩陣200的所有層（如圖2所示為12層）之後，即完成一次迭代的校驗節點更新。最小值搜尋單元131為複數個，以並行處理對應於LDPC矩陣200中位於同一層的各橫列的最小值搜尋程序。亦即，一個最小值搜尋單元131處理對應一個橫列上的最小值搜尋演算。

相似地，在一些實施例中，扁平化最小和計算引擎120還包括其他運算引擎（圖2未示），分次並行處理所有變量節點更新，於此不再重複說明。

在一些實施例中，LDPC矩陣200中的多個直行合併為一行群組。例如圖2所示，第67行與第68行的每一橫列上至多僅有一個非零矩陣，故可合併為一行群組，同理第65行與第66行也可合併為另一行群組。由於LDPC矩陣200的稀疏特性，在合併為行群組之後，可大幅減少直行的數量。一般來說，合併為行群組之後，直行數量約可減少至20多個（mid-twenties），例如23~27個。如此，可以減少待執行最小值搜尋演算的輸入值的數量，但本發明非以輸入值數量需少於30個為必要。由於在一個平移的單位矩陣中，每一列上僅會有一個“1”，因此對於一個最小值搜尋單元131而言，每一行群組至多對應一個輸入值。亦即，最小值搜尋單元131在一次最小值搜尋演算中處理的輸入值數量至多等同於行群組的數量。在一些實施例中，一個最小值搜尋單元131所處理的輸入值的數量在23~69的範圍內。

參照圖4，係為本發明一實施例之最小值搜尋演算之流程圖（一）。步驟S41為獨熱（one-hot）向量300轉換步驟，係將多個輸入值G分別轉換為獨熱向量300，如圖5所示。圖5為本發明一實施例之獨熱向量300轉換示意圖。在一些實施例中，每一輸入值G的位元寬度（bit width）為4位元或5位元，以在糾錯能力與邏輯數量中取得平衡。圖5係以5位元的24個輸入值G[0]~G[23]來說明，然而輸入值G的數量與其位元數非以此為限。每一獨熱向量300具有複數位元（後稱「獨熱位元310」），在同一獨熱向量300中的此些獨熱位元310分別對應不重複的一獨熱位元索引（one-hot bit index）400。在此，獨熱位元索引400為“0”~“31”，其相當於在獨熱向量300中所代表的數。以輸入值G[0]為例，其轉換為由F[744]、…F[168]、F[144]、F[120]、F[96]、F[72]、F[48]、F[24]、F[0]等獨熱位元310所構成的獨熱向量300。標示有實線粗框的獨熱位元310其值為1，沒有標示粗框的獨熱位元310其值為“0”。例如，輸入值G[4]的值為“6”，其轉換為獨熱向量300後，F[148]獨熱位元310的值為“1”，F[148]獨熱位元310對應到的獨熱位元索引400為“6”。

參照程式碼1，係為獨熱向量300轉換的一實施態樣。輸入值G[0]~G[23]逐一地與獨熱位元索引400相比，當若兩者相同，則將對應的獨熱位元310設為“1”。

程式碼1： F[0] = (G[0] == 0); F[1] = (G[1] == 0); … F[23] = (G[23] == 0); F[24] = (G[0] == 1); … F[767] = (G[23] == 31);

需要說明的是，雖然圖5是以二維陣列形式表達輸入值G與獨熱向量300的關係。然而，F[0]~F[767]實質是一維陣列，即一展平向量（flattened vector）。為了方便後續說明，於此定義“0”~“767”為展平位元索引（flattened bit index）。此些展平位元索引一對一地對應獨熱向量300的獨熱位元310。展平向量具有相連接的複數序列（sequences）500，每一序列500對應圖5所示的每一直行。每一序列500包括此些獨熱向量300中在同一獨熱位元索引400上的該些獨熱位元310。例如，圖5中標示的序列500包括每一獨熱向量300中對應4的獨熱位元索引400的獨熱位元310（F[96]~F[119]）。此些序列500所包括的獨熱位元310以同一編排順序排列。如圖5所示，此些序列500所包括的獨熱位元310均由上至下依序排列，且此些序列500的排列順序與輸入值G[0]~G[23]的索引順序一致。此些序列500按照其對應的獨熱位元索引400升序（ascending）排列。例如，包括F[0]~F[23]獨熱位元310的序列500，其對應的獨熱位元索引400為“0”；包括F[24]~F[47]獨熱位元310的序列500，其對應的獨熱位元索引400為“1”，依此類推。

合併參照圖4、圖5及程式碼2。步驟S42係建立複數第一向量。每一第一向量不重複地對應於此些獨熱位元索引400中的其中之一（於後稱「目標位元索引」）。舉例來說，第一向量First_vector[0]對應的獨熱位元索引400為“0”，第一向量First_vector[1]對應的獨熱位元索引400為“1”，以此類推。每一第一向量呈現此些獨熱向量300中在目標位元索引上的此些獨熱位元310間執行或運算（OR operation）的結果。舉例來說，第一向量First_vector[0]呈現獨熱位元索引400為0的獨熱位元310（F[0]~F[23]）之間的或運算的結果。因此，若某一第一向量為“1”，表示至少有一獨熱向量300其對應目標位元索引的獨熱位元310為“1”。

程式碼2： First_vector[0] = F[0] || F[1] || … F[23]; First_vector[1] = F[24] || F[25] || … F[47]; … First_vector[31] = F[744] || F[755] || … F[767]

合併參照圖4、圖5及程式碼3。步驟S43係從此些第一向量中優先解碼（priority decode）出最小值。具體係，根據此些獨熱位元索引400，由低位元至高位元（於此為從“0”至“31”），對此些第一向量優先解碼出最小值。最小值為第一個其值為“1”的第一向量所對應的目標位元索引。以圖5為例，第一個其值為“1”的第一向量所對應的獨熱位元索引400為“1”，因此最小值搜尋結果包括的最小值為“1”。

程式碼3： foreach bit (0..31) last if(First_vector[bit]); Min_value = bit;

合併參照圖5、圖6及程式碼4。圖6為本發明一實施例之最小值搜尋演算之流程圖（二）。此流程是用來找出前述最小值是在輸入值G中的何者。在步驟S61中，建立第二向量。每一第二向量不重複地對應於獨熱向量300中的其中之一（於後稱「目標獨熱向量」）。每一第二向量呈現分別對於目標獨熱向量中的每一獨熱位元310進行一邏輯判斷所產生的複數判斷結果間執行或運算的結果。其中，邏輯判斷為一第一條件及一第二條件的交集。第一條件是進行邏輯判斷的獨熱位元310為“1”。第二條件是，在展平向量中，在比進行邏輯判斷的獨熱位元310的展平位元索引更小的此些展平位元索引上的此些獨熱位元310均為“0”。以第二向量Second_vector[0]來說明，係針對其對應的獨熱向量300中的各個獨熱位元310（F[0], F[24], F[48], …, F[744]）進行邏輯判斷。例如，對於F[24]，第一條件是判斷F[24]是否為“1”，第二條件是判斷F[23:0]是否都為“0”，若兩個條件都為真，表示F[24:0]中F[24]是第一個為“1”的獨熱位元310。此獨熱位元310所在的獨熱向量300所對應的輸入值G[0]，即為具有最小值的輸入值。補充說明，由於沒有比F[0]的展平位元索引更小的展平位元索引，因此對於F[0]僅有判斷第一條件，即判斷F[0]是否為1。

程式碼4： Second_vector[0] = F[0] || F[24] && (F[23:0]==0) || F[48] && (F[47:0]==0)… F[744]&&(F[743:0]==0); Second_vector[1] = F[1] || F[25] && (F[24:0]==0) || F[49] && (F[48:0]==0)… F[745]&&(F[744:0]==0); Second_vector[2] = F[2] || F[26] && (F[25:0]==0) || F[50] && (F[49:0]==0)… F[746]&&(F[745:0]==0); … Second_vector[23] = F[23] || F[47]&&(F[46:0]==0)|| F[71] && (F[70:0]==0)…F[767]&&F[766:0]==0;

合併參照圖5、圖6及程式碼5。步驟S62係從此些第二向量中優先解碼出對應最小值的輸入值G的索引（後稱「輸入值索引」），以在最小值搜尋結果中包括此輸入值索引。具體係，根據序列500中獨熱位元310的編排順序（亦即輸入值G的排列順序），對此些第二向量優先解碼出對應最小值的輸入值索引。輸入值索引為第一個邏輯判斷為真的第二向量所對應的編排順序的一順序索引。如圖5中，F[24]獨熱位元310為最小值，因此經過前述步驟S61之後，第二向量Second_vector[0]的邏輯判斷為真（表示為“1”），且其為第一個邏輯判斷為真的第二向量。於是，最小值的輸入值索引為“0”（即此第二向量的索引值，也同於相應的輸入值索引）。

程式碼5： foreach bit (0..23) last if(Second_vector[bit]); Min_index = bit;

在一些實施例中，LDPC解碼演算法使用前述最小和演算法的變形，例如：正規化最小和（normalized min-sum）演算法、補償式最小和（offset min-sum）演算法等，其除了使用最小值之外，還會使用第二最小值（second minimum）。在一例子中，當輸入值G[2]與G[5]皆為“3”，其他輸入值G為“4”，則最小值為“3”，次小值也為“3”。在另一個例子中，當輸入值G[1]為“2”，當輸入值G[0]為 “4”，其他輸入值G大於“4”，則最小值為“2”，次小值為“4”。接下來說明如何透過前述展平向量獲得第二最小值，以提供包括第二最小值的最小值搜尋結果。

合併參照圖5、圖7及程式碼6，圖7為本發明一實施例之第二最小值搜尋演算之流程圖。在步驟S71中，建立複數第三向量。每一第三向量不重複地對應於一個獨熱位元索引400（即目標位元索引）。第三向量呈現分別對於獨熱向量300的目標位元索引上的獨熱位元310進行一邏輯判斷所產生的複數結果的交集。其中，邏輯判斷為一第三條件及一第四條件的交集。第三條件是進行邏輯判斷的獨熱位元310為“1”。第四條件是，在展平向量中，在比進行邏輯判斷的獨熱位元310的展平位元索引更小的此些展平位元索引上的獨熱位元310非均為 “0”。以第三向量Third_vector[2]來說明，係針對其對應的獨熱位元索引400（“2”）上的獨熱向量300中的各個獨熱位元310（F[48]~F[71]）進行邏輯判斷。例如，對於F[50]，第三條件是判斷F[50]是否為“1”，第四條件是判斷F[49:0]是否非均為“0”，若兩個條件都為真，表示F[50:0]中F[49]是第二個為“1”的獨熱位元310。補充說明，由於沒有比F[0]的展平位元索引更小的展平位元索引，因此在第三向量Third_vector[0]中省略了對F[0]的判斷。

程式碼6： Third_vector[0] = F[1] &&!(F[0]==0) || F[2] && !(F[1:0]==0) || … F[23] && !(F[22:0]==0); Third_vector[1] = F[24] && !(F[23:0]==0) || F[25] && !(F[24:0]==0) … F[47] && !(F[46:0]==0); … Third_vector[31] = F[744] && !(F[743:0]==0) || F[745] && !(F[744:0]==0) || … F[767] && !(F[766:0]==0);

合併參照圖5、圖7及程式碼7。步驟S72係從此些第三向量中優先解碼出第二最小值。具體係，根據此些獨熱位元索引400，由低位元至高位元，對此些第三向量優先解碼出第二最小值。此第二最小值為第一個邏輯判斷為真的第三向量所對應的目標位元索引。如圖5中，F[50]獨熱位元310為第二最小值，因此經過前述步驟S71之後，第三向量Third_vector[2]的邏輯判斷為真（表示為“1”），且其為第一個邏輯判斷為真的第三向量。於是，第二最小值為“2”（即相應的目標位元索引，也同於此第三向量的索引值）。

程式碼7： foreach bit (0..31) last if(Third_vector[bit]); Third_min_value = bit;

在一些實施例中，一些最小和演算法的變形（例如前述之補償式最小和演算法）所使用的最小值，是經過偏移（offset）處理的。亦即，最小值搜尋結果包括的最小值為經偏移處理的最小值。接下來說明如何將前述尋找出的最小值進行偏移處理。

合併參照圖5、圖8及程式碼8~10，圖8為本發明一實施例之最小值搜尋演算之流程圖（三）。在根據前述步驟S43獲得第一向量之後，執行步驟S44至步驟S46之偏移處理。在此，偏移量是以1為例，但本發明非以此為限。

在步驟S44中，對於獨熱位元索引400在偏移量以下的第一向量（於此為First_vector[1:0]），優先解碼出第一值（bit_no_offset），如程式碼8所示。第一值（bit_no_offset）為第一個其值為“1”的第一向量所對應的獨熱位元索引400。若第一向量First_vector[0]為“1”，第一值（bit_no_offset）為“0”。若第一向量First_vector[0]為“0”且第一向量First_vector[1]為“1”，第一值（bit_no_offset）為“1”。

程式碼8： foreach bit_no_offset (0..1) last if(First_vector[bit_no_offset]);

在步驟S45中，對於其他的獨熱位元索引400的第一向量，亦即獨熱位元索引400不在偏移量以下的第一向量（於此為First_vector[31:2]），優先解碼出第二值（bit_offset），如程式碼9所示。第二值（bit_offset）為第一個其值為“1”的第一向量所對應的獨熱位元索引400減去偏移量。例如，當第一向量First_vector[2]為“0”且第一向量First_vector[3]為“1”，第二值（bit_offset）為2。

程式碼9： foreach bit_ offset (1..30) last if(First_vector[bit_offset+1]);

在步驟S46中，將獨熱位元索引400在偏移量以下的第一向量（First_vector[1:0]）執行或運算。若運算結果為“1”，表示最小值出現在此些第一向量中，則將第一值作為經偏移處理的最小值。若運算結果為“0”，表示最小值出現其他第一向量中，則將第二值作為經偏移處理的最小值。

程式碼10： Min_value_with_offset = (First_vector[0] || First_vector[1]) ? bit_no_offset : bit_offset;

相較於使用如程式碼11以比較邏輯的方式，圖8根據由展平向量建立的第一向量執行偏移處理，能夠利用扁平結構（flattened structure）提昇處理速度。

程式碼11： Min_value_with_offset = Min_value ＞ 1 ? Min_value – 1 : Min_value;

本發明一些實施例提出之LDPC解碼器及最小值搜尋方法，透過扁平化設計可快速找出最小值、第二最小值或/及經偏移處理的最小值，而不需以線性方式或基於樹的方式迭代地比較，可滿足高速通訊的高效解碼需求。

100:LDPC解碼器 110:儲存單元 120:扁平化最小和計算引擎 130:運算引擎 131:最小值搜尋單元 140:碼字 150:解碼結果 200:LDPC矩陣 300:獨熱向量 310:獨熱位元 400:獨熱位元索引 500:序列 G,G[0]~G[23]:輸入值 S31~S34:步驟 S41~S46:步驟 S61~62:步驟 S71~72:步驟

圖1為本發明一實施例之LDPC解碼器的架構示意圖。 圖2為本發明一實施例之LDPC矩陣的部份示意圖。 圖3為本發明一實施例之LDPC解碼演算法的流程圖。 圖4為本發明一實施例之最小值搜尋演算之流程圖（一）。 圖5為本發明一實施例之獨熱向量轉換示意圖。 圖6為本發明一實施例之最小值搜尋演算之流程圖（二）。 圖7為本發明一實施例之第二最小值搜尋演算之流程圖。 圖8為本發明一實施例之最小值搜尋演算之流程圖（三）。

S41~S43:步驟

Claims (11)

1. 一種最小值搜尋方法，適於根據複數輸入值輸出一最小值搜尋結果，該最小值搜尋方法包括：將該些輸入值轉換為複數獨熱向量，每一該獨熱向量具有複數獨熱位元，在同一該獨熱向量中的該些獨熱位元分別對應不重複的一獨熱位元索引；建立複數第一向量，每一該第一向量不重複地對應於該些獨熱位元索引中的一目標位元索引，且每一該第一向量呈現該些獨熱向量中在該目標位元索引上的該些獨熱位元間執行或運算的結果；及根據該些獨熱位元索引，由低位元至高位元，對該些第一向量優先解碼出一最小值，該最小值為第一個其值為「1」的該第一向量所對應的該目標位元索引，其中該最小值搜尋結果包括該最小值。
2. 如請求項1所述之最小值搜尋方法，其中該些獨熱向量在一展平向量中，該展平向量具有複數展平位元索引，該些展平位元索引一對一地對應該些獨熱向量的該些獨熱位元，該展平向量包括相連接的複數序列，每一該序列包括該些獨熱向量中在同一該獨熱位元索引上的該些獨熱位元，該些序列所包括的該些獨熱位元以同一編排順序排列，且該些序列按照其對應的該獨熱位元索引升序排列。
3. 如請求項2所述之最小值搜尋方法，還包括：建立複數第二向量，其中每一該第二向量不重複地對應於該些獨熱向量中的一目標獨熱向量，每一該第二向量呈現分別對於該目標獨熱向量中的每一該獨熱位元進行一邏輯判斷所產生的複數判斷結果間執行或運算的結果，其中該邏輯判斷為一第一條件及一第二條件的交集，該第一條件是進行該邏輯判斷的該獨熱位元為「1」，該第二條件是在該展平向量中在比進行該邏輯判斷的該獨熱位元的該展平位元索引更小的該些展平位元索引上的該些獨熱位元均為「0」；及根據該編排順序，對該些第二向量優先解碼出對應該最小值的一輸入值索引，該輸入值索引為第一個該邏輯判斷為真的該第二向量所對應的該編排順序的一順序索引，其中該最小值搜尋結果還包括該輸入值索引。
4. 如請求項2所述之最小值搜尋方法，還包括：建立複數第三向量，其中每一該第三向量不重複地對應於該些獨熱位元索引中的該目標位元索引，該第三向量呈現分別對於該些獨熱向量的該目標位元索引上的該獨熱位元進行一邏輯判斷所產生的複數結果的交集，其中該邏輯判斷為一第三條件及一第四條件的交集，該第三條件是進行該邏輯判斷的該獨熱位元為「1」，該第四條件是在該展平向量中在比進行該邏輯判斷的該獨熱位元的該展平位元索引更小的該些展平位元索引上的該些獨熱位元非均為「0」；及根據該些獨熱位元索引，由低位元至高位元，對該些第三向量優先解碼出一第二最小值，該第二最小值為第一個該邏輯判斷為真的該第三向量所對應的該目標位元索引，其中該最小值搜尋結果還包括該第二最小值。
5. 如請求項1所述之最小值搜尋方法，還包括：對該最小值執行一偏移處理，其中該最小值搜尋結果包括的該最小值為經該偏移處理的該最小值。
6. 如請求項5所述之最小值搜尋方法，其中該偏移處理包括：對於該獨熱位元索引在一偏移量以下的該些第一向量，優先解碼出一第一值，該第一值為第一個其值為「1」的該第一向量所對應的該獨熱位元索引；對於其他的該些第一向量，優先解碼出一第二值，該第二值為第一個其值為「1」的該第一向量所對應的該獨熱位元索引減去該偏移量；及將該獨熱位元索引在該偏移量以下的該些第一向量執行或運算，其中，若運算結果為「1」，則將該第一值作為經該偏移處理的該最小值，若運算結果為「0」，則將該第二值作為經該偏移處理的該最小值。
7. 如請求項1所述之最小值搜尋方法，其中每一該輸入值為一對數似然比。
8. 如請求項1所述之最小值搜尋方法，其中每一該輸入值為4位元或5位元。
9. 如請求項1所述之最小值搜尋方法，其中該些輸入值的數量在23~69的範圍內。
10. 如請求項1所述之最小值搜尋方法，其中該最小值搜尋方法由複數最小值搜尋單元分別執行，而對應於一LDPC矩陣中位於同一層的各列進行並行處理。
11. 一種LDPC解碼器，執行如請求項1至10中任一項所述之最小值搜尋方法。