Building an 8-bit computer, Part 1: The elements of the computer

This blog post is the first in a series where I plan to document where I plan to document the design and eventual build process for an 8-bit computer using logic chips (ie. no microprocessor). I have made several posts on my blog that cover concepts I’ll be referring to and using in this series and will link to them in each post as these topics come up. This post will be going into detail about the individual parts of a CPU and adds more depth to the topics discussed in my first post: What’s a Computer and what’s it thinking?. I would recommend reading that and another one of my posts, Basics of Binary, to be able to follow along.

The computer I will be designing will be based upon Von Neumann architecture which will consist of registers, an arithmetic logic unit, a system bus, memory and a memory management unit, a control unit, and a means for basic input/output. The goal of this post is to break down each of these parts and explain what they will do before I dive into the design process in future posts.

Registers

                Registers act as memory for a single unit of data that can be readily accessed by the computer without the need to load from memory. In the case of my computer design, these will store a single byte (8 bits) of data that can be used by the other parts of the computer as they are needed.

Arithmetic Logic Unit

                The arithmetic logic unit (ALU) is the piece of the computer that will be able to perform mathematical operations on data that is sent to it. I plan to design my ALU to operate using two input registers, Register A and B, and a single output register, Register C. It will be designed such that it can perform the following operations: Add (ADD), which adds registers A and B; Shift Right (SHR), which shifts register A one bit to the right (dividing by two); Shift Left (SHL), which shifts register A left one bit (multiplying by two); Logical And (AND), which takes the AND of registers A and B; Logical Or (OR), which takes the OR of registers A and B; Logical Exclusive Or (XOR), which takes the XOR of registers A and B; and Logical Not (NOT), which takes the NOT of register A. I will not need to implement circuitry to perform subtraction as by using these operations I can subtract two numbers albeit with multiple steps. This concept is covered in my previous post How computers represent negative (integer) numbers.

System Bus

Visualization of a shared system bus
Source: W. Nowicki

The system bus is the network of wires that information is shared between the individual elements of the computer. The system bus will further be broken down into a 16-bit address bus (this is to allow me to address 64k of memory), an 8-bit data bus, and a control bus (the size will be determined later in the design process).

Memory and Memory Management Unit

The memory of the CPU will consist of 64k of addressable memory. I plan on reserving the first 8k for ROM and having the remaining 56k available for RAM and I/O devices. The memory management unit controls the memory and is capable of reading memory to and from the data bus at the location provided to it via the address bus.

Control Unit

The control unit is perhaps the most complicated part of the whole system. It is what controls the timing and operation of all other elements in the computer. This is done by keeping track of where the computer is within a program via the Program Counter and executing a mini-program for each instruction that activates and deactivates the other elements in concert to perform an operation. By way of the control bus, this unit is what allows all element to share common data and address buses without trying to write/read different information simultaneously (Bus contention). I will cover this in far more detail in a future post as it is likely where most of the time spent designing the computer will be focused.

Input/Output

My goal is to make the input/output as generalized as possible so it is simple for me to attach virtually any device without too much added circuitry. Currently, I would like to have some sort of keyboard/text input and a display device. The details of this will be covered further in a future post.

The Next Steps

I plan to break down the design and build process into the individual elements I have described here and document the progress with regular posts. My next post on this topic will cover the design of the ALU. Please follow my blog if you’d like to be updated when I post and follow this project!

If Earth had a ring

In this blog post, I’ll explore a scenario in which Earth has a ring instead of a moon. The goal of this post is to pique the imagination of the reader and demonstrate how math and science can be used to explore such “what if?” questions.

The Moon as a ring

One of the scientific hypotheses for the origin of the Moon, called the  Giant-impact hypothesis, posits that the Moon was formed from the debris that coalesced after a collision between Earth and a mars-sized body approximately 4.5 billion years ago. More information about this hypothesis, supporting evidence, and alternative hypotheses can be found in the provided link. For this case I’ll explore a scenario in which the collision debris dispersed in what such that it never coalesced and instead remained a ring to present day. I’ll be making a lot of assumptions and approximations that I’ll call out, but this provides a good starting point for a somewhat “realistic” scenario that could lead to Earth having a ring.

