No description available.

No / Finite quantum systems in which the position and momentum take values in the Galois field GF(p), are studied. Ideas from the subject of field extension are transferred in the context of quantum mechanics. The Frobenius automorphisms in Galois fields lead naturally to the "Frobenius formalism" in a quantum context. The Hilbert space splits into "Frobenius subspaces" which are labeled with the irreducible polynomials associated with the yp¿y. The Frobenius maps transform unitarily the states of a Galois quantum system and leave fixed all states in some of its Galois subsystems (where the position and momentum take values in subfields of GF(p)). An analytic representation of these systems in the -sheeted complex plane shows deeper links between Galois theory and Riemann surfaces. ©2006 American Institute of Physics

Elliptic curves are the basis for a relative new class of public-key schemes. It is predicted that elliptic curves will replace many existing schemes in the near future. It is thus of great interest to develop algorithms which allow efficient implementations of elliptic curve crypto systems. This thesis deals with such algorithms. Efficient algorithms for elliptic curves can be classified into low-level algorithms, which deal with arithmetic in the underlying finite field and high-level algorithms, which operate with the group operation. This thesis describes three new algorithms for efficient implementations of elliptic curve cryptosystems. The first algorithm describes the application of the Karatsuba-Ofman Algorithm to multiplication in composite fields GF((2n)m). The second algorithm deals with efficient inversion in composite Galois fields of the form GF((2n)m). The third algorithm is an entirely new approach which accelerates the multiplication of points which is the core operation in elliptic curve public-key systems. The algorithm explores computational advantages by computing repeated point doublings directly through closed formulae rather than from individual point doublings. Finally we apply all three algorithms to an implementation of an elliptic curve system over GF((216)11). We provide ablolute performance measures for the field operations and for an entire point multiplication. We also show the improvements gained by the new point multiplication algorithm in conjunction with the k-ary and improved k-ary methods for exponentiation.

Security issues have started to play an important role in the wireless communication and computer networks due to the migration of commerce practices to the electronic medium. The deployment of security procedures requires the implementation of cryptographic algorithms. Performance has always been one of the most critical issues of a cryptographic function, which determines its effectiveness. Among those cryptographic algorithms are the elliptic curve cryptosystems which use the arithmetic of finite fields. Furthermore, fields of characteristic two are preferred since they provide carry-free arithmetic and at the same time a simple way to represent field elements on current processor architectures. Multiplication is a very crucial operation in finite field computations. In this contribution, we compare most of the multiplier architectures found in the literature to clarify the issue of choosing a suitable architecture for a specific application. The importance of the measuring the energy consumption in addition to the conventional measures for energy-critical applications is also emphasized. A new parallel-in serial-out multiplier based on all-one polynomials (AOP) using the shifted polynomial basis of representation is presented. The proposed multiplier is area efficient for hardware realization. Low hardware complexity is advantageous for implementation in constrained environments such as smart cards. Architecture of an elliptic curve coprocessor has been developed using the proposed multiplier. The instruction set architecture has been also designed. The coprocessor has been simulated using VHDL to very the functionality. The coprocessor is capable of performing the scalar multiplication operation over elliptic curves. Point doubling and addition procedures are hardwired inside the coprocessor to allow for faster operation.

Security issues have started to play an important role in the wireless communication and computer networks due to the migration of commerce practices to the electronic medium. The deployment of security procedures requires the implementation of cryptographic algorithms. Performance has always been one of the most critical issues of a cryptographic function, which determines its effectiveness. Among those cryptographic algorithms are the elliptic curve cryptosystems which use the arithmetic of finite fields. Furthermore, fields of characteristic two are preferred since they provide carry-free arithmetic and at the same time a simple way to represent field elements on current processor architectures. Multiplication is a very crucial operation in finite field computations. In this contribution, we compare most of the multiplier architectures found in the literature to clarify the issue of choosing a suitable architecture for a specific application. The importance of the measuring the energy consumption in addition to the conventional measures for energy-critical applications is also emphasized. A new parallel-in serial-out multiplier based on all-one polynomials (AOP) using the shifted polynomial basis of representation is presented. The proposed multiplier is area efficient for hardware realization. Low hardware complexity is advantageous for implementation in constrained environments such as smart cards. Architecture of an elliptic curve coprocessor has been developed using the proposed multiplier. The instruction set architecture has been also designed. The coprocessor has been simulated using VHDL to very the functionality. The coprocessor is capable of performing the scalar multiplication operation over elliptic curves. Point doubling and addition procedures are hardwired inside the coprocessor to allow for faster operation.

