Двойной баловаться - Double dabble
В Информатика, то двойной баловаться алгоритм используется для преобразования двоичные числа в двоично-десятичный (BCD) обозначение.[1][2] Он также известен как сдвиг и добавление -3 алгоритм, и может быть реализован с использованием небольшого количества вентилей в компьютерном оборудовании, но за счет высокой задержка.[3]
Алгоритм
Алгоритм работает следующим образом:
Предположим, что исходное число, которое нужно преобразовать, хранится в регистр то есть п бит шириной. Зарезервируйте пустое место, достаточно широкое, чтобы вместить как исходное число, так и его представление в формате BCD; п + 4×потолок(п/3) бит будет достаточно. Для хранения каждой десятичной цифры требуется максимум 4 бита в двоичном формате.
Затем разделите рабочее пространство на цифры BCD (слева) и исходный регистр (справа). Например, если исходное число, которое нужно преобразовать, имеет ширину восемь бит, рабочее пространство будет разделено следующим образом:
100s Десятки Оригинал 0010 0100 0011 11110011
На диаграмме выше показано двоичное представление 24310 в исходном регистре и двоично-десятичное представление числа 243 слева.
Рабочее пространство инициализируется всеми нулями, а затем значение, которое нужно преобразовать, копируется в пространство «исходного регистра» справа.
0000 0000 0000 11110011
Затем алгоритм повторяет п раз. На каждой итерации любая цифра BCD, равная по крайней мере 5 (0101 в двоичном формате), увеличивается на 3 (0011); тогда все рабочее пространство сдвигается влево на один бит. Приращение гарантирует, что значение 5, увеличенное и сдвинутое влево, станет 16 (10000), таким образом, правильно «переносится» в следующую цифру BCD.
По сути, алгоритм работает путем удвоения значения BCD слева на каждой итерации и добавления единицы или нуля в соответствии с исходным битовым шаблоном. Сдвиг влево выполняет обе задачи одновременно. Если какая-либо цифра равна пяти или больше, добавляется три, чтобы гарантировать, что значение «переносится» в базе 10.
Алгоритм двойного прикосновения, выполненный на значении 24310, выглядит так:
0000 0000 0000 11110011 Инициализация0000 0000 0001 11100110 Shift0000 0000 0011 11001100 Shift0000 0000 0111 10011000 Shift0000 0000 1010 10011000 Добавьте 3 к ONES, так как это было 70000 0001 0101 00110000 Shift0000 0001 1000 00110000 Добавьте 3 к ONES, так как это было 50000 0011 0000 01100000 Shift0000 0110 0000 11000000 Shift0000 1001 0000 11000000 Добавьте 3 к ДЕСЯТКАМ, так как это было 60001 0010 0001 10000000 Shift0010 0100 0011 00000000 Shift 2 4 3 BCD
Теперь выполнено восемь смен, поэтому алгоритм завершается. Цифры BCD слева от пространства «исходного регистра» отображают кодировку BCD исходного значения 243.
Другой пример для алгоритма двойного прикосновения - значение 6524410.
104 103 102 101 100 Исходный двоичный код 0000 0000 0000 0000 1111111011011100 Инициализация0000 0000 0000 0000 0001 1111110110111000 Сдвиг влево (1-й) 0000 0000 0000 0000 0011 1111101101110000 Сдвиг влево (2-й) 0000 0000 0000 0000 0111 1111011011100000 Сдвиг влево (3-й) 0000 0000 0000 0000 1010 1111011011100000 Добавить от 3 до 100, так как это было 70000 0000 0000 0001 0101 1110110111000000 Сдвиг влево (4-й) 0000 0000 0000 0001 1000 1110110111000000 Добавьте 3 к 100, так как это было 50000 0000 0000 0011 0001 1101101110000000 Сдвиг влево (5-й) 0000 0000 0000 0110 0011 1011011100000000 Сдвиг влево (6-й) 0000 0000 0000 1001 0011 1011011100000000 Добавить от 3 до 101, так как это было 60000 0000 0001 0010 0111 0110111000000000 Сдвиг влево (7-й) 0000 0000 0001 0010 1010 0110111000000000 Добавьте 3 к 100, так как это было 70000 0000 0010 0101 0100 1101110000000000 Сдвиг влево (8-й) 0000 0000 0010 1000 0100 1101110000000000 Добавьте 3 к 101, так как это было 50000 0000 0101 0000 1001 1011100000000000 Сдвиг влево (девятый) 0000 0000 1000 0000 1001 1011100000000000 Добавьте 3 к 102, так как это было 50000 0000 1000 0000 1100 1011100000000000 Добавьте 3 к 100, так как это было 90000 0001 0000 0001 1001 0111000000000000 Сдвиг влево (10-й) 0000 0001 0000 0001 1100 0111000000000000 Добавьте 3 к 100, так как это было 90000 0010 0000 0011 1000 1110000000000000 Сдвиг влево (11-й) 0000 0010 0000 0011 1011 1110000000000000 Добавьте 3 к 100, поскольку это было 80000 0100 0000 0111 0111 1100000000000000 Сдвиг влево (12-й) 0000 0100 0000 1010 0111 1100000000000000 Добавьте 3 к 101, так как это было 70000 0100 0000 1010 1010 1100000000000000 Добавьте 3 к 100, так как это было 70000 1000 0001 0101 0101 1000000000000000 Сдвиг влево (13-й) 0000 1011 0001 0101 0101 1000000000000000 Добавьте 3 к 103, так как это было 80000 1011 0001 1000 0101 1000000000000000 Добавьте 3 к 101, поскольку это было 50000 1011 0001 1000 1000 1000000000000000 Добавьте 3 к 100, поскольку это было 50001 0110 0011 0001 0001 0000000000000000 Сдвиг влево (14-й) 0001 1001 0011 0001 0001 0000000000000000 Добавьте 3 к 103, так как это было 60011 0010 0110 0010 0010 0000000000000000 Сдвиг влево (15-й) 0011 0010 1001 0010 0010 0000000000000000 Добавьте 3 к 102, так как это было 60110 0101 0010 0100 0100 0000000000000000 Сдвиг влево (16-й) 6 5 2 4 4 BCD
Было выполнено шестнадцать смен, поэтому алгоритм завершается. Десятичное значение цифр BCD: 6 * 10.4 + 5*103 + 2*102 + 4*101 + 4*100 = 65244.
Параметрическая реализация Verilog двоичного преобразователя двоично-десятичного кода[4]
// параметрическая реализация Verilog преобразователя двоичного кода double dabble в BCD// полный проект см.// https://github.com/AmeerAbdelhadi/Binary-to-BCD-Converterмодуль bin2bcd #( параметр W = 18) // ширина ввода ( Вход [W-1 :0] мусорное ведро , // двоичный выход рег [W+(W-4)/3:0] bcd ); // bcd {..., тысячи, сотни, десятки, единицы} целое число я,j; всегда @(мусорное ведро) начинать за(я = 0; я <= W+(W-4)/3; я = я+1) bcd[я] = 0; // инициализируем нулями bcd[W-1:0] = мусорное ведро; // инициализируем входным вектором за(я = 0; я <= W-4; я = я+1) // итерация по глубине структуры за(j = 0; j <= я/3; j = j+1) // итерация по ширине структуры если (bcd[W-я+4*j -: 4] > 4) // если> 4 bcd[W-я+4*j -: 4] = bcd[W-я+4*j -: 4] + 4'd3; // добавляем 3 конецконечный модуль
Обратный двойной баловство
Алгоритм полностью обратимый. Применяя алгоритм обратного двойного приближения, число BCD можно преобразовать в двоичное. Изменение алгоритма выполняется путем изменения основных шагов алгоритма:
| Двойной баловаться (Двоичный в BCD) | Обратный двойной баловство (BCD в двоичную) |
|---|---|
| Для каждой группы ввода четыре бита: Если группа> = 5, добавьте 3 в группу Левый сдвиг на выходные цифры | Сдвиг вправо в выходной двоичный файл Для каждой группы из четырех входных битов: Если группа> = 8, вычтите 3 из группы |
Пример обратного двойного лабиринта
Алгоритм обратного двойного прикосновения, выполняемый для трех цифр BCD 2-4-3, выглядит следующим образом:
BCD Вход Двоичный Выход 2 4 3 0010 0100 0011 00000000 Инициализация 0001 0010 0001 10000000 Сдвиг вправо 0000 1001 0000 11000000 Сдвинуто вправо 0000 0110 0000 11000000 Вычтено 3 из 2-й группы, потому что это было 9 0000 0011 0000 01100000 Сдвинуто вправо 0000 0001 1000 00110000 Сдвинуто вправо 0000 0001 0101 00110000 Вычли 3 из 3-й группы, потому что это было 8 0000 0000 1010 10011000 Сдвинуто вправо 0000 0000 0111 10011000 Вычтено 3 из 3-й группы, потому что это было 10 0000 0000 0011 11001100 Сдвинуто вправо 0000 0000 0001 11100110 Сдвинуто вправо 0000 0000 0000 11110011 Сдвинуто вправо ===================== ===== 24310
C реализация
Алгоритм двойного прикосновения может выглядеть так, если реализован в C. Обратите внимание, что эта реализация предназначена для преобразования «входного регистра» любой ширины, принимая массив в качестве параметра и возвращая динамически распределяется нить. Также обратите внимание, что эта реализация не хранит явную копию входного регистра в своем рабочем пространстве, как это делалось в описании алгоритма; копирование входного регистра в рабочее пространство было просто педагогический устройство.
#включают <stdio.h>#включают <stdlib.h>#включают <string.h>/* Эта функция принимает массив из n целых чисел без знака, каждый содержит значение в диапазоне [0, 65535], представляющий число в диапазоне [0, 2 ** (16n) -1]. arr [0] - самая старшая «цифра». Эта функция возвращает новый массив, содержащий заданный число как строка десятичных цифр. Для краткости в этом примере предполагается, что calloc и realloc никогда не подведут.*/пустота double_dabble(int п, const беззнаковый int *обр, char **результат){ int nbit = 16*п; / * длина arr в битах * / int не поцарапать = нбит/3; / * длина царапины в байтах * / char *царапать = каллок(1 + не поцарапать, размер *царапать); int я, j, k; int smin = не поцарапать-2; / * оптимизация скорости * / за (я=0; я < п; ++я) { за (j=0; j < 16; ++j) { / * Этот бит будет сдвинут справа. * / int shift_in = (обр[я] & (1 << (15-j)))? 1: 0; / * Добавляем 3 везде, где царапина [k]> = 5. * / за (k=smin; k < не поцарапать; ++k) царапать[k] += (царапать[k] >= 5)? 3: 0; / * Сдвигаем скретч влево на одну позицию. * / если (царапать[smin] >= 8) smin -= 1; за (k=smin; k < не поцарапать-1; ++k) { царапать[k] <<= 1; царапать[k] &= 0xF; царапать[k] |= (царапать[k+1] >= 8); } / * Сдвиг в новый бит от arr. * / царапать[не поцарапать-1] <<= 1; царапать[не поцарапать-1] &= 0xF; царапать[не поцарапать-1] |= shift_in; } } / * Удаляем ведущие нули из рабочего места. * / за (k=0; k < не поцарапать-1; ++k) если (царапать[k] != 0) перемена; не поцарапать -= k; memmove(царапать, царапать+k, не поцарапать+1); / * Преобразуем рабочее пространство из цифр BCD в ASCII. * / за (k=0; k < не поцарапать; ++k) царапать[k] += '0'; / * Изменить размер и вернуть полученную строку. * / *результат = перераспределить(царапать, не поцарапать+1); возвращаться;}/* Этот тестовый драйвер должен печатать следующие десятичные значения: 246 16170604 1059756703745*/int главный(пустота){ беззнаковый int обр[] = { 246, 48748, 1 }; char *текст = НОЛЬ; int я; за (я=0; я < 3; ++я) { double_dabble(я+1, обр, &текст); printf("% s", текст); свободный(текст); } возвращаться 0;}Реализация VHDL
библиотека IEEE;использовать IEEE.STD_LOGIC_1164.ВСЕ;использовать IEEE.numeric_std.все;юридическое лицо bin2bcd_12bit является Порт ( binIN : в STD_LOGIC_VECTOR (11 вниз 0); те : из STD_LOGIC_VECTOR (3 вниз 0); десятки : из STD_LOGIC_VECTOR (3 вниз 0); сотни : из STD_LOGIC_VECTOR (3 вниз 0); тысячи : из STD_LOGIC_VECTOR (3 вниз 0) );конец bin2bcd_12bit;архитектура Поведенческий из bin2bcd_12bit являетсяначинатьbcd1: процесс(binIN) - временная переменная Переменная темп : STD_LOGIC_VECTOR (11 вниз 0); - переменная для хранения выходного числа BCD - организованы следующим образом - тысячи = bcd (от 15 до 12) - сотни = bcd (от 11 до 8) - десятки = bcd (от 7 до 4) - единицы = bcd (от 3 до 0) Переменная bcd : НЕ ПОДПИСАНО (15 вниз 0) := (другие => '0'); -- к - https://en.wikipedia.org/wiki/Double_dabble начинать - обнулить переменную bcd bcd := (другие => '0'); - прочитать ввод во временную переменную темп(11 вниз 0) := binIN; - цикл 12 раз, так как у нас есть 12 входных бит - это можно было бы оптимизировать, нам не нужно проверять и добавлять 3 для - первые 3 итерации, так как число никогда не может быть> 4 за я в 0 к 11 петля если bcd(3 вниз 0) > 4 тогда bcd(3 вниз 0) := bcd(3 вниз 0) + 3; конец если; если bcd(7 вниз 4) > 4 тогда bcd(7 вниз 4) := bcd(7 вниз 4) + 3; конец если; если bcd(11 вниз 8) > 4 тогда bcd(11 вниз 8) := bcd(11 вниз 8) + 3; конец если; - тысячи не могут быть> 4 для 12-битного входного числа - так что не нужно ничего делать с верхними 4 битами bcd - сдвинуть bcd влево на 1 бит, скопировать MSB temp в LSB bcd bcd := bcd(14 вниз 0) & темп(11); - сдвиг температуры влево на 1 бит темп := темп(10 вниз 0) & '0'; конец петля; - установить выходы те <= STD_LOGIC_VECTOR(bcd(3 вниз 0)); десятки <= STD_LOGIC_VECTOR(bcd(7 вниз 4)); сотни <= STD_LOGIC_VECTOR(bcd(11 вниз 8)); тысячи <= STD_LOGIC_VECTOR(bcd(15 вниз 12)); конец процесс bcd1; конец Поведенческий;Испытательный стенд VHDL
БИБЛИОТЕКА ieee;ИСПОЛЬЗОВАТЬ ieee.std_logic_1164.ВСЕ; ЮРИДИЧЕСКОЕ ЛИЦО bin2bcd_12bit_test_file ЯВЛЯЕТСЯКОНЕЦ bin2bcd_12bit_test_file; АРХИТЕКТУРА поведение ИЗ bin2bcd_12bit_test_file ЯВЛЯЕТСЯ - Декларация компонентов для тестируемого устройства (UUT) КОМПОНЕНТ bin2bcd_12bit ПОРТ( binIN : В std_logic_vector(11 вниз 0); те : ИЗ std_logic_vector(3 вниз 0); десятки : ИЗ std_logic_vector(3 вниз 0); сотни : ИЗ std_logic_vector(3 вниз 0); тысячи : ИЗ std_logic_vector(3 вниз 0) ); КОНЕЦ КОМПОНЕНТ; - ВНИМАНИЕ: обратите внимание, что в тестовом стенде нет необходимости в тактовом сигнале, так как конструкция строго - комбинационный (или параллельный, в отличие от реализации C, которая является последовательной). - Эти часы предназначены только для моделирования; вы можете опустить все ссылки на часы и процесс и использовать "wait for ... ns" - заявления вместо этого. - Входы сигнал binIN : std_logic_vector(11 вниз 0) := (другие => '0'); сигнал clk : std_logic := '0'; - можно не указывать - Выходы сигнал те : std_logic_vector(3 вниз 0); сигнал десятые : std_logic_vector(3 вниз 0); сигнал Hunderths : std_logic_vector(3 вниз 0); сигнал тысячи : std_logic_vector(3 вниз 0); - Определения периода времени постоянный clk_period : время := 10 нс; - можно не указывать -- Разное сигнал full_number : std_logic_vector(15 вниз 0);НАЧИНАТЬ - Создание экземпляра тестируемого устройства (UUT) уут: bin2bcd_12bit ПОРТ КАРТА ( binIN => binIN, те => те, десятки => десятые, сотни => Hunderths, тысячи => тысячи ); - Определения часового процесса - весь процесс можно опустить clk_process :процесс начинать clk <= '0'; ждать за clk_period/2; clk <= '1'; ждать за clk_period/2; конец процесс; - Объедините сигналы для полного числа full_number <= тысячи & Hunderths & десятые & те; - Стимулирующий процесс стим_проц: процесс начинать - удерживать состояние сброса 100 нс. ждать за 100 нс; ждать за clk_period*10; - вставить сюда стимул - должен вернуть 4095 binIN <= X "FFF"; ждать за clk_period*10; утверждать full_number = x "4095" строгость ошибка; - используйте "ждать ... нс;" - должен вернуть 0 binIN <= X "000"; ждать за clk_period*10; утверждать full_number = х "0000" строгость ошибка; - должно вернуть 2748 binIN <= X "ABC"; ждать за clk_period*10; утверждать full_number = x "2748" строгость ошибка; ждать; конец процесс;КОНЕЦ;Оптимизированный сниппет Bin2BCD для SBA (VHDL)
- / SBA: Сведения о программе - ========================================= ========== -- Фрагмент: 16-битный преобразователь двоичного в BCD- Автор: Мигель А. Риско-Кастильо.- Описание: преобразователь 16 бит в BCD с использованием алгоритма "Double Dabble".- Перед вызовом необходимо заполнить "bin_in" соответствующим значением, после вызова,- сниппет помещает в переменную "bcd_out" результат преобразования BCD.- Поместите фрагмент в раздел подпрограмм пользовательской программы.- / SBA: Сведения о завершении программы ------------------------------------------ ---------- / SBA: Пользовательские регистры и константы - ====================================== - - Переменная bin_in : беззнаковый(15 вниз 0); - 16-битный входной регистр Переменная bcd_out : беззнаковый(19 вниз 0); - выходной регистр 20 бит- / SBA: Регистры и константы конечного пользователя --------------------------------------- / SBA: Программа пользователя - ========================================= ============= -- / L: Bin2BCD=> bcd_out := (другие=>'0'); если bin_in=0 тогда SBARet; конец если; - если ноль, вернуть=> bcd_out(2 вниз 0) := bin_in(15 вниз 13); - зз 3 bin_in := bin_in(12 вниз 0) & "000";=> за j в 0 к 12 петля за я в 0 к 3 петля - для полубайта от 0 до 3 последний полубайт настраивать не нужно если bcd_out(3+4*я вниз 4*я)>4 тогда - Клев> 4? bcd_out(3+4*я вниз 4*я):=bcd_out(3+4*я вниз 4*я)+3; - добавить 3 к полубайту конец если; конец петля; bcd_out := bcd_out(18 вниз 0) & bin_in(15); --shl bin_in := bin_in(14 вниз 0) & '0'; конец петля; SBARet; - вернуться в основную программу- / SBA: Программа для конечного пользователя ------------------------------------------ ------------Исторический
В 1960-е годы термин двойной баловаться также использовался для другого мысленного алгоритма, используемого программистами для преобразования двоичного числа в десятичное. Это выполняется путем чтения двоичного числа слева направо, удвоения, если следующий бит равен нулю, и удвоения и добавления единицы, если следующий бит равен единице.[7] В приведенном выше примере, 11110011, мыслительный процесс был бы следующим: «один, три, семь, пятнадцать, тридцать, шестьдесят, сто двадцать один, двести сорок три», то же самое, что получено выше.
Смотрите также
- Справочная таблица - альтернативный подход к конвертации
Рекомендации
- ^ Гао, Шули; Аль-Халили, Д .; Чабини, Н. (июнь 2012 г.), «Улучшенный сумматор BCD с использованием 6-LUT FPGA», 10-я Международная конференция по новым схемам и системам IEEE (NEWCAS 2012), стр. 13–16, Дои:10.1109 / NEWCAS.2012.6328944
- ^ "Преобразователь двоичного в двоично-десятичный:" Двойной алгоритм преобразования двоичного в двоично-десятичный формат"" (PDF). Архивировано из оригинал (PDF) 31 января 2012 г.
- ^ Вестиас, Марио П .; Нето, Горацио К. (март 2010 г.), «Параллельные десятичные умножители с использованием двоичных умножителей», VI Южная конференция по программируемой логике (SPL 2010), стр. 73–78, Дои:10.1109 / SPL.2010.5483001
- ^ Абдельхади, Амир (07.07.2019), AmeerAbdelhadi / Преобразователь двоичного кода в BCD, получено 2020-03-03
- ^ Абдельхади, Амир (07.07.2019), AmeerAbdelhadi / Преобразователь двоичного кода в BCD, получено 2020-03-03
- ^ «SBA». sba.accesus.com. Получено 2016-12-31.
Архитектура простого автобуса
- ^ Godse, Deepali A .; Годсе, Атул П. (2008). Цифровые методы. Пуна, Индия: Технические публикации. п. 4. ISBN 978-8-18431401-4.
дальнейшее чтение
- Фальконер, Чарльз "Чак" Б. (2004-04-16). "Объяснение алгоритма преобразования Double-Dabble Bin-BCD". Архивировано из оригинал на 25 марта 2009 г.