Random Shortening of Linear Codes and Applications

Before formally stating our results, we first informally compare the two operations of random puncturing and random shortening. A random $p$-puncturing of a code of length $n$ involves uniformly selecting $p$ positions randomly from $[n]$, and discarding these positions in the code. One can see that under appropriate conditions, this operation preserves the distinctness of all codewords, and thus can increase the rate of the code. However it may decrease the distance or relative distance of the code. In contrast, a random $s$-shortening of a code involves picking $s$ positions uniformly randomly from $[n]$, forming a subcode that consists of codewords which contain only zeros at these positions, and then deleting these positions in the subcode. It can be seen that this operation perserves the distance of the code, and thus increases the relative distance of the code, but on the other hand the rate of the code can potentially decrease. Hence, these two operations are indeed “dual” in some sense, and therefore one can apply both operations to adjust both the rate and the relative distance of the code.

A linear code $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$, where $q=p^{r}$ for some prime $p$, is called $\varepsilon$-biased, if for every codewords $c\in\mathcal{C}$, $\left|\sum_{i=1}^{n}\omega^{\mathrm{tr}\left(a\cdot c_{i}\right)}\right|\leq\varepsilon n$ for all $a\in\mathbb{F}_{q}^{\ast}$. where $\omega=e^{\frac{2\pi i}{p}}$ and $\mathrm{tr}:\mathbb{F}_{q}\rightarrow\mathbb{F}_{p}$ is the field trace map. In Section 2.2, we will provide a more detailed explanation of the $\epsilon$-biased code.

Our main results show that random shortening is an effective way to reduce the bias of a code. Note that this is stronger than increasing the relative distance, since the former implies the latter (see Proposition 2.10). If the mother code satisfies certain conditions, then we show after random shortening the new code can achieve an arbitrarily small bias with high probability. We note that a random linear code has a small bias, and thus in this sense the code after random shortening behaves like random linear codes. Moreover, the condition that the mother code has a low bias is required in several previous works (e.g., [GM22, PP23]), while these works essentially do not care about the rate of the mother code. Thus we can apply a random puncturing to the new code after a random shortening, to get another code where all monotone-decreasing local properties are similar to those of random linear codes. This further weakens the requirements of mother codes in previous works to some extent.

A low-biased code must have a large distance, as stated in Proposition 2.10. However, the reverse may not hold. The following theorem shows that it is also possible to derive a low-biased code from a code with a large distance by random shortening.

We note that the theorem only requires a lower bound on the relative distance, but there are no restrictions on the rate of the original code, $R$. Hence, this requirement is generally easy to satisfy, for example, from simple constructions using code concatenation. Furthermore, we can select an appropriate shortening size to ensure that the rate of the shortened code is arbitrarily close to $R$.

The distance condition of $\mathcal{C}$ in Theorem 1.6 can also be relaxed, resulting in the following theorem.

Indeed, the asymptotic form of the Plotkin bound is given by

Thus Theorem 1.7 implies that as long as the rate-distance trade-off of the original code is close enough to the Plotkin bound, we can obtain a code with an arbitrarily small bias by random shortening. On the other hand, unlike in Theorem 1.6, the rate of the shortened code may not be arbitrarily close to $R$, but we can still get a new rate that is only a constant factor smaller.

In the next theorem, there is no requirement for $\delta$ to be very large. Instead, we impose constraints on its dual distance, $\delta^{\perp}$, and the rate, $R$. If the dual distance is not too small and the rate can be upper bounded, then we can also apply the shortening technique to obtain a low-biased code.

In Theorem 1.8, the rate of the dual code must be sufficiently large. Additionally, if the term $\frac{\frac{1}{2}-2\gamma}{1+0.9\cdot\log_{q}(1-\delta)}$ is less than 1, the rate-distance trade-off of the dual code surpasses the Gilbert-Varshamov (GV) bound. Consequently, when examining the problem within the context of the GV bound, we need to impose specific constraints on $\delta$. This leads to the following corollary.

Theorem 1.8 and Corollary 1.9 show that as long as the mother code and its dual both have a reasonable relative distance, one can use random shortening to get a new code with an arbitrary small bias, while only losing a constant factor in the rate. We note that linear codes such that both the code and its dual have good relative distance are also easily constructible, for example, see [Shp09].

In [GM22], the authors showed that a random puncturing of a low-biased code results in a new code that behaves like random linear codes. Using our theorems, we present a weaker condition that still achieves similar results. This follows from a combination of random shortening and random puncturing, as briefly discussed before.

Our work leaves several open questions for future investigation. One such question is whether we can achieve a good rate when performing random shortening. Right now, using our analysis, the rate of the code after random shortening is potentially worse than the mother code we start with, and thus we do not get a good rate-distance trade-off by simply applying random shortening. Therefore, it is a natural question to see if one can achieve an $\varepsilon$-biased code through random shortening while at the same time maintaining a favorable $R$–$\varepsilon$ trade-off, if we start with some good initial conditions of the mother code. Another direction is further weakening the initial conditions required for obtaining low-biased codes, such as removing the constraint of $\delta$ in Theorem 1.8. In our view, these questions present exciting opportunities for advancing our understanding of random shortening, low-biased codes and their connections.

