Двойной баловаться - 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  конецконечный модуль
Параметрическая реализация Verilog преобразования двоичного кода double dabble в BCD, 18-разрядный пример.
Параметрическая реализация Verilog преобразователя двоично-десятичного кода в двоично-десятичный код, пример 18-разрядного кода.[5]


Обратный двойной баловство

Алгоритм полностью обратимый. Применяя алгоритм обратного двойного приближения, число 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)

[6]

- / 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, мыслительный процесс был бы следующим: «один, три, семь, пятнадцать, тридцать, шестьдесят, сто двадцать один, двести сорок три», то же самое, что получено выше.

Смотрите также

Рекомендации

  1. ^ Гао, Шули; Аль-Халили, Д .; Чабини, Н. (июнь 2012 г.), «Улучшенный сумматор BCD с использованием 6-LUT FPGA», 10-я Международная конференция по новым схемам и системам IEEE (NEWCAS 2012), стр. 13–16, Дои:10.1109 / NEWCAS.2012.6328944
  2. ^ "Преобразователь двоичного в двоично-десятичный:" Двойной алгоритм преобразования двоичного в двоично-десятичный формат"" (PDF). Архивировано из оригинал (PDF) 31 января 2012 г.
  3. ^ Вестиас, Марио П .; Нето, Горацио К. (март 2010 г.), «Параллельные десятичные умножители с использованием двоичных умножителей», VI Южная конференция по программируемой логике (SPL 2010), стр. 73–78, Дои:10.1109 / SPL.2010.5483001
  4. ^ Абдельхади, Амир (07.07.2019), AmeerAbdelhadi / Преобразователь двоичного кода в BCD, получено 2020-03-03
  5. ^ Абдельхади, Амир (07.07.2019), AmeerAbdelhadi / Преобразователь двоичного кода в BCD, получено 2020-03-03
  6. ^ «SBA». sba.accesus.com. Получено 2016-12-31. Архитектура простого автобуса
  7. ^ Godse, Deepali A .; Годсе, Атул П. (2008). Цифровые методы. Пуна, Индия: Технические публикации. п. 4. ISBN  978-8-18431401-4.

дальнейшее чтение