Привет.

В сообщении могут пропадать отдельные байты.
Например, из 32 байтов пришло только 31.
Ворос, как закодировать сообщение, что бы потом его можно было восстановить?
  

можно продублировать сообщение. например в первом случае потеряется 1ый байт во втором - 5, так ты увидиш картину целиком. получается что трафик увеличивается в 2 раза.

А а ещё есть какие-нибудь предложения?

Каков максимальный процент потерь?
Есть ли позиционная или иная зависимость для пропадающих данных?

nworm, Вот попалось случайно 

Для общего случая такого алгоритма нет. Так как могут пострадать и исходные данные и проверочные. 

ksnk, а как с помощью этого восстановить именно пропавшие байты, а не искажённые

Это сейчас изучается.

Пока мне в принципе интересно как бороться именно с пропажей, а не с искажением байтов.

Это сообщение отредактировал(а) nworm - 19.11.2008, 18:47

nworm, Ну, дык, написано-же... по полученой 8-ми байтовой последовательности считать  биты четности. Сверить биты четности с записанными в 6-м байте (с 0-я считаем). Ежели один байт потерялся - восстанавливаем. Если 2 и более - кричим-ругаемся...
Восстановление - вычесть из суммы байт все правильно принятые...

Вообще-то в Гугле можно и уже готовые реализации нарыть...

Добавлено через 56 секунд
O! sorry... пропавшие нужно гуглить ...

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

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

А можно подробнее?
Как вычислять вторую контрольную сумму?

Да как угодно...
Например: имеется массив из 32 байтов. Один любой из них может пропасть, оставшиеся "сдвинутся, закрыв дырку", однако порядок оставшихся байтов не изменится. Для того, чтобы восстановить пропавший байт, достаточно иметь еще один байт, полученный побитным XOR всех байтов. А для того, чтобы восстановить его местоположение... скажем, это может быть стандартный CRC8, и для восстановления точки вставки вычисленного байта потребуется просто посчитать соотв. контрольные суммы для всех возможных его положений и взять совпадающее.

Можно из пальца насосать еще алгоритмов. Необязательно двойная контрольная сумма...

Как выделить из входного потока пакет, если есть вероятность потерять байт 
-- помечать начало пакета специальным байтом. Для подмены этого байта в теле пакета используется подмена (каламбур, господа...). К примеру, для маркера начала пакета выбран байт 0, для "второго" маркера - 0xFF, для третьего - 0xAA. Тогда 0 в теле пакета заменяем на 0xFF,0xFF , простой 0xFF в теле пакета заменяем на 0xFF,xAA. Естественно, разумнее выбрать наименее часто встречающиеся в потоке байт цифры.


-- Итого - пакет: мконтрольная сумма, номер пакета, данные пакета... при передаче первым посылаем маркер, затем подвергнутые "подмене" байты пакета. При приеме, все немаркеры прогоняем через обратную "подмену".
-- номера пакетов должны идти последовательно
-- Корректен пакет или нет - проверяется контрольной суммой. К контрольной сумме прикладываем полученные байты, пока не получим 0 - пакет получен полностью. Если получили непредвиденный маркер - пакет потерян. Если за концом пакета следует немаркер - пакет потерян
--За полностью принятым пакетом должен следовать маркер.

За группой из Х пакетов следует пакет восстановления - пакет максимальной в группе длины, после которого нумерация пакетов сбрасывается.
Пакет восстановления является суммой побайтно всех предыдущих пакетов, добитых 0-ми до максимального размера... восстанавливается отниманием всех правильно принятых.

ksnk
Как проверить целостность принятой информации - очевидно, и тут как раз велосипеда изобретать не надо. Простой CRC сделает это с большой точностью, вероятность коллизии очевидно мала. Только не об этом речь. 

А вот восстановление исходного состояния пакета на основе присланной в его составе избыточной информации - это уже гораздо менее отработанная технология, и именно о ней речь.


Расскажи-ка ты мне, что будет, если в каждом пакете пропадёт по одному байту?

 Ну, это просто. Контрольная сумма пакетов не совпадет - пакет отбросится. 2 пакета в группе ушли - группа отбросится - нужно начинать процедуру сброса канала...

Добавлено через 2 минуты и 41 секунду
Контрольный пакет - также защищен контрольной суммой.

Добавлено через 8 минут и 26 секунд
Допустимая плотность ошибок - одна на группу пакетов. Если больше - линия передачи плохая - связиста вызывать надо...