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

송홍복(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'인가를 판정하는 회로이다. 본 논문에서 제안한 골드스미트 역수 알고리즘을 결과 값의 오차가 일정한 값보다 작아질 때까지만 반복 연산을 수행하므로 역수 계산기의 성능을 높일 수 있으며, 또한 최적의 근사 역수 테이블을 구성한다.

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

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

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

송홍복,박창수,조경연,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.

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

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

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

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

송홍복,서명웅,Song, Hong-Bok,Seo, Myung-Woong 한국지능시스템학회 2002 한국지능시스템학회논문지 Vol.15 No.4

본 논문에서는 전류모드 CMOS의 기본회로를 이용해 다치 논리(Multiple Valued Logic) 연산기를 설계하고자 한다. 우선, 2진(binary)FFT(Fast courier Transform)를 확장해 다치 논리회로를 이용해서 고속 다치 FFT 연산기를 구현하였다. 다치논리회로를 이용해서 구현한 FFT연산은 기존의 2치 FFT과 비교를 해 본 결과 트랜지스터의 수를 상당히 줄일 수 있으며 회로의 간단함을 알 수가 있었다. 또한, 캐리 전파 없는 가산기론 구현하기 위해서 {0, 1, 2, 3}의 불필요한(redundant) 숫자 집합을 이용한 양의 수 표현을 FFT회로에 내부적으로 이용하여 결선의 감소와 VLSI 설계시 정규성과 규clr성으로 효과적이다. FFT 승산을 위해서는 승산기의 연산시간과 면적을 다치 LUT(Look Up Table)로 이용해 승산의 역할을 하였다. 마지막으로 이진시스템(binary system)과의 호환을 위해 다치 하이브리드형 FFT 프로세서를 제시하여 2진 4치 부호기와 4치 2진 복호기 및 전류모드 CMOS회로를 사용하여 상호 호환성을 갖도록 설계를 하였다. In this study, Multi-Values Logic processor was designed using the basic circuit of the electric current mode CMOS. First of all, binary FFT(Fast courier Transform) was extended and high-speed Multi-Valued Logic processor was constructed using a multi valued logic circuit. Compared with the existing two-valued FFT, the FFT operation can reduce the number of transistors significantly and show the simplicity of the circuit. Moreover, for the construction of amount was used inside the FFT circuit with the set of redundant numbers like {0, 1, 2, 3}. As a result, the defects in lines were reduced and it turned out to be effective in the aspect of normality an regularity when it was used designing VLSI(Very Large Scale Integration). To multiply FFT, the time and size of the operation was used toed as LUT(Lood Up Table).

PLA를 이용한 VLSI의 회로설계에 관한 연구

송홍복,Song Hong-Bok 한국컴퓨터산업학회 2006 컴퓨터産業敎育學會論文誌 Vol.7 No.3

본 논문에서는 최근의 64비트 마이크로프로세서에 대해서 PLA설계법 및 검사가 쉽고 용이하도록 하는 방법에 대해서 논하였다. VLSI에서 RAM. ROM. PLA를 사용한 설계법이 정착 되어가고 있으며 PLA는 논리설계와 회로변경 및 검사가 용이하기 때문에 성능과 가격이 중요하다. 향후에도 PLA는 VLSI 설계의 기본요소로서 중요한 위치를 점유할 것이다. In this paper, a method how to make Programmable Logic Array (PLA) design and inspection of circuit relative to recent 64bit microprocessor simple and easy was discussed. A design method using Random Access Memory (RAM), Read Only Memory (ROM) and PLA has been settled down in Very Large Scale Integrated Circuit (VLSI) and logical design, modifying circuit and inspection are easy in PLA so it holds fairly good advantages in the aspect of performance and cost. It is expected PLA will also occupy an important position as a basic factor in designing VLSI in the future.

다층신경망을 이용한 임의의 크기를 가진 얼굴인식에 관한 연구

송홍복(Hong-Bok Song),설지환(Ji-Hwan Seol) 한국지능시스템학회 2005 한국지능시스템학회논문지 Vol.15 No.2

본 논문에서는 실시간 폐쇄회로 화면으로 받은 컬러 이미지에서 얼굴영상을 추출하고 이미 지정된 특정인의 얼굴영상과 비교를 통해 지하철이나 은행 등 공공장소에서의 수배자 등 어떤 특정인을 검출하는 방법을 제안하고자 한다. 감시카메라의 특성상 화면속의 얼굴정보가 임의의 크기로 가변하고 영상 내에서 다수의 얼굴정보를 포함하고 있음을 가정할 때, 얼굴영역을 얼마나 정확하게 검색 할 수 있느냐에 초점을 맞추었다. 이를 해결하기 위하여F.Rosenblatt가 제안한 퍼셉트론 신경망 모델을 기초로 임의의 얼굴영상에 대한 20x20 픽셀로 서브샘플링을 사용한 규준화 작업을 통해서 전면얼굴에서와 같은 인식기법의 효과를 사용하고. 획득한 얼굴후보 영역에 대하여 조명이나 빛에 의한 외부환경의 간섭을 최소화하기 위하여 최적선형필터와 히스토그램 평활화 기법을 이용하였다. 그리고 불필요한 학습을 최소화하기 위하여 달걀형 마스크의 덧셈연산을 전 처리 과정에 추가하였다. 전 처리 과정을 마친 이미지는 각각 세 개의 수용필드로 쪼개어져 특정 위치에 존재하는 눈, 코, 입 등의 정보를 신경망 학습을 통해 최종 결정된다. 또한 각각 다른 초기값을 가지는 3개의 단일셋 네트워크 시스템을 병렬형태로 구성하여 결과의 정확도를 높여 구현하였다. This paper suggest a way to detect a specific wanted figure in public places such as subway stations and banks by comparing color face images extracted from the real time CCTV with the face images of designated specific figures. Assuming that the characteristic of the surveillance camera allows the face information in screens to change arbitrarily and to contain information on numerous faces, the accurate detection of the face area was focused. To solve this problem, the normalization work using subsampling with 20 × 20 pixels on arbitrary face images, which is based on the Perceptron Neural Network model suggested by R. Rosenblatt, created the effect of recogning the whole face. The optimal linear filter and the histogram shaper technique were employed to minimize the outside interference such as lightings and light. The addition operation of the egg-shaped masks was added to the pre-treatment process to minimize unnecessary work. The images finished with the pre-treatment process were divided into three reception fields and the information on the specific location of eyes, nose, and mouths was determined through the neural network. Furthermore, the precision of results was improved by constructing the three single-set network system with different initial values in a row.

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

송홍복,조경연,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.

입력 디코더를 부착한 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의 쪽이 적은 적항수로 실현될 수 있었다.

다치 논리 함수의 ESOP 최소화 알고리즘에 관한 연구

송홍복(Song Hong Bok) 한국정보처리학회 1997 정보처리학회논문지 Vol.4 No.7

This paper presents an algorithm simplifying the ESOP function by several rules. The algorithm is repeatedly performing operations based on the state of each terms by the product transformation operation of two functions and thus it is simplifying the ESOP function through the reduction of the product terms. Through the minimization of the product terms of the multi-valued input binary multi-output function, an optimization of the input has been done using EXOR PLA with input decoder. The algorithm when applied to four valued arithmetic circuit has been used for a EXOR logic circuit design and the the two bits input decoder has been used for a EXOR-PLA design. It has been found from a computer simulation(IBM PC486) that the suggested algorithm can reduce the product terms of the output function remarkably regardless of the number of input variables when the variable AND-EXOR PLA is applied to the poperation circuit.