Множество - кодовые сл
Cтраница 3
Неравенство (3.4) из леммы 3.2 позволяет ограничить эти энтропии сверху через объемы образов gyn ( А, 1 - е) ( где V PYX) - Будем строить нашу функцию /, строя множества AJ с заданными объемами образов, для которых эта оценка является точной. По той же лемме в качестве таких множеств Аг можно брать множества кодовых слов ( п, е) - кодов для ДКБП V, состоящие из последовательностей одного и того же типа. Мы не будем точно определять, что это значит, поскольку это понятие будет использоваться только для предварительного описания формулируемых и доказываемых позже результатов. [31]
Показатель степени в (5.5.1) равен половине показателя для двух кодовых слов, отличающихся в каждой позиции, но Р е все еще стремится к 0 экспоненциально по N. В качестве компенсации за это уменьшение показателя степени появляется способ рассмотрения больших множеств кодовых слов, не требующий заботы о детальном выборе слов. [32]
Мы предположим, что для каждого рассматриваемого кода для канала множество сообщений совпадает с множеством кодовых слов. Таким образом, декодер ( k, е) - кода с множеством кодовых слов f - l ( i) - это некоторое отображение ф ( -): Y - - q - 1 ( О-Очевидно, что отображение с указанными свойствами всегда существует. [33]
Мы применим конструкцию максимального Кода из леммы 3.8 два раза. При доказательстве будем рассматривать только такие коды, для которых кодер является тождественным отображением на множестве кодовых слов. [34]
Если две порождающие матрицы имеют одно и то же пространство строк, то они порождают одно и то же множество кодовых слов, хотя и с различными отображениями информационных последовательностей на кодовые слова. [35]
В последнем параграфе было показано, что вероятность ошибочного декодирования для двух кодовых слов стремится к нулю экспоненциально с ростом длины блока. Вместе с тем в этом случае передается только один двоичный символ источника на блок, так что вероятность ошибки уменьшается только за счет скорости передачи. Ясно, что единственной возможностью для снижения вероятности ошибки без уменьшения скорости передачи является рассмотрение большего множества кодовых слов. [36]
Из определения следует, что код источника можно задать, указав как набор кодовых слов, так и множество тех последовательностей сообщений, которые кодируются взаимно-однозначно. Из приведенного определения следует, что несуществен порядок, в котором сопоставляются кодовые слова последовательностям из Тп. Действительно, два кода источника, имеющие одно и то же множество Тп и одно и то же множество кодовых слов U, имеют одну и ту же вероятность ошибки декодирования РР ( см. (8.3)) и одно и то же число символов, затрачиваемых на кодирование одного сообщения. [37]
Для построения линейных кодов для недвоичных каналов в множестве входных символов полезно ввести арифметическую структуру. Множество кодовых слов образует аддитивную группу; множество полученных слов с одним и тем же синдромом образует Смежный класс по этой подгруппе. Для фиксированного: полученного слова множество возможных векторов ошибок образует смежный класс, содержащий это слово. Задача декодера может быть, таким образом, сформулирована так: по заданному синдрому полученного слова найти наиболее вероятный вектор шума, лежащий в смежном классе слов с этим синдромом. [38]
Если энтропия Н ( S) источника информации не превосходит пропускной способности линии С, то появляется возможность кодировать информацию источника с помощью входного алфавита. При этом, учитывая закон распределения источника, кодовые слова следует составить так, чтобы закон распределения на входе был по возможности близок к закону, дающему максимум взаимной информации. Множество кодовых слов называется кодом. [39]
Заметим, что класс кодов, для которого каждое кодовое слово удовлетворяет ограничению, содержится в классе кодов, для которых удовлетворяется ограничение при усреднении по кодовым словам. Таким образом, любая вероятность ошибочного декодирования, которая может быть достигнута на некотором коде первого класса, может быть также достигнута на коде ( в частности, на том же коде) последнего класса. Обратно, любая нижняя граница вероятности ошибки - последнего класса также будет нижней границей первого класса. Поэтому теорема кодирования будет доказываться при ограничении на каждое кодовое слово, а ее обращение - когда удовлетворяется ограничение только при усреднении по множеству кодовых слов. Таким образом, каждая теорема будет применима к обоим случаям, и будет показано, что нет существенной разницы в том, какой из двух случаев рассматривается. Начнем с изучения обращения теоремы кодирования, так как она почти не отличается от соответствующей теоремы для случая без ограничений. [40]
 |
Соответствие кодовых слов и сообщений. [41] |
При больших k реализация таблицы соответствия кодера становится слишком громоздкой. Для кода ( 127, 92) существует 292 или приблизительно 5 х 1027 кодовых векторов. Если кодирование выполняется с помощью простой таблицы соответствия, то представьте, какое количество памяти нужно для такого огромного числа кодовых слов. К счастью, задачу можно значительно упростить, по мере необходимости генерируя необходимые кодовые слова, вместо того чтобы хранить их в памяти постоянно. Поскольку множество кодовых слов, составляющих линейный блочный код, является - мерным подпространством - мерного двоичного векторного пространства ( k), всегда можно найти такое множество - кортежей ( с числом элементов, меньшим 2), которое может генерировать все 2 кодовых слова подпространства. О генерирующем множестве векторов говорят, что оно охватывает подпространство. Наименьшее линейно независимое множество, охватывающее подпространство, называется базисом подпространства, а число векторов в этом базисном множестве является размерностью подпространства. [42]
Страницы: 1 2 3