Verschlüsselung
Quellen und Kanalkodierung
Interleaving
Sprachaktivitätserkennung
Faltungskodierer
Viterbi Algorithmus

Digitale Signalverarbeitung bei GSM

Subscriber Identity Module und Verschlüsselung

Eine Innovation des deutsche C-Netz schaffte es in den GSM-Standard. Auch hier trennte man die Teilnehmeridentität von dem Gerät. Dies geschah mit einer Chip Karte, die man bei GSM eine SIM-Karte nennt, ein Subscriber Identity Module. Die Chip Karte war jedoch nicht nur als einfacher Speicher für Daten gedacht, sondern enthielt auch einen Prozessor in dem Operationen durchgeführt werden konnten.

Der Prozessor schützt die Karte und die auf ihr enthaltenen Daten vor Missbrauch. Die Benutzung der SIM-Karte muss erstmal „freischalten“. Dies geschieht durch die Eingabe eines 4-stelligen „PIN“ Codes. (PIN = Personal Identification Number). Die SIM-Karte enthält nicht einfach nur die Rufnummer des Teilnehmers. Vielmehr enthält die SIM-Karte einen geheimen Schlüssel für Verschlüsselung von Nachrichten. Dieser Schlüssel ist nicht zugänglich und auch mit Gewalt ist er nicht lesbar. Man verwendet diesen Schlüssel nicht nur für den Schutz von Daten sondern auch für die Identifikation des Teilnehmers.

Zu Beginn der GSM Einführung war die SIM-Karte noch so groß wie eine Checkkarte. Erst später gab es für die Handgeräte kleinere SIM-Karten, die lediglich die Lesekontakte der SIM-Karte und den Chip enthielten.

Verschlüsselung

Die Übertragung von Information in digitaler Form lässt es zu, dass man diese einfach verschlüsseln kann. Im zweiten Weltkrieg war die Verschlüsselung von Sprachsignalen überhaupt die Triebfeder dafür, die Sprache zu digitalisieren, da sie dann einfach verschlüsselt werden kann. Allerdings fand man damals noch keine befriedigenden Lösungen.

Eine Verschlüsselung digitaler Daten geht einfach mit einem sogenannten „geheimen“ digitalen Schlüssel und einer einfachen XOR Funktion. Ein XOR vergleicht zwei binäre Werte. Sind beide Werte verschieden gibt es eine logische EINS als Ergebnis, sonst eine Null.

XOR	0	1
0	0	1
1	1	0

Hat man einen Schlüssel von 8 bit so kann man wie in der folgenden Tabelle digitale Informationen verschlüsseln. Wenn man keine Kenntnis des Schlüssels hat ist es praktisch unmöglich den Originaltext aus dem verschlüsselten Text zu gewinnen.

Verschlüsselung
Text	0	0	1	1	0	1	0	1
Schlüssel	1	1	1	0	0	0	1	1
	XOR
Verschlüsselter Text	1	1	0	1	0	1	1	0
Entschlüsselung
Verschlüsselter Text	1	1	0	1	0	1	1	0
Schlüssel	1	1	1	0	0	0	1	1
	XOR
Text	0	0	1	1	0	1	0	1

Im GSM-System liegt der Schlüssel nur an zwei Orten, einem zentralen nicht zugänglichen Speicher, dem sogenannte Authentication Center und auf der SIM-Karte. Die Schlüssel verlassen diese Orte nicht. Der Schlüssel wird mit Ki bezeichnet und ist 128 bit lang.

Um einen Mobilfunkteilnehmer authentifizieren zu können erzeugt man ein Zufallswort namens RAND. Dieses schickt man an das GSM Authentication Center und an die SIM-Karte. Auf der SIM-Karte läuft nun ein Verschlüsselungsalgorithmus, welcher aus dem Schlüssel Ki und RAND eine 32 bit lange Zahl SRES erzeugt. Das Gleiche geschieht im Authentication Center. Die SRES vergleicht man nun im Mobile Switching Center. Sind die Resultate gleich ist sichergestellt, dass dieselben Schlüssel verwendet wurden und der Teilnehmer ist authentifiziert, ohne dass er seinen Schlüssel preisgegeben hat.

