Ausversehen Bit-Counter optimiert - Kann nicht erklären warum es funktioniert

[Kai (Gast)]

Hallo,
Ich bin auf ein interessantes "Problem" gestoßen.
Eine Uni Aufgabe war es bei einen Input Vektor mit 16 Bits
die Anzahl der gesetzten Bits mit Hilfe einer Baumstruktur
zu berechnen/zählen und eine bestimmte Zeit für den
kritischen Pfad zu unterbieten.

Die Aufgabe war schnell erledigt und ich habe noch weiter versucht
die Zeit vom Wissenschaftlichen Mitarbeiter zu unterbieten, nur so
aus Spaß, da ab einer gewissen Zeit die Geschwindigkeit "egal" ist.

Irgendwann ist mir in VHDL ein Fehler unterlaufen und ich habe,
wie man dem Schaltbild entnehmen kann, nur UND Gatter für
das höchste Bit genutzt um mir so den "Carry Out" zu bestimmen.

Bei der Synthese fiel dies durch eine starke Zunahme der Geschwindigkeit
auf. Aber zu meiner Überraschung gab es bei meiner Testbench keinen
Fehler! Das hat mir sehr überrascht, denn mir ist schon bewusst,
dass ein korrekter Volladdierer nicht nur das höchste Bit betrachtet,
sondern auch den Carry In von der Stufe davor.

Nun habe ich vergeblich versucht ein Gegenbeispiel zu finden und habe 
mir
dann überlegt ob es mit den gegebenen Randbedingungen tatsächlich immer
funktioniert. Von meiner Überlegung her, kann der Fall nich eintreten,
bei dem diese Schaltung einen falschen Ausgang hat, da in keiner
Stufe ein (externes) Carry In hinzukommt und die Halbaddierer der 
einzelnen
Stufen nie ein "gefährliches" Ergebnis berechnen.

Falsch wäre es ja, wenn man bei dem ersten 2-bit Halbaddierer 11 + 01 
rechnet,
da mein UND Gatter ja 0 als Carry Out berechnet, aber der korrekte
Carry Out ja 1 ist.

Nun kann ich aber nicht "beweisen", dass dieser Fall nie eintritt.
Ich würde sehr gerne Eure Meinungen dazu hören und würde mich sehr über
ein Gegenbeispiel oder über eine bessere Erklärung freuen.

Mit freundlichen Grüßen,
Kai

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

Kai schrieb:
> Aber zu meiner Überraschung gab es bei meiner Testbench keinen Fehler!
Evtl. deckt die TB nicht alles ab. Wie sieht denn der Code dazu aus?

> Eine Uni Aufgabe war es bei einen Input Vektor mit 16 Bits
> die Anzahl der gesetzten Bits mit Hilfe einer Baumstruktur
> zu berechnen/zählen und eine bestimmte Zeit für den
> kritischen Pfad zu unterbieten.
Siehe 
http://www.lothar-miller.de/s9y/archives/86-Einsen-im-Vektor-zaehlen.html

[Kai (Gast)]

Das sind die tatsächlich genutzten Testvektoren.

    input_vec(0) := (others => '0');
    output_vec(0) := (others => '0');

    input_vec(1) := x"0001";
    input_vec(2) := x"0010";
    input_vec(3) := x"0100";
    input_vec(4) := x"1000";
    for i in 1 to 4 loop
      output_vec(i) := "00001";
    end loop;

    input_vec(5)   := x"0030";
    input_vec(6)   := x"3000";
    output_vec(5)   := "00010";
    output_vec(6)   := "00010";

    input_vec(7)   := x"0007";
    input_vec(8)   := x"0700";
    output_vec(7)   := "00011";
    output_vec(8)   := "00011";

    input_vec(9)   := x"0008";
    input_vec(10)   := x"0800";
    output_vec(9)   := "00001";
    output_vec(10)   := "00001";

    input_vec(11)   := x"7070";
    input_vec(12)   := x"0707";
    output_vec(11)   := "00110";
    output_vec(12)   := "00110";

    input_vec(13)   := x"7373";
    input_vec(14)   := x"7575";
    output_vec(13)   := "01010";
    output_vec(14)   := "01010";

    input_vec(15)   := x"FFFF";
    output_vec(15)   := "10000";

    input_vec(16)   := x"FF00";
    input_vec(17)   := x"10FF";
    output_vec(16)   := "01000";
    output_vec(17)   := "01001";

Es ist auch ein bisschen aus dem Kontext gerissen. Es ist ein Teil eines
ArmSoftcore Prozessors, der im Laufe des Semester geschrieben wurde und
die Datei wurde dort auch genutzt und hat im laufenden Betrieb keine
Fehler verursacht. (Muss ja nichts heißen,
soll aber nur begründen, warum es
so wenig Testvektoren gab) Meine VHD Datei wurde ja auch abgegeben
und wurde mit der Testbench vom WiMi getestet ohne einen Fehler erzeugt
zu haben, wie diese aussieht, kann ich jedoch nicht sagen.

Ich werde im Laufe der Woche vllt nochmal eine weitaus größere Testbench
schreiben mit randomisierten input vektoren, aber es schien ja auch
auf dem FPGA als Teil eines größeren Projektes erzeugt zu haben.

Vielen Dank für den Link, aber eine "korrekte" Implementierung war
nicht das Problem und hat keine Schwierigkeiten verursacht.

[Klakx (Gast)]

Ich glaube auch, dass die Testbench es nicht alles abdeckt:

Kannst auch mal damit gegenprüfen:

   function count_ones(inp : std_logic_vector) return integer is
   variable temp : natural := 0;
   begin
   for i in inp'range loop
      if inp(i) = '1' then temp := temp + 1; 
      end if;
   end loop;
   return temp;
   end function count_ones;

-- ..

