mikrocontroller.net

Forum: FPGA, VHDL & Co. n Bit Decoder rekursiv


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Jonas B. (holocron)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
für eine Aufgabe sollen wir einen n Bit Encoder rekursiv entwerfen, der 
gemäß folgender beispielhaften Tabelle arbeitet:

2bit Encoder
In | Out
00 |00
01|01
11|10

4bit Encoder:
In|Out
0000|000
0001|001
0011|010
0111|011
1111|100

Ich sitze seit einigen Tagen an der Aufgabe und bin mir sehr unsicher ob 
meine Lösung so passen kann? Ich hab es schon von Hand durch simuliert, 
nur möchte nochmal sicher gehen (insbesondere bevor ich es dann in VHDL 
implementiere).

Danke im Voraus.

Grüße

von Jonas B. (holocron)


Bewertung
0 lesenswert
nicht lesenswert
Nachtrag: ich habe eine Testbench geschrieben, um zu prüfen ob es stimmt 
(es scheint zu passen). Kann man die Testbench so realisieren?
https://www.edaplayground.com/x/4qfP

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Jonas B. schrieb:
> für eine Aufgabe sollen wir einen n Bit Encoder rekursiv entwerfen
"Rekursiv" heißt ja eigentlich, dass in einem Decoder wieder der selbe 
Decoder implementiert ist, in dem wieder der selbe Decoder 
implementiert ist, so lange, bis irgendeine Abbruchbedingung eintritt.
Jetzt ist aber Hardware an sich gar nicht geeignet, unterschiedlich 
"groß" zu sein. Insofern stellt sich mir die Frage:
Wie ist dieses "rekursiv" in der Aufgabenbeschreibung hier zu verstehen?


Evtl. kommt der Lehrende aus der Softwareecke und stellt sich ggfs so 
einen rekursiven Aufruf in dieser Richtung vor:
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;


entity nBitDecoder is
    Port ( din  : in  std_logic_vector (15 downto 0);
           dout : out  std_logic_vector (4 downto 0));
end nBitDecoder;

architecture Behavioral of nBitDecoder is

   function decode(d : std_logic_vector; cnt : integer)  return integer is
   begin
     if  cnt<d'length and d(cnt) = '1' then      
       return decode(d, cnt+1);  -- in decode() wird decode() aufgerufen
     else
       return cnt;
     end if;
   end decode;

