Ray tracing has proven itself to be a highly effective method for producing photo-realistic images of three-dimensional scenes. The basic problem with ray tracing is the enormous amount of computation required for tracking a large number of rays through the scene. Traditionally, each tracked ray has to be checked for intersection with every object in the scene in order to render the image. Many researchers report that more than 95% of the image creation computation time is consumed by object-ray calculation. Various accelerating techniques have been proposed in recent years to reduce the number of ray-object intersection checks, such as bounding volume hierarchies, spatial subdivision, and directional cube methods. Among them, the spatial subdivision technique is the most widely discussed method. While most researchers have concentrated on directly extracting information from the three-dimensional space to accelerate the ray tracing process, information about relationships between objects that also exists on various two-dimensional projection planes has been overlooked. This dissertation presents a technique to track the rays in three-dimensional space by a two-dimensional approach--using multiple projection planes. Although extra projection planes are widely used for building and displaying models and scenes, no previous work has been done to use extra projection planes for accelerating ray tracing. The approach used in this work is as follows. In addition to the projection plane which is used to observe the scene and generate the picture, k additional projection planes are judiciously positioned in the scene. The objects in the scene are projected onto each projection plane and their projected bounding rectangles are collected and properly manipulated. During the ray tracking process, the path of the ray inside the scene is monitored by each of the additional projection planes with the aid of the projected bounding rectangles of the objects. This additional information is consulted to build list of candidate objects which could be intersected by the ray. In order to maintain the accuracy of the information from each additional projection plane, a method is used to coordinate the movement of the ray across these additional projection planes. Several variations of this method were implemented and are discussed in this dissertation along with a series of experiments. Statistics on the execution time and the total number of ray-object intersection tests are reported.

We address the problems of testing circuits for temporal correctness and synthesizing circuits that can be verified for timing correctness. A circuit is said to be delay-verifiable if its correct timing at the operating speed and also at any slower speed can be guaranteed by applying delay tests. It is shown that some circuits are not delay-verifiable. Furthermore, verifying the timing of a circuit may require tests that can detect the simultaneous presence of more than one path delay fault. This dissertation proposes a general framework for examining delay-verifiability of arbitrary combinational circuits by introducing a special class of faults, called primitive path delay faults. We show that it is necessary and sufficient to test every fault in this class to ensure the temporal correctness of a combinational circuit. A procedure to identify primitive faults is presented. Based on this result, we develop necessary and sufficient conditions for delay-verifiability and provide synthesis procedures for delay-verifiable circuits. The requirement for delay-verifiability is less stringent than existing requirements for delay testability. This provides us with a higher degree of freedom in synthesizing circuits. Experimental data show that circuits obtained by our procedure usually require less area than completely delay testable implementations. Several types of circuits are investigated for their delay-verifiability. It will be shown that many delay untestable circuits are delay-verifiable. The concept of delay-verifiability is a complete solution in the sense that it guarantees full verification for temporal correctness. While delay-testable circuits are always irredundant, delay-verifiable circuits allow the existence of redundancies, which are necessary in some applications. This opens up a new domain of circuits that can be verified for timing correctness.

The growth of higher bandwidth networks and powerful new workstations has enabled the development of many new multimedia applications. These applications involve the combined use of different media such as voice, video and text. Supporting these applications requires the resolution of a number of issues both within the network and at the end-hosts that originate the applications. In this dissertation we consider real-time scheduling and protocol problems that arise in this arena. In the realm of applications operating under hard time-constraints, we address both network-node and workstation scheduling. In applications involving the use of video or a combination of voice and video, there can be the need to schedule classes of traffic with differing importance but identical deadlines at a network-node. We examine scheduling algorithms that can be used in the situation of two classes of traffic. We demonstrate using probabilistic arguments that a new "balancing" discipline can provide better loss performance for both classes than more traditional schemes in some operating regions. When delay loss probabilities are low, strict priority scheduling is shown to be a reasonable option. Turning our attention to the end-hosts, we consider the need to process multimedia objects such as voice packets in a periodic fashion within a workstation, and study two common scheduling algorithms--earliest deadline first (ED) and rate monotonic (RM). Recent studies have revealed the importance of the preemption behavior of the scheduler in determining overall processor performance. We prove that there are always fewer preemptions under ED than under RM and show through simulations of well-known task-sets that, on occasion, there can be over 20% more preemptions under RM than under ED. Apart from these scheduling problems, we also look at protocol issues that combine network and host considerations. For applications such as world-wide multimedia lectures, it becomes important to have error-recovery protocols that will scale well to hundreds of receivers. We perform throughput analyses and demonstrate why receiver-initiated protocols based on negative acknowledgements are to be preferred over sender-initiated protocols based on positive acknowledgments. We focus on host processing costs to illustrate this result.

