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:

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)


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:

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:
1
library IEEE;
2
use IEEE.STD_LOGIC_1164.ALL;
3
use IEEE.NUMERIC_STD.ALL;
4
5
6
entity nBitDecoder is
7
    Port ( din  : in  std_logic_vector (15 downto 0);
8
           dout : out  std_logic_vector (4 downto 0));
9
end nBitDecoder;
10
11
architecture Behavioral of nBitDecoder is
12
13
   function decode(d : std_logic_vector; cnt : integer)  return integer is
14
   begin
15
     if  cnt<d'length and d(cnt) = '1' then      
16
       return decode(d, cnt+1);  -- in decode() wird decode() aufgerufen
17
     else
18
       return cnt;
19
     end if;
20
   end decode;
21
22
begin
23
24
  dout <= std_logic_vector(to_unsigned(decode(din,0),dout'length));
25
26
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:
1
   stim_proc: process
2
   begin    
3
      din <= (others => '0');
4
      wait for 7 ns;
5
6
      for i in 0 to 15 loop
7
         din <= (i downto 0 => '1', others => '0');
8
         wait for 7 ns;
9
      end loop;
10
      
11
      wait for 100 ns;
12
   end process;

: Bearbeitet durch Moderator
von Christoph Z. (christophz)


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


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)


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)


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)


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:

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:
1
:
2
:
3
architecture tb of testbench is
4
  constant k: natural := 4;
5
  signal a: std_logic_vector(2**k-1 downto 0) := (others=>'0');
6
  signal b: std_logic_vector(k downto 0);
7
8
begin
9
  TEST: entity nbitdecoder 
10
--  generic map (k)
11
  port map (a, b);
12
  
13
  process 
14
  begin
15
  report "Sie simulieren mit " & "k = " & integer'image(k);
16
    
17
    for i in 0 to 2**k loop
18
        wait for 1 ns;
19
        assert i = to_integer(unsigned(b))
20
           report "error at " & integer'image(i) & " = " & integer'image(to_integer(unsigned(b)));
21
        a <= a(a'left-1 downto 0) & '1';   
22
    end loop;
23
    wait;
24
    
25
  end process;
26
end;


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

: Bearbeitet durch Moderator
von Hugo H. (hugohurtig1)


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)


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


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

von Jonas B. (holocron)


Lesenswert?

Hallo,
sorry für die späte Rückmeldung. Alles klar danke, für eure Hilfe!

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]
  • [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.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

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