더블 다블

Double dabble

컴퓨터 공학에서, 더블 다블 알고리즘은 이진수를 이진 코드 십진법(BCD) 표기법으로 변환하는데 사용된다.[1][2]또한 shift-and-add-3 알고리즘으로도 알려져 있으며, 컴퓨터 하드웨어에서는 적은 수의 게이트를 사용하여 구현이 가능하지만, 높은 대기 시간을 희생하여 구현할 수 있다.[3]

알고리즘.

알고리즘은 다음과 같이 동작한다.

변환할 원래 번호가 n비트 너비의 레지스터에 저장된다고 가정해 보십시오.원래 번호와 BCD 표현을 모두 담을 수 있을 만큼 넓은 스크래치 공간을 예약하십시오. n + 4×ceil(n/3) 비트면 충분하다.각 소수 자릿수를 저장하려면 2진수로 최대 4비트가 필요하다.

그런 다음 스크래치 공간을 BCD 자릿수(왼쪽)와 원래 레지스터(오른쪽)로 분할하십시오.예를 들어, 변환할 원래 숫자의 폭이 8비트인 경우 스크래치 공간은 다음과 같이 분할된다.

100s 텐스 원 오리지널 0010 0100 0011 11110011

위의 도표는 원래 레지스터에서 243의10 이진표현과 왼쪽의 BCD표현 243을 나타낸다.

스크래치 공간이 모두 0으로 초기화되고 변환할 값이 오른쪽의 "원래 레지스터" 공간에 복사된다. 

0000 0000 0000   11110011

알고리즘은 n번 반복한다.각 반복에서 최소 5(이진수 0101)인 BCD 자릿수는 3(0011)씩 증가하며, 그러면 전체 스크래치 공간이 한 비트씩 왼쪽으로 바뀐다.증분을 통해 증분 및 좌변환 값 5가 16(100)이 되므로 다음 BCD 숫자로 정확하게 "이동"할 수 있다.

기본적으로 알고리즘은 각 반복마다 왼쪽의 BCD 값을 두 배로 늘리고 원래의 비트 패턴에 따라 1 또는 0을 추가하는 방식으로 작동한다.좌회전하면 두 가지 과제가 동시에 이루어진다.숫자가 5 이상일 경우, 베이스 10의 "캐리리" 값을 보장하기 위해 3을 더한다.

값 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 시프트 0000 1001 0000 1100000000 6 0001 0010 0001 10000000 시프트 0010 0100 0011 000000 시프트 2 4 3 BCD였으므로 TED에 3을 추가하십시오.

이제 8교대 근무를 했기 때문에 알고리즘은 종료된다."원래 레지스터" 공간의 왼쪽에 있는 BCD 자릿수는 원본 값 243의 BCD 인코딩을 표시한다.

더블 다블 알고리즘의 다른 예 - 값 6524410. 

104103102101100오리지널 2진 000000000000000000001111111011011100 Initialization 000000000000000000011111110110111000 교대 00000000000000000011(1일)1111101101110000 교대(2일)00000000000000000111이고요 1111011011100000고 Shift를 떠나(3)000000000000000010101111011011100000 Add 3대 1을 떠났다.00, s이후 인스 7000000000000000101011110110111000000 교대(4일)000000000000000110001110110111000000부터 5000000001003추가 00000011 00011101101110000000고 Shift를 떠나(5일)0000000000000110 0011 1011011100000000 Shift00000000000010010011 1011011100000000 Add(6일)3에 101을 떠났다 떠났다.60000000000010010 0111이고요 0110111000000000 교대(7일)0000000000010010 10100110111000000000 Add 1003부터 7000000000010 01010100 1101110000000000 교대(8일)000000000010 10000100 1101110000000000부터 5000000000101000010011011100000000000 Shift1013추가를 떠났다(9일)000000001을 떠났다.000000010011011100000000000 Add 3에 102, 이후 5000000001000000011001011100000000000 Add 1003이후 9000000010000000110010111000000000000 교대(10일)000000010000그레고리오력에서 서기 0001년 1100명 0111000000000000 Add 1003이후 900000010 00000011 10001110000000000000 교대(11일)00000010을 떠났다.00000011 10111110000000000000 추가 3에 100, 이후 800000100 00000111이고요 0111이고요 1100000000000000고 Shift를 떠나(12일)00000100 000010100111이고요 1100000000000000 추가 3-101, 이후 700000100 0000101010101100000000000000 Add 3에 100, 이후 7000010000001010101011000000000000000 Shift을 떠나(13일)00001011년.0001010101011000000000000000 Add 3에 103, 이후 800001011년 그레고리오력에서 서기 0001년 100001011000000000000000 Add 1013이후 500001011년 그레고리오력에서 서기 0001년 100010001000000000000000 Add 1003이후 500010110 0011 000100010000000000000000 교대(14일)000110010011 000100010000000000000000 Add 3에 103이후로 남았다. 60011 0010 0110 0010 000000000000000000 시프트 왼쪽(15일) 0011 0010 1001 0010 0010 00000000000000 6 0110010 0100 0100 00000000000000 시프트 왼쪽(16일) 6 2 4 BCD 4 4B0000 시프트 왼쪽(15일) 0011 0010 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002

16교대 교대조가 수행되어 알고리즘이 종료된다.BCD 자릿수의 소수점 값은 6*104 + 5*103 + 2*102 + 4*101 + 4*100 = 65244이다.

BCD 변환기에[4] 대한 이중 다블 바이너리의 파라메트릭 Verilog 구현

// 파라메트릭 Verilog 구현 - BCD 변환기 더블 다블 바이너리 구현 // 전체 프로젝트에 대한 자세한 내용은 // https://github.com/AmeerAbdelhadi/Binary-to-BCD-Converter  모듈 bin2bcd  #( 매개 변수                W = 18)  // 입력 폭   ( 입력하다      [W-1      :0] 통을 만들다   ,  // 이진수     생산량 등기하다 [W+(W-4)/3:0] bcd   ); // BCd {...,cf,cf,cf,ones}    정수의 i,j;    항상 @(통을 만들다) 시작되다     을 위해(i = 0; i <= W+(W-4)/3; i = i+1) bcd[i] = 0;     // 0으로 초기화     bcd[W-1:0] = 통을 만들다;                                   // 입력 벡터로 초기화     을 위해(i = 0; i <= W-4; i = i+1)                       // 구조물 깊이에 반복       을 위해(j = 0; j <= i/3; j = j+1)                     // 구조물 폭에 반복         만일 (bcd[W-i+4*j -: 4] > 4)                      // 만약 > 4가 되면           bcd[W-i+4*j -: 4] = bcd[W-i+4*j -: 4] + 4'd3'; // 3 추가   종지부를 찍다  종말모듈
Parametric Verilog implementation of the double dabble binary to BCD converte, 18-bit example.
BCD 변환기에 대한 이중 다블 바이너리의 파라메트릭 Verilog 구현, 18비트 예.[5]


리버스 더블 다블

알고리즘은 완전히 되돌릴 수 있다.역 더블 다블 알고리즘을 적용하면 BCD 번호를 이진수로 변환할 수 있다.알고리즘의 역방향은 알고리즘의 원리 단계를 역방향으로 하는 것이다.

알고리즘의 기본 단계
더블 다블
(Binary to BCD)		 리버스 더블 다블
(BCD에서 이진으로)
각 입력 그룹 4비트:
그룹 >= 5인 경우 그룹에 3을 추가하십시오.
출력 숫자로의 좌측 시프트		 출력 바이너리로 오른쪽 이동
4개의 입력 비트로 구성된 각 그룹에 대해:
만약 그룹 >= 8이 그룹에서 3을 빼면

역방향 이중 대블 예제

3개의 BCD 자리 2-4-3에 대해 수행된 역방향 더블 다블 알고리즘은 다음과 같다.

BCD 입력 바이너리 출력 2 3 0010 0100 0011 00000000 초기화 0001 0010 0001 1000000 시프트 오른쪽 0000 1001 0000 11000000 시프트 오른쪽 0000 0110 0000 11000000 시프트 오른쪽 0000 0000 0000 01100 시프트 오른쪽 00001 1000 001100 시프트에서 3을 뺀 경우ed 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년대에는 프로그래머들이 이진수를 십진수로 변환하기 위해 사용하는 다른 정신적 알고리즘에도 더블 다블이라는 용어가 사용되었다.왼쪽에서 오른쪽으로 이진수를 읽고, 다음 비트가 0이면 2배, 다음 비트가 1이면 2배, 추가하면 1배씩 하는 방식으로 진행된다.[6]위의 예 11110011에서 사고 과정은 "하나, 셋, 일곱, 열다섯, 서른, 육십, 십이십한, 이백 사십삼"으로, 위에서 얻은 결과와 같은 결과가 될 것이다.

참고 항목

참조

  1. ^ Gao, Shuli; Al-Khalili, D.; Chabini, N. (June 2012), "An improved BCD adder using 6-LUT FPGAs", IEEE 10th International New Circuits and Systems Conference (NEWCAS 2012), pp. 13–16, doi:10.1109/NEWCAS.2012.6328944, S2CID 36909518
  2. ^ "Binary-to-BCD Converter: "Double-Dabble Binary-to-BCD Conversion Algorithm"" (PDF). Archived from the original (PDF) on 2012-01-31.
  3. ^ Véstias, Mario P.; Neto, Horatio C. (March 2010), "Parallel decimal multipliers using binary multipliers", VI Southern Programmable Logic Conference (SPL 2010), pp. 73–78, doi:10.1109/SPL.2010.5483001, S2CID 28360570
  4. ^ Abdelhadi, Ameer (2019-07-07), AmeerAbdelhadi/Binary-to-BCD-Converter, retrieved 2020-03-03
  5. ^ Abdelhadi, Ameer (2019-07-07), AmeerAbdelhadi/Binary-to-BCD-Converter, retrieved 2020-03-03
  6. ^ Godse, Deepali A.; Godse, Atul P. (2008). Digital Techniques. Pune, India: Technical Publications. p. 4. ISBN 978-8-18431401-4.

추가 읽기