Автор работы: Пользователь скрыл имя, 19 Января 2012 в 14:21, курсовая работа
В этой работе речь пойдет о том, без чего в настоящее время трудно представить какую-либо деятельность. Современный человек на столько
привык к использованию «чудо-техники» в своей повседневной жизни, что вряд-ли задумывается о том, как протекают процессы записи, передачи или хранения информации. Все это основано на понятии кодирования.
Кодирование - это преобразование сообщения в форму, удобную для передачи по каналу связи.
Теория кодирования представляет собой один из разделов дискретной математики, в котором рассматривается процесс представления инфор¬мации в определенной стандартной форме и обратный процесс восстано¬вления информации по этому представлению.
Дискретная математика – одна из областей математики, начала которой возникли в глубокой древности. Основной отличительной чертой её классической математики, которая в основном занимается изучением свойств объектов непрерывного характера с использованием основного понятия – предел, является дискретность, противоположность непрерывности. Предметом дискретной математики является изучение свойств произвольных структур (множеств с операциями, отношения и аксиомами), которые появляются как в самой математике, так и в области её приложений.
Дискретная математика включает в себя такие разделы как теорию чисел, алгебру, математическую логику, теорию графов и сетей, теорию кодирования, комбинаторный анализ и теорию конечных автоматов.
Особенностью дискретной математики является, наряду с задачами типа существования, имеющими общематематический характер, наличие задач, связанных с алгоритмической разрешимостью и построением конкретных решающих алгоритмов. При этом по существу впервые возникла необходимость полного исследования так называемых многоэкстремальных задач.
Введение…………………………………………………………………………..3
§ 1. Базовые понятия теории кодирования……………………………………...5
§ 2. Алфавитное кодирование……………………………………………………9
§ 3. Двоичный алфавит………………………………………………………….14
§ 4. Кодирование и обработка чисел компьютером…………………………...20
§ 5. Решение практических задач……………………………………………..25
Заключение………………………………………………………………………35
Литература……………………………………………………………………….36
Выясните, обладает ли эта схема свойством взаимной однозначности.
Решение.
β = (b2)(b1),
β3 = (b1)(b2b2) = (b1b2)(b2),
β4 = (b2)(b1b2b2) = (b2 b1)(b2b2) = (b2)(b1)(b2b2) = (b2b1b2)(b2),
β5 = (b2)(b2b2b2) = (b2b2)(b2b2) = (b1b2b2)(b2).
β2 = (b2)β1 ˄,
β3 = ˄β1(b2b2),
β4 = (b2)β3˄ = (b2)β1(b2b2) = ˄β2(b2b2),
β5 = (b2) ˄ (b2b2b2) = (b2b2) ˄ (b2b2) = (b2b2b2) ˄ (b2).
Задача 6. Выясните, является ли алфавитное кодирование со схемой ∑ взаимно-однозначным, если:
а) С(∑) = {а, b, aab},
б) С(∑) = {cаd, abc, dcc, abca, abcb }.
˄ ˄
abc ˄ ˄
a) abc
˄
˄
б)
Решение.
а) граф G∑ содержит петлю (˄˄) (рис. а). Код не является однозначно кодируемым. Слово декодируемое неоднозначно:
β = (ааb) = (a)(a)(b).
б) граф G∑ контуров и петель, проходящих через ˄, не содержит (рис. б).
Кодирование является взаимно-однозначным.
Задача 7. Покажите, что алфавитное кодирование с кодирующим алфавитом {0, 1, 2} и множеством кодирующих слов С(∑) = {01, 201, 112, 122, 0112} не является взаимно-однозначным.
Решение. Построим
граф G∑ (рис. выше). Он содержит
контур, проходящий через вершину ˄, следовательно,
кодирование не является взаимно-однозначным,
причём декодируемое слово неоднозначно
β = 0112201.
β1 β1
˄
Тема «Коды Хемминга»
Задача 1. По методу Хемминга постройте кодовое слово для сообщения α = 1011.
Решение. m = 4; 24 ≤ 2l/(l +1); l = 7, k = 3, L = {1, 2, 3, 4, 5, 6, 7}.
| τ i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| V0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| V1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| V2 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
L1 = {i ϵ L1 : V1 = 1}; L1 = {2, 3, 6, 7},
L2 = {i ϵ L2:V2 = 1} L2 = {4, 5, 6, 7}.
b3 = а1 = 1, b5 = а2 = 0, b6 = а3 = 1, b7 = а4 = 1.
b2 = b3 ⊕ b6 ⊕ b7 = 1 ⊕ 1 ⊕ 1 = 1,
b4 = b5 ⊕ b6 ⊕ b7 = 0 ⊕ 1 ⊕ 1 = 0.
Таким образом, кодовым словом для α = 1011 является слово β = 0110011.
Задача 2. По методу Хемминга постройте кодовое слово для сообщения α = 1101.
Решение. m = 4; 24 ≤ 2l/(l +1); l = 7, k = 3, L = {1, 2, 3, 4, 5, 6, 7}.
| τ i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| V0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| V1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| V2 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
L1 = {i ϵ L1: V1 = 1}; L1 = {2, 3, 6, 7},
L2 = {i ϵ L2:V2 = 1} L2 = {4, 5, 6, 7}.
b3 = а1 = 1, b5 = а2 = 1, b6 = а3 = 0, b7 = а4 = 1.
b2 = b3 ⊕ b6 ⊕ b7 = 1 ⊕ 0 ⊕ 1 = 0,
b4 = b5 ⊕ b6 ⊕ b7 = 1 ⊕ 0 ⊕ 1 = 0.
Таким образом,
кодовым словом для α = 1101 является
слово β =1010101.
Задача 3. По методу Хемминга постройте кодовое слово для сообщения α = 011.
Решение. m = 3; 23 ≤ 2l/(l +1); l = 6, k = 3, L = {1, 2, 3, 4, 5, 6}.
| τ i | 1 | 2 | 3 | 4 | 5 | 6 |
| V0 | 1 | 0 | 1 | 0 | 1 | 0 |
| V1 | 0 | 1 | 1 | 0 | 0 | 1 |
| V2 | 0 | 0 | 0 | 1 | 1 | 1 |
L1 = {i ϵ L1: V1 = 1}; L1 = {2, 3, 6},
L2 = {i ϵ L2:V2 = 1} L2 = {4, 5, 6}.
b3 = а1 = 0, b5 = а2 = 1, b6 = а3 = 1.
b2 = b3 ⊕ b6 ⊕ b7 = 0 ⊕ 1 = 1,
b4 = b5 ⊕ b6 ⊕ b7 = 1 ⊕ 1 = 0.
Таким образом, кодовым словом для α = 011 является слово β =110011.
Задача 4. Декодируйте слово β’ = 1001110, где произошла ошибка не более чем в одном разряде.
Решение. Имеем l = 7; 2m ≤ 2l/(l + 1) = 27/8 = 24; m = 4; k = l – m = 7 – 4 = 3;
β’ = b҆1b҆2b҆3b҆4b҆5b҆6b҆7 = 1001110.
Вычислим V = {V0, V1, V2}. Имеем
L0 = {1, 3, 5, 7}; V0 = b1
⊕
b3
⊕
b5
⊕
b7 = 1
⊕
0
⊕
1
⊕
0 = 0,
L1 = {2, 3, 6, 7}; V1 = b2
⊕
b3
⊕
b6
⊕
b7 = 0
⊕
0
⊕
1
⊕
0 = 1,
L2 = {4, 5, 6, 7}; V2 = b4
⊕
b5
⊕
b6
⊕
b7 = 1
⊕
1
⊕
1
⊕
0 = 1.
Получили 110 – это двоичное представление числа 6. Следовательно, ошибка произошла в шестом разряде, значит, β = 1001100. Вычёркивая контрольные разряды 1, 2, 4, получим исходное сообщение α = 0100.
Задача 5. Декодирующее слово β’ = 001011110111111.
Решение.
β҆ = b҆1b҆2b҆3b҆4b҆5b҆6b҆7b҆8b҆9b҆1
l = 15; 2m ≤ 215 /16 ≤ 215/24 = 211 =› m = 11, k = l – m = 15 – 11 = 4.
| τ i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| V0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| V1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| V2 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| V3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Lo = {1, 3, 5, 7, 9, 11, 13, 15},
L1 = {2, 3, 6, 7, 10, 11, 14, 15},
L2 = {4, 5, 6, 7, 12, 13, 14, 15},
L3 = {8, 9, 10, 11, 12, 13, 14, 15}.
V0 = b҆1
⊕
b҆3
⊕
b҆5
⊕
b҆7
⊕
b҆9
⊕
b҆11
⊕
b҆13
⊕
b҆15 = 0
⊕
1
⊕
1
⊕
1
⊕
0
⊕
1
⊕
1
⊕
1 = 0;
V1 = b҆2
⊕
b҆3
⊕
b҆6
⊕
b҆7
⊕
b҆10
⊕
b҆11
⊕
b҆14
⊕
b҆15 = 0
⊕
1
⊕
1
⊕
1
⊕
1
⊕
1
⊕
1
⊕
1 = 1;
V2 = b҆4
⊕
b҆5
⊕
b҆6
⊕
b҆7
⊕
b҆12
⊕
b҆13
⊕
b҆14
⊕
b҆15 = 0
⊕
1
⊕
1
⊕
1
⊕
1
⊕
1
⊕
1
⊕
1 = 1;
V3 = b҆8
⊕
b҆9
⊕
b҆10
⊕
b҆11
⊕
b҆12
⊕
b҆13
⊕
b҆14
⊕
b҆15 = 1
⊕
0
⊕
1
⊕
1
⊕
1
⊕
1
⊕
1
⊕
1 = 1.
Получили 1110. Это
двоичное представление числа 14: ошибка
в 14-м разряде β҆ = b҆1b҆2b҆3b҆4b҆5b҆6b҆7b҆8b҆9b҆1
Вычёркивая разряды 1, 2, 4, 8, получим α = 11110111101.
Заключение
В жизни постоянно приходится сталкиваться с необходимостью кодирования информации, это обуславливается потребностью передачи информации и желанием скрыть смысл передаваемых сообщений от посторонних. В современном мире, мире, где стремительно развиваются телекоммуникационные системы и широко используется вычислительная техника, роль кодирования существенна. На сегодняшний день буквально каждый второй является пользователем компьютера, телефона и в каждом доме есть телевизор – всё это основано на процессе кодирования. И раз уж он так плотно вошёл в нашу жизнь, то было бы совсем неплохо иметь представление о том, что называется кодированием.
В результате проделанной работы: рассмотрена сущность понятия кодирование информации; охарактеризован процесс кодирования и декодирования; представлены примеры и задачи, необходимые для усвоения способов кодирования.
Данная работа может быть использована
для внеклассной работы с учащимися и
для спецкурсов по элементам теории кодирования.
Литература