Недвоичные линейные покрывающие коды

Обозначим через F₉ поле Галуа из q элементов. Пусть F* = F₉ \ {0}. Пусть F” -п-размерное векторное пространство над F^. Обозначим [п,п — т]_ц q-ичный линейный код длины п и коразмерности (избыточности) т, который является подпространством пространства F” размерности п — т. Сфера S (с, R) радиуса R с центром св F” - это множество вида {v : v G F”, d(v, с) < R}, г де d(v, с) - расстояние Хэмминга между векторами v и с.

Определение 1. Рассмотрим два эквивалентных определения.

• (І)    Радиус покрытия линейного [п,п — т]_ц-кода - это наименьшее целое R, такое, что пространство F” покрыто сферами радиуса R, центрированных на кодовых словах.

• (ii)    Линейный [п, п— т]_ц-код имеет радиус покрытия R, если каждый столбец пространства F равен линейной комбинации не более чем R столбцов проверочной матрицы кода и R - наименьшее целое с таким свойством.

Обозначим [п, п — т]_ц-код с радиус ом покрытия R как [п, п — т]_ц R-код. Для введения в покрытия пространств Хэмминга над конечными полями см. [1-4]. Для введения в теорию кодирования, частью которой является исследование покрывающих кодов, см. [5-8].

Для [п, п — т]_цR-кода плотность покрытия р определяется как отношение суммарного объема всех q^n-T сфер радиуса R, центрированных на кодовых словах, к объему qⁿ пространства F”. По определению l(i), р > 1. Другими словами,

