Кодирование информации

Равномерные коды
Равномерные коды – все кодовые слова (коды отдельных букв) имеют одинаковую длину.
МАМА МЫЛА ЛАМУ:
000 001 000 001 101 000 010 011 001 101 011 001 000 100
сообщения получаются длинными

Закодируйте свое имя с помощью кодовой таблицы (Windows-1251):

Неравномерные коды
Неравномерные коды – кодовые слова имеют разную длину.
0100010011011011100001110000011010
М
А
М
А
М
Ы
Л
А
А
Л
М
У
Префиксный код – ни одно кодовое слово не совпадает с началом другого кодового слова (условие Фано).

Закодируйте свое имя с помощью азбуки Морзе.
ВАСЯ

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

Декодирование – это восстановление сообщения из последовательности кодов.
МАМА МЫЛА ЛАМУ → 00 1 00 1 11 00 01 0 1 11 0 1 00 10
0010011100010111010010 → ???
ЛЛАЛЛАААЛЛЛАЛАААЛАЛЛАЛ
Приняли сообщение:

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

Лабораторная работа №5
ПОМЕХОУСТОЙЧИВЫЙ КОД ХЭММИНГА
Цель работы: изучение принципов помехоустойчивого кодирования, получение навыков моделирования помехоустойчивых кодов с помощью ElectronicsWorkbench.

ЗАДАНИЕ 1.
Формирование бита чётности
Простейший код, предназначенный для обнаружения одной ошибки (точнее – для обнаружения нечётного числа ошибок), основан на добавлении к информационным битам одного контрольного бита.
При этом контрольный бит должен быть таким, чтобы суммарное число единиц в образованном машинном слове было чётным.
Добавляемый бит называется битом паритета.

Проверочный бит k для n-битного двоичного слова b1b2...bn вычисляется по формуле:

Пример.
Пусть дан байт 10111100.
тогда k=1 и кодовая комбинация равна
101111001

Сформировать бит чётности (бит паритета) для заданного байта передаваемых данных.

ЗАДАНИЕ 2.
Исследование помехоустойчивого кода с формированием бита чётности
Выполнить моделирование процесса передачи информации.

Схема исследований кода с формированием бита паритета

ЗАДАНИЕ 3.
Исправление ошибки с помощью кода Хэмминга
Расчётным путём (вручную) определить, в каком разряде принятого кода Хэмминга произошло искажение. Процесс вычисления искажённого бита следует описать в отчёте.

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

В это время он работал в лаборатории Bell Labs на электромеханической счетной машине Bell Model V.

Идея кода Хемминга заключается в разбиении данных на блоки фиксированной длины и вводе в эти блоки контрольных бит, дополняющих до четности несколько пересекающихся групп, охватывающих все биты блока.
Ричард Хемминг рассчитал минимальное количество проверочных бит, позволяющих однозначно исправлять однократные ошибки.
k=2k – m – 1
m - длина информационного блока;
k - количество контрольных бит.

Рассмотрим пример кодирования бинарной последовательности данных, состоящей из 8 элементов: 10101101.
Определим необходимое количество контрольных разрядов.
k=2k – m – 1
m - длина информационного блока;
k - количество контрольных бит.
k=3
3=23 – 8 – 1, 3>– 1
k=4
4=24 – 8 – 1, 4<7

2. Определим расположение проверочных бит в результирующей закодированной последовательности.
Обозначим информационные биты символом ИБ, а контрольные биты символом КБ.
Контрольные биты будут занимать четыре позиции с порядковыми номерами, равными степени двойки: 20, 21, 22, 23 => 1,2,4,8.

3. Определим, какие группы контролируют проверочные биты.
ИБ3: 3 = 20 + 21 = 1 + 2 => информационный бит проверяется контрольными битами 1 и 2.
ИБ5: 5 = 20 + 22 = 1 + 4 => Информационный бит проверяется контрольными битами 1 и 4.
ИБ6: 6 = 21 + 22 = 2 + 4 => Информационный бит проверяется контрольными битами 2 и 4.

ИБ7: 7 = 20 + 21 + 22 = 1 + 2 + 4 => Информационный бит проверяется контрольными битами 1, 2 и 4.
ИБ9: 9 = 20 + 23 = 1 + 8 => Информационный бит проверяется контрольными битами 1 и 8.
ИБ10: 10 = 21 + 23 = 2 + 8 => Информационный бит проверяется контрольными битами 2 и 8.
ИБ11: 11 = 20 + 21 + 23 = 1 + 2 + 8 => Информационный бит проверяется контрольными битами 1, 2 и 8.
ИБ12: 12 = 22 + 23 = 4 + 8 => Информационный бит проверяется контрольными битами 4 и 8.

4. Рассчитаем значения контрольных бит.
Для этого определим группы для всех контрольных бит, а результат запишем в соответствующие контрольные биты:
KБ1 = ИБ3 ⊕ ИБ5 ⊕ ИБ7 ⊕ ИБ9 ⊕ ИБ11 =
= 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 0
КБ2 = ИБ3 ⊕ ИБ6 ⊕ ИБ7 ⊕ ИБ10 ⊕ ИБ11=
= 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 = 0
КБ4 = ИБ5 ⊕ ИБ6 ⊕ ИБ7 ⊕ ИБ12 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1
КБ8 = ИБ9 ⊕ ИБ10 ⊕ ИБ11 ⊕ ИБ12 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0

Итоговая кодовая комбинация

Рассмотрим пример нахождения искажённого бита с помощью кода Хэмминга.
Места расположения информационных битов (ИБ) и контрольных битов (КБ) в передаваемых данных указаны в таблице.

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

Вычислим значения контрольных битов на приёме.
Расчёт производится по формулам:
KБ’1 = ИБ3 ⊕ ИБ5 ⊕ ИБ7 ⊕ ИБ9 ⊕ ИБ11 =
= 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 0
КБ’2 = ИБ3 ⊕ ИБ6 ⊕ ИБ7 ⊕ ИБ10 ⊕ ИБ11=
= 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 = 1
КБ’4 = ИБ5 ⊕ ИБ6 ⊕ ИБ7 ⊕ ИБ12 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1
КБ’8 = ИБ9 ⊕ ИБ10 ⊕ ИБ11 ⊕ ИБ12 = 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1

Контрольные биты, сформированные на передающей и приёмной сторонах, различаются:
КБ1 = КБ’1 = 0 = 0, КБ2 = КБ’2 = 0 ≠ 1,
КБ4 = КБ’4 = 1 = 1, КБ8 = КБ’8 = 0 ≠ 1,
Для определения неверно принятого бита требуется вычислить так называемый синдром S=s8s4s2s1, где
s1= ИБ1 ⊕ ИБ’1= 0 ⊕ 0 = 0,
s2= ИБ2 ⊕ ИБ’2= 0 ⊕ 1 = 1,
s4= ИБ4 ⊕ ИБ’4= 1 ⊕ 1 = 0,
s8= ИБ8 ⊕ ИБ’8= 0 ⊕ 1 = 1.

Переведём синдром S=1010 из двоичной системы счисления в десятичную S=1*23+0*22+1*21+0*20=10.
Десятичное число 10 говорит о том, что десятый разряд принятых данных (b6) искажён, и этот бит нужно исправить (проинвертировать).
Таким образом, после корректировки принятые данные будут иметь вид, показанный в таблице.

ЗАДАНИЕ 4.
Моделирование работы кода Хэмминга
На передающей стороне формируются контрольные биты.
На приёмной стороне вычисляется синдром.
Имитатор помех позволяет исказить любой бит данных, передаваемых по каналу связи.

Пример схемы передающей стороны

Пример схемы канала связи

Пример схемы принимающей стороны

Семисегментный индикатор