Imagine the following problem: you have to communicate a long and important message to a group of friends in a noisy environment. But your friends have no way of communicating back to you. How can this be solved? Because your friends cannot communicate back to you, you cannot know which parts of the message have been heard and which are missing. One simple way to solve this problem would be to repeat the message again and again - eventually the entire message will get through. For humans this would probably be a reasonable solution, but if the entities communicating were computers we could actually solve this problem in a much more efficient way.
Since computers communicate with bits and bytes we can encode the message with something called an erasure correcting code (ECC). In this post we will simulate the performance difference between communicating by repeating a message and by using an ECC.
First we will describe the setup, but if you want to jump straight to the simulations you can use the links below:
To illustrate the benefits of an ECC we have built a small interactive simulation. In the simulation we have a bunch of cars that needs to receive a message from a transmitting tower. The message has been broken up into several data packets. As in our initial problem the cars have no way of informing the tower of which packets they have already received. In addition, the tower doesn’t know which cars are currently within its transmitting range - it is sending blindly.
Before we go to the actual simulation - here is our setup:
When running the simulations, you should be able to observe the following benefits of an ECC:
Using ECC significantly reduces the number of transmissions needed to send the message to all receivers.
With ECC we can efficiently transmit to several receivers at the same time - even if they are missing different data packets.
Using ECC, there is a high probability that all data packets sent from the tower will be useful to the cars.
Without ECC only data packets which have not been received before will be counted as useful.
To be able to see what is happening in the simulation we have added some details to the animations, these are outlined below:
Below is a detailed explanation of the simulation with a single car:
Once all packets are received, the simulation will stop and the number of transmissions used will be listed below the simulation.
Each simulation can be executed with or without ECC. Let’s get started.
Single Car Simulation
We start off with just having a single car in the simulation. Notice that each run of the simulation will be slightly different, since the transmission tower sends out the data packets in random order. The tower has no information about which packets the car has already received - therefore, random is as good as it gets.
By running the simulation a few times, you should start to notice the difference with or without ECC. By encoding the data packets the tower does not need to know the exact state of the car - pretty amazing! Another benefit of ECC comes when we add multiple cars. With ECC the same coded data packet can be useful to multiple cars - even if they are missing different packets. Let’s have a look.
Multi Car Simulation
In this simulation we have multiple receiving cars. Notice how multiple cars are sometimes in range of the tower. In such cases sending a packet which is useful for all receivers is difficult or even impossible in an uncoded setting. For instance, in a setting of 8 packets; if one car has received the packets 0, 1, 2, and 3 and another car has received packets 4, 5, 6, and 7. Then no uncoded packet would be useful for both of these receivers.
In a coded setting however, all receivers would find the sent packet useful.
As shown in the above simulation an ECC is very useful in cases with multiple receivers. Two receivers may benefit from the same transmission even if they are missing different parts of the message.
Hopefully these small simulations provided some insight into how ECC can make communication systems much more efficient. As we have shown here they offer an elegant solution to one-way and multi-user scenarios. However, they can also be leveraged in many other scenarios e.g. for low-latency communication, fault tolerance, multi path, peer-to-peer etc.
Unfortunately, and despite their significant advantages, ECCs are little known in many industries and therefore many miss out on the advantages they bring. At Steinwurf we are committed to changing this situation and by leveraging our software libraries we hope to educate and benefit all of these industries and their consumers too.
So, reach out to us if you are working in an industry where efficient communication is important, for example satellite, vehicular, broadcasting, military or similar and would like to understand better how ECC can help you!