Η εργασία αφορά ένα ειδικό είδος κωδικοποίησης εντοπισμού και διόρθωσης λαθών, την κωδικοποίση Reed-Solomon. Οι κώδικες αυτού του είδους χρησιμοποιούνται σε τηλεπικοινωνιακές εφαρμογές (ενσύρματη τηλεφωνία, ψηφιακή τηλεόραση, ευρυζωνικές ασύρματες επικοινωνίες) και σε συστήματα ψηφιακής αποθήκευσης (οπτικοί, μαγνητικοί δίσκοι). Η κωδικοποίηση Reed-Solomon βασίζεται σε μία ειδική κατηγορία αριθμητικών πεδίων τα πεδία Galois (Galois Field). Στα πλαίσια της εργασίας πραγματοποιήθηκε μελέτη των ιδιοτήτων των πεδίων Galois. και σχεδιάστηκε κωδικοποιητής-αποκωδικοποιητής για κώδικες Reed Solomon. Η σχεδίαση υλοποιήθηκε σε υλικό (hardware) σε γλώσσα Verilog HDL. Η σύνθεση των κυκλωμάτων πραγματοποιήθηκε με τεχνολογία Πεδίων Προγραμματιζόμενων Πινάκων Πυλών (τεχνολογία FPGA) και τεχνολογία Ολοκληρωμένων Κυκλωμάτων Ειδικού Σκοπού (τεχνολογία ASIC). Ακολουθήθηκε η μεθοδολογία σχεδιασμού Μονάδων Διανοητικής Ιδιοκτησίας για ολοκληρωμένα κυκλώματα (IP core), σύμφωνα με την οποία η σχεδίαση είναι ανεξάρτητη της πλατφόμας υλοποίησης και μπορεί να υλοποιηθεί με καθόλου ή ελάχιστες αλλαγές σε διαφορετικές τεχνολογίες. Η έννοια των IP core βρίσκει ιδιαίτερη εφαρμογή σε Συστήματα σε Ολοκληρωμένα Κυκλώματα (System on Chip). / The present work is about a specific group of error detection and correction codes, the Reed-Solomon codes. Such codes are used in telecommunications applications (wire telephony, digital television, broadband wireless communications) and digital storage systems (optical, magnetic disks). The Reed Solomon codes are based on a specific category of numerical fields, called Galois Fields. The Work consists of the study of the properties of Galois fields and of the design of an codec for Reed Solomon codes. The design was implemented in hardware with the use of Verilog HDL language. The synthesis of the circuit targets Field programmable Gate Array (FPGA) and Applications Specific Integrated Circuit (ASIC) technologies. The design methodology for Intellectual Property Units for integrated circuits (IP cores) was used. According to that methodology the design is platform independent and consequently the implementation can be achieved with minimal or no changes in different technologies. The IP cores model is widely applied in Systems on Integrated Circuits (System on Chips).

Les systèmes de téléphonie mobile de 4ème et 5ème générations ont adopté comme techniques de codage de canal les turbocodes, les codes LDPC et les codes polaires binaires. Cependant, ces codes ne permettent pas de répondre aux exigences, en termes d’efficacité spectrale et de fiabilité, pour les réseaux de communications futurs (2030 et au-delà), qui devront supporter de nouvelles applications telles que les communications holographiques, les véhicules autonomes, l’internet tactile … Un premier pas a été fait il y a quelques années vers la définition de codes correcteurs d’erreurs plus puissants avec l’étude de codes LDPC non binaires, qui ont montré une meilleure performance que leurs équivalents binaires pour de petites tailles de code et/ou lorsqu'ils sont utilisés sur des canaux non binaires. En contrepartie, les codes LDPC non binaires présentent une complexité de décodage plus importante que leur équivalent binaire. Des études similaires ont commencé à émerger du côté des turbocodes. Tout comme pour leurs homologues LDPC, les turbocodes non binaires présentent d’excellentes performances pour de petites tailles de blocs. Du point de vue du décodage, les turbocodes non binaires sont confrontés au même problème d’augmentation de la complexité de traitement que les codes LDPC non binaire. Dans cette thèse nous avons proposé une nouvelle structure de turbocodes non binaires en optimisant les différents blocs qui la constituent. Nous avons réduit la complexité de ces codes grâce à la définition d’un algorithme de décodage simplifié. Les codes obtenus ont montré des performances intéressantes en comparaison avec les codes correcteur d’erreur de la littérature. / Nowadays communication standards have adopted different binary forward error correction codes. Turbo codes were adopted for the long term evolution standard, while binary LDPC codes were standardized for the fifth generation of mobile communication (5G) along side with the polar codes. Meanwhile, the focus of the communication community is shifted towards the requirement of beyond 5G standards. Networks for the year 2030 and beyond are expected to support novel forward-looking scenarios, such as holographic communications, autonomous vehicles, massive machine-type communications, tactile Internet… To respond to the expected requirements of new communication systems, non-binary LDPC codes were defined, and they are shown to achieve better error correcting performance than the binary LDPC codes. This performance gain was followed by a high decoding complexity, depending on the field order.Similar studies emerged in the context of turbo codes, where the non-binary turbo codes were defined, and have shown promising error correcting performance, while imposing high complexity. The aim of this thesis is to propose a new low-complex structure of non-binary turbocodes. The constituent blocks of this structure were optimized in this work, and a new low complexity decoding algorithm was proposed targeting a future hardware implementation. The obtained results are promising, where the proposed codes are shown to outperform existing binary and non-binary codes from the literature.

