Difference between revisions of "CSC103: DT's Notes 1"
| Line 548: | Line 548: | ||
We are now coming to Shannon, who's influence on the field of computer science is quite remarkable, and whose contribution of possibly greatest influence was his Master's thesis at MIT, written in 1948. | We are now coming to Shannon, who's influence on the field of computer science is quite remarkable, and whose contribution of possibly greatest influence was his Master's thesis at MIT, written in 1948. | ||
| − | Shannon knew of the need | + | Shannon knew of the need for calculators (human beings or machines) around the time of the second world-war, (the need was particularly great for machines that would compute tables of possible trajectories for shells fired from canons). He also knew of efforts by various groups in universities to build calculating machines using electricity and relays, and also of early experiments with vacuum tubes (which later replaced the relays). Because the machines used electricity and switches, the binary system with only two values, 0 and 1 was an appealing system to consider and exploit. But there was still an engineering gap in figuring out how to create circuits that would perform arithmetic operations on binary numbers in an efficient way. |
| − | In his thesis, Shannon presented the missing link, the bridge that would allow electrical/electronic computers to perform arithmetic computation. He demonstrated that | + | In his thesis, Shannon presented the missing link, the bridge that would allow electrical/electronic computers to perform arithmetic computation. He demonstrated that if one were to map '''True''' and '''False''' values to '''1''' and '''0''' of the binary system, then the rules of arithmetic because logic rules. That mean adding two integers because a problem in logic, where assertions are either true or false. |
| + | Let's see how this actually works out. Remember the section above when we added two binary numbers together? Let's just concentrate on the bit that is the rightmost bit of both numbers (in computer science we refere to this bit as the ''least significant bit''). If we are adding two bits together, and if both of them can be either 0 or 1, then we have 4 possible possibilities: | ||
| − | + | 0 0 1 1 | |
| − | - | + | + 0 + 1 + 0 + 1 |
| − | - | + | ---- ---- ---- ---- |
| − | + | Using the rules we created above for adding two bits together, we get the following results: | |
| − | |||
| − | - | + | 0 0 1 1 |
| + | + 0 + 1 + 0 + 1 | ||
| + | ---- ---- ---- ---- | ||
| + | 0 1 1 1 0 | ||
| + | Let's take another step which, although it doesn't seem necessary, is absolutely essential. You notice that the last addition generates a carry, and the result is 10. We get two bits. Let's add a leading 0 to the other three resulting bits | ||
| + | 0 0 1 1 <--- a | ||
| + | + 0 + 1 + 0 + 1 <--- b | ||
| + | ---- ---- ---- ---- | ||
| + | 0 0 0 1 0 1 1 0 <--- S | ||
| + | | | ||
| + | +---- C | ||
| + | |||
| + | Let's call the first bit ''a'', the second bit ''b'', the sum bit ''S'', and the extra bit that we just added ''C'' (for '''c'''arry). Let's show the same information we have in the four above additions into a table, similar to the truth tables we used before where we were discussing boolean algebra. | ||
| + | |||
| + | {| | ||
| + | ! a | ||
| + | ! b | ||
| + | ! C | ||
| + | ! S | ||
| + | |- | ||
| + | | 0 | ||
| + | | 0 | ||
| + | | 0 | ||
| + | | 0 | ||
| + | |- | ||
| + | | 0 | ||
| + | | 1 | ||
| + | | 0 | ||
| + | | 1 | ||
| + | |- | ||
| + | | 1 | ||
| + | | 0 | ||
| + | | 0 | ||
| + | | 1 | ||
| + | |- | ||
| + | | 1 | ||
| + | | 1 | ||
| + | | 1 | ||
| + | | 0 | ||
| + | |} | ||
=References= | =References= | ||
Revision as of 20:02, 31 January 2012
--© D. Thiebaut 08:10, 30 January 2012 (EST)
