Bit-serial systolic sorting: general complexities and an implementation in VLSI

Bit-serial systolic sorting in very large scale integration (VLSI) is considered. Lower bounds on the area, computation time, and flush time for such a sorter are derived for three different input formats, namely the bitwise, the wordwise and the unconstrained formats. The logic design and CMOS circuit design of an optimal bit-serial wordwise systolic sorter are presented. The performance characteristics of the designed chip are discussed.