Подпространственные коды на основе ранговой метрики - новое направление в теории кодирования

Представлен аналитический обзор работ нового направления теории кодирования, связанного с подпространственными и ранговыми кодами. Ранговые коды были введены Э. М. Габидулиным в начале 80-х годов прошлого века [1] и к настоящему времени хорошо исследованы. Они приобрели широкую известность, дав начало новому принципу построения криптосистем с открытым ключом [2], и в связи с задачами пространственно-временного кодирования для радиоканалов с множественными антеннами [3]. В последние годы внимание привлек новый подход к организации трафика в сетях с коммутацией пакетов, эксплуатирующий идею формирования линейных комбинаций ретранслируемых пакетов в промежуточных узлах сети [4], [5], [6], [7]. Это привело к появлению новых схем сетевого кодирования и вызвало интерес к изучению подпространственных кодов, элементами которых являются конечномерные линейные пространства [8]. Была обнаружена тесная связь новых подпространственных кодов с изученными ранее ранговыми кодами, что стимулировало как определенный прорыв в теории подпространственных кодов, так и возрождение интереса к ранговым кодам. Обзор построен следующим образом. В разделе 1 обсуждаются постановки задач кодирования для метрических пространств с хэмминговой, ранговой и подпространственной метриками. В разделе 2 приведены известные верхние границы для мощностей кодов. Здесь обсуждаются также новейшие оценки размеров списков при списочном декодировании ранговых кодов. Обзор конструкций кодов в ранговой и подпространственной метриках дан в разделе 3. Особенности алгоритмов декодирования обсуждаются в разделе 4. В разделе 5 обсуждается общее состояние дел и нерешённые проблемы.