binary to hex conversion proof

[njama]

Hello PF members!

I am interested in proving that the conversion of binary to hex is valid.

Example: 1000100100110111

Breaking into 'quartets' 1000 1001 0011 0111

Now using the fact that 24 = 0...15

1000 = 8, 1001 = 9, 0011 = 3, 0111 = 7. So

10001001001101112=893716

I can create the table starting from 0000 to 1111. I need to prove that this conversion really works.

I would start the proof by stating that the number in binary form is:

b_1b_2...b_{n-1}b_n

If n mod 4 == 0 (if the remainder of the division of n with 4 is zero) then:

b_1b_2b_3b_4 .... .... .... b_{n-3}b_{n-2}b_{n-1}b_n

But how to prove afterward?

else we can add m zeroes so that (m+n) mod 4 ==0.

By adding zeroes before the binary number I can easily prove that nothing is changed.

(*)=b_1b_2...b_{n-1}b_n=b_n*2^0 + b_{n-1}*2^1+...+b_2*2^{n-2}+b_1*2^{n-1}

00..00b_1b_2...b_{n-1}b_n=b_n*2^0 + b_{n-1}*2^1+...+b_2*2^{n-2}+b_1*2^{n-1}+0*2^n+0*2^{n+1}...+0*2^{n+m}=(*)

Any help would be appreciated.

[DoctorBinary]

This is not a proof but an example to show how you might think of it (I reversed the numbering of the coefficients in your example, to match the exponents):

A 12-digit binary number: b_{11}2^{11}+b_{10}2^{10}+b_{9}2^{9}+b_{8}2^{8}+b_ {7}2^{7}+b_{6}2^{6}+b_{5}2^{5}+b_{4}2^{4}+b_{3}2^{ 3}+b_{2}2^{2}+b_{1}2^{1}+b_{0}2^{0}

Factor out multiples of 16: 2^8(b_{11}2^{3}+b_{10}2^{2}+b_{9}2^{1}+b_{8}2^{0}) +2^4(b_{7}2^{3}+b_{6}2^{2}+b_{5}2^{1}+b_{4}2^{0})+ 2^0(b_{3}2^{3}+b_{2}2^{2}+b_{1}2^{1}+b_{0}2^{0})

Rewrite with powers of 16: 16^2(b_{11}2^{3}+b_{10}2^{2}+b_{9}2^{1}+b_{8}2^{0} )+16^1(b_{7}2^{3}+b_{6}2^{2}+b_{5}2^{1}+b_{4}2^{0} )+16^0(b_{3}2^{3}+b_{2}2^{2}+b_{1}2^{1}+b_{0}2^{0} )

Everything in parentheses is a hex digit, with value 0-15.

[njama]

Ohh.... Thanks a lot.

Here is what I've done:

