Reed-Muller 전개식에 의한 다치 논리회로의 구성에 관한 연구

성현경,Seong, Hyeon-Kyeong 한국정보처리학회 2007 정보처리학회논문지 A Vol.14 No.2

본 논문에서는 Reed-Muller 전개식에 의한 다치 논리 회로의 구성에 관한 한 가지 방법을 제시하였다. 먼저, Perfect Shuffle 기법과 Kronecker 곱에 의한 다치 논리함수의 입출력 상호연결에 대하여 논하였고, GF(4)의 가산회로와 승산회로를 이용하여 다치 Reed-Muller 전개식의 변환행렬과 역변환행렬을 실행하는 기본 셀을 설계하였다. 이 기본 셀들과 Perfect Shuffle과 Kronecker 곱에 의한 입출력 상호연결 방법을 이용하여 다치 Reed-Muller 전개식에 의한 다치 논리 회로를 구현하였다. 제시된 다치 Reed-Muller 전개식의 설계방법은 모듈구조를 기반으로 하여 행렬변환을 이용하므로 동일한 함수에 대하여 타 방법과 비교하여 간단하고 회로의 가산회로와 증산회로를 줄이는데 매우 효과적이다. 제안된 다치 논리회로의 설계방법은 회선경로 선택의 규칙성, 간단성, 배열의 모듈성과 병렬동작의 특징을 가진다. In this paper, we present a method on the construction of multiple-valued circuits using Reed-Muller Expansions(RME). First, we discussed the input output interconnection of multiple valued function using Perfect Shuffle techniques and Kronecker product and designed the basic cells of performing the transform matrix and the reverse transform matrix of multiple valued RME using addition circuit and multiplication circuit of GF(4). Using these basic cells and the input-output interconnection technique based on Perfect Shuffle and Kronecker product, we implemented the multiple valued logic circuit based on RME. The proposed design method of multiple valued RME is simple and very efficient to reduce addition circuits and multiplication circuits as compared with other methods for same function because of using matrix transform based on modular structures. The proposed design method of multiple valued logic circuits is simple and regular for wire routing and possess the properties of concurrency and modularity of array.

GF($2^m$)상의 셀배열 승산기의 구성

성현경,김흥수,Seong, Hyeon-Kyeong,Kim, Heung-Soo 대한전자공학회 1989 전자공학회논문지 Vol. No.

본 논문에서는 유한체 GF($2^m$) 상에서 두 원소들의 승산을 실현하는 셀배열승산기를 제시한다. 이 승산기는 승산연산부, mod연산부, 원시기약 다항식연산부로 구성한다. 승산연산부는 AND와 XOR게이트로 설계한 기본셀의 배열을 이루며, mod연산부 역시 AND와 XOR게이트에 의한 기본셀을 배열하여 구성하였다. 원시 기약다항식 연산부는 XOR게이트들, D플립플롭 회로들과 한개의, NOT게이트를 사용하여 구성하였다. 본 논문에서 제시한 승산기는 회선경로선택의 규칙성, 간단성, 배열의 모듈성과 병발성의 특징을 가지며 특히 차수 m이 증가하는 유한체의 두 원소들의 승산에서 확장성을 가지므로 VLSI 실현에 적합하다. A cellular array multiplier for performing the multiplication of two elements in the finite field GF($2^m$) is presented in this paper. This multiplier is consisted of three operation part ; the multiplicative operation part, the modular operation part, and the primitive irreducible polynomial operation part. The multiplicative operation part and the modular operation part are composed by the basic cellular arrays designed AND gate and XOR gate. The primitive iirreducible operation part is constructed by XOR gates, D flip-flop circuits and a inverter. The multiplier presented here, is simple and regular for the wire routing and possesses the properties of concurrency and modularity. Also, it is expansible for the multiplication of two elements in the finite field increasing the degree m and suitable for VLSI implementation.

유한체 $GF(2^m)$상의 비트-병렬 곱셈기의 설계

