Редактирование: Метод Лупанова синтеза схем

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 5: Строка 5:
  
 
== Представление функции ==
 
== Представление функции ==
[[Файл:Lupanov fig1.png|450px|thumb|right|Рис. <tex>1</tex>. Описываемая таблица истинности, разделённая на полосы]]
+
[[Файл:Lupanov fig1.png|450px|thumb|right|Рис. 1. Описываемая таблица истинности, разделённая на полосы]]
 
Поделим аргументы функции на два блока: первые <tex>k</tex> и оставшиеся <tex>(n - k)</tex>.
 
Поделим аргументы функции на два блока: первые <tex>k</tex> и оставшиеся <tex>(n - k)</tex>.
  
Для удобства дальнейших рассуждений представим булеву функцию в виде таблицы, изображённой на рис. <tex>1</tex>. Строки индексируются значениями первых <tex>k</tex> переменных, столбцы — значениями оставшихся <tex>(n - k)</tex>; таким образом, на пересечении столбца и строки находится значение функции для соответствующего набора аргументов.
+
Для удобства дальнейших рассуждений представим булеву функцию в виде таблицы, изображённой на рис. 1. Строки индексируются значениями первых <tex>k</tex> переменных, столбцы — значениями оставшихся <tex>(n - k)</tex>; таким образом, на пересечении столбца и строки находится значение функции для соответствующего набора аргументов.
  
 
== Разделение на полосы ==
 
== Разделение на полосы ==
Строка 21: Строка 21:
  
 
== Функция для одной полосы ==
 
== Функция для одной полосы ==
[[Файл:Lupanov_fig2.png|330px|thumb|right|Рис. <tex>2</tex>. Значения, возвращаемые функцией <tex>g_{ij}</tex>]]
+
[[Файл:Lupanov_fig2.png|330px|thumb|right|Рис. 2. Значения, возвращаемые функцией <tex>g_{ij}</tex>]]
 
Пусть для некоторого <tex>i</tex>
 
Пусть для некоторого <tex>i</tex>
 
* <tex>\beta_{j}</tex> {{---}} произвольный столбец <tex>i</tex>-й полосы <tex>j</tex>-го сорта (точное положение столбца далее не будет иметь значения, по определению сорта)
 
* <tex>\beta_{j}</tex> {{---}} произвольный столбец <tex>i</tex>-й полосы <tex>j</tex>-го сорта (точное положение столбца далее не будет иметь значения, по определению сорта)
Строка 32: Строка 32:
 
\end{cases}</tex>
 
\end{cases}</tex>
  
Другими словами, если строка, соответствующая аргументам функции <tex>x_1, x_2, \ldots, x_k</tex>, находится в <tex>i</tex>-й полосе, то функция возвращает значение, записанное в столбце сорта <tex>j</tex> для этой строки. Если же эта строка находится в другой полосе, то функция вернёт <tex>0</tex>. Иллюстрация принципа работы функции <tex>g_{ij}</tex> приведена на рис. <tex>2</tex>.
+
Другими словами, если строка, соответствующая аргументам функции <tex>x_1, x_2, \ldots, x_k</tex>, находится в <tex>i</tex>-й полосе, то функция возвращает значение, записанное в столбце сорта <tex>j</tex> для этой строки. Если же эта строка находится в другой полосе, то функция вернёт <tex>0</tex>. Иллюстрация принципа работы функции <tex>g_{ij}</tex> приведена на рис. 2.
 
=== Вывод исходной функции для фиксированной части параметров ===
 
=== Вывод исходной функции для фиксированной части параметров ===
 
Поскольку изначальный столбец <tex>(\sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_{n})</tex> складывается из столбцов соответствующих сортов в полосах,
 
Поскольку изначальный столбец <tex>(\sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_{n})</tex> складывается из столбцов соответствующих сортов в полосах,
Строка 38: Строка 38:
 
где <tex>j_i</tex> {{---}} номер сорта столбца полосы <tex>i</tex>, являющегося соответствующей частью столбца <tex>(\sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_{n})</tex>.
 
где <tex>j_i</tex> {{---}} номер сорта столбца полосы <tex>i</tex>, являющегося соответствующей частью столбца <tex>(\sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_{n})</tex>.
  
== Мультиплексор и демультиплексор ==
+
== Мультиплексор и дешифратор ==
{{main|Мультиплексор и демультиплексор}}
+
Для упрощения доказательства теоремы будем использовать элементы '''''мультиплексор''''' и '''''дешифратор'''''.
 
 
Для упрощения доказательства теоремы будем использовать элементы '''''мультиплексор''''' и '''''демультиплексор'''''.
 
 
{{
 
{{
 
Определение|definition=
 
Определение|definition=
Строка 50: Строка 48:
 
}}{{
 
}}{{
 
Определение|definition=
 
Определение|definition=
'''Демультиплексор''' (''англ.'' demultiplexer) {{---}} логический элемент, получающий на вход
+
'''Дешифратор''' (или демультиплексор, ''англ.'' demultiplexer) {{---}} логический элемент, получающий на вход
 
* булево значение <tex>z</tex>;
 
* булево значение <tex>z</tex>;
 
* <tex>n</tex>-значное число <tex>x</tex> в двоичном представлении
 
* <tex>n</tex>-значное число <tex>x</tex> в двоичном представлении
Строка 56: Строка 54:
 
}}
 
}}
 
{|
 
{|
|[[Файл:Mux_demux.png|500px|thumb|Мультиплексор слева, демультиплексор справа]]
+
|[[Файл:Mux_demux.png|500px|thumb|Мультиплексор слева, дешифратор справа]]
 
|}
 
|}
  
Оба элемента представимы схемами с числом элементов <tex>O(2^n)</tex> с помощью базиса <tex>B</tex>.
+
Оба элемента представимы схемами с числом элементов <tex>O(2^n)</tex> с помощью базиса <tex>B</tex>. Доказательство этого факта у читателя будет возможность рассказать на практике.
  
 
== Доказательство ==
 
== Доказательство ==
Строка 67: Строка 65:
  
 
Для удобства поделим схему на блоки:
 
Для удобства поделим схему на блоки:
* '''Блок A''' {{---}} демультиплексор, которому на вход подали <tex>1</tex> и <tex>(x_1, x_2, \ldots, x_k)</tex> в качестве двоичного представления числа.
+
* '''Блок A''' {{---}} дешифратор, которому на вход подали <tex>1</tex> и <tex>(x_1, x_2, \ldots, x_k)</tex> в качестве двоичного представления числа.
* '''Блок B''' {{---}} схемная реализация всех <tex>g_{ij}</tex>. Функцию <tex>g_{ij}</tex> можно реализовать как <tex dpi="145">\bigvee\limits_{\beta_l = 1} y_{il}</tex>, где <tex>y_{il}</tex> {{---}} выдал ли демультиплексор <tex>1</tex> на <tex>l</tex>-м выходе <tex>i</tex>-й полосы.
+
* '''Блок B''' {{---}} схемная реализация всех <tex>g_{ij}</tex>. Функцию <tex>g_{ij}</tex> можно реализовать как <tex dpi="145">\bigvee\limits_{\beta_l = 1} y_{il}</tex>, где <tex>y_{il}</tex> {{---}} выдал ли дешифратор <tex>1</tex> на <tex>l</tex>-м выходе <tex>i</tex>-й полосы.
* '''Блок C''' {{---}} схемная реализация всех <tex>f(x_1, x_2, \ldots, x_k, \sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_n)</tex>. ''(здесь <tex>\sigma_i</tex> - фиксированные параметры, см. п. <tex>3.1</tex>)''
+
* '''Блок C''' {{---}} схемная реализация всех <tex>f(x_1, x_2, \ldots, x_k, \sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_n)</tex>. ''(здесь <tex>\sigma_i</tex> - фиксированные параметры, см. п. 3.1)''
 
* '''Блок D''' {{---}} мультиплексор, получающий на вход все <tex>f(x_1, x_2, \ldots, x_k, \sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_n)</tex> и параметры функции <tex>x_{k + 1}, x_{k + 2}, \ldots, x_n</tex> в качестве двоичного представления числа. '''''Результат работы схемы''''' {{---}} вывод мультиплексора.
 
* '''Блок D''' {{---}} мультиплексор, получающий на вход все <tex>f(x_1, x_2, \ldots, x_k, \sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_n)</tex> и параметры функции <tex>x_{k + 1}, x_{k + 2}, \ldots, x_n</tex> в качестве двоичного представления числа. '''''Результат работы схемы''''' {{---}} вывод мультиплексора.
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)