Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Representation of direct product of permutation groups as symmetry groups of boolean functions

Jasionowski P.

Theoretical and Applied Informatics

2012

Vol. 24, No. 2

119-133

We consider boolean functions invariance groups S(f) and some special kinds of boolean functions. We construct a k valued boolean function f which represent a direct product of two permutation groups and give an upper bound of k. Moreover we show that in some cases we can construct 2 valued boolean function which represent this product.

Rozważamy moduł M o n stanach wejściowych x1, x2,....... xn, z których każdy może przyjmować jeden z dwóch możliwych stanów 0 lub 1. Ponadto na wyjściu rozważany moduł przyjmuje także tylko te same dwa stany 0 lub 1 (uogólnieniem takich modułów są urządzenia przyjmujące na wyjściu k różnych wartości dla k większe niż 2, o których także piszemy w jednym z rozdziałów tej pracy). Wyjście modułu w ogólności zależy od uporządkowania danych wejściowych x1, x2,....... xn. Istnieja˛ pewne permutacje danych wejściowych które pozostawiają stan wyjściowy niezmieniony. Na przykład jeśli wyjście modułu M w ogóle nie zależy od uporządkowania danych wejściowych to taki moduł nazywamy symetrycznym. Każdy taki moduł może być jednoznacznie powiązany z opisującą go funkcją boolowską. Mając daną taką funkcję możemy skonstruować grupę permutacji (grupę symetrii) odpowiadajacątej funkcji. Dla funkcji boolowskiej f : {0,1}n strzałka w prawo {0,1,....., k-1} grupę taką definiujemy jako zbiór wszystkich permutacji sigma należących do grupy symetrycznej zbioru n elementowego które spełniają warunek f(x1, x2,..... xn) = f(x sigma(1), x sigma (2),.... x sigma(n)) dla dowolnego wektora boolowskiego (x1, x2, …... xn). Punktem wyjścia do naszych rozważań były prace P. Clote, E. Kranakis, Boolean function invariance groups, and parallel complexity., J. Comput., Vol. 20, No. 3, 1991, 553-590. oraz P. Clote, E. Kranakis, Boolean function and Computation Models, Springer, Berlin, 2002. W pracach tych pojawiły się pewne specjalne konstrukcje funkcji boolowskich oraz grup symetrii tych funkcji. Rozważany problem ma bezpośrednie odniesienie do ułożenia takich modułów w układzie scalonym, w którym permutacje danych wejściowych są dozwolone, lub gdy porządek wejść jest zadany tylko częściowo. Główne rezultaty uzyskane w tej pracy dotyczą iloczynów prostych grup permutacji, a w szczególności iloczynów prostych grup symetrycznych. Przedstawiono tu konkretne algorytmy tworzenia funkcji boolowskich w przypadkach gdy rozważamy iloczyny dowolnej (skończonej) liczby grup symetrycznych. Rozważania zostały podzielone na kilka odrębnych przypadków. W sytuacji ogólnej, gdy rozważamy iloczyn prosty dowolnych grup permutacji podajemy ograniczenie górne dla k reprezentowalności poprzez funkcję boolowska. Podobnie jak autorzy P. Clote, E. Kranakis uważamy, że rozważania dotyczące grup symetrii funkcji boolowskich doprowadzą do algorytmów optymalizujących przestrzeń w projektowaniu układów VLSI. W szczególności mogą one odpowiedzieć na pytanie, kiedy możemy zamienić miejscami poszczególne moduły lub bloki modułów nie zmieniając przy tym uzyskiwanej funkcji na wyjściu.