CRC32 - вопрос по полиномам. Матан.

Хз что за CRC32, но здесь именно возведение в степень.

Во-первых потому что это полином

Во-вторых в тензорной форме записали бы явно по другому.

И ты бы не вырывал формулу из контекста.

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

Многочлен может быть записан в виде вектора коэффициентов, он не перестаёт от этого быть многочленом. Это просто форма записи

Собственно, в CRC32 речь идёт об обратном отображении: любой вектор чисел однозначно определяет некий многочлен, с которым дальше можно совершать какие-то действия как с обычным многочленом, в том числе и делить его на другой по известным правилам.

То «икс в степени» используется матанщиками просто для обозначения некой независимой размерности от других размерностей?

Можно и так интерпретировать. При этом умножение на х - будет поворотом вектора.

Можно и так интерпретировать.

С-но, поле GF(p^n) по факту является n-мерным линейным пространством на Z_p, при этом определено действие этого пр-ва на самом себе - то есть каждому вектору ставится в соответствие линейный оператор. При этом нетривиальное вложение L -> L*L (где * - тензорное произведение) определяется единственный образом (понятно каким).

Глумёжка над ТС-ом засчитана :D

Можно и так интерпретировать. При этом умножение на х - будет поворотом вектора.

Во. Т.е. это просто удобный матаппарат, который подошёл для обозначения «ортогональности» сих коэффициентов (1/0)?

Т.е. они вместо «икс в степени» могли заюзать какое-то другое матанское средство, а реально в степень никто ничего не возводит?

Да.

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

Грубая схема того, как вычисляется CRC, по шагам:
1. Берём наш файл, проходим его бит за битом от конца к началу, и каждый бит считаем коэффициентом при икс-в-степени-порядковый-номер-бита. Получается многочлен.
2. Делим многочлен из шага 1 на «порождающий» многочлен CRC. Результатом деления являются два многочлена: частное и остаток. Частное нас не интересует. Разрядность остатка не может превосходить разрядность «порождающего» многочлена CRC.
3. Интерпретируем коэффициенты многочлена-остатка из шага 2 как биты некоего двоичного числа (операция, обратная тому, что было проделано на шаге 1). Это число и есть контрольная сумма файла.

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

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

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

http://www.ross.net/crc/crcpaper.html