# Tag Info

38

Doing a remainder operation in serial fashion is actually quite easy. The key assumption is that the data comes in MSB-first if it's serial. You only need N states to compute a remainder modulo N. Start in the "0" state and if you end up in the "0" state after the last bit (it doesn't matter how many bits there are), the remainder is zero. simulate this ...

24

Designing by rules of thumb you found on the internet someplace is a bad idea. The right way is to understand the issues, them make intelligent tradeoffs. There is nothing wrong with a system that takes a interrupt, clears the hardware condition, then sets a flag for foreground code to do the remainder of the processing when it gets around to it. The ...

17

The first tactic is to architect the overall firmware so that it's OK for interrupts to occur at any time. Having to turn off interrupts so that the foreground code can execute a atomic sequence should be done sparingly. There is often a architectural way around it. However, the machine is there to serve you, not the other way around. General rules of ...

16

You can also design a state machine if the data comes LSB-first: The existence of such a deterministic finite automaton (DFA) directly follows from the other answer, which describes the DFA for MSB-first. Because languages accepted by DFAs are regular and regular languages are known to be closed under reversal (e.g. see here), there must be a DFA which ...

14

Rom(=Read only memory) is a brute force (=absolutely non-minimized) way to implement a combinatoric circuit. Current state bits and inputs together are address, the data stored into that address contains the next state and possible output bits which both can depend on current state and input bits. When one builds a state machine using standard parts, he ...

9

If you're concerned that code for a simple switch() based state machine (SM) will become untidy, you can split it into smaller subroutines. void do_state_s1() { // stuff if ( /* certain contidition */ ) { g_iState = STATE_S2; // transition to another state } } void do_state_s2() { // other stuff if ( /* some other condition */...

8

Based on the answer by @Nick Alexeev, I'm posting a version that is using a function pointer jump table. In my opinion, this is the ideal way to implement a state machine for an embedded system, since it leaves main perfectly clean. And you don't really need the switch, it will actually get optimized away by the compiler into machine code with a similar ...

8

From a discrete logic & HDL perspective: -Mealy machines (generally) have less states. Mealy machines change their output based on their current input and present state, rather than just the present state. However, less states doesn't always mean simpler to implement. -Moore machines may be safer to use, because they change states on the clock edge (...

8

I'd be surprised if there's a big difference on a 32-bit MCU. Avoiding conditional branches could save you a few cycles, but are you really going to succeed or fail based on a few cycles? The number of wait states on your RAM and ROM are probably at least as important. So is the CPU instruction set. Premature optimization is the root of all evil. Start with ...

7

If you need a critical section, you must make sure, that the operation guarding your critical section is atomic and cannot be interrupted. Thus disabling the interrupts, which is most commonly handled by a single processor instruction (and called using a compiler intrinsic function), is one of the safest bets you can take. Depending on your system, there ...

7

One way to come up with the (MSB first) state machine is as follows: The number received so far is N. Assume you know the remainder M = N mod 5. There is a new bit coming in and new value is now N' = N*2 + b. New remainder is then M' = (N*2 + b) mod 5 = (M*2 + b) mod 5. This is easy enough to tabulate by hand: M b | M' ------------------ 0 0 ...

6

If your goal is to have one output at a time go high, you don't need a 9-bit state machine. You should probably either use a 4017 which has 10 outputs that are hit in sequence, and wire it so that it resets when the tenth output goes active, or else use a 4-bit state machine which will progress through nine states, along with a device that will output one ...

6

Even though a design may be considered 'stateless' because there is no explicit state machine, you may still be actually coding a type of state mechanism without explicitly calling it that. For example, flags may be used to indicate if one part of the code is busy or not. In your 'calculator' example, you may not have a state machine, but you may have a flag ...

6

This look like a general representation of sequential logic. It could be Read Only Memory: Any boolean function or logic gates combination can be implemented as a look-up table, and look-up tables are equivalent to pages of read-only memory where the inputs are the address and the outputs are the content of the memory.

6

Edge-triggered FFs generally will not "beat" their own input setup and hold time requirements. You can usually string them directly together to form shift registers of arbitrary lengths. Therefore, your concern is nothing to worry about. The only real issue in this setup is the maximum clock frequency, which is mostly determined by the longest path through ...

6

implementing a bigger state machine would possibly reduce fmax of a design anyway. That would imply a state machine where the "next state" decision is overly complex. That's a criterion for "not well-designed"! One way to deal with such an issue is to use a soft core to implement the state machine in software. A processor is a state ...

5

You start with the basic form: Inputs | Outputs ------------------ | Then you figure out what your inputs and your outputs are. In this case, your inputs are just the current state, and the output is the next state you're going to switch to: Q2 Q1 Q0 | Q2' Q1' Q0' ---------------------- | Now just start filling it in. To get started, ...

5

Jay covered almost everything to answer your question. One 'advantage' of the Moore machine is that it can be implemented in a Look up Table or SRAM memory. If your implementation is on an FPGA, let's say.. this might sometimes make the decision easy for you.

5

"State machine" is a very generic term for any process (electronic or otherwise) whose output is not simply a function of its current inputs, but also depends on its past history. In other words, it has "memory", or internal state information. Electronic state machines started out as analogs of the mechanical state machines (including such examples as ...

5

If you've determined that a section of code must run uninterrupted then, except under unusual circumstances, you should disable interrupts for the minimum duration possible to complete the task, and re-enable them after. Put a flag inside the respective ISR and (instead of disabling the interrupt), set the flag to false before the critical section and ...

5

One hopes the interview question was about how you would solve the problem, rather than the ins and outs of VHDL or Verilog. The language details are straightforward once you have an algorithm. If the number is passed bit by bit with MSB first, then the value of the number modulo 5 can be computed by initialising the state $S=0$ and then accumulating the ...

5

Moore outputs are synchronous with clock. It changes only with state transition at clock edge. Mealy outputs are asynchronous. They can change immediately with input change, independent of the clock. So we can say moore machine is not as "fast" as mealy.

5

If you have a state machine with N states, there are a number of different ways to encode those states as binary logic. One-hot encoding assigns one FF to each state, so it requires N FFs. Only one FF has the value 1 (is "hot") at a time. If at any time, more than one FF is 1, that's an error. Binary encoding assigns sequential integers to the states, and ...

5

Since you appear to be happy to user older technology, you could use a 16-bit xPROM (Flash EPROM or EEPROM if you prefer). Feed the BCD into the address lines and take the result from the bottom 10 bits of the data lines. The hex-file to program the PROM is left as an exercise for the reader.

4

There are two sides to this problem: the algorithmic and the engineering. Algorithmic: How do you determine the amount of each type of coins to give back as a change, such that the total amount of coins is minimized? In this case, there is very simple algorithm: start by giving back the highest value coins. Once the remaining amount of change gets below ...

4

I went ahead and made a testbench to see the behavior of the circuit. Please right click the image to see it more clearly. From my simulation, there is nothing unexpected or strange about the waveform. The state gets correctly initialized by the reset. When TxSync is high the state toggles once every clock cycle. When TxSync is deasserted the state holds a ...

4

First of all, that's a terrible diagram that you want us to analyze — it's essentially unreadable. The key difference between Moore and Mealy is that in a Moore state machine, the outputs depend only on the current state, while in a Mealy state machine, the outputs can also be affected directly by the inputs. In your design, the state is embodied by ...

4

The short answer: Invert your logic. Drive the column select lines with open-drain (or open-collector) logic where the selected column is pulled low and the un-selected columns are floating. When you look at a row, a key-press will be detected by a '0'. Un-pressed keys will be detected by a '1'. Now the details: As EEIngenuity points out, when you press 2 ...

4

With a Moore state machine, the number of possible output combinations (I hesitate to say "output states") is no more than the number of internal states. With a Mealy machine, the number of possible output combinations can be as high as the number of internal states multiplied by the number of input combinations. Whether one is an "advantage" over the ...

4

This is exactly why a Reset signal is added to the system. To bring it to an initial known state. There is no way to avoid it when working with actual hardware. As for simulation, you can add an initial block to the design and initialize the state to whatever you want, but it is not synthesizable.

Only top voted, non community-wiki answers of a minimum length are eligible