Эффективное кодирование. Код Шеннона - Фано. 2
Министерство образования и науки Российской Федерации
КАЗАНСКИЙ НАУЧНО - ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
им. А.Н.ТУПОЛЕВА
Институт радиоэлектроники и телекоммуникаций
Кафедра радиоэлектронных и телекоммуникационных систем
“Эффективное кодирование. Код Шеннона - Фано”
По курсу “Теория электрической связи”
Задание 3
Выполнила студентка группы 5305
Безденежных Н.Е.
Казань 2011
Содержание
1. Задание
2. Введение
3. Теоретическая часть
4. Практическая часть
5. Заключение
6. Список использованной литературы
Задание 3
Источник сообщений выдает целые значения xi (i=1,2,...9) случайной величины Х, распределение которой подчиняется закону Пуассона с параметром =3.
Закодировать сообщения кодом Шеннона-Фано.
Построить помехоустойчивый код для уменьшения вероятности ошибочного декодирования в 50 раз.
Определить:
1) Пригодность кода для передачи сообщений в смысле их однозначного декодирования.
2) Степень сжатия кода по сравнению с равномерным двоичным кодом (в процентах).
3) Насколько код Шеннона-Фано длиннее оптимального (в процентах).
Введение
Данная работа направлена на изучение методов кодирования, избыточности кода, как одного из факторов безошибочной и наиболее компактной передачи кодированной информации. В ходе работы требуется закодировать сообщения кодом Шеннона-Фано, проверить пригодность кода в смысле однозначного декодирования сообщений, найти степень сжатия кода по сравнению с равномерным двоичным кодом и на сколько код Шеннона-Фано длиннее оптимального, построить помехоустойчивый код для вероятности ошибочного декодирования в 50 раз.
Принцип решения изложен в теоретической части, а результаты расчетов представлены в виде графиков и таблиц практической части.
Теоретическая часть.
При передаче сообщений по линиям связи всегда приходится пользоваться тем или иным кодом, т.е. представлением сообщения в виде ряда сигналов. Кодированием называется отображение состояния одной физической системы с помощью состояния некоторой другой.
Коды различаются по числу элементарных символов (сигналов), из которых формируются комбинации, иными словами – по числу возможных состояний системы. Код с двумя элементарными символами называется двоичным. Двоичные коды широко применяются при вводе информации в электронные цифровые вычислительные машины, работающие по двоичной системе счисления.
Одно и то же сообщение можно закодировать различными способами. Возникает вопрос об оптимальных способах кодирования. Естественно считать оптимальным такой код, при котором на передачу сообщения заданной длины будет затрачено минимальное количество элементарных символов. Если на передачу каждого элементарного символа тратится одно и то же время, то оптимальным будет такой код, при котором на передачу сообщения заданной длины будет затрачено минимальное количество элементарных символов.
Код должен быть закодирован так, чтобы при его получении на приемной стороне он мог быть однозначно декодирован. Для однозначного декодирования код должен обладать префиксным свойством, т.е. никакая кодовая комбинация, взятая целиком, не может являться началом другой кодовой комбинации. Алгоритм Шеннона-Фано построен так, что удовлетворяет данному свойству.
Код может быть однозначно декодирован, если среднее число элементарных символов на сообщение больше, чем минимально допустимая средняя длина кодовой комбинации.
Средняя информация, содержащаяся в одном сообщении, т.е. энтропия, вычисляется по формуле [1,стр507]:
, (1)
где pi - вероятность того, что будет передаваться определённое сообщение.
Среднее число элементарных символов на сообщение [1,стр507]:
где pi - вероятность того, что будет передаваться это сообщение,
ni – количество элементарных символов в данном сообщении.
Если nmin > nср , то это означает, что данный код непригоден для передачи информации, потому что его нельзя однозначно понимать при декодировании. Недостаток такого кода в том, что некоторые кодовые комбинации являются началом (префиксом) для других.
В алгоритме Шеннона-Фано необходимо знать вероятности передаваемых сообщений. Сообщения записываются в столбец в порядке убывания вероятности передаваемых сообщений . Расставленные сообщения разбивают на две группы так, чтобы суммарные вероятности сообщений в каждой группе были равны. Верхней присваивают кодовый символ 1, а нижней 0, деление продолжается пока в каждой группе не останется по одному сообщению.
Вероятности случайных величин, распределенных по закону Пуассона вычисляются по формуле:
где - параметр распределения.
Степень сжатия кода по сравнению с равномерным определяется так:
Сначала вычисляется средняя длинна кодовой комбинации данного кода по формуле:
где - длинна -ого сообщения, - вероятность появления -ого сообщения.
Минимальная длинна кодовой комбинации равномерного кода , которым можно закодировать сообщений, определяется как наибольшее целое к .
Таким образом, степень сжатия кода можно определить по формуле:
Минимальная средняя длина кодовой комбинации оптимального эффективного кода численно равна энтропии источника сообщений:
Таким образом, полученный код длиннее оптимального (в процентах):
Помехоустойчивое кодирование
Основными принципами помехоустойчивого кодирования является обнаружение и исправление ошибки.
При принципе обнаружения определяется код, в котором присутствует ошибка, но разряд не указывается. При принципе исправления определяется код и разряд, в котором присутствует ошибка.
Основой любого помехоустойчивого кода является обычный двоичный код. К каждой кодовой комбинации двоичного кода добавляются избыточные символы. Зачет них решается задача помехоустойчивого кодирования.
где - длина помехоустойчивого кода
-простой код (количество информационных символов)
-добавочные символы
Формула для нахождения вероятность той или иной ошибки:
Для нахождения вероятности любой ошибки:
где - кратность ошибки, количество разрядов кодовой комбинации в которых ошибка произошла.
Линейные двоичные блоковые коды удобны тем, что, представляя информационные и кодовые слова в форме двоичных векторов, мы можем описать процессы кодирования и декодирования с помощью аппарата линейной алгебры. При этом компонентами вводимых векторов и матриц являются символы 0 и 1 [4,стр133]:
Операции над двоичными компонентами производятся по правилам арифметики - „исключающие или” (по модулю 2) Табл.№1.
Сложение | Умножение | ||||
0 | 1 | 0 | 1 | ||
0 | 0 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 1 | 0 | 1 |
Кодер двоичного блокового - кода отображает множество
возможных двоичных информационных слов во множество - мерных кодовых слов. В теории кодирования между этими множествами всегда существует взаимно однозначное соответствие. Рис.1.
Рис.1. Кодер двоичного блокового - кода.
Вместо бит информационного вектора в канал передается бит кодового вектора. В этом случае говорят об избыточном кодировании со скоростью:
Чем ниже скорость, тем больше избыточность кода, и тем большими возможностями для защиты от ошибок он обладает.
Структура кодовых векторных пространств:
Исходным материалом для построения кодовых конструкций служит -мерное двоичное векторное пространство, в котором заданы операция -„исключающие или”(арифметика по модулю 2 - mod2). В него вложено -мерное линейное пространство, содержащее кодовых слов. Код образуется с помощью комбинаций линейно независимых базисных векторов .
Эти векторы образуют строки порождающей матрицы кода .
Для кода существует дуальный код такой, что скалярное произведение любой пары векторов, один из которых принадлежит пространству , а другой — пространству , всегда равно нулю. Это значит, что векторы кода ортогональны векторам кода . С другой стороны, если некоторый вектор ортогонален всем векторам кода , то он принадлежит коду и наоборот. Рис.2.
Рис.2. -мерное двоичное векторное пространство.
Дуальное векторное подпространство «натянуто» на линейно независимые базисные векторы . Эти векторы образуют строки проверочной матрицы.
Следует отметить важное свойство: как в порождающей, так и в проверочной матрице присутствует единичная матрица. И она используется в процессе кодирования и декодирования.
Кодовое слово - и информационное слово - связаны соотношением:
где — порождающая матрица.
Практическая часть.
Решение:
Для создания кода Шеннона-Фано найдем сначала вероятности, с которыми появляются 12 сообщений xi от x1 =1 до x9 =9. Закон Пуассона определяется выражением:
;
где а= - параметр закона.
=3
Сообщение | Рi |
x1=1 | 0,149 |
x2=2 | 0,224 |
x3=3 | 0,224 |
x4=4 | 0,168 |
x5=5 | 0,101 |
x6=6 | 0,05 |
x7=7 | 0,022 |
x8=8 | 0,008 |
x9=9 | 0,002 |
По данной формуле находим все 9 вероятностей и располагаем их в порядке убывания. Затем непосредственно кодируем сообщения кодом Шеннона-Фано.
Суть кодирования состоит в том, что:
1) все символы записываются в порядке убывания их вероятностей;
2) вся совокупность символов разбивается на две примерно равновероятные группы;
3) всем символам верхней группы приписывается первый кодовый символ 1; символам нижней группы - кодовый символ 0;
4) аналогично каждая группа разбивается на подгруппы по возможности с одинаковыми вероятностями, причем верхним подгруппам в обеих группах приписывается символ 1(второй кодовый символ), а нижним - символ 0;
5) эта процедура повторяется до тех пор, пока в каждой подгруппе не останется по одной букве;
Процесс кодирования представлен в таблице.
Кодирование по методу Шеннона-Фано.
Символ | pi | Разбиение | Код. | ||||
а1 а2 а3 а4 а5 а6 а7 а8 а9
| 0,224 0,224 0,168 0,149 0,101 0,05 0,022 0,008 0,002
| 1 0 |
1 0 |
1 0
|
1 0 1
| 11 10 011 010 0011 0010 00011 00010 000011
| |
1. Пригодность кода для передачи сообщений в смысле их однозначного декодирования определяется по наличию у полученного кода т.н. префиксного свойства. Суть этого свойства заключается в том, что никакая кодовая комбинация, взятая целиком, не должна являться началом другой кодовой комбинации этого же кода.
2. Степень сжатия данного кода по сравнению с равномерным определяется так: сначала вычисляется средняя длина кодовой комбинации данного кода:
.
0,224*2+0,224*2+0,149*3+0,168*
Минимальная длина кодовой комбинации равномерного кода, которым можно закодировать 12 сообщений определяется как наибольшее ближайшее целое к log10. Это будет 4. Таким образом степень сжатия кода можно определить:
При оптимальном двоичном кодировании: ;
3. Минимальная средняя длина кодовой комбинации оптимального эффективного кода численно равна энтропии источника сообщений:
.
Таким образом, полученный код длиннее оптимального в процентах на:
ДАЛЕЕ ПЕРЕСЧИТАТЬ КОД ДЛЯ УМЕНЬШЕНИЯ ВЕРОЯТНОСТИ НИ В 100 РАЗ, А В 50!!
Средняя длина кода полученного методом Шеннона-Фано равна и минимальное кодовое расстояние:
Для того чтобы построить помехоустойчивый код, для которого вероятность ошибочного декодирования по сравнению с кодом Шеннона-Фано будет в 100 раз меньше:
1. Допустим, что вероятность ошибки в одном символе полученного кода:
Вероятность ошибки искомого кода будет равно:
2.Найдем - минимальное кодовое расстояние, для которого вероятность ошибки будет равна:
.
3.Методом подбора найдем ближайшее решение задачи для кода, полученного методом Шеннона-Фано:
Восспользуемся формулой:
Если ,
удовлетворяется условие:
Вероятности той или иной ошибки:
Отсюда вероятность ошибочного декодирования, которая меньше в 100 раз:
Найдем разницу:
Погрешность составляет .
Для получения помехоустойчивого кода с вероятностью ошибки декодирования , необходимо добавить информационным символам не менее 9-ти добавочных символ . В итоги получили помехоустойчивый код: .
Опишем метод построения порождающей матрицы, для получения помехоустойчивых кодов, основываясь на теоретическом материале:
Приведем пример построение порождающей матрицы на примере кода-, для кода- построение порождающей матрицы аналогично.
1.В таблице№1 представлены все кодовые слова - кода (- информационные, а - проверочные символы).
№ n\n | |||||
1 | 0 | 0 | 1 | 1 | 0 |
2 | 0 | 1 | 0 | 1 | 1 |
3 | 0 | 1 | 1 | 0 | 1 |
4 | 1 | 0 | 0 | 0 | 1 |
5 | 1 | 0 | 1 | 1 | 1 |
6 | 1 | 1 | 0 | 1 | 0 |
7 | 1 | 1 | 1 | 0 | 0 |
8 | 0 | 0 | 0 | 0 | 0 |
2. Системой проверочных уравнений, определяющих правила формирования проверочных символов по известным информационным символам:
номер проверочного символа;
номер информационного символа;
коэффициенты, принимающие значения 0 или 1 в соответствии с правилами формирования конкретных групповых кодов.
Пример. Для кода проверочные уравнения имеют вид:
.
3. Векторное пространство над включает в себя векторов (-последовательностей), а подпространством его является множество из кодовых слов длины , которое однозначно определяется его базисом, состоящим из линейно независимых векторов. Поэтому линейный - код полностью определяется набором из кодовых слов, принадлежащих этому коду.
Набор из кодовых слов, соответствующих базису, обычно представляется в виде матрицы, которая называется порождающей.
- код, который был представлен в таблице№1, может быть задан матрицей:
Остальные кодовые слова получаются сложением строк матриц в различных сочетаниях.
Общее количество различных вариантов порождающих матрицу определяется выражением:
Для исключения неоднозначности в записи вводят понятие о канонической или систематической форме матрицы, которая имеет вид
где - единичная матрица, содержащая информационные символы;
- прямоугольная матрица, составленная из проверочных символов.
Порождающая матрица в систематическом виде для (5,3) - кода
Порождающая матрица в систематическом виде может быть получена из любой другой матрицы посредством элементарных операций над строками (перестановкой двух произвольных строк, заменой произвольной строки на сумму ее самой и ряда других) и дальнейшей перестановкой столбцов.
Проверочная матрица в систематическом виде имеет вид
где - единичная матрица;
- прямоугольная матрица в транспонированном виде матрицы , из порождающей матрицы.
Проверочная матрица (5,3) – кода
Произведение информационного слова на порождающую матрицу дает кодовое слово кода
Пример для кода (5,3):
Заключение.
В ходе проделанной работы были рассчитаны вероятности сообщений. Эти вероятности были необходимы для кодировки этих сообщений кодом Шеннона-Фано. Установлено, что этот код Шеннона-Фано в данном случае пригоден для передачи сообщений в смысле их однозначного декодирования. Степень сжатия кода по сравнению с равномерным двоичным кодом составляет 54%. Код Шеннона-Фано длиннее оптимального на 1.55%.
Рассчитана, что для получения помехоустойчивого кода с вероятностью ошибки декодирования , необходимо добавить информационным символам не менее 9-ти добавочных символ . В результате получили помехоустойчивый код: . В работе описан метод построения порождающей - , проверочной - матриц.
Список использованной литературы:
1. Вентцель Е.С. «Теория вероятностей». – М.: Высш.шк., 2002г.
2. Зюко А.Г. «Теория передачи сигналов». – М.: Радио и связь, 1986г.
3. Зюко А.Г., Коробов Ю.Ф. «Теория передачи сигналов». – М.: Связь, 1972г.
4. Козлов С.В., Седов С.С. «Теория электрической связи». Пособие по курсовой работе. Казань. 2003г.
11