The Naked Scientists

The Naked Scientists Forum

Author Topic: How efficient is binary?  (Read 11773 times)

Offline Mr. Scientist

  • Neilep Level Member
  • ******
  • Posts: 1451
  • Thanked: 2 times
  • http://www.facebook.com/#/profile.php?ref=profile&
    • View Profile
    • Time Theory
How efficient is binary?
« Reply #25 on: 16/09/2009 01:24:20 »
Jason Fong asked the Naked Scientists:
   
Hi Chris,

As we all know the standard qwerty keyboard layout is rather inefficient, error prone and slow. After all in school we learn that it was designed to slow down "typewritists".

After stumbling into the dvorak keyboard layout whilst trying to increase my characters per minute typed, I suddenly began to question the efficiency of codes such as binary.

Is binary inherently the most efficient way of representing any set data using two states? Or is it just efficient in conveying a set number of characters?

Or should I be asking about the efficiency code which is written in binary?

Also would the complexity of computer code increase linearly or exponentially as we hopefully in the future mature into quantum computing?

Perhaps binary is only efficient for linear calculations, I read that quantum computing will allow multi threaded algorithms, such as the ones used to calculate large primes, to run much faster/efficiently.

What do you think?

It  is very essential when loging valuated matrices. In fact, the entire universe can actually be composed of zero's and one's - but this would be a universe in it's most simplistic format without the need of the complexities. However - i believe the universe will not allow us to understand such complexities, or reduce it so easily. Concerning computers... well, it's necessery. Even when qubic forms are produced as a superpositioning.
 

Offline Mr. Scientist

  • Neilep Level Member
  • ******
  • Posts: 1451
  • Thanked: 2 times
  • http://www.facebook.com/#/profile.php?ref=profile&
    • View Profile
    • Time Theory
How efficient is binary?
« Reply #26 on: 16/09/2009 02:41:29 »
http://www.oilanalysis.com/article_detail.asp?articleid=597

Please don't tell me this is vernon from the site here?

 [V]
 

Offline graham.d

  • Neilep Level Member
  • ******
  • Posts: 2208
    • View Profile
How efficient is binary?
« Reply #27 on: 16/09/2009 08:56:28 »
Ternary can be used in computing though we are not really used to thinking in this way. I have a suspician that it would have been quite hard to think of the design of a multi-bit adder in binary for the first time (a cascade of full adders with carry) and 2's complement arithmatic is not all that obvious. The problem with ternary is that detecting 2 states (high or low) is easy in electronics but a third state would demand some sort of window comparator or, alternatively, running 2 lines from every output. So basically binary is well suited to mapping on to the hardware and efficient in terms of silicon real estate.
 

Offline LeeE

  • Neilep Level Member
  • ******
  • Posts: 3382
    • View Profile
    • Spatial
How efficient is binary?
« Reply #28 on: 16/09/2009 12:17:33 »
Lol  :D - it's only just occurred to me to check wikipedia...

http://en.wikipedia.org/wiki/Ternary_computer

 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #29 on: 16/09/2009 16:35:37 »
Groan! I found the ternary links on Wiki last night too, but I was trying to keep it quiet  :)

Here's an idea: You can build any arbitrarily complex binary logic system from one simple logic element, for example, a two input NAND gate.

Sooooo, "all" we have to do is figure out the ternary/trinary equivalent of the simple nand gate, and we ought to be able to design any logic system we want - piece of cake!
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #30 on: 17/09/2009 03:03:16 »
Ternary can be used in computing though we are not really used to thinking in this way. I have a suspician that it would have been quite hard to think of the design of a multi-bit adder in binary for the first time (a cascade of full adders with carry) and 2's complement arithmatic is not all that obvious. The problem with ternary is that detecting 2 states (high or low) is easy in electronics but a third state would demand some sort of window comparator or, alternatively, running 2 lines from every output. So basically binary is well suited to mapping on to the hardware and efficient in terms of silicon real estate.

GrahamD,
The electronics would be rather challenging as you say, but I suppose it could be done if there was sufficient incentive. I can pretend to myself that I can almost understand how arithmetic operations might be carried out, perhaps because it's not difficult to check that the result of any arithmetic operation is correct. What totally defeats me are many of the logical operations. I think we will need a whole new set of tools because things like K-Maps assume binary states. For example, what would an XOR even mean in trinary? We would need to define some new rules for trinary logic.

Now here's the scary part:

It is necessary for me to reduce logic designs to rather fundamental terms, but that is only because I was trained to do that. At one time, logic gates were quite expensive, so I was conditioned to optimize a design to minimize the number of gates used. Not so the digital engineers of today. They don't think in terms of gates. They don't think in hardware terms at all. They think in terms of expressions and data transfers. These days, digital systems are expressed entirely in software terms.

Today, the only things that really matter are:
How large is the die? (chip size)
How much power does it consume?

So, assuming the hardware guys can devise a robust trinary implementation, the tool designers could create a set of tools that will allow the system designers to produce systems that operates on trinary, but nobody would even know the difference.

(Except the poor guys and gals who have to figure out what's going on when it does not work as expected.)
« Last Edit: 17/09/2009 03:11:02 by Geezer »
 

Offline graham.d

  • Neilep Level Member
  • ******
  • Posts: 2208
    • View Profile
How efficient is binary?
« Reply #31 on: 17/09/2009 11:10:34 »
Yes, Geezer, you are right. It would mean a lot of hard work for the CAD vendors though. Cadence, Mentor, Synopsys, Magma etc would have to do a lot of work for their money :-) Perhaps there would have to be a new expanded set of RTL instructions too. Logical operations could still be binary but arithmetic could be ternary. I can't see it catching on very quickly, though. In theory, it is about 50% more efficient in terms of states to be saved but the structures needed to save those states are probably more complex by a higher percentage.

Actually logical operations can be mapped on to a ternary (or any other) number system though it is not obvious because we tend to think of single logic gates. You have to consider multi-bit in (and multi-bit out) clouds of logic and then there can be a more efficient mapping on to ternary. I think this is where I would let a computer synthesise it :-)

 

Offline LeeE

  • Neilep Level Member
  • ******
  • Posts: 3382
    • View Profile
    • Spatial
How efficient is binary?
« Reply #32 on: 17/09/2009 12:49:40 »
I was wondering about how this could be implemented in 'silicon' (but I fear I may only know enough to make a fool of myself here).

The wikipedia article on Computer Memory (Random-access memory):

http://en.wikipedia.org/wiki/Random-access_memory

says...

Quote
Modern types of writable RAM generally store a bit of data in either the state of a flip-flop, as in SRAM (static RAM), or as a charge in a capacitor (or transistor gate), as in DRAM (dynamic RAM), EPROM, EEPROM and Flash.

Hmm... I'm not sure about how using charge in a capacitor is implemented in practice, but both the flip-flop SRAM and transistor gate DRAM methods are both inherently binary devices.  A tri-state flip-flop, as discussed earlier, seems to be a bit of a contradiction in terms, and I think we might need a sort of combined pnp/npn transistor to use the gate method.  It would seem then, that the individual low-level hardware elements that would be needed to implement a trinary hardware system would be more complex, as graham.d says.

Heh, while the idea of trinary seems relatively straightforward, at first glance, actually implementing it might be a lot trickier that you'd expect.  It makes me wonder how significant it is that no one appears to have made a trinary computer system since that 1950's Russian one; if it were easy, then I think it would have happened but as it hasn't, then it probably isn't.
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #33 on: 17/09/2009 16:28:38 »
I was wondering about how this could be implemented in 'silicon' (but I fear I may only know enough to make a fool of myself here).

The wikipedia article on Computer Memory (Random-access memory):

http://en.wikipedia.org/wiki/Random-access_memory

says...

Quote
Modern types of writable RAM generally store a bit of data in either the state of a flip-flop, as in SRAM (static RAM), or as a charge in a capacitor (or transistor gate), as in DRAM (dynamic RAM), EPROM, EEPROM and Flash.

Hmm... I'm not sure about how using charge in a capacitor is implemented in practice, but both the flip-flop SRAM and transistor gate DRAM methods are both inherently binary devices.  A tri-state flip-flop, as discussed earlier, seems to be a bit of a contradiction in terms, and I think we might need a sort of combined pnp/npn transistor to use the gate method.  It would seem then, that the individual low-level hardware elements that would be needed to implement a trinary hardware system would be more complex, as graham.d says.

Heh, while the idea of trinary seems relatively straightforward, at first glance, actually implementing it might be a lot trickier that you'd expect.  It makes me wonder how significant it is that no one appears to have made a trinary computer system since that 1950's Russian one; if it were easy, then I think it would have happened but as it hasn't, then it probably isn't.
I think you are quite correct. The hardware of today tends very much towards the binary. I suppose it might be possible to store positive or negative charge to store three states (pos, neg or zero) but I suspect it would be more economical to "fake it" using two bits!
It would not surprise me to learn the the Russian guy went off his rocker and had to be institutionalized. I'm pretty sure that's what's going to happen to me if I keep thinking about this topic  ;D
 

Offline Make it Lady

  • Neilep Level Member
  • ******
  • Posts: 4050
  • Hands-on fun for everyone!
    • View Profile
How efficient is binary?
« Reply #34 on: 17/09/2009 19:38:15 »
Thanks more like it boys. A sweety for all of you. I'm sure Jason is smiling.
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #35 on: 18/09/2009 04:38:09 »
Thanks Miss!

You're a sport. You can play with my conkers any time.
 

Offline graham.d

  • Neilep Level Member
  • ******
  • Posts: 2208
    • View Profile
How efficient is binary?
« Reply #36 on: 18/09/2009 08:56:21 »
Geezer and Lee, actually modern Flash memories already use multiple levels (see MLC Flash). Of course it is hard to get a high yield so there is a huge amount of error correction used but it saves a lot of chip area. It has been tried in Dynamic memories too but without much commercial success. It is hard to see how to use it in SRAM (more or less by definition). The multiple levels tend to be binary related (4, 8, 16), but this is because of the logic following will be binary. There is nothing to prevent 3 or 9 states being used.
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #37 on: 18/09/2009 17:40:44 »
Geezer and Lee, actually modern Flash memories already use multiple levels (see MLC Flash). Of course it is hard to get a high yield so there is a huge amount of error correction used but it saves a lot of chip area. It has been tried in Dynamic memories too but without much commercial success. It is hard to see how to use it in SRAM (more or less by definition). The multiple levels tend to be binary related (4, 8, 16), but this is because of the logic following will be binary. There is nothing to prevent 3 or 9 states being used.
Good point!
It struck me that it would not be too difficult to encode three states efficiently on rotating magnetic media too. The biggest challenge may be designing an efficient and reliable trip-flop.
 

Offline LeeE

  • Neilep Level Member
  • ******
  • Posts: 3382
    • View Profile
    • Spatial
How efficient is binary?
« Reply #38 on: 18/09/2009 20:49:47 »
graham.d: Thanks for the pointer to MLC Flash.  Wikipedia reckons that in practice, each cell is limited to four states, corresponding to two bits, but this does seem to be due to manufacturing and yield issues, as you suggest.

It looks like one of the main limitations is the dynamic range that a cell can cope with.  The degree of separation between levels seems to be a key factor in avoiding errors, so with a wider dynamic range, you could use more levels while maintaining the same absolute separation, or possibly run them much faster for the same density.

Have you any idea if they more susceptible to induced noise?  I'm wondering if there's a risk that induced noise could change a charge level, which would be problematic.  Yup, interesting stuff.
 

Offline graham.d

  • Neilep Level Member
  • ******
  • Posts: 2208
    • View Profile
How efficient is binary?
« Reply #39 on: 19/09/2009 21:43:23 »
There are experimental devices with 16 levels but they are very susceptible to errors and need a lot of error correction. It is also very difficult to discriminate the amount of charge stored. Even 4 levels is very challenging. There will be random noise superimposed upon the sense amplifiers when they make decisions about the amount of charge and this gets more significant as the differences between the levels is smaller. This contributes to the number of "soft" errors and the error correction software has to be sufficient to cope with it. This involves storing many more bits and having quite sophisticated error correction logic. Another interesting feature necessary for the life of Flash memories is the extensive hardware and sophisticated algorithms needed for "wear levelling". This is to spread the usage of the memory as evenly as possible as writing the same cells, as many programs would do, will cause them to fail in quite a short time. This technique extends the life considerably.
 

The Naked Scientists Forum

How efficient is binary?
« Reply #39 on: 19/09/2009 21:43:23 »

 

SMF 2.0.10 | SMF © 2015, Simple Machines
SMFAds for Free Forums