Frage zur Programmierung eines Prüfbitgenerator

[frank123]

Guten Tag,
Ich habe die Aufgabe erhalten einen Prüfbitgenerator zu erstellen. (MIr ist klar das man mir in diesem Forum nicht meine Hausaufgaben löst. Ich brauche aber doch etwas Hilfe und erhoffe mir, dass ich diese hier bekomme.)
Kurz zu mir selbst: Ich bin in der 12. Klasse und besuche nur den Grundurs in Informatik. Ich habe die Aufgabe erhalten einen Prüfbitgenerator zu erstellen.
Die Aufgabe lautet genau: Beschreiben sie einen endlichen Automaten, der nacheinander 7 Bits liest, sie wieder ausgibt und als das 8. Bit das Prüfbit anhängt.

Was ich nun bereits für mich in erfahren gebracht habe:
Das 8. Prüfbit wird angehangen um gerade anzahl zu erzeugen. Also muss ich herrausfinden lassen, wie die gesamte Anzahl der 1 und 0 dieser Daten ist. Sollte es eine ungerade Anzahl von 1 sein so muss das 8. Prüfbit ja auch eine 1 sein um eine ungerade Zahl ist.

Ebenfalls habe ich mir bereits einen möglichen "Aufbau" des Programmes überlegt.
Zuerst müsste eine Eingabe der gewünschten Daten bzw. des gewünschten Symbols erfolgen.
Danach müsste doch dieses Symbol für das Programm in Bitform umgewandelt werden um danach zu ermitteln ob es eine ungerade Zahl oder eine gerade Anzahl ist um dadurch herrauszufinden ob ich eine 1 oder eine 0 anhängen muss.

Ich hoffe es findet sich jemand der mir helfen kann.
Mit freundlichen Grüßen
Frank123

[__deets__]

Was hast du denn bisher gemacht? Wir sind hier was Hilfe fuer Hausaufgaben angeht der Meinung, dass Hilfe zur Selbsthilfe selbstverstaendlich gewaehrt wird - aber fertigen Programmtext liefern wir nicht.

Und zu deinen Ueberlegungen: ich sehe in der Aufgabenstellung noch gar keine Progarmmierung. Sondern zuerstmal einen endlichen Automaten, den du zugrunde legen sollst. Die Theorie der endlichen Automaten kennst du? Woraus bestehen die?

Wie sich das dann auf dein Programm auswirkt, koennen wir spaeter besprechen.

[__blackjack__]

@__deets__: Programmierung sehe ich beim erzeugen des Ergebnisses, denn die vielen Zustände per Hand schreiben/zeichnen ist vielleicht etwas mühselig.

[__deets__]

Welche vielen Zustaende denn? Ich zaehle erstmal drei (war mal zwei... - ich vermisse durstreichen mehr als spoilern!). So oder so ist die Frage der Programmierung doch davon losgeloest: wenn die Aufgabenstellung "beschreibe" heisst, dann soll man den beschreiben. Nicht programmieren. So wuerde ich das zumindest erstmal interpretieren. Einen Zustandsautomaten zu programieren ist ja nun auch deutlich schwieriger. Wenn ich den generisch einfuehre, und danach "nur" benutze, ist das deutlich schwieriger, als eine eher implizite Implementierung. Trotzdem ist es hilfreich, sich die Natur des Problems mit dem FA vorher klar zu machen.

[__blackjack__]

Wie zählst Du mit drei Zuständen bis 7? Auf drei, bzw vier Zustände komme ich nur wenn im Eingabealphabet nicht nur '0' und '1' vorkommt, und wenn derjenige der den Automaten füttert selbst bis 7 zählt und dann explizit die Ausgabe des 8. Bitwertes auslösen muss. Das lässt die Aufgabenbeschreibung IMHO nicht zu.

Ich würde nicht den Zustandsautomaten programmieren sondern ein Programm schreiben was mir den Zustandsautomaten erstellt. Also entweder als textuelle Beschreibung oder als Graph. Wobei das auch auf Text hinauslaufen würde → Quelltext für Graphviz.

[__deets__]

