碩士 / 國立交通大學 / 資訊學院碩士在職專班資訊組 / 98 / This work considers the mini-slot scheduling problem in IEEE 802.16d wireless mesh networks (WMNs). An efficient mini-slot scheduling needs to take into account the transmission overhead, the scheduling complexity, and the signaling overhead to broadcast the scheduling results. We are interested in chain and grid WMNs, which are the basic topologies of many applications. We propose scheduling schemes that are featured by low complexity and low signaling overhead. Compared to existing works, this work contributes in developing low-cost schemes to find periodical and regular schedules that achieves near-optimal transmission latencies by balancing between transmission overhead and pipeline efficiency and that are more practical and easier to implement. Simulation results show that our schemes significantly improves over exiting works in computational complexity while maintain similar or better transmission latencies.

碩士 / 國立交通大學 / 資訊科學與工程研究所 / 98 / Despite a lot of research efforts in baseball video processing in recent years, little work has been done in analyzing the detailed semantic baseball event detection. This thesis presents an effective and efficient baseball event classification system for broadcast baseball videos. Utilizing the strictly-defined specifications of the baseball field and the regularity of shot transition, the system recognizes highlight in video clips and identifies what semantic baseball event of the baseball clips is currently proceeding. The semantic exploring system is proposed to achieve the objective. First, a video is segmented into several highlights starting with a PC (Pitcher and Catcher) shot and ending up with a close-up or some specific shots. Before every baseball event classifier is designed, several novel schemes including some specific features such as soil percentage and objects extraction such as first base are applied. The extracted midlevel cues are used to develop baseball event classifiers based on an HMM (Hidden Markov model). Due to specific features detection the proposed method not only improves the accuracy of the highlight classifier but also supports variety types of the baseball events. The proposed approach is very efficient. More importantly, the simulation results show that the classification of twelve significant baseball highlights is very promising.

碩士 / 國立交通大學 / 資訊科學與工程研究所 / 98 / Existing sequential pattern mining algorithms assume that events occur instantaneously. However, events in real world applications usually have durations which are called interval-based events. But complex relationship among event intervals causes difficulty in designing an efficient interval-based event mining algorithm. Therefore, the concept of “coincidence-slice” is proposed to solve the problem caused by the complex relationship among event intervals. The event intervals are incised to disjoint smaller “event slices” according to the coincidences among event intervals, that is, several event slices may occur in the same time period called “coincidence”. Therefore, an original event sequence can be represented as a list of ordered “coincidences” which contains event slices. This new representation proposed is called “coincidence sequence representation”. We transform the problem of complex relationship among event interval to consider the simple relationship among event slices. The proposed interval-based sequential pattern mining algorithm called CTMiner is based on the “coincidence sequence representation”. The CTMier also uses the concept of well-known sequential pattern mining algorithm PrefixSpan to find temporal patterns without candidate generation. Finally, to comprehend the frequent temporal pattern represented by “coincidence sequence representation”, we discover and use relation list to present all the relationships in a pattern. We also implement some pruning strategies to improve the performance of CTMiner by considering the characteristics of the “Coincidence-slice”. Experiments on both synthetic datasets and real dataset of library lending indicate the efficiency and scalability of the proposed algorithm.

碩士 / 國立交通大學 / 資訊科學與工程研究所 / 98

碩士 / 國立交通大學 / 資訊科學與工程研究所 / 98 / We consider the so called Magnus-Derek game, which is a two-person game played on a round table with n positions. The two players are called Magnus and Derek. Initially there is a token placed at position 0. In each round Magnus chooses a positive integer m ≤ n/2 as the distance of the targeted position from his current position for the token to move, and Derek decides a direction, clockwise or counterclockwise, to move the token. The goal of Magnus is to maximize the total number of positions visited, while Derek's is to minimize this number. If both players play optimally, we prove that Magnus, the maximizer, can achieve his goal in O(n) rounds, which improves a previous result with O(nlog n) rounds. Then we consider a modified version of Magnus-Derek game, where one of the players reveals his moves in advance and the other player plays optimally. In this case we prove that Derek has an O(n^3) algorithm to achieve his goal if Magnus reveals his moves in advance. On the other hand, Magnus has an O(n) algorithm. We also consider the circumstance that both players play randomly, and we show that the expected time to visit all positions is O(nlog n).

碩士 / 國立交通大學 / 資訊科學與工程研究所 / 98 / The extension of wireless technology, vehicular ad hoc network (VANET), provides emergency warning services and general data transmission services. To rescue more drivers from being involved in an emergency event on the road, fast emergency message propagation is an important issue in VANET studies. There are two types of multi-hop broadcasting forwarder selection scheme for emergency broadcasting, known as sender-oriented schemes and receiver-oriented schemes. The sender-oriented schemes maintain the neighbor information to choose the best forwarder before broadcasting the message while the receiver-oriented schemes distributedly elect the forwarders. In this thesis, we proposed a vehicle-density-based emergency broadcast (VDEB) scheme to solve the problem of high overhead in sender-oriented schemes and long delay in receiver-oriented schemes. The simulation results show that our VDEB scheme can achieve a better performance with low delay and little overhead.

碩士 / 國立交通大學 / 資訊科學與工程研究所 / 98 / More and more modern processors support SIMD instructions for improving performance in media applications. Programmers usually need detailed target-specific knowledge to use SIMD instructions directly. Thus, an auto-vectorization compiler that automatically generates efficient SIMD instructions is in urgent need. We implement an automatic superword vectorization, based on the LLVM compiler infrastructure, to which an auto-vectorization and an alignment analysis passes have been added. The auto-vectorization pass exploits data-parallelism in a basic block and convert IR instructions from primitive type to vector type. Then, in code generator, the alignment analysis pass analyzes every memory access with respect to those vector instructions and generates the alignment information for generate target-specific alignment instructions. In this paper, we use UltraSPARC as our experimental platform and use two realignment instructions to perform misaligned access. We also present preliminary experimental results, which reveals that our optimization generates vectorized code that are 4% up to 35% speed up.

碩士 / 國立交通大學 / 電子研究所 / 98 / The thesis investigated the analysis, design and implementation of a fully integrated circuit of power amplifier with silicon-based technologies, application to the family of IEEE-802.11a and 5.8-GHz bandwidth on the communication system. This paper proposes two type designs of power combiner, based on the conception of power combination; it can be efficiently to improvement limitation on silicon processes. For the first topic, the technique which we provide a power combiner with a four-ports transformer-coupled is presented here. By the single port of transformer, we introduce the stack structure with metal layers. On primary-side is the structure with all-stack metal layers, which solves the limitation of dc current density based on silicon processes. In part of high frequency, the secondary-side structure with segment stack metal layers can be efficiently to improve the edge-coupled efficiency, and proceed to reach the watt-level of power specification. Second topic, we demonstrate a four-ports impedance transformation transformer III here. For the input impedance match of four-ports differential amplifier, we used a design conception with distributed-active-transformer. The part of four-ports impedance transformation transformer employ the top metal possessed high quality characteristic for layout with metal line. In part of high frequency, it efficiently to change the width of metal line and mid-point with single port transformer is directly ground connection, and proceeds to reach impedance match between the input single-side and the input of four-ports differential amplifier. Finally, to reach a high efficiency and fully integrated power amplifier, how to improve the match between the four-ports differential amplifier and output power combiner efficiently is described in detail in the chapter-4.

碩士 / 國立交通大學 / 電子研究所 / 98 / In cooperative communication systems, multiple carrier frequency offsets (MCFOs) due to the varying accuracies of each node’s oscillators and different Doppler spreads may result in severe Inter-Carrier Interference (ICI), which drastically degrades the performance of BICM-OFDM systems. With proper approximation of the transmission environment, it is straightforward to obtain an equivalent channel matrix taking ICI into account. Based on the trellis structure and the fact that ICI energy is concentrated in adjacent subcarriers, we incorporate an MLSE equalizer into a turbo decoder to eliminate ICI caused by MCFOs and the Doppler effect; henceforth the full diversity is achieved, as shown in computer simulations.

博士 / 國立交通大學 / 電子研究所 / 98 / This dissertation presents a wideband RF transceiver for ultra-wideband (UWB) applications implemented in a 1.2 V 0.13 μm CMOS process. The receiver design focuses on mode 1 of multi-band (MB) orthogonal frequency division multiplexing (OFDM) UWB (3~5 GHz) which is defined as essential band by WiMedia Alliance. The receiver chain is composed by a broadband 3~5GHz ESD-protected low-noise amplifier, a 3th-order notch filter, a current-mode down conversion mixer and a 250MHz wideband analog baseband. In the analog baseband, PGAs and filters are carried out by current-mode amplifiers to achieve wide bandwidth and wide dynamic range of gain, as well as low noise and high linearity. Besides, a current-mode Sallen-Key low-pass filter is adopted for effective rejection of out-of-band interferers. A 6th-order Chebyshev low-pass filter realized in Gm-C topology is designed in the baseband chain for channel selection. Digitally-assisted DC-offset calibration improves second-order distortion of the entire chain. The entire receiver consumes 100 mW under a supply voltage of 1.2 V. In the design of transmitter, we attempt to cover both mode 1 and Band Group 3 of MB-OFDM UWB (3~8 GHz). The 3~8 GHz transmitter chain integrates an analog baseband, an in/quadrature-phase (IQ) modulator, a variable gain amplifier (VGA), a differential-to-single amplifier, a power amplifier, as well as a transmitted signal strength indicator (TSSI). The IQ modulator incorporates DC-offset cancellation circuits to improve carrier leakage suppression. This transmitter provides linear-in-dB output power tuning of 14 dB to fulfill the requirement of WiMedia UWB. Measured maximum output power and OP1dB are -5 dBm and +1.5 dBm, respectively. Measured carrier leakage suppression is over 40 dB after calibration. The high linearity and accurate IQ modulation lead to an error vector magnitude (EVM) of -28 dB under the data rate of 480 Mb/s in WiMedia Mode 1. The entire transmitter consumes 66 mW under a supply voltage of 1.2 V.