As the sizes of modern circuit designs become bigger and bigger, implementing those large circuits into FPGA become arduous. The state-of-the-art academic FPGA place-and-route tool, VPR, has good quality but needs around a whole day to complete a placement when the input circuit netlist contains millions of lookup tables, excluding the runtime needed for routing. / To speed up the placement process, we propose a routability-driven placement algorithm for FPGAs, which adopts techniques used in ASIC global placer. Our placer follows the lower-bound-and-upper-bound iterative optimization process in ASIC placers like Ripple. The total half perimeter wirelength (HPWL) of the circuit is used as the objective cost function and it modeled using the Bound2Bound net model. In lower bound computation, a placement solution with the minimum HPWL is determined by the conjugate gradient method. In upper bound computation, an almost-legalized result is produced by spreading cells linearly in the whole placement area. Those positions are then served as fixed-point anchors and fed into the next lower bound computation. Furthermore, global routing will be performed in the upper bound computation to estimate the routing segments usage, as a mean to consider congestion in the placement. The two bounds computations are computed alternatively until their results converge. / We tested our approach using 20 MCNC benchmarks and 16 large benchmarks for performance and scalability. Experimental results show that based on the island-style architecture which VPR is most optimized, our approach can obtain a placement result 8× faster than VPR with 2% more in channel width, or 3× faster with 1% more in channel width when considering congestion either. Our approach is even 20× faster in placing large benchmarks having over 50,000 lookup tables, however, with 10% more in channel width. Based on the Xilinx Virtex-5 architecture from a recent related work, we can out-perform VPR by reducing the channel width by 3% with almost 3× speedup in runtime. / 現今的電路設計得愈來愈大，要把這些巨大的電路實現在現場可程式邏輯門陣列(FPGA)上變得愈來愈困難，由其在布局及布線程序上變得十分耗時。儘管在一般的情況下，現時在學術領域中，最先進的用在FPGA上的布局及布線工具能夠提供高質素的布局結果，但當所需要布局的電路所包含的邏輯元件數達到數百萬個以上時，該工具也要耗費一整天的時間才能完成整個布局程序，其中並未計算之後布線程序所額外需要的時間。 / 有見及此，我們參考了一些應用在特殊應用積體電路(ASIC)設計軟體上的布局方法，並提出了一個專為FPGA而設的偏向優化Routability的布局算法來縮短布局程序所需要的時間。我們的算法以Bound2Bound模型來模擬電路內邏輯元件間的接線，並估算其Half-Perimeter線長(HPWL)來作為我們的目標函數進行優化。我們採用了一些ASIC布局軟體，如Ripple內的上限及下限交互計算的迭代優化程序。在下限的運算過程中，我們在無視節點重疊的情況下，使用了共軛梯度法來找出HPWL的最少值。在上限的運算過程中，我們把在下限計算找到的結果平均散佈在整個可布局的區域內，從而減少節點重疊的情況來得出一接近有效的布局結果。接著，這些節點的位置會被用作定點錨，附加在下一次的下限計算中，並引導它得出一節點重疊相對較少的布局結果。此外，我們可以選擇在上限的運算過程中加入Global Routing程序來估計該布局結果所需的線段數，從而在布局過程中考慮布線過份擁塞的情況。上限及下限的計算會不斷交互進行，直至雙方所得的結果聚合為止。 / 我們使用了20個MCNC基準電路及16個大型基準電路，來測試我們的布局算法的性能和可擴展性。實驗結果指出，針對島狀結構的FPGA，我們的算法能夠比VPR快8倍得出布局結果，但其通道寬度(Channel Width)卻增加了2%。如果在考慮布線擁塞度的情況下，我們的算法能夠比VPR快3倍，但其通道寬度卻增加了1%。再者，對於一些擁有超過50000個邏輯元件的大型基準電路，相比於VPR，雖然我們的算法能夠提供20倍的速度增長，但其布局結果的通道寬度卻增加了10%。如果我們使用在最近的相關研究中使用的Xilinx Virtex-5結構的話，我們的算法能夠比VPR快接近3倍得出布局結果，並且減少約3%的通道寬度。 / Lam, Ka Chun. / Thesis M.Phil. Chinese University of Hong Kong 2014. / Includes bibliographical references (leaves 64-70). / Abstracts also in Chinese. / Title from PDF title page (viewed on 12, October, 2016). / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only.

