Construction of Residue Number System Using Hardware Efficient Diagonal Function
The residue number system (RNS) is a non-positional number system that allows one to perform addition and multiplication operations fast and in parallel. However, because the RNS is a non-positional number system, magnitude comparison of numbers in RNS form is impossible, so a division operation and...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-06-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/8/6/694 |
| _version_ | 1798024301448790016 |
|---|---|
| author | Maria Valueva Georgii Valuev Nataliya Semyonova Pavel Lyakhov Nikolay Chervyakov Dmitry Kaplun Danil Bogaevskiy |
| author_facet | Maria Valueva Georgii Valuev Nataliya Semyonova Pavel Lyakhov Nikolay Chervyakov Dmitry Kaplun Danil Bogaevskiy |
| author_sort | Maria Valueva |
| collection | DOAJ |
| description | The residue number system (RNS) is a non-positional number system that allows one to perform addition and multiplication operations fast and in parallel. However, because the RNS is a non-positional number system, magnitude comparison of numbers in RNS form is impossible, so a division operation and an operation of reverse conversion into a positional form containing magnitude comparison operations are impossible too. Therefore, RNS has disadvantages in that some operations in RNS, such as reverse conversion into positional form, magnitude comparison, and division of numbers are problematic. One of the approaches to solve this problem is using the diagonal function (DF). In this paper, we propose a method of RNS construction with a convenient form of DF, which leads to the calculations modulo <inline-formula> <math display="inline"> <semantics> <mrow> <msup> <mn>2</mn> <mi>n</mi> </msup> </mrow> </semantics> </math> </inline-formula>, <inline-formula> <math display="inline"> <semantics> <mrow> <msup> <mn>2</mn> <mi>n</mi> </msup> <mo>−</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula> or <inline-formula> <math display="inline"> <semantics> <mrow> <msup> <mn>2</mn> <mi>n</mi> </msup> <mo>+</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula> and allows us to design efficient hardware implementations. We constructed a hardware simulation of magnitude comparison and reverse conversion into a positional form using RNS with different moduli sets constructed by our proposed method, and used different approaches to perform magnitude comparison and reverse conversion: DF, Chinese remainder theorem (CRT) and CRT with fractional values (CRTf). Hardware modeling was performed on Xilinx Artix 7 xc7a200tfbg484-2 in Vivado 2016.3 and the strategy of synthesis was highly area optimized. The hardware simulation of magnitude comparison shows that, for three moduli, the proposed method allows us to reduce hardware resources by 5.98−49.72% in comparison with known methods. For the four moduli, the proposed method reduces delay by 4.92−21.95% and hardware costs by twice as much by comparison to known methods. A comparison of simulation results from the proposed moduli sets and balanced moduli sets shows that the use of these proposed moduli sets allows up to twice the reduction in circuit delay, although, in several cases, it requires more hardware resources than balanced moduli sets. |
| first_indexed | 2024-04-11T18:00:12Z |
| format | Article |
| id | doaj.art-d27f1457a5d647d69ebd23a75177c681 |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-04-11T18:00:12Z |
| publishDate | 2019-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-d27f1457a5d647d69ebd23a75177c6812022-12-22T04:10:32ZengMDPI AGElectronics2079-92922019-06-018669410.3390/electronics8060694electronics8060694Construction of Residue Number System Using Hardware Efficient Diagonal FunctionMaria Valueva0Georgii Valuev1Nataliya Semyonova2Pavel Lyakhov3Nikolay Chervyakov4Dmitry Kaplun5Danil Bogaevskiy6Department of Applied Mathematics and Mathematical Modeling, North-Caucasus Federal University, Stavropol 355009, RussiaDepartment of Applied Mathematics and Mathematical Modeling, North-Caucasus Federal University, Stavropol 355009, RussiaDepartment of Higher Algebra and Geometry, North-Caucasus Federal University, Stavropol 355009, RussiaDepartment of Applied Mathematics and Mathematical Modeling, North-Caucasus Federal University, Stavropol 355009, RussiaDepartment of Applied Mathematics and Mathematical Modeling, North-Caucasus Federal University, Stavropol 355009, RussiaDepartment of Automation and Control Processes, St. Petersburg Electrotechnical University “LETI”, Saint Petersburg 197376, RussiaDepartment of Automation and Control Processes, St. Petersburg Electrotechnical University “LETI”, Saint Petersburg 197376, RussiaThe residue number system (RNS) is a non-positional number system that allows one to perform addition and multiplication operations fast and in parallel. However, because the RNS is a non-positional number system, magnitude comparison of numbers in RNS form is impossible, so a division operation and an operation of reverse conversion into a positional form containing magnitude comparison operations are impossible too. Therefore, RNS has disadvantages in that some operations in RNS, such as reverse conversion into positional form, magnitude comparison, and division of numbers are problematic. One of the approaches to solve this problem is using the diagonal function (DF). In this paper, we propose a method of RNS construction with a convenient form of DF, which leads to the calculations modulo <inline-formula> <math display="inline"> <semantics> <mrow> <msup> <mn>2</mn> <mi>n</mi> </msup> </mrow> </semantics> </math> </inline-formula>, <inline-formula> <math display="inline"> <semantics> <mrow> <msup> <mn>2</mn> <mi>n</mi> </msup> <mo>−</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula> or <inline-formula> <math display="inline"> <semantics> <mrow> <msup> <mn>2</mn> <mi>n</mi> </msup> <mo>+</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula> and allows us to design efficient hardware implementations. We constructed a hardware simulation of magnitude comparison and reverse conversion into a positional form using RNS with different moduli sets constructed by our proposed method, and used different approaches to perform magnitude comparison and reverse conversion: DF, Chinese remainder theorem (CRT) and CRT with fractional values (CRTf). Hardware modeling was performed on Xilinx Artix 7 xc7a200tfbg484-2 in Vivado 2016.3 and the strategy of synthesis was highly area optimized. The hardware simulation of magnitude comparison shows that, for three moduli, the proposed method allows us to reduce hardware resources by 5.98−49.72% in comparison with known methods. For the four moduli, the proposed method reduces delay by 4.92−21.95% and hardware costs by twice as much by comparison to known methods. A comparison of simulation results from the proposed moduli sets and balanced moduli sets shows that the use of these proposed moduli sets allows up to twice the reduction in circuit delay, although, in several cases, it requires more hardware resources than balanced moduli sets.https://www.mdpi.com/2079-9292/8/6/694residue number system (RNS)diagonal function (DF)Chinese remainder theorem (CRT) |
| spellingShingle | Maria Valueva Georgii Valuev Nataliya Semyonova Pavel Lyakhov Nikolay Chervyakov Dmitry Kaplun Danil Bogaevskiy Construction of Residue Number System Using Hardware Efficient Diagonal Function Electronics residue number system (RNS) diagonal function (DF) Chinese remainder theorem (CRT) |
| title | Construction of Residue Number System Using Hardware Efficient Diagonal Function |
| title_full | Construction of Residue Number System Using Hardware Efficient Diagonal Function |
| title_fullStr | Construction of Residue Number System Using Hardware Efficient Diagonal Function |
| title_full_unstemmed | Construction of Residue Number System Using Hardware Efficient Diagonal Function |
| title_short | Construction of Residue Number System Using Hardware Efficient Diagonal Function |
| title_sort | construction of residue number system using hardware efficient diagonal function |
| topic | residue number system (RNS) diagonal function (DF) Chinese remainder theorem (CRT) |
| url | https://www.mdpi.com/2079-9292/8/6/694 |
| work_keys_str_mv | AT mariavalueva constructionofresiduenumbersystemusinghardwareefficientdiagonalfunction AT georgiivaluev constructionofresiduenumbersystemusinghardwareefficientdiagonalfunction AT nataliyasemyonova constructionofresiduenumbersystemusinghardwareefficientdiagonalfunction AT pavellyakhov constructionofresiduenumbersystemusinghardwareefficientdiagonalfunction AT nikolaychervyakov constructionofresiduenumbersystemusinghardwareefficientdiagonalfunction AT dmitrykaplun constructionofresiduenumbersystemusinghardwareefficientdiagonalfunction AT danilbogaevskiy constructionofresiduenumbersystemusinghardwareefficientdiagonalfunction |