Title :
Coding for computing
Author :
Orlitsky, Alon ; Roche, James R.
Author_Institution :
AT&T Bell Labs., Murray Hill, NJ, USA
Abstract :
A sender communicates with a receiver who wishes to reliably evaluate a function of their combined data. We show that if only the sender can transmit, the number of bits required is a conditional entropy of a naturally defined graph. We also determine the number of bits needed when the communicators exchange two messages. Reference is made to the results of rate distortion in evaluating the function of two random variables
Keywords :
data communication; encoding; entropy; function evaluation; graph theory; numerical analysis; random processes; rate distortion theory; bits; combined data function; computing; conditional entropy; function evaluation; message exchange; naturally defined graph; random variables; rate distortion; receiver; Communication standards; Distortion measurement; Entropy; Error probability; Mercury (metals); Random variables; Rate-distortion; Robustness; Sorting; Upper bound;
Conference_Titel :
Information Theory, 1995. Proceedings., 1995 IEEE International Symposium on
Conference_Location :
Whistler, BC
Print_ISBN :
0-7803-2453-6
DOI :
10.1109/ISIT.1995.550438
