Лекция №11. Оптимальное и помехоустойчивое кодирование Отимальное кодирование icon

Лекция №11. Оптимальное и помехоустойчивое кодирование Отимальное кодирование



Смотрите также:
Лекция 4
Задачи на кодирование звуковой информации 5 Решение задач на кодирование звуковой информации 6...
Презентация по теме: «Кодирование и шифрование информации»...
Курсовая работа (проект) часов...
Kibernētika
Курсовая работа по теме: «Программа для разархивации файла, созданного по алгоритму rle»...
Кодирование графической и звуковой информации Двоичное кодирование графической информации...
Правила кодирования. Классификаторы Товароведение как наука и учебная...
Кодирование алгоритмических структур основных типов на языке программирования Visual Basic...
Лекция 13
Тема : Кодирование текстовой информации. Кодировка ascii. Основные кодировки кириллицы...
Реферат по дисциплине "Информатика"...



скачать
Лекция №11. Оптимальное и помехоустойчивое кодирование

Отимальное кодирование.

Возможно ли так закодировать сообщение, чтобы скорость передачи достигала своего максимального значения, равного пропускной способности двоичного канала

Одним из кодов, удовлетворяющих указанному условию, является код Шеннона-Фано. Для ознакомления с принципами его построения рассмотрим в качестве примера источник сообщений, вырабатывающий четыре сообщения с вероятностями: P(a1),P(a2),P(a3),P(a4).

Все сообщения выписываются в кодовую таблицу (табл. 11.1) в порядке убывания их вероятностей. Затем они разделяются на две группы так, чтобы суммы их вероятностей по возможности были одинаковыми. В данном примере в первую группу входит сообщение а1 с вероятностью 0,5 и во вторую сообщения с суммарной вероятностью, также равной 0,5.

Таблица 11.1



Комбинациям, которые соответствуют сообщениям первой группы, присваивается в качестве первого символа кода — 0, а комбинациям второй группы — 1. Каждая из двух групп опять делится на две группы с применением того же правила присвоения символов 0 и 1. В идеальном случае после первого деления вероятности каждой группы должны быть равны 0,5, после второго деления — 0,25 и т. д. Процесс деления продолжается до тех пор, пока в группах не останется по одному сообщению.

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

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

Важным свойством кода Шеннона-Фано является то, что, несмотря на его неравномерность, здесь не требуются разделительные знаки. Это обусловлено тем, что короткие комбинации не являются началом более длинных. Код является префиксным.

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

Указанное свойство легко проверить на примере любой последовательности:



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

(11.1)

Для сравнения рассмотрим кодирование тех же четырех сообщений с применением обычного равномерного двоичного кода. Количество комбинаций при этом определяется выражением , где - число элементов в комбинации. Так как, то а длительность каждой комбинации —. Производя вычисления по аналогии с (11.1), получим:



Пропускная способность в этом случае используется только частично.

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

Одним из способов оптимального кодирования зависимых сообщений является применение так называемых "скользящих" кодов, основная идея которых состоит в том, что присвоение кодовых комбинаций по правилу Шеннона-Фано производится с учетом условных, а не априорных вероятностей сообщений. Число элементов в кодовой комбинации выбирается как т.е. текущему сообщению присваивается та или иная комбинация в зависимости от того, какие сообщения ему предшествовали.

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

^ Принцип построения оптимальных кодов:

1.   Каждый элементарный символ должен переносить максимальное количество информации, для этого необходимо, чтобы элементарные символы (0 и 1) в закодированном тексте встречались в среднем одинаково часто. Энтропия в этом случае будет максимальной.

2.   Необходимо буквам первичного алфавита, имеющим большую вероятность, присваивать более короткие кодовые слова вторичного алфавита.

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

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

Для того чтобы код обладал корректирующими способностями, в кодовой последовательности должны содержаться дополнительные (избыточные) символы, предназначенные для корректирования ошибок. Чем больше избыточность кода, тем выше его корректирующая способность.

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

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

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

Разновидностями как блочных, так и непрерывных кодов являются разделимые и неразделимые коды. В разделимых кодах всегда можно выделить информационные символы, содержащие передаваемую информацию, и контрольные (проверочные) символы, которые являются избыточными и служат исключительно для коррекции ошибок. В неразделимых кодах такое разделение провести невозможно.

Наиболее многочисленный класс разделимых кодов составляют линейные коды. Основная их особенность состоит в том, что контрольные символы образуются как линейные комбинации информационных символов.

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


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

В теории помехоустойчивого кодирования важным является вопрос об использовании избыточности для корректирования возникающих при передаче ошибок. Здесь удобно рассмотреть блочные коды, в которых всегда имеется возможность выделить отдельные кодовые комбинации. Для равномерных кодов, число возможных комбинаций равно М=2n, где п — значность кода.

В обычном некорректирующем коде без избыточности, например, в коде Бодо, число комбинаций ^ М выбирается равным числу сообщений алфавита источника М0, и все комбинации используются для передачи информации. Корректирующие коды строятся так, чтобы число комбинаций М превышало число комбинаций источника М0. Однако в этом случае лишь М0 комбинаций из общего числа используются для пе­редачи информации. Эти комбинации называются разрешенными, а остальные М М0 комбинации носят название запрещенных. На приемном конце в декодирующем устройстве известно, какие комбинации являются разрешенными и какие — запрещенными. Поэтому если переданная разрешенная комбинация в результате ошибки преобразуется в некоторую запрещенную комбинацию, то такая ошибка будет обнаружена, а при определенных условиях — исправлена. Ес­тественно, что ошибки, приводящие к образованию другой разрешенной комбинации, не обнаруживаются.

Различие между комбинациями равномерного кода принято характеризовать расстоянием, равным числу символов, которыми отличаются комбинации одна от другой. Расстояние dij между двумя комбинациями Ai и Aj определяется количеством единиц в сумме этих комбинаций по модулю два. Например:



Для любого кода . Минимальное различие между разрешенными комбинациями в данном коде называется кодовым расстоянием



Рис. 11.1. Геометрическое представление разрешенных и запрещенных кодовых комбинаций

Расстояние между комбинациямиусловно обозначено на рис.11.1а, где показаны промежуточные комбинации, отличающиеся друг от друга одним символом. В общем случае некоторая пара разрешенных комбинаций. и разделенных кодовым расстоянием изображается на прямой рис. 11.1б, где точками указаны запрещенные комбинации. Для того чтобы в результате ошибки комбинациипреоб­разовалась в другую разрешенную комбинацию, должно исказиться d символов. При искажении меньшего числа символов комбинацияперейдет в запрещенную комбинацию, и ошибка будет обнаружена. Отсюда следует, что ошибка всегда обнаруживается, если ее кратность, т. е. число искаженных символов в кодовой комбинации:

(11.2)

Если g <d , то некоторые ошибки также обнаруживаются. Однако полной гарантии обнаружения ошибок здесь нет, так как ошибочная комбинация в этом случае может совпасть с какой-либо разрешенной комбинацией. Минимальное кодовое расстояние, при котором обнаруживаются любые одиночные ошибки, d = 2.

Процедура исправления ошибок в процессе декодирования сводится к определению переданной комбинации по известной принятой. Расстояние между переданной разрешенной комбинацией и принятой запрещенной комбинацией d0 равно кратности ошибок g. Если ошибки в символах комбинации происходят независимо относительно друг друга, то вероятность искажения некоторых g -символов в п -значной ком­бинации будет равна:

(11.3)

где Р0 — вероятность искажения одного символа. Так как обычно то вероятность многократных ошибок уменьшается с увеличением их кратности, при этом более вероятны меньшие расстояния В этих условиях исправление ошибок может производиться по следующему правилу. Если принята запрещенная комбинация, то считается переданной ближайшая разрешенная комбинация Например, пусть образовалась запрещенная комбинация А0 (см. рис. 11.2б), тогда принимается решение, что была принята комбинация А1. Это правило декодирования для указанного распределения ошибок является оптимальным, так как оно обеспечивает исправление максимального количества ошибок. (В общем случае оптимальное правило декодирования зависит от распределения ошибок.)

Аналогичное правило используется в теории потенциальной помехоустойчивости при оптимальном приеме дискретных сигналов, когда решение сводится к выбору того переданного сигнала, который в наименьшей степени отличается от принятого. Нетрудно определить, что при таком правиле декодирования будут исправлены все ошибки кратности:

(11.4)

Минимальное значение d , при котором еще возможно исправление любых одиночных ошибок, равно 3.

Возможно также построение таких кодов, в которых часть ошибок исправляется, а часть только обнаруживается. Так, в соответствии с рис. 11.1 в ошибки кратности исправляются, а ошибки, кратность которых лежит в пределах только обнаруживаются. Что касается ошибок, кратность которых сосредоточена в пределах то они обнаруживаются, однако при их исправлении принимается ошибочное решение — считается переданной комбинация вместо,или наоборот. Существуют двоичные системы передачи информации, в которых решающее устройство выдает, кроме обычных символов 0 и 1, еще и так называемый символ стирания Этот символ соответствует приему сомнительных сигналов, когда затруднительно принять определенное решение в отношении того, какой из символов 0 или 1 был передан. Принятый символ в этом случае стирается. Однако при использовании корректирующего кода возможно восстановление стертых символов. Если в кодовой комбинации число символов оказалось равным gc, причем

(11.5)

а остальные символы приняты без ошибок, то такая комбинация полностью восстанавливается. Действительно, для восстановления всех символов необходимо перебрать всевозможные сочетания из символов типа 0 и 1. Естественно, что все эти сочетания, за исключением одного, будут неверными. Но так как в неправильных сочетаниях кратность ошибок, то согласно неравенству (11.2) такие ошибки обнаруживаются. Другими словами, в этом случае неправильно восстановленные сочетания из-символов совместно с правильно принятыми символами образуют запрещенные комбинации, и только одно сочетание стертых символов дает раз­решенную комбинацию, которую и следует считать как правильно восстановленную.

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

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

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

(11.6)

что, в свою очередь, требует избыточного числа символов, где к — количество символов в комбинации кода без избыточности. Можно ввести понятие избыточности кода и количественно определить, как:

(11.7)

При независимых ошибках вероятность определенного сочетания g ошибочных символов в-значной кодовой комбинации выражается формулой (11.3), а количество всевозможных сочетаний ошибочных g-символов в комбинации зависит от ее длины и определяется известной формулой числа сочетаний:



Отсюда полная вероятность ошибки кратности g , учитывающая все сочетания ошибочных символов, равняется:

(11.8)

Используя (11.8), можно записать формулы, определяющие вероятность отсутствия ошибок в кодовой комбинации, т. е. вероятность правильного приема:



и вероятность правильного корректирования ошибок:



Здесь суммирование производится по всем значениям кратности ошибок g, которые обнаруживаются и исправляются. Таким образом, вероятность некорректируемых ошибок равна:

(11.9)

Анализ формулы (11.9) показывает, что при малой величинеи сравнительно небольших значениях и наиболее вероятны ошибки малой кратности, которые и необходимо корректировать в первую очередь.

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

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




Скачать 123,09 Kb.
оставить комментарий
Дата04.03.2012
Размер123,09 Kb.
ТипЛекция, Образовательные материалы
Добавить документ в свой блог или на сайт

отлично
  3
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх