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

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

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

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

Представление чисел в прямом коде: Основы, особенности и ограничения

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

Принципы прямого кода и его форматы

В своей основе прямой код предназначен для представления как положительных, так и отрицательных чисел. Ключевая особенность заключается в том, что для знаковых чисел старший разряд (так называемый знаковый бит) используется исключительно для индикации знака: ‘0’ обозначает положительное число, а ‘1’ — отрицательное. Все остальные разряды, именуемые цифровыми, содержат двоичное представление абсолютного значения (модуля) числа.

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

• Если число A ≥ 0, его прямой код [A]ПР просто равен самому числу A.
• Если число A < 0, его прямой код [A]ПР вычисляется как 2^N + |A|, где N — общее количество разрядов, отведённых под число, а 2^N соответствует весу знакового разряда. Например, для 8-разрядного числа, где знаковый разряд находится в 7-й позиции (если считать с 0), N=7, и формула примет вид 2⁷ + |A|.

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

• Если A ≥ 0, [A]ПР = A.
• Если A < 0, [A]ПР = 1 + |A|.

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

A = (1 - 2aзнак) ∑ni=-k aipi

Где:

• aзнак — это значение знакового разряда (0 для ‘+’ и 1 для ‘-‘).
• ai — значение i-го разряда числа.
• p — основание системы счисления (для двоичных чисел p=2).
• n — номер старшего разряда целой части.
• -k — номер младшего разряда дробной части.

Преимущества и недостатки прямого кода

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

Однако у прямого кода есть и существенные недостатки. Самый заметный из них — существование двух представлений для числа ноль: +0 (все нули) и -0 (единица в знаковом разряде, остальные нули). Это усложняет логику сравнения на равенство нулю и может приводить к ошибкам в программах, если не учитывать эту особенность. Следовательно, при проектировании системы на прямом коде, требуется либо дополнительная логика для обработки нуля, либо строгое соглашение о его представлении.

Особенности арифметических операций в прямом коде (акцент на умножении)

Наибольшие сложности прямой код создаёт при выполнении операций алгебраического сложения и вычитания. Если операнды имеют одинаковые знаки, сложение модулей и сохранение общего знака относительно просты. Однако, когда знаки операндов различны, ситуация усложняется: необходимо сначала определить, какое из чисел больше по модулю, затем выполнить операцию вычитания меньшего модуля из большего, и только после этого присвоить результату знак числа, имевшего больший модуль. Этот процесс требует раздельной обработки знаковых и цифровых разрядов, а также наличия как суммирующего, так и вычитающего устройств в арифметико-логическом блоке (АЛБ), что значительно усложняет архитектуру процессора и снижает его эффективность. Почему это важно? Потому что усложнение архитектуры напрямую ведет к увеличению числа транзисторов, повышению энергопотребления и снижению тактовой частоты.

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

1. Перемножение модулей: Абсолютные значения (модули) сомножителей перемножаются так, как если бы они были беззнаковыми числами.
2. Определение знака результата: Знак итогового произведения определяется отдельно, как сумма по модулю два (операция «исключающее ИЛИ», ⊕) знаковых разрядов множимого и множителя (знак Z = знак X ⊕ знак Y). Это означает, что если знаки одинаковы, результат будет положительным (0 ⊕ 0 = 0, 1 ⊕ 1 = 0), а если различны — отрицательным (0 ⊕ 1 = 1, 1 ⊕ 0 = 1).

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

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

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

Обзор методов умножения двоичных чисел

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

1. С младших разрядов множителя, сдвиг множимого влево, сумма частичных произведений неподвижна. Это классический «школьный» метод, перенесённый в двоичную арифметику. Частичные произведения формируются путём умножения множимого на каждый бит множителя, начиная с младшего, и сдвига множимого влево перед каждым последующим сложением.
2. С младших разрядов множителя, сдвиг суммы частичных произведений вправо, множимое неподвижно. В этом методе множимое остаётся на месте, а сумма частичных произведений сдвигается вправо. Это часто используется в аппаратных реализациях, так как упрощает регистры множимого.
3. Со старших разрядов множителя, сдвиг суммы частичных произведений влево, множимое неподвижно. В данном подходе обработка начинается со старшего бита множителя. Частичные произведения накапливаются в регистре, который сдвигается влево.
4. Со старших разрядов множителя, сдвиг множимого вправо, сумма частичных произведений неподвижна. Этот метод является предметом нашего детального рассмотрения. Его преимущество заключается в том, что регистр для накопления частичных произведений не требует цепей сдвига, что упрощает его схемотехническую реализацию. Однако это перекладывает сложность на регистр множимого, который должен поддерживать сдвиг вправо.

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

Пошаговое описание алгоритма: Микрооперации и логика сдвигов

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

