검색어 입력폼

Booth’s Algorithm 구현(부스 알고리즘 C언어구현)

저작시기 2008.09 |등록일 2010.01.09 한글파일한글 (hwp) | 9페이지 | 가격 2,000원

소개글

Booth’s Algorithm 구현(부스 알고리즘 C언어구현)

부스알고리즘에 대한 요약과 그리고 프로그램 구현한 것을 담았고 리포트는
좋은 점수를 받았습니다^^

1. 프로그램 소스
2. 동작 확인
64 X 8 의 출력 과정
3. 부스 알고리즘의 이해와 적용

목차

1. 프로그램 소스
2. 동작 확인
64 X 8 의 출력 과정
3. 부스 알고리즘의 이해와 적용

본문내용

(1) Booth’s Algorithm 구현

첫 번째 예로 32bit 곱셈에서 기존의 방법은 32회 계산을 수행해서 해당 번째의 multiplier의 bit를 확인하여 1이면, multiplicand를 shift left해 준 값을 product에 더해 준다. 따라서, shift는 32회 발생한다. 또한 add 연산은 multiplier의 bit 중 1의 개수만큼 발생하므로 비효율적이다. 이를 개선하여, 특정 숫자 k를 2^n – 2^m으로 바꾸어 연산하는 것을 booth algorithm이라 한다. 따라서, 같은 숫자를 갖는 bit가 연이어 나올 경우 연산을 상당히 줄일 수 있다. 따라서 여러 번 발생하는 add 연산을 적은 수의 add, sub 연산으로 바꾼다. Booth’s simulator에서는 이를 구현하며, 각 과정에서의 결과 중 argument에서 지정한 결과를 출력하고, 최종 결과를 화면에 출력한다
곱셈을 수행할 두 변수를 입력 받게되면, 입력 받은 A를 multiplicand로, B를 multiplier로 놓고 곱셈을 수행하도록 한다. 두 변수는 16bit의 입력으로 가정하고, product는 32bit로 한다. 이 때, Booth’s algorithm에서 이전의 LSB를 저장하는 bit를 하나 더 두어 연산을 수행하도록 하였으므로, extra Bit 변수를 선언하여 사용한다. Extra Bit 변수는 실제로는 32bit의 integer로 선언하나 0과 1 중 하나만을 갖도록 한 다.
위의 가정에서 두 변수가 16bit로 가정하였으므로, iteration은 16회 발생하며 여기에 0번째 iteration이 있으므로 총 17회의 iteration이 발생한다. 0번째 iteration에서는 product에 multiplier의 하위 16bit를 더해 주고, extra bit을 0으로 set해 준다. 이 경우 입력받은 multiplier는 32bit였으므로, 아래의 연산을 통해 하위 16bit만을 취하도록 한다.

참고 자료

없음
다운로드 맨위로