Дисертації з теми "Bit-complexity"

Bit-serial multiplication with a fixed coefficient is commonly used in integrated circuits, such as digital filters and FFTs. These multiplications can be implemented using basic components such as adders, subtractors and D flip-flops. Multiplication with the same coefficient can be implemented in many ways, using different structures. Other studies in this area have focused on how to minimize the number of adders/subtractors, and often assumed that the cost for D flip-flops is neglectable. That simplification has been proved to be far too great, and further not at all necessary. In digital devices low power consumption is always desirable. How to attain this in bit-serial multipliers is a complex problem.

The aim of this thesis was to find a strategy on how to implement bit-serial multipliers with as low cost as possible. An important step was achieved by deriving formulas that can be used to calculate the carry switch probability in the adders/subtractors. It has also been established that it is possible to design a power model that can be applied to all possible structures of bit- serial multipliers.

Reed-Solomon codes (RS codes) are an important method for achieving error-correction in communication and storage systems. However, it has proved difficult to find a soft-decision decoding method which has low complexity. Moreover, in some previous soft-decision decoding approaches, bit-level soft-decision information could not be employed fully. Even though RS codes have powerful error correction capability, this is a critical shortcoming. This thesis presents bit-level soft-decision decoding schemes for RS codes. The aim is to design a low complexity sequential decoding method based on bit-level soft- decision information approaching maximum likelihood performance. Firstly a trellis decoding scheme which gives easy implementation is introduced, since the soft-decision information can be used directly. In order to allow bit-level soft-decision, a binary equivalent code is introduced and Wolf's method is used to construct the binary-trellis from a systematic parity check matrix. Secondly, the Fano sequential decoding method is chosen, which is sub-optimal and adaptable to channel conditions. This method does not need a large amount of storage to perform an efficient trellis search. The Fano algorithm is then modified to improve the error correcting performance. Finally, further methods of complexity reduction are presented without loss of decoding performance, based on reliability-first search decoding using permutation groups for RS codes. Compared with the decoder without permutation, those schemes give a large complexity reduction and performance improvement approaching near maximum likelihood performance. In this thesis, three types of permutation, cyclic, squaring and hybrid permutation, are presented and the decoding methods using them are implemented.

In this thesis, a bit parallel architecture for a parallel finite field multiplier with low complexity in composite fields GF((2n)m) with k = n ·
m (k 32) is investigated. The architecture has lower complexity when the Karatsuba-Ofman algorithm is applied for certain k. Using particular primitive polynomials for composite fields improves the complexities. We demonstrated for the values m = 2, 4, 8 in details. This thesis is based on the paper &ldquo
A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields &rdquo
by Christof Paar. The whole purpose of this thesis is to understand and present a detailed description of the results of the paper of Paar.

This dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ''quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and perform Gaussian operations. These operations are a subset of what is allowed by quantum physics, and plays a central role in quantum optics. Hence, it is an accurate model of communication through optical fibers. We show that unfortunately this restriction does not allow secure bit commitment. The proof of this result is based on the notion of ''intrinsic purification'' that we introduce to circumvent the use of Uhlman's theorem when the quantum states are Gaussian. We then examine a weaker primitive, ''quantum weak coin flipping'', in the standard model of quantum computation. Mochon has showed that there exists such a protocol with arbitrarily small bias. We give a clear and meaningful interpretation of his proof. That allows us to present a drastically shorter and simplified proof.The second part of the dissertation deals with different methods of proving lower bounds on the quantum query complexity. This is a very important model in quantum complexity in which numerous results have been proved. In this model, an algorithm has restricted access to the input: it can only query individual bits. We consider a generalization of the standard model, where an algorithm does not compute a classical function, but generates a quantum state. This generalization allows us to compare the strength of the different methods used to prove lower bounds in this model. We first prove that the ''multiplicative adversary method'' is stronger than the ''additive adversary method''. We then show a reduction from the ''polynomial method'' to the multiplicative adversary method. Hence, we prove that the multiplicative adversary method is the strongest one. Adversary methods are usually difficult to use since they involve the computation of norms of matrices with very large size. We show how studying the symmetries of a problem can largely simplify these computations. Last, using these principles we prove the tight lower bound of the INDEX-ERASURE problem. This a quantum state generation problem that has links with the famous GRAPH-ISOMORPHISM problem.

Nous abordons dans cette thèse le problème du calcul de la topologie de courbes algébriques planes. Nous présentons un algorithme qui, grâce à l’application d’outils algébriques comme les bases de Gröbner et les représentations rationnelles univariées, ne nécessite pas de traitement particulier de cas dégénérés. Nous avons implanté cet algorithme et démontré son efficacité par un ensemble de comparaisons avec les logiciels similaires. Nous présentons également une analyse de complexité sensible a la sortie de cet algorithme. Nous discutons ensuite des outils nécessaires pour l’implantation d’algorithmes de géométrie non-linéaire dans CGAL, la bibliothèque de référence de la communauté de géométrie algorithmique. Nous présentons un noyau univarié pour CGAL, un ensemble de fonctions nécessaires pour le traitement d’objets courbes définis par des polynômes univariés. Nous avons validé notre approche en la comparant avec les implantations similaires
We tackle in this thesis the problem of computing the topology of plane algebraic curves. We present an algorithm that avoids special treatment of degenerate cases, based on algebraic tools such as Gröbner bases and rational univariate representations. We implemented this algorithm and showed its performance by comparing to simi- lar existing programs. We also present an output-sensitive complexity analysis of this algorithm. We then discuss the tools that are necessary for the implementation of non- linear geometric algorithms in CGAL, the reference library in the computational geom- etry community. We present an univariate algebraic kernel for CGAL, a set of functions aimed to handle curved objects defined by univariate polynomials. We validated our approach by comparing it to other similar implementations

Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le ``tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISM
This dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ``quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and perform Gaussian operations. These operations are a subset of what is allowed by quantum physics, and plays a central role in quantum optics. Hence, it is an accurate model of communication through optical fibers. We show that unfortunately this restriction does not allow secure bit commitment. The proof of this result is based on the notion of ``intrinsic purification'' that we introduce to circumvent the use of Uhlman's theorem when the quantum states are Gaussian. We then examine a weaker primitive, ``quantum weak coin flipping'', in the standard model of quantum computation. Mochon has showed that there exists such a protocol with arbitrarily small bias. We give a clear and meaningful interpretation of his proof. That allows us to present a drastically shorter and simplified proof.The second part of the dissertation deals with different methods of proving lower bounds on the quantum query complexity. This is a very important model in quantum complexity in which numerous results have been proved. In this model, an algorithm has restricted access to the input: it can only query individual bits. We consider a generalization of the standard model, where an algorithm does not compute a classical function, but generates a quantum state. This generalization allows us to compare the strength of the different methods used to prove lower bounds in this model. We first prove that the ``multiplicative adversary method'' is stronger than the ``additive adversary method''. We then show a reduction from the ``polynomial method'' to the multiplicative adversary method. Hence, we prove that the multiplicative adversary method is the strongest one. Adversary methods are usually difficult to use since they involve the computation of norms of matrices with very large size. We show how studying the symmetries of a problem can largely simplify these computations. Last, using these principles we prove the tight lower bound of the INDEX-ERASURE problem. This a quantum state generation problem that has links with the famous GRAPH-ISOMORPHISM problem

Роговенко, А. І. Методи та інформаційна технологія прискореного обчислення великих даних для систем розподіленої обробки інформації : дис. ... канд. техн. наук : 05.13.06 / А. І. Роговенко. - Чернігів, 2021. - 178 с.
Дисертація присвячена дослідженню актуальних проблем підвищення ефективності цифрових обчислювальних засобів алгоритмів кодування/декодування завадостійких кодів шляхом зменшення складності реалізації за умови високої швидкості й великого об’єму вхідного потоку даних, із використанням особливостей і властивостей апаратної платформи сучасної мікропроцесорної техніки. У першому розділі дисертаційної роботи проаналізовано сучасний стан і перспективи прискорення обчислень у сучасних системах розподіленої обробки інформації. Особлива потреба в прискорювачах виникає у криптографічних системах та системах завадостійкого кодування, де суттєву частину всіх обчислювальних перетворень над великими даними становлять операції в полях Галуа. Проведений аналіз задачі прискорення обчислень у системах розподіленої обробки інформації виявив необхідність зменшення обчислювальної складності реалізації базових операцій, які використовуються в технологіях вирішення задачі виявлення та виправлення помилок у системах розподіленої обробки інформації, зокрема в сучасних системах радіозв’язку. Проаналізовано коди, що використовуються для коригування помилок у сучасних системах радіозв’язку, та визначені основні напрямки прискорення процесу кодування/декодування при використанні алгебраїчних кодів. На основі аналізу було визначено, що процес кодування/декодування базується на апараті арифметики скінчених полів. Таким чином, спрощення та прискорення виконання операції в полях Галуа має привести до зменшення обчислювальної складності реалізації процедур кодування/декодування завадостійких кодів. Проведений аналіз основних методів обчислень операцій у полях Галуа, виявив, що більш пріоритетною є задача спрощення та прискорення виконання операцій додавання, як складових операцій множення, піднесення до степеня та інших. На основі аналізу існуючих методів обчислень операцій у полях Галуа було зроблено висновок, що сучасні широко представлені реалізації блоків обчислення операцій у скінчених полях мають обмеження та недоліки, які призводять до зменшення використовуваності алгебраїчних кодів у вирішеннях задачі виявлення та виправлення помилок. Отже, необхідно розробити методи підвищення продуктивності спеціалізованих обчислювальних засобів із урахуванням особливостей і властивостей апаратної платформи сучасної мікропроцесорної техніки, складності реалізації та швидкодія яких задовольняла б існуючі вимоги та була прогнозованою залежно від розрядності (розміру) оброблюваних послідовностей. У другому розділі роботи проводиться удосконалення методу прискорення та зменшення апаратних витрат на реалізацію блоків виконання операцій за модулем, розробка структурних рішень та модифікація алгоритмів виконання операцій за модулем. Розроблено та запропоновано метод зменшення апаратних витрат суматора за модулем на основі одновимірного каскаду конструктивних модулів з однорідною структурою. Цей метод базується на введенні у схему ланцюгів наскрізного переносу. Ефект від впровадження цього удосконалення полягає у зменшенні обчислювальної ємнісної складності, що забезпечує зменшення апаратних витрат у середньому на 10 % порівняно з наявним базовим методом. Розроблено та запропоновано удосконалений метод зменшення обчислювальної ємнісної складності реалізації моделі суматора за модулем на основі одновимірного каскаду конструктивних модулів, який, на відміну від раніше запропонованого, використовує конструктивні модулі нерегулярного типу. Встановлено, що модифікацію методу можна застосовувати для зменшення обчислювальної складності в разі некритичності вимог до регулярності структури обчислювача. Використання модифікованого методу дозволяє зменшити обчислювальну ємнісну складність, що забезпечує зменшення апаратних витрат у середньому на 50 % порівняно з наявним базовим методом. Розроблено та запропоновано метод збільшення швидкодії суматора за модулем на основі одновимірного каскаду конструктивних модулів, який, на відміну від відомих, використовує ланцюги групового переносу, що дозволяє підвищити швидкість виконання операцій у 8 разів порівняно з реалізацією базовим методом. Запропоновано модифікацію алгоритму множення та піднесення до степеня за змінним модулем, з урахуванням особливостей застосування моделей суматорів на основі одновимірних каскадів конструктивних модулів, в якому зменшене значення нижньої оцінка часової складності. У третьому розділі запропоновано модель обчислювальних структур завадостійких кодів для виконання операцій за змінним простим модулем над числами великої розрядності, виконано її реалізацію та дослідження. Модель була створена з орієнтацією на адаптацію до елементів операційного обчислювального середовища для забезпечення можливості конструювання необхідних комбінацій виконавчих пристроїв для виконання однотипних арифметичних інструкцій за модулем над числами великої розрядності. Також у цьому розділі виконана адаптація алгоритму обчислення операції множення та піднесення до степеня за модулем з урахуванням особливостей її побудови раніше запропонованим методом одновимірного каскаду. Запропонована структура моделі та алгоритм роботи спрощеного завантаження багаторозрядних операндів до блоків виконання операції за модулем. При реалізації моделі використовувався структурний опис з використанням бібліотеки стандартних ресурсів Xilinx мовою опису апаратури VHDL. Запропонований алгоритм роботи блоку спрощеного завантаження операндів. Цей блок являє собою блок керування без логіки вибору операції, оскільки для дослідження одного конкретного обчислювача вона не потрібна, але може справляти додатковий вплив на характеристики. Розроблена модель обчислювальних структур завадостійких кодів для виконання операцій за змінним простим модулем, як і більшість подібних до неї, рідко використовуються як окрема одиниця та зазвичай являють собою частину складнішої синхронної системи. Таким чином, проведені експерименти вирішили задачу визначення максимальної тактової частоти, на якій може працювати розроблена модель без помилок у обчисленнях вихідної функції. Четвертий розділ присвячений розробці інформаційної технології прискореного обчислення великих даних для систем розподіленої обробки інформації. Інформаційна технологія базується на розроблених раніше удосконалених методах зменшення апаратних витрат та прискорення обчислення великих даних. Інформаційна технологія ґрунтується на розроблених раніше, удосконалених методах зменшення апаратних витрат та прискорення обчислення великих даних. Додатково, для доповнення технології було розроблено: проєкт обчислювальної системи на основі софтпроцесора, проєкт співпроцесора з драйверами до обчислювальної системи, набір програмних функцій мовою С, які реалізують програмне виконання базових операцій, та засоби тестування для моделі обчислювальних структур. Для автоматизації процесу створення та тестування моделей був реалізований набір скриптів та бібліотека моделей мовою VHDL, яка містить моделі обчислювальних структур. Також було розроблено архітектуру та систему команд функціональної моделі співпроцесора, орієнтованого на виконання операцій у скінченних полях.
The dissertation is devoted to research of actual problems of increase of efficiency of digital computing means of algorithms of coding / decoding of noise - tolerant codes by reduction of complexity of realization at the condition of high speed and big volume of an input data stream, using features and properties of a hardware platform of modern microprocessor technics. In the first section of the dissertation the current state and prospects of acceleration of calculations in modern systems of distributed information processing are analyzed. A special need for accelerators arises in cryptographic systems and noise-tolerant coding systems, where a significant part of all computational transformations over big data are operations in Galois fields. The analysis of the problem of computing acceleration in distributed information processing systems revealed the need to reduce the computational complexity of the basic operations used in technologies to solve the problem of detecting and correcting errors in distributed information processing systems, in particular in modern radio systems. The codes used to correct errors in modern radio communication systems are analyzed, and the main directions of accelerating the encoding / decoding process when using algebraic codes are identified. Based on the analysis, it was determined that the encoding / decoding process is based on the finite field arithmetic apparatus. Thus, simplifying and speeding up the operation in Galois fields should reduce the computational complexity of implementing encoding / decoding procedures for noise-tolerant codes. An analysis of the main methods of calculating operations in Galois fields, found that the priority is to simplify and accelerate the execution of addition operations, as components of multiplication, multiplication and others. Based on the analysis of existing methods of computing operations in Galois fields, it was concluded that modern widely implemented implementations of computing units in finite fields have limitations and shortcomings that lead to reduced use of algebraic codes in solving problems of error detection and correction. performance of specialized computing facilities, taking into account the features and properties of the hardware platform of modern microprocessor technology, the complexity of implementation and speed of which would meet existing requirements and be predicted depending on the bit size of the processed sequences. In the second section of the work is the development of improving the method of acceleration and reduction of hardware costs for the implementation of units of operations on the module, development of structural solutions and modification of algorithms for operations on the module. A method for reducing the hardware costs of the adder per module based on a one-dimensional cascade of structural modules with a homogeneous structure is developed and proposed. This method is based on the introduction into the circuit of through transmission circuits. The effect of implementing this improvement is to reduce the computational complexity, which reduces hardware costs by an average of 10% compared to the existing basic method. An improved method for reducing the computational capacity of the modulator adder model implementation based on a one-dimensional cascade of structural modules is developed and proposed, which, in contrast to the previously proposed, uses structural modules of irregular type. It is established that the modification of the method can be used to reduce the computational complexity in the case of non-critical requirements for the regularity of the computer structure. The use of a modified method reduces the computational complexity, which reduces hardware costs by an average of 50% compared to the existing basic method. A method of increasing the speed of the adder modulo based on a onedimensional cascade of structural modules is developed and proposed, which, unlike the known ones, uses group transfer chains, which allows to increase the speed of operations 8 times compared to the basic method. A modification of the algorithm of multiplication and exponentiation by a variable module is proposed, taking into account the peculiarities of the application of adder models based on one-dimensional cascades of structural modules, in which the value of the lower estimate of time complexity is reduced. The third section proposes a model of computational structures of noise-tolerant codes for performing operations on a variable simple module over high-digit numbers, its implementation and research. The model was created with a focus on adaptation to the elements of the operational computing environment to provide the ability to design the necessary combinations of actuators to perform the same type of arithmetic instructions modulo over high-digit numbers. Also in the section the adaptation of the algorithm for calculating the operation of multiplication and exponentiation modulo taking into account the peculiarities of its construction by the previously proposed method of one-dimensional cascade. The structure of the model and the algorithm of work of the simplified loading of multi-bit operands to blocks of performance of operation on the module are offered. The model was implemented using a structural description using the Xilinx standard resource library in the VHDL hardware description language. The algorithm of operation of the block of the simplified loading of operands is offered. This unit is a control unit without the logic of the choice of operation, as for the study of one particular computer, it is not required, but can have an additional impact on performance. Keep in mind that the contribution of the FSL interface and the simplified load scheme to the values of resources and delays may not have characteristics with a high coefficient of determination, as their implementation uses a behavioral description. The model of computational structures of noise-tolerant codes for performing operations on a variable simple module, like most similar ones, is rarely used as a separate unit, and is usually part of a more complex synchronous system. Thus, the experiments solved the problem of determining the maximum clock frequency at which the developed model can work without errors in the calculations of the original function. The fourth section is devoted to the development of information technology for accelerated computation of large data for distributed information processing systems. Information technology is based on previously developed advanced methods to reduce hardware costs and speed up the calculation of big data. Information technology is based on previously developed, improved methods to reduce hardware costs and speed up the calculation of big data. In addition, to complement the technology, a computer processor-based computer system project, a coprocessor project with computer system drivers, a set of C-program functions that implement software execution of basic operations, and testing tools for the computer structure model were developed. To automate the process of creating and testing models, a set of scripts and a library of models in VHDL, which contains models of computational structures, was implemented. The architecture and command system of the functional model of the coprocessor, focused on performing operations in finite fields, were also developed.

Nowadays, the digital terrestrial television (DTT) market is characterized by the high capacity needed for high definition TV services. There is a need for an efficient use of the broadcast spectrum, which requires new technologies to guarantee increased capacities. Non-Uniform Constellations (NUC) arise as one of the most innovative techniques to approach those requirements. NUCs reduce the gap between uniform Gray-labelled Quadrature Amplitude Modulation (QAM) constellations and the theoretical unconstrained Shannon limit. With these constellations, symbols are optimized in both in-phase (I) and quadrature (Q) components by means of signal geometrical shaping, considering a certain signal-to-noise ratio (SNR) and channel model. There are two types of NUC, one-dimensional and two-dimensional NUCs (1D-NUC and 2D-NUC, respectively). 1D-NUCs maintain the squared shape from QAM, but relaxing the distribution between constellation symbols in a single component, with non-uniform distance between them. These constellations provide better SNR performance than QAM, without any demapping complexity increase. 2D-NUCs also relax the square shape constraint, allowing to optimize the symbol positions in both dimensions, thus achieving higher capacity gains and lower SNR requirements. However, the use of 2D-NUCs implies a higher demapping complexity, since a 2D-demapper is needed, i.e. I and Q components cannot be separated. In this dissertation, NUCs are analyzed from both transmit and receive point of views, using either single-input single-output (SISO) or multiple-input multiple-output (MIMO) antenna configurations. In SISO transmissions, 1D-NUCs and 2D-NUCs are optimized for a wide range of SNRs and different constellation orders. The optimization of rotated 2D-NUCs is also investigated. Even though the demapping complexity is not increased, the SNR gain of these constellations is not significant. The highest rotation gain is obtained for low-order constellations and high SNRs. However, with multi-RF techniques, the SNR gain is drastically increased, since I and Q components are transmitted in different RF channels. In this thesis, multi-RF gains of NUCs with and without rotation are provided for some representative scenarios. At the receiver, two different implementation bottlenecks are explored. First, the demapping complexity of all considered constellations is analyzed. Afterwards, two complexity reduction algorithms for 2D-NUCs are proposed. Both algorithms drastically reduce the number of distances to compute. Moreover, both are finally combined in a single demapper. Quantization of NUCs is also explored in this dissertation, since LLR values and I/Q components are modified when using these constellations, compared to traditional QAM constellations. A new algorithm that is based on the optimization of the quantizer levels for a particular constellation is proposed. The use of NUCs in multi-antenna communications is also investigated. It includes the optimization in one or two antennas, the use of power imbalance, the cross-polar discrimination (XPD) between receive antennas, or the use of different demappers. Assuming different values for the parameters evaluated, new Multi-Antenna Non-Uniform Constellations (MA-NUC) are obtained by means of a particularized re-optimization process, specific for MIMO. At the receiver, an extended demapping complexity analysis is performed, where it is shown that the use of 2D-NUCs in MIMO extremely increases the demapping complexity. As an alternative, an efficient solution for 2D-NUCs and MIMO systems based on Soft-Fixed Sphere Decoding (SFSD) is proposed. The main drawback is that SFSD demappers do not work with 2D-NUCs, since they perform a Successive Interference Cancellation (SIC) step that needs to be performed in separated I and Q components. The proposed method quantifies the closest symbol using Voronoi regions and allows SFSD demappers to work.
Hoy en día, el mercado de la televisión digital terrestre (TDT) está caracterizado por la alta capacidad requerida para transmitir servicios de televisión de alta definición y el espectro disponible. Es necesario por tanto un uso eficiente del espectro radioeléctrico, el cual requiere nuevas tecnologías para garantizar mayores capacidades. Las constelaciones no-uniformes (NUC) emergen como una de las técnicas más innovadoras para abordar tales requerimientos. Las NUC reducen el espacio existente entre las constelaciones uniformes QAM y el límite teórico de Shannon. Con estas constelaciones, los símbolos se optimizan en ambas componentes fase (I) y cuadratura (Q) mediante técnicas geométricas de modelado de la señal, considerando un nivel señal a ruido (SNR) concreto y un modelo de canal específico. Hay dos tipos de NUC, unidimensionales y bidimensionales (1D-NUC y 2D-NUC, respectivamente). Las 1D-NUC mantienen la forma cuadrada de las QAM, pero permiten cambiar la distribución entre los símbolos en una componente concreta, teniendo una distancia no uniforme entre ellos. Estas constelaciones proporcionan un mejor rendimiento SNR que QAM, sin ningún incremento en la complejidad en el demapper. Las 2D-NUC también permiten cambiar la forma cuadrada de la constelación, permitiendo optimizar los símbolos en ambas dimensiones y por tanto obteniendo mayores ganancias en capacidad y menores requerimientos en SNR. Sin embargo, el uso de 2D-NUCs implica una mayor complejidad en el receptor. En esta tesis se analizan las NUC desde el punto de vista tanto de transmisión como de recepción, utilizando bien configuraciones con una antena (SISO) o con múltiples antenas (MIMO). En transmisiones SISO, se han optimizado 1D-NUCs para un rango amplio de distintas SNR y varios órdenes de constelación. También se ha investigado la optimización de 2D-NUCs rotadas. Aunque la complejidad no aumenta, la ganancia SNR de estas constelaciones no es significativa. La mayor ganancia por rotación se obtiene para bajos órdenes de constelación y altas SNR. Sin embargo, utilizando técnicas multi-RF, la ganancia aumenta drásticamente puesto que las componentes I y Q se transmiten en distintos canales RF. En esta tesis, se han estudiado varias ganancias multi-RF representativas de las NUC, con o sin rotación. En el receptor, se han identificado dos cuellos de botella diferentes en la implementación. Primero, se ha analizado la complejidad en el receptor para todas las constelaciones consideradas y, posteriormente, se proponen dos algoritmos para reducir la complejidad con 2D-NUCs. Además, los dos pueden combinarse en un único demapper. También se ha explorado la cuantización de estas constelaciones, ya que tanto los valores LLR como las componentes I/Q se ven modificados, comparando con constelaciones QAM tradicionales. Además, se ha propuesto un algoritmo que se basa en la optimización para diferentes niveles de cuantización, para una NUC concreta. Igualmente, se ha investigado en detalle el uso de NUCs en MIMO. Se ha incluido la optimización en una sola o en dos antenas, el uso de un desbalance de potencia, factores de discriminación entre antenas receptoras (XPD), o el uso de distintos demappers. Asumiendo distintos valores, se han obtenido nuevas constelaciones multi-antena (MA-NUC) gracias a un nuevo proceso de re-optimización específico para MIMO. En el receptor, se ha extendido el análisis de complejidad en el demapper, la cual se incrementa enormemente con el uso de 2D-NUCs y sistemas MIMO. Como alternativa, se propone una solución basada en el algoritmo Soft-Fixed Sphere Decoding (SFSD). El principal problema es que estos demappers no funcionan con 2D-NUCs, puesto que necesitan de un paso adicional en el que las componentes I y Q necesitan separarse. El método propuesto cuantifica el símbolo más cercano utilizando las regiones de Voronoi, permitiendo el uso de este tipo de receptor.
Actualment, el mercat de la televisió digital terrestre (TDT) està caracteritzat per l'alta capacitat requerida per a transmetre servicis de televisió d'alta definició i l'espectre disponible. És necessari per tant un ús eficient de l'espectre radioelèctric, el qual requereix noves tecnologies per a garantir majors capacitats i millors servicis. Les constel·lacions no-uniformes (NUC) emergeixen com una de les tècniques més innovadores en els sistemes de televisió de següent generació per a abordar tals requeriments. Les NUC redueixen l'espai existent entre les constel·lacions uniformes QAM i el límit teòric de Shannon. Amb estes constel·lacions, els símbols s'optimitzen en ambdós components fase (I) i quadratura (Q) per mitjà de tècniques geomètriques de modelatge del senyal, considerant un nivell senyal a soroll (SNR) concret i un model de canal específic. Hi ha dos tipus de NUC, unidimensionals i bidimensionals (1D-NUC i 2D-NUC, respectivament). 1D-NUCs mantenen la forma quadrada de les QAM, però permet canviar la distribució entre els símbols en una component concreta, tenint una distància no uniforme entre ells. Estes constel·lacions proporcionen un millor rendiment SNR que QAM, sense cap increment en la complexitat al demapper. 2D-NUC també canvien la forma quadrada de la constel·lació, permetent optimitzar els símbols en ambdós dimensions i per tant obtenint majors guanys en capacitat i menors requeriments en SNR. No obstant això, l'ús de 2D-NUCs implica una major complexitat en el receptor, ja que es necessita un demapper 2D, on les components I i Q no poden ser separades. En esta tesi s'analitzen les NUC des del punt de vista tant de transmissió com de recepció, utilitzant bé configuracions amb una antena (SISO) o amb múltiples antenes (MIMO). En transmissions SISO, s'han optimitzat 1D-NUCs, per a un rang ampli de distintes SNR i diferents ordes de constel·lació. També s'ha investigat l'optimització de 2D-NUCs rotades. Encara que la complexitat no augmenta, el guany SNR d'estes constel·lacions no és significativa. El major guany per rotació s'obté per a baixos ordes de constel·lació i altes SNR. No obstant això, utilitzant tècniques multi-RF, el guany augmenta dràsticament ja que les components I i Q es transmeten en distints canals RF. En esta tesi, s'ha estudiat el guany multi-RF de les NUC, amb o sense rotació. En el receptor, s'han identificat dos colls de botella diferents en la implementació. Primer, s'ha analitzat la complexitat en el receptor per a totes les constel·lacions considerades i, posteriorment, es proposen dos algoritmes per a reduir la complexitat amb 2D-NUCs. Ambdós algoritmes redueixen dràsticament el nombre de distàncies. A més, els dos poden combinar-se en un únic demapper. També s'ha explorat la quantització d'estes constel·lacions, ja que tant els valors LLR com les components I/Q es veuen modificats, comparant amb constel·lacions QAM tradicionals. A més, s'ha proposat un algoritme que es basa en l'optimització per a diferents nivells de quantització, per a una NUC concreta. Igualment, s'ha investigat en detall l'ús de NUCs en MIMO. S'ha inclòs l'optimització en una sola o en dos antenes, l'ús d'un desbalanç de potència, factors de discriminació entre antenes receptores (XPD), o l'ús de distints demappers. Assumint distints valors, s'han obtingut noves constel·lacions multi-antena (MA-NUC) gràcies a un nou procés de re-optimització específic per a MIMO. En el receptor, s'ha modificat l'anàlisi de complexitat al demapper, la qual s'incrementa enormement amb l'ús de 2D-NUCs i sistemes MIMO. Com a alternativa, es proposa una solució basada en l'algoritme Soft-Fixed Sphere Decoding (SFSD) . El principal problema és que estos demappers no funcionen amb 2D-NUCs, ja que necessiten d'un pas addicional en què les components I i Q necessiten separar-se. El mètode proposat quantifica el símbol més pròxim utilitzan
Fuentes Muela, M. (2017). Non-Uniform Constellations for Next-Generation Digital Terrestrial Broadcast Systems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/84743
TESIS

