Every positive integer has a unique radix 2 representation which uses the digits {0,1}. However, if we allow digits other than 0 and 1, say {0,1,-1}, then a positive integer has many representations. Of these <i>redundant</i> representations, it is possible to choose one that has few nonzero digits. It is well known that using representations of integers with few nonzero digits allows certain algebraic operations to be done more quickly. This thesis is concerned with various representations of integers that are related to efficient implementations of algebraic operations in cryptographic algorithms. The topics covered here include: <ul> <li> <i>The width-w nonadjacent form (w-NAF)</i>. We prove that the <i>w</i>-NAF of an integer has a minimal number of nonzero digits; that is, no other representation of an integer, which uses the <i>w</i>-NAF digits, can have fewer nonzero digits than its <i>w</i>-NAF. </li> <li><i>A left-to-right analogue of the w-NAF</i>. We introduce a new family of radix 2 representations which use the same digits as the <i>w</i>-NAF, but have the property that they can be computed by sliding a window from left to right across the binary representation of an integer. We show these new representations have a minimal number of nonzero digits. </li> <li><i>Joint representations</i>. Solinas introduced a {0,1,-1}-radix 2 representation for pairs of integers called the joint sparse form. We consider generalizations of the joint sparse form which represent <i>r</i>&ge;2 integers and use digits other than {0,1,-1}. We show how to construct a {0,1,2,3}-joint representation that has a minimal number of nonzero columns. </li> <li><i>Nonadjacent digit sets</i>. It is well known that if <i>x</i> equals 3 or -1 then every nonnegative integer has a unique {0,1,<i>x</i>}-nonadjacent form; that is, a {0,1,<i>x</i>}-radix 2 representation with the property that, of any two consecutive digits, at most one is nonzero. We investigate what other values of <i>x</i> have this property. </li> </ul>

Submitted by Cristiane Chim (cristiane.chim@ucpel.edu.br) on 2017-02-13T12:39:14Z No. of bitstreams: 1 RENATO HARTWIG NEUENFELD.pdf: 1118711 bytes, checksum: 8e3e693c9c6a6328935397f57a1da60c (MD5) / Made available in DSpace on 2017-02-13T12:39:14Z (GMT). No. of bitstreams: 1 RENATO HARTWIG NEUENFELD.pdf: 1118711 bytes, checksum: 8e3e693c9c6a6328935397f57a1da60c (MD5) Previous issue date: 2016-12-05 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES# / #2075167498588264571# / #600 / In the FFT computation, the butterflies play a central role, since they allow calculation of complex terms. In this calculation, involving multiplications of input data with appropriate coefficients, the optimization of the butterfly can contribute for the reduction of power consumption of FFT architectures. In this work, different and dedicated structures for the 16 bit-width radix- 2, radix-4 and split-radix DIT butterflies are implemented, where the main goal is to minimize the number of arithmetic operators in order to produce power-efficient structures. Firstly, we improve a radix-2 butterfly previously presented in literature, reducing one adder and one subtractor in the structure. After, part of this optimized radix-2 butterfly is used to reduce the number of real multipliers in both radix-4 and split-radix butterflies. In this work, multi-operands addition schemes were exploited in order to improve the efficiency of the FFT butterflies. Combinations of simultaneous addition of 3, 5 and 7 operands are inserted in the structures of the butterflies in order to produce power-efficient structures. For the multi-operand additions, Carry Save Adder (CSA), and adder compressors are used. The main results show that the use of part of the optimized radix-2 into the radix-4 and split-radix leads to the reduction of power consumption for these structures. Moreover, the use of Carry Save Adder reduces still more the power dissipation of the optimized butterflies structures / No cálculo da Transformada Rápida de Fourier (FFT - Fast Fourier Transform), as borboletas desempenham um papel principal, uma vez que elas permitem o cálculo dos termos complexos. Neste cálculo, envolvendo multiplicações de dados de entrada com coeficientes apropriados, a otimização da borboleta pode contribuir para a redução da dissipação de potência em arquiteturas FFT. Nesse trabalho são implementadas estruturas dedicadas de borboletas radix-2, radix-4 e split-radix com decimação no tempo, para dados de 16 bits de largura, onde o objetivo principal é reduzir o número de operadores aritméticos, a fim de produzir estruturas mais eficientes em termos de dissipação de potência. Primeiramente foi otimizada a estrutura da borboleta radix-2 apresentada na literatura, reduzindo um circuito somador e um subtrator nessa estrutura. Após, parte desta borboleta radix-2 otimizada foi usada para reduzir o número de multiplicadores reais nas borboletas radix-4 e split-radix. Neste trabalho também foram explorados esquemas de adição simultânea de vários operandos, a fim de melhorar a eficiência dessas borboletas FFT. Combinações de somas simultâneas de 3, 5 e 7 operandos são inseridos nas estruturas das borboletas, a fim de produzir estruturas de baixa dissipação de potência. Para tal, foram utilizadas arquiteturas de somadores do tipo Carry Save Adder (CSA) e somadores compressores. Os principais resultados mostram que o uso de parte da borboleta radix-2 otimizada nas borboletas radix-4 e split-radix, leva à redução da dissipação de potência nessas estruturas. Além disso, a utilização de somadores do tipo Carry Save reduz ainda mais a dissipação de potência nas estruturas das borboletas otimizadas. Palavras-chave: FFT. radix-2. radix-4. split

The main goal of this thesis will be the design and implementation of a 2048-point FFT on an FPGA through the use of VHDL code.The FFT will use a butterfly Radix-2 architecture with focus on the comparison of the parameters between the system with different Worlengths, Coefficient Wordlengths and Symbol Error rates as well as different modulation types, comparing 64QAM and 256QAM for the 5Gsystem.This implementation will replace an FFT function block in a Matlab based open source 5G NR simulator based on the 3GPP 15 standard and simulate spectrum, MSE payload,and SER performance.

Every positive integer has a unique radix 2 representation which uses the digits {0,1}. However, if we allow digits other than 0 and 1, say {0,1,-1}, then a positive integer has many representations. Of these <i>redundant</i> representations, it is possible to choose one that has few nonzero digits. It is well known that using representations of integers with few nonzero digits allows certain algebraic operations to be done more quickly. This thesis is concerned with various representations of integers that are related to efficient implementations of algebraic operations in cryptographic algorithms. The topics covered here include: <ul> <li> <i>The width-w nonadjacent form (w-NAF)</i>. We prove that the <i>w</i>-NAF of an integer has a minimal number of nonzero digits; that is, no other representation of an integer, which uses the <i>w</i>-NAF digits, can have fewer nonzero digits than its <i>w</i>-NAF. </li> <li><i>A left-to-right analogue of the w-NAF</i>. We introduce a new family of radix 2 representations which use the same digits as the <i>w</i>-NAF, but have the property that they can be computed by sliding a window from left to right across the binary representation of an integer. We show these new representations have a minimal number of nonzero digits. </li> <li><i>Joint representations</i>. Solinas introduced a {0,1,-1}-radix 2 representation for pairs of integers called the joint sparse form. We consider generalizations of the joint sparse form which represent <i>r</i>&ge;2 integers and use digits other than {0,1,-1}. We show how to construct a {0,1,2,3}-joint representation that has a minimal number of nonzero columns. </li> <li><i>Nonadjacent digit sets</i>. It is well known that if <i>x</i> equals 3 or -1 then every nonnegative integer has a unique {0,1,<i>x</i>}-nonadjacent form; that is, a {0,1,<i>x</i>}-radix 2 representation with the property that, of any two consecutive digits, at most one is nonzero. We investigate what other values of <i>x</i> have this property. </li> </ul>

