Двойной баловство
В информатике алгоритм двойного прикосновения используется для преобразования двоичных чисел в двоично-десятичное представление (BCD). [1] [2] Он также известен как алгоритм сдвига и сложения -3 и может быть реализован с использованием небольшого количества вентилей в компьютерном оборудовании, но за счет высокой задержки . [3]
Алгоритм
[ редактировать ]Алгоритм работает следующим образом:
Предположим, что исходное число, подлежащее преобразованию, хранится в регистре шириной n бит. Зарезервируйте свободное пространство, достаточно широкое, чтобы вместить как исходное число, так и его представление в формате BCD; n + 4× ячеек ( n /3) бит будет достаточно. Для хранения каждой десятичной цифры требуется максимум 4 бита в двоичном формате.
Затем разделите рабочее пространство на цифры BCD (слева) и исходный регистр (справа). Например, если исходное преобразуемое число имеет ширину восемь бит, рабочее пространство будет разделено следующим образом:
Hundreds Tens Ones Original 0010 0100 0011 11110011
На диаграмме выше показано двоичное представление числа 243 10 в исходном регистре и представление числа 243 в двоично-десятичном формате слева.
Рабочее пространство инициализируется всеми нулями, а затем преобразуемое значение копируется в пространство «исходного регистра» справа.
0000 0000 0000 11110011
Затем алгоритм повторяется n раз. На каждой итерации любая цифра BCD, равная не менее 5 (0101 в двоичном формате), увеличивается на 3 (0011); тогда все рабочее пространство сдвигается на один бит влево. Приращение гарантирует, что значение 5, увеличенное и сдвинутое влево, станет 16 (10 000), таким образом правильно «перенося» в следующую цифру BCD.
По сути, алгоритм работает, удваивая значение BCD слева на каждой итерации и добавляя либо единицу, либо ноль в соответствии с исходным битовым шаблоном. Сдвиг влево позволяет выполнить обе задачи одновременно. Если какая-либо цифра равна пяти или больше, к ней добавляется три, чтобы гарантировать, что значение «переносится» в базу 10.
Алгоритм двойного пропускания, выполняемый со значением 243 10 , выглядит следующим образом:
0000 0000 0000 11110011 Initialization
0000 0000 0001 11100110 Shift
0000 0000 0011 11001100 Shift
0000 0000 0111 10011000 Shift
0000 0000 1010 10011000 Add 3 to ONES, since it was 7
0000 0001 0101 00110000 Shift
0000 0001 1000 00110000 Add 3 to ONES, since it was 5
0000 0011 0000 01100000 Shift
0000 0110 0000 11000000 Shift
0000 1001 0000 11000000 Add 3 to TENS, since it was 6
0001 0010 0001 10000000 Shift
0010 0100 0011 00000000 Shift
2 4 3
BCD
Теперь выполнено восемь смен, поэтому алгоритм завершает работу. Цифры BCD слева от пространства «исходного регистра» отображают BCD-кодировку исходного значения 243.
Еще один пример алгоритма двойного даббла — значение 65244 10 .
104 103 102 101 100 Original binary
0000 0000 0000 0000 0000 1111111011011100 Initialization
0000 0000 0000 0000 0001 1111110110111000 Shift left (1st)
0000 0000 0000 0000 0011 1111101101110000 Shift left (2nd)
0000 0000 0000 0000 0111 1111011011100000 Shift left (3rd)
0000 0000 0000 0000 1010 1111011011100000 Add 3 to 100, since it was 7
0000 0000 0000 0001 0101 1110110111000000 Shift left (4th)
0000 0000 0000 0001 1000 1110110111000000 Add 3 to 100, since it was 5
0000 0000 0000 0011 0001 1101101110000000 Shift left (5th)
0000 0000 0000 0110 0011 1011011100000000 Shift left (6th)
0000 0000 0000 1001 0011 1011011100000000 Add 3 to 101, since it was 6
0000 0000 0001 0010 0111 0110111000000000 Shift left (7th)
0000 0000 0001 0010 1010 0110111000000000 Add 3 to 100, since it was 7
0000 0000 0010 0101 0100 1101110000000000 Shift left (8th)
0000 0000 0010 1000 0100 1101110000000000 Add 3 to 101, since it was 5
0000 0000 0101 0000 1001 1011100000000000 Shift left (9th)
0000 0000 1000 0000 1001 1011100000000000 Add 3 to 102, since it was 5
0000 0000 1000 0000 1100 1011100000000000 Add 3 to 100, since it was 9
0000 0001 0000 0001 1001 0111000000000000 Shift left (10th)
0000 0001 0000 0001 1100 0111000000000000 Add 3 to 100, since it was 9
0000 0010 0000 0011 1000 1110000000000000 Shift left (11th)
0000 0010 0000 0011 1011 1110000000000000 Add 3 to 100, since it was 8
0000 0100 0000 0111 0111 1100000000000000 Shift left (12th)
0000 0100 0000 1010 0111 1100000000000000 Add 3 to 101, since it was 7
0000 0100 0000 1010 1010 1100000000000000 Add 3 to 100, since it was 7
0000 1000 0001 0101 0101 1000000000000000 Shift left (13th)
0000 1011 0001 0101 0101 1000000000000000 Add 3 to 103, since it was 8
0000 1011 0001 1000 0101 1000000000000000 Add 3 to 101, since it was 5
0000 1011 0001 1000 1000 1000000000000000 Add 3 to 100, since it was 5
0001 0110 0011 0001 0001 0000000000000000 Shift left (14th)
0001 1001 0011 0001 0001 0000000000000000 Add 3 to 103, since it was 6
0011 0010 0110 0010 0010 0000000000000000 Shift left (15th)
0011 0010 1001 0010 0010 0000000000000000 Add 3 to 102, since it was 6
0110 0101 0010 0100 0100 0000000000000000 Shift left (16th)
6 5 2 4 4
BCD
Было выполнено шестнадцать смен, поэтому алгоритм завершает работу. Десятичное значение цифр BCD: 6*10. 4 + 5*10 3 + 2*10 2 + 4*10 1 + 4*10 0 = 65244.
Параметрическая реализация Verilog
[ редактировать ]// parametric Verilog implementation of the double dabble binary to BCD converter
// for the complete project, see
// https://github.com/AmeerAbdelhadi/Binary-to-BCD-Converter
module bin2bcd
#( parameter W = 18) // input width
( input [W-1 :0] bin , // binary
output reg [W+(W-4)/3:0] bcd ); // bcd {...,thousands,hundreds,tens,ones}
integer i,j;
always @(bin) begin
for(i = 0; i <= W+(W-4)/3; i = i+1) bcd[i] = 0; // initialize with zeros
bcd[W-1:0] = bin; // initialize with input vector
for(i = 0; i <= W-4; i = i+1) // iterate on structure depth
for(j = 0; j <= i/3; j = j+1) // iterate on structure width
if (bcd[W-i+4*j -: 4] > 4) // if > 4
bcd[W-i+4*j -: 4] = bcd[W-i+4*j -: 4] + 4'd3; // add 3
end
endmodule
Обратный двойной баловство
[ редактировать ]Алгоритм полностью обратим. Применяя обратный алгоритм двойного пропускания, число BCD можно преобразовать в двоичное. Обращение алгоритма осуществляется путем изменения основных шагов алгоритма:
| Двойной баловство (Двоичный код в BCD) |
Обратный двойной баловство (BCD в двоичный код) |
|---|---|
| Для каждой группы входов четыре бита: Если группа >= 5, добавьте 3 в группу. Сдвиг влево в выходные цифры |
Сдвиг вправо в выходной двоичный файл Для каждой группы из четырех входных битов: Если группа >= 8, вычтите 3 из группы. |
Пример обратного двойного даббла
[ редактировать ]Алгоритм обратного двойного даблинга, выполняемый с тремя цифрами BCD 2-4-3, выглядит следующим образом:
BCD Input Binary
Output
2 4 3
0010 0100 0011 00000000 Initialization
0001 0010 0001 10000000 Shifted right
0000 1001 0000 11000000 Shifted right
0000 0110 0000 11000000 Subtracted 3 from 2nd group, because it was 9
0000 0011 0000 01100000 Shifted right
0000 0001 1000 00110000 Shifted right
0000 0001 0101 00110000 Subtracted 3 from 3rd group, because it was 8
0000 0000 1010 10011000 Shifted right
0000 0000 0111 10011000 Subtracted 3 from 3rd group, because it was 10
0000 0000 0011 11001100 Shifted right
0000 0000 0001 11100110 Shifted right
0000 0000 0000 11110011 Shifted right
==========================
24310
Исторический
[ редактировать ]В 1960-х годах термин «двойной баловство» также использовался для обозначения другого мысленного алгоритма, используемого программистами для преобразования двоичных чисел в десятичные. Это выполняется путем чтения двоичного числа слева направо, удвоения, если следующий бит равен нулю, и удвоения и прибавления единицы, если следующий бит равен единице. [5] В приведенном выше примере 11110011 мыслительный процесс будет таким: «один, три, семь, пятнадцать, тридцать, шестьдесят, сто двадцать один, двести сорок три», тот же результат, что и полученный выше.
См. также
[ редактировать ]- Таблица поиска – альтернативный подход к выполнению преобразования.
Ссылки
[ редактировать ]- ^ Гао, Шули; Аль-Халили, Д.; Чабини, Н. (июнь 2012 г.), «Улучшенный сумматор BCD с использованием 6-LUT FPGA», 10-я Международная конференция по новым схемам и системам IEEE (NEWCAS 2012) , стр. 13–16, doi : 10.1109/NEWCAS.2012.6328944 , ISBN 978-1-4673-0859-5 , S2CID 36909518
- ^ «Преобразователь двоичных чисел в BCD: «Алгоритм двойного преобразования двоичных чисел в BCD» » (PDF) . Архивировано из оригинала (PDF) 31 января 2012 г.
- ^ Вестиас, Марио П.; Нето, Горацио К. (март 2010 г.), «Параллельные десятичные множители с использованием двоичных множителей», VI Южная конференция по программируемой логике (SPL 2010) , стр. 73–78, doi : 10.1109/SPL.2010.5483001 , ISBN 978-1-4244-6309-1 , S2CID 28360570
- ^ Перейти обратно: а б Абдельхади, Амир (07 июля 2019 г.), AmeerAbdelhadi/Binary-to-BCD-Converter , получено 3 марта 2020 г.
- ^ Годзе, Дипали А.; Годзе, Атул П. (2008). Цифровые техники . Пуна, Индия: Технические публикации. п. 4. ISBN 978-8-18431401-4 .
Дальнейшее чтение
[ редактировать ]- Фалконер, Чарльз «Чак» Б. (16 апреля 2004 г.). «Объяснение алгоритма преобразования Double-Dabble Bin-BCD» . Архивировано из оригинала 25 марта 2009 г.