0
$\begingroup$

This is a naive question, but what makes binary representation special from a theoretical standpoint and from the standpoint of information theory?

If for technical reasons building ternary computers where the information is encoded as trits was easier than building traditional binary computers, I get the feeling that most theoretical computer science and information theory would still use bits and base-2 representation by default.

Even if I have an intuitive feeling of why, I would have liked to know a formal explanation of that: from a purely theoretical standpoint what makes bits and binary representation special compared to any other base?

If the answer is more complex than one may first think, links to books and scientific papers are welcome.

$\endgroup$
2
  • $\begingroup$ cs.stackexchange.com/q/27656/755 $\endgroup$
    – D.W.
    Nov 17, 2019 at 7:27
  • $\begingroup$ Information theory doesn't care about bits at all. Theoretical computer science cares about them mostly because it's the simplest setting. $\endgroup$ Nov 17, 2019 at 12:36

2 Answers 2

1
$\begingroup$

Well, the fact is that binary values are much easier to handle technically that ternary values. And there are reasons for it. So if there was some technical breakthrough where suddenly ternary values become easy to handle, there would be a good reason to believe that binary values would have a similar breakthrough very soon.

So yours is a purely hypothetical question. And you are making assumptions about how people would react in a purely hypothetical situation.

In lots of situations, for many algorithms, binary or ternary doesn't matter. At a high level, we just talk about integers. But for many basic operations, ternary is at a disadvantage. Design a format for signed integers. Preferably one where the same representation is used for positive signed integers and for unsigned integers. You have a problem unless you use one trit and use it as a sign bit. Which means you now have a representation where not every trit value is valid.

Floating-point arithmetic: I don't remember if it was Knuth and Kahan who showed that "round to nearest even" has some very nice properties, and then showed that you have these nice properties whenever the floating-point base is 8k + 2 (including binary and decimal, what a luck) but not for base 3.

Design the logic for a full-adder. Two inputs from 0 to 2 and one input 0 or 1 (the carry from the previous operation). Quite complicated. Much much more complicated than binary. Going one level down, is there anything like NAND and NOR for trits that can serve as the basis of all logical operations? Try creating a fast multiplier. For binary, the basis for this is an operation which produces x*0 or x*1. Now you need something that produces x*0, x*1 or x*2. Wait, that can't be stored in a single trit. Trouble. Plus you can't use the ordinary full adder to finish off the fast multiplier.

$\endgroup$
0
$\begingroup$

There are two parts to the answer.

One part is about how computers are designerad internally. There is altardy a good answer to that.

The other part is about information theory. In information theory the unit is bits.

$\endgroup$
2
  • $\begingroup$ That doesn’t answer the question. Why is the unit a bit? Because we are used to it, or because there is a reason? BTW Your SSD drive doesn’t store bits. Your broadband connection doesn’t transmit and receive bits. $\endgroup$
    – gnasher729
    Nov 19, 2019 at 7:32
  • $\begingroup$ Look up Shannon information entropi from 1948. This is the fundamentals of information theory. One bit answers one question Yes/No. $\endgroup$
    – ghellquist
    Nov 19, 2019 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.