M.Sc Thesis

M.Sc StudentAdler Nitzan
SubjectBurst-Erasure Correcting Codes with Optimal Average Delay
DepartmentDepartment of Electrical and Computer Engineering
Supervisor ASSOCIATE PROF. Yuval Cassuto
Full Thesis textFull thesis text - English Version


The majority of research in the field of information theory is based on the traditional tradeoff between code rate and error tolerance. A third factor, the decoding delay, which is the time between a packet's erasure and its full reconstruction, is much less studied. When discussing time-critical communications, the decoding delay becomes a much more significant factor that must be taken into account. In this work we propose and study low-delay codes that span a triple tradeoff between these three parameters: code rate, error tolerance and decoding delay.

Previous works have concentrated on the constant-delay scenario, where all erased packets need to exhibit the same decoding delay. In our work we consider a new scenario of heterogeneous delay, where the principal objective is to minimize the average delay across the erased packets in a burst. This new model is motivated by communications in sense and control networks, where the received data is also processed.  Thus, the temporal accuracy of the process is determined by the number of currently known packets.

In our work we derive lower bounds for the average delay, and show that they are strictly lower than the constant-delay bounds for all rates, except the single rate point 0.5, where they are equal.

After providing lower bounds for the average delay, constructions with optimal average delays are proposed for the entire range of code rates. The construction for rates under 0.5 achieves optimality for every erasure instance, while the constructions for rates above 0.5 are optimal for an infinite number, but not all, of the erasure instances. Nevertheless, the average delay obtained for the suboptimal erasure instances is significantly lower than the corresponding constant delay.

Finally, we show natural applications and matching heterogeneous-delay constructions. We show an application where packets with different urgency levels require a heterogeneous-delay construction that prioritizes the recovery of the more urgent packets. The scenario we choose is of packets with a pre-defined significance hierarchy. Our suggested construction enables a faster recovery of packets with higher significance levels.

Another model discussed in the applications chapter deals with packets whose urgency levels are defined by their freshness, meaning that in packet reconstruction after a burst erasure event the more recent packets are more urgent than the older ones. A suitable construction is presented for models with such property.