A TUTORIAL INTRODUCTION TO MULTIPLE-VALUED LOGIC.


PORTLAND STATE UNIVERSITY
DEPARTMENT OF ELECTRICAL
AND COMPUTER ENGINEERING
SYMPOSIUM



Marek Perkowski In May 2000 a 30th International Symposium on Multiple-Valued Logic (ISMVL) will take place in Portland, Oregon. Dr. Perkowski is the Chair of this symposium and several other PSU ECE faculty are involved. It will be a unique opportunity for Oregon's EDA engineers to listen to presentations of top world researchers in the theory of logic synthesis, such as Professors Sasao, Rosenberg, Butler, Moraga, K.C. Smith, Mukaidono and others.

ISMVL has been a birthplace of fuzzy logic, spectral methods, multi-valued simulation, decomposition and many other ideas that became since a mainstream of software and hardware research projects worldwide. For instance, fuzzy logic hardware controls a train in Sendai Japan, and multi-valued memory chip has been fabricated by Intel. Multi-valued image processing VLSI chips have been developed recently in Japan, and multi-valued decomposers for Machine Learning in Slovenia, Germany, Holland, Poland, USA, Japan and Canada. These ideas have been also used by IBM researchers to predict stock market.

However, in contrast to binary logic that everybody knows, in most Universities there are no classes that would teach about MVL. The goal of this talk will be to help understand the fundamental ideas, concepts and notations used in MVL so that the audience will be prepared to understand (at least some of) the ISMVL talks, panel discussions and posters, as well as to read original research papers (look to Dr. Perkowski's WWW Page for more information).

Firstly, we will review briefly basic binary gates and we will show how the MV gates generalize binary gates; for instance gate MINIMUM generalizes gate AND. We will generalize the familiar concepts of Karnaugh maps and binary decision diagrams to MV logic, and next we will discuss MV spectral approaches, that have some relation to DSP transforms that you may know from other classes. Binary function will be generalized to MV relations by generalizing the concept of a "don't care". Optimization techniques and open research problems will be very briefly mentioned.

Multi-valued logic has applications in software and in hardware. First, as you may guess, MV gates are built as circuits and next MV VLSI chips are built with them. This approach is still rare in industry, but many researchers expect that new optical, DNA and quantum computers that will arrive before year 2020 will use MV logic.

Secondly, and this is already used in practice today, MV logic is used as a mathematical notation in logic synthesis programs, which allows to minimize functions more efficiently and with more levels of logic. For instance, a popular program ESPRESSO used by many EDA companies, uses MV logic internally.

Thirdly, MV logic networks synthesized automatically are software data. They can be next transformed, interpreted, analyzed and evaluated entirely by software, so there is no need to practically build the MV gates. Such approaches have been used in many commercial and academic programs for image processing, pattern recognition, Data Mining, Machine Learning, and Knowledge Discovery from Data Bases.

For those interested, there is much information on MVL from Dr. Perkowski's WWW Page, and Alan Mishchenko developed a graphical MVL simulator and fault simulator that you can download from his WWW Page and play with to understand the MVL concepts intuitively. It allows to use arbitrary MV gates specified by tables.

SHORT BIOGRAPHY

Marek A. Perkowski

A native of Poland, Marek A. Perkowski has his M.S. and Ph.D Degrees from Warsaw University of Technology, Warsaw, Poland. He has been on the faculty at the Institute of Automatic Control, Warsaw University of Technology, Warsaw, Poland; Department of Electrical Engineering, University of Minnesota; Eindhoven University of Technology, Eindhoven, the Netherlands; University of Montpellier, Montpellier, France, and is currently a professor at the Department of Electrical Engineering, Portland State University. His current interests are in design automation, logic synthesis, Machine Learning and Intelligent Robotics, particularly robot societies and theatre, and his current effort is to organize interdisciplinary Intelligent Robotics Laboratory, in which faculty from different PSU departments and Oregon's universities will participate.

He spend the Summer of 1994 in Wright Laboratories, Wright-Patterson Air Force Base, working on application of Boolean Decomposition to Machine Learning and works on these topics ever since on several grants, includig the very recent one from Intel. This method have been now used by several research groups around the world. The Third Oregon Symposium on Logic, Design and Learning organized this year on May 22, just before ISMVL, will be devoted to applications of logic synthesis methods outside traditional circuits design, and mainly to robotics.

Dr. Perkowski has taught courses in Advanced Design Automation, Intelligent Robotics, Advanced Logic Synthesis, Finite State Machines, Control Unit Design, Fast Prototyping usignn FPGAs, Image Processing, Artificial Intelligence, VLSI Design, Logic Design, Microprocessors, Computer Architecture, Lisp and AI Languages, Digital Design using VHDL and Verilog, Test and Design for Test, and Formal Methods in Design and Verification.

His main research accomplishment is creation of a comprehensive theory of EXOR logic, based on spectral and linear algebra fundaments which is a powerful generalization of the AND/OR theory used currently in industry. The theory and associated CAD tools allow to synthesize very testable multi-level logic circuits with EXOR, AND, and OR gates. Four international workshops in this area have been organized since 1993 and some tools are used in industry. He has research publications in digital circuits, logic synthesis, state machines, computer architecture, image processing, Machine Learning, Artificial Intelligence, and biomedical applications. His publications include four books, 12 book chapters, and a total of 212 other papers. He consulted and worked as summer professor and software contractor for several companies.