(I've excluded the case which I have already proof with the zeroes before the number)

So lets suppose there are m+n+1 digits, and we can form a quartets.

The binary number is:

b_{m+n}2^{m+n} + b_{m+n-1}2^{m+n-1} + ... + b_32^3+b_22^2+b_12^1+b_02^0

Now factoring out multiples of 16

2^{m+n-3}(b_{m+n}2^3+b_{m+n-1}2^2+...+b_{m+n-3}2^0)+....+2^0(b_32^3+b_22^2+b_12^1+b_02^0)

There are m+n / 4 hexadecimal digits. Did I do the proof correctly ? (except for minor mistakes)

[DoctorBinary]

That looks pretty good, except I think you need to make it clear that the terms are powers of 16. That will make the notation cumbersome though. For example, 2^{m+n-3} would be (2^{4})^{(m+n+1)/4 - 1}. Not too pretty, but a cleaner way doesn't come to mind at the moment.

[zgozvrm]

Try thinking about it this way:

Each more significant binary digit is represented by a 0 or 1 multiplied by a power of 2 that is greater than the previous digit by 1. In other words (sticking with whole numbers), the lowest binary digit can be represented by b_02^0

Remembering, of course that b_n=0 or b_n=1 for all n.

The next more significant binary digit can be represented by b_12^1

and so on... Then, for any binary number with more than 4 digits, you have: 2^n , 2^{n-1}, ..., 2^3, 2^2, 2^1, 2^0

By breaking a large (more than 4 digits) binary number into quartets, and re-assigning them to values of 0..15, you are actually reassigning the appropriate power of 2 (the exponent) for all digits more significant than b_32^3

Obviously, for the 1st quartet (4 least significant bits), which is b_3b_2b_1b_0, the value is already correct (there is no reassignment of exponents) and the quartet's value is b_32^3+b_22^2+b_12^1+b_02^0

For the 2nd quartet, b_7b_6b_5b_4, you are essentially changing the exponents from 2^7, 2^6, 2^5, and \phantom{1}2^4 to 2^3, 2^2, 2^1, and\phantom{1}2^0
This results in the 2nd quartet having the value b_72^3+b_62^2+b_52^1+b_42^0 (The actual value is, of course: b_72^7+b_62^6+b_52^5+b_42^4)

What you've done here is subtracted 4 from each of the exponents in the 2nd quartet: b_72^{7-4}+b_62^{6-4}+b_52^{5-4}+b_42^{4-4}

Using one of the laws of exponents: \frac{X^a}{X^b}=X^{a-b}, we can show that 2nd quartet as: b_7\frac{2^7}{2^4}+b_6\frac{2^6}{2^4}+b_5\frac{2^5 }{2^4}+b_4\frac{2^4}{2^4}

We can then factor out \frac{1}{2^4}, resulting in \frac{1}{2^4}(b_72^7+b_62^6+b_52^5+b_42^4)

And, since 2^4=16, what you've effectively done, is divided the 2nd quartet by 16!

Extending this same technique out to the next quartet, you'll find that you will have divided that quartet by 2^8=16^2

Remember also, that each more significant digit in hexidecimal (base 16) is a successively larger power of 16, such that you have
h_n16^n+h_{n-1}16^{n-1}+...+h_316^3+h_216^2+h_116^1+h_016^0
with h_n = 0...9, A..F

[zgozvrm]

So, for each quartet Q_n \phantom{0} (n\geqq1), you obtain the hex digit by dividing the binary value of the quartet by 16^{n-1}

[njama]

Thank you for the help all of you.

So do I need to write it like this:


16^{(m+n-3)/4)}(b_{m+n}2^3+b_{m+n-1}2^2+...+b_{m+n-3}2^0)+16^{(m+n-3)/4 -1}(b_{m+n-4}2^3+...+b_{m+n-7}2^0)....+16^0(b_32^3+b_22^2+b_12^1+b_02^0)

[HallsofIvy]

Hello PF members!

I am interested in proving that the conversion of binary to hex is valid.

Example: 1000100100110111

Breaking into 'quartets' 1000 1001 0011 0111
Of course 100002= 16 so while 01112= (01112)(1)= (01112)(160)= 7(160), the second set, "00112", is (00112)(16)= (00112)(161)= 3(161, the third "10012 is (10012)(162)= 9(162), and the fourth "10002" is (10002)(163)= 7(163.


Now using the fact that 2[sup]4 = 0...15

1000 = 8, 1001 = 9, 0011 = 3, 0111 = 7. So

10001001001101112=893716

I can create the table starting from 0000 to 1111. I need to prove that this conversion really works.

I would start the proof by stating that the number in binary form is:

b_1b_2...b_{n-1}b_n

If n mod 4 == 0 (if the remainder of the division of n with 4 is zero) then:

b_1b_2b_3b_4 .... .... .... b_{n-3}b_{n-2}b_{n-1}b_n

But how to prove afterward?

else we can add m zeroes so that (m+n) mod 4 ==0.

By adding zeroes before the binary number I can easily prove that nothing is changed.

(*)=b_1b_2...b_{n-1}b_n=b_n*2^0 + b_{n-1}*2^1+...+b_2*2^{n-2}+b_1*2^{n-1}

00..00b_1b_2...b_{n-1}b_n=b_n*2^0 + b_{n-1}*2^1+...+b_2*2^{n-2}+b_1*2^{n-1}+0*2^n+0*2^{n+1}...+0*2^{n+m}=(*)

Any help would be appreciated.

[njama]

Ok, I believe to makes things better I should use m+n-1 = 4k

[zgozvrm]

Ok, I believe to makes things better I should use m+n-1 = 4k

I would simplify things a little by first stating that any number (binary, or otherwise) can be led with any number of 0's and still retain the same value. That said, I would FIRST add the number of 0's needed (one, two, or three of them) to make the number of binary digits (bits) evenly divisible by 4. Then use "n" to represent the total number of bits in the binary number (including those added 0's, if any).

Then, you can write it as:

16^{\frac{n}{4}-1}(b_n2^3 + b_{n-1}2^2 + b_{n-2}2^1 + b_{n-3}2^0) + 16^{\frac{n}{4}-2}(b_{n-3}2^3 + b_{n-4}2^2 + b_{n-5}2^1 + b_{n-6}2^0) + ... + 16^1(b_72^3 + b_62^2 + b_52^1 + b_42^0) + 16^0(b_32^3 + b_22^2 + b_12^1 + b_02^0)