Обсуждение:Циклический избыточный код

↓

Пожалуйста, добавляйте новые темы снизу

Я у няни

Просмотрел анг. вики, и задался логичным вопросом: почему они, "тупые", могут обяснить принцип без формул, а наши "вумные" - в первом же разделе "Алгоритмы" напихали тучу формул где, извините, мне, не математику, ни х#$а не ясно... В который раз на ру.вики убеждаюсь что мат. статьи пишут какие-то задроти которые хотят повипендриватся, а чтоб объяснит что-то, так им не интересно. Я уже на 90% уверен что проще посидеть и перевести англ.вики и понять тему, чем заниматься любовью с попытками понять наши топики. --ol_b 10:26, 24 января 2012 (UTC)

• Ну как разберетесь - перепишите статейку как сочтете правильным. Впрочем беглый осмотр английской версии показывает что там просто послали в другие статьи за объяснениями что же такое CRC. В этих самых других статьях формулы не хуже. ASDFS 12:25, 24 января 2012 (UTC)

слово "полином" ссылкой

слово "полином" стоит сделать ссылкой на другую статью. — Эта реплика добавлена с IP 85.90.121.75 (о) 13:31, 2 апреля 2008 (UTC)

примеры кода

Примеры кода в статье на C, а не на C++. 92.124.84.174 20:04, 10 января 2009 (UTC)

Почему сумма?

Вычисление контрольной суммы — другой алгоритм, не CRC, основанный на сложении всех байт, например, исходного массива. В вычислении CRC нет ни одной операции сложения. — Эта реплика добавлена с IP 195.222.71.77 (о) 22:12, 18 мая 2009 (UTC)

• Не понимайте всё так буквально: контрольной суммой может являться не только банальная сумма байтов. С другой стороны, с теоретической точки зрения, CRC - это деление полиномов, а там сложение есть. -- A^VB^talk 05:11, 19 мая 2009 (UTC)

int long dword и прочее. Господа, определитесь!

Пожалуйста сформулируйте причины откатов правок AterLux 12:02, 10 сентября 2009 (UTC)

Перенесено со страницы User talk:AVB#long.

Где это вы видели не 32 битный long ? :)--77.87.200.242 09:52, 10 сентября 2009 (UTC)

• Во-первых, раньше он мог быть и 16-битным. Во-вторых, вы забываете о другой стороне вопроса - эффективности. Если на некоторой 32-битной платформе long 64-битный, то мы будем иметь потери и в памяти, и в скорости. Правильная типизация избавляет от оооочень многих проблем. -- A^VB^talk 09:55, 10 сентября 2009 (UTC)

• Это int на многих 16-битных и 8-битных системах бывает 16-битным. А long всегда 32 бита. Правильная типизация это хорошо в реальных приложениях, но в примере, имхо, она излишняя, ибо делает код сложнее. Вы переписали код исходя из линуксовых стандартов, но Си используется не только на линуксах.--77.87.200.242 10:05, 10 сентября 2009 (UTC)

• делает код сложнее - она делает код надёжнее и эффективнее. линуксовых стандартов - на это я могу вам только ответить, что вы давно не перечитывали стандарт языка Си. stdint - это стандарт уже больше десяти лет (с C99, а может и раньше, я уже не помню). Просто в Си всё как всегда делается через задницу, но линукс тут как бы непричём. -- A^VB^talk 10:12, 10 сентября 2009 (UTC)

• Для примеров не нужна надёжность и эффективность портирования, а нужна предельная простота. Кстати в английской википедии есть целая статья о stdint.h :)--77.87.200.242 10:20, 10 сентября 2009 (UTC)

• предельная простота - в таком случае не используйте реальный язык, особенно вроде C/C++ (в них слишком много заморочек), а используйте псевдокод. Это во-первых. Во-вторых, утверждать, что использование int или long проще, чем uint_least32_t, можно только с большоооооооооооооооооой натяжкой. -- A^VB^talk 10:30, 10 сентября 2009 (UTC)

• Проще, и вы об этом знаете, поскольку вы сами же его оставили, когда переносили объявление i и j. А псевдокод всё равно сложнее реального языка, при условии что реальный язык знают многие, а в псевдокоде надо ещё разбираться. Хотя если я перепишу на Паскаль (как более приближенный к человеческому) вы сильно возражать не будете? Кстати, вы заметили, что первый пример "Пример программы расчёта CRC32 на языке Си" также является табличным, но таблица рассчитывается на лету?--77.87.200.242 11:03, 10 сентября 2009 (UTC)

• переносили объявление i и j - не понял, а это тут причём? i и j я перенёс потому, что в Си это синтаксическая ошибка, к uint_least32_t это не имеет никакого отношения. вы сильно возражать не будете - я, вообще-то, и его знаю - но зачем переписывать? Это вы про простоту заговорили, не я. вы заметили - вообще-то, я как бы в курсе этого вопроса. Оригинальный алгоритм является битовым, и есть промежуточный вариант, обрабатывающий входной поток ниблами (по 4 бита, вместо 8-битных байтов-октетов), которому нужна таблица всего на 16 значений. -- A^VB^talk 11:11, 10 сентября 2009 (UTC)

• я, вообще-то, и его знаю - но зачем переписывать? Это вы про простоту заговорили, не я. - правильно ли я понял, что если предложили не вы, то возражать вы будете? Отмена правки 18351316 участника 77.87.200.242 это не лишнее, поскольку переменная может быть больше 32 би - значит поставленный вами тип uint_least32_t теперь уже может быть больше 32 бит? Или вы отменили правку по другой причине, не указанной в описании изменений? --77.87.200.242 11:32, 10 сентября 2009 (UTC)

• если предложили не вы, то возражать вы будете - не понимаю, к чему вы клоните. Если вы хотите заменить сишный вариант паскалевским, то вам лучше это сначала предложить в обсуждении статьи. может быть больше 32 бит - конечно. Вы хотя бы в кратце пролистайте упомянутую вами статью в англовики про stdint. -- A^VB^talk 11:56, 10 сентября 2009 (UTC)

Я в сях не силён, но почитал это, там написано что long как минимум 32 бит, в то время как int может быть и 16 бит. Поэтому int не походит. Но на 32битных платформах, как понимаю int = 32 бит, а long = 2 х 32 бит, что так же делает его неприятным. Что такое uint_least32_t ? Есть ли в C++ более понятные на глаз и однозначные типы вроде DWORD например? AterLux 15:18, 10 сентября 2009 (UTC)

• long = 2 х 32 бит - не обязательно, long может быть равен int, а может быть равен, к примеру, 10*sizeof int. uint_least32_t - один из стандартных типов, введённых в C99 или даже раньше. Подробнее читайте в стандарте (ссылка есть в статье о языке) или в en:stdint.h. C++ - в C++ этих типов не было (но я за новинками не слежу, могло и появиться), это стандарт языка Си. однозначные типы вроде DWORD - неужели? И что же "однозначного" в подобном типе? С чего вы взяли, что и word, и dword, и даже byte равны какой-то фиксированной величине (как я понимаю, вы расчитываете, что dword=2*word, word=2*byte, byte=8?)? -- A^VB^talk 23:54, 10 сентября 2009 (UTC)

• long как минимум 32 бит - совершенно верно, AterLux. Поэтому всё можно сделать на longах, при учёте что он вдруг по AVB станет большим.--77.87.200.242 08:58, 14 сентября 2009 (UTC)

CRC vs FCS

Надо заметить, что помимо СRC суммы есть и FCS [1] Вот тут есть описание после слов "16-bit FCS Computation Method" Пожадуйста добавьте его. А то со страницы VHDL ссылка на контрльную сумму есть, а ссылка на CRC-16, это совсем не та сумма.

Konstantin BY 13:28, 18 сентября 2009 (UTC)

CRC16-CCITT init

Оборудование с которым я работаю, считает CRC-16-CCITT с инициализацией в 0x1021 (который хотя и совпадает с полиномом, но различие между ними я понимаю). Вопрос: как правильно? Кто нибудь видел оборудование работающее по CCITT но с другой инициализацией контрольной суммы? AterLux 05:02, 3 ноября 2009 (UTC)