RBA_NR_OF_REGS <= std_logic_vector(to_unsigned((count_ones(RBA_REGLIST),RBA_NR_OF_REGS'length));

[Lötpunkt (Gast)]

Hallo Kai,

das liegt an den möglichen Wertebereichen der Adder-Stufen.
Die Stufe 1 addiert maximal zwei gesetzte Bit. D.h. Ausgang des Adders 
eins und zuätzlich Übertrag kann nicht auftreten.

Das setzt sich dann nach weiter fort...

[Dr. Sommer (Gast)]

Angenommen, du wüsstest, dass beim Eingang maximal 15 bits '1' sein 
können. Dann würden deine kaskadierten Addierer ausreichen, da die ja 
eben maximal bis 15 zählen können. Für den Fall, dass eben doch alle 16 
bits '1' sind, sind noch die (kaskadierten) AND-Gatter hinzugefügt um 
das 16er-Bit im Ausgang zu setzen, in welchem Falle die Addierer 
überlaufen und 0 ausgeben, und die Ausgabe "16" ist. Sollte doch 
stimmen?

[Kai (Gast)]

Also ich kann mir inzwischen nicht mehr vorstellen,
dass es sich bei meiner Implementierung für diesen Fall,
um einen Fehler handelt. Ich habe mit einem Python Skript
(ja das hab ich schneller zusammengeschrieben als eine Funktion
in VHDL und habe es auch nicht sauber eingebunden) 2000
Zufallsvektoren erstellt und diese inklusiver Output Vektoren
und es scheint keine Fehler zu geben.

Im Anhang habe ich die Testbench hochgeladen und an dieser Stelle
sei darauf verwiesen, dass die Vorlage von der TU Berlin
aus dem Modul HWPTI stammt.

[Kai (Gast)]

Entschuldigung Dr. Sommer,
ich verstehe nicht ganz was du mir sagen möchtest.
Angenommen wir spielen es durch bei dem alle Bits gesetzt worden
sind.

Wir haben als Eingaenge bei den Addieren:
Wobei a_b bedeutet, dass a und b die Eingänge eines
Addierers sind.

10_10 10_10 10_10 10_10 |
100_100 100_100 |
1000 1000
mit dem Ausgang (vom Und Gatter und dem letzten Addierer)
letzlich 10000 was genau dem Erwartungswert
entspricht.

Und @Lötpunkt so im Gefühl habe ich das auch,
aber es fehlt mir so bisschen "Beweis".
Angenommen der WiMi würde mich in die Mangel nehmen,
dann könnte ich ihm nicht mit Sicherheit überzeugen,
dass es stimmt. Wenn du es vllt ein wenig ausführen könntest,
dann wäre ich wirklich glücklich darüber.

Mit freundlichen Grüßen,
Kai

[Kai (Gast)]

Hier ist auch nochmal der VHDL Code den ich
benutzt habe, vllt hilft Euch das mehr als das Bild,
um zu verstehen, was ich gemacht habe.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity ArmRegisterBitAdder is
  Port (
    RBA_REGLIST   : in  std_logic_vector(15 downto 0);
    RBA_NR_OF_REGS   : out  std_logic_vector(4 downto 0)
  );
end entity ArmRegisterBitAdder;

architecture structure of ArmRegisterBitAdder is
    type firstStage_Type is array (0 to 7) of unsigned(1 downto 0);
    type secondStage_Type is array (0 to 3) of unsigned(2 downto 0);
    type thirdStage_Type is array (0 to 1) of unsigned(3 downto 0);
begin
    process(RBA_REGLIST)
        variable firstStage: firstStage_Type;
        variable secondStage: secondStage_Type;
        variable thirdStage: thirdStage_Type;
    begin
        for I in 0 to 7 loop
            -- Das hier beschreibt das Verhalten eines Halbaddierers.
            firstStage(I)(0) := RBA_REGLIST(I*2+1) xor RBA_REGLIST(I*2);
            firstStage(I)(1) := RBA_REGLIST(I*2+1) and RBA_REGLIST(I*2);
        end loop;
        for I in 0 to 3 loop
            secondStage(I) := (firstStage(I*2+1)(1) and firstStage(I*2)(1)) & (firstStage(I*2+1) + firstStage(I*2));
        end loop;
        for I in 0 to 1 loop
            thirdStage(I) := (secondStage(I*2+1)(2) and secondStage(I*2)(2)) & (secondStage(I*2+1) + secondStage(I*2));
        end loop;
            RBA_NR_OF_REGS <= std_logic_vector( (thirdStage(1)(3) and thirdStage(0)(3)) & (thirdStage(1) + thirdStage(0)) );
    end process;
end architecture structure;

[Dr. Sommer (Gast)]

Kai schrieb:
> mit dem Ausgang (vom Und Gatter und dem letzten Addierer)
> letzlich 10000 was genau dem Erwartungswert
> entspricht.
Ja, ist doch supi. Und in allen anderen Fällen wird das oberste 
Ausgangsbit nicht gesetzt, und die Addierer arbeiten normal.

Du hast ja 4 Stufen: Die linkeste, bestehend aus AND+XOR, sind 
1-Bit-Halbaddierer mit Carry-Ausgang (könntest du vermutlich auch als 
solchen in VHDL modellieren). Die linkesten Stufen (derer gibt es 8) 
können jeweils maximal 2 ausgeben. Die 2. Stufen können jeweils maximal 
4 ausgeben, die nächste 8, die letzte 16. Der Fall, dass das Maximum 
ausgegeben wird, ist durch die AND-Gatter korrekt abgedeckt (wie du 
schon geschrieben hast). Der Fall, dass etwas anderes ausgegeben wird, 
ist durch die Halbaddierer korrekt abgedeckt (dann wird kein Carry-Bit 
benötigt, es werden jeweils die normalen Ausgangsbits entsprechend 
gesetzt). Nur die Fälle dass mehr als 16 rauskommen sind nicht korrekt 
abgedeckt, aber die können ja nicht auftreten!

[Kai (Gast)]

Solangsam leuchtet es ein...
Die Halbaddierer decken alle Fälle außer dem Maximum ab,
weil es keinen Carry In gibt und man dann nur jeweils das oberste
Bit betrachten muss, um den Carry Out zu bestimmen korrekt?

$$C_{out} = AB \lor (C_{in}(A \oplus B))$$

Und diese Gleichung "halte ich ein", weil ich keinen Carry In betrachte
oder?

Entschuldigung, wenn es ich so doof Frage, aber ich will sicher gehen,
dass ich es auch wirklich verstanden habe. :)

[Matthias Göbel (Gast)]

Guten Tag,

ich bin der wissenschaftliche Mitarbeiter, der die angesprochene 
Lehrveranstaltung betreut, aus dem diese Aufgabe entstammt. Ich habe 
wiederholt per Mail an die im Impressum hinterlegte Adresse darum 
gebeten, dass dieser Thread bzw. die entsprechenden Posts gelöscht 
werden, da hier komplette Lösungen für Hausaufgaben verbreitet wurden.

Leider habe ich keinerlei Antwort darauf erhalten. Daher bitte ich 
hiermit noch einmal eindringlich darum, die vom Gast "Kai" angehängten 
bzw. ausgeschriebenen VHDL-Dateien inklusive der Wahl der Testvektoren 
zu entfernen.

Alternativ hier noch einmal der klare Hinweis an zukünftige Studierende 
des Moduls: Ja, wir sind uns bewusst, dass hier Lösungen zu finden sind 
und werden bei der Abgabe darauf achten, ob die hier zu findenden 
Lösungen (ggf. in leicht modifizierter Form) abgegeben worden sind.

Viele Grüße,
Matthias Göbel

[X. X. (chrissu)]

Mimimimimi...

Wie billig ist das denn?

Alternativ:
Vielleicht einfach mal im nächsten Semester sich einen neue Aufgabe 
ausdenken???

Es gibt unendlich viele... Und fördert die Kreativität...

[Matthias Göbel (Gast)]

Sehr geehrter Herr X.,

wenn Sie möchten, können Sie mich gerne kontaktieren, damit wir über die 
Vorzüge und Nachteile verschiedener Lehrkonzepte diskutieren. Meine 
Kontaktadresse finden Sie über die Seite der TU Berlin.

Mit freundlichen Grüßen,
Matthias Göbel

[J. S. (engineer)]

Mal ungeachtet der Frage, ob hier wirklich der wissenschaftliche 
Mitarbeiter schreibt (was man ja immer in Frage stellen muss) folgender 
Einwurf:

Ich fürchte, dass es wenig bringt, auf Löschungen offiziell in Foren 
geposteter Lösungen zu setzen, weil damit lediglich die Spitze des 
Eisbergs angetastet würde. Vielmehr muss man sich der Tatsache bewusst 
sein, dass die Studis heute ohnehin CDs und USB-Sticks mit Lösungen 
untereinander austauschen, handeln oder ihre Aufgaben in Foren erledigen 
lassen, bzw ...

... erfahrenen, im Beruf stehenden Ingenieuren Geld anbieten, ihnen die 
Hausaufgaben zu machen, die "bachelor-Thesis" nachzusehen und zu 
korrigieren sowie Tipps zu deren Verbesserung zu liefern. (Ja, passiert 
mir regelmäßig und Nein, ich gehe nicht drauf ein).

Im Gegenteil denke Ich, dass man eigentlich froh sein muss, wenn die 
Aufgaben hier offen auftauchen, weil sie dann "verbrannt" sind, also als 
"gelöst" bekannt sind. Damit wird kaum ein Studi auf die Idee kommen, 
sie abzukupfern, weil das auffliegen wird. Mit derselben Begründung 
haben einige meiner Profs die Lösungen alter Klausuren in gedruckter 
Form verbreitet, damit sich jeder was kopieren konnte und alle die 
gleichen Chancen hatte. Umgekehrt gab es im Seminar Aufgaben, die man in 
Echtzeit vorrechnen musste und Erklärungen für Zwischenfragen parat 
haben musste. Ich bin meinen Profs ausdrücklich dankbar dafür, dass sie 
zum Selberdenken angeregt haben.

Fazit: Als Betreuer (der Ich auch mal ein Zeit war) sollte man die 
Aufgaben stets so stellen, dass auswendig Gelerntes und Abgekupfertes 
nicht so viel Gewicht haben. Das ist nicht einfach, ja, bringt aber die 
besten Ergebnisse was die Beruteilung der Studies und deren Förderung 
angeht. Letztlich muss man die Studis davor bewahren, dass sie 
abkupfern, weil sie das nur dazu bringt, zu glauben, sie könnten was, um 
dann den Studiengang fortzusetzen und deutlich später aufzulaufen, statt 
gleich zu merken, dass sie mehr tun müssen oder es lassen sollten.

Auch deshalb gibt es von mir keine Lösungen auf Bestellung.

Wie man sich da als Betreuer aufstellt, ist jedem selber überlassen. Es 
gibt auch die, die meinen "gut recherchiert ist auch gewonnen" und 
überlassen es den Studis, fair zu spielen, denn letztlich betrügt sich 
ja der Betrüger nur selber.