Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-091 | 26th May 2024 18:06

When Do Low-Rate Concatenated Codes Approach The Gilbert--Varshamov Bound?

RSS-Feed




Revision #1
Authors: Dean Doron, Jonathan Mosheiff, Mary Wootters
Accepted on: 26th May 2024 18:06
Downloads: 474
Keywords: 


Abstract:

The 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}}.



Changes to previous version:

Added a discussion about [BJT'01]


Paper:

TR24-091 | 14th May 2024 15:14

When Do Low-Rate Concatenated Codes Approach The Gilbert--Varshamov Bound?





TR24-091
Authors: Dean Doron, Jonathan Mosheiff, Mary Wootters
Publication: 14th May 2024 15:21
Downloads: 559
Keywords: 


Abstract:

The 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}}.



ISSN 1433-8092 | Imprint