ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2025-25-2-286-294ntv-448Research ArticleКОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИCOMPUTER SCIENCEПостроение множества плотных информационных совокупностей для кодов Гилберта и их расширенийDevelopment of dense information sets for Gilbert codes and its extensionshttps://orcid.org/0009-0007-6228-0617ИсаеваМ. Н.IsaevaM. N.

Исаева Мария Николаевна — младший научный сотрудник.

Санкт-Петербург, 190008, sc 57243599200

Maria N. Isaeva — Junior Researcher.

Saint Petersburg, 190008, sc 57243599200

misaeva@hse.ruНациональный исследовательский университет «Высшая школа экономики»РоссияHSE University-St. PetersburgRussian Federation202524042025252286294Copyright © Исаева М.Н., 20252025Исаева М.Н.Isaeva M.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ntv.elpub.ru/jour/article/view/448Введение

Введение. При передаче информации по каналам с группирующимися ошибками традиционным подходом является декорреляция канала и использование кодов, исправляющих независимые ошибки. Процедура декорреляции понижает достижимые скорости надежной передачи, поэтому актуальной является задача использования специальных кодов для каналов с памятью и построения эффективных вычислительных методов декодирования для исправления группирующихся ошибок. Для класса случайных кодов известен подход с использованием информационных совокупностей ограниченного диаметра при исправлении пакетов ошибок. Размер множества информационных совокупностей растет линейно с увеличением длины кода, а построение множества описывается вероятностной процедурой. В работе рассматривается построение множества информационных совокупностей для специального класса кодов, исправляющих пакеты ошибок, называемого кодами Гилберта.

Метод

Метод. Рассмотрены множества кодовых позиций наименьшего возможного диаметра. На основе вычисления рангов подматриц проверочной матрицы кода Гилберта оценена вероятность того, что набор позиций является информационной совокупностью. Для заданного расположения информационной совокупности проанализированы позиции исправляемых пакетов. На основании проведенного анализа предложена методика построения множества плотных информационных совокупностей для кодов Гилберта с целью исправления всех пакетов ошибок в пределах корректирующей способности кода. Используя особенности задания параметров кодов Гилберта, проведена оценка размера полученного множества плотных информационных совокупностей. Основные результаты. При простом размере блока проверочной матрицы квазициклического кода показано, что для кодов Гилберта на любой позиции находится плотная информационная совокупность. Установлено, что в случае расширенных кодов Гилберта совокупности минимального диаметра существуют только на последней позиции каждого блока. Предложена процедура построения множества плотных информационных совокупностей минимального диаметра для кодов Гилберта и их расширений. Проведено сравнение размера множества информационных совокупностей и вероятность его получения для кодов Гилберта и случайных кодов. Установлено, что количество информационных совокупностей, полученных по предложенной процедуре, не растет с увеличением длины кода.

Обсуждение

Обсуждение. Полученные в работе результаты, показывают возможность разработки вычислительно эффективных декодеров на основе информационных совокупностей при исправлении однократных пакетов ошибок. В отличие от случайных линейных кодов, для которых методы построения информационных совокупностей, в том числе плотных, носят вероятностный характер, для кодов Гилберта определена процедура гарантированного построения множества информационных совокупностей минимального диаметра. Квазициклическая структура кодов Гилберта позволяет строить множества плотных информационных совокупностей меньшей размерности, чем для случайных кодов. Полученные результаты позволяют гарантировать исправление пакетов ошибок в пределах корректирующей способности кодов Гилберта и их расширений с малой вычислительной сложностью. Использование вычислительно эффективных процедур кодирования и декодирования пакетов ошибок позволит повысить надежность доставки сообщений в каналах с памятью.

When transmitting information over channels with grouping errors, the traditional approach is channel decorrelation and use of codes correcting independent errors. The decorrelation procedure lowers achievable rates of reliable transmission, therefore the problem of using special codes for channels with memory and construction of computationally effective decoding methods for correction of grouping errors is actual. For the class of random codes, an approach is known using information sets of limited diameter to correct error bursts. The size of the set of information sets grows linearly with increasing code length, and the construction of the set is described by a probabilistic procedure. This article considers the construction of a set of information sets for a special class of codes that correct error bursts called Gilbert codes. The sets of code positions of the smallest possible diameter are considered. Based on the calculation of the ranks of the submatrices of the parity-check matrix of the Gilbert code, the probability that the set of positions is an information set is estimated. For a given location of the information set, the positions of the corrected bursts are analyzed. Based on the analysis, a method for constructing a set of dense information sets for Gilbert codes for correcting all error bursts within the code correcting capacity is proposed. Using the features of setting the parameters of Gilbert codes, an estimate of the size of the resulting set of dense information sets is carried out. For a simple block size of the paritycheck matrix of a quasi-cyclic code, it is shown that for Gilbert codes a dense information set is located at any position. In the case of extended Gilbert codes, it is shown that sets of minimum diameter exist only at the last position of each block. A procedure for constructing a set of dense information sets of minimum diameter for Gilbert codes and their extensions is proposed. A comparison is made of the set size of information sets and the probability of obtaining it for Gilbert codes and random codes. It is shown that the number of information sets obtained by the proposed procedure does not increase with the length of the code. The results obtained in the paper demonstrate the possibility of developing computationally efficient decoders based on information sets when correcting single error bursts. Unlike random linear codes, for which the methods of constructing information sets including dense ones, are probabilistic, a procedure for guaranteed construction of a set of information sets of minimal diameter is specified for Gilbert codes. The quasi-cyclic structure of Gilbert codes allows constructing sets of dense information sets of smaller dimension than for random codes. The obtained results allow us to guarantee the correction of error bursts within the correcting capacity of Gilbert codes and their extensions with low computational complexity. The use of computationally efficient procedures for encoding and decoding error bursts will improve the reliability of message delivery in channels with memory.