Finally, it would also be quite interesting to completely derandomize the random shortening, thus yielding explicit constructions of low-biased codes with special structures (e.g., LDPC codes or expander codes). This will complement existing constructions of low-biased codes, and possibly lead to more efficient decoding algorithms.

The shortening results in changes to the parameters of the code. Here, we mainly apply shortening for two purposes: adjusting the bias and amplifying the relative distance.

1. 1.

   Adjusting the bias: Let $\mathcal{C}$ be of length $n$. When $\mathcal{C}_{\varepsilon^{\prime}}$ is hit by $\mathcal{S}$, it implies that the codewords in $\mathcal{C}$ not hit by $\mathcal{S}$ are all $\varepsilon^{\prime}$-biased. However, it doesn’t directly imply that the shortened code $\mathcal{C}^{[\mathcal{S}]}$ is also $\varepsilon^{\prime}$-biased, since the shortening operation changes the length of the code. Nevertheless, the new bias $\varepsilon$ of $\mathcal{C}^{[\mathcal{S}]}$ is given by $\varepsilon\leq\frac{\varepsilon^{\prime}n+s}{n-s}$, where $s$ is the size of the shortening $\mathcal{S}$. If $s$ is small compared to $n$, $\varepsilon$ is close to $\varepsilon^{\prime}$. In the proof of Theorem 1.6, we can choose $s$ to be a sufficiently small fraction of $n$. In the proof of Theorem 1.8, we provide an upper bound for $R$, which also enables us to choose a small shortening size. In both cases, we set the shortening size to be less than $0.05\varepsilon^{\prime}n$, allowing us to choose $\varepsilon^{\prime}=0.9\varepsilon$.

2. 2.

   Amplifying the relative distance: We use another technique in the proof of Theorem 1.7 to first transform a code with a rate-distance trade-off near the Plotkin bound into a code with near-optimal distance. By Proposition 2.8, the distance of the shortened code $\mathcal{C}^{[\mathcal{S}]}$ is no less than that of the original code $\mathcal{C}$. However, since $\mathcal{C}^{[\mathcal{S}]}$ has length $n-s$ instead of $n$, its relative distance becomes $\frac{\delta}{1-\frac{s}{n}}$. This allows us to increase the relative distance of the code. In turn, Theorem 1.7 follows from Theorem 1.6.

This is the most critical part of all our proofs. For Theorem 1.6 and Theorem 1.8, we have two different ways of estimating the upper bound of $|\mathcal{C}_{\varepsilon}|$:

1. 1.

   Estimating $|\mathcal{C}_{\varepsilon}|$ with relative distance $\delta$: We use $J_{q}(\delta)$ to denote the list decoding radius corresponding to the classical Johnson bound for a code over $\mathbb{F}_{q}$ with relative distance $\delta$. It is easy to see that when $\delta$ is close to the optimal $\frac{q-1}{q}$, so is $J_{q}(\delta)$. To give an upper bound of $|\mathcal{C}_{\varepsilon}|$, we construct $q$ balls in $\mathbb{F}_{q}^{n}$ with radius $J_{q}(\delta)$ and centered at $t\cdot\vec{1}$, where $\vec{1}$ is the all-one vector and $t\in\mathbb{F}_{q}$. By the Johnson bound, the number of codewords covered by these balls is at most $\mathrm{poly}(n)$. We show that, if a codeword $c$ is not covered by these balls, its empirical distribution over $\mathbb{F}_{q}$ is close to the uniform distribution, which implies $c$ is small biased. This upper bounds $|\mathcal{C}_{\varepsilon}|$ by $\mathrm{poly}(n)$.

2. 2.

   Estimating $|\mathcal{C}_{\varepsilon}|$ with relative dual distance $\delta^{\perp}$ and rate $R$: If $\mathcal{C}$ has dual distance $d^{\perp}$, then any $d^{\perp}-1$ columns of the generator matrix of $\mathcal{C}$ are linearly independent, which means that if we uniformly randomly choose a codeword from $\mathcal{C}$, then any $d^{\perp}-1$ symbols of the codeword are independently uniform, i.e., the symbols of a random codeword are $d^{\perp}-1$-wise independent. We can now use this property to estimate the probability that a codeword randomly chosen from $\mathcal{C}$ is not $\varepsilon$-biased. This is a typical application of the concentration phenomenon from the higher moment method, where we use Hoeffding inequality, Chernoff bound, and Sub-Gaussian property to bound the $(d^{\perp}-1)$th moment of the summation of some random variables. Then by Markov’s inequality, the probability that a random codeword is not $\varepsilon$-biased can be bounded, which also gives an upper bound on $|\mathcal{C}_{\varepsilon}|$.

To obtain random-like codes, we combine our results with those in [GM22], which state that a randomly punctured low-biased code is likely to possess any monotone-decreasing local property typically satisfied by a random linear code of a similar rate. By our results, we can start from a code with less stringent conditions and achieve the same results as in [GM22], through the operations of a random shortening followed by a random puncturing.

The rest of this paper is organized as follows. In Section 2, we describe some basic definitions, terms, and useful properties. In Section 3, we show how to combine other theorems and the work of [GM22] to obtain a random-like code with weaker initial conditions and prove Theorem 1.10. In Section 4, we present two methods for estimating $|\mathcal{C}_{\varepsilon}|$. In Section 5, we prove Theorem 1.6 and Theorem 1.7. In Section 6, we prove Theorem 1.8 and Corollary 1.9.