基於Matlab HDL Coder的8x8實矩陣QR分解
點我下載，使用Matlab 2018b打開
QR分解是計算機視覺以及機器學習中重要的矩陣求逆方法。它可以將矩陣分解成一個正交矩陣Q與一個上三角矩陣R的積。一般來說，QR分解有三種方法：1. Householder transformations，2. Givens rotation，3. Gram-Schmidt orthogonalization。其中Matlab的qr()函數使用的是方法1，此處我們應用方法2來分解矩陣，方法3是一般教材中介紹的常規方法。
P.S. 實現8x8實矩陣是因為在我RANSAC的項目中需要固定實現8x8矩陣的求逆，這個基於循環的演算法可以很容易的拓展到其他大小的矩陣上去，但並不適用於未知大小矩陣的分解。
本文對基於Givens旋轉的QR分解原理不做介紹，具體可見一下鏈接：
【1】高等數值演算法與應用（三），清華大學 喻文健
【2】Givens Rotation，WikiPedia
一下貼出用於驗證的matlab代碼
Givens旋轉的本質上就是計算兩個向量夾角的sin和cos函數，因此，我們選取DSP HDL工具包中的優化CORDIC模塊（Complex to Magnitude-Angle HDL Optimized）來計算，因此圖1中Givens函數的Simulink模塊設計如下：
由於G矩陣只有4個非零值，所以在嵌套循環中，Q和R的每次只需要更新兩行/列，其餘則保持不變。我們自需要每次讀出需要更新的行/列，與2x2的sub G矩陣相乘即可，如下圖所示：
至此，基於Givens的QR分解主要功能模塊已經設計完成，我們進行剩下的控制模塊設計。QR分解的外部介面如下：
U_col_?，V_col_? - Q和R分量load介面
start_pulse - 分解完成後讀取開始信號
start_svd - QR分解開始信號
R_rd_ext，Q_rd_ext - 分解完成後QR矩陣讀取address
R_col，Q_row - 分解完成後QR矩陣輸出
qrd_done - 分解完成信號
FSM用來控制每一步的進行。首先FSM在idle狀態，當外界將待分解矩陣U和單位矩陣V裝載進QR分解模塊之後，將start_svd信號置1，開始QR分解（請原諒我沒有把svd改成qr，我直接把svd分解的狀態機拿過來改改用了）。然後FSM進入read狀態讀取Givens矩陣計算所需要的R分量，當計算完成後FSM進入update狀態來更新Q和R矩陣。如果循環完成，則回到idle狀態等待下一輪分解，否則回到read狀態讀取R對應分量。FSM設計推薦使用matlab function模塊，具體設計參見附件模塊中FSM。
嵌套計數器設計沒有太多好說的，直接上圖：
為了設計方便，我們將Q按行分別存儲在8個RAM中，R按列分別存儲在8個RAM中。
至此，QR分解模塊已經設計完成。從性能上來看，完成一次8x8的實矩陣分解需要(1+7)*7/2=28次循環，通過logical analyzer的模擬，一共需要約1500個時鐘周期。此設計的不足之處在於一些trigger的添加，比如QRdecomp/Subsystem/trig1以及與其類似的模塊，這是由於對hdl coder模塊功能理解不到位引起的（Enabled Delay和Unit Delay Enabled Synchronous，以後會有這兩個模塊的講解）。
後話：一年前我是極其抵制使用金主爸爸的HDL Coder和Vision HDL工具包的，因為學習曲線陡峭，Community太小等原因，但是習慣就會發現這個工具實在太好了，徹底擺脫了代碼的編寫，可以把精力放在演算法本身，並且debug比起其他HLS工具方便了很多。對於初學者建立硬體思維很有益處~
推薦閱讀：
TAG:MATLAB |