| Paper ID | D4-S5-T4.3 |
| Paper Title |
Decoding for Optimal Expected Normalized Distance over the t-Deletion Channel |
| Authors |
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 |
| Session |
D4-S5-T4: Insertions/Deletions II |
| Chaired Session: |
Thursday, 15 July, 23:20 - 23:40 |
| Engagement Session: |
Thursday, 15 July, 23:40 - 00:00 |
| Abstract |
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.
|