Ich habe einen Startzustand, und zwei Zustaende welche die Paritaet darstellen. Ich fuettere 7 Bits da rein, und das achte lese ich dann aus. Es gibt ja nunmal kein allgemein definiertes Modell wie sich Zustaende wiederum zu Ausgaben verhalten. Ich bezweifele auch stark, dass das gefragt ist. Den faktisch erfasst man eine Eingabe, zerteilt sie, fuettert sei einzeln ein, aber das bitte nur bis 7, danach muss es von alleine gehen? Hmjane.

Und wenn man das irgendwie so definieren will, dann sind es halt 15. Komme ich auch noch wunderbar mit einem A5-Blatt hin. Muss aber auch dort ein kuenstliches reset-Signal einfuehren. Da kann ich auch einfach meinen viel einfacheren 3-Zustand-Automaten bedienen. Und ich denke auch ehrlich gesagt, das ist einer Implementierung naeher. Halt mit XOR fuer das Pruefbit.

Edit: ich muss mich korrigieren. Wenn ich die Zustaende gleichzeitig zur Ausgabe benutzen will, geht das nicht. Dann werden es wohl 127. Womit ich das auch fuer einen verfehlten Ansatz halte. Die 15 wuerden klappen, wenn ich die Uebergaenge zur Ausgabe nutze. Aber dann brauche ich immer noch mindestens einen Epsilon-Uebergang am Ende.

[__blackjack__]

Ich bin halt von der Aufgabenstellung ausgegangen die sagt das der Automat 7 Bits liest, die wieder ausgibt und das Prüfbit ausgibt. Also von sich aus, nach dem lesen des 7. Bits.

[__deets__]

Ein solchen Automaten zu bauen wuerde mir persoenlich deutlich schwerer fallen, als ich mir das fuer einen solchen Grundkurs vorstellen kann. Oder ich uebersehe gerade etwas, und man kann die 127 Zustaende die man sonst braucht irgendwie geschickt zusammen falten. Aber auch das ist dann schon wieder deutlich fortgeschritten.

Nunja. Letzlich muss der TE sich dazu aeussern.

[__blackjack__]

@__deets__: Naja, deswegen eben Programmierung, weil damit 127 Zustände nicht so kompliziert zu erstellen sind.

[__deets__]

Joa, aber ditt is ja noch mehr la-meta

[__blackjack__]

@__deets__: Ich denke ich bekomme es mit 29 Zuständen hin. Startzustand, vier Zustände pro Bit, ausser beim ersten, da reichen zwei, und dann noch mal zwei für die Ausgabe des 8. Bits. Wenn man es erst einmal sieht, ist es auch sehr regelmässig und auch einleuchtend. Also ich hätte auch durch Nachdenken drauf kommen können.

[frank123]

Vielen Dank für die Diskussion zu meinem Beitrag,
nur viel schlauer bin ich daraus nicht geworden

Darum eine kleine Erweiterung...
Mein aktuelles Programm sieht wiefolgt aus:
# Prüfbitbitgenerator

print("!! Nur Eingaben von je einer 0 oder 1 sind möglich !!")

b1=int(input("1. Bit: "))
b2=int(input("2. Bit: "))
b3=int(input("3. Bit: "))
b4=int(input("4. Bit: "))
b5=int(input("5. Bit: "))
b6=int(input("6. Bit: "))
b7=int(input("7. Bit: "))

b8=0

bx= b1, b2, b3, b4, b5, b6, b7

print("Ihre eingegebene 7-stellige Dualzahl lautet: ", bx)

bz=b1+b2+b3+b4+b5+b6+b7

if bz == 1:
b8=1

elif bz == 3:
b8=1

elif bz == 5:
b8=1

elif bz == 7:
b8=1

elif bz == 9:
b8=1

elif bz == 0:
b8=0
elif bz == 2:
b8=0

elif bz == 4:
b8=0

elif bz == 6:
b8=0

elif bz == 8:
b8=0

bneu= b1+b2+b3+b4+b5+b6+b7+b8

print()
print("Das Prüfbit ist eine: ", b8)
print()
print("Die 8-stellige Dualzahldarstellung lautet: ", b1, b2, b3, b4, b5, b6, b7, b8)

