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.

In this thesis, the VLSI implementation of Viterbi decoder using a design and simulation platform called SystemC is studied. For this purpose, the architecture of Viterbi decoder is tried to be optimized for VLSI implementations. Consequently, two novel area efficient structures for reconfigurable Viterbi decoders have been suggested. The traditional and SystemC design cycles are compared to show the advantages of SystemC, and the C++ platforms supporting SystemC are listed, installation issues and examples are discussed. The Viterbi decoder is widely used to estimate the message encoded by Convolutional encoder. For the implementations in the literature, it can be found that special structures called trellis have been formed to decrease the complexity and the area. In this thesis, two new area efficient reconfigurable Viterbi decoder approaches are suggested depending on the rearrangement of the states of the trellis structures to eliminate the switching and memory addressing complexity. The first suggested architecture based on reconfigurable Viterbi decoder reduces switching and memory addressing complexity. In the architectures, the states are reorganized and the trellis structures are realized by the usage of the same structures in subsequent instances. As the result, the area is minimized and power consumption is reduced. Since the addressing complexity is reduced, the speed is expected to increase. The second area efficient Viterbi decoder is an improved version of the first one and has the ability to configure the parameters of constraint length, code rate, transition probabilities, trace-back depth and generator polynomials.

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

In this thesis, symbol timing recovery in MSK signals is investigated making use of matched filtering. A decision-directed symbol synchronizer cascaded with an MLSE receiver is proposed for fine timing. Correlation (matched filter) method is used to recover the timing epoch from the tentative decisions obtained from the Viterbi algorithm. The fractional delays are acquired using interpolation and an iterative maximum search process. In order to investigate the tracking performance of the proposed symbol synchronizer, a study is carried out on three possible optimum timing phase criteria: (i) Mazo criterion, (ii) the minimum squared ISI criterion (msISI), and (iii) the minimum BER criterion. Moreover, a discussion is given about the timing sensitivity of the MLSE receiver. The performance of the symbol synchronizer is assessed by computer simulations. It is observed that the proposed synchronizer tracks the variations of the channels almost the same as the msISI criterion. The proposed method eliminates the cycle slips very succesfully and is robust to frequency-selective multipath fading channel conditions even in moderate signal-to-noise ratios.

The process of locating moving objects through video sequences is a fundamental computer vision problem. This process is referred to as video tracking and has a broad range of applications. Even though video tracking is an open research topic that have received much attention during recent years, developing accurate and robust algorithms that can handle complicated tracking tasks and scenes is still challenging. One challenge in computer vision is to develop systems that like humans can understand, interpret and recognize visual information in different situations. In this master thesis work, a tracking algorithm based on eye tracking data is proposed. The aim was to compare the tracking performance of the proposed algorithm with a state-of-the-art video tracker. The algorithm was tested on gaze signals from five participants recorded with an eye tracker while the participants were exposed to dynamic stimuli. The stimuli were moving objects displayed on a stationary computer screen. The proposed algorithm is working offline meaning that all data is collected before analysis. The results show that the overall performance of the proposed eye tracking algorithm is comparable to the performance of a state-of-the-art video tracker. The main weaknesses are low accuracy for the proposed eye tracking algorithm and handling of occlusion for the video tracker. We also suggest a method for using eye tracking as a complement to object tracking methods. The results show that the eye tracker can be used in some situations to improve the tracking result of the video tracker. The proposed algorithm can be used to help the video tracker to redetect objects that have been occluded or for some other reason are not detected correctly. However, ATOM brings higher accuracy.

