edu-csa

# Архитектура компьютера

## Лекция 4

## Цифровая схемотехника

Пенской А.В., 2025

----

## План лекции

- Принцип развития иерархических систем Седова & Метасистемный переход
- Кодирование информации
    - Булев базис.
    - Двоичное кодирование.
    - Код Грея, BCD, BASE64, BASE58
- Цифровая схемотехника.
    - Комбинационные схемы.
    - Триггер.
    - Схемы с состоянием.

---

<dl>
  <dt> - Принцип развития иерархических систем Седова </dt>
  <dd>  закономерности и механизмы, по которым развиваются сложные иерархические системы. Ключевой принцип: ограничение разнообразия на нижележащем уровне для получения разнообразия на вышележащем уровне. </dd>
</dl>
 
<dl>
  <dt> - Метасистемный переход </dt>
  <dd>  концепция, предложенная Валентином Турчиным, описывает процесс перехода системы на новый уровень организации, становясь метасистемой. В этом процессе несколько систем интегрируются в одну более сложную, обладающую новыми свойствами. </dd>
</dl>
 
(Турчин В.Ф. Феномен науки: Кибернетический подход к эволюции)

---

## Цифровая схемотехника. <br/> Булев базис

Элементы цифровой схемотехники:

1. двоичная логика;
2. полный набор булевых функций:
    - И, ИЛИ, НЕ;
    - штрих Шеффера $x|y = \overline{x y}$;
    - стрелка Пирса $x \downarrow y = \overline{x \vee y}$.
3. комбинационные схемы;
4. триггер — хранение состояния.

</div><div class="col">

![](/fig/level-of-abstraction-for-computing-system-vert.png)

</div></div>

---

## Кодирование

### Двоичное кодирование

![](/fig/logic-levels-and-noise-margins.png)

----

#### Достоинства двоичного

1. Надежно и помехоустойчиво.
2. Простая арифметика.
3. Диапазоны и точность наращиваются разрядностью (слева и справа соответственно).
4. Погрешности "by design", а не "by implementation"

#### Недостатки

1. Нечитаемое представление.
2. Простые десятичные дроби записываются в виде бесконечных двоичных дробей.
3. Дискретное кодирование сигналов (точность).

</div><div class="col">

![](/fig/signal-analog-discreet.png)

</div></div>

---

#### Машинное слово. Представления данных

Машинное слово — единица данных, естественная для обработки вычислителем. Пример: сложение, пересылка, и т.п.

![](/fig/big-little-endian.png)

Что удобнее? (см. далее)

</div><div class="col">

- Целые числа:
    - Позиционные системы счисления.
    - Дополнительный код.
    - Big & Little endian.
- Дроби:
    - С фиксированной точкой.
    - С плавающей точкой.
- Перечисления:
    - Двоично-десятичное кодирование.
    - Символы (старые кодировки).
- Тегированные данные.

</div></div>

----

![](/fig/big-little-endian-why.jpg)

Адресация внутри машинного слова. Обращения к байтам, смещения.

----

*Offtopic*: Классификация типов по версии IBM

![](/fig/ibm-primitive-types.jpg)

---

### Код Грея и BCD

<dl>
  <dt> Код Грея </dt>
  <dd>  две "соседние" кодовые комбинации различаются только цифрой в одном двоичном разряде. </dd>
</dl>
 
<dl>
  <dt> BCD </dt>
  <dd>  форма записи рациональных чисел, когда каждый десятичный разряд числа записывается в виде его четырёхбитного двоичного кода </dd>
</dl>
 
</div><div class="col">

![](/fig/gray_code.png)
![](/fig/code_BCD.png)

</div></div>

----

### Base64 и Base58

![](/fig/base64.png)

<dl>
  <dt> Base64 </dt>
  <dd>  стандарт кодирования двоичных данных при помощи только 64 символов ASCII. Алфавит кодирования содержит латинские символы A-Z, a-z, цифры 0-9 (всего 62 знака) и 2 дополнительных символа. </dd>
</dl>
 
<dl>
  <dt> Base58 </dt>
  <dd>  Similar to Base64, but modified to avoid non-alphanumeric chars and letters that might look ambiguous when printed (0, I, O, l). </dd>
</dl>
 
---

### Комбинационные схемы (КС)

