Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Проектування цифрових структур
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Компютерних технологій автоматики та метрології
Факультет:
Комп'ютерна інженерія
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Прикладна теорія цифрових автоматів
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівска політехніка»
Курсова робота
З дисципліни «Прикладна теорія цифрових автоматів»
На тему: «Проектування цифрових структур»
1.1 Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. При цьому перші 3 цифри відповідають цілій частині числа, а останні - дробовій.
Наприклад, Біда Ян Андрійович, 8 перших різних літер для варіанту В1: Б, І, Д, А, Я, Н, Р, Й.
З кодової таблиці маємо:
Б - 52, І - 14, Й - 36.
Число - 521,436.
Вважаючи це число десятковим, перевести його до шістнадцяткової, вісімкової та двійкової систем числення з точністю відповідно 3, 3 та 5 розрядів після коми.
З кодової таблиці маємо:
С - 35; А – 78; Д – 28.
Число: 357,82810.
Переведення в двійкову систему числення:
Переведення цілої частини:
357 / 2 = 178 [1];
178 / 2 = 89 [0];
89 / 2 = 44 [1];
44 / 2 = 22 [0];
22 / 2 = 11 [0];
11 / 2 = 5 [1];
5 / 2 = 2 [1];
2 / 2 = 1 [0];
[1];
35710 = 1011001012
Переведення дробової частини:
0,828
Х
2
1,656
Х
2
1,312
Х
2
0,624
Х
2
1,248
Х
2
0,496
Х
2
0,992
Х
2
1,984
Х
2
1,968
Х
2
1,936
Х
2
1,872
Х
2
1,744
Х
2
1,488
0,82810 = 0,1101001111112
357,82810 = 101100101 ,1101001111112
Переведення в вісімкову систему числення:
101 100 101 , 110 100 111 1112 = 545,64778
*Переведення: розбиття на тріади, починаючи від коми (ліворуч і прворуч), причому у дробовій частині останню тріаду доповнюють нулями при необхідності.
Переведення в шістнадцяткову систему числення:
1 0110 0101 , 1101 0011 11112 = 165,D3F16
*Переведення: аналогічне попередньому методу, тільки розбиваєм на тетради.
357,82810 = 101100101 ,1101001111112 = 545,64778 = 165,D3F16
1.2 Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. При цьому перші 3 цифри відповідають цілій частині числа, а останні - дробовій.
Вважаючи це число шістнадцятковим, перевести його до десяткової, вісімкової та двійкової систем числення з точністю відповідно 3, 3 та 5
розрядів після коми.
Число: 357,82816
357,82816 = 11 0101 0111 , 1000 0010 10002
1 101 010 111 , 100 000 101 0002 = 1527,40508
3*256 + 5*16 + 7 , 8*0,0625 + 2*0,00390625 + 8*0,000244140625 = 855,523437510
357,82816 = 855,523437510 = 1527,40508 = 1101010111,1000001010002
1.3 Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. Вважаючи це число десятковим, перевести його до системи числення залишкових класів із мінімально необхідною кількістю основ 2, 3, 5, 7, 11, ... . Після цього зробити зворотне переведення отриманого результату до десяткової системи числення.
Число: 357828.
p1 = 2;
p2 = 3;
p3 = 5;
p4 = 7;
p5 = 11;
p6 = 13;
p7 = 17.
P = p1 * p2 * p3 * p4 * p5 * p6 * p7 = 2 * 3 * 5 * 7 * 11 * 13 *17 = 510510.
357828 mod 2 = 0;
357828 mod 3 = 0;
357828 mod 5 = 3;
357828 mod 7 = 2;
357828 mod 11 = 9;
357828 mod 13 = 3;
357828 mod 17 = 12.
357828 = ( 0, 0, 3, 2, 9, 3, 12).
B1 = 1*n/2 = 255255; 255255 / 2 = 127627 [1]
B2 = 1*n/3 = 170170; 170170 / 3 = 56723 [1]
B3 = 1*n/5 = 102102; 102102 / 5 = 20420 [2]
B3 = 2*n/5 = 204204; 204204 / 5 = 40840 [4]
B3 = 3*n/5 = 306306; 306306 / 5 = 61261 [1]
B4 = 1*n/7 = 72930; 72930 / 7 = 10418 [4]
B4 = 2*n/7 = 145860; 145860 / 7 = 20837 [1]
B5 = 1*n/11 = 46410; 46410 / 11 = 4219 [1]
B6 = 1*n/13 = 39270; 39270 / 13 = 3020 [10]
B6 = 2*n/13 = 78540; 78540 / 13 = 6041 [7]
B6 = 3*n/13 = 117810; 117810 / 13 = 9062 [4]
B6 = 4*n/13 = 157080; 157080 / 13 = 12083 [1]
B7 = 1*n/17 = 30030; 30030 / 17 = 1766 [8]
B7 = 2*n/17 = 60060; 60060 / 17 = 3532 [16]
B7 = 3*n/17 = 90090; 90090 / 17 = 5299 [7]
B7 = 4*n/17 = 120120; 120120 / 17 = 7065 [15]
B7 = 5*n/17 = 150150; 150150 / 17 = 8832 [6]
B7 = 6*n/17 = 180180; 180180 / 17 = 10598 [14]
B7 = 7*n/17 = 210210; 210210 / 17 = 12365 [5]
B7 = 8*n/17 = 240240; 240240 / 17 = 14131 [13]
B7 = 9*n/17 = 270270; 270270 / 17 = 15898 [4]
B7 = 10*n/17 = 300300; 300300 / 17 = 17664 [12]
B7 = 11*n/17 = 330330; 330330 / 17 = 19431 [3]
B7 = 12*n/17 = 360360; 360360 / 17 = 21197 [11]
B7 = 13*n/17 = 390390; 390390 / 17 = 22964 [2]
B7 = 14*n/17 = 420420; 420420 / 17 = 24730 [10]
B7 = 15*n/17 = 450450; 450450 / 17 = 26497 [1]
B1 = 255255;
B2 = 170170;
B3 = 306306;
B4 = 145860;
B5 = 46410;
B6 = 157080;
B7 = 450450.
( 0, 0, 3, 2, 9, 3, 12) = ( 0 * 255255 + 0 * 170170 + 3 * 306306 + 2 * 145860 + 9 * 46410 + 3 * 157080 + 12 * 450450 ) ( mod 510510 ) = 7504968 mod 510510 = 357828.
357828 = ( 0, 0, 3, 2, 9, 3, 12).
1.4 Виконати ефективне кодування визначених літер прізвища, при умові, що отримане
за допомогою кодової таблиці число - десяткове і говорить про те, скільки разів у "повідомленні" зустрічається дана літера (при цьому, "повідомлення" складається всього з 8 обраних літер).
Визначити ефективність проведенного кодування та порівняти її з ентропією джерела повідомлення і ефективністю рівномірного кодування, тобто з випадком, коли довжина коду для кожної літери одна й та сама. За допомогою отриманих кодів ∑скласти повідомлення, яке складається з визначених літер у тій послідовності, в якій вони зустрічаються у прізвищі. Визначити довжину (в бітах) повідомлення при ефективному і рівномірному кодуванні.
С 35 0,12
А 78 0,3
Л 33 0,11
Ш 17 0,06
Н 23 0,08
И 11 0,04
К 53 0,19
Д 28 0,1
∑278 ∑100%
Літера
Імовірність
Ефективний код
Не ефективний код
код
довжина
код
довжина
А
0,3
11
2
000
3
К
0,19
10
2
001
3
С
0,12
011
3
010
3
Л
0,11
010
3
011
3
Д
0,1
001
3
100
3
Н
0,08
0001
4
101
3
Ш
0,06
00001
5
110
3
И
0,04
00000
5
111
3
H = = - ( 0.3*log20.3 + 0.19*log20.19 + 0.12*log20.12 + 0.11*log20.11 + 0.1*log0.1 +
0.08*log20.08 + 0.06*log20.06 + 0.04*log20.04 ) = - ( - 0.522 – 0.456 – 0.3684 – 0.3509 – 0.33 – 0.2936 – 0.2442 – 0.1868) = - ( - 2.7519) = 2.7519
Lсер. не еф = = 3 = 3
Lсер. еф = = 2*0.3 + 2*0.19 + 3*0.12 + 3*0.11 + 3*0.1 + 4*0.08 + 5*0.06 + 5*0.04 = 0.6 + 0.38 + 0.24 + 0.33 + 0.3 + 0.32 + 0.3 + 0.2 = 2.67
Lсер. еф. < H < Lсер. не еф.
011 11 010 00001 0001 00000 10 001 27 біт
010 000 011 110 101 111 001 100 24 біт
1.5 Для шістнадцяти розрядного двійкового коду (1ц1л)(2ц1л)(1ц8л)(2ц8л) сформувати код Геммінга (Hamming) і продемонструвати його реакцію на однократний збій. Результати подати у вигляді таблиці.
355316 = 00110101010100112
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
k1
k2
i3
k4
i5
i6
i7
k8
i9
i10
i11
i12
i13
i14
i15
k16
i17
i18
i19
i20
i21
1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 0 0 1 1
(1)
k1 = i3 # i5 # i7 # i9 # i11 # i13 # i15 # i17 # i19 # i21 = 0 # 0 # 1 # 0 # 0 # 0 # 0 # 1 # 0 # 1 = 1
k2 = i3 # i6 # i7 # i10 # i11 # i14 # i15 # i18 # i19 = 0 # 1 # 1 # 1 # 0 # 1 # 0 # 0 # 0 = 0
k4 = i5 # i6 # i7 # i12 # i13 # i14 # i15 # i20 # i21 = 0 # 1 # 1 # 1 # 0 # 1 # 0 # 1 # 1 = 0
k8 = i9 # i10 # i11 # i12 # i13 # i14 # i15 = 0 # 1 # 0 # 1 # 0 # 1 # 0 = 1
k16 = i17 # i18 # i19 # i20 # i21 = 1 # 0 # 0 # 1 # 1 = 1
K1 = i3 # i5 # i7 # i9 # i11 # i13 # i15 # i17 # i19 # i21 = 0 # 0 # 1 # 0 # 0 # 0 # 0 # 1 # 1 # 1 = 0
K2 = i3 # i6 # i7 # i10 # i11 # i14 # i15 # i18 # i19 = 0 # 1 # 1 # 1 # 0 # 1 # 0 # 0 # 1 = 1
K4 = i5 # i6 # i7 # i12 # i13 # i14 # i15 # i20 # i21 = 0 # 1 # 1 # 1 # 0 # 1 # 0 # 1 # 1 = 0
K8 = i9 # i10 # i11 # i12 # i13 # i14 # i15 = 0 # 1 # 0 # 1 # 0 # 1 # 0 = 1
K16 = i17 # i18 # i19 # i20 # i21 = 1 # 0 # 1 # 1 # 1 = 0
K # k = (K16 # k16)(K8 # k8)(K4 # k4)(K2 # k2)(K1 # k1) = (0 # 1)(1 # 1)(0 # 0)(1 # 0)(0 # 1) = 100112
1.6 Для послідовності 16-кових цифр (1ц1л)(2ц1л)(1ц2л)(2ц2л)…(1ц8л)(2ц8л),
користуючись картами Карно, визначити всі можливі помилкові коди, які можуть виникати при переході від цифри до цифри.
С – 35
А – 78
Л – 33
Ш – 17
Н – 23
И – 11
К – 53
Д – 28
357833172311532816
Визначення всіх можливих помилкових кодів.
1) 3 => 5
0011 => 0101:
помилкові коди при переході = 0111, 0001.
2) 5 => 7
0101 => 0111:
помилкові коди при переході = —————
3) 7 => 8
0111 => 1000:
помилкові коди при переході = 0000, 0001, 0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100, 1101, 1110, 1111.
4) 8 => 3
1000 => 0011:
помилкові коди при переході = 0000, 0001, 0010, 1001, 1010, 1011.
5) 3 => 3
0011 => 0011:
помилкові коди при переході = —————
6) 3 => 1
0011 => 0001:
помилкові коди при переході = —————
7) 1 => 7
0001 => 0111:
помилкові коди при переході = 0101, 0011.
8) 7 => 2
0111 => 0010:
помилкові коди при переході = 0110, 0011.
9) 2 => 3
0010 => 0011:
помилкові коди при переході = —————
10) 3 => 1
0011 => 0001:
помилкові коди при переході = —————
11) 1 => 1
0001 => 0001:
помилкові коди при переході = —————
12) 1 => 5
0001 => 0101:
помилкові коди при переході = —————
13) 5 => 3
0101 => 0011
помилкові коди при переході = 0001, 0111.
14) 3 => 2
0011 => 0010:
помилкові коди при переході = —————
15) 2 => 8
0010 => 1000:
помилкові коди при переході = 0000, 1010.
2.1 Визначити класи функцій алгебри логіки, до яких належить задана за допомогою
таблиці функція трьох змінних (табл. ТZ.2), і її функціональну повноту. Двійкові коди цифр у графі "f" табл. ТZ.2 потрібно написати вертикально, старший розряд - наверху.
a
b
c
f
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
1ц4л – 1 0001
2ц7л – 3 0011
Функція на нульовому наборі змінних f(0,0,0) = 0. Отже, функція зберігає константу «0».
Функція на одиничному наборі змінних f(1,1,1) = 1. Отже, функція зберігає константу «1».
Функція не є монотонною, оскільки при будь-якому зростанні кількості "1" у послідовності сусідніх наборів змінних значення функції зменшується.
a
b
c
f
a
b
c
f
a
b
c
f
a
b
c
f
a
b
c
f
a
b
c
f
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
1
1
1
1
0
1
0
0
1
1
1
1
1
0
1
1
0
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
a
b
c
f
a
b
c
f
0
0
0
0
1
1
1
1
0
0
1
0
1
1
0
1
0
1
0
0
1
0
1
0
0
1
1
1
1
0
0
0
Функція не є самодвоїстою, оскільки на третій парі протилежних наборів функція не приймає протилежні значення.
Для визначення лінійності функції подамо її у вигляді полінома Жегалкіна
f = /abc # ab/c # abc = (a#1)bc # ab(c#1) # abc = abc # bc # abc # ab # abc =
= abc # abc # abc # (=abc)
# bc # (=bc)
# ab = (=ab)
= abc # bc # ab.
Оскільки поліном містить добутки змінних, то функція не є лінійною.
Отже, із п'яти необхідних для створення ФПС властивостей відсутні дві – не зберігання константи «0» та «1», тому дана функція не утворює ФПС.
2.2 Мінімізувати за допомогою методу Квасна-Мак-Класкі-Петрика 5 функцій (f0, f1,
f2, f3, f4) 5-ти змінних (a, b, c, d, e). Функції задано за допомогою таблиці ТZ.3. Побудувати
таблицю, яка ілюструє процес знаходження простих імплікант,і таблицю покриття
(імплікантну таблицю). За допомогою методу Петрика визначити всі мінімальні розв'язки.
Кожний третій набір для кожної з функцій має невизначене значення. Відлік починається
від першого згори одиничного значення функції з врахуванням зміщення, величина якого
позначена у табл. ТZ.3:
S - відлік починається безпосередньо від першого згори одиничного значення;
-S - відлік починається від попереднього набору відносно першого згори одиничного
значення;
+S - відлік починається від наступного набору відносно першого згори одиничного
значення.
С
А
Л
Ш
Н
И
К
Д
3
5
7
8
3
3
1
7
2
3
1
1
5
3
2
8
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
0
0
0
1
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
1
0
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
1
0
0
1
1
0
0
1
0
1
0
0
0
Зміщення
невизначеного
значення
-S
S
+S
-S
S
№
набору
a
b
c
d
e
f0
f1
f2
f3
f4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
x0
0
0
х0
0
2
0
0
0
1
0
1
x1
1
1
х1
3
0
0
0
1
1
1
1
x1
0
0
4
0
0
1
0
0
x0
0
0
х0
0
5
0
0
1
0
1
1
x1
1
0
х0
6
0
0
1
1
0
0
0
x0
1
1
7
0
0
1
1
1
x1
1
1
х1
1
8
0
1
0
0
0
0
x0
0
0
х0
9
0
1
0
0
1
1
1
x1
0
0
10
0
1
0
1
0
х1
1
1
х0
0
11
0
1
0
1
1
1
x1
1
1
х1
12
0
1
1
0
0
1
1
х1
0
0
13
0
1
1
0
1
х0
0
0
х0
0
14
0
1
1
1
0
0
х0
0
0
х0
15
0
1
1
1
1
0
0
х0
1
1
16
1
0
0
0
0
х0
0
0
х0
0
17
1
0
0
0
1
0
х0
0
1
х1
18
1
0
0
1
0
1
1
х1
0
0
19
1
0
0
1
1
х1
1
1
х1
1
20
1
0
1
0
0
0
х0
0
0
х0
21
1
0
1
0
1
0
0
х0
0
0
22
1
0
1
1
0
х1
1
1
х1
1
23
1
0
1
1
1
1
х1
1
1
х1
24
1
1
0
0
0
0
0
х0
0
0
25
1
1
0
0
1
х0
0
0
х0
0
26
1
1
0
1
0
0
х0
0
1
х1
27
1
1
0
1
1
1
1
х1
0
0
28
1
1
1
0
0
х0
0
0
х1
1
29
1
1
1
0
1
1
х1
1
0
х0
30
1
1
1
1
0
1
1
х1
0
0
31
1
1
1
1
1
х1
1
1
х0
0
Будуємо таблицю, яка ілюструє знаходження простих імплікант:
Мінімізація функції f0
1 2 3
К
П
У
C
К
П
У
С
К
П
У
00001
а0
+
a0b0
000_1
f0
+
f0g3
0_0_1
k0
-
00010
а1
+
a0b1
0_001
f1
+
f1g1
0_0_1
k1
-
00100
а2
+
a1b0
0001_
f2
+
f2g6
0_01_
k2
-
10000
а3
+
a1b2
0_010
f3
+
f2g8
_001_
k3
-
00011
b0
+
a1b4
_0010
f4
+
f3g1
0_01_
k4
-
01001
b1
+
a2b3
0_100
f5
-
f4g2
_001_
k5
-
01010
b2
+
a3b4
100_0
f6
-
g0h3
_0_11
l0
-
0110
b3
+
b0c0
00_11
g0
+
g1h4
_ _011
l1
-
10010
b4
+
b0c1
0_011
g1
+
g2h0
_0_11
l2
-
00111
c0
+
b0c3
_0011
g2
+
g2h1
_ _011
l3
-
01011
c1
+
b1c1
010_1
g3
+
g3h7
_10_1
l4
-
01101
c2
+
b1c2
01_01
g4
+
g4h8
_1_01
l5
-
10011
c3
+
b1c5
_1001
g5
+
g5h1
_10_1
l6
-
10110
c4
+
b2c1
0101_
g6
-
g5h2
_1_01
l7
-
11001
c5
+
b3c2
0110_
g7
+
g7h9
_110_
l8
-
11100
c6
+
b4c3
1001_
g8
+
g8h5
10_1_
l9
-
10111
d0
+
c0d0
_0111
h0
-
h3i1
1_ _11
m0
-
11011
d1
+
c1d1
_1011
h1
-
h4i0
1_ _11
m1
-
11101
d2
+
c2d2
_1101
h2
-
h5i3
1_11_
m2
-
11110
d3
+
c3d0
10_11
h3
+
h6i0
1_11_
m3
-
11111
e0
+
c3d1
c4d0
c4d3
c5d1
c5d2
c6d2
c6d3
1_011
h4
+
h7i2
11_ _1
m4
-
1011_
1_110
110_1
11_01
1110_
111_0
h5
h6
h7
h8
h9
h10
+
+
+
+
+
+
h8i1
h9i3
h10i2
11_ _1
111_ _
111_ _
m5
m6
m7
-
-
-
d0e0
d1e0
d2e0
d3e0
1_111
11_11
111_1
1111_
i0
i1
i2
i3
+
+
+
+
Отже простими імплікантами є кон’юнкції:
/ac/d/e: 0_100; a/b/c/e: 100_0; /ab/cd: 0101_; /bcde: _0111; b/cde: _1011; bc/de: _1101; /a/ce: 0_0_1; /a/cd: 0_01_; /b/cd: _001_; /bde: _0_11; /cde: _ _011; b/ce: _10_1; b/de: _1_01; bc/d: _110_; a/bd: 10_1_; ade: 1_ _11; acd: 1_11_; abe: 11_ _1; abc: 111_ _.
Мінімізація функції f1
1 2 3 4
К
П
У
C
К
П
У
С
К
П
У
C
К
00010
а0
+
a0b0
0001_
f0
+
f0g5
0_01_
k0
+
k0l7
__01_
01000
а1
+
a0b3
0_010
f1
+
f0g9
_001_
k1
+
k1l4
__01_
00011
b0
+
a0b6
_0010
f2
+
f1g1
0_01_
k2
+
k2l7
__01_
00101
b1
+
a1b3
010_0
f3
+
f2g2
_001_
k3
+
k3l4
__01_
01001
b2
+
a1b4
01_00
f4
+
f3g4
010_ _
k4
-
l6m4
1__1_
01010
b3
+
b0c0
00_11
g0
+
f3g7
01_ _0
k5
-
l6m5
1__1_
27.11.2012 22:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора