Simple, fast, and exact RNS scaler for the three-moduli set {2n - 1, 2n, 2n + 1}
Scaling in RNS has always been conceived as a performance bottleneck similar to the residue-to-binary conversion problem due to the inefficient intermodulo operation. In this paper, a simple and fast scaling algorithm for the three-moduli set {2n - 1, 2n, 2n + 1} RNS is proposed. The complexity of i...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2015
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/79409 http://hdl.handle.net/10220/25604 |
| _version_ | 1811678677003403264 |
|---|---|
| author | Chang, Chip-Hong Low, Jeremy Yung Shern |
| author2 | School of Electrical and Electronic Engineering |
| author_facet | School of Electrical and Electronic Engineering Chang, Chip-Hong Low, Jeremy Yung Shern |
| author_sort | Chang, Chip-Hong |
| collection | NTU |
| description | Scaling in RNS has always been conceived as a performance bottleneck similar to the residue-to-binary conversion problem due to the inefficient intermodulo operation. In this paper, a simple and fast scaling algorithm for the three-moduli set {2n - 1, 2n, 2n + 1} RNS is proposed. The complexity of intermodulo operation has been resolved by a new formulation of scaling an integer in RNS domain by one of its moduli. By elegant exploitation of the Chinese Remainder Theorem and the number theoretic properties for this moduli set, the design can be readily implemented by a standard cell based design methodology. The low cost VLSI architecture without any read-only memory (ROM) makes it easier to fuse into and pipeline with other residue arithmetic operations of a RNS-based processor to increase the throughput rate. The proposed RNS scaler possesses zero scaling error and has a critical path delay of only 2[log2n]+ 9 units in unit-gate model. Besides the scaled residue numbers, the scaled integer in normal binary representation is also produced as a byproduct of this process, which saves the residue-to-binary converter when the binary representation of scaled integer is also required. Our experimental results show that the proposed RNS scaler is smaller and faster than the most area-efficient adder-based design and the fastest ROM-based design besides being the most power efficient among all scalers evaluated for the same three-moduli set. |
| first_indexed | 2024-10-01T02:57:03Z |
| format | Journal Article |
| id | ntu-10356/79409 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:57:03Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | ntu-10356/794092020-03-07T13:57:23Z Simple, fast, and exact RNS scaler for the three-moduli set {2n - 1, 2n, 2n + 1} Chang, Chip-Hong Low, Jeremy Yung Shern School of Electrical and Electronic Engineering DRNTU::Engineering::Electrical and electronic engineering::Electronic circuits Scaling in RNS has always been conceived as a performance bottleneck similar to the residue-to-binary conversion problem due to the inefficient intermodulo operation. In this paper, a simple and fast scaling algorithm for the three-moduli set {2n - 1, 2n, 2n + 1} RNS is proposed. The complexity of intermodulo operation has been resolved by a new formulation of scaling an integer in RNS domain by one of its moduli. By elegant exploitation of the Chinese Remainder Theorem and the number theoretic properties for this moduli set, the design can be readily implemented by a standard cell based design methodology. The low cost VLSI architecture without any read-only memory (ROM) makes it easier to fuse into and pipeline with other residue arithmetic operations of a RNS-based processor to increase the throughput rate. The proposed RNS scaler possesses zero scaling error and has a critical path delay of only 2[log2n]+ 9 units in unit-gate model. Besides the scaled residue numbers, the scaled integer in normal binary representation is also produced as a byproduct of this process, which saves the residue-to-binary converter when the binary representation of scaled integer is also required. Our experimental results show that the proposed RNS scaler is smaller and faster than the most area-efficient adder-based design and the fastest ROM-based design besides being the most power efficient among all scalers evaluated for the same three-moduli set. Accepted version 2015-05-19T09:15:34Z 2019-12-06T13:24:37Z 2015-05-19T09:15:34Z 2019-12-06T13:24:37Z 2011 2011 Journal Article Chang, C.-H., & Low, J. Y. S. (2011). Simple, fast, and exact RNS scaler for the three-moduli set {2n - 1, 2n, 2n + 1}. IEEE transactions on circuits and systems I : regular papers, 58(11), 2686-2697. 1549-8328 https://hdl.handle.net/10356/79409 http://hdl.handle.net/10220/25604 10.1109/TCSI.2011.2142950 en IEEE transactions on circuits and systems I : regular papers © 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: [http://dx.doi.org/10.1109/TCSI.2011.2142950]. 12 p. application/pdf |
| spellingShingle | DRNTU::Engineering::Electrical and electronic engineering::Electronic circuits Chang, Chip-Hong Low, Jeremy Yung Shern Simple, fast, and exact RNS scaler for the three-moduli set {2n - 1, 2n, 2n + 1} |
| title | Simple, fast, and exact RNS scaler for the three-moduli set {2n - 1, 2n, 2n + 1} |
| title_full | Simple, fast, and exact RNS scaler for the three-moduli set {2n - 1, 2n, 2n + 1} |
| title_fullStr | Simple, fast, and exact RNS scaler for the three-moduli set {2n - 1, 2n, 2n + 1} |
| title_full_unstemmed | Simple, fast, and exact RNS scaler for the three-moduli set {2n - 1, 2n, 2n + 1} |
| title_short | Simple, fast, and exact RNS scaler for the three-moduli set {2n - 1, 2n, 2n + 1} |
| title_sort | simple fast and exact rns scaler for the three moduli set 2n 1 2n 2n 1 |
| topic | DRNTU::Engineering::Electrical and electronic engineering::Electronic circuits |
| url | https://hdl.handle.net/10356/79409 http://hdl.handle.net/10220/25604 |
| work_keys_str_mv | AT changchiphong simplefastandexactrnsscalerforthethreemoduliset2n12n2n1 AT lowjeremyyungshern simplefastandexactrnsscalerforthethreemoduliset2n12n2n1 |