Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

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

Диссертация: Исследование и разработка методологии проектирования основных вычислительных узлов для устройств цифровой обработки сигналов в модулярной арифметике
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • Глава 1. Особенности реализации основных вычислительных процедур в устройствах цифровой обработки сигналов в модулярной арифметике
    • 1. 1. Основные свойства и основные понятия модулярной арифметики
    • 1. 2. Применение модулярной арифметики при построении устройств цифровой обработки сигналов
    • 1. 3. Основные вычислительные процедуры в устройствах цифровой — «обработки сигналов в модулярной арифметике
  • Выводы по главе 1
  • Глава 2. Методы аппаратной реализации модулярных сумматоров
    • 2. 1. Методы реализации и анализ типовых структур модулярных сумматоров
    • 2. 2. Методы аппаратной реализации сумматоров по модулю (2"+1). Сравнение и анализ типовых и оптимизированных структур
    • 2. 3. Методы аппаратной реализации сумматоров по модулю (2п-1). Сравнение и анализ типовых и оптимизированных структур
    • 2. 4. Методы логического синтеза сумматоров с ускоренным переносом по модулю (2п-1) на основе BDD-технологии
  • Выводы по главе 2
  • Глава 3. Принципы построения модулярных индексных умножителей
    • 3. 1. Архитектура и принципы функционирования индексного модулярного умножителя
    • 3. 2. Архитектура и принципы функционирования параллельного индексного субмодулярного умножителя
    • 3. 3. Критерии выбора значений модулей и подмодулей при построении индексных модулярных и субмодулярных умножителей на основе анализа и сравнения результатов синтеза
    • 3. 4. Особенности применения индексных модулярных умножителей в системах цифровой обработки сигналов в модулярной арифметике
  • Выводы по главе 3
  • Глава 4. Преобразование из модулярного представления в двоичную систему счисления на основе алгоритма с предварительной обработкой данных
    • 4. 1. Математический алгоритм восстановления целого числа по его модулярному представлению
    • 4. 2. Аппаратная реализация преобразователя из модулярного представления в двоичную систему счисления на основе модифицированного алгоритма с предварительной обработкой данных
  • — 4.3.¦ Программа генерации синтезируемых поведенческих Verilog-описаний таблиц соответствия, используемых при построении преобразователя, с учетом алгоритма с предварительной обработкой данных
  • Выводы по главе 4
  • Глава 5. Принципы построения фильтров с конечной импульсной характеристикой в модулярной арифметике
    • 5. 1. Методы аппаратной реализации КИХ-фильтров в прямой и транспонированной формах
    • 5. 2. Анализ и реализация фильтров в двоичной системе счисления
    • 5. 3. Анализ и реализация фильтров в модулярной арифметике
  • Выводы по главе 5

Исследование и разработка методологии проектирования основных вычислительных узлов для устройств цифровой обработки сигналов в модулярной арифметике (реферат, курсовая, диплом, контрольная)

Актуальность темы

.

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

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

В 70−80-е годы были проведены значительные теоретические исследования в области модулярной арифметики (в том числе и в России) и реализован ряд высокоэффективных вычислительных систем на ее основе. Однако данное направление не получило дальнейшего широкого развития во многом из-за проблем в реализации этих устройств, связанных с элементной базой, принципиально ориентированной на двоичную булеву арифметику. В настоящее время с развитием интегральной схемотехники появляются возможности по использованию новых методов проектирования (технология проектирования систем на кристалле — SoC) как для отдельных узлов, реализующих вычислительные операции, так и устройств в целом. Интегральное исполнение устройств, под которым здесь, прежде всего, понимается возможность гибкого проектирования и выбора тобрй элементной базы, дает возможность реализовывать устройства с применением модулярной арифметики также эффективно, как и для обычной двоичной. Таким образом, проблема реализации систем с применением модулярной арифметики, в частности устройств ЦОС, в интегральном исполнении является с одной стороны новой и малоисследованной, а с другой — обещающей высокую эффективность,.что доказано предыдущими поколениями вычислительной техники.

Цель диссертационной работы.

Целью работы является разработка методологии проектирования основных вычислительных блоков для устройств ЦОС в модулярной арифметике при их реализации в интегральном исполнении и обеспечивающих их минимальные аппаратные затраты и максимальное быстродействие. Для достижения поставленной цели решались следующие задачи:

1. Анализ и систематизация основных вычислительных процедур для устройств ЦОС, реализованных с применением аппарата модулярной арифметики. Определение разрядности значений модулей, используемых при построении указанных систем.

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

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

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

5. Анализ и сравнение реальных устройств ЦОС, реализованных в двоичной системе счисления и в модулярной арифметике.

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

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

1. Проведен анализ существующих типовых структур модулярных сумматоров и предложены методы аппаратной реализации сумматоров по модулям (2п-1) и (2″ +7) в интегральном исполнении, позволяющие получить выигрыш в занимаемой площади без ухудшения, а в некоторых случаях с улучшением по быстродействию.

2. Разработаны методы логического синтеза быстрых сумматоров по модулю (2″ -7) на основе существующих методов декомпозиции BDD, в том числе для функций переноса. При этом обеспечивается выигрыш в быстродействии при их реализации в интегральном исполнении для различных базисов.

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

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

5. На основе разработанных методов предложена структура КИХ-фильтров с применением транспонированной формы в модулярной арифметике, обеспечивающая повышение быстродействия устройства в целом.

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

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

1. Методы аппаратной реализации сумматоров по модулям вида (2п-1) и (2п+1), реализованных в интегральном исполнении.

2. Методы логического синтеза сумматоров с ускоренным переносом по модулю вида (2″ -7) на основе BDD-технологии. Основной принцип декомпозиции функций переноса для сумматоров по модулю (2″ -7).

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

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

5. Принципы построения КИХ-фильтров в транспонированной форме с применением аппарата модулярной арифметики.

Реализация результатов.

По результатам работы разработана методология проектирования основных вычислительных узлов для устройств ЦОС в модулярной арифметике, с учетом их реализации в интегральном исполнении. Также предложена архитектура для построения КИХ-фильтров в транспонированной форме с применением аппарата модулярной арифметики.

Разработан ряд вспомогательных программ, генерирующих синтезируемые Verilog-описания отдельных блоков, используемых при проектировании данных устройств, что позволяет в1 совокупности со стандартными средствами s’синтеза автоматизировать их структурное проектирование.

Результаты диссертации внедрены и использовались в следующих организациях: ГУ НПК «Технологический Центр», МИЭТ, а также использовались в научно-исследовательских работах ИППМ РАН.

Практическая значимость результатов работы.

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

Апробация работы.

Основные «положения и результаты диссертационной работы были представлены на следующих Всероссийских конференциях:

— Десятая межвузовская НТК «Микроэлектроника и информатика-2003», Москва 2003;

— Одиннадцатая межвузовская НТК «Микроэлектроника и информатика-2004», Москва 2004.

Публикации.

По вопросам диссертации автором опубликовано 6 печатных работ, 1 отчет по завершенному НИР и 2 выступления на Всероссийских конференциях.

Список печатных работ приведен в конце автореферата.

Структура и объем работы.

Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений.

Основные результаты диссертации:

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

2. Проведен анализ и сравнение типовых структур модулярных сумматоров, выполненных с применением блоков двоичной арифметики. Для сумматоров по модулям типа (2″ +1) и (2″ -7) разработаны методы аппаратной реализации в интегральном исполнении, обеспечивающие выигрыш по занимаемой площади до 25−30%.

3. Разработаны методы логического синтеза сумматоров по модулю (Т-1) на основе BDD-технологии, в том числе для функций переноса. Сформулирован основной принцип декомпозиции функций переноса для сумматоров данного типа. На основе полученных методов предложены методы схемотехнической реализации сумматоров по модулю {Т-1) в базисе из мультиплексоров и в базисе элементов 2И-ИЛИ.

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

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

6. Проведен анализ и сравнение КИХ-фильтров, выполненных в двоичной системе счисления и в модулярной арифметике. Показано, что фильтры, реализованные с применением аппарата модулярной арифметики, обладают более высоким быстродействием по сравнению с традиционными фильтрами в позиционной системе.

Заключение

.

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

Показать весь текст

Список литературы

  1. И.Я., Юдицкий Д. И. Машинная арифметика в остаточных классах.- М.: Советское радио, 1968. 440 с.
  2. В.М., Стемпковский A.JI., Широ Г. Э. Быстродействующий согласованный фильтр, построенный по модулярному принципу // Информационные технологии. 2004. — Вып. 9.
  3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. — 536 с.
  4. А.В. Оценка затрат при модулярной реализации согласованного фильтра // Микроэлектроника и информатика-2001: Восьмая всероссийская межвузовская конференция студентов и аспирантов: Тезисы докладов, М.: МИЭТ, 2001. 336 с. — С. 90.
  5. JI.M., Матюшкин Б. Д., Поляк М. Н. Цифровая обработка сигналов.- М.: Радио и связь, 1990. 256 с.
  6. В.Е. Недвоичная машинная арифметика и специализированные процессоры / Под ред. Акушского И .Я. М.: МИФИ Сервис, 1992. — 267 с.
  7. О.Д. Обработка числовых данных с повышенной точностью в модулярной алгебре // Информационные технологии. 2004. — Вып. 2. — С. 1015.
  8. С.А. Теория и методы моделирования вычислительных структур с параллелизмом машинных операций // Автореферат на соискание ученой степени доктора технических наук, Москва. 2001.
  9. Т.Ю., Корнилов А. И. Алгоритм декомпозиции логических функций, ориентированный на синтез быстродействующих цифровых устройств // Информационные технологии. Вып. 4, 2001. — С. 26−31.
  10. Т.Ю. Разработка и исследование методов логического синтеза быстродействующих КМОП БИС // Автореферат на соискание ученой степени кандидата технических наук, Москва. 2002.
  11. Исследование методов проектирования и разработка программных средствсинтеза быстродействующих арифметических устройств // Заключительный отчет по НИР «Вега-0-К-2003» (проект № 1.5/03) (Инв. № 02.2.405 859),-М.гИППМ РАН. -2003.
  12. B.C. Основные виды архитектур модулярных сумматоров для двух операндов // Микроэлектроника и информатика-2004. Одиннадцатая всероссийская межвузовская конференция студентов и аспирантов. Тезисы докладов. М.: МИЭТ, 2004. — 444 с. — С. 217.
  13. B.C., Ласточкин О. В., Семенов М. Ю. Лабораторный практикум по курсу «Основы логического синтеза средствами САПР Synopsys с использованием Verilog HDL» / под ред. чл.-корр. РАН, д.т.н. А. Л. Стемпковского. М.: МИЭТ, 2004. — 88 с.
  14. Кнут Дональд Э. Искусство программирования, том 2. Получисленные алгоритмы. М.: Издательский дом «Вильяме», 2001. — 832 с.
  15. Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.-960 с.
  16. А.И. Построение быстродействующих арифметических устройств в одном универсальном логическом базисе // Техника средств связи. Сер. Микроэлектронная аппаратура. 1990. — Вып.1−2(12−13). — С. 41−47.
  17. А.И., Исаева Т. Ю., Семенов М. Ю. Методы логического синтеза сумматоров с ускоренным переносом по модулю (2п-1) на основе BDD-технологии // Известия ВУЗов. Электроника. 2004. — Вып. 3. — С. 54−60.
  18. А.И., Семенов М. Ю. Преобразователь из модулярного представления в двоичную систему счисления на основе алгоритма с предварительной обработкой данных // Известия ВУЗов. Электроника. 2003. — Вып. 3. — С. 54−58.
  19. А.И., Семенов М. Ю., Калашников B.C. Методы аппаратной оптимизации сумматоров для двух операндов в системе остаточных классов// Известия ВУЗов. Электроника. 2004. — Вып. 1. — С. 75−82.
  20. А.И., Семенов М. Ю., Ласточкин О. В. Принципы построения модулярных индексных умножителей // Известия ВУЗов. Электроника. 2004. -Вып. 2.-С. 48−55.
  21. А.Б. Цифровая обработка сигналов. СПб.: Питер, 2002. — 608 с.
  22. Стемпковский A. JL, Корнилов А. И., Семенов М. Ю. Особенности реализации устройств цифровой обработки сигналов в интегральном исполнении с применением модулярной арифметики // Информационные технологии. 2004. -Вып. 2.-С. 2−9.
  23. У., Шенк К. Полупроводниковая схемотехника. М: Мир, 1982. — 2 С.
  24. Е. Цифровая схемотехника. СПб.: БХВ-Петербург, 2001. — 528с.
  25. О.А. Модулярная арифметика параллельных логических вычислений / Под ред. В. Д. Малюгина. М.: Институт проблем управления РАН- Краснодар: Краснодарский военный институт, 2003.-224 с.
  26. Barraclough S.R., Sotheran М., Burgin К., Wise А.Р., Vadher A., Robbins W.P., Forsythe R.M. The Design and Implementation of the IMS A110 Image and Signal Processor // IEEE Custom Integrated Circuits Conf. 1989. — P. 24.5.1−24.5.4.
  27. Bryant R.E. Graph-Based Algorithms // IEEE Transactions on Computers- Aug. 1986. V. C-35, N 8. — P. 677−691.
  28. Bryant R.E. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams // ACM Computing. 1992. — V. 24, N 3.
  29. Bayomi M.A., Jullien G.A. A VLSI Implementation of the Residue Adders // IEEE Trans, on Circuits and Systems. March 1987. — V. 34, N 3. — P. 284−288.
  30. Becker В., Drechsler R. How Many Decomposition Types Do We Need? // Proc. of
  31. IP Workshop on Logic and Architecture Synthesis, Institut National Polytechnique de Grenoble, France, 19−20 December, 1994.
  32. Burrascano P., Cardarilli G.C., Lojacono R., Martinelli G., Salerno M. RNS Fourier Transforms // ICASSP-88, International Conference on Acoustics, Speech and Signal Processing, 11−14 Aug. 1988. V. 3. — P. 1427−1430.
  33. Burrascano P., Cardarilli G.C., Lojacono R., Martinelli G., Salerno M. Application of Number Theory to Structurally Passive Digital Filters // IEEE International Symposium on Circuits and Systems.-Jun.l988.-V. 2.-P. 1775−1778.
  34. Cardarilli G.C., Lojacono R., Martinelli G., Salerno M. Structurally Passive Digital Filters in Residue Number Systems // IEEE Trans, on Circuits and Systems. -February 1988.-V. 35, N2.-P. 149−158.
  35. Cardarilli G.C., Re M., Lojacono R. A new RNS FIR Filter Architecture// DSP-97, IEEE 13 International Conference on Digital Signal Processing, 2−4 Jul. 1997. -V. 2.-P. 671−674.
  36. Cardarilli G.C., Nannarelli A., Re M. Reducing Power Dissipation in FIR Filters using the Residue Number System // Proc. of 43rd IEEE Midwest Symp. on Circuits and Systems. Aug. 2000. — P. 320−323.
  37. Cardarilli G.C., Del Re A., Nannarelli A., Re M. Residue Number System Reconfigurable Datapath // ISCAS 2002, IEEE International Symposium on Circuits and Systems. May 2002. — V. II. — P. 11−756 -11−759.
  38. David R.Smith. «Verilog Styles for Synthesis of Digital Systems», Prentice Hall, Inc. 2000.
  39. Del Re A., Nannarelli A., Re M. Implementation of Digital Filters in Carry-Save Residue Number System // IEEE Conference Record on the Thirty-Fifth Asilomar Conference on Signals, Systems and Computers, 4−7 Nov. 2001 V. 2. — P. 13 091 313.
  40. Dugdale M. VLSI Implementation of Residue Adders Based on Binary Adders // Trans, on Circuits and Systems II: Analog and Digital Signal Processing. May 1992.-V. 39.-P. 325−329.
  41. Efstathiou C., Vergos H.T. Modified Booth l’s Complement and Modulo 2n-l Multipliers // ICECS 2000, The 7th IEEE International Conference on Electronics, Circuits and Systems, 2000. V. 2. — P. 637−640.
  42. Grofischad 1 J. The Chinese Remainder Theorem and its Application in a High-Speed RSA Crypto Chip // ACSAC’OO, 16 Annual Conference, Computer Security Application. December 2000. — P. 384−393.
  43. Hiasat A. New Memoryless, mod (2n±l) Residue Multiplier // IEEE Electronic Letters, 30 Januaiy 1992. -V. 28, N3. P. 314−315.
  44. Hiasat A. RNS Arithmetic Multiplier for Medium and Large Moduli // IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. -Sept. 2000. V. 47, N 9. — P: 937−940.
  45. Jullien G.A. Number Theoretic Techniques in Digital Signal Processing // Academic Press Inc., Advances in Electronic and Electron Physics. 1991. — V. 80, Chapter 2. -P. 69−163.
  46. Kebschull U., Schubert E., Rosenstiel W. Multilevel Logic Synthesis Based on Functional Decision Diagrams // Proc. of ICC AD. 1992. — P. 43−47.
  47. Kornilov A., Isaeva T. Circuit Depth Optimization by BDD Based Function Decomposition // IFIP Workshop on Logic and Architecture Synthesis. Grenoble, France. 1994.-P.64−70.
  48. Kornilov A., Isaeva Т., Syngaevsky V. Carry Circuit Depth Optimization by BDD Based Decomposition // Proc. of PATMOS'97 Workshop Louvain-la-Neuve, Belgium, 8−10 Sep. 1997. — P.89−98.
  49. Lim K.P., Premkumar A.B. A Modular Approach to the Computation of Convolution Sum Using Distributed Arithmetic Principles // IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. Jan. 1999. — V. 46, N 1. — P. 9296.
  50. Massey James L. An Introduction to Contemporary Cryptology // Proc. of IEEE. May 1988. — V. 76, N 5. — P. 533−549.
  51. Nannarelli A., Re M., Cardarilli G.C. Tradeoffs between Residue Number System and Traditional FIR Filters // ISCAS 2001, Proc. of IEEE International Symposium on Circuits and Systems. May 2001. — V. II. — P. 305−308.
  52. Preethy A. P., Radhakrishnan D., Omondi A. Fault-tolerance Scheme for an RNS MAC: Performance and Cost Analysis // ISC AS 2001, The 2001 IEEE International Symposium on Circuits and Systems, 6−9 May 2001. -V. 2. P. 717−720.
  53. Radhakrishnan D., Yuan Y. A Fast RNS Galois Field Multiplier // IEEE International Symposium on Circuits and Systems. May 1990. -V. 4. — P. 2909−2912.
  54. Radhakrishnan D., Pyon T. Fault Tolerance in RNS: An Efficient Approach // ICCD'90, IEEE International Conference on Computer Design, 17−19 September 1990.-P. 41−44.
  55. Radhakrishnan D., Yuan Y. Novel Approaches to the Design of VLSI RNS Multipliers // IEEE Trans, on Circuits and Systems II: Analog and Digital Signal Processing. — January 1992. — V. 39, N 1. — P. 52−57.
  56. Slegel T.J., Veracca R.J. Design and performance of the IBM Enterprise System/9000 Type 9121 vector facility // IBM J. Res. Develop. May 1991. — V. 35. — P. 367−381.
  57. M.A., Jenkins W.K., Jullien G.A., Taylor F.J. (EDS) Modern Application of Residue Number System Arithmetic to Digital Signal Processing. -New York: IEEE Press, 1986.
  58. Taylor F.J. An RNS Discrete Fourier Transform Implementation // IEEE Transactions on Acoustics, Speech, and Signal Processing. Aug. 1990. — V. 38, N 8. — P. 13 861 394.
  59. Wall Larry, Christiansen Tom and Schwartz Randal with Stephen Potter Programming Perl, Second Edition. O’Reilly & Associates, Inc. Copyright 1996.
  60. Walter C.D. Systolic Modular Multiplier // IEEE Trans. Computers. Mar. 1993. -V. 42, N3.-P. 376−378.
Заполнить форму текущей работой

На отлично!