유한체상에서의 선형디지털스위칭함수 구성

박춘명,Park, Chun-Myoung 한국정보통신학회 2008 한국정보통신학회논문지 Vol.12 No.12

본 논문에서는 유한체의 수학적 성질과 그래프이론을 바탕으로 GF(P)상의 선형디지털스위칭함수구성을 효과적으로 구성하는 한가지 방법을 제안하였다. 제안한 방법은 주어진 임의의 디지털스위칭함수의 입출력 사이의 연관관계특성으로 부터 DCG를 도출한 후에 노드의 개수를 인수분해한다. 이때 행렬방정식을 해당 차수보다 낮은 기약다항식으로 인수분해하여 그 결과를 부분회로실현한 다음 선형결합함으로써 최종 선형디지털스위칭함수를 구성하였다. 그 결과 기존의 방법에 비해 선형디지털스위칭함수구성을 상당히 간단화 할 수 있었으며 회로구성은 유한체 GF(P)내에서 정의된 가산기와 계수곱셈기를 사용하여 용이하게 실현 할 수 있다. This paper presents a method of constructing the Linear Digital Switching Function(LDSF) over finite fields. The proposed method is as following. First of all, we extract the input/output relationship of linear characteristics for the given digital switching functions, Next, we convert the input/output relationship to Directed Cyclic Graph(DCG) using basic gates adder and coefficient multiplier that are defined by mathematical properties in finite fields. Also, we propose the new factorization method for matrix characteristics equation that represent the relationship of the input/output characteristics. The proposed method have properties of generalization and regularity. Also, the proposed method is possible to any prime number multiplication expression.

GFDD에 기초한 디지털논리시스템 구성

박춘명,Park Chun-Myoung 한국정보통신학회 2005 한국정보통신학회논문지 Vol.9 No.8

본 논문에서는 그래프 이론에 기초를 둔 GFDD를 사용하여 디지털논리시스템을 구성하는 한가지 방법을 제안하였다. 제안한 방법은 먼저 유한체와 그래프 이론의 수학적 성질을 논의하였으며, 단일변수에 대한 동작영역과 함수영역간의 변환을 용이하게 하기 위한 변환행렬 $\psi$GF(P)(1)과 $\xi$GF(P)(1)을 논의하였다. 그리고 디지털스위칭함수를 구하기 위한 Reed-Muller 확장을 논의하였으며, 이를 다변수인 경우로 확장하기 위해 Kronecker Product를 논의하였다. This paper propose the design method of the constructing the digital logic systems over galois fields using by the galois field decision diagram(GFDD) that is based on the graph theory. The proposed design method is as following. First of all, we discuss the mathematical properties of the galois fields and the basic properties of the graph theory. After we discuss the operational domain and the functional domain, we obtain the transformation matrixes, $\psi$GF(P)(1) and $\xi$GF(P)(1), in the case of one variable, that easily manipulate the relationship between two domains. And we extend above transformation matrixes to n-variable case, we obtain $\psi$GF(P)(1) and $\xi$GF(P)(1). We discuss the Reed-Muller expansion in order to obtain the digital switching functions of the P-valued single variable. And for the purpose of the extend above Reed-Muller expansion to more two variables, we describe the Kronecker product arithmetic operation.

그래프에 기초한 스위칭함수 구현

박춘명,Park, Chun-Myoung 한국정보통신학회 2011 한국정보통신학회논문지 Vol.15 No.9

본 논문에서는 그래프에 기초하여 유한체상의 스위칭함수를 도출하는 알고리즘과 이를 바탕으로 스위칭함수를 회로로 구현하는 방법을 제안하였다. 방향성그래프의 경로 수로부터 행렬방정식을 유도한 후에 이에 따른 스위칭 함수회로설계 알고리즘을 제안하였으며, 설계된 회로와 함께 방향성 그래프의 특성을 만족할 수 있게 노드들에 대한 코드를 할당하는 알고리즘을 제안하였다. 본 논문에서 제안한 알고리즘을 통해 설계한 스위칭함수회로는 기존의 방법에 비해 좀 더 최적화된 스위칭함수회로를 구현할 수 있었으며, 제안한 스위칭함수회로설계 알고리즘을 통해 임의의 자연수의 경로 수를 갖는 방향성 그래프에 대한 설계가 가능하였다. 또한, 입출력단자 수의 감소, 회로구성의 간략화, 연산속도의 향상과 비용감소 등의 이점이 있었다. This paper proposes the method of switching function implementation using switching function extraction based on graph over finite fields. After we deduce the matrix equation from path number of directional graph, we propose the switching function circuit algorithm, also we propose the code assignment algorithm for nodes which is satisfied the directional graph characteristics with designed circuits. We can implement more optimal switching function compare with former algorithm, also we can design the switching function circuit which have any natural number path through the proposed switching function circuit implementation algorithms. Also the proposed switching function implementation using graph theory over finite fields have decrement number of input-output, circuit construction simplification, increment arithmetic speed and decrement cost etc.

De Bruijn 그래프에 의한 다중처리기 구성

박춘명,Park, Chun-Myoung 한국정보통신학회 2006 한국정보통신학회논문지 Vol.10 No.12

본 논문에서는 De Bruijn그래프에 기초한 다중처리기 구성 방법에 대해 논의하였다. 유한체 상의 수학적 성질과 그래프의 성질을 사용하여 변환연산자에 대해 논의하였으며, 이들 변환연산자를 이용하여 De Buijn그래프의 변환표를 도출하였다. 그리고, 이 변환표로부터 유한체 상의 De Bruijn 그래프를 도출하였다. 제안한 다중처리기는 유한체 상에서의 임의 소수와 양의 정수에 대해 구성할 수 있으며 고장허용컴퓨팅 시스템, 파이프라인 시스템, 병렬처리 네트워크, 스위칭 함수와 이의 회로, 차세대 디지털논리 시스템 및 컴퓨터 구조 등에 적 용할 수 있다. This paper presents a method of constructing the universal multiple processing element unit(UMPEU) by De Bruijn Graph. The second method is as following. First, we propose transformation operators in order to construct the De Bruijn UMPEU using properties of graph. Second, we construct the transformation table of De Bruijn graph using above transformation operators. Finally we construct the De Bruijn graph using transformation table. The proposed UMPEU be able to construct the De Bruijn graph for any prime number and integer value of finite fields. Also the UMPEU is applied to fault-tolerant computing system, pipeline class. parallel processing network, switching function and its circuits.

결정도에 기초한 다중출력조합디지털논리시스템

박춘명,Park Chun-Myoung 한국정보통신학회 2005 한국정보통신학회논문지 Vol.9 No.6

본 논문에서는 TDBM과 CMTEDD를 사용하여 다중출력조합디지털논리시스템 설계방법의 한가지를 제안하였다. 또한, CBDD와 CMTEDD를 기반으로 최종 조합디지털논리시스템 구성을 멀티플렉서를 사용하여 구현하였다. 제안한 방법은 기존의 방법에 비해 모듈사이의 내부결선을 효과적으로 줄일 수 있으며 입력변수의 쌍과 출력함수의 쌍에 의해 게이트 수를 줄일 수 있는 장점이 있다. This paper presents a design method for multiple-output combinational digital logic systems using time domain based on multiplexing(TDBM) and common multi-terminal extension decision diagrams(CMTEDD). The CMIEDDs represents extension valued multiple-output functions, while TDBM systems transmit several signals on a single lines. The proposed method can reduce the 1)hardware, 2)logic levels and 3)pins. In the logic system design, we use two types of decision diagrams(DDs), that is the common binary decision diagrams(CBDDs) and CMTEDDs. Also, we propose an algorithms to derive common multiple-terminal binary decision diagrams(CMTBDD) from CBDDs, and CMTEDDs from CMTBDDs. The CMTEDDs over CBDDs is more compactness in terms of number of non-terminal nodes, where the nodes for output selection variables are not included in the non-terminal nodes. In the logic design, each non-terminal nodes of an CBDDs and an CMTEDDs is realized by a multiplexer(MUX). In addition, we compare the proposed TDBM realization with the conventional one.