For generations, communication networks are built by using electronic devices and components. The transmission speed (or bandwidth) is limited up to about 1 Gb/s mainly due to the capacity of the transmission lines (e.g. copper wires and coaxial cables). The introduction of fiber optics brings us to a new age. The speed of a single optical fiber line is approximately 30 terabit per second which creates a virtually unlimited transmission media for communications. Therefore, the full utilization of such high speed transmission becomes a new and exciting challenge. Many problems and challenges exist in current optical networks. They come mainly from the bottleneck effect in electronic components. This dissertation addresses two related issues. First, the problem of flow control is presented and solved in a high speed internetworking environment. Then a new optical switch is introduced along with an efficient channel access control.

Far ranging developments in VLSI and fiber optic technology have begun to form the basis for integrated networks that provide many new multimedia and real-time services. These services involve the combined use of different media such as voice, video, image and data. Supporting these applications requires the resolution of a number of issues within the network to provide the quality of service (QOS) guarantees. In this dissertation, we address four specific problems related to the design, and performance of high-speed packet switches and integrated services. At the heart of a high-speed network are the switching fabrics. The architecture and queueing strategy of the switch fabric contributes significantly to the QOS of applications. In the area of switch fabric design, we focus on a buffering strategy that is simple to implement, yet provides performance comparable to complex buffering mechanisms. We study the performance of different buffering strategies using analytical models and simulations. Turning our attention to the multimedia applications, specifically video traffic which is expected to contribute to a majority of the traffic on these integrated networks, we study quality of service issues. We examine the effects of packet loss on the quality of compressed video. We show that trade-offs are involved in total bit rate and susceptibility to packet loss. We propose different techniques to reduce packet loss and to mitigate the effect of packet loss on picture quality. In applications involving the use of video or other real-time applications there is a need to schedule different classes of traffic to provide priority to time-constrained applications. We propose four new scheduling policies that approximate the behavior of the optimal minimum laxity scheduling policy. The computational complexity of all four policies is independent of the number of packets in queue. Further, our results indicate that the performance of the best of the four policies is within 5% of the optimal scheduling policy. Simulation of high-speed packet switches is computationally intensive. We demonstrate that parallel time-driven simulations can be effectively used for high-speed packet switch simulations which are inherently discrete time based. We develop, new processor synchronization and processor assignment techniques that exploit the topology of packet switches and parallelize the time-driven simulations to achieve near linear speedups.

In this thesis we have looked at various ways to improve the performance of a sequential circuit. In particular, an important problem of multi-cycle false path removal from sequential circuits was studied in detail. The thesis presents certain observations and discusses properties of multi-cycle false paths at various levels of abstraction. A thorough and complete analysis of multi-cycle false paths at the logical, functional and behavioral level is presented and the relationship between the various levels is explained. The thesis presents a method to identify and remove false paths at the functional level and a method for the prediction of false paths at the behavioral level. The thesis also describes an efficient method utilizing high level information for timing verification and test generation. The necessary and sufficient conditions to remove multi-cycle false paths is derived and a constrained satisfaction based direct encoding methodology to obtain false path free sequential circuits is presented. A simple formula for the minimum number of registers needed for such an encoding is also derived.

<p> Image Processing and Computer Vision (CVIP) applications can be developed and analyzed using the CVIPtools software developed at Southern Illinois University Edwardsville in the CVIP Laboratory under the guidance of Dr. Scott E Umbaugh. The CVIPtools software has been created with the code in the C/C++/C# programming languages. Due to the popularity in engineering applications for Matlab use it was decided to port the CVIPtools libraries functions to Matlab M-files and create a CVIP Toolbox for Matlab. </p><p> This work consists of developing, testing, packaging, developing documentation for, and releasing the first version of the Matlab Computer Vision and Image Processing Toolbox. In this there are several steps involved which are described clearly in this research work. The primary aim of thesis work is to create a toolbox which is independent of any other toolboxes in Matlab. CVIPtools has over 200 functions which are written in C, but due to growing demand for Matlab we decided to make the functions available in Matlab. After the toolbox is created, the user can install it and can use the functions in the toolbox as Matlab inbuilt functions. This will make it easy for the user to understand and experiment with different CVIP algorithms. </p><p> Initially the toolbox was created writing wrapper functions for the programs written in C through the creation of MEX functions. But later due to problems during testing, it was determined [5] that it would be more suitable to write separate Matlab code, M-files for all the functions and create new toolbox. </p><p> The CVIP Toolbox for Matlab is an open source project and is independent of any other toolboxes. Thus, the user can install the toolbox and can use all the functions as Matlab inbuilt functions without the need to purchase any of the other Matlab toolboxes, which is required for other toolboxes of this type. There are 206 functions in this first version of toolbox which are the primary functions for CVIP applications. These functions are arranged according to categories so that it will be easy for the user to understand and search various functions. </p><p> The CVIP Toolbox is organized into several folders including CVIP Lab, which allows the user to create any algorithm with the help of functions available in the toolbox. The user can explore by using different functions in the toolbox and varying parameters experimentally to achieve desired results. The skeleton program for lab is in cviplab.m which has a sample function implemented so that the user can see how the sample is executed and can call other functions using the same method.</p><p>

