Stanislav Kondrashov kzdailyreport.com.




Розділ 1. КОДУВАННЯ ІНФОРМАЦІЇ ТА ПЕРЕТВОРЕННЯ КОДІВ.
Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. При цьому перші 3 цифри відповідають цілій частині числа, а останні - дробовій.
Вважаючи це число десятковим, перевести його до шістнадцяткової, вісімкової та двійкової систем числення з точністю відповідно 3, 3 та 5 розрядів після коми.
Кодова таблиця (В-4)
Таблиця 1.1.1

Друга цифра
Перша цифра


2
4
7
5
3
1

7
А
Б
В
Г
Д
Е

9
Є
Ж
З
И
І
Ї

6
Й
К
Л
М
Н
О

8
П
Р
С
Т
У
Ф

1
Х
Ц
Ч
Ш
Щ
Ю

3
Я
Ь





За допомогою кодової таблиці четвертого варіанту (таблиця 1.1.1) ставимо у відповідність першим 8 різним літерам власного прізвища (при необхідності ? ім’я та по-батькові) двозначні числа, при цьому літери не можуть повторюватись.
СОРОКЕВИЧ МАКСИМ ІГОРОВИЧ


Кодова таблиця
Таблиця 1.1.2

С
О
Р
К
Е
В
И
Ч

78
16
48
46
17
77
59
71

Таким чином визначаємо 8 двозначних кодів, які відповідають 8 літерам, і заносимо їх у таблицю 1.1.2.
Запишемо складене з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища шестизначне число: X(10) = 781.671
Переводимо його до шістнадцяткової системи. Спочатку цілу частину:
:16

781


48
13

3
0

0
3


X(16)ціл = 30D.
*16


671

A
736

B
776

C
416

6
656

Тепер переводимо дробову частину:
Після округлення до трьох знаків після
коми, отримаємо:
X(16)дроб = 0.ABC
Отже наше число, переведене в шістнадцяткову систему матиме вигляд:
X(16) = 30D.ABC
Переводимо число з шістнадцяткової системи до двійкової методом тетрад, а методом тріад – до вісімкової (таблиця 1.1.3).
Таблиця переведення
Таблиця 1.1.3

шістнадцяткова
3
0
D
A
B
C

двійкова
0
0
1
1
0
0
0
0
1
1
0
1
1
0
1
0
1
0
1
1
1
1
0
0

вісімкова
1
4
1
5
5
2
7
4

Отже отримане вісімкове число, округлене до трьох розрядів після коми має вигляд:
X(8) = 1415.530
Двійкове число, округлене до п’яти розрядів після коми:
X(2) = 1100001101.10101
Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. При цьому перші 3 цифри відповідають цілій частині числа, а останні – дробовій.
Вважаючи це число шістнадцятковим, перевести його до десяткової, вісімкової та двійкової систем числення з точністю відповідно 3, 3 та 5 розрядів після коми.
Число в шістнадцятковій системі: X(16) = 781.671
1.2.1. Переведення до десяткової системи числення:
X(10) = 162*7 + 161*8 + 160*1 + 16-1*6 + 16-2*7 + 16-3*1(1921.403
X(10 )= 1921.403
1.2.2. Переведення до двійкової системи числення способом тетрад (таблиця 1.2.1).
(16) ( (2)
Таблиця 1.2.1

7
8
1
6
7
1

0
1
1
1
1
0
0
0
0
0
0
1
0
1
1
0
0
1
1
1
0
0
0
1

X(2) = 11110000001,01101
1.2.3. Переведення до вісімкової системи чисення способом тріад (таблиця 1.2.2).
(2) ( (8)
Таблиця 1.2.2

0
1
1
1
1
0
0
0
0
0
0
1
0
1
1
0
0
1
1
1
0
0
0
1

3
6
0
1
3
1
6
1

X(8) = 3601.316
Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. Вважаючи це число десятковим, перевести його до системи числення залишкових класів із мінімально необхідною кількістю основ 2, 3, 5, 7, 11, ... . Після цього зробити зворотне переведення отриманого результату до десяткової системи числення.
Складене число: X(10) = 781671
Базис: {2,3,5,7,11,13,17,19}
1.3.1. Переведення числа з десяткової системи числення до системи числення залишкових класів (СЗК):
1. 781671/2=390835, залишок [1];
2. 781671/3=260557, залишок [0];
3. 781671/5=156334, залишок [1];
4. 781671/7=111667, залишок [2];
5. 781671/11=71061, залишок [0];
6. 781671/13=60128, залишок [7];
7. 781671/17=45980, залишок [11];
8. 781671/19=41140, залишок [11];
Отже X(СЗК)=(1,0,1,2,0,7,11,11).
1.3.2. Зворотне переведення в десяткову систему числення:
Знаходимо Р=2*3*5*7*11*13*17*19=9696960.
Знаходимо ортогональні базиси Вn і перевіряємо їх на ортогональність:
Bn=(mk*P)/Pn (1.3.1),
де mk?послідовні цілочисельні значення, починаючи від 1.
В1=9699690/2=4849845; перевірка: 4849845/2=2424922, залишок [1]. В1 =4849845
В3=2*9699690/5=3879876; перевірка: 3879876/5=775975, залишок [1]. В3 =3879876
В4=6*9699690/7=8314020; перевірка: 8314020/7=1187717, залишок [1]. В4 =8314020
В6=5*9699690/13=3730650; перевірка: 3730650/13=286973, залишок [1]. В6 =3730650
В7=16*9699690/17=9129120; перевірка: 9129120/17=537607, залишок [1]. В7 =9129120
В8=18*9699690/19=9189180; перевірка: 9189180/19=483641, залишок [1]. В8 =9189180
Тоді:
Х(10)=(1*4849845+1*3879876+2*8314020+7*3730650+11*9129120+11*9189180)mod 9699690
Х(10)=252973611 mod 9699690=781671
Отже 1,0,1,2,0,7,11,11(СКЗ)= 781671(10)
Виконати ефективне кодування визначених літер прізвища, при умові, що отримане за допомогою кодової таблиці число - десяткове і говорить про те, скільки разів у „повідомленні” зустрічається дана літера (при цьому, „повідомлення” складається всього з 8 обраних літер).
Визначити ефективність проведеного кодування та порівняти її з ентропією джерела повідомлення і ефективністю рівномірного кодування, тобто з випадком, коли довжина коду для кожної літери одна й та сама. За допомогою отриманих кодів скласти „повідомлення”, яке складається з визначених літер у тій послідовності, в якій вони зустрічаються у прізвищі. Визначити довжину (в бітах) „повідомлення” при ефективному і рівномірному кодуванні.
Записуємо до таблиці 1.4.1 коди літер (кількість у „повідомленні”) та імовірності їх появи у „повідомленні”. Імовірність визначаємо за формулою: Pi = Ki/(
Таблиця імовірностей
Таблиця 1.4.1

Літера
С
О
Р
К
Е
В
И
Ч
(

Кількість (Кi)
78
16
48
46
17
77
59
71
412

Імовірність появи (Pi)
78/412=
=0.189
16/412=
=0.039
48/412=
=0.117
46/412=
=0.112
17/412=
=0.041
77/412=
=0.187
59/412=
=0.143
71/412=
=0.172
1

Таблиця ефективного кодування
Таблиця 1.4.2

Літера
Імовірність
Ефективний код
Неефективний код

ai
Pi
код
Ni
код
Ni

С
0.189
00
2
000
3

В
0.187
01
2
001
3

Ч
0.172
100
3
010
3

И
0.143
101
3
011
3

Р
0.117
1100
4
100
3

К
0.112
1101
4
101
3

Е
0.041
1110
4
110
3

О
0.039
1111
4
111
3


Тепер присвоюємо кожній літері власний ефективний код (таблиця 1.4.2).
Формула для визначення ентропії:
8
H = -?(Рі*log2Рі) (1.4.1)
i=1
Визначаємо ентропію джерела за формулою 1.4.1:
H = 0.45427+0.45433+0.43680+0.40125+0.36216+0.35374+0.18894+0.18253 = 2.074
Середня довжина коду літери при ефективному кодуванні:
8
Lсер.еф. = ?(Рі*Nі) (1.4.2)
і=1
Lсер.еф. = 0.189*2+0.187*2+0.172*3+0.143*3+0.117*4+0.112*4+0.041*4+0.039*4 = 2.933 > H
Коефіцієнт відносної ефективності: Кеф.=Н?Lсер.еф. (1.4.3)
Кеф.=2.074/2.933=0.7071
Середня довжина коду літери при неефективному кодуванні:
8 8
Lсер.нееф.=? pini = 3·?pi (1.4.4)
і=1 i=1
Lсер.нееф. = 3*1 = 3 > Lсер.еф. > H
Коефіцієнт відносної ефективності (при неефективному кодуванні):
Кнееф.=H/Lсер.нееф. (1.4.5)
Кнееф.= 2.074/3=0.6913
Кеф.>Кнееф.
Кількість біт у „повідомленні” з ефективним кодуванням:
Mеф. = 78*2+77*2+71*3+59*3+48*4+46*4+17*4+16*4 = 1208.
Кількість біт у „повідомленні” з неефективним (рівномірним) кодуванням:
Mнееф. = 78*3+77*3+71*3+59*3+48*3+46*3+17*3+16*3 = 1236.
Для шістнадцяти розрядного двійкового коду (1ц1л)(2ц1л)(1ц8л)(2ц8л) сформувати код Геммінга (Hamming) і продемонструвати його реакцію на однократний збій. Результати подати у вигляді таблиці.
Код Геммінга розроблено для максимальної достовірності передачі інформації. Він належить до кодів, які дозволяють виправляти помилки, що виникають при пересиланні інформації.
При пересиланні інформації до k інформаційних розрядів додається r перевірочних розрядів так, що загальна довжина n слова, яке пересилається, становить n=k+r.
Позиції, на яких розміщуємо перевірочні розряди знаходяться за формулою:
Ri = 2і (1.5.1),
де і = 0, 1, 2, 3, 4...)
Двійкове число, для якого треба сформувати код: Х(2)=0111 1000 0111 0001
Знаходимо перевірочні позиції: 20=1, 21=2, 22=4, 23=8, 24=16
Отже, перевірочними будуть позиції: 1, 2, 4, 8, 16. Тому загальна довжина коду становитиме 21 розряд.
Формуємо код Геммінга. Спочатку обчислюємо перевірочні розряди:
r1 = k1 # k2 # k4 # k5 # k7 # k9 # k11 # k12 # k14 # k16 = 0 # 1 # 1 # 1 # 0 # 0 # 1 # 1 # 0 # 1 = 0;
r2 = k1 # k3 # k4 # k6 # k7 # k10 # k11 # k13 # k14 = 0 # 1 # 1 # 0 # 0 # 1 # 1 # 0 # 0 = 0;
r3 = k2 # k3 # k4 # k8 # k9 # k10 # k11 # k15 # k16 = 1 # 1 # 1 # 0 # 0 # 1 # 1 # 0 # 1 = 0;
r4 = k5 # k6 # k7 # k8 # k9 # k10 # k11 # r15 = 1 # 0 # 0 # 0 # 0 # 1 # 1 = 1;
r5 = k12 # k13 # k14 # k15 # k16 = 1 # 0 # 0 # 0 # 1 = 0.
Отриманий код Геммінга зображено у таблиці 1.5.1.
Код Геммінга
Таблиця 1.5.1

n1
n2
n3
n4
n5
n6
n7
n8
n9
n10
n11
n12
n13
n14
n15
n16
n17
n18
n19
n20
n21

0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
1
1
1
1
0
0
0
0
1
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
0
1

r1
r2
k1
r3
k2
k3
k4
r4
k5
k6
k7
k8
k9
k10
k11
r5
k12
k13
k14
k15
k16

0
0
0
1
1
1
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1


Припустимо, що під час передачі в 6-ому розряді відбувся збій – число взяте в дужки. Це показано в таблиці 1.5.2.
Код Геммінга
Таблиця 1.5.2

n1
n2
n3
n4
n5
n6
n7
n8
n9
n10
n11
n12
n13
n14
n15
n16
n17
n18
n19
n20
n21

0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
1
1
1
1
0
0
0
0
1
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
0
1

r1
r2
k1
r3
k2
k3
k4
r4
k5
k6
k7
k8
k9
k10
k11
r5
k12
k13
k14
k15
k16

0
0
0
1
1
(0)
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1


Перевірочні розряди R, сформовані приймачем, такі:
R1 = k1 # k2 # k4 # k5 # k7 # k9 # k11 # k12 # k14 # k16 = 0 # 1 # 1 # 1 # 0 # 0 # 1 # 1 # 0 # 1 = 0;
R2 = k1 # k3 # k4 # k6 # k7 # k10 # k11 # k13 # k14 = 0 # 0 # 1 # 0 # 0 # 1 # 1 # 0 # 0 = 1;
R3 = k2 # k3 # k4 # k8 # k9 # k10 # k11 # k15 # k16 = 1 # 0 # 1 # 0 # 0 # 1 # 1 # 0 # 1 = 1;
R4 = k5 # k6 # k7 # k8 # k9 # k10 # k11 # R15 = 1 # 0 # 0 # 0 # 0 # 1 # 1 = 1;
R5 = k12 # k13 # k14 # k15 # k16 = 1 # 0 # 0 # 0 # 1 = 0.
Схема порівняння порозрядно порівнює коди R і r за допомогою операції додавання за модулем 2:
R # r = (R5 # r5)(R4 # r4)(R3 # r3)(R2 # r2)(R1 # r1) = (0 # 0)(1 # 1)(1 # 0)(1 # 0)(0 # 0) = 00110.
Отримуємо код 110(2)=6(10). Цей код показує, що в 6-ому розряді відбувся збій.
Для послідовності 16-кових цифр
(1ц1л)(2ц1л)(1ц2л)(2ц2л)(1ц3л)(2ц3л)...(2ц7л)(1ц8л)(2ц8л), користуючись картами Карно, визначити всі можливі помилкові коди, які можуть виникати при переході від цифри до цифри.
Послідовність виникнення помилкових кодів залежить від того, який з двійкових розрядів змінюється першим. Загалом, якщо 2 коди відрізняються n двійковими розрядами, то помилкових проміжних станів буде 2n-2,
а їхніх можливих послідовностей – (1.6.2).
Виявляти помилкові проміжні стани зручно за допомогою карт Карно. Якщо 2 коди відрізняються на n розрядів, то потрібні нам шляхи пролягатимуть через n-1 клітинок карти Карно.
Карта Карно
Таблиця 1.6.1

0
1
3
2

4
5
7
6

С
D
F
E

8
9
B
A

Послідовність шістнадцяткових цифр:
7 > 8 > 1 > 6 > 4 > 8 > 4 > 6 > 1 > 7 > 7 > 7 > 5 > 9 > 7 > 1
7-3-1-0-8
7-5-1-0-8
7-6-2-0-8
7-F-B-9-8

7-3-1-9-8
7-5-1-9-8
7-6-2-A-8
7-F-B-A-8

7-3-2-0-8
7-5-4-0-8
7-6-4-0-8
7-F-D-9-8

7-3-2-A-8
7-5-4-C-8
7-6-4-C-8
7-F-D-C-8

7-3-B-9-8
7-5-D-9-8
7-6-E-A-8
7-F-E-A-8

7-3-B-A-8
7-5-D-C-8
7-6-E-C-8
7-F-E-C-8


1) 7 > 8:
0111 > 1000
Змінюються 4 розряди (n=4).
Послідовностей: 24
14 помилкових проміжних станів:
0, 1, 2, 3, 4, 5, 6, 9, A, B, C, D, E, F.
0
1
3
2

4
5
7x
6

С
D
F
E

8x
9
B
A

0
1x
3
2

4
5
7
6

С
D
F
E

8x
9
B
A


2) 8 > 1
8-0-1

8-9-1

1000 > 0001
n=2. Послідовностей: 2.
2 помилкових проміжних стани: 0, 9.
0
1x
3
2

4
5
7
6x

С
D
F
E

8
9
B
A


1-0-2-6
1-3-7-6

1-0-4-6
1-5-4-6

1-3-2-6
1-5-7-6

3) 1> 6
0001 > 0110
n=3. Послідовностей: 6
6 помилкових проміжних станів: 0, 2, 3, 4, 5, 7.
0
1
3
2

4x
5
7
6x

С
D
F
E

8
9
B
A


4) 6> 4
0110 > 0100 – n=1 – помилкових станів немає.
0
1
3
2

4x
5
7
6

С
D
F
E

8x
9
B
A

5) 4 > 8
4-0-8

4-C-8

0100 > 1000
n=2. Послідовностей: 2
2 помилкових проміжних стани: 0, C.
0
1
3
2

4x
5
7
6

С
D
F
E

8x
9
B
A

6) 8 > 4
8-0-4

8-C-4

1000 > 0100
n=2. Послідовностей: 2
2 помилкових проміжних стани: 0, C.
0
1
3
2

4x
5
7
6x

С
D
F
E

8
9
B
A


7) 4> 6
0100 > 0110 – n=1 – помилкових станів немає.
0
1x
3
2

4
5
7
6x

С
D
F
E

8
9
B
A

6-2-0-1
6-4-5-1

6-2-3-1
6-7-3-1

6-4-0-1
6-7-5-1

8) 6> 1
0110 > 0001
n=3. Послідовностей: 6
6 помилкових проміжних станів: 0, 2, 3, 4, 5, 7.
0
1x
3
2

4
5
7x
6

С
D
F
E

8
9
B
A

1-3-7

1-5-7

9) 1 > 7
0001 > 0111
n=2. Послідовностей: 2
2 помилкових проміжних стани: 3, 5.
10) 7 > 7 – n=0.
0
1
3
2

4
5x
7x
6

С
D
F
E

8
9
B
A

11) 7 > 7 – n=0.
12) 7 > 5
0111 > 0101 – n=1 – помилкових станів немає.
0
1
3
2

4
5x
7
6

С
D
F
E

8
9x
B
A

13) 5 > 9
5-1-9

5-D-9

0101 > 1001
n=2. Послідовностей: 2
2 помилкових проміжних стани: 1, D.
9-1-3-7
9-B-F-7

9-1-5-7
9-D-5-7

9-B-3-7
9-D-F-7


0
1
3
2

4
5
7x
6

С
D
F
E

8
9x
B
A

14) 9 > 7
1001 > 0111
n=3. Послідовностей: 6
6 помилкових проміжних станів: 0, 2, 3, 4, 5, 7.
0
1x
3
2

4
5
7x
6

С
D
F
E

8
9
B
A

15) 7 > 1
7-3-1

7-5-1

0111 > 0001
n=2. Послідовностей: 2
2 помилкових проміжних стани: 3, 5.

Stanislav Kondrashov kzdailyreport.com.