Embed Word.Picture.8 Рис. 7. Пример кодового дерева

Таблица 1.

i	Сим- волы	ti	Pi	Объединение символов
				1	2	3	4	5	6	7
										0,579
									0,422	0,422
								0 ,316	0,316
1	А	5	0,263	0,263	0,263	0,263	0,263	0,263	0,263
							0,212	0,212
						0,210	0,210	0,210
2	О	3	0,158	0,158	0,158	0,158	0,158
3	Р	3	0,158	0,158	0,158	0,158	0,158
				0,106	0,106	0,106
					0,106	0,106
4	Б	2	0,105	0,105	0,105
5	Т	2	0,105	0,105	0,105
6	Л	1	0,053	0,053
7	Н	1	0,053	0,053
8	Я	1	0,053
9	пробел	1	0,053

Теперь, двигаяся по кодовому дереву сверху вниз, можно записать для каждого исходного алфавита соответствующую ему кодовую комбинацию: А-01, О-000, Р – 001, Б-110, Т-111, Л-1010, Н-1011, Я-1000, пробел-1001.

Заданная текстовая строка, закодированная кодом Хаффмана, будет иметь вид:

10100111000000101111000001101101100010010010111000011101 и занимать объем памяти Qк=56 бит.

Таким образом, рассчитанный по (10) коэффициент сжатия Rсж2,71. Энтропия исходного сообщения согласно (8):

а среднее число разрядов , приходящихся на один символ сообщения, по формуле (9):

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

3.2. Помехоустойчивое кодирование информации кодом Хэмминга

Защита информации от ошибок в ВЗУ базируется на достижениях тео­рии помехоустойчивого кодирования, отличительными чертами которой яв­ляются намеренное введение избыточности и дискретный характер сигна­лов [7]. Дискретность позволяет описывать наборы сигналов символами неко­торого абстрактного алфавита. Намеренное введение избыточности обеспечивает возможность исправления ошибок при использовании сложных комбинаторных конструкций. Это позволяет сформулировать задачи поме­хоустойчивого кодирования как чисто математические.

Различают два различных класса стратегий кодирования - блочное и неблочное кодирование. Блочное кодирование используется в ВЗУ наи­более часто. Сущность его состоит в том, что последовательность сим­волов, поступающее на вход кодера, разбивается на блоки (векторы) по k символов в каждом: . Кодер преобразует каждый входной k–блок в выходной n–блок таким образом, чтобы различным входным блокам соответствовали различные выходные. Заметим, что во входной последовательности символов все символы имеют одинаковую длину.

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

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

Из теории помехоустойчивого кодирования известно, что двоичные ( q=2 ) блочные линейные систематические (n, k)–коды с конструктив­ным кодовым расстоянием d способны исправить в кодовом слове длины n бит t ошибочных бит, если , где k - количество информационных разрядов в кодовом слове.

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

Значения проверочных разрядов (n,k)–кода выбираются так, чтобы

, (11)

где – вектор кодового слова, – матрица размера с линейно-независимыми строками, называемая проверочной матрицей, Т - символ транспонирования.

Линейный код определяется как множество решений (11). Процедура кодирования линейных кедов наиболее проста, так как для её выполнения достаточно хранить в памяти только r векторов матрицы . Для нелинейного кода мощностью необходимо помнить все кодовых последовательностей.

В классе двоичных линейных кодов одни из самых простых проце­дур кодирования и декодирования имеют систематические коде Хэмминга [2].

Рассмотрим их особенности на примере (7,4) - кода Хемминга с d=3 и . Проверочная матрица этого кода имеет раз­мерность . Столбцами являются всевозможные ненулевые двоичные наборы длины r , которые располагают так, чтобы i-й слева столбец h_i представлял собой двоичное разложение числа i (старшие разряда сверху):

(12)

Кодовое олово имеет вид , где разряды x5, x6, x7 – проверочные. Чтобы получить зависимость значений проверочных разрядов от информационных, матрицу целесо­образно преобразовать к виду

, (13)

где – квадратная единичная подматрица размера .

Преобразование матрицы осуществляется путем сложения по модулю два различных комбинаций r её строк. Подставив (13) в (11) и учитывая, что все операции сложения в (11) выполняются по модулю два, получим выражения для определения проверочных символов:

(14)

Рассмотрим пример кодирования. Пусть из кодера Хаффмана в кодер кода Хэмминга поступает последовательность 110010101... Разбиваем данную последовательность на информационные блоки по 4 разряда: 1100 1010 I... К каждому информационному блоку добавляем 3 проверочных разряда, вычисленные согласно (14): 1100110 1010101 I...., и передаем их на вход канального кодера.

Исправление возникшей ошибки не вызывает особых затруднений. Если вместо кодового слова в декодер кода Хэмминга поступило сообщение , необходима вычислить

, (15)

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

Например, пусть передавалось кодовое слово , а в декодер кода Хэмминга поступило слово с ошибкой в разря­де х4. Тогда, вычисляя (15) с матрицей вида (12) получим , что соответствует четвертому столбцу матрицы, и четвертый разряд слова должен быть инвертирован. Отбрасывая после декодирования проверочные разряди, передаем в декодер кода Хаффмана восстановленную последовательность.