Кто силён в хешировании, подскажите.

[Штабскапитан Овечкин]

Имеется канал передачи данных на станок ЧПУ. В данный момент реализован только контроль чётности побайтно. Нужен какой-нибудь алгоритм подсчёта контрольной суммы всего файла. Желательно, чтобы легко реализовывался аппаратно на приёме.

Если, допустим, просто и без затей, применить 256-битный XOR, как можно грубо прикинуть вероятность коллизий? Длина файлов от ~1кБ до `65кБ.

[егорка75]

Станок самодельный ?

[Штабскапитан Овечкин]

Станок нормальный, серийный СМ-600 (сверлильно-фрейзерный). Но канал связи - самопал. Плата сопряжения с фотосчиткой заменена на самопальную плату, принимающую данные по 1 верёвке. Вот на этой-то плате есть возможность прилепить примочку для подсчёта КС.

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

[ARV]

чем CRC32 не устраивает? программная реализация сильно тяжкой не будет для микроконтроллера

[Штабскапитан Овечкин]

Главным образом напрягает аппаратная реализация на стороне станка. Требуется что-нибудь по-проще. На простой логике.

Всё-таки, кто-нибудь может прикинуть на пальцах, какая будет вероятность ошибки, если использовать просто XOR? Ну к примеру 4-х байтный.

[Pe3ucTop]

Можно как в интернет сети - контрольная сумма (сумма всех с учётом переноса-переполнения) и в конце пакета добовляем ..
На приёме опять таки тотже алгоритм - суммы. и теперь он уже для всего пакета с добавкои даст, не знаю как сказать - максимум... (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 варианта:
- "максимум - сумма"
- "инверсия суммы" = "побитовое не суммы" или "исключаюшее или от суммы по максимому"
Вообщем это уже дело програмирования и архитектуры..

[Штабскапитан Овечкин]

А всё-таки, что будет, если просто проксорить? Дело в том, что морозить что-то серьёзное на стороне станка не представляется возможным. Надо какое-то совсем простое решение. Если, допустим, я сложу все передаваемые байты в 256-битную переменную, без учёта переноса (ну, или с учётом) и то же самое проделаю с помощью простой логики на приёме? Будет какой-нибудь эффект в плане надёжности передачи? Какая будет вероятность случайного совпадения КС?

[asteroid7]

Как следствие чётности подсчитать количество единичных бит. Аппаратно легко сделать. Чётность не плохо используется в простейших пакетах.

[Пухич]

Обождите, штабскапитан!

Вам что нужно - обеспечить надежность передачи? Если да, то тут надо именно так вопрос ставить - чего бы мне такое сделать, чтобы было без ошибок.

Если мне не изменяет память, то в 155-й серии были микрухи для работы с кодом, защищенным по методу Хемминга. Они обеспечивают гарантированное обнаружение двойных и устранение одиночных ошибок. Разумеется код Хемминга позволяет повысить защищенность еще выше, но вроде в тех ИМС именно такая (считающаяся стандартной) схема.

[Rokl]

Если мне не изменяет память, то в 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разрядная схема обнаружения и исправления ошибок

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

[Секретный кот]

К155ВЖ1 SN74630 16-разрядная схема контроля по коду "Хемминга".

Доставаемость её, думаю, ещё более низкая. Хотя у меня где-то одна валялась вроде.

[Пухич]

В 155 серии не было вроде, скорей в 555 серии проверка на четность.

Да вроде были. Вот и Секретный кот подтвердил.

А в буржуинских сериях полно:

Это да. Правда там сплошь аналоги 555-й и 1533-й. Может у нас в 1533-й тоже куча таких ИМС. Хотя я что-то не слышал.

З.Ы.: Интересно, автору подходит код Хемминга? Чего-то он молчит.

[Штабскапитан Овечкин]

Благодарю всех за ответы.

На счёт Хемминга - пожалуй, что нет, не подойдёт. На стороне станка стоит протой регистр стдвига, который копит 1 байт и передаёт его станку (старший бит - чётность). Если я правильно понимаю тему - код Хемминга требует пакетной передачи. Если ошибаюсь - пожалуйста, поправьте. А вот что такое 32-разрядная схема обраружения и исправления - это, если можно, пожалуйста разъясните. Или это имеется в виду всё тот же код Хемминга?

Короче так. Излагаю проблему ещё раз, чтобы вы могли сделать вывод - что мне подходит, а что нет. Ибо самому мне это не под силу. Что такое коды Хемминта, Грея и т. п. - для меня это очень далёкий звон.
И так: имеется программа под ДОСом, которая нестандартным способом по самопальному протоколу (если вобще применимо это слово) передаёт файлы в станок. Исходников никаких не сохранилось. В этой программе по мере своих сил ковыряюсь с помощью IDA Pro. Раньше она, вообще, работала через ISAшный порт. Мне удалось перенаправить её через COM (на новом компе нет шины ISA). В екзешнике есть место, куда можно засунуть свою процедуру, около 8 кБ. Туда возможен простой Call (тот же сегмент) из процедуры, выводящей в порт. То есть, теоретически, при достаточной математической подкованности, можно свормировать там иходный код, к примеру Хемминга. Допустим, даже мне удалось это сделать. Что далее? Ка принять этот код? Вышеупомнутая 32 разрядная схема обнаружения и исправления его примет и проанализирует? Она должна накопить 32 бита и затем их выдать? (Поправляйте, если неправ). Во-первых, в каком виде она их выдаст - в хемминговом? Мне-то нужет простой байт - 7 бит данных и 1 бит чётность. Во-вторых, приняв 32 бита она должна же и выдать сразу 32? А мне надо 8. То есть передал 8 бит - принял 8 бит. И т. д.

Вот, вкратце, каковы мои сомнения. Если я что-то не так понял, прошу меня поправить.

Ещё раз благодарю всех, кто ответил.

[Kotische]

Аппаратно, проще всего поставить прооостинький микроконтроллер со встроенным USART, который будет принимать несколько байт считать по любому алгоритму контрольную сумму и выдавать тебе в станок парралельный код и строб. Нужно всего 2 микросхемы - микроконтроллер (например atmega32 хотя для твоей задачи она избыточна) и преобразователь уровней RS232<->TTL (например max232).
Если не хочешь связываться с написанием примитивнейшей прошивки для микроконтроллера, можешь сделать свой собственный корректирующий преобразователь:
парралельный код с твоего регистра подаешь на адресную линию ПЗУшки, а с её шины данных снимешь скорректированный код.
В ПЗУшку зашиваешь таблицу корректировки, хочешь Хеминга, хочешь кого другого....

[Штабскапитан Овечкин]

Вот это, пожалуй, хорошая мысель - Дешифратор на ПЗУхе.
Теперь задача намба ван - как программно реализовать на передающей стороне.
Вторая задача - таблица дешифровки этого Хемминга.

[Kotische]

Про Хеминга на вскидку не скажу...
но можешь поюзать матричный код:

Принцип формирования следующий:
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 битное слово которое подаешь на адресную шину ПЗУхи.

[Пухич]

Если я правильно понимаю тему - код Хемминга требует пакетной передачи. Если ошибаюсь - пожалуйста, поправьте. А вот что такое 32-разрядная схема обраружения и исправления - это, если можно, пожалуйста разъясните. Или это имеется в виду всё тот же код Хемминга?

В схемах обнаружения и исправления обычно Хемминг и используется. Вы даташит на любую микру скачайте и поглядите. Мы ж тоже не можем догадаться, что вам подойдет. Думаю, что подойдет. По большому счету вам надо одну такую микру. Она стоит на приеме у станка и берет у шифта принятый байт (этот момент должен кто-то квитировать, вообще кто-то очень примитивный должен генерить управляющие сигналы для микры Хемминга, там идет чтение и захват инфы и допкода для проверки, генерация допкода Хемминга, исправление). Затем она байт проверяет, корректирует, и отдает станку. На стороне компа код Хемминга генерите вы сам. Код Хемминга не запрещает использовать одновременно и четность внутри байта. Возможно даже можно будет что-то упростить.

Еще будут нужны двунаправленные порты-буфера, типа 244-го.

Она должна накопить 32 бита и затем их выдать? (Поправляйте, если неправ). Во-первых, в каком виде она их выдаст - в хемминговом? Мне-то нужет простой байт - 7 бит данных и 1 бит чётность. Во-вторых, приняв 32 бита она должна же и выдать сразу 32? А мне надо 8. То есть передал 8 бит - принял 8 бит. И т. д.

Она ничего не копит. Она получает параллельные байты (так у 16-разр, по 32-разр сказать не могу), и с ними делает что-то, что захотите. Если вы используете 16-разр микру, то на ее младший байт данных надо подать байт с информационного шифта, а на старший нолики прямо у микры. А еще надо поставить шифт, с которого инфа пойдет на контрольное слово и управление. Тогда вы пихаете в линию не 8 бит, а 16 бит, причем первые 8 бит - инфа, а вторые - контролька. Вторые 8 бит генерите в проге на компе. Таким образом, после нескольких операций засылки (может и проще обойдется) вы получаете проверенный байт на выходе.

[Kotische]

2 Штабскапитан Овечкин
Автор... ау!...
Что ни будь получилось?

[Штабскапитан Овечкин]

Прикинул кое-что к носу и решил всё-таки ПОКА не заморачиваться с Хеммингом. Нет в данный момент времени 1 - изучать эту математику, 2 - искать и заказывать вышеупомянутые схемы обнаружения ошибок. Решил делать на том, что имеется под руками и то, что проще. Возможно, что это будет временный вариант. Просто сейчас уже надо дать станку работать, а тем временем можно будет параллельно заниматься всё-таки Хеммингом. Если рабоче-крестьянский вариант будет работать удовлетворительно, возможно он и останется. Но всеми советами, непременно воспользуюсь в будущем. Очень много полезной информации. Душевно всех благодарю.
А текущий вариант такой: 2 контрольные суммы - XOR и ADD. Это подсказал один человек, у которого это применено на практике.

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

Ещё раз повторюсь - дело в дефиците времени. Нет возможности долго держать всё у себя - станок должен уже работать. О результатах обязательно отпишусь.

Огромное всем спасибо за ответы. Почерпнул мого полезного. Возможно вернусь позже к предложенным вами вариантам.

[Пухич]

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

Нифига контроль не абсолютный. Можеи иметь место некая статическая помеха, которая успешно будет портить один и тот же бит во всех байтах.Хотя это бывает редко, так что можно сделать и так. Но с оговоркой.

А текущий вариант такой: 2 контрольные суммы - XOR и ADD. Это подсказал один человек, у которого это применено на практике.

Не понял. Что такое "2 контрольные суммы - XOR и ADD". Это как?