<p> The objective of this dissertation is the design, development, and experimental evaluation of novel algorithms and reconfigurable radio architectures for spectrally efficient cognitive networking in terrestrial, airborne, and underwater environments. Next-generation wireless communication architectures and networking protocols that maximize spectrum utilization efficiency in congested/contested or low-spectral availability (extreme) communication environments can enable a rich body of applications with unprecedented societal impact. In recent years, underwater wireless networks have attracted significant attention for military and commercial applications including oceanographic data collection, disaster prevention, tactical surveillance, offshore exploration, and pollution monitoring. Unmanned aerial systems that are autonomously networked and fully mobile can assist humans in extreme or difficult-to-reach environments and provide cost-effective wireless connectivity for devices without infrastructure coverage. </p><p> Cognitive radio (CR) has emerged as a promising technology to maximize spectral efficiency in dynamically changing communication environments by adaptively reconfiguring radio communication parameters. At the same time, the fast developing technology of software-defined radio (SDR) platforms has enabled hardware realization of cognitive radio algorithms for opportunistic spectrum access. However, existing algorithmic designs and protocols for shared spectrum access do not effectively capture the interdependencies between radio parameters at the physical (PHY), medium-access control (MAC), and network (NET) layers of the network protocol stack. In addition, existing off-the-shelf radio platforms and SDR programmable architectures are far from fulfilling runtime adaptation and reconfiguration across PHY, MAC, and NET layers. Spectrum allocation in cognitive networks with multi-hop communication requirements depends on the location, network traffic load, and interference profile at each network node. As a result, the development and implementation of algorithms and cross-layer reconfigurable radio platforms that can jointly treat space, time, and frequency as a unified resource to be dynamically optimized according to inter- and intra-network interference constraints is of fundamental importance. </p><p> In the next chapters, we present novel algorithmic and software/hardware implementation developments toward the deployment of spectrally efficient terrestrial, airborne, and underwater wireless networks. In Chapter 1 we review the state-of-art in commercially available SDR platforms, describe their software and hardware capabilities, and classify them based on their ability to enable rapid prototyping and advance experimental research in wireless networks. Chapter 2 discusses system design and implementation details toward real-time evaluation of a software-radio platform for all-spectrum cognitive channelization in the presence of narrowband or wideband primary stations. All-spectrum channelization is achieved by designing maximum signal-to-interference-plus-noise ratio (SINR) waveforms that span the whole continuum of the device-accessible spectrum, while satisfying peak power and interference temperature (IT) constraints for the secondary and primary users, respectively. In Chapter 3, we introduce the concept of all-spectrum channelization based on max-SINR optimized sparse-binary waveforms, we propose optimal and suboptimal waveform design algorithms, and evaluate their SINR and bit-error-rate (BER) performance in an SDR testbed. Chapter 4 considers the problem of channel estimation with minimal pilot signaling in multi-cell multi-user multi-input multi-output (MIMO) systems with very large antenna arrays at the base station, and proposes a least-squares (LS)-type algorithm that iteratively extracts channel and data estimates from a short record of data measurements. Our algorithmic developments toward spectrally-efficient cognitive networking through joint optimization of channel access code-waveforms and routes in a multi-hop network are described in Chapter 5. Algorithmic designs are software optimized on heterogeneous multi-core general-purpose processor (GPP)-based SDR architectures by leveraging a novel software-radio framework that offers self-optimization and real-time adaptation capabilities at the PHY, MAC, and NET layers of the network protocol stack. Our system design approach is experimentally validated under realistic conditions in a large-scale hybrid ground-air testbed deployment. Chapter 6 reviews the state-of-art in software and hardware platforms for underwater wireless networking and proposes a software-defined acoustic modem prototype that enables (i) cognitive reconfiguration of PHY/MAC parameters, and (ii) cross-technology communication adaptation. The proposed modem design is evaluated in terms of effective communication data rate in both water tank and lake testbed setups. In Chapter 7, we present a novel receiver configuration for code-waveform-based multiple-access underwater communications. The proposed receiver is fully reconfigurable and executes (i) all-spectrum cognitive channelization, and (ii) combined synchronization, channel estimation, and demodulation. Experimental evaluation in terms of SINR and BER show that all-spectrum channelization is a powerful proposition for underwater communications. At the same time, the proposed receiver design can significantly enhance bandwidth utilization. Finally, in Chapter 8, we focus on challenging practical issues that arise in underwater acoustic sensor network setups where co-located multi-antenna sensor deployment is not feasible due to power, computation, and hardware limitations, and design, implement, and evaluate an underwater receiver structure that accounts for multiple carrier frequency and timing offsets in virtual (distributed) MIMO underwater systems.</p><p>

Higher bandwidths in computer networks have made application with real-time constraints, such as control, command, and interactive voice and video communication feasible. We describe two congestion control mechanisms that utilize properties of real-time applications. First, many real-time applications, such as voice and video, can tolerate some loss due to signal redundancy. We propose and analyze a congestion control algorithm that aims to discard packets if they stand little chance of reaching their destination in time as early on their path as possible. Dropping late and almost-late packets improves the likelihood that other packets will make their deadline. Secondly, in real-time systems with fixed deadlines, no improvement in performance is gained by arriving before the deadline. Thus, packets that are late and have many hops to travel are given priority over those with time to spare and close to their destination by introducing a hop-laxity priority measure. Simulation results show marked improvements in loss performance. The implementation of the algorithm within a router kernel for the DARTnet test network is described in detail. Because of its unforgiving real-time requirements, packet audio was used as one evaluation tool; thus, we developed an application for audio conferencing. Measurements with that tool show that traditional source models are seriously flawed. Real-time services are one example of traffic whose perceived quality of service depends not only on the loss rate but also on the correlation of losses. We investigate the correlation of losses due to buffer overflow and deadline violations in both continuous and discrete-time queueing systems. We show that loss correlation does not depend on value of the deadline for M/G/1 systems and is generally only weakly influenced by buffer sizes. Per-stream loss correlation in systems with periodic and Bernoulli on/off sources are evaluated analytically. Numerical examples indicate that loss correlation is of limited influence as long as each stream contributes less than about one-tenth of the overall network load.

<p> State-of-the-arts design, implementation, and optimization of Ultra-Low Power Radio Frequency Integrated Circuits (ULP RFIC) for medical, space, and mobile applications have been proposed. New approximated formulas in modeling of the circuits and systems for CAD development have been suggested which make the computer simulations more accurate. Algorithm optimizations for faster design time and possible automations compared to traditional and manual implementations are also offered that reduce the final release time of the products in a more systematic way. These design methodologies are based on advancements of IC fabrication in scaling to Nano-meter regimes, improvement of powerful software simulation tools especially at high frequencies, and manipulating novel ideas in development phases. Note that these design proposals are not only limited to space, biomedical, and mobile application; as a matter of fact, they can be used in any chip design and development ranging from smart watch to glasses and etc.</p><p> To have a comprehensive understanding of wireless system design and circuit implementation requires years of experiences and research on multi-disciplinary areas ranging from semiconductor at physic level, circuit analysis, software programming for simulation, test and automation purposes, architecture level, high frequency and RF behavior of components and many more. That is why it has been said the RF design is challenging and takes more years to become an expert on these areas. There are still huge shortages for RF and Analog engineers due to the challenges throughout the world both in industry and academia.</p><p> For the circuits presented in this dissertation, frequencies range from ISM band 2.4GHz for mobile application to 10GHz and 24 GHz in microwave applications. The detail analyses for implementations and simulations have been shown to verify the implementations. Optimizations are presented by extensive analysis and iterative simulations. Solutions and tips to simplify design flows are mentioned throughout the dissertation.</p><p> Chapters begin with introductions and motivations; next, detail discussion and investigation are presented in subsequent sections; finally summaries giving at the end of each chapter. At the end of dissertation, the possible future works and research orientation have been proposed.</p>