Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: transformacje Walsha

Sortuj według:

Ogranicz wyniki do:

Towards calculation of boolean functions nonlinearity using Walsh transform

Porwik P.

Archiwum Informatyki Teoretycznej i Stosowanej

2000

T. 12, z. 1

51-64

The estimation of nonlinearity function has wide applications in cryptography, transmission of information, correction of erros, etc. Linearity and nonlinearity plays important role in designing of digital circuits too - particularly in build of Boolean functions through spectral decomposition. This work presents a method to evaluate linearity and nonlinearity by analysis of spectral coefficients. The nonlinearity can be expressed in terms of Walsh spectra of Boolean functions. In this paper relation between linear Boolean functions and their Walsh spectra is presented. Analysis of the coefficients' distribution allows determining various combinatorial properties of the Boolean functions: redundancy, monotonicity or linearity for example, what seems to be more difficult to execute by means of other methods. Additionaly the Walsh-Hadamard transform allows us to accelerate the computer calculates, particularly for very large Boolean functions (of many variables) and to reduce the cost of correlation computations.

W pracy przedstawiono metodę wyznaczania liniowości i nieliniowości funkcji boolowskiej za pomocą transformacji Walsha. Koncepcja zaproponowanego rozwiązania polega na obliczaniu współczynników korelacji R lub S pomiędzy badaną funkcją boolowską i odpowiednią podstawową lub rozszerzoną dyskretną funkcją Walsha. Stosując znany algorytm szybkiej transformacji Walsha, można zredukować złożoność wyznaczania nieliniowości do n2n operacji dodawań. Jednokrotne obliczenie współczynników (widma) ze zbioru R lub S jest równoznaczne ze znajomością współczynników liniowości/nieliniowości badanej funkcji boolowskiej w stosunku do wszystkich innych możliwych funkcji liniowych o tym samym rozmiarze. Metoda może być stosowana podczas weryfikacji projektów układów cyfrowych oraz w kryptografii.