To see the other types of publications on this topic, follow the link: The Viterbi algorithm.
Dissertations / Theses on the topic 'The Viterbi algorithm'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'The Viterbi algorithm.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Dobson, Jonathan M. "ASIC implementations of the Viterbi Algorithm." Thesis, University of Edinburgh, 1999. http://hdl.handle.net/1842/13669.
Full textAbstract:
The Viterbi Algorithm is a popular method for decoding convolutional codes, receiving signals in the presence of intersymbol-interference, and channel equalization. In 1981 the European Telecommunications Administration (CEPT) created the Groupe Special Mobile (GSM) Committee to devise a unified pan-European digital mobile telephone standard. The proposed GSM receiver structure brings together Viterbi decoding and equilization. This thesis presents three VLSI designs of the Viterbi Algorithm with specific attention paid to the use of such modules within a GSM receiver. The first design uses a technique known as redundant number systems to produce a high speed decoder. The second design uses complementary pass-transistor logic to produce a low-power channel equalizer. The third design is a low area serial equalizer. In describing the three designs, redundant number systems and complementary pass-transistor logic are examined. It is shown that while redundant number systems can offer significant speed advantages over twos complement binary, there are other representations that can perform equally well, if not better. It will also be shown that complementary pass-transistor logic can offer a small improvement for VLSI circuits in terms of power consumption.
2
Dujari, Rajeev. "Parallel Viterbi search algorithm for speech recognition." Thesis, Massachusetts Institute of Technology, 1992. http://hdl.handle.net/1721.1/13111.
Full text
3
Ju, Zilong. "Fast Viterbi Decoder Algorithms for Multi-Core System." Thesis, KTH, Signalbehandling, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-98779.
Full textAbstract:
In this thesis, fast Viterbi Decoder algorithms for a multi-core system are studied. New parallel Viterbi algorithms for decoding convolutional codes are proposed based on tail biting trellises. The performances of the new algorithms are first evaluated by MATLAB and then Eagle (E-UTRA algorithms for LTE) link level simulations where the optimal parameter settings are obtained based on various simulations. One of the algorithms is proposed for implementation in the product due to its good BLER performance and low implementation complexity. The new parallel algorithm is then implemented on target DSPs for Ericsson internal multi-core system to decode the PUSCH (Physical Uplink Shared Channel) CQI (Channel Quality Indicator) in LTE (Long Term Evolution). And the performance of the new algorithm in the real multi-core system is compared against the current implementation regarding both cycle and memory consumption. As a fast decoder, the proposed parallel Viterbi decoder is computationally efficient which reduces significantly the decoding latency and solves memory limitation problems on DSP.
4
Yamazato, Takaya, Iwao Sasase, and Shinsaku Mori. "A New Viterbi Algorithm with Adaptive Path Reduction Method." IEICE, 1993. http://hdl.handle.net/2237/7839.
Full text
5
Cui, Xiaoxiao. "MODIFIED VITERBI DECODING ALGORITHM FOR CIRCULAR TRELLIS-CODED MODULATION." Ohio University / OhioLINK, 2000. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1171649965.
Full text
6
Werling, Brett W. "A VHDL Implementation of the Soft Output Viterbi Algorithm." International Foundation for Telemetering, 2010. http://hdl.handle.net/10150/604276.
Full textAbstract:
ITC/USA 2010 Conference Proceedings / The Forty-Sixth Annual International Telemetering Conference and Technical Exhibition / October 25-28, 2010 / Town and Country Resort & Convention Center, San Diego, California<br>In this paper we present a VHDL implementation of the soft output Viterbi algorithm (SOVA). We discuss the usefulness of the SOVA in a serially concatenated convolutional code (SCCC) system. We explore various hardware design decisions along with their implications. Finally, we compare the simulated performance of the hardware implementation to a software reference model over an additive white Gaussian noise (AWGN) channel for several bit widths and traceback window lengths.
7
Bull, Tristan. "Implementation of the Viterbi Algorithm Using Functional Programming Languages." International Foundation for Telemetering, 2009. http://hdl.handle.net/10150/606012.
Full textAbstract:
ITC/USA 2009 Conference Proceedings / The Forty-Fifth Annual International Telemetering Conference and Technical Exhibition / October 26-29, 2009 / Riviera Hotel & Convention Center, Las Vegas, Nevada<br>In this paper, we present an implementation of the Viterbi algorithm using the functional programming language Haskell. We begin with a description of the functional implementation of the algorithm. Included are aspects of functional programming that must be considered when implementing the Viterbi algorithm as well as properties of Haskell that can be used to simplify or optimize the algorithm. Finally, we evaluate the performance of the Viterbi algorithm implemented in Haskell.
8
Alam, Daniel. "Coded SOQPSK-TG Using the Soft Output Viterbi Algorithm." International Foundation for Telemetering, 2009. http://hdl.handle.net/10150/606121.
Full textAbstract:
ITC/USA 2009 Conference Proceedings / The Forty-Fifth Annual International Telemetering Conference and Technical Exhibition / October 26-29, 2009 / Riviera Hotel & Convention Center, Las Vegas, Nevada<br>In this paper we present a system-level description of a serially concatenated convolutional coding scheme for shaped offset quadrature phase shift keying, telemetry group (SOQPSK-TG). Our paper describes the operation of various system modules. In addition, implementation details and references for each module in the system are provided. The modified Soft Output Viterbi Algorithm (SOVA) is employed for decoding inner and outer convolutional codes. The modified SOVA possess strong performance and low-complexity cost. The comparison of the modified (SOVA) and Max-Log-maximum a posteriori (MAP) decoding algorithm is presented. The SOVA after a simple modification displays the same performance as Max-Log-MAP algorithm, which is demonstrated by the simulation results. The advantage of the simple implementation of the modified SOVA makes it superior to Max-Log-MAP for our purposes.
9
Lavin, Christopher. "THE IMPLEMENTATION OF AN IRREGULAR VITERBI TRELLIS DECODER." International Foundation for Telemetering, 2007. http://hdl.handle.net/10150/604495.
Full textAbstract:
ITC/USA 2007 Conference Proceedings / The Forty-Third Annual International Telemetering Conference and Technical Exhibition / October 22-25, 2007 / Riviera Hotel & Convention Center, Las Vegas, Nevada<br>The Viterbi algorithm has uses for both the decoding of convolutional codes and the detection of
signals distorted by intersymbol interference (ISI). The operation of these processes is
characterized by a trellis. An ARTM Tier-1 space-time coded telemetry receiver required the
use of an irregular Viterbi trellis decoder to solve the dual antenna problem. The nature of the
solution requires the trellis to deviate from conventional trellis structure and become time-varying.
This paper explores the architectural challenges of such a trellis and presents a solution
using a modified systolic array allowing the trellis to be realized in hardware.
10
Shanker, M. Ravi. "A parallel implementation of the A*-Viterbi Algorithm for speech recognition /." Thesis, McGill University, 1993. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=69682.
Full textAbstract:
The problem of speech recognition is one that lends itself to parallelization. A common method used for speech recognition is the Viterbi algorithm. Unfortunately, this method is computationally expensive for large vocabularies. A new two pass method has been proposed, using the Viterbi algorithm as the first pass and the A$ sp *$ algorithm as the second, making use of the results of the Viterbi algorithm. Both these algorithms can be made faster by parallelizing them.<br>This thesis report describes the design and implementation of a parallel version of these algorithms on a BBN Butterfly multi-processor machine, and it also presents the outcome of the parallelization. It was observed that the parallel version of the Viterbi algorithm ran 8 times faster than the sequential version. This was observed for the recognition of both short words and long words. The A$ sp *$ algorithm, however, displayed different behaviour for short words as compared to long words. With a short word, the parallel version of the A$ sp *$ algorithm ran slightly slower than the sequential version; for a long word, it ran considerably faster than the sequential version--it was observed to run as much as 150 times faster.<br>This thesis comments on the results thus obtained, and attempts to explain the behaviour of the different parallel implementations.
11
Nguyen, Hoang. "The expectation-maximization Viterbi algorithm for blind channel identification and equalization /." For electronic version search Digital dissertations database. Restricted to UC campuses. Access is free to UC campus dissertations, 2003. http://uclibs.org/PID/11984.
Full text
12
Beale, Martin Warwick. "Reduced state decoding of convolutional codes." Thesis, University of Cambridge, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.320013.
Full text
13
Scott, Chuck, Howard Nussbaum, and Scott Shaffer. "Magellan Recorder Data Recovery Algorithms." International Foundation for Telemetering, 1993. http://hdl.handle.net/10150/611897.
Full textAbstract:
International Telemetering Conference Proceedings / October 25-28, 1993 / Riviera Hotel and Convention Center, Las Vegas, Nevada<br>This paper describes algorithms implemented by the Magellan High Rate Processor to recover radar data corrupted by the failure of an onboard tape recorder that dropped bits. For data with error correction coding, an algorithm was developed that decodes data in the presence of bit errors and missing bits. For the SAR data, the algorithm takes advantage of properties in SAR data to locate corrupted bits and reduce there effects on downstream processing. The algorithms rely on communication approaches, including an efficient tree search and the Viterbi algorithm to maintain the required throughput rate.
14
Wu, Lan. "Multi-view hockey tracking with trajectory smoothing and camera selection." Thesis, University of British Columbia, 2008. http://hdl.handle.net/2429/2402.
Full textAbstract:
We address the problem of multi-view multi-target tracking using multiple stationary cameras in the application of hockey tracking and test the approach with data from two cameras. The system is based on the previous work by Okuma et al. [50]. We replace AdaBoost detection with blob detection in both image coordinate systems after background subtraction. The sets of blob-detection results are then mapped to the rink coordinate system using a homography transformation. These observations are further merged into the final detection result which will be incorporated into the particle filter. In addition, we extend the particle filter to use multiple observation models, each corresponding to a view. An observation likelihood and a reference color model are also maintained for each player in each view and are updated only when the player is not occluded in that view. As a result of the expanded coverage range and multiple perspectives in the multi-view tracking, even when the target is occluded in one view, it still can be tracked as long as it is visible from another view. The multi-view tracking data are further processed by trajectory smoothing using the Maximum a posteriori smoother. Finally, automatic camera selection is performed using the Hidden Markov Model to create personalized video programs.
15
DESAI, PRANAY A. "SEQUENCE CLASSIFICATION USING HIDDEN MARKOV MODELS." University of Cincinnati / OhioLINK, 2005. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1116250500.
Full text
16
Sozen, Serkan. "A Viterbi Decoder Using System C For Area Efficient Vlsi Implementation." Master's thesis, METU, 2006. http://etd.lib.metu.edu.tr/upload/12607567/index.pdf.
Full textAbstract:
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.
17
Urbiš, Oldřich. "Algoritmy rozpoznávání řeči na FPGA/DSP." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2008. http://www.nusl.cz/ntk/nusl-235943.
Full textAbstract:
This master's thesis deals with design of speech recognition algorithms with consideration of target technology, which is platform combinating digital signal processing and field programmable gate array. Algorithms for speech recognition includes: feature extraction of Melfrequency cepstral coefficients, hidden Markov models and their evaluation by Viterbi algorithm.
18
Amaral, Marcos Almeida do. "Estimação de sinais caóticos com aplicação em sistemas de comunicação." Universidade Presbiteriana Mackenzie, 2011. http://tede.mackenzie.br/jspui/handle/tede/1403.
Full textAbstract:
Made available in DSpace on 2016-03-15T19:37:36Z (GMT). No. of bitstreams: 1
Marcos Almeida do Amaral.pdf: 924821 bytes, checksum: 9688a401b13ea6bec24b0af1024abf72 (MD5)
Previous issue date: 2011-02-01<br>Communications have achieved great development on several fronts over the years. Among these, the communication using chaotic signals has been object of growing interest among researchers due to the characteristics of spread spectrum and hard detection. However these techniques still have inferior performance in comparison to conventional methods in non-ideal channels. To contribute do the solution of this problem, statistical estimation algorithms have been applied to the detection of the transmitted signal. The objective of this thesis is to study a communication system using chaotic carriers and reception with maximum likelihood (ML-CSK - Maximum Likelihood Chaos Shift Keying). For this, the application of Viterbi algorithm in chaotic modulation signals is investigated. As the previously proposed algorithms offer only good performance to signals generated by maps that present well-behaved probability density, a new technique was designed based on analysis of the map characteristics, obtained numerically through a training vector. The results of performed simulations assure the applicability and the good performance of the proposed innovations.<br>As comunicações têm alcançado grande desenvolvimento em várias frentes ao longo dos anos. Dentre estas, a comunicação utilizando sinais caóticos vêm sendo objeto de crescente interesse por parte dos pesquisadores devido às características de espalhamento espectral e difícil detecção. Entretanto estas técnicas ainda apresentam um desempenho inferior em comparação com os métodos convencionais em canais não ideais. Para contornar este problema, algoritmos estatísticos de estimação vêm sendo aplicados na detecção dos sinais transmitidos. O objetivo desta dissertação é estudar um sistema de comunicação utilizando portadoras caóticas e recepção com máxima verossimilhança (ML-CSK - Maximum Likelihood Chaos Shift Keying). Para isto, a aplicação do algoritmo de Viterbi em sistemas de modulação por sinais caóticos é investigada. A partir da constatação de que os algoritmos propostos anteriormente só apresentam bom desempenho para sinais gerados por mapas que apresentam densidade de probabilidade bem comportada, uma nova técnica foi concebida baseada no levantamento das características do mapa, obtidas numericamente através de um vetor de treinamento. Os resultados das simulações executadas atestam a aplicabilidade e o bom desempenho das inovações propostas.
19
McGinty, Nigel, and nigel mcginty@defence gov au. "Reduced Complexity Equalization for Data Communication." The Australian National University. Research School of Information Sciences and Engineering, 1998. http://thesis.anu.edu.au./public/adt-ANU20050602.122741.
Full textAbstract:
Optimal decision directed equalization techniques for time dispersive communication channels are often too complex to implement. This thesis considers reduced complexity decision directed equalization that lowers complexity demands yet retains close to optimal performance. The first part of this dissertation consists of three reduced complexity algorithms based on the Viterbi Algorithm (VA) which are: the Parallel Trellis VA (PTVA); Time Reverse Reduced State Sequence Estimation (TR-RSSE); and Forward-Backward State Sequence Detection (FBSSD). The second part of the thesis considers structural modifications of the Decision Feedback Equalizer (DFE), which is a special derivative of the VA, specifically, optimal vector quantization for fractionally spaced DFEs, and extended stability regions for baud spaced DFEs using passivity analysis are investigated.¶
For a special class of sparse channels the VA can be decomposed over a number of independent parallel trellises. This decomposition will be called the Parallel Trellis Viterbi Algorithm and can have lower complexity than the VA yet it retains optimal performance. By relaxing strict sparseness constraints on the channel a sub-optimal approach is proposed which keeps complexity low and obtains good performance.¶
Reduced State Sequence Estimation (RSSE) is a popular technique to reduce complexity. However, its deficiency can be the inability to adequately equalize non-minimum phase channels. For channels that have energy peaks in the tail of the impulse response (post-cursor dominant) RSSE's complexity must be close to the VA or performance will be poor. Using a property of the VA which makes it invariant to channel reversal, TR-RSSE is proposed to extend application of RSSE to post-cursor dominant channels.¶
To further extend the class of channels suitable for RSSE type processing, FBSSD is suggested. This uses a two pass processing method, and is suited to channels that have low energy pre and post-cursor. The first pass generates preliminary estimates used in the second pass to aid the decision process. FBSSD can range from RSSE to TR-RSSE depending on parameter settings.¶
The DFE is obtained when the complexity of RSSE is minimized. Two characterizing properties of the DFE, which are addressed in this thesis, are feedback and quantization. A novel fractionally spaced (FS) DFE structure is presented which allows the quantizer to be generalized relative to the quantizer used in conventional FS-DFEs. The quantizer can be designed according to a maximum a posteriori criterion which takes into account a priori statistical knowledge of error occurrences. A radically different quantizer can be obtained using this technique which can result in significant performance improvements.¶
Due to the feedback nature of the DFE a form of stability can be considered. After a decision error occurs, a stable DFE will, after some finite time and in the absence of noise, operate error free. Passivity analysis provides sufficient conditions to determine a class of channels which insures a DFE will be stable. Under conditions of short channels and small modulation alphabets, it is proposed that conventional passivity analysis can be extended to account for varying operator gains, leading to weaker sufficient conditions for stability (larger class of channels).
20
Tsai, Kuang, and Gee L. Lui. "BINARY GMSK: CHARACTERISTICS AND PERFORMANCE." International Foundation for Telemetering, 1999. http://hdl.handle.net/10150/608731.
Full textAbstract:
International Telemetering Conference Proceedings / October 25-28, 1999 / Riviera Hotel and Convention Center, Las Vegas, Nevada<br>Gaussian Minimum Shift Keying (GMSK) is a form of Continuous Phase Modulation (CPM) whose spectral occupancy can be easily tailored to the available channel bandwidth by a suitable choice of signal parameters. The constant envelope of the GMSK signal enables it to corporate with saturated power amplifier without the spectral re-growth problem. This paper provides a quantitative synopsis of binary GMSK signals in terms of their bandwidth occupancy and coherent demodulation performance. A detailed account of how to demodulate such signals using the Viterbi Algorithm (VA) is given, along with analytical power spectral density (PSD) and computer simulated bit-error-rate (BER) results for various signal BT products. The effect of adjacent channel interference (ACI) is also quantified. Ideal synchronization for both symbol time and carrier phase is assumed.
21
Mohammad, Maruf H. "Blind Acquisition of Short Burst with Per-Survivor Processing (PSP)." Thesis, Virginia Tech, 2002. http://hdl.handle.net/10919/46193.
Full textAbstract:
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.<br>Master of Science
22
Zelenanska, Alexandra. "Processi markoviani nascosti." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amslaurea.unibo.it/8704/.
Full textAbstract:
We introduce the notation of Markov chains and their properties, and give the definition of ergodic, irreducible and aperiodic chains with correspective examples. Then, the definition of hidden Markov models is given and their characteristics are examined. We formulate three basic problems regarding the hidden Markov models and discuss the solution of two of them - the Viterbi algorithm and the forward-backward algorithm.
23
Ejnestrand, Ida, and Linnéa Jakobsson. "Object Tracking based on Eye Tracking Data : A comparison with a state-of-the-art video tracker." Thesis, Linköpings universitet, Datorseende, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-166007.
Full textAbstract:
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.
24
Noel, D. Peter (David Peter) Carleton University Dissertation Engineering Electrical. "The architecture development and design considerations of a high- speed, single chip, CMOS convolutional decoder based on a modification of the Viterbi algorithm." Ottawa, 1990.
Find full text
25
Billah, Md Munibun. "Generalization of Signal Point Target Code." DigitalCommons@USU, 2019. https://digitalcommons.usu.edu/etd/7586.
Full textAbstract:
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.
26
Fang, Juing. "Décodage pondère des codes en blocs et quelques sujets sur la complexité du décodage." Paris, ENST, 1987. http://www.theses.fr/1987ENST0005.
Full textAbstract:
Etude de la compléxité théorique du décodage des codes en blocs à travers une famille d'algorithmes basée sur le principe d'optimisation combinatoire. Puis on aborde un algorithme parallèle de décodage algébrique dont la complexitré est liée au niveau de bruit du canal. Enfin on introduit un algorithme de Viterbi pour les applications de traitement en chaînes.
27
Sezginer, Serdar. "Symbol Synchronization For Msk Signals Based On Matched Filtering." Master's thesis, METU, 2003. http://etd.lib.metu.edu.tr/upload/1057348/index.pdf.
Full textAbstract:
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.
28
Ter-Hovhannisyan, Vardges. "Unsupervised and semi-supervised training methods for eukaryotic gene prediction." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/26645.
Full textAbstract:
Thesis (Ph.D)--Biology, Georgia Institute of Technology, 2009.<br>Committee Chair: Mark Borodovky; Committee Member: Jung H. Choi; Committee Member: King Jordan; Committee Member: Leonid Bunimovich; Committee Member: Yury Chernoff. Part of the SMARTech Electronic Thesis and Dissertation Collection.
29
Homelius, Marcus. "Tracking of Ground Vehicles : Evaluation of Tracking Performance Using Different Sensors and Filtering Techniques." Thesis, Linköpings universitet, Reglerteknik, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-148432.
Full textAbstract:
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.
30
Tomášek, Pavel. "Kdy kdo mluví?" Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2011. http://www.nusl.cz/ntk/nusl-236946.
Full textAbstract:
This work aims at a task of speaker diarization. The goal is to implement a system which is able to decide "who spoke when". Particular components of implementation are described. The main parts are feature extraction, voice activity detection, speaker segmentation and clustering and finally also postprocessing. This work also contains results of implemented system on test data including a description of evaluation. The test data comes from the NIST RT Evaluation 2005 - 2007 and the lowest error rate for this dataset is 18.52% DER. Results are compared with diarization system implemented by Marijn Huijbregts from The Netherlands, who worked on the same data in 2009 and reached 12.91% DER.
31
Zeydan, Engin. "Channel Phase And Data Estimation In Slowly Fading Frequency Nonselective Channels." Master's thesis, METU, 2006. http://etd.lib.metu.edu.tr/upload/12607419/index.pdf.
Full textAbstract:
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.
32
Yu, Junyi. "A Layered Two-Step Hidden Markov Model Positioning Method for Underground Mine Environment Based on Wi-Fi Signals." Thesis, Mittuniversitetet, Avdelningen för informations- och kommunikationssystem, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:miun:diva-26328.
Full textAbstract:
The safety of miners is of interest to all countries. In the event of a coal mine disaster, how to locate the miners remains the biggest and most urgent issue. The aim of this study is to propose a precise positioning method for underground mine environments to a low cost and with acceptable accuracy. During the research work, in-depth learning and analysis of current geolocation methods for indoor areas have been carried out: advantages, disadvantages and the level of suitability of each method for mine environment have been presented. A layered two-step Hidden Markov Model has been proposed to simulate human walking in underground mine environments and an improved Viterbi algorithm suitable for the model has been implemented. The result of the positioning accuracy is quite satisfying compared to other positioning methods in the same category. A small modification to the proposed model has been illustrated in the future work which makes it more suitable for different situations rather than that limited by assumptions. The proposed positioning method can be claimed to be quite suitable for underground mine environments to a low cost and with acceptable accuracy.
33
Pertsinidou, Christina Elisavet. "Stochastic models for the estimation of the seismic hazard." Thesis, Compiègne, 2017. http://www.theses.fr/2017COMP2342.
Full textAbstract:
Dans le premier chapitre, la notion d'évaluation des risques sismiques est définie et les caractéristiques sismotectoniques de la région d'étude sont brièvement présentés. Un examen rigoureux des modèles stochastiques, appliqués au domaine de la sismologie est fourni. Dans le chapitre 2, différents modèles semi-Markoviens sont développés pour étudier la sismicité des îles Ioniennes centrales ainsi que le Nord de la mer Egée (Grèce). Les quantités telles que le noyau semi-Markovien et les probabilités de destination sont évaluées, en considérant que les temps de séjour suivent les distributions géométrique, discrète Weibull et Pareto. Des résultats utiles sont obtenus pour l'estimation de la sismicité. Dans le troisième chapitre un nouvel algorithme de Viterbi pour les modèles semi-Markoviens cachés est construit, dont la complexité est une fonction linéaire du nombre d'observations et une fonction quadratique du nombre d'états cachés, la plus basse existante dans la littérature. Une extension de ce nouvel algorithme est développée pour le cas où une observation dépend de l'état caché correspondant, mais aussi de l'observation précédente (cas SM1-M1). Dans le chapitre 4 les modèles semi-Markoviens cachés sont appliquées pour étudier la sismicité du Nord et du Sud de la mer Égée. La séquence d'observation est constituée des magnitudes et des positions d’un tremblement de terre et le nouvel algorithme de Viterbi est mis en œuvre afin de décoder les niveaux des tensions cachés qui sont responsables pour la sismogenèse. Les phases précurseurs (variations des tensions cachées) ont été détectées en avertissant qu’un tremblement de terre pourrait se produire. Ce résultat est vérifié pour 70 sur 88 cas (le score optimal). Les temps de séjour du processus caché étaient supposés suivre les distributions Poisson, logarithmique ou binomiale négative, tandis que les niveaux de tensions cachés ont été classés en 2, 3 ou 4 états. Les modèles de Markov caché ont également été adaptés sans présenter des résultats intéressants concernant les phases précurseurs. Dans le chapitre 5 un algorithme de Viterbi généralisé pour les modèles semi-Markoviens cachés, est construit dans le sens que les transitions au même état caché sont autorisées et peuvent également être décodées. De plus, une extension de cet algorithme généralisé dans le contexte SM1-M1 est présentée. Dans le chapitre 6 nous modifions de manière convenable le modèle Cramér-Lundberg y compris des sinistres négatifs et positifs, afin de décrire l'évolution avec le temps des changements de contraintes de Coulomb (valeurs ΔCFF) calculées pour sept épicentres (M ≥ 6) du Nord de la mer Egée. Formules pour les probabilités de ruine sont définies sous une forme générale. Corollaires sont également formulés pour la distribution exponentielle et Pareto. L'objectif est de mettre en lumière la question suivante qui pose la problématique dans la Sismologie: Au cours d'une année pourquoi un tremblement de terre s’est produit dans une position précise et pas dans une autre position, aux régions sismotectoniquement homogènes ayant valeurs ΔCFF positives. Les résultats montrent que les nouvelles formules de probabilité peuvent contribuer à répondre au problème susmentionné<br>In the first chapter the definition of the seismic hazard assessment is provided, the seismotectonic features of the study areas are briefly presented and the already existing mathematical models applied in the field of Seismology are thoroughly reviewed. In chapter 2, different semi-Markov models are developed for studying the seismicity of the areas of the central Ionian Islands and the North Aegean Sea (Greece). Quantities such as the kernel and the destination probabilities are evaluated, considering geometric, discrete-Weibull and Pareto distributed sojourn times. Useful results are obtained for forecasting purposes. In the third chapter a new Viterbi algorithm for hidden semi-Markov models is developed, whose complexity is a linear function of the number of observations and a quadratic function of the number of hidden states, the lowest existing in the literature. Furthermore, an extension of this new algorithm is introduced for the case that an observation depends on the corresponding hidden state but also on the previous observation (SM1-M1 case). In chapter 4, different hidden semi-Markov models (HSMMs) are applied for the study of the North and South Aegean Sea. The earthquake magnitudes and locations comprise the observation sequence and the new Viterbi algorithm is implemented in order to decode the hidden stress field associated with seismogenesis. Precursory phases (variations of the hidden stress field) were detected warning for an anticipated earthquake occurrence for 70 out of 88 cases (the optimal model’s score). The sojourn times of the hidden process were assumed to follow Poisson, logarithmic or negative binomial distributions, whereas the hidden stress levels were classified into 2, 3 or 4 states. HMMs were also adapted without presenting significant results as for the precursory phases. In chapter 5 a generalized Viterbi algorithm for HSMMs is constructed in the sense that now transitions to the same hidden state are allowed and can also be decoded. Furthermore, an extension of this generalized algorithm in the SM1-M1 context is given. In chapter 6 we modify adequately the Cramér-Lundberg model considering negative and positive claims, in order to describe the evolution in time of the Coulomb failure function changes (ΔCFF values) computed at the locations of seven strong (M ≥ 6) earthquakes of the North Aegean Sea. Ruin probability formulas are derived and proved in a general form. Corollaries are also formulated for the exponential and the Pareto distribution. The aim is to shed light to the following problem posed by the seismologists: During a specific year why did an earthquake occur at a specific location and not at another location in seismotectonically homogeneous areas with positive ΔCFF values (stress enhanced areas). The results demonstrate that the new probability formulas can contribute in answering the aforementioned question
34
Peh, Lin Kiat. "Performance comparison of two implementations of TCM for QAM." Thesis, Monterey, California. Naval Postgraduate School, 2007. http://hdl.handle.net/10945/55202.
Full textAbstract:
Approved for public release; distribution is unlimited.<br>Trellis-Coded Modulation (TCM) is employed with quadrature amplitude modulation (QAM) to provide error correction coding with no expense in bandwidth. There are two common implementations of TCM, namely pragmatic TCM and Ungerboeck TCM. Both schemes employ Viterbi algorithms for decoding but have different code construction. This thesis investigates and compares the performance of pragmatic TCM and Ungerboeck TCM by implementing the Viterbi decoding algorithm for both schemes with 16-QAM and 64-QAM. Both pragmatic and Ungerboeck TCM with six memory elements are considered. Simulations were carried out for both pragmatic and Ungerboeck TCM to evaluate their respective performance. The simulations were done using Matlab software, and an additive white Gaussian noise channel was assumed. The objective was to ascertain that pragmatic TCM, with its reduced-complexity decoding, is more suitable to adaptive modulation than Ungerboeck TCM.<br>Civilian
35
Ledet, Jeffrey H. "Simulation and Performance Evaluation of Algorithms for Unmanned Aircraft Conflict Detection and Resolution." ScholarWorks@UNO, 2016. http://scholarworks.uno.edu/td/2168.
Full textAbstract:
The problem of aircraft conflict detection and resolution (CDR) in uncertainty is addressed in this thesis. The main goal in CDR is to provide safety for the aircraft while minimizing their fuel consumption and flight delays. In reality, a high degree of uncertainty can exist in certain aircraft-aircraft encounters especially in cases where aircraft do not have the capabilities to communicate with each other. Through the use of a probabilistic approach and a multiple model (MM) trajectory information processing framework, this uncertainty can be effectively handled. For conflict detection, a randomized Monte Carlo (MC) algorithm is used to accurately detect conflicts, and, if a conflict is detected, a conflict resolution algorithm is run that utilizes a sequential list Viterbi algorithm. This thesis presents the MM CDR method and a comprehensive MC simulation and performance evaluation study that demonstrates its capabilities and efficiency.
36
Král, Tomáš. "Fixed-point implementace rozpoznávače řeči." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2007. http://www.nusl.cz/ntk/nusl-412781.
Full textAbstract:
Master thesis is related to the problematics of automatic speech recognition on systems with restricted hardware resources - embedded systems. The object of this work was to design and implement speech recognition system on embedded systems, that do not contain floating-point processing units. First objective was to choose proper hardware architecture. Based on the knowledge of available HW resources, the recognition system design was made. During the system development, optimalization was made on constituent elements so they could be mounted on chosen HW. The result of the the project is successful recognition of Czech numerals on embedded system.
37
Pelchat, Émilie. "Décodage Viterbi Dégénéré." Mémoire, Université de Sherbrooke, 2013. http://hdl.handle.net/11143/6595.
Full textAbstract:
La correction d'erreur fera partie intégrante de toute technologie d'information quantique. Diverses méthodes de correction d'erreurs quantiques ont par conséquent été élaborées pour pallier les erreurs inévitables qui proviennent de la manipulation des qubits ainsi que de leur interaction inévitable avec l'environnement. Parmi les familles de codes de correction d'erreurs se trouvent les codes convolutifs, dont l'utilité envisagée est surtout pour protéger l'information quantique envoyée à travers un canal de communication bruyant. La méthode de décodage des codes convolutifs utilise des algorithmes d'estimation d'erreur basés sur un principe de maximum de vraisemblance. L'algorithme de Viterbi permet de déterminer ce maximum de vraisemblance de façon efficace. Cette méthode permet de trouver le mot code le plus probable et ce en utilisant des outils telle décodage par trellis. De plus, cet algorithme a une complexité linéaire avec le nombre de qubits encodés. Ce mémoire porte sur l'effet de la dégénérescence sur le décodage Viterbi. La dégénérescence est une propriété de lamécanique quantique ne possédant aucun analogue classique par laquelle des corrections distinctes peuvent corriger une erreur donnée. Les versions précédentes de décodage quantique suivant l'algorithme de Viterbi étaient sous-optimales parce qu'elles ne tenaient pas compte de la dégénérescence. La réalisation principale de ce mémoire est la conception d'un algorithme de décodage de Viterbi qui tient compte des erreurs dégénérées et nous les testons par des simulations numériques. Ces simulations démontrent qu'il y a effectivement un avantage à utiliser le décodeur Viterbi qui tient compte de la dégénérescence.
38
Wilhelmsson, Anna, and Sofia Bedoire. "Driving Behavior Prediction by Training a Hidden Markov Model." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-291656.
Full textAbstract:
Introducing automated vehicles in to traffic withhuman drivers, human behavior prediction is essential to obtainoperation safety. In this study, a human behavior estimationmodel has been developed. The estimations are based on aHidden Markov Model (HMM) using observations to determinethe driving style of surrounding vehicles. The model is trainedusing two different methods: Baum Welch training and Viterbitraining to improve the performance. Both training methods areevaluated by looking at time complexity and convergence. Themodel is implemented with and without training and tested fordifferent driving styles. Results show that training is essentialfor accurate human behavior prediction. Viterbi training is fasterbut more noise sensitive compared to Baum Welch training. Also,Viterbi training produces good results if training data reflects oncurrently observed driver, which is not always the case. BaumWelch training is more robust in such situations. Lastly, BaumWelch training is recommended to obtain operation safety whenintroducing automated vehicles into traffic.<br>N ̈ar automatiserade fordon introduceras itrafiken och beh ̈over interagera med m ̈anskliga f ̈orare ̈ar det vik-tigt att kunna f ̈orutsp ̊a m ̈anskligt beteende. Detta f ̈or att kunnaerh ̊alla en s ̈akrare trafiksituation. I denna studie har en modellsom estimerar m ̈anskligt beteende utvecklats. Estimeringarna ̈ar baserade p ̊a en Hidden Markov Model d ̈ar observationeranv ̈ands f ̈or att best ̈amma k ̈orstil hos omgivande fordon itrafiken. Modellen tr ̈anas med tv ̊a olika metoder: Baum Welchtr ̈aning och Viterbi tr ̈aning f ̈or att f ̈orb ̈attra modellens prestanda.Tr ̈aningsmetoderna utv ̈arderas sedan genom att analysera derastidskomplexitet och konvergens. Modellen ̈ar implementerad medoch utan tr ̈aning och testad f ̈or olika k ̈orstilar. Erh ̊allna resultatvisar att tr ̈aning ̈ar viktigt f ̈or att kunna f ̈orutsp ̊a m ̈anskligtbeteende korrekt. Viterbi tr ̈aning ̈ar snabbare men mer k ̈ansligf ̈or brus i j ̈amf ̈orelse med Baum Welch tr ̈aning. Viterbi tr ̈aningger ̈aven en bra estimering i de fall d ̊a observerad tr ̈aningsdataavspeglar f ̈orarens k ̈orstil, vilket inte alltid ̈ar fallet. BaumWelch tr ̈aning ̈ar mer robust i s ̊adana situationer. Slutligenrekommenderas en estimeringsmodell implementerad med BaumWelch tr ̈aning f ̈or att erh ̊alla en s ̈aker k ̈orning d ̊a automatiseradefordon introduceras i trafiken<br>Kandidatexjobb i elektroteknik 2020, KTH, Stockholm
39
Huang, Zhiyong. "Modified Viterbi decoding algorithms for high dimensional trellis coded modulation." Ohio : Ohio University, 2003. http://www.ohiolink.edu/etd/view.cgi?ohiou1175094385.
Full text
40
Saidane, Mohamed. "Modèles à Facteurs Conditionnellement Hétéroscédastiques et à Structure Markovienne Cachée pour les Séries Financières." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2006. http://tel.archives-ouvertes.fr/tel-00089558.
Full textAbstract:
Dans cette thèse nous proposons une nouvelle approche dans le cadre des modèles d'évaluation des actifs financiers permettant de tenir compte de deux aspects fondamentaux qui caractérisent la volatilité latente: co-mouvement des rendements financiers conditionnellement hétéroscédastiques et changement de régime. En combinant les modèles à facteurs conditionnellement hétéroscédastiques avec les modèles de chaîne de Markov cachés, nous dérivons un modèle multivarié localement linéaire et dynamique pour la segmentation et la prévision des séries financières. Nous considérons, plus précisément le cas où les facteurs communs suivent des processus GQARCH univariés. L'algorithme EM que nous avons développé pour l'estimation de maximum de vraisemblance et l'inférence des structures cachées est basé sur une version quasi-optimale du filtre de Kalman combinée avec une approximation de Viterbi. Les résultats obtenus sur des simulations, aussi bien que sur des séries financières sont prometteurs.
41
Ferreira, Nathan. "An Assessment of Available Software Defined Radio Platforms Utilizing Iterative Algorithms." Digital WPI, 2015. https://digitalcommons.wpi.edu/etd-theses/728.
Full textAbstract:
As the demands of communication systems have become more complex and varied, software defined radios (SDR) have become increasingly popular. With behavior that can be modified in software, SDR's provide a highly flexible and configurable development environment. Despite its programmable behavior, the maximum performance of an SDR is still rooted in its hardware. This limitation and the desire for the use of SDRs in different applications have led to the rise of various pieces of hardware to serve as SDR platforms. These platforms vary in aspects such as their performance limitations, implementation details, and cost. In this way the choice of SDR platform is not solely based on the cost of the hardware and should be closely examined before making a final decision. This thesis examines the various SDR platform families available on the market today and compares the advantages and disadvantages present for each during development. As many different types of hardware can be considered an option to successfully implement an SDR, this thesis specifically focuses on general purpose processors, system on chip, and field-programmable gate array implementations. When examining these SDR families, the Freescale BSC9131 is chosen to represent the system on chip implementation, while the Nutaq PicoSDR 2x2 Embedded with Virtex6 SX315 is used for the remaining two options. In order to test each of these platforms, a Viterbi algorithm is implemented on each and the performance measured. This performance measurement considers both how quickly the platform is able to perform the decoding, as well as its bit error rate performance in order to ascertain the implementations' accuracy. Other factors considered when comparing each platform are its flexibility and the amount of options available for development. After testing, the details of each implementation are discussed and guidelines for choosing a platform are suggested.
42
Giraldo, Juan Fernando Eusse. "Implementação em hardware de um acelerador hibrido viterbi-plan7/algoritmo das divergências para comparação de proteinas." reponame:Repositório Institucional da UnB, 2009. http://repositorio.unb.br/handle/10482/8240.
Full textAbstract:
Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2009.<br>Submitted by Jaqueline Ferreira de Souza (jaquefs.braz@gmail.com) on 2011-06-06T14:24:38Z
No. of bitstreams: 1
2009_JuanFernandoEusseGiraldo.pdf: 4745967 bytes, checksum: 76224827c593ebb7c15bc3993fa53665 (MD5)<br>Approved for entry into archive by Jaqueline Ferreira de Souza(jaquefs.braz@gmail.com) on 2011-06-06T14:25:37Z (GMT) No. of bitstreams: 1
2009_JuanFernandoEusseGiraldo.pdf: 4745967 bytes, checksum: 76224827c593ebb7c15bc3993fa53665 (MD5)<br>Made available in DSpace on 2011-06-06T14:25:37Z (GMT). No. of bitstreams: 1
2009_JuanFernandoEusseGiraldo.pdf: 4745967 bytes, checksum: 76224827c593ebb7c15bc3993fa53665 (MD5)<br>Os Modelos Ocultos de Markov (HMM - Hidden Markov Models) constituem uma poderosa ferramenta para mapeamento e organização de proteínas, uma vez que permitem reconhecer estruturas altamente representativas e unidades funcionais dentro das cadeias de aminoácidos que as conformam. O Viterbi é um dos principais algoritmos para comparação e identificação de proteínas (sequências de aminoácidos) baseados em HMM, e é implementado dentro do software livre HMMER [1][2], muito utilizado na comunidade científica. Nos últimos anos, devido ao crescimento exponencial das bases de dados que armazenam proteínas, surge a necessidade de acelerar a execução do software para reduzir os tempos de processamento dos algoritmos de comparação. Neste trabalho de mestrado, é realizada a aceleração do software HMMER para alinhamento de sequências biológicas através da implementação de um acelerador em hardware. O acelerador proposto utiliza um novo algoritmo chamado de Algoritmo das Divergências, o qual permite ao sistema completo (Hardware+Software) economizar uma grande quantidade de cálculos para gerar os alinhamentos de proteínas. O Hardware produz a medida de similaridade da proteína com o modelo HMM e os índices inicial e final da porção de interesse da sequência de aminoácidos como uma primeira etapa de filtragem. Isto, quando gerado pelo acelerador, significa uma economia de processamento adicional para o software, o qual tem que reprocessar dita região para gerar o alinhamento da sequência com o profileHMM, e contribui com a aceleração da execução do algoritmo. O Acelerador atinge ganhos de até 182x quando comparado com o software não acelerado. Além disso, o trabalho propõe uma nova medida para a comparação do desempenho e realiza medições exatas acerca da aceleração atingida ao integrar o acelerador ao fluxo de execução do software. _______________________________________________________________________________ ABSTRACT<br>Hidden Markov Models are a powerful tool for protein organization and identification because they allow identifying and classifying highly representative structures and functional units inside the amino acid chains that form them. The Viterbi algorithm is one of the most used algorithms in protein comparison and identification using Hidden Markov Models, and is implemented inside the open source software HMMER [1][2], which is widely used among the scientific community. Due to the exponential growth in the size of protein databases in the past years, the necessity to accelerate software execution to reduce comparison and search times rose. In this master thesis, a hardware accelerator is implemented in VHDL in order to reduce those processing times in the protein comparison and search processes. The implemented accelerator uses a new algorithm which enables the system (Hardware+Software) to economize processing time by reducing the number of calculations needed to perform a comparison. The accelerator not only produces the similarity score for a sequence when compared against a profileHMM but also produces the parameters to limit the region of the Dynamic Programming Matrices that must be reprocessed to generate the alignment. The implemented accelerator produces a maximum gain of up to 182 times when compared to unaccelerated software. A new performance measurement strategy is introduced in this work, which not only takes into account the acceleration achieved by the hardware, but also the post-processing stages that follows hardware made comparisons.
43
Bajot, Yann. "Etude et spécification d'un coeur de processeur de traitement du signal configurable pour systèmes embarques spécialisés." Paris 6, 2001. http://www.theses.fr/2001PA066262.
Full text
44
Segkos, Michail. "Advanced techniques to improve the performance of OFDM Wireless LAN." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 2004. http://library.nps.navy.mil/uhtbin/hyperion/04Jun%5FSegkos.pdf.
Full textAbstract:
Thesis (M.S. in Electrical Engineering and M.S. in Applied Physics)--Naval Postgraduate School, June 2004.<br>Thesis advisor(s): Tri T. Ha, Brett H. Borden. Includes bibliographical references (p. 107-109). Also available online.
45
Tönder, Nico. "Kanalschätzung, Demodulation und Kanalcodierung in einem FPGA-basierten OFDM-Funkübertragungssystem." Aachen Shaker, 2007. http://d-nb.info/98784976X/04.
Full text
46
Kriouile, Abdelaziz. "La reconnaissance automatique de la parole et les modèles markoviens cachés : modèles du second ordre et distance de Viterbi à optimalité locale." Nancy 1, 1990. http://www.theses.fr/1990NAN10273.
Full textAbstract:
Des travaux intensifs sur la reconnaissance automatique de la parole utilisant les modèles stochastiques ont été réalisés durant les cinq dernières années. L'application des modèles markoviens cachés (HMM) du premier ordre a conduit 0 des résultats impressionnants dans le domaine de la reconnaissance de mots isolés et de la parole continue. Notre objectif était de montrer que l'apport des modèles markoviens cachés à la reconnaissance automatique de la parole est d'autant plus important qu'on mène des réflexions fondamentales sur les modèles markoviens eux-mêmes et sur la façon de les appliquer. Nous avons développé une nouvelle formulation de Baum-Welch et une extension de l'algorithme de Viterbi, qui rendent les modèles markoviens cachés du second ordre efficaces en calcul pour des applications en temps réel. Il y avait une nette amélioration du taux de reconnaissance avec le second ordre. L'extension a des HMM d'ordre plus élevé a été aussi discutée. Enfin, nous avons proposé une nouvelle stratégie d'utilisation de l'algorithme de Viterbi pour la reconnaissance de la parole continue. Elle est basée sur la comparaison d'optimums locaux dans une fenêtre de trames. Cette stratégie, par bloc, a donné de meilleurs résultats que les versions classiques de l'algorithme de Viterbi. Elle permet une interaction avec d'autres processeurs.
47
Baudry, Séverine. "Stratégies de codage de canal pour le tatouage de video." Paris, ENST, 2002. http://www.theses.fr/2002ENST0006.
Full text
48
BENCHIMOL, Isaac Benjamim. "Módulo de Treliça Mínimo Para Códigos Convolucionais." Universidade Federal de Pernambuco, 2012. https://repositorio.ufpe.br/handle/123456789/11180.
Full textAbstract:
Submitted by Eduarda Figueiredo (eduarda.ffigueiredo@ufpe.br) on 2015-03-06T15:14:54Z
No. of bitstreams: 2
Tese - Issac.pdf: 1699623 bytes, checksum: 0b927be3b372049f2ce08bca320becfc (MD5)
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)<br>Made available in DSpace on 2015-03-06T15:14:54Z (GMT). No. of bitstreams: 2
Tese - Issac.pdf: 1699623 bytes, checksum: 0b927be3b372049f2ce08bca320becfc (MD5)
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
Previous issue date: 2012-11-22<br>FAPEAM<br>Esta tese apresenta uma medida de complexidade computacional para códigos
convolucionais adequada para receptores que implementam o algoritmo de Viterbi em
software. A definição desta complexidade envolve a determinação do número de operações aritméticas executadas em um módulo de treliça durante a decodificação, a implementação destas em uma arquitetura de processadores digitais de sinais e a avaliação do respectivo custo computacional de cada operação. Na sequência, esta medida é utilizada para avaliar o impacto do seccionamento do módulo de treliça mínimo. Um conjunto de regras é introduzido para construir padrões de seccionamento que resultem em estruturas de treliça mais compactas e regulares e de mesma complexidade da treliça mínima, constituindo uma alternativa de interesse em aplicações práticas. Finalmente, este trabalho apresenta um método para a construção do módulo de treliça mínimo para codificadores convolucionais sistemáticos recursivos adotados em esquemas turbo. Esta abordagem contribui para a redução da complexidade de decodificação de um decodificador turbo típico operando com
codificadores constituintes de taxas altas. Uma busca de códigos é realizada e obtém-se um refinamento da relação complexidade de decodificação versus distância livre efetiva do código turbo.
49
Zahabi, Mohammad Reza. "Analog approaches in digital receivers." Limoges, 2008. https://aurore.unilim.fr/theses/nxfile/default/42bc3667-aba8-4a87-9fbc-b35358105335/blobholder:0/2008LIMO4009.pdf.
Full textAbstract:
Modern digital receivers need computationally demanding processes that leads to prohibitive complexity and power consumption. The idea of lending analog blocks for realization of digital algorithms can sometimes relaxes the complexity and high power consumption of digital receivers. The issue of analog approaches in digital receivers is studied in this dissertation by concentrating on two areas; analog decoding and front-end processing. For analog decoding, the realizations of some efficient decoders are presented along which our contribution in this area in conjunction with graph theory is proposed. In addition, analog realization of a fast Viterbi decoder is considered. It is shown that there is a very nice analog solution for realization of Add-Compare- Select that plays the central rule in Viterbi algorithm. In order to justify the proposed analog decoders, Cadence package is used. For front-end processing, a novel mixed-signal programmable filter is designed and investigated. The filter is suitable for high-rate communication systems. The proposed filter has analog input and analog sampled outputs. The filter is based on simple CMOS inverter and thus can be integrated efficiently with digital parts<br>Cette thèse propose d’utiliser des circuits analogiques pour réaliser des algorithmes numériques. Le but étant de diminuer la complexité et la puissance consommée et augmenter la vitesse. Deux applications gourmandes en temps de calcul ont été considérées dans cette thèse : le décodeur et le filtre RIF. On propose une structure analogique CMOS très efficace pour un décodeur Viterbi et pour un décodeur sur les graphes de Tanner. Les structures proposées ont été implantées et testées sous l’outil Cadence et démontre la validité de notre démarche. Quant au traitement de signal à l’entrée de décodeurs, un filtre RIF programmable utilisant la technologie CMOS a été étudié, conçu et implanté. La structure proposée est bien adapté aux systèmes de communications haut-débits. Le filtre possède une entrée analogique et une sortie échantillonnée, basée sur un simple inverseur CMOS et peut donc être intégré de manière efficace avec les parties numériques sur une seule puce
50
Charantonis, Anastase Alexandre. "Méthodologie d'inversion de données océaniques de surface pour la reconstitution de profils verticaux en utilisant des chaînes de Markov cachées et des cartes auto-organisatrices." Paris 6, 2013. http://www.theses.fr/2013PA066761.
Full textAbstract:
Les observations satellitaires permettent d'estimer les valeurs de différents paramètres biogéochimiques à la surface des océans. D’une manière générale, les paramètres observés sont reliés à des grandeurs géophysiques de l’océan comme : les profils verticaux de concentrations en Chlorophylle-A, les profils de Salinité et de Température… La dimensionnalité de ces données environnementales est très grande, autant dans le cas des données de surface que des profils verticaux. A cause de leur grande dimensionnalité, et de la dynamique complexe qui relie ces données, il est difficile de modéliser leurs relations de façon linéaire. Il s'agit dans cette thèse d'élaborer une méthodologie d'inversion statistique des observations de surface afin de retrouver ces profils verticaux. La méthodologie développée et que nous avons nommée PROFHMM, fait appel aux Cartes Topologiques Auto-organisatrices pour pouvoir modéliser le problème sous forme d’une chaîne de Markov cachée. PROFHMM utilise les capacités topologiques des Carte Auto-organisatrices non seulement pour déterminer les états et la topologie de la chaîne de Markov cachée générée, mais aussi pour améliorer l’estimation des probabilités qui sont essentielles pour son fonctionnement. Sur les applications géophysiques que nous avons traité dans cette thèse, l’introduction des cartes topologiques auto-organisatrices se révèle un élément essentiel pour assurer les performances obtenues. Le manuscrit est structuré en quatre parties. La première partie présente les méthodes statistiques qui forment la base des méthodologies proposées dans cette thèse. Il s’agit des chaînes de Markov Cachées , de l’algorithme de Viterbi et des cartes topologiques auto-organisatrices. Chaque partie suivante représente un article : Le premier présente la méthodologie générale de PROFHMM, et traite de l’application qui porte sur la reconstitution temporelle des profils verticaux de Chlorophylle-A. Cette application permet de voir qu’il est possible de synchroniser des données issues de modèles numériques avec des données d’observation satellitaires. Le second article présente les résultats obtenus par l’application de PROFHMM pour reconstruire les données de la campagne ARAMIS à partir des données altimétriques AVISO et la température de surface fournie par la NOAA. Les performances obtenues prouvent qu’il est possible de synchroniser une dynamique océanique apprise par des données in-situ et des donnes de surface. Finalement, dans le troisième article nous présentons une modification à l’algorithme de Viterbi pour prendre en compte, durant la phase de reconstruction de trajectoires, une connaissance à priori sur la qualité des observations. La validité de l’approche est démontrée à partir d’expériences jumelles de reconstruction de séries temporelles de données surface<br>Satellite observations provide us with the values of different biogeochemical parameters at the surface layer of the ocean. These observations are highly correlated with the underlying vertical profiles of different oceanic parameters, such as the Chlorophyll-A concentration, the salinity and temperature of the water column… The sea-surface data and the vertical profiles of the oceanic parameters constitute multi-dimensional vectors. Due to their multi-dimensionality and the high complexity of the dynamics connecting these data sets, their links cannot be modeled linearly. In this thesis we present a methodology to statistically invert sea-surface observations in order to retrieve these vertical profiles. The developed methodology, named PROFHMM, makes use of Self Organizing Maps in order to render the inversion problem compatible with the Hidden Markov Model formalism. PROFHMM makes full use of the topological aspect of the Self Organizing Maps in order not only to generate the topology and states of the Hidden Markov Model, but also improve the estimation of the probabilities essential to the accuracy of the model. The use of the Self Organizing maps was essential in obtaining the results for the geophysical applications of PROFHMM presented in this manuscript. The manuscript was structured in three chapters, each consisting of an article. In the first one, the general methodology of PROFHMM is developed, then tested for the retrieval of vertical profiles of Chlorophyll-A by inverting sea-surface observations. This application demonstrated the ability to synchronize sea-surface data with the output data of numerical models. The second article presents the application of PROFHMM on the inversion of sea-surface data obtained from the AVISO and NOAA projects, in order to retrieve the vertical profiles of temperature over the rail of the ARAMIS mission. The performances obtained demonstrate the ability of PROFHMM to synchronize sea-surface data with in-situ measurements. Finally, in the third article, we present a modification to the Viterbi Algorithm in order to take into account an à priori knowledge of the quality of the observations when performing reconstructions. The proposed methodology, named PROFHMM_UNC, was applied for the reconstruction of the temporal evolution of sea-surface data, by taking into account the quality of the satellite observations used. The validity of the method was proven by performing a twin experiment on the outputs of a numerical model