Talk:Four bit adder

Cleanup

Some things that ought to be cleaned up in the description of this task:

Provide some math notation describing the individual gates; that will be of some use to those not accustomed to thinking in schematic gate logic.
(Maybe?) individual images per-gate. Replace mentions of specific gates with their symbol, or...
Make gate-specific usages of the words AND, OR, NOT, XOR and their negated counterparts consistent in terms of capitalization and style.
My embedding job for the images isn't particularly stable, wrt coexistence with the pre blocks, but I don't have time atm to do a nice table for them. Whoever does...thank you? :)

--Michael Mol 13:51, 15 June 2010 (UTC)

Indeed I did the images thinking to describe the task more in a visual way instead of sticking to notation only...! ;; linked wikipedia gates page to avoid to have to do other images:D, I could add a little "lecture" about boolean notation and gates, but I suppose there must be a limit ;; more easily doable, I will do it (later);; --ShinTakezou 16:48, 15 June 2010 (UTC)

The images push down into the following code, which looks wrong. I think that entry headers should get the {clear: both} style? --Rdm 16:52, 15 June 2010 (UTC)

I can try that. It's going to slow the site down some to edit that particular template, though! Just beware... --Michael Mol 17:33, 15 June 2010 (UTC)

That did not seem to help, for me (I am using Chrome). Perhaps because the style is on a <span>?

http://www.blooberry.com/indexdot/css/properties/classify/clear.htm says that css2 says that clear:both only works on block elements. So I made myself a local copy of the page (setting the base href so it still worked), and the images stopped overlapping the text for the C entry when I changed the raw html so it looked like this: <div class="mw-headline"><div style="clear:both"><a href="/wiki/Category:C" title="Category:C">C</a></div></div>

That is still not great, but maybe its a starting point? --Rdm 18:06, 15 June 2010 (UTC)

Not likely to work well; the div would need to be made flow-inline, to avoid breaking the header, and that would in turn break clear-both again. The best solution for this particular page (at least for the moment) is to put the images in a table, instead of off to the side the way they are. I don't have time to much with it, though. I'll revert Template:Header and let someone get the table working properly. --Michael Mol 18:10, 15 June 2010 (UTC)

I put an empty div with clear:both at the bottom of the introductory section. That should be good enough for now. --Rdm 18:13, 15 June 2010 (UTC)

Accidental reversion

Don't worry about the reversion of the C example. It can be brought back after the page activity has settled down a bit. I don't know why MW didn't warn Mwn3d about the intermediate change, but I'm not worried about it. --Michael Mol 17:55, 15 June 2010 (UTC)

Anyway restored back sather impl adding to the current (after reversion) version; it could be I need a rest --ShinTakezou 17:56, 15 June 2010 (UTC)

I think it didn't warn me because it was also warning me about new messages on my talk page? Sorry anyway. It looks like it was just comments so that's not as bad. --Mwn3d 18:07, 15 June 2010 (UTC)

Extra long, educational version of the task (draft)

I was thinking about making the task description better. This draft likely is too long to be suitable; maybe also too much educational, even though still "incomplete" someway. I don't dislike it totally however. Suggestions? --ShinTakezou 17:21, 16 June 2010 (UTC)

Preface

It is often said that computers "understand" 1s and 0s. Indeed, the digital electronics that makes them to work is (as the word digital suggests) a two-state elettronics (we won't talk here about the need for a "third" state and the fact that resistors, capacitors, inductors are present of course).

Seen at the lowest level (but not so low that we can see the physics behind the scenes) we can say that every digital circuit consists of elements able to do operations on 1s and 0s (we call these two possible states bits from now on). The most basic operations correspond to the one we already know from the boolean algebra (we can interpret the two possible states also as true and false). So, the possible operations are e.g. not , and, or, exclusive or (xor)... and several others that however can be rewritten in term of the previous one.

For each of those operations we can imagine it exists a hardware component, that we call logic gate or simply gate, able to perform them. So the most elemental gates are NOT, AND, OR, XOR.

 These images (except Xor) are not ready

NOT	AND	OR	XOR
NOT gate			XOR gate

We imagine that these are "binary" gates, accepting two inputs and yielding one output, save for NOT which is an unary gate: it has an input and an output. At each input and output corresponds a pin. Commonly gates are packaged together into a single package, containing e.g. four gates, and they exist also chips that "implement" a N-input OR, AND... However these can be done using several gates in their binary "version", so we don't consider them elemental.

Indeed considering the De Morgan laws and other amenities from boolean algebra, we can see that our set of gates is still not really the minimal elemental set of gates. The discussion about which gates can be considered elemental should not ignore how these gates are created in hardware using "transistors", and the fact that a single purposely chosen gate is all we need to create our circuits.

For example, the NAND gates is a gate similar to the AND, but the output is inverted (noted). All the other gates can be realized using this single gate! So that the minimal set of elemental gates can contain just one element, e.g. the NAND, but the NOR can be used similarly (see for example this link, that shows how a CMOS NAND and AND are realized and how they work; observe that the NAND has 4 transistors while the AND needs six transistors).

But since we are interested in a certain degree of comfort, we shall build the schematics for our circuits using several not-so-elemental gates. We shall consider only three gates (NOT, OR and AND) as "elemental".

We can easily imagine that a complex digital circuit, if explicitly written in terms of gates NOT, OR and AND, can become rather hard to be understood and maintained. Exactly how it happens in programming, it is comfortable to build "functional" blocks, containing other (interconnected) functional blocks, containing other functional blocks... until we reach the most elemental blocks that can be "described" only in terms of elemental gates.

More complex "blocks" can be "analitically" described using truth tables: for each possible input, we write the output(s). From this table it is easy to write one (or several) analitycal expression(s) that then can be simplified and used as model to implement the block using the usable gates. We shall use as notation a + for or, the product sign · for and (or nothing: A·B = AB, inheriting mathematical conventions), a bar over a symbol or a group of symbols as not; the $\oplus$ (being a xor) will be considered as a shortcut for ${\overline {A}}B+A{\overline {B}}$ , i.e. for the xor written in terms of and, or and not.

One of the most simple but useful "block" we can imagine is the one able to sum two bits. The block has two input pins (let us call them A and B) and two output pins (let us call them S and C, we'll understand later why). Using the binary numeric system, we know that

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10

The last line, in particular, can be read the following way: one summed to one gives 0, with a carry of 1. So the two inputs are the addends, while first output pin is the result of the Sum, and the second pin is the Carry. The carry is 1 only when both input are 1. If we study the truth table of the logic and (which is realized in hardware with an AND gate), we see that its "output" is true (1) only when both inputs are true (1). So we can write:

C = AB

Let us now study the S bit we find on the output S pin of our block. It is comparable to the truth table of the xor and so we can say that

S = $A\oplus B$

The expressions for C and S, given A and B, describe our adder. This is called indeed half-adder. Now let us first see how easily these two expressions can be "transformed" in a digital circuit schematic, using for the gates the symbols already seen above.

We can consider this as a fuctional block of its own, and later we'll be not interested anymore in its inner details: we know its function, and we'll use it as a "black box".

The limit of a half-adder is that it can't be used to sum more bits. If we go into the process of summing two binary number by hand, exactly as it happens while summing two base-N numbers, we soon find that we need to sum not only two digits of the same column, but also the carry from the previous column. So, to fully be able to sum two bits, being these part of numbers consisting of more than one digits, we should have a block that accepts three inputs: two for the addends and one for the carry from the previous "column".

At this point we could build our truth table for these three inputs and two outputs, find our two expressions for outputs S and C and simplify them, and use them to build the block that we can call full-adder.

But we have already "half" of the function we want, and so let us use it. The half-adder is not able to "recognize" the source of its inputs. So let us connect the S-output of a half-adder (Left) to the A-input of another half-adder (Right); now the S-output of HA-R is the sum of its A and B inputs, but A is the S-output of HA-L, i.e. it is the sum of two bits. Thus, we can be easily convinced of the fact that the S-output of HA-R is the sum of three bits. We have still two C-outputs from the half-adders, that we would like to combine so that the final carry is the correct one expected from the sum ot three bits.

These two carries can be combined using an OR (we could have used also a XOR, but since for us this is not elemental, we should avoid it). Explaning this is a little bit "tricky", but we can do an empirical check looking at the truth table.

Indeed, full-adders are not realized using two half-adders and an OR, since there's a more cheap way of doing it. However this approach is more clear.

Since the full-adder is able to sum also a carry from a previous stage, it can be easily used to implement an adder for more than two one-bit numbers. If we want to sum two N-bits numbers, we need simply N full-adders: each full-adder sums the n-th bits from the two input "numbers", plus the carry from the sum of the previous (n-1)th bits; therefore we can call the inputs of a full-adder A_n, B_n, C_n-1 and the outputs S_n and C_n. Since the unity bits can't have a carry, the carry input of the "first" full-adder (the one summing the unity bits) is set to zero. Moreover, the last carry (the carry of the last full-adder, the one summing the Most Significant Bits) can be used to know if there was an overflow.

References

Wikipedia (inline links)
J.Millman, A.Grabel Microelectronics (McGraw-Hill)

Task

Using only AND, OR and NOT gates (simulated by the bitwise logical operators of your language), create the following functional block (from bottom-up)

XOR
Half-adder
Full-adder
4-bit adder

The XOR gate, once described in terms of AND, NOT and OR, can be used the same way of the other elemental gate, i.e. as an existing bitwise operator.

As it can be seen from the image, the 4-bit adder has 8 inputs (4 per input "number") and five outputs: 4 are the result of the sum, while the last is the overflow bit.

Solutions should try to be as descriptive as possible, making as easy as possible to identify "connections" between higher-order "blocks". It is not mandatory to replicate the syntax of higher-order blocks in the "elemental" gate blocks, i.e. elemental gate operations can be performed as usual bitwise operations, or they can be "wrapped" in a block in order to expose the same syntax of higher-order blocks, at implementers' choice.

In order to test the 4-bit adder, write a test code to sum two 4-bit numbers: set the eight input bits to certain values and show the five output bits.

It's interesting, but I see two problems.

Full treatment of the task subject outside of software is outside Rosetta Code's domain. A brief explanation, with a link to someone else's full treatment, would be more appropriate. Alternately, you could treat gate logic as its own language, and apply implementations for things like mathematical operators and logic, and through sufficient examples describing those, provide for a full treatment via intra-site linking.
Where did all that text come from? --Michael Mol 17:28, 16 June 2010 (UTC)

Could I write that outside (e.g. on my capo-nord/soci/xmav) and provide a link then? (In case it would be useful for hardware unaware people to dive in the POV that allowed some implementers to use words like Wire, GND and Bus, catching someway the "hardware" PoV I liked for ths task)
From my fingers. Parts of the explanation are excerpt of stuffs I started to write (in italian) for an old educational course about "informatics" (since my idea was/is that without having an idea about how computers do their things, one could find harder to understand some concepts that could "emerge" even from everyday usage by non-programmers who usually just "click" on the right place) --ShinTakezou 17:39, 16 June 2010 (UTC)

Forgot the most important note for the point 2: the course was never completed nor released; even if it were, the license would be a CC non-commercial sharealike (compatible to RC one I suppose), or GFDL. ShinTakezou 17:43, 16 June 2010 (UTC)

How about Four bit adder/Indepth for supplementary details? Something over in the Encyclopedia area might work, too.
Ah. Sorry; I was just a bit suspicious, because your English isn't usually that good, and the text showed up pretty quickly. >.> --Michael Mol 17:44, 16 June 2010 (UTC)

I think I will do that if it seems useful to people, otherwise is the Task part only better than the current one? (Adding tiny bits —but what exactly...— from above?)
It is what I am doing from this morning (with pauses of course), with emacs and translate.google as dictionary to enlarge a bit my used lemmas set,... so it was not so quick! Subsequent edits show that I should use more the preview button anyway :D --ShinTakezou 18:11, 16 June 2010 (UTC)

Hi Guys,
Wouldn't this be better off in the Category:Encyclopedia (sic) section?
P.S. my spell checker says it should be encyclopaedia with an ae). --Paddy3118 05:00, 17 June 2010 (UTC)

With an “æ”? Yes, but a lot of people have problems typing such things and US dictionaries are slipping towards using a plain “e” in those locations. Sic transit gloria mundi. –Donal Fellows 12:52, 18 June 2010 (UTC)

Motivations behind the task (and point 1 (RC domain))

My idea when I've created this task was to begin something I've never started but that was in my mind since eons: implementing a small microprocessor. I know they exist languages like VHDL and Verilog (that by the way are on RC too, and this task should be suitable for them!) and more, but I would like a standalone software, and not to be too much hardware-design bound; i.e., I want an emulator, that emulates the innermost hardware in a lowlevel way, but "outside" behaves like a software emulator (I doubt Bochs and similar do their emulation so "low-level")

I don't know the exact "extension" of what languages like VHDL can do, but once I tried SPICE and it did not grasp my attention as a suitable tool for my idea.

The four bit adder was a pilot test for more similar task (if this sort of tasks are suitable for RC domain, being a little bit hardware-related) (e.g. I discovered on the run that ideas in the Go implementation, according to what I can understand of Go, can "model" a latch, while C impl can't) ... --ShinTakezou 18:48, 16 June 2010 (UTC)

It sounds like something on the scale of RCRPG/RCBF/RCSNUSP, and it has its own kinds of interest. I'd say go ahead and try it, but don't use Template:Task for it, at least not soon. I'd suggest you first try modeling the basic gates (including allowing XOR to be done natively), then extend to half adder, full adder, flip-flops, etc. I noticed you didn't account for the possibility of clocks and/or propagation. (I thought of doing a C++ example that had a Clock() method, for example.)

Find a corner of the wiki and see what you come up with; there are obviously already some HW-savvy folks around here, and maybe you'll come up with something that can be incorporated/adapted/fit with the wiki in general. Also, let me know if you come up with a gate-logic implementation of BF. My step-dad was interested in doing that a while back. ;) --Michael Mol 18:57, 16 June 2010 (UTC)

The idea as whole is enough large to be in the project category. Constructive blocks however are simple task of their own (task used in the general way, not as "RC task"); having a library of these blocks should then make it simpler (!) to realized the final project.

Indeed, as the "4-bit adder" task was done, it proved to be badly planned. The general way I set up things do not allow for all the needed things to do all kinds of circuits needed for the final project. E.g. as I did both C and Sather impl can't describe a latch at all, even expanding to allow a clock; deeper thoughts made me believe Go too could have problem, putting the program in a never-ending wait for ready signal, but I didn' analyse it further.

As already said, my aim is not to build things too much hardware-design bound. But I am realizing that maybe some "real" simulation trick must be used sooner or later (again, latch ... I'll be going to experiment on my own before saying more, but I vaguely see they can be problematic in a straightforward approach). Being curious to answer the question "is this idea not new?", I searched the net and of course I've found already done stuffs, but as real hardware design (e.g. the harp project, and YASEP), very interesting for anybody interested in.

I think the "processor" can have as instruction set BF, with the understanding that . and , can interface the cpu to any suitable device (that must be projected purposely) and likely more instructions for jump could be useful to augment performance (the [ needs look-ahead and a [-stack ...). Currently my ideas about how all this can be realized are rather foggy; however I've installed some VHDL tools, going to see how this task would look with it. -ShinTakezou 10:36, 17 June 2010 (UTC)

For a latch, two nor gates with their outputs cross-wired to the other's input should be sufficient? You do need to represent their "previous state", which complicates things, but I do not think you need additional logic? --Rdm 12:20, 17 June 2010 (UTC)

By "definition", it can be done that way. But note that C impl is sequential, so it is not possible to use as input an output produced later; on the other hand, about Go, it seems it would wait for the input to be available... the problem could be that one input will be not available until the output is generated, and it is not generated since both gates will be awaiting for a value to be set in the connection. What does it happen if a random value (0 or 1) is set preliminarly as output for the NOR gates? Does the simulated latch becomes "bistable" as it happens in reality, or rather it will expose a wrong (to be analysed) behaviour? It is of course implementation specific and can be fixed, but current implementation and in particular my sequential approach to the "description" of the circuit does not help. --ShinTakezou 18:23, 17 June 2010 (UTC)

I was thinking of something like this: <lang c>#include <stdio.h>

typedef char pin_t;

define IN const pin_t *
define OUT pin_t *
define STATE pin_t *
define PIN(X) pin_t _##X; pin_t *X = & _##X;
define V(X) (*(X))

/* a NOT that does not soil the rest of the host of the single bit */

define NOT(X) (~(X)&1)

define NOR(X,Y) (NOT((X)|(Y)))

void latch(IN a, STATE b, STATE c, IN d) {

 V(b)= NOR(V(a),V(c));
 V(c)= NOR(V(b),V(d));

}

int main() {

 PIN(p0); PIN(p1); PIN(p2); PIN(p3);
 V(p0)= V(p1)= V(p2)= V(p3)= 0;

 int j;
 for (j= 0; j < 16; j++) {
   int bit= 4&j ?1 :0;
   V(p0)= 1&j ?bit :NOT(bit);
   V(p3)= 2&j ?bit :NOT(bit);
   if (V(p0) && V(p3)) continue; /* forbidden case */
   else if (V(p0)) printf("%d\tset\t", j);
   else if (V(p3)) printf("%d\treset\t", j);
   else printf("%d\t\t", j);
   printf("%d%d%d%d\t", V(p0),V(p1),V(p2),V(p3));
   latch(p0, p1, p2, p3);
   printf("%d%d%d%d\t", V(p0),V(p1),V(p2),V(p3));
   if (V(p2)) printf("is on\n");
   else if (V(p1)) printf("is off\n");
   else printf("is switching\n");
   printf("\t\t");
   V(p0)= 0;
   V(p3)= 0;
   printf("%d%d%d%d\t", V(p0),V(p1),V(p2),V(p3));
   latch(p0, p1, p2, p3);
   printf("%d%d%d%d\t", V(p0),V(p1),V(p2),V(p3));
   if (V(p2)) printf("is on\n");
   if (V(p1)) printf("is off\n");
 }
 return 0;

}</lang> --Rdm 21:05, 17 June 2010 (UTC)

P.S. note that that latch function really needs to be run twice to reach steady state. However, because I made one gate faster than the other, this is only apparent some of the time. --Rdm 13:28, 18 June 2010 (UTC)

This is interesting, I will reconsider the whole topics once healed by failing with vhdl quick-attempts with found free (as in beer and as in speech) tools... --ShinTakezou 17:47, 28 July 2010 (UTC)