BRIEF INTRODUCTION TO RESEARCH AREAS OF MAREK PERKOWSKI

1. Design Automation of digital
systems and related mathematical theories and programming methods.

 1.1. Exor Logic and Spectral Methods. New representations of Discrete Functions.
 1.2. Layout-driven Logic Synthesis for Deep Sub-Micron Technologies.
 1.3. Functional Decomposition of Discrete Functions.
 1.4. High-level Design Models: Non-Deterministic Finite State Machines, 
      Recursive Machines, and Glushkov Machines.

2. Machine Learning.

 2.1. Constructive Induction Approach based on Ashenhurst/Curtis 
      and other Decomposition Approaches. 
 2.2  Applications in Medicine: Ovulation Confirmation and Prediction.

3. Reconfigurable Computing

  3.1. Hardware-Software Codesign of NP-Complete Combinatorial Algorithms.
  3.2. Cube Calculus Machine.
  3.3. FPGA based High Performance Emulator DEC PERLE-1.

4. Field Programmable Analog Arrays and Mixed Digital/Analog Programmable Arrays.
   Low-cost supercomputing.

5. Intelligent  Robotics.

MORE DETAILS

1.1. Exor Logic and Spectral Methods. New representations of Discrete Functions.

• Project Started: 1987.
  
• Former Students: Haomin Wu, Martin Helliwell, Ingo Schaefer, Andisheh Sarabi, Bogdan Falkowski, Philip Ho,
  Pan Wu, Li-Fei Wu, and many other contributed to this project in 1988 - 1994.
  
• Current Students: Song Ning.
  
• Funding: NSF, PSU, Dutch NSF, US industry.
  
• Since 1987 Dr. Perkowski has worked on application of
  spectral methods to the synthesis of logic circuits.
  
• The special emphasis was on the binary logic with multiple-valued inputs, new orthogonal
  (Linearly Independent) transforms for logic synthesis, design for testability, minimization of three and multi-level logic circuits, and the design of circuits with high
  
• In the last few years Dr. Perkowski's group has worked on application of spectral methods to the synthesis of logic circuits.
  The special emphasis was on the binary logic with multiple-valued inputs, new orthogonal (Linearly Independent) transforms for logic synthesis, design for testability, minimization of three and multi-level logic circuits, and the design of circuits with high percentage of EXOR gates.
  In this last area Dr. Perkowski and his students designed several algorithms and computer programs (for Reed Muller forms, Generalized Reed Muller forms, Mixed Polarity Exclusive Sum of Products form) that are or have been considered the most advanced and the fastest programs available.
  
• Especially known is our EXORCIM-MV program for approximate minimization of ESOP functions for multi-output, multi-valued incomplete functions. Song Ning works on improving EXORCISM-MV-3 and implementation of SOP and AND/OR/EXOR multi-level minimizers for regular arrays.
  
• Recently, several families of new Linearly Independent transforms have been found in our group, that find applications not only to logic synthesis but also in image coding and recognition.
  The created for them fast algorithms were implemented in computer programs whose aplications in image processing are now investigated.
  
• We invented also a new representation called Multi-Valued Cube Diagram Bundles, especially useful for strongly unspecified functions.
  
• Several papers recently published, accepted or submitted. Most of the work recently is only theoretical and performed by Marek Perkowski. Collaboration with Profs. Rolf Drechsler, Bernd Steinbach, Lech Jozwiak and Dr. B. Falkowski.

1.2. Layout-driven Logic Synthesis for Deep Sub-Micron Technologies.

• Project Started: 1990.
  
• Former Students: Tushar Shah, Sanof Mohamed.
  
• Current Students: Craig Files, Karen Dill, Ben Drucker.
  
• Funding: CNRS (French NSF), PSU.
  
• In collaboration with Professor Malgorzata Chrzanowska-Jeske, we investigate the so-called Lattice Diagrams as improved models of representation of Boolean functions.
  Next, these diagrams are mapped directly to hardware, especially using pass transistor.
  They allow for very regular layout and short, local connections.
  
• We considered also more generalized diagrams that include Shannon, Positive Davio and Negative Davio expansions.
  Several papers have been submitted in 1997 and numerical results are very good.
  
• In another approach, in collaboration with Professors Daniel Auvergne and Michel Robert from the University of Montpellier, we investigate networks from complex gates for layout generators.
  Two papers have been published in 1996.
  
• In yet another approach, Marek Perkowski and Edmund Pierzchala, in collaboration with Prof. Rolf Drechsler from University of Freiburg, Germany, investigate Multi-Valued, continuous and word-level (integer) Lattice Diagrams and their hardware realizations.
  Two papers have been submitted in 1997.

1.3. Functional Decompositions of Discrete Functions.

• Project Started: 1986.
• Former Students: Hoang Uong, James Brown, Wei Wan.
• Current Students: Craig Files, Sridhar Srinivasan.
  
• Funding: NSF, CNRS (French NSF), PSU.
• We apply the generalization of the Ashenhurst/Curtis Decomposition to relations for logic synthesis for layout, and FPGAs.
  Three papers will be published in 1997.

1.4. High-level Design Models: Non-Deterministic Finite State Machines, Recursive Machines, and Glushkov Machines.

• Project Started: 1983.
  
• Former Students: Jiuling Liu, David Smith, William Zhao, Nhat Nguyen, Loc Bao Nguyen, and many other.
  
• Current Student: Dwaine Franzke.
  
• Current Funding: none.
  
• Other area of our research are Finite State Machines. Dr. Perkowski created several efficient algorithms for state assignment and state minimization of state machines.
  He wrote also a unique program for concurrent state minimization and state assignment.
  