성현경,Seong, Hyeon-Kyeong 한국정보통신학회 2008 한국정보통신학회논문지 Vol.12 No.7

In this paper, we present a new bit-parallel multiplier for performing the bit-parallel multiplication of two polynomials in the finite fields $GF(2^m)$. Prior to construct the multiplier circuits, we consist of the vector code generator(VCG) to generate the result of bit-parallel multiplication with one coefficient of a multiplicative polynomial after performing the parallel multiplication of a multiplicand polynomial with a irreducible polynomial. The basic cells of VCG have two AND gates and two XOR gates. Using these VCG, we can obtain the multiplication results performing the bit-parallel multiplication of two polynomials. Extending this process, we show the design of the generalized circuits for degree m and a simple example of constructing the multiplier circuit over finite fields $GF(2^4)$. Also, the presented multiplier is simulated by PSpice. The multiplier presented in this paper use the VCGs with the basic cells repeatedly, and is easy to extend the multiplication of two polynomials in the finite fields with very large degree m, and is suitable to VLSI. 본 논문에서는 $GF(2^m)$ 상에서 표준기저를 사용한 두 다항식의 곱셈을 비트-병렬로 실현하는 새로운 형태의 비트-병렬 곱셈기를 제안하였다. 곱셈기의 구성에 앞서, 피승수 다항식과 기약다항식의 곱셈을 병렬로 수행 한 후 승수 다항식의 한 계수와 비트-병렬로 곱셈하여 결과를 생성하는 VCG를 구성하였다. VCG의 기본 셀은 2개의 AND 게이트와 2개의 XOR 게이트로 구성되며, 이들로부터 두 다항식의 비트-병렬 곱셈을 수행하여 곱셈 결과를 얻도록 하였다. 이러한 과정을 확장하여 m에 대한 일반화된 회로의 설계를 보였으며, 간단한 형태의 곱셈회로 구성의 예를 $GF(2^4)$를 통해 보였다. 또한 제시한 곱셈기는 PSpice 시뮬레이션을 통하여 동작특성을 보였다. 본 논문에서 제안한 곱셈기는 VCG의 기본 셀을 반복적으로 연결하여 구성하므로, 차수 m이 매우 큰 유한체상의 두 다항식의 곱셈에서 확장이 용이하며, VLSI에 적합하다.

Reed-Muller 전개식에 의한 3치 논리회로의 설계

성현경,Seong, Hyeon-Kyeong 한국정보통신학회 2007 한국정보통신학회논문지 Vol.11 No.3

본 논문에서는 Reed-Muller 전개식에 의한 3치 논리 회로를 설계하는 한 가지 방법을 제시하였다. 제시된 3치 논리 회로의 설계 방법은 Reed-Muller 전개식의 계수에 대하여 모든 변수의 차수를 검사하여 RME 모듈(Reed-Muller Expansions module)의 수를 최소화하는 최적의 제어 입력 변수의 순서를 결정한다. 최적의 제어 입력 변수의 순서는 회로 비용 행렬의 계산에 사용되며, 이 회로 비용 행렬의 계산 결과를 이용하여 Reed-Muller 전개식에 의한 RME 모듈의 나무 구조의 3치 논리 회로를 설계한다. 제시된 방법은 최적 제어 입력 변수를 찾는데 유일하게 단위시간 내에 수행되며, 컴퓨터 프로그램이 가능하고, 프로그래밍 수행 시간이 $3^n$이다. In this paper, we present a design method of the ternary logic circuits based on Reed-Muller expansions. The design method of the presented ternary logic circuits checks the degree of each variable for the coefficients of Reed-Holler Expansions(RME) and determines the order of optimal control input variables that minimize the number of Reed-Muller Expansions modules. The order of optimal control input variables is utilized the computation of circuit cost matrix. The ternary logic circuits of the minimized tree structures to be constructed by RME modules based on Reed-Muller Expansions are realized using the computation results of its circuit cost matrix. This method is only performed under unit time in order to search for the optimal control input variables. Also, this method is able to be programmed by computer and the run time on programming is $3^n$.

유한체 GF(2^m)상의 셀 배열 병렬 승산기의 설계

성현경,Seong, Hyeon-Kyeong 한국정보처리학회 2004 정보처리학회논문지 A Vol.11 No.1

본 논문에서는 유한체 GF$(2^m)$상에서 두 다항식의 승산을 실현하는 병렬-입력 및 병렬-출력을 갖는 셀 배열 병렬 승산기를 제시한다 이 승산기는 승산연산부, 기약다항식연산부. MOD연산부로 구성한다. 승산연산부는 AND 게이트와 XOR 게이트로 설계한 기본 셀의 배열로 이루어지며, 기약다항식연산부는 XOR 게이트와 D 플림플롭회로를 사용하여 구성하며, MOD연산부는 AND 게이트와 XOR 게이트에 의한 기본 셀을 배열하여 구성하였다. 제시한 승산기는 PSpice 시뮬레이션을 통하여 동작특성을 보였으며, 클럭신호의 주기를 l${\mu}\textrm{s}$로 하였다. 제시한 셀 배열 병렬 승산기는 m=4인 경우에 AND 게이트의 수가 24개, XOR 게이트의 수가 32개 필요하며, D 플립플롭회로가 4개 필요하다. 또한, AOP 기약 다항식을 사용하면 AND 게이트와 XOR 게이트의 수가 24개 필요하며 D 플립플롭은 사용되지 않는다. 셀 배열 병렬 승산기의 승산연산부의 동작시간은 1 단위시간(클럭시간)이 소비되고, 기약다항식연산부에 의한 MOD연산부의 동작시간은 m 단위시간(클럭시간)이 소비되어 전체 동작시간은 m+1 단위시간(클럭시간)이 소비된다. 본 논문에서 제시한 셀 병렬 승산기는 회선경로 선택의 규칙성, 간단성, 배열의 모듈성과 병렬동작의 특징을 가지며, 특히 차수 m이 매우 큰 유한체강의 두 다항식의 승산에서 확장성을 갖는다. A cellular array parallel multiplier with parallel-inputs and parallel-outputs for performing the multiplication of two polynomials in the finite fields GF$(2^m)$ is presented in this paper. The presented cellular way parallel multiplier consists of three operation parts: the multiplicative operation part (MULOP), the irreducible polynomial operation part (IPOP), and the modular operation part (MODOP). The MULOP and the MODOP are composed if the basic cells which are designed with AND Bates and XOR Bates. The IPOP is constructed by XOR gates and D flip-flops. This multiplier is simulated by clock period l${\mu}\textrm{s}$ using PSpice. The proposed multiplier is designed by 24 AND gates, 32 XOR gates and 4 D flip-flops when degree m is 4. In case of using AOP irreducible polynomial, this multiplier requires 24 AND gates and XOR fates respectively. and not use D flip-flop. The operating time of MULOP in the presented multiplier requires one unit time(clock time), and the operating time of MODOP using IPOP requires m unit times(clock times). Therefore total operating time is m+1 unit times(clock times). The cellular array parallel multiplier is simple and regular for the wire routing and have the properties of concurrency and modularity. Also, it is expansible for the multiplication of two polynomials in the finite fields with very large m.

전류모드 CMOS에 의한 3치 가산기 및 승산기의 구현

성현경,Seong, Hyeon-Kyeong 한국정보통신학회 2009 한국정보통신학회논문지 Vol.13 No.9

