Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

15.4 INVERSION IN GF(pⁿ)

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-log₂(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 ...