We compare LDPC block and LDPC convolutional codes with respect to their decoding performance under low decoding latencies. Protograph based regular LDPC codes are considered with rather small lifting factors. LDPC block and convolutional codes are decoded using belief propagation. For LDPC convolutional codes, a sliding window decoder with different window sizes is applied to continuously decode the input symbols. We show the required Eb/N0 to achieve a bit error rate of 10 -5 for the LDPC block and LDPC convolutional codes for the decoding latency of up to approximately 550 information bits. It has been observed that LDPC convolutional codes perform better than the block codes from which they are derived even at low latency. We demonstrate the trade off between complexity and performance in terms of lifting factor and window size for a fixed value of latency. Furthermore, the two codes are also compared in terms of their complexity as a function of Eb/N0. Convolutional codes with Viterbi decoding are also compared with the two above mentioned codes.

Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.

Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification.

La première primitive est la "mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il est possible d'avoir une sécurité lorsque les deux parties sont soumises à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opérations gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien.

Nous examinons ensuite une primitive cryptographique plus faible, le "tirage faible à pile ou face", dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.

La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement qu'en effectuant des requêtes sur chacune des variables de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique.

Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes.

Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessitent le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs.

Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème Index-Erasure, un problème de génération d'état quantique lié au célèbre problème Isomorphisme-de-Graphes.
Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished

We compare LDPC block and LDPC convolutional codes with respect to their decoding performance under low decoding latencies. Protograph based regular LDPC codes are considered with rather small lifting factors. LDPC block and convolutional codes are decoded using belief propagation. For LDPC convolutional codes, a sliding window decoder with different window sizes is applied to continuously decode the input symbols. We show the required Eb/N0 to achieve a bit error rate of 10 -5 for the LDPC block and LDPC convolutional codes for the decoding latency of up to approximately 550 information bits. It has been observed that LDPC convolutional codes perform better than the block codes from which they are derived even at low latency. We demonstrate the trade off between complexity and performance in terms of lifting factor and window size for a fixed value of latency. Furthermore, the two codes are also compared in terms of their complexity as a function of Eb/N0. Convolutional codes with Viterbi decoding are also compared with the two above mentioned codes.

In this thesis, bandwidth-efficient transmission with bit-interleaved coded modulation (BICM) over fading channels is considered. The main focus of this work is on the design and analysis of iterative decoding schemes employing hard-decision feedback. Although suboptimum by nature, hard-decision feedback allows for low-complexity iterative decoders, which renders this approach advantageous for practical implementations. Two particular 16-ary modulation schemes with their corresponding decoders are considered for bandwidth-efficient transmission. The first scheme is 16-ary quadrature amplitude modulation (16QAM) with coherent iterative decoding (ID), so-called BICM-ID, which relies on (possibly imperfect) channel estimation. We analyze the reliability of the output of the demodulator, which is the inner component decoder in the iterative decoding scheme, and we propose the application of a metric truncation technique to improve the quality of the decision variable and thus the performance of hard-decision feedback iterative decoding. Simulation results for different variants of this metric truncation show notable gains in power efficiency, while decoding complexity is not increased. The second scheme we consider is so-called twisted absolute amplitude and differential phase-shift keying (TADPSK), which allows for iterative decoding without the need for channel estimation. We extend previous work on iterative decision-feedback decoding for TADPSK, so-called iterative decision-feedback differential demodulation (DFDM), and propose a sliding-window DFDM (SWDFDM) module as inner component decoder. Similar to the case of 16QAM, the application of metric truncation yields significant performance improvements also for TADPSK transmission. Finally, we compare 16QAM and TADPSK transmission by means of simulations. Depending on the quality of channel estimation, TADPSK with low-complexity iterative DFDM is shown to outperform 16QAM BICM-ID in some cases.
Applied Science, Faculty of
Electrical and Computer Engineering, Department of
Graduate

