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:
de.wikipedia.org/wik...erkorrekturverfahren
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?

Also wenn Du nur Zahlen im Eingabefeld zulassen willst, machst Du das,
in dem Du folgendes in das "onKeyPress"- Ereignins des Edit-Feldes schreibst:



(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

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.

@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.

Ist schon ne Weile her, aber konnte der Hamming-Code bei n-Bit Länge nicht 2^n Bits gegen Einzelbitfehler absichern?

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

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.

Wieso nach den Sternen greifen? Probiers mal mit Modulo-11 z.B. hier oder hier. Wenns bei ISBN funktioniert, dann bestimmt auch bei dir...
Der Vorteil: Nur eine weitere Stelle wird benötigt
Der Nachteil: nur EC und kein ECC und du brauchst neben den Ziffern eventuell noch ein X

Es gibt da noch n paar Verbesserungen davon (alle Einzelfehler und alle Doppelfehler), kannst du dich ja dann selber schlau machen.

MfG

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.