I’ll make a few assumptions to figure out the size of the ring. These assumptions are: the ring has a density similar to that of Saturn’s (~45 kg/m3), the ring is centered about the current orbit of the moon (~385,000 km with an inclination of ~5°), the ring’s thickness is similar to that of Saturn’s (~30m), and the mass of the ring is equal to that of the Moon (7.35×10^22 kg). Using these assumptions, I can calculate that the ring has a volume of:

And from this, the distance between the inner and outer edges of the ring with the following formula:

Unfortunately, we run into a bit of a problem here in that the distance between the outer and inner edges of our ring is greater than the distance that our ring is to earth. Something not possible. This is because we use the mass of the moon as the mass of our rings. By using the Moon’s mass, we are assuming that the ring has a mass nearly 1000 times greater than that of the rings of Saturn. This would be more like a debris field surrounding the Earth. I took the liberty of providing a rendition of this.

A bad ring at best, total obliteration of Earth’s surface at worst

A ring like the Moon

Since our last attempt to determine the size of a ring failed, we’ll just make some more assumptions. This time, we’ll assume the following: the ring has a density similar to that of Saturn’s (~45 kg/m3), the ring is centered about the current orbit of the moon (~385,000 km with an inclination of ~5°), the ring’s thickness is similar to that of Saturn’s (~30m), and the ring has a distance between the inner and outer edges equal to the diameter of the moon (~3,474 km). Using these assumptions, I calculated the mass of the ring to be equal to around 1/10000th the mass of our last ring (working this out took up a lot of space, so you’ll just have to trust me on that unless you want to work it out yourself). Modeling this, the result is much more ring-like.

Our Earth-Ring system
Earth from the ring
The ring (barely visible) from near Earth

Earth’s real-life ring

An interesting tidbit to add: the Earth has a synthetic ring of man-made satellites. At an altitude of around 35,800 km above the equator there are about 400 or so satellites in a ring around the Earth in Geosynchronous orbit. So while this ring is incredibly sparse and in no way possible to observe, it is technically still there.

Please like and share if you enjoyed reading!

The Periodic Table: An index of everything

This post builds further off the concepts that I covered in one of my previous posts: The Atom: The building blocks of everything. If you aren’t familiar with what an atom is, or what protons, neutrons, isotopes, and electrons are, I recommend giving it a read to be better able to understand some of the concepts I’ll discuss in this post. In this post, I’ll be discussing the period table, what information can be found on it, and what that information means.

An Individual Element

All periodic tables that you’d find are arranged in the same way, but the information provided about each individual element will vary. For example, the one I’ll be using and referring to in the blog post has information about the valance of an element. This provides us with information about the common oxidation states for each element, I’ll discuss this further in a future blog post. Despite this, several key pieces of information are likely going to be found on any periodic table. These are: atomic number, symbol, and atomic mass.

Atomic Number

The atomic number, usually listed at the top of an individual element’s square, tells us the number of protons an atom of an element has. This also gives us some insight into how many electrons an atom will have, as it is generally equal to the number of protons in the element unless the element has been oxidized or reduced (lost or gained an electron through a chemical reaction).

Symbol

The symbol for an element is a simplified way of representing said element. The symbol is either 1 or 2 letters that can be used to abbreviate the full names of an element when expressed in chemical compounds or reaction formulas. Some symbols are easy to understand where they come from for example, C for carbon. Other times these symbols may not make immediate sense like Au for gold, which comes from the Latin word for gold “Aurum.” Generally, if the source of the symbol isn’t immediately obvious from the name of an element, that element was discovered and isolated in antiquity and the symbol refers to its name from the period of discovery.

Atomic mass

The atomic mass of an element describes the average mass of an atom of that element in atomic mass units (defined as 1/12 the mass of a carbon-12 atom). This number is a weighted average equal to the sum of the mass of the isotopes that occur in nature and their relative percent abundances on Earth. Using this weighted average is useful as most chemistry is done at the macroscopic scale where huge numbers of atoms are present that likely are representative of the natural distribution of isotopes.

The table as a whole

