DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
Bounds to Complexities of Networks for Sorting and for Switching,
ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB
Pagination or Media Count:
A network which sorts n numbers when used to sort numbers of only two sizes, 0 and 1, can be regarded as forming the n frontal unate symmetric boolean functions of n arguments. When sorting networks are constructed from comparator modules they appear to require 1 delay time or number of levels of order log of n to the base 2 squared, 2 size or number of elements of order log of n to the base 2 squared, and 3 formula length or number of literals of order n log of n to the base 2. If one permits the use of negations in constructing the corresponding boolean functions, these three measures of complexity can be reduced to the orders of log of n to the base 2, n, and n to the 5th power respectively. The latter network however is incapable of sorting numbers and may be thought of as merely counting the number of inputs which are 1. One may incorporate this network, however, in a larger network which does sort and in time proportional to only log of n to the base 2. Author
APPROVED FOR PUBLIC RELEASE