Аннотация результатов, полученных в 2018 году
Получены новые границы достижимых скоростей передачи для кодов малой длины и малой вычислительной сложности при фиксированных вероятностях правильной передачи и модуляции. Для этого были выбраны коды с малой плотностью проверок (МПП-коды) над полем GF(q), так как для этого класса кодов возможно провести теоретический анализ. Была получена оценка радиуса декодирования (числа исправляемых ошибок) для нерегулярных МПП-кодов над полем GF(q). Выбор нерегулярных кодов обусловлен тем, что такие коды показывают лучшую корректирующую способность по сравнению с регулярными кодами при небольших значениях параметра q. Для данного класса кодов был предложен мажоритарный алгоритм декодирования с малой вычислительной сложностью. Предложенное решение является обобщением алгоритма инвертирования бита, применяемого в двоичном случае. Полученные оценки демонстрируют больший радиус декодирования по сравнению с двоичными МПП-кодами и этот радиус возрастает с ростом порядка поля (q). Выведены нижние границы экспоненты вероятности ошибки для МПП-кодов. Для этого используется специальная конструкция таких кодов. Сравниваются две экспоненты вероятности ошибки: при декодировании по максимуму правдоподобия – ML (экспоненциальная сложность) и при декодировании с использованием специального алгоритма (сложность декодирования порядка n log(n), где n – длина кода). Несмотря на то, что экспонента вероятности при ML-декодировании лучше, предложенная конструкция МПП-кодов достигает пропускной способности даже при использовании алгоритма декодирования с малой сложностью. Кроме того, экспонента вероятности при ML-декодировании близка к экспоненте лучших линейных кодов. Разработаны конструкции недвоичных МПП кодов и свёрточных кодов с циклическим замыканием с малой длиной блока и соответствующие алгоритмы кодирования-декодирования с малой вычислительной сложностью и энергопотреблением. Проведено сравнение данных классов кодов с использованием таких интегральных критериев, как помехоустойчивость (в том числе проведено сравнение с полученными выше границами достижимости), задержка, сложность декодирования, энергопотребление. Предложен алгоритм построения проверочных матриц квазициклических кодов с малой плотностью проверок (КЦ МПП-коды) над полем GF(q). Разработанные коды превосходят конкурентов по помехоустойчивости при сравнимой сложности реализации. Исследованы новые математические методы нахождения границ достижимых скоростей передачи при использовании неортогональных методов множественного доступа для доставки блоков данных малого размера при большом числе устройств с учетом ограничений на время доставки данных и энергопотребления. Формализована модель массового неортогонального множественного доступа, в которой предполагается, что в каждый момент времени передачу осуществляет лишь малая доля устройств по сравнению с общим числом устройств, что соответствует модели массового межмашинного взаимодействия. Устройства передают сообщения, используя одну и ту же кодовую книгу. При этом проблемы идентификации пользователей и декодирования сообщений разделены: от декодера требуется лишь вернуть список переданных сообщений без указания, кто их передал. Поскольку энергоэффективность – наиболее важный параметр для сценария массового межмашинного взаимодействия, главная цель заключается в минимизации энергии, требуемой для передачи информационного бита (Eb/N0). Для такого сценария была получена граница достижимости при декодировании по максимуму правдоподобия. Граница выведена с использованием модифицированного метода случайного кодирования как для гауссовской кодовой книги (пользователи передают гауссовские сигналы – идеализированный случай), так и для модуляций BPSK и QPSK. Полученные границы на сегодняшний день являются лучшими границами достижимости для сценария массового межмашинного взаимодействия. Получена граница достижимости для алгоритма случайного множественного доступа с малой сложностью реализации. Суть алгоритма состоит в использовании ортогональных преамбул и механизма временного переключения в режим с разделением времени, если несколько абонентов передавали данные в одном частотно-временном ресурсе. Такой подход позволяет разрешить «конфликт» без использования процедуры случайного доступа, что существенно повышает максимальную скорость передачи по сравнению с алгоритмом АЛОХА. С помощью имитационного моделирования показано, что максимальная скорость передачи данных в режиме случайного множественного доступа может быть существенно увеличена. Построены схемы неортогональной передачи на основе МПП-кодов, достигающих или приближающихся к границе достижимости. Предложен общий протокол случайного множественного доступа, известный T-кратная кодированная слотированная АЛОХА: в системе присутствует синхронизация по фреймам, которые, в свою очередь, разделены на слоты. Каждый пользователь передает свой пакет в нескольких слотах. Пользователи выбирают число передач случайно, в соответствии с заданным распределением, которое одинаково для всех пользователей. Слоты, в которые передаются копии пакета, тоже выбираются случайно. При успешном декодировании пакета производится его вычитание из всех слотов, где передавались его реплики. Степень кратности T означает, что коллизии кратности не более T могут быть разрешены. Для такой системы был модифицирован метод эволюции плотностей и найдены оптимальные распределения числа повторений пакета, а также показано, что пропускная способность (англ. throughput, среднее число успешно переданных пакетов за слот) растет с ростом T. Таким образом, ключевой задачей является разработка кодов, способных разрешать коллизии малой кратности. Для разрешения коллизий малой кратности в канале с аддитивным белым гауссовским шумом (АБГШ) была разработана специальная конструкция МПП-кодов. Существует набор теоретически обоснованных методов оптимизации МПП-кодов для однопользовательских каналов. Для многопользовательского режима была предложена модификация метода PEXIT (protograph-based extrinsic information transfer). Предложенные коды и система в целом были исследованы методом имитационного моделирования. Показано, что данная схема превосходит существующие решения (на 2-4 дБ) и находится в пределах 1-2 дБ от границы достижимости. Также была разработана новая сигнально-кодовая конструкция для векторного дизъюнктивного канала, в котором пользователи передают векторы длины L. Разработанные специальные методы кодирования и декодирования для данного сценария множественного доступа имеют приемлемую сложность для широкого диапазона параметров, и при этом их помехоустойчивость очень близка к помехоустойчивости алгоритма максимального правдоподобия. Получены зависимости относительной суммарной скорости передачи (при фиксированной вероятности ошибки) для разного числа активных пользователей и показано, что предложенная схема множественного доступа имеет хорошую помехоустойчивость даже в случае малой длины блока. Эффективное разрешение коллизий в задачах массового межмашинного взаимодействия может быть достигнуто в том числе с применением многоантенных систем на базовой станции. Для этого был предложен метод дискретной оптимизации для сортировки сигналов, принимаемых одновременно от нескольких устройств (до 48) в системе с большим числом принимающих антенн (до 64). Сортировка необходима для упорядочивания абсолютных значений диагональных элементов матрицы R (в QR разложении) в порядке возрастания для устранения эффекта распространения ошибок в режиме детектирования. С помощью модели канала Quadriga в сценарии с многолучевым распространением сигнала было показано, что потери в производительности по сравнению с методом максимального правдоподобия составляют не более 1 дБ. При этом вычислительная сложность в 2.5 раза меньше, чем у использующегося в настоящий момент детектора K-best. На базе оборудования лаборатории Интернета Вещей Сколковского Института Науки и Технологий был создан испытательный стенд для апробации алгоритма декодирования коротких МПП-кодов над полем GF(q). Стенд построен на базе оборудования, поддерживающего технологию программно-определяемого радио (SDR).