본 논문에서는 전류모드 CMOS에 의한 2변수 3치 가산기 회로와 승산기 회로를 구현하였다. 제시된 전류모드 CMOS에 의한 3치 가산기 회로와 승산기 회로는 전압 레벨로 동작하며, HSpice 시뮬레이션을 통하여 이 회로들에 대하여 동작 특성을 보였다. 제시 된 회로들은 $0.180{\mu}m$ CMOS 표준 기술을 사용하여 HSpice로 시뮬레이션 하였다. 2 변수 3치 가산기 및 승산기 회로의 단위 전류 $I_u$는 $5{\mu}A$로 하였으며, NMOS의 길이와 폭 W/L는 $0.54{\mu}m/0.18{\mu}m$이고, PMOS의 길이와 폭 W/L는 $1.08{\mu}m/0.18{\mu}m$이다. VDD 전압은 2.5V를 사용하였으며 MOS 모델은 LEVEL 47으로 시뮬레이션 하였다. 전류모드 CMOS 3치 가산기 및 승산기 회로의 시뮬레이션 결과에서 전달 지연 시간이 $1.2{\mu}s$이며, 3치 가산기 및 승산기 회로가 안정하게 동작하여 출력 신호를 얻는 동작 속도가 300MHz, 소비 전력이 1.08mW임을 보였다. In this paper, the circuit of 2 variable ternary adder and multiplier circuit using current mode CMOS are implemented. The presented ternary adder circuit and multiplier circuit using current mode CMOS are driven the voltage levels. We show the characteristics of operation for these circuits simulated by HSpice. These circuits are simulated under $0.18{\mu}m$ CMOS standard technology, $5{\mu}A$ unit current in $0.54{\mu}m/0.18{\mu}m$ ratio of NMOS length and width, and $0.54{\mu}m/0.18{\mu}m$ ratio of PMOS length and width, and 2.5V VDD voltage, MOS model Level 47 using HSpice. The simulation results show the satisfying current characteristics. The simulation results of current mode ternary adder circuit and multiplier circuit show the propagation delay time $1.2{\mu}s$, operating speed 300KHz, and consumer power 1.08mW.

VCG를 사용한 GF(2^m)상의 고속병렬 승산기 설계에 관한 연구

성현경,Seong, Hyeon-Kyeong 한국정보통신학회 2010 한국정보통신학회논문지 Vol.14 No.3

In this paper, we present a new type high speed parallel multiplier for performing the multiplication of two polynomials using standard basis in the finite fields GF($2^m$). Prior to construct the multiplier circuits, we design the basic cell of vector code generator(VCG) to perform the parallel multiplication of a multiplicand polynomial with a irreducible polynomial and design the partial product result cell(PPC) to generate the result of bit-parallel multiplication with one coefficient of a multiplicative polynomial with VCG circuits. The presented multiplier performs high speed parallel multiplication to connect PPC with VCG. The basic cell of VCG and PPC consists of one AND gate and one XOR gate respectively. Extending this process, we show the design of the generalized circuits for degree m and a simple example of constructing the multiplier circuit over finite fields GF($2^4$). Also, the presented multiplier is simulated by PSpice. The multiplier presented in this paper uses the VCGs and PPCS repeatedly, and is easy to extend the multiplication of two polynomials in the finite fields with very large degree m, and is suitable to VLSL. 본 논문에서는 GF($2^m$)상의 표준기저를 사용한 새로운 형태의 VCG에 의한 고속병렬 승산회로를 제안하였다. 승산기의 구성에 앞서, 피승수 다항식과 기약다항식의 승산을 병렬로 수행하는 벡터 코드 생성기(VCG) 기본 셀을 설계하였고, VCG 회로와 승수 다항식의 한 계수와 비트-병렬로 승산하여 결과를 생성하는 부분 승산결과 셀(PPC)를 설계하였다. 제안한 승산기는 VCG와 PPC를 연결하여 고속의 병렬 승산을 수행한다. VCG 기본 셀과 PPC는 각각 1개의 AND 게이트와 1개의 XOR 게이트로 구성된다. 이러한 과정을 확장하여 m에 대한 일반화된 회로의 설계를 보였으며, 간단한 형태의 승산회로 구성의 예를 GF($2^4$)를 통해 보였다. 또한 제시한 승산기는 PSpice 시뮬레이션을 통하여 동작특성을 보였다. 본 논문에서 제안한 승산기는 VCG와 PPC을 반복적으로 연결하여 구성하므로, 차수 m이 매우 큰 유한체상의 두 다항식의 곱셈에서 확장이 용이하며, VLSI에 적합하다.

