在硬決策軟解碼期間決定何時結束位翻轉算法的方法與流程

2023-10-09 04:04:54 2

本發明涉及用於一低密度奇偶校驗(low-densityparitycheck，ldpc)解碼器的硬解碼(harddecoding)，尤其是涉及一種具備省電設計的位翻轉(bitflipping)算法。
背景技術：
：：低密度奇偶校驗解碼器使用具有多個奇偶位的線性錯誤更正碼，其中所述奇偶位建立具有多個奇偶方程式的解碼器，以對接收到的碼字(codeword)進行驗證。舉例來說，低密度奇偶校驗可為一固定長度的二進位代碼，其中所述二進位代碼中所有的符元(symbol)相加會等於零。在編碼過程中，所有的數據位會被重複執行並且被傳送至對應的編碼器，其中每個編碼器會產生一奇偶符元(paritysymbol)。碼字是由k個信息位(informationdigit)以及r個校驗位(checkdigit)所組成。如果碼字總共有n位，則k＝n-r。上述碼字可用一奇偶校驗矩陣來表示，其中所述奇偶校驗矩陣具有r列(表示方程式的數量)以及n行(表示位數)，如圖1所示。這些碼被稱為「低密度」是因為相較於奇偶校驗矩陣中位0的數量而言，位1的數量相對的少。在解碼過程中，每次的奇偶校驗都可視為一奇偶校驗碼，並隨後與其他奇偶校驗碼一起進行交互校驗(cross-check)，其中解碼會在校驗節點(checknode)進行，而交互校驗會在變量節點(variablenode)進行。ldpc解碼器支持三種模式：硬決策硬解碼(harddecisionharddecoding)、軟決策硬解碼(softdecisionharddecoding)，以及軟決策軟解碼(softdecisionharddecoding)。圖1是奇偶校驗矩陣h(圖1的上半部份)以及tannergraph(圖1的下半部份)的示意圖，其中tannergraph是另一種表示碼字的方式，並且可用於解釋當使用一位翻轉(bitflipping)算法時，ldpc解碼器的一些涉及硬決策軟解碼的操作。在tunnergraph中，方形(c1～c4)所表示的校驗節點(checknode)代表奇偶位(paritybit)的數量，且圓形(v1～v7)所表示的變量節點(variablenode)是一碼字中位的數量。如果一特定方程式與碼符元(codesymbol)有關，則對應的校驗節點與變量節點之間會以聯機來表示。被估測的消息會沿著這些聯機來傳遞，並且於節點上以不同的方式組合。一開始時，變量節點將發送一估測至所有聯機上的校驗節點，其中這些聯機包括被認為是正確的位。接著，每個校驗節點會依據對所有其他的連接的估測(connectedestimate)來針對每一變數節點進行新的估測，並且將新的估測傳回至變量節點。新的估測是基於：奇偶校驗方程式迫使所有的變量節點連接至一特定校驗節點，以使總和為零。這些變量節點會接收新的信息並且使用多數規則(majorityrule)(也就是硬決策)來判斷所傳送的原始位的值是否正確，若不正確，所述原始位會被翻轉(flipped)。接著，所述位會被傳回至所述校驗節點，且上述步驟會被迭代地執行一預定次數，直到符合這些校驗節點的奇偶校驗方程式。若有符合這些奇偶校驗方程式(也就是校驗節點所計算的值符合接收自變量節點的值，則可啟用提前終止(earlytermination)，這會使得系統在最大迭代次數達到之前就結束解碼程序。迭代的次數會被錯誤位的數量所限制，若執行超出特定次數的迭代，錯誤位會急劇地增加，在此情況下，有需要將系統切換至一不同模式。在無法得知錯誤位的正確數量的情況下，何時要切換模式(例如由位翻轉切換至軟決策軟解碼(softdecisionsoftdecoding))會根據解碼器的性能來決定。上述的位翻轉算法是一低功率解碼方法，而硬決策軟解碼(harddecisionsoftdecoding)也可採用其他的解碼算法，諸如n2解碼器以及n6解碼器所採用的算法。這些不同的解碼算法將會導致不同結果，而這些結果各有其優缺點。若能判斷出位翻轉算法的可更正位率(correctablebitrate)會在何時開始下降，則可據以切換至比較適合的解碼類型。位翻轉解碼器在原始錯誤位(rawerrorbit)較少的情況下具有低功率的優勢，而當位翻轉解碼器的效能開始下降時，則有需要採用其他具有較高的可更正率的解碼器。技術實現要素：本發明的一目的在於公開一種用於決定位翻轉算法的效能何時開始下降的方法，以及使用所產生的信息來切換至一具有更高可更正率的解碼算法。本發明的一實施例公開了一種用於在一低密度奇偶校驗(lowdensityparitycheck，ldpc)解碼器執行硬決策軟解碼(harddecisionsoftdecoding)的期間決定何時結束一位翻轉算法的方法。所述方法包括有：選取一特定次數的迭代，作為一第一臨界值；當達到所述第一臨界值時，針對目前為止所進行的每一次迭代決定出一最高可變節點碼字(codeword)，以產生多個最高可變節點碼字；將所述最高可變節點碼字與一第二臨界值進行比較；以及當所述最高可變節點碼字的值是小於或等於所述第二臨界值時，結束所述位翻轉算法。附圖說明圖1是根據現有技術的用於進行低密度奇偶校驗解碼的一奇偶校驗矩陣以及tannergraph的示意圖。其中，附圖標記說明如下：h奇偶校驗矩陣c1～c4校驗節點v1～v7變數節點具體實施方式如上所述，本發明的目的在於避免位翻轉算法沒有效率地進行太多次迭代，此外，本發明能夠找出解碼算法需要被切換成硬決策軟解碼的正確時間點。為了實現以上目的，本發明公開一種動態的位翻轉方法，其中迭代的次數並非預設，而是採用一效能參數來作為決定最大迭代次數的指標(benchmark)。在進行位翻轉期間，所述變量節點是使用多數決定準則(majorityrule)，以通過找出最大的變量節點、翻轉原始位以及判斷校驗節點是否為零，來決定出正確信息。在執行一特定次數的迭代之後，所有的校驗節點應為零，除非有無法更正的錯誤出現，而這種情況下就需要一種新的解碼算法。一變量節點的行權重被定義為奇偶校驗矩陣的一行中「1」的數量，這也表示所述變量節點的最大錯誤。參考圖1，行權重也代表了每一變量節點耦接至多少個校驗節點。行權重在此作為量測之用，以決定何時結束位翻轉。數值t是用來在使用行權重進行量測之前，設定一最小迭代次數。在本範例中，t被選為3，這是因為通常不太可能在第一次甚至是第二次迭代就會滿足所述碼字，然而t的值不限於此，可根據不同的需求來作調整。令t等於3，以及令行權重事先用來進行量測效能的迭代次數等於i(即當前迭代次數為i)，則所述解碼器將會經歷一第一次迭代「i–2」以及一第二次迭代「i–1」。如以上所述，位翻轉算法會參考多個變量節點的最大碼字並且翻轉一原始位。在此情況下，系統也會分別針對第一次迭代i–2、第二次迭代i–1以及當前迭代i，來將最大變量節點碼字的值與對應的「行權重除以2」來作比較。倘若每一次迭代所使用的值小於或等於對應的「行權重除以2」，這表示解碼模式需要切換。反之，倘若每一次迭代所使用的值大於對應的行權重除以2，這表示所述位翻轉算法可再作一次迭代，可用以下方程式來表示：若[mi–t，…，mi]<floor(columnweight/2)，則終止位翻轉。在以上方程序中，mi是第i次迭代的最大臨界值(也就是最大的變量碼字)，以及t是期望的迭代次數，其中t是可調整。一旦判斷出在經過一定次數的迭代之後，所述最高可變節點碼字小於或等於所述行權重除以2，即表示使用目前的位翻轉算法的錯誤位已多到無法解決的程度，故需要切換另一種解碼算法。由以上說明可知，本發明通過只對算法執行一特定次數的迭代，來節省進行位翻轉的功率損耗。通過使用行權重作為一效能參數，可迅速地得知終止位翻轉的正確時間點，並且於目前的位翻轉算法終止後，可選用其他的解碼算法。以上所述僅為本發明的優選實施例而已，並不用於限制本發明，對於本領域的技術人員來說，本發明可以有各種更改和變化。凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。當前第1頁12當前第1頁12