by Wan Wai Leung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 77-[80]). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Wireless Multimedia System --- p.1 / Chapter 1.2 --- Motivation of this thesis --- p.2 / Chapter 1.3 --- The theme of this thesis --- p.4 / Chapter 1.3.1 --- System Model and Assumptions --- p.4 / Chapter 1.3.2 --- Outline of the thesis --- p.5 / Chapter 2 --- Overview of TDMA/FDMA Digital Cellular Systems --- p.7 / Chapter 2.1 --- The Cellular Concept --- p.7 / Chapter 2.2 --- Channel Assignment Strategies --- p.9 / Chapter 2.2.1 --- Fixed Channel Assignment --- p.9 / Chapter 2.2.2 --- Dynamic Channel Assignment --- p.9 / Chapter 2.3 --- Multiple Access Techniques --- p.10 / Chapter 2.3.1 --- Introduction to Multiple Access --- p.10 / Chapter 2.3.2 --- Frequency Division Multiple Access - FDMA --- p.11 / Chapter 2.3.3 --- Time Division Multiple Access - TDMA --- p.12 / Chapter 2.4 --- A TDMA/FDMA System - GSM --- p.13 / Chapter 2.4.1 --- Global System for Mobile --- p.13 / Chapter 2.4.2 --- GSM radio subsystem --- p.13 / Chapter 3 --- Multi-rate Data in TDMA/FDMA Digital Cellular Systems --- p.17 / Chapter 3.1 --- Incorporation of Multimedia Data --- p.17 / Chapter 3.2 --- A Global Optimal Strategy --- p.19 / Chapter 3.2.1 --- Channel Rearrangement --- p.19 / Chapter 3.2.2 --- Analytical Performance Analysis of a Special Case --- p.21 / Chapter 3.2.3 --- Numerical Results --- p.24 / Chapter 3.2.4 --- Issues in Channel Rearrangement --- p.25 / Chapter 4 --- Multiple Slots Allocations --- p.26 / Chapter 4.1 --- Introduction --- p.26 / Chapter 4.2 --- No-Split Algorithm --- p.27 / Chapter 4.2.1 --- No-Split Algorithm --- p.27 / Chapter 4.2.2 --- Pros and Cons --- p.28 / Chapter 4.3 --- Best Fit Algorithm --- p.29 / Chapter 4.3.1 --- Best Fit Algorithm --- p.29 / Chapter 4.3.2 --- Optimization --- p.31 / Chapter 4.3.3 --- Pros and Cons --- p.32 / Chapter 4.4 --- Comparison of the two algorithms --- p.32 / Chapter 5 --- Buddy Algorithm --- p.37 / Chapter 5.1 --- Introduction --- p.37 / Chapter 5.2 --- Buddy System in Memory Management --- p.38 / Chapter 5.3 --- Buddy Algorithm --- p.40 / Chapter 5.3.1 --- Adaptation in slot allocation --- p.40 / Chapter 5.3.2 --- Data structure --- p.40 / Chapter 5.3.3 --- Slot allocation --- p.40 / Chapter 5.3.4 --- Slot deallocation --- p.44 / Chapter 5.4 --- Inference Property --- p.45 / Chapter 5.4.1 --- Proof of the Inference Property --- p.47 / Chapter 5.5 --- Pros and Cons --- p.49 / Chapter 6 --- Performance Study --- p.51 / Chapter 6.1 --- Introduction --- p.51 / Chapter 6.2 --- Fixed Channel Assignment --- p.52 / Chapter 6.2.1 --- System Parameters --- p.52 / Chapter 6.2.2 --- Simulation Results --- p.53 / Chapter 6.3 --- Dynmaic Channel Assignment --- p.55 / Chapter 6.3.1 --- System Parameters --- p.55 / Chapter 6.3.2 --- Simulation Results --- p.56 / Chapter 7 --- A Case Study - H.263 Video Coding --- p.59 / Chapter 7.1 --- CCITT H.263 Image Compression --- p.59 / Chapter 7.2 --- On a GSM Network --- p.60 / Chapter 8 --- Conclusion --- p.63 / Chapter A --- A General Data + Voice System with Channel Rearrangement --- p.65 / Chapter A.1 --- System Model --- p.65 / Chapter A.2 --- Markovian Analysis --- p.66 / Chapter B --- NP-Completeness Proof of the Best Fit Algorithm --- p.69 / Chapter B.1 --- CONSTRAINT SUBSET-SUM Problem --- p.69 / Chapter B.2 --- BEST-FIT Problem --- p.72 / Chapter C --- Proof of Proposition 5.2 --- p.74 / Chapter C.1 --- Upper Bound on Demand Advancement --- p.74 / Chapter C.2 --- Proof of Proposition 5.2 --- p.75 / Bibliography --- p.77

