быстрый алгоритм, определения отсуствующего байта произвольного массива байтов размером Опции

[sKWO]

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

Сообщение отредактировал sKWO - Jun 1 2007, 10:59

[sergeeff]

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

[ANV]

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

Какая идеология разборки пакета может накрыться???
Выпадение байта (равно как и его искажение при приеме) просто приведут к тому, что что-то не сойдется. Ведь, кроме CRC, может не сойтись межбайтная пауза (ее обрабатывать просто необходимо), сигнатура конца пакета и пр. Инициатор пакета не дождется ответа и просто его повторит. А если ошибок так много, что и в повторных пакетах есть ошибки, то скорее всего у Вас проблема с железом.

...для чего и придумали crc и приамбулу... и в целом протокол обмена
...еще один вариант оформления пакета, здесь пример:

55h 0aah 86h 6h 18h 55h 55h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 55h 5ah
55h 0aah - маркер начала, 55h 5ah - маркер конца, если внутри пакета встречается байт с кодом 55h то он дублируется, т.е. в случае когда весь пакет содержит 55h его реальная длина будет в два раза больше. В примере выше содержимое пакета будет 86h 6h 18h 55h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

Дело в том, что мне кажется, что надежность такой структуры пакета чуть неоптимальна. Добавление своих символов в полезные данные (т.е. зависимость по данным) в некоторых случаях может создавать некоторую избыточность информации в пакете. ИМХО, лучше ее (и не только) направить на более полезные нужды, чем просто передача информации. К тому же, все равно необходимо контроллировать целостность данных (CRC), иногда требуется передать некоторую дополнительную информацию, например, о назначении пакета, некоторые метаданные и др.

В любом случае такой подход имеет право на жизнь, все ведь зависит от задачи. Не так ли?

[tag]

Какая идеология разборки пакета может накрыться???
Выпадение байта (равно как и его искажение при приеме) просто приведут к тому, что что-то не сойдется. Ведь, кроме CRC, может не сойтись межбайтная пауза (ее обрабатывать просто необходимо), сигнатура конца пакета и пр. Инициатор пакета не дождется ответа и просто его повторит. А если ошибок так много, что и в повторных пакетах есть ошибки, то скорее всего у Вас проблема с железом.
Дело в том, что мне кажется, что надежность такой структуры пакета чуть неоптимальна. Добавление своих символов в полезные данные (т.е. зависимость по данным) в некоторых случаях может создавать некоторую избыточность информации в пакете. ИМХО, лучше ее (и не только) направить на более полезные нужды, чем просто передача информации. К тому же, все равно необходимо контроллировать целостность данных (CRC), иногда требуется передать некоторую дополнительную информацию, например, о назначении пакета, некоторые метаданные и др.

В любом случае такой подход имеет право на жизнь, все ведь зависит от задачи. Не так ли?

...подразумевается что внутри пакета между маркером начала и маркером конца и есть доп. и полезная информация, в частности CRC. Что касается избыточности, то насколькоя помню это один из постулатов надежности передачи информации...