Цифровое кодирование. Сжатие RLE (Run Length Encoding)

1. Цифровое кодирование

2. Сжатие RLE (Run Length Encoding)

Флаг
(1 бит )
Информация о байтах данных
(7 бит)
Формат служебного байта
00 00 00 00 CC BF BB16
Сжимается в…
84 00 03 CC BF BB16
00 00 …. 0016
А8 00 16
40 Нулевых байт сжимаются в…

3.

Дерево Шеннона-Фано
Символ
Частота
ABCDEF (215)
A
B
C
D
E
F
50
39
18
49
35
24
1
ABC (107)
1
0
A (50)
BC (57)
1
C (18)
0
B (39)
0
DEF (108)
0
EF (59)
1
F (24)
1
D (49)
0
E (25)

4.

Дерево Хаффмана
Символ
Pi
A
B
C
D
E
0.3 0.26 0.24 0.11 0.09

5.

Структура систематических кодов
n=k+r
n-общее число разрядов
k-информационные разряды
r-контрольные разряды

6.

Таким образом имееем:
М=
k
q – Количество возможных
информационных сообщений
C=
r
q – Количество возможных
контрольных комбинаций
q – основание СС, используемой
для кодирования

7.

Основное ограничение систематических кодов
n
q /(n+1)
≥М
r
q ≥n+1

8. Порождающая и проверочная матрицы

9. Предупреждение

Излагаемый далее алгоритм
составления порождающих и
проверочных матриц
Не являются единственным.
Возможно также их построение на основе
единичных квадратных матриц k*k

10. Применение порождающей матрицы

MESSAGES_H=MESSAGES * G

11. Применение проверочной матрицы

S=H * MESSAGES_HT

12. Применение проверочной матрицы

Имеются ошибки

13. Расширенные матрицы

14. Расширенный код Хемминга

MESSAGES_HЕ=MESSAGES * GЕ

15. Проверка расширенного кода

SЕ=HE*MESSAGES_HET

16. Есть ошибки расширенного кода