par Michael Zaus

(traduction : Gérard A. Langlet. Rapport original en anglais, daté du 14 février 1996)

Cet article a pour but de fournir une vue d’ensemble de l’espace binaire Bⁿ et des concepts associés, en particulier de l’opération de OU_Exclusif  (XOR) x Å y  ainsi que sa généralisation à l’intégrale scalaire binaire  Åⁿ_i=1 x_i  et à l’intégrale vectorielle binaire �ⁿ_i=1 x_i  pour les vecteurs x Î Bⁿ. Nous présentons ces fondements mathématiques selon une nomenclature standard en informatique, mais nous nous rapporterons aussi à la nomenclature d’APL, car l’intégrale vectorielle binaire, exposée dans la section 2.3 tire son origine d’APL ([IVE62], [IVE78], [LAN93], [LOC89], [ZA95]).

2.1  L’Espace Bⁿ = {0,1}ⁿ

Les objets à étudier essentiellement en logique de la parité sont des vecteurs de dimension n contenant des composantes binaires. Selon le contexte, ces vecteurs peuvent avoir une signification différente; ils comprennent des points, des motifs, des mots, des items de mémoire, des données, des paramètres, des chromosomes artificiels, des images, des événements, des ensembles flous, des signaux de télévision, des signaux corporels (EEG, ECG, EOG etc...), des vecteurs d’état de milieu excitable, et bien plus encore. Les représentations de ces entités sont basées sur l’espace Bⁿ  que nous obtenons par produit cartésien n-uple sur B = {0,1} :

Bⁿ = B  ´ B . . .  ´ B

n  fois

En développant l’espace Bⁿ = {0,1} on obtient l’ensemble des vecteurs binaires à n dimensions :

(1)           Bⁿ = {x : x = (x₁ , x₂, ..., x_n); x_i Î {0,1}; i = 1, 2, ..., n}

Le nombre de points dans Bⁿ  est 2ⁿ. Du fait que la représentation binaire des entiers sur n chiffres binaires dans l’intervalle [0, 2ⁿ] s’identifie avec les éléments de Bⁿ , on peut les considérer comme identiques, à condition que ceci ait un sens pour une application spécifique. Par exemple, dans les algorithmes génétiques et l’optimisation de fonctions, l’ensemble B  = {0,1} est un alphabet de symboles et l’application e : Bⁿ® D  est une fonction de codage pour un certain domaine discret et fini D . Le codage des éléments de D est une application à partir des chaînes (chromosomes artificiels) de longueur n de B vers D, et Bⁿ est appelé l’espace de recherche. La dimension n de l’espace dépend strictement de la précision requise pour la fonction soumise à optimisation (ZA95c]).

Dans d’autres domaines d’appplications, par exemple dans les réseaux de neurones, en particulier les modèles de mémoire distribuée de manière peu dense, les éléments de Bⁿ peuvent toujours s’écrire comme des entiers à n bits, en représentation binaire, p. ex. 1001 ... 0111, mais ils représentent ici des items de mémoire en termes de motifs de zéros et de un à n composantes, sans que l’on assigne une signification spécifique aux composantes, du fait que ce sont des caractéristiques abstraites. Ici, Bⁿ doit avoir une grande dimension de sorte que la mémoire soit répartie de façon peu dense dans le modèle à mémoire distribuée.

Un espace à relativement basse dimension Bⁿ est utilisé dans la pratique courante des puces floues en technologie VLSI. Ici, 0 ou bien 0000 représente une non-appartenance, tandis que 15 ou bien 1111 représente une appartenance complète. Les autres nombres intermédiaires sont utilisés pour représenter des points équidistants dans l’intervalle unité [0,1] selon la progression 1/15, 2/15, ... 14/15. Chaque vecteur de quatre bits représente donc un degré de flou entre 0 et 1, et si l’univers du discours d’un ensemble flou est discrétisé en 31 éléments, il en résulte une quantification en 124 bits de la fonction d’appartenance ([WAT92]).

Un autre exemple concerne l’analyse de signaux binaires, où les éléments de Bⁿ représentent des coefficients binomiaux modulo 2 lesquels à leur tour représentent des fonctions standard du temps (composantes spectrales). L’espace sous-jacent (Bⁿ, N) est alors utilisé pour déterminer des fonctions discrètes du temps, c’est-à-dire des signaux binaires.  Ceci sera développé dans les sections suivantes. Le triangle de Pascal modulo 2, sa complétion en un carré de Pascal, ainsi que son identification avec la matrice S d’Iverson et avec la matrice retournée de Langlet appelée pariton va jouer un rôle central ([BOP81], [IVE62], [LAN92a], [ZA95b]).

Le fait de considérer les éléments de Bⁿ comme des entiers est certainement plus une exception qu’une règle, au vu de ces exemples et de ceux donnés au début de cette section. L’espace Bⁿ a plein de structure, et cela dépend de l’introduction de relations et d’opérations dans Bⁿ. Afin de fournir une base convenable pour effectuer de la modélisation à l’aide d’espaces binaires, il est avantageux de caractériser une paire de structures intimement associées dans Bⁿ avant de passer à un traitement plus détaillé de ses opérations et de ses opérateurs.

D’abord, la paire áBⁿ ,£ñ est un ensemble partiellement ordonné, où la relation £ est réflexive, antisymétrique et transitive. Dans Bⁿ, l’ordre partiel de la relation £ est défini comme des points ou des coordonnées (bit à bit) selon :

(2)                               x £ y = (x₁ £ x₂, ... x_n  £  y_n) .

Ainsi, de manière à être partiellement ordonnés, les vecteurs x et y doivent satisfaire l’une des égalités  0 £ 0,   0 £ 1, ou 1 £ 1. La paire áBⁿ,£ñ  est importante pour des ordres métriques de la représentation de Bⁿ par des diagrammes de Hasse  qui permettent des représentations spatiales de Bⁿ.