개선된 자동정리증명 기법에 기초한 유한체상의 디지털논리시스템 구성

박춘명,Park, Chun-Myoung 한국정보통신학회 2006 한국정보통신학회논문지 Vol.10 No.10

본 논문에서는 개선된 자동정리증명 기법에 기초하여 유한체상의 디지털논리 시스템을 구성하는 방법을 제안하였다. 제안한 방법은 먼저 유한체상의 중요한 학적 성질을 논의하였고 자동정리증명기법의 개념과 기본 성질을 서술하였다. 그리고 개선된 자동정리증명기법을 적용하기 위해 몇 가지 정의를 하였으며 이를 근간으로 디지털논리 시스템의 Building Block을 제안하였다. 또한, 디지털논리 시스템을 구성하기 위한 중요한 관계를 정의하였으며 최종 유한체상의 디지털논리시스템을 개선된 자동정리 증명 기법에 의해 구성하였다. This paper propose the method of constructing the Digital Logic Systems based on the Improved Automatic Theorem Proving Techniques(IATP) over Finite Fields. The proposed method is as following. First, we discuss the background and the important mathematical properties for Finite Fields. Also, we discuss the concepts of the Automatic Theorem Proving Techniques(ATP) including the syntactic method and semantic method, and discuss the basic properties for the Alf. In this step, we define several definitions of the IAIP, Table Pseudo Function Tab and Equal. Next, we propose the T-gate as Building Block(BB) and describe the mathematical representation for the notation of T-gate. Then we discuss the important properties for the T-gate. Also, we propose the several relationships that are Identity relationship, Constant relationship, Tautology relationship and Mod R cyclic relationship. Then we propose Mod R negation gate and the manipulation of the don't care conditions. Finally, we propose the algorithm for the constructing the method of the digital logic systems over finite fields. The proposed method is more efficiency and regularity than my other earlier methods. Thet we prospect the future research and prospects.

유한체상의 순차디지털시스템 구성

박춘명,Park, Chun-Myoung 한국정보통신학회 2010 한국정보통신학회논문지 Vol.14 No.12

본 논문에서는 유한체상의 순차디지털시스템을 구성하는 방법을 제안하였다. 제안한 방법은 유한체의 성질로 부터 유한체상의 모든 원소를 디지트코드로 할당하는 알고리즘을 제안하였고, 유한체상의 순차디지털시스템을 구성하는데 사용하는 T-gate의 동작특성에 대해 논의하였으며, 이를 토대로 궤환이 없는 순차디지털시스템을 구성하였다. 이를 위해 상태천이도를 상태디지트코드로 할당하였고, 상태함수와 현재상태와 이전상태와의 관계를 나타내는 전순표를 도출하였다. 다음에 상태함수와 전순표로부터 다음상태함수를 도출하였으며, 이를 T-gate와 복호기를 시용하여 순차디지털시스템을 구성하였다. 제안한 방법으로 효과적이고 체계적으로 순차디지털시스템을 구성할 수 있었음을 확인하였다. This paper presents a method of constructing the sequential digital systems over finite fields. We assign all elements in finite fields to digit codes using mathematical properties of finite fields. Also, we discuss the operational characteristics and properties of the building block T-gate which is used to implement the sequential digital systems over finite fields. Then, we implemented sequential digital systems without feed-back. The sequential digital systems without feed-back is constructed as following steps. First, we assign the states in state-transition diagram to state digit codes, then obtain the state function and predecessor table which is explaining the relationship between present states and previous states. Next, we obtained the next-state function from state function and predecessor table. Finally we realize the circuit using T-gate and decoder. The proposed method is more efficiency and systematic than previous method.

PLA에 기초한 디지털논리스위칭함수 구성

박춘명,Park, Chun-Myoung 한국정보통신학회 2008 한국정보통신학회논문지 Vol.12 No.10

본 논문에서는 PLA를 사용하여 디지털논리 스위칭함수를 효과적으로 구성하는 방법을 제안하였다. 제안한 방법은 먼저 포스트 대수를 기반으로 MIN 대수연산과 MAX 대수연산을 제안하였고, 이를 구현하기 위해 T-gate에 대해 논의하였다. 그리고 PLA의 기본 회로인 MIN 배열, MAX 배열과 리터럴에 대해 논의하였다. PLA를 사용하여 디지털논리스위칭함수를 설계하기 위해 변수분할, 모듈러 구조, 리터럴 생성기, 복호기와 인버터를 제안하였다. 제안한 방법은 좀 더 콤펙트하고 확장성이 용이하다. This paper presents a method of constructing the digital logic switching functions using PLA. First of all, we propose a MIN and MAX algebra arithmetic operation based on the Post algebra. And we discuss the T-gate which is used for realization of the MIN and MAX algebra arithmetic operation. Next, we discuss the MIN array and MAX array which are basic circuit of the PLA, also we discuss the literal property. For the purpose of the design for the digital logic switching functions using PLA, we Propose the variable partition, modular structure design, literal generator, decoder and invertor. The proposed method is the more compactable and extensibility.

모서리값 확장 그래프를 사용한 함수구성에 관한연구

박춘명,Park, Chun-Myoung 한국정보통신학회 2013 한국정보통신학회논문지 Vol.17 No.4

본 논문에서는 최근의 디지털논리시스템의 함수구성시에 도입되고 있는 그래프이론에 바탕을 둔 새로운 형태의 데이터구조 형태인 모서리값 확장 그래프를 추출하는 알고리즘을 제안하였다. 이를 위해 수학적 배경으로는 리터럴 함수와 리드 뮬러 확장에 대해 논의하였으며, 본 논문의 근간인 모서리 확장 그래프의 도출에 대해 논의하였다. 또한, 모서리 확장 그래프로부터 임의의 m치 n변수의 축약된 함수구성을 도출하는 알고리즘을 제안하였으며 이를 예에 적용하여 그 타당성을 보였다. 제안된 알고리즘의 규칙성을 고려하여 동일부분을 모듈화함으로써 일반성을 가짐을 보였다. In recently years, many digital logic systems based on graph theory are analyzed and synthesized. This paper presented a method of constructing the function using edge valued extension graph which is based on graph theory. The graph is applied to a new data structure. from binary graph which is recently used in constructing the digital logic systems based on the graph theory. We discuss the mathematical background of literal and reed-muller expansion, and we discuss the edge valued extension graph which is the key of this paper. Also, we propose the algorithms which is the function derivation based on the proposed edge valued extension graph. That is the function minimization method of the n-variables m-valued functions and showed that the algorithm had the regularity with module by which the same blocks were made concerning about the schematic property of the proposed algorithm.

방향성 그래프에 기초한 분할연산 회로설계에 관한 연구

박춘명,Park, Chun-Myoung 한국정보통신학회 2013 한국정보통신학회논문지 Vol.17 No.9

본 논문에서는 방향성 그래프에 기초하여 절점들 간의 입출력 관계가 트리의 특성을 갖는 연관관계를 분할연산기법과 수학적 해석을 통하여 함수로 변환하고 이를 회로 설계하는 방법에 대하여 논의하였다. 기존에 제안된 알고리즘이 임의의 절점수를 갖는 방향성 그래프에 대하여 같은 수의 잉여절점수를 삽입함으로써 생성되는 매개변수들이 양의 정수로 표현되지 못하여 회로의 설계가 불가능하게 되는 문제점이 있었다. 이를 개선하기 위해서 본 논문에서는 트리의 성질을 수학적으로 해석하여 주어진 임의의 절점수를 가지는 방향성 그래프에 대하여 절점들의 관계를 규명해주는 매개변수들과 논리레벨 P의 승수로 표현되어 항상 양의 정수 값을 갖도록 레벨 간에 각기 다른 잉여절점을 삽입하여 효율적인 회로설계를 하였다. This paper present a method of efficiency circuit design based on directed graph which was represented by tree structure relationship between input and output of nodes. In this paper, we introduce the concept of mathematical analysis based on tree structure which was designed by optimal localized computable circuit. Using the proposed circuit design algorithms in this paper, it is possible to design circuit which directed tree graph have any node number. The proposed method is more effective, regularity and extensibility than former method.