Browse Prior Art Database

Multiplier Circuit in Transformed Domain

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

IBM

Related People

Nussbaumer, H: AUTHOR

Abstract

It is well known that Mersenne and Fermat transforms provide an efficient way of implementing digital filters. In such approaches, the bulk of the processing workload corresponds to the multiplication modulo p = 2/q/+/-1 in the transformed domain. Further progress in digital filtering via Mersenne and Fermat transforms is therefore contingent upon improving the computing efficiency of multipliers defined modulo 2/q/+/-1. An efficient implementation for multiplying a variable number X by a constant number B is proposed. ((B.X))(modulo p).

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

Page 1 of 2

Multiplier Circuit in Transformed Domain

It is well known that Mersenne and Fermat transforms provide an efficient way of implementing digital filters. In such approaches, the bulk of the processing workload corresponds to the multiplication modulo p = 2/q/+/-1 in the transformed domain. Further progress in digital filtering via Mersenne and Fermat transforms is therefore contingent upon improving the computing efficiency of multipliers defined modulo 2/q/+/-1. An efficient implementation for multiplying a variable number X by a constant number B is proposed. ((B.X))(modulo p).

The general approach, which will be used here for performing the multiplication, involves logical and mathematical steps similar to those involved in conventional methods for performing a binary multiplication by using so called uniform shifts, i.e., successive groups of bits of the multiplier are analyzed and, depending upon the bit combination of each group, a given contribution representing a multiple of the multiplicand B is accumulated with the previous result.

In the present case, let us define:

(Image Omitted)

Let us also decide to analyze the multiplier term X by groups of four bits spaced by q/4 bits, i.e., x(i), x(i+q/4), x(i+q/2), x(i+3q/4).

If we define A(1) = (1+2/q/2/) (1+2/q/4/) and A(2) = (1+2/q/2/) (1-2/q/4/), then, it may be shown that any contribution to the multiplication deriving from said bit analysis will derive from A(1).B or A(2).B multiplied by +/- 1; +/- 2/q/4/;...