When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916318079352832 |
|---|---|
| author | Doron, Dean Mosheiff, Jonathan Wootters, Mary |
| author_facet | Doron, Dean Mosheiff, Jonathan Wootters, Mary |
| contents | The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $ε^2$ has relative distance at least $\frac{1}{2} - O(ε)$ with high probability. However, it is a major challenge to construct explicit codes with similar parameters.
One hope to derandomize the Gilbert--Varshamov construction is with code concatenation: We begin with a (hopefully explicit) outer code ${C}_\mathrm{out}$ over a large alphabet, and concatenate that with a small binary random linear code ${C}_\mathrm{in}$. It is known that when we use independent small codes for each coordinate, then the result lies on the GV bound with high probability, but this still uses a lot of randomness. In this paper, we consider the question of whether code concatenation with a single random linear inner code ${C}_\mathrm{in}$ can lie on the GV bound; and if so what conditions on ${C}_\mathrm{out}$ are sufficient for this.
We show that first, there do exist linear outer codes ${C}_\mathrm{out}$ that are "good" for concatenation in this sense (in fact, most linear codes codes are good). We also provide two sufficient conditions for ${C}_\mathrm{out}$, so that if ${C}_\mathrm{out}$ satisfies these, ${C}_\mathrm{out}\circ {C}_\mathrm{in}$ will likely lie on the GV bound. We hope that these conditions may inspire future work towards constructing explicit codes ${C}_\mathrm{out}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_08584 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? Doron, Dean Mosheiff, Jonathan Wootters, Mary Information Theory Computational Complexity The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $ε^2$ has relative distance at least $\frac{1}{2} - O(ε)$ with high probability. However, it is a major challenge to construct explicit codes with similar parameters. One hope to derandomize the Gilbert--Varshamov construction is with code concatenation: We begin with a (hopefully explicit) outer code ${C}_\mathrm{out}$ over a large alphabet, and concatenate that with a small binary random linear code ${C}_\mathrm{in}$. It is known that when we use independent small codes for each coordinate, then the result lies on the GV bound with high probability, but this still uses a lot of randomness. In this paper, we consider the question of whether code concatenation with a single random linear inner code ${C}_\mathrm{in}$ can lie on the GV bound; and if so what conditions on ${C}_\mathrm{out}$ are sufficient for this. We show that first, there do exist linear outer codes ${C}_\mathrm{out}$ that are "good" for concatenation in this sense (in fact, most linear codes codes are good). We also provide two sufficient conditions for ${C}_\mathrm{out}$, so that if ${C}_\mathrm{out}$ satisfies these, ${C}_\mathrm{out}\circ {C}_\mathrm{in}$ will likely lie on the GV bound. We hope that these conditions may inspire future work towards constructing explicit codes ${C}_\mathrm{out}$. |
| title | When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? |
| topic | Information Theory Computational Complexity |
| url | https://arxiv.org/abs/2405.08584 |