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

• Autorzy: Porwik P.

Warianty tytułu

PL

Rozpoznawanie afinicznej funkcji boolowskiej na podstawie jej trówartościowego znakowego widma Walsha

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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).

Słowa kluczowe

EN

Walsh coefflcients; coefflcients distribution; Boolean functions; linear Boolean function

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2005
• Tom: T. 17, z. 3
• Strony: 199--211
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Porwik P.

Bibliografia

• [1] Ahmed N. Rao K.R.. Orthogonal Transforms for Digital Signal Processing. Springer-Verlag. Berlin. 1975
• [2] Besslich Ph.W.. Trachtenberg E.A.. Binary input/ternary output switching circuits designed via the sign transformation. Proc. of the 22nd IEEE International Symposium on Multiple-valued logic. Sendai. Japan. 1992. pp. 348-354
• [3] Besslich Ph.W., Trachtenberg E.A.. Three-valued quasi linear transformation for logic synthesis. IEE Proc.Comp. Digital Technique. No 143(6). 1996. pp. 391-400.
• [4]Clarke E.M.. McMillan K.L.. Zhao. X.. Fujita M.. Spectral Transformation for Extremely Large Boolean functions. Proc. of the I FI P WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design. 1993. pp. 86-90.
• [5]Falkowski B.J.. Porwik P.. Evaluation of Nonlinearity in Boolean Functions by Extended Walsh- Hadamard Transform. 2nd Int. Conf. on Information Communications and Signal Processing ICISC'99. Singapore paper 2B2.2 1999. pp 1-4.
• [6]Falkowski B.J.. Kannurao S.. Generation of sign Walsh spectra from disjoint cubes of Boolean function. Computers and Electrical Engineering. Pergamon Press. No 28. 202. pp. 631-641.
• [7]Falkowski B.J.. Schafer 1.. Perkowski M.A.. Effective Computer Methods for the Calculation of Rademacher-Walsh Spectrum for Completely and Incompletely Specified Boolean Functions IEEE Tran, on Computer-Aided Design. Vol. 11. No 10.. 1992. pp. 1207-1226.
• [8| Falkowski B.. Van S.. Fidex sign Walsh hardware structure. Journal of IEICE Electronics Express. Japan. Vol. 2. No. 2. 2005. pp. 91-96.
• |9] Harmuth H.F.. Sequency Theory. Foundations and Applications. Academic Press. New York. 1977.
• [10]Hurst S.L.,Miller D.M.. Muzio J.C.. Spectral Techniques in Digital Logic. Academic Press. London. 1985
• 11] Karpovsky M.G.. Finite Orthogonal Series in the Design of Design of Digital Devices. John Wiley. New York. 1976.
• [12] Porwik P.. Falkowski B.J.. Informatics Properties of the Walsh Transform. 2nd Int. Cun!', on Information Communications and Signal Processing ICISC 99. Singapore. paper2B2.4. 1999. pp. 1-5.
• [13] Porwik P.. Inwards Calculation of Boolean Functions Xonlinearity Using Walsh Transform. Archi wum Informalyki Teoretycznej i Stosowanej PAN. No. 1. T. 12. 2002. pp. 51-64.
• [14] Porwik P.. Efficient calculation of the Reed-Muller forms by means of the Walsh spectrum. Int. Journal of Applied Mathematics and Computer Science. Vol. 12. No.4. 2002. pp.571-579.
• [15]Porwik P.. The Spectral Test of the Boolean Function Linearity. Int. Journal of Applied Mathematics and Computer Science. Vol. 13. No. 4. 203. pp. 567-675.
• [16]Porwik P.. Efficient spectral method of identification of linear Boolean Junction. Int. Journal Control and Cybernetics. Vol. 33. No.4 2004. pp. 663-678.
• [17]Sasao T.. Logic Synthesis and Optimization. Kluwer Academic Publisher. Dordrecht. Holland. 1993.
• [18]Sasao T.. Representation of Logic Functions using FXOR Operators. Workshop on Applications of the Reed-Muller Expansion in Circuit Design. Makuhari.. Japan. 1995. pp. 308-313.
• [19] Seberry J.. Zhang X.M.. Construction of Bent function from Two Know n Bent Functions. Austral-asian Journal of Combinatorics. Vol.9. 1994. pp.2 1-34.
• [20] Stanković R.S.. Astola J.T.. Spectral Interpretation of Decision Diagram. Springer-Verlag. New York. 2003.
• [21]Stankovic R.S. Stojić M.R.. Stankovic M.. Recent Development in Abstract Harmonic Analysis with Applications in Signal Processing. Belgrade. Science Publisher. 1996.
• [22]Yanushkevich S.. Logic Differential Calculus in Multi-Valued Logic Design. Academic Publishers of Technical Univ. of Szczecin. Poland. 1998.