1
$\begingroup$

How do I calculate the information density of an encoding system?

This question came up as I was reading several papers about encoding data in DNA (I think I have gone through just about every major paper on encoding data in DNA after Church's). All of them mention the information density of their encoding system, which I understand to be given in units along the lines of bits or bytes per nucleotide.

From looking around on the internet and asking around in the hbar (the Physics chat) I understand the absolute basics: that one creates a model that gives the probability distribution over the possible messages in your system (say, English, or ASCII) and then from there calculate the average information density of a message using that distribution.

Unfortunately, as a complete beginner, I don't know how to do any of those things. I'd like to understand that process and in the end be able to do my own calculations. Any resources would be helpful, of course, but I was advised to ask this question here.

Tl;dr: how do you calculate the information density of a system?

$\endgroup$
  • $\begingroup$ You can start with Elements of Information Theory of Cover and Thomas, the classic textbook. $\endgroup$ – Yuval Filmus Jun 29 '17 at 1:26
  • $\begingroup$ We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. If you are not sure how to improve your question maybe we can help you in Computer Science Chat? $\endgroup$ – Raphael Jun 29 '17 at 5:08
  • $\begingroup$ @Raphael I have edited the question rather drastically, I believe it narrows the focus quite a bit; can it be reopened or does something else need to be done? $\endgroup$ – heather Jun 29 '17 at 15:19
  • $\begingroup$ I have some tips for improving your question. Tip #1: rather than asking for a resource that describes how to do X, ask how to do X. (I've edited the question accordingly.) Tip #2: do some research, and show us in the question what research you have done. What resources have you already looked at? Have you read textbooks on information theory? Tip #3: narrow down the question. Right now you say "I know I need to do X, Y, and Z, but I don't know how to do any of that". One way to make the question more focused is to pick one of those things you don't know how to do, and ask about that. $\endgroup$ – D.W. Jun 29 '17 at 17:30
  • $\begingroup$ @D.W. I have followed your advice and further improved the question. Is it okay now? If not, what else should I do? $\endgroup$ – heather Jun 29 '17 at 20:07
1
$\begingroup$

When people talk about information density in this context, they probably mean that the information density is

$$\text{density} = {n \over m}$$

where $m$ is the number of nucleotides needed to encode $n$ bits. Here the assumption is that the $n$ bits come from the uniform random distribution (i.e., all $2^n$ possibilities are equally likely). Implicitly, we are taking $n$ to be very large, or taking the limiting value of the density as $n \to \infty$.

So, think of it this way. Imagine we had $n = $ 1 million bits. How many nucleotides would the encoding scheme need, to encode those 1 million bits, on average? Call that $m$. Now divide $n$ by $m$; that's your information density.

The way to figure out the average number of nucleotides needed to encode a one-million-bit input will depend on the particular encoding scheme.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.