Tag: FRI

Reed-Solomon codes

Let $\mathbb{F}$ be a finite field, and write $\mathbb{F}[X]^{< n}$ for the polynomials of degree less than $n$ over $\mathbb{F}$. For any $\omega \in \mathbb{F}^n$, write $$ \epsilon_\omega: \mathbb{F}[X]^{< n} \to \mathbb{F}^n \qquad f \mapsto (f(\omega_i))_{i=1, \dots, n} \quad \forall f$$ for the evaluation map. For any such choice of $n, \omega$ and of $0 < k \leqslant n$, let $$ RS_{n,k}[\omega] := \epsilon_\omega (\mathbb{F}[X]^{< k})$$ denote the corresponding Reed-Solomon code. We’ll require that the entries of $\omega$ are distinct, so that $RS_{n,k}[\omega]$ is a $k$-dimensional subspace of $\mathbb{F}^n$ and hence is a $(n,k)$ linear code. The ambient space $\mathbb{F}^n$ is considered to be equipped with a fixed basis, and comparison of the coefficients of two vectors with respect to this basis defines the Hamming distance.

Equivalences of linear codes

Recall that two $(n,k)$ linear codes are equivalent if there exists a linear isomorphism $\mathbb{F}^n \to \mathbb{F}^n$ that preserves the Hamming distance on the ambient and maps the codes to one another. Expressed with respect to the fixed bases, an equivalence of codes is a matrix with precisely one non-zero entry in each row and column.

Equivalences of Reed-Solomon codes

The construction of a Reed-Solomon $RS_{n,k}[\omega]$ code depends on the choice of evaluation points $\omega$ – but to what extent does it really matter which $\omega$ is chosen? It is easy to see that it doesn’t always matter. For instance, permuting the entries of $\omega$ gives an equivalent code. A more interesting example: if $\lambda \in \mathbb{F}^\times$, then $RS_{n,k}[\lambda \omega] = RS_{n,k}[\omega]$, i.e. the two codes are coincide. To see this, just notice that any polynomial $f(X)$ has the same degree as $f(\lambda^{-1}X)$, and that $\epsilon_\omega (f(X)) = \epsilon_{\lambda \omega} (f(\lambda^{-1}(X)))$. Hence the codes coincide. This example generalizes immediately to invertible affine transformations of $\mathbb{F}$ applied to coordinate-wise to $\omega$.

Non-equivalent $(n, k)$-Reed-Solomon codes

There are choices of $\omega$ that lead to non-equivalent $RS_{n,k}[\omega]$, but this seems difficult to verify manually. A computational approach is to use Sage to compute the automorphism groups (i.e. group of self equivalences) of $RS_{n,k}[\omega]$ for various $\omega$. Equivalent codes must have isomorphic automorphism groups. So it is sufficient to find two choices of $\omega$ such that the automorphism groups of the associated code $RS_{n,k}[\omega]$ have distinct orders. For example:

from sage.all import *
from sage.coding.grs_code import GeneralizedReedSolomonCode

K = GF(7)
C1 = GeneralizedReedSolomonCode(vector(K, [0,1,2,3]), 2)
C2 = GeneralizedReedSolomonCode(vector(K, [0,1,2,4]), 2)
C1size = C1.automorphism_group_gens()[1]
C2size = C2.automorphism_group_gens()[1]
C1size, C2size  # outputs (48, 72)

Hence the $\mathbb{F_7}$-linear codes $RS_{4, 2}[(0, 1, 2, 3)]$ and $RS_{4, 2}[(0, 1, 2, 4)]$ are not equivalent.

Generalized Reed-Solomon codes

In order to find further examples of equivalences of Reed-Solomon codes, it turns out to be helpful to describe what at first appears to be a more general construction, but is in fact (up to equivalence of codes) simply a re-parameterization of the same objects. For $\omega \in \mathbb{F}^n$ with distinct entries and $\alpha \in (\mathbb{F}^\times)^n$, let $$\epsilon_{\omega, \alpha}: \mathbb{F}[X]^{<n} \to \mathbb{F}^n \quad f \mapsto (\alpha_i f(\omega_i))_{i=1, \dots, n} \quad \forall f.$$ Then $\epsilon_{\omega, \alpha}$ is linear, and the image of $\mathbb{F}[X]^{<k}$ under this map is the generalized Reed-Solomon code $GRS_{n,k}[\omega, \alpha]$. Notice that (trivially) a Reed-Solomon code is equivalent to every generalized Reed-Solomon code with the same evaluation points, i.e. $$\begin{equation}\label{Equiv}\tag{Equiv}RS_{n,k}[\omega] \cong GRS_{n,k}[\omega, \alpha] \quad \forall \alpha \in (\mathbb{F}^\times)^n.\end{equation}$$So the GRS codes are just a more redundant parameterization of the RS codes – nothing new is gained! Indeed, “generalized Reed-Solomon code” is a misleading name. Yet the GRS codes are more convenient when it comes to constructing equivalences: in order to demonstrate $RS_{n,k}[\omega] \cong RS_{n,k}[\omega’]$, it suffices to find $\alpha, \alpha’$ such that $GRS_{n,k}[\omega, \alpha] \cong GRS_{n,k}[\omega, \alpha’]$, and this is often easier.