by Walter Chi-Woon Fung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 64-[67]). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- Limitation of Existing Research --- p.3 / Chapter 1.3 --- Contributions of This Thesis --- p.3 / Chapter 1.4 --- Organization of the Thesis --- p.4 / Chapter 2 --- Related Work --- p.5 / Chapter 2.1 --- Ongoing Efforts For The Support of Real Time Applications on the Internet - RTP --- p.5 / Chapter 2.2 --- Using the Algorithm on top of RTP --- p.7 / Chapter 3 --- An Adaptive Video Retrieval Algorithm --- p.9 / Chapter 3.1 --- Lossless Environment --- p.9 / Chapter 3.1.1 --- Adapting the Request Rate to the Available Bandwidth --- p.12 / Chapter 3.2 --- Lossy Environment --- p.17 / Chapter 3.2.1 --- Adapting Ar in Lossy Environment --- p.20 / Chapter 3.3 --- Adjusting the Window Size --- p.24 / Chapter 3.4 --- Measurement Issues --- p.27 / Chapter 3.5 --- Mapping between Data Rate and Frame Rate --- p.28 / Chapter 4 --- Rate Measurement --- p.30 / Chapter 4.1 --- Arrival Rate Estimation --- p.30 / Chapter 4.2 --- Loss Rate Estimation --- p.32 / Chapter 5 --- Frame Skipping and Stuffing --- p.37 / Chapter 5.1 --- MPEG-1 Video Stream Basics --- p.37 / Chapter 5.2 --- Frame Skipping --- p.38 / Chapter 5.3 --- Frame Stuffing In Lossy Environment --- p.40 / Chapter 6 --- Experiment Result and Analysis --- p.43 / Chapter 6.1 --- Experiment --- p.43 / Chapter 6.2 --- Analysis --- p.54 / Chapter 6.2.1 --- Interacting With Streams With No Rate Control --- p.56 / Chapter 6.2.2 --- Multiple Streams Running The Algorithm --- p.58 / Chapter 6.2.3 --- Calculation of p --- p.59 / Chapter 7 --- Conclusions --- p.61 / Bibliography --- p.64

Lee, Hiu Fung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 80-82). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese.

Zhang, Yupeng. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 45-48). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese.

Cheong Chi Hong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 81-86). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.v / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problem statement --- p.1 / Chapter 1.2 --- Major contributions --- p.4 / Chapter 1.3 --- Thesis organization --- p.4 / Chapter 2 --- Smart Card System --- p.6 / Chapter 2.1 --- Introduction --- p.7 / Chapter 2.2 --- Related Work --- p.11 / Chapter 2.2.1 --- Mining Customer Behaviors --- p.11 / Chapter 2.2.2 --- Privacy Preserving Data Mining --- p.12 / Chapter 2.2.3 --- Definitions of Privacy --- p.13 / Chapter 2.3 --- Model --- p.14 / Chapter 2.4 --- Algorithms --- p.17 / Chapter 2.4.1 --- Baseline Algorithm --- p.17 / Chapter 2.4.2 --- Privacy Equation --- p.19 / Chapter 2.4.3 --- Random Subsequence Selection Algorithm (RSSA) --- p.20 / Chapter 2.4.4 --- Popular Item Selection Algorithm (PISA) --- p.21 / Chapter 2.5 --- Analysis --- p.26 / Chapter 2.5.1 --- Accuracy --- p.26 / Chapter 2.5.2 --- Analysis of RSSA: Determine te values --- p.27 / Chapter 2.5.3 --- Analysis of RSSA: Accuracy --- p.30 / Chapter 2.5.4 --- Analysis of PISA --- p.33 / Chapter 2.5.5 --- Theoretical Proof of PISA --- p.41 / Chapter 2.5.6 --- Privacy Protection --- p.42 / Chapter 2.6 --- Simulations --- p.45 / Chapter 3 --- Transportation System --- p.48 / Chapter 3.1 --- Introduction --- p.49 / Chapter 3.2 --- Related Work --- p.51 / Chapter 3.3 --- Model --- p.56 / Chapter 3.4 --- Algorithms --- p.60 / Chapter 3.5 --- Simulations --- p.63 / Chapter 4 --- Enhanced Features in a Smart Card System --- p.67 / Chapter 4.1 --- Adding Time Information --- p.68 / Chapter 4.1.1 --- Motivation --- p.68 / Chapter 4.1.2 --- Time Intervals --- p.68 / Chapter 4.1.3 --- Original Graph --- p.69 / Chapter 4.1.4 --- New Graph --- p.70 / Chapter 4.1.5 --- Adding the New Graph into the Model --- p.72 / Chapter 4.1.6 --- Rewriting the Definition of a Path --- p.73 / Chapter 4.1.7 --- Drawback of Adding Time Information --- p.73 / Chapter 4.2 --- Generalization --- p.75 / Chapter 4.2.1 --- Motivation --- p.75 / Chapter 4.2.2 --- Generalization --- p.75 / Chapter 4.3 --- Specialization vs. Generalization --- p.75 / Chapter 5 --- Conclusion --- p.79 / Bibliography --- p.81

Several algorithms for Public Key Cryptography (PKC), such as RSA, Diffie-Hellman, and Elliptic Curve Cryptography, require modular multiplication of very large operands (sizes from 160 to 4096 bits) as their core arithmetic operation. To perform this operation reasonably fast, general purpose processors are not always the best choice. This is why specialized hardware, in the form of cryptographic co-processors, become more attractive. Based upon the analysis of recent publications on hardware design for modular multiplication, this M.S. thesis presents a new architecture that is scalable with respect to word size and pipelining depth. To our knowledge, this is the first time a word based algorithm for Montgomery's method is realized using high-radix bit-parallel multipliers working with two different types of finite fields (unified architecture for GF(p) and GF(2n)). Previous approaches have relied mostly on bit serial multiplication in combination with massive pipelining, or Radix-8 multiplication with the limitation to a single type of finite field. Our approach is centered around the notion that the optimal delay in bit-parallel multipliers grows with logarithmic complexity with respect to the operand size n, O(log3/2 n), while the delay of bit serial implementations grows with linear complexity O(n). Our design has been implemented in VHDL, simulated and synthesized in 0.5μ CMOS technology. The synthesized net list has been verified in back-annotated timing simulations and analyzed in terms of performance and area consumption.

General purpose operating systems have been designed to provide fast, loss-free disk service to all applications. However, multimedia applications are capable of tolerating some data loss, but are very sensitive to variation in disk service timing. Present research efforts to handle multimedia applications assume pessimistic disk behaviour when deciding to admit new multimedia connections so as not to violate the real-time application constraints. However, since multimedia applications are ``soft' real-time applications that can tolerate some loss, we propose an optimistic scheme for admission control which uses average case values for disk access. Typically, disk scheduling mechanisms for multimedia applications reduce disk access times by only trying to minimize movement to subsequent blocks after sequencing based on Earliest Deadline First. We propose to implement a disk scheduling algorithm that uses knowledge of the media stored and permissible loss and jitter for each client, in addition to the physical parameters used by the other scheduling algorithms. We will evaluate our approach by implementing our admission control policy and disk scheduling algorithm in Linux and measuring the quality of various multimedia streams. If successful, the contributions of this thesis are the development of new admission control and flexible disk scheduling algorithm for improved multimedia quality of service.

This dissertation is motivated by the pressing need for solving real-world large-scale optimization problems with the main objective of developing scalable algorithms that are capable of solving such problems efficiently. Large-scale optimization problems naturally appear in complex systems such as power networks and distributed control systems, which are the main systems of interest in this work. This dissertation aims to address four problems with regards to the theory and application of large-scale optimization problems, which are explained below: Chapter 2: In this chapter, a fast and parallelizable algorithm is developed for an arbitrary decomposable semidefinite program (SDP). Based on the alternating direction method of multipliers, we design a numerical algorithm that has a guaranteed convergence under very mild assumptions. We show that each iteration of this algorithm has a simple closed-form solution, consisting of matrix multiplications and eigenvalue decompositions performed by individual agents as well as information exchanges between neighboring agents. The cheap iterations of the proposed algorithm enable solving a wide spectrum of real-world large-scale conic optimization problems that could be reformulated as SDP. Chapter 3: Motivated by the application of sparse SDPs to power networks, the objective of this chapter is to design a fast and parallelizable algorithm for solving the SDP relaxation of a large-scale optimal power flow (OPF) problem. OPF is fundamental problem used for the operation and planning of power networks, which is non-convex and NP-hard in the worst case. The proposed algorithm would enable a real-time power network management and improve the system's reliability. In particular, this algorithm helps with the realization of Smart Grid by allowing to make optimal decisions very fast in response to the stochastic nature of renewable energy. The proposed algorithm is evaluated on IEEE benchmark systems. Chapter 4: The design of an optimal distributed controller using an efficient computational method is one of the most fundamental problems in the area of control systems, which remains as an open problem due to its NP-hardness in the worst case. In this chapter, we first study the infinite-horizon optimal distributed control (ODC) problem (for deterministic systems) and then generalize the results to a stochastic ODC problem (for stochastic systems). Our approach rests on formulating each of these problems as a rank-constrained optimization from which an SDP relaxation can be derived. We show that both problems admit sparse SDP relaxations with solutions of rank at most~3. Since a rank-1 SDP matrix can be mapped back into a globally-optimal controller, the rank-3 solution may be deployed to retrieve a near-global controller. We also propose computationally cheap SDP relaxation for each problem and then develop effective heuristic methods to recover a near-optimal controller from the low-rank SDP solution. The design of several near-optimal structured controllers with global optimality degrees above 99\% will be demonstrated. Chapter 5: The frequency control problem in power networks aims to control the global frequency of the system within a tight range by adjusting the output of generators in response to the uncertain and stochastic demand. The intermittent nature of distributed power generation in smart grid makes the traditional decentralized frequency controllers less efficient and demands distributed controllers that are able to deal with the uncertainty in the system introduced by non-dispatchable supplies (such as renewable energy), fluctuating loads, and measurement noise. Motivated by this need, we study the frequency control problem using the results developed in Chapter 4. In particular, we formulate the problem and then conduct a case study on the IEEE 39-Bus New England system. The objective is to design a near-global optimal distributed frequency controller for the New England test system by optimally adjusting the mechanical power input to each generator based on the real-time measurement received from neighboring generators through a user-defined communication topology.

