Введение в каноническое обозначенное цифровое представление
CSD - элегантный способ более эффективного использования цифровых мультипликаторов. В этой статье рассматриваются основы CSD и ее реализация.
Как правило, алгоритмы цифровой обработки сигналов требуют большого количества умножений. В качестве простого примера рассмотрим FIR-фильтр с 32 кранами. Используя симметрию в коэффициентах фильтра, нам нужно 16 умножений для создания одного образца выходного сигнала фильтра. В зависимости от количества бит, используемых для представления входных выборок и коэффициентов фильтра, эти умножения могут легко стать трудоемким процессом.
Дизайн аппаратно-эффективных мультипликаторов привлек большое внимание на протяжении десятилетий, и обширные исследования привели к ряду решений. В этой статье рассматриваются основные понятия представления канонической символьной цифры (CSD). CSD представляет собой интересное решение для реализации эффективных множителей, особенно при умножении входного сигнала на постоянную мультипликацию, например. При внедрении КИХ-фильтра, где мы сталкиваемся с некоторыми фиксированными коэффициентами.
Основная идея CSD
Предположим, что мы хотим умножить $$ x $$ на двоичное число $$ y = 1 1 110 $$. Самый простой способ сделать это будет основан на следующем уравнении:
$$ z = 2 ^ {4} x + 2 ^ {3} x + 2 ^ {2} x + 2 ^ {1} x $$
Умножение (и деление) на два может быть достигнуто с помощью операций побитового сдвига. Следовательно, приведенное выше уравнение означает, что нам нужно добавить сдвинутые версии $$ x $$. Количество операций сдвига и сложения зависит от количества ненулевых цифр мультипликатора. В этом примере есть четыре 1s, поэтому для умножения требуются четыре смены и три дополнения. Если бы мы могли представлять $$ y $$ с меньшим количеством ненулевых цифр, мы могли бы уменьшить сложность умножения. В этом конкретном примере на самом деле можно более эффективно представлять $$ y $$, потому что $$ y = 30 = 2 ^ {5} -2 ^ {1} $$. С этим представлением, называемым CSD, вышеупомянутое умножение требует двух сдвигов и только одного вычитания. CSD - это представление, в котором число ненулевых цифр становится минимальным. Для этого CSD использует систему тернарных чисел, которая использует новую цифру $$ -1 $$, обозначенную $$ \ бар {1} $$. Например, CSD-представление $$ 30 $$ равно $$ 1000 \ bar {1} 0 $$. Хотя представление в уравнении выше полагается на Суммирование степеней двух, CSD использует как дополнения, так и d-вычитания.
Это обеспечивает большую гибкость при реализации арифметических функций; однако мы столкнемся с двумя проблемами: во-первых, мы должны представлять каждое число с набором цифр $$ {-1, 0, 1 } $$ вместо двоичного представления, которое имеет набор цифр $$ {0, 1 } $$. Это означает, что для хранения одной цифры номера CSD требуются два бита. Во-вторых, поскольку мы обычно используем двоичное представление, Мы должны добавить некоторую схему, которая преобразует двоичное число в CSD перед выполнением умножения.
Как видно из рассмотренного примера, CSD особенно полезен при работе с числами, которые содержат строку из 1s. В этих случаях CSD заменяет несколько операций сдвига и добавления, возникающих из строки 1 с двумя сменами и одной вычитательной операцией.
Важные свойства представления CSD
В номере CSD две условные цифры не могут быть отличными от нуля, т. Е. $$ 1 \ bar {1} $$ и $$ \ bar {1} 1 $ $ Не разрешены. Поэтому максимальное число ненулевых цифр для $$ N $$ - битового CSD-номера будет $$ \ lfloor { frac {N} {2}} rfloor $$. Даже с $$ N $$ наибольшее число, которое может быть представлено $$ N $$-бит CSD, $$ 2 ^ {N-1} + 2 ^ {N-3} + \ dots + 2 ^ {1} approx \ frac {2 ^ {N + 1}} {3} $ $
Следовательно, хотя четырехбитное двоичное число может представлять десятичное $$ 15 $$, наибольшее значение, представляемое четырехбитовым CSD-номером, составляет $$ 10 $$.
Для числа $$ N $$-бит CSD, $$ C = \ sum_ {i = 0} ^ {N-1} c_ {i} 2 ^ {i} $$, вероятность $$ c_ { i} $$, отличное от нуля, задается формулой
$$ P (| c_ {i} | = 1) = \ frac {1} {3} + \ frac {1} {9N} left (1- \ left (- \ frac {1} {2} right) ^ N \ справа) $$
При относительно большой $$ N $$ приведенная выше вероятность становится примерно равной $$ \ frac {1} {3} $$. Однако для двоичного $$ N $$ - битового числа вероятность того, что один конкретный бит отличен от нуля, равна $$ \ frac {1} {2} $$. Это означает, что CSD уменьшает количество ненулевых цифр и приводит к более эффективной реализации умножения.
В то время как двоичное представление использует концепцию дополнения 2 к коду отрицательными числами, нам нужно только инвертировать знак цифр в номере CSD для представления отрицательных чисел. Это возможно, потому что набор цифр CSD включает $$ - 1 $$. Например, $$ - 30 $$ представлен $$ \ bar {1} 00010 $$.
Алгоритм преобразования из двоичного кода в CSD
Существует несколько алгоритмов преобразования двоичного числа в CSD. Простой подход, подходящий для преобразования бумажных и карандашей из двоичного представления без знака в CSD, - это поиск номера от LSB до MSB, поиск строки из 1 с, за которой следует 0, Например $$ 0111 $$, и замените их представлением CSD, т. Е. $$ 100 \ bar {1} $$. Возможно, нам придется повторять этот процесс несколько раз, потому что могут быть другие строки из них, или новые строки из них могут быть созданы в результате предыдущей итерации. Давайте рассмотрим некоторые примеры, чтобы прояснить этот процесс:
Пример 1: Найдите эквивалент CSD $$ 01011101 $$.
На первой итерации поиска с LSB на MSB мы находим строку $$ 0111 $$, которая может быть представлена $$ 100 \ bar {1} $$. После замены этой строки на ее CSD-представление у нас есть $$ 01100 \ bar {1} 01 $$. Теперь мы снова ищем полученный номер от LSB до MSB, чтобы узнать, есть ли какая-либо другая строка из них. Мы видим, что из-за первой итерации процесса создается новая строка: $$ 011 $$. Это может быть заменено на $$ 10 \ bar {1} $$. Тогда эквивалент CSD $$ 01011101 $$ будет $$ 10 \ bar {1} 00 \ bar {1} 01 $$.
Пример 2. Найдите CSD-представление $$ 1010111 $$.
В первой итерации мы найдем $$ 0111 $$ и заменим ее $$ 100 \ bar {1} $$, и получим $$ 101100 \ bar {1} $$. На второй итерации мы найдем $$ 011 $$ и заменим ее $$ 10 \ bar {1} $$. Следовательно, мы имеем $$ 110 \ bar {1} 00 \ bar {1} $$. Теперь есть еще одна строка $$ 11 $$. Чтобы найти эквивалент CSD этой итерации, нам нужно добавить $$ 0 $$ в крайнее левое положение $$ 110 \ bar {1} 00 \ bar {1} $$. Очевидно, это не изменит значение этого числа, но это позволит нам заменить $$ 011 $$ $$ 10 \ bar {1} $$. Наконец, мы получаем CSD-представление как $$ 10 \ bar {1} 0 \ bar {1} 00 \ bar {1} $$.
Блок-схема формального алгоритма, подходящая для аппаратной реализации, проиллюстрирована на следующем рисунке. Алгоритм преобразуется из дополнения 2 к CSD. На рисунке 1, $$ x_ {i} $$ и $$ c_ {i} $$ обозначают входное двоичное число и конечное число CSD, соответственно. Алгоритм должен определить вспомогательный сигнал «переносить» и реплицировать MSB двоичного числа $$ n $$ бит, $$ x_ {n-1} $$, В битовой позиции $$ x_ {n} $$.
Рисунок 1. Алгоритм преобразования двоичного числа в CSD. Изображение предоставлено IEEE Explore
Как выполнять умножение с CSD "" src = "// www.allaboutcircuits.com/uploads/articles/Fig2m5292017.png" />
Рисунок 2. Возможная реализация для умножения на $$ 1000 \ bar {1} 00 \ bar {1} 0 \ bar {1} 010 \ bar {1} 0 \ bar {1} $$
Хотя умножение на постоянный номер CSD является простым, умножение на переменную мультипликацию требует некоторой дополнительной схемы для преобразования бинарного числа в представление CSD, Мы можем использовать метод на основе таблицы поиска или непосредственно реализовать алгоритм, показанный на рисунке 1.
В качестве последней заметки помните, что иногда мы можем еще больше упростить умножение CSD. Например, при разработке FIR-фильтра можно ввести небольшую ошибку в отклике амплитуды фильтра и добиться гораздо более эффективной системы. Некоторые другие конструкции полагаются на идею о том, что с разными коэффициентами масштабирования число ненулевых цифр CSD-представления фильтра FIR изменяется. Используя это свойство, можно найти лучшую импликацию, исследуя различные коэффициенты масштабирования. Это более интересно, чем предыдущее решение, потому что здесь мы не торгуем эффективностью для точности.
Если вы хотите узнать больше о CSD, вы можете найти полезную информацию в ссылках, приведенных в этой статье.