High data rate applications are the trend in today's wireless technology. W-CDMA standard was designed to support such high data rates of up to 3.84 Mcps. The main purpose of this research was to analyze the feasibility of a fixed-point implementation of the W-CDMA downlink receiver algorithm on a general-purpose digital signal processor (StarCore SC140 by Motorola). The very large instruction word architecture of SC140 core is utilized to generate optimal implementation, to meet the real time timing requirements of the algorithm. The other main aim of this work was to study and evaluate the performance of the W-CDMA downlink structure with incorporated space-time transmit diversity. The effect of the channel estimation algorithm used was extensively studied too.

DNA can be represented abstrzctly as a language with only four nucleotides represented by the letters A, C, G, and T, yet the arrangement of those four letters plays a major role in determining the development of an organism. Understanding the signi cance of certain arrangements of nucleotides can unlock the secrets of how the genome achieves its essential functionality. Regions of DNA particularly enriched with cytosine (C nucleotides) and guanine (G nucleotides), especially the CpG di-nucleotide, are frequently associated with biological function related to gene expression, and concentrations of CpGs referred to as \CpG islands" are known to collocate with regions upstream from gene coding sequences within the promoter region. The pattern of occurrence of these nucleotides, relative to adenine (A nucleotides) and thymine (T nucleotides), lends itself to analysis by machine-learning techniques such as Hidden Markov Models (HMMs) to predict the areas of greater enrichment. HMMs have been applied to CpG island prediction before, but often without an awareness of how the outcomes are a ected by the manner in which the HMM is applied. Two main ndings of this study are: 1. The outcome of a HMM is highly sensitive to the setting of the initial probability estimates. 2. Without the appropriate software techniques, HMMs cannot be applied e ectively to large data such as whole eukaryotic chromosomes. Both of these factors are rarely considered by users of HMMs, but are critical to a successful application of HMMs to large DNA sequences. In fact, these shortcomings were discovered through a close examination of published results of CpG island prediction using HMMs, and without being addressed, can lead to an incorrect implementation and application of HMM theory. A rst-order HMM is developed and its performance compared to two other historical methods, the Takai and Jones method and the UCSC method from the University of California Santa Cruz. The HMM is then extended to a second-order to acknowledge that pairs of nucleotides de ne CpG islands rather than single nucleotides alone, and the second-order HMM is evaluated in comparison to the other methods. The UCSC method is found to be based on properties that are not related to CpG islands, and thus is not a fair comparison to the other methods. Of the other methods, the rst-order HMM method and the Takai and Jones method are comparable in the tests conducted, but the second-order HMM method demonstrates superior predictive capabilities. However, these results are valid only when taking into consideration the highly sensitive outcomes based on initial estimates, and nding a suitable set of estimates that provide the most appropriate results. The rst-order HMM is applied to the problem of producing synthetic data that simulates the characteristics of a DNA sequence, including the speci ed presence of CpG islands, based on the model parameters of a trained HMM. HMM analysis is applied to the synthetic data to explore its delity in generating data with similar characteristics, as well as to validate the predictive ability of an HMM. Although this test fails to i meet expectations, a second test using a second-order HMM to produce simulated DNA data using frequency distributions of CpG island pro les exhibits highly accurate predictions of the pre-speci ed CpG islands, con- rming that when the synthetic data are appropriately structured, an HMM can be an accurate predictive tool. One outcome of this thesis is a set of software components (CpGID 2.0 and TrackMap) capable of ef- cient and accurate application of an HMM to genomic sequences, together with visualization that allows quantitative CpG island results to be viewed in conjunction with other genomic data. CpGID 2.0 is an adaptation of a previously published software component that has been extensively revised, and TrackMap is a companion product that works with the results produced by the CpGID 2.0 program. Executing these components allows one to monitor output aspects of the computational model such as number and size of the predicted CpG islands, including their CG content percentage and level of CpG frequency. These outcomes can then be related to the input values used to parameterize the HMM.

