L'invention se rapporte au domaine des télécommunica¬ tions numériques, et plus particulièrement au traitement de signal numérique nécessaire dans ce type d'applications .

Les télécommunications numériques sont soumises à des perturbations qui nécessitent une protection efficace de l'infor¬ mation par codage au moyen de codes détecteurs et correcteurs d'erreurs .

Des codes particulièrement intéressants pour ce type de détection et correction d'erreurs sont les codes de type Reed Solomon (RS) ou BCH qui offrent un équilibre raisonnable entre la complexité de mise en oeuvre et l'efficacité . Ces codes font appel à des traitements de polynômes à valeurs dans les corps de Galois .

La demande de brevet français n° 86 14677 au nom de l demanderesse décrit un opérateur polynomial dans les corps de Galois et un processeur de traitement de signal numérique utilisant un tel opérateur. L'élément central d'un tel opérateur est un circuit multiplieur-additionneur effectuant les opéra¬ tions de multiplication et d'addition de polynômes dans les corps de Galois . Le multiplieur-additionneur décrit dans cette demande n'était pas optimisé, tant par le nombre de niveaux logiques nécessaires au calcul que par la surface de l'opéra¬ teur, d'où une durée de calcul et un encombrement trop impor¬ tants . On connaît par ailleurs, par un article de B . A. LAWS

Jr et al intitulé "A cellular-array multiplier for GF(2m) " , pages 1575-1578 du Vol. C20, n°12, Décembre 1971 de IEEE Transactions on computers, un multiplieur-additionneur de type matriciel utilisant une décomposition de l'opération polynomiale P = A*B+C qui effectue un calcul itératif au moyen d'une structure matricielle carrée .

L'invention a pour objet un multiplieur-additionneur programmable dans les corps de Galois simple et paramétrable, à vitesse de traitement plus rapide, cet opérateur pouvant traiter tous les corps de Galois jusqu à CG(2 N ) , N étant déterminé au départ par le concepteur.

Suivant l'invention, un multiplieur-additionneur paramétrable dans les corps de Galois jusqu'à CG(2 ) où N est un entier prédéterminé, à trois entrées multiples destinées à recevoir les coefficients de polynômes opérandes A, B, C, de degré m-1 inférieur à N pour l'opération polynomiale P dans le corps de Galois de degré m, CG(2 ^m ) : P = (A * B) + C, où * et + sont respectivement la multiplication et l'addition, effec¬ tuées Modulo G, dans le corps de Galois CG(2 ) de polynôme générateur G, et une entrée de données paramétrable, pour ce polynôme générateur, comportant :

- un décodeur constitué d'une ligne de N cellules élémentaires identiques CD., ordonnées de j = 0 à N-l, recevant les coefficients du polynôme générateur G(N:0) et transmettant les coefficients de ce polynôme sans celui de degré le plus élevé G(N-1:0) et un polynôme à un coefficient significatif déduit par combinaison logique du polynôme générateur marquant le degré m du corps de Galois choisi, DG(N-1:0) ;

- une matrice de calcul constituée de p lignes de cellules de calcul élémentaires identiques pour effectuer le calcul polynomial en p étapes, les ceEules de la dernière ligne fournissant les termes de degrés 0 à m-1 du polynôme résultat P, est caractérisé en ce que, pour un calcul en p = 2N-1 étapes, la matrice de calcul comporte 2n-l lignes de i = 0 à

2 (N-l) et N colonnes de j = 0 à N-l de cellules CM. . connectées de manière arborescente, les entrées non connectées recevant des niveaux "0" logique, chaque cellule élémentaire de calcul MC. . comportant :

- cinq entrées verticales reliées aux sorties vertica¬ les de la cellule précédente de la même colonne, recevant les termes de degré j, G(j) DG(j) et B(j) du polynôme générateur,

du polynôme degré, et du polynôme B , le terme de degré i-j du polynôme A, et le terme de degré j d'un résultat intermédiaire z (j) , deux entrées latérales recevant de la cellule de la colonne de rang inférieur de la même ligne le terme de degré j-1 du résultat intermédiaire z (j"l) et le terme de degré

(i + 1 - j) , A(i + 1 - j) , du polynôme A,

- deux sorties latérales à destination de la cellule de rang supérieur de la même ligne fournissant le terme de de¬ gré j du résultat intermédiaire z (j) et le terme de degré i-j, A(i-j) du polynôme A.

L'invention a également pour objet l'utilisation d'un tel multiplieur-additionneur, programmable dans les corps de Galois, dans un processeur de traitement de signal numérique .

