Как шлёпанцы запоминают: глубокое понимание последовательных схем / Хабр

Flip‑flop (в дословном переводе — «шлёпанцы») — так называется элемент, благодаря которому микропроцессор в вашем компьютере, да и вообще любой современный чип, обрёл способность запоминать.

Представьте абстрактную схему, у которой есть вход и выход. Интуитивно понятно: если мы подаём на схему какое‑то входное значение или меняем его, меняется и выходное значение — то есть выход напрямую зависит от входа. Но как получилось, что такую, казалось бы, чисто комбинационную схему (без памяти) заставили запоминать входное значение и использовать его в дальнейшем для вычисления новых выходов?

В этой статье я хочу:

разобраться, как мы получили память (flip‑flop);
заодно затронуть, откуда берутся проблемы setup/hold time и метастабильности, связанные с памятью.

Начнём, пожалуй, с комбинационных схем. Любую такую схему можно описать с помощью булевой алгебры. Например, операцию сложения трёх бинарных разрядов:

можно описать следующими уравнениями:

$\begin{equation} S = A \oplus B \oplus C_{in} \end{equation}$ $\begin{equation} C_{out} = (A \cdot B) + (B \cdot C_{in}) + (A \cdot C_{in}) \end{equation}$

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

Можно замкнуть цепь — соединить вход схемы с её же выходом — и вывести из этой петли один выходной контакт.

Звучит немного безумно, но такая схема действительно обладает свойством сохранять значение (напомню, что я рассматриваю схему только на логическом, цифровом уровне, без учёта конкретного семейства логики (logic family), в котором она в итоге будет реализована). Правда, сохранять она умеет, а вот записывать — нет: если изначальное значение равно 1, схема будет бесконечно «гонять» эту единицу по кругу, и перезаписать её мы не сможем. Значит, нужен способ задавать (и менять) хранимое значение.

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

Селектор мультиплексора назовём clk: когда он равен 0 — режим хранения, MUX пропускает через себя сигнал внутренней петли; когда он равен 1 — режим записи, MUX пропускает новое входное значение. В теории это должно работать точно как D‑триггер‑защёлка (D latch). Но как это выглядит на практике? Попробуем записать несколько значений в такую «защёлку» в симуляции и посмотрим на результат.

`timescale 1us / 1ns

module custom_d_latch(
	output wire Q,
	input clk, D
);
	wire D_and_out, Q_and_out, inv_clk;

	not (inv_clk, clk);
	and (D_and_out, D, clk);
	and (Q_and_out, Q, inv_clk);
	or (Q, D_and_out, Q_and_out);

endmodule


module stimulus;
	localparam DELAY=1;
	reg clk=0, D=1;
	wire Q;

	custom_d_latch dl(.clk(clk), .D(D), .Q(Q));

	initial begin
		$monitor("Q=%d", Q);
		set_q(1'b0);
		set_q(1'b1);
	end

	task set_q(input d);
	begin
		D=d;
		clk=1;
		#DELAY;
		clk=0;
		#DELAY;
	end
	endtask

endmodule

output:
Q=0
Q=1
Q=0

Несмотря на то что последнее записанное значение — 1, Q снова возвращается к 0. Это происходит потому, что путь A (схема 3) быстрее, чем путь B (на пути B стоит дополнительный инвертор). При переходе clk из 1 в 0 из‑за разницы в задержках распространения сигнала возникает короткое «окно» с неверным (0) значением. По сути, это гоночное, метастабильное поведение схемы.

Есть два выхода: либо вручную выравнивать задержки каждого пути, либо переработать схему средствами булевой алгебры и проверить все переходы входных сигналов на появление таких «окон» с неправильными значениями. Пойдём по второму пути.

Минимизированная формула нашей схемы с мультиплексором:

$Q^+ = D \cdot clk + \overline{clk} \cdot Q$

По теореме консенсуса мы можем добавить продукт DQ и вывести Q за скобку:

$Q^+ = D \cdot clk + \overline{clk} \cdot Q + (D \cdot Q)$ $Q^+ = D \cdot clk + Q \cdot (\overline{clk} + D)$

Осталось применить закон де Моргана, чтобы получить формулу, реализуемую целиком на элементах NAND:

$Q^+ = D \cdot clk + Q \cdot (\overline{clk \cdot \overline{D}})$ $Q^+ = \overline{\overline{D \cdot clk + Q \cdot (\overline{clk \cdot \overline{D}})}}$ $Q^+ = \overline{ \overline{(D \cdot clk)} \cdot \overline{Q \cdot (\overline{clk \cdot \overline{D}})} }$

Посмотрим, как выглядит схема, реализующая это булево уравнение:

Это и есть D‑триггер‑защёлка (D‑type latch)! Проверим все переходы на предмет метастабильного поведения.

`timescale 1us / 1ns

module custom_d_latch_nand(
	output wire Q,
	input clk, D
);
	not (inv_D, D);
	nand (D_nand_clk, D, clk);
	nand (iD_nand_clk, inv_D, clk);
	nand (Q_nand, iD_nand_clk, Q);
	nand (Q, Q_nand, D_nand_clk);

endmodule

module stimulus;
	localparam DELAY=1;
	reg clk=0, D=1;
	wire Q;

	custom_d_latch_nand dl(.clk(clk), .D(D), .Q(Q));

	initial begin
		$monitor("Q=%d", Q);
		set_q(1'b0);
		#DELAY;
		set_q(1'b0);
		#DELAY;
		set_q(1'b1);
		#DELAY;
		set_q(1'b1);
		#DELAY;
		set_q(1'b0);
		#DELAY;
	end

	task set_q(input d);
	begin
		$display("setting q = %b\n", d);
		D=d;
		clk=1;
		#DELAY;
		clk=0;
		#DELAY;
	end
	endtask

endmodule

output:

setting q = 0

Q=0
setting q = 0

setting q = 1

Q=1
setting q = 1

setting q = 0

Q=0

На этот раз никаких неожиданных переходов, как в прошлый раз. Если соединить две такие защёлки в конфигурацию master‑slave, получится flip‑flop — но сейчас не об этом. Если разобрать SR‑защёлку — «зерно», лежащее в основе всех подобных схем, — получится примерно такой мультиплексор:

Главное, что нам удалось, — заглянуть внутрь «чёрного ящика» flip‑flop и понять, откуда берётся такая на первый взгляд странная схема. Точно так же можно разобрать и другие типы цифровой памяти (JK‑, T‑триггеры) — все они в конечном счёте базируются на SR‑защёлке.

Взгляд на такие схемы как на замкнутый в петлю мультиплексор даёт интересную перспективу на метастабильность и setup‑violation. При метастабильности ячейка памяти начинает «мигать», постоянно меняя значение, — потому что в замкнутую петлю мультиплексора одновременно попадают противоречивые значения. Представьте стабильную петлю со значением 1, в которую вдруг частично «просочилось» значение 0. Это похоже на трубу с водой, в которую попали пузырьки воздуха: на выходе течёт вода, но время от времени — воздух, то есть поток нестабилен.

Так же увидели, что метастабильность возникает не только из‑за нарушения временных характеристик (setup/hold), но и из‑за неправильно спроектированной схемы самого flip‑flop.