Nowadays, Internet plays an indispensable role in human lives. People use Internet to search information, transmit data, download ?le, and so on. The data transformed to the composed digital signal by ¡¦0¡¦ and ¡¦1¡¦ are transmitted on Internet . However, Internet is open and unreliable, data may be stolen from the other people if they are not encrypted. In order to ensure the security and secret of data, the cryptosystem is very important. RSA is a famous public-key cryptosystem, and it has easy concept and high security. It needs a lot of modular exponentiations while encryption or decryption. The key length of RSA is always larger than 1024 bits to ensure the high security. In order to achieve real time transmission, we have to speed up the RSA cryptosystem. Therefore, it must be implemented on hardware. In RSA cryptosystem, modular exponentiation is the only operation. Modular exponentiation is based on modular multiplications. Montgomery¡¦s Algorithm used simple additions and shifts to implement the complex modular multiplication. Because the key length is usually larger than 1024 bits, some signals have a lot of fan-outs in hardware architecture. Therefore, the signals have to connect buffers to achieve enough driving ability. But, it may lead to longer delay time and more power consumption. So, Tenca et al. proposed a Multiple Word Montgomery Algorithm to improve the problem of fan-out. Recently, Huang et al. proposed an algorithm which can reduce data dependency of Tenca¡¦s algorithm. This research is based on the architecture of Huang¡¦s algorithm and detects the redundant operations. Then, we block the unnecessary signals to reduce the switch activities. Besides, we use low power shift register to reduce the power consumption of shift register. Experimental results show that our design is useful on decreasing power consumption.

A crescente utilização de equipamentos móveis que empregam a transformada rápida de Fourier (FFT) nas operações de sinal digital pode ter seu uso restrito devido ao comprometimento da durabilidade da bateria e de suas dimensões. Estas possíveis limitações de uso fazem crescer a necessidade do desenvolvimento de técnicas que visam à otimização nos três requisitos básicos de projeto digital: dissipação de potência, área e atraso. Para tanto, é abordado neste trabalho um método que realiza a implementação de arquiteturas FFT com ênfase na otimização através da decomposição dos coeficientes trigonométricos. No cálculo da FFT, as borboletas desempenham um papel central, uma vez que permitem o cálculo de termos complexos. Neste cálculo, que envolve multiplicações dos dados de entrada com coeficientes trigonométricos apropriados, a otimização das borboletas pode contribuir diretamente para a redução de potência e área. Na técnica proposta são analisados quais são os coeficientes trigonométricos existentes na arquitetura FFT utilizada como base e a escolha para decomposição será o que apresentar o menor custo de implementação em hardware. A decomposição de um coeficiente deve garantir a reconstituição de todos os demais coeficientes necessários para a implementação de toda a arquitetura FFT. Assim, a decomposição diminui o número de coeficientes necessários para reconstruir a FFT original. O conjunto dos novos coeficientes gerados são implementados com apenas somadores\subtratores e deslocamentos através de Multiplicação de Matrizes Constantes (CMM – Constant Matrix Multiplication), associados a um sistema de controle com multiplexadores que controlam o caminho para a correta operação da FFT. As implementações dos circuitos somadores/subtratores são realizadas com métrica no nível de portas lógicas, visando menor atraso e dissipação de potência para topologias com somadores dos tipos CSA (Carry Save Adder) e Ripple carry. Os resultados apresentados pelo método proposto, quando comparados com soluções da literatura, são significativamente satisfatórios, pois minimizaram a dissipação de potência e área em 30% e 24% respectivamente. Os resultados apresentam também a redução de componentes somadores necessários para a implementação de arquiteturas FFTs. / The increasing use of mobile devices using the Fast Fourier Transform (FFT) operations in digital signal may have its use restricted due compromising the durability of the battery and its dimensions. These possible limitations on usage makes grow the need to develop techniques aimed at optimizing the three basic requirements of digital design: power dissipation, area and delay. Therefore, this thesis discusses a method that performs the FFT implementation of architectures with emphasis on optimization through decomposition of twiddle factors (trigonometric coefficients). In the FFT the butterflies play a key role, since it allows the computation of complex terms. In this calculation, which involves multiplications of input data with appropriate twiddle factors, optimization of the butterflies can contribute directly to the reduction in power and area. In the proposed technique are analyzed what are the twiddle factors existing in FFT architecture used as a basis and to choose the decomposition that provide the lowest cost hardware implementation. The decomposition of coefficient to must ensure the rebuilding of all the other twiddle factors necessary for the implementation of the architecture FFT. Thus, the decomposition decreases the number of twiddle factors needed to reconstruct the original FFT. The new sets of coefficients generated are implemented with only adders\subtracters and shifting through of Constants Matrix Multiplication (CMM). A control system of multiplexers makes the way for the correct operation of the FFT. The implementations of the circuits arithmetic adders/subtracters are performed at the gate level, seeking lower delay and power consumption for topologies with adders types of CSA (Carry Save Adder) and Ripple carry. The results presented by the proposed method, compared with literature solutions are significantly satisfactory, since minimized power dissipation and area as well as reduced component adders required for implementation architectures FFTs.

