Основные свойства линейных кодов

1. Произведение любого кодового слова на транспонированную проверочную матрицу дает нулевой вектор размерности (n - k)

Пример. для кода (5,3)

2. Произведение некоторого кодового слова , т.е. с ошибкой, на транспонированную проверочную матрицу называется синдромом и обозначается S_i(x),

3. Между порождающей и проверочной матрицами в систематическом виде существует однозначное соответствие, а именно:

4. Кодовое расстояние d₀ (n, k)-кода равно минимальному числу линейно зависимых столбцов проверочной матрицы

Пример. для кода (5,3): , d₀ = 2; для кода (5,2): , d₀ = 3

5. Произведение информационного слова на порождающую матрицу дает кодовое слово кода

Пример. для кода (5,3):

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

7. Кодовое расстояние любого линейного (n, k)-кода удовлетворяет неравенству (граница Сингтона). Линейный (n ,k)-код, удовлетворяющий равенству , называется кодом с максимальным расстоянием.

Оптимальное кодирование.

Оптимальное кодирование служит для наиболее эффективного использования пропускной способности каналов, т.е. каждый символ при оптимальном кодировании несет в себе максимальное количество информации. Рассмотрим код Хафмана и алгоритм Шеннона-Фано.

Код Хаффмана ‑ статистический способ сжатия, который дает снижение средней длины кода используемого для представления символов фиксированного алфавита. Код Хаффмана является примером кода, оптимального в случае, когда все вероятности появления символов в сообщении - целые отрицательные степени двойки. Код Хаффмана может быть построен по следующему алгоритму:

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;

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

3. Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (например, направо ‑ 1, налево ‑ 0).

Или в виде таблицы :

P(m1) = 0,6	1			1
P(m2) = 0,3	0	1		01
P(m3) = 0,2		0	1	001
P(m4) = 0,1			0	000

Для заданного распределения частот символов может существовать несколько возможных кодов Хаффмана, ‑ это дает возможность определить каноническое дерево Хаффмана, соответствующее наиболее компактному представлению исходного текста.

Близким по технике построения к кода Хаффмана являются коды Шеннона-Фано, предложенные Шенноном и Фано в 1948-49 гг. независимо друг от друга. Их построение может быть осуществлено следующим образом:

1. Выписываем в ряд все символы в порядке возрастания вероятности появления их в тексте;

2. Последовательно делим множество символов на два подмножества так, чтобы сумма вероятностей появления символов одного подмножества была примерно равна сумме вероятностей появления символов другого. Для левого подмножества каждому символу приписываем "0", для правого ‑ "1". Дальнейшие разбиения повторяются до тех пор, пока все подмножества не будут состоять из одного элемента.

Алгоритм создания кода Хаффмана называется "снизу-вверх", а Шеннона-Фано ‑ "сверху-вниз". Преимуществами данных методов являются их очевидная простота реализации и, как следствие этого, высокая скорость кодирования/декодирования. Основным недостатком ‑ неоптимальность в общем случае.