先進錯誤控制技術及其應用之研究

Abstract

編碼與錯誤控制理論在近十餘年來有突破性的進步，使得通訊系統性能已經可以十 分接近消息理論所預測的極限，即所謂的謝儂極限(Shannon limit)。這些突破主要由於 渦輪碼(turbo code)的發明與低密度位元檢測碼(low density parity check code, LDPC code) 的重新被發現(re-discovery)。這兩類碼之所以有強大的改錯能力，追本溯源應當歸功於 其所用的遞迴式信度傳遞(belief propagation, BP)解碼法。由於BP 在諸多領域如計算機 視覺、人工智慧、錯誤控制碼(Error Control Codes, ECC)，以及數位通訊上的廣泛應用及 突出的性能表現，信度傳遞已被公認為一非常有效且強而有力的統計推論工具。 然而，單就錯誤控制技術的領域而言，現存的信賴傳遞演算法仍有許多改善空間。 以信度傳遞演算法應用於渦輪碼和低密度位元檢測碼的加乘演算法(sum-product algorithm, SPA)為例，晚近的研究顯示信度傳遞演算法的固定點(fix point)相當於其對應 分解圖(factor graph)的自由能在貝特近似下的全域(global)穩態點。不過，當分解圖包含 迴圈(loops)時，信度傳遞演算法不保證必然收斂，即便收斂也只被保證收斂於貝特自由 能的區域穩態點。因而，最近有一些新演算法試圖避免區域最小化而透過直接使用傳統 的最優化方法使自由能減到最小來得到最佳估測解。不過，這些最佳化方法常常有複雜 度高且收斂慢的缺點。因此，本計畫主要目的之一即在試圖針對信賴傳遞演算法做更進 一步的研究。其主要的方向有二：一、在以不改變現有信賴傳遞演算法的原則之下，如 何利用解碼排程來有效提升性能表現加快收斂速度並減少硬體與記憶體之使用量與複 雜度以利於硬體實現。二、透過最優化方法裡使用的退火法，我們嘗試使用退火的信度 傳遞(annealed belief propagation, ABP)演算法來進一步減輕區域性收斂的問題。 另一方面由於BCH 碼或里德-所羅門碼(Reed-Solomon code, RS code)長久以來 廣泛被使用在各種資料儲存系統及諸如外太空通訊系統、數位廣播系統等通訊領 域。這些改錯碼配合硬式解碼器雖有不錯的表現但離最佳ML 解碼尚有一段不小的 差距，而軟式解碼技術過去將近十年雖有不少進步，可惜大都因為複雜度過高而陷 於難以實現的困境。我們打算從不同的角度來解決這個問題。我們準備嘗試利用基 於KL 距離(Kullback-Leibler distance)的馬可夫鏈蒙地卡羅(Markov Chain Monte Carlo) 隨機最佳化法來著手，希望能以綜合隨機與決定論(deterministic)的方式找出 性能可以任意逼近最佳解的低複雜度解決方案。 如同傳統的信度傳遞或蒙地卡羅最佳化技術有廣泛的應用範圍，我們準備發展的 這些技術也可應用到改錯碼之外的領域。我們考慮的應用課題將包含同步、細胞收尋、 通道估計與合併同步通道估測與解碼等。

Two major breakthroughs in coding theory, namely the invention of the turbo code and the rediscovery of the LDPC codes, have ignited highly intensive research and development efforts worldwide in the past decade. Thanks to these endeavors, we now have a much better understanding about the behaviors of these two classes of codes, their variations and the associated iterative decoding algorithms, e.g. BCJR algorithm for turbo decoding and sum-product algorithm (SPA) for LDPC codes. Recent studies show that fixed points of BP algorithms correspond to the stationary points of the Bethe approximation of the free energy for a factor graph. However, BP algorithms do not promise convergence when the associated graph contains cycles. Even if they converge, they are only guaranteed to converge to a local minimum of the Bethe free energy. Some new algorithms attempt to avoid local minimums by directly minimizing the free energy, through using the conventional optimization schemes. These algorithms, however, are often much more complex and yield much slower convergence rate. One of the main goals of this proposed effort is to develop advanced schemes that solve these problems. More specifically, we shall develop (i) New scheduling approaches for BP-based decoding algorithms that reduce the short-cycle effect, improve the BER performance, and lessen both computational and memory requirements. (ii) Novel annealed BP (ABP) algorithms, which are inspired by the deterministic annealing methods used in optimization problems, to alleviate ill-convergence behavior of conventional BP approach. On the other hand, BCH and Reed-Solomon (RS) codes have been used for error control in a wide variety of applications, ranging from data storage systems to deep-space communications. However, the existent decoding schemes either perform far inferior to that achievable by the ML solution or are often much more complex than that of a hard-decision decoder. We shall solve this soft-decision decoding problem from a different perspective. We shall develop novel stochastic decoding algorithms for RS codes by using a Kullback-Leibler distance (i.e., cross entropy, CE) based Markov Chain Monte Carlo approach. Based upon our understanding of the CE-based Monte Carlo method and the algebraic properties of BCH and RS codes, the proposed approach does promise an efficient solution and near-optimal performance. Besides presenting the decoding performance of the proposed approaches, we shall also apply these techniques to related communication design issues like synchronization, preamble structure and cell-search, channel estimation and joint synchronization and channel estimation, etc.