Parallel FPGA implementation of DCD algorithm

Jie Liu, Zhi Quan, Yuriy Zakharov

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Parallel implementation of the dichotomous coordinate descent (DCD) algorithm is proposed and analyzed. The DCD algorithm allows, multiplication-free Solution of the normal equations. The computational load of the algorithm is mainly due to "successful" iterations, when an N-length auxiliary vector is updated, N being the problem size. The parallel design exploits the fact that element of the auxiliary vector call he updated simultaneously. As such an Update involves additions and bit-shifts only, the increase in complexity compared with the serial implementation is not significant, while the throughput call be enhanced. Two parallel designs are proposed; the first uses registers for the system matrix, while the second uses random access memory (RAM). The use of RAM significantly reduces the chip area (number of FPGA slices) without decreasing the throughput. The RAM design exploits the fact that, for the update of the auxiliary vector, only one row of the system matrix is used. The proposed parallel design is verified by applying to an MVDR antenna array beamformer. It is also compared with a QRD-based MVDR beamformer exploiting CORDIC processors. Antenna beampattern obtained from weights calculated in the fixed-point FPGA implementation is compared with a floating-point simulation. The comparison shows good match for a 9-element linear array. The proposed design call provide weight update rate as high as 27 kHz for a 9-element MVDR beamformer.

Original languageEnglish
Title of host publicationProceedings of the 2007 15th International Conference on Digital Signal Processing
EditorsS Sanei, JA Chambers, J McWhirter, Y Hicks, AG Constantinides
Place of PublicationNEW YORK
Number of pages4
ISBN (Print)978-1-4244-0881-8
Publication statusPublished - 2007
Event15th International Conference on Digital Signal Processing - Cardiff
Duration: 1 Jul 20074 Jul 2007


Conference15th International Conference on Digital Signal Processing


  • FPGA
  • DCD
  • MVDR
  • parallel design
  • normal equations
  • multiplication-free

Cite this