• Вопрос, конечно, интересный. Про оборудование ничего не скажу, но отталкиваться нужно не от конкретного оборудования, а от спецификаций. Так вот, имеющиеся в у меня сорсы либо инициализируют в 0, либо, как описано в имеющемся у меня в данный момент на руках A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS от Ross N. Williams, версия 3 от августа 1993 года, раздел "16. A Catalog of Parameter Sets for Standards", Init равен FFFF. Причём местный раздел "Классификация реализаций алгоритмов CRC", похоже, основан на табличках оттуда. -- A^VB^talk 02:01, 4 ноября 2009 (UTC)
  • Посмотрите по этой ссылке. Имя алгоритма "KERMIT".

Modbus

В разделе Наиболее используемые и стандартизованные CRC в таблице указано, что CRC-16-IBM используется протоколом Modbus. Это не совсем так. Для CRC Modbus можно сопоставить следующие параметры модели RockSoft:

• Width = 16
• Poly = 8005
• Init = FFFF
• RefIn = true
• RefOut = true
• XorOut = 0

В то время, как для CRC-16-IBM параметр Init=0. При этом, полученное значение записывается младшим байтом вперёд. Считаю необходимым убрать Modbus из списка. GoronkovKA 19:54, 19 января 2011 (UTC)

• Эта таблица вообще страдает недосказанностью актуальных параметров и по идее ее надо конкретно дорабатывать. В данном случае убирать Модбас не надо а надо добавить еще строчку с CRC16-ModbusRTU. ASDFS 09:29, 20 января 2011 (UTC)
  • Точно. Еще заметил, что в той-же таблице в колонке Представления есть представление реверсированное от обратного, которое на самом деле далеко не представление нормального полинома. В Элементарном руководстве по CRC в §12 "Зеркальные полиномы" сказано, что зеркальный, который в таблице назван обратным, тоже является хорошим, если нормальный полином хорош в смысле вычисления CRC, то есть он не относится непосредственно к вычислению CRC по указанному в строчке алгоритму, а лишь является "тоже хорошим" - таким, который можно использовать в других алгоритмах, и при этом получать схожие результаты по обнаружению ошибок. По этой причине следует указать алгоритм вычисления зеркального (или, как он назван в таблице, обратного полинома), но убрать все вхождения "представления" реверсированное от обратного из таблицы. --GoronkovKA 12:19, 20 января 2011 (UTC)

Неосвещенное свойство CRC

У CRC есть важное и широко используемое свойство, почему-то не описанное в данной статье — если дописать к блоку данных его CRC (в порядке big-endian), CRC полученного блока будет равен 0, что значительно упрощает проверку. В английском разделе об этом написано. Grain 22:05, 21 марта 2011 (UTC)

• Удобнее если дописывать поксоренный с константой CRC, тогда не ноль получится. ASDFS 09:55, 22 марта 2011 (UTC)

э ... 10x, кэп :) а смысл такого xor-a ? и чем это удобнее и проще проверки на ноль ? Grain 15:21, 22 марта 2011 (UTC)

Начальное значение ноль и данные ноль -> CRC тоже ноль, что приведет к невыявлению ошибки длины данных. Специфическая ситуация но вполне возможная. ASDFS 16:07, 22 марта 2011 (UTC)

В целом мысль понятна, хотя описанная ситуация больше похожа на баг — sizeof(блок+CRC) никак не должен быть нулевым, разве что проверка длины пропущена из соображений производительности, полагаясь на штамм CRC о котором вы говорите. По крайней мере об этом свойстве нативного (немодифицированного) CRC, было бы неплохо сказать, правда сначала придется отделить native от not-native. Grain 22:53, 24 марта 2011 (UTC)

Если Если параметры RefIn и RefOut будут равны, a XorOut=0000, то Вы получите Ваше неосвещённое свойство CRC.GoronkovKA 08:08, 12 апреля 2011 (UTC)

Всё строго зависит от того как и куда считается CRC, начиная с какого бита, как инициализируется и т.д. и т.п. Например всеми наими любимое CRC-32 (IEEE 802.3) инициализируемый через 0xFFFFFFFF, в результате такой операции даст вовсе не 0, и даже не -1 (0xFFFFFFFF), а вполне даже 0xDEBB20E3 AterLux 12:02, 27 июля 2011 (UTC)

Стиль примеров программ

Добрый день. Считаю, что примеры очень плохо читаются, особенно для людей незнакомых с Си (я тоже не сразу все понял, хотя на Си программировать микроконтроллеры приходится):

       for (i = 0; i < 8; i++)
           crc = crc & 0x80 ? (crc << 1) ^ 0x31 : crc << 1;

Может выражение в цикле заменить на if else ? --193.233.70.76 09:07, 25 марта 2011 (UTC) Алексей Анучин anuchinas@mpei.ru

• Так вам больше нравится:

unsigned long CRC32CCITT_ByteCount(BYTE _D, unsigned long _crc)
{
BYTE		_mask;
#define		CRC32_Polynom	0xEDB88320
	_mask = 1;
	do {
		if (_crc & 1) {
			if (_D & _mask)
				_crc = _crc >> 1;
			else
				_crc = (_crc >> 1) ^ CRC32_Polynom;
		} else {
			if (_D & _mask)
				_crc = (_crc >> 1) ^ CRC32_Polynom;
			else
				_crc = _crc >> 1;
		}
	} while (_mask <<= 1);
	return (_crc);
}
unsigned long CRC32CCITT_ArrayCount(BYTE *_ptr, unsigned long _len)
{
unsigned long	CRC32_Value;
	CRC32_Value = 0xFFFFFFFF;
	while (_len--) {
		CRC32_Value = CRC32CCITT_ByteCount(*_ptr, CRC32_Value);
		_ptr++;
	}
	CRC32_Value ^= 0xFFFFFFFF;
	return (CRC32_Value);
}

ASDFS 13:06, 25 марта 2011 (UTC)

У меня как-то проще получалось (фрагмент из драйвера MODBUS):

RxCRC^=RxReg;
for (i=0; i<8; i++)
	if (RxCRC&0x01)
	{
		RxCRC>>=1;
		RxCRC^=MagicNumber;
	}
	else
		RxCRC>>=1;

Единственное, операции присваивания в сочетании с операцией тоже можно раскрыть:

RxCRC=RxCRC^RxReg;
for (i=0; i<8; i++)
	if (true==RxCRC&0x01)
	{
		RxCRC=(RxCRC>>1);
		RxCRC=RxCRC^MagicNumber;
	}
	else
		RxCRC=(RxCRC>>1);

Так это понятно программисту любого уровня.

83.167.114.195 18:36, 26 марта 2011 (UTC) Алексей Анучин anuchinas@mpei.ru

И вы называете это хорошим стилем ? (взял на себя смелость поправить wiki-форматирование) Grain 13:49, 1 февраля 2012 (UTC)

Code or Check

Вопрос в канонической расшифровке CRC. Это Cyclic redundancy check или Cyclic redundancy code? В интернете встречаются оба варианта. В английской вики используется check. --4epenOK 19:29, 24 июля 2011 (UTC)

• Расшифровка аббревиатуры вполне может определяться контекстом. Что касается курица или яйцо - то конечно code появился раньше потому как check только одно из применений этого самого code. ASDFS 21:51, 24 июля 2011 (UTC)

Логично. Однако в Гугле по точному запросу Cyclic redundancy code результатов примерно 358 000, а по Cyclic redundancy check примерно 1 470 000. Разница существенная. На мой взгляд нужно употребить наиболее распространённый и узнаваемый вариант.--4epenOK 04:01, 25 июля 2011 (UTC)

• Давайте не будем путать наиболее массовое применение и само явление. Если Вам так хочется - расскажите о вариантах в самой статье. ASDFS 08:09, 25 июля 2011 (UTC)

• Вообще вы правы в том смысле что данная статья рассказывает именно о check, а о code как математическом феномене есть более общая статья Циклический код. Впрочем, я все равно не знаю какое решение здесь нужно: то ли переименовать статью (как именно?), то ли сделать уточнение в шапке о том что статья не о матфеномене а об одном из применений. ASDFS 15:16, 25 июля 2011 (UTC)

Честно говоря я весьма поверхностно понимаю crc да и вообще мат. алгоритмы, поэтому врятли смогу правильно сформулировать (просто в глаза бросилось непривычная расшифровка). Хочу обратить внимание так же на то, что в русской вики (результаты поиска) термин CRC расшифровывается как Cyclic redundancy check в 7 статьях: Magnet-ссылка, Хеш-сумма, SCSI, Обнаружение и исправление ошибок, Линейный код, Список терминов, относящихся к алгоритмам и структурам данных, Список алгоритмов. А термин Cyclic redundancy code в поиске даёт 0 результатов, кроме этой статьи. --4epenOK 21:26, 26 июля 2011 (UTC)

• Согласен что имеет место быть некое достаточно массовое недопонимание вопроса отягощенное отсутствием такого разделения в русском переводе сокращения (есть только код и нет проверка). Надо обкатать эту мысль в голове и написать некое примечание в статье. Если кто то не сделает это раньше меня. ASDFS 11:17, 27 июля 2011 (UTC)

Переделал как смог --4epenOK 10:35, 30 июля 2011 (UTC)

• Сейчас, в статье два противоречия:

• Дан один английский синоним "Cyclic redundancy check", но основным АИ к английскому термину "Philip Koopman, Tridib Chakravarty. Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks" без единого слова "check";
• Во введении Cyclic Redundancy Code или Cyclic Redundancy Check объявлены синонимами, но в самой словарной статье только один английский синоним.

• Наверное надо статью начать с "Циклический избыточный код (англ. Cyclic redundancy code, Cyclic redundancy check, CRC[1][4])..."? Сергей Леонтьев, Крипто-Про (обс.) 00:10, 15 февраля 2021 (UTC)

Варианты CRC-8

1. Откуда взят CRC с полиномом "x8 + x7 + x3 + x2 + 1"? В рекомендации "ITU-T I.432.1 (02/99)" описывается вариант "x8 + x2 + x + 1". В английской версии статьи такой полином отсутствует. В каталоге "Catalogue of parametrised CRC algorithms" (http://regregex.bbcmicro.net/crc-catalogue.htm) полином "0x8D" также отсутствует.

2. Также предлагаю добавить информацию о том, что полином "x8 + x7 + x6 + x4 + x2 + 1" описан в рекомендации "ETSI EN 302 307".

Zaytsev Artem 11:50, 19 сентября 2011 (UTC)

• ВП:Правьте смело, предоставляя ссылки на источники информации. На полином x8 + x7 + x3 + x2 + 1 можете навесить ^{Источник?} --4epenOK 12:05, 19 сентября 2011 (UTC)

• Поправил смело. Полином "x8 + x7 + x3 + x2 + 1" удалил напрочь, т. к. там не просто непроверенная информация, а именно ложная информация: в рекомендации "ITU-T I.432.1 (02/99)" про полином ничего нет (проверял). Единственная информация, которую я нашёл, есть здесь: http://en.wikipedia.org/wiki/User_talk:Ralf.Baechle. Проведя специальное расследование истории болезни изменения статьи, могу предположить, что дело было так: полином "x8 + x7 + x3 + x2 + 1" был скопирован из английской вики, затем там он был удалён, а потом кто-то скопировал оттуда ссылку на "ITU-T I.432.1", но присобачил её не к тому полиному. Если кто-то захочет вернуть этот сомнительный полином, то пусть при этом предоставит верный источник --Zaytsev Artem 13:39, 19 сентября 2011 (UTC)

Рецензия на 10 декабря 2012 года

Здесь находятся завершившиеся обсуждения. Просьба не вносить изменений.

Рецензирование статьи Циклический избыточный код

Мир вам всем, товарищи. Хотелось бы услышать критику, комментарии, замечания и предложения по данной статье. Заранее благодарен за оказанную поддержку. — Эта реплика добавлена участником Mewmewmew (о • в) 16:37, 10 декабря 2012 (UTC)

немного от меня

• смотри ВП:Сноски, особенно со знаками препинания
• заготовка во введении лишняя
• внутренних ссылок здесь нужно побольше
• Математическое описание - нет сносок
• Вычисление CRC - нет сносок
• Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE)... - тоже сноски на стандарты бы не помешали
• Примеры программ для вычисления CRC на языке C

