선형 면적-시간 복잡도를 가지는 고성능 정렬기의 설계

Implementation of High-Performance Sorting Machine with Linear Area-Time Complexity

Sorting arbitrarily ordered data is one of the most important and widely used task in digital signal and data processing applications. The conventional sorting algorithms used in such applications are mostly based on word-level sorting. As such, the area-time complexity increasesnon linearly with increase in the number of inputs, and the performance of the sorting machine deteriorates correspondingly. In this paper, we propose a new and efficient sorting algorithm based on bit-level sorting method. The hardware implementation of this algorithm results in a compact and modular sorting engine architecture capable of processing large number of inputs in linear time. The algorithm was created using Very High Speed Integrated Circuit Hard ware Description Language and graphical environment in MAX+PlusII of Altera. The simulation results, obtained using 970 logic cells, indicate that the operating frequency of the proposed circuit is 24.21MHz.