Метод каскадів дозволяє мінімізувати трудомісткість синтезу логічної схеми за рахунок зниження розмірності синтезується функції і за рахунок використання спеціального структурного модуля - модуля виключення змінної.
В основі методу лежить теорема Шеннона:
Теорема Шеннона. Будь-яка, відмінна від тотожного нуля логічна функція f (x1, ..., xn) подана в вигляді
Функції f (x1, ..., xi-1, 1, xi + 1 ..., xn) і f (x1, ..., xi-1, 1, xi + 1 ..., xn) виходять підстановкою в f (x1, ..., xn ) замість змінної xi значень 1 і 0, відповідно. Розмірність цих функцій на 1 менше вихідної. Функції f (x1, ..., xi-1, 1, xi + 1 ..., xn) і f (x1, ..., xi-1, 1, xi + 1 ..., xn) називають залишковими функціями при розкладанні f (x1, ... , xn) за змінної xi одиничної і нульовий, відповідно. Надалі, ці функції для стислості будуть позначатися як і. відповідно.
У загальному вигляді теорема Шеннона формулюється так:
Це означає, що при розкладанні функції по k-змінним виходить 2 k залишкових функцій, кожна з яких залежить від n-k змінних.
Слідство з теореми Шеннона. Граничне розкладання функції по n-змінним є досконала діз'юнктівная нормальна форма (СовДНФ).
Дійсно, розкладання Шеннона буде представлено диз'юнкція констітуєнт, кожна з яких кон'юнктивний пов'язана із залишковою функцією-константою. Функція константа приймає має значення 1, якщо відповідна їй конституента є одиничною, і 0 - в іншому випадку.
Для стислості розкладання Шеннона по одній змінної представляється як. Якщо припустити, що є конструктивний блок, який реалізує цю виставу (блок виключення змінної - БІП), його внутренняю структура в класичному базисі повинна мати такий вигляд:
Метод каскадів можна уявити як процедуру послідовного виключення змінних:
- на першому кроці - з вихідної функції виключається деяка змінна, яка подається до лівого входу БІПА, а до нижніх відповідних входів БІПА підключаються одинична і нульова залишкові функції недоступні з цієї змінної;
- далі до кожної залишкової функції застосовується зазначена в попередньому кроці послідовність дій.
Зазначена процедура застосовується до тих пір, поки розмірність залишкових функцій не буде перевищувати 2. Такі прості функції доцільно синтезувати не шляхом каскадів, а шляхом безпосереднього моделювання в заданому логічному базисі.
1. Вихідна функція для методу каскадів може бути задана в будь-якому вигляді (її мінімізація або приведення до якого-небудь стандартного вигляду не потрібно)