Research On FPGA Design Of QR Decomposition

QR decomposition is a well-known matrix decomposition method in matrix computing theory,with the aim of computing two output matrices Q and R(each output matrix has a specific structure)from the input matrix A.QR decomposition is widely employed in many engineering fields intended to solve the least-square problems,linear system equations and other practical applications.The QR decomposition algorithm based on Givens Rotations is widely used due to its excellent numerical stability and the structure suitable for FPGA(Field Programmable Gate Array)design.However,the calculation of the rotation factor involves complex operations such as division and square root,which is a huge challenge for FPGA design.In view of this problem,this paper makes the following research on FPGA design of QR decomposition:1.Research on QR decomposition alogrithm.At first,three classical QR decomposition mathematical methods are introduced.By comparison,Givens Rotations alogrithm is chosen to solve QR decomposition,and the detailed process has been dicussed.2.Research on triangular systolic array.The triangular systolic array is the ideal structure for implementing QR decomposition based on Givens Rotations.In this paper,the QR decomposition step based on this array is studied and the correctness of the decomposition results is analyzed.3.The FPGA design of square root reciprocal.In this paper,a computation method of square root reciprocal is studied,which is based on the Search-Approximation method.This method avoids the division and square root calculations,and has high accuracy.Moreover,the fact that normalization and denormalization processes will not lead to error expansion is analyzed and verified.Finally,the specific implementation details of the method are studied,and a square root reciprocal calculation module based on FPGA is designed.4.The FPGA design,simulation and verification of triangular systolic array.The FPGA architecture of the two calculation units,boundary module(a square root reciprocal calculation module included)and internal module,are designed.And a 4?4 triangular systolic array which consists of 4 boundary modules and 6 internal modules is designed.Each independent module is simulated and the result is verified.At last,the QR decomposition through the systolic array is simulated,and the result is analyzed and verified.Compared with the similar design,the design of this paper has a great improvement in throughput.