(I) Architectural revisions: Probably due to historical reasons, programmable switches on conventional FPGA architectures are divided into two kinds of substructures: Connection boxes (C-boxes) and Switch boxes (S-boxes), where C-boxes are used to connect logic/pad pins with their crossing wire segments, and S-boxes are used to connect wire segments of surrounding routing channels. In this work, we will challenge if this divided C- and S-boxes structure is really necessary and will explore a new experimental architecture which adopts only one kind of switching components - Connection-Switch boxes (CS-boxes). Extensive experiments are conducted on MCNC benchmark circuits to justify its architectural performance impacts. The results show that this CS-box based FPGA outperforms the conventional FPGA in terms of channel width, circuit delay, and segment usage. Besides an over 20% drastic dropping in the total number of manufactured switches needed, circuit delay performance is improved by 10% under the usage of the same pin assignments and router. / (II) New EDA technique/flow: By applying circuit rewirings, logic perturbations can be carried out by shifting logic resources from perhaps costly Look-Up-Table (LUT) external to cost-free LUT internal areas, or from critical to non-critical paths. This work presents a simple, while effective and low-overhead postlayout logic perturbation scheme for improving LUT-based FPGA routings without altering placements. A rewiring-based logic perturbation technique is used to improve upon a timing-driven FPGA P&R tool - TVPR. Compared with the already high-quality pure TVPR results, our approach reduces critical path delay by up to 31.74% (avg. 11%) without disturbing the placement or sacrificing chip areas, where only 4% of the nets are perturbed in our scheme. The complexity of our algorithm is linear in the total number of nets of the circuit. The experimental results show that the CPU time used by the rewiring engine is only 5% of the total time consumed by the placement and routing of TVPR. / Based on these studies, we believe the prospect for FPGA performance improvement is still quite profound in both architectural and EDA aspects. On the EDA technique, we have also performed logic perturbations to improve both the technology mapping and routing to investigate the effectiveness of the logic perturbation if applied in a larger context. The results show that a best technology mapping is not always leading to a best final routing, which seems to suggest that an ideal FPGA EDA flow should consider more on trade-offs between different stages. To the best of our knowledge, this is the first work exploring the power of logic perturbations applied for multiple physical stages for LUT-based FPGAs. The encouraging hardware improvement shown in our proposed CS-box based FPGAs seems to suggest a new design direction for FPGA routing architectures. / With the advent of deep submicron technologies, the extreme high design and mask costs incurred for ASICs have made FPGAs an increasingly popular hardware implementation option. However, it has been shown that the programmable routing structure underlined contributes over 60% of the signal delay and as high as 90% of the total chip area. As a result, current FPGAs still cannot meet performance requirements of many high-end applications. To attack this issue, we propose new solutions along the two major tracks: (I) architectural revisions (hardware) and (II) new EDA technique/flow (software). / Zhou Lin. / "October 2007." / Adviser: Yu-Liang Wu. / Source: Dissertation Abstracts International, Volume: 69-08, Section: B, page: 4953. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 101-108). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

