Фонтанные коды. Хочется передать некоторый объём текстовых данных через IP-сеть по UDP-протоколу. Объём данных достаточно большой, десятки килобайт. Этого достаточно, чтобы практически заметить такие эффекты, как пропадание отдельных пакетов или перестановку пакетов местами. Какие возможны варианты? Очевидно:
1) использовать протокол с квитированием, наподобии X-modem, например, TFTP;
2) дополнять данные контрольным кодом и перезапрашивать целиком в случае несовпадения (проще, чем протокол с квитированием);
3) использовать какую-либо форму "фонтанного кода" (
https://en.wikiped …ki/Luby_transform_code) для передачи данных и надеяться, что в большинстве случаев возможно переупорядочивание и восстановление потерянных пакетов на принимающей стороне (в крайнем случае возможен перезапрос, как в пункте 2).
Понятно, что вариант 1 в общем случае -- лучший. Но в силу ряда причин (например, в промежутке есть некоторое уже существующее ПО которое уже умеет только запрашивать по команде и сохранять вывод) хочется рассмотреть вариант 3.
Допустим, что число избыточных блоков будет до 50% от исходного, т.е. объём передаваемых данных увеличивается всего в 1.5 раза. Допустим так же, что исходные данные будут побиты на блоки объёмом в ~512 байт, далее согласно алгоритму будут отправлены блоки проксоренные с рядом других блоков и снабжённые заголовком, в котором указываются списки блоков принявшие участие в проксоривании. И каждый такой блок отправится в отдельном пакете. Очевидно, кстати, что даже при 0% избыточных блоков такой алгоритм уже защищает от перестановки блоков местами.
Вопрос, какой способ проксоривания, каких блоков с какими и в каких количествах, наиболее оптимален. Оригинальный алгоритм предусматривает, что для каждого отправляемого блока выбирается как случайное число исходных проксориваемых блоков, так и случайные их номера. Со случайностями оно, конечно, хорошо работает на больших числах блоков, но когда избыточных блоков немного то запросто может дать результат очень далёкий от оптимального.
Очевидны крайние случаи: если избыточность 0%, то проксоривается 1 блок (т.е. не ксорится ничего). Если избыточность в 1 блок, то оптимальным вариантом является добавить блок проксоривающий все прочие блоки (тогда он может заместить любой один потерянный блок). Можно ли как-то продолжить эти рассуждения?
Например, при избыточности в два блока, нет смысла во втором точно таком же проверочном блоке, он должен чем-то отличаться. Например, если он будет ксорить только половину входных блоков, то сможет заместить любой из этих блоков. И тогда можно терять уже два блока, один из которых не должен входит в число проксоренных для второго избыточного блока.
Можно продолжить далее и получить большее число избыточных блоков, первый из которых ксорит все N входных блоков, второй первую половину, третий первую и третью четверть... последний половину блоков через один. Например для восьми входных блоков можно получить:
блок 0: + . . . . . . .
блок 1: . + . . . . . .
блок 2: . . + . . . . .
блок 3: . . . + . . . .
блок 4: . . . . + . . .
блок 5: . . . . . + . .
блок 6: . . . . . . + .
блок 7: . . . . . . . +
пров. блок 1: x x x x x x x x
пров. блок 2: x x x x . . . .
пров. блок 3: x x . . x x . .
пров. блок 4: x . x . x . x .
Мне начинает казаться, это какой-то код Рида-Соломона...
Для других размеров получается log2(N)+1 проверочных (избыточных) блоков для N входных блоков. В случае восьми изначальных блоков, добавляется 4 проверочных блока, в случае 16-и -- 5 проверочных блоков и т.п.
В случае 8-ми изначальных блоков и 4-х проверочных можно потерять до 4-х любых блоков и информация может быть восстановлена.
Но насколько оптимален такой способ формирования избыточных блоков? И самое главное, непонятно как дальше увеличивать избыточных блоков, хотелось бы больше, чем log2(N), что-то прямо-пропорциональное N (но не сильно большее). Исходя из того, что для каждого входного блока есть небольшая вероятность его пропажи.
И потом неудобно, как-то уравнения эти решать, что понять чего с чем ксорить для восстановления блоков. По-моему я что-то упускаю, может кто подскажет.
Уж очень матрица, практически буквально, напоминает такую же матрицу Хэмминга (только там минимизируется расстояние) или BCH, или коды Рида-Соломона.
Но хотелось бы какой-то простейший способ. Есть современные сложные алгоритмы описанные в RFC например, но их проблема в том, что они громоздкие и сложные.