Файл: 1. Функциональная схема системы передачи информации, назначение ее составляющих.pdf

1
1. Функциональная схема системы передачи информации,
назначение ее составляющих
Схема предстаалена следующим образом:
Источник, кодирование (на стороне передатчика), канал (который может быть подвержен помехам), декодирование (на стороне приемника), получатель.
Рисунок 1.1 – система передачи информации
2. Основные виды сигналов, используемых при передаче
информации
Рисунок 2.1 – виды сигналов
Сигналы делятся на два типа: цифровой и аналоговый.
Цифровой: сигнал, который можно представить в виде последовательности дискретных (цифровых) значений. (Цифровой сигнал представляется в виде нулей и единиц)
Аналоговый: сигнал данных, у которого каждый из представленных параметров описывается функцией времени и непрерывным множеством возможных значений.

2
Рисунок 2.2 – примерный вид сигналов
3. Характеристики источника информации и канала связи
Основными информационными характеристиками источника информации являются:
1. количество информации в сообщениях (информативность);
2. энтропия источника информации (энтропия);
3. избыточность источника информации (избыточность);
4. производительность источника сообщений (производительность).
Основными информационными характеристиками канала являются:
1. скорость передачи информации по каналу связи (скорость);
2. пропускная способность канала связи (пропускная способность).
4. Энтропия источника дискретных сообщений
Энтропия – среднее количество информации, которое приходится на одно сообщение (один символ последовательности), поступающее от источника без памяти. Получим, применяя операцию усреднения по всему объему алфавита
????(????) = − ∑
????(????
????
????
????=1
) log
2
????(????
????
) = ∑
????(????
????
) log
2 1
????(????
????
)
????
????=1
(4.1)
(Уравнение 4.1) известно как формула Шеннона для энтропии источника дискретных сообщений. (ее высчитывали в ДЗ №1)
Энтропия равна нулю, если с вероятностью 100% (1.0) источником выдается всегда одно и то же сообщение (в этом случае неопределенность в поведении источника сообщений отсутствует). Энтропия максимальна, если символы источника появляются независимо и с одинаковой вероятностью.
5. Энтропия источника непрерывных сообщений

3
Полная энтропия источника непрерывных сообщений состоит из двух слагаемых, одно из которых определяется законом распределения, а второе является постоянной величиной, определяющей шаг квантования, который влияет на точность измерений.
Этот член выражения определяет постоянную составляющую и исключается из рассмотрения.
6. Энтропия сложных сообщений и ее свойства *
В понимании энтропии сложных сообщений, необходимо выделить 4 свойства:
1. Энтропия источника и количество информации тем больше, чем больше размер алфавита источника;
2. Энтропия источника зависит от статистических свойств сообщений.
Энтропия максимальна, если сообщения источника равновероятны и статистически независимы;
3.
Энтропия источника, вырабатывающего неравновероятные сообщения, всегда меньше максимально достижимой;
4. При наличии статистических связей между элементарными сообщениями (памяти источника) его энтропия уменьшается.
А также в этот раздел входит все то, что входит в п.4 и 5 данной работы. https://studizba.com/files/show/doc/129245-1-63429.html
7. Количество информации в сообщении при недостоверной
передаче *
Если принятое сообщение недостоверно, то количество получаемой приемником информации уменьшается на величину неопределенности, вносимой помехами.
Если неопределенность источника информации не превышает пропускной способности канала, то существует код, обеспечивающий передачу информации через канал с помехами со сколь угодно малой частотой

4 ошибок. Такие коды можно получить, вводя избыточность в передаваемую информацию, что потребует дополнительных разрядов в коде сообщения.
В вычислительной технике для передачи информации широко применяются посылочные корректирующие коды, имеющие дополнительные контрольные разряды.
Эти коды имеют различную степень избыточности, от которой и зависит их корректирующая способность. Чтобы можно было не только обнаружить ошибку, возникшую при передаче данных, но и исправить ее, необходимо использовать коды с большей избыточностью (с большим количеством дополнительных разрядов).
Примером может служить метод Р. Хэмминга, пользуясь которым можно построить коды различной длины. Эти коды позволяют исправлять все одиночные ошибки, а также исправлять все одиночные ошибки и обнаруживать все двойные ошибки, но не исправлять их.
Рисунок 7.1 – Код Хэмминга
8. Энтропия и количество информации при статистической
зависимости элементов сообщений *
Сообщение может состоять из отдельных элементов (слов, букв, цифр и т.п.), каждый из которых можно рассматривать как сообщение более низкого ранга. В этом случае сообщение следует рассматривать как сложное, и его

5 энтропия определяется энтропией элементов, их вероятностными характеристиками и статистическими свойствами (степенью зависимости).
Сообщение, в котором элементы некоррелированы (статистически не зависимы) и равновероятны, обладает максимальной энтропией (2.12) , (2.15)
Hmax (x) . В противном случае энтропия сообщения уменьшается. Сообщения, энтропия которых максимальна, являются оптимальными с точки зрения наибольшего количества передаваемой информации. Мерой количественной оценки того, насколько данное реальное сообщение по своей энтропии отличается от соответствующего ему оптимального сообщения: является коэффициент сжатия
???? =
????(????)
????
????????????
(????)
(8.1)
Если передается последовательность сообщений, то справедливо равенство
???? ∗ ????(????) = ????
′
????
????????????
(????)
(8.2) где n и nç длина последовательностей реальных и оптимальных сообщений. Тогда коэффициент сжатия можно выразить через длины последовательностей
???? =
????(????)
????
????????????
(????)
=
????
′
????
(8.3)
Таким образом, реальные сообщения при одинаковой информативности обладают определенной избыточностью (длиннее) по сравнению с оптимальными. Мерой избыточности является коэффициент избыточности
???? =
????−????
′
????
= 1 − ???? =
????
????????????
(????)−???? (????)
????
????????????
(????)
(8.4)
Избыточность приводит к увеличению времени передачи сообщений, излишней загрузке каналов связи. Однако избыточность повышает помехоустойчивость сообщений. Все языки обладают избыточностью, что позволяет восстановить слова и даже целые фразы при наличии ошибок.
Наконец, сообщения могут формироваться источником с большим или меньшим темпом.

6
В этой связи вводится еще одна характеристика - производительность источника, которая характеризуется величиной энтропии, формируемой источником в единицу времени
R =
????(????)
????
(8.5) где H(x) - величина энтропии, формируемой источником за время Т.
9. Эффективное кодирование (алгоритм Шеннона)
1. Символы первичного алфавита m
1
выписывают по убыванию вероятностей;
2. Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу;
3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1»;
4. Полученные части рекурсивно делятся, и их частям назначаются соответствующие двоичные цифры в префиксном коде.
Рисунок 9.1 - алгоритм шеннона (пример таблица)
Когда размер подалфавита становится равен нулю или единице, то дальнейшего удлинения префиксного кода для соответствующих ему символов первичного алфавита не происходит, таким образом, алгоритм присваивает различным символам префиксные коды разной длины. На шаге деления алфавита существует неоднозначность, так как разность суммарных вероятностей может быть одинакова для двух вариантов разделения

7
(учитывая, что все символы первичного алфавита имеют вероятность больше нуля).
Рисунок 9.2 – кодирование по алгоритму Шеннона http://toi.kb-8.com/task?n=3
10. Эффективное кодирование (алгоритм Фано (Шеннона - Фано))
1. на вход приходят упорядоченные по невозрастанию частот данные;
2. находится середина, которая делит алфавит примерно на две части.
Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева;
3. шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок.

8
Рисунок 10.1 – кодирование алгоритмом Шеннона-Фано, этап: 1
Рисунок 10.2 – кодирование алгоритмом Шеннона-Фано, этап: 2

9
Рисунок 10.3 – кодирование алгоритмом Шеннона-Фано, этап: 3
Рисунок 10.4 – кодирование алгоритмом Шеннона-Фано, этап: 4

10
Рисунок 10.5 – кодирование алгоритмом Шеннона-Фано, этап: 5
Рисунок 10.6 – кодирование алгоритмом Шеннона-Фано, этап: 6 http://toi.kb-8.com/task?n=3
11. Эффективное кодирование (алгоритм Хаффмана)
1. на вход приходят упорядоченные по невозрастанию частот данны;
2. выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»);
3. потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0»;

11 4. шаг два повторяется до тех пор, пока не будет найден главный родитель — «корень». http://toi.kb-8.com/huffman http://toi.kb-8.com/task?n=3
12. Арифметическое кодирование *
Арифметическое кодирование — один из алгоритмов энтропийного сжатия.
В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов группам бит выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов
Пусть имеется некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1.
Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу.
Рисунок 12.1 – арифметическое кодирование
Теперь возьмём символ из потока и найдём для него отрезок среди только что сформированных, теперь отрезок для этого символа стал рабочим.
Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту

12 операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.
13. Универсальное кодирование. Коды Элиаса
Универсальный код – префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распределение – монотонно (то есть p (i) ≥ p (i+1) для любого i ), ожидаемые длины двоичных слов находятся в пределах постоянного фактора ожидаемых длин, которые оптимальный код назначил бы для этого распределения вероятностей
Универсальное кодирование применяется, когда декодеру приходится работать с данными по мере поступления.
Большинство префиксных кодов для целых чисел назначает более длинные ключевые слова большим целым числам. Такой код используется, чтобы эффективно закодировать потоковое сообщение из набора возможных кодовых слов, методом упорядочивания набор кодовых слов по уменьшению вероятности, а затем пересылая индекс слова. Универсальные коды в общем не используются для точно известных распределений вероятностей.
Универсальные коды включают в себя:
– Унарное кодирование;
– Гамма-код Элиаса;
– Дельта-код Элиаса;
– Омега-код Элиаса;
– Дельта-код;
– Кодирование Фибоначчи;
– Экспоненциальный код Голомба.
Гамма-код Элиаса Универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Он используется при

13 кодировании целых чисел, максимальное значение которых не может быть определено заранее, или чтобы сжать данные, в которых маленькие значения встречаются более часто, чем большие. (Листинг кода находится в приложении А)
Дельта-код
Элиаса
Универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Дельта-код с некоторого числа короче гамма-кода. (Листинг кода находится в приложении
А)
Омега-код Элиаса – это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Так же, как гамма- и дельта-код Элиаса, он приписывает к началу целого числа порядок его величины в универсальном коде. В отличие от двух других кодов, омега- код рекурсивно кодирует префикс, именно поэтому он также известен, как рекурсивный код Элиаса. (Листинг кода находится в приложении А)
14. Словарные методы кодирования. Алгоритм LZW
Алгоритм LZW
1. Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы ω первым символом сообщения;
2. Считать очередной символ K из кодируемого сообщения;
3. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для ω, закончить кодирование, иначе переход к 4;
4. Если фраза ωK уже есть в словаре, присвоить входной фразе значение
ωK и перейти к шагу 2, иначе выдать код, соответствующий ω, добавить ωK в словарь, присвоить входной фразе значение K и перейти к шагу 2.
LZW — алгоритм сжатия на основе "словаря". Это означает, что вместо сведения в таблицу количества символов и построения деревьев (как при кодировании по Хаффману), LZW кодирует данные, обращаясь к словарю.
Таким образом, чтобы закодировать подстроку, в выходной файл нужно записать только одно кодовое число, соответствующее индексу этой подстроки в словаре. Хотя LZW часто рассматривается в контексте сжатия

14 текстовых файлов, его можно использовать для любого типа файлов. Однако, как правило, он лучше всего справляется с файлами, где есть повторяющиеся подстроки, например, с текстовыми файлами.
15. Дискретный симметричный канал без памяти *
ДСК является частным случаем более общего канала с дискретным входом и дискретным выходом. Предположим, что входом кодера канала являются q-ичные символы, т.е.X = {x
0
, x
1
, … , x
????−1
}, а выходом детектора являются Q-ичные символы, где ???? ≥ ???? = 2
????
. Если канал и модуляция без памяти, тогда характеристика вход-выход составного канала
16. Дискретный симметричный канал с памятью *
Для дискретного канала с памятью каждая буква выходной последовательности статистически зависит как от соответствующего входа, так и от прошлых входов и выходов (здесь и в дальнейшем предполагается, что канал является каналом без предвосхищения, т. е. при заданном текущем входе и заданных входах и выходах в прошлом текущий выход статистически не зависит от будущих входов). Без потери общности последовательность входов и выходов вплоть до заданного момента может быть рассмотрена как состояние канала в этот момент. В этих понятиях статистическое поведение канала описывается совместной вероятностной мерой на выходной букве и состоянии в заданный момент при условии, что заданы текущая входная буква и предыдущее состояние.
17. Основные определения и классификация помехоустойчивых
кодов.
Помехоустойчивые коды делятся на блочные и непрерывные.
Блочными называются коды, в которых последовательность информационных символов разбивается на группы и каждая из них преобразуется в определённую последовательность (блок) кодовых символов.