| Форум РадиоКот https://radiokot.ru/forum/ |
|
| Кто силён в хешировании, подскажите. https://radiokot.ru/forum/viewtopic.php?f=2&t=13714 |
Страница 1 из 2 |
| Автор: | Штабскапитан Овечкин [ Пт фев 13, 2009 12:28:31 ] |
| Заголовок сообщения: | Кто силён в хешировании, подскажите. |
Имеется канал передачи данных на станок ЧПУ. В данный момент реализован только контроль чётности побайтно. Нужен какой-нибудь алгоритм подсчёта контрольной суммы всего файла. Желательно, чтобы легко реализовывался аппаратно на приёме. Если, допустим, просто и без затей, применить 256-битный XOR, как можно грубо прикинуть вероятность коллизий? Длина файлов от ~1кБ до `65кБ. |
|
| Автор: | егорка75 [ Пт фев 13, 2009 15:31:58 ] |
| Заголовок сообщения: | |
Станок самодельный ? |
|
| Автор: | Штабскапитан Овечкин [ Пт фев 13, 2009 15:36:44 ] |
| Заголовок сообщения: | |
Станок нормальный, серийный СМ-600 (сверлильно-фрейзерный). Но канал связи - самопал. Плата сопряжения с фотосчиткой заменена на самопальную плату, принимающую данные по 1 верёвке. Вот на этой-то плате есть возможность прилепить примочку для подсчёта КС. Проблема - как лучше сгенерить эту КС на передающем конце. По какому алгоритму. Чтобы как можно прооще было аппаратно восстановить её в приёмнике. И в то же время, чтобы по-надёжнее, в плане коллизий. |
|
| Автор: | ARV [ Пт фев 13, 2009 18:29:10 ] |
| Заголовок сообщения: | |
чем CRC32 не устраивает? программная реализация сильно тяжкой не будет для микроконтроллера 
|
|
| Автор: | Штабскапитан Овечкин [ Пт фев 13, 2009 18:34:49 ] |
| Заголовок сообщения: | |
Главным образом напрягает аппаратная реализация на стороне станка. Требуется что-нибудь по-проще. На простой логике. Всё-таки, кто-нибудь может прикинуть на пальцах, какая будет вероятность ошибки, если использовать просто XOR? Ну к примеру 4-х байтный. |
|
| Автор: | Pe3ucTop [ Пт фев 13, 2009 18:52:40 ] |
| Заголовок сообщения: | |
Можно как в интернет сети - контрольная сумма (сумма всех с учётом переноса-переполнения) и в конце пакета добовляем .. На приёме опять таки тотже алгоритм - суммы. и теперь он уже для всего пакета с добавкои даст, не знаю как сказать - максимум... (255 ... 65535 , FF .. FFFF в зависимости сколькобитная контрольная сумма) Т.е. пример десяцтичной контрольной суммы: пакет: 1, 2, 3, 7, 6, 4 сумма: 23 - т.е. 2 было это переносы в десятки , тоесть сумма с учетом переноса будет: 2 + 3 = 5 дополнение будет - до максимума десятичнои системы: т.е. 9 - 5 = 4 передаём пакет : 1, 2, 3, 7, 6, 4, 4 на приёме сумма: 27 сумма с учетом переносов: 2 + 7 = 9 Приблезительно так только для нужной битности..
Для быстроты подсчетов : есть два варианта для учёта переноса: - в начале находим общую сумму ( битность суммы больсхе данных ) и потом старший порядок сумируем с младшим. - считаем сумму (размерность суммы и данных равны), и во время подсчета когда случается переполнение - добавляем к сумме 1
Для нахождения дополнения пакета тоже 2 варианта: - "максимум - сумма" - "инверсия суммы" = "побитовое не суммы" или "исключаюшее или от суммы по максимому" Вообщем это уже дело програмирования и архитектуры.. |
|
| Автор: | Штабскапитан Овечкин [ Пт фев 13, 2009 19:10:02 ] |
| Заголовок сообщения: | |
А всё-таки, что будет, если просто проксорить? Дело в том, что морозить что-то серьёзное на стороне станка не представляется возможным. Надо какое-то совсем простое решение. Если, допустим, я сложу все передаваемые байты в 256-битную переменную, без учёта переноса (ну, или с учётом) и то же самое проделаю с помощью простой логики на приёме? Будет какой-нибудь эффект в плане надёжности передачи? Какая будет вероятность случайного совпадения КС? |
|
| Автор: | asteroid7 [ Пт фев 13, 2009 22:01:28 ] |
| Заголовок сообщения: | |
Как следствие чётности подсчитать количество единичных бит. Аппаратно легко сделать. Чётность не плохо используется в простейших пакетах. |
|
| Автор: | Пухич [ Сб фев 14, 2009 02:05:55 ] |
| Заголовок сообщения: | |
Обождите, штабскапитан! Вам что нужно - обеспечить надежность передачи? Если да, то тут надо именно так вопрос ставить - чего бы мне такое сделать, чтобы было без ошибок. Если мне не изменяет память, то в 155-й серии были микрухи для работы с кодом, защищенным по методу Хемминга. Они обеспечивают гарантированное обнаружение двойных и устранение одиночных ошибок. Разумеется код Хемминга позволяет повысить защищенность еще выше, но вроде в тех ИМС именно такая (считающаяся стандартной) схема. |
|
| Автор: | Rokl [ Сб фев 14, 2009 11:08:06 ] |
| Заголовок сообщения: | |
Пухич писал(а): Если мне не изменяет память, то в 155-й серии были микрухи для работы с кодом, защищенным по методу Хемминга. Они обеспечивают гарантированное обнаружение двойных и устранение одиночных ошибок. Разумеется код Хемминга позволяет повысить защищенность еще выше, но вроде в тех ИМС именно такая (считающаяся стандартной) схема.
В 155 серии не было вроде, скорей в 555 серии проверка на четность. А в буржуинских сериях полно: 74ALS280-9рзрядная схема проверки четности 74AS286-9рзрядная схема проверки четности 74F418-32разрядная схема обнаружения и исправления ошибок 74F420-32разрядная схема обнаружения и исправления ошибок 74ALS616-16разрядная схема обнаружения и исправления ошибок 74ALS617-16разрядная схема обнаружения и исправления ошибок 74LS630-16разрядная схема обнаружения и исправления ошибок 74LS631-16разрядная схема обнаружения и исправления ошибок 74ALS632-32разрядная схема обнаружения и исправления ошибок 74ALS633-32разрядная схема обнаружения и исправления ошибок 74ALS634-32разрядная схема обнаружения и исправления ошибок 74ALS635-32разрядная схема обнаружения и исправления ошибок 74LS636-8разрядная схема обнаружения и исправления ошибок 74LS637-8разрядная схема обнаружения и исправления ошибок Привел такой длинный список потому, что наверное достать такой раритет возможно будет с огромным трудом. |
|
| Автор: | Секретный кот [ Сб фев 14, 2009 13:43:40 ] |
| Заголовок сообщения: | |
К155ВЖ1 SN74630 16-разрядная схема контроля по коду "Хемминга". Доставаемость её, думаю, ещё более низкая. Хотя у меня где-то одна валялась вроде. |
|
| Автор: | Пухич [ Сб фев 14, 2009 15:33:02 ] |
| Заголовок сообщения: | |
Rokl писал(а): В 155 серии не было вроде, скорей в 555 серии проверка на четность. Да вроде были. Вот и Секретный кот подтвердил. Цитата: А в буржуинских сериях полно:
Это да. Правда там сплошь аналоги 555-й и 1533-й. Может у нас в 1533-й тоже куча таких ИМС. Хотя я что-то не слышал. З.Ы.: Интересно, автору подходит код Хемминга? Чего-то он молчит. |
|
| Автор: | Штабскапитан Овечкин [ Сб фев 14, 2009 17:50:03 ] |
| Заголовок сообщения: | |
Благодарю всех за ответы. На счёт Хемминга - пожалуй, что нет, не подойдёт. На стороне станка стоит протой регистр стдвига, который копит 1 байт и передаёт его станку (старший бит - чётность). Если я правильно понимаю тему - код Хемминга требует пакетной передачи. Если ошибаюсь - пожалуйста, поправьте. А вот что такое 32-разрядная схема обраружения и исправления - это, если можно, пожалуйста разъясните. Или это имеется в виду всё тот же код Хемминга? Короче так. Излагаю проблему ещё раз, чтобы вы могли сделать вывод - что мне подходит, а что нет. Ибо самому мне это не под силу. Что такое коды Хемминта, Грея и т. п. - для меня это очень далёкий звон. И так: имеется программа под ДОСом, которая нестандартным способом по самопальному протоколу (если вобще применимо это слово) передаёт файлы в станок. Исходников никаких не сохранилось. В этой программе по мере своих сил ковыряюсь с помощью IDA Pro. Раньше она, вообще, работала через ISAшный порт. Мне удалось перенаправить её через COM (на новом компе нет шины ISA). В екзешнике есть место, куда можно засунуть свою процедуру, около 8 кБ. Туда возможен простой Call (тот же сегмент) из процедуры, выводящей в порт. То есть, теоретически, при достаточной математической подкованности, можно свормировать там иходный код, к примеру Хемминга. Допустим, даже мне удалось это сделать. Что далее? Ка принять этот код? Вышеупомнутая 32 разрядная схема обнаружения и исправления его примет и проанализирует? Она должна накопить 32 бита и затем их выдать? (Поправляйте, если неправ). Во-первых, в каком виде она их выдаст - в хемминговом? Мне-то нужет простой байт - 7 бит данных и 1 бит чётность. Во-вторых, приняв 32 бита она должна же и выдать сразу 32? А мне надо 8. То есть передал 8 бит - принял 8 бит. И т. д. Вот, вкратце, каковы мои сомнения. Если я что-то не так понял, прошу меня поправить. Ещё раз благодарю всех, кто ответил.
|
|
| Автор: | Kotische [ Сб фев 14, 2009 21:25:07 ] |
| Заголовок сообщения: | |
Аппаратно, проще всего поставить прооостинький микроконтроллер со встроенным USART, который будет принимать несколько байт считать по любому алгоритму контрольную сумму и выдавать тебе в станок парралельный код и строб. Нужно всего 2 микросхемы - микроконтроллер (например atmega32 хотя для твоей задачи она избыточна) и преобразователь уровней RS232<->TTL (например max232). Если не хочешь связываться с написанием примитивнейшей прошивки для микроконтроллера, можешь сделать свой собственный корректирующий преобразователь: парралельный код с твоего регистра подаешь на адресную линию ПЗУшки, а с её шины данных снимешь скорректированный код. В ПЗУшку зашиваешь таблицу корректировки, хочешь Хеминга, хочешь кого другого.... |
|
| Автор: | Штабскапитан Овечкин [ Сб фев 14, 2009 21:52:10 ] |
| Заголовок сообщения: | |
Вот это, пожалуй, хорошая мысель - Дешифратор на ПЗУхе. Теперь задача намба ван - как программно реализовать на передающей стороне. Вторая задача - таблица дешифровки этого Хемминга. |
|
| Автор: | Kotische [ Сб фев 14, 2009 22:33:18 ] |
| Заголовок сообщения: | |
Про Хеминга на вскидку не скажу... но можешь поюзать матричный код: Принцип формирования следующий: D0 D1 D2 D3 Y1 D4 D5 D6 D7 Y2 D8 D9 Da Db Y3 Dc Dd De Df Y4 X1 X2 X3 X4 C Y1 = D0 xor D1 xor D2 xor D3 Y2 = D4 xor D5 xor D6 xor D7 Y3 = D8 xor D9 xor Da xor Db Y4 = Dc xor Dd xor De xor Df X1 = D0 xor D4 xor D8 xor Dc X2 = D1 xor D5 xor D9 xor Dd X3 = D2 xor D6 xor Da xor De X4 = D3 xor D7 xor Db xor Df C = X1 xor X2 xor X3 xor X4 xor Y1 xor Y2 xor Y3 xor Y4 на 16 бит данных 9 бит избыточности. гарантированно исправляет 1 ошибку, иногда 2 ошибки, гарантированно обнаруживает толи 2 толи 3 ошибки... Аналогичная конструкция возможна для 8 битных данных. Тогда будет достаточно 7 бит избыточности
формировать можно массивом размерностью 256 байт, 1 байт на входе как адрес, из ячейки массива берёшь байта и отправляешь в СОМ-порт 2 байта, оригинальный и добытый из массива. На приеме имеешь 16 битное слово которое подаешь на адресную шину ПЗУхи. |
|
| Автор: | Пухич [ Вс фев 15, 2009 03:03:49 ] |
| Заголовок сообщения: | |
Цитата: Если я правильно понимаю тему - код Хемминга требует пакетной передачи. Если ошибаюсь - пожалуйста, поправьте. А вот что такое 32-разрядная схема обраружения и исправления - это, если можно, пожалуйста разъясните. Или это имеется в виду всё тот же код Хемминга? В схемах обнаружения и исправления обычно Хемминг и используется. Вы даташит на любую микру скачайте и поглядите. Мы ж тоже не можем догадаться, что вам подойдет. Думаю, что подойдет. По большому счету вам надо одну такую микру. Она стоит на приеме у станка и берет у шифта принятый байт (этот момент должен кто-то квитировать, вообще кто-то очень примитивный должен генерить управляющие сигналы для микры Хемминга, там идет чтение и захват инфы и допкода для проверки, генерация допкода Хемминга, исправление). Затем она байт проверяет, корректирует, и отдает станку. На стороне компа код Хемминга генерите вы сам. Код Хемминга не запрещает использовать одновременно и четность внутри байта. Возможно даже можно будет что-то упростить. Еще будут нужны двунаправленные порты-буфера, типа 244-го. Цитата: Она должна накопить 32 бита и затем их выдать? (Поправляйте, если неправ). Во-первых, в каком виде она их выдаст - в хемминговом? Мне-то нужет простой байт - 7 бит данных и 1 бит чётность. Во-вторых, приняв 32 бита она должна же и выдать сразу 32? А мне надо 8. То есть передал 8 бит - принял 8 бит. И т. д.
Она ничего не копит. Она получает параллельные байты (так у 16-разр, по 32-разр сказать не могу), и с ними делает что-то, что захотите. Если вы используете 16-разр микру, то на ее младший байт данных надо подать байт с информационного шифта, а на старший нолики прямо у микры. А еще надо поставить шифт, с которого инфа пойдет на контрольное слово и управление. Тогда вы пихаете в линию не 8 бит, а 16 бит, причем первые 8 бит - инфа, а вторые - контролька. Вторые 8 бит генерите в проге на компе. Таким образом, после нескольких операций засылки (может и проще обойдется) вы получаете проверенный байт на выходе. |
|
| Автор: | Kotische [ Пн фев 16, 2009 00:47:56 ] |
| Заголовок сообщения: | |
2 Штабскапитан Овечкин Автор... ау!... Что ни будь получилось? |
|
| Автор: | Штабскапитан Овечкин [ Пн фев 16, 2009 10:23:10 ] |
| Заголовок сообщения: | |
Прикинул кое-что к носу и решил всё-таки ПОКА не заморачиваться с Хеммингом. Нет в данный момент времени 1 - изучать эту математику, 2 - искать и заказывать вышеупомянутые схемы обнаружения ошибок. Решил делать на том, что имеется под руками и то, что проще. Возможно, что это будет временный вариант. Просто сейчас уже надо дать станку работать, а тем временем можно будет параллельно заниматься всё-таки Хеммингом. Если рабоче-крестьянский вариант будет работать удовлетворительно, возможно он и останется. Но всеми советами, непременно воспользуюсь в будущем. Очень много полезной информации. Душевно всех благодарю. А текущий вариант такой: 2 контрольные суммы - XOR и ADD. Это подсказал один человек, у которого это применено на практике. Ещё была мысель просто-напросто дублировать каждый байт и браковать передачу при первом же несравнении. По скольку передача занимает всего несколько секунд, а перезагружать станок надо не чаще двух-трёх раз в смену, то это было бы вполне приемлемо. К тому же, контроль в этом случае почти абсолютный. Пока ещё не решил, на каком из двух вариантов остановться. Ещё раз повторюсь - дело в дефиците времени. Нет возможности долго держать всё у себя - станок должен уже работать. О результатах обязательно отпишусь. Огромное всем спасибо за ответы. Почерпнул мого полезного. Возможно вернусь позже к предложенным вами вариантам. |
|
| Автор: | Пухич [ Пн фев 16, 2009 20:21:42 ] |
| Заголовок сообщения: | |
Цитата: Ещё была мысель просто-напросто дублировать каждый байт и браковать передачу при первом же несравнении. По скольку передача занимает всего несколько секунд, а перезагружать станок надо не чаще двух-трёх раз в смену, то это было бы вполне приемлемо. К тому же, контроль в этом случае почти абсолютный. Пока ещё не решил, на каком из двух вариантов остановться. Нифига контроль не абсолютный. Можеи иметь место некая статическая помеха, которая успешно будет портить один и тот же бит во всех байтах.Хотя это бывает редко, так что можно сделать и так. Но с оговоркой. Цитата: А текущий вариант такой: 2 контрольные суммы - XOR и ADD. Это подсказал один человек, у которого это применено на практике.
Не понял. Что такое "2 контрольные суммы - XOR и ADD". Это как? |
|
| Страница 1 из 2 | Часовой пояс: UTC + 3 часа |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|
