Есть ли алгоритм кодирования, который не допускает подряд 3-6 одинаковых значений?

Question

[Kalombyr]

Здравствуйте!
Два устройства общаются через com-порт. Пусть будут Arduino, т.к. тестирую на них.
Нужно как-то отделять пакет от пакета, при условии, что в потоке возможны искажения. Понятно дело, контрольные суммы, контроль чётности и т.д.
Но вот встал вопрос, как лучше разделять "пакеты" (последовательность байт) ?
Пока что ставлю подряд 3 нуля. В идеале, ищу какой-либо простой и быстрый алгоритм кодирования/декодирования байт, который бы позволил избежать несколько подряд (ну скажем от 3 до 6) одинаковых фиксированных значений (то есть мне нужно заранее знать, что бы его поставить разделителем)
Думал просто к каждому третьему байту добавлять единицу, но тогда проблема: если искажение будет в нём при передаче и он станет равным 0.

Answer 1

[dollar]

Контрольная сумма (хеш).

Если искажение и будет, то шанс его не обнаружить - один на миллион (на самом деле ещё меньше, хотя зависит от разрядности).

Comments

[Kalombyr]

Но что бы мне её из потока байт получить, нужно как-то понять, где она начинается.

[dollar]

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

[Kalombyr]

dollar, я правильно понял, Вы предлагаете каждый вновь пришедший байт добавлять к контрольной сумме (ещё нужно такую найти, для которой не требуются все байты разом) и, как только она совпадёт, то значит, пакет полностью пришёл?

Допустим, а как тогда быть, если, в следующем пакете в первом байте контрольной суммы есть ошибка?
Тогда получается, что все остальные байты уйдут в "мусор" и всё равно придётся как-то понять, где начинается следующая, предположительно "правильная" контрольная сумма.

[dollar]

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

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

Контрольная сумма выигрывает простотой реализации. Берём для неё 64 бита. Добавляем соль, чтобы исключить типичную ситуацию, когда поток состоит из нулей. Можете сами посчитать, каков шанс, что пакет случайно соберется сам. К тому же сборка следующего пакета начнётся сразу после предыдущего. Так что считать ошибку можно лишь в первом пакете (при условии, что ошибки вообще достаточно редки). Плюс в самом пакете должна быть какая-то структура, скорее всего. Хотя бы его длина (если она не фиксирована). Это тоже как бы плюс к разрядности контрольной суммы.

Конечно, ошибка испортит пакет, и тогда придётся искать начало следующего попытками собрать его. Но если ошибки так уж прям часты, то скорее всего нужно уже не алгоритм искать, а фиксить саму среду, по которой передаются данные. А чисто алгоритмически можно увеличить разрядность. Поднимите её до 128 бит, это уже астрономическая точность, хоть и не 100%. При такой точности ваше устройство скорее сгорит, утонет или будет украдено, чем допустит ошибку в пакете. Поднимите ещё, если мало.

Полностью решать задачу за вас я и не собирался. Просто отвечаю на вопрос про "простой и быстрый алгоритм кодирования/декодирования байт". Ответом является контрольная сумма. Точнее, ссылка на статью вики про хеш-функции. А дальше сами думайте, как вам там удобнее. Хотите разделитель - пожалуйста, делайте. Можете перед пакетом ставить какой-то неповторимый разделитель. Если он вдруг будет искажен в пакете, это тоже будет означать потерю пакета, но как по мне - слишком много информации тратится и слишком мало выхлопа в плане проверки пакетов по сравнению с контрольной суммой, в которой можно просто наращивать разрядность, и точность будет расти по экспоненте.

[xmoonlight]

dollar, Kalombyr, Вы обсуждаете тут разные вещи.
А именно, спутаны в тексте "поток" и "пакет".

Kalombyr, просит дать алгоритм разделения потока на пакеты.
А dollar говорит про контроль целостности ОДНОГО! пакета.

Т.е. то, про что говорит dollar однозначно стоит применять внутри ОДНОГО пакета, но только не хеширование, а любым алгоритмом с проверкой чётности, например.
В общем, похожим, но менее затратным в плане вычислительной нагрузки для формирования контрольных разрядов (контрольная сумма пакета) для ОДНОГО пакета.

[dollar]

xmoonlight, нет, я говорю, что хеш можно использовать в том числе и для разделения на пакеты внутри потока. Получается 2 в 1.

[xmoonlight]

dollar, только, если все длины строго фиксированные. Да?

[dollar]

xmoonlight, нет. Если длина не фиксирована, то где-то там сразу до/после (зависит от структуры пакета) будет указана длина, которая будет участвовать в попытке собрать пакет.

Но, как я говорил выше, многое зависит от нюансов. Если нужно шифрование, например, то всё сильно усложняется.

[xmoonlight]

dollar, а как эти все поля-то различать?
весь пакет, данные пакета, длина пакета, разделитель между пакетами: где что - как понять?

[dollar]

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

[dollar]

xmoonlight, и если длина не фиксирована, то так тоже просто. Например, длина в самом начале пакета для удобства. Заранее обговариваем, что она не больше X и не меньше Y, что отсекает сразу кучу вариантов. Далее ждём, когда придут все данные (согласно заявленной длине). Затем смотрим на другие характеристики пакета. Какие-то поля должны тоже удовлетворять каким-то условиям, ограничениям. Если что-то не так, списываем на искажение данных и идём дальше. Ну а если со структурой всё ок, то вишенкой на торте считаем контрольную сумму.

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

Если не секрет, зачем вы перебираете решения для всех возможных кейсов, которые автор даже не назвал? Вы же в курсе, что 100% универсальности не существует. Более-менее универсальный вариант (не 100%) всё же возможен, но за универсальность нужно платить. А у автора вопроса вообще вполне себе конкретный вариант. Просто деталей мы не знаем. Да и они уже не уместны будут в этом абстрактом вопросе, лучше новый вопрос задать.

[Kalombyr]

dollar, спасибо! Пожалуй, так и поступлю.

[xmoonlight]

dollar,

только, если все длины строго фиксированные. Да?

нет. Если длина не фиксирована, то где-то там сразу до/после (зависит от структуры пакета) будет указана длина, которая будет участвовать в попытке собрать пакет.

и если длина не фиксирована, то так тоже просто. Например, длина в самом начале пакета для удобства. Заранее обговариваем, что она не больше X и не меньше Y, что отсекает сразу кучу вариантов. Далее ждём, когда придут все данные (согласно заявленной длине). Затем смотрим на другие характеристики пакета.

Понятно... )

Answer 2

[Pavel K]

Доброго дня.
Если я правильно понял, то, алгоритма то не требуется (можно применить сжатие LZW, но, боюсь, Ардуинка половину времени будет вычислять его, что явно не устроит).

По-моему, проще будет пробежаться по байтам и вместо 0 0 0 0 0 вставлять 0 N, где N - их количество (если не хотите возиться со сдвигом массива, то вместо остальных ставьте любое значение, потом только при парсинге поставите обратно).
Но вот если 0 действительно один, то всё равно придётся вставлять дополнительно 0 1, иначе будет не отличить где один, а где несколько.

И вообще "0" - хреновый разделитель, т.к., по-моему, самое часто встречающееся значение в потоке обмена. Лучше уж 42.

Comments

[Kalombyr]

Спасибо! Всё было бы замечательно, если бы не приходилось перед одиноким 0 добавлять его количество - обработка существенно усложняется. Сжатие по LZW существенно усложняет, да.
Вверху $ написал ответ. Буду использовать разделитель + контрольную сумму и пытаться собрать пакет.

Answer 3

[xmoonlight]

одинаковых фиксированных значений

почему не хотите, чтобы они были разными?!)
Просто исключите нужную последовательность, используя её же в качестве xor-ключа (с повторами при превышении данными длинны ключа) при кодировании/декодировании данных.
В итоге: никогда не будет в последовательности данных пакета разделителя пакетов.

Comments

[Kalombyr]

Спасибо, но, допустим, массив такой:
1 2 3 0 0 0 5 6 7 0 0 0 9
разделитель, а так же ключ 5 6 7
Нахожу в данных последовательность 5 6 7, если я сделаю xor, то тогда просто получу нули.

А как при декодировании быть, если в итоге в массиве будет куча нулей рядом идущих?

[xmoonlight]

Kalombyr, А какая разница что там рядом?!
Вы же ВСЕГДА! применяете снова ОДИН И ТОТ ЖЕ! xor и ВСЕГДА! получаете изначальные закодированные данные.
1. Длина данных (размер пакета) от нулей - вообще никак не меняется.
2. Вы же не как с текстом (надеюсь!) работаете с пакетом?!))

[Kalombyr]

xmoonlight, извините, Вы немогли бы подробнее расписать?
Вот, например, данные ДО: 1 2 3 0 0 0 5 6 7 0 0 0 9, ключ 5 6 7, как будут выглядеть данные на отправку?

[xmoonlight]

Kalombyr, ну тут байты же будут при XOR. А текст байты - ну никак не напечатает так, как они будут))
Ключ растягивается до длины данных: 5675675675675 и дальше - делаете XOR.

Answer 4

[Александр Скуснов]

1) манчестерское кодирование
2) шина CAN (служебные биты автоматически следят за ошибками)

Comments

[Kalombyr]

Увы, у меня не транспортный уровень.

Answer 5

[mayton2019]

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