Помехоустойчивое кодирование

1. Методы повышения верности

Чтобы ввести дополнительную избыточность надо увеличить объем сигнала.

;

Р — мощность сигнала; ДF — ширина спектра; Тс — время передачи сигнала.

На практике возможности увеличения избыточности за счет мощности и ширины спектра при передаче по стандартным каналам не используется, поэтому основное развитие получили МПВП, основанные на увеличении длительности передачи Тс.

Эти методы реализуются системами с ОС и без ОС. В системах без ОС для увеличения верности приема используются следующие способы :

1) многократная передача кодовой комбинации (КК);

2) одновременная передача одной КК по нескольким параллельным каналам;

3) помехоустойчивое кодирование (использование кодов исправляющих ошибки).

Иногда используют комбинации этих способов. Самый простой способ — 1). Этот способ используют в низкоскоростных СП. При этом за истинный сигнал принимают тот, который чаще встречается при многократном повторении (мажоритарный принцип). С точки зрения оптимального приема сигналов, повторение — это увеличение времени накопления сигналов. Это приводит к уменьшению скорости передачи. Этому способу аналогичен способ передачи по параллельным каналам. Такой же мажоритарный принцип используется и необходимо нечетное число каналов (не < 3). Но не эффективно используется полоса.

Наиболее эффективное применение 3). При этом в КК из кинформационных разрядов вводятся r избыточных (k+r=n). Эти избыточные разряды формируются по заранее известным правилам. Структура кода и его исправляющие возможности рассчитываются для некоторого идеализированного канала с некоторой вероятностью ошибки. Свойства любого реального канала не постоянны и могут резко отличаться от выбранной модели. Могут быть системы, когда нет ошибок, но продолжается передача. И наоборот, когда канал может быть в таком состоянии, что данной избирательности недостаточно. Статистика ошибок плохо поддается формализации. Поэтому правильный выбор кода — трудная задача. В таких случаях увеличивают верность без уменьшения пропускной способности можно введением переменной избыточности. Такие системы — адаптивны, приспосабливают к свойствам канала. Для их построения нужно на приемной стороне оценивать статистику ошибок. Нужен обратный канал. поэтому переменная избыточность реализуется в системах с ОС. Эти системы делятся на 3 группы:

1) система с решающей ОС — РОС;

2) система с информационной ОС — ИОС;

3) комбинирование системы — КОС.

Характерной особенностью систем является повторение КК в случае обнаружения ошибки. В системах РОС передаваемое сообщение кодов исправляющей ошибки. На приемной стороне ошибка обнаруживается и в кодовой комбинации повторяется.

Устойчивое кодирование не применяется. Приемники по обратному каналу либо дублируют, либо передаются специальные сигналы, имеющие большой объем, но обеспечивающий необходимое качество. Эти сведения называются квитанции.

Сравнивая РОС и ИОС видим, что в ИОС не требуется спецкодирование. ИОС реализуются проще. КОС представляет собой сочетание 2-х упомянутых. В таких системах решение о выдаче информации абоненту или по информации принимается или в приемнике или в передатчике, а ОС используется как для передачи принятия решений или квитанций.

2. Основные определения и понятия теории кодирования

Код — это набор кодовых последовательностей (кодограмм). Кодограмма — последовательность символов.

Основание кода — число различных символов m, используемых для построения кодограмм (в двоичных m=2).

Значность кода n — число символов, образующих кодограмму. При заданных m и n общее число возможных кодограмм. Если значимость всех кодограмм кода одинаково такой код равномерный, в противном случае — неравномерный.

Порядковый номер — называется разрядом. При этом первый символ кода — старший. Но это условно. Количество символов, в котором одна кодовая комбинация равномерного кода отличается от другой, при по парном поразрядном сравнении называется кодовым расстоянием или Хемминговым расстоянием. Попарное поразрядное сравнение осуществляется сложением по модулю 2. Затем подсчитывается число единиц.

3. Принципы помехоустойчивого кодирования

В обычном равномерном помехоустойчивом коде число разрядов КК определяется числом сообщений и основанием кода. При этом любая из этих 5 элементарных комбинаций представляет знак алфавита. Любая ошибка интерпретируется как другая буква. Все 32 КК называются разрешенными и ошибка переводит из одной разрешенной КК в другую. При передачи речи и текста ошибку может обнаружить получатель за счет избирательности. В ТГ общего пользования избыточность не используется. Он является оптимальным ДК-ром.

Коды, у которых все КК разрешены называются простыми или равнодоступными. Т.к. цифровая информация этим свойством не обладает, то необходима избыточность по определенным правилам. Правила должны быть известны и на приемной стороне и на передающей.

Введение

избыточности достигается тем, что для передачи информации используется большая значность, чем требуется. Требуется код значности k, то нужно — возможных кодограмм. Для увеличения помехоустойчивости используется код большей значности n=k+r следовательно,; n>k и N>K .

Выбранные k кодовые комбинации — разрешенные, а остальные (n-k) — запрещенные, которые никогда не могут быть переданы. Это свойство используется на приемной стороне. Если принятая КК совпадает с запрещенной , — ошибка.