碩士
國立交通大學
電子工程系所
97
An automatic algorithm using complexity information for the floating point to fixed point conversion is proposed. The goal of the proposed algorithm is to minimize the hardware complexity and reduce the simulation times. The algorithm considers both the integer bit width and the fraction bit width. For the integer bit width, the algorithm identifies numbers of the integer bit width to prevent the overflow. For the fraction bit width, the algorithm uses the lower bound and the upper bound to find the results. We apply the proposed algorithm to the OFDM system. The results show that the proposed algorithm reduces almost 30% simulation time than complexity-and-distortion measure and sequential search method.

碩士
國立成功大學
電機工程學系碩博士班
97
AAC provides the highest quality and compression rate among all of the audio coding standards. However, AAC encoder’s complexity is higher than any other. Particularly in the bit allocation module. Two level loop’s part needs to do a lot of loops and operation time. In the thesis, we study the famous FAAC encoder’s calculation of distortion and try to predict quantize step size. Proposed a new and simply mathematical bit allocation module without outer iteration loop. Comparing to the original FAAC, our new methods saves 85% encoding time in FixNoise function and 25% in whole encoder, but still maintains the quality. According to removing the loops, the new method dramatically reduce the amount of operations.

碩士
國立虎尾科技大學
電子工程系碩士班
102
This thesis proposes a novel two-bit transform for block motion estimation of video coding. The first two-bit transform technique computes bit transform thresholds for two bit planes by using mean and standard deviation of threshold window. The second two-bit transform technique uses the second order derivative of threshold window and threshold window mean to compute bit transform threshold for two bit planes. However, it is very likely to find a non-best match block for block motion estimation by using threshold window mean to compute bit transform threshold. In addition, the second two-bit transform proposed a weighted NNMP(number of non-matching point) matching criterion to reduce the chance to derive a local minimum NNMP in the first two-bit transform. Hence, the thesis generates the first bit plane by using bit transform threshold computed with Multiband-pass filtered image used in one-bit transform, and adopts weighted NNMP. Experimental results shows the proposed novel two-bit transform technique not only achieves better video quality than the previous two-bit transforms, while also maintains similar computational complexity.

碩士
國立中興大學
電機工程學系
93
Recently, the applications of finite field is widely applied in many areas, such as error correcting codes, cryptography, and computer science. Multiplication has large complexity and enormous time consuming among the basic arithmetic operations in finite field multiplier. Therefore, to choose a finite field multiplier with simple architecture and high efficiency is necessary. The complexity of finite field multiplier is closely related to the choice of a basis in finite field. The selection of finite field bases results in different construction and complexity for the multiplier. We will study the Massey-Omura multiplier over normal bases and propose some variations of it. The finite field multipliers can be roughly classified into two categories: bit series multiplier and bit parallel multiplier. The main difference between bit series and bit parallel multipliers is their area and time complexity. Though the area complexity of bit series multiplier is lower than bit parallel multiplier, the time complexity of bit series multiplier is increased. On the other hand, bit parallel multiplier has higher area complexity with high speed. The redundancy problem and redundancy construction of bit parallel multiplier over normal basis will be addressed in the paper. We will discuss two previous constructions and proposed two new normal basis multipliers. The area complexity of two new bit parallel multipliers can be reduced by the redundancy of key function and we can trade off the area complexity and time complexity.

