Computer Engineering Commons^™

Kolmogorov Complexity Justifies Software Engineering Heuristics, Ann Q. Gates, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

The "clean bill of health" produced by such a technique does not guarantee that the program is actually correct. In this paper, we show that several heuristic techniques for software testing that have been developed in software engineering can be rigorously justified. In this justification, we use Kolmogorov complexity to formalize the terms "simple" and "random" that these techniques use. The successful formalization of simple heuristics is a good indication that Kolmogorov complexity may be useful in formalizing more complicated heuristics as well.

Quality Of Service Semantics For Multimedia Database Systems, Jonathan Walpole, Charles Krasic, Ling Liu, David Maier, Calton Pu, Dylan Mcnamee, David Steere

Computer Science Faculty Publications and Presentations

Quality of service (QoS) support has been a hot research topic in multimedia databases, and multimedia systems in general, for the past several years. However, there remains little consensus on how QoS support should be provided. At the resource-management level, systems designers are still debating the suitability of reservation- based versus adaptive QoS management. The design of higher system layers is less clearly understood, and the specification of QoS requirements in domain-specific terms is still an open research topic. To address these issues, we propose a QoS model for multimedia databases. The model covers the specification of user-level QoS preferences …

Experimental Investigations Of Wavelength And Angular Errors In Holographic Gratings With Non-Bragg-Matched Read Beams, Monish Ranjan Chatterjee, Vivek Ray

Electrical and Computer Engineering Faculty Publications

Perfect Bragg matching is generally desirable for accurate optical interconnections with holographic gratings. In reality, however, gratings may be illuminated by READ beams with non-Bragg-matched angles, or wavelengths, or both. In such cases, the scattered beams are generally misdirected, and may suffer loss of efficiency and possibly more serious errors such as crosstalk noise or missed connections. A conventional wave-vector triad method of analyzing the scattered beam errors leads readily to near-Bragg estimates of the output angular misalignment. However, the READ wave-vector triads appear to indicate a possible wavelength shift in the output beam even with a Bragg-matched READ wavelength, …

Multiple Streams Synchronization In Collaborative Multimedia Systems, Emilia Stoica

Computer Science Theses & Dissertations

With the recent increase of the communication bandwidth and processor power, new types of applications have emerged. Among them, there are multimedia application, in which users are able to control, combine, and manipulate different types of media, such as text, sound, video, computer graphics, and animation. A key requirement in any multimedia application is to synchronize the delivery of various media streams to the user. To achieve this, the sender has to provide the temporal relations between the streams as they are captured. Since the receiver uses this information in streams presentation, its accuracy is very important.

Our main contribution …

The Cluster Multipole Algorithm For Far-Field Computations, Rakesh R. Patel

Electrical & Computer Engineering Theses & Dissertations

Computer simulations of N-body systems are beneficial to study the overall behavior of a number of physical systems in fields such as astrophysics, molecular dynamics, and computational fluid dynamics. A new approach for computer simulations of N-body systems is proposed in this research. The new algorithm is called the Cluster Multipole Algorithm (CMA). The goals of the new algorithm are to improve the applicability to non-point sources and to provide more control on the accuracy over current algorithms. The algorithm is targeted to applications that do not require rebuilding the data structure about the system every time step due to …

System And Method For Performing Optical Code Division Multiple Access Communication Using Bipolar Codes, James F. Young, Benhaam Aazhnag, Lim Nguyen

Department of Electrical and Computer Engineering: Faculty Publications

An optical encoding and decoding system which performs code-division multiple access (CDMA) communication in the incoherent, or direct detection, optical domain using bipolar +1/-1 codes. The present invention uses code modu lation and detection principles that permit all-optical imple mentation of the bipolar. +1/-1. code and correlation detec tion that have been developed for the radio frequency (RF) systems. This is possible in spite of the non-negative, or unipolar, +1/0, nature of the incoherent optical system that only detects and processes the signal intensity. The unipolar optical system of the present invention is equivalent to the bipolar RF system in …