L'invention sera mieux comprise et d'autres caractéris- tiques apparaîtront à l'aide de la description qui suit en réfé¬ rence aux figures annexées .

La figure 1 est le schéma synoptique d'un type de multiplieur-additionneur dans le corps de Galois ;

La figure 2 est un schéma du décodeur du polynôme générateur ;

La figure 3 est un schéma de la cellule élémentaire de ce décodeur ;

La figure 4 est le schéma d'un mode de réalisation de la matrice de calcul selon l'art antérieur ; La figure 5 est le schéma de la cellule logique élémen¬ taire correspondante ;

La figure 6 est le schéma de la cellule logique élémen¬ taire utilisée dans la matrice de calcul selon l'invention ;

La figure 7 est le schéma de la matrice de calcul selon l'invention.

Un corps de Galois est défini par sa taille, c'est-à-dire par le nombre de bits des opérandes à traiter, et donc des résultats obtenus, et par son polynôme générateur . Soient A, B, et C trois polynômes d'un corps de Galois, et G son polynôme générateur :

G est le polynôme binaire de degré m générateur du corps de Galois correspondant, qui fixe la taille du corps de Galois dans lequel sont réalisées les opérations polynomiales ; A,B,et C sont aussi des polynômes binaires de degré m-1. Soit z l'élément générateur du corps de Galois qui est racine du poly¬ nôme générateur ^* G de degré m : l'élément nul et z ¹ de i = 0 à 2 - 2 sont les 2 éléments du corps de Galois CG(2 ^m ) et sont les M = 2 symboles de m bits utilisés pour la transmission. Toute opération dans ce corps génère nécessairement un élément du corps, et ces opérations peuvent s'écrire de manière générale :

^P = < ^A * ^B ulo G ^{+ C} où * est la multiplication dans le corps de Galois (utilisant des opérations élémentaires ET logique) et où + est l'addition dans le corps de Galois (OU exclusif logique) , '

Par simple décomposition, comme décrit par exemple dans l'article précité, les polynômes A,B, C et G peuvent

m-1 i . _r J2- _-,- ¹ = 0- m-1 ⁱ r - <=""_: ^c i ^z ' ^{ϋ "} _

Le coefficient de degré m le plus élevé du polynôme G est tou¬ jours ég.al à 1 : g_ m = 1.

En conséquence le résultat P peut être présenté de la manière suivante :

- » _. <Λ-' modulo G i=0

Le résultat P développé donne alors : P=C ^• + b _n 0A _Λ 0 + b 1_,A1.. +...b 1.A1. + ...+b m-1 _.A m-1 _.

Le calcul du produit se décompose en une somme de pro¬ duits partiels successifs : P-1 ^{= C P} 0 = ^P -l ^{+ b} 0 ^A 0 . _Pl = P _{Q +} b.A,

P m-1 , = P m-2 ^{+ b} m-1 , m-1 , = P.

Le calcul des A. s'exécute suivant la séquence suivante : A _Q = A

^(A i-l ^z) modulo G

- Si le terme de plus haut degré est égal à 0 :A.=A.__.z

- Si le terme de plus haut degré est non nul : A. = A. _.z + G. ^β i î-l

Ces deux expressions peuvent être écrites simultané¬ ment, sous la forme : A.=A._ ₁ z+(G AND A.^ m-l)) (2) avec A. (m-1) coefficient du terme de degré le plus élevé du polynôme A. , .

D'une manière générale un multiplieur-additionneur utilise les expressions décrites ci-dessus pour effectuer les opérations nécessaires au codage et au décodage dans un corps de Galois CG(2 ) où m est programmable jusqu'à m = N au moyen d'une structure matricielle : La figure 1 est le schéma synoptique d'un tel multiplieur-additionneur. Il se compose de deux parties essentielles :

³ - un décodeur 10 du polynôme générateur G, qui a pour ^" entrée le polynôme générateur G (sur N+l fils) de degré m compris entre 0 et N, N étant le degré maximal du corps de Galois dans lequel le multiplieur-additionneur est susceptible de travailler, et pour sortie le même polynôme générateur, mais sans son bit de plus fort poids qui n'est pas nécessaire au calcul, soit G(N-1:0) (sur N fils) et également comme autre sortie un polynôme degré, DG qui marque le terme de degré m du polynôme générateur du corps de Galois utilisé ;

