Parallel FPGA Implementation of DCD Algorithm

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 iV-length auxiliary vector is updated, N being the problem size. The parallel design exploits the fact that elements of the auxiliary vector can be 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 can 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 can provide weight update rate as high as 27 kHz for a 9-element MVDR beamformer.