以分解圖及外來資訊轉換曲線輔助的無線通訊系統之分析與設計

Design and Analysis of Wireless Systems with Factor Graph and EXIT Chart

李曜男(Yao-Nan Lee)

指導教授 ： 陳博現

國立清華大學/電機資訊學院/通訊工程研究所/博士(2007年)

摘要

為了滿足使用者高速下載數位多媒體內容的需求，通訊領域的研究 人員一直持續不斷地發展不同層面的通訊傳輸技術以期使整體無線 通訊系統的效能可發揮到極致。從文獻中可以發現要達到這個目標 所需克服的研究挑戰包含1) 發展一個有效率的時空編碼及調變機制來提高傳輸速率，2) 發展一個實用的迭代式接收器來復原被破壞的傳送信號，及3) 發展一個嶄新的無線網路架構及其上所使用的封包排序演算法來有效地利用網路中可重複使用的空間資源並避免交互 干擾的情形發生。明顯地這些挑戰都不是很容易解決的研究問題， 例如設計一個有效率的排序演算法在本質上是一個複雜的高維度最 佳化問題。然而近來由於外來資訊轉換曲線(EXIT Chart)及分解圖(Factor Graph)理論的高度發展，此論文主要就是呈現我們是如何 利用這兩項工具來試圖解決以上所提到的研究挑戰。 第一個研究主要是利用EXIT Chart及大系統效能分析技巧來探討低密度檢查碼及多輸入多輸出系統之間的關係，我們證明了傳送天線 數目及接收天線數目的比率在設計這一類的系統上扮演一個非常重 要的參數，並且我們所提出的時空編碼設計方式較傳統的方式而言 在時間上是非常有效率的。 第二，由於利用Wiener濾波器來做頻道估測是一個簡單又有效的方法，所以我們想要利用EXIT Chart 來探討有軟資訊輔助的Wiener 頻道估測器在迭代式接收器中的行為表現。我們發現在接收器上使 用迭代式資訊交換技術並不一定總是能使得接收器的效能變好，主 要仍得取決於1) 所選取的錯誤更正碼種類，及2) Wiener頻道估測 器如何使用這些軟資訊。 第三，利用分解圖理論我們發展了一個嶄新的分散式封包排序演算 法來處理接力式網路中的封包排序問題。此演算法無論在平均封包 接收率，使用者公平性，複雜度及可適性上都具有相當不錯的效能。

關鍵字

分解圖 ； 外來資訊轉換曲線 ； 低密度檢查碼 ； 迭代式接收器 ； 接力式網路 ； 封包排序

並列摘要

To satisfy the demand for ubiquitously accessing multimedia data services, researchers have been continuing to develop various techniques which aim at pushing the overall system throughput to its limit. From the literature, research challenges towards this end include the developments of 1) an efficient space-time encoding and modulation scheme to raise the transmission rate, 2) a practical iterative receiver to recover the corrupted transmit-signals, and 3) a brand-new network architecture with an efficient scheduling algorithm to exploit the possible reuse of spatial resources without mutual interference. Each of the three challenges is not an easy-to-deal-with obstacle, for example, designing an efficient scheduling algorithm involves a complex multi-dimensional optimization which in nature is an NP-complete problem. However, thanks to the recent celebrated break-through in the EXtrinsic Information Transfer (EXIT) chart and the Graph theory, this thesis presents the progress we have made toward solving the three challenges with the help of the EXIT chart and Graph techniques.

First, a close-to-Shannon-limit space-time encoding and modulation scheme for multiple-input multiple-output (MIMO) system is developed with the help of the EXIT chart by researchers at Bell Lab in 2004, which maps the coded bits of an irregular low-density parity-check (LDPC) code directly onto a modulation signal set. Instead of further searching for more capacity-approaching LDPC codes for all the practical MIMO system configuration, we develop several universal-good LDPC codes by investigating the relationship between the LDPC codes and the underlying MIMO system configuration through the EXIT chart and the large-system performance analysis technique. We demonstrate that the ratio of the numbers of the transmit and the receive antennas plays a crucial role in such LDPC-Coded MIMO systems, and the rewards for redesigning LDPC codes are not so much when the antenna ratio is unchanged.

Second, since the channel estimation techniques through Wiener filtering are believed to be efficient methods for receivers to recover the corrupted transmit-signals, it is especially desired to know whether the promising idea of iterative processing can be applied to the receivers consisting of soft-information-aided Wiener-filter-based channel estimators and error-correction decoders. Therefore, we wish to investigate 1) how different variants of the two functional blocks interact, and 2) whether such iterative interactions can improve or degrade the system performance through a unified EXIT chart analysis. It is shown that the iterative processing between Wiener-filter-based channel estimator and error-correction decoder does not always improve the receiver performance, depending on 1) which family the error-correction code is from, and 2) how we utilize the soft information of the coded bits at the Wiener-filter-based channel estimator.

Third, the cellular relay network capable of multi-hop data transmission seems to be a promising network architecture to boost the overall system throughput. However, since simultaneous data transmissions are allowed in such network, it needs an efficient scheduling algorithm to avoid the frequent data collisions problem. Otherwise, significantly higher data packet throughput in a relay network can never be achieved. A novel distributed algorithm tackling with this NP-complete scheduling problem is developed through the recent modeling and computational methodology of factor graphs. Numerical experiments show that the proposed distributed scheduling algorithm not only obtains average packet throughput comparable or even better than some exhaustive-search-based algorithms, but also takes care of the throughput fairness issue among all the MSs.

並列關鍵字

Factor Graph ； EXIT Chart ； LDPC Codes ； Iterative Receivers ； Relay Networks ； Scheduling Algorithms

參考文獻

[1] G. J. Foschini and M. J. Gans, “On limits of wireless communications in a fading environment when using multiple antennas,” Kluwer Academic Publishers-Wireless Personal Communication, pp. 311-335, Jan. 1998.

[2] ˙I. E. Telatar, “Capacity of multi-antenna Gaussian channel,” European Trans. Telecom., vol. 10, pp. 585–595, 1999.

[4] S. ten Brink, G. Kramer, and A. Ashikhmin, “Design of low-density parity-check codes for modulation

[5] H.-A Loeliger, “An introduction to factor graphs,” IEEE Signal Processing Magazine, vol. 21, pp. 28-41, Jan. 2004.

[6] Y. Mao and F. R. Kschischang, “On factor graphs and the Fourier transform,” IEEE Transaction