Главная страница  Дискретный канал связи 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [ 47 ] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

7"

Рис 5.2. Параметры некоторых двоичных квадратично-вычетных кодов. Знаком сноски ) огмечены параметры лучших из известных кодов с данными пик.

5.9. КВАДРАТИЧНО-ВЫЧЕТНЫЕ КОДЫ

Класс квадратично-вычетных кодов представляет собой частный подкласс циклических кодов, широко изучаемых потому, что в этом подклассе было найдено несколько хороших кодов и поэтому имеется надежда найти в нем другие хорошие коды. На рис. 5.2 приведены параметры некоторых квадратично-вычетных кодов с известным минимальным расстоянием. Наиболее известным кодом класса является код Голея. Большинство кодов из этого списка обладают большим минимальным расстоянием, чем любой другой известный код с теми же параметрами пик, что и привлекает внимание исследователей к квадратично-вычетным кодам. Однай) не все эти коды хороши, и не известно, существуют ли хорошие квадратично-вычетпые коды большой длины. Поэтому неясно, насколько квадратично-вычетпые коды полезны в практических приложениях.

Мы рассмотрим только двоичные квадратично-вычетпые коды. Название этих кодов отражает их связь с теми элементами простого поля, которые имеют в этом поле квадратный корень. Как показывает теорема 4.6.15, в полях характеристики 2 каждый элемент имеет единственный квадратный корень. В простом поле GF (р), р Ф 2, квадратный корень имеет точно половина непулевых элементов, а именно те (р - 1)/2 элементов, которые равны четным степеням примитивного элемента. Эти элементы принято называть квадратичными вычетами (так как они равны квадратам своих квадратных корней по модулю р). Подчеркнем, что.



хотя мы рассматриваем коды над GF (2), квадратичные вычеты, входящие в их определение, лежат в поле GF (р), р Ф1. Не следует также путать поле локаторов GF (2") с полем GF (р), которое не является подполем поля локаторов.

Определение 5.9.1. Квадраттно-вычетным кодом называется циклический код над GF (2), длина которого равна простому числу р, делящему 2" - 1 при некотором т, а корнями порождающего многочлена являются все элементы aJ из GF (2"), такие, что / является квадратичным вычетом поля GF (р).

Как следует из этого определения, g{x)= П (х-а/),

где произведение вычисляется по множеству QR всех квадратичных вычетов по модулю р, причем предполагается, что g (х) представляет собой многочлен над GF (2). Если такой многочлен не является многочленом над GF (2), то для этого значения р кода не существует.

Из определения многочлена g (х) следует также, что

хР-1 ={х- l)g{x) g{x),

где многочлен g (х) определяется тем, что все (р - 1)/2 его корней суть элементы вида aJ из GF (2") для всех ненулевых квадратичных невычетов / из GF (р). Многочлен g (х) является взаимным к g{x) и порождает эквивалентный код. Многочлен

g(x) = (x-l) П (x-aJ)

порождает другой код. У этого многочлена корней на один больше, чем у многочлена g (х), и, следовательно, порождаемый им код является подкодом квадратично-вычетного кода. Этот подкод тоже называется квадратично-вычетным, но он не так интересен, как исходный код, и в дальнейшем мы не будем его рассматривать.

Квадратично-вычетный код над полем GF (2) существует только тогда, когда все коэффициенты многочлена g (х) лежат в этом поле. Вскоре мы увидим, что квадратично-вычетный код существует только тогда, когда р является простым числом вида р= ~ 8k ±1. Но для описания одного такого кода надо знать его минимальное расстояние. Обычно задача вычисления минимального расстояния квадратично-вычетного кода является достаточно сложной, и каждый из кодов требует индивидуального подхода. Один из примеров мы встретили в предыдущем параграфе при исследовании (23, 12)-кода Голея. Для всех перечисленных на рис. 5.2 квадратично-вычетных кодов минимальные расстояния



известны. Имеется много других квадратично-вычетных кодов, но их минимальные расстояния не известны.

Мы укажем одну границу для минимального расстояния произвольного квадратично-вычетного кода. Граница не очень хороша, но легко доказывается.

Теорема 5.9.2 (граница квадратного корня). Минимальное расстояние произвольного квадратично-вычетного кода длины р удовлетворяет неравенству d* т/р.

Доказательство. Зафиксируем произвольный ненулевой элемент S поля GF (р), не являющийся квадратичным вычетом. Каждый элемент поля GF (р) можно записать в виде js для некоторого / (так как GF(р) - поле). Если число / является квадратичным вычетом, то, очевидно, js будет квадратичным невычетом, если же / - квадратичный невычет, то js является квадратичным вычетом.

Пусть с (х) представляет собой кодовый многочлен минимального веса d*. Тогда с (х) = а (х) g (х) для некоторого а (х). Определим с (х) с {х) (mod хР ~ 1). При этом с (х) = а {х) X Xg{x) (mod х" - 1), и вес многочлена с (х) равен самое большее d*. Но если / - квадратичный вычет, то g (а) Ф О, а если / - квадратичный невычет, то g (aJ) = 0. Таким образом, g (х) = = g (х). Следовательно, с (х) с (х) (mod хр - 1) делится как на g{x), так и на g{x). Этот многочлен кратен многочлену хр~ + + хР- + ... -j- x + 1, а степень его равна самое большее р - 1, и поэтому

с (х) с (х) = хР- -]- xP-2 ------Ь а; -f 1 (mod хр - I).

В правой части стоит многочлен веса р, а так как вес многочлена с (х) равен d*, то возможный вес многочлена в левой части не превосходит (d*). Итак, d* ур, что и требовалось доказать.□

Теперь определим, когда коэффициенты определенного выше многочлена g (х) принимают только двоичные значения. Если 2 является квадратичным вычетом, то все степени двойки также являются квадратичными вычетами. Далее, если / - другой квадратичный вычет, то все числа 2/, 4/, 8/, ... также являются квадратичными вычетами. Следовательно, вместе с а все его сопряженные относительно поля GF (2) элементы являются корнями порождающего многочлена. В этом случае многочлены g-(x) и g {х) представляют собой многочлены над GF (2). Таким образом, квадратично-вычетпые коды существуют для всех таких р, для которых 2 является квадратичным вычетом в поле GF (р). Мы увидим, что числа р, для которых 2 является квадратичным вычетом в поле GF (р), исчерпываются простыми числами вида р = 8k ±1 для произвольного целого k. Это утверждение яв-




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [ 47 ] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

0.03