This thesis investigates the use of Maximum Likelihood Sequence Estimation (MLSE) in the presence of unknown channel parameters. MLSE is a fundamental problem that is closely related to many modern research areas like Space-Time Coding, Overloaded Array Processing and Multi-User Detection. Per-Survivor Processing (PSP) is a technique for approximating MLSE for unknown channels by embedding channel estimation into the structure of the Viterbi Algorithm (VA). In the case of successful acquisition, the convergence rate of PSP is comparable to that of the pilot-aided RLS algorithm. However, the performance of PSP degrades when certain sequences are transmitted. In this thesis, the blind acquisition characteristics of PSP are discussed. The problematic sequences for any joint ML data and channel estimator are discussed from an analytic perspective. Based on the theory of indistinguishable sequences, modifications to conventional PSP are suggested that improve its acquisition performance significantly. The effect of tree search and list-based algorithms on PSP is also discussed. Proposed improvement techniques are compared for different channels. For higher order channels, complexity issues dominate the choice of algorithms, so PSP with state reduction techniques is considered. Typical misacquisition conditions, transients, and initialization issues are reported. / Master of Science

Detecting and correcting errors occurring in the transmitted data through a channel is a task of great importance in digital communication. In Error Correction Coding (ECC), some redundant data is added with the original data while transmitting. By exploiting the properties of the redundant data, the errors occurring in the data from the transmission can be detected and corrected. In this thesis, a new coding algorithm named Signal Point Target Code has been studied and various properties of the proposed code have been extended. Signal Point Target Code (SPTC) uses a predefined shape within a given signal constellation to generate a parity symbol. In this thesis, the relation between the employed shape and the performance of the proposed code have been studied and an extension of the SPTC are presented. This research presents simulation results to compare the performances of the proposed codes. The results have been simulated using different programming languages, and a comparison between those programming languages is provided. The performance of the codes are analyzed and possible future research areas have been indicated.

No description available.

In coherent receivers, the effect of the multipath fading channel on the transmitted signal must be estimated to recover the transmitted data. In this thesis, the channel phase and data estimation problems are investigated in a transmitted data sequence when the channel is modeled as slowly fading, frequency non-selective channel. Channel phase estimation in a transmitted data sequence is investigated and data estimation is obtained in a symbol-by-symbol MAP receiver that is designed for minimum symbol error probability criterion. The channel phase is quantized in an interval of interest, the trellis diagram is constructed and Viterbi decoding algorithm is applied that uses the phase transition and observation models for channel phase estimation. The optimum coherent and noncoherent detectors for binary orthogonal and PSK signals are derived and the modulated signals in a sequence are detected in symbol-by-symbol MAP receivers.Simulation results have shown that the performance of the receiver with phase estimation is between the performance of the optimum coherent and noncoherent receiver.

It is crucial to find a good balance between positioning accuracy and cost when developing navigation systems for ground vehicles. In open sky or even in a semi-urban environment, a single global navigation satellite system (GNSS) constellation performs sufficiently well. However, the positioning accuracy decreases drastically in urban environments. Because of the limitation in tracking performance for standalone GNSS, particularly in cities, many solutions are now moving toward integrated systems that combine complementary sensors. In this master thesis the improvement of tracking performance for a low-cost ground vehicle navigation system is evaluated when complementary sensors are added and different filtering techniques are used. How the GNSS aided inertial navigation system (INS) is used to track ground vehicles is explained in this thesis. This has shown to be a very effective way of tracking a vehicle through GNSS outages. Measurements from an accelerometer and a gyroscope are used as inputs to inertial navigation equations. GNSS measurements are then used to correct the tracking solution and to estimate the biases in the inertial sensors. When velocity constraints on the vehicle’s motion in the y- and z-axis are included, the GNSS aided INS has shown very good performance, even during long GNSS outages. Two versions of the Rauch-Tung-Striebel (RTS) smoother and a particle filter (PF) version of the GNSS aided INS have also been implemented and evaluated. The PF has shown to be computationally demanding in comparison with the other approaches and a real-time implementation on the considered embedded system is not doable. The RTS smoother has shown to give a smoother trajectory but a lot of extra information needs to be stored and the position accuracy is not significantly improved. Moreover, map matching has been combined with GNSS measurements and estimates from the GNSS aided INS. The Viterbi algorithm is used to output the the road segment identification numbers of the most likely path and then the estimates are matched to the closest position of these roads. A suggested solution to acquire reliable tracking with high accuracy in all environments is to run the GNSS aided INS in real-time in the vehicle and simultaneously send the horizontal position coordinates to a back office where map information is kept and map matching is performed.