Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 110

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 104 105 106 107 108 109 < 110 > 111 112 113 114 115 116 .. 355 >> Следующая


Следствие. При всех положительных целых L и N, L < N существуют систематические (N, 1)-коды с проверкой на четность, для которых при использовании их в ДСК

Ре, тп ехр [—NET (R)] для всех m, 1 ^ т ^ 2L, (6.2.5)

где R = (L In 2)/N, а ЕТ (R) определяется равенствами (5.6.41) и и (5.6.45). ___________

*> Для этого необходимо, чтобы строки матрицы G были линейно независимы. В коде с линейно зависимыми строками каждому кодовому слову соответствуют по меньшей мере два сообщения, и декодер максимального правдоподобия всегда будет принимать решение в условиях неопределенности. Так как все подобного рода события теорема 5.6.1 классифицирует как ошибки, то коды, для которых выполняется неравенство Ре ^ ехр [—NEr (R)], должны существовать среди кодов, для которых строки матрицы G линейно независимы.

223
Рассмотрим теперь использование кодов с проверкой на четность в произвольных дискретных каналах без памяти. В качестве первого примера рассмотрим случай, когда входной алфавит канала состоит из трех букв, и допустим, что нужно кодировать двоичные входные последовательности длины L кодовыми словами длины N. Скорость передачи в данном случае равна R = (L In 2)/N. Предположим, что для данного канала и данной скорости передачи значения входных вероятностей, максимизирующие величину Ет (R) в (5.6.16), равны Q (0) = %, Q (1) = 3/8, Q (2) — 2/g. Первой нашей задачей будет

Рис. 6.2,1. Отображение двоичных последовательностей во входные буквы канала.

построение смежного кода с длиной блока 3 N путем использования правила кодирования (6.2.1), где G — двоичная матрица размера L на 3N, a v — двоичная последовательность длины 3N. Можно рассматривать двоичные кодовые слова как последовательности N троек двоичных символов. Затем эти тройки двоичных символов кодируются во входные буквы канала по правилу, представленному на рис. 6.2.1. Это отображает каждое кодовое слово, представляющее собой последовательность 3N двоичных символов, в кодовое слово канала, представляющее собой последовательность N символов канала.

Для ансамбля кодов, рассмотренных в теореме 6.2.1, каждое кодовое слово является последовательностью 3N независимых равновероятных двоичных символов. Поэтому каждое кодовое слово канала представляет собой последовательность N троичных независимых символов с вероятностями Q (0) = 3/8, Q (1) = 3/g, Q (2) = V4-Более того, кодовые слова попарно статистически независимы и поэтому снова можно применять теоремы 5.6.1 и 5.6.2. В результате получаем, что существует код рассматриваемого типа, для которого Ре<ехр [-NEr (R)].

В общем случае дискретного канала без памяти можно применить аналогичный метод доказательства, отличающийся лишь тем, что конкретное преобразование, представленное на рис. 6.2.1, будет другим. Необходимо лишь аппроксимировать нужные входные вероятности Q в теореме кодирования следующим образом:

Q(k)iv~; (6.2.6)

2f ft

224
Тогда для любого k, ih двоичных последовательностей длины / отображаются во входной символ канала к, аналогично тому, как на рис. 6.2.1. Как велико должно быть / в соотношении (6.2.6), аппроксимирующем Q [к), зависит от Q и от того, как близко нужно приблизиться к показателю экспоненты Ет (R). При любых заданных j, длине сообщения L и длине кодового слова в канале N нужно использовать рассмотренный в теореме 6.2.1 ансамбль двоичных кодов с длиной двоичного блока jN. После отображения при помощи описанного выше преобразования двоичных кодовых слов в кодовые слова канала длины N и после использования теоремы 5.6.2 получаем, что существует код, для которого

Ре < ехр]{ — N [max (?0 (р, Q) — p#)j j , (6.2.7)

где Q определяется соотношением Q (k) = ih/2>.

Таким образом, мы описали простой алгоритм генерирования кодовых слов, при помощи которого можно достаточно хорошо приблизиться к границам, задаваемым теоремой кодирования. К сожалению, проблема нахождения алгоритмов декодирования является не такой простой.

6.3. ТЕОРИЯ ГРУПП

В предыдущих двух параграфах было широко использовано сложение по модулю 2. Для этого вначале было введено множество элементов 0 и 1, а затем определена операция ® над этими элементами. Под операцией здесь будем понимать правило, ставящее что-то в соответствие комбинации двух элементов множества. Ниже также будет рассматриваться ряд других множеств элементов и операций. Так как все они будут иметь одну и ту же математическую природу (образовывать группу), то полезно здесь прервать изложение и привести некоторые элементарные результаты теории групп, которые потребуются в дальнейшем.

Группой называется множество элементов а, Ь, с, ... с операцией, обозначаемой символом -, обладающей следующими свойствами*).
Предыдущая << 1 .. 104 105 106 107 108 109 < 110 > 111 112 113 114 115 116 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed