Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Porwik P.

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: linear Boolean function

Sortuj według:

Ogranicz wyniki do:

The Three-Yalued Sign Walsh Coefficients Calculation for an Affine Boolean Function Recognition

Porwik P.

Archiwum Informatyki Teoretycznej i Stosowanej

2005

T. 17, z. 3

199-211

The paper discusses a problem of recognition of the Boolean function linearity. The linearity of function is investigated by means of the threevalued sign Walsh coefficients. The linearity and nonlinearity play an important role in many domains especially in designing of digital circuits. The knowledge about spectral coefflcients distribution allows to determine the various combinatorial properties of the Boolean functions: redundancy, monotonicity, self-duality, correcting capability, etc., which seems to be more difficult in realization by means of others methods. Experimental results demonstrate the efficiency of the approach.

W pracy przedstawiono metodę rozpoznawania afmicznej funkcji boolowskiej na podstawie analizy jej trójwartościowego, znakowego widma Walsha. Boolowskie funkcje liniowe (afmiczne) są ważną klasą funkcji wykorzystywaną w kryptografii, projektowaniu układów arytmetycznych i kodów kontrolnych. Ze względu na ważność zagadnienia, metody znajdowania lub rozpoznawania takich funkcji są ciągle przedmiotem badań i udoskonaleń. Wykazano, że dla celów rozpoznawania w pełni określonych funkcji afinicznych klasyczną transformację Walsha-Hadamarda można uprościć i zrealizować w wersji znakowej, co ogranicza zakres dopuszczalnych wartości widma. W pracy wykazano, że widmo wyznaczone dla funkcji zapisanej w postaci ON-sześcianów (ang. cubes) może zostać również uproszczone. Zaproponowano trójwartościową reprezentację widma, gdzie używane są tylko trzy znaki (symbole) {+1, -1,0},co zmniejsza liczbę bitów niezbędnych do przechowywania wartości widma. Wyznaczono złożoność obliczeniową (O) oraz pamięciową (M) w bajtach obu przedstawionych w pracy metod. Wartości te wynoszą odpowiednio: dla znakowej transformacji Walsha-Hadamarda: O(2n) oraz M(2n+2), natomiast dla znakowej transformacji wykorzystującej zapis w postaci sześcianów O(n2 2n) oraz M(2n-2).

Efficient spectral method of identification of linear Boolean function

Porwik P.

Control and Cybernetics

2004

Vol. 33, no 4

663-678

This paper discusses a problem of recognition of the Boolean function's linearity. The article describes the spectral method of analysis of incompletely specified Boolean functions using the Walsh Transform. The linearity and nonlinearity play an important role in design of digital circuits. The analysis of the spectral coefficients' distribution allows to determine the various combinatorial properties of the Boolean functions: redundancy, monotonicity, self-duality, correcting capability, etc. which seems to be more difficult to obtain by means of other methods. In particular, the distribution of spectral coefficients allows us to determine whether Boolean function is linear. The method described in the paper can be easily used in investigations of large Boolean functions (of many variables), what seems to be very attractive for modern digital technologies. Experimental results demonstrate the efficiency of the approach.