# US 5,745,734 A · Method and system for programming a gate array using a compressed configuration bit stream > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 5,745,734 A - Document ID: US5745734A - Status: Granted - Kind: A - Application number: 08/536,901 - Filed: 1995-09-29 - Granted: 1998-04-28 - Earliest claimed: 1995-09-29 - Assignees: International Business Machines Corporation - Inventors: David John Craft; Scott Whitney Gould; Frank Ray Keyser, III; Brian Worth - Web page: https://patentgrep.com/patent/US5745734A ## CPC - G06T 9/005: {Statistical coding, e.g. Huffman, run length coding} - H03M 7/3084: {using adaptive string matching, e.g. the Lempel-Ziv method} - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract A generalized data decompression engine is incorporated within a field programmable gate array ("FPGA"). The generalized data decompression engine uses a general purpose data decompression technique such as, for example, a Lempel-Ziv type technique. During operation, a compressed configuration bit stream is received by the generalized data decompression engine in the FPGA and is decompressed thereby. A resultant decompressed configuration bit stream is then used to program logic cells within the FPGA. ## Claims ### Claim 1 A programmable logic circuit comprising: a plurality of programmable logic resources; a configuration input; and a generalized data decompression engine having a compressed input and a decompressed output, said compressed input being coupled to said configuration input and said decompressed output being coupled to said plurality of programmable logic resources to provide programming thereof, wherein said generalized data decompression engine comprises a Lempel-Ziv decompression engine. ### Claim 2 (depends on 1) The circuit of claim 1, wherein said generalized data decompression engine comprises and ALDC decompression engine. ### Claim 3 A programmable logic circuit comprising: a plurality of programmable logic resources; a configuration input; a generalized data decompression engine having a compressed input and a decompression output, said compressed input being coupled to said configuration input and said decompressed output providing direct run-time personalization of said plurality of programmable logic resources; and a configuration memory for said direct run-time personalization of said plurality of programmable logic resources said configuration memory also comprising a history buffer of said generalized data decompression engine. ### Claim 4 (depends on 3) The circuit of claim 3, wherein said generalized data decompression engine comprises a Lempel-Ziv decompression engine. ### Claim 5 (depends on 3) The circuit of claim 3, wherein said generalized data decompression engine further comprises means for copying data from an already loaded portion of said configuration memory to another portion of said configuration memory. ### Claim 6 (depends on 5) The circuit of claim 5, wherein said means for copying comprises a read address register for storing an address of said configuration memory from which data is to be copied. ### Claim 7 (depends on 6) The circuit of claim 6, further comprising a write address register for storing an address of said configuration memory to which data is to be written. ### Claim 8 (depends on 7) The circuit of claim 7, further comprising an arithmetic logic unit ("ALU") having two inputs, a first input of said two inputs being coupled to said write address register, a second input of said two inputs being coupled to the compressed input of said generalized data decompression engine, an output of said arithmetic logic unit being coupled to said read address register for storing therein an address as an arithmetic function of said first input and said second input. ### Claim 9 (depends on 8) The circuit of claim 8, wherein said read address register and said write address register comprise shift registers. ### Claim 10 (depends on 9) The circuit of claim 9, wherein said ALU comprises a one bit serial ALU wherein said first input, said second input, and said output are each one bit wide. ### Claim 11 (depends on 10) The circuit of claim 10, wherein said arithmetic function comprises a subtraction of said second input from said first input. ### Claim 12 (depends on 11) The circuit of claim 11, wherein said ALU further comprises a borrow out and a carry in, said borrow out coupled to said carry in by a one bit carry/borrow latch. ### Claim 13 (depends on 7) The circuit of claim 7, further comprising a count register for storing a number of words of data to be copied by said means for copying. ### Claim 14 (depends on 13) The circuit of claim 13, further comprising means for incrementing the read register, incrementing the write register and decrementing the count register for each word of data copied of said number of words of data to be copied. ### Claim 15 (depends on 14) The circuit of claim 14, further comprising means for terminating copying upon said count register holding a value of zero. ### Claim 16 A programmable logic circuit comprising: a plurality of programmable logic resources; a configuration input; a generalized data decompression engine having a compressed input and a decompressed output, said compressed input being coupled to said configuration input and said decompressed output being coupled to said plurality of programmable logic resources to provide programming thereof, wherein said generalized data decompression engine comprises serial processing logic and wherein said compressed input of said generalized data decompression engine comprises a serial data input; and a parallel to serial converter including a parallel address output, a parallel data input and a serial data output, said serial data output being coupled to said serial data input of said generalized data decompression engine, said parallel address output and said parallel data input adapted to couple to a parallel organized memory. ### Claim 17 (depends on 16) The circuit of claim 16, wherein said generalized data decompression engine comprises a Lempel-Ziv decompression engine. ### Claim 18 (depends on 16) The circuit of claim 16, further comprising an address shift register coupled to said parallel address output and a serial increment circuit for incrementing an address stored in said address shift register. ### Claim 19 (depends on 18) The circuit of claim 18, further comprising means for simultaneously shifting said address shift register and shifting a data shift register coupling said parallel data input and said serial data output such that serial data is output simultaneous with said address being incremented. ### Claim 20 A programmable logic circuit comprising: a plurality of programmable logic resources; a configuration input; and a generalized data decompression engine having a compressed input and a decompressed output, said compressed input being coupled to said configuration input and said decompressed output being coupled to said plurality of programmable logic resources to provide programming thereof, wherein said circuit comprises an integrated circuit chip having a floorplan, said floorplan having an elongated region separating groups of said plurality of programmable logic resources, said generalized data decompression engine being within said elongated region. ### Claim 21 (depends on 20) The circuit of claim 20, wherein said generalized data decompression engine comprises a Lempel-Ziv decompression engine. ### Claim 22 A method for programming a programmable logic circuit comprising a plurality of programmable logic resources, said method comprising the steps of: (a) receiving a compressed configuration; (b) decompressing said compressed configuration using a generalized data decompression technique to produce a decompressed configuration; and (c) programming said plurality of logic resources using said decompressed configuration, wherein said decompressing step (b) comprises decompressing said configuration using a Lempel-Ziv decompression technique. ### Claim 23 (depends on 22) The method of claim 22, wherein said decompressing step (b) comprises decompressing said configuration using an ALDC decompression technique. ### Claim 24 A method for programming a programmable logic circuit comprising a plurality of programmable logic resources, said method comprising the steps of: (a) receiving a compressed configuration; (b) decompressing said compressed configuration using a generalized data decompression technique to produce a decompressed configuration; and (c) programming said plurality of logic resources using said decompressed configuration, wherein said programmable logic circuit further comprises a configuration memory for direct run-time personalization of said plurality of programmable logic resources, said method further including accessing said configuration memory as a history buffer during said decompressing step (b). ### Claim 25 (depends on 24) The method of claim 24, wherein said decompressing step (b) comprises decompressing said configuration using a Lempel-Ziv decompression technique. ### Claim 26 (depends on 24) The method of claim 24, further comprising copying data from an already loaded portion of said configuration memory to another portion of said configuration memory. ### Claim 27 (depends on 26) The method of claim 26, wherein said programmable logic circuit further comprises a read address register, said method further comprising storing an address of said configuration memory from which data is to be copied from in said read address register. ### Claim 28 (depends on 27) The method of claim 27, wherein said programmable logic circuit further comprises a write address register, said method further comprising storing an address of said configuration memory to which data is to be written in said write address register. ### Claim 29 (depends on 28) The method of claim 28, wherein said programmable logic circuit further comprises an arithmetic logic unit ("ALU") said method further including subtracting a history offset from a value within said write address register using said ALU, and storing a result in said read address register. ### Claim 30 (depends on 29) The method of claim 29, wherein said arithmetic logic unit comprises a one bit serial arithmetic logic unit such that said subtracting comprises subtracting using serial processing. ### Claim 31 (depends on 30) The method of claim 30, wherein said arithmetic logic unit further comprises a borrow out and a carry in, said method further comprising passing said borrow out to said carry in during said subtracting using serial processing. ### Claim 32 (depends on 28) The method of claim 28, wherein said programmable logic circuit further comprises a count register, said method further comprising storing a number of words of data to be copied in said count register. ### Claim 33 (depends on 32) The method of claim 32, further comprising incrementing the read register, incrementing the write register and decrementing the count register for each word of data copied of said number of words of data to be copied. ### Claim 34 (depends on 33) The method of claim 33, further comprising terminating said copying upon said count register holding a value of zero. ### Claim 35 A method for programming a programmable logic circuit comprising a plurality of programmable logic resources said method comprising the steps of: (a) receiving a compressed configuration; (b) decompressing said compressed configuration using a generalized data decompression technique to produce a decompressed configuration; and (c) programming said plurality of logic resources using said decompressed configuration, wherein said compressed configuration comprises a serial bit stream, said programmable logic circuit further comprising a parallel to serial converter including a parallel address output, a parallel data input and a serial data output for generating said serial bit stream, said parallel address ouptut and said parallel data input adapted to couple to a parallel organized memory, said method further including serializing said parallel data input to produce said serial bit stream. ### Claim 36 (depends on 35) The method of claim 35, wherein said decompressing step (b) comprises decompressing said configuration using a Lempel-Ziv decompression technique. ### Claim 37 (depends on 35) The method of claim 35, further comprising incrementing an address of said parallel address output by shifting said address through serial incrementer logic. ### Claim 38 (depends on 37) The method of claim 37, further comprising simultaneously shifting said address and shifting a data value of said parallel data input such that serial data is output simultaneous with said address being incremented. ### Claim 39 A method for reducing the amount of configuration information needed to configure a programmable logic circuit comprising the steps of: (a) compressing a configuration for the programmable logic circuit using a generalized compression technique to produce a compressed configuration; and (b) transferring said compressed configuration to a configuration storage device that facilitates loading of the programmable logic circuit, wherein said compressing step (a) comprises compressing said configuration with a Lempel-Ziv compression technique.