# Random code[1]

## Description

Code whose construction is non-deterministic in some way, i.e., codes that utilize an elements of randomness somewhere in their construction. Members of this class range from fully non-deterministic codes, to codes whose multi-step construction is deterministic with the exception of 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 \(2^{K}\) codewords with length \(N\) chosen uniformly from the ensemble of all \(2^N\) bit-strings. Each bit in the codeword is randomly chosen between 0 and 1 with equal probability. For another example, a random binary linear code is generated from a random chosen \(K\) generators of length \(N\), where each bit of the generators is randomly chosen between 0 and 1 with equal probability. Equivalently, a random binary linear code is defined by a randomly generated \(K\) by \(N\) generator matrix, where each entry is randomly chosen between 0 and 1 with equal probability.

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

## Decoding

## Realizations

## Notes

## Parent

## Child

## 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 non-determinisitically.
- 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.

## 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”, Advances in Cryptology – CRYPTO 2011 743 (2011) DOI
- [4]
- A. Becker et al., “Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding”, Advances in Cryptology – EUROCRYPT 2012 520 (2012) DOI
- [5]
- M. Finiasz and N. Sendrier, “Security Bounds for the Design of Code-Based Cryptosystems”, Advances in Cryptology – ASIACRYPT 2009 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 et al., “Secure Computation from Random Error Correcting Codes”, Advances in Cryptology - EUROCRYPT 2007 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.