Reed – Muller genişletmesi - Reed–Muller expansion - Wikipedia

İçinde Boole mantığı, bir Reed – Muller genişletmesi (veya Davio genişlemesi) bir ayrışma bir Boole işlevi.

Boole işlevi için Biz ararız

olumlu ve olumsuz kofaktörler nın-nin göre , ve

boole türetimi göre , nerede gösterir ÖZELVEYA Şebeke.

Sonra Reed-Muller'a sahibiz veya olumlu Davio genişlemesi:

Açıklama

Bu denklem, benzer bir şekilde yazılmıştır. Taylor genişlemesi nın-nin hakkında . Bir genişlemeye karşılık gelen benzer bir ayrışma vardır. (negatif Davio genişlemesi):

Reed-Muller genişlemesinin tekrar tekrar uygulanması, bir XOR polinomuna neden olur. :

Bu gösterim benzersizdir ve bazen Reed-Muller genişlemesi olarak da adlandırılır.[1]

Örneğin. için sonuç olurdu

nerede

.

İçin sonuç olurdu

nerede

.

Geometrik yorumlama

Bu duruma aşağıdaki gibi kübik bir geometrik yorum (veya grafik teorik yorum) verilebilir: kenar boyunca hareket ederken -e Katsayısını elde etmek için kenarın iki uç köşesinin fonksiyonlarını XOR . Taşınmak için -e en kısa iki yol vardır: biri, içinden geçen iki kenarlı bir yoldur ve diğeri içinden geçen iki kenarlı bir yol . Bu iki yol, bir karenin dört köşesini kapsar ve bu dört köşenin fonksiyonlarını XORlamak, katsayısını verir. . Sonunda, hareket etmek için -e üç kenarlı yol olan en kısa altı yol vardır ve bu altı yol küpün tüm köşelerini kapsar, bu nedenle katsayısı sekiz köşenin tümünün işlevlerini XORing yaparak elde edilebilir. (Belirtilmeyen diğer katsayılar simetri ile elde edilebilir.)

Yollar

En kısa yolların tümü değişkenlerin değerlerinde monoton değişiklikleri içerirken, en kısa olmayan yolların tümü bu tür değişkenlerin monoton olmayan değişikliklerini içerir; veya başka bir deyişle, en kısa yolların tümü, başlangıç ​​ve hedef köşeleri arasındaki Hamming mesafesine eşit uzunluklara sahiptir. Bu, bir doğruluk tablosundan katsayıları elde etmek için bir algoritmayı, hiper boyutlu durumlar için bile bir doğruluk tablosunun uygun satırlarından XORing yaparak genelleştirmenin kolay olması gerektiği anlamına gelir ( ve yukarıda). Bir doğruluk tablosunun başlangıç ​​ve hedef satırları arasında, bazı değişkenlerin değerleri sabit kalır: doğruluk tablosunun tüm satırlarını, bu değişkenler verilen değerlerde aynı şekilde sabit kalacak şekilde bulun, sonra XOR yukarı fonksiyonlarını ve sonuç, hedef satıra karşılık gelen tek terimli için katsayı. (Böyle bir tek terimliye, değeri 1 olan herhangi bir değişkeni dahil edin (o satırda) ve değeri 0 olan değişkenin olumsuzlamasını minterm stilinde olduğu gibi dahil etmek yerine değeri 0 olan herhangi bir değişkeni (o satırda) hariç tutun. )

Benzer ikili karar diyagramları (BDD'ler), düğümlerin temsil ettiği Shannon genişlemesi göre değişkene göre, bir karar diyagramı Reed-Muller genişlemesine dayalı. Bu karar diyagramlarına işlevsel BDD'ler (FBDD'ler) denir.

Türevler

Reed-Muller genişlemesi, kimlik kullanılarak Shannon ayrıştırmasının XOR-formundan türetilebilir. :

İçin genişlemenin türetilmesi :

İkinci dereceden boole türevinin türetilmesi:

Ayrıca bakınız

Referanslar

  1. ^ Kebschull, U .; Schubert, E .; Rosenstiel, W. (1992). "Fonksiyonel karar diyagramlarına dayalı çok düzeyli mantık sentezi". Bildiriler 3. Avrupa Tasarım Otomasyonu Konferansı.

daha fazla okuma