Multi-value digital calculating circuits, including multipliers

• US 7,562,106 B2
• Filed: 12/20/2004
• Issued: 07/14/2009
• Est. Priority Date: 08/07/2004
• Status: Expired due to Fees

• Current Assignee: Ternarylogic LLC
• Original Assignee: Ternarylogic LLC
• Inventors: Lablans, Peter
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US11/018,956
• Publication Number:
  US 20060031278A1
• Time in Patent Office: 1,667 Days
• Field of Search: 708/493, 708/620, 708/623, 708/624
• US Class Current: 708/493
• CPC Class Codes: G06F 7/49 Computations with a radix, other than binary, 8, 16 or decimal, e.g. ternary, negative or imaginary radices, mixed radix non-linear PCM G06F7/4824 takes precedence

Abstract

Apparatus and method for performing multi-value arithmetic operations are disclosed. Multi-value signals can be added, subtracted and multiplied using a first truth table to generate a residue and a second truth table to generate a carry. Additionally, method and apparatus to efficiently perform the function a0b1+a1b0 on multi-value signals are disclosed. Also an efficient method of processing large binary signals is disclosed.

Claims

1. Apparatus for performing a multiplication operation of a multiplicand A having at least radix-n digits a0 and a1 with and a multiplier B having at least radix-n digits b0 and b1, with n>

2 and each of the radix-n digits a0, a1, b0 and b1 not being zero, comprising;

a first circuit in a first plurality of circuits, the first circuit implementing a table that determines a residue of a sum of a product of a0 and b1 and a product of a1 and b0, the first circuit having a first and a second input and an output, wherein;

a residue of the product of a0 and b1 and a residue of the product of a1 and b0 have an identical radix-n position;

the output of the first circuit provides a signal representing the residue of the sum when the first input receives a signal representing a0 and the second input receives a signal representing a1;

the first circuit is selected from the first plurality of circuits based on b0 and b1; and

no signal representing the residue of the first product is generated to determine the residue of the sum;

a second circuit in a second plurality of circuits, the second circuit having a first and a second input and an output, the second circuit implementing a table that determines a carry of the sum of the product of a0 and b1 and the product of a1 and b0-wherein;

the output of the second circuit in the second plurality of circuits provides a signal representing the carry of the sum when the first input of the second circuit receives the signal representing a1 and the second input of the second circuit receives the signal representing a1 and the second circuit is selected from the second plurality of circuits based on b0 and b1;

means for determining the first circuit from the first plurality of circuits based on the value of b0 and b1; and

means for determining the second circuit from the second plurality of circuits based on the value of b0 and b1.

2. Apparatus for performing a radix-n multiplication with n>

2 of a constant multiplier having at least a first and a second radix-n digit and a variable multiplicand having at least a first radix-n digit represented by a first n-valued signal and a second radix-n digit represented by a second n-valued signal with n>

2, each n-valued signal being provided on a single signal line and able to assume one of 3 or more states and each radix-n digit not being equal to zero, comprising;

an implementation of a first logic table having a first input enabled to receive the first n-valued signal and a second input enabled to receive the second n-valued signal and an output enabled to provide an n-valued signal representing a residue of a sum of a first product of the first digit of the multiplicand and the second digit of the multiplier and a second product of the second digit of the multiplicand and the first digit of the multiplier, wherein;

a residue of the first product and a residue of the second product have identical radix-n positions; and

no signal representing the residue of the first product is generated to determine the residue of the sum; and

an implementation of a second logic table having a first input enabled to receive the first n-valued signal and a second input enabled to receive the second n-valued signal and an output enabled to provide an n-valued signal representing a carry of the sum of the first product and the second product.

3. A digital filter for processing an input signal represented by a:

plurality of samples into an output signal represented by a plurality of samples, wherein a sample of the plurality of input samples is represented by at least a first and a second radix-n digit with n>

2 and a sample of the plurality of output samples is represented by at least one third radix- n digit with n>

2, a each radix-n digit is represented by an n-valued signal on a single signal line and able to assume one of 3 or more states, a sample of the output signal is generated by processing at least a first n -valued signal representing the first radix-n digit and a second n-valued signal representing the second radix-n digit by generating a residue of a sum of a first and a second partial product, comprising;

a first circuit implementing a first n -valued logic table, with the first n-valued signal provided on a first input of the first circuit and with the second n-valued signal provided on a second input of the first circuit to generate on an output of the first circuit an n-valued signal representing the residue of a the sum of a first partial product of the first radix-n digit and a first constant and a second partial product of the second radix-n digit and a second constant, wherein a residue of the first partial product and a residue of the second partial product have an identical radix-n position, and whereby no signal representing the residue of the first partial product is generated to determine the residue of the sum; and

a second circuit implementing a second n-valued logic table with the first n-valued signal provided on a first input of the second circuit and with the second n-valued signal provided on a second input of the second circuit to generate on an output of the second circuit an n-valued signal representing a carry of the sum of the first and the second partial product, and wherein

a relation between the plurality of output samples and the plurality of input samples is provided by

$y<br><br><br><br>\left(m\right)=\underset{i=0}{\overset{k}{\sum <br><br>}}<br><br><br><br>\mathrm{ci}·<br><br>x<br><br><br><br>\left(m-i\right)+\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br><br><br>\mathrm{di}·<br><br>y<br><br><br><br>\left(m-i\right)$

 

with y(i) is an output sample at time i, x(i) is an input sample at time i and ci and di are predefined constants.