Code-Quest

1948 war die Welt noch ein analoger Ort. Candid Camera und Ed Sullivan begannen gerade ihre langen TV-Läufe; Jack Bennys Radiosendung hatte zig Millionen Hörer. Aber schlechter Empfang war eine Tatsache des Lebens. Elektromagnetische Interferenzen, physische Hindernisse zwischen einem Sendemast und einem Empfänger und andere Quellen von Geräuschen, die Ingenieure nennen, störten routinemäßig Bennys Monologe oder die Auftritte von Sullivans Gästen. In den meisten Gegenden, zumindest bei einigen Sendern, fanden sich die Leute mit verschneiten Bildern oder statisch geplagtem Ton ab.



Claude Shannon, 1948

Im selben Jahr veröffentlichte jedoch Claude Shannon, SM '40, PhD '40, eine wegweisende Arbeit, in der er mathematisch bewies, dass es sogar bei viel Rauschen möglich ist, Informationen praktisch fehlerfrei zu übertragen. Es war eine analoge Welt, aber Shannons beeindruckende Schlussfolgerung war das Ergebnis seiner Fähigkeit, digital zu denken. Informationen in jedem Medium, argumentierte Shannon, könnten durch binäre Ziffern oder Bits dargestellt werden – ein Wort, das sein Aufsatz der Welt vorstellte. Während Rauschen in einem Kommunikationskanal die Bits verfälschen kann, erklärte er, wird es durch das Hinzufügen zusätzlicher Bits, die mit den ursprünglichen Bits durch einen bekannten Algorithmus in Beziehung stehen – einen fehlerkorrigierenden Code – möglich, die ursprüngliche Sequenz abzuleiten.



Je verrauschter der Kanal, desto mehr zusätzliche Informationen müssen hinzugefügt werden, um eine Fehlerkorrektur zu ermöglichen. Und je mehr zusätzliche Informationen enthalten sind, desto langsamer wird die Übertragung. Shannon zeigte, wie man die kleinste Anzahl zusätzlicher Bits berechnet, die einen minimalen Fehler garantiert – und damit die höchste Rate, mit der eine fehlerfreie Datenübertragung möglich ist. Aber er konnte nicht sagen, wie ein praktisches Codierungsschema aussehen könnte.



Forscher verbrachten 45 Jahre damit, nach einem zu suchen. Schließlich, im Jahr 1993, kündigten zwei französische Ingenieure eine Reihe von Codes – Turbo-Codes – an, die Datenraten nahe an Shannons theoretischer Grenze erreichten. Die erste Reaktion war Ungläubigkeit, aber die anschließende Untersuchung bestätigte die Behauptungen der Forscher. Es stellte sich auch eine noch verblüffendere Tatsache heraus: Codes, die genauso gut waren wie Turbo-Codes, die sogar auf demselben mathematischen Trick beruhten, wurden mehr als 30 Jahre zuvor in der MIT-Doktorarbeit von Robert Gallager, SM, vorgestellt. 57, ScD '60. Nach Jahrzehnten der Vernachlässigung haben Gallagers Codes endlich praktische Anwendung gefunden. Sie werden bei der Übertragung von Satellitenfernsehen und drahtlosen Daten verwendet, und Chips für deren Entschlüsselung finden sich in handelsüblichen Mobiltelefonen.

Die Geburt der Informationstheorie

Gallager kam 1956 ans MIT – im selben Jahr kehrte Shannon selbst nach 15 Jahren an den Bell Labs als Professor zurück. Aber es war nicht die Aussicht auf eine Zusammenarbeit mit Shannon, die ihn dazu veranlasste, das MIT dem Yale vorzuziehen, wo er sich auch für eine Graduiertenschule beworben hatte. Ich war in der Armee – in einem bedeutungslosen Auftrag – und ich habe es wirklich gehasst, was ich tat, sagt Gallager, der nach seiner Promotion mehr als 40 Jahre am MIT gelehrt hat und immer noch Doktoranden als emeritierter Professor im Forschungslabor von . berät Elektronik. MIT begann eine Woche früher als Yale. Und ich war so erpicht darauf, aus der Armee auszusteigen, dass dies mein einziger Grund war, zum MIT zu gehen.



