Explicit binary codes of constant rate and distance

Throughout this page, for $N\ge 1$ the relative Hamming distance between $x,y\in \{0,1{\}}^N$ is $\delta (x,y):=\frac{\mathrm{\#}\{i\in \{1,\dots ,N\}:x_i\mathrm{\ne }{y}_i\}}{N}\in [0,1],$ and the relative distance of a subset $C\subseteq \{0,1{\}}^N$ with $\mid C\mid \ge 2$ is $\min \{\delta (x,y):x\mathrm{\ne }y,x,y\in C\}$, while a subset with exactly one element has relative distance $1$ by convention.

A binary code family is a sequence of maps $C_k:\{0,1{\}}^k\to \{0,1{\}}^{N(k)}$ for $k\ge 1$, each injective, with an integer length function $N(k)\ge k$. Its rate at $k$ is $k\mathrm{/}N(k)$. The family is explicit with constant rate and constant distance when there are absolute constants $c_0>0$, ${\delta }_0>0$, $C_0>0$ such that for every $k\ge 1$ $N(k)\le C_{0}k,\frac{k}{N(k)}\ge c_0,\delta (C_k(x),C_k(y))\ge {\delta }_0\text{ for all }x\mathrm{\ne }y\in \{0,1{\}}^k,$ and each encoder $C_k$ is computable by one deterministic algorithm in time polynomial in $k$, uniformly in $k$: the algorithm takes $1^k$ together with $x\in \{0,1{\}}^k$ as input and writes the $N(k)$ output bits.

• Explicit here means the same convention as for constraint graphs in Complete uniform gap-preserving CSP reductions: the output is written bit by bit, so that the running time is measured against the length of the produced codeword plus the input length, and a family is uniform when one algorithm serves all $k$. Nothing is claimed about the parity-check matrix, the decoder, or the existence of a fast decoder.
• The padding convention is part of the definition: the code is defined for every $k\ge 1$ with its own length $N(k)$, and a construction that first pads $x$ to some convenient length $\bar{k}\ge k$ and then encodes is admissible only when the resulting length is $O(k)$ and the analysis of injectivity and distance is done for the padded map, as in A polynomial-time explicit constant-rate constant-distance code.
• Rate and distance trade off, and both constants above are absolute: the page needs $N(k)=O(k)$ so that a constraint system whose variables are the $k$ message bits and whose size is measured against $N(k)$ stays linear in $k$, and it needs ${\delta }_0>0$ so that a constant fraction of the encoded bits witnesses every error in a message. The padded construction of A polynomial-time explicit constant-rate constant-distance code achieves ${\delta }_0=1\mathrm{/}8$ and rate greater than $1\mathrm{/}128$ with $N(k)<128k$; $1\mathrm{/}32$ is the rate before padding.
• The relative distance of a code is a minimum over pairs of codewords and is defined to be one for a one-element code so that the convention matches the relative-distance convention for testers, where an empty solution set is assigned distance one (Assignment tester and rejection ratio).