Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ПРОЕКТУВАННЯ ЦИФРОВИХ СТРУКТУР.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2002
Тип роботи:
Методичні вказівки
Предмет:
Прикладна теорія цифрових автоматів
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти І науки України
національний університет “Львівська політехніка”
Кафедра ЕОМ
Проектування цифрових структур
Методичні вказівки
до курсової роботи
з дисципліни "Прикладна теорія цифрових автоматів"
для студентів базового напрямку 6.0915
“Комп’ютерна інженерія”
Затверджено
на засідання кафедри
“Електронні обчислювальні машини”.
Протокол №2 від 03.09.2002 р.
Львів – 2002
Методичні вказівки до курсової роботи з дисципліни "Прикладна теорія цифрових автоматів" для студентів бакалаврату 6.0915 "Комп'ютерна інженерія", видання друге, стереотипне /Укл. В.С.Глухов, В.А.Голембо. Львів: ДУ"ЛП", 2002.-137 с.
Укладачі В.С.Глухов, к.т.н.
В.А.Голембо, к.т.н.
Відповідальний за випуск В.С.Глухов, к.т.н.
Рецензенти: Ю.С.Вітер, к.т.н.,
М.Й.Томаш, к.т.н.
ВСТУП
У процесі оволодіння студентами бакалаврату "Комп'ютерна інженерія" учбовим матеріалом із дисципліни "Прикладна теорія цифрових автоматів" (ПТЦА) важливу роль відіграє виконання курсової роботи.
В запропонованих методичних указівках курсова робота складається з 29 окремих завдань, об'єднаних у такі чотири розділи:
кодування інформації та перетворення кодів (6 завдань);
використання функцій алгебри логіки та їхня мінімізація (4 завдання);
синтез комбінаційних схем (15 завдань);
виконання арифметико-логічних операцій (9 завдань).
Указівки складаються з теоретичної частини та прикладів розв'язку завдань, так само згрупованих у чотири розділи. Загальна кількість прикладів - 41 (розв'язки завдань першого розділу показані на 11 прикладах, другого - на 8, третього - на 8, четвертого – на 14).
Для поглибленого вивчення теоретичного та практичного матеріалу, у процесі виконання курсової роботи у списку літератури наведені основні навчальні підручники та посібники з ПТЦА [1-3] та суміжних дисциплін [4-14] і довідкова література [15-17].
Зважаючи на те, що в основній та допоміжній навчальній літературах із дисципліни ПТЦА переважає російська мова [1-4, 6-14], для студентів, які вивчають дисципліну ПТЦА українською мовою, запропонований російсько-український словник-мінімум термінологічної лексики з ПТЦА (більше ніж 1100 слів). Необхідно зазначити, що в тексті методичних указівок була використана традиційна термінологічна лексика, якою активно користуються в навчальних посібниках, написаних українською мовою (наприклад, [5]). У свою чергу, метою словника було ознайомити читача із сучасними тенденціями розвитку термінологічної лексики в галузі ПТЦА. Тому при побудові словника поєднувались традиційна лексика [18-19] і перспективна термінологічна лексика, значний внесок у розвиток якої зробив рецензент словника - академік АІН України та де-факто Академік із мови Володимир Перхач [20-23].
У другому стереотипному виданні “Методичних указівок...” виправленні помилки, виявлені у першому виданні.
Відгуки та зауваження до "Методичних указівок..." укладачі просять надсилати відповідальному за випуск доценту кафедри електронних обчислювальних машин інституту комп'ютерних технологій, автоматики та метрології Національного університету "Львівська політехніка" к.т.н. Глухову В.С.
Завдання на роботу, вказівки щодо вибору варіанта роботи
Метою курсової роботи є закріплення у студентів основних теоретичних положень курсу "Прикладна теорія цифрових автоматів", набуття практичних навичок побудови цифрових схем та самостійної роботи з учбовою літературою, яка рекомендована при вивченні курсу.
Робота складається із завдань, які розподілені на чотири частини:
кодування інформації та перетворення кодів;
функції алгебри логіки та їх мінімізація;
синтез комбінаційних схем;
арифметико-логічні операції.
Таблиця ТZ.1
Друга (молодша) цифраПерша (старша) цифраВ8124753В7312475В6247531В5531247В4975312В3753124В2421357В8В7В6В5В4В3В2В135791893745862АБВГДЕ65967184ЄЖЗИІЇ87689316ЙКЛМНО16816538ПРСТУФ38138751ХЦЧШЩЮ71351973ЯЬ
Для вибору варіанта роботи необхідно, користуючись заданим викладачем варіантом кодової таблиці (В1...В8 у табл.ТZ.1), поставити у відповідність першим 8 різним літерам власного прізвища (при необхідності - ім'я та по-батькові) двозначне шістнадцяткове число.
Таким чином визначити 8 двозначних кодів, які відповідають 8 літерам. Далі в тексті (якщо не буде вказано інше) буде позначатися:
1ц1л - переведений у двійковий код шістнадцятковий код першої цифри (1ц) першої літери (1л);
2ц4л - переведений у двійковий код шістнадцятковий код другої цифри (2ц) четвертої літери (4л) і т.д.
Конкретна кодова таблиця задається викладачем окремо для кожної групи студентів.
У процесі виконання першої частини роботи необхідно виконати наведені нижче завдання.
Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. При цьому перші 3 цифри відповідають цілій частині числа, а останні - дробовій.
Наприклад, Біда Ян Андрійович, 8 перших різних літер для варіанту В1: Б, І, Д, А, Я, Н, Р, Й. З кодової таблиці маємо:
Б - 52, І - 14, Й - 36.
Число - 521,436.
Вважаючи це число десятковим, перевести його до шістнадцяткової, вісімкової та двійкової систем числення з точністю відповідно 3, 3 та 5 розрядів після коми.
Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. При цьому перші 3 цифри відповідають цілій частині числа, а останні - дробовій.
Вважаючи це число шістнадцятковим, перевести його до десяткової, вісімкової та двійкової систем числення з точністю відповідно 3, 3 та 5 розрядів після коми.
Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці кодів 1-ої, 2-ої та 8-ої літер прізвища. Вважаючи це число десятковим, перевести його до системи числення залишкових класів із мінімально необхідною кількістю основ 2, 3, 5, 7, 11, ... . Після цього зробити зворотне переведення отриманого результату до десяткової системи числення.
Виконати ефективне кодування визначених літер прізвища, при умові, що отримане за допомогою кодової таблиці число - десяткове і говорить про те, скільки разів у "повідомленні" зустрічається дана літера (при цьому, "повідомлення" складається всього з 8 обраних літер).
Визначити ефективність проведеного кодування та порівняти її з ентропією джерела повідомлення і ефективністю рівномірного кодування, тобто з випадком, коли довжина коду для кожної літери одна й та сама. За допомогою отриманих кодів скласти повідомлення, яке складається з визначених літер у тій послідовності, в якій вони зустрічаються у прізвищі. Визначити довжину (в бітах) повідомлення при ефективному і рівномірному кодуванні.
Для шістнадцяти розрядного двійкового коду
(1ц1л)(2ц1л)(1ц8л)(2ц8л)
сформувати код Геммінга (Hamming) і продемонструвати його реакцію на однократний збій. Результати подати у вигляді таблиці.
Для послідовності 16-кових цифр
Таблиця ТZ.2
abcf0001ц4л0010100111002ц7л101110111
(1ц1л)(2ц1л)(1ц2л)(2ц2л)(1ц3л)(2ц3л)...(2ц7л)(1ц8л)(2ц8л),
користуючись картами Карно, визначити всі можливі помилкові коди, які можуть виникати при переході від цифри до цифри.
У процесі виконання другої частини роботи необхідно виконати наведені нижче завдання.
Визначити класи функцій алгебри логіки, до яких належить задана за допомогою таблиці функція трьох змінних (табл. ТZ.2), і її функціональну повноту.
Двійкові коди цифр у графі "f" табл. ТZ.2 потрібно написати вертикально, старший розряд - наверху.
Таблиця ТZ.3
Зміщення першого невизначеного значення-SS+S-SS№ наборуabcdef0f1f2f3f40000001ц
1л1ц
1л1ц
1л1ц
5л1ц
5л1000012000103000114001002ц
1л2ц
1л2ц
1л2ц
5л2ц
5л5001016001107001118010001ц
2л1ц
2л1ц
2л1ц
6л1ц
6л9010011001010110101112011002ц
2л2ц
2л2ц
2л2ц
6л2ц
6л13011011401110151111116100001ц
3л1ц
3л1ц
3л1ц
7л1ц
7л17100011810010191001120101002ц
3л2ц
3л2ц
3л2ц
7л2ц
7л21101012210110231011124110001ц
4л1ц
4л1ц
4л1ц
8л1ц
8л25110012611010271101128111002ц
4л2ц
4л2ц
4л2ц
8л2ц
8л291110130111103111111
Мінімізувати за допомогою методу Квасна-Мак-Класкі-Петрика 5 функцій (f0, f1, f2, f3, f4) 5-ти змінних (a, b, c, d, e). Функції задано за допомогою таблиці ТZ.3. Побудувати таблицю, яка ілюструє процес знаходження простих імплікант,і таблицю покриття (імплікантну таблицю). За допомогою методу Петрика визначити всі мінімальні розв'язки. Кожний третій набір для кожної з функцій має невизначене значення. Відлік починається від першого згори одиничного значення функції з врахуванням зміщення, величина якого позначена у табл. ТZ.3:
S - відлік починається безпосередньо від першого згори одиничного значення;
-S - відлік починається від попереднього набору відносно першого згори одиничного значення;
+S - відлік починається від наступного набору відносно першого згори одиничного значення.
Наприклад, Біда Ян Андрійович, із кодової таблиці (варіант В1) маємо:
1л) Б - 5216 = 0101 00102,
2л) І - 1416 = 0001 01002,
3л) Д - 1216 = 0001 00102,
4л) А - 3216 = 0011 00102,
5л) Я - 3316 = 0011 00112,
6л) Н - 1616 = 0001 01102,
7л) Р - 5816 = 0101 10002,
8л) Й - 3616 = 0011 01102.
Таблиця ТZ.4
Зміщення першого невизначеного значення-SS+S-SS№ наборуabcdef0f1f2f3f4000000(0)X00001000011(1)X1(0)X020001000(0)X1(1)X300011(1)X11114001000X0(0)X050010100(0)X0(0)X600110(1)X11117001110X0(1)X1 . . .
Табл. ТZ.3 буде мати вигляд табл. ТZ.4 (Х – невизначене значення, показані лише перші 8 рядків таблиці).
Мінімізувати за "1" за допомогою карт Карно функції, задані табл. ТZ.3. Після мінімізації доповнити функції сполучними термами, підкреслити вирази для цих термів в аналітичному записі функції і позначити їх на картах Карно. Результат мінімізації повинен співпадати з одним із розв'язків, знайдених за допомогою методу Петрика (п. 2.2).
Мінімізувати за "0" за допомогою карт Карно функції, задані табл. ТZ.3. Після мінімізації доповнити функції сполучними термами, підкреслити вирази для цих термів в аналітичному записі функції і позначити їх на картах Карно.
У процесі виконання третьої частини роботи необхідно виконати наведені нижче завдання.
Реалізувати функції, отримані в результаті виконання завдання 2.3, у базисі Буля. На виході кожного елемента написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Елементи можуть мати довільну кількість входів. Навести таблиці істинності задіяних елементів.
Реалізувати функції, отримані в результаті виконання завдання 2.3, у базисі Буля. На виході кожного елемента написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Усі елементи повинні мати не більше двох входів. Навести таблиці істинності задіяних елементів.
Реалізувати функції, отримані в результаті виконання завдання 2.3, у монобазисі І-НЕ. На виході кожного елемента І-НЕ написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Елементи можуть мати довільну кількість входів. Навести таблиці істинності задіяних елементів.
Реалізувати функції, отримані в результаті виконання завдання 2.3, у монобазисі Шеффера. На виході кожного елемента Шеффера написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Усі елементи Шеффера повинні бути двовходовими. Навести таблицю істинності елемента Шеффера.
Реалізувати функції, отримані в результаті виконання завдання 2.4, у монобазисі АБО-НЕ. На виході кожного елемента АБО-НЕ написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Елементи можуть мати довільну кількість входів. Навести таблиці істинності задіяних елементів.
Реалізувати функції, отримані в результаті виконання завдання 2.4, у монобазисі Пірса. На виході кожного елемента Пірса написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Усі елементи Пірса повинні бути двовходовими. Навести таблицю істинності елемента Пірса.
Функції, мінімізовані в завданні 2.3, реалізувати за допомогою дешифраторів. У кожного з задіяних дешифраторів кількість виходів не повинна перевищувати 16. Навести таблиці істинності, які пояснюють роботу задіяних дешифраторів.
Функції, мінімізовані в завданні 2.3, реалізувати за допомогою мультиплексорів. У кожного з задіяних мультиплексорів кількість інформаційних входів не повинна перевищувати 16. Навести таблиці істинності, які пояснюють роботу задіяних мультиплексорів.
Функції, мінімізовані в завданні 2.3, реалізувати за допомогою постійного запам'ятовуючого пристрою (ПЗП). Скласти таблиці прошиття ПЗП.
Функції, мінімізовані в завданні 2.3, реалізувати за допомогою програмованої логічної матриці (ПЛМ) типу PAL. Скласти таблиці прошиття (програмування) ПЛМ. Навести функціональну схему запрограмованої ПЛМ.
Функції, мінімізовані в завданні 2.4, реалізувати за допомогою програмованої матриці логіки (ПМЛ) типу PLA. Скласти таблиці прошиття (програмування) ПМЛ. Навести функціональну схему запрограмованої ПМЛ.
Для схем, побудованих у завданнях 3.1 - 3.7, визначити їх "ціну", підрахувавши кількість корпусів задіяних елементів. Визначити оптимальний (найдешевший) варіант.
Для схем, побудованих у завданнях 3.1 - 3.7, визначити їх "ціну", підрахувавши кількість виводів задіяних елементів. Визначити оптимальний (найдешевший) варіант.
Для схем, побудованих у завданнях 3.1 - 3.7, визначити час проходження сигналів від входу до виходу. Визначити оптимальний (найшвидший) варіант.
На базі ПЛМ типу PAL з кількістю інформаційних входів не більше 16 і з входом вибору кристалу створити дешифратор діапазону адрес, який повинен формувати сигнали "більше", "дорівнює", "менше". Діапазон адрес задається 17-розрядним двійковим кодом, який формується з 17 молодших двійкових розрядів коду (2ц1л)(1ц2л)(2ц7л)(1ц8л)(2ц8л). Отриманий таким чином 17-розрядний двійковий код необхідно ще раз переписати, міняючи місцями старші й молодші двійкові розряди (переписати ззаду наперед). Менший з двох 17-розрядних кодів буде нижньою границею діапазону адрес, більший - верхньою. Сигнал "менше" повинен формуватися, коли на вході схеми присутні адреси, які менші за нижню границю діапазону. Сигнал "більше" повинен формуватись, коли на вході схеми присутні адреси, які більші за верхню границю діапазону. Сигнал "дорівнює" повинен формуватись, коли на вході схеми присутні адреси, які знаходяться посередині діапазону. У кожної з задіяних ПЛМ кількість входів не повинна перевищувати 16. Скласти таблиці прошиття ПЛМ, для кожного рядка таблиці прошиття визначити діапазон адрес, якому цей рядок відповідає. Намалювати числову вісь, на якій позначити:
мінімальне і максимальне значення 17-розрядного коду;
верхню і нижню границі;
діапазони кодів, які обробляються різними ПЛМ.
У процесі виконання четвертої частини роботи необхідно виконати наведені нижче завдання.
Виконати порозрядні операції над двома 16-розрядними
кодами:
(1ц1л)(2ц1л)(1ц2л)(2ц2л) and (1ц7л)(2ц7л)(1ц8л)(2ц8л),
(1ц1л)(2ц1л)(1ц2л)(2ц2л) or (1ц7л)(2ц7л)(1ц8л)(2ц8л),
(1ц1л)(2ц1л)(1ц2л)(2ц2л) xor (1ц7л)(2ц7л)(1ц8л)(2ц8л).
Синтезувати в базисі Буля функціональні схеми пристроїв, які виконують дані операції, і навести значення сигналів на входах схеми і на виходах кожного елемента схеми.
Виконати операцію віднімання чисел у двійковому коді:
(1ц3л)(1ц1л)(2ц1л)-(1ц8л)(2ц8л),
(1ц8л)(2ц8л)-(1ц3л)(1ц1л)(2ц1л).
Від'ємний результат потім перевести в прямий код.
Після виконання вказаних операцій навести у шістнадцятковому коді значення операндів і результату.
Синтезувати на базі повних однорозрядних суматорів функціональну схему багаторозрядного суматора, який виконує дані операції, і навести значення сигналів на входах схеми і на виходах кожного однорозрядного суматора.
Синтезувати в базисі Буля функціональну схему повного однорозрядного суматора, навести його таблицю істинності і значення сигналів на входах суматора і на виходах кожного його елемента для кожного розряду згаданого вище багаторозрядного суматора.
Виконати округлення 16-розрядних двійкових кодів із точністю до 1/2 одиниці молодшого розряду, який залишається. Коди:
1(1ц4л)(2ц4л)(1ц5л)(2ц5л) - від'ємне число в доповняльному коді,
0(1ц4л)(2ц4л)(1ц5л)(2ц5л) - додатне число в доповняльному коді.
При першому округленні відкинути два молодших розряди. Наступні округлення провести послідовно через кожних два двійкових розряди. Результат чергового округлення – це початкові дані для наступного округлення.
Виконати операцію віднімання чисел у двійково-десятковому коді (числа задані в шістнадцятковому коді):
(1ц1л)(2ц1л)-(1ц8л)(2ц8л),
(1ц8л)(2ц8л)-(1ц1л)(2ц1л).
Від'ємний результат потім перевести в прямий двійково-десятковий код.
Виконати операції множення в доповняльному коді двійкових чисел, поданих спочатку в прямому коді:
(+2ц1л) х (+2ц8л),
(-2ц1л) х (+2ц8л),
(+2ц1л) х (-2ц8л),
(-2ц1л) х (-2ц8л).
Попередньо всі числа перевести в доповняльний код. Навести алгоритм множення й таблицю, яка відображає зміни всіх операндів (множеного, множника, лічильника, проміжної суми, окремих розрядів та ознак), які беруть участь у множенні, після виконання кожного з операторів алгоритму.
Синтезувати на базі повних однорозрядних суматорів і з використанням елементів базиса Буля функціональну схему матричного помножувача, який виконує операцію множення додатніх чисел (+2ц1л) х (+2ц8л), і навести значення сигналів на входах схеми і на виходах кожного елемента схеми.
Виконати операцію множення в доповняльному коді методом Бута двійкових чисел, представлених спочатку в прямому коді:
(+2ц1л) х (+2ц8л),
(-2ц1л) х (+2ц8л),
(+2ц1л) х (-2ц8л),
(-2ц1л) х (-2ц8л).
Попередньо всі числа перевести в доповняльний код. Навести алгоритм множення й таблицю, яка відображає зміни всіх операндів (множеного, множника, лічильника, проміжної суми, окремих розрядів та ознак), які беруть участь у множенні, після виконання кожного з операторів алгоритму.
Виконати операцію ділення 10-розрядного двійкового коду (10)(1ц2л)(1ц8л) на 5-розрядний двійковий код (1)(1ц1л) методом із відновленням залишків. Навести алгоритм ділення й таблицю, яка відображає зміни всіх операндів (діленого, дільника, лічильника, частки, окремих розрядів та ознак), які беруть участь у множенні, після виконання кожного з операторів алгоритму.
Виконати операцію ділення 10-розрядного двійкового коду (10)(1ц2л)(1ц8л) на 5-розрядний двійковий код (1)(1ц1л) методом без відновлення залишків. Навести алгоритм ділення й таблицю, яка відображає зміни всіх операндів (діленого, дільника, лічильника, частки, окремих розрядів та ознак), які беруть участь у множенні, після виконання кожного з операторів алгоритму.
Виконати операції додавання A+B, віднімання A-B, множення AB і ділення A/B над числами, представленими у форматі з рухомою комою. Число A складається з кодів (2ц1л,2ц8л), число B складається з кодів (2ц2л,2ц7л). Формат операндів і результатів повинен задовільняти вимогам табл. ТZ5.
Таблиця ТZ5
Курсова робота оформляється у вигляді розрахунково-пояснювальної записки (обсягом 30-50 сторінок), до якої додаються функціональні схеми, виконані згідно з вимогами ЄСКД. Креслення в курсовій роботі не передбачаються.
Пояснювальна записка повинна починатися титульним аркушем. У записці повинен знаходитися Зміст з вказівкою назв і номерів розділів і задач, а також сторінок записки, з яких починається розв’язок кожної задачі і кожний розділ. Усі сторінки записки повинні бути пронумеровані. Перша сторінка – титульний аркуш – не нумерується.
Пояснювальна записка повинна розкривати всі дії, які виконувалися студентом, по виконанню кожного з пунктів роботи. Перед розв’язком кожної задачі повинна наводитися її умова. Текстова інформація повинна бути зведена до мінімуму. У кінці записки повинен знаходитися список літератури, яка використовувалася.
Захист курсової роботи є формою перевірки якості її виконання й знань студента в галузі прикладної теорії цифрових автоматів. Захист роботи складається з короткої (10-15 хв.) доповіді студента по виконаній роботі і з письмової відповіді на запитання. У результаті захисту курсової роботи студенти отримують оцінку за чотирибальною системою (незадовільно, задовільно, добре, відмінно). Оцінки виставляються після виправлення студентом усіх помилок, які були виявлені викладачем у роботі під час її перевірки, а також після усунення його зауважень.
Студент, який не здав у встановлений термін курсової роботи і не захистив її без поважної причини, вважається таким, який має академічну заборгованість.
Для рівномірного навантаження студента під час виконання курсової роботи та для своєчасного її подання до захисту рекомендується дотримуватися послідовності виконання роботи згідно з табл. ТZ.6. Таблиця ТZ.6 може мінятися в залежності від програми курсу й уточнюється викладачем під час видачі завдання на курсову роботу.
Допускається захист роботи частинами (завданнями) протягом семестру.
Таблиця ТZ.6
№Характер роботи Термін виконання (тижнів) початокзакінчення1Аналіз технічного завдання122Виконання завдань частини 1 243Виконання завдань частини 2 584Виконання завдань частини 3 9125Виконання завдань частини 4 13166Захист роботи 1718
Методичні вказівки щодо кодування інформації та з перетворення кодів
Переведення чисел до десяткової системи числення з іншої однорідної позиційної системи числення з основою k, коли дії виконуються в десятковій системі
В однорідних позиційних системах числення при безпосередньому представленні цифр число записується у вигляді
X = xsxs-1...x1x0,x-1...x-m.
Кількісний еквівалент, який виражається цим записом, визначається так:
X = ksxs+ks-1xs-1+...+k1x1+k0x0+k-1x-1+...+k-mx-m,(1.1.1)
де k - основа системи числення,
s+1 - розрядність цілої частини числа,
m - розрядність дробової частини числа,
xi - цифри і-го розряду запису числа (xi = 0, 1, ..., k-1),
ki - вага і-го розряду. У даному випадку вага і-го розряду в k разів більша за вагу (і-1)-го розряду. Такі системи числення називають системами з природним порядком ваги, і до них належать двійкова, вісімкова, десяткова і шістнадцяткова системи числення.
Цифри цих систем та їхні еквіваленти наведені в табл. 1.1.1.
Таблиця 1.1.1
Основа системи числення102816000011112(10)223(11)334(100)445(101)556(110)667(111)778(1000)(10)89(1001)(11)9(10)(1010)(12)A(11)(1011)(13)B(12)(1100)(14)C(13)(1101)(15)D(14)(1110)(16)E(15)(1111)(17)F
Примітка: в дужках указані величини десяткових, двійкових та вісімкових еквівалентів.
На використанні формули (1.1.1) заснований один із методів переведення чисел із системи числення з основою k до десяткової системи. Для переведення необхідно записати число у формі (1.1.1), замінити цифри k-тої системи числення та основу k їхніми десятковими еквівалентами, а потім обчислити вираз за правилами десяткової арифметики.
Приклад 1.1.1. Перевести число X2 = 1011,1001 до десяткової системи числення.
1011,10012 =
= 1·23+ 0·22+1·21+1·20+1·2-1+0·2-2+0·2-3+1·2-4 =
= 8 + 0 + 2 + 1 + 0,5 + 0 + 0 + 0,0625 = = 11,5625;
X10 = 11,5625.
Приклад 1.1.2. Перевести вісімкове число 105,71 до десяткової системи числення.
105,718 = 1·82 + 0·81 + 5·80 + 7·8-1 + 1·8-2 =
= 64 + 0 + 5 + 0,875 + 0,015625 = = 69,890625;
X10 = 69,890625.
Приклад 1.1.3. Перевести шістнадцяткове число 2ED,0A до десяткової системи числення.
2ED,0A16 = 2·162+ 14·161+13·160+0·16-1+10·16-2=
= 512 + 224 +13+0+0,0390625 =
= 849,0390625;
X10 = 849,0390625.
Переведення чисел із десяткової системи числення до іншої однорідної позиційної системи числення з основою k, коли дії виконуються в десятковій системі
При даному переведенні окремо виконується переведення цілої частини числа й окремо - дробової, результати потім додаються.
Переведення цілої частини числа
Цілу частину числа X10 ділять на основу системи числення k за правилами десяткової арифметики до отримання залишку, який буде десятковим еквівалентом молодшої цифри результату. Якщо частка від ділення не дорівнює 0, то вона стає діленим і процес ділення на k продовжується. Як тільки чергова частка стане рівною 0, процес ділення на k припиняється. Залишок, який отримали при першому діленні на k, є цифрою розряду результату з вагою k0, залишок при другому діленні - цифрою з вагою k1 і т.д. Останній залишок є старшою цифрою результату.
Переведення дробової частини числа
Дробова частина числа X10 помножується на k за правилами десяткової арифметики. В отриманому добутку від'єднується ціла частина, яка може дорівнювати 0, а дробова частина знову помножується на k із наступним від'єднанням цілої частини. Ця операція повторюється або до отримання нульової дробової частини добутку, або до отримання необхідної кількості розрядів числа Xk. Старша цифра результату переведення (тобто, перша після коми) збігається з першою від'єднаною цілою частиною, друга цифра результату - із другою від'єднаною цілою частиною і т.д. При цьому від’єднані цілі частини необхідно представити в системі числення з основою k.
Приклад 1.2.1. Перевести десяткове число 11,5625 до двійкової системи числення з точністю п’ять розрядів після коми.
Переведення цілої частини:
11 : 2 = 5, залишок 1 (молодший розряд результату),
5 : 2 = 2, залишок 1,
2 : 2 = 1, залишок 0,
1 : 2 = 0, залишок 1 (старший розряд результату).
Таблиця 1.1.2
КрокДрібРезультат множення на k=2Ціла частина результату множення, яка вилучаєтьсяВага двійкового розряду10,56251,1251Старший (перший після коми)20,1250,25030,250,5040,51,0150,00,00Молодший
Результат X2ц = 1011.
Хід переведення дробової частини наведений у табл. 1.1.2.
Результат X2д =0,10010.
Повний результат X2= X2ц+X2д = 1011 + 0,10010 = = 1011,10010.
Переведення чисел з шістнадцяткової й вісімкової систем до двійкової і зворотне переведення чисел
Для переведення чисел з 16-кової і 8-кової систем числення до двійкової необхідно кожну цифру числа, яке переводиться, замінити відповідно чотири- або трирозрядним двійковим еквівалентом (табл. 1.1.1) - тетрадою або тріадою, а отримані двійкові цифри розташувати на місцях 16-кових або 8-кових цифр.
При необхідності переведення чисел із 10-кової системи числення до 8-кової, 16-кової та двійкової переведення робиться тільки до однієї системи (8-кової або 16-кової), подальше переведення виконується через двійкову систему з використання тріад і тетрад.
Приклад 1.3.1. Перевести число 12345,67 з десяткової системи числення до двійкової, 8 кової, 16-кової.
1) переведення цілої частини числа до 8-кової системи:
12345 : 8 = 1543, залишок 1;
1543 : 8 = 192, залишок 7;
192 : 8 = 24, залишок 0;
24 : 8 = 3, залишок 0;
3 : 8 = 0, залишок 3;
результат 300718.
2) переведення дробової частини числа до 8-кової системи:
0,67 х 8 = 5,36;
0,36 х 8 = 2,88;
0,88 х 8 = 7,04;
0,04 х 8 = 0,32;
наближений результат 0,5270... .
Повний результат 30071,5270... .
3) переведення до двійкової та 16-кової систем числення:
3 0 0 7 1 , 5 2 7 0 - 8-кові цифри,
011.'000'0.00'11.1'001',101'0.10'11.1'000 - 2-кові цифри,
3 0 3 9 , A B 8 -16-кові цифри.
Тріади виділені апострофами, тетради - крапками.
Розбиття двійкового числа на тріади і тетради починається від коми ліворуч і праворуч.
Результат
12345,6710=30071,52708=11000000111001,1010101112=
= 3039,AB816.
Алгоритм ефективного кодування Шеннона - Фано
Алгоритм ефективного кодування Шеннона - Фано формує двійкові коди літер алфавіту за принципом "чим частіше зустрічається літера - тим коротшим є її код". Послідовність виконання ефективного кодування така:
1) літери алфавіту виписуються до таблиці в порядку зменшення ймовірності їхньої появи в тексті;
2) таблиця ділиться на дві групи так, щоб суми ймовірностей у кожній з груп були приблизно однаковими;
3) усім літерам верхньої групи як перший символ коду надається значення "1", а нижньої - "0";
4) для визначення наступних символів дії двох попередніх пунктів (пп. 2, 3) повторюються для кожної з груп, доти, поки в групах не залишиться по одній літері.
Якщо групи не вдається сформувати з приблизно рівними ймовірностями, то вводяться нові символи, які є комбінаціями літер (табл. 1.4.1).
Ентропія.
В інформатиці ентропія характеризує степінь нестачі інформації про значення фізичної величини.
Таблиця 1.4.1
ЛітераІмовірністьНова літераКомбінація Імовірністьa00,8b0a0·a0 0,64 b1a0·a1 0,16a1 0,2 b2a1·a0 0,16 b4a1·a1 0,04
Припустимо, що ми провели N дослідів, отримали k різних результатів, і-ий результат (і = 1,2,...,k) повторюється ni разів і вносить кількість інформації Іi.
Середня кількість інформації, яка надається одним дослідом, дорівнює Ісер=(n1І1+ n2І2+...+nkІk)/N,
Іi= log2(1/pi) = -log2pi (чим менша ймовірність події, тим більше інформації ми здобуваємо, коли подія відбувається).
log2x- позначення двійкового логарифму числа x, двійковий логарифм обраховується за допомогою десяткового або натурального логарифму
log2x = log10x/log102 = lgx/lg2 = lnx/ln2;
ni/N = pi;
k
Ісер= -p1log2p1-p2log2p2-...-pilog2pi = - ∑pilog2pi= Ісер = H
і=1
(за Шенноном ентропія H дорівнює середній кількості інформації, вимірюється в бітах).
Властивості ентропії:
1) невід'ємна;
2) дорівнює 0, коли ймовірність однієї події = 1, а решти - 0;
3) максимальна, коли всі ймовірності однакові: p1 = p2 =…=pk = p = 1/k,
Hmax = -kplog2p = - log2p.
Залежність ентропії однократної події від її ймовірності наведена на рис. 1.4.1.
1
1/2
0
p
Рис. 1.4.1
H
0
1
Шеннон довів: повідомлення, які складаються з літер певного алфавіту, можна закодувати так, що середнє число двійкових символів на літеру буде як завгодно близьке до ентропії джерела цих повідомлень, але не менше цієї величини. Таке кодування називається ефективним.
Приклад 1.4.1. Для табл. 1.4.2 ентропія дорівнює
7
Н = - ∑ pilog2pi = 1·1/2 + 2·1/4 +
і=0
+ 3·1/8 + 4·1/16 + 7·1/128 = = 127/64.
Середня довжина коду літери при ефективному кодуванні:
7
Lсер.еф. = ∑ pini = 1·1/2 + 2·1/4 +...+ 7·1/128·7 = 127/64.
і=0
Lсер.еф. = H.
Середня довжина коду літери при неефективному кодуванні:
7
Lсер.нееф. = ∑ pini = 1/2·3 + 1/4·3 +...+ 1/128·3 = 3 > H.
і=0
Приклад 1.4.2. Для табл. 1.4.3 ентропія дорівнює
7
Н = - ∑ pilog2pi = 8·3·1/8 = 3.
і=0
Середня довжина коду літери при ефективному кодуванні:
7
Lсер.еф. = ∑ pini = 8·3·1/8 = 3 = H.
і=0
Середня довжина коду літери при неефективному кодуванні:
7
Lсер.нееф. = ∑ pini = 1/8·1 + 1/8·2 +...+ 1/8·7 = 35/8 > H.
і=0
Таблиця 1.4.2
ЛітераІмовірністьЕфективний код Неефективний кодai piкодДовжинакодДовжинаa01/2 110003a11/4 0120013a21/8 00130103a31/16 000140113a41/32 0000151003a51/64 00000161013a61/128 000000171103a71/128 000000071113
Приклад 1.4.3. Виконати ефективне кодування літер, для яких табл. 1.4.4 визначає, скільки разів вони зустрічаються в "тексті".
Процес кодування відображений у табл. 1.4.5.
Послідовність поділу таблиці на групи літер показана в графі "Крок".
Ентропія:
6
H = - ∑ pi·log2pi = 0,3log20,3+0,29log20,29+0,28log20,28+
і=0
+0,06log20,06+0,04log20,04+0,02log20,02+0,01log20,01 = 2,1.
Середня довжина коду літери при ефективному кодуванні:
6
Lсер.еф.=∑pini=0,30·2+0,29·2+0,28·2+0,06·3+0,04·4+0,02·5+0,01·6+0,00·6=2,14>H.
і=0
Середня довжина коду літери при неефективному кодуванні:
6 6
Lсер.нееф. = ∑ pini = 3· ∑pi = 3 > Lсер.еф. > H.
і=0 і=0
Таблиця 1.4.3
ЛітераІмовірністьНефективний код Ефективний кодai 1/8 кодДовжинакодДовжинаa01/8 110003a11/8 0120013a21/8 00130103a31/8 000140113a41/8 0000151003a51/8 00000161013a61/8 000000171103a71/8 000000071113
1.5. Система залишкових класів
Таблиця 1.4.4
ЛітераКількістьІмовірністьБ1111/249 = 0.04І7272/249 = 0.29Д7111/249 = 0.28А0101/249 = 0.01Я0000/249 = 0.00Н7474/249 = 0.30Р1616/249 = 0.06Й0411/249 = 0.02Усього249249/249 = 1.00
У системі числення, яка називається системою залишкових класів (СЗК), будь-яке число X (Xmin ≤ X < Xmin + P, де P = p1·p2·...·pn) можна зобразити однозначно як сукупність його залишків (q1, q2, ..., qn), які виникають при діленні цього числа на вибрані основи. При цьому основи - це група взаємно простих чисел p1, p2, ..., pn;
0 ≤ qi < pi; і = 1, 2, ..., n.
Основна перевага СЗК - незалежність утворення розрядів числа, внаслідок чого кожний розряд містить у собі інформацію про все число X. Це створює можливість незалежної обробки розрядів, тобто порозрядного виконання операцій.
До недоліків СЗК, які значно ускладнюють її практичне використання в обчислювальній техніці, можна віднести:
відсутність достатньо простих ознак виходу числа за межі діапазону [Xmin, P+Xmin];
отримання завжди точного результату операції, внаслідок чого виключається можливість безпосереднього округлення результату і взагалі наближеного виконання операцій;
неможливість прямого ділення двох довільних чисел;
неможливість візуального порівняння двох чисел.
Переведення чисел із позиційної десяткової системи числення у СЗК.
Переведення чисел із позиційної десяткової системи числення у СЗК виконується послідовним діленням числа на вибрані основи до отримання залишків. Набір цих залишків - це і є число в СЗК.
Таблиця 1.4.5
┌───┬──────┬───────┬──────────┬────────────┬────┐
│ │Літера│Імовір-│Ефективний│Неефективний│Крок│
│ │ │ ність │ код │ код │ │
│ ├──────┼───────┼──────┬───┼──────┬─────┤ │
│ і │ ai │pi │ │ ni │ │ ni │ │
├───┼──────┼───────┼──────┼───┼──────┼─────┼────┤
│ 0 │ Н │0.30 │11 │ 2 │000 │ 3 │ │
├───┼──────┼───────┼──────┼───┼──────┼─────┤<- 2│
│ 1 │ І │0.29 │10 │ 2 │001 │ 3 │ │
├───┼──────┼───────┼──────┼───┼──────┼─────┤<- 1│
│ 2 │ Д │0.28 │01 │ 2 │010 │ 3 │ │
├───┼──────┼───────┼──────┼───┼──────┼─────┤<- 3│
│ 3 │ Р │0.06 │001 │ 3 │011 │ 3 │ │
├───┼──────┼───────┼──────┼───┼──────┼─────┤<- 4│
│ 4 │ Б │0.04 │0001 │ 4 │100 │ 3 │ │
├───┼──────┼───────┼──────┼───┼──────┼─────┤<- 5│
│ 5 │ Й │0.02 │00001 │ 5 │101 │ 3 │ │
├───┼──────┼───────┼──────┼───┼──────┼─────┤<- 6│
│ 6 │ А │0.01 │00000 │ 6 │110 │ 3 │ │
└───┴──────┴───────┴──────┴───┴──────┴─────┴────┘
Приклад 1.5.1. Перевести в СЗК з основами (базисом) p1=2, p2=3, p3=5 перші n чисел (n=3) натурального ряду.
Спочатку визначимо P = p1·p2·p3 = 2·3·5 = 30.
Тобто, у вибраній системі можливо зобразити без повторень лише 30 різних чисел (у даному прикладі від 0 до 29, табл. 1.5.1).
З наведеного прикладу видно, що для обраного базису (2,3,5) у СЗК число 30 має такий самий код, як і число 0. Тобто однозначне переведення можливе тільки в межах визначеного діапазону P.
Переведення чисел з СЗК до позиційної десяткової системи числення.
Таблиця 1.5.1
ЧислоЗалишки від діленняКод у СЗКна 2на 3на 5 00000,0,011111,1,120220,2,231031,0,340140,1,451201,2,060010,0,171121,1,280230,2,391041,0,4100100,1,0111211,2,1120020,0,2131131,1,3140240,2,4151001,0,0160110,1,1171221,2,2180030,0,3191141,1,4200200,2,0211011,0,1220120,1,2231231,2,3240040,0,4251101,1,0260210,2,1271021,0,2280130,1,3291241,2,4300000,0,0
Переведення числа (q1,q2,q3,...qn) з СЗК з базисом (p1, p2, p3, ..., pn) до позиційної десяткової системи числення виконується за формулою
А = (q1·B1 + q2·B2 + q3·B3 + qn·Bn)(mod P),
де В1 = (1,0,0,...,0),
B2 = (0,1,0,...,0),
B3 = (0,0,1,...,0),
... ,
Bn = (0,0,0,...,1) - ортогональні базиси – вага n-го розряду числа, яке записано у СЗК. Вага Bn обчислюється за формулою
Bn = mn·P/pn,
де mn - ціле число, вага ортогонального базису, обирається з умови
Вn/pn = 1(mod pn).
Ортогональні базиси подаються цифрами десяткової системи числення.
Приклад 1.5.2. Перевести число (1,2,3,2) з СЗК із базисом (2,3,5,7) до позиційної десяткової системи числення.
Знаходимо P = 2·3·5·7 = 210.
Знаходимо ортогональні базиси для різних mn і починаємо з mn = 1:
В1 = 1·n/2 = 105; перевірка умови ортогональності:
105/2 = 52[1], залишок 1 - умова виконується, отже, В1 = 105.
В2 = 1·n/3 = 70; перевірка умови ортогональності:
70/3 = 23[1], залишок 1 - умова виконується, отже, В2 = 70.
В3 = 1·n/5 = 42; перевірка умови ортогональності:
42/5 = 8[2], залишок 2 - умова не виконується, пробуємо наступну вагу m3 = 2:
В3 = 2·n/5 = 84; перевірка умови ортогональності:
84/5 = 8[4], залишок 4 - умова не виконується, пробуємо наступну вагу m3 = 3:
В3 = 3·n/5 = 126; перевірка умови ортогональності:
126/5 = 25[1], залишок 1 - умова виконується, отже, В3 = 126.
В4 = 1·n/7 = 30; перевірка умови ортогональності:
30/7 = 4[2],
залишок 2 - умова не виконується, пробуємо наступну вагу m4 = 2:
В4 = 2·n/7 = 60; перевірка умови ортогональності
60/7 = 8[4],
залишок 4 - умова не виконується, пробуємо наступну вагу m4 = 3:
В4 = 3·n/7 = 90; перевірка умови ортогональності
90/7 = 12[6],
залишок 6 - умова не виконується, пробуємо наступну вагу m4 = 4:
В4 = 4·n/7 = 120; перевірка умови ортогональності
120/7 = 17[1], залишок 1 - умова виконується, отже, В4 = 120.
Власне переведення:
(1,2,3,1) = (1·105 + 2·70 + 3·126 + 2·120)(mod 210) =
= 863(mod 210) =(863/210)(mod 210) = 23.
Отже, (1,2,3,2) = 23.
1.6. Код Геммінга
Код Геммінга належить до кодів, які дозволяють виправляти помилки, що виникають при пересиланні інформації. Найпростіший код Геммінга дозволяє визначати та виправляти однократні помилки.
При пересиланні інформації до k інформаційних розрядів додається r перевірочних розрядів так, що загальна довжина n слова, яке пересилається, становить n = k + r розрядів. Співвідношення n, k, та r обирається з умови
2k ≤ 2n/(1+n).
Для різних значень n обчислені значення k та r наведені у табл. 1.6.1.
Таблиця 1.6.1
nkr7431511431265
Формули, за допомогою яких формуються перевірочні розряди r, виводяться за допомогою перевірочної матриці (табл. 1.6.2).
У табл. 1.6.2 позначено: k1...k11 - інформаційні розряди, які необхідно переслати лінією зв'язку;
Таблиця 1.6.2
┌────────────────────────────────────────────────────┐
│ n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 n14 n15 │
├────────────────────────────────────────────────────┤
│ 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 │
│ 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 │
│ 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 │
│ 1 0 1 0 1 0 1 0 1 0 1 0 1 ...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора