Anathem by Neal Stephenson is tangentially related to Information Theory. More abstract/concepual math and general philosophy than CS/InfoTheory.<p>An excellent novel, highly recommended.
Daemon & Freedom by Daniel Suarez (<a href="http://en.wikipedia.org/wiki/Daniel_Suarez" rel="nofollow">http://en.wikipedia.org/wiki/Daniel_Suarez</a>)<p>Rudy Rucker (<a href="http://en.wikipedia.org/wiki/Rudy_Rucker" rel="nofollow">http://en.wikipedia.org/wiki/Rudy_Rucker</a>)<p>Cory Doctorow has some good stuff and most of it is available free from his site (<a href="http://craphound.com/" rel="nofollow">http://craphound.com/</a>).
some of the older greg egan stuff (he was a programmer). i can't remember any titles, but a look at the summaries should make things clear (or his site - <a href="http://gregegan.customer.netspace.net.au/" rel="nofollow">http://gregegan.customer.netspace.net.au/</a>)<p>[edit: ok, so after looking there (ow my eyeballs!) permutation city is one i remember, and there was also a collection of short stories...]
<i>His Master's Voice</i> by Stanislaw Lem is about trying to decipher an alien radio transmission, and focuses a lot on the mathematics and information theory involved as far as I remember.