Timos Blog

Vor einiger Zeit habe ich einen kleinen Reed-Solomon-Encoder (ein Verfahren der Vorwärtsfehlerkorrektur, Forward Error Correction, FEC) in Java geschrieben.

Er ist eigentlich gedacht für den Einsatz in einem ISO/IEC 16022:2000 DataMatrix-2D-Barcode-System und die Voreinstellungen der Parameter sind entsprechend gewählt. Der Encoder unterstützt die aber Angabe einer (nahezu) beliebigen Galois-Feld-Größe sowie von Generatorpolynomen sowie primitiven Polynomen.

Der weitaus spannendere Teil, der RS-Decoder, steht noch aus. Eine Implementierung ist zwar geplant, aber momentan kann ich daran leider nicht arbeiten.

Eine Demoklasse, die den RS-Encoder verwendet

Hier ein Beispiel kurzes für den häufig benutzten (255, 223)-Reed–Solomon-Code.
Ein Array wird mit zufälligen Beispieldaten gefüllt (mit Random Seed 0, um einigermaßen Reproduzierbarkeit zu haben) und mit dem RSEncoder kodiert. Anschließend enthält das Array die Beispieldaten sowie im Anschluss daran die RS-Prüfstellen. In der Ausgabe (s. Kommentar) sind diese durch eine gestrichelte Linie von den Datensymbolen getrennt:

package name.holle.timo.demos;
 
import org.toolio.datamatrix.ecc200.RSEncoder;
 
/**
 * RS-Encoder Demo Class
 * @author Timo
 */
public class RSEncoderDemo {
 
     public static void main(String[] args) {
 
        /* create new "random" number generator with seed 0 */
        java.util.Random generator = new java.util.Random(0);
 
        /* standard (255, 223)-Reed–Solomon code: 223 Reed–Solomon input symbols
           (each eight bits long) are encoded into 255 output symbols. */
 
        int datalen = 223;
        int codelen = 255-datalen;
 
        /* array to hold both data and correction codewords */
        int[] d = new int[datalen + codelen];
 
        for (int i = 0; i < datalen; i++) {
            d[i] =  java.lang.Math.abs(generator.nextInt()) % 255;
        }
 
        RSEncoder e = new RSEncoder(codelen);
        e.encode(d);
 
        for (int i = 0; i < datalen; i++) {
            System.out.println("d[" + i + "] = " + d[i]);
        }
 
        System.out.println("-------------------------------------------------");
 
        for (int i = datalen; i < d.length; i++) {
            System.out.println("d[" + i + "] = " + d[i]);
        }
    }
}

Lizenz

Der RS-Encoder kann als Quelltext heruntergeladen werden.
Die Weitergabe und Verwendung in eigenen Projekten ist in seiner derzeitigen Form allerdings untersagt.
Bei Bedarf stelle ich den Code gern nach Absprache unter einer geeigneten Lizenz (z.B. GPL) zur Verfügung.

Download

Den Encoder gibt es hier zum Download: Reed Solomon Encoder (Java-Quelltext im ZIP-Archiv)

Andere Implementierungen von FEC in Java

• Onion Networks Java FEC Library v1.0.3 Lizenz: BSD-Style, basierend auf Effective erasure codes for reliable computer communication protocols von Luigi Rizzo
• http://www.ningning.org/academic/itc/code/src/

Java, Topstory Code, ECC, FEC, Java, Quellcode, Quelltext, Reed-Solomon, Source