Ensuite, si l’on introduit dans Bⁿ  les opérations  d’intersection (Ù) , d’union (Ú) , de complémentation (^-) ainsi que les définitions point à point telles que :

(3)                               x Ù y = (x₁ Ù y₁, ...,  x_n Ù y_n )

(4)                               x Ú y = (x₁ Ú y₁, ...,  x_n Ú y_n )

(5)                                     x = (x_1,  x₂, ...,  x_n ),

nous obtenons une algèbre booléenne áBⁿ, Ù, Ú, ^- ñ. Cette structure est importante, mais moins intéressante pour les systèmes binaires dynamiques en général, et pour la représentation de signaux binaires et leur analyse en particulier. En ce qui concerne ces derniers, nous avons besoin de concepts métriques et topologiques dans Bⁿ , spécialement d’applications préservant les distances, c’est-à-dire des isométries et des déplacements, en particulier des réflexions, des rotations et des translations. En outre, il faudra des opérations préservant l’entropie pour des propagations, résistant à l’erreur, de différences concernant les signaux et les transformées de ces signaux dans Bⁿ.

Ces conditions nécessaires peuvent se trouver satisfaites par au moins trois approches, surtout par le passage naturel aux anneaux booléens, ou par le passage plus radical à des groupes finis binaires ou même à des corps de Galois en algèbre modulo 2 ([BOP81], [LAN92b, [AIG93]). Nous nous restreindrons à une brève caractérisation de la première option en faisant ressortir le passage de áBⁿ , Ù, Ú, ^- ñ vers un anneau booléen.

Le concept central de ce passage est XOR, l’opération de OU-eXclusif (en anglais « eXclusive-OR »), définie selon la loi de de Morgan par

(6)                               (x Å y) = [(x Ù y) Ú (x Ù y)] = (x ¹ y) .

Remarquer que nous avons défini XOR en utilisant la notation Å aussi bien que ¹ . Cela ne devrait pas constituer une surprise pour le lecteur que OU-exclusif (XOR) et différent soient des concepts synonymes. Nous mettons l’accent sur ce fait, car ce n’est pas seulement une affaire de notation mais aussi une affaire de sens. XOR représente la parité, le concept permettant de distinguer une grandeur paire d’une grandeur impaire, comme nous le montrerons plus loin. Si inégal a le sens de différent, alors non inégal a le sens d’équivalent, et c’est précisément le sens de la définition par la dualité de la loi de de Morgan :

                                    _____

(7)                               (x Å y) = [(x Ú y) Ù (x Ú y)] = (x =y) .

Ainsi, les définitions (6) et (7) utilisent la dualité des lois de de Morgan, et le fait de penser à XOR comme ¹ va apporter un fondement formel d’une manière élégante avec des concepts nouveaux et généralisés. En notation standard, la définition ponctuelle de XOR dans Bⁿ est donnée par

(8)                               (x Å y) = (x₁ Å y₁ , Ù ... , x_n Å y_n ) ,

et en posant x ^. y  = x Ù y  en incluant sa définition ponctuelle, on obtient finalement :

(9)                                        B R (n) = áBⁿ ,Å,^.ñ ,

c’est-à-dire un anneau booléen avec identité, du fait que la propriété x^.x = xx = x est satisfaite pour tous les éléments de x Î Bⁿ . Théoriquement, on peut toujours repasser de áBⁿ, Ù, Ú, ^- ñ à áBⁿ ,Å,^.ñ , et vice-versa, car nous pouvons toujours recapturer les opérations d’intersection (Ù), d’union (Ú) et de complément (^-) par x Ù y = x ^. y, x  Ú y = x  Å y  Å (x ^. y) et x  = 1  Å x  . L’intérêt des anneaux booléens provient du fait que l’opération Å nous permet d’introduire des fonctions de distance, des propriétés de réversibilité, des applications congruentes ainsi que le groupe des déplacements dans Bⁿ . Remarquer encore que l’algèbre áBⁿ, Ù, Ú, ^- ñ nous permet aussi d’introduire l’opération x ‚ y = x Ù y, appelée soustraction booléenne. Une « symétrisation » de la différence x ‚ y  s’obtient par (x ‚ y ) Ú (y ‚ x) , mais ceci est équivalent à x Å y  , d’où à XOR. L’équivalence des expressions

(10)          (x  Å y ) = [(x Ùy) Ú (x Ùy)] = [(x ‚y) Ú (y ‚ x )] = (x ‚ y )

est aisément confirmée et est une caractéristique bien connue pour les anneaux booléens et l’algèbre binaire. Ainsi, les deux opérations Å et ‚ sont identiques dans les anneaux booléens áBⁿ ,Å,^.ñ , et XOR est bien l’opération principale des modèles basés sur l’espace Bⁿ.  Ainsi, nous avons montré comment l’algèbre áBⁿ, Ù, Ú, ^-ñ détermine l’anneau booléen áBⁿ ,Å,^.ñ. Cette étape nous rend capables d’appliquer la théorie algébrique des anneaux à l’étude des modèles dans Bⁿ.

2.2  Propriétés fondamentales de XOR

La caractérisation de l’espace Bⁿ et de ses structures nécessitait de connaître plusieurs propriétés de XOR. Le but de cette section consiste à donner une vue plus systématique de cette opération. La section 2.3 présente sa généralisation à l’intégrale binaire scalaire et à l’intégrale binaire vectorielle. La plupart de ces propriétés sont exprimées dans des théorèmes, des lemmes et des corollaires dont les preuves sont données dans Zaus ([ZA95c]). Le lecteur peut utiliser cette section comme un guide pour explorer XOR, ou comme référence pour les sections suivantes. Rappelons d’abord la définition de XOR :

Définition 2.1             (x Å y) = [(x Ù y) Ú (x Ù y)] = (x ¹ y)

Théorème 2.1  L’opération Å a les propriétés suivantes pour tout x, y, z, w Î Bⁿ :

                (2.1.1)         x Å y  = y Å x                                       commutativité

                (2.1.2)         x Å 0 = x    

                (2.1.3)         x Å x  = 1

                (2.1.4)         x Å (y Å z) = (x Å y) Å z                          associativité

                (2.1.5)         (x Å y ) Å (z Å w) = (x Å z) Å (y Å w)       bisymétrie

                (2.1.6)         x Ù (y Å z) = (x Ù y) Å (x Ù z)                  distributivité

                (2.1.7)         x Å x  = 0

                (2.1.8)         x Å y  =  x Å z Þ y = z                               annulation

                (2.1.9)         1 Å y  =  x                                                complément

Le Théorème 2.1 recouvre des propriétés structurales importantes de XOR. La  bisymétrie du théorème (2.1.5) résulte de (2.1.1) et de (2.1.4) et est la propriété la plus importante de XOR, à cause du fait que l’on peut échanger les termes à gauche ce qui produit une permutation équivalente à droite. La bisymétrie correspond à la loi de la conservation de l’entropie, et un examen plus approfondi de XOR montre qu’il s’agit effectivement d’une opération préservant l’entropie. Par exemple, si x, y, z et w  sont des signaux ou des vecteurs d’états, alors le vecteur résultant u = (x Å y ) Å (z Å w) demeure invariant si on réordonne les termes deux à deux. Ceci est généralisable au cas n-symétrique. XOR est manifestement une opération isentropique.

Des mesures élémentaires pour définir le poids des vecteurs binaires ou des distances entre les vecteurs sont introduites comme suit ([BASS83], [BOP81], [LAN92a]) :

Définition 2.2  La masse totale de x est dim (x), le nombre de composantes de x.

Définition 2.3  La masse pesante mp (x) est le nombre de 1 dans x, c’est-à-dire ||x ||₁ = Sⁿ_i=1 x_i .

Définition 2.4  La masse cachée mc (x) est le nombre de zéros dans x, c’est-à-dire ||x ||₀ = Sⁿ_i=1  1 Å x_i .

Les deux dernières mesures sont utilisées pour déterminer la majorité M (x); c’est une fonction caractéristique définie par :

La notation indique que la masse pesante est la norme de x, tandis que la masse cachée est la conorme de x, car la première est aussi la distance à l’origine 0, tandis que la dernière est la distance de son complément au sommet 1. Les deux mesures admettent des relativisations, le taux de norme (||x ||₁ ¸ n) et le taux de conorme (||x ||₀ ¸ n). Ces grandeurs sont parfois plus informatives que la seule majorité M (x). Ceci sera démontré sur des exemples numériques. Pour établir une relation entre ces mesures et la métrique de Bⁿ, nous avons besoin de la fonction de distance suivante.

Définition 2.5  Pour deux vecteurs quelconques x,y Î Bⁿ, leur distance est définie par

                                         _{n                     n}

(12)                    d (x,y) = S (x_i Åy_i ) = S (x_i ¹ y_i )

                                       _{i = 1                 i = 1}

La définition 2.5 définit la distance de Hamming bien connue entre deux vecteurs binaires, c’est-à-dire le nombre de dimensions par lesquelles x et y diffèrent. C’est un produit interne généralisé, appelé le produit interne « somme-Ou_exclusif » x +.¹ y  en APL. Le théorème suivant montre que la fonction de distance d (x,y) a toutes les propriétés de la fonction commune de distance dans l’espace euclidien avec l’exception de la propriété d’être un nombre réel non négatif.

Théorème 2.2   Dans Bⁿ la fonction de distance d (x,y) satisfait les propriétés suivantes :

                (2.2.1)         x = y  ®      d (x,y) = 0             non négativité

                (2.2.2)         x ¹ y  ®      d (x,y) ¹ 0             positivité

                (2.2.3)         d (x,y)  =     d (y,x)                   commutativité

                (2.2.4)         d (x,y)  £     d (x,z) + d (z,x)      inégalité du triangle

Nous sommes maintenant prêts à présenter quelques exemples numériques qui expliquent les concepts précédents à titre comparatif.

Exemples          La Table 1 concerne n = 6 avec B ⁶,  x =100100 et y =111101

Table 1

Remarquer que la norme et la conorme dans les exemples 2 et 3 ont pour somme la dimension de x dans l’exemple 1. L’exemple 4 montre que les distances et les normes entre deux vecteurs binaires sont identiques. Les exemples 5 - 7 montrent que les mesures relatives peuvent être plus informatives que la fonction majorité M. L’exemple 8 montre la condition d’orthogonalité pour des vecteurs binaires et l’exemple 9 les compléments de x et de y.

Le théorème suivant établit la propriété de réversibilité de XOR. En patrticulier, une opération est logiquement réversible si on peut toujours déduire les données à partir des résultats. L’intersection (Ù) et l’union (Ú), par exemple, sont des opérations irréversibles, tandis que le complément (^-) est réversible, c’est une involution. La réversibilité de XOR va jouer un rôle important pour l’intégrale vectorielle binaire ci-dessous, mais discutons d’abord de l’importance du Théorème 2.3 et du Corollaire 2.1 en ce qui concerne les différentielles binaires.

Théorème 2.3   Si x,y Î Bⁿ avec x Å y = z, alors y = x Å z et x = y Å z .

Corollaire 2.1   Si x,z Î Bⁿ , alors il existe exactement un seul y Î Bⁿ  de telle sorte que x Å y = z .

Le théorème et son corollaire montrent que Bⁿ a trois entités distinctes : (a) des sommets x Î Bⁿ , (b) des directions dx Î Bⁿ et (c) des côtés (x, dx) Î Bⁿ . Considérez maintenant les tables 2a et 2b ci-après :

     Table 2a                                                                                         Table 2b

Le fait que les deux tables présentent la table de vérité de XOR n’est pas le point central. L’important c’est que la table 2a montre la partie-si du théorème 2.3 pour les composantes x_i , y_i , z_i Î x, y, z Î Bⁿ de sorte que x_i et y_i sont considérées comme des variables binaires indépendantes. La preuve de y_i  = x_i Å z_i  est basée sur l’implication :

    ((x_i Å y_i = z_i) et (x_i Å y_i = z_i)) ® ((x_i Ù y_i)=(x_i Ù z_i) et (x_i Ù y_i)=(x_i Ù z_i)) .

Ainsi, y_i  = (x_i Ù z_i) Ú (x_i Ù z_i) = (x_i Å z_i). De la même manière, on prouve que x_i =y_i Å z_i .  De là, le fait d’échanger l’entrée et la sortie (les données et les résultats) montre que XOR est une opération réversible.

Le Corollaire 2.1, d’un autre côté, révèle l’existence de différentielles binaires uniques. Ceci est le message de la table 2b ci-dessus. Le vecteur  z = x Å y  dans le corollaire 2.1 est appelé la différence de x et de y . Maintenant, soient x, x^* Î Bⁿ deux vecteurs distincts, alors dx = x Å x^*  est un nouveau vecteur dx = (dx₁, dx₂, ..., dx_n). Il est engendré point à point par XOR et est appelé la différentielle dx. Puisque dx définit une direction dans Bⁿ , il s’agit d’un vecteur d’orientation qui décrit le changement de x en x^* à chaque coordonnée x_i  Î x.  Avec x, il constitue un côté (x, dx) dans Bⁿ qui pointe en x^*. Finalement, puisque dx = x Å x^* implique x^*= x Å dx  par le théorème 2.3, nous reconnaissons les relations entre les tables 2a et 2b comme indiqué pour les composantes x_i , dx_i et x_i^* . Ceci établit l’existence de différentielles binaires uniques.

Pour donner un autre exemple soit x valant 0101 et soit x^* valant 1100. Alors dx = 1001. Remarquer que dx contient en chaque coordonnée dx_i  la parité des coordonnées respectives x_i  et x_i^*. Ceci montre que chaque différentielle binaire est aussi la différentielle de parité de x, et donc l’inverse de l’intégrale binaire vectorielle, définie plus loin.

Le corollaire 2.1 établit aussi que tout élément donné de Bⁿ forme une base métrique pour Bⁿ. Ceci signifie qu’il n’y a pas de triplets isocèles de vecteurs distincts deux à deux dans Bⁿ , ce qui, à son tour, est important pour le groupe des déplacements dans Bⁿ.  Cela sera considéré dans la section 2.4 sur les déplacements, les produits internes, et le géniton.

2.3  Fondements des Opérateurs XOR (Ou_exclusif) Généralisés

Tournons-nous maintenant vers les opérateurs XOR généralisés, c’est-à-dire l’intégrale binaire scalaire et l’intégrale binaire vectorielle. Ces concepts ont besoin d’une notation mathématique rigoureuse en accord avec ce qui vient d’être développé formellement. Toutefois, nous éprouvons de la difficulté, parce que ni les mathématiques conventionnelles ni la terminologie de l’informatique n’offrent une notation consistante en ce qui concerne les opérateurs monadiques généralisés. C’est pourquoi nous prendrons un compromis en introduisant une notation partiellement nouvelle, mais logiquement saine. La table 3 ci-dessous prévoit ce à quoi le lecteur doit s’attendre en ce qui concerne le XOR généralisé.

La rangée 1 de la table 3 présente le compromis pour une notation standard en informatique et la rangée 2 présente la notation APL standard.

Table 3

Des détails sur la table 3 vont suivre pas à pas. Ce sur quoi les opérateurs agissent est formellement appelé des opérandes. Un opérateur f prend une fonction ƒ et la convertit en quelque chose de différent appelé fonction dérivée z ¬ ƒ/ x  pour un certain argument x. Dans la table 3, l’opération binaire XOR est la fonction logique ¹ , et le fait de la soumettre à l’opérateur de réduction / produit la fonction dérivée z ¬ ¹/ x  c’est-à-dire la réduction généralisée par XOR. De même, si ¹ est soumis à l’opérateur de balayage cumulatif \ , nous obtenons la fonction dérivée z ¬ ¹\ x , c’est-à-dire l’opérateur de balayage par XOR généralisé. Ceci s’applique pour n’importe quelle opération binaire ƒ , et cela explique la notation de la rangée 2 de la table 3 ci-dessus. Remarquer que chaque opérateur a son opérateur dual en vertu des lois de de Morgan^[1]. Les propriétés formelles de ces opérateurs sont décrites dans ce qui suit.

Définition 2.6   L’intégrale binaire scalaire (IBS) est la somme par XOR.

                                 _n

(13)                    z = Å x_i  = (...(x₁ Å x₂) Å x₃) Å ...) Å x_n ) =

                                ⁱ⁼¹

                                         = x₁ Å x₂ Å  ...  Å x_n  .

