Au cours des 15 dernières années, des progrès spectaculaires dans l'analyse et la conception des codes définis par des graphes bipartites et décodables par des algorithmes itératifs ont permis le développement de systèmes de correction d'erreurs, avec des performances de plus en plus proches la limite théorique de Shannon. Dans ce contexte, un rôle déterminant a été joué par la famille des codes à matrice de parité creuse, appelés codes LDPC (pour " Low-Density Parity-Check ", en anglais), introduit par Gallager au début des années 60 et décrits plus tard en termes de graphes bipartites. Négligés pendant de longues années, ces codes ont été redécouverts à la fin des années 90, après que la puissance du décodage itératif a été mise en évidence grâce à l'invention des Turbo-codes. Ce n'est qu'au début des années 2000 que les techniques nécessaires à l'analyse et l'optimisation des codes LDPC ont été développées, techniques qui ont permis ensuite la construction des codes avec des performances asymptotiques proches de la limite de Shannon. Cette remarquable avancée a motivé l'intérêt croissant de la communauté scientifique et soutenu le transfert rapide de cette technologie vers le secteur industriel. Plus récemment, un intérêt tout particulier a été porté aux codes LDPC définis sur des alphabets non-binaires, grâce notamment à leur meilleure capacité de correction en " longueur finie ". Bien que Gallager ait déjà proposé l'utilisation des alphabets non-binaires, en utilisant l'arithmétique modulaire, les codes LDPC non-binaires définis sur les corps finis n'ont étés étudiés qu'à partir de la fin des années 90. Il a été montré que ces codes offrent de meilleures performances que leurs équivalents binaires lorsque le bloc codé est de longueur faible à modérée, ou lorsque les symboles transmis sur le canal sont eux-mêmes des symboles non- binaires, comme par exemple dans le cas des modulations d'ordre supérieur ou des canaux à antennes multiples. Cependant, ce gain en performance implique un coût non négligeable en termes de complexité de décodage, qui peut entraver l'utilisation des codes LDPC non binaires dans des systèmes réels, surtout lorsque le prix à payer en complexité est plus important que le gain en performance. Cette thèse traite de l'analyse et de la conception des codes LDPC non binaires pour des canaux à évanouissements. L'objectif principal de la thèse est de démontrer que, outre le gain en performance en termes de capacité de correction, l'emploi des codes LDPC non binaires peut apporter des bénéfices supplémentaires, qui peuvent compenser l'augmentation de la complexité du décodeur. La " flexibilité " et la " diversité " représentent les deux bénéfices qui seront démontrées dans cette thèse. La " flexibilité " est la capacité d'un système de codage de pouvoir s'adapter à des débits (rendements) variables tout en utilisant le même encodeur et le même décodeur. La " diversité " se rapporte à sa capacité d'exploiter pleinement l'hétérogénéité du canal de communication. La première contribution de cette thèse consiste à développer une méthode d'approximation de l'évolution de densité des codes LDPC non-binaires, basée sur la simulation Monte-Carlo d'un code " infini ". Nous montrons que la méthode proposée fournit des estimations très fines des performances asymptotiques des codes LDPC non-binaires et rend possible l'optimisation de ces codes pour une large gamme d'applications et de modèles de canaux. La deuxième contribution de la thèse porte sur l'analyse et la conception de système de codage flexible, utilisant des techniques de poinçonnage. Nous montrons que les codes LDPC non binaires sont plus robustes au poinçonnage que les codes binaires, grâce au fait que les symboles non-binaires peuvent être partialement poinçonnés. Pour les codes réguliers, nous montrons que le poinçonnage des codes non-binaires obéit à des règles différentes, selon que l'on poinçonne des symboles de degré 2 ou des symboles de degré plus élevé. Pour les codes irréguliers, nous proposons une procédure d'optimisation de la " distribution de poinçonnage ", qui spécifie la fraction de bits poinçonnés par symbole non-binaire, en fonction du degré du symbole. Nous présentons ensuite des distributions de poinçonnage optimisées pour les codes LDPC non binaires, avec des performances à seulement 0,2 - 0,5 dB de la capacité, pour des rendements poinçonnés variant de 0,5 à 0,9. La troisième contribution de la thèse concerne les codes LDPC non binaires transmis sur un canal de Rayleigh à évanouissements rapides, pour lequel chaque symbole modulé est affecté par un coefficient d'évanouissement différent. Dans le cas d'une correspondance biunivoque entre les symboles codés et les symboles modulés (c.-à-d. lorsque le code est définit sur un corps fini de même cardinalité que la constellation utilisée), certains symboles codés peuvent être complètement noyés dans le bruit, dû aux évanouissements profonds du canal. Afin d'éviter ce phénomène, nous utilisons un module d'entrelacement au niveau bit, placé entre l'encodeur et le modulateur. Au récepteur, le module de désentrelacement apporte de la diversité binaire en entrée du décodeur, en atténuant les effets des différents coefficients de fading. Nous proposons un algorithme d'entrelacement optimisé, inspirée de l'algorithme " Progressive Edge-Growth " (PEG). Ainsi, le graphe bipartite du code est élargi par un nouvel ensemble de nœuds représentant les symboles modulés, et l'algorithme proposé établit des connections entre les nœuds représentant les symboles modulés et ceux représentant les symboles codés, de manière à obtenir un graphe élargi de maille maximale. Nous montrons que l'entrelaceur optimisé permet d'obtenir un gain de performance par rapport à un entrelaceur aléatoire, aussi bien en termes de capacité de correction que de détection d'erreurs. Enfin, la quatrième contribution de la thèse consiste en un schéma de codage flexible, permettant d'atteindre la diversité maximale d'un canal à évanouissements par blocs. La particularité de notre approche est d'utiliser des codes Root-LDPC non binaires couplés avec des codes multiplicatifs non binaires, de manière à ce que le rendement de codage puisse facilement s'adapter au nombre de blocs d'évanouissement. Au niveau du récepteur, une simple technique de combinaison de diversité est utilisée en entrée du décodeur. Comme conséquence, la complexité du décodage reste inchangée quel que soit le nombre de blocs d'évanouissement et le rendement du code utilisé, tandis que la technique proposée apporte un réel bénéfice en termes de capacité de correction.

A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are given the same color. The chromatic number of a graph is the least number of colors needed to color all of its vertices. Graph coloring problems can be applied to many real world applications, such as scheduling and register allocation. Computationally, the decision problem of whether a general graph is m-colorable is NP-complete for m ≥ 3. The graph studied in this thesis is a well-known combinatorial object, the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all k; however, coloring the square of the cube is a much more interesting problem. This is the graph in which the vertices are binary vectors of length k, and two vertices are adjacent if and only if the Hamming distance between the two vectors is at most 2. Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis will begin with an introduction to binary codes and their structure. One of the most fundamental combinatorial problems is finding optimal binary codes, that is, binary codes with the maximum cardinality satisfying a specified length and minimum distance. Many upper and lower bounds have been produced, and we will analyze and apply several of these. This leads to many interesting results about the chromatic number of the square of the cube. The smallest k for which the chromatic number of Q2k is unknown is k = 8; however, it can be determined that this value is either 13 or 14. Computational approaches to determine the chromatic number of Q28 were performed. We were unable to determine whether 13 or 14 is the true value; however, much valuable insight was learned about the structure of this graph and the computational difficulty that lies within. Since a 13-coloring of Q28 must have between 9 and 12 color classes being (8; 20; 3) binary codes, this led to a thorough investigation of the structure of such binary codes.