Perfect Shuffle에 의한 5치 논리회로의 구성에 관한 연구

성현경,Seong, Hyeon-Kyeong 한국정보통신학회 2011 한국정보통신학회논문지 Vol.15 No.3

본 논문에서는 Perfect Shuffle에 의한 5치 논리 회로의 구성에 관한 한 가지 방법을 제시하였다. 먼저, Perfect Shuffle 기법과 Kronecker 곱에 의한 5치 논리함수의 입출력 상호연결에 대하여 논하였고, GF(5)의 가산회로와 승산회로를 이용하여 5치 Reed-Muller 전개식의 변환행렬과 역변환행렬을 실행하는 기본 셀을 설계하였다. 이 기본 셀들과 Perfect Shuffle과 Kronecker 곱에 의한 입출력 상호연결 방법을 이용하여 5치 Reed-Muller 전개식에 의한 5치 논리 회로를 구현하였다. 제시된 5치 Reed-Muller 전개식의 설계방법은 모듈구조를 기반으로 하여 행렬변환을 이용하므로 동일한 함수에 대하여 타 방법과 비교하여 간단하고 회로의 가산회로와 승산회로를 줄이는데 매우 효과적이다. 제안된 5치 논리회로의 설계방법은 회선경로 선택의 규칙성, 간단성, 배열의 모듈성과 병렬동작의 특징을 가진다. In this paper, we present a method on the construction of quinternary logic circuits using Perfect shuffle. First, we discussed the input-output interconnection of quinternary logic function using Perfect Shuffle techniques and Kronecker product, and designed the basic cells of performing the transform matrix and the reverse transform matrix of quinternary Reed-Muller expansions(QRME) using addition circuit and multiplication circuit of GF(5). Using these basic cells and the input-output interconnection technique based on Perfect Shuffle and Kronecker product, we implemented the quinternary logic circuit based on QRME. The proposed design method of QRME is simple and very efficient to reduce addition circuits and multiplication circuits as compared with other methods for same logic function because of using matrix transform based on modular structures. The proposed design method of quinternary logic circuits is simple and regular for wire routing and possess the properties of concurrency and modularity of array.

전류모드 CMOS에 의한 다치 연산기 구현에 관한 연구

성현경,윤광섭,Seong, Hyeon-Kyeong,Yoon, Kwang-Sub 대한전자공학회 1999 電子工學會論文誌, C Vol.c36 No.8