Théorème 2.4 ^[2]

                                       _n                                       1  ssi || x ||₁  =  pair

                                   Å_i=1 x_i  = z =

                                                               0  ssi || x ||₁  =  impair

Nous avons utilisé un moyen subtil de définir l’IBS pour nous assurer que le lecteur réalise la différence avec l’intégrale binaire vectorielle de la définition 2.7 ci-dessous. A partir de la définition 2.6 et du théorème 2.4, il s’ensuit que l’IBS détermine la parité pour tout x Î Bⁿ , c’est-à-dire qu’un vecteur x a pour parité 1 ssi la norme de x est impaire, sinon x a pour parité 0.  Par exemple, le vecteur  x = 100100 des exemples de la table 1 a pour parité 0, tandis que y = 111101 a pour parité 1. Le corollaire 2.2 ci-dessous montre que l’IBS est équivalente à la somme modulo 2 de x Î Bⁿ .

Corollaire 2.2

                                   Åⁿ_{i =1} x_i = z = 2|₀ Sⁿ_i=1 x_i

Ceci signifie que Å⁶_{i =1} 111101 = (2|₀ 5) = 1 et que Å⁶_{i =1} 100100 = (2|₀ 2) = 0. Remarquer toutefois que l’IBS est un opérateur booléen non-absorbant non- numérique, tandis que la somme modulo 2 est basée sur l’opération numérique d’addition et est donc un opérateur numérique.