博士
長庚大學
電機工程研究所
93
The design of an efficient arithmetic circuit over finite field is an extensive research topic in error control coding and cryptography. In 1989, based on the polynomial (standard) basis, Itoh and Tsujii proposed two low-complexity multipliers for a class of finite fields GF(2m) which generated by the irreducible all one polynomial (AOP) and the irreducible equally spaced polynomial (ESP), reducing the system complexity. Since then, many investigators were interested in this topic. This work presents a ringed bit-parallel systolic multiplicative architecture over a class of GF(2m) based on the irreducible AOP or the irreducible ESP. Compared with other relative multipliers, the ringed bit-parallel systolic multiplier over the class of GF(2m) is free of global connections and requires fewer gates and input pins. Moreover, with the advantage of three-dimensional (3-D) routing, the VLSI implementation of this ringed configuration is easy. Chapter 2, we review some important literatures and introduce several bases of finite field. Two ringed bit-parallel systolic multipliers for computing C+AB, AB, C+AB2 or AB2 over a class of finite fields GF(2m) is presented in Ch 3 and Ch 4, respectively, where A, B and C are three elements in GF(2m) and all elements are represented using a root of an AOP or an ESP. Furthermore, we proposed a general rule to plan the multipliers easily. Chapter 5, based on irreducible trinomials, we proposed a new bit-parallel combinational circuit of multiplication over a class of finite fields GF(2m) using weakly dual basis. Accordingly, the presented circuit is regular and suitable for VLSI implementation since all XOR gates of the multiplier is integrated in an XOR section. Moreover, without increasing circuit complexity, the critical delay is shorter than that of other well-known multipliers presented previously. Chapter 6, we presents a new architecture for the bit-parallel multipliers over finite fields GF(2^m) using weakly dual bases (WDB). Based on a new formulation for WDB multiplication, a general architecture for the bit-parallel multiplier was developed. According to this new architecture, all XOR gates of the multiplier are integrated into an XOR section. Therefore, the circuit is more regular and suitable for VLSI implementation. The time and area complexities using an arbitrary generating polynomial are also derived. Notably, the time complexity is analyzed as a function of the reduction matrix R. More specifically, to our knowledge, this is the first time that the time complexity is given in terms of R. An algorithm is also developed to reduce the circuit complexity. Compared with other multipliers, it reveals that the time delay of the proposed multiplier is less than (at least, the same as) that of other multipliers within comparable circuit complexity.

博士
長庚大學
電機工程研究所
89
Finite field arithmetic has been extensively applied in error control coding [7] and cryptography, [8]. Important operations in finite fields are addition, multiplication, exponentiation, division and computing multiplicative inverse. Addition is very simple and can be implemented with an extremely simple circuit if field elements are represented in a polynomial form. The other operations are much more complex. This study focuses on the hardware implementation of fast and low-complexity multipliers over GF(2m) since computing exponentiation, division and computing multiplicative inverse can be performed by computing multiplication iteratively. In 1984, Yeh, Reed and Truong [5] developed a parallel-in parallel-out systolic architecture to perform the operation AB+C in a general field GF(2m). Since then, many bit-parallel systolic multipliers have been proposed (see, for example,[3-5]). However, these multipliers are inefficient for cryptographic applications due to the system’s complexity. In 1989, Itoh and Tsujii [17] designed two low-complexity multipliers for the class of GF(2m), based on the irreducible all one polynomial (AOP) of degree m and the irreducible equally spaced polynomial (ESP) of degree m, to reduce the system’s complexity. Later, Hasan, Wang and Bhargava [21] developed an ESP-based multiplier using small-scale AOP-based multipliers as the processing units. Recently, Koc and Sunar [18] presented low-complexity bit-parallel canonical and normal basis multipliers based on an AOP. Wu et al. [20] also proposed low-complexity bit-parallel multipliers using weakly dual basis. Drolet [22] introduced a representation based on an isomorphism from GF(2m) into the residue polynomial ring modulo xn+1. With this representation, he presented a serial multiplier and claimed that it is comprised of the least number of gates of all serial multipliers. Although the above low-complexity multipliers adequate for secure cryptosystem applications, none of them is designed with a systolic technique. Accordingly, the computation delay for multiplications over GF(2m) is very long if m is large. The bit-parallel systolic architectures for computing multiplication and exponentiation over a class of fields GF(2m) were presented in this thesis. In Chapter 3, two operations, called the cyclic shifting and the inner product, are defined by the properties of irreducible all one polynomials. An effective algorithm is proposed for computing multiplications over a class of fields GF(2m) using the two operations. Then, two low-complexity bit-parallel systolic multipliers are presented based on the algorithm. An algorithm for computing AB2+C over a finite field GF(2m) in Chapter 4 is presented using the properties of the irreducible all one polynomial of degree m. In Chapter 5, it has shown that if, for a certain degree, an irreducible ESP of a large degree can be obtained from a corresponding irreducible AOP of a extremely small degree. A small AOP-based multiplier of small size can also be applied to construct a large ESP-based multiplier, in which the root of an irreducible equally spaced polynomial of degree nr represents the elements. Then regarding complexity, the structure of an ESP-based multiplier can be applied to construct modular architecture. In Chapter 6, the designed multiplication tree, based on the characteristic of a binary tree, uses the ideal bit-parallel systolic multipliers to compute exponentiation in GF(2^m). Finally, Chapter 7 presents a bit-parallel systolic multiplier in the finite field GF(2^m) over the polynomial basis, where irreducible trinomials xm+xn+1 generate the fields GF(2^m). As compared to the conventional systolic multipliers, the proposed multipliers were designed using systolic technology that involves a very low latency and a very high throughput, and significantly reduce the time and space complexity. Moreover, they are well suited for use in VLSI techniques.