Diminished-1 multiplier for a fast convolver and correlator using the Fermat number transform

Abstract

Work on using the Fermat number transform (FNT) for convolution and correlation has recently appeared in the literature, and it is known that by using the diminished-1 number scheme all the operations required for the FNT can be computed exactly. The paper presents a diminished-1 parallel multiplier that improves the overall speed of an FNT based convolver/ correlator. The multiplication algorithm used realises the diminished-1 product (A · B − 1) = (A · B) − 1. The work has also highlighted an error in the above algorithm when the data is equal to −1 and offers a method to overcome this problem.