1561-5405 10.24151/1561-5405 Proceedings of Universities. Electronics Scientifical and technical journal "Proceedings of Universities. Electronics" Научно-технический журнал «Известия высших учебных заведений. Электроника» 1561-5405 2587-9960 National Research University of Electronic Technology Национальный исследовательский университет "Московский институт электронной техники" 10.24151/1561-5405-2019-24-6-610-618621.3.049.771Algorithm for Compression and Decompression of the FPGA Configuration Bit StreamАлгоритм компрессии и декомпрессии потока конфигурационных данных ПЛИСКузьминов Игорь Васильевич КузьминовИгорь Васильевич VasilevichKuzminov IgorKuzminov Igor VasilevichЛосев Владимир ВячеславовичЛосевВладимир ВячеславовичLosevVladimir V.Vladimir V. LosevНовожилов Иван Сергеевич НовожиловИван Сергеевич SergeevichNovozhilov IvanNovozhilov Ivan SergeevichЧаплыгин Юрий АлександровичЧаплыгинЮрий АлександровичChaplyginYury A.Yury A. ChaplyginНациональный исследовательский университет «МИЭТ», г. Москва, Россия; АО «Научно-исследовательский институт молекулярной электроники», г. Москва, РоссияНациональный исследовательский университет «МИЭТ», г. Москва, РоссияНациональный исследовательский университет «МИЭТ», г. Москва, Россия; АО «Научно-исследовательский институт молекулярной электроники», г. Москва, Россия610618http://ivuz-e.ru/issues/6-_2019/algoritm_kompressii_i_dekompressii_potoka_konfiguratsionnykh_dannykh_plis/

It is necessary to reduce the configuration bit stream volume if there is a need to write several FPGA configurations to the ROM. This leads to decrease in the topological size of the ROM block on the chip. The article discusses the development of the mechanism of compression and decompression of the FPGA configuration bit stream. It has been shown that the stream of configuration data has some regularities. This is due to the presence of a large number of «forbidden» states in the configuration data set, when inadmissible connections of logical elements are formed. The algorithm of compression and decompression of the FPGA configuration bit stream has been proposed. The algorithm is based on the analysis of the FPGA architecture and the compilation of the conversion table using the prefix code commands. The advantage of the algorithm is the search for the most repetitive combinations based on the analysis of the FPGA architecture, instead of searching for the entropy of a random set of configuration data. Another advantage is the relative simplicity of the decoding algorithm, which saves hardware resources for the implementation of the decompression mechanism.

При записи в ПЗУ ряда зашивок ПЛИС возникает необходимость уменьшения объема конфигурационных данных. Это позволяет уменьшить топологический размер блока ПЗУ на кристалле. Существующие алгоритмы компрессии конфигурационных данных базируются на поиске энтропии случайного набора прошивок. В работе предложен механизм компрессии и декомпрессии конфигурационных данных ПЛИС, основанный на особенностях архитектуры. Показано, что поток конфигурационных данных имеет некоторые закономерности, обусловленные большим количеством «запрещенных» состояний в наборе конфигурационных данных, когда образуются недопустимые связи логических элементов. Предложен алгоритм компрессии и декомпрессии потока конфигурационных данных ПЛИС, базирующийся на анализе архитектуры ПЛИС и составлении таблицы перекодировки с помощью команд префиксного кода. Преимуществом алгоритма является поиск наиболее повторяющихся комбинаций на основе анализа архитектуры ПЛИС вместо поиска энтропии случайного набора конфигурационных данных. Алгоритм декодирования характеризуется относительной простотой, что позволяет сэкономить аппаратные ресурсы для реализации механизма декомпрессии.

алгоритм компрессииконфигурационные данные ПЛИСпрефиксное кодирование Шалтырев В.А., Шалтырев К.А., Шагурин И.И. Динамическая реконфигурация ПЛИС с ис-пользованием сжатых битовых потоков // Изв. вузов. Электроника. – 2009. – №2(76). – С. 43–50.Hemnath P., Prabhu V. Compression of FPGA bitstreams using improved RLE algorithm // 2013Intern. Conf. on Information Communication and Embedded Systems (ICICES). IEEE. – 2013. – P. 834–839.Hauck S., Wilson W.D. Runlength compression techniques for FPGA configurations // In Proc. IEEE Symp. Field Program. Custom Comput. Mach. IEEE. – 1999. – P. 286–287.Dandalis A., Prasanna V.K. Configuration compression for FPGA-based embedded systems // IEEE Trans. Very Large Scale Integr. (VLSI) Syst. – 2005. – Vol. 13. – Iss. 12. – P. 1394–1398.Rui Yu, Yibin Li. Compression of FPGA bitstreams using a novel bitmask and RLE algorithm // Interna-tional Journal of Advanced Computational Engineering and Networking. – 2015. – Vol. 3. – Iss. 4. – P. 17–22.Марков А.А. Введение в теорию кодирования. – М.: Наука, 1982. – 192 с.Левитин А.В. Жадные методы: алгоритм Хаффмана // Алгоритмы. Введение в разработку и ана-лиз. – М.: Вильямс, 2006. – Гл. 9. – С. 392–398.Choueka Y., Fraenkel A., Klein S., Segal E. Improved hierarchical bit-vector compression in document retrieval systems // Proc. of ACM Conf. on Research and Development in Information Retrieval. – 1986. – P. 88–96.