|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
17.04.2017, 12:37 | #1 |
Пользователь
Регистрация: 16.02.2013
Сообщений: 36
|
Восстановление данных по CRC перебором
Есть испорченные данные с контрольной суммой CRC-16. Я пытаюсь исправить ровно 1 бит и в 70% случаев у меня это венчается успехом. Всё вроде бы хорошо, но очевидно можно добиться лучших результатов, так как прослеживается явная систематичность ошибок и можно с хорошей вероятностью (около 70%) найти ошибку в определённых битах (всего битов 1040, ошибкоопасных по статистике около 10-20). Хочется перебирать побольше битов.
Вопрос такой, как я понимаю, то в алгоритме CRC-16 для получении коллизии достаточно перебрать любые 16 последовательных битов, а если я буду перебирать непоследовательные 16 битов, то шанса коллизии нет? Просто эти опасные биты идут как раз с периодичностью в 16, ломается почти всегда старший бит 16-битового слова. Или сколько битов я могу перебрать, чтобы не получить "ложное" совпадение? Пытался загуглить, нашёл немногое. P.S. Я сам не программист, а физик, с такими делами особо не сталкивался. Последний раз редактировалось UaKot; 17.04.2017 в 12:39. |
17.04.2017, 13:19 | #2 |
Форумчанин
Регистрация: 12.04.2017
Сообщений: 889
|
https://ru.wikipedia.org/wiki/%D0%9E...B1%D0%BE%D0%BA
"перебор" это не совсем верно математически. В целом, чтобы восстановить потери - нужны избыточные данные. "Оишбкоопасные" биты наводят на мысль, что у вас на компьютере не верная программа, а точнее, в ее коде (на каком-то из этапов, начиная от драйвера кабеля, и кончая графиками) идет смешивание знакового и без-знакогового целого (например, unsigned short и short). Такое смешивание и дает потерю, потому что старший бит считается то знаком числа, то данными. Для такой разной интерпретации в процессоре есть разные команды, использование разных команд ведет к тому, что вы видите. Последний раз редактировалось alexzk; 17.04.2017 в 13:24. |
17.04.2017, 13:52 | #3 |
Пользователь
Регистрация: 16.02.2013
Сообщений: 36
|
Я наврал похоже... Просто числа 8 и 16 в голове перепутались слегка. Ошибки происходят не в каждом слове, а в каждом восьмом слове и при этом не обязательно в начале или в конце, но есть чётко выраженные места, где они локализованы.
Вот пример количества ошибок (первый столбец - номер слова, второй и далее - ошибки по битам) 44 : 0 : 348 : 1777 : 2235 : 421 : 1274 : 0 : 0 : 0 : 0 : 9537 : 775 : 378 : 0 : 0 : 0 45 : 0 : 0 : 0 : 0 : 0 : 3 : 0 : 1 : 0 : 0 : 1 : 1 : 1 : 0 : 0 : 0 46 : 0 : 0 : 3 : 0 : 1 : 1 : 0 : 0 : 0 : 0 : 2 : 1 : 0 : 0 : 0 : 0 47 : 0 : 1 : 0 : 0 : 0 : 4 : 0 : 0 : 0 : 0 : 0 : 0 : 1 : 0 : 0 : 0 48 : 0 : 0 : 0 : 1 : 1 : 6 : 0 : 0 : 0 : 0 : 0 : 1 : 0 : 0 : 0 : 0 49 : 0 : 0 : 1 : 0 : 0 : 1 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 1 : 0 : 0 50 : 0 : 0 : 1 : 0 : 1 : 2 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 1 : 0 : 0 51 : 1 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 52 : 0 : 3 : 50 : 138 : 29 : 74 : 0 : 0 : 0 : 0 : 6035 : 590 : 181 : 0 : 0 : 0 То есть нет, старший бит у меня не трогается, и есть достоверная информация, что портится около 1 бита. Я построил гистограммы обработанных где-то 200тысяч таких записей, картина не нарушается нигде + есть тенденция к тому, что в элекронике присутствуют 2 независимых источника ошибок, потому что явно видно 2 семейства пиков. Вот и решил проверять по 2 бита за раз. Последний раз редактировалось UaKot; 17.04.2017 в 14:08. |
17.04.2017, 14:04 | #4 |
Форумчанин
Регистрация: 12.04.2017
Сообщений: 889
|
Как вы получаете эти диаграммы ошибок?
1. О реальной ошибке можно говорить уверенно только, путем замера на кабеле (промежуточное устройство, включеное м-у компом и кабелем). А еще лучше, получить заведомо известные данные много раз и отслеживать их цепочку - где порча. 2. А как вы собссно определяете номер бита с ошибкой? CRC считает только верность ( и то, возможны сдвоенные ошибки, которые в итоге дадут верную крк), она не может указать бит, в каком есть ошибка (т.е. коррекция на ее основе мат. не верно). 3. Почему слова у вас 16 бит? У вас что, на каждое слово в 16 бит считается crc-16 (т.е. удвоение сигнала)? Обычно так не делают, а считают crc сразу на большой блок слов (например 10-20-30). Вообще crc придуманы для простейших схем, поток данных проходит через crc вычислитель,а в конце должен получится ноль. Это аппаратно просто и дешево. Алгоритмы на компьютере выдают инверсию реальной крк, так что она совпадает с конечной, но аппаратно, без инверсии, сумма всего ноль. Последний раз редактировалось alexzk; 17.04.2017 в 14:15. |
17.04.2017, 14:19 | #5 |
Пользователь
Регистрация: 16.02.2013
Сообщений: 36
|
Вопрос о том, портятся данные или нет - не стоит. Они портятся. Вопрос только в том, где именно.
Всё, что мне доступно, это выходные результаты и всё. То есть механически полезть и делать какие-то замеры я не могу. CRC-16 считается не на одно слово, а на 64 слова, 65ым словом передаётся сам CRC. Определяю номер слова так: просто произвожу xor с единицей в каждом из возможных мест, и каждый раз проверяю полученный CRC c тем, что хранится в 65 слове. Если CRC сошёлся, то просто запоминаю место, на котором стояла единица, если нет, то опять xor и единица сдвигается. Последний раз редактировалось UaKot; 17.04.2017 в 14:22. |
17.04.2017, 14:23 | #6 | |
Форумчанин
Регистрация: 12.04.2017
Сообщений: 889
|
Цитата:
В вашем случае, нада пробовать получать заведомо известные данные, или заведомо одинаковые данные. Тогда, по 1000 замеров, можно сказать какие биты портятся. Если окажется, что всегда на одних местах, с большой вероятностью - это или ошибка знаковости в программе, или могут быть аппаратные сбои регистров, например, каждый 7й бит в пачках по 16. |
|
17.04.2017, 14:29 | #7 | |
Пользователь
Регистрация: 16.02.2013
Сообщений: 36
|
Цитата:
|
|
17.04.2017, 14:32 | #8 | |
Форумчанин
Регистрация: 12.04.2017
Сообщений: 889
|
Цитата:
В целом все равно будет не надежно, например вы ставите лимит скорости (когда считать не верной) 100м/с, а у вас аварийно разогналось на 110. Упустите аварию. И т.д. Последний раз редактировалось alexzk; 17.04.2017 в 14:41. |
|
17.04.2017, 14:42 | #9 | |
Пользователь
Регистрация: 16.02.2013
Сообщений: 36
|
Цитата:
|
|
17.04.2017, 14:48 | #10 |
Форумчанин
Регистрация: 12.04.2017
Сообщений: 889
|
Короче Для восстановления вам нужна избыточная информация. Скажем, вместо 8 бит на байт, нужно получать 9. (см. ссылку я дал на математику).
Если такую информацию получать не возможно, можно использовать физические ограничения системы и взаимные обязательные корелляции данных (проистекающих из физики, например, ускорение при импульсе и фиксированной массе) на приемнике. Если таких ограничений тоже нет .... то у вас нет доп. информации и восстановить инфу надежно нельзя. Если не говорить о надежности - то вообще какая разница - один случай, другой случай... |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
восстановление данных | Астролог | Помощь студентам | 10 | 14.04.2015 01:14 |
восстановление данных | mishabcbb | Помощь студентам | 0 | 17.04.2011 16:17 |
Восстановление данных | FANATID | Компьютерное железо | 7 | 25.02.2009 12:31 |
Восстановление данных | Serega_P | Операционные системы общие вопросы | 4 | 10.02.2009 17:39 |