Міністерство освіти І науки України національний університет “Львівська політехніка” КАФЕДРА ЕОМ
Курсова робота з дисципліни: Прикладна теорія цифрових автоматів Львів – 2001 Вибір варіанту роботи. В даній курсовій роботі усі розрахунки проводяться згідно даних таблиці № 2, яка наводиться нижче: Таблиця №2 Визначимо коди за допомогою , яких буде виконано дану курсову роботу. Перших вісім різних літер імені [ім’я автора приховано] є такі: К , О , З , А , Ч , Р , М , Н. Поставимо у відповідність кожній літері код у таблиці. З кодової таблиці маємо: 1л) К - 7810 = 4Е16; 2л) О - 2810 = 1С16; 3л) З - 5610 = 3816; 4л) А - 9410 = 5Е16; 5л) Ч - 5310 = 3516; 6л) Р - 7110 = 4716; 7л) М - 3810 = 2616; 8л) Н - 1810 = 1216. Кодування інформації та перетворення кодів. 1.1. Десяткове число 782.81810 перевести в шістнадцятковий, вісімковий та двійкові коди. 3 782 768 14 16 48 48 0 16 0.818 16 13.088 0.088 16 1.408 0.408 16 6.528 0.528 16 8.448 0.448 16 7.168      782.81810 = 30E.D168716 = 001100001110.110100010110100001112 = 1416.64264178 1.2. Шістнадцяткове число 4E1.C1216 перевести в десятковий вісімковий та двійковий коди. 4E1.C1216 = 010011100001.1100000100102 = 2341.60228 = 1249.7543910 4 162 + 1416 + 3 + 1216-1 + 16-2 + 216-3 = 1249.75439 1.3. Число 4E1C1216 перевести в систему числення залишкових класів з мінімальною кількістю основ 2, 3, 5, 7, 11, 13, 17, ... Після цього зробити зворотнє перетворення. 4E1C1216 = 511899410 2  3  5  7  11  13  17 = 510510 2  3  5  7  11  13  17  19 = 9 699 690 p = 9699690 Базис {2, 3, 5, 7, 11, 13, 17, 19} 5118994mod 2 = 0 5118994mod 11 = 1 5118994mod 3 = 1 5118994mod 13 = 10 5118994mod 5 = 4 5118994mod 17 = 5 5118994mod 7 = 6 5118994mod 19 = 14 1716496 = (0, 1, 4, 6, 1, 10, 5, 14) Зворотнє переведення A = (q1  b1 +q2  b2 + … + qn  bn) mod p. b1 = 1  9699690 / 2 = 4849845 4849845 mod 2 = 1 b1 = 4849845 b2 = 1  9699690 / 3 = 3233230 3233230 mod 3 = 1 b2 = 3233230 b3 = 1  9699690 / 5 = 1939938 1939938 mod 5 = 3 b3 = 2  9699690 / 5 = 3879876 3879876 mod 5 = 1 b3 = 3879876 b4 = 1  9699690 / 7 = 1385670 1385670 mod 7 = 6 b4 = 2  9699690 / 7 = 2771340 2771340 mod 7 = 5 b4 = 3  9699690 / 7 = 4157010 4157010 mod 7 = 4 b4 = 4  9699690 / 7 = 5542680 5542680 mod 7 = 3 b4 = 5  9699690 / 7 = 6928350 6928350 mod 7 = 2 b4 = 6  9699690 / 7 = 8314020 8314020 mod 7 = 6 b4 = 8314020 b5 = 1  9699690 / 11 = 881790 881790 mod 11 = 8 b5 = 2  9699690 / 11 = 1763580 1763580 mod 11 = 5 b5 = 3  9699690 / 11 = 2645370 2645370 mod 11 = 2 b5 = 4  9699690 / 11 = 3527160 3527160 mod 11 = 10 b5 = 5  9699690 / 11 = 4408950 4408950 mod 11 = 7 b5 = 6  9699690 / 11 = 5290740 5290740 mod 11 = 4 b5 = 7  9699690 / 11 = 6172530 6172530 mod 11 = 1 b5 = 6172530 b6 = 1  9699690 / 13 = 746130 746130 mod 13 = 8 b6 = 2  9699690 / 13 = 1492260 1492260 mod 13 = 3 b6 = 3  9699690 / 13 = 2238390 2238390 mod 13 = 11 b6 = 4  9699690 / 13 = 1492260 1492260 mod 13 = 6 b6 = 5  9699690 / 13 = 3730650 3730650 mod 13 = 1 b6 = 3730650 b7 = 1  9699690 / 17 = 570570 570570 mod 17 = 16 b7 = 2  9699690 / 17 = 1141140 1141140 mod 17 = 15 b7 = 3  9699690 / 17 = 1711710 1711710 mod 17 = 14 b7 = 4  9699690 / 17 = 2282280 2282280 mod 17 = 13 b7 = 5  9699690 / 17 = 2852850 2852850 mod 17 = 12 b7 = 6  9699690 / 17 = 3423420 3423420 mod 17 = 11 b7 = 7  9699690 / 17 = 3993990 3993990 mod 17 = 10 b7 = 8  9699690 / 17 = 4564560 4564560 mod 17 = 9 b7 = 9  9699690 / 17 = 5135130 5135130 mod 17 = 8 b7 = 10  9699690 / 17 = 5705700 5705700 mod 17 = 7 b7 = 11  9699690 / 17 = 6276270 6276270 mod 17 = 6 b7 = 12  9699690 / 17 = 6846480 6846840 mod 17 = 5 b7 = 13  9699690 / 17 = 7417410 7417410 mod 17 = 4 b7 = 14  9699690 / 17 = 7987980 7987980 mod 17 = 3 b7 = 15  9699690 / 17 = 8558550 8558550 mod 17 = 2 b7 = 16  9699690 / 17 = 9129120 9129120 mod 17 = 1 b7 = 9129120 b8 = 1  9699690 / 19 = 510510 510510 mod 19 = 18 b8 = 1  9699690 / 19 = 510510 510510 mod 19 = 18 b8 = 2  9699690 / 19 = 1021020 1021020 mod 19 = 17 b8 = 3  9699690 / 19 = 1531530 1531530 mod 19 = 16 b8 = 4  9699690 / 19 = 2042040 2042040 mod 19 = 15 b8 = 5  9699690 / 19 = 2552550 2552550 mod 19 = 14 b8 = 6  9699690 / 19 = 3063060 3063060 mod 19 = 13 b8 = 7  9699690 / 19 = 3573570 3573570 mod 19 = 12 b8 = 8  9699690 / 19 = 4084080 4084080 mod 19 = 11 b8 = 9  9699690 / 19 = 4594590 4594590 mod 19 = 10 b8 = 10  9699690 / 19 = 5105100 5105100 mod 19 = 9 b8 = 11  9699690 / 19 = 5615610 5615610 mod 19 = 8 b8 = 12  9699690 / 19 = 6126120 6126120 mod 19 = 7 b8 = 13  9699690 / 19 = 6636630 6636630 mod 19 = 6 b8 = 14  9699690 / 19 = 7147140 7147140 mod 19 = 5 b8 = 15  9699690 / 19 = 7657650 7657650 mod 19 = 4 b8 = 16  9699690 / 19 = 8168160 8168160 mod 19 = 3 b8 = 17  9699690 / 19 = 8678670 8678670 mod 19 = 2 b8 = 18  9699690 / 19 = 9189180 9189180 mod 19 = 1 b8 = 9189180 A = ( 3233230 + 4  3879876 + 6  8314020 + 6172530 + 10  3730650 + 5  9129120 + 14  9189180) mod 9699690 = 170013724 mod 9699690 = 5118994 1.4. Виконати ефективне кодування літер призвіща, якщо відповідний код літери говорить скільки разів вона зустрічається в “повідомленні”. Довжина ефективного коду: le = 0.216  2 + 0.179  3 + 0.163  3 + 0.128  3 + 0.122  3 + 0.087  3 + 0.064  4 + 0.041  4 = 2.889 Довжина неефективного коду: lne = 3 Ентропія: H= – EMBED Equation.3 
PAGE \# "'Стр: '#' '"   EMBED Equation.3 
 H =  ( 0.216  log20.216 + 0.179  log20.179 + 0.163  log20.163 + 0.128  log20.128 + 0.122  log20.122 + 0.087  log20.087 + 0.064  log20.064 + 0.041  log20.041 ) = 2.84 1.5. Для шістнадцятирозрядного двійкового коду 4E1216 = 01001110000100102 сформувати код Хеммінга і продемонструвати його реакцію на однократний збій. p = 16 тоді k = 5 оскільки 2k  p + k n = p + k = 16 + 5 = 21 k1 = r1 # r3 # r5 # r7 # r9 # r11 # r13 # r15 # r17 # r19 # r21 k2 = r2 # r3 # r6 # r7 # r10 # r11 # r14 # r15 # r18 # r19 k3 = r4 # r5 # r6 # r7 # r12 # r13 # r14 # r15 # r20 # r21 k4 = r8 # r9 # r10 # r11 # r12 # r13 # r14 # r15 k5 = r16 # r17 # r18 # r19 # r20 # r21 Виділений рядок у таблиці – код , який треба передати. Нижній стовпець – отриманий код із збоєм у 4 розряді. Контрольні розряди після передачі коду обраховані по вищенаведених формулах: k1 = 0; k2 = 0; k3 = 0; k4 = 1; k5 = 0; В розряді (k5k4k3k2k1) = (01000)2 = 810 отримано помилку. Інвертуємо даний розряд , для того щоб отримати правильний код. 1.6. Для послідовності 16-кових цифр визначити всі можливі помилкові коди, які можуть виникати при переході від цифри до цифри. 4  E  1  C  3  8  5  E  3  5  4  7  2  6  1  2 4  E 0100 22  2 = 2 1110 Хибні коди: 1100; 0110 E  1 1110 24  2 = 14 0001 Хибні коди: 0110; 1010; 1100; 1111; 0101; 1001; 0011; 0000; 0010; 0100; 0111; 1000; 1011; 1101 1  C 0001 23  2 = 6 1100 Хибні коди: 1001; 0101; 0100; 1000; 1101; 0000 C  3 1100 24  2 = 14 0011 Хибні коди: 0000; 0001; 0010; 0100; 0101; 0110; 0111;1000; 1001; 1010; 1011; 1101; 1110; 1111 3  8 0011 23  2 = 6 1000 Хибні коди: 1011; 0001; 0010; 0000; 1010; 1001 8  5 1000 23  2 = 6 0101 Хибні коди: 0000; 1100; 1001; 1101; 0001; 0100 5  E 0101 23  2 = 6 1110 Хибні коди: 1101; 0111; 0100; 0110; 1100; 1111 E  3 1110 23  2 = 6 0011 Хибні коди: 0110; 1010; 1111; 1011; 0111; 0010 3  5 0100 22  2 = 2 1111 Хибні коди: 0111; 0001 5  4 0101 Гонок немає 0100 4  7 0100 22  2 = 2 0111 Хибні коди: 0110; 0101 7  2 0111 22  2 = 2 0010 Хибні коди: 0011; 0110 2  6 0010 Гонок немає 0110 6  1 0110 23  2 = 6 0001 Хибні коди: 0010; 0100; 0111; 0101; 0011; 0000 1  2 0001 22  2 = 2 0010 Хибні коди: 0011; 0000 2. Функції алгебри логіки та їх мінімізація 2.1. Визначити функціональну повноту заданої таблично функції алгебри логіки трьох змінних: 1) Оскільки на нульовому наборі f(0,0,0) = 0 , то ця функція зберігає константу нуля “0”. 2) Оскільки на одиничному наборі f(1,1,1) = 0 , то ця функція не зберігає константу одиниці “1”. 3) Послідовності сусідніх наборів подані в таблицях (а) , (б) , (в) , (г) , (д) , (е) : (а) (б) (в) (г) (д) (е) Оскільки на всіх шести послідовностях сусідніх наборів функція не є монотонною (а досить було б і на одному) , то функція не є монотонною взагалі. 4)