Der Schlüssel kommt auch für die Verschlüsselung von Nachrichten zum Einsatz, jedoch nur indirekt. Die Verschlüsselung muss praktisch „öffentlich“ im Signalprozessor (DSP) des Mobiltelefons oder der Basisstation geschehen. Der Schlüssel darf aber seinen Ort nicht verlassen. Daher gibt es einen weiteren Algorithmus, A8, welcher in der SIM-Karte aus einer Zufallszahl und dem Schlüssel Ki einen temporären Schlüssel Kc erzeugt. Diesen verwendet man dann, um den Strom von Informationsbits mit einem A5 genannten Algorithmus zu verschlüsseln.

Quellen und Kanalkodierung

Sprachkodierung wurde bereits unter Signalverarbeitung besprochen. Für die Kodierung benutzt man stets Sprachrahmen von 160 Abtastwerten entsprechend 20 ms. Auch bei dem ersten GSM Sprachkodierer, dem Full Rate Codec, macht man eine LPC-Analyse um Vokaltraktparameter zu bestimmen. Diese sind für die Verständlichkeit der Sprache von größter Bedeutung und auch einfach darzustellen. 36 bit sind ausreichend. Der zweite Parametersatz ist die Periodizität. Hier schätzt man ein Filter, welches aus alten Daten, aktuelle Daten schätzen kann. Auch diese Daten werden mit nur 36 bit kodiert. Es verbleibt ein sogenanntes Restsignal. In diesem Restsignal kodiert man nur jeden dritten Abtastwert. Dennoch ist der erzeugte hörbare Fehler relativ gering. Die Restsignalkodierung benötigt 188 bit. Insgesamt hat der Sprachkodec somit eine Bitrate von 260 bit pro 20 ms also 13 kbit/s. Dies ist gegenüber den 64 kbit/s von PCM eine Reduzierung um einen Faktor von fast fünf.

Die „Rohbits“ muss man nun noch durch Kanalkodierung vor Übertragungsfehlern schützen. Vor allen bei bits die die Vokaltraktparameter beschreiben sind Fehler fatal und führen zu starken Störungen. Die Informationsbits vom Sprachkodierer werden in drei Klassen eingeteilt. Die erste Klasse (Ia) mit 50 bits werden besonders geschützt. Sie beinhalteten nicht nur Informationsbits, sondern auch drei Checkbits aus denen man ermitteln kann das trotz Fehlerkorrektur immer noch Fehler vorhanden sind. Ist dies der Fall, ist es besser Parameter (wie Vokaltraktparameter) zu wiederholen als Fehler zuzulassen. Weitere 132 bits von Class (Ib) werden nicht zusätzlich geschützt und gehen mit den geschützten bits von Ia in einen Faltungskodierer. Dieser erzeugt aus 189 Eingangsbits 378 Faltungscodierte bits. Faltungskodierer sind weiter unten beschrieben. Sie sind einfach zu realisieren. Die verbleibenden 78 bits vom Restsignal werden überhaupt nicht kodiert, sondern ungeschützt übertragen. Als Resultat ergeben sich 456 bits, ausreichend für 4 Zeitschlitze.

Interleaving

