Nachricht aus dem All II
Inhaltsverzeichnis
Die Aufgabenstellung
Eine Raumsonde sendet Nachrichten zur Erde. Wegen der großen Entfernung zwischen der Erde und der Raumsonde kommen die Signale nicht so an wie sie gesendet wurden, sondern werden verrauscht. Das bedeutet, dass einige Signale durch ein beliebiges Signal ersetzt werden. Damit man die Nachricht trotzdem noch entschlüsseln kann, sendet die Raumsonde die Nachricht mehrmals.
Meine Aufgabe bestand somit darin ein Programm zu schreiben, das die Nachrichten sowohl verrauschen (1) als auch entschlüsseln (2) kann.
Grundsätzliche Hinweise
Im Laufe meines Projektes hat es sich als sinnvoll erwiesen das Programm auf mehrere Units und grundlegende Funktionen zu verteilen, um so die Unit1 möglichst kompakt zu halten. Tritt zum Beispiel ein Problem in einer öfters verwendeten Funktion (Prozedur) auf, so muss man den Quelltext nur einmal ändern.
Zum angegebenen Quellcode:
Es handelt sich bei dem Quellcode um einen kleinen vereinfachten Ausschnitt, der nur dazu dient die Prinzipien der Lösung der Aufgabe zu verstehen. Der wirklich verwendete Quellcode ist umfangreicher, um eine möglichst hohe Benutzerfreundlichkeit zu erreichen.
Meine Lösungen
Aufgabe 1
In Aufgabe 1 soll ein Programm geschrieben werden, das eine Nachricht verrauschen kann. Es müssen somit eine zu verrauschende Nachricht, die gesendeten Wiederholungen, sowie die Fehlerfahrscheinlichkeit (die Wahrscheinlichkeit, dass ein empfangenes Signal falsch ist) vorgegeben werden.
Mein Lösungsansatz
Der vorgegebene Lösungsansatz sieht vor, dass der Benutzer festlegt wieviele Signale verrauscht werden. Ich halte dies jedoch für realitätsfern. Deshalb kann der Benutzer in meinem Programm eine Fehlerwahrscheinlichkeit vorgeben. Jedes einzelne Signal der Nachricht wird nun mit der vom Benutzer festgelegten Fehlerwahrscheinlichkeit verrauscht.
Das grundlegende Problem bei dieser Aufgabe liegt in der Erzeugung von Zufallszeichen. Da Delphi jedoch die Möglichkeit von Zufallszahlen bereitstellt, ist es mit Hilfe des ASCII Codes kein großes Problem hieraus Zufallszeichen zu erzeugen. Meht dazu unter (3).
Quellcodeausschnitt:
for i:= 1 to wdh do (1)
begin
ausgabetext := eingabetext;
for h:=1 to length (ausgabetext) do
begin
randomize;
pp:=random(99)+ 1; (2)
if p>pp then
begin
pp := random (126) + 32; (3)
zufall:= asciiText(pp);
ausgabetext[h]:= zufall;
end;
end;
memo2.Lines.add(ausgabetext);
end;
(1) Diese Schleife wird so oft wie die Anzahl der Wiederholungen durchlaufen. Das Programm erzeugt somit für jede Wiederholung genau eine verrauschte Nachricht, die an ein Memofeld angehängt wird.
(2)pp wird ein Zufallswert zwischen 99 und 1 zugewiesen. Ist dieser niedriger als die vom Benutzer festgelegte Wahrscheinlichkeit mit der das Signal falsch ist, so wird das Signal verrauscht. Die Zufallszahl darf höchstens 99 sein, damit bei einer festgelegten Fehlerwahrscheinlichkeit von 100% jedes Signal falsch ist.
(3) Um ein Signal zu verrauschen benötigt man ein Zufallszeichen. Dies wird erreicht, indem man einer Zufallszahl zwischen 32 und 126 das dazugehörige Zeichen mit Hilfe des ASCII Codes zuordnet. Zu Beginn habe ich eine selbst geschriebene Funktion verwendet, doch im Laufe des Projektes hat es sich als sinnvoll erwiesen die Delphifunktion „chr(Zufallszahl)“ zu verwenden, da so auch die Laufzeit bei dem Verrauschen von Signalen verringert werden konnte.
Ein kurzer Ausschnitt hierzu:
Die Delphi Funktion:
function AsciiText (Ascii:byte) :char; begin AsciiText:= chr(Ascii); end;
Eine selbst geschriebene Funktion:
function AsciiText (pp:integer):char; var Z: char; begin Z:='_'; case pp of 33: Z:='!'; 34: Z:='"'; 35: Z:='#'; 36: Z:='$'; 37: Z:='%'; 38: Z:='&'; [...] 124: Z:='|'; 125: Z:='}'; 126: Z:='~'; end; AsciiText := Z; end;
Aufgabe 2 und 3
In der Aufgabe 2 sollte ein Programm geschrieben werden, das eine (wie unter Aufgabe 1) verrauschte Nachricht entschlüsseln kann.
Der Grundgedanke bei der Lösung dieser Aufgabe liegt darin, dass das Programm den am häufigsten vorkommenden Buchstaben in den Stellen der Wiederholungen sucht und diesen anschließend ausgibt.
Eine Lösung des verrauschten Signals ist somit nur möglich, wenn es mehr richtige Signale gibt als das am häufigsten vorkommende falsche Signal. Falls notwendig könnte man das Programm an dieser Stelle ergänzen, so dass für jedes Signal einer Nachricht in aufzählender Weise alle vorkommenden Zeichen pro Stelle mit einer Wahrscheinlichkeitsangabe ausgegeben werden.
Deshalb ist es wichtig, dass das richtige Signal nach dem Verrauschen wieder vorkommen könnte, damit bei hohen Fehlerwahrscheinlichkeiten die Nachricht noch entschlüsselt werden kann. Nur so kann eine Nachricht mit 99% Fehlerwahrscheinlichkeit bereits mit (meistens) 2600 Wiederholungen entschlüsselt werden.
Ein Quellcodeausschnitt:
ausgabetext:=;
for I := 1 to signallaenge do (4)
begin -
for J := 0 to wiederhol -1 do -
begin -
int:= i + J*Signallaenge; (4)
buchstabe := eingabetext[int];
int:= TextAscii(buchstabe);
anzahl[int]:=anzahl[int] +1; (1)
end;
k:=0;
for j := 32 to 126 do (2)
begin
if anzahl[j]>k then
begin
k:= anzahl[j];
by := j;
end;
end;
buchstabe := asciiText(by);
ausgabetext := ausgabetext + buchstabe; (3)
for j := 32 to 126 do //Array leeren
anzahl[j]:=0;
end;
entschlüsseln:=ausgabetext;
end;
(1) Bei der Variablen "anzahl" handelt es sich um einen (integer-) Array, der im verwendeten ASCII Bereich definiert ist. In ihm wird für jedes mögliche Zeichen die vorkommende Anzahl im Signal gezählt. Ein Beispiel: anzahl[65] zählt die vorkommenden A Signale.
(2) Nun wird in dem Array "anzahl" der größte Wert gesucht und dadurch der am häufigsten vorkommende Buchstabe. Dieser wird nun an den Ausgabetext angehängt (3).
(4) Die Schwierigkeit bei dieser Aufgabe bestand darin, die vorkommenden Buchstaben so nacheinander im Array "anzahl" zu zählen, dass zuerst alle ersten Buchstaben der Wiederholungen gezählt werden, anschließend die zweiten Buchstaben jeder Wiederholung,... Dies konnte durch die doppelte Schleife realisiert werden.
Mit diesem Quelltext ergibt sich somit für Aufgabe 3 die folgende Lösung:
cqchs's_ikdefmdzsinke_fuirwheb_sischmjcnotbkslut_sn,edabkephrey_dpu_tghekumgchois_ cdtaynbjqhxvpctoarmoin_tiscijdacrtmdjgud_undirnpcrnfeerixnnwotscrxmahumisbrutkgngs cmqbv_nuerxdvnzcivbhyacaayspgrt_q.d_hcnrz_feenpdej_uqtkhwplgwnxz_kztauskbdankl_zu. fvdnnefesqrvychhhlvguwjundadkdhsbftfrczex_qischexcoj'bovit_unafdl,ki_fxerddemdvsth ynachxi'smgmyjuwhnpenkktmdxo_deaqfeckhukaclugpkgftaond_ronabgfuoyaaet_zaszhl
macht's_gut_und_danke_fuer_den_fisch!
Meine Erweiterungen
zx"_ˆGo—Ltœs„Dl”-U~=e%M‹gss!_‡GkaR{:b"tPX+S‘;xhPx8`rH€*R:o!
_8`ˆsp0X– H…0moU}=eMu5]…‚,Ts<d$LNv H†0r–Ai’Qw9at#Ks2[˜r€z$sŠJr2Z
ˆ3p˜X€rhv ^sFn–Vk“={%o‹Jk~(fŽMr5m•U}weLm•s}'eM:c‹ws2ZPam•T}'d
‡1Z—A?)t2Es,j’Rzaa4q™YAy#s‰Iq™YPB€*R:wT|'OŒotœda6tœ[„C&av6^†Fn
Š4rsZ‚BtJa1Y—A?)qƒCs+S;PQy#a‰IqŠ5]sE‚,j—A?)Qrw)QŽ9w I†P`‰Hp0Xz
Da die wenigsten Menschen eine Raumsonde im Orbit haben, habe ich mir weitere Gedanken über mögliche Verwendungszwecke von diesem Programm gemacht.
Eine Möglichkeit, die mir eingefallen ist, nachdem ich die oben stehende Nachricht gesehen habe, ist die Verwendung von dem Programm zum Speichern von "unwichtigen" Passwörtern auf einem Computer. So sollte man diese gefahrlos in einer Textdatei speichern können, ohne dass weitere Benutzer von dem Computer dies ohne Vorkenntnisse lesen können. Wer vermutet schließlich hinter dem oben stehenden Text ein "Passwort"?
Um dies zu ermöglichen, habe ich die Möglichkeit hinzugefügt, Textdateien zu speichern und zu laden.
//laden
if OpenDialog1.Execute then
begin
memo1.Clear;
DateiName := (OpenDialog1.Filename);
memo1.lines.LoadFromFile(Dateiname);
end;
//speichern
if SaveDialog1.Execute then
begin
DateiName := SaveDialog1.Filename + '.txt';
memo2.lines.SaveToFile(Dateiname);
end;
Da die Verschlüsselung von Passwörtern nur über Wahrscheinlichkeiten realisiert wird, habe ich das Programm so erweitert, dass man die Nachricht entschlüsseln lassen und automatisch mit einer vorgegebenen Lösung abgleichen lassen kann. Es kann nämlich passieren, dass auch bei einer Fehlerwahrscheinlichkeit von nur 1% alle Signale falsch sind.
Original := InputBox('Ausgabe prüfen', 'Bitte Originaltext eingeben:',' ');
eingabetext:= ;
Memozeilen := memo2.Lines.Count;
for I := 0 to Memozeilen - 1 do
begin
eingabetext:= eingabetext + memo2.Lines[I];
end;
if length(original)=0 then
showmessage('Geben Sie ein gültiges Signal ein!')
else
begin
if length(eingabetext)mod length(original)=0 then
begin
wiederhol := length(eingabetext) div length(original);
ausgabe:= entschlüsseln(eingabetext, wiederhol); (1)
if ausgabe=original then showmessage('Das Signal kann wiederhergestellt werden!')
else
showmessage('Das Signal kann nicht wiederhergestellt werden!');
end
else showmessage('Das Signal kann nicht wiederhergestellt werden!');
end;
(1) "entschlüsseln" ist eine Funktion, die im Wesentlichen wie die Lösung der Aufgabe 2 aufgebaut ist.
Weiterhin kann man im Entwicklermodus einen Text in den ASCII Code (und umgekehrt) umwandeln.
Die Masterschleife
Die Entstehungsgeschichte der Masterschleife
Eines Tages hatte ein namhafter Ingenieur in spe das Programm verwendet, um ein wichtiges Passwort zu verschlüsseln. Was er dabei jedoch nicht bedacht hatte: Die Anzahl der Wiederholungen wurde nicht mitgespeichert. Ohne diese ist es aber bis dato nicht möglich gewesen, die Nachricht zu entschlüsseln. Nach langen Überlegungen, einem DIN A2 Blatt mit Notizen kam endlich die rettende Idee: die Masterschleife. Diese machte es erstmals unnötig sich die Anzahl der Wiederholungen zu merken; sie konnten aus der verschlüsselten Datei wiederhergestellt werden.
Was ist "die Masterschleife"?
Der Grundgedanke der Masterschleife ist es, die Wiederholungen aus einem verschlüsselten Text zu ermitteln.
Var
mgl : array [2..2550] of boolean; --> In mgl[i] wird gespeichert, ob I Wiederholungen möglich sind.
signallänge : array [2..2550] of integer; --> In singallänge[i] wird die Länge eines Signals bei I
Wiederholungen gespeichert.
fehler : array[2..2550] of integer; --> Die auftretenden Fehler jeder Wiederholung
for I := 2 to 2550 do (1) if länge mod i = 0 then mgl[i] := true else mgl[i]:= false;
(1) Hierzu wird zuerst versucht alle Möglichkeiten der Wiederholungen (bis zu 2550) zu ermitteln. Die Anzahl der Signale (Buchstaben, Lehrzeichen [...]) muss ganzzahlig durch die Wiederholung teilbar sein. Hier können bereits in einer Vorschleife die meisten Wiederholungen ausgeschlossen werden.
//Anfang der Masterschleife
for I := 2 to 2550 do (A)
if mgl[i]= true then
begin
for k := 1 to signallänge[i] do
begin
übergabetext:=;
for j := 0 to i - 1 do (B)
begin
übergabetext:= übergabetext + eingabetext[k+j*(Signallänge[i])]; (2)
end;
richtig := entschlüsseln(übergabetext, length(übergabetext)); (3)
for j := 1 to length(übergabetext) do
begin
if übergabetext[j]=richtig then (4)
else fehler[i] := fehler[i] +1;
end;
end;
end;
// Ende der Masterschleife
(2) Zuerst wird in der Masterschleife der Übergabetext ermittelt. Dieser enthält alle n-ten Buchstaben jeder Wiederholung. Dies wird durch die Kombination von zwei Schleifen erreicht.
(3) Nun wird der häufigste Buchstabe des Übergabetextes gesucht. "entschlüsseln" funktioniert im wesentlichen wie bei Aufgabe 2.
(4) Weicht nun ein Buchstabe im Übergabetext von dem häufigsten Buchstaben ab, so wird dieser als Fehler im Array "fehler" gezählt.
(B) Nun wird die Schleife für den n+1 - ten Buchstaben durchlaufen, und zwar solange, bis die Schleife den letzten Buchstaben erreicht hat.
(A) Zuletzt wird die Schleife für die n+1 Wiederholung durchlaufen. Solange bis 2550 Wiederholungen durchlaufen wurden. Beachte: Die Schleife wird nur durchlaufen, wenn die Wiederholungen möglich sind.
Erklärungen zur Masterschleife
In der Entwicklung der Masterschleife habe ich zu Beginn nur die ersten Buchstaben jeder Wiederholung ermittelt und diesen anschließend in einem String gespeichert. Nun habe ich den am häufigsten vorkommenden Buchstaben bestimmt und anschließend die Fehler (d.h. alle anderen als den häufigsten Buchstaben) in einem Array gespeichert. Anschließend habe ich den kleinsten Wert des Arrays gesucht und die dazu entsprechenden Wiederholungen ausgegeben.
Dabei ist das Problem aufgetreten, dass bei 2 Wiederholungen der maximale Fehler bei 2 liegt (da nur 2 Buchstaben überprüft werden) und somit meistens 2 Wiederholungen als Lösung ausgegeben werden. Deshalb habe ich das Programm so erweitert, dass alle Buchstaben eines Signals mit denen der anderen Wiederholungen verglichen werden. Eine weitere Verbesserung brachte der Übergang von den Fehlern zur Fehlerwahrscheinlichkeit.
fehlerp[i]:= fehler[i] / (length(eingabetext)- signallänge[i]);
Der Vorteil liegt darin, dass wenige Wiederholungen nicht so stark berücksichtigt werden, da sonst bei diesen der maximale Fehler bei einer halben Gesamtsignallänge (eine Wiederholung ist maximal falsch) liegt.
Zuletzt wird nur noch die geringste Fehlerwahrscheinlichkeit gesucht und die entsprechenden Werte ausgegeben.
for I := 2 to 255 do
begin
if mgl[i] = true then
begin
if fehlerp[i] <= minfehler then
begin
minfehler:= fehlerp[i];
wiederholungen:= i;
end;
end;
end;
Ausgabefehler:= round(fehlerp[wiederholungen]*100) ;
memo2.lines.add(inttostr(wiederholungen)+ ' Wiederholungen');
Ein Problem
Bei stark verrauschten Nachrichten und vielen Wiederholungen kann es passieren, dass die Masterschleife eine Lösung findet, deren Fehlerwahrscheinlichkeit unterhalb der Fehlerwahrscheinlichkeit der Lösung liegt. Deshalb ist es sinnvoll auch die zweit - und drittwahrscheinlichste Lösung auszugeben.
Dies spricht dafür, dass die Masterschleife meinen Lösungsansatz zum Bestimmen der Wiederholungen komplett erfüllt, und dass weiterhin hier seine Grenzen liegen.
Weitere denkbare Erweiterungen
Anstelle beim Verrauschen Signale zu ersetzen, könnte man diese komplett löschen. Dies würde die Entschlüsselung erheblich erschweren. Man müsste nach Regelmäßigkeiten des verrauschten Signals suchen. Ein Ansatz könnte eine erweiterte Masterschleife bieten.
Da jedoch meine Zeit begrenzt ist, konnte ich diesen Ansatz nicht umsetzen...
Download
Programme und Dateien entfernt
