Курсовая работа по «Основам сбора, передачи и обработки информации»

Министерство образования и  науки Украины

Национальный технический университет  Украины

«Киевский Политехнический Институт»

Кафедра автоматики и управления в  технических системах

 

 

Курсовая работа

По дисциплине  «Основы сбора, передачи и обработки информации»

 

Руководитель     Исполнитель

Букасов М.М.     ст. Оконский И.В.

зач. книжка № ИА-7115

гр. ИА-71

«Допущен к защите»

___________________

(личная подпись руководителя)

                        _______________________

«____» _____________ 2009 г.                (подпись исполнителя)

Защищен с оценкой    «___» ____________ 2009г.

__________________________

          (оценка)

«____» _____________ 2009 г.

 

Члены комиссии:

_______________________                      _________________________

       (Личная подпись)                                  (Расшифровка подписи)

_______________________                      _________________________

       (Личная подпись)                                   (Расшифровка подписи)

                                           

Киев-2009

Содержание

 

ВВЕДЕНИЕ

Информация (от лат. informatio – осведомление, разъяснение, изложение) – в широком смысле абстрактное понятие, имеющее множество значений, в зависимости от контекста. В узком смысле этого слова – сведения (сообщения, данные) независимо от формы их представления. В настоящее время не существует единого определения термина информация. С точки зрения различных областей знания, данное понятие описывается своим специфическим набором признаков. Например, «информация» может трактоваться, как совокупность данных, зафиксированных на материальном носителе, сохранённых и распространённых во времени и пространстве.

Клод Шеннон подразумевает под термином информация нечто фундаментальное (нередуцируемое), то есть категорию. Интуитивно полагается, что информация имеет содержание. Информация уменьшает общую неопределённость и информационную энтропию, доступна измерению. Согласно Шеннону, «информация» – это некоторые новые для нас знания (ведения) об окружающем или внутреннем мире.

Согласно данному определению, вполне очевидно, что, как человек, так  и все его творения, постоянно  вовлечены в процессы поиска информации и обмена ею. В виду этого встаёт вопрос представления информации в некотором виде, пригодном и удобном для использования как человеком, так техникой, для представления информации, её хранения, передачи и сохранения в подлинном виде. Данные вопросы как раз и являются предметом такой области как «Основы хранения, передачи и обработки информации», целью которой является поиск оптимальных способов решения поставленных выше задач.

С представлением, хранением и передачей  информации неразрывно связан термин «кодирование» - процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки. Этот процесс являет собой представление информации символами, знаками, взятыми из определенного алфавита по определённым правилам.

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

 

ПОСТАНОВКА  ЗАДАЧИ

1. Исходные данные: ФИО студента (ФИО – 3 первые большие буквы русского алфавита) – переводим комбинацию букв в 24 бита ASCII  (таблицу брать в учебнике стр.121) → получаем ФИО в цифровом коде.
2. Простейшие коды. Кодировать и декодировать ФИО следующими кодами:

1. Двоично-десятичные (два разных кода по весам). Рассчитать избыточность
2. Код Грея. Показать уменьшение веса ошибки

3. Статистическое кодирование.

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

Закодировать полученный в п.1 алфавит кодами:

1. Шеннона-Фано
2. Хаффмана. Построить кодовое дерево

Для а) и б) доказать расчетами  оптимальность кодов.

Закодировать в новых алфавитах ФИО студента и сравнить с результатом п.І.

4. Коды, обнаруживающие ошибки с подсчетом избыточности. Показать процедуру кодирования и декодирования ФИО следующими кодами:

1. С проверкой на четность

2. С проверкой на нечетность
3. Инверсный код
4. Корелляционный код
5. Код Бергера
6. Код на одно сочетание

7. Код с количеством единиц в кодовых комбинациях, кратным трём.

5. Коды, исправляющие ошибки: закодировать, внести ошибку и исправить ее при декодировании.

1. Код Варшамова в матричном представлении

2. Код Хэмминга (2 первых буквы ФИО)
3. Расширенный код Хэмминга
4. Итеративный код
5. Коды-спутники (для 1-й буквы ФИО и d_min = 1,2)
6. Циклический код с d_min = 3
7. БЧХ (для 21 первых битов ФИО)
8. Рекуррентный

6. Канальные коды:

1. Дуобинарный
2. Квазитроичный
3. Манчестер II
4. 4B3T

7. Закодировать и представить в графическом виде штрих-код EAN-8 десятичного числа, содержащего последовательно: число, месяц и год рождения.

8. Разработать программу работы кодера или декодера для кода, согласованного с руководителем, на любом алгоритмическом языке.

 

РЕШЕНИЕ ПО РАЗДЕЛАМ

1. Исходные данные

Оконский Илья Вячеславович

ASCII-коды символов ФИО:

О – 11101111

И – 11101001

В – 11110111

Следовательно, исходная кодовая комбинация ФИО в цифровом коде:

111011111110100111110111

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Простейшие коды

2.1. Двоично-десятичные коды

Краткие теоретические сведения

В двоично-десятичном коде (ДДК) каждая десятичная цифра представляется группой цифр, состоящей из 4-х  двухпозиционных символов. Данная группа позволяет сформировать N = 2⁴ = 16 кодовых комбинаций. Так как в десятичной системе используется лишь десять цифр, шесть комбинаций являются избыточными. Поэтому выбор десяти используемых для построения ДДК комбинаций имеет 16! · 6! = 2.9 · 10¹⁰ вариантов. Использование, например, первых четырех степеней цифры 2 (2⁰ = 1; 2¹ = 2; 2² = 4; 2³ = 8) приводит к одному из возможных кодов 8-4-2-1.

Каждый разряд ДДК  имеет постоянный вес. ДДК строятся с учетом следующих условий:

1. Вес наименьшей значащей цифры q₁ равен 1.
2. Вес второй по минимальному значению цифры q₂ составляет 1 или 2.
3. Веса, соответствующие двум оставшимся цифрам кода, подбирают так, чтобы их сумма была больше или равна 6 (если q₂=2), или 7 (если q₂ = 1).

В соответствии с этим можно получить 17 видов кодов:

8-4-2-1,	7-4-2-1,	6-4-2-1,	5-4-2-1,	4-4-2-1,
7-3-2-1,	6-3-2-1,	5-3-2-1,	4-3-2-1,	3-3-2-1,
6-2-2-1,	5-2-2-1,	4-2-2-1,	6-3-1-1,	5-3-1-1,
4-3-1-1,	5-2-1-1.

Для перевода одной десятичной цифры в двоично-десятичный код, необходимо, начиная со старшего двоичного  разряда, проверить, не больше ли вес  текущей (двоичной) цифры остатка числа; если меньше или равен – то в выходной код записать 1 и вычесть вес двоичной цифры из остатка числа, иначе в выходной код записать 0.

 

Кодирование

Исходная кодовая комбинация, которую необходимо закодировать:

111011111110100111110111,

представим её в десятичном виде:

15 722 999.

Выберем две комбинации ДДК:  7-4-2-1,  4-3-1-1.

	7-4-2-1	4-3-1-1
1	0·7+0·4+0·2+1·1	0·4+0·3+1·1+0·1
5	0·7+1·4+0·2+1·1	1·4+0·3+1·1+0·1
7	1·7+0·4+0·2+0·1	1·4+1·3+0·1+0·1
2	0·7+0·4+1·2+0·1	0·4+0·3+1·1+1·1
2	0·7+0·4+1·2+0·1	0·4+0·3+1·1+1·1
9	1·7+0·4+1·2+0·1	1·4+1·3+1·1+1·1
9	1·7+0·4+1·2+0·1	1·4+1·3+1·1+1·1
9	1·7+0·4+1·2+0·1	1·4+1·3+1·1+1·1

Закодированное число  будет иметь вид:

ДДК	Закодированное число
7-4-2-1	0001 0101 1000 0010 0010 1010 1010 1010
4-3-1-1	0010 1010 1100 0011 0011 1111 1111 1111

 

Декодирование

Декодируем полученные кодовые комбинации:

0001 0101 1000 0010 0010 1010 1010 1010

0010 1010 1100 0011 0011 1111 1111 1111

зная, что они закодированы в  двоично-десятичных кодах 7-4-2-1 и 4-3-1-1 соответственно.

 

7-4-2-1		4-3-1-1
0·7+0·4+0·2+1·1=	1	0·4+0·3+1·1+0·1=	1
0·7+1·4+0·2+1·1=	5	1·4+0·3+1·1+0·1=	5
0·7+1·4+0·2+1·1=	7	1·4+1·3+0·1+0·1=	7
0·7+0·4+1·2+0·1=	2	0·4+0·3+1·1+1·1=	2
0·7+0·4+1·2+0·1=	2	0·4+0·3+1·1+1·1=	2
1·7+0·4+1·2+0·1=	9	1·4+1·3+1·1+1·1=	9
1·7+0·4+1·2+0·1=	9	1·4+1·3+1·1+1·1=	9
1·7+0·4+1·2+0·1=	9	1·4+1·3+1·1+1·1=	9

