177,587 research outputs found
Viterbi decoding strategies for 5 GHz wireless LAN systems
No full textStandards for the operation of wireless local area network (WLAN) technology in the 5 GHz band have been developed in Europe, North America and Japan. These systems employ orthogonal frequency division multiplexing (OFDM) technology, and utilize forward error correction (FEC) coding, based on a 1/2-rate convolutional encoder, to combat frequency selective fading caused by multipath channels. This paper examines methods, based on the popular Viterbi algorithm, for maximum-likelihood (ML) decoding of this convolutional code within the WLAN baseband receiver. Although the paper focuses on the European HIPERLAN/2 standard, because of international physical (PHY) layer harmonization, the work is equally applicable to the North American and Japanese WLAN systems. Received error rate results, based on a software simulation of the HIPERLAN/2 PHY layer, are presented for both hard and soft decision decoding strategies. In addition, the effect of quantization on soft decision decoding is investigated. The results highlight the importance of the decoder design on the performance of the WLAN
Data detection algorithms for perpendicular magnetic recording in the presence of strong media noise
No full textAs the throughput and density requirements increase for perpendicular magnetic recording channels, the presence of strong media noise degrades performance.
Detection algorithms have been developed that increase performance in channels with strong media noise through the use of data dependent detectors. However optimal data dependent detectors are exponentially more complex than data independent detectors, and therefore cannot be fully exploited. In this thesis we shall discuss the existing detection algorithms, comparing the performance against the complexity.
We then introduce a new sub-optimal detection algorithm, which employs a simple pre-detector that supplies estimates to a main detector. Numerical simulations are performed which show near optimal performance, but without the exponential increase in complexity.
We will also show how detector implementations can exploit structure in the trellis to further reduce complexity, through loops and path invariants.
An analytical means of measuring bit error rate from only the statistics of noise is presented, and this is utilised to optimally determine the equaliser and ISI target coefficients for a white noise Viterbi detector.
Finally, we introduce a new class of VLSI binary addition algorithms which can be utilised to increase the throughput of a Viterbi detector, but which also has a wider application in hardware design
Unifying Performance Metric of Viterbi Decoders
No full textConvolutional codes and Viterbi decoders were extensively used in error control systems.
The survivor memory management (SMM) unit of Viterbi decoder is extremely important in determining the throughput, hardware area and coding gain performance of the whole system.
Many SMM architectures were proposed in the past, but we lack an unifying metric to compare the coding gain performance of them.
In this thesis, we define a metric, average traceback depth (ATBD), to unify the diversity of different SMM architectures.
The ATBD metric can be used to equalize different SMM architectures and predict the optimal traceback depth (TBD) of them.
The optimality is in terms of coding gain performance and hardware cost.
We perform extensive computer simulations with three popular convolutional codes (DVB, DCII and UMTS) and many SMM architectures to verify the validity of the ATBD metric.
Simulation results show that the difference between optimal TBD and ATBD is at most 10%.
With this unifying metric, we can estimate the hardware cost of different SMM architectures under fixed coding gain performance.
Besides, system architects can use it to fast evaluate the tradeoff among hardware cost, throughput and coding gain performance because the calculation of ATBD metric is very simple.1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Convolutional Code & Viterbi Algorithm 5
2.1 Convolutional Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 The Viterbi Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Punctured Convolutional Codes . . . . . . . . . . . . . . . . . . . . . 14
2.4 Communication Channel Models . . . . . . . . . . . . . . . . . . . . . 17
3 Viterbi Decoder Architecture 21
3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Register Exchange Architecture . . . . . . . . . . . . . . . . . . . . . 24
3.3 Modified Register Exchange architecture . . . . . . . . . . . . . . . . 27
3.3.1 Comment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4 Traceback Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5 One-Pointer Traceback . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Multiple Pointer Traceback . . . . . . . . . . . . . . . . . . . . . . . . 36
3.7 Traceforward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.8 Sliding Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.9 Best State Traceback Architecture . . . . . . . . . . . . . . . . . . . . 46
3.10 Comparison of Architectures . . . . . . . . . . . . . . . . . . . . . . . 48
4 Performance Analysis and Metric 53
4.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Coding Gain Analysis of Viterbi Algorithm . . . . . . . . . . . . . . . 57
4.2.1 Simple Traceback Architecture . . . . . . . . . . . . . . . . . . 57
4.2.2 Register Exchange Architecture . . . . . . . . . . . . . . . . . 59
4.2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3 Equalization of SMM Architectures . . . . . . . . . . . . . . . . . . . 62
4.3.1 DCII & UMTS . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.2 Best State Architecture . . . . . . . . . . . . . . . . . . . . . . 63
4.4 Hardware Equalization . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.5 Coding Gain Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 72
5 Conclusion & Future Work 73
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
A Acronyms & Abbreviations 75
B Glossary of Notation 7
Multi-Mode Viterbi Decoder VLSI Design for Wireless Communication Systems
No full text在現今的無線通訊系統中，行動手持設備的應用已經越來越廣泛。同時，使用者對於手持設備資料傳輸的能力以及其訊號接受範圍的需求也日益增加。這樣的趨勢促使適用於廣泛領域的通訊規格及系統快速地發展，例如無線網路通訊系統中的IEEE 802.16(WiMAX)，802.16e(mobile WiMAX)，以及手機通訊系統中的3GPP，HSDPA(high speed downlink packet access)等等。支援多規格的手持通訊系統將是未來的一個趨勢。
在上述的規格中，維特比解碼器都是其通道編解碼器(channel CODEC)中不可獲缺的模組。雖然維特比解碼器的錯誤更正能力比不上近年來快速發展的渦輪解碼器(turbo decoder)以及低密度奇偶校驗解碼器(LDPC)，但其低功率且低硬體資源需求的特性使得維特比解碼器依然被各種先進的通訊規格所採用。因此，在此論文中我們設計出符合多種規格的維特比解碼器。
在本論文中，我們致力於兩個部份。首先，我們針對維特比解碼器中的存活路徑管理單元(survivor memory management unit, SMU)提出了兩種創新的技術，藉此我們可以在沒有錯誤更正效能損失的情況下降低功率消耗以及提高解碼速度。另外，我們提出了支援WiMAX，3GPP，以及HSDPA等多重規格的維特比解碼器架構。在硬體實作上，我們提出的維特比解碼器是透過標準單元的設計流程並利用TSMC 0.13um的先進製程來實現。The mobile handheld devices have been widely used as the application of the wireless communication systems. The requirement of the data throughput and the effective range of the handheld devices have been increased at the same time. It makes the needs of the long-range communication systems, such as IEEE 802.16 (WiMAX), 802.16e (mobile WiMAX), 3GPP of the mobile communication system, and the HSDPA (high speed downlink packet access), increase rapidly. In order to access different communication systems, the mobile communication devices suitable for multiple standards will be an important trend in the coming future.
In the standards mentioned above, Viterbi decoder is one of the essential modules of the channel CODEC. Though the error correcting performance of the Viterbi decoder may not better than the Turbo or LDPC decoders, Viterbi decoders are still widely adopted in the modern communication systems due to its lower power consumption and lower hardware requirements. As the reasons mentioned above, we propose several techniques for improving the Viterbi decoder and a structure suitable for a multi-mode Viterbi decoder design.
In this thesis, we were devoted to two fields. First, we propose two techniques of modifying the structure of the survivor memory units (SMU), which can reduce the power consumption and the decoding latency. Second, we propose a Viterbi decoder structure for fulfilling the specification of the WiMAX, 3GPP, and HSDPA at the same time. We use the 0.13 technology of the cell-based design flow to implement our proposed Viterbi decoder chip.Contents
List of Figures ix
List of Tables xii
Chapter 1 Introduction 1
1.1 Overview of Error-Correcting Codes 1
1.2 Overview of WiMAX & 3G-Based Systems 2
1.3 Motivation & Goal 4
1.4 Thesis Organization 6
Chapter 2 Convolutional Code & the Viterbi Algorithm 7
2.1 Convolutional Codes 7
2.1.1 Definition of a Convolutional Code 8
2.1.2 Trellis Diagram of a Convolutional Code 12
2.1.3 Decoding the Convolutional Codes 14
2.2 Viterbi Algorithm 16
2.2.1 Definition of Viterbi Algorithm 16
2.2.2 An Example of Viterbi Decoding 19
2.2.3 Basic Processing Units of Viterbi Decoders 22
Chapter 3 Proposed Survivor Memory Management Techniques 25
3.1 Register Exchange (RE) Method 26
3.2 Trace-Back (TB) Method 28
3.2.1 Basic Concept 28
3.2.2 Memory & Processor Configuration 31
3.2.3 K-Pointer Architecture 33
3.3 Trace-Forward (TF) Concept [18] 35
3.4 Proposed State Exchange (SE) Method 38
3.4.1 Basic Concept 38
3.4.2 Low Power State Exchange Architecture 41
3.5 Proposed Pipelined Trace-Forward Method 44
Chapter 4 Multi-Mode Viterbi Decoder Architecture 47
4.1 Multi-Mode Branch Metric Unit 49
4.2 Dual-Mode Add-Compare-Select Unit 52
4.3 Dual-Mode Survivor Memory Unit 56
Chapter 5 VLSI Implementation of the Proposed Viterbi Decoder 59
5.1 Fixed Point Simulation 59
5.2 Chip Implementation 62
5.2.1 Design Flow 62
Chapter 6 Conclusions and Future Work 69
6.1 Conclusions 69
6.2 Future Work 70
References 7
HABITAT USE BY A REINTRODUCED POPULATION OF BEARDED VULTURES (GYPAETUS BARBATUS) IN THE ITALIAN ALPS
No full textFollowing the reintroduction of the Bearded Vulture (Gypaetus barbatus) in the western Alps in 1987, the species reappeared in the Gran Paradiso National Park, Italy, where it had not been recorded since 1930. We analysed 1157 sighting records collected inside the park borders from 1989 to 2007. The number of sightings per year was not correlated with the number of captive-bred individuals released during the same year in the western Alps but was positively correlated with the number released one year prior and two years prior. Bearded Vultures were recorded mainly at higher altitudes during warmer months, and at lower altitudes when the terrain was mostly covered by snow, as were the two most abundant ungulates of the park, the alpine ibex (Capra ibex) and the alpine chamois (Rupicapra rupicapra), whose carcasses were primary food sources for vultures. Three habitats were used with a frequency significantly higher than expected based on availability: vegetated cliffs and screes, forest-scrub mosaic, and agriculture. Bare rocks and deciduous forests were used less frequently than expected, and other habitats were used in the same proportion as expected, including alpine grassland, coniferous forests, and alpine heaths and scrubs
Low Complexity Symbol Detection Method for Multilevel 2-D Optical Storage Based on a Linear Channel Model.
No full textA symbol detection scheme based on the Viterbi algorithm that simultaneously processes subsets of 2-D data in the presence of Gaussian noise was recently proposed for binary 2-D optical storage (TwoDOS). In the case of multilevel TwoDOS, a straightforward full-fledged maximum likelihood symbol detector, or even the previous Viterbi-based algorithm, is not an ideal solution due to complexity restrictions. We propose a suboptimum low complexity symbol detector, which still performs within the accepted performance bound for optical storage. We describe the procedures involved in designing and developing a practical symbol detection scheme for multilevel TwoDOS by analyzing the signal values generated by a linear channel model in the presence of Gaussian noise. Our proposed detection scheme exploits the properties of the 2-D data format on the disk, and is flexible enough to accommodate performance and complexity restrictions for optical storage applications
The Viterbi algorithm
No full textThis paper is a tutorial introduction to the Viterbi Algorithm, this is reinforced by an example use of the Viterbi Algorithm in the area of error correction in communications channels. Some extensions to the basic algorithm are also discussed briefly. Some of the many application areas where the Viterbi Algorithm has been used are considered, including it's use in communications. target tracking and pattern recognition problems. A proposal for further research into the use of the Viterbi Algorithm in Signature Verification is then presented, and is the area of present research at the moment
Design and testing of a real time simulation for Trellis Coded Modulation
No full textBibliography: leaves 75-76.The aim of this project is to build and test a real time simulation for Trellis Coded Modulation(TCM). The tests to be performed are a comparison between Ungerboeck and pragmatic codes and varying and observing different Viterbi decoder parameters for coded 8PSK. TCM is coded modulation which means the choice of modulation scheme is linked with the encoding technique. Convolutional codes are important for an understanding of TCM. They are described by the rate (which is the number of inputs over the number of outputs) and the number of memory elements, v. For TCM schemes, soft decision decoding, based on euclidean distance, rather than hard decision decoding, based on hamming distance, is used. Ungerboeck developed a mapping of encoder bits to channel signals on a constellation diagram. The mapping is called mapping by set partitioning and aims to find the smallest free euclidean distance for a given code. The free euclidean distance is the minimum euclidean distance between output sequences in a code. The asymptotic coding gain is a measure of coding gain based on the free euclidean distance
A parallel Viterbi decoder for block cyclic and convolution codes
No full textWe present a parallel version of Viterbi's decoding procedure, for which we are able to demonstrate that the resultant task graph has restricted complexity in that the number of communications to or from any processor cannot exceed 4 for BCH codes. The resulting algorithm works in lock step making it suitable for implementation on a systolic processor array, which we have implemented on a field programmable gate array and demonstrate the perfect scaling of the algorithm for two exemplar BCH codes. The parallelisation strategy is applicable to all cyclic codes and convolution codes. We also present a novel method for generating the state transition diagrams for these codes
Assessment of landscape change’s impact on Alpine species distribution using a multi-scale approach
No full textThere is a strong relation between biodiversity and traditional land use in Mediterrean areas. In these highly human dominated regions traditional acitvities profoundly shape the landscape with strong consequences on biodiversity pattern. However, in the last few decades the rapid socio-economic change lead to the abandonment of “marginal” land modifying the landscape structures. Available remote sensing data can provide information about environmental changes, but the occurrence of temporal and spatial gaps (e.g., the limited temporal archive of historical aerial images and the coarser spatial resolution of satellite data) can reduce the applicability of gained information. Considering the importance of the scale-dependency of ecological processes, we propose a multi-temporal and scale approach, combining remote sensed and field data, to monitor changes in vegetation and landscape structures and to evaluate their role in shaping Alpine species distribution. The study area is the Gran Paradiso National Park (NW Italian Alps) and we focused both on 5 altitudinal transects, representative of three altitudinal belts, and on landscape level. At first, from the interpretation of historical aerial photos in sampled areas, we reconstructed the land cover changes occurred during the last decades and we extended this information to the entire Park landscape, through a supervised classification of satellite data. Further, we developed a low-cost procedure of UAV (Unmanned Aerial Vehicle) survey adapted to Alpine environment, integrated with botanical sampling, in order to obtain highresolution land cover maps in test areas to replace the use of aerial photos in supervised classification of satellite data. This multi-scale analysis of landscape change allows us to detail how the environmental patterns affect the Alpine animal species distribution ranging from discrete areas to entire Park area
- …
