This site contains announcements and additional material for CSC310.

• 12 Apr 2003
  Supplemental (but interesting!) material:
  - The famous Reed-Solomon error correction codes, used in so many systems such as storage devices (tape, hard drives, Compact Disc, DVD, barcodes), communications (satellite, cell phones, high-speed modems/DSL, digital television), are overviewed in SIAM News, Volume 26, No. 1, January 1993 (also available here). Another introductory resource with a good explanation and useful links is available here.
  - If you are curious about the ubiquitous Universal Product Codes (the UPC bar codes), a nice explanation is available here.
• 15 Mar 2003
  The example of a 3-repetition code on a 3-extension of the BSC is presented here.
• 18 Feb 2003
  A good introductory survey about several data compression methods, appeared in ACM Computing Surveys, Volume 19, Issue 3 (September 1987) is available at NEC's CiteSeer. Alternately, you may download the paper from one of the authors' web site, in compressed Postscript and in HTML.
  Among other things, the survey covers the following codings: Shannon-Fano, static and dynamic Huffman, Lempel-Ziv, and arithmetic. If you want to read further, the references point you to the original papers.
  I wish to point out an inaccuracy: the Lempel-Ziv coding described in the paper is actually the Lempel-Ziv-Welch coding (1984), derived from Lempel-Ziv (1978). This is not the original Lempel-Ziv (1977) coding.
• 10 Feb 2003
  The official answers to the assignment 1 are here. The marking scheme is here.
• 17 Jan 2003
  - The entire story of the roulette game is here.
  - An interesting question was asked in today's tutorial.
  Question: Given a uniquely-decipherable, non-instantaneous code, how many bits from the incoming message are necessary to decode the next symbol?
  Example: Given the code (a=00, b=10, c=11, d=110) and the message 110010, the first 4 bits are necessary to decide that the first symbol is c. It is not enough to preload only the first 3 bits, because it cannot be decided whether they correspond to c (followed by another code), or to d.
  Answer: It is not possible to find the minimum number of bits required in the general case. Assuming the same example code, the message 110000000000000010 is decomposed as 11.00.00.00.00.00.00.00.10, while the message 1100000000000000010 (with an extra 0 in the middle) is decomposed as 110.00.00.00.00.00.00.00.10. It is not possible to decide whether the first symbol is c or d until all the 0's are read and the last 1 is reached.
  Conclusion: Remeber the consequence of the Kraft-McMillan inequality: a uniquely-decipherable code exists if and only if an instantaneous code exists, so there is no good reason to use non-instantaneous codes in practice.

---

Cosmin Truta
Last updated: 12 Apr 2003