Systematic Decoding Video with Kodo

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.