Головоломка с логическими вентилями и решение на HDL

24 июля 2017

Некоторое время назад Стас Кельвич подкинул мне занятную головоломку про логические вентили. Задача формулируется крайне просто, а вот найти решение среднему по больнице человеку не так-то легко. Должен предупредить, что это одна из тех задач, которая не будет давать вам спать, пока вы ее не решите. Также должен предупредить, что в этой заметке содержится полное решение.

Задача формулируется следующим образом:

Есть три логических входа: 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 и воспользовался ей.

Если вам нравятся головоломки, вас также могут заинтересовать следующие заметки из этого блога:

А какие задачки / головоломки знаете вы?

Метки: , .

Подпишись через RSS, E-Mail, Google+, Facebook, Vk или Twitter!

Понравился пост? Поделись с другими: