This book brings together five topics on the application of Boolean functions. They are
1. Equivalence classes of Boolean functions: The number of n-variable functions is large, even for values as small as n = 6, and there has been much research on classifying functions. There are many classifications, each with their own distinct merit.
2. Boolean functions for cryptography: The process of encrypting/decrypting plaintext messages often depends on Boolean functions with specific properties. For example, highly nonlinear functions are valued because they are less susceptible to linear attacks.
3. Boolean differential calculus: An operation analogous to taking the derivative of a real-valued function offers important insight into the properties of Boolean functions. One can determine tests or susceptibility to hazards.
4. Reversible logic: Most logic functions are irreversible; it is impossible to reconstruct the input, given the output. However, Boolean functions that are reversible are necessary for quantum computing, and hold significant promise for low-power computing.
5. Data mining: The process of extracting subtle patterns from enormous amounts of data has benefited from the use of a graph-based representation of Boolean functions. This has use in surveillance, fraud detection, scientific discovery including bio-informatics, genetics, medicine, and education.
Written by experts, these chapters present a tutorial view of new and emerging technologies in Boolean functions.
Table of Contents
Equivalence Classes of Boolean Functions
Boolean Functions for Cryptography
Boolean Differential Calculus
Synthesis of Boolean Functions in Reversible Logic
Data Mining Using Binary Decision Diagrams
About the Author(s)Tsutomu Sasao
, Fukuoka, Japan
Tsutomu Sasao received the B.E., M.E., and Ph.D. degrees in Electronics Engineering from Osaka University, Osaka Japan, in 1972, 1974, and 1977, respectively. He has held faculty/research positions at Osaka University, Japan, IBM T. J. Watson Research Center, Yorktown Height, NY and the Naval Postgraduate School, Monterey, CA. He has served as the Director of the Center for Microelectronic Systems at the Kyushu Institute of Technology, Iizuka, Japan. Now, he is a Professor of Department of Computer Science and Electronics. His research areas include logic design and switching theory, representations of logic functions, and multiple-valued logic. He has published more than 8 books on logic design including, Logic Synthesis and Optimization
, Representation of Discrete Functions
, Switching Theory for Logic Synthesis
, and Logic Synthesis and Verification
, Kluwer Academic Publishers 1993, 1996, 1999, 2002 respectively. He has served as Program Chairman for the IEEE International Symposium on Multiple-Valued Logic (ISMVL) many times. Also, he was the Symposium Chairman of the 28th ISMVL held in Fukuoka, Japan in 1998. He received the NIWA Memorial Award in 1979, Takeda Techno Entrepreneurship Award in 2001, and Distinctive Contribution Awards from IEEE Computer Society MVL-TC for papers presented at ISMVLs, in 1987, 1996, 2003. He has served an associate editor of the IEEE Transactions on Computers. He is a Fellow of the IEEE.Jon Butler
, California, USA
Jon T. Butler received the B.E.E. and M.Engr. degrees from Rensselaer Polytechnic Institute, Troy, New York, U.S.A., in 1966 and 1967, respectively. He received the Ph.D. degree from The Ohio State University, Columbus, Ohio, U.S.A., in 1973. Since 1987, he has been a Professor at the Naval Postgraduate School, Monterey, California, U.S.A. From 1974 to 1987, he was at Northwestern University, Evanston, Illinois, U.S.A. During that time he served two periods of leave at the Naval Postgraduate School, first as a National Research Council Senior Postdoctoral Associate (1980-1981) and second as the NAVALEX Chair Professor (1986-1987). He served one period of leave as a foreign visiting professor at the Kyushu Institute of Technology, Iizuka, Japan. His research interests include logic optimization, multiple-valued logic, and reconfigurable computing. He has served on the editorial boards of the IEEE Transactions on Computers, Computer, and the IEEE Computer Society Press . He has served as the editor-in-chief of Computer and the IEEE Computer Society Press. He received the Award of Excellence, the Outstanding Contributed Paper Award, and a Distinctive Contributed Paper Award for papers presented at the International Symposium on Multiple-Valued Logic. He received the Distinguished Service Award, two Meritorious Awards, and nine Certificates of Appreciation for service to the IEEE Computer Society. He is a Life Fellow of the IEEE.