Декодированное число:

15 722 999.

Избыточность

Избыточность рассчитывается по формуле

, (1)

где r – количество избыточных данных,

n – длина кодовой комбинации.

В нашем случае:

(длина кодовой комбинации, закодированной  двоично-десятичным кодом),

(k – количество символов в исходной комбинации),

следовательно, избыточность:

2.2. Код Грея

Краткие теоретические сведения

Отражённые (рефлексные) коды строятся таким образом, что  соседние кодовые комбинации, в отличие  от простых двоичных кодов, различаются  цифрой только в одном разряде, т.е. кодовое расстояние между соседними кодовыми комбинациями такого кода равно единице. Из отражённых кодов наибольшее распространение получил код Грея.

Преобразование простого двоичного кода в код Грея производится по алгоритму: Y_n = X_n; Y_i = X_i xor X_i+1 , (xor – суммирование по модулю 2), где Y_i – значение i-го разряда кода Грея; X_i, X_i+1 – соответствующие значения разрядов двоичного числа (i = 1, 2, ..., n, считая разряд с i = 1 – младшим, i = n - старшим). Т.е., для всех разрядов, кроме младшего, значение кода Грея равно сумме по модулю 2 соответствующего и следующего более старшего разрядов двоичного кода. Самый старший разряд сохраняется.

Декодирование (обратное преобразование) кода Грея в двоичный код осуществляют по следующей формуле: X_n = Y_n; X_i = X_i+1 xor Y_i, где X_n и Y_n – значения старшего разряда двоичного кода и кода Грея соответственно (i = n-1, n-2, ..., 1, считая разряд с i = 1 – младшим, i = n – старшим).

1. Старший разряд переносится в декодированную последовательность без изменений.
2. Следующий разряд получаются суммированием по модулю 2 соответствующего и всех более старших разрядов закодированного сообщения – при 8-ми разрядном сообщении для декодирования 4-го разряда необходимо сложить по модулю 2 разряды 4, 5, 6, 7 и 8 кодовой комбинации.

Кодирование

Кодовая комбинация, которую необходимо закодировать:

111011111110100111110111.

Y₂₄ = X₂₄ = 1 Y₁₂ = X₁₂ xor X₁₃ = 1

Y₂₃ = X₂₃ xor X₂₄ = 0 Y₁₁ = X₁₁ xor X₁₂ = 1

Y₂₂ = X₂₂ xor X₂₃ = 0 Y₁₀ = X₁₀ xor X₁₁ = 0

Y₂₁ = X₂₁ xor X₂₂ = 1 Y₉ = X₉ xor X₁₀ = 1

Y₂₀ = X₂₀ xor X₂₁ = 1 Y₈ = X₈ xor X₉ = 0

Y₁₉ = X₁₉ xor X₂₀ = 0 Y₇ = X₇ xor X₈ = 0

Y₁₈ = X₁₈ xor X₁₉ = 0 Y₆ = X₆ xor X₇ = 0

Y₁₇ = X₁₇ xor X₁₈ = 0 Y₅ = X₅ xor X₆ = 0

Y₁₆ = X₁₆ xor X₁₇ = 0 Y₄ = X₄ xor X₅ = 1

Y₁₅ = X₁₅ xor X₁₆ = 0 Y₃ = X₃ xor X₄ = 1

Y₁₄ = X₁₄ xor X₁₅ = 0 Y₂ = X₂ xor X₃ = 0

Y₁₃ = X₁₃ xor X₁₄ = 1 Y₁ = X₁ xor X₂ = 0

Закодированная кодовая  комбинация:

1001 1000 0001 1101 0000 1100.

 

Декодирование

Декодируем полученную кодовую комбинацию:

1001 1000 0001 1101 0000 1100.

X₂₄ = Y₂₄ = 1

X₂₃ = Y₂₄xorY₂₃ = 1

X₂₂ = Y₂₄xorY₂₃xorY₂₂ = 1

X₂₁ = Y₂₄xorY₂₃xorY₂₂xorY₂₁x = 0

X₂₀ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀ = 1

X₁₉ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉ = 1

X₁₈ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈ = 1

X₁₇ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇ = 1

X₁₆ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆ = 1

X₁₅ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅ = 1

X₁₄ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆ xorY₁₅xorY₁₄ = 1

X₁₃ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃ = 0

X₁₂ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂ = 1

X₁₁ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁ = 0

X₁₀ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁ xorY₁₀ = 0

X₉ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁ xorY₁₀ xorY₉ = 1

X₈ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁ xorY₁₀ xorY₉xorY₈ = 1

X₇ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁ xorY₁₀ xorY₉xorY₈ xorY₇ = 1

X₆ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁ xorY₁₀ xorY₉xorY₈ xorY₇xorY₆ = 1

X₅ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁ xorY₁₀ xorY₉xorY₈ xorY₇xorY₆xorY₅ = 1

X₄ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁ xorY₁₀ xorY₉xorY₈ xorY₇xorY₆xorY₅xorY₄ = 0

X₃ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁ xorY₁₀ xorY₉xorY₈ xorY₇xorY₆xorY₅xorY₄xorY₃ = 1

X₂ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁ xorY₁₀ xorY₉xorY₈ xorY₇xorY₆xorY₅xorY₄xorY₃xorY₂ = 1

X₁ = Y₂₄xorY₂₃xorY₂₂xorY₂₁xorY₂₀xorY₁₉xorY₁₈xorY₁₇xorY₁₆xorY₁₅xorY₁₄xor Y₁₃xorY₁₂xorY₁₁xorY₁₀xorY₉xorY₈xorY₇xorY₆xorY₅xorY₄xorY₃xorY₂xor Y₁ = 1

Декодированное сообщение:

1110 1111 1110 1001 1111 0111.

Иллюстрация уменьшения веса ошибки

1. Внесем ошибку в исходную кодовую комбинацию в 4й слева разряд:

1111 1111 1110 1001 1111 0111,

и найдем вес ошибки, отняв от искаженной комбинации исходную:

w = 1111 1111 1110 1001 1111 0111 – 1110 1111 1110 1001 1111 0111=

= 1 0000 0000 0000 0000 0000₂ = 1 048 576₁₀.

2. Внесем ошибку в эту же кодовую комбинацию, но закодированную кодом Грея, в 4й слева разряд:

1000 1000 0001 1101 0000 1100,

декодируем искаженную кодовую комбинацию:

111100000001011000001000

1111 0010 0001 0100 0001 0010,

и найдем вес ошибки, отняв от декодированной искаженной комбинации исходную:

w_Гр = 1111 0000 0001 0110 0000 1000- 1110 1111 1110 1001 1111 0111=

= 10 1100 0001 0001₂ = 11 281₁₀.

3. Сравним веса ошибок при искажении исходного сообщения и при искажении этого же сообщения, закодированного кодом Грея:

1 048 576₁₀ > 11 281₁₀,

то есть: w > w_Гр.

4. Вывод: при искажении данных, закодированных кодом Грея, вес ошибки уменьшается по сравнению с весом ошибки при аналогичном искажении исходного двоичного кода.

 

3. Статическое  кодирование

3.1. Количество информации и энтропия

Краткие теоретические сведения

Количество информации является апостериорной  характеристикой и определяет количество информации, которое получают после приема сообщений. Если p_i – вероятность i-ого сообщения, то индивидуальное количество информации:

 (2)

Энтропия – это средняя величина неопределенности состояния источника  сообщения. Является объективной характеристикой источника сообщений, и, если известна статистика сообщений, может быть определена априорно, т.е до получения сообщений.

 (3)

Анализ источника

Для текста, составленного из полного  написания моих фамилии, имени и  отчества и фамилии, имени и отчества моих родителей посчитем вероятности появления букв p_i (прописную и строчную буквы будем считать одной), количество информации в символах I_i и энтропию источника H по соответствующим формулам. Вероятности появления букв будем рассчитывать следующим образом:

, (4)

где n_i - количество i-той буквы в тексте,

n - общее количество букв в тексте

Исходный текст:

Оконский Илья Вячеславович

Оконский Вячеслав Анатолиевич

Оконская Наталия Сергеевна,

количество букв в данном тексте:

.

По формулам (4) и (2) рассчитаем искомые  величины для каждой буквы и представим их значения в виде таблицы.

Таблица 1

Значения количества в исходном тексте, вероятностей появления и  количества информации для каждой буквы  алфавита.

Буква	ni	pi	Ii
о	8	0,1067	3,2288
к	6	0,0800	3,6439
н	6	0,0800	3,6439
с	6	0,0800	3,6439
и	7	0,0933	3,4215
й	2	0,0267	5,2288
л	5	0,0667	3,9069
ь	1	0,0133	6,2288
я	5	0,0667	3,9069
в	7	0,0933	3,4215
ч	4	0,0533	4,2288
е	6	0,0800	3,6439
а	8	0,1067	3,2288
т	2	0,0267	5,2288
р	1	0,0133	6,2288
г	1	0,0133	6,2288

