An improved Chen's parity detection technique for the two-moduli set

Abstract

This paper improved Chen's residue number system (RNS) parity detection technique such that the original two-moduli set {2 ^h −1, 2 ^h +1} is extended to {2p−1, 2p+1}, where h and p are positive integers. Given an RNS number X=(x ₁, x ₂) based on the extended two-moduli set, it is found that the parity of X is (p mod 2)·y ₀ ⊕ y ₁ if x ₁≥x ₂, where y ₁ y ₀ denotes the binary representation of x ₁+x ₂ mod 4. On the contrary, if x ₁<x ₂, the parity of X is . Obviously, our parity technique, compared with Lu and Chiang's, can discover the parity of an RNS number without the table lookup and fractional number approaches.

Keywords:

• RNS
• parity detection technique

2000 AMS Subject Classification :

• 00A06