Greater than N in combinatorial logic

[c4757p]

summing currents followed by a comparator - the amount of components and complexity is at least order of magnitude less than the implementation with adders and gates.

Using a PIC or AVR with ZERO external components is an order of magnitude less parts than the comparator solution.

"components and complexity", unless your comparators have to be programmed

[richard.cs]

For 3 of 10 then a circuit with 12 resistors and a comparator is about as simple as it gets, but it gets clumsy if 1) the driving logic doesn't have tightly defined voltages requiring you to buffer first or 2) you have so many inputs you run into component tolerance problems. A micrcontroller is potentially less board space (but maybe not, 16 pin micro vs a sot-23-5 comparator and some passives) but definately more design time in writing the code. The pure logic solutions are instructive to think about but the counter ones offer little advantage over a microcontroller, still being sampled. The gate only solutions could be the fastest way for many inputs but will be massive implimented as separate chips.

[free_electron]

The problem with this kind of circuits is that the matrix is so sparse or dense you cant form clusters to minimize logic away.

The only real way of doing it is to solve it numerically. Adding the pins until you get a 4 bit representation and then sending that through a magnitude comparator. Like a 7475 .
For a 10 pin input you would need a pretty long ladder of adders ...

[Kalvin]

A 1M * 8 EPROM costs less than a $1 in ebay which will perform quite well for this kind of application, and will provide you with two 10-bit comparators or one 20-bit comparator or anything between. Some EPROMs can be configured for 8-bit or 16-bit devices, which will provide quite nice combinatorial logic possibilities: 1M*8/512K*16 EPROM can provide a combination logic for 20 inputs and eight outputs or 19 inputs and 16 outputs.  The EPROM solution is somewhere between the discrete logic and CPLD/FPGA. Of course, one should provide necessary flip-flops for the inputs/outputs if synchronous design is desired.

[German_EE]

Exactly, ten bits is 1024 combinations so you just feed your input into the address pins and take your output from the data pins. At a thousand or so addresses I would be tempted to program it by hand and it is certainly much easier than wiring dozens of gates together.

[codeboy2k]

I would do it with an EEPROM.  It's just so much simpler, having just one device, that's dead-easy to program correctly.

A PIC or AVR MCU would be acceptable too, as paulie pointed out.  Both devices need to be mass programmed, so on that bullet point neither one is better than the other. However, the EEPROM wins out because it's just a memory map to be programmed, whereas the MCU solution needs a software programmer to write the code that does the majority function, and that code can be written incorrectly, and/or could have subtle timing errors that are hard to track down.  There's no need to introduce that extra risk.

[zapta]

I would do it with an EEPROM.  It's just so much simpler, having just one device, that's dead-easy to program correctly.

A PIC or AVR MCU would be acceptable too, as paulie pointed out.  Both devices need to be mass programmed, so on that bullet point neither one is better than the other. However, the EEPROM wins out because it's just a memory map to be programmed, whereas the MCU solution needs a software programmer to write the code that does the majority function, and that code can be written incorrectly, and/or could have subtle timing errors that are hard to track down.  There's no need to introduce that extra risk.

MCU can do other things such as independent debouncing on the inputs, identifying the first N active inputs (e.g. as a game controller, etc), have state memory, short output pulse on change, etc. It depends what the rest of the circuit need to do.

[codeboy2k]

MCU can do other things ....

Sure. If the OP needs it to do other things or can use it for other things in the overall design then perhaps the MCU makes sense. That need wasn't specified up front. But I agree, the MCU + cost of software development might outweigh other seemingly simpler solutions if it the right fit and can be put to extra uses in the entire system design at less overall cost. 

As engineers, we routinely make these kinds of cost/benefit decisions.

... It depends what the rest of the circuit need to do.

Unfortunately, we don't know what the rest of the OP's circuit needs to do. Perhaps the OP's circuit needs to have such high reliability and low failure rate that only a hard-wired solution will suffice.   Or perhaps a mask programmed PROM is OK. Or perhaps that's not needed and an in-circuit programmed EEPROM will do.  Or perhaps an MCU is just fine. We don't know, but if an MCU is a good fit then it should be used, I'm all for it.  It's all about using what's right for the job at hand and when.

[T3sl4co1l]

What hasn't been stated, I think: any kind of memory is relatively expensive and slow.  MCUs are not only atrociously slow, but often nondeterministic as well.

True, memories are only a buck or two, but a discrete logic function (which since it's not standard logic, I guess, means an ASIC... so, this is a pretty bad example, isn't it?) would be cents on the dollar in a fair comparison.  It's also on the order of 50-200ns response time, whereas the optimal solution would be on the order of the logic family's characteristics (say, 20-50ns for 74LS or HC, down to a few ns or sub-ns for LVC, ECL and so on).  Or without an ASIC, implementing it with a standard logic family (using discrete gates and adders and such) might have comparable delay to the memory (i.e., several times the logic family's basic delay, so ~100-200ns for HC), but could still be quite a bit faster in other families (<10ns for LVC, ECL, etc.?).

And, true, you probably don't even need that kind of speed.  Say this were part of a classical microprocessor system, where you're monitoring a peripheral input, and communicating with a parallel bus.  Perhaps the input is merely polled every so often: it might be perfectly reasonable to have the processor wait a few cycles (potentially several us) before releasing the data bus.  In that time, you could implement not only a static (combinational) solution, but an iterated solution as well (i.e., accumulating "register <= register + bit[N]" -- only need a register, counter and mux, and lg(N) full adders, to complete in N cycles), or even use a secondary MCU for the same computation.

The absolute worst part about using an MCU is timing.  You cannot build a digital logic circuit to any kind of performance, if you can't count on the timing characteristics of the logic you're using.  Can you imagine building a computer out of gates, where the RTL* is implemented as software loops on individual MCUs?

*Register Transfer Level, i.e., more or less, a high level / MSI/LSI building block implementation.  Registers, adders, muxes, those sorts of things.

Even if you are careful with your software implementations, the best you can do is trigger an interrupt from a given event (say a clock edge).  And even in the lowest latency MCUs, this burns many cycles.  True, those cycles may be at 50 or 100MHz internal clock, but even just reading ports will take more and more cycles, and pretty soon, by the time you've finished implementing your function and written it to the output ports, it's taking 10 or 20us, and probably the elapsed time varies nondeterministically, too! (I.e., the result doesn't arrive consistently following the 'request' event.)  Trying to inspect the results with traditional methods (logic source, analyzer) will be maddening, because you'll have some ports changing before others, and the delay is flopping around, and...

True, you can very easily make something that behaves like, say, an LED display driver.  And it'll work statically.  And often times, that's all that matters.  But that's no challenge.  That's trivial, and hardly worth discussing.  If something is computable, Turing Completeness guarantees that it can be done, eventually (given enough memory, anyway).  Where the challenge lies, is in doing it quickly.  And more practically, computer engineering has to do with doing it, and quickly, AND cheaply.

To put it another way, I'd be impressed if that little PIC-faking-a-display-driver (different thread) were capable of being used in a muxed display.  Can it change state, coherently, in under a millisecond?  How about in ten microseconds or less?

Not to demean the fake-display-driver project, because it's still interesting.  But for other reasons.  The software is likely wholly unremarkable (as stated on the project page by its own author, no less -- not in the same words, but I expect this statement would not be found untrue, either).

Tim

[paulie]

Like I said before this would only take a dozen or so lines of code. And consider that you can program a $1 MCU with nothing more than a serial port instead of $200 prom programmer. Anybody that is not able to implement this in a few minutes or unable to avoid bugs in a program that small is in the wrong hobby.

Though I guess it could just be an emotional issue. MCU-phobia!

[codeboy2k]

Like I said before this would only take a dozen or so lines of code. And consider that you can program a $1 MCU with nothing more than a serial port instead of $200 prom programmer. Anybody that is not able to implement this in a few minutes or unable to avoid bugs in a program that small is in the wrong hobby.

Though I guess it could just be an emotional issue. MCU-phobia!

I don't consider myself MCU phobic.  They have their place. In this case they may be OK to use too, as I already said. 

My position is simply that there are conditions under which an MCU may not be appropriate, and we don't know in this case.

It's not about being able to write bug-free code, but rather what are the system requirements, as that dictates to me what is appropriate to use here. Previously I posted that a (EE)PROM seems like the best solution. I said that in absence of any other knowledge about the system, to provide a black-box solution to a majority-N decoder where N=10. The PROM provides guaranteed timing and will be bug-free and completely deterministic. It can be proven to be correct.  It will not glitch.  This is the right solution if we know nothing else about the system.

If glitches don't matter, if timing is not a problem, if the system is "slow" enough, if it doesn't need to be deterministic (in both output and timing relationships), and doesn't need to be provably correct, then an MCU is probably a better solution, as it's likely much cheaper and easier to program as you've said.

My opinion on this matter is simply that cheaper isn't always better and that there are other considerations too.

Cheers!

[Retep]

It's not about being able to write bug-free code, but rather what are the system requirements, as that dictates to me what is appropriate to use here. Previously I posted that a (EE)PROM seems like the best solution. I said that in absence of any other knowledge about the system, to provide a black-box solution to a majority-N decoder where N=10. The PROM provides guaranteed timing and will be bug-free and completely deterministic. It can be proven to be correct.  It will not glitch.  This is the right solution if we know nothing else about the system.

If you don't know nothing else about the system you can't say if it is the right solution or that one solution is better than the other. Period.

It may very well be that are other criteria that make that solution unacceptable. For example with (E)PROMs you have to consider access time, during which the data outputs are undefined, thus potentially incorrect for some time after the inputs have changed. Is that acceptable? Who knows? It might be that the inputs come from switches, in that case one has to consider debouncing, which (E)PROM don't do. There might be size (footprint), power, flexibility and/or cost constraints for which (E)PROM memory might be suboptimal or even unacceptable...etc.

The bottom line is that it is important for the TS to provide criteria, or at least provide relevant context from which criteria can be derived, so people can assess if a potential solution is acceptable and/or optimal for the problem. Often the "why" is more useful information than the "what".

[codeboy2k]

If you don't know nothing else about the system you can't say if it is the right solution or that one solution is better than the other. Period

True. I concede that. 

Yes, the TS (or in this case OP) needs to provide the details needed to make the best decision.

[T3sl4co1l]

Considering all solutions, and in the absence of additional constraints, I agree: the ROM solution is an excellent way to go.  Generally fast enough to interface with most glue logic applications, without adding too much in timing constraints or losing deterministic behavior (given that the outputs may glitch during the propagation delay -- which is explicitly stated in the datasheet, so that's foreseeable and can be addressed).

Using the microcomputer example -- you could put it on the bus, without having to add too much logic for wait-states.  Not that this example is relevant anymore, as 4MHz parallel-bus microprocessors have gone the way of the dodo for >30 years now in embedded applications -- but, if you're familiar with the tech, it's still a good reference to measure against.

The worst part about MCUs, to me personally, is the lack of consistent timing (just try to do precision real time DSP with an average MCU core*), the massive number of permutations through which code can be written, tested (and left untested!), and pass or fail; and therefore the lack of provable correctness and performance.

*Using a real DSP core is probably cheating, because they would provide DMAs for consistent timing.  If you removed that, and still drove the output timing directly from software, you would have the same problems as with any other core.

Information and bandwidth are much the same thing, and this point should never be forgotten: as I have said before, use only the bandwidth [or information] that you require!  If you provide unlimited bandwidth from the outside world, into a jellybean op-amp for example, expect problems (e.g., an LM358 will rectify RF on the input and output pins!).  Analogously for digital design: provide only as many logic states or inputs/outputs as required!  An MCU with a mere 128 bits of memory (including registers) has a potential 2^128 states -- how can you ever possibly ensure, within the present age of the universe, that every one of those states is recoverable?  And that's not even to count hidden states (anything not explicitly in the datasheet?) like stuck latches and incomplete powerup (example: apparently ATmegas were notorious for POR/BOD problems under some conditions, like slow voltage rise/fall?).

Tim

[hamster_nz]

Given the same constraints, I would do this using 6 x 74LS83.

IC1 - 7483,

Connect I1, I2, I3 to the adders C0,A1 and B1.  The outputs S2:S1 will contain the number of inputs that are high. Call this D2 and D1.

IC2 -  7483,

Connect I4, I5, I6 to the adders C0,A1 and B1.  The outputs S2:S1 will contain the number of inputs that are high. Call this E2 and E1

Connect  D2:D1 to A4:A3. Connect E2:E1 to B4:B3. The outputs of C4:S4:S3 will be the the number of inputs in I6:I1 that are set. Call this F3:F2:F1.

IC3 & IC4 - 74LS83.

Wire them as above, to count I12:I7 giving G3:G2:G1.

IC5 - 74LS83
Wire it to add 0:F3:F2:Fa and 0:G3:G2:G1, giving the count of up to 12 input bits as H4:H3:H2:H1.

IC6 - 74LS83
Add H4:H3:H2:H1 to a constant, and use C4 as the "exceeded count" output The constant should be 16-n, where n is the number of inputs you want to trigger the overflow. For example, the constant of 13 (0b1101) will overflow when any three inputs are asserted. If you wanted to avoid this magic constant you could use four inverters plus the carry input on IC6 to calculate the "16-n' constant from a four bit input.

All the usual provisos apply

[zapta]

Analogously for digital design: provide only as many logic states or inputs/outputs as required!  An MCU with a mere 128 bits of memory (including registers) has a potential 2^128 states -- how can you ever possibly ensure, within the present age of the universe, that every one of those states is recoverable?

Come on, MCUs and computers run the world as we know it, from car engines to this very forum.

[T3sl4co1l]

Analogously for digital design: provide only as many logic states or inputs/outputs as required!  An MCU with a mere 128 bits of memory (including registers) has a potential 2^128 states -- how can you ever possibly ensure, within the present age of the universe, that every one of those states is recoverable?

Come on, MCUs and computers run the world as we know it, from car engines to this very forum.

And how often do those systems need to be restarted on various levels (resetting program state, rebooting computers, clearing network states..)?  If the answer is something other than "never", I think you've illustrated my point.

Tim

[zapta]

Analogously for digital design: provide only as many logic states or inputs/outputs as required!  An MCU with a mere 128 bits of memory (including registers) has a potential 2^128 states -- how can you ever possibly ensure, within the present age of the universe, that every one of those states is recoverable?

Come on, MCUs and computers run the world as we know it, from car engines to this very forum.

And how often do those systems need to be restarted on various levels (resetting program state, rebooting computers, clearing network states..)?  If the answer is something other than "never", I think you've illustrated my point.

Tim

Look at the big picture, not just the failure. Overall MCUs and computers bring plenty of good in all aspects of our lives, including mission critical applications despite the ginormous 2^n number of unique states in the various memory layers.

[Mr Smiley]

Hi all,

I'm looking for something like an OR gate, but that needs at least N inputs to be high for the output to be high. N would be something like 2-3 and the number of inputs would be about 10. I am curious about doing it in discrete gates, not HDLs.

Is this is a solved problem? Or perhaps it is one of those problems with a solution so complicated that it is useless?

Of all the answers given, has nobody noticed that an OR gate won't do what he wants, you only need a single high on any input to give a logic high out.

To answer the question we have to see the truth table.

Also he's talking 'about' x inputs,  with his x being about 11, about not being a logical and definitive number; even so, for a micro your looking at two 8 bit ports.

 

[Zero999]

Analogously for digital design: provide only as many logic states or inputs/outputs as required!  An MCU with a mere 128 bits of memory (including registers) has a potential 2^128 states -- how can you ever possibly ensure, within the present age of the universe, that every one of those states is recoverable?

Come on, MCUs and computers run the world as we know it, from car engines to this very forum.

And how often do those systems need to be restarted on various levels (resetting program state, rebooting computers, clearing network states..)?  If the answer is something other than "never", I think you've illustrated my point.

Tim

Look at the big picture, not just the failure. Overall MCUs and computers bring plenty of good in all aspects of our lives, including mission critical applications despite the ginormous 2^n number of unique states in the various memory layers.

That doesn't change the fact that MCUs aren't always the best solution, especially for parallel processing where they're very slow. Given no other information a ROM is definitely the best solution in this case.

[zapta]

That doesn't change the fact that MCUs aren't always the best solution, especially for parallel processing where they're very slow. Given no other information a ROM is definitely the best solution in this case.

Of course not. ROM output take time to stabilize which means that the output is undefined for some period after an input change. This can result in false positives or false negatives.

Also, ROM size grows exponentially with the number of inputs. Not scalable.

Engineering is not a white and black thing.

[paulie]

MCUs aren't always the best solution

True.But these days with quite fast chips available for as little as 15 cents they are ALMOST always the best solution. Certainly with no timing constraints specified in the OP they are the cheapest, easiest to program (no $200 prom or fpga burner required), lowest component count, i.e. BEST solution here.

And all things being equal the CHEAPEST solution IMO is also always the best one. Of course there are those who will insist a more costly item is better even if there is no performance, quality, or reliability advantage. Apparently the word "expensive" just automatically means it's better.

It's hard to tell if people here really believe some of the things they are saying or just typical internet argumentation. I've recently gotten into similar discussion on another forum for insisting an MCU was better choice in a certain NE555 application. It was cheaper and fewer parts than the proposed NE555 circuit but that nasty "c" word (coding) reared it's ugly head again. LOL

[T3sl4co1l]

Look at the big picture, not just the failure. Overall MCUs and computers bring plenty of good in all aspects of our lives, including mission critical applications despite the ginormous 2^n number of unique states in the various memory layers.

My point isn't about pictures, big or small: you also seem to be giving it much more breadth than it concerns, too!

Regarding mission-critical applications: they work very hard to attempt to prove, or at least verify, the correctness of their code.  It's very hard work, but an excellent example of well disciplined design process.

Sometimes, they'll also use redundant or lock-stepped cores, just in case the hardware itself isn't all there, either!  (Radiation damage and bit-flipping and such.)

Done very carefully, those 2^N states can be pared down substantially, making testing nearly practical (for instance, certain memory addresses may be provably inconsequential, where they're simply not read at all, or the value that is read is handled in a complete manner, along with everything else relating to it).

In the end, even mission-critical applications rarely achieve such level of testing; more than a few probes and landers have flown in space, and some retarded bone-up floored them when it came time to operate!  Even as hard as they try, it's simply not possible to prove correctness.  Which was the point: provably correct is an exceeding narrow subset of "practical programs".  For those rare occasions where you need it, you're probably better looking at a different architecture altogether, because so many states floating around is just a bad idea.  Fortunately, most applications don't, and we're just stuck with dealing with the occasional (sometimes more frequent than we'd like) bugs and resets and such.

Tim