## 15.4 INVERSION IN *GF*(*p*^{n})

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;foriin1..n-1loopifstate (n-i+1)=0 and a(n-i)=0thenstate (n-i):=0;elsestate (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_{2}(*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 ...

Get *Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems* now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.