RS-код на библиотеке schifra - как настроить полином?

В настоящее время я пытаюсь запустить библиотеку schifra для выполнения некоторых тестов, чтобы реализовать ее позже в моем коде.

В настоящее время я просматриваю schifra_reed_solomon_example02.cpp и пытаюсь понять, как мне установить значения, соответствующие моим потребностям.

/* Finite Field Parameters */
   const std::size_t field_descriptor                 =   8; // GF(2^8) ok
   const std::size_t generator_polynommial_index      = 120; // what is this?
   const std::size_t generator_polynommial_root_count =  32; // polynomial up to x^32

   /* Reed Solomon Code Parameters */
   const std::size_t code_length = 255;  // amount of symbols in codeword
   const std::size_t fec_length  = 32;  // minimal distance d ?
   const std::size_t data_length = code_length - fec_length; // amount of symbols my message has

Итак, я пытаюсь получить RS-код для n, k, d = (128, 16, 113)

И я бы поступил следующим образом:

/* Finite Field Parameters */
   const std::size_t field_descriptor                 =   8; // I want GF(2^8)
   const std::size_t generator_polynommial_index      = 120; // still not knowing
   const std::size_t generator_polynommial_root_count =  16; // because polynomial up to 16

   /* Reed Solomon Code Parameters */
   const std::size_t code_length = 128;  // 128 byte codewords
   const std::size_t fec_length  = 113;  // minimal distance, 113 because d = n - k +1
   const std::size_t data_length = 16; 

Затем я получаю при кодировании сообщения ошибку.

schifra::galois::field_polynomial generator_polynomial(field);

   schifra::sequential_root_generator_polynomial_creator(field,
                                                         generator_polynommial_index,
                                                         generator_polynommial_root_count,
                                                         generator_polynomial);

   /* Instantiate Encoder and Decoder (Codec) */
   schifra::reed_solomon::encoder<code_length,fec_length> encoder(field,generator_polynomial);
   schifra::reed_solomon::decoder<code_length,fec_length> decoder(field,generator_polynommial_index);

   std::string message = "A professional i"; // its 16 bytes
   std::cout << "Original Message:   [" << message << "]" << std::endl;
  message = message + std::string(data_length - message.length(),static_cast<unsigned char>(0x00)); // this one is also done in example

   std::cout << "Original Message:   [" << message << "]" << std::endl;
   std::cout << "Message length: " << message.length() << std::endl; // still 16 bytes

   /* Instantiate RS Block For Codec */
   schifra::reed_solomon::block<code_length,fec_length> block;

   /* Transform message into Reed-Solomon encoded codeword */
   if (!encoder.encode(message,block))
   {
      std::cout << "Error - Critical encoding failure!" << std::endl;
      return 1;
   }

Затем дается Error - Critical encoding failure!.

Я думаю, что я делаю неправильно, правильно настраиваю полином - может быть, кто-то может мне помочь?


person Stefan    schedule 28.01.2014    source источник


Ответы (2)


Я новичок, пробовал пользоваться библиотекой Schifra. Я ничего не знал о кодах Рида Соломона, и после нескольких недель копания в исходном коде я нашел комбинацию, которая всегда работает. Я до сих пор не знаю ни одной математики, которую используют коды RS.

Некоторый жаргон, который может быть полезен:

  • Символ: наименьший квант информации, который распознает код RS (обычно устанавливается на 8 бит (1 байт))
  • FEC: это «символы» избыточности или исправления ошибок, которые добавляются в конце ваших данных.
  • Данные: данные, для которых вы хотите сгенерировать коды RS.
  • Поле Галуа: многочлен или отображение, которое код Рида-Соломона использует для исправления ошибок (я не знаю никакой математики, стоящей за кодами RS).

Комбинация, которая работает и имеет некоторый смысл в инициализирующих переменных, не углубляясь в математику:

  • Дескриптор поля = размер символа (обычно устанавливается на 8 битов в длину)
  • Индекс полинома генератора = Не знаю, что это такое, но установка его на 0 всегда работает и дает небольшой прирост производительности по сравнению с другими значениями.
  • Число корней полинома генератора = должно быть равно длине FEC
  • Длина кода = Это значение ДОЛЖНО быть (2^(размер символа или дескриптор поля)-1). Он обозначает количество символов в вашей окончательной закодированной строке (символы данных + символы исправления ошибок). Обратите внимание, что общий размер закодированной строки в битах равен длине кода * размеру символа.
  • Длина FEC: количество символов исправления ошибок.
  • Длина данных: количество символов данных. (Как инициируется в примерах как Code_length - FEC_length) это не следует трогать.

Следует отметить, что для конкретного размера символа длина кода фиксирована, и можно варьировать, какой процент от этой длины кода будет приходиться на данные, а какой на символы исправления ошибок. И, как подсказывает здравый смысл, чем больше символов для исправления ошибок, тем больше возможностей для исправления ошибок.

При запуске кодировщика вы передаете объект блока вместе с данными в качестве аргументов.

При запуске метода encoder.encode «блок» заполняется закодированными данными (данные + ECC).

После повреждения выполняется декодирование. Количество ошибок, стираний, которые может исправить декодер, объясняется в этом ссылка

Декодер принимает блок и список стираний (если применимо) в качестве аргументов и возвращает исходное сообщение/данные, если количество стираний и ошибок находится в пределах диапазона ECC (см. ссылку).

person Priyal Chhatrapati    schedule 01.12.2019

Кодировка Рида-Соломона не предназначена для работы
с вашими параметрами независимо от программного кода.

Вы можете выбрать следующие вещи:

  • A B, это количество битов в одном блоке данных (например, B=8 для обычных байтовых данных).
  • T с 0 <= T < (2^b)/3: большее значение T означает лучшую коррекцию ошибок, но меньшую скорость кодирования.
  • Какая-то неприводимая полиномиальная и базовая степень, здесь неважная.

Вы НЕ можете выбрать:

  • GF/основание полинома равно 2^B, и ничего больше.
  • Каждый блок открытого текста (без данных контрольной суммы RS) должен состоять
    из (2^B - 2*T - 1) единиц данных (в данном случае байтов), больше ничего.
  • Для каждого блока открытого текста RS дополнительно вычисляет 2*T данных контрольной суммы единиц данных.
  • Таким образом, блок с открытым текстом и данными контрольной суммы вместе имеет 2^B -1 единиц данных.
    Это означает, что с байтами в качестве единиц данных такой блок имеет ровно 255 байт, больше ничего.
  • При повторном декодировании можно исправить до T неверных блоков данных
    (ошибки могут быть в открытом тексте и/или в части контрольной суммы, не имеет значения)
  • Можно распознать до 2*T неверных единиц данных, но обязательно исправить.
  • При наличии более 2*T ошибок все ставки снимаются.

В примере кода (частично):

const std::size_t field_descriptor = 8;
const std::size_t code_length = 255; 
const std::size_t fec_length = 32;
const std::size_t data_length = code_length - fec_length;  
  • field_descriptor — это B.
  • code_length — полная длина блока (открытый текст + контрольная сумма).
  • fec_length — длина контрольной суммы.
  • data_length — длина блока открытого текста.

Таким образом, для каждых 233 байтов открытого текста RS вычисляет 32 байта контрольной суммы
(= 255 байтов всего), чтобы впоследствии можно было исправить до 16 неправильных байтов.

В вашем коде вы выбираете GF (2 ^ 8) и байтовые данные, поэтому B = 8, поэтому длина кода 128 неверна. Должно быть 255. Длина части контрольной суммы 113 слишком велика и неравномерна, а длина открытого текста не является разницей предыдущих значений.
...

Помимо этого, из 6 кодов RS, которые я знаю в Интернете, Shifra, безусловно, худший (очень медленный, несмотря на то, что его хвалят как «высокооптимизированный», причудливый код, проблемная лицензия, ...). Выбирайте что угодно, только не Шифру.

Я проверю, если я могу поделиться тем, что я написал ... В том числе изучение внутренней работы алгоритма, написание всего (кодировщик + декодер) заняло даже не один день, и это было в 3 раза быстрее, чем Шифра на тестовой машине назад затем (без ассемблера, только C++). Недостатком является то, что он может работать только с байтовыми данными, т.е. B=8, без возможности выбора других баз. Но, наверное, вам это все равно не нужно.

person deviantfan    schedule 10.11.2015