Wenn man Übertragungsfehler bei Funübertragung untersucht, stellt man fest, dass diese nicht einfach zufällig verteilt sind, sondern unter Umständen mehrere bits hintereinander betreffen. Solche Fehler lassen sich dann auch nicht mit Faltungscodes korrigieren. Aus diesem Grunde verteilt man benachbarte Informationsbits auf acht Zeitschlitze. Das erste von den 465 bits kommt in Zeitschlitz 1 das zweite in Zeitschlitz 2 das dritte in Zeitschlitz 3 bis schließlich das achte bit in den Zeitschlitz 8 kommt. Danach kommt das 9. bit wieder in Zeitschlitz 1 und so weiter. Diesen Vorgang nennt man interleaving oder verschachteln. Beim Empfang muss vor der Verarbeitung alles deinterleaved werden. Wenn etwa nun bis zu acht bits nebeneinander gestört wurden, so werden daraus 8 einzelne Fehler die man vermutlich mit dem Kanaldekodierer korrigieren kann.

Sprachaktivitätserkennung

In einer normalen Konversation spricht eine Person, während die andere Person zuhört. Es wäre daher von Vorteil, dass man in dem Fall, dass man schweigt, auch nicht sendet. GSM sieht eine solche Aktivitätserkennung vor. Bestimmte Merkmale bei der Sprachanalyse sind dazu geeignet, um zu bestimmen ob gesprochen oder geschwiegen wird. Wird geschwiegen, so wird dies dem Netzwerk mitgeteilt und in dem entsprechenden Traffic Channel wird nicht gesendet. Der Kanal wird zwar nicht für andere Nutzer freigegeben, aber es wird in dem betroffenen Zeitschlitz nicht gesendet. Dadurch verringert sich eine mögliche Interferenz mit Nachbarkanälen.

Nun ist es jedoch sehr störend, wenn der Sprachkanal in dieser Zeit quasi „stumm“ ist. Der sprechende Teilnehmer würde sofort wahrnehmen, dass sein „Gegenüber“ nicht mehr da ist. Dies liegt daran, dass man fast immer Hintergrundgeräusche hört. Aus diesem Grunde wird das Hintergrundgeräusch von der Signalverarbeitung ständig geschätzt und mit wenigen bits kodiert. Wenn man nun eine Verbindung wegen fehlender Sprachaktivität stoppt, so wird kurz der Code des Rauschens übertragen. Damit erzeugt man beim Empfänger ein künstliches Rauschen und gaukelt somit eine bestehende Verbindung vor.

Faltungskodierer

Bei GSM kommen wie oben gezeigt Faltungskodierer zum Einsatz. Ein Faltungskodierer erzeugt aus einer Informationssequenz durch „Faltung“ eine Ausgangssequenz die höher ist als die Originalsequenz, somit also Redundanz enthält. Im Folgenden beschreiben wir ein Beispiel wie durch einen Algorithmus aus jeweils drei Eingangswerten, zwei Ausgangswerte entstehen.

Wie in der Abbildung erzeugt man aus einem eingehenden Wert u(i) und zwei gespeicherten Eingangswerte, jeweils zwei Ausgangswerte x1(i) und x2(i). Dadurch wird die Anzahl an bits verdoppelt. Am Anfang sind die „Speicherwerte“ Null. Somit ist das erste Paar von x entweder 11 (wenn u(1) = 1 ist oder 00, wenn u(1) = 0 ist. Die Werte werden mit einem AND verknüpft. Der Faltungskodierer kann 4 verschiedene Zustände haben: 00,01,10 und 11. Er kann aber nicht von einem beliebigen Zustand in einen anderen beliebigen Zustand übergehen. Es gibt immer nur zwei Übergänge.

Die obige Abbildung zeigt die Zustände und die möglichen Übergänge. Es entsteht ein Diagramm welches an einen Spaliergitter (engl. Trellis) erinnert. Deshalb bezeichnet man es als Trellis Diagramm. Kodiert man eine Folge von Informationsbits entspricht dies „einem Weg“ durch ein solches Trellis Diagramm. Ein solcher Pfad beginnt immer im Zustand 00 und endet auch mit 00 indem man dem letzten Informationsbits zwei Nullen anhängt.

Die folgende Abbildung zeigt einen solchen Pfad für eine gegebene bitfolge
1 1 0 1 0

In der obigen Abbildung ist nur der wirkliche Trellispfad gezeigt. Es gibt aber viel mehr möglich Pfade durch ein Trellisdiagramm. Die möglichen Pfade sind jedoch mit den zu empfangenden bits zu vergleichen. In unserem Fall 11 01 01 00 10 11 00. Jeder Schritt durch den Pfad entspricht nun auch einem bitpaar. Dieses ist mit dem empfangenen bitpaar zu vergleichen. Dazu nimmt man den Hemmingabstand, der die bits vergleicht. Sind die bits gleich ist der Abstand null. Unterscheidet sich ein bit so ist der Abstand 1 und sind beide bits unterschiedlich so ist der Abstand 2. Man misst nun (theoretisch) für alle Trellispfade den gesamten Hammingabstand (Summation über alle Schritte). Der Pfad mit dem kleinsten Abstand ist der richtige Pfad. Wenn keine Übertragungsfehler auftreten ist der Hammingabstand Null wie oben gezeigt. Was passiert aber wenn ein Übertragungsfehler auftritt?

Die obige Abbildung zeigt mögliche Pfade, wenn beim zweiten übertragenen Paar ein Fehler auftritt. Nun tritt auch im „korrekten Pfad“ ein Abstand von eins auf. Der gesamte Pfad hat also einen Abstand von eins. Potentiell könnte es noch einen (oder mehrere) weitere Pfade geben. Gezeigt ist ein Pfad, der im zweiten Schritt ebenfalls einen Abstand von eins aufweist. Im weiteren Verlauf kommen jedoch Fehler bzw. Hammingabstände hinzu, so dass der gesamte Pfad einen Abstand von vier aufweist und somit ausscheidet.

Diese Abbildung zeigt den korrekten und einen alternativen Pfad bei zwei Übertragungsfehlern. Der korrekte Pfad hat einen Hammingabstand von 2, ein möglicher Alternativpfad hat in diesem Beispiel den Hammingabstand 4.

In den gezeigten Beispielen haben wir nur wenige bits kodiert. Bei realistischen Anwendungen wie GSM sind die Informationsfolgen jedoch 189 bit lang. Dadurch entstehen natürlich eine gewaltig hohe Anzahl von Pfaden welche man nicht einfach alle ausprobiert kann um den optimalen Pfad zu finden. Deshalb verwendet man zur Dekodierung einen besonderen Algorithmus, den Viterbi Algorithmus.

Viterbi Algorithmus

Der Viterbi Algorithmus ist in der obigen Abbildung gezeigt. Jeder Zustandsübergang zusammen mit dem jeweils empfangenen bitpaar führt zu einem Hammingabstand. Im Beispiel ist das beim ersten Übergang 2 und 0. Die entsprechenden Zustände zu diesem Zeitpunkt erhalten den akkumulierten Hammingabstand. In diesem Fall 2 und 0. Nun beginnen die nächsten möglichen Übergänge mit den entsprechenden Hammbingabständen. Die akkumulierten Abstände sind nun 2, 4, 1 und 1 (weil in diesem Übergang ein Fehler war. Bei dem nächsten Übergang, bei dem der Trellis eingeschwungen ist gibt es für jeden Zustand zwei Pfade. Der Zustand bekommt nun den Hammingabstand der von beiden Pfaden der kleiner ist. Man merkt sich aus welcher Richtung dieser gekommen ist. Auf diese Art und Weise sind die Abstände 2, 2, 1, 3.

So geht es weiter durch den Trellis. Am Ende steht der Hammingabstand des optimalen Pfades im Zustand 00. Nun macht man ein „Backtracking“. Man hatte sich ja gemerkt, woher der optimale Pfad kam und kann nun rückwärts den Pfad zurückverfolgen und dadurch die fehlerkorrigierte Informationsbitfolge gewinnen.