n Bit Decoder rekursiv

[Jonas B. (holocron)]

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

[Jonas B. (holocron)]

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

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

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;

[Christoph Z. (christophz)]

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 :-))

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

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

[Jonas B. (holocron)]

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?

[Hugo H. (hugohurtig1)]

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?

[Duke Scarring (Gast)]

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

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

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

[Hugo H. (hugohurtig1)]

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 :-(

[Anselm (Gast)]

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

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

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

[Jonas B. (holocron)]

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