Arduino.ru

Этот материал для тех, у кого возникает проблема неуверенного приёма цифрового сигнала из линии связи или не слишком надёжного хранилища, когда данные приходят с некоторым количеством ошибок. Конечно, проблема проблеме рознь и в первую очередь следует озаботиться улучшением программных и схемных решений, для исключения источников помех и уменьшения их влияния. Но нередки ситуации, когда все средства исчерпаны, а данные всё равно приходят с ошибками.

Простейший вариант – добавить к данным надёжную контрольную сумму и, в случае обнаружения ошибки, перезапросить отправку пакета, но это не всегда возможно. Решением здесь может стать использование для передачи данных т.н. корректирующих (помехоустойчивых) кодов, специально предназначенных для обнаружения и исправления ошибок передачи (англ. ECC — «error-correcting code», например, если Вы видели маркировку ECC на платах памяти, то это именно оно и есть).

Я не буду здесь останавливаться на лежащей за этими кодами математике. Она очень красива, но это тема отдельной большой статьи, а скорее - серии статей. Те, кому интересны математические подробности и соответствующая теория, могут почитать фундаментальную книгу Питерсона и Уэлдона «Коды, исправляющие ошибки». Изд. «Мир», 1976, которая доступна в сети, или же начать со статьи на Хабре.

Здесь же я опишу небольшую библиотеку, реализующую кодировку Рида-Соломона – одного из наиболее распространенных корректирующих кодов.

Почему именно кодировка Рида-Соломона? Сам я не считаю себя особо компетентным в этих вопросах, поэтому просто положился на мнение специалистов, которые выбрали именно эту кодировку для передачи данных с аппарата «Вояджер» на расстояние в двадцать миллиардов километров, для корректировки ошибок в CD-ROM и очень много для чего ещё.

Если нужно передавать данные с большими скоростями, то лучше использовать аппаратные кодировщики/декодировщики (например, IPC4507, CS3110/12, SAA7207H и ещё много, поищите Reed-Solomon encoder decoder IC datasheet), но это не самые дешёвые микросхемы, да и использовать их на скоростях передачи в десятки килобод – из пушки по воробьям, они, по большей части, на мегабоды заточены.

Суть применения метода Рида-Соломона

Чтобы воспользоваться кодировкой Рида-Соломона, необходимо заранее оценить количество ошибок, которое может возникнуть на Вашей линии связи (обозначим его через E) при передаче сообщения длинны N. Тогда, если при передаче в сообщение вкрадутся E или меньше ошибок, то Вы сможете полностью, гарантированно восстановить исходное сообщение. При этом передаваемое сообщение будет содержать P=N-2xE байтов полезной информации и 2хЕ служебных байтов.

Как оценить величину E? Да как сможете. Могу рассказать, как я это делал при решении задачи, которая и привела меня к созданию этой библиотеки.

Мне нужно было передавать пакеты размером в P=23 байта. Я выбрал «окно» размером в 64 байта (оставил запас на «служебную информацию) и запустил «бесконечную» передачу (заведомо зная что именно я передаю). На принимающей стороне фиксировал ошибки. Тест длился целую неделю. В результате я узнал, что за неделю непрерывной работы, максимальное количество ошибок на 64 байта сообщения составило 6. Т.е. никакие подряд идущие 64 байта не содержали более шести ошибок. Поскольку коэффициент Мэрфи обычно принимают равным π, я выбрал E равным 19 (6xπ) и, думаю, что этого хватит. Таким образом, я передаю пакеты в 23 + 19х2 = 61 байт и, если количество ошибок на пакет не превысит 19, у меня всё будет в порядке – я восстановлю исходное сообщение.

Итак, когда известны допустимое количество ошибок (E) и размер полезных данных (P), необходимо закодировать сообщение (получится пакет размера P+2хE) и передать его. А на принимающей стороне раскодировать. Если при этом ошибок оказалось не больше, чем E, то сообщение будет полностью восстановлено. Если же их окажется больше, то Вы по, крайней мере, об этом узнаете (не примете неудачно раскодированное сообщение за правильное). Последнее утверждение имеет одно исключение, см. раздел «Где лежат грабли» ниже.

Библиотека содержит две базовые функции – одну для кодирования и одну для декодирования (кто бы мог подумать!). Кроме того, там есть ещё две функции и три макроса, которые являются обёрткой (синтаксическим сахаром) для базовых и призваны предельно упростить использование библиотеки в простых случаях.

Базовые функции библиотеки:

Параметры у них одинаковые:

buf - адрес буфера, содержащего в начале 2хЕ байтов для служебной информации, а после них полезную информацию. Для rsEncode эти 2хЕ байтов могут содержать что угодно, функция просто заменит их чем нужно, а для rsDecode - это просто буфер, полученный из линии связи как есть.

Е - допустимое количество ошибок

bufSize - размер буфера (целиком, включая и полезную, и служебную информацию).

Возвращаемые значения:

rsEncode - возвращает одно из следующих значений:

RSE_NO_ERROR - всё в порядке

RSE_NOT_ENOUGH_MEMORY - не хватило памяти для выполнения операции (см. ниже)

RSE_BUFFER_TOO_SMALL - буфер слишком мал (меньше 3-х байтов)

RSE_LARGE_AMOUNT_OF_ERRORS -величина Е слишком велика для указанного размера буфера

rsDecode - в случае нормального завершения функция возвращает неотрицательное число, равное количеству ошибок, которые удалось исправить. В случае же ошибки, возвращает одно из следующих значений:

RSE_TOO_MANY_ERRORS - пакет содержит более, чем E ошибок

RSE_NOT_ENOUGH_MEMORY - не хватило памяти для выполнения операции (см. ниже)

RSE_BUFFER_TOO_SMALL - буфер слишком мал (меньше 3-х байтов)

RSE_LARGE_AMOUNT_OF_ERRORS -величина Е слишком велика для указанного размера буфера

Для работы функциям нужна дополнительная память которую они динамически запрашивают (а перед выходом освобождают). Размер запрашиваемой зависит от Е и равен: для rsEncode - 7+4хЕ, а для rsDecode - 20+14хЕ байтов. Если память выделить не удалось, функции вернут RSE_NOT_ENOUGH_MEMORY. Это лучше бы всегда проверять.

Ну, теперь мы готовы запустить первый пример. Чтобы не усложнять, здесь опущены проверки на возвращаемые значения. В примерах же, прилагаемых к библиотеке всё делается как надо.

Надеюсь, этот пример полностью самодокументирован и в дополнительных комментариях не нуждается.

Мне очень не нравится строка №12. Непонятно, зачем служебная информация располагается перед полезной, а не после (и какой идиот так сделал!). Если бы она была после, то строку №12 можно было бы просто выбросить, чтобы мозг не выносила. Но, уж, как сделано, так сделано, переделывать лень.

Для того, чтобы не париться с размером и спецификой формирования буфера, к библиотеке был добавлен

Синтаксический сахар:

который состоит из трёх макросов для формирования правильного буфера и двух функций «обёрток» для наших базовых функций.

Макрос DECLARE_PAYLOAD(name, type, errors)

Создание буфера. Первый параметр – имя переменной, которую нужно создать (собственно имя будущего буфера). Второй параметр – тип данных полезного сообщения. И третий параметр – выбранная величина E.

Заметьте, что полезное сообщение – это всегда один элемент данных некоторого типа. Если число, то число указанного вторым параметром типа, если структура – то структура. Если требуется передавать массив фиксированного размера, то необходимо описать соответствующий тип и именно этот тип использовать в качестве второго параметра. Чуть ниже мы это проделаем.

Тип может быть почти любым. Не допускаются виртуальные методы и наличие неумолчательного конструктора.

Макрос создаст переменную с именем, которое задано первым параметром у которой будет поле payload. Это поле будет иметь тип, указанный вторым параметром, и именно через него Вы можете заполнять пакет полезной информацией (и вытаскивать информацию после декодирования на принимающей стороне).

Заметьте, что данный макрос не позволяет инициализировать полезные данные при объявлении. Их можно задать только во время выполнения через поле payload.

Макрос DECLARE_PAYLOAD_INIT(name, type, errors)

Тоже самое, что и предыдущий макрос, но здесь позволяется инициализировать полезные данные. Инициализацию следует писать сразу после вызова макроса. Пишется она по правилам инициализации переменных типа, указанного вторым параметром.

Сразу же после данных для инициализации, следует вызвать макрос END_OF_DECLARE_PAYLOAD_INIT, который и завершит описание. У макроса END_OF_DECLARE_PAYLOAD_INIT параметров нет.

Поскольку данные здесь инициализируется, используемый тип имеет право иметь неумолчательный конструктор. Виртуальные методы по-прежнему запрещены.

Обёрточные функции называются rsEncode и rsEncode (вызываются БЕЗ указания пространства имён). У обеих единственный параметр – переменная объявленная одним из макросов DECLARE_PAYLOAD или DECLARE_PAYLOAD_INIT. Возвращают они те же самые значения, что и соответствующие базовые функции, описанные выше.

Чтобы показать, насколько эти макросы и обёрточные функции упрощают жизнь, запишем вышеразобранный пример с использованием макроса DECLARE_PAYLOAD

а теперь с использованием макроса DECLARE_PAYLOAD_INIT

Проще ведь, чем было с базовыми функциями?

Где лежат грабли

Выше было сказано, что метод достаточно безопасен. Если ошибок при передаче окажется не больше, чем Е, то всё восстановится, а если больше, то функция декодирования вернёт RSE_TOO_MANY_ERRORS, т.е. ошибка не проскочит незамеченной.

Встаёт вопрос, а может ли получиться так, что ошибки (в количестве, большем, чем Е) совпадут таким образом, что сообщение правильно декодируется, но с перевранными данными? Ответ - теоретически возможно, но вероятность этого такая же, как того, что мой кот Матвеич «натопчет» на клавиатуре точную копию этого поста. В принципе, конечно, возможно.

Но грабли таки есть! Дело в том, что если полезная часть пакеты полностью состоит из нулей, то и служебная будет содержать только нули. И тут уж возможны варианты! Например, если Вы на принимающей стороне объявите буфер глобально (он будет заполнен нулями), а приём у Вас по каким-то причинам сорвётся - вообще ничего не примете, то такой заполненный нулями буфер успешно декодируется, покажет ноль ошибок и радостно выдаст Вам эти нули в качестве результата. Чтобы этого не случилось, следите, чтобы разумное сообщение никогда не состояло только из нулей. Например, добавьте к нему один байтик и всегда пихайте туда единицу. Тогда на принимающей стороне, Вы, проверив эту единицу, всегда сможете отличить реально пришедшие нули от ошибочных.

Ну, собственно и всё.

Библиотека живёт на гитверзе. К ней прилагаются семь примеров:

1. Передача числа типа long с использованием DECLARE_PAYLOAD_INIT
2. Передача числа типа long с использованием DECLARE_PAYLOAD
3. Передача массива из 10 элементов типа int с использованием DECLARE_PAYLOAD_INIT
4. Передача массива из 10 элементов типа int с использованием DECLARE_PAYLOAD
5. Передача сложной (с блэкджеком и девочками) структуры с использованием DECLARE_PAYLOAD_INIT
6, Передача сложной (с блэкджеком и девочками) структуры с использованием DECLARE_PAYLOAD
7. Передача русского текста с использованием только базовых функций

Чистых Вам линий!