- Une matrice de calcul 20, qui a pour entrées les opérandes polynomiaux A, B, C, ainsi que les sorties du déco¬ deur, G(N-1:0) , et DG(N-1:0) , et pour sortie le résultat P, ses différentes entrées et sorties étant des liaisons à N fils. La notation G(N:O) indique une liaison à N+l fils numérotés de 0 à N transmettant les différents coefficients du polynôme générateur G. La notation G(i) indique une liaison à 1 fil transmettant le coefficient de degré i du polynôme généra¬ teur G. Cette notation est utilisée ci-après et sur les figures pour les différentes entrées et sorties des circuits utilisés .

Le décodeur 10 du polynôme générateur est représenté plus en détails sur la figure 2. Il est constitué de N cellules élémentaires identiques CD ₀ , CD.. , . . . , CD., . . . CD-, .. , et sa fonction consiste comme indiqué ci- des sus à transmettre les termes de degrés m-1 à 0 du polynôme générateur G vers la matrice de calcul et à détecter le degré de ce polynôme généra¬ teur.

La cellule de degré j, CD. du décodeur, est représen¬ tée en détails sur la figure 3. Cette cellule élémentaire com-

porte une entrée recevant le coefficient de degré j du polynôme générateur, G(j) , et deux entrées reliées aux sorties de la cellule adjacente de degré j+1, G(j+1) et DD(j+l) . A partir de ces trois entrées, la cellule du décodeur transmet le coeffi¬ cient de degré j, G(j) d'une part à la cellule du décodeur de rang inférieur CD. - , et d'autre part à la sortie, à destination de la matrice de calcul 20. Elle forme le terme DD(j) au moyen d'une porte OU, 11, dont les deux entrées sont reliées aux liaisons DD(j+l) et G(j+1) et dont la sortie est DD(j) , et elle forme le terme DG(i) au moyen d'une porte ET dont une entrée reçoit G(j+1) et dont l'autre entrée, inversée reçoit DD(j+l) . En sortie, le bit mis à 1 dans DG(N-1:0) pour indiquer le degré est le bit de rang m de G prélevé dans la cellule de rang m du décodeur du polynôme générateur. Le polynôme DG(N-1 :0) n'a que son coefficient de rang m-1 égal à 1 et G(N-1:0) est sembla¬ ble à G(N:0) sans son coefficient de rang N :

X représente 0 ou 1 suivant le corps de Galois dans lequel sont effectués les calculs . A titre d'exemple pour CG(2 ) soit m = 4, G = (10011) que l'on écrit aussi sous forme polynomiale G(X) = X ⁴ + X + 1 et DG = (01000) .

Dans un mode de réalisation connu par l'article préci¬ té, la matrice de calcul 20 est constituée d'un assemblage de cellules élémentaires identiques en N lignes de N cellules, formant N colonnes, le matriçage assurant automatiquement l'in¬ terconnexion des cellules.

Le schéma d'une telle matrice de calcul est représen¬ té sur la figure 4, où les cellules CC. . sont indexées par les l . J rangs des lignes et des colonnes auxquelles elles appartiennent. ^• Une ligne horizontale traite un mot, c'est-à-dire un polynôme .

Elle reçoit de la ligne précédente de rang i-1- les résultats intermédiaires A î.-l _, et P î.-l _. définis ci-dessus ', ainsi q ^ue le polynôme générateur G(N-1:0) et le degré du polynôme générateur DG(N-1:0) et fournit à la ligne suivante A., P., G et DG. Les bits b. du polynôme B sont distribués chacun sur une ligne horizontale B (i) .

Chaque cellule sur une ligne i traite 1 bit. La cel¬ lule CC. . située sur la ligne de rang i et sur la colonne de rang j reçoit de la cellule adjacente de la ligne précédente i-1, les bits de rang j du polynôme A.__. , du polynôme DG, du polynôme G et du polynôme P. - , soient A.__. (j) , DG(j) , G(j) , et P._, (j) . Elle reçoit également de la cellule adjacente de la colonne j-1 le terme A.__. (j-1) et transmet à la cellule adjacente de la colonne j+1 A.__. (j) . Enfin une liaison horizontale transmet le terme de rang i de B, B(i) à toutes les cellules de la ligne et une autre ligne R. fournit une information décrite ci-après -à toutes les cellules de cette même ligne.

La cellule élémentaire d'un tel mode de réalisation de la matrice de calcul est représentée sur la figure 5. Les différents bits ainsi appliqués à une cellule sont combinés logiquement au moyen de 5 portes élémentaires de la manière suivante :

- une porte trois états 21, reçoit A.__. (j) et son en- trée de validation reçoit DG(j) . Cette porte impose à sa sortie le bit A.__. (j) seulement pour la colonne j=m-l où DG(j)=l, soit A. - (m-1) ; la sortie de la porte trois états est reliée à la liaison entre cellules de la ligne i, R..

- une porte NON ET, 22 et une porte OU exclusif inver- sée 23 génèrent le résultat

A.(j)=A._ ₁ (j-l) + G(j) A.^m-l) , ce qui pour une ligne complète correspond à l'équa¬ tion (2) mentionnée ci-dessus : pour cela les entrées de la porte 22 sont reliées aux lignes G(j) et R., et sa sortie est

reliée à une entrée de la porte 23 dont l'autre entrée reçoit A.__. (j-1) ; la sortie de la porte 23 fournit A. (j) .

- une porte NON ET 24 et une porte OU exclusif inver¬ sée 25 génèrent le résultat P.(j) = P.^Q) + B (i)A. (j) , ce qui pour une ligne complète correspond à l'équation (1) mentionnée ci-dessus : pour cela la porte 24 reçoit B (i) et A. (j) sur ses deux entrées et sa sortie est reliée à une entrée de la porte 25 dont l'autre entrée reçoit P._- (j) . Les bits G(j) et DG(j) sont transmis à la cellule adjacente suivante de la même colonne.

Comme indiqué ci-dessus, P_-, ⁼ C, c'est-à-dire que les entrées P._ . des cellules de la première ligne (rang 0) reçoivent les termes C(j) du polynôme C comme représenté sur la figure 4. Enfin les sorties P(N-1:0) des cellules de la N ièmθ ligne sont les sorties de résultat.

Pour que le résultat du calcul obtenu à la dernière ligne de la matrice soit significatif, il faut que tous les opérandes A, B, C aient des degrés strictement inférieurs à celui du polynôme générateur G.

La caractéristique essentielle d'un tel type de multi¬ plieur-additionneur, telle qu'elle ressort de la description ci-dessus du premier mode de réalisation, est qu'après décodage du polynôme générateur G, de degré au plus égal à N, et utilisa- tion d'une matrice de cellules élémentaires identiques, il est possible d'effectuer des calculs dans tous les corps de Galois jusqu i à CG(2 N ) . Ce mode de réalisation utilise une matrice de cellules élémentaires, de dimensions NxN, le schéma logique de la cellule comportant une porte 3 états, deux portes NON ET et deux portes OU exclusifs, et des interconnexions entre cellules telles que définies ci-dessus .

Mais, dans ce mode de réalisation de type connu, le polynôme générateur intervient à chaque étape dans le calcul des

Ai ; ce qui conduit à des temps de calcul importants .

L'invention a pour objet un multiplieur-additionneur paramétrable dans les corps de Galois dans lequel la vitesse de traitement est privilégiée, cet opérateur est décrit ci-après en référence aux figures 6 et 7, à partir d'une analyse différente : Le produit P=(A*B) , , _G +C peut s'écrire de la manière suivante :

fam-1) ^{uio G}

^{a ec z} o ^{= a} o ^b o

Z ₁ = a ₀ b _1+aι b ₀

Z m- ₁ 1 = a m-1 _,b m-1 _. e calcul des z est effectué de la manière suivante : z =1

(z ) , . ≈ z.z si le terme de poids fort est nul

(z ) j . „ = z. z +G si le terme de poids fort n'est pas nul.

Le calcul des Z. est réalisé directement au moyen d'une matrice de cellules élémentaires dans laquelle les cellu¬ les utiles au calcul sont organisées et reliées suivant une structure arborescente pour qu'à chaque ligne i, on dispose du résultat intermédiaire Zi, des zones de câblage entre lignes et entre colonnes étant prévues dans la matrice comme décrit ci-après .

Le schéma logique de la cellule élémentaire MC. . utilisée est représenté sur la figure 6, la matrice de calcul

utilisant une matrice de N colonnes et 2N-1 lignes de cellules telles que celle représentée sur la figure 6.

La cellule élémentaire MC. . de la colonne i (j entre

0 et N-l) et de la ligne i(i entre 0 et 2N-2) a 5 entrées verticales respectivement pour B (j) , z ¹ (j) , DG(j) , G(j) et

A(i-j) . L'entrée z (j) est utilisée pour la cellule adjacente d'une sortie horizontale , ) de la cellule adjacente de la colonne j-1, MC. . _. . ι,J"l Comme dans la cellule élémentaire de calcul décrite antérieurement, une porte trois états 21 reçoit z (j) , comme précédemment A._. (j) et est activée par DG(j) . La seule porte activée est celle correspondant au degré le plus élevé du poly¬ nôme générateur, m-1, qui transfère z (m-1) sur la liaison horizontale R. traversant toutes les cellules de la ligne i.

