Sorting without exchanges on a bit-serial systolic array

Megson, Graham M. (1990) Sorting without exchanges on a bit-serial systolic array. Circuits, Devices and Systems, IEE Proceedings G, 137 (5). pp. 345-352. ISSN 0956-3768

Full text not available from this repository.
Official URL:


The author considers, a number of bit-serial systolic designs for ordering a list of n elements without 'on-the-fly' exchanges are considered. The algorithms require 4n+p+k bit steps where p=log2 n and k is the number of bits required to encode all the possible elements. The arrays require O(n(p+k)) bit cells with a complexity roughly the same as that of a full adder and between max (p,k) and p+k input/output pins. The input to the array is the list to be sorted and an auxiliary vector whose elements have bit length p. The output is the list itself and the auxiliary vector, which is updated to produce pointers to the correct position of each element in the ordered list.

Item Type: Article
Uncontrolled Keywords: VLSI, cellular arrays, digital arithmetic, logic arrays parallel processing, sorting, subroutines, algorithms auxiliary vector, bit length, bit-serial systolic array full adder, nonexchange sorting, on-the fly exchanges ordered list, pointers
Subjects: University of Westminster > Science and Technology > Electronics and Computer Science, School of (No longer in use)
Depositing User: Miss Nina Watts
Date Deposited: 27 Jan 2009 11:29
Last Modified: 19 Oct 2009 15:29

Actions (login required)

Edit Item (Repository staff only) Edit Item (Repository staff only)