201209201101


Digitaaltehnika II

Учебные материалы: 
На эстонском:
            
  1. U.Kald. Impulss- ja arvutus- tehnika alused, 1990
         
На других языках

  2. C. Petzold, Code: The Hidden Language of Computer Hardware and Software, 2001 (Есть русский перевод).
            
Сроки и содержание обучения (содержание учебной работы по неделям: тема(ы), форма обучения (лекция, семинар, групповая работа, дискуссия, практическая работа), рассматриваемые понятия, теории, подходы и т.д.), самостоятельная работа по освоению предмета.

  +------+-----+----------------------------------+---------------+
  |Неделя|Часов|Описание темы                     |Самостоятельная|
  |No    |(ч)  |                                  |домашняя работа|
  +------+-----+----------------------------------+---------------+
  |      |     |Последовательные схемы. Временные |               |
  | 1    |  2  |диаграммы и таблицы состояния.    |               |
  |      |     |Асинхронные триггеры. RS-триггер. |               |
  +------+-----+----------------------------------+---------------+       
  |      |     |Синхронные триггеры. D-триггер,   |               |
  | 2    |  2  |JK-триггер, T-триггер.            |               |
  |      |     |Динамические триггеры.            |               |
  +------+-----+----------------------------------+---------------+
  |      |     |Конечные автоматы. Автоматы Мура  |               |
  | 3    |  2  |и Мили.                           |               |
  +------+-----+----------------------------------+---------------+
  |      |     |Параллельные регистры.            |               |
  | 4    |  2  |Последовательные регистры         |               |
  |      |     |Сдвиговые регистры.               |               |
  +------+-----+----------------------------------+---------------+
  |      |     |Последовательный двоичный счетчик.|               |
  | 5    |  2  |Параллельный двоичный счетчик.    |               |
  +------+-----+----------------------------------+---------------+
  |      |     |Счетчики с переносом для целых    |               |
  | 6    |  2  |чисел. Делители частоты.          |               |
  +------+-----+----------------------------------+---------------+
  |      |     |Упражнения. Синтез простых авто-  |               |
  | 7    |  2  |матов с помощью программы Logisim.|               |
  +------+-----+----------------------------------+---------------+
  |      |     |Контрольная работа. Синтез        |               |
  | 8    |  2  |счетчика.                         |               |
  +------+-----+----------------------------------+---------------+
  | 9    |  2  |Постоянные запоминающие устройства|               |
  +------+-----+----------------------------------+---------------+
  |      |     |Статическая оперативная память    |               |
  |10    |  2  |SRAM.                             |               |
  +------+-----+----------------------------------+---------------+
  |11    |  2  |Флеш-память NAND и NOR            |               |
  +------+-----+----------------------------------+---------------+
  |      |     |Цифро-Аналоговые преобразователи. |               |
  |12    |  2  |Аналого-цифровые преобразователи. |               |
  +------+-----+----------------------------------+---------------+
  |13    |  2  |Итоги                             |               |
  +------+-----+----------------------------------+---------------+
  |14    |  2  |Зачет                             |               |
  +------+-----+----------------------------------+---------------+


Занятие 0. Введение
       
Мотивация изучения цифровой техники.

При рассмотрении доступных приборов и информации по их созданию следует исходить из мотивации их создания и мотивации наполнения ими рынка.

  - Одним из важнейших мотиваторов являются деньги, образующие в сочетании с компьютерными сетями для совершения финансовых операций самообучающиеся нейронные сети с изменяющимся, благодаря самообучению, поведением.

  - Существенный мотиватор - жажда творчества, снижение роли денежной составляющей в списке мотиваторов - проекты OpenHardware.
    
  - Административно - бюрократический мотиватор (если я буду знать предмет, то получу диплом, место работы и т.п.) 
    
  - Находясь в зоне евро, более децентрализованной по сравнению с долларовой зоной, важным мотиватором является любознательность - каждый индивидум должен владеть объективной картиной (понимать а не верить слепо там, где это возможно). 
    
  - Стремление к созданию совершенной машины, превосходящей ее создателя (человека, другой машины, а чаще их комбинации).
    
  - Использование исторически накопившихся знаний. Хочу использовать в свое время освоенные курсы латыни и цифровой техники, например в медицине, программировании PLC и.т.п.)
    
  - Принцип подобия. Надеюсь использовать полученные знания в других областях (например генетике).
    
  - Знание истории предмета (Интересуюсь историей):
  
    http://ru.wikipedia.org/wiki/История_вычислительной_техники
         
    http://sixrevisions.com/resources/the-history-of-computers-in-a-nutshell/