информационные совокупностикорректирующая способностькоды Гилбертаканалы с памятьюпакеты ошибокinformation setserror correcting capabilityGilbert codeschannels with memoryerror burstsРабота подготовлена в результате проведения исследования в рамках Программы фундаментальных исследований Национального исследовательского университета «Высшая школа экономики» (НИУ ВШЭ), лаборатория Интернета вещей и киберфизических систем НИУ ВШЭ в Санкт-ПетербургеThe article was prepared within the framework of the Basic Research Program at HSE University, Internet of Things and Cyber-Physical Systems Laboratory, St. Petersburg School of Physics, Mathematics, and Computer ScienceReferencesВеличко В.В., Попков Г.В., Попков В.К. Модели и методы повышения живучести современных систем связи. М.: Горячая линия– Телеком, 2014. 270 с.Velichko V.V., Popkov G.V., Popkov V.K. Models and Methods of Increasing the Survivability of Modern Communication Systems. Moscow, Hotline–Telecom, 2014, 270 p. (in Russian)Нетес В.А. Основы теории надежности. М.: Горячая линия– Телеком, 2024. 102 с.Netes V.A. Fundamentals of Reliability Theory. Moscow, Hotline– Telecom, 2024, 102 p. (in Russian)Половко А.М., Гуров С.В. Основы теории надежности. СПб: БХВ-Петербург, 2006. 704 с.Polovko A.M., Gurov S.V. Fundamentals of Reliability Theory. St. Petersburg BHVPetersburg, 2006, 704 p. (in Russian)Bogatyrev A.V., Bogatyrev V.A., Bogatyrev S.V. The probability of timeliness of a fully connected exchange in a redundant real-time communication system // Proc. of the Wave Electronics and its Application in Information and Telecommunication Systems (WECONF). 2020. P.1–4. https://doi.org/10.1109/weconf48837.2020.9131517Bogatyrev A.V., Bogatyrev V.A., Bogatyrev S.V. The probability of timeliness of a fully connected exchange in a redundant real-time communication system. Proc. of the Wave Electronics and its Application in Information and Telecommunication Systems (WECONF) , 2020, pp. 1–4. https://doi.org/10.1109/weconf48837.2020.9131517Bogatyrev V.A., Bogatyrev A.V., Bogatyrev S.V. Multipath transmission of heterogeneous traffic in acceptable delays with packet replication and destruction of expired replicas in the nodes that make up the path // Communications in Computer and Information Science. 2023. V. 1748. P. 104–121. https://doi.org/10.1007/978-3-031-30648-8_9Bogatyrev V.A., Bogatyrev A.V., Bogatyrev S.V. Multipath transmission of heterogeneous traffic in acceptable delays with packet replication and destruction of expired replicas in the nodes that make up the path. Communications in Computer and Information Science, 2023, vol. 1748, pp. 104–121. https://doi.org/10.1007/978-3-031-30648-8_9Bogatyrev V.A., Bogatyrev S.V., Bogatyrev A.V. Control of multipath transmissions in the nodes of switching segments of reserved paths // Proc. of the International Conference on Information, Control, and Communication Technologies (ICCT). 2022. P. 1–5. https://doi.org/10.1109/ICCT56057.2022.9976839Bogatyrev V.A., Bogatyrev S.V., Bogatyrev A.V. Control of multipath transmissions in the nodes of switching segments of reserved paths. Proc. of the International Conference on Information, Control, and Communication Technologies (ICCT), 2022, pp. 1–5. https://doi.org/10.1109/ICCT56057.2022.9976839Lin S., Li J. Fundamentals of Classical and Modern Error-Correcting Codes. Cambridge, Cambridge University Press, 2022. 840 p.Lin S., Li J. Fundamentals of Classical and Modern Error-Correcting Codes. Cambridge, Cambridge University Press, 2022, 840 p.Moon T.K. Error correction coding: Mathematical methods and algorithms. Wiley, 2020. 992 p.Moon T.K. Error Correction Coding: Mathematical methods and algorithms. Wiley, 2020, 992 p.Kulhandjian M., Kulhandjian H., D’Amours C. Improved soft decoding of Reed-Solomon codes on Gilbert-Elliott channels // Proc. of the IEEE International Symposium on Information Theory (ISIT). 2019. P. 1072–1076. https://doi.org/10.1109/ISIT.2019.8849456Kulhandjian M., Kulhandjian H., D’Amours C. Improved soft decoding of Reed-Solomon codes on Gilbert-Elliott channels. Proc. of the IEEE International Symposium on Information Theory (ISIT) , 2019, pp. 1072–1076. https://doi.org/10.1109/ISIT.2019.8849456Xiao X., Vasic B., Lin S., Li J., Abdel–Ghaffar K. Quasi-cyclic LDPC codes with parity-check matrices of column weight two or more for correcting phased bursts of erasures // IEEE Transactions on Communications. 2021. V. 69. N 5. P. 2812–2823. https://doi.org/10.1109/TCOMM.2021.3059001Xiao X., Vasic B., Lin S., Li J., Abdel–Ghaffar K. Quasi-cyclic LDPC codes with parity-check matrices of column weight two or more for correcting phased bursts of erasures. IEEE Transactions on Communications, 2021, vol. 69, no. 5, pp. 2812–2823. https://doi.org/10.1109/TCOMM.2021.3059001Li L., Lv J., Li Y., Dai X., Wang X. Burst error identification method for LDPC coded systems // IEEE Communications Letters. 2024. V. 28. N 7. P. 1–5. https://doi.org/10.1109/LCOMM.2024.3391826Li L., Lv J., Li Y., Dai X., Wang X. Burst error identification method for LDPC coded systems. IEEE Communications Letters, 2024, vol. 28, no. 7, pp. 1–5. https://doi.org/10.1109/LCOMM.2024.3391826Yang M., Pan Z., Djordjevic I.B. FPGA-based burst-error performance analysis and optimization of regular and irregular SDLDPC codes for 50G-PON and beyond // Optics Express. 2023. V. 31. N 6. P. 10936–10946. https://doi.org/10.1364/OE.477546Yang M., Pan Z., Djordjevic I.B. FPGA-based burst-error performance analysis and optimization of regular and irregular SDLDPC codes for 50G-PON and beyond. Optics Express, 2023, vol. 31, no. 6, pp. 10936–10946. https://doi.org/10.1364/OE.477546Aharoni Z., Huleihel B., Pfister H.D., Permuter H.H. Data-Driven polar codes for unknown Channels with and without memory // Proc. of the IEEE International Symposium on Information Theory (ISIT). 2023. P. 1890–1895. https://doi.org/10.1109/ISIT54713.2023.10206663Aharoni Z., Huleihel B., Pfister H.D., Permuter H.H. Data-Driven polar codes for unknown Channels with and without memory. Proc. of the IEEE International Symposium on Information Theory (ISIT), 2023, pp. 1890–1895.https://doi.org/10.1109 / ISIT54713.2023.10206663Fang Y., Chen J. Decoding polar codes for a generalized Gilbert-Elliott channel with unknown parameter // IEEE Transactions on Communications. 2021. V. 69. N 10. P. 6455–6468. https://doi.org/10.1109/TCOMM.2021.3095195Fang Y., Chen J. Decoding polar codes for a generalized GilbertElliott channel with unknown parameter. IEEE Transactions on Communications, 2021, vol. 69, no. 10, pp. 6455–6468. https://doi.org/10.1109/TCOMM.2021.3095195Ghaddar N., Kim Y.-H., Milstein L.B., Ma L., Yi B.K. Joint channel estimation and coding over channels with memory using polar codes // IEEE Transactions on Communications. 2021. V. 69. N 10. P. 6575–6589. https://doi.org/10.1109/TCOMM.2021.3098822Ghaddar N., Kim Y.-H., Milstein L.B., Ma L., Yi B.K. Joint channel estimation and coding over channels with memory using polar codes. IEEE Transactions on Communications, 2021, vol. 69, no. 10, pp. 6575–6589. https://doi.org/10.1109/TCOMM.2021.3098822Ovchinnikov А.А., Veresova А.М., Fominykh А.А. Decoding of linear codes for single error bursts correction based on the determination of certain events // Information and Control Systems. 2022. N 6. P. 41–52. https://doi.org/10.31799/1684-8853-2022-6-41-52Ovchinnikov А.А., Veresova А.М., Fominykh А.А. Decoding of linear codes for single error bursts correction based on the determination of certain events. Information and Control Systems, 2022, no. 6. pp. 41–52. https://doi.org/10.31799/1684-8853-2022-6-41-52Исаева М.Н., Овчинников А.А. Исправление одиночных пакетов ошибок за пределами корректирующей способности кода с использованием информационных совокупностей // Научнотехнический вестник информационных технологий, механики и оптики. 2024. Т. 24. № 1. С. 70–80. https://doi.org/10.17586/2226-1494-2024-24-1-70-80Isaeva M.N., Ovchinnikov A.A. Correction of single error bursts beyond the code correction capability using information sets. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2024, vol. 24, no. 1, pp. 70–80. (in Russian). https://doi.org/10.17586/2226-1494-2024-24-1-70-80Исаева М.Н. Поиск информационных совокупностей при исправлении пакетов ошибок квазициклическими кодами // T-Comm: Телекоммуникации и транспорт. 2023. Т. 17. № 7. С. 4–12. https://doi.org/10.36724/2072-8735-2023-17-7-4-12Isaeva M.N. Finding information sets when correcting error bursts with quasi-cyclic codes. T-Comm, 2023, vol. 17, no. 7, pp. 4–12. (in Russian). https://doi.org/10.36724/2072-8735-2023-17-7-4-12Крук Е.А., Овчинников А.А. Точная корректирующая способность кодов Гилберта при исправлении пакетов ошибок // Информационно-управляющие системы. 2016. № 1(80). С. 80–87. https://doi.org/10.15217/issn1684-8853.2016.1.80Krouk E.A., Ovchinnikov A.A. Exact burst-correction capability of Gilbert Codes. Information and Control Systems, 2016, no. 1(80), pp. 80–87. (in Russian). https://doi.org/10.15217/issn16848853.2016.1.80Veresova A., Ovchinnikov. Burst detection and correction for Gilbert Codes and its QC-LDPC extensions // Proc. of the IEEE International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON). 2024. P. 47–51. https://doi.org/10.1109/sIBIRCON63777.2024.10758475Veresova A., Ovchinnikov. Burst detection and correction for Gilbert Codes and its QC-LDPC extensions. Proc. of the IEEE International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), 2024, pp. 47–51. https://doi.org/10.1109/sIBIRCON63777.2024.10758475Исаева М.Н. Разработка и анализ методики построения множества плотных информационных совокупностей для исправления пакетов ошибок // T-Comm: Телекоммуникации и транспорт. 2024. Т. 18. № 10. С. 20–26. https://doi.org/10.36724/2072-8735-2024-18-10-20-26Isaeva M.N. Development and analysis of a method for constructing dense information sets for error bursts correction. T-Comm, 2024, vol. 18, no. 10, pp. 20–26. (in Russian). https://doi.org/10.36724/2072-8735-2024-18-10-20-26Крук Е.А., Федоренко С.В. Декодирование по обобщенным информационным совокупностям // Проблемы передачи информации. 1995. Т. 31. № 2. С. 54–61.Kruk E.A., Fedorenko S.V. Decoding by generalized information sets. Problemy Peredachi Informatsii, 1995, vol. 31, no. 2, pp. 54–61. (in Russian)Barg A., Krouk E., van Tilborg H.C.A. On the complexity of minimum distance decoding of long linear codes // IEEE Transactions on Information Theory. 1999. V. 45. N 5. P. 1392‒1405. https://doi.org/10.1109/18.771141Barg A., Krouk E., van Tilborg H.C.A. On the complexity of minimum distance decoding of long linear codes. IEEE Transactions on Information Theory, 1999, vol. 45, no. 5, pp. 1392‒1405. https://doi.org/10.1109/18.771141Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998. 703 с.Graham R.L., Knuth D.E., Patashnik O. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Professional, 1994, 672 p.

The authors declare that there are no conflicts of interest present.