Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.

Informationstheorie: Den Zufall bezwingen

Dank hochdimensionaler Graphen ist es einem Forscherteam gelungen, einen lang gesuchten Code zu entwickeln. Dieser gibt sofort preis, ob eine Nachricht bei der Übertragung durch Rauschen beschädigt wurde.
Nachdenklicher Mann abgebildet mit digitalen Informationen

Angenommen, Sie möchten eine Nachricht übermitteln. Sie wandeln dafür jedes Zeichen in eine Folge von Bits um, die Sie in Form eines Signals über Kupferleitungen, Glasfaser oder Luft versenden. Doch egal wie sehr Sie sich bemühen, wird der Code, der auf der anderen Seite ankommt, nicht exakt mit den ursprünglichen Daten übereinstimmen. Durch Rauschen entstehen bei der Übermittlung zwangsweise Fehler.

In den 1940er Jahren haben sich Fachleute erstmals mit diesem Problem auseinandergesetzt. Fünf Jahrzehnte später kamen sie auf eine interessante Idee: Sie suchten nach einer Codierung, aus der sich sofort klar erkennen lässt, ob eine Nachricht verändert wurde – ohne dass der Empfänger sie vollständig lesen muss. Diese Eigenschaft nennen sie »lokale Testbarkeit«, denn man sollte die Unversehrtheit an nur wenigen Stellen extrem schnell prüfen können.

In den folgenden 30 Jahren gab es zwar erhebliche Fortschritte auf dem Gebiet, aber die Bemühungen blieben erfolglos – bis jetzt …

Von »Spektrum der Wissenschaft« übersetzte und bearbeitete Fassung des Artikels »Researchers Defeat Randomness to Create Ideal Code« aus »Quanta Magazine«, einem inhaltlich unabhängigen Magazin der Simons Foundation, die sich die Verbreitung von Forschungsergebnissen aus Mathematik und den Naturwissenschaften zum Ziel gesetzt hat.

Kennen Sie schon …

Spektrum Kompakt – Des Rätsels Lösung - Mathematische Beweise und ihre Entdecker

Korrekt oder nicht? Mathematische Beweise beruhen auf Annahmen und Schlussfolgerungen. Das klingt im Prinzip einfach, es dauert aber nicht selten Jahrzehnte oder länger, bis sie gefunden werden - wenn es überhaupt gelingt. Die Geschichten und die Menschen dahinter bieten oft spannende Geschichten.

Spektrum der Wissenschaft – Spezial 4/2003: Omega

Die Lösung des "Eternity puzzle" • Wer wird Millionär? • Graphentheorie • Im Reich der Terabytes • Ebene Schnitte aus Würfeln • Der Beweis der Catalan’schen Vermutung

Schreiben Sie uns!

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

  • Quellen

Dinur, I. et al.: Locally Testable Codes with constant rate, distance, and locality. ArXiv: 2111.04808, 2021

Tanner, R.: A recursive approach to low complexity codes. IEEE Transactions on Information Theory 27, 1981