Методика Хаффмена

Буквы записываются в порядке убывания вероятности и последние две объединяются, если запись в порядке убывания вероятности и т.д.

022 0,22 0,22 0,26 0,32 0,42 0,58

0,2 0,2 0,2 0,22 0,26 0,32 0,42

0,16 0,16 0,16 0,2 0,22 0,26

0,16 0,16 0,16 0,16 0,2

0,1 0,1 0,16 0,16

0,1 0,1 0,1

0,04 0,06

0,02 затем строится кодовое дерево.

Особенности систем эффективного оптимального кодирования.

1. Длина кодовых комбинаций различна.

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

2. При кодировании блоками необходимо еще одна задержка до кодирования. Причем при появлении блока с малой вероятностью происходит задержка при декодировании.

3. При воздействии помех возможно изменение комбинации, что влечет за собой неправильное декодирование всех последующих комбинаций.

Помехоустойчивое кодирование

При скорости передачи, меньшей пропускной способности канала существует код, при котором вероятность ошибки приема сообщения как угодно мала.

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

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

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

В блоковых кодах каждой k последовательности символов сопоставлены n символов другого кода, причем n>k. Код называют равномерным, если n-const для всех букв сообщения.

Если в коде из n символов, возможно указать на информационные и избыточные, то код называется разделимым.

Использование избыточности

Допустим, на вход кодирующего устройства подано k информационных символов, а на выходе получена последовательность n символов, причем k < n. Может быть реализовано 2^k входных последовательностей и 2ⁿ выходных. Но из 2ⁿ выходных только 2^k комбинаций соответствуют входным последовательностям, это «разрешенные» кодовые комбинации, остальные 2^k-2ⁿ «запрещенные».

Искажения в процессе передачи заключаются в том, что одна из разрешенных комбинаций заменяется другой (необязательно разрешенной). Получается, что каждое из 2^k сообщений может перейти в каждое из 2ⁿ комбинаций. Возможно 2^k2ⁿ случаев передачи, из них 2^k - безошибочная передача, 2^k(2^k-1) - переход в другие разрешенные комбинации, 2^k(2ⁿ-2^k) - в запрещенную комбинацию. Часть ошибок может быть обнаружена

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

Если d=2, то не одна одиночная ошибка не будет пропущена. Этот случай может выглядеть так:

000 011 101 110 разрешенные

001 010 100 111 запрещенные

Код обнаруживает ошибки кратности 2, если d  2+1.

Для исправления одиночной ошибки кодовое расстояние d  3, чтобы запрещенные подмножества не пересекались.

000 111 разрешенные

001 010 100 110 101 011 запрещенные

В общем случае для исправления ошибки кратность S d_min  2S+1.

Для обнаружения ошибок кратности  и исправления ошибок кратности S d_min  +S+1.

Общее число исправляемых ошибок для 1-й кодовой комбинации , всех комбинаций вместе с разрешенной в этом подмножестве 1 + однозначное декодирование возможно, если эти подмножества не пересекаются.

Так как общее число n разрядных комбинаций равно 2ⁿ, то число разрешенных комбинаций не может быть больше

или

Геометрическая интерпретация корректирующих кодов

Любая и разрядная кодовая комбинация может быть представлена как вершина n мерного единичного куба, при n=2 это вершины квадрата, при n=3 вершины куба, при n=4 вершины 4 мерного куба и т.д. Геометрический смысл расстояния Хемминга это число ребер, которое необходимо пройти, чтобы перейти из одной кодовой комбинации до другой.

Кодовое расстояние

Степень отличия двух кодовых комбинаций характеризуется кодовым расстоянием (расстояние Хемминга). Это выражается числом d = числу разрядов, в которых комбинации отличаются друг от друга, причем d = min числу разрядов.

1001111

1100010 Декодирование осуществляется так,что принятая комбинация отождествляется с той к которой меньше расстояние d.

Если d=1 n=3, то все кодовые комбинации, разрешенные 000 001 010 011 100 101 110 111 любая одиночная ошибка переводит переданную в другую разрешенную.

Систематические коды

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

Число проверочных равенств, проверочных символов и номера проверяемых информационных разрядов, входящих в каждое равенство определяется тем, сколько и каких ошибок должен исправлять и обнаруживать код.

При декодировании производится проверка, проверочных равенств. В случае двоичного кода эта процедура сводится к проверке на четность символов, входящих в данное равенство. Совокупность проверок позволяет обнаружить и исправить ошибки.

