Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2202.00240 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909510902218752 |
|---|---|
| author | Rao, Anup Sprumont, Oscar |
| author_facet | Rao, Anup Sprumont, Oscar |
| contents | We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive codes and Reed-Muller codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular.
1) We give a tight bound on the weight distribution of every transitive linear code $C \subseteq \mathbb{F}_2^N$: $\Pr_{c \in C}[|c| = αN] \leq 2^{-(1-h(α)) \mathsf{dim}(C)}$.
2) We give a criterion that certifies that a linear code $C$ can be decoded on the binary symmetric channel. Let $K_s(x)$ denote the Krawtchouk polynomial of degree $s$, and let $C^\perp$ denote the dual code of $C$. We show that bounds on $\mathbb{E}_{c \in C^{\perp}}[ K_{εN}(|c|)^2]$ imply that $C$ recovers from errors on the binary symmetric channel with parameter $ε$. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $C^\perp$ is sufficiently close to the binomial distribution in some interval around $\frac{N}{2}$, $C$ is resilient to $ε$-errors.
3) We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for Reed-Muller codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for Reed-Muller codes achieve the information-theoretic optimal trade-off between rate and list size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_00240 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Criterion for Decoding on the BSC Rao, Anup Sprumont, Oscar Information Theory We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive codes and Reed-Muller codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular. 1) We give a tight bound on the weight distribution of every transitive linear code $C \subseteq \mathbb{F}_2^N$: $\Pr_{c \in C}[|c| = αN] \leq 2^{-(1-h(α)) \mathsf{dim}(C)}$. 2) We give a criterion that certifies that a linear code $C$ can be decoded on the binary symmetric channel. Let $K_s(x)$ denote the Krawtchouk polynomial of degree $s$, and let $C^\perp$ denote the dual code of $C$. We show that bounds on $\mathbb{E}_{c \in C^{\perp}}[ K_{εN}(|c|)^2]$ imply that $C$ recovers from errors on the binary symmetric channel with parameter $ε$. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $C^\perp$ is sufficiently close to the binomial distribution in some interval around $\frac{N}{2}$, $C$ is resilient to $ε$-errors. 3) We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for Reed-Muller codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for Reed-Muller codes achieve the information-theoretic optimal trade-off between rate and list size. |
| title | A Criterion for Decoding on the BSC |
| topic | Information Theory |
| url | https://arxiv.org/abs/2202.00240 |