Алексеев В.Б. Лекции по дискретной математике (1083733), страница 10

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

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

Пусть уже выбраны наборы α~1 ,!,α~k . Для выбора набора α~k +1 запрещено точек не больше, чем k·S2r (n), то есть, если k·S2r (n) < 2n, то можно выбрать α~k +1 . Тупик наступит при выборе m-го набора, когда2nm ⋅ S 2 r (n ) ≥ 2 n ⇔ m ≥S 2 r (n )⇒ M r (n ) ≥2nS 2 r (n ).Теорема доказана.§34. Коды Хэмминга. Оценка функции M1 (n).Рассмотрим коды, исправляющие одну ошибку типа замещения в словах длины n. Выберем натуральное k таким, что k ≤ log 2 n + 12k −1 ≤ n ≤ 2k − 1 ⇔ ⇔ k = log 2 n + 1 = log 2 (n + 1) .k ≥ log 2 (n + 1)Разобьём номера всех разрядов исходного слова на k классов:Di = {m | m = (mk–1mk–2…m0)2, mi = 1}, 1 ≤ m ≤ n.так, например, D0 = {1, 3, 5, 7, …}, D1 = {2, 3, 6, 7, …}, D2 = {4, …}.Определение.

Кодом Хэмминга порядка n называется множество наборовα~ = (α ,α ,!,α ) ∈ E k ,12n2удовлетворяющих системе уравнений (суммы по модулю 2): ∑ j∈D α j = 00 ∑ j∈D1 α j = 0.(∑α =0 j∈Dk −1 j37Теорема 6. Код Хэмминга порядка n содержит 2n – k наборов, где k = log 2 n  + 1 и исправляет одну ошибку.Доказательство. Рассмотрим систему уравнений из определения кода Хэммингаα1 ⊕ (α 3 ⊕ !) = 0 α ⊕ (!) = 02.( α 2k −1 ⊕ (!) = 0Задаём произвольно αj, кроме α1 ,α 2 ,α 4 ,!,α 2k −1 .

Это можно сделать 2n – k способами. Так какα1 ,α 2 ,α 4 ,!,α 2k −1 в скобках не встречаются, то они однозначно определяются из системы.Пусть передано кодовое слово α~ = (α1α 2 !α n ) , ошибка произошла в d-ом разряде и~пусть d = (γk–1γk–2…γ1γ0)2. Пусть на выходе получено слово β = (β1 β 2 ! β n ) , при этом βi = αi∑ β ,δпри i ≠ d, βd = αd ⊕ 1. Обозначим δ 0 =jj∈D01=∑ β ,!, δj∈D1Утверждение. (δk–1δk–2…δ1δ0)2 = d.Доказательство.

Пусть γi = 0 ⇒ d ∉ Di, тогдаПусть теперь γi = 1 и d ∈ Di. Тогда∑ β = ∑αj∈Diij∈Di∑βj∈Diijj=k −1=∑αj∈Di∑βj∈Dk −1jj., следовательно, δi = 0 и δi = γi.⊕1 = 1 ⇒ δ i = 1 ⇒ δ i = γ i .Утверждение доказано.Теорема доказана.Замечание. Обычно разряды с номерами 1, 2, 4, 8, …, 2k–1 называют проверочными (иликонтрольными), остальные — информационными.2n2nТеорема 7.≤ M 1 (n ) ≤.2nn +12n2nДоказательство. Имеем≤ M r (n ) ≤. Правое неравенство следует из того,S 2 r (n )S r (n )что S1 (n) = n + 1. Заметим предварительно, что аналогично нельзя получить и левое неравенство, так какnn(n − 1) n 2~S 2 (n ) = 1 + n +   = 1 + n +.22 2Всего различных слов в коде, исправляющем одну ошибку — m = 2n–k.

Посколькуk = log 2 n  + 1 , имеемk ≤ log 2 n + 1 ⇒ m ≥ 2n −log 2 n −1Теорема доказана.382n2n=⇒ M 1 (n ) ≥ m ≥.2n2nГлава V. Основы теории конечных автоматов§35. Понятие ограниченно детерминированных (автоматных) функций,их представление диаграммой Мура. Единичная задержка.Пусть даны A = {a1, a2, …, ar} — входной алфавит и B = {b1, b2, …, bm} — выходной алфавит.

Определим множества A∞ и B∞ как множества всевозможных последовательностей валфавитах A и B соответственно.Определение 1. Отображение ϕ: A∞ → B∞ называется детерминированной функцией(д.-функцией), если b(t) для любого t = 1, 2, … однозначно определяется по a(1), a(2), …, a(t).a (1)! a1 (t )! → b1 (1)!b1 (t )!Обозначать д.-функции будем так: ϕ : 1, причём,a2 (1)! a2 (t )! → b2 (1)!b2 (t )!если a1 (1) = a2 (1), то b1 (1) = b2 (1); a1 (1) = a2 (1)a (2) = a (2) 12если , то b1(t) = b2(t).( a1 (t ) = a2 (t )Определение 2.

Пусть задана д.-функция ϕ: A∞ → B∞. Рассмотрим произвольное словоa = a1a2 ! ak ∈ A* . Определим функцию ϕ a следующим образом: пусть a(1), a(2), …, a(t)…— произвольная входная последовательность. Рассмотримϕ (a1a2…aka(1)a(2)…a(t)…) = b1b2…bkb(1)b(2)…b(t)….Тогда положим ϕ a (a (1)a (2)! a(t )!) = b(1)b(2 )!b(t )! . ϕ a при этом называется остаточнойфункцией для ϕ по слову a ∈ A∗ .Определение 3. Детерминированная функция ϕ : A∞→B∞ называется ограниченно детерминированной, если у неё имеется лишь конечное число различных остаточных функций.Определение 4. Автоматом (инициальным) называется любая шестёрка(A, B, Q, G, F, q0), где A, B, Q — конечные алфавиты, G: A × Q → Q, F: A × Q → B, q0 ∈ Q —начальное состояние.Входом автомата служит последовательность a(1)a(2)a(3)…, a(t)… ∈ A* (конечная илибесконечная), выходом автомата служит последовательность z(t), при этом автомат задаётсясистемой канонических уравнений z (t ) = F (x(t ), q (t − 1)),q (t ) = G (x(t ), q (t − 1)),q (0) = q0 .Определение 5.

Отображение ϕ: A∞ → B∞ называется автоматной функцией, если существует автомат, который реализует это отображение.Утверждение. Функция является автоматной тогда и только тогда, когда она являетсяограниченно детерминированной.Пример. Пусть A = B = Q = {0, 1} и система канонических уравнений выглядит следующим образом: z (t ) = q(t − 1), q(t ) = x(t ), q(0) = 0.39Такой автомат, очевидно, осуществляет отображение 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)0a(1) a(2)Определение 6.

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

ДиаграммаМура однозначно задаёт автомат.§36. Схемы из функциональных элементов и элементов задержки.Автоматность осуществляемых ими отображений.Определение. Схемой из функциональных элементов и элемента задержки называетсясхема из функциональных элементов в функциональном базисе, к которому добавлен элемент, реализующий функцию единичной задержки. В схеме из функциональных элементов иэлементов задержки допускаются ориентированные циклы, но любой ориентированный циклдолжен проходить хотя бы через одну задержку.Пусть A = B = {0, 1}, E2n — множество всех булевых векторов длины n.Теорема 1.

Схема из функциональных элементов и задержки осуществляет автоматноеотображение.Доказательство. 1) Пусть в схеме имеется r элементов задержки. Пусть i-я задержка Riприписана вершине vi, в которую идёт дуга из вершины wi. Для всех i = 1, …, r удалим изСФЭЗ дуги (wi, vi). По определению СФЭЗ в полученном после этого графе не будет ориентированных циклов и он, тем самым будет представлять собой СФЭ. Входами этой СФЭ будут все входы исходной схемы, а также все вершины vi, i = 1, …, r (заметим, что все они различны и отличны от входов исходной схемы).

Выходами полученной СФЭ объявим все выходы исходной схемы и вершины wi, i = 1, …, r. Пусть в исходной схеме выходам приписаныпеременные z1, …, zm, входам — переменные x1, …, xn. Вершинам vi припишем переменныеq'1, …, q'r, а вершинам wi — переменные q1, …, qr. В соответствии с определением функционирования СФЭ, для некоторых функций алгебры логики fi, gj справедливо: zi = f i (x1 ,!, xn , q1′,!, qr′ ), i = 1,!, m,q j = g j (x1 ,!, xn , q1′,!, qr′ ), j = 1,!, r.(1)Естественно считать, что равенства (1) выполняются в каждый момент времени t = 1, 2, 3,…,то есть zi (t ) = f i (x1 (t ),! , xn (t ), q1′ (t ),!, qr′ (t )), i = 1,! m,q j (t ) = g j (x1 (t ), !, xn (t ), q1′ (t ),!, q′r (t )), j = 1,! , r.(2)Так как, в соответствии с каноническими уравнениями элемента единичной задержки еговыход в момент t совпадает с его входом в момент t – 1, то естественно считать, что в исходной схеме q'i (t) = qi (t – 1) при t = 1, 2, … для всех i = 1, …, r, где qi (0) = 0.

Тогда равенства (2)принимают вид (где i = 1, …, m и j = 1, …, r): zi (t ) = f i (x1 (t ),!, xn (t ), q1 (t − 1),!, qr (t − 1)),q j (t ) = g j (x1 (t ),! , xn (t ), q1 (t − 1),!, qr (t − 1)),q j (0) = 0.(3)Полученные равенства определяют функционирование СФЭЗ и называются её каноническими уравнениями.402) Пусть отображение ψ, осуществляемое схемой Σ, задаётся каноническими уравнениями (3). Введём переменные X = (x1, …, xn), Q = (q1, …, qr), Z = (z1, …, zm), принимающиезначения, соответственно в E2n , E2r , E2m .

Положим q0 = (0, …, 0). Тогда (3) можно переписатьв видеZ (t ) = F (X (t ), Q(t − 1)),Q(t ) = G (X (t ), Q(t − 1)),Q(0) = q0 ,где функции F, G не зависят явно от t. Отсюда видно, что отображение, осуществляемое схемой, совпадает с отображением, задаваемым автоматом E2n , E2m , E2r , G, F , q0 , то есть являетсяавтоматной функцией. Теорема доказана.()§37. Моделирование автоматной функции схемой из функциональных элементови элементов задержки.Определение.

Пусть автоматная функция ϕ отображает последовательности в конечномалфавите A в последовательности в конечном алфавите B. Пусть СФЭЗ Σ осуществляет преобразование ψ последовательностей с элементами из E2n в последовательности с элементамииз E2m . Будем говорить, что Σ моделирует ϕ, если существуют отображения (кодирования)K1 : A → E2n и K 2 : B → E2m , сопоставляющие разным элементам разные элементы и обладающие свойством: для любой последовательности P = a(1)a(2)…a(t) в алфавите A, еслиϕ (P) = T = b(1)b(2)…b(t), то ψ (K1 (P)) = K2 (T), где K1 (P) = K1 (a(1))K1 (a(2))…K1 (a(t)),K2 (T) = K2 (b(1))K2 (b(2))…K2 (b(t)).Теорема 2.

Для любой автоматной функции существует моделирующая её СФЭЗ в базисе из функциональных элементов дизъюнкции, конъюнкции, отрицания и элементазадержки.Доказательство. Пусть автоматная функция дана автоматом D = (A, B, Q, G, F, q0). Выберем n, m, r так, что 2n ≥ |A|, 2m ≥ |B|, 2r ≥ |Q|.

Рассмотрим произвольные отображения (кодирования) K1 : A → E2n , K 2 : B → E2m , K 3 : Q → E2r , при которых разные элементы отображаются в разные элементы. Дополнительно потребуем, чтобы K3 (q0) = (0, …, 0). Рассмотримотображения G′ : E2n × E2r → E2r и F ′ : E2n × E2r → E2m такие, что для любых a ∈ A и q ∈ QвыполняетсяG′(K1 (a ), K 3 (q )) = K 3 (G (a, q )), F ′(K1 (a ), K 3 (q )) = K 2 (F (a, q )).(1)~Равенства (1) определяют отображения G' и F' только для пар α~ ∈ E2n , β ∈ E2r таких, что α~~является кодом некоторой буквы из A, а β является кодом некоторой буквы из B. Для ос~тальных пар отображения G' и F' доопределим произвольно.

Пусть 0 = (0,!,0) . Рассмотрим~автомат H = E2n , E2m , E2r , G′, F ′, 0 с каноническими уравнениями()Z (t ) = F ′(X (t ), Q(t − 1)),Q(t ) = G′( X (t ), Q(t − 1)),~Q(0 ) = 0 .(2)Из (1) вытекает, что если автомат D преобразует последовательность P в алфавите A впоследовательность T в алфавите B, то H преобразует код K1 (P) последовательности P в код41K2 (T) последовательности T. Таким образом, достаточно показать, что автоматную функцию,задаваемую равенствами (2), можно реализовать схемой. Так как значением переменной Xявляются наборы длины n из E2n , то её можно рассматривать как набор переменных(x1, …, xn), принимающих значения из E2.

Аналогично для переменных Q и Z. Тогда (2) можно переписать в эквивалентном виде для некоторых функций алгебры логики fi, gj: zi (t ) = f i (x1 (t ),!, xn (t ), q1′ (t ),! , q′r (t )), i = 1,!, m,q j (t ) = g j (x1 (t ),!, xn (t ), q1′ (t ),!, q′r (t )), j = 1,! , r.Тогда можно построить схему из функциональных элементов в базисе {∨,&, } с n + r входами и m + r выходами, реализующую семейство функций zi = f i (x1 ,!, xn , q1′,!, qr′ ), i = 1,!, m,q j = g j (x1 , !, xn , q1′,!, qr′ ), j = 1,!, r.Пусть в этой СФЭ входная переменная q′j приписана вершине vj, а выходная переменная qj— вершине wj. Добавим дугу (wj, vj) и сопоставим вершине vj элемент задержки.

Проделавэто для всех пар q j , q′j ( j = 1,!, r ) , получим СФЭЗ, функционирование которой описываетсяканоническими уравнениями zi (t ) = f i (x1 (t ),!, xn (t ), q1 (t − 1),!, qr (t − 1)), i = 1,!, m,q j (t ) = g j (x1 (t ),!, xn (t ), q1 (t − 1),! , qr (t − 1)), j = 1,!, r ,q j (0 ) = 0.Эта схема является искомой. Теорема доказана.§38. Теорема Мура.

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

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