Chu-Keung Chung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 88-92). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgments --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation and Aims --- p.1 / Chapter 1.2 --- Contributions --- p.3 / Chapter 1.3 --- Structure of the Thesis --- p.4 / Chapter 2 --- Literature Review --- p.6 / Chapter 2.1 --- Introduction --- p.6 / Chapter 2.2 --- Complete Algorithms --- p.7 / Chapter 2.2.1 --- Parallel Checking --- p.7 / Chapter 2.2.2 --- Mom's --- p.8 / Chapter 2.2.3 --- Davis-Putnam --- p.9 / Chapter 2.2.4 --- Nonchronological Backtracking --- p.9 / Chapter 2.2.5 --- Iterative Logic Array (ILA) --- p.10 / Chapter 2.3 --- Incomplete Algorithms --- p.11 / Chapter 2.3.1 --- GENET --- p.11 / Chapter 2.3.2 --- GSAT --- p.12 / Chapter 2.4 --- Summary --- p.13 / Chapter 3 --- Algorithms --- p.14 / Chapter 3.1 --- Introduction --- p.14 / Chapter 3.2 --- Tree Search Techniques --- p.14 / Chapter 3.2.1 --- Depth First Search --- p.15 / Chapter 3.2.2 --- Forward Checking --- p.16 / Chapter 3.2.3 --- Davis-Putnam --- p.17 / Chapter 3.2.4 --- GRASP --- p.19 / Chapter 3.3 --- Incomplete Algorithms --- p.20 / Chapter 3.3.1 --- GENET --- p.20 / Chapter 3.3.2 --- GSAT Algorithm --- p.22 / Chapter 3.4 --- Summary --- p.23 / Chapter 4 --- Field Programmable Gate Arrays --- p.24 / Chapter 4.1 --- Introduction --- p.24 / Chapter 4.2 --- FPGA --- p.24 / Chapter 4.2.1 --- Xilinx 4000 series FPGAs --- p.26 / Chapter 4.2.2 --- Bitstream --- p.31 / Chapter 4.3 --- Giga Operations Reconfigurable Computing Platform --- p.32 / Chapter 4.4 --- Annapolis Wildforce PCI board --- p.33 / Chapter 4.5 --- Summary --- p.35 / Chapter 5 --- Implementation --- p.36 / Chapter 5.1 --- Parallel Graph Coloring Machine --- p.36 / Chapter 5.1.1 --- System Architecture --- p.38 / Chapter 5.1.2 --- Evaluator --- p.39 / Chapter 5.1.3 --- Finite State Machine (FSM) --- p.42 / Chapter 5.1.4 --- Memory --- p.43 / Chapter 5.1.5 --- Hardware Resources --- p.43 / Chapter 5.2 --- Serial Graph Coloring Machine --- p.44 / Chapter 5.2.1 --- System Architecture --- p.44 / Chapter 5.2.2 --- Input Memory --- p.46 / Chapter 5.2.3 --- Solution Store --- p.46 / Chapter 5.2.4 --- Constraint Memory --- p.47 / Chapter 5.2.5 --- Evaluator --- p.48 / Chapter 5.2.6 --- Input Mapper --- p.49 / Chapter 5.2.7 --- Output Memory --- p.49 / Chapter 5.2.8 --- Backtrack Checker --- p.50 / Chapter 5.2.9 --- Word Generator --- p.51 / Chapter 5.2.10 --- State Machine --- p.51 / Chapter 5.2.11 --- Hardware Resources --- p.54 / Chapter 5.3 --- Serial Boolean Satisfiability Solver --- p.56 / Chapter 5.3.1 --- System Architecture --- p.58 / Chapter 5.3.2 --- Solutions --- p.59 / Chapter 5.3.3 --- Solution Generator --- p.59 / Chapter 5.3.4 --- Evaluator --- p.60 / Chapter 5.3.5 --- AND/OR --- p.62 / Chapter 5.3.6 --- State Machine --- p.62 / Chapter 5.3.7 --- Hardware Resources --- p.64 / Chapter 5.4 --- GSAT Solver --- p.65 / Chapter 5.4.1 --- System Architecture --- p.65 / Chapter 5.4.2 --- Variable Memory --- p.65 / Chapter 5.4.3 --- Flip-Bit Vector --- p.66 / Chapter 5.4.4 --- Clause Evaluator --- p.67 / Chapter 5.4.5 --- Adder --- p.70 / Chapter 5.4.6 --- Random Bit Generator --- p.71 / Chapter 5.4.7 --- Comparator --- p.71 / Chapter 5.4.8 --- Sum Register --- p.71 / Chapter 5.5 --- Summary --- p.71 / Chapter 6 --- Results --- p.73 / Chapter 6.1 --- Introduction --- p.73 / Chapter 6.2 --- Parallel Graph Coloring Machine --- p.73 / Chapter 6.3 --- Serial Graph Coloring Machine --- p.74 / Chapter 6.4 --- Serial SAT Solver --- p.74 / Chapter 6.5 --- GSAT Solver --- p.75 / Chapter 6.6 --- Summary --- p.76 / Chapter 7 --- Conclusion --- p.77 / Chapter 7.1 --- Future Work --- p.78 / Chapter A --- Software Implementation of Graph Coloring in CHIP --- p.79 / Chapter B --- Density Improvements Using Xilinx RAM --- p.81 / Chapter C --- Bit stream Configuration --- p.83 / Bibliography --- p.88 / Publications --- p.93

Tsoi Kuen Hung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 84-92). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Objectives --- p.3 / Chapter 1.3 --- Contributions --- p.3 / Chapter 1.4 --- Thesis Organization --- p.4 / Chapter 2 --- Background and Review --- p.6 / Chapter 2.1 --- Introduction --- p.6 / Chapter 2.2 --- Cryptographic Algorithms --- p.6 / Chapter 2.3 --- Cryptographic Applications --- p.10 / Chapter 2.4 --- Modern Reconfigurable Platforms --- p.11 / Chapter 2.5 --- Review of Related Work --- p.14 / Chapter 2.5.1 --- Montgomery Multiplier --- p.14 / Chapter 2.5.2 --- IDEA Cipher --- p.16 / Chapter 2.5.3 --- RC4 Key Search --- p.17 / Chapter 2.5.4 --- Secure Random Number Generator --- p.18 / Chapter 2.6 --- Summary --- p.19 / Chapter 3 --- The IDEA Cipher --- p.20 / Chapter 3.1 --- Introduction --- p.20 / Chapter 3.2 --- The IDEA Algorithm --- p.21 / Chapter 3.2.1 --- Cipher Data Path --- p.21 / Chapter 3.2.2 --- S-Box: Multiplication Modulo 216 + 1 --- p.23 / Chapter 3.2.3 --- Key Schedule --- p.24 / Chapter 3.3 --- FPGA-based IDEA Implementation --- p.24 / Chapter 3.3.1 --- Multiplication Modulo 216 + 1 --- p.24 / Chapter 3.3.2 --- Deeply Pipelined IDEA Core --- p.26 / Chapter 3.3.3 --- Area Saving Modification --- p.28 / Chapter 3.3.4 --- Key Block in Memory --- p.28 / Chapter 3.3.5 --- Pipelined Key Block --- p.30 / Chapter 3.3.6 --- Interface --- p.31 / Chapter 3.3.7 --- Pipelined Design in CBC Mode --- p.31 / Chapter 3.4 --- Summary --- p.32 / Chapter 4 --- Variable Radix Montgomery Multiplier --- p.33 / Chapter 4.1 --- Introduction --- p.33 / Chapter 4.2 --- RSA Algorithm --- p.34 / Chapter 4.3 --- Montgomery Algorithm - Ax B mod N --- p.35 / Chapter 4.4 --- Systolic Array Structure --- p.36 / Chapter 4.5 --- Radix-2k Core --- p.37 / Chapter 4.5.1 --- The Original Kornerup Method (Bit-Serial) --- p.37 / Chapter 4.5.2 --- The Radix-2k Method --- p.38 / Chapter 4.5.3 --- Time-Space Relationship of Systolic Cells --- p.38 / Chapter 4.5.4 --- Design Correctness --- p.40 / Chapter 4.6 --- Implementation Details --- p.40 / Chapter 4.7 --- Summary --- p.41 / Chapter 5 --- Parallel RC4 Engine --- p.42 / Chapter 5.1 --- Introduction --- p.42 / Chapter 5.2 --- Algorithms --- p.44 / Chapter 5.2.1 --- RC4 --- p.44 / Chapter 5.2.2 --- Key Search --- p.46 / Chapter 5.3 --- System Architecture --- p.47 / Chapter 5.3.1 --- RC4 Cell Design --- p.47 / Chapter 5.3.2 --- Key Search --- p.49 / Chapter 5.3.3 --- Interface --- p.50 / Chapter 5.4 --- Implementation --- p.50 / Chapter 5.4.1 --- RC4 cell --- p.51 / Chapter 5.4.2 --- Floorplan --- p.53 / Chapter 5.5 --- Summary --- p.53 / Chapter 6 --- Blum Blum Shub Random Number Generator --- p.55 / Chapter 6.1 --- Introduction --- p.55 / Chapter 6.2 --- RRNG Algorithm . . --- p.56 / Chapter 6.3 --- PRNG Algorithm --- p.58 / Chapter 6.4 --- Architectural Overview --- p.59 / Chapter 6.5 --- Implementation --- p.59 / Chapter 6.5.1 --- Hardware RRNG --- p.60 / Chapter 6.5.2 --- BBS PRNG --- p.61 / Chapter 6.5.3 --- Interface --- p.66 / Chapter 6.6 --- Summary --- p.66 / Chapter 7 --- Experimental Results --- p.68 / Chapter 7.1 --- Design Platform --- p.68 / Chapter 7.2 --- IDEA Cipher --- p.69 / Chapter 7.2.1 --- Size of IDEA Cipher --- p.70 / Chapter 7.2.2 --- Performance of IDEA Cipher --- p.70 / Chapter 7.3 --- Variable Radix Systolic Array --- p.71 / Chapter 7.4 --- Parallel RC4 Engine --- p.75 / Chapter 7.5 --- BBS Random Number Generator --- p.76 / Chapter 7.5.1 --- Size --- p.76 / Chapter 7.5.2 --- Speed --- p.76 / Chapter 7.5.3 --- External Clock --- p.77 / Chapter 7.5.4 --- Random Performance --- p.78 / Chapter 7.6 --- Summary --- p.78 / Chapter 8 --- Conclusion --- p.81 / Chapter 8.1 --- Future Development --- p.83 / Bibliography --- p.84

"In the design of any antenna radiator, single or multi-element, a significant amount of time and resources is spent on impedance matching. There are broadly two approaches to impedance matching; the first is the distributed impedance matching approach which leads to modifying the antenna geometry itself by identifying appropriate degrees of freedom within the structure. The second option is the lumped element approach to impedance matching. In this approach instead of modifying the antenna geometry a passive network attempts to equalize the impedance mismatch between the source and the antenna load. This thesis introduces a new technique of impedance matching using lumped circuits (passive, lossless) for electrically small (short) non-resonant dipole/monopole antennas. A closed form upper-bound on the achievable transducer gain (and therefore the reflection coefficient) is derived starting with the Bode-Fano criterion. A 5 element equalizer is proposed which can equalize all dipole/monopole like antennas. Simulation and experimental results confirm our hypothesis. The second contribution of this thesis is in the design of broadband, small size, modular arrays (2, 4, 8 or 16 elements) using the distributed approach to impedance matching. The design of arrays comprising a small number of elements cannot follow the infinite array design paradigm. Instead, the central idea is to find a single optimized radiator (unit cell) which if used to build the 2x1, 4x1, 2x2 arrays, etc. (up to a 4x4 array) will provide at least the 2:1 bandwidth with a VSWR of 2:1 and stable directive gain (not greater than 3 dB variation) in each configuration. Simulation and experimental results for a solution to the 2x1, 4x1 and 2x2 array configurations is presented. "

Glycans and their conjugates form the largest and most diverse class of biological molecules found within nature. These glycosides are vital for numerous cellular functions including recognition events, protein stabilisation and energy storage, to name a few. Additionally, abnormalities within these structures are associated with a wide range of disease states. As a result, robust analytical techniques capable of in depth characterisation of carbohydrates and their binding partners are required. Currently, liquid chromatography coupled with tandem mass spectrometry (MS2) is the 'gold standard' for characterising these species. However there are inherent challenges for 'sequencing' carbohydrates given that most structures are diastereomeric. As a result MS alone is insufficient to fully elucidate all stereochemical and often regiochemical information and alternative analytical techniques have inherent issues meaning that they are not suitable for medium/high throughput analysis. To facilitate elucidation of these structures, ion mobility spectrometry (IMS) has been used in-line with MS2. IMS of mono- and di-saccharide product ions generate by collision-induced dissociation (CID) of various glycans and their conjugates enables unambiguous identification of the monomer and the regio-/stereo-chemistry of the glycosidic bond, independent of the precursor structure. Also, given the prominence of glycans in biological recognition events, high-throughput techniques capable of elucidating and characterising carbohydrate to glycan-binding protein (GBP) interactions are highly sought after. Historically, (micro)array strategies are employed to screen large numbers of biological interactions, with detection conventionally achieved with fluorescent tagging. The major disadvantage of this approach is the requirement of a labelling step to facilitate detection of glycan-GBP binding. MS offers the ability to unambiguously identify GBPs when combined with routine bottom-up proteomics strategies, namely on-chip proteolysis followed by mass fingerprinting and MS2 analysis and subsequent comparison to protein databases. It is anticipated that these methodologies developed throughout these studies, both for carbohydrate sequencing and the characterisation of glycan-binding proteins, will greatly add to the Glycomics toolbox.