Современные методы синтеза цифровых схем.

  - Программирование структуры матриц PAL, FPGA, CPLD.
  
  - Создание аппаратуры методами программирования. Языки описания схем (hardware description languages - HDL) VHSIC, Abel, VHDL, Verilog и подобные. Симуляторы синтезированных таким образом схем.
    
  - Синхронные и асинхронные схемы. Экономия энергии в асинхронных схемах. Об архитектуре ARM. (Cortex микропроцессоры и FPGA)
    
  - Аппаратная реализация систем счисления с основанием, отличающимся от двух (гибридные схемы 2-4 и 2-8. MLС (multi level cell) флеш-память (англ. flash memory) в картах памяти SDXC и SSD накопителях.
    
    
Ограничение доступа к информации.

                              "Information wants to be free"
                              
                              1994. Автор неизвестен.

Не вся информация имеется в свободном доступе.

  - Для определения способности учеником пользоваться опеределенным видом информации, нет необходимости в ее публикации в открытом доступе. После успешного прохождения тестов по математике, физике, электронике, можно предоставить право доступа через регистрацию. Хищение и публикация такой информации в торрентах и других видах раздач носит, как правило, ограниченный во времени и по тематике характер.
    
Информация, имеющаяся в свободном доступе, имеет ценность после получения обратной связи о ее использовании. 


Примеры

  - Шахматный компьютер (1997, обыгрывает чемпиона мира).
  - Диагностика заболеваний с помощью поисковых систем (Google, Yahoo, Bing, Яндекс и.т.п.) (http://vimeo.com/33395872)
  - Танцующие роботы-андроиды (http://www.3dnews.ru/news/631470, http://www.3dnews.ru/editorial/630543)

  
Упражнения

Назовите сказки, в которых фигурирует число три.

  0. "Три поросёнка"
  1. "Огниво" - три комнаты   
  2. "Три толстяка"
  3. "Три орешка для Золушки"
  4. У царей во многих сказках - три сына
  5. "Аленький цветочек" - три дочери


Занятие 1.

Содержание курсов Digitaaltenika I и Digitaaltenika II

На наших занятиях мы будем рассматривать электронные схемы, оперирующие двумя уровнями напряжения (тока) - логический ноль и логическая единица. Предполагается, что Вы знакомы с базовыми курсами elektrotehnika, elektroonika и digitaaltehnika I. Для практических занятий дома и в классе, а также для иллюстраций мы будем использовать симулятор цифровых электронных схем Logisim, который Вы можете скачать по адресу:

  http://ozark.hendrix.edu/~burch/logisim/download.html
  http://sourceforge.net/projects/circuit/files/latest/download
  
Курс охватывает комбинационные схемы, последовательные схемы а также простейшие автоматы включая симулятор простой машины фон Неймана (ПМН). Достаточно просто изготовить самостоятельно простейшие механические логические элементы: буфер, инвертор и элемент ИЛИ. Поскольку для создания цифровой схемы любой степени сложности больше ничего не нужно, возникает соблазн сделать очень много таких элементов (конрад Цузе, 1938, порядка 100000 элементов). Его краткая характеристика приведена ниже

  Память 64 22х битных слова
  Тактовая частота 1 Герц
  Количество регистров 2 по 22 бита
  Вес 1 тонна
  Арифметический узел (сложение 5 секунд, вычитание, 
                       умножение 10 секунд, деление)
  Ввод-вывод десятичные числа с плавающей запятой.
  Источник http://en.wikipedia.org/wiki/Z1_(computer)#Specifications
                       
Главный враг всякой сложной механической машины - низкая надежность (после двух лет постройки Z1 не работал). Но наша задача не в том, чтобы в одиночку воссоздать Терминатора (см. фильм Терминатор, 1984) из песка (на что безусловно потребуется очень много времени), а в том чтобы дать представление о том, как работают цифровые устройства. О том, почему это может быть полезно, мы говорили на вводном занятии.

Для освежения в памяти первой части курса Digitaaltehnika I, рекомендуется ознакомиться с моим материалом 2002 года, приводимым далее (следует иметь ввиду, что десять лет назад люди достаточно точно прогнозировали основные параметры компьютерной техники 2012-2013 годов. Что было совершенно неясно, это на каких принципах будет строится сосуществование машин (компьютерных сетей, роботов) и людей. Далее приводится курс Digitaaltehnika I за 2002 год (исправлены некоторые опечатки и изменен формат представления информации.

Цифровые устройства. Заметки.                  
20021231
Кирилл Нелус      

Теоретические основы цифровой техники.

  - Двоичная арифметика.
  - Булева алгебра.
  - Теория конечных автоматов.


Системы счисления.

Цифра. Число. Разряд. Позиционные системы.

Проблема: сосчитать мамонтов. Не умеем считать. Ставим в соответствие каждому мамонту символ "I". Считаем:

   мамонт  ->  I
   мамонт, мамонт -> II
   мамонт, мамонт, мамонт -> III
   мамонт, мамонт, мамонт, мамонт -> IIII
   мамонт, мамонт, мамонт, мамонт, мамонт -> IIIII
   ...
   
После некоторой тренировки "III" воспринимается как один символ. Возникает новая проблема: отличие IIIII от IIIIII не бросается в глаза. Ставим в соответствие "IIIII" символ "V". Считаем:

   IIIII   ->  V
   IIIIII  ->  VI
   IIIIIII ->  VII
   ...
   
Семь воспринимается как пять и два. Возникает идея сложения. Вводим новые символы: "+" сложить, X - десять. Вводим понятие числа - изображение количества с помощью символов. Записываем

   V + V = X
   V + V + V = XV
   ...

Замечаем зависимость. Возникает идея умножения. Вводим новый символ "*".

   I * V = V
   II * V = X
   III * V = XV
   ...
   
Замечаем, что число может быть записано как сумма произведений:

   III * X + V * I

Возникает идея позиционной записи. Вводим новые символы: 1, 2, 3, 4, 5, 6, 7, 8, 9 - цифры. Тринадцать записываем как 13  ( или 1 * X + 3).

Возникает проблема - как, например записать "десять" с помощью новых символов? Вводим новый символ "0". Десять записываем как 10 ( или 1*X + 0*1 )

Записываем все большие числа: 666, 1984

Цифр в числе так много, что начинаем считать уже сами цифры. Порядковый номер цифры в числе называем разряд.

  число:  1 9 8 4
  разряд: 3 2 1 0

Замечаем зависимость - цифру нужно умножать на 10 столько раз каков разряд, в который она записана. Саму запись числа называем позиционной.

   666 = 6 * 10 * 10 + 6 * 10 + 6
  1984 = 1 * 10 * 10 * 10 + 9 * 10 * 10 + 8 * 10 + 4

Вводим новое действие - степень.

    0         1          2               3
  10 = 1    10 = 10    10 = 10 * 10    10 = 10 * 10 * 10

Обобщаем: запись числа в виде выражения

             3        2        1        0
  1984   = 10 * 1 + 10 * 9 + 10 * 8 + 10 * 4
      10

называем "полином". Цифру 10 считаем основанием. На планете проходит миллион лет. На часах проходит 2 минуты. Наступает 20-й век.


Двоичная система счисления.

Считаем все большие числа. Не успеваем считать. Хотим построить счетную машину. Замечаем, что основание 10 было выбрано по числу пальцев на руках. Делаем вывод, что можно создать и другие позиционные системы счисления. Ищем минимальное основание. Это 1. Пытаемся считать мамонтов - ноль, ноль... Странно, помнится, раньше удавалось. Увеличиваем основание. Это 2. Считаем: 0, 1, 10, 11, 100. Пишем полином для основания 2.

           3       2       1       0
  1101  = 2 * 1 + 2 * 1 + 2 * 0 + 2 * 1
      2


Бит. Ниббл. Байт. Слово. 

Считаем все большие числа. 10010100101001111010101000010101. Рябит в глазах. Вводим новые понятия. Один разряд - бит. 4 разряда - ниббл. 8 разрядов - байт. 2, 4 или 8 байтов - слово. Так 2, 4 или 8? А все-равно. Вносим неразбериху.


16-ная система счисления.

Группируем справа налево по 4 бита, если последняя группа неполная, дополняем нулями слева. Вводим символьные обозначения:

  0000 - 0  0001 - 1  0010 - 2  0011 - 3
  0100 - 4  0101 - 5  0110 - 6  0111 - 7
  1000 - 8  1001 - 9  1010 - A  1011 - B
  1100 - C  1101 - D  1110 - E  1111 - F

Пример:

  1001 0100 1010 0111 1010 1010 0001 0101
    9    4    A    7    A    A    1    5

  10010100101001111010101000010101  = 94A7AA15
                                  2           16

Полученную систему счисления называем 16-ной и для обозначения принадлежности числа к определенной системe используем индексы (2, 16).


8-ная система счисления.

Задаемся вопросом: почему группировали по 4 бита? Из желания напакостить (шутка) группируем справа налево по 3 бита, если последняя группа неполная, дополняем нулями слева. Вводим символьные обозначения:

  000 - 0  001 - 1  010 - 2  011 - 3
  100 - 4  101 - 5  110 - 6  111 - 7

Пример:

  010 010 100 101 001 111 010 101 000 010 101
   2   2   4   5   1   7   2   5   0   2   5

  10010100101001111010101000010101  = 22451725025
                                  2              8

Полученную систему счисления называем 8-ной и для обозначения принадлежности числа к определенной системe используем индексы (2, 8). Обилие систем счисления запутывает окончательно. Вещи, еще вчера казавшиеся бесспорными, выглядят сомнительными. Чтобы восстановить ясность мышления нужна надежная логика.


Введение в булеву алгебру.

Математик Буль думал о логике. Пытаемся упростить язык - убираем времена. 1847й год. Математик Буль думает о логике. Убираем из языка пространство - под, выше, за, далеко, внутри, и так далее. Все еще можно передавать информацию. Обобщаем: объект - существительное, глагол - действие.


Понятие алгебры. Высказывание. Алгебра Буля. Инверсия. Таблица истинности. Функции одной и двух переменных.

Вводим понятие: алгебра - объекты и действия над ними. Замечаем: часто фраза может быть оценена как истина или ложь:

  Буль родился на Марсе (ложь)
  Мамонты вымерли       (истина)

Вводим символы 0 - ложь, 1 - истина. Определяем объекты алгебры Буля: {0, 1}. Определяем булеву переменную: х может принимать значения 0, 1. Существует функциональная зависимость, если значение переменной y зависит от значения x. Записываем это как y=v(x). Поскольку x принимает всего 2 значения, 0 или 1, можно изобразить булеву функцию в виде таблицы. Например:

    x  |  v(x)
   ----+-----
    1  |  0
    0  |  1

Называем такую таблицу таблицей истинности. Пытаемся определить, сколько разных булевых функций одного переменного всего существует ? Для этого перебираем все возможные комбинации.

   x  | v0(x) v1(x) v2(x) v3(x)
  ----+-------------------------
   0  |  0     1     0     1
   1  |  0     0     1     1

Функции v0(x) и v3(x) вырожденные - они никак не зависят от x. Функция v2(x) тривиальна  v2(x) = x. Таким образом, практический интерес представляет только функция v1(x). Называем ее функция НЕ (инверсия). Записываем y(x) = x' или кратко y = x'.

   Инверсия    x  |  x'
              ----+----
    y = x'     0  |  1
               1  |  0

Определяем все возможные функции двух переменных y=w(x,t).

   x t | w0 w1 w2 w3 w4 w5 w6 w7 w8 w9 wA wB wC wD wE wF
  -----+-------------------------------------------------
   0 0 | 0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
   0 1 | 0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1
   1 0 | 0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1
   1 1 | 0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1

Их 16. Проводим выборы мисс. Как и в случае функций одной переменной, в таблице есть полностью вырожденные функции (w0, w15) не зависящие ни от x ни от t. Кроме того, есть функции зависящие только от одного переменного, а потому попадающие в класс функций одного переменного:

  w3(x,t)  = w(x) = x
  w5(x,t)  = w(t) = t
  w10(x,t) = w(t) = t'
  w12(x,t) = w(x) = x'

Во второй тур попадает 10 функций. Симметрия красива. В третий тур проходят функции w1, w6, w7, w8, w9, w14. Для них cправедливо выражение симметрии:
                           
  w(x,t) = w(t,x)

  Назовем их. w1  - И, коньюнкция, AND
              w6  - Исключающее ИЛИ, сложение по модулю 2, XOR
              w7  - ИЛИ, дизьюнкция, OR
              w8  - ИЛИ-НЕ, стрелка Pierce
              w9  - Эквивалентность, EQV
              w14 - И-НЕ, штрих Sheffer

Одну несимметричную функцию также нельзя оставлять не названной.

            w13 - импликация, (ЕСЛИ - ТО).

Функций слишком много. Замечаем, что одни функции можно выразить через другие. Приходим к понятию базиса - набора функций, через которые можно выразить все остальные. Например И, ИЛИ, НЕ. Ищем минимальные наборы функций - (минимальные базисы). Например И-НЕ. Рассматриваем функции, как элементарные действия (операции) над объектами. Вместо записи f(x,t) вводим запись x f t. Вводим новые символы: + дизьюнкция, * коньюнкция, = эквивалентность, -> импликация. Например:

    y = w1( a, w7( b, c)) теперь записываем как y = a * ( b + c )

Вводим понятие сложного выражения - состоящего из нескольких операций, входящих в базис. Вводим понятие приоритета операций - в какой последовательности совершать действия. Приоритет определяем из списка приоритетов. Например базис И, ИЛИ, НЕ может иметь два разных списка приоритетов (слева высший):

  НЕ, И, ИЛИ
  НЕ, ИЛИ, И

Кроме того, выбираем понравившееся правило из двух:

  - в случае равного приоритета действия совершаем слева направо.
  - в случае равного приоритета действия совершаем справа налево.

Для управления последовательностью операций вводим скобки. Теперь мы готовы записывать выражения.


Теоремы и законы булевой алгебры.

Пишем законы. Выражение, составляющее закон всегда истинно.

  - Отражение                x=x
  - Отрицание отрицания      x=x''
  - Симметрия                если a=b то b=a.
  - Транзитивность           если a=b и  b=c то a=c
  - Пустое множество         x*0=0,  x+0=x
  - Универсальное множество  x*1=x,  x+1=1
  - Дополнение               x+!x=1, x*!x=0
  - Идемпотентность          x*x*...*x=x, x+x+...+x=x

  - Коммутативный закон      a+b=b+a, a*b=b*a
  - Ассоциативный закон      (a*b)*c=a*(b*c), (a+b)+c=a+(b+c)
  - Дистрибутивный закон     a*(b+c)=a*b+a*c, a+(b*c)=(a+b)*(a+c)

  - Формулы D'Morgan-a       (a+b+...+z)'=
                             a'*b'*...*z', (a*b*...*z)'=a'+b'+...+z'

Доказываем таблицей истинности. Например, симметрия. Фраза "если a равно b то b равно а" может быть записана в виде следующего логического выражения:

  w13( w9(a,b), w9(b,a))   (с помощью функций)
  (a = b) -> (b = a)       (с помощью операций)

  a  b | a=b | b=a | (a=b)->(b=a)
  -----+-----+-----+--------------
  0  0 |  1  |  1  |      1
  0  1 |  0  |  0  |      1
  1  0 |  0  |  0  |      1
  1  1 |  1  |  1  |      1

Вспоминаем, что теоремы доказываются на основе аксиом. Какие законы можно отнести к аксиомам а какие доказывать на их основе? Здесь опять ситуация аналогичная случаю с базисом - можно выбирать из множества вариантов.


Канонические формы булевых функций.

Ищем связь между таблицей истинности и логическим выражением. Вспоминая свойство операции "И" приходим к СДНФ, совершенной дизьюнктивной нормальной форме - дизьюнкции коньюнкций из всех переменных функции (минтермов). Чтобы получить СДНФ по таблице истинности, составляем минтермы только для тех строк, где функция равна 1. CКНФ (коньюнкцию макстермов) получаем, наоборот, для тех строк, где функция равна 0. 

Пример:

   a b c | f
  -------+---
   0 0 0 | 1
   0 0 1 | 0
   0 1 0 | 0  СДНФ  y = a'*b'*c' +  a'*b*c + a*b*c' + a*b*c
   0 1 1 | 1  СКНФ  у = (a'+b'+c) * (a'+b +c') * (a+b'+c') * (a+b'+c)
   1 0 0 | 0
   1 0 1 | 0
   1 1 0 | 1
   1 1 1 | 1


Упрощение логических выражений в аналитической форме.

Для упрощения сложных логических выражений используем следующие правила

  - Поглощение     a + a * b      = a
  - Склеивание     a * b + a * b' = a
  - Развертывание  a = a * b + a * b'

Упрощаем СДНФ выражения методами поглощения и склеивания. Приходим к ДНФ. Все еще дизьюнкция коньюнкций но уже не обязательно минтермов, а импликант содержащих не все переменные функции.


Набор. Вес. Ранг. Расстояние по Hamming-у.
------------------------------------------
Ввели много новых понятий. Вводим еще больше. Набор - конкретные значения всех переменных функции. Ранг - количество разрядов в наборе. Вес - количество единиц в наборе. Расстояние по Хэммингу (Hamming) - в скольких разрядах два набора отличаются.

Ну вот. Фундамент построен. Один из многих возможных, в нем есть противоречия и желающих спуститься еще ниже остается напутствовать афоризмом: "я опустился на самое дно и вдруг услышал, что снизу кто-то стучит.."


Коды Грэя (Gray). Карта Карно (Karnaugh).
-----------------------------------------
Попробуем упростить некоторую СДНФ склеиванием. Склеивать можно соседние наборы, то есть наборы расстояние по Hamming между которыми равно 1. Например ab'cd и аbcd соседние, а ab'cd и аbcd' нет. В таблице истинности мы располагаем наборы в порядке возрастания соответствующих им двоичных чисел, то есть в соседних строках стоят не соседние наборы. Например, пары наборов (00, 01), (10, 11) - соседние, а вот (01, 10) - нет. Gray расположил наборы так, что рядом всегда стоят соседние. Кроме того, первый и последний наборы также соседние.

   a   b |       
  -------+---   
   0   0 |      
   0   1 |
   1   0 |           
   1   1 |
   
Вот как выглядит код Грэя для набора с рангом 2.

  00, 01, 11, 10
        
Для ранга 3 имеем: 000, 001, 011, 010, 110, 111, 101, 100. Карно придумал заполнять таблицу истинности в порядке кодов Грэя:
          a       
       ------     
  +----+----+     
  |y(0)|y(1)|                
  +----+----+

В случае функции одного переменного имеем всего 2 клетки.

  - полоской отмечаем область, где переменная имеет значение 1.
  - в клетки записываем значения логической функции.
  
2 переменных: Поскольку крайние наборы соседние, полоску следует склеить в кольцо. Мысленно.

         ab  ab  ab  ab  
  Gray:  00  01  11  10    
                                
                       
    b ---------     
  +---+---+---+---+      
  |   |   |   |   |  
  +---+---+---+---+         
          --------- a
                                 
В случае 3х переменных:

         abc abc abc abc abc abc abc abc                                 
  Gray:  000 001 011 010 110 111 101 100
                        ----------------- c
        +---+---+---+---+---+---+---+---+
        |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+
              b -----------------      
          a ---------     a ---------
                        
Разорванная область переменной a делает карту менее наглядной. У Карно возникает еще одна идея. Для изображения третьей переменной привлечь вторую координату:

          b              
      ---------          
  +---+---+---+---+ |           
  |   |   |   |   | | a 
  +---+---+---+---+ | 
  |   |   |   |   |   
  +---+---+---+---+   
          ---------   
              c       
              
Теперь легко составить карту для случая 4х переменных:

                 d
             ---------
     +---+---+---+---+|  
     |   |   |   |   ||  
    |+---+---+---+---+| b
    ||   |   |   |   ||  
  a |+---+---+---+---+|  
    ||   |   |   |   |   
    |+---+---+---+---+   
     |   |   |   |   |   
     +---+---+---+---+   
         ---------       
             c           

Мысленно сворачиваем обе изображенные карты в бублики. 5 и 6 переменных красивее всего расположить в прозрачном кирпиче. Мысленно сворачиваем его в 4-х мерный гипербублик. И так далее..


Понятие цифрового сигнала. Связь между логическим выражением и схемой. Понятие комбинационной схемы. Условные обозначения И, ИЛИ, НЕ.

Молния ударяет в дерево и дерево раскалывается. Это электричество. Возникает идея построить вычислитель логической функции на электричестве. Вводим понятие цифрового сигнала: 0 вольт - логический ноль. 5 вольт - логическая диница. А если наоборот? Можно наоборот - называем инверсной логикой. А если не 5 вольт? Можно не 5.

Соединяем лампочку с батарейкой. Горит! Вставим последовательно два нормально разомкнутых контакта (замыкающих цепь при нажатии кнопки). Горит только тогда, когда обе кнопки нажаты. Это функция "И" (рисунок а)). Вставим параллельно два нормально разомкнутых контакта. Горит тогда, когда нажата хотя бы одна кнопка. Это функция "ИЛИ" (рисунок б)). Вставим нормально замкнутый контакт (размыкающий цепь при нажатии кнопки). Это инвертор, "НЕ" (рисунок в)).

       |      |
      -+-    -+-
  +---o o----o o---+
  |                |
  =               (x)
 ---               |
  |                |
  +-------o--------+
          |
         ---    
         ///      а)

          |
         -+- 
  +------o o-------+
  |                |
  |       |        |
  |      -+-       |
  +------o o-------+
  |                |
  =               (x)
 ---               |
  |                |
  +-------o--------+
          |
         ---
         ///      б)
         
          |
  +-----o | o------+
  |     --+--      |
  =               (x)
 ---               |
  |                |
  +-------o--------+
          |
         ---    
         ///      в)

Вместо кнопки ставим электромагнит с якорем, управляющим контактом. Получаем реле. На реле можем собирать релейные схемы. Схема, заключенная на рисунке в рамочку, представляет из себя ничто иное, как логический элемент "И". Подавая логические сигналы на входы элемента мы получим на выходе их коньюнкцию.

                                             +--------------+
                                             |              |
                    /\    /\    /\           o|             |
      _____________/  \  /  \  /  \  +-][=====+             |
     |                 \/    \/    \/|       o|             |
     |                               |       |              |
     |                               |       |             (x)
     |                               |       |              |
     |              /\    /\    /\   |       o |            |
     |           __/  \  /  \  /  \  +-] [=====+            |
     |          |      \/    \/    \/|       o |            |
     |          |                    |       |              |
     |          |                    +-------+              |
    |o       |  o                            |              |
  --+      --+                              -+-             |
    |o       |  o                          --+--            | 
     |          |                            |              |
    -+-        -+-                          -+-            -+-
    ///        ///                          ///            ///

Приняв во внимание, что значениям на входах логического элемента соответствуют значения переменных логической функции, а значение самой функции соответствует значению выходного сигнала, мы можем строить более сложные схемы.

Нам понадобятся элементы "ИЛИ", "И", "НЕ". Введем для них условные обозначения:

    +-----+   
    |     |   
  --+     O-- 
    |     |   
    +-----+  а) 

    +-----+        +-----+   
    |   & |        |   & |   
  --+     |      --+     |   
    |     +--      |     O-- 
  --+     |      --+     |   
    |     |        |     |   
    +-----+  б)    +-----+  в)

    +-----+        +-----+   
    |   1 |        |   1 |   
  --+     |      --+     |   
    |     +--      |     O-- 
  --+     |      --+     |   
    |     |        |     |   
    +-----+  г)    +-----+  д)
  
  а) элемент "НЕ" 
  б) элемент "И" 
  в) элемент "И-НЕ" 
  г) элемент "ИЛИ" 
  д) элемент "ИЛИ-НЕ".

Реализуем, например схему "исключающее или":

                       y = a * b' + a' * b
        +-----+    
        |     |    
   --+--+     O--+
     |  |     |  |    
     |  +-----+  |  +-----+                 
     |           |  |   & |
     +-----+     +--+     |  
           |        |     +--+      
     +-----|--------+     |  |  +-----+  
     |     |        |     |  |  |   1 |  
     |     |        +-----+  +--+     |  
     |     |                    |     +----
     |     |        +-----+  +--+     |  
     |     |        |   & |  |  |     |  
     |     +--------+     |  |  +-----+  
     |              |     +--+
     |           +--+     |   
     |           |  |     |   
     |  +-----+  |  +-----+   
     |  |     |  |  
   --+--+     O--+  
        |     |    
        +-----+    

  
                     Цифровая техника имеет божественное происхождение.
                     Аналоговую создали динозавры. Но любая из них 
                     превосходит своих создателей.

                                    Компьютер Фибоначчи

Занятие 2.

Специализированные комбинационные схемы.
----------------------------------------
Синтезируем разные логические схемы. Наиболее полезным из них даем названия. Вводим понятие комбинационной схемы - выход зависит только от текущих значений входных сигналов. То есть такие схемы не обладают способностью помнить. Рассказываем о них в жанре комиксов. Комиксы смотрите на симуляторе Logisim доступном для бесплатного скачивания на сайте: 

   http://ozark.hendrix.edu/~burch/logisim/ 

