Beginning Logic Design – Part 2

Hello and welcome to Part 2 of my Beginning Logic Design series!

In this lesson we are going to build a 4-bit adding machine!

Binary Numbers

In the digital world all we have is 0 and 1, so we need to come up with some clever ways to represent numbers. For now we’ll only worry about 4-bit unsigned integers.

Here’s a chart of the decimal numbers we’ll be able to represent, along with those same numbers in Binary and Hexadecimal

The numbers we’ll be able to represent with 4 bits

The digit displays in Logicly have 4 inputs, each represents a binary bit. The order for this display in Logicly goes from the least significant bit at the top to the most significant bit at the bottom.

Logicly digit display showing the hexadecimal value for 0101

I suggest building this design in Logicly yourself and playing with the switches if this is unfamiliar to you.



The Classic 1-Bit Adder Circuits

Probably the most famous of combinational circuits is the Adder. Take two numbers in, and output the sum. Typically we start this design by creating what is known as a half adder, it takes two 1-bit inputs and adds them together.

Let’s look at a truth table for 1 bit addition (in binary!)

As you can see, to handle all 4 possible cases, we need to output 2 binary digits due to the 1+1 case. To support addition with any set number of digits, you need one more output digit to support the carry over value that changes a higher digit. This is similar to when you do 9+9 with decimal numbers, you carry a 1 to the 10’s place so you can represent the sum as 18 instead of just 8, which would be wrong! We’ll separate out the sum and carry out in our table so that they are easy to reference.

Half adder truth table

Looking at this table, think of what gate could take a and b as inputs and output carry, as well as what could take a and b as inputs and output sum.

The answer is that we can use an AND gate to determine what the carry should be, and an XOR gate to determine the sum.

A half adder circuit

This is called a half adder, named so because it provides roughly half of a more useful design called a full adder. The full adder also lets us add two 1-bit numbers together, but can also handle chaining carry values together to add numbers of any width of bits!

The full adder shares the same two outputs, but adds a carry in input to consider the carry out value of a lower digit. Think about how we handle long addition in decimal, with the example of adding 123 and 99.

Very Math

For the middle digit of the answer here, you will add three numbers, 2 + 9 + 1(the carry in) to land at 2 (carry out the 1).

We follow this same principle for the full adder, the truth table for which is a wee bit more complicated, due to the additional input.

Truth table for a full adder

The design for the full adder will take a bit more effort to work out, but let’s look at this table and make a few observations.

  • When the carry in input is 0, the carry out and sum are the same as for the half adder, so we can use that design as a base for half of the input possibilities
  • When carry in is 1, the sum is the opposite of what it otherwise would be
  • When carry in is 1, the carry out is 1 if any other input is also 1

Try on your own to make a full adder!

The Full Adder

Hopefully you found some success in building your own full adder, but if not, don’t fret! Build this design on your end and tinker with it a bit.

A common full adder implementation, other designs are possible

It takes some practice to analyze these circuits. This one only has 3 inputs and two outputs, but it’s the arrangement of the 5 logic gates inside that makes you scratch your head. To understand a circuit like this I will look at the outputs, and follow the lines back to the inputs.

In this design, the XOR gates that lead to sum creates a situation where sum will be 1 if an odd number of the inputs are 1. For carry out there are two AND gates that result in the final OR gate outputting 1 if either a AND b, or if ((a XOR b) AND carry in).

With this design validated, we can save this as a custom component in logicly so we hide this complexity within a black box and get back to focusing on our goal, the adding machine!

We’ll first need to name the inputs and outputs. You can name them by clicking on the switches and light bulbs and entering the name into prompt that pops up. Next, highlight the whole design and go to Edit->Create Integrated Circuit or right click and select Create Integrated Circuit from the menu.

Create integrated circuit prompt

On my end, before hitting save, I moved the outputs so that sum was on top and carry_out was below it. We now have a reusable Full Adder circuit!

Putting It All Together

Before I go too far, and make a huge mess of our schematic, I’ll make a 2-bit adder. I’ll start by adding some switches I can use to setup my inputs, along with displays to see what number it represents.

