Random Shortening of Linear Codes and Applications

Xue Chen, Kuan Cheng, Xin Li, Songtao Mao

Introduction

In the field of coding theory, Random Linear Codes (RLCs) represent a theoretical gold standard. They are known to achieve near-optimal parameters, including Shannon capacity and the Gilbert-Varshamov bound. However, their practical utility is limited by the massive amount of randomness required for their construction and the significant computational challenges associated with efficient decoding.

To address these limitations, researchers have sought methods to "derandomize" or partially derandomize these constructions. While random puncturing—the process of randomly deleting columns from a generator matrix—has been the traditional approach, it often necessitates a highly robust "mother code" to begin with. This paper explores an alternative and complementary technique: random shortening. The authors demonstrate that random shortening can transform relatively "weak" codes into $\epsilon$-biased codes, a property typically reserved for highly random structures, while maintaining a constant rate.

The Mechanics of Random Shortening

While random puncturing involves deleting coordinates from every codeword in a code $C$, random shortening is a more selective process. It involves two steps:

  1. Selecting only the subset of codewords that contain zeros at specific, randomly chosen positions.
  2. Deleting those specific positions from the selected codewords.

A critical insight provided by the authors is the dual perspective: shortening a code $C$ is mathematically equivalent to puncturing its dual code $C^\perp$. This duality allows the application of analytical tools from both puncturing and shortening domains to understand the resulting code's properties.

The "Hitting" Argument

The core of the paper's proof technique rests on identifying a set of "bad" codewords ($C_\epsilon$)—those that fail to meet the $\epsilon$-biased criteria. The authors prove that a random shortening process is highly likely to "hit" these bad codewords. By hitting them (forcing them to have non-zero values in the positions designated for zeros), these undesirable codewords are removed from the code, leaving behind a sub-code comprised only of "good," low-bias codewords.

Theoretical Framework and Weight Distribution

To bound the size of the "bad" set of codewords, the authors employ two distinct mathematical strategies:

  1. Distance-Based Estimation: Utilizing the Johnson bound, the authors show that if a mother code possesses a sufficiently large minimum distance, it cannot contain an excessive number of codewords that deviate significantly from a uniform distribution.
  2. Dual Distance-Based Estimation: For codes where the distance might be smaller, the authors use higher-moment methods and concentration inequalities (such as Hoeffding and Chernoff bounds). They demonstrate that if the dual distance is sufficiently large, the symbols within a codeword behave like independent random variables, naturally limiting the bias.

Key Results and Theorems

The paper establishes several landmark results that define the efficacy of random shortening:

  • Theorems 1.6 & 1.7: These theorems establish that if a mother code has a relative distance approaching the Plotkin bound, random shortening will produce an $\epsilon$-biased code. Crucially, the resulting code maintains a rate that is a constant fraction of the original mother code.
  • Theorem 1.8: This result extends the utility of shortening to codes with smaller distances, provided they have a low initial rate and a sufficiently large dual distance.
  • Theorem 1.10 (The Pipeline): The authors propose a powerful construction pipeline: starting with a weak mother code, applying random shortening, and following it with random puncturing. The result is a code that satisfies nearly all local properties of a true Random Linear Code, effectively "tuning" a weak code into a high-performance one.

Insights and Implications

The most significant takeaway is that random shortening is an exceptionally effective tool for bias reduction. In many cryptographic and pseudorandomness applications, low-biased codes are essential because they ensure that non-zero codewords have a nearly uniform distribution of symbols.

Furthermore, the paper shows that the initial conditions required for these transformations are surprisingly lenient. Unlike previous methodologies that required specific structures like Reed-Solomon or Reed-Muller codes, this work suggests that almost any code with decent distance or dual distance can be transformed into a high-quality, low-bias code.

Limitations and Future Directions

Despite the theoretical breakthroughs, several challenges remain for future research:

  • Rate Trade-offs: The shortening process currently results in a noticeable drop in the code's rate. Future work is needed to determine if the analysis can be tightened to achieve optimal rate-distance trade-offs.
  • Explicit Constructions: While the paper reduces the amount of randomness needed, the shortening process itself remains stochastic. The "holy grail" remains a fully deterministic, explicit construction of these low-bias codes.
  • Decoding Complexity: While shortening preserves certain structural properties (like those found in LDPC codes), the paper does not provide specific new decoding algorithms for the shortened outputs. Understanding how the shortening process impacts the complexity of practical decoding remains an open question.

Summary updated

BibTeX
@inproceedings{chen2023random,
  author = {Xue Chen and Kuan Cheng and Xin Li and Songtao Mao},
  title = {{Random Shortening of Linear Codes and Applications}},
  booktitle = {COCOON},
  year = {2023},
  doi = {10.1007/978-3-031-49193-1\_14},
}
Figure