<p>The family of Low Density Parity Check (LDPC) codes is a strong candidate to be used as Forward Error Correction (FEC) in future communication systems due to its strong error correction capability. Most LDPC decoders use the Message Passing algorithm for decoding, which is an iterative algorithm that passes messages between its variable nodes and check nodes. It is not until recently that computation power has become strong enough to make Message Passing on LDPC codes feasible. Although locally simple, the LDPC codes are usually large, which increases the required computation power. Earlier work on LDPC codes has been concentrated on the binary Galois Field, GF(2), but it has been shown that codes from higher order fields have better error correction capability. However, the most efficient LDPC decoder, the Belief Propagation Decoder, has a squared complexity increase when moving to higher order Galois Fields. Transmission over a channel with M-PSK signalling is a common technique to increase spectral efficiency. The information is transmitted as the phase angle of the signal.</p><p>The focus in this Master’s Thesis is on simplifying the Message Passing decoding when having inputs from M-PSK signals transmitted over an AWGN channel. Symbols from higher order Galois Fields were mapped to M-PSK signals, since M-PSK is very bandwidth efficient and the information can be found in the angle of the signal. Several simplifications of the Belief Propagation has been developed and tested. The most promising is the Table Vector Decoder, which is a Message Passing Decoder that uses a table lookup technique for check node operations and vector summation as variable node operations. The table lookup is used to approximate the check node operation in a Belief Propagation decoder. Vector summation is used as an equivalent operation to the variable node operation. Monte Carlo simulations have shown that the Table Vector Decoder can achieve a performance close to the Belief Propagation. The capability of the Table Vector Decoder depends on the number of reconstruction points and the placement of them. The main advantage of the Table Vector Decoder is that its complexity is unaffected by the Galois Field used. Instead, there will be a memory space requirement which depends on the desired number of reconstruction points.</p>

The family of Low Density Parity Check (LDPC) codes is a strong candidate to be used as Forward Error Correction (FEC) in future communication systems due to its strong error correction capability. Most LDPC decoders use the Message Passing algorithm for decoding, which is an iterative algorithm that passes messages between its variable nodes and check nodes. It is not until recently that computation power has become strong enough to make Message Passing on LDPC codes feasible. Although locally simple, the LDPC codes are usually large, which increases the required computation power. Earlier work on LDPC codes has been concentrated on the binary Galois Field, GF(2), but it has been shown that codes from higher order fields have better error correction capability. However, the most efficient LDPC decoder, the Belief Propagation Decoder, has a squared complexity increase when moving to higher order Galois Fields. Transmission over a channel with M-PSK signalling is a common technique to increase spectral efficiency. The information is transmitted as the phase angle of the signal. The focus in this Master’s Thesis is on simplifying the Message Passing decoding when having inputs from M-PSK signals transmitted over an AWGN channel. Symbols from higher order Galois Fields were mapped to M-PSK signals, since M-PSK is very bandwidth efficient and the information can be found in the angle of the signal. Several simplifications of the Belief Propagation has been developed and tested. The most promising is the Table Vector Decoder, which is a Message Passing Decoder that uses a table lookup technique for check node operations and vector summation as variable node operations. The table lookup is used to approximate the check node operation in a Belief Propagation decoder. Vector summation is used as an equivalent operation to the variable node operation. Monte Carlo simulations have shown that the Table Vector Decoder can achieve a performance close to the Belief Propagation. The capability of the Table Vector Decoder depends on the number of reconstruction points and the placement of them. The main advantage of the Table Vector Decoder is that its complexity is unaffected by the Galois Field used. Instead, there will be a memory space requirement which depends on the desired number of reconstruction points.

Cette thèse a pour première vocation d’être un état de l’art sur le calcul quantique, sinon exhaustif, simple d’accès (chapitres 1, 2 et 3). La partie originale de cet essai consiste en deux approches mathématiques du calcul quantique concernant quelques systèmes quantiques : la première est de nature algébrique et fait intervenir des structures particulières : les corps et les anneaux de Galois (chapitre 4), la deuxième fait appel à la géométrie dite projective (chapitre 5). Cette étude a été motivée par le théorème de Kochen et Specker et par les travaux de Peres et Mermin qui en ont découlé / The first vocation of this thesis would be a state of the art on the field of quantum computation, if not exhaustive, simple access (chapters 1, 2 and 3). The original (interesting) part of this treatise consists of two mathematical approaches of quantum computation concerning some quantum systems : the first one is an algebraic nature and utilizes some particular structures : Galois fields and rings (chapter 4), the second one calls to a peculiar geometry, known as projective one (chapter 5). These two approaches were motivated by the theorem of Kochen and Specker and by work of Peres and Mermin which rose from it