My two bit operands

Next, I’ll add two full adders, and wire the upper switch (least significant bits) to the first adder.

Starting to wire it up

Next I’ll hook up the output display by routing the sum to it.

The display is angry!

The full adder isn’t outputting a valid state because some of its own inputs are invalid, in this case the lack of a carry in signal. I’ll use a constant to keep it low for the lowest bit.

Setting the carry input to 0

At this point it can handle 1 bit input, but only 1 bit output. I could hook up the carry in for the 2nd bit.

Reading both output bits

To handle 2 bit input, I’ll route the 2nd bit switches to the next adder and route the carry out of the first adder to the carry in of the next. To display the output here, I’ll route the sum of the first adder to the 1st bit of display input, route the 2nd adder’s sum to the 2nd bit input, and the final carry out to the 3rd bit.

A working 2 bit adder

This same pattern can be extended to handle another 2 bits.

A 4 bit adder!

There’s the 4-bit adding machine! It could be made to any bit width, but 4 fits a single display. It is possible for there to be a 5th bit of output, but we’ll just drop that for now. In many adders that final carry is interpreted as an carry flag to let you know the sum digit width was larger than the input digit width.

For a messier example of how this can scale, here’s a 16-bit adder in logicly.

This is the largest I’m willing to fuss with in Logicly

That covers this post on building some digital adders. If you have any feedback or questions please leave a comment! Keep tinkering!

Save

Save

Save

Save

Save

Beginning Logic Design – Part 1

I have a passion for learning about technology. My desire to understand more about how things work has driven me to dive into lower and lower levels of computing systems. For the last couple years I’ve been trying to go all the way down to working with the basic digital components. I did not find many resources to help learning these low level basics, so today I am kicking off a series to teach others how easy it can be to get started with digital logic design.

How We’ll Be Learning

There are not a lot of tools I’ve found that are modern, useful or stable enough to use to get started with learning basic digital design. Most legit hardware design tools are based on using a Hardware Description Language such as VHDL or SystemVerilog. I think the early digital knowledge you need is best solidified with schematic design and simulation; by working with the most basic logic gates to understand how larger and more complex designs can be made from very simple components.

The best tool I’ve found so far for digital logic design and simulation is logic.ly, an educational piece of software that has a clean and usable interface along with a good set of features around managing subcomponents. It is not free software, a full license runs around $60, but there is a free trial that you can use for up to 30 days. It is also only supported for Windows and OSX, though I have had good luck running it via Wine on my Ubuntu box.

The best free (and open source!) alternative to this I found was BOOLR, which is a fairly impressive simulator but as of this writing is not stable enough to recommend. I’ll be keeping an eye on that project to see where it goes.

As far as prerequisite knowledge requirements, I recommend some familiarity with binary and hexadecimal numbers. Outside of that, some determination is all you need!



Getting Started

To get started, download Logicly and get it installed. Activate your 30-day trial and fire it up!

Logicly running via Wine on Ubuntu 16.04

To get the lay of the land, let’s look at some of the most basic components Logicly has to offer.

Input and Output devices in Logicly

I have Logicly’s 5 input devices on the left and its 2 output devices on the right.

Starting from the top of the inputs, Logicly has a toggle switch that operates very similar to a light switch, it outputs 0 when the switch is off and 1 when the switch is on. Below that is a button, or momentary switch, that normally outputs 0, but while it is held down will output 1. The next input devices is a clock signal, it automatically flips its output after a configurable time, one second by default. The last two inputs are constants, always 1 or always 0.

On the right side we have the outputs. The light bulb is lit or unlit depending on the signal being driven to it. The second output device is a digit display, which will show a 0-F hexadecimal value based on its 4 input bits. We’ll only be using the light bulb for this lesson.

Feel free to dabble with these components if you’d like, we’ll use them to explore the logic gates in the next section.

Basic Logic Gates

Logicly has 9 components in it’s Logic Gates category, we’ll explore them each here.

