Васюков В.Н. - Введение в ТЭС (1275345), страница 6

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

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

,

где – матрица размера , состоящая из нулей, – символ транспонирования. С учетом можно записать

,

причем для двоичного кода минус можно опустить, так как сложение и вычитание по модулю 2 совпадают.

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

Коды Хэмминга.

Одним из наиболее известных классов помехоустойчивых линейных блочных кодов являются коды Хэмминга. Коды Хэмминга представляют собой -коды, удовлетворяющие условию

при некотором целом .

В частности, рассмотренный (7,4)-код является кодом Хэмминга.

Особое свойство кодов Хэмминга заключается в строении проверочной матрицы. Для любого линейного кода проверочная матрица содержит строк и столбцов; для кода Хэмминга и проверочная матрица содержит в качестве столбцов все возможные комбинации нулей и единиц, исключая нулевой вектор.

Для кода (7,4), рассмотренного в примере 6, проверочная матрица в соответствии с выражением , очевидно, имеет вид

.

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

Умножим принятую комбинацию на транспонированную проверочную матрицу

,

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

Чтобы убедиться в корректирующих свойствах кода Хэмминга, рассмотрим пример обнаружения ошибки в кодовой комбинации.

Пример 7. Предположим, что передавалась разрешенная кодовая комбинация 0100111 (напомним, что разрешенными комбинациями являются все линейные комбинации строк порождающей матрицы кода). Предположим также, что при передаче произошла ошибка, скажем, во втором символе, так что принята комбинация 0000111.

Умножая вектор-строку, соответствующую принятой комбинации, слева на транспонированную проверочную матрицу , получим синдром

,

который совпадает со второй строкой матрицы . Это указывает на то, что ошибочным является второй символ принятой комбинации. 

То обстоятельство, что синдром позволяет определить номер «испорченного» символа, фактически означает возможность исправления ошибок. В самом деле, если точно известно, что во втором символе имела место ошибка, декодер может ее исправить, прибавив (по модулю 2) к ошибочному символу единицу. Поэтому код Хэмминга принадлежит к кодам, исправляющим ошибки, или корректирующим.

Границы корректирующей способности кода Хэмминга иллюстрируются следующим примером.

Пример 8. Предположим, что при передаче разрешенной кодовой комбинации 0100111 произошли две ошибки, скажем, в третьем и пятом символах, так что принята комбинация 0110011. Найдем синдром:

.

Синдром указывает на 6-й символ, как на ошибочный. Таким образом, в случае двукратной ошибки факт ошибки обнаруживается (синдром оказывается ненулевым), но исправить ошибку нельзя, так как синдром оказывается таким же, как в случае однократной ошибки в другом символе. Итак, код Хэмминга (7,4) обнаруживает одно- и двукратные ошибки и исправляет однократные. 

Помехоустойчивость рассмотренного кода Хэмминга просто объясняется с геометрической точки зрения. Легко убедиться, что расстояние между любыми двумя разрешенными комбинациями этого кода не менее 3. Поэтому при приёме запрещенной комбинации она заменяется той разрешенной комбинацией, расстояние до которой равно 1. Двукратная ошибка отдаляет принимаемую комбинацию на расстояние, равное 2, что и приводит к ошибочному «исправлению» ошибки. При этом «исправляется» один символ, поэтому «исправленная» комбинация отстоит от принятой на расстояние 1.

Упражнения.

1. Найдите две разрешенные кодовые комбинации кода Хэмминга (7,4), не совпадающие со строками порождающей матрицы, и убедитесь в том, что расстояние между ними не менее трех.

2. Измените в одной из комбинаций два символа, найдите синдром и «исправьте» в принятой комбинации символ, на который он укажет. Найдите расстояние между «исправленной» и принятой комбинациями.

1. Информативность непрерывных источников сообщений

Наряду с дискретными источниками сообщений часто встречаются непрерывные источники, которые вырабатывают сообщения, обычно описываемые функциями, принимающими значения из непрерывного множества. Ярким примером непрерывного сообщения является речевое сообщение, описываемое функцией времени с вещественными значениями. Значение непрерывного сообщения в некоторый отдельный момент времени представляет собой непрерывную случайную величину , описываемую функцией распределения

,

где – реализация случайной величины , или плотностью распределения

.

Очевидно, введенное ранее понятие энтропии неприменимо к непрерывному источнику, так как неопределенность относительно любого конкретного значения непрерывной случайной величины равна бесконечности.

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

Для этой дискретной случайной величины можно записать энтропию

.

Подставив вместо вероятности ее приближенное значение , получим в пределе при

.

Из полученного выражения следует, что энтропия непрерывного распределения равна бесконечности за счет второго слагаемого, которое одинаково для всех непрерывных распределений, заданных на интервале . «Индивидуальность» распределения определяется первым слагаемым, которое и принимают в качестве меры информативности непрерывного источника и называют относительной, или дифференциальной энтропией

.

Дифференциальная энтропия, в отличие от энтропии дискретного источника, самостоятельного смысла не имеет и служит для сравнения информативности различных непрерывных источников между собой [3].

ВОПРОСЫ И ЗАДАЧИ К РАЗДЕЛУ

Вопросы для самоконтроля

1. Зачем применяют модуляцию?

2. В чем состоит цель экономного кодирования?

3. Что такое избыточность дискретного источника?

4. Какой источник обладает минимальной избыточностью и чему равна его энтропия?

5. Может ли равномерный код быть оптимальным (безызбыточным)?

6. В результате применения процедуры экономного кодирования получился троичный код с вероятностями символов 0.5, 0.2 и 0.3 соответственно. Можно ли считать такой код оптимальным?

7. Можно ли применять коды, для которых префиксное правило не выполняется?

8. Может ли помехоустойчивый код быть безызбыточным?

9. На чем основано корректирующее свойство помехоустойчивых кодов?

10. Что такое кодовое расстояние?

11. В какой связи находятся порождающая и проверочная матрицы линейного кода?

12. Какой геометрический смысл имеют строки порождающей матрицы?

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

14. Что такое синдром?

Задачи

1. Даны источники с алфавитами, содержащими по три символа и с распределениями вероятностей и . Найти энтропии источников.

2. Имеются два дискретных источника с матрицами
   ,
   (верхняя строка матрицы содержит символы, нижняя – их вероятности). Определить, какой источник обладает большей неопределенностью в случае если: а) , ; б) , .

3. По каналу связи передается один из двух символов или с одинаковыми вероятностями. На выходе они преобразуются в символы и , причем из-за помех в среднем два символа из ста принимаются неверно. Определите среднее количество информации на один символ, передаваемое по такому каналу. Сравните с аналогичной величиной при отсутствии помех.

4. Источник сообщений вырабатывает символы , и с вероятностями , и соответственно. Вероятности появления пар заданы таблицей

	0.1	0.2	0.1	0.2	0.3	0	0.1	0	0

Определить энтропию источника и сравнить с энтропией источника без памяти с такими же вероятностями символов.

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

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