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

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

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

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

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

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

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

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

Можно как в интернет сети - контрольная сумма (сумма всех с учётом переноса-переполнения) и в конце пакета добовляем ..
На приёме опять таки тотже алгоритм - суммы. и теперь он уже для всего пакета с добавкои даст, не знаю как сказать - максимум... (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-битную переменную, без учёта переноса (ну, или с учётом) и то же самое проделаю с помощью простой логики на приёме? Будет какой-нибудь эффект в плане надёжности передачи? Какая будет вероятность случайного совпадения КС?

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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



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