WHAT IS 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 ECE faculty are involved. All student members of IEEE will be able to attend this event at a very reduced price or even for free. It will be a unique opportunity for PSU community 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 we learn starting from ECE 171, there are not many classes at PSU that you can learn about MVL. The goal of this talk will be to help you understand the fundamental ideas, concepts and notations used in MVL so that you 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. Much research has been done on MVL by Dr. Perkowski's Ph.D. students, and the talk will briefly introduce our current research and project/thesis opportunities.

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; Department of Electrical Engineering, University of Minnesota; and is currently a professor at the Department of Electrical Engineering, Portland State University. His current interests are in design automation, logic synthesis and Machine Learning.

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. This method have been now used by several research groups around the world.

He has taught courses in Advanced Design Automation, Intelligent Robotics, Image Processing, Artificial Intelligence, VLSI Design, Logic Design, Microprocessors, Computer Architecture, VHDL, Test and Design for Test and Formal 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.