An adder or a subtractor in Zp[x]/f(x) is just a set of n modulo p adders or subtractors working in parallel (Algorithms 8.17 and 8.18). The same occurs with the multiplication of a polynomial by an element of Zp: the corresponding circuit is a set of modulo p multipliers working in parallel (Section 8.3.2, procedure by_coefficient). In order to multiply two polynomials, Algorithm 8.22 can be used. The corresponding data path is shown in Figure 15.12. Initially, a(x) must be stored in a (nonrepresented) p-ary shift register, which implements the right_rotate function.
The circuit of Figure 15.12 includes 2.n multipliers and n adders. For relatively large values of p, the corresponding cost could be excessive. Another solution is a completely sequential implementation (see next example).
Example 15.8 (Complete VHDL source code available.) Generate a sequential multiplier based on Algorithm 8.21. A possible data path is shown in Figure 15.13. The VHDL descriptions of the data path and of the control unit are the following:
entity poly_data_path is port ( a, b: in polynomial; clk, clear_z, write_enable: std_logic; addr_i, addr_j: in address; z: inout polynomial ); end poly_data_path; architecture circuit of poly_data_path is component main_operation … end component; signal z_jminus1, z_nminus1, r_j, a_nminus, b_j, next_z, provi: std_logic_vector(m-1 downto 0); signal en: std_logic_vector(n downto 0); signal r: polynomial; begin r<=poly_module; --multiplexers ...