Реалізація підстановок довільної розрядності на базі комбінованих каскадів конструктивних модулів
Олександр Тесленко, Максим БондарчукШвидкість перетворення і простота реалізації є одними з ключових факторів підстановок. У статті розглянуто реалізацію підстановки довільної розрядності в області комп’ютерної інженерії на одному із класів комбінаційних структур лінійної складності від кількості змінних – комбінованих каскадів конструктивних модулів. Використано той факт, що відображення, яке формує вказана лінійна структура, повністю збігається з відображенням відповідного скінченного автомата Мілі як прототипу конструктивного модуля каскаду. Це дозволило досліджувати властивості конструктивних модулів та каскаду в цілому у розрізі понять теорії цифрових автоматів. Реалізація підстановок довільної розрядності полягає у використанні зв’язаних пронумерованих однонаправлених автоматів для таблиці станів і використанні унікальних комбінацій без повторів для кожного рядку таблиці виходів. Метою реалізації даної підстановки є швидке перетворення даних великих об’ємів з можливістю застосування в кількох напрямках досліджень при простій реалізації на апаратному або програмному рівні. Виконано дослідження забезпечення бієктивності відображення та проведено аналіз еквівалентності відображень. Показано алгоритми формування автоматів для реалізації прямих та обернених підстановок, а також приклади формування таблиць переходів та виходів таких автоматів. Наведено приклади апаратної реалізації на програмованих логічних інтегральних схемах. Виконано оцінку об’єму таблиць переходів та виходів для апаратної та програмної реалізації. Виконано оцінку кількості унікальних бієктивних відображень. Проведено теоретичну оцінку швидкості бієктивних відображень при реалізації на програмованих логічних інтегральних схемах, а також при програмній реалізації згідно з сучасними показниками швидкості видів пам’яті обчислювальних пристроїв для кожного виду. Проведено порівняння швидкодії програмних реалізацій на базі комбінованого та одновимірного каскадів конструктивних модулів. Наведено експериментальну оцінку, а також проведено практичну перевірку швидкості перетворення за допомогою програмної реалізації. Запропоновано області застосування досліджених реалізацій підстановок довільної розрядності
Використані джерела
[1] Hazewinkel, M. (Ed.). (2000). Encyclopedia of mathematics (Vol. 2). Berlin: Springer. doi: 10.1007/978-94-015-1279-4.
[2] Peng, L. (2019). The Generation of (n,n(n-1),n-1) Permutation group codes for communication systems. IEEE Transactions on Communications, 67(7), 4535-4549. doi: 10.1109/TCOMM.2019.2902149.
[3] Boss, E., Grosso, V., Güneysu, T., Leander, G., Moradi, A., & Schneider, T. (2017). Strong 8-bit sboxes with ecient masking in hardware. Journal of Cryptographic Engineering, 7, 149-165. doi: 10.1007/s13389-017-0156-7.
[4] Fomin, D., & Trifonov, D. (2019). On hardware implementation of one class of byte substitutions. Applied Discrete Mathematics. Appendix, 12, 134-137. doi: 10.17223/2226308X/12/39.
[5] Oliinikov, R., Gorbenko, I., Kazimirov, O., Ruzhentsev, V., & Gorbenko, Yu. (2015). Principles of construction and main properties of the new national standard of block encryption of Ukraine. Protection of information, 17(2), 142-157. doi: 10.18372/2410-7840.17.8789.
[6] National Institute of Standards and Technology. (2001). Advanced Encryption Standard (AES). doi: 10.6028/NIST.FIPS.197.
[7] Tarasenko, V., Teslenko, O., & Yanovska, O. (2007). Problems of hardware implementation of substitutions. UNDIZ Scientific Notes, 2, 52-58,
[8] Tarasenko, V., Teslenko, O., & Yanovska, O. (2010). Properties of complete substitutions realized by the simplest unidirectional regular one-dimensional cascade of constructive modules. Radioelectronic and Computer Systems, 6, 123-128.
[9] Tarasenko, V., Teslenko, O., & Yanovska, O. (2012). Possibilities of the simplest bidirectional regular one-dimensional cascades of constructive modules regarding the implementation of various complete substitutions. Radioelectronic and Computer Systems, 7, 147-153.
[10] Teslenko, O., & Bondarchuk, M. (2020). Implementation of arbitrary bitness permutations in one of the classes of linear structures. Herald of Advanced Information Technology, 3(1), 406-417. doi: 10.15276/hait01.2020.7.
[11] Teslenko, O., & Bondarchuk, M. (2022). Using implementations of substitutions of arbitrary bitness for cryptographic transformations. Scientific News of KPI, 1-2. doi: 10.20535/kpisn.2022.12.263225.
[12] Glushkov, V. (1967). Synthesis of digital automata. Kyiv: Publishing House of the Academy of Sciences of the Ukrainian SSR.
[13] Karandashov, M. (2014). Investigation of bijective automatic subtractions displayed on a ring modulo 2k. Computer Sciences and Information Technologies, 2, 148-152.
[14] Gill, A. (1962). Introduction to the theory of finite-state machines. New York: McGraw-Hill.
[15] Bondarchuk, M. (n.d.). Algorithm for generating a table of transitions as a table of a connected numbered unidirectional graph. Retrieved from https://github.com/MaksymBondarchuk/Article-3materials/blob/master/ConnectedGraphStateAlgorithm.cs.
[16] Bondarchuk, M. (n.d.). Algorithm for generating a table of outputs with unique values in each row. Retrieved from https://github.com/MaksymBondarchuk/Article-3materials/blob/master/RandomNonRepeatingRowsOutputAlgorithm.cs.
[17] Frobenius G., & Stickelberger, L. (1879). Ueber Gruppen von vertauschbaren Elementen. Journal für die Reine und Angewandte Mathematik, 86, 217-262. doi: 10.1515/crll.1879.86.217.
[18] Bondarchuk, M. (n.d.). Algorithm for generating inverse automata. Retrieved from https://github.com/MaksymBondarchuk/Article-3-materials/blob/master/ReversedMachine.cs .
[19] Summary of Virtex-6 FPGA Features. Virtex-6 Family Overview. XILINX DS150 (v2.5). (n.d.). Retrieved from https://www.xilinx.com/support/documentation/data_sheets/ds150.pdf.
[20] Sequence A001349 – Number of connected graphs with n nodes. (n.d.). Retrieved from http://oeis.org/A001349.
[21] Van Lint, J., & Wilson, R. (1992). A course in combinatorics. Cambridge University Press.
[22] Sequence A001187 – Number of connected labeled graphs with n nodes. (n.d.). Retrieved from http://oeis.org/A001187.
[23] SiSoftware Official Live Ranker "SiSoftware Zone". (n.d.). Retrieved from https://ranker.sisoftware.co.uk/top_device_all.php?q=d6ebdb.
[24] Memory Performance in a Nutshell. (n.d.). Retrieved from https://www.intel.com/content/www/us/en/developer/articles/technical/memory-performance-in-anutshell.html.
[25] RAM UserBenchmarks – 115 Memory Kits Compared. (n.d.). Retrieved from https://ram.userbenchmark.com.
[26] SSD UserBenchmarks – 1071 Solid State Drives Compared. (n.d.). Retrieved from https://ssd.userbenchmark.com.
[27] HDD UserBenchmarks – 1015 Hard Drives Compared. (n.d.). Retrieved from https://hdd.userbenchmark.com.
[28] Yanovska, O., Tarasenko, V., & Teslenko, O. (2013). Using direct and inverse substitutions of arbitrary bit rate to improve the efficiency of existing data compression tools. In Abstracts of reports of the Fourth International Scientific and Practical Conference "Methods and means of coding, protection and compression of information (pp. 223-226), Vinnytsia: VNTU.
[29] Tarasenko, V., Teslenko, O., & Yanovska, O. (2010). Analysis of the influence of substitutions on the decomposition of Boolean functions. Bulletin of the University "Ukraine", 8, 40-47.
[30] Klyatchenko, Ya., Tarasenko, V., Teslenko, O., & Yanovska, O. (2011). Using substitutions for non-algorithmic implementation of encoders and decoders of interference-tolerant coding. In Modern Computer Systems and Networks: Development and Use (ACSN'2011) (pp. 191-193). Lviv: Lviv Polytechnic National University.
[31] Melnikova O., & Maslennikova, A. (2017). Substitutions for increasing the efficiency of software implementation of algorithms that use symbolic-digital representations. Mathematical and Computer Modeling, 15, 126-132.
[32] Abornev, A. (2014). Nonlinear substitutions on a vector space recursively generated over a Galois ring of characteristic 4. Applied Discrete Mathematics. Appendix, 7, 40-41.