The present invention provides techniques for compressing and decompressing data in a programmable circuit. Programmable circuits can be configured according to user design by configuration data. Configuration data is compressed using a compression algorithm to save memory space. When the configuration data is needed, the compressed configuration data is decompressed using a decompressor. A decompressor can decompress configuration data using a variety of decompression algorithms such as arithmetic decoding. In an arithmetic encoding algorithm, symbol probabilities are used to increase compression of the data. The symbol probabilities can be transferred in a header of the encoded data stream and subsequently stored in a symbol probability table. The input of the decompressor may be coupled to a FIFO that temporarily stores the encoded data until it can be used by the decompressor.