Matrice MDS

Une méthode courante pour construire des matrices MDS consiste à générer un code de Reed-Solomon sur ${\displaystyle \mathbb {F} _{2^{m}}}$, puis mettre sa matrice génératrice sous forme systématique ${\displaystyle {\begin{pmatrix}I_{k}|M\end{pmatrix}}}$.

Prenons par exemple ${\displaystyle K=\mathbb {F} _{8}\simeq \mathbb {F} _{2}[X]/(X^{3}+X+1)}$et construisons sur ${\displaystyle K}$un code de Reed-Solomon de paramères [6, 3, 4], alors on obtient la matrice génératrice sous forme systématique ${\displaystyle {\begin{pmatrix}I_{3}|M\end{pmatrix}}}$avec

$${\displaystyle M={\begin{pmatrix}1&X&X^{3}\\1&X^{6}&X^{6}\\1&X^{4}&X^{5}\end{pmatrix}}}$$

On peut obtenir à partir de ${\displaystyle M}$une matrice binaire en remplaçant chaque ${\displaystyle X^{m}}$par la puissance correspondante de la matrice compagnon du polynôme ${\displaystyle X^{3}+X+1}$ , on obtient alors

$${\displaystyle M_{b}={\begin{pmatrix}{\begin{array}{c|c|c}{\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}0&1&0\\0&0&1\\1&1&1\end{array}}&{\begin{array}{ccc}1&1&0\\0&1&1\\1&1&1\end{array}}\\\hline {\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}1&0&1\\1&0&0\\0&1&0\end{array}}&{\begin{array}{ccc}1&0&1\\1&0&0\\0&1&0\end{array}}\\\hline {\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}0&1&1\\1&1&1\\1&0&1\end{array}}&{\begin{array}{ccc}1&1&1\\1&0&1\\1&0&0\end{array}}\end{array}}\end{pmatrix}}}$$

Utiliser une représentation différente de ${\displaystyle \mathbb {F} _{8}}$donnerait des matrices ${\displaystyle M}$et ${\displaystyle M_{b}}$différentes et non isomorphes.

Toutes les matrices MDS ne découlent pas de la construction ci-dessus. En particulier, il peut être souhaitable de doter la matrice de propriétés supplémentaires (qu'elle soit circulante, par exemple, afin d'en simplifier l'implémentation). Dans ces cas, il n'est pas rare de procéder à une recherche exhaustive[7] - [8] - [9].