автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Комбинаторно-информационная оценка сложности при синтезе дискретных управляющих устройств

ВВЕДЕНИЕ . Ч

ТАБЛИЦА ОБОЗНАЧЕНИЙ .2V

УКАЗАТЕЛЬ ТЕРМИНОВ.

Глава I АЛГЕБРАИЧЕСКИЕ ОСНОВЫ ПОНЯТИЯ ЭНТРОПИИ.

1.1. Основные определения

1.2. Свойства энтропии для разбиений

1.3. Отношение квазинезависимости для разбиений

1.4. Отношение независимости для разбиений . .3<?

1.5. Энтропия как полуоценка для решетки разбиений

1.6. Функция расстояния между разбиениями .^

Выводы .М

Глава II ИНФОРМАЦИОННЫЕ СВОЙСТВА СИСТЕМЫ РАЗБИЕНИЙ .$

2.1. Основные определения

2.2. Независимость и взаимная независимость систем разбиений

2.3. Изоморфизм систем разбиений

2.4. Отношение порядка в системе разбиений

2.5. Подструктуры

2.6. Информационная связка. .п

Выводы

Глава III ИНФОРМАЦИОННЫЕ СООТНОШЕНИЯ ДЛЯ ПАР

РАЗБИЕНИЙ .9?

3.1. Основные определения

3.2. Информационные соотношения для каналов

3.3. Свойства информационной связки для булевых функций . .Ш

Выводы . .ш

Глава 1У ШЫНАТОРШ-ИНФОРМАЩОННАЯ ОПЕНКА СЛОЖНОСТИ

ПРИ СИНТЕЗЕ ДИСКРЕТНЫХ УПРАВЛЯЮЩИХ УСТРОЙСТВ.ИЗ

4.1. Оценка сложности булевых функций . .И

4.2. Декомпозиция конечных автоматов по ИС

4.3. Реализация булевых функций на сети мультиплексоров

Выводы .¿

Актуальность проблемы. При анализе и синтезе системных объектов часто возникает надобность характеризовать их через концепцию сложности. Сложность позволяет нам сравнивать между собой объекты различного характера и принципа работы. На основе оценок сложности удается часто эффективнее решить различные оптимизационные задачи, особенно в тех случаях, когда сталкиваемся с трудоемкими задачами логико-комбинаторного характера. Понятие сложности приобретает большое значение при решении задач синтеза дискретных управляющих устройств (ДУУ). Имея оценки сложности для математических моделей ДУУ, которые хорошо коррелируются со сложностью реальных схемных или программных реализаций, мы можем направить процесс синтеза, раличая перспективные варианты от неперспективных и тем самым получить более оптимальный конечный результат. Особенно важно это при декомпозиционном синтезе ДУУ, ибо проблема нахождения оптимальной декомпозиции является одной из труднейших в процессе проектирования ДУУ. Роль формализованных оценок сложности возрастает и в связи с переходом на автоматизированное проектирование, которое исключает интуитивные критерии.

Среди различных возможностей обоснования понятия сложности, предназначенного для решения вышеназванных проблем, одним из наиболее перспективных является информационный подход, который отличается большой универсальностью и общностью. Но до сих пор отсутствовало математическое обоснование соответствующей оценки сложности. Хотя уже в начале 60-х годов известным японским ученым Са-тоси Ватанабе была выдвинута идея использовать для характеризации сложности системного объекта информационную завис&юсть между его компонентами / I, 2 /, до сих пор практических численных результатов по этому методу получить не удалось, ибо использованный вероятностный подход к определению понятия информации не подходит для изучения свойств единичных объектов, которые не имеют статистического характера. Также при этом подходе не учитываются все необходимые взаимосвязи между компонентами рассматриваемого объекта для получения оценки, отражающей сложность известных на практике реализаций. Зато в алгебраической структурной теории автоматов Дж. Хартманиса и Р. Стирнза / 3 /, представляющей собой развитый и перспективный аппарат декомпозиции ДУУ, предложен необходимый комбинаторный подход к определению понятия информации, используя понятие разбиения в качестве алгебраического эквивалента информации. Однако при сравнении разбиений они остались только на качественном уровне , используя для этой цели отношение частичного порядка. При таком подходе невозможно оценивать количественно информационную зависимость в системе декомпозиционных разбиений. Следовательно, отсутствует и количественная оценка эффективности для декомпозиции. Из вышеприведенного следует, что выработка математического аппарата комбинаторной теории информации, позволяющей получить универсальные оценки сложности для широкого класса различных ДУУ, достаточно хорошо согласующейся с практическими оценками сложности, имеет большую актуальность.

