Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 68

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 68)

Зная совместные функции кратности ошибок и стираний в канале связи, можно рассчитать верхнюю границу для р„(1',г„,г,), используя (7.44). 272 Теорема 7.5. Если код имеет минимальное расстояние а' > 2г„*1, то использование алгоритма совместного исправления ошибок кратности до гн включительно и обнаружения ошибок, обеспечивает гарантированное исправление ошибок кратности не больше ~„и обнаруживает число ошибок кратности не более Ы вЂ” 1 — гн. Доказательство утверждения о гарантированном исправлении ошибок очевидно, а доказательство утверждения о гарантированном обнаружении ошибок производится аналогично доказательству теорем 7.3 и 7.4. Теорема 7.5 позволяет получить верхнюю границу для вероятности необнаруженной ошибки р (1',г„), и нижнюю границу для вероятности правильного декодирования р (Г,г„) при использовании кодов с данным алгоритмом совместного исправления и обнаружения ошибок р (1«,г„)< ~Р(п,т) (7.42) «=а-«« р (1', г„) > ~ Р(п, т).

(Подставляя (7.36) в эти неравенства, получаем соответствующие границы для частного случая канала тСК без памяти.) В некоторых случаях на выходе канала могут появляться дополнительные пометки о ненадежности принятых символов, что приводит к их стиранию. Это может происходить из-за низкого отношения сигнал-шум, соответствующего данному тактовому интервалу. Заметим, что алгоритм исправления ошибок и стираний является промемгуточным вариантом между так называемым жестким декодированием (в дискретном канале) и мягким декодированием (в полунепрерывном канале). Более подробно эта проблема обсуждается в п.7.3.10.

Полученные границы для рно(Р) и род( Р) показывают, что желательно иметь код с наибольшим возможнь1м значением минимального расстояния д. Однако интуиция подсказывает нам, что мы можем добиться увеличения д при фиксированной длине блока п, только уменьшая скорость кода Я. Хотелось бы иметь точные формулы, определяющие д как функцию Я и п или хотя бы верхние и нижние границы для этого параметра. Кроме того, для обеспечения р,„-+О, что было обещано теоремой кодирования Шеннона, придется увеличивать и длины кодовых блоков и, но при этом количество комбинаций кода М экспоненциально возрастает.

Это неизбежно вызовет большие трудности при реализации процедур кодирования и декодирования. (Действительно, при кодировании нужно запомнить М комбинаций и извлекать из памяти каждый раз новую комбинацию, соогветствуюшую поступившему сообшению, а при декодировании вычислить Мхэмминговских расстояний и находить среди них минимальное.) Поэтому мы нуждаемся в более конструктивном (регулярном) задании кода, чем его описание таблицей кодовых комбинаций. Эту проблему удается решить при переходе к специальному классу так называемых линейных кодов, который описан в следующем разделе.

Однако, прежде чем перейти к его рассмотрению, сделаем еше одно замечание. Сравнение границ 17.37) и (7.40) показывает, что в любых каналах связи и для любых кодов р„,(р) я р,х(р), причем это неравенство справедливо не только для границ, но и для точных значений соответствуюших вероятностей ошибок. Однако этот факт еше не означает, что всегда целесообразно использовать обнаружение ошибок, а не их исправление. Действительно, после обнаружения ошибок в блоке он оказывается стертым, а следовательно, не может быть выдан получателю.

Обычно его доставка осушествляется при помощи повторной передачи, что требует затрат дополнительного времени. К вопросам получения более точных оценок для р„,(Р) и л,а(Р), а также к сравнению систем с обнаружением и исправлением ошибок мы еще вернемся в следующем разделе. 7.3.3. ЛИНЕЙНЫЕ ДВОИЧНЫЕ КОДЫ ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ ОШИБОК Здесь мы ограничимся описанием только двоичных кодов, поскольку это не потребует пока использования в качестве математического аппарата такого достаточно сложного раздела современной алгебры, как теория конечных полей.

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

(Последнее свойство можно назвать замкнутостью относительно поразрядного сложения по гпод2.) Пример. Множество последовательностей длины 5: 00000, 11101, 01010, 10111, образует линейный код, что проверяется непосредственно. Поразрядная сумма по шоб2 2-й и 3-ей комбинации дает 4-ю комбинацию, сумма 3 и 4 дает 2-ю, а сумма 2 и 4 дает 3-ю комбинацию.

