Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
4.Проблема кодирования. Однозначность декодирования. Коды Хэмминга.
В широком смысле слова под кодированием понимают сопоставление элементам множества 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 разряда.
Построение кода Хэмминга.
Построение кода Хэмминга происходит в несколько этапов.
I. Нахождение числа k контрольных разрядов.
При передаче кода , очевидно, возможны следующие варианты получения кодов на выходе канала связи (рис.2.15).
Первый вариант сообщения на выходе канала связи не содержит искажений, остальные – по одному искажению разряда. Таким образом, число вариантов равно .
Количество k контрольных разрядов в коде сообщения определяется таким образом, чтобы по их содержимому можно было однозначным образом определить, какой разряд сообщения искажен, т.е. в каком из вариантов передано сообщение.
Содержимое контрольных разрядов – двоичное слово длины k. Для однозначного соответствия этим словам различных вариантов передачи сообщения, очевидно, должно выполняться условие:
|
(2.6) |
Отсюда определяется k как наименьшее целое, удовлетворяющее этому условию . Преобразуем неравенство (2.6). Учитывая, что и подставляя разность в (2.6), получаем
|
(2.7) |
Отсюда при известном значении m можно выбрать как наименьшее целое, удовлетворяющее (2.7), а затем вычислить . Ясно, что при этом должна быть уверенность, что передача кода длины l не вызовет искажения более одного разряда.
II. Выделение из отрезка натуральных чисел k последовательностей.
Пусть V–натуральное число из отрезка и – его двоичная запись, т.е. . Поскольку число изображается в двоичной системе счисления записью 10…0, содержащей 1 только в - м разряде, то отсюда и из условия (1.6) следует, что любое число из отрезка в двоичном представлении имеет не более k разрядов.
1) В первую последовательность включим все натуральные числа V из отрезка , в двоичном представлении которых первый разряд равен 1, т.е. . Этими числами являются
|
1 , |
2 , |
5 , |
7 , |
9 ,…. |
|
1 |
11 |
101 |
111 |
1001 |
Нижняя строка содержит двоичные числа указанных чисел.
2) Во вторую последовательность включаются все числа V , второй разряд, равный 1, т.е. :
|
2 , |
3 , |
6 , |
7 , |
10 ,…. |
|
10 |
11 |
110 |
111 |
1010 |
3) В третью последовательность включаются числа с :
|
4 , |
5 , |
6 , |
7 , |
12 ,…. |
|
100 |
101 |
110 |
111 |
1100 |
………………………………………………………………..
k) B k-последовательности все числа имеют
|
2 k-1 , |
2 k-1 +1 ,… |
|||
|
10…00 |
10…01 |
Первыми членами этих последовательностей являются степени двойки:. Те разряды набора , у которых индекс I является степенью двойки, являются контрольными, остальные – информационными. Контрольных разрядов будет ровно k, информационных .
III. Определение содержимого информационных разрядов.
В информационные разряды (разряды с номерами, не являющимися степенью двойки) записываются последовательно двоичные символы сообщения :
и т. д.
IV. Определение содержимого контрольных разрядов.
Содержимое контрольных разрядов определяется по формулам:
|
(2.8) |
Таким образом, есть сумма по модулю 2 содержимого всех разрядов с номерами, принадлежащим первой последовательности, кроме ее первого члена, есть аналогичная сумма по второй последовательности и т. д.
Все разряды, указанные в правой части равенств являются информационными. Их содержимое определено ранее.
По сути, каждое равенства (2.6) задают код с проверкой на четность для каждой выделенной последовательности кроме ее первого элемента, а значение контрольной суммы записывается не в последний, а в первый разряд каждой последовательности.
В этом случае проверочными соотношениями являются:
|
(2.9) |
Первое равенство в (2.9) получается из первого равенства (2.8), если прибавить по модулю 2 слева и справа элемент , второе — получается из второго равенства в (2.8), если прибавить слева и справа и т. д.
Пример 1. Пусть известно, что l=7.
I. Из (2.6) получим, что k=3, а m=l-k=4. Определим, какой код будет
иметь, например, сообщение .
II. Получим три последовательности:
1, 3, 5, 7 — первая последовательность,
2, 3, 6, 7 — вторая последовательность,
4, 5, 6, 7 — третья последовательность.
III. Заполняем информационные разряды коды (рис.2.16)
|
1 |
0 |
0 |
1 |
|||
|
Рис.2.16 |
IV. Определяем содержимое контрольных разрядов согласно (2.8):
– суммирование по первой найденной
последовательности,
– суммирование по второй найденной
последовательности
– суммирование по третьей найденной
последовательности
Заполняя контрольные разряды, получаем код (рис. 2.17).
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
|
Рис.2.17 |
Пример 2. Определим код Хэмминга для слова .
II. Выделенные последовательности имеют вид:
1, 3, 5, 7, 9 – первая последовательность,
2, 3, 6, 7 – вторая последовательность,
4, 5, 6, 7 – третья последовательность,
8,9 – четвертая последовательность.
III. После заполнения информационных разрядов имеем (рис.2.18):
|
0 |
1 |
1 |
1 |
0 |
||||
Рис.2.18 |
IV. Подсчитываем содержимое контрольных разрядов:
После заполнения контрольных разрядов имеем код .
Обнаружение ошибки в коде Хэмминга.
Пусть по каналу связи передавался код , на выходе канала связи было принято слово, т.о. произошло искажение s-го разряда. Заметим, что s может быть номером как информационного, так и контрольного разряда. Пусть – запись числа S в двоичной системе исчисления. Сформируем число , двоичные разряды которого вычисляются следующим образом:
есть сумма по модулю 2 содержимого всех разрядов кода на выходе канала связи с номерами, принадлежащими первой последовательности, включая ее первый элемент. При подсчетеаналогичное суммирование ведется по 2,…,k-й последовательности.
Теорема. Число является номером искаженного разряда, т.е..
Доказательство. Покажем, что числа равны, потому что поразрядно равны их двоичные представления, т.е. для всех .
Пусть . Т.к. в первую последовательность включаются числа, имеющие в двоичном представлении первый разряд, равный 1, то это означает, что S не принадлежит первой последовательности. Это означает также, что все разряды кода с номерами, принадлежащими первой последовательности, не искажены, поэтому получим
, т.к. для разрядов Хэмминга выполняется (2.8). Таким образом, из того, что следует . Пусть теперь , тогда номер S искаженного разряда принадлежит первой последовательности. Т.к. искаженный разряд кода есть и, получим:
Получим, что из того, чтоследует . Тогда .
Аналогично доказывается, что .
Замечание. Если при передаче кода нет искажений, то . После определения номера S в том случае, когда , производится коррекция ошибки, т.е. заменяется на .
Пример 3. Пусть на вход канала связи поступил код и в нем в результате помех был искажен 6-ой разряд, т.е. на выходе канала связи был получен код . Убедимся, что по коду можно вычислить номер искаженного разряда. Поскольку , то согласно неравенству (2.6) находим , тогда . Вычислим
Следовательно, в двоичной системе счисления, т.е. . Т.к., то 6 – номер искаженного разряда. После этого, заменяя в 6-ом разряде 0 на 1, получим код .
Пример 4. Пусть на выходе канала связи получен код . Определим, было ли искажение при передаче, и если да, то в каком разряде. Т.к. , то из (2.6) получаем . Тогда
Таким образом, , т.е. код был передан без искажений.
Декодирование.
Декодирование состоит в построении исходного сообщения по коду . Для этого из кода извлекается содержимое информационных разрядов.
Пример 5. Для кода информационными являются разряды 3, 5, 6, 7, остальные – контрольные. Отсюда .
Пример 6. Для кода информационные разряды – 3, 5, 6, 7, 9. Отсюда .
A*
B*
C
сообщение
на выходе КС
код сообщения
на выходе КС
код
сообщения
сообщение
Кодер
Канал связи (КС)
Декодер. Корректировка
кода
помехи
Рис.2.2
Сообщение
на входе канала
связи
Сообщение
на выходе канала связи