유한체상의 여분기저를 사용한 효율적인 멀티플렉서 기반 AB² 곱셈기

김기원(Keewon Kim) 한국컴퓨터정보학회 2020 韓國컴퓨터情報學會論文誌 Vol.25 No.1

본 논문에서는 유한체상의 여분 기저(redundant basis)를 사용한 모듈러 AB² 곱셈을 수행하는 멀티플렉서(multiplexer) 기반의 기법을 제안한다. 그리고 제안한 기법을 사용하여 효율적인 멀티플렉서 기반의 세미-시스톨릭(semi-systolic) AB² 곱셈기를 제안한다. 모듈러 AB² 곱셈기의 셀 내부의 연산을 멀티플렉서로 처리할 수 있는 수식을 유도한다. 멀티플렉서를 이용하여 셀을 구현하여, 셀의 지연시간을 감소시킨다. 기존의 구조들과 비교하면, 제안한 AB² 곱셈기는 Liu 등, Lee 등, Ting 등, 및 Kim-Kim의 곱셈기들의 AT 복잡도보다 약 80.9%, 61.8%, 61.8%, 및 9.5% 가량이 감소되었다. 따라서, 제안한 곱셈기는 VLSI(very large scale integration) 구현에 적합하며 다양한 응용에 쉽게 적용할 수 있다. In this paper, we propose a multiplexer based scheme that performs modular AB² multiplication using redundant basis over finite field. Then we propose an efficient multiplexer based semi-systolic AB² multiplier using proposed scheme. We derive a method that allows the multiplexers to perform the operations in the cell of the modular AB2 multiplier. The cell of the multiplier is implemented using multiplexers to reduce cell latency. As compared to the existing related structures, the proposed AB² multiplier saves about 80.9%, 61.8%, 61.8%, and 9.5% AT complexity of the multipliers of Liu et al., Lee et al., Ting et al., and Kim-Kim, respectively. Therefore, the proposed multiplier is well suited for VLSI implementation and can be easily applied to various applications.

Low-area Bit-parallel Systolic Array for Multiplication and Square over Finite Fields

Keewon Kim(김기원) 한국컴퓨터정보학회 2020 韓國컴퓨터情報學會論文誌 Vol.25 No.2

본 논문은 유한체상의 곱셈과 제곱을 동시에 실행 가능한 알고리즘에서 공통적인 연산 부분을 도출하고, 순차적인 처리를 통해서 하드웨어를 감소시키고 공간면에서 효율적인 비트-병렬 시스톨릭 어레이를 제안한다. 제안한 시스톨릭 어레이는 기존의 어레이에 비해 적은 공간 및 공간-시간 복잡도(area-time complexity)를 가진다. 기존의 구조들과 비교하면, 제안한 시스톨릭 어레이는 공간 복잡도면에서 Choi-Lee, Kim-Kim의 시스톨릭 어레이의 약 48%, 44% 감소되었으며, 공간-시간 복잡도면에서 약 74%, 44% 가량 감소되었다. 따라서 제안한 시스톨릭 어레이는 VLSI 구현에 적합하며 사물인터넷과 같이 하드웨어 제약이 있는 환경에서 기초적인 구성 요소로 적용할 수 있다. In this paper, we derive a common computational part in an algorithm that can simultaneously perform multiplication and square over finite fields, and propose a low-area bit-parallel systolic array that reduces hardware through sequential processing. The proposed systolic array has less space and area-time (AT) complexity than the existing related arrays. In detail, the proposed systolic array saves about 48% and 44% of Choi-Lee and Kim-Kim’s systolic arrays in terms of area complexity, and about 74% and 44% in AT complexity. Therefore, the proposed systolic array is suitable for VLSI implementation and can be applied as a basic component in hardware constrained environment such as IoT.

유한체상의 효율적인 세미-시스톨릭 AB² 곱셈기

김기원(Keewon Kim) 한국컴퓨터정보학회 2020 韓國컴퓨터情報學會論文誌 Vol.25 No.1

본 논문에서는 유한체상의 SPB(shifted polynomial basis)를 사용한 효율적인 AB² 곱셈 알고리즘을 제안한다. SPB의 특징을 이용하여, AB² 곱셈을 위한 수식을 두 부분으로 분할하였다. 분할된 두 수식은 동시에 실행가능하며, 이를 병렬로 처리하는 알고리즘을 도출하였다. 그리고 제안한 알고리즘을 기반으로 효율적인 세미-시스톨릭(semi-systolic) AB² 곱셈기를 제안한다. 제안한 곱셈기는 기존의 곱셈기에 비해 낮은 공간-시간 복잡도(area-time complexity)를 가진다. 기존의 구조들과 비교하면, 제안한 AB² 곱셈기는 공간-시간 복잡도면에서 Wei, Wang-Guo, Kim-Lee, 및 Choi-Lee의 곱셈기들의 약 94%, 87%, 86%, 및 83% 가량이 감소되었다. 따라서 제안한 곱셈기는 VLSI(very large scale integration) 구현에 적합하며 다양한 응용의 기초적인 구성 요소로 쉽게 적용할 수 있다. In this paper, we propose an efficient AB² multiplication algorithm using SPB(shifted polynomial basis) over finite fields. Using the feature of the SPB, we split the equation for AB² multiplication into two parts. The two partitioned equations are executable at the same time, and we derive an algorithm that processes them in parallel. Then we propose an efficient semi-systolic AB² multiplier based on the proposed algorithm. The proposed multiplier has less area-time (AT) complexity than related multipliers. In detail, the proposed AB² multiplier saves about 94%, 87%, 86% and 83% of the AT complexity of the multipliers of Wei, Wang-Guo, Kim-Lee, Choi-Lee, respectively. Therefore, the proposed multiplier is suitable for VLSI implementation and can be easily adopted as the basic building block for various applications.

Ray tracing simulation of SCOTS test for GMT secondary mirror

김기원,김성환,김영수,Kim, Ki-Won,Kim, Sug-Whan,Kim, Young-Soo 한국천문학회 2012 天文學會報 Vol.37 No.2

We present SCOTS test simulation for on axis segment of the GMT secondary mirror that is ellipsoidal shape surface of 1.064m in diameter, 4.166747m in radius of curvature, -0.7154 in conic constant and $18.023{\mu}m$ P-V in asphericity. SCOTS test comprises a screen(diffusing sinusoidal fringe source), test surface(GMT secondary mirror), and a camera(CCD detector). We report ray tracing simulation result that is distorted sinusoidal fringe pattern detected at the camera. This simulation is to be used for analysis of experimental design, sensitivity from uncertainty, errors on fabrication and design.

선형 사진트리로 표현된 이진 영상의 면적과 둘레 길이를 계산하기 위한 상수시간 RMESH 알고리즘

김기원,우진운,Kim, Gi-Won,U, Jin-Un 한국정보처리학회 1998 정보처리학회논문지 Vol.5 No.7

계층적 자료구조인 사진트리는 이진 영상을 표현하는데 매우 중요한 자료구조이다. 사진트리를 메모리에 저장하는 방법중 선형 사진트리 표현 방법은 다른 표현 방법과 비교할 때 저장 공간을 매우 효율적으로 절약할 수 있는 이점이 있기 때문에 사진트리와 관련된 연산의 수행을 위해 선형 사진트리를 사용하는 효율적인 알고리즘 개발에 많은 연구가 진행되어 왔다. 본 논문에서는 REMSH(Reconfigurable MESH) 구조에서 3-차원 n$\times$n$\times$n 프로세서를 사용하여 선형 사진트리로 표현된 이진 영상의 면적과 둘레 길이를 계산하는 알고리즘을 제안한다. 이 알고리즘은 0(1) 시간 복잡도를 갖는다.

해태 생산라인에서의 실시간 시각검사 시스템

김기원,김봉기,Kim, Gi-Weon,Kim, Bong-Gi 한국정보통신학회 2007 한국정보통신학회논문지 Vol.11 No.6

