14321 Sekunde a 100 Samples Baustelle
DCF-Codierschema

Diese Seite beschreibt Überlegungen zur Implementierung eines DCF-Empängers in Software. Falls Du noch nicht mit dem Aufbau des DCF-Signals vertraut bist, findest Du Erklärungen und hilfreiche Texte auf den folgenden Seiten:

Das deutsche Funkuhr-Signal DCF77 wird amplituden­moduliert mit einer Träger­frequenz von 77.5 kHz von Mainflingen bei Franfurt/Main ausgestrahlt. Die Übertra­gungsrate beträgt ein Bit pro Sekunde.

Durch Absenkung des Trägers für 100ms zum Sekundenanfang wird eine Null — im folgenden mit B0 bezeichnet — übertragen. Analog wird eine Eins, also B1, durch eine Absenkung von 200ms Dauer codiert. Auf diese Weise werden jede Minute 59 Bit übermittelt, die unter anderem die Zeitinformation für die folgende Minute im BCD-Format enthalten. In der 60-ten Sekunde wird der Träger nicht abgesenkt, bezeichnet als BM oder #. Die Marke BM dient als Kennung der Minuten­enden, das heißt mit dem Ende von BM und dem Anfang des nächsten Bits beginnt die Minute, deren Zeit­information soeben übertragen wurde.

Zu diesen drei Werten kommt aus Sicht eines Empfängers noch ein vierter Wert hinzu: B?. Er steht für einen nicht zuortenbaren Wert, der bei schlechter Empfangslage auftreten kann.

Strategie

Die Strategie eines einfachen DCF-Decoders ist simpel: Es werden solange Bits empfangen bis eine Minute komplett ist. Dann werden die Daten decodiert. Weicht ein Bit weiter als eine vorge­gebene Maximal­toleranz vom DCF-Format ab, dann beginnt man einfach von vorne mit dem Einsammeln der Bits.

Mit dieser Strategie dauert ein Zeitabgleich bei guter Empfangs­lage nur wenige Minuten; ist das Signal jedoch gestört, dann ist ein Zeitab­gleich sehr unwahr­scheinlich: Gehen wir davon aus, dass zur Dekodierung 65 Bits in Folge korrekt empfangen werden müssen und die Wahr­schein­lichkeit für ein korrekt empfangenes Bit bei 90% liegt, dann liefert ein naives Wahr­schein­lich­keits­modell eine zu erwartende Zeit von rund 16 Stunden (0.9−65 Minuten), bis ein Abgleich erfolg­reich ist. Sollen sogar zwei Minuten in Folge fehler­frei empfangen werden, um die Daten der beiden Minuten gegen­einander zu testen, dann erhöht sich die erwartete Zeit auf ein Jahr, nämlich auf 0.9−125 Minuten.

Die Wahrscheinlichkeit, dass bei zwei aufeinander folgenden Minuten ein bestimmtes Bit nicht empfangen wurde liegt bei 1−0.9·0.9 = 1%. Könnten wir nicht­bekannte Bits von der vorherigen Minute über­nehmen, ergäbe sich eine Wahr­schein­lichkeit von 0.9965 ≈ 0.52 dafür, dass wir alle Bits zusammen haben. Sollen zwei aufeinander folgende dieser 2-Minuten-Einheiten für einen Integritäts­test verwendet werden, dann brauch man 4 dieser 2-Minuten-Einheiten. Die Empfangs­dauer von einem Jahr reduziert sich daher mit der Fehlerkorrektur auf rund 10 Minuten.

Auch wenn das Wahrscheinlichkeitsmodell stark vereinfacht — Übertragungs­fehler sind unabhängig vonein­ander und es besteht Minuten-Synchronität — zeigt die Betrach­tung das Potential einer Fehler­korrektur.

Die Probleme einer Fehlerkorrektur sind erhöhter Resourcen-Bedarf an Daten- und Programm­speicher, Laufzeit, Hirnschmalz und Entwick­lungs­zeit. Hinzu kommt die Möglichkeit der Fehler­aus­breitung bei Kuckuksei-Bits. Daher müssen sämtliche Möglich­keiten der Fehler-Erkennung genutzt werden, um die Wahr­schein­lichkeit falsch empfangener Daten zu minimieren, das heißt praktisch auszu­schließen.

Zur Fehler-Erkennung und -Vermeidung bieten sich viele nahe­liegende Wege, die im folgenden Abschnitt kurz und kommen­tarlos zusammen­gefasst werden.

Fehler-Vermeidung

