Back to results
US 2024/0152330 A1Published application
K-cluster residue number system using look-up tables with reduced data capacity for addition, subtraction, and multiplication operations
AssigneeKneron Inc.
InventorsOscar Ming Kin Law, Chun Chen Liu
Life of this patent
Estimating the term…
Abstract
A k-cluster residue number system has a processor and a memory. The processor is used to generate an addition and subtraction look-up table and a multiplication look-up table based on periodic behaviors of the modulo to compress the sizes of the addition and subtraction look-up table and the multiplication look-up table. The addition and subtraction look-up table has 2mi cells for recording values from zero to (mi−1) in an ascending order twice, wherein mi is a coprime integer of a modular set of the k-cluster residue number system. The multiplication look-up table has S cells, where S = ( m i 2 - 1 4 ) .
Claims14
A method for performing addition and subtraction operations in a k-cluster residue number system, the method comprising:
- generating an addition and subtraction look-up table comprising 2mi cells for recording values from zero to (mi−1) in an ascending order twice, wherein mi is a coprime integer of a modular set of the k-cluster residue number system;
- storing the addition and subtraction look-up table in a memory of the k-cluster residue number system;
- retrieving a value recorded in a cell at position Q of the addition and subtraction look-up table when performing an addition operation on two integers A and B, where Q=((A mod mi)+(B mod mi));
- and
- retrieving a value recorded in a cell at position R of the addition and subtraction look-up table when subtracting an integer X by an integer Y, where R=(X mod mi)−(Y mod mi)=(X mod mi)+(mi−(Y mod mi))=rx+(mi−ry)=rx+ry′, rx is equal to (X mod mi), ry is equal to (Y mod mi), and ry′ is equal to (mi−(Y mod mi)).
2 more elements
A method for performing multiplication operations in a k-cluster residue number system, the method comprising:
- generating a multiplication look-up table for a coprime integer mi of a modular set of the k-cluster residue number system, wherein the coprime integer mi is not 2, the multiplication look-up table is composed of S cells,
- S
- =
- (
- m
- i
- 2
- -
- 1
- 4
- )
- ;
- and
- storing the multiplication look-up table in a memory of the k-cluster residue number system;
- and
- performing a multiplication operation on a multiplicand and a multiplicator using the multiplication look-up table, comprising:
- determining whether a complement of the multiplicand is greater than or equal to the multiplicator;
- if it is determined that the complement of the multiplicand is greater than or equal to the multiplicator, perform the following steps:
- selecting the multiplicand as a column entry and the multiplicator as a row entry, and determining whether the column entry is greater than or equal to the row entry;
- if it is determined that the column entry is greater than or equal to the row entry, keeping the column entry and the row entry;
- and
- if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry;
- if it is determined that the complement of the multiplicand is less than the multiplicator, perform the following steps:
- selecting the complement of the multiplicand as the column entry and a complement of the multiplicator as the row entry, and determining whether the column entry is greater than or equal to the complement of the row entry;
- if it is determined that the column entry is greater than or equal to the complement of the row entry, keeping the column entry and the row entry;
- and
- if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry;
- and
- retrieving a value from the multiplication look-up table as a product of the multiplicand and the multiplicator according to the column entry and the row entry.
26 more elements
A k-cluster residue number system comprising:
- a processor configured to:
- generate an addition and subtraction look-up table comprising 2mi cells for recording values from zero to (mi−1) in an ascending order twice, wherein mi is a coprime integer of a modular set of the k-cluster residue number system;
- retrieve a value recorded in a cell at position Q of the addition and subtraction look-up table when performing an addition operation on two integers A and B, where Q=((A mod mi)+(B mod mi));
- and
- retrieve a value recorded in a cell at position R of the addition and subtraction look-up table when subtracting an integer X by an integer Y, where R=(X mod mi)−(Y mod mi)=(X mod mi)+(mi−(Y mod mi))=rx+(mi−ry)=(rx+ry′), rx is equal to (X mod mi), ry is equal to (Y mod mi), and ry′ is equal to (mi−(Y mod mi));
- and
- a memory coupled to the processor and configured to store the addition and subtraction look-up table.
4 more elements
A k-cluster residue number system, comprising:
- a processor configured to:
- generate a multiplication look-up table for a coprime integer mi of a modular set of the k-cluster residue number system, wherein the coprime integer mi is not 2, and the multiplication look-up table is composed of S cells,
- S
- =
- (
- m
- i
- 2
- -
- 1
- 4
- )
- ;
- and
- perform a multiplication operation on a multiplicand and a multiplicator using the multiplication look-up table by performing the following steps:
- determining whether a complement of the multiplicand is greater than or equal to the multiplicator;
- if it is determined that the complement of the multiplicand is greater than or equal to the multiplicator, perform the following steps:
- selecting the multiplicand as a column entry and the multiplicator as a row entry, and determining whether the column entry is greater than or equal to the row entry;
- if it is determined that the column entry is greater than or equal to the row entry, keeping the column entry and the row entry;
- and
- if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry;
- if it is determined that the complement of the multiplicand is less than the multiplicator, perform the following steps:
- selecting the complement of the multiplicand as the column entry and a complement of the multiplicator as the row entry, and determining whether the column entry is greater than or equal to the complement of the row entry;
- if it is determined that the column entry is greater than or equal to the complement of the row entry, keeping the column entry and the row entry;
- and
- if it is determined that the column entry is less than the row entry, interchanging the column entry and the row entry;
- and
- retrieving a value from the multiplication look-up table as a product of the multiplicand and the multiplicator according to the column entry and the row entry;
- and
- a memory coupled to the processor and configured to store the multiplication look-up table.
27 more elements
Dependencies are inferred from the claim text.