Содержание
Часть 1.Теория информации
1. Системапередачи дискретных сообщений
1.1 Схемадискретного канала, функции блоков, источника и приемника
1.2 Видыинформации
2. Канальнаяматрица (КМИ; КМП; КМО) и их взаимосвязь
2.1 Свойстваканальных матриц
3. Информационныехарактеристики источника сообщений
3.1 Количествоинформации /> источника
3.2 Информационныепотери />
4. Информационныехарактеристики приемника
4.1 Количествоинформации /> приемника
4.2 Информационныепотери />
5. Скоростныехарактеристики
5.1 Скоростьмодуляции /> симв/сек;
5.2 Производительностьисточника /> бод;
5.3 Скоростьпередачи /> или /> бод;
5.4 Емкостьканала /> или /> бод;
5.5Коэффициент эффективности дискретного канала />;
5.6 ТеоремыШеннона о критической скорости и кодированию
Часть 2. Теориякодирования
6. Оптимальноекодирование. Идея сжатия
6.1 Равномерныйдвоичный код (РДК), корневое бинарное дерево РДК, длина кода РДК, сообщение вРДК
6.2 Оптимальныйнеравномерный код ОНК Шеннона-Фано, алгоритм расчета ОНК, средняя длина,энтропия, коэффициент сжатия, коэффициент эффективности, сообщение в ОНК,критерий Фано, корневое бинарное дерево ОНК Шеннона-Фано
6.3 Оптимальныйнеравномерный ОНК Хаффмана, алгоритм расчета ОНК, средняя длина, энтропия,коэффициент сжатия, коэффициент эффективности, сообщение в ОНК, КБД
6.4 ЭффективностьОНК
7. Помехоустойчивоекодирование. Назначение
7.1 Обнаруживающиекоды
7.1.1Обнаруживающий код четности (ОКЧ)
7.1.2 Обнаруживающийкод удвоения (ОКУ)
7.1.3 Обнаруживающийкод инверсией (ОКИ)
7.1.4 Обнаруживающийкод Стандартный телеграфный код (ОК СТК №3) №3
7.2 Корректирующийсистематический код Хэмминга: генерация, диагностика, коррекция, декодирование
7.3 Корректирующийциклический код: генерация, диагностика, коррекция, декодирование
7.4 Корректирующиймажоритарный код: генерация, диагностика, коррекция, декодирование (другиеназвания – код по голосованию, К-удвоения)
7.5 Эффективностьпомехоустойчивых кодов
8. Криптографическоекодирование. Назначение
8.1 Основыкриптографического кодирования
8.2 Принципыкриптографии по Шеннону
8.3Требования к криптографическим алгоритмам
8.4Криптографическое правило Кирхгофа
8.5 Абсолютностойкий ключ по Шеннону
8.6 Жизненныйцикл конфиденциальности данных
8.7 Критериивзлома ключа
8.8Классификация криптографических методов
Часть 1. Теория информации1. Система передачи дискретных сообщений
Информационные каналы бывают аналоговые (информация в непрерывном виде) ицифровые (дискретные). Широкое развитие получила цифровая техника и дискретныеканалы.
1.1 Схема, функции блоков источника и приемника
Информационную систему передачи данных по каналу связи можно представить крупноблочно (Рис1).
/>
Рис1.Крупноблочное представление информационного канала
Источник сообщения (ИС) – вырабатывает сообщения, кодеры источникапреобразуют сообщения в кодовые слова, используя методы оптимального,помехоустойчивого и криптографического кодирования. Модулятор преобразуетбинарные коды в электрические сигналы.
Линия связи (ЛС) – это физическая среда, в которой распространяютсясигналы: кабельные, радио и спутниковые линии.
Приемник сообщения (ПС) – выполняет обратное превращение: демодуляторпреобразует электрические сигналы в бинарные коды, декодеры выполняютдиагностику и корректирование ошибок, снимают сжатие, помехоустойчивость икриптографическую защиту информации.
/>
Рис.2.Схема системы передачи дискретных сообщений
Функции блоков источника:
· АЦП –алфавитно-цифровой преобразователь (аналоговая информация преобразуется вдискретную);
· Шифратор –устанавливает криптографическую защиту;
· Кодер ОНК (ОНК — оптимальный неравномерный код) — сжимает данные;
· Кодер ПЗК (ПЗК –помехозащищенный код) – устанавливает защиту от помех;
· Модулятор –преобразует цифровую информацию в электрические сигналы;
· Линии связи –телефонные, кабельные, радио, спутниковые.
Функции блоков приемника:
· Демодулятор –преобразует электрические сигналы в двоичный код;
· Декодер ПЗК –определяет наличие ошибки, вычисляет адрес ошибки, корректирует её, снимаетпомехоустойчивую защиту;
· Декодер ОНК –неравномерный код преобразуется в равномерный двоичный код;
· Дешифратор –снимает криптозащиту;
· ЦАП –цифро-аналоговый преобразователь (дискретную информацию преобразовывает внепрерывную).
1.2 Виды информации
В процессе прохождения по каналуинформация многократно меняет свою форму, сохраняя при этом свое содержание:
1) Непрерывнаяинформация;
2) Дискретнаяинформация;
3) Криптокод;
4) Оптимальныйнеравномерный код (двоичный);
5) Помехоустойчивыйкод;
6) Электрическиесигналы.
Расчёт количества информации символов алфавита
Для начала нам необходимо вычислить vi– частоту появления каждого символа алфавита. Сумма vi будет равна длине сообщения ls.
Теперь рассчитываем P(ai)– вероятность появления символа нашего алфавита всообщении.
P(ai) = vi/ls
Сумма таких вероятностей должна быть равна единице.
После этого мы можем найти требуемое количество информации по формуле: I(ai) = — log(P(ai)) [бит]
Свойства количества информации:
1. Количество информации не отрицательно:
I(ai) ≥ 0
2. Чем выше вероятность, тем меньшее количество информации содержитсимвол.
/>
Рис.3. График к свойству 2
3. Если вероятность символа равна 1, то количество информации этогосимвола равно 0:
Р(ai) = 1 ⇒ I(ai) = 0
4. Аддитивность. Количество информации нескольких символов равно суммеколичеств информаций каждого:
I(a1, a2, a3) = I(a1) + I(a2) + I(a3)
Энтропия дискретного ансамбля сообщения
Энтропия – среднее количество информации на символ сообщения.
Расчёт энтропии алфавита
Для вычисления энтропии алфавита нам понадобится lа — количество символов алфавита.
Максимальная энтропия алфавита будет равна:
Hmax(А)= log la [бит/символ]
Причём нужно отметить, что логарифм мы берём по основанию 2.
Расчёт энтропии сообщения
Для нахождения энтропии сообщения нам требуется вычислить такое значение:
H (A) = -∑(P(ai)*logP(ai)) [бит/символ]
Расчёт максимальной энтропии
Максимальную энтропию считаем по формуле:
Hmax(А)= log ls[бит/символ]
Свойства энтропии:
1. Энтропия не отрицательна:
Н(A) ≥ 0
2. Энтропия равна нулю тогда и только тогда, когда вероятность символаравна 1.
Н(A) = 0 ⇔ Р(ai) =1
3. Энтропия ограничена:
H (A) ≤ log ls[бит/символ]
где ls – количество символов в сообщении.
4. Максимальная энтропия равна:
Hmax(А ) = log ls[бит/символ]
/>
Рис.4. График к свойству 4
Расчётная таблица результатов
В данную таблицу мы внесем все наши результаты расчётов и, как результат,построим график количества информации и график энтропии.
S= (Ужизни есть чувство юмора)
А= (У, ж, и, з, н, е, с, т, ь, ч, в, о, ю, м, р, а, .)i
ai
vi
P(ai)
I(ai) H 1 У 2 0,077 3,700 0,285 2 ж 1 0,038 4,700 0,181 3 и 2 0,077 3,700 0,285 4 з 1 0,038 4,700 0,181 5 н 1 0,038 4,700 0,181 6 е 1 0,038 4,700 0,181 7 с 2 0,077 3,700 0,285 8 т 2 0,077 3,700 0,285 9 ь 1 0,038 4,700 0,181 10 ч 1 0,038 4,700 0,181 11 в 2 0,077 3,700 0,285 12 о 2 0,077 3,700 0,285 13 ю 1 0,038 4,700 0,181 14 м 1 0,038 4,700 0,181 15 р 1 0,038 4,700 0,181 16 а 1 0,038 4,700 0,181 17 _ 4 0,154 2,700 0,415 Суммы 26 1,000 3,931
H(А)= log la= log16 = 4 [бит/символ]
Hmax(A)= log22= 4,4594 [бит/символ]
2. Канальные матрицы (КМИ, КМП, КМО) и их взаимосвязь
Канальная матрица определяет действие помех на дискретном канале.
Канальные матрицы бывают трёх видов: канальная матрица источника,канальная матрица приёмника и канальная матрица объединения.
Канальная матрица источника (КМИ)
Канальная матрица источника состоит из условных вероятностей принимаемыхсигналов /> относительно переданныхсигналов />, которые отражают действиепомех на канал.
Эта матрица отражает статистические характеристики действия помех.Канальная матрица источника является матрицей прямых переходов переданныхсигналов /> в принятые сигналы />.
Каждая строка КМИ представляет собой распределение условных вероятностейпринятых сигналов /> относительнопереданных сигналов />. Все этиусловные вероятности p(bj/ai) и образуют КМИ.
/>
Канальная матрица приемника (КМП)
Дискретный канал полностью задан, если известны безусловные вероятностиприема сигналов /> и заданаканальная матрица приемника.
Условные вероятности р(ai /bj) приёма сигналов /> относительно переданныхсигналов /> составляют канальнуюматрицу приемника (КМП) и отражают действие помех на канале.
/>
/>
Канальная матрица объединения (КМО)
Дискретный канал полностью задан канальной матрицей объединения (КМО).
КМО состоит из совместных вероятностей появления сигналов /> и /> - р(ai ,bj) и отражает действие помех на каналесвязи.
Элементами матрицы являются совместные вероятности:
/>
Взаимосвязь канальных матриц
Из КМО в КМИ
p(bi/aj) = /> />
p(ai) = />p(ai,bj)(i=1,2…n)
Из КМИ в КМО
/> />
Из КМО в КМП
p(ai/bj) = /> />
p(bj) = />p(ai,bj) (j=1,2…n)
Из КМП в КМО
p(ai, bj) = p(bj) ·p(ai/bj) />2.1 Свойства канальных матриц
Свойства канальной матрицы источника (КМИ):
1. КМИ – квадратнаяматрица, то есть её размер nxn ;
2. Сумма условныхвероятностей каждой строки равна 1, то есть образует полную группу:
/> (i=1,2…n)
3. Условныевероятности главной диагонали КМИ отражают вероятность правильного приемасигналов /> относительно переданных сигналов />;
4. Остальныеусловные вероятности канальной матрицы (кроме главной диагонали) отражаютвероятность ложного приема переданных сигналов;
5. Для идеальногоканала, на котором нет помех, канальная матрица имеет вид:
/>
Свойства канальной матрицы приемника (КМП):
1. КМП – этоквадратная матрица, то есть её размер nxn ;
2. Сумма условныхвероятностей каждого столбца равна 1, то есть образует полную группу:
/> (j=1,2…n)
3. Условныевероятности главной диагонали КМПотражают вероятность правильного приема сигналов /> относительно переданных сигналов />;
4. Остальныеусловные вероятности канальной матрицы приемника (кроме главной диагонали) отражают вероятность ложного приема переданныхсигналов;
5. Для идеального канала,на котором нет помех, КМП имеет вид:
/>
Свойства канальной матрицы объединения (КМО):
1. Сумма совместныхвероятностей каждой строки равна безусловной вероятности источника:
дискретный матрица приемник кодирование
/> (i=1,2…n)
Σ p(ai) = 1
2. Сумма совместныхвероятностей каждого столбца равна соответствующей безусловной вероятностиприемника:
/> (j=1,2…n)
3. Сумма всехэлементов канальной матрицы объединения равна 1.
/>
Σ p(bj) = 1
3. Информационные характеристики источника сообщений
Для того, чтобы понять что такое информационные характеристики, нужновначале дать определение таким терминам, как алфавит сообщения, кортежупорядоченных уникальных символов и дискретный ансамбль сообщения (ДАС).
Алфавитом сообщения называются символы, которые входят в сообщение.Например:
A={a1, a2,…,an}
Кортеж упорядоченных уникальных символов – это упорядоченнаяпоследовательность символов.
Х={х1, х2,…, хn} – сообщение – кортеж символов
Дискретный ансамбль сообщения (ДАС) – сообщение с вероятностями символов ДАС{Х, p(хi) или A, p(ai)} 3.1 Количество информации /> источникасообщений
Количество информации
Количеством информации символа сообщения определяется:
I(ai) = — log2(p(ai)) = — log(p(ai)) [бит] (i=1,2…n)
В Шенноновской теории информации количество информации источникаопределяется вероятностью появления символа.
I(ai) = — ln(p(ai)) [нат]
I(ai) = — lg(p(ai)) [дит]
Каждый символ сообщения содержит своё количество информации.
Свойства количества информации источника сообщений
1. Количество информации неотрицательно:
I(ai) >= 0
2. Чем выше вероятность, тем меньшее количество информации содержитсимвол.
3. Если вероятность символа равна 1, то количество информации этогосимвола равно 0.
р(ai) = 1 ⇒ I(ai) = 0
4. Аддитивность. Количество информации нескольких символов равно суммеколичеств информаций каждого.
I(a1, a2, a3) = I(a1) + I(a2) + I(a3)
Энтропия – среднее количество информации на символ сообщения(средневзвешенное).
/> [бит/символ]
Свойства энтропии
1. Энтропия неотрицательна: Н(А) ≥ 0
2. Энтропия равна нулю тогда и только тогда, когда вероятность символаравна 1: Н(ai) = 0 ⇔ р(ai) =1
3. Энтропия ограничена: H (ai) ≤ log n[бит/символ]
где n – количество символов в сообщении.
4. Максимальная энтропия равна: Hmax(А) = log n[бит/символ]3.2 Информационные потери />
Существует двавида условной энтропии, которые определяют действия помех на дискретном канале– это частная условная энтропия (ЧУЭ) и общая условная энтропия (ОУЭ).
Частная условная энтропия источника (ЧУЭИ) сообщений отображает количествопотерь информации при передаче каждого сигнала аi:
H(В/аi) = − />p(bj/ai)log p(bj/ai) (i = 1,2…n) [бит/символ]
Общая условная энтропия источника (ОУЭИ) определяет средние потери количестваинформации на принятый сигнал /> относительно переданных сигналов />.
/> [бит/символ]
4. Информационные характеристики приемника сообщений4.1 Количество информации /> приёмника
Количество информации
Количеством информации символа сообщения определяется:
I(bj) = — log2(p(bj)) = — log(p(bj)) [бит] (j=1,2…n)
В Шенноновской теории информации количество информации приемникаопределяется вероятностью появления символа.
I(bj) = — ln(p(bj)) [нат]
I(bj) = — lg(p(bj)) [дит]
Каждый символ сообщения содержит своё количество информации.
Свойства количества информации приемника сообщений
1. Количество информации неотрицательно: I(bj) ≥ 0
2. Чем выше вероятность, тем меньшее количество информации содержитсимвол.
3. Если вероятность символа равна 1, то количество информации этогосимвола равно 0.
р(bj) = 1 ⇒ I(bj) = 0
4. Аддитивность. Количество информации нескольких символов равно суммеколичеств информаций каждого.
I(b1, b2, b3) = I(b1) + I(b2) + I(b3)
Энтропия – среднее количество информации на символ сообщения(средневзвешенное).
/> [бит/символ]
Свойства энтропии
1. Энтропия неотрицательна:
Н(А) ≥ 0
2. Энтропия равна нулю тогда и только тогда, когда вероятность символаравна 1:
Н(ai) = 0 ⇔ р(ai) =1
3. Энтропия ограничена
H (B) =[бит/символ]
где n – количество символов в сообщении.
4. Максимальная энтропия равна
Hmax(B) =log n[бит/символ]/> /> /> /> /> /> /> /> />
4.2 Информационные потери/>
Существует двавида условной энтропии, которые определяют действия помех на дискретном канале– это частная условная энтропия (ЧУЭ) и общая условная энтропия (ОУЭ).
Частная условная энтропия приемника (ЧУЭП) сообщений определяет потериинформации каждого принятого сигнала />.
H(A/ bj) = − />p(ai/bj)log p(ai/ bj) (j = 1,2…n) [бит/символ]
Общая условная энтропия приемника (ОУЭП) определяет средние потериинформации на символ /> при приеме ансамбля {B, p(/>)}:
/> [бит/символ]
5. Скоростные характеристики5.1 Скорость модуляции /> [симв/сек]
/> />[симв/сек],
где /> - длительность передачи одногосигнала
Если длительность передачи сигналов различна, то вычисляется среднеевремя передачи одного сигнала.
/>
5.2 Производительность источника /> бод;Производительность источника — количество бит,вырабатываемых в единицу времени — 1 секунду./> [бод]
5.3 Скорость передачи /> или /> бод;
Скорость передачи источника:
/> [бит/сек], [бод]
Скорость передачи приёмника:
/> [бит/сек], [бод]
5.4 Емкость канала /> или /> бод;
Емкостьканала (пропускнаяспособность канала) — это максимальное
количество бит, передаваемое в единицу времени – секунду.
Пропускная способность – максимальная скорость передачи.
C=maxR
Емкость канала источника:
/> [бит/сек], [бод]
Емкость канала приёмника:
/> [бит/сек], [бод]5.5 Коэффициентэффективности дискретного канала />
Чем больше коэффициент эффективности дискретного канала стремится кединице, тем эффективнее канал и тем меньше информационные потери на нём.
/>
/>5.6 Теоремы Шеннона о критической скорости и кодировании
1) Теорема окритической скорости:
Теорема определяет критическую скорость передачи />, зависящую только отраспределения вероятности, при которой существует способ передачи со скоростьюR (/>), при котором возможновосстановление исходного сообщения (/>), где С– пропускная способность канала, Н(А) – энтропия источника;
2) Теорема окодировании:
Если H’(A) –производительность источника — меньше емкости канала (/>), то существует способ кодирования и декодирования, при которомвероятность ошибки будет сколь угодно мала /> инаоборот.Пример расчёта скоростных характеристик для канальнойматрицы источника.
1. Исходные данные
Дана матрица условных вероятностей, которые отражают действие помехдискретного канала связи.
/>
Сумма вероятностей каждой строки равна 1,00.
Время передачи символа τ = 0,0002 сек. Передано 250 символов.
Безусловные вероятности появления символов на выходе:
p(a1)=0.25, p(a2)=0.35, p(a3)=0.15,p(a4)=0.25
2. Расчёты
1) Количество информации I(ai )каждого символа a1,a2, a3 дискретного сообщения :
/> (i=1,2,3) [ бит]
/> [бит]
/> [бит]
/> [бит]
/> [бит]
2)Среднее количество информации, переданное одним символом определяетэнтропия источника сообщений Н(А):
/> [бит/символ]
H(A) = -(0,25*(-2) + 0,35*(- 1,51) + 0,15*(- 2,73)+ 0,25*(-2) = -(-0,5 — 0,53 – 0,41 – 0,5) = 1,94 [бит/символ]
3)Максимальная энтропия источника сообщений Hmax(A)
Hmax(A)= log N=log 4=2 [бит/символ]
где N-количество символов в алфавите сообщения.
4)Информационные потери при передаче каждого символа ai определяетчастная условная энтропия H(B/ai ):
/> [бит/символ]
H(B/a1 )=-(0,9*(-0,15) + 0,05*(-4,32) + 0,03*(-5,05)+0,02*(-5,64) =
-(-0,1368 – 0,2161 – 0,1518 – 0,1129) = 0,6175 [бит/символ]
H(B/a2 )= -(0,1*(-3,32) + 0,84*(-0,25) + 0,06*(-4,05)+0) =
-(-0,3321 – 0,2112 – 0,2435 – 0) = 0,787 [бит/символ]
H(B/a3 )= -(0+ 0,01*(-6,64) + 0,98*(-0,03)+0,01*(-6,64)) =
-(-0 – 0,0664 – 0,0286 – 0,0664) = 0,1614 [бит/символ]
H(B/a4 )= -(0+ 0 + 0,01*(-6,64)+0,99*(-0,0145)) =
-(-0– 0 – 0,0664 – 0,0144) = 0,081 [бит/символ]
5)Средние потери информации при передаче одного символа определяет общаяусловная энтропия источника Н(B/А):
/>
H(B|A) = 0,25*0,6175 + 0,35*0,787 + 0,15*0,1614 + 0,25*0,081 =0,1543 + 0,2755 + 0,0242 + 0,02 = 0,4743 [бит/символ]
6)Общие потери информации в канале святи при передаче сообщения,состоящего из 250 символов I
I = k H (B / A) = 2500,737476 = 184 [бит]
где k – количество символов в переданном сообщении.
7) Среднееколичество информации, принятое приемником на один символ, определяетсяэнтропией приемника Н(B)
/>[бит/символ]
/>
p(b1) = 0,9*0,25 + 0,35*0,1 + 0 + 0 = 0,225 +0,035 = 0,26
p(b2) = 0,05*0,25 + 0,84*0,35 + 0,01*0,15 +0 =0,0125+0,294+0,0015 =0,35
p(b3) = 0,03*0,25 + 0,06*0,35 +0,98*0,15+0,01*0,25 = 0,0075+0,021+ 0,147+0,0025 = 0,178
p(b4) = 0,02*0,25 + 0 + 0,01*0,15 + 0,99*0,25 =0,005 + 0+0,0015+ 0,2475=0,254
H(B) = -(0,26*(-1,94) + 0,35*(-1,7) + 0,178*(-2,49) +0,254*(-1,97)) = -
-(-0,5 – 0,5234 – 0,4432 – 0,5) = 1,974 [бит/символ]
8) Максимальная энтропия приемника, Hmax(B)
Hmax(B)= log N = log 4=2 [бит/символ]
9)Среднее количество принятой приемником информации, на один символ сучетом потерь информации, I (A, B)
I (A, B) = H (B) – H (B / A) = />-/>= 1,5 [бит/символ]
10) Скорость модуляции дискретного канала, n
n=/>=/>=500 [бод]
11) Продуктивность дискретного канала сообщений, H’(A)
H’(A)=/> [бод]
H’(A) = />= 970,3227 [бод]
12) Скорость передачи информации, R
R = />
R= (1,974- 0,4743)/0,002 = 749,8676 [бод]
13) Пропускная способность (емкость) дискретного канала связиопределяется максимальной скоростью передачи: C=max R
С=/>
C=/>= 762,8716 [бод]
14) Коэффициент эффективности дискретного канала связи Kэ
Kэ=/>=/>=0,9829
15) Критическая скорость передачи Rкр
Rкр=/>=/>= 393,102 [бод]
Оценка надёжности и эффективности дискретного канала связи
1. Оценка теоремыШеннона по скорости
R
749,8676 > 393,102
2. Оценка выполнениятеоремы по кодированию
H’(A)
970,3227 > 762,8716
3. Рекомендации поповышению надёжности и эффективности
Из-за невыполнения теоремы о скорости передачи невозможным становитсявосстановление исходного сообщения. При кодировании и декодировании информациивероятность ошибки может быть сколь угодно велика. Для улучшения эффективностинеобходимо увеличить емкость канала С.
Теоремы Шеннона не выполняются, а значит, наш канал связи не являетсяэффективным и надежным.
Построение канальной матрицы объединения
Найдем безусловные вероятности появления сигналов на входе приемника поформуле:
/>
Зная КМИ можно построить КМО: р(аi,,bj)= p(ai)p(bj/аi)
/>
Построение канальной матрицы приемника
Зная КМО мы можем построить КМП, найдя элементы по формуле :
p(ai / bj)= p(ai,bj)/p(bj)
/>
Часть 2. Теория кодирования6. Оптимальное кодирование. Идея сжатия
Основной характеристикой дискретного канала связи является скоростьпередачи данных. При избыточности переданного сообщения скорость передачиуменьшается. Для исключения избыточности сообщения используют математические ипрограммные средства компрессии данных без потери содержания информации, в томчисле оптимальное кодирование.
Оптимальное кодирование применяют для того, чтобы:
· сжимать данные(компрессия);
· снижать времяпередачи данных при той же скорости передачи;
· уменьшитьвозможные потери и искажения данных;
· архивироватьданные, эффективно использовать память.
Основная идея оптимального кодирования лежит в том, что символамсообщения, которые имеют большую вероятность, присваивают короткие бинарныекоды, то есть образуются бинарные кодовые слова разной длины – неравномерныекоды. Оптимальным неравномерным кодом (ОНК) называется такой код, для которогосредняя длина кода есть минимальной.
Такая идея сжатия была применена в азбуке Морзе, где наиболеевстречающимся символам соответствовали наиболее короткие коды. Сам алфавитсостоял из точек и тире.6.1 Равномерный двоичный код (РДК), корневое бинарноедерево РДК, длина кода РДК, сообщение в РДК
Составление сообщения
Нам дано сообщение:
Х= «Остановите землю, я сойду»
Длина сообщения Lx=24 [символа]
Алфавит сообщения
Найдём алфавит нашего сообщения:
A={о, с, т, а, н, в, и, е, з, м, л, ю, я, с, й, д, у,_. }
Длина алфавита La=21 [символ]
Вероятности
На данном этапе вычисления РДК нам требуется вычислить вероят-ности появлениякаждого символа в алфавите сообщения. Для этого мы воспользуемся формулой:
pi = vi/ ls
где vi- количество раз, которое символвстречается в сообщении.
Сумма vi должна соответствовать длинеисходного сообщения.
Таблица данных, РДК
/>
Таким образом, наше сообщение будет выглядеть:
SРДК=00001000110010001001001100000100111010000010000101000100101000100101011011000110100010011100001000011000001011111000010001
/>
6.1.6 Длина сообщения
Длина сообщения, записанного в РДК равна:
lsрдк = ls· lрдк
где lрдк = 5 бит.
Таким образом, длина сообщения:
lsрдк = 24·5 = 120 бит6.2 Оптимальный неравномерный код ОНК Шеннона-Фано,алгоритм расчета ОНК, средняя длина, энтропия, коэффициент сжатия, коэффициентэффективности, сообщение в ОНК, критерий Фано, корневое бинарное дерево ОНКШеннона-Фано
Расчёт ОНК
Оптимальный неравномерный код (ОНК) мы будем рассчитывать по методу Шеннона-Фано,который ещё называют методом бисекции.
Для вычисления ОНК вся работа разбивается на несколько этапов.
Предварительный шаг: вероятности появления символа в сообщении ранжируютсяпо убыванию.
Шаг первый: все вероятности разбиваются на две равновероятные группы.Символам верхней секции назначим 0, символам нижней секции – 1. Первый бит ОНКвычислен.
Шаг второй: каждую группу делим на две равновероятные подгруппы. Верхнимподгруппам присваивается 0, нижним – 1. и т. д.
Деление заканчивается, когда в подгруппе остаётся один символ.
Нахождение ОНК
/>
Критерий Фано однозначного декодирования ОНК: ни одно слово ОНК неявляется началом другого слова ОНК. Это ещё называется свойством префиксности.
Критерий Фано позволяет однозначно декодировать сжатое сообщение SОНК. Сообщение в ОНК будет выглядеть:
SОНК=111101100101010111111011010110010011000110010011000010000011001010010010011010111100010001100000
/>
Характеристики ОНК
1. Средняя длина ОНК
Lcp.онк= 4.23 [бит]
2. Энтропия ОНК
H(A)= 1,18 [бит/символ]
3. Максимальнаяэнтропия
Hmax= log 17= 4,08[бит/символ]
4. Относительнаяэнтропия
/>
5. Информационнаяизбыточность
/>
6. Абсолютнаянедогруженость
/>
7. Коэффициентсжатия
Кс = 1- Lcp.онк/ LРДК = 0,15 = 15 %
8. Коэффициентэффективности Кэ
Кэ=Н/ Lcp.онк = 0,27
Эффективность ОНК тем выше, чем больше средняя длина ОНК стремится к энтропии.6.3 Оптимальный неравномерный ОНК Хаффмана, алгоритмрасчета ОНК, средняя длина, энтропия, коэффициент сжатия, коэффициентэффективности, сообщение в ОНК, КБД
Расчет ОНК Хаффмена
При расчёте оптимального неравномерного кода Хаффмена нам потребуютсявероятности появления символов в нашем сообщении. Они у нас уже рассчитаны ивыстроены в порядке убывания.
Сам оптимальный неравномерный код Хаффмена мы будем вычислять при помощиалгоритма Хаффмена:
Шаг 1. «Склеиваются» две самых маленьких вероятности.
Шаг 2. В усечённом алфавите снова «склеивают» две самыхмаленьких вероятности.
Объединение вероятностей заканчивается, когда в усечённом алфавитеостаётся лишь одна вероятность.
Критерий Фано
Полученный ОНК Хаффмена обязан обладать свойством пре-фиксности, то естьни одно слово ОНК не должно являться началом другого слова. Критерий Фано позволяетоднозначно декодировать сжатое сообщение.
/>
Cообщениепримет вид:
S=1001101011011111001001010101100011101010011101000100001100010111101111111001100101101000
/>
Характеристики ОНК
1. Средняя длина ОНК
Lcp.онк= 4.23 [бит]
2. Энтропия ОНК
H(A)= 1,18 [бит/символ]
3. Максимальнаяэнтропия
Hmax= log 17= 4,08[бит/символ]
4. Относительнаяэнтропия
/>
5. Информационнаяизбыточность
/>
6. Абсолютнаянедогруженость
/>
7. Коэффициентсжатия
Кс = 1- Lcp.онк/ LРДК = 0,15 = 15 %
8. Коэффициентэффективности Кэ
Кэ=Н/ Lcp.онк = 0,27
Эффективность ОНК тем выше, чем больше средняя длина ОНК стремится кэнтропии.6.4 Эффективность ОНК
Однозначно декодировать ОНК можно с помощью критерия Фано, которыйговорит о свойстве префиксности, которым обладают коды. Благодаря сжатиюинформации возможно значительно сократить исходный код.
Эффективность ОНК можно определить с помощью коэффициента эффективности,то есть чем ближе Кэ стремится к единице, тем эффективнееоптимальный неравномерный код.
ОНК не обладает избыточностью, так как к нему не прикрепляютсяконтрольные биты.
7. Помехоустойчивое кодирование. Назначение
Назначение помехоустойчивого кодирования состоит в защите данных отдействия помех.
Эти коды делятся на две группы:
· Обнаруживающиекоды – коды только обнаруживают ошибки, но не указывают их адрес
· Корректирующиекоды – обнаруживают наличие ошибки, вычисляют адрес ошибки (позицию), в которомпоявился ошибочный бит.7.1 Обнаруживающие коды
Двоичный кодстановится обнаруживающим за счет добавления дополнительных контрольных бит.
Можно назвать следующие обнаруживающие коды: обнаруживающий код четности(ОКЧ), обнаруживающий код удвоения (ОКУ), обнаруживающий код инверсией (ОКИ),обнаруживающий код стандартный телеграфный код № 3 и другие.
7.1.1 Обнаруживающий код четности (ОКЧ)
Данный двоичный код дополняется одним контрольным битом в конце слова.
nи — длинаинформационной части, количество бит.
nк — длина контрольнойчасти.
n=nи + nк — длина слова.
Пример.
Генерация.
Пусть исходное слово 0101.
Макет ОКЧ — 0101К,
где К – контрольный бит, равно сумме по модулю 2 информационных битисходника.
К = 0/>1/>0/>1 = 0
ОКЧ (n; nи )
ОКЧ (5; 4) = 01010
Проверим:
S = 0 />1/>0/>1/>0 = 0 — /> ошибки, то есть ошибки не существуетКоличество ошибок Передано Принято Наличие ошибки Нет ошибок 01010 01010
S = 0, /> ошибки 1 ошибка 01010 11010
S = 1, /> ошибка 2 ошибки 01010 11011
S = 0, /> ошибки 3 ошибки 01010 10011
S = 1, /> ошибка 4 ошибки 01010 10111
S = 0, /> ошибки
Недостаток: ОКЧ позволяет определять наличие ошибки при нечетном ихколичестве и не определяет ошибку при их четном количестве.
Эффективность.
1. Минимальное количество контрольных бит.
2. Просто и удобный алгоритм генерации кода и диагностики (обнаруженияошибок).
7.1.2 Обнаруживающий код удвоения (ОКУ)
Генерация ОКУ.
Пусть исходное сообщение будет 0101.
Макет ОКУ: 0101 К1 К2 К3 К4,
где nи = 0101 и nк = К1 К2 К3 К4, тоесть nи = nк.
Контрольные биты равны соответствующим информационным битам.
ОКУ (8; 4) = 01010101
Диагностика.
При диагностике суммируются по модулю 2 информационная и контрольнаячасти ОКУ.
/>
Во всех остальных случаях ошибка существует.
Передано 01010101.
Принято 00010101.
/>
Эффективность ОКУ.
1. Обнаруживаетлюбое число ошибок и приблизительно указывает адрес ошибки;
2. Простота алгоритмагенерации и диагностики;
3. Недостаток –избыточность, длина контрольной части 100%.
7.1.3 Обнаруживающий код инверсии (ОКИ)
Генерация ОКИ.
Пусть исходное сообщение будет 0101.
Макет ОКИ: 0101 К1 К2 К3 К4,
где nи = 0101 и nк = К1 К2 К3 К4, тоесть nи = nк.
Контрольные биты ОКИ равны инверсии соответствующих бит
информационной части исходника.
ОКУ (8; 4) = 01011010
Диагностика.
При диагностике суммируются по модулю 2 информационная и
контрольная части ОКУ./>
Если S = 1 – ошибка не существует. S=0 — /> ошибка
Передано 01011010.
Принято 10011011.
/>
Эффективность ОКИ.
1. Обнаруживаетлюбое число ошибок и приблизительно указывает адрес ошибки.
2. Простотаалгоритма генерации и диагностики.
3. Недостаткомявляется избыточность, длина контрольной части 100%.
7.1.4 Обнаруживающий код Стандартный телеграфный код (ОК СТК №3) №3
Количество единиц в двоичном коде называется весом кода.
Для всех символов, букв, цифр, спецзнаков разработаны двоичные кодывесом, равным 3 ( т. е. содержат 3 единицы).
Диагностика.
Если в принятом двоичном слове количество единиц равно 3, то ошибки нет.Во всех остальных случаях ошибка есть.
Символ с ошибкой не корректируется, а удаляется.7.2 Корректирующий систематический код Хэмминга: генерация,диагностика, коррекция, декодирование
Генерация КСКХ.
Определим количество контрольных бит и их позиции по формуле:
Пi=2j-1 => kj —> Пi
Отсюда получаем:
для K1, j=1, Пi =21-1=20=1, K1 →П1 ;
для K2, j =2, Пi =22-1=21=2, K2 →П2 ;
для K3, j =3, Пi =23-1=22=4, K3 →П4 ;
для K4, j =4, Пi =24-1=23=8, K4 →П8 ;
Макет КСКХ
nи = 7 бит, nk = 4 бит, n = 7+4 = 11 бит.Позиции
П1
П2
П3
П4
П5
П6
П7
П8
П9
П10
П11 Макет
к1
к2 1
к3 1
к4 1
Определим правила четности Хемминга.
/>
Вычислим значения контрольных бит. Макет КСКХ обработаем правиламичетности, получим уравнения с одной переменной, решив которые, найдем значенияк.
ПЧ1 => к1/>1/>0/>1/>1/>0 = 0. к1/>1= 0 → k1 = 1
ПЧ2 => к2/>1/>0/>1/>0/>0 = 0. к2/>0= 0 → k2 = 0
ПЧ3 => к3/>0/>0/>1= 0. к3/>1= 0 → k3 = 1
ПЧ4 => к4/>0/>0 = 0. к4/>1= 0 → k4 = 1Позиции
П1
П2
П3
П4
П5
П6
П7
П8
П9
П10
П11 Макет
к1
к2 1
к3 1
к4 1 КСКХ 1 1 1 1 1 1
КСКХ(11;7) = 10110011100
Диагностика.
Передан КСКХ: 10110011100
Принят: 10111011100
Обрабатываем КСКХ правилами четности:
ПЧ1 => 1/>1/>0/>1/>1/>0 = 1 → АО=1
ПЧ2 => 0/>1/>0/>1/>0/>0 = 0 → АО=0
ПЧ3 => 1/>1/>0/>1= 1 → АО=1
ПЧ4 => 1/>1/>0/>0= 0 → АО=0
АО=01012=510
АО =П5
Коррекция.
Заключается в инверсии ошибочной позиции П5:1→0
КСКХ(11;7) = 10110011100
Декодирование.
Заключается в удалении контрольных бит: 1001100
Эффективность. Контрольные биты размещаются междубитами исходника. Код содержит минимальное количество контрольных бит иявляется плотноупакованным.7.3 Корректирующий циклический код: генерация, диагностика,коррекция, декодирование
Корректирующий циклический код (КЦК) определяет и корректирует однуошибку. Широко употребляется в станках с числовым программным управлением(ЧПУ).
Контрольные биты размещаются в конце информационной части кода. Значенияконтрольных бит вычисляются с помощью порождающего полинома.
Диагностика наличия ошибки и вычисление её адреса также выполняются спомощью порождающего полинома.
Генерация КЦК.
Дано сообщение:
Л = 1001101
nи = 7 бит
Построим корректирующий циклический код.
Запишем исходник в форме полинома
К = 1001100 /> />=Q(x).
nи= 7 бит, nk = nи+2=9 бит, n = 7+9 = 16 бит.
Макет строится путем сдвига исходника на 9 бит влево
/>=/>
Вычислим значения контрольных бит. Для этого макет поделим на порождающийполином. Порождающим полиномом в нашем случае является:
/>
/>
/>/>/>/>/>/>Запишем корректирующий циклический код:
КЦК(16;7)= />
Диагностика.
Принятый КЦК делится по модуля 2 на порождающий полином.
Наличие и адрес ошибки определяется по остатку m(x):
— если m(x)=0, то ошибки нет.
— ошибка в информационной части, есть m(x) имеет «обрамление».
Адрес ошибки указывает единица внутри обрамления.
— ошибка в контрольной части, если m(x) содержит однуединицу, а
остальные биты равны нулю. Единица указывает адрес ошибки в
контрольной части.
— КЦК содержит более одной ошибки при другой форме остатка m(x).
1. Ошибка в информационной части
Передано 1001100110011001
Принято 1001110110011001/>
/>/>/>/>/>/>
Мы получили обрамление в остатке => АО=П6 (единицавнутри обрамления) и это ошибка в информационной части).
2. Ошибка в контрольной части
Передано: 1001100110011001 Принято: 1001100110010001
/>/>/>
По форме остатка определяем, что ошибка в контрольной части КЦК. Единицауказывает адрес ошибки АО= П13
Коррекция.
Для первого случая: инвертируем ошибочную позицию П6: 1→0. Получаем 1001100110011001.
Для второго случая: инвертируем ошибочную позицию П13 0→1
Получаем 1001100110011001.
Декодирование.
Заключается в отбрасывании контрольных бит. Получаем 1001100.
Эффективность.
1. Определяет икорректирует одну ошибку, широко применяется в станках с ЧПУ.
2. Контрольные битыразмещаются в конце информационной части кода. Значения контрольных битвычисляются с помощью порождающего полинома.
3. Диагностиканаличия ошибки и вычисление ее адреса также выполняется с помощью порождающегополинома.7.4 Корректирующий мажоритарный код: генерация,диагностика, коррекция, декодирование (другие названия – код по голосованию,К-удвоения)
Корректирующий мажоритарный код(КМК) иначе называют кодом по голосованиюлибо кодом удвоения.
Образуется КМК путём добавления к исходнику контрольной части, содержащейК удвоений, где К – нечетное число (К = 3, 5,7…).
Генерация КМК.
Пусть дано сообщение:
К = 1001101
nи = 7 бит
К исходнику добавляется контрольная часть, содержащая к
удвоений (к=3,5,7).
Запишем макет для 3-удвоения:
КМК(21;7)= />
Значения контрольных бит равны соответствующим значениям информационныхбит:
КМК(21;7)= 1001100 1001100 1001100.
Диагностика.
Для каждого инф. бита строится свой синдром. Если в синдроме битыодинаковые, то ошибки нет. Если разные, то ошибка в позиции с «наименьшимчислом голосов».
Передано 1001100 1001100 1001100.
Принято 1101100 1001000 1001101.
Для П1 S1{П1, П8, П15}={1,1,1} =>нет ошибки.
Для П2 S2{П2, П9, П16}={1,0,0}=>есть ошибка, АО=П2
Для П3 S3{П3, П10, П17}={0,0,0}=>нет ошибки
Для П4 S4{П4, П11, П18}={1,1,1}=>нетошибки
Для П5 S5{П5, П12, П19}={1,0,1}=>есть ошибка, АО=П12
Для П6 S6{П6, П13, П20}={0,0,0}=>нет ошибки
Для П7 S7{П7, П14, П21}={0,0,1}=>естьошибка, АО=П21
Для сильно зашумленных каналов применяют 7,9 удвоений.
Коррекция.
Инвертируем ошибочные позиции П2 1→0,
П12 0→1,
П21 1→0;
Получаем 1001100 1001100 1001100.
Декодирование.
Удаляем контрольные биты, получаем 1001100.
Эффективность.
1. Обнаружение икоррекция кратных ошибок;
2. Удобный, простойалгоритм генерации и диагностики;
3. Большаяизбыточность: 200, 400, 500%.7.5 Эффективность помехоустойчивых кодов
Помехоустойчивые коды предлагают простые и удобные алгоритмы генерациикода, диагностики, то есть обнаружения ошибок, а также их коррекции.
В состав помехоустойчивого кода входит определенное количествоконтрольных бит, из-за чего помехоустойчивые коды обладают большойизбыточностью от 100 % до 600%.
8. Криптографическое кодирование (Создатель Клод Шеннон)
Крипта – латинское слово «тайна»
Криптография – тайная запись
Криптология – наука о тайнах состоит из двух частей:
Криптография – создание методов защиты информации от несанкционированногодоступа (НСД);
Криптоанализ – разработка методов «взлома» систем защитыинформации.
Принципы криптографии по Шеннону
1. Перемешиваниеданных.
2. Рассеиваниеданных. Изменение структуры данных
8.1 Требованияк криптографическим алгоритмам
1. Конфиденциальность– секретность;
2. Целостностьданных – нет замен, добавлений и удалений;
3. Аутентичность –подлинность, истинность сообщения и абонента;
4. Неотслеживаемостьинформации. Не устанавливается, кому и от
кого идет сообщение;
5. Оперативностьдоступа для санкционированного пользователя и непреодолимая защита дляостальных;
6. Юридическаязначимость электронного документа обеспечивается электронной цифровой подписью(ЭЦП);
7. Криптостойкостьалгоритма – способность алгоритма противостоять взлому. Обеспечивается ключомшифрования.
Криптографическое правило Кирхгофа
Криптоаналитику известно все (методы шифрования, программное обеспечение,фрагмент или весь шифротекст и т.д.), но не известен ключ шифрования.
Следствие.Ключ определяет криптостойкость алгоритма.
Абсолютно стойкий ключ по Шеннону
1. Длина ключа равнадлине сообщения />;
2. Ключ случайнымобразом выбирается из ключевого пространства;
3. Ключ используетсятолько один раз;
4. Ключ создается наоснове неразрешимой математической задачи, т.е. на основе этого принципа быласоздана открытая криптография (открытый ключ шифрования) и ЭЦП.
8.2 Жизненныйцикл конфиденциальности данных
1. Военная,тактическая информация ………… минуты, часы
2. Средства массовойинформации (СМИ) …...………… сутки
3. Заявления овыпуске товара ………………… неделя
4. Бизнес проект………………………… месяцы, год
5. Производственныесекреты, технологии ………………10 лет
6. Секрет созданияводородной бомбы ………………. 40 лет
7. Информация оразведчиках ………………...…… 50 лет
8. Личная информация………………… более 50 лет
9. Дипломатическаятайна (государственная) …………. 65лет
10. Сведения опереписи населения ………………….… 100 лет
Критерии взлома ключа
1) /> – критерий по времени;
/> – критерий по стоимости;
2) Недостижимыересурсы:
- вычислительныересурсы (быстродействие, емкость памяти);
- объем перехватасообщения, фрагмент шифротекста должен быть достаточно большим;
- неразрешимаяматематическая задача.
8.3 Классификация криптографических методов
Симметричные – шифрование происходит с помощью секретного ключа идешифрование производится с помощью этого же ключа:
1. Поточные методы,т.е. информация шифруется в потоке символ за символом. Шифрование ведется наоснове простых и сложных замен. Существуют:
а) шифр Цезаря;
б) шифр Полибия;
в) шифр «Модульная арифметика»;
г) шифр «Алфавитное сложение»;
д) шифры на основе математических методов.
2. Блочные методы – методы перестановки:
а) шифр сцитала (с греческого – жезл);
б) стандартная перестановка;
в) вертикальная перестановка;
г) комбинированная перестановка;
д) магический квадрат;
е) квадратная и прямоугольная решетки Кордано.
3. Многоалфавитныесистемы:
а) шифр квадрат Вижинера (/>);
4. Шифр DES.
Несимметричные:
1. Открытаякриптография – работает два ключа: ключ секретный (личный), который никому непередается; ключ открытый (общедоступный):
а) RSA и др.;
2. Электроннаяцифровая подпись (ЭЦП);
3. Стеганография –скрывается факт передачи сообщения. Скрытие факта дешифрованного сообщения(решетки, микроточки и т.д.).
Физическая защита вычислительного центра и компьютера:
1. Кодовые замки сантропологическим ключом (отпечаток пальца, сетчатка глаза и т.д.);
2. Скремблеры(криптографический телефон);
3. Генератор шума;
4. Парольная системазащиты компьютера, базы данных.
Применение в комплексе этих методов защиты обеспечивает выполнение требованийкриптографии.