Reed-Solomon outer code and binary linear inner code

Fix an integer $m\ge 1$ and put $q:=2^m$ and $K:=q\mathrm{/}2$. Choose, by scanning the monic polynomials of degree $m$ over ${\mathbb{F}}_2$ in a fixed order and testing each for irreducibility by trial division against all monic polynomials of positive degree at most $\lfloor m\mathrm{/}2\rfloor$, the first monic irreducible $f\in {\mathbb{F}}_2[z]$ of degree $m$; by For every finite field ${\mathbb{F}}_q$ and every $n\ge 1$, a monic irreducible polynomial of degree $n$ exists such an $f$ exists, and the scan is deterministic and takes time polynomial in $2^m$. Set ${\mathbb{F}}_q:={\mathbb{F}}_2[z]\mathrm{/}(f),$ a field with exactly $q$ elements by For every prime $p$ and $n\ge 1$, a field with $p^n$ elements exists and A simple algebraic extension is its minimal-polynomial quotient and has power basis $1,a,\dots ,a^{n-1}$ and degree $n$, in which the classes of $1,z,\dots ,z^{m-1}$ form a power basis; write $\mathrm{e}\mathrm{n}\mathrm{c}:{\mathbb{F}}_q\to {\mathbb{F}}_2^m,\mathrm{e}\mathrm{n}\mathrm{c}({\sum }_{j<m}{c}_j{z}^j+(f)):=(c_0,\dots ,c_{m-1}),$ for the resulting bit encoding, which is a bijection, and list the elements of ${\mathbb{F}}_q$ in the order induced by $\mathrm{e}\mathrm{n}\mathrm{c}$ on the binary representations $0,1,\dots ,q-1$ of the exponents.

The outer code. The Reed-Solomon outer code ${\mathrm{R}\mathrm{S}}_{q,K}$ encodes a message $(c_0,\dots ,c_{K-1})\in {\mathbb{F}}_q^K$, read as the polynomial $P(X):={\sum }_{i<K}{c}_i{X}^i$ of degree less than $K$, into the word ${\mathrm{R}\mathrm{S}}_{q,K}(c):=(P(\alpha ){)}_{\alpha \in {\mathbb{F}}_q}\in {\mathbb{F}}_q^q,$ the evaluation at all $q$ field elements in the fixed order above. It is ${\mathbb{F}}_q$-linear of dimension $K$ over ${\mathbb{F}}_q$, hence $Km$ bits of message and $qm$ bits of outer codeword.

The inner code. A binary linear inner code of rate $1\mathrm{/}16$ is a fixed injective ${\mathbb{F}}_2$-linear map $E_{\mathrm{i}\mathrm{n}}:{\mathbb{F}}_2^m\to {\mathbb{F}}_2^{16m},$ written on messages as $u\mapsto Mu$ for a binary $16m\times m$ matrix $M$, the generator matrix; its existence with relative distance at least $1\mathrm{/}4$ is the content of Conditional expectation constructs the inner code deterministically and the construction is uniform in $m$.

The concatenated code. Let $M$ be the generator matrix of an inner code as above. The concatenation ${\mathrm{R}\mathrm{S}}_{q,K}\circ M$ encodes a message $u\in {\mathbb{F}}_2^{Km}$, split as $u=(u_1,\dots ,u_K)$ with $u_j\in {\mathbb{F}}_2^m$, in two steps: form the outer word $({\alpha }_1,\dots ,{\alpha }_q):={\mathrm{R}\mathrm{S}}_{q,K}({\mathrm{e}\mathrm{n}\mathrm{c}}^{-1}(u_1),\dots ,{\mathrm{e}\mathrm{n}\mathrm{c}}^{-1}(u_K))$, and output the concatenation of $M\mathrm{e}\mathrm{n}\mathrm{c}({\alpha }_1),\dots ,M\mathrm{e}\mathrm{n}\mathrm{c}({\alpha }_q)$. Its output is a string of $16qm$ bits, its input is $Km=qm\mathrm{/}2$ bits, and it is injective because ${\mathrm{R}\mathrm{S}}_{q,K}$ and each of $\mathrm{e}\mathrm{n}\mathrm{c},E_{\mathrm{i}\mathrm{n}},{\mathrm{e}\mathrm{n}\mathrm{c}}^{-1}$ is. It is the code used by A polynomial-time explicit constant-rate constant-distance code.

• Determinism. The field ${\mathbb{F}}_q$ is not presupposed: the definition names the first irreducible polynomial of degree $m$ in a fixed enumeration, so the field, its power basis, the order of its elements, the Reed-Solomon evaluation points and the bit encoding are all functions of $m$ alone and involve no choice. The time to find $f$ is polynomial in $2^m$, because testing irreducibility of one degree-$m$ polynomial by trial division costs $O(2^m)$ field operations and at most $2^m$ polynomials are tried.
• Two different alphabets. The outer code is linear over ${\mathbb{F}}_q$ and the inner code over ${\mathbb{F}}_2$; the concatenation is a binary code, and its parameters are computed in Concatenation multiplies rate and relative distance. The rate of the outer code is $K\mathrm{/}q=1\mathrm{/}2$ and the rate of the inner code is $m\mathrm{/}16m=1\mathrm{/}16$, so the concatenation has rate $1\mathrm{/}32$.
• The inner code is part of the data of the definition rather than a canonical object: any matrix $M$ produced by the uniform procedure of Conditional expectation constructs the inner code deterministically gives the same parameters, so all statements of this page are independent of which of these matrices is used. The convention of Explicit binary codes of constant rate and distance is used for rate and relative distance.