Programme de doctorat
Département d’informatique et de génie logiciel
Faculté des sciences et de génie
SOUTENANCE DE THÈSE
de
Ahmad Al-Rababa’a
Le vendredi 18 mars 2016 à 10h30
Local 3370, Pavillon Adrien-Pouliot
Arithmetic Bit Recycling Data Compression
Président
Monsieur Brahim Chaib-draa, Ph.D.
Directeur des programmes gradués
Département d’informatique et de génie logiciel
Université Laval
Examinateurs
Monsieur Danny Dubé, Ph.D. (Directeur de recherche)
Département d’informatique et de génie logiciel
Université Laval
Monsieur Pascal Tesson, Ph.D. (Examinateur)
Département d’informatique et de génie logiciel
Université Laval
Monsieur Paul Fortier, Ph.D. (Examinateur)
Département de génie électrique et de génie informatique
Université Laval
Monsieur Jean-Yves Chouinard, Ph.D. (Examinateur)
Département de génie électrique et de génie informatique
Université Laval
Monsieur Jun Chen, Ph.D. (Examinateur externe)
Department of Electrical and Computer Engineering
McMaster University
Plusieurs techniques de compression de données souffrent d’un problème appelé la multiplicité des encodages (ME), ce qui diminue leurs performances. Le recyclage de bits (BR) a été présenté par Dubé et Beaudoin. Il vise à diminuer la redondance causée par la ME. La technique originale du BR, appelée HuBR, est basée sur les codes de Huffman et, à ce titre, est incapable de manipuler des fractions de bits, ce qui l’empêche d’éliminer complètement la redondance causée par la ME. Les contributions dans cette thèse sont les suivantes. Une variante du BR, appelée ACBR et basée sur le codage arithmétique est proposée. Cette première variante requiert l’emploi de précision arbitraire dans les calculs effectués par le codeur arithmétique. Une variante de ACBR en précision finie est ensuite proposée, ce qui rend ACBR applicable en pratique. Afin de démontrer l’applicabilité étendue du BR, deux techniques de codage ont été avantageusement choisies comme cibles du BR: les codes variables-à-fixes à analyses syntaxiques multiples de Savari et les codes équilibrés de Knuth.
Abstract
Many data compression techniques suffer from a problem called the Multiplicity of Encodings (ME), which decreases the performance of these techniques. The Bit Recycling (BR) has been introduced by Dubé and Beaudoin to reduce the redundancy caused by ME. The original technique of BR, HuBR, is based on Huffman codes, which cannot manipulate fractional bits, hampering the ability of HuBR to fully recover the redundancy caused by ME. The contributions in this thesis are the following. A variant of BR, ACBR, based on Arithmetic Coding is proposed. This initially proposed variant uses arbitrary precision in the computations performed by the arithmetic coder. A finite-precision variant of ACBR is proposed next, which makes ACBR practical. As demonstrations of the wide applicability of BR, two coding techniques are successfully targeted by BR: Savari’s plurally parsable variable-to-fixed codes and Knuth’s balanced codes.
Bienvenue à tous !
