4 ms·

"Aha! moment". Well, I have to say that, for me, this came with the practice, not the study, of FSM's and, in particular Turing Machines. I could not imagine

"Aha! moment". Well, I have to say that, for me, this came with the practice, not the study, of FSM's and, in particular Turing Machines. I could not imagine a world without them. Look around you. While I studied FA formally it never really clicked until years later. Sometimes you don't really learn until you are holding a cat by the tail. I should say that I've always called them "FSM" when, in most cases, in reality I was using a TM. A TM, of course, is also an FSM, so I'm at peace with my loose use of the term. I really started to use FSM's with great frequency while working on developing hardware with FPGA's. Everything from reset modules to FIFO and SD/DD RAM controllers and more benefit from FSM's. They greatly reduce complexity and allow you to express very complex logic in code that can actually be followed and understood. For some reason FSM's feel more "at home" in hardware rather than software for me (although I use them extensively in software as well). There's something about looking at the definition of an FSM's states and realizing that it's a bunch of single bits (flip-flops) that makes it real: // Fictitious example parameter STATE_RESET = 5'b00001; parameter STATE_STOP = 5'b00010; parameter STATE_FORWARD = 5'b00100; parameter STATE_TURN_RIGHT = 5'b01000; parameter STATE_TURN_LEFT = 5'b10000; Later, when you code the FSM --and if you've been doing this for a while-- you can look at the code and almost literally see the flip-flops and latches forming the structure: always @ (posedge SOME_CLK) begin case(state) STATE_RESET: begin // Do something in this state end STATE_STOP: begin // Do something in this state end STATE_FORWARD: begin // Do something in this state end STATE_TURN_RIGHT: begin // Do something in this state end STATE_TURN_LEFT: begin // Do something in this state end endcase end It's really cool. Geeking-out just thinking about it. In the software front, everything from communications packet processors to email address validation and menu processors benefit from using FSM's. I like the application of FSM's to web app controllers where you can encode a lot of knowledge and sophistication into your control module and not end-up with a huge rats-nest of procedural code that is nearly impossible to understand and maintain. I have to admit being guilty of "thinking like an FSM" at times to the extent that I see the opportunity to use them in almost every project, hardware or software. Again, today I could not imagine designing hardware or writing software without FSM's.

csense 14y ago
What's the logic behind defining your states as bitflags instead of enums? I would typically write STATE_RESET = 0, STATE_STOP = 1, STATE_FORWARD = 2, STATE_TURN_RIGHT = 3, STATE_TURN_LEFT = 4... Unless, of course, you're doing an NFA and have a reason to superimpose states (i.e. be in STATE_TURN_RIGHT and STATE_TURN_LEFT simultaneously).
- robomartin 14y ago
  Ah, remember, this is hardware and, this is Verilog, not C. What you are looking at is called "one-hot" encoding. If you enumerate your states you are asking Verilog to infer a register to hold your states. This also means that you have to have additional (slow) combinatorial logic to identify which state you are in. With one-hot encoding each state is represented by a single and discrete flip-flop (FF) and no combinatorial logic is required. If you have 33 states the state machine has 33 FF's and only one of them can be "hot" or set to "1" at any given time. One-hot encoding is faster, and offer a lot of other advantages (ease of debugging, ease of optimization, timing closure, etc.). Here's a good resource: http://www.xilinx.com/txpatches/pub/documentation/xactstep6/hdlsynth.pdf http://www.xilinx.com/txpatches/pub/documentation/xactstep6/... Go directly to Appendix A.
  - csense 14y ago
    I've never actually done hardware design. I last looked at it a few years ago and it seemed really confusing. What I really want is an FPGA on a board like the Raspberry Pi, where I can just plug in USB, network and power, copy-paste some code from a tutorial, have it run, and start learning HDL from that point. I want to be able to develop an FPGA program that can maybe do a specific bitwise computation faster than a CPU or GPU (like SHA hashes for bitcoin mining, but this is just one example) and send inputs and outputs back and forth with a regular computer. Without also having to design and solder my own circuit board in order to do it. It seems, though, like as soon as you say the word "FPGA," people automatically assume you have a ton of experience and equipment for building your own circuit boards. Which I really don't. And learning this on the same project learning HDL seems like it would really make things kinda hard. "It doesn't work" could mean anything from a solder blob shorting two wires, to some screw-up earlier in the process having destroyed a component and now it'll never work even if you do the rest of it correctly (and you have to increase your budget to replace the now-fried chip), to a failure to understand something about HDL, to some electromagnetic bug in the design of the circuit (like "you need a capacitor here, you need an inductor there, your resistor is 100x too big or too small")...a bug in the HDL of course...or it could be a bug in the USB interface hardware/software I made on the board...or in the custom USB driver I wrote (I've also never actually written a hardware driver before) running on the general-purpose computer...In short, it seems like, to get started teaching yourself hardware design, you have to have approximately one university degree worth of hardware design knowledge already. Learning HDL, I want to be able to eliminate all of the above sources of error but "if it doesn't work, it must be a bug in my HDL code." Bootstrapping software programming through self-learning is easy enough that probably at least tens of thousands of middle and high school kids do it on their own every year (I was one of them). Bootstrapping GPU programming is a little harder but still seems doable (I haven't actually done more than dabbling, though). Bootstrapping FPGA should be just as easy, but it isn't. I haven't been able to find what hardware I should buy to do this, and I haven't even been able to figure out what search terms I should be using. It's been a few years since I looked, though, so maybe I should look again.

csense 14y ago

What's the logic behind defining your states as bitflags instead of enums? I would typically write STATE_RESET = 0, STATE_STOP = 1, STATE_FORWARD = 2, STATE_TURN_RIGHT = 3, STATE_TURN_LEFT = 4... Unless, of course, you're doing an NFA and have a reason to superimpose states (i.e. be in STATE_TURN_RIGHT and STATE_TURN_LEFT simultaneously).

robomartin 14y ago
Ah, remember, this is hardware and, this is Verilog, not C. What you are looking at is called "one-hot" encoding. If you enumerate your states you are asking Verilog to infer a register to hold your states. This also means that you have to have additional (slow) combinatorial logic to identify which state you are in. With one-hot encoding each state is represented by a single and discrete flip-flop (FF) and no combinatorial logic is required. If you have 33 states the state machine has 33 FF's and only one of them can be "hot" or set to "1" at any given time. One-hot encoding is faster, and offer a lot of other advantages (ease of debugging, ease of optimization, timing closure, etc.). Here's a good resource: http://www.xilinx.com/txpatches/pub/documentation/xactstep6/hdlsynth.pdf http://www.xilinx.com/txpatches/pub/documentation/xactstep6/... Go directly to Appendix A.
- csense 14y ago
  I've never actually done hardware design. I last looked at it a few years ago and it seemed really confusing. What I really want is an FPGA on a board like the Raspberry Pi, where I can just plug in USB, network and power, copy-paste some code from a tutorial, have it run, and start learning HDL from that point. I want to be able to develop an FPGA program that can maybe do a specific bitwise computation faster than a CPU or GPU (like SHA hashes for bitcoin mining, but this is just one example) and send inputs and outputs back and forth with a regular computer. Without also having to design and solder my own circuit board in order to do it. It seems, though, like as soon as you say the word "FPGA," people automatically assume you have a ton of experience and equipment for building your own circuit boards. Which I really don't. And learning this on the same project learning HDL seems like it would really make things kinda hard. "It doesn't work" could mean anything from a solder blob shorting two wires, to some screw-up earlier in the process having destroyed a component and now it'll never work even if you do the rest of it correctly (and you have to increase your budget to replace the now-fried chip), to a failure to understand something about HDL, to some electromagnetic bug in the design of the circuit (like "you need a capacitor here, you need an inductor there, your resistor is 100x too big or too small")...a bug in the HDL of course...or it could be a bug in the USB interface hardware/software I made on the board...or in the custom USB driver I wrote (I've also never actually written a hardware driver before) running on the general-purpose computer...In short, it seems like, to get started teaching yourself hardware design, you have to have approximately one university degree worth of hardware design knowledge already. Learning HDL, I want to be able to eliminate all of the above sources of error but "if it doesn't work, it must be a bug in my HDL code." Bootstrapping software programming through self-learning is easy enough that probably at least tens of thousands of middle and high school kids do it on their own every year (I was one of them). Bootstrapping GPU programming is a little harder but still seems doable (I haven't actually done more than dabbling, though). Bootstrapping FPGA should be just as easy, but it isn't. I haven't been able to find what hardware I should buy to do this, and I haven't even been able to figure out what search terms I should be using. It's been a few years since I looked, though, so maybe I should look again.