by Kwok-Shing Cheng. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 114-120). / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Importance of Text Compression --- p.1 / Chapter 1.2 --- Motivation of this Research --- p.2 / Chapter 1.3 --- Characteristics of Chinese --- p.2 / Chapter 1.3.1 --- Huge size of character set --- p.3 / Chapter 1.3.2 --- Lack of word segmentation --- p.3 / Chapter 1.3.3 --- Rich semantics --- p.3 / Chapter 1.4 --- Different Coding Schemes for Chinese --- p.4 / Chapter 1.4.1 --- Big5 Code --- p.4 / Chapter 1.4.2 --- GB (Guo Biao) Code --- p.4 / Chapter 1.4.3 --- HZ (Hanzi) Code --- p.5 / Chapter 1.4.4 --- Unicode Code --- p.5 / Chapter 1.5 --- Modeling and Coding for Chinese Text --- p.6 / Chapter 1.6 --- Static and Adaptive Modeling --- p.6 / Chapter 1.7 --- One-Pass and Two-Pass Modeling --- p.8 / Chapter 1.8 --- Ordering of models --- p.9 / Chapter 1.9 --- Two Sets of Benchmark Files and the Platform --- p.9 / Chapter 1.10 --- Outline of the Thesis --- p.11 / Chapter 2 --- A Survey of Chinese Text Compression --- p.13 / Chapter 2.1 --- Entropy for Chinese Text --- p.14 / Chapter 2.2 --- Weakness of Traditional Compression Algorithms on Chinese Text --- p.15 / Chapter 2.3 --- Statistical Class Algorithms for Compressing Chinese --- p.16 / Chapter 2.3.1 --- Huffman coding scheme --- p.17 / Chapter 2.3.2 --- Arithmetic Coding Scheme --- p.22 / Chapter 2.3.3 --- Restricted Variable Length Coding Scheme --- p.26 / Chapter 2.4 --- Dictionary-based Class Algorithms for Compressing Chinese --- p.27 / Chapter 2.5 --- Experiments and Results --- p.32 / Chapter 2.6 --- Chapter Summary --- p.35 / Chapter 3 --- Indicator Dependent Huffman Coding Scheme --- p.37 / Chapter 3.1 --- Chinese Character Identification Routine --- p.37 / Chapter 3.2 --- Reduction of Header Size --- p.39 / Chapter 3.3 --- Semi-adaptive IDC for Chinese Text --- p.44 / Chapter 3.3.1 --- Theoretical Analysis of Partition Technique for Com- pression --- p.48 / Chapter 3.3.2 --- Experiments and Results of the Semi-adaptive IDC --- p.50 / Chapter 3.4 --- Adaptive IDC for Chinese Text --- p.54 / Chapter 3.4.1 --- Experiments and Results of the Adaptive IDC --- p.57 / Chapter 3.5 --- Chapter Summary --- p.58 / Chapter 4 --- Cascading LZ Algorithms with Huffman Coding Schemes --- p.59 / Chapter 4.1 --- Variations of Huffman Coding Scheme --- p.60 / Chapter 4.1.1 --- Analysis of EPDC and PDC --- p.60 / Chapter 4.1.2 --- "Analysis of PDC, 16Huff and IDC" --- p.65 / Chapter 4.1.3 --- Time and Memory Consumption --- p.71 / Chapter 4.2 --- "Cascading LZSS with PDC, 16Huff and IDC" --- p.73 / Chapter 4.2.1 --- Experimental Results --- p.76 / Chapter 4.3 --- "Cascading LZW with PDC, 16Huff and IDC" --- p.79 / Chapter 4.3.1 --- Experimental Results --- p.82 / Chapter 4.4 --- Chapter Summary --- p.84 / Chapter 5 --- Applying Compression Algorithms to Word-segmented Chi- nese Text --- p.85 / Chapter 5.1 --- Background of word-based compression algorithms --- p.86 / Chapter 5.2 --- Terminology and Benchmark Files for Word Segmentation Model --- p.88 / Chapter 5.3 --- Word Segmentation Model --- p.88 / Chapter 5.4 --- Chinese Entropy from Byte to Word --- p.91 / Chapter 5.5 --- The Generalized Compression and Decompression Model for Word-segmented Chinese text --- p.92 / Chapter 5.6 --- Applying Huffman Coding Scheme to Word-segmented Chinese text --- p.94 / Chapter 5.7 --- Applying WLZSSHUF to Word-segmented Chinese text --- p.97 / Chapter 5.8 --- Applying WLZWHUF to Word-segmented Chinese text --- p.102 / Chapter 5.9 --- Match Ratio and Compression Ratio --- p.105 / Chapter 5.10 --- Chapter Summary --- p.108 / Chapter 6 --- Concluding Remarks --- p.110 / Chapter 6.1 --- Conclusions --- p.110 / Chapter 6.2 --- Contributions --- p.111 / Chapter 6.3 --- Future Directions --- p.112 / Chapter 6.3.1 --- Integrate Decremental Coding Scheme with IDC --- p.112 / Chapter 6.3.2 --- Re-order the Character Sequences in the Sliding Window of LZSS --- p.113 / Chapter 6.3.3 --- Multiple Huffman Trees for Word-based Compression --- p.113 / Bibliography --- p.114