| Побудова кодопреобразователя[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.
скачати
Міністерство освіти і науки Російської Федерації Південно-Уральський державний університет Кафедра Автоматики і Управління Пояснювальна записка до курсової роботи за курсом: «Цифрові автомати» «Побудова кодопреобразователя» Керівник Радкевич І. А. «» 2007р. Автор роботи студентка групи ЗФ-228-с Ватутіна / Лазука / А. Л. «» 2007р. Проект захищений з оцінкою _________________________ « » 2007р. Челябінськ 2007 Зміст Завдання Введення Поняття про дискретно (цифровому) автоматі. Основні поняття алгебри логіки. Поняття теорії графів Граф-дерево автомата Мура. Граф-дерево автомата Мілі. Таблиця переходів по автомату Мілі Таблиця виходів по автомату Мілі Мінімізація цифрового автомата Мілі. Таблиця переходів з розподілом невизначеностей. Виняток недосяжних станів. Визначення класу сумісності. Класи одиничної сумісності Класи двійкової сумісності Класи трійкової сумісності Класи четверичной сумісності Класи п'ятеричному сумісності Таблиця станів і виходів нормалізованого автомата Структурний синтез цифрового автомата Вибір тригера Представлення функції збудження Таблиця станів і виходів нормалізованого автомата Мінімізують карти Мінімізація функцій за методом Квайна Мінімізація функцій за методом Мак-Класкі Висновок Література Завдання Побудувати пристрій для перетворення послідовного двійково-десяткового коду X = (х З, х 2, х 1, х 0), який подається на вхід пристрою z = (z 3, z 2, z 1, z 0). Десятковий еквівалент X двійково-десяткового коду може бути обчислений: Х = Ë x i p i, де x i = 0, 1 - цифра двійково-десяткового коду, a p i - вага i - ro розряду. Варіант завдання представлений у таблиці: Номер варіанта | X Р 3 Р 2 Р 1 P 0 | z Р 3 Р 2 Р 1 P 0 | 24 | 4311 | 5211 |
Мета Дослідження впливу алгоритмів синтезу цифрових автоматів на складність структури самого цифрового автомата. Будь-яке цифровий пристрій з необхідним поведінкою може бути спроектована на основі єдиної моделі, а саме як автомат Милі або автомат Мура. У роботі вивчаються синхронні варіанти автоматів Мілі і Мура. Синхронізація забезпечує стійкість станів автомата і дозволяє провести його синтез найпростішим чином. Введення У ході виконання курсової роботи було реалізовано побудова кодопреобразователя за заданим значенням функцій входу і виходу. На першому рівні реалізації роботи була складена таблиця відповідностей вхідного і вихідного сигналів для десяти заданих значень і вироблені перетворення для дотримання умови автоматними. На наступному рівні роботи було вироблено побудова граф-дерев абстрактних автоматів Мура і Милі. Потім по графу складені таблиці переходів і виходів для автомата Мілі. На третьому рівні роботи зроблена мінімізація автомата Мілі шляхом складання таблиці переходів з розподілом невизначеностей, винятком недосяжних станів проектованого автомата, визначення класів сумісності до отримання нормалізованого автомата, побудова графа отриманого автомата. На четвертому рівні роботи був проведений структурний синтез цифрового автомата з кодуванням двійковим кодом вхідний, вихідний функцій автомата, а також функції станів. Визначено таблиця станів обраного для реалізації кодопреобразователя D-тригера. П'ятим етапом виконання роботи була мінімізація за допомогою діаграм Вейча, функцій виходу кодопреобразователя і збудження D-тригера, а також їх реалізація в базисі І, АБО, НЕ. На останньому рівні роботи була складена схема послідовного кодопреобразователя заданого вхідного коду в заданий вихідний на найпростіших цифрових автоматах з пам'яттю. Особливістю цифрового автомата є залежність оператора перетворення А від попередніх станів кодопреобразователя, тобто наявність пам'яті у цифрового автомата. В окремому випадку відсутності пам'яті у цифрового автомата, він є логічною схемою. Таким чином, предметами дослідження в теорії цифрових автоматів є як власне цифрові автомати (системи з пам'яттю), так і автомати без пам'яті або логічні схеми. Найбільш розроблена теорія цифрових автоматів стосовно канонічної структурі цифрового автомата, представленої на рис.1. Для подальшого розгляду використовується тільки ця структура цифрового автомата. 
КС ВХ - Вхідна комбінаційна схема; П - пам'ять; Кс ВЬ1Х - вихідна комбінаційна схема; Х-вхідний цифровий код; В - код порушення пам'яті; А - код стану пам'яті; Y - вихідний код. Рис.1. Канонічна структурна схема цифрового автомата За структурною схемою цифрового автомата видно, що вхідні коди вхідний і вихідний комбінаційних схем виходять в результаті конкатенації (об'єднання) вхідного коду та коду стану пам'яті цифрового автомата. Поняття про дискретно (цифровому) автоматі. Дискретними автоматами прийнято називати пристрої, що служать для перетворення дискретної інформації. У сучасних цифрових автоматах прийнято звичайно ототожнювати букви використовуваного стандартного алфавіту з цифрами тієї чи іншої системи числення (найчастіше двійковій або десятковій). Тому дискретні автомати прийнято також називати цифровими автоматами. Основною якістю, виділяє дискретні автомати з числа всіх інших перетворювачів інформації, є наявність дискретного (при цьому реальних автоматах завжди кінцевого) безлічі внутрішніх станів і властивості стрибкоподібного переходу автомата з одного стану в інший. Стрибкуватість переходу означає можливість трактувати цей перехід як миттєвий, причому як такий, що відбувається безпосередньо, минаючи будь-які проміжні стану. Зміни станів цифрового автомата називаються вхідними сигналами, що виникають поза автомата і передаються в автомат за кінцевим числу вхідних каналів. Результатом роботи цифрового автомата є видача вихідних сигналів, що передаються з автомата в зовнішні ланцюги за кінцевим числа вихідних каналів. Цифровий автомата (першого або другого роду) називається правильним, якщо вихідний сигнал y (t) визначається одним лише його станом (a (t -1) або a (t)) і не залежить явно від вхідного сигналу x (t). Автомати першого роду звичайно також називають автоматами Мілі, за ім'ям американського вченого, який вперше почав їх систематичне вивчення. Особливий інтерес на практиці мають правильні автомати другого роду, відомі зазвичай під більш коротким назвою автоматів Мура. Основні поняття алгебри логіки. Поняття цифрового автомата було введено як модель для опису функціонування пристроїв, призначених для переробки цифровий або дискретної інформації. Для формального опису цифрових автоматів застосовується апарат алгебри логіки, створеної англійським математиком Дж. Булем (1815-1864). Тому алгебру логіки називають алгеброю Буля або булевої алгеброю. В алгебрі логіки стосовно до опису цифрових автоматів, що працюють у двійковому поданні кодів (або цифрової інформації) основними поняттями є логічна (булева) змінна і логічна функція (функція алгебри логіки - ФАЛ). Логічна (булева) змінна - така величина x, яка може приймати тільки два значення: х = {0,1}. Логічна функція (функція алгебри логіки - ФАЛ) - функція багатьох аргументів f (x n -1, х n -2, ..., х 0), що приймає значення рівні нулю або одиниці на наборах логічних змінних x n -1, х n -2, ..., х 0. Надалі у формальних описах наборів змінних і логічних функцій самі набори змінних інтерпретуються як двійкові коди (числа). У двійкових кодах розташування логічних змінних впорядковано в порядку зменшення індексу зліва направо, і кожна логічна змінна має вагу в залежності від позиції в коді, що збільшується справа наліво. Вага кожної i-тої логічної змінної, що є значенням розряду двійкового числа дорівнює 2 i (i = 0 ,..., n - l). Для n-розрядного коду загальна кількість унікальних наборів змінних: N = 2 n (1) Максимальне числове значення двійкового коду одно: A макс = 2 n - 1 (2) Значення всіх логічних функцій від однієї змінної представлені в таблиці 1. Таблиця 1 X | f 0 (x) | f 1 (x) | f 2 (x) | f 3 (x) | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 |
Функція f 0 (x) називається константою нуля, а функція f 3 (x) - константою одиниці. Функція f i (x), що повторює значення логічної змінної, - тотожна функція (f i (x) = x), а функція f 2 (x), що приймає значення, зворотні значенням змінної х, - логічне заперечення або інверсія (НЕ) ( f 2 (x) = 
).
Елементи алгебри логіки мають наступні операції:
Кон'юнкція (І, логічне множення) - твір двох висловлювань Р і Q, результатом якого є істина, якщо обидва висловлювання Правдиві й кривду у всіх інших випадках.
Диз'юнкція (АБО, логічна сума) - сума двох висловлювань Р і Q; результатом є хибне висловлювання, якщо обидва висловлювання хибні, і справжнє у всіх інших випадках.
Інверсія (Заперечення) - запереченням висловлювання Р називається висловлювання істинне, якщо саме висловлювання Р помилкове, або навпаки.
Для функції двох змінних, відповідно до ф. (1), існує чотири унікальні набору змінних. Функції відрізняються один від одного набором значень 0 і 1 у чотирьох розрядах коду значень функції. Загальна кількість функцій на п-місцевому або п-розрядному наборі змінних дорівнює: 
(3).
Дві функції рівносильні одна одній, якщо вони беруть на всіх можливих наборах змінних одні й ті ж значення.
Аналітично це властивість описується наступною формулою:
f 1 (x n -1, x n -2, ..., x 0) = f 1 (x n -1, x n -2, ..., x 0) (4)
Обидві функції у ф. (4) можуть мати різні форми аналітичного запису, але практично найбільш вигідною буде найпростіша форма запису.
Система булевих функцій W називається функціонально повною, якщо для будь-якої булевої функції п-змінних f (x n -1, х n -2, ..., х 0) може бути побудована рівносильна їй функція комбінуванням булевих змінних x n -1, х n -2, ..., х 0 та функцій системи W, узятих в будь-якому кінцевому кількості екземплярів кожна. Така система булевих функцій (W) називається базисом.
Таким чином, базис - повна система функцій алгебри логіки (ФАЛ), за допомогою якої будь-яка ФАЛ може бути представлена суперпозицією вихідних функцій W.
Базисом є система функцій І (сполучення), АБО (диз'юнкція), НЕ, (інверсія), властивості яких були вперше вивчені Дж. Булем.
Базис є мінімальним, якщо видалення з нього хоча б однієї функції перетворює систему ФАЛ в неповну. Базис І, АБО, НЕ - надлишковий.
Для абстрактного математичного опису цифрового автомата як кодопреобразователя використовується представлення 6-елементної множини S = {А, Х, У, d, l, a 1,}.
Поняття множини - поняття, яке не має визначення. Множини мають свої підмножини, воно може бути кінцевим і нескінченним. Впорядкованим буде безліч, в якому кожен елемент має своє місце.
Безліч буде складатися з наступних елементів:
А = {а 1 ..., а п}-безліч станів автомата,
X = {х 1 ..., х п} - безліч вхідних сигналів,
Y = {у 1 .. ., У п} - безліч вихідних сигналів,
d - функція переходів абстрактного цифрового автомата,
l - функція виходів абстрактного цифрового автомата,
a 1 - початковий стан автомата (a i належить А).
Для однозначного управління цифровим автоматом необхідно, щоб він починав роботу з певного початкового стану. Автомат є кінцевим, якщо А, X і Y не є нескінченними множинами. Теоретично всі елементи множин А, X, Y можуть бути закодовані числами в системі числення з будь-якою підставою, але на практиці завжди використовується двійкова система числення. Згідно структурній схемі (рис.1), коди наборів змінних комбінаційних схем визначаються в результаті конкатенації кодів вхідних сигналів і кодів станів блоку пам'яті. Як набори вхідних змінних, так і коди станів блоку пам'яті в загальному випадку містять заборонені комбінації, тому системи функцій алгебри логіки, що описують комбінаційні схеми, не будуть повністю визначеними.
Використовуючи поняття та визначення алгебри логіки, складемо таблицю (відповідності) значень вхідних і вихідних сигналів.
Десяткові цифри | Вхідний код 4311 | Вихідний код 5311 |
0 | 0000 | 0000 |
1 | 0001 | 0001 |
2 | 0010 | 0010 |
3 | 0011 | 0011 |
4 | 0100 | 0100 |
5 | 0101 | 0101 |
6 | 1000 | 1010 |
7 | 1001 | 1011 |
8 | 1100 | 1110 |
9 | 1101 | 1111 |
При розгляді кінцевого автомата необхідно розглянути умова автоматна, тобто виконання наступних умов:
Довжина вхідного слова повинна відповідати довжині вихідного слова. У загальному випадку при невідповідності вхідного і вихідного слів відсутні фрагменти заповнюються порожніми символами (0);
Мінімум три перших символу вхідних і вихідних слів повинні відповідати один одному. У нашому випадку ця умова частково не виконується, тому для дотримання умови автоматної кодопреобразователя до вхідного і вихідного словами додамо порожні символи (0).
При цьому таблиця відповідності прийме вигляд:
Десяткові цифри | Вхідний код 4311 | Вихідний код 5311 |
0 | 0000 000 | 000 0000 |
1 | 0001 000 | 000 0001 |
2 | 0010 000 | 000 0010 |
3 | 0011 000 | 000 0011 |
4 | 0100 000 | 000 0100 |
5 | 0101 000 | 000 0101 |
6 | 1000 000 | 000 1010 |
7 | 1001 000 | 000 1011 |
8 | 1100 000 | 000 1110 |
9 | 1101 000 | 000 1111 |
Найчастіше на практиці використовується два різновиди цифрових автоматів, що відрізняються способом формування вихідних сигналів:
- При описі функціонування автомата виразами:
a (t + l) = 5 [a (t), z (t)],
w (t) = l [a (t), z (t)] - він називається автоматом Мілі;
- При описі функціонування автомата виразами:
a (t +1) = d [a (t), z (t)],
w (t) = l [а (t)] - він називається автоматом Мура.
У цих виразах t - поточний момент дискретного автоматного часу, t +1-наступний момент дискретного автоматного часу.
Поняття теорії графів
Графами називають взаємозв'язок двох множин складаються з безлічі вершин і безлічі ребер, індукованих (пов'язаних) між собою.
Повний граф - це граф, який не має петель, кратності ребер, і всі його вершини зв'язані між собою.
Неорієнтований граф - граф, який не має вказівки напрямів ребер, при переході з однієї вершини в іншу.
Орієнтований (повний) граф - граф з ребрами, що вказують конкретний напрям при переході з однієї вершини в іншу.
Граф-дерево - це слабкозв'язаного граф, у якого якщо видалити одне ребро, то він розпадається на два графа.
Граф автомата - орієнтований зв'язний граф, вершини якого відповідають станам, а дуги - переходам між ними.
Теорія графів має великі програми, так як мова теорії, з одного боку, є очевидним, а, з іншого боку, зручний в нормальному дослідженні. При повному зображенні графа не всі деталі малюнка мають однакове значення, а саме геометричні властивості ребер (кривизна, довжина і т.д.) і розташування вершин на площині відносно один одного.
Дві вершини графа автомата а т і a s (вихідний стан і стан переходу) з'єднуються дугою (ребром), спрямованої від а т в a s. Дузі (а т, a s) графа автомата приписується вхідний сигнал х і вихідний сигнал у, якщо він визначений, і, в іншому випадку, ставиться прочерк. Якщо перехід автомата зі стану а т в стан a s відбувається під дією декількох вхідних сигналів, то дузі (a m, a s) приписуються всі ці вхідні і відповідні вихідні сигнали.
При описі автомата Мура у вигляді графа вихідний сигнал y записується всередині вершини а т або поруч з нею, а вхідний сигнал х над дугою (ребром), яка демонструє перехід з одного стану в інший.
При описі автомата Мілі у вигляді графа всередині вершини записується стан, у який переходить автомат, а над дугою (ребром), яка демонструє перехід з одного стану автомата в інше, записується дріб, у чисельнику якого вказується вхідний сигнал, а в знаменнику - вихідний сигнал.
Для завдання функцій переходів і виходів побудуємо граф-дерево автомата Мура, а потім автомата Мілі. При використанні табличного опису автомата Мура таблиці переходів автоматів Милі і Мура співпадуть, а таблиця виходів автомата Мілі вийде з таблиці переходів заміною a s символом вихідного сигналу.
У технічних цілях використовуються тільки детерміновані цифрові автомати, в яких виконана умова однозначності переходів: - автомат, що знаходиться в деякому стані, під дією будь-якого вхідного сигналу не може перейти більш ніж в один стан. Стосовно до табличного способу завдання опису автоматів це означає, що в клітинах переходів / виходів вказується тільки по одному стану / вихідному сигналу. Стосовно до графічного способу завдання опису автоматів це означає, що в графі автомата з будь-якої вершини не можуть виходити дві або більше дуги, відмічені одним і тим же вхідним сигналом.
Стійким станом автомата називається такий стан, що для будь-якого х, d (a m, x) = a s, має місце d (a s, x) = a s. Це означає, що якщо автомат перейшов у якийсь стан х, то вийти з цього стану може тільки під дією іншого сигналу.
Синхронним називається автомат, якщо він не є асинхронним і кожне його стан стійко.
Якщо для деякої пари (a m, z f) вихідний сигнал автомата не визначений, то для цієї пари не визначається і функція переходу, тому що не визначено допустиме слово, яке здійснює перехід з цього стану.
Граф-дерево автомата Мура.
Для побудови графа-дерево автомата Мура використовуємо таблицю відповідності, доповнену до виконання умови автоматними. Після виконання умови автоматної граф-дерево прийме вигляд:
Два автомата з однаковими вхідним і вихідним алфавітами називаються еквівалентними, якщо після установки початкового стану їх реакції на будь-яке вхідне слово збігаються. Звідси випливає, що для будь-якого автомата Мілі існує еквівалентний автомат Мура, і, назад, для будь-якого автомата Мура існує еквівалентний йому автомат Милі. Таким чином, можливі взаємні трансформації автоматів.
Граф-дерево автомата Мілі.
10
У ході етапу побудови кодопреобразователя здійснюється перетворення графа-дерево автомата Мура в граф-дерево автомата Мілі. Для цього всі кінцеві стани автомата Мура замінюються нульовим станом. Граф-дерево автомата Мілі:
Таблиця переходів по автомату Мілі
Наступним кроком є побудова кодопреобразователя за отриманим графу автомата Мілі - побудова таблиці переходів автомата з одного стану в інший під дією вхідних змінних.
x / a | a 0 | a 1 | a 2 | a 3 | a 4 | a 5 | a 6 | a 7 | a 8 | a 9 | a 10 | a 11 | a 12 | a 13 | a 14 | a 15 | a 16 | a 17 | a 18 | a 19 | a 20 | a 21 |
0 | a 1 | a 3 | a 5 | a 7 | a 9 | a 10 | a 11 | a 12 | a 14 | a 16 | a 18 | a 20 | a 22 | a 23 | a 24 | a 25 | a 26 | a 27 | a 28 | a 29 | a 30 | a 31 |
1 | a 2 | a 4 | a 6 | a 8 | - | - | - | a 13 | a 15 | a 17 | a 19 | a 21 | - | - | - | - | - | - | - | - | - | - |
x / a | a 22 | a 23 | a 24 | a 25 | a 26 | a 27 | a 28 | a 29 | a 30 | a 31 | a 32 | a 33 | a 34 | a 35 | a .36 | a 37 | a 38 | a 39 | a 40 | a 41 |
0 | a 32 | a 33 | a 34 | a 35 | a 36 | a 37 | a 38 | a 39 | a 40 | a 41 | a 0 | a 0 | a 0 | a 0 | a 0 | a 0 | a 0 | a 0 | a 0 | a 0 |
1 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
Таблиця виходів по автомату Мілі
Якщо для деякої пари а i x i вихідний сигнал не визначено, то для цієї пари можна не визначати і функцію переходів, так як не існує допустимого слова, що здійснює перехід для цього слова. Виходячи з вищевикладеного, будуємо таблицю виходів по графу Милі:
x / a | a 0 | a 1 | a 2 | a 3 | a 4 | a 5 | a 6 | a 7 | a 8 | a 9 | a 10 | a 11 | a 12 | a 13 | a 14 | a 15 | a 16 | a 17 | a 18 | a 19 | a 20 | a 21 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | - | - | - | 0 | 0 | 0 | 1 | 1 | - | - | - | - | - | - | - | - | - | - |
x / a | a 22 | a 23 | a 24 | a 25 | a 26 | a 27 | a 28 | a 29 | a 30 | a 31 | a 32 | a 33 | a 34 | a 35 | a .36 | a 37 | a 38 | a 39 | a 40 | a 41 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
Рядки цих таблиць відповідають вхідним сигнальним множинам х, а стовпці станам а, причому перший лівий стовпець означає початковий стан инициального цифрового автомата. У нашому варіанті функція визначена не повністю, тому функцію необхідно довизначити. Це довизначення довільне і залежить від завдання, яке ставиться перед довизначенням. Надалі передбачається проводити мінімізацію функції, тому довизначення краще зробити так, щоб мінімальна форма функції вийшла простіше, ніж мінімальна дізьюктівная нормальна функція, що отримується при інших довизначення. Мінімізація цифрового автомата Мілі. Абстрактний автомат, побудований за технічним завданням формальним чи евристичним методами, зазвичай не є мінімальним за кількістю станів. Побудова еквівалентного йому абстрактного цифрового автомата з найменшим числом станів і є завданням оптимізації. При мінімізації кількості станів зменшується вартість, як блоку пам'яті автомата, так і його вхідний і вихідний комбінаційних схем. Два повністю певних автомата називаються еквівалентними, якщо вони індукують (виробляють) один і той же відображення множини вхідних слів в безліч вихідних слів. Частковий цифровий автомат А називається еквівалентним продовженням часткового автомата В, якщо індуковані їм відображення збігається з відображенням, індукованим автоматом В на всіх допустимих для автомата У словах. Повністю певний автомат є окремим випадком часткового автомата. Таблиця переходів з розподілом невизначеностей. Першим (попередніми) етапом будь-якої мінімізації є виділення невизначених вихідних сигналів і станів та внесення відповідної невизначеності в таблиці переходів і виходів автомата. Внесення невизначеності не повинно змінювати початкового відображення, яке повинен індукувати розглянутий автомат. Ступінь повноти внесеної невизначеності визначає значною мірою і можливості подальшої мінімізації. Виняток недосяжних станів. Якщо в автоматі є стан (але тільки не початкове), в яке він не може потрапити під впливом будь-якого припустимого вхідного слова, то такий стан називається недосяжним. Недосяжні стану виключаються з опису абстрактного автомата без зміни, індукованого автоматом відображення. Автомат, всі стани якого досяжні, є зв'язковим автоматом. Визначення класу сумісності. Стани а i і a j називаються сумісними, якщо, рухаючись з цих станів під впливом будь-якого вхідного сигналу, автомат індукує однакове його відображення. Стани називаються i-сумісними для i = 1, 2 ,..., якщо результат застосування до цих станів будь-якого слова довжини i буде однаковим. Класи сумісних станів можуть бути знайдені безпосередньо за таблицею виходів. В один і той же 1 - клас зараховуються стану, що позначають збігаються (з точністю до невизначених вихідних сигналів) стовпці таблиці виходів. Класи (i +1) - сумісності виходять з класів i - сумісності шляхом їх розщеплення на класи (i +1) - сумісності. Для цього в кожного стану, що належить j - класу i - сумісності C j (i), номери класів (індекси), в які автомат переходить під впливом кожної вхідної літери. Якщо номер класу не визначений, то ставиться спеціальний символ, наприклад, прочерк. Індекси класів, в які переходить автомат під впливом вхідного сигналу, утворюють позначку. Безліч станів з однаковими відмітками в класі C j (i) утворюють класи (i +1) - сумісності. При виконанні операції розщеплення класів спеціальний символ невизначеності може бути замінений номером (індексом) будь-якого класу. Якщо операцію розщеплення i-класів застосувати послідовно, починаючи з 1-класу, то через кінцеве число кроків процес розщеплення закінчиться. Нерозщеплюваних далі класи утворюють класи сумісних станів. Іноді позначки станів різних класів збігаються, але об'єднувати такі стани в один клас (i +1) - сумісності абсолютно неприпустимо. Завданням мінімізації методом розщеплення класів є отримання якомога меншої кількості і як можна більшої ємності класів кінцевої сумісності. Класи одиничної сумісності У класи одиничної сумісності помістимо: C 1 (1) | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 3 | 1 | 1 | 4 | 1 | - | 5 | 2 | - | 6 | 2 | - | 7 | 1 | 1 | 8 | 1 | 1 | 9 | 2 | 2 | 12 | 1 | - | 13 | 1 | - | 14 | 2 | - | 15 | 2 | - | 18 | 2 | - | 19 | 2 | - | 22 | 1 | - | 23 | 2 | - | 26 | 1 | - | 27 | 2 | - | 32 | 1 | - | 34 | 1 | - | 36 | 1 | - | 38 | 1 | - | 40 | 1 | - |
C 2 (1) | 0 | 1 | 10 | 1 | 1 | 11 | 2 | 2 | 16 | 1 | - | 17 | 1 | - | 20 | 2 | - | 21 | 2 | - | 24 | 1 | - | 25 | 2 | - | 28 | 1 | - | 29 | 2 | - | 30 | 1 | - | 31 | 2 | - | 33 | 1 | - | 35 | 1 | - | 37 | 1 | - | 39 | 1 | - | 41 | 1 | - |
Бачимо, що в таблицях є несумісні переходи класів, тому продовжимо розбиття. Класи двійкової сумісності D 1 (2) | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 1 | 1 | 4 | 2 | - | 7 | 1 | 1 | 8 | 2 | 2 | 12 | 1 | - | 13 | 2 | - | 22 | 3 | - | 26 | 3 | - |
| - |
9 | 4 | 4 |
14 | 4 | - |
15 | 6 | - |
18 | 4 | - |
19 | 6 | - |
23 | 5 | - |
27 | 5 | - |
D 3 (2) | 0 | 1 |
32 | 1 | - |
34 | 1 | - |
36 | 1 | - |
38 | 1 | - |
40 | 1 | - |
D 5 (2) | 0 | 1 |
33 | 1 | - |
35 | 1 | - |
37 | 1 | - |
39 | 1 | - |
41 | 1 | - |
D 6 (2) | 0 | 1 |
11 | 6 | 6 |
20 | 4 | - |
21 | 6 | - |
25 | 5 | - |
29 | 5 | - |
3 січня | 5 | - |
D 4 (2) | 0 | 1 |
10 | 2 | 2 |
16 | 1 | - |
17 | 2 | - |
24 | 3 | - |
28 | 3 | - |
30 | 3 | - |
Бачимо, що в таблицях є несумісні переходи класів, тому продовжимо розбиття. E 10 (3) | 0 | 1 |
24 | 7 | - |
28 | 7 | - |
30 | 7 | - |
|
|
|
E 12 (3) | 0 | 1 |
11 | 13 | 12 |
21 | 14 | - |
|
|
|
E 13 (3) | 0 | 1 |
20 | 10 | - |
|
|
|
E 14 (3) | 0 | 1 |
25 | 11 | - |
29 | 11 | - |
31 | 11 | - |
Класи трійкової сумісності E 1 (3) | 0 | 1 |
0 | 1 | 2 |
1 | 1 | 2 |
3 | 1 | 2 |
7 | 1 | 2 |
12 | 3 | - |
|
|
|
E 2 (3) | 0 | 1 |
2 | 4 | 5 |
4 | 4 | - |
8 | 4 | 5 |
13 | 6 | - |
E 3 (3) | 0 | 1 |
22 | 7 | - |
26 | 7 | - |
|
|
|
E 4 (3) | 0 | 1 |
5 | 8 | - |
9 | 9 | 8 |
14 | 10 | - |
18 | 10 | - |
|
|
|
E 5 (3) | 0 | 1 |
6 | 12 | - |
15 | 14 | - |
19 | 14 | - |
E 7 (3) | 0 | 1 |
32 | 1 | - |
34 | 1 | - |
36 | 1 | - |
38 | 1 | - |
40 | 1 | - |
|
|
|
E 8 (3) | 0 | 1 |
10 | 4 | 5 |
17 | 6 | - |
|
|
|
E 9 (3) | 0 | 1 |
16 | 3 | - |
E 6 (3) | 0 | 1 |
23 | 11 | - |
27 | 11 | - |
E 11 (3) | 0 | 1 |
33 | 1 | - |
35 | 1 | - |
37 | 1 | - |
39 | 1 | - |
41 | 1 | - |
F 21 (4) | 0 | 1 |
11 | 23 | 22 |
|
|
|
F 22 (4) | 0 | 1 |
21 | 24 | - |
|
|
|
F 23 (4) | 0 | 1 |
20 | 19 | - |
|
|
|
F 24 (4) | 0 | 1 |
25 | 20 | - |
29 | 20 | - |
31 | 20 | - |
Класи четверичной сумісності F 1 (4) | 0 | 1 | 0 | 2 | 6 |
|
|
| F 2 (4) |
|
0 | 1 | 1 | 3 | 6 |
|
|
| F 3 (4) | 0 | 1 | 3 | 4 | 6 |
|
|
| F 5 (4) | 0 | 1 | 12 | 8 | - |
|
|
| F 6 (4) | 0 | 1 | 2 | 9 | 12 | 4 | 10 | - | 8 | 11 | 13 |
|
|
| F 7 (4) | 0 | 1 | 13 | 14 | - |
|
|
| F 8 (4) | 0 | 1 | 22 | 15 | - | 26 | 15 | - |
|
|
| F 9 (4) | 0 | 1 | 5 | 16 | - |
|
|
| F 10 (4) | 0 | 1 | 9 | 18 | 17 |
|
|
| F 11 (4) | 0 | 1 | 14 | 19 | - | 18 | 19 | - |
|
|
| F 12 (4) | 0 | 1 | 6 | 21 | - |
F 13 (4) | 0 | 1 |
15 | 24 | - |
19 | 24 | - |
|
|
|
F 14 (4) | 0 | 1 |
23 | 20 | - |
27 | 20 | - |
|
|
|
F 15 (4) | 0 | 1 |
32 | 1 | - |
34 | 1 | - |
36 | 1 | - |
38 | 1 | - |
40 | 1 | - |
|
|
|
F 16 (4) | 0 | 1 |
10 | 11 | 13 |
|
|
|
F 17 (4) | 0 | 1 |
17 | 14 | - |
|
|
|
F 18 (4) | 0 | 1 |
16 | 8 | - |
|
|
|
F 19 (4) | 0 | 1 |
24 | 15 | - |
28 | 15 | - |
30 | 15 | - |
|
|
|
F 20 (4) | 0 | 1 |
33 | 1 | - |
35 | 1 | - |
37 | 1 | - |
39 | 1 | - |
41 | 1 | - |
Класи п'ятеричному сумісності
G 1 (5) | 0 | 1 |
0 | 2 | 6 |
|
|
|
G 2 (5) | 0 | 1 |
1 | 3 | 7 |
|
|
|
G 3 (5) | 0 | 1 |
3 | 4 | 8 |
|
|
|
G 4 (5) | 0 | 1 |
7 | 5 | 9 |
|
|
|
G 5 (5) | 0 | 1 |
12 | 10 | - |
|
|
|
G 6 (5) | 0 | 1 |
2 | 11 | 14 |
|
|
|
G 7 (5) | 0 | 1 |
4 | 12 | - |
|
|
|
G 8 (5) | 0 | 1 |
8 | 12 | 15 |
|
|
|
G 9 (5) | 0 | 1 |
13 | 16 | - |
|
|
|
G 10 (5) | 0 | 1 |
22 | 17 | - |
26 | 17 | - |
|
|
|
G 11 (5) | 0 | 1 |
5 | 18 | - |
|
|
| G 12 (5) | 0 | 1 | 9 | 20 | 19 |
|
|
| G 13 (5) | 0 | 1 | 14 | 21 | - | 18 | 21 | - |
|
|
| G 14 (5) | 0 | 1 | 6 | 23 | - | G 15 (5) | 0 | 1 | 15 | 26 | - | 19 | 26 | - |
|
|
| G 16 (5) | 0 | 1 | 23 | 22 | - | 27 | 22 | - |
|
|
| G 17 (5) | 0 | 1 | 32 | 1 | - | 34 | 1 | - | 36 | 1 | - | 38 | 1 | - | 40 | 1 | - |
|
|
| G 18 (5) | 0 | 1 | 10 | 13 | 15 |
|
|
| G 19 (5) | 0 | 1 | 17 | 16 | - |
|
|
| G 20 (5) | 0 | 1 | 16 | 10 | - |
|
|
| G 21 (5) | 0 | 1 | 24 | 17 | - | 28 | 17 | - | 30 | 17 | - |
|
|
| G 22 (5) | 0 | 1 | 33 | 1 | - | 35 | 1 | - | 37 | 1 | - | 39 | 1 | - | 41 | 1 | - |
|
|
| G 23 (5) | 0 | 1 | 11 | 25 | 24 |
|
|
| G24 (5) | 0 | 1 | 21 | 26 | - |
|
|
|
G 25 (5) | 0 | 1 | 20 | 21 | - |
|
|
| G 26 (5) | 0 | 1 | 25 | 22 | - | 29 | 22 | - | 31 | 22 | - |
При побудові нормалізованого автомата перехід d = (C i, z j) вважається невизначеним, якщо для всіх станів цього класу не визначені переходи в інший стан. Якщо хоча б для одного стану класу перехід визначено, то в клітину таблиці нормалізованого автомата заноситься індекс класу, до якого переходить цифровий автомат з цього стану. Таким чином, доопределяют невизначені переходи вихідного автомата. Нормалізоване автомат є еквівалентним будь-якому з мінімізованих автоматів і не має, як мінімум, жодної пари сумісних станів. Відповідно до викладеної методикою мінімізації виходять або повністю певні, або часткові нормалізовані автомати. У повністю певних автоматів клас кінцевої сумісності не перетинаються, тому нормалізоване автомат є єдиним і процес мінімізації цим закінчується. У разі отримання часткового автомата класи i-сумісності перетинаються. Це призводить до того, що нормалізоване автомат може описуватися кінцевим кількістю варіантів таблиць чи графів. У разі часткових автоматів часто відмовляються від досягнення абсолютної мінімізації та обмежуються знаходженням нормалізованого автомата і його магічними довизначенням. Таблиця станів і виходів нормалізованого автомата Вх / сост | G 1 | G 2 | G 3 | G 4 | G 5 | G 6 | G 7 | G 8 | G 9 | G 10 | G 11 | G 12 | G 13 | 0 | G 2 / 0 | G 3 / 0 | G 4 / 0 | G 5 / 0 | G 10 / 0 | G 11 / 0 | G 12 / 0 | G 13 / 0 | G 16 / 0 | G 17 / 0 | G 18 / 0 | G 20 / 0 | G 21 / 0 | 1 | G 6 / 0 | G 7 / 0 | G 8 / 0 | G 9 / 0 | - / - | G 14 / 0 | - / - | G 15 / 0 | - / - | - / - | - / - | G 19 / 0 | - / - |
|
|
|
|
|
|
|
|
|
|
|
|
|
| Вх / сост | G 14 | G 15 | G 16 | G 17 | G 18 | G 19 | G 20 | G 21 | G 23 | G 24 | G 25 | G 26 |
| 0 | G 23 / 0 | G 26 / 0 | G 22 / 0 | G 1 / 0 | G 13 / 0 | G 16 / 0 | G 10 / 1 | G 17 / 1 | G 25 / 1 | G 26 / 1 | G 21 / 0 | G 22 / 1 |
| 1 | - / - | - / - |
| - / - | - / - | G 15 / 1 | - / - | - / - | - / - | G 24 / 1 | - / - | - / - | - / - |
|
У результаті всіх перетворень ми отримали нормалізоване мінімізований автомат, за яким побудуємо граф автомата Мілі: 
Структурний синтез цифрового автомата Структурний синтез цифрового автомата - це кодування його вхідних і змінних і станів автомата та отримання функції збудження і функцій виходів тригера. Завданням етапу структурного синтезу є побудова принципової схеми автомата з елементарних автоматів заданого типу. Елементарні автомати поділяються на два великих класи: Завдання синтезу цифрового автомата має рішення в тому випадку, якщо система елементарних автоматів є структурно повною. Будь-яка система елементарних автоматів, що містить елементарний автомат, Мура (тригер) і яку-небудь функціонально повну систему логічних елементів є структурно повною системою. Якщо автомат має М станів, то для двійкового структурного алфавіту кількість тригерів у блоці пам'яті цього автомата n =] log 2 M [(1) де ]...[- найближче більше ціле число. Якщо в кожну клітину таблиці переходів і виходів записати двійковий код, відповідний розміщеним там станів чи вихідним сигналам цифрового автомата, то таким чином виходять кодовані таблиці переходів і виходів. Кодована таблиця виходів є табличним описом системи булевих функцій, реалізованих схемою КС ВИХІД. Кодована таблиця переходів тільки після переробки з використанням матриці переходів для заданого типу тригерів буде називатися кодованої таблицею збуджень і відповідати опису комбінаційної схеми КС ВХ. Таким чином, задача синтезу полягає у визначенні за таблицями функцій виходу і функцій збудження тригерів заданого типу в блоці пам'яті, мінімізації їх для вибраної елементної бази та схемної реалізації у функціонально повному базисі елементів. Вибір тригера Комбінаційна схема з зворотними зв'язками, що має два стійких стани і призначена для зберігання одного біта інформації, називається елементарним автоматом або тригером. Для синтезу цифрових автоматів тригери розглядаються як елементи систем, і важливим є вивчення його поведінки в системі, а не внутрішня структура чи принципова схема. У цьому полягає системотехнічних підхід до вивчення тригерів різних типів. Тригер типу RS. Назва тригера походить від англійських слів set і reset, він має два входи - S для встановлення тригера в одиницю і R для установки його в нуль. Як правило, він має два виходи: прямий і інверсний. Якщо для перекладу тригера з одного стану в інший на настановні входи необхідно подавати не логічні одиниця, а нулі, то такий тригер називається тригером з інверсним керуванням. 
Рис. 2. Тригери типу RS з прямим (а) і інверсним (б) управлінням Тригер типу JK. Тригер типу JK працює також як і тригер RS, з тією лише різницею, що допустима одночасна подача сигналів J = K = 1, яка змінює його стан на протилежний. Вхід K еквівалентний входу R, а вхід J - входу S. Тригер типу D. Назва тригера походить від англійського слова «затримка» (delay). Тригер має один вхід. На виході він повинен повторювати сигнал, що існував на своєму вході в попередній такт: D-тригери завжди випускаються синхронними, так як асинхронний тригер працює просто як повторювач вхідних сигналів. 
Рис. 3. Умовні позначення JK і D тригера. Тригер типу T. Тригери цього типу випускаються промисловістю як самостійні пристрої. Вони можуть бути зібрані з тригерів інших типів як на рис. 4. логічна одиниця, прикладена до T-входу тригера, змінює його стан на протилежний. 
Рис. 4. Рахункові тригери Тригер типу RST. Це лічильний тригер з двома установчими входами. Багатовхідних тригер в цифровому автоматі дозволяє спростити його структуру. Для вирішення нашого завдання виберемо D-тригер, який має лише один вхід (D) і на виході він повторює сигнал на вході D, що існував у попередньому такті автоматного часу. Оскільки в межах періоду синхроімпульсів вхідний сигнал з'являється у довільний момент часу, то на вихід вхідний сигнал проходить з довільною затримкою, що не перевищує тривалість періоду синхросигналу. Представлення функції збудження За формулою (1) розрахуємо необхідну кількість розрядів для кодування: N =] log 23 лютого [= 5 розрядів. Якщо в кожну клітину таблиці переходів і виходів записати двійковий код, відповідний розміщеним там станів чи вихідним сигналам цифрового автомата, то таким чином виходять кодовані таблиці переходів і виходів. Кодована таблиця виходів є табличним описом системи булевих функцій, реалізованих схемою КС вих. Кодована таблиця переходів тільки після переробки з використанням матриці переходів для заданого типу тригерів буде називатися кодованої таблицею збуджень і відповідати опису комбінаційної схеми КС ВХ. Очевидно, що при кодуванні переходів і виходів можна дотримуватися двох принципів опису булевих функцій. Якщо бажано отримати табличне опис функцій виходів з найменшою кількістю одиничних значень, то для кодування часто зустрічаються в таблиці виходів сигналів слід використовувати коди з максимально можливою кількістю нулів у коді, а для кодування наступних за кількістю посилань в таблиці виходів сигналів використовувати коди з кількістю одиниць в кодових комбінаціях. Для кодування станів блоку пам'яті на D тригерах також можна використовувати цей принцип кодування, оскільки таблиця збуджень для них збігається з таблицею переходів. Рекомендувати цей принцип для, загального застосування при синтезі автоматів не можна, тому що при мінімізації булевих функцій можливе отримання більш простих результуючих форм представлення функцій, що мають більш складну запис у СДНФ (Нормальна дізьюктівная форма - це набір змінних без загальних заперечень і дужок. Досконала НДФ - це коли всі набори змінних маю однакову довжину. СДНФ - це набір кон'юнкція змінних однакової довжини). Цей принцип можна використовувати тільки в тому випадку, якщо ФАЛ виходів і ФАЛ збуджень для D тригерів не підлягають мінімізації, оскільки реалізуються на мультиплексорах, дешифратора або постійних запам'ятовуючих пристроях. Другий принцип кодування відповідає протилежним підходом і орієнтований на можливість отримання значних спрощень ФАЛ в результаті мінімізації. Для кодування вихідних сигналів з максимальною кількістю посилань в таблиці виходів використовується код з максимальною кількістю одиниць, а для кодування наступних за кількістю посилань в таблиці вихідних сигналів використовувати коди з зменшуваним кількістю одиниць в кодових комбінаціях. Цей принцип також без застережень застосуємо для кодування станів блоку пам'яті на D тригерах для випадку застосування елементної бази, що вимагає мінімізації для своєї реалізації. Мінімальний з матеріальних витрат варіант кодування вибирається з кінцевих результатів при використанні всіляких варіантів кодування. Таблиця станів і виходів нормалізованого автомата Вх / сост | G 1 | G 2 | G 3 | G 4 | G 5 | G 6 | G 7 | G 8 | G 9 | G 10 | G 11 | G 12 | G 13 | 0 | G 2 / 0 | G 3 / 0 | G 4 / 0 | G 5 / 0 | G 10 / 0 | G 11 / 0 | G 12 / 0 | G 13 / 0 | G 16 / 0 | G 17 / 0 | G 18 / 0 | G 20 / 0 | G 21 / 0 | 1 | G 6 / 0 | G 7 / 0 | G 8 / 0 | G 9 / 0 | - / - | G 14 / 0 | - / - | G 15 / 0 | - / - | - / - | - / - | G 19 / 0 | - / - |
|
|
|
|
|
|
|
|
|
|
|
|
|
| Вх / сост | G 14 | G 15 | G 16 | G 17 | G 18 | G 19 | G 20 | G 21 | G 23 | G 24 | G 25 | G 26 |
| 0 | G 23 / 0 | G 26 / 0 | G 22 / 0 | G 1 / 0 | G 13 / 0 | G 16 / 0 | G 10 / 1 | G 17 / 1 | G 25 / 1 | G 26 / 1 | G 21 / 0 | G 22 / 1 |
| 1 | - / - | - / - | - / - | - / - | G 15 / 1 | - / - | - / - | - / - | G 24 / 1 | - / - | - / - | - / - |
|
Закодуємо стану трьома розрядами: Стан / код | Q 4 Q 3 Q 2 Q 1 Q 0 | G 1 | 00000 | G 2 | 00001 | G 3 | 00010 | G 4 | 00011 | G 5 | 00100 | G 6 | 00101 | G 7 | 00110 | G 8 | 00111 | G 9 | 01000 | G 10 | 01001 | G 11 |
| 01010 |
G 12 | 01011 |
G 13 | 01100 |
G 14 | 01101 |
G 15 | 01110 |
G 16 | 01111 |
G 17 | 10000 |
G 18 | 10001 |
G 19 | 10010 |
G 20 | 10011 |
G 21 | 10100 |
G 22 | 10101 |
G 23 | 10110 |
G 24 | 10111 |
G 25 | 11000 |
G 26 | 11001 |
QQ * | D |
0 0 | 0 |
0 1 | 1 |
1 0 | 2 |
1 січня | 1 |
Таблиця переходів D-тригера:
Для випадку D-тригера кодованих таблиця збудження блоку пам'яті співпадає з кодованої таблицею переходів:
Стан / код | Q 4 Q 3 Q 2 Q 1 Q 0 | 0 | 1 |
|
| D 4 D 3 D 2 D 1 D 0 | D 4 D 3 D 2 D 1 D 0 |
G 1 | 00000 | 00001 | 00101 |
G 2 | 00001 | 00010 | 00110 |
G 3 | 00010 | 00011 | 00111 |
G 4 | 00011 | 00100 | 01000 |
G 5 | 00100 | 01001 | 00000 |
G 6 | 00101 | 01010 | 01101 |
G 7 | 00110 | 01011 | 00000 |
G 8 | 00111 | 01100 | 01110 |
G 9 | 01000 | 01111 | 00000 |
G 10 | 01001 | 10000 | 00000 |
G 11 | 01010 | 10001 | 00000 |
G 12 | 01011 | 10011 | 10010 |
G 13 | 01100 | 10100 | 00000 |
G 14 | 01101 | 10110 | 00000 |
G 15 | 01110 | 11001 | 00000 |
G 16 | 01111 | 10101 | 00000 |
G 17 | 10000 | 00000 | 00000 |
G 18 | 10001 | 01100 | 01110 |
G 19 | 10010 | 01111 | 00000 |
G 20 | 10011 | 01001 | 00000 |
G 21 | 10100 | 10000 | 00000 |
G 22 | 10101 | 00000 | 00000 |
G 23 | 10110 | 11000 | 10111 |
G 24 | 10111 | 11001 | 00000 |
G 25 | 11000 | 10100 | 00000 |
G 26 | 11001 | 10101 | 00000 |
Виконаємо конкатенацію кодів вхідних сигналів і кодів станів з порядку проходження змінних xQ 2 Q 1 Q 0 і заповнимо таблицю істинності для функцій виходу і збуджень.
Таблиця істинності функцій виходів і входів:
XQ 4 Q 3 Q 2 Q 1 Q 0 | D 4 D 3 D 2 D 1 D 0 | Y | 000000 | 00001 | 0 | 000001 | 00010 | 0 | 000010 | 00011 | 0 | 000011 | 00100 | 0 | 000100 | 01001 | 0 | 000101 | 01010 | 0 | 000110 | 01011 | 0 | 000111 | 01100 | 0 | 001000 | 01111 | 0 | 001001 | 10000 | 0 | 001010 | 10001 | 0 | 001011 | 10011 | 0 | 001100 | 10100 | 0 | 001101 | 10110 | 0 | 001110 | 11001 | 0 | 001111 | 10101 | 0 | 010000 | 00000 | 0 | 010001 | 01100 | 1 | 010010 | 01111 | 1 | 010011 | 01001 | 1 | 010100 | 10000 | 1 | 010101 | 00000 | 1 | 010110 | 11000 | 1 | 010111 | 11001 | 1 | 011000 | 10100 | 1 | 011001 | 10101 | 1 | 100000 | 00101 | 0 | 100001 | 00110 | 0 | 100010 | 00111 | 0 | 100011 | 01000 | 0 | 100100 | 00000 | 0 | 100101 | 01101 | 0 | 100110 | 00000 | 0 | 100111 | 01110 | 0 | 101000 | 00000 | 0 | 101001 | 00000 | 0 | 101010 | 00000 | 0 | 101011 | 10010 | 0 | 101100 | 00000 | 0 | 101101 | 00000 | 0 | 101110 | 00000 | 0 | 101111 | 00000 | 0 | 110000 | 00000 | 0 | 110001 | 01110 | 1 | 110010 | 00000 | 1 | 110011 | 00000 | 1 | 110100 | 00000 | 1 | 110101 | 00000 | 1 | 110110 | 10111 | 1 | 1101111 | 00000 | 1 | 111000 | 00000 | 1 | 111001 | 00000 | 1 |
Оскільки числова СДНФ форма ФАЛ має найкомпактнішу запис і дозволяє при необхідності перейти до будь-якого іншого опису цієї функції, за таблицею істинності функцій виходів і входів запишемо саме в числовій формі функції виходів Y, D 1, D 2, D 3, D 4, D 5 від
x Q 4 Q 3 Q 2 Q 1 Q 0. Y = D 4 = v010110v010111v011000v011001v101011v110110 D 3 = v010011v010110v010111v100011v100101v100111v110001 D 2 = D 1 = V100001v100010v100111v101011v110001v110110 D 0 = Для подальшої роботи необхідно мінімізувати отримані вихідні функції автомата. Мінімізують карти Одним з видів представлення ФАЛ від невеликого числа змінних (як правило, не більше 5) є діаграми Карно або Вейча, які будуються на розгортках багатовимірних кубів на площину. При цьому вершини куба представляються клітинами карти, координати яких збігаються з координатами відповідних вершин куба. Карта заповнюється шляхом позначки кодів вершин, відповідних наборів, на яких ФАЛ дорівнює одиниці. Іншими символами позначаються коди наборів, на яких ФАЛ не визначена. Таким чином, діаграма на карті Карно або Вейча відповідає уявленню ФАЛ в СДНФ. Якщо будується карта Карно для непарної кількості змінних в наборі, то на відстані одиниці ліворуч від вихідної карти для парного кількості змінних зображується повернена на 180 ° навколо осі, що проходить між вихідною і новою картами, нова карта тієї ж розмірності. Після цього в старшому розряді двійкових кодів наборів вихідної карти додаються незначущі нулі, а в старшому розряді нової картки додаються одиниці. Ці дві карти об'єднуються в одну більшої розмірності. Якщо будується карта Карно для парного кількості змінних в наборі, то на відстані одиниці знизу від вихідної карти для непарної кількості змінних зображується повернена на 180 ° навколо осі, що проходить між вихідною і новою картами, нова карта тієї ж розмірності. Після цього в старшому розряді двійкових кодів наборів вихідної карти додаються незначущі нулі, а в старшому розряді нової картки додаються одиниці. Ці дві карти об'єднуються в одну більшої розмірності. У картах набори змінних, на яких функція приймає поодинокі значення, позначаються нечисловими символами. Карта з нанесеними на ній значеннями ФАЛ називається діаграмою. Карти, на яких коди наборів зображуються у вісімковій системі числення, називаються картами Вейча. Мінімізація функцій за методом Квайна При мінімізації за методом Квайна в базисі І, АБО, НЕ вихідна ФАЛ задається в СДНФ Метою мінімізації є знаходження всіх первинних импликант і вибір деяких з них для мінімальної записи функції. Импликанта функції - деяка логічна функція, звертається в нуль при наборі змінних, на якому сама функція також дорівнює нулю. Тому будь-який кон'юнктивний терм, що входить до складу СДНФ, або група термів, з'єднаних знаками диз'юнкції є импликантами вихідної ФАЛ. Імпліканти мають поодинокі значення тільки на підмножині наборів з безлічі наборів, на яких вихідна ФАЛ дорівнює одиниці. Первинна импликанта функції - импликанта типу елементарної кон'юнкції деяких змінних, ніяка частина якої вже не є импликантой. Завдання мінімізації за методом Квайна вирішується шляхом попарного порівняння всіх импликант, що входять в ФАЛ, з метою виявлення можливості їх неповного склеювання з якоїсь змінної на проміжних етапах. При склеюванні знижується ранг термів. Склеювання проводиться до тих пір, поки не залишиться жодного терма, що допускає склеювання з яким-небудь іншим термо. Терми, які зазнали склеюванню, відзначаються. Невідмічені терми представляють собою первинні імпліканти. Після отримання безлічі всіх первинних импликант досліджується можливість знаходження найпростішої запису ФАЛ. Для цього складається таблиця, в першому рядку якій записані минтерм вихідної ФАЛ, а в першому стовпці записані всі знайдені первинні імпліканти. Клітини цієї таблиці позначаються в тому випадку, якщо первинна импликанта входить до складу будь-якого минтерм вихідної ФАЛ. Після цього завдання спрощення зводиться до того, щоб знайти таку мінімальну кількість первинних импликант, які покривають всі стовпці минтермов вихідної ФАЛ. Мінімізація функцій за методом Мак-Класкі Недоліком методу Квайна є - необхідність вичерпного попарного порівняння або зіставлення всіх минтермов на етапі знаходження первинних импликант. З ростом числа минтермов збільшується кількість попарних порівнянь. Числове подання ФАЛ дозволяє спростити самий трудомісткий перший етап. Всі минтерм СДНФ ФАЛ записуються у вигляді їх двійкових кодів, а всі коди розбиваються по числу одиниць на непересічні групи. Минтерм, що підлягають склеюванню, розрізняються тільки по одній змінній, а їхні коди - тільки в одному розряді. З цієї причини порівняно підлягають тільки двійкові коди минтермов сусідніх груп. Розглянувши декілька методів мінімізації ФАЛ, можна зробити висновок про те, що для рішення нашої задачі найбільш підходящим є метод Мак-Класкі. Мінімізуємо Y: Y = i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
| 2 | 010001 | 21 |
|
| 010010 | 22 |
|
| 010100 | 24 |
|
| 011000 | 30 |
| 3 | 010011 | 23 |
|
| 010101 | 24 |
|
| 010110 | 26 |
|
| 011001 | 31 |
|
| 110001 | 61 |
|
| 110010 | 62 |
|
| 110100 | 64 |
|
| 111000 | 70 |
| 4 | 010111 | 27 |
|
| 110011 | 63 |
|
| 110101 | 65 |
|
| 110110 | 66 |
|
| 111001 | 71 |
| 5 | 110111 | 67 |
|
Склеювання 1 i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
| 2 | 0100-1 | 21, 23 |
|
| 010-01 | 21, 25 |
|
| 01-001 | 21, 31 |
|
| -10001 | 21, 61 |
|
| 01001 - | 22, 23 |
|
| 010-10 | 22, 26 |
|
| -10010 | 22, 62 |
|
| 01010 - | 24, 25 |
|
| 0101-0 | 24, 26 |
|
| -10100 | 24, 64 |
|
| 01100 - | 30, 31 |
|
| -11000 | 30, 70 |
| 3 | 010-11 | 23, 27 |
|
| -10011 | 23, 63 |
|
|
| 0101-1 | 25, 27 |
|
| -10101 | 25, 65 |
|
| 01011 - | 26, 27 |
|
| -010110 | 26, 66 |
|
| -11001 | 31, 71 |
|
| 1100-1 | 61, 63 |
|
| 110-01 | 61, 65 |
|
| 11-001 | 61, 71 |
|
| 11001 - | 62, 63 |
|
| 110-10 | 62, 66 |
|
| 11010 - | 64, 65 |
|
| 1101-0 | 64, 65 |
|
| 11100 - | 64, 66 |
|
4 | -10111 | 27, 67 |
|
| 110-11 | 63, 67 |
|
| 1101-1 | 65, 67 |
|
| 11011 - | 66, 67 |
|
Склеювання 2
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
2 | 010 - 1 | 21, 23, 25, 27 |
|
| -100-1 | 21, 23, 61, 63 |
|
| -10-01 | 21, 25, 61, 65 |
|
| -1-001 | 21, 31, 61, 71 | A |
| 010-1 - | 22, 23, 26, 27 |
|
| -1001 - | 22, 23, 62, 63 |
|
| -10-10 | 22, 26, 62, 63 |
|
| 0101 - | 24, 25, 26, 27 |
|
| -1010 - | 24, 25, 64, 65 |
|
| -101-0 | 24, 26, 64, 66 |
|
| -1100 - | 30, 70, 31, 71 | B |
3 | -10-11 | 23, 27, 63, 67 |
|
| -101-1 | 25, 27, 65, 67 |
|
| -1011 - | 26, 27, 66, 67 |
|
| 110 - 1 | 61, 63, 65, 67 |
|
| 110-1 - | 62, 63, 66, 67 |
|
| 1101 - | 64, 65, 66, 67 |
|
Склеювання 3
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
2 | -10 - 1 | 21, 23, 25, 27, 61, 63, 65, 67 | C |
| - 10-1 - | 22, 23, 26, 27, 62, 63, 66, 67 | D |
| -101 - | 24, 25, 26, 27, 64, 65, 66, 67 | E |
|
|
|
|
|
|
|
|
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 30 | 31 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 70 | 71 |
A | ' |
|
|
|
|
|
|
| ' | ' |
|
|
|
|
|
|
| ' |
B |
|
|
|
|
|
|
| Ä | ' |
|
|
|
|
|
|
| Ä | ' |
C | ' |
| ' |
| ' |
| ' |
|
| ' |
| ' |
| ' |
| ' |
|
|
D |
| Ä | ' |
|
| ' | ' |
|
|
| Ä | ' |
|
| ' | ' |
|
|
E |
|
|
| Ä | ' | ' | ' |
|
|
|
|
| Ä | ' | ' | ' |
|
|
Y = -1100 - v -10-1 - v -101 -
Мінімізуємо D 4
D 4 = 001 001 v 001010 v 001011 v 001100 v 001101 v 001110 v 001111 v 010100 v
v 010110 v 010111 v 011000 v 011001 v 101011 v 110110
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
2 | 001001 | 11 |
|
| 001010 | 12 |
|
| 001100 | 14 |
|
| 010100 | 24 |
|
| 011000 | 30 |
|
3 | 001011 | 13 |
|
| 001101 | 15 |
|
| 001110 | 16 |
|
| 010110 | 26 |
|
| 011001 | 31 |
|
4 | 001111 | 17 |
|
| 010111 | 27 |
|
| 101011 | 53 |
|
| 110110 | 67 |
|
Склеювання 1
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
2 | 0010-1 | 11, 13 |
|
| 001-01 | 11, 15 |
|
| 0-1001 | 11, 31 | A |
| 00101 - | 12, 13 |
|
| 001-10 | 12, 16 |
|
| 00110 - | 14, 15 |
|
| 0011-0 | 14, 16 |
|
| 0101-0 | 24, 26 | B |
| 01100 - | 30, 31 | C |
3 | 001-11 | 13, 17 |
|
| -01011 | 13, 53 | D |
| 0011-1 | 15, 17 |
|
| 00111 - | 16, 17 |
|
| 01011 - | 26, 27 | E |
| -10110 | 26, 67 | F |
Склеювання 2
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
2 | 001 - 1 | 11, 13, 15, 17 | G |
| 001-1 - | 12, 13, 16, 17 | H |
| 0011 - | 14, 15, 16, 17 | I |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 24 | 26 | 27 | 30 | 31 | 53 | 67 |
A | ' |
|
|
|
|
|
|
|
|
|
| ' |
|
|
B |
|
|
|
|
|
|
| Ä | ' |
|
|
|
|
|
C |
|
|
|
|
|
|
|
|
|
| Ä | ' |
|
|
D |
|
| ' |
|
|
|
|
|
|
|
|
| Ä |
|
E |
|
|
|
|
|
|
|
| ' | Ä |
|
|
|
|
F |
|
|
|
|
|
|
|
| ' |
|
|
|
| Ä |
G | ' |
| ' |
| ' |
| ' |
|
|
|
|
|
|
|
H |
| Ä | ' |
|
| ' | ' |
|
|
|
|
|
|
|
I |
|
|
| Ä | ' | ' | ' |
|
|
|
|
|
|
|
D 4 = 0101-0 v 01100 - v -01011 v 01011 - v -10110 v 001-1 - v 0011 -
Мінімізуємо D 3
D 3 = 000100 v 000101 v 000110 v 000111 v 001000 v 001110 v 010001 v 010010 v
v010011v010110v010111v100011v100101v100111v110001
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
1 | 000100 | 4 |
|
| 001000 | 10 | A |
2 | 000101 | 5 |
|
| 000110 | 6 |
|
| 010001 | 21 |
|
| 010010 | 22 |
|
3 | 000111 | 7 |
|
| 001110 | 15 |
|
| 010011 | 23 |
|
| 010110 | 26 |
|
| 100011 | 43 |
|
| 100101 | 45 |
|
| 110001 | 61 |
|
4 | 010111 | 27 |
|
| 100111 | 47 |
|
Склеювання 1
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
1 | 00010 - | 4, 5 |
|
| 0001-0 | 4, 6 |
|
2 | 0001-1 | 5, 7 |
|
| -00101 | 5, 45 |
|
| 00011 - | 6, 7 |
|
| 00-110 | 6, 15 | C |
| 0-0110 | 6, 26 |
|
| 0100-1 | 21, 23 | D |
| -10001 | 21, 61 | E |
| 01001 - | 22, 23 |
|
| 010-10 | 22, 26 |
|
3 | 0-0111 | 7, 27 |
|
| -00111 | 7, 47 |
|
| 010-11 | 23, 27 |
|
| 01011 - | 26, 27 |
|
| 100-11 | 43, 47 | F |
| 1001-1 | 45, 47 |
|
|
|
|
|
Склеювання 2
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
1 | 0001 - | 4, 5, 6, 7 | G |
2 | -001-1 | 5, 7, 45, 47 | H |
| 0-011 - | 6, 7, 26, 27 | I |
| 010-1 - | 22, 23, 26, 27 | J |
| 4 | 10 | 5 | 6 | 21 | 22 | 7 | 15 | 23 | 26 | 43 | 45 | 61 | 27 | 47 |
A |
| Ä |
|
|
|
|
|
|
|
|
|
|
|
|
|
C |
|
|
| ' |
|
|
| Ä |
|
|
|
|
|
|
|
D |
|
|
|
| ' |
|
|
| ' |
|
|
|
|
|
|
E |
|
|
|
| ' |
|
|
|
|
|
|
| Ä |
|
|
F |
|
|
|
|
|
|
|
|
|
| Ä |
|
|
| ' |
G | Ä |
| ' | ' |
|
| ' |
|
|
|
|
|
|
|
|
H |
|
| ' |
|
|
| ' |
|
|
|
| Ä |
|
| ' |
I |
|
|
| ' |
|
| ' |
|
| ' |
|
|
| ' |
|
J |
|
|
|
|
| Ä |
|
| ' | ' |
|
|
| ' |
|
D 3 = 001000 v 00-110 v -10001 v 100-11 v 0001 - v -001-1 v 010-1 -
Мінімізуємо D 2
D 2 = 000 011 v 000111 v 001000 v 001100 v 001101 v 001111 v 010001 v 010010 v
v 011000 v 011001 v 100000 v 100001 v 100010 v 100101 v 100111 v 110001 v 110110
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
1 | 001000 | 10 |
|
| 100000 | 40 |
|
2 | 000011 | 3 |
|
| 001100 | 14 |
|
| 010001 | 21 |
|
| 010010 | 22 | A |
| 011000 | 30 |
|
| 100001 | 41 |
|
| 100010 | 42 |
|
| 100100 | 44 |
|
3 | 000111 | 7 |
|
| 001101 | 15 |
|
| 011001 | 31 |
|
| 110001 | 61 |
|
4 | 001111 | 17 |
|
| 100111 | 47 |
|
| 110110 | 66 | B |
Склеювання
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
1 | 001-00 | 10, 14 | C |
| 0-1000 | 10, 30 | D |
| 10000 - | 40, 41 | E |
| 1000-0 | 40, 42 | F |
| 100-00 | 40, 44 | G |
2 | 000-11 | 3, 7 | H |
| 00110 - | 14, 15 | I |
| 01-001 | 21, 31 | J |
| -10001 | 21, 61 | K |
| 01100 - | 30, 30 | L |
| 1-0001 | 41, 61 | M |
3 | 00-111 | 7, 17 | N |
| -00111 | 7, 41 | O |
| 0011-1 | 15, 17 | P |
| 3 | 7 | 10 | 14 | 15 | 17 | 21 | 22 | 30 | 31 | 40 | 41 | 42 | 44 | 47 | 61 | 66 |
A |
|
|
|
|
|
|
| Ä |
|
|
|
|
|
|
|
|
|
B |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Ä |
C |
|
| ' | ' |
|
|
|
|
|
|
|
|
|
|
|
|
|
D |
|
| ' |
|
|
|
|
| ' |
|
|
|
|
|
|
|
|
E |
|
|
|
|
|
|
|
|
|
| ' | ' |
|
|
|
|
|
F |
|
|
|
|
|
|
|
|
|
| ' |
| Ä |
|
|
|
|
G |
|
|
|
|
|
|
|
|
|
| ' |
|
| Ä |
|
|
|
H | Ä | ' |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I |
|
|
| ' | ' |
|
|
|
|
|
|
|
|
|
|
|
|
J |
|
|
|
|
|
| ' |
|
| ' |
|
|
|
|
|
|
|
K |
|
|
|
|
|
| ' |
|
|
|
|
|
|
|
| ' |
|
L |
|
|
|
|
|
|
|
| ' | ' |
|
|
|
|
|
|
|
M |
|
|
|
|
|
|
|
|
|
|
| ' |
|
|
| ' |
|
N |
| ' |
|
|
| ' |
|
|
|
|
|
|
|
|
|
|
|
O |
| ' |
|
|
|
|
|
|
|
|
|
|
|
| Ä |
|
|
P |
|
|
|
| ' | ' |
|
|
|
|
|
|
|
|
|
|
|
D 2 = 010 010 v 110110 v 1000-0 v 100-00 v 000-11 v -00111
Мінімізуємо D 1
D 1 = 000001 v 000010 v 000101 v 000110 v 001000 v 001011 v 001101 v 010010 v
V 100001 v 100010 v 100111 v 101011 v 110001 v 110110
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
1 | 000001 | 1 |
|
| 000010 | 2 |
|
| 001000 | 10 | A |
2 | 000101 | 5 |
|
| 000110 | 6 |
|
| 010010 | 22 |
|
| 100001 | 41 |
|
| 100010 | 42 |
|
3 | 001011 | 13 |
|
| 001101 | 15 |
|
| 110001 | 61 |
|
4 | 100111 | 47 | B |
| 101011 | 53 |
|
| 110110 | 66 | C |
Склеювання
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
1 | 000-01 | 1, 5 | D |
| -00001 | 1, 41 | E |
| 000-10 | 2, 6 | F |
| 0-0010 | 2, 22 | G |
| -00010 | 2, 42 | H |
2 | 00-101 | 5, 15 | I |
| 1-0001 | 41, 61 | J |
3 | -01011 | 13, 53 | K |
| 1 | 2 | 5 | 6 | 10 | 13 | 15 | 22 | 41 | 42 | 47 | 53 | 61 | 66 |
A |
|
|
|
| Ä |
|
|
|
|
|
|
|
|
|
B |
|
|
|
|
|
|
|
|
|
| Ä |
|
|
|
C |
|
|
|
|
|
|
|
|
|
|
|
|
| Ä |
D | ' |
| ' |
|
|
|
|
|
|
|
|
|
|
|
E | ' |
|
|
|
|
|
|
| ' |
|
|
|
|
|
F |
| ' |
| Ä |
|
|
|
|
|
|
|
|
|
|
G |
| ' |
|
|
|
|
| Ä |
|
|
|
|
|
|
H |
| ' |
|
|
|
|
|
|
| Ä |
|
|
|
|
I |
|
| ' |
|
|
| Ä |
|
|
|
|
|
|
|
J |
|
|
|
|
|
|
|
| ' |
|
|
| Ä |
|
K |
|
|
|
|
| Ä |
|
|
|
|
| Ä |
|
|
D 1 = 001000 v 100111 v 110110 v 000-10 v 0-0010 v -00010 v 00-101 v 1-0001 v -01011
Мінімізуємо D 0
D 0 = 000000 v 000010 v 000100 v 000110 v 001000 v 001010 v 001011 v 001110 v
V 001111 v 010010 v 010011 v 010111 v 011001 v 100000 v 100010 v 100101 v 110110
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
0 | 000000 | 0 |
|
1 | 000010 | 2 |
|
| 000100 | 4 |
|
| 001000 | 10 |
|
| 100000 | 40 |
|
2 | 000110 | 6 |
|
| 001010 | 12 |
|
| 010010 | 22 |
|
| 100010 | 42 |
|
3 | 001011 | 13 |
|
| 001110 | 16 |
|
| 010011 | 23 |
|
| 011001 | 31 | A |
| 100101 | 45 | B |
4 | 001111 | 17 |
|
| 010111 | 27 |
|
| 110110 | 66 | D |
Склеювання 1
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
0 | 0000-0 | 0, 2 |
|
| 000-00 | 0, 4 |
|
| 00-000 | 0, 10 |
|
| -00000 | 0, 40 |
|
1 | 00-010 | 2, 12 |
|
| 0-0010 | 2, 22 | E |
| -00010 | 2, 42 |
|
| 000-10 | 2, 6 |
|
| 0001-0 | 4, 6 |
|
| 0010-0 | 10, 12 |
|
| 1000-0 | 40, 42 |
|
2 | 00101 - | 12, 13 |
|
| 001-10 | 12, 16 |
|
| 01001 - | 22, 23 | F |
| 00-110 | 6, 16 |
|
3 | 001-11 | 13, 17 |
|
| 00111 - | 16, 17 |
|
| 010-11 | 23, 27 | G |
Склеювання 2
i | x Q 4 Q 3 Q 2 Q 1 Q 0 | Вісімкове число |
|
0 | 000 - 0 | 0, 2, 4, 6 | H |
| 00-0-0 | 0, 2, 10, 12 | I |
| -000-0 | 0, 2, 40, 42 | J |
1 | 00 - 10 | 2, 12, 6, 16 | K |
2 | 001-1 - | 12, 13, 16, 17 | L |
| 0 | 2 | 4 | 6 | 10 | 12 | 13 | 16 | 17 | 22 | 23 | 27 | 31 | 40 | 42 | 45 | 66 |
A |
|
|
|
|
|
|
|
|
|
|
|
| Ä |
|
|
|
|
B |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Ä |
|
D |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Ä | E |
| ' |
|
|
|
|
|
|
| ' |
|
|
|
|
|
|
| F |
|
|
|
|
|
|
|
|
| ' | ' |
|
|
|
|
|
| G |
|
|
|
|
|
|
|
|
|
| ' | Ä |
|
|
|
|
| H | ' | ' | Ä | ' |
|
|
|
|
|
|
|
|
|
|
|
|
| I | ' | ' |
|
| Ä | ' |
|
|
|
|
|
|
|
|
|
|
| J | ' | ' |
|
|
|
|
|
|
|
|
|
|
| Ä | Ä |
|
| K |
| ' |
| ' |
| ' |
| ' |
|
|
|
|
|
|
|
|
| L |
|
|
|
|
| ' | Ä | ' | Ä |
|
|
|
|
|
|
|
|
D 0 = 011001 v 100101 v 110110 v 010-11 v 000 - 0 v 00-0-0 v -000-0 v 00 - 10 v 001-1 - Висновок Для отримання оптимального варіанта кодування необхідно зіставляти результати мінімізації комбінаційних схем при використанні всіх можливих варіантів кодування. Мінімальний варіант побудови принципової схеми може бути отриманий тільки після перебору і порівняння всіх можливих варіантів побудови цифрового пристрою. Для практичного використання методів мінімізації виключне значення має інженерна інтуїція при виборі варіантів кодування та мінімізації. Функції виходу цифрового автомата потрібно задавати порівняно рідко, оскільки найчастіше застосовуються цифрові автомати, не мають вихідного комбінаційної схеми. Для більш складних цифрових автоматів вхідні комбінаційна схема, як правило, представляє собою перетворювач коду, або шифратор, стану блок пам'яті цифрового автомата у вихідний код цифрового автомата. Для більшості стандартних застосувань вихідні комбінаційні схеми цифрових автоматів мінімізовані, розроблені та виготовлені у вигляді інтегральних схем. Таким чином, мета мінімізації вихідний комбінаційної цифрового автомата найчастіше зводиться до вибору інтегральних мікросхем для конкретного використання. Для структурного синтезу цифрових автоматів бажано застосовувати табличні методи, так як вони виконуються в більш суворої формі, ніж структурний синтез по графу, який вимагає величезної уваги на процесах синтезу та перевірки його результатів. Кількість помилок при застосуванні методу структурного синтезу по графу набагато більше кількості помилок при використанні табличного методу структурного синтезу при всіх інших однакових умовах виконання процесу синтезу. У ході виконання курсової роботи було вироблено побудова кодопреобразователя за заданими вхідним і вихідним функцій. У процесі виконання роботи нами були придбані практичні навички з курсів «Дискретна математика» та «Цифрові автомати». Література Гуділін А.В. Цифрова схемотехніка. Челябінськ, 2000. Іванов В.І. Синтез цифрових автоматів для систем зв'язку та управління. Челябінськ, 1980 Щелкунов М.М., Діанов А.П. Процедури програмування логічних матриць, - Мікропроцесорні засоби і системи, 1986, № 2. Іванов В.І. Синтез цифрових автоматів для систем зв'язку та управління, Челябінськ, ЧПІ, 1980. Баранов СІ. Синтез мікропрограмних автоматів. - Л.: Енергія, 1979. Електронний конспект лекцій Гуділін Олексій Євгенович. Конспект лекцій з курсу цифрові автомати. ЮУрГУ 2004.
Додати в блог або на сайт
Цей текст може містити помилки.
Програмування, комп'ютери, інформатика і кібернетика | Курсова
399.2кб. | скачати
Схожі роботи:
Побудова діаграм
Побудова організації
Побудова Декарта
Побудова бухгалтерського балансу
Побудова структури організації
Побудова потенційної діаграми
Побудова скінченних множин
Побудова системного аналізу
Побудова концептуальної моделі
|