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

005061313

На правах рукописи

Захаров Илья Дмитриевич

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

05.13.12 - Системы автоматизации проектирования (приборостроение)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

6 ИЮН 2013

Санкт-Петербург - 2013

О

005061313

Работа выполнена на кафедре Вычислительной техники в Санкт-Петербургском национальном исследовательском университета информационных технологий, механики и оптики.

Нау чаы й руководитель: Официальные оппоненты:

доктор технических наук, профессор, Ожиганоо Александр Аркадьевич доктор технических наук, профессор, Арустамов Сергей Аркадьевич, профессор кафедры проектирования и безопасности компьютерных систем НИУ ИТМО

кандидат технических наук, Климате Виталий Александрович, ведущий специалист дирекции по информационным технологиям ОАО "Силовые машины"

ФГУП "Санкт-Петербургское ОКБ "Электроавтоматика" им. П.А. Ефимова"

Защита состоится "17" июня 2013 г. в 15 часов 50 минут на заседании диссертационного совета Д. 212.227.05 при Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики, расположенном по адресу: 197101, г. Санкт-Петербург, Кронверкский проспект, д.49, лит.А.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан "16" мая 2013 г.

Ведущая организация:

Ученый секретарь диссертационного совета. кандидат технических наук, доцент

Поляков В. И.

Общая характеристика работы

Актуальность работы. Бурное развитие цифровой вычислительной техники естественным образом породило острую потребность в средствах аналогово-цифрового преобразования (АЦП). Распространёнными устройствами для выполнения аналогово-цифрового преобразования являются цифровые преобразователи угла (ЦПУ). Такие устройства находят своё применение в приборостроении, робототехнике, радио- и лазерной локации, различных системах связи и навигации, управления движением и пр.

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

Значительный вклад в развитие ЦПУ внесли работы отечественных учёных Домрачева В.Г., Мейко B.C., Городецкого А.Б., Кривенкова В.В., Месь-кина И.В., Ожиганова A.A., Прибыткииа П.А., Шарина Ю.С. и др. Однако зачастую под развитием средств ЦПУ подразумевается исключительно повышение точности и надёжности преобразователей. В последнее время особенную актуальность приобрела принципиально новая задача повышения разрешающей способности при одновременном уменьшении массо-габаритных характеристик ЦПУ.

В тех случаях, когда не накладывается ограничений на массо-габаритные характеристики преобразователя, существует множество методов решения задачи повышения разрешающей способности. Однако задача повышения разрешающей способности преобразователя при одновременном уменьшении его массо-габаритных характеристик остаётся открытой, В силу копструктив-

ных особенностей преобразователей, решение этой задачи напрямую связано с проектированием кодовой шкалы (КШ) ЦПУ. Основной функциональной частью КШ является её кодирующая маска (КМ). Именно сложность процесса синтеза КМ, в основном, определяет сложность проектирования как КШ, так и ЦПУ в целом.

