assignments

information entropy

• Take a first pass at reading Biggs textbook chapters 1 through 3, with an eye towards understanding the definition and intuition behind the terms
  • alphabet, string, message, word
  • code
  • uniquely decodable
  • prefix-free
  • kraft-mcmillan number
  • optimal code
  • information entropy
  • huffman code
• Give a specific example of each of the preceding terms.
• For another take on the notion of "information entropy", start reading part 1 of Shannon's Mathematical Theory of Communication, which is the first paper to propose this concept.
• Follow up any of these in wikipedia or other online sources as need be.

more entropy

• Finish reading through chapter 3. Start reading chapter 4, including LZW.
• On page 33, do exercises 3.6, 3.7, and 3.8.
• Do exercise 3.13 on page 40.
• In a computer language of your choice, start writing a program that calculates the information entropy of some input text. You should have at least a working prototype by Tues, which will be further tested and refined for next week's assignment. The program should
  • Count the number of each symbol (i.e. character).
  • From that, construct the probabilities p(i).
  • From that, and assuming for now (incorrectly, probably) that the character probabilities don't depend on other characters, calculate the entropy. Decide what base to use, and discuss why you chose that one.
• Choose some text sources, and test your program. (You can if you like generate random text with different characteristics to test, or use, say, Moby Dick.)
• Try compressing those text files with any of the standard utitilies (gzip etc). Is there any connection between the entropy and how much the file can be compressed, and if so, what exactly?

conditional probability

• Read through chapter 4
• Read chapter 2 in MacKay's book .
• Do exercise 4.7 on page 54 of our "Codes..." text. What is the order 0 entropy estimate of that distribution? The order 1 entropy estimate?
• Extend your code from last week to calculate the order 1 entropy, using the probabilities of pairs of symbols. Compare with the order 0 and gzip compression ratio with some english text, and discuss.
• Read about (i.e. google search, wikipedia, our text, ...) "arithmetic coding", explain its basic ideas, and give a simple example.
• Read about (from any source) "LZW compression", explain its basic ideas, and give a simple example.
• Read about (from any source) "Burrows-Wheeler" compression (or transform), explain its basic ideas, and give a simple example.
• One more: explain briefly "run length" encoding.

DCT

• Finish the reading from last assignment.
• Explore the discrete cosine transform and JPEG's loss of information:
  • read wikipedia:discrete cosine transform, which defines it.
  • Using either the DCT or an analogous 4x4 transform, calculate explicitly its effect on a representative block of numbers, such as a "stripe" pattern made up of (say) 50's and 100's, alternating in 2 to 4 pixel wide stripes.
  • Round some of the higher frequency components to a power of 2
  • Transform back to see the change.
• If that feels like too much of a challenge, read up on "Discrete Fourier Transforms", and do something similar in 1 dimension with N=4, transforming [50,50,100,100] into something else. Again, round off the higher frequencies, and transform back.
• Pick one of the lossless compression algorithms we've discussed, and design an implementation. Start writing some code. The first graded "mini-project" will be to finish this, along with an entropy analysis and comparison, for the following week.

compression project

• Finish the compression coding project that was assigned last week, for the first graded work this term.
  • You should have a working computer program, including documentation and sample runs, which
  • takes as input a text file, and
  • implements any one of the compression algorithms we've looked at
  • calculates the entropy of the input, and
  • outputs some statistics about compression ratios, entropy, and all that.
  • Specific details are up you: your job is to convince me you understand this stuff.

noisy channels

• Read chapter 5 in the text.
• Finish the calculation we started in class on Feb 19, namely with Γ = (1,0; .5, .5) find the maximum channel capacity, and discuss what that means.

error correcting

• Read chapter 6 in the text.
• Do problems 6.6, 6.15, 6.17
• Read chapter 8
• Do problems 8.7, 8.10, 8.11, 8.13

midterm grades

• a place for Jim to record midterm grades

hamming codes, rates, capacity

