Ich habe mal das Primzahlsieb in VHDL nachgebaut. Eine nette Übung. Mir gefällt das ganze aber noch nicht vom Aufbau, Bezeichnung der Signale usw. Wie kann man es besser machen ? Ist etwas lang, aber wie kann ich hier eine Zip-Datei hochladen ? Wer kann etwas zu der folgenden Warnung und den zwei Infos sagen ? Ich finde die Ursachen nicht. WARNING:Xst:1780 - Signal <clock_modulus> is never used or assigned. This unconnected signal will be trimmed during the optimization process. INFO:Xst:1433 - Contents of array <teilerarray> may be accessed with an index that exceeds the array size. This could cause simulation mismatch. INFO:Xst:1767 - HDL ADVISOR - Resource sharing has identified that some arithmetic operations in this design can share the same physical resources for reduced device utilization. For improved clock frequency you may try to disable resource sharing. [vhdl] library ieee; use ieee.std_logic_1164.all; use ieee.numeric_std.all; use ieee.math_real.all; -- Modulus als Zustandsmaschine -- Modulus als "einfache" Subtraktion; nur für positive Zahlen -- Der normale Modulusbefehl kann in VHDL nur genutzt werden wenn der Modulus konstant ist entity modulus is generic ( size_basis : integer := 8; size_modulus : integer := 8 ); port ( ----------------------- Inputs clock_modulus : in std_logic; enable_modulus : in std_logic; basis_modulus : in std_logic_vector (size_basis-1 downto 0); modulo_modulus : in std_logic_vector (size_modulus-1 downto 0); ----------------------- Outputs ready_modulus : out std_logic; valid_modulus : out std_logic; result_modulus : out std_logic_vector (size_modulus-1 downto 0) ); end modulus; architecture modulus_rtl of modulus is -- Die Zustände type states is (init, enable, check, multiply, divide, subtract, output); signal state : states; -- Typen und Signale subtype long1 is natural range 2**size_basis-1 downto 0; subtype long2 is natural range 2**size_modulus-1 downto 0; signal temp_modulo, integer_base : long1; signal integer_modulo : long2; begin process (clock_modulus) begin if rising_edge(clock_modulus) then case state is when init => -- The output is not valid, but the machine is ready valid_modulus <= '0'; ready_modulus <= '1'; state <= enable; when enable => if enable_modulus = '1' then ready_modulus <= '0'; -- Convert from std_logic_vector to integer integer_base <= to_integer(unsigned(basis_modulus)); integer_modulo <= to_integer(unsigned(modulo_modulus)); state <= check; end if; when check => -- Fängt mod(a,0) und mod(a,b) mit b>a ab if (integer_modulo = 0) or (integer_modulo > integer_base) then state <= output; -- Fängt mod(a,1) und mod(a,a) ab elsif (integer_modulo = 1) or (integer_modulo = integer_base) then integer_base <= 0; state <= output; else temp_modulo <= integer_modulo; state <= multiply; end if; when multiply => -- Multipliziere solange Modulus < Basis mit 2 -- 141 mod 7 = 1 -- (2**4)*7 = 112 -- 141 - 112 = 29 if 2*temp_modulo < integer_base then temp_modulo <= 2*temp_modulo; else -- Subtraktion minus (2^n)*Modulo integer_base <= integer_base - temp_modulo; state <= divide; end if; when divide => -- Subtrahiere fortlaufend die nächst kleinere Zweierpotenz -- Subtraktion minus (2^(n-m))*Modulo -- 29 - 56 geht nicht -- 29 - 28 = 1 -- if 112 > 7 if temp_modulo > integer_modulo then temp_modulo <= temp_modulo/2; state <= subtract; else state <= output; end if; when subtract => -- if 29 >= 56 if integer_base >= temp_modulo then integer_base <= integer_base - temp_modulo; end if; state <= divide; when output => -- Output the result result_modulus <= std_logic_vector(to_unsigned(integer_base,size_modulus)); valid_modulus <= '1'; state <= init; end case; end if; end process; end architecture modulus_rtl; ----------------------------------------------------------------------- library ieee; use ieee.std_logic_1164.all; use ieee.numeric_std.all; -- Wie gross ist die n-te Primzahl ? -- x = n*(ln(n)+ln(ln(n))-1) -- Entsprechend obiger Abschätzung ergibt sich: -- Ab hier Datenbreite ist gleich Adressbreite plus 2 Bit -- Adressbreite 3 x(2**3) = 15 Datenbreite 5 Bit = 32-1 -- Adressbreite 4 x(2**4) = 45 Datenbreite 6 Bit = 64-1 -- Adressbreite 5 x(2**5) = 119 Datenbreite 7 Bit = 128-1 -- Ab hier Datenbreite ist gleich Adressbreite plus 3 Bit -- Adressbreite 6 x(2**6) = 293 Datenbreite 9 Bit = 512-1 -- Adressbreite 7 x(2**7) = 695 Datenbreite 10 Bit = 1024-1 -- Adressbreite 8 x(2**8) = 1602 Datenbreite 11 Bit = 2048-1 -- Adressbreite 9 x(2**9) = 3619 Datenbreite 12 Bit = 4096-1 -- Adressbreite 10 x(2**10) = 8056 Datenbreite 13 Bit = 8192-1 entity erasthotenes is generic ( address_width : natural := 4; data_width : natural := 6 ); port ( ------------------------------------ Inputs clock_erasthotenes : in std_logic; enable_erasthotenes : in std_logic; ------------------------------------ Outputs data_out_erasthotenes : out std_logic_vector(data_width - 1 downto 0); ready_erasthotenes : out std_logic; valid_erasthotenes : out std_logic ); end erasthotenes; architecture erasthotenes_rtl of erasthotenes is component modulus is generic ( size_basis : natural := data_width; size_modulus : natural := data_width ); port ( ------------------- Inputs clock_modulus : in std_logic; basis_modulus : in std_logic_vector (size_basis-1 downto 0); modulo_modulus : in std_logic_vector (size_modulus-1 downto 0); enable_modulus : in std_logic; ------------------- Outputs result_modulus : out std_logic_vector (size_modulus-1 downto 0); ready_modulus : out std_logic; valid_modulus : out std_logic ); end component modulus; subtype data_range is natural range 0 to 2**data_width-1; subtype address_range is natural range 0 to 2**address_width-1; subtype data is std_logic_vector (data_width-1 downto 0); subtype address is std_logic_vector (address_width-1 downto 0); -------------------- RAM type RAM is array (address_range) of data; signal teilerarray : RAM; ------------------- Modulus signal enable_modulus, clock_modulus, ready_modulus, valid_modulus : std_logic; signal basis_modulus : data; signal modulo_modulus, result_modulus : data; signal hat_teiler : boolean; signal zahl, teiler : data_range; signal index : address_range; signal anzahl : natural range 1 to 2**address_width; type states is (init_signals, init_parameter, for_loop, while_loop, if_wurzel, result_of_modulus, if_not_hat_teiler, increment_zahl, end_primzahl); signal state : states; begin -- Modulus Funktion Modulo : modulus generic map ( size_basis => data_width, size_modulus => data_width ) port map ( --------------- Inputs clock_modulus => clock_erasthotenes, basis_modulus => basis_modulus, modulo_modulus => modulo_modulus, enable_modulus => enable_modulus, --------------- Outputs result_modulus => result_modulus, ready_modulus => ready_modulus, valid_modulus => valid_modulus ); primzahl : process (clock_erasthotenes) begin if rising_edge(clock_erasthotenes) then case state is when init_signals => -- The output is not valid, but the machine is ready valid_erasthotenes <= '0'; ready_erasthotenes <= '1'; if enable_erasthotenes = '1' then ready_erasthotenes <= '0'; state <= init_parameter; end if; when init_parameter => anzahl <= 1; -- Initialisierung des ersten Teilers -- teilerarray(0)=3; -- Vorsicht: Anzahl hat noch nicht den Wert 1 ! teilerarray(0) <= std_logic_vector(to_unsigned(3,data_width)); zahl <= 5; state <= for_loop; when for_loop => if anzahl <= 2**address_width then -- Noch kein Teiler gefunden -- teiler = false; hat_teiler <= false; index <= 0; state <= while_loop; end if; when while_loop => -- while (index<=anzahl) -- Index beginnt bei Null ! if index < anzahl then -- report "index < anzahl"; -- report "Index = " & natural'image(index); -- report "Anzahl = " & natural'image(anzahl); -- Ermittle den nächsten Teiler -- teiler = teilerarray(index); teiler <= to_integer(unsigned(teilerarray(index))); -- report "teilerarray(index) = " & natural'image(to_integer(unsigned(teilerarray(index)))); state <= if_wurzel; else state <= if_not_hat_teiler; end if; when if_wurzel => -- Prüfung des Wurzelkriteriums (Formel von Heron) -- if teiler < (zahl+1)/2 -- report "Teiler = " & natural'image(teiler); -- report "Zahl = " & natural'image(zahl); if teiler < (zahl+1) / 2 then -- report "teiler < (zahl+1)/2"; if ready_modulus = '1' then -- report "Prüfe auf Teilbarkeit"; -- report "Basis = " & natural'image(zahl); -- report "Modulus = " & natural'image(teiler); -- if mod(zahl,teiler) == 0 basis_modulus <= std_logic_vector (to_unsigned(zahl,data_width)); modulo_modulus <= std_logic_vector(to_unsigned(teiler,data_width)); enable_modulus <= '1'; state <= result_of_modulus; end if; else state <= if_not_hat_teiler; end if; when result_of_modulus => if valid_modulus = '1' then -- Unbedingt zurücksetzen ! enable_modulus <= '0'; -- if mod(zahl, teiler) == 0 if to_integer(unsigned(result_modulus)) = 0 then -- report "Hat Teiler"; hat_teiler <= true; state <= increment_zahl; else -- Inkrementiere den Index -- index=index+1; index <= index + 1; state <= while_loop; end if; end if; when if_not_hat_teiler => -- Kein Teiler gefunden; also Prim -- if (~hat_teiler) if not hat_teiler then -- Speicherung der Primzahl als neuen Teiler -- anzahl = anzahl + 1; if anzahl < 2**address_width then anzahl <= anzahl + 1; -- Bezieht sich noch auf den vorherigen Wert von anzahl -- report "teilerarray(anzahl) = " & natural'image(zahl); teilerarray(anzahl) <= std_logic_vector(to_unsigned(zahl,data_width)); -----------------> Ausgabe data_out_erasthotenes <= std_logic_vector(to_unsigned(zahl,data_width)); state <= increment_zahl; else state <= end_primzahl; end if; end if; when increment_zahl => zahl <= zahl + 2; state <= for_loop; when end_primzahl => Null; end case; end if; -- rising_edge end process; end erasthotenes_rtl; ------------------------------------------------------------------- LIBRARY ieee; USE ieee.std_logic_1164.ALL; USE ieee.std_logic_unsigned.all; USE ieee.numeric_std.ALL; ENTITY Testbench IS END Testbench; ARCHITECTURE behavior OF Testbench IS -- Muss mit den Werten in generic übereinstimmen; etwas unschön -- Gilt für die Port-Anweisung constant address_width_erasthotenes : natural := 4; constant data_width_erasthotenes : natural := 6; COMPONENT erasthotenes generic ( address_width : natural := 4; data_width : natural := 6 ); PORT( clock_erasthotenes : IN std_logic; enable_erasthotenes : IN std_logic; data_out_erasthotenes : OUT std_logic_vector(data_width_erasthotenes-1 downto 0); ready_erasthotenes : OUT std_logic; valid_erasthotenes : OUT std_logic ); END COMPONENT; --Inputs signal clock_erasthotenes : std_logic := '0'; signal enable_erasthotenes : std_logic := '0'; --Outputs signal data_out_erasthotenes : std_logic_vector(data_width_erasthotenes-1 downto 0); signal ready_erasthotenes : std_logic; signal valid_erasthotenes : std_logic; -- Clock period definitions constant clock_erasthotenes_period : time := 5ns; BEGIN -- Instantiate the Unit Under Test (UUT) uut: erasthotenes PORT MAP ( clock_erasthotenes => clock_erasthotenes, enable_erasthotenes => enable_erasthotenes, data_out_erasthotenes => data_out_erasthotenes, ready_erasthotenes => ready_erasthotenes, valid_erasthotenes => valid_erasthotenes ); -- Clock process definitions clock_erasthotenes_process :process begin clock_erasthotenes <= '0'; wait for clock_erasthotenes_period/2; clock_erasthotenes <= '1'; wait for clock_erasthotenes_period/2; end process; -- Stimulus process stim_proc: process begin enable_erasthotenes <= '1'; wait; end process; END architecture;
Bevor man sich den Code anschaut : Das Konzept. Jede neue Zahl muss man ja zurch die bisherigen Primzahlen kleiner als die wurzel zu teilen versuchen. Daher sollten ja die bisherigen Primzahlen im RAM gehalten werden. Ist das so ? Oder aehnlich ?
Ja, das ist so. Eigentlich sollte man ein externes RAM verwenden; aber ist ja auch nur eine Übung. Wer braucht sowas schon in der Praxis ? Miller-Rabin-Test oder ähnliches im FPGA ist wahrscheinlich interessanter. Wurzelberechnung ist nicht (noch nicht ?) implementiert, da etwas aufwändiger. Habe stattdessen eine einfache Abfrage genutzt.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.