Вікіпедія

Циклічний надлишковий код: відмінності між версіями

Інтерактивний перегляд історії
[перевірена версія][перевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Немає опису редагування
Рядок 2:
 
== Введення ==
Поняття [[Циклічний код|циклічні коди]] достатньо широке. У англомовній літературі CRC розшифровується двояко в залежності від контексту: ''Cyclic Redundancy Code''  або ''Cyclic Redundancy Check.'' Під першою розшифровкою розуміють математичний феномен циклічних кодів, під другою  — конкретне застосування цього феномену як [[Геш-функція|геш-функції]].
 
== Завадостійке кодування ==
Рядок 17:
 
== Математичний опис ==
Алгоритм CRC базується на властивості [[ділення з остачею]] двійкових [[Многочлен|многочленів]], тобто многочленів над [[Скінченне поле|скінченним полем]] <math>GF(2)</math>. Значення CRC є по суті остачею від ділення многочлена, відповідного вхідним даним, на деякий фіксований породжувальний многочлен.
 
Кожній послідовності бітів <math>a_0, a_1, ..., a_{N-1}</math> взаємно однозначно зіставляється двійковий многочлен <math>\textstyle \sum_{n=0}^{N-1} \displaystyle a_nx^n</math>, послідовність коефіцієнтів якого являє собою початкову послідовність. Наприклад, послідовність бітів 1011010 відповідає многочлену:<blockquote><math>P(x) = 1\cdot x^6 + 0\cdot x^5 + 1\cdot x^4 + 1\cdot x^3 + 0\cdot x^2 + 1\cdot x^1 + 0\cdot x^0 =
x^6 + x^4 + x^3 + x^1.</math></blockquote>Кількість різних многочленів степені меншої <math>N</math> дорівнює <math>2^N</math>, що збігається з числом всіх двійкових послідовностей довжини <math>N</math>.
 
Значення контрольної суми в алгоритмі з породжуючим многочленом <math>G(x)</math> степені <math>N</math> задається як бітова послідовність довжини <math>N</math>, яка представляє многочлен <math>R(x)</math>, отриманий в остачі при діленні многочлена <math>P(x)</math>, який представляє вхідний потік біт, на многочлен <math>G(x)</math>:<blockquote><math>R(x) = P(x)\cdot x^N\bmod\ G(x) </math></blockquote>де
: <math>R(x)</math> &nbsp;— многочлен, який представляє значення CRC;
: <math>P(x)</math>— многочлен, коефіцієнти якого представляють вхідні дані;
: <math>G(x)</math> &nbsp;— породжувальний многочлен;
: <math>N</math> &nbsp;— степінь породжувального многочлена.
Множення <math>x^N</math> здійснюється приписуванням нульових бітів до вхідної послідовності, що покращує якість гешування для коротких вхідних послідовностей.
 
Рядок 36:
Одним з основних параметрів CRC є породжувальний многочлен.
 
З породжувальним многочленом пов'язаний інший параметр &nbsp;— його [[Степінь многочлена|степінь]], який визначає кількість бітів, застосованих для обчислення значення CRC. На практиці найбільш поширені 8-, 16- та 32-бітові слова, що є наслідком особливостей архітектури сучасної обчислювальної техніки.
 
Ще одним параметром є початкове (стартове) значення слова. Вказані параметри повністю визначають «традиційний» алгоритм обчислення CRC. Існують також модифікації алгоритму, наприклад, які використовують [[Порядок байтів|зворотний порядок]] обробки бітів.
 
=== Опис процедури ===
З файлу береться перше слово &nbsp;— це може бути бітовий (CRC-1), байтовий (CRC-8) або будь-який інший елемент. Якщо старший біт у слові «1», то слово зсувається вліво на один розряд з подальшим виконанням операції [[XOR]] з породжувальним многочленом. Відповідно, якщо старший біт у слові «0», то після [[Бітовий зсув|зсуву]] операція XOR не виконується. Після зсуву втрачається старий старший біт, а молодший біт звільняється &nbsp;— його значення встановлюється рівним нулю. На місце молодшого біту завантажується черговий біт із файлу, й операція повторюється до тих пір, поки не завантажиться останній біт файлу. Після проходження всього файлу, в слові залишається остача, яка і є контрольною сумою.
 
== Популярні й стандартизовані многочлени ==
В той час, як циклічні надлишкові коди є частиною стандартів, у цього терміну не існує загальноприйнятого визначення &nbsp;— трактування різних авторів нерідко суперечать один одному.
 
Цей парадокс стосується й вибору многочлена-генератора: найчастіше [[Стандартизація|стандартизовані]] многочлени не є найбільш ефективними в плані [[Неперервний рівномірний розподіл|статичних]] властивостей відповідного їм ''check redundancy code''.
 
При цьому багато широко використовуваних многочленів не є найефективнішими із всіх можливих. У 1993—2004 роках група вчених займалася дослідженням породжувальних многочленів розрядності до 16, 24 та 36 біт й знайшла многочлени, які дають кращу, ніж стандартизовані многочлени, продуктивність у сенсі [[Відстань Геммінга|кодової відстані]]. Один із результатів цього дослідження вже знайшов своє застосування в протоколі [[iSCSI]].
 
Найпопулярніший та рекомендований [[IEEE]] многочлен для CRC-32 використовується в [[Ethernet]], [[FDDI]]; також цей многочлен є генератором [[Коди Гемінга|коду Геммінга]]. Використання іншого многочлену &nbsp;— CRC-32C &nbsp;— дозволяє досягти такої ж продуктивності при довжині вихідного повідомлення від 58 біт до 131 кбіт, а в деяких діапазонах довжини вхідного повідомлення може бути навіть більше &nbsp;— тому в наш час він також користується популярністю. Наприклад, [https://www.itu.int/dms_pub/itu-t/opb/tut/T-TUT-HOME-2010-PDF-E.pdf стандарт ITU-T G.hn]<ref>{{Cite book|title=ITU-T|last=|first=|year=2010|publisher=|location=|pages=|language=en|isbn=}}</ref> використовує CRC-32C з ціллю виявлення помилок в [[Корисне навантаження|корисному навантаженні]].
 
Нижче в таблиці приведені найбільш розповсюджені многочлени &nbsp;— генератори CRC. На практиці обчислення CRC може включати пре- та пост-інверсію, а також зворотний порядок обробки бітів. У власницьких реалізаціях CRC для ускладнення аналізу коду використовують ненульові початкові значення регістрів.
{| class="wikitable"
! rowspan="2" |Назва
Рядок 61:
!Нормальне
!Реверсоване
!Реверсоване
від зворотнього
|-
|CRC-1
|<math>x + 1</math>
|використовується в апаратному контролі помилок;
також відомий як [[біт парності]]
|0x1
Рядок 102:
|-
|CRC-6-ITU
|<math>x^6 + x + 1</math>
|[[ITU]] G.704<ref>{{Cite web|url=http://www.itu.int/rec/T-REC-G.704-199810-I/en|title=G.704 : Synchronous frame structures used at 1544, 6312, 2048, 8448 and 44 736 kbit/s hierarchical levels p.3|last=tsbmail|first=|date=|website=www.itu.int|publisher=|language=|accessdate=}}</ref>
|0x03
Рядок 109:
|-
|CRC-7
|<math>x^7 + x^3 + 1</math>
|системи телекомунікації, [[ITU]]-T G.707<ref>{{Cite web|url=http://www.itu.int/rec/T-REC-G.707/en|title=G.707 : Network node interface for the synchronous digital hierarchy (SDH) P. 7|last=tsbmail|first=|date=|website=www.itu.int|publisher=|language=|accessdate=}}</ref>, [[ITU]]-T G.832<ref>{{Cite web|url=http://www.itu.int/rec/T-REC-G.832/en|title=G.832 : Transport of SDH elements on PDH networks - Frame and multiplexing structures|last=tsbmail|first=|date=|website=www.itu.int|publisher=|language=|accessdate=}}</ref>, [[MultiMediaCard|MMC]], [[Secure Digital|SD]]
|0x09
Рядок 174:
|CRC-16-[[IBM]]
|<math>x^{16} + x^{15} + x^2 + 1</math>
|Bisync, [[Modbus]], [[USB]], [[ANSI]] X3.28<sup>[20]</sup>, багато інших;
також відомий як ''CRC-16'' та ''CRC-16-ANSI''
|0x8005
Рядок 182:
|CRC-16-CCITT
|<math>x^{16} + x^{12} + x^5 + 1</math>
|[[X.25]], [[HDLC]],  XMODEM, [[Bluetooth]], [[Secure Digital|SD]] та інші
|0x1021
|0x8408
Рядок 188:
|-
|CRC-16-T10-DIF
|<math>x^{16} + x^{15} + x^{11} + x^9 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1</math>
|[[SCSI]] DIF
|0x8BB7
Рядок 239:
 
<math>x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + 1 </math>
|[[iSCSI]],  G.hn payload
|0x1EDC6F41
|0x82F63B78
Рядок 262:
|CRC-64-ISO
|<math>x^{64} + x^4 + x^3 + x + 1 </math>
|HDLC &nbsp;— ISO 3309
|0x000000000000001B
|0xD800000000000000
Рядок 286:
* Ступінь породжує контрольну суму многочлена (width);
 
* Сам виготовляючий поліном (poly). Для того, щоб записати його у вигляді значення, його спочатку записують як бітову послідовність, при цьому старший біт опускається -&nbsp;— він завжди дорівнює 1. Наприклад, многочлен в даній нотації буде записаний числом. Для зручності отримане двійкове подання записують в шістнадцятковій формі. Для нашого випадку воно буде дорівнює або 0x11;
 
* Стартові дані (init), тобто значення регістрів на момент початку обчислень;
 
* Прапор (RefIn), який вказує на початок і напрямок обчислень. Існує два варіанти: False -&nbsp;— починаючи зі старшого значущого [http://arduino.ua/ru/prog/ShiftOut біта (MSB-first),]<ref>{{Cite web|url=http://arduino.ua/ru/prog/ShiftOut|title=ShiftOut Программирование Ардуино|last=|first=|date=|website=arduino.ua|publisher=|language=|accessdate=}}</ref> або True -&nbsp;— з молодшого [http://arduino.ua/ru/prog/ShiftOut (LSB-first);]<ref>{{Cite web|url=http://arduino.ua/ru/prog/ShiftOut|title=ShiftOut Программирование Ардуино|last=|first=|date=|website=arduino.ua|publisher=|language=|accessdate=}}</ref>
 
* Прапор (RefOut), що визначає, інвертується чи порядок бітів регістра при вході на елемент XOR;
Рядок 1030:
* [http://posibnyky.vntu.edu.ua/e_s/index.htm Електронні системи: навчальний посібник / Й.&nbsp;Й.&nbsp;Білинський, К.&nbsp;В.&nbsp;Огороднік, М.&nbsp;Й.&nbsp;Юкиш.&nbsp;— Вінниця: ВНТУ, 2011.&nbsp;— 208 с.]
 
{{Хеш-функції навігація}}
{{програмування-доробити}}
 
Отримано з https://uk.wikipedia.org/wiki/Циклічний_надлишковий_код