Recursive Odd-Even Sorter for Vector Quantizer

Abstract

A recursive, odd-even transposition sorter based vector quantizer which is used in mismatch shaping algorithms is presented. Although recursive parallel sorting algorithms require less area than fully parallel sorting algorithms, they are slower than fully parallel algorithms. A widely used recursive parallel sorting algorithm is the perfect shuffle which requires multiple clock cycles to shuffle and sort the data. The proposed recursive algorithm uses fewer clock cycles than the perfect shuffle to sort less than 80 inputs. An area efficient version is also proposed to sort less than 16 inputs faster than perfect shuffle algorithm. To compare the performance of various sorting algorithms suitable for vector quantizer, they are realized and synthesized in TSMC 40nm low-power technology. Speed and area results indicate that the proposed algorithm sorts 32 inputs at a 42% faster rate by using 14% fewer components than the perfect shuffle sorter and a 80% slower rate by using 27% fewer components than the Bitonic sorter. The area efficient version sorts 32 inputs at a 21% slower rate by using 32% fewer components than the perfect shuffle sorter.