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

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

Содержание ▲

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

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

Слайд 1

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

Теория кодирования Ирина Борисовна Просвирнина Коды, примеры кодов Порождающие матрицы Смежные классы группы по подгруппе, теорема Лагранжа Декодирование по лидеру смежного класса Декодирование по лидеру смежного класса с использованием синдромов Коды Хемминга

Слайд 2

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

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

Слайд 3

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

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

Слайд 4

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

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

Слайд 5

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

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

Слайд 6

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

Коды Разновидностью префиксного кода является кома-код. При его использовании каждый символ кодируется строкой из единиц, в конце которой стоит нуль. Значит, множество строк кода имеет вид Этот код имеет явный недостаток: элементы кода могут быть очень длинными и занимать большой объем памяти.

Слайд 7

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

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

Слайд 8

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

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

Слайд 9

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

Коды В коде Морзе буквы разделены "пробелами", а слова – тремя "пробелами". В данном случае "пробелы" – это единицы времени.

Слайд 10

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

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

Слайд 11

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

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

Слайд 12

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

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

Слайд 13

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

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

Слайд 14

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

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

Слайд 15

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

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

Слайд 16

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

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

Слайд 17

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

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

Слайд 18

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

Слайд 19

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

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

Слайд 20

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

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

Слайд 21

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

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

Слайд 22

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

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

Слайд 23

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

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

Слайд 24

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

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

Слайд 25

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

Порождающие матрицы Если – множество всех двоичных строк длины , то код – подмножество множества .

Слайд 26

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

Напоминание Группа представляет собой множество вместе с бинарной операцией (или произведением) на , обладающей следующими свойствами: для всех и из (т.е. операция на ассоциативна). В существует элемент , называемый единицей, который обладает свойством: для всех из Для каждого элемента из множества существует элемент из множества , который называется обратным элементом для и такой, что

Слайд 27

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

Напоминание Подмножество группы является подгруппой группы , если с той же самой операцией, что и , также является группой.

Слайд 28

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

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

Слайд 29

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

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

Слайд 30

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

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

Слайд 31

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

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

Слайд 32

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

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

Слайд 33

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

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

Слайд 34

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

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

Слайд 35

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

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

Слайд 36

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

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

Слайд 37

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

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

Слайд 38

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

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

Слайд 39

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

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

Слайд 40

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

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

Слайд 41

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

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

Слайд 42

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

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

Слайд 43

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

Порождающие матрицы Отметим, что имеет вид и что передает сообщение. А что делает ? Рассмотрим снова пример лекции: .

Слайд 44

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

Порождающие матрицы Если – строка сообщения, то закодированная строка имеет вид

Слайд 45

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

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

Слайд 46

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

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

Слайд 47

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

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

Слайд 48

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

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

Слайд 49

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

Порождающие матрицы В общем случае, если имеется закодированная строка и то для имеем

Слайд 50

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

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

Слайд 51

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

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

Слайд 52

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

Теорема Лагранжа Определение 1 Для подгруппы группы и произвольного из для некоторого из называется левым смежным классом подгруппы группы .

Слайд 53

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

Теорема Лагранжа Лемма 1 Для фиксированной подгруппы группы левые смежные классы подгруппы группы образуют разбиение группы .

Слайд 54

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

Лемма 1 Для фиксированной подгруппы группы левые смежные классы подгруппы группы образуют разбиение группы . Доказательство Каждый левый смежный класс непустой, поскольку для левого смежного класса элемент находится в .

Слайд 55

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

Лемма 1 Для фиксированной подгруппы группы левые смежные классы подгруппы группы образуют разбиение группы . Доказательство Предположим, что пересечение и непустое; пусть элемент принадлежит пересечению. Следовательно, для некоторых и из . Умножая обе части уравнения на , получаем , поэтому по определению обратного элемента имеем: ().

Слайд 56

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

Лемма 1 Для фиксированной подгруппы группы левые смежные классы подгруппы группы образуют разбиение группы . Доказательство. () для всех из Аналогично, Значит, Следовательно, левые смежные классы образуют разбиение группы .

Слайд 57

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

Теорема Лагранжа Лемма 2 Если – конечная группа и – подгруппа группы , то все левые смежные классы подгруппы группы содержат одно и то же количество элементов, а именно, количество элементов, которое находится в подгруппе . Доказательство Пусть – левый смежный класс подгруппы из . Определим таким образом: . – взаимно однозначное соответствие, или биекция.

Слайд 58

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

Теорема Лагранжа Теорема (Лагранж). Если – конечная группа и – подгруппа группы , то порядок делит порядок . Доказательство Если – порядок , – количество левых смежных классов в и – порядок , то согласно двум предыдущим леммам .

Слайд 59

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

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

Слайд 60

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

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

Слайд 61

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

Декодирование по лидеру смежного класса Опять выбираем элемент из который имеет минимальный вес и не принадлежит ни одному из предыдущих смежных классов. Например, можно выбрать . Смежный класс

Слайд 62

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

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

Слайд 63

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

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

Слайд 64

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

Декодирование по лидеру смежного класса В последнем смежном классе необходимо использовать строки веса . Можно выбрать одну из строк или .

Слайд 65

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

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

Слайд 66

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

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

Слайд 67

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

Коды

Слайд 68

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

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

Слайд 69

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

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

Слайд 70

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

Декодирование по лидеру смежного класса Теперь поищем более простой способ обнаружения ошибок. Пусть и – векторы (или строки) длины . Вектор называется ортогональным вектору , если их скалярное произведение . Пусть задан код . Двойственным кодом к коду , обозначаемым , называется множество всех строк из , ортогональных каждой строке из кода .

Слайд 71

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

Декодирование по лидеру смежного класса – подгруппа группы . Если код является -кодом, так что он порожден строками, то порожден строками.

Слайд 72

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

Декодирование по лидеру смежного класса Пусть – групповой код, а – двойственный ему код. Теорема 2 Строка принадлежит коду тогда и только тогда, когда она ортогональна каждой строке из , множества порождающих элементов кода .

Слайд 73

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

Теорема 2 Строка принадлежит коду тогда и только тогда, когда она ортогональна каждой строке из , множества порождающих элементов кода . Доказательство Если строка принадлежит коду , то она ортогональна каждой строке из множества , поскольку она ортогональна каждой строке из кода и .

Слайд 74

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

Теорема 2 Строка принадлежит коду тогда и только тогда, когда она ортогональна каждой строке из , множества порождающих элементов кода . Доказательство Предположим, что и строка ортогональна строке для всех , так что для всех . Каждый элемент из имеет вид где каждое равно или .

Слайд 75

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

Декодирование по лидеру смежного класса Вспомним, что в рассматриваемом примере Определим теперь где – матрица, транспонированная матрице

Слайд 76

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

Декодирование по лидеру смежного класса Матрица называется матрицей контроля четности.

Слайд 77

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

Декодирование по лидеру смежного класса Перебирая все возможные варианты, можно показать, что скалярное произведение любой строки из с любой строкой из равно . Отсюда получаем, что где — транспозиция -ой строки матрицы . По определению транспозиции является -ой строкой матрицы , преобразованной в столбец. Мы превращаем строку в столбец, чтобы на него можно было умножить матрицу .

Слайд 78

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

Декодирование по лидеру смежного класса Таким образом, если умножить матрицу на транспозицию любого элемента из то получим .

Слайд 79

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

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

Слайд 80

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

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

Слайд 81

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

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

Слайд 82

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

Если два элемента и из принадлежат одному и тому же смежному классу, образованному в с использованием группы , то Доказательство Если и принадлежат одному смежному классу, то для некоторого . Следовательно, и так как для всех .

Слайд 83

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

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

Слайд 84

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

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

Слайд 85

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

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

Слайд 86

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

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

Слайд 87

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

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

Слайд 88

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

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

Слайд 89

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

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

Слайд 90

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

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

Слайд 91

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

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

Слайд 92

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

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

Слайд 93

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

Слайд 94

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

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

Слайд 95

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

Декодирование по лидеру смежного класса Отсюда следует, что находится в строке . Лидер смежного класса – , элемент крайнего левого столбца строки, содержащей . Элемент кода , расположенный в верхней строке столбца, содержащего , равен . Согласно способу построения таблицы имеем , поэтому можем предположить, что переданная строка должна иметь вид , и в пятом бите была ошибка.

Слайд 96

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

Декодирование по лидеру смежного класса Этот метод намного быстрее, поскольку требует только умножить матрицу на транспозицию строки-сообщения, найти строку, содержащую синдром, и найти переданное сообщение. Лидер для этого сообщения – индикатор ошибки, а элемент кода , расположенный в первой строке столбца, содержащего переданное сообщение, есть исправленное сообщение.

Слайд 97

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

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

Слайд 98

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

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

Слайд 99

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

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

Слайд 100

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

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

Слайд 101

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

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

Слайд 102

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

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

Слайд 103

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

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

Слайд 104

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

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

Слайд 105

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

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

Слайд 106

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

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

Слайд 107

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

Коды Хемминга Например, пусть и – матрица Тогда – матрица

Слайд 108

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

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

Слайд 109

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

Коды Хемминга Теорема 3 Для строк и вес Доказательство Пусть и . Если , то либо , либо . Поэтому существованию каждой единицы в соответствует существование единицы либо в , либо в .

Слайд 110

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

Коды Хемминга Расстояние Хемминга, или просто расстояние между двумя строками кода и , имеющими одинаковую длину, это число соответствующих битов в строке, где одна строка имеет цифру 1, а другая имеет цифру 0. Будем обозначать функцию расстояния через .

Слайд 111

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

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

Слайд 112

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

Коды Хемминга Теорема 4 Функция расстояния Хемминга имеет следующие свойства: для строк и расстояние тогда и только тогда, когда ; для строк и расстояние ; для строк , и выполняется соотношение .

Слайд 113

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

Коды Хемминга Доказательство Первые два пункта следуют из определения. Докажем c). Для строк и вес Если и то вносит 1 в вес тогда и только тогда, когда и Но это верно в том и только в том случае, когда и различны, что вносит 1 в .

Слайд 114

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

Коды Хемминга Доказательство Заметим, что для любой строки строка состоит только из нулей. Обозначим такую строку через . для каждой строки . Следовательно,

Слайд 115

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

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

Слайд 116

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

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

Слайд 117

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

Коды Хемминга Теорема 5 Для кода , если , то использование кода позволяет обнаружить вплоть до ошибок; если , то использование кода позволяет исправить вплоть до ошибок.

Слайд 118

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

Коды Хемминга Доказательство a) Если , то для данной строки отсюда следует, что отличается от любой другой строки кода по крайней мере в позициях. Поэтому, если переданная строка имеет или менее ошибок, то она не может быть другой строкой кода, и ошибка определена.

Слайд 119

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

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

Слайд 120

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

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

Слайд 121

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

Коды Хемминга Теорема 6 Минимальное расстояние кода равно . Доказательство По определению , существуют такие, Обратно, для имеем Следовательно, Отсюда