---------------------------------------------------------------------------- -- Pseudo Euclidean Divider (pseudo_Euclidean_Divider.vhd) -- -- Defines 8 entities: -- - mod_239_inverter (read the table and gives the inverted x) -- - mod_239_reducer (as in ch3) -- - mod_239_multiplier (as in ch3) -- - subtractor parameters (a package for subtractor) -- - subtractor (defines a modular subtraction) -- - binary_algorithm_polynomials_parameters (a package) -- - binary_algorithm_polynomials (the divider) -- ---------------------------------------------------------------------------------------------------------------------------------------- ---- mod 239 inverter -------------------------------------------------------------------------------------------------------------------------- ---- Binary algorithm for division of polynomials -------------------------------------------------------------- --library IEEE; --use IEEE.STD_LOGIC_1164.ALL; --use IEEE.STD_LOGIC_ARITH.ALL; --use IEEE.STD_LOGIC_UNSIGNED.ALL; --library unisim; --use unisim.vcomponents.all; --entity table is -- Port ( address : in std_logic_vector(8 downto 0); -- data : out std_logic_vector(7 downto 0); -- clk : in std_logic); -- end table; -- --architecture low_level_definition of table is ---- ---- Attributes to define ROM contents during implementation synthesis. ---- The information is repeated in the generic map for functional simulation ---- --attribute INIT_00 : string; --attribute INIT_01 : string; --attribute INIT_02 : string; --attribute INIT_03 : string; --attribute INIT_04 : string; --attribute INIT_05 : string; --attribute INIT_06 : string; --attribute INIT_07 : string; --attribute INIT_08 : string; --attribute INIT_09 : string; --attribute INIT_0A : string; --attribute INIT_0B : string; --attribute INIT_0C : string; --attribute INIT_0D : string; --attribute INIT_0E : string; --attribute INIT_0F : string; ---- ---- Attributes to define ROM contents during implementation synthesis. ---- --attribute INIT_00 of ram_256_x_16 : label is "3608216F3E2E990A34A3940C975DE10F10DE5C145718BA1ECD28303C50780100"; --attribute INIT_01 of ram_256_x_16 : label is "811BC0049E8882AF711FE6174BC4C805B21A55C9BD4A2306BEC354A629E81D7F"; --attribute INIT_02 of ram_256_x_16 : label is "4E59120DDAA25EDC0BD62D254889B403765F95D9332ACB53658C6174848672B7"; --attribute INIT_03 of ram_256_x_16 : label is "20B8AE85AB60A002ED4F8F446A4137CF1CB0B687AC73AD83B59D4762A964457A"; --attribute INIT_04 of ram_256_x_16 : label is "EC3B66A7CAC219E413914D15E2DD96A175AA8B468DA8523A6C427C4368393FD3"; --attribute INIT_05 of ram_256_x_16 : label is "EA272BA4D809D07E406D6751EB2FD46E387D696B7B8E638A9C24C5BC165A9079"; --attribute INIT_06 of ram_256_x_16 : label is "E00E9258E35B4CBBE556C1B180CEE7B970D207C6499B2C31E9CCA532269AD53D"; --attribute INIT_07 of ram_256_x_16 : label is "0000000000000000000000000000000000EE779FB3BFC722D135D798DB9311DF"; --attribute INIT_08 of ram_256_x_16 : label is "0000000000000000000000000000000000000000000000000000000000000000"; --attribute INIT_09 of ram_256_x_16 : label is "0000000000000000000000000000000000000000000000000000000000000000"; --attribute INIT_0A of ram_256_x_16 : label is "0000000000000000000000000000000000000000000000000000000000000000"; --attribute INIT_0B of ram_256_x_16 : label is "0000000000000000000000000000000000000000000000000000000000000000"; --attribute INIT_0C of ram_256_x_16 : label is "0000000000000000000000000000000000000000000000000000000000000000"; --attribute INIT_0D of ram_256_x_16 : label is "0000000000000000000000000000000000000000000000000000000000000000"; --attribute INIT_0E of ram_256_x_16 : label is "0000000000000000000000000000000000000000000000000000000000000000"; --attribute INIT_0F of ram_256_x_16 : label is "0000000000000000000000000000000000000000000000000000000000000000"; ---- --begin ---- -- --Instantiate the Xilinx primitive for a block RAM -- ram_256_x_16: RAMB4_S8 -- --translate_off -- --INIT values repeated to define contents for functional simulation -- --synopsys translate_off -- generic map ( -- INIT_00 => -- X"3608216F3E2E990A34A3940C975DE10F10DE5C145718BA1ECD28303C50780100", -- INIT_01 => -- X"811BC0049E8882AF711FE6174BC4C805B21A55C9BD4A2306BEC354A629E81D7F", -- INIT_02 => -- X"4E59120DDAA25EDC0BD62D254889B403765F95D9332ACB53658C6174848672B7", -- INIT_03 => -- X"20B8AE85AB60A002ED4F8F446A4137CF1CB0B687AC73AD83B59D4762A964457A", -- INIT_04 => -- X"EC3B66A7CAC219E413914D15E2DD96A175AA8B468DA8523A6C427C4368393FD3", -- INIT_05 => -- X"EA272BA4D809D07E406D6751EB2FD46E387D696B7B8E638A9C24C5BC165A9079", -- INIT_06 => -- X"E00E9258E35B4CBBE556C1B180CEE7B970D207C6499B2C31E9CCA532269AD53D", -- INIT_07 => -- X"0000000000000000000000000000000000EE779FB3BFC722D135D798DB9311DF", -- INIT_08 => -- X"0000000000000000000000000000000000000000000000000000000000000000", -- INIT_09 => -- X"0000000000000000000000000000000000000000000000000000000000000000", -- INIT_0a => -- X"0000000000000000000000000000000000000000000000000000000000000000", -- INIT_0b => -- X"0000000000000000000000000000000000000000000000000000000000000000", -- INIT_0c => -- X"0000000000000000000000000000000000000000000000000000000000000000", -- INIT_0d => -- X"0000000000000000000000000000000000000000000000000000000000000000", -- INIT_0e => -- X"0000000000000000000000000000000000000000000000000000000000000000", -- INIT_0f => -- X"0000000000000000000000000000000000000000000000000000000000000000") -- --translate_on -- port map( DI => "00000000", -- EN => '1', -- WE => '0', -- RST => '0', -- CLK => clk, -- ADDR => address, -- DO => data(7 downto 0)); ---- --end low_level_definition; ---- ------------------------------------------------------------------------------------ -- -- END OF FILE program.vhd -- ------------------------------------------------------------------------------------ --library IEEE; --use IEEE.STD_LOGIC_1164.ALL; --use IEEE.STD_LOGIC_ARITH.ALL; --use IEEE.STD_LOGIC_UNSIGNED.ALL; --library unisim; --use unisim.vcomponents.all; --entity mod_239_inverter is --port ( --clk: in std_logic; --x: in std_logic_vector(7 downto 0); --z: out std_logic_vector(7 downto 0) --); --end mod_239_inverter; -- --architecture table of mod_239_inverter is -- component table -- port( -- address : in std_logic_vector(8 downto 0); -- data : out std_logic_vector(7 downto 0); -- clk : in std_logic -- ); -- end component; -- signal clkb: std_logic; -- signal address: std_logic_vector(8 downto 0); -- signal data: std_logic_vector(7 downto 0); --begin -- memory_block: table port map(address, data, clkb); -- clkb <= not(clk); -- address(8) <= '0'; -- address(7 downto 0) <= x; -- z <= data; --end table; ------------------------------------------------------------ -- mod 239 inverter ------------------------------------------------------------ library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity mod_239_inverter is port ( clk: in std_logic; x: in std_logic_vector(7 downto 0); z: out std_logic_vector(7 downto 0) ); end mod_239_inverter; architecture table of mod_239_inverter is type RomType is array (0 to 238) of natural; constant ROM: RomType := (0, 1, 120, 80, 60, 48, 40, 205, 30, 186, 24, 87, 20, 92, 222, 16, 15, 225, 93, 151, 12, 148, 163, 52, 10, 153, 46, 62, 111, 33, 8, 54, 127, 29, 232, 41, 166, 84, 195, 190, 6, 35, 74, 189, 201, 85, 26, 178, 5, 200, 196, 75, 23, 230, 31, 113, 175, 130, 136, 158, 4, 192, 27, 129, 183, 114, 134, 132, 116, 97, 140, 101, 83, 203, 42, 51, 217, 149, 95, 118, 3, 180, 137, 72, 37, 45, 214, 11, 220, 94, 162, 218, 13, 18, 89, 78, 122, 69, 100, 169, 98, 71, 157, 181, 131, 173, 115, 172, 135, 182, 176, 28, 207, 55, 65, 106, 68, 143, 79, 237, 2, 160, 96, 171, 133, 174, 184, 32, 211, 63, 57, 104, 67, 124, 66, 108, 58, 82, 168, 141, 70, 139, 170, 117, 161, 150, 221, 226, 21, 77, 145, 19, 228, 25, 194, 202, 167, 102, 59, 236, 121, 144, 90, 22, 188, 197, 36, 156, 138, 99, 142, 123, 107, 105, 125, 56, 110, 212, 47, 235, 81, 103, 109, 64, 126, 208, 9, 216, 164, 43, 39, 234, 61, 213, 154, 38, 50, 165, 204, 233, 49, 44, 155, 73, 198, 7, 210, 112, 185, 231, 206, 128, 177, 193, 86, 229, 187, 76, 91, 227, 88, 146, 14, 224, 223, 17, 147, 219, 152, 215, 53, 209, 34, 199, 191, 179, 159, 119, 238 ); begin z <= conv_std_logic_vector(ROM(conv_integer(x)),8); end table; ------------------------------------------------------------ -- mod 239 reducer ------------------------------------------------------------ library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_arith.all; use ieee.std_logic_unsigned.all; entity mod_239_reducer is port ( x: in std_logic_vector(15 downto 0); z: out std_logic_vector(7 downto 0) ); end mod_239_reducer; architecture circuit of mod_239_reducer is signal x1_by_17, x0, sum, xx1_by_17, xx0, xxx: std_logic_vector(8 downto 0); signal long_xxx, minus_239, dif: std_logic_vector(9 downto 0); signal x2_by_33, long_sum, xx: std_logic_vector(9 downto 0); begin x1_by_17 <= '0'&x(11 downto 8)&x(11 downto 8); x0 <= '0'&x(7 downto 0); sum <= x1_by_17 + x0; x2_by_33 <= '0'&x(15 downto 12)&'0'&x(15 downto 12); long_sum <= '0'∑ xx <= x2_by_33 + long_sum; xx1_by_17 <= "000"&xx(9 downto 8) &"00"&xx(9 downto 8); xx0 <= '0'&xx(7 downto 0); xxx <= xx1_by_17 + xx0; minus_239 <= conv_std_logic_vector(273, 10); long_xxx <= '0'&xxx; dif <= long_xxx + minus_239; with dif(9) select z <= dif(7 downto 0) when '1', xxx(7 downto 0) when others; end circuit; ------------------------------------------------------------ -- mod 239 multiplier ------------------------------------------------------------ library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_arith.all; use ieee.std_logic_unsigned.all; entity mod_239_multiplier is port (x, y: in std_logic_vector(7 downto 0); z: out std_logic_vector(7 downto 0) ); end mod_239_multiplier; architecture circuit of mod_239_multiplier is component mod_239_reducer is port ( x: in std_logic_vector(15 downto 0); z: out std_logic_vector(7 downto 0) ); end component; signal product: std_logic_vector(15 downto 0); begin product <= x*y; main_component: mod_239_reducer port map(product, z); end circuit; ------------------------------------------------------------ -- Subtractor parameters ------------------------------------------------------------ library IEEE; use IEEE.std_logic_1164.all; use IEEE.std_logic_arith.all; use IEEE.std_logic_unsigned.all; package subtractor_parameters is constant k: natural := 8; constant p: std_logic_vector(k-1 downto 0) := conv_std_logic_vector(239, k); end subtractor_parameters; ------------------------------------------------------------ -- Binary algorithm for division of polynomials ------------------------------------------------------------ library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_arith.all; use ieee.std_logic_unsigned.all; use work.subtractor_parameters.all; entity subtractor is port ( x, y: in std_logic_vector(k-1 downto 0); z: out std_logic_vector(k-1 downto 0) ); end subtractor; architecture rtl of subtractor is signal long_x, not_y, sum1: std_logic_vector(k downto 0); signal c1: std_logic; signal z1, z2: std_logic_vector(k-1 downto 0); begin long_x <= '0'&x; not_gates: for i in 0 to k-1 generate not_y(i) <= not(y(i)); end generate; not_y(k) <= '0'; sum1 <= 1 + long_x + not_y; c1 <= sum1(k); z1 <= sum1(k-1 downto 0); z2 <= z1 + p; with c1 select z <= z1 when '1', z2 when others; end rtl; ------------------------------------------------------------ -- Binary algorithm Parameters ------------------------------------------------------------ library IEEE; use IEEE.std_logic_1164.all; use IEEE.std_logic_arith.all; use IEEE.std_logic_unsigned.all; package binary_algorithm_polynomials_parameters is constant k: natural := 8; constant p: std_logic_vector(k-1 downto 0) := conv_std_logic_vector(239, k); --subtype coefficient is natural range 0 to 238; constant m: natural := 17; --subtype degree is natural range 0 to m; type long_polynomial is array(m downto 0) of std_logic_vector(k-1 downto 0); type polynomial is array(m-1 downto 0) of std_logic_vector(k-1 downto 0); constant logm: natural := 6; constant f: long_polynomial := ("00000001", "00000000", "00000000", "00101010", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00011101", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "11101101" ); constant inv_f0_by_f: long_polynomial := ("01110111", "00000000", "00000000", "11011010", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "01101001", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000001" ); constant zero_poly: polynomial := (others => "00000000"); end binary_algorithm_polynomials_parameters; ------------------------------------------------------------ -- Binary algorithm for division of polynomials ------------------------------------------------------------ library IEEE; use IEEE.std_logic_1164.all; use IEEE.std_logic_arith.all; use IEEE.std_logic_unsigned.all; use work.binary_algorithm_polynomials_parameters.all; entity binary_algorithm_polynomials is port( g, h: in polynomial; clk, reset, start: in std_logic; z: out polynomial; done: out std_logic ); end binary_algorithm_polynomials; architecture circuit of binary_algorithm_polynomials is component mod_239_inverter is port ( clk: in std_logic; x: in std_logic_vector(7 downto 0); z: out std_logic_vector(7 downto 0) ); end component; component subtractor is port ( x, y: in std_logic_vector(k-1 downto 0); z: out std_logic_vector(k-1 downto 0) ); end component; component mod_239_multiplier is port ( x, y: in std_logic_vector(7 downto 0); z: out std_logic_vector(7 downto 0) ); end component; signal a, coef_by_b, ab, subtractor_input, subtractor3_output: long_polynomial; signal b, c, d, next_b, next_d, cd, c_or_d, coef_by_cd, b_div_x, ab_div_x, w: polynomial; signal inv_ab, inv_input, coef, w_m, mult_in: std_logic_vector(k-1 downto 0); signal alpha, beta, next_beta, dec_input: std_logic_vector(logm-1 downto 0); signal ce_ac, ce_bd, sel_bd, first, beta_non_negative, alpha_gt_beta, b_zero, final: std_logic; type states is range 0 to 4; signal current_state: states; begin with final select inv_input <= b(0) when '0', a(0) when others; inverter1: mod_239_inverter port map(clk, inv_input, inv_ab); multiplier1: mod_239_multiplier port map(a(0), inv_ab, coef); multipliers2: for i in 0 to m-1 generate a_multiplier: mod_239_multiplier port map(coef, b(i), coef_by_b(i)); end generate; coef_by_b(m) <= conv_std_logic_vector(0, k); subtractor1: for i in 0 to m generate sub1: subtractor port map(a(i), coef_by_b(i), ab(i)); end generate; divide_by_x1: for i in 0 to m-2 generate b_div_x(i) <= b(i+1); end generate; b_div_x(m-1) <= conv_std_logic_vector(0, k); divide_by_x2: for i in 0 to m-1 generate ab_div_x(i) <= ab(i+1); end generate; with sel_bd select next_b <= b_div_x when '0', ab_div_x when others; with final select mult_in <= coef when '0', inv_ab when others; with final select c_or_d <= d when '0', c when others; multipliers3: for i in 0 to m-1 generate a_second_multiplier: mod_239_multiplier port map(mult_in, c_or_d(i), coef_by_cd(i)); end generate; z <= coef_by_cd; subtractor2: for i in 0 to m-1 generate sub2: subtractor port map(c(i), coef_by_cd(i), cd(i)); end generate; with sel_bd select w <= d when '0', cd when others; multipliers4: for i in 0 to m generate a_third_multiplier: mod_239_multiplier port map(w(0), inv_f0_by_f(i), subtractor_input(i)); end generate; subtractor3: for i in 0 to m-1 generate sub3: subtractor port map(w(i), subtractor_input(i), subtractor3_output(i)); end generate; w_m <= conv_std_logic_vector(0, k); sub4: subtractor port map(w_m, subtractor_input(m), subtractor3_output(m)); divide_by_x3: for i in 0 to m-1 generate next_d(i) <= subtractor3_output(i+1); end generate; registers_ac: process(clk) begin if clk'event and clk = '1' then if first = '1' then a <= f; c <= zero_poly; elsif ce_ac = '1' then a(m) <= conv_std_logic_vector(0, k); for i in 0 to m-1 loop a(i) <= b(i); end loop; c <= d; end if; end if; end process registers_ac; registers_bd: process(clk) begin if clk'event and clk = '1' then if first = '1' then b <= h; d <= g; elsif ce_bd = '1' then b <= next_b; d <= next_d; end if; end if; end process registers_bd; register_alpha: process(clk) begin if clk'event and clk = '1' then if first = '1' then alpha <= conv_std_logic_vector(m, logm) ; elsif ce_ac = '1' then alpha <= beta; end if; end if; end process register_alpha; with ce_ac select dec_input <= beta when '0', alpha when others; next_beta <= dec_input - 1; register_beta: process(clk) begin if clk'event and clk = '1' then if first = '1' then beta <= conv_std_logic_vector(m-1, logm) ; elsif ce_bd = '1' then beta <= next_beta; end if; end if; end process register_beta; beta_non_negative <= '1' when beta(logm-1) = '0' else '0'; alpha_gt_beta <= '1' when alpha > beta else '0'; b_zero <= '1' when b(0) = conv_std_logic_vector(0,k) else '0'; control_unit: process(clk, reset, current_state, beta_non_negative, alpha_gt_beta, b_zero) begin case current_state is when 0 to 1 => ce_ac <= '0'; ce_bd <='0'; sel_bd <= '0'; first <= '0'; final <= '1'; done <= '1'; when 2 => ce_ac <= '0'; ce_bd <= '0'; sel_bd <= '0'; first <= '1'; final <= '0'; done <= '0'; when 3 => if beta_non_negative = '0' then ce_ac <= '0'; ce_bd <= '0'; sel_bd <= '0'; elsif b_zero = '1' then ce_ac <= '0'; ce_bd <= '1'; sel_bd <= '0'; elsif alpha_gt_beta = '1' then ce_ac <= '1'; ce_bd <= '1'; sel_bd <= '1'; else ce_ac <= '0'; ce_bd <= '1'; sel_bd <= '1'; end if; first <= '0'; final <= '0'; done <='0'; when 4 => ce_ac <= '0'; ce_bd <='0'; sel_bd <= '0'; first <= '0'; final <= '1'; done <= '0'; end case; if reset = '1' then current_state <= 0; elsif clk'event and clk = '1' then case current_state is when 0 => if start = '0' then current_state <= 1; end if; when 1 => if start = '1' then current_state <= 2; end if; when 2 => current_state <= 3; when 3 => if beta_non_negative = '0' then current_state <= 4; end if; when 4 => current_state <= 0; end case; end if; end process control_unit; end circuit;