Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 69
Текст из файла (страница 69)
(В нашем случае все операции производятся по гпод2). Доказывается, что это множество всегда является линейным пространством, причем если код 1'имеет размерность )с, то код 1" будет иметь размерность п — 7с, т.е. содержать 2".' комбинаций. Код г, совпадающий с ортогональным пространством, называется дуальным к коду г'. Он, очевидно, также может быть задан своей порождающей матрицей 6'=Н размерностью (и — )с) х и. Тогда комбинации исходного кода Р'могут быть определены как решения векторно-матричного уравнения Г = (гс хнт = 0), (7.51) где Т означает символ транспонирования матрицы Н, т.е. взаимную замену строк и столбцов. Матрица Н, которая является порождающей для кода 1", называется проверочной матрицей для исходного кода, )г.
Матрица Н так же, как и 6, может быть представлена в канонической форме, причем можно показать 1211, что Н=(1„„Р ), (7.52) где Р— та же самая матрица, что и в представлении (7.48). В теории линейных кодов найдены границы для минимального расстояния а. Теорема 7.7. Верхняя граница Плоткина. Если длина кодового блока на 2д — 1, то число проверочных символов г = н — к, необходимых для того, чтобы минимальное расстояние линейного кода достигало значения И, равно самое меньшее 2Ы вЂ” 2 — 1оя И . (Доказательство можно найти в 12Ц.) Как следствие, 2И вЂ” 2 — 10я! И Теорема 7.8. Нижняя граница Варшамова-Гильберта.
Существует (н, lс)-код с минимальным расстоянием ко меныией мере а(, которое удовлетворяет следующему неравенству: л-2 ~" С„', >2а-ь. (7.53) ! о Доказательство. Пусть Н вЂ” проверочная матрица кода К Тогда из (7.51) следует, что для любого слова х еГ хэмминговского веса ~х~ = !ь существует такой набор из !ь столбцов матрицы Н, элементы которой при покоординатном сложении по щод 2 дадут нулевой столбец. Верно и обратное, а именно, что если для некоторой проверочной матрицы Н любые д — 1 и меньшее число столбцов всегда является линейно независимым (т.е.
в сумме не дают нулевых столбцов), то соответствующий ей линейный код имеет минимальное расстояние, самое меньшее И. Построим проверочную матрицу, обладающую таким свойством. В качестве ее первого столбца возьмем любой двоичный набор длины г = н — к. Затем возьмем также любой двоичный набор длины г, не совпадающий с первым, далее — третий набор, не равный нх сумме и так далее до столбца длиной г, который не является суммой Ы вЂ” 2 и меньшего числа предыдущих столбцов. Очевидно, что очередной столбец может быть присоединен к матрице в том случае, если совокупность всех сумм из д — 2 нли меньшего числа предыдущих столбцов матрицы не исчерпывает всех наборов длины г.
В наихудшем случае все такие суммы будут различными. Поскольку общее число таких сумм при выборе из общего числа У вЂ” 1 столбе-! цов равно ~С,',, а число различных вариантов двоичных ненулевых столбцов длины г равно ! 1 2" — 1, то достаточное условие существования кода с длиной блока 7', имеющего самое большее г проверочных символов, принимает вид 276 0,8 0,6 0,4 0,2 0,5 оЯ22 0,25 Рис.7.3. Границы Плоткина и Вар2ламова-Гильберта И вЂ” 2 ~~2 С', в2" — 1.
(7. 54) Пусть теперь и — наибольшее значение /, для которого справедливо (7.54). Прибавив к обеим частям неравенства (7.54) С~2, =1, получаем (7.53). Это завершает доказательство тео- ремы. Если длина блока л достаточно велика, то неравенство (7.54) можно преобразовать к следующему виду: (7.55) г < ил — или 21 > 1 — Ь— где 12(х) = -(х 1ок2 х + (1- х) 1ок2 (1 — х)) . На рис.
7.3 построены кривые, соответствующие верхней границе Плоткина и нижней границе Варшамова-Гильберта, как функции скорости кода К=1с!и от аргумента Ы/2и. В отличие от границы Плоткина граница Варшамова-Гнльберта означает, что всегда существуют коды, которые имеют скорость, лежащую на соответствующей кривой, а возможно, и выше этой кривой. Заметим, что верхняя граница строилась по соотношению, определяемому теоремой 7.7 при достаточно больших Ы, когда вторым н третьим слагаемым в выражении для оценки числа проверочных символов можно было пренебречь. Нижняя граница была получена из соотношения (7.55), где также в качестве аргумента функции использовалось й(п, что верно для больших л.
Параметры наилучших реализуемых кодов могут лежать только в заштрихованной области между верхней и нижней границами. (В действительности получен и целый ряд других границ, которые уточняют значение 22, т.е. сужают данную область при некоторых значениях аргументов.) Заметим, что хотя теорема 7.7 и описывает, казалось бы, конструктивный метод построения кода с заданной величиной а1, однако его практическое использование оказывается невозможным, поскольку при больших значениях и и г требуется перебор огромного количества возможных вариантов столбцов проверочной матрицы Н. Нижняя граница Варшамова-Гильберта позволяет оценить аснмптотическне возможности линейных двоичных кодов по исправлению ошибок гарантированной кратности. Действительно, среднее число ошибок в блоке длины и для 2СК без памяти будет равно ир, где р— вероятность ошибки символа в данном канале.
Для того чтобы после использования кода 1ли р„= О, очевидно, необходимо, чтобы код имел 22 не меньше, чем 2лр, и тогда при л-М~ 277 больших д получаем д/лпгр, а неравенство (7.55) можно переписать в следующей форме: л ~1-й(гр) . Интересно сопоставить нижнюю границу Варшамова-Гилъберта йаг =1-л(гр) с верхней границей для скорости кода, установленной теоремой Шеннона для 2СК: С(р) =1 — Ь(р). Ясно, что при р = 0 эти границы совпадают. При р ~ 0;25 нижняя граница Варшамова-Гилъберта йаг — — О, в то время как верхняя граница Шеннона С(р) > О (см. рис.
6.3). В области р ~ 10 2 граница Шеннона существенно выше, чем граница ВаршамоваГилъберта. Эта разница объясняется тем, что нижняя граница Варшамова-Гнлъберта соответствует алгоритму исправления ошибок только гарантированной кратности, в то время как граница Шеннона определена при оптимальном, сколь угодно сложном декодировании. Однако, хотя скорость кода й, получаемая из границы Варшамова-Гилъберта, меньше, чем значение, следующее из теоремы оптимального кодирования,.она является гарантированной и реально достижимой. Исследование линейных кодов позволяет также упростить алгоритм декодирования по минимуму расстояния Хзмминга, расчет р,д для этого алгоритма и ближе подойти к проблеме оптимизации выбора кодов.
Для этого рассмотрим конструкцию, которая называется стандартным раслоложеиием по заданному коду и В качестве первой строки такого расположения (таблицы) выберем кодовые комбинации х, самого кода и Далее возъмем произвольное двоичное слово я1 длины и, которое не принадлежит коду Р; и образуем М = 2к слов следующей строки по правилу у„=х,9я,, ~= 1, 2, ..., 2, гпе 9 означает поразрядное суммирование по пюд 2. Затем возьмем двоичное слово яг длины л так, чтобы я, ~ х„й, ~ уи, ~ = 1, 2, ..., 2", и построим третью строку у„=х,9й„и так далее вплоть до исчерпания всех двоичных векторов длины л, не входящих в предыдущие строки. Легко проверить, что в каждой строке матрицы будут содержаться лишь различные слова и в строках не будет содержать повторения слов.
Данная таблица будет содержать все 2" двоичных слов длины т Поэтому число строк таблицы всегда в точности — = 2, а число столбцов 2 . Можно убедиться также в справедг" ъ 2" ливости следующих свойств для данной расстановки: поразрядная сумма по пкх1 2 любой пары слов, находящихся в одной строке, всегда дает кодовое слово, а лежащих в разных строках — слово в некоторой строке, отличной от взятых, но не принадлежащих первой строке (т.е.
коду). Замена слова яь формирующего 1-ю строку, на какое-либо слово в этой же строке не изменяет полной совокупности слов, образующих данную строку, а производит лишь их перестановку в строке. В алгебре такие строки, полученные по некоторой группе (коду), называются смежиыми классами, а слова яг..я1,, называются образующими нли лидерами смежных классов. После построения стандартного расположения по некоторому коду Р'определим способ декодирования, соответствующий этой таблице, следующим образом: если принято некоторое слово у, то декодируется кодовое слово хъ находящееся в том же столбце, что и у.
Тогда вероятность перехода Р(у)х,) для любого двоичного канала связи с аддитивным шумом будет равна вероятности появления образца ошибки е, совпадающего с лидером смежного класса я, к которому принадлежит у. Поэтому для того, чтобы сделать декодирование оптимальным по критерию максимума правдоподобия, достаточно выбрать в качестве лидеров образцы ошибок, имеющие максимальные вероятности в каждом смежном классе. (Если несколько слов имеют в некотором смежном классе одинаковые вероятности, то можно в качестве лидера выбрать любое из них.) Определение 13. Синдромом по коду балля любого принятого на выходе канала связи двоичного слова у длины и будем называть двоичный вектор-строку длины п — )с: я=уН „ (7.56) где Н вЂ” т1роверочная матрица кода К Легко убедиться, что для всех слов, принадлежащих одному и тому же смежному классу кода К синдромы оказываются одинаковыми, а для 278 Регистр сдвига из и ячеек Регистр сдвига нз Ь ячеек Рис.7.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
