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

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;

image

Figure 15.12 Multiplier in GF(pn).

image

Figure 15.13 Sequential multiplier in GF(pn).

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset