Циклічний надлишковий код - Комп’ютерні мережі
Багаторівнева архітектура Інтернету
Циклічний надлишковий код
Метод виявлення помилок, що широко застосовується в сучасних комп'ютерних мережах, заснований на контролі за допомогою циклічного надлишкового коду (Cyclic Redundancy Check, CRC). Циклічні надлишкові коди також називають поліноміальними кодами, так як при їх обчисленні бітовий рядок розглядається як багаточлен (поліном), коефіцієнти якого дорівнюють 0 або 1, і операції з цим бітовим рядком можна інтерпретувати як операції поділу та множення багаточленів.
Циклічні коди працюють в такий спосіб. Розглянемо фрагмент даних Д, що складається з d розрядів, які передавальний вузол хоче відправити приймаючому вузлу. Відправник і одержувач повинні домовитися про послідовність з r+ 1 біт, яка називається утворюючим багаточленом (або генератором), який ми позначатимемо G. Старший (найлівіший) біт утворюючого багаточлена G повинен дорівнювати 1. Ключову ідею циклічних надлишкових кодів ілюструє рис. 5.7. Для заданого фрагмента даних D відправник формує г додаткових розрядів R, які він додає до даних Д так що що отримується в результаті число, що складається з d + г біт, ділиться по модулю 2 утворює багаточлен (число) G без залишку. Отже, процес перевірки даних наявність помилки щодо простий. Одержувач ділить отримані d + г біт на утворює многочлен G. Якщо залишок від розподілу не дорівнює нулю, це означає, що дані пошкоджені. В іншому випадку дані вважаються вірними та приймаються.
Усі операції з обчислення CRC-коду виробляються в арифметиці за модулем 2 без переносів сусідні розряди. Це означає, що операції складання та віднімання ідентичні один одному та еквівалентні порозрядній операціїщо виключає АБО (exclusive OR, XOR). Наприклад: 1011 XOR 0101 = 1110 1001 XOR 1101 = 0100 Також ми отримаємо: 1011-0101 = 1110 1001-1101 = 0100
Перетворення множення і поділу аналогічні відповідним операціям у звичайній двійковій арифметиці з тією різницею, що будь-яка операція складання або віднімання, яка при цьому при цьому потрібна, виконується без переносів у сусідній розряд. Як і звичайній арифметиці, множення на 2(k) означає зсув числа на k розрядів вліво. Таким чином, при заданих значеннях D і R величина D 2(k) XOR R відповідає послідовності d+r біт, показаної на рис. 5.7. У нашому подальшому обговоренні ми будемо використовувати саме цю форму алгебри для позначення послідовності з d + r біт. Повернемося тепер до головного питання: як відправник обчислює R? Згадаймо, що нам потрібно знайти таке значення R, щоб для деякого п виконувалася така рівність: D 2(r) XOR R = nG.
Тобто потрібно вибрати таке значення R, щоб D 2(k) XOR R ділилося на G без залишку. Якщо додати до кожної частини рівняння значення R по модулю 2, ми отримаємо D•2(r) = nG XOR R.
Звідси випливає, що якщо ми розділимо D • 2(r) на G, то залишок буде дорівнює R. Таким чином, ми можемо обчислити R як
На рис. 5.8 показаний приклад обчислення R для D = 101110, d = 6, G = 1001 та r = 3. У цьому випадку відправник передає наступні 9 біт: 1011100І. Ви можете перевірити правильність розрахунків, а також переконатися, що D•2(r)-101011•2(r)=G XOR R.
Для 8-, 12-, 16- і 32-розрядних багаточленів, що утворюють, визначені міжнародні стандарти. Восьмирозрядний CRC-код використовується для захисту 5-байтового заголовка ATM-осередків. У 32-розрядному стандарті CRC-32, прийнятому в ряді IEEE-протоколів канального рівня,використовується утворює багаточлен виду
Кожен стандарт CRC-коду здатний виявляти помилкові пакети довжиною трохи більше г розрядів. Крім того, при відповідних припущеннях помилковий пакет довжиною більш ніж г розрядів буде знайдено з ймовірністю 1 - 0,5Г. Крім цього, кожен стандарт CRC-коду може виявляти помилки непарної кратності.
Мій блог знаходять за такими фразами
Відповідальність за всі зміни, внесені в систему за порадами цієї статті, Ви берете на себе.