Для построения кода Шеннона - Фано составлена табл. 3.4.

Таблица 3.4

Сообще-ние	Вероят- ность	Номер деления на подгруппы			Символ кода			Длительность сигнала
		1	2		1	2	3
х1	0,7				0				1
х2	0,2				1	0			2
х3	0,1				1	1			2

Средняя длительность сигнала при этом будет

.

Скорость передачи информации в этом случае равна

.

Как видим, переход к более эффективному коду позволяет ^{увеличить скорость передачи информации в раза.}

Эффективность кодирования может быть еще увеличена, если от кодирования одиночных сообщений перейти к кодированию последовательностей (групп) сообщений (табл. 3.5).

Таблица 3.5

Сооб-щение	Вероят- ность	Деление на подгруппы						Код		Длитель- ность сигнала
х2х2 х1х2 х2х1 х2х3 х3х2 х1х1 х1х3 х3х1 х3х3	0,49 0,14 0,14 0,07 0,07 0,04 0,02 0,02 0,01								0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1		 3 3 4 4 4 5 6 6

В табл. 3.5 дано построение кода Шеннона.-.Фано для случая передачи всех возможных пар сообщений.

Средняя длительность сигнала, обеспечивающего передачу одного сообщения, в этом случае будет

.

Соответствующая скорость передачи сообщений равна

.

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

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

Заметим еще, что описанный метод построения эффективного кода Шеннона.-.Фано может быть распространен и на коды с основанием больше двух.

Рассмотренные примеры построения эффективных кодов согласуются с основной теоремой Шеннона для дискретного канала без помех. Теорема формулируется следующим образом: если поток информации , вырабатываемой источником, равен Н(Х) = С_с – , где  – сколь угодно малая величина, то всегда можно найти такой способ кодирования, который обеспечивает передачу всех сообщений, вырабатываемых источником, причем скорость передачи = С_с –  .

Обратное утверждение состоит в том, что невозможно обеспечить передачу всех сообщений источника, у которого .

21. Какое кодирование называется эффективным?

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

---

Дискретный канал, в котором передаваемые сообщения представлены двоичным кодом, называется двоичным каналом. Если код имеет m символов (разрядов), то очевидно, что всего можно закодировать n = 2^m сообщений, а длительность одного сообщения составит T = m, где  – длительность символа кода с учетом того, что все символы обычно имеют одинаковую длительность. Двоичные коды, состоящие из одинакового числа символов m, называются равномерными. Пропускная способность рассматриваемого канала с учетом формул (3.1), (3.2) и (3.3) составит

. (3.4)

Выражение (3.4) принимает максимальное значение, когда энтропия ансамбля событий (сообщений) H(Y_T) будет наибольшей. Из свойств энтропии следует, что H(Y_T) будет максимальна, если сообщения равновероятны, это максимальное значение может быть определено мерой Хартли и будет равно log n = log 2^m = m.

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

Возможность построения эффективных кодов согласуется с основной теоремой Шеннона для дискретного канала без помех.

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

Обратное утверждение состоит в том, что невозможно обеспечить передачу всех сообщений источника, у которого .

К эффективным относится, в частности, код Шеннона.-.Фано, пригодный для кодирования статистически независимых сообщений.

22. Построение кода Шеннона-Фано

Рассмотрим построение кода Шеннона.-.Фано для источника сообщений х₁, х₂, х₃, х₄, приведенных в примере 2. Использование равномерного кода для этих сообщений, как отмечалось ранее, не позволяет обеспечить максимальную скорость передачи информации. Покажем, что с помощью кода Шеннона.-.Фано рассматриваемые сообщения можно передать с максимальной скоростью, равной пропускной способности двоичного канала. Кодирование сообщений в этом случае иллюстрируется табл. 3.1, которая составлена следующим образом.

Записывают сообщения в порядке убывания их вероятностей.

Таблица 3.1

Сообще-ние xi	Вероят- ность р(хi)	Номер деления на подгруппы			Символ кода			Длительность кодовой комбинации i
					Позиции
		1	2	3	1	2	3
х1	0,5				0				1
х2	0,25				1	0			2
х3	0,125				1	1	0		3
х4	0,125				1	1	1		3

Проводят первое деление всех сообщений на две подгруппы I и II так, чтобы сумма вероятностей сообщений в подгруппах I и II была бы по возможности одинаковой. В данном случае это условие выполняется точно: при первом делении в подгруппу I входит сообщение х₁, вероятность которого равна 0,5, а в подгруппу II входят сообщения х₂, х₃, х₄, сумма вероятностей которых (0,25 + 0,125 + 0,125) будет тоже составлять 0,5.

---

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

Номер подгруппы, в которую попадает данное сообщение при каждом делении, определяет символ на соответствующей позиции кода этого сообщения. В рассматриваемой таблице принадлежность к подгруппе I обозначается символом 0, а к подгруппе II – символом 1. Так, в частности, первое деление дало на первой позиции кода для сообщения x₁ символ 0, а для остальных сообщений – символ 1.

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

Для наглядности в табл. 3.2 для сообщений х₁, х₂, х₃, х₄ приведены неравномерный код Шеннона - Фано и равномерный, используемый ранее в примерах 1 и 2. Анализируя неравномерный код Шеннона.-.Фано, можно убедиться в том, что наиболее вероятному сообщению соответствует самая короткая кодовая комбинация, наименее вероятному – длинная. Этим можно объяснить увеличение скорости передачи информации при использовании данного кода.

Таблица 3.2

Сообщение xi	Код Шеннона - Фано	Равномерный код
x1	0	00
x2	10	01
x3	110	10
x4	111	11

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

Для вычисления скорости передачи информации при использовании кода Шеннона.-.Фано воспользуемся формулой (3.2), применительно к которой, как и в примере 2, Н(Х) = 1,75, .

Как отмечалось ранее, код Шеннона.-.Фано является неравномерным. Поэтому целесообразно отыскать среднюю длительность сигнала _с одного сообщения, определяемую по формуле математического ожидания длительности _i сообщения x_i [по аналогии с энтропией Н(Х)]:

.

Для выбранного примера по табл. 3.1 (n = 4) находим _с = 1,75, что позволяет считать кодовую комбинацию состоящей в среднем из m = 1,75 символа.

По формуле (3.2) для полученных значений Н(Х) и _с находим скорость передачи:

.

Таким образом, в данном примере код Шеннона - Фано позволил полностью согласовать статистические характеристики источника сообщений с каналом связи, поскольку скорость передачи информации оказалась равной пропускной способности канала: .

---

Равномерный код, как отмечалось в примере 2, не является эффективным. Это можно объяснить тем, что при использовании эффективного кода Шеннона.-.Фано сигнал каждого сообщения в среднем состоит из 1,75 символа, а при использовании равномерного кода – из 2-х (табл. 3.2), из чего следует, что в единицу времени сообщений, представленных кодом Шеннона.-.Фано, будет передано больше, чем при использовании равномерного кода.

Необходимо заметить и то, что, действуя по правилу построения кода Шеннона.-.Фано для четырех равновероятных сообщений, рассмотренных в примере 1, получаем приведенный в табл. 3.2 равномерный код, который в данном случае является эффективным.

Нарушение условия формирования кода Шеннона.-.Фано, заключающегося в том, что наиболее вероятному сообщению должна соответствовать наиболее короткая кодовая комбинация, неизбежно приведет к снижению скорости передачи информации.

Для иллюстрации изложенного поменяем местами кодовые комбинации для сообщений х₁ и х₄ (см. табл. 3.1). Тогда по формуле математического ожидания средняя длительность сообщения увеличится и составит , а скорость передачи информации

Проследим еще, что дают различные способы кодирования на примере 3.

Пример 3. Источник сообщений описывается как

.

Коррелятивные связи между сообщениями отсутствуют. Передача информации производится по двоичному каналу. Длительность символов кодированного сигнала равна . Определим скорость передачи информации при использовании равномерного кода и кода Шеннона - Фано.

Используя (1.6), находим

или

.

Согласно (3.2) скорость передачи информации равна

.

При равномерном коде для передачи каждого сообщения придется израсходовать два символа (табл. 3.3).

Таблица 3.3

Сообщение	Код
x1	00
x2	01
x3	10

Очевидно, что в этом случае и, следовательно,

,

^{где– пропускная способность данного канала.}

