Ahsan, Kim, Nghiem, Kenny – The Genetic Code

Very interesting paper and presentation on a coding theory view of the genetic code included in our bodies in DNA, RNA, etc. I think it would have been good to include a discussion of the precise analogy between the DNA-RNA-ribosome system and the abstract communications channels that Shannon introduced (along the lines of the diagram that you used in the talk). On the coding theory side, it would also have been good to make the point that the sorts of codes you consider are a bit different from the block codes that we studied (different because you allow codewords of different lengths). Of course, the DNA code is actually a block code since all the codons are triplets(!) I would also have liked to see a bit more of your own work on the proof of Kraft’s Theorem and in some of the examples. You took most of that pretty directly from Ash’s book (properly cited, though). Otherwise, your paper is very good, and presents good discussions of both the genetics and the relevant coding theory.

Some Specific Comments

1) This statement is not very clear. In general, I think it’s better to give a precise definition of ideas like unique decipherability or the instantaneous property first, and then explain them in everyday terms (if possible). What you say later – that instantaneous implies uniquely decipherable – but not vice versa, is much clearer (to the mathematician in me at least!)

2) You say this later on, but it would be better to make the point here: The real issue for the instantaneous property is whether the decoder needs to remember what previous symbols were in order to process a new symbol, or whether the decoder can work symbol by symbol, discarding symbols as they are processed. Instantaneous codes are one where the decode needs no memory. (I think this is what you mean by “decoding step by step” here, but again, it would be better to say it more precisely.)

3) You could just say the inequality in McMillan’s Theorem is a necessary condition for unique decipherability, but not a sufficient condition.

4) I don’t have my copy of Ash’s book with me since you borrowed it, but this looks pretty much like a direct quotation of the proof there. It would be better to work this out in your own words and justify some of the things that are claimed but not explicitly shown – specifically the inequalities at the end.

5) The explanation for this point (which you “punted” on in the presentation) is that if any quantity has N distinct values (like the N = 4 possible values for one nucleotide in DNA or RNA or N = 20 possible amino acids), then you need m = log_{2}(N) bits to represent those N possible values (because 2^{m} = N and a string of m bits has 2^{m} possible values). (Of course if log_{2}(N) is not an integer, then you would have to round up to the next integer for this intuitive idea.) In any case, you say that there are log_{2}(N) bits of information in each instance of that quantity.

6) (I also mentioned this during the presentation.) This notation isn’t clear. The subscript k on the 2 is supposed to indicate the “2 from the kth word”, I guess), but it would be better to omit the subscript altogether. In this sum, all the terms are the same, since the codewords all have the same length.

7) This is true, but not quite as generally as one might think from what you say. Note that in most cases, the first two bases in the codon cannot be changed without changing the amino acide coded for. But the third base can be altered in many cases. This is a case where errors can don’t matter if they occur in a particular location, but they could matter if they occur in others. We didn’t study that sort of code at all in the course because they would be very rare in communication applications.

8) This is very interesting, because it seems to indicate a sort of “extremely dumb” approach to error control – embed the message in a lot of junk which can be changed without any effect(!) Then the probability of the errors “hitting” the important stuff is small. That’s almost the exact opposite of all the error control techniques we discussed in the course, which try to maximize the code rate (or minimize redundancy) and maximize the error-correcting capability. Why do you suppose the dumb approach is an effective technique for genetic information?

Murphy, Flynn, O’Connell – Reed-Solomon Codes and The Compact Disc Audio System

This is a reasonably good paper on the coding theory issues involved in applications like the CD audio system. I have a a few suggestions about the organization of the paper, though. For example, see comment 11 below. What you say close to the end about the physical characteristics of how information is stored on CD’s really should have come first to set up the discussion of burst error correction. Somewhere toward the beginning, it would also have been good to add a paragraph about how analog sound signals are converted to digital form for storage on a CD. Also, it would have been good to say a bit more about the actual specifications that the engineers had for this system (i.e. how long a burst error this system can correct, and so forth).

The presentation was also reasonably good, but it seemed that you could have used a bit more practice and/or imagination to put together a really effective discussion of this material. Since you volunteered to go first, I won’t penalize you for this, though.

Here are some specific comments (see markings in the paper):

Some Specific Comments

1) It would have been good to go into a bit more detail about how the CD audio system fits into the general framework of the abstract communications systems that Shannon introduced (the “block diagram” from the first day of class). Note that the “transmission” here is a bit different from other communications systems. The “channel,” for instance, is the process of manufacturing the CD and whatever happens to it in storage, handling, etc. until you play it back. One of the strengths of this framework is that it can be applied to so many different types of situations!

2) You could also say a bit more about how analog musical signals (sound vibrations of varying frequencies) are actually sampled and quantized to produce digital signals.

3) You have not explained what the cyclic burst length is, so this is not very clear. Also, you don’t use this concept later, so it could have been omitted.

4) It would be good to point out here that the t errors can be anywhere in a codeword (no assumption about locations).

5) I know what you mean here, but you have not laid out the notation you are using, and the two ways to think about the codewords of a Reed-Solomon code (as vectors with entries in F_{2^{r}} or as binary vectors of length r(2^{r} − 1)). You need to say somewhere that the codewords are c = (c_{1}, c_{2}, …, c_{2^{r}−2}), where c_{i} ∈ F_{2^{r}}, or the corresponding binary strings of length r.

6) Be more careful with the terminology! The codeword is the whole vector

(c_{1}, c_{2}, …, c_{2^{r}−2})

with entries in F_{2^{r}}. The c_{i} individually are entries in a codeword.

7) This is OK, but hardly a “formal proof” of the result you are talking about. All you need to say is something like this: We want to determine the maximum length of a burst of bit errors that will affect only t entries in a codeword, no matter where the burst starts. The “worst case” occurs if the burst starts in the last bit of one c_{i}. A burst of length > 1 + r(t − 1) starting in the last bit of some c_{i} will affect more than t of the c_{i}, so it may not be correctable. However A burst of length ≤ 1 + r(t − 1) never affects more than t of the c_{i}. Hence the maximum burst length that is always correctable is 1 + r(t − 1).

8) Of course the thing that makes this work is that, when you de-interleave, in each codeword you have a burst of length ℓ. You should say that.

9) This depends, of course, on how long the whole burst is, and also how large s is.

10) Not exactly. You don’t need to worry about those because you’re splitting the whole burst over two batches of codewords, so each batch gets a number of errors no more than the total length of the burst. It would be better to say: the total length of the burst cannot be big enough so that entries 1, 2, …, ℓ + 1 of c_{1} are all affected. Hence the upper bound on the length of the burst is ...

11) These general comments on the actual mechanics of how information is stored on a CD should probably have come much earlier in the paper. This would have been a good introductory section explaining why burst error correction is the key issue in this application – then start in with the discussion of how you define burst length, burst error correction capacity, and so forth.

Bain, Emmons, Fitzpatrick, Wiemers – Cryptography: The Art of Secret Communication

This is a reasonably good introduction to the ideas behind certain types of cryptographic systems. You have introduced the basics well and indicated in general terms how these systems work. The title of the paper is much too broad, though. After the first page or two, you are really focusing on public-key cryptosystems (RSA, and McEliece). A more descriptive title would be better. The discussion of Goppa codes could use some work, though. See comment 8 below.

Another general reaction: the text-format equations make the technical discussions very hard to read. Neat, handwritten formulas would have been much preferable to what you have here, which is unfortunately rather messy.

Some Specific Comments

1) This is imprecise and not really correct. The error control codes we have studied are designed to make communications systems reliable. Whether or not messages are “easy to read” (whatever that means) is not usually a consideration. And along the same lines, the goal of cryptography is to make communications secure (“hard to read” for unauthorized readers).

2) “Useless” is too strong, because as you say on the next page there are very simple effective attacks on Caesar ciphers. Did you mean “apparently meaningless”?

3) Also, the keyword for a Vigenere cipher can be changed regularly (or randomly) by the authorized users of the system. This gives an added level of security.

