MATH3411 Information, Codes and Ciphers

MATH3411 is a Mathematics Level III course. See the course overview below.

Units of credit: 6

Prerequisites: MATH1081 or MATH1090 or MATH1231(CR) or MATH1241(CR) or MATH1251(CR) or MATH2099. 

Cycle of offering: Yearly in Semester 2 

Graduate attributes: The course will enhance your research, inquiry and analytical thinking abilities.

More information: This recent course handout (pdf) contains information about course objectives, assessment, course materials and the syllabus.

The Online Handbook entry contains up-to-date timetabling information.

If you are currently enrolled in MATH3411, you can log into UNSW Moodle for this course.

Course Overview

Well known examples of codes include morse, ASCII, ISBN book numbers, as well as the bar code used on grocery items. A code provides a way of converting a message from an arbitrary source alphabet into a form suitable for transmission or storage. This usually entails some binary procedure suitable for an electronic device. Coding theory is largely motivated by two basic problems:

  1. how can this be achieved most efficiently, and
  2. how can an appropriate error correcting capability be built into the code?

The theoretical framework to answer the first question was established by Claude Shannon in 1948. At that time he introduced the notion of entropy as the measure of the amount of information in a source alphabet. Shannon showed that the average length of a symbol when coded is greater than the entropy and he was able to show that this average length could be made close to the value of the entropy in a certain sense. The code that generally achieves the aims of (1) is the Huffman code.

Almost all modern computers have memories that are built from silicon chips. Alas, a stored 0 or 1 in a memory chip can spontaneously switch to what it should not be! Such errors are usually caused by alpha particles released during radioactive decay. There is no known economically feasible way to shield a computer memory against alpha particles, and as a consequence the mean time before failure for a one megabyte memory is only about 40 days. This physical fact highlights the importance of the second problem of coding theory, for error-correcting codes can cope with this failure. If the (64,57) Hamming code is designed into the architecture the mean time before failure becomes about 63 years. The Reed-Solomon codes used on compact discs are so powerful that holes up to 3mm diameter can be drilled through a disc with no loss of sound quality (or at least so it's said!).

A cipher is a secret code. The ancient Romans are said to have communicated secret messages by shaving a slave's head, inscribing the message on the scalp and then sending the slave to deliver the message after the hair had grown back. This is actually irrelevant to the course but at least adds substance to the claim that the Romans made no significant contribution to mathematics. Modern "field operatives" generally used "one-time pads" and such ciphers are essentially unbreakable provided they are used only once. In any case the course will expose the flaws of traditional ciphers and will introduce the RSA public key cryptosystem, the one which is the rage today.