Gallager war sich nicht einmal sicher, ob er Informationstheorie studieren wollte, die aufkeimende neue Disziplin, die aus Shannons Arbeit von 1948 hervorgegangen war. Aber bevor er zum Army Signal Corps kam, hatte auch Gallager mehrere Jahre bei Bell Labs gearbeitet, wo er drei Tage die Woche in einem Klassenzimmer verbrachte, um sich über die neuesten Fortschritte in der Elektrotechnik zu informieren. Obwohl er Shannon nie begegnet war, half ihm diese Erfahrung, den Umfang seiner Leistung zu erkennen. Ich habe ihn nur als eine Art Gott angesehen, sagt Gallager.

Als Shannon an die MIT-Fakultät kam, war er tatsächlich eine unbedeutende Berühmtheit. Bereits 1953 hatte ein Artikel über Informationstheorie in der Zeitschrift Fortune deklamiert: Es ist nicht übertrieben zu sagen, dass der Fortschritt des Menschen im Frieden und die Sicherheit im Krieg mehr von fruchtbaren Anwendungen der Informationstheorie abhängen als von physischen Demonstrationen, entweder in Bomben oder in Kraftwerken, dass Einsteins berühmte Gleichung funktioniert.

Was die öffentliche Vorstellungskraft beflügelte, war die Idee, dass Informationen in all ihrer Vielfalt – Text, Audio, Video – auf bloße Folgen von Einsen und Nullen reduziert werden könnten. Kommerzielle digitale Geräte gab es noch nicht, so dass es die Leute umgehauen hat, dass 001001010101000101011101 einen Teil einer Symphonie oder einen Teil eines Films oder eine Farbe oder eine Zeile aus einem Buch darstellen könnte. Aber wie Shannon in seiner Arbeit betonte, hatte sein Bell Labs-Kollege Ralph Hartley 20 Jahre zuvor einen ähnlichen Vorschlag gemacht. Der Aspekt des Papiers, der die Ingenieurskollegen von Shannon faszinierte und noch immer fasziniert, war die geniale Art und Weise, wie er bewies, dass es einen Code geben muss, der fehlerfreie Datenübertragungen bis zur Kapazität eines Kanals produzieren kann.



Um zu verstehen, wie ein fehlerkorrigierender Code funktioniert, stellen Sie sich jemanden vor, der versucht, eine Vier-Bit-Nachricht über einen verrauschten Kanal zu senden. Wenn das Rauschen dazu führt, dass eines der Bits in sein Gegenteil kippt, hat der Empfänger keine Möglichkeit zu wissen, dass ein Fehler aufgetreten ist. Das einfache Wiederholen der Nachricht, sodass aus 0011 00110011 wird, löst dieses Problem: Wenn nun ein Bit ins Gegenteil verkehrt wird, weiß der Empfänger, dass ein Fehler vorliegt, da die beiden Versionen der Nachricht nicht übereinstimmen. Aber es ist unmöglich zu sagen, welche richtig ist. Ein besserer Weg, die Nachricht zu codieren, könnte die vier zusätzlichen Bits verwenden, um Informationen über die Nachrichtenbits darzustellen: Das fünfte Bit könnte Ihnen beispielsweise sagen, ob die ersten beiden Bits der Nachricht dieselben oder unterschiedliche Werte haben; das sechste Bit könnte dasselbe für die Bits drei und vier tun, das siebte für die Bits eins und drei und das achte für die Bits zwei und vier. Wenn eines der ersten vier Bits umgedreht wird, können die letzten vier es identifizieren; Wenn eines der letzten vier Bits umgedreht wird, können die anderen drei möglicherweise genügend Informationen übermitteln, um dies auszugleichen.

Shannons Aufsatz vermeidet jedoch solche Grübeleien darüber, wie man tatsächlich Codes konstruiert. Stattdessen nähert es sich dem Konzept der Fehlerkorrektur durch statistische Analyse der allgemeinen Eigenschaften von Codes, die vollständig zufällig ausgewählt wurden. Um ein Gefühl für seinen Ansatz zu bekommen, könnte es hilfreich sein zu sehen, wie er auf unsere hypothetischen Acht-Bit-Sequenzen angewendet werden könnte, die Vier-Bit-Nachrichten codieren.