본 논문에서는 $GF(p^m)$상에서 두 다항식의 가산 및 승산 알고리즘을 제시하였고, 가산 및 승산 알고리즘을 수행하는 전류 모드 CMOS에 의한 $GF(4^3)$상의 직렬 입력-병렬 출력 모듈 구조의 4치 연산기를 구현하였다. 제시된 전류 모드 CMOS 4치 연산기는 가산/승산 선택 회로, mod(4) 승산 연산 회로, mod(4) 가산 연산 회로를 2개 연결하여 구성한 MOD 연산회로, mod(4) 승산 연산 회로와 동일하게 동작하는 원시 기약 다항식 연산 회로에 의해 구현하였으며, PSpice 시뮬레이션을 통하여 이 회로들에 대하여 동작 특성을 보였다. 제시된 회로들의 시뮬레이션은 $2{\mu}m$ CMOS 기술을 이용하고, 단위 전류를 $15{\mu}A$로 하였으며, VDD 전압은 3.3V을 사용하였다. 본 논문에서 제시한 전류 모드 CMOS의 4치 연산기는 회선 경로 선택의 규칙성, 간단성, 셀 배열에 의한 모듈성의 이점을 가지며, 특히 차수 m이 증가하는 유한체상의 두 다항식의 가산 및 승산에서 확장성을 가지므로 VLSI화 실현에 적합할 것으로 생각된다. In this paper, the addition and the multiplicative algorithm of two polynomials over finite field $GF(p^m)$ are presented. The 4-valued arithmetic processor of the serial input-parallel output modular structure on $GF(4^3)$ to be performed the presented algorithm is implemented by current mode CMOS. This 4-valued arithmetic processor using current mode CMOS is implemented one addition/multiplication selection circuit and three operation circuits; mod(4) multiplicative operation circuit, MOD operation circuit made by two mod(4) addition operation circuits, and primitive irreducible polynomial operation circuit to be performing same operation as mod(4) multiplicative operation circuit. These operation circuits are simulated under $2{\mu}m$ CMOS standard technology, $15{\mu}A$ unit current, and 3.3V VDD voltage using PSpice. The simulation results have shown the satisfying current characteristics. The presented 4-valued arithmetic processor using current mode CMOS is simple and regular for wire routing and possesses the property of modularity. Also, it is expansible for the addition and the multiplication of two polynomials on finite field increasing the degree m and suitable for VLSI implementation.

전류모드 CMOS에 의한 다치 가산기 및 승산기의 구현

성현경,Seong, Hyeon-Kyeong 한국정보처리학회 2004 정보처리학회논문지 A Vol.11 No.2

본 논문에서는 전류모드 CMOS를 사용하여 다치 가산기 및 다치 승산기를 구현하였으며, 먼저 효과적인 집적회로 설계 이용성을 갖는 전류모드 CMOS를 사용하여 3치 T-게이트와 4치 T-게이트를 구현하였다. 구현된 다치 T-게이트를 조합하여 유한체 $GF(3^2)$의 2변수 3치 가산표와 승산표를 실현하는 회로를 구현하였으며, 이들 다치 T-게이트를 사용하여 유한체 $GF(4^2)$의 2변수 4치 가산표와 승산표를 실현하는 회로를 구현하였다. 또한, Spice 시뮬레이션을 통하여 이 회로들에 대한 동자특성을 보였다. 다치 가산기 및 승산기들은 $1.5\mutextrm{m}$ CMOS 표준 기술의 MOSFET 모델 LEVEL 3을 사용하였고, 단위전류는 $15\mutextrm{A}$로 하였으며, 전원전압은 3.3V를 사용하였다. 본 논문에서 구현한 전류모드 CMOS의 3치 가산기와 승산기, 4치 가산기와 승산기는 일정한 회선경로 선택의 규칙성, 간단성, 셀 배열에 의한 모듈성의 이점을 가지며 특히 차수 m이 증가하는 유한체의 두 다항식의 가산 및 승산에서 확장성을 가지므로 VLSI화 실현에 적합한 것으로 생각된다. In this paper, the multiple-valued adders and multipliers are implemented by current-mode CMOS. First, we implement the 3-valued T-gate and the 4-valued T-gate using current-mode CMOS which have an effective availability of integrated circuit design. Second we implement the circuits to be realized 2-variable 3-valued addition table and multiplication table over finite fields $GF(3^2)$, and 2-variable 4-valued addition table and multiplication table over finite fields $GF(4^2)$ with the multiple-valued T-gates. Finally, these operation circuits are simulated under $1.5\mutextrm{m}$ CMOS standard technology, $15\mutextrm{A}$ unit current, and 3.3V VDD voltage Spice. The simulation results have shown the satisfying current characteristics. The 3-valued adder and multiplier, and the 4-valued adder and multiplier implemented by current-mode CMOS is simple and regular for wire routing and possesses the property of modularity with cell array. Also, since it is expansible for the addition and multiplication of two polynomials in the finite field with very large m, it is suitable for VLSI implementation.