by Cheng Shu Ling. / Thesis submitted in: July 1997. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 70-71). / Abstract also in Chinese. / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Image Coding Standard: JPEG --- p.1 / Chapter 1.2 --- Video Coding Standard: MPEG --- p.6 / Chapter 1.2.1 --- MPEG history --- p.6 / Chapter 1.2.2 --- MPEG video compression algorithm overview --- p.8 / Chapter 1.2.3 --- More MPEG features --- p.10 / Chapter 1.3 --- Summary --- p.17 / Chapter Chapter 2 --- Error Resiliency --- p.18 / Chapter 2.1 --- Introduction --- p.18 / Chapter 2.2 --- Traditional approaches --- p.19 / Chapter 2.2.1 --- Channel coding --- p.19 / Chapter 2.2.2 --- ARQ --- p.20 / Chapter 2.2.3 --- Multi-layer coding --- p.20 / Chapter 2.2.4 --- Error Concealment --- p.20 / Chapter 2.3 --- MPEG-4 work on error resilience --- p.21 / Chapter 2.3.1 --- Resynchronization --- p.21 / Chapter 2.3.2 --- Data Recovery --- p.25 / Chapter 2.3.3 --- Error Concealment --- p.28 / Chapter 2.4 --- Summary --- p.29 / Chapter Chapter 3 --- Fixed length codes --- p.30 / Chapter 3.1 --- Introduction --- p.30 / Chapter 3.2 --- Tunstall code --- p.31 / Chapter 3.3 --- Lempel-Ziv code --- p.34 / Chapter 3.3.1 --- LZ-77 --- p.35 / Chapter 3.3.2 --- LZ-78 --- p.36 / Chapter 3.4 --- Simulation --- p.38 / Chapter 3.4.1 --- Experiment Setup --- p.38 / Chapter 3.4.2 --- Results --- p.39 / Chapter 3.4.3 --- Concluding Remarks --- p.42 / Chapter Chapter 4 --- Self-Synchronizable codes --- p.44 / Chapter 4.1 --- Introduction --- p.44 / Chapter 4.2 --- Scholtz synchronizable code --- p.45 / Chapter 4.2.1 --- Definition --- p.45 / Chapter 4.2.2 --- Construction procedure --- p.45 / Chapter 4.2.3 --- Synchronizer --- p.48 / Chapter 4.2.4 --- Effects of errors --- p.51 / Chapter 4.3 --- Simulation --- p.52 / Chapter 4.3.1 --- Experiment Setup --- p.52 / Chapter 4.3.2 --- Results --- p.56 / Chapter 4.4 --- Concluding Remarks --- p.68 / Chapter Chapter 5 --- Conclusions --- p.69 / References --- p.70