Cette sortie est reliée à l'entrée de la porte NON ET 22 dont l'autre l'entrée reçoit G(j) et dont la sortie est reliée à une première entrée de la porte OU exclusif inversée 23 ayant son autre entrée recevant z (j-1) de la cellule de rang précédent de la même ligne, et qui délivre sur une sortie verticale z (j) .

De plus, chaque cellule comporte une porte ET, 26 relié aux entrées verticales A (i-j) et B (j) pour le calcul d'un terme A(i-j) B (j) et une porte OU exclusif 27 dont les entrées et la sortie sont prises verticalement dans une première zone de câblage inter cellule s, horizontale, située au bas de la cellule pour le calcul des produits partiels Z.= <fx A(i-j) B(j) à partir des résultats intermédiaires . . A (i-j) B (j) . . .

- De plus, chaque cellule comporte de la même façon une seconde porte ET 28 dont une entrée est reliée à la sortie de la porte OU exclusif inversée 23 qui fournit z (j) , et dont l'autre entrée est reliée à la liaison intercellules d'une même ligne dans la zone de câblage horizontale, Z. , la sortie de cette porte ET 28 étant amenée à une zone de câblage verticale dans laquelle peut être calculée pour une colonne, P(j) = ^- Z.z ¹ (j) . Pour cela chaque cellule comporte en outre

une porte OU exclusif 29 qui prend ses entrées dans la zone de câblage verticale et dont la sortie est ramenée dans cette même zone de câblage.

- Enfin deux liaisons "obliques" , sont prévues dans la cellule, l'une à partir de l'entrée verticale A (i-j) transmet ce bit A (i-j) par une connexion horizontale de sortie à la cellule de rang j+1 de la même ligne i, et l'autre transmet à partir de l'entrée A(i+l-j) provenant de la cellule précédente de la même ligne par une entrée horizontale, ce bit sur une sortie verti- cale A(i+l-j) de la cellule MC. . à destination de la cellule ι,J suivante de la même colonne MC. ₊₁ . ; ces liaisons permettent de constituer la structure arborescente utile dans l'interconnexion des cellules élémentaires ainsi décrites, comme représenté sur la figure 7. Cette figure 7 représente la matrice de calcul corres¬ pondante pour un mode de réalisation où N = 4. Cette matrice comporte donc N = 4 colonnes (soit j = 0 à 4) et 2N-1 = 7 (soit i = 0 à 6) lignes de cellules élémentaires avec des zones d'in¬ terconnexion horizontales et verticales entre cellules d'une même ligne ou d'une même colonne. Par souci de simplification, les liaisons entre cellules n'ont pas toutes été représentées : seules ont été représentées les liaisons obliques qui mettent en évidence la structure arborescente de la matrice pour le calcul des produits a. .b., et les liaisons entre cellules réalisées dans les zones de câblage horizontales et verticales réservées à cet effet pour le calcul

- des produits partiels Z. = ^"a. _.b. et des termes P(j) = ^- Z.z (j)

- du produit résultat P(N-1:0) .

Les notations du type a. .b. utilisent les coeffi- cients des polynômes tels que définis initialement, et, les notations du type A(i-j)BQ) correspondent aux opérations réali¬ sées avec les coefficients présents sur les entrées des matrices telles que définies ci-dessus. Ces notations sont à peu près équivalentes si ce n'est que lorsque l'on travaille dans un corps de Galois de degré inférieur au degré maximum possible,

certaines entrées du type A(i) , B (j) , C(j) reçoivent des coeffi¬ cients nuls .

Il résulte de ce qui précède que certaines cellules élémentaires ne sont pas utiles aux calculs des a. . b. . C'est i-J J le cas des cellules élémentaires MC. . pour i inférieur à i et i i supérieur ou égal à j+4. Pour rendre la matrice strictement répétitive, ce qui facilite les procédés de fabrication correspondants , ces cellules n'ont pas été supprimées , les por¬ tes élémentaires inutiles sont rendues inopérantes par câblage de leurs entrées à un niveau inactif .

Ainsi comme il ressort de la description ci-dessus , le multiplieur-additionneur est paramétrable, par le polynôme géné¬ rateur dont la valeur code l'ordre m du corps de Galois dans lequel sont effectuées les opérations polynomiales, m étant au plus égal à N.

L'opérateur utilise alors une matrice de calcul dont la taille est fonction du paramètre N ; cette matrice . utilise une seule cellule de base pour les calculs et reçoit les données caractérisant le corps de Galois dans lequel sont effectuées les opérations par une matrice 1 x N constituée elle aussi d'un seul type de cellule .