• Welcome
  • News
  • Blog
  • Technology
  • Research
  • About

Systematic Decoding Video with Kodo

April 20, 2016 - Morten Pedersen

The below video illustrates systematic decoding of data, in this case a bitmap image. The left side is a view of the “received” data during the decoding, and the right side is a view of the decoding matrix. In this case we are using Erasure Correcting Codes (ECC).

Details

A typical use-case for ECC is to repair packet loss occurring when sending data through a computer network. A common approach to ECC is to create linear equations describing the original data, this process is called “encoding”. A receiver then collect equations and can solve the equation system to obtain the original data, this process is called “decoding”.

In this example we mimic the sending of a picture. We will use an approach called systematic coding, which simply refers to the fact that we first send all the original data (the systematic phase) and afterwards encode and send redundant data which consists of equations describing the original data (the redundancy phase) - also called coded data. This is typically useful since if there are no errors we don’t unnecassarily use computations to encode at the sender and decode at the receiver.

The visualization is divided into two sections. The left-side display the picture as it is being received. The right-side show the decoding matrix (all the equations describing the data). The matrix is visualized by showing all non-zero values as white dots and all zero values as black dots. The data is decoded once the identity matrix is obtained on the right-side i.e. all ones (white) on the diagonal of the matrix and otherwise zeros (black).

In the systematic phase the horizontal lines of the picture is filled one by one, where each line of the picture represents a packet on the network. When a black line appears in the picture that means that the corresponding packet was lost. You should be able to notice a white line appearing in the diagonal of the right most matrix.

In the redundancy phase coded data is used to fill the gaps in the picture. This is done by “decoding” the coded data using Gaussian elimination. Essentially the inverse operations performed during encoding is performed. Once enough equations have been received to solve the matrix the original data will be fully decoded and the picture have been successfully transmitted.

Share this blog:

Recent Blog Posts

  • 22 Jan 2021 | Hardware Acceleration

    Erasure correcting codes (ECC/FEC) provide elegant solutions to many networking problems. Whether you want to build reliable super low latency applications or efficiently send data to 1000s of devices simultaneously, ECC/FEC can provide compelling advantages. However, one common concern when integrating an ECC/FEC algorithm is often how big is the computational overhead?

  • 07 Jan 2021 | Multicast ECC/FEC

    A typical use-case for broadcast/multicast is when we need to transmit the same data (e.g. a file) to multiple receivers simultaneously. The use of multicast/broadcast means that multiple devices may benefit from a single transmission increasing the efficiency of the system. However, a challenge in such systems is how to efficiently deal with packet loss. In the following we will show how using an erasure correcting code/Forward Erasure correction (ECC/FEC) can lead to significant bandwidth savings over a traditional retransmission based system.

  • 30 Oct 2020 | Content-Aware ECC/FEC

    In some of our previous posts we have discussed some of the challenges when implementing a reliability scheme targeting low latency applications. For example in Coding for low latency (block codes) we discuss how large block codes such as RaptorQ or LDPC can be problematic in low latency communication. Similarly in In our post What about the latency, stupid we discuss the latency penalty of using a retransmission based reliability scheme. In this post we will consider what can happen when we want to protect the traffic coming from a latency sensitive application where the structure of the content is important.

  • Twitter
  • Facebook
  • Linkedin
  • Mail
  • Github
  • Youtube
Design: TEMPLATED