схемы прилагаются по следующим темам:

  - Декодеры. Синтез комбинационных схем с помощью декодеров. Кодеры Преобразователи кода.
  - Демультиплексоры. Мультиплексоры. Синтез комбинационных схем с помощью мультиплексоров.

Сложение в двоичном коде. Сумматор.
-----------------------------------
                                                         1        0
  0 + 0 = 0.  0 + 1 = 1.  1 + 0 = 1.  1 + 1 = 10.  (1 * 2  + 0 * 2 )

При сложении наборов с рангом больше 1 складываем поразрядно справа налево. Возникает перенос в старший разряд. Короче, сложение в столбик понимают все, словами долго объяснять, и опять же двусмысленно. Пример:

  перенос    111
             010110
           + 
             011100
           =
             110010

Или не все понимают? Вводим понятие сложения по модулю 2. Иначе, это называется четвертьсуммирование.

      a  b | s        Записываем СДНФ:     s = a'* b + b'* a.
     ------+---            
      0  0 | 0             
      0  1 | 1             
      1  0 | 1             
      1  1 | 0

Смотрим, когда возникает перенос? Это функция "И".

      a  b | c        Записываем СДНФ:     c = a * b
     ------+--- 
      0  0 | 0  
      0  1 | 0  
      1  0 | 0  
      1  1 | 1  

