Примитивные полиномы
Среди полиномов, которые можно использовать для построения циклического кода длины n, существуют так называемые примитивные полиномы, которые дают число ненулевых синдромов, равное 2r-1. Именно такие полиномы следует использовать для построения кодов, исправляющих ошибки. Такие полиномы степени (r=23) используются, например, в системах мобильной связи и технологиях xDSL (x23+x5+1).
Например: Для построения циклического кода (15, 11) можно использовать образующий полином g1(x)=x4+x+1, который является примитивным и дает 15 ненулевых остатков, то есть этот код можно использовать для исправления одиночных ошибок. Или можно использовать образующий полином g2(x)=x4+x3+x2+x+1, который не является примитивным, дает только 5 ненулевых остатков, и, поэтому, полученный код можно использовать только в режиме обнаружения ошибок.
Признаком примитивных полиномов является наличие остатка равного 1 только для полиномов x0 и xn.
Коды crc
Как уже отмечалось, для построения циклического кода длины n можно использовать полиномы, которые входят в разложение, то есть являются делителями полинома xn+1. При больших значениях n делителей степени r=n-k может быть много. Вопрос: какой из этих делителей порождает наилучший код? – не имеет однозначного ответа. Международный союз электросвязи рекомендует пользоваться таблицей наилучших двоичных циклических кодов, которые стандартизованы для различных систем передачи данных. Эта группа циклических кодов получила название CRC-коды (Cyclic redundancy check – контроль ошибок с помощью циклического избыточного кода).
Эти коды обладают следующими свойствами:
Коды имеют кодовое расстояние dmin=4.
Коды обнаруживают все ошибки веса 3 и менее.
Коды обнаруживают все ошибки нечетного веса.
Коды обнаруживают все пакеты ошибок длины l=r или менее.
Перечисленные свойства позволяют эффективно использовать CRC-код в системах передачи данных с автоматическим запросом повторения, то есть в протоколах ARQ.
Образующие полиномы CRC-кодов - g(x)
|
CRC-4 |
X4+X+1 |
ISDN (PRI, E1) |
|
CRC-8 |
X8+X2+X+1 |
ATM (HEC) |
|
CRC-16 |
X16+X12+X5+1 |
IBM, LAPB, LAPD |
|
CRC-32 |
X32+X26+X23+X22+X16+X12+X11+X10+ X8+X7+X5+X4+X2+X+1 |
Сетевые адаптеры локальных сетей, контроллеры жестких дисков |
Использование crc-кода в технологии атм
(Asynchronous Transfer Mode)
В технологии АТМ данные любой природы передаются пакетами фиксированной длины 53 Байт. Пакеты АТМ получили название ячеек (cell). Из 53-х пять байт составляют заголовок ячейки. Собственно управляющая информация занимает 4 байта, последний байт заголовка называется HEC – Header Error Control, и представляет контрольную последовательность заголовка, полученную при кодировании предыдущих 4-х байт циклическим кодом CRC-8.
|
Общее управление потоком GFC – Generic Flow Control (4 бита) [UNI] или VPI [NNI] |
Идентификатор виртуального пути VPI – Virtual Path Identifier (4 бита) | |
|
VPI (4 бита) |
VCI (4 бита) | |
|
Идентификатор виртуального канала VCI – Virtual Channel Identifier | ||
|
VCI (4 бита) |
Тип полезной нагрузки PTI – Payload Type Identifier (3 бита) |
CLP (1 бит) |
|
Контрольная сумма заголовка HEC – Header Error Control | ||
|
48 Байт – информационное поле | ||
CLP (Cell Loss Priority) – приоритет потери ячеек
Образующий полином g(x)=x8+x2+x+1=(x+1)*(x7+x6+x5+x4+x3+x2+1)
Из стандартного циклического кода с параметрами (127, 120) получен укороченный код (40, 33). Один информационный бит используется для проверки на четность. В результате в стандарте АТМ используется укороченный код (40, 32). Код содержит 232 кодовых слов, скорость кода R=0,8 , кодовое расстояние dmin=4 . Вероятность необнаруженной ошибки составляет величину порядка 10-25 при условии передачи сообщений по дискретному каналу с независимыми ошибками и вероятностью возникновения ошибки в двоичном символе pe=10-8 (что характерно для передачи по оптоволоконным линиям связи).
Pно=Pn(t≥dmin)/2r=P40(t≥4)/28≈C404 (10-8 )4 (1-10-8)36/28≈10-25
Однако это идеализированная ситуация, и в стандарте реализуется алгоритм работы декодера ячеек АТМ для случая работы по дискретному каналу с памятью с двумя состояниями.
Модель передачи ячеек АТМ по каналу с двумя состояниями
Предполагается, что дискретный канал может находиться в двух состояниях – хорошем состоянии и плохом. Этим состояниям соответствуют два режима работы декодера ячеек АТМ.
При получении каждой ячейки вычисляется ее контрольная последовательность и сравнивается с содержимым HEC. Пока ошибки не обнаруживаются (канал находится в хорошем состоянии), декодер остается в режиме исправления одиночных ошибок. При обнаружении ошибок декодер вычисляет число ошибочных бит. При возникновении одиночной ошибки, она исправляется. В случае многократной ошибки ячейка стирается. В любом случае декодер предполагает, что канал перешел в плохое состояние, в котором наиболее вероятно возникновение многократных ошибок (пакетов ошибок), и переходит в режим обнаружения ошибок. В этом режиме все ячейки с обнаруженными ошибками отбрасываются. Попытки исправлять ошибки не предпринимаются. После получения ячейки без ошибок декодер возвращается в режим исправления одиночных ошибок.
При
вероятность отбрасывания ячеек
.