Теория кодов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Теория кодов. Доклад-сообщение содержит 39 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Теория кодов

Слайд 2

Описание слайда:

Слайд 3

Описание слайда:

Введение Раздел теории кодов, посвященный декодированию сообщений, называется криптографией. Код – представление множества символов строками, состоящими из 0 и 1. Это множество символов обычно включает буквы алфавита, цифры и определенные контрольные символы. Коды представляются бинарными строками с целью использования из компьютерами для хранения и передачи данных. Коды должны обладать (по возможности) некоторыми свойствами. Наиболее важное свойство кода: когда сообщение кодируется как двоичная строка, состоящая из конкатенации элементов кода, эта конкатенация однозначна. Конкатенация – склеивание объектов линейной структуры. Конкатенация - бинарная операция, определенная на словах данного алфавита.

Слайд 4

Описание слайда:

Введение При декодировании сообщения не должно возникать проблем с тем, какую букву представляет элемент кода. Такой код называют декодируемым кодом. Способы достижения этой цели: 1) кодирование всех символов двоичными строками одной длины. Такой код называют блоковым. Полезен при ограничении длины кода для каждого посланного символа или буквы. 2) префиксный код иначе мгновенный код). Код С является префиксным, если элемент кода не может быть начальной строкой другого элемента кода. При чтении строки из единиц и нулей, изображающий символ, всегда известен момент завершения сроки.

Слайд 5

Описание слайда:

Кома-код Разновидность префиксного кода. При его использовании каждый символ кодируется строкой из единиц, в конце которой находится 0. Множество строк имеет вид {0, 10, 110, 1110, 11110, …}. Недостаток: элементы кода могут быть очень длинными и занимать большой объем памяти.

Слайд 6

Описание слайда:

Код минимизирующий время передачи данных и объем памяти - код Хаффмана. - код Морзе. Буквы разделяются пробелами, а слова тремя пробелами. Пробел – единица времени.

Слайд 7

Описание слайда:

Код Морзе

Слайд 8

Описание слайда:

Код Морзе

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

Код Грея Имеется вращающийся диск, разделенный на секторы, и серия щеток или лазерных лучей, выделяющих информацию о скорости вращения диска. Если двоичные строки, записывающие нумерацию соседних секторов, существенно различаются в в отдельных цифрах при переходе от одного сектора к следующему, тогда считывающее устройство воспримет это так, чтобы измененный сектор мог выбрать число, совершенно отличное от числа, выбранного любым из секторов. Желательно пронумеровать секторы таким образом, чтобы двоичные строки, определяющие соседние секторы, различались только цифрой.

Слайд 11

Описание слайда:

Код ASCII - блоковый код, использует 7 битов. Любой закодированный символ изображается строкой из семи символов 1 и 0. Восьмой бит добавляется таким образом, чтобы количество единиц было четным. Если код переданной строки получен с единственной ошибкой, то количество единиц будет нечетным, получатель информации поймет, что произошла ошибка. Если произойдет две ошибки, их нельзя обнаружить, т.к. количество единиц будет четным.

Слайд 12

Описание слайда:

Код ASCII

Слайд 13

Описание слайда:

Код ASCII Пусть вероятность ошибки при передаче равна 0, 01 как для изменения 1 и 0, так и для изменения 0 и 1. Пусть вероятность ошибки не зависит от расположения ошибки и от того, что является ошибкой: изменение 1 и 0 или наоборот. Пусть появление одной ошибки не влияет на вероятность появления другой. Поскольку 3 ошибки будут обнаружены, вероятность не обнаружить более двух ошибок меньше, чем вероятность наличия 4-х или более ошибок, т.к. любое нечетное количество ошибок будет обнаружено. И эта вероятность

Слайд 14

Описание слайда:

Порождающие матрицы Предполагается, что все строки кода имеют фиксированную длину n, эти строки трактуют как векторы или матрицы (1  n) –матрицы. Сложение: 1 + 1 = 0 11110001 + 10100111 = 01010110 - линейные коды. Строки кода С – двоичные строки длины n, которые являются векторами или (1  n) –матрицами. Если Bn - множество всех двоичных строк длины n, то С – подмножество множества Bn.

Слайд 15

Описание слайда:

Определение Код С называется линейным, если С – подгруппа группы Bn . Закон дистрибутивности: A (B + C) = AB + AC для любых матриц A, B, C, произведение которых определено. Если то скалярное произведение

Слайд 16

Описание слайда:

Определение Весом строки кода, обозначается wt(c), называется количество единиц в строке. Например, если с = 1011010, то wt(c) = 4. Пусть имеется (k  n) – матрица G = [Ik  An-k] G - называется порождающей матрицей. Строки порождающей матрицы – векторы или строки кода. Множество строк обозначается S. S = {100101, 010110, 001011}

Слайд 17

Описание слайда:

Определение Пусть С – код, образованный всеми векторами, которые являются конечными суммами строк из S. С – подгруппа Bn. Складывая две первые строки из S, 110011 будет принадлежать С. Группа С порождена множеством S. S является минимальным множеством, порождающим код С. Обозначение – группа С порождена множеством S: C = S* Код С вида [Ik  An-k] (порожденный строками [Ik  An-k] ) называется [n, k] – кодом.

Слайд 18

Описание слайда:

Теорема [n, k] – код С содержит 2k строк.

Слайд 19

Описание слайда:

Пример Если необходимо передать строки сообщения длины k, то кодируем их, умножая справа на матрицу С. Если то кодируем это строкой wC. Например, закодируем 110 или 110011.

Слайд 20

Описание слайда:

В общем случае Если S = (s1, s2, …, sk) – множество строк порождающей матрицы то закодированная строка имеет вид - сумма строк из S, т.к. каждое wi равно либо 1, либо 0 принадлежит С, т.к. С – группа, порожденная множеством S.

Слайд 21

Описание слайда:

Закодированная строка имеет вид Четвертый бит строки должен быть равен w1 +w2. Пятый бит должен быть равен w2 + w3. Шестой бит должен быть равен w1 + w3. Если закодированная строка имеет вид (w1, w2, w3, w4, w5, w6), То w4 = w1 + w2, w5 = w2 +w3, w6 = w1 +w3. Если любая закодированная строка после передачи не удовлетворяет этим соотношениям, то при передаче произошла ошибка.

Слайд 22

Описание слайда:

Матрица An-k служит для контроля точности передачи данных. В общем случае, если имеется закодированная строка w1 w2 w3 … wk … wn и

Слайд 23

Описание слайда:

Метод – использование лидеров смежных классов Проблема – исправление ошибки, если известно, что произошла единственная ошибка. Пример.

Слайд 24

Описание слайда:

Сформируем для С смежные классы в Bn . Первым смежным классом является сам С. Для формирования следующего смежного класса выберем элемент из Bn , который имеет минимальный вес и не принадлежит С. Например, можно выбрать b1 = 100000 . Смежный класс Опять выбираем элемент из Bn , который имеет минимальный вес и не ни одному из предыдущих смежных классов. Например, можно выбрать b2 = 010000 . Смежный класс

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

Определение Вектор v называется ортогональным вектору w, если скалярное произведение v  w = 0. Пусть задан код С. Двойственным к коду С, обозначается C , называется множество всех строк из Bn , ортогональных каждой строке из кода С . Теорема. C - подгруппа группы Bn.

Слайд 27

Описание слайда:

Теорема Пусть С - групповой код, а C - двойственный ему код. Строка t принадлежит коду C тогда и только тогда, когда она ортогональна каждой строке из множества S , множества порождающих элементов кода С .

Слайд 28

Описание слайда:

Прошлый пример . Матрица контроля честности где At3 – транспозиция матрицы А3 , полученная заменой строк матрицы А3 на столбцы. Матрица G называется матрицей контроля честности.