[go: up one dir, main page]

Golomb et al., 1977 - Google Patents

Integer Convolutions over the Finite Field GF(3⋅2^n+1)

Golomb et al., 1977

Document ID
17092591028533796727
Author
Golomb S
Reed I
Truong T
Publication year
Publication venue
SIAM Journal on Applied Mathematics

External Links

Snippet

An analogue of the discrete Fourier transform is defined in the finite field GF(q_n), where q_n is a prime of the form 3*2^n+1. The arithmetic operations performing this transform require integer multiplication, addition, subtraction, and bit shifts of a word. It is shown that …
Continue reading at epubs.siam.org (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/52—Multiplying; Dividing
    • G06F7/523—Multiplying only
    • G06F7/533—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even
    • G06F7/5332—Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even by skipping over strings of zeroes or ones, e.g. using the Booth Algorithm
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/724—Finite field arithmetic
    • G06F7/726—Inversion; Reciprocal calculation; Division of elements of a finite field
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/729—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic using representation by a residue number system
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03H—IMPEDANCE NETWORKS, e.g. RESONANT CIRCUITS; RESONATORS
    • H03H17/00—Networks using digital techniques
    • H03H17/02—Frequency selective networks
    • H03H17/0223—Computation saving measures; Accelerating measures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
    • G06F17/141—Discrete Fourier transforms
    • G06F17/142—Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
    • G06F2207/7209—Calculation via subfield, i.e. the subfield being GF(q) with q a prime power, e.g. GF ((2**m)**n) via GF(2**m)

Similar Documents

Publication Publication Date Title
US6823000B1 (en) Method and apparatus for optimal dot product calculation
US6038577A (en) Efficient way to produce a delayed version of a maximum length sequence using a division circuit
Zierler Primitive trinomials whose degree is a Mersenne exponent
US5101431A (en) Systolic array for modular multiplication
Golomb et al. Integer Convolutions over the Finite Field GF(3⋅2^n+1)
US4041284A (en) Signal processing devices using residue class arithmetic
CN110620633B (en) Method and device for generating aperiodic four-phase Z-complementary sequence pair signal
US3971927A (en) Modular discrete cosine transform system
Baraniecka et al. Residue number system implementations of number theoretic transforms in complex residue rings
Han et al. New $ M $-ary sequence families with low correlation and large size
Lu Solution of the matrix equation AX+ XB= C
US4020333A (en) Digital filter for filtering complex signals
RU2015537C1 (en) Modulo two multiplier
Dubois et al. The generalized discrete Fourier transform in rings of algebraic integers
Golomb Properties of the sequences 3⋅ 2ⁿ+ 1
US6557019B1 (en) Apparatus and method for compact Haar transform
RU2324972C2 (en) Creator of random module reminder of number
KR100322740B1 (en) Modular computing apparatus and method thereof
Dubois et al. Number theoretic transforms with modulus 2 2q-2 q+ 1
Stamenković ISOMORPHIC TRANSFORMATION AND ITS APPLICATION TO THE MODULO (2^ n+ 1) CHANNEL FOR RNS BASED FIR FILTER DESIGN
Eichmann et al. Number theoretic transform modular residue processors
CA2129203A1 (en) Public key cryptography utilizing elliptic curves
Thomas et al. Implementing exact calculations in hardware
CN110688090B (en) Floating point multiplication method, circuit and equipment for AI (artificial intelligence) calculation
Günther Parallel generation of recurring sequences