골드스미트 역수 알고리즘에 관한 연구

송홍복(Hong-Bok Song) 동의대학교 정보통신연구소 2005 정보통신연구지 Vol.6-2 No.-

본 논문에서는 골드스미트 부동소수점 역수 알고리즘을 변형하여, 오차가 정해진 값보다 작아질 때까지 곱셈을 반복해서 역수를 계산하는 가변 시간 골드스미트 부동소수점 역수 알고리즘을 제안한다. 부동소수점 F의 역수는 '1/F'의 근사 값 T를 분모와 분자에 곱하면 '1/F=T/TF=T/B'가 된다. B가 '1'보다 큰 경우에는 'A=B-1, 1/F=T(1-A)(1+A²)(1+A⁴)...'을 'Ai<2-P/2'이 될 때까지 계산을 하고 p는 누적 오차를 고려한 유효 자리수?. B가 '1'보다 작으면 'A=1-B, 1/F=T(1+A)(1+A²)(1+A⁴)...'을 'Ai<'2-p/2'이 될 때까지 계산한다. A는 항상 양의 수이므로 'Ai<'2-p/2'을 판정하는 회로는 A의 소수점 이하P/2 비트가 모도 '0'인가를 판정하는 회로이다. 본 논문에서 제안한 골드스미트 역수 알고리즘을 결과 값의 오차가 일정한 값보다 작아질 때까지만 반복 연산을 수행하므로 역수 계산기의 성능을 높일 수 있으며, 또한 최적의 근사 역수 테이블을 구성한다.

M-AND, M-OR, NOT 연산을 이용한 다치 논리 함수의 간단화에 관한 연구

송홍복,김영진,김명기 한국통신학회 1992 韓國通信學會論文誌 Vol.17 No.6

본 논문에서는 Lukasiewicz가 제시한 M-AND, M-OR, 보07연산을 기본으로 하는 다치(MultipleValued)논리 함수의 간단화 방법을 제 시 하였다. 먼저 간단화를 행하기 위해서는 Cube를 나열하는 방법에 의해서 그 결과가 틀리기 때문에 가장 효과적인 인접항을 찾는 방법은 간단화에서 무엇보다도 중요하다. 이 방법에 의하여 진리표에 주어진 2변수 다치논리함수를 분해하고 이함수로부터 적항수의 개수를 비교하였다 본 논문의 방법에 의하면 기존방법[3]에 비해 동일한 함수를 실현시키는데 소자수 및 코스트가 상당히 감소됨 이 밝혀졌다. This paper offers the simplification method of Multiple-Valued logic function based on M-AND,M-OR, NOT operation presented by Lukasiewicz. First in performing the simplification the result is different by the method to arrange Cube, the method to find the most effective adjacent term if, most of all, important in simplification. According to this method, the two-variable multiple-valued logic function given by truth table is decomposed. The simplification method in this paper proves that the number of devices and cost is considerably reduced comparing with the existing method 141 to realize the same logic functions.

동영상에서 다층신경망을 이용한 실시간 얼굴위치 추적

송홍복(Hong-bok Song),설지환(Ji-hwan Seal) 동의대학교 정보통신연구소 2002 정보통신연구지 Vol.3-1 No.-

동영상에서 움직이는 인간을 검출하고 얼굴인식에 적합한 좋은 품질의 얼굴 영상을 취득하는 일은 동영상기반 얼굴인식 응용분야의 전단계로서 매우 중요한 부분이다. 본 논문 에서는 실생활 환경에서 실시간으로 응용이 가능한 빠르고 신뢰할 수 있는 인간과 얼굴 검출 기법을 제안하고자 한다. 정지 영상 기반 얼굴검출을 위해서는 눈 영역 기반 탐색영역 축소와 고유 얼굴 기법이 사용되며 동영상 기반 인간과 얼굴 검출을 위해서는 하이브리드 형태의 누적 차영상 기법과 움직임 추적을 위한 칼만 필터가 결합되어 사용되었다.