For example, it turns out to be straight-forward to show the following (proof below) $$\begin{equation}\tag{Invert}\label{Invert}\forall \omega \in (\mathbb{F}^\times)^n \ \ \forall \alpha \in (\mathbb{F}^\times)^n \ \ \exists \beta \in ( \mathbb{F}^\times)^n \ \ : \ \ GRS_{n, k}[\omega, \alpha] = GRS_{n,k}[\omega^{-1}, \beta].\end{equation}$$ Indeed, $\beta_i = \alpha_i \omega_i^{-k}$ works. Setting $\alpha_i = 1 \ \forall i$ and invoking \eqref{Equiv} twice, this allows us to conclude that $$ RS[\omega] \cong GRS[\omega, \alpha] = GRS[\omega^{-1}, \beta] \cong RS[\omega^{-1}].$$This is a pretty neat result!

Following is a proof of \eqref{Invert}. While very simple, it seems to be peculiarly “linguistic” as it involves the re-ordering of some coefficients. We’ll explore this next.

(For more on the generalized Reed-Solomon codes and these equivalences, see these lecture notes).

Reed-Solomon codes as algebraic geometry codes

We’ve demonstrated that, if $\omega$ and $\omega’$ can be related by a composition of entry-wise affine transformations and inversions, then $RS_{n,k}[\omega] \cong RS_{n,k}[\omega’]$. Being able to build code equivalences from two apparently distinct sorts of transformations of $\mathbb{F}$ invites us to look for a more general context in which they are two instances of the same thing. A hint as to what that might be (if another was needed) is contained in the above proof of \eqref{Invert}: in what context does reversing the order of the coefficients of a polynomial become meaningful? This transformation would be more naturally described as interchanging the indeterminates of bivariate polynomials of homogeneous degree $k-1$. Indeed, the needed generalization uses the projective line $\text{P}^1(\mathbb{F})$ in place of $\mathbb{F}$ as the source of the evaluation points and uses “appropriate” functions on $\text{P}^1(\mathbb{F})$ in place of $\mathbb{F}[X]^{< k}$. The natural notion of functions on $\text{P}^1(\mathbb{F})$ are the “rational functions”: ratios of homogeneous bivariate polynomials where the numerator and denominator have the same degree. In this new context, the polynomials of degree $< k$ become those rational functions that only have poles at the point at infinity $(1:0)$, and then only of order $< k$. Importantly, these functions form a vector space, and the evaluation of any such function at an affine point $(\omega_i:1)$ is (since any pole could only be at infinity) an element of the field $\mathbb{F}$.

The first sort of equivalence of RS codes constructed above resulted from an affine transformation of $\mathbb{F}$. Just as invertible affine transformations transform the 1-dimensional affine space $\mathbb{F}$, homographies (i.e. isomorphisms of projective space) transform the projective line $\text{P}^1(\mathbb{F})$. A homography of the projective line has the form
$$ (X:Y) \mapsto (aX + bY: cX + dY) \quad \forall (X:Y) \in \text{P}^1(\mathbb{F}),$$
for some invertible 2×2 matrix $\begin{pmatrix}a & b\\ c & d\end{pmatrix}$. Let’s consider some special cases. Setting $c=0, d=1$, this is (an extension of) an invertible affine transformation of $\mathbb{F}$. On the other hand, setting $a=d=0$, $b=c=1$, we have an extension of the map that inverts non-zero field elements (and induces an interchanging of the indeterminates of bivariate homogeneous polynomials!). So the homographies are sufficiently general to include the two sorts of transformations $\mathbb{F}$ used above to construct our equivalences of RS codes.

Thus we might define a “projective RS code” by beginning with a sequence of $n$ distinct points $P_i \in \text{P}^1(\mathbb{F})$ and a constraint on the maximum order of poles at every point on $\text{P}^1(\mathbb{F})$ (and such that no poles are permitted at any $P_i$). Call this constraint $D$ and write $L(D)$ for the linear space of all rational functions that satisfy the constraint $D$. Since no poles are permitted at the $P_i$, the evaluation map $\epsilon : L(D) \to \mathbb{F}^n$ is well-defined linear map. Indeed, given a further technical assumption on the constraint, $\epsilon$ is injective, and we’ve constructed an $(n,k)$ code where $k=\text{dim}(L(D))$. Clearly it includes the familiar RS codes, and indeed it can be shown (see e.g. Walker Theorem 6.4 & Exercise 6.6) that all these codes are MDS codes. The natural generalization of the code equivalences constructed above are constructed from homographies of $\text{P}^1(\mathbb{F})$. The homographies transform the evaluation points as well as the functions being evaluated (along with their constraint). The advantage of this viewpoint is that now there is nothing to prove: the linear code is defined using structures in projective space, and since homographies are the structure preserving maps of projective space, it is vacuously true that homographies induce equivalences of codes.

Instead of defining such codes, we go just one step further, and consider an arbitrary non-singular projective plane curve $\mathcal{C} \subset \text{P}^2(\mathbb{F})$ in place of the projective line. There are $n$ distinct evaluation points $P_i \in \mathcal{C}$, and the “constraint” on the order of the poles takes the form of a divisor $D$ on $\mathcal{C}$ whose support does not contain the $P_i$. The space of functions $L(D)$ are the rational functions on the curve associated to the divisor $D$, i.e. is the Riemann-Roch space. The dimension $k$ of the resulting algebraic geometry code $AG[\mathcal{C}, (P_1, \dots P_n), D]$ is determined by the degree of the divisor and the genus of $\mathcal{C}$.

Further reading

These lecture notes are an excellent elementary introduction to equivalences of GRS codes. See Walker’s “Codes & Curves” for a speedy introduction to algebraic geometry codes, and read The automorphism groups of Reed-Solomon codes (Dür, 1987) for a description of the automorphism group of Reed-Solomon codes in terms of fractional linear transformations (i.e. homographies of the projective line).