(
https://dl.dropboxusercontent.com/u/6706516/RS_and_XTEA.rar)
Вдруг кому-то интересно будет:
1. Шифровалка XTEA.
2. Корректирующие коды Рида-Соломона;
Шифровалка — в качестве примера выдрал кусок из своей проги, отрезав всё лишнее. Комментарии внутри.
А RS — "древние утерянные знания прошлых веков".
На их основе сначала пробовал работу алгоритма с длиной слова 4, 5 и 6 бит.
Потому что у младшего микроконтроллера сил на большее не хватало.
Теперь с Pic24 перешёл на 8-битное слово.
Теорию (про поля Галуа и пр.) каждый может поискать в гугле.
А практика такая:
Выбрав длину слова m получаем максимальную длину блока — n = 2^m - 1
Для привычных 8-битных байтов m = 8 и n = 255.
Внутри блока выделяем некоторое количество пар слов под контрольные.
Число выделенных слов должно быть чётное = 2 * t
И тогда для собственно данных остаётся вот столько слов:
k = (n - 2 * t)
Маленькая хитрость.
Если надо передавать немного инфы, так что контрольные и данные уменьшаются в блок меньшего размера, то можно спокойно остаток блока забивать (например) нулями, кодировать, полностью обрабатывая весь блок, а передавать только нужную часть, без нулей.
А при приёме, приняв контрольные и данные, остаток блока опять забивать нулями. Как бы нули передались виртуально, причём совершенно без помех.
А потом уже натравливать на полный блок декодирование.
Если число ошибок не более t, то алгоритм их всех исправляет.
Если больше, и исправить не может, то оставляет как есть, сообщая об ошибке.
Но иногда при большом числе ошибок случаются ложные исправления — алгоритм считает, что исправил, а на самом деле получилась фигня.
Это случается при небольшом числе контрольных слов.
Количество ложных исправлений не зависит от длины передаваемого блока (урезанный или полный). И, похоже, не зависит от превышения числа ошибок над t.
Для байтовых слов получается примерно так:
t = 6 — ложных исправлений около 1/1000.
t = 7 — 1/6000.
t = 8 — 1/50000.
Для приёмников часто приводят "чувствительность при частоте ошибок 1/1000".
Если есть коррекция ошибок, то можно приёмник отодвинуть на большее расстояние, ухудшившееся отношение сигнал/шум будет компенсировано коррекцией участившихся ошибок. При том же уровне ошибок 1/1000 расстояние будет больше (таблица для блока 912 бит = 114 байт):
t = 08 — 08.4 — 1.311 — 98 байтов
t = 10 — 10.6 — 1.362 — 94 байтов
t = 12 — 12.8 — 1.408 — 90 байтов
t = 17 — 18.7 — 1.512 — 80 байтов
t = 22 — 25.0 — 1.609 — 70 байтов
t = 27 — 31.5 — 1.700 — 60 байтов
Третья колонка — увеличение расстояния.
Вторая колонка — это средняя граница числа ошибок. Когда в одно слово попадает больше одной битовой ошибки, для алгоритма это всего одно испорченное слово.