Powiadomienia systemowe
- Sesja wygasła!
Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Metoda wyznaczania nieliniowości funkcji boolowskich za pomocą transformacji Walsha
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Rocznik
Tom
Strony
51--64
Opis fizyczny
Twórcy
autor
- Division of Electronics&Computer Systems University of Silesia ul. Będzińska 60 41-200 Sosnowiec
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUJ1-0007-0021