1 The problem of communication

Once upon a time there was a Country called the Phantastic Land of Magic News (PLMN).

In this Land was a big river called the "Disturbing Channel" and in this river was an Island with a castle called Big Solitude (BS). In the castle lived a King with his servants. On the other side of the river was another castle called Mostly Silence (MS). In this castle lived another King with his servants.

Both Kings were great friends and all they wanted to do was to communicate with each other. The only problem was the river called the "Disturbing Channel". It was very hard to cross the river by boat to send letters. So the King of BS tried to think of a better and safer way to communicate.

2 The Idea of Transmitting Data using Multiple Arrows

The King of Big Solitude had a soldier called "Airy Inter" who found a way to communicate. He was able to shoot an arrow over the "Disturbing Channel". His idea was to fix a small piece of paper to an arrow and use this to communicate with Mostly Silence. The problem was of course, that it was not possible to write a complete letter on such small pieces of paper, so the idea was to use a lot of arrows one after the other to transmit the news. The King was very exited about this idea and called the invention "Transmitting Data using Multiple Arrows" (TDMA).

3 The Source Coding Problem

There was one problem with the great idea of TDMA, Airy Inter could not write words. All he could do was write digits. The King called all the wise people of his castle to find a solution to the problem. One of these wise people was Samuel Cody. He knew, that everybody in the Phantastic Land of Magic News was using the same dictionary. This dictionary had exactly 10,000 entries. He suggested numbering all the words of the dictionary from 0 to 9,999. Now if the king wants to transmit news, Samuel just looks for the corresponding numbers of the words and than shouts the digits coming from the (code)book to Airy.

4 The error correction problem

After the problem with illiterate Airy was solved, both Kings started to communicate. However, the result was very disappointing. The words that Mostly Silence picked out of the codebook made no sense. For example, when BS transmitted "The King is fine" MS received "The dog is blue". It took quite a while for the wise people to find out what was wrong. The problem was again with Airy. He was sitting next to the "Disturbing Channel" when Samuel was shouting the words to him. The result was that every 5th to 10th number was misunderstood. Therefore instead of transmitting 3907 (King) Airy transmitted 3007 (Dog).

Again the wise people discussed a lot how to overcome this problem. The only solution was to transmit more than the 4 digits.

The first suggestion was to shout each number twice. However, this did not help much. If Airy was misunderstanding a number it was possible to see that one of the two numbers was wrong, but which one?

So doubling the numbers was not enough. The next suggestion was to transmit the number three times. The majority should then be taken:

3907 -> 333999000777 (Airy)-> 333909000377 -> 3907

This works, but it costs 12 instead of 4 digits. Furthermore there are problems if two errors are to close together, since up to three of the twelve digits could be wrong.

3907 -> 333999000777 (Airy)-> 333090000777 -> 3007

So the King was not very satisfied with this solution.

5 The idea of Charles Cody

Samuel Cody had a brother named Charles Cody. He had a better idea to correct the errors (although it took a while until everybody understood his trick). He suggested to doing mathematical operations on the digit string. Every digit was related to the two previous digits in a way that gave two code digits for every digit in the original string. His recipe worked as follows:

Example:

When Samuel encoded 3907 he first added zeros. This gave 00390700

Then the arithmetic begins. By the way, Samuel used quite a bit of scratch paper to code the message.

3+0 = 3, 3+0 = 3 combining the digits gave 33

9+0 = 9, 9+3 = 2 -> 92

0+3 = 3, 0+9 = 9 -> 39

7+9 = 6, 7+0 = 7 -> 67

0+0 = 0, 0+7 = 7 -> 07

0+7 = 0, 0+0 = 0 -> 70

So the code for King (or 3907) was shouted to Airy as 339239670770

Unfortunately it is more difficult to extract the original sequence from the transmitted sequence. However, it was known, that the string starts and ends with two zeroes. These are anchor points. The rest must be tested by the following: make a guess for the next number of the code and calculate the corresponding pair of two shouted numbers; compare these to the received sequence:

The correction of errors was really boring but a girl in MS called Vivian Terby found a good scheme to do it.

For each pair of two successive digits that Airy received, she drew a diagram with all the possible digits that Samuel could have shouted. Each possible sequence of digits can now be drawn as a "path" along this trellis. The path consists of many "steps" between two numbers from the code. To each step a penalty is given: a single penalty if one digit in the received pair does not correspond to the number in the original code, and a double penalty if both digits do not correspond. Of course if both numbers are consistent one number from the code penalty is 0.

Moreover, the path must end with two zeroes, otherwise it is certainly incorrect and should therefore be discarded. For each path, the penalties of each step are added together. The path with the lowest penalty is selected to give the most likely codeword that Samuel had shouted.

If two paths with different penalties reach the same number (or node), the path with the higher penalty is deleted.

Example with one error:

The method of Charles Cody and Vivian Terby also worked for three errors.

6 The Problem of "always tired" Airy

After the problem of the errors caused by Airy was solved, communication was tried again. It worked much better now. Nevertheless some words were still senseless. Obviously some errors still could not be corrected by the trick of Charles and Vivian.

After a lot of examination the reason was found. Since he was shooting arrows all the time, Airy was getting very tired and every now and then he fell asleep. He was fading away. Owing to this fading problem, three or more errors occurred one after the other, rather than distributed every fifth time. Such errors could not be recovered.

A solution was soon found. Instead of shouting the digits down to Airy right away, they were first written into a table row by row. After the table was filled up, the digits were shouted to Airy column by column.

Example:

Input Sequence: 64 92 30 12 55 82, 07 83 52 57 24 63, 90 11 38 54 83 23

Output Sequence: 61 05 95 42 77 04, 95 82 18 25 34 13, 38 56 32 02 23 83

If the interleaved output sequence had contained errors due to "fading" it could have looked as follows:

61 05 95 42 EE EE, 95 82 18 25 34 1E, EE 56 32 02 23 83

Sequence after deinterleaving:

64 92 E0 12 55 E2, 0E 83 E2 5E 24 52, 9E 11 38 5E 8E 23

The trick of interleaving distributed the "fading" errors. These distributed errors could now be handled by the error correction trick of Charles and Vivian.

7 How the "Disturbing Channel" spoiled the transmission

After all the effort that had been necessary so far, the worst problem was still to come.

Owing to the long sequences that had to be attached to the arrows, the arrows became too slow. Especially if the wind was blowing from the opposite direction, the arrows would fall into the river "Disturbing Channel". Fortunately they fell into the channel very close to the bank, so it was easy to collect them. However, the pieces of paper always became wet and the ink started to wash away. After the ink dried, a sequence of numbers looked like this:

Now nearly everybody gave up. Obviously, this disturbance could not be recovered.

8 The Idea of Liza Equally

But Vivian Terby had a friend called Liza Equally. She could not believe that this should be the end of the great method of communication called TDMA.

She looked at the destroyed sequences again and again and discovered that the digits were disturbed heavily, but they were all disturbed in the same manner. To find out how they were disturbed, she asked Airy to transmit some sequences that had some free space in the middle with a small dot in the center.

This dot showed how the water of the "Disturbing Channel" was scattering the ink on the paper. The single dot of the original sequence became thicker and was washed away several times to different locations, so that in the received sequence up to 6 dots could be found lying in an irregular in a row.

Now Liza could tell how the digits before and after the dot had been disturbed.

9 The trick of Liza and Vivian

Liza discussed her finding with Vivian, and Vivian wondered if the trick that they used to correct the errors of Airy could also be used for this problem. The trick was, if you cannot recover the received sequence, guess a sequence, disturb it using the traces of the dots and compare it with the received sequence. In other words, find the maximum likelihood sequence.

This job was much more time consuming than the recovery of digit errors. It worked in the following manner:

First try all ten digits, disturb them according to the received pattern of dots, and compare them with the first part of the received sequence.

Take the most likely digit. If it is uncertain try the next steps with more than one hypothesis.

Take the first hypothesis and add all possible digits to it. Again compare it with the received sequence.

After this second step, the first digit is fixed and probably also the second. If not, try more than one hypothesis for the second digit.

Then continue as in the second step:

10 Summary

Using the trick of Liza and Vivian it was really possible to communicate using the "Transmission of Data using Multiple Arrows", TDMA. All the activities could be summarized as follows:

Big Solitude and Mostly Silence communicated for a short time in this way. But after a while, everybody, especially Vivian Terby and Liza Equally got very tired of all the necessary estimations. So they stopped the TDMA system, and Big Solitude and Mostly Silence remained what they were.

But fortunately, the grand ideas of the TDMA system were not forgotten. Some centuries later, engineers found a miraculous tiny machine that could do all the tasks described above, the

Digital Baseband Processor

And this is the reason that today BS and MS can communicate in the PLNM.

And, if not a different system called "Communicating Data using Millions of very tiny Arrows" (or CDMA) will take over, they will still communicate.

THE END