CRC

[fat_crocodile]

Очень вольный пересказ классического текста Ross N. Williams A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS, с лакунами, добавлениями, изменениями, попытками изложить лучше сложные места и пропустить простые. Вообще текст рекомендую, он очень милый и прекрасно написан, но некоторые места мне всё же было сложно понять, поэтому я подошел к ним

Comments

[lj_frank_bot]

Здравствуйте!
Система категоризации Живого Журнала посчитала, что вашу запись можно отнести к категории: 18+.
Если вы считаете, что система ошиблась - напишите об этом в ответе на этот комментарий. Ваша обратная связь поможет сделать систему точнее.
Фрэнк,
команда ЖЖ.

[fat_crocodile]

!!!!

[stierliz]

!

[fat_crocodile]

я думаю, это слово "многочлен" повлияло.

[kodt_rsdn]

Однако, как всё просто становится, когда подчёркивается ключевая идея: что црц - это остаток от деления.

Тогда сразу можно прибегнуть к простым и очевидным вещам вокруг дистрибутивных законов.
И смотреть на кольцо остатков по модулю.
То есть, вынести делитель за скобки.

Сложение ряда x₀ + Bx₁ + B²x₂ + B³x₃ + ... + Bnxn

Группировка разрядов по k штук: (xyz0) + T1(xyz1) + T2(xyz2)
где T = Bk

Рекуррентное сложение с головы или с хвоста - схема Горнера.

И тогда становится понятно, почему на практике мы не делим в столбик, а суммируем, умножаем и делаем какие-то табличные подстановки.

[fat_crocodile]

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

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

Так, кольцо остатков, допустим.
Там правда сложность в том, что деление у нас не обычное. Оно работает на многочленах над GF(2). Так что группировать там члены разных степеней.... Не очень понятно как.

Схему Горнера освежил в памяти, но это же вообще про вычисление значения многочлена, как это связано с делением?

[kodt_rsdn]

Ну смотри.
Мы делим в столбик для чего? Чтобы найти остаток от деления.
Собственно, это и есть схема Горнера.

Сейчас мы забудем про то, что исходное кольцо у нас - двоичные многочлены, со своими прикольными операциями сложения и умножения. Нам это вообще не важно (хотя радикально облегчает жизнь, потому что арифметика сводится к сдвигам и ксорам).

Итак, у нас есть число N = 1000a + 100b + 10c + d, и мы в столбик будем искать остаток.

N mod D = ((1000a mod D) + (100b mod D) + 10c mod D + d mod D) mod D

Деление в столбик: перепишем N по схеме Горнера
(Это полином степеней основания системы счисления; а то, что у нас и арифметика с полиномами - это так, совпадение)

N = ((((a * 10 + b) * 10 + c) * 10 + d)
N mod D = (((((a) modD * 10modD + b) modD * 10modD + c) modD * 10modD + d) modD

a b c d | D

[kodt_rsdn]

Обозначу оператор остатка modD значком суффикса # - чтоб меньше писанины разводить.

(10a + b)# = ((10# * a#)# + b#)#
мы спроецировали из кольца обычной арифметики в кольцо по модулю.

Пока 10 < D, 10# = 10, то есть, это просто сдвиг, очень удобно.
Ну и если разряды числа тоже меньше D, то тоже всё просто:
(10a + b)# = ((10a)# + b)# < D
То есть, у нас возникает операция "сдвиг-и-остаток" (10a)#

Но когда станем укрупнять систему счисления, - по-прежнему, не вылезая за D, картинка несколько усложняется
(1000abc + def)# = ((1000# * abc)# + def)#
Если укрупнили до предела, то есть, 100 < D < 1000, то множитель 1000# становится нетривиальным