Составим схему, вычисляющую как четвертьсумму, так и перенос, это называется полусумма.

          +-----+                            
  a       |     |                            
  --+--+--+     O--+                         
    |  |  |     |  |                         
    |  |  +-----+  |  +-----+                
    |  |           |  |   & |                
    |  +-----+     +--+     |                
    |        |        |     +--+             
    |  +-----|--------+     |  |  +-----+    
    |  |     |        |     |  |  |   1 |    
    |  |     |        +-----+  +--+     |   s 
    |  |     |                    |     +----
    |  |     |        +-----+  +--+     |    
    |  |     |        |   & |  |  |     |    
    |  |     +--------+     |  |  +-----+    
    |  |              |     +--+             
    |  |           +--+     |                
    |  |           |  |     |                
    |  |  +-----+  |  +-----+                
  b |  |  |     |  |                         
  --(--+--+     O--+                         
    |  |  |     |                 +-----+    
    |  |  +-----+                 |   1 |    
    |  +--------------------------+     |   c 
    |                             |     +----
    +-----------------------------+     |    
                                  |     |    
                                  +-----+    

Создадим схему полного суммирования в одном разряде. Посмотрим на таблицу истинности, где c - перенос из предыдущего разряда,
 
  q0 - полусумма a и b, q1 - полусумма q0 и с, 
  c0 - перенос при сложении a и b, 
  c1 - перенос при сложении q0 и c:

    а   b   c  | q0 | c0 | q1 | c1 | cумма | перенос
  -------------+----+----+----+----+-------+---------
    0   0   0  | 0  | 0  | 0  | 0  | 0     |   0
    0   0   1  | 0  | 0  | 1  | 0  | 1     |   0
    0   1   0  | 1  | 0  | 1  | 0  | 1     |   0
    0   1   1  | 1  | 0  | 0  | 1  | 0     |   1
    1   0   0  | 1  | 0  | 1  | 0  | 1     |   0
    1   0   1  | 1  | 0  | 0  | 1  | 0     |   1
    1   1   0  | 0  | 1  | 0  | 0  | 0     |   1
    1   1   1  | 0  | 1  | 0  | 1  | 1     |   1

Сумму получим если сложим по модулю 2 a и b а затем сложим по модулю 2 полученный результат и с. То есть нужно два раза использовать схему полусумматора.

Перенос - это функция "с0 ИЛИ с1". Нужна функция ИЛИ. Тогда полный сумматор будет выглядеть так:

        +---+                   
  a     |   |                   
  --+-+-+   O-+                 
    | | |   | |                 
    | | +---+ | +---+           
    | |       | | & |           
    | +---+   +-+   |           
    |     |     |   +-+         
    | +---|-----+   | | +---+   
    | |   |     |   | | | 1 |       +---+                       
    | |   |     +---+ +-+   |       |   |                      
    | |   |             |   +---+-+-+   O-+                 
    | |   |     +---+ +-+   |   | | |   | |                   
    | |   |     | & | | |   |   | | +---+ | +---+             
    | |   +-----+   | | +---+   | |       | | & |             
    | |         |   +-+         | +---+   +-+   |             
    | |       +-+   |           |     |     |   +-+          
    | |       | |   |           | +---|-----+   | | +---+    
    | | +---+ | +---+           | |   |     |   | | | 1 |    
  b | | |   | |                 | |   |     +---+ +-+   |         s  
  --(-+-+   O-+                 | |   |             |   +----------
    | | |   |           +---+   | |   |     +---+ +-+   |    
    | | +---+           | 1 |   | |   |     | & | | |   |    
    | +-----------------+   |   | |   +-----+   | | +---+   
    |                   |   +-+ | |         |   +-+        
    +-------------------+   | | | |       +-+   |            
                        |   | | | |       | |   |            
                        +---+ | | | +---+ | +---+            
  c                           | | | |   | |                
  ----------------------------(-(-+-+   O-+                
                              | | | |   |           +---+  
                              | | | +---+           | 1 |   +---+  
                              | | +-----------------+   |   | 1 |  
                              | |                   |   +---+   | c 
                              | +-------------------+   |   |   +--
                              |                     |   | +-+   |  
                              |                     +---+ | |   |  
                              +---------------------------+ +---+  

Соединяем полные сумматоры змейкой - получаем параллельный сумматор с последовательным переносом. Схемы для симуляции в разделе Compute.


Представление отрицательных двоичных чисел. Прямой, Инверсный, Дополнительный коды. Алгоритм перевода в дополнительный код.

Храним двоичные числа в регистре. Индикатором факта, что в регистре хранится отрицательное число, является наличие "1" в старшем бите. Наиболее распространены прямой, инверсный (1s-complement) и дополнительный (2s complement) коды. Инверсный код образуется инвертированием всех битов в регистре. Например 

  -5   = 1010  . 
    10       2
                                                                        
Дополнительный код образуется вычитанием абсолютного значения числа из 2 в степени n, где n - количество разрядов в регистре. Замечено, что справедлив следующий алгоритм: рассматриваем разряды числа справа налево. При появлении в разряде "1" все последующие биты инвертируем. 

Например код 00110100. Тогда, дополнительный код 11001100.

Схемы для симуляции в разделе Compute.
  

Вычитание.

Замечаем, что существует две разные операции "-": бинарная операция вычитания (a - b), и унарная (-a) изменения знака числа. Храним отрицательные числа в дополнительном коде, используем сумматор для вычитания:

  a - b = a + (-b)


Умножение.

Умножение аналогично "умножению в столбик" для десятичной системы. Разумеется, складываем по правилам двоичного сложения. Схема в разделе Compute.


Деление.

Деление можно осуществить на комбинационной схеме. (схема в разделе Compute).


Последовательные схемы.

Автомат Moore. Автомат Mealy.


Автомат Миля-Гофмана (Мealy-Huffman).

                  +----+----+----+
        \---------+ x0 | KC | z0 +---------\
    In   \        |    |    |    |          \  Out
         /        .    .    .    .          /
        /---------+ xL |    | zN +---------/
                  +----+    +----+
            +-----+ u0 |    | w0 +-----+
            |     |    |    |    |     |
            .     .    .    .    .     |
            |     |    |    |    |     |
            |  +--+ uM |    | wM +--+  |
            |  |  +----+----+----+  |  |
            |  |                    |  |
            |  |  +----+----+----+  |  |
            |  +--+ DM | KC | QM +--+  |
            |     |    |    |    |     |
            |  +-->    |    |    |     |
            |  |  +----+----+----+     |
            |  |                       |
            .  .  . . . . . . . . .    .
            |  |                       |
            |  |  +----+----+----+     |
            +--)--+ D0 | KC | Q0 +-----+
               |  |    |    |    |
    Clock -----+-->    |    |    |
                  +----+----+----+

   

Автомат Мура (Moore).                                            

  +-------------------------------------------------------+
  |                                                       |
  |                                                       |
  |  +----------------------------------------------+     |
  |  |  +----------------------------------------+  |     |
  |  |  |                                        |  |     |
  |  |  |  +----+----+----+         +--+---+--+  |  |     |
  |  |  +--+ y0 | КС | z0 +---------+D0|   |Q0+--+--)-----)---> Out 0
  |  |     |    |    |    |         |  |   |  |     |     |
  |  |     |    |    |    |     +--->  |   |  |     |     |
  |  |     |    |    |    |     |   +--+---+--+     |     |
  |  |     |    |    |    |     |                   |     |
  |  |     |    |    |    |     |   +--+---+--+     |     |
  |  +-----+ y1 |    | z1 +-----)---+D1|   |Q1+-----+-----)---> Out 1
  |        |    |    |    |     |   |  |   |  |           |
  |        |    |    |    |     +--->  |   |  |           |
  |        |    |    |    |     |   +--+---+--+           |
  |        |    |    |    |     .                         .
  |        |    |    |    |     .   . . . . . .           .
  |        |    |    |    |     .                         .
  |        |    |    |    |     |   +--+---+--+           |
  +--------+ yN |    | zN +-----)---+DN|   |QN+-----------+---> Out N
           +----+    |----|     |   |  |   |  |
  In 0 >---+ x0 |    |    |     +--->  |   |  |
           |    |    |    |     |   +--+---+--+
  In 1 >---+ x1 |    |    |     |
           .              .     .
           .              .     .
           .              .     .
  In M >---+ xM |    |    |     |
           +----+----+----+     |
                                |
  clock ------------------------+

На рисунке: КС - комбинационная схема, D0..DN - блок памяти (параллельный N-разрядный регистр на D-триггерах.) Можно показать, что автомат Mealy, всегда можно заменить автоматом Moore. Но не всегда такая замена упрощает схему.


Триггеры.

Асинхронный RS-триггер. Собираем на элементах ИЛИ-НЕ.

                         +----------------- Q (прямой выход)
             +----+      |
    (S)et >--+   1|      |      +----+   
             |    o------+------+   1|      -
          +--+    |             |    o--+-- Q (инверсный выход)
          |  +----+   (R)eset --+    |  |
          |                     +----+  |
          |                             |
          +-----------------------------+
          
                      -
Cостояние в точках RSQQ показано на таблице и на графике, называемом временной диаграммой.

                     -
    время | S  R  Q  Q
  --------+-------------
    t0    | 0  0  1  0
    t1    | 0  1  0  1
    t2    | 0  0  0  1
    t3    | 1  0  1  0
    t4    | 0  0  1  0  
    t5    | 1  1  0  0
    t6    | 0  0  x  x
    
  S ^
    |               -       -
    |              | |     | |
    |--------------   -----   -----
    +--+---+---+---+---+---+---+---->
       t0  t1  t2  t3  t4  t5  t6
  R ^
    |       -               -
    |      | |             | |
    |------   -------------   -----
    +--+---+---+---+---+---+---+---->
       t0  t1  t2  t3  t4  t5  t6
  Q ^
    |-------         -------
    |       |       |       |   XXX
    |        -------         ---
    +--+---+---+---+---+---+---+---->
  -    t0  t1  t2  t3  t4  t5  t6
  Q ^
    |    -------
    |   |       |               XXX
    |---         ---------------
    +--+---+---+---+---+---+---+---->
       t0  t1  t2  t3  t4  t5  t6
    
Выход из состояния обоих единиц на входах непредсказуем и потому состояние S=1, R=1 запрещено.

Условное обозначение:

      +---+----+---+
      |   | RS |   |
    --+ S |    | Q +--
      |   |    |   |
      |   |    | - |
    --+ R |    | Q o--
      |   |    |   |
      +---+----+---+

Комиксы - матрешки. Каждый следующий триггер сделан на базе предыдущего:


Синхронный RS-триггер.

Схема на основе асинхронного RS-триггера.

             +---+   +---+----+---+
  Set   -----+  &|   |   | RS |   |
             |   +---+ S |    | Q +--
          +--+   |   |   |    |   |
          |  +---+   |   |    |   |
  Clock --+          |   |    |   |
          |  +---+   |   |    |   |
          +--+  &|   |   |    | - |
             |   +---+ R |    | Q o--
  Reset -----+   |   |   |    |   |
             +---+   +---+----+---+
             
Условное обозначение.

                     +---+----+---+
                     |   | RS |   |
                  ---+ S |    | Q +--
                     |   |    |   |
                     |   |    |   |
                  --->   |    |   |
                     |   |    |   |
                     |   |    | - |
                  ---+ R |    | Q o--
                     |   |    |   |
                     +---+----+---+
             

D-триггер.

Схема на основе синхронного RS-триггера.

                     +---+----+---+
                     |   | RS |   |
  Data  --+----------+ S |    | Q +--
          |          |   |    |   |
          |          |   |    |   |
  Clock --)---------->   |    |   |
          |  +---+   |   |    |   |
          |  |   |   |   |    | - |
          +--+   o---+ R |    | Q o--
             |   |   |   |    |   |
             +---+   +---+----+---+
             
Условное обозначение.

                     +---+----+---+
                     |   | D  |   |
                  ---+ D |    | Q +--
                     |   |    |   |
                     |   |    | - |
                  --->   |    | Q o--
                     |   |    |   |
                     +---+----+---+
 

Двухтактный RS-триггер.

Схема

                  +---+----+---+         +---+----+---+  
                  |   | RS |   |         |   | RS |   |  
   Set    --------+ S |    | Q +---------+ S |    | Q +--
                  |   |    |   |         |   |    |   |  
                  |   |    |   |         |   |    |   |  
             +---->   |    |   |    +---->   |    |   |  
             |    |   |    |   |    |    |   |    |   |  
             |    |   |    | - |    |    |   |    | - |  
   Reset  ---)----+ R |    | Q o----)----+ R |    | Q o--
             |    |   |    |   |    |    |   |    |   |  
             |    +---+----+---+    |    +---+----+---+  
             |                      |
             |        +----+        |
             |        |    |        |
   Clock  ---+--------+    o--------+
                      |    |
                      +----+

Условное обозначение

                +---+----+---+   
                |   | RS |   |   
          ------+ S | RS | Q +------
                |   |    |   |   
                |   |    |   |   
                |   |    |   |   
          ------>   |    |   |   
                |   |    |   |   
                |   |    |   |   
                |   |    | - |   
          ------+ R |    | Q o------
                |   |    |   |   
                +---+----+---+   


Двухтактный JK-триггер. 

       +-----------------------------------+
       |                                   |
       |  +----+       +---+----+---+      |
       +--+  & |       |   | RS |   |      |
          |    o-------+ S | RS | Q +---+--)-----
   J -----+    |       |   |    |   |   |  |
          +----+       |   |    |   |   |  |
                       |   |    |   |   |  |
   C ------------------>   |    |   |   |  |
                       |   |    |   |   |  |
          +----+       |   |    |   |   |  |
   K -----+  & |       |   |    | - |   |  |
          |    +-------+ R |    | Q o---)--+-----
       +--+    |       |   |    |   |   |
       |  +----+       +---+----+---+   |
       |                                |
       +--------------------------------+

Условное обозначение.

                +---+----+---+   
                |   | JK |   |   
          ------+ J |    | Q +------
                |   |    |   |   
                |   |    |   |   
                |   |    |   |   
          ------+ K |    |   |   
                |   |    |   |   
                +---+    |   |   
                |   |    | - |   
          ------> C |    | Q o------
                |   |    |   |   
                +---+----+---+   
                
Выход из состояния обоих единиц на входах используется для счета синхроимпульсов, в отличие от RS-триггера состояние J=1, K=1 активно используется.


T-триггер.

Т-триггер представляет собой JK-триггер с соединенными между собой входами J и K. Если на вход T подавать логическую единицу, то такой триггер переключается всякий раз при поступлении следующего синхроимпульса.

                +---+----+---+   
                |   | JK |   |   
    T     ---+--+ J |    | Q +------
             |  |   |    |   |   
             |  |   |    |   |   
             |  |   |    |   |   
             +--+ K |    |   |   
                |   |    |   |   
                +---+    |   |   
                |   |    | - |   
    Clock ------> C |    | Q o------
                |   |    |   |   
                +---+----+---+   

Условное обозначение.

                +---+----+---+   
                |   | T  |   |   
          ------+ T |    | Q +------
                |   |    |   |   
                +---+    |   |   
                |   |    | - |   
          ------> C |    | Q o------
                |   |    |   |   
                +---+----+---+   

  - Схема образования динамического синхроимпульса по переднему фронту.
  - Схема образования динамического синхроимпульса по заднему фронту.


Параллельные регистры.

Количество D-триггеров, образующих параллельный регистр, является его разрядностью. Жгут из проводов D0..DN обрвзует шину разрядности N. Схема:

                     +---+----+---+
                     |   | D  |   |
         Data 0 -----+ D |    | Q +--
                     |   |    |   |
                     |   |    | - |
                  +-->   |    | Q o--
                  |  |   |    |   |
                  |  +---+----+---+
                  |  +---+----+---+
                  |  |   | D  |   |
         Data 1 --)--+ D |    | Q +--
                  |  |   |    |   |
                  |  |   |    | - |
                  +-->   |    | Q o--
                  |  |   |    |   |
                  |  +---+----+---+
                  .  . . . . . . . .
                  |  +---+----+---+
                  |  |   | D  |   |
         Data N --)--+ D |    | Q +--
                  |  |   |    |   |
                  |  |   |    | - |
         Clock ---+-->   |    | Q o--
                     |   |    |   |
                     +---+----+---+
                     
Oбозначение

                     +---+----+---+
                     |   | RG |   |
       Input  \------+ D0|    | Q0+----\  Output
       Data    \     | D1|    | Q1|     \ Data
       Bus     /     | ..|    | ..|     / Bus
              /------+ DN|    | QN+----/
                     |   |    |   |
                     +---+    |   |
       Clock  ------->   |    |   |
                     +---+----+---+
                     

Последовательные регистры. 

Файлы схем для симулятора в разделе регистры.


Cчетчики. Делители частоты. 

Последовательный счетчик на базе T-триггера.

  1 --+------------------+------------------+----------------
      |                  |                  |                
      |  +-+---+-+       |  +-+---+-+       |  +-+---+-+     
      |  | | T | |       |  | | T | |       |  | | T | |     
      +--+T|   |Q+--+    +--+T|   |Q+--+    +--+T|   |Q+--+  
         | |   | |  |       | |   | |  |       | |   | |  |  
         +-+   | |  |       +-+   | |  |       +-+   | |  |  
         | |   | |  |       | |   | |  |       | |   | |  |  
  Clock ->C|   | |  +------->C|   | |  +------->C|   | |  +--
         | |   | |          | |   | |          | |   | |     
         +-+---+-+          +-+---+-+          +-+---+-+     


Параллельный счетчик.

Счетчик можно создать, если знать как считать. Пока не знаем. Можно 
просто помнить последовательность 000,001,010,011,100,110,111. Теперь 
понятно, что каждый разряд следующего набора получается с помощью 
некоторой логической функции.

Составим таблицу истинности, упростим функции картами Карно.         

   x2 x1 x0 | y2 y1 y0   
  ----------+----------  
   0  0  0  | 0  0  1    
   0  0  1  | 0  1  0    
   0  1  0  | 0  1  1    
   0  1  1  | 1  0  0    
   1  0  0  | 1  0  1    
   1  0  1  | 1  1  0    
   1  1  0  | 1  1  1    
   1  1  1  | 0  0  0

Вспоминаем, какие наборы в какие клетки попадают. Рисуем шаблон.

        x1             
     ---------         
   | +---+---+---+---+ 
x0 | |011|111|101|001| 
   | +---+---+---+---+ 
     |010|110|100|000| 
     +---+---+---+---+ 
         ---------     
            x2

Теперь легко заполнить карты для y2, y1, y0:

  y2               y1               y0
        x1               x1               x1               
       -----            -----            -----       
     | +-+-+-+-+      | +-+-+-+-+      | +-+-+-+-+   
  x0 | |1|0|1|0|   x0 | |0|0|1|1|   x0 | |0|0|0|0|   
     | +-+-+-+-+      | +-+-+-+-+      | +-+-+-+-+   
       |0|1|1|0|        |1|1|0|0|        |1|1|1|1|   
       +-+-+-+-+        +-+-+-+-+        +-+-+-+-+   
         -----            -----            -----     
          x2               x2               x2                                  

Итак:
 
  y2 = x0 * x1 * x2' + (x0' + x1') * x2 
  y1 = x0 * x1' + x0' * x1           
  y0 = x0'

Считаем: Подали на вход нашей комбинационной схемы (КС) 000. На выходе 
получили 001. Запомнили, и подали на вход 001. И так далее.

  +------------------------------------------------------+
  |  +------------------------------------------------+  |
  |  |  +------------------------------------------+  |  |
  |  |  |                                          |  |  |
  |  |  |  +----+----+----+         +---+---+---+  |  |  |
  |  |  +--+ x0 | КС | y0 +---------+ D |   | Q +--+  |  |
  |  |     |    |    |    |         |   |   |   |     |  |
  |  |     |    |    |    |     +--->   |   |   |     |  |
  |  |     |    |    |    |     |   +---+---+---+     |  |
  |  |     |    |    |    |     |                     |  |
  |  |     |    |    |    |     |   +---+---+---+     |  |
  |  +-----+ x1 |    | y1 +-----)---+ D |   | Q +-----+  |
  |        |    |    |    |     |   |   |   |   |        |
  |        |    |    |    |     +--->   |   |   |        |
  |        |    |    |    |     |   +---+---+---+        |
  |        |    |    |    |     |                        |
  |        |    |    |    |     |   +---+---+---+        |
  +--------+ x2 |    | y2 +-----)---+ D |   | Q +--------+
           |    |    |    |     |   |   |   |   |
           |    |    |    |     +--->   |   |   |
           +----+----+----+     |   +---+---+---+
                                |
  clock ------------------------+
    
Файлы схем для симулятора в разделе счетчики. Делители частоты, как 
правило, делают на базе счетчиков.
