矩陣求逆的 FPGA實現

李濤, 張忠培

(電子科技大學通信抗干擾技術國家級重點實驗室,四川 成都 611731)

0 引言

矩陣求逆在低密度校驗(LDPC)編碼,多輸入多輸出正交頻分復用(MIMO-OFDM)等領域有著重要的作用,即是應用于 MIMO-OFDM系統中對多徑衰落信道進行信道估計。目前,矩陣求逆大都是用軟件實現,在低速通信的情況下基本能滿足要求,但在高速通信領域,軟件運算速率低的弊端嚴重影響其應用,這就要求在已有軟件算法的基礎上用FPGA加以實現。

目前已有文獻提出對三角矩陣求逆的硬件實現方法[1],但很少有對任意矩陣求逆的硬件實現方法的研究。現結合已有三角矩陣求逆的硬件實現方法和矩陣的 LU分解算法,提出了一種對任意滿秩矩陣求逆的硬件實現方法。VHDL代碼采用流水線操作,并利用 MAC(乘累加)單元,使系統工作頻率得到了進一步提高,系統工作頻率達到100 MHz以上。

1 理論分析

矩陣的一種有效而廣泛應用的分解方法是矩陣的 LU三角分解,將一個n階矩陣A分解為一個下三角矩陣 L和一個上三角矩陣U的乘積。利用上下三角矩陣求逆的便利性來得求任意n階矩陣A的逆矩陣可大大減少運算量和復雜度。具體的流程為：首先對矩陣進行 LU分解,接著對 L和 U矩陣求逆得到L-1和 U-1,再利用矩陣乘積求得原始矩陣 A的逆矩陣 A-1=U-1L-1。

1.1 矩陣的LU分解

若 n階方陣 A∈Cn*n

n的各階順序主子式不等于零,即：

由矩陣的乘法原理,可推導出LU分解的迭代算法[3]：

矩陣的LU分解是一個循環迭代的過程,U矩陣是從第 1行迭代到第n行,而 L矩陣則是從第 1列迭代到第n列,且U矩陣先于 L矩陣一個節拍。

1.2 L矩陣和 U矩陣求逆

首先假設下三角矩陣 L的逆矩陣為R,不失一般性,考慮 4階的情況,利用 LR=I有：

從而求得下三角矩陣L的逆矩陣 R式(4),同樣的方法可以求出 U矩陣的逆矩陣。

首先,利用原始矩陣 L求出逆矩陣 R的斜對角元素 rii。接著,利用原始矩陣L和已求出的逆矩陣的斜對角元素求出與斜對角元素相鄰的斜列 rj,j-1,依次循環,迭代 n-1次,求出整個逆矩陣R。

1.3 矩陣相乘

上三角矩陣U的逆矩陣V與下三角矩陣L的逆矩陣 R相乘,最終得到原始矩陣 A的逆矩陣 A-1=U-1L-1=VR,完成整個矩陣求逆的過程。

2 FPGA實現

與理論算法對應,硬件實現電路包括 3個主要模塊：LU分解、上下三角矩陣求逆和矩陣相乘。硬件系統結構如圖 1所示。

圖 1 硬件系統結構

功能描述：

① Invmatrix_top：頂層模塊,控制整個系統的時序邏輯;

② LU：LU分解模塊,將輸入到 RAM的數據進行 LU分解,結果存儲進 RAM;

③ Inverse_matrix：求逆模塊,分別計算出 L和 U的逆矩陣R和V;

④ Multi：乘法模塊,R和 V相乘,得到 A的逆矩陣,并將結果存入RAM;

⑤ RAM：存儲模塊,隨機存取存儲器。

2.1 LU分解模塊

根據式(2),采用 VHDL硬件描述,在賽靈思(XILINX)的xc4vlx80-12ff1488型號 FPGA布局布線下,采用 ISE仿真,系統工作時鐘能達到 100 MHz以上(約 153.726 MHz)。4?4矩陣的 LU分解仿真結果如圖 2所示。