• read 9.1 on hamming codes.
• read the beginning of chapter 7; review "channel capacity"
• do the following problems : 7.8, 7.11, 8.14, 8.17
• What are (n, k, delta) for a hamming code with m=5? Give an example of a correct code word. Give an example of a word that contains an error, and specify where the error is.
• Coming: after break I am planning on assigning a programming assignment to implement encode/error_simulate/decode for the m=5 hamming code from the previous question, which will be the 2nd piece of graded work for the course.

CRC

• Browse filipg's painless guide to CRC error detection.
• Do a simple CRC example out by hand, using any input message and reasonable CRC poly. In other words, do a calculation like that in the fully worked example.
• Give me a status report of your hamming project code.
• ... and I will likely assign some readings on crypto; stay tuned.

hamming project

• This is the 2nd graded work.
• I'm giving you two weeks, but we'll have moved on by then.
• Implement, test, analyze, and discuss a hamming error correcting code simulation.
• Any reasonable programming language (python, mathematica, ...) is OK.
• Your simulation should :
  • Choose a specific version of a hamming code (n,k) to implement, with r=1 and d=3. (A 1 error correcting code.)
  • Create an input information stream, or use a given source file as input.
  • Encode blocks of the input information using the hamming code.
  • Introduce some random bit errors with some (small) chosen probability.
  • Decode the blocks, correcting any errors.
  • Test pieces of your code on some simple cases were you know the answer.
  • Calculate the entropies and channel capacity (both analytically and numerically for full credit) and discuss what's going on.
• You don't need to do this using bit arithmetic if you don't want to; strings of 0's and 1's are fine.
• ... but binary is OK too.
• One reasonable choice would be the SECDED (72,64) code described in wikipedia:hamming code. (This could even be done in binary, with the encoding turning a block of 8 ascii charcters into 9.)

symmetric codes

• Read chapter 12 in the text (if you haven't already), and do exercises 12.10 and 12.11. (We started these in class last week).
• Get a command-line openssl on your computer, if it isn't already. Use it to encode the text "This is the plain text that you should encode to make Jim happy." with the key "quick_brown_foxes_are_foxy" in aes-128-cbc and base64.
  • So ... what is aes-128-cbc? Be specific.
  • Did you use a salt? Is your code the same each time, or different?
  • Is all of the key required? Should it be longer? Will any other key give the same result?
• Read (or at least start reading) chapter 13, on RSA. Use any other sources (i.e. wikipedia) you like to explore this topic, and come to class Tues ready to talk about it.
• Do exercises 13.4 and 13.6 in the text, both on page 211.
• Read about diffie hellman shared secrets.

asymmetric codes and hashes

• Read
  • chapter 14, on diffie-hellman and hash functions.
  • http://en.wikipedia.org/wiki/Diffie-Hellman
  • http://en.wikipedia.org/wiki/Cryptographic_hash_function
  • http://en.wikipedia.org/wiki/MD5
  • http://en.wikipedia.org/wiki/SHA-1
• Come to class Tues ready to discuss MD5 and SHA-1.
• Do exercises 14.5, 14.6, 14.9, 14.15, 14.16 in the text.
• Use openssl to generate a public/private RSA pair, and encrypt/decrypt a message with them.

project description

• Come to class with a description of what you're doing for your final project, ready to discuss : what algorithms are you using, what is the protocol of exchanged messages, and what does the protocol accomplish.

final project - a toy crypto suite

• Implement a "toy" version of something like the secure sockets layer cryptographic protocol : a negotiated public/private key or other shared secret, an exchanged symmetric key, a message hash, an embedded date, and a delivered package of header + coded message + hash.
• The size of your keys does *not* have to be cryptographically secure. For example, using RSA or D-H with small primes is OK.
• Your method doesn't have to be exactly the same as SSL, as long as it accomplishes (at least in principle, if scaled up in size) the same goals: a signed, secure, tamper-proof channel.
• Explain how your system works, and give a specific example.
• Please *don't* give me just the code : I really want to see a coherent description of what's going on.

term grade

• a place for Jim to record grades