# 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

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 ...

8

A FSM is a structured method of constructing a sequential machine. The machine can only exist in a fixed number of discrete states - ie ‘finite state’. FSMs can be formally proven for correctness. Other benefits are that they are easy to construct in code and debug. Going from a state diagram to writing code is a straightforward process. Traffic lights are a ...

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

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

"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

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

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

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.

4

As written there, "Moore outputs are synchronous with the clock, only changing with state transitions. Mealy outputs are asynchronous and can change in response to any changes in the inputs, independent of the clock." In your specific case, Q0 and Q1 change sinchronously with the clock (because of the presence of the two D flip-flops), hence it's a Moore ...

4

If you have to split an operation across multiple clock cycles, you have two options : pipelining, and sequencing Let's consider a mythical operation consisting of four multiplications , for example - where each multiplication (except the first) requires the output of the previous multiplication as one of its inputs. However the basic ideas are much more ...

4

Yes, the one hot method. For a state diagram of N states, use N d-type flipflops and a code that has N - 1 zeroes and a single 1. When you are in S0 then the S0 flipflop has a '1' in it. It is hot. This method has the cost of needing one flipflop per state but does allow design by inspection rather than needing to draw up lots of tables. The method has ...

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