Аннотация результатов, полученных в 2019 году
В рамках проекта в течение первого года были исследованы и предложены новые конструкции бэтч кодов и кодов для конфиденциального восстановления информации. Все полученные результаты можно разбить на две смысловые части. 1) Были исследованы новые алгебраические конструкции кодов, которые являются в некотором смысле обобщением кодов Рида-Маллера и кодов Рида-Соломона (РС). Опишем общую конструкцию более подробно. Два полинома от одной переменной над конечным полем будем называть эквивалентными до некоторого порядка, если вычисления этих полиномов и всех производных до этого порядка включительно во всех точках поля совпадают. Полином от нескольких переменных над конечным полем назовем хорошим, если его ограничение на произвольную прямую в пространстве эквивалентно до некоторого порядка полиному ограниченной степени. Тогда расширенный код с кратностями задается как вычисление хороших полиномов вместе со всеми частными производными во всех точках пространства. В рамках проекта был исследован вопрос использования расширенных кодов с кратностями от двух переменных в качестве бэтч кодов. Эта конструкция позволила улучшить ранее известные результаты для некоторых параметров бэтч кодов. В случае, когда производные не вычисляются, указанная выше конструкция также называется расширенным РС-кодом, поскольку ограничение произвольного кодового слова на прямую в пространстве представляет собой слово РС-кода. Отметим, что это свойство автоматически гарантирует хорошие локальные свойства предложенных кодов, но не означает, что его можно использовать как конструкцию бэтч кодов. Другая задача из данного направления связана с анализом скорости расширенного РС-кода от трех переменных, которая вычисляется как доля хороших мономов к общему числу мономов. Показано, что для вычисления числа плохих мономов как функции от степени расширения двоичного поля можно воспользоваться рекуррентной формулой третьего порядка. Вычисляя максимальное по модулю собственное значения матрицы, описывающей рекуррентное соотношение, можно оценить скорость расширенного РС-кода. Этот результат позволил улучшить прежние оценки на избыточность кодов для конфиденциального восстановления информации при определенных параметрах. 2) Предложен новый подход к построению бэтч кодов, который основан на свойствах и конструкциях из конечных геометрий. Опишем сначала конструкцию, существование которой доказано вероятностным методом. Для построения порождающей матрицу вида G=[I E] систематического бэтч кода определим E как матрицу инцидентности случайно выбранных подмножеств точек в афинной плоскости. Для получения подмножества точек возьмем прямую в плоскости с некоторой вероятностью и оставим на ней часть точек со второй вероятностью. При определении порождающей матрицы указанным выше способом мы устанавливаем взаимосвязь между информационными битами и точками плоскости, а также между проверочными битами и случайно выбранными подмножествами прямых. При определенных параметрах в случайной модели можно показать, что существует жадный алгоритм, который успешно находит непересекающиеся восстанавливающие множества для произвольного подмножества информационных бит с высокой вероятностью. Таким образом доказывается существование порождающей матрицы систематического линейного бэтч кода. Для описания второй явной конструкции воспользуемся также соображениями из конечных геометрий, но больших размерностей. Аналогично первой конструкции построим порождающую матрицу вида G=[I E] систематического бэтч кода, где E - это матрица инцидентности l-мерных аффинных подпространств в (2l+1)-мерном пространстве. Ключевым соображением в данной конструкции является следующее впервые предложенное определение. Семейство l-мерных подпространств назовем хорошим, если оно является частичным спрэдом, а также произвольное (l+1)-мерное подпространство, содержащее одно из подпространств семейства, пересекает лишь константное число подпространств. В рамках проекта было представлено хорошее семейство подпространств мощности примерно порядка размера поля. При этом каждое подпространство задается как линейная оболочка столбцов проверочной матрицы некоторого кода Рида-Соломона. Данная конструкция асимптотически имеет избыточность меньшую, чем первая конструкция, но не является такой гибкой с точки зрения выбора параметров.

Аннотация результатов, полученных в 2020 году
В рамках проекта в течение второго года были исследованы и предложены новые конструкции кодов, которые можно использовать в различных системах хранения информации. Первое направление исследований во втором году существенным образом расширяет и дополняет результаты, полученные в течение первого года проекта. Были исследованы различные аспекты кодов, обобщающих коды Рида-Соломона и коды с кратностями. Эти коды можно задать как вычисление хороших многочленов от многих переменных и всех их производных до фиксированной степени во всех точках пространства. Основное свойство хороших многочленов состоит в том, что при ограничении на произвольную прямую в пространстве они ведут себя как многочлены малой степени от одной переменной. Это свойство непосредственно гарантирует хорошие локальные восстанавливающие свойства кода. Для анализа скорости этих кодов мы исследовали подкод, содержащий все хорошие мономы. Таким образом, мы свели задачу к комбинаторному подсчету числа двоичных матриц с определенными ограничениями. Мы показали, что это число можно подсчитать с помощью рекуррентного соотношения порядка, равного числу переменных в многочленах. Полученные результаты позволяют утверждать, что рассматриваемые коды являются наилучшей на текущий момент конструкцией бэтч кодов и кодов для конфиденциального восстановления информации. Были исследованы алгоритмы списочного декодирования кодов, обобщающих коды Рида-Соломона и коды с кратностями. Это направление является новым в контексте рассматриваемых кодов. Предложенные алгоритмы декодирования существенным образом опираются на две нетривиальные идеи. Во-первых, с помощью биективного отображения, заданного стандартным следом расширенного поля, можно показать, что хорошие многочлены от нескольких переменных являются эквивалентыми в некотором смысле многочленам небольшой степени от одной переменной, заданным над расширенным полем. Таким образом, можно воспользоваться существующим алгоритмом списочного декодирования для случая одной переменной и найти список многочленов от одной переменной, находящихся на небольшом расстоянии от полученного зашумленного слова. Затем можно сформировать список многочленов от нескольких переменных, согласованных с первым списком. Однако, число подобных согласованных многочленов от нескольких переменных может оказаться велико. Чтобы уменьшить это число до константы, мы использовали другое соображение. Для этого мы рассмотрели целое семейство различных биективных отображений, которые находятся в так называемом общем положении, и на выходе алгоритма стали рассматривать лишь те многочлены, которые согласованы с каждым отображением из семейства. Использую подобную структуру, мы показали, как эффективно реализовать списочный алгоритм за полиномиальное время. Были рассмотрены коды для Z-канала с двухшаговым алгоритмом кодирования. Этот канал используется для моделирования различных асимметричных систем хранения и передачи информации. Для комбинаторной модели ошибок нам удалось найти максимальную долю исправляемых ошибок, при которой кодер может безошибочно передать экспоненциальное число сообщений. И теорема существования, и теорема несуществования опираются на два понятия, широко известных в теории кодирования: списочные коды с экспоненциальным размером и коды нулевой скорости с большой корректирующей способностью. На первом шаге кодер должен отослать кодовое слова из кода, который можно декодировать списком практически оптимальным образом для всех размеров списка. Между первым и вторым шагом кодер и декодер могут посчитать число произошедших ошибок, поскольку в этот момент используется канал обратной связи. Они формируют список сообщений, которые согласованы с частично принятым словом. Таким образом, на втором шаге остается лишь отличить настоящее сообщение от других сообщений в списке. Кодер посылает кодовое слово из кода, имеющего размер как у списка, но обладающего оптимальной корректирующей способностью. Мы показали, что подобная стратегия является оптимальной.