Метод декодирования ВШЭ и Сколтеха снизил сложность на сотни процентов
В Московском институте электроники и математики имени А.Н. Тихонова ВШЭ и Сколтехе создали подход к декодированию кодов, которые применяют при передаче данных. Гибридная схема заметно сокращает вычислительные затраты, а её можно воплотить на электронных компонентах. Работа опубликована в IEEE Transactions on Communications. Об этом пишет Naked Science.
Современные системы связи работают при шумах, поэтому данные защищают помехоустойчивым кодированием: к информации добавляют дополнительные символы, по которым получатель находит и исправляет ошибки. От качества декодирования зависит восстановление сообщения без искажений, но обычно улучшение работы декодера повышает расход ресурсов. Учёные ищут компромисс между качеством и вычислительной нагрузкой, а новые методы построены на парадигме суперкодов. Исходный код описывают через пересечение нескольких кодов с большей размерностью и меньшей избыточностью; обрабатывать каждый суперкод и суммировать результаты дешевле, чем напрямую работать с исходным кодом.
Первый метод задействует мягкие декодеры: жёсткие оперируют строгими нулями и единицами, а мягкие учитывают надёжность каждого бита и потому исправляют больше ошибок. Сложность падает за счёт меньшей избыточности отдельных суперкодов, а схема допускает предварительную обработку методом Чейза. Система получает несколько вариантов декодирования и выбирает лучший. Такой двухуровневый отбор снижает нужные мощности без роста времени обработки, пояснил первый автор исследования Алексей Кувшинов, младший научный сотрудник кафедры информационной безопасности киберфизических систем МИЭМ ВШЭ.
Второй вариант представляет собой универсальный гибридный декодер. Здесь к итеративному мягкому декодированию добавляются алгебраические декодеры. Метод Чейза–Пиндиаха даёт мягкие оценки вероятностей битов после жёсткого декодирования, затем они проходят финальную обработку вместе с остальными суперкодами. Анна Фоминых, аспирантка Сколтеха, сравнила схему с командой: одни точно решают узкую задачу, другие следят за согласованностью проекта, а суперкоды хорошо подходят для параллельных вычислений.
Математическое моделирование показало: с ростом параметра Чейза схемы выходят на производительность, близкую к оптимальной. Вычислительная сложность остаётся приемлемой для современных задач, а в отдельных случаях оказывается ниже, чем у других методов, на сотни процентов. Для полярных и случайных линейных кодов гибридный декодер превзошёл известные аналоги. Авторы считают, что схема подойдёт для многих семейств кодов, позволит делать гибкие декодеры под конкретные задачи и может быть воплощена в аппаратуре.