Die Empfangsbedingungen können das Signal abschwächen/stören und damit zu Bitfehlern oder nicht zu identi­fi­zierten Bits B? beitragen.

  • Monitore und Rechner
  • Schaltnetzteile etc.
  • Metallteile und Stahlbeton
  • mangelhafte Antennenausrichtung
  • zu große Toleranzen für die Bitlängen in der Software

In simpler DCF-Software werden üblicherweise Intervalle für die Bitlängen imple­mentiert, zum Beispiel 90ms–110ms für B0. Bei schlechter Empfangs­lage ist es nicht ratsam, diese Toleranz – welche im übrigen schon eine Art der Fehler­korrektur darstellt – zu groß zu wählen. Das ist zwar verlockend, weil die Längen der Signale bei schlechtem Empfang in weiteren Grenzen variieren, es erhöht aber die Wahr­schein­lichkeit von Bit­fehlern. Es ist wesentlich unkriti­scher, für ein Bit den Wert B? einzutragen, als schwer erkennbare Bitfehler zu riskieren.

Im allgemeinen kann gesagt werden, dass bei schlechtem Empfang die Bit­längen kleiner erscheinen als vom Sender ausgesandt, was wohl auf atmosphä­rische Störungen zurück­zu­führen ist. Durch die Störung wird auch bei abgesenktem Signal etwas empfangen. Daher wird öfter fälschlicherweise B0 anstatt B1 erkannt als umgekehrt. Analog wird öfter BM anstatt B0 erkannt als umgekehrt.

Erschwerend kommt hinzu, dass viele DCF-Empfänger einen AGC (Automatic Gain Control) zum Pegel­angleich an die Signal­stärke besitzen, der das Signal ebenvalls verziehen kann.

Fehler-Erkennung

Bit-Integrität
  1. Der Abstand (in einer noch festzulegenden Metrik) zu einem der Bits B0, B1, BM ist hinreichend klein
Protokoll-Integrität
  1. Die Minuten-Marken sind im richtigen Abstand
  2. Bit 0 ist Null und Bit 20 ist Eins
  3. Zwei aufeinanderfolgende Minuten sind nie beide gerade oder beide ungerade
Daten-Integrität
  1. Die empfangenen Zeitwerte für Minute, Stunde, etc sind im BCD-Format
  2. Die Zeitwerte liegen in den erlaubten Bereichen; die Minuten zum Beispiel im Intervall von 0 bis 59
  3. Die Paritätsprüfung ist OK
  4. Es ist nicht gleichzeitig Sommer- und Winterzeit
  5. Es gibt keinen Widerspruch zu den Daten der vorhergehenden Minute(n)/Decodierung(en)

Synchronisation

Sekunden-Sync

Bei verrauschtem Signal variieren sowohl die Sekunden-Anfänge als auch ihre Längen. Zudem gibt es hin und wieder Spikes auf dem Signal. Daher kann es mit einem klassischen Empfänger schwierig sein, den Sekunden­anfang zu detek­tieren und auch bei Störungen nachzu­ver­folgen.

Als praktikabel erweist sich die Berechnung der zyklischen Faltung mittels Haar-Wavelets wie in der Animation rechts verdeut­licht. Zyklische Faltung mit einem Haar-Wavelet Zunächst sei angemerkt, dass die Faltungen auch mit begrenzten Resourcen, wie sie typischer­weise auf Mikro­con­trollern vorherr­schen, gut berechnet werden können.

Im Bild ist ein schwarz-weißer Kreisring zu sehen, der eine Sekunde darstellt und aus 100 Stücken besteht; jedes Stückchen stellt einen Zeitraum von 10ms dar und ist einge­färbt anhand des vom DCF-Empfänger abge­fragten Wertes: Weiß für abgesenkten Träger und Schwarz für vollen Träger. Rechts im Bild wurde wohl für 200ms (1/5 des Kreises) der Träger abgesenkt, was einem B1 entspricht. Hinzu kommen einige Spikes.

Rot unterlegt ist ein 200ms breites Haar-Wavelet, mit dem gefaltet wird. Werden pro Sekunde N Samples abgefragt und hat das Wavelet die Breite w, werden für j = 0..N−1 die Summen

     S_{w,j} = \sum_{i=0}^{w-1} s_{i+j}

berechnet. Indizes sind dabei immer modulo N zu nehmen. In der Animation ist dieser Wert in Grün unterlegt. Ist ein Wert berechnet, können die Folgewerte effizient über die Beziehung

     S_{w,j+1} - S_{w,j}= s_{w+j} -s_j

erhalten werden. Damit sind nicht mehr N·w Schleifendurchläufe pro Sekunde und Wavelet nötig, sondern lediglich N+w. Außerdem müssen die Werte nicht gespeichert werden; es genügt, das Maximum und dessen Position zu kennen:

     M_w = \max_j  \{S_{w,j}\}

     j_w = \min_j  \{j  |  M_w = S_{w,j}\}

Bis zur Sekunden-Synchronisation werden diese Faltungen berechnet. Wird ein Bit als B0 oder B1 kategorisiert, dann geht es in die Berechnung des Sekunden-Anfanges ein. Hierzu werden alle Samples der "guten" Sekunden aufsummiert – im Endeffekt also gemittelt – und nach einigen Sekunden die Faltungen über diese Summen berechnet. Liegen Positionen der Maxima für M100ms und M200ms hinreichend dicht zusammen, dann ist dies der Anfang der Sekunde.

Nach erfolgtem Sekunden-Abgleich gehen die guten Bits weiterhin in die Bestimmung des Sekunden-Anfanges ein. Zur Unterscheidung, ob es sich bei einem empfangenen Wert um B0, B1, BM oder B? handelt, muss nur noch an der Position des Sekunden-Anfangs gefaltet werden. Der Sekunden-Anfang muss ständig nachgeregelt werden, weil er sich durch Änderung der Empfangslage etwas verschieben kann und durch Ungenauigkeit der internen Zeitbasis (i.d.R ein Schwingquarz) wegzulaufen scheint.

Minuten-Sync

Fehlerkorrektur

Das Zeitsignal besteht aus mehreren Ziffern, welche alle binär übertragen werden. Von einer Minute zur nächsten gibt es drei Möglichkeiten, wie sich eine solche Ziffer ändern kann:

  1. Die Ziffer bleibt unvervändert
  2. Die Ziffer wird um Eins erhöht
  3. Die Ziffer wird von ihrem Maximalwert auf ihren Minimalwert zurückgesetzt (Reset)

Ziffern in diesem Sinne sind zum Beispiel:

  • Einer der Minute/Stunde (min=0, max=9)
  • Zehner der Minute/Stunde (min=0, max=5)
  • Wochentag (min=1, max=7)

Die Minute selbst ist nicht als Ziffer anzusehen, weil es von Minute 9 zu Minute 10 aufgrund der BCD-Codierung eine Erhöhung des Wertes von 9 auf 16 (916 auf 1016) gibt; ähnliches gilt für Stunde, Tag, Monat, und Jahr.

Kann ein Reset der Ziffer ausgeschlossen werden, dann ergeben sich aus den Übergängen eines ihrer Bits folgende Schlussfolgerungen, denn eine Ziffer wird maximal um 1 erhöht:

  • 0→0: alle höherwertigen Bits bleiben unverändert
  • 0→1: alle höherwertigen Bits bleiben unverändert
  • 1→1: alle höherwertigen Bits bleiben unverändert

Dabei ist die Wertigkeit der Parity-Bits von der Größenordnung wie das LSB der Werte, für die es codiert. Das Minuten-Parity hat also die Wertigkeit von Bit Minute.0.

Hieran ist folgendes zu erkennen:

  • Fehlerkorrektur ist auf Bit-Ebene möglich, und Fehler pflanzen sich mit dieser Methode nicht auf benachbarte Bits fort.
  • Die Fehlerkorrektur sollte nach Möglichkeit bei den niederwertigsten Bits beginnen. Kann aufgrund der Werte eine Fehlerkorrektur erst später – etwa beim Monat – beginnen, können nicht mehr viele Bits korrigiert werden. Daher werden zur Entscheidung, ob eine Fehlerkorrektur möglich ist, nur die Minuten-Bits verwendet. Höhere Bits in die Entscheidung einzubeziehen bringt mehr Aufwand, jedoch kaum weiteren Gewinn.
  • Reset-Wert von Minuten-Einer und -Zehner ist 0; wird also eine 1 in den Minuten-Bits empfangen, dann gab es von der vorhergehenden auf die aktuelle Minute keinen Reset, daher können dann alle höheren Bits korrigiert werden.

Ein besonders einfacher Spezialfall sind die ungeraden Minuten, d.h. Minuten, für die gilt Minute.0 = 1. Dieser Fall ist sehr einfach zu testen und liegt jede zweite Minute vor: Alle höherwertigen Bits dürfen kopiert werden. Das Minuten-Parity muss wechseln. Der Wechsel von Minute.0 geschieht in jeder Minute, unabhängig von Sommer- und Winterzeit und von Schaltjahren und -sekunden. Der Wechsel von Minute.0 kann sogar zur Minuten-Synchronisation verwendet werden, weil kein anderes Bit diese Eigenschaft hat, und daher sind sogar Bitfehler in Minute.0 erkennbar bzw. selbst wenn Minute.0 als B? empfangen wurde, ist dessen Wert bekannt. Die Fehlerkorrektur beruht in diesem Fall also auch nie auf einer falschen Grundlage wie zum Beispiel einem Fehlerbit (einer 0/1-Verwechslung).

