Non-binary Distributed Arithmetic Coding by Ziyang Wang Thesis submitted to the Faculty of Graduate and Postdoctoral Studies In partial fulfillment of the requirements For the Masc degree in Electrical and Computer Engineering Department of Electrical and Computer Engineering Faculty of Engineering University of Ottawa (cid:13)c Ziyang Wang, Ottawa, Canada, 2015 Abstract Distributed source coding (DSC) is a fundamental concept in information theory. It refers to distributed compression of correlated but geographically separated sources. With the development of wireless sensor networks, DSC has attracted great research interest in the recent years [26]. Although many channel code based DSC schemes have been developed (e.g., those basedonturbocodes[11]andLDPCcodes[20]), thisthesisfocusesonthearithmeticcoding based approaches, namely, Distributed Arithmetic Coding (DAC) due to its simplicity in encoding [8]. To date, most of the DAC approaches that have been proposed deal with binarysourcesandcannothandlenon-binarycases. Littleresearchhasbeendonetoextend DAC for non-binary sources. This work aims at developing efficient DAC techniques for the compression of non-binary sources. The key idea of DAC is representing the source symbols by overlapping intervals, as opposed to the case of conventional arithmetic coding where the intervals representing the symbols do not overlap. However the design of the overlapping intervals has been com- pletely of heuristic nature to date. As such, the first part of this work is a thorough study of various interval-overlapping rules in binary DAC so as to understand how these rules im- pact the performance of DAC. The insight acquired in this study is used in the second part of this work, where two DAC algorithms are proposed to compress non-binary non-uniform sources. The first algorithm applies a designed overlap structure in DAC process, while the second converts a non-binary sequence into a binary sequence by Huffman Coding and encoding the result in binary DAC. Simulation studies are performed to demonstrate the efficiencies of the two proposed algorithms in a variety of source parameter settings. ii Acknowledgements I would like to thank all the little people who made this possible. My deepest gratitude goes first and foremost to Professor Yongyi Mao, my supervisor, for his constant encouragement and guidance. He has walked me through all the stages of the writing of this thesis. Without him, I am still a student who is content to the knowledge learning in the course and have no opportunity to get access to the beautiful world of mathematics, and this thesis could not have reached its present form without his help. Second, IwouldliketoexpressmygratitudetoProfessorIlujuKringa, mycosupervisor, for his guidance on Database topic. He gives me an opportunity to apply the knowledge I learn into a real-life project, showing me how to combine research with applications, and also give me funding to support my study. Third, I feel grateful to my classmates who often discuss some knowledge with me. In the discussion with them, I can always figure out some concepts that used to be confused to me. Last but not the least, my thanks goes to my family who support me and give their love and considerations to me all these years, and I also want to thank all the people who helped me and gave me warm when I was abroad alone. iii Dedication This is dedicated to the one I love. My parents, who support me and love me all these years. iv Table of Contents List of Tables viii List of Figures ix 1 Introduction 1 2 Entropy Coding 4 2.1 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Source Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.1 Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Arithmetic Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.3 Lempel-Ziv Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3 Distritbuted Source Coding 15 3.1 The Slepian-Wolf Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Distributed Source Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.1 Distributed Source Coding Using Syndromes(DISCUS) . . . . . . . 18 3.2.2 Distributed Source Coding Using Turbo Code . . . . . . . . . . . . 19 3.2.3 Distributed Source Coding Using LDPC Code . . . . . . . . . . . . 19 v 3.3 Distritbuted Arithmetic Coding . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.1 Binary Distributed Arithmetic Coding . . . . . . . . . . . . . . . . 21 3.3.2 Block Distributed Arithmetic Coding . . . . . . . . . . . . . . . . . 29 4 OverlapRuleDesigninNon-uniformBinaryDistributedArithmeticCod- ing 35 4.1 Problem Set-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 Proposed Overlap Rule Design . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2.1 Rule 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.2.2 Rule 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.2.3 Rule 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2.4 Rule 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3.1 PerformanceEvaluationForShortLengthStronglyCorrelatedSource Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.3.2 Performance Evaluation For Short Length Weakly Correlated Source Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3.3 PerformanceEvaluationForLongLengthStronglyCorrelatedSource Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3.4 Performance Evaluation For Long Length Weakly Correlated Source Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.4 Discussion and Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5 Non-binary Distributed Arithmetic Coding 56 5.1 Multi-Interval Distributed Arithmetic Coding (MI-DAC) . . . . . . . . . . 57 vi 5.1.1 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.1.2 Encoding Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.1.3 Decoding Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.2 Huffman Coded Distributed Arithmetic Coding (HC-DAC) . . . . . . . . . 62 5.2.1 Encoding Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2.2 Decoding Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.3.1 4-ary Source Input Simulation . . . . . . . . . . . . . . . . . . . . . 66 5.3.2 Time Complexity In 4-ary Simulation . . . . . . . . . . . . . . . . . 71 5.3.3 8-ary Source Input Simulation . . . . . . . . . . . . . . . . . . . . . 72 5.3.4 Time Complexity In 8-ary Simulation . . . . . . . . . . . . . . . . . 74 5.4 The decoding complexity in HC-DAC . . . . . . . . . . . . . . . . . . . . . 76 5.5 Discussion and Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6 Conclusion 80 References 81 vii List of Tables 2.1 Distribution of source input X . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Codebook in Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Distribution of the input sequence X . . . . . . . . . . . . . . . . . . . . . 13 5.1 Diadic distribution of input X . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.2 Non-diadic distribution of source input X . . . . . . . . . . . . . . . . . . 69 5.3 Operation time of encoding process . . . . . . . . . . . . . . . . . . . . . . 71 5.4 Operation time of decoding process . . . . . . . . . . . . . . . . . . . . . . 71 5.5 Distribution of source input X . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.6 Operation time of encoding process . . . . . . . . . . . . . . . . . . . . . . 74 5.7 Operation time of decoding process . . . . . . . . . . . . . . . . . . . . . . 75 5.8 Distribution of source input X . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.9 Operation time of the decoding process on different selection of M . . . . . 78 viii List of Figures 2.1 Encoding process of Huffman Coding . . . . . . . . . . . . . . . . . . . . . 8 2.2 The model for Arithmetic coding . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Example of Arithmetic coding . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1 Distributed source coding . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Splepian-Wolf Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Design of DISCUS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.4 Factor graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.5 Structure of the partitioning stage and the encoding stage . . . . . . . . . 22 3.6 Structure of overlapped intervals . . . . . . . . . . . . . . . . . . . . . . . . 22 3.7 Error probability for strongly correlated side infor- mation in p = 0.5. (H(X|Y) = 0.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.8 Errorprobabilityforweaklycorrelatedsideinfor-mationinp = 0.5. (H(X|Y) = 0.722) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.9 Simulation result for Block DAC [28] . . . . . . . . . . . . . . . . . . . . . 34 4.1 Encoding process of DAC . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2 Overlap structure in encoding process . . . . . . . . . . . . . . . . . . . . . 36 ix 4.3 Error probability for 200 length sequences with strongly correlated side in- formation in p = 0.6. (H(X|Y) = 0.28) . . . . . . . . . . . . . . . . . . . . 46 4.4 Error probability for 200 length sequences with strongly correlated side in- formation in p = 0.8. (H(X|Y) = 0.28) . . . . . . . . . . . . . . . . . . . . 47 4.5 Error probability for 200 length sequences with strongly correlated side in- formation in p = 0.9. (H(X|Y) = 0.28) . . . . . . . . . . . . . . . . . . . . 47 4.6 Error probability for 200 length sequences with weakly correlated side in- formation in p = 0.6. (H(X|Y) = 0.61) . . . . . . . . . . . . . . . . . . . . 48 4.7 Error probability for 200 length sequences with weakly correlated side in- formation in p = 0.8. (H(X|Y) = 0.61) . . . . . . . . . . . . . . . . . . . . 49 4.8 Error probability for 1000 length sequences with strongly correlated side information in p = 0.6. (H(X|Y) = 0.28) . . . . . . . . . . . . . . . . . . . 50 4.9 Error probability for 1000 length sequences with strongly correlated side information in p = 0.8. (H(X|Y) = 0.28) . . . . . . . . . . . . . . . . . . . 50 4.10 Error probability for 1000 length sequences with strongly correlated side information in p = 0.9. (H(X|Y) = 0.28) . . . . . . . . . . . . . . . . . . . 51 4.11 Error probability for 1000 length sequences with weakly correlated side in- formation in p = 0.6. (H(X|Y) = 0.61) . . . . . . . . . . . . . . . . . . . . 52 4.12 Error probability for 1000 length sequences with weakly correlated side in- formation in p = 0.8. (H(X|Y) = 0.61) . . . . . . . . . . . . . . . . . . . . 52 4.13 Distribution of real number of codewords for equiprobable source sequences 54 4.14 Distribution of real number of codewords for non-equiprobable source se- quences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.1 The structure of Multi-interval DAC encoder . . . . . . . . . . . . . . . . . 57 5.2 Structure of overlap design . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 x