Целью данной диссертации является развитие информационных методов оценки сложности ДУУ и создание на этой основе эффективных алгоритмов и оптимизационных процедур для их автоматизированного синтеза.

Методы исследования. В работе использовался аппарат теории информации, теории решеток, теории дискретных функций и алгебраической структурной теории конечных автоматов.

Основные научные результаты настоящей работы следующие:

1. Показано, что разбиение как алгебраическая интерпретация информации имеет однозначно определенную количественную оценку в виде энтропии.

2. Выявлены информационные свойства систем разбиений и введено понятие информационной связки СИС) для систем разбиений. Показано, что ИС отражает сложность объектов, представимых в виде систем разбиений.

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

4. Показано, что на основе ИС могут быть найдены оценки сложности для широкого класса ДУУ, имеющие высокую корреляцию со сложностью реальных аппаратных или программных реализаций и позволяющие направить процесс декомпозиционного синтеза.

Практическая ценность работы. Разработанный в диссертации метод комбинаторно-информационной оценки сложности ДУУ позволяет начиная с ранних стадий в процессе синтеза с высокой степенью достоверности оценить альтернативные варианты по отношению^конечной практической реализации. На базе комбинаторно-информационного критерия в работе предложен метод нахождения оптимальной декомпозиции конечного автомата и способ разложения булевых функций для получения наипростейших реализаций на сети мультиплексоров. Предложенные методы и алгоритмы реализованы в системе автоматизированного проектирования ДУУ ДЕМЕЛОС, разработанной на кафедре ЭВМ Таллинского политехнического института. Созданный комплекс программ применяется в инженерной практике проектирования, способствуя экономии материальных и трудовых ресурсов.

Апробация работы» Научные и практические результаты диссертации докладывались и обсуждались на:

- постоянно действующем семинаре "Теория проектирования дискретных устройств" в Таллинском политехническом институте (Таллин,

1979);

- УШ Всесоюзном совещании по проблемам управления (Таллин,

1980);

- XXIII Всесоюзной школе-семинаре им. М.А. Гаврилова по теории дискретных систем (Таллин, 1981);

- научном семинаре Института проблем передачи информации АН СССР (Москва, 1981);

- научном семинаре по синтезу ДУУ Института проблем управления (Москва, 1984);

- семинаре по алгебре Тартуского государственного университета (Кяэрику, 1982);

- Всесоюзной конференции "Проблемы преобразовательной техники" (Киев, 1983).

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

выводы

I) Показано, что оценка внутренней сложности булевых функций на базе ИС имеет сильную корреляцию со сложностью известных на практике реализаций.

II) Предложен метод нахождения декомпозиции конечного автомата по минимальной ИС, повышающий сильно эффективность декомпозиционного синтеза ДУУ. В том числе предложен метод решения декомпозиционных неравенств, являющийся основой для итеративной декомпозиции конечных автоматов, который позволяет значительно сократить перебор альтернативных вариантов.

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

ЗАКЛЮЧЕНИЕ

В работе получены следующие основные результаты:

Ш Показано, что разбиение на конечном множестве как алгебраическая интерпретация информации имеет однозначно определенную количественную оценку в виде энтропии, позволяющую в значительной мере расширить сравнимость разбиений и количественно оценить силу взаимосвязей в единичном объекте.

II) Выявлены информационные свойства систем разбиений и введено понятие информационной связки (ИС) для систем разбиений, которое количественно учитывает всевозможные взаимозависимости в системе разбиений. Показано, что ИС отражает сложность объектов, представимых в виде систем разбиений.

СIII) Выявлены информационные соотношения в системе пар разбиений и обобщено- понятие ИС для систем пар разбиений, что служит основой при оценке сложности дискретных функций.

С1У) Показано, что оценка внутренней сложности булевых функций на базе ИС имеет сильную корреляцию со сложностью известных на практике аппаратных и программных реализаций.

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

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

1. Watanabe S., 1.formation Theoretical Anal/sis of Multivariate Correlation, IBM Journal of Res. and Development, 1960, 4-, no. 1, 66-82.

2. V/atanabe S., Knowing and Guessing, John Wiley and Sons, Inc., New York, 1969.

3. Hartmanis, J,, Stearns, R.E., Algebraic Structure Theory of Sequential Machines, Prentice-Hall, Inc. Englewood Cliffs, New York, 1966.

4. Месарович M., Такахара Я., Общая теория систем: математические основы, Изд-во "Мир", М., 1978.