Fehlerkorrektur: Ein Beispiel

Unten folgen zwei Bilder der fehlerkorriegerte Daten des schwarz-weissen Spaghetti-Bildes links. Jeder Pixel des linken Bildes stellt 10ms dar: Abgesekter Träger ist in Weiß codiert, nicht-abgesenkter Träger in Schwarz. Jede Zeile repräsentiert eine Sekunde empfangener Daten und ist somit 100 Pixel breit. Die Gesamtdauer des Streifens ist 14231 Sekunden, also knapp 4 Stunden.

Du kannst die PNG-Datei verwenden, um Deinen eigenen Fehler-Korrektur-Ansatz zu testen. Speichere dazu das Bild auf Deinem Rechner und wandle es mit einem Grafik-Progamm in das PBM-Format um. Das geht zum Beipiel mit convert:

   convert -compress None dcf-10ms-pulses.png dcf-10ms-pulses.pbm

Das erzeugt die PBM-Datei, also einfachen Text. Die Datei sieht so aus (Schwarz=1 und Weiß=0), und damit kannst Du Dein Programm füttern:

   P1
   100 14231
   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
   0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
   ...

Folgende Bilder zeigen fehlerkorrigierte DCF-Daten. Jede Zeile enthält eine Minute, also 60 farbcodierte Sekunden:

   SchwarzB0Null
   WeißB1Eins
   BlauBMMinutenmarke
   GrünB?Unbekannt
   RotB0 ↔ B1 Ein Kuckucksei: B0 statt B1 oder umgekehrt korrigiert zu B?
   BraunB1Beginn der Zeitinfo

Im linken Bildteil sind die Originaldaten, rechts die Daten nach Fehlerkorrektur. Die Blöcke sind getrennt durch einen hallblau hinterlegten Streifen von 3 Paritäts­bits für Minute, Stunde und Datum, welche sich auf den rechten, fehler­korrigierten Block beziehen.

   GrünB0Parity OK
   GelbB?Parity unbekannt
   RotB1Parity fehlerhaft

Zeilen mit 3 grünen Parity-Bits können also weiter­verarbeitet werden, indem zum Beispiel weitere Konsistenz­test zur Daten­integrität folgen. Daten-Tests 1) bis 3) von oben wurden in den Bildern schon durchge­führt, Daten-Tests 4) und 5) noch nicht.


Verfahren: Z-Parity (Z0)
Hier wird als Grundlage nur Bit 0 der Minute verwendet. In geraden Minuten geschieht keine Fehler­korrektur oder -erkennung. In den ungeraden Minuten können unbe­kannte Bits aus der vorherigen, geraden Minute über­nommen werden bzw. die Bits der beiden Minuten gegen­ein­ander getestet werden: alle Bits ab Minute.1 müssen gleich geblieben sein, und das Minuten-Parity muss wechseln. Es kann also auch geprüft werden, ob das Minuten-Parity richtig übertragen wurde!

Fehlerkorrigierte DCF-Daten, Bit 21

Anmerkung:
Die blaue Minuten-Marke im linken Block zeigt nicht die Empfangslage, sondern ergibt sich aus der Minuten-Synchronisation. Auch der Beginn der Zeit-Information (Bit 20 in Braun und Bit 21) im rechten Teilbild wurden so erhalten und sind deshalb selbst bei stark gestörtem Signal bekannt.

Verfahren: Z0–6
Hier dienen alle Bits der Minute als Entscheidungsgrundlage: Falls ein Bit der momentanen Minute vom Minimalwert 0 abweicht, oder ein Bit der vorher­gehenden Minute vom Maximal­wert 5916 abweicht, dann muss für alle höherwertigen Bits dieser beiden Minuten Gleichheit herrschen. Wie man sieht, gibt es hier deutlich mehr brauchbare Daten. Im unteren Bildteil gibt es viele komplett nutzbare Daten­sätze – erkennbar an einem zu der Minute gehörenden grünen Mittel­balken – und es wurden mehr Übertra­gungs­fehler erkannt und korrigiert.

Bei Stunden­wechseln ist eine Fehler­korrektur aufgrund des Minuten-Resets nicht mehr möglich; es können also keine Bits aus der Vorminute über­nommen werden. Daher dauert es einige Zeit, bis wieder alle Bits aufge­sammelt sind und die Zeit­infor­mation komplett ist.

Fehlerkorrigierte DCF-Daten, Bits 21-27