БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

кафедра РЭС

реферат на тему:

«Практическое кодирования по Хэммингу»

МИНСК, 2009

Пусть нам предстоит закодировать текст, записанный на некотором языке, таком, что число букв в алфавите этого языка n = 2m (m целое число), а появление в тексте тех или иных букв алфавита равновероятно и не зависит от того, какие буквы им предшествовали. Тогда имеем

p(i) = p(j) = 1/n; H = log2 = m.

Условия задачи таковы, что достичь оптимального кодирования можно самым незатейливым методом кодирования - побуквенным кодированием с постоянной длиной (l = m) кодовых наборов. При этом, однако, мы оказались бы лишенными какой-либо возможности обнаруживать, а тем более исправлять ошибки. Чтобы такая возможность появилась, необходимо отказаться от оптимальности кода, "раскошелиться" на несколько дополнительных двоичных символов на букву, т.е. умышленно ввести некоторую избыточность, которая смогла бы помочь нам обнаружить или исправить ошибки. Необходимое число дополнительно вводимых двоичных символов на одну букву обозначим через x, и тогда длина кодового набора станет равной l = m + x. Примем, что в результате помех (случайных или преднамеренных) лишь один или вовсе никакой из m + x двоичных символов может превращаться из единицы в нуль или, наоборот, из нуля в единицу. Примем далее, что 1 + m + x событий, заключающиеся в том, что ошибка вообще не произойдет, произойдет на уровне первого, второго, .... (m + x)-го символа кодового набора, равновероятны. Энтропию угадывания того, какое именно из этих 1 + m + x событий будет иметь место, в силу равновероятности этих событий можно определить по формуле Н = log2 (1 + m + х) бит. Таким образом, для обнаружения самого факта наличия одиночной ошибки и установления ее позиции необходимо заполучить информацию в количестве не менее Н = log2(1 + m + x) бит. Источником этой информации служат лишь дополнительно введенные x двоичных символов, так как остальные m символов из-за оптимальности кодирования до предела заняты описанием самого текста. Заметим, что x двоичных символов в лучшем случае могут содержать информацию в количестве x бит. Таким образом, при конструировании кода, обнаруживающего и исправляющего одиночную ошибку, следует учесть, что этого можно добиться лишь при значениях x, удовлетворяющих неравенству

х>= log2(l+m+x),

или 2x-x-1>=m.

Рис. 1.Зависимость нижней границы допустимых значений x от m (сплошная линия) и зависимость относительной избыточности от m (пунктирная линия).

Р. Хэмминг разработал конкретную конструкцию кода. которая обеспечивает весьма элегантное обнаружение и исправление одиночных ошибок при минимально возможном числе дополнительно вводимых двоичных символов, т.е. при знаке равенства. Проследим за построением этого кода, когда m = 4. Из рисунка следует, что при этом допустимое значение x равно трем, т.е. при числе основных (информационных) двоичных символов m = 4, число дополнительно введенных, т.е. контрольных символов должно быть не менее трех. Примем, что нам удалось "обойтись" именно тремя дополнительными символами, т.е. удалось сконструировать такой код, при котором каждый из дополнительно введенных трех символов дает нам максимально возможное количество информации, т.е. ............