* = (^ £ (q — ¹⁾‘ ( " )) q” = 1 g (q — < ) > ¹          <»

Качество покрытия лучше, если плотность покрытия меньше. Для фиксированных параметров q, т, R, плотность покрытия [п, п — т]цR-кода уменьшается с уменьшением длины п.

Коды, исследуемые с точки зрения качества покрытия, обычно называются покрывающими кодами (.cowering codes) [1] в противоположность кодам, исправляющим ошибки; см. онлайн библиографию [9], работы [2,4,10-47] и ссылки в них.

Изучение покрывающих кодов - классическая комбинаторная проблема. Покрывающие коды связаны с различными областями теории и практики, например, с исправлением ошибок и стираний, сжатием данных, памятью с одноразовой записью, теорией футбольного тотализатора (так называемого «footbal pool»), графами Кэли, так называемыми играми Бэрлекампа-Гэйла, см. [1, глава 1.2]. Коды радиуса покрытия 2 и коразмерности 3 являются релевантными для проблемы «степень/диаметр» в теории графов [41,48] и для определяющих множеств в блок-схемах [49]. Покрывающие коды могут использоваться в стеганографии [5, глава 14], [16,35,36], в построении баз данных [40], при конструировании идентификационных кодов [34,43], для решения задачи паритетности обучения и шума (learning parity with noise) [38], при анализе блоковых переключателей [50], в представлении логических функций [11], в списочном декодировании кодов, исправляющих ошибки [17], в криптографии [51]. Существует интересная связь между покрывающими кодами и популярной пазл-игрой «Шляпы на линии» («Hats-on-a-line») [10,45].

Если радиус покрытия R и коразмерность т фиксированы, то проблемой покрытия является построение кодов относительно небольшой длины и/или получение хороших оценок длины.

Определение 2. Функция длины £_q (т, R) - это наименьшая возможная длина q-ичного линейного кода коразмерности (избыточности) т и радиуса покрытия R.

Во всей статье с и с являются константа ми, независимыми от q, но возможна их зависимость от т и R. В [14,24], [31, предложение 4.2.1], см. также ссылки в этих работах, рассмотрена ниэюняя граница, связанная с (1):

lq (т, R) >  сq^(r-R'^)/R, R и т фиксированы.                        (2)

В [4,21] граница (2) дана в другой (асимптотической) форме.

Открытая проблема 1. Доказать, что нижняя граница (2) функции длины l_q(r,R) достигается, возможно, асимптотически при достаточно больших значениях q. Определить значения константы с для различных г и R.

В настоящее время открытая проблема 1 решена толвко для специальных сочетаний параметров q, R, г. Пусть t, s, t* - целые и q‘ - степень простого числа. В литературе доказано, что в следующих случаях граница (2) достигается:

г = tR, q = (q')R, [4,21,31,32,39,41];(3)

R = sR*,г = tR + f s, 1 6 f < R*, q = (q')R*, [4.21.31];(4)

г = tR, q - произвольная степень простого числа, [4.19.21.23.28.29].(5)

Мы говорим: «q является произвольной степенью простого числа», имея в виду, что структура q произвольная, например, другая, чем в (3), (4). Случаи (3) - (5) подробнее рассмотрены в разделе 3.

В общем случае для произвольных г, R, q, в частности, когда г = tRu q является произвольной степенью простого числа, проблема достижения границы (2) остается открытой.

В литературе [12-15,24-26,46,49,52], верхние границы lq(г,R') получены в форме lq(г, R) 6 cq(-R/R • Л/М, г = tR, q - произвольная степень простого числа,    (6)

см. подробнее в разделе 4.

Замечание 1. В границе (6) множитель ^in q - это «цена» произвольной структуры q.

Открытая проблема 2. Доказать, что верхняя граница (6) функции длины l_q(г,R') справедлива. Определить значения константы с для различных г и R.

В этой работе выполнен обзор известных результатов по решению открытых проблем 1 и 2 для недвоичных кодов с q >  2. Насколько известно автору, в опубликованной литературе такой обзор не представлен.

Линейные покрывающие коды и насыщающие множества в проективных пространствах над конечными полями - эквивалентные комбинаторные объекты, см. раздел 2. Поэтому данный обзор полезен и для проективной геометрии.

Отметим, что для построения бесконечных семейств покрывающих кодов продуктивным является следующий подход. Для относительно небольшого значения г геометрическими методами строится насыщающее множество в проективном пространстве, эквивалентное [п, п — г]qR-коду. Затем, используя лифт-конструкции, получаем бесконечное семейство кодов с растущей коразмерностью г. Эффективными лифт-конструкциями являются каскадные q^m-KOHCTpyKpHH удлинения покрывающих кодов, см. раздел 5. Такой подход использован, например, в работах [4,12-15,19-26,29,30].

Статья организована следующим образом. Раздел 2 описывает взаимно-однозначное соответствие между линейными покрывающими кодами и насыщающими множествами в проективном пространстве. В разделах 3 и 4 рассматриваются описанные в литературе случаи решения открытых проблем 1 и 2 соответственно. В разделе 5 приведены каскадные qm-KOHCTpyKpHH удлинения покрывающих кодов как инструмент построения бесконечных кодовых семейств растущей коразмерности. В разделе 6 отмечены некоторые проблемы многократных покрытий.

2.    Эквивалентность линейных покрывающих кодов и насыщающих множеств в проективных пространствах

Насылцаюгцие множества ^saturating sets') в проективных пространствах над конечными полями комбинаторно эквивалентны покрывающим кодам и полезны для их построения и оценки границ.

Обозначим PG(^, q) - Жразмерное проективное пространство пан полем Fq. Точку пространства. PG(^, q) в гомогешічпых координатах лозкыо рассматривать как вектор из F^+1.

Определение 3. Множество точек S С PG(N,q) является рнасыщающим (рsaturating), если каждую точку из PG(N, q) можно представить линейной комбинацией не более чем р + 1 точек из S, и р является наименьшим целым с этим свойством, ср. определение l(ii).

В англоязычной литературе насыщающие множества называют также «saturated sets», «spanning sets», «dense sets».

Обозначим s_q(N, р) - наименьший возможный размер ^насыщающего множества в пространстве PG(N, q).

Если д-ичные позиции ст*>лбца проверочной (г х п)-матрппы [п,п — г]9Д-кода трактуются как гомогеничные координаты точки из PG(г — 1,q), тогда эта матрица определяет (R — 1)-насыщающее множество размера п в PG(г — 1,q), обратное также верно. Таким образом, существует взаимно-однозначное соответствие между [п, п — г^R-кодами и (R — 1)-пасыщаюпшмн п-миожествами в пространстве PG(г — 1, q). Поэтому lq (г,R) = Sq (Г — 1,R — 1). (7)

Для введения в проективную геометрию над конечными полями и ее связь с теорией кодирования см. [4,33,37,42,44,53-56]. В работах [3,4,12-15,18-33,37,39,41,42,44,46,47] рассмотрены различные аспекты покрывающих кодов и насыщающих множеств, включая их совместные исследования.

3.    О решении открытой проблемы 1

Если существует [п,п — г]_qR-код, тогда l_q(r,R) 6 п. Теоремы 3-15 описывают параметры бесконечных семейств покрывающих кодов, полученных в литературе, и тем самым дают конструктивные верхние границы функции длины l_q(pR), эти границы можно рассматривать как решение открытой проблемы 1.

3.1.    Случай г = tR, q — произвольная степень простого числа

В рассматриваемом и других случаях полезна и часто используется так называемая конструкция прямой суммы [1,2,4], формирующая [п1 + п₂,п1 + п₂ — (г1 + г₂)]_qR-код радиуса покрытия R = R 1 + R₂ из двух кодов [пі, п 1 — г₁]_q R 1 и [п₂, п₂ — г₂]_qR₂.

Теорема 3. Существуют бесконечные семейства [п, п — г]_q 2-кодов радиуса покрытия R = 2, коразмерности г = 2t и следующими параметрами:

(i) R = 2, г = 2t > 4, t >  2, q = 3, г = 8, [4, раздел 4.3], [27]

п = 5 • 3('-2)/2 — 1 + < 22

0,                если г = 4с + 2 2 • 3'/4 — 2,       если г = 8с + 4 . 2 • 3(г+4)/4 — 2, если г = 8с

(ii) R = 2, г = 2t > 4, t > 2, q > 7, q = 9, г = 8,12, [4. раздел 4.3]. [29]

п = 2q⁽'^-2)^/2 + q^^-4/ .

• (iii)    R = 2, г = 8,12, q > 7, q = 9, [4. раздел 4.3]. [29] п = 2q⁽'^-2)/² + q('^-4)/² + q('^-6)/² + q('^-8)/².

• (iv)    R = 2, г = 2t > 4, t >  2, q = 4, 5, 9, г = 8,12 для, всех q, [4. раздел 4.3]. [20] г = 14, 20 д.:ія q = 4, п = 2q^(r-2)/2 + q^(r-4)/2 + ^q^(r-6)/²j .

• (v)    R = 2, q = 4, 5, 9, [4. раздел 4.3]. [20]

п = 2q³ + q² + 2q + 2 4- ія г = 8, п = q⁵ + (q⁶ — 1)/(q — 1) 4- -ія г = 12.

Теорема 4. Существуют бесконечные семейства [п,п — г]_у 3-кодов радиуса покрытия R = 3, коразмерности г = 3t и следующими параметрами:

• (i)    R = 3, г = 3t > 6, t >  2, q > 5 и г = 9, [4, раздел 5], [29] г = 9 и q = 16, q > 23, п = 3q("^-3^/³ + q^(r-6)/3.

• (ii)    R = 3, г = 9, q = 5, 9, п = 3q² + 2q + 2. [4, раздел 5], [30]

• (iii)    R = 3, г = 9, q = 7, 8,11,13,17,19, п = 3q² + 2q + 1. [4, раздел 5], [30]

• (iv)    R = 3, г = 3t, t = 6 и t >  10, q = 3, п 6 ^p^q^-³)/³. ^^’ ^теоР^ема Ю]

• (v)    R = 3, г = 3t, t = 4 и t >  7, q = 4, п 6 —lq(^r-3)^/3. [30, теорема 11]

Теорема 5. Существуют бесконечные семейства [п, п — г]_у R-кодов радиуса покрытия

R >  4, коразмерности г = tR и следующими параметрами:

(i) R > 4, п = Hq^^r-R^^/R + q^(r-2K)/R + Ay(г, R), г = tR, [23, теорема 1] где для mi = [log_y(R + 1)] + 1 справедливо

• (а)    A_y(г, R) = 0, если t = 2, q = 4 и q >  7, R >  4;

• (b)    A_y(г, R) = 0, если t = 2, q = 5, R = 4, 5;

• (с)    A_y (г, R) = 0, если t >  [logy R] + 3, q >  7 нечетно> R >  4; t

• (d)    A_y (г, R) = £ q⁽'^r-j^R)/^R, _еслп m1 +2 < t < 3m1 +2, q >  8 чет ное, R >  4; 3=2

  m1+2

  (е) Ay(г, R) = £ qC-3^R/R , 3=2

  
  

если t = mi +2 и t > 3m1 + 2, q > 8 чет ное, R >  4.

(ii) R > 4, п = Rq^(r-R)/R +

[ RI

q⁽-r ^2R)/R + ^_y(г, R), [4, теоремы 6.1, 6.2], [21,29]

г = tR, t >  2, где

• (a)    5_y(г, R) = 0, если q > 4, г = 2R;

• (b)    5_y (г, R) = 0, если q = 16, q > 23, г = 3R;

• (c)    5_y (г, R) = 0, если q > 7, q = 9, г > 5R, г = 6R;

• (d)    5_y(г, R) = (2R mod 3) • (q^{(r 3R)/R} + 1), сслзі q > 7, q = 9, г = 4R, 6R.

3.2.    Случай г = tR, q = (q')R, q' - степень простого числа

Чтобы получить результаты теоремы 5(i), в [23] предложена геометрическая конструкция «Линия+Овалы» («Line+Ovals»), формирующая (R — 1)-насыщающие (Rq + 1)-множества в проективном пространстве PG(2R — 1,q). Эта конструкция обобщает конструкции «овал плюс линия» [19, теорема 5.1], [57, р. 104] и «два овала плюс линия» [28]. Полученное насыщающее множество соответствует [Rq + 1,Rq + 1 — 2R]_y R покрывающему коду. Он, в свою очередь, используется как стартовый код каскадной q^m-KOHCTpyKpnn, формирующей бесконечное кодовое семейство.

Результаты теоремы 5(ii) получены в том числе применением конструкции прямой суммы к результатам теорем 3 и 4.

Отметим, что в теореме 5 при одинаковых параметрах г, R, q-коды в ситуации (i), как правило, короче кодов для случая (ii). Однако для некоторых сочетаний г, R, q-коды в (І) не существуют, и тогда нужно использовать (ii).

В работе [4] введен полезный для построения насыщающих множеств в проективных пространствах геометрический объект - многократное строго блокирующее множество.

Определение 4. [4, определение 3.1] Пусть 2 <  t <  v. Множество точек В в проективном пространстве PG(v,q) является t-кратным строго блокирующим множеством tMold strong blocking set), если каждое (t — 1)-размерное подпространство PG(v,q) порождается t точками it 5 В.

В англоязычной литературе многократные строго блокирующие множества называют также generator sets [58, определение 2] и cutting blocking sets [39], [59, определение 3.4].

Теорема 6. [4, теорема 3.2] Пусть R >  2 - целое число ид’ - степень простого числа. Пусть q = (q')^R. Пусть v >  R. Тогда любое R-кратное строго блокирующее множество S в подпространстве PG(v,q') С PG(v,q) является (R — 1)-насыщающим множеством в PG(v,q), эквивалентным линейному [|S|, |S| — (v + 1)]_q R покрывающему коду.

Результаты теорем 7-9 получены с помощью построения многократных строго блокирующих множеств в проективных пространствах небольшой размерности и вытекающих из них насыщающих множеств. Затем покрывающие коды, соответствующие этим насыщающим множествам, используются как стартовые коды в каскадных qm-KOHCTpyKii,HHx для получения бесконечных кодовых семейств.

Теорема 7. Существуют бесконечные семейства [n, n — r]_q2-кодов радиуса покрытия R = 2, коразмерности г = 2t + 1 и следующими параметрами:

• (i)    R = 2, г = 2t + 1 > 3, t >  1, q = (q')² > 16, q'- степень простого числа,

n = 3q^(T-2)/2 — q^(T-3)/2 + [q^(r-5)/2J

[4, формула (4.12)], [19, теорема 5.2], [20, пример 6], [23, замечание 4], [41].

• (ii)    R = 2, г = 2t + 1 > 3, t >  1, q = (q')⁴, q'- степень простого числа, п = 2q⁽ t^{- 2) / 2} + 2q^(r-2.5)^/2 + 2q⁽T^-3)^/2 + )д^(т'^-)/Ч [4- теоремы 3.4. 4.3].

• (iii)    R = 2, г = 2t + 1 > 3, t >  1, г = 9,13, q = (q')⁶, q' < 73 - простoe число,

  n = (2 + 4= + 6^

  
  

  -^= + —^ q^{(T 2)/2} + 2[q^{(T 5)/2}J [4. тео}:>сма 4.5].

Для г = 3 из теоремы 7 получаем [3q — 1, 3q — 1 — 3]q2-код над полем F(_Q‘)2. Этот в некотором смысле знаковый результат получен в [19, теорема 5.2] на алгебраическом языке и проанализирован с геометрической точки зрения в [23, замечание 4]. Начало исследований в этой области положено в статье [60], где на геометрическом языке построен [3q, 3q — 3]q2-код, иногда называемый «пример Уги (Ughi)».

Теорема 8. [4, теоремы 5.1, 5.2] Пусть q' - степень простого числа. Существуют бесконечные' семейства [n,n—r]_q3-кодов радиуса 'покрытия R = 3. коразм::рности г = 3t+1, 3t+2 и следующими параметрами:

(1) R = 3, г = 3t + 1 > 7, t > 2, q = (q')³ > 64, n = 4q^(T-3)/3 + 4q^(T-4)/3.

(9 — 4 + ^ q(T-3)/3

^q  Vi2

(ii) R = 3, r = 3t + 2 > 8, t >  2, q = (q')³ > 27, n 6

Теорема 9. [4, теорема 6.3] Пусть q' - степень простого числа. Существуют бесконечные' семейства [n, n — r]_qR-кодов радиуса 'покрытия R >  4. коразм::рности r = tR + 1 и следующими параметрами:

R > 4, r = Rt + 1, q = (q')R, t = 1 11 t > to, qto 1 > nR,q, nR,q = ( ^Q — 1) (^(МИ — 2^ + R + 5, n 6 nR,q • qq'-R-C/R + wq(T R 1)/^ — 1 2                                                  q — 1

w = 0 для q' > 4, w G {0,1} для q' = 3.

Теорема 10. [31, следствие 7.2.11] Пусть q' - степень простого числа. Существуют бесконечные семейства [n, n — г]q R-кодов радиус а покрытия 3 6 R 6 г — 1, коразмерности г и длины n 6

^{R(R +} 1) Дт-ИДК

2 q

+ (R — 1)R

Qt - RPR _— q^1/R — 1

q = (q')^R

Результаты теоремы 10 получены (на языке насыщающих множеств) в [31] с помощью оригинального геометрического подхода, использующего аффинные подгеометрии. Для простоты представления [31, следствие 7.2.11] аппроксимирует другие результаты [31], которые на самом деле слегка лучше, чем в (8).

Для больших радиусов покрытия R результаты теорем 9 и 10 можно улучшить, применяя [39, следствие 6.7].

3.3.    Случай R = sR*, г = tR+Ps, 1 6 te < R*, q = (qr)R*, q' - степень простого числа

Мы рассматриваем непростые радиусы покрытия R = sR* для целых s и R*.

Теорема 11. [4, лемма 7.1] Пусть R = sR * . Пусть существует [n * , n * — (tR * + t^e)]_q R*-код радиуса покрытия R * > t* >  1. Тогда существует [sn * , sn * — (tR + st ^ )]_q R-код радиуса покрытия R.

Теорема 12. [4, разделы 4.4 и 7, следствие 7.2], [20, пример 6], [21] Для четных радиусов покрытия R > 4 существуют бесконечные семейства [n, n — г]_q R-кодов коразмерности г = tR + ^R и следующими параметрами:

• (i)    q = (q')², q' ~ степень простого числа, t > 1, n = ^R (3 — —) q^-^-K/R + ^R ^—q^(r-2R)/RJ .

• (ii)    q = (q')⁴, q' - степень пуюстого числа, t > 1,

  - = R (¹⁺ - + -) ^q,-^'^R +R [ ^^J.

• (iii)    q = (q')⁶, q' - простoe число , q' < 73, t > 1, t = 4, 6,

  n = R (

  
  
  
  
  
  

  ^{1 +} "ёж ⁺ Аж ⁺—ж ) ⁷ ^9  ^7

  
  

  .(r-R)/R + _R ।   ¹_q( r -2 K ) /lJ .

  
  

Теорема 13. [23, теорема 2] Рассмотрим четный радиус покрытия R > 2. Пустъ р -простое число, q = р^2т! , т) >  2. Тогда существуют бесконечные семейства [n, n — г]_ц R-кодов коразмерности г = tR + ^R, t > 1, и следующими параметрами:

• (i)    n 6 R (1 +     z-⁷ — ¹   . ) q "і^ + R I q^{(r 2R/R} ° - ⁵ I + ^Rfq (г, R), р > 3;

vq )^{—                               2}

• (ii)    n 6 R (1+1+4=) q^(r-R)/R + R I q^(r-2R)/R-°^-5 I + ^R/ q (г, R), р > 7;

V р VqJ             ^{L           J 2}

где p(q) - порядок наименьшего собственного подполя поля F_q;

/ q ^(-r,R) = I

для г = 9R/2,13R/2

для г = 9R/2,13R/2

q( r -3 R ) /R -° . 5 + q( r -4 R ) /R -° . 5

Теорема 12 использует теоремы 7 и 11. Теорема 13 использует теорему 11 и дважды блокирующие множества в проективной плоскости.

Если Дц = р^ для не четного ту > 3, тогда коды теоремы 13 короче, чем в теореме 12. Например, если q = р⁶, ту = 3, длина кода теоремы 13(ii) на Rq^(r-R)/R-1/3 меньше, чем в теореме 12. Кроме того, результаты теоремы 13(ii) справедливы для всех р >  7, тогда как в теореме 12(ііі) р 6 73. Наконец, для нечетного ту > 5, в кодах теоремы 12 главный член 2 Rq^(r-R''^)/R. тогда как в теоутеме 13 он равен Rq^(r-R''⁾^^R.

Теорема 14. [4, следствие 7.3] Пусть q* - степень простого числа и 3 делит R. Тогда существуют бесконечные семейства [n, п — г]_ц R-кодов со следующими параметрами:

• (i)    R = 3s, г = tR + 3, q = (q*)³ > 64, t > 1, n 6 ^3

  ( i+у) ,<^r- « > /« .

  V V^

  
  

  (ii) R = 3s, г = tR +-^, q = (q*)³ > 27, t > 1, n 6 ^R ^9

  
  

  _-

  
  

  _8_ ₊       I _O( r - R ) /R

  y⁺ y? "

  
  

  .

  
  

Теорема 15. [4, следствие 7.4] Пусть q' - степень простого числа, R = sR* и q = (q^r)^R . Тогда существуют бесконечные семейства [п, п — г]^ R-кодов со следующими параметрами:

R = sR*, R* > 4, г = Rt + s, q = (q')R , t = 1 a nd t > to, qto 1 > nR* q, nR.q = ( ^^q — 1) (— 2) + R* +5, п 6 s ^nR.j9 • q(r R s)/R + w —

, (r-R-s)/R

-

^{q — 1}

, w = 0 для q' > 4, w Е {0,1} для q’ = 3.

Дальнейшие результаты для рассматриваемой ситуации R = sR* можно получить, применяя теорему 11 к теореме 10.

4.    О решении открытой проблемы 24.1.    Покрывающие коды над маленькими полями

Мы приводим результаты из [30], формально удовлетворяющие границе (6).

Теорема 16. [30, теоремы 7-9,12,16,17] Существуют бесконечные семейства [n, п — г]_ц3- кодов радиуса покрытия R = 3 со следующими параметрами:

	'(7 • 3t — 3)/4             для t = 0, 2 (mod 4)
(i) q = 3, n = <	(7 • 3t + 3(t+3)/2 — 6)/4 для t = 1  (mod 4)   , г = 3t + 1, t = 2 и t >  4. _ (7 • 3t + 3(t+5)/2 — 6)/4 для t = 3  (mod 4)

'(11 • 3^t — 3)/4            для t = 0, 2  (mod 4)

(ii) q = 3, n = < (11 • 3^t + 3^(t+3)^/2 — 6)/4 дл st = 1  (mod 4)   , г = 3t + 2, t = 2 и t >  4.

(11 • 3^t + 3^(t+5)/2 — 6)/4 для t = 3  (mod 4)

(iii) q = 4, n = 341 • 4^t-4, г = 3t + 1, t = 4 и t >  7.

(iv) q = 4, n = 54 • 4^t-3, г = 3t + 2, t = 3 и t >  6.

(v) q = 5, n = < '(5t+1 — 1)/4 + ^5(t, 2)                             для t = 1, 3 (mod 4) (5t+1 +5t/2 — 2)/4 + ls(t/2, 2) • 5t/2              для t = 2 (mod 4)   , ,(5t+1 +2 • 5(t+2)/2 — 3)/4 + l5(t:22, 2) • 5(t+2)/2  для t = 0 (mod 4) г = 3t + 1, t = 3 и t > 5.

(vi) q = 5, n = 267 • 5^t-3, г = 3t + 2, t = 3 и t >  6.

4.2.    Покрывающие коды над произвольными полями

Теорема 17. [13,14,46] Пусть q - произвольная степень простого числа. Существуют бесконечные семейства [п,п — r\_q 2-кодов радиус а покрытия R = 2 со следующими параметрами:

п 6 Ф(q) • q( ^2)/2 • // in q + 2 [q^{(r 5)/2}J, г = 2t + 1 > 3, г = 9,13, t >  1, t = 4, 6;

f 0.998Va < 1.729

ф(q) = *

1.05^3 < 1.819

v^+w+

V

3ln² q

+

V q In q

< 1.836

для q 6 160001

для. 160001 < q 6 321007 .

;

для. q >  321007

iim Ф(q) = V3. q ^^

Теорема 18. [14,24-26,61] Пусть q - произвольная степень простого числа. Пусть 5щ -дельта Кронекера. Существуют бесконечные семейства [п,п — г]_q 3-кодов радиуса покрытия R = 3 со следующими параметрами:

(І) п 6 С4 • q(r-3)/3 • //inq + 3[q(r-7)/3J + 2 ^(r-10)/3j + 5г,із, г = 3t + 1, t > 1; с4 <

(2.61 для 13 6 q 6 4373

(2.65 для 4373 < q 6 7577 ^.

(іі) п 6 С5 • q(r-3)/3 • //inq + 3[q(r-8)/3J + 2 |yr-n)/3J + ф, 14, г = 3t + 2

t >  1;

J2.785 для 11 6 q 6 401 (2.884 для 401 < q 6 839 ^.

В теореме 17 результаты для г = 3 получены на компьютере, если q 6 321007, и теоретическим путем, если q >  321007. При этом изящная геометрическая конструкция из [46] слегка модифицирована в [13,14]. В теореме 18 результаты для г = 4, 5 получены на компьютере. Остальные результаты в этих теоремах получены применением лифт-конструкций (каскадных q^m-KOHCTpyKций или q^m-concatenating constructions), в которых коды с г = 3, R = 2 и г = 4, 5, R = 3 использованы как стартовые.

Теорема 19. [26] Пусть q - произвольная степень простого числа, с и DRin - константы., нс. зависящие' от q: при этом D^™ зависит от R так. что min

R

—— /R(R — 1) • R! <

R — 1

1.651R	для	R > 3
0.961R	для	R > 7
0.498R	для	R > 36
0.4R	для	R > 178

.

Существуют бесконечные семейства [п,п — г]_q R-кодов радиуса покрытия R > 3 со следующими параметрами:

(і) п 6 cq^(r-K'^)/R • ^Ыд, R > 3, г = tR + 1, t >  1.

(іі) п <  (dR^ + R ²⁺ q^r— 1) ) q^(r-R)/R • /inq <  3.43Rq^(r-R)/R • /М, V q in q

R > 3, г = tR + 1, t > 1, q достаточно большое, для t > 2 граилыщ, справедлива, если DR™ /q in q + 2R 6 q + 1.

Для t = 1 результаты теоремы 19 получены на языке насыщыющих множеств в [26], где предложена конструкция, которую можно рассматривать в широком смысле как обобщение конструкции [46] из плоскости на пространство. Затем применяются каскадные q^m-KOHCTpyKpHH, формирующие бесконечные кодовые семейства с растущей коразмерностью г.

5.    Каскадные (/"-конструкции ((/"-concatenating constructions) удлинения покрывающих кодов

Каскадные (/"-конструкции удлинения покрывающих кодов являются мощным инструментом построения бесконечных кодовых семейств. В англоязычной литературе они называются «/"-concatenating constructions». Эти конструкции предложены в [18] и развиты в [4,14,19-22,29,30], см. также ссылки в этих работах и [1, раздел 5.4]. Каскадные /"-конструкции для фиксированного радиуса покрытия R получают бесконечные семейства [п, п — r]_qR покрывающих кодов растущей коразмерности г, используя стартовые коды с относительно небольшим значением г. Плотность покрытия кодов из бесконечных семейств приблизительно такая же, как у стартовых кодов.

Мы описываем здесь базовую каскадную (/"-конструкцию QM и приводим два конкретных варианта, названных в литературе QMi и QM4.

Все матрицы и столбцы являются /-ичными. Элемент поля Fq™, приведенный в /-ичной матрице, обозначает /-ичное представление этого элемента, записанное в виде m-размерного /-ичного столбца.

Базисная конструкция QM. Пусть столбец h j G F^ и пусть H o = [ h i Һ 2... h „₀ ] является проверочной матрицей [по, по — ro]_q R стартового кода Bq. Пусть m > 1 - целое, зависящее от по. Ассоциируем с каждым столбцом hj элемент 3j G F_q™ U {*}, такой что 3г = 3j, ^если ^ = 3- Назовем 3j индикатор ом столбца h j, а В = {31,32 , ..., 3п0 } С F_q™ и {*} - множеством ндикаторов. Пусть C -матрица размера (t q + Rm) х N_m, где N_m <  RQ_m,_q, ©_m,_q = (q^m — 1)/(/ — 1)- В заключение определим V как [п, п — (t q + Rm)]_q Ry код длины п = /^тпо + N_m и проверочной матрицей следующей формы:

B j =

h j

£i

h j    • • •    h j

0   •••0

• ♦                     ••

• ♦                     ••

• ♦                     ••

0   •••0

£2   • • •

ДЛЯ 3j = *,

H y = [ C B i B 2 ... B „ 0] ,

	h j	h j       •	•        h j
	£i	£2       •	•      £ q ™
	3 j £1	3 j £2     •	•    3 j £ q ™
B j =	32£i	32£2    •	•    32£ q ™	для 3j G Fq™

3 R ^-i£i 3 R ^-i£2  ••• 3 f ^-1^ ^

^гД^{е {£}1, ^£2, . . • , ^£q™ ^} = Fq™.

Если m, C, В выбраны правильно, радиус покрытия Ry нового кода V равен радиусу покрытия R стартового кода B q .

Введем обозначения:

Wm ~ проверочная матрица [0m,q, 0m,q — m]q 1 кода Хэмминга;

l_q(г, R) - наименьшая известная длина [п, п — r]_qR-покрывающего кода радиуса покрытия R п коразмерности г (очевидно. lq (г, R) 6 l_q(г, R)):

A r," ~ проверочная матрица [l_q(mR, R),l_q(mR, R) — mR]_qR-KOfla;

0^ - нулевая матрица с k строками (число столбцов определяется контекстом).

^R,_m ^- «прямая сумма» R матриц W_m, т.е. (Rm х RB_m,_q)-матрица вида

	Wm  0 m   • • •   0 m 0 m   Wm  • • •   0 m
^ R,m —	•                        •                 .                        • •                        •                     •                     • •                        •                                           ■ 0 m 0 m • • •   W m

Конструкция QM 1. Здесь R > 2, q^m + 1 > по, В С F.™ и {*},

C =	0    ] , п = qmпо + RӨm,q . ^R,m J

Конструкция QM 4. Здесь R > 2, q^m — 1 > п₀, ВС F*_m,

C =	= lR;0J.m 0 m;R/2J   ,п < qm„0 + fl 9m, + I. Mf , f ). O mfR/2]    A fR/21,m

Теорема 20. [4,19] Новый [п, п — (го + Rm)]₉ Ry-код V, полученный конструкуиями QMi и QM4• имеет радиус покрытия Ry. равный радиусу покрытая R стартового кода V0.

Разнообразные варианты каскадных дт-конструкций приведены в [4,14,18-22,29,30].

6.    О многократных покрытиях

Определение 5. Код С длины п и радиуса покрытия R называется (R, ^-многократным покрытием наиболее удаленных точек (или (R, ц)-МПУТ кодом для краткости), если для каждого слова ж G F” на расстоянии R от С существует по меньшей мере ц кодовых слов в < (]>ере Хэмминга S (ж, R) радиуса, R с центром в ж.

В англоязычной литературе код С из определения 5 называется (R, ц)-тиШр1е covering of the farthest-off points ((R, ц)-МСҒ code для краткости). Для введения в многократные покрытия см. [1,62-65] и ссылки в этих работах.

Многократные покрытия полезны, например, для изучения комбинаторной теории футбольного тотализатора (generalized football pool problem) [63] и для списочного декодирования корректирующих кодов [8,66,67].

Результаты о двоичных и троичных (R, ц)-МПУТ кодах представлены в [1,62,63]. Для недвоичных кодов см. [12,64,65,68,69].

В [64] введены многократные (р, ц)-насыщающие множества в проективных пространствах PG(^, q) комбинаторно эквивалентные линейным (р + 1,ц)-МПУТ кодам. Эта эквивалентность использована, в [64,65,68,69] для построения эффективных многократных покрывающих кодов с хорошими параметрами. В [12] применены вероятностные методы.

Для (R, ц)-МПУТ кода С длины п и радиуса покрытия R важной характеристикой является ц-плотности покрытия - cjщлпее значение величины Д #(S(ж,R') ПС). г,де ж G F” - слово на расстоянии R от С и среднее вычисляется над всеми такими словами. Очевидно, ц-плотность покрытия больше или равна 1.

Если минимальное расстояние d кода С не менее 2R — 1, тогда наилучшая ц-плотность среди линейных q-ичных кодов с той же коразмерностью г и радиусом покрытия R достигается самым коротким кодом. Важными классами являются почти совершенные и совершенные МПУТ коды, которые соответствуют оптимальным многократным насыщающим множествам. Для этих кодов каждое слово на расстоянии R от кода принадлежит точно ц сферам радиуса R, центрированным на кодовых словах; они имеют наилучшую возможную ц-плотность, равную 1.

Определение 6. Мы определяем ц-функцию длины l^(_R,r,q) как наименьшую возможную длину п линейного (R, ц)-МПУТ кода с параметрами [п, п — r]_qR и минимальным расстоянием d >  3.

Многочисленные примеры почти совершенных и совершенных недвоичных МПУТ кодов получены в [64,65,68,69] геометрическими и алгебраическими методами, в том числе с использованием распределения весов смежных классов кодов с масксимальным допустимым расстоянием (МДР кодов).

7.    Заключение

В работе представлен обзор известных результатов о недвоичных линейных [п, п — т]₉ R покрывающих кодах (covering codes) над полем F^, q > 2. Исследование покрывающих кодов - интересная комбинаторная проблема, важная с теоретической и практической точек зрения. Связи покрывающих кодов с другими областями исследований отмечены во введении с многочисленными ссылками на литературу.

Приведена известная нижняя граница функции длины l_q ( t,R ) т.е. наименьшей возможной длины q-ичного линейного кода коразмерности т и радиуса покрытия R. Сформулированы две открытые проблемы: построение кодов, асимптотически достигающих границы (открытая проблема 1), и кодов, имеющих близкие к границе параметры (открытая проблема 2). В разделах 3 и 4 подробно, с указанием параметров кодов, рассмотрены случаи, когда в литературе эти проблемы решены. Приведен обширный список литературы.

В разделе 2 описано взаимно-однозначное соответствие между линейными покрывающими кодами и насыщающими множествами в проективных пространствах PG(N,q). На протяжении всей статьи подчеркивается эффективность использования геометрических методов для решения открытых проблем.

В разделе 5 рассмотрены каскадные qm-кoнcтpyкции удлинения покрывающих кодов как инструмент построения бесконечных кодовых семейств растущей коразмерности.

В разделе б кратко указаны некоторые проблемы многократных покрытий. Разумеется, это направление заслуживает отдельного более подробного обзора.

Проведённый в разделах 3 и 4 анализ основных работ по теме недвоичных покрывающих кодов показал, что в настоящее время открытые проблемы 1 и 2 решены не для всех сочетаний параметров q, R, т. Изучение литературы и некоторый собственный опыт автора обзора позволяют предположить, что, по крайней мере, в ближайшее время для открытой проблемы 1 не следует ожидать принципиального изменения ситуации и расширения списка указанных сочетаний. Однако улучшение констант в формулах длины возможно, и именно это происходит в последние годы.

С другой стороны, в открытой проблеме 2 следует ожидать как расширения списка параметров, при котором проблема решается, так и улучшения констант.

Этот обзор существенно дополняет список из 69 публикаций классических и современных исследований.