Anonymous user
Talk:Four bit adder: Difference between revisions
→Extra long, educational version of the task (draft): new section
(→Extra long, educational version of the task (draft): new section) |
|||
Line 25:
: Anyway restored back sather impl adding to the current (after reversion) version; it could be I need a rest --[[User:ShinTakezou|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. --[[User:Mwn3d|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?
'''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 [[wp:Three-state logic|"third" state]] and the fact that [[wp:Resistor|resistors]], [[wp:Capacitor|capacitors]], [[wp:Inductor|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 [[wp:Boolean algebra (logic)|boolean]] [[wp:Boolean logic|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 [[wp:Logic gate|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
|-
| [[Image:Not.svg|thumb|64px|alt=NOT gate]]
| [[Image:And.svg|thumb|64px|alt=AND gate]]
| [[Image:Or.svg|thumb|64px|alt=OR gate]]
| [[Image:Xor.svg|thumb|64px|alt=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 [[wp:Lead (electronics)|pin]]. Commonly gates are [[wp:Integrated circuit packaging|packaged]] together into a single [[wp:Chip carrier|package]], containing e.g. [[wp:7400 series|four gates]], and they exist also [[wp:Integrated circuit|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 [[wp:De Morgan's laws|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. Indeed 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 (''not''ed). 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 [http://tams-www.informatik.uni-hamburg.de/applets/hades/webdemos/05-switched/40-cmos/nand.html|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 [[wp:Circuit diagram|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 "''analatitically''" described using [[wp:Truth table|truth tables]]: for each possible input, we write the output(s). From this table it is easy to write one (or several)
[[wp:Canonical form (Boolean algebra)|analitycal expression(s)]] that then can be [[wp:Karnaugh map|simplified]] and used as model to implement the block using the usable gates. We shall use as [[wp:Boolean logic#Other notations|notation]] a + for ''or'', the product sign · for ''and'' (or nothing: A·B = AB, leveraging mathematical conventions), a bar over a symbol or a group of symbols as ''not''; the <math>\oplus</math> (being a ''xor'') will be considered as a shortcut for
<math>\overline{A}B + A\overline{B}</math>, 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
[[wp:Truth table#Exclusive disjunction|truth table of the ''xor'']] and so we can say that
* S = <math>A \oplus B</math>
The expressions for C and S, given A and B, ''describe'' our ''adder''. This is called indeed [[wp:Adder (electronics)#Half adder|''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.
<!-- [[Image:Halfadder.svg|center|300px|alt=Half adder]] -->
[[Image:Halfadder.png|center|alt=Half adder]]
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 [[wp:Carry (arithmetic)|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 [[wp:Adder (electronics)#Full adder|looking at the truth table]].
<!-- [[Image:Fulladder.svg|center|300px|alt=Full adder]] -->
[[Image:Fulladder.png|center|alt=Full adder]]
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<sub>n</sub>, B<sub>n</sub>, C<sub>n-1</sub> and the outputs S<sub>n</sub> and C<sub>n</sub>. 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.
<!-- [[Image:4bitsadder.svg|center|300px|alt=4-bit adder]] -->
[[Image:4bitsadder.svg|center|alt=4-bit adder]]
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.
| |||