一個以元素為基底的疊代並適用於多輸入多輸出通訊的高精確度低複雜度奇異值分解處理器

An Element-Based High Accuracy Low Complexity SVD Processor for MIMO Communications

羅竹均(Chu-Chun Lo)

指導教授 ： 馬席彬

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

摘要

在最近幾年，多輸入多輸出的技術對於無線通訊來說具有一定的影響，因為它不需要額外的頻寬就可以提供大量的資料傳輸。多輸入多輸出技術有許多實現的方式，其中一種便是使用預先編碼的方式來編碼傳輸端的傳輸資料進而改善資料的穩定傳輸，而達到波束成型的概念。預先編碼矩陣通常可以藉由奇異值分解來產生，但是奇異值分解的所需要的運算複雜度卻非常的高，因為這種線性運算需要涉及大量的矩陣乘法並且反覆地進行疊代運算，因此整體系統的運算上，奇異值分解的演算法的設計是非常重要的。
　　在本篇論文，提出了一個以元素為基底的疊代演算法，並使用此方法將矩陣的運算問題轉換成元素的運算問題，而減少奇異值分解所需要大量的矩陣乘法。這種演算法相對於另一種需要以QR分解來進行奇異值分解的演算法來說，少了更多的矩陣乘法而且複雜度更低，因為QR分解在每個步驟都有大量的矩陣乘法。本論文所提出的演算法分成三個主要步驟，分別是是預先處理、慣性特徵值逼近法和三對角分解特徵向量方法。在第一個步驟中的預先處理，會先將矩陣進行三對角化，如此可以減少後續的疊代運算；第二步驟是慣性特徵值逼近法，將已經三對角化的矩陣進行反遞迴的分解和利用矩陣的慣性原理來獲得特徵值；最後是三對角分解特徵向量方法，將所估算的特徵值帶回三對角矩陣配合三對角演算法進行分解。此演算法的架構上是可以組合的，可將維度較小的矩陣分解結果組合成較大的矩陣分解結果。我們使用此演算法來實現16X16維度的奇異值分解運算並且比較使用QR分解來進行奇異值分解來說有將近節省70%的運算複雜度。
　　我們同時將此演算法設計成硬體電路，並且藉由國家晶片中心所提供的90奈米製程技術來實現實體的晶片電路。我們所完成的晶片設計可以操作在100百萬赫茲的運作頻率而其中的消耗功率為22.9毫瓦特。我們的設計每秒可以分解137千個8X8維度的矩陣，其中分解的結果的標準均方差可達10的-4次方。

關鍵字

奇異值分解 ； 多輸入多輸出技術 ； 以元素為基底

並列摘要

In recent years, multiple-input multiple-output (MIMO) technology has attracted attention in wireless communications, because it offers significant increases in data throughput and link range without additional bandwidth.
One of the MIMO techniques uses the pre-coding to adjust the transmitted signal to improve the data reliability and the most widely used technique today is using singular value decomposition (SVD) to generate the pre-coding matrix.
However, the computational complexity of SVD is significantly high due to the matrix multiplications and iterative characteristic.

In this thesis, we present a new element-based iterative, high accurate and low cost singular value decomposition (SVD) algorithm. A new element-based iterative algorithm which with less iterative number of matrix multiplication than QR-based SVD algorithm and matrix's multiplication-based iterative algorithm. The proposed SVD algorithm can be separated into three stages. They are preprocessing, eigenvalue approximation by law of inertia (EALOI) and computing the eigenvectors with tri-diagonal matrix algorithm (CETDMA). The proposed SVD is scalable architecture, so that means a 16X16 SVD can combined by results of 8X8 SVD. Saving 70% complexity in 16X16 matrix compared with QR-based SVD. Based on element's iterative multiplication reduces the complexity efficiently, which support a larger size matrix with 8X8 and 16X16. We verify the proposed design by using the VLSI implementation with CMOS 90 nm technology. The post-layout result of the design has the feature of 0.887X0.887 (mm^2) core area and 22.9mW power consumption at 100MHz operating frequency. Our design can achieve 137k channel matrices (8X8)/s, and NMSE can achieve 10^(-4) and can be extended to deal with different transmit and receive antenna sets.

並列關鍵字

SVD ； Singular value decomposition ； MIMO ； Element-Based

參考文獻

(ReConFig), Quintana Roo, MX, Dec. 2010, pp. 400-405.

[41] Richard L. Burden and J. Douglas Faires, Numerical Analysis, 8nd ed. Flo-

[9] D. P. O'Leary and G. W. Stewart, "Computing the Eigenvalues and Eigenvec-

[30] D. P. O. Leary and G. W. Stewart, "Computing the Eigenvalues and Eigenvec-

[10] J. R. Bunch, C. P. Nielsen, and D. C. Sorensen, "Rank-One Modication of