Complete Communications Engineering

Particle Swarm Optimization (PSO) is an algorithm first introduced in 1995 that not only lends itself well to implementation on a Field Programmable Gate Array (FPGA) but actually benefits from being moved from software to firmware. In PSO, we have “particles” which move in a semi-random manner in search of the optimum value of a function ƒ. The algorithm requires evaluation of ƒ at the position of each particle and then each particle’s position needs to be updated based on its history.

This is where the FPGA structure gives us an advantage. In a software implementation we would be required to evaluate ƒ at the position of each particle one at a time. By implementing the algorithm on an FPGA we can perform these evaluations in parallel. This greatly reduces the time necessary for convergence of what is already a fast algorithm. In a typical application there are 20 to 40 particles. This means that a parallel implementation can cut the convergence time to less than 5% of what it would be in series. For a more difficult convergence problem, we might need 100 or more particles to prevent getting caught in a local optimum.

A FPGA implementation of PSO would have applications wherever there is a need to perform the same optimization repeatedly with different inputs. For example, in signal processing, often an adaptive Infinite Impulse Response (IIR) filter would outperform an adaptive Finite Impulse Response (FIR) filter, assuming that we can find the optimal filter coefficients. This is the difficult part, and the reason why generally adaptive filters tend to be FIR filters. Firmware implementation of PSO optimized adaptive IIR filters could be used in echo cancellation in speaker phones and microphones, for modeling the vocal tract for voice compression and in many other applications.