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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
↓
Пожалуйста, добавляйте новые темы снизу


Я у няни[править код]

Просмотрел анг. вики, и задался логичным вопросом: почему они, "тупые", могут обяснить принцип без формул, а наши "вумные" - в первом же разделе "Алгоритмы" напихали тучу формул где, извините, мне, не математику, ни х#$а не ясно... В который раз на ру.вики убеждаюсь что мат. статьи пишут какие-то задроти которые хотят повипендриватся, а чтоб объяснит что-то, так им не интересно. Я уже на 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 - это деление полиномов, а там сложение есть. -- AVBtalk 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-битный, то мы будем иметь потери и в памяти, и в скорости. Правильная типизация избавляет от оооочень многих проблем. -- AVBtalk 09:55, 10 сентября 2009 (UTC)[ответить]
  • Это int на многих 16-битных и 8-битных системах бывает 16-битным. А long всегда 32 бита. Правильная типизация это хорошо в реальных приложениях, но в примере, имхо, она излишняя, ибо делает код сложнее. Вы переписали код исходя из линуксовых стандартов, но Си используется не только на линуксах.--77.87.200.242 10:05, 10 сентября 2009 (UTC)[ответить]
  • делает код сложнее - она делает код надёжнее и эффективнее. линуксовых стандартов - на это я могу вам только ответить, что вы давно не перечитывали стандарт языка Си. stdint - это стандарт уже больше десяти лет (с C99, а может и раньше, я уже не помню). Просто в Си всё как всегда делается через задницу, но линукс тут как бы непричём. -- AVBtalk 10:12, 10 сентября 2009 (UTC)[ответить]
  • Для примеров не нужна надёжность и эффективность портирования, а нужна предельная простота. Кстати в английской википедии есть целая статья о stdint.h :)--77.87.200.242 10:20, 10 сентября 2009 (UTC)[ответить]
  • предельная простота - в таком случае не используйте реальный язык, особенно вроде C/C++ (в них слишком много заморочек), а используйте псевдокод. Это во-первых. Во-вторых, утверждать, что использование int или long проще, чем uint_least32_t, можно только с большоооооооооооооооооой натяжкой. -- AVBtalk 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 значений. -- AVBtalk 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. -- AVBtalk 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?)? -- AVBtalk 23:54, 10 сентября 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", похоже, основан на табличках оттуда. -- AVBtalk 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)[ответить]

э ... 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 объявлены синонимами, но в самой словарной статье только один английский синоним.

Варианты 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" удалил напрочь, т. к. там не просто непроверенная информация, а именно ложная информация: в рекомендации "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)[ответить]

немного от меня[править код]

Итоговый массив для табличного (быстрого) расчёта 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)[ответить]

Неверные примеры[править код]

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

В частности, "Пример программы расчёта 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)[ответить]

Алексей

Источник — https://ru.wikipedia.org/w/index.php?title=Обсуждение:Циклический_избыточный_код&oldid=112390102