유한체 상의 고속 인버터 연산회로 설계

송홍복 東義大學校 産業技術開發硏究所 1999 産業技術硏究誌 Vol.13 No.-

The arithmetic operations on the field GF(P???) nas many important applications. It's applied to error-correcting code, cryptographic, switching theory and digital signal processing. There is a need for a high speed Inverter circuit in the finite field GF(P???), because 'Inversion' is most complicated and lengthy operation. In this paper, we will propose a design method of high speed inverter circuit that is based on the Euclids algorithm. The inverter circuit is composed of a number of the identical basic circuits. There fore the designed circuit has a regular and expandable feature and has a modular structure.

개선된 역수 알고리즘을 사용한 정수 나눗셈기

송홍복,박창수,조경연,Song, Hong-Bok,Park, Chang-Soo,Cho, Gyeong-Yeon 한국정보통신학회 2008 한국정보통신학회논문지 Vol.12 No.7

반도체 집적 기술의 발달과 컴퓨터에서 멀티미디어 기능의 사용이 많아지면서 보다 많은 기능들이 하드웨어로 구현되기를 원하는 요구가 증가되고 있다. 그래서 현재 사용되는 대부분의 32 비트 마이크로프로세서는 정수 곱셈기를 하드웨어로 구현하고 있다. 그러나 나눗셈기는 기존의 알고리즘인 SRT 알고리즘의 방식이 하드웨어 구현상의 복잡도와 느린 동작 속도로 인해 특정 마이크로프로세서에 한해서만 하드웨어로 구현되고 있다. 본 논문에서는 'w bit $\times$ w bit = 2w bit' 곱셈기를 사용하여 $\frac{N}{D}$ 정수 나눗셈을 수행하는 알고리즘을 제안한다. 즉, 제수 D 의 역수를 구하고 이를 피제수 N 에 곱해서 정수 나눗셈을 수행한다. 본 논문에서는 제수 D 가 '$D=0.d{\times}2^L$, 0.5<0.d<1.0'일 때, '$0.d{\times}1.g=1+e$, $e<2^{-w}$'가 되는 '$\frac{1}{D}$'의 근사 값 '$1.g{\times}2^{-L}$'을 가칭 상역수라고 정의하고, 상역수를 구하는 알고리즘을 제안하고, 이렇게 구한 상역수 '$1.g{\times}2^{-L}$'을 피제수 N에 곱하여 $\frac{N}{D}$ 정수 나눗셈을 수행한다. 제안한 알고리즘은 정확한 역수를 계산하기 때문에 추가적인 보정이 요구되지 않는다. 본 논문에서 제안하는 알고리즘은 곱셈기만을 사용하므로 마이크로프로세서를 구현할 때 나눗셈을 위한 추가적인 하드웨어가 필요 없다. 그리고 기존 알고리즘인 SRT 방식에 비해 빠른 동작속도를 가지며, 워드 단위로 연산을 수행하기 때문에 기존의 나눗셈 알고리즘보다 컴파일러 작성에도 적합하다. 따라서, 본 논문의 연구 결과는 마이크로프로세서 및 하드웨어 크기에 제한적인 SOC(System on Chip) 구현 등에 폭넓게 사용될 수 있다. With the development of semiconductor integrated technology and with the increasing use of multimedia functions in computer, more functions have been implemented as hardware. Nowadays, most microprocessors beyond 32 bits generally implement an integer multiplier as hardware. However, as for a divider, only specific microprocessor implements traditional SRT algorithm as hardware due to complexity of implementation and slow speed. This paper suggested an algorithm that uses a multiplier, 'w bit $\times$ w bit = 2w bit', to process $\frac{N}{D}$ integer division. That is, the reciprocal number D is first calculated, and then multiply dividend N to process integer division. In this paper, when the divisor D is '$D=0.d{\times}2^L$, 0.5 < 0.d < 1.0', approximate value of ' $\frac{1}{D}$', '$1.g{\times}2^{-L}$', which satisfies ' $0.d{\times}1.g=1+e$, $e<2^{-w}$', is defined as over reciprocal number and then an algorithm for over reciprocal number is suggested. This algorithm multiplies over reciprocal number '$01.g{\times}2^{-L}$' by dividend N to process $\frac{N}{D}$ integer division. The algorithm suggested in this paper doesn't require additional revision, because it can calculate correct reciprocal number. In addition, this algorithm uses only multiplier, so additional hardware for division is not required to implement microprocessor. Also, it shows faster speed than the conventional SRT algorithm and performs operation by word unit, accordingly it is more suitable to make compiler than the existing division algorithm. In conclusion, results from this study could be used widely for implementation SOC(System on Chip) and etc. which has been restricted to microprocessor and size of the hardware.

전류 모드 CMOS를 이용한 다치 FFT 연산기 설계

송홍복(Hong-Bok Song),서명웅(Myung-woong Seo) 한국지능시스템학회 2002 한국지능시스템학회논문지 Vol.12 No.2

CCD를 이용한 다치논린회로의 설계에 관한 Tabular법

송홍복,정만영 한국통신학회 1988 韓國通信學會論文誌 Vol.13 No.5

본 논문에서는 Tabular法을 이용한 CCD(charge-coupled device) 4値論理回路를 설계하는 방법을 제시하였다. 첫 번째 4値 논리함수를 수산(手算) 및 컴퓨터 프로그래밍에 의해서 분해하고 이것을 기초로 하여 Tabular法에 의한 CCD 4値회로를 실현시키는 알고리즘을 유도하였다. 이 알고리즘에 의해서 2變數 4値 논리함수를 분해(分解)해서 4개의 기본게이트에 의해서 CCD회로를 실현시켰다. 본 논문의 방법에 의하면 기존방법에 비해 동일한 함수를 실현시키는데 소자수(素子數)와 코스트가 상당히 감소됨이 밝혀졌다. This paper offers a method to design CCD four-valued circuits using the tabular method. First, the four-valued logic function is decomposed by hand-calculation or computer program. Nest, the algorithm is derived form the tabular method based on the decomposition process to realize the DDC four-valued circuit. According to this algorithm, the two-variable four valued logic function is decomposed and realized by CCD network with four basic gates. The synthesis method in this paper proves that the number of devices and cost is considerably reduces as compared with the existing methods to realize the same logic functions.

입력 디코더를 부착한 AND-EXOR형 PLA의 설계법에 관한 연구

송홍복,김명기,Song, Hong-Bok,Kim, Myung-Ki 대한전자공학회 1990 전자공학회논문지 Vol. No.

An optimization problem of AND-EXOR PLA's with input decoders can be regarded as a minimization problem of Exclusive-Or Sum-Of-Products expressions (ESOP's) for multiple-valued input two-valued output functions. In this paper, We propose a minimization algorithm for ESOP's. The algorithm is based on an iterative improvement. Five rules are used to replace a pair of products with another one. We minimized many ESOP's for arithmetic circuits. In most cases, ESOP's required fewer products than SOP's to realized same functions. 입력 디코더(decoder)가 달린 AND-EXOR형 PLA(programmable logic array)의 간단한 문제는 다치(Multiple-Value)입력 2치 출력 함수를 표현하는 ESOP(배타적 논리화를 이용한 적화형 논리식)의 간단한 문제에 대응한다. 본 논문에서는 5종류 적항의 변형 규칙(rule)을 이용한 ESOP의 간단한 알고리듬을 제안한다. 본 알고리듬에 의해 많은 산술회로의 데이타에 대해서 간단화를 행하였다. 그 결과, 1비트 입력디코더 및 2비트 입력디코더가 달린 PLA의 어느쪽에도 같은 예로써, AND-OR형 PLA 보다 AND-EXOR형 PLA의 쪽이 적은 적항수로 실현될 수 있었다.

