2개의 곱항에서 공통인수를 이용한 논리 분해식 산출

권오형,Kwon, Oh-Hyeong 한국컴퓨터산업학회 2006 컴퓨터産業敎育學會論文誌 Vol.7 No.4

본 논문에서는 부울 분해식을 산출하기 위한 방법을 제시한다. SIS 1.2에서 사용되는 코커널 큐브 행렬은 코커널/커널들로부터 만들어지며, 이 행렬은 단지 대수 분해식만을 산출한다. 제안한 방법은 2개의 항에서 공통인수를 추출하고, 이들로부터 분해식 산출 행렬을 만들고 이로부터 부울 분해식을 산출하는 방법을 제안한다. A factorization is an extremely important part of multi-level logic synthesis. The number of literals in a factored form is a good estimate of the complexity of a logic function, and can be translated directly into the number of transistors required for implementation. Factored forms are described as either algebraic or Boolean, according to the trade-off between run-time and optimization. A Boolean factored form contains fewer number of literals than an algebraic factored form. In this paper, we present a new method for a Boolean factorization. The key idea is to identify two-cube Boolean subexpression pairs from given expression. Experimental results on various benchmark circuits show the improvements in literal counts over the algebraic factorization based on Bryton's co-kernel cube matrix.

2-큐브 제수와 보수에 의한 공통 논리식 산출

권오형,오임걸,Kwon, Oh-Hyeong,Oh, Im-Geol 한국정보처리학회 2008 정보처리학회논문지 A Vol.15 No.1

본 논문에서는 논리합성을 위한 공통식 추출 방법을 새롭게 제안한다. 제안하는 방법은 주어진 각 논리식들에서 2개의 큐브만으로 구성된 2-큐브 논리식 쌍을 추출한다. 2개의 큐브로 구성된 논리식 쌍들로부터 2-큐브 행렬을 만들고, 여기에 2-큐브 논리식의 보수를 추가하여 확장된 2-큐브 행렬과 압축 2-큐브 행렬을 만든다. 다음, 공통식 추출을 위해 압축 2-큐브 행렬을 분석한다. 그리디 방법(greedy method)에 의해 가장 많은 리터럴 개수를 줄일 수 있는 공통식을 선택한다. 실험결과 여러 벤치마크 회로에 대하여 제안한 방법을 논리회로 합성도구에 활용할 경우 기존 합성도구보다 리터럴 개수를 줄일 수 있음을 보였다. This paper presents a new Boolean extraction technique for logic synthesis. This method extracts two-cube Boolean subexpression pairs from each logic expression. It begins by creating two-cube array, which is extended and compressed with complements of two-cube Boolean subexpressions. Next, the compressed two-cube array is analyzed to extract common subexpressions for several logic expressions. The method is greedy and extracts the best common subexpression. Experimental results show the improvements in the literal counts over well-known logic synthesis tools for some benchmark circuits.

확장된 2-큐브 행렬을 이용한 부울 분해식 산출

권오형,오임걸,Kwon, Oh-Hyeong,Oh, Im-Geol 한국컴퓨터산업학회 2007 컴퓨터産業敎育學會論文誌 Vol.8 No.4

분해식은 SOP 형태의 논리식들이 논리합과 논리곱으로 반복해서 표현된 논리식이다. 분해식을 산출하는 과정은 논리식 내에 있는 공통식을 찾아 인수분해를 반복하는 과정이다. 분해식의 형태에 따라 대수 분해식과 부울 분해식으로 구분되며, 리터럴 개수를 기준으로 부울 분해식이 대수 분해식보다 간략화된 형태를 갖는다. 본 논문은 부울 분해식 산출 방법을 제안한 것이다. 제안하는 방법은 주어진 논리식에서 2개의 큐브를 선택하여 제수/몫 쌍들을 산출한다. 이 때, 2개의 큐브로 구성된 몫에 공통인수를 남겨두어 확장 제수/몫 쌍들을 산출하고 후에 몫/몫 쌍들을 산출하도록 하였다. 산출된 제수/몫 쌍과 확장 제수/몫 쌍, 몫/몫 쌍들을 이용하여 부울 분해식 산출 을 위한 행렬을 산출하고, 행렬 커버링을 통해 부울 분해식을 산출하는 방법을 제시한다. A factored form is a sum of products of sums of products, ..., of arbitrary depth. Factoring is the process of deriving a parenthesized form with the smallest number of literals from a two-level form of a logic expression. The factored form is not unique and described as either algebraic or Boolean. A Boolean factored form contains fewer number of literals than an algebraic factored form. In this paper, we present a new method for a Boolean factorization. The key idea is to identify two-cube Boolean subexpressions from given two-level logic expression and to extract divisor/quotient pairs. Then, we derive extended divisor/quotient pairs, where their quotients are not cube-free, from the generated divisor/quotients pairs. We generate quotient/quotient pairs from divisor/quotient pairs and extended divisor/quotient pairs. Using the pairs, we make a matrix to generate Boolean factored form based on a technique of rectangle covering.

