To design a circuit, and to do anything useful with it, we need a way to describe it. The description can take two forms. A specification is a clear statement of what the system is intended to do, while an implementation shows how the primitive components can be connected together into a circuit that satisfies the specification. The specification of an adder says that the output is the sum of the inputs; the implementation of an adder says that a specific collection of logic gates connected by wires in a specific way will output the specified result. An implementation of hardware is a circuit design. Both the specification and implementation need to be clear, complete, and precise.

An implementation (i.e. a circuit design) may take the form of a diagram or a piece of text. For digital circuits, a pictorial specification is called a schematic diagram, while a textual specification uses a hardware description language. Both forms can also be used for software: a textual specification of a software algorithm uses a programming language, but there are also visual programming languages that use diagrams to describe software algorithms.

A schematic diagram is an abstract picture of a circuit. It shows the components and how they are connected with wires, but it doesn't directly describe the circuit's function. A schematic diagram implies some geometric information, such as the relative placement of components, and this geometry may be used in fabricating the circuit.

An alternative approach is to use a computer hardware description language (CHDL or HDL). A circuit specification using an HDL is a text document, so it looks superficially like a computer program, but it describes hardware rather than software. Most hardware description languages are based on existing programming languages intended for software, and they model circuits using the paradigms of programming.

An algorithm can be realised using either software, hardware, or a combination of both. Algorithms may be specified abstractly, without referring to either hardware or software. A common misconception is to think "if it's a picture, then it must be hardware; if it's text it must be software". That's doubly wrong: visual programming languages use pictures to describe software, and hardware description languages like Hydra use text to describe hardware.

Schematic diagrams and hardware description languages each have their merits. A diagram may be easier for a beginner to understand, and it's more obvious that a schematic diagram describes hardware and isn't just a computer program. However, schematics for large and complex circuits are cumbersome, while hardware description languages scale up well. Diagrams just sit there inertly on paper, and don't do anything, but CHDLs support useful software tools for simulation, fabrication, and testing.

Some HDLs are based on imperative programming languages, using the assignment statement to model a state change in a circuit. In contrast, Hydra is based on pure functional programming, and it models a circuit as a function that takes inputs and produces outputs. This is natural, because both a circuit and a function act as a black box that takes some inputs and produces some outputs. The underlying model – circuits as functions rather than state changes as assignments – is the fundamental difference between Hydra and imperative HDLs.

Hydra is an example of an embedded domain-specific language (DSL or EDSL). A domain-specific language is a language intended for one specific application domain, not for general purpose programming. Hydra is suitable specifically for expressing algorithms as digital circuits, but it isn't a general purpose programming language. It is implemented by embedding in Haskell, a general purpose functional language. This means that Hydra doesn't have a separate compiler; instead, its implementation consists of a library of Haskell modules. A circuit specification written in Hydra is compiled by the Haskell compiler and linked with the Hydra library. However, it is best to think of Hydra as a distinct language: designing a circuit is not the same as writing a program in Haskell, and some Haskell programs don't correspond to circuits.

The following sections explain the language and show how to write circuit specifications. A collection of examples can be found in hydra/examples. If you would like to see a simple circuit before going on, look at examples/simple/SimpleCirc.hs. To simulate it, enter these commands:

cd examples/simple
ghc -e main SimpleCircRun

Hydra is a functional computer hardware description language for specifying the structure and behavior of digital circuits. It supports several levels of abstraction, including logic gates, register transfer level, datapath and control, and processors. There are tools for simulating circuits, generating netlists, and emulating instruction set architectures. It is an embedded domain specific language implemented using Haskell.

• The User Guide is available online at https://jtod.github.io/home/Hydra/UserGuide/HydraUserGuide.html. The Guide is in development, and this online link may give a newer version than the one in the installation directory.
• The User Guide is also available in the installation directory HydraUserGuide.html
• The API reference gives types of the exported definitions. If you build using cabal, it will be in the the dist-newstyle directory. The path depends on software versions, but may be something like this: ../../dist-newstyle/build/x86_64-windows/ghc-9.2.3/hydra-3.4.16/doc/html/hydra/index.html. If you install using cabal, it should also be placed in the standard location for Haskell API references.

This is free and open source software released under the GPL-3 license.

• Author: John T. O'Donnell, School of Computing Science, University of Glasgow
• Copyright (c) 2022 John T. O'Donnell
• Author's home page: https://jtod.github.io/index.html
• License: This software is free and open source, released under the GPL-3 license. See LICENSE.txt.
• Source code repository: https://github.com/jtod/Hydra
• Version: see Hydra.cabal

Hydra runs in a shell using a command line interface. Any shell can be used; the examples use the bash shell.

To design a new circuit, you need to take a set of existing circuits and connect them with signals. The simplest circuits are primitive components. Every circuit is either a primitive component, or a number of circuits connected by wires.

There are two kinds of primitive: combinational components (called logic gates) and sequential components (called latches or flip flops). Here are a few of the most commonly used logic gates:

• The simplest logic gate is the inverter, which takes one input and produces one output. The inverter outputs 0 if its input is 1, and outputs 1 if its input is 0. The name of the inverter is inv.
• The and2 gate takes two inputs and outputs 1 if both inputs are 1; otherwise it outputs 0.
• The or2 gate takes two inputs and outputs 1 if either (or both) input is 1; it outputs 0 if all inputs are 0.

Suppose we have two signals named x and y, and want to connect them to the inputs of an or2 gate. This is done by writing the name of the component, followed by the names of the input signals:

or2 x y

The value of this expression is the signal which is the output of the or2 gate. Such an expression is called an application because the component is applied to its input signals.

Each circuit takes a specific number of inputs, and an application using that circuit must supply the corresponding number of input signals. Here are several applications of logic gates, each with the right number of inputs:

inv x
and2 a one
xor3 p q r
nor4 a zero c d

A signal may be given a name, such as x or y, although this is optional. You can also refer to a signal using an application of a component to its inputs, such as inv x; the output of the inverter is an anonymous signal as it has no name.

An anonymous signal is described by an expression, and that expression is written with several tokens. When you use it as an input to a circuit, this expression must be enclosed by parentheses, to turn it into a single entity. For example, suppose we have an inverter whose input is x, and we want to connect the inverter's output to the first input of an and2 gate. The second input to the and2 gate should be y. Here is the correct way to write it:

and2 (inv x) y

There are two expressions following and2, denoting its two inputs. The first expression is (inv x) and it denotes an anonymous signal (the output of the inverter). The second expression is y, which of course is a named signal. The following notation would be wrong:

and2 inv x y   -- Wrong!

This wrong expression says that the and2 gate is being given three inputs, and the first input (inv) isn't even a signal.

Parentheses are used for grouping, just as in mathematics. You don't need to use parentheses just to specify the arguments to a function (that is, the inputs to a circuit). Some programming languages requires lots of punctuation to indicate function application, but Hydra doesn't do that:

inv (x)                     -- Wrong!
and2 (a,b)                  -- Wrong!
nand3 (x, and2 (p,q), z);   -- Wrong!

In Hydra (as in Haskell) you don't need the extra parentheses and commas, and they will lead to error messages. Use parentheses only when they are necessary to get the right grouping. Here is the correct notation:

inv x
and2 a b
nand3 x (and2 p q) z

The following table lists all of the standard logic gates. Each gate is shown applied to input signals named a, b, etc.

The buffer produces an output that is the same as the input; it is the identify function.

Many of the logical operations can be performed on any number of inputs. For example, there is the logical conjunction (and) of two, three, or four inputs. These correspond to distinct logic gates: the and2 gate has two input ports and there is no way to connect three inputs to it. Therefore Hydra doesn't have an and gate; it has distinct and2, and3, and4 gates. This doesn't go on indefinitely; Hydra does not define the and5 gate or and73.

