# GATE2006-40

10.3k views

Consider numbers represented in 4-bit Gray code. Let $h_{3}h_{2}h_{1}h_{0}$  be the Gray code  representation of a number $n$ and let $g_{3}g_{2}g_{1}g_{0}$ be the Gray code of $(n+1)(modulo 16)$  value of the number. Which one of the following functions is correct?

1. $g_{0}(h_{3}h_{2}h_{1}h_{0})=\sum (1,2,3,6,10,13,14,15)$
2. $g_{1}(h_{3}h_{2}h_{1}h_{0})=\sum (4, 9,10,11,12,13,14,15)$
3. $g_{2}(h_{3}h_{2}h_{1}h_{0})=\sum (2, 4,5,6,7,12,13,15)$
4. $g_{3}(h_{3}h_{2}h_{1}h_{0})=\sum (0,1,6,7,10,11,12,13)$
0
can someone plz help ? i understood the solution but my doubt is why ?  we have map this with the corresponding grey code number  like ( 0110 with 0010 (2) ) as while design the grey code circuit (kmap) we get the minterms by checking the corresposding decimal no like 0110 is grey code of 3(0011) so here  g2 bit is 1 so its mean minterm should be 3, like in this way ? is just for making my concept more clear , bcoz this question can be further modified so, kindly clear this doubt n thanks in advance .
8

As we know grey codes are not weighted code means there is no pattern to generate grey code and also grey code are reflected code,,lets generate grey code using reflecting property

0
what does modulo16 mean in question?

Decimal n Binary n H(x) = gray(n) G(x) = gray[(n+1) mod16]
0 $0000$ $0000 (00)$ $0001$
1 $0001$ $0001 (01)$ $0011$
2 $0010$ $0011 (03)$ $0010$
3 $0011$ $0010 (02)$ $0110$
4 $0100$ $0110 (06)$ $0111$
5 $0101$ $0111 (07)$ $0101$
6 $0110$ $0101 (05)$ $0100$
7 $0111$ $0100 (04)$ $1100$
8 $1000$ $1100 (12)$ $1101$
9 $1001$ $1101 (13)$ $1111$
10 $1010$ $1111 (15)$ $1110$
11 $1011$ $1110 (14)$ $1010$
12 $1100$ $1010 (10)$ $1011$
13 $1101$ $1011 (11)$ $1001$
14 $1110$ $1001 (09)$ $1000$
15 $1111$ $1000 (08)$ $0000$

We need to map min terms of $g_3g_2g_1g_0$ w.r.t $h_3h_2h_1h_0$.

Hence as highlighted $g_2$ matches with option C.

Edit :
We have to map $h(x)$ with $g(x)$. Mod 16 is used in $g(x)$ only because since we have $4$ bits, mamximum possible no that can be represented is $15$, so after $15$ we shouldn't get $16$ and go back to $0$. thats why.
Now, mapping is simple.We just have to map such that h(x)---->g(x+1)
Means if h represents gray code of 0 then g will represent gray code of 1
If h represents gray code of 1 then g will represent for 2 and so on.
For last number h(15), mod $16$ actually comes into picture which will make it to represent as g(0)
So, draw table as mentioned above.
Now, write $g$ as a function of $f$. Simply how we do minimisation. See the min terms.
Be careful only in one thing here.
Example for 2 gray code representation is 0011 meaning 3 in decimal.So, if we select this row as a min term(just an Example) then we have selected 3 and not 2, means row numbers are not representing min terms. Rest everything is fine!

edited
4
how are you doing matching ...?? whats the exact meaning of g(h1h2h3h4) ??
1
Yeah explain pls how are you doing matching with respect to g(h3h2h1h0) ?
4

I got this solution in gatementor. But Dont know how the matching happens ?

6
@prasanna, h3h2h1h0 is taken as an 4-bit input and g3g2g1g0 is taken as 4-bit output. so, output from g2 will be the sum of the minterms where it is high.
0
Thank you
2
1
i have added some more explanation...now it should be clear fr everyone!!
0
@sudhso

not getting thiz

now write g as a function of f ? what does it signify ?not getting any sense .
2
see for g0 , g1 ,g2 ,g3 are separate functions of h(x) in themselves..its like the same thing designing one flip flop from other kind
if we need to find g0 see where it is 1 for h(x)
like it is one at row no 0,1,4,5,8,9,12,13..these are row nos not min terms...so for those rows find out the min terms and represent...like see row 0..min term there is 0...see row 1 min term is 1...now see row 4 min term is 0110 means 6 and so on...do this for all and then match with options.
0

g0(h3h2h1h0) what is meant tell that ?

g0 is lsb of G(x) ?

and h3 h2 h1 h0 are position of four digits?

if it than we take g0 of which means there are 15 g0 at respective column and how do match ?

0
to find g0 see what are its min terms inform of (h3 h2 h1 h0)
same thing do fr all
0

@bikram sir

We need to map min terms of g3g2g1g0 w.r.t h3h2h1h0

what does it mean?...plz elaborate this procedure .

0
I think 14 is missing in C option ?
0

But gray code id non-weighted ..so

(0011) In gray means (0010) in binary and hence 2 in decimal.

how it is 3 ..

0

@jatin khachane 1 check the mapping given in the question don't do conversion here.

Step 1: 4 bits hence 16 combinations. Write down all 16 combinations of gray code for each of binary (0-15)

Step 2 : it says a gray code combination of a binary number n will map to gray code of binary number n+1. Check value for each code is mapped to value below it.

Continuing to your answer. gray code of 2(0010) will be (0011) and now this (0011) will be mapped to gray code of 3 which is 0010.

0

I'm getting g2(h3h2h1h0)=∑(2,4,5,6,7,12,14,15)

But in the options it is g2(h3h2h1h0)=∑(2,4,5,6,7,12,13,15)

Anyone on the same boat with me?

0
bro it's not saying (h+1)(modulo 16) it's saying (n+1)(modulo 16). you might be considering h at last.
0
I cant understand how g is calculated. For example if I take n as 0101(5) then its gray code h will be 0111. now (n+1) is 0110(6). Then (n+1)mod 16 is 1010(10). whose gray code g will be 1111. Where am I getting it wrong?
0
@Gupta731  (5+1)%16=6 (0110). Gray code: 0101.
0

I understand how to calculate gray code and how to find the minterms, but I’m a bit confused about what the operation is. This is what I got from the question assuming the example 1000

• the binary number is 8
• finding the grey code, we get 1100, this is h(b)
• h(b)+1 is 1101
• [ h(b)+1 mod 16 ] is 1101
• now finding g(b)→ gray( ( (h(b)+1) mod 16 ) )
• shouldn’t this be gray(1101) = 1011 and not 0000 like in the table.

I know I am wrong, I just don’t understand where please help me read the question right and figure out what the operation means.

For each gi, we need to find the 4-bit sequences whose next code gives a 1 for bit position i. So, based on the Gray code sequence (in below link) we get (C) as true. (Just convert the Gray code to decimal, and we get the minterm).

http://electrical4u.com/gray-code-binary-to-gray-code-and-that-to-binary-conversion/

0
Can u jus elaborate wat does g(h1h2h3h4) mean l??
0
not getting the answer . How to map ? (Else conversion other thing are clear )
1
g2(h3h2h1h0) means the values of h3h2h1h0 where g2 is 1. ($\sum$ means the sum of combinations in truth table where the output is 1)
0
little more describe buddy i think i will get it.
8
Think of how you get the canonical sum of products ∑ form from the truth table. It's the rows in truth table for which the output is 1, we consider them as 'minterms' and write something like ABC + A'BC + A'B'C' and so on as SOP.
So, in this question they are asking ..does function for g1 taking in the input variables h0,h1,h2,h3 has the following minterms?
They have given decimal equivalents of the minterm. So, in the table check where g1 is 1 and the decimal equivalent of gray code h3h2h1h0 is the minterm.
Do this for all g0,g1,g2,g3 and match with options.
0

atlast got it..tie buddy .

god fill ur account with black money . tie lot.

now come on following question

https://gateoverflow.in/1056/gate2004-61

1

g2(h3h2h1h0)

1) see the value of 1  corresponding g2 in all 0 to 15 number

2) write value in decimal for given h3h2h1h0 in the form of minterms

The question simply says that if 'h' (coded as $h_3h_2h_1h_0$) is the 4-bit gray code of n then 'g' (coded as $g_3g_2g_1g_0$) is the gray code of (n+1) mod 16.

So, write the gray code as:

function h function g
$n$ $h_3$ $h_2$ $h_1$ $h_0$ $g_3$ $g_2$ $g_1$ $g_0$
0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 1 1
2 0 0 1 1 0 0 1 0
3 0 0 1 0 0 1 1 0
4 0 1 1 0 0 1 1 1
5 0 1 1 1 0 1 0 1
6 0 1 0 1 0 1 0 0
7 0 1 0 0 1 1 0 0
8 1 1 0 0 1 1 0 1
9 1 1 0 1 1 1 1 1
10 1 1 1 1 1 1 1 0
11 1 1 1 0 1 0 1 0
12 1 0 1 0 1 0 1 1
13 1 0 1 1 1 0 0 1
14 1 0 0 1 1 0 0 0
15 1 0 0 0 0 0 0 0

Now, we just have to write $g_2$ as a function of $h$ i.e $g_2(h_3h_2h_1h_0)=\sum(minterms \ of\ g_2)$

To get minterms, convert h to decimal wherever you get '1' in $g_2$.

$\therefore g_2=\sum (2,4,5,6,7,12,13,15)$

0
I cant understand how g is calculated. For example if I take n as 0101(5) then its gray code h will be 0111. now (n+1) is 0110(6). Then (n+1)mod 16 is 1010(10). whose gray code g will be 1111. Where am I getting it wrong?
0
n= 0101 (5)

h(n)= gray code of n = 0111

g(n)= gray code of(n+1 mod 16)= gray code of (5+1)mod16= gray code of 6=gray(0110)=0101

NOTE: @Gupta731 What you are doing wrong is, (n+1)mod16 = 6mod16 = 6 NOT 10

g0 (h3h2h1h0) = ∑ (1,2,3,6,10,13,14,15)

These 1,2,3,6,10... numbers are not in decimal. They're in Gray Code.

Minterms of g2 would be: 3,4,5,6,7,8,9,10.

In Gray code, it'll be: 2,4,5,6,7,12,13,15 (not respectively)

Hence, Option C.

0
Can you please explain g2 is not 1 at 0010 why is that included in the min term?

Rest everywhere g2 is 1.

I think we can get the answer in thhe following way also:-

## Related questions

1
10.6k views
We consider the addition of two $2's$ complement numbers $b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by $c_{n-1}c_{n-2}\dots c_{0}$ and the carry-out by $c_{out}$ ... $c_{out}\oplus c_{n-1}$ $a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$
Convert $1101_2$ to corresponding $excess-3$ binary number. (A) $10000$ (B) $01000110$ (C) $100110$ (D) $10110$
Given two three bit numbers $a_{2}a_{1}a_{0}$ and $b_{2}b_{1}b_{0}$ and $c$ ...
Consider the circuit above. Which one of the following options correctly represents $f\left(x,y,z\right)$ $x\bar{z}+xy+\bar{y}z$ $x\bar{z}+xy+\overline{yz}$ $xz+xy+\overline{yz}$ $xz+x\bar{y}+\bar{y}z$