Аннотация:В дипломной работе Юлии Ковтун рассматривается задача синтеза булевых операторов плоскими схемами и многослойными плоскими схемами. Отличие от схем из функциональных элементов рассматриваемых схем состоит в том, что плоские схемы учитывают разводку проводов. Это особенно актуально, поскольку интересные для практики автоматные операторы реализуются схемами, в которых провода занимают большую площадь, чем функциональные элементы.
В работе реализуются два автоматных оператора. Первый из них – это модель компьютерной памяти. Показано, что реализация плоскими схемами, т.е. когда провода проводятся в той же плоскости, что функциональные элементы, в 2 или 3 раза хуже по площади, чем при реализации многослойными плоскими схемами.
Второй автоматный оператор реализуется только в многослойными плоскими схемами и используется в кодах исправляющих ошибки. Это процедура поиска Ченя, используемая при вычислении позиций ошибок. Она состоит в вычислении полинома локаторов ошибок последовательно для всех элементов поля Галуа. Для увеличения пропускной способности декодера обычно за один такт осуществляется вычисление полинома локаторов ошибок сразу в p точках, где p – параметр процедуры. Современные БЧХ коды используют поля порядка 2^15, а параметр p=32, но современные системы синтеза чипов испытывают серьезные трудности при синтезе данной процедуры для данных параметров, и проблема связана с тем, что они не могут развести провода в данной схеме, а для значения параметра p=64 уже не могут осуществить синтез. Юлия удалось реализовать данный автоматный оператор многослойными плоскими схемами для полей порядка 2^16 и 2^20 и для произвольного значения параметра p, т.е. Юлия предложила алгоритм укладки функциональных элементов и алгоритм разводки проводов, который слабо зависит от параметра p. При этом степень утилизации (отношение площади схемы к числу функциональных элементов) построенных Юлией схем составляет не менее 75%, что является, что считается очень хорошей степенью утилизации.