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

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 равна: