| Decoding for Optimal Expected Normalized Distance over the t-Deletion Channel
|Daniella Bar-Lev, Yotam Gershon, Technion — Israel Institute of Technology, Israel; Omer Sabary, University of California San Diego, United States; Eitan Yaakobi, Technion — Israel Institute of Technology, Israel
|D4-S5-T4: Insertions/Deletions II
|Thursday, 15 July, 23:20 - 23:40
|Thursday, 15 July, 23:40 - 00:00
This paper studies optimal decoding for a special case of the deletion channel, referred by the t-deletion channel, which deletes exactly t symbols of the transmitted word uniformly at random. The goal of the paper is to understand how such an optimal decoder operates in order to minimize the expected normalized distance. A full characterization of a decoder for this setup is given for a channel that deletes one or two symbols. For t=1 it is shown that when the code is the entire space, the decoder is the lazy decoder which simply returns the channel output. Similarly, for t=2 it is shown that the decoder acts as the lazy decoder in almost all cases and when the longest run is significantly long, it prolongs the longest run by one symbol.