Логическим представлением маски КШ является двоичный код. Обычно в качестве такого кода используется обыкновенный двоичный код или код Г{>ея. При этом, число информационных кодовых дорожек как правило равно разрядности преобразователей, что негативно влияет на массо-габаритные характеристики ЦПУ.

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

Развитием ПСКШ являются псевдорегулярные кодовые шкалы (ПРКШ), позволяющие в заданных габаритах ЦПУ всего на нескольких КД (до 5) реализовать разрешающую способность до 20 двоичных разрядов.

Синтез псевдорегулярных КШ является трудоёмкой задачей и до настоящего времени выполнялся вручную. При этом, получаемый результат не давал разнообразия вариантов масок, необходимых для эффективного проектирования. Поэтому актуальной является проблема разработки методов и алгоритмов синтеза псевдорегулярных КШ и автоматизации процесса их проектирования. Такие КШ позволили бы на своей основе создавать ЦПУ с улучшенными массо-габаритными и технологическими характеристиками.

Цель диссертационной работы состоит в разработке методов и алгоритмов для синтеза псевдорегулярных кодовых шкал цифровых преобразо-

вателей угла с улучшеными массогабаритпыми характеристиками.

Для достижения указанной цели потребовалось решить следующие, задачи:

1. Провести ан&пиз методов построения кодовых шкал современных цифровых преобразователей угла.

2. Осуществить поиск новых классов двоичных последовательностей пригодных для построения информационных рисунков псевдорегулярных кодовых шкал.

3. Разработать методы и алгоритмы автоматизированного синтеза псевдорегулярных кодовых шкал на основе найденных двоичных последовательностей.

4. Разработать структуру и программный код САПР псевдорегулярных кодовых шкал цифровых преобразователей угла.

Научная новизна результатов исследования заключается в следующем:

1. Предложен метод синтеза полного множества порождающих полиномов М-последовательностей с одинаковым периодом на основе одного заданного с улучшенными показателями вычислительной сложности.

2. Разработан алгоритм получения индексов децимации, используемый как основной этан в методе построения порождающих полиномов М-носле-довательвостей.

3. Предложен метод синтеза псевдорегулярных кодовых шкал на основе М-последовательностей.

4. Разработан алгоритм синтеза полного множества двоичных последовательностей де Брейна заданной степени.

5. Предложен метод синтеза псевдорегулярных кодовых шкал на основе двоичных последовательностей де Брейиа.

6. Предложен метод синтеза псевдорегулярных кодовых шкал на основе комбинации М-последовательностей и двоичных последовательностей де Брейна.

7. Подложена структура и разработан программный код системы автоматизирован нош проек'пцювания нсевдорегулярных кодовых шкал ЦПУ.

Практическая значимость. Результаты, изложенные в диссертации, могут быть использованы для синтеза масок кодовых шкал, позволяющих строить на своей основе ЦПУ с улучшенными масс»-габаритными и технологическими характеристиками. Разработанные методы и алгоритмы: являются научной основой для создания САПР псевдорегулярных масок кодовых шкал ЦПУ.

На защиту выносятся следующие основные результаты и положения:

1. Метод синтеза полного множества порождающих полиномов М-после-дователыюстей с одинаковым периодом на основе одного заданного.

2. Алгоритм синтеза полного множества двоичных последовательностей де Брейна заданной степени.

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

4. Структура и программный код системы автоматизированного проектирования псевдорегулярных кодовых шкал ЦПУ.

Апробация работы. Основные результаты диссертационной работы и результаты исследований докладывались на различных конференциях, в том числе на I и И Майоровских чтениях в НИУ ИТМО (2010г., 2011г., СПб), VIII конференции молодых ученых НИУ ИТМО (2011 г.. СПб), ХЬ и ХЫ1 научных и учебно- метод и ческ и х конференциях I! НИУ ИТМО (2011 г.. 2013 г., СПб), V Научно-технической конференции молодых специалистов по радиоэлектронике в ОАО "Авангард"(2012 г., СПб).

Публикации. Теоретические и практические результаты, представленные в диссертации, отражены в 7 научных работах, в том числе входящие в список рекомендованных ВАК для защиты кандидатских диссертаций [1-3], сборники трудов сотрудников кафедры ВТ НИУ ИТМО [4, 5], сборники трудов конференций и тезисов докладов [6, 7].

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

Структура и объем диссертации. Диссертация состоит из введения, 4 разделов, заключения, библиографии и 7 приложений. Общий объем диссертации 173 страницы, из них 128 страниц текста, включая 17 рисунков. Библиография включает 67 наименований на 8 страницах.

Содержание работы

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

В первом разделе содержится обзор состояния вопроса и постановка задачи диссертациоииого исследования.

Дана классификация измерительных шкал и определено место кодовых шкал в этой классификации. Проведен сравнительный анализ кодовых шкал преобразователей перемещения с пространственным кодированием. Были рассмотрены различные подходы к синтезу кодовых шкал преобразователей и коды, положенные в основу их масок. Произведённый анализ проиллюстрирован примерами.

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

Во втором разделе рассмотрены теоретические основы построения рекуррентных последовательностей. Использованы такие понятия как линейная однородная рекуррентная последовательность, порождающий полином, порядок линейно!« рекуррентного уравнения и др.

Дальнейшее изложение делится на две части. В первой части рассмотрены вопросы синтеза полного множества порождающих полиномов М-после-довательностей. Предлагается метод их построения на основе нормальных децимаций и алгоритма Берлекемпа-Мэсси.

Метод синтеза порождающих полиномов М-послсдовательностей включает в себя следующие шаги:

1. Из числа примитивных полиномов с минимальным количеством ненулевых коэффициентов выбирается примитивный полином вида

п

(!)

¡=о

степени п, где п е {2,3,4,..., 14}, 1ц е {0,1}.

2. На основе полинома (1) строится рекуррентное выражение

п-1

= ф Ъ+А, 3 = 0,1,(2)

г=о

где знак ф означает суммирование, по модулю два, а индексы при символах М-последовательности берутся по модулю 2™— 1. Начальные значения символов М-последовательности аоа1-..ап-1 могут выбираться произвольно, за исключением нулевой комбинации.

3. Посредством рекуррентного выражения (2) генерируются символы М-последовательности {а} с периодом М = 2п — 1.

4. В соответствии с выражением N — определяется число примитивных полиномов к(х) степени п.

5. Осуществляется поиск значений индексов децимации 1 = 1,2,..., ЛГ — 1, позволяющих сформировать все нормальные децимации М-последовательности {а}, на основе которых может быть получено N — 1 различных М-последовательностей {а}5' с периодом М.

6. Производится нормальная децимация М-последовательности {а} по индексу qi. Результатом такой децимации является М-последрвателыюсть {а}4" с периодом М.

7. Далее, с использованием алгоритма Берлекемпа-Мэсси и предварительной выборки 2п символов из полученной М-последовательности {а}9' определяется полином hi(x), который также будет примитивным.

8. Шаги 6 и 7 повторяются для всех нормальных децимаци й, найденных на шаге 5. Результатом применения метода являются N — 1 порождающих полиномов степени п.

Эффективность разработанного метода в основном определяется результатом выполнения шага 5. Для оптимизации поиска значений индексов децимации рассмотрим алгоритм, в котором: q - нечетный индекс децимации, q S {3,5, ...,2" — 1}; REG[n} - n-разрядный двоичный циклический регистр сдвига; REGz, z = 0,1,...,п—1,- значение z-ro разряда регистра; s - счетчик числа сдвигов регистра REG[n}\ С - множество проверенных индексов децимации; R - множество результатов работы алгоритма.

Алгоритм включает в себя следующие шаги:

1. q := 1; С := 0; R := 0.

2. <i := q -)- 2; q добавляется в множество С.

3. Если (/ > 2п — 1. переход к шагу 13.

4. Если q € С, переход к шагу 2.

5. Запись q в REG[n\: s :— 0.

6. Если s > п — 1, переход к шагу 10.

7. Циклический сдвиг регистра ЯЕС[п\ на один разряд влево; в := з + 1.

8. КЕС[п] добавляется в множество С.

9. Возврат к шагу 6.

10. Если НОД(д, 2" - 1) = 1, переход к шагу 12.

11. Переход к шагу 2.

12. Добавление полученного значения ц в множество результатов II: Переход к шагу 2.

13. Вывод множества результатов К.

Таким образом, используя рассмотренный алгоритм, можно найти все значения индексов, позволяющие сформировать нормальные децимации М-после-дователыюсти {а} по индексу д¡, I = 1,..., N - 1, на основе которых могут быть получены Аг-1 различных М-последователыюстей {о}® с периодом М.

Использование предложенного метода позволяет сократить вычислительную сложность получения одной М-последовательности с 0(2"+1) до 0(п2 + 2").

Описанный метод синтеза порождающих полиномов М-последовательно-стей проиллюстрирован примером.

Во второй части второго раздела рассматриваются вопросы синтеза полного множества двоичных последовательностей де Брейна заданной степени п. Приведён алгоритм их построения. Общее число синтезируемых последовательностей составляет = 22"~1~". Алгоритм «хютоит из двух этапов. На нервом этапе формируется матрица смежности соогветствующего графа де Брейна, а на втором этапе по полученной матрице смежности находятся собственно последовательности.

Схема алгоритма формирования матрицы смежности приведена на рис.1. Сначала, в соответствии с заданной степенью п, формируется двоичная маска индекса для каждой вершины, т.е. mask '— 2™ — 1. Это достигается побитовым сдвигом изначально нулевой переменной mask с последующим инкрементом на единицу. После формирования маски начинается построчное заполнение матрицы смежности Л. Для каждой из 2™ строк матрицы элементам с индексами (2i)foma.sk и (2i)8zmask + 1 (здесь і - индекс текущей строки) присваиваются значения 1. Таким образом, устанавливается наличие всех направленных связей от вершины г.

Второй этап алгоритма представляет собой рекурсивную процедуру над

строкой і матрицы смежности А, полученной ранее. Схема алгоритма рекурсивной процедуры получения последовательностей показана на рис.2. В качестве параметров в процедуру передается индекс текущей строки і (изначально і = 0) и текущее состояние выходной последовательности. Затем осуществляется проход по строке с индексом і матрицы смежности Л в поисках элемента ау = 1, где 3 - индекс текущего столбца. Если находится элемент Яу = 1 (есть ребро из вершины і в вершину з), следует добавить индекс і в выходную последовательность. Затем обнуляется вся строка і (далее нас не интересуют рёбра графа из вершины г) и столбцы і и з (далее не будут рассматриваться рёбра в вершинах і и ]). Данная процедура вызывается с индексом строки з в качестве параметра.

Рис. 2. Схема алгоритма рекурсивной процедуры поиска последовательностей де Брейна па основе матрицы смсжпости

Если в текущей строке не осталось единичных элементов, выходная последовательность при условии, что её длина равна 2", сохраняется, а сама

процедура завершается, возвращая управление на предыдущий уровень рекурсии.

Вычислительная сложность полного цикла предложенного алгоритма составляет 0(| ■ 22" ').

Описанный алгоритм проиллюстрирован примером.

В третьем разделе приведены методы синтеза псевдорегулярных масок кодовых шкал ЦПУ. Разрешающая способность 6 таких масок может быть вычислена по формуле:

(3)

пи я

где к - число кодовых дорожек маски, а Мр - длина периода последовательности, положенной в основу информационного рисунка р-ой КД, р € {1,... ,к}.

Практически применимыми являются варианты синтеза кодирующих масок с числом кодовых дорожек к от 2 до 4.

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

Так метод синтеза кодирующих масок на основе М-последовательностей состоит из следующих шагов:

1. Задаётся значение разрешающей способности <5П-

2. Выбирается число кодовых дорожек кодирующей маски к, к Є {2,3,4}, и их разрядность пр, р Є {1,2,..., к}.

3. Для каждой КД с индексом р, р € {1,2,..., к}, вычисляется Мр = 2"* — 1.

4. В соответствия с (3) вычисляется разрешающая способность 6 кодирующей маски. Если полученное значение не удовлетворяет требованиям

к разрешающей способности, заданным на шаге 1, происходит возврат к шагу 2.

5. Для каждой КД с индексом р 15 соответствии с методом построения порождающих полиномов М-последовательностей генерируется порождающий полином ¡1р(х) степени пр вида:

--у £=0

где р Є {1, 2,..., к}, }ц Є {0,1}, а пр Є {2,3,4,..., 14}.

6. На основании каждого из полученных на шаге 5 порождающих полиномов Нр{х) синтезируются соответствующие им двоичные М-послодова-тельности {ар} = (аь а2,..., аМр).

7. На основании каждой из полученных на шаге 6 М-последователыюстей {яР} формируются информационные рисунки кодовых дорожек.

8. Исходя из конструктивных и технологических соображений, для кодовой дорожки с индексом р выбирается полином размещения считывающих элементов Гріх) вида:

х"

т= 1

гр(х) = X]

ще ят Є {1,2, ...,МР}.

9. На основании полинома размещения, выбранного на шаге 8, формируется соответствующая ему квадратная матрица Тр вида:

Тр =

( \

(Ч+я, • ■ ■ аі ■ зП/

а2+«! 12+^2 • ' ■ °2+з„,

^ ап+з! оп+32 ... ап+3пі> і

В случае, когда определитель АТр равен нулю, происходит возврат к шагу 8.

10. Шаги 8 и 9 выполняются для всех р, р Є {1,2,..., к} до тех пор, пока не будет найдено корректное размещение считывающих элементов для всех кодовых дорожек.

Метод синтеза кодирующих масок на основе последовательностей де Брей-на состоит из следующих шагов:

1. Задаётся значение разрешающей способности 6а-

2. Выбирается число кодовых дорожек кодирующей маски к, к € {2,3,4}, и их разрядность пр, р Є {1,2,..., к}.

3. Для каждой КД с индексом р, р Є {1,2,..., к}, вычисляется Мр = 2п".

4. В соответствии с (3) вычисляется разрешающая способность 6 кодирующей маски. Если полученное значение не удовлетворяет требованиям к разрешающей способности, заданным на шаге 1, происходит возврат к шагу 2.

5. Для каждой КД с индексом р в соответствии с алгоритмом построения последовательностей де Брей на генерируется двоичная последовательность де Брейиа {6Р}, где р Є {1,2,..., к}.

6. На основании каждой из полученных на шаге 5 последовательностей де Брейна {Ьр} формируются информационные рисунки кодовых дорожек.

7. Исходя из конструктивных и технологических соображений, для кодовой дорожки с индексом р выбирается полином размещения считываю-

щих элементов гр(х) вида:

пр

Гр(х) = XX™'

т=1

где вт Є {1, 2,..., Мр}.

8. Производится проверка на уникальность кодовых комбинаций, получаемых на выходах размещённых считывающих элементов. В случае получения повторяющихся кодовых комбинаций, происходит возврат к шагу 7.

9. Шаги 7 и 8 выполняются для всех р, р Є {1, 2,..., к} до тех пор, пока не будет найдено корректное размещение считывающих элементов для всех кодо пых дорожек.

Метод синтеза кодирующих масок на основе комбинации М-последова-тельностей и последовательностей де Брейна состоит из следующих шагов:

1. Задаётся значение разрешающей способности ¿02. Выбирается число кодовых дорожек кодирующей маски к, к Є {2,3,4}, их разрядность пр, р 6 {1,..., к} и классы двоичных последовательностей, которые будут использованы для формирования информационных рисунков кодовых дорожек. Синтез информационного рисунка старшей кодовой дорожки целесообразно производить на основе М-последова-тельности.

3. Для каждой КД с индексом р, р Є {1, 2,...,к}, вычисляется Мр. В случае использования М-последовательности в качестве основы для информационного рисунка, Мр = 2"» - 1. В случае использования последовательности до Брейна в качестве основы для информационного рисунка, Мр = 2Пр.

4. В соответствии с (3) вычисляется разрешающая способность 5 кодирующей маски. Если полученное значение не удовлетворяет требованиям к разрешающей способности, заданным на шаге 1, происходит возврат к шагу 2.

5. В соответствии с методом построения порождающих полиномов М-после-довательностей генерируется порождающий полином /гДж) степени п,\ вида:

где/і* Є {0,1}, а ще {2, 3,4,... ,14}.

6. На основании полученного порождающего полинома /її (ж) синтезируется двоичная М-последовательность {аі}.

7. На основании полученной М-последовательности {04} формируется информационный рисунок старшей кодовой дорожки.

8. В случае использования М-последовательиости в качестве основы для кодового рисунка следующей дорожки - переход к шагу 9.

В случае использования последовательности де Брейка в качестве основы для кодового рисунка следующей дорожки - переход к шагу 12

9. В соответствии с методом построения порождающих полиномов М-носле-довательностей генерируется порождающий полином кр(х) степени пр

Ы®) = Х^"''

вида:

где р Є {2,..., к}, Ы Є {0,1}, а пр Є {2,3,4,..., 14}.

10. На основе полученного на шаге 9 порождающего полинома Нр(х) синтезируется собственно двоичная М-последовательность {ар}.

11. На основе полученной на шаге 10 М-носледовательиости формируется информационный рисунок кодовой дорожки с индексом р. Переход к шагу 14.

12. В соответствии с алгоритмом построения последовательностей до Брей-иа генерируется двоичная последовательность де Брейна {Ьр}, где р 6 {2,..., к}.

13. На основе полученной на шаге 12 последовательности де Брейна формируется информационный рисунок кодовой дорожки с индексом р.

14. В зависимости от числа выбранных кодовых дорожек, шаг 8 повторяется и для оставшихся кодовых дорожек.

15. Исходя из конструктивных и технологических соображений, для кодовой дорожки с индексам р выбирается полином размещения считывающих элементов гр(х) вида:

71,

т=1

где € {1, 2,..., Л/р}.

16. Производится проверка на уникальность кодовых комбинаций, получаемых на выходах размещённых считывающих элементов. В случае получения повторяющихся кодовых комбинаций, происходит возврат к шагу 15.

17. Шаги 15 и 16 выполняются для всех р, р е {1,2,..., к} до тех пор, пока не будет найдено корректное размещение считывающих элементов для всех кодовых дорожек.

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

Таблица 1. Методы синтеза круговых псевдорегулярных кодовых шкал

Характеристика На основе М-последовательностей На основе последовательностей де Брейна

Число различимых кодовых комбинаций на одну КД Мьи.э = 2" - 1 Мов = 2"

Число получаемых кодирующих масок Мшэ = N00 = 22"~1~п

Вычислительная сложность формирования кодирующей маски О (ті2 + 2") 0(§ • 2")

В четвёртом разделе рассматриваются вопросы, связанные с разработкой САПР ПРКШ.

В начале раздела рассматриваются основные понятия, связанные с САПР, такие как процесс проектирования, системный подход к проектированию, описание основных этапов проектирования, перечисляются типовые операции и общие принципы, такие как принцип включения, принцип системного единства, принцип комплексности, принцип информационно!« единства, принцип совместимости, принцип инвариантности, принцип развития или принцип модульного построения, принцип эквифинальности, принцип иерархии.

Далее дано описание структуры и объектной иерархии предлагаемой системы автоматизированного проектирования ПРКШ. Предлагаемая система

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

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

Рассматриваемая в настоящей работе САПР ПРКШ позволяет унифицировать реализацию алгоритмов формирования двоичных последовательностей, инкапсулируя вычислительную масть в модулях-генераторах и предоставляя единый интерфейс. Таким образом реализуется принцип инвариантности.

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

На основе рассмотренного подхода реализована САПР ПРКШ на языке С#. с использованием .NET4 Framework. Разработанное программное обеспечение внедрено в производственный процесс в ОАО "Авангард", где используется в процессе проектирования фотоэлектрических цифровых преобразователей угла.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработан и исследован метод получения порождающих полиномов М-последовательностей путём нормальных децимаций на основе одного заданного.

2. Разработан алгоритм получения индексов децимации, используемый как основной этап в методе построения порождающих полиномов М-последовательностей.

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

4. Разработан и исследован алгоритм получения двоичных последовательностей де Брейна.

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

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

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

8. Разработана логическая структура и прог-раммный кода САПР псевдорегулярных кодовых шкал.

Список публикаций

1. Ожиганов А. А., Захаров И. Д. Использование порождающих полиномов М-последователыюстей при построении псевдослучайных кодовых

шкал Ц Известия вузов. Приборостроение. 2012. Т. 54, № 6. С. 49—56.

22

2. Ожиггшов А. А., Захаров И. Д. Применение последовательностей де Брейка для построения псевдорегулярных кодовых шкал // Научно-технический вестник информационных технологий, механики и оптики. 2012. Л-' 2(78). С. 69-74.

3. Ожиганов А. А., Захаров И. Д. Система автоматизированного проектирования псевдорегулярных кодовых шкал // Известия вузов. Приборостроение. 2012. Т. 55, № 10. С. 80-84.

4. Захаров И. Д. Алгоритм вычисления нормальных децимаций М-последо-вательнсстсй // Сборник трудов молодых ученых и сотрудников кафедры ВТ / Под ред. д.т.н., проф. Т.Н. Алиева. СПб: СПбГУ ИТМО. 2011. № 2. С. 33 36.

5. Захаров И. Д. Алгоритм генерации последовательностей де Брейна // Сборник трудов молодых ученых и сотрудников кафедры ВТ / Под ред. д.т.н., проф. Т.Н. Алиева. СПб: СПбГУ ИТМО. 2012. № 3. С. 21-24.

6. Захаров И. Д. Система автоматизированной) проектирования линейных псевдослучайных кодовых шкал // Сборник тезисов докладов конференции молодых ученых. СПб: СПбГУ ИТМО. 2011. С. 58-59.

7. Захаров И. Д. Структура системы автоматизированного проектирования псевдорегулярных кодовых шкал // Сборник докладов V научно-технической конференции молодых специалистов по радиоэлектронике. СПб: ОАО «Авангард». 2012. С. СЭ-72.

Тиражирование и брошюровка выполнены в учреждении "Ун и верситетские телеком му никаци и" 197101, Санкт-Петербург, Кронверкский пр., д. 49. Тел. (812) 233 46 69 Объём 1 п.л. Тираж 100. экз.

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики

На правах рукописи

0420135*1 24 Захаров Илья Дмитриевич

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

05.13.12 - Системы автоматизации проектирования (приборостроение)

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н., проф.

Ожиганов Александр Аркадьевич

Санкт-Петербург - 2013

Содержание

Введение ................................... 5

Раздел 1. Обзор состояния вопроса и постановка задачи ... 10

1.1. Цифровые преобразователи угла на основе считывания.....10

1.2. Кодовые шкалы цифровых преобразователей угла и коды, которые лежат в основе их построения ...............11

1.3. Рекурсивные кодовые шкалы....................15

1.4. Выводы................................20

Раздел 2. Теоретические основы построения рекуррентных последовательностей ...........................22

2.1. Основы построения рекуррентных последовательностей .... 23

2.2. Построение М-последовательностей................24

2.3. Построение последовательностей де Брейна...........43

2.4. Выводы................................56

Раздел 3. Методы синтеза круговых псевдорегулярных кодовых шкал.................................57

3.1. Метод синтеза круговых псевдорегулярных кодовых шкал на основе М-последовательностей...................57

3.2. Метод синтеза круговых псевдорегулярных кодовых шкал на основе последовательностей де Брейна..............76

3.3. Метод синтеза круговых псевдорегулярных кодовых шкал на основе комбинации М-последовательностей и последовательностей де Брейна............................90

3.4. Сравнение методов синтеза круговых псевдорегулярных кодовых шкал...............................106

3.5. Устранение неоднозначности считывания в псевдорегулярных кодовых шкалах...........................109

3.6. Выводы................................110

Раздел 4. Система автоматизированного проектирования псевдорегулярных кодовых шкал.....................113

4.1. Основные принципы автоматизированного проектирования . . 113

4.2. Описание системы автоматизированного проектирования псевдорегулярных кодовых шкал....................118

4.3. Сценарий взаимодействия модулей системы в процессе проектирования ..............................123

4.4. Выводы................................125

Заключение..................................127

Литература..................................129

Приложение А. Документы о внедрении..............137

Приложение Б. Листинг класса-генератора двоичных последовательностей де Брейна........................142

Приложение В. Листинг класса-генератора М-последователь-ностей...................................150

Приложение Г. Конструктивно-целесообразные сочетания кодовых дорожек для синтеза кодирующих масок на основе двоичных М-последовательностей.................156

Приложение Д. Возможные размещения СЭ на КД с информационными рисунками на основе некоторых М-последователь-

ностей...................................161

Приложение Е. Конструктивно-целесообразные сочетания кодовых дорожек для синтеза кодирующих масок на основе двоичных последовательностей де Брейна............166

Приложение Ж. Возможные размещения СЭ на КД с информационными рисунками на основе некоторых последовательностей де Брейна............................171

Введение

Актуальность работы. Бурное развитие цифровой вычислительной техники естественным образом породило острую потребность в средствах ана-логово-цифрового преобразования (АЦП). Распространёнными устройствами для выполнения аналогово-цифрового преобразования являются цифровые преобразователи угла (ЦПУ). Такие устройства находят своё применение в приборостроении, робототехнике, радио- и лазерной локации, различных системах связи и навигации, управления движением и пр.

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

Значительный вклад в развитие ЦПУ внесли работы отечественных учёных Домрачева В.Г., Мейко B.C., Городецкого А.Е., Кривенкова В.В., Месь-кина И.В., Ожиганова A.A., Прибыткина П.А., Шарина Ю.С. и др. Однако зачастую под развитием средств ЦПУ подразумевается исключительно повышение точности и надёжности преобразователей. В последнее время особенную актуальность приобрела принципиально новая задача повышения разрешающей способности при одновременном уменьшении массо-габаритных характеристик ЦПУ.

В тех случаях, когда не накладывается ограничений на массо-габаритные характеристики преобразователя, существует множество методов решения задачи повышения разрешающей способности. Однако задача повышения разрешающей способности преобразователя при одновременном уменьшении его массо-габаритных характеристик остаётся открытой. В силу конструктив-

ных особенностей преобразователей, решение этой задачи напрямую связано с проектированием кодовой шкалы (КШ) ЦПУ. Основной функциональной частью КШ является её кодирующая маска (КМ). Именно сложность процесса синтеза КМ, в основном, определяет сложность проектирования как КШ, так и ЦПУ в целом.

Логическим представлением маски КШ является двоичный код. Обычно в качестве такого кода используется обыкновенный двоичный код или код Грея. При этом, число информационных кодовых дорожек как правило равно разрядности преобразователей, что негативно влияет на массо-габаритные характеристики ЦПУ.

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

Развитием ПСКШ являются псевдорегулярные кодовые шкалы (ПРКШ), позволяющие в заданных габаритах ЦПУ всего на нескольких КД (до 5) реализовать разрешающую способность до 20 двоичных разрядов.

Синтез псевдорегулярных КШ является трудоёмкой задачей и до настоящего времени выполнялся вручную. При этом, получаемый результат не давал разнообразия вариантов масок, необходимых для эффективного проектирования. Поэтому актуальной является проблема разработки методов и алгоритмов синтеза псевдорегулярных КШ и автоматизации процесса их проектирования. Такие КШ позволили бы на своей основе создавать ЦПУ с улучшенными массо-габаритными и технологическими характеристиками.

Цель диссертационной работы состоит в разработке методов и алгоритмов для синтеза псевдорегулярных кодовых шкал цифровых преобразо-

вателей угла с улучшеными массогабаритными характеристиками.

Для достижения указанной цели потребовалось решить следующие задачи:

1. Провести анализ методов построения кодовых шкал современных цифровых преобразователей угла.

2. Осуществить поиск новых классов двоичных последовательностей пригодных для построения информационных рисунков псевдорегулярных кодовых шкал.

3. Разработать методы и алгоритмы автоматизированного синтеза псевдорегулярных кодовых шкал на основе найденных двоичных последовательностей.

4. Разработать структуру и программный код САПР псевдорегулярных кодовых шкал цифровых преобразователей угла.

Научная новизна результатов исследования заключается в следующем:

1. Предложен метод синтеза полного множества порождающих полиномов М-последовательностей с одинаковым периодом на основе одного заданного с улучшенными показателями вычислительной сложности.

2. Разработан алгоритм получения индексов децимации, используемый как основной этап в методе построения порождающих полиномов М-после-довательностей.

3. Предложен метод синтеза псевдорегулярных кодовых шкал на основе М-последовательностей.

4. Разработан алгоритм синтеза полного множества двоичных последовательностей де Брейна заданной степени.

5. Предложен метод синтеза псевдорегулярных кодовых шкал на основе двоичных последовательностей де Брейна.

6. Предложен метод синтеза псевдорегулярных кодовых шкал на основе комбинации М-последовательностей и двоичных последовательностей де Брейна.

7. Предложена структура и разработан программный код системы автоматизированного проектирования псевдорегулярных кодовых шкал ЦПУ.

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

На защиту выносятся следующие основные результаты и положения:

1. Метод синтеза полного множества порождающих полиномов М-после-довательностей с одинаковым периодом на основе одного заданного.

2. Алгоритм синтеза полного множества двоичных последовательностей де Брейна заданной степени.

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

4. Структура и программный код системы автоматизированного проектирования псевдорегулярных кодовых шкал ЦПУ.

Апробация работы. Основные результаты диссертационной работы и результаты исследований докладывались на различных конференциях, в том числе на I и II Майоровских чтениях в НИУ ИТМО (2010г., 2011г., СПб), VIII конференции молодых ученых НИУ ИТМО (2011 г., СПб), XL и XLII научных и учебно-методических конференциях в НИУ ИТМО (2011 г., 2013 г., СПб), V Научно-технической конференции молодых специалистов по радиоэлектронике в ОАО "Авангард"(2012 г., СПб).

Публикации. Теоретические и практические результаты, представленные в диссертации, отражены в 7 научных работах, в том числе входящие в список рекомендованных ВАК для защиты кандидатских диссертаций [3840], сборники трудов сотрудников кафедры ВТ НИУ ИТМО [16, 18], сборники трудов конференций и тезисов докладов [17, 19].

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

Структура и объем диссертации. Диссертация состоит из введения, 4 разделов, заключения, библиографии и 7 приложений. Общий объем диссертации 173 страницы, из них 128 страниц текста, включая 17 рисунков. Библиография включает 67 наименований на 8 страницах.

Раздел 1

Обзор состояния вопроса и постановка задачи

1.1. Цифровые преобразователи угла на основе считывания

Бурное развитие цифровой вычислительной техники, и в особенности систем реального времени, естественным образом породило острую потребность в средствах аналогово-цифрового преобразования (АЦП). Распространёнными устройствами для выполнения аналогово-цифрового преобразования являются преобразователи углового перемещения в код. Такие устройства находят своё применение в различных системах связи и навигации, управления движением и пр. Особенно важным стало применение таких средств в робототехнике и авиа-космическом приборостроении.

Современные ЦПУ строятся на основе различных физических принципов. В соответствии с физическими методами считывания информации ЦПУ можно разделить на шесть групп:

• контактные [14, 15];

• пневмоакустические [14];

• электромагнитные [5];

• электростатические [14];

• фотоэлектрические [9, 15, 22, 47];

• прочие (магнитоэлектрические, тепловые и др.).

Наиболее перспективными на данный момент являются фотоэлектрические ЦПУ.

Значительный вклад в развитие ЦПУ внесли работы таких отечественных учёных, как В.Г.Домрачев, Б.С.Мейко, А.Б.Городецкий, В.В.Кривенков, И.В.Меськин, А.А.Ожиганов, Ю.С.Шарин и др. Однако зачастую под развитием средств АЦП подразумевается исключительно повышение точности и надёжности преобразователей. В последнее время особенную актуальность приобрела принципиально новая задача повышения разрешающей способности преобразователей при одновременном уменьшении массо-габаритных характеристик ЦПУ. Подобные задачи характерны для предприятий военно-промышленного комплекса и авиа-космической отрасли.

В то время как методы повышения точности преобразователей изучены достаточно хорошо, работ посвящённых одновременному уменьшению массо-габаритных характеристик недостаточно. В силу конструктивных особенностей преобразователей, решение этой задачи напрямую связано с проектированием измерительной шкалы ЦПУ.

1.2. Кодовые шкалы цифровых преобразователей угла и коды, которые лежат в основе их построения

Можно выделить два основных класса измерительных шкал [7]:

• временные измерительные шкалы;

• пространственные измерительные шкалы.

В свою очередь множество пространственных измерительных шкал по конструкторско-технологическому исполнению можно разделить на следующие классы:

• линейные пространственные шкалы;

• угловые пространственные шкалы;

• двухкоординатные пространственные шкалы.

По признаку прецизионности, из множества линейных и угловых пространственных шкал можно выделить ананалоговые и дискретные (кодовые) шкалы. Именно кодовая шкала (КШ) является основным технологически ёмким элементом ЦПУ.

Разрешающая способность шкальных ЦПУ, как правило, определяется градацией младшей информационной кодовой дорожки (КД) шкалы. Повышение разрешающей способности шкальных ЦПУ обычно связано со значительным увеличением размеров КШ.

Классический подход к построению ЦПУ базируется на использовании КШ с числом информационных кодовых дорожек, равным, как правило, разрядности преобразователей. Шкалы выполняются в обыкновенном двоичном коде (ОДК), коде Грея и др. Массо-габаритные характеристики ЦПУ в основном определяются диаметром КШ и с увеличением разрядности преобразователя так же возрастают. Разрешающая способность таких шкал <5 = 27г/2п, где п - разрядность преобразователя.

В случае формирования кодирующей маски КШ на основе ОДК, каждому значению ставится в соответствие его представление в двоичном коде. Недостатком применения данного подхода на практике является возможность ошибок, связанных с неоднозначностью считывания. На рис. 1.1 показан пример линейной развёртки простейшей четырёхразрядной кодовой шкалы с кодирующей маской, выполненной на основе ОДК.

Рис. 1.1. Линейная развёртка четырёхразрядной кодовой шкалы на основе ОДК

КШ, кодированная маска которых построена на основе кода Грея, лишена подобного недостатка в силу того, что каждое значение отличается от соседних лишь на один разряд. Нерешённой остаётся проблема большого числа КД, характерная и для КШ, построенных на основе ОДК. На рис. 1.2 показан пример линейной развёртки четырёхразрядной кодовой шкалы с кодирующей маской, выполненной на основе кода Грея.

Рис. 1.2. Линейная развёртка четырёхразрядной кодовой шкалы на основе кода Грея

В работе [61] была предложена модификация кода Грея, получившая название Single-Track Gray Code (STGC). В ней кодовые комбинации последовательно располагаются на одной КД. Такой метод лишён недостатков обыкновенного кода Грея, он компактен и обладает свойством цикличности. Недостатком этого подхода является меньшее количество кодовых комбинаций для заданной разрядности кода, а так же весьма трудоёмкий процесс получения кодовой последовательности. Последняя особенность делает практически невозможным применение таких кодов на практике для преобразователей большой разрядности. На рис. 1.3 показан пример пятиразрядной кодовой шкалы, кодирующая маска которой выполнена на основе модифицированного кода Грея.

Известны так же КШ с нанесённой на них комбинаторной кодовой маской [50]. Несмотря на то, что такие шкалы имеют лишь одну КД, их использование ограничивается ЦПУ очень малой разрядности из-за трудоёмкости процесса синтеза комбинаторного кода.

Рис. 1.3. Пятиразрядная кодовая шкала на основе модификации кода Грея на одной КД

В работе [15] рассматриваются ЦПУ шкально-матричного кодирования. В преобразователях, построенных по этому принципу, операции квантования и кодирования распределены между КШ и электронной матрицей. Шкально-матричный принцип построения ЦПУ позволяет сохранить точность и быстродействие ЦПУ при одновременном уменьшении габаритов и сложности устройства. При этом, каждая КД имеет рисунок, соответствующий сразу нескольким разрядам преобразователя, каждый из которых соответствует определённому участку дорожки. Однако данный подход к построению КШ так же не позволяет повысить разрешающую способность ЦПУ без увеличения