ECCC-Report TR24-091https://eccc.weizmann.ac.il/report/2024/091Comments and Revisions published for TR24-091en-usSun, 26 May 2024 18:06:50 +0300
Revision 1
| When Do Low-Rate Concatenated Codes Approach The Gilbert--Varshamov Bound? |
Dean Doron,
Mary Wootters,
Jonathan Mosheiff
https://eccc.weizmann.ac.il/report/2024/091#revision1The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $\varepsilon^2$ has relative distance at least $\frac{1}{2} - O(\varepsilon)$ 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 $\mathcal{C}_{\mathrm{out}}$ over a large alphabet, and concatenate that with a small binary random linear code $\mathcal{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 $\mathcal{C}_{\mathrm{in}}$ can lie on the GV bound; and if so what conditions on $\mathcal{C}_{\mathrm{out}}$ are sufficient for this.
We show that first, there do exist linear outer codes $\mathcal{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 $\mathcal{C}_{\mathrm{out}}$, so that if $\mathcal{C}_{\mathrm{out}}$ satisfies these, $\mathcal{C}_{\mathrm{out}}\circ \mathcal{C}_{\mathrm{in}}$ will likely lie on the GV bound. We hope that these conditions may inspire future work towards constructing explicit codes $\mathcal{C}_{\mathrm{out}}$.Sun, 26 May 2024 18:06:50 +0300https://eccc.weizmann.ac.il/report/2024/091#revision1
Paper TR24-091
| When Do Low-Rate Concatenated Codes Approach The Gilbert--Varshamov Bound? |
Dean Doron,
Mary Wootters,
Jonathan Mosheiff
https://eccc.weizmann.ac.il/report/2024/091The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $\varepsilon^2$ has relative distance at least $\frac{1}{2} - O(\varepsilon)$ 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 $\mathcal{C}_{\mathrm{out}}$ over a large alphabet, and concatenate that with a small binary random linear code $\mathcal{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 $\mathcal{C}_{\mathrm{in}}$ can lie on the GV bound; and if so what conditions on $\mathcal{C}_{\mathrm{out}}$ are sufficient for this.
We show that first, there do exist linear outer codes $\mathcal{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 $\mathcal{C}_{\mathrm{out}}$, so that if $\cout$ satisfies these, $\mathcal{C}_{\mathrm{out}}\circ \mathcal{C}_{\mathrm{in}}$ will likely lie on the GV bound. We hope that these conditions may inspire future work towards constructing explicit codes $\mathcal{C}_{\mathrm{out}}$.Tue, 14 May 2024 15:21:40 +0300https://eccc.weizmann.ac.il/report/2024/091