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

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

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

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

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

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

__Для данного автомата M его функции j_M и y_M могут быть определены не только на множестве А всех входных букв, но и на множестве А * всех входных слов. Для любого входного слова a = a _j1 a _j2... a_jk

j(s_i, a_{j 1} a_{j 2}... a_jk) = j(j(…j(s_i, a _j1), a _j2),..., a_{jk- 1}), a_jk).

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

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

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

j(s_i, a a_j) = j(j(s_i, a), a_j). (1)

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

y(s_i, a a_j) = y (j(s_i, a), a_j). (2)

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

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

w = y (S0, a_{j 1}) y (S0, a_{j 1} a_{j 2})... y (S0, a_{j 1}... a_jk). (3a)

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

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

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

M (s_i, a_j) = y (s_i, a_j)

M (s_i, a a_j) = M (s_i, a) y (j(s_i, a), a_j) (3б)

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

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

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

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

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

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

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

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

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

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

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

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

___Пусть M = (A_M, S_M, B_M, j _M, y _M) и T = (A_T, S_T, B_T, j _T, y _T) — два автомата.

____Тройка отображений f: A_M ® A_T, g: S_M ® S_T, h: B_M ® B_T называется гомоморфизмом автомата M в автомат T, если для любых a Î A_M, s Î S_M, b Î B_M выполнены условия:

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 = (A_M, _SM, B_M, j _M, f _M) и T = (A_T, S_T, B_T, j _T, f _T) — два автомата и тройка отображений f: A_M ® A_T, g: S_M ® S_T, h: B_M ® B_T

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

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

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

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

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

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

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

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

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

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

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

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

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

___Теорема. Для любого автомата M существует минимальный автомат M ₀, единственный с точностью до изоморфизма; если множ. состояний M можно разбить на l классов эквивалентности (l £ n): C ₁ = { s ₁₁,..., s _{1 i 1}},..., С_l = { s_{l 1},..., s_lil }, то M ₀ имеет 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=log_mh

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

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

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

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

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

убывания их вероятностей: Р (А ₁)³ Р (А ₂)… P (A_N).

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

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

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

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

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

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

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

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

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

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

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

2) Образовать новое множ. А¹ ={A₁, А₂, …, A_N-2, А }. Говорят, что А¹

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

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

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

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

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

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

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

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

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

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

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

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

Пусть V ={ a _l, а ₂,..., a_N } префиксный двоичный код. Длины кодовых слов a ₁, а ₂, …, a_N, равны l ₁, l ₂,..., l_N, при этом длина слова равна номеру этажа на котором находится концевая вершина

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

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

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

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

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

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

2) Типы кодов

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

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

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

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

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

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

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

__Вставляем значения 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´M^T = 0

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

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

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

Дата добавления: 2015-11-16