Novel RNS Reverse Conversion Algorithm Based on Core Function

Residue Number System (RNS) provides advantages for accelerating arithmetic computations using multiplications and additions only due to absence of long carry propagation logic in its modular adders and multipliers. However, a conversion from RNS to Binary Number System (BNS) is a well-known complex operation requiring larger hardware area and consuming more power than modular multipliers which significantly limits applicability of RNS. Many non-modular operation (e.g. comparison, division) implementations are also based on reverse conversion. This article presents a novel algorithm for RNS to BNS reverse conversion for an arbitrary modular set based on a Core function. We proposed core function coefficients selection method, which allows configuration of the Core function dynamic range and simplifies the conversion complexity. New algorithm allows to achieve up to 13% of hardware area and up to 51% of power consumption reduction and become up to 17% faster than existing best optimized implementations of RNS reverse convertors for the large arbitrary moduli set.