New Approaches to the Analysis of Connecting and Sorting Networks.
Abstract
The report is a study of the application of information theory techniques to the field of connecting networks. It shows that these techniques are useful in this new area, and demonstrates that two types of networks can be constructed with a complexity that is proportional to an informational lower bound which is due to Claude E. Shannon. The concepts of information and entropy are extended to fit the context of connecting networks. These not only give insight into the problems of these networks, but are used directly to show that the basic sort-merge algorithm does not of itself imply that sorting networks are inefficient. It is then shown that connecting networks with small blocking probability and time-slot interchangers can be implemented with a complexity that is proportional to the informational minimum. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 17, 1972
- Accession Number
- AD0740198
Entities
People
- Michael J. Marcus
Organizations
- Massachusetts Institute of Technology