Le théorème 2.5 ci-dessous est un compagnon de la loi de de Morgan et montre que  la forme duale  de l’IBS,  la somme par  non-XOR  dans  l’entrée (1,2)  de la

                                                _____

table 3, puisque z ¬ (=/ x ) = ( ¹/ x ) . La somme par non-XOR est ainsi la somme binaire d’équivalence, comme le montre le théorème 2.5 .

Théorème 2.5

                                   [1 Å Åⁿ_{i =1} 1 Å x_i ] = „ⁿ_{i =1} x_i

Le corollaire 2.3 ci-dessous est la version duale du corollaire 2.3 ci-dessus et résulte directement du théorème 2.5 . Il montre aussi comment agit l’opérateur du théorème 2.5 sur ses arguments.

Corollaire 2.3

                                                     ________

                                   „ⁿ_{i =1} x_i = 2|₀ Sⁿ_i=1 x_i

                               ______                                    ____

En particulier, „⁶_{i =1} 111101 = [(1=1=1=1=0=1)=0] = [( 2|₀ 1) = 0],  et de manière

                    ______                                       ____

analogue „⁶_{i =1} 100100 = [(1=0=0=1=0=0)=1] = [( 2|₀ 4) = 1]. D’où le fait que la somme binaire par l’équivalence détermine si x et y sont chacun de parité paire, ou non.

