[go: up one dir, main page]

TW201703442A - 階層式低密度奇偶碼解碼器的早期退出系統及方法 - Google Patents

階層式低密度奇偶碼解碼器的早期退出系統及方法 Download PDF

Info

Publication number
TW201703442A
TW201703442A TW105114536A TW105114536A TW201703442A TW 201703442 A TW201703442 A TW 201703442A TW 105114536 A TW105114536 A TW 105114536A TW 105114536 A TW105114536 A TW 105114536A TW 201703442 A TW201703442 A TW 201703442A
Authority
TW
Taiwan
Prior art keywords
vector
sub
check
code
stored
Prior art date
Application number
TW105114536A
Other languages
English (en)
Inventor
默罕莫德阿塔爾 哈伊勒
雪莉小玲 方
吉米 蒲
Original Assignee
聯芸科技（杭州）有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 聯芸科技（杭州）有限公司 filed Critical 聯芸科技（杭州）有限公司
Publication of TW201703442A publication Critical patent/TW201703442A/zh

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H03M13/1108—Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H03M13/1131—Scheduling of bit node or check node processing
    • H03M13/114—Shuffled, staggered, layered or turbo decoding schedules
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H03M13/1128—Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/116—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/116—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
    • H03M13/1165—QC-LDPC codes as defined for the digital video broadcasting [DVB] specifications, e.g. DVB-Satellite [DVB-S2]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0045—Arrangements at the receiver end
    • H04L1/0047—Decoding adapted to other signal detection operation
    • H04L1/005—Iterative decoding, including iteration between signal detection and decoding operation
    • H04L1/0051—Stopping criteria
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0056—Systems characterized by the type of code used
    • H04L1/0057—Block codes

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Signal Processing (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Error Detection And Correction (AREA)
  • Multimedia (AREA)
  • Computational Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Algebra (AREA)
  • Computing Systems (AREA)

Abstract

本發明提供的系統與方法，可以偵測到一階層式低密度奇偶碼解碼器的一或多層的位元節點的硬決策之改變，並且可以做這些層之部分校驗碼累加運算的更新。當這些位元節點的硬決策產生之後，會和既有的舊值進行比較。當硬決策改變時，相對應於該已改變之硬決策的碼節點之校驗矩陣的一或多行中具有非零元素的各層之部分校驗碼的計算結果被累加。若硬決策不變時，無須更新相應層之部分校驗碼的計算結果。碼字的硬決策改變會被追蹤，相應於已改變硬決策之位元節點的校驗矩陣各行所對應之各層的部分校驗碼被翻動。

Description

階層式低密度奇偶碼解碼器的早期退出系統及方法
本發明係關於在通信或資料存儲系統中用於解碼的系統與方法，特別係關於在階層式低密度奇偶碼(LDPC,low density parity check)解碼器當中用於早期偵測到已正確解出之碼字(codeword)的系統與方法。
在通信或資料存儲系統中，被接收器或控制器所接收的攜帶資訊的信號可能會被噪訊、電磁干涉或其他種擾動而遭到破壞。為了確保資訊能夠被正確地重建，通常會使用錯誤更正碼(ECC,error correction codes)，亦即在攜帶資訊的信號中加入重複位元或檢查位元。低密度奇偶碼屬於一種稱之為線性區塊碼的錯誤更正碼。低密度奇偶碼是由分布非常稀疏之元素所形成的校驗位元矩陣來定義，亦即該稀疏校驗矩陣中的非零元素的分布密度相當低。低密度奇偶碼解碼器可能需要疊代地判斷一接收向量的最可能的乘載資訊碼字。低密度奇偶碼解碼過程可以使用總和乘積(sum-product)演算法、最小值總和(Min-Sum)演算法或其變形來實現。給定由m乘以n的校驗矩陣所定義的一個低密度奇偶碼，不論是採用哪一種特定解碼演算法，低密度奇偶碼的解碼過程可以被視為在某一集合中m個校驗(或限制)節點(check node)與另一集合中n個位元(或訊息)節點(bit node)之間 的一個疊代的訊息更新與傳遞(message update and passing)程序。不同的低密度奇偶碼解碼演算法具有不同的訊息更新計算規則與/或不同的訊息傳遞(或交換)排程策略。為了校驗一個被解出的碼字，低密度奇偶碼解碼器可能要在一個校驗作業(parity check operation)當中，執行硬決策(hard decision)向量與低密度奇偶碼之校驗矩陣的一矩陣相乘運算。當矩陣相乘運算的結果產生出零向量時，就能宣告該碼字是有效的。舉例來說，在一具有區塊長度n的低密度奇偶碼中，其具有(n-m)個資訊位元與m個檢查位元，其碼率為(n-m)/n，該低密度奇偶碼的校驗矩陣為一個m乘以n的二元(binary)矩陣。將一個m乘以n的校驗矩陣乘以一個n乘以1的接收向量之硬決策，產生m個校驗節點。在階層式的低密度奇偶碼解碼過程中，m乘以n校驗矩陣的每一列都稱為一層。每層都有一個校驗節點，可以對該矩陣之一層內的具有元素1的硬決策進行異或(XOR,exclusive-or)運算，用以產生該層的校驗碼(syndrome)。當所有層的校驗碼都為零時，可以說碼字已被正確地解出。
在傳統的階層式低密度奇偶碼解碼器中，硬決策的產生是在多個層內進行。當接收到某一層的位元節點之硬決策之後，可以更新該層的校驗碼。當需要更新所有層的校驗碼時，就需要階層式低密度奇偶碼解碼器在每一層都執行更新動作，可能需要耗費m個時脈週期。當在這個階層化解碼的過程中，有任何位元節點的硬決策改變時，需要耗費另外m個時脈週期來驗證所有層的校驗碼是否都為零。這種做法增加了解碼的延遲時間，並且降低了解碼的輸出總量。
再者，由於傳統的階層式低密度奇偶碼解碼器持續地更新硬決策，階層式的解碼過程在校檢作業進行時必須暫停運作，這更降低解碼 的輸出總量。為了避免在執行檢查作業時暫停解碼過程，其中一種做法是採用儲存兩套硬決策的記憶體。可以分別在這兩套記憶體上分別同時執行檢查作業和硬決策更新。然而，多出一套硬決策記憶體的做法會增加成本、晶片面積與耗電量。而且也沒有辦法保證當所有硬決策產生之後，校驗作業會馬上停止，因為解碼作業的退出時間仍然取決於正確解碼的資料何時進到硬決策的記憶體內。在最差的情況底下，仍然可能在最後的硬決策產生之後的m個時脈週期才完成校驗碼的計算，以及指示解碼完成的校驗作業。據此，需要一種階層式低密度奇偶碼解碼器，能在執行檢查作業時具有一最小化且固定的退出時間，而且能將成本、晶片面積與耗電量的增加減到最低。
本發明提供的系統與方法，可以偵測到一階層式低密度奇偶碼解碼器的一或多層的位元節點的硬決策之改變，並且可以做這些層之部分校驗碼累加運算的更新。當這些位元節點的硬決策產生之後，會和既有的舊值進行比較。當硬決策改變時，相對應於該已改變之硬決策的碼節點之校驗矩陣的一或多行中具有非零元素的各層之部分校驗碼的計算結果被累加。若硬決策不變時，無須更新相應層之部分校驗碼的計算結果。由於一低密度奇偶碼之一行的非零元素之個數，或稱為行權重會少於各層的總數，對已改變之硬決策的對應層進行部分校驗碼的累加計算，可能只會增加最少量的計算複雜度。
在一或多個實施例中，碼字的硬決策改變會被追蹤，相應於已改變硬決策之位元節點的校驗矩陣各行所對應之各層的部分校驗碼被翻 動。為了增加解碼器的處理總量，可以分割校驗矩陣以便能夠平行地產生多組硬決策。本發明的校驗碼累加技術可以被彈性地平行處理化，以便配合多組硬決策的平行產生。該技術也自然地適用於校驗單元中對於碼字之硬決策的亂序處理。當位元節點的硬決策改變時，校驗節點之所有相關層的校驗碼累加結果會被更新，因此自校驗碼計算至一有效碼字的硬決策被產生之間的退出時間可以是固定不變的。據此，可以令一階層式低密度奇偶碼之動態校驗的退出時間是最小化且固定不變的延遲時間，而且所付出的成本、晶片面積與耗電量是最少的。
根據本發明一實施例，提供一種低密度奇偶碼的解碼方法。該方法包含由一處理器接收一已解碼碼字的一已接收子向量。該方法也包含判斷該已接收子向量是否與一相應的已儲存子向量不同。當該已接收子向量與該相應的已儲存子向量不同時，將該已接收子向量儲存為該已儲存子向量，並且根據兩者的差異，更新校驗節點的一或多層的部分校驗碼，其中該一或多層具有相應於該已接收子向量的一碼矩陣之一行的多個非零元素。該方法更包含校驗該校驗節點的所有該層的該部分校驗碼。
根據本發明一實施例，提供一種低密度奇偶碼的解碼裝置。該裝置包含一記憶體單元，用於儲存一低密度奇偶碼的一已解碼碼字的複數個已儲存子向量。該裝置也包含一部分校驗碼累加器用於儲存該低密度奇偶碼之校驗節點的複數層之部分校驗碼。該裝置更包含一控制單元。該控制單元用於接收該碼字的一已接收子向量。該控制單元判斷該已接收子向量是否與該記憶體單元內儲存的相應的已儲存子向量不同。當該已接收子向量與該相應的已儲存子向量不同時，將該已接收子向量儲存為該記憶 體單元內的該已儲存子向量，並且根據兩者的差異，更新該部分校驗碼累加器之該校驗節點的一或多層的部分校驗碼，其中該一或多層具有相應於該已接收子向量的一碼矩陣之一行的多個非零元素。該裝置更包含一最終校驗碼檢查單元，用於校驗該部分校驗碼累加器之該校驗節點的所有該層的該部分校驗碼。
101‧‧‧訊息存儲單元
103‧‧‧訊息處理單元
105‧‧‧校驗單元
201‧‧‧位元節點
203‧‧‧校驗節點
502‧‧‧校驗碼累加器控制模組
504‧‧‧硬決策記憶體
506‧‧‧更新校驗碼累加器
508‧‧‧校驗碼累加器緩衝器
510‧‧‧最終校驗碼檢查模組
602‧‧‧比較器模組
604‧‧‧硬決策記憶體
606‧‧‧多工器
608‧‧‧校驗碼累加器
610‧‧‧異或閘
612‧‧‧最終校驗碼檢查模組
702‧‧‧循環移位器
704‧‧‧異或閘
706‧‧‧正反器
802‧‧‧循環移位器
804‧‧‧異或閘
806‧‧‧緩衝器
902~918‧‧‧步驟
1002‧‧‧平行校驗單元
1004‧‧‧平行校驗碼累加器
1102‧‧‧硬決策記憶體
1202~1214‧‧‧步驟
為了使得讀者對於本發明之實施例的說明有較佳的理解，在此提供以下的圖示。圖示與實施例僅提供本發明的說明，而非用於限制本發明的範圍。本領域的普通技術人員可以修改圖式，以產生其他實施例的圖式，其仍然落入本發明的範圍。
圖1為根據本發明一實施例的一階層式低密度奇偶碼解碼器之方塊示意圖。
圖2為低密度奇偶碼之二分(bipartite)圖形的一範例。
圖3為對應圖2所示之二分圖形的一4x8 H矩陣。
圖4為非正規的低密度奇偶碼之校驗矩陣的一範例。
圖5為根據本發明一實施例的具有最小退出延遲時間的一低密度奇偶碼解碼器之校驗單元的一方塊示意圖。
圖6為根據本發明一實施例的具有最小退出延遲時間的一階層式低密度奇偶碼解碼器之校驗單元的一方塊示意圖。
圖7為根據本發明一實施例的一校驗碼累加器的一方塊示意圖，該校驗碼累加器係用於執行一準循環(quasi-cyclic)低密度奇偶碼之校驗矩陣的循環元素(circulant)與硬決策的一子向量之矩陣乘法。
圖8為根據本發明一實施例的一校驗碼累加器的一方塊示意圖，該校驗碼累 加器具有的循環移位器的個數等於一校驗矩陣的行權重。
圖9為根據本發明一實施例的校驗單元之執行過程的一流程示意圖。
圖10為根據本發明一實施例的平行處理之校驗單元的一方塊示意圖，該校驗單元係用來對硬決策的多個群組進行校驗碼的累加。
圖11為根據本發明一實施例的校驗單元的一方塊示意圖，該校驗單元使用額外的硬決策記憶體來同步校驗碼的驗證與解碼資料。
圖12為根據本發明一實施例的校驗單元之校驗碼累加器控制模組的一流程示意圖，其用於同步校驗碼的驗證與解碼資料。
以下段落與其附屬的圖式用於一起描述本發明的各個實施例。請注意這些實施例僅用於描述本發明，而非用於限制本發明的範圍。
低密度奇偶碼的校驗矩陣是相當稀疏的，因為校驗矩陣當中的非零元素的數量很少，用於簡化解碼的硬體設計。低密度奇偶碼的校驗矩陣可以寫成： 其中Hi,j可以是子矩陣。如果每個子矩陣Hi,j為循環元素矩陣(circulant matrix)，且Hi,j的每一列是其上一列的循環移位時，該低密度奇偶碼為準循環低密度奇偶碼(QC-LDPC)。這種類別的低密度奇偶碼具有內在結構的正規性(regularity)，可以顯著地簡化硬體設計。此外，準循環低密度奇偶碼能夠達成非常強的錯誤更正能力，也具有足夠低的錯誤下限。假定每個循環 元素矩陣Hi,j的尺度為p×p，則校驗矩陣H為一個(m．p)×(n．p)的二元矩陣。使用此校驗矩陣所定義的低密度奇偶碼可以用(m．p)個位元來保護(n-m)．p個位元的資料，而一個碼字的長度為(n．p)個位元。其碼率為(n-m)/n。對任何一個有效的低密度奇偶碼的碼字來說，具有這樣的關係式H．=0： 其中vi為p個位元的子向量，而碼字為(n．p)個位元的區塊碼。校驗矩陣的(m．p)個列為(m．p)個校驗等式。每個校驗等式為碼字向量的硬決策的模2(modulo 2)運算之和，而該碼字向量於列向量 H i,1 H i,2...H i,n 的相應行位置中具有一個1元素。由於在校驗矩陣H的列向量中的1元素的個數不多，校驗等式的硬體設計可以簡化。以下的討論使用一個二元的矩陣H作為範例。然而，現有的技術也可以用於非二元的校驗矩陣。
圖1為根據本發明一實施例的一階層式低密度奇偶碼解碼器之方塊示意圖。階層式低密度奇偶碼解碼器將校驗矩陣的每一列視為一層。比起其他已知的解碼演算法，階層式解碼的演算法具有較快的解碼收斂速度。(也就是說，它比其他已知的演算法使用較少的疊代解碼次數就能成功地解碼。)
從傳送器或資料存儲裝置送出的以低密度奇偶碼編碼的資料被存放在一訊息存儲單元101。該訊息存儲單元101可以為一記憶體緩衝器，其用於儲存長度為(n．p)個位元的區塊碼，以便後續對此以編碼資料進行解碼。該訊息存儲單元101也可以用於儲存一個疊代的訊息更新與傳遞程 序中的「位元至校驗」(bit-to-check)與「校驗至位元」(check-to-bit)訊息。訊息處理單元103用於處理來自訊息存儲單元101內的區塊碼，並用於估測(estimate)原始碼字的碼位元(code bits)。訊息處理單元103也可以利用校驗矩陣H的校驗等式來估測在上述疊代的訊息更新與傳遞程序中的最有可能的碼字。訊息處理單元103也可以透過校驗矩陣H各層的計算進程，逐漸地產生(n．p)個位元的碼位元。當碼位元的估測值隨著疊代而修正時，硬決策也許會跟著改變。
由m×n校驗矩陣所定義的低密度奇偶碼可以被m個校驗節點與n個位元節點之間的一個二分(bipartite)圖形來表示。訊息處理單元103所執行的上述疊代的訊息更新與傳遞的低密度奇偶碼編碼程序可以使用到此二分圖形。圖2為低密度奇偶碼之二分圖形的一範例。圖3為對應圖2所示之二分圖形的一個4x8 H矩陣。請參考回圖2，該低密度奇偶碼的二分圖形顯示了在4x8校驗矩陣中，八個位元節點201與四個校驗節點203之間的連接關係。當位元節點201被頻道訊息(channel message)初始化之後，藉由訊息在位元節點201與校驗節點203之間連線的交換傳遞，以此進行的疊代計算用於估測原始碼字。當估測被精煉修正之後，便可以產生碼字的硬決策。
請參考回圖1，校驗單元105根據從訊息處理單元103所獲得的現行硬決策來進行執行時期(run-time)的校驗。校驗單元105執行一個稀疏矩陣與向量的相乘計算，以便判斷校驗等式是否成立，亦即H．=0。校驗矩陣的每一列或每一層都是一個校驗節點，對每一列中所有非零循環元素(circulant)的硬決策的異或運算結果會產生該層的校驗碼(其等於 H i,1 H i,2...H i,n ．的模2運算之和)。當所有層的校驗碼為零時，所解出的 資料是無誤的，碼字的解碼過程完畢，且上述的疊代解碼過程可以終止。在校驗碼計算中，具有硬決策之校驗矩陣H的一相應行的層的數目，就是該行的行權重(column weight)。
如果每一行的行權重wc為常數，且每一列的列權重值wr也為常數時，這種的低密度奇偶碼視為正規(regular)。圖3所示的4x8校驗矩陣H是一個正規低密度奇偶碼校驗矩陣的範例。低密度奇偶碼校驗矩陣的每一個方塊都表示一個非零循環元素。在圖3的範例中，列權重wr=4，行權重wc=2。在一個或多個實施例中，w r =w c ．(n/m)。如果校驗矩陣具有低密度的特性，但每一列或每一行中的元素1的數目不是常數，其稱為非正規的低密度奇偶碼。圖4為非正規的低密度奇偶碼之校驗矩陣的一範例。
圖5為根據本發明一實施例的具有最小退出延遲時間的一低密度奇偶碼解碼器之校驗單元的一方塊示意圖。校驗碼累加器控制模組502用來控制校驗碼計算、更新與累加的運算。校驗碼累加器控制模組502從圖1的訊息處理單元103取得輸入資料data_in。訊息處理單元103可以在校驗矩陣的各層上進行操作，以疊代地產生上述的輸入資料data_in，作為p個位元之已解碼碼字的硬決策。當該碼字為一個準循環低密度奇偶碼時，p可以是該準循環低密度奇偶碼之校驗矩陣的子矩陣的循環元素的尺寸。
校驗碼累加器控制模組502判斷在輸入資料data_in中的p個位元之已解碼碼字的硬決策是否為首次收到。當該p個位元的硬決策是首次收到時(亦即在碼字解碼過程剛開始時)，輸入資料data_in會被寫入到硬決策記憶體HD_MEM 504的適當位置，而相關於該p個位元硬決策的校驗碼會累加到一校驗碼累加器緩衝器SA_BUF 508當中。硬決策記憶體HD_MEM 504 可以具有(n．p)個欄位的深度以便容納已解碼碼字的(n．p)個硬決策。在一或多個實施例中，當輸入資料data_in表示解碼過程剛開始時所解出的首次p個碼位元時，輸入資料data_in會被寫入到硬決策記憶體HD_MEM 504的第一個位置。
此外，更新校驗碼累加器506用來計算相關於該p個碼位元的校驗矩陣該行的各層之部分校驗碼。也就是說，對於相應於該p個位元的硬決策的準循環低密度奇偶碼校驗矩陣該行的每一個非零循環元素而言，可以執行非零循環元素之子矩陣p×p與該p個位元的硬決策的一矩陣相乘運算。在上述輸入資料data_in表示解碼過程剛開始時所解出的首次p個碼位元之硬決策的實施例中，相應的行是該校驗矩陣的第一行。準循環低密度奇偶碼校驗矩陣H的第一行之行權重wc可以是3。因此，三個非零循環元素的p×p子矩陣會被乘以p個硬決策，以便為相應的三層產生部分校驗碼3×p。此部分校驗碼3×p會被存在校驗碼累加器緩衝器508當中。某一層的部分校驗碼可以藉由校驗碼累加器緩衝器508進行p個硬決策與循環元素p×p的矩陣相乘運算以及異或(XOR)運算的累加運算。在一或多個實施例中，校驗碼累加器緩衝器508可以具有(m．p)個欄位的深度以便容納(m．p)個部分校驗碼。
當校驗碼累加器控制模組502判斷在輸入資料data_in中的碼字的p個硬決策在先前已經被校驗單元所接收過，亦即輸入資料data_in是前述的疊代解碼程序的更新資料時，校驗碼累加器控制模組502會將輸入資料data_in當中更新後的p位元硬決策與儲存在硬決策記憶體504內的硬決策進行比較。當不相符時，輸入資料data_in的硬決策會寫入到硬決策記憶體504 進行更新。相應的校驗碼也會根據兩者的差異，累加至校驗碼累加器緩衝器508當中。舉例來說，當輸入資料data_in表示該碼字的前p個碼位元的新版硬決策，輸入資料data_in會和硬決策記憶體504的前p個位置的既有硬決策進行比較。當兩者不同時，表示p個已解碼的碼位元當中的一或多個碼位元已經被翻動(flipped)，輸入資料data_in將會被寫入硬決策記憶體504的前p個位置當中，用於更新該p位元的硬決策。更新校驗碼累加器506可根據已更動的硬決策，計算校驗矩陣該行所對應之各層的部分校驗碼之差異，並且根據已更新的部分校驗碼來更新校驗碼累加器緩衝器508。
當輸入資料data_in內的新的p位元硬決策和存在於硬決策記憶體504的舊的硬決策相符時，就不需要對硬決策記憶體504和校驗碼累加器緩衝器508進行更新，因為既有的p位元硬決策並沒有改變，因此不需要對校驗矩陣該行所對應之各層的部分校驗碼進行更動。由於輸入資料data_in可能表示碼字的不同p個碼位元的硬決策，不同的輸入資料data_in的部分校驗碼可能會牽涉到校驗矩陣中不同行的循環元素與p位元硬決策的乘法計算。因此，在輸入資料data_in中的不同的p位元硬決策可能會更新不同層的部分校驗碼。對於現行輸入資料data_in相關行的wc個層之部分校驗碼，會和儲存在校驗碼累加器緩衝器508當中的該些層的部分校驗碼累加起來。最終校驗碼檢查模組510將會監視校驗碼累加器緩衝器508當中的部分校驗碼。當碼字的所有(n．p)個碼位元的硬決策都至少被接收過一次之後，最終校驗碼檢查模組510會判斷存在於校驗碼累加器緩衝器508之內的(m．p)個部分校驗碼是否全為零。如果全為零，則解碼完成，且已解碼的資料從硬決策記憶體504當中輸出。校驗單元可以重置校驗碼累加器緩衝器 508，並且預備讓校驗碼累加器緩衝器508接收碼字的下一輪(n．p)個碼位元。
如先前所述，準循環低密度奇偶碼的校驗矩陣的每個子矩陣Hi,j可以是p×p循環元素的子矩陣，其中子矩陣Hi,j的每一列是前一列的循環移位。4x4循環矩陣的一個範例為：
該準循環低密度奇偶碼的校驗矩陣是個稀疏矩陣，每一個循環元素的行權重wc不是1，就是0。行權重為1的循環矩陣與碼字的一子向量的乘積運算能夠得到該子向量的循環移位。
當準循環低密度奇偶碼的校驗矩陣H是一個(t．p)×(c．p)的矩陣，且碼字向量u具有c個p位元的子向量u1到uc時，校驗等式y為校驗矩陣H與碼字向量u的乘積。 其中每個校驗節點的子向量yi可以表示為： 其中每個乘積H i,j ．u j 為碼字向量uj的一循環移位或為一個全零的向量。因此，當p位元的子向量uj的硬決策被校驗單元接收時，對於具有非零循環元 素的校驗矩陣Hi,j(1<=i<=t)的各層，會計算與累加校驗節點的子向量yi的部分校驗碼。
圖6為根據本發明一實施例的具有最小退出延遲時間的一階層式低密度奇偶碼解碼器之校驗單元的一方塊示意圖。校驗單元自圖1所示的訊息處理單元103接收已解碼碼字的p位元子向量uj的硬決策，亦即輸入資料data_in。輸入資料data_in的子向量uj可以是u1,u2,...,uC的順序，或是以其他順序來排列。一比較器模組602用來判斷在輸入資料data_in的子向量uj的硬決策是否為首次收到。若是首次收到的話，如同碼字解碼程序的開頭，輸入資料被寫入硬決策記憶體604內，相應於該子向量uj的該校驗矩陣支該行各層的部分校驗碼被寫入校驗碼累加器608內部的緩衝器SA_BUF。硬決策記憶體604可以具有(n．p)個欄位的深度以便容納已解碼碼字的(n．p)個硬決策。緩衝器SA_BUF可以具有(m．p)個欄位的深度以便容納(m．p)層的個部分校驗碼yi。
當校驗矩陣的行的循環元素與子向量uj的乘積可以被簡化為子向量uj的循環移位時，校驗碼累加器608可以被實作為一累加器與其後的一循環移位器。圖7為根據本發明一實施例的一校驗碼累加器的一方塊示意圖，該校驗碼累加器係用於執行一準循環(quasi-cyclic)低密度奇偶碼之校驗矩陣的循環元素(circulant)與硬決策的一子向量uj之矩陣乘法。一個p位元的循環移位器702用以循環的方式對子向量uj之p個位元的硬決策進行移位運算，該子向量可以表示為uj 1,uj 2,...,uj p，其移位量則由p×p循換子矩陣所決定。循環移位器702的數量可以等同於行權重wc，以便讓wc個層的校驗碼計算能夠同時進行。對於不同的子向量uj來說，相應於子向量uj之校驗矩陣 該行之各層可以是不同的。因此，對於不同的子向量uj來說，wc個移位器的輸出會和緩衝器SA_BUF內的不同部分校驗碼之集合累加在一起。在一或多個實施例中，循環移位器702的數量可以是層的數量m。在這些實施例當中，對於每一個子向量uj來說，m個p位元循環移位器當中只有wc個移位器是作用的，儘管對不同的子向量uj來說，會有不同集合的p位元循環移位器是作用的。
對某一層而言，循環移位器702的p位元輸出是儲存於緩衝器SA_BUF的相應p位元部分校驗碼的模2運算之和。模2運算可以用異或閘(XOR gate)704來實現。緩衝器SA_BUF可以用正反器(flip-flop)706來實現。可以有(m．p)個正反器來對應(m．p)個層。在一或多個實施例中，緩衝器SA_BUF可以用單埠(single-port)記憶體來實現。由於單埠記憶體一次僅能存取一個記憶體位置，對應於wc個p位元部分校驗碼yi，可以有wc個單埠記憶體。每一個單埠記憶體可以具有m個記憶體位置，而每個位置可以具有p個位元的寬度，以便儲存一個p位元長度的部分校驗碼。相對應於不同的子向量uj，wc個單埠記憶體可以用來累加不同集合的wc個部分校驗碼yi，因為其對應到校驗矩陣的不同層。這些部分校驗碼yi可能分布在所有的wc個單埠記憶體當中。為了產生部分校驗碼yi的一最終校驗碼，必須要將分布在所有的wc個單埠記憶體當中的所有部分校驗碼yi相加起來。在一或多個實施例中，為了簡化實作的複雜度，緩衝器SA_BUF可以是m組(m．p)個單埠記憶體，儘管在對應到任一個子向量uj時，僅有wc個單埠記憶體被使用。
回到圖6所示，當比較器模組602判斷在輸入資料data_in當中的子向量uj先前已經被校驗矩陣處理過的時候，比較器模組602可以比對新 的子向量uj和儲存在硬決策記憶體604的既有子向量uj。假設這些硬決策相符，則無需更新硬決策記憶體604的內容。多工器606會為校驗碼累加器608選擇輸入0，而且不會更新緩衝器SA_BUF。當這些硬決策不相符時，輸入資料data_in將會寫到硬決策記憶體604。異或閘610會產生輸入資料data_in與儲存在硬決策記憶體604的既有硬決策的差異，以便偵測輸入資料data_in的p位元之中的那些位元被翻動過。比較器模組602會通過多工器606來選擇輸入資料data_in當中那些被翻動的位元來作校驗碼的更新。校驗碼累加器608會循環移位這些輸入資料當中被翻動的位元，以便翻動這些位元所對應的校驗矩陣該行之各層的部分校驗碼。更新後的部分校驗碼會寫入校驗碼累加器608中的緩衝器SA_BUF。因此，當子向量uj中的位元節點的一或多個硬決策在疊代解碼程序中被翻動，被這些翻動過的硬決策所影響的校驗節點的部分校驗碼也會跟著翻動。
最終校驗碼檢查模組612會監視對應到所有層的緩衝器SA_BUF當中的部分校驗碼。當在u1,u2,...,uC當中的所有子向量uj都至少被接收過一次之後，最終校驗碼檢查模組612會判斷所有層的部分校驗碼是否全為零。若全為零，則會舉起一個旗標synd_ok來表示已經偵測到一個有效的碼字。這個碼字會從硬決策記憶體604輸出，而解碼程序結束。最終校驗碼檢查模組612可以利用一個具有m個輸入的反或閘(NOR)，其中m為校驗矩陣的列或層的個數。當某一準循環低密度奇偶碼有(m．p)層時，上述的m個輸入就變為(m．p)個輸入。當現行碼字的解碼程序結束後，多工器606可以選擇輸入0來重置緩衝器SA_BUF以便令下一個碼字的部分校驗碼從新開始。由於相應於被翻動碼位元的校驗矩陣之各層的部分校驗碼是同時平行 累加的，因此自有效碼字進入驗證單元到結束解碼程序的退出時間是固定不變的。
如先前所述，為了減少校驗碼累加器的尺寸，p位元循環移位器的數量可以等於校驗矩陣的行權重wc。對應至不同的子向量uj，校驗矩陣之各層具有不同的非零循環元素之子矩陣p×p。對某個子向量uj，不同層進行循環移位該子向量uj的次數也可以是不同的。一張行對層(column-to-layer)查詢表(look-up table)可以在接收到某個子向量uj的行數字之後，查詢到該行的所有非零循環元素的層數字。每個層數字可以用來查詢該層的循環移位次數。每個層數字也可以用來當成該層對應之部分校驗碼儲存於緩衝器SA_BUF內的位置。在一或多個實施例中，行對層查詢表也可以查詢到該層所對應的循環移位次數。
圖8為根據本發明一實施例的一校驗碼累加器的一方塊示意圖，該校驗碼累加器具有的循環移位器的個數等於一校驗矩陣的行權重wc。在本實施例中，行權重wc與循環移位器802的數量為3。每個循環移位器802為uj 1,uj 2,...,uj p所組成的子向量uj進行循環移位，其移位量由該層的非零循環元素之子矩陣p×p所決定。每個循環移位器802的輸出與儲存在緩衝器SA_BUF 806內的部分校驗碼會被一個異或閘804進行模2運算之和。這三層所對應的部分校驗碼會同時自緩衝器SA_BUF 806中讀出。這三層所對應的更新後的部分校驗碼也會同時寫入到緩衝器SA_BUF 806。
緩衝器SA_BUF 806可以用正反器、單埠記憶體、多埠記憶體或其他元件來實現。如果是以正反器來實現，則可以有(m．p)個正反器，代表m個層當中的每一層都具有p個校驗節點。在具有三個循環移位器802 的範例當中，可以選用(3．p)個正反器，以便在同一個時脈當中對子向量uj所對應之三層的部分校驗碼進行更新。如果是以多埠記憶體來實現，則可以用m個記憶體字節(word)來實現緩衝器SA_BUF 806，而每個記憶體字節具有p個位元。多埠記憶體可以在一個時脈當中同時存取m層的部分校驗碼。然而，當m不是個小數目，或者當(m．p)的數量相當大時，可以用單埠記憶體來實作緩衝器SA_BUF 806，此舉將更有效率。例如，可以用wc個單埠記憶體，每個單埠記憶體有m個記憶體字節(word)，而每個記憶體字節具有p個位元。針對於某個子向量uj，每個單埠記憶體可以用來更新wc層當中的一層。由於對於不同的子向量uj，該wc層當中的層數字也會有所不同，所以某一層的部分校驗碼會分布到所有的wc個單埠記憶體之中。最終校驗碼累加器可以在輸出部分校驗碼到最終校驗碼檢查模組之前，將分布到wc個單埠記憶體的同一層的部分校驗碼進行模2運算之和。
圖9為根據本發明一實施例的校驗單元之執行過程的一流程示意圖。圖5的校驗碼累加器控制模組502可用於執行該流程，以便用於控制校驗碼計算、更新與累加的運算。校驗碼累加器控制模組502可以利用硬體、在處理器上執行的軟體、或本領域普通技術人員已知的軟硬體混和的方式來實施該流程。
從步驟902開始，校驗單元自訊息處理單元103接收輸入資料data_in，亦即p位元碼字的已解碼硬決策。對於一準循環低密度奇偶碼來說，p可以是循環子矩陣的大小。在步驟904當中，校驗單元評估輸入資料data_in以及硬決策記憶體504的狀態。輸入資料data_in可以是依照u1,u2,...,uC順序接收的子向量uj。在其他實施例中，當訊息處理單元103以亂序的方 式對已接收的碼字進行疊代解碼時，可能會以亂序的方式接收子向量uj。在步驟906當中，校驗單元判斷輸入資料data_in內的子向量uj所對應的硬決策是否為首次接收，或者子向量uj為疊代解碼過程當中對於硬決策的更新版本。在步驟908中，當子向量uj為首次接收時，則子向量uj會被寫入到硬決策記憶體504，而對應到子向量uj的校驗矩陣該行之各層的部分校驗碼會被寫入到校驗碼累加器緩衝器508。由於被寫入的是該層中的首個部分校驗碼，就可以讓子向量uj與校驗矩陣該行之各層的元素進行矩陣相乘的運算結果直接存入校驗碼累加器緩衝器508，而免去再跟校驗碼累加器緩衝器508內部的資料再作模2運算之和。
在步驟910當中，當子向量uj為疊代解碼過程當中對於硬決策的更新版本時，校驗單元會判斷子向量uj是否和存在於硬決策記憶體504內的版本相符。當它們不同的時候，存在於硬決策記憶體504內的子向量uj的一或多個硬決策會被翻動。在步驟912，校驗單元會將更新的子向量uj寫入硬決策記憶體504。校驗單元也會將對應到該翻動位元的校驗矩陣該行的各層之部分校驗碼進行更新，並且存到校驗碼累加器緩衝器508內。舉例來說，對於準循環低密度奇偶碼來說，校驗單元將校驗碼累加器緩衝器508內對應到已翻動之子向量uj硬決策的部分校驗碼進行翻動。
在步驟910當中，當校驗單元判斷子向量uj和存在於硬決策記憶體504內的版本相符時，該疊代解碼程序就不會翻動該子向量uj的硬決策。存在於硬決策記憶體504內的子向量uj和存在於校驗碼累加器緩衝器508內的部分校驗碼就不需要更新。在步驟914當中，校驗單元判斷各層的部分校驗碼是否全為零。校驗單元會等到子向量uj內的u1,u2,...,uC都至少被接收 過一次之後，才會宣告所有層的校驗碼均為零。如果至少還有一個部分校驗碼不是零，則已解碼的碼字並未通過各校驗節點的檢查，校驗單元會回到步驟904，以便等待下一次疊代得到的已解碼子向量uj作為輸入資料data_in。在另一方面，當所有部分校驗碼均為零時，便偵測到一個有效的碼字。在步驟916當中，校驗單元將硬決策記憶體504的內容輸出作為已解碼的碼字，並且在步驟918終止解碼程序。在一或多個實施例中，當經過某一時間間隔，而部分校驗碼仍有非零的情況出現時，校驗單元可能會放棄解碼程序。因為部分校驗碼只有在對應到被翻動的碼位元的各層中進行更新，因此從一合格碼字進入到該校驗單元至終止解碼的退出時間相當快速。
圖10為根據本發明一實施例的平行處理之校驗單元的一方塊示意圖，該校驗單元係用來對硬決策的多個群組進行校驗碼的累加。為了增加解碼程序的吞吐量，校驗矩陣H可以被分割。平行處理化的訊息處理單元103可以利用被分割之校驗矩陣的校驗等式，在一疊代解碼程序中估測最可能的碼字。每個訊息處理單元103可以為一分割後的校驗矩陣產生一個子向量uj。因此，平行處理的訊息處理單元103可以根據校驗矩陣的分割數目來產生多個子向量uj。平行校驗單元1002可以支援從平行的訊息處理單元103所接收到的多個子向量uj。
具有三層的準循環低密度奇偶碼之校驗矩陣H可以用來解碼具有四個子向量的碼字，底下是範例之一： 對於兩個平行的訊息處理單元103與兩個平行校驗單元1002而言，上述的矩陣H可以被中間的分隔線分為左右兩個分割矩陣： 在一或多個實施例中，可以讓校驗矩陣中具有較多連接關係的行放在同一分割矩陣當中。一個訊息處理單元103與一個平行校驗單元1002可以在第一個分割矩陣上操作，以便為頭一個分割矩陣的三層累加其部分校驗碼： 第二個訊息處理單元103與第二個平行校驗單元1002可以在第一個分割矩陣上操作，以便為頭一個分割矩陣的三層累加其部分校驗碼：
自這兩個分割矩陣之三個層所對應的部分校驗碼由一個平行校驗碼累加器104所累加。當校驗矩陣是二元矩陣時，平行校驗碼累加器1004可以用異或閘來實現。
實現平行校驗單元1002的成本是隨著分割的數目而增加的緩衝器SA_BUF的容量。在前述有兩個分割的校驗矩陣H的範例中，緩衝器SA_BUF的容量需要(m．p．2)個正反器。當一個正規校驗矩陣具有行權重wc，而緩衝器SA_BUF是採用單埠記憶體來實現時，緩衝器SA_BUF的容量為(m．p．w c ．分割的數量)。平行處理的訊息處理單元可以採用亂序的方式來產生碼字子向量的硬決策。平行校驗單元1002因此就支援對接收的子向量進 行亂序處理的能力。
如前述的階層化低密度奇偶碼解碼的校驗單元，從子向量的硬決策進入硬決策記憶體到最終校驗碼檢驗輸出有校的校驗碼之間，可能具有固定的處理管線延遲時間。在此管線延遲時間當中，當解碼器判斷出有效校驗碼時，硬決策記憶體可能已經被子向量的額外硬決策更新了。舉例來說，在某些條件下，解碼器可能短暫地收斂(例如在一個時脈週期)，而在下次收斂之前可能發散一段時間(例如幾十或幾百的時脈週期)。因此，當在收斂的初始窗口內宣告一個有效校驗碼時，儲存在硬決策記憶體內的碼字已經和該有效校驗碼所對應的碼字不同了。為了避免校驗單元輸出錯誤的碼字，硬決策記憶體可能需要進一步的緩衝空間。
圖11為根據本發明一實施例的校驗單元的一方塊示意圖，該校驗單元使用額外的硬決策記憶體來同步校驗碼的驗證與解碼資料。硬決策記憶體1102內的級連(cascade chain)結構用來儲存在管線延遲時間內所接收的硬決策。硬決策記憶體1102內的欄位數量可以是管線延遲時間的時脈數量Z。當最終校驗檢查程序宣告找到有效校驗碼時，可以從硬決策記憶體1102內的最後一級取走有效碼字。因此，就算是在管線延遲時間內，有硬決策的變化，導致有效校驗碼的碼字也會被儲存起來以供後續的輸出。在一或多個實施例中，除了儲存硬決策記憶體1102的多重拷貝以外，也可以只儲存在管線延遲時間內被新接收之子向量uj所翻動的硬決策。那些在管線延遲時間之間就已經儲存的已翻動硬決策之記憶體，可以被重新利用。
由於記憶體在晶片尺寸和耗電量方面相當昂貴，一般都希望避免使用額外的記憶體來儲存硬決策。比較可以接受的折衷方案是只保留 單一份硬決策記憶體的拷貝，而只讓解碼器在少數情況下錯過收斂的短暫窗口。為了實現這種方案，可能要付出晶片尺寸與耗電量的代價來修改校驗單元的校驗碼累加器控制模組502，使得校驗單元能夠在偵測到有效校驗碼的管線延遲時間之後，還能夠輸出有效的碼字。
圖12為根據本發明一實施例的校驗單元之校驗碼累加器控制模組502的一流程示意圖，其用於同步校驗碼的驗證與解碼資料。流程開始於步驟1202，假定校驗單元已經從訊息處理單元103接收碼字的全部(n．p)碼位元至少一次。在步驟1204，校驗碼累加器控制模組502將一校驗成功之計數器(syn_ok_cnt)重置為零。在步驟1206，校驗碼累加器控制模組502在接收到額外的子向量uj之硬決策後，判斷硬決策記憶體504的內容是否被改變。由於疊代解碼程序翻動了既有子向量uj之至少一個硬決策而導致硬決策記憶體504的內容改變時，校驗碼累加器控制模組502將控制流程回到步驟1204以便重置該校驗成功之計數器。
另一方面，若硬決策記憶體504的內容沒被改變，校驗碼累加器控制模組502將在步驟1208令該校驗成功之計數器內容加一。舉例而言，當新的子向量uj和存在於硬決策記憶體504的既有子向量uj相符時，意味著疊代解碼程序並未翻動任何子向量uj的硬決策。硬決策記憶體504的既有子向量uj並未更動，所以硬決策記憶體504的內容不變。校驗碼累加器控制模組502令該校驗成功之計數器內容加一，用於表示硬決策記憶體504的內容在一個時脈週期內不變。於步驟1210，當最終校驗檢查模組510宣告找到一有效校驗碼時，校驗碼累加器控制模組502判斷該校驗成功之計數器內容是否等於管線延遲時間。當硬決策記憶體504的內容在管線延遲時間當中都 沒有變化的情況時，也就是校驗單元於管線延遲時間內根據硬決策記憶體504的碼字來產生最終校驗碼檢查的結果。假設上述的判斷結果為真，於步驟1212當中，校驗單元將硬決策記憶體504的碼字輸出，而解碼程序於步驟1214終止。
反之，當該校驗成功之計數器內容不等於管線延遲時間，或者沒有任何有效校驗碼時，校驗碼累加器控制模組502將流程回到步驟1206，以便接收額外的子向量的硬決策。舉例來說，當收斂所發生的時間要短於管線延遲時間，硬決策記憶體504的內容會在管線延遲時間內發生變化。該校驗成功之計數器內容會小於管線延遲時間，而步驟1210的判斷結果為否。據此，校驗單元並不會輸出硬決策記憶體504內的錯誤碼字。圖12的流程確保了輸出的碼字都是有效的，而付出的代價是錯過短暫的收斂窗口，據而輕微地增加解碼時間。
上述的解釋與描述係用於描繪本發明的一或多個實施例，而非用於限制本發明的範圍。儘管本發明已經於上述實施例中詳細解說，但本領域的普通技藝人員可以通過對已揭露實施例的修改或等同元件的替換來獲得本發明的其他實施例。任何修改、等同元件的替換與改善，而不偏離本發明的精神與發明原理者都屬於本發明的範圍。以下就是本發明所宣告的範圍。
502‧‧‧校驗碼累加器控制模組
504‧‧‧硬決策記憶體
506‧‧‧更新校驗碼累加器
508‧‧‧校驗碼累加器緩衝器
510‧‧‧最終校驗碼檢查模組

Claims (20)

  1. 一種低密度奇偶碼的解碼方法，包含：由一處理器接收一已解碼碼字的一已接收子向量；判斷該已接收子向量是否與一相應的已儲存子向量不同；當該已接收子向量與該相應的已儲存子向量不同時，將該已接收子向量儲存為該已儲存子向量，並且根據兩者的差異，更新校驗節點的一或多層的部分校驗碼，其中該一或多層具有相應於該已接收子向量的一碼矩陣之一行的多個非零元素；以及校驗該校驗節點的所有該層的該部分校驗碼。
  2. 如申請專利範圍第1項的解碼方法，更包含：若沒有該已儲存子向量時，將該已接收子向量儲存為該已儲存子向量，並且更新該校驗節點之一或多層的該部分校驗碼，其中該一或多層具有相應於該已接收子向量的一碼矩陣之一行的多個非零元素。
  3. 如申請專利範圍第2項的解碼方法，更包含：重複該接收步驟、該判斷步驟與該儲存步驟，以及更新該碼字的複數個子向量。
  4. 如申請專利範圍第3項的解碼方法，其中上述之校驗該部分校驗碼的步驟更包含：確定該碼字的每一個子向量均有一個已儲存子向量；以及 當該校驗節點的所有層對應的該部分校驗碼均為零時，輸出所有的該已儲存子向量作為有效解碼的該碼字。
  5. 如申請專利範圍第3項的解碼方法，其中上述之校驗該部分校驗碼的步驟更包含：確定該碼字的每一個子向量均有一個已儲存子向量；確定全部的該已儲存子向量在一最小時間周期內沒有改變；當該校驗節點的所有層對應的該部分校驗碼均為零時，輸出所有的該已儲存子向量作為一有效解碼的碼字。
  6. 如申請專利範圍第1項的解碼方法，其中上述之根據已接收子向量與已儲存子向量的差異之該更新步驟，更包含：偵測已接收子向量與已儲存子向量所差異的一翻動位元；以及翻動該校驗節點的一或多層的該部分校驗碼，其中該一或多層具有相應於該翻動位元的該碼矩陣之一行的多個非零元素，其中上述之儲存該已儲存子向量的步驟包含儲存該翻動位元以便更新該已儲存子向量的一相應位元。
  7. 如申請專利範圍第6項的解碼方法，其中上述之儲存該已儲存子向量的步驟更包含：在該校驗該校驗節點的所有該層的該部分校驗碼之步驟完成之前，儲存該已儲存子向量，以避免該已儲存子向量被該已接收子向量的該翻動位元所複寫。
  8. 如申請專利範圍第1項的解碼方法，其中上述之低密度奇偶碼為一準循環低密度奇偶碼，其包含尺度為p×p的循環子矩陣，其中該碼字的該已接收子向量具有p個硬決策。
  9. 如申請專利範圍第1項的解碼方法，更包含：由該處理器平行地接收該已解碼碼字的複數個已接收子向量；平行地對該複數個已接收子向量進行該判斷步驟、該儲存步驟與該更新步驟，以便為該校驗節點的該一或多層平行地產生複數個部分校驗碼；以及在該校驗該校驗節點的所有該層的該部分校驗碼之步驟前，為該校驗節點的該一或多層中的每一層累加該複數個部分校驗碼。
  10. 一種裝置，包含：一記憶體單元，用於儲存一低密度奇偶碼的一已解碼碼字的複數個已儲存子向量；一部分校驗碼累加器用於儲存該低密度奇偶碼之校驗節點的複數層之部分校驗碼；一控制單元，用於執行下列步驟：接收該碼字的一已接收子向量；判斷該已接收子向量是否與該記憶體單元內儲存的相應的已儲存子向量不同；以及 當該已接收子向量與該相應的已儲存子向量不同時，將該已接收子向量儲存為該記憶體單元內的該已儲存子向量，並且根據兩者的差異，更新該部分校驗碼累加器之該校驗節點的一或多層的部分校驗碼，其中該一或多層具有相應於該已接收子向量的一碼矩陣之一行的多個非零元素；以及一最終校驗碼檢查單元，用於校驗該部分校驗碼累加器之該校驗節點的所有該層的該部分校驗碼。
  11. 如申請專利範圍第10項的裝置，其中上述之控制單元在沒有該已儲存子向量時，更用於：將該已接收子向量儲存為該記憶體單元內的該已儲存子向量；以及更新該部分校驗碼累加器之該校驗節點之一或多層的該部分校驗碼，其中該一或多層具有相應於該已接收子向量的一碼矩陣之一行的多個非零元素。
  12. 如申請專利範圍第11項的裝置，其中上述之控制單元更用於：連續地接收複數個已接收子向量；判斷每一個該已接收子向量是否與該記憶體單元內儲存的相應的已儲存子向量不同；以及當每一個該已接收子向量與該相應的已儲存子向量不同時，將該已接收子向量儲存為該已儲存子向量，並且根據兩者的差異，更新該部分校驗碼累加器之該校驗節點的一或多層的部分校驗碼，其中該一或多層具有相應 於該已接收子向量的一碼矩陣之一行的多個非零元素。
  13. 如申請專利範圍第12項的裝置，其中上述之最終校驗碼檢查單元更用於：確定該記憶體單元內的該碼字的每一個子向量均有一個已儲存子向量；以及當該部分校驗碼累加器之該校驗節點的所有層對應的該部分校驗碼均為零時，輸出所有的該已儲存子向量作為有效解碼的該碼字。
  14. 如申請專利範圍第12項的裝置，其中上述之最終校驗碼檢查單元更用於：確定該記憶體單元內的該碼字的每一個子向量均有一個已儲存子向量；確定全部的該已儲存子向量在一最小時間周期內沒有改變；以及當該部分校驗碼累加器之該校驗節點的所有層對應的該部分校驗碼均為零時，輸出所有的該已儲存子向量作為有效解碼的該碼字。
  15. 如申請專利範圍第10項的裝置，其中上述之控制單元更用於：偵測已接收子向量與已儲存子向量所差異的一翻動位元；以及翻動該部分校驗碼累加器之校驗節點的一或多層的該部分校驗碼，其中該一或多層具有相應於該翻動位元的該碼矩陣之一行的多個非零元素，其中上述之儲存該已儲存子向量的步驟包含儲存該翻動位元以便更新在該記憶體單元內之該已儲存子向量的一相應位元。
  16. 如申請專利範圍第15項的裝置，其中上述之記憶體單元更包含一緩衝器，用於在該校驗該校驗節點的所有該層的該部分校驗碼之步驟完成之前，在該緩衝器內儲存該已儲存子向量，以避免該已儲存子向量被該已接收子向量的該翻動位元所複寫。
  17. 如申請專利範圍第10項的裝置，其中上述之低密度奇偶碼為一準循環低密度奇偶碼，其包含尺度為p×p的循環子矩陣，其中該碼字的該已接收子向量具有p個硬決策。
  18. 如申請專利範圍第17項的裝置，其中上述之部分校驗碼累加器更包含：一或多個循環移位器，用於根據相應於該已接收子向量的該碼矩陣之該行的一或多個循環子矩陣，對該已接收子向量進行循環移位；以及複數個異或閘，用於累加該一或多個循環移位器的輸出。
  19. 如申請專利範圍第10項的裝置，其中上述之控制單元更用於：平行地接收該已解碼碼字的複數個已接收子向量；判斷每一個該已接收子向量是否與該記憶體單元內儲存的相應的已儲存子向量不同；以及當每一個該已接收子向量與該相應的已儲存子向量不同時，將該已接收子向量儲存為該記憶體單元內的該已儲存子向量，並且根據兩者的差異，平行地更新該部分校驗碼累加器之該校驗節點的一或多層的部分校驗碼， 其中該一或多層具有相應於該已接收子向量的一碼矩陣之一行的多個非零元素；以及將該部分校驗碼累加器之該校驗節點的一或多層的該複數個部分校驗碼累加起來。
  20. 如申請專利範圍第10項的裝置，其中上述之部分校驗碼累加器更包含：複數個記憶體，其數量等於該碼矩陣的最大行權重，其中該記憶體用於平行地累加該校驗節點的所有該層之該部分校驗碼。
TW105114536A 2015-05-11 2016-05-11 階層式低密度奇偶碼解碼器的早期退出系統及方法 TW201703442A (zh)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US14/708,507 US9692450B2 (en) 2015-05-11 2015-05-11 Systems and methods for early exit of layered LDPC decoder

Publications (1)

Publication Number Publication Date
TW201703442A true TW201703442A (zh) 2017-01-16

Family

ID=57277408

Family Applications (1)

Application Number Title Priority Date Filing Date
TW105114536A TW201703442A (zh) 2015-05-11 2016-05-11 階層式低密度奇偶碼解碼器的早期退出系統及方法

Country Status (3)

Country Link
US (1) US9692450B2 (zh)
CN (1) CN106160752B (zh)
TW (1) TW201703442A (zh)

Families Citing this family (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102254102B1 (ko) * 2015-01-23 2021-05-20 삼성전자주식회사 메모리 시스템 및 메모리 시스템의 동작 방법
CN108370253B (zh) * 2015-12-24 2022-05-03 英特尔公司 用于低密度奇偶校验解码的混合式调度和基于锁存器的流水线
US20170222659A1 (en) * 2016-02-02 2017-08-03 Silicon Motion Inc. Power improvement for ldpc
KR20170101368A (ko) * 2016-02-26 2017-09-06 에스케이하이닉스 주식회사 에러 정정 회로 및 에러 정정 방법
US10116333B2 (en) * 2016-07-29 2018-10-30 Sandisk Technologies Llc Decoder with parallel decoding paths
TWI631830B (zh) * 2016-12-30 2018-08-01 慧榮科技股份有限公司 解碼方法與相關解碼裝置
EP3373488B1 (en) 2017-03-07 2020-05-06 Commissariat à l'Energie Atomique et aux Energies Alternatives Stopping criterion for decoding quasi-cyclic ldpc codes
US12210958B2 (en) 2017-09-21 2025-01-28 Qualcomm Incorporated Compression of sparse deep convolutional network weights
CN111052622B (zh) * 2017-10-02 2022-06-17 联想（新加坡）私人有限公司 使用确定的压缩矩阵来形成复合波束的集合的方法和装置
US10523236B2 (en) * 2017-11-21 2019-12-31 Silicon Motion, Inc. Method employed in LDPC decoder and the decoder
KR102475279B1 (ko) * 2017-12-18 2022-12-07 삼성전자주식회사 컨볼루션 타입의 저밀도 패리티 체크 코드를 이용하여 인코딩 및 디코딩을 수행하는 메모리 컨트롤러, 이를 포함하는 메모리 시스템 및 이의 동작 방법
CN109936378B (zh) * 2017-12-19 2022-08-26 北京紫光展锐通信技术有限公司 Ldpc的乱序译码实现方法及装置
CN108566211B (zh) * 2018-03-27 2021-11-02 西安电子科技大学 基于H矩阵层处理顺序动态变化的layered LDPC译码方法
CN108649963B (zh) * 2018-07-09 2024-07-16 卓荣集成电路科技有限公司 Qc-ldpc解码器、分层解码方法、存储设备及通信模组
KR102678314B1 (ko) 2018-08-03 2024-06-25 삼성전자주식회사 유저 데이터에 대한 에러 정정을 수행하는 에러 정정 회로 및 이를이용한 에러 정정 방법
CN111142058B (zh) * 2020-01-02 2022-05-17 联芸科技（杭州）有限公司 电阻检测装置及方法
CN113691263B (zh) * 2021-08-19 2024-02-27 Oppo广东移动通信有限公司 多比特并行校验方法及装置、存储介质及Turbo译码器
US11863201B2 (en) * 2022-04-01 2024-01-02 Qualcomm Incorporated Correlation-based hardware sequence for layered decoding
TWI858704B (zh) * 2023-05-12 2024-10-11 睿寬智能科技有限公司 準循環低密度奇偶校驗碼的解碼器
TWI863310B (zh) * 2023-05-26 2024-11-21 睿寬智能科技有限公司 準循環低密度奇偶校驗碼的快速解碼器

Family Cites Families (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1182657C (zh) * 2002-12-20 2004-12-29 清华大学 用于降低乘积码译码所需存储量和复杂度的方法
US7296216B2 (en) 2003-01-23 2007-11-13 Broadcom Corporation Stopping and/or reducing oscillations in low density parity check (LDPC) decoding
US7760880B2 (en) 2004-10-13 2010-07-20 Viasat, Inc. Decoder architecture system and method
WO2006068435A2 (en) 2004-12-22 2006-06-29 Lg Electronics Inc. Apparatus and method for decoding using channel code
JP2008544721A (ja) 2005-06-27 2008-12-04 トムソン ライセンシング 反復デコーダの電力削減のための方法及び装置
US8234537B2 (en) 2006-03-31 2012-07-31 Intel Corporation Layered decoder and method for performing layered decoding
US8418023B2 (en) 2007-05-01 2013-04-09 The Texas A&M University System Low density parity check decoder for irregular LDPC codes
US8291285B1 (en) 2008-09-18 2012-10-16 Marvell International Ltd. Circulant processing scheduler for layered LDPC decoder
US8751912B1 (en) * 2010-01-12 2014-06-10 Marvell International Ltd. Layered low density parity check decoder
US8756479B2 (en) * 2011-01-14 2014-06-17 Marvell World Trade Ltd. LDPC multi-decoder architectures
CN102684709B (zh) * 2012-05-10 2014-10-15 天津大学 一种译码方法及其译码装置
US9136877B1 (en) * 2013-03-15 2015-09-15 Sandisk Enterprise Ip Llc Syndrome layered decoding for LDPC codes
TWI540844B (zh) * 2013-03-27 2016-07-01 國立清華大學 雙重準循環低密度同位校驗碼
CN103208995B (zh) * 2013-03-27 2016-02-24 东南大学 一种低密度奇偶校验码译码的提前终止方法
US20150106666A1 (en) 2013-10-10 2015-04-16 Lsi Corporation Speculative Bit Error Rate Calculator

Also Published As

Publication number Publication date
CN106160752B (zh) 2019-11-08
US9692450B2 (en) 2017-06-27
CN106160752A (zh) 2016-11-23
US20160336964A1 (en) 2016-11-17

Similar Documents

Publication Publication Date Title
TW201703442A (zh) 階層式低密度奇偶碼解碼器的早期退出系統及方法
US9544090B2 (en) Hard input low density parity check decoder
US8996972B1 (en) Low-density parity-check decoder
US10511326B2 (en) Systems and methods for decoding error correcting codes
US9391639B2 (en) LDPC multi-decoder architectures
KR101854954B1 (ko) 치환 소행렬의 합을 사용하는 체크섬
KR101405962B1 (ko) Ｌｄｐｃ 코드를 이용한 복호화 방법
US11115051B2 (en) Systems and methods for decoding error correcting codes
JP5199463B2 (ja) ターボｌｄｐｃ復号
US8656249B2 (en) Multi-level LDPC layer decoder
EP1622276A2 (en) Layered decoding of low density parity check (LDPC) codes
CN109586731B (zh) 用于解码纠错码的系统和方法
US9195536B2 (en) Error correction decoder and error correction decoding method
US9490844B1 (en) Syndrome computation in a layered low density parity check decoder
WO2011109084A1 (en) Quasi-cyclic ldpc encoding and decoding for non-integer multiples of circulant size
CN113783576A (zh) 用于从循环置换矩阵的集群构建的准循环低密度奇偶校验码的垂直分层解码的方法及设备
CN115296675B (zh) 用于ldpc码的解码的提前收敛
US9015548B2 (en) Error detection correction method and semiconductor memory apparatus
CN100544212C (zh) 高速的减少存储需求的低密度校验码解码器
JP6567238B1 (ja) 誤り訂正復号装置および誤り訂正復号方法
Benhayoun et al. Embedded Parallel Implementation of LDPC Decoder for Ultra‐Reliable Low‐Latency Communications
KR101226439B1 (ko) 리드-솔로몬 디코더, 이를 포함하는 메모리 시스템 및 디코딩 방법
KR20140034579A (ko) 채널 복호화 장치