Проблема кодирования. Однозначность декодирования. Коды Хэмминга

В широком смысле слова под кодированием понимают сопоставление элементам множества Qпроизвольной природы элементов множества K также произвольной природы.

В узком смысле слова под кодированием понимают преобразование слов в некотором алфавите в слова в другом алфавите. Под словом понимаем любую последовательность символов. Обозначим через А* множество слов в алфавите A, включая пустое слово e.

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

Пусть А – алфавит сообщений, В – кодирующий алфавит. Под кодированием, таким образом, понимают отображение из понимают А* в B* f: А*® B* (рис.2.1).

Слова из R = Domf (из области определенияf) называются сообщениями. Если , то называется кодом слова . Множество C =Imf (область значений f) называется код множества R ..

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

Декодированием называется преобразование, обратное кодированию, которое позволяет по коду восстановить исходное сообщение. Ясно, что декодирование возможно, если у fесть обратное отображение f ^–1 . В этом случае говорят, что кодирование взаимно однозначно (или что код является разделимым).

Кодирование как преобразование слов в слова обычно преследует следующие цели:

– удобство хранения и передачи данных,

– обеспечение помехоустойчивости при передаче данных по каналу связи

Кодирование, осуществляемое с целью защиты от действий злоумышленника, обычно называют шифрованием.

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

Задача состоит в том, чтобы придумать такой способ кодирования, чтобы выполнялось . В основе многочисленных существующих методов кодирования лежат два основных вида кодирования: алфавитное (побуквенное)и равномерное (блочное).

1.Алфавитное кодирование – кодирование, определяемое соответствием:

где , слова

При этом соответствии каждому сообщению сопоставляется код . Соответствие называется схемой алфавитногокодирования, а слова – элементарными кодами (они заменяют один символ в сообщении).

Пример 1. Рассмотрим схему кодирования

Тогда сообщению сопоставляется код .

2. Равномерное кодирование – кодирование, определяемое соответствием:

где

при этом соответствии сообщению сопоставляется его код .

Соответствие называется схемой равномерного кодирования, а – элементарными кодами.

Заметим, что при равномерном кодировании слова одинаковой длины кодируются словами одинаковой длины, а если для слова существует представление вида , то оно единственно (т.к. имеют одинаковую длину).

Пример 2. Рассмотрим схему равномерного кодирования

,

Тогда слову сопоставляется код

Как при алфавитном, так и при равномерном декодирование состоит в разбиении кодового слова на элементарные коды и сопоставлении им прообразов (согласно схеме).

Пример. При равномерном кодировании со схемой

для кода имеем разбиение . Отсюда исходное сообщение есть .

Коды Хэмминга относятся к методам равномерного кодирования.

Рассматривается случай, когда исходный и кодирующий алфавиты являются двоичными, т.е. . В этом случае 1 символ слова соответствует 1 двоичному разряду.

Пусть – код сообщения . При передаче кода по каналу связи на выходе канала связи получают слово .

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

Поиск по сайту: