Polar Codes For Ids Channels
summary
Coding scheme for the deletion channel uses long guard bands of zeros inserted recursively, trellis-based decoding and a bespoke trim deletion channel for analysis, achieving error ~2^{-N^{1/3}} with worst-case decoding O(N^2). Replacing per-block trellises by one big trellis improves the bound to ~2^{-sqrt(N)} at polynomial (≈N^4) cost. Extensions to insertion–deletion–substitution channels use mixed zero/one guard bands and a windowed majority test to chunk outputs, yielding an IDS error bound ≈2^{-N^{1/3}}; input Markov families can approach capacity.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:06Deletion channel coding
- 10:11Polar codes fundamentals
- 21:21Genie with guard bands
- 25:53Error probability with trellises
- 28:45Insertion deletion substitution
- 30:17Overhead and trade-offs
- 38:05Q&A
related talks
39mBroadcasting on Directed Acyclic Graphs
12msub0 Asia 2024 - Axay Sagathiya (Chainsafe)
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
01h 14mErasure Coding at Scale
15mLESS is More for I/O-Efficient Repairs in Erasure-Coded Storage
57mCoding for Interactive Communication
17mFrom Channel Assignment to Subgraph Isomorphism
27mComputation Over the Noisy Broadcast Channel with Malicious Parties