Liu, Jie (2008) DCD Algorithm: Architectures, FPGA Implementations and Applications. PhD thesis, University of York.

Text (PhD thesis by Jie Liu, Electronics Department, 2008)
PhD_thesis_Jie_Liu.pdf Available under License Creative Commons AttributionNoncommercialNo Derivative Works 2.0 UK: England & Wales. Download (1858Kb) 
Abstract
In areas of signal processing and communications such as antenna array beamforming, adaptive filtering, multiuser and multipleinput multipleoutput (MIMO) detection, channel estimation and equalization, echo and interference cancellation and others, solving linear systems of equations often provides an optimal performance. However, this is also a very complicated operation that designers try to avoid by proposing different suboptimal solutions. The dichotomous coordinate descent (DCD) algorithm allows linear systems of equations to be solved with high computational efficiency. It is a multiplicationfree and divisionfree technique and, therefore, it is well suited for hardware implementation. In this thesis, we present architectures and fieldprogrammable gate array (FPGA) implementations of two variants of the DCD algorithm, known as the cyclic and leading DCD algorithms, for realvalued and complexvalued systems. For each of these techniques, we present architectures and implementations with different degree of parallelism. The proposed architectures allow a tradeoff between FPGA resources and the computation time. The fixedpoint implementations provide an accuracy performance which is very close to the performance of floatingpoint counterparts. We also show applications of the designs to complex division, antenna array beamforming and adaptive filtering. The DCDbased complex divider is based on the idea that the complex division can be viewed as a problem of finding the solution of a 2x2 realvalued system of linear equations, which is solved using the DCD algorithm. Therefore, the new divider uses no multiplication and division. Comparing with the classical complex divider, the DCDbased complex divider requires significantly smaller chip area. A DCDbased minimum variance distortionless response (MVDR) beamformer employs the DCD algorithm for multiplicationfree finding the antenna array weights. An FPGA implementation of the proposed DCDMVDR beamformer requires a chip area much smaller and throughput much higher than that achieved with other implementations. The performance of the fixedpoint implementation is very close to that of floatingpoint implementation of the MVDR beamformer using direct matrix inversion. When incorporating the DCD algorithm in recursive least squares (RLS) adaptive filter, a new efficient technique, named as the RLSDCD algorithm, is derived. The RLSDCD algorithm expresses the RLS adaptive filtering problem in terms of auxiliary normal equations with respect to increments of the filter weights. The normal equations are approximately solved by using the DCD iterations. The RLSDCD algorithm is wellsuited to hardware implementation and its complexity is as low as O(N2) operations per sample in a general case and O(N) operations per sample for transversal RLS adaptive filters. The performance of the RLSDCD algorithm, including both fixedpoint and floatingpoint implementations, can be made arbitrarily close to that of the floatingpoint classical RLS algorithm. Furthermore, a new dynamically regularized RLSDCD algorithm is also proposed to reduce the complexity of the regularized RLS problem from O(N^3) to O(N^2) in a general case and to O(N) for transversal adaptive filters. This dynamically regularized RLSDCD algorithm is simple for finite precision implementation and requires small chip resources.
Item Type:  Thesis (PhD) 

Academic Units:  The University of York > Electronics (York) 
Depositing User:  Dr Yuriy Zakharov 
Date Deposited:  02 Sep 2011 15:28 
Last Modified:  08 Aug 2013 08:46 
URI:  http://etheses.whiterose.ac.uk/id/eprint/1629 