Forum: FPGA, VHDL & Co. Primzahlsieb als Übung; Kommentare ?


von Hans-werner M. (hanswerner)


Lesenswert?

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;

von Slash-N (Gast)


Lesenswert?

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 ?

von Hans-werner M. (hanswerner)


Lesenswert?

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
Noch kein Account? Hier anmelden.