Ich suche ein Fehlererkennungsverfahren, das bei einer variablen
Zeilenlänge erkennt, ob eine Zeile von maximal n Zeilen fehlerhaft ist
und welche das ist, und deren Prüfstring möglichst kurz ist. Also z.B.
nicht länger als 10 Hex-Zeichen lang ist.
Was würde sich dafür anbieten?
Und was wäre hier die beste Vorgehensweise?
Die maximale Anzahl an Zeilen n ist endlich, ich dachte daran, 10 Zeilen
zusammenzufassen und aus diesen 10 Zeilen einen Prüfstring zu bilden.
Sollten weitere Zeilen dazukommen, bekommen die Blockweise ihren eigenen
Prüfstring. Die Blöcke sollen nicht verkettet werden und sind somit
unabhängig voneinander.
Da die einzelnen Zeilen eine variable Länge haben und nur erkannt werden
muss, ob eine Zeile fehlerhaft ist, aber nicht an welcher Stelle in der
Zeile der Fehler vorkommt, dachte ich aus jeder Zeile einen kurzen Hash
zu bilden.
Für eine Zeile ist also nur wichtig zu erkennen, da ist ein Fehler oder
da ist keiner. Eine Fehlerkorrektur ist nicht erforderlich.
Allerdings sollten einfache Kollisionen vermieden werden, deswegen der
Hash und nicht einfach nur ein Prüfbit, das bspw. alle Zeichen
zusammenzählt und dann sagt, ob das Ergebnis gerade oder ungerade ist,
da wäre die Gefahr von versehentlichen Kollisionen zu groß.
Danach hat man 10 Hashs, für jede Zeile einen.
Alle Hashs aneinandergereiht ergeben aber immer noch einen zu langen
String.
Also müssen alle Hashs noch einmal miteinander verwurstelt werden um
daraus einen kurzen Prüfstring zu generieren. Aus diesem soll man aber
jetzt erkennen können, welcher Hash bzw. welche Zeile fehlerhaft war.
Wie würdet ihr das lösen und welche Verfahren wären hier empfehlenswert?
Am Ende soll das bspw. so aussehen, man hat 10 Zeilen Text:
1
Hans geht einkaufen. // 1. Zeile
2
Berta sucht ihren Schlüssel.
3
Anton fährt Auto.
4
...
5
Der Kühlschrank ist defekt.
6
Das Nachbarshaus brennt. // 10. Zeile
Prüfstring: AF37D287B1
Der Empfänger kriegt jetzt den Text inkl. Prüfstring in Papierform und
tippt den Text ohne Prüfstring auf seinem Computer runter. In der 3. und
5. Zeile tippt er falsch ab und merkt dies erst einmal nicht.
Zum Schluss übergibt er seinem Prüfprogramm den abgetippten Text als
Textdatei und zusätzlich noch den Prüfstring AF37D287B1.
Das Programm berechnet dann mithilfe der Textdatei den Hash jeder
eingetippten Zeile intern erneut und verwurstelt das ganze wie oben zu
einem neuen Prüfstring.
Beim Vergleichen des neu berechneten Prüfstrings und des eingegebenen
Prüfstrings erkennt es dann, dass die Zeilen 3 und 5 einen oder mehrere
Fehler haben müssen, also fehlerhaft sind und zeigt das dem Empfänger
an.
Nano schrieb:> Ich suche ein Fehlererkennungsverfahren, das bei einer variablen> Zeilenlänge erkennt, ob eine Zeile von maximal n Zeilen fehlerhaft ist> und welche das ist, und deren Prüfstring möglichst kurz ist. Also z.B.> nicht länger als 10 Hex-Zeichen lang ist.
CRC-4 über jede Zeile, dann hast Du bei 10 Zeilen 10 Hex-Digits.
Wofür soll das in der Praxis genutzt werden?
Nano schrieb:> Also z.B.> nicht länger als 10 Hex-Zeichen lang ist.> ...> ich dachte daran, 10 Zeilen> zusammenzufassen und aus diesen 10 Zeilen einen Prüfstring zu bilden.> ...> Danach hat man 10 Hashs, für jede Zeile einen.
Das heißt du willst eigentlich jede Zeile einzeln überprüfen und nicht
ob in einem 10 Zeilen langen Block irgendwo was nicht stimmt?
Macht also ein Hex = 4 Bit pro Zeile. Das wäre dann sowas wie CRC4
Je nachdem was wichtiger ist, die genaue Zeile oder ob überhaupt ein
Fehler vorhanden ist. Würde ich eher 16 Zeilen nehmen und für jede Zeile
nur ein Parity-Bit verwenden und über alle 16-Zeilen ein CRC32 bilden.
Bei mehreren Fehlern muss dann nicht unbedingt die ermittelte Zeile
stimmen, aber die Erkennung ob überhaupt ein Fehler vorhanden ist sollte
so schon recht gut sein.
Hmmm schrieb:> CRC-4 über jede Zeile, dann hast Du bei 10 Zeilen 10 Hex-Digits.>> Wofür soll das in der Praxis genutzt werden?
Code Listings zum Abtippen wie früher und leichteren finden von
Tippfehlern mit dem Ziel, das sich der Abtipper auch Gedanken macht ohne
lange suchen zu müssen.
Irgend W. schrieb:> Nano schrieb:>> Also z.B.>> nicht länger als 10 Hex-Zeichen lang ist.>> ...>> ich dachte daran, 10 Zeilen>> zusammenzufassen und aus diesen 10 Zeilen einen Prüfstring zu bilden.>> ...>> Danach hat man 10 Hashs, für jede Zeile einen.>> Das heißt du willst eigentlich jede Zeile einzeln überprüfen und nicht> ob in einem 10 Zeilen langen Block irgendwo was nicht stimmt?
Nunja, es soll nur einen einzigen und kurzen Prüfstring geben und den
gesamten 10 Zeilen Block umfassen.
Der Unterschied ist allerdings die Qualität der Datensicherheit
bezüglich einzelner Zeile vs. ganzer Block.
Denn auf Zeilenebene muss nur erkannt werden, ob die Zeile fehlerhaft
ist, nicht wo der Fehler ist.
Beim ganzen Block soll dagegen aber erkannt werden, welche Zeile
fehlerhaft ist.
Das dürfte auch bei der Reduktuion der Daten für den Prüfstring helfen.
> Macht also ein Hex = 4 Bit pro Zeile. Das wäre dann sowas wie CRC4>> Je nachdem was wichtiger ist, die genaue Zeile oder ob überhaupt ein> Fehler vorhanden ist.
Die Zeile wo der Fehler vorkommt.
> Würde ich eher 16 Zeilen nehmen und für jede Zeile> nur ein Parity-Bit verwenden und über alle 16-Zeilen ein CRC32 bilden.> Bei mehreren Fehlern muss dann nicht unbedingt die ermittelte Zeile> stimmen, aber die Erkennung ob überhaupt ein Fehler vorhanden ist sollte> so schon recht gut sein.
Das ist aber genau der Punkt, man soll ja nicht in 16 Zeilen den oder
die Fehler finden, sondern man soll gleich sehen, Zeile k und i hat
einen oder mehrere Fehler, die anderen sind fehlerfrei.
Martin S. schrieb:> Dein Ansatz funktioniert blockweise nicht.>> Beispiel: Der Nutzer vergisst eine Zeile, jeder folgende Block ist> daraufhin falsch.
Die Blöcke sind voneinander ja unabhängig. D.h. unter jedem Block steht
der Prüfstring als Kommentar.
Daran ist erkennbar, wo ein Block beginnt bzw. endet.
Wenn jetzt der Empfänger anstatt 10 Zeilen nur 9 eintippt und bspw. die
7. vergessen hat, dann dürften ihm die 7., 8., 9. und 10. Zeile als
fehlerhaft angezeigt werden.
Den Rest muss er dann schon manuell merken.
Wenn er jetzt den Prüfstring falsch setzt, dann werden alle Folgeblöcke
falsch, das ist richtig, aber spätestens das sollte er dann auch merken,
wenn ihm alle Folgezeilen als falsch gemeldet werden.
Das gab es schon zu C-64 Zeiten. Wenn man HEX-Programme eingetippt hat.
Nach jeder Zeile gab es ein 2 Stelligen HEX-code. Der wurde mit
eingetippt und man war sicher.
Je größer der Block je mehr muss man Suchen.
Schlaumaier schrieb:> Das gab es schon zu C-64 Zeiten. Wenn man HEX-Programme eingetippt> hat.>> Nach jeder Zeile gab es ein 2 Stelligen HEX-code. Der wurde mit> eingetippt und man war sicher.>> Je größer der Block je mehr muss man Suchen.
Hast du dafür ein Beispiellisting?
Würde mir das gerne mal ansehen.
Nano schrieb:> Hast du dafür ein Beispiellisting?
Schlaumaier meint vermutlich MSE:
https://www.c64-wiki.de/wiki/MSE
Wobei mir MSE 2.0 nie in freier Wildbahn begegnet ist, aber 1990 war
meine C64-Zeit auch schon vorbei.
Hmmm schrieb:> Nano schrieb:>> Hast du dafür ein Beispiellisting?>> Schlaumaier meint vermutlich MSE:
Genau. Wie das MSE 1.0 in deinen Link.
Das ganze funktionierte so. Man musste zuerst ein Programm einmalig
abtippen und das dann starten.
Dann wurde ein Editor gestartet in den man den code eingeben hat. Ich
finde zwar auf die schnelle keine nähere Infos dazu ABER hier in den
Link ist ein Foto des "Programm-Codes" den man eingeben musste.
Die Zahl vorne gab die Zeilenstellung an. Die 2 Stelligen Zahlen danach
waren der Code. Die Zahl die in der Zeile als letzte etwas abgesetzt war
ist die Prüfsumme. Wenn da ein Fehler war, konnte man die nächste Zeile
nicht mehr eingeben.
Ich habe mir damals extra dafür einen externe 10er Tastatur
(Taschenrecher-Layout" gekauft und den "Treiber" so umgeschrieben das
die Rechen-Symbole mit den Buchstaben A-F umgewandelt wurden.
https://www.oliver-kilb.de/wp/2016/05/22/1986-chris-huelsbeck-und-shades-verblueffen-die-c64-welt/
Vorher wurde das Ganze nämlich SO ein gegeben.
Eine kleine For-Next-Schleife und dann viele Poke ;) Der Code sah dann
ca. so aus.
https://www.c64-wiki.de/wiki/Listing_des_Monats
Den Code auf den Foto habe ich damals auch abgetippt.Es war nämlich der
erste Schnell-Lader. Lang lang ist her ;)
Schlaumaier schrieb:> Die Zahl vorne gab die Zeilenstellung an.
Was soll eine "Zeilenstellung" sein?
Das ist die Startadresse der jeweiligen Zeile, und die erste im Beispiel
($0801) ist der Anfang des BASIC-Programmspeichers, wo auch
standardmässig alles landete, was mit LOAD geladen wurde.
In den ersten Bytes hat sich üblicherweise minimaler BASIC-Code
verborgen, um per SYSxxxx den dahinter liegenden Code anzuspringen.
Schlaumaier schrieb:> Vorher wurde das Ganze nämlich SO ein gegeben.>> Eine kleine For-Next-Schleife und dann viele Poke ;)
Nein, ganz viele DATA-Zeilen und ein POKE innerhalb der Schleife.
Danke euch beiden.
Habe das Programm hier gefunden:
https://www.idealine.info/emuecke/tools_64.htm
Wenn man es downlädt und entpackt, kann man es in diesem
browserbasierten C64 Emulator ausführen:
https://c64online.com/c64-online-emulator/
Allerdings komme ich nicht weiter. Da müsste ich wohl erst MUSE auf dem
Rechner installieren.
Wie war das eigentlich so von der Erfahrung her beim Abtippen der
Programmlistings?
Hat es bezüglich der Vorfreude Spaß gemacht oder hat es mehr genervt?
Und habt ihr davon viel oder wenig gelernt?
Ich schätze mal, dass man von dem BASIC Programmlistings mehr lernen
konnte, als von den Hexcode Listings, da man letztere nur abtippen, aber
nicht wirklich lesen konnte. Oder?
Nano schrieb:> Allerdings komme ich nicht weiter. Da müsste ich wohl erst MUSE auf dem> Rechner installieren.
Sorry, meinte eigentlich MAME.
Wobei der wohl, wenn ich mich jetzt nicht irre, gar keinen C64 emulieren
kann, also VICE.
Moin,
Nano schrieb:> Hat es bezüglich der Vorfreude Spaß gemacht oder hat es mehr genervt?
Solche Befindlichkeiten haben damals keinen gekratzt.
> Und habt ihr davon viel oder wenig gelernt?
Naja, sicherlich mehr, als wenns damals schon Internet oder gar soziale
Medien gegeben haette.
> Ich schätze mal, dass man von dem BASIC Programmlistings mehr lernen> konnte, als von den Hexcode Listings, da man letztere nur abtippen, aber> nicht wirklich lesen konnte. Oder?
Mit der Zeit konnte ich schon die gaengigen Z80-"Vokabeln" in Dezimal.
djnz ist z.b. 16 und ret 201. Damit werd' ich wahrscheinlich noch im
Altersheim die Pflegekraefte nerven koennen, wenn sonst garnix mehr
geht.
Zu deinem urspruenglichen Problem:
Du schreibst da was von "moeglichst kurz" als Fehlererkennung in einer
Zeile. Das ist halt Bullshit, denn moeglichst kurz waere 1 bit, z.b. als
Paritaet ueber eine Zeile ASCII.
Da kanns natuerlich gut sein, dass du dann Fehler nicht erkennst. Das
wird dir auch nicht passen. Also brauchste ein Verfahren mit > 1bit
"Pruefsumme". Such' dir was raus. Wenn du Fehler nur erkennen, aber
nicht korrigieren koennen willst, ist CRC ein gaengiges Verfahren.
Laenge halt nach Geschmack.
Dann kriegst du halt fuer deinen Haufen Zeilen einen Haufen CRC-Werte.
So kannste jede Zeile auf Fehlerfreiheit checken. Fertsch.
Gruss
WK
einfach alle Zeichen im Block 8/16/32-bit addieren. die
Wahrscheinlichkeit, dass es bei richtiger Prüfsumme auch richtig ist,
steigt mit Länge der Prüfsumme. Auch bei Ibans können sich zwei Fehler
so aufheben, dass die Prüfsumme trotzdem stimmt - glaube ich zumindest.
Sorry, dass ich nichts schlaueres als schon genanntes beitragen kann,
aber mich lässt eine Frage nicht los...
Nano schrieb:>> Wofür soll das in der Praxis genutzt werden?>> Code Listings zum Abtippen wie früher und leichteren finden von> Tippfehlern mit dem Ziel, das sich der Abtipper auch Gedanken macht ohne> lange suchen zu müssen.
Warum um alles in der Welt?
"Abtippen" und "Gedanken machen" schließen sich (zumindest für mich)
gegenseitig aus.
Hmmm schrieb:> Nein, ganz viele DATA-Zeilen und ein POKE innerhalb der Schleife.
Meinte ich doch ;)
mh schrieb:> "Abtippen" und "Gedanken machen" schließen sich (zumindest für mich)> gegenseitig aus.
Absolut nicht.
Es gibt in der allgemeinen Schulwissenschaft immer noch die Logik. "Wenn
man es aufschreibt merkt man es sich". Hat bei mir nie funktioniert.
Aber das liegt eher daran das ich mich (mit bescheidenen Erfolg) auf
meine Rechtschreibung konzentriert habe. ;)
ABER. Ich habe durch das abtippen und von Listings programmieren
gelernt. Genau so wie viel Leute heute mit YT-Videos Sachen lernen. Frei
nach den Motto : "So wird es gemacht".
Selbst heute noch schau ich mir bei gewissen Situationen sogenannte
"Codeschnipsel" an. 10 Zeilen Code die zeigen wie die Syntax geht, und
was das Ergebnis ist sind auch heute noch vielen Profis sehr hilfreich.
Siehe z.b. MS-Hilfe.
Es geht dabei Grundsätzlich um 2 Fragen. GIBT es ein Befehl + wie
funktioniert er. Und selbst heute kenne ich nicht alle
Befehle+Funktionen meiner Lieblingsprogrammiersprachen. Das gebt ich
ehrlich zu. Aber ich weiß wo sie zu finden sind.
ABER. ganz ehrlich ein ganzen Programm würde ich heute nicht mehr
abtippen. Also frage ich mich ernsthaft was der TO mit seinen Plan will.
grundschüler schrieb:> einfach alle Zeichen im Block 8/16/32-bit addieren.
5+5 gibt 10
2+8 gibt aber auch 10
3+3+4 gibt ebenfalls 10
1+9 auch
5+4+1 auch
Und die Länge einer Zeile ist Variable.
Wenn du nur addierst, dann kannst du auf diese Weise eine Zeile komplett
falsch schreiben und deine Summe stimmt trotzdem.
D.h. so erkennst du keine Fehler, weil deine Wahrscheinlichkeit, dass
andere Kombinationen genauso gut auf die Summe passen, viel zu hoch ist.
Deswegen funktioniert CRC auch nicht so.
> die> Wahrscheinlichkeit, dass es bei richtiger Prüfsumme auch richtig ist,> steigt mit Länge der Prüfsumme.
Die Prüfsumme soll aber möglichst kurz gehalten werde.
mh schrieb:> Warum um alles in der Welt?>> "Abtippen" und "Gedanken machen" schließen sich (zumindest für mich)> gegenseitig aus.
Unterbewusst wirst du trotzdem ein bisschen mitdenken, das ist
unvermeidlich.
Spätestens wenn du dich wunderst und die fragst, warum da jetzt etwas
kommt, mit dem du nicht gerechnet hast, wirst du genauer hinsehen
wollen.
Moin,
Nano schrieb:> Die Prüfsumme soll aber möglichst kurz gehalten werde.
Ich schrub es schonmal: Das ist Bullshit. Oder du nimmst eben ein
Paritybit fuer jede Zeile. Das ist die kuerzest moegliche Pruefsumme.
Die wird dir aber wahrscheinlich nicht passen, weil eben schon 2 Fehler
in einer Zeile damit nicht mehr sicher erkannt werden koennen.
Du musst eine max. zulaessige Zeilenlaenge definieren und eine max.
erkennbare Anzahl von Fehlern in dieser Zeilenlaenge.
Daraus kann man dann die dafuer die mindestens noetige Laenge der
Pruefsumme bestimmen. Das Zauberwort ist: Mindesthammingdistanz.
Gruss
WK
Jede Prüfsumme hat eine Fehlerquote.
Wenn dir eine 1:256 Quote reicht, dann addiere doch einfach die
ASCII-Werte des Textes. Errechne aus den Wert solange eine Quersumme bis
der letzte Wert < 256 ist. Den nimmst du als Prüfsumme und fertig ist
das ganze.
Hex eingegeben ergibt das dann 2 Zeichen zu tippen.
Dergute W. schrieb:> Moin,>> Nano schrieb:>> Die Prüfsumme soll aber möglichst kurz gehalten werde.>> Ich schrub es schonmal: Das ist Bullshit.
Das ist eine Anforderung und damit wertfrei.
> Oder du nimmst eben ein> Paritybit fuer jede Zeile. Das ist die kuerzest moegliche Pruefsumme.> Die wird dir aber wahrscheinlich nicht passen, weil eben schon 2 Fehler> in einer Zeile damit nicht mehr sicher erkannt werden koennen.> Du musst eine max. zulaessige Zeilenlaenge definieren und eine max.> erkennbare Anzahl von Fehlern in dieser Zeilenlaenge.
Deswegen der Gedanke mit der Bildung eines Hashs pro Zeile.
Ein Hashalgorithmus macht aus vielen Daten variabler Länge einen kurzen
Hash und der ist ausreichend eindeutig, dass Kollisionen zwar möglich,
aber die Wahrscheinlichkeit dafür gering ist. Das ist also bedeutend
besser, als dieses aufaddieren welches Grundschüler vorgeschlagen hat.
Im nächsten Schritt, wenn es um die 10 Hashs der 10 Zeilen geht, ich
nenne sie mal Zeilenhashs, muss ich jetzt nur alle Zeilenhashs zu einem
einzigen Gesamthash reduzieren, also daraus erneut einen neuen Hash
bilden.
Zu beachten ist ja, dass die Zeilenhashs aus dem Text jederzeit neu
gebildet werden können, wenn Fehler enthalten sind, ergibt das einen
anderen Zeilenhash.
Was ich aber jetzt brauche ist eine Möglichkeit aus diesem neuen Hash,
der aus allen vorherigen gebildet wurde, wenigstens rekonstruieren zu
können, welche der vorherigen Hashs falsch waren.
Und ich weiß nicht, ob es dafür ein geeignetes Hashverfahren gibt?
Ich habe also:
H1, H2, H3, ..., H10 => Hges
Hges ist kurz.
Dessen Eingabestrom, also H1 bis H10, kann Kollisionen haben, es wären
also mehrere verschiedene Eingabeströme möglich, aber die
Wahrscheinlichkeit welche zu finden, die dann auf Hges passen, die soll
wiederum gering sein.
Und eine weitere Anforderung ist, dass es möglich sein muss, aus Hges
schließen zu können, welche Hashs des Eingabestroms mit einer gewissen
Wahrscheinlichkeit falsch waren.
Und hier hapert es. Die meisten Hashverfahren sind darauf ausgelegt,
dass man nur unter hohem Aufwand, sofern überhaupt, passende
Eingabeströme finden kann. Das ist aber nicht zwingend das, was ich
brauche, denn ich muss ja nur wissen, ob er richtig oder falsch war und
nicht, wie er ganz genau aussah.
Der Empfänger bekommt den Text und Hges.
Aus dem Text macht er dann:
H1, H2, H3b, ..., H10
H3b sei hier fehlerhaft, also nicht identisch mit H3. Ob dem so ist,
weiß man aber noch nicht.
Jetzt muss also aus:
H1, H2, H3b, ..., H10 = Hges2
gemacht werden.
Wenn Hges2 identisch mit Hges ist, dann waren mit einer gewissen
Wahrscheinlichkeit (wegen der Kollisionsmöglichkeit) alle Zeilenhashs
korrekt.
In dem Beispiel wird Hges2 aber abweichen, da ja H3b anders war.
Man weiß also schon einmal, dass mindestens einer der Zeilenhashs falsch
war.
Jetzt soll es nur noch möglich sein, aus Hges und dem Text, sowie den
gerade arbeiteten Informationen rekonstruieren zu können, welcher das
war.
> Daraus kann man dann die dafuer die mindestens noetige Laenge der> Pruefsumme bestimmen. Das Zauberwort ist: Mindesthammingdistanz.
Danke, mir ist auch das Nyquist-Shannon-Abtasttheorem bekannt, weswegen
ich mich auf Wahrscheinlichkeiten bezüglich Kollisionen verlassen
möchte, damit durch das Zulassen von Kollisionen die Datenmenge
reduziert werden kann, aber man anhand der Wahrscheinlichkeit dann doch
eine ausreichende Sicherheit bezüglich der Plausibilität hat.
Betrachte es also als so eine Art verlustbehaftete Fehlererkennung.
Moin,
Nano schrieb:>> Ich schrub es schonmal: Das ist Bullshit.>> Das ist eine Anforderung und damit wertfrei.
Nein, das ist dumm, sorry.
Genauso dumm, wie wenn du sagst: Du willst einen moeglichst rauscharmen
Verstaerker. Oder einen moeglichst lineaeren. Du musst da konkrete Werte
nennen, dann gehts weiter. Bzw. es wird klar, dass das z.b. zu teuer,
gross oder sonstwas wird.
Denn was heisst "moeglichst kurz"?
Am kuerzesten sind 0bit. Also nix. Haste halt auch ueberhaupt keine
Sicherung. Willste nicht, logo.
Das naechstkuerzeste ist 1bit, also z.b. Parity. Das willste aber nicht,
denn das ist dir zu unsicher.
Also musst du doch auch angeben, wie "unsicher" ist fuer dich dann
sicher genug.
Und da spielt dann die max. moegliche Laenge einer Zeile mit rein, um
auf eine Mindestlaenge fuer deine Pruefsumme zu kommen. Wie du dann auf
die Pruefsumme kommst, also: wie der Algorithmus heisst, ob jetzt Hash
oder Paritaet oder Schlonz ist da erstmal voellig wurst.
Nano schrieb:> Der Empfänger bekommt den Text und Hges.> Aus dem Text macht er dann:> H1, H2, H3b, ..., H10>> H3b sei hier fehlerhaft, also nicht identisch mit H3. Ob dem so ist,> weiß man aber noch nicht.>> Jetzt muss also aus:> H1, H2, H3b, ..., H10 = Hges2> gemacht werden.>> Wenn Hges2 identisch mit Hges ist, dann waren mit einer gewissen> Wahrscheinlichkeit (wegen der Kollisionsmöglichkeit) alle Zeilenhashs> korrekt.>> In dem Beispiel wird Hges2 aber abweichen, da ja H3b anders war.> Man weiß also schon einmal, dass mindestens einer der Zeilenhashs falsch> war.> Jetzt soll es nur noch möglich sein, aus Hges und dem Text, sowie den> gerade arbeiteten Informationen rekonstruieren zu können, welcher das> war.
Schoener Traum, seh' ich aber nix, was dem naeherkommt, als einfach alle
Hashes/Pruefsummen (mit bekannter, konstanter Laenge) hintereinander zu
schreiben.
Dann da willst du ja mehr als eine Fehlererkennung, sondern du willst
die Position des Fehlers und dann auch noch bis zu "alle Zeilen sind
falsch".
Gruss
WK
Dergute W. schrieb:> Du musst da konkrete Werte> nennen, dann gehts weiter. Bzw. es wird klar, dass das z.b. zu teuer,> gross oder sonstwas wird.>> Denn was heisst "moeglichst kurz"?> Am kuerzesten sind 0bit. Also nix. Haste halt auch ueberhaupt keine> Sicherung. Willste nicht, logo.>> Das naechstkuerzeste ist 1bit, also z.b. Parity. Das willste aber nicht,> denn das ist dir zu unsicher.>> Also musst du doch auch angeben, wie "unsicher" ist fuer dich dann> sicher genug.
Ich habe ja nicht gesagt, dass es gar keine Länge haben soll.
Die Anzahl an notwendigen Prüfzusatzbits steigen bei einem gegebenen
Hamming-Abstand mit der Anzahl der Zeilenlänge und die ist variabel.
Habe ich also eine super lange Zeile, dann wird auch die Kette an
Prüfbits super lang.
Das möchte ich aber vermeiden, deswegen die Bildung eines Hash.
Der Hash hat dann eine fest definierte Länge und dem kann man dann eine
kurze Folge an Prüfbits anhängen.
Damit kann ich zwar keine Fehler der gesamten Zeile korrigieren, was
keine Anforderung ist, aber ich kann zumindest den Hash auf Richtigkeit
überprüfen, mehr ist auf Zeilenbasis nicht erforderlich.
Das Risiko von Kollisionen nehme ich in Kauf, wie hoch dieses ist, ist
abhängig vom Hashalgorithmus und da genügt es wenn es ausreichend
unwahrscheinlich ist.
Jemand der einen Text abtippt, wird entweder in der Zeile verrutschen
und somit eine völlig andere Zeile abtippen oder aber einen großen Teil
der Zeile richtig abtippen. Damit ist die Wahrscheinlichkeit einer
Kollision schon extrem gering, denn Kollisionen sind bei gescheiten
Hashalgorithmen meist etwas, was in der Praxis nur mit Vorsatz, bei dem
man dann Kauderwelsch als Eingabe eingeben muss, vorkommt und nicht
durch Fehler.
Gegen Vorsatz will ich die Zeile nicht absichern, das macht hier auch
keinen Sinn, sondern lediglich gegen Flüchtigkeitsfehler beim Abtippen.
Das ist die Sicherheitsanforderung.
Zeichen aufzuaddieren und daraus eine Quersumme zu bilden ist aber nicht
sicher genug. Manche Hashverfahren machen eine Polynomdivision, ich bin
aber kein Mathematiker um mir da etwas optimales auszudenken.
> Und da spielt dann die max. moegliche Laenge einer Zeile mit rein, um> auf eine Mindestlaenge fuer deine Pruefsumme zu kommen.
Dein Denkfehler ist, dass du dich auf eine, ich formuliere es mal so,
lossless Fehlererkennung beziehst. Wenn das meine Anforderung wäre, dann
hättest du recht. Ist sie aber nicht, da ich über die Hashbildung
bereits Informationsverluste habe und somit Kollisionen möglich sind,
die ich aber durch wegen der Wahrscheinlichkeit in Kauf nehme.
> Wie du dann auf> die Pruefsumme kommst, also: wie der Algorithmus heisst, ob jetzt Hash> oder Paritaet oder Schlonz ist da erstmal voellig wurst.
Ein Hash und Prüfsummen sind zwei verschiedene Dinge.
Wenn du bspw. eine ISO Datei mit einer Größe von 650 MB downlädts, dann
hätte die eine so riesigen Bitprüfstring, dass deine Prüfsumme nach
deinen Kriterien extrem lang werden würde. Und das so zu machen ist dann
dumm.
Deswegen macht man es nicht so. Man erstellt stattdessen einen Hash.
Da reicht bspw. ein MD5 Hash. Der ist 32 Hex Zeichen kurz, also um
mehrere Größenordnungen kürzer als ein dein Bitprüfstring.
Und er ist ausreichend sicher um sagen zu können, dass die Datei
fehlerfrei downgeladen wurde.
Und trotzdem gibt es bei ihm die Möglichkeit von Kollisionenen, die sind
aber so unwahrscheinlich, dass das Risiko vernachlässigbar ist.
So eine Kollision wäre sehr wahrscheinlich nicht einmal ein lesbares ISO
Image, spätestens hier würde man es erkennen, selbst wenn die MD5 Summe
identisch wäre.
Und in meinem Beispiel wäre es ganz genauso. Der Empfänger würde sich
wunder, warum er plötzlich Kauderwelsch abtippt.
Also gibt es hier Möglichkeiten Informationsverluste in Kauf zu nehmen
und damit schrumpft dann auch die Länge des Strings, womit man die Daten
auf "enthält Fehler" oder "enthält mit einer gewissen Wahrscheinlichkeit
keine Fehler" überprüfen kann.
> Nano schrieb:>> Der Empfänger bekommt den Text und Hges.>> Aus dem Text macht er dann:>> H1, H2, H3b, ..., H10>>>> H3b sei hier fehlerhaft, also nicht identisch mit H3. Ob dem so ist,>> weiß man aber noch nicht.>>>> Jetzt muss also aus:>> H1, H2, H3b, ..., H10 = Hges2>> gemacht werden.>>>> Wenn Hges2 identisch mit Hges ist, dann waren mit einer gewissen>> Wahrscheinlichkeit (wegen der Kollisionsmöglichkeit) alle Zeilenhashs>> korrekt.>>>> In dem Beispiel wird Hges2 aber abweichen, da ja H3b anders war.>> Man weiß also schon einmal, dass mindestens einer der Zeilenhashs falsch>> war.>> Jetzt soll es nur noch möglich sein, aus Hges und dem Text, sowie den>> gerade arbeiteten Informationen rekonstruieren zu können, welcher das>> war.> Schoener Traum, seh' ich aber nix, was dem naeherkommt, als einfach alle> Hashes/Pruefsummen (mit bekannter, konstanter Laenge) hintereinander zu> schreiben.> Dann da willst du ja mehr als eine Fehlererkennung, sondern du willst> die Position des Fehlers und dann auch noch bis zu "alle Zeilen sind> falsch".
Ja, wobei es hier aber um Positionsstrings blockweise geht, nicht um
einzelne Zeichen.
Ich werde mir mal ein paar Gedanken dazu machen.
Vielleicht könnte man durch Bildung von 3 Gesamthashs, die aus den 10
Zeilenhashs gebildet werden, den Fehlerhaften Zeilenhash erkennen.
Einfach dadurch, in dem ich die 10 Zeilenhashs in der Reihenfolge vor
der Hashbildung eines Gesamthashs ändert.
ABCDE = Hges1 (nacheinander)
ACEBD = Hges2 (jede ungerade Stelle, dann die geraden)
EBCDE = Hges3 (rückwärts)
Und dann wird Hges1, Hges2, Hges3 nur noch verkettet und fertig ist mein
Prüfstring.
So etwa sind der Art.
3 Gesamthashs sind dann immer noch kürzer als 10 Zeilenhashs.
Nano schrieb:> ABCDE = Hges1 (nacheinander)> ACEBD = Hges2 (jede ungerade Stelle, dann die geraden)> EBCDE = Hges3 (rückwärts)>> Und dann wird Hges1, Hges2, Hges3 nur noch verkettet und fertig ist mein> Prüfstring.>> So etwa in der Art.>> 3 Gesamthashs sind dann immer noch kürzer als 10 Zeilenhashs.
Genaugenommen müsste ich es überlappend mit Teilmengen machen.
Also bspw. aus ABCDEF
A mit C und E = Hges1
B mit D mit F = Hges2
und
A mit D bspw. E = Hges3
Ist C dann falsch, dann wäre Hegs1 falsch und Hges2 und 3, sowie A, B,
D, F und E richtig, somit C der Fehler wäre und als dieser erkannt
werden würde.
Moin,
Nano schrieb:> Ein Hash und Prüfsummen sind zwei verschiedene Dinge.
Wo siehst du da einen Unterschied? Ich sehe keinen (Ja, vielleicht sind
die "guten" Hashalgorithmen einigermassen sicher, um provozierte
Kollisionen schwer zu machen, aber das ist bei dir wohl eher wurscht.)
Nano schrieb:> Vielleicht könnte man durch Bildung von 3 Gesamthashs, die aus den 10> Zeilenhashs gebildet werden, den Fehlerhaften Zeilenhash erkennen.> Einfach dadurch, in dem ich die 10 Zeilenhashs in der Reihenfolge vor> der Hashbildung eines Gesamthashs ändert.
Mit Bits statt Hashes hat der Herr Hamming schon vor Jahren sowas in der
Art gemacht. Problem ist nur: Damit kannst du nicht beliebig viele
Fehler erkennen, sondern beim "klassischen" (7,4) eben nur 1
korrigieren.
Jetzt kannste hergehen und statt Bits eben Symbole (also deine Hashes,
bestehend aus mehreren Bits) nehmen, iirc kommste dann bei BCH- oder
RS-Codes raus. Aber die sind eher auf Fehlerkorrektur getrimmt, als auf
Fehlererkennung incl. Position. Und niemals auf Fehlererkennnung von bis
zu allen Symbolen.
Gruss
WK
Dergute W. schrieb:> Moin,
Moin
https://www.youtube.com/watch?v=2NSi9w23-HA> Nano schrieb:>> Ein Hash und Prüfsummen sind zwei verschiedene Dinge.>> Wo siehst du da einen Unterschied?
Das ergibt sich bereits aus dem unterschiedlichen Anwendungsziel.
Prüfsummen können dazu dienen, Fehler zu erkennen und bei ausreichendem
Hemming-Abstand auch zu korrigieren.
Bei einem Hash kannst du nur auf einen Fehler schließen, sofern dich
eine Kollision nicht in die Irre führt, aber du kannst den Fehler nicht
mit dem Hash korrigieren, wie es mit einer entsprechenden Prüfsumme
ginge.
> Jetzt kannste hergehen und statt Bits eben Symbole (also deine Hashes,> bestehend aus mehreren Bits) nehmen, iirc kommste dann bei BCH- oder> RS-Codes raus. Aber die sind eher auf Fehlerkorrektur getrimmt, als auf> Fehlererkennung incl. Position.
Werde mir die Codes mal anschauen. Bisher ging ich davon aus, dass die
Fehlerkorrektur eine Stufe höher vor der Fehlererkennung liegt.
Eine Fehlererkennung also immer dann möglich ist, wenn auch eine
Fehlerkorrektur möglich ist, aber nicht umgekehrt.
> Und niemals auf Fehlererkennnung von bis> zu allen Symbolen.
Ja, mir ist schon aufgefallen, dass ich bei meiner obigen Überlegung mit
den Teilabschnitten wohl auf eine Fehlererkennung eines einzelnen
Fehlers wenn mehreren Fehler der 10 Symbole auftreten, verzichten muss.
Moin, ;-)
Nano schrieb:> Das ergibt sich bereits aus dem unterschiedlichen Anwendungsziel.
Kommt fuer mich trotzdem beides aufs Selbe raus.
Ich hab ein paar Bit und aus denen kann ich per irgendeinem mehr oder
weniger schlauen Algorithmus ein paar "neue" bits ausrechnen.
> Prüfsummen können dazu dienen, Fehler zu erkennen und bei ausreichendem> Hemming-Abstand auch zu korrigieren.> Bei einem Hash kannst du nur auf einen Fehler schließen, sofern dich> eine Kollision nicht in die Irre führt, aber du kannst den Fehler nicht> mit dem Hash korrigieren, wie es mit einer entsprechenden Prüfsumme> ginge.
Triviales Gegenbeispiel: Wenn ich 1 Bit Nutzinformation durch einen z.b.
SHA256 "schuetze", dann kann ich ziemlich sicher auch Fehler
korrigieren, nicht nur erkennen.
Ist eben nicht eine Frage, ob ich jetzt meinen Algorithmus Hash oder
Pruefsumme nenne, sondern nur eine Frage der Mindesthammingdistanz.
Und natuerlich gibt's Algorithmen, die in der Praxis besser geeignet
sind, Fehler zu korrigieren und andere eher zu erkennen. Das ist aber
reine Implementierungsfrage. Und sowas kann sich auch mit der Zeit
aendern. Die LDPC Codes, die bei DVB-S2 verwendet werden, sind uralt -
war aber frueher zuviel Aufriss/DSP/Power, sowas zu implementieren - da
hat die keiner fuer irgendwas praktisches hergenommen. Heute kannste
ohne kaum mehr Fernsehen gucken.
Gruss
WK
Dergute W. schrieb:> Triviales Gegenbeispiel: Wenn ich 1 Bit Nutzinformation durch einen z.b.> SHA256 "schuetze", dann kann ich ziemlich sicher auch Fehler> korrigieren, nicht nur erkennen.
Nein, denn ich kann dir jetzt schon sagen, dass es mindestens n > 1
Kollisionen gibt, die den gleichen SHA256 Wert ergeben aber deutlich
länger als dieses 1 Bit sind.
Zumal, wie soll dein Algorithmus dazu aussehen?
Bei Hashwerten kann man in der Regel nicht den Ausgangswert
zurückrechnen, das geht nur in eine Richtung.
> Die LDPC Codes, die bei DVB-S2 verwendet werden, sind uralt -> war aber frueher zuviel Aufriss/DSP/Power, sowas zu implementieren - da> hat die keiner fuer irgendwas praktisches hergenommen. Heute kannste> ohne kaum mehr Fernsehen gucken.
Naja, die Leistung der Hardware ist begrenzt und früher war die
schwächer als heute, also konnte man nur Algorithmen verwenden, die mit
dieser schwachen Hardware auch in Echtzeit realisierbar war.
Die Algorithmen sind oftmals früher bekannt, bevor es eine geeignete
Hardware dafür gibt. Umgekehrt passiert es nicht so oft.
Moin,
Nano schrieb:> Nein, denn ich kann dir jetzt schon sagen, dass es mindestens n > 1> Kollisionen gibt, die den gleichen SHA256 Wert ergeben aber deutlich> länger als dieses 1 Bit sind.
Ja klar kannst du das dann. Aber wenn du eben weisst, dass du nur 1 Bit
Originallaenge hattest, kannst du prima korrigieren.
Und wenn du irgendwelche Wahrscheinlichkeiten haben willst, mit denen
was schiefgeht, dann ist das stark von der Menge deiner zu schuetzenden
Bits abhaengig.
Gruss
WK
Hmmm schrieb:> Nein, ganz viele DATA-Zeilen und ein POKE innerhalb der Schleife.
Ich habe das von damals anders in Erinnerung. Hatte auch etliche
solcher Listings abgetippt.
Die DATAs wurden dann in einer Schleife gelesen (geholt) und
dann binär, also auch wieder byteweise hintereinander in eine Datei
geschrieben, die mit .com endete.
Die ersten Bytes (Hexzahlen) beschrieben die Dateiart (HEADER -
ausführbar),
wie heutzutage bei einer .EXE auch ersichtlich. Danach erhielt man dann
die ausführbare .com - Datei.
Sowas ähnliches benutze ich heute gelegentlich noch, um z.B. Bilder
oder auch .DLLs in einen normalen Speicherbereich zu bekommen. Statt
Hexzahlen spuckt der Integerzahlen raus. Bei meiner Sprache gibt es
halt keine DATAs. Die Zahlen stehen dann als Klartext in meinem
Programmlisting. Bei Ausführung des Programm wird dieser Speicherblock
dann als Block in eine Bilddatei, .DLL o.ä. geschrieben. Das hatte ich
deshalb gemacht, weil einige Benutzer meines Programm die beigefügte
.DLL einfach gelöscht hatten und sich wunderten, daß mein Programm
nachher nicht mehr funktionierte. Somit konnte ich dann sichergehen,
daß die .DLL bei Programmstart neu geschrieben wurde und dann auch
zur Verfügung stand.
Retrofan schrieb:> Die DATAs wurden dann in einer Schleife gelesen (geholt) und> dann binär, also auch wieder byteweise hintereinander in eine Datei> geschrieben, die mit .com endete.
Dann redest Du von MS-DOS-PCs, nicht vom C64, um den es oben ging.
Retrofan schrieb:> Die ersten Bytes (Hexzahlen) beschrieben die Dateiart (HEADER -> ausführbar),> wie heutzutage bei einer .EXE auch ersichtlich.
Nein, COM-Files haben keinen Header und werden an eine feste Adresse
geladen. Bei EXEs wiederum gibt es den PE-Header.
Retrofan schrieb:> Somit konnte ich dann sichergehen,> daß die .DLL bei Programmstart neu geschrieben wurde und dann auch> zur Verfügung stand.
Das knallt aber in dem Moment, wo Du a) nicht im Programmverzeichnis
schreiben kannst (inzwischen der Regelfall) und b) per Group Policy
verhindert wird, dass DLLs aus Quellen geladen werden, wo Du es kannst.
Da ist der Ansatz, einen Installer mitzuliefern, sinnvoller. Zumindest
sind mir noch keine Leute begegnet, die planlos in C:\Program Files DLLs
löschen.
Aber wir schweifen vom Thema des Threads ab.
Hmmm schrieb:> Aber wir schweifen vom Thema des Threads ab.
Das Thema bezüglich Retro Programmlistings früher ist durchaus
interessant. Man könnte dafür einen neuen Thread aufmachen und jeder
seine Erfahrung dazu schreiben.
Nano schrieb:> Code Listings zum Abtippen wie früher und leichteren finden von> Tippfehlern mit dem Ziel, das sich der Abtipper auch Gedanken macht ohne> lange suchen zu müssen.
wenn das wirklich der Anwendungsfahl ist, bietet sich dann nicht eher
ein QR Code mit Link auf Seite mit komplettem Listing an? Oder einfach
nur ein Link?
Wer tippt 2022 denn noch Quellcodes ab?
"Ab der 64'er-Ausgabe 06/1994 entfiel das Abtippen der MSE-Listings, da
die Programmservicediskette dem Heft monatlich beigelegt wurde."
Sollte einem zu Denken geben ;)
Dergute W. schrieb:> die bei DVB-S2 verwendet werden, sind uralt -> war aber frueher zuviel Aufriss/DSP/Power, sowas zu implementieren
Erinnert mich an so 10 Jahre vorweg.. da konnte man Pay Tv mit einem
"gehackten" Sat-Receiver entschlüsseln.. Glaube das Stichwort war
"Nagra"
Oder auch 1998, da konnte man Premiere mit einer TV-Karte und nem Tool
aus der PC-Zeitschrift entschlüsseln :D
Wobei ich früher auch Programme für den C64 in HEX abgetippt habe...
Thread beobachten
Seitenaufteilung abschalten