지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2016.3
- 수록면
- 9 - 17 (9page)
- DOI
- 10.14801/jkiit.2016.14.3.9
이용수
초록· 키워드
오류제보하기
본 논문은 회로 최소화 문제에 대해 컴퓨터 프로그램에서 채택한 표 방식의 Quine-McCluskey 알고리즘(QMA)에 비해 보다 간단히 수행할 수 있는 알고리즘을 제안하였다. QMA는 주어진 함수의 각 항에 포함된 1의 개수에 대한 색인 집합으로 분류하고, 이웃 색인 집합 간 항을 반복적으로 병합하여 주 내포 항 (PI)를 추출하고, 중복된 PI를 삭제한다. 따라서 QMA의 PI 추출에 적용되는 색인 집합 병합은 변수 개수가 증가하면 병합 항이 기하급수적으로 증가하여 NP-난제로 분류되어 있다. 본 논문에서는 거리를 가진 주어진 부울 함수의 항 집합을 거리 1인 병합집합 과 독립집합으로 분할하고, 병합집합은 거리 2,4,8로 병합하고, 독립집합에 대해서는 거리 2,4,8의 병합 쌍을 찾아 다시 거리 4,8로 병합하여 정복하는 분할-정복 기법을 제안하였다. 제안된 알고리즘을 다양한 실험 데이터에 적용한 결과 QMA에 비해 동일한 결과를 얻으면서도 O(2<SUP>n</SUP>log n)의 다항시간으로 수행되어 수행횟수를 평균 66% 감소시킬 수 있었다.
목차
요약
Abstract
Ⅰ. 서론
Ⅱ. 관련 연구
Ⅲ. 거리기반 분할-정복 알고리즘
Ⅳ. 실험 및 결과 분석
Ⅴ. 결론
References
참고문헌 (15)
참고문헌 신청
V. Kabanets and J. Y. Cai, "Circuit Minimization Problem", Proceedings of 32nd Symposium on Theory of Computing, Portland, Oregon, USA, pp. 73-79, June 2000.
M. Karnaugh, "The Map Method for Synthesis of Combinational Logic Circuits", Transactions of the American Institute of Electrical Engineers, part I, Vol. 72, No. 9, pp. 593-599, Nov. 1953.
N. Sarkar, K. Petrus, and H. Hossain, "Software Implementation of the Quine-McCluskey Algorithm for Logic Gate Minimisation", Proceedings of the NACCQ, Napier, New Zealand, pp. 375-378, July 2001.
D. Belton, "Tabular Method of Minimization", http://www.ee.surrey.ac.uk/Projects/Labview/minimi sation/tabular.html, Department of Electronic Engi- neering, University of Surrey, Apr. 1998.
R. K. Brayton, G. D. Hachtel, C. McMullen, and A. L. Sangiovanni-Vincentelli, "Logic Minimization Algorithms for VLSI Synthesis", Springer, 1984.
M. Karnaugh, "The Map Method for Synthesis of Combinational Logic Circuits", Transactions of the American Institute of Electrical Engineers, part I, Vol. 72, No. 9, pp. 593-599, Nov. 1953.
N. Sarkar, K. Petrus, and H. Hossain, "Software Implementation of the Quine-McCluskey Algorithm for Logic Gate Minimisation", Proceedings of the NACCQ, Napier, New Zealand, pp. 375-378, July 2001.
D. Belton, "Tabular Method of Minimization", http://www.ee.surrey.ac.uk/Projects/Labview/minimi sation/tabular.html, Department of Electronic Engi- neering, University of Surrey, Apr. 1998.
R. K. Brayton, G. D. Hachtel, C. McMullen, and A. L. Sangiovanni-Vincentelli, "Logic Minimization Algorithms for VLSI Synthesis", Springer, 1984.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
선거구 획정 문제의 분할정복 알고리즘
한국컴퓨터정보학회논문지
2015 .12
-
유전 알고리즘과 분할 정복 기법을 결합한 수색 구조 유닛의 배치 방법
한국통신학회 인공지능 학술대회 논문집
2023 .09
-
Merging Unit 신호 분석 사례 연구
대한전기학회 학술대회 논문집
2017 .07
-
High-resolution Matting based on Divide-and-Conquer Method with Refined Trimap
한국컴퓨터그래픽스학회 학술대회
2017 .07
-
Merging Unit의 샘플링 주파수 변조
대한전기학회 학술대회 논문집
2022 .11
-
Full 디지털변전소 Merging Unit 개발 및 실증 연구
대한전기학회 학술대회 논문집
2024 .07
-
Numerical investigations of droplet merging in the microchannel
대한기계학회 춘추학술대회
2016 .12
-
CMP 장비의 초 고압(800g/cm²) 조건에서 구조 특성에 관한 연구
한국정밀공학회 학술발표대회 논문집
2015 .12
-
디지털변전소 Merging Unit의 상호 운용성에 관한 연구
대한전기학회 학술대회 논문집
2024 .07
-
현무암과 포놀라이트 비정질 규산염의 원자구조 차이에 대한 고상핵자기 공명 분광분석 연구
한국광물학회지
2015 .01
-
Stackelberg 게임이론을 활용한 자율주행차 차선병합 전략 개발
한국자동차공학회 추계학술대회 및 전시회
2020 .11
-
Cross-Component Merge 리스트 후보 구성 순서가 정확도에 미치는 영향 분석
한국방송미디어공학회 학술발표대회 논문집
2024 .06
-
HEVC 부호화기를 위한 Merge Mode 연산량 감소 방법
대한전자공학회 학술대회
2015 .11
-
다중 경로 특징점 융합 기반의 의미론적 영상 분할 기법
한국통신학회 학술대회논문집
2019 .01
-
1D Divide-and-Conquer Sum Apart Multiplication의 고속 구현 및 성능 분석
대한전자공학회 학술대회
2022 .11
-
Full-Digital 변전소 Process Bus용 Merging Unit 개발
대한전기학회 학술대회 논문집
2022 .07
-
최대 클릭 문제의 분할정복 알고리즘
한국정보기술학회논문지
2015 .06
-
아마존웹서비스_‘인프라부터 서비스까지’ 생성형 AI 정복 겨눈 AWS
전자기술
2024 .01
-
고분자 결함 구조에 따른 CMP pad의 표면 형상 및 CMP 성능 변화 연구
한국트라이볼로지학회 학술대회
2019 .04
-
Process Bus 구축을 위한 IEC61850기반의 Merging Unit 개발
대한전기학회 학술대회 논문집
2020 .07
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2016-566-002620175