2
\$\begingroup\$

I was asked to design a digital system that receives two inputs: X and X+2, and must output X+1, without using any adders or subtractors. (We weren't told what is the number of bits for X and X+2)

I came across the circuit shown below (see attached diagram). It uses a multiplexer and some simple logic feedback to achieve the required output.

However, I have a question about how this works: The MUX has a single select input (X[0]), but both data inputs are multi-bit signals (X and X+2). How can a MUX with one select bit handle multi-bit inputs like that? Isn’t it supposed to only choose between 0 and 1?

I’m wondering if the idea here is actually that the system uses n parallel 2:1 multiplexers, one per bit — and that would explain how the multi-bit selection works? Since the output is also an n-bit value, maybe that’s the intended interpretation?

But here's a concern: If we assume X = 11111110 or X = 11111111 (i.e., near the upper bound of n bits), then X+2 would overflow and require n+1 bits. So wouldn’t we actually need n+1 multiplexers and produce an n+1-bit output? That is, X+2 and X+1 could be wider than n bits. How is this handled in such a design?

Any clarification would be appreciated!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ This looks much like homework question. If it is, you should definitely try to design it by yourself rather than copy a design you found on the Internet and you don’t understand. As for what happens in case of overflow between X and X+2, I guess you might ignore such a case (since you don’t really have X and X+2)… \$\endgroup\$ Commented Oct 22 at 8:18
  • \$\begingroup\$ Hi, it is not homework question, its a interview question. But anyway, I don't need a solution... I also tried to design it, I already know what to do... If X is even, so just change the LSB from 0 to 1. if X is odd, so just change the X+2 LSB from 1 to 0 (since they are both odd). My question is just as I said in the body \$\endgroup\$ Commented Oct 22 at 8:20
  • \$\begingroup\$ And I understand that solution... the only thing not understandable is the MUX 2:1 with multiple inputs, thats it, nothing else, nothing more... That was my problem when I tried to solve it, how do I enter to a mux multiple inputs, so I looked at the solution and it had the same idea as mine, but again, as said \$\endgroup\$ Commented Oct 22 at 8:21
  • \$\begingroup\$ There is no feedback. \$\endgroup\$ Commented Oct 22 at 17:33
  • \$\begingroup\$ @greybeard Sorry, wasn't online, now seeing the comments. \$\endgroup\$ Commented Oct 23 at 7:10

3 Answers 3

Reset to default
4
\$\begingroup\$

It's a mux that select all N bits of the inputs it receives as it clearly has a bus marked with N bits out.

A mux is a generic block diagram for any arbitrary signal or whole bus of them, it doesn't mean it selects only one bit. The inputs are just labeled bus 0 and bus 1, so the two inputs can be selected with one bit.

And the output is defined to be N bits, so that is what you need to work with. If X overflows by a bit when you add one, it has also already overflowed when X+2 is added, the assignment doesn't state that overflow needs to be considered so it does not need to be considered, but if the output N is large enough that X+2 fits then X+1 also fits, so this is a non-issue, the output can be made to whatever it needs to be and outside the scope.

What is given is that Y has N bits and it is your new signal. It does not matter how many bits X or X+1 had to begin with.

The point of these kinds of questions is to not only end up in a correct solution but also to raise discussion around the subject, so understanding that things left ambiguous need to be defined in actual implementation if it matters.

\$\endgroup\$
7
  • \$\begingroup\$ Hi, thanks for the answer, so just a few basic questions:;;;;;; 1. So a 2:1 MUX or 4:1 MUX or 8:1 MUX, can receive inputs that are 10,20 bits, although the select is only 1,2,3 bits? First time hearing it..... If I did n MUX of 2:1 and just entered x[0], X+2[0], and to the second X[1], X+2[1] and so on... and did it in parallel with the same control X[0], is it okay or its bad? \$\endgroup\$ Commented Oct 22 at 8:42
  • \$\begingroup\$ 2. Regarding the output to be N bits, its just the person that solved it did this, but they didn't say at the question how many bits the inputs are. That is why I assumed there is a possible of overflow here. But you say I shouldn't assume if I wasn't told, so X,X+2 will neccesarily be both N bits, right? \$\endgroup\$ Commented Oct 22 at 8:43
  • 1
    \$\begingroup\$ @BenShaines The bitness is really irrelevant, the X and X+2 are just numbers like variables and you simply get them as given. Either, X+2 already overflows or it doesn't, it isn't relevant in the context for getting a correct block diagram for arbitrary length numbers. The numbers could be 1-bit, 2-bit, 3-bit, 8-bit, and it might or might not be important to consider overflow. The important part here is that you are already thinking that overflow can matter in some instances, but it is not known if it does in this instance. \$\endgroup\$ Commented Oct 22 at 9:14
  • \$\begingroup\$ Okay, got it regarding the overflow. But regarding the idea of MUX that I gave, is it possible to do it like that? N mux of 2:1 in parallel and then just take the output and the right half of the solution is the same basically. I just want to make sure. \$\endgroup\$ Commented Oct 22 at 9:16
  • 2
    \$\begingroup\$ @BenShaines And that is a block diagram how to handle some numbers in some way, not a specific implementation of piece of hardware that uses specific chips to do that, nor a specific piece of Verilog/VHDL/Python/C/Assembly language program that does it on some hardware. \$\endgroup\$ Commented Oct 22 at 11:55
2
\$\begingroup\$

Assume the inputs are binary, so the last bits are equal for both inputs.

The result is X with the last bit set if the last bit of X is 0, and X+2 with the last bit cleared if the last bit of X is 1.

\$\endgroup\$
3
  • \$\begingroup\$ Hi, sorry, didn't really understand what you wrote. But I already got answer to my question, so thanks though :) \$\endgroup\$ Commented Oct 23 at 7:13
  • 1
    \$\begingroup\$ @BenShaines : That is "if the least significant bit of X is 0, return X with its least significant bit set to 1, else return X+2 with its least significant bit set to zero." \$\endgroup\$ Commented Oct 23 at 10:03
  • \$\begingroup\$ Oh that is how I solved this, thanks :) \$\endgroup\$ Commented Oct 23 at 10:16
2
\$\begingroup\$

Actually, you do not need a multiplexer wide enough for \$X+2\$: one bit less will do, as both LSBs will be the same.

If we assume X = 11111110 or X = 11111111 (i.e., near the upper bound of n bits), then…

The diagram shows \$n\$ bit to be sufficient for \$X+2\$ as well as \$X\$, selected by \$X[0]\$.
It's just that the domain for \$X\$ does not include all ones -
you don't complain 0 or 1 is no useful value for \$X+2\$ - or do you?

But you can use one bit of an n-bit 2-to-1 selector to do without an inverter:
feed a H for select = L, an L for select = H.

\$\endgroup\$
6
  • \$\begingroup\$ The answer is different from the question, I mean, the question didn't say how many bits are X and X+2, the solution is assuming that they are both n bits, but I just gave a specific case in which X+2 is n+1 bits and X is n bits...... Regarding N bit of 2:1 MUX, exactly, so its good, Thanks :)............ If I understood wrong what you said, so please tell. \$\endgroup\$ Commented Oct 23 at 7:12
  • \$\begingroup\$ @BenShaines The design task in the question's 1st sentence is explicitly qualified in parenthesis to not specify a width. What's presented does not even specify a number representation: it could be unary or Gray. The diagram in the question body depicts output width as n, and the concern expressed there is all about that. The possibility to represent X in one bit less than X+2 needing n bits does not prevent representation of X in n bits - or 42 times that. \$\endgroup\$ Commented Oct 23 at 7:24
  • \$\begingroup\$ I am sorry, I really don't understand what you say at the end. What does it mean not prevent representation of X in n bits? Could be my english is bad, but you mean that the solution is the same regardless if X is n bit and X+2 is n+1 bit? I still need n MUX and not n+1 MUX? \$\endgroup\$ Commented Oct 23 at 7:53
  • 1
    \$\begingroup\$ I take n to be the number of bits X+2 is represented in. Assuming binary representation, you need to as n bits (minus one), no matter if the MSB of X is 0 or 1. Actually, "all ones"-1 happens to work just fine with another bit less/just enough to represent X. \$\endgroup\$ Commented Oct 23 at 7:59
  • \$\begingroup\$ Oh, i see what you say. Didn't think of it \$\endgroup\$ Commented Oct 23 at 8:07

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.