0
$\begingroup$

Prove that for every $n \in \mathbb N$ with $n \geq 1$ a $1$-step binary code $C_n$ for the inteval $[0, 2^n −1]$ with code words of length $n$ exists.

I have to prove it using induction.

$\endgroup$
2
  • $\begingroup$ Welcome to SE. What have you tried so far? $\endgroup$ – Behrad Moniri Apr 14 '19 at 16:32
  • $\begingroup$ Tried to find a function for the 1 step binary. Just struggled to define a function for that came to the point of 0 0, 0 1, 1 0 , 1 1. is 0 and 1 with added 0 and 1. And frustrating don't know if it's kind of a right way to solve the answer. $\endgroup$ – Rack Cloud Apr 14 '19 at 16:40
0
$\begingroup$

Given an $n$ bit code, an $n+1$ bit code consists of all the strings prefixed with a $0$ and all the strings prefixed with $1$. Start with the code with the $0$ prefix, which gets you half way there. All the rest start with $1$, so the first code with $1$ has to match on all of he other bits. Going from the last to the first you will have a change in the first bit, so again all the others have to match. Can you see how to construct it?

$\endgroup$
3
  • $\begingroup$ So the n+1 Code is 2 times the n code with 1 and 0 added in front and these put together are the gray code. But how do i write down this in a mathematical proof with induction. $\endgroup$ – Rack Cloud Apr 14 '19 at 17:50
  • $\begingroup$ You have to reverse the order of the second half to make it work. You have to explain that there is only one bit changed at each point $\endgroup$ – Ross Millikan Apr 14 '19 at 19:34
  • $\begingroup$ For example, a two bit code is $00,01,11,10$. Put a zero in front of each, then put a one in front in reverse order and you get $000,001,011,010,110,111,101,100$ which works. You need to show this process always works. $\endgroup$ – Ross Millikan Apr 15 '19 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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