Бочкообразный сдвигатель и каскады MUX

Предварительные знания: MUX^{iМультиплексор — комбинационная схема, соединяющая один из нескольких входов с выходом по сигналу выбора. Соответствие битов выбора и номеров входов должно быть задано явно. Подробнее}, логические и арифметические сдвиги, задержка распространения^{iЗадержка распространения — время от изменения входа до установления правильного выхода. Логическая эквивалентность выражений и их временные характеристики — разные вопросы. Подробнее} комбинационных схем.

Переменный сдвиг как выбор фиксированных соединений

Сдвиговому регистру^{iРегистр хранит многобитное состояние. Синхронные регистры в этом курсе записывают определённый вход на фронте тактового сигнала. Подробнее}, перемещающему по одному биту, требуется столько тактов, сколько сдвигов. Barrel shifter получает величину сдвига и формирует результат за один комбинационный путь. Биты не перемещаются несколько раз во времени: выбирается путь соединения нужного входного бита с выходом.

Для 16-битного значения и сдвига 0–15 величина $s=s_0+2s_1+4s_2+8s_3$. Поэтому последовательно ставят четыре ступени на 1, 2, 4, 8 позиций. Каждая MUX-ступень выбирает прямой проход либо фиксированный сдвиг.

Например, 11 — двоичное 1011: выбираются 1, 2, 8, ступень 4 пропускается. Логический правый сдвиг $X=0xD2A5$ последовательно даёт 0x6952, 0x1A54, 0x1A54, 0x001A. Это значения четырёх комбинационных ступеней, а не четырёх тактов.

Четыре группы по 16 MUX дают 64 однобитные точки выбора 2:1 до оптимизации соединений и констант. В общем случае $W=2^K$ структура выбора пропорциональна $W\log_2W$, глубина — $\log_2W$. Даже отдельные W:1 MUX для каждого выхода могут стать деревом после синтеза; число строк RTL не определяет площадь или частоту.

Вход 0xD2A5 сдвигается логически вправо на 11. Показаны четыре комбинационные ступени, управляемые битами 1011, а не выполнение за четыре такта.

Левый сдвиг через правую структуру

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

Арифметический правый сдвиг заполняет старшие свободные позиции знаковым битом исходного входа. Левый сдвиг заполняет нулями даже в арифметическом режиме. Для дополнительного кода^{iДополнительный код представляет знаковые целые битовой последовательностью фиксированной ширины. Для n бит диапазон составляет от −2^(n−1) до 2^(n−1)−1. Подробнее} арифметический и логический левый сдвиги одинаковы по битам и не проверяют signed overflow автоматически.

Диапазон величины сдвига — часть контракта. Пример принимает 0–31 через 5-битный shamt. При ≥16 логический и левый сдвиги дают 0, арифметический правый — 16 копий знака. Только четыре младших бита ошибочно превратили бы сдвиг на 16 в сдвиг на 0, поэтому нужна отдельная обработка.

module barrel16 (
  input  wire [15:0] x,
  input  wire [4:0] shamt,
  input  wire left,
  input  wire arithmetic,
  output wire [15:0] y
);
  wire fill;
  wire [15:0] stage [0:4];
  assign fill = (!left) && arithmetic && x[15];

  for (genvar i = 0; i < 16; i++) begin : direction
    assign stage[0][i] = left ? x[15-i] : x[i];
    assign y[i] = shamt[4] ? fill :
                  (left ? stage[4][15-i] : stage[4][i]);
  end

  for (genvar k = 0; k < 4; k++) begin : shift_stage
    localparam int D = 1 << k;
    assign stage[k+1] = shamt[k]
      ? {{D{fill}}, stage[k][15:D]}
      : stage[k];
  end
endmodule

K в generate — константа построения схемы, а не четыре исполнения цикла во время работы. Длины part-select и повторений фиксированы, поэтому получается четыре фиксированных соединения с MUX. Fill не меняется между ступенями, сохраняя один знак при нескольких выбранных сдвигах.

RTL явно задаёт знаковое заполнение и потому реализует арифметический сдвиг даже unsigned^{iБеззнаковая интерпретация (unsigned) рассматривает битовую последовательность как неотрицательное целое. Диапазон n бит — от 0 до 2^n−1; знаковая интерпретация тех же битов может дать другое число. Подробнее}-вектором. Краткая запись оператором требует signed-операнда и >>>. Одного знака >>> или signed у исходной переменной перед part-select недостаточно. Конкатенация и частичные выборки могут терять signed-интерпретацию: сначала преобразуйте к signed нужной ширины. Поддерживаемые синтезом операторы описаны в документации AMD по выражениям Verilog.

Разделяйте задержку и потерю информации

К четырём комбинационным ступеням добавляются выбор направления и диапазона, а также проводники. При нехватке времени можно вставить регистры, но оставшиеся величину сдвига и управление направлением нужно задержать вместе с данными на те же такты. Тогда меняется latency^{iЗадержка (latency) — время или число циклов от приёма входа до появления соответствующего выхода. Она отличается от пропускной способности — объёма обработки за единицу времени. Подробнее}, и интерфейс уже не равнозначен чисто комбинационному модулю.

Сдвиг не восстанавливает отброшенные данные. При unsigned-сдвиге влево хотя бы одна вытолкнутая старшая 1 означает выход за диапазон. Signed-переполнение требует учёта исходного знака и отброшенных битов. Модуль таких флагов не выдаёт. Арифметический правый сдвиг отрицательного числа округляет деление на $2^s$ вниз: $-3$ на одну позицию даёт $-2$, а не $-1$ целочисленного деления к нулю.