Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What is the enlightenment I'm supposed to attain after studying finite automata?

cstheory.stackexchange.com

Post reply on HN
Print view View original

61–66 of 66 posts

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#61

Post by makomk »

robomartin wrote: post #54
csense wrote: post #52

Earlier quoted context omitted.

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

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 combin…

Of course, a more subtle aspect of state machine design is that Xilinx's tools can actually change the encoding your state machine uses behind the scenes. I actually traced a fun and very intermittent stability issue in one design to this. (Bitcoin mining stuff which used a state machine for clock domain crossing; the Xilinx tools replaced a safe state machine that could handle getting into an invalid state with one that couldn't.)

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#62

Post by robomartin »

csense wrote: post #59
robomartin wrote: post #54

Earlier quoted context omitted.

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 combin…

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…

Honestly, there's absolutely nothing that would prevent you from learning HDL. There are a number of excellent development boards and tutorials. Start here:

http://www.xilinx.com/university/students/index.htm

The issue with doing higher-level work is that you really need to understand circuit design and implementation. A lot of what you do in an FPGA is to type out text that looks like code but in reality is a "secret contract" with the compiler for it to "infer" the circuit you want. In many ways you could say that there are idioms that you learn that will result in specific circuit constructs once they go through one turn of the wheel.

Then there's the issue of optimization. Sometimes you just don't get the performance you want and have to resort to, effectively, hand-wiring stuff in code. Whether VHDL or Verilog, you have the ability to literally hand-wire FPGA internals to build circuits that usually perform or place better than the what the tools can do:

(sorry, this is long)

    module ADDER
    #(parameter WIDTH = 8)
    (
         input wire CLK,
         input wire CE,
        input wire RST,
        input wire CIN,
         input wire [WIDTH - 1:0] A,
        input wire [WIDTH - 1:0] B,
        output wire [WIDTH:0] SUM
    );

    genvar i;

    wire [WIDTH - 1:0] xor2;
    wire [WIDTH:0] cy;
    wire [WIDTH - 1:0] xorcy;

    assign cy[0] = CIN;

    generate
    for(i=0; i 
    endmodule

    //synthesis attribute LUT_MAP of myXOR2 is YES;  
    module myXOR2
    (
      output O,
      input I0,
      input I1
    );

    assign O = I0 ^ I1;

    endmodule
That's the kind of thing you have to do if you have to squeeze the last MHz in performance out of an FPGA. That code was part of an FIR filter I designed that, about ten years ago, could not break 150MHz using the "hey compiler, you figure it out" approach. If I remember correctly, the hand-wired filter easily did 200MHz.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#63

Post by robomartin »

makomk wrote: post #61
robomartin wrote: post #54

Earlier quoted context omitted.

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 combin…

Of course, a more subtle aspect of state machine design is that Xilinx's tools can actually change the encoding your state machine uses behind the scenes. I actually traced a fun and very intermittent stability issue in one design to this. (Bitcoin mining stuff which used a state machine for clock domain crossing; the Xilinx tools replaced a safe state machine that could handle getting into an invalid state with one…

That's always fun. You just have to know your tools. That's why I tend to be very verbose and explicit in some aspects of my FPGA work. I rather not-so-gently guide the tools towards what I want them to infer vs. what they sometimes think I want them to infer.

Circuit inference is one aspect of HDL that sets it apart from writing software. To begin with, you are describing hardware and have to be aware of and live within the constraints it imposes. Then there's this inference thing that I've come to call my "secret contract" with the compiler: I say X and we agree that it is going to implement X12345 and we are all happy.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#64

Post by mturmon »

jacquesm wrote: post #57
aaronblohowiak wrote: post #44

Earlier quoted context omitted.

Where is the infinite tape? Finite automata are as capable, in the real world, as Turing-like machines, because it is impossible to fabricate a machine with infinite storage.

Turing machines have infinite storage by definition, no such machine has ever been built (we're using approximations), real world restrictions do not apply to imaginary constructs. If a Turing machine were not defined that way then you'd have to set some upper limit to the size of the tape and that in turn would have odd implications for what would be considered 'computable'. By making the tape infinite by definition…

Indeed, we have done everything we can to provide ways to keep the illusion of running on a Turing machine going -- I'm thinking about mmap(), swapping to disk, tape robots, and databases, among others.

Yes, Virginia, you can always obtain more memory.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#65

Post by krichman »

makomk wrote: post #60
joe_the_user wrote: post #58

Earlier quoted context omitted.

Yes, It seems like both Wikipedia and Stack Overflow are done, at least approximately. It is just that Wikipedia has at least some structures that have adapted to being done while it seem that SO framework never considered the possibility of the "frontier of general questions" being settled.

Wikipedia hasn't adapted as well to being "done" as you might think. For instance, there's apparently at least one editor who just goes around Wikipedia deleting random sections from articles that appear to be uncited. He never adds anything, any contributions come from actual subject area experts who have to take time away from editing other articles to deal with the mess he leaves behind. The Wikipedia bureaucracy…

Those two websites are case studies of the Peter Principle.

Re: What is the enlightenment I'm supposed to attain after studying finite automata?

#66

Post by ruchir »

mcmatterson wrote: post #12

Honestly, my answer to this came about many years after living through a very theoretical CS undergrad, by way of a chapter in Charles Petzold's book, 'Code' (of all things. I originally bought the book for my dad to help him understand 'what it was I did all day'). Basically, the insight centered around the physicality of how FA are taught; FA are usually taught by thinking of the FA itself as being fixed in space,…

I think Turing's key insight was that a special FA with a tape mechanism could be devised that could imitate any other FA. The power of this FA in imitating other FAs is limited only by the length of the tape.

However the improvement of this construction over any specific FA is that you have a device that can run any FA. As the length of the tape increases you have a device that can imitate the any and all possible FAs.

The CPU is precisely this FA which can imitate any other FA. The tape is memory.

However it is important to note that, at the end of it, any specific program that is being run on finite memory is still an FA.

Post reply on HN