Ein Fountain-Code (englisch fountain code, auch ratenloser Code, rateless code) ist eine Klasse von Vorwärtsfehlerkorrektur-Codes für den Löschkanal (Erasure Channel). Aus einer endlichen Menge von Quellsymbolen lässt sich eine beliebig lange Folge von Encodierungssymbolen erzeugen — wie ein Springbrunnen tropft der Sender Symbole, bis der Empfänger genug gesammelt hat, um die Originaldaten zu rekonstruieren.
Idee: ratenlos statt fester Coderate
Klassische Blockcodes wie Reed-Solomon oder LDPC-Codes arbeiten mit einer festen Coderate: Sender und Empfänger müssen vorab wissen, wie viel Redundanz der Kanal verlangt. Ein Fountain-Code hat keine feste Rate — der Sender erzeugt so lange neue Symbole, bis der Empfänger per Rückmeldung oder per vereinbarter Stückzahl signalisiert, dass er genug hat. Entscheidend ist die Eigenschaft, dass die Originaldaten aus beliebigen empfangenen Symbolen dekodierbar sind, sobald deren Anzahl die Zahl der Quellsymbole nur geringfügig übersteigt.
Praktische Vertreter
- LT-Codes (Luby Transform, Michael Luby 2002): erste praktische Fountain-Codes, nahezu optimal auf dem Löschkanal
- Raptor-Codes (Amin Shokrollahi): Kombination aus einem schwachen äußeren Code und einer LT-Schicht — lineare Encodier- und Decodierzeit
- RaptorQ: Weiterentwicklung mit höherer Effizienz, standardisiert in 3GPP MBMS/eMBMS und DVB
Anwendungen
Fountain-Codes eignen sich ideal für Broadcast und Multicast, bei denen viele Empfänger unterschiedlich viele Pakete verlieren: Jeder Empfänger braucht nur genug Symbole, eine individuelle Rückkanal-Planung entfällt. Typische Einsätze sind mobiler Rundfunk (3GPP MBMS/eMBMS), Dateiverteilung über unzuverlässige Netze und Tiefraummissionen.
Verwandte Grundlagen: Fehlererkennung, LDPC-Code, Polar-Code.