본 논문의 내용은 실시간 영상 처리에 의한 해태 생산라인에서의 불량 제품을 자동으로 추출하는 무인 품질검사 시스템을 개발하는 것이다. 즉, 생산라인에서 해태 김의 결함을 분석하여 형태 결함을 자동 검출하는 무인 품질 검사 시스템을 개발하였다. 이를 위해 본 논문에서는 먼저 CCD 카메라를 통해 영상을 실시간으로 입력받아 고속영상 처리 보드를 통해 이진 영상으로 전처리를 수행한다. 그 후 이진 영상에서 특징이 추출되고 추출된 특징을 이용하여 품질에 결함이 있는지를 판별하였다. In this paper dose a laver surface check using a real time image process. This system does false retrieval of a laver at a laver production line. At first, a laver image was read in real time using a CCD camera. In this paper, we use an area scan CCD camera. Image is converted into a binary code image using a high-speed imaging process board afterwards. A laver feature is extracted by a binary code image. Surface false retrieval is finally executed using a laver feature. In this paper, we use an area feature of a laver image.

숲과 음악

김기원,Kim, Gi-Won 한국자연공원협회 1997 한국자연공원 Vol.68 No.-

한국 음악 속의 수학

김기원,안선필,Kim Ki-Won,Ahn Sun-Phill 한국수학사학회 2004 Journal for history of mathematics Vol.17 No.4

수학과 음악은 그 표현 방법이 아주 다른 학문이지만, 오래 전부터 수학과 음악이 관련이 있음을 이야기 해오고 있다. 이 논문에서는 수학과 한국 음악의 관계를 고찰해보고 수학 교육에의 활용 방안을 모색해 본다. Even though mathematics and music play very different roles in our society, they are closely related to each other. In this paper, we studies relations between mathematics and Korean traditional music, and give some ideas to use such relations in mathematics education.

'경영위기 아니다' 주장에 병원계 초비상

김기원,Kim, Gi-Won 대한병원협회 2002 대한병원협회지 Vol.31 No.3

WDM 전광망에서 라우팅과 파장할당을 위한 휴리스틱 방법에 대한 연구

김기원,정영철,Kim, Ki-Won,Chung, Young-Chul 대한전자공학회 2001 電子工學會論文誌-TC (Telecommunications) Vol.38 No.8

The recent explosion in the Internet applications, Internet. host number and the traffic in the IP backbone network is posing new challenges for transport network. This requires a high-speed IP backbone network that has a substantially higher bandwidth than the one offered by current networks, which prompts the development of all-optical network. To obtain optical network utilization gains, we need a software which establishs logical topology to make possible the efficient use or physical topology, and control the optical network in combination with the IP layer routing protocols. Finally, the logical topology is required higher efficient than physical topology. For this an efficient algorithm for the routing and wavelength assignment(RWA) in the WDM all-optical network is necessary. In this paper, two kinds of heuristic algorithms to establish logical topology for WDM networks and arc applied to the design of logical topology of domestic backbone network. These algorithms are found to work quite well and they arc compared with each other in terms of blocking rate, etc. 최근 인터넷 응용계층, 사용자수와 IP 백본망에서 트래픽의 폭발적인 증가는 전송망에 대해서 새로운 변화를 요구하고 있다. 이에 따라 대용량 WDM시스템들이 광범위하게 설치되고 있으며 이를 인터넷에 효율적으로 운영하기 위하여 IP/WDM을 구현하려는 노력이 진전되고 있다. WDM 전광망의 이용이득을 얻기 위해서는 IP 계층의 라우팅 프로토콜과 함께 전광망의 물리적인 망을 효율적으로 활용하게 해주는 논리적 토폴로지를 형성하고 광망을 제어하는 소프트웨어가 필요하다. 이를 위하여 WDM 전광망에서의 라우팅과 파장할당(RWA)을 효율적으로 수행할 수 있는 알고리듬이 필요하다. 본 논문에서는 WDM 전광망의 논리적인 토폴로지 형성을 위한 두 개의 직관적인 알고리듬을 구현하여 국내 백본망에 적용하였으며, 이들이 잘 동작함을 보였고 이들을 블록킹율등의 측면에서 비교분석하였다.