Thue-Morse-Bit

Die Thue-Morse-Folge ist die klassische überlappungsfreie binäre Folge, die entsteht, indem man jede nichtnegative ganze Zahl n nimmt und die Parität der Anzahl der Einsen in ihrer Binärdarstellung schreibt. Index null ist null (Binär null hat keine Einsen), Index eins ist eins, Index zwei ist eins, Index drei ist null, und so weiter, was den vertrauten Block 0, 1, 1, 0, 1, 0, 0, 1 ergibt. Studierende der Wortkombinatorik, Kodierungstheorie-Kurse und Forschung zu automatischen Folgen brauchen eine schnelle, deterministische Antwort für einen beliebigen sicheren Ganzzahlindex, ohne eigene Bit-Zähler zu schreiben.

Was die Thue-Morse-Folge ist

Die Thue-Morse-Folge ordnet jeder nichtnegativen ganzen Zahl eine 0 oder eine 1 zu. Dazu schreiben Sie die Zahl im Zweiersystem und zählen ihre Einsen. Ist diese Anzahl gerade, lautet das Glied 0, ist sie ungerade, lautet es 1. Die Stelle null hat keine Einsen und ergibt 0, die Stelle sieben ist 111 und ergibt 1. So entsteht der bekannte Anfang 0, 1, 1, 0, 1, 0, 0, 1. Die Folge enthält nie denselben Block dreimal hintereinander und gilt deshalb als Musterbeispiel einer Folge, die sich nicht periodisch wiederholt.

Einsatz und häufige Fehler

Sie begegnet Ihnen in der Kombinatorik auf Wörtern, in Kursen zur Codierungstheorie und in Vorführungen nichtperiodischer Bitfolgen. Lehrkräfte nutzen sie, um Aufgaben mit einer eindeutigen Antwort zu bewerten. Ein typischer Fehler ist, ab eins statt ab null zu zählen, wodurch jedes Glied um eine Stelle verrutscht. Ein zweiter betrifft negative Stellen: Sie gehören nicht zur üblichen Definition und werden abgelehnt, statt über die interne Darstellung negativer Zahlen im Rechner gedeutet zu werden. Verwechseln Sie die Folge auch nicht mit einem Prüfbit für eine beliebige Bitkette.

Was das Thue-Morse-Bit ist und warum popcount mod 2 es definiert

Die unendliche Thue-Morse-Folge t(0), t(1), t(2), … ist definiert durch t(n) gleich der Summe der Binärziffern von n modulo zwei. Äquivalent ist t(n) null, wenn n eine gerade Anzahl von Eins-Bits hat, und eins, wenn diese Anzahl ungerade ist. Diese Definition ist genau der Population-Count (popcount) von n modulo zwei, sodass zur Laufzeit kein rekursiver Morphismus und keine Papierfalt-Konstruktion nötig sind: wandeln Sie n in die Basis zwei um, zählen Sie die Einsen und nehmen Sie die Parität.

Die ersten sechzehn Terme veranschaulichen das Muster: für n von null bis fünfzehn sind die Bits 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0. Die Folge ist würfelfrei und überlappungsfrei, weshalb sie in der Wortkombinatorik, bei Konstruktionen automatischer Folgen und in einfachen Demos aperiodischer Binärstrings vorkommt. Weil die Abbildung nur von den binären Einsen einer einzigen nichtnegativen ganzen Zahl abhängt, ist die Antwort eindeutig, nebenwirkungsfrei und in jeder Sprache identisch, die Integer-popcount gleich umsetzt.

Negative Indizes liegen außerhalb der hier verwendeten Standarddefinition: die Folge wird durch die nichtnegativen ganzen Zahlen indiziert, daher wird ein negatives n abgelehnt statt in Zweierkomplement-Bitmuster gefaltet zu werden, die Erwartungen im Unterricht verwirren würden. Wenn Sie das Bit für einen konkreten Hausaufgabenwert brauchen — etwa n gleich sieben, binär eins-eins-eins, drei Einsen, Parität eins — liefert dieser Endpunkt jenes Bit zusammen mit der Zwischen-Binärzeichenkette und der Einsenzahl, damit Lernende die Parität Schritt für Schritt prüfen können.