Аннотация результатов, полученных в 2019 году
Предложен многопороговый мажоритарный алгоритм для декодирования недвоичных МПП-кодов. Основная идея этого алгоритма заключается в том, что на каждом шаге декодируются наиболее ненадежные символы. Многопороговый алгоритм декодирования был обобщен на случай наличия оценок надежности символов из канала. Показано, что увеличение количества порогов значительно улучшает корректирующие способности алгоритма декодирования, при этом сложность реализации многопорогового алгоритма декодирования остается сравнимой с “жестким” алгоритмом, что значительно ниже сложности реализации недвоичного алгоритма распространения доверия. Разработан алгоритм декодирования недвоичных МПП-кодов на основе глубоких нейронных сетей. Для решения этой задачи связи в нейронной сети строятся в соответствии с правилами декодирования и результирующая нейронная сеть получается разреженной. Активационная функция в узле сети была изменена в соответствии с алгоритмом распространения доверия, что потребовало модификации методов оптимизации весов нейронной сети. Методами имитационного моделирования показано, что сходимость алгоритма декодирования на основе нейронных сетей значительно превосходит сходимость обычного итеративного алгоритма распространения доверия, поэтому для достижения заданной вероятности успешного декодирования для предложенного алгоритма декодирования требуется в два раза меньше итераций. Был предложен алгоритм последовательного исключения для декодирования недвоичных полярных кодов. Данный алгоритм работает с распределениями для каждого из символов и производит операции свертки и поэлементного умножения. Для упрощения операции свертки, аналогично случаю недвоичных МПП-кодов, было предложено использование преобразования Фурье над конечным полем. Также был предложен списочный вариант декодера недвоичных полярных кодов. Показано, что недвоичные полярные коды превосходят двоичные полярные и недвоичные МПП-коды по помехоустойчивости. Проведено исследование эффективности протокола T-кратная кодированная слотированная АЛОХА в канале с АБГШ применительно для сценария массового межмашинного взаимодействия. Получена фундаментальная граница на пропускную способность рассматриваемого протокола при фиксированной вероятности ошибки в слоте. Также была получена граница достижимости на основе комбинации метода эволюции плотностей и границы случайного кодирования для кодов фиксированной длины. Рассмотрены случаи фиксированного и случайного числа активных пользователей. Предложена схема неортогональной передачи на основе полярных кодов. Данный класс кодов выбран ввиду их крайней эффективности при малых длинах, что является естественным требованием при рассматриваемом сценарии. В работе рассмотрены два алгоритма декодирования: совместное последовательное исключение и совместное итеративное декодирование. Показано, что алгоритм совместного последовательного исключения значительно превосходит по корректирующим свойствам итеративный алгоритм. Для оптимизации конструкции кодов был предложен алгоритм на основе метода эволюции плотностей. Методами имитационного моделирования показано, что предложенная схема кодирования значительно превосходит по энергоэффективности рассмотренные ранее схемы на основе кодов с малой плотностью проверок (МПП-кодов), а также очень близка к полученной ранее границе достижимости. Проведено исследование потенциальной энергоэффективности схем кодирования для сценария неортогонального множественного доступа в квазистатическом канале Рэлея. Рассмотрен случай, когда информация о состоянии канала недоступна, как передатчикам, так и приемнику. Предложена схема передачи на основе оптимизированных для многопользовательского канала МПП-кодов и итеративного алгоритма совместного декодирования, производящего одновременную оценку состояния канала и декодирование сообщений. Данный алгоритм основан на подходе максимизации математического ожидания (англ. expectation maximization). Было проведено имитационное моделирование, которое показало, что разработанная схема очень близка к границе достижимости при числе активных пользователей, не превосходящем 150 (напомним, что сценарий mMTC подразумевает потенциально бесконечное число пользователей, лишь небольшая часть из которых активна). Проведено сравнение разработанной схемы с предложениями, сделанными в рамках комитета по стандартизации 3GPP (SCMA и RSMA) и показано, что предложенная схема значительно их превосходит. Идеальная синхронизации невозможна в практических системах, особенно когда речь идет об автономных маломощных датчиках, к которым предъявляется требование высокой энергоэффективности. В связи с этим проведено исследования практических схем для асинхронного квазистатического канала Рэлея. Предложена схема на основе OFDM, иными словами, передача происходит не во временной, а в частотной области. Благодаря этому подходу, задача определения временного сдвига трансформируется в задачу определения сдвига фазы. В качестве кодов были выбраны МПП-коды, как и в синхронном случае. Был предложен новый алгоритм декодирования TIN-SIC, основанный на комбинации алгоритмов обработки интерференции как шума (англ. treat interference as noise) и последовательного исключения интерференции (англ. successive interference cancellation). Отметим, что сложность процедуры исключения интерференции заключается в том, что коэффициенты замираний неизвестны, поэтому был разработан новый метод для вычитания найденного слова из принятого сигнала. Идея метода заключается в использовании процедуры градиентного спуска для подбора коэффициента замирания такого, что оставшийся после вычитания сигнал имеет минимальную норму. Отметим, что сложность декодера TIN-SIC растет лишь линейно с числом пользователей, а корректирующие свойства превосходят корректирующие свойства многопользовательского итеративного алгоритма. Энергоэффективность разработанной схемы совпадает с границей достижимости при числе активных пользователей, не превосходящем 250, что почти в 2 раза больше в сравнении с алгоритмом совместного декодирования. Отметим, что разработанный алгоритм TIN-SIC лучше алгоритма совместного декодирования и в синхронном случае. На базе собранного SDR-стенда реализованы и валидированы декодер коротких недвоичных МПП-кодов на основе нейронных сетей и декодер недвоичных полярных кодов, а также реализован протокол передачи коротких сообщений с применением узкополосной передачи данных. Основное внимание уделено проблеме синхронизации. Был разработан корреляционный детектор. Предварительные результаты показали, что данный метод позволяет с высокой точностью определять начало пакетов, а также минимизировать число ложных срабатываний и пропусков.