다변수 출력 함수에서 공통 논리식 추출

권오형,Kwon, Oh-Hyeong 한국컴퓨터산업학회 2006 컴퓨터産業敎育學會論文誌 Vol.7 No.5

본 논문에서는 여러 개의 출력단을 갖는 논리회로에서 공통식을 찾는 방법을 제안하였다. 각각의 출력단위로 2개의 큐브로 구성된 몫을 찾고, 이 몫들 간의 쌍을 이용해서 부울 공통식을 찾는 방법을 보였다. 실험 결과로 2개의 큐브만을 이용한 공통식 산출만으로 전체 논리회로의 크기를 줄이는 데 효과가 있음을 SIS1.2 결과와 비교하여 보였다. Extraction is tile most important step in global minimization. Its approache is to identify and extract subexpressions, which are multiple-cubes or single-cubes, common to two or more expressions which can be used to reduce the total number of literals in a Boolean network. Extraction is described as either algebraic or Boolean according to the trade-off between run-time and optimization. Boolean extraction is capable of providing better results, but difficulty in finding common Boolean divisors arises. In this paper, we present a new method for Boolean extraction to remove the difficulty. The key idea is to identify and extract two-cube Boolean subexpression pairs from each expression in a Boolean network. Experimental results show the improvements in the literal counts over the extraction in SIS for some benchmark circuits.

부울 대입에 의한 논리식 최적화

권오형(Kwon, Oh-Hyeong) 한국산학기술학회 2009 한국산학기술학회논문지 Vol.10 No.11

본 논문에서는 나눗셈 행렬을 이용하여 부울 대입식을 산출하는 논리합성 방법을 제안한다. 최적화하고자 하는 2개의 논리식들로부터 대수 나눗셈에 의한 행렬을 만들고 부울 공리와 리터럴 추가를 통해 부울 나눗셈 행렬로 확장을 한다. 부울 나눗셈 행렬에 리터럴을 추가하여 확장된 부울 나눗셈 행렬을 만들고, 원소들을 커버링하여 부울 대입식을 산출한다. 실험결과 여러 벤치마크 회로에 대하여 제안한 방법이 기존 합성도구보다 리터럴 개수를 줄일 수 있음을 보였다. A method for performing Boolean resubstitution is proposed. This method is efficiently implemented using division matrix. It begins by creating an algebraic division matrix from given two logic expressions. By introducing Boolean properties and adding literals into the algebraic division matrix, we make the Boolean division matrix. Using this extended division matrix, Boolean substituted expressions are found. Experimental results show the improvements in the literal counts over well-known logic synthesis tools for some benchmark circuits.

다출력 논리회로에서 공통식 산출

권오형(Oh-Hyeong Kwon) 대한전자공학회 2021 대한전자공학회 학술대회 Vol.2021 No.6

This is a proposal for a method for extracting common logic expressions. The Hadamard matrix is used to reduce the number of literals used in all logical expressions. The proposed method was compared with other methods for the execution time and the number of literals for the benchmark circuits. Experimental results show that the proposed method can reduce the number of literals.

해밍거리가 3인 큐브를 활용한 공통식 추출

권오형 ( Oh-hyeong Kwon ) 한국컴퓨터교육학회 2017 컴퓨터교육학회 논문지 Vol.20 No.4

