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

'''Циклі́чний надлишко́вий код''' ( {{lang-en|Cyclic redundancy check}}, CRC ) - — алгоритм обчислення [[Контрольна сума|контрольної суми]], призначений для [[Виявлення і виправлення помилок|перевірки цілісності даних]]. CRC є практичним додатком завадостійкого [[кодування]], заснованому на певних математичних властивостях {{Нп5|Циклічний код|циклічного коду|ru|Циклический код}}.

== Завадостійке кодування ==

Перші спроби створення кодів з надлишковою інформацією почалися задовго до появи сучасних ПК. До прикладу, ще в шістдесятих роках минулого століття Рідом і Соломоном була розроблена ефективна методика кодування - — [[Кодкод Ріда-Соломона]]. Використання її у ті часи не представлялося можливим, так як провести операцію [[декодування]] за розумний час першими алгоритмами не вдавалося. Крапку в цьому питанні поставила фундаментальна робота Берлекампа, опублікована в 1968 році. Ця методика, на практичне застосування якої вказав через рік Мессі, і донині використовується в цифрових пристроях, що забезпечують прийом RS-кодованих даних. Більш того: дана система дозволяє не тільки визначати позиції, але й виправляти невірні кодові символи (найчастіше октети).

Але далеко не скрізь від коду потрібна корекція помилок. Сучасні канали зв'язку мають прийнятні характеристики, і часто достатньо лише перевірити, чи успішно пройшла передача або виникли будь-які складності; структура ж помилок і конкретні позиції невірних символів абсолютно не цікавлять приймаючу сторону, яка приймає дані. І в цих умовах дуже вдалим рішенням виявилися алгоритми, що використовують контрольні суми. CRC як найкраще підходить для подібних задач: невисокі витрати ресурсів, простота реалізації і вже сформований математичний апарат з теорії лінійних циклічних кодів забезпечили їй величезну популярність.

== Контрольна сума ==

У найзагальнішому своєму вигляді [[контрольна сума]] являє собою деяке значення, побудоване за певною схемою на основі кодованого повідомлення. Перевірочна інформація при систематичному кодуванні дописується, найчастіше, на кінець повідомлення - — після корисних даних. На приймаючій стороні абонент знає алгоритм обчислення контрольної суми: відповідно, програма має можливість перевірити коректність прийнятих даних.

* [[Хешування]]

* [http://posibnyky.vntu.edu.ua/e_s/index.htm Електронні системи: навчальний посібник / Й.  Й.  Білинський, К.  В.  Огороднік, М.  Й.  Юкиш. – — Вінниця : ВНТУ, 2011. – — 208 с.]