Еще проще просто сумма, качество обнаружения ошибки падает, но не критично
На самом деле зависит от конкретной ситуации. Например, при параллельной передаче байте, если одна из шин битая (всегда 0 или 1), то "просто сумма" этой ошибки не увидит вообще, а CRC - увидит.
Если же говорить о МК, то лучше сочетать "просто сумму" с контролем четности. Тогда не только всегда выявим двойную ошибку в блоке данных, но и сможем исправить одиночную. Для примера. Пусть мы передает по последовательному каналу байты. Пусть блок у нас 8 байт. Добавляем к каждому передаваемому байту бит четности и после каждых 8 байт пересылаем сумму (XOR) этих 8 байтов девятым контрольным байтом. Тогда, если ошибка была в одном бите, то не совпадет бит четности в ошибочном байте и один бит в контрольной сумме. То есть, если инвертировать в ошибочном байте тот бит, который не совпал в контрольной сумме - ошибка будет исправлена.
На самом деле зависит от конкретной ситуации. Например, при параллельной передаче байте, если одна из шин битая (всегда 0 или 1), то "просто сумма" этой ошибки не увидит вообще, а CRC - увидит.
Увидит, передаем 0000 и 0000 сумма 0000, битая шина в 1 установлена, в итоге приняли 0001 и 0001, посчитали контрольную контрольную сумму 0010, ничего не совпадает.
Совпадет XOR, сумма по модулю 2, двойная ошибка может легко проскочить. А полная сумма немного перемешивает биты между собой и это хорошо.
Цитата:
Если же говорить о МК, то лучше сочетать "просто сумму" с контролем четности. Тогда не только всегда выявим двойную ошибку в блоке данных, но и сможем исправить одиночную.
Цитата:
Для примера. Пусть мы передает по последовательному каналу байты. Пусть блок у нас 8 байт. Добавляем к каждому передаваемому байту бит четности и после каждых 8 байт пересылаем сумму (XOR) этих 8 байтов девятым контрольным байтом. Тогда, если ошибка была в одном бите, то не совпадет бит четности в ошибочном байте и один бит в контрольной сумме. То есть, если инвертировать в ошибочном байте тот бит, который не совпал в контрольной сумме - ошибка будет исправлена.
Да, типа по столбикам и строкам отдельно биты четности.
Только контрольная сумма очень слабая. 2 сбойных бита в одном столбике и 2 бита в строке дадут иллюзию правильных данных. Или 3 сбойных бита, а мы восстанавливая данные портим 4й бит и получаем иллюзию целых данных. Нужна гарантия что сбойных бит всего 1. По хорошему всё это хозяйство нужно подписать правильной CRC.
В своей задумке я воспользовался аппаратными возможностями STM32. Расчет КС может быть по ширине 16 или 32 бита. По скорости все равно 1 такт (по datasheet ?). Расчет остатков всяко дольше.
Только контрольная сумма очень слабая. 2 сбойных бита в одном столбике и 2 бита в строке дадут иллюзию правильных данных.
Если у Вас прут три ошибки на 64 бита, то Вам уже никакое CRC не поможет, только БЧХ-коды. Потому что CRC не позволяет исправлять ошибки и Вы ни один пакет через такой зашумленный канал доставить не сможете.
Почти вся ECC память ошибку в одном бите 64-х битного слова (8 байт, как и у меня) исправляет, в двух детектирует, в трех может пропустить. Разница только в том, что ECC память, обычно, использует код Хемминга и избыточность всего 8 бит на 64 бита, тогда как у меня избыточность 17 бит на те же 64 бита.
Только контрольная сумма очень слабая. 2 сбойных бита в одном столбике и 2 бита в строке дадут иллюзию правильных данных.
Что-то у Вас не то с математикой. Нечетное количество ошибок механизм расчета битов четности и по строкам и по столбцам детектирует всегда. Он может пропустить 4 ошибки, причем в очень специфичной ситуации, когда эти ошибки расположены "квадратом" - в одной и той же паре столбцов и строк. На практике, за несколько лет работы с ЕС-овскими магнитными лентами, использующие именно такой принцип кодирования, на блоках данных в 80 байт (такие приходили из СПД), я с пропуском ошибочных данных не столкнулся ни разу!
Качественное и безопасное устройство, работающее от аккумулятора, должно учитывать его физические и химические свойства, профили заряда и разряда, их изменение во времени и под влиянием различных условий, таких как температура и ток нагрузки. Мы расскажем о литий-ионных аккумуляторных батареях EVE и нескольких решениях от различных китайских компаний, рекомендуемых для разработок приложений с использованием этих АКБ. Представленные в статье китайские аналоги помогут заменить продукцию западных брендов с оптимизацией цены без потери качества.
Он может пропустить 4 ошибки, причем в очень специфичной ситуации, когда эти ошибки расположены "квадратом" - в одной и той же паре столбцов и строк. На практике, за несколько лет работы с ЕС-овскими магнитными лентами, использующие именно такой принцип кодирования, на блоках данных в 80 байт (такие приходили из СПД), я с пропуском ошибочных данных не столкнулся ни разу!
Ну я и написал про 4 ошибки, 2+2 ошибки. Кроме 4 ошибок может пропустить 8 ошибок, 12 и так далее. Вплоть до случая с инвертированием данных всех. Вероятность пропуска ошибки в блоке 8*10 байт выше 1/262144 (потому что 2^18), сыпались бы ошибки массово, они бы проходили. Если бы вы считывали 20 971 520 байт очень шумной информации, ошибка бы вылезла на 50% бы, хотя бы одна. И это без восстановления. Если делаем попытки восстановления, изредка будем восстанавливать одни сбойные блоки в другие сбойные блоки. Например если как вы написали сбойные биты пришли по квадрату, только не все 4, а 3 сбойных бита, мы воостанавливаем еще один и получаем квадрат из сбойных битов сделанный из трех сбойных битов. В итоге без восстановления ошибок пропускаем только 4 сбойных бита по квадрату, а с восстановлением данных пропускаем и 3 сбойных бита, которые алгоритм по ошибке восстановит до 4х сбойных бит. Можно в принципе проверить. Программку простую написать и имитировать сбойные пакеты. По моим ощущениям будет чуть хуже CRC по статистике (биты не перемешиваются при ошибке), но работать будет нормально всё ))
Компания EVE выпустила новый аккумулятор серии PLM, сочетающий в себе высокую безопасность, длительный срок службы, широкий температурный диапазон и высокую токоотдачу даже при отрицательной температуре.
Эти аккумуляторы поддерживают заряд при температуре от -40/-20°С (сниженным значением тока), безопасны (не воспламеняются и не взрываются) при механическом повреждении (протыкание и сдавливание), устойчивы к вибрации. Они могут применяться как для автотранспорта (трекеры, маячки, сигнализация), так и для промышленных устройств мониторинга, IoT-устройств.
Вероятность пропуска ошибки в блоке 8*10 байт выше 1/262144 По моим ощущениям будет чуть хуже CRC
Вероятность пропуска ошибки в таком же блоке для CRC16 существенно выше (по Вашему упрощенному расчету - 1/65536), при том, что исправить ошибку он не позволит в принципе. А CRC32 потребует два дополнительных байта, то бишь сравнение некорректно. На самом деле, я не понимаю вообще смысла сравнения кодирования с исправлением ошибок и кодирования с расчетом контрольной суммы. В первом случае, при определенной избыточности, Вы всегда данные передадите. Во втором, в общем случае - никогда.
Вероятность пропуска ошибки в таком же блоке для CRC16 существенно выше (по Вашему упрощенному расчету - 1/65536), при том, что исправить ошибку он не позволит в принципе.
Тоже не корректно сравнивать 16 и 18 бит избыточных данных. В CRC каждый дополнительный бит снижает вероятность ошибки в 2 раза, это очень круто. А вот XOR так не работает, там эффективность растет намного слабее. Может даже в 10 раз хуже CRC будет, лень проверять )) Исправление ошибки достигается высокой ценой, так как снижается надежность обнаружения ошибок и появляется вероятность пропустить 3, 7, 11 бит ошибок расположенных по неполному квадрату в матрице общей. Но это можно компенсировать большой CRC на большом блоке данных. Вот как вы написали блоки маленькие по 80 байт, их можно объединить в огромный блок по 800 байт и подписать CRC32, надежность будет высочайшая и возможность исправления ошибок. И небольшая избыточность.
Цитата:
На самом деле, я не понимаю вообще смысла сравнения кодирования с исправлением ошибок и кодирования с расчетом контрольной суммы. В первом случае, при определенной избыточности, Вы всегда данные передадите. Во втором, в общем случае - никогда
Вообще-то сравнивать можно, так как главное, обычно, это передать без ошибок. Оба метода это пытаются обеспечить своими силами. CRC лучше выявит наличие ошибок, а кодирование с избыточными данными не потребует повторного запроса (на дисках и лентах это вообще невозможно).
Вообще-то сравнивать можно, так как главное, обычно, это передать без ошибок.
Категорически не согласен. Главное, для начала, вообще передать. Контрольная сумма позволит Вам что-то передать только по каналу связи, в котором вероятность одиночной ошибки в блоке данных существенно меньше единицы. Тогда как использование кодов корректирующих ошибки позволяет передать данные, когда вероятность одиночной ошибки в одном блоке данных вообще равна единице или пренебрежимо близка к ней. Что толку в том, что Вы выявите ошибку, если данные без ошибки Вы не сможете получить?
Условно говоря, мой метод позволяет передавать данные вплоть до вероятности ошибки в 1/4 - матрицей 2х2 на каждый бит. Ваш же способ не пригоден при вероятности ошибки в 1/24 (CRC16 на каждый байт).
друзья, перечитайте еще раз название темы и сравните ваши последние 7-10 сообщений с темой - соответствуют ли они ей? в применении CRC нет ничего оригинального, необычного или хитрого, особенно если применяются стандартные полиномы и т.п.
_________________ если рассматривать человека снизу, покажется, что мозг у него глубоко в жопе при взгляде на многих сверху ничего не меняется...
Категорически не согласен. Главное, для начала, вообще передать. Контрольная сумма позволит Вам что-то передать только по каналу связи, в котором вероятность одиночной ошибки в блоке данных существенно меньше единицы. Тогда как использование кодов корректирующих ошибки позволяет передать данные, когда вероятность одиночной ошибки в одном блоке данных вообще равна единице или пренебрежимо близка к ней.
Это в теории. На практике где вероятность есть вероятность ошибки ~1 на блок данных, чуть реже будет проскакивать и 2 ошибки (восстановить невозможно), и 3 ошибки (можно восстановить с ошибкой, если расположены "квадратом" неполным)
Вот нормальное распредедение, ждем 1 ошибку, а будут отклонения во все стороны
Цитата:
Что толку в том, что Вы выявите ошибку, если данные без ошибки Вы не сможете получить?
Тут можно сразу 2-3 раза передавать данные. И восстанавливать хитрым алгоритмом. Или применять более сложные алгоритмы, жесткий матан, я там ничего не понял, коды Рида-Соломона https://habr.com/ru/post/191418/
Но там тоже противоречие, вокруг которого и мы тут ходим. Чем больше избыточных данных, тем надежнее восстановление. Нужен компромисс.
Цитата:
Условно говоря, мой метод позволяет передавать данные вплоть до вероятности ошибки в 1/4 - матрицей 2х2 на каждый бит.
Чуть хуже, 3 бита в этой матрице 2х2, алгоритм "подумает" что это одиночная ошибка, исправит добавив сбойный бит до матрицы 2х2 и отрапортует что справился ))
На глазок, думаю будет примерно так. Передаем 1 млн. сбойных пакетов где 1,2,3..10 бит с ошибкой. И смотрим результат. CRC16 пропускает 15 ошибок и 0 восстанавливает. Ваш метод, при 18 выделенных битах пропустит как-бы не 500 ошибок. Но при этом часть восстановит, может 20% или 200 000 пакетов, из которых 500 будут с ошибками. Я даже не знаю хорошо это или плохо, наверное есть задачи где именно это и нужно.
в применении CRC нет ничего оригинального, необычного или хитрого, особенно если применяются стандартные полиномы и т.п.
CRC тоже можно считать по табличке, черех XOR побитно и аппаратно через сдвиги по кругу. И тут не про CRC, а другие оригинальные методы, которые сравниваются с CRC. А если речь пойдет о коде Рида-Соломона, то это будет взрыв мозга и на ночь такое лучше вообще не читать, куда еще хитрее то ))
вы как-то упускаете, что тем, кто знает, вы ничего нового не принесете, а тем кто не знает, ваша заумь непонятна. я думаю, для многих будет открытием алгоритм обмена значений двух переменных без использования третьей... а вы про Рида с Соломоном...
_________________ если рассматривать человека снизу, покажется, что мозг у него глубоко в жопе при взгляде на многих сверху ничего не меняется...
вы как-то упускаете, что тем, кто знает, вы ничего нового не принесете, а тем кто не знает, ваша заумь непонятна. я думаю, для многих будет открытием алгоритм обмена значений двух переменных без использования третьей... а вы про Рида с Соломоном...
Заморачиваться на экономии байта это не заумь (это вообще-то задача компилятора), а CRC-подобные алгоритмы, которые обсуждает 3 человека, для вас не нужно. Вам надо чтобы только ваши интересы все разделяли? или просто потроллить? ))
И на практике, и в теории, в тех случаях, когда вероятность ошибки не нулевая, рано или поздно, какие бы способы контроля Вы не использовали, произойдет ошибка, которую Вы не обнаружите. И Вам это не изменить.
С точки зрения передачи по USART, когда бит четности формируется автоматически, послать после блока данных контрольный байт, полученный обыкновенным XOR из всех ранее переданных байтов, сможет даже начинающий. И при этом, уже по желанию, может или исправлять одиночные ошибки, или детектировать до трех ошибок в блоке. Альтернативный предложенный Вами вариант простого суммирования позволит детектировать только одиночные ошибки, не позволит детектировать двойные и, тем более, не позволит ничего исправить. Хотя по сложности реализации ничем не отличается от перекрестного контроля на четность. Использование же CRC, с расчетом контрольной суммы по полиному, на многих МК (без аппаратной поддержки CRC) вообще не факт, что совместимо с высокими скоростями передачи, да и на порядок сложней в реализации, чем предыдущие два способа. Но требует избыточных 2-4 байта на блок данных, который у многих здесь редко превышает нескольких байт. Про БЧХ-коды вести тут речь вообще не факт, что имеет смысл, как заметил ARV.
В итоге, первый алгорит прост, в два раза более устойчив, чем второй, не менее устойчив, чем третий, хоть и проще его на порядок, позволяет корректировать ошибки и легко масштабируется для слов с любым количеством бит (для USART от 5 до 9). Чем он Вам не угодил? Излишней избыточностью? Так это вполне адекватная цена за простоту реализации.
И на практике, и в теории, в тех случаях, когда вероятность ошибки не нулевая, рано или поздно, какие бы способы контроля Вы не использовали, произойдет ошибка, которую Вы не обнаружите. И Вам это не изменить.
CRC64 даст полную надежность, ошибка не успеет возникнуть за время существования вселенной. Маленькие блоки данных подписывать нецелесообразно, а большие, более 200 байт уже не так затратно. С увеличением разрядности CRC она становится круче экспоненциально, в отличие от других вариантов.
Цитата:
В итоге, первый алгорит прост, в два раза более устойчив, чем второй, не менее устойчив, чем третий, хоть и проще его на порядок, позволяет корректировать ошибки и легко масштабируется для слов с любым количеством бит (для USART от 5 до 9). Чем он Вам не угодил? Излишней избыточностью? Так это вполне адекватная цена за простоту реализации
Алгоритм прост, но не устойчив. Я только не могу этого доказать, там небольшую программку надо накидать для тестов. Почему это он мне не угодил? Интересный алгоритм, можно бесконечно улучшать его, комбинировать с CRC-подобными, что позволит все плюсы объединить. Надо подумать над этим ))
CRC64 даст полную надежность, ошибка не успеет возникнуть за время существования вселенной.
Вы серьезно или прикалыаетесь? Если CRC32 еще используется из-за простоты его вычисления, но в тех сферах, где действительно требуется надежность, даже от MD5 уже отказываются в пользу SHA-2. Я уж молчу о банковской сфере, где хеши меньше 1024 бита в принципе даже рассматриваются. И при этом вероятность дублирования хеша все равно существует и вполне ожидаема.
Для примера, всего в конце прошлого года была мной найдена интересная бага. Программист, вместо того, чтобы проверять на уникальность набор из десятка полей по одному, тупо считал SHA-256 хеш по всем ним и сравнивал только его. Это проработало чуть больше года, пока неожиданно не выявилось, что в БД размером в несколько десятков терабайт уже дважды(!) уникальность проверялась некорректно: в БД не попали два сообщения, воспринятые, как уже существующие. Какое там время существования вселенной? )))
Про SHA-1 (160 бит) вообще молчу, так как многие сами сталкивались с тем, что файл скачанный по bittorrent оказывался битым, хотя SHA-1 хеш его совпадал с оригиналом.
Вы серьезно или прикалыаетесь? Если CRC32 еще используется из-за простоты его вычисления, но в тех сферах, где действительно требуется надежность, даже от MD5 уже отказываются в пользу SHA-2. Я уж молчу о банковской сфере, где хеши меньше 1024 бита в принципе даже рассматриваются. И при этом вероятность дублирования хеша все равно существует и вполне ожидаема.
Вы путаете криптографию и контрольную сумму. 1024 бита это вообще тема с открытым ключом.
Цитата:
Для примера, всего в конце прошлого года была мной найдена интересная бага. Программист, вместо того, чтобы проверять на уникальность набор из десятка полей по одному, тупо считал SHA-256 хеш по всем ним и сравнивал только его. Это проработало чуть больше года, пока неожиданно не выявилось, что в БД размером в несколько десятков терабайт уже дважды(!) уникальность проверялась некорректно: в БД не попали два сообщения, воспринятые, как уже существующие. Какое там время существования вселенной? )))
Ошибка в алгоритме где-то. Хватило бы и 128 бит. Возможно он из базы данных брал первые 8 байт и по ним считал SHA, или что-то в этом роде.
Цитата:
Про SHA-1 (160 бит) вообще молчу, так как многие сами сталкивались с тем, что файл скачанный по bittorrent оказывался битым, хотя SHA-1 хеш его совпадал с оригиналом
Я не сталкивался. А умышленно такое можно сделать искуственно испортив файл, например, чтобы вирус внедрить и подпись осталась корректной. Очень сложно, через уязвимости алгоритма и радужные таблицы, заранее просчитанных чего-то там.
Обратный пример, примитивный RC-72 до сих пор не взломан, энтузиасты сделали распределенную сеть, миллионы компов лет 10 считают, я тоже считал, и ничего. Сначала на процессорах считали, потом на видеокартах, 100 мегахешей в секунду с компа, и всей планетой код не взломали. Приз 10 000$, но принято получившему отдавать на благотворительность, не в деньгах цель. Вот проект, проверил, до сих пор считают: http://www.distributed.net/RC5
Я тоже тестировал контрольные суммы, собирал статистику для статьи на Хабре. 8-16 бит нормально, 32 бита уже на часы надо было комп оставлять, чтобы найти коллизии в пакетах. 64 бита ни одной коллизии за неделю работы, что и не удивительно, я и не ждал. Пришлось контрольную сумму обрезать до младших 32 бит и их уже тестировать, там всё совпало с теорией.
Если вы о криптографии, то CRC нельзя использовать как криптографическую подпись или криптоалгоритм, там математика простая, хорошо изучена и хаккеры мигом подберут обратные алгоритмы, у них много приемов для этого.
А чем по Вашему отличается контрольная сумма от значения криптографической функции? Только тем, что к последней предъявляются более жесткие требования.
Цитата:
1024 бита это вообще тема с открытым ключом.
В чем разница? Транзакция подписывается для того, чтобы невозможно было изменить ее содержимое так, чтобы хеш остался прежним. Мы же о хеш функциях говорим, а не о шифровании. И CRC - частный вид хеш функции.
Цитата:
Ошибка в алгоритме где-то. Хватило бы и 128 бит. Возможно он из базы данных брал первые 8 байт и по ним считал SHA, или что-то в этом роде.
Если бы было "что-то в этом роде" то такую багу выявили бы еще при тестировании или промэксплуатации, а не через год работы.
Цитата:
пример, примитивный RC-72 до сих пор не взломан
При чем тут взлом? Приз был объявлен за расшифровку зашифрованных RC5 сообщений. Мы же говорим о случайном совпадении значения хеша у двух блоков.
А чем по Вашему отличается контрольная сумма от значения криптографической функции? Только тем, что к последней предъявляются более жесткие требования.
Не жесткие, а специфические, для защиты от известных на сегодняшний день атак. Для применения по назначению CRC походит идеально, улучшать нечего. Та же CRC прекрасно подошла бы как подпись для документов, хеш, но простая математика позволит очень быстро подобрать блок данных с таким же хешем (хотя я бы не смог без посторонней помощи, а перебором бы ждал миллиард лет).
Цитата:
О популярных хэш-алгоритмах Алгоритмы CRC16/32 — контрольная сумма (не криптографическое преобразование).
Алгоритмы MD2/4/5/6. Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
Алгоритм MD6 — очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.
Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 — собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.
Российский стандарт — ГОСТ 34.11-94.
Вот по алгоритмам шифрования или хеширования, даже проще CRC, просто повторят многократно для усложнения.
Для применения по назначению CRC походит идеально, улучшать нечего.
CRC-32 еще используется только благодаря тому, что вычисляется быстрее, чем более надежные криптографические хеш-функции. Ну и еще потому, что зафиксирована в стандартах 802.3 и IPv4. В IPv6 от расчета контрольной суммы вообще отказались. При этом UDP и TCP вполне так обходятся тупой 16-ти битной контрольной суммой. Если нужна хеш функция, то есть более надежные криптографические. Если нужна надежность передачи - есть БЧХ-коды. Забудьте о CRC. Дни его уже сочтены )
Цитата:
Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.
... Отсутствует Checksum заголовка, соответственно, его не надо проверять, а также пересчитывать для каждого пакета при изменении TTL Hop Limit. Так как checksum больше нет, то вся ответственность за целостность информации должна лежать на протоколе более низкого уровня, так например у Ethernet фреймов есть свой честный CRC32. Так же у UDP пакетов наличие checksum теперь обязательно и UDP/IPv6 пакеты с Checksum 0000 будут просто отбрасываться принимающим хостом;
По CRC128 и даже 256 что нашел, отговаривают использовать тоже
I agree with you except that the accidental collision rate is higher than 1 in 2^32 or 1 in 2^64 for 32 bit and 64 bit CRCs respectively.
I wrote an app that kept track of things by their CRC values for tracking items. We needed to track potentially millions of items and we started with a CRC32 which in real world practice has a collision rate of around 1 in 2^16 which was an unpleasant surprise. We then re-coded to use a CRC64 which had a real world collision rate of about 1 in 2^23. We tested this after the unpleasant surprise of the 32 bit one we started with and accepted the small error rate of the 64 bit one.
Типа даже CRC64 дает всего 1 на 2^23, а не 1 на 2^64. Может напутали что-то конечно. Мне не верится, если бы CRC была так плоха, её бы не применяли. Для расчета целостности данных (а не криптоподписи!) она нормально подходит. Как хеш функция для всяких баз данных под вопросом, для индексации и всего такого, у меня нет статистики. Наверное есть и получше алгоритмы.
Сейчас этот форум просматривают: Vladislav14 и гости: 12
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения
Вход
Регистрация
Правила
FAQ
Поиск
