Дипломная работа: Разработка устройства кодирования-декодирования 32-х разрядных слов методом Хемминга

Контрольная сумма (Checksum) – Число, которое является функцией некоторого сообщения. Буквальная интерпретация данного слова указывает на то, что выполняется простое суммирование байтов сообщения, что, по видимому, и делалось в ран них реализациях расчетов. Однако, на сегодняшний момент, несмотря на использование более сложных схем, данный термин все имеет широкое применение.

Если сложение, очевидно, не пригодно для формирования эффективной контрольной суммы, то таким действием вполне может оказаться деление при условии, что делитель имеет ширину регистра контрольной суммы.

Основная идея алгоритма CRC состоит в представлении сообщения виде огромного двоичного числа, делении его на другое фиксированное двоичное число и использовании остатка этого деления в качестве контрольной суммы. Получив сообщение, приемник может выполнить аналогичное действие и сравнить полученный остаток с "контрольной суммой" (переданным остатком).

Пример:

Предположим, что сообщение состоит из 2 байт (6, 23), как и в предыдущем примере. Их можно рассматривать, как шестнадцатеричное число 0167h, или как двоичное число 0000 0110 0001 0111. Предположим, что ширина регистра контрольной суммы составляет 1 байт, а в качестве делителя используется 1001, тогда сама контрольная сумма будет равна остатку от деления 0000 0110 0001 0111 на 1001. Хотя в данной ситуации деление может быть выполнено с использованием стандартных 32 битных регистров, в общем случае это не верно. Поэтому воспользуемся делением "в столбик". Только на этот раз, оно будет выполняться в двоичной системе счисления:

...0000010101101 = 00AD = 173 =

----_---_---_---_

9= 1001 ) 0000011000010111 = 0617 = 1559 =

0000.,,....,.,,,

----.,,....,.,,,

0000,,....,.,,,

0000,,....,.,,,

----,,....,.,,,

0001,....,.,,,

0000,....,.,,,

----,....,.,,,

0011....,.,,,

0000....,.,,,

----....,.,,,

0110...,.,,,

0000...,.,,,

----...,.,,,

1100..,.,,,

1001..,.,,,

====..,.,,,

0110.,.,,,

0000.,.,,,

----.,.,,,

1100,.,,,