Real Time Trigger Using A Finite State Machine Having A Counting State

Abstract

An apparatus that searches for a pattern in a signal is disclosed. The apparatus can be used to implement a real time trigger in an instrument such as a high speed oscilloscope. The apparatus includes a symbol generator and a finite state machine (FSM). The symbol generator receives an ordered sequence of signal values and converts the ordered sequence of signal values into an ordered sequence of symbols, each symbol having a plurality of states. The FSM receives the ordered sequence of symbols and generates a match signal if the ordered sequence of symbols includes a target sequence specified by a regular expression that includes a counting limitation on one of the symbol states. The FSM includes a counting state that includes a counter that counts instances of the one of the symbol states.

What is claimed is: 
     
         1 . An apparatus comprising:
 a symbol generator that receives an ordered sequence of signal values and converts said ordered sequence of signal values into an ordered sequence of symbols, each symbol having a plurality of states; and   a finite state machine (FSM) that receives said ordered sequence of symbols and generates a match signal if said ordered sequence of symbols includes a target sequence specified by a regular expression that includes a counting limitation for one of said symbols, wherein   said FSM includes a counting state including a counter that counts instances of said one of said symbol.   
     
     
         2 . The apparatus of  claim 1  wherein said FSM is characterized by an input word and an FSM clock period, and wherein said FSM processes said input word during each FSM clock period, said input word comprising a plurality of said symbols. 
     
     
         3 . The apparatus of  claim 1  wherein said counting limitation comprises a requirement that a precise number of instances of one of said symbol states be present in said target sequence. 
     
     
         4 . The apparatus of  claim 1  wherein said counting limitation comprises a requirement that more than a specified number of instances of one of said symbol states be present in said target sequence. 
     
     
         5 . The apparatus of  claim 1  wherein said counting limitation comprises a requirement that more than a first specified number of said instances of one of said symbol states and less than a second specified number of said instances of said one of said symbols be present in said target sequence. 
     
     
         6 . The apparatus of  claim 1  wherein said FSM has a memory that stores a state table that specifies a next state for said FSM based on a present state for said FSM and said input word currently being processed by said FSM, said state table specifying first and second next states for said FSM when said FSM is in said counting state, said FSM choosing one of said first and second next states based on whether said counting limitation has been satisfied. 
     
     
         7 . The apparatus of  claim 6  wherein said counting limitation is not satisfied if said counter has a value less than a first value or greater than a second value, and wherein said one of said first and second next states that said FSM chooses also depends on whether said counter is less than said first value or greater than said second value. 
     
     
         8 . The apparatus of  claim 1  further comprising a signal digitizer and a signal memory, said signal digitizer receiving a signal and generating said ordered sequence of signal values therefrom, said ordered sequence of signal values being stored in said signal memory. 
     
     
         9 . The apparatus of  claim 8  wherein said signal digitizer generates a first number of signal values during each FSM clock period, each of said first number of signal values being converted to a corresponding symbol during one FSM clock period, and wherein said FSM processes said corresponding symbols as a single input word during one FSM clock period. 
     
     
         10 . The apparatus of  claim 8  further comprising a display controller and a display, said display controller displaying a portion of said signal values on said display in response to said FSM generating said match signal. 
     
     
         11 . The apparatus of  claim 1  wherein said FSM is a Mealy FSM. 
     
     
         12 . A method for operating a data processing system to detect a signal pattern in a signal comprising an ordered sequence of signal values, said method comprising:
 converting said ordered sequence of signal values and converts said ordered sequence of signal values into an ordered sequence of symbols, each symbol having a plurality of states; and   implementing an FSM in said data processing system, said FSM receiving said ordered sequence of symbols and generating a match signal if said ordered sequence of symbols includes a target sequence specified by a regular expression that includes a counting limitation for one of said symbols, wherein   said FSM includes a counting state including a counter that counts instances of said one of said symbol.   
     
     
         13 . The method of  claim 12  wherein said FSM is characterized by an input word and an FSM clock period, and wherein said FSM processes said input word during each FSM clock period, said input word comprising a plurality of said symbols. 
     
     
         14 . The method of  claim 12  wherein said counting limitation comprises a requirement that a precise number of instances of one of said symbol states be present in said target sequence. 
     
     
         15 . The method of  claim 12  wherein said counting limitation comprises a requirement that more than a specified number of instances of one of said symbol states be present in said target sequence. 
     
     
         16 . The method of  claim 12  wherein said counting limitation comprises a requirement that more than a first specified number of said instances of one of said symbol states and less than a second specified number of said instances of said one of said symbols be present in said target sequence. 
     
     
         17 . The method of  claim 1  wherein said FSM has a memory that stores a state table that specifies a next state for said FSM based on a present state for said FSM and said input word currently being processed by said FSM, said state table specifying first and second next states for said FSM when said FSM is in said counting state, said FSM choosing one of said first and second next states based on whether said counting limitation has been satisfied. 
     
     
         18 . The method of  claim 17  wherein said counting limitation is not satisfied if said counter has a value less than a first value or greater than a second value, and wherein said one of said first and second next states that said FSM chooses also depends on whether said counter is less than said first value or greater than said second value. 
     
     
         19 . The method of  claim 12  further comprising a signal digitizer and a signal memory, said signal digitizer receiving a signal and generating said ordered sequence of signal values therefrom, said ordered sequence of signal values being stored in said signal memory. 
     
     
         20 . The method of  claim 9  wherein said signal digitizer generates a first number of signal values during each FSM clock period, each of said first number of signal values being converted to a corresponding symbol during one FSM clock period, and wherein said FSM processes said corresponding symbols as a single input word during one FSM clock period.