The first row has the Buffer and the NOT gate. These are the simplest gates. The Buffer simply outputs an identical signal to its input, in Logicly this is generally only useful for adding a bit of delay to signal propagation. We won’t be using the Buffer component very much, if at all. The NOT gate will output the opposite of its input.

A buffer and a NOT gate in parallel

As you can see above, when the switch is on, the light behind the buffer is also on, while the NOT gate inverts the signal and the light behind it stays off. Notice the similarity of the component symbols, in digital design you’ll often see a small circle that indicates the inversion of a signal from low to high or high to low.

The next row of components is the AND gate and the NAND (NOT-AND) gate. The AND gate will output 1 only if all inputs provided to it are 1.

AND gate in various input configurations

The NAND gate has the opposite output of the AND gate, similar to what you’d see if you used a NOT gate to invert the output of an AND gate.

NAND gate in various input configurations

The next two gates are OR and NOR. The OR gate will output 1 if any input is 1, and 0 if all inputs are 0.

OR gate in various input configurations

As you may expect, the NOR gate is very similar to the OR gate, but with inverted outputs.

The next couple gates are XOR and XNOR. The XOR gate, short for exclusive-or, is a little bit trickier. In a 2-input configuration it will output 1 if the two inputs differ, and 0 if the two inputs are the same.

XOR gate in various input configurations

This symbol for XOR is very similar to OR, but has an extra curved line on its input side to stand apart. Just like with the other N* gates the XNOR has the opposite outputs of XOR.

The last basic logic gate Logicly gives us is a Tri-State Gate. It is very similar to the Buffer with the addition of a signal to control if the output of the buffer is enabled. If the Tri-State is enabled, the output will match the input, if disabled it will not emit an output which leaves the connection unset, or floating, allowing something else to control the output line its connected to. Don’t worry about this gate for now, we won’t use it for a bit.

It can take a while to get used to these symbols and their outputs, here’s a diagram that shows the truth tables, and boolean algebraic expressions for these gates.

These gates are each fairly simple but all digital electronics are composed of just these gates in various arrangements! It may take a while to understand how things like RAM, CPUs and entire computers can be built from such simple components, but as you practice building incrementally more complex circuits it will begin to make sense.

Functionally Complete Gates

Two of these logic gates (NAND and NOR) have a very special feature, they are functionally complete. This means that any other gate, and therefore any digital machine, can be made of just NAND gates or just NOR gates. This has some significant benefits for manufacturing electronics, but since we’re not fabs we’ll just explore this property to get a bit of practice building some simple circuits. NAND logic is a bit more popular for various reasons, so let’s explore how we can make some of other other basic gates by using just NAND gates.

To start off with, here’s a NAND gate setup to work just like a NOT gate, I have these gates in parallel so they share the same input to allow for easy comparison.

NOT gate next to NOT implemented with a NAND gate

By simply wiring the switch to both NAND inputs, we get the exact same behavior as a NOT gate.

We can use this same concept to implement an AND gate. Since NAND has the opposite output of AND, we can use the previous NOT-like configuration to flip the output of NAND to match AND. NNAND?

AND gate next to AND implemented with NAND gates

For some solo practice, try your hand at replicating the function of OR and XOR gates using only NAND gates. If you get stuck (I did), reference Wikipedia’s page on NAND Logic for the solution and look at the wire states in Logicly as you toggle the inputs and think about why it works.

 

This is a whopper of a first lesson, but I hope it’s useful for folks just starting out. If you have any questions or feedback please leave a note in the comments and I’d be glad to help you out. In the next post we’ll be exploring some of the interesting things you can do by combining these basic logic gates. Keep tinkering!

Save

Save

Save

Getting BusyBox with It

Following up on the Building a Barebones Linux System post, today I will be adding BusyBox to make the system a smidge more usable.

What is this BusyBox?

BusyBox is a refers to itself as The Swiss Army Knife of Embedded Linux. It is a collection of common Unix tools living within a single binary that uses the magic of argv[0] to facilitate a lightweight implementation of common programs like sh, ls, cat and many more. It is extremely common in the embedded systems community because it is a well maintained open source project and can be built very small.

For my purposes, I will use BusyBox instead of going into a full Linux From Scratch route. This will give me a shell and a few other basic userspace tools needed to allow me to make some use of this bare bones system.



Automating the builds

At this point I have been dabbling with this bare bones setup long enough that I want some additional tooling to help manage rebuilding as necessary. There are many good tools out there for managing custom Linux builds, but for now I’d like to continue using custom tools to learn more of what it takes to build a Linux distro from square one.

I’ve made a repo on Github and a Makefile that will pull in the kernel, build it, and build my initramfs. It also has a runvm command that will help me test my builds quickly.

KERNEL_VERSION=4.13.3
KERNEL_DIRECTORY=linux-$(KERNEL_VERSION)
KERNEL_ARCHIVE=$(KERNEL_DIRECTORY).tar.xz
KERNEL_URL=https://cdn.kernel.org/pub/linux/kernel/v4.x/$(KERNEL_ARCHIVE)


all: vmlinuz initramfs


# Kernel build targets
vmlinuz: $(KERNEL_DIRECTORY)
  cd $(KERNEL_DIRECTORY) && make defconfig && make -j`nproc`
  cp $(KERNEL_DIRECTORY)/arch/x86_64/boot/bzImage vmlinuz

$(KERNEL_DIRECTORY):
  wget $(KERNEL_URL)
  tar xf $(KERNEL_ARCHIVE)


# Initramfs build targets
initramfs: initfs initfs/init
  cd initfs/ && find . | cpio -o --format=newc > ../initramfs

initfs/init: initfs init.c
  gcc -o initfs/init -static init.c

initfs:
  mkdir -p initfs/bin


# Utility targets
runvm: vmlinuz initramfs
  qemu-system-x86_64 -m 2048 -kernel vmlinuz -initrd initramfs

clean:
  rm -rf vmlinuz $(KERNEL_DIRECTORY) $(KERNEL_ARCHIVE)

 

Configuring and Building BusyBox

BusyBox uses buildroot so its configuration and build process are very similar to the kernel itself. After downloading and extracting the source I’ll use make menuconfig to use the ncurses based config editor.

I’ll be leaving most settings at their default, but will configure the build to generate a static binary since I don’t yet have a libc implementation to link against.

Configuring and Building BusyBox

With BusyBox built, I’ll add it to my initfs directory so that my Makefile includes it in my initramfs.

Copying busybox binary to my initfs/bin directory

The busybox binary will act differently based on what it is called as, if we renamed it to sh it would act as a shell, or if named ls it will list our files and such. To allow it to serve all of these functions I’ll check what commands my build implements and create symlinks for each program it provides.

Creating the symlinks for BusyBox

Switching the Build to BusyBox

With my process for building BusyBox roughly figured out, I’ll save a copy of my BusyBox config, so that future builds will also be static linked. I’ll also include a small shell script that builds my symlinks.

cd initfs/bin
for i in `./busybox --list`
do
  ln -s busybox $i
done

Now that I have BusyBox in my initramfs, I’ll switch my init process from my custom binary to a shell script that will forever spawn a shell to use.

#!/bin/sh

while true
do
  sh
  sleep 1
done

With this script in place I’ll update my Makefile and repo to include the changes I’ve made here.

And now we test!

Testing the build in QEMU

There are a few deficiencies in here still, e.g. ps won’t work because I have no procfs mounted and sh will complain about being unable to access tty.

To get a few more things to run sanely, I’ll add /dev, /proc and /sys to my initramfs and modify my init script to mount the procfs and sysfs. I’ll also run mdev -s which is provided by BusyBox to populate /dev and /sys. Lastly, I’ll launch my shell with setsid cttyhack sh so that job control is enabled.

With all that setup, the system is substantially more usable! I’ll push these changes to my repo and call it a wrap. If you have any questions or feedback please let me know in the comments 😀

Save

Save

Save