Рид-Мюллер кеңеюі - Reed–Muller expansion - Wikipedia

Жылы Логикалық логика, а Рид-Мюллер кеңеюі (немесе Davio кеңеюі) Бұл ыдырау а Логикалық функция.

Логикалық функция үшін біз қоңырау шаламыз

оң және теріс кофакторлар туралы құрметпен , және

логикалық туындысы құрметпен , қайда дегенді білдіреді XOR оператор.

Сонда бізде Рид-Мюллер немесе Давионың жағымды кеңеюі:

Сипаттама

Бұл теңдеу а-ға ұқсас етіп жазылған Тейлордың кеңеюі туралы туралы . Кеңеюге сәйкес келетін осындай ыдырау бар (Дэвионың теріс кеңеюі):

Рид-Мюллер кеңеюін бірнеше рет қолдану нәтижесінде XOR полиномы шығады :

Бұл ұсыныс ерекше, кейде оны Рид-Мюллер кеңеюі деп те атайды.[1]

Мысалы. үшін нәтиже болар еді

қайда

.

Үшін нәтиже болар еді

қайда

.

Геометриялық интерпретация

Бұл жағдайға кубтық геометриялық интерпретацияны (немесе графикалық-теориялық интерпретацияны) келесі түрде беруге болады: шетінен жылжу кезінде дейін , Коэффициентін алу үшін шеткі екі шыңның функцияларын XOR . Көшу дейін екі қысқа жол бар: бірі - екі жиекті жол ал екіншісі - екі жиекті жол . Бұл екі жол квадраттың төрт шыңын қамтиды және осы төрт төбенің функцияларын XOR-ге айналдыру коэффициентін береді . Соңында, көшу дейін үш қысқа жол болатын алты қысқа жол бар, және бұл алты жол текшенің барлық шыңдарын қамтиды, сондықтан коэффициент барлық сегіз шыңның функцияларын XORing арқылы алуға болады. (Басқа, аталмаған коэффициенттерді симметрия арқылы алуға болады.)

Жолдар

Ең қысқа жолдар барлығы айнымалылардың мәндеріне монотонды өзгерістер енгізеді, ал ең қысқа жолдар осындай айнымалылардың монотонды емес өзгерістерін қамтиды; немесе, басқаша айтқанда, ең қысқа жолдардың барлығының ұзындықтары бастапқы және тағайындалған шыңдар арасындағы Хамминг қашықтығына тең болады. Бұл дегеніміз, ақиқат кестесінен коэффициенттерді алу алгоритмін жалпылау оңай, дегенмен гиперөлшемді жағдайлар үшін ақиқат кестесінің сәйкес жолдарынан функцияның мәндерін XOR шығару арқылы ( және одан жоғары). Ақиқат кестесінің басталатын және тағайындалатын жолдарының арасында кейбір айнымалылардың мәндері тұрақты болып қалады: ақиқат кестесінің барлық жолдарын табыңыз, сол сияқты осы айнымалылар берілген мәндерде өзгермейді, содан кейін олардың функциялары XOR болады және нәтиже келесідей болуы керек: тағайындалған жолға сәйкес келетін мономальды коэффициент. (Мұндай мономиялыққа minterm стиліндегі сияқты мәні 0 болатын айнымалыны жоққа шығарудың орнына мәні 1-ге тең болатын кез-келген айнымалыны қосыңыз (мәні осы жолда) және мәні 0-ге тең болатын кез-келген айнымалыны алып тастаңыз. )

Ұқсас екілік шешім схемалары (BDD), мұнда түйіндер ұсынылады Шеннонды кеңейту сәйкес айнымалыға қатысты біз а анықтай аламыз шешім диаграммасы Рид-Мюллер кеңеюіне негізделген. Бұл шешімдер диаграммалары функционалдық BDD (FBDD) деп аталады.

Туындылар

Рид-Мюллердің кеңеюін Шеннонның ыдырауының XOR-формасынан, сәйкестікті қолдана отырып алуға болады. :

Үшін кеңейтуді шығару :

Екінші ретті буль туындысын шығару:

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Кебшулл, У .; Шуберт, Е .; Розенстиль, В. (1992). «Функционалды шешім схемаларына негізделген көп деңгейлі логикалық синтез». Дизайнды автоматтандыру бойынша 3-ші Еуропалық конференция материалдары.

Әрі қарай оқу

  • Кебшулл, У .; Розенстиль, В. (1993). «Функционалды шешім схемаларын графикке негізделген есептеу және манипуляциялау». Дизайнды автоматтандыру бойынша 4-ші Еуропалық конференция материалдары: 278–282.
  • Максфилд, Клайв «Макс» (2006-11-29). «Рид-Мюллер логикасы». Логика 101. EETimes. 3 бөлім. Мұрағатталды түпнұсқасынан 2017-04-19. Алынған 2017-04-19.
  • Штайнбах, Бернд; Posthoff, Christian (2009). «Кіріспе сөз». Логикалық функциялар мен теңдеулер - мысалдар мен жаттығулар (1-ші басылым). Springer Science + Business Media B. V. б. xv. ISBN  978-1-4020-9594-8. LCCN  2008941076.