Помогите с помехоустойчивым кодированием

← →
kami © (2008-09-04 13:46) [0]

Суть задачи:
имеется устройство, отправляющее на компьютер№1 пакетные данные по UDP. Эти данные разбиваются на под_пакеты, снабжаются служебной информацией и отправляются через несколько низкоскоростных каналов (dial-up модемы) на компьютер№2, который собирает из них исходные пакетные данные.
Проблема в том, что (само собой) под_пакеты, отправляемые так же по UDP, не всегда доходят до компьютера №2. Это не есть смертельно (данные - видеопоток, и теряют свою актуальность почти сразу же), но весьма неприятно, когда оказываются несобранными несколько пакетов (а то и десятков) подряд.

Возникла мысль добавить избыточность в исходный пакет, чтобы при потере хотя бы 1 (лучше 2) под_пакетов (из 8 на данный момент) можно было бы восстановить исходный.

В интернете нашел в основном общие фразы и математические описания кодов Рида-Соломона, Хемминга и т.д. Но, т.к. в математике я не силен (мягко говоря), то это мне мало что дало, кроме общего понимания. Да и насколько я понял, эти коды дают возможность побитового восстановления, а мне нужно несколько другое. Не подскажете, где можно почитать про решение такой задачи (интересует сам алгоритм, на исходники я не рассчитываю).

← →
Правильный$Вася (2008-09-04 14:01) [1]

это не помехоустойчивость
помеха - это порча данных, а не пропадание их вовсе
поменяй протокол на с гарантированой доставкой или используй эту самую избыточность, хотя она вряд ли поможет сильно
для восстановления одного бита в байте нужно (не помню точно) не менее 2 излишних битов, что увеличит количество пакетов на 25%, а если они будут теряться с прежней же вероятностью, то ты только увеличишь трафик практически без увеличения качества

← →
Rouse_ © (2008-09-04 14:18) [2]

Вот это посмотри, с исходниками:
http://www.insidepro.com/kk/027/027r.shtml

← →
kami © (2008-09-04 18:36) [3]

> Правильный$Вася (04.09.08 14:01) [1]
> это не помехоустойчивость
Возможно, не силен в терминологии.
> поменяй протокол на с гарантированой доставкой
нельзя. Канал может улучшаться/ухудшаться, а данные идут непрерывно. Задержка одного из низкоскоростных направлений для гарантированной доставки под_пакета затормозит и все остальные, что недопустимо. Такая реализация тоже есть, но она "признана недееспособной" и нормально работает только с каналами, обеспечивающими хорошую пропускную способность.

> или используй эту самую избыточность, хотя она вряд ли поможет сильно
> для восстановления одного бита в байте нужно (не помню точно)
> не менее 2 излишних битов, что увеличит количество пакетов
> на 25%, а если они будут теряться с прежней же вероятностью,
> то ты только увеличишь трафик практически без увеличения
> качества
Вот именно, что мне нужно восстанавливать не биты, а целые фрагменты пакета (пакеты идут длиной от 400 до 1400 байт и разделяются (на данный момент) на 8 частей).
Единственное, что пришло в голову - дублировать под_пакеты через разные каналы, но - это увеличение трафика в 2 раза :(

> Rouse_ © (04.09.08 14:18) [2]
> Вот это посмотри, с исходниками:

Спасибо, уже смотрю.

← →
Leonid Troyanovsky © (2008-09-04 18:45) [4]

> kami © (04.09.08 18:36) [3]

> Единственное, что пришло в голову - дублировать под_пакеты
> через разные каналы, но - это увеличение трафика в 2 раза

Дык, чудес не бывает.
Либо неспеша принять весь стрим, отвергая непонятое (и требуя повтора).
Либо мириться с пропусками.

--
Regards, LVT.

← →
kami © (2008-09-04 21:54) [5]

> Leonid Troyanovsky © (04.09.08 18:45) [4]
> Дык, чудес не бывает.

Это я понимаю прекрасно. Но хотелось бы для гарантированного восстановления "куска" в 12-14% информации увеличивать трафик не в 2 раза, а в лучшем случае 1,25-1,5 раз, на что можно пойти почти безболезненно :)

← →
kami © (2008-09-04 21:56) [6]

> Rouse_ © (04.09.08 14:18) [2]

Наскоком не получилось - последний пример, с использованием сторонней библиотеки способен исправить 52 байта максимум из 2048 исходных :)
Сижу, разбираю предыдущий пример. Только такое ощущение, что работать будет непозволительно долго.

← →
Правильный$Вася (2008-09-04 22:11) [7]

> способен исправить 52 байта максимум из 2048 исходных

и сколько из 2 кб являются избыточными?

← →
kami © (2008-09-04 22:28) [8]

> Правильный$Вася (04.09.08 22:11) [7]
> и сколько из 2 кб являются избыточными?

2048 - это полезная информация, к ней добавляется 304 байта "сопровождения".
В общем, исправление последовательности в 52 байта из 2048 - это 2,5%. Это мало, нужно 12-14 %, чтобы восстановить 1 потерянный кусок пакета.

← →
kami © (2008-09-04 22:29) [9]

+ в каждом под_пакете передается моя служебная информация в 6 байт весом

← →
Правильный$Вася (2008-09-04 22:41) [10]

> 2048 - это полезная информация, к ней добавляется 304 байта
> "сопровождения".

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

> т.е. уже больше четверти от полезной инфы

Да и пусть, не особенно волнует.

> она добавляется к каждому подпакету или ко всему пакету
> в целом?

Пока еще никуда не добавляется, это был только тест

Нет, я наверное, неправильно выразился.
Перевел и скомпилировал проект по ссылке Rouse_ © (04.09.08 14:18) [2]

Тот код позволяет исправить 52 байта из 2048 полезных (длина=2048 байт не обсуждается - особенность сторонней библиотеки). Итого - 2,5% полезной информации.

У меня же немного другая ситуация: исходный пакет <=1400 байт, разделяется на 8 частей <= 175 байт каждая (полезной информации).
Определяемся, что допустима потеря 1 части, то есть 12,5%.
Служебную информацию (как "мою" для идентификации под_пакетов, так и для восстановления потерь, если ее размер не превышает 50% от общего объема полезной) в расчет не принимаем.

← →
Smile (2008-09-04 23:04) [12]

Что ж это за такие низкоскоростные каналы,в которых теряются пакеты?

> а то ведь потеря подпакета с информацией восстановления приведет к потере всего пакета

Если действительно определение, что допустима потеря 1 части - достаточно продублировать информацию для восстановления исходного пакета в 2 под_пакетах для гарантированного ее приема.

> Smile (04.09.08 23:04) [12]
> Что ж это за такие низкоскоростные каналы,в которых теряются
> пакеты?

обычные dial-up соединения.
А udp пакеты вообще обладают свойством теряться, и не только в низкоскоростных каналах :)

Помогите с помехоустойчивым кодированием Найти похожие ветки