CRC FAQ. Что, зачем и как
Глава 1. Что такое CRC и зачем он нужен
CRC (cyclic redundancy code) — циклический избыточный код, иногда называемый также контрольным кодом. По своей сути — это просто вычисленное на основе исходного передаваемого сообщения число (или можно сказать код), которое передаётся вместе с самим сообщением (дописывается в конец информационной части) и служит для контроля его безошибочной передачи.
Число это вычисляется по определённым правилам и всегда имеет строго определённое заранее количество разрядов. Очень удобно заранее знать, сколько разрядов занимает контрольное число, потому что иначе станет заранее неизвестной длина сообщения целиком, вместе с CRC, даже при условии, что мы точно знаем длину информационной части. Кроме того, это позволяет заранее выделить для вычисления CRC регистр нужного размера.
Никакой дополнительной информационной нагрузки это число не несёт, поэтому с точки зрения передачи полезной информации оно избыточно. Однако, как я уже сказал, его наличие позволяет диагностировать некоторое количество ошибок, если такие возникают при передаче.
Глава 2. Базовая теория, необходимая для вычисления CRC
По большому счёту, вся теория нахождения CRC базируется на двух вещах.
Первое. Любое сообщение можно представить в виде одного большого двоичного числа и считать что значения разрядов этого числа кодируют коэффициенты некоторого полинома.
Например, возьмём сообщение «15». В шестнадцатиричном виде оно кодируется так: 0x31,0x35. Если перевести эту запись в двоичную форму и записать всё в одну строку, то получим: 00110001 00110101. Если считать, что каждый разряд полученного числа — это коэффициент полинома, то этот полином будет иметь вид:
0*x 15 +0*x 14 +1*x 13 +1*x 12 +0*x 11 +0*x 10 +0*x 9 + 1*x 8 +0*x 7 +0*x 6 +1*x 5 +1*x 4 +0*x 3 +1*x 2 + 0*x 1 +1*x 0
Кратко его можно записать так: x 13 +x 12 +x 8 +x 5 +x 4 +x 2 +1
По большому счёту, мы можем оставить и двоичную запись (чаще всего так и делают, иксы писать неудобно), но будем помнить, что теперь это не просто число, а вектор, составленный из коэффициентов полинома (можно даже продолжать называть такие вектора полиномами). Причём нулевые коэффициенты при старших степенях можно опустить (в дальнейшем вы увидите, что нулевые коэффициенты при старших степенях ни на что не влияют) и написать его в виде 11000100110101.
Второе. Количество разрядов любого двоичного сообщения — это вполне конкретные, конечные числа. Соответственно, множества всех возможных N-разрядных сообщений (где N-любое целое положительное число), составленных по описанному выше способу, — это конечные множества. При использовании особой алгебры такие конечные множества можно считать конечными полями, являющимися расширением простого конечного поля GF(2). Соответственно, любые полиномы, коэффициенты которых составлены из значений разрядов двоичных чисел, можно рассматривать как многочлены над конечным полем.
Подробно многочлены над конечными полями изучаются в отдельном разделе математики, в который мы не будем сильно углубляться в рамках этой статьи. Если кто-то хочет узнать больше — вектор поисков для самостоятельного изучения, я считаю, вполне определён. Нам же интересно, что это за особая алгебра и как это связано с вычислением CRC.
Так вот, отличия этой алгебры от обычной заключаются в следующем:
— операции сложения и вычитания в ней тождественны и выполняются как сложение по модулю 2 (XOR),
— вместо понятий «меньше»/»больше» используются понятия «старше»/»младше». Старшим считается многочлен с большей степенью (наибольшая степень, у которой коэффициент при x равен единице). Например x 3 +1 старше, чем x 2 +x, потому что 3>2.
Нахождение CRC заключается в делении с остатком информационного полинома (тот который составлен из информационного сообщения) на некоторый специальный полином. Делим мы как обычно — столбиком, но вместо операции «вычитания» используем «сложение по модулю 2» и продолжаем деление до тех пор, пока оставшийся в делимом полином не окажется младше полинома делителя. Полученный остаток — это и есть CRC.
Для примера разделим рассмотренный выше полином, составленный из сообщения «15», на полином x 4 +x+1, для чего сначала запишем последний полином со всеми коэффициентами в явном виде (1*x 4 +0*x 3 +0*x 2 +1*x 1 +1*x 0 ), а потом запишем эти коэффициенты в виде вектора (10011). Деление будет выглядеть так, как на рисунке справа.
Нули в самом начале делимого, как я и обещал, нам не пригодились, точно также, как они не пригодились бы нам и при обычном делении.
Идём далее. Что это за специальный полином, на который мы делим наше представленное в виде полинома сообщение?
А это как раз один из основных параметров CRC-алгоритма, называемый также порождающим многочленом или порождающим полиномом. В качестве порождающего многочлена обычно берут какой-либо неприводимый многочлен.
Деление с остатком на полином степени N позволяет получить 2 N различных остатков от деления, причем все эти остатки можно описать N-1 разрядными векторами.
Описанные выше действия — это то, что мы по сути всегда делаем при нахождении CRC. Такое описание алгоритма удобно теоретикам и неудобно инженерам. Поэтому теперь перейдём к частностям, которые приближают нас к практической действительности.
Глава 3. Модификация алгоритма для практического применения.
Посмотрим ещё раз внимательно на наш пример деления столбиком и обратим внимание вот на что — при вычислениях мы фактически всегда оперируем только пятью битами, а могли бы оперировать и четырьмя, поскольку во всех операциях XOR у нас самый старший бит равен единице и он всегда сокращается. То есть, если считать, что вычисления происходят в каком-то выделенном четырёхбитном регистре, то всё деление будет выглядеть так, как будто мы просто на каждом шаге сдвигаем биты в регистре влево, загружая новое значение младшего бита, а старший бит просто выкидываем, если он равен нулю, или, если он равен единице, выполняем XOR регистра и младших четырёх битов порождающего полинома.
То есть теперь можно описать наш алгоритм так: побитно загружаем наше информационное сообщение в регистр нужного размера (на единицу меньше степени порождающего полинома), каждый раз сдвигая регистр влево и помещая новый бит в младший разряд. При этом, если вытесняемый из регистра старший бит равен единице, то выполняем XOR регистра со всеми битами порождающего полинома, кроме старшего. Значение регистра после обработки всего сообщения — это и есть CRC.
На картинке слева тот же самый пример, который мы рассматривали выше, но оформленный в соответствии с новым (инженерным) описанием алгоритма вычисления CRC (хотя по сути, это то же самое деление, что и выше).
Одно отличие в нашем инженерном алгоритме от рассматриваемого выше деления столбиком всё же есть. Отличие это заключается в начальном значении регистра. Мы инициализировали регистр нулями. В итоге наше сообщение стало несколько длиннее первоначального. Как мы знаем, нули в начале сообщения не влияют на результат вычислений, их там можно хоть сколько написать. Но ведь можно инициализировать регистр и не нулями.
Что изменится? Да особенно ничего, просто мы тогда будем искать CRC для несколько модифицированного исходного сообщения (с приписанными в начале битами). Если тот, кто будет определять правильность передачи сообщения, знает об этом и знает какое значение для инициализации регистра нужно выбирать, то он сможет правильно посчитать CRC. Надо сказать, что на практике чаще всего используется инициализация всего регистра нулями или инициализация всего регистра единицами.
Ещё одна особенность практической реализации основана на таком свойстве деления с остатком: если C — это остаток от деления A на B, то остаток от деления (A-C) на B будет равен нулю, а остаток от деления (A-C+D) на B будет равен D (если D 4 +x+1
Параметры, определяющие формирование битовой последовательности должны описывать:
- начальное значение регистра, в котором вычисляется CRC.
- битовую последовательность, которая дописывается в конце сообщения.
- порядок записи бит в байтах и байтов в словах исходного сообщения.
Наличие последнего параметра связано с тем, что сообщения как правило передаются побайтно и при этом возможны два варианта передачи: старшим битом вперёд (в этом случае биты исходного сообщения располагаются в битовой последовательности, для которой вычисляется CRC, в нормальном порядке) или младшим битом вперёд (в этом случае биты исходного сообщения располагаются в битовой последовательности, для которой вычисляется CRC, в обратном порядке). Причём, иногда переворачивают не только биты в байтах, но и, например, байты в словах. Кстати говоря, во всех примерах, которые приводятся в этой статье, рассматривался только нормальный порядок бит (старшим битом вперёд).
Кроме того, иногда полученный в результате деления остаток дополнительно инвертируют и в качестве CRC используют не сам остаток, а это инвертированное значение.
Помимо описанного в этой статье прямого способа вычисления, существует, так называемый, табличный или быстрый способ расчёта CRC, но об этом как-нибудь в другой раз. А на сегодня, пожалуй, всё.
Источник
Ошибка в данных CRC — как исправить
Ошибка в данных CRC может возникнуть в самых разных случаях: при инициализации жесткого диска или работе с внешним жестким диском, картой памяти или флешкой, попытках произвести действия с накопителем в DISKPART, часто — при установке программ и игр, скачанных с торрента.
Текст ошибки также может быть разным: от простого сообщения диспетчера виртуальных дисков об ошибке в данных при инициализации диска, сообщений «DISKPART обнаружила ошибку: Ошибка в данных (CRC)» или «Расположение недоступно. Нет доступа к диску, ошибка данных (CRC)» при действиях с HDD, картой памяти или USB накопителем, до окон вида «CRC error» или «Ошибка копирования файла» с указанием на файлы устанавливаемого ПО. В этой инструкции подробно о причинах такой ошибки, что она означает и о возможных методах её исправить.
Что такое ошибка CRC и причины ошибки
CRC (Cyclic Redundancy Check) или Циклический избыточный код представляет собой метод обнаружения ошибок при передаче данных с помощью контрольных сумм, используемый при обмене блоками данных с накопителями, а также в сетях, предназначенный для обнаружения изменений в передаваемых данных.
В случае с жесткими дисками и SSD, SD-картами и флешками, при обмене данными CRC используется для проверки их целостности после передачи: один и тот же алгоритм применяется к передаваемому и полученному блокам данных и в случае различного результата делается вывод об ошибках CRC.
Наиболее распространенные причины рассматриваемой проблемы:
- Ошибка CRC для HDD и SSD, карт памяти, USB-накопителей при инициализации, форматировании, обмене данными, изменении свойств дисков:
- Проблемы с подключением накопителя — особенно распространено для SATA-жестких дисков, внешних HDD
- Повреждения файловой системы диска
- Аппаратные неисправности накопителя, контроллера
- Антивирусное ПО и другие программы, имеющие возможность менять данные в оперативной памяти
- Проблемы с оперативной памятью, в некоторых случаях — нестабильная работа RAM или CPU в разгоне.
- Иногда — аппаратные неисправности электронных компонентов самого компьютера или ноутбука, отсутствие заземления и статика на USB разъемах (при работе с внешними накопителями), недостаток питания для работы внешнего HDD.
- Ошибка CRC при установке игр и программ:
- Нарушение целостности данных при скачивании установщика
- Аппаратные неисправности или ошибки файловой системе на диске, с которого запускается установщик
- Ошибки при архивации установщика (установщики игр и программ — это, по сути, архивы).
- Антивирусное ПО, особенно распространено для не самых лицензионных программ: при их установке антивирус может применять действия к подозрительным данным в памяти, что может выливаться в ошибку CRC.
- Ошибки оперативной памяти, разгон RAM и CPU.
И отдельно про оптические диски DVD, CD, Blu-ray — ошибка в данных CRC для них может говорить о физическом повреждении записи (в том числе и самопроизвольном по истечении некоторого времени после записи), о загрязненной поверхности диска, иногда — проблемах с работой привода для чтения дисков.
Как исправить ошибку в данных CRC
В зависимости от того, в какой ситуации вы столкнулись с ошибкой CRC — при каких-либо действиях с накопителем, например, при инициализации жесткого диска или при установке игр и программ, их запуске, а также при распаковке архивов, действия будут отличаться, рассмотрим варианты решения для каждого случая.
Ошибка при инициализации жесткого диска, обращениях к внешним HDD, SSD, картам памяти и USB-накопителям
Прежде чем приступить к изложенным далее методам исправления, при наличии возможности рекомендую попробовать подключить этот накопитель к другому компьютеру или ноутбуку, а для внутренних накопителей SATA при подключении на другом устройстве — использовать другой кабель.
Если на другом компьютере диск, карта памяти или флешка работает исправно, из приведённых далее методов можно использовать только те, которые имеют отношение к самому компьютеру и операционной системе, с диском всё в порядке. Если же и на другом компьютере возникает ошибка в данных CRC, ищем проблему в самом накопителе.
Единственного рабочего метода исправить ошибку данных CRC для диска нет и иногда мы имеем дело с его аппаратной неисправностью. Среди возможных способов решения проблемы:
- Если на компьютере или ноутбуке ранее любым способом включался разгон памяти или процессора, отключите его. Если в последнее время менялась конфигурация, например, добавлялись модули RAM, верните исходную конфигурацию и посмотрите, не приведёт ли это к исчезновению ошибки.
- Проверьте работу, загрузив Windows в безопасном режиме (Как зайти в безопасный режим Windows 10). При загрузке в безопасном режиме встроенный антивирус Windows 10 и 8.1 не запускается. Если при наличии стороннего антивируса он запустился — временно отключите и его. Проверьте, сохраняется ли ошибка. Если ошибка CRC не возникает, ошибка может быть как в антивирусе (более вероятно), так и в сторонних службах и фоновых программах из автозагрузки (которые также не запускаются в безопасном режиме).
- Следующее действие лучше всего выполнять, не выходя из безопасного режима. Если диск с ошибкой инициализирован и ему присвоена буква, запустите командную строку от имени администратора и введите следующую команду, заменив букву диска D на свою (подробнее: Проверка жесткого диска на ошибки).
Выполнение команды может занять очень продолжительное время, не выполняйте при питании от батареи на ноутбуке.
Внимание: при рассматриваемой ошибке обновление прошивки может привести и к полной неработоспособности диска.
Одно из решений должно позволить исправить ошибку в данных CRC, при условии, что мы не имеем дело с аппаратной неисправностью диска. Если к настоящему моменту времени работа диска не была проверена на другом компьютере — найдите возможность сделать это, а при сохранении проблемы от использования накопителя придется отказаться.
Если диск содержит важные данные и инициализируется в системе, вы можете использовать бесплатные программы для восстановления данных (с большой вероятностью подойдет DMDE в режиме просмотра содержимого томов), если не инициализируется — останется обратиться в специализированную лабораторию для восстановления.
Ошибка возникает при установке игр и программ или при их запуске
В случае, если ошибка в данных CRC появляется при попытках установить или запустить какое-либо программное обеспечение, возможными вариантами решения будут:
- Отключение вашего антивируса, повторная загрузка установщика игры или программы, добавление папки с установщиком и папки, куда производится установка в исключения антивируса, запуск установки.
- Загрузка установщика из другого источника.
- В случае если не запускается программа, которая раньше работала — использование точек восстановления системы при их наличии, переустановка программы.
- Отключение разгона оперативной памяти и процессора, отключение утилит для очистки оперативной памяти при их наличии.
- Проверка жесткого диска на ошибки командой из 3-го шага предыдущего раздела.
- Загрузка установщика программы на другой физический диск, если на компьютере их более одного.
- В случае недавнего изменения аппаратной конфигурации компьютера, добавления или замены RAM, попробуйте вернуть исходную конфигурацию и проверить, сохраняется ли ошибка.
- В редких случаях причиной проблемы могут быть символы кириллицы в пути к файлу установщика или в пути к месту установки: проверьте, сохранится ли ошибка если исключить кириллицу в именах папок и полных путей к этим расположениям.
И, в завершение, если один из способов помог в исправлении ошибки в данных CRC, буду благодарен вашему комментарию с описанием ситуации и решения: это поможет составить статистику, которая будет полезной другим читателям.
Источник
