Communication without noise

Communicating information is perhaps the highlight of the 21st century; the obvious example is the boom in internet and smartphone use in the last 20 years or so; everything is well connected and messages get sent within a fraction of a second. A less obvious example of communicating information is through reading information stored in physical object prone to damage. For example, a CD could be scratched slightly but still, all the relevant information can be recovered properly. 

How did we arrive at such a resilient communication? Let's take communicating with your partner as an example. Without sounding too much like a family consultant, the key here is to send your message as clearly as possible to avoid misunderstanding. Let's say you are an intelligent being who can formulate a proper and grammatically correct sentence, and you wanted to say "I want pizza". You could say the sentence face to face, and hopefully, your crave for pizza would be communicated properly. However, there's a chance that you mumbled the words; or your partner was thinking about something else; or you were talking in a busy street or anything else that stopped your message from getting across clearly. We shall call anything stopping effective communication Noise. 

Now, you might be upset that your partner doesn't know that you want pizza, but you decided to repeat yourself three or more times, to make sure that you get your message across, or perhaps you decided to speak louder. These can be effective methods, but its what I call brute-force methods to compact noise.

Going digital

Let's step away from family matters now and back to technology. As you might be aware, almost all digital communication happen through encoding any message (e.g. text, image, music, ...) into zeros and one (Link here to know more text encoding), then sending these message through a medium (e.g. electrical wires or radio waves) and decoding these messages from the receiving end back to its original form, whether that is a picture or a text message. That medium will almost certainly contain some noise, and the effect of that noise is literally flipping some of these zeros and ones or eradicating them completely through the transmission, as illustrated below.

Schematic illustrating the flow of digital information

Using the brute-force method mentioned previously, one could compact noise by simply adding more energy to the sender. This could help slightly, but adding energy to the source comes with its own drawbacks making it more expensive to send a message, let alone amplifying the internal noise in your machine.

Another method we mentioned to compact noise was to simply repeat yourself. I know it is quite tiresome to say " I want pizza I want pizza I want ...." every time you want to express yourself, but it is a rather good starting point to achieve resilient digital communication, let's take a simple example to illustrate why. Imagine wanting to send the number 7 using a telegraphy machine. A 4-bit message is more than enough to send the number 7 across or sending the binary sequence (0111). Using morse code for communication, let's make dots represent zeros and dashes represent one:

 

The noise could disturb the message, say that the receiver is not sure whether the second digit was dot or a dash. Well then, let's try repeating ourselves three times by sending the digit 7 three times:

The receiver could simply compare each digit with the received repetition, digit by digit, and take for granted the ones that get repeated two or three times. While this seems to solve the problem of noise, there are major drawbacks; what if the same digit is unknown across all repetitions? And it is also very impractical. The length of the message increased from 4 digits to 12 digits, 2/3 of the message is reserved for redundancy, while only 1/3 contains the actual information we want to send.

Shannon's insights 

Claude Shannon juggling

In 1948, Claude Shannon published what turns out to be a very influential paper in digital communication, titled A Mathematical Theory of Communication. The paper had a rather unusual take on communication and the influence of noise, it attempted to quantify numerically the amount of useful information sent in a message. Most previous attempts to compact noise were isolating context from the message, while Shannon did exactly the opposite. For example, if you're sending an English text, there are some links between the letters and their frequency of occurrence in sentences, For example, you'd expect the letter 'E' to occur more frequently in a sentence relative to, say, the letter 'Q'. Speaking of the letter 'Q', you'd expect 'Q' to be followed by 'U', and so on.
In his paper, Shannon deduced mathematically that there exists a way of coding information that maximises the bit rate communication and reduces the noise to a very small fraction. What made Shannon a rockstar and the Godfather of the informatics age is that he didn't explicitly say what the right coding scheme was to achieve a high bit rate! He just proved it mathematically that such a coding scheme exists, and deduced a theoretical limit on the maximum amount of information that could be sent while maintaining minimum noise.

That paper excited the scientific community, many attempts were made to try to achieve the Shannon limit. Fast-forward 14 years since the publication of Shannon's paper and one coding scheme almost achieved Shannon's limit, called a low-density parity-check code.

Parity checks

It's better to explain what parity checks are before explaining the low-density parity-check code. The idea of parity checks was first conceptualised by Richard Hamming, an American mathematician who shared an office with Shannon at Bell Labs –hardly a coincidence? The idea behind parity checks is to use a smaller number of bits as redundancy to check the consistency of the code, these redundant bits are called parity bits. More concretely, one could simply count the number of 1's in the message and assigning a zero parity-bit if the count is even, commonly known as an even parity check.

The best way to explain parity checks is by giving an example using the traditional Hamming encoding technique. Again, we will stick to a 4-bit message for simplicity. Say we want to send the number "5" across a channel (0101 in binary). If you have been reading carefully, you know that in order to protect the message from noise during transmission, we have to add some redundant code in the message. Hamming encoding techniques gives the exact extra number codes needed by the following formula:

                                                     2^r ≥ m + r + 1 

           where, r = redundant bit, m = message bit

where we want to find the minimum "r" that satisfies the previous inequality, in our 4-bit message, r=3. The position of these redundant bits (or more accurately, parity bits) is also crucial, they are arranged as 2 to the power of the number of parity-bits. So if we calculated that the parity-bits to be 3, that means the placement of these bits is given by the following rule, assuming r=3:

                                                      r1 = 2^(r-3) = 1

                                                       r2 = 2^(r-2) = 2

                                                       r3 = 2^(r-1) = 4

                                

in words, the first parity bit should be first in the message, the second parity-bit should be placed second, and the third parity-bit should be the fourth. Now, our message (remember, we are sending the number "5" in binary) to be sent is in the following form:

        

                                            r1  r2  0  r3  1  0  1

We are yet to determine the values of these parity-bits, but first, we must understand what role they play in the message. Each parity-bit is responsible for a number of message-bits, by responsible I mean counting the number of 1's connected to that parity-bit and changing its own value to 0 if the count is even and 1 otherwise. They are connected by the following rules:

•  Parity bit 1 covers all the bits positions whose binary representation includes a 1 in the least significant position (1, 3, 5, 7, 9, 11, etc).
•  Parity bit 2 covers all the bits positions whose binary representation includes a 1 in the second position from the least significant bit (2, 3, 6, 7, 10, 11, etc).
• Parity bit 3 covers all the bits positions whose binary representation includes a 1 in the third position from the least significant bit (4–7, 12–15, 20–23, etc).

We could show graphically how the parity-bits are connected in our example:

The reason for that specific connection will become apparent once we decode the message. For now, figuring out the values of these bits becomes easy once you know the connections; just count the number of the bits connected to that parity-bit and output a zero if the number of 1's is even and zero otherwise; that gives r1=0; r2=1 and r3=0. Then the whole message sent will be:

                    0  1  0  0  1  0  1

Decoding Hamming code

The receiver receives the 7-bit mentioned earlier and knows that it is actually a 4-bit message with three parity-bits. What the receiver doesn't know is whether any of these bits got altered during transmission, but that's ok because there's some routine work to do to check the validity of the code. Simply take each parity-bit and check whether the count of 1's is even or odd, and compare that with the value of the parity-bit. The previous operation is equivalent to performing an "Exclusive-or" operation to all the bits connected to a single parity-bit, which makes coding and decoding Hamming code in computer software is rather trivial using XOR functions. For more details on how to implement Hamming code in an algorithm, visit this link.

Assume that during transmission of the previous message, one digit got altered and the receiver gets the following:

                                                

                                                                                          1          2          3           4           5           6          7

                                   0  1  0  0  1  0  0

                        r1   r2   m1   r3   m2    m3   m4

 

Going through the routine checks:

• Parity-bit 1 (r1) has a value of zero, and it is connected to bits (3, 5, 7) and their values are (0, 1, 0) respectively. That's an odd number of 1's and that doesn't agree with the value of the parity-bit, so we know there's something fishy here but not quite sure where.
• Parity-bit 2 (r2) has a value of one, and it is connected to bits (3, 6, 7) and their values are (0, 0, 0) respectively. No ones are counted so we know that some number here has changed since the parity-bit value of one does not match the count.
• Parity-bit 3 (r3) has a value of zero, and it is connected to bits (5, 6, 7) and their values are (1, 0, 0) respectively. Thus we expected a value of 1 for the parity-bit instead of zero.

Going through the bits, we know that there is something wrong since the parity-bits don't match the count of even ones. Since all parity-bits don't match up with the count, we can confidently deduce that bit-7 has been altered, because it is the only bit that is connected to all parity-bits.

Hopefully, I have communicated how elegant Hamming codes are, and how a rather simple encoding solves a big problem. However, the state of the art in encoding is the low-density parity-check code, which you can think of as a variation of Hamming code, but that deserves its own blog. 

I have coded a simple interactive Hamming encoding for fun below, the source code of it is available here.

            

Select Digit

Select digit: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Binary representation:

Encoded message:

Received message:

Error position:

Hamming corrected message: