Код с проверкой на четность. Итеративный код. Код с удвоением элементов. Инверсный код. Код Шеннона-Фано. Код Хаффмена

Июль 27, 2022

Главная
Информатика
Код с проверкой на четность. Итеративный код. Код с удвоением элементов. Инверсный код. Код Шеннона-Фано. Код Хаффмена

Содержание

2. 2 Код с проверкой на четность ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Алгоритм кодирования. Выполняется суммирование по модулю 2
3. 3 Код с проверкой на четность ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
4. 4 Код с проверкой на четность ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
5. 5 Код с проверкой на четность ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Выводы: Код способен выполнять обнаружение ошибок нечетной
6. 6 Итеративный код ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Алгоритм кодирования. Исходная кодовая комбинация разбивается на отдельные блоки равной
7. 7 Итеративный код ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Общее уравнение кодирования Исходная комбинация Разбивка на блоки и запись
8. 8 Итеративный код ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Уравнение кодирования по строкам Уравнение кодирования по столбцам Результирующая матрица
9. 9 Итеративный код ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Пример. Исходная комбинация Матрица итеративного кода Результирующая комбинация
10. 10 Итеративный код ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Искажение
11. 11 Итеративный код ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Выводы: Код способен выполнять обнаружение и исправление ошибок кратности 1
12. 12 Код с удвоением элементов ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Метод кодирования с удвоением элементов характеризуется наличием дополнительного
13. 13 Код с удвоением элементов ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Характеристики кода: Код не исправляет ошибки, приводящие к
14. 14 Инверсный код ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ В основе метода лежит повторение кодовой комбинации. Если исходная комбинация
15. 15 Инверсный код ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Пример.
16. 16 Код Шеннона-Фано ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Алгоритм кодирования. Все символы алфавита упорядочиваются в порядке убывания вероятности
17. 17 Код Шеннона-Фано ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Пример.
18. 18 Код Хаффмана ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ Алгоритм кодирования. Все символы алфавита упорядочиваются в порядке убывания их
20. Скачать презентацию

Слайд 2

2
Код с проверкой на четность
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Алгоритм кодирования.
Выполняется суммирование по модулю

2 разрядов, образующих код.
Вместе с информационной частью кода передается один контрольный разряд. Его значений «0» или «1» выбирается с условием, чтобы сумма цифр в предаваемом коде была равна 0 по модулю 2 (для случая четности) или 1 (для случая нечетности). Допускается что может возникнуть только одна ошибка.
Алгоритм декодирования.
Вычисляется сумма по модулю 2 всех разрядов с учетом контрольного.
Если результат проверки равен 0, ошибок в кодовой комбинации не найдено. В противном случае – в коде присутствует ошибка.

Слайд 3

3
Код с проверкой на четность
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ

Слайд 4

4
Код с проверкой на четность
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ

Слайд 5

5
Код с проверкой на четность
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Выводы:
Код способен выполнять обнаружение ошибок

нечетной кратности.
Избыточность кода минимальна.
Помехоустойчивые характеристики минимальны.

Слайд 6

6
Итеративный код
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Алгоритм кодирования.
Исходная кодовая комбинация разбивается на отдельные блоки

равной длины. При невозможности сформировать такие блоки допускается дополнить недостающие разряды нулями.
Полученные блоки помещаются в матрицу (как правило используется квадратная матрица).
Для каждого блока вычисляется контрольный разряд по правилу суммирования по модулю 2. Суммирование выполняется по строкам и столбцам. Полученные кодовые разряды помещаются в конце строки или столбца соответственно.
Алгоритм декодирования.
Полученная кодовая комбинация помещается в матрицу.
Выполняется проверка по строками и столбцам, аналогичная кодированию.
Если проверка не выполняется, строка или столбец помечаются.
Искаженные разряды находятся на пересечении помеченных строк и столбцов.

Слайд 7

7
Итеративный код
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Общее уравнение кодирования
Исходная комбинация
Разбивка на блоки и запись

элементов в матрицу

Слайд 8

8
Итеративный код
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Уравнение кодирования по строкам
Уравнение кодирования по столбцам
Результирующая матрица

Слайд 9

9
Итеративный код
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Пример.
Исходная комбинация
Матрица итеративного кода
Результирующая комбинация

Слайд 10

10
Итеративный код
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Искажение

Слайд 11

11
Итеративный код
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Выводы:
Код способен выполнять обнаружение и исправление ошибок кратности

1 - 100% случаев.
Ошибки кратности 2 могут быть обнаружены в 100% случаев.
Код обладает большой избыточностью.
Помехоустойчивые характеристики высокие.

Слайд 12

12
Код с удвоением элементов
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Метод кодирования с удвоением элементов характеризуется

наличием дополнительного символа для каждого информационного символа передаваемого кода.

1 → 10
0 → 01
Показателем искажения являются сочетания типа 00 или 11 в парных элементах.
Код не способен исправлять ошибки, приводящие к двукратным противоположным изменениям разрядов в парных элементах. Помехоустойчивость кода выше, чем кода с проверкой на четность, но существенно возрастает избыточность.

-- Исходная комбинация

-- Закодированная комбинация
-- Комбинация с ошибкой

