Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

S, A, j, y задаются по столбцам.

Читайте также:
  1. Следующим шагом задаются параметры страницы и автоматическая расстановка переносов.

ДИАГРАММА ПЕРЕХОДОВ::::

__Ориентированный мультиграф, называемый графом переходов или диаграммой переходов

__Вершины графа соответствуют состояниям. Если j (Si,aj)=Sk, y(Si,aj)=bl, то из вершины Si в вершину Sj веден дуга на которой написано (aj, bl)

___В каждой вершине si выполнены условиями корректности:

1) для любой входной буквы aj имеется дуга, выходящая из si, на которой написано aj (условие полноты);

2) любая буква aj, встречается только на одном ребре, выходящем из si (условие непротиворечивостиили детерминированности)

63. Автоматы и входные слова. Автоматное отображение и его свойства.

__Для данного автомата M его функции jM и yM могут быть определены не только на множестве А всех входных букв, но и на множестве А * всех входных слов. Для любого входного слова a = a j1 a j2... ajk

j(si, aj 1 aj 2... ajk) = j(j(…j(si, a j1), a j2),..., ajk- 1), ajk).

Иначе, определяя индуктивно:

а) j(si, aj) задается автоматной таблицей M;

б) для любого слова a Î А * и любой буквы aj

j(si, a aj) = j(j(si, a), aj). (1)

С помощью расширенной функции j определяется (также индуктивно) расширенная функция y:

y(si, a aj) = y (j(si, a), aj). (2)

АВТОМАТНОЕ ОТОБРАЖЕНИЕ::::

__Зафиксируем в M начальное состояние S 0 и каждому входному слову a = aj 1 aj 2... ajk поставим в соответствие слово w в выходном алфавите:

w = y (S0, aj 1) y (S0, aj 1 aj 2)... y (S0, aj 1... ajk). (3a)

_Это соответствие, отображающее входные слова в выходные слова, называется автоматным отображением, а также автоматным (или ограниченно детерминированным) оператором, реализуемым автоматом (M, S0).

_Если результатом применения оператора к слову a является выходное слово w, то это будем обозначать соответственно M (S0, a) = w или M (a) = w.

___Число букв в слове a, как обычно, называется длиной a и обозначается |a| или l (a). Автоматное отображение также удобно определить индуктивно:

M (si, aj) = y (si, aj)

M (si, a aj) = M (si, a) y (j(si, a), aj) (3б)

СВ_ВА АВТОМАТНОГО ОТОБРАЖЕНИЯ::::::::

1) слова a и w = M (a) имеют одинаковую длину: |a| = |w| (свойство сохранения длины);

2) если a = a1a2 и M (a1a2) = w1w2, где |a1| = |w1|, то M (a1) = w1; иначе говоря, образ отрезка длины i равен отрезку образа той же длины.

__Автоматные операторы — это операторы без предвосхищения, т. е. операторы, которые, перерабатывая слово «не заглядывая вперед»: i -я буква выходного слова зависит только от первых i букв входного слова.

64. Виды автоматов: Мили, сильносвязанный, автономный, Мура. Изоморфизм и эквивалентность автоматов. Изоморфизм графов и автоматов. Неотличимые автоматы. Минимальный автомат.

__Общая модель конечного автомата (S-конечно), которая рассматривалась ранее, называется автоматом Мили.

___Состояние sj называется достижимым из состояния si, если существует входное слово a, такое, что j(si, a) = sj. Автомат M называется сильно связным, если из любого его состояния достижимо любое другое состояние.

__Автомат называется автономным, если его входной алфавит состоит из одной буквы: А ={ а }. Все входные слова автономного автомата имеют вид аа... а.

___Конечный автомат называется автоматом Мура, если его функция выходов зависит только от состояний, т.е. для любых s, ai, aj y(s, ai) = y(s, aj). Функция выходов автомата Мура естественно одноаргументная; обычно ее обозначают буквой m и называют функцией отметок. В графе автомата Мура выход пишется не на ребрах, а при вершине.

__Теорема: Для любого автомата Мили существует эквивалентный ему автомат Мура.

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

ИЗОМОРФИЗМ И ЭКВИВАЛ,:::::

___Пусть M = (AM, SM, BM, j M, y M) и T = (AT, ST, BT, j T, y T) — два автомата.

____Тройка отображений f: AM ® AT, g: SM ® ST, h: BM ® BT называется гомоморфизмом автомата M в автомат T, если для любых a Î AM, s Î SM, b Î BM выполнены условия:

j T (g (s), f (a)) = g (j M (s, a));

y T (g (s), f (a)) = h (y M (s, a)).

___В этом случае автомат Т называется гомоморфным автомату M.

___Если все три отображения сюръективны, то эта тройка называется гомоморфизмом M на Т.

__Пусть M = (AM, SM, BM, j M, f M) и T = (AT, ST, BT, j T, f T) — два автомата и тройка отображений f: AM ® AT, g: SM ® ST, h: BM ® BT

___Если автомат Т гомоморфный автомату M и кроме этого, все три отображения взаимно однозначны, то они называются изоморфизмом M на Т;

___Автоматы, для которых существует изоморфизм, называются изоморфными. Ясно, что мощности соответствующих алфавитов изоморфных автоматов должны быть одинаковыми.

ИЗОМОРФИЗМ ГРАФОВ И АВТОМ,::::

__В графе автомата Т поменяем местами буквы на двух ребрах: на ребре (r 1, r 2) напишем v, а на ребре (r 2, r 1) напишем w. Получим автомат Т ¢¢, граф которого изоморфен графу Т;

__Однако сам автомат Т ¢¢ не изоморфен Т. Действительно, при изоморфизме графов вершина r 4 автомата Т изоморфна вершине r 4 автомата Т ¢¢, однако Т (r 4, ааа) = vvv Т ¢¢(r 4, ааа) = vvw, (очевидно из графов).

РИСУНОК (лекция 14(17))

НЕОТЛИЧИМЫЕ АВТОМАТЫ::::

___Автоматы M и Т называются неотличимыми, если для любого состояния s автомата M найдется неотличимое от него состояние r автомата Т и, наоборот, для любого r из Т найдется неотличимое от него s из M.

___Неотличимость автоматов означает, что любое автоматное отображение, реализуемое одним из них, может быть реализовано другим; иначе говоря, их возможности по реализации преобразований входной информации в выходную совпадают.

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

МИНИМАЛЬНЫЙ АВТОМАТ:::::

__Переход от автомата M к эквивалентному автомату называется эквивалентным преобразованием автомата M.

__Можно ставить различные задачи о поиске автоматов, эквивалентных данному и обладающих заданными свойствами. Наиболее изученной среди таких задач является задача о минимизации числа состояний автомата: среди автоматов, эквивалентных M, найти автомат с наименьшим числом состояний — минимальный автомат.

___Теорема. Для любого автомата M существует минимальный автомат M 0, единственный с точностью до изоморфизма; если множество состояний M можно разбить на l классов эквивалентности (l £ n): C 1 = { s 11,..., s 1 i 1},..., Сl = { sl 1,..., slil }, то M 0 имеет l состояний.

65. Подстановочные, перестановочные криптограммы, Шифр Тритемиуса.

ПОДСТАНОВОЧНЫЕ::::

__Каждой букве алфавита сопоставляют определенный символ (иногда тоже букву) и при кодировании всякую букву текста заменяют на соответствующий ей символ

___Прием декодирования — с учетом вероятностей появления букв и буквосочетаний (частотный анализ)

ПЕРЕСТАНОВОЧНЫЕ::::

__Весь текст разбивается на группы, состоящие из одинакового числа букв

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

___Если группа достаточно длинная (иногда это весь текст целиком), то число возможных перестановок очень велико, отсюда большое многообразие перестановочных криптограмм

ШИФР ТРИТЕМИУСА:::::

__Буквы алфавита нумеруются по порядку числами 0, 1,..., 30. При шифровании ключевое слово (или номера его букв) подписывается под сообщением с повторениями

____например:

всвязиссоздавшимсяположениемотодвигаемсрокивозвращениядомойрамзай

записьзаписьзаписьзаписьзаписьзаписьзаписьзаписьзаписьзаписьзаписьзапи

____Каждая буква сообщения «сдвигается» вдоль алфавита по следующему правилу: буква с номером m, под которой стоит буква ключевого слова с номером k, заменяется на букву с номером l = m + k (если m + k <31) или букву с номером l = m + k (mod 31). (если m + k >31).

66. Равномерные коды, неравномерные однозначно декодируемы (префиксные) коды: код и дерево Фано, кодирование и дерево по Хафменну.

__Равномерные коды содержат кодовые комбинации одинаковой длины для каждого символа в сообщении.

__Число знаков n для кодовой комбинации каждого символа сообщения для равномерного кода, имеющего основание m определяется следующим образом:

Если нам необходимо закодировать k символов, то

1) находим h ≥ k, которое является ближайшей степенью m

2) определяем n=logmh

НЕРАВНОМЕРНЫЕ ОДН.ДЕКОД(ПРЕФ):::

___Однозначно декодируемые коды – это такие коды, у которыхвсякая последовательность кодовых символов может быть единственным образом разбита на кодовые слова.

__Префиксные коды относятся к однозначно декодируемым и обладают тем свойством, что никакое кодовое слово не является началом (префиксом) другого кодового слова, что позволяет однозначно декодировать код.

ПРЕФИКСНЫЙ КОД(МЕТОД ФАНО)::::

__Располагаем N сообщений в порядке

убывания их вероятностей: Р (А 1Р (А 2)… P (AN).

__Разбиваем множество символов на две группы так,,чтобы суммарные вероятности символов каждой из групп были как можно более близки друг к другу. Символам из одной группы в качестве первого знака кодового слова приписывается символ 0, сообщениям из другой — 1.

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

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

___Понятно, что чем более вероятен символ, тем быстрее оно образует «самостоятельную» группу и тем более коротким словом оно будет закодировано.

ДЕРЕВО ФАНО:::LРИСУНОК)
___Нулевой уровень дерева – это корень

___Первый уровень располагаются первые две группы разбиения («А1») и («А2», «А3», «А4»). Эти группы соединяются с корнем ребра и им присваивается первые кодовые символы. Слева располагается группа, которой присваивается 0, справа группа, которой присваивается 1.

____На i+1-ом уровне располагаются группы, получаемые разбиением групп i-го уровня с соответствующими присваиваемыми символами.

___Концевые вершины дерева имеют по одному кодируемому символу.

___Кодовая комбинация для каждого кодируемого символа состоит из всех символов в ветке.

КОДИРОВ. ПО ХАФФМЕНУ:::::
1) В исходном множестве элементов

сообщений А0 ={A1, А2, …, AN-2, АN-1, AN}, отсортированных по убыванию вероятности, объединить два наименее вероятных сообщения АN-1, AN в одно сообщение А с вероятностью появления P(A) = P(АN-1)+P(AN).

2) Образовать новое множество А1 ={A1, А2, …, AN-2, А }. Говорят, что А1

получают сжатием А0.

3) Множество А1 отсортировать в порядке убывания вероятностей.

4) Используя процедуру описанную в 1-3

пунктах получить новое множество А2

путем сжатия множества А1.

5) Шаги 1-4 повторять, пока в множестве

АN-2 не останется два элемента

ДЕРЕВО ХАФФЕНА::::

___Дерево кодирования на первом уровне имеет два элемента множества АN-2, которые соединяются ребрами с корнем дерева. Элементу с меньшей вероятностью приписывается символ 1, а элементу с большей вероятностью -0.

___i+1-ый уровень дерева состоит из элементов множества АN-i-2, которые соединяются ребра с элементами i-го уровня из которых они получены расщеплением. Элементу с меньшей вероятностью приписывается символ 1, а элементу с большей вероятностью символ 0.

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

67. Условие однозначной декодируемости для неравномерных кодов.

__Пусть V ={ a l, а 2,..., aN } префиксный двоичный код. Длины кодовых слов a 1, а 2, …, aN, равны l 1, l 2,..., lN, при этом длина слова равна номеру этажа на котором находится концевая вершина

___Раннее установлено, что

 

Здесь n i число концевых вершин i-го этажа дерева

___ Учитывая взаимосвязь длины слова и номера этажа получаем неравенство Крафта

__Неравенством Крафта является условием однозначной декодируемости префиксных кодов

 

68. Кодирование и декодирование при передаче информации по каналам связи с «шумом». Типы кодов: с обнаружением и исправлением ошибки. Расстояние Хемминга и аксиомы расстояний. Вес слова. Теоремы об исправлении и обнаружении ошибок.

1) КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ?

2) Типы кодов

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

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

РАССТ ХЕММИНГА,АКСИОМЫ,ВЕС::

__На множестве двоичных слов длины m расстоянием d (a, b) между словами a и b называет расстоянием Хемминга и определяется числом несовпадающих позиций этих слов.

__Расстояние Хемминга удовлетворяет аксиомам расстояний:

1) d (a, b) ³ 0 и d (a, b) = 0 тогда и только тогда, когда a = b;

2) d (a, b) = d (b, a);

3) d (a, b) + d (b, c) ³ d (a, c) (неравенство треугольника).

__Весом w(a) слова a называют число единиц среди его координат.

__Тогда расстояние между словами a и b есть вес суммы a Å b: d (a, b) = w (a Å b), где Å — операция покоординатного сложения по модулю 2.

ТЕОРЕМЫ ОБ ИСПР И ОБНАР:::

_Теорема Для того, чтобы код позволял обнаруживать ошибки в k (или менее) позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было ³ k + 1.

_Теорема Для того, чтобы код позволял исправлять все ошибки в k (или менее) позициях, необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было ³ 2k + 1.

69. Кодирование и декодирование по Хеммингу.

КОДИРОВАНИЕ:

__Для определения значения элементов вектора В, являющимися степенями двойки b0, b1, b4, b8 … используется матрица M размера k´m, в которой каждый столбец заполняется номером столбца в двоичном виде, где k-число потребовавшихся дополнительных позиций, а m-общее число позиций в векторе B.

_Записываем систему уравнений B´MT = 0

_ Операция сложения подразумевает сложение по модулю 2.

ДЕКОДИРОВАНИЕ:

__Вставляем значения bi, определенных из системы уравнений

В = b1 b2 b3 b4 b5 b6 b7 b8 b9 b10

b11

0 0 0 0 1 1 0 0 1 1 0

_Вектор ошибок E(e1…em) состоит из всех нулей, если при передаче не было допущено ошибки. Если ошибка была допущена в позиции bi, то ei=1

__Принятое слово D(d1… dm) = В(b1… bm) + E(e1…em) состоит из суммы (сложения по модулю 2) закодированного слова и вектора ошибок.

__В принятом слове D(d1… dm) нет ошибки если D´MT = 0

Доказательство: D´MT = (B+E) ´MT = B´MT +E´MT = 0+0=0 (B´MT =0 по построению, E´MT =0 так как предполается отсутствие ошибки)

__В принятом слове D(d1… dm) ошибка содержится в столбце i, номером которого это двоичная запись вектора X, являющегося решением системы уравнений Х=D´MT

Доказательство: Х=D´MT =(B+E)´MT =B´MT +E´MT =0+E´MT =E´MT. Вектор E может содержать только одну «1». Пусть «1» находится в позиции bi, тогда запись E´MT соответствует системе уравнений, где на «1» от вектора E умножается только bi элемент каждого столбца. В результате вектор Х(х1… хk) будет содержать значение bi строки матрицы MT. В свою очередь bi строка матрицы MT соответствует bi столбцу матрицы М. А матрица М заполнялась таким образом, что содержимое bi столбца соответствовало двоичной записи номера данного столбца.


Дата добавления: 2015-11-16; просмотров: 43 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Построения СКНФ| ТЕМА XII. СЕМЬЯ И СОЦИАЛИЗАЦИЯ ЛИЧНОСТИ ....................... 159

mybiblioteka.su - 2015-2024 год. (0.025 сек.)