Reed–Muller expansion

In Boolean logic, a Reed–Muller expansion (or Davio expansion) is a decomposition of a Boolean function.

For a Boolean function we call

the positive and negative cofactors of with respect to , and

the boolean derivation of with respect to , where denotes the XOR operator.

Then we have for the Reed–Muller or positive Davio expansion:

Description

This equation is written in a way that it resembles a Taylor expansion of about . There is a similar decomposition corresponding to an expansion about (negative Davio expansion):

Repeated application of the Reed–Muller expansion results in an XOR polynomial in :

This representation is unique and sometimes also called Reed–Muller expansion.[1]

E.g. for the result would be

where

.

For the result would be

where

.

Geometric interpretation

This case can be given a cubical geometric interpretation (or a graph-theoretic interpretation) as follows: when moving along the edge from to , XOR up the functions of the two end-vertices of the edge in order to obtain the coefficient of . To move from to there are two shortest paths: one is a two-edge path passing through and the other one a two-edge path passing through . These two paths encompass four vertices of a square, and XORing up the functions of these four vertices yields the coefficient of . Finally, to move from to there are six shortest paths which are three-edge paths, and these six paths encompass all the vertices of the cube, therefore the coefficient of can be obtained by XORing up the functions of all eight of the vertices. (The other, unmentioned coefficients can be obtained by symmetry.)

Paths

The shortest paths all involve monotonic changes to the values of the variables, whereas non-shortest paths all involve non-monotonic changes of such variables; or, to put it another way, the shortest paths all have lengths equal to the Hamming distance between the starting and destination vertices. This means that it should be easy to generalize an algorithm for obtaining coefficients from a truth table by XORing up values of the function from appropriate rows of a truth table, even for hyperdimensional cases ( and above). Between the starting and destination rows of a truth table, some variables have their values remaining fixed: find all the rows of the truth table such that those variables likewise remain fixed at those given values, then XOR up their functions and the result should be the coefficient for the monomial corresponding to the destination row. (In such monomial, include any variable whose value is 1 (at that row) and exclude any variable whose value is 0 (at that row), instead of including the negation of the variable whose value is 0, as in the minterm style.)

Similar to binary decision diagrams (BDDs), where nodes represent Shannon expansion with respect to the according variable, we can define a decision diagram based on the Reed–Muller expansion. These decision diagrams are called functional BDDs (FBDDs).

Derivations

The Reed–Muller expansion can be derived from the XOR-form of the Shannon decomposition, using the identity :

Derivation of the expansion for :

Derivation of the second-order boolean derivative:

See also

References

  1. ^ Kebschull, Udo; Schubert, Endric; Rosenstiel, Wolfgang (1992). "Multilevel logic synthesis based on functional decision diagrams". Proceedings of the 3rd European Conference on Design Automation.

Further reading

Read other articles:

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Typographic approximation – news · newspapers · books · scholar · JSTOR (February 2012) (Learn how and when to remove this template message) A typographic approximation is a replacement of an element of the writing system (usually a glyph) with another glyph or...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (مارس 2019) بيير دريفوس (بالفرنسية: Pierre Dreyfus)‏    معلومات شخصية الميلاد 18 نوفمبر 1907  باريس  الوفاة 25 ديسمبر 1994 (87 سنة)   باريس  مواطنة فرنسا  مناصب رئيس-مدير...

 

Heidi Hammel Información personalNacimiento 14 de marzo de 1960 (63 años)California (Estados Unidos) Nacionalidad EstadounidenseEducaciónEducada en Instituto Tecnológico de MassachusettsUniversidad de Hawái Información profesionalOcupación Astrónoma Empleador Instituto Tecnológico de MassachusettsSpace Science Institute Miembro de Sociedad PlanetariaUnión Astronómica Internacional Distinciones Premio Klumpke-Roberts (1995)Harold C. Urey Prize (1996)Medalla Carl Sagan ...

Der Titel dieses Artikels ist mehrdeutig. Weitere Bedeutungen sind unter Augsburg (Begriffsklärung) aufgeführt. Wappen Deutschlandkarte 48.37166666666710.898333333333494Koordinaten: 48° 22′ N, 10° 54′ O Basisdaten Bundesland: Bayern Regierungsbezirk: Schwaben Höhe: 494 m ü. NHN Fläche: 146,85 km2 Einwohner: 301.033 (31. Dez. 2022)[1] Bevölkerungsdichte: 2050 Einwohner je km2 Postleitzahlen: 86150–86199 Vorwahl: 0821 K...

 