Если совокупность ошибок. Если совокупность ошибок переводит из разрешенных в разрешенные, то ошибка не обнаруживается, т. е. каждый код имеет обнаруживающую способность.

Избыточность кода:

Чтобы ошибки были обнаружены, необходимо чтобы кодовые расстояния, где — кратность ошибки. Всего K разрешенных КК. Любая из них может превратиться в N возможных. Общее число случаев — KN.

Число случаев, когда ошибки обнаруживаются равно K (N-K). Тогда доля обнаруженных ошибочных комбинаций:

Аналогичные рассуждения проводятся и для кода, исправляющего ошибки. При этом для исправления кода можно построить граф:

Способ приема должен быть таким, что если принята КК принадлежащая множеству, то считаем, что передан символ. При этом можем правильно принять или ошибиться. Ошибка всегда исправляется в N-K случаях, а общее число переходов равно K (N-K). Тогда отношение числа исправленных к числу обнаруженных:

Способность кода исправлять ошибки зависит от способа приема. Общее правило: для исправления ошибок кодовое расстояние должно быть: .

Правило выбора разрешенных КК из общего числа возможных и определяет обнаруживающую и исправляющую способность кода.

4. Классификация помехоустойчивых кодов

Помехоустойчивые блоки делятся на блочные и не блочные. Непрерывные (сверточные или рекуррентные) — это непрерывная последовательность единичных элементов, не разделенных на блоки. В таких кодах избыточные разряды размещаются в определенном порядке между.

К блочным относят коды, в которых каждому элементу сообщения относят блок из одинакового числа символов и различного числа (равномерные и неравномерные). Наиболее широкое применение нашли равномерные коды. Равномерные блочные коды делятся на разделимые и неразделимые. В разделимых — элементы проверочных частей всегда стоят в определенных местах. В неразделенных — проверочные и информационные разряды отсутствуют. Разделенные делятся на систематические (линейные) и несистемные (нелинейные). Код называется линейным, если любая разрешенная кодовая комбинация может быть получена в результате линейной операции над набором из k ненулевых линейно независимых КК. В систематических кодах проверочные элементы формируются линейным преобразованием элементов. Эти коды в системе передачи дискретной информации получили наибольшее распространение. Нелинейные коды этим свойством не обладают и применяются реже. Различают 2 метода формирования проверочных разрядов:

— поэлементно;

— в целом.

Элементный — для каждого проверочного разряда существует свое правило:

1), i=1…k.

2)

формирует всю группу.

Второе правило используется в полиномиальных кодах (разновидность — циклические коды). Среди системных кодов нашли распространение циклические или коды Хемминга.

Код Хемминга обеспечивает, т. е. может исправлять одну ошибку.

5. Код Хемминга (КХ)

КХ — это линейные систематические коды с или. У этих кодов проверочные разряды формируются по первому правилу .

Обнаружение и исправление ошибок кодом Хемминга сводится к определению и последующему анализу синдрома. Под синдромом понимают совокупность элементов, сформулированных суммированием по модулю 2 принятых проверочных элементов и вычисленных по принятым информационным элементам. Вычисление должно проводиться производиться по такому же правилу как на передающей стороне.

— передача;

— прием.

Если синдром равен 0 (000.0), то ошибки нет. Если где-то появится ошибка, то в составе синдрома появятся единицы. Очевидно, если ошибка произошла в проверочном разряде, то в синдроме будет одна ошибка. Ошибки в информационном разряде приводят к большому числу единиц. По синдрому можно указать №, где произошла ошибка. Двоичное число синдром представляет собой при переводе в 10-ую систему номер разряда, где произошла ошибка. Построение кода сводится к выбору или установлению такого оператора, который сопоставляет двоичное число синдром с элементом КК, где ошибка.

Рассмотрим правила построения кода:

(9,5)

0 0 0 0 — ошибки нет;

0 0 0 1 — ошибка в ;

0 0 1 0 — ошибка в ;

0 1 0 0 — ошибка в ;

1 0 0 0 — ошибка в .

Составим правила для остальных разрядов. Появление большого числа единиц соответствует появлению ошибки в информационной части.

В этом правиле можно делать только 1 линейное преобразование суммирование по модулю 2. Построим алгоритм так, чтобы он включал в себя те информационные элементы, ошибка в которых приводит к появлению 1-цы в соответствующем разряде синдрома:

;

Эти соотношения можно отобразить в виде проверочной матрицы (в ней строк столько, сколько проверочных разрядов)

Кодирующее устройство для такого кода может быть реализовано в виде регистра сдвига с ОС.

В исходном состоянии все ячейки регистра сдвига находятся в состоянии 0. Затем в триггеры с 1 по 5 записывается информационная часть. После этого в сумматоре формируются остатки и записываются в оставшиеся ячейки памяти. Затем появляются импульсы продвижения.

6. Циклические коды

ЦК — относятся к классу нелинейных системных кодов. Удобно рассматривать КК ЦК не в виде последовательности 0 и 1, а в виде полинома некоторой степени.