A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are given the same color. The chromatic number of a graph is the least number of colors needed to color all of its vertices. Graph coloring problems can be applied to many real world applications, such as scheduling and register allocation. Computationally, the decision problem of whether a general graph is m-colorable is NP-complete for m ≥ 3. The graph studied in this thesis is a well-known combinatorial object, the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all k; however, coloring the square of the cube is a much more interesting problem. This is the graph in which the vertices are binary vectors of length k, and two vertices are adjacent if and only if the Hamming distance between the two vectors is at most 2. Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis will begin with an introduction to binary codes and their structure. One of the most fundamental combinatorial problems is finding optimal binary codes, that is, binary codes with the maximum cardinality satisfying a specified length and minimum distance. Many upper and lower bounds have been produced, and we will analyze and apply several of these. This leads to many interesting results about the chromatic number of the square of the cube. The smallest k for which the chromatic number of Q2k is unknown is k = 8; however, it can be determined that this value is either 13 or 14. Computational approaches to determine the chromatic number of Q28 were performed. We were unable to determine whether 13 or 14 is the true value; however, much valuable insight was learned about the structure of this graph and the computational difficulty that lies within. Since a 13-coloring of Q28 must have between 9 and 12 color classes being (8; 20; 3) binary codes, this led to a thorough investigation of the structure of such binary codes.

String-to-String Correction is the process of transforming some mutable string M into an exact copy of some other string (the target string T), using a shortest sequence of well-defined edit operations. The formal STRING-TO-STRING CORRECTION problem asks for the optimal solution using just two operations: symbol deletion, and swap of adjacent symbols. String correction problems using only swaps and deletions are computationally interesting; in his paper On the Complexity of the Extended String-to-String Correction Problem (1975), Robert Wagner proved that the String-to-String Correction problem under swap and deletion operations only is NP-complete for unbounded alphabets. In this thesis, we present the first careful examination of the binary-alphabet case, which we call Binary String-to-String Correction (BSSC). We present several special cases of BSSC for which an optimal solution can be found in polynomial time; in particular, the case where T and M have an equal number of occurrences of a given symbol has a polynomial-time solution. As well, we demonstrate and prove several properties of BSSC, some of which do not necessarily hold in the case of String-to-String Correction. For instance: that the order of operations is irrelevant; that symbols in the mutable string, if swapped, will only ever swap in one direction; that the length of the Longest Common Subsequence (LCS) of the two strings is monotone nondecreasing during the execution of an optimal solution; and that there exists no correlation between the effect of a swap or delete operation on LCS, and the optimality of that operation. About a dozen other results that are applicable to Binary String-to-String Correction will also be presented. / Graduate / 0984 / 0715 / tspreen@gmail.com

Les communications par satellites sont l’aboutissement de recherches menées dans les domaines de télécommunications et des technologies spatiales depuis plus de 50 ans. Les premiers satellites souffraient d’un coût exorbitant pour des performances très limitées. Les avancées technologiques apparues dans ces domaines ont permis de rendre ce rapport satisfaisant et commercialement viable ce qui a permis de multiplier leurs lancements et ainsi de mettre en place de véritables réseaux de satellites. À ce jour, il existe de nombreuses constellations de satellites géostationnaires et d’orbites basses utilisées à des fins civiles ou militaires. De manière générale, le routage au sein de ces constellations s’effectue suivant un pré-calcul des routes existantes qui est alors utilisé sur une période donnée et rafraîchi si besoin. Ce type de routage n’étant optimal que sur des topologies déterministes, nous sommes donc amenés à considérer d’autres solutions si l’on relaxe cette hypothèse. L’objectif de cette thèse est d’explorer les alternatives possibles au routage pré-calculé. En tant que piste potentielle, nous proposons de vérifier l’adéquation des protocoles de routage à réplication issus du monde des réseaux tolérants au délai, DTN, aux constellations de satellites. Afin de nous offrir un cadre d’étude pertinent à la vue de cet objectif, nous nous focalisons sur une constellation particulière à caractère quasi-déterministe n’offrant pas une connectivité directe entre tous les nœuds du système. Dans une deuxième partie nous nous intéressons à la modélisation du protocole de routage Binary Spray and Wait. Nous développons un modèle capable de déterminer théoriquement la distribution du délai d’acheminement pour tout type de réseau, homogène et hétérogène. / Satellite communication is the achievement of more than 50 years of research in the fields of telecommunications and space technologies.First satellites had exorbitant costs for very limited performances. Technological advances occurred in these areas have helped them to become commercially feasible and satisfying. This enable the increase of satellite launches and thus, building complete satellite networks.Today, there are many GEO or LEO satellite constellations used for civilian or military applications. In general, routing in these constellations is done by pre-computing existing routes. These routes are then used for a given period and refreshed if needed. This type of routing is optimal only on deterministic topologies as a consequence we need to consider other solutions if we relax this assumption. The objective of this thesis is to explore alternatives to pre-computed routing. As a potential solution, we propose to assess the suitability of replication based routing protocols issued from the world of delay tolerant networks, DTN. To provide a relevant framework to study this topic, we focus on a particular constellation that present a quasi-deterministic nature and do not provide direct connectivity between all nodes of the system. In a second part, we focus on the modeling of the Binary Spray and Wait, routing protocol. We develop a model that can theoretically determine the distribution of end-to-end delay for any type of network, homogeneous and heterogeneous. Finally, we present a possible use of this model to conduct more in-depth theoretical analysis.

Magister Scientiae - MSc (Computer Science) / A machine translation system that can convert South African Sign Language (SASL) video to audio or text and vice versa would be bene cial to people who use SASL to communicate. Five fundamental parameters are associated with sign language gestures, these are: hand location; hand orientation; hand shape; hand movement and facial expressions. The aim of this research is to recognise facial expressions and to compare both feature descriptors and machine learning techniques. This research used the Design Science Research (DSR) methodology. A DSR artefact was built which consisted of two phases. The rst phase compared local binary patterns (LBP), compound local binary patterns (CLBP) and histogram of oriented gradients (HOG) using support vector machines (SVM). The second phase compared the SVM to arti cial neural networks (ANN) and random forests (RF) using the most promising feature descriptor|HOG|from the rst phase. The performance was evaluated in terms of accuracy, robustness to classes, robustness to subjects and ability to generalise on both the Binghamton University 3D facial expression (BU-3DFE) and Cohn Kanade (CK) datasets. The evaluation rst phase showed HOG to be the best feature descriptor followed by CLBP and LBP. The second showed ANN to be the best choice of machine learning technique closely followed by the SVM and RF.

A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are given the same color. The chromatic number of a graph is the least number of colors needed to color all of its vertices. Graph coloring problems can be applied to many real world applications, such as scheduling and register allocation. Computationally, the decision problem of whether a general graph is m-colorable is NP-complete for m ≥ 3. The graph studied in this thesis is a well-known combinatorial object, the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all k; however, coloring the square of the cube is a much more interesting problem. This is the graph in which the vertices are binary vectors of length k, and two vertices are adjacent if and only if the Hamming distance between the two vectors is at most 2. Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis will begin with an introduction to binary codes and their structure. One of the most fundamental combinatorial problems is finding optimal binary codes, that is, binary codes with the maximum cardinality satisfying a specified length and minimum distance. Many upper and lower bounds have been produced, and we will analyze and apply several of these. This leads to many interesting results about the chromatic number of the square of the cube. The smallest k for which the chromatic number of Q2k is unknown is k = 8; however, it can be determined that this value is either 13 or 14. Computational approaches to determine the chromatic number of Q28 were performed. We were unable to determine whether 13 or 14 is the true value; however, much valuable insight was learned about the structure of this graph and the computational difficulty that lies within. Since a 13-coloring of Q28 must have between 9 and 12 color classes being (8; 20; 3) binary codes, this led to a thorough investigation of the structure of such binary codes. / Graduate Studies, College of (Okanagan) / Graduate

