FAQ, страница 3

количество входов и количество выходов.AlecSoft design © 1996Сложностью L(S) функциональной схемы S называется число функциональных элементов, еесоставляющих.Вопрос об алгоритме A синтеза СФЭ для произвольной булевой функции n аргументов. Функции Шеннона LA(n) = sup{LA(f), f - функция n аргументов}.23. Дешифратор. Асимптотика сложности дешифратора. Верхняяоценка сложности реализации произвольной булевой функции.Дешифратором Dn называется произвольная СФЭ, имеющая n входов и 2n-1 выходов и реализующая вычисление 1 на выходе №M и 0 на всех остальных выходах, если на входы подана двоичная запись числа M.L(Dn)  2n.СДНФ для произвольной булевой функции можно реализовать простейшим способом со сложностью LA(n)  n2n.24. Мультиплексор.

Верхняя оценка сложности мультиплексора.25. Шифратор. Верхняя оценка сложности шифратора.Дешифратором Sn называется произвольная СФЭ, имеющая 2n-1 входов и n выходов и реализующая вычисление двоичной записи числа M, если на входе №M подана 1 и 0 подан на всех остальных входах.Одна из возможных реализаций шифратора основана на следующей простой идее. Чтобы бит nчисла M оказался равным 1  чтобы была подана 1 на вход, номер которого имеет 1 в n-бите двоичной записи.

Поэтому этот выход вычисляется как дизъюнкция всех битов №k входа, в двоичнойзаписи номера которых k этот бит n равен 1. Т.е. достаточно на выход 0 подать дизъюнкцию входов№№1,3,5,...; на выход №1 - дизъюнкцию №№2,3,6,7,... и т.д.; на выход №(n-1) - дизъюнкцию №№2n1 n-1,2 +1,...2n-1.Сложность этой реализации L(S) = n2n-1.26. Сумматор. Верхняя оценка сложности сумматора.Дешифратором n называется произвольная СФЭ, имеющая 2n входов и n выходов и реализующая вычисление двоичная запись числа (A+B)(mod 2n), если на первую группу из n входов поданадвоичная запись числа A и на вторую - двоичная запись числа B.Существует схема из 9 элементов, реализующая одновременное вычисление суммы трех битовпо mod 2 и бита переноса (С.В. Яблонский, c.

262, рис. 28). Поэтому можно указать реализациюсумматора с L(n) = 9n.27. Понятие ограниченно-детерминированной функции.Пусть отображение F имеет аргументом некую входную последовательность {a(t), t  N} букв изалфавита A и вычисляет выходную последовательность {b(t), t  N} букв из алфавита B. При этомбудем рассматривать только такие отображения, где каждый элемент выхода не зависит от следующих элементов входа, т.е.

b(t) есть функция {a(1),...,a(t)}. Такие F называются детерминированнымиавтоматами.Детерминированные автоматы (функции) задаются с помощью деревьев. Каждое поддерево скаким-то корнем  естественным образом определяет соответствующую ему детерминированнуюфункцию F. Два поддерева называются эквивалентными, если соответствующие функции совпадают.

Число r (мощность множества) классов эквивалентности поддеревьев называется весом детерминированной функции (автомата, дерева).AlecSoft design © 199628. Конечные автоматы и автоматные функции. Представление конечного автомата диаграммой Мура.

Автомат единичной задержки.Автомат F называется конечным (ограниченно-детерминированным), если он имеет конечныйвес r.Ограниченно-детерминированная функция с весом r задается с помощью специального графа с rвершинами - диаграммы Мура. Одна из вершин определена в качестве начальной; из каждой вершины исходит N = Card A ребер, ребрам приписаны пары (0,0), (1,1), ... , (N-1,N-1), i  B.Канонические уравнения для о.-детерминированного автомата рекуррентным образом определяют функцию:b(t) = b(a(t),q(t-1)); q(t) = q(a(t),q(t-1)); q(0) = qo.Автомат единичной задержки по входной последовательности вида {a,b,c,...} вычисляет{0,a,b,c,...}, т.е. определяется свойством b(t) = b(t-1), b(1) = 0 и может быть реализован следующимиканоническими уравнениями: b(t) = q(t-1); q(t) = a(t); q(0) = 0.29. Преобразование периодических последовательностей автоматными функциями.Лемма.

Пусть на вход F - конечного автомата с  состояниями подается последовательность a(t)с периодом Т (т.е. a(t+Т) = a(t) начиная с некоторого момента Т0). Тогда последовательность на выходе имеет период Т’=T’ , где ’  .Рассмотрим моменты времени Т0, Т0+Т, ...

, Т0+Т. Среди +1 состояния q(Т0 ), q(Т0+Т), ... ,q(Т0+Т) найдутся два одинаковых: q(Т0+iТ) = q(Т0+jТ) при j > i. Тогда очевидно, вычисление в момент Т0+jТ полностью повторяет вычисление в момент Т0+iТ  выходная последовательность имеет период Т’ = Т(j - i).30. Схемы из функциональных элементов и элементов задержки.Автоматность осуществляемых ими отображений.СФЭ, дополненные элементами единичной задержки могут реализовывать любые конечные автоматы. При этом допускаются ориентированные циклы, содержащие хотя бы один элемент единичной задержки.Покажем, что любая такая схема S осуществляет некоторое автоматное отображение.

Будем считать, что входом и выходом автомата F(S) являются соответственно совокупность входов a(t) и совокупность выходов b(t) схемы S. Совокупность входов элементов единичной задержки из S обозначим q(t), а совокупность выходов этих элементов - q(t-1). Тогда часть S, являющаяся СФЭ (S\{элты ед.з.}), в любой момент времени осуществляет вычисление b(t)=b(a(t),q(t-1)) и q(t)=q(a(t),q(t-1)).Таким образом, S осуществляет ограниченно-детерминированное отображение F: a  b.31. Моделирование автоматной функции схемой из функциональныхэлементов и элементов задержки.Любую ограниченно-детерминированную функцию F можно вычислить с помощью СФЭ, пополненной элементами единичной задержки.

Пусть F задана каноническими уравнениямиb(t)=b(a(t),q(t-1)) и q(t)=q(a(t),q(t-1)).Построим СФЭ, которая в каждый момент времени вычисляет на выходах b(t) и q(t), принимаяна входах a(t) и q(t-1). Соединим выходы, помеченные q(t) с входами, помеченными q(t-1) элементами единичной задержки. Очевидно, что построенная S моделирует F.AlecSoft design © 199632. Отсутствие полной конечной системы автоматных функций вслучае схем без обратной связи.37. Алфавитное кодирование. Схемы кодирования, обладающиесвойством префикса. Неприводимые коды и их свойства.Пусть фиксированы алфавиты A и B. Алфавитным кодированием называется замена символов Aна cлова (конечные последовательности) символов B, т.е.

любое инъективное отображение f: (ai A)  (Bi  B). Применение f r каждой букве слова (сообщения) A* кодирует это сообщение в B* =f(A*).Если B={0,1}, то кодирование называется двоичным. Если длины кодовых слов одинаковы: | Bi |= const, то код называется равномерным.Требование однозначности декодирования: по (закодированной) последовательности B* = f(A*)однозначно восстанавливается (оригинальная) последовательность A*.Код называется префиксным, если ни одно из слов Bi не является началом другого.

Очевидно,любой префиксный код однозначен (свойство префикса есть достаточное условие декодируемости).Слово в алфавите В называется неприводимым, если (1) оно допускает неоднозначное декодирование; и (2) при удалении из него любого подслова оно допускает однозначное декодирование илине допускает никакого.Рассмотрим два разбиения слова В на элементарные слова - Т1(нижнее) и Т2(верхнее) и возьмемпроизведение этих разбиений - Т = Т1Т2. Отрезки этого разбиения разделим на два класса. Отрезками первого рода назовем элементарные слова; все остальные назовем отрезками второго рода. Ясно, что каждый отрезок первого рода входит только в одно разбиение, а слова второго рода являются одновременно началами и концами элементарных кодов разных разбиений.Лемма. Любые два отрезка второго рода  и ’ в неприводимом слове В различны.

Предположим противное, т.е. B = B’B’’B’’’. Утверждается, что слово B’B’’’ допускает неоднозначноедекодирование - т.к. в каждом из четырех случаев расположения  и ’ оказывается возможнымвыкинуть середину B’’ , сохранив разбиения Т1 и Т2.Рассмотрим нетривиальное разложение элементарного кодового слова вида В i =<w кодовыхслов:D1...Dw>’ (предполагается, что  не оканчивается и ’ не начинается на кодовое слово). Введем характеристику кода W = max w , взятый по всем словам Вi и по всем разложениям каждогослова.38.

Теорема Маркова о взаимной однозначности алфавитного кодирования.Теорема (Марков). Для всякого алфавитного кодирования С существует натуральное ( W  1 )( L  r  1 )  , такое, что проблема однозначности С сводится к проблемеN0  N *  2однозначности кодирования слов в алфавите А длины не более No.Пусть кодирование С неоднозначно. Для доказательства достаточно установить, что можнонайти такое слово В с двумя различными расшифровками А, А’ длины не более N*. Возьмем произвольное неоднозначно декодируемое слово B* и выделим из него неприводимое B.Все отрезки второго рода в В различны, их число р не превосходит числа возможных начал элементарных кодовых слов : р  (l1-1)+ (l2-1)+...+ (lr-1) = L - r, где L = li. Отрезки второго рода i разбивают В не более чем на L-r+1 подслов (групп отрезков второго рода), некоторые из которых могут оказаться пустыми.Подсчитаем число элементарных слов, входящих в разбиения.

С каждым куском связаны w  Wэлементарных кодов одного разбиения и один элементарный код другого (чередуясь через один кусок). Отсюда получается оценка для No.AlecSoft design © 199640. Неравенство Макмиллана.Для однозначного кодирования f с длинами кодовых слов li = |Bi| выполняется соотношение q  li  1 , где q = |B|.i41. Существование кода со свойством префикса в классе кодов с заданными длинами кодовых слов.Пусть задан некоторый набор длин кодовых слов li, удовлетворяющий неравенству Макмиллана(Крафта). Тогда с помощью простого алгоритма можно построить кодовое дерево с заданным количеством листьев на каждом ярусе.Таким образом, имея код с заданным набором длин кодовых слов, можно без ограничения общности считать его префиксным.42.

Коды с минимальной избыточностью (оптимальные коды). Существование приведенного кода.Стоимостью кода называется матожидание длины кодового слова. Если известно распределениевероятностей входных букв P: p1, p2, ... , pr , то стоимость кода С = <B1 B2 ... Br> вычисляется какL( P ,C )  ir1 li pi, где li = |Bi|.В оптимальном коде менее вероятный символ не может кодироваться более коротким словом,т.е. pk > pm  lk  lm.В оптимальном коде всегда найдутся два слова наибольшей длины43.