- •Теорема дискретизации
- •Дискретизация двумерных сигналов (изображений)
- •Квантование сообщений. Ошибки квантования
- •Периодические сигналы
- •Лекция 3. Модуляция и управление информационными параметрами сигналов.
- •Энтропия источника дискретных сообщений
- •Тема. Основы экономного кодирования Лекция 7. Системы сжатия данных для кодирования источника информации
- •Алгоритм Хаффмена
- •Коды с памятью
- •Арифметическое кодирование
- •А. Кодирование
- •Декодирование
- •Пример распаковки данных с помощью алгоритма lz78
- •Кодирование длин повторений
- •Дифференциальное кодирование
- •Методы сжатия с потерей информации
- •Стандарт сжатия jpeg
- •Рекурсивный (волновой) алгоритм
- •Методы сжатия подвижных изображений (видео)
- •Методы сжатия речевых сигналов
- •Итеративный код
- •Лекция 12. Алгоритмы помехоустойчивого кодирования и синдромное декодирование линейных блочных кодов Порождающая матрица линейного блочного кода
- •Проверочная матрица
- •Синдром и обнаружение ошибок
- •Синдромное декодирование линейных блочных кодов
- •Лекция 13. Применение корректирующего кодирования в системах связи
- •Каскадные коды
- •Кодирование с чередованием (перемежением)
- •Лекция 14. Элементы теории приема и обработки информации
- •Оказывается, что значение p (Uk / X) принимает максимальное значение в том случае, когда минимальна величина
- •Лекция 15. Принципы многоканальной передачи информации и понятие о разделении сигналов
- •Пропускная способность многоканальных систем передачи информации
- •Множественный доступ с частотным разделением в спутниковых системах
Проверочная матрица
Линейный систематический блочный код может быть определен также с использованием так называемой проверочной матрицы H, обладающей следующим свойством:
- если некоторая последовательность U является кодовым словом, то
U* HT = 0. (1.17)
Другими словами, проверочная матрица H ортогональна любой кодовой последовательности данного кода.
Проверочная матрица имеет размерность (n-k)*n и следующую структуру :
|
P00 |
P10 |
… |
Pk-1, 0 |
1 |
0 |
0 |
… |
0 |
|
|
P01 |
P11 |
… |
Pk-1, 1 |
0 |
1 |
0 |
… |
0 |
|
H = |
P22 |
P12 |
… |
Pk-1, 2 |
0 |
0 |
1 |
… |
0 |
, (1.18) |
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
|
P0, n-k-1 |
P1, n-k-1 |
… |
Pk-1, n-k-1 |
0 |
0 |
0 |
… |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
PT |
I1(n-k)´(n-k) |
|
где PT - транспонированная подматрица P из порождающей матрицы G ;
I1(n-k)´(n-k) - единичная матрица соответствующего размера.
Видно, что единичная и проверочная подматрицы в G и H поменялись местами, кроме того, изменился их размер.
Для рассматриваемого нами в качестве примера (7,4)-кода Хемминга проверочная матрица H имеет вид
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
H(7,4)= |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
. (1.19) |
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
Проверочная матрица позволяет легко определить, является ли принятая последовательность кодовым словом данного кода.
Если принята последовательность символов c = (1011001), то
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
T |
c* HT = (1011001) |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
= (1 1 0) ¹ 0 . |
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
Отсюда можно сделать вывод, что последовательность c = (1011001) не является кодовым словом данного кода.
Рассмотрим другой пример. Допустим, принята последовательность d = (0010111), тогда
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
T |
d × HT = (0010111) |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
= (0 0 0) = 0 , |
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
то есть двоичная последовательность d принадлежит коду с проверочной матрицей H.