Эффективное кодирование.
Для вопросов 3 и 14 по Вилли
Аналог – величина, в которой информация представлена в значении информационного параметра.
Код (цифра) – сигнал, представляющий собой комбинацию нескольких признаков.
Код – система правил, определяющая принцип комбинаций.
Способы задания кода.
1. Кодовая таблица – дает однозначное соответствие между входной и выходной величиной.
2. Кодовый граф – любые плоские диаграммы, иллюстрирующие свойства кода.
3. Формула.
- позиционный код.
4. Алгоритм. Например, задание кода 8421 или 2421 (определяет алгоритм кодирования).
Унитарные коды.
Унитарный (единичный) код – сигнал, имеющий только один признак.
Унитарная величина
(унитарный код)
Унитарный позиционный сигнал (код) – количество единиц, определяющее наличие информации в разрешенном поле.
N x
Код "1 из N" – унитарный код, представляющий собой полную группу несовместных событий.
Пример: A=1000 (00) C=0010 (10)
B=0100 (01) D=0001 (11)
(это может рассматриваться как декод двоичного кода).
Коды двоичной группы.
Двоичные коды – коды, у которых число информационных признаков сигнала равно двум.
Код 2421 – число возможных комбинаций – 211, так как 11 вершин, в которых происходит разветвление.
Эффективное кодирование.
Опр. Это процесс, позволяющий снизить избыточность.
1. Код Шеннона.
Наиболее часто повторяющиеся комбинации (символы) кодируются более простыми последовательностями.
Выбрали 8-ный ИИ (N=8).
(бита/сообщение)
- способность кода (производительная).
Матрица вероятностей.
,
где ni – длина i-ой комбинации
0≤IСР≤n
Можно считать n=Hmax.
| |
Построение кода Шеннона.
p
| Код Ш.
| 0.729
| 1––––
| 0.081
| 011––
| 0.081
| 010––
| 0.081
| 001––
| 0.009
|
| 0.009
|
| 0.009
|
| 0.001
|
| Алгоритм построения кодовой страницы:
1. Вся группа сигналов разбивается на 2 подгруппы так, чтобы сумма вероятностей в каждой из них была по возможности одинаковой.
2. Полученные группы разделяем по этому же принципу.
Разбиение продолжается до тех пор, пока в каждой группе не останется по одному элементу.
Одной группе присваивается значение единицы, другой – нуля.
Средняя длина последовательности: (фактически это число бит на сообщение).
[бит/символ]
Избыточность ∆N=1–0.47=0.53 для равновероятных событий (pi=0.125=1/8).
Для кода Шеннона и ∆N=0.53–0.47=0.06
Свойства кода Шеннона.
1. Беспрефиксность. Ни одна из более коротких комбинаций не является префиксом более длинной.
2. …
2. Биоковое (биочное) кодирование.
Кодирование осуществляется не по отдельным символам, а по группам символов.
Выбираются пары, для них определяются новые вероятности.
Sy
| Py
| Код
|
| 0.01
|
|
| 0.09
|
|
| 0.09
|
|
| 0.81
|
|
Поиск по сайту:
|