# Etude de codes binaires abeliens modulaires autoduaux de petites longueurs

Paul Camion

► To cite this version:

Paul Camion. Etude de codes binaires abeliens modulaires autoduaux de petites longueurs. [Rapport de recherche] IRIA-RR-350, IRIA. 1979, pp.29. hal-04716598

HAL Id: hal-04716598

https://inria.hal.science/hal-04716598v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

ÉTUDE DE CODES BINAIRES
ABELIENS MODULAIRES
AUTODUAUX
DE PETITES LONGUEURS

Bibliothèque
IRIA

Paul CAMION

Rapport de Recherche N° 350

Avril 1979

29p.
# ÉTUDES DE CODES BINAIRES ABELIENS MODULAIRES AUTODUAUX DE PETITES LONGUEURS

Paul Camion (C.N.R.S./IRIA)

avec une contribution de Franco Preparata (University of Illinois/IRIA)

## Résumé :

On étudie des codes autoduaux qui sont des idéaux principaux de l'algèbre de $\mathbb{F}_2G$, où G est un 2-groupe abélien élémentaire. On propose pour ces codes un décodage inspiré du piégeage des erreurs de Rudolph et Mitchell et du décodage par permutations de Mac Williams qui ne requiert que des multiplications et des additions dans $\mathbb{F}_2G$ sur la donnée d'un $x \in \mathbb{F}_2G$ et de variétés linéaires du $\mathbb{F}_2$-espace vectoriel G. Pour les longueurs 8, 32 et 128, on s'efforce de déterminer parmi les codes étudiés la proposition de ceux qui contiennent des mots de petits poids.

## Abstract :

Selfdual codes which are principal ideals of the algebra $\mathbb{F}_2G$ of the 2-elementary abelian group G over the finite field $\mathbb{F}_2$ are investigated. A decoding method is suggested relying on error trapping (Rudolph and Mitchell) and permutation decoding (Mac Williams). This only requires multiplications and additions in $\mathbb{F}_2G$ where a single element $x$ is given as well as some linear varieties in G (considered as a vector space over $\mathbb{F}_2$). For the lengths 8, 32 and 128, we strive to determine among the codes investigated the amount of those containing codewords with small weights.

<figure><img src="image_3.png" /></figure>
# 0. Introduction

On étudie des codes autoduaux qui sont des idéaux principaux de $\mathbb{F}_2^G$, où $G$ est un 2-groupe abélien élémentaire. Si $(x)$ est un de ces codes, à toute variété linéaire $V$ de $G$ correspond un $x_V$ formé de la somme des termes de $x$ à indices dans $V$ et l'on met en évidence de nombreux $x_V$ qui permettent de définir chacun un ensemble de symboles d'information. De plus $(x)$ a un groupe transitif d'automorphisme et on peut donc proposer un décodage par piégeage des erreurs où les opérations requises ne sont que des multiplications et additions dans $\mathbb{F}_2^G$ sur la donnée de $x$ et de variétés linéaires de $G$. La maJEure partie de l'article est consacrée à l'étude théorique des idéaux principaux concernés. Pour les longueurs 8 et 32, on s'aperçoit qu'une proposition importante de ces idéaux sont des codes extrémaux. L'étude de la longueur 128 met en évidence les difficultés que l'on doit rencontrer dans une étude plus générale.

# 1. Codes modulaires autoduaux

## 1.1. Généralités

On considère l'algèbre $\mathbb{F}_2^G$, où $G \cong (\mathbb{F}_n^+, +)$, pour $n = 2^r$. Comme d'habitude, nous utiliserons une notation polynomiale pour désigner les éléments d'une telle algèbre de groupe abélien. Le produit de $x$ par $y$ dans $\mathbb{F}_2^G$ s'écrit donc

$$ (1) \quad \sum_{g \in G} \left( \sum_{h+k=g} x_h y_k \right) x^g , $$

$$ \text{pour } x = \sum_{g \in G} x_g x^g, \quad y = \sum_{g \in G} y_g x^g. \quad \cdot $$

On sait que dans $\mathbb{F}_2^G$, il n'y a que deux possibilités pour le carré $x^2$ d'un élément $x : x^2 = 0$ ou $x^2 = 1$. Dans (1) en effet on voit que pour $g \neq 0$, on a $h \neq k$ pour $h+k=g$ et que les termes du coefficient de $x^2$ peuvent se grouper par paires ; $x_h x_k + x_k x_h = 0$.

Le coefficient de $x^0$ est

$$ \sum_{h+k=0} x_h x_k = \sum_{g \in G} x_g^2 = \sum_{g \in G} x_g . $$

Donc $x$ est **nilpotent** ou **unité de l'anneau** $\mathbb{F}_2^G$ selon que $\sum_{g \in G} x_g$ vaut 0 ou 1.
Un idéal de $\mathbb{F}_2G$ ne peut contenir que des nilpotents et puisque les nilpotents sont les éléments de poids pairs de $\mathbb{F}_2G$, la somme de deux nilpotents est un nilpotent et le produit d'un élément quelconque de $\mathbb{F}_2G$ par un nilpotent est un nilpotent. D'où

**Propriété 1** : Tout ensemble de nilpotents de $\mathbb{F}_2G$ engendre un idéal propre de $\mathbb{F}_2G$.

## 2. Idéaux principaux autoduaux.

Nous allons étudier ici certains idéaux principaux de $\mathbb{F}_2G$. G est un espace vectoriel de dimension r, pour $n = 2^r$ et $\mathbb{F}_2G$ est un espace vectoriel de dimension n. Les codes que nous allons étudier sont des sous-espaces vectoriels de $\mathbb{F}_2G$. Nous étudions de tels sous-espaces qui soient en plus des idéaux de l'anneau $\mathbb{F}_2G$.

Soit H un sous-groupe d'index deux de G. Si G est considéré comme un $\mathbb{F}_2$-espace vectoriel, H est donc un hyperplan.

**Propriété 2** : Soit x un nilpotent de $\mathbb{F}_2G$ tel que $\sum_{g \in H} x_g = 1$. Alors l'idéal principal $(x) = C$ de $\mathbb{F}_2G$ est un code autodual.

