Random code[1]
Description
Code whose construction is non-deterministic in some way, i.e., codes that utilize an element of randomness somewhere in their construction. Members of this class range from fully non-deterministic codes to codes whose multi-step construction is deterministic except for a single step.
Typically, random codes are selected with uniform distribution from some ensemble of codes. For example, a random binary code is a set of \(K\) codewords of length \(n\) chosen uniformly from the ensemble of all \(2^n\) bit-strings. Each bit in each codeword is chosen independently and uniformly. For another example, a random binary linear code is generated from \(k\) randomly chosen generators of length \(n\). Equivalently, it is defined by a random \(k \times n\) binary generator matrix whose entries are chosen independently and uniformly.
In both of the above random code constructions, the ensemble size scales exponentially with \(n\). A common convention is to think of the resulting code constructions as effectively explicit (as opposed to random) in cases where the ensemble size is independent of \(n\) or even when the size scales polynomially with \(n\).
Rate
Typical random codes (TRC) or typical random linear codes (TLC) refer to codes in the respective ensemble that satisfy a certain minimum-distance property. The relative fraction of typical codes in the ensemble approaches one as \(n\) goes to infinity [1] (see also Ref. [2]). Asymptotically, given relative distance \(\delta=d/n\), the maximum rate for a TRC is \(R=\frac{1}{2}R_{GV}(\delta)\), where \(R_{GV}(\delta)=1-h(\delta)\) is the Gilbert-Varshamov (GV) bound and \(h(\delta)\) is the binary entropy function. The maximum rate for a TLC is \(R=R_{GV}(\delta)\), meaning that TLCs achieve the asymptotic GV bound.Decoding
Ball-collision decoding [3].Information set decoding (ISD) [4] and Finiasz and Sendrier (FS-ISD) decoding [5].Realizations
Distributed storage systems [6].Classical and quantum cryptography based on the learning-with-errors problem, which is related to decoding a random linear code [7].Random codes can be used to realize secure computation [8].Notes
Shannon’s pioneering work [1] analyzes the distance distribution of the code given a rate. Given \(n\) and rate \(R\), the minimum distance of a TRC is governed asymptotically by the GV bound \(d=n\delta_{GV}(2R)\), where \(\delta_{GV}(x)=h^{-1}(1-x)\) for \(0\leq x \leq 1\). For a TLC, the minimum distance is similarly governed by \(d=n\delta_{GV}(R)\).Cousins
- Fountain code
- Justesen code— The required inner codes are obtained by random sampling from the Wozencraft ensemble, whose length scales logarithmically with \(n\).
- Goldreich-Sudan code
- Low-density parity-check (LDPC) code— LDPC codes are often constructed nondeterministically.
- Generalized RS (GRS) code— Concatenations of GRS codes with random linear codes almost surely attain the GV bound [9].
- Meir code
- Random quantum code
- Expander LP code— Expander lifted-product codes are quantum CSS codes that utilize short classical codes in their construction which need to satisfy some properties (Ref. [10], Lemma 10). It is shown that such codes exist, but they are not explicitly constructed. Such codes can be obtained by repeated random sampling or by performing a search of all codes of desired length. Nevertheless, since the length of the desired short codes does not scale with \(n\), this construction is effectively explicit.
Primary Hierarchy
References
- [1]
- C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948) DOI
- [2]
- A. Barg and G. D. Forney, “Random codes: minimum distances and error exponents”, IEEE Transactions on Information Theory 48, 2568 (2002) DOI
- [3]
- D. J. Bernstein, T. Lange, and C. Peters, “Smaller Decoding Exponents: Ball-Collision Decoding”, Lecture Notes in Computer Science 743 (2011) DOI
- [4]
- A. Becker, A. Joux, A. May, and A. Meurer, “Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding”, Lecture Notes in Computer Science 520 (2012) DOI
- [5]
- M. Finiasz and N. Sendrier, “Security Bounds for the Design of Code-Based Cryptosystems”, Lecture Notes in Computer Science 88 (2009) DOI
- [6]
- Yunfeng Lin, Ben Liang, and Baochun Li, “Priority Random Linear Codes in Distributed Storage Systems”, IEEE Transactions on Parallel and Distributed Systems 20, 1653 (2009) DOI
- [7]
- O. Regev, “On lattices, learning with errors, random linear codes, and cryptography”, Journal of the ACM 56, 1 (2009) DOI
- [8]
- H. Chen, R. Cramer, S. Goldwasser, R. de Haan, and V. Vaikuntanathan, “Secure Computation from Random Error Correcting Codes”, Lecture Notes in Computer Science 291 (2007) DOI
- [9]
- C. Thommesen, “The existence of binary linear concatenated codes with Reed - Solomon outer codes which asymptotically meet the Gilbert- Varshamov bound”, IEEE Transactions on Information Theory 29, 850 (1983) DOI
- [10]
- P. Panteleev and G. Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes”, (2022) arXiv:2111.03654
Page edit log
- Victor V. Albert (2022-04-26) — most recent
- Xiao Xiao (2022-03-26)
Cite as:
“Random code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/random
Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/properties/random.yml.