Zhou Lin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (leaves 50-53). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Aims and Contribution --- p.3 / Chapter 1.3 --- Thesis Overview --- p.4 / Chapter 2 --- Field-Programmable Gate Array and Routing Algorithm in VPR --- p.6 / Chapter 2.1 --- Commercially Available FPGAs --- p.6 / Chapter 2.2 --- FPGA Logic Block Architecture --- p.7 / Chapter 2.2.1 --- Logic Block Functionality vs. FPGA Area-Efficiency --- p.7 / Chapter 2.2.2 --- Logic Block Functionality vs. FPGA Delay-Performance --- p.7 / Chapter 2.2.3 --- Lookup Table-Based FPGAs --- p.8 / Chapter 2.3 --- FPGA Routing Architecture --- p.8 / Chapter 2.4 --- Design Parameters of FPGA Routing Architecture --- p.10 / Chapter 2.5 --- CAD for FPGAs --- p.10 / Chapter 2.5.1 --- Synthesis and Logic Block Packing --- p.11 / Chapter 2.5.2 --- Placement --- p.11 / Chapter 2.5.3 --- Routing --- p.12 / Chapter 2.5.4 --- Delay Modelling --- p.13 / Chapter 2.5.5 --- Timing Analysis --- p.13 / Chapter 2.6 --- FPGA Programming Technologies --- p.13 / Chapter 2.7 --- Routing Algorithm in VPR --- p.14 / Chapter 2.7.1 --- Pathfinder Negotiated Congestion Algorithm --- p.14 / Chapter 2.7.2 --- Routing Algorithm Used by VPR --- p.16 / Chapter 3 --- Connection-Switch Box Design --- p.17 / Chapter 3.1 --- Introduction --- p.17 / Chapter 3.2 --- Connection-Switch Box Design Algorithm --- p.19 / Chapter 3.2.1 --- Connection between Logic Pins and Tracks --- p.20 / Chapter 3.2.2 --- Connection between Pad Pins and Tracks --- p.25 / Chapter 3.3 --- Switch Number Comparisons --- p.26 / Chapter 3.4 --- Experimental Results --- p.29 / Chapter 3.5 --- Summary --- p.32 / Chapter 4 --- Optimal MST-Based Graph Algorithm on FPGA Segmenta- tion Design --- p.37 / Chapter 4.1 --- Introduction --- p.37 / Chapter 4.2 --- MST-Based Graph Algorithm on FPGA Channel Segmentation Design --- p.39 / Chapter 4.2.1 --- Net Merging Problem of Row-Based FPGAs --- p.41 / Chapter 4.2.2 --- Extended Net Merging Problem of Symmetrical Array FPGAs --- p.44 / Chapter 4.3 --- Experimental Results --- p.46 / Chapter 4.4 --- Summary --- p.46 / Chapter 5 --- Conclusions --- p.48 / Bibliography --- p.50

Lee Wai Ki. / Thesis submitted in: May 2004. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 62-66). / Abstracts in English and Chinese. / Chapter Chapter 1: --- Introduction --- p.8 / Chapter 1.1 --- Motivation --- p.8 / Chapter 1.2 --- Organization of the thesis --- p.10 / Chapter Chapter 2: --- Background Technology --- p.12 / Chapter 2.1 --- Introduction: FUZZY EM CAD formula for impedance of the edge of the patch antenna --- p.12 / Chapter 2.2 --- Fringe field extension of the patch: --- p.12 / Chapter 2.2.1 --- Applying the root of area capacitance formula --- p.12 / Chapter 2.2.2 --- Defining microstrip parallel plate capacitor with infinite substrate --- p.13 / Chapter 2.2.3 --- The parallel plate capacitor formula --- p.14 / Chapter 2.2.4 --- DC fringe field leading to the patch extension --- p.15 / Chapter 2.3 --- Cavity model of the patch --- p.16 / Chapter 2.3.1 --- Cavity model analysis on its internal field --- p.16 / Chapter 2.3.2 --- Input impedance derived from cavity model --- p.19 / Chapter 2.3.3 --- Quality factor of patch antenna --- p.19 / Chapter 2.4 --- Fringe extension applied to cavity model in RF --- p.23 / Chapter Chapter 3: --- Simple one Port wide band multi-layer patch Antenna --- p.24 / Chapter 3.1 --- Introduction --- p.24 / Chapter 3.2 --- Antenna design --- p.25 / Chapter 3.3 --- Measured results --- p.26 / Chapter 3.4 --- Antenna Analysis --- p.29 / Chapter 3.5 --- Conclusion --- p.30 / Chapter Chapter 4: --- Design synthesis of patch antennas of the T-square Probe --- p.31 / Chapter 4.1 --- Introduction --- p.31 / Chapter 4.2 --- The physics interpretation --- p.32 / Chapter 4.3 --- The Smith chart movement by the T-square feed on the patch --- p.33 / Chapter 4.4 --- Conclusion --- p.35 / Chapter Chapter 5: --- Design synthesis of the wideband tuning-fork-shaped feeding for patch antenna --- p.36 / Chapter 5.1 --- Introduction --- p.36 / Chapter 5.2 --- Antenna design --- p.36 / Chapter 5.3 --- The Smith chart movements of the tuning-fork shaped feeding on the patch --- p.37 / Chapter 5.4 --- Conclusion --- p.41 / Chapter Chapter 6: --- "Fork on H-slot feed of multilayer microstrip antenna for wideband, high isolation and low cross polarization" --- p.42 / Chapter 6.1 --- Introduction --- p.42 / Chapter 6.2 --- Antenna analysis - Isolation improvement considerations --- p.44 / Chapter 6.3 --- Antenna design and measured results --- p.46 / Chapter 6.3.1 --- The simulated return loss and current distribution s in various structure of the two port. --- p.47 / Chapter 6.3.2. --- The hardware and the comparison of results --- p.50 / Chapter 6.3.3. --- The simulated properties of the radiation patterns and cross-polarizations --- p.52 / Chapter 6.3.4. --- The comparison of radiation patterns between simulation and hardware --- p.56 / Chapter 6.4 --- Further improvements --- p.58 / Chapter 6.5 --- Conclusion --- p.59 / Chapter Chapter 7: --- Conclusions --- p.60 / Reference --- p.62 / List of Publication --- p.66

