Apparatus and method for generating state transition rules for memory efficient programmable pattern matching finite state machine hardware

Number of patents in Portfolio can not be more than 2000

United States of America Patent

PATENT NO 7219319
APP PUB NO 20060253816A1
SERIAL NO

11422520

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

A programmable finite state machine (FSM) includes, in part, first and second memories, and a selection circuit coupled to each of the memories. Upon receiving a (k+m)-bit word representative of the k-bit input symbol and the m-bit current state, the first memory supplies one ore more matching transition rules stored therein. The selection circuit selects the most specific of the supplied rules. The transition rules are stored in the first memory in a ranking order of generality. The second memory receives the selected transition rule and supplies the next state of the FSM. The first memory may be a ternary content addressable memory and the second memory may be a static random access memory. The contents of both the content addressable memory and the static random memory is determined by an algorithm which minimizes the number of terms required to represent the next-state transition functions.

Loading the Abstract Image... loading....

First Claim

See full text

Family

Loading Family data... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
INTEL CORPORATIONSANTA CLARA, CA29226
Sensory Networks, Inc.PALO ALTO, CA5

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Barrie, Robert Matthew Double Bay, AU 22 625
de, Jong Nicholas Bondi Junction, AU 5 85
Gould, Stephen Queens Park, AU 43 755
Williams, Darren Newtown, AU 27 622

Cited Art Landscape

Patent Info (Count) # Cites Year
 
YALE UNIVERSITY (1)
6609189 Cycle segmented prefix circuits 61 1999
 
APPLE INC. (1)
5873097 Update mechanism for computer storage container manager 117 1996
 
MITEL NETWORKS CORPORATION (1)
2002/0131,402 Registering an IP phone with an IP phone switch 12 2001
 
Cadence Design Systems, Inc. (1)
* 7073143 Solving constraint satisfiability problem for circuit designs 10 2001
 
Sensory Networks, Inc. (1)
2005/0114,700 Integrated circuit apparatus and method for high throughput signature based network applications 83 2003
 
TEXAS INSTRUMENTS INCORPORATED (1)
* 5515292 Circuit activity driven state assignment of FSMS implemented in CMOS for low power reliable operations 15 1993
 
XILINX, INC. (1)
5617573 State splitting for level reduction 8 1994
 
LOCKHEED MARTIN CORPORATION (1)
5125098 Finite state-machine employing a content-addressable memory 18 1989
 
RICOH COMPANY, LTD. (2)
5475388 Method and apparatus for using finite state machines to perform channel modulation and error correction and entropy coding 83 1993
5471206 Method and apparatus for parallel decoding and encoding of data 101 1994
 
BINARY SERVICES LIMITED LIABILITY COMPANY (1)
5610812 Contextual tagger utilizing deterministic finite state transducer 97 1994
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (2)
* 6836877 Automatic synthesis script generation for synopsys design compiler 119 1998
6418042 Ternary content addressable memory with compare operand selected according to mask value 40 1998
 
MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD. (1)
* 5926396 Logic synthesis method, semiconductor integrated circuit and arithmetic circuit 19 1996
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
VMWARE, INC. (3)
* 9032398 Online classification of memory pages based on activity level represented by one or more bits 4 2010
* 2012/0011,504 ONLINE CLASSIFICATION OF MEMORY PAGES BASED ON ACTIVITY LEVEL 34 2010
8990531 Multiple time granularity support for online classification of memory pages based on activity level 3 2011
 
Sensory Networks, Inc. (1)
* 7301792 Apparatus and method of ordering state transition rules for memory efficient, programmable, pattern matching finite state machine hardware 7 2006
 
FUJITSU LIMITED (8)
9138143 Annotating medical data represented by characteristic functions 0 2010
9002781 Annotating environmental data represented by characteristic functions 0 2010
* 8930394 Querying sensor data stored as binary decision diagrams 0 2010
8874607 Representing sensor data as binary decision diagrams 0 2010
* 2012/0046,913 REPRESENTING SENSOR DATA AS BINARY DECISION DIAGRAMS 4 2010
* 2012/0047,160 QUERYING SENSOR DATA STORED AS BINARY DECISION DIAGRAMS 2 2010
9176819 Detecting sensor malfunctions using compression analysis of binary decision diagrams 0 2011
9075908 Partitioning medical binary decision diagrams for size optimization 0 2011
 
HUAWEI TECHNOLOGIES CO., LTD. (2)
* 8583961 Method and device for creating pattern matching state machine 0 2010
* 2010/0229,040 METHOD AND DEVICE FOR CREATING PATTERN MATCHING STATE MACHINE 0 2010
 
SIEMENS PRODUCT LIFECYCLE MANAGEMENT SOFTWARE INC. (2)
* 8050986 System and method for determining a quantity mismatch report 1 2006
* 2008/0021,797 Quantity mismatch report 2 2006
 
COMTECH EF DATA CORP. (2)
* 7764205 Decompressing dynamic huffman coded bit streams 4 2008
* 2009/0058,694 Decompressing Dynamic Huffman Coded Bit Streams 0 2008
* Cited By Examiner

Maintenance Fees

Fee Large entity fee small entity fee micro entity fee due date
11.5 Year Payment $7400.00 $3700.00 $1850.00 Nov 15, 2018
Fee Large entity fee small entity fee micro entity fee
Surcharge - 11.5 year - Late payment within 6 months $160.00 $80.00 $40.00
Surcharge after expiration - Late payment is unavoidable $700.00 $350.00 $175.00
Surcharge after expiration - Late payment is unintentional $1,640.00 $820.00 $410.00