Für meine Kenntnisse habe ich nun ein Programm erstellt was die Bits einliest und das nötige 8. Prüfbit ausgibt. Nur leider bin ich nicht wirklich der Meinung, dass es sich hiebei um einen endlichen Automaten handelt. Außerdem ist es vom Niveau her sehr einfach gehalten.

Der vollständige Wortlaut meiner Aufgabe lautet:
"Beschreiben Sie einen endluche Automaten, der nacheinander 7 Bits liest, sie wieder ausgibt und als das 8. Prüfbit anhängt."


Entschulden Sie mich bitte nochmal, dass ich solange nicht geantwortet hatte.
mit freundlichen Grüßen Frank123

[frank123]

Was hast du denn bisher gemacht? Wir sind hier was Hilfe fuer Hausaufgaben angeht der Meinung, dass Hilfe zur Selbsthilfe selbstverstaendlich gewaehrt wird - aber fertigen Programmtext liefern wir nicht.

Und zu deinen Ueberlegungen: ich sehe in der Aufgabenstellung noch gar keine Progarmmierung. Sondern zuerstmal einen endlichen Automaten, den du zugrunde legen sollst. Die Theorie der endlichen Automaten kennst du? Woraus bestehen die?

Wie sich das dann auf dein Programm auswirkt, koennen wir spaeter besprechen.

Vielen Dank für Ihre Antwort.
in dem hiervor geschriebenen Kommentar habe ich meinen aktuellen Stand mitgeteilt. Ich hoffe Sie können etwas damit anfangen und mir gegebenenfalls helfen.

[__deets__]

Was hast du denn schon über endliche Automaten gelernt? Woraus bestehen die?

[__blackjack__]

@frank123: Es wurde ja bereits von __deets__ gesagt: Du sollst einen endlichen Automaten beschreiben. Das ist *kein* Python-Programm oder ein Programm in einer anderen Programmiersprache, sondern eine mathematisch formale Beschreibung eines endlichen Automaten der aus verschiedenen Bestandteilen wie dem Eingabealphabet, dem Ausgabealphabet, einer Zustandsübergangfunktion, und so weiter besteht. Auch letzteres ist keine Funktionsdefinition in einer Programmiersprache, sondern wird als Tabelle angegeben welcher Eingangszustand mit welcher Eingabe zu welchem Ausgangszustand mit welcher Ausgabe führt. Oder man gibt die Funktion als Graph an, mit den Zuständen als Knoten und den Eingaben als Übergängen. Schau Dir mal den Wikipedia-Artikel Endlicher Automat an.

[__blackjack__]

@frank123: Auch wenn kein Python-Programm gefragt ist, trotzdem mal ein paar Anmerkungen zu dem Quelltext von Dir.

Der fängt mit der Ausgabe einer Lüge an. Es ist sehr wohl möglich etwas anderes als 0 und 1 einzugeben. Wenn der Benutzer keine Zahlen eingibt, bricht das Programm mit einem `ValueError` ab. Wenn er Zahlen eingibt, kann er für jedes Bit eine beliebige ganze Zahl eingeben, auch negative.

Ein- oder zweibuchstabige Variablennamen sind in der Regel keine guten Namen. Namen sollen dem Leser vermitteln was der Wert hinter dem Namen bedeutet. Wenn man `bit` meint, sollte man auch `bit` schreiben, und nicht nur `b`. Das `bx` ein Tupel mit Bitwerten oder `bz` eine Summe von Bits ist, lässt sich aus dem Namen (in Python) nicht erkennen.

Wenn man anfängt Namen durchzunummerieren, dann will man in der Regel bessere Namen wählen, oder gar keine einzelnen Werte sondern eine Datenstruktur. Meistens eine Liste. So auch hier. Statt jedes Bit an einen eigenen Namen zu binden, würde man die in eine Liste stecken. Die Abfrage kann dann in einer Schleife erfolgen, womit man weniger Code hat. Auch das aufaddieren wird dann mit der `sum()`-Funktion einfacher. `bx` fällt dann weg, beziehungsweise wird durch die Liste ersetzt.

`b8` wird am Anfang unnötigerweise mit 0 belegt, diese 0 wird aber (bei korrekter Benutzereingabe) nie verwendet.