If you want to and together a lot of signals, use andw. For example, andw [a, b, c, d, e, f, g] = acts like =and7 would if it existed. The square bracket notation describes a word, covered in a later section.

Most of these logic gates are provided for convenience; only a few of them are necessary. For example, you can replace and3 a b c by and2 a (and2 b c). However, logic gates with several inputs can be fabricated on chips, they are slightly more efficient, and most importantly, it's more readable to use and3 rather than two and2 gates.

Hydra normally uses just one kind of flip flop: the delay flip flop, named dff. It is sometimes called a latch. This takes one input and produces one output: for example, the value of dff x is the output signal produced by a delay flip flop with input x. All flip flops must be connected to the same clock; we do not consider the clock to be a data input to the flip flop.

It can be helpful to give both a schematic diagram and a textual specification for a circuit. Each form of description provides insight, and having both together is often worthwhile.

It's important to check that the two descriptions of the circuit are consistent with each other. To do this,

• Check that every box in the diagram corresponds to a circuit (function) in the text, and check that every circuit in the text corresponds to a box in the diagram.
• Check that each wire in the diagram corresponds to a signal in the text.
• The wire should be connected to exactly one component output, which places a logic value on the wire. The wire may be connected to one or more component inputs.

Sometimes it's useful to give a name to a signal, rather than using it anonymously. A named signal can be used as an input to several different components, but an anonymous signal cannot. Names can also make it easier to explain the circuit, and well chosen names help document the purpose of a signal.

A signal can be named using an equation. The left hand side of the equation is the name, and the right hand side is an expression that defines the signal. The following equation says that the output of the and3 gate has the name x.

x = and3 a (inv b) c

With that equation, x can be used as the input to any component:

x = and3 a (inv b) c
y = or2 a x

A defining equation defines the name on the left hand side to have the same value as the signal expression on the right hand side. The order of equations is immaterial, just as with equations in mathematics. It's fine to use a signal name before the equation that defines it. The example above could be written like this, and it would specify exactly the same circuit:

y = or2 a x
x = and3 a (inv b) c

However, in mathematics you can swap the left and right hand sides, but a Hydra defining equation must have the name on the left side and its value on the right side. It's called a defining equation because it defines the name on the left hand side to have the value of the right hand side. If you reverse the two sides, you'll get an error:

a = inv b      -- Correct, defines the name a
inv c = d      -- Error, need a name (not application) on left

Later we will see a technique called equational reasoning, which is useful for analysing circuits. This uses equations with a more general form. Both of the two lines in the example above are valid equations, but only the first is a valid defining equation. To give a name to a signal, you need to use a defining equation, where the left hand side is always a signal name.

It's a good idea to write the equations in an order that makes the circuit more readable. If most of the signals are defined before they are used, a person reading the text will get a bottom-up understanding. Using signals before they are defined gives a top-down presentation. Both styles are useful, and we will see examples of both.

Sometimes the choice between anonymous and named signals is just a matter of style. Here is a signal defined using three anonymous signals:

x = nand2 (xor2 a b) (inv (nor2 c d))

This can be rewritten so as to give every signal an explicit name, by introducing additional equations:

x = nand2 p q
p = xor2 a b
q = inv r
r = nor2 c d

Both styles are correct. Use whichever you find more readable.

A constant signal always carries the same value: either it is always 0, or always 1. The names of these two constant signals are written as zero and one. Names in Hydra always begin with a lower case letter, never with a digit. Don't use 0/1, or T/F, or True/False in a circuit specification; those notations have other meanings and will lead to bizarre error messages.

x = and2 a one   -- Correct, x is same as a
y = and2 a 1     -- Error, 1 isn't a signal

A logic gate is a primitive combinational component (combinational means that the output depends on the current values of the inputs).

There are several libraries of existing circuits that you can use, and you can also define libraries of your own circuits for further use. The Hydra libraries provide as primitives the standard logic gates, summarised in the following table.

The buffer produces an output that is the same as the input; it is the identify function.

Most of these logic gates are provided for convenience; only a few of them are necessary. For example, you can replace and3 a b c by and2 a (and2 b c). However, logic gates with several inputs can be fabricated on chips, they are slightly more efficient, and most importantly, it's more readable to use and3 rather than two and2 gates.

An equation that defines a circuit called circuit_name has this general form:

circuit_name input1 ... inputn = output

The left hand side of the equation is an application of the circuit's name to the names of the input signals, for example input1, etc. There can be any number of inputs. The right hand side is the value of the circuit's output.

As a simple example: mycirc takes two inputs. It outputs 1 iff the first input is 1 and the second is 0:

mycirc a b = and2 a (inv b)

As another example, suppose we want to define a new circuit called and5 that takes five inputs and outputs 1 if and only iff all the inputs are 1. It is a 5-input and gate, but and5 is not one of the standard primitives. This will do it:

and5 a b c d e = and2 (and3 a b c) (and2 d e)

Given this definition, you can use and5 by applying it to some input signals, for example and5 x y p q r.

The input names in the circuit defining equation are local. They are in scope only within the definition of the circuit, including the right hand side of the circuit defining equation.

The expression that defines the circuit's output can become fairly complicated, and it's often simpler to define it using several other named signals which are inside the black box. Each of these needs a defining equation. To do this, write the keyword where after the circuit defining equation, and after the where you can write any number of signal defining equations. The general form is:

circuit_name input1 ... inputn = output_expression
  where x = ...
        y = ...
        ...

The definition of and5 above had a fairly large output expression. This can be simplified by defining some internal signals and5:

and5 a b c d e = and2 p q
  where p = and3 a b c
        q = and2 d e

This definition describes exactly the same circuit as the previous version of and5; the only difference is that local names p and q are given to the outputs of the internal and3 and and2 gates. These names are just part of the description of the circuit; both versions of and5 have exactly the same components and wires.

Here is an example of a circuit named c22 that takes three inputs and produces one output.

c22 a b c = x
  where
    x = xor2 p q
    p = and2 a b
    q = or2 b c

The equations should be indented consistently, and there is no extra punctuation (no curly braces, no semicolons). The compiler determines the structure of a definition from the indentation, not from punctuation. Therefore

The indentation is mandatory: it determines which equations are inside the black box. Note that you don't need curly braces around the internal equations, and don't need semicolons at the end of each line. The essential rules to remember are that

• Each internal equation must be indented relative to the circuit defining equation
• All the internal equations must start in the same column

The indentation is essential, and if it's wrong then the specification will be parsed incorrectly. There are several indentation styles, which differ in the placement of the where keyword and what column the internal equations start in. Each of the following examples is ok; use whichever you prefer.

c22 a b c = x
  where
    x = xor2 p q
    p = and2 a b
    q = or2 b c

c22 a b c = x
  where x = xor2 p q
        p = and2 a b
        q = or2 b c

c22 a b c = x where
  x = xor2 p q
  p = and2 a b
  q = or2 b c

A register is a circuit with an internal state, and with the ability to load an external value into the state and to read out the state.

module Reg1 where
import HDL.Hydra.Core.Lib
import HDL.Hydra.Circuits.Combinational

reg1 :: CBit a => a -> a -> a
reg1 ld x = r
  where r = dff (mux1 ld r x)

The reg1 circuit has a feedback loop: the output of the flip flop is connected to one of the inputs to the mux1, whose output in turn is input to the flip flop. Hydra does not allow feedback loops in pure combinational logic, but feedback that goes through a flip flop is fine. When a circuit contains a feedback loop, there will be a circular path in the schematic diagram, and there will be circular equations in its specification. For the reg1 circuit. the feedback loop can be seen in the equation which has r on both the left and right hand side. Thus r is being defined in terms of itself. The way this works, and the reason that r is well-defined, is explained in the section on circuit semantics.

-- Simulation driver for reg1
module Main where
import HDL.Hydra.Core.Lib
import Reg1

main :: IO ()
main = do
  runReg1 testdata

testdata :: [[Int]]
testdata =
------------------------
--  ld  x       output
------------------------
  [ [1, 1],  -- 0  output in cycle 0 is initial state
    [0, 0],  -- 1  state changed to 1 at tick between cycles 0/1
    [0, 1],  -- 1  no change
    [0, 0],  -- 1  no change
    [1, 0],  -- 1  still see 1 but at end of cycle, set state to 0
    [0, 0],  -- 0 during this cycle can see result of state change
    [1, 1],  -- 0 but set state to 1 on tick at end of cycle
    [1, 0],  -- 1 the 1 becomes visible in this cycle
    [0, 0],  -- 0 the 0 now becomes visible
    [0, 0],  -- 0 no change
    [0, 0]   -- no comma after last element of list
  ]

runReg1 input = runAllInput input output
  where
-- Input signals
    ld = getbit input 0
    x  = getbit input 1
-- Circuit
    y = reg1 ld x
-- Format the input and output signals
    output =
      [string "Input ld = ", bit ld,
       string " x = ", bit x,
       string "   Output = ", bit y]

The circuits we have looked at so far have just one output. We need a way to allow circuits to produce any number of outputs.

Files: examples/adder/HalfAdd.hs and examples/adder/HalfAddRun.hs

A half adder circuit takes two inputs x and y, and produces a pair of outputs, the carry output and the sum output. The carry is the logical and of x and y, while the sum is their exclusive or. The circuit specification is in the file HalfAdd.hs.

The module statement gives a name to this module, and the import statement brings in the essential Hydra library definitions. The circuit definition is a one-line equation which says halfAdd is a circuit, gives names x and y to its inputs, and calculates the outputs using and2 and xor2 logic gates.

To see the circuit working, we can simulate it. This requires three things, all provided in HalfAddRun.hs:

