Головоломка с логическими вентилями и решение на HDL
Некоторое время назад Стас Кельвич подкинул мне занятную головоломку про логические вентили. Задача формулируется крайне просто, а вот найти решение среднему по больнице человеку не так-то легко. Должен предупредить, что это одна из тех задач, которая не будет давать вам спать, пока вы ее не решите. Также должен предупредить, что в этой заметке содержится полное решение.
Задача формулируется следующим образом:
Есть три логических входа: A, B, C. Нужно построить цепь на логических вентилях, выдающую на выходе !A, !B и !C. При этом в цепи можно использовать не более двух вентилей НЕ, а также неограниченное количество И и ИЛИ. Другие вентили (XOR, NAND, …) использовать нельзя.
Если вы не сильно интересуетесь железом, то задачу можно переформулировать и так:
Есть процедура, принимающая три булевых аргумента – a, b и c. Нужно посчитать !a, !b и !c, используя не более двух логических отрицаний. Вы не можете использовать условные операторы, циклы и прочие конструкции выбранного вами языка программирования. Вы только можете объявлять переменные булева типа, а также использовать присваивание, неограниченное количество операторов логического И и ИЛИ, а также не более двух операторов НЕ.
Ниже приведено решение задачи на SystemVerilog:
`timescale 1ns / 1ps
module puzzle(
input logic CLK100MHZ,
input logic [3:0] sw,
output logic [3:0] led
);
always_ff @(posedge CLK100MHZ)
begin
logic a,b,c,
two_or_more_high, two_or_more_low,
odd_high, even_high,
zero_high, one_high, two_high,
not_a, not_b, not_c;
a <= sw[0];
b <= sw[1];
c <= sw[2];
two_or_more_high <= (a && b) || (b && c) || (a && c);
two_or_more_low <= ! two_or_more_high;
odd_high <= (a && b && c) || ( (a || b || c) && two_or_more_low );
even_high <= ! odd_high;
zero_high <= two_or_more_low && even_high;
one_high <= two_or_more_low && odd_high;
two_high <= two_or_more_high && even_high;
not_a <= zero_high || (one_high && (b || c)) || (two_high && b && c);
not_b <= zero_high || (one_high && (a || c)) || (two_high && a && c);
not_c <= zero_high || (one_high && (a || b)) || (two_high && a && b);
led[0] <= not_a;
led[1] <= not_b;
led[2] <= not_c;
end
endmodule
Легко проверить, что в нем используются только операторы && и ||, а также ровно два логических отрицания. С тем же успехом можно предложить решение на C или любом другом языке. Просто я увидел возможность попрактиковаться в SystemVerilog и воспользовался ей.
Если вам нравятся головоломки, вас также могут заинтересовать следующие заметки из этого блога:
- Интересные задачки с собеседований (и типа конкурс);
- Решение задачи про игру «кошки-мышки» на OCaml;
- Решение задачи «кто на ком женат» с помощью Haskell;
- Мое решение задачи об олимпийских кольцах на Erlang;
- Решение задачи о кодировании цифр на Haskell и Perl;
- Задача о роботе-пылесосе без датчиков и решение на Haskell;
- Алгоритм поиска A* на Haskell и превращение мухи в слона;
А какие задачки / головоломки знаете вы?