Кодирование информации
<<  Примеры кодирования информации Сериализация  >>
Помехоустойчивое кодирование
Помехоустойчивое кодирование
Предположения
Предположения
Исходная стратегия декодирования
Исходная стратегия декодирования
Расстояние Хэмминга
Расстояние Хэмминга
Свойства расстояния Хэмминга
Свойства расстояния Хэмминга
Свойства расстояния
Свойства расстояния
Кодирование
Кодирование
Систематическое кодирование
Систематическое кодирование
Введение избыточности
Введение избыточности
Линейное систематические кодирование
Линейное систематические кодирование
Пример линейного систематического кодирования
Пример линейного систематического кодирования
Линейный код
Линейный код
Примеры
Примеры
Недвоичный код
Недвоичный код
Обнаружение одиночной ошибки
Обнаружение одиночной ошибки
Обнаружение ошибки перестановки
Обнаружение ошибки перестановки
Добавление проверки на четность
Добавление проверки на четность
Порождающая матрица
Порождающая матрица
Систематический код
Систематический код
Длина слов
Длина слов
Проверки
Проверки
Проверочная матрица
Проверочная матрица
Связь порождающей и проверочной матрицы
Связь порождающей и проверочной матрицы
Матрицы систематического кода
Матрицы систематического кода
Сводка результатов по линейным кодам
Сводка результатов по линейным кодам
Презентация «Помехоустойчивое кодирование». Размер 132 КБ. Автор: Billy Gates.

Загрузка...

Помехоустойчивое кодирование

содержание презентации «Помехоустойчивое кодирование.ppt»
СлайдТекст
1 Помехоустойчивое кодирование

Помехоустойчивое кодирование

Помехоустойчивое кодирование. Линейные коды.

2 Предположения

Предположения

Некоторые предположения. Блоковый код- код, в котором все слова имеют одинаковую длину. Кодовое слово – слово из некоторого кода С. Исходные предположения относительно канала 1. Сохранение длины. Слово на выходе канала имеет такую же длину, как кодовое слово на входе канала. 2. Независимость ошибок. Вероятность ошибки любого символа сообщения одна и та же.

3 Исходная стратегия декодирования

Исходная стратегия декодирования

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

4 Расстояние Хэмминга

Расстояние Хэмминга

Расстояние Хэмминга. Интуитивное понятие “близости'' двух слов формализуется с помощью расстояния Хэмминга d(x, y) слов x, y. Для двух слов x, y d(x, y) = число символов, в которых они различаются. Примеры: h(10101, 01100) = 3, h(fourth, eighth) = 4.

5 Свойства расстояния Хэмминга

Свойства расстояния Хэмминга

Свойства расстояния Хэмминга (1). (1) d(x, y) = 0 ? x = y (2) d(x, y) = d(y, x) (3) d(x, z) ? d(x, y) + d(y, z) (неравенство треугольника) Важнейшей характеристикой кодаC является его минимальное расстояние d(C) = min {d(x, y) | x,y ? C, x ? y}, d (C) дает наименьшее число ошибок, необходимое для перевода одного кодового слова в другое.

6 Свойства расстояния

Свойства расстояния

Свойства расстояния Хэмминга (2). Теорема (Основная теорема исправления ошибок) (1) Код C может обнаруживать до s ошибок, если d(C) ? s + 1. (2) Код C может исправлять до t ошибок, если d(C) ? 2t + 1. Доказательство (1) Очевидно. (2) Предположим d(C) ? 2t + 1. Пусть передается кодовое слово x и получено слово y так что d(x, y) ? t. Если x' ? x является кодовым словом, тогда d(x' ‚ y) ? t + 1 поскольку в противном случае d(x', y) < t + 1 и следовательно d(x, x') ? d(x, y) + d(y, x') < 2t + 1 что противоречит предположению d(C) ? 2t + 1.

7 Кодирование

Кодирование

Кодирование – введение избыточности –алгебраический подход. Кодер.

8 Систематическое кодирование

Систематическое кодирование

Систематическое кодирование. Кодер.

9 Введение избыточности

Введение избыточности

Кодирование – введение избыточности (систематическое кодирование).

10 Линейное систематические кодирование

Линейное систематические кодирование

Линейное систематические кодирование – линейные функции.

11 Пример линейного систематического кодирования

Пример линейного систематического кодирования

Пример линейного систематического кодирования - добавление проверки на четность(1). Пример. Информационное слово. Кодовое слово. 000. 0000. 001. 0011. 010. 0101. 011. 0110. 100. 1001. 101. 1010. 110. 1100. 111. 1111.

12 Линейный код

Линейный код

Линейный код (некоторые параметры) - (n,k,d)-код. n – длина кодовых слов (длина кода) k – число информационных разрядов d – минимальное кодовое расстояние - скорость передачи Комментарий: Хороший (n,k,d)-код имеет маленькое n и большие k и d.

13 Примеры

Примеры

Примеры. C1 = {00, 01, 10, 11} есть (2,2,1)-код. C2 = {000, 011, 101, 110} есть (3,2,2)-код. C3 = {00000, 01101, 10110, 11011} есть (5,2,3)-код.

14 Недвоичный код

Недвоичный код

Isbn-код – недвоичный код. Каждая книга имеет International Standard Book Number, которое представляет собой 10-разрядное кодовое слово создаваемое издателем и имеющее следующую структуру: l p m w = x1 … x10 язык издатель номер взвешенная контрольная сумма 0 07 709503 0 так что Издатель добавляет X в 10-ю позицию, если x10 = 10. The ISBN code is designed to detect: (a) any single error (b) any double error created by a transposition.

15 Обнаружение одиночной ошибки

Обнаружение одиночной ошибки

Isbn-код – недвоичный код. Обнаружение одиночной ошибки Пусть X = x1 … x10 - правильный код и пусть Y = x1 … xJ-1 yJ xJ+1 … x10 , причем yJ = xJ + a, a ? 0 В таком случае:

16 Обнаружение ошибки перестановки

Обнаружение ошибки перестановки

Isbn-код – недвоичный код. Обнаружение ошибки перестановки. Пусть xJ и xk поменялись местами.

17 Добавление проверки на четность

Добавление проверки на четность

Пример линейного систематического кодирования - добавление проверки на четность(2). Пример. Информационное слово. Кодовое слово. 000. 0000. 001. 0011. 010. 0101. 011. 0110. 100. 1001. 101. 1010. 110. 1100. 111. 1111.

18 Порождающая матрица

Порождающая матрица

Порождающая матрица. Пусть - кодовое слово длины n - информационное слово длины k G – nxk порождающая матрица кода.

19 Систематический код

Систематический код

Систематический код. Первые разрядов кодового слова совпадают с информационными битами.

20 Длина слов

Длина слов

Порождающая матрица. Пример. Длина слов n=7, число иформационных разрядов =4, число проверочных разрядов n-k=3.

21 Проверки

Проверки

Проверки. Пример. Получаем проверки.

22 Проверочная матрица

Проверочная матрица

Проверочная матрица. Пример. H – (n-k)xn проверочная матрица:

23 Связь порождающей и проверочной матрицы

Связь порождающей и проверочной матрицы

Связь порождающей и проверочной матрицы систематического кода. Пример.

24 Матрицы систематического кода

Матрицы систематического кода

Связь порождающей и проверочной матрицы систематического кода.

25 Сводка результатов по линейным кодам

Сводка результатов по линейным кодам

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

«Помехоустойчивое кодирование»
Сайт

5informatika.net

115 тем
5informatika.net > Кодирование информации > Помехоустойчивое кодирование.ppt