Главная страница  Алгебраическая теория кодирования 

[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]

Задачи

15.1. Суженный двоичный КВ-код с блоковой длиной 31 можно задат] порождающим многочленом

(a) Выписать 7 кодовых слов веса 8 для 1-удлиненного двоичного КВ-код с длиной 32, содержащего единицы в позициях {оо. О, 1}.

Ответ: {оо, О, 1} U {26, 13, 29, 9, 16} или {26,23,6,7,5}, ил {26, 17, 30, 20, 25} или {26, 21, 27, 2, 18}, или {21, 23, 17, 9, 14} ш {27, 17, 29, 7, 19}, или {12, 29, 21, 5, 25}.

(b) Сколько из 21" смежных классов 1-удлиненного двоичного КВ-код длины 32 содержат точно по одному лидеру веса 4? Сколько из них имен 2, 3, 4, 5, . . . слов веса 4?

(c) Сколько из 2" смежных классов РМ-кода второго порядка длины 3ij содержат 1, 2, 3, ... слов веса 4?

15.2. Используя результаты задачи 15.1а, показать, что каждая нереста! новка, сохраняющая 1-удлиненный двоичный КВ-код длины 32, содержите в проективной унимодулярной группе.

Указание. Позиции 1, 2, . . ., 30 можно разбить на два подмножества та» что если существует не менее трех кодовых слов веса 8 с единицами в позиция {оо, Q,x,y}, то хку относятся к различным множествам. Следовательно, одна подстановка, сохраняющая код, не может фиксировать позиции х и и изменять вычеты и невычеты. Более того, любая подстановка, сохраняю! код и фиксирующая каждую из позиций {оо. О, 1}, должна фиксировать поз ции 26, 12, 28, 17, 7, 19, 14, 9, . . .; иными словами, она должна быть тождв ственной.

15.3. (Ассмус, Мэттсон [1966]). Группа всех подстановок на множест; из 24 символов, сохраняющая 1-удлиненный двоичный КВ-код {1-удлиненн: код Голея), называется группой Матье.

(a) Показать, что группа Матье 5-транзитивна.

(b) Показать, что порядок группы Матье равен 16x15x14x12x8-X 23x11x3.

Указание. Пусть А тп В - подмножества позиций, соответствующих нул; и единицам некоторого фиксированного кодового слова веса 8. Тогда \ А = 1С \ В 1 = 8. Пусть а - фиксированный элемент из 4, Ъ - фиксированный эл мент из В. Пусть S - подгруппа группы Матье, относительно которой А и инвариантны, - подгруппа группы , оставляющая на месте каждый эл-мент 5, а - подгруппа группы фиксирующая а. Пусть сд, J

и д, <Жд, 3д - подгруппы подстановок соответственно множеств А и индуцированные группами &G, Ъ WG - единичная подгруппа).

Каждое из 2*2 кодовых слов кода Голея может быть спроектировано на и В. Вес кодового слова равен сумме весов его проекций А ш В. Вес проекц: любого кодового слова на А либо равен О, либо 4. Множество 21* различи проекций кодовых слов 1-удлиненного кода Голея на А образует линейный К с длиной 16 и минимальным весом 4. Так как этот код эквивалентен 1-удлиненп му коду Хэмминга, то множество А можно представить в виде 4-мерного векто; ного пространства над GF (2), нулевой вектор которого соответствует точке Множество 2 различных проекций кодовых слов 1-удлиненного кода Голея на должно быть эквивалентно коду длины 18 с единственной проверкой на че ность. Если проекция кодового слова на В есть нуль-вектор, то его проек: на Л - кодовое слово РМ-кода первого порядка с длиной 16.

Согласно теореме 15.35, и &еа - подгруппы группы всех обрати: аффинных преобразований поля GF (2*) над GF (2); J ~ нодгруппа груп:

X всех обратимых линейных преобразований поля GF (2*) над GF (2). Порядок Л равен 16 X 15x14x12 X 8; порядок X равен 15 х 14 X 12 х 8 = 81/2. Ь11авнительно просто показать, что &е - группа аддитивных сдвигов на GF (2*) 11(1 рядка 16. Труднее доказать, что J = и С/в = - знакопеременная группа над множеством из 8 символов. (Эти факты можно проверить с помощью перебора всех 35 кодовых слов 1-удлиненного кода Голея веса 8, содержаш;их I! позициях а и Ь единицы.) Отсюда следует, что порядок Л равен порядку g. Так как код Голея совершенен, то для любых пяти позиций 1-удлиненный код содержит слово веса 8, содержащее единицы в этих позициях. Всего он содержит 2/1 X 23 X 22 X 21 X 20 X 20/8 Х7х6х5х4 = 23х11х3 кодовых слов веса 8. Нетрудно показать, что эти слова веса 8 переводятся друг в друга некоторой подстановкой из унимодулярной проективной группы . Согласно теореме 15.26, - подгруппа группы Матье.

Чтобы найти подстановку я, осуществляющую отображение х yi, хч ->• г/2, . . ., аб -> Уь, надо сначала определить множества X = {х, хг, ... . 5, х, х, xg} и Y = {у1, г/2, . . ., у}, соответствующие номерам еди-цпчпых позиций кодовых слов веса 8. После этого полагаем п = щпп, где

лЗ, Х-В, пз, Y->В, Я2 - подходящая подстановка из Ъ-

15.4. Определить порядок группы всех подстановок, оставляющих инвариантным 1-удлйненный двоичный КВ-код длины 18.

15.5. Используя рис. 15.9, указать, какие из следующих ошибок могут быть исправлены с помощью декодера рис. 15.8.

(a) {О, 1, 2, 3};

(b) {О,. 1, 2, 3, 4};

(c) {О, 1, 2, 3, 4, 5};

(d) {О, 1, 2, 3, 4, 5, 6};

(e) {О, 1, 2, 3, 4, 30};

(f) {О, 1, 3, 27}.

Ответ. Да; да; да; нет; нет; нет.

15.6. Предположим, что декодер рис. 15.8 может быть улучшен включением па первом уровне девяти пороговых элементов с шестью входами, осуществляющих соответственно оценку девяти подпространств, ортогональных на нулевой позиции (см. рис. 15.9). Величина Ef, вычисляется затем на пороговом элементе с девятью входами и Г = 5. Прокомментируйте такую возможность.

15.7. Построить совершенные простые разностные множества но mod 7, 13, 21, 31, 57, 73. Какие из этих множеств могут быть использованы для построения разностных кодов над GF (2)?

15.8. (Мак-Вильямс, Манн [1968] и Смит [1967]). В условиях теоремы 15.599

показать, что т (р, т, т - 2, s) =

If,*



Глава 16 Нумераторы весов

16.1. Соотношения между нумераторами весов и вероятность» отказа от декодирования

В некоторых случаях ошибки декодирования играют очень серьез ную роль, в то время как отказ от декодирования является всего лиг досадной неприятностью. В таких случаях целесообразно использс вать очень неполный алгоритм декодирования, который декодируе принятое слово только тогда, когда оно является кодовым. Это алгоритм декодирует правильно тогда и только тогда,- когда векто ошибки - нулевой, декодирует неправильно тогда и только тогда когда этот вектор совпадает с кодовым словом, и приводит к отказу от декодирования в остальных случаях. Для двоичного симметрич: ного канала и кода длины п вероятность того, что вектор шума совпа дает с некоторым кодовым словом веса i, равна Р (1 - Р)"-*, гд Р - вероятность искажения одного символа. Если код содерж! Ло= 1 слов весаО, 1 слов веса 1, Л2 слов веса 2, . . ., слов веса ii то вероятность того, что вектор шума совпадет с кодовым словом!

равна 2 iP (1 - -Р)""*. Удобно ввести в рассмотрение нумераА

тор весов кода (z) = 2 t- терминах нумератора весов вероят-<

НОСТЬ того, что ошибка в канале равна кодовому слову, задаете* формулой (1 - Р) А (Р/(1 - Р)). Вероятность правильного деке дирования равна (1 - Р)"; вероятность ошибки декодирования рав на (1 - Р)" [А {P/{i - Р)) - 1]. Вероятность отказа от декодирс вания равна 1 - (1 - Р)" А (Р/(1 - Р)). Таким образом, прв использовании неполного алгоритма декодирования, когда полу- ченное слово декодируется лишь тогда, когда оно кодовое, вероят-i ности правильного и неправильного декодирования и отказа от деко-; дирования легко выражаются через нумератор весов кода.

Нумератор весов кода можно также использовать для вычисления! вероятностей ошибки и отказа от декодирования таких алгоритмов декодирования, которые всегда исправляют до t ошибок включи-! тельно, и ничего более. В этом случае вероятность правильного деко-*

дирования равна 2 ( ) "~ )"~ ~" вероятности того, что

вес вектора шума в канале не превосходит t. Вероятность отказ

от декодирования равна вероятности того, что вектор шума принадлежит смежному классу веса >t вероятность ошибки декодирования равна вероятности того, что вектор шума не является лидером смежного класса веса Пусть \¥%~> - число слов веса к,

находяш;ихся на расстоянии / от некоторого фиксированного слова с весом i и длиной п. Тогда найдется 2гИ!й"~ слов веса к,

находяш,ихся на расстоянии / от кодовых слов. Если кодовое расстояние >2i -1-1, то ни одно слово не может находиться на расстоянии от двух различных кодовых слов, так что число слов веса /с, принадлежащих смежному классу веса задается формулой .2 .S г WJft"" Вероятность декодирования (правильного, или неправильного) соответственно равна

(16.11) Положим

S S 2Л;П<-у-*>Р(1 Р)«-\

fe=0 3=0 i=0

Wf- (у) = 2 wh-V и wt: ix, г/) == 2 S wtrxy.

" i ft

