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

Содержание


Презентации» Информатика» Помехоустойчивое кодирование. Линейные коды
Помехоустойчивое кодирование
 Линейные кодыНекоторые предположения
 Блоковый код- код, в котором все слова имеют одинаковуюИсходная стратегия декодирования 
 При декодировании мы используем принцип максимального правдоподобия,Расстояние Хэмминга
 Интуитивное понятие “близости'' двух слов формализуется с помощью расстоянияСвойства расстояния Хэмминга (1)
 (1) d(x, y) = 0 Ű xСвойства расстояния Хэмминга (2)
 Теорема (Основная теорема исправления ошибок)
 (1) КодКодирование – введение избыточности –алгебраический подходСистематическое кодированиеКодирование – введение избыточности (систематическое кодирование)Линейное систематические кодирование – линейные функцииПример линейного систематического кодирования - добавление проверки на четность(1)
 Пример.Линейный код (некоторые параметры) - (n,k,d)-код
 n – длина кодовых словПримеры
 	C1 = {00, 01, 10, 11} есть (2,2,1)-код.
 	C2 =ISBN-код – недвоичный код
 Каждая книга имеет International Standard Book Number,ISBN-код – недвоичный код
 Обнаружение одиночной ошибки
 Пусть X = x1ISBN-код – недвоичный код
 Обнаружение ошибки перестановкиПример линейного систематического кодирования - добавление проверки на четность(2)
 Пример.Порождающая матрица
 Пусть      - кодовое словоСистематический код
 Первые  разрядов кодового слова совпадают с информационными битамиПорождающая матрица
 
 Пример.       Проверки
 Пример. Получаем проверкиПроверочная матрица
 Пример. 
 
 
 
 
 
 
 HСвязь порождающей и проверочной матрицы систематического кода
 
 Пример.Связь порождающей и проверочной матрицы систематического кодаСводка результатов по линейным кодам
 Линейный код задается порождающей (



Слайды и текст этой презентации
Слайд 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) Пример.

Слайд 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-код – недвоичный код Обнаружение ошибки перестановки

Слайд 17
Описание слайда:
Пример линейного систематического кодирования - добавление проверки на четность(2) Пример.

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

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

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

Слайд 21
Описание слайда:
Проверки Пример. Получаем проверки

Слайд 22
Описание слайда:
Проверочная матрица Пример. H – (n-k)xn проверочная матрица:

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

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

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


Скачать презентацию на тему Помехоустойчивое кодирование. Линейные коды можно ниже:

Похожие презентации