FPGA Implementation of an Extended Binary GCD Algorithm for Systolic Reduction of Rational Numbers

摘要

We present the FPGA implementation of an extension of the binary plus-minus systolic algorithm which computes the GCD (greatest common divisor) and also the normal form of a rational number, without using division. A sample array for 8 bit operands consumes 83.4% of an Atmel 40K10 chip and operates at 25 MHz.