곱셈기를 사용한 배정도 정수 나눗셈기

송홍복,조경연,Song, Hong-Bok,Cho, Gyeong-Yeon 한국정보통신학회 2010 한국정보통신학회논문지 Vol.14 No.3

본 논문에서는 'w bit $\times$ w bit = 2w bit' 곱셈기를 사용하여 2w 비트 정수 N과 w 비트 정수 D의 $\frac{N}{D}$용 나눗셈을 수행하는 알고리즘을 제안한다. 본 연구에서 제안하는 알고리즘은 제수 D가 '$D=0.d{\times}2^L$, 0.5 < 0.d < 1.0'일 때, '$0.d{\times}1.g=1+e$, e < $2^{-w}$'가 되는 '$\frac{1}{D}$'의 근사 값 '$1.g{\times}2^{-L}$'을 가칭 상역수로 정의하고, 피제수 N을 'w-3' 비트 보다 작은 워드로 분할하고, 각 분할된 워드에 상역수를 곱해서 부분 몫을 계산하고, 부분 몫을 합산하여 배정도 정수 나눗셈의 몫을 구한다. 제안한 알고리즘은 정확한 몫을 산출하기 때문에 추가적인 보정이 요구되지 않는다. 본 논문에서 제안하는 알고리즘은 곱셈기만을 사용하므로 마이크로프로세서를 구현할 때 나눗셈을 위한 추가적인 하드웨어가 요구되지 않는다. 그리고 기존 알고리즘인 SRT 방식에 비해 동작속도가 빠르다. 따라서 본 논문의 연구 결과는 마이크로프로세서 및 하드웨어 크기에 제한적인 SOC(System on Chip) 구현 등에 폭넓게 사용될 수 있다. This paper suggested an algorithm that uses a multiplier, 'w bit $\times$ w bit = 2w bit', to process $\frac{N}{D}$ integer division of 2w bit integer N and w bit integer D. An algorithm suggested of the research, when the divisor D is '$D=0.d{\times}2^L$, 0.5 < 0.d < 1.0', approximate value of $\frac{1}{D}$, '$1.g{\times}2^{-L}$', which satisfies '$0.d{\times}1.g=1+e$, e < $2^{-w}$', is defined as over reciprocal number and the dividend N is segmented in small word more than 'w-3' bit, and partial quotient is calculated by multiplying over reciprocal number in each segmented word, and quotient of double precision integer division is evaluated with sum of partial quotient. The algorithm suggested in this paper doesn't require additional correction, because it can calculate correct reciprocal number. In addition, this algorithm uses only multiplier, so additional hardware for division is not required to implement microprocessor. Also, it shows faster speed than the conventional SRT algorithm. In conclusion, results from this study could be used widely for implementation SOC(System on Chip) and etc. which has been restricted to microprocessor and size of the hardware.

NP 同値類 대표함수를 이용한 AND-EXOR 最少 論理式의 表現

宋洪復,金聖大,金明起 동아대학교 공과대학 부설 한국자원개발연구소 1990 硏究報告 Vol.14 No.1

The paper presents a catalog of AND-EXOR expressions for representative functions of four-variable NP-equivalence classes. Minimality is defined as minimizing first the number of product terms and then the total number of literal in the expression. Also, the properties of minimum expressions are discussed. Using this as a base, we compare minimum expressions of AND-OR type two-variable circuit with minimum expressions of AND-EXOR type two-variable circuit which used algorithm in this paper. As a result if was found that in the case of AND-OR type minimum expressions, number of product terms is under 8, and in the case of AND-EXOR type minimum expressions all functions are formed in which number of product terms is under 6, and generally number of product term is considerably small to realize four variable function toward AND-EXOR type minimum expression circuit.