Wyniki wyszukiwania - BazTech

1

High-speed binary-to-residue converter design using 2-bit segmentation of the input word

Smyk Robert, Czyżak Maciej

Scientific Journal of Gdynia Maritime University

|

2022

|

nr 124

42--56

EN

In this paper a new approach to the design of the high-speed binary-to-residue converter is proposed that allows the attaining of high pipelining rates by eliminating memories used in modulo m generators. The converter algorithm uses segmentation of the input binary word into 2-bit segments. The use and effects of the input word segmentation for the synthesis of converters for five-bit moduli are presented. For the number represented by each segment, the modulo m reduction using a segment modulo m generator is performed. The use of 2-bit segments substantially reduces the hardware amount of the layer of input modulo m generators. The generated residues are added using the multi-operand modulo m adder based on the carry-save adder (CSA) tree, reduction of the number represented by the output CSA tree vectors to the 2m range and fast two-operand modulo m additions. Hardware amount and time delay analyses are also included.

2

SIGN detection and signed integer comparison for three-moduli SET {2n ±1, 2n+k}

Torabi Zeinab, Timarchi Somayeh

Computer Science

|

2021

|

T. 22 (3)

387–401

EN

Comparison, division, and sign detection are considered to be complicated op erations in a residue number system (RNS). A straightforward solution is to convert RNS numbers into binary formats and then perform complicated op erations using conventional binary operators. If efficient circuits are provided for comparison, division, and sign detection, the application of RNS can be extended to those cases that include these operations. For RNS comparison in three-moduli set τ = {2 n−1, 2 n+k , 2 n+1},(0 ≤ k ≤ n), we have found only one hardware realization. In this paper, an efficient RNS comparator is proposed for moduli set τ , which employs a sign-detection method and operates more efficiently than its counterparts. The proposed sign detector and comparator utilize dynamic range partitioning (DRP), which has been recently presented for unsigned RNS comparison. The delay and cost of the proposed comparator are lower than the previous works, which makes it appropriate for RNS applications with limited delay and cost.

3

Multifunctional unit for reverse conversion and sign detection based on five-moduli set { 2 2n , 2 n + 1, 2 n − 1, 2 n + 3, 2 n − 3 }

Mojahed Mohsen, Molahosseini Amir Sabbagh, Zarandi Azadeh Alsadat Emrani

Computer Science

|

2021

|

T. 22 (1)

101-121

EN

A high dynamic range moduli set { 2 2n , 2 n + 1, 2 n − 1, 2 n + 3, 2 n − 3} has recently been introduced as an arithmetically balanced five-modull set for the residue number system (RNS). In order to utilize this moduli set in applications handling signed numbers, two important components are needed: a sign detector, and a signed reverse converter. However, having both of these components results in high-hardware requirements, which makes RNS impractical. This paper overcomes this problem by designing a unified unit that can perform both signed reverse conversion as well as sign detection through the reuse of hardware. To the authors’ knowledge, this is the first attempt to design a sign detector for a moduli set that includes a {2 n 3} moduli. In order to achieve a hardwareamenable design, we first improved the performance of the previous unsigned reverse converter for this moduli set. Then, we extracted a sign-detection method from the structure of the reverse converter. Finally, we made an unsigned reverse converter-to-sign converter through the use of the extracted sign signal from the reverse converter. The experimental results show that the proposed reverse convertor and sign detector result in improvements of 31% and 28% in area and delay, respectively, as compared to the previous unsigned reverse convertor with sign output using a comparator.

4

Efficient implementation of Chinese remainder theorem in minimally redundant residue number system

Selianinau Mikhail

Computer Science

|

2020

|

T. 21 (2)

237--252

EN

The Chinese remainder theorem is widely used in many modern computer applications. This paper presents an efficient approach to the calculation of the rank of a number, a principal positional characteristic that is used in the residue number system. The proposed method does not use large modulo addition operations as compared to a straightforward implementation of the Chinese remainder theorem algorithm. The rank of a number is equal to the sum of an inexact rank and a two-valued correction factor that only takes on values of 0 or 1. We propose a minimally redundant residue number system that provides a low computational complexity of the rank calculation. The effectiveness of the novel method is analyzed regarding a conventional non-redundant residue number system. Owing to the extension of the residue code, the complexity of the rank calculation goes down from O(k2) to O(k) by adding the extra residue modulo 2 (where k equals the number of non-redundant residues).

5

Scaled residue reverse converter for signed numbers with low cost moduli base

Czyżak Maciej, Smyk Robert

Poznan University of Technology Academic Journals. Electrical Engineering

|

2019

|

No. 98

101--114

EN

The paper presents a realization of the scaled residue reverse converter for the low cost moduli base {2n -1,2n ,2n+1} . The moduli of this type allow for the memoryless reverse conversion using the Chinese Remainder Theorem because the orthogonal projections can be obtained by shifts and additions. Moreover, the modulo reduction of the sum of projections and sign detection algorithms are shown. Also the converter architecture is presented.

6

High level synthesis in FPGA of TCS/RNS converter

Smyk R., Czyżak M.

Poznan University of Technology Academic Journals. Electrical Engineering

|

2017

|

No. 91

143--154

EN

The work presents the design process of the TCS/RNS (two's complement–to– residue) converter in Xilinx FPGA with the use of HLS approach. This new approach allows for the design of dedicated FPGA circuits using high level languages such as C++ language. Such approach replaces, to some extent, much more tedious design with VHDL or Verilog and facilitates the design process. The algorithm realized by the given hardware circuit is represented as the program in C++. The performed design experiments had to show whether the obtained structures of TCS/RNS converter are acceptable with respect to speed and hardware complexity. The other aim of the work was to examine whether it is enough to write the program in C++ with the use of basic arithmetic operators or bit–level description is necessary. Finally, we present the discussion of results of the TCS/RNS converter design in Xilinx Vivado HLS environment.

7

Parallel generator of q-valued pseudorandom sequences based on arithmetic polynomials

Finko O, Samoylenko D, Dichenko S, Eliseev N

Przegląd Elektrotechniczny

|

2015

|

R. 91, nr 3

24-27

EN

A new method for parallel generation of q-valued pseudorandom sequence based on the presentation of systems generating logical formulae by means of arithmetic polynomials is proposed. Fragment consisting of k-elements of q-valued pseudorandom sequence may be obtained by means of single computing of a single recursion numerical formula. It is mentioned that the method of the “arithmetization” of generation may be used and further developed in order to protect the encryption gears from cryptographic onset, resulting in the initiating of mass hardware failures.

PL

Zaproponowano metodę równoległej generacji q-wartościowych sekwencji pseudolosowych na podstawie przedstawienia generujących układów rekurencyjnych wzorów logicznych za pomocą wielomianów liczbowych. Fragment zawierający k elementów q-wartościowych sekwencji pseudolosowej można uzyskać za pomocą jednokrotnego obliczania jednego ze wzorów numerycznych. Zwrócono uwagę na to, że proponowana metoda “arytmetyzacji” generowania takich sekwencji może w przyszłości być rozpowszechniona na przypadek zabezpieczenia urządzeń kryptograficznych przed kryptoanalitycznymi atakami, polegającymi na wywoływaniu masowych zaburzeń funkcjonowania osprzętu.

8

On configuration of residue scaling process in pipelined radix-4 MQRNS FFT processor

Smyk R., Czyżak M.

Poznan University of Technology Academic Journals. Electrical Engineering

|

2014

|

No. 80

145--150

EN

Residue scaling is needed in pipelined FFT radix-4 processors based on the Modified Quadratic Residue Number System (MQRNS) at the output of each butterfly. Such processor uses serial connection of radix-4 butterflies. Each butterfly comprises n subunits, one for each modulus of the RNS base and generates four complex residue numbers. In order to prevent the arithmetic overflow in the succesive stage, every number has to be scaled, i.e. divided by a certain constant. The dynamic range of the processed signal increases due to the summation within the butterfly and the transformation of coefficients of the FFT algorithm to integers. The direct approach would require eight residue scalers that would be highly ineffective regarding that such a set of scalers had to be placed after each butterfly. We show and analyze a structure which uses parallel-to-serial transformation of groups of numbers so that only two scalers are needed.

9

On simplification of residue scaling process in pipelined Radix-4 MQRNS FFT processor

Smyk R., Czyżak M.

Computer Applications in Electrical Engineering

|

2014

|

Vol. 12

588--596

EN

Residue scaling is needed in pipelined FFT radix-4 processors based on the Modified Quadratic Residue Number System (MQRNS) at the output of each butterfly. Such processor uses serial connection of radix-4 butterflies. Each butterfly comprises n subunits, one for each modulus of the RNS base and generates four complex residue numbers. In order to prevent arithmetic overflow intermediate results after each butterfly have to be scaled, i.e. divided by a certain constant. The number range of the processed signal increases due to transformation of coefficients of the FFT algorithm to integers and summation and multiplication within the butterfly. The direct approach would require eight residue scalers that would be highly ineffective regarding that such a set of scalers had to be placed after each butterfly. We show and analyze a structure which uses parallel-to-serial transformation of groups of numbers so that only two residue scalers are needed.

10

The network coding method in wireless sensor networks based on residue number system

Yatskiv V

Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska

|

2013

|

z. 67

135--144

EN

The paper presents and investigates the method of network encoding in the residue number system for usage in wireless sensor networks. The method of encoding provides increase of total network bandwidth by choosing coprime digit capacity different modules and different routes of transmission residues.

PL

W artykule zaproponowano i zbadano metodę kodowania sieciowego w systemie resztowym do stosowania w bezprzewodowych sieciach sensorowych. Opracowana metoda kodowania zwiększa ogólną przepustowość sieci dzięki wyborowi względnie pierwszych modułów o różnej pozycyjności i przesyłaniu reszt przez różne trasy.

11

Residue number system (RNS)

Sharoun A. O.

Poznan University of Technology Academic Journals. Electrical Engineering

|

2013

|

No. 76

265--270

EN

In the residue number system, a set of moduli which are independent of each other is given. An integer is represented by the residue of each modulus and the arithmetic operations are based on the residues individually. The arithmetic operations based on residue number system can be performed on various moduli independently to avoid the carry in addition, subtraction and multiplication, which is usually time consuming. However, the comparison and division are more complicated and the fraction number computation is immatured. Due to this, a residue number system is not yet popular in general-purpose computers, though it is extremely useful for digital-signal-processing applications. This thesis deals with the design, simulation and microcontroller implementation of some (residue number system based) building blocks for applications in the field of digital signal processing. The building blocks which have been studied are binary to residue converter, residue to binary converter, residue adder and residue multiplier.

12

Pipelined division of signed numbers with the use of residue arithmetic for small number range with the programmable gate array

Smyk R., Ulman Z., Czyżak M.

Poznan University of Technology Academic Journals. Electrical Engineering

|

2013

|

No. 76

117--126

EN

In this work an architecture of the pipelined signed residue divider for the small number range is presented. Its operation is based on reciprocal calculation and multiplication by the dividend. The divisor in the signed binary form is used to compute the approximated reciprocal in the residue form by the table look-up. In order to limit the look-up table address an algoritm based on segmentation of the divisor into two segments is used. The approximate reciprocal transformed to residue representation with the proper sign is stored in look-up tables. During operation it is multiplied by the dividend in the residue form and subsequently scaled. The pipelined realization of the divider in the FPGA environment is also shown.

13

Scaling of signed residue numbers with mixed-radix conversion in FPGA with extended scaling factor selection

Smyk R., Czyżak M., Ulman Z.

Computer Applications in Electrical Engineering

|

2013

|

Vol. 11

465--477

EN

A scaling technique of signed residue numbers in FPGA is proposed. The technique is based on conversion of residue numbers to the Mixed-Radix System (MRS). The scaling factor is assumed to be a moduli product from the Residue Number System (RNS) base. Scaling is performed by scaling of MRS terms, the subsequent generation of residue representations of scaled terms, binary addition of these representations and generation of residues for all moduli. The sign of the residue number is detected by using the most significant digit of the MRS representation. Basic blocks of the scaler are realized in the form of modified two-operand modulo adders with included additional multiply and modulo reduction operations. An exemplary pipelined realization of the scaler in the Xilinx FPGA environment is shown. The design is based on Look-Up Tables (LUT)(2,sup>6 x 1) that simulate small RAMs which serve as main components for the look-up realization. Also a method is shown that allows for flexible selection of scaling factors from a set of moduli products of the RNS base. This is made by forming auxiliary MRSs by permutation of moduli of the base. All formed MRSs are associated with the given RNS with respect to the base but each MRS has different set of weights. Thus for the required scaling factor, the suitable MRS can be chosen that provides for the scaling error smaller than 1.

14

Pipelined division of signed numbers with the use of residue arithmetic in FPGA

Czyżak M., Smyk R., Ulman Z.

Computer Applications in Electrical Engineering

|

2013

|

Vol. 11

455--464

EN

An architecture of a pipelined signed residue divider for small number ranges is presented. The divider makes use of the multiplicative division algorithm where initially the reciprocal of the divisor is calculated and subsequently multiplied by the dividend. The divisor represented in the signed binary form is used to compute the approximated reciprocal in the residue form by the table look-up. In order to reduce the needed length of the look-up table address, a reciprocal computation algorithm based on segmentation of the divisor into two segments is used. The signed approximate reciprocal, transformed to the residue representation, is stored in look-up tables division and multiplied by the dividend in the residue form. The obtained quotient is scaled. The pipelined realization of the divider in the FPGA environment is also shown.

15

Hierarchical residue number systems with small moduli and simple converters

Tomczak T.

International Journal of Applied Mathematics and Computer Science

|

2011

|

Vol. 21, no 1

173-192

EN

In this paper, a new class of Hierarchical Residue Number Systems (HRNSs) is proposed, where the numbers are represented as a set of residues modulo factors of 2k š 1 and modulo 2k. The converters between the proposed HRNS and the positional binary number system can be built as 2-level structures using efficient circuits designed for the RNS (2k - 1, 2k, 2k +1). This approach allows using many small moduli in arithmetic channels without large conversion overhead. The advantages resulting from the use of the proposed HRNS depend on the possibility of factorisation of moduli [...].

16

FPGA implementation of the two-stage high-speed FIR filter in residue arithmetic

Czyżak M., Smyk R.

Elektronika : konstrukcje, technologie, zastosowania

|

2011

|

Vol. 52, nr 12

90-92

EN

The paper presents the implementation of the high-speed two-stage finite- impulse response filter (FIR) in residue arithmetic in the Field-Programmable Gate Array (FPGA). The application of residue arithmetic allows one to attain high pipelining rates of the FIR due to the use of small multipliers. This advantage is offset to some extend by the need of scaling in the multi-stage cascade connection of FIR's in order to avoid overflow of number range of the residue number system. The scaling operation may represent significant burden from hardware complexity point of view, hence its effective realization is necessary. The sealer has been applied based on the improved scaling algorithm. Finally the results of implementation of two FIR's with the order N=128 in Xilinx FPGA environment are given and analyzed.

PL

W pracy przedstawiono implementację szybkiego dwustopniowego, kaskadowego filtru FIR w technologii FPGA. Zastosowanie arytmetyki resztowej pozwala na uzyskanie dużych częstotliwości potokowania w związku z użyciem małych mnożników. Zalety wynikające z użycia arytmetyki resztowej są w pewnym stopniu ograniczane koniecznością wykonywania skalowania przy kaskadowym połączeniu filtrów FIR tak, aby uniknąć nadmiaru arytmetycznego w postaci przekroczenia zakresu liczbowego zastosowanego systemu resztowego. Operacja skalowania może przedstawiać istotne obciążenie z punktu widzenia rozmiaru sprzętu, stąd jest konieczna jej efektywna realizacja. W pracy zastosowano skaler opracowany w oparciu o ulepszony algorytm skalowania. Podano rezultaty implementacji dwóch filtrów rzędu N=128. w środowisku Xilinx FPGA.

17

Arytmetyka resztowa w szyfrowaniu RSA

Jabłoński A.

Przegląd Elektrotechniczny

|

2010

|

R. 86, nr 9

145-148

PL

W artykule przedstawiona została metoda poprawy efektywności szyfrowania RSA. Proponowane rozwiązanie korzysta z resztowej reprezentacji liczb (ang. Residue Number System, RNS) oraz konwersji z systemu resztowego do stałobazowego zaproponowanej przez Wang-a. RNS prowadzi do redukcji rozmiaru czynników oraz wprowadzenia zrównoleglenia przetwarzania na poziomie algorytmu. Natomiast Małe Twierdzenie Fermata zostało wykorzystane do redukcji wykładnika w schemacie RSA.

EN

This article presents efficiency improvement method for the RSA coding. Proposed solution uses Residue Number System as well as conversion proposed by Wang’a. The Residue Number System (RNS) leads to reduction of size of factors as well as the induction the parallel processing on level of algorithm. In proposed solution the Small Fermat Theory and Wang conversion was used to reduction of exponent in RSA schema.

18

High-speed FPGA pipelined binary-to-residue converter

Czyżak M., Smyk R.

Poznan University of Technology Academic Journals. Electrical Engineering

|

2008

|

No 58

65-72

EN

An architecture and the FPGA realization of a high-speed pipelined binary-to-residue converter for five-bit moduli are presented. The converter algorithm is based on segmentation of the input binary word into segments of at most five-bit length. For the number represented by each segment modulo m reduction is performed. The obtained residues are added by using the multi-operand modulo adder m based on the carry-save adder (CSA) tree, reduction of the number represented by the output CSA tree vectors to 2m range and fast two-operand modulo m adder.

19

Detekcja nadmiaru multiplikatywnego w resztowym systemie liczbowym

Ożarowski M., Plebanek M., Ulman Z.

Metody Informatyki Stosowanej

|

2008

|

nr 2 (Tom 15)

69-78

PL

W artykule został opisany nowy równoległy algorytm detekcji nadmiaru multiplikatywnego w RNS, który nie wymaga rozszerzenia reprezentacji liczb. Detekcja nadmiaru dla większości możliwych iloczynów a ź b może być zrealizowana bez konieczności wykonywania mnożenia. Realizacja algoytmu w RNS może być wykonana przy użyciu konwersji do systemu liczbowego z mieszanymi podstawami (Mixed-Radix Conversion - MRC) lub przy użyciu funkcji rdzenia liczby.

EN

A new algorithm of multiplicative overflow detection in the Residue Number System has been presented. It makes possible overflow detection for all products a-b, where a,b L {0, 1, ..., M - 1} and M is number range of the system, without executing of time consuming and difficult division. For the majority of products a b overflow detection is possible before realization of multiplication. The algorithm is realize with use the core function.

20

An improved high-speed residue-to-binary converter based on the Chinese Remainder Theorem

Czyżak M.

Pomiary Automatyka Kontrola

|

2007

|

R. 53, nr 4

72-73

EN

A new high-speed residue-to-binary converter for five bit moduli based on the Chinese Remainder Theorem is presented. The orthogonal projections are computed by mapping using five-variable logic functions. The sum of projections is calculated using the Wallace tree. The output carry-save representation is partitioned into four segments in such a way that the sum of the numbers represented by the low-order segments does not exceed the Residue Number System (RNS) range M. The bits of the high-order segments are compressed by the small carry-propagate adder that in effect diminishes the size of the modulo M generator used to reduce the number represented by the high-order segments. The obtained sum is smaller than 2M, thus the effective two-operand final modulo M adder can be used. The proposed converter can be pipelined on the full-adder level.

PL

Zaprezentowano nową architekturę konwertera z systemu resztowego do systemu binarnego dla modułów 5-bitowych opartą na chińskim twierdzeniu o resztach. Projekcje ortogonalne określane są poprzez odczyt z pamięci ich obliczonych wartości. Pamięć symulowana jest poprzez użycie funkcji logicznych o liczbie zmiennych równej bitowej długości modułu. Suma projekcji obliczana jest przy użyciu sumatora wielooperandowego opartego na drzewie Wallace'a. Wyjściowe wektory sumy i przeniesienia są dzielone na cztery segmenty w taki sposób, że suma liczb reprezentowanych przez bity o młodszych wagach nie przekracza zakresu liczbowego systemu resztowego, M. Bity należące do segmentów o starszych wagach są dodawane w niewielkim sumatorze, co w efekcie umożliwia znaczne zmniejszenie rozmiaru generatora stosowanego do redukcji modulo M liczby reprezentowanej przez te bity. Suma otrzymana po zsumowaniu liczby reprezentowanej przez segmenty o młodszych wagach i zredukowanej liczby reprezentowanej przez segmenty starszych wagach nie przekracza 2M, co umożliwia zastosowanie efektywnego sumatora końcowego modulo M. Konwerter w proponowanej konfiguracji może pracować potokowo na poziomie pełnego sumatora.