Efficient Algorithm of Affine form Searching for Weakly Specified Boolean Function

• Autorzy: Porwik P.
• Języki publikacji: EN

Abstrakty

EN

This paper presents the spectral method of recognition of an incompletely defined Boolean function. The main goal of analysis is fast estimation whether a given single output function can be extended to affine form. Furthermore, a simple extension algorithm is proposed for functions, for which the affine form is reachable. The algorithm is compared with other methods. Theoretical and experimental results demonstrate the efficiency of the presented approach.

Słowa kluczowe

EN

Walsh coefficients; coefficients; distribution; incompletely defined Boolean function; affine function

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 77, nr 3
• Strony: 277--291
• Opis fizyczny: bibliogr. 22 poz., tab.

Twórcy

autor

Porwik P.

• Institute of Informatics University of Silesia Będzińska 39, 41-200 Sosnowiec, Poland,

Bibliografia

• [1] Ahmed N., Rao K.R.: Orthogonal Transforms for Digital Signal Processing, Springer-Verlag. Berlin, 1975.
• [2] Aho A., V., Hopcroft J.E., Ullman J.D.: Data Structures and Algorithms, Pearson Education Inc. Bell Telephone Laboratories, 1983.
• [3] Canteaut A., Carlet C., Charpin P., Fontaine C.: On cryptographic properties of the cosets of RM(1,m), IEEE Trans. Inform. Theory, 47(4),2001, 1494-1513.
• [4] 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, 1999, 1-4.
• [5] Falkowski B.J., Schafer I., PerkowskiM.A.: Effective ComputerMethods for the Calculation of Rademacher-Walsh Spectrum for Completely and Incompletely Specified Boolean Functions. IEEE Trans. on Computer-Aided Design, 11(10), 1992, 1207-1226.
• [6] Fujita M., Yang J., Clarke E., Zudong Z., McGeer P.: Fast Spectrum Computation for Logic Functions using Binary Decision Diagrams, IEEE Int. Symp.Circuits and Systems, 1994, 275-278.
• [7] Graham A.: Kronecker Products and Matrix Calculus with Applications, John Wiley&Sons, New York, 1981.
• [8] Hurst S.L., Miller D.M., Muzio J.C.: Spectral Techniques in Digital Logic, Academic Press, London, 1985.
• [9] KarpovskyM.G.: Finite Orthogonal Series in the Design of Digital Devices, JohnWiley, New York, 1976.
• [10] Karpovsky M.G., Stankovi´c R.S., Astola J.T.: Reduction of Size Decision Diagrams by Autocorrelation Functions, IEEE Trans. on Comp.,52(5), 2003, 592-606.
• [11] Mishchenko A., Perkowski M.: Fast Heuristic Minimization of Exclusive-Sum-of-Products, Proc. of Reed-Muller Workshop, Starkville, Mississippi, 2001, 242-250.
• [12] 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, 571-579.
• [13] Porwik P.: The Spectral Test of the Boolean Function Linearity, Int. Journal of Applied Mathematics and Computer Science, Vol.13, No.4, 2003, 567-575.
• [14] Porwik P.: Walsh Coefficients Distribution for Some Types of Boolean Function, Archives of Theoretical and Applied Informatics, Polish Acad. Sci, Vol.16, No.2, 2004, 109-120.
• [15] Porwik P.,Wrobel K., Zaczkowski P.: Some practical remarks about Binary Decision Diagram size reduction, IEICE Electronic Express, Japan, Vol.3, No.3, 2006, 51-57.
• [16] Sasao T.: Representation of Logic Functions using EXOR Operators, Workshop on Applications of the Read-Muller Expansion in Circuit Design, Makuhari, Japan, 1995, 308-313.
• [17] Seberry J., Zhang X.M.: Construction of Bent Function from Two Known Bent Functions, Australasian Journal of Combinatorics, Vol.9, 1994, 21-34.
• [18] Sloane N.J.A.,MacWiliams F.J.: The Theory of Error-Corecting Codes, North-Holland Publishing Company, 1977.
• [19] Stankovi´c R.S., Falkowski B.: Spectral Transform Calculation through Decision Diagrams. VLSI Design. Vol.14(1), 2002, 5-12.
• [20] Stergiou S., Daskalakis K., Papakonstantinou G.: A Fast and Efficient Heuristic ESOP Minimization Algorithm. Great Likes Symposium on VLSI, Boston, MA., USA, 2004, 78-81.
• [21] Yanushkevich S.: Logic Differential Calculus in Multi-Valued Logic Design, Academic Publishers of Technical Univ. of Szczecin, Poland, 1998.
• [22] Zakrevskij A.: Search Space Reducing: a Super-Fast Algorithm for Minimum AND/EXOR Implementation of System of Weakly Specified Boolean Functions, Proc. Int. Conf. on Pattern Recognition and Information Processing, Minsk, Belarus, Vol.1, 1997, 327-331.