Fonction booléenne

Arbre de décision binaire

Une fonction booléenne est une fonction prenant en entrée une liste de bits et donnant en sortie un unique bit.

Les fonctions booléennes sont très utilisées en informatique théorique, notamment en théorie de la complexité et en cryptologie (par exemple dans les boîtes-S et les chiffrements par flot -- fonction de filtrage ou de combinaison de registres à décalage à rétroaction linéaire).

Définition, exemple et circuits

Une fonction booléenne est une fonction de dans désigne le corps fini à 2 éléments. Un exemple de fonction booléenne est la fonction parité, dont la sortie dépend de la parité du nombre de 1 dans l'entrée. Une fonction booléenne peut être représentée par un circuit booléen.

Propriétés

Forme algébrique normale

Les corps finis et les polynômes interpolateurs de Lagrange conduisent rapidement à une propriété fondamentale des fonctions booléennes : la représentation dite « forme algébrique normale » (algebraic normal form ou ANF). Toute fonction booléenne peut s'écrire comme un polynôme en variables à coefficients dans . Cependant, différents polynômes de donnent la même fonction. Par exemple, et donnent bien la même valeur lorsqu'ils sont évalués sur un élément de . Pour obtenir une représentation unique, il faut considérer les éléments de l'anneau quotient, soit :

Autrement dit, une fonction booléenne peut être représentée de manière unique par un polynôme de la forme :

( est une suite d'éléments de et ).

On pose fréquemment , et , permettant l'écriture compacte :

.

La notion de degré d'une fonction booléenne est alors évidente, il s'agit du degré maximal des monômes de son ANF.

Exemple de forme algébrique normale sur  :

Linéarité et non-linéarité

Les fonctions de degré 1 sont appelées les fonctions affines. En fait, ce sont des formes affines de l'espace vectoriel — vu comme espace sur le corps . Ce sont les fonctions les plus simples, hormis les constantes. Il a fini par apparaître que « ressembler » à une fonction linéaire était une propriété pouvant être exploitée en cryptanalyse. La ressemblance en question se base sur le nombre de fois où deux fonctions prennent la même valeur, il s'agit de la distance de Hamming :

Les cryptographes utilisent le terme de non-linéarité pour parler de la distance d'une fonction booléenne à l'ensemble des fonctions affines :

L'intérêt de cette notion est de quantifier l'erreur commise si on remplace la fonction par une fonction affine : dans le meilleur des cas, on se « trompe » fois sur si est le nombre de variables.

On montre, en utilisant la transformée de Fourier, que la non-linéarité d'une fonction booléenne est au plus de

Lorsque est pair, cette borne supérieure est atteinte, on parle alors de fonction courbe.

Précisons que l'ensemble des fonctions affines a une importance particulière en théorie des codes correcteurs, au point qu'il possède un nom, le code de Reed-Muller d'ordre 1 (en variables). L'ordre est le degré maximal des fonctions. Ainsi, le code de Reed-Muller d'ordre en , usuellement noté est l'ensemble des fonctions en variables de degré au plus . Dans le contexte de la théorie des codes, la non-linéarité maximale se trouve correspondre au « rayon de recouvrement » du code , c'est-à-dire la distance maximale entre un mot binaire de longueur et un mot du code.

Outil d'étude : la transformée de Fourier

La transformation de Fourier, appliquée aux fonctions booléennes, se révèle être un moyen très puissant pour explorer les différentes propriétés de ces objets. Elle est, par exemple, fréquemment utilisée pour étudier des propriétés cryptographiques comme la non-linéarité maximale. On la retrouve également dans des aspects plus appliquées : l'existence d'algorithmes de calcul de la transformée de Fourier de type FFT sert à décoder efficacement les codes de Reed et Muller. On trouvera dans la suite une présentation générale de la transformation de Fourier dans le cas des groupes abéliens finis qui est ensuite particularisée pour le cas des fonctions booléennes.

Cas d'un groupe abélien fini

Dans le cas d'un groupe abélien fini, le théorème de Kronecker assure que le groupe est isomorphe à un produit direct de groupes cycliques. Ce théorème est à la base de nombreuses propriétés des fonctions booléennes.

Caractère et groupe dual

De manière générale, on peut définir une transformation de Fourier sur un groupe en utilisant la notion de caractère. Un caractère est un morphisme de dans , le groupe des racines de l'unité du corps des nombres complexes .

L'ensemble des caractères opèrent sur l'ensemble des applications de dans , cet ensemble est appelé algèbre du groupe et est généralement noté . Il est muni du produit hermitien suivant :

Ici si z est un complexe, z* désigne son conjugué.

Les caractères forment une base orthonormale de l'algèbre du groupe.

L'ensemble des caractères de peut être muni d'une structure de groupe en utilisant la multiplication entre applications, ce groupe est appelé le groupe dual. Le groupe et son dual sont isomorphes si est abélien.

Les démonstrations sont données dans l'article détaillé.

Définition de la transformée de Fourier

Lorsque est abélien et fini, il est possible de définir simplement la transformée de Fourier. On appelle transformée de Fourier d'un élément de l'algèbre du groupe de une application du groupe dual dans notée ici et définie par :

Cette application dispose de toutes les propriétés usuelles d'une transformée de Fourier, elle est linéaire, l'égalité de Parseval le théorème de Plancherel, la formule sommatoire de Poisson et la dualité de Pontryagin sont par exemple vérifiées. Il est aussi possible de définir un produit de convolution.

Les démonstrations sont données dans l'article détaillé.

Espace vectoriel fini

Il existe un cas important, celui où le groupe est un espace vectoriel fini V, donc de dimension fini sur un corps fini . Dans ce cas, il existe un isomorphisme entre V et son groupe dual, appelé dualité de Pontryagin. Soit . une forme bilinéaire non dégénérée de V et μ un caractère non trivial de , l'application χ de V dans son dual, qui à y associe le caractère χy définie par l'égalité suivante est cet isomorphisme :

Cet isomorphisme permet d'exprimer la transformation de Fourier d'un élément f de l'algèbre du groupe de V de la manière suivante :

Espace vectoriel sur le corps F2

Formes des caractères et isomorphisme avec le dual

On considère maintenant le cas où le corps est celui à deux éléments noté et l'espace vectoriel est n est un entier strictement positif. Soit x = (xi) et y = (yi) deux éléments de l'espace vectoriel, la forme bilinéaire . est définie par :

Il n'existe que deux caractères dans , le caractère trivial et celui qui à s associe (-1)s. Comme il n'existe qu'un caractère non trivial, l'isomorphisme χ du paragraphe précédent prend la forme suivante :

Transformation de Walsh

Dans le cas d'un espace vectoriel binaire (ie. sur le corps fini à deux éléments) la transformée de Fourier prend le nom de transformée de Walsh. Elle prend la forme suivante :

On remarque que le signe moins utilisé dans la définition disparait car dans la multiplication par -1 est égale à l'identité. On remarque que la transformée de Walsh est idempotente, c'est-à-dire qu'elle est égale à son inverse.

On voit donc que l'un des intérêts de cette identification est d'avoir la transformation de Walsh et son inverse qui agissent sur les mêmes objets : des fonctions de dans .

Formule de Poisson

Un autre intérêt de l'identification de et de son dual, et non moins agréable que celui évoqué précédemment, est de simplifier considérablement la formule de Poisson. En effet, on obtient alors

On remarque que s'identifie naturellement à . C'est ce qui est fait dans la formule ci-dessus, passant ainsi d'une notation multiplicative pour à une notation additive (on a également utilisé dans le cas de ). On vérifie également que et sont des espaces vectoriels sur .

Voir aussi

Liens externes

Bibliographie

Read other articles:

AmbarketawangKalurahanNegara IndonesiaProvinsiDaerah Istimewa YogyakartaKabupatenSlemanKecamatanGampingKode pos55599Kode Kemendagri34.04.01.2002 Luas635,89 haJumlah penduduk19.237 jiwaKepadatan31 jiwa/km² Ambarketawang (Jawa: ꦲꦩ꧀ꦧꦂꦏꦼꦠꦮꦁ) adalah sebuah desa atau kelurahan yang terletak di Kapanewon Gamping, Kabupaten Sleman, Daerah Istimewa Yogyakarta, Indonesia. Terbentuknya Desa Ambarketawang berdasarkan Maklumat Pemerintah Provinsi Yogyakarta pada tahun 1946 ya...

 

New Zealand field hockey player Ella Gunson Personal informationBorn (1989-07-09) 9 July 1989 (age 34)Whangārei, New ZealandHeight 1.62 m (5 ft 4 in)[1]Weight 62 kg (137 lb)Playing position MidfielderClub informationCurrent club NorthlandSenior careerYears Team NorthlandNational teamYears Team Apps (Gls)2009– New Zealand 191 Medal record Representing  New Zealand Women's field hockey Commonwealth Games 2018 Gold Coast Team 2010 Delhi Team Oceania ...

 

عبد الحميد كرامي   رئيس الحكومة اللبنانية الثاني في المنصب9 كانون الثاني 1945 – 22 آب 1945 رياض الصلح سامي الصلح وزير الدفاع الوطني و وزير المالية في المنصب9 كانون الثاني 1945 – 22 آب 1945 مجيد أرسلان حميد فرنجية أحمد الأسعد إميل جرجس لحود نائب طرابلس في البرلمان اللبناني ...

Artikel ini bukan mengenai Dave Harbour atau Dave Barbour. David HarbourHarbour di San Diego Comic-Con 2019LahirDavid Kenneth Harbour[1]10 April 1975 (umur 49)White Plains, New York, USATempat tinggalNew York, USAAlmamaterDartmouth CollegePekerjaanPemeranTahun aktif1999–sekarangTinggi190 cm (6 ft 3 in) David Kenneth Harbour (lahir 10 April 1975) adalah seorang pemeran Amerika Serikat. Ia memulai karier filmnya pada 2004, dan memainkan peran-peran pendukung d...

 

←→Январь Пн Вт Ср Чт Пт Сб Вс 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31         2024 год Содержание 1 Праздники и памятные дни 1.1 Религиозные 1.2 Именины 2 События 2.1 До XIX века 2.2 XIX век 2.3 XX век 2.4 XXI век 3 Родились 3.1 До XIX века 3.2 XIX век 3.3 XX век 4 Скончались 4.1 До XIX века 4.2 XI...

 

Voce principale: Associazione Calcio Pavia. Associazione Calcio PaviaStagione 1950-1951Sport calcio Squadra Pavia Allenatore Alfredo Foni, poi Oreste Barale Presidente Gino Gruppi Serie C3º nel girone A Maggiori presenzeCampionato: Ezio Lombardi (38) Miglior marcatoreCampionato: Roberto Serone (14) StadioStadio Comunale 1949-1950 1951-1952 Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti l'Associazione Calcio Pavia nelle competizioni ufficiali de...

United States historic placeEzekiel Emerson FarmU.S. National Register of Historic Places Show map of VermontShow map of the United StatesLocationVT 73, Rochester, VermontCoordinates43°51′23″N 72°49′21″W / 43.85639°N 72.82250°W / 43.85639; -72.82250Area38 acres (15 ha)Built1840 (1840)Architectural styleQueen AnneMPSAgricultural Resources of Vermont MPSNRHP reference No.01001284[1]Added to NRHPNovember 29, 2001 The Ezekiel Em...

 

Genus of palms For other uses, see Areca (disambiguation). Areca Areca catechu – 1897 illustration[2] Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Monocots Clade: Commelinids Order: Arecales Family: Arecaceae Subfamily: Arecoideae Tribe: Areceae Subtribe: Arecinae Genus: ArecaL. Type species Areca catechu [1]L. Synonyms[3] Mischophloeus Scheff. Gigliolia Becc. Pichisermollia H.C.Monteiro Arecus Areca is a genus of 51 ...

 

1962 film Bill of HareDirected byRobert McKimsonStory byJohn DunnProduced byDavid H. DePatie(uncredited)StarringMel BlancMusic byMilt FranklynAnimation byTed BonnicksenWarren BatchelderGeorge GrandpréLayouts byRobert GribbroekBackgrounds byRobert GribbroekColor processTechnicolorProductioncompanyWarner Bros. CartoonsDistributed byWarner Bros. PicturesRelease dateJune 9, 1962[1]Running time6:25[1]LanguageEnglish Bill of Hare is a 1962 Warner Bros. Merrie Melodies cartoon direc...

Protein-coding gene in the species Homo sapiens GALR2IdentifiersAliasesGALR2, GAL2-R, GALNR2, GALR-2, Galanin receptor 2External IDsOMIM: 603691 MGI: 1337018 HomoloGene: 2863 GeneCards: GALR2 Gene location (Human)Chr.Chromosome 17 (human)[1]Band17q25.1Start76,074,781 bp[1]End76,077,537 bp[1]Gene location (Mouse)Chr.Chromosome 11 (mouse)[2]Band11 E2|11 81.1 cMStart116,171,765 bp[2]End116,174,764 bp[2]RNA expression patternBgeeHumanMouse (ort...

 

NaCp redirects here. For other uses, see NACP (disambiguation). Sodium cyclopentadienide The cyclopentadienide anion Names Preferred IUPAC name Sodium cyclopentadienide Other names Sodium cyclopentadienylide, Cyclopentadienylsodium Identifiers CAS Number 4984-82-1 Y 3D model (JSmol) Interactive image ChemSpider 71032 Y ECHA InfoCard 100.023.306 EC Number 225-636-8 PubChem CID 78681 CompTox Dashboard (EPA) DTXSID9063665 InChI InChI=1S/C5H5.Na/c1-2-4-5-3-1;/h1-5H;/q-1;+1 YKey:...

 

Canadian actor (1928–2000) John ColicosBorn(1928-12-10)December 10, 1928Toronto, Ontario, CanadaDiedMarch 6, 2000(2000-03-06) (aged 71)Toronto, Ontario, CanadaOccupationActorYears active1950–1999Spouse Mona McHenry ​ ​(m. 1956; div. 1981)​Children2 John Colicos (December 10, 1928 – March 6, 2000) was a Canadian actor.[1] He performed on stage and television in the United States and Canada. Early life Colicos was born in T...

William GordonFonctionsCommander-in-Chief, The Nore1854-1857Membre du 16e Parlement du Royaume-Uni16e Parlement du Royaume-Uni (d)Aberdeenshire (en)7 juillet 1852 - août 1854Membre du 15e Parlement du Royaume-Uni15e Parlement du Royaume-Uni (d)Aberdeenshire (en)29 juillet 1847 - 1er juillet 1852Membre du 14e Parlement du Royaume-Uni14e Parlement du Royaume-Uni (d)Aberdeenshire (en)29 juin 1841 - 23 juillet 1847Fourth Sea Lord (en)1841-1846Membre du 13e Parlement du Royaume-Uni13e Parlement d...

 

  提示:此条目页的主题不是中國—瑞士關係。   關於中華民國與「瑞」字國家的外交關係,詳見中瑞關係 (消歧義)。 中華民國—瑞士關係 中華民國 瑞士 代表機構駐瑞士台北文化經濟代表團瑞士商務辦事處代表代表 黃偉峰 大使[註 1][4]處長 陶方婭[5]Mrs. Claudia Fontana Tobiassen 中華民國—瑞士關係(德語:Schweizerische–republik china Beziehungen、法�...

 

Кооперативная паевая марка Центросоюза СССР и РСФСР (1950-е, 1 рубль) Кооперати́вные ма́рки — вид кредитных марок, выпускаемых массовыми коллективными объединениями, функционирующими в области производства и обмена, — потребительскими, снабженческо-бытовыми, креди�...

Mother of Stanislaw Leszczynski, king of Poland See also: Anna Jabłonowska and Anna Leszczyńska (1699–1717) Anna Leszczyńska née JabłonowskaCoat of armsPrus IIIBorn1660Kraków, PolandDied29 August 1727 (aged 66–67)Chambord, Loir-et-Cher, FranceNoble familyJabłonowskiSpouse(s)Rafał LeszczyńskiIssueStanisław LeszczyńskiFatherStanisław Jan JabłonowskiMotherMarianna Kazanowska Anna Leszczyńska née Jabłonowska (1660–1727) was a Polish noblewoman, born into the Hou...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أبريل 2021) غرّيبة قنبلة إزميرمعلومات عامةالمنشأ تركياالمنطقة إزميرالنوع غرِّيبةالمكونات الرئيسية نوتيلا, طحين, صودا الخبز, ملح, زبدة, سكر خشن, سكر ناعم, بيض, خلاصة الفا...

 

For the Christian image in the Philippines, see Our Lady of Guidance. Municipality in Canary Islands, SpainSanta María de Guía de Gran CanariaMunicipalityView of La Atalaya FlagCoat of armsMunicipal location in Gran CanariaSanta María de Guía de Gran CanariaLocation in the province of Las PalmasShow map of Province of Las PalmasSanta María de Guía de Gran CanariaSanta María de Guía de Gran Canaria (Canary Islands)Show map of Canary IslandsSanta María de Guía de Gran CanariaSanta Mar...

British electric railway freight locomotive British Rail Class 92A GBRF Class 92 in Caledonian Sleeper livery at London EustonType and originBuilderABB Transportation and Brush TractionBuild date1993–1996[1]Total produced46SpecificationsConfiguration:​ • AARC-C • UICCo′Co′ • CommonwealthCo-CoGauge1,435 mm (4 ft 8+1⁄2 in) standard gaugeWheel diameter1.14 m (3 ft 9 in)[2]Minimum curve120...

 

صخور القمر هو مصطلح يشير إلى الصخور التي تكونت على سطح القمر (التابع لكوكب الأرض).[1][2][3] مصادر الصخور هناك حالياً ثلاثة مصادر لصخور القمر على الأرض: الصخور التي جمعتها بعثات أبولو إلى القمر الأمريكية. العينات المعادة من قبل مهمات الاتحاد السوفيتي القمرية. الصخو�...