• Suitable test data, expressed as a list of [x,y] inputs
• A [Simulation driver](#simulation-drivers), which converts between human readable input and output and the internal signal representations. The simulation driver is not part of the circuit; it's simply formatting inputs and outputs.
• A main program that runs the simulation driver on the test data.

See `examples/adder/HalfAddRun.hs'

Run the simulation using any of the methods given above, e.g. enter ghc -e main HalfAddRun. Here is the result:

$ ghc -e main HalfAddRun
Input: x = 0 y = 0  Output: c = 0 s = 0
Input: x = 0 y = 1  Output: c = 0 s = 1
Input: x = 1 y = 0  Output: c = 0 s = 1
Input: x = 1 y = 1  Output: c = 1 s = 0

The multiplexer is an example of a circuit that can be defined by conecting several logic gates together. The multiplexer is one of the most important building blocks for larger systems. There are many varieties of multiplexer; here we look at the 1-bit multiplexer, called mux1.

Files:

• examples/mux/Mux1.hs
• examples/mux/Mux1Run.hs

A multiplexer is a hardware version of the if-then-else expression, and is used to perform conditional actions in a circuit. It takes three inputs: a control input c, and two data inputs x and y.

The idea is that the multiplexer will choose one of the data inputs – either x or y – and output it. The data input that is not chosen is simply ignored. The choice is determined by the value of c.

The behavior of the multiplexer can be described informally using an if–then–else expression. This is just an English description, not a circuit, because if is not a circuit: it's programming language notation.

-- informal specification
mux1 c x y = if c = zero then x else y

The multiplexer can be implemented with logic gates. The circuit is defined in the file Mux1.hs, and a simulation driver is in Mux1Run.hs. A simulation driver is a software interface to the actual circuit; the software takes inputs in a readable notation, formats the outputs, and controls the simulation.

Files:

• examples/mux/Mux1.hs
• examples/mux/Mux1Run.hs

To run the simulation, enter

cd examples/mux
ghc -e main Mux1Run

Given inputs c, x, y, the circuit outputs a bit whose value is

or2 (and2 (inv c) x) (and2 c y)

There are several ways to understand how this Boolean logic implements the if-then-else construct. One way is simply to build a truth table showing the output for each possible input.

This expression can be read by working through each subexpression:

• inv c says there is an inverter, and its input is connected to c. The subexpression inv c denotes the output signal produced by the inverter.
• and2 (inv c) a denotes the output of an and2 gate; its first input is the output of the inverter and its second input is a. This signal is the first input to the or2 gate.
• and2 c y is the output of an and2 gate with inputs c and y; the output of the gate is the second input to the or2 gate.

The file examples/mux/Mux1.hs defines the circuit as follows.

mux1 c x y = or2 (and2 (inv c) x) (and2 c y)

Circuit definitions are discussed in more detail later, as well as the rest of the file:

module Mux1 where
import HDL.Hydra.Core.Lib

-- mux1 is defined in the Hydra circuit libraries, so here
-- the circuit is called mymux1 to ensure that we're testing
-- this definition

mymux1 :: Bit a => a -> a -> a -> a
mymux1 c x y = or2 (and2 (inv c) x) (and2 c y)

module Main where
-- Mux1Run: test the mux1 circuit

import HDL.Hydra.Core.Lib
import Mux1

main :: IO ()
main = mux1Run testdata

testdata :: [[Int]]
testdata =
-----------------------------------------
--   c  x  y       expected result
-----------------------------------------
  [ [0, 0, 0]  --  0  (c=0 so output=x)
  , [0, 0, 1]  --  0  (c=0 so output=x)
  , [0, 1, 0]  --  1  (c=0 so output=x)
  , [0, 1, 1]  --  1  (c=0 so output=x)
  , [1, 0, 0]  --  0  (c=1 so output=y)
  , [1, 0, 1]  --  1  (c=1 so output=y)
  , [1, 1, 0]  --  0  (c=1 so output=y)
  , [1, 1, 1]  --  1  (c=1 so output=y)
  ]

mux1Run input = runAllInput input output
  where
-- Extract input signals  
    c = getbit input 0
    x = getbit input 1
    y = getbit input 2
-- The circuit to be simulated
    z = mymux1 c x y
-- Format the output
    output =
      [string "  c=", bit c,
       string "  x=", bit x,
       string "  y=", bit y,
       string "    output z=", bit z
      ]

We can run it with a simulation driver that runs the circuit on all possible inputs, so the outputs form a truth table. It's good practice to write the test data with clean indentation, so the inputs line up in columns, and to include the expected outputs in comments.

See examples/mux/Mux1Run.hs')

The circuit is defined in a module SimpleCirc, which is in the file named SimpleCirc.hs.

-- SimpleCirc: minimal example of a circuit specification
-- This file is part of Hydra. See README and https://github.com/jtod/Hydra
-- Copyright (c) 2022 John T. O'Donnell

module SimpleCirc where
import HDL.Hydra.Core.Lib

-- Define a circuit "simpleCirc" which takes two input bits and
-- outputs their logical conjunction, using an and2 logic gate.

-- To run the circuit simulation, see SimpleCircRun and
-- SimpleCircRunInteractive.

simpleCirc :: Bit a => a -> a -> a   -- interface: two inputs, one output
simpleCirc x y = and2 x y            -- circuit is just an and2 logic gate

A module begins with a module statement that gives its , followed by statements that import other modules. All Hydra modules must contain import HDL.Hydra.Core.Lib, which defines, among other things, the and2 logic gate.

Following the imports, the module may contain any number of circuit definitions. The definition of the circuit simpleCirc contains two lines of code: a type declaration which contains the symbol :: and a defining equation which contains the symbol =.

A type declaration specifies the name of the circuit and its interface. The declaration simpleCirc :: Bit a => a -> a -> a contains several parts:

• The beginning means "simpleCirc has type…".
• Bit a means the circuit uses Bit signals, and we will use the name a for the type of a bit signal
• a -> a -> a says the circuit takes an input of type a, a second input also of type a, and it outputs a signal of type a
• There may be any number of inputs, and each is followed by ->. This means that the number of inputs is the number of -> in the type.
• There must be exactly one output. The last a in the type is the type of the output. Later, we will see how to allow a circuit to produce several outputs.

The defining equation specifies local names for the circuit's inputs, and it gives a circuit that produces its output. The defining equation for this circuit is simpleCirc x y = and2 x y. This says

• We will use the names x and y as local names for the inputs to the circuit
• There is an and2 logic gate with inputs x and y
• The output of that logic gate is the output of the circuit

To test the circuit, we can simulate it with some inputs. This requires a simulation driver which is defined in a separate module in the file SimpleCircRun.hs. The simulation driver defines the interface to the circuit and specifies how to format the inputs and outputs, so you don't have to read and write thousands of 0s and 1s.

The file begins by defining the module and importing some required libraries. Every Hydra file needs to import HDL.Hydra.Core.Lib. In addition, a simulation driver like SimpleCircRun needs to import the circuit file, which should be in the same directory.

-- SimpleCircRun:  simulation driver for SimpleCirc
-- This file is part of Hydra. See README and https://github.com/jtod/Hydra
-- Copyright (c) 2022 John T. O'Donnell

-- Usage:  $ ghc -e main SimpleCircRun

module Main where
import HDL.Hydra.Core.Lib
import SimpleCirc

A simulation driver can define input data, although this is not required. The data is given as a list of strings. Each string corresponds to one clock cycle, and it gives the values of the inputs during that cycle.

testdata1 :: [String]
testdata1=
------------------------------
--   x   y     expected output
------------------------------
  [ "0  0"   --  0
  , "0  1"   --  0
  , "1  0"   --  0
  , "1  1"   --  1
  ]

The file defines a function main that will run the simulation. These two lines are boiler plate and every driver should contain them:

main :: IO ()
main = driver $ do
-- Input data
  useData testdata1

-- Inputs
  x <- inputBit "x"
  y <- inputBit "y"

-- Circuit
  let z = simpleCirc x y

-- Output ports
  outputBit "z" z

-- Run
  runSimulation

If you want the simulation to use any test data (e.g. testdata1), the useData statement specifies which test data to use. This command is optional; if you don't include it (or if you comment it out) the simulation will be interactive, and prompt you for the input values every clock cycle. But if the useData statement is present, the simulation will run to completion without any intervention by the user.

useData testdata1

Every driver is required to define an input port for every circuit input. The convention is that in input signal named x has an input prt named in_x. Each input port is created with a statement of the form portname <- inPortBit "signame". If the inport is a word, rather than a bit, you would definit like this: in_w <- inPortWord "w" 8 where 8 is the word size.

There must be an input signal for each port. These are defined using inbsig for bits, and inwsig for words.

What is the difference between a port and a signal? A signal is a wire, and it can be connected directly to a circuit. A port is a data structure that contains the signal and also some addiitonal metadata required by the simulator.

Notice that ports are defined using <- and signals are defined with the let keyword and =.

The next piece of the driver is an equation that connects the input and output signals to the circuit. This equation is given in a let statement

The simulator will print out the values of all the signals for each clock cycle. You can either have the system do this automatically, or you can supply a detailed format that gives precise control over the output.

The easiest approach is to ask for automatic output of all the signals. To do this, you need to define an output port for each output signal. This uses the outPortBit function, which takes the name of the signal "z" and the corresponding signal z.

The final piece of the driver is the command runSimulation. If you omit this, the simulation won't run and there won't be any output.

runSimulation

Alternatively, you can use the format statement which gives precise control over the formatting of the simulation output. The format is a list of field specifiers. The field specifier string "…" says that the literal string "…" should appear in the output. The field specifier bit x says that x is a signal; its value should be printed in the output (it will be either 0 or 1).

-- Formatted output
  format [string "x=", bit x,
          string "  y=", bit y,
          string "   output = ", bit z,
          string "\n"
         ]

There are several format specifiers, that allow output of words using bit strings, decimal, hexadecimal, and both binary and two's complement. See examples/SimDriver for examples of these specifiers.

To run a circuit you should cd to the directory that contains the circuit (Circuit.hs) and its simulation driver (CircuitRun.hs) files.

One way to run the simulation is to use the ghc command, which will run the main program in CircuitRun as a single command:

ghc -e main CircuitRun

An alternative is to use the ghci command, which launches the interactive version of ghc. This offers many useful debugging tools, but you need to give it several commands to run the simulation:

ghci
:load CircuitRun
:main

You can run a circuit simulation in batch mode, which will run to completion with no intervention by the user. Alternatively, you can run it interactively. The choice between the modes is determined by just one line of code: the presence or absence of a useData statement.

If you run a simulation in interactive mode, the system will prompt "hydra>" and wait for you to enter a command. When it does so, just press Enter, which is the command to simulate one clock cycle. It will then prompt you for the value of each signal; enter a decimal number. When all the inputs have been provided, the driver will now print out all the signal values and prompt for a command again. The help command will print a list of the available commands.

You can try out both approaches with the SimpleCircRun driver. It contains a useData, so it will run in batch mode. But if you comment out the useData, the driver will revert to interactive mode.

Files: adder/Add4.hs and examples/Add4Run.hs

*Main> :main
  x =  5  y =  8  cin = 0    ==>    cout = 0  s = 13
  x =  7  y =  3  cin = 0    ==>    cout = 0  s = 10
  x =  8  y = 12  cin = 0    ==>    cout = 1  s =  4
  x =  8  y =  1  cin = 0    ==>    cout = 0  s =  9
  x = 12  y =  1  cin = 1    ==>    cout = 0  s = 14
  x =  2  y =  3  cin = 1    ==>    cout = 0  s =  6
  x = 15  y = 15  cin = 1    ==>    cout = 1  s = 15
(0.00 secs, 252,808 bytes)
*Main>

This part of a definition is optional; if present it follows the where keyword.

There are two ways to indicate a comment

• Enclose the comment in brackets {- so this is a comment -}
• A double dash – indicates that everything else – on the line is a comment

Names (also called identifiers) are used for circuits (e.g. logic gates) and signals. A name must begin with a lower case letter, and may contain letters, digits, underscores, and primes (single quote). The following are valid names:

x
select
adder
y'
bypass_ctl

Product    -- begins with upper case letter
x?3        -- contains invalid character ?
0          -- use zero to get the constant 0 signal

The following identifiers cannot be used to name a circuit or signal:

A signal is specified in Hydra by an expression. The simplest form of expression is simply the name of a signal. For example, suppose we have signals named x and y. Then the following expressions denote the corresponding signals. Note that zero and one are simply the names of the constant signals.

zero
one
x
y

A signal is denoted by an expression, which can have any of the following forms:

• The constants zero and one are names that are pre-defined. These should not be redefined: don't write zero or one on the left hand side of an equation.
• The name of a signal which is in scope: x, carry, ctl_ld. Later we will see how to define these, using equations or circuit inputs.
• An application of a circuit to inputs denotes a signal: or2 x y specifies a signal which is the output of an or2 gate connected to inputs x and y.

Any of these notations can be used as input to a component.

The component and the inputs are separated by a space; don't use punctuation.

c = and2 a b          -- correct
d = and2 (a,b);       -- wrong! don't use ( , ) ;

Haskell normally uses indentation, rather than punctuation, to determine the structure of a definition. There are good reasons behind this approach to syntax.

It is also possible to use braces and semicolons to determine the structure, instead of indentation. This is particularly useful for generators, where the specification is not written by hand and also not intended to be human readable. There are also some situations where a large number of very short equations can be more readable with many placed on each line, separated by punctuation. However, these situations are relatively uncommon. Normally it's best to use indentation and to make the layout of the code as readable as possible.

The equations in a definition need to be lined up vertically

circ x y = a   -- a good definition
  where
    p = bla bla...
    q = bla...
    r = bla...

circ x y = a  -- a bad definition
  where
    p = bla bla...
   q = bla...
    r = bla...

The interface gives the name of the circuit and names its inputs and outputs. A circuit is created with a circuit defining equation. The left hand side of the equation is the name of the circuit followed by the names of the input signals. There may be any number of inputs. The right hand side is an expression giving the value of the output signal:

circ_name input1 input2 = expression

This defines a circuit whose name is circ_name, which takes two inputs named input1 and input2, and produces an output with the specified signal value. Here is an example:

mycirc a b c = and3 a (inv b) c

The input names a, b, and c, are local to the definition of mycirc, and they can be used to calculate the value of the output. Another circuit can connect signals with arbitrary names, or no names at all, to the inputs of mycirc.

The \emph{type} of a circuit describes its interface; in particular

• how a signal is represented: this determines the choice of semantic model;
• how many inputs it takes, how they are structured;
• how many outputs it produces, and how they are structured;
• the size parameters, if any;
• the building block circuits, if any.

If you try to plug the wrong number of signals into a circuit, you will get a type error message.

Short version. If you're writing a routine circuit and just want to simulate it, you can just write CBit a => for the signal class constraint and then use a as the type for every bit signal. In more complicated situations, or if you want to know what this means, read on.

When a circuit specification is executed, each signal has a specific type. Many types can be used, for example Bool or Stream Lattice. The choice of type determines what happens during execution. Some types lead to combinational simulation, others lead to synchronous simulation, others perform a path depth analysis, or generate a netlist.

It's possible to define a circuit with a specific type, and if you do this the class constraint (the part before =>) is omitted. For example, we could define a Bool version of the mux1 circuit (call it halfAddB) to operate in signals of type Bool:

halfAddB :: Bool -> Bool -> (Bool,Bool)
halfAddB x y = (and2 x y, xor2 x y)

This is a little simpler than the standard definition halfAdd, which (1) uses the type class constraint Bit a =>, and (2) uses a rather than Bool as the bit signal type.

After the signal class (i.e. after the => symbol) come the types of the inputs and output of the circuit. In the simplest case, each input or output signal is just a bit of type a. There may be any number of input arguments, and there must be one output result. A single arrow -> must follow each input; thus the number of single arrows in the type is the same as the number of inputs.

The inverter has one input of type a, which is followed by ->, and the type a of the output appears last. The type declaration can be read as "inv uses signals in the Bit class; it takes one input and produces one output": Thus the entire type declaration ``*inv :: Bit a => a -> a*'' says ``*inv* is a circuit that takes an input bit signal, and produces an output bit signal.''

inv :: Bit a => a -> a

The notation a -> a means "the circuit takes an input signal and produces an output signal". This is similar to conventional mathematical notation; for example in mathematics there is a function im that is given a complex number (type \(C\)) and returns its imaginary part (type \(R\)), and a mathematician might write its type as im : C -> R. (The reason :: is used in Haskell (and Hydra) is that : is used for something else.)

Circuits that take several inputs have a slightly more complicated type. For example, here are the types for the family of and-gates:

and2 :: Bit a => a -> a -> a
and3 :: Bit a => a -> a -> a -> a
and4 :: Bit a => a -> a -> a -> a -> a

There is always one output, but any number of inputs, and every input is followed by ->. To find out how many inputs a circuit takes, just count the number of times -> appears in its type.

If a circuit has several outputs, they must be enclosed in a container, and this is reflected in the type. See the section on Containers.

The circuit type is covered in a later section. It's optional, although it is generally best to include it. If present, the type can be recognized by the :: symbol and a number of right arrow symbols; a typical example is

halfAdd :: Bit a => a -> a -> (a,a)

circname :: signalClass => inType -> inType -> outType

• circname is the name of the circuit; starts with lower case letter
• signalClass gives information about the signal. We will normally use either {\color{red}Bit a} or {\color{red}CBit a}, but there are many other options we won't be using
• input and output types: {\color{red}a} for a bit signal, {\color{red}[a]} or {\color{red}(a,a)} for a container holding several bits

• You can omit the type declaration; the compiler will work it out automatically
• There are some advantages for declaring the type:
  • It provides helpful documentation
  • It enables the compiler to give better error messages, if there is an error in a circuit
  • A useful design technique is to specify first the types of your circuits and to go back later to implement them

• There is a close relationship between \emph{how a signal is represented} and \emph{how the circuit is evaluated}.
  • Example: if you use Bool, then you can do logic simulation but not synchronous simulation.
  • If you use streams, you can handle timing.
  • If you want to allow special techniques (tristate drivers, wired or) you need a multiple-value logic.
• For this reason, it's not a good idea to give circuit types like \texttt{inv :: Bool -> Bool}.
• Instead, we use a \emph{type variable}, typically \texttt{a}, to represent the signal type.

When you write \texttt{inv

Bit a => a -> a}, the \texttt{Bit a =>} part means ``for an arbitrary type \texttt{a}, provided that \texttt{a} is in the set of types that can represent a bit signal''.

Similarly, \texttt{reg1

CBit a => a -> a -> a}, the constraint \texttt{CBit a =>} means the signal type \texttt{a} has to be capable of representing clocked synchronous bit signals.

(no term)

Hydra offers many signal representations.

(no term)

Normally, the choice of specific signal type will be made by the simulation driver.

• By convention, the type of a bit signal is called \texttt{a}.
• The scope of the type variable \texttt{a} is the type statement.
• This means you can have a signal named \texttt{a} in the circuit definition, without confusion.

circ1 :: Bit a => a -> a -> a
circ1 a b = and2 a (inv b)

In the first line, \texttt{a} is the signal type, but in the second line \texttt{a} is the name of the first input signal.

• For a combinational circuit, use {\color{red}|Bit a =>|} and the type of a bit signal is {\color{red}|a|}
• For a clocked synchronous circuit, use {\color{red}|CBit a =>|} and the type of a bit signal is {\color{red}|a|}

There are many other options for the signal classes, but we won't use them in CA4.

• A bit signal is indicated by the signal type \texttt{a}.
• Each input signal group is followed by an arrow \texttt{->}. This means that the number of arrows in the type is the number of inputs.
• The output signal group follows the last arrow.

  \texttt{and2

  Bit a => a -> a -> a} has two arrows \texttt{->}, so there are two input groups, both with type \texttt{a}. The output has type \texttt{a}.

  \texttt{mux2

  Bit a => (a,a) -> a -> a -> a -> a -> a} has five input groups: a bit pair (used for control), four bits (for data), and there is one output bit.

You construct a tuple simply by writing its components in parentheses:

code = (x,y,z)

Given a tuple, you can supply names for its components with an equation. The tuple is a \emph{pattern} that defines the elements

(p,q,r) = code

• Hydra requires every circuit to have \emph{one} output.
• If there are several output signals, just group them in a tuple.

The half adder and demux1 circuits produce two outputs, which can be specified as expressions in a tuple.

halfAdd x y = (and2 x y, xor2 x y)
demux1 c x = (and2 (inv c) x, and2 c x)

In |demux2| it's necessary to define the output as a tuple of names which are defined by equations.

demux2 (c0,c1) x = (y0,y1,y2,y3)
  where  (p,q) = demux1 c0 x
         (y0,y1) = demux1 c1 p
         (y2,y3) = demux1 c1 q

• A word \([x_0, x_1, \ldots, x_{k-1}]\) is used to represent binary numbers.
• There are notations to allow you to build words and extract parts of words.
• Some circuits are defined recursively: the definition for a \(k+1\) bit word uses a subcircuit of size \(k\).
• Sometimes you need to extract a bit or a field from a word, or construct new words.
• Therefore we need operators to add a new bit to a word, extract a bit from a word, etc.

• You can have a tuple containing two words |:: ([a], [a])|
• Or a word of tuples |:: [(a,a,a)]|
• Or arbitrarily deeply nested containers |:: ([(a,a)], a, ([a],a), [a])|
• Bit a => a -> [(a,a)] -> (a,[a])| has two input groups: a singleton bit (the carry input) and a word of pairs (the numbers to add). The output contains a singleton (carry output) and a word (the sum).
  • The type {\color{red}|[(a,a)]|} is an important special case which is called {\color{blue}bit slice format}. The |rippleAdd4| type is an example of bit slice format.

In a physical circuit, every wire carries one bit, and doesn't have any relationship to any other wire (unless it is actually connected to that other wire). When we design a circuit, however, it takes several wires to carry any data value that isn't just a Boolean. For example, it takes 16 wires to transmit a 16-bit word, and to the designer there is definitely a clear relationship among these wires.

Circuits may contain large numbers of signals, and it would be tiresome to name them all. You can simplify the description of a circuit by defining containers that hold a collection of signals. Then you can use the container as a single object, without referring explicitly to its components.

A design is clearer if related signals together are grouped together, with a name for the entire collection. For example, we could give the name x to a 16-bit word, and just use x to refer to all the wires collectively.

Hydra provides two kinds of container: tuples and words. Tuples are useful for circuits that have multiple inputs and outputs; an example of a tuple is (x, (a,b)). Words are appropriate when several signals are used to represent a number, for example [x0,x1,x2,x3].

Both kinds of container are written with several elements separated by commas. A quick way to tell them apart is that tuples use round parentheses ( … ) but words use square brackets [ … ].

Containers are just notations that help to simplify the description of large circuits. If you look at the layout of a chip under a microscope, you won't see any tuples or words—just thousands of individual wires and components. A circuit specification that names each one explicitly would be long and unreadable; containers enable us to write compact and readable descriptions of such large circuits.

You can choose between automatic or manual formatting of the simulation results.

• If a format statement is present, the automatic output is disabled and the outport is produced entirely by the format. However, the system will indicate the clock cycles.
• If the format is omitted, then the system will generate output using the port definitions. In this case, outport definitions are required.

A simulation driver must either define the outports, or it must contain a format. If it contains both, the outports are ignored. So if you wish to provide a format there is no need to define the outports.

For small circuits, it may be easiest to define the outports and use the automatic output. For large circuits, you can make the results more compact and more readable by defining a format.

Files: BSR4.hs and BSR4Run.hs

A bidirectional shift register

Define a shift register that takes an operation code op and data inputs x, li, ri, and performs an a state change depending on op:

• op=0 – no state change
• op=1 – load input word x
• op=2 – shift right
• op=3 – shift left

The circuit uses a building block srb ("shift register block") which has an internal state to hold the bit in that position in the word. The inputs to an srb are an input from the left (for shifting to the right), an input from the right (for shifting to the left), and a bit input from the word x (for loading a word). The circuit outputs a triple: the left and right outputs, and the word giving the current state of the register. (Minor point: the left and right outputs aren't essential, as they also appear as the most and least significant bits of the word output, but this approach makes it easier to connect several sr4 circuits together, and it also fits well with the definition of the more general sr circuit below.)

The structure of the 4-bit version comes directly from the data dependencies.

The shift register block uses a dff to hold the state, and it uses a mux2 to determine the new value of the state. This is either the old value, the data bit x from a load, or the input from the left or right in case of a shift.

examples/shift/BSR4.hs examples/shift/BSR4Run.hs

The test data and simulation driver are defined in BSR4Run.hs. Running the circuit produces this:

$ ghc -e main BSR4Run
op=01 l=0 r=0 x=9   Output lo=0 ro=0 y=0
op=00 l=0 r=0 x=0   Output lo=1 ro=1 y=9
op=11 l=0 r=0 x=0   Output lo=1 ro=1 y=9
op=11 l=0 r=1 x=0   Output lo=0 ro=0 y=2
op=00 l=0 r=0 x=0   Output lo=0 ro=1 y=5
op=01 l=0 r=0 x=4   Output lo=0 ro=1 y=5
op=10 l=1 r=0 x=0   Output lo=0 ro=0 y=4
op=10 l=0 r=0 x=0   Output lo=1 ro=0 y=a
op=10 l=0 r=0 x=0   Output lo=0 ro=1 y=5
op=10 l=1 r=0 x=0   Output lo=0 ro=0 y=2
op=00 l=0 r=0 x=0   Output lo=1 ro=1 y=9

The solution is to identify the signals by name and to collect a group of named signals in a record. Here is a definition from the Datapath module, which provides a number of output signals that are collected into a record with type DPoutputs a:

data DPoutputs a = DPoutputs
     { aluOutputs :: ([a], [a])
     , r :: [a]        -- alu output
     , ccnew :: [a]     -- alu output
     , ma :: [a]
...
     }

The Datapath module defines the signals: it contains an equation for each element of the record giving the value.

...
aluOutputs = ...
r = ...
ccnew = ...
...

The record itself is named dp and is defined by this equation:

dp = DPoutputs {..}

The notation {..} means that each defined value whose name is listed in the record type (DPoutputs) should be included in the actual record (dp). For example, the record type DPoutputs a defines a field named ccnew and there is an equation defining the value ccnew, so ccnew is included in the record dp.

The definition of the datapath circuit is an equation where the right hand side says that the output is dp, which is defined to be the record of signals dp:

datapath (CtlSig {..}) (SysIO {..}) memdat = dp
  where

-- Interface
    dp = DPoutputs {..}

The first input to the datapath circuit is (CtlSig {..}), which is a record of signals output by the control circuit. When used as an input, this {..} notation means that every field in the CtlSig record defines the corresponding name. With this notation, you don't need to write a separate equation for every element of the CtlSig record.

The {..} notation makes it easy to add a new signal to a record. For example, suppose you modify the datapath to contain two new signals: pqr which is a bit, and xyz which is a word of bits. The following changes are required:

• Add equations defining the new signals to the Datapath module:

pqr = ...
xyz = ...

• Add the new signals to the record definition in the Interface module:

data DPoutputs a = DPoutputs
  { ...
  , pqr :: a
  , xyz :: [a]
  ...
}

• Now you can use pqr and xyz in any module that receives the DPoutputs.

Word inverter: |winv4| takes a word and inverts each of its bits

winv4 :: Bit a => [a] -> [a]
winv4 [a,b,c,d] = [inv a, inv b, inv c, inv d]

• You can use {\color{blue}|winv4 x|} if |x| is a 4-bit word, but not if it's an 8 or 16 bit word.
• The generic circuit {\color{blue}|winv|} works for any word size. It's defined using a {\color{red}circuit generator} called {\color{red}map}.

winv :: Bit a => [a] -> [a]
winv = map inv

• winv4 is a 4-bit word inverter
• winv generates an $n$-bit word inverter: it works for \emph{every word size}
• The circuit generator works by (1) measuring the size of the input word and (2) generating the required number of components
• {\color{red}This is not software to do the operation — it is still a real circuit.}

Take a word, and and/or all its bits together

andw4 [a,b,c,d] = and2 (and2 a b) (and2 c d)

For bigger words, it's better to use generic circuits andw, orw that are defined using the circuit generator {\color{red}foldl}:

andw, orw :: Bit a => [a] -> a
andw = foldl and2 one
orw = foldl or2 zero

The input is a word of bits, and the output is the and/or of all those bits. This is like an $n$-bit or gate with an $n$-bit input word.

rippleAdd4 :: Bit a => a -> [(a,a)] -> (a,[a])
rippleAdd4 cin [(x0,y0),(x1,y1),(x2,y2),(x3,y3)]
  = (c0, [s0,s1,s2,s3])
  where
    (c0,s0) = fullAdd (x0,y0) c1
    (c1,s1) = fullAdd (x1,y1) c2
    (c2,s2) = fullAdd (x2,y2) c3
    (c3,s3) = fullAdd (x3,y3) cin

In Sigma16 we need a 16-bit adder. Many current machines contain 64-bit adders. This would be painful to write in the style of

• The \texttt{rippleAdd} generic circuit is similar to \texttt{rippleAdd4}, except it works on all word sizes.
• It's defined using a very powerful generator called {\color{red}mscanr}
• At circuit generation time, the generator measures the sizes of its input words, and then it constructs a circuit with the right number of full adders, and automatically does all the wiring.

• Notice that |rippleAdd| is equivalent to an infinite set of definitions |rippleAdd0|, |rippleAdd1|, |rippleAdd2|, |rippleAdd3|,

  rippleAdd4

  , \(\ldots\),

  rippleAdd64

  , \(\ldots\),

• Yet the definition of |rippleAdd| is far simpler than e.g. |rippleAdd4|.
• This is due to the power of the generator |mscanr|.

rippleAdd :: Bit a => a -> [(a,a)] -> (a,[a])
rippleAdd = mscanr fullAdd

• Programmers talk about two ``times'' involved in running a program:
  • Compile time
  • Run time
• This makes a real difference: an error message at compile time is very different from a crash at run time
• Hydra has four ``times''
  • Model transformation time
  • Circuit generation time
  • Circuit compilation time
  • Runtime (simulator execution time)
  • And to get real hardware, there is
    • Netlist and layout generation time
    • Fabrication time
    • Running the hardware circuit

We will generally specify large circuits using a circuit generator, not by drawing every component individually. There are two kinds of circuit generator. Design patterns (higher order functions) are the focus of this chapter. Special languages for special kinds of circuit (e.g. control algorithms) are covered later.

Design patterns use circuits as building blocks

Design patterns are higher order functions: they take one or more circuit specifications as parameters. The pattern defines how to connect up these given circuits in a regular pattern. A pattern definition looks just like an ordinary circuit specification, except It uses recursion to decompose groups of signals. It uses abstract circuits, supplied as parameters, instead of specific circuits. Its type may include building block circuits (these parameters contain an -> in their type) and/or size parameters (with a type like Int).

zero                   signal with constant 0 value
one                    signal with constant 1 value

inv                    inverter
and2, and3, and4       and gate with 2, 3, 4 inputs
nand2, nand3, nand4    and gate with 2, 3, 4 inputs
or2, or3, or4          or gate with 2, 3, 4 inputs
nor2, nor3, nor4       nor gate with 2, 3, 4 inputs
xor2, xor3, xor4       xor gate with 2, 3, 4 inputs

Fanout takes a signal and splits it to several outputs.

fanout2 :: a -> (a,a)
fanout2 x = (x,x)

fanout3 :: a -> (a,a,a)
fanout3 x = (x,x,x)

fanout4 :: a -> (a,a,a,a)
fanout4 x = (x,x,x,x)

mux1 :: Bit a => a -> a -> a -> a
mux1 p a b = x
  where x = or2 (and2 (inv p) a) (and2 p b)

mux2 :: Bit a => (a,a) -> a -> a -> a -> a -> a
mux2 (c,d) p q r s =
  mux1 c  (mux1 d p q)
          (mux1 d r s)

mux3 :: Bit a => (a,a,a) -> a -> a -> a -> a -> a-> a -> a -> a -> a
mux3 (c0,c1,c2) a0 a1 a2 a3 a4 a5 a6 a7 =
  mux1 c0
    (mux1 c1
      (mux1 c2 a0 a1)
      (mux1 c2 a2 a3))
    (mux1 c1
      (mux1 c2 a4 a5)
      (mux1 c2 a6 a7))

mux22 :: Bit a => (a,a) -> (a,a) -> (a,a) -> (a,a) -> (a,a) -> (a,a)
mux22 (p0,p1) (a0,a1) (b0,b1) (c0,c1) (d0,d1) = (x,y)
  where x = mux2 (p0,p1) a0 b0 c0 d0
        y = mux2 (p0,p1) a1 b1 c1 d1

mux1 :: Bit a => a -> a -> a -> a
mux1 p a b = x
  where x = or2 (and2 (inv p) a) (and2 p b)

mux2 :: Bit a => (a,a) -> a -> a -> a -> a -> a
mux2 (c,d) p q r s =
  mux1 c  (mux1 d p q)
          (mux1 d r s)

mux3 :: Bit a => (a,a,a) -> a -> a -> a -> a -> a-> a -> a -> a -> a
mux3 (c0,c1,c2) a0 a1 a2 a3 a4 a5 a6 a7 =
  mux1 c0
    (mux1 c1
      (mux1 c2 a0 a1)
      (mux1 c2 a2 a3))
    (mux1 c1
      (mux1 c2 a4 a5)
      (mux1 c2 a6 a7))

mux22 :: Bit a => (a,a) -> (a,a) -> (a,a) -> (a,a) -> (a,a) -> (a,a)
mux22 (p0,p1) (a0,a1) (b0,b1) (c0,c1) (d0,d1) = (x,y)
  where x = mux2 (p0,p1) a0 b0 c0 d0
        y = mux2 (p0,p1) a1 b1 c1 d1

A demultiplexer is an important building block circuit which is related to the multiplexer. It plays a central role in digital circuit design, and we will see many applications that require them. A common application a demultiplexer is to decode binary numbers. For example, we will use them later to implement memories (since the address needs to be decoded), and they are also crucial in a computer's control unit (where they are used to decode instruction opcodes).

A 1-bit demultiplexer, called demux1, takes a control input c and a data input x. It produces two outputs y0 and y1 — so it provides a good practical example of the use of tuples.

(y0,y1) = demux1 c x

The idea of demux1 is that we want to send the data input x to one of the two outputs, and the choice depends on the control input c — thus if c=0 then y0=x, but if c=1 then y1=x. But what happens to the output that is not selected by c? That output has to have a well-defined value too, and we will set it to the constant 0. To summarize, the behavior of the demux1 is

y0 = if c==0 then x else 0
y1 = if c==1 then x else 0

 c   x   y0   y1
--- --- ---- ----
 0   0    0    0
 0   1    1    0
 1   0    0    0
 1   1    0    1

The implementation is straightforward. From the truth table, you can see that the y1 has the same truth table as the and2 gate, and y0=1 if c=0 and x=1.

demux1 :: Bit a => a -> a -> (a,a)
demux1 c x = (y0,y1)
  where  y0 = and2 (inv c) x
         y1 = and2 c x

It isn't actually necessary to define the names of the outputs; here is an alternative definition that outputs a tuple of anonymous signals. The two circuits are identical; the only difference is in the way they are described. One advantage of the first definition is that it offers the names y0 and y1 that may be helpful in discussing how the circuit works, but the definitions yield the same circuit and the choice between them is a matter of style.

demux1 :: Bit a => a -> a -> (a,a)
demux1 c x = (and2 (inv c) x, and2 c x)

There are several ways that a larger circuit could incorporate a demux1. If the pair (y0,y1) is being connected to the input of some other circuit circ that takes a pair, then we could simply write circ (demux1 c x). However, if the larger circuit needs explicit access to y0 or y1, then they should be given names using an equation.

A demux2 circuit takes a two-bit control and produces \(2^{2} = 4\) outputs.

demux2 :: Bit a => (a,a) -> a -> (a,a,a,a)
demux2 (c0,c1) x = (y0,y1,y2,y3)
  where  (p,q) = demux1 c0 x
         (y0,y1) = demux1 c1 p
         (y2,y3) = demux1 c1 q

When two bits are added together, the result could be 0, 1, or 2. Two bits are needed to represent the result, so a bit adder is an example of a circuit that needs to output several signals. The circuit that does this is called a ``half adder'', and its name is halfAdd. (Later we will discuss the ``full adder'', which adds three bits.) The half adder can be specified with a truth table:

Table: Truth table for halfAdd

From the table, it is clear that the carry function is just and2, and the sum function is xor2.

halfAdd :: Bit a => a -> a -> (a,a)
halfAdd x y = (c,s)
  where
    c = and2 x y
    s = xor2 x y

If you don't want to give names to the outputs c and s, the definition can be shortened by putting the expressions for the signals directly in the output tuple:

halfAdd :: Bit a => a -> a -> (a,a)
halfAdd x y = (and2 x y, xor2 x y)

The choice between these alternative definitions is a matter of style: both are correct and both describe the same circuit. The definition with anonymous signals is shorter, while the definition with named outputs uses simpler expressions and gives standard names for talking about the outputs.

There is another bit adder circuit that illustrates how inputs can be handled using either separate arguments or tuples. This is the full adder, which adds three bits. Full adders are needed to add binary numbers, because we have to add the carry as well as the two data bits at each position.

Table: Truth table for fullAdd. The three input bits x, y, z are added to produce a two-bit result consisting of a carry c and a sum s. (Note that the input bits do not represent a 3-bit binary number; they are simply three separate variables to be added.)

Since there are two output signals, it is necessary to combine them in a tuple, so the type will have the form … -> (a,a). We have a choice for handling the three input signals. They could be treated as separate arguments:

fullAdd :: Bit a => a -> a -> a -> (a,a)   -- version 1

Alternatively, the three inputs could be collected into a tuple:

fullAdd :: Bit a => (a,a,a) -> (a,a)   -- version 2

But those are not the only possibilities. Another approach is to collect just two of the signals into a tuple, so there would be two arguments, a tuple and a bit. This gives two more ways to organize the inputs:

fullAdd :: Bit a => (a,a) -> a -> (a,a)   -- version 3
fullAdd :: Bit a => a -> (a,a) -> (a,a)   -- version 4

At this point, there is little reason to prefer one of these types over another. Later, however, when design patterns are introduced, it will turn out that the design of larger circuits can be simplified if we choose version (3), so that is the type actually used for the half adder in the Hydra circuit library.

Don't worry about making the ``best'' choice for such decisions. No one always can make the best choice among the possible alternatives while designing a large system. What happens in the real world is that systems are designed according to experience, judgment, and taste. If it turns out later that the design could be made clearer or more elegant by changing one of these arbitrary choices, then that can be done when the system is cleaned up. The Hydra libraries have going through this process several times.

Now we can define the full adder circuit. For convenience, the calculation of the carry and sum results will be performed by auxiliary circuits, bcarry and bsum.

fullAdd :: Bit a => (a,a) -> a -> (a,a)
fullAdd (x,y) c = (bcarry (x,y) c, bsum (x,y) c)

It isn't necessary to name the x and y signals individually. Notice that the pair (x,y) comes into the circuit, and is then passed to bcarry and bsum. The fullAdd circuit itself doesn't use either x or y directly. Therefore we could just give a name, such as xy, to the cluster (x,y). This shortens the notation:

fullAdd :: Bit a => (a,a) -> a -> (a,a)
fullAdd xy c = (bcarry xy c, bsum xy c)

Note that the signals x and y in the previous definition have the bit signal type a. This can be stated as x :: a and y :: a. In the simplified definition, the argument xy is a pair of bits, so xy :: (a,a).

To complete the circuit, we need to implement bcarry and bsum. There are many ways to do this; the following specifications are reasonable. Since bsum and bcarry have the same type, we can declare those types in one statement. Read this as ``*bsum* and bcarry both have type …''.

bsum, bcarry :: Bit a => (a,a) -> a -> a
bsum (x,y) c = xor3 x y c
bcarry (x,y) c = or3 (and2 x y) (and2 x c) (and2 y c)

dff :: CBit a => a -> a                  delay flip flop
reg1 :: CBit a => a -> a -> a     1-bit register

fanout :: Bit a => Int -> a -> [a]
fanout k x = take k (repeat x)

Buffered fanout takes a signal and splits it to several outputs, and inserts a buffer to ensure the outputs are strong enough.

fanoutbuf2 :: Bit a => a -> (a,a)
fanoutbuf2 x = (y,y)
  where y = buf x

fanoutbuf3 :: Bit a => a -> (a,a,a)
fanoutbuf3 x = (y,y,y)
  where y = buf x

fanoutbuf4 :: Bit a => a -> (a,a,a,a)
fanoutbuf4 x = (y,y,y,y)
  where y = buf x

fanout2 :: a -> (a,a)
fanout2 x = (x,x)

fanout3 :: a -> (a,a,a)
fanout3 x = (x,x,x)

fanout4 :: a -> (a,a,a,a)
fanout4 x = (x,x,x,x)

A wiring pattern that replicates a singleton signal to form a word. The input x is a signal, which is replicated n times to form a word w of size n.

Usage:

w = fanout n x

General form:

fanout :: Bit a => Int -> a -> [a]
fanout n b             connect bit b to n outputs, forming a word

Representing a boolean bit as a word: boolword takes a bit x, and pads it to the left with 0s to form a word. If the input x is False (0), the result is the integer 0 (i.e. n 0-bits), and if x is True (1) the result is the integer 1 (rightmost bit is 1, all others are 0).

Usage:

boolword n b           form an n-bit word, lsb = b, other bits = 0

Definition:

boolword :: Bit a => Int -> a -> [a]
boolword n x = fanout (n-1) zero ++ [x]

Calculating a bit from a word

any1                   or the bits in a word: result is 1 if any 1 bit

orw :: Bit a -> [a] -> a
andw :: Bit a -> [a] -> a

And/Or over a word: Determine whether there exists a 1 in a word, or whether all the bits are 0. A tree fold can do this in log time, but for simplicity this is just a linear time fold.

orw, andw :: Bit a => [a] -> a
orw = foldl or2 zero
andw = foldl and2 one

Logic on each bit in a word

Word inverter: winv takes a word and inverts each of its bits

winv :: Bit a => [a] -> [a]
winv x = map inv x

wlatch :: CBit a => Int -> [a] -> [a]

Defines a register with output r, containing n bits, and with input x. At every clock cycle, the register discards its old state and replaces it with the current value of the input.

r = wlatch n x

reg n ld x is an n-bit register with load control ld, data input x

reg
  :: CBit a =>
  Int             -- ^ k = the word size
  -> a          -- ^ ld = the load control signal
  -> [a]        -- ^ input word of size k
  -> [a]        -- ^ output is the register state

reg k ld x = mapn (reg1 ld) k x

The regfile circuit is a register file with 2^k registers, each n-bits wide, load control ld, destination address d,` reads out registers sa and sb, data input x

regfile n k ld d sa sb x