ldpc碼bp演算法

A. 請問LDPC解碼中的BP和BF演算法有什麼區別，謝謝

BP是belief-propagation，指得是置信傳播法。
BF是Bit-Flipping，指得是比特翻轉法。
兩者的思想都是通過信息傳遞迭代判斷最可能錯誤的點。但BP在計算中使用了先驗概率和後驗概率作為判斷的依據。而BF則是根據傳遞的信息評估某位是1或0的可能性，不同值超過50%則1變0，0變1。
其實，可以把BF看成一種特殊條件下的BP。

B. LDPC碼的簡介

任何一個(n，k)分組碼，如果其信息元與監督元之間的關系是線性的，即能用一個線性方程來描述的，就稱為線性分組碼。
低密度奇偶校驗碼圖（LDPC碼）本質上是一種線形分組碼，它通過一個生成矩陣G將信息序列映射成發送序列，也就是碼字序列。對於生成矩陣G，完全等效地存在一個奇偶校驗矩陣H，所有的碼字序列C構成了H的零空間 (null space)，即。
LDPC模擬系統圖DLPC 碼的奇偶校驗矩陣H是一個稀疏矩陣，相對於行與列的長度，校驗矩陣每行、列中非零元素的數目(我們習慣稱作行重、列重)非常小，這也是LDPC碼之所以稱為低密度碼的原因。由於校驗矩陣H的稀疏性以及構造時所使用的不同規則，使得不同LDPC碼的編碼二分圖(Taner圖)具有不同的閉合環路分布。而二分圖中閉合環路是影響LDPC碼性能的重要因素，它使得LDPC碼在類似可信度傳播(Belief ProPagation)演算法的一類迭代解碼演算法下，表現出完全不同的解碼性能。
當H的行重和列重保持不變或盡可能的保持均勻時，我們稱這樣的LDPC碼為正則LDPC碼，反之如果列、行重變化差異較大時，稱為非正則的LDPc碼。研究結果表明正確設計的非正則LDPC碼的性能要優於正則LDPC。根據校驗矩陣H中的元素是屬於GF(2)還是GF(q)(q=2p)，我們還可以將LDPC碼分為二元域或多元域的LDPC碼。研究表明多元域LDPC碼的性能要比二元域的好。

C. LDPC碼的發展現狀

LDPC碼
LDPC ( Low-density Parity-check，低密度奇偶校驗）碼是由 Gallager 在1963 年提出的一類具有稀疏校驗矩陣的線性分組碼 (linear block codes)，然而在接下來的 30 年來由於計算能力的不足，它一直被人們忽視。1996年，D MacKay、M Neal 等人對它重新進行了研究，發現 LDPC 碼具有逼近香農限的優異性能。並且具有解碼復雜度低、可並行解碼以及解碼錯誤的可檢測性等特點，從而成為了信道編碼理論新的研究熱點。
Mckay ，Luby 提出的非正則 LDPC 碼將 LDPC 碼的概念推廣。非正則LDPC碼 的性能不僅優於正則 LDPC 碼，甚至還優於 Turbo 碼的性能，是目前己知的最接近香農限的碼。
Richardson 和 Urbank 也為 LDPC 碼的發展做出了巨大的貢獻。首先，他們提出了一種新的編碼演算法，在很大程度上減輕了隨機構造的 LDPC 碼在編碼上的巨大運算量需求和存儲量需求。其次，他們發明了密度演進理論，能夠有效的分析出一大類 LDPC 解碼演算法的解碼門限。模擬結果表明，這是一個緊致的解碼門限。最後，密度演進理論還可以用於指導非正則 LDPC碼 的設計，以獲得盡可能優秀的性能。
LDPC水印系統結構框圖LDPC碼具有巨大的應用潛力，將在深空通信、光纖通信、衛星數字視頻、數字水印、磁/光/全息存儲、移動和固定無線通信、電纜調制/解調器和數字用戶線(DSL)中得到廣泛應用。
M.Chiain 等對 LDPC 碼用於有記憶衰落信道時的性能進行了評估。B.Myher 提出一種速率自適應 LDPC 編碼調制的方案用於慢變化平坦衰落信道，經推廣還可用於 FEC-ARQ 系統。
Flarino 開發的集成了 V-DLPC 的 flash-OFDM 移動無線晶元組己可用於基於 IP 的移動寬頻網。VOCAL Technologies.Ltd 提出了一種用於 WLAN 的LDPC/Turbo 不對稱解決方案，即下行鏈路採用 LDPC 碼，上行鏈路採用 Turbo碼。研究表明採用該方案後用於IEEE802.11 a/b/gWLAN移動終端的電池壽命可延長至原來的4倍。
工業界也己經有 LDPC 編譯碼晶元問世。其中，處於領先地位的 Flarion公司 推出的基於 ASIC 的 Vector-LDPC 解決方案使用了約 260 萬門，最高可以支持 50000的碼長，0.9 的碼率，最大迭代次數為 10，解碼器可以達到 10Gbps 的吞吐量，其性能己經非常接近香農限，可以滿足目前大多數通信業務的需求。AHA 公司、Digital Fountain公司也都推出了自己的編解碼解決方案。

D. 機情觀察室：華為5G polar Code是什麼

【IT168 評測】11月18日，在互聯網上當所有人都被林丹出軌刷屏的時候，可能許多人並沒有注意，在大洋彼岸的拉斯維加斯舉行的3GPP RAN1#87次會議上，正式宣布由華為主推的Polar碼成為5G eMBB場景下控制信道的短碼編碼方案。而隨後在互聯網上，一些諸如「碾壓高通」「稱霸5G」類似的報道連篇累牘，點燃許多吃瓜群眾愛國之情，紛紛在朋友圈、微博上奔走相告好不歡喜。我們今天的機情觀察室，就來聊聊Polar碼是個什麼東西，所謂的華為「拿下」5G又是怎麼回事？

LDPC碼和Polar碼究竟是什麼?

首先，無論是LDPC還是polar，都是一種信道編碼，並且均為第一次入選3GPP的標准。信道編碼是通訊行業中的一個名詞，廣泛用作表示檢測及糾正編碼錯誤的一種術語，常常用於通信及存儲領域，是通信系統的核心技術之一。簡單的說就是信道編碼就是在傳輸過程中保護數據以及在出錯時恢復數據用的一種數字調制方式。

▲信道編碼相當於數據的保護盒

因為在無線傳輸過程中，我們會將比較復雜的模擬信號(含有復雜的數據信息)轉化成簡單的數字信號(由0和1組成)，這樣雖然便於傳輸但是會影響還原數據的准確性。因為無線數據傳輸過程中，往往會出現摻雜噪音或者丟失數據的情況。信道編碼則是將這些數字信號進行分組，接收存儲之後再重復接受並與之前存儲的數據進行對比，如果相同分組的數據相同則判斷為正確。比如接受存儲的數據為1，經過3組對比後該數據全部為1，則判斷正確傳輸數據1。信道編碼的作用就像在運快遞，有用的數據是你買的東西，但是為了確保東西安全送給你，需要對其包裝。本來一車能運100個，現在包完了只能送50個，但是准確率有所提高。

對於5G網路來說，3GPP對5G網路的定義范圍包括：eMBB（大流量移動帶寬業務）、mMTC（大規模物聯網）、URLLC（低延時高可靠的業務，比如自動駕駛）。整個5G網路覆蓋的場景對下載速率、時延的要求更加嚴格。因此，對於信道編碼來說，在保證可靠性的前提下，效率顯得異常重要。這里的效率，指的是接近信道容量的極限：香農限。簡單來說，香農限是指在帶寬一定、噪音已知(可以根據通道數據算出來)的情況下，一個傳輸通道能通過有用的數據量上限能夠接近信道所能容納的最大數據量。目前，能夠符合5G網要求的信道編碼就只有LDPC和Polar。

▲典型的LDPC

LDPC碼：即低密度奇偶校驗碼。在1963年由MIT的Gallager博士提出，但在當時由於計算過於復雜而被人所忽略。後來經過不斷努力，簡化LDPC解碼演算法。之後，有人發現LDPC碼可以逼近香農極限，此時的LDPC碼又回到大家的視野。LDPC碼是一種具有稀疏校驗矩陣的線性分組碼，具有更低的誤碼平台，解碼過程簡單高效，復雜度和時延都比較低，目前已經在廣播系統、有線、無線甚至航空航天等通訊系統有所應用，編解碼的演算法比較成熟。

▲Polar Code的優勢

Polar碼：即極化碼。與有著50多歲高齡的LDPC碼相比，Polar碼完全算得上少年兒童。Polar碼由土耳其教授Erdal Arikan在2008年提出。Polar碼基於信道極化理論，在解碼時將信道分為無噪信道和全噪信道，將有用的信息分到無噪信道，將垃圾信息分到全噪信道。因此在理論速度上，Polar碼可以擁有無限逼近香農極限的速率，相比LDPC碼，Polar碼在網路性能能更有優勢，並且編碼和驛碼的復雜度也比較低。

LDPC碼與Polar在入選5G標准中的差異?

而從3GPP RAN1#87次會議的最終結果來看，eMBB場景下，LDPC碼最終成為eMBB成為數據信道編碼長碼，而Polar碼則是控制信道短碼編碼方案。polar碼也並非唯一的標准，而是作為控制信道的短碼。因此主要的問題，就在於數據信道與控制信道、長碼與短碼之間的區別。

簡單來說，控制信道主要負責傳輸指令和同步參數，數據信道主要傳輸數據。舉個例子，比如高速公路，數據信道相當於主路，傳輸各種主要信息，控制信道相當於應急車道，個中作用大家可想而知。而控制信道中所謂的「長短碼」，則是將數字信號所形成的二進制指令進行分組，常用的信息用相對短的二進制位數表示，不常用信息的採用相對長的二進制位數表示。這樣做可以在指令不變的情況下更迅速的進行編碼(常用碼較短，易校對編譯，不常用的較長，可以快速的帶過並且不會影響數據的准確性)。

因此從會議確定的結果來看，此次華為不僅不是所謂的「拿下5G標准」，甚至在5G的eMBB場景下也不是唯一編碼標准。在整個5G eMMB場景中，LDPC拿下數據信道與長碼，Polar拿下控制信道與短碼，最多算是平分秋色。

Polar碼入選5G標准對意味著什麼?

▲會議上支持華為的企業

關注手機的人或許聽說過一句玩笑：高通就是一家賣基帶送處理器的公司。這也從某方面顯示出通訊專利對於企業的重要性。此次Polar碼入選5G標准，對於以華為為首主導Polar碼的中國通訊界，經過多年的努力，終於能在世界通訊標准中立足，盡管只是確立5G標准進程中的一小部分，但也終於實現了中國通訊企業從無到有的一大步，在基礎標准領域有了一定的話語權。並且對於主導Polar碼的華為以及其它中國企業，其已經積累的研究成果在未來有了落地的可能性。

E. LDPC碼的二元域與多元域LDPC碼

對LDPC碼的定義都是在二元域基礎上的，MaKcay對上述二元域的LDPC碼又進行了推廣。如果定義中的域不限於二元域就可以得到多元域GF(q)上的LDPC碼。多元域上的LDPC碼具有較二進制LDPC碼更好的性能，而且實踐表明在越大的域上構造的LDPC碼，解碼性能就越好，比如在GF(16)上構造的正則碼性能己經和Turbo碼相差無幾。多元域LDPC碼之所以擁有如此優異的性能，是因為它有比二元域LDPC碼更重的列重，同時還有和二元域LDPC碼相似的二分圖結構。
假設在域GF(2)和域GF(q)(q=2p)上構造的LDCP碼所對應的校驗矩陣分別是H2和Hq。H2中的元素是0或1，而Hq是由元素0，1，…，q-1構成，Hq中的每個元素都是H2中p個元素的合成。如果設域GF(q)(q=2p)上的一個值a與一個1*p的二進制向量相關聯，那麼把這個向量代入Hq中，就可以得到Hq的二進製表示。對於二進制LDPC碼來說，如果它的校驗矩陣H的列重量足夠大，那麼它可以任意地接近香農限，但是如果增加列重量會使得二分圖中節點之間短圈的數H急劇增加從而使BP演算法的性能下降。而在GF(q)域上構造的LDPC可以解決這個矛盾，它的檢驗矩陣H。可以增加與之對應的二進制校驗矩陣HZ中列的平均重量，且它的二分圖結構並沒有改變，不會造成節點之間短圈數目的增加，從而使得解碼性能得到顯著的提高。這種多元域上的編碼構造會增加解碼復雜度，但是相對於解碼性能的提高來說這種增加是值得的。

F. 用准循環構造法構造LDPC碼的校驗矩陣的演算法流程

QC LDPC碼，可以用代數法和隨機方法構造。如果是代數方法，這里很難說清楚，需要找Linshu老師那邊的文章看看，方法一般都還算簡單，但是需要有限域的知識。

隨機構造的話，以802.16e為代表的QC LDPC碼，大致過程如下
1：先確定基矩陣的大小，基矩陣大的話，存儲需要的空間也會大，但是性能會好些。
2：確定度分布，這個和應用場合有關，一般而言，最大變數度分布大的話，瀑布區性能會好些，但是也還是對存儲要求更高。而且如果基矩陣不夠大的話，度分布大的話，密度會高，這樣會使得環分布優化困難 。
3：確定好基矩陣後，就是利用circulant去替換每個「1」元素了，至於如何選擇circulant，就是個試探的過程。原則多種多樣。

G. ldpc碼的編解碼原理是什麼ldpc碼是如何構造出來的解碼演算法有哪些

BP是belief-propagation，指得是置信傳播法。 BF是Bit-Flipping，指得是比特翻轉法。 兩者的思想都是通過信息傳遞迭代判斷最可能錯誤的點。但BP在計算中使用了先驗概率和後驗概率作為判斷的依據。而BF則是根據傳遞的信息評估某位是1或0的可能性

H. LDPC碼的優勢和劣勢

和另一種近Shannon限的碼-Turbo碼相比較，LDPC碼主要有以下幾個優勢：
1. LDPC碼的解碼演算法，是一種基於稀疏矩陣的並行迭代解碼演算法，運算量要低於Turbo碼解碼演算法，並且由於結構並行的特點，在硬體實現上比較容易。因此在大容量通信應用中，LDPC碼更具有優勢。
2. LDPC碼的碼率可以任意構造，有更大的靈活性。而Turbo碼只能通過打孔來達到高碼率，這樣打孔圖案的選擇就需要十分慎重的考慮，否則會造成性能上較大的損失。
Trubo碼編碼器結構3. LDPC碼具有更低的錯誤平層，可以應用於有線通信、深空通信以及磁碟存儲工業等對誤碼率要求更加苛刻的場合。而Turbo碼的錯誤平層在10量級上，應用於類似場合中，一般需要和外碼級聯才能達到要求。
4. LDPC碼是上個世紀六十年代發明的，現在，在理論和概念上不再有什麼秘密，因此在知識產權和專利上不再有麻煩。這一點給進入通信領域較晚的國家和公司，提供了一個很好的發展機會。
而LDPC碼的劣勢在於：
1. 硬體資源需求比較大。全並行的解碼結構對計算單元和存儲單元的需求都很大。
2. 編碼比較復雜，更好的編碼演算法還有待研究。同時，由於需要在碼長比較長的情況才能充分體現性能上的優勢，所以編碼時延也比較大。
3. 相對而言出現比較晚，工業界支持還不夠。

I. LDPC的解碼演算法都有哪些 BF,BP 和積演算法

置信傳播（BP）一類中有：概率BP，LLR BP，APP-Based，UMP BP-Based等演算法；
比特翻轉（BF）一類中有：KLF加權比特翻轉，LP加權比特翻轉，IMWBF，RRWBF等演算法。