<dl>
  <dt> Комбинационная схема </dt>
  <dd>  схема, составленная из набора логических элементов, в совокупности реализующая заданную таблицу истинности. </dd>
</dl>
 
Простейшие элементы комбинационных схем:

![](/fig/logic-elems.png)

----

#### КС: Возможности

Реализация функций — отображение множества $A$ на множество $B$.

$A$ и $B$ конечны (представимы конечной последовательностью бит) $\longrightarrow$ возможно построить комбинационную схему.

#### КС: Подход к построению

1. через таблицу истинности (чёрный ящик);
2. через алгоритмизацию (белый ящик, этапность/структура расчёта).

*Offtopic*: логарифмическая линейка и арифмометр.

---

#### Через таблицу истинности

Шаги:

1. Формирование таблицы истинности.
2. Запись таблицы истинности в каноническую форму (ДНФ или КНФ), отображаемую в комбинационную схему.
3. Минимизация булевой функции (сокращаем размер схемы).

**Подробнее**: дискретная математика, Поляков: ККНФ и КДНФ, минимизация булевых функций, метод Петрика, карты Карно и т.д.

</div><div class="col">

![](/fig/encoder_block_diagram.jpg)  
![](/fig/encoder-4-to-2-table.png)

Пример (4 to 2 encoder) — на следующем слайде.

</div></div>

----

##### Шифратор (Encoder, 4-to-2)

##### 1. Таблица истинности

![](/fig/encoder-4-to-2-table.png)

##### 2. КДНФ

$o_1 = \overline{i_3} i_2 \overline{i_1} \overline{i_0} \vee i_3 \overline{i_2} \overline{i_1} \overline{i_0}$

$o_0 = \overline{i_3} \overline{i_2} i_1 \overline{i_0} \vee i_3 \overline{i_2} \overline{i_1} \overline{i_0}$

</div><div class="col">

##### 3. Минимизированная функция

$o_1 = i_3 \vee i_2$

$o_0 = i_3 \vee i_1$

![](/fig/encoder_4-to-2.png)

</div></div>

---

#### Через алгоритмизацию

Схема строится на основе понимания функции, взаимосвязи входа и выхода. Творческий процесс. Схема может быть каскадной.

Полный сумматор (1-bit):

- $A$, $B$ — биты операндов;
- $S$ — результат;
- $С_{in}$, $С_{out}$ — бит переноса.

</div><div class="col">

![](/fig/logic-full-adder-right-to-left.png)

</div></div>

------------------

Каскадный сумматор:

- Размер: $O(n)$.
- Для таблицы истинности: $O(n^2)$.

</div><div class="col">

![](/fig/logic-adder-left-to-right.png)

</div></div>

----

##### Процесс каскадного сумматора

![](/fig/logic-adder-right-to-left.png)

![](/fig/logic-full-adder.png)

</div><div class="col">

```text
C0 _____________________________ (0)
         _______________________ (1)
A0 _____/                        (0)
         _______________________ (1)
B0 _____/                        (0)
S0 _____________________________ (0)

_________________ (1)
C1 ___________/                  (0)
         _______________________ (1)
A1 _____/                        (0)
B1 _____________________________ (0)
               ______
S1 ___________/      \__________ (0)

__________ (1)
C2 __________________/           (0)
A2 _____________________________ (0)
B2 _____________________________ (0)
                            ____ (1)
S2 ________________________/     (0)

^     ^      ^     ^
------------- time ---------------->
```

</div></div>

---

#### Свойства комбинационных схем

1. Возможность **установления стабильного состояния** при корректном входе (нет циклов).
1. **Задержка** установления состояния после изменения входных значений.
1. **Накопление ошибки** в физическом процессе, что может привести к ошибке на логическом уровне (буферы).
1. **Параллелизм уровня бит** (узлы с параллельным включением работают параллельно).
1. **Уровень линии**, не сигнал <br/> (как и с реле).

</div><div class="col">

^     ^      ^     ^
------------- time ---------------->
```

</div></div>

---

#### Реальная ситуация с двоичным кодированием

Вы ведь не думаете, что это на самом деле два состояния?

----

Заимствовано из стандарта для языка описания цифровых схем Verilog.

- Очевидное `0` и `1`.

<div>

- `x` — неизвестно, значение может быть произвольным, т.к. таблица истинности определена частично. Примеры:
    - деление на `0`;
    - квадратный корень из отрицательного числа;
    - пример "Шифратор (4-to-2)" выше.

</div>

<div>

- `z` — отключено, когда ваш источник данных (провод) висит в воздухе. `0` обычно не кодируют нулевым уровнем сигнала.

**Вопрос**: Как получить условный оператор?

</div>

---

### Условный оператор. Мультиплексор

Схемотехника не может не работать. **Уровень не может не быть**.

На уровне комбинационных схем без состояния: <br/> Спекулятивные вычисления и выбор нужного результата.

![*Мультиплексор (Wikipedia)*](/fig/multiplexer.png)

**"Скрутки"** — запрещены.

</div><div class="col">

Verilog:

```verilog
assign in0 = f0(...);
assign in1 = f1(...);

assign out = sel ? in0 : in1;
```

Python:

```python
in0 = f0(...)
in1 = f1(...)

out = in0 if sel else in1
```

</div></div>

---

### Состояние в комбинационной схеме

Триггер — класс электронных устройств, обладающих способностью длительно находиться в одном из двух устойчивых состояний и чередовать их под воздействием внешних сигналов.

Триггер позволяет:

1. Зафиксировать состояние линии на длительное время.
1. Ограничить распространение сигнала по схеме.
    - Разорвать цикл.
    - Сократить задержку в комбинационной схеме.

</div><div class="col">

![*Логическая схема с состоянием*](/fig/logic-with-state.png)

D-триггер.

</div></div>

----

#### Виды триггеров

1. Условие изменения состояния:
    - **по фронту**;
    - по уровню.
1. Интерфейс:
    - **D-триггер** (от англ. Delay) — запоминает состояние входа и выдаёт его на выход.
    - RS-триггер (от англ. Reset/Set) — асинхронный триггер, который сохраняет своё предыдущее состояние при неактивном состоянии обоих входов и изменяет своё состояние при подаче на один из его входов активного уровня.
    - и др.

---

#### Многотактовые схемы (в несколько тактов)

- (1) **Конвейерное исполнение**

- Количество стадий — количество параллельных задач.
    - Больше "разбиений" — ниже задержка схемы, выше частота.

![](/fig/scheme-sort.png)

----

- (2) **Spatial and Temporal Computation**

- Сложение 16 битных чисел:
    - сумматор на 16 бит и 1 такт.
    - сумматор на 8 бит и 2 такта + система управления.

</div><div class="col">

![](/fig/spatial-and-temporal-add16.png)

</div></div>

----

Сумматор на 8 бит и 2 такта + система управления

```text
+---------+     A[15:8]     +-----+                      receive always, latch if needed
|         +---------------->|     |                                       :
| A[15:0] |                 | MUX +-----+                                 :
|         +---------------->|     |     | A/2                             :      +--------+
+-------+-+     A[7:0]      +--+--+     |                                 +----->| C_high |
        ^                       ^       |                                 |      +---+----+
        |                       |       |         +-----+                 |          ^
latch_A-+              sel_A ---+       +-------->+     |        C[7:0]   |          |
                                                  | sum +------+----------+        latch_C
                                        +-------->+     |      |          |          high
+---------+     B[15:8]     +-----+     |         +--+--+      |          |
|         +---------------->|     |     | B/2        ^         | C[8]     |      +--------+
| B[15:0] |                 | MUX +-----+            |         |          +----->| C_low  |
|         +---------------->|     |                  |         |                 +---+----+
+-------+-+     B[7:0]      +-----+                +-----+     ++-----+              ^
        ^                      ^           sel---->+ MUX |     |carry |              |
        |                      |           carry   ++---++     ++---+-+            latch_C
latch_B-+             sel_B ---+                    ^   ^       |   ^               low
                                                    |   |       |   |
                                              0-----+   +-------+  latch_carry
