Лучшие вопросы
Таймлайн
Чат
Перспективы
Циклический избыточный код
Из Википедии, свободной энциклопедии
Remove ads
Циклический избыточный код (англ. Cyclic redundancy check[нет в источнике], CRC[1]) — алгоритм нахождения контрольной суммы, предназначенный для проверки целостности данных[2]. CRC является практическим приложением помехоустойчивого кодирования, основанным на определённых математических свойствах циклического кода.
Remove ads
Введение
Суммиров вкратце
Перспектива
Понятие циклические коды — достаточно широкое[3]. В англоязычной литературе CRC понимается двояко в зависимости от контекста: Cyclic Redundancy Code или Cyclic Redundancy Check[4]. Под первым понятием подразумевают математический феномен циклических кодов, под вторым — конкретное применение этого феномена как хеш-функции.
Циклические коды не только просты в реализации, но и обладают тем преимуществом, что подходят для обнаружения пакетных ошибок: непрерывных последовательностей ошибочных символов данных в сообщениях. Это важно, потому что пакетные ошибки являются распространёнными ошибками передачи во многих каналах связи, включая магнитные и оптические устройства. Обычно n‑разрядный CRC, применяемый к блоку данных произвольной длины, и при расположении контрольной суммы непосредственно вслед за данными, обнаруживает любой одиночный пакет ошибок длиной не более n бит, а доля всех более длинных пакетов ошибок, которые он обнаружит, равна (1 − 2−n).
![]() | Этот раздел нужно дополнить. |
Помехоустойчивое кодирование
Первые попытки создания кодов с избыточной информацией начались задолго до появления современных компьютеров. К примеру, ещё в 1960-х годах Ридом и Соломоном была разработана эффективная методика кодирования — Код Рида-Соломона. Использование её в те времена не представлялось возможным, так как произвести операцию декодирования за разумное время первыми алгоритмами не удавалось. Точку в этом вопросе поставила фундаментальная работа Берлекэмпа, опубликованная в 1968 году. Эта методика, на практическое применение которой указал через год Мэсси, и по сей день используется в цифровых устройствах, обеспечивающих приём RS-кодированных данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего октеты).
Но далеко не всегда от кода требуется коррекция ошибок. Многие современные каналы связи обладают приемлемыми характеристиками, и зачастую достаточно лишь проверить, успешно ли прошла передача или возникли какие-нибудь сложности; структура же ошибок и конкретные позиции неверных символов совершенно не интересуют принимающую сторону. И в этих условиях очень удачным решением оказались алгоритмы, использующие контрольные суммы. CRC как нельзя лучше подходит для подобных задач: невысокие затраты ресурсов, простота реализации и уже сформированный математический аппарат из теории линейных циклических кодов обеспечили ей огромную популярность.
Хотя код CRC используют обычно только для обнаружения ошибок, его математические свойства дают возможность найти и исправить одиночную ошибку в блоке бит, если каждому биту защищаемого блока (включая проверочные биты) соответствует свой уникальный остаток от деления на порождающий многочлен. Например, если порождающий многочлен неприводим, и длина блока не превышает порядок порождённой циклической группы.
Контрольная сумма
В общем виде контрольная сумма представляет собой некоторое значение, вычисленное по определённой схеме на основе кодируемого сообщения. Проверочная информация при систематическом кодировании приписывается к передаваемым данным. На принимающей стороне абонент знает алгоритм вычисления контрольной суммы: соответственно, программа имеет возможность проверить корректность принятых данных.
При передаче пакетов по сетевому каналу могут возникнуть искажения исходной информации вследствие разных внешних воздействий: электрических наводок, плохих погодных условий и многих других. Сущность методики в том, что при хороших характеристиках контрольной суммы в подавляющем числе случаев ошибка в сообщении приведёт к изменению его контрольной суммы. Если исходная и вычисленная суммы не равны между собой, принимается решение о недостоверности принятых данных, и можно запросить повторную передачу пакета.
Remove ads
Математическое описание
Суммиров вкратце
Перспектива
Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем . Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен[англ.].
Каждой конечной последовательности битов взаимно однозначно сопоставляется двоичный полином , последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:
Количество различных многочленов степени, меньшей , равно , что совпадает с числом всех двоичных последовательностей длины .
Значение контрольной суммы в алгоритме с порождающим многочленом степени определяется как битовая последовательность длины , представляющая многочлен , получившийся в остатке при делении многочлена , представляющего входной поток бит, на многочлен :
где
- — многочлен, представляющий значение CRC;
- — многочлен, коэффициенты которого представляют входные данные;
- — порождающий многочлен;
- — степень порождающего многочлена.
Умножение осуществляется приписыванием нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.
При делении с остатком различных исходных многочленов на порождающий полином степени можно получить различных остатков от деления. зачастую является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хеш-функции в контексте каждого конкретного применения.
Тем не менее, существует множество стандартизированных образующих многочленов, обладающих хорошими математическими и корреляционными свойствами (минимальное число коллизий, простота вычисления), некоторые из которых перечислены ниже.
Remove ads
Вычисление CRC
Суммиров вкратце
Перспектива
Параметры алгоритма
Одним из основных параметров CRC является порождающий полином.
С порождающим полиномом связан другой параметр — его степень, которая определяет количество битов, используемых для вычисления значения CRC. На практике наиболее распространены 8-, 16- и 32-битовые слова, что является следствием особенностей архитектуры современной вычислительной техники.
Ещё одним параметром является начальное (стартовое) значение слова. Указанные параметры полностью определяют «традиционный» алгоритм вычисления CRC. Существуют также модификации алгоритма, например, использующие обратный порядок обработки битов.
Описание процедуры
Из файла берётся первое слово — это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR с порождающим полиномом. Соответственно, если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига теряется старший бит, а на место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла в слове остаётся остаток, который и является контрольной суммой.
Популярные и стандартизованные полиномы
Суммиров вкратце
Перспектива
В то время как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу[1][5].
Этот парадокс касается и выбора многочлена-генератора: зачастую стандартизованные полиномы не являются самыми эффективными в плане статистических свойств соответствующего им check redundancy code.
При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах группа учёных занималась исследованием порождающих многочленов разрядности до 16[1] 24 и 32 бит[6][7] и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле кодового расстояния[7]. Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.
Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI; также этот многочлен является генератором кода Хемминга[8]. Использование другого полинома — CRC-32C — позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше, поэтому в наши дни он тоже пользуется популярностью[7]. К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке.
Ниже в таблице перечислены наиболее распространённые многочлены — генераторы CRC. На практике вычисление CRC может включать пре- и постинверсию, а также обратный порядок обработки битов. В проприетарных реализациях CRC для усложнения анализа кода применяют ненулевые начальные значения регистров.
Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время[когда?] вытеснены криптографическими хеш-функциями.
Remove ads
Спецификации алгоритмов CRC
Суммиров вкратце
Перспектива
Одной из самых известных является методика Ross N. Williams[25]. В ней используются следующие параметры:
- Название алгоритма (name);
- Степень порождающего контрольную сумму многочлена (width);
- Сам производящий полином (poly). Для того, чтобы записать его в виде значения, его сначала записывают как битовую последовательность, при этом старший бит опускается — он всегда равен 1. К примеру, многочлен в данной нотации будет записан числом . Для удобства полученное двоичное представление записывают в шестнадцатеричной форме. Для нашего случая оно будет равно или 0x11;
- Стартовые данные (init), то есть значения регистров на момент начала вычислений;
- Флаг (RefIn), указывающий на начало и направление вычислений, для обнаружения пакетов ошибок должно соответствовать порядку передачи в канале[англ.]. Существует два варианта: False — начиная со старшего значащего бита (MSB-first) или True — с младшего (LSB-first);
- Флаг (RefOut), определяющий, инвертируется ли порядок битов регистра при входе на элемент XOR;
- Число (XorOut), с которым складывается по модулю 2 полученный результат;
- Значение CRC (check) для строки «123456789» .
- Примеры[26]
Remove ads
Примечания
Литература
Ссылки
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads