Computer algorithms

We study the embedding of binomial trees with variable roots in faulty hypercubes. Based on novel embedding strategies, we propose three embedding algorithms with variable nodes as the root. The first algorithm can tolerate up to n - 1 faulty links, but the execution can be done within log2(n - 1) subcube splits. The second one can tolerate up to [(3(n - 1))\2] faulty links. The last one can tolerate up to [(3(n - 4))\2] faulty nodes.

Based on multi-agent supporting system (MASS) structures used to investigate the synchronous algorithms in my previous work, the partially and totally asynchronous distributed algorithms are proposed in this thesis. The stability of discrete MASS with asynchronous distributed algorithms is analyzed. The partially asynchronous algorithms proposed for both 1- and 2-dimensional MASS are proven to be convergent, if the vertical disturbances vary sufficiently slower than the convergent time of the system. The adjacent error becomes zero when the system converges. It is also proven that in 1-dimensional MASS using the proposed totally asynchronous algorithm, the maximum of the absolute value of the adjacent error is non-increasing over time. Finally, the simulation results for all the above cases are presented to demonstrate the theoretical findings.

Indexed Resource Auction Multiple Access (I-RAMA), a new medium access protocol for wireless cellular networks based on Resource Auction Multiple Access (RAMA) is presented. I-RAMA relies in variable length resource auctions, whose length depends on the time it takes the Base Station to uniquely identify the Mobile Station. This identification is done by using dynamic Base Station information about the users present in the cell at any moment. I-RAMA effectively reduces the amount of time spent in the resource auctions without introducing contention or excessive complexity at the Base Station. The effects of introducing data users in the system are investigated using a simulation, and it is shown that I-RAMA guarantees Quality of Service for isochronous users while maintaining a bounded delay for data users at much higher loads than RAMA.

This thesis presents simulation results comparing the performance of different realizations and adaptive algorithms for channel equalization. An attempt is made to study and compare the performance of some filter structures used as an equalizer in fast data transmission over the baseband channel. To this end, simulation experiments are performed using minimum and non minimum phase channel models with adaptation algorithms such as the least mean square (LMS) and recursive least square (RLS) algorithms, filter structures such as the lattice and transversal filters and the input signals such as the binary phase shift keyed (BPSK) and quadrature phase shift keyed (QPSK) signals. Based on the simulation studies, conclusions are drawn regarding the performance of various adaptation algorithms.

This thesis presents simulation results evaluating the performance of blind equalization techniques in the Digital Cellular environment. A new method of a simple zero memory non-linear detector for complex signals is presented for various forms of Fractionally Spaced Equalizers (FSE). Initial simulations are conducted with Binary Phase Shift Keying (BPSK) to study the characteristics of FSEs. The simulations are then extended to complex case via $\pi/$4-Differential Quaterny Phase Shift Keying ($\pi/$4-DQPSK) modulation. The primary focus in this thesis is the performance of this complex case when operating in Additive White Gaussian Noise (AWGN) and Rayleigh Multipath Fading channels.

A barrier to the use of digital imaging is the vast storage requirements involved. One solution is compression. Since imagery is ultimately subject to human visual perception, it is worthwhile to design and implement an algorithm which performs compression as a function of perception. The underlying premise of the thesis is that if the algorithm closely matches visual perception thresholds, then its coded images contain only the components necessary to recreate the perception of the visual stimulus. Psychophysical test results are used to map the thresholds of visual perception, and develop an algorithm that codes only the image content exceeding those thresholds. The image coding algorithm is simulated in software to demonstrate compression of a single frame image. The simulation results are provided. The algorithm is also adapted to real-time video compression for implementation in hardware.

Compared to the traditional wireless network, the multi-hop ad hoc wireless network (simply called ad hoc networks) is self-configurable, dynamic, and distributed. During the past few years, many routing protocols have been proposed for this particular network environment. While in wired and optical networks, multi-protocol label switching (MPLS) has clearly shown its advantages in routing and switching such as flexibility, high efficiency, scalability, and low cost, however MPLS is complex and does not consider the mobility issue for wireless networks, especially for ad hoc networks. This thesis migrates the label concept into the ad hoc network and provides a framework for the efficient Label Routing Protocol (LRP) in such a network. The MAC layer is also optimized with LRP for shorter delay, power saving, and higher efficiency. The simulation results show that the delay is improved significantly with this cross-layer routing protocol.

This research aims at proposing a model for visual pattern recognition inspired by the neural circuitry in the brain. Our attempt is to propose few modifications in the Alopex algorithm and try to use it for the calculations of the receptive fields of neurons in the trained network. We have developed a small-scale, four-layered neural network model for simple character recognition as well as complex image patterns, which can recognize the patterns transformed by affine conversion. Here Alopex algorithm is presented as an iterative and stochastic processing method, which was proposed for optimization of a given cost function over hundreds or thousands of iterations. In this case the receptive fields of the neurons in the output layers are obtained using the Alopex algorithm.

K-means algorithm and Kohonen network possess self-organizing characteristics and are widely used in different fields currently. The factors that influence the behavior of K-means are the choice of initial cluster centers, number of cluster centers and the geometric properties of the input data. Kohonen networks have the ability of self-organization without any prior input about the number of clusters to be formed. This thesis looks into the performances of these algorithms and provides a unique way of combining them for better clustering. A series of benchmark problem sets are developed and run to obtain the performance analysis of the K-means algorithm and Kohonen networks. We have attempted to obtain the better of these two self-organizing algorithms by providing the same problem sets and extract the best results based on the users needs. A toolbox, which is user-friendly and written in C++ and VC++ is developed for applications on both images and feature data sets. The tool contains K-means algorithm and Kohonen networks code for clustering and pattern classification.

This thesis refers to a research addressing the use of binary representation of the DNA for the purpose of developing useful algorithms for Bioinformatics. Pertinent studies address the use of a binary form of the DNA base chemicals in information-theoretic base so as to identify symmetry between DNA and complementary DNA. This study also refers to "fuzzy" (codon-noncodon) considerations in delinating codon and noncodon regimes in a DNA sequences. The research envisaged further includes a comparative analysis of the test results on the aforesaid efforts using different statistical metrics such as Hamming distance Kullback-Leibler measure etc. the observed details supports the symmetry aspect between DNA and CDNA strands. It also demonstrates capability of identifying non-codon regions in DNA even under diffused (overlapped) fuzzy states.