Electrical and Computer Engineering Commons^™

Uniqueness Of Bilevel Image Degradations, Elisa H. Barney Smith

Electrical and Computer Engineering Faculty Publications and Presentations

Two major degradations, edge displacement and corner erosion, change the appearance of bilevel images. The displacement of an edge determines stroke width, and the erosion ofa corner affects crispness. These degradations are functions of the system parameters: the point spread function (PSF) width and functional form, and the binarization threshold. Changing each of these parameters will affect an image differently. A given amount of edge displacement or amount of erosion of black or white corners can be caused by several combinations of the PSF width and the binarization threshold. Any pair of these degradations are unique to a single PSF …

Efficient Algorithms For Creation Of Linearly-Independent Decision Diagrams And Their Mapping To Regular Layouts, Marek Perkowski, Bogdan Jaroslaw Falkowski, Malgorzata Chrzanowska-Jeske, Rolf Dreschler

Electrical and Computer Engineering Faculty Publications and Presentations

A new kind of a decision diagrams are presented: its nodes correspond to all types of nonsingular expansions for groups of input variables, in particular pairs. The diagrams are called the Linearly Independent (LI) Decision Diagrams (LI DDs). There are 840 nonsigular expansions for a pair of variables, thus 840 different types of nodes in the tree. Therefore, the number of nodes in such (exact) diagrams is usually much smaller than the number of nodes in the well-known Kronecker diagrams (which have only single-variable Shannon, Positive Davio, and Negative Davio expansions in nodes). It is usually much smaller than 1/3 …

Term Trees In Application To An Effective And Efficient Atpg For And–Exor And And–Or Circuits, Lech Jozwiak, Aleksander Ślusarczyk, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

A compact data representation, in which the typically required operations are performed rapidly, and effective and efficient algorithms that work on these representations are the essential elements of a successful CAD tool. The objective of this paper is to present a new data representation—term trees (TTs)—and to discuss its application for an effective and efficient structural automatic test-pattern generation (ATPG). Term trees are decision diagrams similar to BDDs that are particularly suitable for structure representation of AND–OR and AND–EXOR circuits. In the paper, a flexible algorithm for minimum term-tree construction is discussed and an effective and efficient algorithm for ATPG …

Multiple-Valued Quantum Logic Synthesis, Marek Perkowski, Anas Al-Rabadi, Pawel Kerttopf

Electrical and Computer Engineering Faculty Publications and Presentations

This paper asks the question: is logic synthesis for quantum computers a practical research subject?

We would like to assume that any two quantum wires can interact, but we are limited by the realization constraints. Structure of atomic bonds in the molecule determines neighborhoods in the circuit. This is similar to restricted routing in FPGA layout - link between logic and layout synthesis known from CMOS design now appears in quantum. Below we are interested only in the so-called “permutation circuits” - their unitary quantum matrices are permutation matrices.

Generalized Inclusive Forms — New Canonical Reed-Muller Forms Including Minimum Esops, Marek Perkowski, Alan Mishchenko, Malgorzata Chzanowka-Jeske

Electrical and Computer Engineering Faculty Publications and Presentations

Reed-Muller (AND/EXOR) expansions play an important role in logic synthesis and circuit design by producing economical and highly-testable implementations of Boolean functions [3–6]. The range of Reed-Muller expansions include canonical forms, i.e. expansions that create unique representations of a Boolean function. Several large families of canonical forms: fixed polarity Reed-Muller forms (FPRMs), generalized Reed-Muller forms (GRMs), Kronecker forms (KROs), and pseudo- Kronecker forms (PKROs), referred to as the Green/Sasao hierarchy, have been described [7–9]. (See Fig. 1 for a settheoretic relationship between these families.)

Gaussian Beams In Hollow Metal Waveguides: Experiment, Marius Ghita, Lee W. Casperson

Electrical and Computer Engineering Faculty Publications and Presentations

Gaussian beams have been widely used for propagating electromagnetic waves in free space and in certain other optical systems. It has been suggested that recurring forms of such beams might also be useful for propagation in planar or rectangular metal waveguides. Experimental verification of the recurrence of the Gaussian field distribution in metal waveguides is reported here.