Множества, для которых определены алгебраические операции, называются алгебраическими. Под алгебраической операцией понимается однозначное сопоставление двум элементам третьего. Обычно это сложение a+b=c или умножение ab=c, обратные операции называются вычитанием и делением. Иногда эти операции проводятся не над числами и не идентичны арифметическим операциям.

Группой называется алгебраическая система, состоящая из множества элементов в которой определена одна основная операция: ассоциативная (a+b)+c=a+(b+c) (ab)c=a(bc) коммутативная, а+b=b+a ab=ba и есть обратная операция.

В каждой группе G_n существует однозначно определяемый элемент для всех a из G_n удовлетворяющих условие a+0=a, 0+a=а, если основная операция сложение и a1=a, 1a=а, если основная операция умножение.

Всякий элемент a обладает элементом однозначно определяемым из

a+(-a)=(-a)+a=0 или aa^-1=a^-1a=1

Этот элемент называется обратным или противоположным.

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

Группа, состоящая из конечного числа элементов, называется замкнутой или конечной.

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

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

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

Множество 01; 10; 11 не группа, так как нет нулевого элемента.

Множество 0000 1101 1110 0111 не замкнутая группа, так как 1101+1110=0011 Элемента 0011 нет в исходном множестве.

Множество G 001 010 011 100 101 110 111 будет группой, так как удовлетворяет всем условиям группы, при введении сложения по модулю 2.

Подмножество группы, само являющееся группой, называется подгруппой A_n.

000, 001, 010, 011 подгруппа из группы G . Если в абелевой группе G есть подгруппа A_n, то сумма A_j с B, где B элемент множества не входящий в A_n образует смежный класс группы G_n по подгруппе A_n порождаемый элементом B. В этом смежном классе есть и сам элемент B так как в A_n есть 0. Беря некоторые B_i, не входящие в смежные классы, можно всю группу G разложить в смежные не пересекающиеся классы по подгруппе A_i. Элемент B_i называется главным образующим.

Следствия.

1. Два смежных класса не имеют ни одного общего элемента A_i .

2. В смежном классе нет двух одинаковых элементов так как C=A_i B.

Построение группового кода.

Построение кода производятся исходя из необходимого объема кода Q (число команд, уровней измерения и так далее) и статистических данных о наиболее вероятных векторах ошибки в используемом канале связи.

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

Учитывая, что 2^k-1Q определяют k число разрядов НДК для передачи заданного числа команд.

Теперь каждой из 2^k-1 комбинации k разрядного кода нам надо поставить в соответствии комбинацию из n символов n>k.

Значения символов в n-k проверочных разрядов устанавливаются в результате суммирования по модулю 2 значений символов в определенных информационных разрядах.

Множество 2^k (разрешенных) n разрядных кодовых комбинаций может быть подгруппой группы n разрядных комбинаций. Это множество и будет групповым кодом.

Разложим группу 2ⁿ n разрядных кодовых комбинаций в смежные классы по 2ⁿ разрешенным n разрядным кодовым комбинациям, в которых пока не заполнены проверочные разряды. В разложении будет 2^n-k-1 смежный класс. Элементы каждого смежного класса есть сумма разрешенных кодовых комбинаций и образующего элемента данного класса. Если за образующие элементы принять наиболее вероятные для данного канала ошибки, то в каждом классе сгруппируются кодовые комбинации, полученные в результате воздействия на все разрешенные комбинации вектора определенной ошибки.

Для исправления ошибки на выходе канала надо определить, к какому классу смежности относится полученная кодовая комбинация.

Суммируя по модулю 2, с образующим элементом этого класса полученную кодовую комбинацию, мы получим переданную кодовую комбинацию, устранив ошибку. Такой код исправляет 2^n-k-1 ошибок по числу смежных классов, а всего ошибок 2ⁿ-1.

Чтобы выяснить к какому классу смежности относится принятая комбинация, каждому классу смежности поставлена в соответствии некоторая последовательность символов, которая называется определитем или опознавателем.

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

Исправление ошибок возможно при однозначном составлении опознавателя и смежного класса, таким образом, число исправляемых ошибок определяет число избыточных разрядов n-k .

Если необходимо исправить одиночные ошибки 000...01, 000...10, ...100...00 различных ненулевых последовательностей должно быть n.

Число проверочных разрядов может быть определено из 2^n-k-1= или в случае однократной ошибки 2^n-k-1=C_nⁱ=n. Если передается 15 команд k=4 Q=2^k 2^n-k-1=n 2^n-4-1=n n=7.

Число исправляемых ошибок тоже 7.