ТПИ
.docЗадача 1
Задача 2
Задача 3
Задача 4
Алфавит сообщения состоит из 3 символов, появляющихся независимо друг от друга (вероятности появлении символов взять из первой задачи). Составить код Шеннона – Фэно при кодировании по одной и блоками по две и по три буквы. Сравнить эффективности полученных кодов (вычислить их энтропию и среднюю длину кодового слова).
Решение
Для построения кода Шеннона-Фано все сообщения выписываются в порядке убывания их вероятностей. Записанные таким образом сообщения затем разбиваются на две по возможности равновероятные подгруппы. Всем сообщениям первой подгруппы присваивают цифру 1 в качестве первого кодового символа, а сообщениям второй подгруппы – цифру 0. Аналогичное деление на подгруппы продолжается до тех пор, пока в каждую подгруппу не попадёт по одному сообщению.
1. Кодирование по одной
Si |
p(Si) |
1 шаг, группы |
2 шаг, группы |
Кодовые слова |
S3 |
0.7 |
1 |
|
1 |
S1 |
0.2 |
2 |
1 |
01 |
S2 |
0.1 |
2 |
00 |
Энтропия и средняя длина
2. Кодирование по две
S |
p(Si) p(Sj) |
Кодовые слова |
S3S3 |
0.49 |
1 |
S3S1 |
0.14 |
0111 |
S1S3 |
0.14 |
0110 |
S3S2 |
0.07 |
0101 |
S2S3 |
0.07 |
0100 |
S1S1 |
0.04 |
0011 |
S2S1 |
0.02 |
0010 |
S1S2 |
0.02 |
0001 |
S2S2 |
0.01 |
0000 |
3. Кодирование по три
S |
p(Si) p(Sj) p(Sk) |
Кодовые слова |
S3S3S3 |
0.343 |
1 |
S3S3S1 |
0.098 |
0110 |
S3S1S3 |
0.098 |
0101 |
S1S3S3 |
0.098 |
0100 |
S3S3S2 |
0.049 |
0011 |
S3S2S3 |
0.049 |
0010 |
S2S3S3 |
0.049 |
0001 |
S1S1S3 |
0.028 |
0010011 |
S1S3S1 |
0.028 |
0010010 |
S3S1S1 |
0.028 |
0010001 |
S1S2S3 |
0.014 |
0010000 |
S1S3S2 |
0.014 |
0001111 |
S2S1S3 |
0.014 |
0001110 |
S2S3S1 |
0.014 |
0001101 |
S3S1S2 |
0.014 |
0001100 |
S3S2S1 |
0.014 |
0001011 |
S1S1S1 |
0.008 |
0001010 |
S2S2S3 |
0.007 |
0001001 |
S2S3S2 |
0.007 |
0001000 |
S3S2S2 |
0.007 |
0000111 |
S1S1S2 |
0.004 |
0000110 |
S1S2S1 |
0.004 |
0000101 |
S2S1S1 |
0.004 |
0000100 |
S2S2S1 |
0.002 |
0000011 |
S2S1S2 |
0.002 |
0000010 |
S1S2S2 |
0.002 |
0000001 |
S2S2S2 |
0.001 |
0000000 |
Таким образом, разность величин (L0 - Hх) - избыточность кода минимальна для третьего случая – кодирования блоком по три.
Задача 5
Декодировать полученное сообщение С, если известно, что использовался код Хэмминга (4, 7).
n |
С |
2 |
1010011 |
Решение
Позиция бита: |
М4 |
М3 |
М2 |
С3 |
М1 |
С2 |
С1 |
Значение бита: |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
В общем случае код имеет N=M+C бит и предполагается, что не более чем один бит в коде может иметь ошибку. Тогда возможно N+1 состояние кода (правильное состояние и n ошибочных). Пусть М=4, а N=7, тогда слово-сообщение будет иметь вид: M4, M3, M2, C3, M1, C2, C1. Вычислим значения С1, С2, С3. Для этого используются уравнения, где все операции представляют собой сложение по модулю 2:
С1 = М1 + М2 + М4 = 0+1+1=0
С2 = М1 + М3 + М4 = 0+0+1=1
С3 = М2 + М3 + М4 = 1+0+1=0
Для определения того, доставлено ли сообщение без ошибок, вычисляем следующие выражения (сложение по модулю 2):
С11 = С1 + М1 + М2 + М4= 1+0+1+1=1
С12 = С2 + М1 + М3 + М4 = 1+0+0+1=0
С13 = С3 + М2 + М3 + М4 = 0+1+0+1=0
Результат вычисления интерпретируется следующим образом.
С11 |
С12 |
С13 |
Значение |
1 |
2 |
4 |
Позиция бит |
0 |
0 |
0 |
Ошибок нет |
0 |
0 |
1 |
Бит С3 не верен |
0 |
1 |
0 |
Бит С2 не верен |
0 |
1 |
1 |
Бит М3 не верен |
1 |
0 |
0 |
Бит С1 не верен |
1 |
0 |
1 |
Бит М2 не верен |
1 |
1 |
0 |
Бит М1 не верен |
1 |
1 |
1 |
Бит М4 не верен |
Таким образом, бит С1 не верен.
Исправленное сообщение будет иметь вид
Позиция бита: |
М4 |
М3 |
М2 |
С3 |
М1 |
С2 |
С1 |
Значение бита: |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
Задача 6
Закодировать методом гаммирования сообщение, которым является часть фамилии студента из первых 6 букв (если фамилия меньше 6 букв, то дописать именем, например «Крук Юрий»: «КРУК Ю»), представленная в двоичном виде в кодировке ANSI (для одного символа – 8 бит). Гамма шифра вырабатывается конгруэнтным датчиком псевдослучайных последовательностей.
Параметры датчика конгруэнтного датчика ПСЧ: T(0)=7, A=11, C=9.
Решение
Линейный конгруэнтный датчик ПСЧ вырабатывает последовательности псевдослучайных чисел T(i), описываемые соотношением:
Ti+1=(A·Ti+C) mod m,
где А и С – константы, от которых зависит период генерируемой псевдослучайной последовательности; Т0 - исходная величина, выбранная в качестве порождающего числа, m=2s (обычно), где s – длина слова в битах.
Ti+1=(11·Ti+9) mod m,
В нашем случае m=8.
n |
Ti+1 |
Значение Т (дес) |
Значение T(бит) |
T1 |
(11*7+9)mod8 |
6 |
0000 0110 |
T2 |
(11*6+9)mod8 |
3 |
0000 0011 |
T3 |
(11*3+9)mod8 |
2 |
0000 0010 |
T4 |
(11*2+9)mod8 |
7 |
0000 0111 |
T5 |
(11*7+9)mod8 |
6 |
0000 0110 |
T6 |
(11*6+9)mod8 |
3 |
0000 0011 |
Номер буквы |
1 |
2 |
3 |
4 |
5 |
6 |
Исходное сообщение |
К |
У |
Л |
Ь |
Б |
А |
Кодировка |
202 |
211 |
203 |
220 |
193 |
192 |
Код 8-бит |
1100 1010 |
1101 0011 |
1100 1011 |
1101 1100 |
1100 0001 |
1100 0000 |
Ti |
0000 0110 |
0000 0011 |
0000 0010 |
0000 0010 |
0000 0110 |
0000 0011 |
Зашифрованное сообщения |
1100 1100 |
1101 0000 |
1100 1001 |
1101 1110 |
1100 0111 |
1100 0011 |
Сообщение |
204 |
208 |
201 |
222 |
199 |
195 |
Закодированное сообщение |
М |
Р |
Й |
Ю |
З |
Г |