Name
Abstract | ||
|---|---|---|
In this paper, we propose a polar coding scheme for binary deletion channels. We also present an implementation of low-complexity polar SC decoder for deletion channels. The modified decoding algorithm requires only O(d(2)n log n) computational complexity, where d and n respectively denote the number of deletions and the code-length. This is a huge improvement over naive implementation of the SC decoder for channels with deletion with O(n(d+1) log n) computation complexity that was recently proposed by Thomas et al. in [21], and is based on running individual instances of SC decoder for every deletion pattern while treating the deleted symbols as erasures.We also prove polarization theorems for the polar bit-channels in presence of deletions when d = o(n), which implies that our coding scheme is capable of achieving the symmetric information rate for this concatenated scheme with diminishing error probabilities as n becomes large. The same framework, in both theory and implementation, is also applicable to channels formed as a concatenation between binary discrete memoryless channels and the d-deletion channel, which marks our coding scheme as the first family of practical codes that is capable of decoding noisy channels with deletions at the optimal code rate. |
Year | Venue | Field |
|---|---|---|
2018 | 2018 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) | Discrete mathematics,Binary logarithm,Combinatorics,Code rate,Computer science,Communication channel,Coding (social sciences),Concatenation,Decoding methods,Binary number,Computational complexity theory |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kuangda Tian | 1 | 7 | 2.81 |
| Arman Fazeli | 2 | 53 | 9.83 |
| Alexander Vardy | 3 | 2736 | 272.53 |