Для построения кода Шеннона - Фано составлена табл. 3.4.

Таблица 3.4

Сообще-ние	Вероят- ность	Номер деления на подгруппы			Символ кода			Длительность сигнала
		1	2		1	2	3
х1	0,7				0				1
х2	0,2				1	0			2
х3	0,1				1	1			2

Средняя длительность сигнала при этом будет

.

Скорость передачи информации в этом случае равна

.

Как видим, переход к более эффективному коду позволяет ^{увеличить скорость передачи информации враза.}

Эффективность кодирования может быть еще увеличена, если от кодирования одиночных сообщений перейти к кодированию последовательностей (групп) сообщений (табл. 3.5).

Таблица 3.5

Сооб-щение	Вероят- ность	Деление на подгруппы						Код		Длитель- ность сигнала
х2х2 х1х2 х2х1 х2х3 х3х2 х1х1 х1х3 х3х1 х3х3	0,49 0,14 0,14 0,07 0,07 0,04 0,02 0,02 0,01								0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1		 3 3 4 4 4 5 6 6

---

В табл. 3.5 дано построение кода Шеннона.-.Фано для случая передачи всех возможных пар сообщений.

Средняя длительность сигнала, обеспечивающего передачу одного сообщения, в этом случае будет

.

Соответствующая скорость передачи сообщений равна

.

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

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

Заметим еще, что описанный метод построения эффективного кода Шеннона.-.Фано может быть распространен и на коды с основанием больше двух.

Рассмотренные примеры построения эффективных кодов согласуются с основной теоремой Шеннона для дискретного канала без помех. Теорема формулируется следующим образом: если поток информации , вырабатываемой источником, равен Н(Х) = С_с – , где  – сколь угодно малая величина, то всегда можно найти такой способ кодирования, который обеспечивает передачу всех сообщений, вырабатываемых источником, причем скорость передачи = С_с –  .

Обратное утверждение состоит в том, что невозможно обеспечить передачу всех сообщений источника, у которого .

Вопрос 23.

Пропускная способность (цифровых) каналов

с шумами

Для дискретного канала с шумами (рис. 3.1) количество информации, содержащейся в последовательности выходных сигналов Z_T о входных сигналах Y_T, cоставит:

I(Z_T,Y_T) = H(Z_T) – H(Z_T /Y_T) = H(Y_T) – H(Y_T /Z_T) , (3.5)

где H(Z_T /Y_T) и H(Y_T /Z_T) – условные энтропии.

Для последовательности сообщений длительностью Т, содержащей m сигналов источника, имеем

H(Z_T)= mH(Z), (3.6)

где H(Z) – энтропия выходного сигнала или энтропия выхода канала, рассматриваемого как эргодический источник.

Аналогично для условной энтропии выхода канала запишем:

H(Z_T /Y_T) = mH(Z/Y). (3.7)

Тогда из (3.5)  (3.7) находим

I(Z_T,Y_T) = mH(Z) – mH(Z/Y) . (3.8)

Скорость передачи в дискретном канале с шумами с учетом (3.8) составит

, (3.9)

где – средняя длительность сигнала одного сообщения.

Аналогично с учетом (3.5) найдем

. (3.10)

В равенстве (3.10) – поток информации на выходе кодирующего устройства, характеризует потерю информации, обусловленную действием помех.

Из соотношений (3.9) и (3.10) пропускная способность канала может быть определена из условия

.

Вопрос 24.  Приведите модель двоичного канала с шумами

В качестве примера рассмотрим двоичный канал связи без памяти. Каналами без памяти называются такие каналы, у которых на каждый передаваемый сигнал (символ) шум действует независимо от того, какие символы передавались ранее. Длительности передаваемых символов двоичного кода у₀ и у₁ («0» и «1») примем одинаковыми и равными , следовательно, _с=.

---

Смотрите также файлы

• Навч.посібник Акушерство, гінекологія та штучне осіменіння с.г. тварин, Харута, 2013.pdf

• Ветеринарне акушерство, Яблонський, 2006.pdf

• МЕДИКО-тактическая характеристика очагов.docx

• Этика ДО Экзамен Ответы.docx

• 1.3 Формы общественной организации производсива.docx