begin

  dout <= std_logic_vector(to_unsigned(decode(din,0),dout'length));

end Behavioral;
Der Simulator macht das auch tatsächlich.

Und auch der Synthesizer kann das in eine Schaltung umbauen. In dieser 
Schaltung ist von irgendeiner Rekursion natürlich nichts mehr zu sehen, 
weil in der Hardware ja alles auch für den schlimmsten Fall mit 
maximaler Rekursionstiefe vorbereitet sein muss. Letztlich sind das also 
nur noch große Multiplexer für jedes Bit des Resultats.

Jonas B. schrieb:
> Kann man die Testbench so realisieren?
Sieht hinreichend aufwändig aus. Ich mach das in etwa so:
   stim_proc: process
   begin    
      din <= (others => '0');
      wait for 7 ns;

      for i in 0 to 15 loop
         din <= (i downto 0 => '1', others => '0');
         wait for 7 ns;
      end loop;
      
      wait for 100 ns;
   end process;

: Bearbeitet durch Moderator
von Christoph Z. (christophz)


Bewertung
0 lesenswert
nicht lesenswert
Jonas B. schrieb:
> für eine Aufgabe sollen wir einen n Bit Encoder rekursiv entwerfen, der
> gemäß folgender beispielhaften Tabelle arbeitet:

Das Bit Muster sieht für mich verdächtig nach Gray Code aus (Wohl aus 
didaktischen Gründen nicht erwähnt in der Aufgabenstellung, da man ja 
sonst gleich die Lösung suchen könnte :-))

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Christoph Z. schrieb:
> Das Bit Muster sieht für mich verdächtig nach Gray Code aus
Eigentlich nicht. Da gibt es einfach nur 0en links und 1en rechts. Ein 
durchaus gültiger Graycode wie "10" oder "1100" oder "1001" taucht in 
den Tabellen gar nicht auf.
Also ist das nur ein Prioritätsencoder nach dem Motto "finde das MSB":
http://www.lothar-miller.de/s9y/archives/55-Finde-das-MSB.html

von Jonas B. (holocron)


Bewertung
0 lesenswert
nicht lesenswert
Danke für die Rückmeldungen. Aber wäre meine Umsetzung oder Testbench so 
überhaupt richtig? Ob umständlich mal abgesehen.

Rekursive Schaltkreise hatten wir in der Technischen Informatik 
Vorlesung immer auf die Art definiert, also analog zur Rekursion bei 
Funktionen. Allerdings wurde diese und die vorige tatsächlich von 
Informatikern gehalten. Ist diese rekursive Schaltkreisrealisierung 
nicht üblich?

von Hugo H. (hugohurtig1)


Bewertung
0 lesenswert
nicht lesenswert
Lothar M. schrieb:
> Also ist das nur ein Prioritätsencoder nach dem Motto "finde das MSB":

Jonas B. schrieb:
> 4bit Encoder:
> In|Out
> 0000|000
> 0001|001
> 0011|010
> 0111| *011*
> 1111|100

Das kann  nicht ganz passen - oder?

von Duke Scarring (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Jonas B. schrieb:
> Ist diese rekursive Schaltkreisrealisierung
> nicht üblich?
Nein.

> Allerdings wurde diese und die vorige tatsächlich von
> Informatikern gehalten.
Da mögen von der Theorie her brilliante Lösungen entstehen, aber laß die 
Leute bloß nicht an Webseiten, GUIs oder programmierbare Logik...

Duke

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Jonas B. schrieb:
> Ist diese rekursive Schaltkreisrealisierung nicht üblich?
Nein. Weil es eben keine "rekursive Hardware" mit variablem Abbruch 
gibt.
Der Synthesizer muss immer die komplette Hardware ausrollen, deshalb ist 
es irreführend, wenn einem da irgendeine Rekursion vorgegaukelt wird.

> Aber wäre meine Umsetzung oder Testbench so überhaupt richtig?
Sie funktioniert, sie geht wegen der Verwendung des Integers für die 
"Hilfsrechnungen" (da sieht man den Software-Programmierer, der lieber 
das nimmt, was er schon kennt...;-) eben nur bis 31 Bit Vektorbreite.

Ansonsten kann man das leicht selber ausprobieren. Ich empfehle dazu 
aber schon auch, die Waveform (also die grafische Ausgabe) anzusehen.

Ich habe mal deine Testbench gegen meinen Code laufen lassen. Der geht 
fehlerfrei durch. Wenn ich bewusst einen Fehler einbaue, dann werden 
auch die Asserts geworfen.

> Ob umständlich mal abgesehen.
Wenn man nicht sieht, was die Testbench da überhaupt macht, tut man sich 
auch schwer, abzuschätzen, ob es das Richtige ist....

Ich habe hier noch eine Variante mit einem Schieberegister, bei dem mit 
jedem Zyklus eine '1' von rechts nachgeschoben wird:
:
:
architecture tb of testbench is
  constant k: natural := 4;
  signal a: std_logic_vector(2**k-1 downto 0) := (others=>'0');
  signal b: std_logic_vector(k downto 0);

begin
  TEST: entity nbitdecoder 
--  generic map (k)
  port map (a, b);
  
  process 
  begin
  report "Sie simulieren mit " & "k = " & integer'image(k);
    
    for i in 0 to 2**k loop
        wait for 1 ns;
        assert i = to_integer(unsigned(b))
           report "error at " & integer'image(i) & " = " & integer'image(to_integer(unsigned(b)));
        a <= a(a'left-1 downto 0) & '1';   
    end loop;
    wait;
    
  end process;
end;


Hugo H. schrieb:
> Das kann  nicht ganz passen - oder?
Wo nicht?
im Vektor    ist die führende 1 an Bitposition
0000      |        000    0 wie "nirgends"
0001      |        001    1
0011      |        010    2
0111      |        011    3
1111      |        100    4

: Bearbeitet durch Moderator
von Hugo H. (hugohurtig1)


Bewertung
0 lesenswert
nicht lesenswert
Lothar M. schrieb:
> Wo nicht?im Vektor    ist die führende 1 an Bitposition
> 0000      |        000    0 wie "nirgends"
> 0001      |        001    1
> 0011      |        010    2
> 0111      |        011    3
> 1111      |        100    4

Falsch gedacht :-(

von Anselm (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ich hätte anhand der Tabelle gesagt: "Wieviel 1 sind im Eingang 
vorhanden"
Mit der Tabelle passt es, da eben keine Konstellation mit einer 0 rechts 
der 1 vorhanden ist

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Allerdings kann man für diese Aufgabe eigentlich kein sinnvolles 
rekursives "Programm" schreiben, weil man sowieso immer alle Bitstellen 
durchlaufen muss, denn das einzige Abbruchkriterium für die Rekursion (= 
Bitanzahl) steht ja von vorn herein fest.


> "Wieviel 1 sind im Eingang vorhanden"
Siehe dazu die Betrachtungen:
http://www.lothar-miller.de/s9y/archives/86-Einsen-im-Vektor-zaehlen.html

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.