Regional county municipality in Quebec, CanadaLes BasquesRegional county municipalityCoordinates: 48°06′N 69°04′W / 48.100°N 69.067°W / 48.100; -69.067[1]CountryCanadaProvinceQuebecRegionBas-Saint-LaurentEffectiveApril 1, 1981County seatTrois-PistolesGovernment[2] • TypePrefecture • PrefectBertin DenisArea[2][3] • Total1,130.70 km2 (436.57 sq mi) • Land1,121.82 k...

 

Welcome Welcome! Hello, Timgrable, and welcome to Wikipedia! Thank you for your contributions. I hope you like the place and decide to stay. Here are some pages that you might find helpful: The five pillars of Wikipedia Tutorial How to edit a page How to write a great article Manual of Style I hope you enjoy editing here and being a Wikipedian! Please sign your messages on discussion pages using four tildes (~~~~); this will automatically insert your username and the date. If you need help, c...

Renault Renault Type O (1903)Renault Type O (1903) Type O Produktionszeitraum: 1903 Klasse: Rennwagen Karosserieversionen: Phaeton Motoren: Ottomotor:6,3 Liter (29,4 kW) Länge: Breite: Höhe: Radstand: Leergewicht: Fahrgestell: 600 kg Vorgängermodell Renault Type K Nachfolgemodell Renault Type O (b) Der Renault Type O war ein frühes Rennwagenmodell von Renault. Er war nur mit einem leichten, zweisitzigen Aufbau erhältlich. Inhaltsverzeichnis 1 Beschreibung 2 Autorennen 3 Literatur 4 ...

 

2008 EP by LoadedWasted HeartEP by LoadedReleasedSeptember 22, 2008RecordedJune 4–18, 2008, at Jupiter Studios, Seattle, WashingtonGenreHard rock, alternative rock, punk rockLength20:12LabelCentury MediaProducerMartin FeveyearLoaded chronology Dark Days(2001) Wasted Heart(2008) Sick(2009) Wasted Heart is the first EP, and third release overall, by American rock band Loaded. Background Following Scott Weiland's departure from Velvet Revolver on April 21, 2008[1] Loaded de...

 

Official script of the Serbian language Serbian alphabet redirects here. For the Serbian Latin alphabet, see Gaj's Latin alphabet. Serbian Cyrillic alphabetСрпска ћирилицаScript type Alphabet Time period9th century – presentLanguagesSerbianRelated scriptsParent systemsEgyptian hieroglyphs[1]Phoenician alphabetGreek alphabet (partly Glagolitic alphabet)Early Cyrillic alphabetSerbian Cyrillic alphabetChild systemsMontenegrin CyrillicISO 15924ISO 15924Cyrl (220), &#x...

Comics character Mother PanicTextless variant cover of Mother Panic #8, art by Emanuela Lupacchino.Publication informationPublisherDC Comics (Young Animal)First appearanceDC's Young Animal Ashcan Edition (2016)Created by Jody Houser Tommy Lee Edwards Gerard Way In-story informationAlter egoViolet PaigeSpeciesHuman CyborgPlace of originGotham CityPartnershipsBatmanAbilities Cybernetic enhancement Superhuman strength Mother Panic, also known as Violet Paige, is a fictional vigilante appearing i...

 

American professional wrestler Christie RicciRicci as Glory for Wrestlicious in May 2010Born (1982-11-11) November 11, 1982 (age 41)[1]Jackson, Mississippi, United States[2]Professional wrestling careerRing name(s)Christie RicciGloryGloria[3]Billed height5 ft 10 in (1.78 m)[2]Billed weight160 lb (73 kg)[2]Trained byLeilani KaiDebut2000[2] Christie Ricci (born November 11, 1982) is the ring name of an American profes...

 

