Kombination von zuverlässigkeitsbasierten und algebraischen Strategien zur Decodierung verketteter Codes
Final Report Abstract
In zahlreichen Anwendungen werden verschiedene Techniken der Kanalcodierung kombiniert, es lassen sich so aufwandsgünstige Verfahren mit geeigneter Decodierleistung entwerfen. Eine verbreitete Variante isl beispielsweise die Verkettung eines Fallungscodes mit einem Blockcode. Hier werden die Informationsworte zunächst mit dem Blockcode, bspw. einem ReedSolomon (RS) Code encodiert. Die Symbole des resultierenden Codewortes werden anschließend mit dem Fallungscode encodiert und das Codewort des verketteten Codes wird überlragen. Auf Empfängerseite erfolgt dann zunächst die Decodierung des Fallungscodes. Dadurch werden die übertragenen Daten bereits von einem Großteil der entstandenen Fehler befreit, Faltungscodes sind für die Übertragung über vergleichsweise schlechte Kanäle geeignet. Nach der Decodierung des Faltungscodes verbleiben ggfs. aber noch burstarlige Restfehler, welche durch die Decodierung des Blockcodes korrigiert werden können. Man nutzt also die Vorteile beider Codeklassen: Der Faltungscode wird im vergleichsweise schlechten Übertragungskanal verwendet. Faltungsencoder, Übertragungskanal und Faltungsdecoder ergeben zusammen genommen einem Superkanal, welcher als vergleichsweise gut anzusehen ist. Für genau diesen Fall ist aber der Blockcode geeignet, er kann die Fehlerrate bis auf extrem niedrige Werte verringern. Die beschriebene Struktur wird als verketteter Code bezeichnet, der Blockcode ist in diesem Beispiel der äußere Code und der Fallungscode der innere Code. Ein Beispiel isl der CCSDS-Standard für die Kanalcodierung in Raumfahrt-Telemelrie-Kanälen [CCS02]. Hier werden mehrere, zeilenweise angeordnete äußere RS Codes und ein innerer Faltungscode verwendet. Zeilenweise angeordnete RS Codes werden auch als Interleaved ReedSolomon (IRS) Codes bezeichnet, es existieren mächtige Verfahren zur ihrer Decodierung. Unler anderem wurde im Rahmen dieses Projekts ein Algorithmus entwickelt, der auf der Synthese linearer Schieberegister basiert und einen großen Decodierradius - größer als die halbe Mindestdislanz der Komponentencodes - aufweist. Die Einschränkung hierbei ist, dass die Fehler spaltenweise auftrelen müssen und zur Nutzung des größtmöglichen Radius nicht beliebig verteilt sein können. Genau dieses Fehlermuster lässt sich aber im Superkanal (bestehend aus Falmngsencoder, Übertragungskanai und Faltungsdecoder) mit einer geringfügigen Modifikation erreichen. Man muss dazu den Fallungscode nur spaltenweise "lailbiten", ein Verfahren welches die Fortpflanzung von Fehlern über die Spaltengrenzen hinweg verhindert. Ein Nachteil der Decodierung bis über die halbe Mindesldistanz eines Codes isl, dass stets eine Restwahrscheinlichkeit für ein Decodierversagen bestehi. Im Rahmen dieses Projekts wurde diese Wahrscheinlichkeit nach oben abgeschätzt und es wurde gezeigt, dass sie entweder vemachlässigbar klein ist oder mit marginal veränderten Codeparametem vemachlässigbar klein gemacht werden kann. Zusammen mit Abschätzungen für die Fehlerwahrscheinlichkeiten von Faltungscodes kann damit die Fehlerwahrscheinlichkeit des gesamten verketteten Codes analytisch bestimmt werden, so dass keine aufwändigen Simulationen - besonders für sehr niedrige Fehlerraten, wie sie hier erzielt werden sollen - notwendig sind. Es wurde im Projekt femer untersucht, die Decodiemng von IRS Codes gewinnbringend in die Decodiemng von verallgemeinert verketteten Codes zu integrieren. Hier handelt es sich - ausgehend von einer Beschreibung von Dumer [Dum80], [Dum981 - um eine Kaskade von mehreren verketteten Codes. In einem ersten Schritt wurden innere Blockcodes angenommen, um Ergebnisse bezüglich des erreichbaren Decodierradius zu erhalten. Es wurde gezeigt, dass bei entsprechenden Codeparametem die Anzahl der notwendigen Decodierversuche in der Mehrschritt-Generalized Minimum Distance (Mehrschritt-GMD) Decodierung [For66] reduziert werden kann, der erreichbare Decodierradius bleibt dabei erhalten. Es wurden bereits erste Arbeiten dahingehend untemommen, die IRS Decodierung zur Verringemng der Restfehlerwahrscheinlichkeit von verketteten und verallgemeinert verketteten Codes einzusetzen, Ergebnisse sind in den nächsten Monaten zu erwarten. Ein Hauptergebnis des Projekts ist die Erweitemng des Syndroms von niederrangen (R < 1/3) RS Codes durch die Berechnung neuer Syndromgleichungen. Dieses Verfahren verwendet eine einfache symbolweise Exponentation, um einen RS Code mit niedriger Rate in einen IRS Code zu transformieren. Zu dessen Decodiemng wird dann ein erarbeiteter Aigorthmus zur effizienten IRS Decodiemng verwendet. Es wurde gezeigt, dass diese Lösung eine vergleichbare Leistung wie der Algorithmus von Sudan [Sud97] aufweist, es kann also für niederratige Codes über die halbe Mindestdistanz hinweg decodiert werden. Dabei ist das im Projekt erarbeitete Verfahren aufwandsgünstiger, die Komplexität steigt nur linear im Vergleich zur traditionellen Decodiemng bis zur halben Mindestdistanz bspw. mit dem Algorithmus von Berlekamp-Massey. In zukünftigen Arbeiten sollen die Ansätze zur Mehrschritt-GMD Decodiemng weiter verfolgt werden. So ist z.B. angedacht, optimale Schwellwerte zur Maximiemng des erreichbaren Fehlerexponenten herzuleiten, erste Ergebnisse hierzu existieren bereits. Es soll in dieser Hinsicht auch in Richtung verallgemeinert verketteter Codes geforscht werden, welche aus Sicht der Decodiemng eine Kaskade von einfach verketteten Codes sind. Alle Ergebnisse für verkettete Codes lassen sich also direkt auf verallgemeinert verkettete Codes üebertragen. Femer ist bis dato unbekannt, in welchem Verhältnis der Algorithmus von Sudan [Sud97] zu der Überfuhmng eines niederratigen (R < 1/3) RS Codes in einen IRS Code durch symbolweise Exponentation steht. Die erzielten Simulationsergebnisse bezüglich der Restfehlerwahrscheinlichkeit stimmen weitgehend überein, es fehlt jedoch bisher eine algebraische Erklärung.
Publications
- Error and erasure cortection of interieaved Reed-Solomon codes. In Proc. Int. Workshop on Coding and Cryptography, pages 20-29, Bergen, Norway, March 2005
G. Schmidt, V. R. Sidorenko, and M. Bossert
- Interleaved Reed-Solomon codes in concatenated code designs. In Proc. IEEE ITSOC Inform. Theory Workshop, pages 187-191, Roloma, New Zealand, August 2005
G. Schmidt, V. R. Sidorenko, and M. Bossert
- Multitrial decoding of concatenated Reed-Solomon codes. In Proc. IEEE Int. Symposium on Inform. Theory, pages 2241-2245, Adelaide, Australia, September 2005
G. Schmidt, C. Huppert, and M. Bossert
- Decoding Reed-Solomon codes beyond half the minimum distance using shift-register synthesis. In Proc. IEEE Int. Symposium on Inform. Theory, pages 459-463, Seattle, WA, USA, July 2006
G. Schmidt, V. R. Sidorenko, and M. Bossert
- Error and erasure correction of interleaved Reed-Solomon codes. In Coding and Cryptography, volume 3969 of Lecture Notes in Computer Science, pages 22-35. Springer Verlag, Berlin, 2006
G. Schmidt, V. R. Sidorenko, and M. Bossert
- Heterogeneous interleaved Reed-Solomon code designs. In Proc. 10th Int. Workshop on Algebraic arui Combinatorial Coding Theory (ACCT-IO), pages 230-233, Zvenigorod, Russia, September 2006
G. Schmidt, V. R. Sidorenko, and M. Bossert
- Linear shift-register synthesis for multiple sequences of varying length. Preprint, available online, 2006
G. Schmidt and V. R. Sidorenko
- Multi-sequence linear shift-register synthesis: The varying length case. In Proc. IEEE Int Symposium on Inform. Theory, pages 1738-1742, Seattle, WA, USA, July 2006
G. Schmidt and V. R. Sidorenko
- Algebraic Decoding Beyond Half the Minimum Distance Based on Shift-Register Synthesis. Fortschritt-Berichte VDI. VDI Verlag, Düsseldorf, 2007. ISBN 978-3-18-378110-2
G. Schmidt
- Enhancing the cortecting radius of interleaved Reed-Solomon decoding using syndrome extension techniques. In Proc. IEEE Int. Symposium on Inform. Theory, Nice, France, June 2007
G. Schmidt, V. R. Sidorenko, and M. Bossert
- Syndrome decoding of Reed-Solomon codes beyond half the minimum distance based on shift-register synthesis. Preprint, available online, 2007
G. Schmidt, V. R. Sidorenko, and M. Bossert
- Concatenated code designs with outer interleaved Reed-Solomon codes and inner tailbiting convolutional codes. In Proc. Intemational ITG Conference on Source and Channel Coding, Ulm, Germany, January 2008
G. Schmidt, Ch. Senger, and M. Bossert
- Decoding generalized concatenated codes using interleaved Reed-Solomon codes. In Proc. IEEE Int. Symposium on Inform. Theory, Toronto, ON, Canada, July 2008
Ch. Senger, V. R. Sidorenko, M. Bossert, and V. V. Zyablov
- Decoding punctured Reed-Solomon codes up to the Singleton Bound. In Proc. International ITG Conference on Source arui Channel Coding, Ulm, Germany, January 2008
V. R. Sidorenko, G. Schmidt, and M. Bossert
- Single-trial adaptive decoding of concatenated codes. In Proc. Intemational Workshop on Algebraic and Combinatorial Coding Theory, Pamporovo, Bulgaria, June 2008
V. R. Sidorenko, Ch. Senger, M. Bossert, and V. V. Zyablov
- Collaborative decoding of interleaved Reed- Solomon codes and concatenated code designs. IEEE Trans. Inform. Theory, IT-55(7):2991- 3012, July 2009
G. Schmidt, V. R. Sidorenko, and M. Bossert
- On extended fomeykovalev gmd decoding. In Proc. IEEE Int. Symposium on Inform. Theory, Seoul, Korea, July 2009
V. R. Sidorenko, Anas Chaaban, Christian Senger, and M. Bossert
- On Generalized Minimum Distance decoding thresholds for the AWGN channel. In Proc. XII Symposium Problems of Redundancy in Information and Control Systems, St. Petersburg, Russia, May 2009
Ch. Senger, V. R. Sidorenko, and V. V. Zyablov