Аннотация результатов, полученных в 2020 году
Были установлены фундаментальные пределы энергетической эффективности для массового случайного доступа в синхронном и асинхронном квазистатических каналах Рэлея. Получены границы для энергии, затрачиваемой на передачу одного информационного бита при фиксированной вероятности ошибки. Предложена схема передачи данных, основанная на оптимизированных для многопользовательского канала МПП-кодах и итеративном алгоритме совместного декодирования, производящем одновременную оценку состояния канала и декодирование сообщений. Проведено сравнение разработанной схемы с предложениями, сделанными в рамках комитета по стандартизации 3GPP (SCMA и RSMA) и показано, что предложенная схема значительно их превосходит. Предложена схема передачи данных, основанная на оптимизированных для многопользовательского канала полярных кодах и алгоритме последовательного погашения интерференции (ППИ, TIN-SIC), имеющем значительно меньшую вычислительную сложность по сравнению с алгоритмом совместного итеративного декодирования. Данный класс кодов выбран ввиду их крайней эффективности при малых длинах, что является естественным требованием при рассматриваемом сценарии. На текущий момент разработанная схема обладает наилучшей энергетической эффективностью и практически достигает фундаментальных пределов. Была разработана схема неортогональной передачи для квазистатического канала Рэлея на основе метода сжатия измерений (англ. compressive sensing). Метод заключается в следующем. Сообщение разбивается на части и кодируется внешним кодом. Каждая из закодированных частей передается в отдельном слоте. Процедура декодирования позволяет восстановить список сообщений, которые были переданы в слоте. Было обнаружено, что в отличие от канала с АБГШ, с достаточно большой вероятностью в восстановленных списках сообщений присутствуют ошибки, таким образом необходимо выбирать внешний код, способный восстанавливать слова из списков при наличии ошибок (в англоязычной литературе данная задача известна как list recovery). Были получены фундаментальные границы для параметров внешнего года, в частности была найдена пропускная способность соответствующего канала. В качестве внешнего кода был выбран код Рида-Соломона в сочетании с алгоритмом Гурусвами-Судана. Были получены границы достижимости на точность оценивания восходящего многопользовательского канала при наличии большого числа антенн (massive MIMO) на базовой станции. Границы получены как в предположении о независимости реализаций коэффициентов ослабления сигнала в канале между различными антеннами базовой станции, так и в случае зависимых коэффициентов ослабления. Было исследовано одновременное итеративное детектирование и декодирование сигнала в сценарии неортогонального множественного доступа с базовой станцией с большим числом приемных антенн. Был исследован итеративный процесс совместной оценки канала и декодирования сигнала при наличии интерференции. Показано, что предлагаемый способ декодирования обеспечивает наименьшую вероятность битовой ошибки среди всех способов детектирования и декодирования сигнала. Было проведено исследование эффективности протокола кодированная слотированная АЛОХА с использованием показателя “возраст информации” (англ. age of information, AoI). Данный показатель имеет важное значение для систем Интернета Вещей, так как определяет время, прошедшее с момента получения последнего успешного обновления информации о системе (например, состояния окружающей среды). Впервые получено точное выражение для среднего возраста информации при использовании протокола кодированная слотированная АЛОХА, а также показано, что данный протокол эффективнее классического протокола слотированная АЛОХА. Работа была отмечена как лучшая работа симпозиума по теории телекоммуникаций на конференции 2020 IEEE Global Communications Conference. На базе SDR-стенда реализованы и валидированы схема неортогональной передачи с декодером TIN-SIC на базе полярных кодов, схема неортогональной передачи на основе метода сжатия измерений и схема неортогональной передачи для канала MIMO. Схемы основаны на протоколе T-кратная слотированная АЛОХА. Основная особенность состоит в том, что базовая станция способна принимать сигнал шириной до 1 МГц. Передающее устройство выбирает частоту передачи случайным образом в полосе шириной 1 МГц и осуществляет передачу сигнала шириной 50 Гц на выбранной несущей частоте. Таким образом, система АЛОХА использует не только временное, но и частотное разделение сигнала, что позволяет получать информацию от большого количества датчиков. Реализация разработанных протоколов в рамках SDR-стенда позволяет убедиться, что полученные путем вычислительных экспериментов вероятности ошибки передачи сообщения на пользователя вполне соответствуют результатам натурных экспериментов.