Так как Tjs"" - аддитивные величины на п координатах кода то производящая функция W [х, у) мультипликативна на этих координатах и П*(П*(W""У* = (а: +г/)(М-а:г/)"-*.

Тогда

п п п

(16.12)

2 2 2 AiWf:rp{i-pr=

ft=0 i=0 i=0

(16-13) 2 2 2 AiWf:rp (1 - p)"-" x =

ft=o i=o 1=0

= Ai{x-xP-h Py (1 -P-i- хРГ = (1 - P + xPT A ( 1 if/J ) •

Пусть

(16.14) /<•> () (1 p + xPT A ( IZffp )

) Здесь и в дальнейшем автор называет весом смежного класса минимальный вес его элементов.- Прим. перев.



Согласно (16.12) и (16.13), /С) (х) - многочлен от х степени Разлагая его но формуле Тейлора, получим, что

(16.15)

Используя (16.11) - (16.15), приходим к следующему выражеш для вероятности отказа от декодирования:

п t п

(16.16) 1-222 AiWji-rp (1 - р)"-" =1-2

ft=0 3=0 1=0

/"• (0)

Формула (16.16), полученная Мак-Вильямс [1963], определяв вероятность отказа от декодирования в случае, когда число t мены половины минимального расстояния кода. Случай = О соотве ствует очень неполному алгоритму декодирования, который деке дирует лишь тогда; когда полученное слово является кодовь

К сожалению, нумератор весов не дает полной информаци которую нам бы хотелось иметь о коде. Например, он ничего говорит о вероятности ошибки декодирования при использова! полного алгоритма декодирования, преобразующего каждое пол ченное слово в лидер смежного класса. В частности, суженный дво1 ный КВ-код с длиной 31 и 2-укороченный РМ-код второго поря с длиной 31 имеют один и тот же нумератор весов, хотя, как показ вает задача 15.1, распределения весов лидеров смежных классе у этих кодов различны.

Тем не менее нумератор весов кода дает о нем значителы информацию, включающую минимальный вес, число кодовых сля каждого веса, вероятности ошибки и отказа от декодирования случая, когда декодируются ошибки веса if, но никакие друг Поэтому исследованию нумераторов весов посвящено большое кол чество работ. В этой главе рассмотрены некоторые основные резул!) таты, полученные в этом направлении.

Все известные результаты о нумераторах весов относятся к ну» раторам весов Хэмминга, причем большинство из них касаетс двоичных кодов. За исключением нескольких тривиальных tooj типа теоремы 13.52, решительно ничего не известно и о нумератора весов Ли.

Нумераторы весов Ли некоторых двоичных кодов приводе! в табл. 16.1; формулы для нумераторов весов некоторых классЙ двоичных кодов с малыми и большими скоростями собре в табл. 16.4 и 16.5 1).

1) Таблицы 16.1-16.6 сгруппированы в конце главы.

16.2. Уравнения Мак-Вильямс - Плесе для нумераторов весов дуальных кодов

Нумераторы весов кодов с малым числом кодовых слов и кодов с малым числом классов эквивалентности относительно некоторой известной группы подстановок могут быть найдены путем полного перебора классов эквивалентности. Этот подход оказывается весьма эффективным для некоторых классов кодов с малой блоковой длиной или малой скоростью. В частности, нумераторы весов для большинства кодов со скоростью <;1/2, приведенные в табл. 16.1, были впервые получены этим способом путем использования циклической группы подстановок и группы подстановок вида Xi Zf (следствие 5.82).

К сожалению, число кодовых слов в большинстве кодов с большой скоростью и умеренной или большой блоковой длиной на много порядков превосходит число всех подстановок, относительно которых код инвариантен. Поэтому нумераторы весов этих кодов не удается определить даже с использованием больших быстродействующих вычислительных машин. Однако, даже если число д" велико, число g{i-R)n может быть относительно мало. Таким образом, может оказаться, что нумератор весов дуального кода, кодовые слова которого образуют проверки исходного кода, вычисляется сравнительно просто. Например, если скорость исходного кода >1/2, то вообще легче вычислить нумератор весов дуального кода, так как он инвариантен относительно той же группы подстановок, что и исходный код. В частности, код, дуальный к циклическому коду с порождающим многочленом g (х), есть циклический код с порождающим многочленом А (х), где h (х) = (х" - i)/g {х) иК (х) - многочлен, взаимный к h (х). Аналогично, если g (х) не делится на а; - 1, то код, дуальный к 1-удлиненному циклическому коду с порождающим многочленом g (х), есть 1-удлиненный циклический код, порожденный многочленом, взаимным к многочлену (х" - l)/g (х) {х - 1).

Если нумератор весов дуального кода известен, то нумератор весов исходного кода может быть определен с помощью замечательной формулы, полученной Мак-Вильямс [1963].

16.21. Теорема (Мак-Вильямс). Пусть Л - линейный код размерности к над GF (q) с нумератором весов Хэмминга А (z), и пусть - его дуальный код с нумератором весов Хэмминга В (z). Тогда

(z) = ,(,- + p.)"5(:p),

где р = (q - i)/q.




[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]

0.0159