Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

15.3 OPERATIONS IN Z_p[x]/f(x)

An adder or a subtractor in Z_p[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 Z_p: 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 ...