![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Циклическая контрольная сумма.⇐ ПредыдущаяСтр 58 из 58
Помехоустойчивое кодирование предполагает введение в передаваемое сообщение, наряду с информационными, так называемых проверочных разрядов, формируемых в устройствах защиты от ошибок (кодерах на передающем конце, декодерах – на приемном). Избыточность позволяет отличить разрешенную и запрещенную (искаженную за счет ошибок) комбинации при приеме, иначе одна разрешенная комбинация переходила бы в другую.
Помехоустойчивый код характеризуется тройкой чисел (n, k, d0), где n – общее число разрядов в передаваемом сообщении, включая проверочные (г), k=n-r – число информационных разрядов, d0 – минимальное кодовое расстояние между разрешенными кодовыми комбинациями, определяемое как минимальное число различающихся бит в этих комбинациях. Число обнаруживаемых (tо) и (или) исправляемых (tи) ошибок (разрядов) связано с параметром d0 соотношениями:
d0 ≥ tо +1,
d0 ≥ 2tи +1,
d0 ≥ tо + tи+ 1
Иногда используются дополнительные показатели избыточности, производные от приведенных выше характеристик n, k: R = г / n – относительная избыточность, v = k / n – относительная скорость передачи.
Рис. 1.3. Классификация помехоустойчивых кодов Циклические коды (CRC)
Циклические коды – это семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей коды Хэмминга. В целом оно обеспечивает большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправления ошибок, определяемой параметром d0, по сравнению с кодами Хэмминга (для которых d0=3 или d0=4). Широкое использование циклических кодов на практике обусловлено также простотой реализации соответствующих кодеров и декодеров.
Основные свойства и само название циклических кодов связаны с тем, что все разрешенные комбинации бит в передаваемом сообщении (кодовые слова) могут быть получены путем операции циклического сдвига некоторого исходного кодового слова:
(a0a1…an-2an-1);
(an-1a0a1…an-2);
……………………….
Циклические коды задаются с помощью так называемых порождающих полиномов (многочленов) g(x) или их корней. Порождающий полином имеет вид
G(x)=gr xr + gr-1 xr-1 + … + g0
где gi={0, 1}, x=2. Кроме того, вводятся полином исходного cообщения
u(x) = uk-1 xk-1 + uk-2 xk-2 + … +u0
и кодированного сообщения
A(x) = an-1 xn-1 + an-2 xn-2 + … + a0
Для этих полиномов, представляющих собой по существу альтернативную запись чисел в двоичной системе счисления, определяются операции сложения, умножения и деления, необходимые для организации кодирования и декодирования сообщения. Все операции выполняются по модулю 2.
Последовательность кодирования на примере циклического кода (7, 4, 3), имеющего g(x) = x3 + x + 1, следующая:
1) информационная часть сообщения записывается в виде полинома:
u(x) = uk-1 xk-1 + uk-2 xk-2 + … +u0
В рассматриваемом примере k=4 и для сообщения 0111 получается
u(x) = x2 + x + 1
2) u(x) умножается xr, что соответствует циклическому сдвигу исходного сообщения на r разрядов влево:
u(x) x3 = (x2 + x + 1) x3 = x5 + x4 + x3
3) полученный многочлен делится на g(x):
u(x)·xr/q(x) = c(x) ⊕ R(x)/q(x)
где c(x) – полином-частное с максимальной степенью (k—1);
R(x) – полином-остаток с максимальной степенью (r-1);
⊕ – обозначение поразрядной операции суммирования по модулю 2 (исключающее ИЛИ). Кодированное сообщение представляется в виде
A(x)=u(x)xr ⊕ R(x)
Таким образом, в этом случае
A(x) = (x5 + x4 + x3) ⊕ x = x5 + x4 + x3 + x
Передаваемое кодированное сообщение в обычной двоичной форме имеет вид 0111 010 ↔ ↔ k – бит r – бит
|