Design Recap

The circuit from my last post:

oS.1:
TH12(
  TH22(
    TH13(iA.1, iB.1, iC.1), -- 1 <= NumBits
    TH23(iA.0, iB.0, iC.0)), -- NumBits < 2
  TH33(iA.1, iB.1, iC.1))); -- 3 <= NumBits

oS.0:
TH12(
  TH33(iA.0, iB.0, iC.0), -- NumBits < 1
  TH22(
    TH23(iA.1, iB.1, iC.1), -- 2 <= NumBits
    TH13(iA.0, iA.0, iA.0)); -- NumBits < 3

oC.1: TH23(iA.1, iB.1, iC.1) -- 2 <= NumBits

oC.0: TH23(iA.0, iB.0, iC.0) -- NumBits < 2

Optimized

The structural VHDL implementation:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.ncl.all;

entity FullAdder is
  port(iC : in ncl_pair;
       a : in ncl_pair;
       b : in ncl_pair;
       oS : out ncl_pair;
       oC : out ncl_pair);
end FullAdder;

architecture structural of FullAdder is
  type first_layer is array (integer range <>) of std_logic_vector(0 to 2);
  signal first_layer_inputs : first_layer(0 to 7);
  signal intermediate : std_logic_vector(0 to 7);
  signal inputs : ncl_pair_vector(0 to 2);

begin
  inputs(2) <= a;
  inputs(1) <= b;
  inputs(0) <= iC;
  input_layer: for i in 0 to 7 generate
    bits: for ibit in 0 to 2 generate
      Input0Selection: if (to_unsigned(2**iBit, 3) and to_unsigned(i, 3)) = 0 generate
        first_layer_inputs(i)(iBit) <= inputs(iBit).Data0;
      end generate;
      Input1Selection: if (to_unsigned(2**iBit, 3) and to_unsigned(i, 3)) > 0 generate
        first_layer_inputs(i)(iBit) <= inputs(iBit).Data1;
      end generate;
    end generate;
    gate: THmn
            generic map(M => 3, N => 3)
            port map(inputs => first_layer_inputs(i),
                     output => intermediate(i));
  end generate;

  oS0: THmn
         generic map(M => 1, N => 4)
         port map(inputs(0) => intermediate(0),
                  inputs(1) => intermediate(3),
                  inputs(2) => intermediate(5),
                  inputs(3) => intermediate(6),
                  output => oS.DATA0);

  oS1: THmn
         generic map(M => 1, N => 4)
         port map(inputs(0) => intermediate(1),
                  inputs(1) => intermediate(2),
                  inputs(2) => intermediate(4),
                  inputs(3) => intermediate(7),
                  output => oS.DATA1);

  oC0: THmn
         generic map(M => 1, N => 4)
         port map(inputs(0) => intermediate(0),
                  inputs(1) => intermediate(1),
                  inputs(2) => intermediate(2),
                  inputs(3) => intermediate(4),
                  output => oC.DATA0);

  oC1: THmn
         generic map(M => 1, N => 4)
         port map(inputs(0) => intermediate(3),
                  inputs(1) => intermediate(5),
                  inputs(2) => intermediate(6),
                  inputs(3) => intermediate(7),
                  output => oC.DATA1);
end structural;

architecture optimized of FullAdder is
  signal sLT2 : std_logic;
  signal sLT3 : std_logic;
  signal sGE2 : std_logic;
  signal sGE1 : std_logic;
  signal sEQ3 : std_logic;
  signal sEQ2 : std_logic;
  signal sEQ1 : std_logic;
  signal sEQ0 : std_logic;
begin
  LT2: THmn
         generic map(M => 2, N => 3)
         port map(inputs(0) => a.DATA0,
                  inputs(1) => b.DATA0,
                  inputs(2) => iC.DATA0,
                  output => sLT2);

  GE2: THmn
         generic map(M => 2, N => 3)
         port map(inputs(0) => a.DATA1,
                  inputs(1) => b.DATA1,
                  inputs(2) => iC.DATA1,
                  output => sGE2);

  GE1: THmn
         generic map(M => 1, N => 3)
         port map(inputs(0) => a.DATA1,
                  inputs(1) => b.DATA1,
                  inputs(2) => iC.DATA1,
                  output => sGE1);

  EQ1: THmn
         generic map(M => 2, N => 2)
         port map(inputs(0) => sGE1,
                  inputs(1) => sLT2,
                  output => sEQ1);

  EQ3: THmn
         generic map(M => 3, N => 3)
         port map(inputs(0) => a.DATA1,
                  inputs(1) => b.DATA1,
                  inputs(2) => iC.DATA1,
                  output => sEQ3);

  S1: THmn
        generic map(M => 1, N => 2)
        port map(inputs(0) => sEQ1,
                 inputs(1) => sEQ3,
                 output => oS.DATA1);

  EQ0: THmn
         generic map(M => 3, N => 3)
         port map(inputs(0) => a.DATA0,
                  inputs(1) => b.DATA0,
                  inputs(2) => iC.DATA0,
                  output => sEQ0);

  LT3: THmn
         generic map(M => 1, N => 3)
         port map(inputs(0) => a.DATA0,
                  inputs(1) => b.DATA0,
                  inputs(2) => iC.DATA0,
                  output => sLT3);

  EQ2: THmn
         generic map(M => 2, N => 2)
         port map(inputs(0) => sGE2,
                  inputs(1) => sLT3,
                  output => sEQ2);

  S0: THmn
        generic map(M => 1, N => 2)
        port map(inputs(0) => sEQ2,
                 inputs(1) => sEQ0,
                 output => oS.DATA0);

  oC.DATA0 <= sLT2;
  oC.DATA1 <= sGE2;

end optimized;

This VHDL implementation of the the un-optimized design  uses generic loops to setup the first layer (the first layer uses all combinations of group values). The second layer is set up manually.

The optimized design’s signals are named in terms of relations Greater or Equal to #, Less Than #, and EQual to #. So sEQ1 is asserted when 1 input group is set to 1, and sGE2 is asserted when at least 2 input groups are set to 1.

Testing

The test script runs through all combinations of inputs. I ran the tests with both versions. Here’s the result, no surprises really.

Commit: a7a9dba, d645811

See this post for the design of the NCL Register.

Implementation

I implemented this module structurally, with a for...generate (you’ll find that I’m a big fan of generics if you keep up with the blog).

This module assumes that all groups (DAT0, DATA1, … DATAn) are dual rail (capped at DATA1); if I need other encodings, I’ll make them as separate modules later. I added a generic RegisterDelay input so that I can better observe pipelines of components (if it is stable for time, then I can read values off the waves easier)

library ieee;
use ieee.std_logic_1164.all;
use work.ncl.all;

entity RegisterN is
  generic(N : integer := 1;
  RegisterDelay : time := 20 ns);
  port(inputs : in ncl_pair_vector(0 to N-1);
  from_next : in std_logic;
  output : out ncl_pair_vector(0 to N-1);
  to_prev : out std_logic);
end RegisterN;

architecture structural of RegisterN is
  signal outs : std_logic_vector(0 to (2*N)-1);
  signal watcher_out : std_logic := '0';
begin

register_gates: for i in 0 to N-1 generate
  T22_i0 : THmn
             generic map(N => 2, M => 2, Delay => RegisterDelay)
             port map(inputs(0) => inputs(i).DATA0,
                      inputs(1) => from_next,
                      output => outs(2*i));
  output(i).DATA0 <= outs(2*i);

  T22_i1 : THmn
             generic map(N => 2, M => 2, Delay => RegisterDelay)
             port map(inputs(0) => inputs(i).DATA1,
                      inputs(1) => from_next,
                      output => outs(2*i+1));
  output(i).DATA1 <= outs(2*i+1);

end generate register_gates;

  watcher: THmn
             generic map (N => N*2, M => N)
             port map (inputs => outs,
                       output => watcher_out);
  WatcherOutput: to_prev <= NOT watcher_out;
end structural;

Testing

For Testing I again used a test script, available on GitHub. It goes through the values, and makes sure that data is sent through correctly. It also checks that DATA/NULL wavefronts are delayed correctly by the control signal (handshaking). Note that the to_prev output signal is always in the ‘opposite’ state of the outputs (outputs NULL => to_prev 1 and otuputs DATA => to_prev 0) there is actually a 1-ns delay (default) in the watcher gate (a TH36 in this case).

Commits: 5d349e7, 4ecfe25, bf16da3

See this post for the theory and design of the NCL Half Adder.

Design Recap

Here’s the circuit design:

(simple version)

(optimized version)

The top two gates are THxor0 gates, the next is a TH34w22, and the last one is a TH22 gate. I will implement this structurally, a fairly straightforward process in this case.

Implementation

library ieee;
use ieee.std_logic_1164.all;
use work.ncl.all;

entity HalfAdder is
 port(a : in ncl_pair;
      b : in ncl_pair;
      s : out ncl_pair;
      c : out ncl_pair);
end HalfAdder;

architecture structural of HalfAdder is
  signal a0b0_ins : std_logic_vector(0 to 1);
  signal a0b0_out : std_logic;
  signal a0b1_ins : std_logic_vector(0 to 1);
  signal a0b1_out : std_logic;
  signal a1b0_ins : std_logic_vector(0 to 1);
  signal a1b0_out : std_logic;
  signal a1b1_ins : std_logic_vector(0 to 1);
  signal a1b1_out : std_logic;

signal s0_ins : std_logic_vector(0 to 1);
  signal s0_out : std_logic;
  signal s1_ins : std_logic_vector(0 to 1);
  signal s1_out : std_logic;

  signal c0_ins : std_logic_vector(0 to 2);
  signal c0_out : std_logic;
begin
  a0b0_ins(0) <= a.DATA0;
  a0b0_ins(1) <= b.DATA0;   T21_A0B0 : THmn
               generic map(N => 2, M => 2)
               port map(inputs => a0b0_ins,
                        output => a0b0_out);

  a0b1_ins(0) <= a.DATA0;
  a0b1_ins(1) <= b.DATA1;   T21_A0B1 : THmn
               generic map(N => 2, M => 2)
               port map(inputs => a0b1_ins,
                        output => a0b1_out);

  a1b0_ins(0) <= a.DATA1;
  a1b0_ins(1) <= b.DATA0;   T21_A1B0 : THmn
               generic map(N => 2, M => 2)
               port map(inputs => a1b0_ins,
                        output => a1b0_out);

  a1b1_ins(0) <=  a.DATA1;
  a1b1_ins(1) <= b.DATA1;   T21_A1B1 : THmn
               generic map(N => 2, M => 2)
               port map(inputs => a1b1_ins,
                        output => a1b1_out);

  s1_ins(0) <= a0b1_out;
  s1_ins(1) <= a1b0_out;   T21_S1: THmn
            generic map(N => 2, M => 1)
            port map(inputs => s1_ins,
                     output => s1_out);
  s.DATA1 <= s1_out;

  s0_ins(0) <= a0b0_out;
  s0_ins(1) <= a1b1_out;   T21_S0: THmn
            generic map(N => 2, M => 1)
            port map(inputs => s0_ins,
                     output => s0_out);
  s.DATA0 <= s0_out;
  c.DATA1 <= a1b1_out;

  c0_ins(0) <= a1b0_out;
  c0_ins(1) <= a0b1_out;
  c0_ins(2) <= a0b0_out;   T31_C0: THmn
            generic map(N => 3, M => 1)
            port map(inputs => c0_ins,
                     output => c0_out);
  c.DATA0 <= c0_out;
end structural;

architecture optimized of HalfAdder is
begin   
  Sum0: THxor0
          port map(A => A.DATA0,
                   B => B.DATA0,
                   C => A.DATA1,
                   D => B.DATA1,
                   output => s.DATA0);

  Sum1: THxor0
          port map(A => A.DATA1,
                   B => B.DATA0,
                   C => A.DATA0,
                   D => B.DATA1,
                   output => s.DATA1);

  Carry0: THmn
            generic map(N => 6, M => 3)
            port map(inputs(0) => A.DATA0,
                     inputs(1) => A.DATA0,
                     inputs(2) => B.DATA0,
                     inputs(3) => B.DATA0,
                     inputs(4) => A.DATA1,
                     inputs(5) => B.DATA1,
                     output => c.DATA0);

  Carry1: THmn
            generic map(N => 2, M => 2)
            port map(inputs(0) => A.DATA1,
                     inputs(1) => B.DATA1,
                     output => c.DATA1);
end optimized;

I have two implementations here. The basic version, and the optimized version. There’s not a lot to explain beyond VHDL syntax. The gates are built as in the diagram, though some orderings might have changed.

Testing

The test script runs through all input values, clearing to NULL in between. The test simulation run:

If you have any questions, leave a comment below.

Commit: a57125a

The THxor0 Gate is a 4-input gate with logic function AB + CD. Data that I have found about implementing this gate is all at the transistor level. For now, I’ll make a behavioral model, but I may later design a structural version (technically a 1-bit state machine). Regardless, I think this implementation is actually synthesizable, so that’s nice

The behavioral implementation:

entity THxor0 is
  generic(Delay : time := 1 ns);
  port(A, B, C, D : in std_logic;
       output : out std_logic);
end THxor0;

architecture behavioral of THxor0 is
begin
  process (A, B, C, D)
  begin
    if (A = '0' and B = '0' and C = '0' and D = '0') then
      output <= '0';
    elsif ((A and B) or (C and D)) = '1' then
      output <= '1';
    end if;
  end process;
end behavioral;

The process statement again has 2 conditions: Set and Clear. If neither is met, the gate holds it’s state.

Testing

The test script was a modified version of the THmn test script. See scripts/test/test_threshold_gate.tcl on GitHub. Below is an excerpt from the test simulation session.

See this post for a Half Adder component that uses this gate.

Commit: 19c8318

Now that we’ve talked about what NCL is, it’s time to actually make something with it.

For complete project files, see my GitHub

I will be using Modelsim as my IDE (with a little Notepad++) and VHDL. I’ll be starting with simulation, but eventually I want to load something on an FPGA, so I’ll be keeping an eye for synthesis where I can.

Setup

The first thing to do is make a package with some useful types and functions. I’ll call it work.NCL:

library ieee;
use ieee.std_logic_1164.all;

package ncl is
  type ncl_pair is record
    data0 : std_logic;
    data1 : std_logic;
  end record ncl_pair;
 
  type ncl_pair_vector is array (integer range <>) of ncl_pair;

  component THmn is
    generic(M : integer := 1;
            N : integer := 1;
            Delay : time := 1 ns);
    port(inputs : in std_logic_vector(0 to N-1);
         output : out std_logic);
  end component THmn;
end ncl;

I’ve decided to make each NCL line be std_logic to allow the synthesizer to use standard logic functions.

The gates themselves operate on single lines, but components take in pairs, though it could be expanded to triples or higher if needed later. Before, we can do anything else we need to build the NCL Threshold gate.

Implementation

I tried to implement the threshold gate structurally with the generic parameter, but I was unable to make it work, I’ll look into making a structural version someday.

For synthesis, I may need to make parameter-specific components. The generic component could maybe act as an automatic selector, instantiating the correct implementations.

The most basic description of a threshold gate is that it sets when enough inputs are set, when no inputs are set, the output clears, otherwise no action is taken. For now, I have decided to implement the threshold gate without weights, and instead to use repeated inputs (handled by the calling entity) if I need weights. A TH23W2 would be instantiated as a TH24, and the first input would be given twice.

Here goes:

library ieee;
use ieee.std_logic_1164.all;

use work.ncl.all;

entity THmn is
  generic(M : integer := 1;
          N : integer := 1;
          Delay : time := 1 ns);
  port(inputs : in std_logic_vector(0 to N-1);
       output : out std_logic := '0');
end THmn;

architecture simple of THmn is
begin
  ThresholdGate: process(inputs)
    variable num_1 : integer;
  begin
    num_1 := 0;
    for i in 0 to N-1 loop
      if inputs(i) = '1' then
        num_1 := num_1 + 1;
      end if;
    end loop;
    if num_1 >= M then
      output <= '1' after Delay;
    elsif num_1 = 0 then
      output <= '0' after Delay;
    end if;
  end process;
end simple;

Essentially, it counts the number of 1’s, and checks for the set and clear conditions.

Testing

I made a test script to help make sure the generics work correctly (and get practice for testing later modules). Part of a test for TH22 is below:

See scripts/tests/test_threshold_gate.tcl on GitHub for my tests.

I have tested it for up to TH77, beyond that it takes too long to run (runtime is 2ⁿ). My test file is designed to test every possible transition of input values, in both the output set and clear states.

Thanks for reading. If you have any thoughts on how to improve the design, let me know by message or in the comments.

Commit: 5b852e5