Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс (1083731), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

удовлетворяющих системе уравнений (суммы по модулю 2):

.

Теорема 6. Код Хэмминга порядка n содержит 2^{n – k} наборов, где и исправляет одну ошибку.

Доказательство. Рассмотрим систему уравнений из определения кода Хэмминга

.

Задаём произвольно _j, кроме . Это можно сделать 2^{n – k} способами. Так как в скобках не встречаются, то они однозначно определяются из системы.

Пусть передано кодовое слово , ошибка произошла в d-ом разряде и пусть d = (_k–1_k–2…₁₀)₂. Пусть на выходе получено слово , при этом _i = _i при i  d, _d = _d  1. Обозначим

Утверждение. (_k–1_k–2…₁₀)₂ = d.

Доказательство. Пусть _i = 0  d  D_i, тогда , следовательно, _i = 0 и _i = _i. Пусть теперь _i = 1 и d  D_i. Тогда .

Утверждение доказано.

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

Теорема доказана.

Замечание. Обычно разряды с номерами 1, 2, 4, 8, …, 2^k–1 называют проверочными (или контрольными), остальные — информационными.

Теорема 7. .

Доказательство. Имеем (теорема 5). Правое неравенство в теореме 7 следует из того, что S₁ (n) = n + 1. Заметим предварительно, что аналогично нельзя получить и левое неравенство, так как

.

По теореме 6 всего различных слов в коде Хэмминга, исправляющем одну ошибку — m = 2^n–k. Поскольку , имеем

.

Теорема доказана.

Глава V. Основы теории конечных
автоматов

§35. Понятие ограниченно детерминированных (автоматных) функций, их представление диаграммой Мура.
Единичная задержка

Пусть даны A = {a₁, a₂, …, a_r} — входной алфавит и B = {b₁, b₂, …, b_m} — выходной алфавит. Определим множества A^∞ и B^∞ как множества всевозможных последовательностей в алфавитах A и B соответственно.

Определение 1. Отображение : A^∞  B^∞ называется детерминированной функцией (д.-функцией), если b(t) для любого t = 1, 2, … однозначно определяется по a(1), a(2), …, a(t). Обозначать д.-функции будем так: , причём,

если a₁ (1) = a₂ (1), то b₁ (1) = b₂ (1);

если , то b₁(t) = b₂(t).

Определение 2. Пусть задана д.-функция : A^∞  B^∞. Рассмотрим произвольное слово . Определим функцию следующим образом: пусть a(1), a(2), …, a(t)… — произвольная входная последовательность. Рассмотрим

 (a₁a₂…a_ka(1)a(2)…a(t)…) = b₁b₂…b_kb(1)b(2)…b(t)….

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

Определение 3. Детерминированная функция  : A^∞B^∞ называется ограниченно детерминированной, если у неё имеется лишь конечное число различных остаточных функций.

Определение 4. Автоматом (инициальным) называется любая шестёрка (A, B, Q, G, F, q₀), где A, B, Q — конечные алфавиты (A называют входным алфавитом, B — выходным алфавитом, Q — множеством состояний), G: A  Q  Q, F: A  Q  B, q₀  Q — начальное состояние.

Входом автомата служит последовательность a(1)a(2)a(3)…a(t)… A^* (конечная или бесконечная), выходом автомата служит последовательность z(t), при этом автомат задаётся системой канонических уравнений

Определение 5. Отображение : A^∞  B^∞ называется автоматной функцией, если существует автомат, который реализует это отображение.

Утверждение. Функция является автоматной тогда и только тогда, когда она является ограниченно детерминированной.

Пример. Пусть A = B = Q = {0, 1} и система канонических уравнений выглядит следующим образом:

Такой автомат, очевидно, осуществляет отображение a(1)a(2)…0a(1)a(2)… и называется единичной задержкой.

x (t)		a (1)	a (2)	a (3)
q (t)	0	a (1)	a (2)	a (3)
z (t)		0	a(1)	a(2)

Определение 6. Диаграммой Мура для автомата называется ориентированный граф с множеством вершин Q, у которого каждой паре (a, q) сопоставляется дуга, идущая из вершины q в вершину, соответствующую G (a, q). Этой дуге приписывается пометка (a, F (a, q)). Особым образом помечена вершина, соответствующая начальному состоянию. Диаграмма Мура однозначно задаёт автомат.

§36. Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими
отображений

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

Пусть A = B = {0, 1}, E₂ⁿ — множество всех булевых векторов длины n.

Теорема 1. Схема из функциональных элементов и задержки осуществляет автоматное отображение.

Доказательство. 1) Пусть в схеме имеется r элементов задержки. Пусть i-я задержка R_i приписана вершине v_i, в которую идёт дуга из вершины w_i. Для всех i = 1, …, r удалим из СФЭЗ дуги (w_i, v_i). По определению СФЭЗ в полученном после этого графе не будет ориентированных циклов и он, тем самым будет представлять собой СФЭ. Входами этой СФЭ будут все входы исходной схемы, а также все вершины v_i, i = 1, …, r (заметим, что все они различны и отличны от входов исходной схемы). Выходами полученной СФЭ объявим все выходы исходной схемы и вершины w_i, i = 1, …, r. Пусть в исходной схеме выходам приписаны переменные z₁, …, z_m, входам — переменные x₁, …, x_n. Вершинам v_i припишем переменные q'₁, …, q'_r, а вершинам w_i — переменные q₁, …, q_r. В соответствии с определением функционирования СФЭ, для некоторых функций алгебры логики f_i, g_j справедливо:

(1)

Естественно считать, что равенства (1) выполняются в каждый момент времени t = 1, 2, 3,…, то есть

(2)

Так как, в соответствии с каноническими уравнениями элемента единичной задержки его выход в момент t совпадает с его входом в момент t – 1, то естественно считать, что в исходной схеме q'_i (t) = q_i (t – 1) при
t = 1, 2, … для всех i = 1, …, r, где q_i (0) = 0. Тогда равенства (2) принимают вид (где i = 1, …, m и j = 1, …, r):

(3)

Полученные равенства определяют функционирование СФЭЗ и называются её каноническими уравнениями.

2) Пусть отображение , осуществляемое схемой , задаётся каноническими уравнениями (3). Введём переменные X = (x₁, …, x_n),
Q = (q₁, …, q_r), Z = (z₁, …, z_m), принимающие значения, соответственно в , , . Положим q₀ = (0, …, 0). Тогда (3) можно переписать в виде

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

§37. Моделирование автоматной функции схемой из
функциональных элементов и элементов задержки

Определение. Пусть автоматная функция  отображает последовательности в конечном алфавите A в последовательности в конечном алфавите B. Пусть СФЭЗ  осуществляет преобразование  последовательностей с элементами из в последовательности с элементами из . Будем говорить, что  моделирует , если существуют отображения (кодирования) и , сопоставляющие разным элементам разные элементы и обладающие свойством: для любой последовательности P = a(1)a(2)…a(t) в алфавите A, если

 (P) = T = b(1)b(2)…b(t), то  (K₁ (P)) = K₂ (T),
где K₁ (P) = K₁ (a(1))K₁ (a(2))…K₁ (a(t)),
K₂ (T) = K₂ (b(1))K₂ (b(2))…K₂ (b(t)).

Теорема 2. Для любой автоматной функции существует моделирующая её СФЭЗ в базисе из функциональных элементов дизъюнкции, конъюнкции, отрицания и элемента задержки.

Доказательство. Пусть автоматная функция дана автоматом
D = (A, B, Q, G, F, q₀). Выберем n, m, r так, что 2ⁿ  |A|, 2^m  |B|, 2^r  |Q|. Рассмотрим произвольные отображения (кодирования) , , , при которых разные элементы отображаются в разные элементы. Дополнительно потребуем, чтобы K₃ (q₀) = (0, …, 0). Рассмотрим отображения и такие, что для любых a  A и q  Q выполняется

(1)

Равенства (1) определяют отображения G' и F' только для пар таких, что является кодом некоторой буквы из A, а является кодом некоторой буквы из B. Для остальных пар отображения G' и F' доопределим произвольно. Пусть . Рассмотрим автомат с каноническими уравнениями

(2)

Из (1) вытекает, что если автомат D преобразует последовательность P в алфавите A в последовательность T в алфавите B, то H преобразует код K₁ (P) последовательности P в код K₂ (T) последовательности T. Таким образом, достаточно показать, что автоматную функцию, задаваемую равенствами (2), можно реализовать схемой. Так как значением переменной X являются наборы длины n из , то её можно рассматривать как набор переменных (x₁, …, x_n), принимающих значения из E₂. Аналогично для переменных Q и Z. Тогда (2) можно переписать в эквивалентном виде для некоторых функций алгебры логики f_i, g_j:

Тогда можно построить схему из функциональных элементов в базисе {,&, } с n + r входами и m + r выходами, реализующую семейство функций

Пусть в этой СФЭ входная переменная приписана вершине v_j, а выходная переменная q_j — вершине w_j. Добавим дугу (w_j, v_j) и сопоставим вершине v_j элемент задержки. Проделав это для всех пар , получим СФЭЗ, функционирование которой описывается каноническими уравнениями

Характеристики

Список файлов лекций