Browse Prior Art Database

# Generalized Mersenne and Fermat Transforms

IP.com Disclosure Number: IPCOM000086683D
Original Publication Date: 1976-Oct-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 2 page(s) / 40K

IBM

## Related People

Nussbaumer, H: AUTHOR

## Abstract

Mersenne and Fermat number transforms have been shown to allow a drastic processing reduction over conventional approaches for computer digital filters.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 63% of the total text.

Page 1 of 2

Generalized Mersenne and Fermat Transforms

Mersenne and Fermat number transforms have been shown to allow a drastic processing reduction over conventional approaches for computer digital filters.

When the signal samples are defined in radix 2 arithmetic, basic arithmetic operations performed modulo 2/q/+/- 1 can be implemented very simply, provided a code conversion is performed on the input numbers in the case of a modulo 2/q/+1 system.

This remark is not only valid for radix 2 arithmetic but could be extended to arithmetic with higher radix. For instance, let us consider the case of radix W =
3. In this case, the signal samples will be represented by a q digit number with:

(Image Omitted)

The arithmetic circuits to be used will have to operate modulo 3/q/+1 Such circuits are quite simple when operating modulo 3/q/-1, while they are more elaborate modulo 3/q/+1. In order to simplify operations performed modulo 3/q/+1, the input sequence (c(n)) is transformed into a new input sequence (c(n)) with: c(n) = 3/q/-a(n).

In this case, the transform C will be computed on the sequence cn according to (1) and the final output samples A(k) will be recovered by a final operation A(k) = C(k) 1. The condition a(n) = o will be depicted by an extra bit flag which will be "1" when a(n) = o, with all other bits then being equal to zero.

Under these conditions, the arithmetic becomes much simpler. For instance, a multiplication of a by 3 corresponds in the transposed system to a m...