5. Колмогоров А.Н., Три подхода к определению понятия "количество информации", Проблемы передачи информации, 1965, I, № I, З-И.

6. Колмогоров А.Н., К логическим основам теории информации и теории вероятностей, Проблемы передачи информации, 1969, 5, № 3, 3-7.

7. Solomonoff R.J., A Formal Theory of Inductive Inference. Part I, Inform, and Control, 1964-, 7, 1-22.

8. Chaitin G.J., On the Length of Programs for Computing Finite Sequences, Journal of ACM, 1966, 13, no. 54-7- 569.

9. Звонкин А.К., Левин Л.А., Сложность конечных объектов и обоснование понятий информации и случайности с помощью теорииалгоритмов, Успехи мат. наук, 1970, 25, № б, 85-127.

10. Chaitin G.J., Algorithmic Information Theory, ГВМ Journal of Res. and Development, 1977, 21, no. 4, 350-359.

11. Dies J.-E., Information et complexité, Ann. Inst. Henri Poincaré, 1978, 14, no. 1, 113-118.

12. Колмогоров A.H., Комбинаторные основания теории информации и исчисления вероятностей, Успехи мат. наук, 1983, 38, № 4, 27-36.

13. Шеннон К.Э., Синтез двухполюсных переключательных схем. В сб. Работы по теории информации и кибернетике, Изд-во иностр. лит., 1963.

14. Лупанов О.Б., 0 сложности реализации функций алгебры логики релейно-контактными схемами, Проблемы кибернетики, 1964, II, 25-47.

15. Шоломов Л.А., Критерии сложности булевых функции, Проблемы кибернетики, 1966, 17, 91-127.

16. Pippenger N., Complexity Theory, Scientific American, 1978, 238, no. 6, 90-100.

17. Nakamura Y., Entropy and Semivalu^iations on Semilafctices, Ködai Math. Sem. Rep., 1970, 22, 443-468.

18. Birkhoff G., Lattice Theory, Amer. Math. Soc. Colloq. Publ., 1948, 25.

19. Ingarden R.S., Urbanik K., Information without Probability, Colloqium. Mathematicum, 1962, 9, Fasc. 1, 131-150.

20. Ingarden R.S., Simplified Axioms for Information without Probability, Roczniki Polskiego Towarzysfcwa maternatycznego, 1965, 9, Séria I, Prace Matematyczne, 273-282.

21. Гоппа В.Д., Невероятностная взаимная информация без памяти, Problems of Control and Information Theory, 1975» 4(2), 97-102.

22. Emptoz H,, Nonprobabilistic Entropies and Indétermination Measures in the Setting of Fuzzy Sets Theory, Fuzzy Sets and Systems, 1981, 5, no.3,307-317.

23. Ore 0., Theory of Equivalence Relations, Duke Math. Journal, 1942, 9, 573-628.

24. Dubreil P., Dubreil-Jacotin M.-L., Theorie algebr^ique des relations d'equivalence, Journal de Mathématiques, 1939, 18, 63-95.

25. Whitman Ph. M., Lattices, Equivalence Relations, and Subgroups, Bull. Amer. Math. Soc., 1946, 52, 507-522.

26. Sachs D., Partition and Modulated Lattices, Pacific J.P. Math., 1961, 11, 325-345.

27. Pudlâk P., Tuma J., Every Finite Lattice can be Embedded in the Lattice of All Equivalences over a Finite Set, Algebra Universalis, 1980, 10, 74-95.

28. Boltzmann L., Vorlesungen über Gastheorie, Leipzig, 1896-1898.

29. Шеннон К.Э., Математическая теория связи. В сб. Работы по теории информации и кибернетике, Изд-во иностр. лит., 1963.

30. Horibe Г., A Note on Entropy Metrics, Inform, and Control, 197З, 22, 403-404.

31. Тани Х.И., Оценка структуры по изменению усредненной энтропии, Третий международный симпозиум по теории информации, Тезисы докладов, часть I, АН СССР, АН ЭССР, Москва-Таллин, 1973.

32. Jakobson G.E., Choosing a Structure of Automata Network According to the Average Entropy of Internal States, The Third International Symposium on Information Theory, Abstracts of papers, part I, Tallinn-Moscow, 1973«

33. Jakobson G.E., Keevallik A.E., Optimization of the Structure of Discrete Control Systems, Proceedings of the 8-th Jugoslav International Symposium on Information Processing, Bled, 1973.

34. Тани Х.И., Усредненные информационные оценки дискретных преобразователей, Дискретные системы, Рига, 1974, № 5, 276-282.

35. Боголюбов И.Н., Воронцова И.П., Овсиевич Б.Л., Об одном подходе к выбору структур систем управления, Изв. АН СССР "Техническая кибернетика", 1974, № 3, 150-155.

36. Кенгерлинский Г.А., Информационный подход к декомпозиции сложных систем, Изв. АН СССР "Техническая кибернетика", 1978, № I, I2I-I28.37» Krohn К., Rhodes J., Complexity of Finite Semigroups, Annals of Mathematics, 1968, 88, no. 1, 128-160.

37. Rhodes J., The Fundamental Lemma of Complexity for Arbitrary Finite Semigroups, Bull. Amer. Math. Soc., 1968, 74, no. 6, 1104-1109.

38. Лаусмаа T.M., Информационная характеристика системы пар разбиений на конечном множестве, Изв. АН ЭССР, Физ. Матем., 1979, 28, № 4, 338-345.

39. Кеэваллик А.Э., Лаусмаа Т.М., Информационный критерий выбора декомпозиции дискретных автоматов, УШ Всесоюзное совещание по проблемам управления, Тезисы докладов, Таллин, 1980, кн.: 3, 760-761.

40. Лаусмаа Т.М., Информационная оценка булевых функций, Изв. АН ЭССР, Физ. Матем., 1980, 29, № 4, 349-355.

41. Лаусмаа Т.М., Количественная информационная мера для пар разбиений, Изв. АН ЭССР, Физ. Матем., 1981, 30, № 3, 226-233.

42. Лаусмаа Т.М., Об учитывании симметрии представления при информационной оценке дискретных функций, Изв. АН ХСР, Физ. Ма-тем., 1981, 30, № 4, 310-318.

43. Лаусмаа Т.М., Об информационной оценке сложности силовых преобразователей, В кн.: Проблемы электромагнитной совместимости силовых полупроводниковых преобразователей, Таллин, АН ЭССР, 1982, 68-69.

44. Лаусмаа Т.М., Об информационных свойствах разбиения, Изв. АН ЭССР, Физ. Матем., 1982, 31, № 4, 390-398.

45. Лаусмаа Т.М., Об алгебраических основах понятия энтропии, Изв. АН ЭССР, Физ. Матем., 1983, 32, № 2, 128-134.

46. Лаусмаа Т.М., Комбинаторно-информационная оценка сложности силовых полупроводниковых преобразователей, В кн.: Проблемыпреобразовательной техники У1, Киев, 1983, 17-20.

47. Gibbs J.W., Elementary Principles in Statistical Mechanics, Yale University Press, New Haven, Conn., 1902,

48. Улиг Д., О связи между сложностью схемной реализации функций алгебры логики и числом их подфункций, Проблемы кибернетики, 1973, 26, 183-201.

49. Яблонский С.В., Об алгоритмических трудностях синтеза минимальных контактных схем, Проблемы кибернетики, 1959, 2, 75-121.

50. Страздинь И.Э., Таблицы типов булевых функции четырех переменных, (Редколлегия ж. "Автоматика и вычисл. техн." АН Латв. ССР) Рига, 1974, Рукопись деп. в ВИНИТИ 3 июня 1974 г., № 1495-74 Деп.

51. Lee C.Y., Representation of Switching Circuits by Binary-Decision Programme, The Bell syst. Techn. Journal, 1959»38, no. 985-999»

52. Leung-Yan-Cheong S.K., Cover T.M., Some Equivalences between Shannon Entropy and Kolmogorov Complexity, IEEE Trans, on Inform. Theory, 1978, IT-24, no. 3, 331-338.

53. Кеэваллик А.Э., Теорема декомпозиции конечных автоматов, Автоматика и вычислительная техника, 1974, № I, 17-24.57«Лейс П., Салум К., Итеративный метод декомпозиции конечных автоматов, Труды Таллинского политехнического института, 1983, 81-88.

54. Yay S.S., Tang С.К., Universal Logic Modules and Their Applications, IEEE Trans, on Сотр., 1970, C-19, no. 2, 141-149.

55. Voith R.P., ULM Implieants for Minimization of Universal Logic Module Circuits, IEEE Trans, on Сотр., 1977, C-26, no. 5, 417-424.

56. Бутов А.А., Синтез одновыходных комбинационных схем с использованием мультиплексоров, Автоматика и вычислительная техника, 1978, № 3, 6-13.

57. Almaini А.Е., Sequential Machine Implementations Using Universal Logic Modules, IEEE Trans, on Сотр., 1978, C-27, no. 10, 951-960.