Помехоустойчивое кодирование Линейные коды. Некоторые предположения Блоковый код- код, в котором все слова имеют одинаковую длину. Кодовое слово – слово.

Презентация:



Advertisements
Похожие презентации
Помехоустойчивое кодирование Вероятность ошибочного декодирования.
Advertisements

Помехоустойчивое кодирование Основные идеи. Литература Алгебраическая теория кодирования Автор: Берлекэмп Э. Издательство: Мир Год: 1971 Теория кодов,
Помехоустойчивое кодирование Циклические коды – подкласс линейных кодов.
Практическая работа 1 4 Теория информации. Теоретическая подготовка Подготовьте ответы на вопросы: В чём заключается сущность помехоустойчивого кодирования?
Помехоустойчивое кодирование Свойства линейных кодов.
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ Презентация лекции по курсу «Общая теория связи» © Д.т.н., проф. Васюков В.Н., Новосибирский государственный.
Исходная информация Информация и искажениями Сообщение с искажениями Сообщение Кодирование Шум Канал связи Декодирование.
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ Федеральное государственное образовательное учреждение Среднего профессионального образования по Владимирской области «Гусевский.
Применение теории кодирования в криптографии Лось Антон Васильевич.
Сжатие данных и помехозащищенное кодирование Лямин Андрей Владимирович.
ГБОУ Гимназия 1505 «Московская городская педагогическая гимназия – лаборатория» автор: Редченко Дмитрий, 10 класс «Б» руководитель: Г.А.Пяткина 2013 г.
Построение матрицы блока турбокода в процессе кодирования. Подготовил: студент группы КЭ-223 Савин И.А. Проверил: доцент кафедры ИКТ Спицын В.С.
Обнаружение одиночных ошибок. Исправление одиночных или обнаружение двойных ошибок. Адхамов З.Ш N3200.
КОДИРОВАНИЕ ИНФОРМАЦИИ Информационные технологии, доц. Колыбанов К.Ю.
Устройства хранения информации Кэш - память Основная память Магнитный (жесткий) диск Регистры Оптические носителиМагнитные носители.
Задача декодирования линейных кодов и некоторые применения помехоустойчивого кодирования.
Системы мобильной связи Лекция 14 Канальное кодирование в стандарте GSM. Принцип кодирования канала трафика. Турбокоды: определение, принцип формирования.
Системы с несколькими конвейерами В процессорах Intel конвейер появился только начиная с 486 модели. Но уже в Pentium-е было два конвейера из 5 стадий:
Обзор современных методов помехоустойчивого кодирования д. т. н. В. В. Золотарёв.
1 ЭФФЕКТИВНОЕ МНОГОПОРОГОВОЕ ДЕКОДИРОВАНИЕ НЕДВОИЧНЫХ САМООРТОГОНАЛЬНЫХ КОДОВ 1 Институт космических исследований 2 Рязанский государственный радиотехнический.
Транксрипт:

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

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

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

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

Свойства расстояния Хэмминга (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) дает наименьшее число ошибок, необходимое для перевода одного кодового слова в другое.

Свойства расстояния Хэмминга (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.

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

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

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

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

Пример линейного систематического кодирования - добавление проверки на четность(1) Пример. Информацио нное слово Кодовое слово

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

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

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

ISBN-код – недвоичный код Обнаружение одиночной ошибки Обнаружение одиночной ошибки Пусть X = x 1 … x 10 - правильный код и пусть Y = x 1 … x J-1 y J x J+1 … x 10, причем y J = x J + a, a 0 В таком случае:

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

Пример линейного систематического кодирования - добавление проверки на четность(2) Пример. Информа ционное слово Кодовое слово

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

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

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

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

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

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

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

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