n Bit Decoder rekursiv

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

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;

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

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

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?

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?

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

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

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

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