The 18 reference contexts in paper V. Lipnitsky A., A. Aliaksiuk O., В. Липницкий А., А. Олексюк О. (2016) “Оценка минимальных расстояний не примитивных кодов Хемминга // Assessment of minimum distances of non-primitive Hamming codes” / spz:neicon:vestift:y:2015:i:2:p:103-110

  1. Start
    628
    Prefix
    К настоящему времени развита достаточно стройная теория помехоустойчивых кодов, равно как и практика их применения. Коды Хемминга – исторически первый класс кодов, разработанный Р. Хеммингом в конце 40-х годов XX в.
    Exact
    [1, 2]
    Suffix
    . Это класс совершенных линейных кодов, исправляющих лишь одну ошибку на каждый блок передаваемой информации. В начале 60-х годов XX в. положено начало исследованию свойств и применению кодов Боуза– Чоудхури–Хоквингема (БЧХ-кодов) [2], допускающих исправление многократных ошибок и включающих в себя как частный предельный случай коды Хемминга.
    (check this in PDF content)

  2. Start
    863
    Prefix
    Это класс совершенных линейных кодов, исправляющих лишь одну ошибку на каждый блок передаваемой информации. В начале 60-х годов XX в. положено начало исследованию свойств и применению кодов Боуза– Чоудхури–Хоквингема (БЧХ-кодов)
    Exact
    [2]
    Suffix
    , допускающих исправление многократных ошибок и включающих в себя как частный предельный случай коды Хемминга. Примитивные БЧХ-коды имеют достаточно завершенную и четкую теорию, являются наиболее применимыми на практике.
    (check this in PDF content)

  3. Start
    1520
    Prefix
    Видимо, из-за этих причин не примитивные БЧХ-коды не вызывают большого интереса в теории и практике помехоустойчивого кодирования. Белорусская школа кодирования ведет систематическую работу по исследованию не примитивных БЧХкодов
    Exact
    [3–5]
    Suffix
    . Цель данной статьи – доказательство того факта, что минимальное расстояние не примитивных кодов Хемминга может принимать сколь угодно большие значения. Необходимые сведения о кодах Хемминга. В данной работе мы опираемся на следующее определение О п р е д е л е н и е 1. [3] Двоичным кодом Хемминга называется линейный циклический код n cx, определяемый следующими тремя параметрами: 1) длина к
    (check this in PDF content)

  4. Start
    1797
    Prefix
    Цель данной статьи – доказательство того факта, что минимальное расстояние не примитивных кодов Хемминга может принимать сколь угодно большие значения. Необходимые сведения о кодах Хемминга. В данной работе мы опираемся на следующее определение О п р е д е л е н и е 1.
    Exact
    [3]
    Suffix
    Двоичным кодом Хемминга называется линейный циклический код n cx, определяемый следующими тремя параметрами: 1) длина кода п – любое нечетное число 7n≥; 2) (2 ) GFm – поле определения кода – имеет минимальное значение показателя m, при котором 21m- делится на п; 3) проверочная матрица кода nxc есть матрица h( ) (1, , , ..., ),21in-=β = ββ β (1) где β-примитивный корень n-й степен
    (check this in PDF content)

  5. Start
    2318
    Prefix
    нечетное число 7n≥; 2) (2 ) GFm – поле определения кода – имеет минимальное значение показателя m, при котором 21m- делится на п; 3) проверочная матрица кода nxc есть матрица h( ) (1, , , ..., ),21in-=β = ββ β (1) где β-примитивный корень n-й степени из 1, принадлежащий (2 )mGF. Данное несколько громоздкое определение требует пояснений. Согласно основам теории полей Галуа
    Exact
    [6, 7]
    Suffix
    , всякое конечное поле состоит из tq-элементов, где q – простое число; t – натуральное число, потому и обозначается через ()tGF q; ненулевые элементы этого поля образуют группу относительно операции умножения – мультипликативную группу *()tGF q; это циклическая группа порядка 1tq-; образующая a группы *()tGF q называется примитивным элементом поля (2 )mGF; поле ()tGF q содержит в качес
    (check this in PDF content)

  6. Start
    4441
    Prefix
    Для любого наперед заданного нечетного числа 1n> существуют поля (2 )tGF, такие, что 21t- делится на n. Одним из них является поле ()(2 )nGFφ, где ()nφ-количество целых k, 1 <kn≤, взаимно простых с n
    Exact
    [8]
    Suffix
    . Действительно, в силу теоремы Эйлера ()21(mod )nnφ≡ для любого нечетного n. Тогда ()21nφ- делится на n. Отсюда следует, что минимальное поле GF(2 )m с условием 21m- делится на n, будет подполем поля ()(2 )mGFφ, а следовательно, его показатель m будет делителем ()mφ.
    (check this in PDF content)

  7. Start
    9461
    Prefix
    Ведь такие коды практически передают только два сообщения: «точка» и «тире». В дальнейшем мы их не рассматриваем, имеется 23 таких кода из 150, из них в диапазон от 9 до 99 попадают коды длиной 11, 13, 19, 29, 37, 53, 59, 61, 67, 83. В
    Exact
    [3]
    Suffix
    описан ряд методов определения минимального расстояния линейного кода: по определению – составлением таблицы весов кодовых слов; по критерию, связанному со столбцами проверочной матрицы кода; синдромным методом; методом орбит.
    (check this in PDF content)

  8. Start
    10232
    Prefix
    Группа Г циклическая порядка n и порождена автоморфизмом s, действующим на каждый вектор 12( , , ..., )nv aaa= векторного пространства размерности n по правилу: s=s( ) ( , , ..., ) ( , , , ..., )12121nnnvaaaa aaa-=
    Exact
    [3, 9, 10]
    Suffix
    . Под действием группы Г векторы ошибок линейного кода разбиваются на непересекающиеся классы – Г-орбиты, состоящие из векторов, последовательно переходящих друг в друга под действием s. Как правило, Г-орбиты являются полными, т. е. содержат по n различных векторов.
    (check this in PDF content)

  9. Start
    11068
    Prefix
    2n- полных Г-орбит: (1, 2) , (1, 3) ,..., (1, 1)< > < > < ν+ > < > < > < ν+ >(1, 2) , (1, 3) ,..., (1, 1) для векторов (1, 2) (1,1, 0,..., 0)=, (1, 3) (1, 0,1, 0,..., 0),..., (1, 1) (1,0,...,0,1,0,...,0)v=+= (1, 3) (1, 0,1, 0,..., 0),..., (1, 1) (1,0,...,0,1,0,...,0)v=+= – вектор, у которого вторая единица стоит на месте под номером 1ν+, где n21= ν+
    Exact
    [3, 10]
    Suffix
    . Каждый вектор ошибок e в коде ncχ имеет свой синдром ()tSe h e= ⋅ – вектор из m-мерного двоичного линейного пространства. В [9] определена формула ( ( ))( ).S eSes =β⋅ (2) Из нее следует, что каждая Г-орбита e<> имеет четко очерченный спектр синдромов()Se<>, синхронно отражающий действие s на векторах Г-орбиты: если < >= s se ee e{,(), (),..., (), () },21nne ee-ss = то
    (check this in PDF content)

  10. Start
    11203
    Prefix
    1) для векторов (1, 2) (1,1, 0,..., 0)=, (1, 3) (1, 0,1, 0,..., 0),..., (1, 1) (1,0,...,0,1,0,...,0)v=+= (1, 3) (1, 0,1, 0,..., 0),..., (1, 1) (1,0,...,0,1,0,...,0)v=+= – вектор, у которого вторая единица стоит на месте под номером 1ν+, где n21= ν+ [3, 10]. Каждый вектор ошибок e в коде ncχ имеет свой синдром ()tSe h e= ⋅ – вектор из m-мерного двоичного линейного пространства. В
    Exact
    [9]
    Suffix
    определена формула ( ( ))( ).S eSes =β⋅ (2) Из нее следует, что каждая Г-орбита e<> имеет четко очерченный спектр синдромов()Se<>, синхронно отражающий действие s на векторах Г-орбиты: если < >= s se ee e{,(), (),..., (), () },21nne ee-ss = то S e( ) {(), (), (),...,21(), () ()}nnSeSeSeSeSeSe-<>= β⋅β⋅ β⋅β⋅=. (3) Иллюстрацией к формуле (3) является П р и м е р
    (check this in PDF content)

  11. Start
    12157
    Prefix
    , порожденной вектором (1, 9)e= в коде 17cχ Векторы Г-орбитыe()es2()es3()es4()es5()es6()es7()es8()es i1() eei = s-(1,9)(2,10)(3,11)(4,12)(5,13)(6,14)(7,15)(8,16)(9,17) deg ( )iSe9243954698499114129 Векторы Г-орбиты9()es10()es11()es12()es13()es14()es15()es16()es17()es i1() eei = s-(1,10)(2,11)(3,12)(4,13)(5,14)(6,15)(7,16)(8,17)(1,9) deg ( )iSe1441591741892042192342499 Как известно (например,
    Exact
    [3, 9]
    Suffix
    ), если минимальное расстояние линейного кода равно 21dt= +, то все векторы весом 1,2,...,t имеют попарно различные синдромы. Верно и обратное. Л е м м а 1. если все векторы ошибок весом 1,2,..., , 1,tt≥ имеют попарно различные синдромы в линейном коде ,c то минимальное расстояние этого кода 21dt≥+.
    (check this in PDF content)

  12. Start
    15493
    Prefix
    В самом деле, ( 1) 12( 1)(1...)(1 ) 1...0. 11 sp ssps ts sps hcss χ +β + +β+β+β ⋅ = +β +β + +β=== +β+β Лемма 2 полностью доказана. Из нее непосредственно вытекает Т е о р е м а 1. Минимальное расстояние d кода cχ находится в диапазоне min
    Exact
    [3, ]
    Suffix
    p для минимального простого делителя min1p> длины кода n. В частности, если n делится на 3, то минимальное расстояние равно 3; если n делится на 5, то d принимает одно из 3 значений: 3, 4 или 5. П р и м е р 4.
    (check this in PDF content)

  13. Start
    17319
    Prefix
    Для построения квадратично-вычетных кодов (КВ-кодов) нужны два простых числа p и l, при этом l является квадратичным вычетом по модулю p. В результате получается код, определенный над полем GF(l). Ограничимся рассмотрением важнейшего для практики случая 2l=. Как известно (например,
    Exact
    [6]
    Suffix
    ), число 2 является квадратичным вычетом по простому модулю p тогда и только тогда, когда p имеет вид 81k±. Именно такие простые числа p мы и будем рассматривать. КВ-код определяется минимальным расширением поля ( )(2)GF lGF=- полем (2 )mGF, содержащим группу pc корней p-й степени из 1.
    (check this in PDF content)

  14. Start
    18415
    Prefix
    Минимальное расширение поля (2)GF, содержащее подгруппу pc корней порядка p из 1, имеет вид (2 )mGF, где m является натуральным делителем числа ( 1) / 2p-, в частности, совпадает с ( 1) / 2p-. Заметим, что простых чисел p вида 81k± бесконечно много
    Exact
    [8]
    Suffix
    . Составим перечень всех простых чисел вида 81pk= ± в диапазоне от 7 до 309 соответствующих им значений ( 1) / 2p-, а также минимальных значений m с условием: 21m- делится на p (табл. 5). В табл. 5 представлено 28 значений 81pk= ±.
    (check this in PDF content)

  15. Start
    19087
    Prefix
    с ( 1) / 2p-, для 10 значений m является делителем ( 1) / 2p-: в двух случаях (113, 281p=) ( 1) / 2 2pт-=, в одном случае (31p=) ( 1) / 2 3pт-=, в трех случаях (73,89, 233p=) ( 1) / 2 4pт-= ( 1) / 2 4pт-=, в двух случаях (151, 241p=) ( 1) / 2 5pт-=, в одном случае (257p=) ( 1) / 2 8pт-= и в одном случае (127p=) ( 1) / 2 9pт-=. Согласно определению (например,
    Exact
    [2, с. 190]
    Suffix
    ), циклический двоичный код длиной n-это идеал в кольце (2)[ ]/1nnR GF x x=< ->, в фактор-кольце кольца (2)[ ]GFx полиномов с коэффициентами из (2)GF по идеалу 1nx< ->, порожденному полиномом 1nx-.
    (check this in PDF content)

  16. Start
    19465
    Prefix
    (например, [2, с. 190]), циклический двоичный код длиной n-это идеал в кольце (2)[ ]/1nnR GF x x=< ->, в фактор-кольце кольца (2)[ ]GFx полиномов с коэффициентами из (2)GF по идеалу 1nx< ->, порожденному полиномом 1nx-. Как и в кольце полиномов, всякий идеал J кольца nR является главным, порожден полиномом ()gx наименьшей степени, принадлежащим идеалу J. Таким образом, ()Jgx=<> (
    Exact
    [2, с. 191]
    Suffix
    ). С этой точки зрения код Хемминга длиной n есть идеал ()J Mxβ=<> кольца nR, где, как уже отмечалось выше, Mx()β – неприводимый на /2zz полином с корнем β [2]. Таблица 5. Простые числа вида =8 ±1pk в диапазоне от 7 до 309 соответствующих величин (p–1)/2 при условии, что 2m–1 делится на p pm12p-pm12p-pm12p7 17 23 31 41 47 71 73 79 89 3 8 11 5 20 23 35 9 39 11 3 8 11 15 20 23 35 36 39 44 97 10
    (check this in PDF content)

  17. Start
    19635
    Prefix
    Как и в кольце полиномов, всякий идеал J кольца nR является главным, порожден полиномом ()gx наименьшей степени, принадлежащим идеалу J. Таким образом, ()Jgx=<> ([2, с. 191]). С этой точки зрения код Хемминга длиной n есть идеал ()J Mxβ=<> кольца nR, где, как уже отмечалось выше, Mx()β – неприводимый на /2zz полином с корнем β
    Exact
    [2]
    Suffix
    . Таблица 5. Простые числа вида =8 ±1pk в диапазоне от 7 до 309 соответствующих величин (p–1)/2 при условии, что 2m–1 делится на p pm12p-pm12p-pm12p7 17 23 31 41 47 71 73 79 89 3 8 11 5 20 23 35 9 39 11 3 8 11 15 20 23 35 36 39 44 97 103 113 127 137 151 167 191 193 199 48 51 28 7 68 15 83 95 96 99 48 51 56 63 68 75 83 95 96 99 223 233 239 241 257 263 271 281 37 29 119 24 16 131 135 70 111 116 11
    (check this in PDF content)

  18. Start
    20204
    Prefix
    191 193 199 48 51 28 7 68 15 83 95 96 99 48 51 56 63 68 75 83 95 96 99 223 233 239 241 257 263 271 281 37 29 119 24 16 131 135 70 111 116 119 120 128 131 135 140 Двоичные КВ-коды имеют простую длину 81np k= = ±, являются циклическими, делятся на четыре класса, поскольку порождаются в кольце pR как идеалы одним из полиномов следу- ющих четырех видов: (),( 1)(), (),( 1)()qx xqx nx xnx--
    Exact
    [2, с. 464]
    Suffix
    . Здесь ()qx и ()nx-специальные полиномы степени ( 1) / 2p- из кольца (2)[ ]GFx: () ( ) i iQ qxx ∈ =-β∏; () ( )r rN nxx ∈ =-β∏; βпримитивный корень p-й степени из 1; Q-циклическая подгруппа квадратов (квадратичных вычетов по модулю p) мультипликативной группы ()GF p∗ поля ()GF p; N-множество квадратичных невычетов по модулю p.
    (check this in PDF content)