CRC
Очень вольный пересказ классического текста Ross N. Williams A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS, с лакунами, добавлениями, изменениями, попытками изложить лучше сложные места и пропустить простые. Вообще текст рекомендую, он очень милый и прекрасно написан, но некоторые места мне всё же было сложно понять, поэтому я подошел к ним
( Read more... )
Мы делим в столбик для чего? Чтобы найти остаток от деления.
Собственно, это и есть схема Горнера.
Сейчас мы забудем про то, что исходное кольцо у нас - двоичные многочлены, со своими прикольными операциями сложения и умножения. Нам это вообще не важно (хотя радикально облегчает жизнь, потому что арифметика сводится к сдвигам и ксорам).
Итак, у нас есть число 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
- +------
a modD * 10 + b | abcd divD
---------------
ab modD * 10 + c
----------------
abc modD * 10 + d
-----------------
abcd modD
Reply
(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# становится нетривиальным.
Отсюда и хитрый сдвиговый регистр. Либо табличка значений: abc ⇒ (1000abc)#
Что забавно, - мы вообще не задумываемся про остатки и про деление.
Мы просто взяли кольцо (N, +, *)
Добавили десятичный / тысячеричный сдвиг (при этом умножение нам больше не понадобится)
f(a) = 10a
F(abc) = 1000abc
Получили структуру (N, +, *, f, F)
И применили к ней морфизм в кольцо остатков - (N#, +#, *#, f#, F#)
сложение элементарное (и для его реализации мы бегаем обратно в исходное кольцо), плюс унарные функции - табличные либо на схемотехнике, кому как нравится.
Итого: берём полином, записанный по схеме Горнера
Ах да, давай ещё введу пару суффиксов, a@ = f(a), a$ = (f(a))#
((((a@ + b)@ + c)@ + d)@ -- тут мы для единообразия лишний нолик в конец приписали
и делаем вжух
((((a$ + b)$ + c)$ + d)$
Заменили одну операцию на другую :) Собственно, так работают морфизмы.
А по сути, мы и выполнили остаток столбиком.
Кстати, видно, зачем в конце пихать нолики!
Reply
N = d + 10c + 100b + 1000a ...
N# = (d + (10#)c + (100#)b + (1000#)a ...)#
Пусть мы уже в укрупнённой системе счисления, то есть, D < 10, - чтоб жизнь мёдом не казалась.
Получаем схему на двух аккумуляторах
S = 0, P = 1
S := S + P*d = 0+d
P := P*10 = 10
S := S + P*c = d + 10c
P := P*10 = 100
S := S + P*b = d + 10c + 100b
P := P*10 = 1000
S := S + P*a = d + 10c + 100b + 1000a
А теперь спроецируем её в остатки
S' = S# = 0,
P' = P# = 1
S' := (S' + P' * input)#
P' := (P' * 10)# = P'$
(повторять для всех input из a, b, c, d...)
И вот здесь уже мы прибегнем к хаку.
N# = (0 + P'0*x0 + P'1*x1 + ... )#
Если бы мы были в кольце натуральных чисел, то пришлось бы или брать остатки на каждом шаге, или неограниченно наращивать разрядность, и мы поменяли бы шило на мыло.
А в кольце двоичных полиномов, внезапненько, разрядность остаётся одна и та же.
Поэтому мы ксорим, ксорим, ксорим... И только в конце делаем вжух.
Reply
там такого просто нет нигде.
инвертируются только биты в рамках одного байта -- в каждом байте.
поэтому этот алгоритм _действительно_ можно реализовать переворачивая каждый отдельный байт
ну либо можно извратиться
Reply
Переход в mod D понятен.
>> Но когда станем укрупнять систему счисления, - по-прежнему, не вылезая за D, картинка несколько усложняется
>> (1000abc + def)# = ((1000# * abc)# + def)#
>> Если укрупнили до предела, то есть, 100 < D < 1000, то множитель 1000# становится нетривиальным.
>> Отсюда и хитрый сдвиговый регистр. Либо табличка значений: abc ⇒ (1000abc)#
Ммм, да, но нет. При 32-х разрядном CRC имеем D 33 бита, а мы укрупняем всего до одного байта.
Тут дело не в том, что множитель становится нетривиальным, а в том, что остаток от прошлого раза сравним с D, и теперь, если умножить его на 10^8, то он получится сильно больше, и чтобы поделить за одну операцию мы используем таблицу.
>> Получили структуру (N, +, *, f, F)
N это натуральные числа?
>> ((((a@ + b)@ + c)@ + d)@ -- тут мы для единообразия лишний нолик в конец приписали
>> и делаем вжух
>> ((((a$ + b)$ + c)$ + d)$
не, ну это понятно, если все операции заменить на "по модулю", то мы перемещаемся в кольцо (или что у нас) "по модулю"
>> Заменили одну операцию на другую :) Собственно, так работают морфизмы.
>> Кстати, видно, зачем в конце пихать нолики!
Ну нет :) Просто нужно было + тоже поменять на +#.
Но вопрос же в другом, как мне кажется. Вопрос же как от этой математики обратно спуститься к алгоритмам. Или как от алгоритмов подняться к математике.
Потому что CRC начинается с очень простой идеи деления и очень простого, соответствующего этой идее алгоритма, после чего начинает отклоняться, отклоняться, и через некоторое время оказывается, что алгоритм уже не является делением в общем случае, и в регистре не копятся остатки, и всё это работает только если в конце много-много нулей.
А ещё через некоторое время мы запускаем его битами с обратной стороны и на деление это перестаёт походить вообще.
Reply
У нас оба кольца над одним и тем же множеством.
И когда мы делаем (a# +# b#) *# 1000#
то можем, на самом-то деле, оставить только последнее взятие остатка:
(a# + b) *# 1000
a# - потому что у нас аккумулятор (обработанные старшие разряды) уже остаток
Сложение без остатка у нас элементарное - ксор.
Умножение-и-остаток - табличное.
Вот мы и пришли к схеме:
- взять семечко
- проксорить с очередным байтом/вордом/двордом
- посмотреть в табличку
Она очень технологична.
Reply
то есть нет, нолики не за этим.
Так если всё же попробовать приблизить к тому, что происходит, и взять 10 за байт, и регистр в 4 байта. Больше-меньше у нас удачно нестрогое, так что всё, что >= 10000 можно делить с остатком.
Приходим к
(a * 10000 + bcde) # = ((a * 10000) # + bcde) #
(a * 10000) # можно посчитать по маленькой таблице из 256 элементов
а операция + у нас настолько удачная, что не даёт переноса, поэтому её не надо брать по модулю, тут можно сэкономить. Получаем
abcde # == (a * 10000) # + bcde
Это типа табличный алгоритм. Здорово, хорошее объяснение.
А как перейти от базовых алгоритмов к продвинутым, которые на деление не похожи?
Reply
Это просто остаток от деления полинома abcd0000, где abcd -- уже продвинувшиеся через регистр части.
А не следующем шаге получает сразу abcde0000, и т.п.
И тут тоже работает формула Герона. В смысле, как получить следующий шаг из предыдущего:
abcde0000 # = abcd00000 # + e0000 # = (abcd0000 # * 10 + e0000) # = (xyzf0 + e0000) # = (x0000 + e0000) # + yzf0 = (x + e) * 10000 # + yzf0
вот и оно
Reply
Reply
регистр = 0
пока в сообщении есть ещё байты
в регистр справа задвигаем нулевой байт
регистр ^= таблица[старший_выдвинутый_байт ^ старший_байт_сообщения]
понять, что это деление с остатком крайне сложно
а уж глядя на алгоритм, в котором ещё и байты в регистр не с той стороны задвигаются...
в этом собственно и состоит трудность объяснения -- как мы от деления перешли к этим странным вещам.
Кстати, чего-то мне кажется, что если бы у нас было обычное деление, сделать по таблице бы не получилось бы -- там есть переносы из младших разрядов. Так что то, что мы можем тут реализовать быстрый табличный алгоритм -- не общее свойство, работающее для любого деления, а частное.
Reply
И в любой системе счисления.
Просто нам потребуется расширенная разрядная сетка.
Вот всюду, где я выше написал - там только в одном месте фигурировало, что мы над полиномами.
И то, исключительно в рассуждении "здесь мы можем сделать хак и сэкономить на промежуточных операциях".
Reply
Кажется, для любого деления нам потребуется таблица размером примерно 2^32, хотя смещаем мы только на байт.
И это сразу перестаёт быть практичным.
Reply
Leave a comment