Tag: Coding theory
-
Two different ways to calculate r-ary Huffman Code
Calculating a binary Huffman code is easy: amalgamate the symbols in the source, two-by-two, and then reverse it to get the code. But what of an r-ary Huffman code, of arbitary . Text books give two “different” methods which puzzled me at first until (not too much, I admit) thinking convinced me they were the…
-
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…
-
Kraft’s inequality
Getting round to re-reading Information and Coding Theory– in physical form after the disappointment of the Kindle edition. Maybe it’s because I’m six months older and wiser, but this time more determined to grasp more of the maths in the book, so came to a basic precept of coding theory – Kraft’s inequality – which…
-
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…
-
With zero thanks to @AmazonKindle
Thanks to the SCONUL inter-library agreement between British universities I was able to join Imperial College‘s university library today and went on to borrow a copy of Information and Coding Theory: the book I bought about six weeks ago for the Kindle and subsequently discovered to be all-but-unreadble on that device. Immediately I can see…
-
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…
-
Parity check matrices
Professor Paul Rubin has pointed out an error in my earlier post on on parity check matrices contains a fairly big error (and I have since spotted a less serious one) – so it is in need to rewriting or serious editing. To make sure I got it right next time I bought a book…
cartesian product ... stuff about computing mostly 