低密度校驗碼（LDPC）
2.3.4 準循環 LDPC 碼的多碼長設計
|2.4 QC-LDPC碼的譯碼結構|
文獻[31] 給出了LDPC譯碼器中的總體架構， 如圖2-26至圖2-28所示。核心處理單元是校驗節點單元(CNU) 和變量節點單元(VNU) 。其中， CNU主要進行校驗節點的更新， 主要的譯碼算法， 比如前面介紹過的Min-Sum算法都是通過CNU的邏輯電路實作。VNU主要進行變量節點的更新， VNU可以通過更新存儲在Memory中的軟資訊來實作其功能， 是以在一些譯碼器的架構圖中， VNU也并不以具體的子產品形式出現。在譯碼的過程中， 軟資訊(Soft Information) 在CNU和VNU之間以并行度為P的水準傳播。
LDPC 譯 碼 的 調 度 方 式 大 體 有 兩 種： 泛 濫 式（Flooding） 和 分 層 式 （Layered）。泛濫式的特點是在每一次譯碼疊代，先計算從變量節點到校驗節 點的所有軟資訊，然後計算從校驗節點到變量節點的所有軟資訊。泛濫式的調 度比較适合下面介紹的全并行結構，通常用于計算機模拟仿真。 分層式的特點是在計算每層的軟資訊時，會更新此次疊代中的相關的節點 資訊，用于下一層的軟資訊計算。分層式的排程适合下面介紹的行并行和塊并 行結構，可以降低所需的疊代次數。相比泛濫式一般能節省一半的疊代次數。
2.4.1 全并行譯碼（Full-parallel）
LDPC 譯碼器中的每個基礎執行單元負責完成 LDPC 碼中的校驗方程基本 運作的各個過程，包括資料讀取、變量更新、校驗更新、資料寫入。LDPC 譯 碼中的 BP 算法本質上是并行的。這也是 LDPC 在高碼率、大碼塊長度時相對 Turbo 碼的優勢。它能夠利用并行運算的特點，提高鍊路的資料吞吐。BP 算 法十分适合大帶寬、高信噪比的傳輸環境。是以，如果譯碼器的硬體複雜度不 是瓶頸，即基礎執行單元的數量沒有嚴格的限制，那麼則可采用全并行譯碼器 結構。圖 2-29 是全并行 LDPC 譯碼器的 Tannar 圖中資訊更新流動示意圖， 該圖的上面部分說明所有變量節點同時更新并提供給所有校驗節點，該圖的下 面部分說明所有校驗節點同時更新并提供給所有變量節點。圖 2-26 畫出了全 并行譯碼結構的硬體結構。可以看出，其所需的硬體資源非常多。
全并行譯碼，意味着 LDPC 碼中的所有奇偶校驗方程（基礎執行單元）同時運作，如基礎校驗矩陣的母碼為 1/3 碼率，基礎矩陣是 mb = 16 行，nb = 24 列， 提升值 z = 500，則一共有 16×500 = 8000 個校驗方程，即在全并行譯碼中有 8000 個基礎執行單元同時運作，運作完算 1 次疊代。設最大疊代次數為 ITER， 則譯碼器總共需要時鐘數目為 Clk = a×ITER。其中，a 為一次疊代所需要的時鐘 數目，那麼吞吐量計算可以表示為式（2-52）。
其中，f 是工作頻率，K 是編碼塊大小，K = 4000。設 f = 200 MHz，最 大疊代次數為 20 次，基礎執行單元需要時鐘數為 8，則吞吐量等于 5 Gbit/s。 但是，在全并行譯碼情況下，需要 8000 個基礎執行單元同時運作，那麼需要 的硬體資源是非常高的。是以全并行的 LDPC 譯碼結構在工程實際中很少應用。
以上所述的全并行譯碼結構都是基于必須為所有校驗節點提供硬體資源， 這樣不僅僅帶來硬體資源的大量浪費，而且特别是在支援任意碼長和碼率的 LDPC 譯碼時該情況更為嚴重。其實可以采用部分并行（類似下面所介紹的分 層譯碼結構，将所有奇偶校驗方程分為多個分組分别進行更新）執行方式實作， 其中各個校驗節點更新可以采用相同的校驗節點單元以及流水線（Pipeline）方 式實作，可以大大節省資源，并提高吞吐量，由于其還是全并行譯碼思想，所 以疊代次數并不能降低。
2.4.2 行并行譯碼（Row-parallel）
行并行譯碼經常與分層式的譯碼排程結合，它和全并行譯碼的差別在于在 疊代中，将校驗節點分成若幹組，在每輪疊代中首先更新校驗矩陣中的一組校 驗節點資訊，接着更新所有和該組校驗節點相鄰的變量節點，然後再更新下一 組校驗節點資訊和與這組校驗節點相鄰的變量節點資訊，直至最後一組。如圖 2-30 和圖 2-31 所示，在譯碼過程中，前面已經更新的變量節點資訊能應用到 本輪疊代後面校驗節點資訊的更新過程中，使疊代收斂速度加快，一般情況下， 行并行譯碼和比全并行譯碼收斂更快，可以節約疊代次數以提高吞吐量，在較 好的情況下可以節約一半左右的疊代次數。
行并行譯碼器的結構如圖 2-32 所示，其中包括存儲器（Memory）、路 由網絡（Route Network）、移位網絡（Shifting Network）、校驗節點單元 （CNU）、控制器（Controller）等。校驗節點單元的輸入管腳數等于基礎校驗 矩陣最大的行重，存儲分片（Memory Slice）的數目近似等于基礎矩陣的核矩 陣的列數。對于 5G-NR eMBB 的 LDPC 矩陣，其存儲分片的數目等于基礎矩 陣—Kernel 矩陣的列數加一。
以 Scale Min-Sum 譯碼算法為例，校驗節點單元包含比較（Comparison）、 選擇（Selection）、加（Addition）、縮放（Scaling）等基本單元，适合行并行 譯碼的校驗節點的内部結構如圖 2-33 所示。其中，校驗節點單元的輸入管腳 數目至少要等于基礎校驗矩陣最大的行重。從圖中可以看出，其複雜度與校驗 節點單元的輸入管腳數目關系很大。校驗節點單元的輸入管腳數越多，複雜度 就越高。
如圖 2-34 所示，路由網絡的功能是将存儲分片中經過循環移位後的資料 輸入到校驗節點單元的管腳，校驗節點單元通過讀取不同組的管腳上的資料來 實作分層譯碼的功能。這種連接配接的目的是實作基礎矩陣中變量節點和校驗節點之間的連接配接。采用路由網絡的優點是可以減少校驗節點單元的輸入管腳的數量， 但是當基礎矩陣比較大時，路由網絡的複雜度也會急劇增加，尤其單個譯碼器 要支援多個基礎矩陣，其路由網絡十分複雜。
圖 2-34 中的路由網絡支援兩個基礎矩陣 Kb 分别為 32 和 10。
如果基礎矩陣比較小，則路由網絡的複雜度可以大大降低，甚至可以将每 個存儲分片和校驗節點單元的管腳數進行一一對應的連接配接，如圖 2-35 所示。 這裡的基礎校驗矩陣的 Kb 為 16。
移位網絡在前面已經提及，常用 Banyan 網絡，主要作用是針對不同的提 升值，支援并行處理，複雜度也與基礎矩陣的大小有關，當基礎矩陣的系統列 數目越大，需要的移位網絡的數量就越多。
存儲器包括對數似然比（LLR）的存儲和校驗節點的存儲，存儲器的容量等 于最大的編碼後的長度。其複雜度還與存儲分片的數量有關。當資訊塊長度越大， 碼率越小時，所需的存儲器容量也越大。在相同的資訊長度下，存儲分片的數量 越多，複雜度越高。
2.4.3 塊并行譯碼（Block-parallel）
基礎矩陣每一行或者層内還可以分為多個循環（塊）的執行，如圖 2-36 所示，包含存儲器（Memory）、移位網絡（Shift Network），校驗節點單元 （CNU）、控制器（Controller）以及之間的連線。塊并行譯碼的并行度小于行 并行。其吞吐量遜于行并行。由于基礎矩陣中的每 個基礎執行單元的存儲是不沖突的，是以每個基礎 執行單元可以采用并行方式進行。
相比行并行，塊并行中的移位網絡的數目要少 得多，一般隻要兩個移位網絡就可以了，一個負責 從 LLR 存儲器中讀取，另一個負責向 LLR 存儲器 寫入。是以，移位網絡的複雜度與存儲器的數目和 基礎矩陣的行重基本無關。但是需要指出的是，如 果需要讓塊并行譯碼與行并行譯碼的吞吐量相近， 則塊并行的最大并行度會成倍增加，這會增加移位 網絡的總體複雜度。
為了提高塊并行的處理速度，也可以采用多個塊同時處理，這時增加路由 網絡和更多的移位網絡，隻不過當同時處理的塊的數量比較少時，路由網絡和 移位網絡相比于行并行時可以簡單一些。兩個塊同時處理的路由網絡和移位網絡如圖 2-37 所示。
塊并行的校驗節點單元的内部結構如圖 2-38 所示，包括 3 個 2 選 1 的運算 線路和 2 個比較的運算線路。相比行并行，塊并行的校驗節點存儲器的複雜度較 低，對存儲器分片的讀寫過程更類似串行處理。此時校驗節點存儲器的複雜度與 存儲器條的個數或者基礎矩陣的行重沒有關系，隻與 CNU 最大支援的并行度有關。
當兩個塊同時處理時，校驗節點單元變為如圖 2-39 所示的形式。
與行并行的情形相同，塊并行的存儲器的容量取決于最大的編碼塊的長度。