Es gibt 16 mögliche Vier-Bit-Nachrichten, und die Methode von Shannon würde jeder von ihnen eine eigene zufällig ausgewählte Acht-Bit-Seriennummer zuweisen – ihr Codewort. Der Empfänger hätte wie der Sender ein Codebuch, das die 16 möglichen Vier-Bit-Nachrichten mit den 16 zufälligen Acht-Bit-Codewörtern korreliert. Da es 256 mögliche Folgen von acht Bits gibt, gibt es 240, die nicht im Codebuch erscheinen. Jemand, der eine dieser 240 Sequenzen empfängt, weiß, dass sich ein Fehler in die Daten eingeschlichen hat. Aber solange sich die 16 erlaubten Codewörter genug voneinander unterscheiden, gibt es wahrscheinlich nur eines, das der beschädigten Sequenz am nächsten kommt. Wenn beispielsweise 00000001 und 11111110 beide gültige Codewörter sind, 00000011 jedoch nicht, dann kann jemand, der die Sequenz 00000011 empfängt, schlussfolgern, dass das beabsichtigte Codewort viel wahrscheinlicher war 00000001 als 11111110.



Im wirklichen Leben macht sich natürlich niemand Sorgen, Nachrichten mit nur vier Bit zu übertragen. Aber durch statistische Analysen konnte Shannon Rückschlüsse auf codierte Nachrichten jeder Länge ziehen, die über Kanäle mit beliebig viel Rauschen gesendet wurden. Insbesondere konnte er sowohl den Grad der Differenz zwischen zufällig ausgewählten Codewörtern als auch die Wahrscheinlichkeit, dass eine beschädigte Sequenz nur einem von ihnen ähnelt, rigoros quantifizieren. Während die Wahrscheinlichkeit, dass zwei 8-Bit-Sequenzen ähnlich sind, relativ hoch ist, zeigte Shannon, dass die Wahrscheinlichkeit einer Ähnlichkeit mit zunehmender Länge von Codewörtern exponentiell abnimmt. Tatsächlich war eines seiner verblüffendsten Ergebnisse, dass die meisten zufällig zugewiesenen Codewörter bei langen Nachrichten fast so unterschiedlich voneinander sind, wie es ihnen möglich ist. Das bedeutet, dass fast jedes Codierungsschema – jede Art und Weise, diese Wörter zu generieren – eine fehlerfreie Übertragung über einen verrauschten Kanal mit nahe der maximalen Rate ermöglichen würde.

Es brauchte viel Intuition, um zu glauben, dass ein vollkommen zufälliger Code im Durchschnitt ein ziemlich guter Code sein könnte, sagt David Forney, SM '63, ScD '65, ein ehemaliger Vizepräsident der Codex Corporation und Motorola, der 1996 zum MIT zurückkehrte als außerplanmäßiger Professor. Es stellt sich heraus, dass dies die Analyse drastisch vereinfacht, da Sie jetzt eine durchschnittliche Fallanalyse durchführen können. Forney hält einen Moment inne und fügt dann hinzu: Um nicht zu sagen, dass es ganz einfach war: Er musste zumindest ein paar Theoreme erfinden, wenn nicht sogar Zweige der Mathematik. Aber Gallager stimmt zu. Über Shannons Aufsatz aus dem Jahr 1948 sagt er: „Nachdem Sie ihn zwei Jahre lang studiert haben, scheint es sehr einfach zu sein. So viele Leute werden Ihnen sagen: „Es ist wirklich sehr einfach.“ Und wenn Sie es verstanden haben, ist es so.

Eine unwiderstehliche Herausforderung

Shannons mathematische Beschreibung von Informationen hatte viele Konsequenzen. Sein Aufsatz von 1948 führte auch die Idee der Datenkomprimierung ein, oder die Darstellung derselben Informationen mit weniger Bits; Komprimierung lässt Programme wie WinZip oder StuffIt Dateien verkleinern, damit sie E-Mail-Server nicht überfordern, und sie wird verwendet, um Speicherplatz auf Festplatten zu sparen. Die Informationstheorie hat auch das Studium der Kryptographie auf eine sicherere mathematische Grundlage gestellt; Tatsächlich glaubt Gallager, dass es Shannons kryptografische Arbeit in den Bell Labs während des Krieges war, die ihn zu seiner neuartigen Neukonzeption der Kommunikation führte.

Als Shannon zum MIT zurückkehrte, hatte er jedoch das Gefühl, dass der Enthusiasmus um seine Theorie ihre beachtlichen Vorzüge überstieg. In einem 1956 erschienenen Artikel mit dem Titel The Bandwagon zitierte er Versuche, die Informationstheorie auf Bereiche wie Biologie, Psychologie, Linguistik, grundlegende Physik, Wirtschaftswissenschaften, Organisationstheorie und viele andere anzuwenden, und verpflichtete sich, in dieser Situation eine gewisse Mäßigung einzuführen.