```

----

- (3) **Синхронная схемотехника**
    - меньше гонок, проще синхронизация;
    - частота по самой медленной комбинационной схеме;
    - дискретизация входных сигналов по времени;
    - синхронность — в заданном диапазоне.

![](/fig/signal-time-discreet.png)

- (4) **Программное управление**

---

### Пример схемы с состоянием <br/> (почему уровень, а не сигнал)

Фрагмент лаб. №4. Управление указателем и чтение памяти данных.

```verilog
    latch ---------->+--------------+  addr   +--------+
    data             | data_address |---+---->|  data  |
    addr       +---->+--------------+   |     | memory |
               |                        |     |        |
           +-------+                    |     |        |
 signal -->|  MUX  |         +----------+     |        |
 data      +-------+         |                |        |
 address    ^     ^          |                |        |
 sel        |     |          |                |        | mem_out
            |     +---(+1)---+                |        |-----+
            |                |                |        |     |
            +---------(-1)---+                |        |     |
                                              +--------+     |
                                                             v
                                      signal_latch_acc    +--------------+    acc
                                     -------------------->| acc_internal |--------->
                                                          +--------------+
```

- `data_address` (за один такт)
    - $\rightarrow$ `data_memory[data_address]` $\rightarrow$ `acc_internal` (by latch)
    - $\rightarrow$ `(+1)` $\vee$ `(-1)` by MUX $\rightarrow$ `data_address` (by latch)

----

#### Реализация схемы на Verilog (техническое)

Интерфейс и инициализация

```verilog
module data_memory
  ( input wire clk

, input wire signal_latch_data_address
  , input wire signal_data_address_sel
  , input wire signal_latch_acc

, output wire  [7:0] acc
  );

reg  [3:0] data_address;
reg  [7:0] mem[15:0];
wire [7:0] mem_out;
reg  [7:0] acc_internal;

// not a part of hardware
integer i;
initial begin
  data_address = 0;
  for (i = 0; i < 8; i = i+1)
    mem[i] = i[7:0];
end
```

</div><div class="col">

Адресация

```verilog
always @(posedge clk)
  if ( signal_latch_data_address )
    data_address <= // < =
      signal_data_address_sel
      ? data_address + 1
      : data_address - 1;
```

Чтение аккумулятора

```verilog
assign mem_out = mem[data_address];

always @(posedge clk)
  if ( signal_latch_acc )
    acc_internal <= mem_out;  // < =

assign acc = acc_internal;

endmodule
```

</div></div>

----

#### Схема детальная с состоянием

![](/fig/bf-data-memory-scheme.png)

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

----

#### Временная диаграмма схемы с состоянием

![](/fig/bf-data-memory-wave-diagram.png)

```verilog
// signal will establish after each clock signal
latch_data_address <= 0; data_address_sel <= 0; latch_acc <= 0; @(posedge clk);
repeat(2) @(posedge clk);

// addr to 3
latch_data_address <= 1; data_address_sel <= 1; latch_acc <= 0; @(posedge clk);
latch_data_address <= 1; data_address_sel <= 1; latch_acc <= 0; @(posedge clk);
latch_data_address <= 1; data_address_sel <= 1; latch_acc <= 0; @(posedge clk);

// latch acc
latch_data_address <= 0; data_address_sel <= 0; latch_acc <= 1; @(posedge clk);

// addr to 2
latch_data_address <= 1; data_address_sel <= 0; latch_acc <= 0; @(posedge clk);

// addr to 1 and latch acc at same time
latch_data_address <= 1; data_address_sel <= 0; latch_acc <= 1; @(posedge clk);

latch_data_address <= 0; data_address_sel <= 0; latch_acc <= 0; @(posedge clk);
repeat(2) @(posedge clk);
```

---

### Ключевые отличия схемотехники <br/> от программирования

1. Все процессы между регистрами всегда происходят параллельно. Не читайте код как алгоритм, рисуйте схему.
2. Передача сигнала — физический аналоговый процесс. Есть питание и контакт — есть передача. Сигнал не может не идти.
3. Нет понятия "система остановилась". Она всегда работает, если есть питание.
4. Таблица истинности неполна — результат будет случайным, но будет (и возможно воспроизводимым).

---

Мы обсудили:

1. Понятия системы и архитектуры.
1. Примеры ещё не компьютерных систем
1. Базис электронных компьютерных систем
1. Параллелизм уровня битов, основы цифровой схемотехники.

1. Как производится аппаратное обеспечение?
1. Что такое Hardware и Software. Что такое Software, зачем и какое бывает? Программное управление.
1. Что такое процессор? Какие бывают и как они устроены?
1. Параллельные процессоры...