273 Из алгебры известно, что всякое к-мерное линейное подпространство и- мерного пространства, состоящего из конечного числа (2") элементов, содержит базис, т.е. совокупность /г линейно независимых элементов, из которых путем поразрядного суммирования по гпой 2 можно образовать любые элементы данного подпространства, т.е. в данном случае комбинации линейного кода. Доказывается, что все базисы такого подпространства состоят из одного и того же числа элементов /с, которое и определяет размерность подпространства.

Общее число комбинаций линейного кода М= 2", поскольку таким будет общее число возможных поразрядных сумм из й элементов базиса, причем среди них не может найтись двух одинаковых сумм ввиду линейной независимости элементов базиса. Совокупность элементов базиса, записанная в виде линейно независимых строк, образует /с х и двоичную матрицу 6, которая называется лорождающей матрицей кода: Яп Ки " Уы 821 е22 ' ' ' е за Ки Ки ...

Яь (7.45) Множество всех кодовых слов, порожденных 6, может быть представлено как х=ЬС, (7.4б) где х — вектор-строка кодовой комбинации размерности и; Ь вЂ” вектор-строка информационных символов длины /с. В (7.46) выполняется умножение гектора на матрицу, а все действия осуществлены по глод 2. Очевидно, что в качестве вектора Ь можно использовать /с последовательных элементов сообщения, выдаваемых двоичным источником. Переход от избьггочньгх кодов общего вида к линейным кодам практически решает проблему сложности кодирования. Действительно, вместо запоминания М = 2е комбинаций длины и, т.е. п2к бит в общем случае, нам достаточно запомнить лишь порождающую матрицу, состоящую из пй =п)од, М бит.

Сама же процедура кодирования потребует выполнения не более чем 2/сп элементарных операций. Переход к линейным кодам значительно упрощает анализ (а следовательно, и задание) их обнаруживающей и исправляющей способности. Действительно, пусть ~' — линейный двоичный код, содержащий комбинации(х„х„..., х...), где х, — нулевая комбинация. Тогда по свойству замкнугости линейного кода для любой пары ненулевых комбинаций (х„х,.) расстояние Хэмминга между ними р(х„х ) =~к, Юх,~ будет равно весу Хэмминга ~х~~ некоторой третьей комбинации, принадлежащей этому же коду, кроме нулевой.

Поэтому получаем важный вывод, что для любого линейного кода минимальное кодовое Очевидно, что линейный код удовлетворяет определению линейного подпространства Г для пространства г'" всех. двоичных последовательностей длины л. (Или иначе — зто подгруппа для группы всех двоичных л-последовательностей относительно групповой операции поразрядного сложения по пюд 2.

Поэтому двоичные линейные коды называются также и групповыми.) О ." О ~ р„р„" р,„, Р!! Р!! " ' Рь-! ОО" 1~р„р "р, =(1,'Р), (7.48) где (р!7) — некоторые двоичные элементы; 1к — единичная 1с х 1с матрица (с единицами на главной диагонали и нулями в других местах); Р— матрица й х (п — к), состоящая,' из двоичных элементов; (А,'В) означает последовательную запись матриц А и В. Используя представление (7.46) с матрицей 6 в виде (7.48), получаем х=(Ь,'с), (7.49) где с=ЬР. По правилу матричного умножения получаем для с = (с!, ..., с„,~) с, =~Ь!р„,(шо!12), у'=1, 2, ..., и-й (7.50) >=! Цз выражений (7.49) и (7.50) следует, что процедура кодирования линейным кодом, определенным канонической матрицей вида (7.48), сводится к формированию кодового слова, состоящего из двух последовательных подслов, причем первое подслово совпадает с информационной последовательностью длины 1с, выданной источником сообщений, а второе образовано путем линейной комбинации строк матрицы Р.

Определение 12. Линейные коды, слова которых представимы в виде (7.49), называются систематическими. Мы фактически показали ранее, что всякий линейный код эквивалентен некоторому систематическому в смысле сохранения списка весов, а следовательно, и расстояний Хэмминга. Первые й символов кодовых слов, совпадающих с символами источника, называются информационными, а последние и — й символов — проверочными. Скорость кода Я, определенная ранее как 1о82М/и, для'линейного кода будет равна 1/и, т.е.

для систематического — отношению числа информационных символов /с к длине кодового блока и. Систематические коды с длиной блока и и с числом информационных символов 1с будем кратко называть (и, й)-кодами. Иногда такой код обозначают тремя параметрами (и, 1с, а), где а' — минимальное кодовое расстояние. 275 расстояние а' равно минимальному весу Хэмминга, которым обладает слово кода, за исключением нулевого, т.е. ш1в )х,~.

(7.47) ПР 1!ФО Таким образом, для всех линейных кодов изучение списка хзмминговских расстояний между парами комбинаций эквивалентно изучению списка хзмминговских весов, что, очевидно, значительно проще. Для любого линейного кода, заданного некоторой порождающей матрицей 6, очевидно также следующее свойство: любые перестановки столбцов и элементарные преобразования строк, заключающиеся в их перестановках или в суммировании друг с другом, не изменяют список весов данного кода. С другой стороны, можно показать, что при- помощи таких 'преобразований любая (1с х и) двоичная матрица 6 с линейно-независимыми строками может быть приведена к каноническому виду В линейной алгебре существует понятие ортогонального пространства или нуль-пространства для заданного линейного пространства )г. Это по определению такое множество 1 векторов х длины п, для которых (х, х) = О при любом хн )г, где (, ) означает скалярное произведение соответствующих векторов.

Характеристики

Список файлов книги