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