Jusqu’ici nous avons fourni la base formelle des colonnes 1 et 2 de la table 3 pour l’intégrale binaire scalaire, la somme par XOR et son dual, la somme binaire par l’équivalence. Le prochain opérateur est l’intégrale binaire vectorielle, l’intégration par XOR de l’entrée (1,3) de la table 3 ci-dessus. On l’appelle balayage par l’inégalité (« unequal-scan » en anglais) en APL, le balayage par préfixe (« prefix-scan ») en informatique, et intégrale de parité en logique de la parité ([LAN92a], [ZA95b]).

Définition 2.7    L’intégrale binaire vectorielle (IBV) est la somme cumulée par XOR.

                 _n

(14)          � x_i = (x₁, (x₁ Å x₂), ... , (x₁ Å x₂ Å ... Å x_n)) = z₁, z₂, ... , z_n                   ⁱ⁼¹

de sorte que

x_i = z₁

x₁ Å x₂ = z₂

x₁ Å x₂ Å x₃ = z₃

.

.

.

x₁ Å x₂  Å ... Å x_n = z_n

L’IBV de la définition 2.7 est une généralisation directe de XOR, mais elle mérite quelques commentaires, quelques explications ainsi que des illustrations informatiques, avant d’en faire ressortir plusieurs théorèmes et corollaires.

La premier fait important au sujet de l’IBV est qu’elle détermine toutes les sommes par XOR pour un argument vectoriel x. Maintenant, pensez à des statistiques et à une distribution de probabilités telle que 0,02  0,04  0,06  0,11  0,20  0,31  0,16  0,07  0,02  0,01 , et calculez sa fonction de distribution cumulée discrète (f.d.c.) par l’expression (15) :

                 p₁ = 0,02

0,02 + 0,04 = 0,06

(15)   F (x) =  S p_i

 0,02 + 0,04 + 0,06 = 0,13

                          x_i < x

0,02 + 0,04 + 0,06 + 0,11 + ... + 0,01= 1

Dans les deux cas, le résultat n’est pas un nouveau scalaire. C’est un nouveau n-tuple dont les composantes sont les valeurs cumulées réduites, les sommes réduites par XOR concernant l’IBV, et les termes réduits par sommation concernant F(x)  = 0,02  0,06  0,12  0,23  0,43  0,74  0,90  0,97  0,99  1 .

Ensuite, soit x Î Bⁿ . En prenant d’abord la première composante, puis les deux premières composantes, puis les trois premières composantes, et ainsi de suite, nous obtenons les vecteurs 1­x = x₁,  2­x = x₁,x₂,  3­x = x₁,x₂,x₃, etc... On les appelle préfixes de x en informatique. L’IBV de la définition 2.7 produit donc la réduction par XOR de tous les préfixes de l’argument vectoriel x,  et c’est pourquoi l’opérateur est aussi appelé le balayage des préfixes (« prefix-scan »). Il s’agit d’un opérateur spécial dans la « connection machine » de Hillis pour le calcul parallèle ([HIL85]), mais il est beaucoup plus général que cela. Nous allons le démontrer maintenant pour de simples vecteurs binaires et pour des IBV itérées dans le but de faire ressortir le concept d’intégration de parité.

                                              _n

Pour voir comment l’opérateur �     x_i  agit  sur  les  éléments  de  x Î Bⁿ ,  nous

                                              ⁱ⁼¹

choisissons le simple vecteur x = 10000000 Î B⁸ . La table 4a ci-dessous montre comment l’opérateur engendre l’intégrale binaire vectorielle de x, de haut en bas par une série de réductions par XOR. Le résultat est l’intégrale vectorielle z = 11111111. Ce vecteur est l’intégrale de parité de x, puisque chaque étape de calcul détermine la parité par paires entre les termes. Chaque composante de z est une parité et la dernière indique la parité du vecteur x, l’argument original. Ceci vaut pour tout élément x Î Bⁿ.

              Table 4a                                                                        Table 4b

                       _n