Инициализация:

1. Регистр множимого (|X|): Исходное значение модуля множимого помещается в старшие N разрядов регистра длиной 2N (двойная длина), а младшие N позиций заполняются нулями. Этот регистр будет подвергаться сдвигам.
2. Регистр множителя (|Y|): Модуль множителя помещается в N-разрядный регистр. Его разряды y_i будут анализироваться последовательно, начиная со старшего.
3. Сумматор частичных произведений (СЧП): Это регистр длиной 2N, инициализируется нулями. Он будет накапливать окончательный результат и не будет сдвигаться в процессе умножения.
4. Счётчик: N-разрядный счётчик циклов инициализируется значением N (или N-1, в зависимости от логики завершения) и будет уменьшаться на единицу на каждом шаге.

Цикл умножения (N шагов):

На каждом шаге (итерации) цикла, начиная со старшего разряда множителя (y_N-1), выполняются следующие микрооперации:

1. Анализ разряда множителя: Проверяется значение текущего анализируемого разряда множителя y_i.
   • Если y_i = 1: Содержимое регистра множимого (|X|), сдвинутое вправо на текущее количество разрядов (то есть, его текущее значение после предыдущих сдвигов), добавляется к содержимому регистра СЧП.
   • Если y_i = 0: К СЧП добавляется ноль. То есть, сложение не производится, но цикл продолжается.
2. Сдвиг множимого: Регистр, хранящий модуль множимого (|X|), сдвигается вправо на 1 разряд. Это подготавливает его к следующему шагу, фактически формируя следующее частичное произведение, сдвинутое относительно предыдущего.
3. Декремент счётчика: Значение счётчика уменьшается на единицу.
4. Проверка завершения: Если счётчик достиг нуля, операция умножения завершена. В противном случае цикл повторяется для следующего разряда множителя.

Таким образом, множимое постепенно «уходит» вправо, а его соответствующие значения, умноженные на 0 или 1 (в зависимости от бита множителя), добавляются к неподвижной сумме частичных произведений.

Требования к регистрам:

• Регистр множителя (|Y|) должен быть оснащён цепями для сдвига влево или иметь прямой доступ к своим разрядам для последовательного чтения от старшего к младшему.
• Регистр множимого (|X|) должен иметь цепи для сдвига вправо. Его двойная длина необходима для корректного размещения частичных произведений без потери точности при сдвигах.
• Сумматор частичных произведений (СЧП) также должен быть двойной длины, чтобы вместить полный результат произведения (до 2N разрядов). Отсутствие необходимости сдвига для СЧП упрощает его схемотехнику.

Пример выполнения операции умножения

Рассмотрим пример умножения двух 4-разрядных чисел в прямом коде: X = 0101₂ (+5) и Y = 0011₂ (+3).

Знак произведения: знак Z = знак X ⊕ знак Y = 0 ⊕ 0 = 0 (положительное).

Модули: |X| = 1012, |Y| = 0112.

Для 4-разрядных чисел, регистры |X| и СЧП будут иметь длину 2N = 8 разрядов.

Исходные данные:

• |X| (в регистре длиной 8): 010100002 (старшие 4 бита — модуль, младшие 4 — нули).
• |Y| (в регистре длиной 4): 00112 (анализируем старшие разряды).
• СЧП (в регистре длиной 8): 000000002.
• Счётчик: 4.

Шаг 1 (y₃ = 0):

• Разряд множителя y₃ = 0. Сложение с СЧП не производится.
• Сдвиг |X| вправо: 001010002.
• Счётчик: 3.
• СЧП: 000000002.

Шаг 2 (y₂ = 0):

• Разряд множителя y₂ = 0. Сложение с СЧП не производится.
• Сдвиг |X| вправо: 000101002.
• Счётчик: 2.
• СЧП: 000000002.

Шаг 3 (y₁ = 1):

• Разряд множителя y₁ = 1.
• Сложение: СЧП = СЧП + |X| (текущее сдвинутое) = 000000002 + 000101002 = 000101002.
• Сдвиг |X| вправо: 000010102.
• Счётчик: 1.
• СЧП: 000101002.

Шаг 4 (y₀ = 1):

• Разряд множителя y₀ = 1.
• Сложение: СЧП = СЧП + |X| (текущее сдвинутое) = 000101002 + 000010102 = 000111102.
• Сдвиг |X| вправо: 000001012.
• Счётчик: 0.
• СЧП: 000111102.

Счётчик достиг нуля, операция завершена.

Результат: Z = 000111102 (в прямом коде, так как знак 0).

000111102 = 16 + 8 + 4 + 2 = 3010.

Отметим, что для классического умножения целых чисел 5 × 3 ожидаемым результатом является 15. Полученный результат 30 свидетельствует о том, что данный алгоритм, применённый к числам, интерпретируемым как целые, фактически производит умножение 5 * 3 * 21 или 5 * 2 * 3, если рассматривать множимое как сдвинутое. Это указывает на его специфическое применение, возможно, для дробных чисел или требующее иной интерпретации начального состояния регистров. При проектировании реальной системы крайне важно учитывать эту особенность, чтобы избежать неверных вычислений и обеспечить соответствие алгоритма ожидаемой семантике чисел.

Синтез управляющего устройства на базе автомата Мура

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

Введение в конечные автоматы: Модели Мура и Мили

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

Ключевое различие между ними заключается в способе формирования выходных сигналов:

• Автомат Мили (Mealy machine): Выходные сигналы зависят как от текущего состояния автомата, так и от текущих входных сигналов. Это обеспечивает быструю реакцию на изменения входов, но может приводить к нестабильности выходных сигналов во время переходных процессов, а также к появлению «сквозных» задержек от входа к выходу через комбинационную логику.
• Автомат Мура (Moore machine): Выходные сигналы зависят исключительно от текущего состояния автомата. Они изменяются только при смене состояния, то есть на следующем такте синхронизации после изменения входов.

Преимущества автомата Мура для управляющих устройств:

• Стабильность выходов: Поскольку выходы зависят только от состояния, они остаются стабильными на протяжении всего такта синхронизации, исключая появление ложных сигналов (глюков) из-за переходных процессов на входах.
• Минимальная выходная задержка: При реализации с выходным регистром, задержка выходного сигнала сводится к задержке переключения самого регистра относительно синхросигнала (параметр T_CO), что является физически минимальной задержкой.
• Простота описания на HDL: Автоматы Мура легко и понятно описываются на языках описания аппаратуры (HDL), таких как VHDL и Verilog. Для описания автомата Мура с регистровым выходом часто достаточно одного блока process (CLK) в VHDL или always@ (posedge CLK) в Verilog, что упрощает синтез и верификацию.
• Предсказуемость: Поведение автомата более предсказуемо и детерминировано, что важно для надёжных управляющих систем.

Благодаря этим преимуществам, автоматы Мура широко применяются в проектировании управляющей логики для цифровых устройств на основе программируемых логических интегральных схем (ПЛИС), например, в контроллерах пешеходных переходов, управляющих блоках электронных часов или в арифметико-логических устройствах микрокалькуляторов.

Формальное определение и ключевые характеристики автомата Мура

Формально, автомат Мура определяется как кортеж из шести элементов:

M = (S, s0, X, Y, Φ, G)

Где:

• S — конечное, непустое множество внутренних состояний автомата.
• s₀ — начальное состояние, элемент S.
• X — конечное, непустое множество входных сигналов (входной алфавит).
• Y — конечное, непустое множество выходных сигналов (выходной алфавит).
• Φ: S × X → S — функция переходов, которая для каждой пары (текущее состояние, входной сигнал) определяет следующее состояние автомата.
• G: S → Y — функция вывода, которая каждому внутреннему состоянию сопоставляет определённый выходной сигнал. Это ключевое отличие от автомата Мили, где функция вывода имеет вид G: S × X → Y.

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

Применение автомата Мура в проектировании управляющих устройств

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

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

• Чёткая синхронизация: Выходные управляющие сигналы, генерируемые автоматом Мура, являются стабильными в течение всего такта, что предотвращает гонки сигналов и обеспечивает предсказуемое поведение ОУ.
• Модульность и иерархия: Управляющее устройство, построенное на автомате Мура, легко интегрируется с операционным устройством. УУ получает признаки (условия) от ОУ (например, «счётчик равен нулю», «знак числа») и на их основе определяет следующее состояние и генерирует новые управляющие сигналы.
• Предсказуемость поведения: Поскольку выход зависит только от состояния, поведение управляющего автомата легко моделировать, анализировать и верифицировать, что значительно упрощает процесс проектирования сложных цифровых систем.

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

Проектирование графа функционирования управляющего автомата для операции умножения

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

Состояния управляющего автомата для умножителя:

1. S₀ (Инициализация): Начальное состояние. Здесь происходит загрузка множимого и множителя в соответствующие регистры операционного устройства, обнуление аккумулятора и счётчика циклов.
   • Микрокоманды: LOAD_X, LOAD_Y, CLR_P, LOAD_COUNTER(N).
   • Переход: Безусловный переход в состояние S₁ (Начало цикла).
2. S₁ (Начало цикла): Состояние, в котором начинается каждая итерация умножения. Здесь анализируется старший (или текущий) разряд множителя.
   • Условие перехода (x₁): Анализ текущего бита множителя yi.
     • Если yi = 1: Переход в состояние S₂ (Сложение).
     • Если yi = 0: Переход в состояние S₃ (Сдвиг).
3. S₂ (Сложение): В этом состоянии выполняется сложение текущего значения множимого (после соответствующих сдвигов) с содержимым регистра СЧП.
   • Микрокоманды: ADD_P_X (P = P + X_{сдвинутое}).
   • Переход: Безусловный переход в состояние S₃ (Сдвиг).
4. S₃ (Сдвиг): В этом состоянии происходит сдвиг регистра множимого вправо на один разряд и декремент счётчика циклов.
   • Микрокоманды: SHIFT_X_RIGHT, DEC_COUNTER.
   • Условие перехода (x₂): Проверка значения счётчика.
     • Если COUNTER = 0: Переход в состояние S₄ (Завершение).
     • Если COUNTER > 0: Переход в состояние S₁ (Начало следующего цикла).
5. S₄ (Завершение): Конечное состояние, сигнализирующее об окончании операции умножения. Может генерировать сигнал «Готово» или «Результат доступен».
   • Микрокоманды: SIGNAL_DONE.
   • Переход: В S₀ (для готовности к новой операции) или оставаться в S₄ до внешнего сброса.

Граф функционирования (концептуальный):

                  ┌─────────┐
                  │   S0    │  Инициализация (LOAD_X, LOAD_Y, CLR_P, LOAD_COUNTER(N))
                  └────┬────┘
                       │
                       ▼
                  ┌─────────┐
                  │   S1    │  Начало цикла (Анализ y_i)
                  └────┬────┘
            y_i=1 ┌────┴────┐ y_i=0
                  ▼         ▼
             ┌─────────┐   ┌─────────┐
             │   S2    │   │   S3    │
             │ Сложение│   │  Сдвиг  │
             │ (ADD_P_X)│   │ (SHIFT_X_RIGHT, DEC_COUNTER) │
             └────┬────┘   └────┬────┘
                  │             │
                  └──────┬──────┘
                         │
                         ▼
                  ┌─────────┐
                  │  Проверка СЧЁТЧИКА │
                  └────┬────┘
            СЧЁТЧИК=0 ┌┴┐ СЧЁТЧИК>0
                      ▼
                 ┌─────────┐
                 │   S4    │  Завершение (SIGNAL_DONE)
                 └─────────┘

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

Аппаратная реализация операционного и управляющего устройства

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

Структурная схема операционного устройства

Операционное устройство (ОУ) является совокупностью функциональных блоков, способных выполнять микрооперации над данными. Для реализации операции умножения N-разрядных чисел ОУ должно включать:

1. Арифметико-логический блок (АЛБ): Ядро ОУ, отвечающее за выполнение базовых арифметических (сложение) и логических операций. В нашем случае, это N+1-разрядный сумматор, который может складывать два N+1-разрядных числа. Дополнительный разряд необходим для корректной обработки переноса при сложении частичных произведений.
2. Регистры общего назначения (РОН):
   • R1 (Регистр множимого |X|): N-разрядный регистр для хранения модуля множимого.
   • R2 (Регистр множителя |Y|): N-разрядный регистр для хранения модуля множителя. Этот регистр должен иметь возможность сдвига влево для последовательной выдачи разрядов множителя.
   • R3 (Регистр частичных произведений / Аккумулятор P): 2N-разрядный регистр, который накапливает сумму частичных произведений. Он должен иметь возможность загрузки и сдвига вправо (для множимого, не для суммы).
   • R4 (Временный регистр / Расширенное множимое X’): 2N-разрядный регистр для хранения множимого, сдвинутого вправо на каждом шаге. Именно это значение будет подаваться на сумматор.
3. Счётчик (Сч): N-разрядный счётчик циклов, необходимый для отслеживания количества выполненных итераций. Он уменьшается на единицу на каждом шаге и сигнализирует о завершении операции, когда достигает нуля.
4. Блок формирования условий (регистр условий): Генерирует признаки (флаги), такие как «счётчик равен нулю», «текущий бит множителя равен 1», которые передаются управляющему устройству.

Пример структурной схемы операционного устройства:

          ┌──────────────────────────────────────────────────┐
          │                  Управляющее устройство (УУ)     │
          │                   (Автомат Мура)                 │
          │                                                  │
          │                   → Управляющие сигналы (yk)    │
          │                                                  │
          └───────────────────┬──────────────────────────────┘
                              │
                     ┌────────┴─────────┐
                     │                  │
                     │  Операционное устройство (ОУ)          │
                     │                  │
                     │  ┌───────────────┴──────────────┐      │
                     │  │ Регистр множимого R1 (|X|)   │      │
                     │  ├──────────────────────────────┤      │
                     │  │ Регистр множителя R2 (|Y|)   │──────┼─(yi)─> УУ (бит множителя)
                     │  ├──────────────────────────────┤      │
                     │  │ Регистр множимого R4 (X', 2N) │──────┼─> Сумматор
                     │  │   (сдвиг вправо)             │      │
                     │  ├──────────────────────────────┤      │
                     │  │ Регистр произведения R3 (P, 2N)│<─────┼─ Сумматор
                     │  │   (Аккумулятор)              │      │
                     │  ├──────────────────────────────┤      │
                     │  │ Счетчик (N-бит)              │──────┼─(xсчётчик_ноль)─> УУ
                     │  ├──────────────────────────────┤      │
                     │  │ N+1-разрядный Сумматор (См)  │<─────┼─ R3 (P)
                     │  └───────────────┬──────────────┘      │
                     │                  │                     │
                     │                  └────────────<─ Управляющие сигналы (yk)
                     │                                        │
                     └────────────────────────────────────────┘

• Назначение элементов:
  • R1 (|X|): Хранит исходный модуль множимого. Может быть загружен из внешней шины данных.
  • R2 (|Y|): Хранит модуль множителя. Имеет выход для текущего (старшего) бита множителя, который поступает на УУ. Должен иметь функцию сдвига влево для подачи следующего бита на анализ.
  • R4 (X'): 2N-разрядный сдвиговый регистр, инициализированный |X| в старших N битах, младшие N битов нули. На каждом шаге сдвигается вправо и его содержимое подаётся на один из входов сумматора.
  • R3 (P): Аккумулятор, хранящий текущую сумму частичных произведений. Его выход подаётся на второй вход сумматора, а результат сложения записывается обратно в него. Неподвижен в том смысле, что его содержимое не сдвигается внутри него.
  • См (Сумматор): N+1-разрядный комбинационный сумматор.
  • Сч (Счетчик): Отсчитывает N циклов.

Детализация микроопераций и управляющих сигналов

Каждое действие в операционном устройстве соответствует микрооперации, которая инициируется соответствующим управляющим сигналом (y_k), генерируемым управляющим устройством.

Основные микрооперации и их управляющие сигналы:

Микрооперация	Описание	Управляющий сигнал (yk)
LOAD_X	Загрузка модуля множимого |X| в регистр R4 (расширенный до 2N бит, со сдвигом влево на N позиций).	yЗАГРУЗКА_X
LOAD_Y	Загрузка модуля множителя |Y| в регистр R2.	yЗАГРУЗКА_Y
CLR_P	Обнуление регистра произведения R3.	yОЧИСТИТЬ_P
LOAD_COUNTER(N)	Загрузка начального значения N в счётчик.	yЗАГРУЗКА_СЧЁТЧИКА
ADD_P_X_SHIFTED	Сложение содержимого регистра R3 (P) с текущим содержимым регистра R4 (X’) и запись результата обратно в R3.	yСЛОЖЕНИЕ
SHIFT_R4_RIGHT	Логический сдвиг содержимого регистра R4 (X’) вправо на один разряд.	yСДВИГ_R4
SHIFT_R2_LEFT	Логический сдвиг содержимого регистра R2 (|Y|) влево на один разряд (для анализа следующего бита множителя).	yСДВИГ_R2
DEC_COUNTER	Уменьшение значения счётчика на единицу.	yУМЕНЬШЕНИЕ_СЧЁТЧИКА
SIGNAL_DONE	Установка флага завершения операции.	yГОТОВО

Взаимодействие операционного и управляющего устройства: Синхронизация и обратная связь

Синхронизация между ОУ и УУ осуществляется тактовым сигналом CLK. В каждом такте УУ, находясь в определённом состоянии, генерирует набор управляющих сигналов (z_i, или y_k в предыдущей таблице), которые активируют одну или несколько микроопераций в ОУ.

Механизм взаимодействия:

1. Управляющие сигналы от УУ к ОУ: УУ, на основе своего текущего состояния и, возможно, входных признаков от ОУ, формирует комбинацию управляющих сигналов. Эти сигналы подаются на входы управления регистров, сумматоров и счётчиков в ОУ, разрешая или запрещая выполнение конкретных микроопераций (например, yСЛОЖЕНИЕ активирует сложение, yСДВИГ_R4 активирует сдвиг R4).
2. Признаки от ОУ к УУ (Обратная связь): После выполнения микроопераций в ОУ, формируются признаки (x_i), которые отражают состояние ОУ. Например, блок формирования условий в ОУ может генерировать сигнал xСЧЁТЧИК_НОЛЬ, если счётчик достиг нуля, или xБИТ_Y_ЕДИНИЦА, если текущий бит множителя равен единице. Эти признаки поступают на входы УУ и используются им для определения следующего состояния (условные переходы в графе функционирования).

Таким образом, УУ «читает» состояние ОУ через признаки, «думает» (переходит в следующее состояние) и «действует» (посылает новые управляющие сигналы), замыкая петлю управления.

Примеры схем комбинационных узлов

1. Полный одноразрядный сумматор:

        Ai ───┐     ┌─── Si
        Bi ───┼──XOR─┤
        Cвх ─┴─┐ ┌──XOR─┘
              AND ├─┐
                  AND ├─OR─ Cвых
              XOR ┴─┐
        Ai ───┐    │
        Bi ───┘    │

Логические выражения:

• Si = Ai ⊕ Bi ⊕ Cвх
• Cвых = (Ai · Bi) ∨ (Cвх · (Ai ⊕ Bi))

2. D-триггер с синхронной загрузкой (основа регистра):

Каждый бит регистра реализуется на D-триггере.

        D ───┐
             D─┐
        CLK ─CLK─Q
             E─┘
        E ───┘

Логика: По положительному фронту CLK, если E=1, Q = D.

3. Фрагмент 2N-разрядного сдвигового регистра (R4) сдвига вправо:

Каждый триггер Qi принимает данные от Qi+1.

        QN-1 ← DN-1
        ...
        Qi ← Di = Qi+1
        ...
        Q0 ← D0 = Q1

При логическом сдвиге вправо самый старший бит Q2N-1 получает 0.

Эти элементарные узлы, объединённые и управляемые автоматом Мура, формируют полноценную аппаратную реализацию умножителя.

Оптимизация аппаратурных затрат через кодирование состояний автомата Мура

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

Методы кодирования состояний: Обзор и выбор оптимальной стратегии

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

1. Бинарное (двоичное) кодирование: Самый компактный метод, использующий минимальное количество D-триггеров (⌊log2 Nсостояний⌋), где Nсостояний — количество состояний. Например, для 4 состояний достаточно 2 триггеров (00, 01, 10, 11). Простота кодирования, но может приводить к сложной комбинационной логике из-за большого количества переключающихся битов при смене состояния.
2. Кодирование Грея: Разновидность бинарного кодирования, где при переходе между соседними состояниями изменяется только один бит кода. Это минимизирует глитчи и энергетические затраты, но не всегда оптимально для произвольных графов состояний.
3. Унитарное (One-Hot) кодирование: Для N состояний используется N D-триггеров. В каждый момент времени только один триггер находится в активном состоянии (‘1’), остальные — в неактивном (‘0’). Это наиболее аппаратно избыточный метод по числу триггеров, но он значительно упрощает комбинационную логику, поскольку условия переходов и выходы легко формируются путём простого ИЛИ-рования нескольких выходов триггеров. Это обеспечивает высокую скорость и простоту проектирования.

Для D-триггеров часто рекомендуется использовать частотную стратегию кодирования, которая может включать элементы унитарного кодирования (one-hot encoding). Суть подхода в том, что состояния, которые встречаются наиболее часто в графе функционирования, кодируются наиболее простыми комбинациями, например, нулевой комбинацией, а следующие по частоте состояния — комбинациями с одной единицей (т.е. one-hot). Например, если у нас есть N состояний, и мы выбираем one-hot, то для каждого состояния будет выделен свой триггер, и только один из них будет активен в каждый момент времени. Это упрощает логику декодирования состояния и формирования управляющих сигналов.

Влияние кодирования на аппаратурные затраты и тестопригодность

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

• Количество логических элементов: Бинарное кодирование минимизирует число триггеров, но часто увеличивает сложность комбинационной логики (количество И, ИЛИ, НЕ элементов). Унитарное кодирование, наоборот, требует больше триггеров, но существенно упрощает комбинационную логику, что может быть выгодным для ПЛИС, где триггеры (LUTs) часто доступны в избытке.
• Быстродействие (задержки): Упрощение комбинационной логики (как в случае с one-hot) приводит к уменьшению задержек распространения сигнала, что повышает тактовую частоту автомата.
• Тестопригодность: Под тестопригодностью понимается лёгкость обнаружения и локализации неисправностей. Оптимальное по тестопригодности кодирование позволяет создавать схемы, которые по аппаратурным затратам не превышают известные интегральные схемы счётчиков, но при этом обладают минимальной длиной отличительной последовательности (последовательности входных сигналов, которая позволяет определить текущее состояние автомата). Это существенно сокращает время и ресурсы, необходимые для тестирования.

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

Примеры кодирования состояний для управляющего автомата умножителя

Для нашего управляющего автомата умножителя, имеющего 5 состояний (S₀, S₁, S₂, S₃, S₄), можно рассмотреть несколько вариантов кодирования.

1. Бинарное кодирование:

Потребуется ⌊log2 5⌋ = 3 D-триггера.

• S₀: 000
• S₁: 001
• S₂: 010
• S₃: 011
• S₄: 100

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

2. Унитарное (One-Hot) кодирование:

Потребуется 5 D-триггеров (по одному на каждое состояние).

• S₀: 00001
• S₁: 00010
• S₂: 00100
• S₃: 01000
• S₄: 10000

Этот метод, несмотря на большее количество триггеров, часто предпочтителен для ПЛИС, поскольку:

• Функции возбуждения D-триггеров (следующее состояние) и выходные функции (управляющие сигналы) становятся очень простыми. Например, для перехода из S₁ в S₂ при yi=1, функция возбуждения для триггера Q2 (соответствующего S₂) будет D2 = Q1 & yi.
• Выходные сигналы напрямую связаны с активным триггером состояния. Например, если yЗАГРУЗКА_X генерируется в S₀, то yЗАГРУЗКА_X = Q0.

Это значительно упрощает логику и ускоряет работу автомата.

Выбор стратегии:

Для большинства современных ПЛИС, где логические ячейки (LUTs) часто содержат триггеры, унитарное кодирование является предпочтительным. Оно обеспечивает высокую скорость работы управляющего устройства за счёт минимизации задержек в комбинационной логике, а также упрощает отладку и тестирование. Простота логических выражений для функций переходов и выходов, характерная для one-hot, снижает вероятность ошибок проектирования и облегчает верификацию. Не стоит ли тогда считать его фактически стандартом де-факто для подобных задач?

Заключение

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

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

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

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

Список использованной литературы

1. Калабеков Б.А. Цифровые устройства и микропроцессорные системы: учебник для техникумов. Москва: Горячая линия — ТЕЛЕКОМ, 2002.
2. Бродин В.Б., Калинин А.В. Системы на микроконтроллерах и БИС программируемой логики. Москва: ЭКОМ, 2002.
3. Фрунзе А.В. Микроконтроллеры? Это же просто! Москва: ООО «ИД СКИМЕН», 2002.
4. Технические аспекты построения управляющих автоматов при проектировании цифровых устройств на основе современных ПЛИС // Журнал «Компоненты и технологии». 2012. № 2. URL: http://www.kit-e.ru/assets/files/pdf/2012_02_108.pdf (дата обращения: 19.10.2025).
5. Кодирование состояний автоматов с целью минимизации аппаратурных затрат. URL: https://studfile.net/preview/6716912/page:37/ (дата обращения: 19.10.2025).
6. Прямой, обратный и дополнительный коды : отрицательные числа. URL: http://prog-cpp.ru/reverse-code/ (дата обращения: 19.10.2025).
7. Умножение чисел в прямом коде. URL: https://miras.edu.kz/assets/files/tsump-lektsiya-rus.pdf (дата обращения: 19.10.2025).
8. ЧЕТЫРЕ СПОСОБА УМНОЖЕНИЯ // Elibrary.ru. URL: https://www.elibrary.ru/item.asp?id=23565922 (дата обращения: 19.10.2025).
9. Прямой код. URL: https://studfile.net/preview/5312389/page:7/ (дата обращения: 19.10.2025).
10. Умножение чисел со старших разрядов в прямом коде — Bstudy. URL: https://bstudy.net/689083/tehnika/umnozhenie_chisel_starshih_razryadov_pryamom_kode (дата обращения: 19.10.2025).
11. Представление чисел в прямом коде. URL: https://studfile.net/preview/791888/page:5/ (дата обращения: 19.10.2025).
12. Представление целых чисел: прямой код, код со сдвигом, дополнительный код // HSE.ru. 2014. URL: https://cs.hse.ru/data/2014/09/22/1100257912/%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F%204.pdf (дата обращения: 19.10.2025).
13. Автоматы Мура и Мили — Викиконспекты. URL: https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D1%8B_%D0%9C%D1%83%D1%80%D0%B0_%D0%B8_%D0%9C%D0%B8%D0%BB%D0%B8 (дата обращения: 19.10.2025).
14. Умножение чисел с фиксированной запятой в прямом и дополнительном кодах — Интуит. URL: https://www.intuit.ru/studies/courses/2193/587/lecture/12478 (дата обращения: 19.10.2025).
15. Методические указания «Арифметические основы ЭВМ и систем». (Электронное учебное пособие) // Elibrary.ru. URL: https://www.elibrary.ru/item.asp?id=25573433 (дата обращения: 19.10.2025).
16. Отрицательные числа в памяти компьютера — дополнительный код • Информатика | Фоксфорд Учебник. URL: https://foxford.ru/wiki/informatika/dopolnitelnyy-kod (дата обращения: 19.10.2025).
17. Представление чисел в прямом, обратном и дополнительном кодах — JavaRush. URL: https://javarush.com/groups/posts/2608-predstavlenie-chisel-v-pryamom-obratnom-i-dopolniteljnom-kodakh (дата обращения: 19.10.2025).
18. Умножение, начиная со старших разрядов множителя при сдвиге вправо множимого и неподвижной сумме частичных произведений — Studbooks.net. URL: https://studbooks.net/1572421/informatika/umnozhenie_nachinaya_starshih_razryadov_mnozhitelya_sdvige_vpravo_mnozhimogo_nepodvizhnoy_summe_chastichnyh_proizvedeniy (дата обращения: 19.10.2025).
19. В чем разница между прямым и обратным кодом в представлении отрицательных чисел? — Вопросы к Поиску с Алисой (Яндекс Нейро). URL: https://yandex.ru/q/question/v_chem_raznitsa_mezhdu_priamym_i_obratnym_29774619/ (дата обращения: 19.10.2025).
20. Лекции по теории автоматов // Elibrary.ru. URL: https://www.elibrary.ru/download/elibrary_12891917_54752538.pdf (дата обращения: 19.10.2025).
21. Самостоятельное изучение схемотехники. Абстрактный автомат. Часть 2 — Habr. URL: https://habr.com/ru/articles/93273/ (дата обращения: 19.10.2025).
22. Алгоритм умножения двоичных чисел в прямых кодах в форме с фиксированной запятой — Теория цифровых автоматов — Ozlib.com. URL: https://ozlib.com/514960/teoriya_tsifrovyh_avtomatov/algoritm_umnozheniya_dvoichnyh_chisel_pryamyh_kodah_forme_fiksirovannoy_zapyatoy (дата обращения: 19.10.2025).
23. Умножение чисел со старших разрядов в прямом коде. URL: https://studfile.net/preview/3074558/page:146/ (дата обращения: 19.10.2025).
24. Кодирование состояний автомата, оптимальное по тестопригодности. — Разработка методов синтеза и логического проектирования модулей сигнатурного мониторинга — Studbooks.net. URL: https://studbooks.net/1301382/informatika/kodirovanie_sostoyaniy_avtomata_optimalnoe_testoprigodnosti (дата обращения: 19.10.2025).
25. Сумматор частичных произведений Регистр множимого. URL: https://studfile.net/preview/3074558/page:147/ (дата обращения: 19.10.2025).
26. Семинар 1. Проектирование управляющего устройства процессора. URL: https://studfile.net/preview/3342371/ (дата обращения: 19.10.2025).
27. Логические и арифметические основы и принципы работы ЭВМ. Лекция 8: Модифицированные коды — НОУ ИНТУИТ. URL: https://www.intuit.ru/studies/courses/2193/587/lecture/12479 (дата обращения: 19.10.2025).
28. Пример. Таблица переходов и выходов. URL: https://studfile.net/preview/7924376/page:5/ (дата обращения: 19.10.2025).
29. Структура операционного устройства. URL: https://studfile.net/preview/3074558/page:205/ (дата обращения: 19.10.2025).
30. Структурная схема операционного автомата — в энергетике. URL: https://www.v-energetike.ru/uploads/files/Energetika-00000000000-00000000000000000000.pdf (дата обращения: 19.10.2025).
31. Разработка структурной схемы сумматора-умножителя. URL: https://studfile.net/preview/3257697/ (дата обращения: 19.10.2025).
32. Каковы преимущества использования автомата Мура при проектировании цифровых устройств? — Вопросы к Поиску с Алисой (Яндекс Нейро). URL: https://yandex.ru/q/question/kakovy_preimushchestva_ispolzovaniia_avtomata_c08b4796/ (дата обращения: 19.10.2025).
33. Виды управляющих автоматов. Структуры автоматов Мили и Мура. URL: https://studfile.net/preview/3074558/page:213/ (дата обращения: 19.10.2025).
34. Исследование аппаратурных затрат в микропрограммном автомате с операционным автоматом переходов // КиберЛенинка. URL: https://cyberleninka.ru/article/n/issledovanie-apparaturnyh-zatrat-v-mikroprogrammno-avtomate-s-operatsionnym-avtomatom-perehodov (дата обращения: 19.10.2025).
35. Применение автомата Мили (Мура) для создания математических моделей ц // Elibrary.ru. URL: https://www.elibrary.ru/item.asp?id=25381862 (дата обращения: 19.10.2025).
36. Минимизация конечных автоматов — Kybernetika. URL: https://www.kybernetika.eu/attachments/article/118/kybernetika_09-1973-1_0001.pdf (дата обращения: 19.10.2025).