在通信網絡中，當我們要傳輸私密信息時，可能有一些非法用戶希望能獲取這些私密信息。在這裡，我們分別稱這個網絡模型模型和非法用戶為竊聽網絡和竊聽者。在本文中，我們希望在某些限制條件下，設計一種編碼來抵抗竊聽者。 / 為了保護私密信息，我們不會在網絡中直接傳遞它，而是傳遞一些加密過的信息，即密文。現在通行的一個方法是:用一些隨機生成的密碼給這些私密信息加密。即使竊聽者能獲取我傳遞的密文，也無法知道確切的私密信息。在本中文，我們考慮了兩種安全級別:完美安全和非完美安全。在完美安全中，密文和私密信息從統計上講是完全獨立的，也就是說竊聽者得到的是一些安全隨機的信息。在非完美安全中，竊聽者被允許獲得一部私密信息。這部分私密信息，是由竊聽者的信息模糊度來衡量的。如果信息模糊度的大小等於私密信息，那麼非完美安全等價於完美安全。 / 本文的重點在於如何以最小的代價保護私密的信息。我們用Ç =(V ， Σ) 來表示通信網絡。其中， ν是所有節點的集合，Σ 是所有信道的集合。一個竊聽者能夠監聽某些信道上的信息。在我們的模型中，每個竊聽者竊聽的信道的集合是固定的。所有這些被竊聽的信道構成了一個竊聽集。我們把所有竊聽集的集合記作A 。 / 在竊聽網絡中，如果考慮完美安全，現有的工作表明，當A是由所有大小為r 的 Σ的子集構成的時候，存在一個線性網絡編碼，在下面兩個標準下是最優的: / 1)私 密信息的長度最大化; / 2) 隨即密鑰的長度最小化。但是，當A 由任意的5 的子集構成的時候，關於性能界的結果很少。 / 在本文的第一部分中，我們著手研究這個方面的問題並得到了以下結論: / 1) 對於私密信息的長度，我們獲得了一個上界並提供了一個多項式算法去計算它。 / 2)對於隨機密鑰的長度，我們從分教覆蓋和分數包裝的為度進行分析，分別獲得了兩個下界。這兩個下界， 我們證明了他們之間存在一個對偶性。接下來，我們討論暸如何去計算這個下界，我們設計了一個暴力算法和一個關於 / 接下來，我們更關注於點對點系統中的非完美安全問題。我們推廣了一個經典的安全模型: II型竊聽信道。在經典的II型竊聽信道模型中，私密信息是通過若干端到端的信道發送的。在這個模型中，假設每個竊聽者只能竊聽A 中的一個竊聽集，其中A是由所有大小為r的信道集構成。在這裡，保護私密信息的策略也和竊聽網絡中一樣。更確切的，我們可以找到一個關於隨機密碼長度的下界，而且這個下界可以通過一個群編碼獲得。我們在推廣中假設A的構成是任意的，每個竊聽者被允許獲得一定的私密信息。在這個模型下，我們定義了關於私密信息，隨機密碼，每個竊聽者的信息模糊度的一個元組。關於這個元組，我們獲得了一個緊的區域。這個區域可以看成是竊聽網絡上關於割集的一個界。 / In a communication network on which a secure message is transmitted, there may exist illegal users who want to obtain information about the message. Here we refer to the network and those illegal users as the wiretap network and wiretappers, respectively. In secure network coding, we aim to find a network code which can protect the message against the wiretappers under certain constraints. / To protect the message we transmit a ciphertext which is a mixture of the message and a private random key, through the channels in the network. In this work, we consider two kinds of security levels: perfect security and imperfect security. In perfect security, the cipher-text is statistically independent of the message, i.e., the wiretapper can obtain only some randomly generated messages. While in imperfect security, the wiretapper can obtain partial information about the message which is measured by the wiretapper's equivocation. If the wiretapper's equivocation is equal to the message size, then the imperfect security reduces to perfect security. / The focus of our work is to protect the message at the minimum cost, which is measured by the size the key and the bandwidth of the network. Here we denote the network by Ç = (V; Σ), where V is the set of nodes and Σ is the set of point-to-point channels in the network. A wiretapper may access the information transmitted on a certain subset of Σ. In our model, it is assumed that the wiretapper can access any one but not more than one set of channels, called a wiretap set, out of a collection A of all possible wiretap sets. / In a wiretap network, if perfect security is required, existing works show that when A consists of all the r -subsets of Σ (i.e. subsets of size r), there exists a linear network code, which is optimal according to the following two criteria: / i) the size of the message is maximum; / ii) the size of random key is minimum. / But when A consists of arbitrary subsets of Σ, very little is known about the fundamental performance limit. / In the first part of our work, we investigate this problem and obtain some results on the above fundamental performance limits. In this work, we adopt the convention that the size of a random variable X is measured by its entropy H(X). / 1) For the size of the message, we derive an upper bound on H(M) and provide a polynomial algorithm to compute it. / 2) For the size of the key, we analyze it from the aspects of fractional covering and fractional packing, respectively, by which we obtain two bounds on H(K) and we prove the duality between them. n520 Then we discuss the algorithms to compute the lower bound, in- cluding a brute force algorithm and a polynomial algorithm in terms of / In the remaining part, we are largely concerned with imperfect security in a point-to-point communication system, where a classical security model referred to as the wire-tap channel II is generalized by introducing imperfect security. In wire-tap channel II, information is sent to the receiver through a set of point-to-point channels. It is assumed that the wiretapper can access any one but not more than one set in A which consists of all the subsets of the channel set with size r. The strategy to protect the private message is the same as that in the wiretap network. Specifically, a lower bound on the size of the key which can be attained by a group code was proved. In our extension, A is arbitrary and from each wiretap set in A, the wiretapper can obtain some partial information about the message. Under these settings, we define an achievable rate tuple in terms of the message, the key and the wiretapper's equivocation, and prove a tight rate region of the rate tuples. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Cheng, Fan. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 103-108). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Abstract --- p.ii / Acknowledgement --- p.ix / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Network Coding --- p.2 / Chapter 1.2 --- Secure Network Coding --- p.3 / Chapter 1.2.1 --- Perfect Secrecy System --- p.3 / Chapter 1.2.2 --- Imperfect Secrecy System --- p.8 / Chapter 1.3 --- Thesis Organization --- p.10 / Chapter 2 --- Basic Concepts and Tools --- p.13 / Chapter 2.1 --- Basic Concepts in Information Theory --- p.14 / Chapter 2.1.1 --- A Universal Approach for Bounds --- p.17 / Chapter 2.2 --- Information Inequalities for Joint Entropy --- p.18 / Chapter 2.2.1 --- Han's Inequalities --- p.18 / Chapter 2.2.2 --- Madiman-Tetali's Inequalities --- p.19 / Chapter 3 --- Performance Bounds on a Wiretap Network --- p.23 / Chapter 3.1 --- Problem Formulation --- p.24 / Chapter 3.1.1 --- Admissible Code --- p.25 / Chapter 3.1.2 --- Performance Measures of an Admissible Code . --- p.27 / Chapter 3.2 --- Related Works and Our Contribution --- p.27 / Chapter 3.3 --- Blocking Sets and Wiretap Sets --- p.29 / Chapter 3.4 --- An Upper Bound on the Message Size --- p.32 / Chapter 3.5 --- The Fractional Packing Bound --- p.34 / Chapter 3.6 --- An Alternative Bound --- p.37 / Chapter 3.7 --- A Duality Result --- p.38 / Chapter 3.8 --- Some Properties about the Lower Bound --- p.42 / Chapter 3.9 --- Algorithms for Computing the Lower Bound --- p.44 / Chapter 3.9.1 --- A Brute Force Algorithm --- p.44 / Chapter 3.9.2 --- A Polynomial Algorithm --- p.45 / Chapter 3.10 --- Tightness of the Lower Bound --- p.50 / Chapter 3.10.1 --- When the Best Lower bound is Zero --- p.52 / Chapter 3.10.2 --- Point-to-Point Communication System --- p.52 / Chapter 4 --- Imperfect Secrecy in Wire-tap Channel II --- p.63 / Chapter 4.1 --- Problem Formulation and Related Result --- p.64 / Chapter 4.1.1 --- Problem Formulation --- p.64 / Chapter 4.1.2 --- Related Result --- p.67 / Chapter 4.2 --- Rate Region of the Rate Tuple --- p.70 / Chapter 4.3 --- A Subregion of the Rate Region --- p.71 / Chapter 4.3.1 --- Converse --- p.72 / Chapter 4.3.2 --- Achievability --- p.76 / Chapter 4.4 --- General Rate Region --- p.85 / Chapter 4.4.1 --- Converse --- p.86 / Chapter 4.4.2 --- Achievability --- p.88 / Chapter 5 --- Conclusion --- p.91 / Chapter A --- Some Related Results --- p.97 / Chapter A.1 --- Definitions and Theorems in Linear Programming --- p.98 / Chapter A.2 --- An Equivalent Lower Bound --- p.101 / Bibliography --- p.103