投影機相機(projector camera)系統近年相當流行，主要原因是它能夠靈活地展示影像，使用戶有更大的自由度作出操作。手提式投影機的技術在過往幾年急速發展、漸見成熟，知名的家用電子産品生産廠閱始推出内置迷你投影機的手機和攝影機。另一方面手機的運算能力正急劇地提升，它們多都配置不同種類且功能强大的周邊設備。 / 本論文提出並討論一種基於現場可编程邏輯閘陣列(Field Programmable Gate Array, FPGA),並適用於嵌入式系统的特殊處理器。該特殊處理器專門處理來自相機的資料串流，透過一系列的象素圖像處理運算如圖像梯度和高斯模糊，去找出相中物件的邊緣，藉此分擔微處器在運算上的負擔。實驗結果明這特殊處理器可實現於低端的FPGA上並和普遍的微處器一起運作。 / 本論文第二個探討的主題是一個利用多模卡爾曼濾波器(Multiple Model Kalman Filter)的直線追踪器，並利用多個直線追踪器去作投影面板的追踪。利用卡爾曼濾波器只需要很低的運算能力的優點,我們的直線追踪器在嵌入式系统實測時能達到每秒200幀的速度。多模卡爾曼濾波器在實驗中有滿意的成績並較單卡爾曼濾波器和擴展卡爾曼濾波器優異。 / Projector-camera (ProCam in short) systems are getting very popular since the user can change the display area dynamically and enjoy more freedom in handling the device. In recent years, the mobile projector technology is becoming mature and manufacturers are shipping mobile phones and digital cameras with projectors. On the other hand, the computation power of a cell phone had dramatically increased and the cell phones are accompanied with large number of powerful peripherals. / In this thesis, the possibility of making an embedded Projector-camera (ProCam) system is investigated. A ProCam system is developed by our research group previously and designed for desktop Personal Computers(PCs). The system uses computer vision techniques to detect a white cardboard as the projection screen and uses particle filter to trace the screen in subsequent frames. The system demands a large computation power, unfortunately the power of low cost embedded system is still not powerful enough to implement the ProCam system.Therefore, specially designed hardware and computationally efficient algorithm are required in order to implement the ProCam system on an embedded system. / An FPGA based special processor to share the workload of the microcontroller in the embedded system is proposed and tested. This special processor will take the data stream of the camera as the inputs and apply pixel-wise image operators such as image gradient and Gaussian blur in order to extract the edge pixels. As a result, the workload of the microcontroller in the embedded system is reduced. The experiments show that the design can be implement on a low-end FPGA with a simple microcontroller. / A line tracker using Multiple Model Kalman lter is also proposed in this thesis. The aim of this tracker is to reduce the time on tracking the board. Benet from the low computation requirement of Kalman filter, the proposed line tracker can run in 200 fps on our testing embedded system. The experiments also show that the robustness of the Multiple Model Kalman filter is satisfactory and it outperforms the line trackers using single Kalman filter or extended Kalman filter alone. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Fung, Hung Kwan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 115-124). / Abstracts also in Chinese. / Abstract --- p.ii / Acknowledgement --- p.v / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation and Objective --- p.1 / Chapter 1.2 --- Contributions --- p.3 / Chapter 1.3 --- Thesis Organization --- p.5 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Introduction --- p.7 / Chapter 2.2 --- Projector-Camera System --- p.8 / Chapter 2.2.1 --- Static Projector-Screen --- p.9 / Chapter 2.2.2 --- Dynamic Projector-Screen --- p.13 / Chapter 2.3 --- Embedded Vision --- p.15 / Chapter 2.4 --- Summary --- p.25 / Chapter 3 --- System Overview --- p.26 / Chapter 3.1 --- System Design --- p.26 / Chapter 3.2 --- Our Approach --- p.28 / Chapter 3.2.1 --- Projector-camera system --- p.28 / Chapter 3.2.2 --- Smart Camera --- p.31 / Chapter 3.2.3 --- Quadrangle Detection and Tracking Module --- p.32 / Chapter 3.2.4 --- Projection Module --- p.32 / Chapter 3.3 --- Extension --- p.33 / Chapter 4 --- Smart Camera --- p.34 / Chapter 4.1 --- Introduction --- p.34 / Chapter 4.2 --- Hardware Overview --- p.35 / Chapter 4.3 --- Image Acquisition --- p.40 / Chapter 4.4 --- Image Processing --- p.42 / Chapter 4.4.1 --- RGB-to-Gray Conversion Module . --- p.44 / Chapter 4.4.2 --- Image Smoothing Module --- p.45 / Chapter 4.4.3 --- Image Gradient Module --- p.49 / Chapter 4.4.4 --- Non-maximum Suppression and Hysteresis Thresholding --- p.53 / Chapter 4.5 --- Summary --- p.55 / Chapter 5 --- Quadrangle Detection and Tracking --- p.57 / Chapter 5.1 --- Introduction --- p.57 / Chapter 5.2 --- Line Feature Extraction --- p.61 / Chapter 5.3 --- Automatic Quadrangle Detection --- p.62 / Chapter 5.4 --- Real-time Quadrangle Tracking --- p.68 / Chapter 5.4.1 --- Line Tracker --- p.69 / Chapter 5.5 --- Tracking Lose Strategy --- p.76 / Chapter 5.6 --- Recover from Tracking Failure --- p.77 / Chapter 5.7 --- Summary --- p.77 / Chapter 6 --- Implementation and Experiment Result --- p.79 / Chapter 6.1 --- Introduction --- p.79 / Chapter 6.2 --- Smart Camera --- p.79 / Chapter 6.3 --- Line Tracking --- p.87 / Chapter 7 --- Limitation and Discussion --- p.101 / Chapter 7.1 --- Introduction --- p.101 / Chapter 7.2 --- Limitation --- p.101 / Chapter 7.3 --- Summary --- p.105 / Chapter 8 --- Application --- p.107 / Chapter 8.1 --- Introduction --- p.107 / Chapter 8.2 --- Portable Projector-Camera System --- p.107 / Chapter 8.3 --- Summary --- p.110 / Chapter 9 --- Conclusion --- p.112 / Bibliography --- p.115

