Код Рида-Соломона

Бывает так, что требуется передать какие либо данные по каналу связи, в котором возможны искажения при передаче, в случае если искажения бывают редко, можно повторно передать данные, но что делать, если искажения неизбежны? В этом случае применяют избыточный код. Избыточный код — код, который за счет усложнения структуры позволяют находить возникающие ошибки. Самый используемый код Рида-Соломона, он применяется в CD/DVD. Вообще говоря, существование CD/DVD в том виде в котором мы их знаем, было бы невозможным без избыточного кода, любой малейший дефект или царапина приводили бы диск в негодность.

Возможности

Код Рида-Соломона позволяет воссоздать пакет информации, при повреждении части пакета. При кодировании к пакету данных добавляется дополнительная информация, количество её задаётся настройками и является постоянной. Допустим мы добавляемым 20 байт, тогда допустимое повреждение пакета составит 20 байт, при условии что мы сообщим алгоритму где именно произошли повреждения, и 10 байт, если алгоритм сам будет вычислять положения ошибок. Может так сложится что положения части ошибок будет известно, а часть нет, тогда допустимое повреждение будет между 10 и 20 байтами.  Для определения избыточности используют запись вида (255,223) это означает, что всего в пакете после кодирования будет 255 символа(в простейшем случае-байт) из них 223-полезная информация, 32 символов-информация для восстановления. теория и механизм работы находятся за пределами этой статьи, только практическое использование.

Библиотека

В сети есть несколько реализаций кода Рида-Соломона, для освоения предлагаю использовать эту библиотеку, она хороша тем, что у неё самый простой API, и она содержит всего 2 файла. Платформо зависимой части у неё нету, я для тестов воспользуюсь STM32, главное чтобы в памяти хватало. Размер символа в битах прочно связан с размером пакета, выбирать размер символа отличный от 8 нет смысла, потому и размер пакета примем равным 255 байт((2^8) — 1). Формула получается(255,223)

Настройка библиотеки

Добавляем библиотеку в свой проект, открываем RS.h, и задаём параметры:

#define MM  8    //2 в степени 8 равно 256, размер пакета будет на один меньше, то есть 255

#define KK 223   //223, информационных символа дают нам возможность исправить от (255-233) / 2  до (255-233) байт.

Создаём массив данных, размером с полный (после добавления избыточности, в нашем случае 255) пакет, и передаём его функции кодирования    encode_rs(&testArray[0], &testArray[223]);, в качестве второго параметра нужно передать массив  куда складывать избыточную информацию, в простейшем случае это тот же пакет, сразу после полезной информации. Вот его содержимое тестового пакета после кодирования.

Содержание массива с полезными данными и данными для востановления

Содержание массива с полезными данными и данными для востановления

Как видим, до 223 элемента идут исходные данные, а после начались избыточная часть. Кстати если в вашем устройстве нет ресурсов для декодирования, а данные приходят в Риде-Соломоне, то ничего не мешает вам просто воспользоватся тем, что сами полезные  данные не искажаются, и можно просто игнорировать информацию избыточную . Теперь внесём ошибку в пакет, у нас 32 байт избыточной информации, значит без указания места можно повредить до 16 байт.

Теперь повредим содержимое массива

Этот код повредит массив данных, всего 16 байт в трёх группах.

Этот код повредит массив данных, всего 16 байт в трёх группах.

Теперь попробуем восстановить данные.  При восстановлении нужно передавать функции известные позиции повреждений данных, для этого создадим массив, размер массива выбирается по принципу «сколько максимум позиций может быть известно» int eras_pos[16]; и запустим восстановление, где 0 — количество известных позиций повреждений.

result = eras_dec_rs(testArray,eras_pos,0);

В rsult у нас теперь результат востановления, принимает следующие значения:
-1:востановить ошибки не удалось
0:нет ошибок
>0:количество исправленных ошибок

Функция возвратила 16, значит всё ок, и мы видим, что данные исправленны
Данные восстановленны после искажения

Данные восстановленны после искажения

 

Скачать проект для IAR, настроен для выполнения в симуляторе.

Оставить комментарий