Bei dem langen ``if``/``elif``-Konstrukt gibt es im Grunde nur zwei mögliche Ausgänge: Das Prüfbit wird auf 0 oder auf 1 gesetzt. Dazu kann man die ganzen Bedingungen für den jeweiligen Fall auch kombinieren.

Da würde dann diese vier Zeilen bei übrig bleiben:

Code: Alles auswählen

    if bit_sum == 1 or bit_sum == 3 or bit_sum == 5 or bit_sum == 7:
        check_bit = 1
    elif bit_sum == 0 or bit_sum == 2 or bit_sum == 4 or bit_sum == 6:
        check_bit = 0

Da immer `bit_sum` gegen verschiedene Werte auf Gleichheit geprüft wird, kann man sich mit dem ``in``-Operator und einer Liste der Werte die vielen Wiederholungen vom Namen `bit_sum` sparen:

Code: Alles auswählen

    if bit_sum in [1, 3, 5, 7]:
        check_bit = 1
    elif bit_sum in [0, 2, 4, 6]:
        check_bit = 0

Letztlich braucht man aber auch gar keine Tests, weil man den Wert von `check_bit` aus dem Wert von `bit_sum` einfach berechnen kann. Entweder der Rest beim Teilen durch zwei (Modulo-Operator) oder in dem man das niederwertigste Bit mit einer bitweisen Und-Verknüpfung ausmaskiert:

Code: Alles auswählen

    check_bit = sum(bits) & 1

`bneu` wird definiert, aber nirgends verwendet.

Zuguterletzt würde ich noch feste Zahlen aus dem Code verbannen. Also die Anzahl der Eingabebits als Variable oder Konstante definieren und die Längenangabe bei der Ausgabe der Dualzahlen nicht fest in die Zeichenkette(n) schreiben, sondern anhand der Länge der `bits`-Liste ermitteln.

Zwischenstand:

Code: Alles auswählen

#/usr/bin/env python3
"""Prüfbitbitgenerator"""


def main():
    input_bit_count = 7
    # 
    # TODO Actually enforce this restriction!
    #     
    print('!! Nur Eingaben von je einer 0 oder 1 sind möglich !!')
    bits = list()
    for i in range(1, input_bit_count + 1):
        bits.append(int(input(f'{i}. Bit: ')))
    assert len(bits) == input_bit_count and set(bits) == {0, 1}
    
    print(f'Ihre eingegebene {len(bits)}-stellige Dualzahl lautet: {bits}')

    check_bit = sum(bits) & 1
    bits.append(check_bit)
    
    print()
    print('Das Prüfbit ist eine: ', check_bit)
    print()
    print(f'Die {len(bits)}-stellige Dualzahldarstellung lautet: {bits}')


if __name__ == '__main__':
    main()

[Sirius3]

@__blackjack__: bei Dir wäre die Eingabe von nur 0en oder nur 1en ein Fehler.

Code: Alles auswählen

def input_bits(input_bit_count):
    while True:
        bits = input(f'Bitte eine {input_bit_count}-stellige Dualzahl eingeben:').strip()
        if len(bits) == input_bit_count and set(bits).issubset('01'):
            return bits
        print("Fehleingabe")

def main():
    input_bit_count = 7
    bits = input_bits(input_bit_count)
    print(f'Ihre eingegebene {input_bit_count}-stellige Dualzahl lautet: {bits}')
    check_bit = bits.count('1') & 1
    print()
    print('Das Prüfbit ist eine: ', check_bit)
    print()
    print(f'Die {input_bit_count+1}-stellige Dualzahl lautet: {bits}{check_bit}')

if __name__ == '__main__':
    main()

[__blackjack__]

Stimmt.

[__blackjack__]

Das wäre die Variante die ich aus der Aufgabenstellung heraus lese:

Die Knotenbeschriftung ist die jeweilige Ausgabe die beim Übergang/Eintritt gemacht wird.

[__deets__]

Ich nicht ich denke nicht, das ein Epsilonübergang wirklich gefragt ist. Simple 3 Zustände Start, Odd, Even - das wird denke ich gereicht haben.