Cheung Chak Chung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 101-114). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgments --- p.iii / Vita --- p.v / Table of Contents --- p.vi / List of Figures --- p.x / List of Tables --- p.xiv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Aims and Contribution --- p.4 / Chapter 1.3 --- Thesis Overview --- p.5 / Chapter 2 --- VLSI Design Cycle --- p.6 / Chapter 2.1 --- Logic Synthesis --- p.7 / Chapter 2.1.1 --- Logic Minimization --- p.8 / Chapter 2.1.2 --- Technology Mapping --- p.8 / Chapter 2.1.3 --- Testability --- p.8 / Chapter 2.2 --- Physical Design Synthesis --- p.8 / Chapter 2.2.1 --- Partitioning --- p.9 / Chapter 2.2.2 --- Floorplanning & Placement --- p.10 / Chapter 2.2.3 --- Routing --- p.11 / Chapter 2.2.4 --- "Compaction, Extraction & Verification" --- p.12 / Chapter 2.2.5 --- Physical Design of FPGAs --- p.12 / Chapter 3 --- Alternative Wiring --- p.13 / Chapter 3.1 --- Introduction --- p.13 / Chapter 3.2 --- Notation and Definitions --- p.15 / Chapter 3.3 --- Application of Rewiring --- p.17 / Chapter 3.3.1 --- Logic Optimization --- p.17 / Chapter 3.3.2 --- Timing Optimization --- p.17 / Chapter 3.3.3 --- Circuit Partitioning and Routing --- p.18 / Chapter 3.4 --- Logic Optimization Analysis --- p.19 / Chapter 3.4.1 --- Global Flow Optimization --- p.19 / Chapter 3.4.2 --- OBDD Representation --- p.20 / Chapter 3.4.3 --- Automatic Test Pattern Generation (ATPG) --- p.22 / Chapter 3.4.4 --- Graph Based Alternative Wiring (GBAW) --- p.23 / Chapter 3.5 --- Augmented GBAW --- p.26 / Chapter 3.6 --- Logic Optimization by using GBAW --- p.28 / Chapter 3.7 --- Conclusions --- p.31 / Chapter 4 --- Multi-way Partitioning using Rewiring Techniques --- p.33 / Chapter 4.1 --- Introduction --- p.33 / Chapter 4.2 --- Circuit Partitioning Algorithm Analysis --- p.38 / Chapter 4.2.1 --- The Kernighan-Lin (KL) Algorithm --- p.39 / Chapter 4.2.2 --- The Fiduccia-Mattheyses (FM) Algorithm --- p.42 / Chapter 4.2.3 --- Geometric Representation Algorithm --- p.46 / Chapter 4.2.4 --- The Multi-level Partitioning Algorithm --- p.49 / Chapter 4.2.5 --- Hypergraph METIS - hMETIS --- p.51 / Chapter 4.3 --- The GBAW Partitioning Algorithm --- p.53 / Chapter 4.4 --- Experimental Results --- p.56 / Chapter 4.5 --- Conclusions --- p.58 / Chapter 5 --- Optimum FPGA Switch-Box Designs - HUSB --- p.62 / Chapter 5.1 --- Introduction --- p.62 / Chapter 5.2 --- Background and Definitions --- p.65 / Chapter 5.2.1 --- Routing Architectures --- p.65 / Chapter 5.2.2 --- Global Routing --- p.67 / Chapter 5.2.3 --- Detailed Routing --- p.67 / Chapter 5.3 --- FPGA Router Comparison --- p.69 / Chapter 5.3.1 --- CGE --- p.69 / Chapter 5.3.2 --- SEGA --- p.70 / Chapter 5.3.3 --- TRACER --- p.71 / Chapter 5.3.4 --- VPR --- p.72 / Chapter 5.4 --- Switch Box Design --- p.73 / Chapter 5.4.1 --- Disjoint type switch box (XC4000-type) --- p.73 / Chapter 5.4.2 --- Anti-symmetric switch box --- p.74 / Chapter 5.4.3 --- Universal Switch box --- p.74 / Chapter 5.4.4 --- Switch box Analysis --- p.75 / Chapter 5.5 --- Terminology --- p.77 / Chapter 5.6 --- "Hyper-universal (4, W)-design analysis" --- p.82 / Chapter 5.6.1 --- "H3 is an optimum (4, 3)-design" --- p.84 / Chapter 5.6.2 --- "H4 is an optimum (4,4)-design" --- p.88 / Chapter 5.6.3 --- "Hi is a hyper-universal (4, i)-design for i = 5,6,7" --- p.90 / Chapter 5.7 --- Experimental Results --- p.92 / Chapter 5.8 --- Conclusions --- p.95 / Chapter 6 --- Conclusions --- p.99 / Chapter 6.1 --- Thesis Summary --- p.99 / Chapter 6.2 --- Future work --- p.100 / Chapter 6.2.1 --- Alternative Wiring --- p.100 / Chapter 6.2.2 --- Partitioning Quality --- p.100 / Chapter 6.2.3 --- Routing Devices Studies --- p.100 / Bibliography --- p.101 / Chapter A --- 5xpl - Berkeley Logic Interchange Format (BLIF) --- p.115 / Chapter B --- Proof of some 2-local patterns --- p.122 / Chapter C --- Illustrations of FM algorithm --- p.124 / Chapter D --- HUSB Structures --- p.127 / Chapter E --- Primitive minimal 4-way global routing Structures --- p.132

