Главная Учебники - Разные Лекции (разные) - часть 16
СОДЕРЖАНИЕ Введение……………………………………………………………………4 1. Задание на курсовую работу……………………………………………5 1.1. Общая постановка задачи………………………………………….….5 1.2. Содержание пояснительной записки …………………………….… 8 1.3. Правила оформления пояснительной записки……………………....8 2. Некоторые теоретические сведения и методические указания к выполнению курсовой работы…………………………………….…..9 2.1. Системы и каналы связи………………… ……………………………9 2.2. Модель источника сообщений……………………………………….10 2.3. Энтропия источника сообщений…………………………………….11 2.4. Кодер источника ……………….…………………………………….12 2.4.1. Код Шеннона – Фанно…………..…………………………………12 2.4.2. Код Хаффмана…….………………………………………………..14 2.5. Замечания относительно алфавита и характеристик обобщенного источника сообщений…………………………………17 2.6. Дискретные каналы связи…………….………………………………18 2.7. Оптимальное решающее правило восстановления символа при приеме по критерию минимума вероятности средней ошибки…………………………………………………………………19 1
. ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ
1.1.
ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ
Задана некоторая система связи для передачи дискретных сообщений. Характеристики источника сообщений представлены в табл. 1. Для передачи сообщения по каналу связи, в зависимости от варианта работы, используется либо код Хаффмена, либо код Шеннона – Фано. Канал связи зашумлен, т.е. принимаемый символ не обязательно совпадает с переданным. В предположении стационарности и отсутствия памяти у канала его переходные вероятности имеют числовые значения, представленные в табл. 2 и 3 (для сильно и слабо зашумленных каналов соответственно). В процессе выполнения работы необходимо проделать следующее. 1. Составить обобщенную структурную схему системы связи для передачи дискретных сообщений, содержащую источник сообщений, кодер, модулятор, канал связи, демодулятор, декодер и приемник сообщений. Изобразить качественные временные диаграммы сигналов во всех промежуточных точках структурной схемы. Вид модуляции выбирается студентом самостоятельно. Все диаграммы должны сопровождаться словесными описаниями. 2. Определить количество информации, содержащейся в каждом элементарном сообщении источника, энтропию и избыточность источника информации. 3. Построить код Шеннона-Фано или Хаффмана (в зависимости от задания варианта) для сообщений источника. 4. Рассчитать вероятности появления двоичных символов, передаваемых по каналу. Определить скорость передачи информации по каналу в предположении отсутствия помех. Вычислить пропускную способность канала, сравнить ее величину со скоростью передачи информации. 5. Определить оптимальное по минимуму вероятности средней ошибки правило восстановления символа при приеме в условиях сильно зашумленного канала. 6. Вычислить среднюю вероятность ошибки при передаче сообщения по слабо зашумленному каналу. 7. Оценить вероятность правильного приема последовательности сообщений, заданной в табл. 3. Таблица 1 Алфавит источника и вероятности символов № а б в г д ж з и к л м н о п 1 0,069 0,019 0,052 0,007 0,09 0,06 0,101 0,11 0,062 0,053 0.1 0,09 0,115 0,072 2 0.035 0.11 0.049 0,089 0.001 0.036 0.077 0.11 0.064 0.097 0.06 0.098 0.078 0.096 3 0.091 0.024 0.067 0.082 0.119 0.027 0.078 0.111 0.023 0.022 0.11 0.068 0.153 0.025 4 0.105 0.025 0.105 0.02 0.094 0.036 0.086 0.093 0.016 0.107 0.066 0.055 0.122 0.07 5 0.055 0.1 0.054 0.116 0.087 0.023 0.099 0.059 0.003 0.067 0.062 0.099 0.077 0.099 6 0.02 0.057 0.052 0.025 0.151 0.109 0.047 0.05 0.146 0.038 0.05 0.021 0.136 0.098 7 0.064 0.102 0.034 0.085 0.092 0.074 0.102 0.028 0.026 0.067 0.014 0.014 0.167 0.131 8 0.032 0.058 0.089 0.064 0.086 0.122 0.089 0.081 0.026 0.079 0.035 0.086 0.083 0.07 9 0.099 0.083 0.107 0.077 0.121 0.097 0.089 0.042 0.041 0. 014 0.113 0.021 0.011 0.085 10 0.082 0.061 0.07 0.023 0.111 0.124 0.131 0.045 0.019 0.118 0.091 0.011 0.098 0.016 11 0.074 0.102 0.034 0.095 0.092 0.084 0.102 0.018 0.026 0.057 0.04 0.014 0.167 0.131 12 0.065 0.1 0.064 0.116 0.097 0.023 0.089 0.059 0.003 0.057 0.052 0.099 0.077 0.089 13 0.097 0.008 0.007 0.111 0.064 0.036 0.116 0.018 0.01 0.016 0.1 0.16 0.128 0.039 14 0.14 0.083 0.021 0.051 0.014 0.092 0.137 0.084 0.056 0.101 0.038 0.047 0.102 0.034 15 0.107 0.084 0.094 0.104 0.063 0.087 0.009 0.081 0.022 0.071 0.053 0.106 0.035 0.084 16 0.02 0.067 0.052 0.035 0.141 0.109 0.037 0.05 0.136 0.038 0.05 0.021 0.126 0.098 17 0,059 0,019 0,062 0,017 0,08 0,06 0,104 0,11 0,062 0,05 0.11 0,08 0,115 0,072 18 0.099 0.093 0.107 0.087 0.131 0.097 0.079 0.042 0.031 0.014 0.113 0.021 0.011 0.075 19 0.105 0.035 0.105 0.02 0.094 0.046 0.096 0.083 0.016 0.107 0.056 0.045 0.122 0.07 20 0.101 0.011 0.074 0.059 0.079 0.088 0.035 0.099 0.08 0.073 0.09 0.096 0.106 0.009 21 0.045 0.11 0.059 0.099 0.001 0.046 0.067 0.11 0.054 0.097 0.06 0.088 0.078 0.086 22 0.082 0.071 0.07 0.033 0.111 0.134 0.131 0.035 0.019 0.1 18 0.081 0.011 0.088 0.016 23 0.042 0.058 0.099 0.064 0.096 0.122 0.079 0.081 0.016 0.079 0.025 0.086 0.073 0.07 24 0.091 0.034 0.067 0.092 0.119 0.037 0. 068 0.111 0.013 0.022 0.11 0.058 0.153 0.025 25 0,039 0,01 0,052 0,007 0,09 0,06 0,132 0,119 0,042 0,073 0.1 0,09 0,115 0,071 Таблица 2 Способ кодирования и элементы матрицы перехода в сильно зашумленном канале № вар. Вид кода № вар. Вид кода 1 Х 0.38 0.62 13 Ш-Ф 0.79 0.27 2 Х 0.29 0.71 14 Ш-Ф 0.75 0.32 3 Ш-Ф 0.36 0.59 15 Х 0.69 0.31 4 Х 0.28 0.69 16 Х 0.75 0.28 5 Х 0.31 0.59 17 Х 0.71 0.35 6 Ш-Ф 0.36 0.61 18 Ш-Ф 0.58 0.41 7 Х 0.32 0.67 19 Х 0.69 0.33 8 Ш-Ф 0.24 0.70 20 Ш-Ф 0.61 0.35 9 Ш-Ф 0.27 0.69 21 Х 0.59 0.39 10 Х 0.32 0.77 22 Х 0.67 0.4 11 Х 0.21 0.70 23 Ш-Ф 0.71 0.31 12 Ш-Ф 0.35 0.68 24 Х 0.62 0.28 25 Х 0.61 0.34 Здесь введены обозначения: Х - код Хаффмена, Ш- Ф - код Шеннона-Фано Таблица 3 Вероятности переходов и вид последовательности сообщений для слабо зашумленного канала связи № вар. Послед. сообщен. № вар. Послед. сообщен. 1 0.957 0.039 кира 13 0.035 0.977 жора 2 0.921 0.065 пила 14 0.021 0.943 бомж 3 0.965 0.047 клаб 15 0.027 0.978 дома 4 0.938 0.056 жбан 16 0.065 0.925 зима 5 0.976 0.045 рома 17 0.034 0.973 лика 6 0.959 0.076 гонг 18 0.051 0.945 дока 7 0.969 0.062 бора 19 0.062 0.955 нора 8 0.981 0.075 азик 20 0.041 0.928 жлоб 9 0.957 0.049 гном 21 0.039 0.947 кило 10 0.968 0.078 липа 22 0.057 0.967 рама 11 0.976 0.081 вода 23 0.048 0.954 клон 12 0 0.965 0.054 жало 24 0.032 0.959 вагон 25 0.078 0.969 банк 1.2. Содержание пояснительной записки
Структура пояснительной записки к курсовой работе и последовательность изложения результатов выполнения должны быть следующими. 1. Титульный лист. 2. Оглавление (Содержание). 3. Введение. 4. Задание и исходные данные в соответствии с номером варианта. 5. Обобщенная структурная схема системы связи для передачи дискретных сообщений. 6. Расчет информационных характеристик источника. 7. Построение кода для сообщений источника. 8. Статистические характеристики закодированных сообщений. 9. Оптимальное по минимуму средней ошибки правило восстановления символа при приеме в условиях сильно зашумленного канала. 10. Ошибки в передаче сообщений по слабо зашумленному каналу. 11. Заключение. 12. Список использованной литературы. 1.3. Правила оформления пояснительной записки
1. В пояснительной записке все пункты выполнения курсовой работы должны располагаться в той последовательности, которая приведена выше, иметь ту же нумерацию и те же заголовки. В зависимости от сложности выполняемого задания разрешается вводить подпункты, структурирующие изложение материала. В начале каждого пункта кратко излагаются необходимые элементы теории. 2. Основные полученные аналитические формулы должны иллюстрироваться рисунками, дающими представление о качественном характере поведения исследуемых величин и процессов. Рисунки должны быть пронумерованы и иметь подписи. 3. В пояснительной записке должны быть введение и заключение. Во введении формулируются цели курсовой работы с учётом её содержания. В заключении даётся краткий анализ результатов с отражением их особенностей. 4. Оглавление курсовой работы располагается после титульного листа, именуется как "Содержание" и состоит из номеров и названий разделов с указанием номеров страниц. 5. оформляется на стандартных листах формата А4. Шрифт для основного текста Times New Roman Cyr, размер 14 пунктов. Текстовая часть проекта выполняется по ГОСТ 2.105-95 "'Общие требования к текстовым документам". Листы должны быть надежно скреплены, страницы пронумерованы. 6. Список использованной литературы оформляется в соответствии с ГОСТ 7.32-91 и приводится на последней странице работы. 7. Текст курсовой работы должен быть расположен на одной стороне листа. Обратная (чистая) сторона листа используется для пояснений и исправлений в соответствии с замечаниями преподавателя, если после рецензирования исправления и комментарии потребуются. 8. После внесения замечаний преподавателя замена листов не допускается. Можно лишь вклеивать дополнительные листы с исправлениями. 2. Некоторые теоретические сведения и методические указания к выполнению курсовой работы
Системой связи называют совокупность технических средств, необходимых для передачи сообщения от источника к получателю В работе рассматривается простейшая модель канала связи, состоящая из модулятора, передатчика, линии связи (среды распространения сигнала), приемника и демодулятора. Кодер и декодер канала в данной работе не рассматриваются, т.к. соответствующий материал отнесен к следующему курсу – «Теория кодирования». Он опирается на другой математический аппарат и известен как алгебраическая теория кодирования. Рассматриваемый в работе метод кодирования может интерпретироваться как результат функционирования кодера источника сообщений и включаться в обобщенную модель источника. Аналогичное справедливо и для декодера, с той лишь разницей, что он вносится в обобщенную модель получателя сообщений. Таким образом, предлагаемая модель системы связи состоит из обобщенных моделей источника и получателя сообщений и модели канала связи. 2.2. МОДЕЛЬ ИСТОЧНИКА СООБЩЕНИЙ
С точки зрения получателя сообщений источник можно рассматривать как некоторый эксперимент с известным набором возможных исходов. В каждом таком эксперименте возможен только один исход, но какой именно – неизвестно. Можно лишь указать вероятность того или иного исхода. Говорят, что источник сообщений задан, если известен набор исходов Полагается, что в единицу времени Источник обычно «генерирует» последовательно не одно, а несколько сообщений. Такую последовательность сообщений можно представить как случайный процесс с дискретным пространством состояний. На рис. 1 представлена одна из реализаций такого случайного процесса. Рис. 1. Одна из реализаций случайного процесса, иллюстрирующая процесс «генерации» источником последовательности сообщений Для закрепления этого материала постройте еще пару отличных от приведенной на рис.1 реализации случайного процесса. При мощности множества 2.3. ЭНТРОПИЯ ИСТОЧНИКА СООБЩЕНИЙ
Получатель знает весь набор возможных сообщений, которые могут быть ему направлены, но какое именно сообщение передано ему сейчас – для него тайна. Именно в этом и заключается неопределенность состояния получателя. Если сообщение принято и есть уверенность, что понято правильно, то неопределенность исчезает. Другими словами сообщение содержало в себе ровно столько информации, сколько было неопределенности у получателя. Таким образом, центральным вопросом становится способ определения меры неопределенности сообщения. Эта величина называется энтропией (точно также как в статистической термодинамике). Если источник информации Таким образом, количество передаваемой информации зависит от того, какое именно сообщение передано, а это сообщение случайно! Поэтому носит название случайной энтропии. Обычно в теории информации работают со средними значениями, поэтому источник принято характеризовать средней (больцмановской) энтропией, определяемой по формуле: Здесь под символом Можно показать, что средняя энтропия максимальна, если все сообщения равновероятны, т.е. Алфавит может иметь вероятностное распределение, далекое от равномерного. Если некоторый исходный алфавит содержит Избыточность показывает, насколько в среднем неплотно, при заданном алфавите, «упакована» информация в сообщениях источника. В частности избыточность современного английского текста составляет 50%, избыточность русского текста - 70%. 2.4. КОДЕР ИСТОЧНИКА
Для уменьшения избыточности источника 2.4.1. КОД ШЕННОНА–ФАНО
Код Шеннона – Фано представляет собой метод сжатия информации схожий с алгоритмом Хаффмана, который появился несколькими годами позже. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано префиксные, то есть никакое кодовое слово не является префиксом (группой первых символов) любого другого слова. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов. Основные этапы создания кода. 1. Символы первичного алфавита М1 выписывают в порядке убывания вероятностей. 2. Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу. 3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1». 4. Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде. Код Шеннона — Фано строится с помощью дерева. Построение этого дерева начинается от корня. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмана. При построении кода Шеннона — Фано разбиение множества элементов может быть произведено, вообще говоря, несколькими способами. Выбор разбиения на уровне n может ухудшить варианты разбиения на следующем уровне (n + 1) и привести к неоптимальности кода в целом. Другими словами, оптимальное поведение на каждом шаге пути ещё не гарантирует оптимальности всей совокупности действий. Поэтому код Шеннона — Фано не является оптимальным в общем смысле, хотя и дает оптимальные результаты при некоторых распределениях вероятностей. Для одного и того же распределения вероятностей можно построить, вообще говоря, несколько кодов Шеннона — Фано, и все они могут дать различные результаты. Если построить все возможные коды Шеннона — Фано для данного распределения вероятностей, то среди них будут находиться и все коды Хаффмана, то есть оптимальные коды. Кодирование Шеннона — Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса. В большинстве случаев длина последовательности, сжатой по данному методу, равна длине сжатой последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях могут сформироваться неоптимальные коды Шеннона — Фано, поэтому более эффективным считается сжатие методом Хаффмана. Пример построения кодового дерева Шеннона - Фано Исходные символы: A (частота встречаемости 50), B (частота встречаемости 39), C (частота встречаемости 18), D (частота встречаемости 49), E (частота встречаемости 35), F (частота встречаемости 24). Рис.2. Кодовое дерево Полученный код: A — 11, B — 101, C — 100, D — 00, E — 011, F — 010. 2.4.2. КОД ХАФФМАНА
Этот метод кодирования состоит из двух основных этапов: – построение оптимального кодового дерева; – построение отображения «код – символ» на основе построенного дерева. Алгоритм построения кода Хаффмана.
1. Подсчитываются вероятности 2. Символы первичного алфавита выписывают в порядке убывания вероятностей. 3. Последние два символа в упорядоченном списке объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение. Вероятность возникшего нового символа равна суммарной вероятности удаленных. Затем вставляют новый символ в список остальных на соответствующее место (повторяют ранжирование списка по вероятности). 4. Предыдущий шаг повторяют до тех пор, пока в списке остается более одного символа. Этот процесс можно представить как построение дерева, корень которого — символ с вероятностью 1, получившийся при объединении символов последнего шага, два его предшественника - символы из предыдущего шага. Каждые два элемента, стоящие на одном уровне, нумеруются: 0 или 1. Коды получаются из путей - от первого потомка корня и до листка. При декодировании можно использовать то же самое дерево: считывается по одной цифре и делается шаг по дереву, пока не достигается лист. Затем выводится символ, стоящий в листе, и производится возврат в корень. Построение дерева Хаффмана
Бинарное дерево, соответствующее коду Хаффмана, называют деревом Хаффмана. Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева. Общая схема построения дерева Хаффмана выглядит следующим образом. 1. Составляется список кодируемых символов. 2. Из списка выбирается 2 узла с наименьшим весом (под весом следует понимать частоту использования символа или вероятность его появления – чем чаще используется, тем больше весит ). 3. Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов. 4. Удалим выбранные узлы из списка. 5. Добавим вновь сформированный узел к списку. 6. Если в списке больше одного узла, то повторить п.п. 2-6. Пример построения кода и дерева Хаффмана
Рассмотрим на примере источника с алфавитом мощностью 9 , задаваемого множеством пар Таблица 4 0.20 0.15 0.15 0.12 0.10 0.10 0.08 0.06 0.04 Таблица 5 1 2 3 4 5 6 7 8 Код. 0.20 11 0.15 001 0.15 011 0.12 010 0.10 101 0.10 100 0.08 0001 0.06 00001 0.04 00000 В рисунке табл. 5 приведены все объединения, указанные в алгоритме Хаффмана. Нетрудно убедиться, что «дерево», изображенное на рис. 3, получено простым поворотом на корень Рис. 3. Схема реализации алгоритма Хафманна При движении от корня к листу Дерево Хаффмана в стандартном виде представлено на рис. 4. На нем каждому повороту направо или налево предыдущей схемы поставлены в соответствие стрелочки Рис. 4. Дерево Хаффмана для рассматриваемого примера 2.5. ЗАМЕЧАНИЯ ОТНОСИТЕЛЬНО АЛФАВИТА И ХАРАКТЕРИСТИК ОБОБЩЕННОГО ИСТОЧНИКА СООБЩЕНИЙ
Как отмечалось выше, источник сообщений и кодер источника часто объединяют вместе в некоторый обобщенный источник. Рассмотрим способ определения его характеристик. Согласно изложенному в п.2.4., мощность нового алфавита равна двум (либо «0», либо «1»). А вот вероятности появления этих символов Вам предстоит вычислить. Как решить эту задачу? Известны вероятности появления сообщений исходного алфавита, и Вы уже построили код Шеннона- Фано или Хаффмана. Согласно последнему можно рассчитать частоту появления «1» (или «0») в каждом кодовом слове. Известна и вероятность появления этого кодового слова. Так, в примере, рассмотренном выше, частота появления «1» при генерации 2.6. Дискретные каналы связи
Канал называется дискретным по входу (выходу), если множество входных (выходных) сообщений конечно. Неотъемлемым свойством любого реального канала связи является наличие в нем источников помех, шумов, искажений. В феноменологической модели канала связи воздействие шумов и помех на сигнал не детализируется, а лишь указывается вероятность того, что сигнал будет искажен на столько, что на приемном конце канала он будет воспринят как некоторый другой сигнал из возможного списка (из алфавита источника). Будем говорить, что дискретный канал – канал без памяти, если каждое сообщение в любой последовательности сообщений искажается в канале независимо от того, какие сообщения передавались ранее, до него. Говорят при этом, что межсимвольной интерференцией можно пренебречь. Говорят, что дискретный канал без памяти задан, если заданы все условные вероятности Остановимся на одном моменте. Должны ли алфавиты входного и выходного устройства канала совпадать? Оказывается – нет! Например, в канале со стиранием выходной алфавит содержит, кроме символов входного алфавита, специальный символ стирания, который появляется на выходе дискретного канала, когда демодулятор не может с уверенностью принять решение в пользу одного из входных символов. При выполнении работы
обратите внимание
на то, что мощность алфавита в кодере источника равна двум. Это значит, что матрица переходов Будем говорить, что канал зашумлен слабо, если величина Если входной и выходной алфавиты совпадают и при ошибке в приеме вероятности появления любых ошибочных символов одинаковы, т.е. то канал называют симметричным. Если, кроме того, вероятность ошибки не зависит от времени, то говорят о стационарном симметричном канале. Наиболее просто выглядит модель стационарного симметричного канала без памяти, в котором ошибки при приеме различных символов являются статистически независимыми. Для такого канала вероятность получения Из этого выражения можно найти такие характеристики, как вероятность правильного приема блока из и вероятность приема блока, содержащего хотя бы одну ошибку, 2.7. ОПТИМАЛЬНОЕ РЕШАЮЩЕЕ ПРАВИЛО ВОССТАНОВЛЕНИЯ СИМВОЛА ПРИ ПРИЕМЕ ПО КРИТЕРИЮ МИНИМУМА ВЕРОЯТНОСТИ СРЕДНЕЙ ОШИБКИ
При приеме сигнала по зашумленному каналу возникает вопрос о том, какой реально символ был передан
, совпадает ли он с тем, что зафиксировано на приемном устройстве, или шумы и помехи исказили его «до неузнаваемости». Другими словами: приняли сигнал В работе нужно получить решающее правило - правило выбора переданного символа Канал связи задается двумя множествами Заметим, что эта условная вероятность принципиально отличается от вероятности перехода, задающей канал связи. Она описывает вероятность при условии известного принятого символа
, тогда как переходная вероятность задается при условии известного переданного символа
. Однако эти вероятности связаны между собой известным соотношением которое можно переписать в виде С максимальной достоверностью переданное сообщение может быть определено как При этом вероятность ошибки в определении переданного символа при принятом символе Если теперь вычислить среднюю ошибку, получаемую усреднением по всем возможным принимаемым символам, то вероятность ошибки будет равна: Из приведенного соотношения видно, что ошибка будет минимальна, если для каждого принятого символа Описанное правило реализуем с помощью следующего алгоритма, проиллюстрированного приводимым ниже примером и рис.5. Пусть вероятности передачи символов по каналу заданы вектором Построим фигуру, изображенную на рис.5 Рис. 5 В соответствии с (13) для каждого ЛИТЕРАТУРА
1. Колесник В.Д. и Полтырев Г.Ш. Курс теории информации. – М.: Наука, 1982. 2. Стратонович Р.Л. Теория информации. – М.: Сов. радио, 1975. 3. Котоусов А.С. Теория информации. – М.: Радио и связь, 2003.
|