本論文研究非同步物理層網絡編碼(PNC) 系統。本文由兩部分構成。在第一部分中，我們提出了一個物理層網絡編碼整體框架，來處理碼元和載波相位異步問題。基於上述框架，本文證明了非同步的物理層網絡編碼可以提高系統性能。本文的第一個重要貢獻在於，不同於以往的主要理解，我們發現在採取適當的解碼方案後，非同步問題並不會降低系統性能。在第二部分中，我們通過理論和實際系統展示了物理層網絡編碼的原型機。特別是，我們採用正交頻分複用(OFDM) 系統，來解決時域的碼元非同步問題。本文的第二個重要貢獻在於，該工作是自五年前物理層網絡編碼理論提出之後，第一個真正的應用系統。 / 第一部分:在本文的第一部分里， 我們研究物理層網絡編碼系統中存在的碼元和載波相位異步問題。在物理層網絡編碼系統中，一個關鍵的問題是，接收機如何處理不同發射機發送的信號之間存在的不同步問題。也就是說，不同的發射機發送的信號達到接收機的時候，存在碼元移位的相位相對偏差。另一個關鍵的問題是，如何將信道編碼投衛和物理層網絡編碼相結合，來實現可靠的信息傳輸。本文研究上迷兩個重要問題，並且有如下四個主要貢獻1)我們提出並且分析了一個基於置信度傳遞(BP) 的物理層網絡編碼整體框架。該框架可以高效地解決碼元和相位異步問題，並且適用於有信道編碼的系統。2) 對於未經信道編碼的物理層網絡編碼系統， 在BPSK 和QPSK 調製下，我們的BP 算法可以顯著地降低非同步帶來的系統性能損失。3) 對於未經信道編碼的物理層網絡編碼系統，在相對碼元偏移為半碼元長度時，我們的BP 算法可以有效地將相位異步帶來的系統性能損失從6dB 降低到不足1dB。4) 對於經過信道編碼的物理層網絡編碼系統，在應用BP 算法後，異步系統性能優於同步系統。最後，在經過信道編碼的物理層網絡編碼系統中， 我們發現由各種碼元和相位異步組合產生的性能損失不超過ldB。上述貢獻3) 說明，如果我們可以精確地控制信號接收時間，那麼人為產生半個碼元偏移會給未經信道編碼的物理層網絡編碼系統帶來好處。上述貢獻4）說明，在採用了信道編碼後，碼元和相位非同步， 將不再是物理層網絡編碼一個主要擔憂的問題。 / 第二部分:在本文的第二部分里，我們展示了第一個物理層網絡編碼原型機的實現過程，這個原型機可以應用於雙向中繼網絡(TWRC) 。截至目前，僅有簡化的物理層網絡編碼系統，稱作模擬網絡編碼(ANC) 投街，被成功實現。模擬網絡編碼的好處在於它的簡單和容易實現;而它的缺點則是，中繼節點在放大信號的同時也放大了噪聲，因而帶來系統性能損失。在物理層網絡編碼系統中，中繼節點只有實現異或(XOR) 運算或者是去噪聲(denoising) PNC 映射，才能能顯著地提高系統性能。但是，要實現上途的XOR PNC 系統我們需要面對很多挑戰。比如， 中繼節點必須能夠處理接收信號的碼元和相位的異步問題，並且可以在解碼前實現信道估計。本文研究頻域物理曾網絡編碼實現，命名為FPNC，來解決上述問題。FPNC 基於OFDM 調製方式實現。在FPNC 系統中， XOR 映射發生在每一個OFDM 碼元的各個子載波上，而不是在時域的採樣點上。我們在通用軟件無線電設備(USRP) 平臺上實現了上述FPNC 系統。需要強調的是，我們的FPNC 實現僅需稍微修改現有的802. lla/g OFDM系統物理層前導序列。在循環前綴(CP) 的幫助下，碼元異步和多經效應都可以被相應地去除。實驗結果顯示，對於經過信道編碼的和未經信道編碼的FPNC 系統，碼元同步系統和碼元異步系統性能沒有區別。 / This thesis investigates asynchronous physical-layer network coding (PNC) systems. It consists of two parts, each part contains a major contribution within the domain of PNC research. The first part presents a theoretical framework for dealing with phase and symbol asynchronies in PNC. We show how this framework can turn asynchronies to an advantage to boost system performance. The major contribution here is the insight that, contrary to the prior belief, asynchrony is not detrimental to the performance of PNC systems with the right methods to deal with it. The second part reports the first PNC implementation prototype. In particular, we demonstrate both in theory and practice that using OFDM in the PNC system can remove the symbol asynchrony in the time domain. The major contribution here is that this is the first experimental feasibility demonstration of the PNC concept since it was conceived theoretically five years ago. / Part I: In the first part of this thesis, we study the phase and symbol asynchrony problems in PNC. A key issue in physical-layer network coding (PNC) is how to deal with the asynchrony between signals transmitted by multiple transmitters. That is, symbols transmitted by different transmitters could arrive at the receiver with symbol misalignment as well as relative carrier-phase offset. A second important issue is how to integrate channel coding with PNC to achieve reliable communication. This thesis investigates these two issues and makes the following contributions: 1) We propose and investigate a general framework for decoding at the receiver based on belief propagation (BP). The framework can effectively deal with symbol and phase asynchronies while incorporating channel coding at the same time. 2) For non-channelcoded PNC, we show that for BPSK and QPSK modulations, our BP method can significantly reduce the asynchrony penalties compared with prior methods. 3) For non-channel-coded PNC, with half symbol offset between the transmitters, our BP method can drastically reduce the performance penalty due to phase asynchrony, from more than 6 dB to no more than 1 dB. 4) For channel-coded PNC, with our BP method, both symbol and phase asynchronies actually improve the system performance compared with the perfectly synchronous case. Furthermore, the performance spread due to different combinations of symbol and phase offsets between the transmitters in channel-coded PNC is only around 1 dB. The implication of 3) is that if we could control the symbol arrival times at the receiver, it would be advantageous to deliberately introduce a half symbol offset in non-channel-coded PNC. The implication of 4) is that when channel coding is used, symbol and phase asynchronies are not major performance concerns in PNC. / Part II: In the second part of this thesis, we present the first implementaii tion of a two-way relay network based on the principle of physical-layer network coding. To date, only a simplified version of physical-layer network coding (PNC) method, called analog network coding (ANC), has been successfully implemented. The advantage of ANC is that it is simple to implement; the disadvantage, on the other hand, is that the relay amplifies the noise along with the signal before forwarding the signal. PNC systems in which the relay performs XOR or other denoising PNC mappings of the received signal have the potential for significantly better performance. However, the implementation of such PNC systems poses many challenges. For example, the relay must be able to deal with symbol and carrier-phase asynchronies of the simultaneous signals received from the two end nodes, and the relay must perform channel estimation before detecting the signals. We investigate a PNC implementation in the frequency domain, referred to as FPNC, to tackle these challenges. FPNC is based on OFDM. In FPNC, XOR mapping is performed on the OFDM samples in each subcarrier rather than on the samples in the time domain. We implement FPNC on the universal soft radio peripheral (USRP) platform. Our implementation requires only moderate modifications of the packet preamble design of 802.11a/g OFDM PHY. With the help of the cyclic prefix (CP) in OFDM, symbol asynchrony and the multi-path fading effects can be dealt with in a similar fashion. Our experimental results show that symbol-synchronous and symbol-asynchronous FPNC have essentially the same BER performance, for both channel-coded and non-channelcoded FPNC. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Lu, Lu. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 123-128). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.viii / Publications --- p.x / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Asynchrony Problems in Physical-Layer Network Coding --- p.3 / Chapter 1.2 --- Implementation of Physical-Layer Network Coding --- p.4 / Chapter 1.3 --- Outline of the Thesis --- p.5 / Chapter 2 --- Asynchronous PNC --- p.7 / Chapter 2.1 --- Introduction --- p.7 / Chapter 2.2 --- Related Work --- p.10 / Chapter 2.2.1 --- Classification --- p.11 / Chapter 2.2.2 --- Non-channel-coded PNC --- p.11 / Chapter 2.2.3 --- Channel-coded PNC --- p.12 / Chapter 2.3 --- System Model --- p.14 / Chapter 2.4 --- Non-channel-coded PNC --- p.19 / Chapter 2.4.1 --- Synchronous Non-channel-coded PNC --- p.19 / Chapter 2.4.2 --- BP-UPNC: A Belief Propagation based Non-channelcoded PNC Scheme --- p.20 / Chapter 2.4.3 --- Numerical Results --- p.27 / Chapter 2.4.4 --- Diversity and Certainty Propagation --- p.29 / Chapter 2.5 --- Channel-coded PNC --- p.33 / Chapter 2.5.1 --- Channel-decoding and Network-Coding (CNC) Process --- p.34 / Chapter 2.5.2 --- Jt-CNC: A Joint Channel-decoding and Network-Coding Scheme --- p.36 / Chapter 2.5.3 --- XOR-CD: A Disjoint Channel-decoding and Network-Coding Scheme --- p.40 / Chapter 2.5.4 --- Numerical Results --- p.43 / Chapter 2.5.5 --- Shannon Limits for Gaussian Channel --- p.48 / Chapter 2.5.6 --- Diversity and Certainty Propagation in Jt-CNC --- p.50 / Chapter 2.6 --- Conclusions --- p.51 / Chapter 3 --- Implementation of Asynchronous PNC --- p.54 / Chapter 3.1 --- Introduction --- p.54 / Chapter 3.1.1 --- Challenges --- p.56 / Chapter 3.2 --- Effect of Delay Asynchrony in Frequency Domain --- p.60 / Chapter 3.2.1 --- Effective Discrete-time Channel Gains --- p.60 / Chapter 3.2.2 --- Delay-Spread-Within-CP Requirement --- p.63 / Chapter 3.3 --- FPNC Frame Format --- p.66 / Chapter 3.3.1 --- FPNC Short Training Symbol --- p.68 / Chapter 3.3.2 --- FPNC Long Training Symbol --- p.69 / Chapter 3.3.3 --- FPNC Pilot --- p.70 / Chapter 3.4 --- Addressing Key Implementation Challenges in FPNC --- p.71 / Chapter 3.4.1 --- FPNC Carrier Frequency Offset (CFO) Compensation --- p.71 / Chapter 3.4.2 --- FPNC Channel Estimation --- p.75 / Chapter 3.4.3 --- FPNC Mapping --- p.76 / Chapter 3.5 --- Experimental Results --- p.80 / Chapter 3.5.1 --- FPNC Implementation over Software Radio Platform --- p.80 / Chapter 3.5.2 --- Experimental Results --- p.81 / Chapter 3.6 --- Conclusions --- p.88 / Chapter 4 --- Conclusions and Future Work --- p.90 / Chapter 4.1 --- Conclusions --- p.90 / Chapter 4.2 --- Future Work --- p.92 / Chapter 4.2.1 --- Asynchronous PNC --- p.93 / Chapter 4.2.2 --- Implementation of PNC --- p.94 / Chapter A --- Message Update Steps of Jt-CNC --- p.97 / Chapter A.1 --- Step 1. Updates of messages below code nodes X: --- p.98 / Chapter A.2 --- Step 2. Updates of upward messages into check nodes C: --- p.98 / Chapter A.3 --- Step 3. Update of upward messages into the source nodes S: --- p.99 / Chapter A.4 --- Step 4. Update of downward messages into the check nodes C: --- p.100 / Chapter A.5 --- Step 5. Updates of downward messages into code nodes X: --- p.100 / Chapter B --- Channel-coded Collision Resolution --- p.101 / Chapter B.1 --- Introduction --- p.101 / Chapter B.2 --- System Model --- p.103 / Chapter B.3 --- C-CRESM --- p.105 / Chapter B.3.1 --- Review of RA code --- p.106 / Chapter B.3.2 --- Virtual Tanner Graph for RA coded CRESM --- p.107 / Chapter B.3.3 --- Definitions --- p.108 / Chapter B.3.4 --- Message Update Rules --- p.109 / Chapter B.4 --- Comparison of Different Methods --- p.115 / Chapter B.4.1 --- Independent Multiuser Detection and Channel Decoding (Independent MU-CD) --- p.116 / Chapter B.4.2 --- Turbo-SIC --- p.117 / Chapter B.4.3 --- Channel-coded CRESM (C-CRESM) --- p.118 / Chapter B.5 --- Simulation Results --- p.119 / Chapter B.6 --- Conclusion --- p.121 / Bibliography --- p.123

Yim, Ka Yee. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 43). / Abstracts in English and Chinese. / Acknowledgements --- p.vii / TABLE OF CONTENTS --- p.viii / LIST OF TABLES --- p.x / LIST OF FIGURES --- p.xi / Chapter CHAPTER 1 : --- INTRODUCTION --- p.1 / Chapter 1.1. --- Motivation --- p.1 / Chapter 1.2. --- Overview --- p.2 / Chapter 1.3. --- H.264 Overview --- p.2 / Chapter CHAPTER 2 : --- CABAC --- p.7 / Chapter 2.1. --- Introduction --- p.7 / Chapter 2.2. --- CABAC Decoder Implementation Review --- p.7 / Chapter 2.3. --- CABAC Algorithm Review --- p.9 / Chapter 2.4. --- Proposed CABAC Decoder Implementation --- p.13 / Chapter 2.5. --- FSM Method Bin Matching --- p.20 / Chapter 2.6. --- CABAC Experimental Results --- p.22 / Chapter 2.7. --- Summary --- p.26 / Chapter CHAPTER 3 : --- INTEGRATION --- p.27 / Chapter 3.1. --- Introduction --- p.27 / Chapter 3.2. --- Reused Baseline Decoder Review --- p.27 / Chapter 3.3. --- Integration --- p.30 / Chapter 3.4. --- Proposed Solution for Motion Vector Decoding --- p.33 / Chapter 3.5. --- Synthesis Result and Performance Analysis --- p.37 / Chapter CHAPTER 4 : --- CONCLUSION --- p.39 / Chapter 4.1. --- Main Contribution --- p.39 / Chapter 4.2. --- Reflection on the Development --- p.39 / Chapter 4.3. --- Future Work --- p.41 / BIBLIOGRAPHY --- p.43