Multi-Spectral Inverse Problems In Satellite Image Processing, Scott A. Starks, Vladik Kreinovich

Departmental Technical Reports (CS)

Satellite imaging is nowadays one of the main sources of geophysical and environmental information. It is, therefore, extremely important to be able to solve the corresponding inverse problem: reconstruct the actual geophysics- or environment-related image from the observed noisy data.

Traditional image reconstruction techniques have been developed for the case when we have a single observed image. This case corresponds to a single satellite photo. Existing satellites (e.g., Landsat) take photos in several (up to 7) wavelengths. To process this multiple-spectral information, we can use known reasonable multi-image modifications of the existing single-image reconstructing techniques. These modifications, basically, handle each …

Fair Division Under Interval Uncertainty, Ronald R. Yager, Vladik Kreinovich

Departmental Technical Reports (CS)

It is often necessary to divide a certain amount of money between n participants, i.e., to assign, to each participant, a certain portion w(i)>=0 of the whole sum (so that w(1)+...+w(n)=1). In some situations, from the fairness requirements, we can uniquely determine these "weights" w(i). However, in some other situations, general considerations do not allow us to uniquely determine these weights, we only know the intervals [w-(i),w+(i)] of possible fair weights. We show that natural fairness requirements enable us to choose unique weights from these intervals; as a result, we present an algorithm for fair division under interval uncertainty.

Kolmogorov Complexity, Statistical Regularization Of Inverse Problems, And Birkhoff's Formalization Of Beauty, Vladik Kreinovich, Luc Longpre, Misha Kosheleva

Departmental Technical Reports (CS)

Most practical applications of statistical methods are based on the implicit assumption that if an event has a very small probability, then it cannot occur. For example, the probability that a kettle placed on a cold stove would start boiling by itself is not 0, it is positive, but it is so small, that physicists conclude that such an event is simply impossible.

This assumption is difficult to formalize in traditional probability theory, because this theory only describes measures on sets (e.g., for an inverse problem, on the set of all functions) and does not allow us to divide functions …

Case Study Of Non-Linear Inverse Problems: Mammography And Non-Destructive Evaluation, Olga Kosheleva, S. Cabrera, Roberto A. Osegueda, Carlos M. Ferregut, Soheil Nazarian, M. J. George, Vladik Kreinovich, K. Worden

Departmental Technical Reports (CS)

The inverse problem is usually difficult because the signal (image) that we want to reconstruct is weak. Since it is weak, we can usually neglect quadratic and higher order terms, and consider the problem to be linear. Since the problem is linear, methods of solving this problem are also, mainly, linear (with the notable exception of the necessity to take into consideration, e.g., that the actual image is non-negative).

In most real-life problems, this linear description works pretty well. However, at some point, when we start looking for a better accuracy, we must take into consideration non-linear terms. This may …

Location Independent Names For Nomadic Computers, David Steere, Mark Morrissey, Peter Geib, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Recent advances in the Domain Name System (DNS) and the Dynamic Host Configuration Protocol (DHCP) have enabled a new approach to supporting mobile users: location independent naming. In this approach, machines use the same hostname from any internet location, but use an IP address that corresponds to their current location. We describe a protocol that implements location independent naming for nomadic computers, i.e., machines that do not need transparent mobility. Our protocol allows hosts to move across security domains, uses existing protocols, and preserves existing trust relationships. Therefore, it preserves the performance and security of normal IP for nomadic computers …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 14, Number 6, June 1998, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A ten page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 14, Number 5, May 1998, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A ten page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Adaptation Space: Surviving Non-Maskable Failures, Crispin Cowan, Lois Delcambre, Anne-Francoise Le Meur, Ling Liu, David Maier, Dylan Mcnamee, Michael Miller, Calton Pu, Perry Wagle, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Some failures cannot be masked by redundancies, because an unanticipated situation occurred, because fault-tolerance measures were not adequate, or because there was a security breach (which is not amenable to replication). Applications that wish to continue to offer some service despite nonmaskable failure must adapt to the loss of resources. When numerous combinations of non-maskable failure modes are considered, the set of possible adaptations becomes complex. This paper presents adaptation spaces, a formalism for navigating among combinations of adaptations. An adaptation space describes a collection of possible adaptations of a software component or system, and provides a uniform way of …

Implementation Of A Database System With Boolean Algebra Constraints, András Salamon

School of Computing: Dissertations, Theses, and Student Research

This thesis describes an implementation of a constraint database system with constraints over a Boolean Algebra of sets. The system allows within the input database as well as the queries equality, subset-equality and monotone inequality constraints between Boolean Algebra terms built up using the operators of union, intersection and complement. Hence the new system extends the earlier DISCO system, which only allowed equality and subset-equality constraints between Boolean algebra variables and constants. The new system allows Datalog with Boolean Algebra constraints as the query lan- guage. The implementation includes an extension of Naive and Semi-Naive evaluation methods for Datalog programs …

Rapid Prototyping Using Reprogrammable Logic, Jared L. Bell

Honors Capstone Projects and Theses

No abstract provided.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 14, Number 4, April 1998, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

An eight page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

A Variation On The Zero-One Law, Andreas Blass, Yuri Gurevich, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

Given a decision problem P and a probability distribution over binary strings, for each n, draw independently an instance xn of P of length n. What is the probability that there is a polynomial time algorithm that solves all instances xn of P? The answer is: zero or one.

Spectral/Temporal Segment Features For Automatic Speech Recognition, Xi Hong Wang

Electrical & Computer Engineering Theses & Dissertations

In this thesis an approach for efficiently computing a compact spectral/temporal feature set for representing a segment of speech, with effective resolution depending on both frequency and time position within the segment, is developed, analyzed, and tested. The goal of this method is to mimic the resolution properties of the human auditory system, but using a computationally efficient FFT-based front end rather than a more complex auditory model. In particular this method applies both frequency and time "warping" to FFT spectra to obtain good frequency resolution at low frequencies and good time resolution at high frequencies. Time resolution is also …

Adding Fuzzy Integral To Fuzzy Control, Hung T. Nguyen, Vladik Kreinovich, Richard Alo

Departmental Technical Reports (CS)

Sugeno integral was invented a few decades ago as a natural fuzzy-number analogue of the classical integral. Sugeno integral has many interesting applications. It is reasonable to expect that it can be used in all application areas where classical integrals are used, and in many such areas it is indeed useful. Surprisingly, however, it has never been used in fuzzy control, although in traditional control, classical integral is one of the main tools.

In this paper, we show that the appropriately modified Sugeno integral is indeed useful for fuzzy control: namely, it provides numerical characterization of stability and smoothness …

How To Divide A Territory? A New Simple Differential Formalism For Optimization Of Set Functions, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical problems, we must optimize a set function, i.e., find a set A for which f(A) is maximum, where f is a function defined on the class of sets. Such problems appear in design, in image processing, in game theory, etc.

Most optimization problems can be solved (or at least simplified) by using the fact that small deviations from an optimal solution can only decrease the value of the objective function; as a result, some derivative must be equal to 0. This approach has been successfully used, e.g., for set functions in which the desired set A …

Computational Complexity And Feasibility Of Fuzzy Data Processing: Why Fuzzy Numbers, Which Fuzzy Numbers, Which Operations With Fuzzy Numbers, Hung T. Nguyen, Misha Kosheleva, Olga Kosheleva, Vladik Kreinovich, Radko Mesiar

Departmental Technical Reports (CS)

In many real-life situations, we cannot directly measure or estimate the desired quantity r. In these situations, we measure or estimate other quantities r1,...,rn related to r, and then reconstruct r from the estimates for r_i. This reconstruction is called data processing.

Often, we only have fuzzy information about ri. In such cases, we have fuzzy data processing. Fuzzy data means that instead of a single number ri, we have several numbers that describes the fuzzy knowledge about the corresponding quantity. Since we need to process more numbers, the computation time for fuzzy …

Operations With Fuzzy Numbers Explain Heuristic Methods In Image Processing, Olga Kosheleva, Vladik Kreinovich, Bernadette Bouchon-Meuiner, Radko Mesiar

Departmental Technical Reports (CS)

Maximum entropy method and its heuristic generalizations are very useful in image processing. In this paper, we show that the use of fuzzy numbers enables us to naturally explain these heuristic methods.

Decision Making Based On Satellite Images: Optimal Fuzzy Clustering Approach, Vladik Kreinovich, Hung T. Nguyen, Scott A. Starks, Yeung Yam

Departmental Technical Reports (CS)

In many real-life decision-making situations, in particular, in processing satellite images, we have an enormous amount of information to process. To speed up the information processing, it is reasonable to first classify the situations into a few meaningful classes (clusters), find the best decision for each class, and then, for each new situation, to apply the decision which is the best for the corresponding class. One of the most efficiently clustering methodologies is fuzzy clustering, which is based on the use of fuzzy logic. Usually, heuristic clusterings are used, i.e., methods which are selected based on their empirical efficiency …

Towards The Use Of Aesthetics In Decision Making: Kolmogorov Complexity Formalizes Birkhoff's Idea, Misha Kosheleva, Vladik Kreinovich, Yeung Yam

Departmental Technical Reports (CS)

Decision making is traditionally based on utilitarian criteria such as cost, efficiency, time, etc. These criteria are reasonably easy to formalize; hence, for such criteria, we can select the best decision by solving the corresponding well-defined optimization problem. In many engineering projects, however, e.g., in designing cars, building, airplanes, etc., an important additional criterion which needs to be satisfied is that the designed object should be good looking. This additional criterion is difficult to formalize and, because of that, it is rarely taken into consideration in formal decision making. In the 1930s, the famous mathematician G. D. Birkhoff has proposed …

Joint Wavelet Transform Correlation With Separated Target And Reference Planes, Boon Yi Soon, Mohammad A. Karim, Russell C. Hardie, Mohammad S. Alam

Electrical and Computer Engineering Faculty Publications

In recent years, we realize the usefulness of feature extraction for optical correlator and hereby, we investigate the capability of Laplace operator in feature extraction of multiple targets. The first-order terms and the false alarm terms in the correlation output would be removed using electronic power spectrum subtraction technique. Most importantly, the entire magneto-optic SLM is completely utilized for displaying only targets in the input scene. A new cost efficient hardware implementation is proposed and aforementioned result of the proposed system is evaluated through computer simulation.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 14, Number 3, March 1998, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

An eight page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Design, Performance, And Applications Of A Coherent Ultra-Wideband Random Noise Radar, Ram M. Narayanan, Yi Xu, Paul D. Hoffmeyer, John O. Curtis

Department of Electrical and Computer Engineering: Faculty Publications

A novel coherent ultra-wideband radar system operating in the 1- to 2-GHz frequency range has been developed recently at the University of Nebraska. The radar system transmits white Gaussian noise. Detection and localization of buried objects is accomplished by correlating the reflected waveform with a time-delayed replica of the transmitted waveform. Broadband dual-polarized log-periodic antennas are used for transmission and reception. A unique signal-processing scheme is used to inject coherence into the system by frequency translation of the ultrawideband signal by a coherent 160-MHz phase-locked source prior to performing heterodyne correlation. The system coherence allows the extraction of a target’s …

Encryption Algorithms Made (Somewhat) More Natural (A Pedagogical Remark), Misha Kosheleva, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

Modern cryptographic algorithms, such as DES, IDEA, etc., are very complex and therefore difficult to learn. Textbooks explain in detail how these algorithms work, but they usually do not explain why these algorithms were designed as they were. In this paper, we explain why, and thus, hopefully, make cryptographic algorithms easier to learn.

An Operationalistic Reformulation Of Einstein's Equivalence Principle, Vladik Kreinovich, R. R. Zapatrine

Departmental Technical Reports (CS)

No abstract provided.