Browse Prior Art Database

# Pseudo Mersenne Transform Devices

IP.com Disclosure Number: IPCOM000088654D
Original Publication Date: 1977-Jul-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 2 page(s) / 31K

IBM

## Related People

Nussbaumer, H: AUTHOR

## Abstract

Pseudo Mersenne and pseudo Fermat transforms have been defined in rings submultiple of 2/q/-1 and 2/q/+1, respectively. These transforms are very attractive for computing convolutions because they generally can be evaluated via a Fast Fourier Transform algorithm, and, therefore, are very useful for digital filtering.

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 60% of the total text.

Page 1 of 2

Pseudo Mersenne Transform Devices

Pseudo Mersenne and pseudo Fermat transforms have been defined in rings submultiple of 2/q/-1 and 2/q/+1, respectively. These transforms are very attractive for computing convolutions because they generally can be evaluated via a Fast Fourier Transform algorithm, and, therefore, are very useful for digital filtering.

Moreover, the bulk of this kind of computation is performed with very easily implemented arithmetic circuits defined modulo p=2/q/+/-1, but a final operation modulo a submultiple of p is then required. In practice, implementing this last operation can be costly. We propose an improved means for simplifying the circuits required.

Let us, for instance, consider the case of pseudo Mersenne transforms defined modulo M, with M being a submultiple of p=2/q/-1. For instance, one may select a prime number q(1) in order to have q =q/2/(1), and M = 2/q//2//1-1/ 2/q/1(-1).

Under these conditions, the pseudo Mersenne transforms {A(k)} of a series {a(n)} would derive from:

(Image Omitted)

This transform has the circular convolution property, which means that the convolution product z(m) = {a(n)} * x(n) of integer sequences a(n) and {x(n)} can be evaluated modulo M = 2/q/-1/2/q/1(-1) by computing the transforms {A(k)} and {X(k)} of {a(n)} and {x(n)} and taking the inverse transform {z(m)} of of {A(k).X(k)}. In practice, z(m) is derived by feeding {a(n)} and {x(n)} into pseudo Mersenne transformers T(1) and T(2), respectively, feed...