Trellis-coded Modulation (TCM) is used in bandlimited communication systems. TCM efficiency improves coding gain by combining modulation and forward error correction coding in one process. In TCM, the bandwidth expansion is not required because it uses the same symbol rate and power spectrum; the differences are the introduction of a redundancy bit and the use of a constellation with double points. <p> In this thesis, a novel TCM encoder/decoder ASIC chip implementation is presented. This ASIC codec not only increases decoding speed but also reduces hardware complexity. The algorithm and technique are presented for a 16-state convolutional code which is used in standard 256-QAM wireless systems. In the decoder, a Hamming distance is used as a cost function to determine output in the maximum likelihood Viterbi decoder. Using the relationship between the delay states and the path state in the Trellis tree of the code, a pre-calculated Hamming distances are stored in a look-up table. In addition, an output look-up-table is generated to determine the decoder output. This table is established by the two relative delay states in the code. The thesis provides details of the algorithm and the structure of TCM codec chip. Besides using parallel processing, the ASIC implementation also uses pipelining to further increase decoding speed. <p> The codec was implemented in ASIC using standard 0.18Ým CMOS technology; the ASIC core occupied a silicon area of 1.1mm2. All register transfer level code of the codec was simulated and synthesized. The chip layout was generated and the final chip was fabricated by Taiwan Semiconductor Manufacturing Company through the Canadian Microelectronics Corporation. The functional testing of the fabricated codec was performed partially successful; the timing testing has not been fully accomplished because the chip was not always stable.

Trellis-coded Modulation (TCM) is used in bandlimited communication systems. TCM efficiency improves coding gain by combining modulation and forward error correction coding in one process. In TCM, the bandwidth expansion is not required because it uses the same symbol rate and power spectrum; the differences are the introduction of a redundancy bit and the use of a constellation with double points. <p> In this thesis, a novel TCM encoder/decoder ASIC chip implementation is presented. This ASIC codec not only increases decoding speed but also reduces hardware complexity. The algorithm and technique are presented for a 16-state convolutional code which is used in standard 256-QAM wireless systems. In the decoder, a Hamming distance is used as a cost function to determine output in the maximum likelihood Viterbi decoder. Using the relationship between the delay states and the path state in the Trellis tree of the code, a pre-calculated Hamming distances are stored in a look-up table. In addition, an output look-up-table is generated to determine the decoder output. This table is established by the two relative delay states in the code. The thesis provides details of the algorithm and the structure of TCM codec chip. Besides using parallel processing, the ASIC implementation also uses pipelining to further increase decoding speed. <p> The codec was implemented in ASIC using standard 0.18Ým CMOS technology; the ASIC core occupied a silicon area of 1.1mm2. All register transfer level code of the codec was simulated and synthesized. The chip layout was generated and the final chip was fabricated by Taiwan Semiconductor Manufacturing Company through the Canadian Microelectronics Corporation. The functional testing of the fabricated codec was performed partially successful; the timing testing has not been fully accomplished because the chip was not always stable.

Since the invention of wireless telegraphy by Marconi in 1897, wireless technology has not only been enhanced, but also has become an integral part of our everyday lives. The first wireless mobile phone appeared around 1980. It was based on first generation analog technology that involved the use of Frequency Division Multiple Access (FDMA) techniques. Ten years later, second generation (2G) mobiles were dependent on Time Division Multiple Access (TDMA) techniques and Code Division Multiple Access (CDMA) techniques. Nowadays, third generation (3G) mobile systems depend on CDMA techniques to satisfy the need for faster, and more capacious data transmission in mobile wireless networks. Wideband CDMA (WCDMA) has become the major 3G air interface in the world. WCDMA employs convolutional encoding to encode voice and MPEG4 applications in the baseband transmitter at a maximum frequency of 2<i>Mbps</i>. To decode convolutional codes, Andrew Viterbi invented the Viterbi Decoder (VD) in 1967. In 2G mobile terminals, the VD consumes approximately one third of the power consumption of a baseband mobile transceiver. Thus, in 3G mobile systems, it is essential to reduce the power consumption of the VD. Conceptually, the Register Exchange (RE) method is simpler and faster than the Trace Back (TB) method for implementing the VD. However, in the RE method, each bit in the memory must be read and rewritten for each bit of information that is decoded. Therefore, the RE method is not appropriate for decoders with long constraint lengths. Although researchers have focused on implementing and optimizing the TB method, the RE method is focused on and modified in this thesis to reduce the RE method's power consumption. This thesis proposes a novel modified RE method by adopting a <i>pointer</i> concept for implementing the survivor memory unit (SMU) of the VD. A pointer is assigned to each register or memory location. The contents of thepointer which points to one register is altered to point to a second register, instead of copying the contents of the first register to the second. When the pointer concept is applied to the RE's SMU implementation (modified RE), there is no need to copy the contents of the SMU and rewrite them, but one row of memory is still needed for each state of the VD. Thus, the VDs in CDMA systems require 256 rows of memory. Applying the pointer concept reduces the VD's power consumption by 20 percent as estimated by the VHDL synthesis tool and by the new power reduction estimation that is introduced in this work. The coding gain for the modified RE method is 2. 6<i>dB</i> at an SNR of approximately 10-3. Furthermore, a novel zero-memory implementation for the modified RE method is proposed. If the initial state of the convolutional encoder is known, the entire SMU of the modified RE VD is reduced to only one row. Because the decoded data is generated in the required order, even this row of memory is dispensable. The zero-memory architecture is called the MemoryLess Viterbi Decoder (MLVD), and reduces the power consumption by approximately 50 percent. A prototype of the MLVD with a one third convolutional code rate and a constraint length of nine is mapped into a Xilinx 2V6000 chip, operating at 25 <i>MHz</i> with a decoding throughput of more than 3<i>Mbps</i> and a latency of two data bits. The other problem of the VD which is addressed in this thesis is the Add Compare Select Unit (ACSU) which is composed of 128 butterfly ACS modules. The ACSU's high parallelism has been previously solved by using a bit serial implementation. The 8-bit First Input First Output (FIFO) register, needed for the storage of each path metric (PM), is at the heart of the single bit serial ACS butterfly module. A new, simply controlled shift register is designed at the circuit level and integrated into the ACS module. A chip for the new module is also fabricated.

Recent attempts to increase the capacity of the compact disc (CD) and digital versatile disc (DVD) have explored the use of multilevel recording instead of binary recording. Systems that achieve an increase in capacity of about three times that of conventional CD have been proposed for production. Marks in these systems are multilevel and fixed-length as opposed to binary and variable length in CD and DVD. The main objective of this work is to evaluate the performance of multilevel ($M$-ary) runlength-limited (RLL) coded sequences in optical data storage. First, the waterfilling capacity of a multilevel optical recording channel ($M$-ary ORC) is derived and evaluated. This provides insight into the achievable user bit densities, as well as a theoretical limit against which simulated systems can be compared. Then, we evaluate the performance of RLL codes on the $M$-ary ORC. A new channel model that includes the runlength constraint in the transmitted signal is used. We compare the performance of specific RLL codes, namely $M$-ary permutation codes, to that of real systems using multilevel fixed-length marks for recording and the theoretical limits. The Viterbi detector is used to estimate the original recorded symbols from the readout signal. Then, error correction is used to reduce the symbol error probability. We use a combined ECC/RLL code for phrase encoding. We evaluate the use of trellis coded modulation (TCM) for amplitude encoding. The detection of the readout signal is also studied. A post-processing algorithm for the Viterbi detector is introduced, which ensures that the detected word satisfies the code constraints. Specifying the codes and detector for the $M$-ary ORC gives a complete system whose performance can be compared to that of the recently developed systems found in the literature and the theoretical limits calculated in this research.

In this thesis, the low-power design of two popular error-control code decoders has been presented. It first proposes a low-power Viterbi decoder based on the improved reference path generation method which can lead to significant reduction of the memory accesses during the trace-back operation of the survival memory unit. The use of the reference path has been addressed in the past; this mechanism is further extended in this thesis to take into account the selection of starting states for the trace-back and path prediction operations. Our simulation results show that the best saving ratio of memory access can be up to 92% by choosing the state with the minimum state-metric for both trace-back and path prediction. However, the implementation of our look-ahead path prediction initiated from the minimum state will suffer a lot of area overhead especially for Viterbi applications with large state number. Therefore, this thesis instead realizes a 64-state Viterbi decoder whose path prediction starts from the predicted state obtained from the previous prediction phase. Our implementation results show that the actual power reduction ratio ranges from 31% to 47% for various signal-to-noise ratio settings while the area overhead is about 10%. The second major contribution of this thesis is to apply the similar low-power technique to the design of Soft-Output-Viterbi-Algorithm (SOVA) based Turbo code decoders. Our experimental results show that for eight-state SOVA Turbo code, our reference path generation mechanism can reduce more that 95% memory accesses, which can help saving the overall power consumption by 15.6% with a slight area overhead of 3%.