A crescente utilização de equipamentos móveis que empregam a transformada rápida de Fourier (FFT) nas operações de sinal digital pode ter seu uso restrito devido ao comprometimento da durabilidade da bateria e de suas dimensões. Estas possíveis limitações de uso fazem crescer a necessidade do desenvolvimento de técnicas que visam à otimização nos três requisitos básicos de projeto digital: dissipação de potência, área e atraso. Para tanto, é abordado neste trabalho um método que realiza a implementação de arquiteturas FFT com ênfase na otimização através da decomposição dos coeficientes trigonométricos. No cálculo da FFT, as borboletas desempenham um papel central, uma vez que permitem o cálculo de termos complexos. Neste cálculo, que envolve multiplicações dos dados de entrada com coeficientes trigonométricos apropriados, a otimização das borboletas pode contribuir diretamente para a redução de potência e área. Na técnica proposta são analisados quais são os coeficientes trigonométricos existentes na arquitetura FFT utilizada como base e a escolha para decomposição será o que apresentar o menor custo de implementação em hardware. A decomposição de um coeficiente deve garantir a reconstituição de todos os demais coeficientes necessários para a implementação de toda a arquitetura FFT. Assim, a decomposição diminui o número de coeficientes necessários para reconstruir a FFT original. O conjunto dos novos coeficientes gerados são implementados com apenas somadores\subtratores e deslocamentos através de Multiplicação de Matrizes Constantes (CMM – Constant Matrix Multiplication), associados a um sistema de controle com multiplexadores que controlam o caminho para a correta operação da FFT. As implementações dos circuitos somadores/subtratores são realizadas com métrica no nível de portas lógicas, visando menor atraso e dissipação de potência para topologias com somadores dos tipos CSA (Carry Save Adder) e Ripple carry. Os resultados apresentados pelo método proposto, quando comparados com soluções da literatura, são significativamente satisfatórios, pois minimizaram a dissipação de potência e área em 30% e 24% respectivamente. Os resultados apresentam também a redução de componentes somadores necessários para a implementação de arquiteturas FFTs. / The increasing use of mobile devices using the Fast Fourier Transform (FFT) operations in digital signal may have its use restricted due compromising the durability of the battery and its dimensions. These possible limitations on usage makes grow the need to develop techniques aimed at optimizing the three basic requirements of digital design: power dissipation, area and delay. Therefore, this thesis discusses a method that performs the FFT implementation of architectures with emphasis on optimization through decomposition of twiddle factors (trigonometric coefficients). In the FFT the butterflies play a key role, since it allows the computation of complex terms. In this calculation, which involves multiplications of input data with appropriate twiddle factors, optimization of the butterflies can contribute directly to the reduction in power and area. In the proposed technique are analyzed what are the twiddle factors existing in FFT architecture used as a basis and to choose the decomposition that provide the lowest cost hardware implementation. The decomposition of coefficient to must ensure the rebuilding of all the other twiddle factors necessary for the implementation of the architecture FFT. Thus, the decomposition decreases the number of twiddle factors needed to reconstruct the original FFT. The new sets of coefficients generated are implemented with only adders\subtracters and shifting through of Constants Matrix Multiplication (CMM). A control system of multiplexers makes the way for the correct operation of the FFT. The implementations of the circuits arithmetic adders/subtracters are performed at the gate level, seeking lower delay and power consumption for topologies with adders types of CSA (Carry Save Adder) and Ripple carry. The results presented by the proposed method, compared with literature solutions are significantly satisfactory, since minimized power dissipation and area as well as reduced component adders required for implementation architectures FFTs.

