|
|
Рабочая тетрадь 1. Рабочая тетрадь 1
3. Задания
|
1.
|
Задача:
|
|
Используя кодирование с избытком, закодируйте следующее сообщение: 00111011, троированием битов.
|
Решение:
|
|
|
Ответ:
|
|
000000111111111000111111
|
2.
|
Задача:
|
|
В предположении, что в трех идущих подряд битах не может быть более одной ошибки, восстановите следующее сообщение: 001011010110011010001111 .
|
Решение:
|
|
001 011 010 110 011 010 001 111
|
Ответ:
|
|
01011001
|
3.
|
Задача:
|
|
В сообщении троировались байты (символы таблицы ASCII). Было получено следующее сообщение:
CCzoYomdmppSuRutptweeQrr__*RssacciBieeenn%Fccjee .
Восстановите исходное сообщение.
|
|
Решение:
|
|
CCz oYo mdm ppS uRu tpt wee Qrr __* Rss acc iBi eee nn% Fcc jee
|
Ответ:
|
|
Computer_science
|
1. Теоретический материал
|
Определим расстояние между символами кода. Пусть каждый символ кодируется последовательностью из N битов  . Расстояние  определим следующей формулой [1]:
где  и  принимают значения ноль или единица. Представленная формула позволяет определить расстояние между представлениями символов в виде кода. Тогда n количество ошибок, которые можно исправить, если определить наименьшее из расстояний d определяется по следующей формуле:
d ≥ 2n + 1.
Обобщим, идея метода состоит в определении количество отличных битов в кодовом представлении символов. Далее из всех выбирается наименьшее значение – это значение с использованием формулы d ≥ 2n + 1, позволяет найти количество ошибок, которые можно исправить. То есть, чтобы исправлять  ошибок, необходимо учитывать расстояние между любыми символами, которое должно быть не меньше  .
|
2. Пример
|
1.
|
Задача:
|
|
Даны следующие коды:
|
буква
|
A
|
B
|
C
|
код
|
00000
|
11100
|
00111
|
|
Найти расстояние между кодами для B и C.
|
Решение:
|
|
Посчитаем количество различных бит в кодах для B и C . Четыре бита различны.
|
|
|
|
Ответ:
|
|
|
2.
|
Задача:
|
|
Сколько ошибок можно исправить при использовании кодов из предыдущего примера?
|
Решение:
|
|
Найдём минимальное расстояние  между кодами.
A
|
0
|
0
|
0
|
0
|
0
|
|
B
|
1
|
1
|
1
|
0
|
0
|
|
C
|
0
|
0
|
1
|
1
|
1
|
B
|
1
|
1
|
1
|
0
|
0
|
|
C
|
0
|
0
|
1
|
1
|
1
|
|
A
|
0
|
0
|
0
|
0
|
0
|
|
|
|
|
|
 → 
Из этого условия найдем . Получим  . Таким образом, всегда можно исправить 1 ошибку.
|
Ответ:
|
|
Можно гарантированно исправить 1 ошибку
|
3. Задания
|
1.
|
Задача:
|
|
Даны следующие коды:
|
буква
|
A
|
B
|
C
|
код
|
0101010
|
1010100
|
0011110
|
|
Найти расстояние между кодами для B и C.
|
Решение:
|
|
1010100
0011110
0110101
|
Ответ:
|
|
3
|
2.
|
Задача:
|
|
Верны ли следующие утверждения:
 ,
 ,
 ?
|
Решение:
|
|
P(A, B) = P(1010100, 0011110) = 3
1010100
0011110
P(A, C) = P(0101010, 0011110) = 3
0101010
0011110
P(B, C) = P(1010100, 0011110) = 3
1010100
0011110
|
Ответ:
|
|
Да
|
3.
|
Задача:
|
|
Сколько ошибок можно гарантированно исправить при использовании кодов из задачи1?
|
Решение:
|
|
D = min(3, 3, 3) = 3
3 >= 2n + 1
N = 1
|
Ответ:
|
|
1
|
Тест 1
|
0.
|
Сколько бит в 1 Кбайт?
|
|
1. 8192 бит 2. 75699 бит
3. 4589 бит 4. 34773 бит
|
Ответ: 1
|
|
|
2.
|
Сколько бит нужно отвести на кодирование одной игральной карты стандартной колоды из 36 карт?
|
|
1. 4 2. 5 3. 6 4. 7
|
Ответ: 3
|
|
|
3.
|
Сколько бит нужно отвести на кодирование двузначного десятеричного числа?
|
|
1. 6 2. 7 3. 8 4. 9
|
Ответ: 2
|
|
128 > 90
|
4.
|
Если не прогуливать занятия, то вероятность сдать сессии на «хорошо» и «отлично» равна 0,7. Найдите энтропию системы.
|
|
1. -0,05 2. 0,91 3. 0,13 4. 0,88
|
Ответ: 4
|
|
Энтропия сдачи = 0.361
Энтропия несдачи = 0.521
|
5.
|
Укажите ASCII код символа G
|
|
1. 67 2. 43 3. 6A 4. 47
|
Ответ: 4
|
|
|
6.
|
Бит четности служит для
|
|
1. исправления ошибок в данных
2. обнаружения ошибки в данных
3. шифрования данных
4. выравнивания данных
|
Ответ: 2
|
|
|
7.
|
Если при пересылке сообщения в нём произошло ДВЕ ошибки, то бит четности
|
|
1. позволит исправить две ошибки
2. позволит их обнаружить
3. не позволит их обнаружить
4. позволит исправить только одну ошибку
|
Ответ: 3
|
|
|
8.
|
В предположении, что в трех идущих подряд битах не может быть более одной ошибки, восстановите следующее сообщение: 001011101010100000001110 .
|
|
1. 01100001 2. 01101101
3. 11100001 4. 01000011
|
Ответ: 1
|
|
001 011 101 010 100 000 001 110
01100001
|
9.
|
Найдите, между какими кодами расстояние наибольшее
|
|
1. 11100010 и 00001111 6
2. 00010111 и 01110101 3
3. 01011010 и 10110101 7
4. 10101010 и 10101101 3
|
Ответ: 3
|
|
|
10.
|
Иконка на рабочем столе имеет разрешение 32x32 пикселя. На кодирование каждого пикселя отводится 24 бита. Найдите сколько бит нужно отвести на кодирование одной иконки.
|
|
1. 54576 бит
2. 32679 бит
3. 16384 бит
4. 24576 бит
|
Ответ: 4
|
|
| |
|
|
Скачать 374.5 Kb.