edu-csa

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

## Лекция 4

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

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

---

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

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

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

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

</div></div>

----

<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$ — результат;
- $C_{in}$, $C_{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. **Уровень линии**, не сигнал (как и в реле).

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

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

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

*Та же временная диаграмма каскадного сумматора*

</div></div>

---

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

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

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

----

Из Verilog (Hardware Description Language, HDL).

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

Почему двоичное? См. в разделе "Кодирование".

---

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

Два сценария:

1. Как выбрать данные из двух источников? 
2. Как отправить данные в один из двух источников?

---

### Условный оператор. Выборка

"Скрутки" — запрещены $\rightarrow$ **Мультиплексор**

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

```verilog
assign in0 = f0(...);         // Verilog
assign in1 = f1(...);
assign out = sel ? in0 : in1;
```

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

```python
in0 = f0(...)                 # Python
in1 = f1(...)
out = in0 if sel else in1
```

</div></div>

Почему не реализуется как "переключатель" (обычно)?

1. Нет усиления/восстановления сигнала.
1. Риск зависшего/неопределённого выхода.

----

#### Цифровой мультиплексор (таблица истинности)

| $sel$ | $in_0$ | $in_1$ | $out$ |
| :---: | :----: | :----: | :---: |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |

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

```text
 ¬sel ──┐
        ├──[AND]──┐
  in0 ──┘         │
                  ├──[OR]──► out
  sel ──┐         │
        ├──[AND]──┘
  in1 ──┘
```

$out = \overline{sel} \cdot in_0 \vee sel \cdot in_1$

</div></div>

----

#### Условный оператор. Отправка

Демультиплексор — зеркало мультиплексора: один вход, $N$ выходов.

| $sel$ | $X$ | $A$ | $B$ |
| :---: | :---: | :---: | :---: |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 |

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

```text
        ┌──(¬sel)──[AND]──► A
   X ───┤
        └──( sel)──[AND]──► B
```

$A = X \cdot \overline{sel}$, $\quad B = X \cdot sel$

</div></div>

**Не использовать в схемах!** Почему?

<div><code>0</code> и <code>1</code> — равноправные значения!</div>

---

### Схемы с состоянием

<dl>
  <dt> Триггер </dt>
  <dd>  элемент схемы хранящий 1 бит — выход зависит не только от входов, но и от состояния. </dd>
</dl>
 
<div class="row"><div class="col">

Позволяет:

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

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

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

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

</div></div>

----

#### `DFF` (D Flip-Flop), D-триггер

`D` меняется когда угодно, но `Q` перескакивает на новое значение только в момент фронта `clk` — и держит его до следующего фронта.

```text
        ┌───────┐
 D ────►│  DFF  ├────► Q
        │       │
    clk►│       │
        └───────┘
```

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

```text
           _____________________________ (1)
D   ______/                              (0)
               ______________ (1)
clk __________/              \__________ (0)
                 ________________________ (1)
Q   ____________/                         (0)
              ^ ^
------------- фронт --------------------->
```

</div></div>

---

#### Регистр. Защёлкивание по условию: Enable

1. `clk` тикает одинаково каждый такт.
2. Мультиплексор определяет, будет ли обновлено значение.
    - `en = 1` — новое значение.
    - `en = 0` — старое значение.

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

```text
 D_new ──┐
         ├──[ MUX ]──► D ──[ DFF ]──┬──► Q
    ┌───►┘      ▲                ▲  │
    │           │                │  │
    │          en               clk │
    │                               │
    └───────────────────────────────┘
```

```text
           ______            ______       (1)
clk ______/      \__________/      \_____ (0)
                         ________________ (1)
en  ____________________/                 (0)
         ________________________________ (1)
D   ____/                                 (0)
                             ____________ (1)
Q   ________________________/             (0)
          ^                 ^
       en=0 -- Q         en=1 -- Q
      не меняется       захватывает D
```

</div></div>

----

<dl>
  <dt> Регистровый файл </dt>
  <dd>  массив из $2^n$ регистров с произвольным доступом по номеру. </dd>
</dl>
 
1. **Запись**: `WADDR` ($n$ бит) $\rightarrow$ `decoder` $\rightarrow$ `enable` ($1$ бит) для одного регистра
    - по фронту `clock`.
1. **Чтение**: `RADDR` ($n$ бит) $\rightarrow$ `multiplexor` выбирает значение одного регистра
    - комбинационное.
1. Число независимых портов чтения/записи = число мультиплексоров/декодеров.

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

![*Регистровый файл, 2 порта чтения + 1 порт записи (Wikipedia)*](/fig/register-file-3-port.svg)

</div></div>

---

#### Многотактовые схемы

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

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

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

----

##### (2) **Синхронная схемотехника**

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

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

----

##### (3) **Spatial** vs. **Temporal** Computation

Сложение 16-битных чисел:

1. сумматор на 16 бит и 1 такт;
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
```

Notes:

0. `latch_A, latch_B` $\longrightarrow$ `sel_A = sel_B = low; sel_carry = 0`
1. `latch_C_low, latch_carry` $\longrightarrow$ `sel_A = sel_B = high; sel_carry = C[8]`
2. `latch_C_high` $\longrightarrow$ ...

----

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

Выбираем регистры входа, регистр выхода, и комбинационную схему.

```text
    ┌──────────────────────────────────────┐
    │         Регистр инструкции           │
    └─┬───────┬──────┬─────────────────┬───┘
      │       │      │                 │
    waddr  raddr1 raddr2              sel
      │       │      │                 │
      │       ▼      ▼                 └────────────────────┐
      │    ┌────────────┐                                   │
      └───►│            ├──── rdata1 ─────┐                 │
           │  РегФайл   │                 │                 │
      ┌───►│            ├──── rdata2 ─────┤                 │
      │    └────────────┘                 │                 │
      │                                   ▼                 │
      │                    ┌─────────────────────────────┐  │
      │                    │   КС1   ...   КС2   ...     │  │
      │                    └─────────────────────────────┘  │
      │                                   │                 │
      │                                   ▼                 │
      │                             ┌───────────┐           │
      │                             │    MUX    │<──────────┘
      │                             └─────┬─────┘
      │  wdata                            │
      └───────────────────────────────────┘
```

---

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

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

![](/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>

---

### Представления чисел и данных

<dl>
  <dt> Машинное слово </dt>
  <dd>  фрагмент данных фиксированного размера, естественный для обработки вычислителем как единое целое. Примеры: сложение, пересылка и т.п. </dd>
</dl>
 
![](/fig/big-little-endian.png)

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

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

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

</div></div>

----

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

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

---

<dl>
  <dt> Позиционная система счисления </dt>
  <dd>  значение цифры зависит от её позиции (разряда): $N = \sum_i d_i \cdot b^i$, $b$ — основание (2, 10, 16...). </dd>
</dl>
 
</div><div class="col">

<dl>
  <dt> Дополнительный код (two's complement) </dt>
  <dd>  представление отрицательных целых — инвертировать биты и прибавить 1. Позволяет складывать и вычитать положительные и отрицательные числа одной и той же схемой. </dd>
</dl>
 
</div></div>

Пример (4 бита): $5 = 0101$, $-5 = \overline{0101} + 1 = 1011$.

----

<dl>
  <dt> One-hot кодирование </dt>
  <dd>  способ кодирования $N$ состояний $N$-битным словом, в котором ровно один бит установлен в <code>1</code>, остальные — в `0`. </dd>
</dl>
 
</div><div class="col">

**Где применяется**:

1. Chip Select (CS), Write enable (WE) — "активен ли я".
1. Состояния конечного автомата.

</div></div>

| Значение | Двоичный | One-hot |
|:--------:|:--------:|:-------:|
| 0 | `00` | `0001` |
| 1 | `01` | `0010` |
| 2 | `10` | `0100` |
| 3 | `11` | `1000` |

----

<dl>
  <dt> BCD </dt>
  <dd>  каждый десятичный разряд — отдельным 4-битным кодом. </dd>
</dl>
 
**Зачем**: точная десятичная арифметика без периодических дробей.

**Где применяется**:

- Калькуляторы.
- Кассы.
- Семисегментные индикаторы.

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

![](/fig/code_BCD.png)

</div></div>

----

<dl>
  <dt> Код Грея </dt>
  <dd>  соседние по значению комбинации отличаются только в одном разряде (код циклический). </dd>
</dl>
 
**Зачем**: при обычном счёте возможен glitch — одновременная смена нескольких бит. В коде Грея — всегда один бит.

**Где применяется**:

- Энкодеры положения.
- Счётчики состояний.
- Карты Карно.

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

![](/fig/gray_code.png)

**Построение**: $g_i = b_i \oplus b_{i+1}$, $b_n = 0$.

**Декодирование**: $b_i = g_i \oplus b_{i+1}$ (от старшего разряда).

</div></div>

----

#### Коды обнаружения и исправления ошибок (offtopic)

Защита от случайного изменения бита.

1. **Бит чётности (parity)** — лишний бит делает сумму единиц чётной.
1. **Код Хэмминга** — несколько битов чётности расположены так, что их комбинация указывает номер ошибочного бита.

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

Где используется:

- Шины передачи данных.
- Error-Correcting Code (ECC) память.
- Там, где "молча перевернувшийся бит" дороже одного лишнего провода.

</div></div>