Эффективное кодирование
Эффективное кодирование – это процедуры направленные на устранение избыточности.
Основная задача эффективного кодирования – обеспечить, в среднем, минимальное число двоичных элементов на передачу сообщения источника. В этом случае, при заданной скорости модуляции обеспечивается передача максимального числа сообщений, а значит максимальная скорости передачи информации.Пусть имеется источник дискретных сообщений, алфавит которого K. При кодировании сообщений данного источника двоичным, равномерным кодом, потребуетсяLpk=log2K двоичных элементов на кодирование каждого сообщения.
Если вероятностиP(ai) появления всех сообщений источника равны, то энтропия источника (или среднее количество информации в одном сообщении) максимальна и равнаHmax(x)= log2K.
В данном случае каждое сообщение источника имеет информационную емкостьlog2K=Lpk бит, и очевидно, что для его кодирования (перевозки) требуется двоичная комбинация не менее Lpkэлементов. Каждый двоичный элемент, в этом случае, будет переносить 1 бит информации.
Если при том же объеме алфавита сообщения не равновероятны, то, как известно, энтропия источника будет меньше
Если
и в этом случае использовать для перевозки
сообщения
-разрядные
кодовые комбинации, то на каждый двоичный
элемент кодовой комбинации будет
приходиться меньше чем 1 бит.
Появляется
избыточность, которая может быть
определена по следующей формуле
Среднее количество информации, приходящееся на один двоичный элемент комбинации при кодировании равномерным кодом
Корректирующее кодирование
Корректирующие коды делятся на блочные и непрерывные к блочным относятся коды, в которых каждому символу алфавита соответствует блок (кодовая комбинация) из n (i) элементов, где i – номер сообщения. Если n (i) = n, т.е. длина блока постоянна и не зависит от номера сообщения, то код называется равномерным. Такие коды чаще применяются на практике. Если длина блока зависит от номера сообщения, то такой код называется неравномерным. В непрерывных кодах передаваемая информационная последовательность не разделяется на блоки, а проверочные элементы размещаются в определенном порядке между информационными.
Корректирующие коды позволяют получить и обнаружить ошибку.
Рисунок 2 – Множество кодовых комбинаций.
Расстояние Хемминга так же используется в корректирующих кодах.
Расстояние - это минимальное расстояние Хемминга между всеми парами разрешенных комбинаций.
Код Хемминга – код с расстоянием 3 и 4.
Решение задач
Задача№1.
Вычислить число архив и необходимое число разрядов для его передачи для алфавита {A} cвероятностями {p}, если передавалась соответствующая последовательность.
Дано:
|
Ai |
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
|
Pi |
0,32 |
0,06 |
0,14 |
0,16 |
0,02 |
0,15 |
0,05 |
0,1 |
|
|
|
|
|
|
|
|
|
|
Изобразим интервалы на единичной прямой:
Рисунок 3 – Вероятностные интервалы сообщений на прямой
Передается: 6346 = a6a3a4a6
Решение:
–нижняя
граница интервала
–верхняя
граница интервала
Где i – номер в исходном алфавите, j–номер в блоке.
a6: 
a3: 
a4: 
a6: 
Найдем середину последнего масштабированного интервала, т.е. число архив:
Вычислим количество разрядов, необходимых для представления числа архива в двоичном виде:
Ответ:
число
архив
10=0,10011100100111012
Задача№2. Нарисовать кодирующее устройство и сформировать разрешенную кодовую комбинацию циклического кода, если задан производящий полином P(x) и кодовая комбинация, поступающая от источника сообщений Q(x). Показать содержимое ячеек памяти кодера на каждом такте.
Дано:
,
Решение:
Сначала аналитически определим разрешенную кодовую комбинацию, соответствующую данной информационной.
Запишем
комбинацию
в
виде полинома:
Далее действуем по алгоритму:
1.
, гдеr–максимальная
степень производящего полинома.
2. Делим полученное выражение на образующий полином.
3.
Полученный остаток прибавляем к
:
,
что в двоичном виде соответствует
комбинации 10011011001–это разрешенная
кодовая комбинация.
Для построения кодера необходимо: четыре ячейки памяти (r=4), три сумматора (r-1=4-1=3). Схема кодера приведена на рисунке 3. В таблице приведенной ниже показаны состояния ячеек памяти кодера на каждом такте.
Правила:
1) Число ячеек памяти равно степени образующего полинома, т.е. r.
2) Число сумматоров на 1 меньше веса образующего полинома.
3) Сумматор ставится после тех ячеек, начиная с нулевой (её на схеме нет), для которых существует соответствующий ненулевой член в полиноме. После ячейки, соответствующей старшему разряду, сумматор не ставится.
Рисунок4 – Схема кодера.
Таблица 1 – Таблица состояний кодера.
|
№такта |
Вход |
№ ячейки ФПГ |
№ ячейки РЗ |
Выход |
Положение ключей | ||||||
|
1 |
2 |
3 |
4 |
1 |
2 |
3 |
4 |
К1в положении 2 К2разомкнут | |||
|
0 |
- |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
- | |
|
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
- | |
|
2 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
- | |
|
3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
- | |
|
4 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
- | |
|
5 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
К1в положении 1 К2замкнут |
|
6 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 | |
|
7 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 | |
|
8 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 | |
|
9 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 | |
|
10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 | |
|
11 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 | |
|
12 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 | |
|
13 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 | |
|
14 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 | |
|
15 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 | |
|
16 |
0 |
0 |
1 |
1 |
1 |
- |
- |
- |
- |
1 |
К1в положении 2 К2разомкнут |
|
17 |
0 |
0 |
0 |
1 |
1 |
- |
- |
- |
- |
1 | |
|
18 |
0 |
0 |
0 |
0 |
1 |
- |
- |
- |
- |
1 | |
|
19 |
0 |
0 |
0 |
0 |
0 |
- |
- |
- |
- |
1 | |
В начальный момент времени ключ K1 в положении 2, ключ K2 разомкнут. Три такта идёт заполнение ячеек ФПГ и РЗ. После третьего такта ключи меняют своё положение, информационные элементы уходят в канал, а в ФПГ идёт деление на образующий полином. На 11 такте деление закончилось, ключи меняют своё положение. После 11 такта проверочные символы уходят в канал, а в это время можно начинать передавать следующую информационную комбинацию.
Задача №3. Нарисовать декодирующее устройство циклического кода с исправлением однократной ошибки. Определить наличие ошибки в кодовой комбинации циклического кода, если задан производящий полином P(x) (взять из задачи 2 главы 1) и кодовая комбинация, поступающая на вход декодера.
Дано:
,
Решение:
Определим наличие ошибок в кодовой комбинации циклического кода:
Шаг 1. Делим вектор ошибки, соответствующий старшему разряду на образующий полином
Получили
остаток
Шаг 2. Делим принятую КК на образующий полином
Так
как R0(x)≠Rx
то ошибки в первом разряде нет.
Шаг 3. Будем повышать степень на 1 и продолжать деление пока Rx не совпадёт с R0(x)
Делаем вывод, что ошибка в 10 разряде.
|
|
Ну почему составители задачи сделали ошибку аж в 10 разряде??? Я устал пока досчитал. |
Изобразим декодирующее устройство циклического кодас исправлением однократной ошибки:
Рисунок 5 – Схема декодера.