其中,rst為復位信號,clk為輸入時鐘,start為模塊使能信號,din為輸入數據,edone和done分別為輸出使能提前標志位和使能標志位。

輸入數據 A為{1 0 1 2;1 4 2 2;0 2 3 2;4 1 3 5},輸出數據 L為{1024 0 0 0;1024 1024 0 0;0 512 1020 0;4096 256-510 1026},U為{1024 0 1024 2048;0 4096 1024 0;0 0 2560 2048;0 0 0-2052}。輸出數據與理論值相符,因為 FPGA不能處理浮點數,所有數據均為理論值的倍。輸出數據寬度為20,包括 10位整數位和 10位小數位[3]。

圖 2 LU分解模塊仿真波形圖

2.2 求逆模塊(Inverse_matrix)

求逆模塊也是一個乘累加過程,首先計算出斜對角元素,再依次求出緊鄰的斜列元素[4]。整個模塊分為 RAM存儲單元,乘累加單元和下標控制單元。求逆模塊結構圖如圖3所示。

圖3 求逆模塊結構

其中,MAC單元的 VHDL代碼優化方法與 LU分解代碼優化方法相同,具體控制參考 1.2節所述下三角矩陣求逆運算流程。

2.3 Multi矩陣乘法模塊

矩陣乘法模塊的輸出即為最終輸出。整個系統的延遲等于三個模塊——LU分解模塊,三角矩陣求逆模塊和矩陣乘法模塊的延遲之和,需要 ramu_quot的位寬與 ramu_remd位寬之和的 N+1倍時鐘周期,其中 LU分解需要ramu_quot的位寬與 ramu_remd位寬之和的N倍時鐘周期,矩陣求逆模塊需要 ramu_quot的位寬與 ramu_remd位寬之和的 1倍時鐘周期,乘法模塊采用流水操作時為及時輸出,延遲為零。

3 實驗仿真結果分析

軟件程序的編寫和仿真采用 Mathworks公司的 MATLAB R2008b[5]軟件環境。輸入矩陣

,軟件仿真輸出的逆矩陣INV_A為式(5)：

硬件仿真采用 Mentor公司的 Modelsim SE 6.2b,電路的FPGA綜合采用 Xilinx ISE 7.1i。硬件仿真波形輸出如圖4所示。

仿真波形表明,硬件仿真結果與軟件仿真結果吻合。因硬件無法處理小數,所有數據均換算為整數進行計算,輸出值為理論值的 210倍,輸出高 10位表示整數部分,輸出低 10位表示小數部分。部分值與理論值存在微小偏差,原因是硬件仿真采用定點仿真算法,軟件仿真采用浮點仿真,定點時數據位的截斷產生了誤差。

圖 4 矩陣求逆系統硬件仿真波形

4 結語

通過對矩陣矩陣求逆算法的理論分析,分別闡述了 LU分解、三角矩陣求逆和矩陣乘法的算法實現和硬件實現方法,再用MATLAB和Model Sim分別對軟件和硬件代碼進行了仿真,利用仿真結果對比分析,驗證了硬件實現的正確性。

由于充分利用了硬件的速度優勢,矩陣求逆的 FPGA實現非常適合于現代數字通信領域。現已用于實際項目中,對多點協作(COMP)條件下 MIMO-OFDM系統的多徑衰落信道的信道矩陣求逆,實時進行信道估計。

[1]董永勝.一種整數矩陣求逆方法的證明 [J].長春師范學院學報,2008,16(02)：4-5.

[2]黃廷祝,鐘守銘,李正良.矩陣理論[M].北京：高等教育出版社,2007.

[3]李增喜.LDPC一致校驗矩陣的 LU分解算法[J].通信技術.2009,42(01)：126-127.

[4]李穎異.中國有線電視 [EB/OL].(2006-07-01)[2010-02-11].http：//scholar.ilib.cn/A-QCode～zgyxds200607018.html.

[5]電子科技大學應用數學學院.MATLAB編程技術與數學試驗[D].成都：電子科技大學出版社,2006.