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