Now that we’ve covered what information is provided for each individual element, we can look at the table and cover what information is further provided about these elements by their arrangement and placement within the table. The general trends found within the table, called periodic trends, are useful to know as they provide insight to the chemical properties of the elements. Some major trends are: electronegativity, ionization energy, electron affinity, and atomic radius.

Electronegativity

Electronegativity refers to an atoms ability to attract electrons that are shared in a chemical bond towards itself. For example, in the cased of water (H2O), oxygen is more electronegative that hydrogen and as such, electrons are more likely to be around the oxygen atom that the hydrogen atoms. This means there is greater electron density around the oxygen atom as a result of its electronegativity relative to hydrogen. The general trend observed in the periodic table is that elements farther to the right have increasing electronegativity (fluorine having the highest) and element farther down the table have lower electronegativity.

Ionization Energy

Ionization energy is the energy required to remove one electron from an atom forming an ion (an atom or molecule with a non-zero net charge) with a charge of +1 as there are now more protons than electrons. The more energy required to do this for an element, the less likely a positive ion is to form (oxidation) in nature. The trend observed in the periodic table is that ionization energy increases as you move to the right and up along the table, meaning it would require a lot more energy to remove an electron from fluorine than it would to remove one from cesium.

Electron Affinity

Electron affinity is the amount of energy released when an electron is added to an atom forming an ion with a -1 charge. This process can be thought of as the opposite of that described for ionization energy. With increasing electron affinity, the more likely a negative ion is to form (reduction) in nature. The trend is the same as with ionization energy in that it increases as you move right and up the table.

Atomic Radius

Atomic radius is the size of the atoms of an element. Since electrons don’t have definite positions or distances from the nucleus of the atom, values for atomic radius are approximations as there is no definitive cutoff where the atom stops. This is usually defined by the Van der Waals radius, which is based upon the closest distance two atoms of an element can get to one another without being chemically bonded.

Additionally, the table can be divided up into groups, periods, and categories. Groups, or the vertical columns of the table, consist of elements that generally have similar reaction proprieties due to similar valance electron arrangements. Periods are the horizontal rows of the table and the periodic trends discussed earlier can be seen moving along these periods, cycling when moving to another period. The cyclical nature of these trends when moving through periods is what gives the table its name. Categories can also be displayed which group elements together that exhibit similar chemical and physical properties.

I hope you were able to learn a little bit about what can be found on the periodic table and are able to appreciate it as more than just a standard science class backdrop. Please like and comment if you learned something and thanks for reading!

Exploring analog video signals

One of the issues I foresee with my goal of building a computer from logic gates is coming up with a solution for outputting video from that computer to the screen. In this post I’ll discuss how I used a micro-controller to send some very basic images to an analog television using composite video signals. It may be helpful to refer to my previous post Electronic Basics: Circuit Components, however I’ll try to explain everything without having to rely too much on that. This is the another type of post that I’d like to have on my blog in addition to my technical posts and interesting/fun application posts where it’s more documenting my tinkering/experiments.

Raster Scanning

Raster scanning is the process by which most common television and monitors display image. This works by scanning across the screen line by line. After a horizontal line has been scanned, the television will then be moved down one line until it reaches the end of the screen. At the end of the screen, the TV starts scanning again from the top left. In the United States, a standard definition composite television has 525 horizontal lines per frame and scans at a rate of 63.555 microseconds per line. This gives an effective framerate of 29.97 frames per second. This was 30 frames per second before color television however, in order to fit color information in the signal without causing artifacts on the screen, the framerate was changed to 29.97.

Raster scanning diagram
Source: http://scanftree.com/computer-graphics/

The signal

The most important part of this whole exercise was figuring out what information needs to be in a composite video signal in order to display a picture. The signal itself conveys two important pieces of information: it tells the TV how bright the point it’s currently drawing should be and when the TV should start the next horizontal line and frame. In order to accomplish this, the signal is split into two parts. First a 0 volt sync signal is sent for either 4.7 µS to tell the tv to move to the next horizontal line (called a horizontal sync or H-sync) or 58.855 µS to tell the TV to start at the top for the next frame (called a vertical sync or V-sync). The rest of the time after the H-sync signal can then be used to transmit the video information with voltages from 0.3 representing black to 1.0 representing white. This gives me enough information to work with in generating my own video signals.