A crescente utilização de equipamentos móveis que empregam a transformada rápida de Fourier (FFT) nas operações de sinal digital pode ter seu uso restrito devido ao comprometimento da durabilidade da bateria e de suas dimensões. Estas possíveis limitações de uso fazem crescer a necessidade do desenvolvimento de técnicas que visam à otimização nos três requisitos básicos de projeto digital: dissipação de potência, área e atraso. Para tanto, é abordado neste trabalho um método que realiza a implementação de arquiteturas FFT com ênfase na otimização através da decomposição dos coeficientes trigonométricos. No cálculo da FFT, as borboletas desempenham um papel central, uma vez que permitem o cálculo de termos complexos. Neste cálculo, que envolve multiplicações dos dados de entrada com coeficientes trigonométricos apropriados, a otimização das borboletas pode contribuir diretamente para a redução de potência e área. Na técnica proposta são analisados quais são os coeficientes trigonométricos existentes na arquitetura FFT utilizada como base e a escolha para decomposição será o que apresentar o menor custo de implementação em hardware. A decomposição de um coeficiente deve garantir a reconstituição de todos os demais coeficientes necessários para a implementação de toda a arquitetura FFT. Assim, a decomposição diminui o número de coeficientes necessários para reconstruir a FFT original. O conjunto dos novos coeficientes gerados são implementados com apenas somadores\subtratores e deslocamentos através de Multiplicação de Matrizes Constantes (CMM – Constant Matrix Multiplication), associados a um sistema de controle com multiplexadores que controlam o caminho para a correta operação da FFT. As implementações dos circuitos somadores/subtratores são realizadas com métrica no nível de portas lógicas, visando menor atraso e dissipação de potência para topologias com somadores dos tipos CSA (Carry Save Adder) e Ripple carry. Os resultados apresentados pelo método proposto, quando comparados com soluções da literatura, são significativamente satisfatórios, pois minimizaram a dissipação de potência e área em 30% e 24% respectivamente. Os resultados apresentam também a redução de componentes somadores necessários para a implementação de arquiteturas FFTs. / The increasing use of mobile devices using the Fast Fourier Transform (FFT) operations in digital signal may have its use restricted due compromising the durability of the battery and its dimensions. These possible limitations on usage makes grow the need to develop techniques aimed at optimizing the three basic requirements of digital design: power dissipation, area and delay. Therefore, this thesis discusses a method that performs the FFT implementation of architectures with emphasis on optimization through decomposition of twiddle factors (trigonometric coefficients). In the FFT the butterflies play a key role, since it allows the computation of complex terms. In this calculation, which involves multiplications of input data with appropriate twiddle factors, optimization of the butterflies can contribute directly to the reduction in power and area. In the proposed technique are analyzed what are the twiddle factors existing in FFT architecture used as a basis and to choose the decomposition that provide the lowest cost hardware implementation. The decomposition of coefficient to must ensure the rebuilding of all the other twiddle factors necessary for the implementation of the architecture FFT. Thus, the decomposition decreases the number of twiddle factors needed to reconstruct the original FFT. The new sets of coefficients generated are implemented with only adders\subtracters and shifting through of Constants Matrix Multiplication (CMM). A control system of multiplexers makes the way for the correct operation of the FFT. The implementations of the circuits arithmetic adders/subtracters are performed at the gate level, seeking lower delay and power consumption for topologies with adders types of CSA (Carry Save Adder) and Ripple carry. The results presented by the proposed method, compared with literature solutions are significantly satisfactory, since minimized power dissipation and area as well as reduced component adders required for implementation architectures FFTs.

No description available.

In digital communication systems, satellites give us world wide services. These satellites should effectively use the available bounded frequency spectrum and, therefore, to carry out flexible frequency-band reallocation (FFBR), on-board signal processing implementation on FFBR network is needed. In the future, to design desired dynamic communication systems, very flexible digital signal processing structures will be needed. The hardware, in the system, shall not be changed as simple changes in the software will be made. The purpose of this thesis is to implement an N-channel FFBR network, where N=20. A 20-channel FFBR network consists of different blocks, e.g., DFT, IDFT, complex multipliers, input/output commutators and polyphase components. The whole 20-channel FFBR network will be implemented in VHDL. In a 20-channel FFBR network, it is a 20-point FFT/IFFT required. This 20-point FFT/IFFT is built by a combination of radix-4 and radix-5 butterflies. The Cooley-Tukey FFT algorithm is chosen to build the 20-point FFT/IFFT. The main aim is to build 20-point FFT/IFFT. There are 20 complex multipliers before the IFFT block and 20 complex multipliers after the IFFT block. In the same way, 20 complex multipliers are used before the FFT block and 20 complex multipliers are used after the FFT block. At the input/output to this FFBR network, 20 FIR filters (polyphase components) are used, respectively.