Combinatorics: BINARY NUMBERS WITH NEGATIVE BITS In this final assignment, we study a number system similar to binary numbers, but different in two respects. First of all, the numbers(bits), in...

1 answer below »
See file


Combinatorics: BINARY NUMBERS WITH NEGATIVE BITS In this final assignment, we study a number system similar to binary numbers, but different in two respects. First of all, the numbers(bits), in addition to +1 (“positive on”) and 0 (“off”), also −1 (“negative on”). Then second, two bits must not be “on” next to each other (positive and/or negative). For example, the number 7, which we usually write in binary as 111 (or for example 00000111 if we look at 8-bit binary numbers), will now be are written as (1, 0, 0, −1), which stands for . And (−1, 0, 0, 1) correctly represents −7. In this exercise we introduce this number system and we prove with the help of combinatorics that we can use all integers (including the negative so) be able to display uniquely (except for leading zeros) So the possible bits are the numbers −1, 0 and 1. A row of bits is called correct if it satisfies the requirement that for all holds that 0 or. So (0, −1, 0, 0, 1, 0) is a correct sequence of 6 bits, but (−1, 0, 0, 1, −1, 0) neither and (1, 0, 1, 0, 1, 1) neither. Call the number of correct sequences of length . Exercise 1. (a) Check that ,and (b) Determine. (c) Prove that the sequence satisfies the recurrence relation (for ). (Don't do that based on a possible observed pattern in the previous section, but give a conclusive combinatorial argument.) (d) Using recursion, calculate how many correct sequences of length 10 there are. (e) Now solve for the recurring relation (so give a direct general formula for as a function of ). (And check this by calculating again) From a correct sequence of bits we now know the integer admit; we then call the sequence a neighborless notation of bits for. Thus (1, 0, 0, −1) and (0, 0, 0, 0, 1, 0, 0, −1) are neighborless notations of 4 respectively 8 bits for the number 7. Exercise 2. (a) Give all correct sequences of 4 bits. What numbers do these correspond to? (b) For given , what is the largest number you can get with bits (in terms of )? And what is the smallest (most negative) number ? How many numbers are there between and (including and itself)? (Distinguish the cases is even and is odd.) (c) Now prove that for every number with there is exactly one neighborless notation of bits for . Hint: Choose and suppose that = holds for two different correct sequences of bitsand . By removing equal initial bits, we may assume that, say . Now distinguish the cases for and and show that the largest number you can get with the first is smaller is then the smallest number you can get with the second.
Answered 1 days AfterJun 02, 2021

Answer To: Combinatorics: BINARY NUMBERS WITH NEGATIVE BITS In this final assignment, we study a number system...

Rajeswari answered on Jun 04 2021
150 Votes
Combinatorics:
BINARY NUMBERS WITH NEGATIVE BITS
In this final assignment, we study a number system similar to binary numbers, but different in t
wo respects. First of all, the numbers(bits), in addition to +1 (“positive on”) and 0 (“off”), also −1 (“negative on”). Then second, two bits must not be “on” next to each other (positive and/or negative).
For example, the number 7, which we usually write in binary as 111 (or for example 00000111 if we look at 8-bit binary numbers), will now be are written as (1, 0, 0, −1), which stands for . And (−1, 0, 0, 1) correctly represents −7.
In this exercise we introduce this number system and we prove with the help of combinatorics that we can use all integers (including the negative so) be able to display uniquely (except for leading zeros)
So the possible bits are the numbers −1, 0 and 1. A row of bits

is called correct if it satisfies the requirement that for all holds that
0 or. So (0, −1, 0, 0, 1, 0) is a correct sequence of 6 bits, but
(−1, 0, 0, 1, −1, 0) neither and (1, 0, 1, 0, 1, 1) neither.
Call the number of correct sequences of length .
Exercise 1.
(a) Check that ,and
We have 3 can be written as 4-1 i.e. 1 0 -1 as we represent in negative.
This is of the form hence of length 1.
So we have
Consider 5 =
5 = 101
There are two positive 1’s hence length 2.
11 can be written with no consecutive positive of negative like this only
i.e. 1 0 -1 0 -1 hence has string 5.
(Note in ordinary binary we write 11 as 2^3+2+1 = 1011 but...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here