Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Prüfziffer für Benutzereingaben
motion - So 16.07.06 00:13
Titel: Prüfziffer für Benutzereingaben
Hallo,
in unserer Applikation müssen die Anwender Rechnungs-Nummern (nur Ziffern, max. 8stellig, Integer) und Lagerorte (nur Ziffern, max. 9stellig, Integer) eingeben.
Hierfür benötige ich jetzt einen Algorithmus, welcher die Erkennung (und wenn möglich auch die Behebung von Einzelfehlern/Vertauschungen) möglich macht.
Dazu kann ich eine Stelle anhängen, welche aus den Ziffern 0-9 und den Buchstaben a-z bestehen kann.
Beispiel:
Rechnungs-Nr. 12345678 --> Ausgaben auf Rechnung bzw. Benutzereingabe 12345678P
Algorithmisch betrachtet muss ich also ein Integer (32 Bit) mit einer Prüfziffer von 5 Bits absichern (0-9 und a-Z entsprechenen 36 Zeichen, bei nutzung von 32 Zeichen sind das 5 Bits).
Reicht das für gestellte Aufgabe?
Welchen Algorithmus kann man verwenden?
Parallel dazu arbeite ich mich gerade durch diese Artikel:
http://de.wikipedia.org/wiki/Fehlerkorrekturverfahren
http://de.wikipedia.org/wiki/Hamming-Distanz
Trotzdem komme ich damit nicht ganz klar.
Reichen die 5 Bits, um eine 31Bit Zahl (nur die positiven Integerwerte) gegen
1. vertauschte,benachbarte Ziffern erkennen/korrigieren
2. eine falsche Ziffer erkennen/korrigieren
3. mehrfache Fehler erkennen/nicht korrigieren
Und welchen Algorithmus kann man verwenden?
Saarpoint - So 16.07.06 07:15
Also wenn Du nur Zahlen im Eingabefeld zulassen willst, machst Du das,
in dem Du folgendes in das "onKeyPress"- Ereignins des Edit-Feldes schreibst:
Delphi-Quelltext
1:
2:
3:
4:
5:
| procedure TForm4.NewPointsKeyPress(Sender: TObject; var Key: Char);
begin
if not (Key in [#8,#48..#57]) then Key := #0;
end; |
(NewPoints ist aus meinem eigenen Prog. Musst Du halt durch den Namen deines Editfeldes ersetzen)
#8 ist der Ascii-Code der Löschen-Taste.
Die länge der auf 8 Zeichen begrenzen, kann man ja im Objekt-Inspector.
Den Buchstaben kann man ja anscließend per Programm dranhängen.
Gruß, Andreas
LLCoolDave - So 16.07.06 09:23
Saarpoint: Es geht nicht darum, die Benutzereingabe zu filtern. Es geht darum, auch eine falsche Eingabe (z.B. Ziffern vertauscht oder eine Ziffer falsch) der richtigen Rechnung zuzuordnen.
Ansonsten kann ich dir auch nicht weiterhelfen. Vor kurzem gab es mal eine Diskussion über eine Ähnlichkeitssuche bei einem MP3 Player, von den damals beteiligten kann dir sicher jemand weiterhelfen.
motion - So 16.07.06 13:03
@LLCoolDave,
korrekt erkannt! Ich brauche eine Prüfziffer, um Fehleingaben (falsche/vertauschte Ziffern) zu erkennen und ggf. zu korrigieren.
Ich habe jetzt schon etliche Artikel darüber gelesen (Wikipedia und was google so alles ausspuckt); ist alles ziemlich mathematisch und so weit von einer konkreten programmtechnischen Realisierung entfernt, das ich da nicht weiter komme.
Eventuell kann ich einen CRC-5 Algorithmus verwenden, da ich 5 Bits für die Prüfsumme zur Verfügung habe. Aber hier bin ich noch nicht richtig weiter.
Spaceguide - Mo 17.07.06 22:50
Ist schon ne Weile her, aber konnte der Hamming-Code bei n-Bit Länge nicht 2^n Bits gegen Einzelbitfehler absichern?
Narses - Mo 17.07.06 22:58
Moin!
Puah, die Vorlesung ist schon ein ganzes Weilchen her, aber das ist zumindest noch hängen geblieben:
Für ECC (Error Correction Code) brauchst du nochmal deutlich mehr Redundanzraum als für EDC (Error Detection Code). Konkret also: mit 5 Bit wirst du kein ECC hinkriegen... :|
Bei CD-ROMs wird doch auch sowas gemacht:
CIRC CROSS-INTERLEAVED REED-SOLOMON CODE
Vielleicht kommst du ja damit als Rechercheansatz weiter. ;)
cu
Narses
motion - Di 18.07.06 12:42
Ja, auch bei mir ist die Vorlesung zum Thema Hamming-Distanz etc. etwas her.
Aber: ich will ja keinen neuen Code verwenden (dazu müßte dieser ja unter Berücksichtigung der Hammingdistanz aufgebaut werden), sondern wirklich eine Prüfziffer! Das ist ein Unterschied. Block-Orientierte Codes wie z.B. Reed-Solomon (von der CD bekannt) haben andere Stärken: Durch die Verschacheltung von Datenblöcken kann es dort zu breiten, lokalen Störungen kommen, die man erkennen und korrigieren kann. Nachteil: Nur für große Datenmengen brauchbar.
Mein aktueller Ansatz ist das ECC Verfahren von Speicherbausteinen nachzuvollziehen.
Dort werden die 32Bit mit 4 (?) Prüfbits abgesichert. Die eigentlich 32Bit Daten werden hierbei nicht modifiziert (das würde ein Hamming Code ja machen; Beispiele sind Manchester und Trallis Codierungen bei den Ethernet varianten (obwohl die Codierung dort nicht zu Fehlererkennung, sondern zum Ausgleich (=Nullung) des Gleichspannungsanteiles dienen)).
Mal schauen, was man damit hinbekommt. Eine Fehlererkennung ist ja schon nicht schlecht, eine Fehlerkorrektur wäre besser. Wahrscheinlich wird das eine CRC Prüfsumme sein. ein CRC5 liesse sich schon realisieren. Bloß, wie bestimmt man die Exponenten der Polynome? Da muss ich noch etwas Literaturstudium betreiben. Wir haben das früher mal auf der FH gemacht, aber das ist schon >10 Jahre her :-(
Vielleicht kann man eine 1 Bit Fehlerkorrektur noch realisieren, aber das ist kein Fehler, der in der Praxis vorkommt. Wenn bei der Eingabe einer Ziffernfolge eine Ziffer falsch getippt wird, sind meist mehr als nur 1 Bit verkehrt. Bei vertauschten Ziffern wird's noch schlimmer.
Also wahrscheinlich wird eine Fehlerkorrektur mit 5 Bits nicht möglich sein. Vielleicht kann ich aber auch eine verdoppelung auf 2 Prüfziffern erreichen. Mit 10 Bit sieht das schon viel besser aus.
motion - Fr 21.07.06 18:15
Ja, das klingt auch nicht schlecht.
Die ISBN Kodierung hatte ich schon mal überflogen aber wegen der fehlenden ECC erst mal verworfen. Da ich das aber mangels verfügbarer Prüfziffern eh vergessen kann, wäre die Modulo-11 Prüfung schon mal nicht schlecht.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!