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 z_jminus1<=z(n-addr_j-2) when addr_j<n-1 else zero; r_j<=r(n-addr_j-1) when addr_j<n else zero; b_j<=b(n-addr_j-1) when addr_j<n else zero; a_nminus<=a(n-addr_i-1); -- z_nminus1<=z(n-1); main_component: main_operation port map(z_jminus1, z_nminus1, r_j, a_nminus, b_j, next_z); --address decoder: process(addr_j, write_enable) begin for i in 0 to n-2 loop if addr_j=n-i-1 and write_enable=‘1’ then en(i)<=‘1’; else en(i)<=‘0’; end if; end loop; if addr_j=n and write_enable=‘1’ then en(n-1)<=‘1’; else en(n-1)<=‘0’; end if; if addr_j=0 and write_enable=‘1’ then en(n)<=‘1’; else en(n)<=‘0’; end if; end process; -- registers: for i in 0 to n-2 generate process(clk) begin if clk'event and clk=‘1’ then if clear_z=‘1’ then z(i)<=zero; elsif en(i)=‘1’ then z(i)<=next_z; end if; end if; end process; end generate; process(clk) begin if clk'event and clk=‘1’ then if clear_z=‘1’ then z(n-1)<=zero; elsif en(n-1)=‘1’then z(n-1)<=provi; end if; end if; end process; process(clk) begin if clk'event and clk=‘1’ then if en(n)=‘1’ then provi<=next_z; end if; end if; end process; end circuit; library ieee; use ieee.std_logic_1164.all; use work.mypackage.all; entity poly_control_unit is port ( clk, reset, start: in std_logic; addr_i, addr_j: inout natural; clear_z, write_enable, done: out std_logic ); end poly_control_unit; architecture rtl of poly_control_unit is subtype internal_state is natural range 0 to 5; signal state: internal_state; begin process(clk, reset) begin case state is when 0=>clear_z<=‘0’; write_enable<=‘0’; done<=‘1’; when 1=>clear_z<=‘0’; write_enable<=‘0’; done<=‘1’; when 2=>clear_z<=‘1’; write_enable<=‘0’; done<=‘0’; when 3=>clear_z<=‘0’; write_enable<=‘0’; done<=‘0’; when 4=>clear_z<=‘0’; write_enable<=‘1’; done<=‘0’; when 5=>clear_z<=‘0’; write_enable<=‘0’; done<=‘0’; end case; if reset=‘1’ then state<=0; elsif clk'event and clk=‘1’ then case state is when 0=>if start=‘0’ then state<=state+1; end if; when 1=>if start=‘1’ then state<=state+1; end if; when 2=>addr_i<=0; state<=state+1; when 3=>addr_j<=0; state<=state+1; when 4=>if addr_j=n then state<=state+1; else addr_j<=addr_j+1; end if; when 5=>if addr_i=n-1 then state<=0; else addr_i<=addr_i+1; state<=3; end if; end case; end if; end process; end rtl;