논리회로 심화학습에 사용할 수 있는 논리식 간략화 도구로 활용하고 더 나아가 반도체 부품 최적화를 위한 설계자동화 도구로 활용할 수 있는 도구를 제안한 것이다. 본 논문에서 제시하는 논리식 간략화 방법은 여러 논리식에 존재하는 공통부분을 찾아 반복 사용을 줄이는 것이다. 최종적으로 전체 논리식에 사용된 리터럴 개수를 최소화하는 것을 목표로 한다. 이 전의 연구들이 나눗셈 원리를 이용해서 공통식을 찾았기 때문에 논리식에 내재한 공통식을 산출하는 데는 실패하였다. 본 논문에서 제안하는 방법은 논리식들 사이에 내재된 공통식을 찾도록 해밍거리가 3인 큐브들을 이용하였다. 벤치마크 회로를 이용한 실험을 통해 타 방법들과 간략화 정도를 비교했을 때, 제안한 방법으로 최대 47% 정도의 리터럴 개수를 줄이는 효과를 보였다. This paper proposes a tool that can be used as a logical expression simplification tool that can be used for deepening learning of logic circuits and further utilized as a design automation tool for optimizing semiconductor parts. The simplification method of logical expressions proposed in this paper is to find common subexpressions existing in various logical expressions and reduce the repetitive use. Finally, the goal is to minimize the number of literals used in all logical expressions. These previous studies failed to produce a common subexpression embedded in the logical expressions because they only use division principle. The proposed method uses cubes with a Hamming distance of 3 to find the common subexpression embedded between logical expressions. Experiments using benchmark circuits show that the proposed method reduces the number of literals by as much as 47% when comparing simplifications with other methods.

부울 나눗셈 표 채움에 의한 논리식 인수분해

권오형(Oh-Hyeong Kwon) 한국정보기술학회 2013 한국정보기술학회논문지 Vol.11 No.8

Factored forms are described as either algebraic or Boolean. A Boolean factored form contains fewer number of literals than an algebraic factored form. In this paper, we present a new method for a Boolean factoring with division mechanism which is a data structure, boolean division matrix, for division and Boolean axioms. The key idea is how to create a boolean division matrix with selected two cubes in a given logic expression. Then we suggest heuristic methods, which are to find only one non-zero columns and dominated columns, in order to make a reduced boolean division matrix for easily extracting rectangles. Experimental results show the improvements in literal counts over previous other factoring methods.

배타 논리합 원리를 이용한 다출력 논리회로 간략화

권오형(Kwon, Oh-Hyeong) 한국산학기술학회 2014 한국산학기술학회논문지 Vol.15 No.9

다출력 논리식에서 공통식을 추출하는 것은 매우 중요한 기술이다. 본 논문에서는 배타 논리합 식 산출 원리를 이용 해서 공통식을 추출하는 새로운 방법을 제안하였다. 산출된 논리식은 AND, OR, NOT 연산자만을 이용해서 전체 논리식을 표현하도록 고안하였다. 공통식 산출의 수행 시간과 리터럴 개수를 줄이기 위해서 선험 방법을 제안하였다. 실험 결과 제안한 방법이 기존의 방법들보다 리터럴 개수를 줄일 수 있음을 보였다. An extraction technique for a common logic expression is an extremely important part of multiple-output logic synthesis. This paper presents a new Boolean extraction technique using an exclusive-OR logic synthesis principle. The logic circuits produced only have AND, OR and NOT gates. Heuristic methods can also be applied to reduce the execution time and the number of literals. The experimental results showed improvements in the literal counts over the previous methods.

논리식 커널들에 스펙트럴 기법을 적용한 공통식 추출

권오형(Oh-Hyeong Kwon) 한국컴퓨터교육학회 2021 한국컴퓨터교육학회 학술발표대회논문집 Vol.25 No.2(A)

주어진 여러 논리식들에서 공통 부분을 추출하여 반복 사용을 줄이기 위한 방법을 제안한 것이다. 제안하는 방법은 기존의 코커널과 커널을 이용한 방법인 나눗셈에 의한 방법에 스펙트럴 방법을 추가해서 기존에 찾을 수 없던 공통식을 산출한 것이며, 논리식은 AND, OR, NOT, XOR 연산자로 구성된다. 커널에 스펙트럴 방식을 적용해서 공통식을 찾는 방법을 고안하였다. 이 때, 하다마드 행렬을 이용한 스펙트럴 방식을 이용하였다. 벤치마크 회로를 대상으로 실시한 실험에서 제안한 방법이 기존 논리식 방법들보다 리터럴 개수를 줄일 수 있음을 보였다.