4) This discussion is OK, but there are a couple of issues that you aren’t addressing clearly. First, it would be good to lay out explicitly the differences between the situation dealt with in “classical” cryptography (e.g. Caesar and Vigenere), and public-key systems. In classical systems, you have, conceptually, a small number of authorized message senders and a small number of authorized message receivers (of course, in practice, the two groups are usually the same). These groups are usually known to each other in some way, and some secure information interchange usually goes on before messages are sent, in order to initialize the system (e.g. the choice of the shift for a Caesar cipher, or the keyword for a Vigenere cipher). For the public-key systems, the idea is that you have a small number of authorized message receivers (maybe just one), but you want anyone to be able to send secure messages to that receiver. The message senders are not known to the receiver beforehand, so while again some information needs to be exchanged to initialize the system, it should not compromise the security of the system to provide that information. This is a big difference! Before the Internet, in fact, I think it is fair to say no one had seriously considered that public-key systems would be useful in practice. Second, it is not really correct to equate non-symmetric cryptosystems with publickey cryptosystems. Public-key codes are non-symmetric, but you could certainly also design a non-symmetric classical system.

5) You should say why this is true. The reason is that

(m^{e})^{d} = m^{ed} ≡ m^{1} mod n

because of Euler’s Theorem (m^{a} ≡ m^{a′} mod n if a ≡ a′ mod (p − 1)(q − 1) = ϕ(n) (Euler ϕ-function).

6) No. It is perfectly possible to factor any integer in the ranges that are used today (p, q about 100 - 200 digits). The obstacle for the attacker is that for big p, q, there is no known fast, efficient way to factor n = p · q. The factoring could take many many years, by which time the value of deciphering is presumably lost.

7) If you don’t have access to good software for typesetting mathematical equations, neatly handwritten formulas are preferable to this sort of thing. Your equations are really hard to read!

8) The equation you are presenting here is the analog for Goppa codes of the Key Equation for decoding that we discussed for the Reed-Solomon codes. It would be good to mention that Goppa codes have such a Key Equation (that’s what makes it possible to find good, efficient decoding methods for them!) But it doesn’t make sense to say that this is the definition of the code. To say what a Goppa code is, you want to describe what the codewords are, and that is where the next equation comes in. The codewords of the Goppa code are the (d_{1}, …, d_{n}) such that

∑_{j=1}^{n} \frac{d_{j}a^{j}}{1 − a^{j}z} ≡ 0 mod g(z)

You actually say that later, but it would be better to say this first to explain what the Goppa code is.

9) At least, that’s what the users of the system hope!

10) “Permutated” is not a real word. Say “permuted”.

Basile, Johnson, Waberski – Shannon’s Theorem: A Statement and Proof.

Your paper on Shannon’s Theorem (and the oral presentation) are both really fine presentations of rather involved, technical material. You explain the main ideas well, and handle the technicalities too. Good work!

As far as the presentation of the paper goes, I have a number of comments (all more or less minor). First, two general reactions on typesetting and organizational matters: First, the formatted equations in the text are pretty good, but there are places where you have used superfluous ∗’s for multiplication and extra parentheses which make the formulas less readable. Typesetting mathematical formulas is an “art”(!) Second, when you need to refer back to a previous formula (which you do a lot here), it is good to number the equations and make the reference more specific that way. Note that this the universal way textbooks are set up – there’s a reason!

I also have a bunch of additional specific comments (see markings in paper).

Some Specific Comments

1) It would be good to mention that Chebyshev’s Theorem is valid no matter what the probability density function of x is – x could be normally distributed, or come from any other type of distribution.

2) It would be better to include the starting and final values of the summation index here to make the formula perfectly clear – |B_{ρ}(x)| = ∑_{i=0}^{ρ} \binom{n}{i}.

3) Maybe I’m just an old “fuddy-duddy” but this sort of humorous interjection rubs me the wrong way in formal mathematical writing(!)

4) Usual notation for this would be just

\frac{ρ}{n} log (\frac{ρ}{n}) = p log(p) + O(n^{−1/2})

(equals sign, not ≅). Saying f(n) = g(n) + O(n^{−1/2}) means that for all n sufficiently large,

f(n) − g(n) ≤ K \frac{1}{n^{1/2}}

for some constant K.

5) All of these summations over y should be ∑_{y∈F_{2}^{n}} (y runs over all binary words of length n – elements of F_{2}^{n}).

6) Not exactly. P^{∗}(M, n, p) ≤ expected value of P_{C} over all codes more less by definition (the minimum overall has to be no bigger than expected value). The real idea is to bound P^{∗}(M, n, p) by the expected value, then show that the expected value goes to zero as n → ∞. You said this more clearly before the proof. It’s not really necessary to say it again now.

7) You are not actually using the definition here, but rather the upper bound on the size |B_{ρ}(x)| that you derived before.