Index

# Encoding messages for a noise-less channel

## Huffman coding

Marc Riera (@mrcasals) - Twitter, GitHub

# Noise-less channels: HOAX!

• A communications channel in which the effects of random influences are negligible -> no random error
• The receiver gets the message from the source without any noise
• They don't exist in the real world (there's always some random error)

PROFIT!

But the souce can't send the message as is, so...

# The elements for a code

## What we need

• The channel's alphabet -> `A = {0,1}`
• Our message(s) -> `S = {a1, a2... an}`
• Our messages' probability distribution -> `P = {p1... pn}`, where `pi = P(ai)`

## What we get

• Our code -> `C = {c1... cn}`, where `ci = encoding(ai, A)`
• ``` ```
``` ```
``` The Huffman method for a binary alphabet Huffman method: properties Unique codification: there's no possibility of confusion when decrypting There's no error control The more probable the message, the shortest the encoded message Sort our message by its probability distribution (from higher to lower) We group the two less probable messages: sum the probabilities give a '1' to the less probable message give a '0' to the most probable message Go back to the first step Note: you can skip the first step, but sorting the messages is easier A -> 010, B -> 00, C -> 10, D -> 1110,E -> 011, F ->1111, G ->110 Thanks for watching! By Marc Riera (@mrcasals - Twitter) (/mrcasals - GitHub) ```
``` Use spacebar or the arrow keys to navigateTweet!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0];if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src="//platform.twitter.com/widgets.js";fjs.parentNode.insertBefore(js,fjs);}}(document,"script","twitter-wjs");See all slidesvar _gaq = _gaq || []; _gaq.push(['_setAccount', 'UA-28971430-1']); _gaq.push(['_trackPageview']); (function() { var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })();```