Unformatted text preview:

Chapter 2Coding and EntropyNote. This topic is used for the second lecture to retain the attention of studentswith mathematical interests, and in class I jump quickly to the mathematics. AtBerkeley, information theory is taught in a graduate course but not an undergrad-uate one, so I assume my students have not seen any of this material. The finalsection summary should be comprehensible even if all the math is skipped.One of my pet peeves is academic topics which have acquired misleadingnames. Today’s topic grew from a 1948 Shannon paper with the title “amathematical theory of communication” but has subsequently acquired thehugely misleading name Information Theory (W) . The latter Wik ipediapage indicates the (surprising large) scope of this paticular topic, and thethought-provoking book Information: A Very Short Introduction by Floridigives one view of how it fits into the much bigger picture of what “informa-tion” really is. In one lecture all I can do is present one or two of the centralmathematical points, which I tr y to motivate by introducing two somewhatparadoxical statements (A,B) in the next section.2.1 On opposites and simila rsRecently my (non-mathemat i ci an) wife asked me how to make reduced sizecopies on our home printer. Having no mem ory for such things, I consultedthe manual, and the following conversation ensued.David: I see you’ve written d own notes on how to make enlargementsKaty: Yes, I know how to enlargeDavid: Well, reducing is just the sameKaty: (in th at parti cu l ar tone of voice wives use on dense husbands) No,dear, reducing is the oppos i te of enlarging.1314 CHAPTER 2. CODING AND ENTROPYWhat I meant was: instead of setting to 150%, set to 67%. So I was employ-ing the phrase the same in a rather speci al way, to mean if you know howto do one then you know how to do the other. Incidently this is the conceptunderlying computational complexity theory – there is a known large collec-tion of “hard” algorithmic problems su ch that, if one could be solved, thenthey all could be solved. And a million d ol lar Clay prize for proving theycan’t!Moving on to the actual topic of this lecture, code and coding have severalmeanings, but we will be concerned with the following two.• Encryption: coding for secrecyfamiliar from old spy novels and from modern concerns about security ofinformation sent over the internet.• Compression: coding to make a text shorteruseful both in data storage and in data transmission, becaus e ther e i s some“cost” both to storage space and transmission time. These differ in the ob-vious way. Compressing files on your com pu t er will produce, say, a .zip file,and the algorithms for comp r ess i ng and decompressing are public. Encryp-tion algorithms in widespread use are commonly like public-key cryptography(W) in that the logical form of the algorithms for encryption and decryp-tion are public, but a private key (like a password) i s required to actuallyperform decryp t i on. In contrast, intelligence agencies presumably use algo-rithms whose form is secret. For concreteness, in this lecture I talk in termsof coding English language text, but the issues are the same for any kind ofdata.Intuitively there seems no particular connection between enc ryp t ion andcompression – if anything, th ey seem opposites, involving secrecy and open-ness. But a consequence of the mathematical theory outlined in this lectureis that(A) finding good codes for encryption is the same as finding goodcodes for compression.That’s th e first of our “opposite but similar” observations, and her e is thesecond. Wri t i ng an English language document – a lecture like this one,for instance – with conscious intent t o have a particular meaning, seems acomplete opposite of anything to do with chance or randomness. Now thetheory of coding starts by supposing a particular form of randomness forthe data; one can design and test algorithms based on this theory and they2.2. A VERBAL ARGUMENT FOR (A) 15work very well in practice, to the extent of testable quantitative predictions.But why?(B) If you designed a vehicle to work well as an airplane, youwouldn’t expect it t o work well as a submarine. So why do al-gorithms, designed to work well on random data, in fact workwell in the completely opposite realm of meaningful English lan-guage?Briefing: on “random”. In everyday language the word random oftencarries the connotation of “equally likely”, e.g. in the phrase “pick at ran-dom”. Mathematicians like me use it to mean “randomness enters in someway”. In particul ar , “algorithms are designed to work well on random data”does not refer to completely random letters (the monkeys on ty pewriters (W)metaphor) but to the notion of stationary in s ect i on 2.3.2.2 A verbal argument for (A)A code or cipher transf orm s plaintex t into ciphertext.Thesimplestsubsti-tution cipher (W) transforms each letter into another letter. Such codes– often featured as puzzles in magazines – are easy t o break using the factthat different letters and letter-pairs occur in English (and other natural lan-guages) with different frequencies. A more abstract viewpoint is that thereare 26! possible “codebooks” but that, given a moderately long ciphertext ,only one codebook corresponds to a meaningful plaintext message.Now imagine a hypot h et i cal language in wh i ch every string of letters likeQHSKUUC . . . had a meaning. In such a language, a substitution cipherwould be unbreakable , because an adversary seeing the ciphertext wouldknow only that it came from of 26! possi bl e plaintexts, and if all the se aremeaningful then there would be no way to pick out the tru e plaintext. Eventhough the context of secrecy would give hints about the general nature of amessage – say it has military significance, and only one in a million messageshas military significance – that still leaves 10−6× 26! possible plaintexts.Returning t o English language plaintext, let us thi nk about what makesa compression code good. it is intuitively clear that for an ideal codin gwe want each possible s e que nc e of ci p he rt e x t to ar i se from some meaningfulplaintext ( ot h er wi se we are wasting an opportunity); and it is also intuitivelyplausible t hat we want the possible cipher t ex t s to be approximately equallylikely (this is the key issue that the mathematics deals with).Suppose there are 21000possible messages, and we’re equally


View Full Document

Berkeley STAT 157 - Coding and Entropy

Download Coding and Entropy
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Coding and Entropy and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Coding and Entropy 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?