Рассчитаем по формуле (3) энтропию источника сообщений и получим  следующее значение:

 

3.2. Код Шеннона-Фано

Краткие теоретические сведения

Основной принцип, положенный в основу кодирования по методу Шеннона-Фано, заключается в том, что при выборе каждой цифры кодовой комбинации следует стремиться к тому, чтобы содержащееся в ней количество информации было наибольшим. Т.е. чтобы независимо от значений всех предыдущих цифр эта цифра принимала оба возможных для нее значения (0 или 1) по возможности с одинаковой вероятностью. Разумеется, количество цифр в различных обозначениях при этом различно, т.е. данный код является неравномерным. Сообщениям, имеющим большую вероятность, соответствуют короткие кодовые комбинации, имеющие меньшую вероятность – более длинные кодовые комбинации.

Кодовые комбинации строятся следующим образом:

1. Сообщения и их вероятности записываются в таблицу и сортируются по убыванию по вероятностям.
2. Таблица делится на две части так, чтобы суммы вероятностей в обеих частях были бы наиболее близки. Если получается два варианта разбиения, для которых одинаково близки  суммы вероятностей, различное для них сообщение относится к верхней подгруппе.
3. В верхней подтаблице в качестве старшего бита кодового слова записывается 0, в нижней – 1.
4. Деление подтаблиц по п.2 повторяется рекурсивно до получения окончательных кодовых комбинаций (количество сообщений в подтаблице станет равным 1).

Кодирование

Закодируем полученный в п. 3.3.1. алфавит кодом Шеннона-Фано.

 

Таблица 2

Иллюстрация кодирования  нашего алфавита кодом Шеннона-Фано

Буква	pi	Шаги кодирования							Конечная кодовая комбинация
		I	II	III	IV	V	VI	VII
о	0,1067	0	0	0					000
а	0,1067	0	0	1					001
и	0,0933	0	1	0	0				0100
в	0,0933	0	1	0	1				0101
к	0,08	0	1	1	0				0110
н	0,08	0	1	1	1				0111
с	0,08	1	0	0	0				1000
е	0,08	1	0	0	1				1001
л	0,0667	1	0	1	0				1010
я	0,0667	1	0	1	1				1011
ч	0,0533	1	1	0	0				1100
й	0,0267	1	1	0	1				1101
т	0,0267	1	1	1	0				1110
ь	0,0133	1	1	1	1	0	0		111100
р	0,0133	1	1	1	1	0	1		111101
г	0,0133	1	1	1	1	1			11111

Кодирование ФИО

Закодируем в данном алфавите мое ФИО кодом Шеннона-Фано.

Исходный текст:

ОИВ;

кодовые комбинации для  букв:

О – 000,

И – 0100;

В - 0101

тогда закодированное ФИО:

00001000101.

Кодовая комбинация ФИО, закодированная кодом Шеннона-Фано, имеет длину 13 бит, а закодированная цифровым кодом – длину 24 бита, то есть ФИО в коде Шеннона-Фано приблизительно в два раза короче ФИО в цифровом коде.

Доказательство оптимальности кода

Докажем, что код Шеннона-Фано является оптимальным кодом.

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

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

, (5)

где l_i – длина кодовой комбинации i-го закодированного символа первичного алфавита,

p_i – вероятность появления i-го символа алфавита.

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

По формуле (5) найдем среднюю  длину кодовой комбинации для  нашего алфавита (количество символов алфавита n = 16), закодированного кодом Шеннона-Фано, и получим следующее значение:

,

то есть в среднем на один символ нашего алфавита приходится 3,8531 двоичных символов.

Количество символов нашего алфавита n = 16. Следовательно, длина кодовой комбинации равномерного двоичного кода, которым можно закодировать наш алфавит, будет равняться 4, поскольку таким кодом можно закодировать алфавит, максимальное количество символов которого будет равняться 2⁴ = 16.

Это означает, что необходимая  длина кодовой комбинации равномерного двоичного кода больше средней длины  кодовой комбинации Шеннона-Фано.

2. Сравним энтропию источника первичного ансамбля сообщений A (нашего алфавита) с энтропией этого же источника при кодировании его ансамбля сообщений кодом Шеннона-Фано.

Рассчитанная ранее по формуле (3) энтропия источника первичного ансамбля сообщений A равна: