Apparatus and method of ordering 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 7301792
APP PUB NO 20060221658A1
SERIAL NO

11422529

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 619
de, Jong Nicholas Bondi Junction, AU 5 84
Gould, Stephen Killara, AU 43 754
Williams, Darren Newtown, AU 27 616

Cited Art Landscape

Patent Info (Count) # Cites Year
 
YALE UNIVERSITY (1)
* 6609189 Cycle segmented prefix circuits 60 1999
 
MEDIATEK INC. (1)
* 6131151 Processing high-speed digital datastreams with reduced memory 12 1997
 
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
 
MINDSPEED TECHNOLOGIES, LLC (1)
* 6442672 Method for dynamic allocation and efficient sharing of functional unit datapaths 41 1998
 
Sensory Networks, Inc. (3)
2005/0114,700 Integrated circuit apparatus and method for high throughput signature based network applications 83 2003
* 7082044 Apparatus and method for memory efficient, programmable, pattern matching finite state machine hardware 28 2004
* 7219319 Apparatus and method for generating state transition rules for memory efficient programmable pattern matching finite state machine hardware 12 2006
 
XILINX, INC. (1)
5617573 State splitting for level reduction 8 1994
 
FUJITSU LIMITED (1)
* 6742107 Dynamically configured processing of composite stream input data using next conversion determining state transition table searched by converted input data 11 2001
 
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
 
APPLE INC. (1)
5873097 Update mechanism for computer storage container manager 117 1996
 
LOCKHEED MARTIN CORPORATION (1)
5125098 Finite state-machine employing a content-addressable memory 18 1989
 
BINARY SERVICES LIMITED LIABILITY COMPANY (1)
5610812 Contextual tagger utilizing deterministic finite state transducer 97 1994
 
MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD. (1)
* 5926396 Logic synthesis method, semiconductor integrated circuit and arithmetic circuit 19 1996
 
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
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
THE REGENTS OF THE UNIVERSITY OF CALIFORNIA (2)
* 8010481 Pattern matching technique for high throughput network processing 1 2007
* 2007/0233,628 Pattern matching technique for high throughput network processing 17 2007
 
THE BOEING COMPANY (3)
* 8442931 Graph-based data search 0 2008
* 2010/0138,375 Graph-Based Data Search 3 2008
8914320 Graph generation method for graph-based search 0 2013
 
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
 
GSI TECHNOLOGY INC. (3)
9076527 Charge sharing in a TCAM array 0 2011
8908465 Using storage cells to perform computation 0 2012
* 2012/0243,284 USING STORAGE CELLS TO PERFORM COMPUTATION 0 2012
 
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 May 27, 2019
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