In wireless communication system, convolution code has been one of the most popular error-correcting code. To prevent from the interference of noise during transmission, the transmitter usually applies convolution encode to code the processed information, and the receiver will use Viterbi decoder to decode and correct the error bit to decrease the bit error rate. In 3G mobile communication, such decoder is often applied between the base station and the communication device as a decoding mechanism. Since traditional decoders of communication devices consume more than one third power of the whole receiver, the present study focuses on the way effectively reducing the power consumption of Viterbi decoder. Traditional convolution coders use zero-tail, which make decoder be able to resist the interference of noise; however, this method would increase extra tail bits, which would decrease the code rate and affect the efficiency of transmission, especially for those information with short length, such as the header of packet. Tail-biting convolution code is another error-correcting code, which maintains the code rate, and it has been used in the control channel of LTE. Tail-biting convolution code is more complex than traditional decoder. Therefore, this thesis modifies the Wrap-Around Viterbi Algorithm (WAVA) to enormously decrease the power consuming while maintaining the bit error rate and the correctness of decoding. The aim of the present study is achieved by decreasing iteration number of WAVA algorithm to reduce one fourth of the whole power consumption. On the other hand, if the received information is not interfered by noise, it¡¦s unnecessary to turn on Tail-biting Convolution Decoder. As a result, the present study introduces the error detection circuit so that the received information can be simply decode and detected with the error detection circuit. If there is no noise interference, it can directly be outputted; if there is noise interference, however, it should be decoded by Tail-biting Convolution Decoder. The experimental results show that the survivor memory unit saves more than 60% power than traditional decoders, moreover, it will save 55%~88% power consumption when it goes with the error detection circuit. Consequently, the proposed method is indeed able to reduce the power consumption of Tail-biting Convolution Decoder. Keyword¡Gwireless communication, tail-biting convolution code, code rate, Viterbi decoder, power consumption

Recent advancements in massively parallel biosensing and sequencing technologies have revolutionized the field of molecular biology and paved the way to novel and exciting innovations in medicine, biology, and environmental monitoring. Among them, biosensor arrays (e.g., DNA and protein microarrays) have gained a lot of attention. DNA microarrays are parallel affinity biosensors that can detect the presence and quantify the amounts of nucleic acid molecules of interest. They rely on chemical attraction between target nucleic acid sequences and their Watson-Crick complements that serve as probes and capture the targets. The molecular binding between the probes and targets is a stochastic process and hence the number of captured targets at any time is a random variable. Detection in conventional DNA microarrays is based on a single measurement taken in the steady state of the binding process. Recently developed real-time DNA microarrays, on the other hand, acquire multiple temporal measurements which allow more precise characterization of the reaction and enable faster detection based on the early dynamics of the binding process. In this thesis, I study target estimation and limits of performance of real time affinity biosensors. Target estimation is mapped to the problem of estimating parameters of discretely observed nonlinear diffusion processes. Performance of the estimators is characterized analytically via Cramer-Rao lower bound on the mean-square error. The proposed algorithms are verified on both simulated and experimental data, demonstrating significant gains over state-of-the-art techniques. In addition to biosensor arrays, in this thesis I present studies of the signal processing aspects of next-generation sequencing systems. Novel sequencing technologies will provide significant improvements in many aspects of human condition, ultimately leading towards the understanding, diagnosis, treatment and prevention of diseases. Reliable decision-making in such downstream applications is predicated upon accurate base-calling, i.e., identification of the order of nucleotides from noisy sequencing data. Base-calling error rates are nonuniform and typically deteriorate with the length of the reads. I have studied performance limits of base-calling, characterizing it by means of an upper bound on the error rates. Moreover, in the context of shotgun sequencing, I analyzed how accuracy of an assembled sequence depends on coverage, i.e., on the average number of times each base in a target sequence is represented in different reads. These analytical results are verified using experimental data. Among many downstream applications of high-throughput biosensing and sequencing technologies, reconstruction of gene regulatory networks is of particular importance. In this thesis, I consider the gene network inference problem and propose a probabilistic graphical approach for solving it. Specifically, I develop graphical models and design message passing algorithms which are then verified using experimental data provided by the Dialogue for Reverse Engineering Assessment and Methods (DREAM) initiative. / text

High data rate applications are the trend in today's wireless technology. W-CDMA standard was designed to support such high data rates of up to 3.84 Mcps. The main purpose of this research was to analyze the feasibility of a fixed-point implementation of the W-CDMA downlink receiver algorithm on a general-purpose digital signal processor (StarCore SC140 by Motorola). The very large instruction word architecture of SC140 core is utilized to generate optimal implementation, to meet the real time timing requirements of the algorithm. The other main aim of this work was to study and evaluate the performance of the W-CDMA downlink structure with incorporated space-time transmit diversity. The effect of the channel estimation algorithm used was extensively studied too.