Digital Commons Network^™

Design And Implementation Of Two Text Recognition Algorithms, Madhumathi Yendamuri

Theses

This report presents two algorithms for text recognition. One is a neural-based orthogonal vector with pseudo-inverse approach for pattern recognition. A method to generate N orthogonal vectors for an N-neuron network is also presented. This approach converges the input to the corresponding orthogonal vector representing the prototype vector. This approach can restore an image to the original image and thus has error recovery capacility. Also, the concept of sub-networking is applied to this approach to enhance the memory capacity of the neural network. This concept drastically increases the memory capacity of the network and also causes a reduction of the …

Numerical Solution Of Laplace's Equation, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial discusses Laplace's equation for steady state heat flow in a two-dimensional region with fixed temperatures on the boundaries. The equilibrium temperatures are computed for a square grid using successive overrelaxation with parity ordering of the grid elements. The numerical method is illustrated by a Pascal algorithm. We assume that the reader is familiar with elementary calculus.

Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.

Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.

Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley

Computer Science: Faculty Publications and Other Works

We present a linear-time algorithm for determining the minimum height of a single-layer routing channel. The algorithm handles single-sided connections and multiterminal nets. It yields a simple routability test for single-layer switchboxes, correcting an error in the literature.

Practical Constraints Pertinent To The Design Of Neural Networks, Said Sadek Abdallah, Rufus H. Cofer

Electrical Engineering and Computer Science Faculty Publications

in designing a feedforward neural network for numerical computation using the backpropagation algorithm it is essential to know that the resulting network has a practical global minimum, meaning that convergence to a stationary solution can be achieved in reasonable time and using a network of reasonable size. This is in contrast to theoretical results indicating that any square-integrable (L2) function can be computed assuming that an unlimited number of neurons are available. A class of problems is discussed that does not fit into this category. Although these problems are conceptually simple, it is shown that in practice convergence to a …

Formal Generation Of Executable Assertions For Application-Oriented Fault Tolerance, Hanan Lutfiyya, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

Executable assertions embedded into a distributed computing system can provide run-time assurance by ensuring that the program state, in the actual run-time environment, is consistent with the logical stage specified in the assertions; if not, then an error has occurred and a reliable communication of this diagnostic information is provided to the system such that reconfiguration and recovery can take place. Application- oriented fault tolerance is a method that provides fault detection using executable assertions based on the natural constraints of the application.

This paper focuses on giving application-oriented fault tolerance a theoretical foundation by providing a mathematical model for …

Simulated Annealing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes simulated annealing, an optimization method based on the principles of statistical mechanics. Simulated annealing finds near-optimal solutions to optimization problems that cannot be solved exactly because they are NP-complete. The method is illustrated by a Pascal algorithm for the traveling salesperson problem. The performance of the algorithm was measured on a Computing Surface.

Primality Testing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes the Miller-Rabin method for testing the primality of large integers. The method is illustrated by a Pascal algorithm. The performance of the algorithm was measured on a Computing Surface.

Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann

Electrical Engineering and Computer Science - Technical Reports

In this report we present a class of efficient maximum-likelihood soft-decision decoding algorithms for linear block codes. The approach used here is to convert the decoding problem into a search problem through a graph which is a trellis for an equivalent code of the transmitted code. Algorithm A*, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to drastically reduce the search …

Comparing Techniques Of Mapping Pyramid Algorithms Onto The Hypercube : A Case Study For The Connection Machine, Muhammad Ali Siddiqui

Theses

The pyramid structure is most widely used for low-level and intermediate-level image processing and computer vision because of its efficient support of both local and global operations. However, the cost of pyramid computers (PC) may be very high. They also do not support the efficient implementation of the majority of the scientific algorithms. In contrast, the hypercube network has widely been used in the field of parallel processing because it offers a high degree of fault tolerance, a small diameter and rich interconnection structure that permits fast communication at a reasonable cost. Thus, several algorithms have been developed for the …

New Algorithms For Mid-Crack Codes In Image Processing, Wai-Tak Wong

Theses

The chain code is a widely-used description for a contour image. Recently, a mid-crack code algorithm has been proposed as another more precise method for image representation. New algorithms using this new mid-crack code for image representation, restoration, and skeletonization are developed. The efficiency and accuracy can be increased obviously.

Firstly, the conversion of a binary image with multiple regions into the mid-crack codes is presented. A fast on-line implementation can be achieved using tables look-up. The input binary image may contain several object regions and their mid-crack codes can be extracted at the same time in a single-pass row-by-row …

Clustering Algorithm For Local Area Network Design In A Cim Environment, A. C. Manjunath

Theses

Communication systems have come to be regarded as being one of the most important aspects in manufacturing enterprises in recent years. It continues to offer enormous potential for improving the efficiency of manufacturing enterprises through Computer Integrated Manufacturing (CIM). It is true however that this potential cannot be realized by developments on the communications front alone. Strategic and economic considerations in installing a communications system in a manufacturing environment is of vital significance.

This thesis, at the outset attempts to bring out some of the issues in the area of communications (research), specifically in relation to CIM. A perception of …

A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang

Electrical Engineering and Computer Science - Technical Reports

This paper presents a simple load balancing algorithm and its probabilistic analysis. Unlike most of the previous load balancing algorithms, this algorithm maintains locality. We show that the cost of this load balancing algorithm is small for practical situations and discuss some interesting applications for data remapping.

Some Aspects Of Multi Source Satellite Image Processing., L. Lalitha Dr.

Doctoral Theses

The observation of a target by a device plaoed at some distance from it is cal.led remote sensing as ngainst in situ sensing where the sensor is kept in contact with the target. Usually physical emanations such as the electr omagnetic radiation from the target s observed by the sensing device. Sensors mounted on aircraft or satallite platforms measure the amount of energy reflected from or emitted by the earth's surface. Sensors scan the ground below a nd to either side of the satellite platform and as the platform noves forward, an image of the earths surface is formed.A satellite …

Scheduling Regular And Irregular Communication Patterns On The Cm-5, Ravi Ponnusamy, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox

Northeast Parallel Architecture Center

In this paper, we study the communication characteristics of the CM-5 and the performance effects of scheduling regular and irregular communication patterns on the CM-5. We consider the scheduling of regular communication patterns such as complete exchange and broadcast. We have implemented four algorithms for complete exchange and studied their performances on a 2D FFT algorithm. We have also implemented four algorithms for scheduling irregular communication patterns and studied their performance on the communication patterns of several synthetic as well as real problems such as the conjugate gradient solver and the Euler solver.

Performance Analysis Of Doa Estimation Algorithms Using Physical Parameters, Hui Liu

Dissertations and Theses

Analytical performance analysis on Direction-Of-Arrival (DOA) estimation algorithms has attracted much excellent research in recent years, various statistical properties have been revealed. However, in most of these analyses, insights of the performance were masked because of the involvement of singular values and singular vectors which depend on the character of the algorithms and data structures in a complex and nonlinear manner.

Hybrid Clamping In Ntsc Digital Video Equipment, Norman R. Cox, Douglas William Irwin

Electrical and Computer Engineering Faculty Research & Creative Works

Two algorithms that are suitable for deriving the blanking level of a National Television Systems Committee (NTSC) composite video signal are described. One method consists of averaging digitized color-burst samples taken from successive scan lines. A second method involves processing a group of samples taken from a single burst interval. Either algorithm used in a hybrid clamping arrangement results in automatic drift compensation and the ability to tie the back porch or sync tip to a predetermined digital output code. This aids in matching the analog signal to the input of the analog-to-signal (A/D) converter for maximum signal-to-noise ratio (SNR). …