Depiction of H-sync, V-sync, and a video line

Actually doing it

Leaning this, I felt as though I had enough to get hands on and try out my hand and generating some video signals. To do this, I used my Arduino microcontroller and a simple resistor network so I can drop the voltage of the Arduino signals to 1 volt to send to the TV, shown below. For the TV, I found a dinky radio television for about 5 bucks at a thrift store that needed a bit of modification in order to get working. This blog post was very helpful in actually getting this to work.

Diagram of the resistor network. Left side are pins from the Arduino and the right side are to the TV. The TV Video and TV Ground wires are connected with a 75 ohm resistor.

The Arduino first sets the sync and video signals to 0 for the required amount of time depending on whether it needs to do a V-sync or H-sync. It then sets the sync signal to 1 and video signals to 0 or 1 for the rest of the time to draw the image. Unfortunately, this setup only allows me to generate black or white and no greys.

 The television needed a bit of modification in that its composite video port wasn’t a standard one so it wouldn’t work with the composite cable I had on-hand. In order to get around this I opened it up, took off the jack, and added some jumper wires. Some pictures showing the modifications are shown below.

Warning: Do not perform electrical work on CRT televisions unless you know what you’re doing. Capacitors within can be charged up to several hundred volts and the CRT itself to several thousand. I took many precautions to ensure all capacitors and the tube were fully discharged before I started working.

The composite video connector for the television. I de-soldered and soldered jumper wires in its place.
Wires in place of connector. Red is video, blue and black are both ground. If blue is not in contact with ground, the TV bypasses the composite signal and switches to radio.

The Result

The television looked just as frustrated with me as I was with it earlier.

After several hours of tinkering, I was finally able to generate what could be called an image. A very basic face that seems none too thrilled to be a part of this escapade. I still have a bit to go in terms of how to draw images as currently I have to hard code each line but I certainly have a better grasp of video signals for when I’ll need to use them in the future.

Like and Follow if you enjoyed the read!

Some more digital logic

This post will be expanding on what I covered in my previous post on this topic: Digital Logic. I am recommending giving that a read if you aren’t familiar with logic gates or digital logic. In that previous post, I mention that logic gates can be connected together in ways that allow us to construct more complicated logic devices and even computers. I’ll be covering several of these more complicated constructions in this post. I will be covering multiplexers, demultiplexers, adders, flip flops, and buffers. This post and the devices described within will be very useful in my goal of documenting designing and building a computer out of logic gates.

Multiplexer

MUX from discrete gates
MUX symbol

A multiplexer, or MUX, is a device that allows us to take multiple inputs (shown in the diagrams as D0 and D1) and select which input to output on the output line (Y in the above diagrams) using select bits (S0 on the diagrams). The number of data lines we can select from with a given number of select bits is equal to 2 to the power of the number of data lines. For example, with 3 select bits we can choose from 2^3 or 8 input data lines. In the above diagram, if S0 is equal to 0 then D0 is output, if S0 is equal to 1 then D1 is output.

Demultiplexer

DEMUX from discrete gates
DEMUX symbol

A demultiplexer, or DEMUX/DMX, is a device that works in the opposite way as a multiplexer. The demux takes in one input data bit (D in the diagrams) and we are able to select which output line (Y0 and Y1 in the diagrams) we would like to output to using select bits (S0 in the diagram). In the above diagram, if S0 is set to 0 then D is output to Y0, if S0 is set to 1 then D is output to Y1.

Adder

Full adder from discrete gates
Full adder symbol

An adder is a device that is able to add two bits together and output the sum of those two bits as well as the carried bit if both inputs are 1. The adder is also able to take a carried bit as input allowing us to chain adders together to add larger binary numbers.

Buffer

Buffer symbol
AND gate buffer

A buffer, or line driver, is a very simple device that acts as a switch and lets us choose to output the input line by setting the enable bit. The device acts like an AND gate however these are critical in situations where we have multiple devices connected to a single output line (for example, a data bus in a computer) where we want to prevent those devices from attempting to output to that line simultaneously. This is because when the enable bit is set to 0, the output is not set to 0 but instead “floating.” This means it isn’t actively trying to write 0 to the output line.