• In this area, Dr. Perkowski and his students collaborated with several companies, incuding GTE, Intel, Sharp Microelectronics, and Cypress Semiconductor.
  
• The system, developed and partially implemented by Dr. Perkowski for Cypress, became next the first integrated system to design highly concurrent sequential logic starting from VHDL-specified And_OR_Not Graphs.
  
• The concept of And-Or_Not Graphs, introduced by him, is the powerful generalization of Petri nets, parallel regular expressions, and other models of micro-parallelism.
  
• The concept was implemented in Warp system.
  
• Current work includes:
  automatic design of non-deterministic state machines.
  Two-dimensional State Minimization of FSMs and non-deterministic FSMs,
  State Assignment of FSMs and non-deterministic FSMs for low power,
  Design of stack machines,
  Design of iterative networks of state machines (kind of "general and soldier" problem - see Minsky).
  Formal specification and minimization of Glushkov machines (Glushkov machines, not known in the West, are the most general mathematical model of digital systems, they allow to optimize concurrently the control-unit finite state machine and the collaborating with it data-path infinite state machine. Algebra of transformations and constraints is used).

2. Machine Learning.

2.1. Constructive Induction Approach based on Ashenhurst/Curtis and other Decomposition Approaches.



• Project Started: 1994.
  
• Former Students: Zhi Wang, Jin Zhang, Marcel Kolsteren, and many other.
  
• Current Students: Stanislaw (Stach) Grygiel, Craig Files, Paul Burkey, Mike Burns, Rahul Malvi, Rahul Malvi, Vishnu Gandhyay, Robert Gatlin, Sridhar Srinivasan.
  
• Funding: Air Force Office of Scientific Research, ABTECH Corp., PSU.
  
• New functional decomposition models are used for learning with supervision. This project is sponsored by and we collaborate with Wright Laboratories of US. Air Force and ABTECH Corporation. Currently we work on adding noise models to our "decomposition of MV relations" model of learning. We collaborate on this topic with Professor Malgorzata Marek-Sadowska from U.C. Santa Barbara, Professor Lech Jozwiak from TU Einhoven and Professor's Tadeusz Luba group fro TU Warsaw.

2.2. Applications in Medicine: Ovulation Confirmation and Prediction.



• Project Started: 1980.
  
• Former Students: Edmund Pierzchala, Shiliang Wang, Cecilia Espinoza, Omar Bermudez.
  
• Current Students: Stanislaw Grygiel.
  
• Former Funding: Pope's John Paul II Commission for Families, PSU, NIH.
  
• Current Funding: None.
  
• In a related research, Functional Decomposition of MV Relations is used as a learning method for ovulation confirmation and prediction.
  Stan Grygiel compares it with the existing rule-based and probabilistic NN approaches that we and other developed since 1980.
  A prototype rule-based PC-based Ovulocomputer with measurements of temperature and many subjective symptomps was designed by Omar Bermudez.
  

3. Reconfigurable Computing

3.1. Hardware-Software Codesign of NP-Complete Combinatorial Algorithms.

3.2. Cube Calculus Machine.

3.3. FPGA based High Performance Emulator DEC PERLE-1.



• Project Started: 1994.
  
• Past Students: David Foote, Coen Englebarts, Edmund Pierchala, Song Ning.
  
• Present Students: Chen Qihong, Guangsheng Ren.
  
• Current Funding: NSF, PSU, software and hardware donations from Intel, Orcad, Sharp and Cypress.
  
• Dr. Perkowski supervises the development of a Cube Calculus Machine, under design by his several graduate students.
  
• This is a FPGA-based reconfigurable supercomputer to perform combinatorial optimization using cube calculus theory in multiple-valued input algebra, perform transforms, and solve some image processing problems.
  
• This highly parallel architecture generalizes the concept of systolic architecture. When ready, this computer will permit to speed up execution of a class of important algorithms of several orders of magnitude.
  
• We are also collaborating on this topic with Professor Lech Jozwiak from Technical University of Eindhoven and Professor Malgorzata Chrzanowska-Jeske.

4. Field Programmable Analog Arrays.

• Project Started: 1989.
  
• Students: Edmund Pierzchala.
  
• Previous Funding: PSU, Design Automation Conference, Research Corp., private investors.
• Current Funding at PSU EE Dept.: none.
  
• We were the second group in the world that developed the concept of analog FPGAs, and the first to develop high-performance fine-grain Mixed FPAAs with local connections.
  
• A company, ANALOGIX, INC., was started to commercialize this technology.

5. Intelligent Robotics.

• Project Started: 1987.
  
• Past Students. Cecilia Espinoza, Kevin Stanton, Dieudonne Mayi, Shiliang Wang.
  
• Current Student. Vaughn Zeechman.
  
• Previous Funding: PSU, Blind of Oregon, private donors.
  
• Current Funding: none.
  
• Other area of Dr. Perkowski's interests, includes applications of spectral and other mathematical methods to image processing and recognition.
  
• This research found applications in two areas: analysis of the so-called "ferning patterns" of cervical mucus with applications in gynecology, and scene analysis for a PSUBOT - the self-navigating wheelchair equipped with TV cameras and AI software.
  
• Two systems have been completed, were functional and documented.
  
• Vaughn Zeechman works on a parallel system based on microcontrollers to take over some tasks from PC.
  
• Unfortunately, because of the lack of funding, little has been achieved in these areas since 1993.
  
• For papers, reports, etc. see elsewhere in this WWW Page or pages of students. Please send questions.

  IMPORTANT !!

  Thanks to outside readers of this WWW Page for many requests of our papers, unfortunately the papers that are not yet available on WWW, are mostly not in Latex, and we have to change their format, retype, or to scan them.
  Our goal is to link every published or accepted paper of our group to WWW, but it takes time.