Кодирование и декодирование

Кодированием называется отображение произвольного множества А в множество конечных последовательностей в некотором алфавите В, а декодированием – обратное отображение.

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

Блочный двоичный (m,n) – код

Решение проблемы кодирования и декодирования обеспечивает надежную передачу информации по каналам связи. Рассмотрим как устроен блочный двоичный (m,n) – код.

Сообщения записываются с помощью 0 и 1. Получается конечная последовательность длины m из 0 и 1. Эта последовательность кодируется более длинной последовательностью длины n (n>m) из 0 и 1, которая и передается по каналам связи. Принятые символы 0 и 1 декодируются по определенной схеме в сообщение, которое с большой вероятностью совпадает с переданным сообщением.

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

Код с проверкой четности

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

Пример. Кодируем слово 0010 с помощью кода с проверкой четности.

Решение. Так как , то будет передано сообщение 00101.

Пример. Декодируем слово 10101 с помощью кода с проверкой четности.

Решение. Отбрасываем последнюю цифру и получаем 1010.

Сумма всех передаваемых символов по модулю 2 при использовании кода с проверкой четности должна быть нулевой. Это позволяет обнаружить однократную ошибку. Но код с проверкой четности не способен обнаружить двойную ошибку.

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

Решени е. Так как сумма полученных символов равна и отлична от 0, то в полученном сообщении содержится ошибка.

Код с проверкой четности не позволяет исправить обнаруженную ошибку.

Код с тройным повторением

Код с тройным повторением – это пример кода с исправлением ошибок.

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

Пример. Кодируем слово 0010 с помощью кода с тройным повторением.

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

Пример. Декодируем сообщение 000110101001 с помощью кода с тройным повторением.

Решение. Из первой тройки символов 000 получаем символ 0. Во второй тройке символов 110 чаще встречается 1. Это и будет очередным символом декодированного сообщения. Из третьей тройки символов 101 получаем символ 1. Последняя тройка символов 001 добавляет к декодированному сообщению 0. Тогда декодированное сообщение будет 0110.

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

Вес и расстояние Хемминга

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

Пусть U = (U₀, U₁, U₂,...U_n-1) - двоичная последовательность длиной n.

Число единиц (ненулевых компонент) в этой последовательности называется весом Хемминга вектора U и обозначается w(U).

Например, вес Хемминга вектора U = (1001011) равен четырем, для вектора U = (1111111) величина w(U) составит 7 и т.д.

Таким образом, чем больше единиц в двоичной последовательности, тем больше ее вес Хемминга.

Далее, пусть U и V будут двоичными последовательностями длиной n.

Число разрядов, в которых эти последовательности различаются, называется расстоянием Хемминга между U и V и обозначается d(U, V).

Например, если U = (1001011), а V = (0100011), то d(U, V) = 3.

Задав линейный код, то есть определив все 2^k его кодовых слов, можно вычислить расстояние между всеми возможными парами кодовых слов. Минимальное из них называется минимальным кодовым расстоянием кода и обозначается d_min.

На множестве двоичных слов длины расстоянием Хемминга между словами называется число несовпадающих позиций в словах .

Пример. Определим расстояние Хемминга между словами

Решение. Так как в словах различны три позиции (1-я, 3-я, 4-я) то расстояние Хемминга между словами равно =3.

Аксиомы расстояний

2.

3.

Теорема. Код позволяет обнаружить не более ошибок тогда и только тогда, когда минимальное расстояние Хемминга между кодовыми словами превосходит

Теорема. Код позволяет исправлять не более ошибок тогда и только тогда, когда минимальное расстояние Хемминга между кодовыми словами превосходит

Для конечного множества мощности можно определить Относительное расстояние Хэмминга: . Очевидно,

Пример 35. На универсальном множестве зададим подмножества и :

, .

Применяя формулу расстояния Хэмминга между множествами, получим:, а для относительного расстояния Хэмминга имеем:

Коды Хемминга

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

Проверочная матрица кода Хемминга

Из 0 и 1 составляется матрица размера , где Е –единичная матрица порядка , а матрица А размера подбирается так, чтобы в столбцах матрицы М были указаны все двоичные разложения чисел от 1 до (т.е в матрице М не должно быть одинаковых столбцов) Порядок составления столбцов матрицы А является произвольным..

Матрица М называется проверочной матрицей - кода Хемминга

Пример. Покажем, что матрица является проверочной матрицей кода Хемминга.

Решение. Три последних столбца образуют единичную матрицу 3-го порядка . А в столбцах матрицы М указаны двоичные разложения чисел 7,3,6,5,4,2,1. Матрица . Так как размеры матрицы . Отсюда . Матрица М является проверочной матрицей (4, 7) кода Хемминга.

Порождающая матрица кода Хемминга

По проверочной матрице кода Хемминга строится порождающая матрица кода Хемминга , где - единичная матрица порядка , а получается транспонированием матрицы А (нужно строки записать в виде столбцов).

Пример. Определим порождающую матрицу кода Хемминга

Решение. Единичная матрица порядка равна , а матрица при транспонировании превратится в матрицу , поэтому порождающая матрица кода Хемминга равна .

Кодирование

При кодировании вектора надо умножить вектор на порождающую матрицу кода Хемминга слева: . При умножении матриц используется сложения по модулю 2. Первые символов вектора - это исходное сообщение, а последние символов нужны для контроля.

Пример. Кодируем сообщение

Решение. Кодированное сообщение равно =(0011) =

, то есть кодированное сообщение 0011011.

Здесь первые символа – это исходное сообщение 0011, а последние 3 символа нужны для контроля.

Исправление ошибок

Коды Хемминга позволяют исправлять однократную ошибку. Предположим, что получено кодированное сообщение . Если при умножении проверочной матрицы М на вектор получается нулевой вектор , то считается, что полученное сообщение не одержит ошибок.

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

При декодировании исправленного сообщения надо взять первые символов. Это и есть исходное сообщение.

Пример. Декодируем сообщение

Решение. Умножим проверочную матрицу на вектор . Получим

Полученный вектор совпадает с 1-м столбцом проверочной матрицы М. поэтому надо изменить 1-й символ сообщения . Получим вектор (1110010). Первые =4 символа (1110) и составляют декодированное сообщение.

Код Хаффмана

Код Хаффмана принадлежит к семейству, кодов с переменной длиной кодовых слов. Самый известный код переменной длины – азбука Морзе.

Основная идея при использовании кодов переменной длины – это передача часто встречающихся символов короткими кодовыми словами, а длинными кодовыми словами передаются редко встречающиеся символы. Это позволяет минимизировать средние затраты.

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

Алгоритм построения кода Хаффмана.

1. Расположить знаки в порядке убывания частот.

2. Объединить два знака с наименьшими частотами в один составной знак.

3. К полученной последовательности применять пункты 1 и 2 до тех пор, пока все знаки не будут объединены.

4. Приписать первой компоненте последнего объединения символ 0, а второй компоненте – 1. Продолжить этот процесс до тех пор, пока все исходные знаки не будут закодированы.

Пример 1. В таблице указаны частоты букв. Построим по этим данным код Хаффмана.

Буква	a	н	о	e	m	u
частота

Расположим буквы в порядке убывания частот. Так как частоты буквы a и u одинаковы, то порядок этих букв в таблице (au или ua) не важен.

Буква	о	е	а	и	н	m
частота

Объединим две буквы с наименьшими частотами (н, m) в один составной знак (нm). Этому знаку припишем частоту, равную сумме частот букв

н, m (9+8=17). После этого расположим все знаки в порядке убывания частот.

Буква	о	е	нm	а	и
частота

Объединим две буквы с наименьшими частотами (а, и) в один составной знак (аи). Этому знаку припишем частоту, равную сумме частот букв

а, и (15+15=30). После этого расположим все знаки в порядке убывания частот

Буква	аи	о	е	нm
частота

На 3-м шаге будет получена следующая таблица.

Буква	е(нm)	аи
частота

На 4-м шаге будет получена следующая таблица.

Буква	аи(о)	е(нm)
частота

На последнем шаге получаем (аи(о))(е(нm)).

После этого строим дерево кодирования. Припишем первой компоненте последнего объединения символ 0, а второй компоненте символ 1. Продолжаем этот процесс до тех пор, пока все исходные знаки не будут закодированы.

0 (аи)

0 (аи)о

0 1 о

е

1 (е)нm 1 0

1 (нm)

0 а

0 1 и

0 1 о

е

1 0 н

1 0

1 m

Получаем таблицу кодирования.

Буква	a	и	о	E	н	m
частота

Пример 2. Кодируем слово «енот» по таблице примера 1.

Решение. Так как по таблице кодирования е=10, н=110, о=01, m=111, то слово «енот» кодируется последовательностью 1011001111.

Пример 3. Декодируем по дереву сообщение 1100101111.

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

Оставшаяся часть сообщения – это 0101111. Двигаемся по дереву кодирования из корня. Первый символ в последовательности 0101111 равен 0, поэтому идем по верхней ветви. Второй символ равен 1, поэтому по нижней ветви и получаем букву о.

Оставшаяся часть сообщения – это 01111. Символы 01 дают букву о. а символам 111 соответствует буква m.

Декодированное сообщение нооm.

Код Хаффмана широко используется в кодировании изображений.

Блочный код определяется двумя функциями К: и

Д: ; К – функция кодирования, Д – функция декодирования. Если Т – функция ошибок, то К, Д, Т выбираются так, что бы композиция с большой вероятностью была близка к тождественной. Двоичный код имеет 2ⁿ кодовых слов.

Коды делятся на коды с обнаружением ошибок и коды с исправлением ошибок.

Рассмотрим, н-р, код с тройным повторением. Функция К определяется так: каждое сообщение разбивается на блоки длины m, каждый передается трижды. Функция Д определяется след образом: полученное сообщение разбивается на блоки длины 3m и в каждом блоке из трех символов выбирается 0 или 1 в зависимости от того, какой встречается больше раз (два или три раза).

На мн-ве двоичных слов длины m расстоянием Хемминга между словами

наз-ся число несовпадающих позиций этих слов. Н-р, расстояние между словами равно 2.

Аксиомы расстояний

2.

3.

Утверждения: 1. Для того чтобы код позволял исправлять ошибки не более чем в k позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами удовлетворяло условию:

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

Рассм. Н-р, (2, 3) код с проверкой четности. Мн-во кодовых слов: 110, 011, 101,000. Минимальное расстояние между кодовыми словами 2. След-но, этот код может обнаружить однократную ошибку.

Более экономичным способом описания схемы кодирования является матричный.

Пусть - матрица порядка , элементами которой являются 0 и 1, соответствующая коду, называемая порождающей матрицей кода;

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

Н-р, порождающей матрице кода с повторениями будет матрица , так как

Одним из распространенных видов кодов являются коды Хемминга, исправляющие однократную ошибку; код Хемминга – код, где

Запишем матричное уравнение: . Здесь матрицы М порядка для кода Хемминга (при ) имеют вид

Если принято слово , где е –ошибка, то , так как . Если , то считают, что ошибки нет. Если е имеет 1 в i-й позиции, то в слове с нужно изменить символ b в i-й позиции, и полученное слово будет результатом декодирования. Если единицы есть больше, чем в одной позиции, то результат декодирования неверен.

Н-р, найдем порождающую матрицу для (4, 7) кода Хемминга. Фундаментальная система решений линейных ур-ий, полученных из уравнения , имеет вид: Тогда порождающей является матрица, составленная из этих векторов:

---

Дата добавления: 2015-10-02