Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Теория кодирования

Содержание

КодыОпределим код как представление множества символов строками, состоящими из единиц и нулей.Это множество символов обычно включает буквы алфавита, цифры и, как правило, определенные контрольные символы. Коды представляются бинарными строками с целью использования их компьютерами для хранения
Теория кодирования КодыОпределим код как представление множества символов строками, состоящими из единиц и нулей.Это КодыЖелательно, чтобы коды обладали некоторыми свойствами. Наиболее важное свойство кода состоит в КодыСуществует несколько способов достижения этой цели. Один из них – кодирование всех Коды  Коды  КодыЧасто необходимо сжимать данные, чтобы минимизировать объем памяти для их хранения или КодыВ кодах Хаффмана и Морзе буквы или символы, которые встречаются наиболее часто, КодыВ коде Морзе буквы разделены КодыВ процессе передачи данных могут возникать ошибки. Все, что может стать причиной КодыВ некоторых случаях интерес представляет только определение наличия ошибки, что соответствует ситуации КодыВ другом случае, когда данные не могут быть переданы еще раз (например, КодыМожет показаться разумным всегда использовать коды с исправлением ошибок. Проблема использования кодов КодыК сожалению, использование кодов с исправлением ошибок и кодов с обнаружением ошибок КодыВ качестве первого метода обнаружения ошибок рассмотрим бит контроля четности.Продемонстрируем этот метод КодыASCII-код является блоковым кодом, который использует 7 битов, поэтому любой закодированный символ КодыК сожалению, если произошло две ошибки, их нельзя будет обнаружить, поскольку количество единиц опять будет четным. Коды  КодыЕсли при кодировании каждая строка повторена один раз, то в результате получаем КодыНапример, если закодированная строка имеет вид 111111010110111011, то ошибки имеются в третьем КодыЕсли имеется отличие в битах в соответствующих позициях строк, то выбирается значение, Коды  Порождающие матрицы  Порождающие матрицы  Напоминание  Напоминание  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Порождающие матрицы  Коды  Теорема Лагранжа   Теорема Лагранжа            Теорема Лагранжа   Теорема Лагранжа   Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса Декодирование по лидеру смежного класса  Коды Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса        Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  В общем случае, если то Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса     Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса Декодирование по лидеру смежного классаСнова вернемся к примеру: Декодирование по лидеру смежного классаУже известно, что первый синдром есть Декодирование по лидеру смежного класса Декодирование по лидеру смежного классаНаходим, чтопоэтому второй синдром есть      . Декодирование по лидеру смежного класса Декодирование по лидеру смежного классапоэтому       – третий синдром. Декодирование по лидеру смежного класса Декодирование по лидеру смежного классаПродолжая процесс, получаем следующую таблицу. Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного классаЗаметим, однако, что процесс можно сделать еще быстрее. Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Декодирование по лидеру смежного класса  Коды ХеммингаВ рассматриваемом примере существуют определенные трудности при попытке исправить код для Коды Хемминга  Коды Хемминга  Коды Хемминга  Коды ХеммингаДля изучения матриц Хемминга необходимо понятие расстояния и его связь с Коды Хемминга  Коды Хемминга  Коды Хемминга  Коды Хемминга  Коды Хемминга  Коды Хемминга  Коды Хемминга  Коды ХеммингаВ приведенной далее теореме сформулирован важный критерий для определения числа ошибок, Коды Хемминга  Коды Хемминга  Коды Хемминга  Коды Хемминга  Коды Хемминга  Коды ХеммингаЗаданиеПостроить код Хэмминга. Изучить корректирующие способности кода Хэмминга.Показать, что синдромы указывают позиции ошибок.
Слайды презентации

Слайд 2 Коды
Определим код как представление множества символов строками, состоящими

КодыОпределим код как представление множества символов строками, состоящими из единиц и

из единиц и нулей.
Это множество символов обычно включает буквы

алфавита, цифры и, как правило, определенные контрольные символы.
Коды представляются бинарными строками с целью использования их компьютерами для хранения и передачи данных.

Слайд 3 Коды
Желательно, чтобы коды обладали некоторыми свойствами.
Наиболее важное

КодыЖелательно, чтобы коды обладали некоторыми свойствами. Наиболее важное свойство кода состоит

свойство кода состоит в том, что когда сообщение кодируется

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

Слайд 4 Коды
Существует несколько способов достижения этой цели.
Один из

КодыСуществует несколько способов достижения этой цели. Один из них – кодирование

них – кодирование всех символов двоичными строками одной длины.

Такой код называется блоковым.
Например, если для кодирования каждого символа используется 8 бит, то известно, что каждые восемь бит представляют один символ передаваемого сообщения.
Блоковый код особенно полезен при ограничении длины кода для каждого посланного символа или буквы.

Слайд 5 Коды
 

Коды 

Слайд 6 Коды
 

Коды 

Слайд 7 Коды
Часто необходимо сжимать данные, чтобы минимизировать объем памяти

КодыЧасто необходимо сжимать данные, чтобы минимизировать объем памяти для их хранения

для их хранения или время для передачи данных.
Что

касается минимизации объема памяти, то наиболее эффективным является код Хаффмана. Преимущество кода Хаффмана состоит также в том, что это мгновенный код.
Хорошо известным примером кода, минимизирующего время передачи, является код Морзе.


Слайд 8 Коды
В кодах Хаффмана и Морзе буквы или символы,

КодыВ кодах Хаффмана и Морзе буквы или символы, которые встречаются наиболее

которые встречаются наиболее часто, имеют более короткий код.


Слайд 9 Коды
В коде Морзе буквы разделены "пробелами", а слова

КодыВ коде Морзе буквы разделены

– тремя "пробелами". В данном случае "пробелы" – это

единицы времени.


Слайд 10 Коды
В процессе передачи данных могут возникать ошибки.
Все,

КодыВ процессе передачи данных могут возникать ошибки. Все, что может стать

что может стать причиной ошибок, называется неопределенным термином "шум".


Например, данные, полученные от отдаленного космического корабля, наверняка подвержены различного рода шумам.

Слайд 11 Коды
В некоторых случаях интерес представляет только определение наличия

КодыВ некоторых случаях интерес представляет только определение наличия ошибки, что соответствует

ошибки, что соответствует ситуации передачи данных еще раз.
Коды,

обладающие свойством определения наличия ошибок, называются кодами, обнаруживающими ошибки.

Слайд 12 Коды
В другом случае, когда данные не могут быть

КодыВ другом случае, когда данные не могут быть переданы еще раз

переданы еще раз (например, данные от удаленного космического корабля),

требуется дополнительная информация о данных с целью не только обнаружения, но и исправления ошибки.
Коды, позволяющие исправлять ошибки, называются кодами, исправляющими ошибки.

Слайд 13 Коды
Может показаться разумным всегда использовать коды с исправлением

КодыМожет показаться разумным всегда использовать коды с исправлением ошибок. Проблема использования

ошибок.
Проблема использования кодов с исправлением ошибок и кодов

с обнаружением ошибок состоит в том, что они должны включать в себя дополнительную информацию, поэтому они являются менее эффективными в отношении минимизации объема памяти.

Слайд 14 Коды
К сожалению, использование кодов с исправлением ошибок и

КодыК сожалению, использование кодов с исправлением ошибок и кодов с обнаружением

кодов с обнаружением ошибок не дает абсолютной гарантии того,

что ошибка будет исправлена или обнаружена.

Слайд 15 Коды
В качестве первого метода обнаружения ошибок рассмотрим бит

КодыВ качестве первого метода обнаружения ошибок рассмотрим бит контроля четности.Продемонстрируем этот

контроля четности.
Продемонстрируем этот метод на примере кода ASCII.


Слайд 16 Коды
ASCII-код является блоковым кодом, который использует 7 битов,

КодыASCII-код является блоковым кодом, который использует 7 битов, поэтому любой закодированный

поэтому любой закодированный символ изображается строкой из семи символов

1 и 0.
Восьмой бит добавляется таким образом, чтобы количество единиц было четным.
Поэтому, если код переданной строки получен с единственной ошибкой, то количество единиц будет нечетным, и получатель информации поймет, что произошла ошибка.

Слайд 17 Коды
К сожалению, если произошло две ошибки, их нельзя

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

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


Слайд 19 Коды
 

Коды 

Слайд 20 Коды
Если при кодировании каждая строка повторена один раз,

КодыЕсли при кодировании каждая строка повторена один раз, то в результате

то в результате получаем код с обнаружением ошибок.
Если

произошла ошибка, то соответствующие позиции не будут совпадать.

Слайд 21 Коды
Например, если закодированная строка имеет вид 111111010110111011, то

КодыНапример, если закодированная строка имеет вид 111111010110111011, то ошибки имеются в

ошибки имеются в третьем и в последнем битах.
Исправить

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

Слайд 22 Коды
Если имеется отличие в битах в соответствующих позициях

КодыЕсли имеется отличие в битах в соответствующих позициях строк, то выбирается

строк, то выбирается значение, которое встречается дважды.
Например, если

строка имеет длину 4 и нам передано 110110011101, то во второй позиции мы два раза получим 1 и один раз 0.
Таким образом, предполагаем, что правильное значение равно 1, и правильным вариантом закодированной строки является 1101.

Слайд 23 Коды
 

Коды 

Слайд 24 Порождающие матрицы
 

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

Слайд 25 Порождающие матрицы
 

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

Слайд 26 Напоминание
 

Напоминание 

Слайд 27 Напоминание
 

Напоминание 

Слайд 28 Порождающие матрицы
 

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

Слайд 29 Порождающие матрицы
 

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

Слайд 30 Порождающие матрицы
 

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

Слайд 31 Порождающие матрицы
 

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

Слайд 32 Порождающие матрицы
 

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

Слайд 33 Порождающие матрицы
 

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

Слайд 34 Порождающие матрицы
 

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

Слайд 35 Порождающие матрицы
 

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

Слайд 36 Порождающие матрицы
 

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

Слайд 37 Порождающие матрицы
 

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

Слайд 38 Порождающие матрицы
 

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

Слайд 39 Порождающие матрицы
 

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

Слайд 40 Порождающие матрицы
 

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

Слайд 41 Порождающие матрицы
 

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

Слайд 42 Порождающие матрицы
 

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

Слайд 43 Порождающие матрицы
 

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

Слайд 44 Порождающие матрицы
 

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

Слайд 45 Порождающие матрицы
 

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

Слайд 46 Порождающие матрицы
 

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

Слайд 47 Порождающие матрицы
 

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

Слайд 48 Порождающие матрицы
 

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

Слайд 49 Порождающие матрицы
 

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

Слайд 50 Порождающие матрицы
 

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

Слайд 51 Коды
 

Коды 

Слайд 52 Теорема Лагранжа
 

Теорема Лагранжа  

Слайд 53 Теорема Лагранжа
 

Теорема Лагранжа  

Слайд 57 Теорема Лагранжа
 

Теорема Лагранжа  

Слайд 58 Теорема Лагранжа
 

Теорема Лагранжа  

Слайд 59 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 60 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 61 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 62 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 63 Декодирование по лидеру смежного класса

Декодирование по лидеру смежного класса

Слайд 64 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 65 Декодирование по лидеру смежного класса

Декодирование по лидеру смежного класса

Слайд 66 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 67 Коды

Коды

Слайд 68 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 69 Декодирование по лидеру смежного класса

Декодирование по лидеру смежного класса

Слайд 70 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 71 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 72 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 75 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 76 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 77 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 78 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 79 В общем случае, если





то

В общем случае, если то

Слайд 80 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 81 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 83 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 84 Декодирование по лидеру смежного класса

Декодирование по лидеру смежного класса

Слайд 85 Декодирование по лидеру смежного класса
Снова вернемся к примеру:

Декодирование по лидеру смежного классаСнова вернемся к примеру:


,



.

Слайд 86 Декодирование по лидеру смежного класса
Уже известно, что первый

Декодирование по лидеру смежного классаУже известно, что первый синдром есть   .

синдром есть


.


Слайд 87 Декодирование по лидеру смежного класса

Декодирование по лидеру смежного класса

Слайд 88 Декодирование по лидеру смежного класса
Находим, что





поэтому второй синдром

Декодирование по лидеру смежного классаНаходим, чтопоэтому второй синдром есть   .

есть .


Слайд 89 Декодирование по лидеру смежного класса

Декодирование по лидеру смежного класса

Слайд 90 Декодирование по лидеру смежного класса





поэтому

Декодирование по лидеру смежного классапоэтому    – третий синдром.

– третий синдром.


Слайд 91 Декодирование по лидеру смежного класса

Декодирование по лидеру смежного класса

Слайд 92 Декодирование по лидеру смежного класса
Продолжая процесс, получаем следующую

Декодирование по лидеру смежного классаПродолжая процесс, получаем следующую таблицу.

таблицу.


Слайд 94 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 95 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 96 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 97 Декодирование по лидеру смежного класса
Заметим, однако, что процесс

Декодирование по лидеру смежного классаЗаметим, однако, что процесс можно сделать еще

можно сделать еще быстрее.
При этом потребуются только два

первых столбца приведенной выше таблицы.

Слайд 98 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 99 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 100 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 101 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 102 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 103 Декодирование по лидеру смежного класса
 

Декодирование по лидеру смежного класса 

Слайд 104 Коды Хемминга
В рассматриваемом примере существуют определенные трудности при

Коды ХеммингаВ рассматриваемом примере существуют определенные трудности при попытке исправить код

попытке исправить код для некоторых строк, поскольку все лидеры

имеют вес 1.
Эти трудности устраняются путем использования матрицы, называемой матрицей Хемминга, в качестве порождающей матрицы.

Слайд 105 Коды Хемминга
 

Коды Хемминга 

Слайд 106 Коды Хемминга
 

Коды Хемминга 

Слайд 107 Коды Хемминга
 

Коды Хемминга 

Слайд 108 Коды Хемминга
Для изучения матриц Хемминга необходимо понятие расстояния

Коды ХеммингаДля изучения матриц Хемминга необходимо понятие расстояния и его связь

и его связь с весом каждой из строк.
Начнем

с теоремы о весах строк.

Слайд 109 Коды Хемминга
 

Коды Хемминга 

Слайд 110 Коды Хемминга
 

Коды Хемминга 

Слайд 111 Коды Хемминга
 

Коды Хемминга 

Слайд 112 Коды Хемминга
 

Коды Хемминга 

Слайд 113 Коды Хемминга
 

Коды Хемминга 

Слайд 114 Коды Хемминга
 

Коды Хемминга 

Слайд 115 Коды Хемминга
 

Коды Хемминга 

Слайд 116 Коды Хемминга
В приведенной далее теореме сформулирован важный критерий

Коды ХеммингаВ приведенной далее теореме сформулирован важный критерий для определения числа

для определения числа ошибок, которые могут быть исправлены или

обнаружены с использованием кода.

Слайд 117 Коды Хемминга
 

Коды Хемминга 

Слайд 118 Коды Хемминга
 

Коды Хемминга 

Слайд 119 Коды Хемминга
 

Коды Хемминга 

Слайд 120 Коды Хемминга
 

Коды Хемминга 

Слайд 121 Коды Хемминга
 

Коды Хемминга 

  • Имя файла: teoriya-kodirovaniya.pptx
  • Количество просмотров: 103
  • Количество скачиваний: 0