CRC
Очень вольный пересказ классического текста Ross N. Williams A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS, с лакунами, добавлениями, изменениями, попытками изложить лучше сложные места и пропустить простые. Вообще текст рекомендую, он очень милый и прекрасно написан, но некоторые места мне всё же было сложно понять, поэтому я подошел к ним
( Read more... )
Тогда сразу можно прибегнуть к простым и очевидным вещам вокруг дистрибутивных законов.
И смотреть на кольцо остатков по модулю.
То есть, вынести делитель за скобки.
Сложение ряда x₀ + Bx₁ + B²x₂ + B³x₃ + ... + Bnxn
Группировка разрядов по k штук: (xyz0) + T1(xyz1) + T2(xyz2)
где T = Bk
Рекуррентное сложение с головы или с хвоста - схема Горнера.
И тогда становится понятно, почему на практике мы не делим в столбик, а суммируем, умножаем и делаем какие-то табличные подстановки.
Reply
Для меня как раз нифига не очевидно, как от деления переходить дальше, я поэтому в этих местах столько и написал.
Первые пункты это я потом уже расписал, когда задумался, что вдруг кто-то заинтересованный не знает про арифметику по модулю 2 и как делить в столбик.
Так, кольцо остатков, допустим.
Там правда сложность в том, что деление у нас не обычное. Оно работает на многочленах над GF(2). Так что группировать там члены разных степеней.... Не очень понятно как.
Схему Горнера освежил в памяти, но это же вообще про вычисление значения многочлена, как это связано с делением?
Reply
Мы делим в столбик для чего? Чтобы найти остаток от деления.
Собственно, это и есть схема Горнера.
Сейчас мы забудем про то, что исходное кольцо у нас - двоичные многочлены, со своими прикольными операциями сложения и умножения. Нам это вообще не важно (хотя радикально облегчает жизнь, потому что арифметика сводится к сдвигам и ксорам).
Итак, у нас есть число 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 ( ... )
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# становится нетривиальным ( ... )
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# становится нетривиальным ( ... )
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