混和隱藏層架構深度學習輔助之低密度奇偶檢查碼解碼器

Deep Learning Assisted Low Density Parity Check Decoder with Hybrid Hidden Layer Architecture

王瑋逸(Wei-Yi. Wang)

指導教授 ： 吳仁銘

國立清華大學/電機資訊學院/電機工程學系所/碩士(2018年)

摘要

在本篇論文中我們運用了深度學習的基礎來輔助置信度傳播演算法(Belief propagation)，進而幫助解碼低密度奇偶檢查碼(Low density parity check codes)。在過去的論文以及實作上已證實了當最小迴圈(small cycles) 的周長很長時，使用置信度傳播演算法來解碼低密度機偶演算法能夠達到接近使用最大似然(Maximum likelihood) 的解碼效果，並且相對於最大以然，置信度傳播有較低的運算複雜度。但是在Tanner 圖上的相同權重(equal weights) 會造成置信度傳播演算法產生訊息重複計算。在Tanner 圖上傳遞的訊息會因為奇偶檢查矩陣(parity check matrix) 的設計，例如：最小迴圈以及小迴圈的總數，或是每個訊息碼在通道中所受到的汙染程度不同進而產生每個訊息有不同的可靠度。置信度傳播演算法在解低密度奇偶檢查碼時依賴每個傳遞訊息之間彼此獨立的特性，但在奇偶檢查矩陣(parity check matrix) 裡的小迴圈會造成在做置信度傳播時彼此訊息產生關連性，違反了置信度傳播其原本的要求，使得整個解碼效果會在高訊雜比時會有一些損失。在過去有URW-BP 及VFAP-BP 使用非相同權重(unqual weights) 來補償因為訊息關聯性而產生的解碼效果損失。但這兩種方法都只使用了一個常數來做調整，並不能夠準確的補償。此外，每個訊息的可靠度會隨著訊息來回傳遞次數以及每個檢查結點(Check node)不同而有不一樣的可靠度，所以很難使用一個公式來表示每個訊息的權重。因此我們設計了一個混合隱藏層神經網路輔助之奇偶檢查碼解碼器，透過神經網路來學習在Tanner 圖上的權重，藉由所學習到的權重補償了相同權重所產生的解碼效果損失，並提高了在高訊雜比的解碼效果。我們也為此設計了一個新的線上學習通訊系統來實現神經網路輔助之奇偶解碼器。

關鍵字

低密度奇偶檢查碼 ； 神經網路 ； 置信度傳播 ； 通道編碼 ； 小迴圈對訊息重複計算的影響

並列摘要

In this thesis, we propose a novel belief propagation for decoding the low density parity check code (LDPC) with the assistance of deep learning method. With long enough girth, the belief propagation (BP) has been shown with the powerful ability to reduce the complexity of decoding the LDPC, and yields nice error correction performance which is close to the maximum likelihood (ML) method. However, the equal weights on the Tanner graph is faced by ”double counting effect”. The messages passed on the edge have different reliability due to the structure of the parity check matrix design, e.g. girth and numbers of small cycles, and the channel condition each bit faced. The performance of BP relies on the independent of messages from different nodes. However, the small cycles in the Tanner graph leads to correlation of messages. The dependency of messages violates the independent requirement of BP in decoding and degrade the performance of belief propagation. There are many methods such as uniformly reweighted belief propagation (URW-BP) and variable factor appearance probability belief propagation (VFAP-BP) using unequal weights to deal with the message dependency in BP. However, the compensation is done by using one constant weights which is not general enough. Besides, the condition of reliability is changed in every iteration of decoding and the condition also varies from different check node. It is very difficult to develop a formula of the reweighted factor. Hence, we design a hybrid hidden layer neural network assisted BP algorithm to learned the unequal weights on Tanner graph. The weights compensate the negative effect of inreliability in the parity check matrix structure. With the aid of the learned weights, the error correction performance in high SNR region is enhanced. We also design an online training communication system to improve the modern system.

並列關鍵字

Low density parity check code ； neural network ； belief propagation ； channel coding ； double counting effect for small cycles

參考文獻

[1] E. Nachmani, Y. Be’ery, and D. Burshtein, “Learning to decode linear codes using deep learning,” in Proc. IEEE Annu. Allerton Conf. Commun. Control Comput. (Allerton), Monticello, IL, USA, 2016, pp. 341–346.

[2] C. Shannon, “Communication in the presence of noise,” in Proceedings of the IEEE, vol. 72, Sep. 1984, pp. 1-5.

[3] R. G. Gallager, Low density parity check codes, Cambridge, 1964.

[4] W. S. McCulloch and W. Pitts, “A logical calculus of the ideas immanent in nervous activity,” The bulletin of mathematical biophysics, vol. 5, pp. 115-133, Dec 1943.

[5] K. Fukushima and S. Miyake, “Neocognitron: A Neural Network Model for a Mechanism of Visual Pattern Recognition,” IEEE Trans. Syst. Man Cybern., vol. SMC13, pp. 826/–834, 1983.