Tag: Information theory
-
Proof of the existence of an optimal code
This is another piece of extended “working out” based on Information and Coding Theory: essentially a note to demonstrate to myself I have followed one of the proofs in the book (and one that gave me some difficulty until the obviousness of it struck on the Tube this morning). We know from McMillian’s inequality that…
-
McMillian’s inequality
Kraft’s inequality states that: There is an instantaneous -ary code with word lengths if and only if : But what of codes that are merely uniquely decodable, and not necessarily instantaneous? There number is given to us by McMillian’s inequality and the surprising thing is that, despite the looser bound this is: There is a…
-
Another (final) episode in the @AmazonKindle farce
In August I bought this book – Information and Coding Theory. As I was then in rural Norfolk I bought it for the Kindle. That was a mistake. The book is a good one – I would recommend it for those seeking to get to grips with the maths of information theory – an increasingly…
-
Entropy and randomness in communications, a quick introduction
Last year I remarked on how Roger Penrose‘s discussion of entropy in Cycles of Time did more to explain the physical nature of the concept (to me, at least) than many years of formal education. And now, another book, Information and Coding Theory has given me some real insight into how computers deliver pseudo-randomness and…
-
More on Huffman encoding
As well as the basic form of Huffman coding, Huffman’s algorithm can also be used to encode streams to deliver compression as well as coding (at a cost of codes being not immediately decipherable). Once again, with thanks to Information and Coding Theory, here’s a brief explanation. With Huffman coding we can directly code a binary…
-
A blast from the past: Huffman coding
Britain used to lead the world in the deployment of a cutting edge technology: the fax machine. Back when I graduated from university in the last 1980s fax machines were the technology every business had to have and Britain had more of them per head of population than anywhere else. Today I work in an office where…
cartesian product ... stuff about computing mostly 