개선된 뉴톤-랍손 역수 및 역제곱근 알고리즘

조경연,Cho, Gyeong-Yeon 한국정보통신학회 2007 한국정보통신학회논문지 Vol.11 No.1

다음은 부동소수점 역수 및 역제곱근 계산에 많이 사용하는 뉴톤-랍손 알고리즘은 일정한 횟수의 곱셈을 반복하여 계산한다. 본 논문에서는 뉴톤-랍손 알고리즘의 반복 과정의 오차를 예측하여 오차가 정해진 값보다 작아지는 시점까지 반복 연산하는 개선된 뉴톤-랍손 알고리즘을 제안한다. 본 논문에서 제안한 알고리즘은 입력 값에 따라서 곱셈 횟수가 다르므로, 평균 곱셈 횟수를 계산하는 방식을 유도하고, 여러 크기의 근사 테이블에서 단정도실수 및 배정도실수의 역수 및 역제곱근 계산에 필요한 평균 곱셈 횟수를 산출한다. 이들 평균 곱셈 횟수를 종래 알고리즘과 비교하여 본 논문에서 제안한 알고리즘의 우수성을 증명한다. 본 논문에서 제안한 알고리즘은 오차가 일정한 값보다 작아질 때까지만 반복 연산을 수행하므로 역수 및 역제곱근 계산기의 성능을 높일 수 있고 최적의 근사 테이블을 구성할 수 있다. 본 논문의 연구 결과는 디지털 신호처리, 컴퓨터 그라픽스, 멀티미디어, 과학 기술 연산 등 부동소수점 계산기가 사용되는 분야에서 폭 넓게 사용될 수 있다. The Newton-Raphson's algorithm for finding a floating point reciprocal and inverse square root calculates the result by performing a fixed number of multiplications. In this paper, an improved Newton-Raphson's algorithm is proposed, that performs multiplications a variable number. Since the number of multiplications performed by the proposed algorithm is dependent on the input values, the average number of multiplications per an operation is derived from many reciprocal and inverse square tables with varying sizes. The superiority of this algorithm is proved by comparing this average number with the fixed number of multiplications of the conventional algorithm. Since the proposed algorithm only performs the multiplications until the error gets smaller than a given value, it can be used to improve the performance of a reciprocal and inverse square root unit. Also, it can be used to construct optimized approximate tables. The results of this paper can be applied to many areas that utilize floating point numbers, such as digital signal processing, computer graphics, multimedia, scientific computing, etc.

부동소수점수 N차 제곱근 K차 골드스미스 알고리즘

조경연 한국멀티미디어학회 2019 멀티미디어학회논문지 Vol.22 No.9

In this paper, a tentative Kth order Goldschmidt floating point number Nth root algorithm for K order convergence rate in one iteration is proposed by applying Taylor series to the Goldschmidt square root algorithm. Using the proposed algorithm, Nth root and Nth inverse root can be computed from iterative multiplications without division. It also predicts the error of the algorithm iteration. It iterates until the predicted error becomes smaller than the specified value. Since the proposed algorithm only performs the multiplications until the error gets smaller than a given value, it can be used to improve the performance of a floating point number Nth root unit.

니블 RLE 코드에 의한 비트 맵 데이타의 압축과 복원에 관한 연구

조경연,Jo, Gyeong-Yeon 한국정보처리학회 1995 정보처리논문지 Vol.2 No.6

In this paper, a nibble RLE(Run Length Encoding) code for real time compression and decompression of Hanguel bit map font and printer data is proposed. The nibble RLE code shows good compression ratio in complete form Hangeul Myoungjo and Godik style bit map font and printer output bit map data. And two ASICs seperating compression and decompression are designed and simulated on CAD to verify the proposed code. The 0.8 micron CMOS Sea of Gate is used to implement the ASICs in amount of 2, 400 gates, and these are running at 25MHz. Therefore, the proposed code could be implemented with simple hardware and performs 100M bit/sec compression and decomression at maximum, it is good for real time applications. 본 논문에서는 한글 비트 맵 폰트와 프린터 데이타의 실시간 압축과 복원에 적합 한 니블 RLE(Run Length Encoding)코드를 제안한다. 제안한 코드를 명조체와 고딕체 완성형 한글 폰트와 프린터 출력 데이타에 적용하여 압축율이 좋음을 보인다. 그리고 압축과 복원을 분리하여 각각 하나의 ASIC(주문형 반도체)으로 설계하고 CAD상에서 시뮬레이션하여 동작을 확인한다. ASIC은 0.8 미크론 CMOS 게이트 어레이로 설계하여 약 2,400 게이트가 소요되었으며 25MHz 클럭으로 동작 하였다. 따라서 제안한 코드는 간단한 하드웨어로 최고 100M bit/sec로 압축 및 복원을 수행하여 실시간 응용에 적합 하다.