Si l’opérateur  �   x_i  est appliqué à des matrices n ´ m au lieu de vecteurs, alors

                      ⁱ⁼¹

on doit spécifier l’axe d’intégration.

                                               _{n                                                                                           m}

(16)          (16.1)          M ^*_ij = � M_ij                  (16.2)          M ^*_ij = � M_ij

                                              ^{i=1                                                                                       j=1}

Dans (16.1) ci-dessus, l’opérateur agit sur les colonnes, tandis que dans (16.2), il agit sur les lignes et détermine leurs intégrales de parité respectives. La table 4b, d’autre part, démontre ce qui arrive quand nous itérons l’opérateur successivement selon :

                                                       _n

(17)                                      x^{(t +1)} = � x_i^(t)  ,

                                                        ⁱ⁼¹

^{où t dénote la variable d’itération. Le résultat est une matrice de parité 8´8 avec une périodicité t = n, puisque le vecteur d’entrée original x(0) réapparaît comme la ne intégrale de parité. La matrice de parité de la table 4b, appelée pariton ([LAN91a,b], [LAN92a], [ZA94b]) sera considérée à nouveau presque dans chacune des sections suivantes à cause de son importance.}

^{Observer que l’opérateur dans l’équation (17) agit comme un générateur d’ondes asymétrique, en ce sens qu’il propage des différences élémentaires de gauche à droite, et de haut en bas par itérations successives. Ainsi, c’est, entre autres choses, le bloc de construction des machines à rétroaction de parité pour modéliser et analyser les milieux excitables ([ZA95b]). D’autres détails relatifs à l’IBV vont suivre dans les sections ultérieures, alors, retournons à ses propriétés formelles concernant les colonnes 3 et 4 de la table 3 .}

^{Théorème 2.6}

Le théorème ci-dessus  est un cousin  du théorème  2.4  et établit  que la parité de

x  Î Bⁿ  est déterminée dans la dernière composante de l’intégrale de parité z. Ainsi, le vecteur x a pour parité 1 ssi z_n vaut 1, sinon x a pour parité 0. Donc l’IBV contient le contrôle de parité de son argument vectoriel dans le dernier item de z. La table 4a ci-dessus le montre explicitement pour chaque intégrale de parité de la matrice 8^´8.

Définition  2.8   La contre-partie cumulative de Sⁿ_i=1 x_i   est la somme de tous les partiels

                           _n

(18)                    †  x_i = (x₁, (x₁ +x₂) ... (x₁ + ... + x_n) ) .

                         ^{i = 1}

Observer que la fonction de distribution cumulative dans l’équation (15) est bien définie pour des variables aléatoires discrètes. Il n’existe, toutefois, aucune notation pour la somme de tous les partiels, c’est pourquoi nous nous sommes décidés pour celle-ci^[3].

Le corollaire 2.4 ci-dessous est le pendant du corollaire 2.2 concernant l’intégrale binaire scalaire. Elle montre l’équivalence entre l’IBV et la somme cumulée modulo 2.

Corollaire 2.4

                                       _{n                                          n}

                                   �_i=1 x_i = z = 2| ₀  †_i=1 x_i

            _n

Ainsi,  �_i=1 111101 =  (2| ₀ 123445) = 101001,  et,  de  manière  correspondante,

    _n

�_i=1 100100 = (2| ₀ 111222) = 111000. L’IBV est, comme l’IBS, un opérateur booléen non numérique et ne nécessite pas de lourd calcul numérique (« bit crunching ») modulo 2.

Le théorème 2.7 ci-dessous est encore un parent de la loi de de Morgan. Il montre que la forme duale de l’IBV,  l’intégration par non-XOR  dans l’entrée (1,4) de la table 3, est l’équivalent de l’opérateur balayage par égal  dans l’entrée (2,4)  de la

                                             _{______}

table 3, puisque z ¬ (=\ x) = (¹\ x) .

Théorème 2.7

                                               _{n                                   n}

                                   [1 Å �_{i =1} 1 Å x_i] = …_{i =1} x_i

L’intégration par non-XOR est donc la somme d’équivalence cumulée binaire.

Nous parvenons finalement au corollaire 2.5, la contre-partie du corollaire 2.3 . Cela peut frapper le lecteur que ce corollaire soit aussi étrangement abstrait, mais nous en avons besoin pour compléter la table 3, à cause de la dualité des opérateurs.

Corollaire  2.5

                          _{______________}

    …ⁿ_{i =1}x_i = 2| ₀  †ⁿ_i=1 x_i

Il montre comment l’opérateur du théorème 2.7 agit sur ses arguments. Il suffit d’un seul exemple :

              ______                                                            _________

   …ⁿ_{i =1} 111101 = [1,(1=1), . . . ,(1=1=1=1=0=1)] =  [2| ₀ 000011] = 111100.

Théorème 2.8

  $x_i  Î x : x_i  ¹ x_ij ® �ⁿ_{i =1} x₁ , x_{2 ,},...,x_n ¹ �ⁿ_{i =1} x_n , x_n-1,...,x₁ ; ij=1,2,...n; (i ¹ j)

Le théorème 2.8 ci-dessus établit que l’IBV est asymétrique pour tout x_i Î Bⁿ excepté l’origine (000...00) et le sommet (111...11). Cela signifie que s’il existe un simple x_i  qui soit différent de tous les autres éléments possiblement équivalents dans x, alors une rotation de x autour de sa première coordonnée produit un résultat différent. Ceci se produit déjà pour le vecteur à 2 composantes x = x₁ , x_{2 ,} = 1 0 et sa rotation 0 1 :

Ceci vaut pour toute dimension n de x. L’importance du théorème 2.8 est que l’opérateur est un propagateur asymétrique de différences symétriques. Le fait que l’opérateur soit également isentropique et réversible résulte de la table 4a et du mécanisme de rétroaction de l’équation (17). A nouveau, le vecteur à deux composantes x = 1 0 et son intégrale de parité intégrée clarifient la situation d’un simple coup d’œil.

