An average-case classifier algorithm and FPGA implementation

A novel algorithm to classify an n-digit scalar from m + 1 intervals is presented. Common classification methods require m comparisons for this problem. The proposed algorithm requires a maximum of n comparisons rather than m. Simulations on scalars expressed in n-bit binary show that, on average, less than n comparisons are required to complete the classification. The algorithm is suitable for regular VLSI implementation, from serial to fully pipelined parallel organizations to optimize either area or time. Synchronous FPGA pipelined implementations are shown, however, the average time benefit of the proposed algorithm and architecture is better suited to self-timed circuits with data completion.