Shannons Abneigung gegen das Rampenlicht grenzte an Zurückgezogenheit. Laut Joel West '79, einem Professor am College of Business der San José State University, der ein Buch über die Entwicklung der Informationstheorie schreibt, hat Shannon während seiner 22 Jahre am MIT nur sieben Doktoranden beraten. Er war ziemlich schüchtern und zurückhaltend, wenn man ihn also als Vorgesetzten gewinnen wollte, musste man wirklich ziemlich aggressiv vorgehen, sagt Gallager. Ich war auch schüchtern und zurückhaltend und hatte nicht genug Selbstvertrauen, um überhaupt hineinzugehen und mit dem Typen zu sprechen.

Als Lehrerin hatte Shannon wenig Geduld mit der Langeweile des Vertrauten. Er habe sich viel mehr für das Neue als für das Alte interessiert, sagt Elwyn Berlekamp '62, SM '62, PhD '64, emeritierter Professor für Mathematik an der University of California, Berkeley, der (mit Gallager) Co-Autor von Shannons letztes veröffentlichtes Papier.

Er habe nicht viel gelehrt, sagt Gallager. Aber wenn er lehrte, war es, als ob er Forschungsvorträge hielt. Ich erinnere mich, dass er einmal eine Vorlesung gehalten hat, die während des Semesters etwa 25 Vorlesungen umfasste, und jede Vorlesung war ein neues Forschungsergebnis. Er machte sie nacheinander und ließ sich immer wieder etwas Interessantes einfallen. Es war eine wirklich fantastische Zeit.

Shannon war meiner Meinung nach in der Wissenschaft ein bisschen fehl am Platz, sagt James L. Massey, SM '60, PhD '62, Informationstheoretiker und emeritierter Professor an der ETH Zürich. Sein eigentliches Genre war es, ein unabhängiger Forscher zu sein und die Dinge auf seine eigene, höchst individualistische Weise zu tun.

Es kann auch sein, dass Shannon sich mit der Bewunderung einfach nicht wohlgefühlt hat. Berlekamp erinnert sich, als die IEEE Information Theory Society Shannon 1973 einlud, einen Vortrag zu halten und den ersten Shannon Award in Israel entgegenzunehmen. Ich habe noch nie jemanden mit mehr Schmetterlingen gesehen als er, sagt er. Fünf Minuten vor Gesprächsbeginn steht er an der Bar und ist ziemlich deprimiert. Er hat wirklich Angst, auf die Bühne zu gehen und alle zu enttäuschen. Denn natürlich erwarten sie Gott, was wahr ist, und er weiß, dass er nicht wie Gott auftreten kann.

Aber obwohl Shannon selten ein direkter Mentor für junge Studenten der Informationstheorie war, hatte er sie vor eine unwiderstehliche Herausforderung gestellt. Zufällige Codierung würde in der Praxis nie funktionieren: Die Größe von Shannons hypothetischem Codebuch verdoppelt sich mit jedem zusätzlichen Bit in der Nachricht. Das Codebuch für ein einzelnes 1.000-Bit-Datenpaket, das über das Internet reist, würde mehr Einträge erfordern, als es Atome im Universum gibt. Aber jeder praktischere Codierungsmechanismus – wie das Wiederholen der ursprünglichen Nachricht oder das Hinzufügen zusätzlicher Bits, die Nachrichtenbits beschreiben – entsprach einem zufälligen Codierungsschema, da es dieselben Codewörter erzeugen würde. Und indem Shannon demonstrierte, dass die überwiegende Mehrheit der Zufallscodierungsschemata die Kapazitätsgrenze erreichte, machte Shannon Hoffnung, dass eines der praktischen auch dies war.

Schwer fassbare Codes

Anstatt ein Codebuch zu verwenden, um Codewörter und Nachrichten abzugleichen, würde ein praktisches Codierungsschema eine Möglichkeit bieten, die Nachricht rechnerisch aus den Codewörtern zu extrahieren. Eine Reihe mathematischer Operationen könnte mit hoher Genauigkeitswahrscheinlichkeit Fehler in einer möglicherweise beschädigten Bitfolge, die über einen verrauschten Kanal empfangen wird, identifizieren und korrigieren.

