K-winners-take-all circuit with O(N) complexity.

Presents a k-winners-take-all circuit that is an extension of the winner-take-all circuit by Lazzaro et al. (1989). The problem of selecting the largest k numbers is formulated as a mathematical programming problem whose solution scheme, based on the Lagrange multiplier method, is directly implemented on an analog circuit. The wire length in this circuit grows only linearly with the number of elements, and the circuit is more suitable for real-time processing than the Hopfield networks because the present circuit produces the solution almost instantaneously-in contrast to the Hopfield network, which requires transient convergence to the solution from a precise initial state. The selection resolution in the present circuit is, however, only finite in contrast to the almost infinite resolution in the Hopfield networks.