Implicit Algorithms For Multi-Valued Input Support Manipulation, Alan Mishchenko, Craig Files, Marek Perkowski, Bernd Steinbach, Christina Dorotska

Electrical and Computer Engineering Faculty Publications and Presentations

We present an implicit approach to solve problems arising in decomposition of incompletely specified multi-valued functions and relations. We introduce a new representation based on binaryencoded multi-valued decision diagrams (BEMDDs). This representation shares desirable properties of MDDs, in particular, compactness, and is applicable to weakly-specified relations with a large number of output values. This makes our decomposition approach particularly useful for data mining and machine learning. Using BEMDDs to represent multi-valued relations we have developed two complementary input support minimization algorithms. The first algorithm is efficient when the resulting support contains almost all initial variables; the second is efficient when …

A General Decomposition For Reversible Logic, Marek Perkowski, Lech Jozwiak, Pawel Kerntopf, Alan Mishchenko, Anas Al-Rabadi, Alan Coppola, Andrzej Buller, Xiaoyu Song, Svetlana Yanushkevich, Vlad P. Shmerko, Malgorzata Chrzanowska-Jeske, Mozammel Huq Azad Khan

Electrical and Computer Engineering Faculty Publications and Presentations

Logic synthesis for reversible logic differs considerably from standard logic synthesis. The gates are multi-output and the unutilized outputs from these gates are called “garbage”. One of the synthesis tasks is to reduce the number of garbage signals. Previous approaches to reversible logic synthesis minimized either only the garbage or (predominantly) the number of gates. Here we present for the first time a method that minimizes concurrently the number of gates, their total delay and the total garbage. Our method adopts for reversible logic many ideas developed previously for standard logic synthesis (such as Ashenhurst/Curtis Decomposition, Dietmeyer’s Composition, non-linear preprocessing …

Fast Heuristic Minimization Of Exclusive-Sums-Of-Products, Alan Mishchenko, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

Exclusive-Sums-Of-Products (ESOPs) play an important role in logic synthesis and design-for-test. This paper presents an improved version of the heuristic ESOP minimization procedure proposed in [1,2]. The improvements concern three aspects of the procedure: (1) computation of the starting ESOP cover; (2) increase of the search space for solutions by applying a larger set of cube transformations; (3) development of specialized datastructures for robust manipulation of ESOP covers. Comparison of the new heuristic ESOP minimizer EXORCISM-4 with other minimizers (EXMIN2 [3], MINT [4], EXORCISM-2 [1] and EXORCISM3 [2]) show that, in most cases, EXORCISM-4 produces results of comparable or better …

Bi-Decomposition Of Multi-Valued Relations, Alan Mishchenko, Marek Perkowski, Bernd Steinbach

Electrical and Computer Engineering Faculty Publications and Presentations

This presentation discusses an approach to decomposition of multivalued functions and relations into networks of two-input gates implementing multi-valued MIN and MAX operations. The algorithm exploits both the incompleteness of the initial specification and the flexibilities generated in the process of decomposition. Experimental results over a set of multi-valued benchmarks show that this approach outperforms other approaches in the quality of final results and CPU time.

Decomposition Of Relations: A New Approach To Constructive Induction In Machine Learning And Data Mining -- An Overview, Marek Perkowski, Stanislaw Grygiel

Electrical and Computer Engineering Faculty Publications and Presentations

This is a review paper that presents work done at Portland State University and associated groups in years 1989 - 2001 in the area of functional decomposition of multivalued functions and relations, as well as some applications of these methods.

Estimating Scanning Characteristics From Corners In Bilevel Images, Elisa H. Barney Smith

Electrical and Computer Engineering Faculty Publications and Presentations

Degradations that occur during scanning can cause errors in Optical Character Recognition (OCR). Scans made in bilevel mode (no grey scale) from high contrast source patterns are the input to the estimation processes. Two scanner system parameters are estimated from bilevel scans using models of the scanning process and bilevel source patterns. The scanner's point spread function (PSF) width and the binarization threshold are estimated by using corner features in the scanned images.

These estimation algorithms were tested in simulation and with scanned test patterns. The resulting estimates are close in value to what is expected based on grey-level analysis. …

Scanner Parameter Estimation Using Bilevel Scans Of Star Charts, Elisa H. Barney Smith

Electrical and Computer Engineering Faculty Publications and Presentations

Scanning a high contrast image in bilevel mode results in image degradation. This is caused by two primary effects: blurring and thresholding. This paper expands on a method of estimating a joint distortion parameter, called the edge spread, from a star sector test chart in order to calculate the values of the point spread function width and binarization threshold. This theory is also described for variations in the source pattern which can represent degradations caused by repetition of the bilevel process as would be seen in printing then scanning, or in repeated photocopying. Estimation results are shown for the basic …

Rules For A Cellular Automaton To Model Quantum-Dot Cellular Automata, Teresa Cole, John C. Lusth

Electrical and Computer Engineering Faculty Publications and Presentations

Quantum-dot cellular automata are one of several new device architectures whose operation is based on local interactions, much like cellular automata. We have implemented several rule sets for a cellular automaton that could be used to model the behavior of quantum-dot cellular automata and used them to test most of the wire and gate configurations proposed for these devices. Arrangements of cells for which any particular cell has neighbors which are not adjacent to each other generally behave as expected. Unfavorable arrangements of cells such as those with bends and crosses tend to either have incorrect outputs or be unstable …

Processing Algorithms For Tracking Speckle Shifts In Optical Elastography Of Biological Tissues, Donald D. Duncan, Sean J. Kirkpatrick

Electrical and Computer Engineering Faculty Publications and Presentations

Parametric and nonparametric data processing schemes for analyzing translating laser speckle data used to investigate the mechanical behavior of biological tissues are examined. Crosscorrelation, minimum mean square estimator, maximum likelihood, and maximum entropy approaches are discussed and compared on speckle data derived from cortical bone samples undergoing dynamic loading. While it was not the purpose of this paper to demonstrate that one processing technique is superior to another, maximum likelihood and maximum entropy approaches are shown to be particularly useful when the observed speckle motion is small.

Regularity And Symmetry As A Base For Efficient Realization Of Reversible Logic Circuits, Marek Perkowski, Pawel Kerntopf, Andrzej Buller, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Xiaoyu Song, Anas Al-Rabadi, Lech Jozwiak, Alan Coppola

Electrical and Computer Engineering Faculty Publications and Presentations

We introduce a Reversible Programmable Gate Array (RPGA) based on regular structure to realize binary functions in reversible logic. This structure, called a 2 * 2 Net Structure, allows for more efficient realization of symmetric functions than the methods shown by previous authors. In addition, it realizes many non-symmetric functions even without variable repetition. Our synthesis method to RPGAs allows to realize arbitrary symmetric function in a completely regular structure of reversible gates with smaller “garbage” than the previously presented papers. Because every Boolean function is symmetrizable by repeating input variables, our method is applicable to arbitrary multi-input, multi-output Boolean …

Gaussian Beams In Hollow Metal Waveguides, Lee W. Casperson

Electrical and Computer Engineering Faculty Publications and Presentations

Various families of Gaussian beams have been explored previously to represent the propagation of nearly plane electromagnetic waves in media having at most quadratic transverse variations of the index of refraction and the gain or loss in the vicinity of the beam. However, such beams cannot directly represent the wave solutions for propagation in planar or rectangular waveguides, and sinusoidal mode functions are more commonly used for such waveguides. On the other hand, it is also useful to consider the possibility of recurring Gaussian beams that have an approximately Gaussian transverse profile at certain distinct planes along the propagation path. …

Power Self-Regulation In Double-Pass High-Gain Laser Amplifiers, Lee W. Casperson, Janet M. Casperson

Electrical and Computer Engineering Faculty Publications and Presentations

Double-pass laser amplifiers can provide automatic passive regulation of the power in an optical signal. This regulation can significantly reduce the amplitude noise on a laser beam that is intended as a continuous wave light source. Analytic expressions are derived to describe the optical-noise-reduction region of double-pass amplifier operation and the dependence of the self-regulation properties on gain, saturation, and mirror reflectivity.

Double-Pass High-Gain Laser Amplifiers, Janet M. Casperson, Frederick G. Moore, Lee W. Casperson

Electrical and Computer Engineering Faculty Publications and Presentations

Double-pass laser amplifiers have advantages of compactness and efficiency in the amplification of optical signals, and such amplifiers have been employed in a wide range of optical systems. Work in this area is reviewed briefly, and analytical solutions are obtained for the intensity of the electromagnetic waves in double-pass homogeneously-broadened high-gain laser amplifiers. Expressions are derived relating the output power to the input, including the effects of arbitrary mirror reflectivity and frequency detuning from line center. In the limits of weak saturation and of high reflectivity the results are consistent with earlier studies.

Constructive Induction Machines For Data Mining, Marek Perkowski, Stanislaw Grygiel, Qihong Chen, Dave Mattson

Electrical and Computer Engineering Faculty Publications and Presentations

"Learning Hardware" approach involves creating a computational network based on feedback from the environment (for instance, positive and negative examples from the trainer), and realizing this network in an array of Field Programmable Gate Arrays (FPGAs). Computational networks can be built based on incremental supervised learning (Neural Net training) or global construction (Decision Tree design). Here we advocate the approach to Learning Hardware based on Constructive Induction methods of Machine Learning (ML) using multivalued functions. This is contrasted with the Evolvable Hardware (EHW) approach in which learning/evolution is based on the genetic algorithm only.

Trace: A Visual Software System To Explore Properties Of Reed-Muller Movement Functions, Marek Perkowski, Alan Mishchenko

Electrical and Computer Engineering Faculty Publications and Presentations

We present new experimental Windows 95/98/NT software for investigation of graph properties of boolean (in particular, Reed-Muller) logic with an equal number n of inputs and outputs (called movement functions). Realized at the input of an n-bit register, such functions create autonomous Finite State Machines (FSMs). TRACE software system allows the user to visualize State Transition Graphs (STGs) of the autonomous FSMs. Other features of TRACE help explore graph properties of function families. These families are produced by a generic function, differing from it only in the order of components, one operation, or one literal (this literal is complemented or …

Constructive Induction Machines For Data Mining, Marek Perkowski, Stanislaw Grygiel, Qihong Chen, Dave Mattson

Electrical and Computer Engineering Faculty Publications and Presentations

"Learning Hardware" approach involves creating a computational network based on feedback from the environment (for instance, positive and negative examples from the trainer), and realizing this network in an array of Field Programmable Gate Arrays (FPGAs). Computational networks can be built based on incremental supervised learning (Neural Net training) or global construction (Decision Tree design). Here we advocate the approach to Learning Hardware based on Constructive Induction methods of Machine Learning (ML) using multivalued functions. This is contrasted with the Evolvable Hardware (EHW) approach in which learning/evolution is based on the genetic algorithm only. Various approaches to supervised inductive learning …

Logic Synthesis For A Regular Layout, Marek Perkowski, Yang Xu, Malgorzata Chrzanowska-Jeske

Electrical and Computer Engineering Faculty Publications and Presentations

New algorithms for generating a regular two-dimensional layout representation for multi-output, incompletely specified Boolean functions, called, Pseudo-Symmetric Binary Decision Diagrams (PSBDDs), are presented. The regular structure of the function representation allows accurate prediction of post-layout areas and delays before the layout is physically generated. It simplifies power estimation on the gate level and allows for more accurate power optimization. The theoretical background of the new diagrams, which are based on ideas from contact networks, and the form of decision diagrams for symmetric functions is discussed. PSBDDs are especially well suited for deep sub-micron technologies where the delay of interconnections limits …

Grazing Reflection Of Gaussian Beams, Lee W. Casperson

Electrical and Computer Engineering Faculty Publications and Presentations

The reflectivities of most surfaces are higher for grazing or near-90-deg angles of incidence than for more perpendicular or near-zero-deg angles. Grazing-incidence configurations are especially important in the development of lasers and optical systems that operate in the far-ultraviolet and soft-x-ray regions of the spectrum, where transparent or highly reflecting media are almost unknown. Analytical solutions of the paraxial wave equation are obtained for the grazing reflection and complex interference effects that take place when a Gaussian beam interacts at shallow angles with a reflecting surface.

Head Movement And Vision In Underwater-Feeding Birds Of Stream, Lake, And Seashore, Lee W. Casperson

Electrical and Computer Engineering Faculty Publications and Presentations

Studies head movement and vision in underwater-feeding birds. Review of relevant literature on the physiological and behavioral aspects of vision; Role of vertical head movement as an aid in the acquisition of visual information.

An Efficient And Effective Approach To Column-Based Input/Output Encoding In Functional Decomposition, Michael Burns, Marek Perkowski, Stanislaw Grygiel, Lech Jozwiak

Electrical and Computer Engineering Faculty Publications and Presentations

Encoding in Curtis-style decompositions is the process of assigning codes to groups of compatible columns (or cubes) so that the binary logic descriptions of the predecessor and successor sub-functions can be created for further decomposition. In doing so, the sub-functions created are functionally equivalent to the set of care values specified in the original function. In this paper an input/output encoding algorithm DC_ENC is presented that is designed to achieve the simplest total complexity of the predecessor and successor sub-functions, and to increase the total number of don't cares for their further utilization in subsequent decomposition steps of these sub-functions.

Production And Propagation Of Hermite–Sinusoidal-Gaussian Laser Beams, Lee W. Casperson, Anthony A. Tovar

Electrical and Computer Engineering Faculty Publications and Presentations

Hermite–sinusoidal-Gaussian solutions to the wave equation have recently been obtained. In the limit of large Hermite–Gaussian beam size, the sinusoidal factors are dominant and reduce to the conventional modes of a rectangular waveguide. In the opposite limit the beams reduce to the familiar Hermite–Gaussian form. The propagation of these beams is examined in detail, and resonators are designed that will produce them. As an example, a special resonator is designed to produce hyperbolic-sine-Gaussian beams. This ring resonator contains a hyperbolic-cosine-Gaussian apodized aperture. The beam mode has finite energy and is perturbation stable.

Photographic Studies Of Laser-Induced Bubble Formation In Absorbing Liquids And On Submerged Targets: Implications For Drug Delivery With Microsecond Laser Pulses, Hanqun Shangguan, Lee W. Casperson, Dennis L. Paisley, Scott A. Prahl

Electrical and Computer Engineering Faculty Publications and Presentations

Pulsed laser ablation of blood clots in a fluid-filled blood vessel is accompanied by an explosive evaporation process. The resulting vapor bubble rapidly expands and collapses to disrupt the thrombus (blood clot). The hydrodynamic pressures following the bubble expansion and collapse can also be used as a driving force to deliver clot-dissolving agents into thrombus for enhancement of laser thrombolysis. Thus, the laser-induced bubble formation plays an important role in the thrombus removal process. We investigate the effects of boundary configurations and materials on bubble formation with time-resolved flash photography and high-speed photography. Potential applications in drug delivery using microsecond …

Hermite–Sinusoidal-Gaussian Beams In Complex Optical Systems, Lee W. Casperson, Anthony A. Tovar

Electrical and Computer Engineering Faculty Publications and Presentations

Sinusoidal-Gaussian beams have recently been obtained as exact solutions of the paraxial wave equation for propagation in complex optical systems. Another useful set of beam solutions for Cartesian coordinate systems is based on Hermite–Gaussian functions. A generalization of these solution sets is developed here. The new solutions are referred to as Hermite–sinusoidal-Gaussian beams, because they are in the form of a product of Hermite-polynomial functions of either complex or real argument, sinusoidal functions of complex argument, and Gaussian functions of complex argument. These beams are valid for propagation through systems that can be represented in terms of complex beam matrices, …

Tooth Contact Sensing Apparatus And Method, John D. Summer, Edmund Pierzchala, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

An apparatus and method for sensing tooth contact includes at least one, and more typically plural, vibration sensors which are coupled to the non-biting surfaces of teeth. These sensors produce output signals when the associated teeth contact one another during jaw closing, the output signals being processed to provide information concerning tooth contact. For example, information concerning the ?rst tooth which contacts may be determined, the sequence of contact by various teeth may be determined, as well as the time between contact of the various teeth. Other information concerning tooth contact may also be determined and dis played in a …