Итоговый массив для табличного (быстрого) расчёта CRC4 (результат работы вышеприведенного кода) --- пусто

Пример программы табличного (быстрого) расчёта CRC8 на языке Си --- только комментарий

Пример программы табличного (быстрого) расчёта CRC-16 CCITT на языке Си --- только комментарий

Пример программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке Си --- только комментарий

• Литература - всего один источник (например статьи по сноскам можно сделать источниками)
• G.704, p. 12 - не лучший вид для примечания
• раздел Категории тоже лишний

---Heimdall--- 01:22, 11 декабря 2012 (UTC)

Спасибо. Действительно, есть над чем поработать. Михаил Алекперов 06:25, 11 декабря 2012 (UTC)

Утеряна часть исходников

В результате последних редактирований статьи утеряна большая часть исходников с табличным рассчётом CRC. Эти исходники наиболее интересны, поскольку именно они используются повсеместно методом копипаст. А вот побитовый рассчёт совсем неинтересен. AterLux 11:13, 11 декабря 2012 (UTC)

• Благодарю за замечание. Восстановлю. Михаил Алекперов 06:07, 12 декабря 2012 (UTC)

Неверные примеры

Как минимум некоторые из приведённых примеров считают неправильно.

В частности, "Пример программы расчёта CRC8 на языке Си".

Нужно либо вектор инициализации заменить с 0xFF на 0xAC (это значение аккумулятора после проведения первых восьми циклов - оно инвариантно вне зависимости от входных данных в силу отсутствия переноса при "вычитании"), либо написать развёрнутый алгоритм. Я считаю, что для наглядности должен даваться именно развёрнутый алгоритм, вики это не место доказывания своей крутизны.

Вот мой развёрнутый (неоптимизированный, но "канонический") вариант, например:

Пример программы расчёта CRC8 на языке Си

unsigned char crc8 (unsigned char *data, unsigned len)
{
    unsigned char crc = 0xff; // вектор инициализации
    unsigned i;

    // Обрабатываем входящие данные по одному биту
    while (len--)
    {
        unsigned char x = *data++;

        for (i = 0; i < 8; i++, x <<= 1)
            if (crc & 0x80)
                crc = ((crc << 1) | (x >> 7)) ^ 0x31;
            else
                crc = ((crc << 1) | (x >> 7));
    }

    // Дополняем входящие данные восемью нулевыми битами
    for (i = 0; i < 8; i++)
    {
        if (crc & 0x80)
            crc = (crc << 1) ^ 0x31;
        else
            crc = (crc << 1);
    }

    return crc;
}

Плюс к этому, перед всеми алгоритмами было бы неплохо разместить словесное описание алгоритма из книги Росс Вильямс (я немного переделал чтобы алгоритм был в общем виде):

Описание алгоритма расчёта CRC

Загрузим в регистр вектор инициализации
Дополним хвостовую часть сообщения W нулевыми битами
ПОКА еще есть необработанные биты
    Сдвинем регистр на 1 бит влево и поместим очередной еще не обработанный бит из сообщения в 0 позицию регистра.
    ЕСЛИ (из регистра был выдвинут бит со значением "1")
        ТО Регистр = Регистр XOR Полином
КОНЕЦ
Теперь в регистре содержится остаток

Контрольный пример: CRC8 ([ 0x55 ]) должен выдавать 0x0A. Zap 11:48, 24 февраля 2013 (UTC)

Многочлен над конечным полем GF(2^N)

Исправил на GF(2), многочлен над конечным полем GF(2^N) означает что коэффициенты из GF(2^N), а у нас коэффициенты из GF(2). В английской википедии верно, а у нас был косяк.

91.201.74.210 04:31, 21 марта 2014 (UTC)

Алексей