Контрольная сумма

> Можно например тупо сложить все байты и отбросить старшую часть

Старшую часть отбрасывать не стоит. Ее можно превратить в младшую и добавить к той же сумме. Кажется, примерно такой алгоритм для вычисления CRC использовался в БК-0010.

Вообще, можно использовать любую хеш-функцию. Детали есть в книге Кнута.

Вспомнил. Можно еще элементы суммы на каждой итерации видоизменять, накладывая на нее некоторую псевдо-случайную последовательноcть. Примерно так сделано в крипто-алгоритме ГОСТ. Там используется очень простой генератор СВЧ, который всегда генерирует _воспроизводимую_ последовательность чисел. Тот алгоритм можно легко видоизменить и настроить на получение чисел, состоящих из 2^n бита. В ГОСТе этот СВЧ называется, кажется, гамма-функцией.

Дополнение. Наложение по XOR некоторой воспроизводимой псевдо-случайной последовательности позволит отлавливать такую вещь как перестановка байтов в исходном пакете... По-моему можно применить XOR прямо к исходным данным, а всю остальную сумму считать обычными методами, т.е. как хеш-функцию.

sum = 0;
for (i=0; i<n; i++)
  sum = ((sum << 5) + sum) + dat[i];

А чем не устраивает CRC32 например? Работает довольно быстро, да и на таких размерах будет давать не плохой результат..

А если взять алгоритм, используемый для подсчета контрольной суммы ip-пакета? Вроде там используется двоичное дополнение суммы двоичных дополнений?

Интересно, а что за ограничения такие? Это электрическая схема? (думаю, с ответа на такие вопросы и надо плясать)

Должно делаться в аппаратуре (вообще ПЛИС, но ресурсов на это не так много).

Тогда мой совет остается прежним.

Контрольная сумма - это прежде всего хеш-функция, которая вычисляет некоторое конечное число по заданной последовательности. Такие функции должны быть хорошо описаны в книге Кнута "Искусство программирования" в отдельной главе. Признаться сам эту главу еще не читал, но примерно знаю о чем она :). Жаль нету под рукой сейчас этой замечательной книги, но я бы очень рекомендовал изучить прежде ту главу, если действительно нужно получить контрольную сумму высокого качества.

Примеров хеш-функций огромное множество. Взять хотя бы тот же знаменитый MD5, или тот метод, что привел выше kmeaw.

И еще раз вспомнил бы о наложении по XOR некоторой псевдо-случайной последовательности на исходную. Например, если {x_i} - исходные данные, а {g_i} - генерируемая псевдо-случайная последовательность (которая всегда одна и та же для любого i и как бы не совсем случайная..), то сумму _намного_ лучше считать уже для обработанной последовательности y_i = x_i ^ g_i. Кажется, у Кнута тоже это есть.

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

Дополнение. Очень часто такое наложение по XOR (или что-то похожее) бывает уже встроенно в сам алгоритм. Вероятно, такая техника присутсвует внутри MD5 и внутри стандартного CRC. Поэтому там такого преобразования делать уже не надо - лишняя трата ресурсов и времени. А вот, при использовании метода, предложенного kmeaw, такое наложение было бы крайне полезным. В общем, нужно смотреть по ситуации.