$(x)$ est un espace vectoriel contenu dans son orthogonal $(x)^\perp$, car si $y, y' \in (x)$, le produit scalaire $\langle y, y' \rangle = \sum_{g \in G} y_g y'_{g'}$ est le terme constant du produit de convolution $yy'$. Celui-ci est nul puisque $y = xz, y' = xz'$ et $xzxz' = x^2zz' = 0$. Montrons alors que $\dim(x) = n/2$. Soit $x' = \sum_{g \in H} x_g x_g^\vee$. De la définition de x, il découle que $x'^2 = 1$, car $x'$ peut être considéré comme un élément de $\mathbb{F}_2H$. Mais $x = x' + x''$ où $x'' = \sum_{g \in H} x_g x_g^\vee$. Donc $x'x = 1 + x'x''$ où $x'x''$ a tous ses termes en $x^\vee$ nuls pour $g \in H$ et par conséquent $\{x_g^\vee x'x\}_{g \in H}$ forme un système libre de $C$ de rang $n/2$. Il forme une base de $C$ puisque $C \subset C^\perp$ oblige que $\dim C \le n/2$. ■

**Propriété 3** : Soit x un nilpotent de $\mathbb{F}_2G$ tel que $\sum_{g \in H} x_g = 1$. Si le poids de x est multiple de quatre, $(x)$ est un code auto-dual à poids multiples de quatre.
Puisque $\{X_g^g x' x\}_{g \in H}$ forme une base de $(x)$, $\{X_g^g x\}_{g \in H} = x' \{X_g^g x' x\}_{g \in H}$ forme égale-
ment une base de $(x) = \mathcal{C}$. Chaque élément de cette base étant obtenu en permu-
tant les composantes de $x$ par une permutation de la forme $h \to g+h$, $\forall h \in G$,
a un poids égal à celui de $x$, donc multiple de 4. On sait d'autre part que
la somme de deux mots orthogonaux à poids multiples de quatre est un mot de
code à poids multiples de quatre $\mathcal{C}$ étant autodual, par la Propriété 1 n'a donc
que des mots à poids multiples de quatre. ■

On notera $s(x)$ le **support** d'un élément $x$ de $\mathbb{F}_2^G$.

$$
(2) \quad s(x) = \{g \mid x_g \neq 0\}.
$$

$s(x)$ est donc une partie de $G$. Quand nous considérerons un tel $s(x)$ nous par-
lerons de ses propriétés relatives au $\mathbb{F}_2$-espace vectoriel $G$. En particulier,
$s(x)$ est une **variété linéaire** lorsqu'il est le translaté dans $G$ d'un sous-
espace vectoriel de $G$.

Exemple :

Soit $G \simeq (\mathbb{F}_8, +)$ et $x$ un mot de poids quatre. On a pour un tel $x$ :

**Propriété 4.** : $\mathcal{C} = (x)$ est un code de Hamming (8,4,4) ssi $s(x)$ n'sst pas une variété linéaire.

On a $(x) = (X_g^g x)$ pour tout $g \in G$. On peut donc se ramener au cas où $x_0 = 1$ et
l'hypothèse dit alors que $s(x)$ n'est pas un sous-espace de dimension deux de
$G$. Donc le rang de $s(x)$ est $> 2$, il ne peut être que $3$. $s(x) \setminus \{0\}$ forme alors
une base de $G$.

Soient $k, k' \in s(x)$ $k \neq k'$, $\{k, k'\}$ sous-tend un hyperplan $H$ de $G$ tel que
$\text{Card}(s(x) \cap H) = 3$. Donc $\sum_{g \in H} x_g = 1$.

Par la propriété 2, $(x) = \mathcal{C}$ est un code autodual à poids multiples de quatre.
$\mathcal{C}$ est donc un code (8,4,4) qui est nécessairement un Hamming.

Au contraire, si $s(x)$ est un hyperplan de $G$, on a nécessairement $g+s(x) = s(x)$
ou $g+s(x) = G \setminus s(x)$, $(x)$ est alors un code trivial de dimension deux. $\blacksquare$
Montrons concrètement comment on construit de la sorte un code de Hamming.

Soit $s(x) = (0,0,0), (1,0,0), (0,1,0), (0,0,1)$.

$H = \{(0,0,0), (1,0,0), (0,1,0), (1;1,0)\}$.

Nous indexons les composantes des mots de code par les éléments de $\mathbb{G}$ écrits en colonnaire.

<table><tr><td></td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td></td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><td></td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><td>x :</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr><tr><td>X<sup>100</sup><sub>x</sub>:</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>X<sup>010</sup><sub>x</sub>:</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><td>X<sup>110</sup><sub>x</sub>:</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td></tr></table>

Fig. 1

### 3. Matrices génératrices d'idéaux autoduaux.

#### 3.1. Représentation de $\mathbb{F}_2^G$

Nous venons de faire apparaître une matrice génératrice du code idéal principal $\mathcal{C} = (x)$. Cette matrice est de taille $(n/2) \times n$ et la matrice $n \times n$ dont les lignes et les colonnes sont indexées par les éléments de $\mathbb{G}$ et dont les lignes sont formées par les mots $X_x^g$ du code $\mathcal{C}$, $g \in \mathbb{G}$ est la matrice $M_x$ définie par

$$ (3) \quad \forall h, h' \in \mathbb{G} : M_x(h,h') = \delta_{h+h'} $$

On sait que l'application $\mathbb{F}_2^G \to M(n,2)$ définie par $x \mapsto M_x$ est une représentation de $\mathbb{F}_2^G$ dans l'algèbre $M(n,2)$ des matrices $n \times n$ à coefficients dans $\mathbb{F}_2$. On a donc

$$ (4) \quad M_{x+y} = M_x + M_y ; $$

$$ (5) \quad M_{xy} = M_x \cdot M_y . $$

En particulier, $M_x$ est inversible ssi $x^2 = 1$, donc ssi $w(x)$ est impair, où l'on note $w(x)$ le poids du mot $x$.
Si on écrit $x = x' + x''$ avec $x' = \sum_{g \in H} x_g X_g^g$ et $x'' = \sum_{g' \in H} x_{g'} X_{g'}^{g''}$, on voit que la matrice génératrice de la Figure 1 est la juxtaposition de la matrice $M'_{x'}$, représentation de $x'$ considéré comme élément de $\mathbb{F}_2^H$ et de la matrice unité de taille $(n/2) \times (n/2)$. On peut donc noter cette matrice $(M'_{x'}, I')$ et les matrices génératrices des codes autoduaux que nous considérons dans cette étude seront notées plus généralement $(M'_{x'}, M'_{x''})$ où $x = x' + x''$, comme précédemment. Puisque $x$ est un nilpotent, $w(x)$ est pair, d'autre part pour que soient vérifiées les hypothèses des Propriétés 2 et 3, il faut que $w(x') \equiv w(x'') \equiv 1 \pmod{2}$.

Remarquons que $M'_{x'}$ et $M'_{x''}$ sont alors inversibles et à la matrice génératrice $(M'_{x'}, M'_{x''})$ d'un tel code $C$ peut être substituée sa transformée $(I', M'_{x'x''})$, puisque $M'_{x'} = I'$.

On a donc la

**Propriété 5** : Un idéal $(x) = C$ de $\mathbb{F}_2^G$ vérifie l'hypothèse de la Propriété 1 ssi il a une matrice génératrice de la forme $(I', M'_{y})$ où $w(y) \equiv 1 \pmod{2}$, $y \in \mathbb{F}_2^H$.

Par la Propriété 5, nous nous ramenons à l'algèbre $\mathbb{F}_2^H$ pour étudier les codes définis par la Propriété 1. Chaque $y \in \mathbb{F}_2^H$, $w(y) \equiv 1 \pmod{2}$ définit un tel code, et deux éléments distincts $y, z \in \mathbb{F}_2^H$ de poids impairs définis-sant des codes différents $y$ et $z$ puisque $C$ et $C$ ont pour matrices générá-trices respectives $(I', M'_{y})$ $(I', M'_{z})$ où $M'_{y} \neq M'_{z}$.

Nous résumons ceci par la

**Propriété 6** : Soit $\mathcal{C}$ l'ensemble des codes autoduaux $(x)$ de $\mathbb{F}_2^G$ qui pour un hyperplan donné $H$ de $\mathcal{G}$ vérifient $\mathrm{Card} \, H \cap s(x) \equiv 1 \pmod{2}$.

$\mathcal{C}$ est alors en bijection avec les unités de $\mathbb{F}_2^H$.

## 3.2. Nombre de codes autoduaux principaux de $\mathbb{F}_2^G$ relatifs à $H$ contenant un élément donné de $\mathbb{F}_2^G$.

Nous écrirons brièvement **H-code** pour un code principal autodual $(x)$ de $\mathbb{F}_2^G$ tel que le support de $x$ a un nombre impair d'éléments dans $H$. Si un élément de $\mathbb{F}_2^G$ appartient à un H-code $C_y$, il est de la forme $(u, uy)$. Le
problème est donc de déterminer l'ensemble Y des unités de $\mathbb{F}_2^H$ tel que

$$ (6) \quad \forall y,z \in Y : uy = uz. $$

Ou bien

$$ uyz = u $$

$$ \text{puisque } z^{-1} = z. $$

On voit que Y forme un groupe d'unités auquel correspond le groupe des matrices $M_y$ qui ont pour point fixe u.

Remarquons que si u est une unité, Y est réduit à l'identité. Plus généralement, on a

$$ uy = u \longleftrightarrow u(y+1) = uy' = 0, $$

et on voit que Y est en bijection avec l'idéal nul de u. Mais nous savons que $uy' = 0 \text{ssi } M_u M_{y'} = 0 \text{ ce qui montre que l'idéal nul de } (u) \text{ n'est autre que } (u)^\perp$.

Il y a des cas où on peut calculer $\dim(u)$, donc $\dim(u)^\perp$ et ceci va nous permettre d'effectuer certains dénombrements. On a par exemple

**Propriété 7** : Soit $u \in \mathbb{F}_2^H$, où $H = (\mathbb{F}_2^{r-1,+})$. Si $s(u)$ est une variété linéaire de dimension $t$ de H, alors $\dim(u) = 2^{r-t-1}$.

Par définition, il existe $h \in H$ tel que $h + s(u)$ soit un espace vectoriel de dimension $t$ sur $\mathbb{F}_2$. $w(u) = 2^t$ et puisque $s(u)$ a $2^{r-t-1}$ translatés distincts dans H, l'ensemble $\{X_u^g\}_{g \in H}$ a $2^{r-t-1}$ éléments de supports deux à deux disjoints. Puisque cet ensemble sous-tend l'idéal (u), la dimension de celui-ci est $2^{r-t-1}$. ■
### 3.3. Autres principes des dénombrements.

#### 3.3.1. Nombre de mots de poids pairs w ayant un poids impair dans au moins un hyperplan.

Soit $H$ un hyperplan de $G$. Card $H = 2^{r-1} = n/2$. Notons $U_{W,H}$ l'ensemble des mots $u$ de $\mathbb{F}_2^G$ de poids $w$, où $w$ est pair, et qui ont un poids impair dans $H$. Notons aussi $U_W$ l'ensemble des mots $u$ de $\mathbb{F}_2^G$ de poids $w$ qui ont un poids impair dans **au moins un hyperplan** de $G$. On a

**Propriété 8 :**

$$ \mathrm{Card} \ U_{W,H} = \frac{1}{2} \left( \binom{n}{w} + (-1)^{\frac{w+2}{2}} \binom{n/2}{w/2} \right), $$

(7) et

$$ \mathrm{Card} \ U_W = \left(1 - \frac{1}{2^r}\right) \left( \binom{n}{w} + (-1)^{\frac{w+2}{2} \binom{n/2}{w/2}} \right). $$

On a d'abord

$$ (8) \quad 2^{r-1} \mathrm{Card} \ U_W = (2^r - 1) \mathrm{Card} \ U_{W,H}, $$

car il y a $2^{r-1}$ hyperplans dans $G$ et tout $u \in U_W$ a un poids impair dans exactement $2^{r-1}$ de ces hyperplans.

Pour calculer $\mathrm{Card} \ U_{W,H}$, observons que pour toute partie $E$ de $G$ de cardinal $m$, on calcule aisément le nombre de $u$ de $\mathbb{F}_2^G$ de poids pair $w$ avec un poids impair dans $E$. De l'identité polynomiale

$$ (9) \quad (1+a)^m (1-a)^m = (1-a^2)^m, $$

on obtient en effet

$$ (10) \quad \sum_{\substack{0 \le i \le w \\ i \equiv 0 \pmod{2}}} \binom{m}{i} \binom{m}{w-i} - \sum_{\substack{0 < i < w \\ i \equiv 1 \pmod{2}}} \binom{m}{i} \binom{m}{w-i} = (-1)^{w/2} \binom{m}{w/2}. $$
Le deuxième terme du premier membre est le nombre cherché. Pour $m = n/2$, on a alors

$$ (11) \quad \binom{n}{w} - 2 \operatorname{Card} U_{w,H} = (-1)^{w/2} \binom{n/2}{w/2} $$

d'où la première des relations (7). La seconde vient alors de (8) ■

**Application** : Compter les **u** de poids 4 de $\mathbb{F}_2^G$ dont les supports sont des variétés linéaires et les autres.

Il est facile de voir que pour $w(u) = 4$, $s(u)$ est une variété linéaire ssi $u$ a un poids pair dans tout hyperplan car alors $\sum_{g \in s(u)} g = 0$. On peut d'ailleurs vérifier l'identité :

$$ (12) \quad \frac{(2^r - 1)(2^r - 2)2^{r-2}}{6} + \frac{(2^r - 1)}{2^r} \left( \binom{2^r}{4} - \binom{2^{r-1}}{2} \right) = \binom{2^r}{4} $$

### 3.3.2. Dénombrements dans l'idéal (u) où $w(u) = 4$ et $s(u)$ n'est pas une variété linéaire.

On peut supposer que $0 \in s(u)$. Soit donc $s(u) = \{0, g_1, g_2, g_3\}$ où $g_1 + g_2 \neq g_3$. Il existe évidemment un hyperplan $H$ contenant $s(u) \setminus \{g_3\}$. Donc $H \cap (g_3 + s(u)) = \{0\}$ et $u' = x^g_3$ $u$ est un générateur de l'idéal (u), $w(u') = 4$ et $s(u') \cap H = \{0\}$. (u) a donc une matrice génératrice de la forme $(I', M'_z)$ où $w(z) = 3$.

**Propriété 8** : Soit $u \in \mathbb{F}_2^G$, où $w(u) = 4$ et $s(u)$ n'est pas une variété linéaire. Les seuls générateurs $v \in (u)$ de poids 4 sont ceux de la forme $x^g u$, $g \in G$.

Nous venons de rappeler que si $s(u)$ n'est pas une variété linéaire, il existe un hyperplan $H$ de $G$ tel que $\operatorname{Card}(s(u) \cap H) = 1$. Autrement dit (u) est un H-code de $\mathbb{F}_2^G$.
Tous des éléments de (u) peuvent être obtenus par combinaison linéaire des lignes de $(I', M'_z)$ et en particulier, les générateurs sont ceux que l'on obtient comme somme d'un nombre impair de ces lignes. Donc v est l'une de ces lignes ou la somme de 3 d'entre elles sans quoi son poids serait supérieur à quatre. Mais $M_{I'}^2 = 1$ et les seules combinaisons linéaires de poids 3 des lignes de $M'_z$ donnant un mot de poids 4 sont celles données par les lignes de $M'_z$ elles-mêmes. Les seuls générateurs de poids 4 de (u) sont donc les lignes de la matrice

$I' M'_z$

$M'_z I'$

c'est-à-dire les éléments de la forme $X_u^g, g \in G$. ■

**Application 1.** Une borne supérieure au nombre de H-codes $C_y$ (voir 3.2) de $\mathbb{F}_2^G$ dans lesquels il existe un mot de la forme $(u, uy)$ avec $w(u) = w(uy) = 4$, lorsque $s(u)$ n'est pas une variété linéaire.

Par la Propriété 5, un tel code $C_y$ a une matrice génératrice de la forme $(I', M'_y)$ et un mot $(u, uy)$ de $C_y$ est obtenu en faisant une combinaison linéaire des lignes de cette matrice au moyen des coefficients de $u \in \mathbb{F}_2^H$. Mais $uy$ peut être considéré, nous l'avons vu en 3.1, comme un élément de $\text{l'idéal } (u) \subset \mathbb{F}_2^H$. Puisque $w(y)$ est impair, $y$ est une unité de $\mathbb{F}_2^H$ et $uy$ un générateur de $\text{l'idéal } (u)$. Soit $v = uy^*$. On sait que le nombre de $y$ tel que $uy = v$ est $\text{Card } (u)^\perp$, nous l'avons vu en 3.2. Puisque $u$ a un poids impair dans un hyperplan de $H$, $\dim(u)^\perp = 2^{r-2}$.

Au total, nous savons que $uy$ est de la forme $X_u^g$, par la Propriété 8, et que le nombre de H-codes $C_y$ contenant $(u, X_u^g)$ est $2^{2^{r-2}}$. Mais chacun de ces codes, s'il contient $(u, X_u^g)$ contient aussi $(X_u^h, X_u^{h+g})$, $\forall h \in H$.

Puisque d'autre part, le nombre de $u$ de poids 4 où $s(u)$ n'est pas une variété linéaire de l'espace vectoriel $H$ est

$$ (13) \quad \left(1 - \frac{1}{2^{r-1}}\right) \left( \begin{pmatrix} 2^{r-1} \\ 4 \end{pmatrix} - \begin{pmatrix} 2^{r-2} \\ 2 \end{pmatrix} \right), $$

par (7), la borne supérieure cherchée peut être établie à
$$
(14) \quad (2^{r-1} - 1) \left( \begin{pmatrix} 2^{r-1} \\ 4 \end{pmatrix} - \begin{pmatrix} 2^{r-2} \\ 2 \end{pmatrix} \right) 2^{2^{r-2} - r + 1}
$$

Exemple : Pour r=7, donc n = Card G = 128, on obtient

$$
(15) \quad 2{,}6841828{,}10^{15} \underline{\hspace{2cm}} .
$$

Application 2. Une borne supérieure au nombre de H-codes $C_y$ de $\mathbb{F}_2^G$ dans lesquels il existe un mot $(u,uy)$ avec $w(u) = 4$, $w(uy) = 8$, lorsque $s(u)$ n'est pas une variété linéaire.

Nous avons pu, pour un u donné préciser le nombre exact de générateurs $v \in (u)$ de poids 4. Ici, nous allons obtenir une borne supérieure pour le nombre de générateurs $v \in (u)$ de poids 8.

Examinons à nouveau la matrice génératrice $(I', M'_z)$ du code $(u)$ introduite en 3.3.2. Puisque chaque ligne de cette matrice est de poids 4, un générateur de poids 8 ne peut être obtenu que par une somme de 3 ou 5 lignes de cette matrice. (7 donneraient un poids supérieur à 8). Ayons bien à l'esprit que $z \in \mathbb{F}_2^H'$, où $H'$ est un hyperplan de l'espace vectoriel $H$. $uy$ peut donc s'écrire $(u', u'z)$. Nous voyons alors que la multiplication par $z$ dans $\mathbb{F}_2^H'$ définit une bijection de l'ensemble des mots de la forme $(u', u'z)$ avec $w(u') = 3$ et $w(u'z) = 5$ sur celui de la forme $(zu', zu'z) = (zu', u')$ où $w(zu') = 5$ et $w(u') = 3$. Il nous suffit donc de compter les premiers et de multiplier par deux le résultat. On peut donc affirmer que le nombre de générateurs de poids 8 de $(u)$ est borné supérieurement par $2$. $$ \binom{2^{r-2}}{3} $$

On connait d'autre part, comme dans l'application 1, le nombre d'y tels que
pour u fixé, uy ait une valeur donnée v. De plus, si un code $C_y$ contient
(u,uy) il contient les $2^{r-1}$ éléments distincts ($x^{g_u}, x^{g_{uy}}$), g ∈ H. La borne
supérieure cherchée peut donc être établie à

$$
(16) \quad 2^{-r+1} \left( 1 - \frac{1}{2^{r-1}} \left( \begin{pmatrix} 2^{r-1} \\ 4 \end{pmatrix} - \begin{pmatrix} 2^{r-2} \\ 2 \end{pmatrix} \right) \right) 2 \begin{pmatrix} 2^{r-2} \\ 3 \end{pmatrix}
$$
Exemple : Pour r = 7, on obtient

$$
\begin{align*}
(17) \quad & \frac{63}{64 \times 64} \left( \binom{64}{4} - \binom{32}{2} \right) \times 2 \times \binom{32}{2} \times 2^{32} \\
& = \underline{4.1604833.10^{17}}
\end{align*}
$$

4. Etude de H-codes autoduaux à poids multiples de quatre de longueur 32 et 128.

4.1. n = 32.

On sait qu'un code binaire autodual (32,16,8) est extrémal. Un code
de Reed-Muller de longueur 2^r d'ordre (r-1)/2 pour r impair est autodual et
a pour distance 2^((r+1)/2).

Pour r = 5, on obtient donc un tel code extrémal.

Pour H = (F₁₆,+) et pour tout y de poids congru à moins un modulo quatre, nous
avons vu (Propriété 3 et n° 3) que (I', M'_y) est la matrice génératrice d'un
H-code à poids multiples de 4.

Si nous voulons qu'un tel code ait pour distance 8, il faut que w(y) = 7, 11 ou 15.

Nous allons considérer l'ensemble des y ∈ $\mathbb{F}_2^H$ avec $w(y) = 7$ tels que
$y_0 = 1$. Il y en a

$$
(18) \quad \left( \begin{pmatrix} 15 \\ 6 \end{pmatrix} \right) = 5.005.
$$

Nous allons voir que parmi eux, il y a une majorité de codes extrémaux.

Puisque nous sommes assurés que les poids d'un tel code soient mul-
tiples de 4, il suffit de choisir y en sorte que le code correspond n'ait
pas de mots de poids 4. Les mots de code ont la forme (u,uy) et nous savons
que w(uy) = 1 ssi uy = Xg pour g ∈ H, donc ssi u = Xg y. En particulier, on
a alors w(u) = 7. Pour w(u) = 2 on peut avoir w(uy) = 2, nous allons examiner
ce cas. Comme nous venons de le voir, pour w(u) = 3 on ne peut pas avoir
w(uy) = 1 tandis que pour u ≠ 0 on ne peut jamais avoir w(uy) = 0 puisque y
est une unité.
En résumé, nous devons compter les y de poids 7 avec $y_0 = 1$ tels qu'il existe u de poids 2 avec $w(uy) = 2$. Si $w(u) = 2$, $s(u)$ est nécessairement une variété linéaire de dimension 1. Par la Propriété 7, $\dim(u) = 8$ et $(u)$ est sous-tendu par l'ensemble $\{X^g_u\}_{g \in H}$ où nous observons que $X^h_u = X'^{h'}$ lorsque fois que $\{h,h'\}$ est $s(u)$ ou l'un de ses translatés. On voit donc que pour avoir $w(uy) = w(yu) = 2$, il faut que $\sum_{g \in H} y_g X^g_u = 0$ avec $y_0 = 0$ donc que $s(y)$ ait un élément dans un translaté de $s(u)$ et un nombre pair (donc 0 ou 2) dans chacun des autres. Le nombre de tels y est

$$2.4. \binom{7}{3} = 280.$$

Soit $Y$ l'ensemble des y de poids 7 avec $y_0 = 1$ et $Y_2$ le sous-ensemble des éléments de $Y$ tels qu'il existe u avec $w(u) = 2$ et $w(uy) = 2$.

Le nombre total de u de poids 2 est $\binom{16}{2}$. Mais pour $u' \in \tilde{\mathcal{U}}$ $w(u',u'y) = w(X^g_{u'}, X^g_{uy}) = 4$.

Donc le nombre de u de poids 2 tels que $w(uy) = 2$ est au moins 8. On a donc

$$(19) \quad 8 \operatorname{Card} Y_2 \le \sum_{y \in Y_2} \delta(y) = 280. \binom{16}{2}$$

où $\delta(y)$ est le nombre de u de poids 2 tels que $w(uy) = 2$.

En conclusion

$$\operatorname{Card} Y_2 \le 4.200$$

**Conclusion.** La proportion de codes extrémaux dans ceux définis par $Y$ est supérieure à $(5005 - 4200)/5.005 \approx 16\%$.
Exemple d'une matrice $M'_y$, $y \in Y \setminus Y_2$

<table><tr><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr><tr><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td></tr></table>
4.2. n = 128

4.2.1. Introduction

Nous venons d'établir que plus de 16 ⁰/⁰ des H-codes C_y avec w(y)=7 et y₀ = 1 en longueur 32 avaient une distance minimum 8, soit celle du code auto-dual de Reed-Muller de même longueur. Nous allons vérifier à présent que plus de 67 ⁰/⁰ des H-codes C_y avec w(y) = 31 en longueur 128 ont une distance minimum au moins égale à 12.

Soit Y l'ensemble des y de longueur 64 et de poids 31.

$$
(20) \quad \mathrm{Card} \, Y = \binom{64}{31} = \frac{1,7770901 \cdot 10^{18}}{}
$$

Dans Y nous allons distinguer les sous-ensembles $Y_i$, i=1,2,3,4.

$Y_1$ est l'ensemble des y $\in Y$ tels que $C_y$ contient un (u,uy) de poids < 12 avec w(u) = 3.

$Y_2$ est celui tel que $C_y$ contient un (u,uy) de poids < 12 avec w(u) = 2.

$Y_3$ est celui tel que $C_y$ contient un (u,uy) de poids < 12 avec $w(u) = 4$ et tel que $s(u)$ est une variété linéaire.

$Y_4$ est celui tel que $C_y$ contient un (u,uy) de poids < 12 avec $w(u) = 4$ et tel que $s(u)$ n'est pas une variété linéaire.

4.2.2. Montrons que pour y $\notin Y_i$, i = 1,2,3,4, C_y n'a aucun mot de poids < 12.

Par la Propriété 3, nous savons que $C_y$ n'a que des poids multiples de quatre.

Considérons $Y_1$. Pour que $w(u,uy) < 12$ avec $w(u)$ impair, il faut que $w(u)$ vaille 3 ou 5 et que $w(uy)$ vaille 8 - $w(u)$. Les couples de valeurs possibles sont donc (3,5) ou (5,3).

Observons que si $(u,uy) \in C_y$, $(uy,u)$ appartient à ce même $C_y$. $Y_1$ est donc bien l'ensemble des y $\in Y$ tels que $C_y$ ne contient aucun $(u,uy)$ de poids < 12 avec $w(u)$ impair.

Dans le cas où $w(u)$ est pair, il faut que $w(uy) \equiv w(u) \pmod 4$. Il faut donc envisager pour couples de valeurs $(w(u),w(uy)) : (2,2), (2,6), (4,4)$. Par le même argument que ci-dessus, il est inutile d'envisager les couples opposés.
4.2.3. Une borne supérieure pour $\text{Card } Y_1$

Un code qui contient $(u,uy)$ avec $w(u) = 3$ contient les 64 éléments distincts $(X_u^g, X_{uy}^g)$, $g \in H$. La borne supérieure cherchée peut donc être établie comme suit :

$$ (21) \quad \text{Card } Y_1 \le \frac{\binom{64}{3} \binom{64}{5}}{64} = \underline{4.963.557.312}. $$

4.2.4. Une borne supérieure pour $\text{Card } Y_2$

Lorsque $w(u) = 2$, $(u)$ a une base de 32 éléments de poids 2 à supports 2 à 2 disjoints puisque $s(u)$ est alors toujours une variété linéaire. Chaque élément de cette base se retrouve deux fois comme ligne de la matrice $M_u$. Nous l'avons vu au n° 3, le produit $uy$ se retrouve comme première ligne

de la matrice $M_y M_u$. Il y a donc exactement $\binom{32}{16} \times 16 \times 2$

matrices $M_y$ telles que $w(uy) = 2$ et $\binom{32}{17} \binom{17}{3} \times 2^3$ matrices $M_y$ telles que $w(uy) = 6$.

En conclusion, on a ici pour un $u$ donné : $1.9234572 10^{10} + 3.0775316 10^{12} = 3.0967662 10^{12}$.

Donc

$$ (22) \quad \text{Card } Y_2 \le 3.096766210^{12} \times 63 = \underline{1.950962710}^{14} $$

4.2.5. Une borne supérieure pour $\text{Card } Y_3$

On voit ici que la matrice $M_u$ n'a que 16 lignes distinctes, chacune de poids 4, chaque ligne étant répétée 4 fois. Les différentes combinaisons linéaires peuvent donner un poids 4 correspondant aux partitions suivantes de l'entier 31 :
$$1 + 2 + 7 \times 4$$

$$1 + 3 \times 2 + 6 \times 4$$

$$1 + 5 \times 2 + 5 \times 4$$

$$1 + 7 \times 2 + 4 \times 4$$

$$1 + 9 \times 2 + 3 \times 4$$

$$1 + 11 \times 2 + 2 \times 4$$

$$1 + 13 \times 2 + 4$$

$$1 + 15 \times 2$$

$$3 + 7 \times 4$$

$$3 + 2 \times 2 + 6 \times 4$$

$$3 + 4 \times 2 + 5 \times 4$$

$$3 + 6 \times 2 + 4 \times 4$$

$$3 + 8 \times 2 + 3 \times 4$$

$$3 + 10 \times 2 + 2 \times 4$$

$$3 + 12 \times 2 + 4$$

$$3 + 14 \times 2$$

Pour une matrice donnée $M_u$, le nombre cherché de combinaisons linéaires de poids 31 est donc la somme des entiers que voici :

$$\binom{16}{9} \binom{9}{2} \binom{2}{1} \binom{4}{2} \times 4 = 19.768.320$$

$$\binom{16}{10} \binom{10}{4} \binom{4}{3} \binom{4}{2} \times 4 = 5.811.886.080$$

$$\binom{16}{11} \binom{11}{6} \binom{6}{5} \binom{4}{2} \times 4 = 3.766\,1022 \ 10^{11}$$

$$\binom{16}{12} \binom{12}{8} \binom{8}{7} \binom{4}{2} \times 4 = 8.0702190 \ 10^{12}$$

$$\binom{16}{13} \binom{13}{10} \binom{10}{9} \binom{4}{2} \times 4 = 6.4561752 \ 10^{13}$$

$$\binom{16}{14} \binom{14}{12} \binom{12}{11} \binom{4}{2} \times 4 = 1.9016370 \ 10^{14}$$

$$\binom{16}{15} \binom{15}{14} \binom{14}{13} \binom{4}{2} \times 4 = 1.7553573 \ 10^{14}$$

$$\binom{16}{16} \binom{16}{16} \binom{16}{15} \binom{4}{2} \times 4 = 3.0091839 \ 10^{13}$$

Sous-total $4.6880765 \ 10^{14}$
$$ \binom{16}{8} \binom{8}{1} 4 = 411.840 $$

$$ \binom{16}{9} \binom{9}{3} \binom{3}{2} \binom{4}{2}^2 \cdot 4 = 415.134.720 $$

$$ \binom{16}{10} \binom{10}{5} \binom{5}{4} \binom{4}{2}^4 \cdot 4 = 5.2306975 \ 10^{10} $$

$$ \binom{16}{11} \binom{11}{7} \binom{7}{6} \binom{4}{2}^6 \cdot 4 = 1.8830511 \ 10^{12} $$

$$ \binom{16}{12} \binom{12}{9} \binom{9}{8} \binom{4}{2}^8 \cdot 4 = 2.4210657 \ 10^{13} $$

$$ \binom{16}{13} \binom{13}{11} \binom{10}{10} \binom{4}{2}^{10} \cdot 4 = 1.1621115 \ 10^{14} $$

$$ \binom{16}{14} \binom{14}{13} \binom{13}{12} \binom{4}{2}^{12} \cdot 4 = 1.916370 \ 10^{14} $$

$$ \binom{16}{15} \binom{15}{15} \binom{15}{14} \binom{4}{2}^{14} \cdot 4 = 7.5229598 \ 10^{13} $$

Sous-total
$$ \frac{4.0775088 \ 10^{14}}{4.0775088 \ 10^{14}} $$

TOTAL
$$ 8.7655853 \ 10^{14} $$

D'autre part, il y a (voir (12))

$$ \frac{(64 - 1)(64 - 2)}{(4 - 1)(4 - 2)} \times 16 = 651 \times 16 $$

variétés linéaires de dimension 2 dans H.

Mais à chaque code *C*<sub>*y*</sub> tel que $(w(u),w(uy)) = (4,4)$ où $s(u)$ est une variété linéaire, correspondent 16 mots de la forme $(X_u^g, X_{uy}^g)$ où $s(X_u^g)$ est une variété linéaire.
On a donc finalement

$$
\begin{align*}
(23) \quad \mathrm{Card} \ Y_3 &\le 651 \times 8{,}765585310^{14} \\
&= 5{,}7063962 \ 10^{17}
\end{align*}
$$

4.2.6. Une borne supérieure pour Card Y₄
..................

Cette borne fut calculée en 3.3.2, application 1. Elle est donnée
par (14) :

$$
(24) \quad \underline{2.6841828 \ 10}^{15}
$$

4.2.7. Conclusion

On a donc

$$
(25) \quad \mathrm{Card} \ Y_1 + \mathrm{Card} \ Y_2 + \mathrm{Card} \ Y_3 + \mathrm{Card} \ Y_4 \le \underline{5.7351888 \ 10}^{17}
$$

On en conclut que la proposition de codes à distance minimum ≥ 12 dans Y est
> 67 °/o .

4.2.8. Où apparaissent les difficultés que l'on doit rencontrer dans l'étude des cas où n > 128.

Examinons une façon d'obtenir une borne supérieure au nombre des H-
codes C_y longueur 128, y ∈ Y, contenant un mot de poids 12. Lorsque le mot
est de la forme (u,uy) avec w(u) impair, on obtient sans difficulté une borne
relativement petite en procédant comme pour établir celle de Card Y₁ en 4.2.3.

Lorsque w(u) = 2, on trouve, en raisonnant comme en 4.2.4, (32) (18) / 25 =
1,292562210¹⁴ matrices M_y telles que w(uy) = 10. Après multiplication par 63,
on obtient un nombre inférieur à 10¹⁶.

Lorsque w(u) = 4, on voit aisément que si s(u) est une variété linéaire, il n'existe pas de y de poids impair tel que w(uy) = 8. Au contraire, si s(u) n'est pas
une variété linéaire, on se trouve devant un problème qui fut traité en 3.3.2, application 2. Mais nous pouvons proposer une méthode à substituer aux applications 1 et 2 de 3.3.2 et qui permettrait d'obtenir une borne supérieure plus proche de la valeur cherchée. On peut en effet calculer le nombre de mots de poids 4 du code (u) où $w(u) = 4$ et $s(u)$ n'est pas une variété linéaire. Par la Propriété 8, il y en a 64 qui sont des générateurs et il est facile de voir qu'il y en a $3 \times 16 = 48$ autres dont les supports sont des variétés linéaires, ceci en utilisant l'argument de la preuve de la Propriété 8. Sachant que (u) est autodual, que tous ses poids sont multiples de quatre, et connaissant le coefficient $A_4$ de son polynôme des poids, les relations de Mac Williams devraient permettre d'obtenir son polynôme des poids. En tous cas nous avons fait ce calcul pour un code (u) de longueur 32, au lieu de 64, où $w(u) = 4$ et $s(u)$ n'est pas une variété linéaire. On obtient comme ici le nombre de mots de poids 4 : $32 + 3 + 8 = 56$. Les coefficients non nuls du polynôme des poids de ce code-là sont alors calculés :

$$A_0 = 1, A_4 = 56, A_8 = 1180, A_{12} = 11.144, A_{16} = 40.774, A_{32} = A_0, A_{28} = A_4, A_{24} = A_8, A_{20} = A_{12}.$$

Pour le code (u) de longueur 64, le coefficient $A_{32}$ nous déterminerait de façon précise le nombre d'y $\in Y$ tels que $w(uy) = 4$. En effet, $w(uy) = 4$ avec $y \in Y$, ssi $s(y) \subset s(z)$, où $w(z) = 32$ et $uz = 0$. Il y a $A_{32}$ mots z de poids 32 vérifiant $uz = 0$, i.e. $z \in (u)$ et pour chacun d'eux $32 y \in Y$ avec $s(y) \subset s(z)$. Si $z \neq z'$, $z, z' \in (u)$ et $w(z) = w(z') = 32$, on ne peut pas avoir $y \in Y$ et $s(y) \subset s(z) \cap s(z')$ puisque $w(z+z') \ge 4$. Donc pour chaque u concerné, le nombre de y $\in Y$ avec $w(uy) = 4$ est exactement $32^{A_{32}}$. Pour l'évaluation d'une borne supérieure au nombre des y $\in Y$ avec $w(uy) = 8$ nous ne pouvons pas proposer un calcul aussi précis. Toutefois, en réexaminant l'application 2 de 3.3.2 et en exploitant la connaissance du polynôme des poids de (u), on pourrait tout au moins remplacer $2^{32}$ par $2A_{28}$ ce qui devrait diviser au moins par 2 la borne (17).

Mais les véritables difficultés vont apparaître lorsqu'on se penchera sur le cas $w(u) = 6, w(uy) = 6$. Dans chaque estimation que nous faisions nous avons vu que le polynôme des poids de $(u)^\perp$ nous renseignait bien mais que, faute de le connaître, la seule connaissance de la dimension de $(u)^\perp$, donc de $(u)$ pouvait nous conduire à des conclusions utiles. Nous répondons à cette question dans le cas présent par la
**Propriété 9.** Soit $u \in \mathbb{F}_2^G$, $G = (\mathbb{F}_2^r, +)$, $r \ge 4$ et $w(u) = 6$. Alors $\dim(u) = 2^{r-1}$ ssi il existe un élément de $s(u)$ qui n'est pas la somme des autres. Dans le cas contraire, $s(u)$ est un ensemble à différences du $\mathbb{F}_2$-sous espace de $G$ qu'il engendre et $\dim(u) = 3 \cdot 2^{r-3}$.

On voit sans peine que $s(u)$ a un nombre pair d'éléments dans tout hyperplan de $G$ (donc dans tout complémentaire d'hyperplan de $G$) ssi $\sum_{g \in s(u)} g = 0$. Lorsque cette somme est non nulle, il est clair que la première hypothèse est réalisée et nous savons qu'alors (u) est un H-code, et $\dim(u) = 2^{r-1}$.

On peut supposer que $0 \in s(u)$.

Si $\sum_{g \in s(u)} g = 0$, alors le rang $r(u)$ de $s(u)$ dans le $\mathbb{F}_2$-espace vectoriel $G$ est $\le 4$. Si $r(u) \le 3$, alors $r(u) = 3$ puisque $\mathrm{Card} \ s(u) = 6$ et on ne peut pas avoir $\sum_{g \in s(u)} g = 0$. Dans le cas qui nous occupe, on a donc $r(u) = 4$ et puisque $\sum_{g \in s(u)} g=0$, chaque élément de $s(u)$ est la somme des autres. Soit $E$ le sous-espace de $G$ sur $\mathbb{F}_2$ sous-tendu par $s(u)$. $E$ est isomorphe à $\mathbb{F}_2^4$ et l'image dans $\mathbb{F}_2^4$ de $s(u)$ par un tel isomorphisme est nécessairement obtenue par automorphisme linéaire de $\mathbb{F}_2^4$ à partir de l'ensemble des colonnes du tableau que voici

```
  0 1 0 0 0 1
  0 0 1 0 0 1
  0 0 0 1 0 1
  0 0 0 0 1 1
```

C'est donc un ensemble à différences de $E$ et il est clair que tout ensemble à différences de $E$ ayant six éléments, puisqu'il est de rang 4 et a un nombre pair d'éléments dans tout hyperplan de $E$ (voir $[5]$ et $[1]$) est de la forme $s(u)$ pour $w(u) = 6$, $\sum_{g \in s(u)} g = 0$ et $r(u) = 4$.

L'idéal $(u)$ de $\mathbb{F}_2^G$ est la somme directe (commun espace vectoriel sur $\mathbb{F}_2$) de l'idéal $(u)$ de $\mathbb{F}_2^E$ et des espaces vectoriels $\mathcal{X}^g(u)$ obtenus en faisant parcourir à $g$ un ensemble de représentants des classes latérales de $E$ dans $G$. Pour achever
la preuve, il nous suffit donc de vérifier que la dimension de l'idéal (u) de $\mathbb{F}_2^E$
est 6. Puisque tous les ensembles à différences $s(u)$ de six éléments s'obtiennent
par transformations linéaires affines de $G$ à partir de celui donné par les colon-
nes du tableau I, tous les idéaux (u) de $\mathbb{F}_2^E$ correspondants sont isomorphes et
isométriques (pour la métrique de Hamming). Ils ont donc tous le même polynôme
des poids. Une base de l'idéal (u) définie par le tableau I est donnée par
les six lignes

<table><tbody><tr><td></td><td>0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1</td></tr><tr><td></td><td>0 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1</td></tr><tr><td></td><td>0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1</td></tr><tr><td></td><td>0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1</td></tr><tr><td rowspan="6">II</td><td>1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1</td></tr><tr><td>1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 0</td></tr><tr><td>1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0</td></tr><tr><td>1 0 0 1 0 1 1 0 0 0 0 1 1 0 0 0</td></tr><tr><td>1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0</td></tr><tr><td>1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0</td></tr></tbody></table>

sous le trait horizontal du tableau II

<figure><img src="image_4.png" /></figure>

Les coefficients du polynôme des poids de (u) sont $A_0 = A_{16} = 1$, $A_6 = A_{10} = 16$, $A_8 = 30$.

<figure><img src="image_5.png" /></figure>

## Conclusion.

Pour $w(u) = 2, 4$ ou $6$ nous avons pu caractériser les idéaux (u) de $\mathbb{F}_2^G$ qui ne sont pas des H-codes. Dans chaque cas il nous a été possible de calculer le polynôme des poids. Le polynôme des poids de l'orthogonal, qui nous intéresse pour dénombrer les H-codes contenant un mot de petit poids, sont dans ces cas-là calculables par les relations de Mac Williams. En fait, pour les cas où $w(u) = 2$ ou $4$, $s(u)$ était une variété linéaire et nous avons pu calculer directement les coefficients utiles du polynôme des poids de $(u)^t$. L'étape suivante serait de caractériser les idéaux (u) de $\mathbb{F}_2^G$ qui ne sont pas des H-codes pour $w(u) = 8$ et $10$. Ou tout au moins de déterminer leurs dimensions.
Il est intéressant de noter que si $(u)$ n'est pas un $H$-code pour $w(u) = 2, 4$ ou $6$ alors $s(u)$ est une variété linéaire ou un ensemble à différence de $G$.

## 5. Décodage

### 5.1. Algorithmes

Soit $(x)$ un $H$-code $(n, n/2, d)$ de $\mathbb{F}_2^G$, et soit $\mathcal{H}$ l'ensemble des hyperplans de $G$ qui ont un nombre impair d'éléments en commun avec $s(x)$. Donc pour $\text{Card } G = n = 2^r$, on a $\text{Card } \mathcal{H}=2^{r-1}$, puisque l'ensemble des polynômes de la forme $\sum_{g \in \mathcal{H}} x_g^g$ forment avec 0 un sous-espace vectoriel de dimension $r$ de $\mathbb{F}_2^G$ lorsque $\mathcal{H}$ parcourt l'ensemble de tous les hyperplans de $G$. Notons de façon générale $\bar{\mathbb{E}}$ le complémentaire de $\mathbb{E}$ dans $G$.

Avec la convention habituelle $\mathcal{X}^0 = 1$, $x$ peut être choisi de la forme $1 + \mathcal{X}_H$ où $\mathcal{X}_H = \sum_{g \in \mathcal{H}} x_g \mathcal{X}_g^g$, ceci par définition même d'un $H$-code (voir 3.2). Supposons que le mot à décoder soit de la forme $y = z+u$, où $z \in (x)$, $w(u) \le e$ et $s(u) \subset \mathcal{H}$. Alors,

$$ (26) \qquad yx = zx + ux = 0 + ux = u + u\bar{x}_H, $$

où $u\bar{x}_H$ n'a que des termes indexés dans $\bar{\mathcal{H}}$.

Au contraire, si $s(u) \not\subset \mathcal{H}$, soit $u = u_\mathcal{H} + u_{\bar{\mathcal{H}}}^-$, où l'on utilise la notation générale $u_E = \sum_{g \in E} u_g \mathcal{X}_g^g$, on aura

$$ (27) \qquad yx = u_\mathcal{H} + u_{\bar{\mathcal{H}}} x_{\bar{\mathcal{H}}} + u_\mathcal{H} x_\mathcal{H} + u_{\bar{\mathcal{H}}} $$

où nécessairement $s(u_\mathcal{H} + u_{\bar{\mathcal{H}}} x_{\bar{\mathcal{H}}}) \subset \mathcal{H}$.

Mais si $2e \le d$, puisque $u_\mathcal{H} + u_{\bar{\mathcal{H}}} x_{\bar{\mathcal{H}}} \in (x)$, $w(u_\mathcal{H}) + w(u_{\bar{\mathcal{H}}} x_{\bar{\mathcal{H}}}) \ge d$, donc
$$ w(u_\mathcal{H} x_{\bar{\mathcal{H}}}) \ge d - w(u_\mathcal{H}) $$
$$ w(u_\mathcal{H} + u_{\bar{\mathcal{H}}} x_{\bar{\mathcal{H}}}) \ge d - w(u_\mathcal{H}) - w(u_\mathcal{H}) = d - e > e. $$
D'où le

## 1er Algorithme

Soit $\overline{H}$ l'ensemble des complémentaires d'hyperplan de $\mathcal{H}$. L'ensemble $\mathcal{H} \cup \overline{\mathcal{H}}$ a donc n éléments.

Pour $E \in \mathcal{H} \cup \overline{\mathcal{H}}$, on calcule $yx_E^x$. Soit d'abord $E \in \mathcal{H}$. On sait que $x_E^2 = 1$, donc $(x_E^x) = (x)$. Alors $x_E^x = x' = 1 + x'^2 \in \overline{E}$ où $x' \in \overline{E} = x_E x_E^x$, et la situation est celle de (26) et (27) où l'on remplace $\overline{H}$ par $E$. On a alors le

### Critère

$$ (28) \qquad \text{Card} \left( s(yx_E^x) \cap E \right) > e \Rightarrow s(u) \notin E. $$

$$ \text{Card} \left( s(yx_E^x) \cap E \right) \leq e \Rightarrow s(u) = s(yx_E^x) \cap E. $$

On peut donc pratiquement calculer $yx$ puis ses différents produits par les $x_E$, $E \in \mathcal{H}$ afin d'appliquer le critère.

Examinons le cas où $E \in \overline{\mathcal{H}}$. Voyons par exemple (27) dans le cas où $E = \overline{\mathcal{H}}$. On observe que si $u_{\overline{\mathcal{H}}} = 0$, $s(yx) \cap \overline{\mathcal{H}} = s(u_{\overline{\mathcal{H}}})$, au contraire, si $s(u) \notin \overline{\mathcal{H}}$, card $(s(yx) \cap \overline{\mathcal{H}}) = w(u_{\overline{\mathcal{H}}}x_{\overline{\mathcal{H}}}^2 + u_{\overline{\mathcal{H}}}) \geq d - e > e$. D'autre part,

$$ (29) \qquad \forall E \in \mathcal{H}, x_E^2 x = x_E \left(x_E + x_E^2\right) = 1 + x_E^2 x_E = x_E^2 = x' $$

De sorte que le critère (28) est applicable également pour $E \in \overline{\mathcal{H}}$ : à chaque application, on examine $s(yx_E^x) \cap E$ et $s(yx_E^x) \cap \overline{E}$.

### Conclusion.

S'il n'y a qu'une erreur, on la corrige en deux étapes au plus (un hyperplan quelconque de $\mathcal{H}$ et son complémentaire).

S'il y a deux erreurs, on peut voir que le nombre de cas où le produit scalaire de $u$ avec chaque vecteur de $\mathbb{F}_2\mathbb{G}$ correspondant à un hyperplan de $\mathcal{H}$ est non nul est $2^{r-1}$. Dès lors, la probabilité pour que ces deux erreurs soient corrigées
par application du premier algorithme est

$$ (30) \qquad \frac{2^r - 2}{2^r - 1} = \frac{n-2}{n-1} $$

Si l'on estime grossièrement, à chaque examen d'un hyperplan $E \in \mathcal{H}$ et de son complémentaire $\bar{E}$, la probabilité de correction de deux erreurs à 1/2, on estime à 2 le nombre moyen d'hyperplans de $\mathcal{H}$ qu'il faut examiner pour corriger deux erreurs.

Si on veut décodeur avec certitude une ou deux erreurs par le premier algorithme, on peut aussi essayer systématiquement, en cas d'échec des 2n applications du critère, les n/2 possibilités restantes pour deux erreurs. Si ceci aboutit à un échec, on est assuré qu'il y a plus de deux erreurs. Observons que pour le code (32,16,8) correcteur de 3 erreurs, en faisant un calcul de probabilité grossier, on peut estimer à $\frac{16.15.14}{32.31.30} = \frac{7}{62}$ la probabilité de trouver les 3 erreurs à chaque application du critère et par conséquent, la probabilité de décodage correct après application des 2n = 64 étapes serait de 0,9995. Le nombre moyen d'hyperplans à considérer serait alors de 4,43. Toutefois, pour des codes plus longs, et pour e > 3, il faut envisager l'échec du premier algorithme. Nous proposons de le faire suivre alors par le

## 2ème Algorithme

Soient $E_0, E_1, ..., E_{t-1}$ les classes latérales d'un sous-espace $E_0$ de $\mathcal{H} \in \mathcal{H}$ et $E_t, ..., E_{2t}$ ses classes latérales dans $\mathcal{G}$ contenues dans $\bar{\mathcal{H}}$. Puisque $\text{Card}(s(x) \cap \mathcal{H}) \equiv 1 \mod 2$, on est assuré de l'existence d'au moins un $E_{t+i}$, $i = 1, ..., t$ tel que $\text{Card}(s(x) \cap E_{t+i}) \equiv 1 \mod 2$. Observons que si $t > 2$, $E = E_1 \cup E_2 \cup ... \cup E_{t-1} \cup E_{t+i}$ n'est pas une variété linéaire puisqu'elle serait alors le complémentaire d'un hyperplan et que la somme de deux quelconques de ses éléments devrait être dans l'ensemble complémentaire dans $\mathcal{G}$. De plus $g+E$ parcourt un ensemble de 2t parties distinctes de $\mathcal{G}$ lorsque $g$ parcourt $\mathcal{G}$. Notre algorithme permettra de trouver le vecteur d'erreurs u lorsque $s(u) \subset \overline{g+E}$, quel que fut le choix de $E_0$.
Montrons d'abord que

$$
(31) \quad \forall z \in (x) , z_E = 0 \Rightarrow z = 0 .
$$

Si $z \in (x)$ avec $x = 1+x_H$, on peut écrire, puisque $\{x^g x\}_{g \in H}$ forme une
base de $(x)$ :

$$
(32) \quad z = \sum_{g \in H} z_g X_g^g x = z_H + z_H x_H = z_H x.
$$

Il suffit donc de montrer que $(z_E = 0) \Rightarrow (z_H = 0)$.
Mais $(z_E = 0) \Rightarrow z_H = z_{E_0}$. Donc, par (32)

$$
(33) \quad z = z_{E_0} + z_{E_0} x_{\bar{H}} = z_{E_0} + z_{E_0} x_{E_t+i} + z_{E_0} x_{\bar{H}} E_{t+i}
$$

expression où l'on voit que z<sub>E<sub>t+i</sub></sub> = z<sub>E<sub>0</sub></sub> x<sub>E<sub>t+i</sub></sub> . Mais puisque s(x) ∩ E<sub>t+i</sub> =
s(x<sub>E<sub>t+i</sub></sub>) a un nombre impair d'éléments x<sub>E<sub>t+i</sub></sub> est une unité de IF<sub>2</sub>G. Donc
(z<sub>E<sub>t+i</sub></sub> = 0) ⇒ (z<sub>E<sub>0</sub></sub> = 0) ⇒ (z<sub>H</sub> = 0). (31) équivaut à dire que (z<sub>g</sub>)<sub>g∈E</sub> est un
ensemble de symboles d'information du mot de code z.

**Décodage** : Soit y le mot reçu entaché d'au plus e erreurs. On sait que si
2 e < d, y s'écrit de façon unique y = z + u où z ∈ (x) et w(u) ≤ e.
On a y_E = z_E ssi s(u) ⊂ E. Nous allons donc calculer l'unique mot de code
z ∈ (x) tel que z_E = z_E et nous serons assurés que c'est bien le mot émis
s'il est à distance ≤ e de y, donc si w(y+z) ≤ e.

**Propriété 10.** Dans les hypothèses ci-dessus, soit
$y' = (y_H + y_{E_0})x$. Alors

$$
(34) \quad z = y' + (y'_{E_{t+i}} + y'_{E_{t+i}}) x_{E_{t+i}} x.
$$

On observe que $y'_{E_i} = y_{E_i}$ pour $i = 1, \dots, t-1$ et que $z \in (x)$.
Notons que $s((y'_{E_{t+i}} + y_{E_{t+i}})x_{E_{t+i}}) \subset E_0$. De plus, le produit de x par un polynomial nôme dont le support est inclu dans $E_0$ a son support dans $E_0 \cup \bar{H}$. Nous sommes donc déjà assurés que $z_{E_i} = y_{E_i}$ pour $i = 1, \dots, t-1$. La preuve sera faite lorsque nous aurons vérifié que pour tout $v \in \mathbb{F}_2^G$, $v_{E_{t+i}} = (v_{E_{t+i}} x_{E_{t+i}} x_{E_{t+i}})$. •

Il suffira en effet de substituer y' et y à v dans cette dernière relation pour obtenir (31).

Or
$$v_{E_t+i} x_{E_t+i} = v_{E_t+i} x_{E_t+i} (x_{E_t+i} + x_{\bar{E}_t+i}) = v_{E_t+i} + v_{E_t+i} x_{E_t+i} x_{\bar{E}_t+i}$$
Puisque $s(v_{E_t+i} x_{E_t+i}) \subset E_0$, on a bien $s(v_{E_t+i} x_{E_t+i} x_{E_t+i}) \subset \bar{E}_{t+i}$, d'où
l'égalité annoncée. ■

## 6. Implementation by F. PREPARATA.

The preceding discussion indicates that the error can be "trapped" with high probability by a strategy consisting of computing the products of the polynomial corresponding to the received word by each member of the previously defined set of "trapping" polynomials. In terms of vectors, a product of polynomials becomes a convolution product. It is then natural, in such a context, to explore the applicability of transform methods.

In our case, the matrix governing the transformation is a $2^r \times 2^r$
Hadamard matrix $H_r$, inductively defined by $H_0 = [1]$ and $H_r = \begin{bmatrix} H_{r-1} & H_{r-1} \\ H_{r-1} & -H_{r-1} \end{bmatrix}$.

It is well-known that the left product of a $2^r$-vector $\mathbf{v}$ by $H_r$, the Hadamard transform of $\mathbf{v}$, can be obtained with $r2^{r-1}$ additions and as many subtractions ; if the components of $\mathbf{v}$ are integers in $\{0,1\}$, then the moduli of the components of $\mathbf{v}H_r$ are bounded by $r$. It is also well-known that the convolution product of $\mathbf{v}$ and $\mathbf{w}$ is the inverse Hadamard transform of the componentwise product of the transforms of $\mathbf{v}$ and $\mathbf{w}$. The inverse Hadamard transform is obtained by multiplying on the right by the same matrix used in the direct transform and dividing the resulting vector by $2^r$.
Thus, we recognize that the convolution product of $v$ and $w$, assuming that the transform of $w$ be available as a library item, can be obtained with $r^2 \cdot 2^{r+1}$ additions/subtractions and $2^r$ multiplications. The operands of the multiplications are represented with $r$ binary digits, whence the componentwise products are to be represented with $2r$ binary digits; it follows that $3r$ binary digits are sufficient for representing the components of the convolution product vector. Division by $2^r$ and subsequent modulo-2 reduction correspond to choosing as result the $(r+1)$-st binary digit of each component. Notice, incidentally, that the operations of the inverse transform need to be carried out on operands of just $2r$ bits, since it is very easy to show that each addition/subtraction involves operands of the same parity; hence each sum/difference is divided by 2, thereby implicitly realizing the required division by $2^r$.

Finally, it is worth mentioning that the operations described above are obviously susceptible of parallel implementation, with $2r$ additive steps and 2 multiplicative step.

It is also natural to adopt the same technique in the encoding process, where a single "library" transform of the generator $g$ will be used in the transform domain and will be multiplied component-by-component by the transform of the information vector.
Bibliographie
==========

[1] P. CAMION, Difference sets in elementary abelian groups, Séminaire de Mathématiques Supérieures de Montréal, (Eté 1977) *Presses de l'Université de Montréal*.

[2] F.J. MAC WILLIAMS, Permutation decoding of systematic codes, *Bell Syst. Techn. J.*, 43 (1964).

[3] F.J. MAC WILLIAMS and N.J.A. SLOANE, *The Theory of Error-Correcting Codes* (North-Holland 1977).

[4] L.D. RUDOLPH and M.E. MITCHELL, Implementation of decoders for cyclic codes, *IEEE Trans. Info. Theory*, 10(1973).

[5] J. WOLFMANN, Aspects géométriques et combinatoires de l'étude des codes correcteurs. *Thèse, Université de Paris 7, Paris (1978).*