Портирование функции Рида Соломона в MATLAB на Java

Question

Я реализовал простую схему исправления ошибок RS в MATLAB с RS(160,80). Основной процесс заключается в следующем:

1. Я генерирую сообщение длиной 80 и 8 бит на символ и генерирую код RS длиной 160.

2. После генерации кода RS я добавляю /XOR другое поле Галуа с длиной кода 160. (это поле содержит только 00000000 и 00000001). Это для симуляции ошибок при добавлении в схему. Это генерирует мой шумный код.

3. Теперь я беру другое поле GF (того же типа, что и выше [00000000 00000001]), в котором < 40 символов отличается от того, которое я использовал для создания шума. Я добавляю /XOR это к сгенерированному шумному коду на предыдущем шаге.

4. Наконец, я запускаю его через декодер RS, который возвращает мое исходное сообщение.

Моя функция MATLAB:

function RSKeyExchange(dev1, dev2)
    dev1_fp = zeros(1,160);
    dev2_fp = zeros(1,160);

    for i=1:160
        dev1_fp(i) = str2double(dev1.key(i));
        dev2_fp(i) = str2double(dev2.key(i));
    end

    n = 160;        % total code length
    k = 80;         % message length - actual message for syncronisation
    m = 8;          % order (2^m)

    % therefore, RS decoder can detect t = n-k = 80 errors
    % and correct t/2 = 40 errors

    msg = gf(randi([1 255],1 ,80), m);
    code = rsenc(msg, n, k);

    noise_add = gf(dev1_fp, 8);
    noise_remove = gf(dev2_fp, 8);

    noisy_code = code + noise_add;

    % noisy_code is now transmitted from dev1 to dev2 (sender to receiver)

    decommited_code = noisy_code + noise_remove;
    [rxcode, cnumerr] = rsdec(decommited_code, n, k);

    fprintf('Number of errors corrected: %d\n', cnumerr);
end

Теперь я искал способы перенести это на Java. Я искал библиотеки, но я не уверен, как точно перенести мой конкретный вариант использования.

• Zxing - принимает только QR и Aztec коды в качестве входных данных

• https://github.com/Backblaze/JavaReedSolomon - исправляет стирание кода, которое не является той ошибкой, которую я создаю, а ввод осуществляется в форме файлов (серьезно сбит с толку относительно того, что здесь происходит)

• Пример простого исправления ошибок RS - Чувствуется немного более разборчиво, но принимает только строки в качестве входных данных. Я чувствую, что могу изменить его в соответствии с моим вариантом использования, но я не уверен, как добавить шум. Я не уверен, как сгенерировать код RS (160, 80) с помощью этой реализации, и я не могу сказать, как генерировать настраиваемые поля GF для добавления шума.

Любая помощь будет принята с благодарностью (особенно если вы можете указать мне на реализацию, которая бы соответствовала моему варианту использования, или помочь изменить один из вышеуказанных ресурсов, который будет работать)

Спасибо!

Answer 1

Я посмотрел на "простой RS" пример "GF28" Java-кода. Похоже, что декодер обрабатывает только стирания (один из входных данных представляет собой массив плохих индексов). Он использует GF(256) на основе шестнадцатеричного 11B = x^8 + x^4 + x^3 + x + 1, так же, как шифрование AES. Это несколько необычный выбор, поскольку самый низкий "примитив" равен 3 (все числа, отличные от нуля, можно считать степенью 3), а не поля, в которых "примитив" равен 2. Полином поля определяется через PX, так что это может быть легко изменено. Я не уверен, почему он генерирует таблицы динамически, а не генерирует их во время инициализации, используя второй набор таблиц true/false, чтобы указать, были ли созданы конкретные значения таблиц.

У меня есть демонстрационная программа C RS для 8-битных полей GF(256). Он интерактивный, вы выбираете поле (их 30), использовать ли самовзаимный полином (обычно он не используется), если первый последовательный корень полинома-генератора равен 1 (если не указано, то первый последовательный корень root - это "примитив"), количество байтов четности и количество байтов данных. Он обрабатывает как стирания, так и ошибки, и, поскольку он является демонстрационной программой, он включает код для 3 основных типов алгоритмов декодера, матричный алгоритм Петерсона, адаптацию расширенного алгоритма Евклида Sugiyama и алгоритм Берлекампа Масси, а также алгоритм Форни для генерации значений ошибок. Интерактивная часть может быть заменена кодом, который выбирает все эти параметры. Для вашей ситуации измените определение для MAXPAR с 20 на 80 (максимальное количество паритетов). Пользовательский ввод осуществляется через stdin, поэтому для запуска демонстрации можно использовать текстовый файл ввода.

http://rcgldr.net/misc/eccdemo8.zip

В моей демонстрации для генерации кодового слова пользователь вводит значения (пользовательская опция "E" или "C"), затем вводит "N" для кодирования. Чтобы генерировать ошибки, пользователь вводит значения в определенных местах. Для создания стираний пользователь использует опцию "P" для ввода значений стирания в определенных местах. "F" используется, чтобы исправить (исправить) кодовое слово.

Статья в вики включает логику для 3 основных типов декодеров. Это также объясняет преобразование Фурье, но преобразование Фурье требует использования одного из других декодеров для генерации многочлена ошибок, и не практично.

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

---

На основании вашего комментария я посмотрел библиотеку Zxing. Описания методов немного кратки и используют неверную терминологию. Вот повторение описания:

GenericGF(primitive, size, b)
    primitive - wrong term, this is the field polynomial

    size - The description is "size of the field", but that is
    determined by the polynomial, a n+1 bit polynomial is used
    for an n bit field. My guess is this is the size of the
    generator polynomial, perhaps the number of roots.

    b - alpha raised to the b power is the first consecutive root.
    alpha is the primitive for the particular field. Unlike the
    comment, b == 0 is about as common as b == 1.

https://en.wikipedia.org/wiki/Primitive_element_(finite_field)

encode(int[] toEncode, int ecBytes)
    toEncode - toEncode includes space for the "parity" data used
    to encode the message.

    ecByte - the number of "parity" elements at the end of to Encode.
    Why is it named ecBytes when it is an array of ints?

decode(int[] received, int twoS )
    received is an array of concatenated encoded messages?
    Since encode generates a single encoded message, then it would
    make more sense for decode to decode a single encoded message.

    twoS - the number of encoded messages?

    Based on the references, it is using the Sugiyama adaptation
    of extended Euclid algorithm. A side benefit is that the
    error evaluator polynomial is generated during the process.

В комментарии обертки также есть ошибка. Максимальный размер для кодового слова GF(256) составляет 255 байтов, поскольку местоположения ошибок ограничены диапазоном от 0 до 254. Это связано с тем, что местоположения связаны с мощностями, и любое число, возведенное в степень 255 в GF(256), таково, что такое же количество.

---

Обратите внимание, что исправление ошибок возможно без запуска исключения библиотеки. Однако с 80 байтами четности потребуется 41 ошибка, чтобы это стало возможным. Исправление ошибок будет включать в себя создание набора из 40 местоположений и значений, которые выдают действительное кодовое слово, но такое, которое отличается от исходного кодового слова на 81 или более байтов (81 или более ошибок). Однако при сокращенном кодовом слове в 160 байтов все 40 сгенерированных местоположений должны были бы находиться в диапазоне от 0 до 159. При случайном равномерном распределении рассчитанных местоположений вероятность их неправильной коррекции будет равна ((160!)/((160-40)!))/(255^40)!= 3,86 × 10^-11 . Неправильная коррекция является проблемой, если использовать полные (255) кодовые слова или меньшее количество четностей.

---