Supermarket chain in the northeastern United States Wegmans Food Markets, Inc.The exterior of a typical Wegmans, pictured in 2018 in Lancaster, Pennsylvania (Store #135).FormerlyRochester Fruit and Vegetable Company (1916–1930)Type Private family business IndustryRetail (Grocery)Founded1916; 107 years ago (1916) in Rochester, New York, U.S.Founder John Wegman Walter Wegman HeadquartersGates, New York, U.S.Number of locations109[1] (2022)Area served Delaware Ma...

American rock and roll band The Royal TeensBackground informationOriginFort Lee, New Jersey, United StatesGenresRockpoprock and rollYears active1956–1965LabelsRCA, Epic/CBS, Capitol/EMI, Musicor, JubileeMembersTom Austin - drums Bob Azzara - piano Flip Cesario - guitar Bill Crandall - saxophone Bill Dalton - bass Bob Gaudio - piano Al Kooper - guitar Larry Qualiano - saxophone Dan Sabatino - vocals Joe Villa (Joe Francavilla) - vocals Raymond Mariani - vocals & composer Vince Cautero - ...

 

Chain of movie theaters in the United States For other uses, see Fox Theatre (disambiguation). Moorish architectural details of the Fox Theatre in Atlanta Fox Theatre in Visalia, California, currently a performing arts hall.[1] Winged lions atop the marquee in Detroit. Fox Theatre in Oakland Fox Theatre in Redwood City, California Fox Theatres was a large chain of movie theaters in the United States dating from the 1920s either built by Fox Film studio owner William Fox, or subsequent...

 

Family amusement and nature park Gilroy Gardens Family Theme ParkPreviously known as Bonfante Gardens (2001–2006)Location3050 Hecker Pass Hwy. Gilroy, California, United StatesCoordinates37°0′19″N 121°37′41″W / 37.00528°N 121.62806°W / 37.00528; -121.62806StatusOperatingOpenedJune 15, 2001OwnerCity of Gilroy, CaliforniaOperated byGilroy Gardens, Inc. a 501(c)(3) organizationOperating seasonLate March–Early JanuaryArea536 acres (35 acres used for theme p...

Soviet footballer In this name that follows Eastern Slavic naming conventions, the patronymic is Ivanovich and the family name is Voronin. Valery Voronin Voronin in 1966Personal informationFull name Valery Ivanovich VoroninDate of birth (1939-07-17)17 July 1939[1][2]Place of birth Moscow, Russian SFSR, Soviet UnionDate of death 19 May 1984(1984-05-19) (aged 44)[1][2]Place of death Moscow, Russian SFSR, Soviet UnionHeight 1.81 m (5 ft 11 ...

 

Canadian ice hockey goaltender (born 1962) Ice hockey player Grant Fuhr Hockey Hall of Fame, 2003 Fuhr in 2016Born (1962-09-28) September 28, 1962 (age 61)Spruce Grove, Alberta, CanadaHeight 5 ft 10 in (178 cm)Weight 184 lb (83 kg; 13 st 2 lb)Position GoaltenderCaught RightPlayed for Edmonton OilersToronto Maple LeafsBuffalo SabresLos Angeles KingsSt. Louis BluesCalgary FlamesNational team  CanadaNHL Draft 8th overall, 1981Edmonton OilersPlaying ca...

 

Prijono Prijono (20 July 1907 – 6 March 1969[1]) was an Indonesian politician and academic. Prijono was a leading figure of the Murba Party and the Indonesian Peace Committee.[2] Prijono served as Minister of Education and Culture between 1957 and 1966.[3][4] He was one of the intellectual ideologues who surrounded President Sukarno.[1] In December 1954 he was awarded the Stalin Peace Prize.[2] Academic Prijono studied in Paris and obtaine...

Road in China This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: China National Highway 105 – news · newspapers · books · scholar · JSTOR (November ...

 

アラバマ 基本情報建造所 バージニア州ノーフォーク海軍工廠運用者 アメリカ海軍艦歴発注 1939年4月1日起工 1940年2月1日進水 1942年2月16日就役 1942年8月16日退役 1947年1月9日除籍 1962年6月1日その後 1964年6月11日より博物館船として公開要目基準排水量 35,000 トン満載排水量 44,374 トン全長 680フィート (210 m)最大幅 108フィート2インチ (32.97 m)吃水 35フィート1インチ (10.69...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!