Цикличен излишен код - Компютърни мрежи

Многослойна интернет архитектура

Цикличен код на излишък

Методът за откриване на грешки, широко използван в съвременните компютърни мрежи, се основава на Проверка на цикличната излишък (CRC). Цикличните излишни кодове се наричат ​​още полиномиални кодове, тъй като когато се изчисляват, битов низ се счита за полином (полином), чиито коефициенти са 0 или 1, а операциите върху този битов низ могат да се интерпретират като операции на разделяне и умножение на полиноми.

Цикличните кодове работят както следва. Да разгледаме част от данните D, състояща се от d бита, която изпращащият възел иска да изпрати на приемащия възел. Изпращачът и получателят трябва да се споразумеят за последователност от r + 1 бита, наречена генераторния полином (или генератор), който ще обозначим с G. Най-значимият (най-левият) бит на генераторния полином G трябва да бъде равен на 1. Ключовата идея за цикличните излишни кодове е илюстрирана на фиг. 5.7. За дадено парче данни D изпращачът формира r допълнителни бита R, които добавя към данните D, така че полученият брой, състоящ се от d + r бита, се разделя по модул 2 от генериращия полином (число) G без остатък. По този начин процесът на проверка на данните за грешки е относително ясен. Приемникът разделя получените d + r бита на генериращия полином G. Ако остатъкът от делението не е нула, това означава, че данните са повредени. В противен случай данните се считат за верни и приети.

Всички операции за изчисляване на CRC кода се извършват в аритметичен модул 2, без да се пренасят към съседни цифри. Това означава, че операциите на събиране и изваждане са идентични помежду си и са еквивалентни на битово изключващо ИЛИ, XOR. Например:

---