Исправление одиночных пакетов ошибок за пределами корректирующей способности кода с использованием информационных совокупностей

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

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

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License