.

х — основание системы счисления;

— цифры данной системы счисления.

.

Представление КК ввиде таких многочленов позволяет установить однозначное соответствие между ними. При этом действия над КК сводятся к действиям над многочленами. Сложение двоичных многочленов осуществляется по модулю 2 коэффициентов при равных степенях переменной Х.

Умножение — по обычному правилу умножения степенных функций. Но когда осуществляется приведение подобных членов коэффициенты складываются по модулю 2. Деление как обычные многочлены. Вычисление — по модулю 2. Циклический сдвиг исходной КК порождает разрешенные КК.

.

Теория построения ЦК базируется на разделах высшей алгебры, которая изучает свойства многочленов. Особую роль играют неприводимые многочлены, т. е. полиномы, которые не могут быть представлены ввиде произведения многочленов низких степеней. Такой многочлен делится без остатка на 1 и на себя. На неприводимый многочлен делится без остатка .

Такие неприводимые многочлены играют особую роль, на их основе строятся — образующий многочлен. Идея построения ЦК сводится к тому, что полином, представляющий информационную часть кода, нужно превратить в полином n-1 степени. Степень образующего многочлена g (x) соответствует числу разрядов проверочных комбинаций. В ЦК проверочная часть получается сразу, т. е. используется 2 правило.

Все разрешенные КК ЦК представленные ввиде полиномов обладают одним признаком. Они делятся без остатка на образующий полином. Построение разрешенной КК сводится к следующему:

1) информационную часть КК представляют ввиде полинома ;

2) осуществляют сдвиг ;

3) делим сдвинутый многочлен на образующий

и результат этого деления представляет, где R (x) — остаток от деления; C (x) — имеет такую же степень, что и g (x). Это из информационных КК. Если умножить обе части на g (x):

.

Прибавим к обеим частям R (x):

.

Очевидно, что получившийся многочлен делится на g (x) без остатка. То это разрешенная КК.

7. Обнаружение ошибок

Обнаружение ошибок при ЦК сводится к делению принятой КК на образующий полином, который используется при кодировании. Если ошибок в принятой КК нет, то деление без остатка. Наличие не нулевого остатка свидетельствует об ошибке. Этот остаток играет роль синдрома. Номер разряда с ошибкой однозначно связан с видом синдрома. По виду синдрома можно определить место ошибки. Но для этого нужно условие, при котором количество ненулевых остатков равно количеству элементов N (при одной ошибке) или числу комбинаций из n по (). Количество различных ненулевых остатков для заданного кода. Необходимо, чтобы это число было больше величины:

следовательно можно найти требуемое число проверочных символов.

8. Выбор образующих многочленов.

Однако не каждый неприводимый многочлен может быть использован в качестве образующего. Удобным является выбор образующего многочлена основанный на свойстве циклического сдвига. Из этого свойства следует, что :

делится без остатка.

H (x) — проверочный многочлен.

Заключение

Необходимость использования методов повышения вероятности передачи (МПВП).

В реальных условиях прием двоичных символов всегда происходит с ошибками. Ошибки возникают из-за следующих причин :

1. Помех (особенно импульсного характера

2. Из-за изменений характеристик канала за время передачи — снижение уровня передачи или нестабильность АЧХ и ФЧХ

3. Кратковременные перерывы

4. Ремонтно-профилактические работы.

Часть этих причин носит эксплуатационный характер, могут быть устранены увеличением качественных показателей аппаратуры, особенностью коммутации, повышение квалификации рабочего персонала.

Улучшение качества КС на линиях большой протяженности способствует включению фазовых корректоров, регенеративные ретрансляторы и т. д. Но даже при этих мерах вероятность ошибки на единичный элемент будет не лучше, чем. Появление ошибок носит случайный характер и является следствием воздействия совокупности мешающих факторов. Обязательно на линии связи исследуют свойства потока ошибок. Математическим аппаратом является теория случайных процессов.

Строение модели сложно, т.к. реальные потоки ошибок нестационарны. Поэтому чисто аппаратные способы повышения верности передачи не позволяют достигнуть нужных характеристик. Поэтому основной мерой является применение специальных методов.

Такие методы можно разбить на две группы :

1. Методы увеличения помехоустойчивости единичных элементов, связанные с выбором уровня сигнала, обеспечивающие определенное отношение С/помеха, выбором ширины полосы канала и т. д.

2. Методы обнаружения и исправления ошибок, основанные на искусственном

избыточность кодирование помехоустойчивый циклический

1. С. И. Баскаков: «Радиотехнические цепи и сигналы» — М.: Высшая школа, 2005.

2. Зюко А. Г., Кловский Д. Д., Коржик В. И., Назаров М. В., под ред. Кловского Д. Д. Теория электрической связи, — М.: Радио и связь, 1999 г.

3. В. И. Каганов: «Радиотехнические цепи и сигналы» — М.: Горячая линия — Телеком, 2004.

4. Нефедов В. И. Основы радиоэлектроники и связи, — М.: Высшая школа, 2005 г.