Le point important de l’implication contenue dans (20) est que cette itération double engendre la structure la plus importante de la logique de la parité, la matrice de parité :

appelée pariton génétique, ou géniton en abrégé ([LAN92a]). Ses propriétés formelles sont traitées dans la section suivante, une fois introduits les concepts des déplacements et des produits internes binaires. Les deux opérateurs, l’IBS aussi bien que l’IBV, seront exploités de façon plus détaillée dans les sections concernant la logique de parité appliquée.

2.4  Mouvements, Produits Internes et Géniton

Le triangle de Pascal modulo 2 et son remplissage en carré de Pascal d’une part, ainsi que le groupe des déplacements concernant les matrices de parité binaires d’autre part, vont jouer un rôle central dans les sections suivantes. La même chose vaut pour les produits internes mettant en jeu XOR. Le fait que áBⁿ,d ñ soit un espace métrique de diamètre n  a déjà été établi dans la définition 2.1 et le théorème 2.2 de la section 2.2 . Pour établir le concept des déplacements dans Bⁿ  nous avons besoin du concept d’isométrie, de la propriété involutive des déplacements préservant la distance, de l’identité et de la propriété des déplacements préservant les compléments. Les deux plus importantes classes de déplacements seront les rotations de vecteurs et les réflexions de tableaux dans Bⁿ pour des transformations effectives, ainsi que le groupe des opérateurs de transformation.

Définition 2.9   Un déplacement j entre deux espaces métriques est une isométrie s’il préserve la distance, c’est-à-dire " x,y Î X : (j : X ® Y) ® d [j (x), j (y)] = d (x,y).

Noter que la définition 2.9 met en jeu deux espaces métriques. Une isométrie définie sur un seul espace dans ou sur lui-même est une application rigide. Pour Bⁿ nous obtenons :

                                                                                                       _sur

Définition 2.10  Une application préservant la distance                   j : Bⁿ ® Bⁿ est un déplacement.

Le fait qu’un déplacement de Bⁿ soit biunivoque résulte du théorème 2.2.1 de la section 2.2, puisque d (x,y) = 0 ssi x = y .  Beaucoup plus important est le lemme suivant :

                                                                                                      _dans

Lemme 2.1                Une application j préservant la distance        j : Bⁿ ® Bⁿ est involutive.

Puisque les involutions jouent un rôle-clé en logique de la parité et dans les calculs réversibles, nous insérons la démonstration du lemme 2.1 . Si x Î Bⁿ , dénotons j(j(x)) par y. Puisque j préserve la distance, d (x, j (x)) = d (j (x),y). Ainsi, chaque vecteur binaire x,y  a la même distance de j (x). Toutefois, puisque j (x) forme une base métrique pour Bⁿ selon le théorème 2.3 et le corollaire 2.1, il s’ensuit que y = x. D’où pour tout x Î Bⁿ :  j (j (x)) = x.  Bien que ceci ait l’air trivial, le lemme 2.1 a d’importantes implications pour les transformées dans Bⁿ (par exemple les transformées de Shegalkin et les transformées de Langlet ([BOP81], [LAN92a], [ZA94b])).

Corollaire 2.6   áBⁿ,d ñ est un espace métrique monomorphe avec un diamètre n, de là toute application préservant la distance j de Bⁿ dans lui-même est un déplacement.

Corollaire 2.7   Si un déplacement j de Bⁿ laisse un élément fixe, c’est une identité.

Lemme 2.2                 Si j est un déplacement quelconque de Bⁿ et que x Î Bⁿ , alors j (x) = ‡ (x), c’est-à-dire que tout déplacement j de x Î Bⁿ préserve son complément.

Pour nous, les déplacements les plus importants sont les rotations et les réflexions. Une distinction significative entre une rotation autour d’un point dans le plan et une réflexion sur une droite dans le plan est qu’une rotation n’a qu’un seul point invariant, le centre de rotation, tandis qu’une réflexion a une droite de points invariants, l’axe de réflexion. Un autre type de déplacement, la translation, n’a aucun point invariant. La seule exception pour laquelle tous les points sont invariants est la transformation identité. Maintenant, l’ensemble de toutes les rotations autour d’un point ou d’une coordonnée p forme un groupe. La même chose vaut pour les réflexions. La réflexion sur une droite donnée l forme un groupe avec la transformation identité, puisque la réflexion sur l , suivie par une autre réflexion sur l , nous ramène au point de départ. Ces concepts couvrent l’algèbre binaire et l’espace Bⁿ. Nous allons le démontrer pour le géniton et pour le groupe des réflexions, et ensuite pour des matrices de parité n ´ n, c’est-à-dire les paritons.

Théorème 2.9   Le géniton et ses rotations de 90° dans le sens des aiguilles d’une montre ou en sens inverse forment un groupe d’opérateurs matriciels c’est-à-dire de transformations.

Théorème 2.10 Le géniton et ses réflexions horizontale h, diagonale d et verticale v forment un groupe d’opérateurs matriciels c’est-à-dire de transformations  G, Gh, Gd, Gv, GU et GU ^NdT .

Pour pouvoir donner des détails sur le théorème 2.10, nous avons besoin du produit matriciel binaire et de la puissance d’une matrice^[4].

Définition 2.12  Le produit matriciel binaire (PMB ^NdT) est le produit interne Ou_exclusif-ET (« XOR-AND ») :

                                                                              ______

(22)                               Z = (X ˆ Y) = (X  ^Å Y) = (X  ⁼ Y)

                                                                 ^{Ù               Ú}

Le PMB est défini en termes des lois de de Morgan ([IVE62]), et la notation signifie que ce produit met en jeu les opérations Å et Ù de sorte que les termes de X et de Y sont d’abord liés par conjonction, puis par XOR. Le produit dans (22) est la contre-partie modulo 2 du produit interne de matrices habituel en algèbre. Les deux se distinguent très bien l’un de l’autre en APL par les notations (X¹.ÙY) et (X+.´Y). La nomenclature standard concernant le produit interne XOR-ET d’une matrice binaire X mn et d’une matrice binaire Y np est donnée par :

                                                                                                 i = 1, 2, ..., m

  z_ik = (x_{i 1} Ù y_1k) Å (x_{i 2} Ù y_2k) Å ^{. . .} Å (x_in Ù y_nk) = Åⁿ_r=1 x_ir  Ù y_rk :

                                                                                                 k = 1,2, ..., p,

dont le résultat est une matrice binaire Z mp. La notation se simplifie quelque peu pour des matrices binaires carrées, mais la logique de la définition 2.12 devrait être transparente maintenant. Le produit binaire en puissance PBP est simplement un produit matriciel binaire n-uple.

La table 5a résume les propriétés essentielles du géniton et du groupe de réflexion (théorème 2.10), tandis que la table 5b présente quelques détails sur les PMB et sur les PBP.

Table 5a

La table 5b ci-dessous est surtout centrée sur G et sur sa réflexion verticale Gv. Les détails concernant G sont valables pour Gd, et ceux concernant Gv sont valables pour Gh. Chaque rangée de la table 5b est une instance du théorème 2.10 sans que l’on montre la totalité de ces instances. Nous utilisons la notation simplifiée de la définition 2.12.

Table 5b

Les deux tables sont des objets d’étude pour les matrices de parité en général. Il vaut mieux s’intéresser en détail aux propriétés du géniton, car ces propriétés valent pour des matrices de plus grande dimension n ´ n, comme nous le montrerons dans les sections suivantes. Nous refermons maintenant ce survol, plutôt condensé, des fondements mathématiques et nous allons aborder un autre domaine des fondements de la logique de parité, l’analyse binaire du signal.

Bibliographie

AIG93 : Aigner, M. 1993 Diskrete Mathematik, Vieweg, Braunschweig.

BAS83 : Basilevsky, A. 1983 Applied Matrix Algebra in the Statistical Sciences, North-Holland, Amsterdam.

BOP81 : Bochmann, D. & Posthoff, Ch. 1981 Binäre dynamische Systeme, Oldenbourg, München.

HIL85 : Hillis D. The Connection Machine, MIT Press, Cambridge, USA.

IVE62 : Iverson, K.E. 1962. A Programming Language, John Wiley & Sons, New York.

IVE78 : Iverson, K.E. 1978-9 Notation as a Tool of Thought. Turing Award Lecture of the ACM. Reprinted in McDonnel,E., 1981. A Source Book in APL, Palo Alto Press, Palo Alto.

LAN91a : Langlet G.A. 1991  Les Génitons : Variations sur Pascal, Sierpinski et Fibonacci, APL-CAM Journal (Belgique), Vol. 13, N° 2, 399-421.

LAN91b : Langlet G.A. 1991  Paritons and Cognitons : Towards a new theory of information. APL-CAM Journal, Vol 13, N° 3, 709-743.

LAN92a : Langlet G.A. 1992 Towards the Ultimate APL-T.O.E.  APL Quote-Quad, ACM Press, USA, 23, 1, July 1992, 118-132.

LAN93 : Langlet G.A. 1993  Symétrie, Forces et Phénomènes. APL-CAM Journal, Vol. 15, N° 1, 57-80.

LOC89 : Lochner, H. 1989, APL2 Handbuch, Springer, Heidelberg.

WAT92 : Watenabe, H., Symon, J.R., Detloff, W.D. & Yount, K.E. 1992  VLSI fuzzy chip and inference accelerator board. in Zadeh, L. & Kacprzyk, K. (Eds.) 1992 Fuzzy Logic for the Management of Uncertainty. Wiley & Sons, Chichester, G.B.

ZA94b : Zaus M., 1994 Theoretische und Andgewandte Paritätslogik. APL-CAM Journal, Vol. 16, N° 3, 447-469. Disponible en français : La Logique de la Parité, Théorique et Appliquée, Les Nouvelles d’APL, N° 12-13, 42-66 1994, Paris.

ZA95 : Zaus, M. 1995  Artificial Evolution in Cognitive Science and Technology, Interim-Report, 160 p. Chapman & Hall, London.

ZA95b : Zaus, M., Parity Integration, Excitable Media and Neural Computing, APL-CAM Journal, Vol. 17, N° 3, 409-432. Disponible en français : Intégration de Parité, Milieux Excitables et Neuro-Calcul, Les Nouvelles d’APL, N° 15, 46-74, 1994, Paris (disponible sur Internet : http://www.ensmp.fr/~scherer/langlet).

ZA95c : Zaus, M., Artificial Evolution in Cognitive Science and Technology, en préparation pour : Chapman & Hall, London, ISBN 0-412486601.

Note : Le rapport original (77p). de M. Zaus « Studies in the Foundations of Parity Logic » est disponible, soit à l’adresse suivante :

 Institut für Kognitionsforschung, FB 5 - A6, Universität Oldenburg, P.O. Box 2503, Allemagne (Fax : {49} 441-7985170),

soit, en France, auprès de : Mme Derost, Bibliothèque SCM, CEA-Saclay, 91191-Gif sur Yvette Cedex.

Ce travail a été financièrement soutenu par la Fondation Scientifique Allemande (DFG), Bourse : Sche 298/5-2. Il a été effectué au sein du Groupe de Recherche Interdisciplinaire sur les Sciences Cognitives, Université de Brême & Université d’Oldenburg.

La seconde partie du rapport paraîtra en français sous forme d’article dans le numéro suivant des Nouvelles d’APL sous le titre « Représentations Analytiques des Signaux Binaires ».

                Pensée à méditer :

« L’aventure, c’est la recherche de la différence »

Paul-Emile Victor