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