Es ist eine der Besonderheiten von fehlerkorrigierenden Codes, dass ein guter Codierungsalgorithmus nicht unbedingt einen guten Decodierungsalgorithmus impliziert. Mithilfe von statistischen Analysen ähnlich der von Shannon konnten Codiertheoretiker zeigen, dass ein bestimmter Code sich an die Kapazität annähert – dass er den Unterschied zwischen Codewörtern maximieren würde. Aber das bedeutete nicht, dass sie eine effiziente Möglichkeit hatten, es zu entschlüsseln.

Zwischen der Veröffentlichung von Shannons Papier und den frühen 1990er Jahren schlugen Forscher immer bessere Codes und auch immer bessere Decodierungsalgorithmen vor. Aber ein praktischer kapazitätsnähender Code blieb schwer fassbar. Früher gab es ein Sprichwort unter Codiertheoretikern, sagt Forney, dass fast jeder Code gut ist – außer allen, die uns einfallen.

Die Codes, die Gallager 1960 in seiner Doktorarbeit vorstellte, waren ein Versuch, einen Teil der Zufälligkeit von Shannons hypothetischem System zu bewahren, ohne die Decodierungseffizienz zu beeinträchtigen. Wie viele frühere Codes verwendet Gallager sogenannte Paritätsbits, die anzeigen, ob eine andere Bitgruppe gerade oder ungerade Summen hat. Aber frühere Codes erzeugten die Paritätsbits auf systematische Weise: Das erste Paritätsbit könnte anzeigen, ob die Summe der Nachrichtenbits eins bis drei gerade war; das nächste Paritätsbit könnte dasselbe für die Nachrichtenbits 2 bis 4 tun, das dritte für die Bits 3 bis 5 und so weiter. In Gallagers Codes hingegen war die Korrelation zwischen Paritätsbits und Nachrichtenbits zufällig: Das erste Paritätsbit könnte beispielsweise die Summe der Nachrichtenbits 4, 27 und 83 beschreiben; der nächste könnte dasselbe für die Nachrichtenbits 19, 42 und 65 tun.

Gallager konnte mathematisch nachweisen, dass seine pseudo-zufälligen Codes für lange Nachrichten die Kapazitätsgrenze erreichten. Abgesehen davon, dass wir auch andere Dinge wussten, die sich der Kapazität näherten, sagt er. Es war nie eine Frage, welche Codes gut sind. Es war immer die Frage, welche Arten von Decodierungsalgorithmen man entwickeln könnte.

Hier gelang Gallager der Durchbruch. Seine Codes verwendeten iterative Dekodierung, was bedeutet, dass der Dekoder die Daten mehrmals durchläuft und immer raffiniertere Vermutungen über die Identität jedes Bits anstellt. Wenn beispielsweise die Paritätsbits Tripel von Bits beschreiben, können zuverlässige Informationen über zwei beliebige Bits Informationen über ein drittes Bit übermitteln. Der iterative Decodierungsalgorithmus von Gallager wird heute am häufigsten verwendet, nicht nur zum Decodieren seiner eigenen Codes, sondern häufig auch zum Decodieren von Turbo-Codes. Es hat auch Anwendung in der Art der statistischen Argumentation gefunden, die in vielen Systemen der künstlichen Intelligenz verwendet wird.

Iterative Techniken beinhalten, eine erste Schätzung zu machen, was ein empfangenes Bit sein könnte, und ihm eine Gewichtung entsprechend seiner Zuverlässigkeit zu geben, sagt Forney. Dann erhalten Sie vielleicht mehr Informationen darüber, weil es an Paritätsprüfungen mit anderen Bits beteiligt ist und Ihnen so eine bessere Einschätzung seiner Zuverlässigkeit ermöglicht. Letztendlich, sagt Forney, sollten die Vermutungen zu einer konsistenten Interpretation aller Bits in der Nachricht führen.

Obwohl Gallager nicht den Mut aufbringen konnte, Shannon als seinen Berater zu bitten, sagte er, dass er während seiner Doktorarbeit drei- oder viermal mit Shannon gesprochen habe. Abgesehen davon, dass ein Gespräch mit Claude drei- oder viermal so war, als würde man mit den meisten Leuten 50-mal sprechen, sagt er. Er war jemand, der die Ideen wirklich sehr, sehr schnell verstanden hat. Er war in allen technischen Details nicht großartig. Aber die Struktur von etwas zu sehen, zu sehen, warum es funktionieren sollte und zu sehen, was es besser machen könnte – nun, er war sicherlich der klügste Mensch, den ich je getroffen habe.

