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 ...

Start Free Trial

No credit card required