Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Программная инженерия > Безопасность, Шифрование
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.04.2017, 12:37   #1
UaKot
Пользователь
 
Регистрация: 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.
UaKot вне форума Ответить с цитированием
Старый 17.04.2017, 13:19   #2
alexzk
Форумчанин
 
Регистрация: 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.
alexzk вне форума Ответить с цитированием
Старый 17.04.2017, 13:52   #3
UaKot
Пользователь
 
Регистрация: 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.
UaKot вне форума Ответить с цитированием
Старый 17.04.2017, 14:04   #4
alexzk
Форумчанин
 
Регистрация: 12.04.2017
Сообщений: 889
По умолчанию

Как вы получаете эти диаграммы ошибок?
1. О реальной ошибке можно говорить уверенно только, путем замера на кабеле (промежуточное устройство, включеное м-у компом и кабелем). А еще лучше, получить заведомо известные данные много раз и отслеживать их цепочку - где порча.
2. А как вы собссно определяете номер бита с ошибкой? CRC считает только верность ( и то, возможны сдвоенные ошибки, которые в итоге дадут верную крк), она не может указать бит, в каком есть ошибка (т.е. коррекция на ее основе мат. не верно).
3. Почему слова у вас 16 бит? У вас что, на каждое слово в 16 бит считается crc-16 (т.е. удвоение сигнала)? Обычно так не делают, а считают crc сразу на большой блок слов (например 10-20-30).

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

Последний раз редактировалось alexzk; 17.04.2017 в 14:15.
alexzk вне форума Ответить с цитированием
Старый 17.04.2017, 14:19   #5
UaKot
Пользователь
 
Регистрация: 16.02.2013
Сообщений: 36
По умолчанию

Вопрос о том, портятся данные или нет - не стоит. Они портятся. Вопрос только в том, где именно.
Всё, что мне доступно, это выходные результаты и всё. То есть механически полезть и делать какие-то замеры я не могу.
CRC-16 считается не на одно слово, а на 64 слова, 65ым словом передаётся сам CRC. Определяю номер слова так: просто произвожу xor с единицей в каждом из возможных мест, и каждый раз проверяю полученный CRC c тем, что хранится в 65 слове. Если CRC сошёлся, то просто запоминаю место, на котором стояла единица, если нет, то опять xor и единица сдвигается.

Последний раз редактировалось UaKot; 17.04.2017 в 14:22.
UaKot вне форума Ответить с цитированием
Старый 17.04.2017, 14:23   #6
alexzk
Форумчанин
 
Регистрация: 12.04.2017
Сообщений: 889
По умолчанию

Цитата:
Сообщение от UaKot Посмотреть сообщение
Вопрос о том, портятся данные или нет - не стоит. Они портятся. Вопрос только в том, где именно.
CRC-16 считается не на одно слово, а на 64 слова, 65ым словом передаётся сам CRC. Определяю номер слова так: просто произвожу xor с единицей в каждом из возможных мест, и каждый раз проверяю полученный CRC c тем, что хранится в 65 слове. Если CRC сошёлся, то просто запоминаю место, на котором стояла единица, если нет, то опять xor и единица сдвигается.
Ну не верно это. При подсчете крк возможна такая комбинация ошибок, что крк будет верной, т.е. вполне вероятно, вы своим xor добавляете еще 1 ошибку и получаете верную крк в сумме.

В вашем случае, нада пробовать получать заведомо известные данные, или заведомо одинаковые данные. Тогда, по 1000 замеров, можно сказать какие биты портятся.
Если окажется, что всегда на одних местах, с большой вероятностью - это или ошибка знаковости в программе, или могут быть аппаратные сбои регистров, например, каждый 7й бит в пачках по 16.
alexzk вне форума Ответить с цитированием
Старый 17.04.2017, 14:29   #7
UaKot
Пользователь
 
Регистрация: 16.02.2013
Сообщений: 36
По умолчанию

Цитата:
Сообщение от alexzk Посмотреть сообщение
Ну не верно это. При подсчете крк возможна такая комбинация ошибок, что крк будет верной, т.е. вполне вероятно, вы своим xor добавляете еще 1 ошибку и получаете верную крк в сумме.

В вашем случае, нада пробовать получать заведомо известные данные, или заведомо одинаковые данные. Тогда, по 1000 замеров, можно сказать какие биты портятся.
Если окажется, что всегда на одних местах, с большой вероятностью - это или ошибка знаковости в программе, или могут быть аппаратные сбои регистров, например, каждый 7й бит в пачках по 16.
Я прекрасно понимаю, что могут наложиться 2 ошибки и в сумме дать верный ответ, но у меня нет другого выбора. Не имею я доступа к электронике. Поэтому и спрашиваю о том, с какой вероятностью это всё может давать верный результат. Я знаю, что портится 1-2 бита, мне это, как факт, сказали просто.
UaKot вне форума Ответить с цитированием
Старый 17.04.2017, 14:32   #8
alexzk
Форумчанин
 
Регистрация: 12.04.2017
Сообщений: 889
По умолчанию

Цитата:
Сообщение от UaKot Посмотреть сообщение
Я прекрасно понимаю, что могут наложиться 2 ошибки и в сумме дать верный ответ, но у меня нет другого выбора. Не имею я доступа к электронике. Поэтому и спрашиваю о том, с какой вероятностью это всё может давать верный результат. Я знаю, что портится 1-2 бита, мне это, как факт, сказали просто.
Значит на основе просто потока данных вы ничего сделать не можете. Можно попробовать искать сбой, исходя из доп. условий. Например, пусть слово 10 показывает скорость, если вы видите, что скорость, превышает скорость света, то сбой там. Более того, если скорость превышает скорость света, а crc корректна, то у вас 2+ сбоев сразу и пакет нужно игнорировать (т.е. проверку доп. условий выполнять всегда и она будет основной, а крк вспомогательной).

В целом все равно будет не надежно, например вы ставите лимит скорости (когда считать не верной) 100м/с, а у вас аварийно разогналось на 110. Упустите аварию. И т.д.

Последний раз редактировалось alexzk; 17.04.2017 в 14:41.
alexzk вне форума Ответить с цитированием
Старый 17.04.2017, 14:42   #9
UaKot
Пользователь
 
Регистрация: 16.02.2013
Сообщений: 36
По умолчанию

Цитата:
Сообщение от alexzk Посмотреть сообщение
Значит на основе просто потока данных вы ничего сделать не можете. Можно попробовать искать сбой, исходя из доп. условий. Например, пусть слово 10 показывает скорость, если вы видите, что скорость, превышает скорость света, то сбой там. Более того, если скорость превышает скорость света, а crc корректна, то у вас 2+ сбоев сразу и пакет нужно игнорировать.

В целом все равно будет не надежно, например вы ставите лимит скорости (когда считать не верной) 100м/с, а у вас аварийно разогналось на 110. Упустите аварию. И т.д.
В моём случае о надёжности вообще говорить не стоит. Абсолютно случайный процесс.
UaKot вне форума Ответить с цитированием
Старый 17.04.2017, 14:48   #10
alexzk
Форумчанин
 
Регистрация: 12.04.2017
Сообщений: 889
По умолчанию

Короче Для восстановления вам нужна избыточная информация. Скажем, вместо 8 бит на байт, нужно получать 9. (см. ссылку я дал на математику).
Если такую информацию получать не возможно, можно использовать физические ограничения системы и взаимные обязательные корелляции данных (проистекающих из физики, например, ускорение при импульсе и фиксированной массе) на приемнике.
Если таких ограничений тоже нет .... то у вас нет доп. информации и восстановить инфу надежно нельзя. Если не говорить о надежности - то вообще какая разница - один случай, другой случай...
alexzk вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
восстановление данных Астролог Помощь студентам 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