binary
I am confuse that how carry works while multiplying two binary numbers
1111 x 1111 = 011100001
but how to handle carries in calculation? Can anyone please explain?
I know how to handle partial sum method when there are three 1s to be added while working out final result of multiplication, but I don't know, how to add four 1s in partial sum?
How carry works while adding four binary 1s in partial sum: (1)2 + (1)2 + (1)2 + (1)2
Why is binary base-2 but decimal is base 10?
This is quite a trivial question, since those are just the terms we use for those bases. It's like asking "why are humans people?"; it's just a word we use. Binary means base-2 and decimal means base-10. There's nothing complicated there.
Why do we use powers of $2$ for binary numbers?
Think about how you represent numbers (integers). It's easy for the first $10$, since we just make a new symbol each time: $0,1,2,3,4,5,6,7,8,9$. But, of course, we don't want to make a new symbol for every new number since it'd get very messy and complicated. So for the number after $9$, we start counting in a new place. So, we put a $1$ (shown in blue) in the place on the left, to get $\color{blue}{1}\text{_}$. Then, in the place on the right, we reset our $9$ to $0$ and start counting all over again (shown in red). Hence, after $9$, we get $\color{blue}{1}\color{red}{0},\color{blue}{1}\color{red}{1},\color{blue}{1}\color{red}{2},\ldots$. The $1$ that we put in the left place is called a carry. Of course, when we get to $19$, we change the $1$ on the left to a $2$ and again, reset the $9$ to a $0$. This may seem obvious, but we need to think about exactly what we're doing.
The whole point of doing this is making it simpler and easier to read numbers. With no loss of clarity, we've managed to represent every integer as a sequence of $10$ symbols. This is the system that we almost always use, and is called base-ten or decimal.
To represent bigger numbers in decimal notation, we'd keep putting a new number on the left every time we can't advance our numbers any further. Hence, $9\mapsto10$, and $99\mapsto100$ and $999\mapsto1000$ and so on. Like I mentioned before, we're carrying the $1$ in each case. What's the common feature among $10,100,100\ldots$? Well, they're all powers of $10$. Think about this, since it's important. We started with $10$ symbols (i.e. $0,1,2,3,\ldots$) but whenever we carry a $1$ (to a new position on the left), we do it at a power of $10$. This isn't a coincidence. This happens because we carry the $1$ every time we've maxed out our count in the other columns, which happens at $9$ and $99$ and so on.
This means that when we write the number $1729$, what we actually mean is $$1\times1000\quad+\quad7\times100\quad+\quad2\times10\quad+\quad9\times1$$
This shows us why base-ten is so fundamentally linked with powers of $10$, because the digits of a number tell you how many $1$'s, $10$'s, $100$'s, etc. there are in it.
In base $10$, we started with $10$ symbols. But why? Is there a special reason for choosing $10$? It turns out that no, there is no fundamental, mathematical reason to prefer $10$ symbols to a different number (say $8$ or $12$). Notice that the number of symbols is the base. There are cultural, historical and practical arguments for choosing $10$ but these aren't relevant here. In fact, the Native American Yuki People use base $8$, while the Babylonians used base $12$.
Let's say we wanted to use base $2$ for our counting (i.e. only using $2$ symbols). For simplicity, we use the first $2$ symbols we were using before (i.e. $0$ and $1$). If we were using this system, how would we count? We'd start with $0,1,???$ and then what? Well, we'd do the same thing we did before and put a $1$ to the left of our numbers. Hence $\color{red}{0},\color{red}{1}\mapsto\color{blue}{1}\color{red}{0},\color{blue}{1}\color{red}{1}$.
In fact, just like how we max out our base-$10$ count at $9$ or $99$ or $999\ldots$, etc., we max out our base $2$ count at $1_B$ or $11_B$ or $111\ldots_B$ (the subscript B indicates that these numbers are in base-2). To make this clearer, look at how we count in binary:
$$0,1,10,11,100,101,110,111,1000\ldots$$
Every time we get a number only made of ones, we carry over a $1_B$ to the left. For instance, after $111_B$ we get $1000_B$.
But when do we get $1_B$ or $10_B$ or $100\ldots_B$? Looking at these numbers in decimal form should give a clearer indication: $1,2,4,8,16,\dots$. These are the powers of $2$. Since we've only got $2$ different symbols, we max out our count after $2$ numbers or $2\times2$ numbers, or $2\times2\times2\ldots$.
Hence, base-$2$ is fundamentally related to powers of $2$. When we write the base-$2$ number $1011_B$, we really mean:
$$1\times8\quad+\quad0\times4\quad+\quad1\times2\quad+\quad1\times1$$.
Where $1,2,4,8,\ldots$ are the powers of $2$. In other words, $2^0,2^1,2^2,\ldots$
In general, for any system with $n$ symbols, when you write $31415_{\text{(base $n$)}}$, you mean the following, in base-$10$: $$(3\times n^4)+(1\times n^3)+(4\times n^2)+(1\times n^1)+(5\times n^0)$$
Hopefully this clears up why base $10$ has a sum of powers of $10$ but base $2$ has powers of $2$. It's a natural consequence of using any base.
Why do we count with base-$10$ for most things but with base-$2$ for computers
As I wrote earlier, using base $10$ for representing numbers is heavily influenced by history and society. Most often, the numbers you'll deal with in your life will be between $1$ and $200$. For example, how many years old you are, how many cars are on your street or how many eggs you ate this week. Of course, these numbers are unlikely to be massive. So it makes sense to need a base approximately $10$ since small or large bases aren't practical.
For practical purposes, base-$2$ is too cumbersome since it uses so many numbers (the number $100$ is $1100100_B$ in base-$2$) but base $1000$ is completely unfeasible since you'd need $1000$ different symbols. Can you think of $1000$ symbols that look significantly different? I can't.
Hence, we use a base around $8-16$. Some people have used $8$ before, some $12$ and some $16$. It doesn't really matter too much which one you choose. It's handy for the base to have a lot of divisors, since it lets you write simple expressions for fractions (like how $\frac15=0.2$ in base-$10$). Hence $11$ and $13$ aren't used. It's also handy to have the base divisible by $2$ so that $\frac12$ can have a simple expression. So $7,9,15$ aren't typically used. This leaves us with $8,10,12,14$ and $16$. Base $14$ isn't often used since one of its divisors is $7$, and why should we include $7$ as a divisor but not $3$ or $5$? Nevertheless, $8,10,12$ and $16$ have been widely used as bases. This rule doesn't cover every culture since even base $64$ has been used (though it needed a lot of symbols!). Also, as @ Luís Henrique points out, the mesoamerican Maya civilization used an interesting combination of base-$5$ and base-$20$ in their number system.
Other commenters have pointed out the fact that we have $10$ fingers/toes so it's easy to count base-$10$ numbers with your fingers. But this doesn't have a huge amount of bearing (in written math) since you don't often count with your fingers. As @Luís Henrique points out, this may have been much more important in more primitive societies where numbers could be communicated by hand-signs (instead of with written or spoken words), so it may give a historical basis for using base-$10$. On the other hand, computers use binary (base-$2$) since they represent numbers in electronic states (i.e. a lightbulb being on or off). It makes computers a lot simpler and easier to work with (particularly in the design and manufacture of transistors) for them work in binary. Though there have been computers that use base-$3$ (ternary computers), they are less common.
Hopefully this answers your questions.
I think you are justifiably confused. This is a poorly worded question and an obscure answer.
Let's start with the question. The main problem is the vagueness of this phrase:
every row and every column of the resulting table has an even number of ones and zeros in it.
What does "even number of ones and zeros" mean? It can mean any of these things:
1s is even, and also the number of 0s is even1s + the number of 0s) is evenAfter I thought about it, I realised that none of these options make much sense with the question posed. They all make the opening statement/claim false (even though the question asks us to prove why it is true). It turns out that the question does not mean any of these options but instead means:
every row and every column of the resulting table has an even number of ones in it.
Or in other words, if we add all the digits of a row or a column (of the extended table) we will get an even number. This is made clearer in the answer, where the parity of rows and columns is mentioned. Parity, in general, means whether an integer is even or odd. If we are talking about the parity of a string of bits (as in our case) then parity refers to the parity of the sum of the bits, or in other words whether the number of 1s in the string is even or odd. In computer science, we have the parity bit which is a bit added to a string of bits in order to always make the parity of the (extended) string be even. So in essense this question asks about adding an extra row and an extra column of parity bits.
Also note that the ending question which mentions
has an odd number of binary digits
is clearly wrong. They mean to say:
has an odd number of binary ones
Let's look into the heart of the question. What is the problem here? If I give you a string of bits, it's easy to compute the (even) parity bit. You count the 1s and if they are even the parity bit is $0$, otherwise we set it to $1$. Here are the parity bits (in blue) for every row and column of your example table:
$$ \begin{array}{llllll|l} 1& 0& 0& 0& 1& 1& \color{blue}1\\ 1& 0& 0& 0& 1& 1& \color{blue}1\\ 1& 0& 0& 0& 1& 1& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ 0& 1& 1& 1& 0& 0& \color{blue}1\\ \hline \color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}& \color{red}? \end{array} $$
They all happen to be $1$ with the table example you gave. The real problem is: What is the bit denoted as a red questionmark? This bit should set the even parity for both the extra row and the extra column. In other words, it is the parity bit of the column of parity bits, as well as the parity bit of the row of parity bits. Since just a single string of bits (either a row or a column) can fully specify a parity bit, our red questionmark bit is overspecified. In our example above we can set it to $\color{red}0$ and satisfy both the extra row and column (i.e., we can set it with no conflict).
Let's see another table. Just take our previous example table and make it non-square by removing the last row. So now we have:
$$
\begin{array}{llllll|l}
1& 0& 0& 0& 1& 1& \color{blue}1\\
1& 0& 0& 0& 1& 1& \color{blue}1\\
1& 0& 0& 0& 1& 1& \color{blue}1\\
0& 1& 1& 1& 0& 0& \color{blue}1\\
0& 1& 1& 1& 0& 0& \color{blue}1\\
\hline
\color{blue}{1}&\color{blue}{0}&\color{blue}{0}&\color{blue}{0}&\color{blue}{1}&\color{blue}{1}& \color{red}1
\end{array}
$$
Again we find that the overspecified bit satisfies the even parity of both the extra row and the extra column. Is this always the case? The question claims that it is, and we need to explain why.
The first observation I made was that if we change a single bit in the $6\times 6$ table of our example (or the truncated $5\times 6$ table), a single bit in the parity column will change, and a single bit in the parity row will also change. This means that the overspecified bit will change too, and both parity row and parity column will be in agreement. So any number of bit changes we make for these table sizes will be ok (no conflict for the overspecified bit). But is there some other table size that produces a conflicted overspecified bit? We could perhaps make an inductive proof for every size table starting with a $1\times 1$ table, but there is a simpler method:
I made this general observation about even parity:
The parity of a concatenation of two strings is equal to the parity of concatenating their parity bits.
This might sound a bit confusing, so let me write it with symbols in order to make it more digestable. I will use the following notation: If $S$ is a string of bits, then $P_e(S)$ is the even parity bit of this string. Also if $S_1, S_2$ are bitstrings, then $S_1\oplus S_2$ is the concatenation of these two strings (in other words "glue" them together to make a bigger string). Finally a parity bit can be considererd a bitstring of length one and can be concatenated with other strings. This is what I claim:
$$P_e(S_1\oplus S_2) = P_e(P_e(S_1)\oplus P_e(S_2))$$
To prove this claim simply consider all four combinations of parity for two strings: (odd, odd), (even, odd), (odd, even), (even, even). Note that when we concatenate two odd strings we get one even string, when we concatenate one odd and one even we get odd, and finally two even strings concatenate in one even. Let $O$ denote odd strings and $E$ denote even strings in the formulas below.
$$ \begin{array}{rlrlrl} P_e(O\oplus O)&= P_e(P_e(O)\oplus P_e(O)) &\iff P_e(E) &= P_e(1\oplus 1)) &\iff 0&=0 \\ P_e(O\oplus E)&= P_e(P_e(O)\oplus P_e(E)) &\iff P_e(O) &= P_e(1\oplus 0)) &\iff 1&=1 \\ P_e(E\oplus O)&= P_e(P_e(E)\oplus P_e(O)) &\iff P_e(O) &= P_e(0\oplus 1)) &\iff 1&=1 \\ P_e(E\oplus E)&= P_e(P_e(E)\oplus P_e(E)) &\iff P_e(E) &= P_e(0\oplus 0)) &\iff 0&=0 \end{array} $$
And more generally: $$P_e(S_1\oplus S_2\oplus \dots \oplus S_n) = P_e(P_e(S_1)\oplus P_e(S_2)\oplus \dots \oplus P_e(S_n)) \qquad (\text{lemma}\; 1)$$
The generalisation is actually crucial for what we want to prove. I will not give a full proof here, but instead provide a sketch and leave the fleshed out proof as an exercise. To prove lemma 1 we need to consider having $i$ odd strings and $k$ even strings. Then examine all four cases were $i,k$ are
(odd, odd), (even, odd), (odd, even), (even, even).
After we have established lemma 1, notice again that the overspecified bit is the even parity of the bits in the parity column. In turn, the bits in the parity column are the even parities of the rows of the table. So, using lemma 1, we can say that the overspecified bit is the even parity bit of all the bits in the table. If this is unclear just set strings $S_1,\dots S_n$ in lemma 1 to be the rows of bits of our table. Moreover, we can have the same argument about the overspecified bit being the parity of the bits in the parity row, and again we end up with the overspecified bit being equal to the parity of all bits in the table (this time we set strings $S_1,\dots S_n$ in lemma 1 to be the columns of bits of our table). In other words, it does not matter if we consider all the bits row-first, or column-first, the overspecified bit is essentially calculated as the even parity bit of all bits in the table. In a picture:
$\hspace{2cm}$
Saying the same thing with formulas: Let $R_1, R_2,\dots R_n$ be the rows of the original (non-extended) table of bits. And let $C_1, C_2,\dots C_n$ be the columns. We have:
$$ P_e(P_e(R_1)\oplus P_e(R_2)\oplus \dots \oplus P_e(R_n)) \stackrel{\text{lemma 1}}= P_e(R_1\oplus R_2\oplus \dots \oplus R_n) = P_e(\text{all the bits in the table}) = P_e(C_1\oplus C_2\oplus \dots \oplus C_n) \stackrel{\text{lemma 1}}= P_e(P_e(C_1)\oplus P_e(C_2)\oplus \dots \oplus P_e(C_n)) $$
I believe that the answer given on the webpage is playing with properties closer to my first observation. The problem is that it describes the "solution" with very few words ("addition of tables (using cell-by-cell xor) preserves even parity") and ends up being obscure. When I first read it, I had no idea what it meant. Now that I've done my analysis I think I understands what it means.
I believe that the general idea is to break the table into "basic" tables where only one cell has a 1 and then you add the parity row and column for each of them to get an extended "basic" table. The parity row and column of an extended "basic" table have only one 1 bit each, and the overspecified bit is always 1. Then you combine these extended basic tables by doing bitwise XOR operations and it is implied that you get your initial extended table. It is further implied that there will always be a valid oversimplified bit. Even though all this is correct, it needs considerably more work to be proven and explained properly. It seems to me that this solution gets messy when you try to explain it properly. I prefer my approach, as I think it's cleaner, but that's a matter of taste.
The question finally asks us what happens if we choose odd parity. Can we always have a valid overspecified bit? It seems that it is nudging us towards a "no". It's easy to find a counterexample. Just look at the truncated table we used before. Let's consider the odd parities this time: $$ \begin{array}{llllll|c} 1& 0& 0& 0& 1& 1& \color{blue}0\\ 1& 0& 0& 0& 1& 1& \color{blue}0\\ 1& 0& 0& 0& 1& 1& \color{blue}0\\ 0& 1& 1& 1& 0& 0& \color{blue}0\\ 0& 1& 1& 1& 0& 0& \color{blue}0\\ \hline \color{blue}{0}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{0}&\color{blue}{0}& \color{red}{0/1} \end{array} $$
We see that now the overspecified bit is conflicted. We could stop there as far as the question is concerned (we found a counterexample) but thanks to our earlier analysis we know why this is the case: Odd parity does not have the property that even parity has. More specifically:
$$P_o(S_1\oplus S_2\oplus \dots \oplus S_n) \neq P_o(P_o(S_1)\oplus P_o(S_2)\oplus \dots \oplus P_o(S_n))$$
For example, consider three odd-parity strings: $$P_o(O\oplus O \oplus O) \neq P_o(P_o(O)\oplus P_o(O) \oplus P_o(O)) \iff P_o(O) \neq P_o(0\oplus 0 \oplus 0)) \iff 0 \neq 1$$
I hope you now have a much fuller understanding of the question and the answer. It was certainly rewarding for me to investigate it.
Best Answer
Since $1_2+1_2+1_2+1_2=100_2$, you add a $1$ two columns to the left to the one you are working with.