12. Схемы из функциональных элементов с элементами задержки (СФЭз), автоматность осуществляемых ими отображений. Реализация КАВ СФЭз (Лекции)

Лекция: Схемы из функциональных элементов сзадержками (СФЭЗ), автоматностьосуществляемых ими отображений.Представление КАВ СФЭЗ. Упрощения КАВ.Отличимость и неотличимость состояний КАВ.Теорема Мура о длине слова, отличающего дваотличимых состояния КАВ.Лектор - доцент Селезнева Светлана НиколаевнаЛекции по “Дискретной математике”-2,1-й курс, группа 141,факультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mathcyb.cs.msu.suСФЭЗУпрощение КАВСФЭ с задержкамиСхемой из функциональных элементов с задержками(СФЭЗ) S(x1 (t), . . .

, xn (t); y1 (t), . . . , ym (t)) в базисе {&, ∨, ¬}называется1) ориентированный граф G = (V , E ) с возможнымиориентированными циклами, все вершины которого имеютполустепень захода не больше двух;2) вершины с нулевой полустепенью захода называютсявходными и им приписываются входные переменныеx1 (t), . . . , xn (t);3) некоторым вершинам с полустепенью захода, равнойединице, приписывается элемент единичной задержки z,причем в любом ориентированном цикле графа G должна бытьхотя бы одна вершина с приписанным элементом единичнойзадержки;СФЭЗУпрощение КАВСФЭ с задержками4) остальным вершинам с полустепью захода, равной единице,приписываются элементы отрицания ¬;5) каждой вершине с полустепью захода, равной двум,приписывается или элемент конъюнкции &, или элементдизъюнкции ∨;6) некоторые (в том числе и входные) вершины называютсявыходными и им приписываются (различные) выходныепеременные y1 (t), .

. . , ym (t).СФЭЗУпрощение КАВТеорема о функционировании СФЭЗТеорема 1. Каждая СФЭЗ S(x1 (t), . . . , xn (t); y1 (t), . . . , ym (t))осуществляет автоматное отображение входовx1 (t), . . . , xn (t) в выходы y1 (t), . . . , ym (t).Доказательство. Рассмотрим граф G = (V , E ) СФЭЗ S.Пусть v1 , . . . , vk ∈ V – все вершины, которым приписанэлемент единичной задержки z. Рассмотрим вершину vi , в неевходит одна дуга из вершины, которую обозначим vi0 .

Удалимэту дугу из графа. Вершине vi0 припишем новую выходнуюпеременную qi (t). Вершина vi станет входной, ей припишемновую входную переменную pi (t). Заметим, что т.к. в любомориентированном цикле графа G хотя бы одной вершине былприписан элемент z, выполнив такое преобразование длявершин v1 , . . . , vk , мы разорвем все ориентированные циклы.СФЭЗУпрощение КАВТеорема о функционировании СФЭЗДоказательство (продолжение).

В результате получили СФЭЗ(без задержек) S 0 . Запишем функции алгебры логики, которыереализуются в ее выходах:yj (t) = Fj (x1 (t), . . . , xn (t), p1 (t), . . . , pk (t)), 1 ≤ j ≤ m;qi (t) = Gi (x1 (t), . . . , xn (t), p1 (t), . . . , pk (t)), 1 ≤ i ≤ k.Из описания функции единичной задержки верно, чтоpi (t) = qi (t − 1), qi (0) = 0. Поэтому yj (t) = Fj (x1 (t), . . . , xn (t), q1 (t − 1), . .

. , qk (t − 1)), 1 ≤ j ≤ m;q (t) = Gi (x1 (t), . . . , xn (t), q1 (t − 1), . . . , qk (t − 1)), iqi (0) = 0,1 ≤ i ≤ k.Т.е. построили канонические уравнения. А значит,преобразование – автоматное.СФЭЗУпрощение КАВТеорема о представлении КАВ СФЭЗТеорема 2. Каждый КАВ A = (A, B, Q, ϕ, ψ, q∗ ) может бытьреализован схемой с задержками в базисе {&, ∨, ¬} принекотором кодировании элементов из множеств A, B, Qвекторами из нулей и единиц.Доказательство. Пусть |A| = r , |B| = s, |Q| = t.Закодируем элементы множества A векторами(x1 , x2 , .

. . , xn ) ∈ {0, 1}n , где n = dlog2 r e;элементы множества B – векторами (y1 , y2 , . . . , ym ) ∈ {0, 1}m ,где m = dlog2 se;элементы множества Q – векторами (q1 , q2 , . . . , qk ) ∈ {0, 1}k ,где k = dlog2 te, причем начальное состояние q∗ закодируемнулевым вектором (0, . .

. , 0).СФЭЗУпрощение КАВТеорема о представлении КАВ СФЭЗДоказательство (продолжение). КАВ A можно задатьканоническими уравнениями: y (t) = ϕ(x(t), q(t − 1));q(t) = ψ(x(t), q(t − 1));q(0) = q∗ .Перепишем эти уравнения для кодов элементов множествA, B, Q. При этом функции ϕ и ψ преобразуются в векторыфункций алгебры логики (F1 , . . . , Fm ) и (G1 , . . . , Gk ): yj (t) = Fj (x1 (t), . . . , xn (t), q1 (t − 1), .

. . , qk (t − 1)), 1 ≤ j ≤ m;q (t) = Gi (x1 (t), . . . , xn (t), q1 (t − 1), . . . , qk (t − 1)), iqi (0) = 0,1 ≤ i ≤ k.(1)СФЭЗУпрощение КАВТеорема о представлении КАВ СФЭЗДоказательство (продолжение). Теперь построим СФЭ (беззадержек) S 0 в базисе {&, ∨, ¬}, реализующую на выходахy1 (t), . . . , ym (t), q1 (t), . . . , qk (t) функции алгебры логики:yj (t) = Fj (x1 (t), . . . , xn (t), q1 (t − 1), . . . , qk (t − 1)), 1 ≤ j ≤ m;qi (t) = Gi (x1 (t), . . .

, xn (t), q1 (t − 1), . . . , qk (t − 1)), 1 ≤ i ≤ k.После чего соединим в схеме S 0 выход qi (t) со входомqi (t − 1) через элемент единичной задержки z для всехi = 1, . . . , k.Получим СФЭЗ S, осуществляющую автоматное отображение всоответствии с каноническими уравнениями (1).СФЭЗУпрощение КАВФункции ϕ̄ и ψ̄Пусть A = (A, B, Q, ϕ, ψ, q1 ) – КАВ.Определим по функциям ϕ и ψоднозначные функции ϕ̄ : A∗ × Q → B ∗ и ψ̄ : A∗ × Q → Q.Для всех a ∈ A, α = ai1 ai2 . . . aik ∈ A∗ и q ∈ Q положим:ϕ̄(a, q) = ϕ(a, q);ϕ̄(ai1 ai2 . .

. aik , q) = ϕ(ai1 , q)ϕ̄(ai2 . . . aik , ψ(ai1 , q));ψ̄(a, q) = ψ(a, q);ψ̄(ai1 ai2 . . . aik , q) = ψ̄(ai2 . . . aik , ψ(ai1 , q)).СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikСФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 .

. . aik ∈ A∗СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 . . . aik ∈ A∗СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1qai2...aikα = ai1 ai2 . . . aik ∈ A∗СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26q...aikα = ai1 ai2 . .

. aik ∈ A∗СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 . . . aik ∈ A∗6bi1 = ϕ(ai1 , q)qСФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 . . . aik ∈ A∗6bi1 = ϕ(ai1 , q)q?bi1СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 . .

. aik ∈ A∗6bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)q?bi1СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai2...aikα = ai1 ai2 . . . aik ∈ A∗6-q?bi1qi2bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...aikα = ai1 ai2 . .

. aik ∈ A∗6-q?bi1qi2bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...aikα = ai1 ai2 . . . aik ∈ A∗6-q?bi1qi2bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . .

. aik ∈ A∗6-q?bi1aik?bi2qi2bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . . . aik ∈ A∗6-q?bi1aik?bi2qi2bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . . . aik ∈ A∗6bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )- -q?bi1aik?bi2qi2qi3СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 .

. . aik ∈ A∗6- - ...q?bi1aik?bi2...qi2qi3. . .bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...66- - ...q?bi1α = ai1 ai2 . . . aik ∈ A∗aik?bi2...qi2qi3. . . qikbi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...66- - ...q?bi1α = ai1 ai2 . .

. aik ∈ A∗aik?bi2...qi2qi3. . . qikbi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...bik = ϕ(aik , qik )СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . . . aik ∈ A∗aik66bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...bik = ϕ(aik , qik )- - ...q?bi1??bi2...bikqi2qi3. . . qikСФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . . .

aik ∈ A∗aik66bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...bik = ϕ(aik , qik )qik+1 = ψ(aik , qik )- - ...q?bi1??bi2...bikqi2qi3. . . qikСФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 .

. . aik ∈ A∗aik66- - ...-q?bi1?bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...bik = ϕ(aik , qik )qik+1 = ψ(aik , qik )?bi2...bikqi2qi3. . . qikqik+1 = ψ̄(α, q)СФЭЗУпрощение КАВСодержательный смысл функций ϕ̄ и ψ̄Содержательный смысл функций ϕ̄ и ψ̄.t0 + k − 1t0ai1ai26...α = ai1 ai2 . . . aik ∈ A∗aik66- - ...-q?bi1?bi1 = ϕ(ai1 , q) qi2 = ψ(ai1 , q)bi2 = ϕ(ai2 , qi2 )qi3 = ψ(ai2 , qi2 )...bik = ϕ(aik , qik )qik+1 = ψ(aik , qik )?bi2...bikqi2qi3. .