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

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

Размещено на

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 принятых проверочных элементов и вычисленных по принятым информационным элементам. Вычисление должно проводиться производиться по такому же правилу как на передающей стороне.