I recently developed two android apps to help my colleagues and I at HTGF manage our large portfolio and investor network. The apps are pretty simple, just a search field and a list of results, with the relevant information displayed when you select a contact or startup (contact details, company history, etc). The problem was, I planned to import both the contacts and the portfolio list SQLLite databases, but each had so much information that the resulting DBs were about 5MB each.
Android compresses Resources and Assets in order to make the resulting APK smaller, but it imposes a 1MB limit (I’ve heard this is larger now) to what it will compress. Any file larger, and the Android Asset Packaging Tool (aapt) refuses to compile/build the APK.
For most developers, this is not a big deal, since typically you wouldn’t want to have that size Assets anyway since you’d preferably keep the DB up to date on a server and have it update the App information when called. But there were two problems with this for our internal use-case: i) we wanted it to work offline, and ii) for data security reasons we weren’t going to put any confidential startup information on an internet-accessible server (the security audit would have been so much work we’d have rather just not had the app). So installing the DB as an Asset within the APK on the initial installation was the only way to go.
I eventually discovered that there are some file types which aren’t automatically compressed during the build, specifically files that have already been compressed or do not compress easily. “.JPEG” is one such file, so the easy solution was to rename the SQLLite DB to “database.jpeg”, since SQLiteOpenHelper doesn’t care what the file is called so long as it’s consistent.
Since then, I’ve been able to use much larger assets simply by called them X.jpeg instead of their normal extension and aapt assumes they are already compressed files. No problems, they are simply built into the APK as is!
After previously building the NAND, Full Adder, Full Subber, and Comparator, I felt ready to tackle the Arithmetic Logic Unit (ALU). Since I’m not certain exactly what opcodes and microcodes I’ll be implementing later, I wasn’t sure which functions to include in the ALU. Working off of the list of operations from the 16 bit ALU from Warren’s Microcoded CPU, I decided on the following 20 operations: addition, subtraction, multiplication, division, remainder, negation, greater than, equal to, less than, AND, OR, NAND, NOR, NOT, XOR, Logical Shift Left, Logical Shift Right, Logical Rotate Left, Logical Rotate Right, and Arithmetic Shift Right. There are some extra slots on the MUX available in case I need to go back and add some operations later.
There’s a flag output for carry_out and borrow_out from the addition and subtraction operations. I decided against including the in and out flags for the multiplication operation for simplicity’s sake and may need to come back and include that later if the micro-codes require it.
(Click on image for higher resolution version).
8 Bit ALU
Now that we have 1 bit of memory, it’s pretty simple to build that into something more useable. By putting 8 D Flip Flops together we get 1 byte of memory. If we double that and add an address bus, we get 2 individual bytes of addressable memory. I could go on but I think two bytes is enough to demonstrate usage of both the data and the address buses.
The address bus is simply 1 bit in this example. 0 means we’re addressing the top 8 bits of data, 1 means we’re addressing the lower 8 bits of data. Doubling this and having 4 lines means 00,01,10,11 or 2 bits of addressable memory, each of which is 1 byte (8 bits).
Typically you would control the read/write* with only 1 bit: 1 means read, 0 means write, but for clarity I have two data buses here: one for input (the 8 bit bus on the bottom of the diagram), and one for output (the 8 bit bus on the top of the diagram).
On the bottom left I have some non-relevant components that I used for testing the 2 bytes of memory. The clock is obviously necessary, but the rest are: a Logisim random number generator (8 bits) to fill the addressed 1 byte of memory for testing, and a 8 bit LED output for testing the output data bus. There are 3 1-bit controls: an on/off for the clock signal, the read/write* control bit, and the 0th / 1st byte switch for testing the address bus.
2 Bytes of RAM from D Flip Flops
For anyone familiar with flip flops, persistent memory in circuits can be achieved with arrays of flip flops (typically clocked D circuits).
For my circuit I’m taking 6 NAND gates (all but one with 2 input values, and 1 with 3 input values) and co
mbining them with the clock for a D Flip Flop / 1 bit Memory circuit.
D Flip Flop Circuit / 1 Bit Memory
To simulate a home-brew computer from the smallest discrete components, I’ll start with transistors, resisters, and a clock signal. We could go smaller and make the clock from a RLC network (resistor, inductor, and capacitor in series), but that would require a simulator other than Logisim. While there are several methods of going from transistor to gate, my example is based on Resistor-Transistor Logic.
Since it’s possible with De Morgan’s laws to change any NOR to NAND or NOT and vice versa, I’m limiting this exercise to only NAND gates (it’s also easier with the transistors I’m simulating).
NAND Gate from NPN Transistors
Since Logisim doesn’t have components for resistors, instead of coupling resistors to the ground and power sources (necessary to avoid shorting the wire if both transistors are allowing current), I am instead connecting a pull-up transistor as the source and a pull-down transistor as a sink. The transistors used were NPN type (and while I don’t think it makes a difference from a logic standpoint, the icon implies they are MOSFET).
Running through the truth table for a NAND gate confirms the above circuit.
You might be wondering why we don’t just connect power and ground instead of the pull-up and pull-down resisters. It’s because doing that would short circuit the network if both gates were allowing current, since it would flow directly from the power source to ground. Not only is shorting bad, but it gives an error as output, since it’d be a floating (unknown) value. Using the resistors ensures that the output value is either pulled high to True or low to False in all scenarios.
I recently discovered Logisim, and incredibly powerful discrete logic simulation program. It’s free and open-source. For such a simple program it’s incredible what it can do, from simple simulations of gated-logic all the way to components of ROM (into which you can save opcodes for a program) and RAM. It even has keyboard and TTY simulation support.
I’ve always been fascinated by how a modern computer is built from the most simple components. Transistors and clock signals can grow into something programmable. In college we had fun with FPGAs but I find there’s something magical about making non-programmable circuits into something programmable.
Over the coming months I intend to build a computer from discrete logic components, starting with transistors and moving up as far as I can with Logisim. Lots of people have done this, so it’s nothing new, but I find the discovery process will be helpful for my understanding of how computers come together. I may even breadboard the final design once it’s complete and have my own home-brew computer!
Home-brew Computer Step 1: Transistor to Gate Logic
Home-brew Computer Step 2: Gate Logic to Memory
Home-brew Computer Step 3: D Flip Flop to Memory