Циклічний надлишковий код: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 41:
=== Опис процедури ===
З файлу береться перше слово — це може бути бітовий (CRC-1), байтовий (CRC-8) або будь-який інший елемент. Якщо старший біт у слові «1», то слово зсувається вліво на один розряд з подальшим виконанням операції [[XOR]] з породжуючим многочленом. Відповідно, якщо старший біт у слові «0», то після [[Бітовий зсув|зсуву]] операція XOR не виконується. Після зсуву втрачається старий старший біт, а молодший біт звільняється — його значення встановлюється рівним нулю. На місце молодшого біту завантажується черговий біт із файлу, й операція повторюється до тих пір, поки не завантажиться останній біт файлу.
== Популярні й стандартизовані многочлени ==
В той час, як циклічні надлишкові коди є частиною стандартів, у цього терміну не існує загальноприйнятого визначення — трактування різних авторів нерідко суперечать один одному.
Цей парадокс стосується й вибору многочлена-генератора: найчастіше [[Стандартизація|стандартизовані]] многочлени не є найбільш ефективними в плані [[Неперервний рівномірний розподіл|статичних]] властивостей відповідного їм ''check redundancy code''.
При цьому багато широко використовуваних многочленів не є найефективнішими із всіх можливих. У 1993—2004 роках група вчених займалася дослідженням породжуючих многочленів розрядності до 16, 24 та 36 біт й знайшла многочлени, які дають кращу, ніж стандартизовані многочлени, продуктивність у сенсі [[Відстань Геммінга|відстані Геммінга]]. Один із результатів цього дослідження вже знайшов своє застосування в протоколі [[iSCSI]].
Найпопулярніший та рекомендований [[IEEE]] многочлен для CRC-32 використовується в [[Ethernet]], [[FDDI]]; також цей многочлен є генератором [[Коди Гемінга|коду Геммінга]]. Використання іншого многочлену — CRC-32C — дозволяє досягти такої ж продуктивності при довжині вихідного повідомлення від 58 біт до 131 кбіт, а в деяких діапазонах довжини вхідного повідомлення може бути навіть більше — цьому в наш час він також користується популярністю. Наприклад, стандарт ITU-T G.hn використовує CRC-32C з ціллю виявлення помилок в [[Корисне навантаження|корисному навантаженні]].
Нижче в таблиці приведені найбільш розповсюджені многочлени — генератори CRC. На практиці обчислення CRC може включати пре- та пост-інверсію, а також зворотний порядок обробки бітів. У власницьких реалізаціях CRC для ускладнення аналізу коду використовують ненульові початкові значення регістрів.
== Див. також ==
| |||