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