Dennoch hat Shannon den Erfolg von Gallagers Codes nicht vorausgesehen. Ich erinnere mich, dass er sie interessant fand, aber ich hatte nicht das Gefühl, dass er von ihnen begeistert war, sagt Gallager. Er versteht warum. Die Codes von Gallager näherten sich mit zunehmender Länge der Kanalkapazität; aber mit zunehmender Dauer wurde auch der Decodierungsprozess komplexer – viel zu komplex für die damaligen Computer. Programmierforscher wussten natürlich, dass sich Computer verbessern würden. Aber niemand wusste, wessen Codes diese Verbesserungen begünstigen würden.

Trotzdem stellte das MIT Gallager aufgrund seiner Dissertation sofort als Fakultätsmitglied ein. In den folgenden Jahren, während sein eigenes Codierungsschema in Vergessenheit geraten war, unterrichtete und betreute er eine Welle brillanter Studenten – darunter Massey, Forney und Berlekamp – deren Beiträge zur Codierungstheorie unmittelbarere praktische Auswirkungen hatten als seine eigenen.

Gallager scheint jedoch von der langen Vernachlässigung seiner Codes genauso unbeeindruckt zu sein wie von ihrer jüngsten Wiederbelebung – vielleicht, weil er immer den Weitblick hatte. Er hat ein Händchen dafür, Dinge zu erfinden, die jahrzehntelang ruhen, bis die Leute plötzlich merken, dass es ziemlich gute Sachen sind, sagt Vincent Chan '71, MS '71, EE '72, PhD '74, ein Professor für Elektrotechnik, der immer noch von sein Schreibtisch das Türschild des Büros, das er einst mit Shannon geteilt hatte. Chan erinnert sich an einen kürzlichen Besuch in den Labors eines großen Softwareunternehmens, wo ein Forscher mit einer neuen Komprimierungstechnik prahlte, mit der Videodateien nur ein Hundertstel so viel Speicher beanspruchen würden wie heute. Chan fühlte sich verpflichtet, darauf hinzuweisen, dass Gallager die Technik 1974 eingeführt hatte. Viele dieser Ideen brauchen viel Zeit zum Durchdenken, sagt er, und wenn man sie durchdenkt, gibt es viele, viele Möglichkeiten . Und man muss wirklich sehr genau und vielleicht über einen langen Zeitraum nachdenken, bevor man herausfindet, welches das Richtige ist. Bob macht das oft.

Muriel Médard '89, '90, MS '91, ScD '95, eine Informationstheoretikerin im Research Lab of Electronics, stimmt dem zu. Bob rannte nicht herum, um zu veröffentlichen und sicherzustellen, dass er nicht ausgeschöpft wurde, sagt sie. Médard erinnert sich zum Beispiel an ein Gespräch zwischen Gallager und einem prominenten jüngeren Informationstheoretiker, der bei der Beschreibung seiner eigenen Arbeit ein kürzlich bewiesenes Theorem zitierte, auf das es sich stützte. Bob fängt an, in Sachen zu wühlen, so wie er es tut, sagt Médard. Schließlich brachte er eine zerfetzte Kopie eines seiner eigenen Papiere hervor. Er hatte diesen winzig kleinen Beweis, sagt Médard. Und es war wie eine Fußnote. Eine dicke Fußnote, aber eine Fußnote. „Haben sie das so genannt?“ „Ja, Bob, das ist jetzt ein wichtiger Satz.“

Heute liegen die Codes von Gallager den Ansätzen zugrunde, die der maximalen Datenrate für einen bestimmten Kommunikationskanal am nächsten kommen – sogar noch näher als Turbo-Codes. Zusätzlich zu ihren Anwendungen in der Telekommunikation beginnen sie, die älteren Codes zu ersetzen, die zum Schutz von Daten in Laufwerken und anderen Speichergeräten verwendet werden.

Für Leute wie Forney, die während dessen, was er das goldene Zeitalter der Codierungstheorie nennt, am MIT waren, ist die Tatsache, dass die Herausforderung von Shannons Arbeit von 1948 gemeistert wurde, etwas bittersüß. Diejenigen von uns, die Programmieren kennen und lieben, sagen nur ungern, dass das Problem vollständig gelöst ist, sagt Forney. Aber es stimmt, dass die meisten Leute zu anderen Dingen übergegangen sind.

Von 1950 bis 1965 war das MIT die Brutstätte der Informationstheorie, sagt Joel West. Es war wirklich ein goldenes Zeitalter.

verbergen