L’introspection de machine virtuelle (VM) consiste à superviser les états et les activités de celles-ci depuis la couche de virtualisation, tirant ainsi avantage de son emplacement qui offre à la fois une bonne visibilité des états et des activités des VMs ainsi qu’une bonne isolation de ces dernières. Cependant, les états et les activités des VMs à superviser sont vus par la couche de virtualisation comme une suite binaire de bits et d’octets en plus des états des ressources virtuelles. L’écart entre la vue brute disponible à la couche de virtualisation et celle nécessaire pour la supervision de sécurité des VMs constitue un challenge pour l’introspection appelé « le fossé sémantique ». Pour obtenir des informations sémantiques sur les états et les activités des VMs à fin de superviser leur sécurité, nous présentons dans cette thèse un ensemble de techniques basé sur l’analyse binaire et la réutilisation du code binaire du noyau d’une VM. Ces techniques permettent d’identifier les adresses et les noms de la plupart des fonctions noyau d’une VM puis de les instrumenter (intercepter, appeler et analyser) pour franchir le fossé sémantique de manière automatique et efficiente même dans les cas des optimisations du compilateur et de la randomisation de l’emplacement du code noyau dans la mémoire de la VM. / Virtual Machine Introspection (VMI) consists inmonitoring VMs security from the hypervisor layer which offers thanks to its location a strong visibility on their activities in addition to a strong isolation from them. However, hypervisor view of VMs is just raw bits and bytes in addition to hardware states. The semantic difference between this raw view and the one needed for VM security monitoring presents a significant challenge for VMI called “the semantic gap”. In order to obtain semantic information about VM states and activities for monitoring their security from the hypervisor layer, we present in this thesis a set of techniques based on analysis and reuse of VM kernel binary code. These techniques enable to identify addresses and names of most VM kernel functions then instrument (call, intercept and analyze) them to automatically bridge the semantic gap regardless of challenges presented by compiler optimizations and kernel base address randomization.

Abstract Local binary patterns (LBP) are among the most popular image description methods and have been successfully applied in a diverse set of computer vision problems, covering texture classification, material categorization, face recognition, and image segmentation, to name only a few. The popularity of the LBP methodology can be verified by inspecting the number of existing studies about its different variations and extensions. The number of those studies is vast. Currently, the methodology has been acknowledged as one of the milestones in face recognition research. The starting point of this research is to gain more understanding of which principles the original LBP descriptor is based on. After gaining some degree of insight, yet another try is made to improve some steps of the LBP pipeline, consisted of image pre-processing, pattern sampling, pattern encoding, binning, and further histogram post-processing. The main contribution of this thesis is a bunch of novel LBP extensions that partly try to unify some of the existing derivatives and extensions. The basis for the design of the new additional LBP methodology is to maximise data-driven premises, at the same time minimizing the need for tuning by hand. Prior to local binary pattern extraction, the thesis presents an image upsampling step dubbed as image pre-interpolation. As a natural consequence of upsampling, a greater number of patterns can be extracted and binned to a histogram improving the representational performance of the final descriptor. To improve the following two steps of the LBP pipeline, namely pattern sampling and encoding, three different learning-based methods are introduced. Finally, a unifying model is presented for the last step of the LBP pipeline, namely for local binary pattern histogram post-processing. As a special case of this, a novel histogram smoothing scheme is proposed, which shares the motivation and the effects with the image pre-interpolation for the most of its part. Deriving descriptors for such face recognition problems as face verification or age estimation has been and continues to be among the most popular domains where LBP has ever been applied. This study is not an exception in that regard as the main investigations and conclusions here are made on the basis of how the proposed LBP variations perform especially in the problems of face recognition. The experimental part of the study demonstrates that the proposed methods, experimentally validated using publicly available texture and face datasets, yield results comparable to the best performing LBP variants found in the literature, reported with the corresponding benchmarks. / Tiivistelmä Paikalliset binäärikuviot kuuluvat suosituimpiin menetelmiin kuville suoritettavassa piirteenirrotuksessa. Menetelmää on sovellettu moniin konenäön ongelmiin, kuten tekstuurien luokittelu, materiaalien luokittelu, kasvojen tunnistus ja kuvien segmentointi. Menetelmän suosiota kuvastaa hyvin siitä kehitettyjen erilaisten johdannaisten suuri lukumäärä ja se, että nykyään kyseinen menetelmien perhe on tunnustettu yhdeksi virstanpylvääksi kasvojentunnistuksen tutkimusalueella. Tämän tutkimuksen lähtökohtana on ymmärtää periaatteita, joihin tehokkaimpien paikallisten binäärikuvioiden suorituskyky perustuu. Tämän jälkeen tavoitteena on kehittää parannuksia menetelmän eri askelille, joita ovat kuvan esikäsittely, binäärikuvioiden näytteistys ja enkoodaus, sekä histogrammin koostaminen ja jälkikäsittely. Esiteltävien uusien menetelmien lähtökohtana on hyödyntää mahdollisimman paljon kohdesovelluksesta saatavaa tietoa automaattisesti. Ensimmäisenä menetelmänä esitellään kuvan ylösnäytteistykseen perustuva paikallisten binäärikuvioiden johdannainen. Ylösnäytteistyksen luonnollisena seurauksena saadaan näytteistettyä enemmän binäärikuvioita, jotka histogrammiin koottuna tekevät piirrevektorista alkuperäistä erottelevamman. Seuraavaksi esitellään kolme oppimiseen perustuvaa menetelmää paikallisten binäärikuvioiden laskemiseksi ja niiden enkoodaukseen. Lopuksi esitellään paikallisten binäärikuvioiden histogrammin jälkikäsittelyn yleistävä malli. Tähän malliin liittyen esitellään histogrammin silottamiseen tarkoitettu operaatio, jonka eräs tärkeimmistä motivaatioista on sama kuin kuvan ylösnäytteistämiseen perustuvalla johdannaisella. Erilaisten piirteenirrotusmenetelmien kehittäminen kasvojentunnistuksen osa-alueille on erittäin suosittu paikallisten binäärikuvioiden sovellusalue. Myös tässä työssä tutkittiin miten kehitetyt johdannaiset suoriutuvat näissä osa-ongelmissa. Tutkimuksen kokeellinen osuus ja siihen liittyvät numeeriset tulokset osoittavat, että esitellyt menetelmät ovat vertailukelpoisia kirjallisuudesta löytyvien parhaimpien paikallisten binäärikuvioiden johdannaisten kanssa.

This dissertation investigates four methods for attacking stream ciphers that are based on nonlinear combining generators: -- Two exhaustive-search correlation attacks, based on the binary derivative and the Lempel-Ziv complexity measure. -- A fast-correlation attack utilizing the Viterbi algorithm -- A decimation attack, that can be combined with any of the above three attacks. These are ciphertext-only attacks that exploit the correlation that occurs between the ciphertext and an internal linear feedback shift-register (LFSR) of a stream cipher. This leads to a so-called divide and conquer attack that is able to reconstruct the secret initial states of all the internal LFSRs within the stream cipher. The binary derivative attack and the Lempel-Ziv attack apply an exhaustive search to find the secret key that is used to initialize the LFSRs. The binary derivative and the Lempel-Ziv complexity measures are used to discriminate between correct and incorrect solutions, in order to identify the secret key. Both attacks are ideal for implementation on parallel processors. Experimental results show that the Lempel-Ziv correlation attack gives successful results for correlation levels of p = 0.482, requiring approximately 62000 ciphertext bits. And the binary derivative attack is successful for correlation levels of p = 0.47, using approximately 24500 ciphertext bits. The fast-correlation attack, utilizing the Viterbi algorithm, applies principles from convolutional coding theory, to identify an embedded low-rate convolutional code in the pn-sequence that is generated by an internal LFSR. The embedded convolutional code can then be decoded with a low complexity Viterbi algorithm. The algorithm operates in two phases: In the first phase a set of suitable parity check equations is found, based on the feedback taps of the LFSR, which has to be done once only once for a targeted system. In the second phase these parity check equations are utilized in a Viterbi decoding algorithm to recover the transmitted pn-sequence, thereby obtaining the secret initial state of the LFSR. Simulation results for a 19-bit LFSR show that this attack can recover the secret key for correlation levels of p = 0.485, requiring an average of only 153,448 ciphertext bits. All three attacks investigated in this dissertation are capable of attacking LFSRs with a length of approximately 40 bits. However, these attacks can be extended to attack much longer LFSRs by making use of a decimation attack. The decimation attack is able to reduce (decimate) the size of a targeted LFSR, and can be combined with any of the three above correlation attacks, to attack LFSRs with a length much longer than 40 bits. / Dissertation (MEng (Electronic Engineering))--University of Pretoria, 2007. / Electrical, Electronic and Computer Engineering / unrestricted