O'Reilly logo

Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems by Gustavo D. Sutter, Gery J.A. Bioul, Jean-Pierre Deschamps

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

15.4 INVERSION IN GF(pn)

In order to execute Algorithm 8.24, the computation resources that correspond to the procedures should be synthesized. Most of them (invert, by_coefficient, sub) have been studied in the preceding sections. The shift procedure can be implemented with a barrel shifter ([ULL1984]). The implementation of the degree procedure could be based on the following iterative algorithm.

Algorithm 15.1 Degree Computation

state(n):=0;
for i in 1..n-1 loop
  if state (n-i+1)=0 and a(n-i)=0 then state (n-i):=0;
  else state (n-i):=1; end if;
end loop;
degree_a:=count (state);

where the count function returns the number of 1's in state. The corresponding iterative circuit includes n − 1 cells. Each of them computes state(i) as a function of a(i) and state(i+1): if state(i+1) = 0 and a(i) = 0 then state(i) = 0; in all other cases state(i) = 1. The circuit that generates the output degree is an (n − 1)-to-log2(n) binary counter.

The data path corresponding to Algorithm 8.24 is shown in Figure 15.14. It is made up of the following computation resources:

degree: implements the degree procedure,

shifter: implements the shift procedure,

coefficient_inverter: implements the invert procedure,

subtractor: implements the sub procedure,

coefficient_multiplier: implements the by_coefficient procedure.

Furthermore, a lot of memory (registers) and connection (multiplexers) resources are necessary. The computation time is proportional to the number of executions of the main iteration (Algorithm ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required