가변 시간 K차 뉴톤-랍손 부동소수점 나눗셈

조경연 대한임베디드공학회 2014 대한임베디드공학회논문지 Vol.9 No.5

The commonly used Newton-Raphson's floating-point number divider algorithm performs two multiplications in one iteration. In this paper, a tentative K'th Newton-Raphson's floating-point number divider algorithm which performs K times multiplications in one iteration is proposed. Since the number of multiplications performed by the proposed algorithm is dependent on the input values, the average number of multiplications per an operation in single precision and double precision divider is derived from many reciprocal tables with varying sizes. In addition, an error correction algorithm, which consists of one multiplication and a decision, to get exact result in divider is proposed. Since the proposed algorithm only performs the multiplications until the error gets smaller than a given value, it can be used to improve the performance of a floating point number divider unit. Also, it can be used to construct optimized approximate reciprocal tables.

K차 뉴톤-랍손 부동소수점수 N차 제곱근

조경연 대한임베디드공학회 2018 대한임베디드공학회논문지 Vol.13 No.1

In this paper, a tentative Kth order Newton-Raphson's floating point number Nth root algorithm for K order convergence rate in one iteration is proposed by applying Taylor series to the Newton-Raphson root algorithm. Using the proposed algorithm, and can be computed from iterative multiplications without division. It also predicts the error of the algorithm iteration and iterates only until the predicted error becomes smaller than the specified value. Since the proposed algorithm only performs the multiplications until the error gets smaller than a given value, it can be used to improve the performance of a floating point number Nth root unit.

곱셈기를 이용한 정확한 부동소수점 제곱근 계산기

조경연,Cho, Gyeong-Yeon 한국정보통신학회 2009 한국정보통신학회논문지 Vol.13 No.8

부동소수점 제곱근 연산은 곱셈을 반복하여 근사값을 계산하는 뉴턴-랍손 알고리즘 및 골드스미트 알고리즘과 뺄셈을 반복하여 정확한 간을 계산하는 SRT 알고리즘이 있다. 본 논문에서는 곱셈기를 사용하여 정확한 값을 계산하는 제곱근 알고리즘을 제안한다. 본 논문에서는 뉴턴-랍손 알고리즘을 이용하여 근사 역제곱근을 구하고, 이의 오차를 줄이면서 제곱근을 구하는 알고리즘과 계산된 제곱근을 보정하는 알고리즘을 제안한다. 제안한 알고리즘은 단정도 실수에서는 전수 조사를 통해서, 배정도 실수에서는 10억 개의 무작위 수를 계산하여 모두 정확한 값을 얻었다. 본 논문에서 제안한 알고리즘은 곱셈기만을 사용하므로 별도의 하드웨어가 필요하지 않다. 따라서 실장제어용기기, 휴대용기기 등 정확한 제곱근 연산을 요구하는 분야에서 사용될 수 있다. There are two major algorithms to find a square root of floating point number, one is the Newton_Raphson algorithm and GoldSchmidt algorithm which calculate it approximately by iterating multiplications and the other is SRT algorithm which calculates it exactly by iterating subtractions. This paper proposes an exact floating point square root algorithm using only multiplication. At first an approximate inverse square root is calculated by Newton_Raphson algorithm, and then an exact square root algorithm by reducing an error in it and a compensation algorithm of it are proposed. The proposed algorithm is verified to calculate all of numbers in a single precision floating point number and 1 billion random numbers in a double precision floating point number. The proposed algorithm requires only the multipliers without another hardware, so it can be widely used in an embedded system and mobile production which requires an efact square root of floating point number.

DL-1-Aminoalkyl Phosphonic Acids와 그유도체들의 합성 (I)

조경연,김덕찬,김용준,Cho Kyung Yeon,Kim Duck Chan,Kim Yong Joon 대한화학회 1971 대한화학회지 Vol.15 No.1

DL-1-Amino-pentyl phosphonic acid, DL-1-Aminopropyl phosphonic acid were synthesized with good yield from caproic acid and butyric acid using the modified Curtius reaction and N-derivatives, N-acetyl-DL-1-amino propyl phosphonic acid, N-acetyl-DL-1-aminopentyl phosphonic acid, N-Benzoyl-DL-1-amino-propyl phosphonic acid, were also prepared by a variety of methods including the Schotten-Baumann reaction. In addition, the chemical and physical properties of the products were investigated. All the products were also identified by means of elemental analysis, Infrared spectrophotometry, Ninhydrin test, and the determination of the neuralization equivalent.

암호와 복호가 동일한 SPN 블록 암호 SSB

조경연,Cho, Gyeong-Yeon 한국정보통신학회 2011 한국정보통신학회논문지 Vol.15 No.4

블록 암호는 Feistel 구조와 SPN 구조로 나눌 수 있다. Feistel 구조는 암호 및 복호 알고리즘이 같은 구조이고, SPN 구조는 암호 및 복호 알고리즘이 다르다. 본 논문에서는 암호와 복호 과정이 동일한 SPN 구조 블록 암호 알고리즘인 가칭 SSB를 제안한다. SSB는 짝수 N 라운드로 구성하고, 각 라운드는 라운드 키 덧셈, 치환 계층, 바이트 교환 및 확산 계층으로 구성한다. 치환 계층은 홀수 라운드와 짝수 라운드가 서로 역의 관계를 이룬다. 확산 계층은 MDS 대합 행렬로 구성한다. SSB의 차분 및 선형 공격 확률은 $2^{-306}$로 AES와 동일하다. 본 논문에서 제안한 암호와 복호가 동일한 SPN 블럭 암호는 하드웨어 구성이 간단한 장점을 가지므로 제한적 하드웨어 및 소프트웨어 환경인 스마트카드와 전자 칩이 내장된 태그와 같은 RFID 환경에서 안전하고 효율적인 암호 시스템을 구성할 수 있다. Feistel and SPN are the two main structures in a block cipher. Feistel is a symmetric structure which has the same structure in encryption and decryption, but SPN is not a symmetric structure. In this paper, we propose a SPN block cipher so called SSB which has a symmetric structure in encryption and decryption. The proposed SSB is composed of the even numbers of N rounds. Each round consists of a round key addition layer, a subsitution layer, a byte exchange layer and a diffusion layer. The subsitution layer of the odd round is inverse function of one of the even round. And the diffusion layer is a MDS involution matrix. The differential and linear attack probability of SSB is $2^{-306}$ which is same with AES. The proposed symmetric SPN block cipher SSB is believed to construct a safe and efficient cipher in Smart Card and RFID environments which is in limited hardware and software resources.

가리왕산 지역의 개미 고도별 분포

조경연,김일권,류동표 한국환경생태학회 2020 한국환경생태학회지 Vol.34 No.2

본 연구는 생물 다양성의 지표종인 개미류의 시기별 우점종 및 개체군 변동을 살펴보고, 추후 기후변화에 따른 개체군 변화의 기초자료를 확보하고자 수행되었다. 조사 기간은 2013년 6월부터 9월까지 고도별 조사 지점을 선정하고, 함정트랩을 사용하여 정방형조사법(10m×10m)으로 개미의 분포를 조사하였다. 고도별 조사 결과, 총 3아과 11속 14종 15,466개체가 채집되었다. 낮은 고도(700m)에서 13종 4,548개체의 분포가 확인되었으며, 우점종은 일본장다리개미(49.9%)로 나타났고, 중간 고도(900m)에서 8종 9,129개체가 채집되었으며, 우점종으로 극동혹개미(57.7%)의 분포가 확인되었으며, 높은 고도 (1,100m)에서 10종 1,789개체가 확인되었으며, 우점종으로 코토쿠뿔개미(43.3%)가 확인되었다. 고도별로 일본장다리개미, 스미스개미, 극동혹개미는 폭넓게 분포하는 것으로 확인되었다. This study investigated the dominant species and the population variation of the ant species, an indicator species of biodiversity, to obtain basic data on the changes of population according to the future climate change. The survey period was from June to September 2013, and we investigated the distribution of ants by square irradiation method (10m × 10m) using traps. The survey in each altitude identified a total of 14 species of 11 genera in 3 subfamilies and collected 15,466 individuals. We confirmed the distribution of 4,548 individuals of 13 species at low altitude (700m), and the dominant species was Aphaenogaster japonica (49.9%). At the middle altitude (900m), we collected 9,129 individuals of 8 species, and the dominant species was Pheidole fervida (57.7%). At high altitude (1,100m), we identified 1,789 individuals of 10 species, and Myrmica kotokui (43.3%) was the dominant species. It was confirmed that Aphaenogaster japonica, Nylanderia flavipes, and Pheidole fervida were widely distributed throughout the altitudes.

오차 교정 K차 골드스미트 부동소수점 나눗셈

조경연,Cho, Gyeong-Yeon 한국정보통신학회 2015 한국정보통신학회논문지 Vol.19 No.10

The commonly used Goldschmidt's floating-point divider algorithm performs two multiplications in one iteration. In this paper, a tentative error corrected K'th Goldschmidt's floating-point number divider algorithm which performs K times multiplications in one iteration is proposed. Since the number of multiplications performed by the proposed algorithm is dependent on the input values, the average number of multiplications per an operation in single precision and double precision divider is derived from many reciprocal tables with varying sizes. In addition, an error correction algorithm, which consists of one multiplication and a decision, to get exact result in divider is proposed. Since the proposed algorithm only performs the multiplications until the error gets smaller than a given value, it can be used to improve the performance of a divider unit. Also, it can be used to construct optimized approximate reciprocal tables.