2014-02-09
2456
Пример
Пусть для передачи сообщений используется циклический код (7,4) с образующим полиномом g(x)= x3+x2+1. Для передачи используется ДСК без памяти. Декодер работает в режиме исправления одиночных ошибок.
При использовании ДСК без памяти таблица декодирования имеет вид
| Вектор ошибки ei | Синдром Si |
| ………….. | ……. |
В качестве типового вектора ошибки и типового синдрома выбираем e0=0000001 и S0=001.
Предположим, при декодировании получен синдром S'=100=х2. Требуется найти имеющий место вектор ошибки и исправить кодовое слово.
S0(x)=S'(x)*x-i mod g(x), проверяем выполнение равенства, задаваясь различными значениями i.
Если i=1, S1= x2* x-1 mod (x3+x2+1) = x, не совпадает с типовым синдромом S0.
Если i=2, S2=x2*x-2 mod (x3+x2+1) = 1, совпадает с типовым синдромом S0.
Искомый вектор ошибки получается циклической перестановкой типового вектора e0 =0000001 на i=2 разряда влево.
e'=0000100
Решим задачу для случая, если в качестве типового вектора ошибки выбран e0=1000000 и соответствующий ему типовой синдром S0=110:
Если i=1, S1= x2* x-1 mod (x3+x2+1) = x, не совпадает с типовым синдромом S0.
Если i=2, S2=x2*x-2 mod (x3+x2+1) = 1, не совпадает с типовым синдромом S0.
Если i=3, S3=x2* x-3 mod(x3+x2+1)=x7-1mod(x3+x2+1)=x6mod (x3+x2+1)=x2+x, совпадает с типовым синдромом S0.
Искомый вектор ошибки получается циклической перестановкой типового вектора e0 =1000000 на i=3 разряда влево.
e'=0000100
Среди полиномов, которые можно использовать для построения циклического кода длины 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.
Как уже отмечалось, для построения циклического кода длины 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 | Сетевые адаптеры локальных сетей, контроллеры жестких дисков |
