Supervision : Michèle SORIA, Laurent FREREBEAU, Hervé DELPEYRAT

Co-supervision : BUI-XUAN Binh-Minh

Streaming unidirectional auto-correcting codes through ELIPS-SD diods

Reliably transmitting information over a transmission channel is a recurrent problem in Informatic Sciences. Whatever may be the channel used to transmit information, we automatically observe erasure of this information, or pure loss. Different solutions can be used to solve this problem, using forward error correction codes is one of them.
In this thesis, we study a corrector code developped in 2014 and 2015 for Thales society during my second year of master of apprenticeship. It is currently used to ensure the reliability of a transmission based on the UDP protocole, and passing by a network diode, Elips-SD. Elip-SD is an optical diode that can be plugged on an optical fiber to physically ensure that the transmission is unidirectional. The main usecase of such a diode is to enable supervising a critical site, while ensuring that no information can be transmitted to this site. At the opposite, another usecase is the transmission from one or multiple unsecured emitters to one secured receiver who wants to ensure that no information can be robbed.
The corrector code that we present is a linear corrector code for the binary erasure channel using packets, that obtained the NATO certification from the DGA ("Direction Générale de Armées" in French). We named it Fauxtraut, for "Fast algorithm using Xor to repair altered unidirectional transmissions". In order to study this code, presenting how it works, its performance and the modifications we added during this thesis, we first establish a state of the art of forward error correction, focusing on non-MDS linear codes such as LDPC codes. Then we present Fauxtraut behavior, and analyse it theorically and with simulations. Finally, we present different versions of this code that were developped during this thesis, leading to other usecases such as transmitting reliable information that can be altered instead of being erased, or on a bidirectionnal channel, such as the H-ARQ protocole, and different results on the number of cycles in particular graphs.
In the last part, we present results that we obtained during this thesis and that finally lead to an article in the Technical Computer Science. It concerns a non-polynomial problema of Graphs theorie : maximum matching in temporal graphs. In this article, we propose two algorithms with polynomial complexity : a 2-approximation algorithm and a kernelisation algorithm for this problema.

2019-2020 Publications

• 2020
  • J. Baste, B.‑M. Bui‑Xuan, A. Roux : “Temporal Matching”, Theoretical Computer Science, (Elsevier) (2020)
• 2019
  • A. Roux : “Streaming unidirectional auto-correcting codes through ELIPS-SD diods”, thesis, phd defence 12/02/2019, supervision Soria, Michèle Frerebeau, Laurent Delpeyrat, Hervé, co-supervision : Bui-xuan, Binh-Minh (2019)