Background noise is particularly damaging to speech intelligibility for people with hearing loss. The problem of reducing noise in hearing aids is one of great importance and great difficulty. Over the years, many solutions and different algorithms have been implemented in order to provide the optimal solution to the problem. Beamforming has been used for a long time and has therefore been extensively researched. Studying the performance of Minimum Variance Distortionless Response (MVDR) beamforming with a three- and four- microphone array compared to the conventional two-microphone array, the aim is to implement a speech signal enhancement and a noise reduction algorithm. By using multiple microphones, it is possible to achieve spatial selectivity, which is the ability to select certain signals based on the angle of incidence, and improve the performance of noise reduction beamformers. This thesis proposes the use of beamforming, an existing technique in order to create a new way to reduce noise transmitted by hearing aids. In order to reduce the complexity of that system, we use hybrid cascades, which are simpler beamformers of two inputs each and connected in series. The configurations that we consider are a three-microphone linear array (monaural beamformer), a three-microphone configuration with a two-microphone linear array and the 3rd microphone in the ear (monaural beamformer), a three-microphone configuration with a two-microphone linear array and the 3rd microphone on contra-lateral ear (binaural beamformer), and finally four-microphone configurations. We also investigate the performance improvement of the beamformer with more than two microphones for the different configurations, against the two-microphone beamformer reference. This can be measured by using objective measurements, such as the amount of noise suppression, target energy loss, output SNR, speech intelligibility index and speech quality evaluation. These objective measurements are good indicators of subjective performance. In this project, we prove that most hybrid structures can perform satisfyingly well compared to the full complexity beamformer. The low complexity beamformer is designed with a fixed target location (azimuth), where its weights are calibrated with respect to a target signal located in front of the listener and for a diffuse noise field. Both second- and third- order beamformers are tested in different acoustic scenarios, such as a car environment, a meeting room, a party occasion and a restaurant place. In those scenarios, the target signal is not arriving at the hearing aid directly from the front side of the listener and the noise field is not always diffuse. We thoroughly investigate what are the performance limitations in that case and how well the different cascades can perform. It is proven that there are some very critical factors, which can affect the performance of the fixed beamformer, concerning all the hybrid structures that were examined. Finally, we show that lower complexity cascades for both second- and third- order beamformers can perform similarly well as the full complexity beamformers when tested for a set of multiple Head Related Transfer Functions (HRTFs) that correspond to a real head shape.