Preview

Научно-технический вестник информационных технологий, механики и оптики

Расширенный поиск

Построение множества плотных информационных совокупностей для кодов Гилберта и их расширений

https://doi.org/10.17586/2226-1494-2025-25-2-286-294

Аннотация

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

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

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

Об авторе

М. Н. Исаева
Национальный исследовательский университет «Высшая школа экономики»
Россия

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

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



Список литературы

1. Величко В.В., Попков Г.В., Попков В.К. Модели и методы повышения живучести современных систем связи. М.: Горячая линия– Телеком, 2014. 270 с.

2. Нетес В.А. Основы теории надежности. М.: Горячая линия– Телеком, 2024. 102 с.

3. Половко А.М., Гуров С.В. Основы теории надежности. СПб: БХВ-Петербург, 2006. 704 с.

4. 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.9131517

5. Bogatyrev 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_9

6. Bogatyrev 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.9976839

7. Lin S., Li J. Fundamentals of Classical and Modern Error-Correcting Codes. Cambridge, Cambridge University Press, 2022. 840 p.

8. Moon T.K. Error correction coding: Mathematical methods and algorithms. Wiley, 2020. 992 p.

9. 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.8849456

10. Xiao 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.3059001

11. Li 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.3391826

12. Yang 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.477546

13. Aharoni 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.10206663

14. Fang 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.3095195

15. Ghaddar 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.3098822

16. Ovchinnikov А.А., 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-52

17. Исаева М.Н., Овчинников А.А. Исправление одиночных пакетов ошибок за пределами корректирующей способности кода с использованием информационных совокупностей // Научнотехнический вестник информационных технологий, механики и оптики. 2024. Т. 24. № 1. С. 70–80. https://doi.org/10.17586/2226-1494-2024-24-1-70-80

18. Исаева М.Н. Поиск информационных совокупностей при исправлении пакетов ошибок квазициклическими кодами // T-Comm: Телекоммуникации и транспорт. 2023. Т. 17. № 7. С. 4–12. https://doi.org/10.36724/2072-8735-2023-17-7-4-12

19. Крук Е.А., Овчинников А.А. Точная корректирующая способность кодов Гилберта при исправлении пакетов ошибок // Информационно-управляющие системы. 2016. № 1(80). С. 80–87. https://doi.org/10.15217/issn1684-8853.2016.1.80

20. Veresova 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.10758475

21. Исаева М.Н. Разработка и анализ методики построения множества плотных информационных совокупностей для исправления пакетов ошибок // T-Comm: Телекоммуникации и транспорт. 2024. Т. 18. № 10. С. 20–26. https://doi.org/10.36724/2072-8735-2024-18-10-20-26

22. Крук Е.А., Федоренко С.В. Декодирование по обобщенным информационным совокупностям // Проблемы передачи информации. 1995. Т. 31. № 2. С. 54–61.

23. 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.771141

24. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998. 703 с.


Рецензия

Для цитирования:


Исаева М.Н. Построение множества плотных информационных совокупностей для кодов Гилберта и их расширений. Научно-технический вестник информационных технологий, механики и оптики. 2025;25(2):286-294. https://doi.org/10.17586/2226-1494-2025-25-2-286-294

For citation:


Isaeva M.N. Development of dense information sets for Gilbert codes and its extensions. Scientific and Technical Journal of Information Technologies, Mechanics and Optics. 2025;25(2):286-294. (In Russ.) https://doi.org/10.17586/2226-1494-2025-25-2-286-294

Просмотров: 29


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-1494 (Print)
ISSN 2500-0373 (Online)