Я сделал пример Java RS ecc GF(256). Он не обрабатывает стирания (что требует изменения синдромов для известных местоположений стирания, а затем объединения локаторов ошибок с локаторами стирания). Он использует алгоритм Евклида для вычисления многочленов локатора и оценщика ошибок. Это прокомментировано, но вам может понадобиться посмотреть статью Wiki RS, чтобы лучше это понять. Код работает с байтами со знаком Java, преобразовывая их в целые числа без знака, используя при необходимости byte&0xff. Я установил параметры на 80 байтов сообщения, 80 байтов четности, чтобы соответствовать примеру вопроса. Хотя и сложение, и вычитание являются xor для GF(256), код использует отдельные функции для сложения и вычитания, так что код соответствует алгоритму, как это будет применяться к GF(p), где p - простое число, такое как GF(257). Расчет для "производной" лямбды также будет отличаться для GF(p), это объясняется здесь:

https://en.wikipedia.org/wiki/Forney_algorithm

Ссылка на пример java rsecc GF(256):

http://rcgldr.net/misc/rsecc8.zip

Интерактивную версию C легче отслеживать, поскольку она интерактивна, отображает некоторые внутренние вычисления (определения можно изменить, чтобы включить / отключить то, что отображается), и пользователь может попробовать различные варианты.

Answer 2

Итак, я смог решить свою проблему. Я немного скомпрометировал, так что это не точный порт, и он довольно взломан. В любом случае, это работает для моего варианта использования.

Я нашел библиотеку-обертку для Zxing, которая делает большую часть тяжелой работы.

Вместо использования GF(8), как моя программа MATLAB, оболочка использует GenericGF.QR_CODE_FIELD_256, который использует GF(256) для кодирования.

Это реализация Java, которая в основном достигает того же самого. (MsgKeyPair - это просто структура данных, содержащая две строки)

public MsgKeyPair generateKey(String fingerprint){
    EncoderDecoder encoderDecoder = new EncoderDecoder();

    try {
        String message = generateMessage();
        byte[] data = message.getBytes();

        byte[] encodedData = encoderDecoder.encodeData(data, 80);
        byte[] noisyData = encodedData.clone();

        for(int i=0; i<encodedData.length; i++){
            byte one = 0xff & 00000001;
            if(fingerprint.charAt(i) == '1') {
                int oneInt = (int) one;
                int edInt = (int)encodedData[i];
                int xor = oneInt ^ edInt;

                noisyData[i] = (byte)(0xff & xor);
            }
        }

        String keyToSend = new String(Base64.encode(noisyData, Base64.DEFAULT));
        return new MsgKeyPair(message, keyToSend);
    }
    catch (Exception e){
        Log.e(TAG, "generateKey: ", e);
    }

    return new MsgKeyPair("", "");
}

public String KeyDecoder(String fingerprint, String key) throws Exception{
    byte[] noisyData = Base64.decode(key, Base64.DEFAULT);

    byte[] decomCode = noisyData.clone();
    for(int i=0; i<noisyData.length; i++){
        byte one = 0xff & 00000001;
        if(fingerprint.charAt(i) == '1'){
            int oneInt = (int)one;
            int ndInt = (int) noisyData[i];
            int xor = oneInt ^ ndInt;

            decomCode[i] = (byte)(0xff & xor);
        }
    }

    EncoderDecoder encoderDecoder = new EncoderDecoder();

    byte[] decodedData = encoderDecoder.decodeData(decomCode, 80);
    String originalMessage = new String(decodedData);

    return originalMessage;
}

public static String generateMessage(){
    String msg = "";

    for(int i=0; i<80; i++){
        int bit = Math.round(randomWithRange(0,1));
        msg = msg + String.valueOf(bit);
    }

    return msg;
}

private static int randomWithRange(int min, int max)
{
    int range = (max - min) + 1;
    return (int)(Math.random() * range) + min;
}