In the first part, some efficient algorithms are proposed to reduce the complexity of H.264 encoder, which is the latest state-of-the-art video coding standard. Intra and Inter mode decision play a vital role in H.264 encoder and can reduce the spatial and temporal redundancy significantly, but the computational cost is also high. Here, a fast Intra mode decision algorithm and a fast Inter mode decision algorithm are proposed. Experimental results show that the proposed algorithms not only save a lot of computational cost, but also maintain coding performance quite well. Moreover, a real time H.264 baseline codec is implemented on mobile device. Based on our real time H.264 codec, an H.264 based mobile video conferencing system is achieved. / The objective of this thesis is to develop some efficient and perceptual image and video coding techniques. Two parts of the work are investigated in this thesis. / The second part of this thesis investigates two kinds of perceptual picture coding techniques. One is the just noticeable distortion (JND) based picture coding. Firstly, a DCT based spatio-temporal JND model is proposed, which is an efficient model to represent the perceptual redundancies existing in images and is consistent with the human visual system (HVS) characteristic. Secondly, the proposed JND model is incorporated into image and video coding to improve the perceptual quality. Based on the JND model, a transparent image coder and a perceptually optimized H.264 video coder are implemented. Another technique is the image compression scheme based on the recent advances in texture synthesis. In this part, an image compression scheme is proposed with the perceptual visual quality as the performance criterion instead of the pixel-wise fidelity. As demonstrated in extensive experiments, the proposed techniques can improve the perceptual quality of picture coding significantly. / Wei Zhenyu. / Adviser: Ngan Ngi. / Source: Dissertation Abstracts International, Volume: 73-01, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 148-154). / 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, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Du Yinggang. / "September 2004." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (p. 113-119). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web. / Abstracts in English and Chinese.

Bo Yan. / "May 2004." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2004. / Includes bibliographical references (p. 117-131). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web. / Abstracts in English and Chinese.

Besides ABT with higher order transform, a transform based template matching is also investigated. A fast method of template matching, called Fast Walsh Search, is developed. This search method has similar accuracy as exhaustive search but significantly lower computation requirement. / In this thesis, the development of simple but efficient order-16 transforms will be shown. Analysis and comparison with existing order-16 transforms have been carried out. The proposed order-16 transforms were integrated to the existing coding standard reference software individually so as to achieve a new ABT system. In the proposed ABT system, order-4, order-8 and order-16 transforms coexist. The selection of the most appropriate transform is based on the rate-distortion performance of these transforms. A remarkable improvement in coding performance is shown in the experiment results. A significant bit rate reduction can be achieved with our proposed ABT system with both subjective and objective qualities remain unchanged. / Prior knowledge of the coefficient distribution is a key to achieve better coding performance. This is very useful in many areas in coding such as rate control, rate distortion optimization, etc. It is also shown that coefficient distribution of predicted residue is closer to Cauchy distribution rather than traditionally expected Laplace distribution. This can effectively improve the existing processing techniques. / Three kinds of order-l 6 orthogonal DCT-like integer transforms are proposed in this thesis. The first one is the simple integer transform, which is expanded from existing order-8 ICT. The second one is the hybrid integer transform from the Dyadic Weighted Walsh Transform (DWWT). It is shown that it has a better performance than simple integer transform. The last one is a recursive transform. Order-2N transform can be derived from order-N one. It is very close to the DCT. This recursive transform can be implemented in two different ways and they are denoted as LLMICT and CSFICT. They have excellent coding performance. These proposed transforms are investigated and are implemented into the reference software of H.264 and AVS. They are also compared with other order-16 orthogonal integer transform. Experimental results show that the proposed transforms give excellent coding performance and ease to compute. / Transform is a very important coding tool in video coding. It decorrelates the pixel data and removes the redundancy among pixels so as to achieve compression. Traditionally, order-S transform is used in video and image coding. Latest video coding standards, such as H.264/AVC, adopt both order-4 and order-8 transforms. The adaptive use of more than one transforms of different sizes is known as Arbitrary Block-size Transform (ABT). Transforms other than order-4 and order-8 can also be used in ABT. It is expected larger transform size such as order-16 will benefit more in video sequences with higher resolutions such as nap and 1a8ap sequences. As a result, order-16 transform is introduced into ABT system. / Fong, Chi Keung. / Adviser: Wai Kuen Cham. / Source: Dissertation Abstracts International, Volume: 73-04, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references. / 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, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

by Wen Jiang. / c.2 author's name on frame header: Wen, Jiang. / Thesis (Ph.D.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (p. 105-[113]). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web.

Leung, Kai Man. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 63-68). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.5 / Chapter 2.1 --- Graph Connectivity --- p.5 / Chapter 2.1.1 --- Preliminaries --- p.5 / Chapter 2.1.2 --- Edge Connectivity --- p.7 / Chapter 2.1.3 --- Vertex Connectivity --- p.7 / Chapter 2.1.4 --- Algorithms for Graph Connectivities --- p.9 / Chapter 2.1.5 --- All Pairs Edge Connectivities --- p.10 / Chapter 2.1.6 --- Edge Splitting-off --- p.11 / Chapter 2.1.7 --- Graph Separator --- p.13 / Chapter 2.1.8 --- Expander Graphs --- p.15 / Chapter 2.1.9 --- Superconcentrator --- p.17 / Chapter 2.2 --- Network Coding --- p.19 / Chapter 2.2.1 --- Concept --- p.19 / Chapter 2.2.2 --- Linear Network Coding --- p.21 / Chapter 2.2.3 --- Random Linear Network Coding --- p.25 / Chapter 2.3 --- Algebraic Tools --- p.26 / Chapter 2.3.1 --- Linear Algebraic Algorithms --- p.26 / Chapter 2.3.2 --- Nested Dissection --- p.28 / Chapter 3 --- Algorithms for Graph Connectivities --- p.35 / Chapter 3.1 --- Introduction --- p.35 / Chapter 3.1.1 --- Our Results --- p.36 / Chapter 3.1.2 --- Related Work --- p.39 / Chapter 3.1.3 --- Techniques --- p.40 / Chapter 3.1.4 --- Organization --- p.41 / Chapter 3.2 --- New Algebraic Characterization --- p.41 / Chapter 3.3 --- Connectivities in Acyclic Graph --- p.46 / Chapter 3.3.1 --- Faster Encoding Algorithms --- p.47 / Chapter 3.4 --- Directed Planar Graphs --- p.49 / Chapter 3.5 --- All Pairs Edge Connectivities --- p.53 / Chapter 3.5.1 --- Connections with Previous Work --- p.55 / Chapter 3.6 --- Edge Splitting-off --- p.56 / Chapter 3.6.1 --- Edge Splitting-off in Directed Graphs --- p.57 / Chapter 3.6.2 --- Edge Splitting-off in Undirected Graphs --- p.58 / Concluding Remarks --- p.61 / Bibliography --- p.62