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

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

Семенов Михаил Юрьевич

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

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва - 2005

Работа выполнена в Институте проблем проектирования в микроэлектронике Российской академии наук (ИППМ РАН)

Научный руководитель: доктор технических наук, чл.-корр. РАН А.Л. Стемпковский

Официальные оппоненты: действительный член НАН Казахстана,

доктор технических наук, профессор В.М. Амербаев кандидат технических наук, профессор В.В. Ермак

Ведущая организация: ФГУП Научно исследовательский институт микроэлектронной аппаратуры "Прогресс"

Защита состоится 19 мая 2005 года в 10 часов на заседании диссертационного совета Д 002.078.01 в Институте проблем проектирования в микроэлектронике Российской академии наук (ИППМРАН) по адресу: 124681, г.Москва, ул. Советская, д.З.

С диссертацией можно ознакомиться в библиотеке ИППМ РАН.

Автореферат разослан 01 апреля 2005 г.

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

А.И. Корнилов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

По вопросам диссертации автором опубликовано 9 печатных работ, список которых приведен в конце автореферата

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

независимость каждого канала по отдельному модулю обеспечивает значительную гибкость при топологическом проектировании и планировке кристалла;

- трассировочные межсоединения распространяются только внутри отдельного канала для каждого модуля, что исключает наличие длинных трасс;

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

Обобщенная структура устройства цифровой обработки сигналов в модулярной арифметике представлена на рис. 1. Па входе данные Х(п) преобразовываются в модулярное представление в базисе модулей после чего производятся

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

Рис. 1. Обобщенная структураустройств ЦОС в модулярной арифметике.

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

- прямое и обратное модулярное преобразование;

- арифметические операции модулярного умножения;

- арифметические операции модулярного сложения.

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

Во второй главе проводится анализ и сравнение типовых структур модулярных сумматоров. Также описаны разработанные методы аппаратной реализации сумматоров по модулям вида (У-!) и (2"+/) в интегральном исполнении, дающие выигрыш в занимаемой площади по сравнению с типовыми структурами. Для значений модулей

разработаны методы логического синтеза сумматоров с ускоренным переносом на основе BDD-технологии.

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

- прямая логическая реализация с использованием блоков двоичной арифметики;

- реализация с использованием таблиц состояний (так называемых look-up tables);

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

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

В случае прямой логической реализации, суммирование по модулю для двух операндов а и b, находящихся в диапазоне {О, I, ...,т,-1}, выполняется по формуле:

Разрядность w модулярного сумматора для произвольного значения модуля т, определяется по формуле:

где через обозначена целая часть двоичного логарифма.

Формуле (1) соответствуют следующие основные типовые структуры:

- Структура 1, содержащая двоичный сумматор, вычитатель и выходной мультиплексор, управляемый выходом компаратора, сравнивающего внутреннюю сумму со значением модуля (рис. 2а);

- Структура 2, содержащая двоичный сумматор, вычитатель и выходной мультиплексор, который управляется знаковым разрядом вычитатсля (рис. 26).

Результаты сравнения типовых структур для различных значений модулей в базисе О 5мкм библиотеки стандартных ячеек показывают, что в интегральном исполнении эти структуры являются примерно равнозначными по площади и быстродействию, а выбор структуры для реализации модулярного сумматора зависит от требований, предъявляемых к нему, технологического базиса и, в первую очередь, от величины конкретного значения модуля

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

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

Сумматоры по модулю могут быть построены более эффективно с точки

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

от 0 до 2"*', где № - разрядность входных операндов, определяемая формулой (2) Таким образом, входные операнды и результат суммирования по модулю находится

внутри полного диапазона их возможного двоичного представления и максимальным

б)

Рис 2 Типовые структуры модулярных сумматоров

значением входного операнда является величина Т или в двоичном коде (10...0). Это означает, что старший разряд позиционного сумматора, входящего в состав модулярного сумматора, не зависит от выходного переноса младших разрядов и может быть реализован в соответствии с формулой:

int_sum[w]=a[w-l]b[w-l]

Следовательно, двоичный сумматор может иметь более компактную реализацию для старших бит входных операндов a[w-lj и b[w-l], в то время как структура позиционного сумматора для младших бит остается неизменной.

Следующим компонентом, который входит в состав модулярного сумматора и может быть реализован с меньшими аппаратными затратами, является вычитатсль константы, вычисляющий значение (а+Ь-т,). Принимая за основу Структуру ] (рис. 2а), можно видеть, что нет необходимости строить полный вычитатсль константы для всех значений (u+h), так как на выходе появляются з н а ч е няиЬ-тг/) л ь к о для тех величин (а+6), которые больше или равны /и,. Поэтому, при построении сумматоров по модулю вида (2"+1) для вычисления выражения (а^Ь-т,) может быть использован частично-определенный вычитатсль с разрядностью на один бит меньше разрядности входных операндов.

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

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

преобразовано в суммирование по модулю соответствии со следующей формулой:

выходной перенос позиционной суммы

Формула (3) соответствует реализации сумматоров с так называемым циклическим переносом из высшего разряда в низший (end-around-cany adder). То есть если перенос ст1 равен то входной перенос младшего разряда также равен и вычисляется сумма (а+Ь+1), а если перенос соШ равен 0, то входной перенос младшего разряда равен 0 и вычисляется сумма (а Ьб). Однако такой сумматор невозможно реализовать напрямую с использованием обычного двоичного сумматора, так как подача выходного переноса старшего разряда на входной перенос младшего разряда создает комбинационную

петлю и может привести к возникновению автогенерации Одним из способов решения этой проблемы является вычисление сумм (а+Ь+1) И (а+Ь) Для уменьшения аппаратных затрат предлагается модифицировать типовую архитектуру для сумматоров по модулю (2"-/) Предлагаемая структура приведена на рис 3

Модифицированная структура, приведенная на рис 3 представляется более оптимистичной по следующим причинам

во-первых, позиционные сумматоры (а+Ь) и (а+Ь+1) являются эквивалентными по площади и быстродействию, поэтому замена сумматора (а+Ь) на сумматор (а+Ь+1) не приводит к каким-либо ухудшениям по площади или быстродействию,

во-вторых, вычитатель единицы оперирует с урезанным значением внутренней позиционной суммы

в-трстьих, вычитатель единицы также является неполным, так как нас интересуют только тс значения которые меньше или равны

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

базисе в базисе 0 5мкм библиотеки стандартных ячеек для различных значений модулей разрядности до 7 бит Сравнение с типовой структурой показывает, что выигрыш по занимаемой площади достигает 20-25% в зависимости от значения модуля

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

Для построения сумматоров по модулю (2"-/) с ускоренным переносом предлагается использовать методы логического синтеза на основе BDD-технологии (в отечественных источниках вместо сокращения BDD - Binary Decision Diagram иногда используется переводная аббревиатура ДДР - Диаграмма Двоичных Решений)

Одной из возможных областей применения BDD является синтез комбинационных схем с использованием разложения Шеннона, которое для функции /имеет общий вид

sf w I 0j

mux

Рис 3 Модифицированная структура сумматора по модулю (2"-1)

f=*fUv*/U

(4)

Формула (4) в аппаратном исполнении соответствует реализации мультиплексора. Однако для традиционных КМОП схем целесообразно использовать монотонный базис. В этом случае удобно рассматривать диаграммы, представляющие иные способы разложения, чем разложение Шеннона. Такие структуры имеют название FDD -функциональные диаграммы решений. FDD обладают похожими с BDD свойствами, и к ним могут быть применимы аналогичные алгоритмы декомпозиции.

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

с,ч|=«,+т (5)

Формула (5) соответствует аппаратной реализации КМОП-элемента 2И-ИЛИ. Для системы функций переноса обычного двоичного сумматора представляется возможным построить функциональную диаграмму (FDD), в котором каждое звено соответствует указанному логическому элементу (рис. 4а). Для сумматоров по модулю в которых

выходной перенос равен входному, FDD принимает вид, показанный на рис. 46.

Рис. 4. FDD для п -разрядного сумматора (а) и преобразованная FDD для сумматора по

модулю (2"-1) (б).

Применим к структуре, изображенный на рис. 4б алгоритм декомпозиции, согласно которому длинная структура FDD может быть сведена обрывом ребра к двум диаграммам, при этом декомпозированные части реализованы параллельно (применительно к функциям переноса сумматора по модулю (2"-/) это соответствует левой и правой частям FDD), а также вводится дополнительная логика. Параллельная реализация обеспечивает более быстродействующую структуру с некоторым увеличением аппаратных затрат.

Таким образом, исходя из общей диаграммы, изображенной на рис. 4б, возможно

построить FDD для каждой из функций переноса с, для сумматора по модулю (■?"-/). При этом необходимо руководствоваться основным принципом, согласно которому, при построении диаграммы для переноса С; рачрсз осуществляется но ребру р,- Данное правило является определяющим при построении FDD для функций переноса сумматоров по модулю Соответственно из параллельной диаграммы можно получить

эквивалентную сокращенную структуру (рис. 5).

Рис. 5. Эквивалентная сокращенная FDD для сумматора помодулю (2"-1).

Подобно FDD для функции переноса можно построить диаграммы для любого переноса с,.

В качестве примера построим FDD функций переноса для сумматора по модулю ш=/5, при этом п=4 (рис. 6).

Рис. б. Исходная FDD для сумматора по модулю 15 и этапы декомпозиции

gJ р,

gi

Рис. 7. Декомпозиция FDD для функции переноса Cj.

Из исходной диаграммы получим FDD, например, для переноса С}, при этом разрез исходной диаграммы должен осуществляться по ребру рз. На рис. 7 приведена декомпозированная диаграмма для функции переноса Схемная реализация для переноса Cj, соответствующая построенной оптимизированной FDD приведена на рис. 8а. Как уже упоминалось, каждое звено диаграммы соответствует реализации на основе элемента 2И-ИЛИ. Для КМОП-базиса, используя правила де Моргана, также можно получить схему с использованием элементов

Рис.8. Аппаратная реализация функции переносаэ в базисе элементов 2И-ИЛИ (а), в базисеэлементов2И-ИЛИ-НЕ/2ИЛИ-И-НЕ(б).

Аппаратная реализация на основе элементов 2И-ИЛИ-НЕ'2ИЛИ-И-НЕ представляется наиболее оптимальной, так как в КМОП-базисе эти элементы обладают наименьшей глубиной и строятся на 6 транзисторах.

Предлагаемые методы логического синтеза сумматоров по модулю типа (2"-1) позволяют строить быстродействующие сумматоры по указанным модулям с увеличением быстродействия в 2 и более раз.

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

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

Индексное представление модулярного числа основывается на понятии первообразного корня по простому модулю т. Первообразным корнем g является целое число, возведение которого в степень дает неповторяющиеся вычеты по

модулю т. Т.е. преобразование модулярного числа строится по формуле (следует отмстить, что модуль должен быть простым числом):

где g - первообразный корень.

Исходя из понятия первообразного корня, отображение операции умножение двух модулярных чисел qJ и q^ по простому модулю т на операцию сложения по модулю (т-1) осуществляется по формуле:

- соответствующие индексы модулярных чисел

Отображение по формуле (6) называется изоморфизмом между мультипликативной

группой {</„}={/,2.....П1-1} с операцией умножения по модулю т и аддитивной группой

с операцией сложения по модулю

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

- нахождение индексов каждого модулярного числа;

- сложение полученных индексов по модулю

- выполнение обратного индексного преобразования.

Структурная схема индексного модулярного умножителя, соответствующая формуле (6), приведена на рис. 9.

<1/ Прямое индексное Сумматор по

преобразование Р модулю (ш-1) Обратное индексное преобразование 19/*«» 1» -

-►

Чк Прямое

индексное

р преобразование Чк -> ¡к Р

Рис. 9. Структурная схемаиндексногомодулярногоумножителя.

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

этом сумматор по модулю расщепляется на несколько модулярных сумматоров с

соответствующим набором подмодулей пкиЬ/.....1тиЬг. При этом подмодули

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

- подмодули должны быть попарно взаимно простыми.

В этом случае существует изоморфизм между индексным представлением {¡„} и субмодулярным разложением {1/„}={(/ц.....(/„.;}, так что: = {|'и|т-ги^ '"•,|'и|т,№(, ) для

П~0,1.....т-2. Это означает, что операция сложения по модулю (т-1) может быть

выполнена как множество параллельных операций модулярного сложения. Количество этих операций определяется количеством подмодулей

Таким образом, процедура умножения двух чисел по модулю т с использованием индексного субмодулярного разложения включает следующие стадии:

- нахождение прямого субмодулярного разложения для набора подмодулей;

- сложение полученных элементов разложения по подмодулям msub1;

- выполнение обратного преобразования из субмодулярного разложения в модулярное представление.

Структурная схема параллельного индексного субмодулярного умножителя приведена на рис. 10.

Обратное субмодулярное

индексное преобразование

Рис. 10. Структурная схема параллельного индексного субмодулярногоумножителя.

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

1. В системах цифровой обработки сигналов в модулярной арифметике целесообразно использовать модулярные индексные умножители по простым значениям модуля типа (.2"+/), например, 5, 17, 257. Следует заметить, что для таких значений индексные субмодулярные умножители не реализуются.

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

Т, например, модули 13 (разложение 3x4), 41 (разложение 5x8), 91 (разложение 3x32)

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

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

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

Восстановление числа А по его модулярному представлению {a¡ ai

в базисе

взаимно попарно простых модулей {m¡ m¡ mp} основан на фундаментальном положении, лежащем в основе модулярного представления чисел "Китайской теореме об остатках", которая устанавливает взаимно однозначное соответствие между целым числом Л и набором вычетов (и/ a¡ ар)

Математический алгоритм восстановления числа А выглядит следующим образом

- вычисляется произведение модулси М (W=J"|(1|"l ) Необходимо, чтобы

произведение модулси Мперекрывало диапазон представления числа Л,

- для набора модулси вычисляется набор структурных чисел

- для набора структурных чисел вычисляется числа, обратные им

где А,-1 определяется из условия х к~

1 =1

- число А восстанавливается по формуле

А =

j^a, хк, 1 х М/т.

(7)

Следует заметить, что для каждого модуля т, значение всегда

фиксировано, а величина I го вычета а, всегда меньше, чем сам модуль т, Поэтому при

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

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

разную разрядность, а суммирование чисел разной разрядности затруднит реализацию финального сумматора по составному модулю М. Предлагается модифицировать алгоритм предварительной обработки данных с целью более эффективной реализации преобразователя. Воспользуемся одним из свойств модулярной арифметики сумма по модулю Ш чисел лт/Дл ,хр равна сумме по этому модулю вычетов этих чисел, т с. формулу (7) можно переписать в виде:

Л,

а,хк, ' хМ 1т,

IМ

М

Л =

^\а,хк, хМ/тл |=Г ''

(8)

Замена формулы (7) на формулу (8) не приводит к усложнению аппаратной реализации предварительной обработки, так как размерность таблиц истинности не

меняется При этом предварительное вычисление произведений (а, х к, ' х М / т, ] по модулю М при построении преобразователя из модулярного представления в двоичное имеет следующие преимущества:

во-первых, разрядность результата на выходах таблиц истинности не увеличивается

в зависимости от значения произведения (а, х х М) т, ) и результат находится в диапазоне от 0 до М,

во-вторых, предварительно вычисленные значения (а, х к, ' х М / т, ) по модулю М упрощают реализацию финального сумматора по составному модулю М

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

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

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

Фильтр с конечной импульсной характеристикой в аппаратном исполнении соответствует формуле для вычисления свертки:

N

У(")= 1Ькх(п-к) к=0

(9)

где - входная и выходная последовательности соответственно, а

Ьк - коэффициенты фильтра.

Формуле (9) соответствуют две основные архитектуры аппаратной реализации фильтров.

На рис. 12 показана прямая форма реализации фильтра с конечной импульсной характеристикой, где /Г' соответствует элементу задержки. Отсчеты входных данных х(п) умножаются па соответствующие коэффициенты Ь, после каждого элемента задержки. Результаты умножения складываются на многовходовом сумматоре. Результат сложения соответствует выходной последовательности у(п).

Рис. 12. Фильтр сконечной импульснойхарактеристикой в прямой форме.

На рис. 13 приведена архитектура КИХ-фильтра в транспонированной форме. Отличие от прямой формы заключается в том, что суммирование результатов умножения входных отсчетов х(п) на соответствующие коэффициенты Ь/, происходит после каждого элемента задержки и результат суммирования поступает на вход следующего элемента задержки Таким образом, на выход продвигается накапливающаяся сумма

произведений входной последовательности х(п) на коэффициенты Ь

Рис 13 Фильтр с конечной импульснойхарактеристикой в транспонированной форме

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

В транспонированной форме (см рис 13) максимальная задержка определяется также задержкой умножителя и задержкой двухвходового

сумматора (вместо задержки многовходового сумматора) Т с транспонированная форма реализации фильтра является более быстродействующей Кроме того, транспонированная форма может быть эффективно использована при построении фильтра в модулярной арифметике, так как результаты модулярного сложения и модулярного умножения имеют такую же разрядность, что и входные операнды В этом случае разрядность накапливающейся суммы произведении не увеличивается после каждого элемента задержки Общую структуру КИХ-фильтра в транспонированной форме в модулярной арифметике можно представить в виде, показанным на рис 14 При этом будем считать, что коэффициенты являются перспрограммирусмыми (т е не константами) и могут быть уже представлены в модулярном форме

Рис N Структура фильтра в транспонированной форме в модулярной арифметике

Проведен анализ и сравнение КИХ-фильтров в двоичном и модулярном представлении. Экспериментальные результаты сравнения подтверждают, что использование транспонированной формы построения фильтров и предлагаемых методов построения модулярных сумматоров, умножителей и преобразователя в двоичное представление обеспечивают увеличение быстродействия фильтров (например, для 30-битного диапазона - почти в 2 раза). Необходимо также отметить, что для дальнейшего повышения быстродействия фильтров в модулярной форме целесообразно использовать принципы конвейерных вычислений при построении преобразователя из модулярного в двоичное представление.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

В ходе выполнения диссертационной работы был разработан ряд методов

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

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

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

2. Проведено сравнение типовых структур модулярных сумматоров, выполненных с применением блоков двоичной арифметики. Для сумматоров по модулям типа (2"+1) и

разработаны методы аппаратной реализации в интегральном исполнении, обеспечивающие выигрыш по занимаемой площади до 25-30% по сравнению с типовыми структурами.

3. Разработаны методы логического синтеза сумматоров по модулю (Т-1) на основе

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

и в базисе элементов 2И-ИЛИ.

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

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

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

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

Публикации. Основные результаты опубликованы в следующих работах:

1. Корнилов А.И., Исаева Т.Ю, Семенов M.IO. Методы логического синтеза сумматоров с ускоренным переносом по модулю (2п-1) на основе BDD-технологии // Известия ВУЗов. Электроника. - 2004. - Вып. 3. - С. 54-60.

2. Корнилов А.И., Семенов М.Ю., Ласточкин О.В. Принципы построения модулярных индексных умножителей//Известия ВУЗов. Электроника. -2004. -Вып. 2.-С. 48-55.

3. Семенов М.Ю. Особенности интегрального исполнения устройств цифровой обработки сигналов в модулярной арифметике // Микроэлектроника и информатика-2004. Одиннадцатая всероссийская межвузовская конференция студентов и аспирантов: Тезисы докладов. - М.: МИЭТ, 2004. - 444 с. - С. 238.

4. Стсмпковский А.Л., Корнилов А.И., Семенов М.Ю. Особенности реализации устройств цифровой обработки сигналов в интегральном исполнении с применением модулярной арифметики // Информационные технологии. - 2004. - Вып. 2. - С. 2-9.

5. Корнилов А.И., Семенов М.Ю., Калашников B.C. Методы аппаратной оптимизации сумматоров для двух операндов в системе остаточных классов // Известия ВУЗов. Электроника. - 2004. - Вып. 1. - С. 75-82.

6. Семенов М.Ю., Калашников B.C., Ласточкин О.В. Структура оптимизированных сумматоров, функционирующих в системе остаточных классов // Микроэлектроника и ииформатика-2003. Десятая всероссийская межвузовская конференция студентов и аспирантов: Тезисы докладов. - М.: МИЭТ, 2003. - 412 с. -С.91.

7. Исследование методов проектирования и разработка программных средств синтеза быстродействующих арифметических устройств // Отчет о НИР (проект №1.5/03, шифр "Вега-О-К-2003"), № госрегистрации 0120.0406674, инв. №02.2.00405859. -М.:ИППМ РАН. -2003.

8. Корнилов А.И., Семенов М.Ю. Преобразователь из модулярного представления в двоичную систему счисления на основе алгоритма с предварительной обработкой данных // Известия ВУЗов. Электроника. - 2003. - Вып. 3. - С. 54-58.

9. Калашников B.C., Ласточкин О.В., Семенов М.Ю. Лабораторный практикум по курсу "Основы логического синтеза средствами САПР Synopsys с использованием Vcrilog HDL" / под ред. чл.-корр. РАН, д.т.н. А.Л. Стемпковского. - М.: МИЭТ, 2004. - 88 с.

Of. Ш- OS. В

^ s»* -

** . / ? г

944

/

2? An;- zoos

Введение.

Глава 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. Виноградов И.М. Основы теории чисел. М.: Наука, Главная редакция физико-математической литературы, 1981. - 176 с.

6. Гольденберг JI.M., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов.- М.: Радио и связь, 1990. 256 с.

7. Евстигнеев В.Е. Недвоичная машинная арифметика и специализированные процессоры / Под ред. Акушского И .Я. М.: МИФИ Сервис, 1992. - 267 с.

8. Жуков О.Д. Обработка числовых данных с повышенной точностью в модулярной алгебре // Информационные технологии. 2004. - Вып. 2. - С. 1015.

9. Инютин С.А. Теория и методы моделирования вычислительных структур с параллелизмом машинных операций // Автореферат на соискание ученой степени доктора технических наук, Москва. 2001.

10. Исаева Т.Ю., Корнилов А.И. Алгоритм декомпозиции логических функций, ориентированный на синтез быстродействующих цифровых устройств // Информационные технологии. Вып. 4, 2001. - С. 26-31.

11. Исаева Т.Ю. Разработка и исследование методов логического синтеза быстродействующих КМОП БИС // Автореферат на соискание ученой степени кандидата технических наук, Москва. 2002.

12. Исследование методов проектирования и разработка программных средствсинтеза быстродействующих арифметических устройств // Заключительный отчет по НИР "Вега-0-К-2003" (проект № 1.5/03) (Инв. №02.2.00405859),-М.гИППМ РАН. -2003.

13. Калашников B.C. Основные виды архитектур модулярных сумматоров для двух операндов // Микроэлектроника и информатика-2004. Одиннадцатая всероссийская межвузовская конференция студентов и аспирантов. Тезисы докладов. М.: МИЭТ, 2004. - 444 с. - С. 217.

14. Калашников B.C., Ласточкин О.В., Семенов М.Ю. Лабораторный практикум по курсу "Основы логического синтеза средствами САПР Synopsys с использованием Verilog HDL" / под ред. чл.-корр. РАН, д.т.н. А.Л. Стемпковского. М.: МИЭТ, 2004. - 88 с.

15. Кнут Дональд Э. Искусство программирования, том 2. Получисленные алгоритмы. М.: Издательский дом "Вильяме", 2001. - 832 с.

16. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.-960 с.

17. Корнилов А.И. Построение быстродействующих арифметических устройств в одном универсальном логическом базисе // Техника средств связи. Сер. Микроэлектронная аппаратура. 1990. - Вып.1-2(12-13). - С. 41-47.

18. Корнилов А.И., Исаева Т.Ю., Семенов М.Ю. Методы логического синтеза сумматоров с ускоренным переносом по модулю (2п-1) на основе BDD-технологии // Известия ВУЗов. Электроника. 2004. - Вып. 3. - С. 54-60.

19. Корнилов А.И., Семенов М.Ю. Преобразователь из модулярного представления в двоичную систему счисления на основе алгоритма с предварительной обработкой данных // Известия ВУЗов. Электроника. 2003. - Вып. 3. - С. 54-58.

20. Корнилов А.И., Семенов М.Ю., Калашников B.C. Методы аппаратной оптимизации сумматоров для двух операндов в системе остаточных классов// Известия ВУЗов. Электроника. 2004. - Вып. 1. - С. 75-82.

21. Корнилов А.И., Семенов М.Ю., Ласточкин О.В. Принципы построения модулярных индексных умножителей // Известия ВУЗов. Электроника. 2004. -Вып. 2.-С. 48-55.

22. Сергиенко А.Б. Цифровая обработка сигналов. СПб.: Питер, 2002. - 608 с.

23. Стемпковский A.JL, Корнилов А.И., Семенов М.Ю. Особенности реализации устройств цифровой обработки сигналов в интегральном исполнении с применением модулярной арифметики // Информационные технологии. 2004. -Вып. 2.-С. 2-9.

24. Титце У., Шенк К. Полупроводниковая схемотехника. М: Мир, 1982. - 2 С.

25. Угрюмов Е. Цифровая схемотехника. СПб.: БХВ-Петербург, 2001. - 528с.

26. Финько О.А. Модулярная арифметика параллельных логических вычислений / Под ред. В.Д. Малюгина. М.: Институт проблем управления РАН; Краснодар: Краснодарский военный институт, 2003.-224 с.

27. 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.

28. Bryant R.E. Graph-Based Algorithms // IEEE Transactions on Computers- Aug. 1986. V. C-35, N 8. - P. 677-691.

29. Bryant R.E. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams // ACM Computing. 1992. - V. 24, N 3.

30. 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.

31. Becker В., Drechsler R. How Many Decomposition Types Do We Need? // Proc.of

32. IP Workshop on Logic and Architecture Synthesis, Institut National Polytechnique de Grenoble, France, 19-20 December, 1994.

33. 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.

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

39. David R.Smith. "Verilog Styles for Synthesis of Digital Systems", Prentice Hall, Inc. 2000.

40. 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. 13091313.

41. 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.

42. 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.

43. 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.

44. Hiasat A. New Memoryless, mod (2n±l) Residue Multiplier // IEEE Electronic Letters, 30 Januaiy 1992. -V. 28, N3. P. 314-315.

45. 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.

46. 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.

47. Kebschull U., Schubert E., Rosenstiel W. Multilevel Logic Synthesis Based on Functional Decision Diagrams // Proc. of ICC AD. 1992. - P. 43-47.

48. 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.

49. 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.

50. 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.

51. Massey James L. An Introduction to Contemporary Cryptology // Proc. of IEEE. May 1988. - V. 76, N 5. - P. 533-549.

52. 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.

53. 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.

54. Radhakrishnan D., Yuan Y. A Fast RNS Galois Field Multiplier // IEEE International Symposium on Circuits and Systems. May 1990. -V. 4. - P. 2909-2912.

55. 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.

56. 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.

57. 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.

58. Soderstrand 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.

59. Taylor F.J. An RNS Discrete Fourier Transform Implementation // IEEE Transactions on Acoustics, Speech, and Signal Processing. Aug. 1990. - V. 38, N 8. - P. 13861394.

60. Wall Larry, Christiansen Tom and Schwartz Randal with Stephen Potter Programming Perl, Second Edition. O'Reilly & Associates, Inc. Copyright 1996.

61. Walter C.D. Systolic Modular Multiplier // IEEE Trans. Computers. Mar. 1993. -V. 42, N3.-P. 376-378.