Title :
The entropy of traces in parallel computation
Author_Institution :
Sch. of Electr. Eng., Cornell Univ., Ithaca, NY, USA
fDate :
7/1/1999 12:00:00 AM
Abstract :
The following problem arises in the context of parallel computation: how many bits of information are required to specify any one element from an arbitrary (non-empty) k-subset of a set? We characterize optimal coding techniques for this problem. We calculate the asymptotic behavior of the amount of information necessary, and construct an algorithm that specifies an element from a subset in an optimal manner
Keywords :
encoding; entropy; parallel algorithms; set theory; VLSI; asymptotic behavior; entropy; information bits; k-subset; optimal coding techniques; parallel computation; Adders; Associate members; Circuits; Concurrent computing; Entropy; Information theory; Probability distribution; Very large scale integration; Voltage; Wire;
Journal_Title :
Information Theory, IEEE Transactions on
