Hardware implementation of code converters designed to reduce the length of binary encoded words. (English. Russian original) Zbl 1533.68425
Program. Comput. Softw. 49, No. 4, 247-267 (2023); translation from Programm. Inzh. 13, No. 8 (2022).
Summary: The problems of synthesis of combinational circuits of code converters designed to reduce the length of words from a given set of encoded binary words is considered. The encoding assumes that different binary words will be encoded by different binary codes of shorter length. Code converters of this type are designed to reduce the length of binary words transmitted in digital systems over data buses when the bit depth of the transmitted words exceeds the bit depth of the data bus. For example, 18-bit or 17-bit words need to be transmitted over a 16-bit data bus. Each such word can be transmitted in two cycles of operation of a digital system; however, this approach reduces the overall performance of the system. One of the approaches to solve such problems is the development of combinational circuits that convert long binary encoded words into shorter ones. The proposed methods for solving the problem of synthesizing circuits of code converters are based on the compilation and logical minimization of such forms of systems of incompletely specified Boolean functions as disjunctive normal forms (DNFs) and binary decision diagrams called BDD representations. Using BDDs to minimize representations of \(k\)-valued functions that depend on Boolean variables is also proposed. Technology-independent logical minimization of functional descriptions of the designed code converters is proposed to be performed by programs for minimizing the systems of Boolean functions in the DNF class and programs for joint minimization of BDD representations of systems of completely specified Boolean functions. Minimization of functional descriptions is aimed at reducing the hardware complexity of combinational circuits in the basis of library elements or FPGA elements implementing code converters of the class in question.
MSC:
| 68W35 | Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) |
| 06E30 | Boolean functions |
| 68M07 | Mathematical problems of computer architecture |
| 94C11 | Switching theory, applications of Boolean algebras to circuits and networks |
Keywords:
code converter; system of Boolean functions; disjunctive normal form; binary decision diagram; Shannon expansion; digital logic synthesis; VHDL; VLSISoftware:
ModelSimReferences:
| [1] | Primenenie integral’nykh mikroskhem v elektronnoi vychislitel’noi tekhnike: Spravochnik (Integrated Circuits in Electronic Computing: Handbook), Faizulaev, B.N. and Tarabrin, B.V., Eds., Moscow: Radio i svyaz’, 1987. |
| [2] | Chervyakov, N.I. et al., Modulyarnye parallel’nye vychislitel’nye struktury neiroprotsessornykh sistem (Modular Parallel Computing Structures of Neuroprocessor Systems), Moscow: Fizmatlit, 2003. |
| [3] | Brayton, K. R.; Hachtel, G. D.; McMullen, C.; Sangiovanni-Vincentelli, A. L., Logic Minimization Algorithm for VLSI Synthesis (1984), Boston: Kluwer Acad. Publ., Boston · Zbl 0565.94020 · doi:10.1007/978-1-4613-2821-6 |
| [4] | Bibilo, P.N., Primenenie diagramm dvoichnogo vybora pri sinteze logicheskikh skhem (Binary Decision Diagrams for Synthesizing Logic Circuits), Minsk: Belarusskaya navuka, 2014. |
| [5] | Bibilo, P.N., Sistemy proektirovaniya integral’nykh skhem na osnove yazyka VHDL. StateCAD, ModelSim, LeonardoSpectrum (Integrated Circuit Design Systems Based on the VHDL Language: StateCAD, ModelSim, LeonardoSpectrum), Moscow: SOLON-Press, 2005. |
| [6] | Avdeev, N. A.; Bibilo, P. N., Logical optimization efficiency for synthesizing combinational circuits consisting of library elements, Mikroelektronika, 44, 383-399 (2015) |
| [7] | Bibilo, P.N. and Romanov, V.I., The system of logical optimization of functional and structural descriptions for digital devices based on production-frame knowledge representation model, in Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem - 2020. Sb. trudov (Promising Micro- and Nano-Electronic Systems: Design Problems. Collection of Scientific Papers 2020), Stempkovskii A.L., Ed., Moscow: Institute for Design Problems in Microelectronics RAS, 2020, issue 4, pp. 9-16. |
| [8] | Bibilo, P. N.; Lankevich, Yu. Yu., Zhegalkin polynomials for minimizing multilevel representations of Boolean functions systems based on the Shannon expansion, Program. Inzheneriya, 8, 369-384 (2017) · doi:10.17587/prin.8.369-384 |
| [9] | Brayton, R. K.; Hachtel, G. D.; Sangiovanni-Vincentelli, A. L., Synthesis of multi-level combinational logic circuits, Tr. Inst. Inzh. Elektrotekhn. Radioelektron., 78, 38-83 (1990) |
| [10] | Mishchenko, A., An Introduction to Zero-Suppressed Binary Decision Diagrams (2014), Berkeley: Univ. of California, Verification and Synthesis Research Center, Department of Electrical Engineering and Computer Sciences, Berkeley |
| [11] | Kam, T., Villa, T., Brayton, R.K., and Sangiovanni-Vincentelli, A.L., Multi-valued decision diagrams for logic synthesis and verification, in Memorandum no. UCB/ERL M96/75, 1996. http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/ERL-96-75.pdf. · Zbl 0876.94057 |
| [12] | Ashenden, P. J.; Lewis, J., VHDL-2008. Just the New Stuff (2008), Burlington, MA: Morgan Kaufman Publ., Burlington, MA |
| [13] | Bibilo, P. N., System of functional blocks logical design for custom CMOS VLSI with reduced power consumption, Mikroelektronika, 46, 72-88 (2017) |
| [14] | Solov’ev, V.V., Arkhitektury PLIS firmy Xilinx: FPGA i CPLD 7-i serii (Xilinx PLIS Architectures: FGPA and CPLD 7-Series), Moscow: Goryachaya liniya-Telekom, 2016. |
| [15] | Tarasov, I.E., PLIS Xilinx. Yazyki opisaniya apparatury VHDL i Verilog, SAPR, priemy proektirovaniya (PLIS Xilinx. Hardware Description Languages VHDL and Verilog, SAPR, Design Techniques), Moscow: Goryachaya liniya-Telekom, 2020. |
| [16] | Amaru, L. G., New Data Structures and Algorithms for Logic Synthesis and Verification (2017) · Zbl 1362.68004 · doi:10.1007/978-3-319-43174-1 |
| [17] | Yang, S., BDS: a BDD-based logic optimization system, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 21, 866-876 (2002) · doi:10.1109/TCAD.2002.1013899 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
