We prove that for all 0 ≤ t ≤ k and d ≥ 2k, every graph G with treewidth at most k has a 'large' induced subgraph H, where H has treewidth at most t and every vertex in H has degree at most d in G, The order of H depends on t, k, d, and the order of G. With t = k, we obtain large sets of bounded degree vertices. With t = 0, we obtain large independent sets of bounded degree. In both these cases, our bounds on the order of H are tight. For bounded degree independent sets in trees, we characterise the extremal graphs. Finally, we prove that an interval graph with maximum clique size k has a maximum independent set in which every vertex has degree at most 2k.
A near infrared (NIR) electrochromic attenuator based on a dinuclear ruthenium complex and polycrystalline tungsten oxide was fabricated and characterized. The results show that the use of the NIR-absorbing ruthenium complex as a counter electrode material can improve the device performance. By replacing the visible electrochromic ferrocene with the NIR-absorbing ruthenium complex, the optical attenuation at 1550 nm was enhanced from 19.1 to 30.0 dB and color efficiency also increased from 29.2 to 121.2 cm2/C.
There have been a number of steganography embedding techniques proposed over the past few years. In turn, there has been great interest in steganalysis techniques as the embedding techniques improve. Specifically, universal steganalysis techniques have become more attractive since they work independently of the embedding technique. In this work, we examine the effectiveness of a basic universal technique that relies on some knowledge about the cover media, but not the embedding technique. We consider images as a cover media, and examine how a single technique that we call steganographic sanitization performs on 26 different steganography programs that are publicly available on the Internet. Our experiments are completed using a number of secret messages and a variety of different levels of sanitization. However, since our intent is to remove covert communication, and not authentication information, we examine how well the sanitization process preserves authentication information such as watermarks and digital fingerprints.
This thesis explores theoretical and practical aspects of iterative decoding algorithms when they are implemented on analog continuous-time platforms. Analog continuous-time iterative decoding was proposed a few years ago to improve the power/speed ratio of decoder chips that decode capacity achieving codes. It was commonly believed that replacing discrete-time processing modules with analog circuits would not change the dynamics of the iterative decoder. On the contrary, we show that not only does continuous-time iterative decoding have different dynamics, but also its error correcting performance can surpass that of conventional iterative decoders. We also present a simple model for ideal continuous-time iterative decoding.As a direct consequence of our study on the dynamics of analog decoders, we show that by looking at the decoding as a numerical problem and using advanced numerical techniques, we are able to improve the convergence rate and decoding performance of iterative decoding algorithms.Furthermore, we devise novel processing modules for implementing affordable high-speed analog min-sum iterative decoders by using strongly inverted CMOS transistors. This is favorable because previously reported analog decoders were either BiCMOS or weakly inverted CMOS designs. The former could be fast but is rather expensive and the latter would be low-power but it is not fast enough for many applications. Our design is modular and the main blocks are constructed based on current mirrors and virtually any accurate current mirror can be used as the main block in our design. As an example, we show how the building modules can be designed in deep submicron CMOS technologies. We also present an appropriate design methodology for implementing high-degree blocks that can drastically reduce silicon area and power consumption.To prove the functionality of the proposed circuits, an analog min-sum iterative decoder chip for a (32,8) regular LDPC code was designed and fabricated in 0.18pm CMOS technology. This chip is the first analog min-sum iterative decoder. Also, it is the first functional analog iterative decoder for an LDPC code and is the fastest reported analog CMOS iterative decoder. Measurement results not only show that the proposed circuits are functional but also confirm the validity of our proposed model for ideal analog decoding. In fact, when noise in the channel is dominant compared to the imperfections in the analog iterative decoder, the simulation results based on our proposed model are close to the measurement results.
In a video conferencing environment, it is desirable to isolate the active talker. Traditionally, talker localization is performed acoustically using a beamforming microphone array or videographically using image processing techniques. Since these approaches rely only on the audio or the video data for performing the localization, they are often prone to errors. In this thesis, a new modular multimodal architecture is designed. Data from each localization modality are separated in the beginning, and localizations are performed using each data stream independently. In order to study the effectiveness of this modular multimodal architecture, this thesis combines audio, visual and infrared cues to locate talkers in the video conferencing environment. Special purpose acoustic, video and thermo localizers are developed to perform the localization. Individual results from the localizers are then combined using data fusion techniques to give the final estimation of the talker’s location. Two common fusion methods, the summing voter and the Bayesian network, are studied in this thesis. The effectiveness of another two novel fusion methods, the talker occupancy grid assisted summing voter and the talker occupancy grid assisted Bayesian network, are also investigated. A unique algorithm that uses the correlation lags to detect acoustic reflections is also developed in the process of this thesis. Based on the results from experiments and computer simulations, the proposed multimodal localization method outperforms localization methods, in terms of accuracy and robustness, when compared with other single modal methods that rely only on audio, video, or infrared data.