Васюков В.Н. - Теория электрическо связи - Часть 3. Теория информации и теория помехоустойчивости (1275348), страница 4
Текст из файла (страница 4)
Оптимальность кода Шеннона – Фано в рассмотренном примере объясняется специально подобранными вероятностями символов.2.В рассмотренных примерах предполагалось, что символы в со-общении являются независимыми (то есть вероятность появления всообщении любых двух символов рядом равна произведению вероятностей каждого из символов). В реальных сообщениях на естественных23языках символы не являются независимыми; в таких случаях следуеткодировать не отдельные символы (буквы), а группы букв или слова.Это уменьшает зависимость и повышает эффективность кода.3.Кодирование групп символов вместо отдельных символов такжеповышает эффективность кодирования в случае независимого источника с сильно различающимися вероятностями символов, как это видноиз следующего примера.Пример 5. Рассмотрим источник, вырабатывающий два независимыхсимвола с вероятностями 0,1 и 0,9.
В этом тривиальном случае методы кодирования Хаффмена и Шеннона – Фано приводят к одинаковому коду: символы алфавита кодируются символами «0» и «1». Пусть для определенностиα1 →0; α 2 →1. Энтропия источника равна H ( Α) =0,469; средняя длина кодового слова равна 1, избыточность источника и избыточность кода одинаковыи равныκ=H max ( Α) − H ( Α) 1 − 0,469== 0,531 .H max ( Α)1Применим кодирование группами по 2 символа алфавита.
Составимвсевозможные пары и запишем их с соответствующими вероятностями (найденными как произведения вероятностей отдельных символов, так как онинезависимы)Таблица 3Кодирование группамиα1α1 :0,81____ α1α1 :0,81α1α 2 :0,09___0,1___α 2α1 :0,09α1α 2 :0,09α 2α 2 :0,01Согласно построенному дереву код Хаффмена для указанных группсодержит следующие кодовые комбинации24α1α1 →1; α1α 2 →00; α 2α1 →011; α 2α 2 →010.Средняя длина кодовой комбинации, приведённая к одному символуалфавита (для этого взвешенная сумма делится на 2), равнаµ=0,81 + 0,09 ⋅ 2 + 0,09 ⋅ 3 + 0,01 ⋅ 3= 0,645 .2Вероятность символа 1 в последовательности кодовых комбинаций находится как среднее количество единиц, отнесённое к средней длине кодового словаp (1) =0,81 + 0,09 ⋅ 2 + 0,01= 0,775 .0,645 ⋅ 2Энтропия кода находится как энтропия случайной величины, принимающей два значения (0 и 1) с вероятностями 0,225 и 0,775:H к = −0,225log 0,225 − 0,775log 0,775 = 0,769 .Избыточность кодаκ=H к max − H к 1 − 0,769== 0,231 .1H к maxСравнение с кодированием одиночных символов показывает, что кодирование групп является более эффективным: уменьшаются избыточность кода и средняя длина кодового слова, вероятности символов 0 и 1 сближаются.Ещё более эффективные коды для данного источника можно получить,объединяя символы алфавита в группы по три, четыре и т.
д. В пределе, согласно теореме Шеннона, средняя длина кодовой комбинации, приведённая кодному символу алфавита, должна стремиться к значению 0,469, избыточность кода – к нулю, а вероятности кодовых символов 0 и 1 – к значению0,5.♦2511.4. Помехоустойчивое кодированиеКодирование источника, называемое также статистическим или экономным кодированием5, преследует цель повышения эффективности передачи информации, под которым понимается максимально быстрая передача.Экономное кодирование можно рассматривать как замену исходного источника другим источником с меньшей (в пределе нулевой) избыточностью. Если в канале действуют помехи, то при приёме сигналов возникают ошибки,приводящие к неправильному декодированию сообщений.
В таких случаяхвыдвигается на передний план задача повышения верности передачи. Однимиз путей ее решения является помехоустойчивое (канальное) кодирование.Помехоустойчивыми или корректирующими кодами называются коды, обеспечивающие автоматическое обнаружение и/или исправление ошибок в кодовых комбинациях. Такая возможность обеспечивается целенаправленнымвведением избыточности в передаваемые сообщения. Наиболее простой способ повышения помехоустойчивости путем введения избыточности состоит вмногократной передаче каждого символа, например, вместо слова связь можно передавать слово сссвввяяязззььь, тогда одиночные ошибки могут бытьисправлены путем «голосования» среди символов каждой тройки. На практике применяются более сложные и более эффективные методы кодирования.Теоретическим обоснованием применения канального кодированияслужит следующая основная теорема кодирования Шеннона для каналов спомехами (шумами) [1]:ТЕОРЕМА.
Если производительность источника H '( Α) меньше пропускной способности канала C , то существует по крайней мере одна процедура кодирования/декодирования, при которой вероятность ошибочного декодирования и ненадежность H ( Α | Β) могут быть сколь угодно малы.
ЕслиH '( Α) > C , то такой процедуры не существует.5Широко употребляется также термин сжатие.26Содержание теоремы кажется парадоксальным: интуиция говорит отом, что для стремления вероятности ошибки к нулю скорость передачи также должна стремиться к нулю (это ясно для случая многократной повторнойпередачи, описанной выше). Тем не менее теорема верна, но, к сожалению,она не указывает практических путей построения соответствующих кодов.Известно лишь, что по мере приближения скорости передачи к пропускнойспособности канала длины кодовых комбинаций и сложность кодера и декодера возрастают; также возрастает задержка декодирования.В настоящее время известно множество кодов, которые с большим илименьшим успехом применяются для канального кодирования, которые подразделяются на классы в соответствии с различными признаками.Если информационная последовательность символов источника (возможно, после экономного кодирования) разбивается на сегменты (блоки), кодируемые независимо друг от друга, то код называется блочным (блоковым),если же информационная последовательность кодируется без разбиения, токод называют непрерывным6.
Блочные коды, как правило, являются равномерными.Если в кодовом слове можно выделить информационные символы,служащие для передачи сообщения, и проверочные (контрольные) символы,предназначенные только для обнаружения и исправления ошибок, такой кодназывают разделимым; если такое разбиение осуществить нельзя, код является неразделимым. Примерами неразделимых кодов являются так называемые коды с постоянным весом, в частности, код «3 из 7» (стандартный телеграфный код №3 [1]), а также коды на основе матриц Адамара (коды РидаМюллера).Разделимые коды, в свою очередь, подразделяются на линейные и нелинейные.В качестве примера рассмотрим один класс помехоустойчивых кодов –линейные блочные коды.6Широкое распространение получили непрерывные коды, принадлежащие подклассу свёрточных кодов.27Блочный равномерный код состоит из кодовых слов (комбинаций)одинаковой длины n .
Элементы кодовых слов выбираются из некоторогоалфавита (канальных) символов объемом q . Если q = 2 , код называется двоичным. Далее для простоты считается, что q = 2 . Поскольку все кодовыеслова имеют одинаковую длину, удобно считать их векторами, принадлежащими линейному пространству размерности n . Для линейных кодов справедливо утверждение: линейная комбинация кодовых слов является кодовымсловом.Всего можно образовать 2n n -мерных векторов с двоичными компонентами (кодовых комбинаций или слов). Из них только M = 2k , k < n комбинаций являются разрешенными и составляют код, который называется(n, k ) -кодом (отношение k / n = R называется скоростью кода). Остальныекомбинации в кодере образоваться не могут (являются запрещенными), номогут получиться из разрешенных под воздействием помех в канале.
Поэтому если в приёмнике имеет место запрещенная комбинация, следовательно,при передаче по каналу произошла ошибка. Разрешенные комбинации, каквекторы линейного пространства, должны отстоять друг от друга достаточнодалеко. Чем больше расстояние между разрешенными комбинациями, темменьше вероятность преобразования их друг в друга под действием помех,тем выше способность кода к обнаружению ошибок. Более того, при приёмезапрещенной комбинации можно не только обнаруживать, но и исправлятьошибки. Для этого декодер должен принимать решение о переданной комбинации на основе расстояния между принятой запрещенной комбинацией иближайшей разрешенной.
Таким образом, чем дальше друг от друга разрешенные комбинации, тем выше корректирующая способность кода. Алгоритм работы декодера формально сводится к разбиению всего пространствана области Ai , i = 1,..., M , каждая из которых содержит одну разрешеннуюкомбинацию xi . Если принятая комбинация yk принадлежит области Ak , то28декодер принимает решение о том, что передавалась разрешенная комбинация xk .Для кодирования и декодирования линейных блоковых кодов применяются действия, описываемые операциями над векторами в линейном пространстве над конечным полем целых чисел [4, 5]. Сложение и умножение вконечном поле понимаются как сложение и умножение по модулю q .
Простейшее из таких полей, называемых полями Галуá – поле по модулю 2, обозначаемое GF (2) . Сложение и умножение в этом поле описываются следующими таблицами сложения и умноженияТаблица 4Таблица 5Таблица сложения в поле GF (2)Таблица умножения в поле GF (2)+01×01001000110101Мерой различия между векторами линейного пространства, как известно, может выступать некоторая функция (функционал), называемая метрикой, или расстоянием [4, 5]. В теории кодирования часто используется метрика Хэмминга, определяемая для двух двоичных кодовых векторов x и yвыражениемd ( x, y ) =n∑ ( xi − yi ) mod 2 .i =1Легко видеть, что расстояние по Хэммингу между двумя двоичнымивекторами равно количеству несовпадающих элементов (например, для векторов 00011100 и 11000110 расстояние равно 5).В n -мерном пространстве двоичных векторов можно определить скалярное произведение выражением ( x, y ) =n∑ xi yi , где сумма понимается какi =129сумма по модулю 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