D-type Flip Flop

D Flip Flop from discrete gates
Animation demonstrating flip-flop function

This device is a little more confusing than the previous ones so I’ve added an animation demonstrating its function. This device allows us to store data, a critical function for computers and electronic devices. It works by setting the output Q to the value of the data line and Q’ to the opposite value only when the clock signal is triggered. When the clock signal is off, the output is “latched” meaning no matter what happens on the data line, the output remains the same. These can be used to create volatile memory cells, something I briefly mention in my post What’s a Computer and what’s it thinking?

Some Circuits

As with the basic logic gates themselves, these devices can be arranged in ways to accomplish more complex tasks. I’ve created a couple of circuits using these as examples. The first uses D-type flip flops to act as a binary counter and the second strings together several adders to allow for the addition of 2 4-bit binary numbers.

Animation showing 4-bit binary counter from flip flops
4-bit adder, adding 3 and 4 as an example

Please like and comment if you learned something or find this interesting and follow my blog to see when I post more content!

Building a black hole

With the recent news of the first image captured depicting the event horizon of a black hole they’re kind of a hot topic. Here’s a good article that sums up the story nicely: link. I’ve mentioned a program I’ve been working on on-and-off for a while in a few of my previous posts (Alien Skies: How bright is a bright and sunny day? (Part 1 of 2), Alien Skies: Goodbye blue sky (Part 2 of 2), and Pretty Math: Strange Attractors) that is essentially a galaxy simulation/exploration program where the user can explore a fully rendered galaxy complete with the menagerie of celestial objects one could expect to find. The program is still very much a work in progress but one of the things that I have implemented already are black holes so I figured I’d piggy back on the hot topic to discuss how I generate and render black holes in my program.

How big should our black hole be?

In order to be able to generate realistic black holes we first need to figure out how big they must be. I’m focusing mostly on stellar mass black holes that have masses from 5 to greater than 10 times the mass of our sun. I chose these because I felt like they would be the most likely black hole someone flying around and exploring a galaxy would come across. These black holes are formed at then end of a large star’s (>5 times the mass of the sun) life cycle when it collapses into an infinitely dense point called a singularity. The most important part to our discussion is that there is some point at a distance near this singularity where the escape velocity (that is the speed required to overcome the force of gravity) is greater than the speed of light. This is called the event horizon and it’s distance from the black hole is governed by the mass of that black hole. If we look directly at any point within this event horizon, we would see only black. The radius of the event horizon (called the Schwarzschild radius) can be determined by the following formula: where r is the radius, G is the gravitational constant, M is the mass of our black hole, and c is the speed of light.

Formula for Schwarzschild with and without units

Using this information, its very easy to generate a black sphere of the appropriate size for a 5 solar mass black hole (~15 km). The results of just this, however, are rather lackluster as shown below.

Gravitational Lensing

An important piece that our current model for a black hole is missing is an effect known as gravitational lensing. This is causes by light bending around the black hole due to gravity. In order to implement this, light near the event horizon of our black hole should warp around and even allow us to see objects that lie directly behind the black hole. In order to accomplish this, I cast a ray of light form the observer and the change the angle of that ray after it passes the center of our black hole relative to the observer based on how close it is to the event horizon. I took a bit of artistic liberty in choosing how must to bend the light as I couldn’t find an easy method of quickly determining how much that beam should be bent. Below is a diagram illustrating my approach.

The ray from the observer’s eye is bent toward the black hole as it passes a line through the center

The Results

The results of this are rather interesting to look at and I’ll let them speak for themselves with some images and animations. Something it is currently still missing that will add a lot to the visuals is the accretion disk. I do currently have a general idea of how I would accomplish this and if it is interesting enough and works I plan to cover that in a future post. Please like and share this post if you found it interesting!

Black with with lensing near event horizion
Same black with a cube partially obstructed
With the cube completely obstructed, it is still visible above and below the event horizon due to the bending light
Showing the effect in motion

Please like and share this post if you found it interesting!

How computers represent negative (integer) numbers

I’ve discussed how computers represent numbers in binary and how binary numbers work in my post Basics of Binary. Check it out of you get lost when I talk about binary numbers. Like with that post, I’ll prefix any binary numbers with “0b” to avoid any potential confusion.

The Problem

Computers store their data in the form of binary numbers where 1’s are represented by high voltage and 0’s by low. When we talk about negative numbers and use them in calculations done by hand we usually use the “-“ negative sign to differentiate them from positive numbers. Unfortunately, we have no way of easily differentiating negative and positive values by just a sign as we are limited to 1’s and 0’s. Perhaps the most obvious potential solution would be to append a “1” before our number and have it act as a sign like so: 0b00000001 is equal to 1 in our system and 0b10000001 is -1 in our system, if we’re using 8 bit numbers. This isn’t a terrible solution, but it does come with a set of problems. The biggest of these problems is that it is not complicated to perform operations using these numbers. From our human perspective, we are able to quickly determine if a number is negative and treat is like such. The process of adding two numbers in our system would go as follow for a human:

  1. Add 0b00000001 and 0b10000001
  2. Translates to, Add 1 and -1.
  3. Solution is 0 or 0b00000000

Now for a computer:

  1. Add 0b00000001 and 0b10000001
  2. Check each number to see if they are positive or negative
  3. Second number is negative, convert to positive number
  4. Subtract 0b00000001 from 0b00000001
  5. Solution is 0b00000000

The biggest problem with this is that on the computer side there are significantly more steps than what adding two numbers should take, which is essentially a one step operation for a human and would be for a computer if only positive numbers were considered since digital circuits can be designed to add and subtract two numbers in one operation. There’s got to be a better way.

How negative numbers work

Understanding how negative numbers work is key to developing and understanding a better solution for representing negative numbers in binary. Negative numbers for the most part are exactly the same as positive number except for their distance from zero is in the opposite direction as positive numbers. This is best explained with a number line.

By working out 3 + (-2) this way, the difference between positive and negative numbers can be represented visually.

The solution

Another thing that needs to be considered to arrive at a good solution to this problem is that computers represent numbers in binary values of a fixed length. For our example we’ll say our computer represents numbers in 8 bits (1 byte) meaning the largest binary number that can be stored in a single unit of memory is 0b111111111 or 255. The key to this whole puzzle is understanding what happens if we try to store a bigger number than that. I like to think of this concept as sort of like an odometer you’d find in a car. Each bit of your byte is like a wheel in your odometer and when it rolls over from 1 to 0 again, the wheel on the left also rolls to its next value. Like so:

The most interesting aspect about this, for our concern, is the second case where the whole odometer is rolling over. We have a number 0b11111111 that, when 1 is added to it, we get 0b00000000. Essentially, we have some number that when added to 1 is equal to zero. Using our knowledge of how negative numbers work, the only possible value for that number is -1.

Can we get this to work with other values? If 0b11111111 is equal to -1 and negative numbers have a distance from zero opposite that of positive numbers, -2 should then be 0b11111110 as it has a distance of 2 to zero. If we add 0b00000010 (2) to this, we get 0b100000000 dropping the highest bit since we can only store 8 bits, we get 0b00000000 or 0. It works!

This is the concept of the 2’s compliment method of representing negative numbers. This works very well as this method is truer to how negative numbers actually behave compared to our previously devised solution of using 1 as a sign and allows us to perform addition and subtraction on computer hardware in only one step. The steps for converting a positive number to negative in 2’s compliment is as follows:

  1. Take the NOT of your binary value (ex. 0b00000010 -> 0b11111101)
  2. Add 1 to the result (ex. 0b11111101 -> 0b11111110)

Something interesting to note is that the highest bit still lets us know the sign of a number, if it is a 1 the number is negative otherwise its positive. Therefore, the largest positive number we can represent in 8 bit 2’s compliment is 0b01111111 or 127 and the largest negative number is 0b10000000 or -128. Notice that we have fewer positive numbers than negative numbers we can represent, this is because the value of 0 (0b00000000) takes up a spot from the positive numbers.

Be sure to like and comment if you learned something new or found this interesting and follow my blog to be notified when I make new posts!