Основное правило кодирования

Пример:

Слайд 13

13
Код с удвоением элементов
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Характеристики кода:
Код не исправляет ошибки, приводящие

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

Слайд 14

14
Инверсный код
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
В основе метода лежит повторение кодовой комбинации.
Если исходная

комбинация содержит четное число единиц, то повторная комбинации в точности повторяет исходную. Иначе повторение происходит в инверсном виде.

Проверка производится суммированием единиц основной комбинации. Если их число четно, то элементы второй части принимаются в том же виде, после чего обе части комбинации сравниваются поэлементно – первый элемент первой части с первым элементом второй части. При несовпадении хотя бы одного элемента принятая комбинация считается неверной.

Инверсный код позволяет обнаружить практически все ошибки приема-передачи. Не обнаруживается лишь одновременное искажение парных элементов в обеих частях кодовой комбинации.

01010 → 0101001010
11010 → 1101000101

Слайд 15

15
Инверсный код
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Пример.

Слайд 16

16
Код Шеннона-Фано
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Алгоритм кодирования.
Все символы алфавита упорядочиваются в порядке убывания

вероятности их появления.
Кодируемые символы делятся на две равновероятные или приблизительно равновероятные подгруппы.
Каждому символу из верхней подгруппы присваивается код «0», а каждому символу из нижней подгруппы ‒ код «1».
Каждая из подгрупп снова делится на две равновероятные или приблизительно равновероятные подгруппы. При этом каждому символу из верхней подгруппы присваивается код «0», а из нижней ‒ «1».
Деление на подгруппы проводится до тех пор, пока в подгруппе не останется по одному символу.
Результирующие кодовые слова записываются слева направо по кодам подгрупп, соответствующих кодируемому символу. Суммарная вероятность появления символов алфавита должна равняться 1.

Слайд 17

17
Код Шеннона-Фано
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Пример.

Слайд 18

18
Код Хаффмана
ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ
Алгоритм кодирования.
Все символы алфавита упорядочиваются в порядке убывания

их вероятностей появления.
Проводится «укрупнение» символов. Для этого два последних символа «укрупняются» в некоторый вспомогательный символ с вероятностью, которая равняется сумме вероятностей символов, которые были «укрупнены».
Образовавшаяся новая последовательность вновь сортируется в порядку убывания вероятностей с учетом вновь образованного за счет «укрупнения» символа.
Процедура повторяется до тех пор, пока не получится один «укрупненный» символ, вероятность которого равна 1.

Замечание. На практике не используют многократное выписывание символов алфавита и их упорядочивание.

Код с проверкой на четность. Итеративный код. Код с удвоением элементов. Инверсный код. Код Шеннона-Фано. Код Хаффмена

Содержание

2Код с проверкой на четностьОСНОВЫ ТЕОРИИ КОДИРОВАНИЯАлгоритм кодирования.Выполняется суммирование по модулю

3Код с проверкой на четностьОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ

4Код с проверкой на четностьОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ

5Код с проверкой на четностьОСНОВЫ ТЕОРИИ КОДИРОВАНИЯВыводы:Код способен выполнять обнаружение ошибок

6Итеративный кодОСНОВЫ ТЕОРИИ КОДИРОВАНИЯАлгоритм кодирования.Исходная кодовая комбинация разбивается на отдельные блоки

7Итеративный кодОСНОВЫ ТЕОРИИ КОДИРОВАНИЯОбщее уравнение кодированияИсходная комбинацияРазбивка на блоки и запись

8Итеративный кодОСНОВЫ ТЕОРИИ КОДИРОВАНИЯУравнение кодирования по строкамУравнение кодирования по столбцамРезультирующая матрица

9Итеративный кодОСНОВЫ ТЕОРИИ КОДИРОВАНИЯПример.Исходная комбинацияМатрица итеративного кодаРезультирующая комбинация

10Итеративный кодОСНОВЫ ТЕОРИИ КОДИРОВАНИЯИскажение

11Итеративный кодОСНОВЫ ТЕОРИИ КОДИРОВАНИЯВыводы:Код способен выполнять обнаружение и исправление ошибок кратности

12Код с удвоением элементовОСНОВЫ ТЕОРИИ КОДИРОВАНИЯМетод кодирования с удвоением элементов характеризуется

13Код с удвоением элементовОСНОВЫ ТЕОРИИ КОДИРОВАНИЯХарактеристики кода:Код не исправляет ошибки, приводящие

14Инверсный кодОСНОВЫ ТЕОРИИ КОДИРОВАНИЯВ основе метода лежит повторение кодовой комбинации.Если исходная

15Инверсный кодОСНОВЫ ТЕОРИИ КОДИРОВАНИЯПример.

16Код Шеннона-ФаноОСНОВЫ ТЕОРИИ КОДИРОВАНИЯАлгоритм кодирования.Все символы алфавита упорядочиваются в порядке убывания

17Код Шеннона-ФаноОСНОВЫ ТЕОРИИ КОДИРОВАНИЯПример.

18Код ХаффманаОСНОВЫ ТЕОРИИ КОДИРОВАНИЯАлгоритм кодирования.Все символы алфавита упорядочиваются в порядке убывания

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